A message through noise
A transmitter sends a message of bits through a channel that sometimes flips a bit. To make the errors correctable, the message is encoded with a convolutional code. The encoder has a register of K bits, initially zero. The next bit of the message is shifted into the register as the high bit, the low bit falls out, and two bits go into the channel: the parities of the register bits marked with ones in the binary notation of the generators g1 and g2. For example, the generator 171 = 11110012 with K = 7 takes the new bit and the bits shifted in 1, 2, 3 and 6 steps earlier. After the message K − 1 more zeros are shifted into the register, and two bits go out for each of them too; this returns the register to zero.
2(n + K − 1) bits have arrived, some of them flipped. Find a message of n bits whose code differs from what arrived in the fewest places.
In the tests the messages are passages from War and Peace in UTF-8, and the channel flips different shares of the bits, from none to half. The code with K = 7 and generators 171 and 133 (octal) is the one from the article.
Input
The first line holds K, g1, g2 and n: 2 ≤ K ≤ 7, the generators written as octal numbers from 1 to 2K − 1, 1 ≤ n ≤ 104. The second holds the bits that arrived: a string of 2(n + K − 1) zeros and ones.
Output
On the first line, the smallest number of places in which the message’s code differs from the bits that arrived. On the second, the message itself: n zeros and ones. If there are several suitable messages, output any.
Examples
Example 1
3 7 5 4 111000010111
0 1011
Example 2
3 7 5 4 101000110111
2 1011
Limits
- Time · Python
- 8000 ms
- Time · Go
- 1000 ms
- Memory
- 256 MB
- Judging
- 10 tests
Walkthrough
Open it step by step: each step gives away a little more. You can jump straight to the solution, but a problem solved with one hint stays with you longer.
1Hint 1
There are 2n messages, and they cannot be enumerated. But the code at each step depends not on the whole message but only on the contents of the register. How many different states does the encoder have between steps?
2Hint 2
A state is the last K − 1 bits of the message, 2K−1 of them, at most 64. Two different message beginnings leading to the same state behave identically from then on. Which of them is worth remembering?
3The idea
Let Dt(s) be the smallest number of mismatches with the bits that arrived among message beginnings of length t after which the encoder is in state s. From state s, bit b leads to the state where b has become the high bit and the low bit of s has fallen out, and produces two bits that are compared with the pair that arrived:
Dt+1(s′) = the minimum, over s, b leading to s′, of Dt(s) + the mismatches of the pair.
Mismatches after step t depend only on the state and the future bits, so of two beginnings with the same state the worse can be forgotten. This is the Viterbi algorithm, the very problem it was invented for: on a trellis of 2K−1 states, look for the path with the smallest sum of mismatches. On the tail steps only bit 0 is allowed, and the answer is D in the zero state at the end.
4Walkthrough
For each step and state store which state you came from; one bit is enough, the one that fell out of the register. The backtrack from the zero state recovers the bits: the message bit at a step is the high bit of the state after that step.
In the second example the code of the message 1011 is twelve bits, of which the second and seventh are flipped. The nearest message is 1011 again, at distance 2. On a passage from the novel almost two thousand bits long, with the code K = 7 and 5% of bits flipped, the nearest message coincides with the one sent; on a longer passage at 10% it differs from it in roughly every tenth bit. At such an error rate the code does not cope, but the nearest message is still well defined, and it has to be found.
4+Solution
5Complexity
O((n + K) · 2K) time: at each step, two transitions out of each of the 2K−1 states. That is a little over a million operations at n = 104 and K = 7. Memory for the backtrack is (n + K) · 2K−1 bits. Real decoders bound it: the decision on a bit is made after a fixed number of steps, usually a few K, when the paths from all states have almost certainly merged.
6Common mistakes
- Bit by bit. Choosing at each step the bit whose pair is closer to the one that arrived, without looking back: one flipped pair leads onto someone else’s branch, and the errors carry on. The second example catches this.
- Forgetting the tail. The last 2(K − 1) bits are the code of the zeros shifted in after the message; they are compared too, and the path must end in the zero state.
- The order of register bits. The new bit is the high one; the generator 171 = 1111001 is applied to the register as is. If the new bit is shifted in at the bottom, you get the mirror-image code, which has the same properties but different output bits.
- Octal notation. “171” is 121 in decimal, not 171.