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
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132

//! Vector-matrix multiplication for [GF(2)](http://mathworld.wolfram.com/FiniteField.html)
//! binary field error correction codes.
//!
//! These routines calculate the multiplication **vM**<sup>T</sup> = **Mv**<sup>T</sup> of
//! a 1×M binary vector **v** with an N×M binary matrix **M**, using GF(2) addition and
//! multiplication. The input vector, output vector, and matrix columns are represented as
//! binary words, so the maximum vector size is determined by the maximum machine word
//! size.
//!
//! ## Example
//!
//! The following examples mutiply the codeword `1010` by the matrix
//!
//! ```text
//! 1 1 1 1
//! 0 0 1 0
//! 1 0 0 0
//! 0 1 0 1
//! 0 0 1 0
//! 1 0 1 0
//! ```
//!
//! The first example computes only the parity bits, and the second example computes the
//! "systematic" codeword, which appends the parity bits to the original codeword.
//!
//! ```rust
//! use binfield_matrix::{matrix_mul, matrix_mul_systematic};
//!
//! assert_eq!(matrix_mul::<u32, u32>(0b1010, &[
//!     0b1111,
//!     0b0010,
//!     0b1000,
//!     0b0101,
//!     0b0010,
//!     0b1010,
//! ]), 0b011010);
//!
//! assert_eq!(matrix_mul_systematic::<u32, u32>(0b1010, &[
//!     0b1111,
//!     0b0010,
//!     0b1000,
//!     0b0101,
//!     0b0010,
//!     0b1010,
//! ]), 0b1010011010);
//! ```

extern crate num_traits;

use num_traits::PrimInt;

/// Compute **vM**<sup>T</sup>, where **v** is the given word and **M** is the given
/// matrix.
pub fn matrix_mul<I, O>(word: I, mat: &[I]) -> O where
    I: PrimInt,
    O: PrimInt + From<u8>,
{
    accum_rows(word, O::zero(), mat)
}

/// Compute [ **v** | **vM**<sup>T</sup> ], where **v** is the given word and **M** is the
/// given matrix.
pub fn matrix_mul_systematic<I, O>(word: I, mat: &[I]) -> O where
    I: PrimInt + Into<O>,
    O: PrimInt + From<u8>,
{
    accum_rows(word, word.into(), mat)
}

/// Starting with the given initial accumulator, compute the GF(2) dot product of the
/// given word with each row in the given matrix, shifting each resulting bit into the LSB
/// of the accumulator.
///
/// This effectively computes the vector-matrix multiplication.
fn accum_rows<I, O>(word: I, init: O, mat: &[I]) -> O where
    I: PrimInt,
    O: PrimInt + From<u8>,
{
    mat.iter().fold(init, |accum, &row| {
        let bit = ((word & row).count_ones() & 1) as u8;
        accum << 1 | bit.into()
    })
}

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

    #[test]
    fn test_mul() {
        let w: u16 = matrix_mul(0b0110011, &[
            0b1010101,
            0b0110011,
            0b0001111,
        ]);
        assert_eq!(w, 0b000);

        let w: u16 = matrix_mul(0b0110111, &[
            0b1010101,
            0b0110011,
            0b0001111,
        ]);
        assert_eq!(w, 0b101);
    }

    #[test]
    fn test_mul_sys() {
        let w: u16 = matrix_mul_systematic(0u16, &[
            0b11111110000,
            0b11110001110,
            0b11001101101,
            0b10101011011,
        ]);
        assert_eq!(w, 0);

        let w: u16 = matrix_mul_systematic(0b11111111111u16, &[
            0b11111110000,
            0b11110001110,
            0b11001101101,
            0b10101011011,
        ]);
        assert_eq!(w, 0b11111111111_1111);

        let w: u16 = matrix_mul_systematic(0b11111111101u16, &[
            0b11111110000,
            0b11110001110,
            0b11001101101,
            0b10101011011,
        ]);
        assert_eq!(w, 0b11111111101_1010);
    }
}