trellis.h

Go to the documentation of this file.

/***************************************************************************
                          trellis.h  -  description
                             -------------------
    begin                : Tue Jul 15 2003
    copyright            : (C) 2003 by Peter Haase
    email                : p.haase@tuhh.de
 ***************************************************************************/

/***************************************************************************
 *                                                                         *
 *   This library is free software; you can redistribute it and/or         *
 *   modify it under the terms of the GNU Lesser General Public            *
 *   License as published by the Free Software Foundation; either          *
 *   version 2.1 of the License, or (at your option) any later version.    *
 *                                                                         *
 *   This library is distributed in the hope that it will be useful,       *
 *   but WITHOUT ANY WARRANTY; without even the implied warranty of        *
 *   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU     *
 *   Lesser General Public License for more details.                       *
 *                                                                         *
 *   You should have received a copy of the GNU Lesser General Public      *
 *   License along with this library; if not, write to the Free Software   *
 *   Foundation, Inc., 59 Temple Place, Suite 330, Boston,                 *
 *   MA  02111-1307  USA                                                   *
 *                                                                         *
 ***************************************************************************/

#ifndef TRELLIS_H
#define TRELLIS_H

#include <iostream>

#include "phbib.h"
#include "signals.h"
#include "bitmapping.h"
#include "demodulator.h"
#include "diffdemodulator.h"

namespace simthlib
{


struct TrellisPath
{
  int prev;

  int data;

  simth::Array<double> metr;

};


struct TrellisBranch
{
  int prev_state;

  int input;

  int output;

  int new_state;
};


class PhaseAmplitudeConstellationDiagram;

class Trellis;
std::ostream& operator<<(std::ostream &os, const Trellis &trellis);


class Trellis
{


  public:
    Trellis(int states, int inbits, int outbits);

    virtual ~Trellis();

    virtual void print(std::ostream &os) const {os<<"# No printing for trellis bases implemented";}

    void printStateDiagram(std::ostream &os) const
    {
      os<<"State diagram printing is not implemented"
      "for trellis bases implemented";
    }

    virtual int getDataLength(int code_length) const;

    virtual int getCodeLength(int data_length) const;

    const int numStates() const {return num_states;}

    const int numInbits() const {return num_inbits;}

    const int numInput() const {return num_input;}

    const int numOutbits() const {return num_outbits;}

    const int numOutput() const {return num_output;}

    virtual int getNextState(int state, int input, size_t step,size_t path_length) const=0;

    virtual int getNextOut(int state, int input, size_t step,size_t path_length) const =0;

    virtual int getPrevState(int state, int index, size_t step,size_t path_length) const =0;

    virtual int getPrevOut(int state, int index, size_t step,size_t path_length) const =0;

    virtual int getPrevIn(int state, int index, size_t step, size_t path_length) const =0;

    typedef std::vector<TrellisBranch> TrellisBranchArray;

    typedef std::vector<TrellisBranchArray> TrellisStatesArray;

    virtual const TrellisStatesArray& 
      getPrevTrellisArray(size_t time_step, size_t path_length) const =0;

    inline static const TrellisBranchArray&
      getPrevArray_state(const TrellisStatesArray& state_array, int state)
      { return state_array[state]; }

    inline static const TrellisBranch& 
      getPrevState_branch(const TrellisBranchArray& branch_array, int index)
      { return branch_array[index]; }

    inline static int getPrevState(const TrellisBranch& tb)
      { return tb.prev_state; }
    inline static int getPrevOut(const TrellisBranch& tb)
      { return tb.output; }
    inline static int getPrevIn(const TrellisBranch& tb)
      { return tb.input; }

    virtual int terminationInput(int state) const = 0;

    bool isTerminationStep(size_t path_length, size_t step) const;

    virtual bool isPossibleStartingState(int state) const = 0;

    size_t numTailsteps() const {return num_tailsteps;}

    size_t numTailbits() const {return num_tailbits;}

  protected:

    void setTailstepLength(int newTailsteps);
    void setTailbitLength(int newTailbits);
    void setPathLength(int newPathLength);

    const int num_states;

    const int num_inbits;

    const int num_input;

    const int num_outbits;

    const int num_output;

  private:

    void invariante() const;


    size_t num_tailsteps;

