Convolutional Encoding and Viterbi Decoding: 22-Elec-B3 Digital Communications Systems, December 2019, Q1

Question 1: 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$, constraint-length $K = 3$ (memory $m = 2$) binary convolutional encoder with

$$g_1(D) = 1 + D^2, \qquad g_2(D) = 1 + D + D^2,$$

outputs interleaved as $v_1 v_2$ per input bit. Part (a): message $\mathbf{u} = 11010$, initial state all-zero, two zero-padding (flush) bits. Part (b): the same encoder, received word $\mathbf{r} = 00111110000111$ (14 bits $=$ 7 branches), encoder terminated in the all-zero state.

Find. (a) The 14-bit encoded output for the message 11010; (b) the maximum-likelihood transmitted message and the position of any bit error, obtained by Viterbi decoding of $\mathbf{r}$.

Figure 1.1 — Shift-register realisation. The state is the pair $(u[k-1],\,u[k-2])$ held in the two delay elements; the upper adder forms $v_1 = u[k] \oplus u[k-2]$ and the lower adder forms $v_2 = u[k] \oplus u[k-1] \oplus u[k-2]$.

Approach. Part (a) is a direct shift-register simulation: step the two-bit state through the message plus two flush bits and read the two modulo-2 sums at each step. Part (b) builds the four-state trellis, runs an add–compare–select forward pass with Hamming branch metrics, traces back the survivor from the terminating all-zero state, and re-encodes the survivor to name the corrected bit.

Part (a) — write the encoder equations from the generators. A generator polynomial is a tap pattern on the shift register, so $$v_1[k] = u[k] \oplus u[k-2], \qquad v_2[k] = u[k] \oplus u[k-1] \oplus u[k-2],$$ with $\oplus$ denoting modulo-2 addition. The state is $\sigma[k] = (u[k-1],\,u[k-2])$, which takes four values, and the next state is $(u[k],\,u[k-1])$.

Step the register through the padded message. Zero padding appends $m = 2$ zeros to 11010, so the input sequence driving the encoder is $1,1,0,1,0,0,0$. Starting from $\sigma = (0,0)$:

$k$	$u[k]$	state $(u[k-1],u[k-2])$	$v_1 = u \oplus u[k-2]$	$v_2 = u \oplus u[k-1] \oplus u[k-2]$	output	next state
1	1	00	$1 \oplus 0 = 1$	$1 \oplus 0 \oplus 0 = 1$	11	10
2	1	10	$1 \oplus 0 = 1$	$1 \oplus 1 \oplus 0 = 0$	10	11
3	0	11	$0 \oplus 1 = 1$	$0 \oplus 1 \oplus 1 = 0$	10	01
4	1	01	$1 \oplus 1 = 0$	$1 \oplus 0 \oplus 1 = 0$	00	10
5	0	10	$0 \oplus 0 = 0$	$0 \oplus 1 \oplus 0 = 1$	01	01
6 (pad)	0	01	$0 \oplus 1 = 1$	$0 \oplus 0 \oplus 1 = 1$	11	00
7 (pad)	0	00	$0 \oplus 0 = 0$	$0 \oplus 0 \oplus 0 = 0$	00	00

Reading the output column left to right and $g_1$ before $g_2$ within each branch gives $$\boxed{\mathbf{v} = 11\;10\;10\;00\;01\;11\;00 = 11101000011100}$$ Two checks worth stating: the encoder ends in state 00, as the flush bits are there to guarantee, and the 5-bit message has produced $2(5+2) = 14$ output bits, which is exactly the length of the sequence part (b) observes.

Part (b) — set up the trellis and the branch metric. The channel is a hard-decision (binary) channel, so maximum-likelihood decoding means minimum Hamming distance: the branch metric is the number of positions in which the branch's 2-bit label disagrees with the corresponding received pair. Splitting $\mathbf{r}$ into branches gives $$\mathbf{r} = 00\;\;11\;\;11\;\;10\;\;00\;\;01\;\;11 .$$ Because the encoder is stated to start and end in the all-zero state, the last $m = 2$ branches are forced to input 0. Imposing that termination is essential — without it the traceback can select a path no terminated encoder could ever have produced.
Run the forward add–compare–select pass. At each node the two incoming path metrics are formed, compared, and the smaller retained as the survivor. Figure 1.2 shows the result: node labels are cumulative path metrics, and the highlighted path is the global survivor.

