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

International Symposium on Information Theory and its Applications

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

Tooru Shigehiro, Hirohisa Yabe, Keiichi Iwamura

Published Dec 1, 2012• 0 citations
OpenAlex

Abstract

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.

Related papers

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

Ryo Shibata, Gou Hosoya, Hiroyuki Yashima

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.

Globecom•Dec 1, 2019•9 citations

Techniques for improving ldpc codes performance

Esa Alghonaim

Low Density Parity Check (LDPC) codes are considered to be one of the best classes of error-correcting codes. This thesis deals with two major issues in LDPC codes: decoder design to enhance error correction performance and efficient decoder implementation. Five techniques have been introduced in this thesis. First, an efficient platform for LDPC code design and performance evaluation is developed. This platform implements parallel simulation algorithms to efficiently evaluate the performance of the proposed algorithms for LDPC decoders and code design. Second, an innovative technique is introduced to improve the performance of LDPC decoding in the error-floor region. Special structures in the code graph, called trapping sets, are considered to be the major source of decoding errors in the error-floor region. The proposed technique is based on eliminating the negative effect of trapping sets during LDPC decoding. As a third contribution, a novel approach to improve the decoder performance and/or throughput is introduced. This approach is based on utilizing LDPC decoder idle times by introducing two queues: one at the decoder input and the other at the decoder output. This architecture enables the decoder to run extra iterations beyond the conventional maximum allowable iterations. The fourth proposed technique reduces the bit error rate of LDPC decoders. This technique is based on tracking the number of failed parity check equations in the intermediate decoding iterations, rather than only relying on the final decoder output (after reaching the maximum number of iterations). The last proposed technique deals with the construction of interconnect efficient fully-parallel LDPC codes with high error correction performance. Fully-parallel implementation is very hard due to the complexity of processing elements interconnections. The proposed technique is based on constructing LDPC codes with less complex interconnections and with low impact on the error correction performance. This goal is achieved by putting a constraint on the maximum connection length between any two processing elements.

•Jan 1, 2008•0 citations

Low-density parity-check codes

Sarah J. Johnson

Introduction In this chapter we introduce low-density parity-check (LDPC) codes, a class of error correction codes proposed by Gallager in his 1962 PhD thesis 12 years after error correction codes were first introduced by Hamming (published in 1950). Both Hamming codes and LDPC codes are block codes: the messages are broken up into blocks to be encoded at the transmitter and similarly decoded as separate blocks at the receiver. While Hamming codes are short and very structured with a known, fixed, error correction ability, LDPC codes are the opposite, usually long and often constructed pseudo-randomly with only a probabilistic notion of their expected error correction performance. The chapter begins by presenting parity bits as a means to detect and, when more than one is employed, to correct errors in digital data. Block error correction codes are described as a linear combination of parity-check equations and thus defined by their parity-check matrix representation. The graphical representation of codes by Tanner graphs is presented and the necessary graph theoretic concepts introduced. In Section 2.4 iterative decoding algorithms are introduced using a hard decision algorithm (bit flipping), so that the topic is developed first without reference to probability theory. Subsequently the sum–product decoding algorithm is presented. This chapter serves as a self-contained introduction to LDPC codes and their decoding. It is intended that the material presented here will enable the reader to implement LDPC encoders and iterative decoders.

Cambridge University Press eBooks•Nov 19, 2009•5 citations

Optimized decoder for low-density parity check codes based on genetic algorithms

Hajar El Ouakili, Mohammed El Ghzaoui, Rachid El Alami

Low-density parity check (LDPC) codes, are a family of error-correcting codes, their performances close to the Shannon limit make them very attractive solutions for digital communication systems. There are several algorithms for decoding LDPC codes that show great diversity in terms of performance related to error correction. Also, very recently, many research papers involved the genetic algorithm (GA) in coding theory, in particular, in the decoding linear block codes case, which has heavily contributed to reducing the bit error rate (BER). In this paper, an efficient method based on the GA is proposed and it is used to improve the power of correction in terms of BER and the frame error rate (FER) of LDPC codes. Subsequently, the proposed algorithm can independently decide the most suitable moment to stop the decoding process, moreover, it does not require channel information (CSI) making it adaptable for all types of channels with different noise or intensity. The simulations show that the proposed algorithm is more efficient in terms of BER compared to other LDPC code decoders.

International Journal of Power Electronics and Drive Systems/International Journal of Electrical and Computer Engineering•Apr 4, 2024•0 citations

Correcting capabilities of binary irregular LDPC code under low-complexity iterative decoding algorithm

Pavel S. Rybin

This paper deals with the irregular binary low-density parity-check (LDPC) codes and two iterative low-complexity decoding algorithms. The first one is the majority error-correcting decoding algorithm, and the second one is iterative erasure-correcting decoding algorithm. The lower bounds on correcting capabilities (the guaranteed corrected error and erasure fraction respectively) of irregular LDPC code under decoding (error and erasure correcting respectively) algorithms with low-complexity were represented. These lower bounds were obtained as a result of analysis of Tanner graph representation of irregular LDPC code. The numerical results, obtained at the end of the paper for proposed lower-bounds achieved similar results for the previously known best lower-bounds for regular LDPC codes and were represented for the first time for the irregular LDPC codes.

Journal of Communications Technology and Electronics•Dec 1, 2016•2 citations

Improved Constructions of Low-Density Parity-Check Codes

