Convolutional Codes.pdf

Convolutional Codes In block coding, the encoder accepts a k-bit message block and generates an n-bit code word. Thus, codewords are produced on a block-by-block basis. – Buffering is needed. m1

m2

m2

m1

Block code Encoder

c1

c2

c2

c1

In some applications, message bits come in serially rather than in large blocks. WY Tam - EIE POLYU

Conv.1

Convolutional Codes A convolutional encoder generates redundant bits by using modulo-2 convolutions. In a convolutional code, the block of n code digits generated by the encoder in a time unit depends not only the block of k message digit with that time unit, but also the preceding N-1 block of message digits. Usually the values of k and n are small. (the redundant bits are generated by using modulo-2 convolutions.) m1 m2

m2 m1

Convolutional Encoder WY Tam - EIE POLYU

c1 c2

c1≠c2 Conv.2

1

Code rate For a convolutional encoder with n modulo-adder and M Flip-flop, an L-bit message produces n( L + M ) bits

L Input Flip-flop 1 n( L + M ) 1 ≈ Q L >> M n

Flip-flop M

r=

Adder n

Adder 1

Output WY Tam - EIE POLYU

Conv.3

Constraint length Constraint length K is the number of shifts over which a single message can influence the encoder output K=M+1 Input Flip-flop 1

Flip-flop M

Adder n

Adder 1

Output WY Tam - EIE POLYU

Conv.4

2

Example For n=2, K=3 An 1000 bit message sequence produces a coded output sequence of 2(1000+2) bits. The code rate is r=

Input

1000 1000 ≈ = 1/ 2 2(1000 + 2) 2000

Output WY Tam - EIE POLYU

Conv.5

Example A convolutional code with rate k/n can be implemented by using k separate shift register and n adders Example:

Input

An L-bit message produces 3(M/2+L/2) bits. Therefore, r=

L 2 ≈ 3(2 / 2 + L / 2) 3 WY Tam - EIE POLYU

Output Conv.6

3

Impulse Response and Generator polynomial Impulse response – response of a path to a symbol 1 applied to its input Example: Impulse response of path 1 is (1,1,1) Impulse response of path 2 is (1,0,1) Input

Path 1

Path 2

Output WY Tam - EIE POLYU

Conv.7

Impulse Response and Generator polynomial The impulse response can be represented by a polynomial Example: (1,0,1,1) can be written as 1 + 0 ⋅ D + 1⋅ D 2 + 1⋅ D 3 = 1 + D 2 + D 3

Example: (1,1,1) can be written as g(1)(D)=1+D+D2 (1,0,1) can be written as g(2)(D)=1+D2 Input

Path 1

Path 2 Output

WY Tam - EIE POLYU

Conv.8

4

Impulse Response and Generator polynomial For the message sequence (10011), we have m(D)=1+D3 +D4 As the convolution in the time domain is transformed into multiplication in D-domain The output of path 1 is c(1)(D)= g(1)(D) m(D)= (1+D+D2)(1+D3 +D4) = 1+D+D2+D3 +D6 = 1111001 WY Tam - EIE POLYU

Conv.9

Impulse Response and Generator polynomial The output of path 2 is c(2)(D)= g(2)(D) m(D)= (1+D2)(1+D3 +D4) = 1+D2+D3 +D4 +D5 +D6 = 1011111 Finally, multiplexing the two output sequence of path 1 (1111001) and path 2 (1011111) gives c = (11,10,11,11,01,01,11) Note: for the shift register to be restored to its zero initial state, a terminating sequence of K-1=2 zeros is appended to the last input bit of the message. These zeros is called the Conv.10 tail of the message. WY Tam - EIE POLYU

5

State diagram A Convolutional encoder can be specified by the state diagram. Example: (n=2,k=1,M=2) convolutional encoder The state of this encoder is the content of the 2-stage shift 1 1 0 register. Input

State: S0: 00 S1: 10 S2: 01 S3: 11

Path 1

Path 2 Output 10

Example: Suppose input is 1 and the original state is S1, the output would be 10 and the new state become S3 WY Tam - EIE POLYU

Conv.11

