Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Telecommunications Forum (TELFOR)

Reduced-Complexity Successive Cancelation Decoding of $\mathbb{Z}_{4}$ Splitting Codes

Aleksandar Minja

Published Nov 25, 2025• 0 citations
Publisher

Abstract

In this paper, we present a novel suboptimal softinput decoding algorithm for linear codes over the ring$\mathbb{Z}_{4}$(the ring of integers modulo 4), based on the lifting decoder technique. The proposed method operates directly on the parity-check matrix, unlike our previous successive cancellation decoder (SCD), which relies on the generator matrix. This results in a reduced number of arithmetic operations and lower computational complexity. The algorithm is demonstrated for a range of Kerdock codes and compared with both the maximum a posteriori (MAP) decoder and the classical SCD. Simulation results show that the proposed decoder achieves comparable error-rate performance to the MAP and classical SCD algorithms, while maintaining the same asymptotic complexity of the classical SCD algorithm, which in the case of Kerdock codes is$O\left(N \log _{2} N\right)$.

DOI
10.1109/telfor67910.2025.11314347

Related papers

SISO Decoding of ℤ4 Linear Kerdock and Preparata Codes

Aleksandar Minja, V. Šenk

Some nonlinear codes, such as Kerdock and Preparata codes, can be represented as binary images under the Gray map of linear codes over rings. This paper introduces MAP decoding of Kerdock and Preparata codes by working with their quaternary representation (linear codes over$\mathbb {Z}_{4}$) with the complexity of$\mathcal {O}(N^{2}\log _{2} N)$, where N is the code length in$\mathbb {Z}_{4}$. A sub-optimal bitwise APP decoder with good error-correcting performance and complexity of$\mathcal {O}(N\log _{2} N)$that is constructed using the decoder lifting technique is also introduced. This APP decoder extends upon the original lifting decoder by working with likelihoods instead of hard decisions and is not limited to Kerdock and Preparata code families. Simulations show that our novel decoders significantly outperform several popular decoders in terms of error rate.

arXiv:2312.00193•IEEE Transactions on Communications•Jan 11, 2022•5 citations

Decoding of Z2S Linear Generalized Kerdock Codes

Aleksandar Minja, V. Šenk

Many families of binary nonlinear codes (e.g., Kerdock, Goethals, Delsarte–Goethals, Preparata) can be very simply constructed from linear codes over the Z4 ring (ring of integers modulo 4), by applying the Gray map to the quaternary symbols. Generalized Kerdock codes represent an extension of classical Kerdock codes to the Z2S ring. In this paper, we develop two novel soft-input decoders, designed to exploit the unique structure of these codes. We introduce a novel soft-input ML decoding algorithm and a soft-input soft-output MAP decoding algorithm of generalized Kerdock codes, with a complexity of O(NSlog2N), where N is the length of the Z2S code, that is, the number of Z2S symbols in a codeword. Simulations show that our novel decoders outperform the classical lifting decoder in terms of error rate by some 5 dB.

Mathematics•Jan 30, 2024•2 citations

Reduced Complexity Successive-Cancellation Decoding of Polar Codes Based on Linear Approximation

Yongli Yan, Xuanxuan Zhang, Bin Wu

In this letter, the principle of LLR-based successive-cancellation (SC) polar decoding algorithm is explored. In order to simplify the logarithm and exponential operations in the updating rules for polar codes, we further utilize a piece-wise linear algorithm to approximate the transcendental functions, where the piece-wise linear algorithm only consists of multiplication and addition operations. It is demonstrated that with one properly allowable maximum error δ chosen for success-failure algorithm, performances approach to that of the standard SC algorithm can be achieved. Besides, the complexity reduction is realized by calculating a linear function instead of nonlinear function. Simulation results show that our proposed piece-wise SC decoder greatly reduces the complexity of the SC-based decoders with no loss in error correcting performance.

IEICE Transactions on Fundamentals of Electronics Communications and Computer Sciences•Jul 31, 2020•1 citation

A Low Complexity Successive Cancellation List Decoding Algorithm of Polar Codes

Jiansong Miao, Weijie Li, Xuejia Hu +1 more

