Solved Problems Block Codes PDF

Preview

Summary

Postgraduate Course Assignment...

Description

ANU

ENGN 3226

AUSTRALIAN NATIONAL UNIVERSITY Department of Engineering

ENGN 3226 Digital Communications Problem Set #8 Block Codes Q1 Consider a (6,3) linear block code defined by the generator matrix →− = 1 0 0 1 1 0 G

0 1 0 0 1 1 0 0 1 1 0 1 →−

(a) Determine if the code is a Hamming code. Find the parity check matrix H of the code in systematic form.

(b) Find the encoding table for the linear block code. (c) What is the minimum distance dmin of the code. How many errors can the code detect. How many errors can the code correct. (d) Draw the hardware encoder diagram. (e) Find the decoding table for the linear block code. (f) Draw the hardware syndrome generator diagram. r 1 1 1 0 0 1 is received. Show how →− = (g) Suppose →− = correct this error. the code can c

1 1 1 0 0 0

is sent and

Q2 Consider a (7,4) linear block code defined by the generator matrix 1 0 0 0 1 1 0 →− = G 0 1 0 0 0 1 1 0

0

0

0

0

1

1

0

1

1

0

1

1

1

→−

(a) Determine if the code is a Hamming code. Find the parity check matrix H of the code in systematic form.

(b) Find the encoding table for the linear block code. (c) What is the minimum distance dmin of the code. How many errors can the code detect. How many errors can the code correct. (d) Draw the hardware encoder diagram. (e) Find the decoding table for the linear block code. (f) Draw the hardware syndrome generator diagram. (g) Suppose c = 1 0 0 1 0 1 1 is sent and r = 1 1 0 1 0 1 1 is received. Show correct this error. →− →− how the code can

Q3 Consider a (5,1) linear block code defined by the generator matrix →− = G 1 1 1 1 1 →− (a) Find the parity check matrix H of the code in systematic form. (b) Find the encoding table for the linear block code. (c) What is the minimum distance dmin of the code. How many errors can the code detect. How many errors can the code correct. (d) Draw the hardware encoder diagram. (e) Find the decoding table for the linear block code (consider single bit errors only). (f) Draw the hardware syndrome generator diagram. 0 1 1 1 1 is received. Show how the code →− = = →− (g) Suppose can correct this c

1 1

1 1 1 is sent and r

error.

Problem Set #8

page 1

ANU

ENGN 3226

Q4 Consider the generator polynomial for a (7,3) cyclic code defined by 4

3

2

g(p) = p + p + p + 1 (a) Find the encoding table for the cyclic code. (b) What is the minimum distance dmin of the code.

Q5 Consider the generator polynomial for a (7,4) cyclic code defined by 3

2

g(p) = p + p + 1 (a) Find the encoding table for the cyclic code. 1 1 1 1 .

(b) What is the minimum distance dmin of the code. c

(c) Find the systematic output codeword for input

Problem Set #8

→−

=

page 2

ANU

ENGN 3226

AUSTRALIAN NATIONAL UNIVERSITY Department of Engineering

ENGN 3226 Digital Communications Problem Set #8 Solution Q1: Complete Solution (a) Testing for hamming code, we have m = n −k = 6 −3 = 3 m

3

k = 2 −m −1 = 2 −3 −1 = 4 6= 3 m

3

n = 2 −1 = 2 −1 = 7 6= 6 Hence (6, 3) is not a Hamming code. We have →− G

=

1

0

0 1

1 0

0 1 0 0 1 1 0 0 1 1 0 1

→−

=

P →−

=

P

1 1 0 0 1 1 1 0 1 1 0 1

T

→− I

1 1 0 0 1 1

3

→−

H →−

1 1 0.

= =

→−

[→−

=

] P T .. I 1 0 1 n−k

1 0

H

0 1 1 0 1 1

1 0 1 1

1

0 0

0 0

1 0 0 1

(b) The encoding table for (6, 3) linear block code is Message 000 001 010 011 100 101 110 111

Code word 000000 001101 010011 011110 100110 101011 110101 111000

Problem Set #8

Weight of code word 0 3 3 4 3 4 4 3 page 3

ANU

ENGN 3226

This is calculated as follows

=0 0 0

c

0=

→−

m

0→−

→−

G

c

1=

→−

m

1→−

→−

=

0 0 0 0

=

0 0

=

0

1

G

c

2=

→−

m

0 1

=

0 1

=

0

0

3=

m

1 0

=

0 1

=

0

1

4=

m

1 1

1 0

0 1 0 0 0 0 1 1 1 1 0 0 1

1 1 0 1 ( 1 0

00 0

0

1

0

1

0 0

→−)

3rd row of G

1 1

0 0 1 1 0 1 0 0 1 1

1

0

1

0 0

0 1 0

(1

→−)

2nd row of G

1 1

=

1 0

=

1

0

0 0 1 1 1 1 0 0 1 1

0

0

1

0 0

0 1 1 0

(

→−

→− )

2nd row of G + 3rd row of G

1 1

4→−

