錯誤更正碼

( ECC:Error Correcting Code)

課程目標: 本課程主要介紹錯誤更正碼之編
碼理論, 其可用來作數據資料"傳輸"及"儲存"
之錯誤更正控制.

評量方式 : 作業及小考(40%), 期中考

(30%), 期末考或期末報告(30%)

2015/9/18 Yuh-Ming Huang CSIE, NCNU Introduction 1

 Outline
 Coding for Reliable Digital Transmission and
Storage
 Linear Block Codes
 Introduction to Algebra
 Cyclic Codes
 Binary BCH Codes
 Nonbinary BCH Codes, Reed-Solomon Codes,
and Decoding Algorithms
 Trellises for Linear Block Codes

2015/9/18 Yuh-Ming Huang CSIE, NCNU Introduction 2

 Textbook : Shu Lin and Daniel J. Costello,
“Error Control Coding – Fundamentals and
Applications,” Second Edition, 2004. (歐亞書局
代理)
 References:

*1. “Theory and Practice of Error Control

Codes”, Richard E. Blahut, 1983.
2. “Error-Control Coding for Data Networks”,
I.S. Reed & X.Chen, 新智, 1999.
*3. “Error Correction Coding-Mathematical Methods
and Algorithms”, Todd K. Moon, 全華,2005

2015/9/18 Yuh-Ming Huang CSIE, NCNU Introduction 3

2015/9/18 Yuh-Ming Huang CSIE, NCNU Introduction 4
 A coded system on an
additive white Gaussian noise channel

Discrete Memory Channel (DMC)

2015/9/18 Yuh-Ming Huang CSIE, NCNU Introduction 5
Binary-Phase-Shift-keying (BPSK)
2 Es
S1 (t )  cos 2 f 0t , 0  t  T
T
2 Es
S2 (t )  cos  2 f 0t   
T
2 Es
 cos 2 f 0 t , 0  t  T ,
T
where the carrier frequency f0 is a multiple of 1/ T , and
Es is the energy of each signal.

2015/9/18 Yuh-Ming Huang CSIE, NCNU Introduction 6

M-ary Phase-Shift-keying (MPSK)

2 Es
Si (t )  cos  2 f0t  i  , 0  t  T ,
T
where i  2 (i -1) / M for 1  i  M .

2015/9/18 Yuh-Ming Huang CSIE, NCNU Introduction 7

 AWGN (Additive White Gaussian Noise) Channel
 A 0 is transmitted as + E and a 1 is transmitted as -
E , where E is the signal energy per channel bit.
ri  1   E  ni , where si is the transmitted
si

bit, ri is the received bit, and ni is a noise sample of a
Gaussian process with single-sided noise power per
hertz N0 .
 The variance of ni is N0/2 and the signal-to-noise
ratio (SNR) for the channel is E/N0 .
( ri ( 1) si E )2
1 
Pr( ri | si )  e N0
, where si  0 or 1, ri  real number.
 N0
( x   )2
1 
[ n ( x;  ;  2 )  e 2 2
with  2  N 0 / 2]
2
2015/9/18 Yuh-Ming Huang CSIE, NCNU Introduction 8
2015/9/18 Yuh-Ming Huang CSIE, NCNU Introduction 9
 Binary Symmetric Channel
 BSC is characterized by a probability p of bit error such
that the probability p of a transmitted bit 0 being
received as a 1 is the same as that of a transmitted 1
being received as a 0.
 When BPSK modulation is used on an AWGN channel
with optimum coherent detection and binary output
quantization
 0
p   pr (ri |1)dri   pr (ri | 0)dri
0 
( ri  E )2 y2
 1   1 
= e N0
dri   e 2
dy  Q ( 2 E / N 0 ),
0  N0 2 E / N0 2
y2
 1 
where Q ( x )   x 2
e 2
dy.

2015/9/18 Yuh-Ming Huang CSIE, NCNU Introduction 10

Probability of error for BPSK signaling
Probability of bit error (p)

