ENGN 3226 Digital Communications Problem Set #8 Block Codes
[Pages:13]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
001101
- (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 1 1 0 0 0 is sent and -r = 1 1 1 0 0 1 is received. Show how the code can correct this error.
Q2
Consider a (7,4) linear block code defined by the generator matrix
1 0 0 0 1 1 0
- G
=
0
0
1 0
0 1
0 0
0 1
1 1
1
1
0001101
- (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 how the code can correct this error.
Q3
Consider a (5,1) linear block code defined by the generator matrix - G = 11111
- (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. (g) Suppose -c = 1 1 1 1 1 is sent and -r = 0 1 1 1 1 is received. Show how the code can correct this error.
Problem Set #8
page 1
ANU
Q4
Consider the generator polynomial for a (7,3) cyclic code defined by g(p) = p4 + p3 + p2 + 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 g(p) = p3 + p2 + 1
(a) Find the encoding table for the cyclic code.
(b) (c)
What is Find the
tshyestmeminaimticumoudtpisuttacnocdeedwmoinrdoffothr eincpoudte-.c
=
1
1
1
1.
ENGN 3226
Problem Set #8
page 2
ANU
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 k = 2m - m - 1 = 23 - 3 - 1 = 4 = 3 n = 2m - 1 = 23 - 1 = 7 = 6
Hence (6, 3) is not a Hamming code.
We have
-
1 0 0 1 1 0
G = 0 1 0 0 1 1
001101
-P
=
1 0
1 1
0 1
101
-P T
=
1 1
0 1
1 0
011
-
1 0 1
I3 = 1 1 0
011
-H = [-P T ...-I n-k]
-H
=
1 1
0 1
1 0
1 0
0 1
0 0
011001
(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
Weight of code word 0 3 3 4 3 4 4 3
ENGN 3226
Problem Set #8
page 3
ANU
ENGN 3226
This is calculated as follows
-c 0 = -m 0-G =
1 0 0 1 1 0 0 0 0 0 1 0 0 1 1
001101
= -c 1 = -m 1-G =
= -c 2 = -m 2-G =
= -c 3 = -m 3-G =
= -c 4 = -m 4-G =
= -c 5 = -m 5-G =
= -c 6 = -m 6-G =
= -c 7 = -m 7-G =
=
000000
1 0 0 1 1 0
0 0 1 0 1 0 0 1 1
001101
001101
- (3rd row of G )
1 0 0 1 1 0
0 1 0 0 1 0 0 1 1
001101
010011
- (2nd row of G )
1 0 0 1 1 0
0 1 1 0 1 0 0 1 1
001101
011110
-
-
(2nd row of G + 3rd row of G )
1 0 0 1 1 0
1 0 0 0 1 0 0 1 1
001101
100110
- (1st row of G )
1 0 0 1 1 0
1 0 1 0 1 0 0 1 1
001101
101011
-
-
(1st row of G + 3rd row of G )
1 0 0 1 1 0
1 1 0 0 1 0 0 1 1
001101
110101
-
-
(1st row of G + 2nd row of G )
1 0 0 1 1 0
1 1 1 0 1 0 0 1 1
001101
111000
-
-
-
(1st row of G + 2nd row of G + 3rd row of G )
(c)
From encoding table, we have
dmin = 3 e = dmin - 1 = 2 1 t 2 (dmin - 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
(d)
The output for general code word is
-c = -m -G = =
1 0 0 1 1 0 m1 m2 m3 0 1 0 0 1 1
001101
m1 m2 m3 m1 + m3 m1 + m2 m2 + m3
The hardware encoder implementation is
ENGN 3226
m (6,3) Linear block code encoder
c
m1 m2 m3
c1 c2 c3 c4 c5 c6
Figure 1: Figure for Question 1 (d).
(e)
We have
-
1 0 1 1 0 0
H = 1 1 0 0 1 0
011001
1 1 0
0 1 1
-H T
=
1
1
0 0
1
0
0
1
0
001
The decoding table is Error Pattern Syndrome
000000
000
100000
110
010000
011
001000
101
000100
100
000010
010
000001
001
Comment all 0's
1st row of -H T 2nd row of -H T 3rd row of -H T 4th row of -H T 5th row of -H T 6th row of -H T
Problem Set #8
page 5
ANU
(f)
The syndrome for general received word is
-s = -r -H T = =
1 1 0
0 1 1
r1
r2
r3
r4
r5
r6
1
1
0 0
1
0
0
1
0
001
r1 + r3 + r4 r1 + r2 + r5 r2 + r3 + r6
The hardware syndrome generator implementation is
ENGN 3226
r
(6,3) Linear block code syndrome generator s
r1 r2 r3 r4 r5 r6
s1 s2 s3
Figure 2: Figure for Question 1 (h).
(g)
Given that -c = 1 1 1 0 0 0 is sent and -r = 1 1 1 0 0 1 is received.
1 1 0
0 1 1
-s
=
-r -H T =
1
1
1
0
0
1
1
1
0 0
1
0
0
1
0
001
= 001
From decoding table, this syndrome corresponds to error pattern -e = [000001]. Hence the corrected code word is
-y = -r + -e
= 111001+000001
= 111000
Problem Set #8
page 6
ANU
Q2: Partial Solution
(a)
Testing for hamming code, we have
m = n-k =7-4=3 k = 2m - m - 1 = 23 - 3 - 1 = 4 n = 2m - 1 = 23 - 1 = 7
Hence (7, 4) is a Hamming code.
We have
- G
=
[-I k...-P ]
1 0 0 0 1 1 0
- G
=
0
0
1 0
0 1
0 0
0 1
1 1
1
1
0001101
-H = [-P T ...-I n-k]
-H
=
1 1
0 1
1 1
1 0
1 0
0 1
0 0
0111001
ENGN 3226
(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
dmin = 3 e = dmin - 1 = 2 1 t 2 (dmin - 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 -c = -m -G = m1 m2 m3 m4
= m1 m2 m3 m4 The hardware encoder implementation is
1 0 0 0 1 1 0
0 1 0 0 0 1 1
0
0
1
0
1
1
1
0001101
m1 + m3 + m4 m1 + m2 + m3
m2 + m3 + m4
m
(7,4) Hamming code encoder c
m1 m2 m3 m4
c1 c2 c3 c4 c5 c6 c7
Figure 3: Figure for Question 2 (d).
(e)
We have
1 1 0
0 1 1
-H T
=
1
1
1 0
1
1
1
0
0
0
1
0
001
The decoding table is
Error Pattern Syndrome
0000000
000
1000000
110
0100000
011
0010000
111
0001000
101
0000100
100
0000010
010
0000001
001
Problem Set #8
page 8
................
................
In order to avoid copyright disputes, this page is only a partial summary.
To fulfill the demand for quickly locating and searching documents.
It is intelligent file search solution for home and business.
Related download
- attach to form 1040 1040 sr 1040 nr 1040 ss or 1041
- peace of mind extended service plan terms h r block
- basic stress equations fairfield university
- midterm exam solutions
- amazon refund bonus h r block
- engn 3226 digital communications problem set 8 block codes
- h r 1096 vs h r 1644 stanford university
- 2 phonetics and phonology 2 1 sounds of english phonetics
- chapter 14 problem 1 howard r hughes college of
- physics 111 homework solution 5