viterbi

Pure-Rust, no-unsafe, no_std-friendly convolutional encoder and Viterbi (Maximum-Likelihood Sequence Estimation) decoder — the CCSDS K = 7, R = 1/2 inner code for concatenated forward error correction.

⚠️ Status: pre-release (v0.0.0). This publish is a name reservation placeholder. The public API is not yet stable and the encoder/decoder are under active development following an SBTDD (Spec → Behavior → Test-Driven Development) workflow. Do not depend on it for production yet.

Where it fits

This crate is the inner code of the classic CCSDS concatenation scheme. Its partner, the outer code, is reedsolomon-rs — RS(255,223) over GF(2⁸). A (planned) interleaver crate sits between them to break up the error bursts a Viterbi decoder produces on failure.

                 TX                                                   RX
  data → [RS(255,223)] → [interleaver] → [conv. K=7] → CHANNEL → [Viterbi] → [de-interleaver] → [RS decode] → data
         outer (block)    spreads bursts   inner (stream)  AWGN   this crate    regroups          outer

The composition applied at the transmitter is VT( interleave( RS( data ) ) ) — read "Viterbi of Reed–Solomon": RS is applied first (outer), Viterbi last (inner, next to the channel). The Viterbi soft-decision decoder extracts the random-noise coding gain (~2 dB); when it errs it produces bursts, which the interleaver disperses and Reed–Solomon — strong against grouped errors — mops up.

Design goals

Provable correctness — validated against known reference vectors and published BER-vs-Eb/N0 curves (CCSDS 130.1-G-2), not "seems to work".
Total memory safety — #![forbid(unsafe_code)] crate-wide. Any future SIMD path is gated behind an opt-in feature with a safe fallback.
no_std first — const-generic buffers where possible; alloc/std are additive features. Runs on MCU and Jetson-class hosts alike.
Determinism — same input ⇒ same output, bit-for-bit, on every platform.
Numerical robustness — no path-metric overflow on arbitrarily long streams (renormalization / modular normalization).
Dual-use API — works standalone on a noisy link and concatenated with reedsolomon-rs, without forcing either.

Reference parameters (CCSDS, primary target)

Parameter	Value
Constraint length	`K = 7` (memory `m = 6`, 64 trellis states)
Mother rate	`R = 1/2` (non-systematic)
Generator G1	`171` octal = `1 + D + D² + D³ + D⁶`
Generator G2	`133` octal = `1 + D² + D³ + D⁵ + D⁶` (output inverted, CCSDS convention)
`d_free`	10
Reference	CCSDS 131.0-B-3 (normative), CCSDS 130.1-G-2 (informative)

Roadmap

Version	Scope
`v0.0.x`	CCSDS K=7 R=1/2 encoder + hard-decision block decoder; reference vectors + round-trip; precomputed trellis; metric abstracted behind a trait.
`v0.1.x`	Soft-decision (3-bit Euclidean); BER validation against curves; robust renormalization.
`v0.2.x`	Streaming mode (sliding-window traceback) with bounded latency for real-time robotics links.
`v0.3.x`	Puncturing (2/3, 3/4, 5/6, 7/8) as a wrapping layer.
`v0.4.x`	End-to-end concatenation: `reedsolomon-rs` + interleaver + `viterbi`.
`v0.5.x`	Node synchronization; `simd` feature; `no_std`/MCU hardening.
`v1.0.0`	Stable API, SOVA/erasures output, full docs, regression benches.

Related crates

reedsolomon-rs — outer RS(255,223) code.
interleaver (planned) — burst-spreading interleaver (CSPRNG-derived primary; block/convolutional baselines).

Contributing

The authoritative design lives in VITERBI_CRATE_SPEC.md. Every requirement maps to a behavior and a test (SBTDD); no version advances without its spec ↔ behavior ↔ test green under nextest, clippy, and miri.

License

Licensed under either of

Apache License, Version 2.0 (LICENSE-APACHE)
MIT license (LICENSE-MIT)

at your option.

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

viterbi 0.0.0