E/N0 (dB)
2015/9/18 Yuh-Ming Huang CSIE, NCNU Introduction 11
 /******AWGN (transfer information to receive sequence)******/
 void awgn_channel(double Y, double R, char information[], double receive[], int size){// Y: SNR(dB) R: code rate
 double u1,u2;
 double r_max;
 int i;

 i = 0;
 #ifdef PC
 r_max = RAND_MAX;
 #endif
 while (i < size){
 #ifdef PC
 u1 = rand()/r_max;
 u2 = rand()/r_max;
 #else
 u1 = drand48();
 u2 = drand48();
 #endif
 receive[i] = sqrt(-2 * log(u1)) * cos(2 * Pi * u2);
 i++;
 if (i<size) {
 receive[i] = sqrt(-2 * log(u1)) * sin(2 * Pi * u2);
 i++;
 }
 }

 for (i = 0; i < size; i++) {

 receive[i] = receive[i] / sqrt(2.0 * R * pow(10.0, Y / 10.0));
 if(information[i] == '1')
 receive[i] = receive[i] + One;
 else
 receive[i] = receive[i] + Zero;
 }
 }
2015/9/18 Yuh-Ming Huang CSIE, NCNU Introduction 12
 p15 = (pow(2,15)-1.0)/2.0;
 do {u1=(float)rand()/p15-1.0;
u2=(float)rand()/p15-1.0;
z=u1*u1+u2*u2;} while(z > 1.0 || z ==
0.0);
 z = sqrt(-2.0*log(z)/z); u1 = u1*z; u2 =
u2*z;
  u1, u2 will be two iid standard
Gaussian rv's
2015/9/18 Yuh-Ming Huang CSIE, NCNU Introduction 13
X , Y : Gaussian
Y
R  X 2  Y 2 : Rayleigh W  tan 1 ( ) : uniform on [0,2 )
X
 X  R cos W , Y  R sin W
(1)
U 1,U 2 : uniform R  2 log U 1 : Rayleigh
X  R cos(2 U 2) : Gaussian
X  R sin(2 U 2) : Gaussian
(2)
U 1,U 2 : uniform Z  U 12  U 22 with Z<1 :uniform
R  2 log Z : Rayleigh
U1 U2
X  R : Gaussian Y  R : Gaussian
Z Z
2015/9/18 Yuh-Ming Huang CSIE, NCNU Introduction 14
 Hard-decision decoding
 The output of the matched filter for
each signaling interval is quantized in
two levels, denoted as 0 and 1.
 e.g. algebraic decodings :using
algebraic structures of the codes
 A hard decision of a received signal
results in a loss of information, which
degrades performance
2015/9/18 Yuh-Ming Huang CSIE, NCNU Introduction 15
 Soft-decision decoding
 If the outputs of the matched filter are unquantized or
quantized in more than two levels, we say that the
demodulator makes soft decisions. A sequence of soft-
decision outputs of the matched filter is referred to as a
soft-decision received sequence. Decoding by processing
this soft-decision received sequence is called soft
decision decoding.
 The decoder uses the additional information contained in
the unquantized (or multilevel quantized) received
samples to recover the transmitted codewords, soft-
decision decoding provides better error performance
than hard-decision decoding.

2015/9/18 Yuh-Ming Huang CSIE, NCNU Introduction 16

 In general, soft-decision maximum likelihood
decoding (MLD) of a code has about 3 dB of
coding gain over algebraic decoding of the code;
however, soft-decision decoding is much harder
to implement than algebraic decoding and
requires more computational complexity.
 These decoding algorithms can be classified into
two major categories:
 Reliability-based (or probabilistic)

 Code structure-based

2015/9/18 Yuh-Ming Huang CSIE, NCNU Introduction 17

 Code rate R=k/n
 Coding gain : the reduction in the Eb/N0 required
to achieve a specific bit error probability (rate)
(BER) for a coded communication system
compared to an uncoded system.
 Coding threshold : There always exists an Eb/N0
below which the code loses its effectiveness and
actually makes the situation worse.
 Eb : the signal energy per information bit
Eb = E / R

2015/9/18 Yuh-Ming Huang CSIE, NCNU Introduction 18

Bit-error performance of a coded communication
system with the (23,12) Golay code

2015/9/18 Yuh-Ming Huang CSIE, NCNU Introduction 19

 Transmission channels : telephone line, high-frequency
radio link, microwave link, satellite link, etc..
 Storage media : semiconductor memory, disk file, optical
memory.

 Source Coding
- # of bits per unit time is minimized
- Non-ambiguous decoding
 Channel Coding
- Encoder : to combat the noisy environment in which
code words must be transmitted or stored.
- Decoder : that minimize the probability of
decoding error

2015/9/18 Yuh-Ming Huang CSIE, NCNU Introduction 20

 Data Error

Compression Control
Coding Cryptography
And
Network Security

Digital Signal Processing

Spectrum

2015/9/18 Yuh-Ming Huang CSIE, NCNU Introduction 21

 Types of Codes
 Linear Block Code (n,k) 2k codewords
 divide the information sequence into message
