Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:cond-mat/0506037 · Physical Review Letters

Diagnosis of Weaknesses in Modern Error Correction Codes: A Physics Approach

М. Г. Степанов, Vladimir Chernyak, Michael Chertkov, Bata Vasić

Published Nov 22, 2005• 76 citations
arXivHTMLPDF

Abstract

One of the main obstacles to the wider use of the modern error-correction codes is that, due to the complex behavior of their decoding algorithms, no systematic method which would allow characterization of the bit-error-rate (BER) is known. This is especially true at the weak noise where many systems operate and where coding performance is difficult to estimate because of the diminishingly small number of errors. We show how the instanton method of physics allows one to solve the problem of BER analysis in the weak noise range by recasting it as a computationally tractable minimization problem.

DOI
10.1103/physrevlett.95.228701

Related papers

The error-floor of LDPC codes in the Laplacian channel

М. Г. Степанов, Misha Chertkov

We analyze the performance of Low-Density-Parity-Check codes in the error-floor domain where the Signal-to-Noise-Ratio, s, is large, s >> 1. We describe how the instanton method of theoretical physics, recently adapted to coding theory, solves the problem of characterizing the error-floor domain in the Laplacian channel. An example of the (155,64,20) LDPC code with four iterations (each iteration consisting of two semi-steps: from bits-to-checks and from checks-to-bits) of the min-sum decoding is discussed. A generalized computational tree analysis is devised to explain the rational structure of the leading instantons. The asymptotic for the symbol Bit-Error-Rate in the error-floor domain is comprised of individual instanton contributions, each estimated as ~ \exp(-l_{inst;L} s), where the effective distances, l_{inst;L}, of the the leading instantons are 7.6, 8.0 and 8.0 respectively. (The Hamming distance of the code is 20.) The analysis shows that the instantons are distinctly different from the ones found for the same coding/decoding scheme performing over the Gaussian channel. We validate instanton results against direct simulations and offer an explanation for remarkable performance of the instanton approximation not only in the extremal, s -> \infty, limit but also at the moderate s values of practical interest.

arXiv:cs/0507031•Jul 12, 2005•4 citations

Instanton method of post-error-correction analytical evaluation

Vladimir Chernyak, Michael Chertkov, М. Г. Степанов +1 more

We present a theoretical tool for evaluation of error code performance on graphs. The method is known under the name of instanton calculus and is common in theoretical physics. We introduce the instanton calculus for linear block codes, and give a closed form expression for the bit error rate for a class of codes whose graphical model is approximated locally by a tree.

Manufacturing Engineer•Apr 6, 2005•11 citations

A Short Introduction to Quantum Error Correction

Thiago Guedes

Abstract As quantum information processing grows into one of the currently most impactful fields in physics and engineering, it becomes indispensable for physicists to understand what challenges lie ahead. This work aims at introducing the main strategies to circumvent the detrimental effects of noise in quantum information processing: the field known as quantum error correction.

Brazilian Journal of Physics•Feb 14, 2026•1 citation

Design and Development of an Improved Split Row Decoding Algorithm with Reduced BER

B. Rajasekar, E. Logashanmugam

An optimized split row algorithm is to be developed to reduce effectively the Bit Error Rate effectively. The usage of LDPC codes, especially in the error correction schemes, is tremendously increasing in the modern era. In the conventional approach, the entire matrix which is computed always leads to computational complexity. As for this, the matrix is split into two equal halves and then error checking is done. In such case, it is difficult to judge which partition has to be taken first. Also, it is necessary to reduce the Bit Error Rate. In this Study a novel technique based on fixing appropriate distance between bits and checking it with a predefined condition. It is also observed that as the number of iterations increases, BER decreases.

Research Journal of Applied Sciences Engineering and Technology•Sep 20, 2014•0 citations

Finding error-correcting codes using computers

Lam Clement

The theory of error-correcting codes is a vast and fast-moving area with many open problems. The objective of this paper is to survey where the current boundaries of knowledge are in a few selected areas, by listing the smallest unsolved cases. Our hope is that these lists will motivate further computational to move these boundaries.

NATO science for peace and security series. D, Information and communication security•Jan 1, 2011•3 citations

Performance Analysis of Different Flexible Decoding Algorithms for NR-LDPC Codes

Layla Mahdi Salih, Thuraya Mahmood Qaradaghi, Jalal J. Hamad Ameen

