Problem Sheet - 3

SCHOOL OF ELECTRONICS ENGINEERING (SENSE)
BECE313L: Information Theory and Coding
PROBLEM SHEET-3
Channel Coding
Instructions:
1. Total Marks: 15
2. Weightage of marks in grades : 4%
3. Last Date for Submission: 15.11.2024
4. All answers must be handwritten
5. Late submission are not allowed
6. Submission must be through teams
Address each problem with thorough analysis and detailed solutions.
Q.No Question Marks

1 Obtain all possible code vectors for a (7, 4) linear block code (LBC) in its 1
systematic form for the generator matrix:
 
1 1 0 0 0 1 1
0 1 0 0 1 0 1
G=
 

1 0 1 0 1 0 1
0 0 0 1 1 1 1
2 Given a systematic (8, 4) LBC with parity check equations: 1
v4 = u1 + u2 + u3
v5 = u0 + u1 + u2
v6 = u0 + u1 + u3
v7 = u0 + u2 + u3
Write the generator and parity check matrices and draw the encoder diagram.
3 A systematic (10, 5) LBC is designed with a minimum Hamming distance of 2
4. The generator matrix is:
 
1 0 0 0 0 1 1 1 0 1
0 1 0 0 0 0 1 1 1 0
 
 
G= 0 0 1 0 0 1 0 1 1 1
0 0 0 1 0 1 1 0 1 0
 
0 0 0 0 1 0 1 1 0 1
1. Verify if the minimum Hamming distance criterion is satisfied by finding

all codewords and computing their Hamming weights.
2. Construct the corresponding parity check matrix H.
3. Analyze the error detection and correction capabilities of this code based
on the minimum Hamming distance.
4. Design the encoder circuit for this code.
4 Consider a (7, 4) cyclic code with generator polynomial g(x) = 1 + x + x3 . 1

Given two input sequences u1 = 1101 and u2 = 0110, perform the following
tasks:
1. Derive the code polynomial for both input sequences using polynomial
multiplication.
2. Construct the full code vector for each input by using the generator poly-
nomial.
3. If the received vector is r(x) = x + x2 + x5 + x6 , compute the syndrome

and determine if any error is detected.
4. Correct the received vector if an error is detected and identify the error
location.
5 A (15, 7) cyclic code is defined by the generator polynomial g(x) = 1 + x + 2
x4 . The code is used in a communication system where the following received
vectors are obtained:
r1 (x) = x3 + x6 + x9 + x12 + x14
r2 (x) = 1 + x + x2 + x7 + x11 + x14
1. For each received vector, calculate the syndrome and determine if there
is any error.
2. Explain the steps required to correct the received vectors if an error exists.
3. Determine the error detection and correction capabilities of the code

based on the properties of the generator polynomial.
4. Explain how this cyclic code could be converted into a systematic form,
if possible, and discuss the implications on encoding complexity.
6 Given
 a (6, 3) linear block code with generator matrix G = 1
1 0 0 1 0 1
0 1 0 1 1 0:
 
0 0 1 0 1 1
1. Construct the entire set of codewords and verify the minimum Hamming
distance.
2. Design the encoder circuit for this code using basic logic gates.
3. If the received vector is r = [1, 0, 1, 1, 0, 1], use syndrome decoding to

check for errors. If an error exists, identify the corrected codeword.
4. Discuss the theoretical maximum error detection and correction capabil-

ities of this code.
7 Consider a (9, 5) systematic block code designed to detect and correct single-bit 2
errors. The parity check matrix for this code is:
 
1 0 1 0 1 0 1 0 1
0 1 1 0 0 1 1 0 0
H=
 

1 1 0 1 0 1 0 1 0
0 0 1 1 1 1 1 0 1
1. Construct the generator matrix G for this systematic code.
2. Using the syndrome decoding approach, analyze how this code detects
and corrects single-bit errors.
3. If a received vector r = [1, 0, 1, 0, 1, 1, 0, 1, 0] is detected, compute the

syndrome and determine if there is an error.
4. Draw the encoder and syndrome decoder circuit diagrams for this code.
5. Provide an analysis on how the minimum Hamming distance impacts the

error detection and correction capabilities for this code.
8 For the following (6, 3) systematic LBC with generator matrix: 1

 
1 0 0 1 0 1
G = 0 1 0 0 1 1
 
0 0 1 0 1 0
1. Find all code vectors.
2. Draw the encoder circuit for the above code.
3. Find the minimum Hamming weight.
4. Find the error detection and correction capabilities.
9 In an LBC, the syndrome is given by: 1
S1 = r1 + r2 + r3 + r4
S2 = r1 + r2 + r4 + r6
S3 = r1 + r3 + r4 + r7
1. Find the parity check matrix.
2. Draw the encoder circuit.
3. Find the codeword for all input sequences.
4. How many errors can it detect and correct?
5. What is the syndrome for the received data 1011011?

10 Consider a (7, 4) cyclic code with g(x) = 1+x+x3 . Obtain the code polynomial 1
in non-systematic form for the input sequences 1010 and 1100.
11 For a (7, 4) cyclic code with generator polynomial g(x) = 1 + x + x3 , obtain 1
the syndrome for the received vector r(x) = 1 + x2 + x3 + x4 + x5 .
12 Given n ≤ 7, identify the (n, k) values of cyclic codes generated by the following 1
generator polynomials:
1. g(x) = 1 + x2 + x3
2. g(x) = 1 + x + x2 + x4
3. g(x) = 1 + x + x2 + x3 + x4

Problem Sheet - 3

Uploaded by

Copyright:

Available Formats

Problem Sheet - 3

Uploaded by

Document Information

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Problem Sheet - 3

Uploaded by

Copyright:

Available Formats

SCHOOL OF ELECTRONICS ENGINEERING (SENSE)

BECE313L: Information Theory and Coding

2. Weightage of marks in grades : 4%

3. Last Date for Submission: 15.11.2024

4. All answers must be handwritten

5. Late submission are not allowed

6. Submission must be through teams

Address each problem with thorough analysis and detailed solutions.

Q.No Question Marks

2 Given a systematic (8, 4) LBC with parity check equations: 1

1. Verify if the minimum Hamming distance criterion is satisfied by finding

2. Construct the corresponding parity check matrix H.

4. Design the encoder circuit for this code.

4 Consider a (7, 4) cyclic code with generator polynomial g(x) = 1 + x + x3 . 1

3. If the received vector is r(x) = x + x2 + x5 + x6 , compute the syndrome

r1 (x) = x3 + x6 + x9 + x12 + x14

r2 (x) = 1 + x + x2 + x7 + x11 + x14

3. Determine the error detection and correction capabilities of the code

3. If the received vector is r = [1, 0, 1, 1, 0, 1], use syndrome decoding to

4. Discuss the theoretical maximum error detection and correction capabil-

1. Construct the generator matrix G for this systematic code.

3. If a received vector r = [1, 0, 1, 0, 1, 1, 0, 1, 0] is detected, compute the

5. Provide an analysis on how the minimum Hamming distance impacts the

8 For the following (6, 3) systematic LBC with generator matrix: 1

1. Find all code vectors.

2. Draw the encoder circuit for the above code.

3. Find the minimum Hamming weight.

4. Find the error detection and correction capabilities.

9 In an LBC, the syndrome is given by: 1

1. Find the parity check matrix.

2. Draw the encoder circuit.

3. Find the codeword for all input sequences.

4. How many errors can it detect and correct?

5. What is the syndrome for the received data 1011011?

You might also like