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

IEICE Transactions on Fundamentals of Electronics Communications and Computer Sciences

Finding Small Fundamental Instantons of LDPC Codes by Path Extension

Junjun Guo, Jianjun Mu, Xiaopeng Jiao, Guiping Li

Published Jan 1, 2014• 1 citation
Publisher

Abstract

In this letter, we present a new scheme to find small fundamental instantons (SFIs) of regular low-density parity-check (LDPC) codes for the linear programming (LP) decoding over the binary symmetric channel (BSC). Based on the fact that each instanton-induced graph (IIG) contains at least one short cycle, we determine potential instantons by constructing possible IIGs which contain short cycles and additional paths connected to the cycles. Then we identify actual instantons from potential ones under the LP decoding. Simulation results on some typical LDPC codes show that our scheme is effective, and more instantons can be obtained by the proposed scheme when compared with the existing instanton search method.

DOI
10.1587/transfun.e97.a.1001

Related papers

An Efficient Instanton Search Algorithm for LP Decoding of LDPC Codes Over the BSC

Shashi Kiran Chilappagari, Michael Chertkov, Bane V. Vasic

We consider linear programming (LP) decoding of a fixed low-density parity-check (LDPC) code over the binary symmetric channel (BSC). The LP decoder fails when it outputs a pseudo-codeword which is not equal to the transmitted codeword. We design an efficient algorithm termed the Instanton Search Algorithm (ISA) which generates an error vector called the BSC-instanton. We prove that: (a) the LP decoder fails for any error pattern with support that is a superset of the support of an instanton; (b) for any input, the ISA outputs an instanton in the number of steps upper-bounded by twice the number of errors in the input error vector. We then find the number of unique instantons of different sizes for a given LDPC code by running the ISA sufficient number of times.

IEEE Transactions on Information Theory•Jun 21, 2011•18 citations

Suppressing Fractional Pseudocodewords by Eliminating Small Instantons

Junjun Guo, Jianjun Mu, Xiaopeng Jiao +1 more

In this letter, a new method is presented to suppress fractional pseudocodewords by eliminating small instantons of irregular low-density parity-check (LDPC) codes under the linear programming (LP) decoding over the binary symmetric channel (BSC). By appending several new rows found by the integer linear programming formulation to the original parity-check matrix, the optimal distribution spectrum of BSC-instantons in the modified code is obtained. Simulation results show that the proposed method can improve the fractional distance of parity-check matrices and considerably enhance the error-correcting performance of irregular LDPC codes under the LP decoding at the cost of a slightly loss of the original code rate.

IEICE Transactions on Fundamentals of Electronics Communications and Computer Sciences•Jan 1, 2016•0 citations

Provably efficient instanton search algorithm for LP decoding of LDPC codes over the BSC

Shashi Kiran Chilappagari, Michael Chertkov, Bane V. Vasic

We consider Linear Programming (LP) decoding of a fixed Low-Density Parity-Check (LDPC) code over the Binary Symmetric Channel (BSC). The LP decoder fails when it outputs a pseudo-codeword which is not a codeword. We design an efficient algorithm termed the Instanton Search Algorithm (ISA) which, given a random input, generates a set of flips called the BSC-instanton. We prove that: (a) the LP decoder fails for any set of flips with support vector including an instanton; (b) for any input, the algorithm outputs an instanton in the number of steps upper-bounded by twice the number of flips in the input. Repeated sufficient number of times, the ISA outcomes the number of unique instantons of different sizes.

arXiv:0808.2515•Aug 19, 2008•3 citations

Analysis of error floor of LDPC codes under LP decoding over the BSC

Chertkov, Michael, Shashi Kiran Chilappagari, Bane V. Vasic +1 more

We consider linear programming (LP) decoding of a fixed low-density parity-check (LDPC) code over the binary symmetric channel (BSC). The LP decoder fails when it outputs a pseudo-codeword which is not a codeword. We propose an efficient algorithm termed the instanton search algorithm (ISA) which, given a random input, generates a set of flips called the BSC-instanton and prove that: (a) the LP decoder fails for any set of flips with support vector including an instanton; (b) for any input, the algorithm outputs an instanton in the number of steps upper-bounded by twice the number of flips in the input. We obtain the number of unique instantons of different sizes by running the ISA sufficient number of times. We then use the instanton statistics to predict the performance of the LP decoding over the BSC in the error floor region. We also propose an efficient semi-analytical method to predict the performance of LP decoding over a large range of transition probabilities of the BSC.

•Jan 1, 2009•1 citation

Analysis of error floors of LDPC codes under LP decoding over the BSC

Shashi Kiran Chilappagari, Bane V. Vasic, Mikhail Stepanov +1 more

We consider linear programming (LP) decoding of a fixed low-density parity-check (LDPC) code over the binary symmetric channel (BSC). The LP decoder fails when it outputs a pseudo-codeword which is not a codeword. We propose an efficient algorithm termed the instanton search algorithm (ISA) which, given a random input, generates a set of flips called the BSC-instanton and prove that: (a) the LP decoder fails for any set of flips with support vector including an instanton; (b) for any input, the algorithm outputs an instanton in the number of steps upper-bounded by twice the number of flips in the input. We obtain the number of unique instantons of different sizes by running the ISA sufficient number of times. We then use the instanton statistics to predict the performance of the LP decoding over the BSC in the error floor region. We also propose an efficient semi-analytical method to predict the performance of LP decoding over a large range of transition probabilities of the BSC.

IEEE International Symposium on Information Theory (ISIT)•Jun 1, 2009•4 citations

Instanton-based techniques for analysis and reduction of error floors of LDPC codes

Shashi Kiran Chilappagari, Michael Chertkov, Mikhail Stepanov +1 more

