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

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);