Figure 1.2 — Viterbi trellis for the received word 00111110000111. Solid branches are input 0, dashed branches input 1; the number under each node is its surviving path metric. The final two stages carry input-0 branches only because the encoder is terminated.

The survivor's cumulative metric evolves as $0,\,0,\,1,\,1,\,1,\,1,\,1$: it takes no penalty over the first two branches, absorbs a single mismatch on branch 3, and matches perfectly thereafter.
Trace back and read the decoded message. Following the survivor backwards from the terminating 00 node and recording the input label of each branch gives the input sequence $0,1,1,0,1,0,0$, of which the last two are the known flush bits. Hence $$\boxed{\hat{\mathbf{u}} = 01101}$$ Re-encoding $\hat{\mathbf{u}}$ through the same shift register returns the codeword $\hat{\mathbf{v}} = 00111010000111$, whose final path metric of 1 confirms the forward pass.
Name the corrected bit and show the decision is unique. Comparing the survivor codeword with the observation,

bit 1–5 bit 6 bit 7–14

received $\mathbf{r}$ 00111 1 10000111

decoded $\hat{\mathbf{v}}$ 00111 0 10000111

so exactly one channel error occurred, in output bit position 6 (the second bit of branch 3), and the decoder has corrected it. Exhaustively scoring all $2^5 = 32$ terminated messages puts the runner-up at Hamming distance 4 against the survivor's distance 1, so the maximum-likelihood decision is unique by a margin of three — a stronger statement than "the survivor won", and cheap to quote.

	bit 1–5	bit 6	bit 7–14
received $\mathbf{r}$	00111	1	10000111
decoded $\hat{\mathbf{v}}$	00111	0	10000111

Quantity	Result
(a) Encoded output for input 11010 (with zero padding)	11101000011100
(a) Branch-by-branch labels	11 10 10 00 01 11 00
(b) Maximum-likelihood input sequence	01101
(b) Corresponding transmitted codeword	00111010000111
(b) Final survivor path metric	1 (runner-up: 4)
(b) Error corrected	single bit error at output position 6

Topic. Rate-$1/2$ convolutional codes and maximum-likelihood sequence estimation by the Viterbi algorithm.

Key relations. Encoder: $v_j[k] = \sum_{i} g_{j,i}\, u[k-i] \pmod 2$. Hard-decision branch metric: Hamming distance $d_H(\text{branch label},\, \text{received pair})$. Add–compare–select: $M_{\text{new}}(\sigma') = \min_{\sigma \to \sigma'} \big[ M(\sigma) + d_H \big]$. Free distance of this $(2,1,2)$ code: $d_{\text{free}} = 5$, so it corrects $\lfloor (d_{\text{free}}-1)/2 \rfloor = 2$ errors per error event.

Why this works. Over a memoryless binary symmetric channel with crossover probability $p < 1/2$, the likelihood of a candidate path falls monotonically with its Hamming distance from the observation, so minimising distance is maximising likelihood. The Viterbi algorithm exploits the Markov structure of the encoder: any two paths arriving at the same state at the same time share an identical future, so the one with the larger accumulated distance can never overtake and is discarded immediately. That reduces an exponential search over $2^{L}$ messages to a linear sweep with $2^{m}$ survivors, and the trellis termination forced by the flush bits removes the ambiguity at the tail where the survivors have not yet merged.

Common pitfall. Forgetting the zero padding, which shortens the codeword by $2m$ bits and makes the received length disagree with the trellis. The second classic slip is allowing input-1 branches in the final $m$ stages of the decoder: the encoder is stated to end all-zero, so those branches do not exist, and permitting them can hand the traceback an illegal path with a spuriously low metric.

Source. Sklar, Digital Communications, 2nd ed., Ch. 7 (Channel Coding Part 2 — convolutional encoding, trellis and state diagrams, Viterbi decoding); Proakis & Salehi, Digital Communications, 5th ed., Ch. 8.

Question 1 of 5: Convolutional Encoding and Viterbi Decoding

Question 1: Convolutional Encoding and Viterbi Decoding (25 marks)