Polar codes are the first provably capacity-achieving novel channel codes. Successive cancellation list (SCL) decoding algorithm has a performance close to maximum-likelihood decoding when code length is finite, though the complexity is high. To reduce the complexity of SCL, a partial path expansion with segmented check and pruning SCL (PPE-SCP-SCL) algorithm is proposed in this paper. Based on the successive decoding structure, if the decoding result of a bit is judged to be reliable enough, then a hard decision is made directly and no path expansion is necessary. Moreover, several parity-check points are introduced to perform segmented parity-check during the decoding process, and if the check fails, the current path is directly abandoned. The rationality of the operations is theoretically verified, and numerical simulations also verify that the proposed algorithm can significantly reduce the complexity of decoding with trivial loss of error performance.

IEEE/CIC International Conference on Communications in China (ICCC)•Aug 9, 2020•0 citations

A new multiple folded successive cancellation decoder for polar codes

Harish Vangala, Emanuele Viterbo, Yi Hong

We consider a new variant of successive cancellation decoder (SCD) for polar codes based on the concept of folding, which was proposed in [1], [2] as technique to reduce the decoding latency at the cost of a higher computational complexity. In this paper, we first formally define the multiple folding operation (iterated κ times), which decomposes the original encoding graph into a number of smaller polar encoding graphs. More specifically, we show that the multiple folding gives rise to a two stage interpretation of the graph representing the polar encoder and the SCD. Based on this, we propose the improved multiple folded successive cancellation decoder (IMFSCD), which combines SCD in one stage and maximum-likelihood decoding in the other. This decoder exhibits a latency gain by a factor of 2κ, still retaining a complexity close to the classic SCD. The small increase in complexity is due to a short maximum likelihood decoder (MLD) used in place of a SCD in the last decoding stage within the IMFSCD. Moreover, we observe by simulation that the decoder performance is exactly the same as that of an SCD at all rates.

IEEE Information Theory Workshop (ITW)•Nov 1, 2014•8 citations

Successive Cancellation Decoding of Single Parity-Check Product Codes: Analysis and Improved Decoding Algorithms

Mustafa Cemil Coşkun, Gianluigi Liva, Alexandre Graell i Amat +1 more

A product code with single parity-check component codes can be seen as a special instance of a multi-kernel polar code, where the rows of the generator matrix are chosen according to the constraints imposed by the product code construction. Following this observation, successive cancellation decoding of such codes is introduced. In particular, the error probability of single parity-check product codes over the binary erasure channel under successive cancellation decoding is characterized. A bridge with the analysis of product codes introduced by Elias is also established. Successive cancellation list decoding of single parity-check product codes is then described. For the provided example, it is shown that successive cancellation list decoding outperforms belief propagation decoding performed on the code graph over the binary input additive white Gaussian channel. Finally, the performance of the concatenation of a product code with a high-rate outer code is investigated via distance spectrum analysis.

