Error Correction and Detection Techniques for Digital Communication

Communication Communication Al-Mustansirya University College of Engineering Electrical Engineering Department Tutorial Tutorial Sheet Communication II Tutorial Sheet No.4 2008-2009 SheetNo. No.4 4 1. A source produces information in blocks of 3-bits. If the prob. of a block bi is given by P(bi) = i/36, i =1,2,. . . .,8 . These blocks are protected against error using a linear block code having the generator matrix : 0 0 1 1 0 1 1 0 1 1 0 1 0 1 [ G ] = 0 0 0 1 1 1 1 Find Prob. of logic zero at channel encoder o/p and the corrected word at the Rx for the received word [R]=[1110011]. 2. Information blocks appear with equal prob. and coded using binary linear block code having the parity check matrix : 0 1 1 1 0 0 1 1 1 0 1 0 [ H ] = 1 0 1 0 0 1 If the codewords are transmitted in bipolar form through AWGN-BSC having SNR of 12 dB . Find : a)prob. of decoding a correct word at the Rx . b)prob. of logic "1" at Rx input. c) the corrected word for [R]=[101110]. 3. A source of information produces equaiprobable blocks of 4-bits. The encoder cct adds an even parity bit for error detection. Prepare the encoder table then find the prob. of the logic pair "10" at encodero/p. 4. A (15,7) cyclic cod has the gen. Polynomial g(x) = 1+x4+ x6+ x7+ x8. a) Use the encoder cct to find the o/p codeword for information word [ 1011011]. b) Discuss error correction and detection capab. Of this code. 5. A (9,5) LBC has the correction bits : C1 = a1 + a3+a5 C2 = C1 +a4 C3 = C2 + a2 + a5 C4 = C3 + a4 + a3 + = Mod. 2 addition. Find the parity and Generator matrix of this code , then find the corrected word at the Rx for the received word [R]=[101011011]. 1

Communication Communication Tutorial Tutorial Sheet SheetNo.4 No.4 6. A cyclic code has the divisor D = 10100110111 is used to protect information In blocks of 5-bits then transmitted in bipolar form on AWGN-BSC having SNR of 6 dB . Find prob. of erroneous words at the Rx .check if [R]=[100100011110101] is correct or not using the logic cct of the decoder cct. 7. A linear systematic (6,3) LBC has been observed to give the following three o/p Codewords : Codeword 1 :100101 Codeword 2 :010011 Codeword 3 :001111 Find the parity check matrix of the code and find the corrected word at the Rx if [R]=[110001]. 8. Draw the state diagram and the trellis diagram of the convolution encoder having L =3 , K=1 , n=2 [g1]=[110] , [g2]=[011] . Using the trellis diagram find the o/p stream for information stream 10110 . . . . . . . 9. For prob. (Q.8) make a distributed random 3 errors at the o/p stream and then use Viterbi decoding algorithm at Rx to find the actual transmitted data sequence. 10. A binary message consists of words which are 5-bits long .The message words are to be encoded using a single error correcting code. a) What is the min. no. of check bits ? What are the parity and generator matrices dimensions. b) Construct an appropriate [H] matrix for systematic code. c)Find the syndrome at the Rx if the 5th. data bit is erroneous. d) How does this code respond to double errors. 8. Calculate the prob. of error for the following binary codes if the error prob. of a channel is Pe =10-3. Use Hamming bound to find the potential random- error capabilities. (n,k) codes : (7,4) , (15,11) , (15,7) , (15,5) , (31,11) , (31,6) . 12. Find the error correction capabilities of the following (15, k) codes for K = 14 , 11 , 10 , 5 , 4 . 2

