Scribd
Upload
3 views4 pages

4c7 Tutorial1 Solutions

The document provides solutions to various problems related to digital communications and coding theory, specifically focusing on systematic block codes, generator matrices, and error correction capabilities. It includes calculations for parameters, minimum Hamming distance, validity of codewords, and construction of parity check matrices. Additionally, it discusses syndrome tables and orthogonality of codewords with respect to parity check matrices.

Uploaded by

Umarr A Sesay
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
3 views4 pages

4c7 Tutorial1 Solutions

The document provides solutions to various problems related to digital communications and coding theory, specifically focusing on systematic block codes, generator matrices, and error correction capabilities. It includes calculations for parameters, minimum Hamming distance, validity of codewords, and construction of parity check matrices. Additionally, it discusses syndrome tables and orthogonality of codewords with respect to parity check matrices.

Uploaded by

Umarr A Sesay
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 4

4C7 – Digital Communications – Tutorial 1 Solutions

1. Consider a systematic block code whose parity check equations are:


= + +
= + +
= + +
= + +

where mi are the message bits, i = 0, 1, 2, 3, and bi are the check bits, i = 0, 1, 2, 3.

(a) What are the parameters n and k? Find the generator matrix for the code.
(b) What is the minimum Hamming distance? How many errors can the code correct?
(c) Is the vector [1 0 1 0 1 0 1 0] a valid codeword?
(d) Is the vector [0 1 0 1 1 1 0 0] a valid codeword?

Solutions:

(a) n = 8, k = 4
⎛1 1 1 0 1 0 0 0⎞
⎜ ⎟
⎜1 0 1 1 0 1 0 0⎟
G =⎜
0 1 1 1 0 0 1 0⎟
⎜ ⎟
⎜1 1 0 1 0 0 0 1 ⎟⎠
⎝

Note: I assumed that the parity bits come at the beginning of the codeword. It would also have
been fine to swap the matrices I and P, making the parity bits come at the end of the codeword.

(b) All possible messages and corresponding codewords are tabulated below:

m c m c
0000 00000000 1000 11101000
0001 11010001 1001 00111001
0010 01110010 1010 10011010
0011 10100011 1011 01001011
0100 10110100 1100 01011100
0101 01100101 1101 10001101
0110 11000110 1110 00101110
0111 00010111 1111 11111111

dmin = 4, so we can correct all single errors.


⎛1 0 0 0⎞
⎜ ⎟
⎜0 1 0 0⎟
⎛1 0 0 0 1 1 0 1⎞ ⎜0 0 1 0⎟
⎜ ⎟ ⎜ ⎟
⎜0 1 0 0 1 0 1 1⎟ ⎜0 0 0 1⎟
(c) H = ⎜ , and H T = ⎜
1 1 0 ⎟⎟
⎟ .
0 0 1 0 1 1 1 0 ⎜1
⎜ ⎟
⎜0 1 1 ⎟⎠ ⎜1 0 1 1⎟
⎝ 0 0 1 0 1
⎜ ⎟
⎜0 1 1 1⎟
⎜1 1 0 1 ⎟⎠
⎝
(1 0 1 0 1 0 1 0 )H T = (0 0 1 1) , so not a codeword.

(d) (0 1 0 1 1 1 0 0 )H T = (0 0 0 0 ) , so a valid codeword.

2. Consider a (7,4) linear block code whose generator matrix is:

⎛1 1 1 1 0 0 0⎞
⎜ ⎟
⎜1 0 1 0 1 0 0⎟
G =⎜
0 1 1 0 0 1 0⎟
⎜ ⎟
⎜1 1 0 0 0 0 1 ⎟⎠ .
⎝

(a) Find all the valid codewords.


(b) Find H, the parity check matrix of the code.
(c) Compute the syndrome for the received vector [1 1 0 1 1 0 1]. Is this a valid codeword?
(d) What is the error correcting capability of the code?
(e) What is the error detecting capability of the code?

Solutions:

(a) All messages and corresponding codewords are listed below:

m c m c
0000 0000000 1000 1111000
0001 1100001 1001 0011001
0010 0110010 1010 1001010
0011 1010011 1011 0101011
0100 1010100 1100 0101100
0101 0110101 1101 1001101
0110 1100110 1110 0011110
0111 0000111 1111 1111111
⎛1 0 0 1 1 0 1⎞
⎜ ⎟
(b) H = ⎜ 0 1 0 1 0 1 1 ⎟
⎜0 0 1 1 1 1 0⎟
⎝ ⎠

(c) s = (1 1 0 1 1 0 1)H T = (0 1 0 ) , so not a codeword.

(d) dmin = 3, so can correct all single errors.

(e) Can detect all single and double errors.

3. The generator matrix for a linear binary code is


⎛0 0 1 1 1 0 1⎞
⎜ ⎟
G = ⎜0 1 0 0 1 1 1⎟ .
⎜1 0 0 1 1 1 0⎟
⎝ ⎠
(a) Express G in systematic [P | I] form.
(b) Determine the parity check matrix H for the code.
(c) Construct the table of syndromes for the code.
(d) Determine the minimum distance for the code.
(e) Demonstrate that the codeword corresponding to information sequence 101 is orthogonal
to H.

Solutions:

⎛1 0 1 1 1 0 0⎞
⎜ ⎟
(a) G = ⎜ 1 1 1 0 0 1 0 ⎟ , by swapping columns 1 and 7, columns 2 and 6, and columns 3
⎜0 1 1 1 0 0 1⎟
⎝ ⎠
and 5.

⎛1 0 0 0 1 1 0⎞
⎜ ⎟
⎜0 1 0 0 0 1 1⎟
(b) H = ⎜
0 0 1 0 1 1 1⎟
⎜ ⎟
⎜0 0 0 1 1 0 1 ⎟⎠
⎝

(c) The syndrome table is below:

Syndrome Coset leader Syndrome Coset leader


0000 0000000 1000 1000000
0001 0001000 1001 1001000,
0010100,
0000011
0010 0010000 1010 1010000,
0100010,
0001100
0011 1000100, 1011 0000100
0100001,
0011000
0100 0100000 1100 1100000,
0010010,
0000101
0101 0101000, 1101 1101000,
0010001, 0110100, etc.
0000110
0110 1000010, 1110 0000010
0110000,
0001001
0111 0000001 1111 1000001,
0100100,
0001010

(d) dmin = 4.

(e) m = (1 0 1) , c = mG = (1 1 0 0 1 0 1) , cH T = (0 0 0 0 ) , so orthogonal.

You might also like