Suspicion Distillation Gradient Descent Bit-Flipping Algorithm
We propose a novel variant of the gradient descent bit-flipping (GDBF) algorithm for decoding low-density parity-check (LDPC) codes over the binary symmetric channel. The new bit-flipping rule is based on the reliability information passed from neighboring nodes in the corresponding Tanner graph. Th...
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2022-04-01
|
| Series: | Entropy |
| Subjects: | |
| Online Access: | https://www.mdpi.com/1099-4300/24/4/558 |
| _version_ | 1797434777041633280 |
|---|---|
| author | Predrag Ivaniš Srdjan Brkić Bane Vasić |
| author_facet | Predrag Ivaniš Srdjan Brkić Bane Vasić |
| author_sort | Predrag Ivaniš |
| collection | DOAJ |
| description | We propose a novel variant of the gradient descent bit-flipping (GDBF) algorithm for decoding low-density parity-check (LDPC) codes over the binary symmetric channel. The new bit-flipping rule is based on the reliability information passed from neighboring nodes in the corresponding Tanner graph. The name <i>SuspicionDistillation</i> reflects the main feature of the algorithm—that in every iteration, we assign a level of suspicion to each variable node about its current bit value. The level of suspicion of a variable node is used to decide whether the corresponding bit will be flipped. In addition, in each iteration, we determine the number of satisfied and unsatisfied checks that connect a suspicious node with other suspicious variable nodes. In this way, in the course of iteration, we “distill” such suspicious bits and flip them. The deterministic nature of the proposed algorithm results in a low-complexity implementation, as the bit-flipping rule can be obtained by modifying the original GDBF rule by using basic logic gates, and the modification is not applied in all decoding iterations. Furthermore, we present a more general framework based on deterministic re-initialization of the decoder input. The performance of the resulting algorithm is analyzed for the codes with various code lengths, and significant performance improvements are observed compared to the state-of-the-art hard-decision-decoding algorithms. |
| first_indexed | 2024-03-09T10:38:16Z |
| format | Article |
| id | doaj.art-ff487a7b30494d069ccf979e7c39af50 |
| institution | Directory Open Access Journal |
| issn | 1099-4300 |
| language | English |
| last_indexed | 2024-03-09T10:38:16Z |
| publishDate | 2022-04-01 |
| publisher | MDPI AG |
| record_format | Article |
| series | Entropy |
| spelling | doaj.art-ff487a7b30494d069ccf979e7c39af502023-12-01T20:51:27ZengMDPI AGEntropy1099-43002022-04-0124455810.3390/e24040558Suspicion Distillation Gradient Descent Bit-Flipping AlgorithmPredrag Ivaniš0Srdjan Brkić1Bane Vasić2School of Electrical Engineering, University of Belgrade, 11000 Belgrade, SerbiaSchool of Electrical Engineering, University of Belgrade, 11000 Belgrade, SerbiaDepartment of ECE, University of Arizona, Tucson, AZ 85721, USAWe propose a novel variant of the gradient descent bit-flipping (GDBF) algorithm for decoding low-density parity-check (LDPC) codes over the binary symmetric channel. The new bit-flipping rule is based on the reliability information passed from neighboring nodes in the corresponding Tanner graph. The name <i>SuspicionDistillation</i> reflects the main feature of the algorithm—that in every iteration, we assign a level of suspicion to each variable node about its current bit value. The level of suspicion of a variable node is used to decide whether the corresponding bit will be flipped. In addition, in each iteration, we determine the number of satisfied and unsatisfied checks that connect a suspicious node with other suspicious variable nodes. In this way, in the course of iteration, we “distill” such suspicious bits and flip them. The deterministic nature of the proposed algorithm results in a low-complexity implementation, as the bit-flipping rule can be obtained by modifying the original GDBF rule by using basic logic gates, and the modification is not applied in all decoding iterations. Furthermore, we present a more general framework based on deterministic re-initialization of the decoder input. The performance of the resulting algorithm is analyzed for the codes with various code lengths, and significant performance improvements are observed compared to the state-of-the-art hard-decision-decoding algorithms.https://www.mdpi.com/1099-4300/24/4/558bit-flipping algorithmdecoder re-initializationsgradient descentiterative decodinglow-density parity-check codes |
| spellingShingle | Predrag Ivaniš Srdjan Brkić Bane Vasić Suspicion Distillation Gradient Descent Bit-Flipping Algorithm Entropy bit-flipping algorithm decoder re-initializations gradient descent iterative decoding low-density parity-check codes |
| title | Suspicion Distillation Gradient Descent Bit-Flipping Algorithm |
| title_full | Suspicion Distillation Gradient Descent Bit-Flipping Algorithm |
| title_fullStr | Suspicion Distillation Gradient Descent Bit-Flipping Algorithm |
| title_full_unstemmed | Suspicion Distillation Gradient Descent Bit-Flipping Algorithm |
| title_short | Suspicion Distillation Gradient Descent Bit-Flipping Algorithm |
| title_sort | suspicion distillation gradient descent bit flipping algorithm |
| topic | bit-flipping algorithm decoder re-initializations gradient descent iterative decoding low-density parity-check codes |
| url | https://www.mdpi.com/1099-4300/24/4/558 |
| work_keys_str_mv | AT predragivanis suspiciondistillationgradientdescentbitflippingalgorithm AT srdjanbrkic suspiciondistillationgradientdescentbitflippingalgorithm AT banevasic suspiciondistillationgradientdescentbitflippingalgorithm |