    size_t num_tailbits;

};




inline void Trellis::invariante() const
{
  //if(DEBUG) {}
}


inline bool Trellis::isTerminationStep(size_t path_length, size_t step) const
{
  if(DEBUG) {
    if(step < 0 || step >= path_length || path_length < num_tailsteps) {
      throw std::runtime_error("Trellis::isTerminationStep() const :  pathLength() < numTailsteps()");
    }
  }
  return (step >= (path_length- num_tailsteps));
}


inline void Trellis::setTailstepLength(int newTailsteps)
{
  num_tailsteps = newTailsteps;
  num_tailbits = num_tailsteps * num_inbits;
}

inline void Trellis::setTailbitLength(int newTailbits)
{
  num_tailbits = newTailbits;
  if(DEBUG) {
    if(num_inbits == 0) {
      throw std::logic_error("inline void Trellis::setNewTailbitLength(int newTailbits) : error 1");
    }
    if(num_inbits % num_inbits != 0) {
      throw std::logic_error("inline void Trellis::setNewTailbitLength(int newTailbits) : error 3");
    }
  }
  num_tailsteps = num_tailbits/num_inbits;
}






//  Shift register
//  Autor: Peter Haase
//  email: p.haase@tu-harburg.de




class BestPolynomials
{
  public:

    static const int genpol2[9][2];

    static const int genpol3[9][3];

    static const int genpol4[9][4];


};




class ShiftRegister
{
  private:

    int mem;
    int symbolsPerStep_;
    int bitsPerSymbol_;
    int M_;

  protected:

    simth::checkedVector<int> polynomials;
    int recursivePolynomial;

    int symbolsPerStep() const {return symbolsPerStep_;}
    int bitsPerSymbol() const {return bitsPerSymbol_;}
    int M() const {return M_;}



  public:
    ShiftRegister(int symbolsPerStep, int bitsPerSymbol, const simth::checkedVector<int>& octalPolynomials, int recursivePolynomial = 0);

    virtual ~ShiftRegister() = 0;

    virtual int getNextState(int inputPattern, int oldState) const = 0;

    /*Computes the output of the shift register according to a given state and input.
    */
    virtual int getOutput(int input, int state) const = 0;

    virtual int getRecursive(int state) const = 0;

    int memoryLength() const {return mem;}

    virtual int tailsteps() const = 0;

    virtual void print(std::ostream &os) const;

    static int computeNumOutputBits(int numPolynomials, int symbolsPerStep, int bitsPerSymbol,bool systematic);

    static void getBestPolynomials(int mem, int inbits, int outbits, simth::checkedVector<int>* genPolynomials);

    static int computeMemoryLength(const simth::checkedVector<int>& polynomials, int recursivePolynomial = 0);

    static int computeMemoryLength(int polynomial);

};

inline  ShiftRegister::~ShiftRegister(){}


class AbstractShiftRegisterBinary : public ShiftRegister
{
  private:


  public:
    AbstractShiftRegisterBinary(int inbitsPerStep,
                                const simth::checkedVector<int>& octalPolynomials, int recursivePolynomial = 0);

    virtual ~AbstractShiftRegisterBinary() = 0;

    virtual int getNextState(int inputPattern, int oldState) const;


    virtual int getOutput(int input, int state) const;

    virtual int getRecursive(int newState) const;

    virtual int tailsteps() const;

};

inline  AbstractShiftRegisterBinary::~AbstractShiftRegisterBinary()
{}

class ShiftRegisterBinary : public AbstractShiftRegisterBinary
{
  public:

    ShiftRegisterBinary(int inbitsPerStep, const simth::checkedVector<int>& octalPolynomials,
                        int recursivePolynomial = 0);

    ~ShiftRegisterBinary(){};

};


class ShiftRegisterSystematicBinary : public AbstractShiftRegisterBinary
{

  public:

    ShiftRegisterSystematicBinary(int inbitsPerStep, const simth::checkedVector<int>& octalPolynomials,
                                  int recursivePolynomial = 0);

    ~ShiftRegisterSystematicBinary(){};

    /* Computes the output of the shift register according to a given state and input.
    */
    virtual int getOutput(int input, int state) const;


    virtual void print(std::ostream &os) const;
};


class ShiftRegisterM : public ShiftRegister
{
  private:

    mutable simth::checkedVector<int> stateVector;

    int M_;

  protected:


    void binaryState2symbolState(int binState, simth::checkedVector<int>& symbolStates) const;
    int symbolState2binaryState(const simth::checkedVector<int>& symbolStates) const;
    void shiftVector(simth::checkedVector<int>& vec, int increment) const;

    int getRecursive(const simth::checkedVector<int>& symbolStates) const;

  public:
    ShiftRegisterM(int symbolsPerStep, int bitsPerSymbol, const simth::checkedVector<int>& octalPolynomials,
                   int recursivePolynomial = 0, int inbits = 1);

    virtual ~ShiftRegisterM(){};

    virtual int getNextState(int inputPattern, int oldState) const;


    virtual int getOutput(int input, int state) const;

    virtual int getRecursive(int newState) const;

    virtual int tailsteps() const;
};



class ConvCodeTrellis : public Trellis
{
  public:

    enum StartingMode {FREE, ZERO, AMBIGOUS};


    ConvCodeTrellis(int states, int inbits, int outbits, StartingMode startingMode);

