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

// Author: BolivarTech
// Version: 1.0.0
// Date: 2026-07-02
//! Full-block traceback from the known terminal state 0 (R2, R3).
use crate::trellis::Trellis;

/// Walk `nstages` survivor words backwards from state 0, writing the input bits (oldest first,
/// tail bits included) into the reused `out` buffer. Bounds-safe; performs **no allocation**
/// when `out` was preallocated to `nstages` capacity.
pub fn traceback<const S: usize>(
    trellis: &Trellis<S>,
    survivors: &[u64],
    nstages: usize,
    out: &mut Vec<u8>,
) {
    let wps = S.div_ceil(64); // decision words per stage (scales with S; = 1 for S ≤ 64)
    out.clear();
    let mut state = 0usize; // terminal state guaranteed by zero-tail (R2)
    for stage in (0..nstages).rev() {
        let word = survivors[stage * wps + state / 64];
        let slot = ((word >> (state % 64)) & 1) as usize; // which predecessor survived
        let branch = trellis.preds[state][slot];
        out.push(branch.input);
        state = branch.from;
    }
    out.reverse();
}

#[cfg(test)]
mod tests {
    use super::*;
    use crate::params::CodeParams;
    use crate::trellis::Trellis;
    #[test]
    fn traceback_from_state0_reconstructs_inputs() {
        let t = Trellis::<64>::from_params(&CodeParams::ccsds_r1_2()).unwrap();
        // Construct survivors so that at every stage state 0's surviving predecessor is slot 0
        // (the predecessor reached by input 0), i.e. an all-zero input path ending at state 0.
        let survivors = vec![0u64; 8]; // all decision bits 0 → slot-0 predecessor everywhere
        let mut inputs = Vec::with_capacity(8);
        traceback::<64>(&t, &survivors, 8, &mut inputs);
        assert_eq!(inputs.len(), 8);
        assert!(inputs.iter().all(|&b| b == 0)); // the all-zero path yields all-zero inputs
    }
}