viterbi 0.1.0

Pure-Rust, no-unsafe convolutional encoder and hard-decision Viterbi (MLSE) decoder — CCSDS K=7 R=1/2 inner code for concatenated FEC.
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148

# viterbi

[![Crates.io](https://img.shields.io/crates/v/viterbi.svg)](https://crates.io/crates/viterbi)
[![Documentation](https://docs.rs/viterbi/badge.svg)](https://docs.rs/viterbi)
[![License](https://img.shields.io/crates/l/viterbi.svg)](https://github.com/BolivarTech/viterbi-rs#license)
[![CI](https://github.com/BolivarTech/viterbi-rs/actions/workflows/ci.yml/badge.svg)](https://github.com/BolivarTech/viterbi-rs/actions/workflows/ci.yml)
[![Release](https://github.com/BolivarTech/viterbi-rs/actions/workflows/release.yml/badge.svg)](https://github.com/BolivarTech/viterbi-rs/actions/workflows/release.yml)

**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`](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

| Capability | Detail |
|------------|--------|
| **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 |
| **Extensible core** | Monomorphized `BranchMetric` trait (soft-decision ready) and const-generic trellis (`K ≤ 9` ready) — the next minor adds soft-decision, puncturing and rate 1/3 additively |

## Installation

```toml
[dependencies]
viterbi = "0.1"
```

## 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

| Version | Scope |
|---------|-------|
| `v0.0.x` | **This release** — CCSDS `K=7 R=1/2` encoder + hard-decision block decoder |
| `v0.1.x` | Soft-decision (3-bit Euclidean) + BER-vs-Eb/N0 validation (~2 dB gain) |
| `v0.2.x` | Streaming (sliding-window traceback), bounded real-time latency |
| `v0.3.x` | Puncturing (2/3, 3/4, 5/6, 7/8) as a separable wrapping layer |
| `v0.4.x` | End-to-end concatenation with `reedsolomon` + interleaver |
| `v0.5.x` | Node synchronization, `simd` feature, `no_std` / MCU hardening |

## Minimum Supported Rust Version

Rust **1.75** 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).