→−

G = 5=

→−

m

0 0

1 0

1

0 0 1 1 1 1 0 0 1 1

0

0

1

0 0

0 1 1 0

(

→−)

1st row of G

1 1

5→−

→−

G

6=

→−

m

=

1

=

1 1

=

1

0 1 0

0 0 1 1 0 11 01 0 1 0

1

0 0

0 1 0

(1

→−

→− )

→−

→− )

1st row of G + 3rd row of G

1 1

6→−

→−

G = c

1

0

1

→−

→−

c

1 1

1 0 0 1

3→−

G

c

0 0

0 1 1 1

→−

→−

c

1

0 0

2→−

G

c

0

1 0

7=

→−

m

1 0

1 1

1

0 0 1 1 1 1 0 0 1 0

1

0

1

0 0

0 1 0

(1

1st row of G + 2nd row of G

1 1

7→−

→−

G =

1

1 1

0 0 1 1 0 1 →− (1st row of 0 0 0

→−

→−)

G + 2nd row of G + 3rd row of G

(c) From encoding table, we have dmin =

3

e = dmin −1 = 2 1 t

≤

2 (dmi n −1)

≤1

Hence the (6, 3) linear block code can detect 2 bit errors and correct 1 bit error in 6 bit output codeword.

Problem Set #8

page 4

ANU

ENGN 3226

(d) The output for general code word is

→−

→− = →−

123

=

mmm

cm G

1

0

0

0

0

1

=m1 m 2 m3 m1 + m3 The hardware encoder implementation is

m m1

m2

0 1 1

1 0

1

0 0

0

1

1 1

m1 + m2 m2 + m 3

c

(6,3) Linear block code encoder m3

c1

c2

c3

c4

c5

c6

Figure 1: Figure for Question 1 (d).

(e) We have

=

→− H

→− HT =

1 1 0 0 1 0 1 0 1 1 0 0 0 1 1 0 0 1 1 1 0 0 1 1 1 0 0 0 0

1

The decoding table is Error Pattern Syndrome 000000

000

100000 010000 001000 000100 000010 000001

110 011 101 100 010 001

Problem Set #8

Comment all 0’s 1st row of H

→− T →− T

2nd row of H

→− 3rd row of H 4th row of H 5th row of H

T

→− T →− T →−

6th row of H

T

page 5

ANU

ENGN 3226

(f) The syndrome for general received word is

→−s = →− r

0 1 1 1

→− 1

= T

H

2

r

r

3

4

r

5

r

r

6

r

1 1 0 0

1 0 0 1

1

0

0

0

0 1

=r 1 + r 3 + r 4 r1 + r2 + r5 r2 + r 3 + r6 The hardware syndrome generator implementation is

(6,3) Linear block code syndrome generators

r r1

r2

r3

r4

r5

r6

s 1

s2

s3

Figure 2: Figure for Question 1 (h).

(g) Given that c

1 1

1

0

0 0

is sent and r

→− =

s

=

0 0

1 is received.

→− = 1 1 0 0 1 1 r →− HT

=

1 1 1 0 0 1

→−

→−

1 1 1

1

0 1

0

0

=

0

1

1 0 0 0 0

1

0 1

From decoding table, this syndrome corresponds to error pattern

e

→−

000001 . Hence the corrected code =[ ]

word is →− y

= = =

Problem Set #8

→−+ →− r

e

1 1 1 0 0 0

1

1

1

0

0

1

+

0

0 0 0

0

1

page 6

ANU

ENGN 3226

Q2: Partial Solution (a) Testing for hamming code, we have m = n −k = 7 −4 = 3 m

3

k = 2 −m −1 = 2 −3 −1 = 4 m

3

n = 2 −1 = 2 −1 = 7 Hence (7, 4) is a Hamming code. We have →− G

→−

= →− [ k .

G

→−]

.

I

=

.P

1

0

0

0

1

1 0

0 0

1 0 0 1 →−

0 0

0 1

1 1 1 1

0

→−

.

=

→−

=

0

1

1

0

1

n −k ]

