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

Mathematics

Decoding of Z2S Linear Generalized Kerdock Codes

Aleksandar Minja, V. Šenk

Published Jan 30, 2024• 2 citations
Publisher

Abstract

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.

DOI
10.3390/math12030443

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

Linear-Programming Decoding of Nonbinary Linear Codes

Mark F. Flanagan, Vitaly Skachek, Eimear Byrne +1 more

A framework for linear-programming (LP) decoding of nonbinary linear codes over rings is developed. This framework facilitates LP-based reception for coded modulation systems which use direct modulation mapping of coded symbols. It is proved that the resulting LP decoder has the ldquomaximum-likelihood (ML) certificaterdquo property. It is also shown that the decoder output is the lowest cost pseudocodeword. Equivalence between pseudocodewords of the linear program and pseudocodewords of graph covers is proved. It is also proved that if the modulator-channel combination satisfies a particular symmetry condition, the codeword error rate performance is independent of the transmitted codeword. Two alternative polytopes for use with LP decoding are studied, and it is shown that for many classes of codes these polytopes yield a complexity advantage for decoding. These polytope representations lead to polynomial-time decoders for a wide variety of classical nonbinary linear codes. LP decoding performance is illustrated for ternary Golay code with ternary phase-shift keying (PSK) modulation over additive white Gaussian noise (AWGN), and in this case it is shown that the performance of the LP decoder is comparable to codeword-error-rate-optimum hard-decision-based decoding. LP decoding is also simulated for medium-length ternary and quaternary low-density parity-check (LDPC) codes with corresponding PSK modulations over AWGN.

arXiv:0707.4360•IEEE Transactions on Information Theory•Aug 24, 2009•66 citations

Partial Permutation Decoding for Several Families of Linear and ${\mathbb{Z}}_4$ -Linear Codes

Roland D. Barrolleta, Mercè Villanueva

A general criterion to obtain s-PD-sets of minimum size s + 1 for partial permutation decoding, which enable correction up to s errors, for systematic codes over a finite field Fq and Z4-linear codes is provided. We show how this technique can be easily applied to linear cyclic codes over Fq, Z4-linear codes which are the Gray map image of a quaternary linear cyclic code, and some related codes such as quasi-cyclic codes. Furthermore, specific results for some linear and nonlinear binary codes, including simplex, Kerdock, Delsarte-Goethals, and extended dualized Kerdock codes are given. Finally, applying this technique, new s-PD-sets of size s + 1 for Z4-linear Hadamard codes of type 2γ4δ, for all δ ≥ 4 and 1δ- 3; and for Z4-linear simplex codes of type 4m, for all m ≥ 2 and 1m+1- 3, are also provided.

IEEE Transactions on Information Theory•May 24, 2018•8 citations

Iterative soft decoding of binary linear codes using a generalized Tanner graph

Eirik Rosnes

In this work, we consider iterative soft-decision decoding of binary linear codes using a generalized Tanner graph. A generalized Tanner graph is constructed from the code's Tanner graph representation under the objective of mitigating the effect of small cycles. Then, iterative decoding is applied to the generalized Tanner graph using trellis-based soft-input soft-output decoding in the generalized check nodes. When combined with the stochastic shifting algorithm of Jiang and Narayanan (IEEE Commun. Letters, 2004), the proposed decoding method provides both improved error rate performance and reduced average decoding complexity, without increasing the worst-case decoding complexity.

IEEE Information Theory Workshop (ITW)•Oct 1, 2011•0 citations

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

Aleksandar Minja

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)$.

Telecommunications Forum (TELFOR)•Nov 25, 2025•0 citations

SCL Decoding of Non-Binary Linear Block Codes

Jingyu Lin, Li Chen, Xiaoqian Ye

Non-binary linear block codes (NB-LBCs) are an important class of error-correcting codes that are especially competent in correcting burst errors. They have broad applications in modern communications and storage systems. However, efficient soft-decision decoding of these codes remains to be further developed. This paper proposes successive cancellation list (SCL) decoding for NB-LBCs that are defined over a finite field of characteristic two, i.e., F2r, whereris the extension degree. By establishing a one-to-r mapping between the binary composition of each non-binary codeword andrbinary polar codewords, SCL decoding of therpolar codes can be performed with a complexity that is sub-quadratic in the codeword length. A simplified path sorting is further proposed to facilitate the decoding. Simulation results on short-length extended Reed-Solomon (eRS) and non-binary extended BCH (NB-eBCH) codes show that SCL decoding can outperform their state-of-the-art soft-decision decoding with fewer finite field arithmetic operations. For length-16 eRS codes, their maximum-likelihood (ML) decoding performances can be approached with a moderate list size.

