Low density parity check codes: a statistical physics perspective

The modem digital communication systems are made transmission reliable by employing error correction technique for the redundancies. Codes in the low-density parity-check work along the principles of Hamming code, and the parity-check matrix is very sparse, and multiple errors can be corrected. The sparseness of the matrix allows for the decoding process to be carried out by probability propagation methods similar to those employed in Turbo codes. The relation between spin systems in statistical physics and digital error correcting codes is based on the existence of a simple isomorphism between the additive Boolean group and the multiplicative binary group. Shannon proved general results on the natural limits of compression and error-correction by setting up the framework known as information theory. Error-correction codes are based on mapping the original space of words onto a higher dimensional space in such a way that the typical distance between encoded words increases.

Typical performance of low-density parity-check codes over general symmetric channels

Typical performance of low-density parity-check (LDPC) codes over a general binary-input output-symmetric memoryless channel is investigated using methods of statistical mechanics. The binary-input additive-white-Gaussian-noise channel and the binary-input Laplace channel are considered as specific channel noise models.

Statistical mechanics of low-density parity-check codes

We review recent theoretical progress on the statistical mechanics of error correcting codes, focusing on low-density parity-check (LDPC) codes in general, and on Gallager and MacKay-Neal codes in particular. By exploiting the relation between LDPC codes and Ising spin systems with multispin interactions, one can carry out a statistical mechanics based analysis that determines the practical and theoretical limitations of various code constructions, corresponding to dynamical and thermodynamical transitions, respectively, as well as the behaviour of error-exponents averaged over the corresponding code ensemble as a function of channel noise. We also contrast the results obtained using methods of statistical mechanics with those derived in the information theory literature, and show how these methods can be generalized to include other channel types and related communication problems.

Average error exponent in Gallager low-density parity-check codes

We present a theoretical method for a direct evaluation of the average error exponent in Gallager error-correcting codes using methods of statistical physics. Results for the binary symmetric channel(BSC)are presented for codes of both finite and infinite connectivity.

Finite-connectivity spin-glass phase diagrams and low-density parity check codes

We obtain phase diagrams of regular and irregular finite-connectivity spin glasses. Contact is first established between properties of the phase diagram and the performance of low-density parity check (LDPC) codes within the replica symmetric (RS) ansatz. We then study the location of the dynamical and critical transition points of these systems within the one step replica symmetry breaking theory (RSB), extending similar calculations that have been performed in the past for the Bethe spin-glass problem. We observe that the location of the dynamical transition line does change within the RSB theory, in comparison with the results obtained in the RS case. For LDPC decoding of messages transmitted over the binary erasure channel we find, at zero temperature and rate R=14, an RS critical transition point at pc 0.67 while the critical RSB transition point is located at pc 0.7450±0.0050, to be compared with the corresponding Shannon bound 1-R. For the binary symmetric channel we show that the low temperature reentrant behavior of the dynamical transition line, observed within the RS ansatz, changes its location when the RSB ansatz is employed; the dynamical transition point occurs at higher values of the channel noise. Possible practical implications to improve the performance of the state-of-the-art error correcting codes are discussed. © 2006 The American Physical Society.

Average and reliability error exponents in low-density parity-check codes

We present a theoretical method for a direct evaluation of the average and reliability error exponents in low-density parity-check error-correcting codes using methods of statistical physics. Results for the binary symmetric channel are presented for codes of both finite and infinite connectivity.

Analysis of common attacks in public-key cryptosystems based on low-density parity-check codes

The security and reliability of a class of public-key cryptosystems against attacks by unauthorized parties, who had acquired partial knowledge of one or more of the private key components and/or of the message, were discussed. The standard statistical mechanical methods of dealing with diluted spin systems with replica symmetric considerations were analyzed. The dynamical transition which defined decryption success in practical situation was studied. The phase diagrams which showed the dynamical threshold as a function of the partial acquired knowledge of the private key were also presented.

Statistical mechanics of broadcast channels using low-density parity-check codes

We investigate the use of Gallager's low-density parity-check (LDPC) codes in a degraded broadcast channel, one of the fundamental models in network information theory. Combining linear codes is a standard technique in practical network communication schemes and is known to provide better performance than simple time sharing methods when algebraic codes are used. The statistical physics based analysis shows that the practical performance of the suggested method, achieved by employing the belief propagation algorithm, is superior to that of LDPC based time sharing codes while the best performance, when received transmissions are optimally decoded, is bounded by the time sharing limit.

Influence of check and field size on the visual evoked magnetic response to a pattern shift stimulus