[→−

H

0

P

H

T

. .

I

1

0

1

1

1

0 0

1 0

1 1

1 1

0 1

0 0

1 0 0 1

(b) The encoding table for (7, 4) linear block code is Message 0000 0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100 1101 1110 1111

Code word 0000000 0001101 0010111 0011010 0100011 0101110 0110100 0111001 1000110 1001011 1010001 1011100 1100101 1101000 1110010 1111111

Weight of code word 0 3 4 3 3 4 3 4 3 4 3 4 4 3 4 7

(c) From encoding table, we have

=

d min

3

e = dmin −1 = 2 1 t ≤

2 ( d m ni −1)

≤1

Hence the (7, 4) linear block code can detect 2 bit errors and correct 1 bit error in 7 bit output codeword.

Problem Set #8

page 7

ANU

ENGN 3226

(d) The output for general code word is →− 1 2 c =m

3

=

→− →−

G

m

m

=m 1 m2

The hardware encoder

implementation is

m 1

m3

2

m

1

0

0 0

0

1

0 0

0

0

1

1

1 0

0

1 1

1

1

0 0 0 1 1 0

0

m3 m4 m1 + m 3 + m4

m4

c1

1

1

m1 + m2 + m3 m 2 + m3 + m 4

(7,4) Hamming code encoder

m

m

m

4

c 2

c c3

c4

c5

c6

c7

Figure 3: Figure for Question 2 (d).

(e) We have

HT

=

→−

1 1 0 0 1 1 1

1

0

1

1

1

100 010 0 The decoding table is Error Pattern 0000000 1000000 0100000 0010000 0001000 0000100 0000010 0000001 Problem Set #8

0 1

Syndrome 000 110 011 111 101 100 010 001 page 8

ANU

ENGN 3226

(f) The syndrome for general received word is

s =rH →−

T

=r1 r2 r3 r4

→−

r

5

r

6

0 1 1 1 0 0

r7

→−

1 1 0 1 1 0

1

=r 1 + r 3 + r 4 + r 5

+r

r 1 + r2 + r3

r2

r1

r 2 + r3 + r4

+ r7

(7,4) Hamming code syndrome generator

r4

r3

0

6

The hardware syndrome generator implementation is r

0

1 0 1 1 0 1

r5

r6

r7

s1

s

s 2

s3

Figure 4: Figure for Question 2 (h).

(g) Given that →− c s =rH →−

→−

= 1

T

0

0

1

0 1 1

→−

is sent and r 0 1

=1 1 0 1 0 1 1

→−

1 0 0 1

=

0

1

0

0 1

0 1 1 is received.

1 0 0 1 1 0 1 0

e0100000 . Hence the corrected code =[ ]

→−

→−

word is y

1 1 1 1 1 0

1

1

From decoding table, this syndrome corresponds to error pattern

→−

=1

= →− r + e = =

1 1

+

1 0 0 1 0 1 1

0

1

0

1

1

0

1 0

0 0

0

0

See also Lecture 19, Example 1.

Problem Set #8

page 9

ANU

ENGN 3226

Q3: Solution (a) →−

= →− . [ k

G

→−]

I

→−

.

=

.P

T.

G

1

→− H

=

1

. P .I

[ →−

n−k

]

1 1 1

→−

1 1 0 0 0 1 0 1 0 0

→− =

H

1

0

0

0

1

1

0

0

1

0

(b) The encoding table for (5, 1) linear block code is Message 0 1

Code word 00000 11111

Weight of code word 0 5

(c) From encoding table, we have

=

d min

5

e = dmin −1 = 4 1 t ≤

≤2

2 ( d m ni −1)

Hence the (5, 1) linear block code can detect 4 bit errors and correct 2 bit errors in 5 bit output codeword.

(d) The output for general code word is →− =→− →− = m 1 c mG 1 1 1 1 1 =

m1

m1

m1

m1

m1

The hardware encoder implementation is

m m1

(5,1) Linear block code encoder c1

c

c

c 2

3

c4

c5

Figure 5: Figure for Question 3 (d).

Problem Set #8

page 10

ANU

ENGN 3226

(e) We have

→−

=

1 1 1

1

1 0 0

0

0 H

1

0

0

T

0 0 1

0

0 0 0

1

The decoding table is Error Pattern Syndrome 00000 0000 10000 1111 01000 1000 00100 0100 00010 0010 00001 0001

(f) The syndrome for general received word is →−s = →− r

→− H

1

= r

T

=

2 r

3 r

4 r

5

1

1 1

1

0 0

r

r 1 + r 2 r 1 + r 3 r 1 + r4

1 0 0

1

0 0

0

0 1

0

0

0 0

1

r1 + r 5

The hardware syndrome generator implementation is (5,1) Linear block code syndrome generator

r r1

r2

r 3

r4

r5

s1

s s2

s

3

s4

Figure 6: Figure for Question 3 (h).

Problem Set #8

page 11

ANU

ENGN 3226

(g) Given that →− c

→−s = →− r

=

1

→−

1

1

1

1

→− = is sent and r 1 1

=

1 0 1 1 1 1

H

1 1 0 1 1

is received.

0 0

0

0

1 1

1

0

0

T

0 0 =

1

1 1

0 0

1 0 0 1 e1000 . Hence the corrected code word

1

From decoding table, this syndrome corresponds to error pattern

→−

=[

]

is →−+ →−

→− = y

r

e

=

0 1 1 1 1 +1 0 0 0 0

1 1 1 1 1

=

Q4: Complete Solution (a) Given that the generator polynomial for a (7,3) cyclic code is 4

3

2

g(p) = p + p + p + 1 The output code words are given by c(p) = M(p)g(p) Tabulating the results Input M(p) c(p) = M(p)g(p) 000 0 0 4 3 2 001 1 p +p +p +1 5 4 3 010 p p +p +p +p 5 2 011 p +p +p+1 p+1 6 5 4 3 100 p +p +p +p p2 2 6 5 3 p +1 101 p +p +p +1 2...