21
Channel Coding I Exercises WS 2009/2010 Carsten Bockelmann NW1, Room N 2360, Tel.: 0421/218-62386 E-mail: [email protected] Universit¨ at Bremen, FB1 Institut f¨ ur Telekommunikation und Hochfrequenztechnik Arbeitsbereich Nachrichtentechnik Prof. Dr.-Ing. K. D. Kammeyer Postfach 33 04 40 D–28334 Bremen WWW-Server: http://www.ant.uni-bremen.de Version from October 26, 2009

Channel Coding

Embed Size (px)

Citation preview

Page 1: Channel Coding

Channel Coding I

Exercises

– WS 2009/2010 –

Carsten BockelmannNW1, Room N 2360, Tel.: 0421/218-62386

E-mail: [email protected]

Universitat Bremen, FB1Institut fur Telekommunikation und Hochfrequenztechnik

Arbeitsbereich NachrichtentechnikProf. Dr.-Ing. K. D. Kammeyer

Postfach 33 04 40D–28334 Bremen

WWW-Server: http://www.ant.uni-bremen.de

Version from October 26, 2009

Page 2: Channel Coding

CONTENTS October 26, 2009 I

Contents

1 Introduction 1

Exercise 1.1: Design of a discrete channel . . . . . . . . . . . . . . .. . . . . . . . . 1

Exercise 1.2: Statistics of the discrete channel . . . . . . . . .. . . . . . . . . . . . . 1

Exercise 1.3: Binary symmetric channel (BSC) . . . . . . . . . . . .. . . . . . . . . 1

Exercise 1.4: Serial concatenation of two BSC . . . . . . . . . . . .. . . . . . . . . . 1

Exercise 1.5: Transmission of a coded data over BSCs . . . . . . .. . . . . . . . . . . 2

2 Information theory 3

Exercise 2.1: Entropy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . 3

Exercise 2.2: Channel capacity of a discrete memory-free channel . . . . . . . . . . . 3

Exercise 2.3: Channel capacity of a BSC . . . . . . . . . . . . . . . . . .. . . . . . . 3

Exercise 2.4: Channel capacity of the AWGN . . . . . . . . . . . . . . .. . . . . . . 4

3 Linear block codes 5

3.2 Finite field algebra . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . 5

Exercise 3.1: 2-out-of-5-code . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . 5

Exercise 3.2: Field . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . 5

3.3 Distance properties of block codes . . . . . . . . . . . . . . . . . .. . . . . . . . . . . 5

Exercise 3.3: Error correction . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . 5

Exercise 3.4: Sphere-packing bound . . . . . . . . . . . . . . . . . . . .. . . . . . . 6

3.5 Matrix description of block codes . . . . . . . . . . . . . . . . . . .. . . . . . . . . . 6

Exercise 3.5: Generator and parity check matrices . . . . . . . .. . . . . . . . . . . . 6

Exercise 3.6: Expansion, shortening, and puncturing of codes . . . . . . . . . . . . . . 6

Exercise 3.7: Coset decomposition and syndrome decoding . .. . . . . . . . . . . . . 7

Exercise 3.8: Coding program . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . 7

3.6 Cyclic Codes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . 7

Exercise 3.9: Polynomial multiplication . . . . . . . . . . . . . . .. . . . . . . . . . 7

Exercise 3.10: Polynomial division . . . . . . . . . . . . . . . . . . . .. . . . . . . . 8

Exercise 3.11: Generator polynomial . . . . . . . . . . . . . . . . . . .. . . . . . . . 8

Exercise 3.12: Syndrome . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . 8

Exercise 3.13: Primitive polynomials . . . . . . . . . . . . . . . . . .. . . . . . . . . 9

Exercise 3.14: CRC codes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . 9

3.7 Reed-Solomon- and BCH-codes . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . 9

Exercise 3.15: Reed-Solomon-codes . . . . . . . . . . . . . . . . . . . .. . . . . . . 9

Page 3: Channel Coding

CONTENTS October 26, 2009 II

Exercise 3.16: BCH-codes . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . 9

Exercise 3.17: Bit- and word error curves of BCH-codes . . . . .. . . . . . . . . . . 10

4 Convolution codes 11

4.1 Fundamental principles . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . 11

Exercise 4.1: Convolution code . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . 11

4.2 Characterization of convolution codes . . . . . . . . . . . . . .. . . . . . . . . . . . . 11

Exercise 4.2: Catastrophic codes . . . . . . . . . . . . . . . . . . . . . .. . . . . . . 11

4.3 Distance properties of convolution codes . . . . . . . . . . . .. . . . . . . . . . . . . . 11

Exercise 4.3: Distance properties of convolution codes* . .. . . . . . . . . . . . . . . 11

Exercise 4.4: Comparison of NSC- and RSC-codes* . . . . . . . . . .. . . . . . . . . 11

4.4 Puncturing of convolution codes of the rate1/n . . . . . . . . . . . . . . . . . . . . . . 12

