ChannelCoding
BY
Dr. Ejidokun T. O .
Lectures No. 13 and 14: Channel Coding
Overview
These lectures will look at the following:
Channel coding
Block codes
Hamming distance
Repetition codes
Single parity check codes
Cross word error correction
DT008/2 Digital Communications Engineering II Slide: 1
Lectures No. 13 and 14: Channel Coding
Introduction
Channel coding deals with error control techniques. If the
data at the output of a communications system has errors
that are too frequent for the desired use, the errors can
often be reduced by the use of a number of techniques.
Coding permits an increased rate of information transfer
at a fixed error rate, or a reduced error rate for a fixed
transfer rate. The two main methods of error control are:
Automatic Repeat Request (ARQ) when a re-
ceiver circuit detects errors in a block of data, it re-
DT008/2 Digital Communications Engineering II Slide: 2
Lectures No. 13 and 14: Channel Coding
quests that the data is retransmitted.
Forward Error Correction (FEC) the transmitted data is
encoded so that the data can correct as well as detect
errors caused by channel noise.
The choice of ARQ or FEC depends on the particular
application. ARQ is often used where there is a full du-
plex (2-way) channel because it is relatively inexpensive
to implement. FEC is used where the channel is not full
duplex or where ARQ is not desirable because real time
is required.
DT008/2 Digital Communications Engineering II Slide: 3
Lectures No. 13 and 14: Channel Coding
Channel Coding
The two main categories of channel codes are:
Block codes a block of k information bits is encoded
to give a codeword of n bits (n > k). For each se-
quence of k information bits, there is a a distinct
codeword of n bits. Examples of block codes include
Hamming Codes and Cyclic Codes. A Cyclic
Redundancy Check (CRC) code can detect any
error burst up to the length of the CRC code itself.
Convolutional Codes the coded sequence of n bits
DT008/2 Digital Communications Engineering II Slide: 4
Lectures No. 13 and 14: Channel Coding
depends not only on the present k information bits
but also on the previous information bits.
The primary objective of coding is that the decoder can
determine if the received word is a valid codeword, or if
it is a codeword which has been corrupted by noise (i.e.
detect one or more errors). Ideally the decoder should
be able to decide which codeword was sent even if the
transmitted codeword was corrupted by noise (i.e. error
correction).
DT008/2 Digital Communications Engineering II Slide: 5
Lectures No. 13 and 14: Channel Coding
Block codes
The block coder input is a stream of information bits.
The coder segments this bit stream into blocks of k in-
formation bits and for each block it calculates a number of r
check bits, or it picks the r check bits from a tabu- lated set
of values. It then transmits the entire block, or codeword
of n = k + r channelbits. This is called an (n,k) block code.
If errors occur in sufficiently few of these transmitted
channel bits, the r check bits may provide the receiver
DT008/2 Digital Communications Engineering II Slide: 6
Lectures No. 13 and 14: Channel Coding
with sufficient information to enable it to detect and/or
correct the channel errors.
The code efficiency (or code rate) is k/n.
If the k information bits are transmitted unaltered first
followed by the transmission of the r check bits it is called a
systematic code.
A non-systematic block code is one which has the check
bits interspersed between the information bits.
DT008/2 Digital Communications Engineering II Slide: 7
Lectures No. 13 and 14: Channel Coding
Hamming Distance
The minimum number of positions in which any two code-
words in any particular block differ from each other is
called the Hamming distance, dmin .
Consider the following set of codewords:
C1 = 0000, C2 = 0101, C3 = 1010, C4 = 1111
The distance, d:
between C2 and C3 is 4
between C2 and C4 is 2
between C3 and C2 is 2
DT008/2 Digital Communications Engineering II Slide: 8
Lectures No. 13 and 14: Channel Coding
The Hamming distance (the smallest distance between
any pair) = dmin = 2.
The distance between any codewords and C1 is equal to
its weight i.e. the number of 1s in the codeword. For
example, the weight of C4 is 4 and the distance from C1
to C4 is 4
The Hamming distance is important:
If a received codeword has e errors, then provided that
e dmin 1, it is possible to detect with certainty that
errors have occurred.
DT008/2 Digital Communications Engineering II Slide: 9
Lectures No. 13 and 14: Channel Coding
If a received codeword has e errors, then provided that
2e + 1 dmin , it is possible to detect the errors and
repair them to regenerate the original codeword. To
repair a single error requires a Hamming distance of
3 or greater.
The 4 bit code in the example above, therefore, cannot correct
the result of occurrence of a single error, (since dmin = 2), but
it can detect it.
DT008/2 Digital Communications Engineering II Slide: 10
Lectures No. 13 and 14: Channel Coding
Repetition Codes
These are the simplest type of block codes.
One way to detect an error in an information block is to
send the information twice. The two received blocks are
compared bit by bit and if there is a difference an error
has occurred.
This method may be extended by sending the information
block three times. If one block differs from the other two,
assume an error has occurred in that block and discard
it.
DT008/2 Digital Communications Engineering II Slide: 11
Lectures No. 13 and 14: Channel Coding
This is repetition coding. It is simple to implement but
very inefficient in terms of information transfer.
Another method is to encode a single symbol into a block
of n identical bits - an (n,1) block code. There are only
two codewords - the sequence of n 0s and the sequence
of n 1s. The first bit is the information bit, the other
r = n 1 bits are check bits. The value of each check
bit is identical to the information bit. The decoder might
use the following rules:
Count the number of 0s and the number of 1s in the
received bits.
DT008/2 Digital Communications Engineering II Slide: 12
Lectures No. 13 and 14: Channel Coding
If there are more received 0s than 1s, decide that the
all-0 codeword was sent.
If there are more 1s than 0s decide that the all-1 code-
word was sent.
If the number of 1s equals the number of 0s do not de-
cide - just flag a decoding failure and perhaps generate
and ARQ (automatic request to repeat the message).
In this case the Hamming distance is n so that the origi-
nal data can be recovered if there are less than (n 1)/2
errors in the received codeword - this is the basis of the
2nd and 3rd steps above. This rule will decode correctly
DT008/2 Digital Communications Engineering II Slide: 13
Lectures No. 13 and 14: Channel Coding
in all cases where the channel noise changes less than half
the bits in any one block.
If the channel noise changes more than half of the bits in
any one block, the decoder will make a decoding error,
i.e., it will decode the received word into the wrong code-
word. If channel errors occur infrequently the probability
of a decoding failure or a decoding error for a repetition
code of long block length is very small indeed.
DT008/2 Digital Communications Engineering II Slide: 14
Lectures No. 13 and 14: Channel Coding
Single Parity Check Codes
This is an example of a high information rate (R = k/n)
code.
It appends a parity check bit to the end of the infor-
mation bits.
This check bit is the modulo-2 sum (modulo-2 addition is
equivalent to the exclusive OR logical operation) of the
codeword (n 1) information bits.
If the number of 1s in the information word is even, then
the modulo-2 sum of all the information bits will be equal
DT008/2 Digital Communications Engineering II Slide: 15
Lectures No. 13 and 14: Channel Coding
to 0. If the number of 1s in the information word is odd
their modulo-2 sum will be equal to 1. The parity bit is
calculated and appended to the information bits to form
the codeword. Even parity means that the parity bit
is set so that the total number of 1s in the codeword is
even. Odd parity means that the total number of 1s in
the codeword must be odd.
This type of code can only detect and cannot correct
errors.
A single bit error (or any number of odd bit errors) will
be detected but any combination of two bit errors (or any
DT008/2 Digital Communications Engineering II Slide: 16
Lectures No. 13 and 14: Channel Coding
number of even bit errors) will cause a decoding error.
Repetitive codes and single parity check codes are, re-
spectively, examples of extreme and relatively trivial block
codes. However, single parity checks are used quite often
with ASCII codes in computer communications.
DT008/2 Digital Communications Engineering II Slide: 17
Lectures No. 13 and 14: Channel Coding
Cross Word Error Correction
This is an extension of the use of parity bits to enable
error recovery.
Assume that data is sent in 7 bit words and a single parity
bit is appended (Shown as Rx in the table below). This
parity bit may be either even or odd.
After 7 data words have been sent, another 8 bit check
word is appended. Bit 1 of this word is a parity bit for
bit 1 in all 7 data words. Bit 2 is a parity bit for bit 2 in
all of the 7 data words etc. etc. These are shown as C x
DT008/2 Digital Communications Engineering II Slide: 18
Lectures No. 13 and 14: Channel Coding
bits in the table below.
If bit 3 in word 4 is errored in transmission it will show
up as two parity bit errors, i.e., parity bit R4 and C3.
This allows the errored bit to be identified and the error
to be corrected.
The problem with this correction method is in the low
transmission efficiency. For example, the above arrange-
ment sends 7 7(49) bits of data but 8 8(64) bits are
required for error correction - the efficiency is 49/64 =
77 %.
DT008/2 Digital Communications Engineering II Slide: 19
Lectures No. 13 and 14: Channel Coding
Word 1 Bit 1 Bit 2 Bit 3 Bit 4 Bit 5 Bit 6 Bit 7 R1
Word 2 Bit 1 Bit 2 Bit 3 Bit 4 Bit 5 Bit 6 Bit 7 R2
Word 3 Bit 1 Bit 2 Bit 3 Bit 4 Bit 5 Bit 6 Bit 7 R3
Word 4 Bit 1 Bit 2 Bit 3 Bit 4 Bit 5 Bit 6 Bit 7 R4
Word 5 Bit 1 Bit 2 Bit 3 Bit 4 Bit 5 Bit 6 Bit 7 R5
Word 6 Bit 1 Bit 2 Bit 3 Bit 4 Bit 5 Bit 6 Bit 7 R6
Word 7 Bit 1 Bit 2 Bit 3 Bit 4 Bit 5 Bit 6 Bit 7 R7
Check Word C1 C2 C3 C4 C5 C6 C7 C8
DT008/2 Digital Communications Engineering II Slide: 20
Lectures No. 13 and 14: Channel Coding
Conclusion
These lectures have looked at the following:
Channel coding
Block codes
Hamming distance
Repetition codes
Single parity check codes
Cross word error correction
DT008/2 Digital Communications Engineering II Slide: 21
