GNU Radio's SATELLITES Package
viterbi/viterbi.h
Go to the documentation of this file.
1 // Viterbi Codec.
2 //
3 // Author: Min Xu <xukmin@gmail.com>
4 // Date: 01/30/2015
5 
6 #ifndef VITERBI_H_
7 #define VITERBI_H_
8 
9 #include <ostream>
10 #include <string>
11 #include <utility>
12 #include <vector>
13 
14 // This class implements both a Viterbi Decoder and a Convolutional Encoder.
16 {
17 public:
18  // Note about Polynomial Descriptor of a Convolutional Encoder / Decoder.
19  // A generator polymonial is built as follows: Build a binary number
20  // representation by placing a 1 in each spot where a connection line from
21  // the shift register feeds into the adder, and a zero elsewhere. There are 2
22  // ways to arrange the bits:
23  // 1. msb-current
24  // The MSB of the polynomial corresponds to the current input, while the
25  // LSB corresponds to the oldest input that still remains in the shift
26  // register.
27  // This representation is used by MATLAB. See
28  // http://radio.feld.cvut.cz/matlab/toolbox/comm/tutor124.html
29  // 2. lsb-current
30  // The LSB of the polynomial corresponds to the current input, while the
31  // MSB corresponds to the oldest input that still remains in the shift
32  // register.
33  // This representation is used by the Spiral Viterbi Decoder Software
34  // Generator. See http://www.spiral.net/software/viterbi.html
35  // We use 2.
36  ViterbiCodec(int constraint, const std::vector<int>& polynomials);
37 
38  std::string Encode(const std::string& bits) const;
39 
40  std::string Decode(const std::string& bits) const;
41 
42  int constraint() const { return constraint_; }
43 
44  const std::vector<int>& polynomials() const { return polynomials_; }
45 
46 private:
47  // Suppose
48  //
49  // Trellis trellis;
50  //
51  // Then trellis[i][s] is the state in the (i - 1)th iteration which leads to
52  // the current state s in the ith iteration.
53  // It is used for traceback.
54  typedef std::vector<std::vector<int>> Trellis;
55 
56  int num_parity_bits() const;
57 
58  void InitializeOutputs();
59 
60  int NextState(int current_state, int input) const;
61 
62  std::string Output(int current_state, int input) const;
63 
64  int BranchMetric(const std::string& bits, int source_state, int target_state) const;
65 
66  // Given num_parity_bits() received bits, compute and returns path
67  // metric and its corresponding previous state.
68  std::pair<int, int> PathMetric(const std::string& bits,
69  const std::vector<int>& prev_path_metrics,
70  int state) const;
71 
72  // Given num_parity_bits() received bits, update path metrics of all states
73  // in the current iteration, and append new traceback vector to trellis.
74  void UpdatePathMetrics(const std::string& bits,
75  std::vector<int>* path_metrics,
76  Trellis* trellis) const;
77 
78  const int constraint_;
79  const std::vector<int> polynomials_;
80 
81  // The output table.
82  // The index is current input bit combined with previous inputs in the shift
83  // register. The value is the output parity bits in string format for
84  // convenience, e.g. "10". For example, suppose the shift register contains
85  // 0b10 (= 2), and the current input is 0b1 (= 1), then the index is 0b110 (=
86  // 6).
87  std::vector<std::string> outputs_;
88 };
89 
90 std::ostream& operator<<(std::ostream& os, const ViterbiCodec& codec);
91 
92 int ReverseBits(int num_bits, int input);
93 
94 #endif // VITERBI_H_
Definition: viterbi/viterbi.h:16
std::string Decode(const std::string &bits) const
int constraint() const
Definition: viterbi/viterbi.h:42
const std::vector< int > & polynomials() const
Definition: viterbi/viterbi.h:44
std::string Encode(const std::string &bits) const
ViterbiCodec(int constraint, const std::vector< int > &polynomials)
int ReverseBits(int num_bits, int input)
std::ostream & operator<<(std::ostream &os, const ViterbiCodec &codec)