Exercise 4.5: Puncturing of convolution codes* . . . . . . . . . .. . . . . . . . . . . 12

4.5 Optimal decoding with Viterbi-algorithm . . . . . . . . . . . .. . . . . . . . . . . . . 13

Exercise 4.6: Viterbi-decoding . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . 13

Exercise 4.7: Viterbi-decoding with puncturing . . . . . . . . .. . . . . . . . . . . . 13

Exercise 4.8: Coding and decoding of a RSC code . . . . . . . . . . . .. . . . . . . . 13

Exercise 4.9: Investigation to Viterbi-decoding . . . . . . . .. . . . . . . . . . . . . . 14

Exercise 4.10: Simulation of a convolution-coder and -decoder . . . . . . . . . . . . . 14

1 Introduction 1

Solution 1.1: Design of a discrete channel . . . . . . . . . . . . . . .. . . . . . . . . 1

Solution 1.3: Binary symmetric channel (BSC) . . . . . . . . . . . .. . . . . . . . . 1

Solution 1.4: Serial concatenation of two BSC . . . . . . . . . . . .. . . . . . . . . . 2

Solution 1.4: Transmission of a coded data over BSCs . . . . . . .. . . . . . . . . . . 2

2 Information theory 3

Solution 2.1: Entropy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . 3

Solution 2.2: Channel capacity of a discrete memory-free channel . . . . . . . . . . . 4

Solution 2.3: Channel capacity of a binary channel . . . . . . . .. . . . . . . . . . . 5

Solution 2.4: Channel capacity of the AWGN . . . . . . . . . . . . . . .. . . . . . . 8

3 Linear block codes 10

3.2 Finite field algebra . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . 10

Solution 3.1: 2-out-of-5-code . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . 10

Solution 3.2: Field . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . 12

Page 4: Channel Coding

CONTENTS October 26, 2009 III

Solution 3.3: Error correction . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . 12

3.3 Distance properties of block codes . . . . . . . . . . . . . . . . . .. . . . . . . . . . . 14

Solution 3.4: Sphere-packing bound . . . . . . . . . . . . . . . . . . . .. . . . . . . 14

3.5 Matrix description of block codes . . . . . . . . . . . . . . . . . . .. . . . . . . . . . 16

Solution 3.5: Generator and parity check matrices . . . . . . . .. . . . . . . . . . . . 16

Solution 3.6: Expansion, shortening, and puncturing of codes . . . . . . . . . . . . . . 17

Solution 3.7: Coset decomposition and syndrome decoding . .. . . . . . . . . . . . . 18

Solution 3.8: Coding program . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . 19

3.6 Cyclic codes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . 19

Solution 3.9: Polynomial multiplication . . . . . . . . . . . . . . .. . . . . . . . . . 19

Solution 3.10: Polynomial division . . . . . . . . . . . . . . . . . . . .. . . . . . . . 20

Solution 3.11: Generator polynomial . . . . . . . . . . . . . . . . . . .. . . . . . . . 21

Solution 3.12: Syndrome . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . 22

Solution 3.13: Primitive Polynomial . . . . . . . . . . . . . . . . . . .. . . . . . . . 23

Solution 3.14: CRC codes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . 24

3.7 Reed-Solomon- and BCH-codes . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . 25

Solution 3.15: Reed-Solomon-codes . . . . . . . . . . . . . . . . . . . .. . . . . . . 25

Solution 3.16: BCH-codes . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . 26

Solution 3.17: Bit and word error curves of BCH-codes . . . . . .. . . . . . . . . . . 27

4 Convolution codes 29

4.1 Fundamental principles . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . 29

Solution 4.1: Convolution code . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . 29

4.2 Characterization of convolution codes . . . . . . . . . . . . . .. . . . . . . . . . . . . 30

Solution 4.2: Catastrophic codes . . . . . . . . . . . . . . . . . . . . . .. . . . . . . 30

4.3 Distance properties of convolution codes . . . . . . . . . . . .. . . . . . . . . . . . . . 31

Solution 4.3: Distance properties of convolution codes . . .. . . . . . . . . . . . . . 31

Solution 4.4: Comparison of NSC- and RSC-codes . . . . . . . . . . .. . . . . . . . 33

4.4 Puncturing of convolution codes of the rate1/n . . . . . . . . . . . . . . . . . . . . . . 35

Solution 4.5: Puncturing of convolution codes . . . . . . . . . . .. . . . . . . . . . . 35

4.5 Optimal decoding with Viterbi-algorithm . . . . . . . . . . . .. . . . . . . . . . . . . 36

Solution 4.6: Viterbi-decoding . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . 37

Solution 4.7: Viterbi-decoding with puncturing . . . . . . . . .. . . . . . . . . . . . 37

Solution 4.8: Coding and decoding of a RSC code . . . . . . . . . . . .. . . . . . . . 39

Solution 4.9: Investigation to Viterbi-decoding . . . . . . . .. . . . . . . . . . . . . . 40

Page 5: Channel Coding

CONTENTS October 26, 2009 IV

