# viterbi
[](https://crates.io/crates/viterbi)
[](https://docs.rs/viterbi)
[](https://github.com/BolivarTech/viterbi-rs#license)
[](https://github.com/BolivarTech/viterbi-rs/actions/workflows/ci.yml)
[](https://github.com/BolivarTech/viterbi-rs/actions/workflows/release.yml)
**Pure-Rust, `#![forbid(unsafe_code)]` convolutional encoder and Viterbi
(Maximum-Likelihood Sequence Estimation) decoder** for the CCSDS inner FEC envelope:
**hard- and soft-decision (LLR)** decoding, **rate 1/2 and 1/3** mother codes,
**puncturing** (2/3, 3/4, 5/6, 7/8), and **generic constraint length `K ≤ 9`** — with the
classic **CCSDS `K = 7`, `R = 1/2`** code (`G1 = 0o171`, `G2 = 0o133`, G2 inverted,
`d_free = 10`) as the first-class default profile. 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`](https://crates.io/crates/reedsolomon)) and a
burst interleaver:
```text
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
| **Error correction** | Viterbi MLSE over the 64-state trellis; corrects channel error patterns up to `⌊(d_free−1)/2⌋ = 4` per constraint span (pattern-dependent, not a fixed block-`t`) |
| **Bit-exact CCSDS** | Encoder output matches the CCSDS `K=7 R=1/2` convention (G2 inverted, `C1,C2` order), cross-checked against an impulse vector and an independent oracle |
| **Deterministic** | Same input ⇒ same output, bit-for-bit, on every platform; integer-only correction path, fixed lower-numbered-predecessor tie-break |
| **No panic on decode** | The ACS correction loop is infallible; `Result` only at configuration boundaries; arbitrary/malformed input never panics or triggers UB |
| **Bounded, fallible memory** | Survivor/scratch buffers preallocated with `try_reserve`; a configurable maximum block length rejects oversized input via `Result` instead of aborting |
| **Overflow-proof metrics** | Mandatory per-stage subtract-min renormalization keeps `u32` path metrics bounded on arbitrarily long streams |
| **No `unsafe`** | `#![forbid(unsafe_code)]` crate-wide |
| **No runtime deps** | std-only; `proptest` / `cargo-fuzz` / `miri` are dev/CI-only |
| **Soft-decision (LLR)** | 3-bit-style `i8` LLR metric (`SoftLlr`, `λ>0 ⇒ bit 0`); integer min-sum, ML-equivalent, deterministic; recovers the ~2 dB soft-decision coding gain, BER-validated against CCSDS 130.1-G-2 |
| **Rate 1/2 & 1/3** | Both CCSDS mother codes; rate-1/3 (`g = 0o133, 0o171, 0o145`, `d_free = 14`) encoder cross-checked against an independent implementation (`komm`); `n`-generic trellis |
| **Puncturing** | Separable wrapping layer — 2/3, 3/4, 5/6, 7/8 (Yasuda/CCSDS patterns as runtime data); catastrophic-puncture rejection; tail-exempt; `ByColumn`/`Interleaved` order |
| **Generic `K ≤ 9`** | Const-generic trellis + runtime tail length `m = k−1`; `CodeProfile` registry (`CcsdsR1_2`, `CcsdsR1_3`, `K9R1_2`) |
| **Extensible core** | Monomorphized `BranchMetric` trait and const-generic trellis; every allocation fallible (`try_reserve`), every length product checked |
## Installation
```toml
[dependencies]
viterbi = "0.2"
```
## Quick Start
```rust
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`](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).
```sh
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
| `v0.0.x` | ✅ CCSDS `K=7 R=1/2` encoder + hard-decision block decoder |
| `v0.1.x` | ✅ Toolchain bump (MSRV + CI → Rust 1.96) |
| `v0.2.x` | ✅ **This release** — soft-decision (LLR) + BER validation (~2 dB gain), rate 1/3, puncturing (2/3–7/8), generic `K ≤ 9` |
| `v0.3.x` | Streaming (sliding-window traceback), bounded real-time latency |
| `v0.5.x` | End-to-end concatenation with `reedsolomon` + interleaver |
| `v0.6.x` | Node synchronization, `simd` feature, `no_std` / MCU hardening |
| `v1.0.0` | Stable API, SOVA / soft-output / erasure reliabilities, regression benches |
## Minimum Supported Rust Version
Rust **1.96** or later.
## License
Licensed under either of [Apache License, Version 2.0](LICENSE-APACHE) or
[MIT license](LICENSE-MIT) 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](https://github.com/BolivarTech). Part of the CCSDS concatenated
FEC family alongside [`reedsolomon`](https://crates.io/crates/reedsolomon).