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

Bell System Technical Journal

Permutation Decoding of Systematic Codes

Jessie MacWilliams

Published Jan 1, 1964• 167 citations
Publisher

Abstract

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.

DOI
10.1002/j.1538-7305.1964.tb04075.x

Related papers

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

An Efficient Block Error Probability Estimation of Reed-Muller Codes under Permutation Decoding

Mikhail Kamenev

A method for estimating the block error probability of Reed-Muller codes on a binary erasure channel and a binary symmetric channel under a permutation decoding algorithm is proposed. This method is based on an analysis of the block error probability under a recursive decoding algorithm for a fixed number of input erasures or errors. Simulation results demonstrate that the proposed method allows to effectively predict the block error rate performance of Reed-Muller codes under permutation decoding with a different number of permutations used.

IEEE Information Theory Workshop (ITW)•Apr 11, 2021•0 citations

On the error-correcting capabilities of iterative error correction codes

Vasyl Semerenko

The influence of the theory of information on development of the error correcting coding theory has been studied. Main differences between the probabilistic approach and the deterministic approach in the analysis of error-correcting capabilities of different classes of linear codes have been demonstrated.The automaton hierarchical models for analysis of permutation decoding of cyclic codes have been developed and a cyclic permutation generator based on two Moore automata has been proposed.A study has been carried out into the regular and irregular states of linear finite-state machines (LFSM) based on the automaton representation of cyclic codes. A possibility of significant simplification of decoding of cyclic codes based on conversion of irregular LFSM syndromes into regular ones using permutations has been shown.The formalized methods for determination of error-correcting capabilities of iteratively decoded cyclic codes (IDCC) have been devised. They imply the replacementof traditional complete checking of all possible options for comparison of code words to directional search for the solution of the assigned problem, which leads to a significant time saving for calculations. The algorithm for determination of error-correcting capabilities of IDCC with respect to double errors is given.It has been shown that all iterative codes increase their error-correcting capabilities with an increase in the number of iterations and one can set it as a percentage for errors of various multiplicities. A distribution of error syndromes to separate iterations has been performed, which makes it possible to reduce the length of a check word in a code. As a result, this leads to an increase in a rate of iterative codes in comparison with the traditional correction codes.A comparative analysis of IDCC and LDPC codes has been carried out to determine a scope of their optimal use

Eastern-European Journal of Enterprise Technologies•Feb 21, 2019•1 citation

On the complete decoding of binary linear codes (Corresp.)

Michele Elia, G. Prati

Complete decoding of systematic linear block codes by standard arrays with coset leaders not necessarily of minimal weight gives, in several interesting cases on the binary symmetric channel with error probabilityp, a smaller symbol error probability than decoding using the coset leaders of minimum weight. The proposed choice of the coset leaders allows for the classes of uniformly packed and nearly perfect binary codes to achieve a lower information bit error probability, at least forpsufficiently near zero.

IEEE Transactions on Information Theory•Jul 1, 1985•8 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•9 citations

A Polar Subcode Approach to Belief Propagation List Decoding

Marvin Geiselhart, Ahmed Elkelesh, Jannis Clausius +1 more

Permutation decoding gained recent interest as it can exploit the symmetries of a code in a parallel fashion. Moreover, it has been shown that by viewing permuted polar codes as polar subcodes, the set of usable permutations in permutation decoding can be increased. We extend this idea to pre-transformed polar codes, such as cyclic redundancy check (CRC)-aided polar codes, which previously could not be decoded using permutations due to their lack of automorphisms. Using belief propagation (BP)-based subdecoders, we showcase a performance close to CRC-aided SCL (CA-SCL) decoding. The proposed algorithm outperforms the previously best performing iterative CRC-aided belief propagation list (CA-BPL) decoder both in error-rate performance and decoding latency.

arXiv:2205.06631•IEEE Information Theory Workshop (ITW)•Nov 1, 2022•8 citations
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.
A method for estimating the block error probability of Reed-Muller codes on a binary erasure channel and a binary symmetric channel under a permutation decoding algorithm is proposed. This method is based on an analysis of the block error probability under a recursive decoding algorithm for a fixed number of input erasures or errors. Simulation results demonstrate that the proposed method allows to effectively predict the block error rate performance of Reed-Muller codes under permutation decoding with a different number of permutations used.
The influence of the theory of information on development of the error correcting coding theory has been studied. Main differences between the probabilistic approach and the deterministic approach in the analysis of error-correcting capabilities of different classes of linear codes have been demonstrated.The automaton hierarchical models for analysis of permutation decoding of cyclic codes have been developed and a cyclic permutation generator based on two Moore automata has been proposed.A study has been carried out into the regular and irregular states of linear finite-state machines (LFSM) based on the automaton representation of cyclic codes. A possibility of significant simplification of decoding of cyclic codes based on conversion of irregular LFSM syndromes into regular ones using permutations has been shown.The formalized methods for determination of error-correcting capabilities of iteratively decoded cyclic codes (IDCC) have been devised. They imply the replacementof traditional complete checking of all possible options for comparison of code words to directional search for the solution of the assigned problem, which leads to a significant time saving for calculations. The algorithm for determination of error-correcting capabilities of IDCC with respect to double errors is given.It has been shown that all iterative codes increase their error-correcting capabilities with an increase in the number of iterations and one can set it as a percentage for errors of various multiplicities. A distribution of error syndromes to separate iterations has been performed, which makes it possible to reduce the length of a check word in a code. As a result, this leads to an increase in a rate of iterative codes in comparison with the traditional correction codes.A comparative analysis of IDCC and LDPC codes has been carried out to determine a scope of their optimal use
Complete decoding of systematic linear block codes by standard arrays with coset leaders not necessarily of minimal weight gives, in several interesting cases on the binary symmetric channel with error probabilityp, a smaller symbol error probability than decoding using the coset leaders of minimum weight. The proposed choice of the coset leaders allows for the classes of uniformly packed and nearly perfect binary codes to achieve a lower information bit error probability, at least forpsufficiently near zero.
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.
Permutation decoding gained recent interest as it can exploit the symmetries of a code in a parallel fashion. Moreover, it has been shown that by viewing permuted polar codes as polar subcodes, the set of usable permutations in permutation decoding can be increased. We extend this idea to pre-transformed polar codes, such as cyclic redundancy check (CRC)-aided polar codes, which previously could not be decoded using permutations due to their lack of automorphisms. Using belief propagation (BP)-based subdecoders, we showcase a performance close to CRC-aided SCL (CA-SCL) decoding. The proposed algorithm outperforms the previously best performing iterative CRC-aided belief propagation list (CA-BPL) decoder both in error-rate performance and decoding latency.