Digital Communications I: Modulation and Coding Course Term 3 - 2008 Catharina Logothetis Lecture 9 Last time we talked about: Evaluating the average probability of symbol error for different bandpass modulation schemes Comparing different modulation schemes based on their error performances. Lecture 9 2 Today, we are going to talk about: Channel coding Linear block codes The error detection and correction capability

Encoding and decoding Hamming codes Cyclic codes Lecture 9 3 Block diagram of a DCS Format Source encode Channel encode Pulse modulate Bandpass modulate Channel Digital modulation Digital demodulation Format Source decode

Channel decode Lecture 9 Detect Demod. Sample 4 What is channel coding? Channel coding: Transforming signals to improve communications performance by increasing the robustness against channel impairments (noise, interference, fading, ...) Waveform coding: Transforming waveforms to better waveforms Structured sequences: Transforming data sequences into better sequences, having structured redundancy. -Better in the sense of making the decision process less subject to errors. Lecture 9 5

Error control techniques Automatic Repeat reQuest (ARQ) Forward Error Correction (FEC) Full-duplex connection, error detection codes The receiver sends feedback to the transmitter, saying that if any error is detected in the received packet or not (Not-Acknowledgement (NACK) and Acknowledgement (ACK), respectively). The transmitter retransmits the previously sent packet if it receives NACK. Simplex connection, error correction codes The receiver tries to correct some errors Hybrid ARQ (ARQ+FEC) Full-duplex, error detection and correction codes Lecture 9

6 Why using error correction coding? Error performance vs. bandwidth Power vs. bandwidth P Data rate vs. bandwidth Coded Capacity vs. bandwidth B A F Coding gain: For a given bit-error probability, the reduction in the Eb/N0 that can be realized through the use of code: Eb [dB] G [dB] N0 u Eb [dB] N0 c Lecture 9

C B D E Uncoded Eb / N 0 (dB) 7 Channel models Discrete memory-less channels Binary Symmetric channels Discrete input, discrete output Binary input, binary output Gaussian channels Discrete input, continuous output

Lecture 9 8 Linear block codes Let us review some basic definitions first that are useful in understanding Linear block codes. Lecture 9 9 Some definitions Binary field : The set {0,1}, under modulo 2 binary addition and multiplication forms a field. Addition 0 0 0 0 1 1 1 0 1 1 1 0 Multiplication 0 0 0

0 1 0 1 0 0 1 1 1 Binary field is also called Galois field, GF(2). Lecture 9 10 Some definitions Fields : Let F be a set of objects on which two operations + and . are defined. F is said to be a field if and only if 1. F forms a commutative group under + operation. The additive identity element is labeled 0. a, b F a b b a F 1. F-{0} forms a commutative group under . Operation. The multiplicative identity element is labeled 1. a, b F a b b a F 1. The operations + and . are distributive:

a (b c) (a b) (a c) Lecture 9 11 Some definitions Vector space: Let V be a set of vectors and F a fields of elements called scalars. V forms a vector space over F if: 1. Commutative:u, v V u v v u F 2.a F , v V a v u V 3. Distributive: (a b) v a v b v and a (u v) a u a v 4. Associative:a, b F , v V (a b) v a (b v ) 5. v V, 1 v v Lecture 9 12 Some definitions Examples of vector spaces The set of binary n-tuples, denoted Vnby

V4 {(0000), (0001), (0010), (0011), (0100), (0101), (0111), (1000), (1001), (1010), (1011), (1100 ), (1101), (1111 )} Vector subspace: Vn A subset S of the vector space subspace if: is called a The all-zero vector is in S. The sum of any two vectors in S is also in S. Example: {(0000), (0101), (1010), (1111)} is a subspace of V4 . Lecture 9 13 Some definitions Spanning set: A collection of vectors , is G v1 , v 2 , , v n said to be a spanning set for V or to span V if

linear combinations of the vectors in G include all vectors in the vector space V, Example: (1000), (0110), (1100), (0011), (1001) spans V4 . Bases: The spanning set of V that has minimal cardinality is called the basis for V. Cardinality of a set is the number of objects in the set. Example: (1000), (0100), (0010), (0001) Lecture 9 is a basis for V4 . 14 Linear block codes Linear block code (n,k)

k 2 A set C Vn with cardinality is called a linear block code if, and only if, it is a subspace of the vector space . Vn Vk C Vn Members of C are called code-words. The all-zero codeword is a codeword. Any linear combination of code-words is a codeword. Lecture 9 15 Linear block codes contd Vk Vn mapping C Bases of C

Lecture 9 16 Linear block codes contd The information bit stream is chopped into blocks of k bits. Each block is encoded to a larger block of n bits. The coded bits are modulated and sent over the channel. The reverse procedure is done at the receiver. Channel Data block encoder k bits n-k Codeword n bits Redundant bits

k Rc Code rate n Lecture 9 17 Linear block codes contd The Hamming weight of the vector U, denoted by w(U), is the number of nonzero elements in U. The Hamming distance between two vectors U and V, is the number of elements in which they differ. d (U, V ) w(U V ) The minimum distance of a block code is d min min d (U i , U j ) min w(U i ) i j i Lecture 9 18 Linear block codes contd Error detection capability is given by

