Bounds on the trellis size of linear block codes

IEEE Transactions on Information TheoryPublished 1 January 1993

Yaniv Berger, Y. Be'ery

DOI10.1109/18.179359

Source URL

Citations46

SJR quartileQ1

SJR score1.46

SNIP1.76

TL;DR

Two general upper bounds on the trellis size, based on the zero-concurring codewords and the contraction index of the subcodes, are presented and related permutations for attaining the bounds are exhibited.

Abstract

The size of minimal trellis representation of linear block codes is addressed. Two general upper bounds on the trellis size, based on the zero-concurring codewords and the contraction index of the subcodes, are presented. The related permutations for attaining the bounds are exhibited. These bounds evidently improve the previously published general bound. Additional bounds based on certain code constructions are derived. The focus is on the squaring construction, and specific constructive bounds for Reed-Muller and repeated-root cyclic codes are obtained. In particular, the recursive squaring construction of Reed-Muller codes is explored and the exact minimal trellis size of this design is obtained. Efficient permutations, in the sense of the trellis size, are also demonstrated by using shortening and puncturing methods. The corresponding bounds are specified.>

Keywords

Computer ScienceEngineering

North-Holland mathematical libraryThe Theory of Error-Correcting Codes

11,012 Citations1977

This book presents an introduction to BCH Codes and Finite Fields, and methods for Combining Codes, and discusses self-dual Codes and Invariant Theory, as well as nonlinear Codes, Hadamard Matrices, Designs and the Golay Code.

IEEE Transactions on Information TheoryCoset codes. II. Binary lattices and related codes

654 Citations1988G. David Forney

The family of Barnes-Wall lattices and their principal sublattices, which are useful in constructing coset codes, are generated by iteration of a simple construction called the squaring construction, and are represented by trellis diagrams that display their structure and interrelationships and that lead to efficient maximum-likelihood decoding algorithms.

IEEE Transactions on Information TheoryEfficient maximum likelihood decoding of linear block codes using a trellis

568 Citations1978J.K. Wolf

It is shown that soft decision maximum likelihood decoding of any (n,k) linear block code over GF(q) can be accomplished using the Viterbi algorithm applied to a trellis with no more than q^{(n-k)} states.

IEEE Transactions on Information TheoryOn repeated-root cyclic codes

216 Citations1991G. Castagnoli, James L. Massey +2 more

The relative minimum distance d/sub min//n of q-ary repeated-root cyclic codes of rate r>or=R is proven to tend to zero as the largest multiplicity of a root of the generator g(x) increases to infinity.

IEEE Transactions on Information TheoryMinimal trellises for block codes

216 Citations1988Douglas J. Muder

It is shown that minimal proper trellises exists for all block codes and bounds are shown to be exact for maximum distance separable codes and nearly so for perfect codes.

IEEE Transactions on Information TheoryRepeated-root cyclic codes

190 Citations1991J. H. van Lint

It is demonstrated that a binary cyclic code of length 2n (n odd) can be obtained from two cyclic codes of length n by the well-known mod u mod u+v mod construction, and the structure theorem generalizes to other characteristics and to other lengths.

View PDF

IEEE Transactions on Information TheoryMaximum likelihood soft decoding of binary block codes and decoders for the Golay codes

112 Citations1989J. Snyders, Y. Be'ery

A binary multiple-check generalization of the Wagner rule is presented, and two methods for its implementation, one of which resembles the suboptimal Forney-Chase algorithms, are described.

IEEE Transactions on CommunicationsBit-level soft-decision decoding of Reed-Solomon codes

92 Citations1991Alexander Vardy, Y. Be'ery

A Reed- Solomon decoder that makes use of bit-level soft-decision information is presented and a Reed-Solomon generator matrix that possesses a certain inherent structure in GF(2) is derived.

IEEE Transactions on Information TheoryOptimal soft decision block decoders based on fast Hadamard transform

91 Citations1986Y. Be'ery, J. Snyders

An approach for efficient utilization of fast Hadamard transform in decoding binary linear block codes is presented and the availability of these codewords in general, and particularly in some of the most frequently encountered codes, is discussed.

IEEE Transactions on Information TheoryShortened BCH codes (Corresp.)

39 Citations1973Hermann J. Helgert, R. Stinaff

By shortening certain binary primitive BCH codes, a number of linear error-correcting codes with minimum distances superior to any known previously are derived.