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

Globecom

Design of Irregular LDPC Codes without Markers for Insertion/Deletion Channels

Ryo Shibata, Gou Hosoya, Hiroyuki Yashima

Published Dec 1, 2019• 9 citations
Publisher

Abstract

Over the past two decades, irregular low-density parity-check (LDPC) codes have been hardly able to decode information corrupted by insertion and deletion (ID) errors without markers. Surprisingly, in this paper, we bring to light the existence of irregular LDPC codes that approach the theoretical limit of the channel with ID errors even without markers. These codes contain high fractions of low-degree check nodes that do not appear in irregular codes for other channels. This motivates us to investigate the contribution of low-degree check nodes to correcting ID errors. The investigation provides the following interesting result: degree-2 check nodes are critical to approaching the theoretical limit even without markers, codes with only degree-3, 4, or more check nodes provide moderate decoding performance, and codes with only degree-5 or more check nodes can hardly correct ID errors. Finally, we present simulation results that confirm the excellent decoding performance of the irregular codes without markers.

DOI
10.1109/globecom38437.2019.9014209

Related papers

Design of capacity-approaching irregular low-density parity-check codes

Tom Richardson, Mohammad Amin Shokrollahi, Rudiger L. Urbanke

We design low-density parity-check (LDPC) codes that perform at rates extremely close to the Shannon capacity. The codes are built from highly irregular bipartite graphs with carefully chosen degree patterns on both sides. Our theoretical analysis of the codes is based on the work of Richardson and Urbanke (see ibid., vol.47, no.2, p.599-618, 2000). Assuming that the underlying communication channel is symmetric, we prove that the probability densities at the message nodes of the graph possess a certain symmetry. Using this symmetry property we then show that, under the assumption of no cycles, the message densities always converge as the number of iterations tends to infinity. Furthermore, we prove a stability condition which implies an upper bound on the fraction of errors that a belief-propagation decoder can correct when applied to a code induced from a bipartite graph with a given degree distribution. Our codes are found by optimizing the degree structure of the underlying graphs. We develop several strategies to perform this optimization. We also present some simulation results for the codes found which show that the performance of the codes is very close to the asymptotic theoretical bounds.

IEEE Transactions on Information Theory•Jan 1, 2001•3,336 citations

Studies on Lowering the Error Floors of Finite Length LDPC codes

Huanlin Li

Low-density parity-check (LDPC) codes can approach the Shannon limit performance closely, and are becoming one of the most promising channel codes in the Error Control Coding area.The performance of an LDPC code with given length is mainly affected by the sizes of some combinatorial characteristics of its corresponding bipartite graph and the distribution of variable degrees and check node degrees.With the help of the density evolution algorithm, randomly designed LDPC codes, with carefully chosen degree distribution pairs, have been shown to achieve better Shannon capacity performance than their regular counterparts when decoded using the iterative belief propagation (BP) decoding algorithm.However, regular LDPC codes outperform their irregular counterparts in term of their error floors.Therefore, construction of LDPC codes which have both attractive error rate performance and low error floor performance has become an attractive topic.Currently, optimization of variable node degree distribution and check node degree distribution for an LDPC code with given length, which could help the code to achieve good Shannon limit performance, has been extensively studied.In this dissertation, we demonstrate some approaches of improving the error floor performance for a given LDPC code with desired degree distribution pair.The contribution mainly includes three parts.In the first part, the relationship between cycles and unfavorable combinatorial

•Jan 1, 2011•0 citations

An improvement of insertion/deletion/substitution error correction capabilities of LDPC codes using slide decoding

Tooru Shigehiro, Hirohisa Yabe, Keiichi Iwamura

This study investigates insertion, deletion, and substitution error correcting codes constructed with low-density parity-check (LDPC) codes. The studies for insertion/deletion/substitution error correcting codes are few comparing with substitution error correcting codes. We improve insertion/deletion/substitution error correction capabilities of LDPC codes using slide decoding for modified check matrix. Our evaluation shows that the block error rate of the proposed method is lower than that of the conventional method using marker codes.

International Symposium on Information Theory and its Applications•Dec 1, 2012•0 citations

On irregular LDPC codes with quantized message passing decoding

Michael Meidlinger, Gerald Matz

Irregular low-density parity-check (LDPC) codes are among the best codes currently known. Unfortunately, the performance of existing codes may deteriorate substantially with practical finite-precision decoder implementations. This motivates us to extend our previous work on finite-alphabet decoders based on look-up tables (LUTs) to irregular LDPC codes. We devise a joint design of the LUTs used for different node degrees and present a strategy to optimize the degree distribution (DD) of the LDPC code under LUT decoding. Numerical simulations show that with 4-bit LUT decoding the resulting codes outperform state-of-the-art codes with floating point min-sum (MS) decoding.

IEEE International Workshop on Signal Processing Advances in Wireless Communications (SPAWC)•Jul 1, 2017•23 citations

Optimized decoding schedule for irregular LDPC codes

Xuwei Chen, Hui Ling Yu, Youyun Xu

Recently, the concept of layered decoding schedule for Low-Density Parity-Check codes has been introduced. But the advantage of layered decoding schedule for irregular LDPC codes is not as obvious as regular LDPC codes. The major drawback of the layered irregular LDPC codes versus the layered regular LDPC codes is its comparative low convergence decoding speed. Simulation results show that different bit node degrees of irregular LDPC codes significantly contribute to the decoding performance. The decoding performance of bit nodes with different degrees is of great difference. Bit nodes with small degrees always converge slower than larger ones. In this paper, we propose an optimized decoding schedule for irregular LDPC codes to accelerate the decoding convergence rate. Meanwhile, for the irregular LDPC decoder, the faster decoding speed means a higher throughput and almost the same error performance.