We describe a family of instanton-based optimization methods developed recently for the analysis of the error floors of low-density parity-check (LDPC) codes. Instantons are the most probable configurations of the channel noise which result in decoding failures. We show that the general idea and the respective optimization technique are applicable broadly to a variety of channels, discrete or continuous, and variety of sub-optimal decoders. Specifically, we consider: iterative belief propagation (BP) decoders, Gallager type decoders, and linear programming (LP) decoders performing over the additive white Gaussian noise channel (AWGNC) and the binary symmetric channel (BSC). The instanton analysis suggests that the underlying topological structures of the most probable instanton of the same code but different channels and decoders are related to each other. Armed with this understanding of the graphical structure of the instanton and its relation to the decoding failures, we suggest a method to construct codes whose Tanner graphs are free of these structures, and thus have less significant error floors.

arXiv:0903.1624•IEEE Journal on Selected Areas in Communications•Jul 29, 2009•41 citations
In this letter, we present a new scheme to find small fundamental instantons (SFIs) of regular low-density parity-check (LDPC) codes for the linear programming (LP) decoding over the binary symmetric channel (BSC). Based on the fact that each instanton-induced graph (IIG) contains at least one short cycle, we determine potential instantons by constructing possible IIGs which contain short cycles and additional paths connected to the cycles. Then we identify actual instantons from potential ones under the LP decoding. Simulation results on some typical LDPC codes show that our scheme is effective, and more instantons can be obtained by the proposed scheme when compared with the existing instanton search method.
We consider linear programming (LP) decoding of a fixed low-density parity-check (LDPC) code over the binary symmetric channel (BSC). The LP decoder fails when it outputs a pseudo-codeword which is not equal to the transmitted codeword. We design an efficient algorithm termed the Instanton Search Algorithm (ISA) which generates an error vector called the BSC-instanton. We prove that: (a) the LP decoder fails for any error pattern with support that is a superset of the support of an instanton; (b) for any input, the ISA outputs an instanton in the number of steps upper-bounded by twice the number of errors in the input error vector. We then find the number of unique instantons of different sizes for a given LDPC code by running the ISA sufficient number of times.
In this letter, a new method is presented to suppress fractional pseudocodewords by eliminating small instantons of irregular low-density parity-check (LDPC) codes under the linear programming (LP) decoding over the binary symmetric channel (BSC). By appending several new rows found by the integer linear programming formulation to the original parity-check matrix, the optimal distribution spectrum of BSC-instantons in the modified code is obtained. Simulation results show that the proposed method can improve the fractional distance of parity-check matrices and considerably enhance the error-correcting performance of irregular LDPC codes under the LP decoding at the cost of a slightly loss of the original code rate.
We consider Linear Programming (LP) decoding of a fixed Low-Density Parity-Check (LDPC) code over the Binary Symmetric Channel (BSC). The LP decoder fails when it outputs a pseudo-codeword which is not a codeword. We design an efficient algorithm termed the Instanton Search Algorithm (ISA) which, given a random input, generates a set of flips called the BSC-instanton. We prove that: (a) the LP decoder fails for any set of flips with support vector including an instanton; (b) for any input, the algorithm outputs an instanton in the number of steps upper-bounded by twice the number of flips in the input. Repeated sufficient number of times, the ISA outcomes the number of unique instantons of different sizes.
We consider linear programming (LP) decoding of a fixed low-density parity-check (LDPC) code over the binary symmetric channel (BSC). The LP decoder fails when it outputs a pseudo-codeword which is not a codeword. We propose an efficient algorithm termed the instanton search algorithm (ISA) which, given a random input, generates a set of flips called the BSC-instanton and prove that: (a) the LP decoder fails for any set of flips with support vector including an instanton; (b) for any input, the algorithm outputs an instanton in the number of steps upper-bounded by twice the number of flips in the input. We obtain the number of unique instantons of different sizes by running the ISA sufficient number of times. We then use the instanton statistics to predict the performance of the LP decoding over the BSC in the error floor region. We also propose an efficient semi-analytical method to predict the performance of LP decoding over a large range of transition probabilities of the BSC.
We consider linear programming (LP) decoding of a fixed low-density parity-check (LDPC) code over the binary symmetric channel (BSC). The LP decoder fails when it outputs a pseudo-codeword which is not a codeword. We propose an efficient algorithm termed the instanton search algorithm (ISA) which, given a random input, generates a set of flips called the BSC-instanton and prove that: (a) the LP decoder fails for any set of flips with support vector including an instanton; (b) for any input, the algorithm outputs an instanton in the number of steps upper-bounded by twice the number of flips in the input. We obtain the number of unique instantons of different sizes by running the ISA sufficient number of times. We then use the instanton statistics to predict the performance of the LP decoding over the BSC in the error floor region. We also propose an efficient semi-analytical method to predict the performance of LP decoding over a large range of transition probabilities of the BSC.
We describe a family of instanton-based optimization methods developed recently for the analysis of the error floors of low-density parity-check (LDPC) codes. Instantons are the most probable configurations of the channel noise which result in decoding failures. We show that the general idea and the respective optimization technique are applicable broadly to a variety of channels, discrete or continuous, and variety of sub-optimal decoders. Specifically, we consider: iterative belief propagation (BP) decoders, Gallager type decoders, and linear programming (LP) decoders performing over the additive white Gaussian noise channel (AWGNC) and the binary symmetric channel (BSC). The instanton analysis suggests that the underlying topological structures of the most probable instanton of the same code but different channels and decoders are related to each other. Armed with this understanding of the graphical structure of the instanton and its relation to the decoding failures, we suggest a method to construct codes whose Tanner graphs are free of these structures, and thus have less significant error floors.