Coding Theory
2
Communication System
Channel
encoder
Source
encoder
Modulator
Demodulator
Channel
Voice
Image
Data
CRC
encoder
Interleaver
Deinterleaver
Channel
encoder
CRC
encoder
Source
decoder
Error control
Impairments
Noise
Fading
3
Error control coding
Limits in communication systems
Bandwidth limit
Power limit
Channel impairments
Attenuation, distortion, interference, noise and fading
Error control techniques are used in the digital
communication systems for reliable transmission under
these limits
4
Power limit vs. Bandwidth limit
Error control coding
Ad!antage of error control coding
"n principle#
E!ery channel has a capacity C
"f you transmit information at a rate R < C, then the error$free
transmission is possible
"n practice#
%educe the error rates
%educe the transmitted power requirements
"ncrease the operational range of a communication system
Classification of error control techniques
&orward error correction '&EC(
Error detection# cyclic redundancy chec) 'C%C(
Automatic repeat request 'A%*(
!
History
+hannon ',-./(
R# 0ransmission rate for data
C# Channel capacity
"f R < C, it is possible to transfer information at error rates
that can be reduced to any desired le!el
"
History
1amming codes ',-23(
+ingle error correcting
Con!olutional codes 'Elias, ,-24(
BC1 codes ',-43(, %+ codes ',-43(
multiple error correcting
5oppa codes ',-63(
5enerali7ation of BC1 codes
Algebraic geometric codes ',-/8(
5enerali7ation of %+ codes
Constructed o!er algebraic cur!es
0urbo codes ',--9(
L:PC codes
#
Channel
;emoryless channel
0he probability of error is independent from one symbol to
the ne<t
+ymmetric channel
P( i | j )=P( j | i ) for all symbol !alues i and j
E<( binary symmetric channel 'B+C(
Additi!e white 5aussian noise 'A=5>( channel
Burst error channel
Compound 'or diffuse( channel
0he errors consist of a mi<ture of bursts and random errors
;any codes wor) best if errors are random
"nterlea!er and deinterlea!er are added
$
Channel
%andom error channels
:eep$space channels
+atellite channels
?se random error correcting codes
Burst error channels# channels with memory
%adio channels
+ignal fading due to multipath transmission
=ire and cable transmission
"mpulse switching noise, crosstal)
;agnetic recording
0ape dropouts due to surface defects and dust particles
?se burst error correcting codes
%&
Encoding
Bloc) codes
Encoding of an @n , kA bloc) code
k 'its k 'its k 'its n 'its n 'its n 'its
message or in(ormation code)ord
Redundanc*+ n k
Code rate+ k / n
Message m
(m
1
, m
2
, , m
k
)
code)ord c
(m
1
, m
2
, , m
k
, p
1
, p
2
, , p
n - k
)
,dd n k redundant
parit* chec- s*m'ols
(p
1
, p
2
, , p
n - k
)
%%
Decoding
:ecoding @n , kA bloc) code
:ecide what the transmitted information was
0he minimum distance decoding is optimum in a
memoryless channel
Received data r
(r
1
, r
2
, , r
n
)
Decoded message
Correct errors and remove
n k redundant s*m'ols
m
) , ..... , , (
2 1 k
m m m
Error vector e = (e
1
, e
2
, , e
n
) = (r
1
, r
2
, , r
n
) (c
1
, c
2
, , c
n
)
%2
Decoding
:ecoding plane
c
1
r
c
4
c
3
c
2
c
6
c
5
%3
Decoding
E<( Encoding and decoding procedure of @4, 9A code
, 5enerate the information ',33( in the source
8 0ransmit the codeword ',33,3,( corresponding to ',33(
9 0he !ector ',3,,3,( is recei!ed
. Choose the nearest codeword ',33,3,( to ',3,,3,(
2 E<tract the information ',33( from the codeword ',33,3,(
In(ormation
&&&
%&&
&%&
%%&
&&%
%&%
&%%
%%%
code)ord
&&&&&&
%&&%&%
&%&&%%
%%&%%&
&&%%%%
%&%&%&
&%%%&&
%%%&&%
Distance (rom .%&%%&%/
4
%
4
2
3
3
2
%4
Parameters of block codes
1amming distance d
H
(u, v)
B positions at which symbols are different in two !ectors
E<( u=(1 0 1 0 0 0)
v=(1 1 1 0 1 0) d
H
(u, v) = 2
1amming weight w
H
(u)
B non7ero elements in a !ector
E<( w
H
(u) = 2, w
H
(v) = 4
%elation between hamming distance and hamming weight
Binary code# d
H
(u, v) = w
H
(u + v),
where + means e<clusi!e C% 'bit by bit(
>onbinary code# d
H
(u, v) = w
H
(u v)
%
Parameters of block codes
;inimum distance d
d = min d
H
(c
i
, c
j
) for all c
i
c
j
C
Any two codewords differ in at least d places
@n, kA code with d @n, k, dA code
Error detection and correction capability
Let s D B errors to be detected
t D B errors to be corrected 's t(
0hen, we ha!e d s + t + 1
Error correction capability
Any bloc) code correcting t or less errors satisfies
d 2t + 1
0hus, we ha!e t = (d 1) / 2
%!
Parameters of block codes
E<( d = 3, 4 t = 1 # single error correcting '+EC( codes
d = 5, 6 t = 2 # double error correcting ':EC( codes
d = 7, 8 t = 3 # triple error correcting '0EC( codes
Coding sphere
t
s
t d
c
i
c
j
%"
Code erformance and coding gain
Criteria for performance in the coded system
BE%# bit error rate in the information after decoding, P
b
+>%# signal to noise ratio, E
b
/ N
0
E
b
D signal energy per bit
N
0
D one$sided noise power spectral density in the channel
Coding gain 'for a gi!en BE%(
G = 'E
b
/ N
0
)
without &EC
'E
b
/ N
0
)
with &EC
[dB
At a gi!en BE%, P
b
, we can sa!e the transmission power by
G @dBA o!er the uncoded system
%#
!inimum distance decoding
;a<imum$li)elihood decoding ';L:(
# estimated message after decoding
# estimated codeword in the decoder
Assume that c was transmitted
A decoding error occurs if
Conditional error probability of the decoder, gi!en r #
Error probability of the decoder#
m
c c
) |
( ) | ( r c c r = P E P
c c m m
=
r
r r ) ( ) | ( ) ( P E P E P 0 )here P(r) is independent o(
decoding rule
%$
!inimum distance decoding
Cptimum decoding rule# minimi7e error probability, P(E)
0his can be obtained by min
r
P(E | r), which is equi!alent to
Cptimum decoding rule is
argma<
c
P(c | r) # ;a<imum a posteriori probability ';AP(
argma<
c
P(r | c) # ;a<imum li)elihood ';L(
BayesE rule
"f equiprobable c, ;AP D ;L
) |
( m!" r c c
r
= P
) (
) ( ) | (
) | (
r
c c r
r c
P
P P
P =
2&
Problems
Basic problems in coding
&ind good codes
&ind their decoding algorithm
"mplement the decoding algorithms
Cost for forward error correction schemes
"f we use @n, kA code, the transmission rate increase from k
to n
"ncrease of channel bandwidth by n / k or decrease of
message transmission rate by k / n.
Cost for &EC
2%
Classification
Classification of &EC
Bloc) codes
1amming, BC1, %+, 5olay, 5oppa, Algebraic geometric
codes 'A5C(
0ree codes
Con!olutional codes
Linear codes
1amming, BC1, %+, 5olay, 5oppa, A5C, etc
>onlinear codes
>ordstrom$%obinson, Ferdoc), Preparata, etc
+ystematic codes !s >onsystematic codes
