Error-Control Coding — Convolutional Encoding and Viterbi Decoding: 22-Elec-B3 Digital Communications Systems, May 2018, Q3

Question 3: Error-Control Coding — Convolutional Encoding and Viterbi Decoding (25 marks)

Question text not reproduced: the examination questions are © Engineers and Geoscientists BC. Open the official past paper (linked at the top of this page) to read the question, then follow the worked solution below.

Given. A rate-1/2 convolutional encoder with generator polynomials $g_1(D) = 1+D^2$ and $g_2(D) = 1+D+D^2$, output pair ordered $(g_1, g_2)$. Memory $m = 2$, so the constraint length is $K = 3$ and the encoder has $2^2 = 4$ states. Part (a) input: 10101, starting in the all-zero state, zero-padded. Part (b) received sequence: 00111110000111 (14 bits = 7 branches), with the encoder known to start and end in the all-zero state.

Find. (a) the 14-bit encoded output for the input 10101; (b) the maximum-likelihood input sequence for the observed 14 bits, together with any corrected errors.

Figure 3.1 — The encoder implied by the generator polynomials. $D$ denotes a one-bit delay, so the two shift-register cells hold $u(k-1)$ and $u(k-2)$; the state is the pair $(u(k-1), u(k-2))$. The upper modulo-2 adder implements $g_1 = 1 + D^2$ and the lower one $g_2 = 1 + D + D^2$.

Approach. Write the two output bits as modulo-2 sums of the current input and the two register contents, run the register through the input sequence for part (a), and for part (b) run a full Viterbi search over the four-state trellis with the terminating branches forced to input 0.

Part (a) — Write the output equations from the generator polynomials. Reading the polynomials as taps on the delay line, $$g_1: \quad v^{(1)}_k = u_k \oplus u_{k-2}, \qquad\qquad g_2: \quad v^{(2)}_k = u_k \oplus u_{k-1} \oplus u_{k-2},$$ where $\oplus$ is addition modulo 2 and the state before clocking bit $k$ is $(u_{k-1}, u_{k-2})$.

Clock the register through the zero-padded input. Zero padding means $m = 2$ tail zeros are appended to flush the register, so the encoder is driven with 1010100 and returns to the all-zero state. Working step by step:

$k$	$u_k$	State before $(u_{k-1},u_{k-2})$	$v^{(1)} = u_k\oplus u_{k-2}$	$v^{(2)} = u_k\oplus u_{k-1}\oplus u_{k-2}$	Output	State after
1	1	00	1	1	11	10
2	0	10	0	1	01	01
3	1	01	0	0	00	10
4	0	10	0	1	01	01
5	1	01	0	0	00	10
6	0 (pad)	10	0	1	01	01
7	0 (pad)	01	1	1	11	00

Concatenating the output column, $$\boxed{\text{encoded output} = 11\ 01\ 00\ 01\ 00\ 01\ 11 = 11010001000111}$$ Seven input bits produce fourteen output bits, confirming the rate of 1/2, and the final state is 00 as the padding requires.

Part (b) — Set up the trellis and the branch metrics. The receiver sees hard-decision bits, so the maximum-likelihood path is the one whose transmitted sequence is closest in Hamming distance to the observation. Split the received sequence into seven branch pairs: $$r = \underbrace{00}_{t=1}\ \underbrace{11}_{t=2}\ \underbrace{11}_{t=3}\ \underbrace{10}_{t=4}\ \underbrace{00}_{t=5}\ \underbrace{01}_{t=6}\ \underbrace{11}_{t=7}$$ The trellis has four states $S_0 = 00$, $S_1 = 01$, $S_2 = 10$, $S_3 = 11$ (again $(u_{k-1},u_{k-2})$). It starts in $S_0$ with metric 0 and all other states unreachable; because the encoder is known to end in the all-zero state, the last two branches ($t = 6, 7$) are restricted to input 0.

Run the add–compare–select recursion. At each stage every surviving state extends along its two outgoing branches, the branch Hamming distance is added to the incoming path metric, and at each new state only the smaller total survives. The table records the surviving path metric at each state after each branch, with the survivor's input history beneath it (“—” means unreachable):

Stage	Received	$S_0 = 00$	$S_1 = 01$	$S_2 = 10$	$S_3 = 11$
$t=0$	—	0	—	—	—
$t=1$	00	0 (0)	—	2 (1)	—
$t=2$	11	2 (00)	3 (10)	0 (01)	3 (11)
$t=3$	11	3 (100)	1 (010)	2 (001)	1 (011)
$t=4$	10	2 (0100)	1 (0110)	2 (0101)	2 (0011)
$t=5$	00	2 (01000)	3 (01010)	1 (01101)	3 (01011)
$t=6$	01	3 (010000)	1 (011010)	—	—
$t=7$	11	1 (0110100)	—	—	—

