In this paper, we propose a type of
GN-coset codes for a highly parallel stage-permuted turbo-like decoder. The decoder exploits the equivalence between two stage-permuted factor graphs of
GN-coset codes. Specifically, the inner codes of a
GN-coset code consist of independent component codes, thus are decoded in parallel. The extrinsic information of the code bits is obtained and iteratively exchanged between the two graphs until convergence. Accordingly, we explore a heuristic and flexible code construction method (information set selection) for various information lengths and coding rates. Simulations show that the proposed
GN-coset codes could achieve a coding performance comparable with polar codes but enjoy higher decoding parallelism.
Soft-decision decoding of a linear block code using the most reliable basis corresponding to each received word is investigated. Based either on probabilistic properties or on the structure of the code considered, three improvements to the algorithm devised by Fossorier and Lin (see ibid., vol.41, no.9, p.1379-1396, 1995) are presented. These modifications allow large computation savings or significant decoding speedup with little error performance degradation. First, a reduced probabilistic list of codeword candidates is associated with order-i reprocessing of a given code. It results in a large reduction of the maximum number of computations with a very small degradation in performance. Then, a probabilistic stopping criterion is introduced for order-0 reprocessing. This new test significantly decreases the average number of computations when appropriately implemented. Finally, the application of the algorithm to coset decoding is considered for |u|u+v| constructed codes. In addition to the conventional coset decoding, a new adaptive practically optimum coset decoding method is presented where at each reprocessing stage, the number of surviving cosets decreases. Suboptimum closest coset decoding is also investigated. It is shown that two-stage decoding with the algorithm of Fossorier and Lin offers a large variety of choices, since the reprocessing order of each stage can be determined independently.
We study exact decoding for the toric code and for planar and rotated surface codes under the standard independent
X/Z noise model, focusing on Separate Minimum Weight (SMW) decoding and Separate Most Likely Coset (SMLC) decoding. For the SMW decoding problem, we show that an
O(n3/2logn)-time decoder is achievable for surface and toric codes, improving over the
O(n3logn) worst-case time of the standard approach based on complete decoding graphs. Our approach is based on a local reduction of SMW decoding to the minimum weight perfect matching problem using Fisher gadgets, which preserves planarity for planar and rotated surface codes and genus~
1 for the toric code. This reduction enables the use of Lipton--Tarjan planar separator methods and implies that SMW decoding lies in
NC. For SMLC decoding, we show that the planar surface code admits an exact decoder with
O(n3/2) algebraic complexity and that the problem lies in
NC, improving over the
O(n2) algebraic complexity of Bravyi \emph{et al.} Our approach proceeds via a dual-cycle formulation of coset probabilities and an explicit reduction to planar Pfaffian evaluation using Fisher--Kasteleyn--Temperley constructions. The same complexity measures apply to SMLC decoding of the rotated surface code. For the toric code, we obtain an exact polynomial-time SMLC decoder with
O(n3) algebraic complexity. In addition, while the SMLC formulation is motivated by connections to statistical mechanics, we provide a purely algebraic derivation of the underlying duality based on MacWilliams duality and Fourier analysis. Finally, we discuss extensions of the framework to the depolarizing noise model and identify resulting open problems.