    virtual ~ConvCodeTrellis();

    void printStateDiagram(std::ostream &os) const;

    virtual simth::BitSeq* Encode(const simth::BitSeq&)const;

    virtual void Encode(const simth::BitSeq &bsin, simth::BitSeq* bsout) const;

   protected:

    // muss noch effizienter werden ! -> erledigt durch Array2d!
    //simth::checkedVector2d<TrellisBranch> forward;
    Trellis::TrellisStatesArray forward;
    //simth::checkedVector2d<TrellisBranch> back;
    Trellis::TrellisStatesArray back;
    //TrellisBranch** forward;
    simth::Array<int> terminationInput_;
    //TrellisBranch** back;
    Trellis::TrellisStatesArray terminationForward;
    Trellis::TrellisStatesArray terminationBack;

    virtual int getNextState(int state, int input, size_t step,size_t path_length) const;

    virtual int getNextOut(int state, int input, size_t step,size_t path_length) const;

    virtual int getPrevState(int state, int index, size_t step,size_t path_length) const;

    virtual int getPrevOut(int state, int index, size_t step,size_t path_length) const;

    virtual int getPrevIn(int state, int index, size_t step,size_t path_length) const;

    virtual const Trellis::TrellisStatesArray&
      getPrevTrellisArray(size_t time_step, size_t path_length) const;

    ConvCodeTrellis::StartingMode startingMode() const {return startingMode_;}

    virtual bool isPossibleStartingState(int state) const = 0;

    virtual int terminationInput(int state) const;
 
  private:

    static const char *punct2[14][7];

    static const char *punct3[8][4];

    static const char *punct4;

    const StartingMode startingMode_;

};


inline int ConvCodeTrellis::getNextState(int state, int input, size_t step,size_t path_length) const
{
  if(DEBUG) {
    if(step < 0 || step >= path_length) {
      throw std::logic_error("inline int ConvCodeTrellis::getNextState(int state, int input, "
                             "size_t step) const : error 1");
    }
  }
  if(!isTerminationStep(path_length,step)) {
    return forward[state][input].new_state;
  }
  else {
    return terminationForward[state][input].new_state;
  }
}

inline int ConvCodeTrellis::getNextOut(int state, int input, size_t step,size_t path_length) const
{
  if(DEBUG) {
    if(step < 0 || step >= path_length) {
      throw std::logic_error("inline int ConvCodeTrellis::getNextOut(int state, int input, "
                             "size_t step) const : error 1");
    }
  }
  if(!isTerminationStep(path_length,step)) {
    return forward[state][input].output;
  }
  else {
    return terminationForward[state][input].output;
  }
}

inline int ConvCodeTrellis::getPrevState(int state, int index, size_t step,size_t path_length) const
{
  if(DEBUG) {
    if(step < 0 || step >= path_length) {
      throw std::logic_error("inline int ConvCodeTrellis::getPrevState(int state, int input, "
                             "size_t step) const : error 1");
    }
  }
  if(!isTerminationStep(path_length,step)) {
    return back[state][index].prev_state;
  }
  else {
    return terminationBack[state][index].prev_state;
  }
}

inline int ConvCodeTrellis::getPrevOut(int state, int index, size_t step,size_t path_length) const
{
  if(DEBUG) {
    if(step < 0 || step >= path_length) {
      throw std::logic_error("inline int ConvCodeTrellis::getPrevOut(int state, int input, "
                             "size_t step) const : error 1");
    }
  }
  if(!isTerminationStep(path_length,step)) {
    return back[state][index].output;
  }
  else {
    return terminationBack[state][index].output;
  }
}

inline int ConvCodeTrellis::getPrevIn(int state, int index, size_t step,size_t path_length) const
{
  if(DEBUG) {
    if(step < 0 || step >= path_length) {
      throw std::logic_error("inline int ConvCodeTrellis::getPrevIn(int state, int input, "
                             "size_t step) const : error 1");
    }
  }
  if(!isTerminationStep(path_length,step)) {
    return back[state][index].input;
  }
  else {
    return terminationBack[state][index].input;
  }
}
inline const Trellis::TrellisStatesArray&
ConvCodeTrellis::getPrevTrellisArray(size_t step, size_t path_length) const
{
  if(DEBUG) {
    if(step < 0 || step >= path_length) {
      throw std::logic_error("inline int ConvCodeTrellis::getPrevIn(int state, int input, "
                             "size_t step) const : error 1");
    }
  }
  if(!isTerminationStep(path_length,step)) {
    return back;
  }
  else {
    return terminationBack;
  }
}




class ConvCodeTrellisShiftRegister : public ConvCodeTrellis
{
  public:

    ConvCodeTrellisShiftRegister(int symbolsPerStep,
                    const simth::checkedVector<int>& polynomials, int recursivePolynomial, bool systematic);