State diagram Original Input Output new 00 State state S0 00 0 00 00 S0 S1 10 0 01 01 11 01 S2 01 0 01 00 01 S1 S3 11 S2 0 00 01 00 1 11 10 10 10 10 1 10 11 00 01 1 10 10 S3 Input=1 11 1 11 11 Input=0

WY Tam - EIE POLYU

11 State diagram Conv.12

6

Trellis diagram To show the time evolution of the coded sequence, a trellis diagram is used. – Trellis diagram is obtained directly from the state diagram by including, from left-to-right, the dimension of time 00 S0

00 11

S0 S1

00 11 01 10

Input=101 Output=110110

S0

S0

S1

S1

10

S2 S3

01

S0

00 Input=1 Input=0

S3

S1

01

S2

S2

11

10

10

S3

WY Tam - EIE POLYU

11 Conv.13

Decoding r

m Channel c Encoder

c'

m'

noise Channel Decoder

Since there is a one-to-one corresponding between m and c, m' = m if and only if c' = c To reducing the probability of decoding error, the maximum-likelihood principle is used to decode the received sequence r into a code sequence c which maximizes the likelihood function p(r|c) or log[p(r|c)]. known

Unknown WY Tam - EIE POLYU

Conv.14

7

Maximum-likelihood Decoding Assume that a codeword c=(c0,c1,…,cN) is transmitted through a binary symmetric channel and the received sequence is r = (r0,r1,…,rN)

1− p

1 0

p 1 p

1− p

0

N

P (r | c) = Π p(ri | ci ) i −0

N

⇒ log P (r | c) = ∑ log p (ri | ci ) i −0

Q log( AB ) = log A + log B

Maximum-likelihood decoding is obtained by choosing the nearest codeword to the received sequence in Hamming distance which maximum the likelihood function. WY Tam - EIE POLYU

Conv.15

Maximum-likelihood Decoding Assume d(r,c)=d, the likelihood function becomes N log P(r | c) = ∑ log p (ri | ci ) i −0

= d log p + ( N − d ) log(1 − p )  p   + N log(1 − p) = d log 1 − p  

1− p

1 0

p 1 p

1− p

0

 p   < 1 log 1− p 

As Nlog(1-p) is a constant for all c and p<1/2 in practice, the maximum-likelihood decding rule become choose the estimate c’ that minimizes the Hamming distance between the r and c WY Tam - EIE POLYU

Conv.16

8

Viterbi algorithm To decode the received sequence r, it is compared with each possible transmitted code vector c, and the particular one closest to r is chosen as the correct transmitted code vector. Min{d(r,c)} for all possible c Viterbi decoder The Viterbi decoder chooses that path through the trellis of the code which has a minimum Hamming distance from the received sequence. d (r , c) = ∑ d (ri , ci ) i

WY Tam - EIE POLYU

Conv.17

Example Suppose m=10111 then c = (11,01,10,10,11,00,01) r = (11,01,11,10,11,00,01) Time Received word 0 11

Input Path 1

Trellis diagram S0 S1

00 11

ds

m’

2 0

0 1

Path 2 Output

Estimated message

1

∑ d (r , c ) i

i =0 Initial state must be 00 Two possible paths from S0 WY Tam - EIE POLYU

i

Conv.18

9

Example Time Received word 1 10

2

r = (11,01,11,10,11,00,01) Trellis diagram S0 00 00 11 11 S1 01 S2 10 S3

01

3 3 0 2

S3

Example

10

Conv.19

r = (11,01,11,10,11,00,01) 00 01

11

S2

S1

100 101 010 111

Finally, we have S0 S1

11

11

2

WY Tam - EIE POLYU

S0

00 01 01 S2 10 10 00 11 S3

00 00 00 ds=5 1 S0 11 11 01 ds=1 S1 1 01 01 S2 4 10 11

11

00

m’

ds

01

00 10

c’=(10,01,10,10,11,00,01) m’ =(1011100)

10

S1 10

S3

00

11

S3

11

01

S2 00

10

S0

11

13

∑ d (r , c ) = 1 i =0

WY Tam - EIE POLYU

i

i

Conv.20

10

Error Probability r