blocks of k information bits each.
 i.e. u=(u1,u2,…,uk) message
 v=(v1,v2,…,vn) codeword
 memoryless
 combinational logic circuit

K bits n bits
。。。 。。。
Encoder

2015/9/18 Yuh-Ming Huang CSIE, NCNU Introduction 22

  Convolutional Code (n,k,m)
 u,v : two sequences of blocks
 memory order m
 sequential logic circuit
 R = k/n code rate

K bits n bits
。。。 。。。
Encoder

previous
m
blocks

2015/9/18 Yuh-Ming Huang CSIE, NCNU Introduction 23

* (7,4) block code
Input u (1011)

u0 u1 u2 u3

To channel

⊕ ⊕ ⊕
v0 v1 v2
v 100 1011

1 (u0,u2,u3) 0 (u0,u1,u2) 0 (u1,u2,u3)

Q: 其它組合?

2015/9/18 Yuh-Ming Huang CSIE, NCNU Introduction 24

* (2,1,2) Convolutional code

 let u=(1 1 0 1 0 0 0 0 0)
v=(11,10,00,10,01,01,00,00,00)

u …0001011
v
…0001011
…0001011
⊕ …0001011
…0001011
…0001011
 u=(…,m-1,m0,m1,…) …0001011
 v=(…,C-1(1), C-1(2), C0(1), C0(2),
C1(1), C1(2),…)

2015/9/18 Yuh-Ming Huang CSIE, NCNU Introduction 25

 Linear Time Invariant System
1 n  0 1 n  k
 (n)    (n  k )   L :  (n)  h(n)
0 n  0 0 n  k
where δ(n) : impulse sequence and h(n) : impulse responsesequence

 f (n)   f (k ) (n  k )
k  


 g ( n )  L{ f ( n)}  L{  f (k ) (n  k )}
k  

time
 
linear
 f (k )L{ (n  k )}  f ( k )h( n  k )  f ( n ) * h( n )
invariant
 
k   k  

2015/9/18 Yuh-Ming Huang CSIE, NCNU Introduction 26

 Ci(1)=∑gk(1)▪mi-k=mi C(1) = m g(1)
k
Ci =∑gk ▪mi-k=m⊕m
(2) (2) C(2) = m g(2)
i i-1⊕mi-2
k
linear convolution
where g0(1) = 1 , others = 0
g0(2) = g1(2) = g2(2) = 1 , others = 0

Impulse response

2015/9/18 Yuh-Ming Huang CSIE, NCNU Introduction 27

 Type of Errors
* random-error-correcting codes
- random-error channels (memoryless)
. deep-space channel
. satelite channel
* burst-error-correcting codes
- burst-error channels (with memory)
. radio channel
* burst-and-random-error-correcting codes
- compound channels

2015/9/18 Yuh-Ming Huang CSIE, NCNU Introduction 28

 1-p P(0|0) 0
0 0 )
0 P(1|0 0 |1
) P(
p 1
p

……
P(
) Q-
1 P(1|1 1|0
)
1 1-p 1 P(Q-1
|1) Q-1

Figure 1.2 Transition probability diagrams :

(a) binary symmetric channel ;
(b) binary-input , Q-ary-output discrete
memoryless channel

2015/9/18 Yuh-Ming Huang CSIE, NCNU Introduction 29

 q1

1-q1 s1 s2 q2

good 1-q2 bad

q1<< q2
State S 1 p1<<p2 State S2

1- p1 1- p2
0 0 0 0
e.g. p2
p1
p1 ≈ 0
p2
p2 ≈ 0.5 p1
1 1 1 1
1- p1 1- p2
Figure 1.7 Simplified model of a channel with memory
e.g. radio channel : error bursts are caused by signal fading

2015/9/18 Yuh-Ming Huang CSIE, NCNU Introduction 30

 Error Control Strategies
 Forward Error Correction (FEC)
 one-way system
 e.g. magnetic tape storage system
 deep-space communication system
 Automatic Repeat Request (ARQ)
 error detection and retransmission
 two-way system
 e.g. telephone channel
 types
 stop-and wait ARQ
 continuous ARQ
 e.g. go-back-N ARQ ; select-repeat ARQ

2015/9/18 Yuh-Ming Huang CSIE, NCNU Introduction 31

 Advantage of ARQ over FEC
 simpler decoding equipment
 For high-speed data network, which is
the better ?

2015/9/18 Yuh-Ming Huang CSIE, NCNU Introduction 32