•Jan 1, 2018•0 citations
Reduced-Complexity Successive Cancelation Decoding of Z4\mathbb{Z}_{4}Z4​ Splitting Codes
In this paper, we present a novel suboptimal softinput decoding algorithm for linear codes over the ringZ4\mathbb{Z}_{4}Z4​(the ring of integers modulo 4), based on the lifting decoder technique. The proposed method operates directly on the parity-check matrix, unlike our previous successive cancellation decoder (SCD), which relies on the generator matrix. This results in a reduced number of arithmetic operations and lower computational complexity. The algorithm is demonstrated for a range of Kerdock codes and compared with both the maximum a posteriori (MAP) decoder and the classical SCD. Simulation results show that the proposed decoder achieves comparable error-rate performance to the MAP and classical SCD algorithms, while maintaining the same asymptotic complexity of the classical SCD algorithm, which in the case of Kerdock codes isO(Nlog⁡2N)O\left(N \log _{2} N\right)O(Nlog2​N).
Some nonlinear codes, such as Kerdock and Preparata codes, can be represented as binary images under the Gray map of linear codes over rings. This paper introduces MAP decoding of Kerdock and Preparata codes by working with their quaternary representation (linear codes overZ4\mathbb {Z}_{4}Z4​) with the complexity ofO(N2log⁡2N)\mathcal {O}(N^{2}\log _{2} N)O(N2log2​N), where N is the code length inZ4\mathbb {Z}_{4}Z4​. A sub-optimal bitwise APP decoder with good error-correcting performance and complexity ofO(Nlog⁡2N)\mathcal {O}(N\log _{2} N)O(Nlog2​N)that is constructed using the decoder lifting technique is also introduced. This APP decoder extends upon the original lifting decoder by working with likelihoods instead of hard decisions and is not limited to Kerdock and Preparata code families. Simulations show that our novel decoders significantly outperform several popular decoders in terms of error rate.
Many families of binary nonlinear codes (e.g., Kerdock, Goethals, Delsarte–Goethals, Preparata) can be very simply constructed from linear codes over the Z4 ring (ring of integers modulo 4), by applying the Gray map to the quaternary symbols. Generalized Kerdock codes represent an extension of classical Kerdock codes to the Z2S ring. In this paper, we develop two novel soft-input decoders, designed to exploit the unique structure of these codes. We introduce a novel soft-input ML decoding algorithm and a soft-input soft-output MAP decoding algorithm of generalized Kerdock codes, with a complexity of O(NSlog2N), where N is the length of the Z2S code, that is, the number of Z2S symbols in a codeword. Simulations show that our novel decoders outperform the classical lifting decoder in terms of error rate by some 5 dB.
In this letter, the principle of LLR-based successive-cancellation (SC) polar decoding algorithm is explored. In order to simplify the logarithm and exponential operations in the updating rules for polar codes, we further utilize a piece-wise linear algorithm to approximate the transcendental functions, where the piece-wise linear algorithm only consists of multiplication and addition operations. It is demonstrated that with one properly allowable maximum error δ chosen for success-failure algorithm, performances approach to that of the standard SC algorithm can be achieved. Besides, the complexity reduction is realized by calculating a linear function instead of nonlinear function. Simulation results show that our proposed piece-wise SC decoder greatly reduces the complexity of the SC-based decoders with no loss in error correcting performance.
Polar codes are the first provably capacity-achieving novel channel codes. Successive cancellation list (SCL) decoding algorithm has a performance close to maximum-likelihood decoding when code length is finite, though the complexity is high. To reduce the complexity of SCL, a partial path expansion with segmented check and pruning SCL (PPE-SCP-SCL) algorithm is proposed in this paper. Based on the successive decoding structure, if the decoding result of a bit is judged to be reliable enough, then a hard decision is made directly and no path expansion is necessary. Moreover, several parity-check points are introduced to perform segmented parity-check during the decoding process, and if the check fails, the current path is directly abandoned. The rationality of the operations is theoretically verified, and numerical simulations also verify that the proposed algorithm can significantly reduce the complexity of decoding with trivial loss of error performance.
We consider a new variant of successive cancellation decoder (SCD) for polar codes based on the concept of folding, which was proposed in [1], [2] as technique to reduce the decoding latency at the cost of a higher computational complexity. In this paper, we first formally define the multiple folding operation (iterated κ times), which decomposes the original encoding graph into a number of smaller polar encoding graphs. More specifically, we show that the multiple folding gives rise to a two stage interpretation of the graph representing the polar encoder and the SCD. Based on this, we propose the improved multiple folded successive cancellation decoder (IMFSCD), which combines SCD in one stage and maximum-likelihood decoding in the other. This decoder exhibits a latency gain by a factor of 2κ, still retaining a complexity close to the classic SCD. The small increase in complexity is due to a short maximum likelihood decoder (MLD) used in place of a SCD in the last decoding stage within the IMFSCD. Moreover, we observe by simulation that the decoder performance is exactly the same as that of an SCD at all rates.
A product code with single parity-check component codes can be seen as a special instance of a multi-kernel polar code, where the rows of the generator matrix are chosen according to the constraints imposed by the product code construction. Following this observation, successive cancellation decoding of such codes is introduced. In particular, the error probability of single parity-check product codes over the binary erasure channel under successive cancellation decoding is characterized. A bridge with the analysis of product codes introduced by Elias is also established. Successive cancellation list decoding of single parity-check product codes is then described. For the provided example, it is shown that successive cancellation list decoding outperforms belief propagation decoding performed on the code graph over the binary input additive white Gaussian channel. Finally, the performance of the concatenation of a product code with a high-rate outer code is investigated via distance spectrum analysis.