m Channel c Encoder

noise

Error Correction

c'

Decoder

m'

PBlock – probability of a transmitted codeword does not correspond to the decoded codeword PBlock = P (c' ≠ c) PBit – probability of a transmitted information bit is incorrect PBit = P (m' ≠ m) WY Tam - EIE POLYU

Conv.21

Error Probability Consider a Binary Symmetric Channel (BSC) 1 0

1− p

1− p

p 1 p

0

Probability of t errors occur during transmission of a binary codeword consisting of n bits is  n  n n! p (t ) =   p t (1 − p ) n −t where   =  t  (n-t)!t! t Example: n = 3, t = 1, the patterns for sending 111 are 011, 101, 110.  3 3!   = =3 1 1! (3 1)! WY Tam - EIE POLYU Conv.22

11

Error Probability If e = (d min − 1) / 2 ,  n j   p (1 − p ) n − j ∑ j = e +1  j  e  n = 1 − ∑   p j (1 − p ) n − j j =0  j 

PBlock =

n

WY Tam - EIE POLYU

Conv.23

Example Repetition code of length n = 3. – a linear block code with k = 1 and n = 3. – Codewords are 000 and 111. • dmin = 3 • Correction capability: (d min − 1) / 2 = 1 1

PBlock = 1 − ∑ C nj p j (1 − p ) n − j j =0

= 1 − p 0 (1 − p ) 3 − 3 p (1 − p ) 2

(PBit = Pblock) If p = 0.01, PBlock= 0.000298. • 97% of error are corrected. • Error rate has been reduced by 34 times. WY Tam - EIE POLYU

Conv.24

12

Applications of Channel coding: LBC Linear Block Code Hamming code have been used in error control of computer memories and long-distance telephony. Example: In ECC memory, 64 bits data are stored in 72 bit physical memory. Can correct 1 error bit and detect 2 error bits

WY Tam - EIE POLYU

Conv.25

Applications of Channel coding: CRC 16 bit CRC-ITU CRC codes are used to perform error detection in almost all modern communication systems. Example: detecting errors at the data-link layer and the transport layer of the Open Systems Interconnection (OSI) reference model 16 bit CRC-ITU was recommended by ITU (International Telecommunication Union) for many applications. Example: Communication protocols: XYModem, Zmodem Kermit file-transfer protocols (FTPs) X.25 for packet communication WY Tam - EIE POLYU Conv.26

13

Applications of Channel coding: CRC In these applications, data-resending approach (ARQ automatic repeat request) is the simplest way to correct transmission errors. • Error detection only Long CRCs are more effective than short ones at detecting errors, but also introduce more overhead redundancy and implementation complexity.

WY Tam - EIE POLYU

Conv.27

Applications of Channel coding: CRC 8 bit CRC-ATM ATM (Asynchronous Transfer Mode) is a high-bandwidth, low-delay switching and multiplexing technology for both public and private communication networks – Aimed at users of high-speed data, local-area network interconnections, imaging and multimedia applications. Five layers: service layer adaptation layer ATM layer convergence layer physical layer WY Tam - EIE POLYU

Conv.28

14

Applications of Channel coding: CRC Employed in the adaptation layer of the ATM (Asynchronous Transfer Mode) protocol g(X ) = X 8 + X 2 + X + 1 CRC-12 Used when the character length is 6 bits

g ( X ) = X 12 + X 11 + X 3 + X 2 + X + 1 CRC-16 Used for 8-bit characters g ( X ) = X 16 + X 15 + X 2 + 1 WY Tam - EIE POLYU

Conv.29

Applications of Channel coding: CRC CRC-32 IBM Token-ring IBM PC Network CSMA/CD Ethernet LANs

g ( X ) = X 32 + X 26 + X 23 + X 22 + X 16 + X 12 + X 11 + X 10 + X 8 + X 7 + X 5 + X 4 + X 2 + X +1

WY Tam - EIE POLYU

Conv.30

15

Application of Channel Coding: BCH codes (511,493) BCH code ITU-T Recommendation H.261 – Video codec for audiovisual services at p x 64 kbit/s – video coding standard used for video conferencing and videophone

