Purser M. Introduction to Error Correcting Codes
Подождите немного. Документ загружается.
BCH codes
error correction
of
binary, 53-58
error correction
of
non binary, 58-59
examples of, 51-52
minimum polynomials in, 47--48
Reed-Solomon codes, 59-67
roots of, 48-51
Berlekamp-Massey algorithm, 58, 125-27
Binary Erasure Channel, 6
Binary information units (bits), 96
Binary symmetric channel (BSC),
III
Binomial approximations, 113-16
B it strings,
1-7
Block codes, 7
and convolutional codes, 91-93
Bose-Chaudhuri-Hocquenghem codes.
See BCH codes
BSC (binary symmetric channel),
III
Bursts,
of
errors,
6--7
Capacity,
of
channel,
110
Closed code,
12
Code(s)
BCH. See BCH codes
bit strings and, 1-7
block, 7, 91-93
closed,
12
convolutional. See Convolutional codes
cyclic. See Cyclic codes
and
error correction,
3-5
Golay,
18,38
immediate, 97
linear. See Linear codes
perfect, 18-19
Reed-Solomon,
29,
59--67
repetition, 18-19
Index
131
tree and trellis, 69-72
Code-distance, 7
Code rate, 8
Codevectors, 3
Codewords, 3
Columns,
of
null matrix, 17-18
Constraint length,
70
Convolutional codes
analysis of, 78-81
block codes and, 91-93
control
of
decoding errors with,
77-78
defined,
73
error correcting with, 81-91
feedback decoding with, 86--89
linear, 72-78
sequential decoding with, 85-86
soft-decision decoding with, 84-85
syndrome decoding with, 87-91
tree and trellis codes, 69-72
Correlated sources, 102-107
Cosets,
12
Cyclic codes
defined,32
error correction with, 42--44
error detection with, 38--42
generating polynomial for, 31-35
nonbinary, 44-46
roots
of
generating polynomial and null
matrix in, 35-37
shortened,
40--42
systematic, 33-35
weight distributions of, 39--40
Decoding
feedback, 86--89
sequential, 85-86
132
Decoding (cont.)
soft-decision,
5-7,
84--85
syndrome, 89-91
Decoding errors, control of, 77-78
Delay operator, 76
Detectable errors, 24--25
Distance,
of
linear code,
17
Entropy, 96
of
correlated source, 102
Equivocation, 108,
III
Erasures,
5-7
Error(s)
bursts of,
6--7
detectable, 24--25
postdecoding,
80-81
Error correction
with binary BCH codes, 53-58
codes and,
3-5
with convolutional codes, 81-91
with cyclic codes,
42-44
forward,4
with nonbinary BCH codes, 58-59
Error detection, with cyclic codes, 38--42
Error locator,
53
Error-recovery, by detection and retransmission, 4
Feedback decoding, with convolutional
codes, 86--89
Feedback shift registers,
40--42
Field(s), 117
finite,
II,
117-24
Forward error correction (FEC), 4
Generating polynomial, 31-35
roots of, and null matrix, 35-37
Generator matrix, 13-14
Golay code,
18,38
Hamming distance,
7-8
Ideal,31
Immediate code, 97
Information
associated with event,
95-96
average, 96
maximum, 96--97
mutual,
109,
III
in transit, 107-111
Information rate,
107
Information theory
correlated sources in,
102-107
information, entropy, redundancy, and
compression in,
95-102
information in transit in, 107-11
Information units, binary, 96
Interleaved
RS code,
63--{)4
Kasami method, 42--43
Linear codes
bounds in practice on, 23-25
convolutional,72-78
distance of,
17
matrix representation for, 11-14
nonbinary,
25-29
null matrix or parity-check matrix for,
14--18
perfect codes in,
18-19
Plotkin bound on, 20-23
Varsharmov-Gilbert bound on,
19-20
Matrix
generator, 13-14
null,
14--18
parity,
13
parity-check, 14--18
representation of, 11-14
Metric,
83
Minimum polynomials, in BCH codes, 47--48
Minimum weight,
12
Mutual information, 109,
111
Nonbinary BCH codes, error correction
of,58-59
Nonbinary cyclic codes, 44--46
Nonbinary linear codes,
25-29
Null matrix, 14--18
columns of, 17-18
roots
of
generating polynomial and, 35-37
Nullspace,
14
Parity-check matrix, 14--18
Parity matrix,
13
Perfect codes, 18-19
Plotkin bound, 20-23
Postdecoding errors, 80-81
Preamble,
72
Redundancy,2-3,97
Reed-Solomon (RS) codes, 29,
59--f,7
interleaved, 63--f,4
nearness to bounds of, 65--f,7
practical use of, 62--f,4
weight distribution of, 64--65
worked example of, 60--f,2
Reliability factor, 6
Repetition codes,
18-19
Residual error rate, 64
Retransmission, error-recovery by, 4
Roots
ofBCH
codes, 48-51
consecutive,
48
of
cyclic codes, 35-37
RS
codes. See Reed-Solomon (RS) codes
Sequential decoding, with convolutional
codes,
85-86
Shannon's theorem, 8-10
Soft-decision decoding,
5-7
with convolutional codes, 84-85
Sources, correlated, 102-7
Sphere-packing,
7-8
Standard array,
12
Subspace,
12
Syndrome, 15-17
Syndrome decoding, with convolutional
codes,
87-91
Tree codes, 69-72
Trellis codes, 69-72
Varsharrnov-Gilbert bound, 19-20
Viterbi algorithm, 70-72
Weight,
of
linear code,
17
Weight distributions
of
cyclic codes, 39-40
of
Reed-Solomon code, 64-65
133