International Conference on Electrical Engineering and Photonics (EExPolytech)

Detecting Minimum Distance of LDPC Codes with Improved Approximately Nearest Codeword Method

Zhewei Tong, Kewu Peng, Zhitong He

Published Oct 20, 2022• 1 citation

Abstract

Approximately nearest codeword (ANC) is a classic approach for detecting minimum distance of low-density parity-check (LDPC) codes. With the principle of local search, ANC method is capable of detecting minimum distance of LDPC codes within acceptable time. However, the message passing (MP) decoding algorithm and scheduling scheme, as well as the local search strategy, still have much space to improve. To fill the gap, this paper proposes an improved-ANC method which employs novel noise introduction method, decoding algorithm, scheduling scheme and searching strategy, to accelerate the computation of the minimum distance of LDPC codes significantly. Finally, we run simulations on LDPC codes in Wi-Fi5 and 5G-NR standards. The simulation results are presented and demonstrate the effectiveness of our proposal.

DOI: 10.1109/eexpolytech56308.2022.9950957

Related papers

On the computation of the minimum distance of low-density parity-check codes

Xiao-Yu Hu, M.P.C. Fossorier, Evangelos S. Eleftheriou

Low-density parity-check (LDPC) codes in their broader-sense definition are linear codes whose parity-check matrices have fewer 1s than 0s. Finding their minimum distance is therefore in general an NP-hard problem. We propose a randomized algorithm called nearest nonzero codeword search (NNCS) approach to tackle this problem for iteratively decodable LDPC codes. The principle of the NNCS approach is to search codewords locally around the all-zero codeword perturbed by minimal noise, anticipating that the resultant nearest nonzero codewords will most likely contain the minimum-Hamming- weight codeword whose Hamming weight is equal to the minimum distance of the linear code. This approach has its roots in Berrou et al.'s error-impulse method and a form of Fossorier's list decoding for LDPC codes.

International Conference on CommunicationsJan 1, 2004156 citations

Computation of the minimum distance of low-density parity-check codes

Min Xiao

Low-density parity-check (LDPC) codes are a good liner block parity codes. In this paper, the fundamental of LDPC codes are introduced briefly first. Then an algorithm called the minimum-weight codeword searching is discussed, which can be used to compute the minimum distance of LDPC codes. The effectiveness and the practicability of the algorithm are demonstrated by some examples. It is significant for us to analyze and optimize the design of LDPC codes.

Information technology newsletterJan 1, 20050 citations

Computing the Minimum Distance of Nonbinary LDPC Codes

Lei Liu, Jie Huang, Wuyang Zhou +1 more

Finding the minimum distance of low-density-parity-check (LDPC) codes is an NP-hard problem. Different from all existing works that focus on binary LDPC codes, we in this paper aim to compute the minimum distance of nonbinary LDPC codes, motivated by the fact that operating in a large Galois field provides one important degree of freedom to achieve both good waterfall and error-floor performance. Our method is based on the existing nearest nonzero codeword search (NNCS) method, but several modifications are incorporated for nonbinary LDPC codes, including the modified error impulse pattern, the dithering method, and the nonbinary decoder. Numerical results on the estimated minimum distances show that a code's minimum distance can be increased by careful selection of nonzero elements of the parity check matrix, or by increasing the mean column weight, or by increasing the size of the Galois field. These results support observations that have been made based on simulated performance in the literature. Finally, we provide an upper bound on the minimum distance for nonbinary quasi-cyclic LDPC codes.

IEEE Transactions on CommunicationsJul 1, 20128 citations

Approximate algorithms for computing the minimum distance of low-density parity-check codes

Xiao-Yu Hu, M.P.C. Fossorier, Evangelos S. Eleftheriou

We propose a family of randomized approximate algorithms, called nearest nonzero codewords search (NNCS), for computing the minimum distance of low-density parity-check (LDPC) codes, including Gallager-type and finite-geometry-type codes.

IEEE International Symposium on Information Theory (ISIT)Dec 23, 20047 citations

Improving the Performance of Layered Iterative minsum Approximation Message Passing Decoding Algorithm for 5G NR LDPC Codes

P. Vigneswari, S. Sivakumari

