International Conference on Information and Communication Technology Convergence (ICTC)

Quantum-Assisted Decoding for Non-Binary Low-Density Parity-Check Codes

Hyun-Woo Jung, Jeonghwan Kang, Jeongseok Ha

Published Oct 20, 2021• 1 citation

Abstract

It is generally known that the log sum-product-algorithm (log-SPA) for non-binary low-density parity-check (NB-LDPC) codes requires a high decoding complexity. The complexity grows exponentially fast and becomes prohibitive as the check node degree and/or the field size increase. In this work, we propose a quantum-assisted decoding (QD) for NB-LDPC codes to resolve the complexity issue associated with the log-SPA. We utilize the quantum amplitude estimation algorithm (QAEA) to calculate the check node messages in the form of log-likelihood ratio vector (LLRV). This work realizes the QAEA with the following two blocks, 1) state preparation and 2) amplitude estimation (AE). In particular, the state preparation provides the AE with the input state. It will be shown that the proposed QD achieves a significant complexity reduction, which becomes more distinctive as the check node degree and/or the field size grows.

DOI: 10.1109/ictc52510.2021.9621026

Related papers

A decoding algorithm with reduced complexity for non-binary LDPC codes over large fields

Jun Ting Lin, Zhiyuan Yan

Non-binary low-density parity-check (NB-LDPC) codes outperform their binary counterparts in some cases, but their high decoding complexity is a significant hurdle to their applications. In this paper, we propose a decoding algorithm with reduced computational complexities and smaller memory requirements for NB-LDPC codes over large fields. First, a simplified algorithm is proposed to reduce the computational complexity of variable node processing. To reduce memory requirements, existing NB-LDPC decoders often truncate the message vectors to a limited number nmof values. However, the memory requirements of these decoders remain high when the field size is large, since nmneeds to be large enough to alleviate error performance degradation. In this paper, an improved trellised based check node processing algorithm is proposed to significantly reduce the memory requirement. The number of elements in a variable-to-check message is reduced to nv(nvm). The sorted log likelihood ratio (LLR) vector of a check-to-variable message is approximated using a piece-wise linear function. Thus, only few LLRs are stored and other LLRs are computed on-the-fly when needed. For each a priori message, most LLRs are approximated with a linear function. Our numerical results demonstrate that the proposed decoding algorithm outperforms existing algorithms. Two LLR generation units (LGUs) are proposed to compute LLR vectors for check-to-variable messages, and the two LGUs require only a fraction of the area needed to store nmLLRs.

IEEE International Symposium on Circuits and Systems proceedingsMay 1, 20132 citations

Efficient Difference-based Decoding Implementations of LDPC Codes

Zhanji Wu, Peng Mugen, Wang Wenbo +1 more

Efficient implementations of the sum-product algorithm (SPA) for decoding low-density parity-check (LDPC) codes using difference-based messages between bit nodes and check nodes are presented. As for the updates of check nodes, reduced- complexity derivatives are also put forward. As compared with the traditional Log-Likelihood-Ratio(LLR)-based decoding implementations, the proposed method has much lower complexity and latency, while it has no obvious loss of the error performance.

IEEE Communications LettersMay 1, 20083 citations

A subp-optimal log-domain decoding algorithm for non-binary LDPC codes

Chirag Dadlani, Ranjan Bose

Low-Density Parity-Check (LDPC) codes have gained significant popularity recently and have been recommended for various wireless standards of the future. Non-binary LDPC codes provide all the well-known advantages of binary LDPC codes but allow for much shorter block lengths. The sum-product decoding algorithm for non-binary LDPC codes is too complex for efficient implementation. Hence, we have represented the sum-product algorithm in a novel log-domain form in terms of operators defined earlier in literature. This form greatly simplifies the key step in the check-node processing and allows us to replace a max* operation in the decoder by a max operation. This leads to a sub-optimal decoding algorithm which we propose in this paper.

Mar 23, 20101 citation

Non-uniform quantization scheme for the decoding of low-density parity-check codes with the sum-product algorithm

