code_rs/coding/
hamming.rs

1//! Encoding and decoding of the (15, 11, 3) standard and (10, 6, 3) shortened Hamming
2//! codes described by P25.
3//!
4//! Both codes can correct up to 1 error. These algorithms are sourced from *Coding Theory
5//! and Cryptography: The Essentials*, Hankerson, Hoffman, et al, 2000.
6
7use binfield_matrix::{matrix_mul, matrix_mul_systematic};
8use num_traits::PrimInt;
9
10/// Encoding and decoding of the (15, 11, 3) code.
11pub mod standard {
12    use super::*;
13
14    /// Encode the given 11 bits of data into a 15-bit codeword.
15    pub fn encode(data: u16) -> u16 {
16        assert!(data >> 11 == 0);
17        matrix_mul_systematic(data, GEN)
18    }
19
20    /// Try to decode the given 15-bit word to the nearest codeword, correcting up to 1
21    /// error.
22    ///
23    /// If decoding was successful, return `Some((data, err))`, where `data` is the 11
24    /// data bits and `err` is the number of corrected bits. Otherwise, return `None` to
25    /// indicate an unrecoverable error.
26    pub fn decode(word: u16) -> Option<(u16, usize)> {
27        assert!(word >> 15 == 0);
28        super::decode(word, PAR, LOCATIONS).map(|(w, n)| (w >> 4, n))
29    }
30
31    /// Generator matrix from the standard, without identity part.
32    const GEN: &[u16] = &[0b11111110000, 0b11110001110, 0b11001101101, 0b10101011011];
33
34    /// Parity-check matrix derived from generator using standard method.
35    const PAR: &[u16] = &[
36        0b111111100001000,
37        0b111100011100100,
38        0b110011011010010,
39        0b101010110110001,
40    ];
41
42    /// Maps 4-bit syndrome values to bit error locations.
43    const LOCATIONS: &[u16] = &[
44        0,
45        0b0000000000000001,
46        0b0000000000000010,
47        0b0000000000010000,
48        0b0000000000000100,
49        0b0000000000100000,
50        0b0000000001000000,
51        0b0000000010000000,
52        0b0000000000001000,
53        0b0000000100000000,
54        0b0000001000000000,
55        0b0000010000000000,
56        0b0000100000000000,
57        0b0001000000000000,
58        0b0010000000000000,
59        0b0100000000000000,
60    ];
61}
62
63/// Encoding and decoding of the (10, 6, 3) code.
64pub mod shortened {
65    use super::*;
66
67    /// Encode the given 6 data bits into a 10-bit codeword.
68    pub fn encode(data: u8) -> u16 {
69        assert!(data >> 6 == 0);
70        matrix_mul_systematic(data, GEN)
71    }
72
73    /// Try to decode the given 10-bit word to the nearest codeword, correcting up to 1
74    /// error.
75    ///
76    /// If decoding was successful, return `Some((data, err))`, where `data` is the 6
77    /// data bits and `err` is the number of corrected bits. Otherwise, return `None` to
78    /// indicate an unrecoverable error.
79    pub fn decode(word: u16) -> Option<(u8, usize)> {
80        assert!(word >> 10 == 0);
81        super::decode(word, PAR, LOCATIONS).map(|(w, n)| ((w >> 4) as u8, n))
82    }
83
84    const GEN: &[u8] = &[0b111001, 0b110101, 0b101110, 0b011110];
85
86    const PAR: &[u16] = &[0b1110011000, 0b1101010100, 0b1011100010, 0b0111100001];
87
88    const LOCATIONS: &[u16] = &[
89        0,
90        0b0000000000000001,
91        0b0000000000000010,
92        0b0000000000100000,
93        0b0000000000000100,
94        0,
95        0,
96        0b0000000001000000,
97        0b0000000000001000,
98        0,
99        0,
100        0b0000000010000000,
101        0b0000000000010000,
102        0b0000000100000000,
103        0b0000001000000000,
104        0,
105    ];
106}
107
108fn decode<T: PrimInt>(word: T, par: &[T], locs: &[T]) -> Option<(T, usize)> {
109    let s: usize = matrix_mul(word, par);
110
111    if s == 0 {
112        return Some((word, 0));
113    }
114
115    locs.get(s).and_then(|&loc| {
116        if loc == T::zero() {
117            None
118        } else {
119            Some((word ^ loc, 1))
120        }
121    })
122}
123
124#[cfg(test)]
125mod test {
126    use super::*;
127
128    #[test]
129    fn test_standard() {
130        assert_eq!(standard::encode(0), 0);
131        assert_eq!(standard::encode(0b11111111111), 0b11111111111_1111);
132
133        for w in 0..1 << 11 {
134            assert_eq!(standard::decode(standard::encode(w)), Some((w, 0)));
135        }
136
137        let w = standard::encode(0b10101010101);
138        assert_eq!(w, 0b10101010101_0101);
139        assert_eq!(standard::decode(w), Some((0b10101010101, 0)));
140
141        for i in 0..15 {
142            assert_eq!(standard::decode(w ^ 1 << i), Some((0b10101010101, 1)));
143        }
144
145        for (i, j) in (0..15).zip(0..15) {
146            if i != j {
147                // Two-bit errors are detected as one-bit errors with an incorrect bit
148                // correction, so just check for the detection.
149                let (_, n) = standard::decode(w ^ (1 << i) ^ (1 << j)).unwrap();
150                assert_eq!(n, 1);
151            }
152        }
153    }
154
155    #[test]
156    fn test_shortened() {
157        assert_eq!(shortened::encode(0), 0);
158        assert_eq!(shortened::encode(0b111111), 0b111111_0000);
159
160        for w in 0..1 << 6 {
161            assert_eq!(shortened::decode(shortened::encode(w)), Some((w, 0)));
162        }
163
164        let w = shortened::encode(0b101010);
165        assert_eq!(w, 0b101010_0110);
166        assert_eq!(shortened::decode(w), Some((0b101010, 0)));
167
168        for i in 0..10 {
169            assert_eq!(shortened::decode(w ^ 1 << i), Some((0b101010, 1)));
170        }
171
172        for (i, j) in (0..10).zip(0..10) {
173            if i != j {
174                // Two-bit errors are detected as one-bit errors with an incorrect bit
175                // correction, so just check for the detection.
176                let (_, n) = shortened::decode(w ^ (1 << i) ^ (1 << j)).unwrap();
177                assert_eq!(n, 1);
178            }
179        }
180    }
181}
code_rs/coding/hamming.rs

code_rs/coding/
hamming.rs
