diff options
author | Alexander Chemeris <Alexander.Chemeris@gmail.com> | 2017-03-17 18:00:50 -0700 |
---|---|---|
committer | Alexander Chemeris <Alexander.Chemeris@gmail.com> | 2017-03-22 18:31:17 +0000 |
commit | 7db522b6d951413d7d62f9c7e52a9b2100622399 (patch) | |
tree | 281be9ad141dc8f6e9951ab0c019947457942e69 | |
parent | ae09b04e26068182b870d7e136e25eeb3767396a (diff) |
BitVector: Remove convolutional codec - we don't use it in osmo-trx.
Now we have more fexibility in how we represent SoftVector, since we
no longer depend on the particular convolutional codec implementation.
Change-Id: I3006b6a26c5eff59dbe9c034f689961802f1d0d0
-rw-r--r-- | CommonLibs/BitVector.cpp | 241 | ||||
-rw-r--r-- | CommonLibs/BitVector.h | 143 | ||||
-rw-r--r-- | CommonLibs/BitVectorTest.cpp | 28 |
3 files changed, 1 insertions, 411 deletions
diff --git a/CommonLibs/BitVector.cpp b/CommonLibs/BitVector.cpp index 8389237..b77a4c4 100644 --- a/CommonLibs/BitVector.cpp +++ b/CommonLibs/BitVector.cpp @@ -217,30 +217,6 @@ uint64_t BitVector::parity(Generator& gen) const } -void BitVector::encode(const ViterbiR2O4& coder, BitVector& target) -{ - size_t sz = size(); - assert(sz*coder.iRate() == target.size()); - - // Build a "history" array where each element contains the full history. - uint32_t history[sz]; - uint32_t accum = 0; - for (size_t i=0; i<sz; i++) { - accum = (accum<<1) | bit(i); - history[i] = accum; - } - - // Look up histories in the pre-generated state table. - char *op = target.begin(); - for (size_t i=0; i<sz; i++) { - unsigned index = coder.cMask() & history[i]; - for (unsigned g=0; g<coder.iRate(); g++) { - *op++ = coder.stateTable(g,index); - } - } -} - - unsigned BitVector::sum() const { @@ -287,142 +263,6 @@ ostream& operator<<(ostream& os, const BitVector& hv) -ViterbiR2O4::ViterbiR2O4() -{ - assert(mDeferral < 32); - mCoeffs[0] = 0x019; - mCoeffs[1] = 0x01b; - computeStateTables(0); - computeStateTables(1); - computeGeneratorTable(); -} - - - - -void ViterbiR2O4::initializeStates() -{ - for (unsigned i=0; i<mIStates; i++) clear(mSurvivors[i]); - for (unsigned i=0; i<mNumCands; i++) clear(mCandidates[i]); -} - - - -void ViterbiR2O4::computeStateTables(unsigned g) -{ - assert(g<mIRate); - for (unsigned state=0; state<mIStates; state++) { - // 0 input - uint32_t inputVal = state<<1; - mStateTable[g][inputVal] = applyPoly(inputVal, mCoeffs[g], mOrder+1); - // 1 input - inputVal |= 1; - mStateTable[g][inputVal] = applyPoly(inputVal, mCoeffs[g], mOrder+1); - } -} - -void ViterbiR2O4::computeGeneratorTable() -{ - for (unsigned index=0; index<mIStates*2; index++) { - mGeneratorTable[index] = (mStateTable[0][index]<<1) | mStateTable[1][index]; - } -} - - - - - - -void ViterbiR2O4::branchCandidates() -{ - // Branch to generate new input states. - const vCand *sp = mSurvivors; - for (unsigned i=0; i<mNumCands; i+=2) { - // extend and suffix - const uint32_t iState0 = (sp->iState) << 1; // input state for 0 - const uint32_t iState1 = iState0 | 0x01; // input state for 1 - const uint32_t oStateShifted = (sp->oState) << mIRate; // shifted output - const float cost = sp->cost; - sp++; - // 0 input extension - mCandidates[i].cost = cost; - mCandidates[i].oState = oStateShifted | mGeneratorTable[iState0 & mCMask]; - mCandidates[i].iState = iState0; - // 1 input extension - mCandidates[i+1].cost = cost; - mCandidates[i+1].oState = oStateShifted | mGeneratorTable[iState1 & mCMask]; - mCandidates[i+1].iState = iState1; - } -} - - -void ViterbiR2O4::getSoftCostMetrics(const uint32_t inSample, const float *matchCost, const float *mismatchCost) -{ - const float *cTab[2] = {matchCost,mismatchCost}; - for (unsigned i=0; i<mNumCands; i++) { - vCand& thisCand = mCandidates[i]; - // We examine input bits 2 at a time for a rate 1/2 coder. - const unsigned mismatched = inSample ^ (thisCand.oState); - thisCand.cost += cTab[mismatched&0x01][1] + cTab[(mismatched>>1)&0x01][0]; - } -} - - -void ViterbiR2O4::pruneCandidates() -{ - const vCand* c1 = mCandidates; // 0-prefix - const vCand* c2 = mCandidates + mIStates; // 1-prefix - for (unsigned i=0; i<mIStates; i++) { - if (c1[i].cost < c2[i].cost) mSurvivors[i] = c1[i]; - else mSurvivors[i] = c2[i]; - } -} - - -const ViterbiR2O4::vCand& ViterbiR2O4::minCost() const -{ - int minIndex = 0; - float minCost = mSurvivors[0].cost; - for (unsigned i=1; i<mIStates; i++) { - const float thisCost = mSurvivors[i].cost; - if (thisCost>=minCost) continue; - minCost = thisCost; - minIndex=i; - } - return mSurvivors[minIndex]; -} - - -const ViterbiR2O4::vCand& ViterbiR2O4::step(uint32_t inSample, const float *probs, const float *iprobs) -{ - branchCandidates(); - getSoftCostMetrics(inSample,probs,iprobs); - pruneCandidates(); - return minCost(); -} - - -uint64_t Parity::syndrome(const BitVector& receivedCodeword) -{ - return receivedCodeword.syndrome(*this); -} - - -void Parity::writeParityWord(const BitVector& data, BitVector& parityTarget, bool invert) -{ - uint64_t pWord = data.parity(*this); - if (invert) pWord = ~pWord; - parityTarget.fillField(0,pWord,size()); -} - - - - - - - - - SoftVector::SoftVector(const BitVector& source) { resize(source.size()); @@ -445,87 +285,6 @@ BitVector SoftVector::sliced() const } - -void SoftVector::decode(ViterbiR2O4 &decoder, BitVector& target) const -{ - const size_t sz = size(); - const unsigned deferral = decoder.deferral(); - const size_t ctsz = sz + deferral*decoder.iRate(); - assert(sz <= decoder.iRate()*target.size()); - - // Build a "history" array where each element contains the full history. - uint32_t history[ctsz]; - { - BitVector bits = sliced(); - uint32_t accum = 0; - for (size_t i=0; i<sz; i++) { - accum = (accum<<1) | bits.bit(i); - history[i] = accum; - } - // Repeat last bit at the end. - for (size_t i=sz; i<ctsz; i++) { - accum = (accum<<1) | (accum & 0x01); - history[i] = accum; - } - } - - // Precompute metric tables. - float matchCostTable[ctsz]; - float mismatchCostTable[ctsz]; - { - const float *dp = mStart; - for (size_t i=0; i<sz; i++) { - // pVal is the probability that a bit is correct. - // ipVal is the probability that a bit is incorrect. - float pVal = dp[i]; - if (pVal>0.5F) pVal = 1.0F-pVal; - float ipVal = 1.0F-pVal; - // This is a cheap approximation to an ideal cost function. - if (pVal<0.01F) pVal = 0.01; - if (ipVal<0.01F) ipVal = 0.01; - matchCostTable[i] = 0.25F/ipVal; - mismatchCostTable[i] = 0.25F/pVal; - } - - // pad end of table with unknowns - for (size_t i=sz; i<ctsz; i++) { - matchCostTable[i] = 0.5F; - mismatchCostTable[i] = 0.5F; - } - } - - { - decoder.initializeStates(); - // Each sample of history[] carries its history. - // So we only have to process every iRate-th sample. - const unsigned step = decoder.iRate(); - // input pointer - const uint32_t *ip = history + step - 1; - // output pointers - char *op = target.begin(); - const char *const opt = target.end(); - // table pointers - const float* match = matchCostTable; - const float* mismatch = mismatchCostTable; - size_t oCount = 0; - while (op<opt) { - // Viterbi algorithm - assert(match-matchCostTable<sizeof(matchCostTable)/sizeof(matchCostTable[0])-1); - assert(mismatch-mismatchCostTable<sizeof(mismatchCostTable)/sizeof(mismatchCostTable[0])-1); - const ViterbiR2O4::vCand &minCost = decoder.step(*ip, match, mismatch); - ip += step; - match += step; - mismatch += step; - // output - if (oCount>=deferral) *op++ = (minCost.iState >> deferral)&0x01; - oCount++; - } - } -} - - - -// (pat) Added 6-22-2012 float SoftVector::getEnergy(float *plow) const { const SoftVector &vec = *this; diff --git a/CommonLibs/BitVector.h b/CommonLibs/BitVector.h index e244be7..7473c32 100644 --- a/CommonLibs/BitVector.h +++ b/CommonLibs/BitVector.h @@ -89,142 +89,6 @@ class Generator { - -/** Parity (CRC-type) generator and checker based on a Generator. */ -class Parity : public Generator { - - protected: - - unsigned mCodewordSize; - - public: - - Parity(uint64_t wCoefficients, unsigned wParitySize, unsigned wCodewordSize) - :Generator(wCoefficients, wParitySize), - mCodewordSize(wCodewordSize) - { } - - /** Compute the parity word and write it into the target segment. */ - void writeParityWord(const BitVector& data, BitVector& parityWordTarget, bool invert=true); - - /** Compute the syndrome of a received sequence. */ - uint64_t syndrome(const BitVector& receivedCodeword); -}; - - - - -/** - Class to represent convolutional coders/decoders of rate 1/2, memory length 4. - This is the "workhorse" coder for most GSM channels. -*/ -class ViterbiR2O4 { - - private: - /**name Lots of precomputed elements so the compiler can optimize like hell. */ - //@{ - /**@name Core values. */ - //@{ - static const unsigned mIRate = 2; ///< reciprocal of rate - static const unsigned mOrder = 4; ///< memory length of generators - //@} - /**@name Derived values. */ - //@{ - static const unsigned mIStates = 0x01 << mOrder; ///< number of states, number of survivors - static const uint32_t mSMask = mIStates-1; ///< survivor mask - static const uint32_t mCMask = (mSMask<<1) | 0x01; ///< candidate mask - static const uint32_t mOMask = (0x01<<mIRate)-1; ///< ouput mask, all iRate low bits set - static const unsigned mNumCands = mIStates*2; ///< number of candidates to generate during branching - static const unsigned mDeferral = 6*mOrder; ///< deferral to be used - //@} - //@} - - /** Precomputed tables. */ - //@{ - uint32_t mCoeffs[mIRate]; ///< polynomial for each generator - uint32_t mStateTable[mIRate][2*mIStates]; ///< precomputed generator output tables - uint32_t mGeneratorTable[2*mIStates]; ///< precomputed coder output table - //@} - - public: - - /** - A candidate sequence in a Viterbi decoder. - The 32-bit state register can support a deferral of 6 with a 4th-order coder. - */ - typedef struct candStruct { - uint32_t iState; ///< encoder input associated with this candidate - uint32_t oState; ///< encoder output associated with this candidate - float cost; ///< cost (metric value), float to support soft inputs - } vCand; - - /** Clear a structure. */ - void clear(vCand& v) - { - v.iState=0; - v.oState=0; - v.cost=0; - } - - - private: - - /**@name Survivors and candidates. */ - //@{ - vCand mSurvivors[mIStates]; ///< current survivor pool - vCand mCandidates[2*mIStates]; ///< current candidate pool - //@} - - public: - - unsigned iRate() const { return mIRate; } - uint32_t cMask() const { return mCMask; } - uint32_t stateTable(unsigned g, unsigned i) const { return mStateTable[g][i]; } - unsigned deferral() const { return mDeferral; } - - - ViterbiR2O4(); - - /** Set all cost metrics to zero. */ - void initializeStates(); - - /** - Full cycle of the Viterbi algorithm: branch, metrics, prune, select. - @return reference to minimum-cost candidate. - */ - const vCand& step(uint32_t inSample, const float *probs, const float *iprobs); - - private: - - /** Branch survivors into new candidates. */ - void branchCandidates(); - - /** Compute cost metrics for soft-inputs. */ - void getSoftCostMetrics(uint32_t inSample, const float *probs, const float *iprobs); - - /** Select survivors from the candidate set. */ - void pruneCandidates(); - - /** Find the minimum cost survivor. */ - const vCand& minCost() const; - - /** - Precompute the state tables. - @param g Generator index 0..((1/rate)-1) - */ - void computeStateTables(unsigned g); - - /** - Precompute the generator outputs. - mCoeffs must be defined first. - */ - void computeGeneratorTable(); - -}; - - - - class BitVector : public Vector<char> { @@ -288,8 +152,6 @@ class BitVector : public Vector<char> { uint64_t syndrome(Generator& gen) const; /** Calculate the parity word for the vector with the given Generator. */ uint64_t parity(Generator& gen) const; - /** Encode the signal with the GSM rate 1/2 convolutional encoder. */ - void encode(const ViterbiR2O4& encoder, BitVector& target); //@} @@ -427,10 +289,7 @@ class SoftVector: public Vector<float> { const SoftVector tail(size_t start) const { return segment(start,size()-start); } //@} - /** Decode soft symbols with the GSM rate-1/2 Viterbi decoder. */ - void decode(ViterbiR2O4 &decoder, BitVector& target) const; - - // (pat) How good is the SoftVector in the sense of the bits being solid? + // How good is the SoftVector in the sense of the bits being solid? // Result of 1 is perfect and 0 means all the bits were 0.5 // If plow is non-NULL, also return the lowest energy bit. float getEnergy(float *low=0) const; diff --git a/CommonLibs/BitVectorTest.cpp b/CommonLibs/BitVectorTest.cpp index 5e487ad..063138f 100644 --- a/CommonLibs/BitVectorTest.cpp +++ b/CommonLibs/BitVectorTest.cpp @@ -35,27 +35,6 @@ using namespace std; int main(int argc, char *argv[]) { - BitVector v1("0000111100111100101011110000"); - cout << v1 << endl; - v1.LSB8MSB(); - cout << v1 << endl; - ViterbiR2O4 vCoder; - BitVector v2(v1.size()*2); - v1.encode(vCoder,v2); - cout << v2 << endl; - SoftVector sv2(v2); - cout << sv2 << endl; - for (unsigned i=0; i<sv2.size()/4; i++) sv2[random()%sv2.size()]=0.5; - cout << sv2 << endl; - BitVector v3(v1.size()); - sv2.decode(vCoder,v3); - cout << v3 << endl; - - cout << v3.segment(3,4) << endl; - - BitVector v4(v3.segment(0,4),v3.segment(8,4)); - cout << v4 << endl; - BitVector v5("000011110000"); int r1 = v5.peekField(0,8); int r2 = v5.peekField(4,4); @@ -70,13 +49,6 @@ int main(int argc, char *argv[]) v5.reverse8(); cout << v5 << endl; - BitVector mC = "000000000000111100000000000001110000011100001101000011000000000000000111000011110000100100001010000010100000101000001010000010100000010000000000000000000000000000000000000000000000001100001111000000000000000000000000000000000000000000000000000010010000101000001010000010100000101000001010000001000000000000000000000000110000111100000000000001110000101000001100000001000000000000"; - SoftVector mCS(mC); - BitVector mU(mC.size()/2); - mCS.decode(vCoder,mU); - cout << "c=" << mCS << endl; - cout << "u=" << mU << endl; - unsigned char ts[9] = "abcdefgh"; BitVector tp(70); |