Solution 4.10: Simulation of a convolution-coder and -decoder . . . . . . . . . . . . . 42

1 Introduction 2

Matlab solution 1.1: Design of a discrete channel . . . . . . . . .. . . . . . . . . . . 2

Matlab solution 1.2: Statistics of the channel . . . . . . . . . . .. . . . . . . . . . . . 3

Matlab solution 1.5: Transmission of a coded data over BSCs .. . . . . . . . . . . . . 5

2 Information theory 6

Matlab solution 2.1: Design of a discrete channel . . . . . . . . .. . . . . . . . . . . 6

Matlab solution 2.3: Channel capacity of a discrete memory-free channel . . . . . . . 6

3 Linear block codes 10

3.2 Finite field algebra . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . 10

Matlab solution 3.1: 2-out-of-5-code . . . . . . . . . . . . . . . . . .. . . . . . . . . 10

3.5 Matrix description of block codes . . . . . . . . . . . . . . . . . . .. . . . . . . . . . 12

Matlab solution 3.5: Generator and parity check matrices . .. . . . . . . . . . . . . . 12

Matlab solution 3.6: Expansion, shortening and puncturingof codes . . . . . . . . . . 13

Matlab solution 3.7: Coset decomposition and syndrome decoding . . . . . . . . . . . 14

Matlab solution 3.8: Coding program . . . . . . . . . . . . . . . . . . . .. . . . . . . 15

3.6 Cyclic Codes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . 17

Matlab solution 3.9: Polynomial multiplication . . . . . . . . .. . . . . . . . . . . . 17

Matlab solution 3.10: Polynomial division . . . . . . . . . . . . . .. . . . . . . . . . 18

Matlab solution 3.11: Generator polynomial . . . . . . . . . . . . .. . . . . . . . . . 18

Matlab solution 3.12: Syndrome . . . . . . . . . . . . . . . . . . . . . . . .. . . . . 19

Matlab solution 3.14: CRC codes . . . . . . . . . . . . . . . . . . . . . . . .. . . . . 21

3.7 Reed-Solomon- und BCH-Codes . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . 23

Matlab solution 3.15: Reed-Solomon-codes . . . . . . . . . . . . . .. . . . . . . . . 23

Matlab solution 3.16: BCH-Codes . . . . . . . . . . . . . . . . . . . . . . .. . . . . 24

Matlab solution 3.17: Bit- und Wortfehlerkurven von BCH-Codes . . . . . . . . . . . 26

4 Convolution codes 29

4.3 Distance properties of convolution codes . . . . . . . . . . . .. . . . . . . . . . . . . . 29

Matlab solution 4.3: Distance properties of convolution codes* . . . . . . . . . . . . . 29

Matlab solution 4.4: Comparison of NSC- and RSC-codes* . . . .. . . . . . . . . . . 31

4.4 Puncturing of1/n-rate convolution codes . . . . . . . . . . . . . . . . . . . . . . . . . 33

Matlab solution 4.5: Puncturing of convolution codes* . . . .. . . . . . . . . . . . . 33

Page 6: Channel Coding

CONTENTS October 26, 2009 V

4.5 Optimal decoding with Viterbi-algorithm . . . . . . . . . . . .. . . . . . . . . . . . . 36

Matlab solution 4.6: Viterbi-decoding . . . . . . . . . . . . . . . . .. . . . . . . . . 36

Matlab solution 4.6: Viterbi-decoding with puncturing . . .. . . . . . . . . . . . . . 37

Matlab solution 4.8: Coding and decoding of a RSC code . . . . . .. . . . . . . . . . 38

Matlab solution 4.9: Investigation to Viterbi-decoding . .. . . . . . . . . . . . . . . . 39

Matlab solution 4.10: Simulation of a convolution-coder and -decoder . . . . . . . . . 42

Page 7: Channel Coding

CONTENTS October 26, 2009 VI

General Information

• The dates for the exercises are arranged in the lectures and take place in room N 2250 or N 2410.The exercises cover the contents of past lectures and contain a theoretical part and a programmingpart, in general. The students are advised to repeat the corresponding chapters and to prepare theexercises for presenting them at the board.

• All references to passages in the text (chapter- and equation numbers) refer to the script: V. Kuhn,“Kanalcodierung I+II” in german language. References of equations in the form of (1.1) refer tothe script, too, whereas equations in the form (1) refer to solutions of the exercises.

• Although MATLAB is used in the exercises, no tutorial introduction can be given due to the limitedtime. A tutorial and further information can be found in

– MATLAB Primer, 3rd edition, Kermit Sigmon

– Practical Introduction to Matlab, Mark S. Gockenbach

– NT Tips und Tricks fur MATLAB, Arbeitsbereich Nachrichtentechnik, Universitat Bremen

– Einfuhrung in MATLAB von Peter Arbenz, ETH Zurich

available onhttp://www.ant.uni-bremen.de/teaching/kc/exercises/.

