itpp::LDPC_Parity_Unstructured Class Reference

Pure abstract class for unstructured LDPC matrices. More...

#include <ldpc.h>

List of all members.

Public Member Functions

virtual void display_stats () const =0
 Display some information about the matrix.
int cycle_removal_MGW (int L)
 Remove cycles (loops) from unstructured parity check matrix.
void initialize (int ncheck, int nvar)
 Initialize an empty matrix of size ncheck x nvar.
GF2mat_sparse get_H (bool transpose=false) const
 Get the parity check matrix, optionally its transposed form.
Sparse_Vec< bin > get_col (int c) const
 Get a specific column from the matrix.
Sparse_Vec< bin > get_row (int r) const
 Get a specific row from the matrix.
int get_nvar () const
 Get the number of variable nodes (number of columns).
int get_ncheck () const
 Get the number of check nodes (number of rows).
void set (int i, int j, bin value)
 Set element (i,j) of the parity check matrix to value.
bin get (int i, int j) const
 Get element (i,j) of the parity check matrix.
bin operator() (int i, int j) const
 Get element (i,j) of the parity check matrix.
double get_rate () const
 Get the code rate.
void import_alist (const GF2mat_sparse_alist &H_alist)
 Import matrix from GF2mat_sparse_alist format.
GF2mat_sparse_alist export_alist () const
 Export matrix to GF2mat_sparse_alist format.
void load_alist (const std::string &alist_file)
 Load matrix from alist_file text file in alist format.
void save_alist (const std::string &alist_file) const
 Save matrix to alist_file text file in alist format.

Protected Member Functions

void generate_random_H (const ivec &C, const ivec &R, const ivec &cycopt)
 Generate a random parity check matrix.
void compute_CR (const vec &var_deg, const vec &chk_deg, const int Nvar, ivec &C, ivec &R)
 Compute target number of columns (C) and rows (R) with a specific number of ones.
int check_for_cycles (int L) const
 Check for cycles of length L.
int check_connectivity (int from_m, int from_n, int to_m, int to_n, int g, int L) const
 Check for connectivity between nodes.

Protected Attributes

bool init_flag
 Flag that indicates proper initialization.
GF2mat_sparse H
 The parity check matrix.
GF2mat_sparse Ht
 The transposed parity check matrix.
int nvar
 Number of variable nodes.
int ncheck
 Number of check nodes.
ivec sumX1
 Actual number of ones in each column.
ivec sumX2
 Actual number of ones in each row.

Static Protected Attributes

static const int Nmax = 200
 Maximum node degree class can handle.

Detailed Description

Pure abstract class for unstructured LDPC matrices.

This class provides a common set of methods for unstructured LDPC matrices. For unstructured codes the parity checks are distributed at random rather than according to a specific pattern, and the generation of a parity matrix can be viewed as drawing a random sample from an ensemble of graphs (matrices) that are described by a specific degree distribution.

This class is used as base for the LDPC_Parity_Irregular and LDPC_Parity_Regular generator classes.

Author:
Erik G. Larsson, Mattias Andersson and Adam Piatyszek

Member Function Documentation

int itpp::LDPC_Parity::check_connectivity ( int  from_m,
int  from_n,
int  to_m,
int  to_n,
int  g,
int  L 
) const [protected, inherited]

Check for connectivity between nodes.

This function examines whether the point (to_m, to_n) in the matrix can be reached from the point (from_m, from_n) using at most L steps. A recursive search is used.

The function can be used to search for cycles in the matrix. To search for a cycle of length L, set from_m=to_m and from_n=to_n, and godir=0.

Parameters:
from_m starting coordinate, row number
to_m goal coordinate, row number
from_n starting coordinate, column number
to_n goal coordinate, row number
g direction: 1=start going vertically, 2=start going horizontally
L number of permitted steps
Returns:
  • -1 or -3 : destination unreachable
  • -2 : meaningless search (started in a "0" point),
  • -4 : meaningless search
  • >=0 : destination reached with certain number of steps left
