Module conv 

Convolutional codes: trellis, Viterbi and BCJR decoders.

A Trellis describes a rate-$1/n$ code with $2^{K-1}$ states: from every state, an input bit leads to a next state and emits $n$ coded bits. Two families are built:

• feed-forward codes (Trellis::feedforward) from octal generators, the most significant bit tapping the current input — the $(133, 171)_{8}$ code of constraint length 7 (ConvolutionalCode::k7) is the classical one (802.11, DVB-S, LTE);
• recursive systematic codes (Trellis::recursive), the constituents of turbo codes, with a feedback and a feed-forward polynomial (LTE: $(13, 15)_{8}$).

Decoders

• viterbi: maximum-likelihood sequence detection; with LLR inputs, the branch metric is the correlation $\sum_{i} (1 - 2 c_{i}) L_{i} / 2$ (soft decisions), with hard decisions it is the Hamming distance — about 2 dB apart (Viterbi 1967; Forney 1973);
• viterbi_tail_biting: a tail-biting code, whose path ends in the state it starts from (Trellis::encode_tail_biting, the code of the PBCH of LTE), by the wrap-around Viterbi algorithm of Shao, Lin and Fossorier (2003);
• bcjr: the a posteriori LLR of every input bit (Bahl, Cocke, Jelinek & Raviv 1974), in the log domain with the exact Jacobian logarithm (log-MAP) or its maximum (max-log-MAP).

Examples

use comnum_fec::block::BlockCode;
use comnum_fec::conv::ConvolutionalCode;
let code = ConvolutionalCode::k7(100)?;
let info: Vec<u8> = (0..100).map(|i| ((i * 7) % 3 == 0) as u8).collect();
let c = code.encode_block(&info)?;
assert_eq!(c.len(), 2 * (100 + 6));                           // terminated
let llr: Vec<f64> = c.iter().map(|&b| if b == 0 { 4.0 } else { -4.0 }).collect(); // noiseless
assert_eq!(code.decode_block(&llr)?, info);

References

1. A. J. Viterbi, “Error bounds for convolutional codes and an asymptotically optimum decoding algorithm,” IEEE Trans. Inf. Theory, 13(2), 260–269, 1967.
2. G. D. Forney, “The Viterbi algorithm,” Proc. IEEE, 61(3), 268–278, 1973.
3. L. R. Bahl, J. Cocke, F. Jelinek and J. Raviv, “Optimal decoding of linear codes for minimizing symbol error rate,” IEEE Trans. Inf. Theory, 20(2), 284–287, 1974.
4. P. Robertson, E. Villebrun and P. Hoeher, “A comparison of optimal and sub-optimal MAP decoding algorithms operating in the log domain,” Proc. IEEE ICC, 1995.
5. R. Y. Shao, S. Lin and M. P. C. Fossorier, “Two decoding algorithms for tailbiting codes,” IEEE Trans. Commun. 51(10), 1658–1665, 2003 (tail biting, the WAVA).

Structs

ConvolutionalCode

A terminated rate-$1/n$ convolutional code over blocks of k information bits, decoded by soft-decision Viterbi.

Trellis

The trellis of a rate-$1/n$ binary convolutional code, built by Trellis::feedforward or Trellis::recursive (its fields are read through getters, so that the tables always agree with the constraint length and the number of outputs).

Functions

bcjr

The BCJR algorithm in the log domain: the a posteriori LLR of every input bit, given the channel LLRs of the coded bits (n per step) and the a priori LLRs of the inputs (apriori, zero if empty). jacobian selects log-MAP (Jacobian::Exact) or max-log-MAP (Jacobian::MaxLog); terminated forces the final state to zero.

viterbi

Viterbi decoding of steps = llr.len() / n trellis steps from state 0; with terminated, the path ends in state 0 and the last $K - 1$ inputs (the tail) are dropped. Returns the decided input bits.

viterbi_tail_biting

Viterbi decoding of a tail-biting code (Trellis::encode_tail_biting) by the wrap-around Viterbi algorithm (WAVA) of Shao, Lin and Fossorier (2003): a pass starts from every state with the metrics that the previous pass ended with (all zero for the first), and the decoding stops at the first pass whose best path starts and ends in the same state; after passes passes, the best path among those that start and end in the same state is kept (the best path if there is none). Returns the decided input bits, one per step.