• Exercises not treated in the lesson are marked by *. Additional exercises, complete solutionsand all necessary MATLAB files can be found in K.-D. Kammeyer u. V. Kuhn:“Matlab in derNachrichtentechnik” , J. Schlembach Fachverlag, 2001, ISBN: 3-935340-05-2.

• PS-files of the tasks, solutions and MATLAB codes are available onhttp://www.ant.uni-bremen.de/whomes/wuebben/kc.

Within the university net the additional pagehttp://www.ant.uni-bremen.de/whomes/wuebben/kcis available. Beside the tasks and solutions you will find additional information on this page, e.g thematlab primer, the original paper of C. E. ShannonA mathematical theory of communication,some scripts and a preliminary version of the book ”Error-Control Coding” of B. Friedrichs!

Page 8: Channel Coding

1 INTRODUCTION October 26, 2009 1

1 Introduction

Exercise 1.1 Design of a discrete channel

a) Given is a transmitting alphabet consisting of the symbols −3, −1, +1, +3. They shall betransmitted over an AWGN-channel, which is real valued and has the varianceσ2

N = 1. At theoutput of the channel a hard-decision takes place, i.e. the noisy values are again mapped to the4 symbols (Aout = Ain), where the decision thresholds in each case lies in the middle of twosymbols. Calculate the transition probabilitiesP (Yµ|Xν) of the channel and represent them in amatrix.

b) Check the correctness of the matrix by checking the sums ofprobabilities to one.

c) Determine the joint probabilitiesP (Xν , Yµ) for equally probable transmitting symbols.

d) Calculate the occurrence probabilities for the channel output symbolsYµ.

e) Calculate the error probabilityPe(Xν) for the transmitting symbolsXν and the mean overall errorprobabilityPe.

Exercise 1.2 Statistics of the discrete channel

a) Given are the channels infigure 1. Complete the missing probabilities.

0.3

0.08

0.8

0.2 0.20.7

Channel 1 Channel 2

0.8X

0X

0Y0

Y0

X1

X1Y

2Y

2

Y1

Y1

Fig. 1: Discrete channel models

Exercise 1.3 Binary symmetric channel (BSC)

a) The word 0110100 is transmitted by a BSC with the error probability Pe = 0.01. Specify theprobability of receiving the word 0010101, wrongly.

b) Determine the probability ofm incorrectly received bits at the transmission ofn bits.

c) For a BSC with the error probabilityPe = 0.01, the probability of more than 2 errors at words ofthe length31 shall be determined.

Exercise 1.4 Serial concatenation of two BSC

Page 9: Channel Coding

1 INTRODUCTION October 26, 2009 2

Two BSC-channels withPe,1 andPe,2 shall be connected in series. Determine the error probability ofthe new channel.

Exercise 1.5 Transmission of a coded data over BSCs

Use Matlab to simulate the transmission of coded data over a Binary Symmetric Channel (BSC) witherror probabilityPe = 0.1. Apply repetition coding of rateRc = 1/5 for error protection.

Page 10: Channel Coding

2 INFORMATION THEORY October 26, 2009 3

2 Information theory

Exercise 2.1 Entropy

a) The average information contentH(Xν) of the signalXν (also called partial entropy) shall bemaximized. Determine the valueP (Xν), for which the partial entropy reaches its maximum valueand specifyH(Xν)max. Check the result with MATLAB by determining the partial entropy forP (Xν) = 0 : 0.01 : 1 and plottingH(Xν) overP (Xν).

b) The random vector(X1X2X3) can exclusively carry the values (000), (001), (011), (101)and(111) each with a probability of1/5.

Determine the entropies:

1. H(X1)

2. H(X2)

3. H(X3)

4. H(X1,X2)

5. H(X1,X2,X3)

6. H(X2|X1)

7. H(X2|X1 = 0)

8. H(X2|X1 = 1)

9. H(X3|X1,X2)

Exercise 2.2 Channel capacity of a discrete memory-free channel

Determine the channel capacity for the following discrete memory-free channel on condition thatP (Xν) =1/3 is valid.

1/2X

0Y

0

X2 Y

2

Y1

X1

1/31/6

1/61/2

1/3

1/2

1/31/6

Exercise 2.3 Channel capacity of a BSC

a) Derive the capacity for equally probable input symbolsP (X0) = P (X1) = 0.5 in dependence onthe error probability for a binary symmetric channel (BSC).

b) Prepare a MATLAB program, which calculates the capacity of an unsymmetric binary channel forthe input probabilitiesP (x) = 0 : 0.01 : 1. It shall be possible to set the error probabilitiesPe,x0

andPe,x1 at the program start. (Attention:P (y) must be calculated!)

Page 11: Channel Coding

2 INFORMATION THEORY October 26, 2009 4

1-Pe,x0

Pe,x0

1-Pex1

Pe,x1

x0 y0

y1x1

c) Determine the channel capacity for several error probabilities Pe at a fixed input probabilityP (x)within MATLAB . PlotC(Pe).

Exercise 2.4 Channel capacity of the AWGN

Derive the channel capacity for a bandwidth limited Gaussian channel (σ2n = N0/2) with a normal

