It has been shown that graph-cover pseudocodewords can be used to characterize the behavior of sum-product algorithm (SPA) decoding of classical codes. In this paper, we leverage and adapt these results to analyze SPA decoding of quantum stabilizer codes. We use the obtained insights to formulate modifications to the SPA that overcome some of its weaknesses.
It has been shown that graph-cover pseudocodewords can be used to characterize the behavior of sum-product algorithm (SPA) decoding of classical codes. In this paper, we leverage and adapt these results to analyze SPA decoding of quantum stabilizer codes. We use the obtained insights to formulate modifications to the SPA that overcome some of its weaknesses.
In previous work, we have shown that pseudocodewords can be used to characterize the behavior of decoders not only for classical codes but also for quantum stabilizer codes. With the insights obtained from this pseudocodewords-based analysis, we have also introduced a two-stage decoder based on pseudocodewords for quantum cycle codes that leads to improved decoding performance. In this paper, we consider quantum (stabilizer) color codes and propose a two-stage decoder that is a generalization of the pseudocodeword-based decoder for quantum cycle codes. Our decoder has local operations w.r.t. the underlying graphs, syndrome-weight-dependent computational complexity, and better decoding performance compared with previous approaches for quantum color codes.
While low-density parity-check (LDPC) codes are near capacity-achieving when paired with iterative decoders, these decoders may not output a codeword due to the existence of pseudocodewords. Thus, pseudocodewords have been studied to give insight into the performance of modern decoders including iterative and linear programming decoders. These pseudocodewords are found to be dependent on the parity-check matrix of the code and the particular decoding algorithm used. In this paper, we consider LP decoding, which has been linked to graph cover decoding, providing functions which capture these pseudocodewords. In particular, we analyze the underlying structure of pseudocodewords from quantum stabilizer codes that arise from LP decoding, quasi-cyclic LDPC codes, and spatially-coupled LDPC codes.
Decoding sparse quantum codes can be accomplished by syndrome-based decoding through using the sum-product algorithm (SPA). We significantly improve this decoding scheme by developing a new feedback adjustment strategy for the standard SPA. In our feedback strategy, we exploit not only the syndrome but also the values of the frustrated checks on individual qubits of the code and the channel model. Consequently, our decoding algorithm, on the one hand, can break the symmetric degeneracy, and on the other hand, can feed back more useful information to the SPA decoder to help the decoder determine a valid output, thereby significantly improving the decoding ability of the decoder. Moreover, our algorithm does not increase the measurement complexity compared with the previous method, but takes full advantage of the measured information.
In this paper, a feedback sum-product decoding algorithm of sparse quantum codes for X-Z Pauli channels is developed. Compared with the previous decoding algorithm, our feedback strategy exploits not just the syndrome but also the values of the frustrated checks on individual qubits of the code and the character of the channel model with the portion of each error to adjust the probability distribution of information nodes. Due to the smart adjustment, our decoding algorithm, on one hand, can break the symmetric degeneracy, and on the other hand, can feed back more useful information to the SPA decoder to help the decoder determine a valid output, thereby significantly improving the decoding ability of the decoder. Moreover, our algorithm, which is based on GF(4), overcomes the limitation caused by decoding in GF(2). Finally, we want to point out that, our method does not increase the measurement overhead in comparison wioth the previous methods, as the extra information comes for free from the requisite stabilizer measurement.
The best-known algorithm for the decoding of low-density parity-check (LDPC) codes is the sum-product algorithm (SPA). The SPA is a message-passing algorithm on a graphical model called a factor graph (FG). The performance of the SPA depends on a structure of loops in a FG. Pearl showed that loops in a graphical model could be erased by the clustering method. This method clusters plural nodes into a single node. In this paper, we show several examples about a decoding on a FG to which the clustering method is applied. And we propose an efficient decoding algorithm for it. For a binary erasure channel (BEC), the performance with this method goes up clearly.
In the last six years, we have witnessed an explosion of interest in the coding theory community, in iterative decoding and graphical models, due primarily to the invention of turbo codes. While the structural properties of turbo codes and low density parity check codes have now been put on a firm theoretical footing, what is still lacking is a satisfactory theoretical explanation as to why iterative decoding algorithms perform as well as they do. In this thesis we make a first step by discussing the behavior of various iterative decoders for the graphs of tail-biting codes and cycle codes. By increasing our understanding of the behavior of the iterative min-sum (MSA) and sum-product (SPA) algorithms on graphs with cycles, we can design codes which achieve better performance.
Much of this thesis is devoted to the analysis of the performance of the MSA and SPA on the graphs for tail-biting codes and cycle codes. We give sufficient conditions for the MSA to converge to the maximum likelihood codeword after a finite number of iterations. We also use the familiar union bound argument to characterize the performance of the MSA after many iterations. For a cycle code, we show that the performance of the MSA decoder is asymptotically as good as maximum likelihood. For tail-biting codes this will depend on our choice of trellis.