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