Channel coding technique is a fundamental building block in any modern communication system to realize reliable, fast, and secure data transmission. At the same time, it is a challenging and crucial task, as the data transmission happens in a channel where noise, fading, and other impairments are present. The Low-Density Parity-Check (LDPC) codes give substantial results close to the Shannon limit when the complexity and processing delay time are unlimited. In this paper, the performance of the LDPC decoding with four algorithms was investigated. The investigated four algorithms were Belief Propagation (BP), Layered Belief Propagation (LBP), Normalized min-sum (NMS), and Offset min-sum (OMS). These algorithms were examined for code rates ranging from 1/3 to 9/10 and message block lengths (64, 512, 1024, and 5120) bits. The simulation results revealed the flexibility of these decoders in supporting these code rates and block lengths, which enables their usage in a wide range of applications and scenarios for fifth-generation (5G) wireless communication. In addition, the effect of the maximum number of decoding iterations on the error correction performance was investigated, and a gain of 5.6 dB can be obtained by using 32 decoding iterations at BER=2*10-3 instead of one decoding iteration. The results showed that the decoders performed better for longer message blocks than for short message blocks, and less power was required for transmitting longer messages. Finally, the comparison results of their performance in terms of bit error rate (BER) under the same conditions showed a gain of 0.8 dB using LBP at BER= 10-5 compared with the NMS decoding algorithm.

Tikrit Journal of Engineering Sciences•Dec 11, 2022•3 citations
One of the main obstacles to the wider use of the modern error-correction codes is that, due to the complex behavior of their decoding algorithms, no systematic method which would allow characterization of the bit-error-rate (BER) is known. This is especially true at the weak noise where many systems operate and where coding performance is difficult to estimate because of the diminishingly small number of errors. We show how the instanton method of physics allows one to solve the problem of BER analysis in the weak noise range by recasting it as a computationally tractable minimization problem.
We analyze the performance of Low-Density-Parity-Check codes in the error-floor domain where the Signal-to-Noise-Ratio, s, is large, s >> 1. We describe how the instanton method of theoretical physics, recently adapted to coding theory, solves the problem of characterizing the error-floor domain in the Laplacian channel. An example of the (155,64,20) LDPC code with four iterations (each iteration consisting of two semi-steps: from bits-to-checks and from checks-to-bits) of the min-sum decoding is discussed. A generalized computational tree analysis is devised to explain the rational structure of the leading instantons. The asymptotic for the symbol Bit-Error-Rate in the error-floor domain is comprised of individual instanton contributions, each estimated as ~ \exp(-l_{inst;L} s), where the effective distances, l_{inst;L}, of the the leading instantons are 7.6, 8.0 and 8.0 respectively. (The Hamming distance of the code is 20.) The analysis shows that the instantons are distinctly different from the ones found for the same coding/decoding scheme performing over the Gaussian channel. We validate instanton results against direct simulations and offer an explanation for remarkable performance of the instanton approximation not only in the extremal, s -> \infty, limit but also at the moderate s values of practical interest.
An optimized split row algorithm is to be developed to reduce effectively the Bit Error Rate effectively. The usage of LDPC codes, especially in the error correction schemes, is tremendously increasing in the modern era. In the conventional approach, the entire matrix which is computed always leads to computational complexity. As for this, the matrix is split into two equal halves and then error checking is done. In such case, it is difficult to judge which partition has to be taken first. Also, it is necessary to reduce the Bit Error Rate. In this Study a novel technique based on fixing appropriate distance between bits and checking it with a predefined condition. It is also observed that as the number of iterations increases, BER decreases.
Channel coding technique is a fundamental building block in any modern communication system to realize reliable, fast, and secure data transmission. At the same time, it is a challenging and crucial task, as the data transmission happens in a channel where noise, fading, and other impairments are present. The Low-Density Parity-Check (LDPC) codes give substantial results close to the Shannon limit when the complexity and processing delay time are unlimited. In this paper, the performance of the LDPC decoding with four algorithms was investigated. The investigated four algorithms were Belief Propagation (BP), Layered Belief Propagation (LBP), Normalized min-sum (NMS), and Offset min-sum (OMS). These algorithms were examined for code rates ranging from 1/3 to 9/10 and message block lengths (64, 512, 1024, and 5120) bits. The simulation results revealed the flexibility of these decoders in supporting these code rates and block lengths, which enables their usage in a wide range of applications and scenarios for fifth-generation (5G) wireless communication. In addition, the effect of the maximum number of decoding iterations on the error correction performance was investigated, and a gain of 5.6 dB can be obtained by using 32 decoding iterations at BER=2*10-3 instead of one decoding iteration. The results showed that the decoders performed better for longer message blocks than for short message blocks, and less power was required for transmitting longer messages. Finally, the comparison results of their performance in terms of bit error rate (BER) under the same conditions showed a gain of 0.8 dB using LBP at BER= 10-5 compared with the NMS decoding algorithm.