comnum_math/
bits.rs

1//! Integers as bit strings: the reflected binary Gray code and the conversions between
2//! an index and its bits, most significant bit first.
3//!
4//! # Model
5//!
6//! The binary reflected Gray code of $i$ and its inverse are
7//!
8//! $$
9//! g(i) = i \oplus \lfloor i / 2 \rfloor, \qquad
10//! g^{-1}(g) = \bigoplus_{k \ge 0} \left\lfloor g / 2^{k} \right\rfloor,
11//! $$
12//!
13//! so that $g(i)$ and $g(i + 1)$ differ in one bit. An index $i$ of $n$ bits is written
14//! $b_{0} b_{1} \dots b_{n-1}$ with $i = \sum_{k=0}^{n-1} b_{k} 2^{n-1-k}$ (the most
15//! significant bit first, the order of the labels of every constellation and of the
16//! symbols of every code of comnum).
17//!
18//! # Examples
19//! ```
20//! use comnum_math::{bits_to_index, gray, gray_inverse, index_to_bits};
21//! assert_eq!(gray(5), 7);                                   // 101 → 111
22//! assert_eq!(gray_inverse(7), 5);
23//! assert_eq!(bits_to_index(&[1, 0, 1, 1]), 11);
24//! assert_eq!(index_to_bits(11, 4).collect::<Vec<u8>>(), [1, 0, 1, 1]);
25//! ```
26
27use comnum_core::{Error, Result};
28
29/// The binary reflected Gray code $g(i) = i \oplus \lfloor i/2 \rfloor$.
30///
31/// # Examples
32/// ```
33/// use comnum_math::gray;
34/// assert_eq!((0..8).map(gray).collect::<Vec<_>>(), [0, 1, 3, 2, 6, 7, 5, 4]);
35/// ```
36#[inline]
37pub fn gray(i: usize) -> usize {
38    i ^ (i >> 1)
39}
40
41/// The inverse of [`gray`]: $g^{-1}(g) = \bigoplus_{k \ge 0} \lfloor g / 2^{k} \rfloor$.
42///
43/// # Examples
44/// ```
45/// use comnum_math::{gray, gray_inverse};
46/// assert!((0..1024).all(|i| gray_inverse(gray(i)) == i));
47/// ```
48#[inline]
49pub fn gray_inverse(mut g: usize) -> usize {
50    let mut i = 0;
51    while g > 0 {
52        i ^= g;
53        g >>= 1;
54    }
55    i
56}
57
58/// The index $i = \sum_{k} b_{k} 2^{n-1-k}$ of the bits $b_{0} \dots b_{n-1}$, the most
59/// significant first (only the lowest bit of every value is read).
60///
61/// # Examples
62/// ```
63/// use comnum_math::bits_to_index;
64/// assert_eq!(bits_to_index(&[1, 1, 0]), 6);
65/// assert_eq!(bits_to_index(&[]), 0);
66/// ```
67#[inline]
68pub fn bits_to_index(bits: &[u8]) -> usize {
69    bits.iter().fold(0usize, |acc, &b| (acc << 1) | usize::from(b & 1))
70}
71
72/// The `n_bits` bits of `index`, the most significant first (the bits above $2^{n}$
73/// are dropped).
74///
75/// # Examples
76/// ```
77/// use comnum_math::index_to_bits;
78/// assert_eq!(index_to_bits(6, 3).collect::<Vec<u8>>(), [1, 1, 0]);
79/// assert_eq!(index_to_bits(6, 2).collect::<Vec<u8>>(), [1, 0]);
80/// ```
81#[inline]
82pub fn index_to_bits(index: usize, n_bits: usize) -> impl Iterator<Item = u8> {
83    (0..n_bits).rev().map(move |k| ((index >> k) & 1) as u8)
84}
85
86/// The indices of the blocks of `n_bits` bits of `bits`, each the [`bits_to_index`] of
87/// its block (the labels of the symbols of a bit stream, the symbols of a code over
88/// $\mathrm{GF}(2^{m})$).
89///
90/// # Errors
91/// [`Error::Config`] for `n_bits = 0`, [`Error::Shape`] if the number of bits is not a
92/// multiple of `n_bits`.
93///
94/// # Examples
95/// ```
96/// use comnum_math::bits::bits_to_indices;
97/// assert_eq!(bits_to_indices(&[1, 0, 1, 1, 1, 0], 3)?, [5, 6]);
98/// assert!(bits_to_indices(&[1, 0, 1], 2).is_err());
99/// # Ok::<(), comnum_core::Error>(())
100/// ```
101pub fn bits_to_indices(bits: &[u8], n_bits: usize) -> Result<Vec<usize>> {
102    if n_bits == 0 {
103        return Err(Error::Config("a symbol needs at least one bit".into()));
104    }
105    if bits.len() % n_bits != 0 {
106        return Err(Error::Shape(format!("{} bits is not a multiple of {n_bits} bits per symbol", bits.len())));
107    }
108    Ok(bits.chunks(n_bits).map(bits_to_index).collect())
109}
110
111#[cfg(test)]
112mod tests {
113    use super::*;
114
115    #[test]
116    fn gray_neighbours_differ_by_one_bit_and_the_conversions_invert() {
117        for i in 0..256 {
118            assert_eq!(gray_inverse(gray(i)), i);
119            assert_eq!((gray(i) ^ gray(i + 1)).count_ones(), 1);
120            let bits: Vec<u8> = index_to_bits(i, 8).collect();
121            assert_eq!(bits_to_index(&bits), i);
122        }
123    }
124}
comnum_math/bits.rs

comnum_math/
bits.rs