A decrease in the check size of a pattern shift stimulus increases the latency and amplitude of the visual evoked potential (VEP) P100. In addition, for a given check size, decreasing the size of the stimulus field increases the latency and amplitude of the P100. These results imply that the central regions of the retina make a significant contribution to the generation of the electrical P100. However, the corresponding magnetic P100m may have a different origin. We have studied the effects of check and field size on the P100m in five normal subjects using a DC-Squid, second-order gradiometer. Magnetic responses were recorded at the positive maximum of the P100m over the occipital scalp to six check sizes (10-100') presented in a large (13 degrees 34') and small (5 degrees 14') field and to a large check (100') presented in seven field sizes (1 degree 45' - 15 degrees 10'). No responses were recorded to any check size with a small field. Decreasing the check size presented in a large field increased latency of the P100m by approx. 30 ms while the amplitude of the response decreased with the largest reduction occurring between 70' and 12' checks. Using a large check, latency increased and amplitude decreased as the field size was reduced. The latency changes in response to check and field size were similar to those described for the VEP although the magnitudes of the magnetic changes were greater. Unlike the VEP, amplitude responses were maximal when large checks were presented in a large stimulus field. This suggests that regions outside the central retina make a more significant contribution to the visual evoked magnetic response than they do to the VEP, and that the P100m may be useful clinically in the study of diseases that affect the more peripheral regions of the retina.

Predictive gene lists for breast cancer prognosis: a topographic visualisation study

Background: The controversy surrounding the non-uniqueness of predictive gene lists (PGL) of small selected subsets of genes from very large potential candidates as available in DNA microarray experiments is now widely acknowledged 1. Many of these studies have focused on constructing discriminative semi-parametric models and as such are also subject to the issue of random correlations of sparse model selection in high dimensional spaces. In this work we outline a different approach based around an unsupervised patient-specific nonlinear topographic projection in predictive gene lists. Methods: We construct nonlinear topographic projection maps based on inter-patient gene-list relative dissimilarities. The Neuroscale, the Stochastic Neighbor Embedding(SNE) and the Locally Linear Embedding(LLE) techniques have been used to construct two-dimensional projective visualisation plots of 70 dimensional PGLs per patient, classifiers are also constructed to identify the prognosis indicator of each patient using the resulting projections from those visualisation techniques and investigate whether a-posteriori two prognosis groups are separable on the evidence of the gene lists. A literature-proposed predictive gene list for breast cancer is benchmarked against a separate gene list using the above methods. Generalisation ability is investigated by using the mapping capability of Neuroscale to visualise the follow-up study, but based on the projections derived from the original dataset. Results: The results indicate that small subsets of patient-specific PGLs have insufficient prognostic dissimilarity to permit a distinction between two prognosis patients. Uncertainty and diversity across multiple gene expressions prevents unambiguous or even confident patient grouping. Comparative projections across different PGLs provide similar results. Conclusion: The random correlation effect to an arbitrary outcome induced by small subset selection from very high dimensional interrelated gene expression profiles leads to an outcome with associated uncertainty. This continuum and uncertainty precludes any attempts at constructing discriminative classifiers. However a patient's gene expression profile could possibly be used in treatment planning, based on knowledge of other patients' responses. We conclude that many of the patients involved in such medical studies are intrinsically unclassifiable on the basis of provided PGL evidence. This additional category of 'unclassifiable' should be accommodated within medical decision support systems if serious errors and unnecessary adjuvant therapy are to be avoided.

Interactive online health promotion interventions : a “health check”

As an increasingly popular medium by which to access health promotion information, the Internet offers significant potential to promote (often individualized) health-related behavioral change across broad populations. Interactive online health promotion interventions are a key means, therefore, by which to empower individuals to make important well being and treatment decisions. But how ldquohealthyrdquo are interactive online health promotion interventions? This paper discusses a literature review (or ldquohealth checkrdquo) of interactive online health interventions. It highlights the types of interactive interventions currently available and identifies areas in which research attention is needed in order to take full advantage for the Internet for effective health promotion.

Interactive online health promotion interventions:a “health check”

As an increasingly popular medium by which to access health promotion information, the Internet offers significant potential to promote (often individualized) health-related behavioral change across broad populations. Interactive online health promotion interventions are a key means, therefore, by which to empower individuals to make important well being and treatment decisions. But how ldquohealthyrdquo are interactive online health promotion interventions? This paper discusses a literature review (or ldquohealth checkrdquo) of interactive online health interventions. It highlights the types of interactive interventions currently available and identifies areas in which research attention is needed in order to take full advantage for the Internet for effective health promotion.

Advanced decoding technics for law density parity check codes decoding

DUE TO COPYRIGHT RESTRICTIONS ONLY AVAILABLE FOR CONSULTATION AT ASTON UNIVERSITY LIBRARY AND INFORMATION SERVICES WITH PRIOR ARRANGEMENT