Abstract In order to cater to the needs of the 5G standard, one of the prominent solutions in terms of high coding gain, high throughput and low power dissipation is the 5G NR LDPC (New Radio Low Density Parity Check) codes which have been adopted by 5G Standard. LDPC codes are the successful Third Generation Forward Error Correcting codes. An Efficient decoder is the key to the success of any Error Correcting Code. LDPC codes are one whose parity check matrix have a very few non zero entries. 5G NR LDPC codes are constructed by Protographs or base graphs and are block structured. This paper improves the performance of Layered Iterative minsum Approximation Message Passing decoding Algorithm using Rate Matching, Fixed Point Quantization and Offset minsum techniques. Rate Matching is to maintain the exact number of encoded blocks with in the TTI. Simulation of this algorithm with BPSK encoding over AWGN channel shows that BER of 10-3 gives Eb/No of~2 dB for the block length of 105.

Journal of Physics Conference SeriesJun 1, 20210 citations

Decoder Improvements for Fast Decoding of Low-Density Parity-Check Codes

Janik Frenzel

In this work, iterative decoders for Low-Density Parity-Check (LDPC) codes are analyzed and optimized for low computational complexity. LDPC block codes are now widely used in industry standards such as Wi-Fi or 5G New Radio (NR). Hence, there is a strong need for decoder concepts suitable for hardware designs. In addition, terminated LDPC convolutional codes are promising candidates for next-generation communication systems. The main theme of this work is to investigate low-overhead strategies for reducing the computational complexity of iterative decoders. Two aspects are considered for fast decoding of the LDPC block codes in 5G NR. Firstly, an efficient but simple-to determine update schedule for the iterative decoding process, i.e., the sequence of updates on different parts of a codeword, is proposed. Secondly, Early Termination (ET), i.e., an option to stop decoding before a maximal number of iterations is exhausted, is improved in two ways: On the one hand, a partial evaluation of the code’s Parity-Check (PC) equations speeds up the detection of valid codewords. On the other hand, a novel criterion detects when the decoding process is unlikely to converge and stops the decoding before a lot of resources are wasted on futile iterations. The combination of all techniques results in a decoder with significant reduction of the computational complexity compared to a decoder without these methods. Still, only few additional residual decoding errors are produced. This work also contains an analysis of various aspects of a Windowed Decoder (WD), which is a specialized decoder design for LDPC convolutional codes. A WD can be configured in even more ways than a decoder for block codes. The analysis in this work assumes a normalization of the computational complexity to a certain maximal value. With this setup, it is shown that a larger size of the decoding window may be preferable over a smaller size to minimize the computational complexity. Furthermore, various window update strategies (determining in which way the code symbol reliabilities are updated in each window) and variations of ET are compared to identify a well-suited WD configuration. Lastly, strategies with Dynamic Scheduling (DS) are considered to further reduce the computational complexity. A novel fixed approach derived from several DS strategies performs well without actual dynamic knowledge of the decoder state. All in all, the optimized WD configuration halves the computational complexity of a block decoder while maintaining an acceptable loss in the decoding performance measured by the number of residual decoding errors. A comparison of systems with Hybrid Automatic Repeat reQuest (HARQ) expands the scope of this work into the domain of error control by retransmissions. The analyzed systems make use of the decoder output, e.g., the final code-symbol reliabilities, to assemble dynamic retransmissions that are as short as possible and contain specifically selected code symbols. These systems stand in contrast to contemporary implementations of HARQ that only use imprecise feedback messages. Still, some compatibility with existing systems is achieved by assuming a limited feedback channel, which requires clever compression of the feedback information. A novel HARQ system is proposed, which evaluates the code’s PC equations to avoid the computational overhead of soft-value processing. The throughput with the proposed system is found to be improved compared to a reference system that evaluates code-symbol reliabilities. Finally, approximations of the accurate message-update rules of the Sum–Product Algorithm (SPA) are analyzed. With fixed-point arithmetic, Look-Up Tables (LUTs) are a promising approach to approximate functions that are costly to compute. It is shown that an optimized LUT with just nine entries can be used in a fixed-point decoder such that the decoding performance is close to that of a floating-point decoder with accurate message updates.

Jan 1, 20200 citations