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

// Author: BolivarTech
// Version: 1.0.0
// Date: 2026-07-02
//! Add-Compare-Select + renormalization + deterministic tie-break (R9, R17).
use crate::metric::BranchMetric;
use crate::trellis::Trellis;

/// Initial metric for unreachable states — large, with headroom below `u32::MAX` (R9).
pub const SENTINEL: u32 = u32::MAX / 2;

/// Advance one trellis stage. `cur` holds the current (already renormalized) state metrics;
/// results go to `next`. `survivors` is this stage's `⌈S/64⌉` decision words — one bit per state
/// (which predecessor survived), so it scales to any `S` (R12). Returns the pre-renorm minimum
/// (diagnostic). Bounds-safe by construction (fixed `[_; S]`; `survivors.len() == ⌈S/64⌉`).
pub fn acs_stage<const S: usize, M: BranchMetric>(
    cur: &[u32; S],
    next: &mut [u32; S],
    survivors: &mut [u64],
    trellis: &Trellis<S>,
    received: &[M::Sample],
) -> u32 {
    let mut min = u32::MAX;
    for w in survivors.iter_mut() {
        *w = 0;
    }
    for state in 0..S {
        let [a, b] = trellis.preds[state];
        // `saturating_add` upholds the no-panic invariant (R11/S9) for the PUBLIC GENERIC API: a custom
        // `BranchMetric` that violates the documented branch-distance bound (see `BranchMetric`) could
        // otherwise overflow this addition. It is not masking a real bug — for `HardHamming` (and any
        // metric respecting the contract) the §4.3 subtract-min renormalization keeps every reachable
        // metric ≤ `METRIC_SPREAD_BOUND` ≪ u32::MAX, so saturation never triggers; the `debug_assert`
        // below still validates that real bound over reachable (non-sentinel) states. Unreachable
        // `SENTINEL` states (first K-1 stages) stay near u32::MAX/2 and are excluded from that check.
        let ca = cur[a.from].saturating_add(M::branch_distance(a.output, received));
        let cb = cur[b.from].saturating_add(M::branch_distance(b.output, received));
        // Tie-break compares the two predecessors by their STATE number (`.from`), NOT the slot index:
        // keep slot 0 (`a`) iff its metric is strictly lower, or (on a tie) `a.from <= b.from` — i.e.
        // always the LOWER-NUMBERED predecessor state (R17). Because the decision reads `.from` (not the
        // slot), it is independent of the order in which `Trellis::from_params` filled the predecessor
        // table: swapping the two predecessor slots yields the identical survivor. Fully deterministic.
        let (winner_metric, winner_slot) = if ca < cb || (ca == cb && a.from <= b.from) {
            (ca, 0u64)
        } else {
            (cb, 1u64)
        };
        next[state] = winner_metric;
        survivors[state / 64] |= winner_slot << (state % 64); // decision bit for this state
        if winner_metric < min {
            min = winner_metric;
        }
    }
    for m in next.iter_mut() {
        *m -= min;
    } // renormalize (lossless): the new minimum is 0
      // Contract guard (debug-only): validate the §4.3 bound using the *metric's own* `MAX_SPREAD`
      // (not a hard-coded value) — every reachable metric (< SENTINEL/2; still-sentinel states of the
      // first K-1 stages are excluded and never false-fail) must stay within it. A `BranchMetric` that
      // violates its declared bound trips this in debug; release is unaffected (ACS uses saturating_add).
    debug_assert!(
        next.iter()
            .filter(|&&m| m < SENTINEL / 2)
            .all(|&m| m <= M::MAX_SPREAD),
        "reachable-state metric spread exceeded the metric's declared MAX_SPREAD (§4.3)"
    );
    min
}

#[cfg(test)]
mod tests {
    use super::*;
    use crate::metric::HardHamming;
    use crate::params::CodeParams;
    use crate::trellis::Trellis;
    #[test]
    fn stage_selects_min_and_renormalizes_to_zero() {
        let t = Trellis::<64>::from_params(&CodeParams::ccsds_r1_2()).unwrap();
        let mut cur = [SENTINEL; 64];
        cur[0] = 0;
        let mut next = [0u32; 64];
        let mut surv = [0u64; 1]; // ⌈64/64⌉ = 1 word per stage
                                  // feed the exact expected symbol of the (state0,input0) branch → a zero-cost branch must exist
        let exp = t.forward[0][0].output;
        let recv = [((exp >> 1) & 1) as u8, (exp & 1) as u8];
        let min = acs_stage::<64, HardHamming>(&cur, &mut next, &mut surv, &t, &recv);
        assert_eq!(min, 0); // renorm subtracts the min
        assert_eq!(*next.iter().min().unwrap(), 0); // post-renorm min is 0
    }
}