Xinru Qu, Liuguo Yin

In this paper, a non-uniform quantization scheme is proposed for the decoding of Low-Density Parity-Check (LDPC) codes with the Sum-Product Algorithm (SPA). With the proposed scheme, the quantization-range and quantization-interval for the soft Log-Likelihood-Ratio (LLR) values of the decoder input, the variable nodes, and the check nodes are set separately, and are also adjusted according to the evolution of the probability density distribution of the LLR values in the iterative decoding procedure to minimize the difference between the decoding values before quantization and that after quantization. Simulation results show that decoding with 3-bit non-uniform quantization of the proposed scheme may obtain a BER performance slightly better than that of decoding with 6-bits quantization of the traditional uniform quantization method.

IEEE International Conference on Electronics Information and Emergency CommunicationJun 1, 20165 citations

Log-Domain Decoding of Quantum LDPC Codes Over Binary Finite Fields

Ching–Yi Lai, Kao-Yueh Kuo

A quantum stabilizer code over$\GF(q)$corresponds to a classical additive code over$\GF(q^2)$that is self-orthogonal with respect to a symplectic inner product. We study the decoding of quantum low-density parity-check (LDPC) codes over binary finite fields$\GF(q=2^l)$by the sum-product algorithm, also known as belief propagation (BP). Conventionally, a message in a nonbinary BP for quantum codes over$\GF(2^l)$represents a probability vector over$\GF(2^{2l})$, inducing high decoding complexity. In this paper, we explore the property of the symplectic inner product and show that scalar messages suffice for BP decoding of nonbinary quantum codes, rather than vector messages necessary for the conventional BP. Consequently, we propose a BP decoding algorithm for quantum codes over${\GF(2^l)}$by passing scalar messages so that it has low computation complexity. The algorithm is specified in log domain by using log-likelihood ratios (LLRs) of the channel statistics to have a low implementation cost. Moreover, techniques such as message normalization or offset can be naturally applied in this algorithm to mitigate the effects of short cycles to improve BP performance. This is important for nonbinary quantum codes since they may have more short cycles compared to binary quantum codes. Several computer simulations are provided to demonstrate these advantages. The scalar-based strategy can also be used to improve the BP decoding of classical linear codes over$\GF(2^l)$with many short cycles.

arXiv:2104.00304IEEE Transactions on Quantum EngineeringJan 1, 202122 citations

Reduced-Complexity Belief Propagation Decoding for LDPC Codes

Heping Wan, Joonyoung Cho, Min Jang +1 more

Two methods are proposed to reduce the complexity of the belief propagation (BP) decoding for low-density parity-check (LDPC) codes, with the focus on the layered decoding for quasi-cyclic LDPC (QC-LDPC) codes. The two methods can be separately incorporated into the layered decoding procedures and combined seamlessly to provide the two-fold complexity reduction. In the first method, the message updates regarding a subset of variable nodes are omitted. To construct the subset, the most reliable bit-level channels, derived fromM-ary input channels, are identified. Then, we select the variable nodes with initial log-likelihood ratios (LLRs) exceeding a threshold among the ones assigned to the most reliable bit-level channels to form the subset. The threshold is designed and adjusted based on characteristics of the most reliable bit-level channels. Our numerical results demonstrate that the first method significantly reduces the complexity with negligibly impacting the error-correcting performance. In the second method, each layer of base graphs of QC-LDPC codes uses either sum-product algorithm (SPA) or min-sum algorithm (MSA) to update LLRs. A degree-based algorithm is presented to determine the layers employing either SPA or MSA. We compare with two intuitive methods: 1) applying SPA to randomly selected layers and MSA to the remaining layers, and 2) applying SPA to the core layers of 5G NR LDPC codes and MSA to the remaining layers. According to the numerical results, the degree-based algorithm maximally reduces the complexity while maintaining the same performance. To evaluate the joint method, the first method is applied on top of the second method. Further complexity reduction is achieved without degrading the performance of the second method.

IEEE AccessJan 1, 20260 citations