arXiv:2511.11256•IEEE Communications Letters•Jan 1, 2026•0 citations
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.
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.
A framework for linear-programming (LP) decoding of nonbinary linear codes over rings is developed. This framework facilitates LP-based reception for coded modulation systems which use direct modulation mapping of coded symbols. It is proved that the resulting LP decoder has the ldquomaximum-likelihood (ML) certificaterdquo property. It is also shown that the decoder output is the lowest cost pseudocodeword. Equivalence between pseudocodewords of the linear program and pseudocodewords of graph covers is proved. It is also proved that if the modulator-channel combination satisfies a particular symmetry condition, the codeword error rate performance is independent of the transmitted codeword. Two alternative polytopes for use with LP decoding are studied, and it is shown that for many classes of codes these polytopes yield a complexity advantage for decoding. These polytope representations lead to polynomial-time decoders for a wide variety of classical nonbinary linear codes. LP decoding performance is illustrated for ternary Golay code with ternary phase-shift keying (PSK) modulation over additive white Gaussian noise (AWGN), and in this case it is shown that the performance of the LP decoder is comparable to codeword-error-rate-optimum hard-decision-based decoding. LP decoding is also simulated for medium-length ternary and quaternary low-density parity-check (LDPC) codes with corresponding PSK modulations over AWGN.
Partial Permutation Decoding for Several Families of Linear and Z4{\mathbb{Z}}_4Z4​ -Linear Codes
A general criterion to obtain s-PD-sets of minimum size s + 1 for partial permutation decoding, which enable correction up to s errors, for systematic codes over a finite field Fq and Z4-linear codes is provided. We show how this technique can be easily applied to linear cyclic codes over Fq, Z4-linear codes which are the Gray map image of a quaternary linear cyclic code, and some related codes such as quasi-cyclic codes. Furthermore, specific results for some linear and nonlinear binary codes, including simplex, Kerdock, Delsarte-Goethals, and extended dualized Kerdock codes are given. Finally, applying this technique, new s-PD-sets of size s + 1 for Z4-linear Hadamard codes of type 2γ4δ, for all δ ≥ 4 and 1δ- 3; and for Z4-linear simplex codes of type 4m, for all m ≥ 2 and 1m+1- 3, are also provided.
In this work, we consider iterative soft-decision decoding of binary linear codes using a generalized Tanner graph. A generalized Tanner graph is constructed from the code's Tanner graph representation under the objective of mitigating the effect of small cycles. Then, iterative decoding is applied to the generalized Tanner graph using trellis-based soft-input soft-output decoding in the generalized check nodes. When combined with the stochastic shifting algorithm of Jiang and Narayanan (IEEE Commun. Letters, 2004), the proposed decoding method provides both improved error rate performance and reduced average decoding complexity, without increasing the worst-case decoding complexity.
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).
Non-binary linear block codes (NB-LBCs) are an important class of error-correcting codes that are especially competent in correcting burst errors. They have broad applications in modern communications and storage systems. However, efficient soft-decision decoding of these codes remains to be further developed. This paper proposes successive cancellation list (SCL) decoding for NB-LBCs that are defined over a finite field of characteristic two, i.e., F2r, whereris the extension degree. By establishing a one-to-r mapping between the binary composition of each non-binary codeword andrbinary polar codewords, SCL decoding of therpolar codes can be performed with a complexity that is sub-quadratic in the codeword length. A simplified path sorting is further proposed to facilitate the decoding. Simulation results on short-length extended Reed-Solomon (eRS) and non-binary extended BCH (NB-eBCH) codes show that SCL decoding can outperform their state-of-the-art soft-decision decoding with fewer finite field arithmetic operations. For length-16 eRS codes, their maximum-likelihood (ML) decoding performances can be approached with a moderate list size.