Main Page | Modules | Namespace List | Class Hierarchy | Alphabetical List | Class List | Directories | File List | Namespace Members | Class Members | File Members

SPUC::Convolutional_Code Class Reference
[Forward Error Correcting Codes]

Binary Convolutional rate 1/n class. More...

#include <convcode.h>

Inheritance diagram for SPUC::Convolutional_Code:

Inheritance graph
[legend]
List of all members.

Public Member Functions

 Convolutional_Code (void)
 Constructor.
virtual ~Convolutional_Code (void)
 Destructor.
void set_code (string type_of_code, int inverse_rate, int constraint_length)
 Set the code according to built-in tables.
void set_generator_polynomials (const ivec &gen, int constraint_length)
 Set generator polynomials. Given in Proakis integer form.
ivec get_generator_polynomials (void)
 Get generator polynomials.
double get_rate (void)
 Return rate of code.
void encode (const bvec &input, bvec &output)
 Encode a binary vector of inputs starting from state set by the set_state function.
bvec encode (const bvec &input)
 Encode a binary vector of inputs starting from state set by the set_state function.
void encode_tail (const bvec &input, bvec &output)
 Encoding that strarts and ends in the zero state.
bvec encode_tail (const bvec &input)
 Encode a binary vector of inputs starting from state set by the set_state function.
void encode_tailbite (const bvec &input, bvec &output)
 Encode a binary vector of inputs using tailbiting.
bvec encode_tailbite (const bvec &input)
 Encode a binary vector of inputs using tailbiting.
void encode_bit (const bin &input, bvec &output)
 Encode a binary bit startinf from the internal encoder state.
bvec encode_bit (const bin &input)
 Encode a binary bit startinf from the internal encoder state.
void init_encoder ()
 Set the encoder internal state in start_state (set by set_start_state()).
void decode_tail (const vec &received_signal, bvec &output)
 Decode a block of encoded data where encode_tail has been used.
bvec decode_tail (const vec &received_signal)
 Decode a block of encoded data where encode_tail has been used.
void decode_tailbite (const vec &received_signal, bvec &output)
 Decode a block of encoded data where encode_tailbite has been used. Tries all start states.
bvec decode_tailbite (const vec &received_signal)
 Decode a block of encoded data where encode_tailbite has been used. Tries all start states.
void decode (const vec &received_signal, bvec &output)
 Viterbi decoding using truncation of memory (default = 5*K).
bvec decode (const vec &received_signal)
 Viterbi decoding using truncation of memory (default = 5*K).
bool inverse_tail (const bvec coded_sequence, bvec &input)
 Calculate the inverse sequence.
void set_start_state (const int state)
 Set encoder and decoder start state. The generator polynomials must be set first.
int get_encoder_state (void)
 Get the current encoder state.
void set_truncation_length (const int length)
 Set memory truncation length. Must be at least K.
int get_truncation_length (void)
 Get memory truncation length.
bool catastrophic (void)
 Check if catastrophic. Returns true if catastrophic.
void distance_profile (llvec &dist_prof, int dmax=100000, bool reverse=false)
 Calculate distance profile. If reverse = true calculate for the reverse code instead.
void calculate_spectrum (Array< llvec > &spectrum, int dmax, int no_terms)
 Calculate spectrum.
int fast (Array< llvec > &spectrum, const int dfree, const int no_terms, const int Cdfree=1000000, const bool test_catastrophic=false)
 Cederwall's fast algorithm.

Protected Member Functions

int next_state (const int instate, const int input)
 Next state from instate given the input.
int previous_state (const int state, const int input)
 The previous state from state given the input.
int weight (const int state, const int input)
 The weight of the transition from given state with the input given.
void weight (const int state, int &w0, int &w1)
 The weight of the two paths (input 0 or 1) from given state.
int weight_reverse (const int state, const int input)
 The weight (of the reverse code) of the transition from given state with the input given.
void weight_reverse (const int state, int &w0, int &w1)
 The weight (of the reverse code) of the two paths (input 0 or 1) from given state.
bvec output_reverse (const int state, const int input)
 Output on transition (backwards) with input from state.
void output_reverse (const int state, bvec &zero_output, bvec &one_output)
 Output on transition (backwards) with input from state.
void calc_metric_reverse (const int state, const vec &rx_codeword, double &zero_metric, double &one_metric)
 Calculate delta metrics for 0 and 1 input branches reaching state \ state.
int get_input (const int state)
 Returns the input that results in state, that is the MSB of state.

