viterbi

Pure-Rust, #![forbid(unsafe_code)] convolutional encoder and hard-decision Viterbi (Maximum-Likelihood Sequence Estimation) decoder, implementing the classic CCSDS K = 7, R = 1/2 inner code: generators G1 = 0o171, G2 = 0o133 (G2 output inverted), 2 output bits per input bit, d_free = 10. Zero runtime dependencies.

It is the inner FEC layer of the CCSDS concatenated coding scheme — pair it with an outer Reed–Solomon code (see reedsolomon) and a burst interleaver:

TX:  data → [RS(255,223)] → [interleaver] → [conv. K=7] → CHANNEL
RX:  CHANNEL → [Viterbi] → [de-interleaver] → [RS decode] → data
                └── this crate

Correction, not detection. The Viterbi decoder returns the maximum-likelihood best-effort sequence; beyond the code's capability it yields a well-formed but possibly wrong result with no integrity flag. Detecting residual errors is the job of the consuming crate's outer code (RS) + CRC. This crate never panics on the decode path.

Features

Installation

[dependencies]
viterbi = "0.1"

Quick Start

use viterbi::{CcsdsViterbiDecoder, CodeParams, ViterbiEncoder};

fn main() {
    let enc = ViterbiEncoder::new(CodeParams::ccsds_r1_2()).unwrap();
    // A decoder sized for the largest block you will feed it (bounds memory, R18):
    let mut dec = CcsdsViterbiDecoder::new(CodeParams::ccsds_r1_2(), 4096).unwrap();

    let data = b"hello, viterbi";
    let mut coded = enc.encode(data).unwrap();       // rate-1/2 coded block (bytes + exact bit length)

    coded.bytes[0] ^= 0b0000_0010;                   // flip one channel bit

    let decoded = dec.decode_block(&coded).unwrap();  // Viterbi corrects it
    assert_eq!(decoded.bytes, data);
}

See examples/roundtrip.rs for a runnable version.

How It Works

The decoder is the canonical three-subsystem Viterbi pipeline:

• BMU (Branch Metric Unit) — hard-decision Hamming distance between the received symbol and each branch's expected output, behind the monomorphized BranchMetric trait.
• ACS (Add-Compare-Select) — the hot path: 64 states × 2 branches per bit. Adds branch metrics, selects the survivor (ties broken deterministically toward the lower-numbered predecessor state), then renormalizes by subtracting the minimum metric every stage — lossless, and the sole guard against u32 overflow on unbounded streams.
• SMU / Traceback — one survivor decision bit per (stage, state); zero-tail termination guarantees the encoder ends in state 0, so traceback walks back from state 0 over the whole block. The m = 6 tail bits are dropped; the payload is unpacked MSB-first.

The encoder appends m = 6 zero tail bits (zero-tail flushing) so encoding starts and ends in state 0.

Guarantees

• No panic on the decode path — decoding arbitrary bytes always terminates with a best-effort output; validated continuously by cargo fuzz and cargo miri.
• No unsafe / no UB — #![forbid(unsafe_code)] crate-wide; miri-clean.
• Bounded memory — a configurable max_info_bits cap rejects oversized input via Result; all hot-path allocation is preallocated and fallible (try_reserve).
• Determinism — no non-deterministic floating point in the correction path.

Convention (configurable, not hardcoded)

Generator polynomials, per-generator output inversion, and output order are data in a CodeParams value (validated, non-catastrophic), with a first-class CodeParams::ccsds_r1_2() preset. Bit/byte I/O is byte slices, MSB-first, with the exact bit length carried explicitly so non-byte-aligned payloads round-trip unambiguously.

Testing

Correctness is validated with reference vectors, proptest property tests (decode(encode(x)) == x, exact recovery under bounded/spaced error injection, packing round-trips), edge/boundary cases, and milestone hardening gates: cargo miri (no UB) and cargo fuzz (decoder never panics on arbitrary input).

cargo nextest run          # unit + property + integration
cargo clippy --all-targets -- -D warnings
cargo +nightly miri test --lib
cargo +nightly fuzz run decode        # and decode_raw

Roadmap

Minimum Supported Rust Version

Rust 1.75 or later.

License

Licensed under either of Apache License, Version 2.0 or MIT license at your option.

Contribution

Unless you explicitly state otherwise, any contribution intentionally submitted for inclusion in the work by you, as defined in the Apache-2.0 license, shall be dual licensed as above, without any additional terms or conditions.

Credits

Developed by BolivarTech. Part of the CCSDS concatenated FEC family alongside reedsolomon.