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
133

#![feature(use_extern_macros)]
#![allow(non_camel_case_types)]
#[macro_use] extern crate finite_fields;
extern crate daggy;
extern crate rand;

finite_fields::binary_type! { b3, 3 }

/// Descriptor for code types.
pub enum CodeType {
  FIRCode,
  IIRCode
}

/// A description of a binary convolutional code, either nonrecursive (FIR), or
/// recursive (IIR), including start state.
pub struct Code {
  /// The starting state of the registers.
  pub start_state: Vec<b1>, // TODO make n-1 width type (see issue)
  /// Storage of the binary polynomial coefficients. Each polynomial corresponds
  /// to an output bit in the order in which they are stored.
  ///
  /// Coefficients are defined in order of increasing delay, e.g. `polys[0][0]`
  /// is applied to `signal[n]`, and `coefs[1]` is applied to `signal[n-1]`, and
  /// so on.
  pub polys: Vec<b3>, // TODO make static length array
  /// Enum describing the type of the code (FIR or IIR).
  pub code_type: CodeType
}

impl Code {
  /// Computes the adjacency matrix of states the code passes through. The
  /// output is a matrix indexed by `[start_index][destination_index]`, with a
  /// unit binary digit in each position (`1` if there is an edge, `0` if there
  /// is not).
  ///
  /// This turns out to be easy for an FIR encoder, because the transitions can
  /// be expressed solely as "pushes" onto an array of previous states that only
  /// differ by the next input bit. For example, for a 3-digit state register,
  /// the adjacency matrix looks like this:
  ///
  /// ```text
  /// 1 1 0 0 0 0 0 0
  /// 0 0 1 1 0 0 0 0
  /// 0 0 0 0 1 1 0 0
  /// 0 0 0 0 0 0 1 1
  /// 1 1 0 0 0 0 0 0
  /// 0 0 1 1 0 0 0 0
  /// 0 0 0 0 1 1 0 0
  /// 0 0 0 0 0 0 1 1
  /// ```
  ///
  /// # Examples
  ///
  /// ```
  /// use turbo::{Code, CodeType, b3, ONE, ZERO};
  ///
  /// let toy_code = Code {
  ///   start_state: vec![ZERO, ZERO],
  ///   polys: vec![b3::new([ZERO, ZERO, ONE]),
  ///               b3::new([ONE, ONE, ZERO])],
  ///   code_type: CodeType::FIRCode
  /// };
  ///
  /// assert_eq!(toy_code.state_adjacency(),
  ///            vec![vec![ONE, ONE, ZERO, ZERO],
  ///                 vec![ZERO, ZERO, ONE, ONE],
  ///                 vec![ONE, ONE, ZERO, ZERO],
  ///                 vec![ZERO, ZERO, ONE, ONE]]);
  /// ```
  pub fn state_adjacency(&self) -> Vec<Vec<b1>> {
    match self.code_type {
      CodeType::FIRCode => {
        // The dimension of the (square) adjacency matrix.
        let state_dim = 2usize.pow(self.start_state.len() as u32);

        (0..state_dim).map(|col_ind| {
          zero_padded_vec(state_dim, vec![ONE, ONE], col_ind * 2)
        }).collect()
      },
      CodeType::IIRCode => vec![vec![ZERO]] // FIXME placeholder
    }
  }

  /// Computes the next states indices reachable given an index corresponding to
  /// an existing state index (numbered in monotonic ascending order).
  ///
  ///
  /// # Examples
  ///
  /// ```
  /// use turbo::{Code, CodeType, b3, ONE, ZERO};
  ///
  /// let toy_code = Code {
  ///   start_state: vec![ZERO, ZERO],
  ///   polys: vec![b3::new([ZERO, ZERO, ONE]),
  ///               b3::new([ONE, ONE, ZERO])],
  ///   code_type: CodeType::FIRCode
  /// };
  ///
  /// assert_eq!(toy_code.next_states(0),
  ///            vec![0, 1]);
  /// assert_eq!(toy_code.next_states(1),
  ///            vec![2, 3]);
  /// assert_eq!(toy_code.next_states(2),
  ///            vec![0, 1]);
  /// assert_eq!(toy_code.next_states(3),
  ///            vec![2, 3]);
  /// ```
  pub fn next_states(&self, state_ind: usize) -> Vec<usize> {
    match self.code_type {
      CodeType::FIRCode => {
        let state_count = 2usize.pow(self.start_state.len() as u32);
        let first_next = (state_ind * 2) % state_count; // 2 here is arity
        vec![first_next, &first_next + 1]
      }, // TODO do more than binary
      CodeType::IIRCode => vec![0] // FIXME placeholder
    }
  }
}

pub mod encoders;
pub mod viterbi;
// pub mod bcjr;

fn zero_padded_vec(vec_len: usize, vals: Vec<b1>, offset: usize) -> Vec<b1> {
  let mut out_vec = vec![ZERO; offset % vec_len];

  for val in vals { out_vec.push(val); }
  for _ in 0..(vec_len - out_vec.len()) { out_vec.push(ZERO); }

  out_vec
}