Communication Communication Tutorial Tutorial Sheet SheetNo.4 No.4 13. Consider a single error correcting code for 4-bit message bits . a) How many check bits are required. b) Write a suitable gen. matrix. c) Find the syndrome if the error in the 3rd data bit. 14. Consider the (7,3) code with g(x) = x4+ x3+ x2+ 1. Find : a) Code table & min. Hamming weight. b) Use Hamming bound & find the error correction capabilities and show that this agrees with (a). c) Implement the encoder using g(x) polynomial .Calculate the check bits using the encoder cct. (Take a simple example of nonzero data word). 15. The generator matrix of a (7,3) systematic LBC is constructed as follows : 1) The 1st row is the action of a 2-input ORgate. 2) The 2nd row is the decimal of15. 3)The 3rd row is the action of a 2-input EX-OR gate. Find the code table & discuss the correction capabilities. 16. Draw the state & trellis diagram of the convolutional encoder having L =4 , K=1 , n=3 [g1]=[1101] , [g2]=[1001] , [g3]=[1100] . Find the o/p stream for input data sequence 10110 . . . . . . . 17. Assume the o/p stream of previous example is received with 3 errors chosen randomly. Perform Viterbi algorithm and verify the original data sequence. 18. Information in 8-bit blocks are protected against errors using a single error linear block code . Find the min. number of check bits required. Construct a suitable parity check matrix for the systematic code. Find the syndrome if the 3rd data bit is inerror. 19. A systematic cyclic cod with generator Polynomial P(x) = x4+ x3+ 1 is used to protect data grouped in blocks of 6-bits then transmitted over a BSC having error prob. of 0.01 . a) Using the encoder logic circuit , find the transmitted word for data word D = [ 100011]. b) Find the syndrome for double errors in the 1st & last positions. c)Find prob. of erroneous word at the Rx. 20. Design an encoder logic cct for the (7,3) systematic cyclic code with generator Polynomial g(x) = 1 + x + x4. Use it to find the codeword for data word [D] = [010]. 3

Communication Communication Tutorial Tutorial Sheet SheetNo.4 No.4 21. The generator matrix of a LBC is : 0 0 0 1 1 0 1 1 1 1 0 0 0 1 0 0 1 0 1 1 1 [ G ]= 0 1 0 1 1 1 0 1 1 0 0 0 1 1 1 1 1 0 0 a) Design a logic cct of the encoder . b) Discuss the error correction capability of this code using the code table. c) Find the syndromes for the following types of errors: ( i ) double errors in 5th & 6th positions ( from the left ) ( ii ) double errors in 1st & last positions. d)Correct the following received words : [R1] = [0011110001] & [R2] = [0111010010]. 22. A (7,3) cyclic code has gen. polynomial with g(x) = 1+x2+ x3+ x4, Find : a) Code table & min. Hamming weight. b) Error correction capability using Hamming bound then check with part (a) . c) The syndromes for single error at 1st position (from the right) & triple errors at (3rd , 4th & 5th ) positions from the right(comment). 23. A source of information produces the following codewords given with Their prob. Codeword Codeword1 Codeword2 Codeword3 Codeword4 Codeword5 message 0011010 1010000 0101100 1100010 0000010 Prob. 0.5 0.2 0.12 0.1 0.08 These codewords are encoded with an odd parity bit then transmitted : a) Find prob. of logic " 0 " at the source o/p. b) Find prob. of logic " 0 " at the encoder o/p. c) The min. Hamming distance at the encoder o/p. d) If one of these codewords are transmitted after encoding and the received word is 11110100 , what is the expected transmitted codeword based on Hamming distance calculation . 4

Communication Communication Tutorial Tutorial Sheet SheetNo.4 No.4 24. A source generates the following messages given with their prob. message 1010101 0101010 0100111 1001000 Prob. 0.45 0.3 0.15 0.1 A LBC with parity check matrix : [H] = [ 3, 5 , 9 , 10 , 11 , 17 , 28 , 1 , 2 , 4 , 8 , 16 ] decimal is used to protect these information . If codewords are transmitted through BSC with Pe = 0.04, Find: 1)P(0) at Tx o/p & Rx i/p. 2)prob. of corrected word at the Rx. 25. For the block diagram shown below : Source of BSC pe=0.15 LBC Receiver informatio The source of information produces the information in blocks of 3-bits. If the prob. of the blocks are : Block a1 0 0 0 0 1 1 1 1 Prob. a2 0 0 1 1 0 0 1 1 a3 0 1 0 1 0 1 0 1 0.32 0.2 0.15 0.1 0.07 0.05 0.04 0.04 Where [H] is given by : 1 0 1 1 0 0 1 1 1 0 1 0 [ H ] = 1 0 1 0 0 1 Find :- a) Prob. of logic zero at the channel encodero/p. b)Prob. of logic zero at the Rx i/p. c) If one of the received codeword is 100111, find the corrected codeword. 5

Communication Communication Tutorial Tutorial Sheet SheetNo. No.4 4 26. A rate 1/2 , L=3 , binary convolutional encoder is shown in fig. a) Draw the tree diagram, the state diagram & the trellis diagram. b) Using the ( tree, state & trellis ) diagrams, find the o/p stream for the information stream 1010 . . c)Find the o/p stream 11 00 00 use Viterbi decoding algorithm at Rx to find the actual transmitted data. C1 Output Input Q1 Q2 Q3 C2 27. Draw the state diagram for the ternary convolutional coder shown then find The o/p coded sequence for input data sequence 201210 . . Assume zero initial state. I/p data Ternary register V1 O/p Mod-3 V2 6