Source-linked AI summary
Min-Max decoding for non binary LDPC codes
Valentin Savin
TL;DR
Non-binary LDPC decoding faces a complexity trade-off between optimal Sum-Product decoding and simpler but sub-optimal Min-Sum decoding. The paper proposes quasi-optimal algorithms, including Min-Max, and develops standard and selective LLR-domain implementations. The selective implementation lowers per-iteration complexity without performance degradation, while Min-Max retains quasi-optimal performance.
Problem
Non-binary LDPC decoding is limited by the complexity of existing Sum-Product and Min-Sum approaches and their associated performance or stability trade-offs.
Method
The paper proposes low-complexity quasi-optimal iterative decoders, including Min-Max, with standard and selective implementations in the LLR domain.
Results
The selective Min-Max implementation reduces operations per decoding iteration without performance degradation and is four times less complex than the standard implementation over GF(16).
Takeaways & Limitations
Quasi-optimal performance together with low complexity makes Min-Max decoding attractive for practical non-binary LDPC decoding.
Abstract
from arXiv · showhide
Iterative decoding of non-binary LDPC codes is currently performed using either the Sum-Product or the Min-Sum algorithms or slightly different versions of them. In this paper, several low-complexity quasi-optimal iterative algorithms are proposed for decoding non-binary codes. The Min-Max algorithm is one of them and it has the benefit of two possible LLR domain implementations: a standard implementation, whose complexity scales as the square of the Galois field's cardinality and a reduced complexity implementation called selective implementation, which makes the Min-Max decoding very attractive for practical purposes.
I. INTRODUCTION
Non-binary LDPC decoding is limited by complexity: Sum-Product is optimal but costly and unstable, while Min-Sum is simpler but sub-optimal. The paper proposes quasi-optimal Min-Max decoding with stable LLR implementations, including a selective version for lower complexity.
- Non-binary LDPC codes remain limited mainly because their decoding complexity is high.
- Sum-Product provides optimal iterative decoding but has increased complexity, computational instability, and dependence on thermal-noise estimation errors.
- Min-Sum is less complex and independent of thermal-noise estimation errors, but its check-node messages are overestimated, causing sub-optimality.
- The paper proposes several low-complexity quasi-optimal algorithms for non-binary LDPC decoding, including the Min-Max algorithm.
- Min-Max has standard and selective LLR-domain implementations; the standard scales as the square of the Galois field cardinality, while the selective version reduces complexity.
B. Equivalent iterative decoders
The paper establishes equivalence among several Min-Sum variants by comparing their a posteriori symbol orders. This equivalence motivates metric-based decoding formulations while identifying Min-Sum⋆ as practically unnecessary.
- Two decoders are equivalent when they induce the same a posteriori symbol order at every variable node and iteration.
- Min-Sum0 uses log-likelihood ratios relative to a fixed symbol, while Min-Sum⋆ uses ratios relative to the currently most likely symbol.
- Min-Sum, Min-Sum0, and Min-Sum⋆ are equivalent and therefore output the same GF(q)-symbol sequence under hard decoding.
- Min-Sum⋆ has no practical interest because equivalent Min-Sum0 is computationally stable, less complex, and avoids minimum computation in variable-node processing.
- The equivalence analysis motivates viewing zero-valued most-likely-symbol messages and positive other messages as distance metrics from the most likely symbol.
III. MIN-NORM DECODING FOR NON BINARY LDPC
The Min-Max decoder interprets variable-node messages as symbol distances and uses the infinity norm to compute check-node messages. This preserves the shared decoding framework while reducing overestimation relative to Min-Sum⋆.
- Min-Max decoding: For each candidate symbol, check-node processing minimizes the distance from the most likely neighboring-symbol sequence to its constraint-compatible tuple set.The compatible tuples are collected in L_a(m), and the point-to-set distance is minimized.
- Min-Max decoding: Min-Max decoding uses the infinity norm to measure distance between symbol sequences during check-node processing.The distance minimizes the largest componentwise distance over tuples satisfying the check constraint.
- Min-norm decoding: p = 1 recovers Min-Sum⋆, while the infinity norm reduces overestimated check-node messages and is empirically more accurate than the 1-norm.The paper also states that the infinity norm’s distance from the 1-norm is less than twice its distance from the Euclidean norm.
- Min-norm decoding: The Min-Max and Euclidean decoders share initialization, variable-node processing, and a posteriori updates with Min-Sum⋆; only check-node processing differs.The paper derives the alternatives by changing the norm used in check-node message computation.
B. Min-Max decoding
The Min-Max decoder computes check-node messages with min-max operations and accelerates them by restricting attention to selected field symbols. The selective implementation preserves the relevant computation while reducing operations substantially.
- Standard implementation: The standard implementation computes check-node messages through forward-backward metrics over the Tanner-graph neighborhood.Forward and backward metrics are recursively defined and then combined to produce the messages.
- Selective implementation: The min-max computation requires O(q^2) comparisons, motivating a reduction in the number of symbols considered.The reduction begins from a proposition guaranteeing suitable subsets whose cardinalities sum to at least q + 1.
- Selective implementation: For GF(8), evaluating eight values uses 18 comparisons instead of 64 when the selected subsets contain six and three symbols.The nine selected values are the nine smallest among the sixteen candidate values.
- Selective implementation: The selected subsets reduce both the number of symbols and the number of maximum computations needed.A maximum is computed only for pairs from subsets with the same index; otherwise, the maximal-index subset determines it.
- Selective implementation: The selective procedure uses normalized a priori information and a cut-off threshold to exclude sufficiently large incoming messages.The subset ranks range from 0 to COT − 1, and the constants depend only on the Galois-field cardinality.
- Selective implementation: In later iterations, uncertainty often concerns fewer symbols, allowing the selective implementation to reduce min-max complexity further.The paper states that the selected subsets may together contain fewer than q + 1 symbols in this regime.
V. SIMULATION RESULTS
Simulations evaluate GF(16)-LDPC decoding at rate 1/2 over AWGN with 16-QAM. Min-Max performance closely matches the Euclidean decoder, while selective processing lowers complexity without changing performance.
- Performance: 0.2 dB is the gap between the Min-Max implementations and Sum-Product decoding in the reported GF(16) simulation.The Euclidean and both Min-Max implementations achieve nearly the same decoding performance.
- Complexity: A factor of 4 lower complexity distinguishes selective Min-Max from standard Min-Max over GF(16).Both Min-Max implementations have the same performance and number of decoding iterations; selective processing uses fewer operations per iteration.
VI. CONCLUSIONS
The paper interprets extrinsic Min-Sum messages as distances from the most likely symbol and derives low-complexity, quasi-optimal decoders, including Euclidean and Min-Max variants. A selective Min-Max implementation reduces per-iteration operations without performance degradation, while retaining quasi-optimal performance and practical attractiveness.
- Extrinsic messages in non-binary Min-Sum decoding can be interpreted as metrics measuring a symbol’s distance from the most likely symbol.
- The Euclidean and Min-Max algorithms are derived as low-complexity quasi-optimal iterative decoders for non-binary codes.
- The canonical selective Min-Max implementation reduces the number of operations per decoding iteration without performance degradation.
- Quasi-optimal performance combined with low complexity makes Min-Max decoding attractive for practical purposes.
APPENDIX I ALTERNATIVE REALIZATIONS OF THE MIN-SUM
The appendix introduces alternative Min-Sum realizations, proves their convergence and equivalence, and uses these relationships to motivate Min-Max decoding over non-binary fields.
- Alternative realizations: Min-Sum0 and Min-Sum⋆ are introduced as alternative realizations of Min-Sum, with equivalence to the MSA algorithm established under a cycle-free Tanner-graph assumption.The cycle-free assumption can be replaced by computation trees and pseudo-codewords.
- Min-Sum0 convergence: The Min-Sum0 decoder converges after finitely many iterations to the stated limiting a posteriori information.
- Min-Sum⋆ convergence: The Min-Sum⋆ decoder likewise converges after finitely many iterations to its stated limiting expression.
- Decoder equivalence: MSA, Min-Sum0, and Min-Sum⋆ are equivalent because they induce the same a posteriori order and therefore the same hard-decoded symbol sequence.
- Binary-field equivalence: Over GF(2), the MSA and MMA decoders are equivalent, with identical check-to-variable update messages.
APPENDIX II PROOF OF PROPOSITION 3
The proof uses injective mappings to show that transformed symbol sets intersect, yielding the existence of symbols satisfying the required relation.
- Because the mappings ϕ and ψ are injective, their images of the relevant sets intersect, so suitable symbols a′ and a′′ exist.