distributed input (σ2x = Es) according to eq. (2.28).

Page 12: Channel Coding

3 LINEAR BLOCK CODES October 26, 2009 5

3 Linear block codes

3.2 Finite field algebra

Exercise 3.1 2-out-of-5-code

a) Given is a simple 2-out-of-5-code of the lengthn = 5 that is composed of any possible words withthe weightwH(c) = 2. Specify the codeC. Is it a linear code?

b) Determine the distance properties of the code. What is to be considered?

c) Calculate the probabilityPue of the occurrence of an undetected error for the considered code ata binary symmetric channel. The transition probabilities of the BSC shall be in the range10−3 ≤Pe ≤ 0.5. RepresentPue in dependence onPe graphically and depict also the error rate of theBSC in the chart.

d) Check the result of c) by simulating a data transmission scheme in MATLAB and measuring thenot detected errors for certain error probabilitiesPe of the BSC.Hint: ChooseN code words by random and conduct a BPSK-modulation. Subsequently, thewords are superposed with additive white, Gaussian distributed noise, where its power correspondsto the desired error probabilityPe = 0.5 · erfc(

Es/N0) of the BSC. After a hard-decision of thesingle bit, the MLD can be realized at the receiver by a correlation of the received word and allpossible code words with subsequent determination of the maximum. Subsequently, the errorshave to be counted.

e) Calculate the error probabilityPw at soft-decision-ML-decoding for the AWGN-channel.

f) Check the results of e) with the help of simulations in the range−2 dB ≤ Es/N0 ≤ 6 dB.Compare the obtained error rates with the uncoded case.Hint: You can use the same transmission scheme as in item d). But this time, the hard-decisionhas to be conducted after the ML-decoding.

Exercise 3.2 Field

Given are the setsMq := {0, 1, . . . , q − 1} and the two connections

• addition modulo q

• multiplication modulo q

Calculate the connection tables forq = 2, 3, 4, 5, 6 and specify, from whichq results a field.

3.3 Distance properties of block codes

Exercise 3.3 Error correction

Given is a(n, k)q block code with the minimal distancedmin = 8.

Page 13: Channel Coding

3 LINEAR BLOCK CODES October 26, 2009 6

a) Determine the maximal number of correctable errors and the number of detectable errors at pureerror detection.

b) The code shall be used for the correction of 2 errors and forthe simultaneous detection of 5 furthererrors. Demonstrate by illustration in the field of code words (cp. fig. 3.1), that this is possible.

c) Demonstrate by illustration in the field of code words, howmany possibilities of variation of acode word have to be taken into consideration at the transmission over a disturbed channel.

Exercise 3.4 Sphere-packing bound

a) A linear(n, 2)2-block code has the minimal Hamming distancedmin = 5. Determine the minimalblock length.

b) A binary codeC has the parametersn = 15, k = 7, dmin = 5. Is the sphere packing boundfulfilled? What does the right side minus the left side of the sphere packing bound (cp. eq. (3.7))state?

c) Can a binary code with the parametersn = 15, k = 7, dmin = 7 exist?

d) Check, if a binary code with the parametersn = 23, k = 12, dmin = 7 can exist.

e) A source-coder generates 16 symbols, that shall be coded binary with a correction capacity of 4 inthe channel coder. How great does the code rate have to be in any case?

3.5 Matrix description of block codes

Exercise 3.5 Generator and parity check matrices

a) State the generator- as well as the parity check matrix fora (n, 1, n) repetition code withn = 4.What parameters and properties does the dual code have?

b) The columns of the parity check matrix of a Hamming code of degreer represent all dual numbersfrom 1 to2r − 1. State a parity check matrix forr = 3 and calculate the corresponding generatormatrix. Determine the parameters of the code and state the code rate.

c) Analyze which connection is between the minimal distanceof a code and the number of linearindependent columns of the parity check matrixH by means of this example.

Exercise 3.6 Expansion, shortening, and puncturing of codes

a) Given is the systematical(7, 4, 3)-Hamming code from exercise 3.5. Expand the code by anadditional test digit such that it gets a minimum distance ofdmin = 4. State the generator matrixGE and the parity check matrixHE of the expanded (8,4,4)-code.Hint: Conduct the construction with the help of the systematic parity check matrixHS and notethe result from 3.5c.

Page 14: Channel Coding

3 LINEAR BLOCK CODES October 26, 2009 7

b) Shortening a code means the decrease of the cardinality ofthe field of code words, i.e. informationbits are cancelled. Shorten the Hamming code from above to the half of the code words and statethe generator matrixGK and the parity check matrixHK for the systematic case. What minimaldistance does the shortened code have?

c) Puncturing a code means gating out code bits which serves for increasing the code rate. Puncturethe Hamming code from above to the rateRc = 2/3. What minimal distance does the new codehave?

Exercise 3.7 Coset decomposition and syndrome decoding

a) State the number of syndromes of the(7, 4, 3)-Hamming code and compare it with the number ofcorrectable error patterns.

