179

6

Error Detection and Correction

for Coding Schemes

Coding techniques are used for several reasons: reduction of dc (direct cur-

rent) wandering, suppression of intersymbol interference, and self-clocking

capability. These problems are of engineering interest in the transmission of

digital data. Error correction and error detection coding—collectively called

error control coding—is the means whereby errors introduced into transmit-

ted data can be detected and corrected at the receiver.

The coding schemes discussed in this chapter are for error detection and

correction, specically forward error correction (FEC) techniques. FEC codes

may be divided into two classes of codes: linear block codes and convolu-

tional codes [1]. Depending on the intended use of codes, FEC enables the

receiver not only to detect errors but also to facilitate their correction.

To enhance the reader’s understanding of the subject matter, we briey

introduce the principle of channel coding, followed by coding and decoding

schemes. This arrangement enables the reader to move on to concrete real-

izations without great difculty.

6.1 Channel Coding

Noise within a transmission channel inevitably causes discrepancies or errors

between the channel input and channel output. A channel is a specic portion

of information carrying capacity of a network interface specied by a certain

transmission rate. In Chapter 3, Section 3.2.5 and Chapter 5, Section5.2, the

concepts of bit error rate and channel capacity using Shannon’s [2] theorem

were respectively discussed in some detail.

Coding enables the receiver to decode the incoming coded signals not only

to detect errors but also to correct them. Effectively encoding signals from

discrete sources and approximating a specied Shannon limit is achievable

by symbol combination in large blocks and by the application of special cod-

ing methods such as Huffman [3] codes and Fano

*

[4] codes. For clarication,

the terms data compression and effective encoding are treated as synonyms,

*

Also called the Shannon-Fado codes.

K21636_Book.indb 179 10/22/13 4:10 PM

180 Satellite Communication Engineering, Second Edition

meaning that redundancy is eliminated from the original signal, and it

is then encoded as economically as possible with a minimum number of

binary symbols. An encoder performs redundancy elimination. The appli-

cation of the effective encoding methods essentially reduces the required

channel transmission rate [5].

In general, if k binary digits enter the channel encoder, and the channel

encoder outputs n binary digits, then the code rate can be dened as

=R

k

n

c

(6.1)

The channel coding theorem species the capacity C

c

as a fundamental

limit on the rate at which the transmission of a reliable error-free message

can take place over a discrete memoryless channel (DMC). The concept of DMC

has been discussed in Chapter 3. For example, let a discrete memoryless

source with an alphabet X have entropy H(X) and produce one symbol every

T

s

seconds. Supposing that a DMC with capacity C

c

(bit/symbol) is used once

every T

c

seconds, then if

( )

≤

H X

T

C

T

s

c

c

(6.2)

there exists a coding scheme for which the source output can be transmit-

ted over the channel and be retrieved and reconstructed with an arbitrarily

small probability of error. Conversely, it is impossible to transfer information

over the channel and reconstruct the source signal with an arbitrarily small

probability of error if

( )

>

H X

T

C

T

s

c

c

(6.3)

The parameter C

c

/T

c

is called the critical rate. When H(X)/T

s

= C

c

/T

c

, the

system is said to be operating at the critical rate (at capacity). Figure5.8 (in

Chapter 5) has demonstrated that operating a system at capacity is achiev-

able only if the value of E

b

/N

o

is above the Shannon limit; that is, log

e

2 (or

–1.6 dB). Recently, however, parallel-concatenated convolutional codes have

achieved a performance close to this theoretical limit [6] (more is said of the

convolutional coding technique in Section 6.2.2). In general, the objective is to

achieve maximum data transfer in a minimum bandwidth while maintain-

ing an acceptable quality of transmission. To achieve this, an error-detecting

code must be devised. The most desirable solution is to use a forward error

correction (FEC) technique. Error detection coding is a technique for adding

redundant (extra) bits to a data stream in such a way that an error in the data

stream can be detected [7].

K21636_Book.indb 180 10/22/13 4:10 PM

Get *Satellite Communication Engineering, 2nd Edition* now with O’Reilly online learning.

O’Reilly members experience live online training, plus books, videos, and digital content from 200+ publishers.