Codes on Graphs: A Survey for Algebraists

Saeed Sharifi Tehrani, Shie Mannor, Warren J. Gross

Stochastic computation is a new alternative approach for iterative computation on factor graphs. In this approach, the information is represented by the statistics of the bit stream which results in simple high-speed hardware implementation of graph-based algorithms. Despite the first purpose of its invention (i.e., low-precision digital circuits), the stochastic representation has recently been shown to be able to provide near-optimal decoding performance for practical Low-Density Parity- Check (LDPC) codes, with respect to Sum-Product Algorithm (SPA). This paper provides a survey of stochastic methods for graph-based iterative decoding, the state-of-the-art and, their possible new applications.

G. David Forney

Vasiliy S. Usatyuk

Short survey about code on the graph by example of hardware friendly quasi-cycle LDPC code. We consider two main properties of code: weight enumerator (well known from classic code theory) and Trapping sets pseudocodewords weight spectrum (a subgraph in code graph's which become reasone of decoding failure under Belief propagation). In paper we show fast methods to measure first components of TS enumerator using EMD=ACE constrains for high girth codes on the graph using graph spectral classification method. This approach simplify solving trouble of agreed between minimal TS pseudocode weight and code distance (which can be measure using knowledge of Authomorphism for algebraic code design methods or measure using lattice reduction(LLL,BKZ) for random graph design methods). In the end of article author raise several challenge problems to improve Sparse and Dense parity-check codes decoding under Belief propagation.

Mohammad Amin Shokrollahi

Igal Sason, Shlomo Shitz Shamai

Upper and lower bounds on the error probability of linear codes under maximum-likelihood (ML) decoding are shortly surveyed and applied to ensembles of codes on graphs. For upper bounds, focus is put on Gallager bounding techniques and their relation to a variety of other reported bounds. Within the class of lower bounds, we address de Caen's based bounds and their improvements, sphere-packing bounds, and information-theoretic bounds on the bit error probability of codes defined on graphs. A comprehensive overview is provided in a monograph by the authors which is currently in preparation.

Ross Duncan, Simon Perdrix