b) Make up a table for the systematic(7, 4, 3)-Hamming coder which contains all syndromes and thecorresponding coset leaders.

c) The wordy = (1 1 0 1 0 0 1) is found at the receiver. Which information wordu was sent with thegreatest probability?

d) The search for the position of the syndromes in H can be dropped by resorting the columns ofH.The decimal representation ofs then can directly be used for the addressing of the coset leader.Give the corresponding parity check matrixH.

Exercise 3.8 Coding program

a) Write a MATLAB -programm which codes and again decodes a certain number of input data bits.Besides it shall be possible to insert errors before the decoding. The(7, 4, 3)-Hamming code withthe generator matrix

G =

1 0 0 0 0 1 1

0 1 0 0 1 0 1

0 0 1 0 1 1 0

0 0 0 1 1 1 1

and the parity check matrix

H =

0 1 1 1 1 0 0

1 0 1 1 0 1 0

1 1 0 1 0 0 1

shall be used.

b) Extend the MATLAB program for taking up bit error curves in the range0 : 20 dB.

3.6 Cyclic Codes

Exercise 3.9 Polynomial multiplication

Given are the two polynomialsf(D) = D3 + D + 1 andg(D) = D + 1.

Page 15: Channel Coding

3 LINEAR BLOCK CODES October 26, 2009 8

a) Calculatef(D) · g(D). Check the result with MATLAB .

b) Give the block diagram of a nonrecursive system for a sequential multiplication of both polynomi-als.

c) Illustrate the stepwise calculation of the polynomialf(D) · g(D) in dependence on the symbolclock by means of a table.

Exercise 3.10 Polynomial division

Given are the two polynomialsf(D) = D3 + D + 1 andg(D) = D2 + D + 1.

a) Calculate the division off(D) by g(D). Check the result with MATLAB .

b) Give the block diagram of a recursive system for a sequential division of the polynomialf(D) bythe polynomialg(D).

c) Illustrate the stepwise calculation of the polynomialf(D) : g(D) in dependence on the symbolclock by means of a table.

Exercise 3.11 Generator polynomial

Given is a cyclic(15, 7) block code with the generator polynomialg(D) = D8 + D7 + D6 + D4 + 1.

a) Indicate thatg(D) can be a generator polynomial of the code.

b) Determine the code polynomial (code word) in systematical form for the messageu(D) = D4 +D + 1.

c) Is the polynomialy(D) = D14 + D5 + D + 1 a code word?

Exercise 3.12 Syndrome

The syndromess1 to s8 of a 1-error-correcting cyclic code are given.

s1 = 1 0 1 0 0s2 = 0 1 0 1 0s3 = 0 0 1 0 1s4 = 1 0 0 0 0s5 = 0 1 0 0 0s6 = 0 0 1 0 0s7 = 0 0 0 1 0s8 = 0 0 0 0 1

a) Determine the parity check matrixH and the generator matrixG.

b) State the number of test digitsn − k and the number of information digitsk.

c) What is the generator polynomialg(D)?

d) How many different code words can be built with the generator polynomialg(D)?

Page 16: Channel Coding

3 LINEAR BLOCK CODES October 26, 2009 9

e) The code wordy1 = (01101011) is received. Has this code word been falsified on the channel?Can the right code word be determined? If yes, name the right code word.

f) Now the code wordy2 = (1 0 1 1 0 1 1 1) has been received. Has this code word been falsified onthe channel? Can the right code word be determined? If yes, name the right code word.

Exercise 3.13 Primitive polynomials

Given are the two irreducible polynomialsg1(D) = D4 +D+1 andg2(D) = D4 +D3 +D2 +D+1.Which of these two polynomials is primitive?

Exercise 3.14 CRC codes

a) Generate the generator polynomial for a CRC code of the length n = 15.

b) Determine the generator matrixG and the parity check matrixH.

c) Now the efficiency of the CRC code shall be examined by considering the perceptibility of allburst errors of the length4 ≤ le ≤ n. Only error patterns with thele errors directly succeedingone another shall be taken into consideration. Give the relative frequency of the detected errors.

3.7 Reed-Solomon- and BCH-codes

Exercise 3.15 Reed-Solomon-codes

a) A RS-code in theGF (23) that can correctt = 1 error shall be generated. Determine the parametersk, n andRc and state the maximal length of a correctable error in bit.

b) Give the generator polynomialg(D) of the Reed-Solomon-code. Use the commandsrspolyresp. eq. (3.77).

c) The messageu = (110 010 111 000 001) shall be coded. At the subsequent transmission 3 bitsshall be falsified. How does the position of the error affect on the decoding result?

d) Now a t = 2 errors correcting code in theGF (8) shall be designed. Again determine theparametersk andRc and giveg(D).

e) The wordy = (000100001011 110010 111) is received. Determine the syndrome, the error digitpolynomial, the position of the error digits and the amplitudes of the errors. Use the commandsrssyndrom, rselp, rschien andrserramp. What was the transmitted message (correctionwith rscorrect )?

