The information sequence is divided into blocks of length
k k. Each block is mapped into
channel inputs of length n n.
The mapping is independent from previous blocks, that is,
there is no memory from one block to another.
k=2
k
2
and
n=5
n
5
information sequence ⇒ codeword (channel input)
A binary block code is completely defined by
2k
2
k
binary sequences of length n
n called codewords.
C=
c
1
c
2
…
c
2
k
C
c
1
c
2
…
c
2
k
(5)
There are three key questions,
- How can one find "good" codewords?
- How can one systematically map information sequences
into codewords?
- How can one systematically find the corresponding
information sequences from a codeword,
i.e., how can we decode?
These can be done if we concentrate on linear codes and utilize finite
field algebra.
A block code is linear if
ci∈C
c
i
C
and
cj∈C
c
j
C
implies
ci⊕cj∈C
c
i
c
j
C
where ⊕
⊕ is an elementwise modulo 2 addition.
Hamming distance is a useful measure of codeword properties
d
H
cicj=
# of places that they are different
d
H
c
i
c
j
# of places that they are different
(7)
Denote the codeword for information sequence
e
1
=1000⋮00
e
1
1
0
0
0
⋮
0
0
by
g
1
g
1
and
e
2
=0100⋮00
e
2
0
1
0
0
⋮
0
0
by
g
2
g
2
,…,
and
e
k
=0000⋮01
e
k
0
0
0
0
⋮
0
1
by
g
k
g
k
.
Then any information sequence can be expressed as
u=
u
1
⋮
u
k
=∑
i
=1k
u
i
e
i
u
u
1
⋮
u
k
i
1
k
u
i
e
i
(8)
and the corresponding codeword could be
c=∑
i
=1k
u
i
g
i
c
i
1
k
u
i
g
i
(9)
Therefore
with
c=01n
c
0
1
n
and
u∈01k
u
0
1
k
where
G=
g
1
g
2
⋮
g
k
G
g
1
g
2
⋮
g
k
,
a
k
kx
n
n matrix and all operations are modulo 2.
In Example 1 with
g
1
=01111T
g
1
0
1
1
1
1
and
g
2
=10100T
g
2
1
0
1
0
0
and
G=(
01111
10100
)
G
0
1
1
1
1
1
0
1
0
0
Examples of good linear codes include Hamming codes, BCH codes,
Reed-Solomon codes, and many more. The rate of these codes is defined as
kn
k
n
and these codes have different error correction and error detection
properties.