Note:
This function can be very slow depending on the nature of the matrix.
Note that smaller cycles may appear as longer cycles when using this method. More specifically, suppose the method is run with a given L and there are cycles in the neighborhood of (from_m,from_n) of length L-2 or less, but which do not contain (from_m,from_n). These shorter cycles may then also be reported as a cycle of length L. For example, if one of the immediate neighbors of (from_m,from_n) is part of a cycle of length 4 this method will report that (from_m,from_n) is part of a cycle of length 6, if run with L=6. However, if it is known that there are no cycles of length L-2 or smaller, and check_connectivity(from_m,from_n,from_m,from_n,0,L) returns a non-negative value, then one will know with certainty that the point (from_m,from_n) is part of a cycle of length L. (This behavior is inherent to the simple recursive search used.)

References itpp::LDPC_Parity::get_col(), itpp::Sparse_Vec< T >::get_nz_indices(), itpp::LDPC_Parity::get_row(), itpp::LDPC_Parity::init_flag, it_assert, and itpp::length().

Referenced by itpp::LDPC_Parity::check_for_cycles(), and generate_random_H().

int itpp::LDPC_Parity::check_for_cycles ( int  L  )  const [protected, inherited]

Check for cycles of length L.

This function implements a recursive routine to find loops. The function is mainly a tool for testing and debugging more sophisticated functions for graph manipulation.

Parameters:
L length of cycles to look for
Returns:
The function returns the number of cycles found of length L or shorter. Cycles may be counted multiple times.
Note:
This function can be very slow for large matrices. It is mainly intended as a debugging aid.

References itpp::LDPC_Parity::check_connectivity(), itpp::LDPC_Parity::get_col(), itpp::Sparse_Vec< T >::get_nz_indices(), itpp::LDPC_Parity::init_flag, it_assert, itpp::length(), and itpp::LDPC_Parity::nvar.

void itpp::LDPC_Parity_Unstructured::compute_CR ( const vec &  var_deg,
const vec &  chk_deg,
const int  Nvar,
ivec &  C,
ivec &  R 
) [protected]

Compute target number of columns (C) and rows (R) with a specific number of ones.

Parameters:
var_deg vector of variable degree distributions, from an edge perspective
chk_deg vector of check degree distributions, from an edge perspective
Nvar number of variable nodes
C number of columns with a specific number of ones
R number of rows with a specific number of ones
The result is passed by reference and saved in C and R.

References itpp::find(), it_info_debug, itpp::length(), itpp::linspace(), itpp::max(), itpp::LDPC_Parity::Nmax, itpp::round(), itpp::sum(), itpp::to_ivec(), itpp::to_vec(), and itpp::zeros_i().

Referenced by itpp::LDPC_Parity_Irregular::generate(), and itpp::LDPC_Parity_Regular::generate().

int itpp::LDPC_Parity_Unstructured::cycle_removal_MGW ( int  L  ) 

Remove cycles (loops) from unstructured parity check matrix.

This function implements the cycle removal algorithm presented by McGowan and Williamson at the IT workshop 2003. The maximum girth of the graph that will be attempted is L. The algorithm is bound to remove all loops of length L, insofar this is possible. I.e., it does not terminate until it is impossible to remove more cycles by swapping two edges.

Parameters:
L Target girth. For example, L=6 attempts to removes all 4-cycles.
Returns:
The girth of the graph, i.e. the length of the shortest cycle. For example, a return value of 6 means that there are no 4-cycles.
Note:
This algorithm can take a long time to run for large L or large graphs.

References itpp::floor_i(), itpp::LDPC_Parity::get_col(), itpp::Sparse_Vec< T >::get_nz_index(), itpp::LDPC_Parity::init_flag, it_assert, it_assert_debug, it_info_debug, itpp::length(), itpp::LDPC_Parity::ncheck, itpp::Sparse_Vec< T >::nnz(), itpp::LDPC_Parity::nvar, itpp::randi(), itpp::randu(), and itpp::Array< T >::set_size().

The documentation for this class was generated from the following files:
Generated on Tue Jun 2 10:02:19 2009 for mixpp by  doxygen 1.5.8