Exercise 3.16 BCH-codes

a) We now want to design at = 3 errors correcting BCH-code in theGF (24). Form the cyclotomiccosetsKi with the commandgfcosets. Which sets can be combined to one setKi for fulfillingthe challenget = 3. Which parameters does the resulting BCH-code have?

Page 17: Channel Coding

3 LINEAR BLOCK CODES October 26, 2009 10

b) With the commandbchpoly all valid parameter combinations can be announced, at declarationof the parametersn andk bchgenpoly supplies a generator polynomialg1(D) and the polyno-mialsmi(D) of those cyclotomic cosetsKi, that are involved ing(D). Choose a suitable code anddetermineg1(D) as well as the polynomialsmi(D).

c) Calculate an alternative generator polynomialg2(D) for the same parameters by means of theresults from item a) by hand.

d) Code the information wordu = (1 1 0 1 1) with the commandbchenc for the two generatorpolynomialsg1(D) andg2(D). Determine the zeroes of the two code wordsc1(D) andc2(D) andcompare them.

e) Transform the code words with the functionfft into the spectral range. What’s striking?

Exercise 3.17 Bit- and word error curves of BCH-codes

a) Simulate the transmission over an AWGN-channel for the standard BCH-code from exercise 3.16for the signal-to-noise ratios from 0 to 10 dB in 2-dB-steps.Conduct the BMD-decoding withbchdec as well as a ML-decoding by comparison with all possible codewords. Measure the bit-and word error rates and oppose the results of the different decoding methods in a diagram.

b) Compare the results with the uncoded case!

Page 18: Channel Coding

4 CONVOLUTION CODES October 26, 2009 11

4 Convolution codes

4.1 Fundamental principles

Exercise 4.1 Convolution code

Given is a convolution code with the code rateR = 1/3, memorym = 2 and the generator polynomialsg1(D) = 1 + D + D2 andg2(D) = 1 + D2 andg3(D) = 1 + D + D2.

a) Determine the output sequence for the input sequenceu = (0 1 1 0 1 0).

b) Sketch the corresponding Trellis chart in the case of the under a) given input sequence.

c) Sketch the state diagram of the encoder.

d) Determine the corresponding free distancedf .

4.2 Characterization of convolution codes

Exercise 4.2 Catastrophic codes

Given is the convolution code with the generator polynomialg(D) = (1 + D2, 1 + D). Show that thisis a catastrophic code and explain the consequences.

4.3 Distance properties of convolution codes

Exercise 4.3 Distance properties of convolution codes*

a) Given is the non-recursive convolution code with the generatorsg0(D) = 1+D+D3 andg1(D) =1 + D + D2 + D3. Determine by means of the MATLAB -routineiowef conv the IOWEF andpresentaw,d (in the script also calledTw,d) for even and odd input weights in separate diagrams(maximal distancedmax = 20). How large is the free distance of the code and what’s striking withreference to the weight distribution?

b) Calculate the coefficientsad andcd.

c) Estimate the word- and bit error rates with the help of theUnion Bound for the AWGN-channelin the range0 dB ≤ Eb/N0 ≤ 6 dB. Draw the determined error rates for several maximallyconsidered distancesd.

d) The convolution code shall now be terminated and considered as block code of the lengthn = 50.Determine the IOWEF with the functioniowef block conv and calculate the bit error ratewith the help of the routinepb unionbound awgn (now, the block lengthn = 50 and theinformation lengthk = 22 is to be specified). How can the difference to the results of item c) beexplained?

Exercise 4.4 Comparison of NSC- and RSC-codes*

Page 19: Channel Coding

4 CONVOLUTION CODES October 26, 2009 12

a) The generator polynomialg0(D) of the code from exercise 4.3 shall now be used for the feedbackof a recursive systematic convolution code. Determine the IOWEF of the code and again drawthem separately for even and odd input weights.

b) Now alternatively use the polynomialg1(D) for feedback. Again determine the IOWEF anddetermine for both RSC-codes the coefficientsad andcd. Compare them with those of the non-recursive code.

c) Estimate the bit error rates with the help of theUnion Bound for both RSC-codes and draw themtogether with the error rate of the non-recursive convolution code in a diagram. Which differencesare striking?

4.4 Puncturing of convolution codes of the rate1/n

Exercise 4.5 Puncturing of convolution codes*

a) The non-recursive convolution code from exercise 4.3 shall now be punctured to the code rateRc = 2/3. Give several puncturing patterns and find out, if the puncturing results in a catastrophiccode with the routinetkatastroph.

b) Determine for the suitable puncturing schemes from item a) the coefficientsad andcd and opposethem to those of the unpunctured code. Note, that the routineiowef block conv doesn’tconsider different starting instants of time and these therefore have to be entered manually (P1a =[3 1]T andP1b = [1 3]T yield different results).

c) Calculate an estimation of the bit error rate for the different puncturing patterns from item b) withthe routinepb unionbound awgn and draw it together with that of the unpunctured code in adiagram. Hand over a mean IOWEF of the under b) determined spectra to the routine.

