root/SigProc/trunk/SigProc/fec_conv.cpp @ 4184

Revision 4184, 13.2 KB (checked in by hvolos, 6 years ago)

Added some throws to ensure sanity
Line 
1/****************************************************************************
2
3Copyright 2007, Virginia Polytechnic Institute and State University
4
5This file is part of the OSSIE Signal Processing Library.
6
7OSSIE Core Framework is free software; you can redistribute it and/or modify
8it under the terms of the Lesser GNU General Public License as published by
9the Free Software Foundation; either version 2.1 of the License, or
10(at your option) any later version.
11
12The OSSIE Signal Processing library is distributed in the hope that it will be useful,
13but WITHOUT ANY WARRANTY; without even the implied warranty of
14MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
15Lesser GNU General Public License for more details.
16
17You should have received a copy of the Lesser GNU General Public License
18along with OSSIE Core Framework; if not, write to the Free Software
19Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
20
21****************************************************************************/
22
23#include "SigProc.h"
24
25#include <math.h>
26
27
28namespace SigProc {
29
30//----------------------------Trellis Entry-------------------------------------
31TrellisEntry::TrellisEntry()
32{
33    previousState=0;
34    symbolNo=0;
35    distance=-1;
36}
37
38TrellisEntry::~TrellisEntry()
39{
40
41
42}
43
44//----------------------------trellisTable--------------------------------------
45
46trellisTable::trellisTable(
47    unsigned int * generatorPolynomials,
48    unsigned short int k_in,
49    unsigned short int n_in,
50    unsigned short K_in)
51{
52    //Build trellis table
53    trellisTable::k=k_in;
54    trellisTable::n=n_in;
55    trellisTable::K=K_in;
56
57    //std::cout<<"Constructor, generatorPolynomials:";
58   // for (int i=0;i<n;i++){
59
60     //   std::cout<<generatorPolynomials[i]<<" ";
61    //}
62    //std::cout<<std::endl;
63
64    //std::cout<<"Input bits:"<<k<<" Contraint Length:"<<K<<std::endl;
65    trellisTable::nextState=NULL;
66    trellisTable::output=NULL;
67    trellisTable::GenerateTrellisTable(generatorPolynomials);
68}
69
70trellisTable::~trellisTable()
71{
72    //Deallocate memory
73    if (trellisTable::nextState!=NULL){
74        for (unsigned int i = 0; i < trellisTable::numberOfTrellisStates; i++){
75            delete []trellisTable::nextState[i];
76        }
77        delete []trellisTable::nextState;
78    }
79
80    if (trellisTable::output!=NULL){
81        for (unsigned int i = 0; i < trellisTable::numberOfTrellisStates; i++){
82            delete []trellisTable::output[i];
83        }
84        delete []trellisTable::output;
85    }
86}
87
88
89void trellisTable::GenerateTrellisTable(unsigned int * generatorPolynomials)
90{
91    numberOfTrellisStates=int(pow(2,(k*(K-1))));
92    numberOfInputStates=int(pow(2,k));
93
94    //std::cout<<"NumberOfTrellisStates="<<numberOfTrellisStates<<std::endl;
95    //std::cout<<"numberOfInputStates="<<numberOfInputStates<<std::endl;
96
97    nextState = new unsigned int *[numberOfTrellisStates];
98
99    for (unsigned int i = 0; i < numberOfTrellisStates; i++){
100        nextState[i] = new unsigned int[numberOfInputStates];
101    }
102
103
104    output = new unsigned int *[numberOfTrellisStates];
105    for (unsigned int i = 0; i < numberOfTrellisStates; i++){
106        output[i] = new unsigned int[numberOfInputStates];
107    }
108
109    unsigned int ENCregister=0, tempOut=0;
110
111    for (unsigned int tstate=0;tstate<numberOfTrellisStates;tstate++){
112        //std::cout<<tstate<<":";
113        for (unsigned short int inputIdx=0;inputIdx<numberOfInputStates;inputIdx++){
114
115            ENCregister=inputIdx*numberOfTrellisStates+tstate;
116            nextState[tstate][inputIdx]=(unsigned int)floor(ENCregister/pow(2,k));
117            tempOut=0;
118
119            for (unsigned short int bitNo=0;bitNo<n;bitNo++){
120                // std::cout<<"\nBitNo:"<<bitNo<<" ENCregister:"<<ENCregister<<" g:"<<generatorPolynomials[bitNo]<<" &:"<<(ENCregister&generatorPolynomials[bitNo])
121                //      <<"power:"<<(unsigned short int)pow(2,n-bitNo-1)<<"tempOut:"<<tempOut<<"\n";
122                // std::cout<<"Mod2add:"<<Modulo2BitWiseAdd((ENCregister&generatorPolynomials[bitNo])*(unsigned short int)pow(2,n-bitNo-1))<<"\n";
123
124                tempOut+=Modulo2BitWiseAdd(ENCregister&generatorPolynomials[bitNo])* (unsigned short int)pow(2,n-bitNo-1);
125            }
126            output[tstate][inputIdx]=tempOut;
127            //std::cout<<output[tstate][inputIdx]<<" ("<<nextState[tstate][inputIdx]<<") ";
128
129
130        }
131        //std::cout<<std::endl;
132    }
133}
134
135unsigned short int trellisTable::Modulo2BitWiseAdd(unsigned short int inputNumber)
136{
137    //std::cout<<"IN:"<<inputNumber;
138    unsigned int tempOut=0;
139    tempOut=inputNumber % 2;
140    inputNumber>>=1;
141
142    while (inputNumber>0){
143        tempOut^=inputNumber % 2;
144        inputNumber>>=1;
145    }
146    // std::cout<<" Out:"<<tempOut<<" ";
147    return tempOut;
148}
149
150
151//-------------------------------fec_conv--------------------------------------
152
153void fec_conv::SetTrellisTable(trellisTable *theTrellisTableIn)
154{
155    theTrellisTable=theTrellisTableIn;
156}
157
158void fec_conv::Dec2Bin(unsigned int decNumber,unsigned short int * outputData,unsigned short int numberOfBits)
159{
160    unsigned short int i;
161    for (i=numberOfBits;i>0;i--){
162        outputData[i-1]=decNumber % 2;
163
164        if (decNumber>0) decNumber>>=1;
165    }
166}
167
168fec_conv_encoder::fec_conv_encoder()
169{
170    currentState=0;
171}
172
173fec_conv_encoder::~fec_conv_encoder()
174{
175
176}
177
178void fec_conv_encoder::ResetState()
179{
180    currentState=0;
181}
182
183unsigned int fec_conv_encoder::GetState()
184{
185    return currentState;
186}
187
188void fec_conv_encoder::Encode(unsigned short int * inputData,unsigned short int * outputData)
189{
190    unsigned int inbits=0,tmp=0,outbits=0;
191
192    for (unsigned short int i=0;i<theTrellisTable->k;i++)    {
193        tmp=inputData[i];
194        //std::cout<<"inputData:"<<tmp<<"\n";
195        tmp<<=theTrellisTable->k-i-1;
196        //std::cout<<"temp"<<tmp<<"\n";
197        inbits+=tmp;
198    }
199   
200    if (inbits>(unsigned int)(theTrellisTable->numberOfInputStates-1)){
201        std::cout<<"ERROR:fec_conv_encoder::Encode inbits>numberOfInputStates-1";
202        std::cout<<"inbits:"<<inbits<<" numberOfInputStates:"<<theTrellisTable->numberOfInputStates;
203        throw 0;
204    };
205
206    //std::cout<<"state:"<<currentState<<" inbits:"<<inbits<<" outbits:"<<outbits<<"\n";
207    outbits=theTrellisTable->output[currentState][inbits];
208
209    currentState=theTrellisTable->nextState[currentState][inbits];
210    Dec2Bin(outbits,outputData,theTrellisTable->n);
211
212}
213
214//------------------------------Decoder-----------------------------------------
215fec_conv_decoder::fec_conv_decoder()
216{
217    tracedBackSymbols=NULL;
218    theTrellis=NULL;
219    decodedSymbolIndex=0;
220    currentTrellisIndex=0;
221    mode=0;
222}
223
224fec_conv_decoder::~fec_conv_decoder()
225{
226    if (tracedBackSymbols!=NULL) delete  []tracedBackSymbols;
227
228    if (theTrellis!=NULL){
229        for (unsigned int i = 0; i < theTrellisTable->numberOfTrellisStates; i++){
230            delete theTrellis[i];
231        };
232       
233        delete []theTrellis;
234    }
235
236};
237void fec_conv_decoder::SetMode(unsigned short int mode)
238{
239    fec_conv_decoder::mode=mode;
240};
241
242void fec_conv_decoder::Reset()
243{
244    decodedSymbolIndex=0;
245    currentTrellisIndex=0;
246     for (unsigned int i=0;i<theTrellisTable->numberOfTrellisStates;i++)
247        for (unsigned int j=0;j<=noOfSymbols2TraceBack;j++){
248            theTrellis[i][j].previousState=0;
249            theTrellis[i][j].symbolNo=0;
250            theTrellis[i][j].distance=(signed int)-1;
251        }
252    theTrellis[0][0].distance=0;
253};
254
255void fec_conv_decoder::SetNoOfSymbols2TraceBack(unsigned int traceBackLength){
256    //std::cout<<theTrellis;
257    if (theTrellis!=NULL){
258        for (unsigned int i = 0; i < theTrellisTable->numberOfTrellisStates; i++){
259            delete theTrellis[i];
260        };
261        delete []theTrellis;
262        theTrellis=NULL;
263    }
264    //std::cout<<theTrellis;
265    //int dummy;
266    //std::cin>>dummy;
267
268    fec_conv_decoder::noOfSymbols2TraceBack=traceBackLength;
269
270    theTrellis= new TrellisEntry*[theTrellisTable->numberOfTrellisStates];
271    for (unsigned int i = 0; i < theTrellisTable->numberOfTrellisStates; i++){
272        theTrellis[i] =new TrellisEntry[noOfSymbols2TraceBack+1];
273    };
274
275    if (tracedBackSymbols!=NULL){
276        delete []tracedBackSymbols;
277        tracedBackSymbols=NULL;
278    };
279    tracedBackSymbols = new unsigned int [noOfSymbols2TraceBack];
280
281    currentTrellisIndex=0;
282    for (unsigned int i=0;i<theTrellisTable->numberOfTrellisStates;i++)
283        for (unsigned int j=0;j<=noOfSymbols2TraceBack;j++){
284            theTrellis[i][j].previousState=0;
285            theTrellis[i][j].symbolNo=0;
286            theTrellis[i][j].distance=(signed int)-1;
287        }
288    theTrellis[0][0].distance=0;
289
290}
291
292void fec_conv_decoder::Symbol2Decode(unsigned short int * inputData)
293{
294
295    unsigned int inbits=0,tmp=0,newState=0;
296    unsigned short int symbol;
297    signed int distance;
298
299    inbits=0;
300    for (unsigned short int i=0;i<theTrellisTable->n;i++){
301        tmp=inputData[i];
302        //std::cout<<"inputData:"<<tmp<<"\n";
303        tmp<<=theTrellisTable->n-i-1;
304        //std::cout<<"temp"<<tmp<<"\n";
305        inbits+=tmp;
306    }
307
308   
309    //std::cout<<"inbits:"<<inbits<<"\n";
310    currentTrellisIndex++;
311
312    if (currentTrellisIndex>noOfSymbols2TraceBack){
313         std::cout<<"ERROR:fec_conv_decoder::Symbol2Decode currentTrellisIndex>Traceback length";
314        throw 0;
315    };
316
317     if (inbits>(unsigned int)(pow(theTrellisTable->n,2)-1)){
318        std::cout<<"ERROR:fec_conv_decoder::Symbol2Decode inbits>2^n-1\n";
319        std::cout<<"inbits:"<<inbits<<" numberOfInputStates:"<<pow(theTrellisTable->n,2)-1;
320        throw 0;
321    };
322
323    //std::cout<<"currentTrellisIndex:"<<currentTrellisIndex<<"\n";
324    for (unsigned int tstate=0;tstate<theTrellisTable->numberOfTrellisStates;tstate++){
325        if (theTrellis[tstate][currentTrellisIndex-1].distance!=-1){
326            for (unsigned short int inputBits=0;inputBits<theTrellisTable->numberOfInputStates;inputBits++){
327                newState=theTrellisTable->nextState[tstate][inputBits];
328                symbol=theTrellisTable->output[tstate][inputBits];
329
330                distance=CalculateDistance(inbits,symbol)+theTrellis[tstate][currentTrellisIndex-1].distance; //Have to calculate;
331                if ((theTrellis[newState][currentTrellisIndex].distance==-1)||
332                        ((distance<theTrellis[newState][currentTrellisIndex].distance))||
333                        (theTrellis[newState][currentTrellisIndex].distance<0)){
334                    theTrellis[newState][currentTrellisIndex].distance=distance;
335                    theTrellis[newState][currentTrellisIndex].previousState=tstate;
336                    theTrellis[newState][currentTrellisIndex].symbolNo=inputBits;
337                };
338            };
339        }
340        else{
341        };
342
343    }
344
345    /*
346        for (unsigned int tstate=0;tstate<numberOfTrellisStates;tstate++)
347        {
348                    std::cout<<"["<<tstate<<"]["<<currentTrellisIndex<<"].previousState:"
349                       <<theTrellis[tstate][currentTrellisIndex].previousState<<".distance:"
350                        <<theTrellis[tstate][currentTrellisIndex].distance<<".symbol:"<<
351                        theTrellis[tstate][currentTrellisIndex].symbolNo<<"\n";
352        };
353    */
354};
355
356signed int fec_conv_decoder::CalculateDistance(unsigned short int inBits, unsigned short int symbol)
357{
358    unsigned short int tmp;
359    signed int distance=0;
360    tmp=inBits^symbol;
361
362    while (tmp>0){
363        distance+=(signed int)(tmp % 2);
364        tmp>>=1;
365    };
366    return distance;
367
368}
369
370void fec_conv_decoder::TraceBackTrellis(){
371    //std::cout<<"cTi:"<<currentTrellisIndex<<"; cS:"<<currentState<<";";
372    unsigned int currentState;
373    signed int minDistance=9999;
374    unsigned int minDistState=0;
375
376    if (currentTrellisIndex==noOfSymbols2TraceBack){
377        if (mode==1){
378            currentState=0;
379        } else{
380            for (unsigned int tstate=0;tstate<theTrellisTable->numberOfTrellisStates;tstate++)
381                if ((theTrellis[tstate][currentTrellisIndex].distance!=-1)
382                        &&(theTrellis[tstate][currentTrellisIndex].distance<minDistance)){
383                    minDistance=theTrellis[tstate][currentTrellisIndex].distance;
384                    minDistState=tstate;
385                };
386
387            currentState=minDistState;
388        }
389       // std::cout<<"\nMinDistance:"<<minDistance<<" minDistState:"<<minDistState<<"\n";
390
391
392        unsigned short int symbol;
393        while (currentTrellisIndex>0)
394        {
395            symbol=theTrellis[currentState][currentTrellisIndex].symbolNo;
396            currentState=theTrellis[currentState][currentTrellisIndex].previousState;
397            currentTrellisIndex--;
398            //Dec2Bin(symbol,outputData,k);
399            tracedBackSymbols[currentTrellisIndex]=symbol;
400            // std::cout<<"\nsymbol:"<<symbol<<"outputData"<<outputData[0]<<"\n";
401        }
402
403        decodedSymbolIndex=0;
404    }
405}
406
407void fec_conv_decoder::GetDecodedSymbol(unsigned short int * outputData)
408{
409    if (currentTrellisIndex==0){
410
411        if (decodedSymbolIndex<noOfSymbols2TraceBack){
412            Dec2Bin(tracedBackSymbols[decodedSymbolIndex],
413            outputData,
414            theTrellisTable->k);
415        } else {
416        std::cout<<"ERROR: fec_conv_decoder::GetDecodedSymbol attempt to get more symbols of what is available\n";
417        throw 0;
418   
419        }
420       
421        decodedSymbolIndex++;
422       
423    } else {
424        std::cout<<"ERROR: fec_conv_decoder::GetDecodedSymbol trellis wasnt traced back properly\n";
425        throw 0;
426    }
427}
428
429
430
431} // namespace SigProc
432
Note: See TracBrowser for help on using the browser.