Protected Attributes

int n
 Number of generators.
int K
 Constraint length.
int m
 Memory of the encoder.
ivec gen_pol
 Generator polynomials.
ivec gen_pol_rev
 Generator polynomials for the reverse code.
int encoder_state
 The current encoder state.
int start_state
 The encoder start state.
int trunc_length
 The decoder truncation length.
double rate
 The rate of the code.
bvec xor_int_table
 Auxilary table used by the codec.

Related Functions

(Note that these are not member functions.)

int reverse_int (int length, int in)
 Reverses the bitrepresentation of in (of size length) and converts to an integer.
int weight_int (int length, int in)
 Calculate the Hamming weight of the binary representation of in of size length.
int compare_spectra (llvec v1, llvec v2)
 Compare two distance spectra. Return 1 if v1 is less, 0 if v2 less, and -1 if equal.
int compare_spectra (ivec v1, ivec v2, vec weight_profile)
 Compare two distance spectra using a weight profile.

Detailed Description

Binary Convolutional rate 1/n class.

The codes are given as feedforward encoders an given in the Proakis form. That is the binary generators (K-tuples) are converted to octal integers. Observe that the constraint length (K) is defined as the number of meomory cells plus one (as in Proakis).

Encoding is performed with the encode function. Also available is the encode_tail function which automatically add a tail of K-1 zeros and also assume that the encoder starts in the zero state. Observe that decode_tail is used for data encoded with encode_tail, and decode assumes that the memory truncation length either is the default (5*K) or set using the set_truncation_length function.

Example of use: (rate 1/3 constraint length K=7 ODS code using BPSK over AWGN)

  Convolutional_Code code;
  ivec generator(3);
  generator(0)=0133;
  generator(1)=0165;
  generator(2)=0171;
  code.set_generator_polynomials(generator, 7);
  code.set_truncation_length(30);

  bvec bits=randb(100), encoded_bits, decoded_bits;
  vec tx_signal, rx_signal;

  code.encode(bits, encoded_bits);
  tx_signal = bpsk.modulate_bits(encoded_bits);
  rx_signal = tx_signal + sqrt(0.5)*randn(tx_signal.size());
  code.decode(rx_signal, decoded_bits);
Comment: ODS-code stand for Optimum Distance Spectrum Code. For details see T. Ottosson, "Coding, Modulation and Multiuser Decoding for DS-CDMA Systems," Ph.d. thesis, Department of Information Theory, Scool of Electrical and Computer Engineering, Chalmers University of Technology, G├Âteborg 1997.

It is also possible to set the generatorpolynomials directly using the builtin tables which consists of: Maximum Free Distance (MFD) Codes of rates R=1/2 through R=1/8 and Optimum Distance Spectrum (ODS) Codes of rates R=1/2 through R=1/4.


Constructor & Destructor Documentation

SPUC::Convolutional_Code::Convolutional_Code void   )  [inline]
 

Constructor.

Here is the call graph for this function:

virtual SPUC::Convolutional_Code::~Convolutional_Code void   )  [inline, virtual]
 

Destructor.


Member Function Documentation

void Convolutional_Code::calc_metric_reverse const int  state,
const vec &  rx_codeword,
double &  zero_metric,
double &  one_metric
[protected]
 

Calculate delta metrics for 0 and 1 input branches reaching state \ state.

void Convolutional_Code::calculate_spectrum Array< llvec > &  spectrum,
int  dmax,
int  no_terms
 

Calculate spectrum.

Calculates both the weight spectrum (Ad) and the information weight spectrum (Cd) and returns it as llvec:s in the 0:th and 1:st component of spectrum, respectively. Suitable for calculating many terms in the spectra (uses an breadth first algorithm). It is assumed that the code is non-catastrophic or else it is a possibility for an eternal loop. dmax = an upper bound on the free distance no_terms = no_terms including the dmax term that should be calculated

Reimplemented in SPUC::Punctured_Convolutional_Code.

bool Convolutional_Code::catastrophic void   ) 
 

Check if catastrophic. Returns true if catastrophic.

Reimplemented in SPUC::Punctured_Convolutional_Code.

bvec SPUC::Convolutional_Code::decode const vec &  received_signal  )  [inline]
 

Viterbi decoding using truncation of memory (default = 5*K).

Reimplemented in SPUC::Punctured_Convolutional_Code.

Here is the call graph for this function:

void Convolutional_Code::decode const vec &  received_signal,
bvec &  output
 

