viterbi 0.0.1

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

// Author: BolivarTech
// Version: 1.0.0
// Date: 2026-07-02
//! Branch-metric abstraction: hard-decision Hamming now, soft/erasure-ready (R7).

/// Sentinel `Sample` for [`HardHamming`] meaning "erased" (contributes zero).
pub const HARD_ERASURE: u8 = 0xFF;

/// Cost model for a trellis branch, generic over the received sample type.
///
/// # Contract (bounded branch distance)
/// `branch_distance` MUST return a per-stage cost small enough that, combined with the decoder's
/// per-stage subtract-min renormalization (which keeps the *spread* of state metrics bounded), the
/// accumulated `u32` state metric never exceeds `u32::MAX`. Concretely a bound on the order of a few
/// times `N` per stage is expected — [`HardHamming`] returns at most `N` (one per output bit). The
/// decoder guards its ACS additions with `saturating_add`, so a metric that *violates* this bound
/// **degrades to an incorrect (saturated) result rather than panicking** — the no-panic invariant
/// (R11/S9) always holds — but *correct* decoding requires implementations to respect the bound.
pub trait BranchMetric {
    /// The per-output-bit received sample type.
    type Sample: Copy;
    /// Upper bound on the post-renormalization spread of *reachable* state metrics this metric can
    /// produce (`max reachable metric` after each stage's subtract-min). The decoder `debug_assert!`s
    /// reachable metrics stay `<= MAX_SPREAD`, so the bound is a property of the metric, not hard-coded
    /// in the generic ACS. For [`HardHamming`] it is a conservative value for the CCSDS K=7 profile.
    const MAX_SPREAD: u32;
    /// Cost of a branch whose expected N-bit `expected` symbol (C1 in the high bit) meets `received`.
    /// See the trait-level contract: the returned value must be bounded (see [`BranchMetric`]).
    fn branch_distance(expected: u32, received: &[Self::Sample]) -> u32;
    /// A neutral "erasure" sample that contributes zero to any branch distance.
    fn erasure() -> Self::Sample;
}

/// Hard-decision Hamming metric. `Sample = u8`: `0`/`1` are bits, [`HARD_ERASURE`] (`0xFF`) is an erasure
/// (contributes zero). Any other value is interpreted by its least-significant bit (`s & 1`); the
/// on-air `decode_block` path only ever produces `0`/`1`, so this matters only for the raw `decode` API.
/// Distance per stage is at most `N`, satisfying the [`BranchMetric`] bound contract.
pub struct HardHamming;
impl BranchMetric for HardHamming {
    type Sample = u8;
    /// Conservative bound for the CCSDS K=7 profile — the true post-renorm spread is ~`(K-1)·N`; this
    /// loose value only needs to exceed it to catch an overflow/renorm bug in debug builds.
    const MAX_SPREAD: u32 = 256;
    fn branch_distance(expected: u32, received: &[Self::Sample]) -> u32 {
        let n = received.len();
        let mut d: u32 = 0;
        for (j, &s) in received.iter().enumerate() {
            if s == HARD_ERASURE {
                continue;
            }
            // `expected` holds `n` output bits (C1 in the high bit). Guard the shift so a caller passing a
            // slice longer than 32 samples (never happens on the N=2 decode path) can't overflow-shift a
            // `u32`: positions at/above bit 32 hold no expected bit, so treat them as 0. No panic (R11).
            let shift = n - 1 - j;
            let exp_bit = if shift < 32 {
                ((expected >> shift) & 1) as u8
            } else {
                0
            };
            if exp_bit != (s & 1) {
                d = d.saturating_add(1); // saturating for consistency (d ≤ received.len(), never overflows here)
            }
        }
        d
    }
    fn erasure() -> u8 {
        HARD_ERASURE
    }
}

#[cfg(test)]
mod tests {
    use super::*;
    #[test]
    fn hamming_counts_bit_mismatches() {
        // expected symbol 0b10 (C1=1,C2=0), received [1,0] → distance 0; received [0,0] → 1; [0,1] → 2
        assert_eq!(HardHamming::branch_distance(0b10, &[1, 0]), 0);
        assert_eq!(HardHamming::branch_distance(0b10, &[0, 0]), 1);
        assert_eq!(HardHamming::branch_distance(0b10, &[0, 1]), 2);
    }
    #[test]
    fn erasure_sample_is_free() {
        assert_eq!(HardHamming::erasure(), 0xFF);
        assert_eq!(HardHamming::branch_distance(0b11, &[0xFF, 0xFF]), 0);
        assert_eq!(HardHamming::branch_distance(0b11, &[0xFF, 0]), 1); // one real mismatch
    }
}