Digital Signal Processing Reference
In-Depth Information
2.3
Coding: the concept of distance
In the previous section, the notion of symbol (bit) sequences and distances be-
tween sequences was introduced. It was also suggested that the error-correcting
capabilities of a coding algorithm rely on the minimum distance between the
sequences in a subset. It is also intuitively clear that in case of transmission
errors, a large distance between sequences prevents that one sequence is acci-
dentally mistaken for another in the decoder of the receiver. However, it was
not explained what this 'distance between sequences' actually means and how
this distance should be calculated.
In order not to overcomplicate the story, let's start with the basic example of
Hamming distance
. The Hamming distance between two symbol sequences of
equal length is defined as the number of positions at which the symbols differ.
For example, the Hamming distance between '010011' and '101011' is 3. As-
sume that, at a certain moment in the coding process this pair represents the
complete subset of allowed sequences, and '111011' is offered to the decoder.
Sequence '101011' has the largest probability of being transmitted by the en-
coder since its distance from the received sequence is only 1 bit. This is only
true, of course, for as long as each bit has an equal probability of being flipped.
If the sequence is transmitted over the wireless channel on a bit-by-bit basis,
each data bit will be equally affected by noise. Another example is the infor-
mation stored in the dram memory of a computer. Also in this case, there is
no special reason why certain bits would have a sensitivity to failure which is
different from the other bits.
The situation becomes completely different when some bit positions are sys-
tematically treated in a different way. It turns out that this is the case when bits
are grouped and mapped on a constellation of symbols in the analog domain
(Figure 2.4). Each of the 2
n
points in such a constellation represents a collec-
tion of
n
bits (e.g. 3 bits in case of 8-psk). When a symbol is sent through
a noisy channel, 'clouds' will form around the constellation points when the
received constellation map is visualized. It is more likely that the symbol-to-
bit demapper in the receiver will confuse neighbouring points than two more
distant constellation points.
Example: 8-psk with natural symbol mapping
Back to the example from above, where the encoder in the transmitter
has produced the sequence '101011'. As is exemplified in Figure 2.4,
suppose that this sequence is split in words of 3 bits ('101' and '011')
by the 8-psk symbol mapper in the transmitter. Remark that, in the
case of natural mapping, the left-most bit (msb) always controls two
opposing constellation points, independently from the other two bits.
