comnum_fec/
crc.rs

1//! Cyclic redundancy checks.
2//!
3//! A CRC of degree $L$ appends the remainder of $D^{L} a(D)$ divided by the generator
4//! polynomial $g(D)$ to the information bits $a(D)$ (most significant bit first, zero
5//! initial state, no reflection, no final XOR — the convention of 3GPP TS 38.212,
6//! Sec. 5.1). The polynomials of 5G NR are provided.
7//!
8//! | Constructor | $g(D)$ | Use in NR |
9//! |---|---|---|
10//! | [`Crc::crc24a`] | `0x864CFB` | transport blocks |
11//! | [`Crc::crc24b`] | `0x800063` | code blocks |
12//! | [`Crc::crc24c`] | `0xB2B117` | downlink control (polar) |
13//! | [`Crc::crc16`] | `0x1021` | small transport blocks |
14//! | [`Crc::crc11`] | `0x621` | uplink control (polar) |
15//! | [`Crc::crc6`] | `0x21` | uplink control (polar) |
16//!
17//! # Examples
18//! ```
19//! use comnum_fec::crc::Crc;
20//! let crc = Crc::crc24a();
21//! let mut word = crc.attach(&[1, 0, 1, 1, 0, 0, 1]);
22//! assert_eq!(word.len(), 7 + 24);
23//! assert!(crc.check(&word));
24//! word[3] ^= 1;
25//! assert!(!crc.check(&word));
26//! ```
27//!
28//! # References
29//!
30//! 1. 3GPP TS 38.212, *NR; Multiplexing and channel coding*, Sec. 5.1.
31//! 2. W. W. Peterson and D. T. Brown, "Cyclic codes for error detection," *Proc. IRE*,
32//!    49(1), 228–235, 1961.
33
34use comnum_core::{Error, Result, ensure};
35use comnum_math::gf2::poly_rem;
36
37/// A cyclic redundancy check of degree `width` and generator `poly` (without its
38/// leading term), valid by construction ([`Crc::new`] checks them).
39#[derive(Clone, Debug, PartialEq, Eq)]
40pub struct Crc {
41    name: &'static str,
42    width: u32,
43    poly: u64,
44}
45
46impl Crc {
47    /// A CRC of degree `width` (1 to 64) and generator `poly` without its leading term.
48    ///
49    /// # Errors
50    /// [`Error::Config`] for a degree outside 1 to 64 or a generator with bits above it.
51    pub fn new(name: &'static str, width: u32, poly: u64) -> Result<Crc> {
52        ensure((1..=64).contains(&width), || format!("the CRC degree must be 1 to 64, got {width}"))?;
53        ensure(width == 64 || poly < (1u64 << width), || {
54            format!("the generator {poly:#x} exceeds the degree {width}")
55        })?;
56        Ok(Crc { name, width, poly })
57    }
58
59    /// Name of the CRC.
60    pub fn name(&self) -> &'static str {
61        self.name
62    }
63
64    /// Degree $L$.
65    pub fn width(&self) -> u32 {
66        self.width
67    }
68
69    /// Generator polynomial without its leading term $D^{L}$.
70    pub fn poly(&self) -> u64 {
71        self.poly
72    }
73
74    /// CRC24A of 5G NR.
75    pub fn crc24a() -> Crc {
76        Crc { name: "CRC24A", width: 24, poly: 0x86_4CFB }
77    }
78
79    /// CRC24B of 5G NR.
80    pub fn crc24b() -> Crc {
81        Crc { name: "CRC24B", width: 24, poly: 0x80_0063 }
82    }
83
84    /// CRC24C of 5G NR.
85    pub fn crc24c() -> Crc {
86        Crc { name: "CRC24C", width: 24, poly: 0xB2_B117 }
87    }
88
89    /// CRC16 of 5G NR and of LTE, $g_{\mathrm{CRC16}}(D) = D^{16} + D^{12} + D^{5} + 1$ (CCITT).
90    pub fn crc16() -> Crc {
91        Crc { name: "CRC16", width: 16, poly: 0x1021 }
92    }
93
94    /// CRC11 of 5G NR.
95    pub fn crc11() -> Crc {
96        Crc { name: "CRC11", width: 11, poly: 0x621 }
97    }
98
99    /// CRC6 of 5G NR.
100    pub fn crc6() -> Crc {
101        Crc { name: "CRC6", width: 6, poly: 0x21 }
102    }
103
104    /// A CRC of 5G NR by name: `crc24a`, `crc24b`, `crc24c`, `crc16`, `crc11` or `crc6`
105    /// (case-insensitive).
106    ///
107    /// # Errors
108    /// [`Error::Config`] for another name.
109    pub fn from_name(name: &str) -> Result<Crc> {
110        Ok(match name.to_ascii_lowercase().as_str() {
111            "crc24a" => Crc::crc24a(),
112            "crc24b" => Crc::crc24b(),
113            "crc24c" => Crc::crc24c(),
114            "crc16" => Crc::crc16(),
115            "crc11" => Crc::crc11(),
116            "crc6" => Crc::crc6(),
117            other => {
118                return Err(Error::Config(format!(
119                    "unknown CRC {other:?}: crc24a, crc24b, crc24c, crc16, crc11 or crc6"
120                )));
121            }
122        })
123    }
124
125    /// The $L$ parity bits of `bits`: the remainder of $b(D)\, D^{L}$ by the generator
126    /// ([`comnum_math::gf2::poly_rem`]).
127    pub fn checksum(&self, bits: &[u8]) -> Vec<u8> {
128        poly_rem(bits, &self.generator())
129    }
130
131    /// The generator $g(D)$, lowest degree first, $D^{L}$ included.
132    fn generator(&self) -> Vec<u8> {
133        (0..self.width).map(|i| ((self.poly >> i) & 1) as u8).chain([1]).collect()
134    }
135
136    /// `bits` followed by their parity bits.
137    pub fn attach(&self, bits: &[u8]) -> Vec<u8> {
138        let mut out = bits.to_vec();
139        out.extend(self.checksum(bits));
140        out
141    }
142
143    /// Whether a word (information then parity bits) passes the check.
144    pub fn check(&self, word: &[u8]) -> bool {
145        let w = self.width as usize;
146        word.len() >= w && self.checksum(&word[..word.len() - w]) == word[word.len() - w..]
147    }
148}
149
150#[cfg(test)]
151mod tests {
152    use super::*;
153
154    /// The 64-bit register that computed the checksum before `poly_rem`.
155    fn former_checksum(crc: &Crc, bits: &[u8]) -> Vec<u8> {
156        let top = 1u64 << (crc.width - 1);
157        let mask = (top << 1).wrapping_sub(1);
158        let mut reg = 0u64;
159        for &b in bits {
160            let fb = ((reg & top) != 0) ^ (b & 1 == 1);
161            reg = (reg << 1) & mask;
162            if fb {
163                reg ^= crc.poly;
164            }
165        }
166        (0..crc.width).rev().map(|i| ((reg >> i) & 1) as u8).collect()
167    }
168
169    #[test]
170    fn the_checksums_are_those_of_the_former_register() {
171        let mut rng = comnum_core::rng::Rng::new(9);
172        let mut crcs = vec![Crc::crc24a(), Crc::crc24b(), Crc::crc24c(), Crc::crc16(), Crc::crc11(), Crc::crc6()];
173        crcs.extend([Crc::new("one", 1, 1).unwrap(), Crc::new("wide", 64, 0x1B).unwrap()]);
174        for crc in &crcs {
175            for len in [0, 1, 12, 300] {
176                let bits: Vec<u8> = (0..len).map(|_| rng.bit()).collect();
177                assert_eq!(crc.checksum(&bits), former_checksum(crc, &bits), "{} on {len} bits", crc.name);
178            }
179        }
180    }
181
182    #[test]
183    fn the_remainder_of_a_codeword_is_zero_and_every_single_error_is_detected() {
184        for crc in [Crc::crc24a(), Crc::crc24b(), Crc::crc24c(), Crc::crc16(), Crc::crc11(), Crc::crc6()] {
185            let word = crc.attach(&[1, 1, 0, 1, 0, 0, 1, 0, 1, 1, 1, 0]);
186            // a codeword is divisible by g(D): its own checksum is zero
187            assert!(crc.checksum(&word).iter().all(|b| *b == 0), "{}", crc.name);
188            for i in 0..word.len() {
189                let mut e = word.clone();
190                e[i] ^= 1;
191                assert!(!crc.check(&e), "{} misses an error at {i}", crc.name);
192            }
193        }
194        // CRC-16/CCITT ("XMODEM" convention: zero init) of the ASCII "123456789" is 0x31C3
195        let msg: Vec<u8> = b"123456789".iter().flat_map(|c| (0..8).rev().map(move |i| (c >> i) & 1)).collect();
196        let v = Crc::crc16().checksum(&msg).iter().fold(0u32, |a, b| (a << 1) | u32::from(*b));
197        assert_eq!(v, 0x31C3);
198        // the degrees 1 and 64 are valid
199        for w in [1, 64] {
200            let c = Crc::new("edge", w, 1).unwrap();
201            assert!(c.check(&c.attach(&[1, 0, 1])));
202        }
203        assert!(Crc::new("bad", 65, 1).is_err() && Crc::new("bad", 4, 16).is_err());
204        assert_eq!(Crc::from_name("CRC24A").unwrap(), Crc::crc24a());
205    }
206}
207
208/// Checks against the published tables (`references/`).
209#[cfg(test)]
210mod literature {
211    use super::*;
212
213    /// 3GPP TS 38.212 V18.5.0, Sec. 5.1 (p. 11): the generator polynomials of the six
214    /// CRCs of NR, written by their exponents.
215    #[test]
216    fn ts_38_212_sec_5_1_generator_polynomials() {
217        let exponents = |crc: &Crc| -> Vec<u32> {
218            let mut e: Vec<u32> = (0..crc.width).filter(|i| (crc.poly >> i) & 1 == 1).collect();
219            e.push(crc.width);
220            e.sort_unstable_by(|a, b| b.cmp(a));
221            e
222        };
223        assert_eq!(exponents(&Crc::crc24a()), [24, 23, 18, 17, 14, 11, 10, 7, 6, 5, 4, 3, 1, 0]);
224        assert_eq!(exponents(&Crc::crc24b()), [24, 23, 6, 5, 1, 0]);
225        assert_eq!(exponents(&Crc::crc24c()), [24, 23, 21, 20, 17, 15, 13, 12, 8, 4, 2, 1, 0]);
226        assert_eq!(exponents(&Crc::crc16()), [16, 12, 5, 0]);
227        assert_eq!(exponents(&Crc::crc11()), [11, 10, 9, 5, 0]);
228        assert_eq!(exponents(&Crc::crc6()), [6, 5, 0]);
229    }
230}
comnum_fec/crc.rs

comnum_fec/
crc.rs