IET International Communication Conference on Wireless Mobile and Computing (CCWMC)•Jan 1, 2009•2 citations

Local Loop Removal from Irregular LDPC Codes

Chunjiang Duanmu

In low-density parity-check(LDPC) codes,the small loops between low degree nodes are more detrimental to the decoding performance than those between high degree nodes.In order to reduce small loops,we propose a method of exchanging the edges between nodes.It first removes the small loops between low degree nodes as much as possible,and then removes the small loops from whole LDPC codes under the condition of ensuring the smallest loop between low degree nodes not to be changed.Finally,the simulation result of constructing LDPC codes by the method is compared with that by only removing the small loops from whole LDPC codes.

Computer Era•Jan 1, 2011•0 citations
Over the past two decades, irregular low-density parity-check (LDPC) codes have been hardly able to decode information corrupted by insertion and deletion (ID) errors without markers. Surprisingly, in this paper, we bring to light the existence of irregular LDPC codes that approach the theoretical limit of the channel with ID errors even without markers. These codes contain high fractions of low-degree check nodes that do not appear in irregular codes for other channels. This motivates us to investigate the contribution of low-degree check nodes to correcting ID errors. The investigation provides the following interesting result: degree-2 check nodes are critical to approaching the theoretical limit even without markers, codes with only degree-3, 4, or more check nodes provide moderate decoding performance, and codes with only degree-5 or more check nodes can hardly correct ID errors. Finally, we present simulation results that confirm the excellent decoding performance of the irregular codes without markers.
We design low-density parity-check (LDPC) codes that perform at rates extremely close to the Shannon capacity. The codes are built from highly irregular bipartite graphs with carefully chosen degree patterns on both sides. Our theoretical analysis of the codes is based on the work of Richardson and Urbanke (see ibid., vol.47, no.2, p.599-618, 2000). Assuming that the underlying communication channel is symmetric, we prove that the probability densities at the message nodes of the graph possess a certain symmetry. Using this symmetry property we then show that, under the assumption of no cycles, the message densities always converge as the number of iterations tends to infinity. Furthermore, we prove a stability condition which implies an upper bound on the fraction of errors that a belief-propagation decoder can correct when applied to a code induced from a bipartite graph with a given degree distribution. Our codes are found by optimizing the degree structure of the underlying graphs. We develop several strategies to perform this optimization. We also present some simulation results for the codes found which show that the performance of the codes is very close to the asymptotic theoretical bounds.
Low-density parity-check (LDPC) codes can approach the Shannon limit performance closely, and are becoming one of the most promising channel codes in the Error Control Coding area.The performance of an LDPC code with given length is mainly affected by the sizes of some combinatorial characteristics of its corresponding bipartite graph and the distribution of variable degrees and check node degrees.With the help of the density evolution algorithm, randomly designed LDPC codes, with carefully chosen degree distribution pairs, have been shown to achieve better Shannon capacity performance than their regular counterparts when decoded using the iterative belief propagation (BP) decoding algorithm.However, regular LDPC codes outperform their irregular counterparts in term of their error floors.Therefore, construction of LDPC codes which have both attractive error rate performance and low error floor performance has become an attractive topic.Currently, optimization of variable node degree distribution and check node degree distribution for an LDPC code with given length, which could help the code to achieve good Shannon limit performance, has been extensively studied.In this dissertation, we demonstrate some approaches of improving the error floor performance for a given LDPC code with desired degree distribution pair.The contribution mainly includes three parts.In the first part, the relationship between cycles and unfavorable combinatorial
This study investigates insertion, deletion, and substitution error correcting codes constructed with low-density parity-check (LDPC) codes. The studies for insertion/deletion/substitution error correcting codes are few comparing with substitution error correcting codes. We improve insertion/deletion/substitution error correction capabilities of LDPC codes using slide decoding for modified check matrix. Our evaluation shows that the block error rate of the proposed method is lower than that of the conventional method using marker codes.
Irregular low-density parity-check (LDPC) codes are among the best codes currently known. Unfortunately, the performance of existing codes may deteriorate substantially with practical finite-precision decoder implementations. This motivates us to extend our previous work on finite-alphabet decoders based on look-up tables (LUTs) to irregular LDPC codes. We devise a joint design of the LUTs used for different node degrees and present a strategy to optimize the degree distribution (DD) of the LDPC code under LUT decoding. Numerical simulations show that with 4-bit LUT decoding the resulting codes outperform state-of-the-art codes with floating point min-sum (MS) decoding.
Recently, the concept of layered decoding schedule for Low-Density Parity-Check codes has been introduced. But the advantage of layered decoding schedule for irregular LDPC codes is not as obvious as regular LDPC codes. The major drawback of the layered irregular LDPC codes versus the layered regular LDPC codes is its comparative low convergence decoding speed. Simulation results show that different bit node degrees of irregular LDPC codes significantly contribute to the decoding performance. The decoding performance of bit nodes with different degrees is of great difference. Bit nodes with small degrees always converge slower than larger ones. In this paper, we propose an optimized decoding schedule for irregular LDPC codes to accelerate the decoding convergence rate. Meanwhile, for the irregular LDPC decoder, the faster decoding speed means a higher throughput and almost the same error performance.
In low-density parity-check(LDPC) codes,the small loops between low degree nodes are more detrimental to the decoding performance than those between high degree nodes.In order to reduce small loops,we propose a method of exchanging the edges between nodes.It first removes the small loops between low degree nodes as much as possible,and then removes the small loops from whole LDPC codes under the condition of ensuring the smallest loop between low degree nodes not to be changed.Finally,the simulation result of constructing LDPC codes by the method is compared with that by only removing the small loops from whole LDPC codes.