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

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

#include <convcode.h>

List of all members.

Public Member Functions

Convolutional_Code (void)

Default constructor - sets (0133,0171) code with tail.

virtual ~Convolutional_Code (void)

Destructor.

void set_method (const CONVOLUTIONAL_CODE_METHOD method)

Set encoding and decoding method (Trunc, Tail, or Tailbite).

void set_code (const CONVOLUTIONAL_CODE_TYPE 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) const

Get generator polynomials.

void reset ()

Reset encoder and decoder states.

virtual void decode (const bvec &coded_bits, bvec &decoded_bits)

Decode a bvec of coded data.

virtual bvec decode (const bvec &coded_bits)

Decode a bvec of coded data.

virtual double get_rate (void) const

Return rate of code (not including the rate-loss).

void set_start_state (int state)

Set encoder default start state.

void init_encoder ()

Initialise internal encoder state with start state. Has no effect on Tail and Tailbite methods.

int get_encoder_state (void) const

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

Get memory truncation length.

bool catastrophic (void)

Check if catastrophic. Returns true if catastrophic.

bool inverse_tail (const bvec coded_sequence, bvec &input)

Calculate the inverse sequence.

void distance_profile (ivec &dist_prof, int dmax=100000, bool reverse=false)

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

void calculate_spectrum (Array< ivec > &spectrum, int dmax, int no_terms)

Calculate spectrum.

int fast (Array< ivec > &spectrum, const int dfree, const int no_terms, const int Cdfree=1000000, const bool test_catastrophic=false)

Cederwall's fast algorithm.

virtual void encode (const bvec &input, bvec &output)

Encode an input binary vector using specified method (Tail by default).

virtual bvec encode (const bvec &input)

Encode a bvec of input.

void encode_trunc (const bvec &input, bvec &output)

Encode a binary vector starting from the previous encoder state.

bvec encode_trunc (const bvec &input)

void encode_tail (const bvec &input, bvec &output)

Encoding that starts and ends in the zero state.

bvec encode_tail (const bvec &input)

void encode_tailbite (const bvec &input, bvec &output)

Encode an input binary vector using tailbiting.

bvec encode_tailbite (const bvec &input)

void encode_bit (const bin &input, bvec &output)

Encode a binary bit starting from the internal encoder state.

bvec encode_bit (const bin &input)

virtual void decode (const vec &received_signal, bvec &output)

Decode a block of encoded data using specified method (Tail by default).

virtual bvec decode (const vec &received_signal)

Decode a vec of received data.

virtual void decode_tail (const vec &received_signal, bvec &output)

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

virtual bvec decode_tail (const vec &received_signal)

virtual void decode_tailbite (const vec &received_signal, bvec &output)

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

virtual bvec decode_tailbite (const vec &received_signal)

virtual void decode_trunc (const vec &received_signal, bvec &output)

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

virtual bvec decode_trunc (const vec &received_signal)

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.

