Adaptive Multiset Stochastic Decoding of Non-Binary LDPC Codes

We propose a non-binary stochastic decoding algorithm for low-density parity-check (LDPC) codes over ${\rm GF}(q)$ with degree two variable nodes, called Adaptive Multiset Stochastic Algorithm (AMSA). The algorithm uses multisets, an extension of sets that allows multiple occurrences of an element, to represent probability mass functions that simplifies the structure of the variable nodes. The run-time complexity of one decoding cycle using AMSA is $O(q)$ for conventional memory architectures, and $O(1)$ if a custom memory architecture is used. Two fully-parallel AMSA decoders are implemented on FPGA for two (192,96) (2,4)-regular codes over GF(64) and GF(256), both achieving a maximum clock frequency of 108 MHz. The GF(64) decoder has a coded throughput of 65 Mb/s at $E_{b}/N_{0}={\hbox{2.4 dB}}$ when using conventional memory, while a decoder using the custom memory version can achieve 698 Mb/s at the same $E_{b}/N_{0}$ . At a frame error rate (FER) of $2\times 10^{-6}$ the GF(64) version of the algorithm is only 0.04 dB away from the floating-point SPA performance, and for the GF(256) code the difference is 0.2 dB. To the best of our knowledge, this is the first fully parallel non-binary LDPC decoder over GF(256) reported in the literature.