So-called linear codes create error-correction bits by combining the data bits linearly. The
phrase "linear combination" means here single-bit binary arithmetic.

For example, let's consider
the specific
(7,4)
(
7
,
4
)
error correction code described by the following coding table and,
more concisely, by the succeeding matrix expression.

The length-KK block of data bits is
represented by the vector bb,
and the length- NN
output block of the channel coder, known as a codeword, by
cc. For
example, if
b=1000T
b
1
0
0
0
,
c=1000101T
c
1000101
. The generator matrix
GG
defines all block-oriented linear channel coders.

In this
(7,4)
(
7
,
4
)
code,
24=16
2
4
16
of the
27=128
2
7
128
possible blocks arriving at the channel decoder correspond to error-free transmission and
reception. In analyzing the error-correcting capability of this or any other channel code,
we must have a systematic way of assigning a codeword to a received block when
communication errors occur. Note that the number of possible received blocks is much
larger than the number of codewords; the channel has ample opportunity to
confuse us! Conceptually, we want to assign to each possible received length-
NN block
a length- KK
block of data bits. This assignment should correspond to the most probable error
pattern that could have transformed a transmitted block into the one received.
Because the matched-filter receiver guarantees that the single-bit error probability
p
e
p
e
of the digital channel
will be less than
1/2
12
,
the most probable error pattern is the one having the *fewest *errors. The
way of assessing error patterns is to compute the distance between the
received block and all codewords. The Hamming distance between blocks
c
1
c
1
and
c
2
c
2
, denoted
by
d
c
1
c
2
d
c
1
c
2
, equals
the sum of the difference between the bit sequences comprising the two blocks. For example,
if
c
1
=1000101T
c
1
1
0
0
0
1
0
1
and
c
2
=1010101T
c
2
1
0
1
0
1
0
1
, the difference
equals
0010000T
0
0
1
0
0
0
0
,
the number of nonzero terms equals one, and thus
d
c
1
c
2
=1
d
c
1
c
2
1
.
Interestingly, examination of the binary
arithmetic table reveals that
subtraction and addition are equivalent. We can express the Hamming distance as

d
c
1
c
2
=
sum
c
1
⊕
c
2
d
c
1
c
2
sum
c
1
c
2

(1)
Error correction amounts to searching for the codeword
cc
closest to the
received block cc
in terms of the Hamming distance between the two. The error correction capability of a
channel code is limited by how close together any two error-free blocks are. Bad codes
would produce blocks close together, which would result in ambiguity when assigning a
block of data bits to a received block. The quantity to examine, therefore, in
designing code error correction codes is the minimum distance between codewords.

d
min
=mind
c
i
c
j
with
c
i
≠
c
j
d
min
min
d
c
i
c
j
with
c
i
c
j

(2)
Suppose this minimum distance is one; this means the channel code has two codewords
with the not-so-desirable property that one error occurring somewhere within the

NN-bit
block transforms one codeword into another! The receiver would never realize that an
error occurred in this case. Such a channel code would have no error-correction
capability, and because the energy/bit must be reduced to insert error correction bits, we
obtain larger error probabilities. Now suppose the minimum distance between error-free
blocks is two. This situation is better than the previous one: If one error occurs anywhere
within a block, no matter what codeword was transmitted, we can detect the
fact that an error occurred. Unfortunately, we

*cannot *correct the error. Because
the minimum distance is two, a received block containing one error can be a
distance of one from two (or more) codewords; we cannot associate such a block

*uniquely *with a codeword. We must be resigned to the fact that to correct errors, we
must have the minimum distance between error-free blocks be at least three.

Suppose we want a channel code to have an error-correction capability of
nn
bits. What must the minimum Hamming distance between codewords
d
min
d
min
be?

How do we calculate the minimum distance between codewords? Because we have
2K
2
K
codewords, the number of possible unique pairs equals
2K−1(2K−1)
2
K
1
2
K
1
,
which can be a large number. Recall that our channel coding procedure is linear, with
c=Gb
c
G
b
. Therefore
c
i
⊕
c
j
=G
b
i
⊕
b
j
G
c
i
c
j
G
b
i
b
j
. Because
b
i
⊕
b
j
b
i
b
j
always yields another block of *data *bits, we find that the difference
between any two codewords is another codeword! Thus, to find
d
min
d
min
we need
only compute the number of ones that comprise all non-zero codewords. Finding these
codewords is easy once we examine the coder's generator matrix. Note that the columns
of GG are
codewords, and that all codewords can be found by all possible pairwise sums of the columns.
To find
d
min
d
min
,
we need only count the number of bits in each column and sums of columns. For our example
(7,4)
(
7
,
4
)
((Reference)),
GG's first column
has three ones, the next one four, and the last two three. No sum of columns has fewer than three
bits, meaning
d
min
=3
d
min
3
,
and we have a channel coder that can correct all occurrences of one error within a received
77-bit
block.

Find the generator matrix for our three-fold
repetition code. Show that it indeed has single-bit error correction
capability. How many repetitions would be required to yield a
double-error-correcting channel code?

G=111T
G
1
1
1
. As
it has only one non-zero codeword and it has three ones, it has single-bit error correction
capability. For double-bit error correction, we would need a five-fold repetition code.

We must question whether a
(7,4)
(
7
,
4
)
code's
error correction capability compensates for the increased error probability due
to the necessitated reduced bit energy. (For example, the repetition
code does not meet this requirement.) Figure 3 shows that if the signal-to-noise
ratio is large enough that channel coding indeed yields a smaller overall error
probability.

Because the bit stream emerging from the source coder is segmented into four-bit blocks,
the fair way of comparing coded and uncoded transmission is to compute the probability
of a *block *error: the probability that any bit in a block remains in error despite error
correction and regardless of whether the error occurs in the data or coding bits. Clearly,
our
(7,4)
(
7
,
4
)
channel code does yield smaller error rates, and is worth the additional systems required
to make it work.