S72.3410 Linear Codes (1) 1
'
&
$
%
Block Codes
block code A code C that consists of words of the form
(c
0
, c
1
, . . . , c
n−1
), where n is the number of coordinates (and is
said to be the length of the code).
qary code A code whose coordinate values are taken from a set
(alphabet) of size q (unless otherwise stated, GF(q)).
encoding Breaking the data stream into blocks, and mapping
these blocks onto codewords in C.
The encoding process is depicted in [Wic, Fig. 41].
c
72.3410 Linear Codes (1) 1
'& $ %
Block Codes
block code
A code
C
that consists of words of the form(
c
0
,c
1
,...,c
n
−
1
), where
n
is the number of
coordinates
(and issaid to be the
length
of the code).
q
ary code
A code whose coordinate values are taken from a set(alphabet) of size
q
(unless otherwise stated, GF(
q
)).
encoding
Breaking the data stream into blocks, and mappingthese blocks onto codewords in
C
.The encoding process is depicted in [Wic, Fig. 41].
c
Patric¨Osterg˚ard72.3410 Linear Codes (1) 2
'& $ %
Redundancy
If the data blocks of a
q
ary code are of length
k
, then there are
M
=
q
k
possible data vectors. (But all data blocks are notnecessarily of the same length.)There are
q
n
possible words of length
n
, out of which
q
n
−
M
arenot valid codewords. The
redundancy
r
of a code is
r
=
n
−
log
q
M,
which simpliﬁes to
r
=
n
−
k
if
M
=
q
k
.
c
Patric¨Osterg˚ard72.3410 Linear Codes (1) 3
'& $ %
Code Rate
The redundancy is frequently expressed in terms of the code rate.The
code rate
R
of a code C of size
M
and length
n
is
R
=log
q
M n.
Again, if
M
=
q
k
,
R
=
k/n
.
c
Patric¨Osterg˚ard72.3410 Linear Codes (1) 4
'
& $ %
Transmission Errors
The corruption of a codeword by channel noise, modeled as anadditive process, is shown in [Wic, Fig. 42].
error detection
Determination (by the error control decoder)whether errors are present in a received word.
undetectable error
An error pattern that causes the receivedword to be a valid word other than the transmitted word.
error correction
Determine which of the valid codewords is mostlikely to have been sent.
decoder error
In error correction, selecting a codeword otherthan that which was transmitted.
c
Patric¨Osterg˚ard
72.3410 Linear Codes (1) 5
'& $ %
Error Control
The decoder may react to a detected error with one of the followingthree responses:
automatic repeat request (ARQ)
Request a retransmission of the word. For applications where data reliability is of greatimportance.
muting
Tag the word as being incorrect and pass it along. Forapplications in which delay constraints do not allow forretransmission (for example, voice communication).
forward error correction (FEC)
(Attempt to) correct theerrors in the received word.
c
Patric¨Osterg˚ard72.3410 Linear Codes (1) 6
'& $ %
Weight and Distance (1)
The
(Hamming) weight
of a word
c
, denoted by
w
(
c
) (or
w
H
(
c
)), is the number of nonzero coordinates in
c
.
Example.
w
((0
,α
3
,
1
,α
)) = 3,
w
(0001) = 1.The
Euclidean distance
between
v
= (
v
0
,v
1
,...,v
n
−
1
) and
w
= (
w
0
,w
1
,...,w
n
−
1
) is
d
E
(
v
,
w
) =
(
v
0
−
w
0
)
2
+ (
v
1
−
w
1
)
2
+
···
+ (
v
n
−
1
−
w
n
−
1
)
2
.
c
Patric¨Osterg˚ard72.3410 Linear Codes (1) 7
'& $ %
Weight and Distance (2)
The
Hamming distance
between two words,
v
= (
v
0
,v
1
,...,v
n
−
1
) and
w
= (
w
0
,w
1
,...,w
n
−
1
), is the number of coordinates in which they diﬀer, that is,
d
H
(
v
,
w
) =
{
i

v
i
=
w
i
,
0
≤
i
≤
n
−
1
}
,
where the subscript
H
is often omitted. Note that
w
(
c
) =
d
(
0
,
c
),where
0
is the allzero vector, and
d
(
v
,
w
) =
w
(
v
−
w
).The
minimum distance
of a block code
C
is the minimumHamming distance between all pairs of distinct codewords in
C
.
c
Patric¨Osterg˚ard72.3410 Linear Codes (1) 8
'
& $ %
Minimum Distance and Error Detection
Let
d
min
denote the minimum distance of the code in use. For anerror pattern to be undetectable, it must change the values in atleast
d
min
coordinates.
A code with minimum distance
d
min
can detect
all
errorpatterns of weight less than
d
min
.Obviously, a large number of error patterns of weight
w
≥
d
min
canalso be detected.
c
Patric¨Osterg˚ard
72.3410 Linear Codes (1) 9
'& $ %
Forward Error Correction
The goal in FEC systems is to minimize the probability of decodererror given a received word
r
. If we know exactly the behavior of the communication system and channel, we can derive theprobability
p
(
c

r
) that
c
is transmitted upon receipt of
r
.
maximum a posteriori decoder
(MAP decoder) Identiﬁes thecodeword
c
i
that maximizes
p
(
c
=
c
i

r
).
maximum likelihood decoder
(ML decoder) Identiﬁes thecodeword
c
i
that maximizes
p
(
r

c
=
c
i
).
Bayes’s rule
p
(
c

r
) =
p
C
(
c
)
p
(
r

c
)
p
R
(
r
)
.
c
Patric¨Osterg˚ard72.3410 Linear Codes (1) 10
'& $ %
Minimum Distance and Error Correction
The two decoders are identical when
p
C
(
c
) is constant, that is,when all codewords occur with the same probability. Themaximum likelihood decoder is assumed in the sequel.The probability
p
(
r

c
) equals the probability of the error pattern
e
=
r
−
c
. Smallweight error patterns are more likely to occurthan highweight ones
⇒
we want to ﬁnd a codeword thatminimizes
w
(
e
) =
w
(
r
−
c
).
A code with minimum distance
d
min
can correct
all
errorpatterns of weight less than or equal to
(
d
min
−
1)
/
2
.It is sometimes possible to to correct errors with
w >
(
d
min
−
1)
/
2
.
c
Patric¨Osterg˚ard72.3410 Linear Codes (1) 11
'& $ %
Decoder Types
A
complete errorcorrecting decoder
is a decoder that, given areceived word
r
, selects a codeword
c
that minimizes
d
(
r
,
c
).Given a received word
r
, a
t
errorcorrecting boundeddistancedecoder
selects the (unique) codeword
c
that minimizes
d
(
r
,
c
) iﬀ
d
(
r
,
c
)
≤
t
. Otherwise, a
decoder failure
is declared.
Question.
What is the diﬀerence between decoder errors anddecoder failures in a boundeddistance decoder?
c
Patric¨Osterg˚ard72.3410 Linear Codes (1) 12
'
& $ %
Example: A Binary Repetition Code
The binary repetition code of length 4 is
{
0000
,
1111
}
.Received Selected Received Selected0000 0000 1000 00000001 0000 1001 0000 or 1111
∗
0010 0000 1010 0000 or 1111
∗
0011 0000 or 1111
∗
1011 11110100 0000 1100 0000 or 1111
∗
0101 0000 or 1111
∗
1101 11110110 0000 or 1111
∗
1110 11110111 1111 1111 1111
∗
Boundeddistance decoder declares decoder failure.
c
Patric¨Osterg˚ard
72.3410 Linear Codes (1) 13
'& $ %
ErrorCorrecting Codes and a Packing Problem
A central problem related to the construction of errorcorrectingcodes can be formulated in several ways:
1.
With a given length
n
and minimum distance
d
, and agiven ﬁeld GF(
q
), what is the maximum number
A
q
(
n,d
)of codewords in such a code?
2.
What is the minimum redundancy for a
t
errorcorrecting
q
ary code of length
n
?
3.
What is the maximum number of spheres of radius
t
thatcan be packed in an
n
dimensional vector space over GF(
q
)?
c
Patric¨Osterg˚ard72.3410 Linear Codes (1) 14
'& $ %
The Hamming Bound
The number of words in a sphere of radius
t
in an
n
dimensionalvector space over GF(
q
) is
V
q
(
n,t
) =
t
i
=0
ni
(
q
−
1)
i
.
Theorem 41.
The size of a
t
errorcorrecting
q
ary code of length
n
is
M
≤
q
n
V
q
(
n,t
)
.
c
Patric¨Osterg˚ard72.3410 Linear Codes (1) 15
'& $ %
The Gilbert Bound
Theorem 42.
There exists a
t
errorcorrecting
q
ary code of length
n
of size
M
≥
q
n
V
q
(
n,
2
t
)
.
Proof:
Repeatedly pick any word
c
from the space, and after eachsuch operation, delete all words
w
that satisfy
d
(
c
,
w
)
≤
2
t
fromfurther consideration. Then the ﬁnal code will have minimumdistance at least 2
t
+ 1 and will be
t
errorcorrecting. The theoremfollows from the fact that at most
V
q
(
n,
2
t
) words are deleted fromfurther consideration in each step.
c
Patric¨Osterg˚ard72.3410 Linear Codes (1) 16
'
& $ %
Comparing Bounds
Theorems 41 and 42 say that for the redundancy
r
of a code,log
q
V
q
(
n,t
)
≤
r
≤
log
q
V
q
(
n,
2
t
)
.
These bounds for binary 1errorcorrecting codes are compared in[Wic, Fig. 43].
c
Patric¨Osterg˚ard