    ConvCodeTrellisShiftRegister(int symbolsPerStep, 
                 int bitsPerSymbol,StartingMode startingMode,
                 map_type mappMode,
                 const simth::checkedVector<int>& polynomials, 
                 int recursivePolynomial, bool systematic=false);



    virtual ~ConvCodeTrellisShiftRegister();


    int symbolsPerStep() const {return symbolsPerStep_;}
    int bitsPerSymbol() const {return bitsPerSymbol_;}

    virtual void print(std::ostream &os) const;

 protected:

    virtual bool isPossibleStartingState(int state) const;

 private:

    ShiftRegister* shiftRegister;
    ShiftRegister* terminationShiftRegister;

    //mapping
    MappingScheme* usedMapping;

    int symbolsPerStep_;
    int bitsPerSymbol_;

    //Initializes the array of the base class ConvCodeTrellis:
    void initTrellis();
};



//++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++


class ConvCodeTrellisExplicit : public ConvCodeTrellis
{
  public:

    ConvCodeTrellisExplicit(int inbits, int outbits, StartingMode startingMode,map_type mappMode);

     /* Constructor that allows to set each parameter explicitly.
        
        The second argument specifies the bits per input symbol. For a conventional binary
        code this argument equals one. In this case the input symbols are actually input bits. 
        Hence in this case the first parameter sets the number of input bits.    
 
        @param symbolsPerStep  The number of input symbols per step (or bits, see above)
        @param bitsPerSymbol   The number of bits per input symbol
        @param startingMode    For conventional codes the starting mode should be set to 'ZERO'.
        @param mappMode        For conventional codes the mapping mode should be set to 'NATURAL'
        @param polynomials     The sequence of forward polynomials specifying the code
        @param recursivePolynomial The recursive polynomial (equals 0 for non recursive codes)  
        @param systematic      If true a systematic part is considered
      
    */
    //ConvCodeTrellisExplicit(int symbolsPerStep, int bitsPerSymbol,StartingMode startingMode,
    //              map_type mappMode,
    //              const simth::checkedVector<int>& polynomials, int recursivePolynomial, bool systematic=false);



    virtual ~ConvCodeTrellisExplicit();


    //int symbolsPerStep() const {return symbolsPerStep_;}
    //int bitsPerSymbol() const {return bitsPerSymbol_;}

    virtual void print(std::ostream &os) const;

 protected:

    virtual bool isPossibleStartingState(int state) const;

 private:

    //mapping
    MappingScheme* usedMapping;

    //    int symbolsPerStep_;
    //int bitsPerSymbol_;

    //Initializes the array of the base class ConvCodeTrellis:
    void initTrellis();
};


























class AdachiTrellis : public Trellis
{

  private:

    Trellis::TrellisStatesArray forward;
    //TrellisBranch **forward;

    Trellis::TrellisStatesArray back;
    //TrellisBranch **back;

  protected:

    virtual int getNextState(int state, int input, size_t step,size_t path_length) const;

    virtual int getNextOut(int state, int input, size_t step, size_t path_length) const;

    virtual int getPrevState(int state, int index, size_t step, size_t path_length) const;

    virtual int getPrevOut(int state, int index, size_t step, size_t path_length) const;

    virtual int getPrevIn(int state, int index, size_t step, size_t path_length) const;

    virtual const Trellis::TrellisStatesArray&
      getPrevTrellisArray(size_t time_step, size_t path_length) const;

    virtual bool isPossibleStartingState(int state) const;

    virtual int terminationInput(int state) const;

  public:
    AdachiTrellis(const DiffDemodulator& demod);

    ~AdachiTrellis();

};


inline AdachiTrellis::~AdachiTrellis()
{
  //DelArray2D(forward);
  //DelArray2D(back);
}

inline int AdachiTrellis::getNextState(int state, int input, size_t /*step*/,size_t /*path_length*/) const
{
  return forward[state][input].new_state;
}

inline int AdachiTrellis::getNextOut(int state, int input, size_t /*step*/,size_t /*path_length*/) const
{
  return forward[state][input].output;
}

inline int AdachiTrellis::getPrevState(int state, int index, size_t /*step*/,size_t /*path_length*/) const
{
  return back[state][index].prev_state;
}

inline int AdachiTrellis::getPrevOut(int state, int index, size_t /*step*/,size_t /*path_length*/) const
{
  return back[state][index].output;
}

inline int AdachiTrellis::getPrevIn(int state, int index, size_t /*step*/,size_t /*path_length*/) const
{
  return back[state][index].input;
}
inline const Trellis::TrellisStatesArray&
AdachiTrellis::getPrevTrellisArray(size_t time_step, size_t path_length) const
{
  return back;
}

}



#endif

---