GNU Radio's GSM Package
ViterbiR204.h
Go to the documentation of this file.
1 /*
2 * Copyright 2008, 2009, 2014 Free Software Foundation, Inc.
3 * Copyright 2014 Range Networks, Inc.
4 *
5 * This software is distributed under the terms of the GNU Affero Public License.
6 * See the COPYING file in the main directory for details.
7 *
8 * This use of this software may be subject to additional restrictions.
9 * See the LEGAL file in the main directory for details.
10 
11  This program is free software: you can redistribute it and/or modify
12  it under the terms of the GNU Affero General Public License as published by
13  the Free Software Foundation, either version 3 of the License, or
14  (at your option) any later version.
15 
16  This program is distributed in the hope that it will be useful,
17  but WITHOUT ANY WARRANTY; without even the implied warranty of
18  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
19  GNU Affero General Public License for more details.
20 
21  You should have received a copy of the GNU Affero General Public License
22  along with this program. If not, see <http://www.gnu.org/licenses/>.
23 
24 */
25 
26 #ifndef _VITERBIR204_H_
27 #define _VITERBIR204_H_ 1
28 
29 #include "Viterbi.h"
30 
31 
32 /**
33  Class to represent convolutional coders/decoders of rate 1/2, memory length 4.
34  This is the "workhorse" coder for most GSM channels.
35 */
36 class ViterbiR2O4 : public ViterbiBase {
37 
38  private:
39  /**name Lots of precomputed elements so the compiler can optimize like hell. */
40  //@{
41  /**@name Core values. */
42  //@{
43  static const unsigned mIRate = 2; ///< reciprocal of rate
44  static const unsigned mOrder = 4; ///< memory length of generators
45  //@}
46  /**@name Derived values. */
47  //@{
48  static const unsigned mIStates = 0x01 << mOrder; ///< (16) number of states, number of survivors
49  static const uint32_t mSMask = mIStates-1; ///< survivor mask
50  static const uint32_t mCMask = (mSMask<<1) | 0x01; ///< candidate mask
51  static const uint32_t mOMask = (0x01<<mIRate)-1; ///< ouput mask, all iRate low bits set
52  static const unsigned mNumCands = mIStates*2; ///< number of candidates to generate during branching
53  static const unsigned mDeferral = 6*mOrder; ///< deferral to be used
54  //@}
55  //@}
56 
57  /** Precomputed tables. */
58  //@{
59  uint32_t mCoeffs[mIRate]; ///< polynomial for each generator
60  // (pat) There are 16 states, each of which has two possible output states.
61  // These are stored in these two tables in consecutive locations.
62  uint32_t mStateTable[mIRate][2*mIStates]; ///< precomputed generator output tables
63  // mGeneratorTable is the encoder output state for a given input state and encoder input bit.
64  uint32_t mGeneratorTable[2*mIStates]; ///< precomputed coder output table
65  //@}
66  int mBitErrorCnt;
67 
68  public:
69 
70  /**
71  A candidate sequence in a Viterbi decoder.
72  The 32-bit state register can support a deferral of 6 with a 4th-order coder.
73  */
74  typedef struct candStruct {
75  uint32_t iState; ///< encoder input associated with this candidate
76  uint32_t oState; ///< encoder output associated with this candidate
77  float cost; ///< cost (metric value), float to support soft inputs
78  int bitErrorCnt; ///< number of bit errors in the encoded vector being decoded.
79  } vCand;
80 
81  /** Clear a structure. */
82  void vitClear(vCand& v)
83  {
84  v.iState=0;
85  v.oState=0;
86  v.cost=0;
87  v.bitErrorCnt = 0;
88  }
89 
90 
91  private:
92 
93  /**@name Survivors and candidates. */
94  //@{
95  vCand mSurvivors[mIStates]; ///< current survivor pool
96  vCand mCandidates[2*mIStates]; ///< current candidate pool
97  //@}
98 
99  public:
100 
101  unsigned iRate() const { return mIRate; }
102  uint32_t cMask() const { return mCMask; }
103  uint32_t stateTable(unsigned g, unsigned i) const { return mStateTable[g][i]; }
104  unsigned deferral() const { return mDeferral; }
105 
106 
107  ViterbiR2O4();
108 
109  /** Set all cost metrics to zero. */
110  void initializeStates();
111 
112  /**
113  Full cycle of the Viterbi algorithm: branch, metrics, prune, select.
114  @return reference to minimum-cost candidate.
115  */
116  const vCand* vstep(uint32_t inSample, const float *probs, const float *iprobs, bool isNotTailBits);
117 
118  private:
119 
120  /** Branch survivors into new candidates. */
121  void branchCandidates();
122 
123  /** Compute cost metrics for soft-inputs. */
124  void getSoftCostMetrics(uint32_t inSample, const float *probs, const float *iprobs);
125 
126  /** Select survivors from the candidate set. */
127  void pruneCandidates();
128 
129  /** Find the minimum cost survivor. */
130  const vCand& minCost() const;
131 
132  /**
133  Precompute the state tables.
134  @param g Generator index 0..((1/rate)-1)
135  */
136  void computeStateTables(unsigned g);
137 
138  /**
139  Precompute the generator outputs.
140  mCoeffs must be defined first.
141  */
142  void computeGeneratorTable();
143 
144  public:
145  void encode(const BitVector &in, BitVector& target) const;
146  void decode(const SoftVector &in, BitVector& target);
147  int getBEC() { return mBitErrorCnt; }
148 };
149 #endif
uint32_t oState
encoder output associated with this candidate
Definition: ViterbiR204.h:76
struct ViterbiR2O4::candStruct vCand
unsigned deferral() const
Definition: ViterbiR204.h:104
uint32_t cMask() const
Definition: ViterbiR204.h:102
uint32_t iState
encoder input associated with this candidate
Definition: ViterbiR204.h:75
Definition: BitVector.h:120
void vitClear(vCand &v)
Definition: ViterbiR204.h:82
Definition: BitVector.h:333
unsigned iRate() const
Definition: ViterbiR204.h:101
float cost
cost (metric value), float to support soft inputs
Definition: ViterbiR204.h:77
const vCand * vstep(uint32_t inSample, const float *probs, const float *iprobs, bool isNotTailBits)
Definition: ViterbiR204.h:36
int bitErrorCnt
number of bit errors in the encoded vector being decoded.
Definition: ViterbiR204.h:78
Definition: Viterbi.h:22
Definition: ViterbiR204.h:74
void encode(const BitVector &in, BitVector &target) const
int getBEC()
Definition: ViterbiR204.h:147
void initializeStates()
void decode(const SoftVector &in, BitVector &target)
uint32_t stateTable(unsigned g, unsigned i) const
Definition: ViterbiR204.h:103