information that can be used by the channel decoder. In particular, for the BPSK example the distance
of the received bit from
E
b
and
-
E
b
can be used in the channel decoder to make better decisions
about the transmitted codeword. When these distances are used in the channel decoder it is called soft-
decision decoding. Soft decision decoding is not typically used in block codes due to its complexity, and
therefore we will not treat soft decision decoding of block codes (we will treat if for other code types, e.g.
convolutional codes, later in the chapter).
Hard decision decoding typically uses minimum-distance decoding. In minimum distance decoding
the n bits corresponding to a codeword are first demodulated, and the demodulator output is passed
to the decoder. The decoder compares this received codeword to the 2
k
possible codewords comprising
the code, and decides in favor of the codeword that is closest in Hamming distance (differs in the least
number of bits) to the received codeword. Mathematically, for a received codeword R the decoder uses
the formula
pick C
j
s.t. d(C
j
, R)
d(C
i
, R)
i = j.
If there is more than one codeword with the same minimum distance to R, one of these is chosen at
random by the decoder. This minimum distance decoding methods picks the transmitted codeword that
is most likely to have produced the received codeword (maximum likelihood decoding), i.e. it picks the
C
j
satisfying
P (R
|C
j
)
P (R|C
i
), i = 1, . . . , 2
k
,
since the most probable error event in an AWGN channel is the event with the minimum number of errors
needed to produce the received codeword. Once the maximum likelihood codeword C
i
is determined, it
is decoded to the k bits that produce codeword C
i
.
Since maximum likelihood detection of codewords is based on a distance decoding metric, we can best
illustrate this process in state space, as shown in Figure ??. The minimum distance between codewords,
illustrated by the black dots in this figure, is d
min
. Each codeword is centered inside a circle of radius
t = .5(d
min
- 1) , where x denotes the largest integer greater than or equal to x. The shaded dots
represent received codewords where one or more bits differ from those of the transmitted codeword.
Minimum distance decoding can be used to either detect or correct errors. Detected errors in a
data block either cause the data to be dropped or a retransmission of the data (the ARQ protocol).
Error correction allows the corruption in the data to be reversed. For error correction the minimum
distance decoding process ensures that a received codeword lying within a Hamming distance t from the
transmitted codeword will be decoded correctly. Thus, the decoder can correct t errors, as can be seen
from ??. We see from Figure ?? that the decoder can also detect all error patterns of d
min
- 1 errors. In
fact, a decoder for an (n, k) code can detect 2
n
- 2
k
possible error patterns. The reason is that there are
2
k
- 1 nondetectable errors, corresponding to the case where a corrupted codeword is exactly equal to
a codeword in the set of possible codewords (of size 2
k
) that is not equal to the transmitted codeword.
Since there are 2
n
- 1 total possible error patterns, this yields 2
n
- 2
k
nondetectable error patterns.
Example 8.4:
A (5, 2) code has codewords C
0
= (00000), C
1
= (01011), C
2
= (10101), and C
3
= (11110). Suppose
the all zero codeword C
0
is transmitted. Find the set of error patterns corresponding to nondetectable
errors for this codeword transmission.
Solution: The nondetectable error patterns correspond to the three nonzero codewords, i.e. e
1
=
(01011), e
2
= (10101), and e
3
= (11110) are nondetectable error patterns, since adding any of these to
C
0
results in a valid codeword.
184