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

//! Decoding of Hamming codes for common air interfaces
//!
//! This algorithm is sourced from *Coding Theory and Cryptography: The Essentials*,
//! Hankerson, Hoffman, et al, 2000.

extern crate binfield_matrix;
extern crate num_traits;

use binfield_matrix::matrix_mul;
use num_traits::PrimInt;

/// Decode the given N-bit word to the nearest codeword using the given M×N parity-check
/// matrix and 2<sup>M</sup>×N error location lookup table, correcting up to one bit
/// error.
///
/// The word should be in systematic form, with k data bits in the MSB followed by N-k
/// parity bits in the LSB.
///
/// On success, return `Some((word, err))`, where `word` is the decoded N-bit codeword and
/// `err` is the number of corrected errors. Otherwise, return `None` if the word was
/// detected to be unrecoverable.
pub fn decode<T: PrimInt>(word: T, par: &[T], locs: &[T]) -> Option<(T, usize)> {
    // Compute syndrome.
    let s: usize = matrix_mul(word, par);

    if s == 0 {
        return Some((word, 0));
    }

    locs.get(s).and_then(|&loc| if loc == T::zero() {
        None
    } else {
        Some((word ^ loc, 1))
    })
}

#[cfg(test)]
mod test {
    use super::*;

    const PAR: &[u16] = &[
        0b1110011000,
        0b1101010100,
        0b1011100010,
        0b0111100001,
    ];

    const LOCS: &[u16] = &[
        0,
        0b0000000000000001,
        0b0000000000000010,
        0b0000000000100000,
        0b0000000000000100,
        0,
        0,
        0b0000000001000000,
        0b0000000000001000,
        0,
        0,
        0b0000000010000000,
        0b0000000000010000,
        0b0000000100000000,
        0b0000001000000000,
        0,
    ];

    #[test]
    fn test_decode() {
        let w = 0b101010_0110;

        assert_eq!(decode(w, PAR, LOCS), Some((0b101010_0110, 0)));

        for i in 0..10 {
            assert_eq!(decode(w ^ 1 << i, PAR, LOCS), Some((0b101010_0110, 1)));
        }

        for (i, j) in (0..10).zip(0..10) {
            if i != j {
                // Two-bit errors are detected as one-bit errors with an incorrect bit
                // correction, so just check for the detection.
                let (_, n) = decode(w ^ (1 << i) ^ (1 << j), PAR, LOCS).unwrap();
                assert_eq!(n, 1);
            }
        }
    }
}