At $t = 6$ and $t = 7$ only input-0 branches are permitted, which is why states $S_2$ and $S_3$ fall away and the trellis funnels back to $S_0$.

Trace back the survivor. The single surviving path into $S_0$ at $t = 7$ carries a total Hamming metric of 1, and its state trajectory is $$S_0 \to S_0 \to S_2 \to S_3 \to S_1 \to S_2 \to S_1 \to S_0.$$

Figure 3.2 — The Viterbi trellis for the seven received branch pairs. Thin grey lines are the candidate transitions explored; the bold path is the survivor. Its branch labels are the bits the encoder would have transmitted, and they differ from the received sequence in exactly one place.
Read off the decoded input and the corrected sequence. The survivor's input history is 0110100, of which the last two bits are the known terminating zeros, so the transmitted message was $$\boxed{\hat{u} = 01101}$$ Re-encoding that message confirms the decision: the encoder driven with 0110100 emits $$\hat{v} = 00\ 11\ 10\ 10\ 00\ 01\ 11 = 00111010000111,$$ against the received $00111\underline{1}10000111$. The two differ in one bit only, at position 6, which the decoder has therefore corrected from 1 back to 0.
Confirm that the decision is unambiguous. The survivor's metric is 1, while the next-best terminated path (message 00101, 01001 or 11101) is at Hamming distance 4. The margin is three, so no plausible tie exists and the decoding is decisive. This is the expected behaviour: the free distance of this classic $(2,1,3)$ code with generators $(5,7)$ in octal is $d_{free} = 5$, so any single error inside the span is guaranteed correctable, since $t = \lfloor (d_{free}-1)/2 \rfloor = 2$.

Result	Value
(a) Zero-padded input driven into the encoder	1010100 (message 10101 plus two tail zeros)
(a) Encoded output	11 01 00 01 00 01 11 = 11010001000111
(b) Received sequence	00111110000111
(b) Surviving path metric (Hamming)	1 (next-best terminated path: 4)
(b) Most likely transmitted code sequence	00111010000111
(b) Most likely input (decoded message)	01101
(b) Error corrected	one bit, at received position 6 (1 → 0)

Topic. Rate-1/2 convolutional encoding and maximum-likelihood sequence decoding by the Viterbi algorithm.

Key relations. Output taps $v^{(j)}_k = \bigoplus_i g^{(j)}_i u_{k-i}$; state $= (u_{k-1},\dots,u_{k-m})$ with $2^m$ states and constraint length $K = m+1$; hard-decision branch metric $=$ Hamming distance between the received and hypothesised branch pairs; add–compare–select $\Gamma_{new}(s') = \min_{s} \left[\Gamma(s) + d_H(r, v(s\to s'))\right]$; correction capability $t = \lfloor (d_{free}-1)/2\rfloor$, with $d_{free} = 5$ for the $(5,7)_8$ code used here.

Why this works. A convolutional code has no block boundary, so decoding cannot be done symbol by symbol — the maximum-likelihood answer is the single path through the trellis whose output sequence is closest to what was received. Enumerating all paths is exponential in the message length, but the encoder is a finite-state machine, and that is the whole leverage: any two paths arriving at the same state at the same time have identical futures, so the one with the larger accumulated distance can never win and may be discarded immediately. That single observation reduces the search from $2^L$ paths to $2^m$ survivors per stage, which is why Viterbi decoding is linear in message length rather than exponential. Terminating the encoder in the all-zero state costs $m$ tail bits of rate but is what allows the traceback to start from a known state instead of guessing the best final state.

Common pitfall. Reversing the output order — the question explicitly says $g_1$ first, and swapping them produces a valid but different code and a wrong answer to both parts. Two more: forgetting the tail bits, so the encoded sequence is 10 bits instead of 14 and the trellis is never forced back to $S_0$; and allowing input-1 branches on the last $m$ stages of the trellis, which lets the decoder finish in the wrong state and can select a path that no terminated encoder could have produced.

Source. B. Sklar, Digital Communications: Fundamentals and Applications, 2nd ed., Ch. 7 (Channel coding: convolutional codes and the Viterbi algorithm); B. P. Lathi and Z. Ding, Modern Digital and Analog Communication Systems, 4th ed., §16.4.

Question 3 of 5: Error-Control Coding — Convolutional Encoding and Viterbi Decoding

Question 3: Error-Control Coding — Convolutional Encoding and Viterbi Decoding (25 marks)