Aiden Price

There is an ongoing need to improve the efficiency and error-correcting performance of error correcting codes, which are widely used to enhance accuracy when retrieving or communicating information. This research investigates several potential improvements to a high-performing class of error correcting codes known as low-density parity-check (LDPC) codes. The results presented here further the known literature surrounding a specific class of functions (Alltop functions). Additionally, this work demonstrates ways of manipulating existing LDPC code constructions using relaxed difference sets to provide constructions with far more flexible code parameters. These constructions have competitive performance when compared to relevant modern codes.

•Jan 1, 2019•0 citations
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.
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.
Low Density Parity Check (LDPC) codes are considered to be one of the best classes of error-correcting codes. This thesis deals with two major issues in LDPC codes: decoder design to enhance error correction performance and efficient decoder implementation. Five techniques have been introduced in this thesis. First, an efficient platform for LDPC code design and performance evaluation is developed. This platform implements parallel simulation algorithms to efficiently evaluate the performance of the proposed algorithms for LDPC decoders and code design. Second, an innovative technique is introduced to improve the performance of LDPC decoding in the error-floor region. Special structures in the code graph, called trapping sets, are considered to be the major source of decoding errors in the error-floor region. The proposed technique is based on eliminating the negative effect of trapping sets during LDPC decoding. As a third contribution, a novel approach to improve the decoder performance and/or throughput is introduced. This approach is based on utilizing LDPC decoder idle times by introducing two queues: one at the decoder input and the other at the decoder output. This architecture enables the decoder to run extra iterations beyond the conventional maximum allowable iterations. The fourth proposed technique reduces the bit error rate of LDPC decoders. This technique is based on tracking the number of failed parity check equations in the intermediate decoding iterations, rather than only relying on the final decoder output (after reaching the maximum number of iterations). The last proposed technique deals with the construction of interconnect efficient fully-parallel LDPC codes with high error correction performance. Fully-parallel implementation is very hard due to the complexity of processing elements interconnections. The proposed technique is based on constructing LDPC codes with less complex interconnections and with low impact on the error correction performance. This goal is achieved by putting a constraint on the maximum connection length between any two processing elements.
Introduction In this chapter we introduce low-density parity-check (LDPC) codes, a class of error correction codes proposed by Gallager in his 1962 PhD thesis 12 years after error correction codes were first introduced by Hamming (published in 1950). Both Hamming codes and LDPC codes are block codes: the messages are broken up into blocks to be encoded at the transmitter and similarly decoded as separate blocks at the receiver. While Hamming codes are short and very structured with a known, fixed, error correction ability, LDPC codes are the opposite, usually long and often constructed pseudo-randomly with only a probabilistic notion of their expected error correction performance. The chapter begins by presenting parity bits as a means to detect and, when more than one is employed, to correct errors in digital data. Block error correction codes are described as a linear combination of parity-check equations and thus defined by their parity-check matrix representation. The graphical representation of codes by Tanner graphs is presented and the necessary graph theoretic concepts introduced. In Section 2.4 iterative decoding algorithms are introduced using a hard decision algorithm (bit flipping), so that the topic is developed first without reference to probability theory. Subsequently the sum–product decoding algorithm is presented. This chapter serves as a self-contained introduction to LDPC codes and their decoding. It is intended that the material presented here will enable the reader to implement LDPC encoders and iterative decoders.
Low-density parity check (LDPC) codes, are a family of error-correcting codes, their performances close to the Shannon limit make them very attractive solutions for digital communication systems. There are several algorithms for decoding LDPC codes that show great diversity in terms of performance related to error correction. Also, very recently, many research papers involved the genetic algorithm (GA) in coding theory, in particular, in the decoding linear block codes case, which has heavily contributed to reducing the bit error rate (BER). In this paper, an efficient method based on the GA is proposed and it is used to improve the power of correction in terms of BER and the frame error rate (FER) of LDPC codes. Subsequently, the proposed algorithm can independently decide the most suitable moment to stop the decoding process, moreover, it does not require channel information (CSI) making it adaptable for all types of channels with different noise or intensity. The simulations show that the proposed algorithm is more efficient in terms of BER compared to other LDPC code decoders.
This paper deals with the irregular binary low-density parity-check (LDPC) codes and two iterative low-complexity decoding algorithms. The first one is the majority error-correcting decoding algorithm, and the second one is iterative erasure-correcting decoding algorithm. The lower bounds on correcting capabilities (the guaranteed corrected error and erasure fraction respectively) of irregular LDPC code under decoding (error and erasure correcting respectively) algorithms with low-complexity were represented. These lower bounds were obtained as a result of analysis of Tanner graph representation of irregular LDPC code. The numerical results, obtained at the end of the paper for proposed lower-bounds achieved similar results for the previously known best lower-bounds for regular LDPC codes and were represented for the first time for the irregular LDPC codes.
There is an ongoing need to improve the efficiency and error-correcting performance of error correcting codes, which are widely used to enhance accuracy when retrieving or communicating information. This research investigates several potential improvements to a high-performing class of error correcting codes known as low-density parity-check (LDPC) codes. The results presented here further the known literature surrounding a specific class of functions (Alltop functions). Additionally, this work demonstrates ways of manipulating existing LDPC code constructions using relaxed difference sets to provide constructions with far more flexible code parameters. These constructions have competitive performance when compared to relevant modern codes.