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

IEEE Transactions on Information Theory

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

Roland D. Barrolleta, Mercè Villanueva

Published May 24, 2018• 8 citations
Publisher

Abstract

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.

DOI
10.1109/tit.2018.2840226

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

Permutation Decoding and the Stopping Redundancy Hierarchy of Cyclic and Extended Cyclic Codes

Abstract — We introduce the notion of the stopping redundancy hierarchy of a linear block code as a measure of the trade-off between performance and complexity of iterative decoding for the binary erasure channel. We derive lower and upper bounds for the stopping redundancy hierarchy via Lovász’s Local Lemma and Bonferroni-type inequalities, and specialize them for codes with cyclic parity-check matrices. Based on the observed prop-erties of parity-check matrices with good stopping redundancy characteristics, we develop a novel decoding technique, termed automorphism group decoding, that combines iterative message passing and permutation decoding. We also present bounds on the smallest number of permutations of an automorphism group decoder needed to correct any set of erasures up to a prescribed size. Simulation results demonstrate that for a large number of algebraic codes, the performance of the new decoding method is close to that of maximum likelihood decoding.

•Feb 28, 2015•0 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

Permutation Decoding and the Stopping Redundancy Hierarchy of Cyclic and Extended Cyclic Codes

Thorsten Hehn, Olgica Milenković, Stefan Laendner +1 more

We introduce the notion of the stopping redundancy hierarchy of a linear block code as a measure of the tradeoff between performance and complexity of iterative decoding for the binary erasure channel. We derive lower and upper bounds for the stopping redundancy hierarchy via Lovasz's local lemma (LLL) and Bonferroni-type inequalities, and specialize them for codes with cyclic parity-check matrices. Based on the observed properties of parity-check matrices with good stopping redundancy characteristics, we develop a novel decoding technique, termed automorphism group decoding, that combines iterative message passing and permutation decoding. We also present bounds on the smallest number of permutations of an automorphism group decoder needed to correct any set of erasures up to a prescribed size. Simulation results demonstrate that for a large number of algebraic codes, the performance of the new decoding method is close to that of maximum-likelihood (ML) decoding.

arXiv:0708.0905•IEEE Transactions on Information Theory•Dec 1, 2008•33 citations

Permutation Decoding of Systematic Codes

Jessie MacWilliams

A symmetry of a systematic code is a permutation of bit positions in each code word (the same permutation is applied to all code words) which preserves the code as a whole. Permutation decoding makes use of these symmetries to build up a decoding algorithm for the code. It is difficult to find an appropriate set of symmetries for a code picked at random. For cyclic codes the problem is somewhat easier, and for some special cyclic codes it is solved completely in this paper. For these codes, at least, it is evident that permutation decoding is easy to implement and inexpensive compared with other decoding schemes. Permutation decoding as a n eans of error control is evaluated for the binary symmetric channel and for the switched telephone network as represented by experimental data. It is found to be extremely effective on the binary symmetric channel and of very doubtful value on the present telephone network.

Bell System Technical Journal•Jan 1, 1964•165 citations

Permutation Decoding and the Stopping Redundancy Hierarchy of Linear Block Codes

Thorsten Hehn, Olgica Milenković, Stefan Laendner +1 more

We investigate the stopping redundancy hierarchy of linear block codes and its connection to permutation decoding techniques. An element in the ordered list of stopping redundancy values represents the smallest number of possibly linearly dependent rows in any parity-check matrix of a code that avoids stopping sets of up to a given size. Redundant parity-check equations can be shown to have a similar effect on decoding performance as permuting the coordinates of the received codeword according to a selected set of automorphisms of the code. Based on this finding we develop new decoding strategies for data transmission over the binary erasure channel that combine iterative message passing and permutation decoding in order to avoid errors confined to stopping sets. We also introduce the notion of s-SAD sets, containing the smallest number of automorphisms of a code with the property that they move any set of not more than s erasures into positions that do not correspond to stopping sets within a judiciously chosen parity-check matrix.

arXiv:cs/0702050•IEEE International Symposium on Information Theory (ISIT)•Jun 1, 2007•3 citations
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.
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.
Abstract — We introduce the notion of the stopping redundancy hierarchy of a linear block code as a measure of the trade-off between performance and complexity of iterative decoding for the binary erasure channel. We derive lower and upper bounds for the stopping redundancy hierarchy via Lovász’s Local Lemma and Bonferroni-type inequalities, and specialize them for codes with cyclic parity-check matrices. Based on the observed prop-erties of parity-check matrices with good stopping redundancy characteristics, we develop a novel decoding technique, termed automorphism group decoding, that combines iterative message passing and permutation decoding. We also present bounds on the smallest number of permutations of an automorphism group decoder needed to correct any set of erasures up to a prescribed size. Simulation results demonstrate that for a large number of algebraic codes, the performance of the new decoding method is close to that of maximum likelihood decoding.
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.
We introduce the notion of the stopping redundancy hierarchy of a linear block code as a measure of the tradeoff between performance and complexity of iterative decoding for the binary erasure channel. We derive lower and upper bounds for the stopping redundancy hierarchy via Lovasz's local lemma (LLL) and Bonferroni-type inequalities, and specialize them for codes with cyclic parity-check matrices. Based on the observed properties of parity-check matrices with good stopping redundancy characteristics, we develop a novel decoding technique, termed automorphism group decoding, that combines iterative message passing and permutation decoding. We also present bounds on the smallest number of permutations of an automorphism group decoder needed to correct any set of erasures up to a prescribed size. Simulation results demonstrate that for a large number of algebraic codes, the performance of the new decoding method is close to that of maximum-likelihood (ML) decoding.
A symmetry of a systematic code is a permutation of bit positions in each code word (the same permutation is applied to all code words) which preserves the code as a whole. Permutation decoding makes use of these symmetries to build up a decoding algorithm for the code. It is difficult to find an appropriate set of symmetries for a code picked at random. For cyclic codes the problem is somewhat easier, and for some special cyclic codes it is solved completely in this paper. For these codes, at least, it is evident that permutation decoding is easy to implement and inexpensive compared with other decoding schemes. Permutation decoding as a n eans of error control is evaluated for the binary symmetric channel and for the switched telephone network as represented by experimental data. It is found to be extremely effective on the binary symmetric channel and of very doubtful value on the present telephone network.
We investigate the stopping redundancy hierarchy of linear block codes and its connection to permutation decoding techniques. An element in the ordered list of stopping redundancy values represents the smallest number of possibly linearly dependent rows in any parity-check matrix of a code that avoids stopping sets of up to a given size. Redundant parity-check equations can be shown to have a similar effect on decoding performance as permuting the coordinates of the received codeword according to a selected set of automorphisms of the code. Based on this finding we develop new decoding strategies for data transmission over the binary erasure channel that combine iterative message passing and permutation decoding in order to avoid errors confined to stopping sets. We also introduce the notion of s-SAD sets, containing the smallest number of automorphisms of a code with the property that they move any set of not more than s erasures into positions that do not correspond to stopping sets within a judiciously chosen parity-check matrix.