d) Now puncture the code to the rateRc = 3/4 and consider the results from item a). Check if thecode is catastrophic.

e) For reaching higher code rates than 2/3 with this code, theRSC-code from exercise 4.4b) shallnow be punctured, where the systematic information bits arealways transmitted. Determine forthe code ratesRc = 3/4, Rc = 4/5 andRc = 5/6 the puncturing schemes and the resulting biterror rates for the AWGN-channel. Sketch them together withthose of the unpunctured code andof the code that is punctured to the rateRc = 2/3.

Page 20: Channel Coding

4 CONVOLUTION CODES October 26, 2009 13

4.5 Optimal decoding with Viterbi-algorithm

Exercise 4.6 Viterbi-decoding

Given is a convolution code withg0(D) = 1 + D + D2 andg1(D) = 1 + D2, where a terminated codeshall be used.

a) Generate the corresponding Trellis and code the information sequenceu(ℓ) = (1 1 0 1).

b) Conduct the Viterbi-decoding respectively for the transmitted code sequencex = (110101001011)and for the two disturbed receiving sequencesy1 = (111101011011) andy2 = (111110011011)and describe the differences.

c) Check the results with the help of a MATLAB -program.

Define the convolution code withG=[7;5],r flag=0 andterm=1, generate the trellis diagramwith trellis = make trellis(G,r flag) and sketch it withshow trellis(trellis).Encode the information sequenceu with c = conv encoder (u,G,r flag,term) anddecode this sequence withviterbi omnip(c,trellis,r flag,term,length(c)/n,1).

Decode now the sequencesy 1 andy 2.

Exercise 4.7 Viterbi-decoding with puncturing

Given is a convolution code withg0(D) = 1 + D + D2 andg1(D) = 1 + D2, out of which shall begenerated a punctured code by puncturing with the scheme

P1 =

(

1 1 1 0

1 0 0 1

)

a) Determine the code rate of the punctured code.

b) Conduct the Viterbi-decoding in the case of the undisturbed receiving sequencey = (1 1 0 0 0 1 0 1) (pay attention to the puncturing!).

Exercise 4.8 Coding and decoding of a RSC code

a) We now consider the recursive systematic convolution code with the generator polynomialsg0(D) =1 andg1(D) = (1+ D + D3)/(1+ D + D2 + D3). Generate the Trellis diagram of the code withthe help of the MATLAB -commandmake trellis([11;15],2).

b) Conduct a coding for the input sequenceu(ℓ) = (1 1 0 1 1). The coder shall be conducted to thezero state by adding tail bits (commandconv encoder (u,[11;15],2,1)). What are theoutput- and the state sequences?

c) Now the decoding of convolution codes with the help of the Viterbi-algorithm shall be considered.For the present the sequenceu(ℓ) = (1 1 0 1 1 0 0 1 1 1 1 0) has to be coded (with termination),modulated with BPSK and subsequently superposed by Gaussian distributed noise. Choose asignal-to-noise ratio ofEb/N0 = 4 dB. With the help of the programviterbi the decodingnow can be made. By setting the parameterdemo=1 the sequence of the decoding is representedgraphically by means of the Trellis diagram. What’s striking concerning the error distribution ifthe Trellis is considered as not terminated?

Page 21: Channel Coding

4 CONVOLUTION CODES October 26, 2009 14

d) Now the influence of the error structure at the decoder input shall be examined. Therefor specifi-cally add four errors, that you once arrange bundled and another time distribute in a block, to thecoded and BPSK-modulated sequence. How does the decoding behave in both cases?

Exercise 4.9 Investigation to Viterbi-decoding

a) Simulate a data transmission system with the convolutioncode from exercise 4.8, a BPSK-modulation,an AWGN-channel and a Viterbi-decoder. The block length of the terminated convolution codeshall beL = 100 bits. Decode the convolution code with the decision depths (K1 = 10, K2 = 15,K3 = 20, K4 = 30 und K5 = 50). The signal-to-noise ratio shall beEb/N0 = 4 dB. Whatinfluence does the decision depth have on the bit error rate?

b) Now puncture the convolution code to the rateRc = 3/4 and repeat item a). What about thedecision depths now?

c) Conduct simulations for an unknown final state. Evaluate the distribution of the decoding errors atthe output. What’s striking?

Exercise 4.10 Simulation of a convolution-coder and -decoder

Generate a MATLAB -program that codes, BPSK-modulates, transmits over an AWGN-channel and sub-sequently hard decodes an information sequenceu of the lengthk = 48 with the terminated convolutioncodeg = (5, 7). Take with this program the bit error curve forEb/N0 = 0 : 1 : 6 dB corresponding tofig. 4.14 by transmittingN = 1000 frames per SNR, adding the bit errors per SNR and subsequentlydetermining the bit error rate per SNR.

Therefor use the following MATLAB -functions:

trellis = make trellis(G,r flag

c= conv encoder(u,G,r flag,term)

u hat= viterbi(y,trellis,r flag,term,10)