void previous_state (const int state, int &S0, int &S1)

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 output_reverse (const int state, int &zero_output, int &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.

void calc_metric (const vec &rx_codeword, vec &delta_metrics)

Calculate delta metrics for all possible codewords.

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.

int no_states

Number of states.

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.

imat output_reverse_int

output in int format for a given state and input

CONVOLUTIONAL_CODE_METHOD cc_method

encoding and decoding method

imat path_memory

Path memory (trellis).

Array< bool > visited_state

Visited states.

vec sum_metric

Metrics accumulator.

int trunc_ptr

Truncated path memory pointer.

int trunc_state

Truncated memory fill state.

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 (ivec v1, ivec 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 and 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 memory cells plus one (as in Proakis).

Encoding is performed with the encode function. The default method for encoding is by adding a tail of K-1 zeros and also assume that the encoder starts in the zero state (the encode_tail() function). Observe that decode() by default also assumes that a tail is added. Both encoding and decoding method can be changed by the set_method() function.

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

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

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

  code.encode_tail(bits, encoded_bits);
  tx_signal = bpsk.modulate_bits(encoded_bits);
  rx_signal = tx_signal + sqrt(0.5)*randn(tx_signal.size());
  code.decode_tail(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, Goteborg 1997.

It is also possible to set the generator polynomials 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.

Member Function Documentation

void itpp::Convolutional_Code::calculate_spectrum	(	Array< ivec > &	spectrum,
		int	dmax,
		int	no_terms
	)

Calculate spectrum.

Calculates both the weight spectrum (Ad) and the information weight spectrum (Cd) and returns it as ivec: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

Observe that there is a risk that some of the integers are overflow if many terms are calculated in the spectrum.

Reimplemented in itpp::Punctured_Convolutional_Code.

References m, next_state(), no_states, itpp::Array< T >::set_size(), itpp::spectrum(), and weight().

void itpp::Convolutional_Code::decode_tail	(	const vec &	received_signal,
		bvec &	output
	)			`[virtual]`

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 itpp::Punctured_Convolutional_Code.

References calc_metric(), get_input(), it_error_if, m, itpp::max(), itpp::Array< T >::mid(), no_states, output_reverse_int, path_memory, previous_state(), sum_metric, and visited_state.

Referenced by decode().

void itpp::Convolutional_Code::decode_tailbite	(	const vec &	received_signal,
		bvec &	output
	)			`[virtual]`

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

The decoding algorithm tries all start states, so the decode_tailbite() is $2^{K-1}$ times more complex than the decode_tail method.

Reimplemented in itpp::Punctured_Convolutional_Code.

References calc_metric(), get_input(), it_error_if, itpp::max(), no_states, output_reverse_int, path_memory, previous_state(), sum_metric, and visited_state.

Referenced by decode().

void itpp::Convolutional_Code::encode_bit	(	const bin &	input,
		bvec &	output
	)

Encode a binary bit starting from the internal encoder state.

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

References encoder_state, gen_pol, m, and xor_int_table.

void itpp::Convolutional_Code::encode_tail	(	const bvec &	input,
		bvec &	output
	)

Encoding that starts 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.

Note:: The init_encoder() function has no effect on the starting state for this method.

Reimplemented in itpp::Punctured_Convolutional_Code.

References encoder_state, gen_pol, m, and xor_int_table.

Referenced by encode().

void itpp::Convolutional_Code::encode_tailbite	(	const bvec &	input,
		bvec &	output
	)

Encode an input binary vector using tailbiting.

In the Tailbiting method the starting state of the encoder is initialised with the last K-1 bits of the input vector. This gives an additional information to the decoder that the starting and ending states are identical, although not known a priori.

Well suited for packet transmission with small packets, because there is no tail overhead as in the Tail method.

Note:: The init_encoder() function has no effect on the starting state for this method.

Reimplemented in itpp::Punctured_Convolutional_Code.

References encoder_state, gen_pol, m, and xor_int_table.

Referenced by encode().

void itpp::Convolutional_Code::encode_trunc	(	const bvec &	input,
		bvec &	output
	)

Encode a binary vector starting from the previous encoder state.

The initial encoder state can be changed using set_start_state() and init_encoder() functions.

Reimplemented in itpp::Punctured_Convolutional_Code.

References encoder_state, gen_pol, m, and xor_int_table.

Referenced by encode().

int itpp::Convolutional_Code::fast	(	Array< ivec > &	spectrum,
		const int	dfree,
		const int	no_terms,
		const int	Cdfree = `1000000`,
		const bool	test_catastrophic = `false`
	)

Cederwall's fast algorithm.

Calculates both the weight spectrum (Ad) and the information weight spectrum (Cd) and returns it as ivec: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

Observe that there is a risk that some of the integers are overflow if many terms are calculated in the spectrum.

See IT No. 6, pp. 1146-1159, Nov. 1989 for details.

References distance_profile(), m, next_state(), itpp::reverse(), itpp::Array< T >::set_size(), itpp::spectrum(), weight(), and weight_reverse().

bool itpp::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 itpp::Punctured_Convolutional_Code.

References gen_pol, it_error_if, m, and xor_int_table.

void itpp::Convolutional_Code::set_code	(	const CONVOLUTIONAL_CODE_TYPE	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 according to Frenger, Orten and Ottosson.

Reimplemented in itpp::Punctured_Convolutional_Code.

References it_assert, and set_generator_polynomials().

Referenced by Convolutional_Code().

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.

The documentation for this class was generated from the following files:


Public Member Functions
	Convolutional_Code (void)
	Default constructor - sets (0133,0171) code with tail.
virtual	~Convolutional_Code (void)
	Destructor.
void	set_method (const CONVOLUTIONAL_CODE_METHOD method)
	Set encoding and decoding method (Trunc, Tail, or Tailbite).
void	set_code (const CONVOLUTIONAL_CODE_TYPE 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) const
	Get generator polynomials.
void	reset ()
	Reset encoder and decoder states.
virtual void	decode (const bvec &coded_bits, bvec &decoded_bits)
	Decode a bvec of coded data.
virtual bvec	decode (const bvec &coded_bits)
	Decode a bvec of coded data.
virtual double	get_rate (void) const
	Return rate of code (not including the rate-loss).
void	set_start_state (int state)
	Set encoder default start state.
void	init_encoder ()
	Initialise internal encoder state with start state. Has no effect on `Tail` and `Tailbite` methods.
int	get_encoder_state (void) const
	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) const
	Get memory truncation length.
bool	catastrophic (void)
	Check if catastrophic. Returns true if catastrophic.
bool	inverse_tail (const bvec coded_sequence, bvec &input)
	Calculate the inverse sequence.
void	distance_profile (ivec &dist_prof, int dmax=100000, bool reverse=false)
	Calculate distance profile. If reverse = true calculate for the reverse code instead.
void	calculate_spectrum (Array< ivec > &spectrum, int dmax, int no_terms)
	Calculate spectrum.
int	fast (Array< ivec > &spectrum, const int dfree, const int no_terms, const int Cdfree=1000000, const bool test_catastrophic=false)
	Cederwall's fast algorithm.

virtual void	encode (const bvec &input, bvec &output)
	Encode an input binary vector using specified method (Tail by default).
virtual bvec	encode (const bvec &input)
	Encode a bvec of input.

void	encode_trunc (const bvec &input, bvec &output)
	Encode a binary vector starting from the previous encoder state.
bvec	encode_trunc (const bvec &input)

void	encode_tail (const bvec &input, bvec &output)
	Encoding that starts and ends in the zero state.
bvec	encode_tail (const bvec &input)

void	encode_tailbite (const bvec &input, bvec &output)
	Encode an input binary vector using tailbiting.
bvec	encode_tailbite (const bvec &input)

void	encode_bit (const bin &input, bvec &output)
	Encode a binary bit starting from the internal encoder state.
bvec	encode_bit (const bin &input)

virtual void	decode (const vec &received_signal, bvec &output)
	Decode a block of encoded data using specified method (Tail by default).
virtual bvec	decode (const vec &received_signal)
	Decode a vec of received data.

virtual void	decode_tail (const vec &received_signal, bvec &output)
	Decode a block of encoded data where encode_tail has been used.
virtual bvec	decode_tail (const vec &received_signal)

virtual void	decode_tailbite (const vec &received_signal, bvec &output)
	Decode a block of encoded data where encode_tailbite has been used.
virtual bvec	decode_tailbite (const vec &received_signal)

virtual void	decode_trunc (const vec &received_signal, bvec &output)
	Viterbi decoding using truncation of memory (default = 5*K).
virtual bvec	decode_trunc (const vec &received_signal)
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.
void	previous_state (const int state, int &S0, int &S1)
	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	output_reverse (const int state, int &zero_output, int &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.
void	calc_metric (const vec &rx_codeword, vec &delta_metrics)
	Calculate delta metrics for all possible codewords.
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.
int	no_states
	Number of states.
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.
imat	output_reverse_int
	output in int format for a given state and input
CONVOLUTIONAL_CODE_METHOD	cc_method
	encoding and decoding method
imat	path_memory
	Path memory (trellis).
Array< bool >	visited_state
	Visited states.
vec	sum_metric
	Metrics accumulator.
int	trunc_ptr
	Truncated path memory pointer.
int	trunc_state
	Truncated memory fill state.
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 (ivec v1, ivec 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.

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

Public Member Functions

Protected Member Functions

Protected Attributes

Related Functions

Detailed Description

Member Function Documentation

Friends And Related Function Documentation

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