IEEE Transactions on Information Theory

A large automorphism group decreases the number of computations in the construction of an optimal encoder/decoder pair for linear block code

Ludo M. G. M. Tolhuizen, W.J. Van Gils

Published Mar 1, 1988• 7 citations

Abstract

For a linear block code it is shown how the number of computations needed for the determination of an optimal encoder/decoder pair can be reduced by using the code's automorphism group. Furthermore, it is shown that the use of an unequal-error-protection-optical generator matrix and a minimum-weight coset leader decoder is suboptimal for a q-ary symmetry channel, but their determination needs less computational effort.>

DOI: 10.1109/18.2646

Related papers

Optimal information bit decoding of linear block codes

Aaron B. Kiely, J.T. Coffey, Mark R. Bell

We consider the problem of decoding a linear block code used over a binary symmetric channel with crossover probability p when the goal of the decoding is to minimize the probability of an information bit error. In general, there will be several different decoding strategies, each corresponding to the optimal rule over some range p/spl isin/[p/sub i-1/, p/sub i/]. Each of these strategies can be implemented by standard array with the appropriate choice of coset leaders that are not in general of minimum weight. We give optimal rules for selecting coset leaders in the first region [0, p/sub 1/] and the region [p/sub max/, 1/2] for any linear mapping between information bits and codewords. The determination of the optimal rule has been an open problem for small p. The rule for p>p/sub max/ is important because for many codes, when p is fixed the optimal rule for any coset corresponds to either the optimal rule for small p, or the optimal rule for p near 1/2. The optimal decoding strategy varies with the generator matrix used in general, but it is demonstrated that the optimal generator matrix is separable when d/sup /spl perp//>2. The results are shown to extend in a natural way to the case where the goal is to minimize the probability that arbitrary collections of information bits are in error. We examine some specific codes, and compare the performance under optimal decoding to the performance of previously suggested strategies.>

IEEE Transactions on Information TheoryJan 1, 199511 citations

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 TheoryJul 1, 19858 citations

Implementing gradient descent decoding

Robert A. Liebler

Abstract Given a linear block code on a BSC channel, and arbitrary pre-determined information about the coset of each possible received sequence, a method is given for construction of a new kind of parity check matrix that carries the given information. This pre-determined coset data is easily reconstructed by a simple decoder. When this coset information is related to coset leader weight, there is simple iterative gradient descent algorithm that is optimal, provably accurate and potentially of low complexity. An explicit gradient function construction is given for an code for which pseudo-codewords obstruct LDPC decoding convergence. 1 Introduction Many communication channels accept as input binary strings and return output strings of the same length that have been altered and whose terms can be interpreted as "the probability that 1 was sent in this position. " This paper is restricted to the binary symmetric channel (BSC) for which the output is also binary although the basic ideas seem to apply more generally. The task of a decoding algorithm is to reconstruct sent message(s) from the channel output. There are several critical attributes of a decoding algorithm. The design complexity is a measure of the effort required to design and implement an instance of the algorithm. The implementation cost is a measure of the (time and space) resources required to decode messages once the algorithm is implemented. The apparent accuracy of an algorithm is a measure of its ability to actually identify a nearest codeword to a given message in practice. The proven accuracy is a measure of the algorithm's proven ability to correctly move from message to nearest codeword without failure of any kind. A decoding algorithm is optimal if it correctly identifies the most likely channel error for each channel output for which there is a unique such error.

The Michigan Mathematical JournalMay 1, 200910 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.0905IEEE Transactions on Information TheoryDec 1, 200833 citations

Generalized Automorphisms of Channel Codes: Properties, Code Design, and a Decoder

Jonathan Mandelbaum, Holger Jäkel, Laurent Schmalen

Low-density parity-check codes together with belief propagation (BP) decoding are known to be well-performing for large block lengths. However, for short block lengths there is still a considerable gap between the performance of BP decoding and maximum likelihood decoding. Different ensemble decoding schemes such as, e.g., automorphism ensemble decoding (AED), can reduce this gap in short block length regime. We propose generalized AED (GAED) that uses automorphisms according to the definition in linear algebra. Here, an automorphism of a vector space is defined as a linear, bijective self-mapping, whereas in coding theory self-mappings that are scaled permutations are commonly used. We show that the more general definition leads to an explicit joint construction of codes and automorphisms, and significantly enlarges the search space for automorphisms of existing linear codes. Furthermore, we prove the concept that generalized automorphisms can indeed be used to improve decoding. Additionally, we propose a code construction of linear codes enabling the construction of codes with suitably designed automorphisms. Finally, we analyze the decoding performances of GAED for some of our constructed codes.

arXiv:2304.14379International Symposium on Turbo Codes and Iterative Information ProcessingSep 4, 20236 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 Lová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, 20150 citations