22-Elec-B3 Digital Communications Systems · May 2016
Question 3 of 5: Error-control coding
Nivaar worked solution (AI-drafted; not reviewed by a licensed engineer)
Notes on this paper
Paper format. Professional Engineers of Ontario annual examinations, May 2016, 07-Elec-B3 Digital Communication Systems — 3 hours, closed book, a PEO-approved non-programmable calculator permitted. Five questions of 25 marks are printed; any four constitute a complete paper worth 100 marks, and only the first four appearing in the answer book are marked. Marks are shown in the left margin. Note 1 on the cover page urges the candidate to submit a clear statement of any assumptions made. All five questions are solved below, because the set is intended as a study resource rather than a sitting.
Reference texts. J. G. Proakis and M. Salehi, Communication Systems Engineering, 2nd ed. (link budgets, source coding, PCM); S. Haykin and M. Moher, Communication Systems, 5th ed.; B. Sklar, Digital Communications: Fundamentals and Applications, 2nd ed. (spread spectrum, ch. 12); T. M. Cover and J. A. Thomas, Elements of Information Theory, 2nd ed. (entropy and Huffman codes); S. Lin and D. J. Costello, Error Control Coding, 2nd ed. (convolutional codes and the Viterbi algorithm); A. V. Oppenheim and R. W. Schafer, Discrete-Time Signal Processing, 3rd ed. (sampling and quantization); T. S. Rappaport, Wireless Communications: Principles and Practice, 2nd ed. (path-loss models). In the Canadian frame, licence-exempt spread-spectrum equipment in the 2.4 GHz band is governed by ISED RSS-247, and spectrum allocations by the Canadian Table of Frequency Allocations.
Given. A rate-1/2 convolutional encoder with generator polynomials $g_1(D)=1+D^{2}$ and $g_2(D)=1+D+D^{2}$, outputs read $g_1$ then $g_2$, starting and ending in the all-zero state. Part (a) supplies the message 11010 with zero padding; part (b) supplies the received sequence 00111110000111.
Find. (a) the transmitted code sequence; (b) the maximum-likelihood message recovered by the Viterbi algorithm, together with any corrected errors.
Rate-1/2, K = 3 convolutional encoder. Green taps form v1 from g1(D) = 1 + D squared; amber taps form v2 from g2(D) = 1 + D + D squared.
Approach. Write the two output bits as modulo-2 sums of the current input and the two shift-register contents, run the message through the register to get part (a), then build the four-state trellis and accumulate Hamming branch metrics stage by stage, keeping one survivor per state and tracing back from the terminating all-zero state.
Part (a) — write down the encoder equations and the state definition. The generators have degree 2, so the encoder holds two memory elements and the code has constraint length $K=3$ with four states. Taking the state as $(s_1,s_2)=(u_{k-1},u_{k-2})$, the generator polynomials translate directly into
$$v_1^{(k)} = u_k \oplus u_{k-2}, \qquad v_2^{(k)} = u_k \oplus u_{k-1} \oplus u_{k-2},$$
where $\oplus$ is modulo-2 addition. Two flush bits are appended so the register returns to all-zero, making the message 11010 into the 7-bit input 1101000.
Part (a) — step the register through the padded message. Each row below applies the two equations, then shifts.
Encoder trace for input 11010 with two flush zeros
$k$
$u_k$
State $(u_{k-1},u_{k-2})$
$v_1$
$v_2$
Output
Next state
1
1
00
1
1
11
10
2
1
10
1
0
10
11
3
0
11
1
0
10
01
4
1
01
0
0
00
10
5
0
10
0
1
01
01
6
0
01
1
1
11
00
7
0
00
0
0
00
00
Reading the output column left to right,
$$\boxed{\text{encoded output} = 11\ 10\ 10\ 00\ 01\ 11\ 00 = 11101000011100}$$
Two checks confirm the length and the termination: 7 input bits at rate 1/2 must give 14 output bits, and the final state is 00 as the zero padding requires.
Part (b) — tabulate every trellis branch once. The Viterbi algorithm needs the output label of all eight transitions, which follow from the same two equations:
Trellis branch table (state $\rightarrow$ next state / output)
State
Input 0
Input 1
00
→ 00 / 00
→ 10 / 11
10
→ 01 / 01
→ 11 / 10
01
→ 00 / 11
→ 10 / 00
11
→ 01 / 10
→ 11 / 01
Note that the two branches leaving any state carry outputs at Hamming distance 2, which is what gives the code its error-correcting power.
Part (b) — split the received sequence into branch symbols. Fourteen received bits form seven stages:
$$r = 00\ \ 11\ \ 11\ \ 10\ \ 00\ \ 01\ \ 11.$$
Because the encoder is known to start and end in state 00, the first two stages fan out from 00 only, and the last two stages admit input 0 only — the trellis closes at both ends, which is what makes the terminating survivor unique.
Four-state trellis for the received sequence, with the surviving maximum-likelihood path in red.
Part (b) — accumulate the survivor metrics. At each stage every state keeps only the incoming path of least accumulated Hamming distance; ties would be broken arbitrarily, but none occurs on the surviving path here. A dash marks a state not yet reachable or no longer reachable once the trellis begins to close.
Part (b) — trace back from the terminating state. The path arriving at state 00 after stage 7 carries a total metric of 1. Following its stored predecessors backwards gives the state sequence
$$00 \rightarrow 00 \rightarrow 10 \rightarrow 11 \rightarrow 01 \rightarrow 10 \rightarrow 01 \rightarrow 00,$$
and since a transition into state $(u_k, u_{k-1})$ is caused by input $u_k$, the leading bit of each state read forward recovers the input sequence 0110100. Discarding the two flush zeros,
$$\boxed{\text{most likely message} = 01101}$$
Part (b) — identify and correct the channel error. Re-encoding 01101 with two flush zeros gives the valid code sequence
$$\hat{c} = 00\ \ 11\ \ 10\ \ 10\ \ 00\ \ 01\ \ 11 = 00111010000111,$$
which differs from the received 00111110000111 in the sixth bit only, matching the terminating metric of 1. So a single bit error occurred in the third branch symbol and the decoder has corrected it:
$$\boxed{\text{corrected sequence} = 00111010000111,\ \text{one error at received bit 6}}$$
Confirm the decision is unique. The nearest competing zero-terminated code sequence lies at Hamming distance 4 from the received word, three units further away than the survivor. That gap is consistent with the free distance of this code, $d_{free}=5$: a single error is comfortably inside the guaranteed correction radius $\lfloor (d_{free}-1)/2 \rfloor = 2$, so no other path can plausibly explain the observation and the maximum-likelihood decision is unambiguous.
