Alexander Chemeris has submitted this change and it was merged.
Change subject: BitVector: Remove convolutional codec - we don't use it in
osmo-trx.
......................................................................
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
---
M CommonLibs/BitVector.cpp
M CommonLibs/BitVector.h
M CommonLibs/BitVectorTest.cpp
3 files changed, 1 insertion(+), 411 deletions(-)
Approvals:
Tom Tsou: Looks good to me, approved
Max: Looks good to me, but someone else must approve
Jenkins Builder: Verified
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 @@
}
-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 @@
-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 @@
}
-
-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 @@
-
-/** 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 @@
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 @@
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 @@
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);
@@ -69,13 +48,6 @@
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";
--
To view, visit https://gerrit.osmocom.org/2141
To unsubscribe, visit https://gerrit.osmocom.org/settings
Gerrit-MessageType: merged
Gerrit-Change-Id: I3006b6a26c5eff59dbe9c034f689961802f1d0d0
Gerrit-PatchSet: 3
Gerrit-Project: osmo-trx
Gerrit-Branch: master
Gerrit-Owner: Alexander Chemeris <alexander.cheme...@gmail.com>
Gerrit-Reviewer: Alexander Chemeris <alexander.cheme...@gmail.com>
Gerrit-Reviewer: Jenkins Builder
Gerrit-Reviewer: Max <msur...@sysmocom.de>
Gerrit-Reviewer: Tom Tsou <t...@tsou.cc>
