Convolutional Codes

What Problem Are We Solving?

When you send data over a wireless channel, bits can get corrupted. To fix errors, you add redundancy, extra bits that help the receiver figure out what you actually sent.

Hamming codes do this by working on fixed blocks. Take 11 bits, add 4 check bits, send the 15-bit block. Each block is independent.

Convolutional codes take a different approach. Instead of fixed blocks, they work on a continuous stream of bits. And here’s the key difference:

Each output bit depends not just on the current input, but also on the previous inputs.

The encoder remembers what you sent before.

What is an Encoder?

The encoder is the device that takes your input bits and produces output bits with redundancy added.

Think of it as a machine with a few memory slots. When you feed in a bit:

1. The new bit enters the first slot
2. The old bits shift over to make room
3. The encoder looks at what’s in the slots and produces output

The animation shows bits shifting through memory slots. As each new bit enters, the previous bits move over. The encoder uses all the bits currently in memory to create output.

Why Memory Matters

Because the output depends on multiple bits (current + previous), there’s more redundancy built in.

If one bit gets corrupted during transmission, the receiver can use the surrounding context to figure out what it should have been. More memory = more context = better error correction.

The Generator Polynomial

Now we need to tell the encoder exactly how to combine the bits in memory. That’s what the generator polynomial does.

A generator polynomial is just a pattern that tells the encoder which memory slots to use when creating output.

Example: $G_0 = 1101$

Read it right to left. Each position corresponds to a memory slot:

• $1$ (rightmost) → use the current bit (slot 0)
• $0$ → skip slot 1
• $1$ → use slot 2
• $1$ (leftmost) → use slot 3

So $G_0 = 1101$ means: “combine the bits in slots 0, 2, and 3 to produce one output bit.”

Two Polynomials = Two Outputs

If the encoder has two generator polynomials ($G_0$ and $G_1$), it produces two output bits for every input bit.

• $G_0$ tells it how to make the first output
• $G_1$ tells it how to make the second output

This is where the redundancy comes from. You put in $1$ bit, you get $2$ bits out. The extra bit carries information about the history, which helps correct errors.

How Encoding Works

Let’s see the actual encoding process step by step.

The polynomial tells you which slots to look at!

Each digit in the polynomial corresponds to a slot. A $1$ means “use this slot”, a $0$ means “skip it”.

$G_0 = 1101$ — read right to left:

So $G_0 = 1101$ means: look at slots 0, 2, and 3. XOR those values together.

$G_1 = 1110$ — same idea:

• Slots 0, 1, 2 → Yes (the three $1$s)
• Slot 3 → No (the $0$)

Now watch the animation. It will highlight which slots each polynomial looks at, then XOR those values to produce output.

Step 1: Input bit $1$ arrives

Using $G_0 = 1101$: The 1s are at positions 0, 2, 3 (reading right to left). So we look at slots 0, 2, and 3. They contain: $1$, $0$, $0$. XOR them: $1 \oplus 0 \oplus 0 = 1$

Using $G_1 = 1110$: The 1s are at positions 0, 1, 2. So we look at slots 0, 1, and 2. They contain: $1$, $0$, $0$. XOR them: $1 \oplus 0 \oplus 0 = 1$

Output: $11$

Step 2: Input bit $0$ arrives (everything shifts right)

Using $G_0 = 1101$: Look at slots 0, 2, and 3. They contain: $0$, $0$, $0$. XOR them: $0 \oplus 0 \oplus 0 = 0$

Using $G_1 = 1110$: Look at slots 0, 1, and 2. They contain: $0$, $1$, $0$. XOR them: $0 \oplus 1 \oplus 0 = 1$

Output: $01$

Result: Input $10$ became output $1101$

Two input bits became four output bits. That’s the redundancy. And notice how the second output ($01$) depends on both the current bit ($0$) AND the previous bit ($1$) that shifted into slot 1.

The Key Numbers

Now we can understand what the formulas actually mean:

Code Rate

How many output bits do you get for each input bit?

If you have 2 polynomials → 2 outputs per input → $R = 1/2$

If you have 3 polynomials → 3 outputs per input → $R = 1/3$

Lower rate = more redundancy = better error correction (but more bandwidth used).

Constraint Length (K)

How many digits are in the polynomial?

This tells you the encoder’s memory size. $K-1$ slots hold previous bits.

• $K = 4$ → 3 memory slots
• $K = 6$ → 5 memory slots

Longer polynomial = more memory = output depends on more history = better error correction.

Number of States

The memory slots hold bits ($0$ or $1$). The state is whatever combination of bits is currently in memory.

States = $2^{K-1}$

Which Code is Better?

If two codes have the same rate but different constraint lengths:

Longer constraint length = lower bit error rate.

More memory means the encoder can create more sophisticated redundancy. The decoder has more context to work with when fixing errors.

$K = 6$ beats $K = 4$. Always.

Worked Example

Given:

• Scheme I: $G_0 = 1101$, $G_1 = 1110$
• Scheme II: $G_0 = 110101$, $G_1 = 111011$

Find the code rate, constraint length, and number of states. Which has lower BER?

Summary