EC3003E Communication Engineering-II
Part-A
Problem Sheet-5
Dr. Nujoom Sageer Karat
14-11-2025
Based on Lec-21, 22 and 23
Table 1: Irreducible polynomials over F2 , degrees 1–6.
Degree Irreducible polynomials over F2
1 x, x + 1
2 x2 + x + 1
3 x3 + x + 1, x3 + x2 + 1
4 x4 + x + 1, x4 + x3 + 1, x4 + x3 + x2 + x + 1
5 x5 + x2 + 1, x5 + x3 + 1, x5 + x3 + x2 + x + 1,
x5 + x4 + x2 + x + 1, x5 + x4 + x3 + x + 1, x5 + x4 + x3 + x2 + 1
6 x6 + x + 1, x6 + x3 + 1, x6 + x4 + x2 + x + 1,
x6 + x4 + x3 + x + 1, x6 + x5 + 1, x6 + x5 + x2 + x + 1,
x6 + x5 + x3 + x2 + 1, x6 + x5 + x4 + x + 1, x6 + x5 + x4 + x2 + 1
1. (Topic: Generator Polynomial) Check whether the following are valid generator poly-
nomials of cyclic code of length 15. Give reason.
(a) g(x) = x4 + x + 1.
(b) g(x) = x5 + x + 1.
(c) g(x) = x8 + x7 + x5 + x4 + x3 + x + 1.
(d) g(x) = x6 + x3 + x2 + x + 1.
2. (Topic: Polynomial factorization)
(a) Factorize (x4 − x) to irreducible polynomials with binary coefficients.
1
(b) Factorize (x31 − 1) to irreducible polynomials with binary coefficients.
3. (Topic: Number of cyclic codes) Give the number of possible distinct cyclic codes of
length:
(a) 15
(b) 31
(c) 63
4. (Topic: Generator polynomial and check polynomial) Consider the n = 7 binary cyclic
code with generator polynomial g(x) = 1 + x + x3 .
(a) Find all codewords of the code.
(b) Give a generator matrix for the code.
(c) Give the check polynomial for the code.
(d) Systematically encode the message [1011].
5. (Topic: Choosing generator polynomial) Choose an appropriate generator polynomial
for a length 31 cyclic Hamming code.
6. (Topic: Check Polynomial) A binary cyclic code of length 15 has generator polynomial
g(x) = (x4 + x + 1)(x4 + x3 + x2 + x + 1).
(a) Find the dimension of the code.
(b) Give a check polynomial for this code. What will be the dimension of the dual
code?
7. (Topic: Dimension of cyclic code) Find the dimension and generator polynomial for
every binary cyclic code of length 15 and 31.
8. (Topic: Cyclic subcodes) Let two length-n cyclic codes C1 and C2 be generated by
g1 (x) and g2 (x) respectively. Show that C1 ⊆ C2 iff g1 (x) is a factor of g2 (x).
9. (Topic: Generator Polynomial) Let g(x) be the generator polynomial of a binary cyclic
code of length n.
(a) Show that if (x+1) is a factor of g(x), the code contains no odd-weight codewords.
(b) If n is odd and (x + 1) is not a factor of g(x), show that the code contains the
all-1s codeword.
10. (Topic: Convolutional Encoder) Consider a convolutional encoder shown in Figure 1:
(a) Find the rate and memory order of this encoder.
(b) Give the impulse responses (generator sequences) and their polynomial represen-
tations.
2
Figure 1: Convolutional Encoder for Question 10
(c) Express the l-th output bits in terms of input.
(d) Find the codeword polynomial corresponding to the information sequence m(D) =
1 + D2 + D3 + D4 .
(e) Give a state diagram for this encoder. How many states are possible?
(f) Is this a systematic encoder? Convert this to a systematic encoder with the same
rate. Is the resulting encoder recursive?
11. (Topic: Convolutional Encoder) Consider the (3, 1, 2) nonsystematic encoder with
g (0) = (1 1 0), g (1) = (1 0 1), g (2) = (1 1 1).
(a) Draw the encoder block diagram.
(b) Find the time-domain generator matrix G.
(c) Find the codeword c corresponding to the information sequence m = (1 1 1 0 1).
(d) Find the transform-domain generator matrix G(D).
(e) Find the set of output sequences and the codeword corresponding to the informa-
tion sequence m(D) = 1 + D2 + D3 + D4 .
12. (Topic: Trellis Diagram) Consider a convolutional code with the generator matrix
G(D) = [1 + D3 , 1 + D + D2 + D3 ].
(a) Draw the circuit of this encoder.
(b) Draw three stages of the trellis for the encoder.
13. (Topic: Viterbi Decoding) Consider the encoder in Figure 2.
(a) Encode the infinite message sequence m = (111 . . .) (all 1s).
(b) Do a Viterbi-hard decision decoding for the received sequence 00101010101000111.
3
Figure 2: Encoder for Question 3
(c) How many survivor paths would exist after each stage? Give the codeword cor-
responding to each of them.
14. (Topic: Viterbi Decoder) Consider a binary convolutional encoder of rate 1/3 whose
generator polynomials (in D-domain) are
g (0) (D) = 1 + D + D2 + D3 , g (1) (D) = 1 + D2 + D3 , g (2) (D) = 1 + D + D3 .
(a) Draw the state diagram for this encoder and clearly label the output triples on
each branch.
(b) (Hard-decision Viterbi) You receive the following hard-decided codeword (grouped
as output triples):
110 |{z}
|{z} 001 |{z}
011 |{z}
100 |{z}
111 |{z}
010 .
t=1 t=2 t=3 t=4 t=5 t=6
Using the Viterbi algorithm with Hamming-distance branch metric, decode this
received sequence. Show the survivor paths.
(c) (Soft-decision Viterbi) Assume binary phase-shift keying (BPSK) mapping 0 7→
+1, 1 7→ −1. For the same trellis length, use the following soft samples (one real
number per coded bit, time ordered, total 6 × 3 = 18 samples):
− 0.7, 0.8, 0.1, 0.9, −0.8, 0.6, −0.4, −0.9, 0.2, 0.95, 0.1, −0.6,
0.85, −0.7, −0.9, 0.2, −0.1, 0.9.
Using the Viterbi algorithm with Euclidean (soft) branch metric, decode these
soft observations and give the survivor paths.
15. (Soft-in Soft-out Decoder) Consider a (3, 1) binary repetition code (each information
bit u is repeated three times). BPSK mapping is used with 0 7→ +1, 1 7→ −1, and
the channel is AWGN with noise variance σ 2 = 1. A codeword corresponding to some
information bit was transmitted and the three channel outputs are
y1 = 0.9, y2 = 0.5, y3 = −0.2.
2y
The channel (intrinsic) LLR for a received sample y is given by Lch = .
σ2
4
(a) Compute the intrinsic (channel) LLRs Lch,1 , Lch,2 , Lch,3 .
(b) For the first replica (associated with y1 ) compute the extrinsic LLR L(1)
e produced
by a repetition decoder (i.e. the information coming from the other two replicas).
(c) Compute the total LLR L(1) for the first replica.
16. (Min-Sum Belief Propagation Algorithm) Consider the binary linear code of length
n = 6 defined by the parity-check matrix
1 1 0 1 0 0
H = 0 1 1 0 1 0 ,
1 0 1 0 0 1
so there are m = 3 check nodes. The code is used over an AWGN channel with BPSK
mapping (0 7→ +1, 1 7→ −1). The receiver computes the intrinsic log-likelihood ratios
(LLRs) for the six variable nodes as
Lch = 2.2, −1.5, 0.9, −0.7, 1.1, −0.8 ,
where a positive LLR favors bit 0 and a negative LLR favors bit 1.
Using the min-sum approximation algorithm do the following:
(a) Write down the Tanner graph (list neighbors of each variable node and check
node) implied by H.
(b) Initialize the variable-to-check messages m(0) (0)
v→c using the channel LLRs (i.e. mv→c =
Lch
v for every edge).
(c) Perform message-passing iterations (check→variable updates using min-sum, vari-
able→check updates by summing incoming messages excluding the target check,
and posterior LLR updates by summing channel LLR and incoming check→variable
messages).
(d) At the end of each iteration t = 1, 2, . . . compute the posterior LLRs L̃(t)
v and
(t) (t) (t)T
the hard decisions x̂v = 1{L̃v < 0}, and check whether H x̂ = 0 (all parity
checks satisfied).
(e) Show all intermediate messages (variable→check and check→variable) and pos-
terior LLRs for iterations t = 1 and t = 2. Continue iterating until the decoder
converges or until a maximum of 10 iterations is reached.
Stopping rule: stop when all parity checks are satisfied (i.e. H x̂(t)T = 0) or after 10
iterations.
17. (Topic: Belief-propagation decoding)
5
Consider the following parity-check matrix:
0 1 0 1 1 0 0 1
1 1 1 0 0 1 0 0
H= 0
.
0 1 0 0 1 1 1
1 0 0 1 1 0 1 0
(a) Draw the Tanner graph corresponding to this matrix and determine its girth.
(b) The code is transmitted over a binary symmetric channel (BSC). The receiver
makes a hard decision using the rule:
(
0, if received symbol is closer to + 1,
r̂i =
1, if received symbol is closer to − 1.
(Equivalently: map received +1 to bit 0 and received −1 to bit 1.)
Assume the resulting hard-decision vector is
r = [ 1 0 1 1 0 1 0 1 ].
Using the belief-propagation (sum–product) algorithm on the Tanner graph, de-
code the received vector. In your solution, clearly show the following message-
passing steps:
(a) Initialization: For every edge (vi , cj ) in the Tanner graph, initialize the
variable-to-check message
m(0)
vi →cj = r̂i
(since decoding is hard-decision based, treat the message as the bit estimate
itself).
(b) Check-node update (at iteration t): For each check node cj and each
connected variable node vi , compute
m(t)
cj →vi
using the parity constraint: the message sent to vi is the XOR of all incoming
bits from the *other* variable nodes connected to cj .
(c) Variable-node update (at iteration t): For each variable node vi and
each check node cj connected to it, compute
m(t)
vi →cj
by taking the majority vote among:
r̂i and all incoming messages m(t)
ck →vi from check nodes ck ̸= cj .
6
(d) Posterior estimate (after iteration t): For each variable node vi , form
the tentative decoded bit
(t) (t) (t)
x̂i = majority r̂i , mcj1 →vi , mcj2 →vi , . . . .
(e) Stopping criterion: Stop when
H x̂(t)T = 0 (all parity checks satisfied),
or when you reach 10 iterations.
Finally, report the decoded vector after the algorithm stops.