User login 
codingCoding Theory and applications Lowering the error floor of Gallager codes: a statisticalmechanical viewThe problem of error correction for Gallager's lowdensity paritycheck codes is notoriously equivalent to that of computing marginal Boltzmann probabilities for an Isinglike model with multispin interactions in a nonuniform magnetic field. Since the graph of interactions is locally a tree, the solution is very well approximated by a generalized meanfield (BethePeierls) approximation. Belief propagation (BP) and similar iterative algorithms are an efficient way to perform the calculation, but they sometimes fail to converge, or converge to noncodewords, giving rise to a nonnegligible residual error probability (error floor). On the other hand, provablyconvergent algorithms are far too complex to be implemented in a real decoder. In this work we consider the application of the probabilitydamping technique, which can be regarded either as a variant of BP, from which it retains the property of low complexity, or as an approximation of a provablyconvergent algorithm, from which it is expected to inherit better convergence properties. We investigate the algorithm behaviour on a real instance of Gallager code, and compare the results with stateoftheart algorithms. Date:
Thu, 18/12/2014  14:30
Speaker:
Marco Pretti (Politecnico Torino)
Place:
Sala Affrescata, HuGeF, Molecular Biology Center (MBC), Via Nizza 52
RBP algorithm for lossy compression in reduced, ultrasparse GF(q) codes
This code implements a novel data compression technique for binary symmetric sources based on the cavity method over GF(q), the Galois Field of order q. We present a scheme of low complexity and nearoptimal empirical performance. The compression step is based on a reduction of a sparse lowdensity paritycheck code over GF(q) and is done through the socalled reinforced beliefpropagation equations. These reduced codes appear to have a nontrivial geometrical modification of the space of codewords, which makes such compression computationally feasible.
Efficient LDPC Codes over GF(q) for Lossy Data Compression
Efficient LDPC Codes over GF(q) for Lossy Data Compression. In: IEEE International Symposium on Information Theory, 2009. ISIT 2009. Seul, Korea; 2009.
MessagePassing Algorithms for NonLinear Nodes and Data Compression
MessagePassing Algorithms for NonLinear Nodes and Data Compression. ComPlexUs. 2006;3:5865.
Statistical physics, optimization and source coding
Statistical physics, optimization and source coding. Pramana. 2005;64:116173.
Source coding by efficient selection of groundstate clusters.
Source coding by efficient selection of groundstate clusters. Phys Rev E. Stat Nonlin Soft Matter Phys. 2005;72:015103.