e d min 1 Error correcting-capability t of a code is defined as the maximum number of guaranteed correctable errors per codeword, that is d min 1 t 2 Lecture 9 19 Linear block codes contd For memory less channels, the probability that the decoder n n j decoding commits an Perroneous is n j p (1 p) M j

j t 1 p is the transition probability or bit error probability over channel. The decoded bit error probability is 1 PB n n j n j j p ( 1 p ) j t 1 j n Lecture 9

20 Linear block codes contd Discrete, memoryless, symmetric channel model 1-p 1 1 p Tx. bits Rx. bits p 0 1-p 0 Note that for coded systems, the coded bits are modulated and transmitted over the channel. For example, for M-PSK modulation on AWGN channels (M>2): 2 log 2 M Ec 2 log 2 M Eb Rc 2 2

p Q sin Q sin log 2 M N0 M log M N M 2 0 Ec Rc Eb E c where is energy per coded bit, given by Lecture 9 21 Linear block codes contd Vn mapping Vk

C Bases of C A matrix G is constructed by taking as V1 , V2 , , Vk } its rows the vectors of the {basis, v11 v12 v1n . V1 G Vk v 21 vk 1 v22 vk 2 Lecture 9 v2 n

vkn 22 Linear block codes contd Encoding in (n,k) block code U mG V1 V (u1 , u 2 , , u n ) (m1 , m2 , , mk ) 2 Vk (u1 , u 2 , , u n ) m1 V1 m2 V2 m2 Vk The rows of G are linearly independent. Lecture 9 23 Linear block codes contd Example: Block code (6,3) Message vector V1 1 1 0 1 0 0

G V2 0 1 1 0 1 0 V3 1 0 1 0 0 1 Lecture 9 Codeword 000 100 010 000000 110100 011010 110 001 101 011 1 11 1 011 1 0 1 01 0 0 1 0 111 0 1 1 1 0 011 0 0 0 1 11 24 Linear block codes contd Systematic block code (n,k)

For a systematic code, the first (or last) k elements in the codeword are information bits. G [ P I ] k I k k k identity matrix Pk k (n k ) matrix U (u1 , u2 ,..., un ) ( p1 , p2 ,..., pn k , m1 , m2 ,..., mk ) parity bits Lecture 9 message bits 25 Linear block codes contd For any linear code we can find a matrix H ( n k )n , such that its rows G of : are orthogonal to the rows T GH 0 H is called the parity check matrix and its rows are linearly independent. T For systematic codes: H linear

[I n k Pblock ] Lecture 9 26 Linear block codes contd Data source Format m Channel encoding U Modulation channel Data sink Format m Channel decoding r

Demodulation Detection r U e r (r1 , r2 ,...., rn ) received codeword or vector e (e1 , e2 ,...., en ) error pattern or vector Syndrome testing: S is the syndrome of r, corresponding to the error pattern Se.rH T eH T Lecture 9 27 Linear block codes contd Standard array For rowi 2,3,...,2 n k find a vector V inn of minimum weight that is not already listed in the array. i : th e i

Call this pattern zerocorresponding codeword coset leaders U1 e2 e 2 n k and form the coset U2 e2 U2 e 2 n k U 2 Lecture 9 row as the U 2k e 2 U 2k e 2 n k U 2 k coset

28 Linear block codes contd Standard array and syndrome table decoding S rHT 1. Calculate S e e i 2. Find the coset , corresponding r leader, U e m to . 3. Calculate and the corresponding . r e (U e) e U (e e ) U e e Note that e e, the error is corrected. If If , undetectable decoding error occurs.

Lecture 9 29 Linear block codes contd Example: Standard array for the (6,3) code 000000 000001 000010 000100 001000 010000 100000 010001 codewords 110100 110101 110111 110011 111100 100100 010100 100101 011010 011011 011000 011100

101110 101111 101100 101010 101001 101000 101011 101101 011101 011100 011111 011010 110011 110010 110001 110111 000111 000110 000101 000110 coset

010110 Coset leaders Lecture 9 30 Linear block codes contd Error pattern Syndrome 000000 000001 000010 000100 001000 010000 100000 010001 000 101 011 110 001 010 100 111 U (101110) transmitted. r (001110) is received. The syndrome of r is computed : S rH T (001110) H T (100) Error pattern corresponding to this syndrome is

e (100000) The corrected vector is estimated r e (001110) (100000) (101110) U Lecture 9 31 Hamming codes Hamming codes Hamming codes are a subclass of linear block codes and belong to the category of perfect codes. m 2are expressed as a function of Hamming codes a single integer . m Code length : n 2 1 Number of information bits : k 2 m m 1 Number of parity bits : n-k m Error correction capability : t 1

The columns of the parity-check matrix, H, consist of all non-zero binary m-tuples. Lecture 9 32 Hamming codes Example: Systematic Hamming code (7,4) 1 0 0 0 1 1 1 H 0 1 0 1 0 1 1 [I 33 0 0 1 1 1 0 1 0 1 1 1 0 0 0 1 0 1 0 1 0 0 [P G 1 1 0 0 0 1 0 1 1 1 0 0 0 1 Lecture 9 PT ] I 44 ] 33 Cyclic block codes

Cyclic codes are a subclass of linear block codes. Encoding and syndrome calculation are easily performed using feedback shift-registers. Hence, relatively long block codes can be implemented with a reasonable complexity. BCH and Reed-Solomon codes are cyclic codes. Lecture 9 34 Cyclic block codes A linear (n,k) code is called a Cyclic code if all cyclic shifts of a codeword are also codewords. U (u0 , u1 , u2 ,..., un 1 ) U (i ) i cyclic shifts of U

(un i , un i 1 ,..., un 1 , u0 , u1 , u2 ,..., un i 1 ) Example: U (1101) U (1) (1110 ) U ( 2) (0111) U (3) (1011) U ( 4) (1101) U Lecture 9 35 Cyclic block codes Algebraic structure of Cyclic codes, implies expressing codewords in polynomial form U( X ) u0 u1 X u 2 X 2 ... un 1 X n 1 degree (n-1) Relationship between a codeword and its cyclic shifts: XU( X ) u0 X u1 X 2 ..., un 2 X n 1 un 1 X n un 1 u0 X u1 X 2 ... un 2 X n 1 un 1 X n un 1 U (1 ) ( X ) u n 1 ( X n 1) U (1) ( X ) un 1 ( X n 1) U (1) ( X ) XU( X ) modulo ( X n 1)

Hence:By extension U ( i ) ( X ) X i U( X ) modulo ( X n 1) Lecture 9 36 Cyclic block codes Basic properties of Cyclic codes: Let C be a binary (n,k) linear cyclic code g( X ) 1. Within the set of code polynomials in C, r monic n. g ( X )polynomial there is a unique with minimal degree is r ( X ) generator g 0 g1 X polynomial. ... g r X calledgthe U( X ) U( X ) min

( XC)gcan ( X ) be 1. Every code polynomial expressed uniquely as g ( X ) X n 1generator polynomial 2. The is a factor of Lecture 9 37 Cyclic block codes The orthogonality of G and H in n ( X )h( X ) X polynomial form is gexpressed as 1 . This means is h( X ) X nalso 1 a factor of i, i 1,..., k 1. The row , of the generator " i 1" matrix is formed by the coefficients of of g r the generator 0

g 0 gshift 1 the g( X ) cyclic g g g 0 1 r polynomial. Xg ( X ) G k1 X g ( X ) 0

g0 g1 g r g0 Lecture 9 g1 g r 38 Cyclic block codes Systematic encoding algorithm for an (n,k) Cyclic code: m( X ) 1. Multiply the message polynomial n k X by

1. Divide the result of Step 1 by the (X ) p( X ) . Let generator gpolynomial the reminder. be p( X ) X n k m( X ) (X ) 1. U Add to to form the codeword Lecture 9 39 Cyclic block codes Example: For the systematic (7,4) Cyclic g( X ) 1 X X 3 code with generator polynomial 1. Find the codeword for the message m (1011) n 7, k 4, n k 3 m (1011) m( X ) 1 X 2 X 3

X n k m( X ) X 3m( X ) X 3 (1 X 2 X 3 ) X 3 X 5 X 6 Divide X n k m( X ) by g ( X) : X 3 X 5 X 6 (1 X X 2 X 3 )(1 X X 3 ) 1 quotient q(X) generator g(X) remainder p ( X ) Form the codeword polynomial : U ( X ) p( X ) X 3m ( X ) 1 X 3 X 5 X 6 U (1 0 0 1 0 1 1 ) parity bits message bits Lecture 9 40 Cyclic block codes Find the generator and parity check matrices, G and H, respectively. g( X ) 1 1X 0 X 2 1X 3 ( g 0 , g1 , g 2 , g 3 ) (1101) 1 0 G 0 0

1 0 1 0 0 0 1 1 0 1 0 0 0 1 1 0 1 0 0 0 1 1 0 1 1 0 G 1 1 1 1 1 0 P 0 1 1 1 1 0 0 0 0 1 0 0

0 0 1 0 0 0 0 1 I 44 Lecture 9 Not in systematic form. We do the following: row(1) row(3) row(3) row(1) row(2) row(4) row(4) 1 0 0 1 0 1 1 H 0 1 0 1 1 1 0 0 0 1 0 1 1 1 I 33 PT 41 Cyclic block codes

Syndrome decoding for Cyclic codes: Received codeword in polynomial form is given by Received codeword r ( X ) U( X ) e( X ) Error pattern The syndrome is the remainder obtained by dividing the received polynomial by the generator polynomial. r ( X ) q( X )g( X ) S( X ) Syndrome With syndrome and Standard array, the error is estimated. In Cyclic codes, the size of standard array is considerably reduced. Lecture 9 42 Example of the block codes

PB 8PSK QPSK Eb / N 0 [dB] Lecture 9 43