Viterbi decoding using truncation of memory (default = 5*K).

Reimplemented in SPUC::Punctured_Convolutional_Code.

bvec SPUC::Convolutional_Code::decode_tail const vec &  received_signal  )  [inline]
 

Decode a block of encoded data where encode_tail has been used.

Reimplemented in SPUC::Punctured_Convolutional_Code.

Here is the call graph for this function:

void Convolutional_Code::decode_tail const vec &  received_signal,
bvec &  output
 

Decode a block of encoded data where encode_tail has been used.

Thus is assumes a decoder start state of zero and that a tail of K-1 zeros has been added. No memory truncation.

Reimplemented in SPUC::Punctured_Convolutional_Code.

bvec SPUC::Convolutional_Code::decode_tailbite const vec &  received_signal  )  [inline]
 

Decode a block of encoded data where encode_tailbite has been used. Tries all start states.

Here is the call graph for this function:

void Convolutional_Code::decode_tailbite const vec &  received_signal,
bvec &  output
 

Decode a block of encoded data where encode_tailbite has been used. Tries all start states.

void Convolutional_Code::distance_profile llvec &  dist_prof,
int  dmax = 100000,
bool  reverse = false
 

Calculate distance profile. If reverse = true calculate for the reverse code instead.

bvec SPUC::Convolutional_Code::encode const bvec &  input  )  [inline]
 

Encode a binary vector of inputs starting from state set by the set_state function.

Reimplemented in SPUC::Punctured_Convolutional_Code.

Here is the call graph for this function:

void Convolutional_Code::encode const bvec &  input,
bvec &  output
 

Encode a binary vector of inputs starting from state set by the set_state function.

Reimplemented in SPUC::Punctured_Convolutional_Code.

bvec SPUC::Convolutional_Code::encode_bit const bin input  )  [inline]
 

Encode a binary bit startinf from the internal encoder state.

Here is the call graph for this function:

void Convolutional_Code::encode_bit const bin input,
bvec &  output
 

Encode a binary bit startinf from the internal encoder state.

To initialize the encoder state use set_start_state() and init_encoder()

bvec SPUC::Convolutional_Code::encode_tail const bvec &  input  )  [inline]
 

Encode a binary vector of inputs starting from state set by the set_state function.

Reimplemented in SPUC::Punctured_Convolutional_Code.

Here is the call graph for this function:

void Convolutional_Code::encode_tail const bvec &  input,
bvec &  output
 

Encoding that strarts and ends in the zero state.

Encode a binary vector of inputs starting from zero state and also adds a tail of K-1 zeros to force the encoder into the zero state. Well suited for packet transmission.

Reimplemented in SPUC::Punctured_Convolutional_Code.

bvec SPUC::Convolutional_Code::encode_tailbite const bvec &  input  )  [inline]
 

Encode a binary vector of inputs using tailbiting.

Here is the call graph for this function:

void Convolutional_Code::encode_tailbite const bvec &  input,
bvec &  output
 

Encode a binary vector of inputs using tailbiting.

int Convolutional_Code::fast Array< llvec > &  spectrum,
const int  dfree,
const int  no_terms,
const int  Cdfree = 1000000,
const bool  test_catastrophic = false
 

Cederwall's fast algorithm.

See IT No. 6, pp. 1146-1159, Nov. 1989 for details. Calculates both the weight spectrum (Ad) and the information weight spectrum (Cd) and returns it as llvec:s in the 0:th and 1:st component of spectrum, respectively. The FAST algorithm is good for calculating only a few terms in the spectrum. If many terms are desired, use calc_spectrum instead. The algorithm returns -1 if the code tested is worse that the input dfree and Cdfree. It returns 0 if the code MAY be catastrophic (assuming that test_catastrophic is true), and returns 1 if everything went right.

  • dfree the free distance of the code (or an upper bound)
  • no_terms including the dfree term that should be calculated
  • Cdfree is the best value of information weight spectrum found so far

int SPUC::Convolutional_Code::get_encoder_state void   )  [inline]
 

Get the current encoder state.

ivec SPUC::Convolutional_Code::get_generator_polynomials void   )  [inline]
 

Get generator polynomials.

Reimplemented in SPUC::Punctured_Convolutional_Code.

int SPUC::Convolutional_Code::get_input const int  state  )  [inline, protected]
 

Returns the input that results in state, that is the MSB of state.

double SPUC::Convolutional_Code::get_rate void   )  [inline]
 

Return rate of code.

