Chapter 1 Chapter 1 pp

Coding for Reliable Digital Coding for Reliable Digital

T i i d St T i i d St Transmission and Storage Transmission and Storage
Wireless Information Transmission System Lab. Wireless Information Transmission System Lab.
Institute of Communications Engineering Institute of Communications Engineering g g g g
National Sun National Sun Yat Yat- -sen sen University University
Introduction Introduction
A major concern of designing digital data transmission and storage
systemsisthecontrol of errorssothat reliablereproductionof data systems is the control of errors so that reliable reproduction of data
can be obtained.
In 1948, Shannon demonstrated that, by proper encodingof the
information, errors induced by a noisy channel or storage medium y y g
can be reduced to any desired level without sacrificing the rate of
information transmission or storage, as long as the information rate
i l th th it f th h l is less than the capacity of the channel.
A d l f ff h b d d h bl f d i i A great deal of effort has been expended on the problem of devising
efficient encoding and decoding methods for error control in a noisy
environment
2
environment.
Typical Digital Communications Systems Typical Digital Communications Systems
Block diagram of a typical data transmission or storage system
3
1.2 Types of 1.2 Types of Major Codes Major Codes
There are four types of codes in common use today:
Bl k d Block codes
Convolutional codes
T b d Turbo codes
Low-Density Parity-Check (LDPC) Codes
4
Block Codes Block Codes
Block codes (cont.)
Theencoder for ablockcodedividestheinformationsequence The encoder for a block code divides the information sequence
into message blocks of k information bits each.
A messageblockisrepresentedbythebinaryk tuple A message block is represented by the binary k-tuple
u=(u
1
,u
2
,,u
k
) called a message.
Thereareatotal of 2
k
different possiblemessages Theencoder There are a total of 2 different possible messages. The encoder
transforms each message u into an n-tuplev=(v
1
,v
2
,,v
n
) of
discrete symbols called a code word.
This set of 2
k
code words of length n is called an (n,k) block code.
The ratio R=k/n is called the code rate.
n-k redundant bits can be added to each message.
Since the n-symbol output code word depends only on the
correspondingk bit input message theencoder ismemoryless
5
corresponding k-bit input message, the encoder is memoryless,
and can be implemented with a combinational logic circuit.
Finite Field (Galois Field) Finite Field (Galois Field)
Much of the theory of linear block code is highly mathematical in
nature andrequiresanextensivebackgroundinmodernalgebra nature, and requires an extensive background in modern algebra.
Finite field was invented by the early 19th century mathematician,
i l i EvaristeGalois.
GaloiswasayoungFrenchmathwhiz whodevelopedatheoryof Galois was a young French math whiz who developed a theory of
finite fields, now know as Galois fields, before being killed in a duel
at the age of 21.
For well over 100 years, mathematicians looked upon Galois fields
aselegant mathematicsbut of nopractical value as elegant mathematics but of no practical value.
6
Convolutional Convolutional Codes Codes
Convolutional code
Theencoder for aconvolutional codealsoacceptsk bit blocksof The encoder for a convolutional code also accepts k-bit blocks of
the information sequence u and produces an encoded sequence
(code word) v of n-symbol blocks.
Each encoded block depends not only on the corresponding k-bit
message block at the same time unit, but also on m previous
messageblocks Hence theencoder hasamemoryorder of m message blocks. Hence, the encoder has a memoryorder of m.
The set of encoded sequences produced by a k-input, n-output
encoder of memory order m is called an (n, k, m) convolutional y ( , , )
code.
The ratio R=k/n is called the code rate.
Since the encoder contains memory, it must be implemented with
a sequential logic circuit.
7
Convolutional Convolutional Codes Codes
Binary convolutional encoder with k=1, n=2, and m=2
8
Convolutional Convolutional Code Structure Code Structure
1 2 k 1 2 k 1 2 k
1 2 K
k bits
+ + + +
1 2 n-1 n
Output
9
Turbo Codes Basic Concepts Turbo Codes Basic Concepts
Turbo coding uses parallel or serial concatenationof two
recursivesystematicconvolutional codesjoinedthroughan recursive systematic convolutional codes joined through an
interleaver.
f i bi d dbl kb bl k Information bits are encoded block by block.
Turbo codes uses iterative decoding techniques.
Soft-output decoder is necessary for iterative decoding.
TurbocodescanapproachtoShannonlimit Turbo codes can approach to Shannon limit.
10
Turbo Codes Encoder Turbo Codes Encoder An Example An Example
X(t)
X(t)
Y(t)
( )
Interleaver
Y(t) Y (t)
When the switch is placed on the low position, the tail bits are feedback
X'(t)
11
and the trellis will be terminated.
1.5 Types of Errors 1.5 Types of Errors
On memorylesschannels, the noise affects each transmitted symbol
independently independently.
Memorylesschannels are called random-error channels.
12
Transition probability diagrams for binary symmetric channel (BSC).
1.5 Types of Errors 1.5 Types of Errors
On channels with memory, the noise is not independent from
transmissiontotransmission transmission to transmission.
Channel with memory are called burst-error channels.
13
Simplified model of a channel with memory.
1.6 Error Control Strategies 1.6 Error Control Strategies
Error control for a one-way systemmust be accomplished using
forward error correction (FEC) that is byemployingerror- forward error correction (FEC), that is, by employing error
correcting codes that automatically correct errors detected at the
receiver.
Error control for a two-way systemcan be accomplished using error
detection and retransmission, called automatic repeat request (ARQ).
This is also know as thebackward error correction (BEC).
In an ARQ system, when errors are detected at the receiver, a request is sent
for thetransmitter torepeat themessage andthiscontinuesuntil themessage for the transmitter to repeat the message, and this continues until the message
is received correctly.
The major advantage of ARQ over FEC is that error detection
requires much simpler decoding equipment than does error
correction.
14
1.6 Error Control Strategies 1.6 Error Control Strategies
ARQ is adaptivein the sense that information is retransmitted only
whenerrorsoccur when errors occur.
Whenthechannel error rateishigh retransmissionsmust besent too When the channel error rate is high, retransmissions must be sent too
frequently, and the system throughput, the rate at which newly
generated messages are correctly received, is lowered by ARQ. g g y y
In general, wire-line communications (more reliable) adopts BEC g , ( ) p
scheme, while wireless communications (relatively unreliable)
adopts FEC scheme.
15
Error Detecting Codes Error Detecting Codes
Cyclic Redundancy Code (CRC Code) also know as the
polynomial code polynomial code.
Polynomial codesarebasedupontreatingbit stringsas Polynomial codes are based upon treating bit strings as
representations of polynomials with coefficients of 0 and 1 only.
For example, 110001representsasix-termpolynomial: x
5
+x
4
+x
0
For example, 110001 represents a six term polynomial: x x x
When the polynomial code method is employed, the sender and
receiver must agree upon a generator polynomial, G(x), in advance.
To compute the checksum for some frame with m bits,
di h l i l M( ) h f b l corresponding to the polynomial M(x), the frame must be longer
than the generator polynomial.
16
Error Detecting Codes Error Detecting Codes
The idea is to append a checksum to the end of the frame in such a
waythat thepolynomial representedbythechecksummedframeis way that the polynomial represented by the checksummedframe is
divisible by G(x).
When the receiver gets the checksummedframe, it tries dividing it g , g
by G(x). If there is a remainder, there has been a transmission error.
The algorithm for computing the checksum is as follows: g p g
17
Calculation of the polynomial code checksum Calculation of the polynomial code checksum
18
Calculation of the polynomial code checksum Calculation of the polynomial code checksum
19