Error correcting codes

Software (available under GPLv3+ license)

ldpcc.c — subroutines for iterative and linear programming decoding
- version 3.2.3, 2011-05-16
  subroutines grow_lp_cone_cross_section() and lp_search2() [cs.IT/1102.3902] are added
  send_msg_w2b_calc_h() is pulled out of decoding subroutines
  debugging output in memory allocations is added
- version 3.2.2, 2010-05-08
  subroutine lp_search() [cs.IT/0601113] is added
  memory allocation bug in read_short_H_matrix() is fixed
  a model channel (isotropic_erasure_channel) is added
  verbosity level is reduced
- version 3.2.1, 2009-06-05
  first version of ldpcc.c posted online
programs using ldpcc.c
- id_mc_awgn.c (+id_mc_processing.c) and lp_mc_awgn.c — Monte Carlo simulations
- instanton.c — finding instantons for iterative decoding with large number of iterations
  
  M. Stepanov, Instantons causing iterative decoding to cycle [cs.IT/1108.5547].
- lp_search.c, lp_search2.c — finding low-weight pseudocodewords for linear programming decoding
  
  M. Chertkov, M.G. Stepanov, An efficient pseudocodeword search algorithm for linear programming decoding of LDPC codes, IEEE Trans. Inf. Theory 54 (4) 1514–1520 (2008) [cs.IT/0601113].
  M. Chertkov, M. Stepanov, Polytope of correct (linear programming) decoding and low-weight pseudo-codewords — in IEEE 2011 Intl. Symp. Inf. Theory (St. Petersburg, Russia, July 31–August 5, 2011) [cs.IT/1102.3902].

Tanner's [155, 64, 20] code

&xi_A (weight < 11.475333) and &xi_B (weight ≈ 11.4996) instantons withstanding 100 iterations (AWGN channel)
M. Stepanov, Instantons causing iterative decoding to cycle [cs.IT/1108.5547].
iterative decoder Monte Carlo data
linear programming spectrum (65536 tries, gzipped, about 191 KiB)
linear programming decoder Monte Carlo data

The work on this website was (2008-09–2011-08) supported by NSF grant DMS-0807592 “Asymptotic Performance of Error Correcting Codes”. Any opinions, findings, and conclusions or recommendations expressed here are those of the author(s) and do not necessarily reflect the views of the National Science Foundation.