Reimplemented in SPUC::Punctured_Convolutional_Code.

int SPUC::Convolutional_Code::get_truncation_length void   )  [inline]
 

Get memory truncation length.

void SPUC::Convolutional_Code::init_encoder  )  [inline]
 

Set the encoder internal state in start_state (set by set_start_state()).

Reimplemented in SPUC::Punctured_Convolutional_Code.

bool Convolutional_Code::inverse_tail const bvec  coded_sequence,
bvec &  input
 

Calculate the inverse sequence.

Assumes that encode_tail is used in the encoding process. Returns false if there is an error in the coded sequence (not a valid codeword). Do not check that the tail forces the encoder into the zeroth state.

Reimplemented in SPUC::Punctured_Convolutional_Code.

int SPUC::Convolutional_Code::next_state const int  instate,
const int  input
[inline, protected]
 

Next state from instate given the input.

void Convolutional_Code::output_reverse const int  state,
bvec &  zero_output,
bvec &  one_output
[protected]
 

Output on transition (backwards) with input from state.

bvec Convolutional_Code::output_reverse const int  state,
const int  input
[protected]
 

Output on transition (backwards) with input from state.

int SPUC::Convolutional_Code::previous_state const int  state,
const int  input
[inline, protected]
 

The previous state from state given the input.

void Convolutional_Code::set_code string  type_of_code,
int  inverse_rate,
int  constraint_length
 

Set the code according to built-in tables.

The type_of_code can be either MFD or ODS for maximum free distance codes (according to Proakis) or Optimum Distance Spectrum Codes accoring to Frenger, Orten and Ottosson.

Reimplemented in SPUC::Punctured_Convolutional_Code.

void Convolutional_Code::set_generator_polynomials const ivec &  gen,
int  constraint_length
 

Set generator polynomials. Given in Proakis integer form.

Reimplemented in SPUC::Punctured_Convolutional_Code.

void SPUC::Convolutional_Code::set_start_state const int  state  )  [inline]
 

Set encoder and decoder start state. The generator polynomials must be set first.

void SPUC::Convolutional_Code::set_truncation_length const int  length  )  [inline]
 

Set memory truncation length. Must be at least K.

void Convolutional_Code::weight const int  state,
int &  w0,
int &  w1
[protected]
 

The weight of the two paths (input 0 or 1) from given state.

int Convolutional_Code::weight const int  state,
const int  input
[protected]
 

The weight of the transition from given state with the input given.

void Convolutional_Code::weight_reverse const int  state,
int &  w0,
int &  w1
[protected]
 

The weight (of the reverse code) of the two paths (input 0 or 1) from given state.

int Convolutional_Code::weight_reverse const int  state,
const int  input
[protected]
 

The weight (of the reverse code) of the transition from given state with the input given.


Friends And Related Function Documentation

int compare_spectra ivec  v1,
ivec  v2,
vec  weight_profile
[related]
 

Compare two distance spectra using a weight profile.

Return 1 if v1 is less, 0 if v2 less, and -1 if equal.

int compare_spectra llvec  v1,
llvec  v2
[related]
 

Compare two distance spectra. Return 1 if v1 is less, 0 if v2 less, and -1 if equal.

int reverse_int int  length,
int  in
[related]
 

Reverses the bitrepresentation of in (of size length) and converts to an integer.

int weight_int int  length,
int  in
[related]
 

Calculate the Hamming weight of the binary representation of in of size length.


Member Data Documentation

int SPUC::Convolutional_Code::encoder_state [protected]
 

The current encoder state.

ivec SPUC::Convolutional_Code::gen_pol [protected]
 

Generator polynomials.

ivec SPUC::Convolutional_Code::gen_pol_rev [protected]
 

Generator polynomials for the reverse code.

int SPUC::Convolutional_Code::K [protected]
 

Constraint length.

int SPUC::Convolutional_Code::m [protected]
 

Memory of the encoder.

int SPUC::Convolutional_Code::n [protected]
 

Number of generators.

double SPUC::Convolutional_Code::rate [protected]
 

The rate of the code.

int SPUC::Convolutional_Code::start_state [protected]
 

The encoder start state.

int SPUC::Convolutional_Code::trunc_length [protected]
 

The decoder truncation length.

bvec SPUC::Convolutional_Code::xor_int_table [protected]
 

Auxilary table used by the codec.


The documentation for this class was generated from the following files:
Generated on Fri Sep 16 11:07:39 2005 for spuc by  doxygen 1.4.4