IEEE International Conference on Consumer Electronics-Asia (ICCE-Asia)

Sum-Product Decoding based Simple Hamming Code for Low Power Mobile Devices

Taiga Mano, Koki Yamashita, Tensho Nagasato, Chang-Jun Ahn

Published Oct 26, 2022• 1 citation

Abstract

Since IoT requires low power transmission and ultra-small devices, a strong error correction codes with simple encoders are needed. Hamming code is considered as an useful simple error correction code. Hamming code with hard decision has a low complexity scheme, but its error correction capability is degraded. Therefore, in this paper, we consider a low complexity decoding method to improve error correction property with applying Sum-product algorithm. Sum-product decoding is a kind of brief propagation (BP) decoding, and can efficiently determine the posterior probability. In addition, using messages in the LLR domain, decoding operation will be much easier. However, it is not an exact MAP decoding because the Tanner graph of the Hamming code has the loops of length 4, and its decoding performance is not predictable. Therefore, we verified the effectiveness of the proposed scheme by computer simulation.

DOI: 10.1109/icce-asia57006.2022.9954736

Related papers

Improved LDPC decoding algorithms based on min-sum algorithm

Y.V. A. C. Kumara, Chandika Bandara Wavegedara

Low-Density Parity check (LDPC) codes offer high-performance error correction near the Shannon limit which employs large code lengths and some iterations in the decoding process. The conventional decoding algorithm of LDPC is the Log Likelihood Ratio based Belief Propagation (LLR BP) which is also known as the `Sum-Product algorithm' which gives the best decoding performance and requires the most computational complexity and implementations with increased hardware complexity. Another simpler variant of this algorithm is used which is known as `min-sum algorithm' which reduces computational complexity as well as hardware complexity but with reduced accuracy. This paper analyzes the reason min-sum algorithm is more prone to errors when compared to the sum-product algorithm, and puts forward two improved algorithms which improve the performance of the min-sum algorithm with comparable algorithmic complexity.

Moratuwa Engineering Research Conference (MERCon)Apr 1, 20168 citations

Analysis of Hamming code's iterative decoding performance based on sum-product algorithm

Dan Wang, Lin Wang, Wei Qin-fang

Iterative decoding that is adopted by near capacity limit error-correcting codes,improves the correcting capability of coding system greatly.This paper presents the design of encoding and decoding system of hamming codes with iterative decoding,and the theoretical analysis of iterative decoding process of hamming codes using modern encoding and decoding theory such as factor graph and sum-product algorithm.Simulation results show that there is 3 db coding gain between iterative decoding and classical decoding in hamming codes when the BER(bit error rate) is 10~(-3) under some times of iterative decoding and AWGN channel.At the same time,the BER performances between iterative decoding and the best enumerate decoding are equal,but the complexity of iterative decoding descends evidently,which is of importantly actual value for the hamming codes to be used in practical systems.

Journal of Chongqing University of Posts and TelecommunicationsJan 1, 20050 citations

Sum of the Magnitude for Hard Decision Decoding Algorithm Based on Loop Update Detection

Jiahui Meng, Danfeng Zhao, Hai Tian +1 more

In order to improve the performance of non-binary low-density parity check codes (LDPC) hard decision decoding algorithm and to reduce the complexity of decoding, a sum of the magnitude for hard decision decoding algorithm based on loop update detection is proposed. This will also ensure the reliability, stability and high transmission rate of 5G mobile communication. The algorithm is based on the hard decision decoding algorithm (HDA) and uses the soft information from the channel to calculate the reliability, while the sum of the variable nodes’ (VN) magnitude is excluded for computing the reliability of the parity checks. At the same time, the reliability information of the variable node is considered and the loop update detection algorithm is introduced. The bit corresponding to the error code word is flipped multiple times, before this is searched in the order of most likely error probability to finally find the correct code word. Simulation results show that the performance of one of the improved schemes is better than the weighted symbol flipping (WSF) algorithm under different hexadecimal numbers by about 2.2 dB and 2.35 dB at the bit error rate (BER) of 10−5 over an additive white Gaussian noise (AWGN) channel, respectively. Furthermore, the average number of decoding iterations is significantly reduced.

SensorsJan 15, 20181 citation

Design and Implementation of Low Bit Error Rate of LDPC Decoder

Ashlesha P. Kshirsagar, Sandeep Kakde, Manish Devendra Chawhan +1 more

Many classes of high-performance Low-density parity check codes are based on parity check matrices composed of permutation sub matrices. The emulation-simulation framework further allows the algorithm and implementation to be iteratively redefined to improve the error floor performance of message passing decoder. Log-Like hood-Ratio (LLR) based Belief-Propagation (BP) algorithm is presented for Low Density Parity Check codes. Numerically accurate representation of check node update computation used in LLR-BP decoding is described. The implementation of Sum-Product algorithm (SPA) within Low Density Parity Check Code (LDPC) decoder is described in this paper and the correction term is used to improve the decoding performance of min-sum algorithm (MSA). Quantization and log-tanh function approximation in sum-product decoder strongly affect which absorbing set dominates in error floor region. For LDPC decoder, bit error rate (BER) decreases with increase in the signal to noise ratio.

International Conference on Communication Systems and Network TechnologiesApr 1, 20151 citation

An improved LDPC decoding algorithm based on min-sum algorithm

Yue Cao

Low density parity check code is a kind of high-performance linear block code. It has excellent performance which is near the Shannon limit. LDPC has low decoding complexity, free structure and receives extensive attention. The typical decoding algorithm of LDPC is LLR BP algorithm, which is also called “sum-product algorithm”. LLR BP algorithm is the best algorithm at present. But it needs complex computation, which causes great difficulty in its hardware design. To solve this problem, an algorithm that gets approximation of LLR BP algorithm is put forward, which is called min-sum algorithm. Min-sum algorithm greatly reduces the computation and makes the hardware design simpler, but its accuracy has a wide gap with BP algorithm. This article analyzes the reason why min-sum algorithm has errors, and puts forward an improved algorithm called min-sum linear approximation algorithm based on min-sum algorithm.

International Symposium on Communications and Information TechnologiesOct 1, 20119 citations

A Modified Sum-Product Algorithm over Graphs with Short Cycles

Nithin Raveendran

We investigate into the limitations of the sum-product algorithm for binary low density parity check (LDPC) codes having isolated short cycles. Independence assumption among messages passed, assumed reasonable in all configurations of graphs, fails the most in graphical structures with short cycles. This research work is a step forward towards understanding the effect of short cycles on error floors of the sum-product algorithm. We propose a modified sum-product algorithm by considering the statistical dependency of the messages passed in a cycle of length 4. We also formulate a modified algorithm in the log domain which eliminates the numerical instability and precision issues associated with the probability domain. Simulation results show a signal to noise ratio (SNR) improvement for the modified sum-product algorithm compared to the original algorithm. This suggests that dependency among messages improves the decisions and successfully mitigates the effects of length-4 cycles in the Tanner graph. The improvement is significant at high SNR region, suggesting a possible cause to the error floor effects on such graphs. Using density evolution techniques, we analysed the modified decoding algorithm. The threshold computed for the modified algorithm is higher than the threshold computed for the sum-product algorithm, validating the observed simulation results. We also prove that the conditional entropy of a codeword given the estimate obtained using the modified algorithm is lower compared to using the original sum-product algorithm.

Jan 1, 20180 citations