g ( X ) = X 18 + X 15 + X 12 + X 10 + X 8 + X 7 + X 6 + X 3 +1 (40,32) BCH code – used in the ATM (Asynchronous Transfer Mode ) layer of ATM WY Tam - EIE POLYU

Conv.31

Application of Channel Coding: RS codes RS (255,233) – recommended by Consultative Committee for Space Data Systems (CCSDS) for communication channel coding standard for spacecraft – Examples • Mars Observer launched in 1992 and arrived Mars in 1993 • Pathfinder lander launched in 1996 and arrived Mars in 1997 • Cassini launched in 1997 and to arrive Saturn in 2004 WY Tam - EIE POLYU

Conv.32

16

Application of Channel Coding: RS codes Compact Disc (CD) Source of errors – dust, fingerprints and scratches on the disc – surface roughness The CD error-control system is designed to handle bursts by means of Interleaving and the RS codes (Cross Interleaved RS code) 1.41Mbps

RS1

Interleaver

RS2

1.88Mbps

RS1: RS (28,24) RS2: RS (32,28) Also used for the CD-ROM, CD-I, and the MiniDisc WY Tam - EIE POLYU

Conv.33

Application of Channel Coding: RS codes Digital-Video-Disk (DVD) – Increased physical density implies that physical imperfections affect proportionally more bits – DVD is a true multimedia disc Therefore, a more powerful error-correction code is needed. RS1: RS (208,192)

RS2: RS (182,172)

Maximum correctable-burst length: CD: 500 bytes (2.4mm) DVD: 2200 bytes (4.6mm) WY Tam - EIE POLYU

Conv.34

17

Application of Channel Coding: Convolutional codes Global System for Mobile communications (GSM) Speech coding in GSM Microphone

Channel Speech Bandpass A/D Encoder Encoder filter Modulator 0.3-3.4kHz fs=8kHz 13 bits 13kbps 22.8kbps 104kbps

Three classes of speech data bits: Class I - Class III

WY Tam - EIE POLYU

Conv.35

Application of Channel Coding: Convolutional codes Step 1: Class I: block coded with a CRC code Class I

Class I

Class II

Class II

260bits

Class III

200ms

Class III

CRC bits (error detection) Class III

456bits

Step 2: Class I and Class II: convolutional coded (r=1/2, K=5) WY Tam - EIE POLYU

Conv.36

18

Application of Channel Coding: Convolutional codes Data Channel in the GSM system Five different data channels in the GSM system Example: 9.6 kbps data transmission 9.6 kbps Coding in the terminal equipment (base station) 4 0s to reset the encoder

240 bits (=12 kbps)

Convolutional code with r=1/2, K=5 488 bits

WY Tam - EIE POLYU

Conv.37

Application of Channel Coding: Convolutional codes Singaling Channel in the GSM system Most important data in the network 184 bits Block code (Fire code) for detection and correction of burst error 184 bits

4 0s to reset the encoder Check bits

40 bits

Convolutional code: r=1/2, K=5 456 bits

WY Tam - EIE POLYU

Conv.38

19

Application of Channel Coding: Convolutional codes CDMA cellular systems – CDMA: Code-division multiple access – users in the CDMA-based cellular system are distinguished from each other by a code – IS-95 (standard proposed by North America) PN code – spread the spectrum of a radio which shares access in a system by the use of a particular high speed pseduorandom (PN) code. WY Tam - EIE POLYU

Conv.39

Application of Channel Coding: Convolutional codes – If each radio has its own radio-specific PN code, then all radios, except the one it is desired to receive, look like noise to all other receivers in the system. Desired receiver

Code 1 Base Station

noise noise noise

WY Tam - EIE POLYU

Conv.40

20

Application of Channel Coding: Convolutional codes Reverse Channel (mobile unit to base station) r=1/3, K=9 Add 8 bit Convolutional encoder tail 4.4kbps 4.8kbps Encoder 14.4kbps

Symbol Repetition 28.8kbps

4.8kbps Interleaver

64-ary Modulator 28.8kbps PN chip: 1.2288 Mcps WY Tam - EIE POLYU

Conv.41

21