(2,1,6) Convolutional Code — Encoder + Viterbi Decoder

A from-scratch C implementation of a rate-1/2, constraint-length K = 7 convolutional code with a 64-state, soft- and hard-decision Viterbi decoder, plus a BER-vs-SNR Monte-Carlo simulation over a BPSK / AWGN channel.

This is the classic NASA / CCSDS standard code with generator polynomials (octal 133, 171):

$$ \begin{aligned} x_1 &= 1 + D^2 + D^3 + D^5 + D^6 \\ x_2 &= 1 + D + D^2 + D^3 + D^6 \end{aligned} $$

Everything — the encoder, the AWGN channel model, the trellis, and the Viterbi algorithm — is written by hand with no external DSP/comms libraries.

---

Repository layout

.
├── src/conv_viterbi_sim.c   # encoder + AWGN channel + Viterbi decoder + BER
├── Sim.txt                  # simulation parameters (read at startup)
├── Makefile                 # build & run
├── assets/                  # BER figure + its dependency-free generator
├── matlab/plot_ber.m        # BER-vs-SNR plotting of collected results
└── docs/                    # project report (PDF) and slides (PPTX)

Build & run

Requires a C11 compiler and the math library (-lm).

make          # builds ./conv_viterbi_sim
make run      # builds (if needed) and runs the simulation in Sim.txt
make clean    # removes the binary and the generated Output_*.txt files

Example output:

N= 50000
truncation window width L = 18
SNR= 5.000000 dB
decoded bits= 49982
decided bit errors= 3
BER= 6.0e-05

Simulation parameters — Sim.txt

One value per line (the trailing %… text is a comment and is ignored):

50000  %N    : number of information bits
18     %L    : Viterbi truncation window width
5.0    %SNR  : bit signal-to-noise ratio (dB)
-2000  %Seed : negative integer seed for the PRNG
1      %      : 0 = hard-decision, 1 = soft-decision

The run writes the noisy channel symbols followed by the decoded bits to Output_Soft.txt (soft decision) or Output_Hard.txt (hard decision), and prints the measured bit-error rate to stdout.

How it works

The transmit/receive chain is a straight pipeline, and the decoder is structured in three stages that mirror a hardware datapath:

1. Message — a length-N test sequence from an x⁶ + x⁵ + 1 LFSR (m-sequence).
2. Encoder — each input bit is pushed through the 6-stage shift register to produce the two coded bits (x1, x2), then BPSK-mapped (0 → +1, 1 → −1). Six zero tail bits flush the register back to the all-zero state.
3. Channel — i.i.d. Gaussian noise (polar Box–Muller on a portable minimal-standard PRNG, ran1) is added so that 1/σ² = 10^(SNR/10).
4. Decision — soft decision keeps the real-valued correlations; hard decision quantises each symbol back to ±1.
5. Viterbi decoder (64 states, branch metric = correlation / inner product, so the survivor is the maximum-metric path):
   • INITIAL — enumerate all 64 depth-6 paths and seed their metrics.
   • ACS — add-compare-select until the survivor window is filled to depth L.
   • SLIDING — emit one decoded bit per step while sliding the window forward; path metrics are periodically renormalised to avoid overflow.
6. BER — decoded bits are compared against the transmitted message.

Results — soft vs. hard decision (L = 18, N = 200 000)

Soft-decision decoding shows the expected ~2 dB coding gain over hard decision:

SNR (dB)	Hard-decision BER	Soft-decision BER
0	3.9 × 10⁻¹	2.0 × 10⁻¹
1	2.8 × 10⁻¹	7.5 × 10⁻²
2	1.5 × 10⁻¹	1.8 × 10⁻²
3	5.2 × 10⁻²	2.4 × 10⁻³
4	1.2 × 10⁻²	2.0 × 10⁻⁴
5	2.1 × 10⁻³	2.5 × 10⁻⁵

Regenerate the figure with python3 assets/plot_ber.py (no dependencies), or the full multi-block-length curves with matlab/plot_ber.m.

References

• A. J. Viterbi, "Error bounds for convolutional codes and an asymptotically optimum decoding algorithm," IEEE Trans. Inf. Theory, 1967.
• W. H. Press et al., Numerical Recipes in C, 2nd ed. — ran1 PRNG.
• See docs/ for the full project report and slides.

License

Released under the MIT License.

Author

TimmyPan — course project for Error-Correcting Codes (ECC).