With any parity check matrix H of a code C(n,k,d) one may associate a graph whose vertices represent distinct bases, i.e., sets of n-k independent columns of H. Such basis specifies a unique error pattern. A search is carried out over a limited part of the bases graph for an error pattern having the minimum confidence value. Properties of the bases graph are utilized to reduce the complexity of the search procedure. Bounds are derived for the worst case computational complexity as well as for the correct-decoding probability.

Several additive codes of odd length over Z/sub 2//sup 2/ are introduced. These codes are cyclic and reversible. Furthermore, they are self-dual under an appropriately selected binary-valued inner product. Some binary derivatives of these codes have good parameters. All cyclic and reversible [5,2.5,3] additive codes over Z/sub 2//sup 2/ are isomorphic and possess interesting properties.

For pt. I see ibid. vol.46, p.1592-1601 (1998). Soft-decision maximum-likelihood decoding of convolutional codes over GF(q) can be accomplished via searching through an error-trellis for the least weighing error sequence. The error-trellis is obtained by a syndrome-based construction. Its structure lends itself particularly well to the application of expedited search procedures. The method to carry out such error-trellis-based decoding is formulated by four algorithms. Three of these algorithms are aimed at reducing the worst case computational complexity, whereas by applying the fourth algorithm, the average computational complexity is reduced under low to moderate channel wise level. The syndrome decoder achieves substantial worst case and average computational gains in comparison with the conventional maximum-likelihood decoder, namely the Viterbi decoder, which searches for the most likely codeword directly within the code.

An error-trellis is a directed graph that represents all the sequences belonging to the coset which contains the symbol-by-symbol detected version of a given received sequence. A modular construction of error-trellises for an (n,k) convolutional code over GF(q) is presented. The trellis is designed on the basis of partitioning the scalar check matrix of the code into submatrices of l rows, accompanied with a corresponding segmentation of the syndrome. The value of the design parameter l is an essentially unconstrained multiple of n-k. For all the cosets of the code, the sections of the error-trellis are drawn from a collection of only q/sup l/ modules; the module for each section is determined by the value of the associated syndrome segment. In case the construction is based on a basic polynomial check matrix, either canonical or noncanonical, then the error-trellis is minimal in the sense that /spl sigma//spl les//spl mu/, where /spl sigma/ is the dimension of the state space of the trellis and /spl mu/ is the constraint length of a canonical generator matrix for the code. For basic check matrices with delay-free columns, the inequality reduces to /spl sigma/=/spl mu/.

In this correspondence, various aspects of reliability-based syndrome decoding of binary codes are investigated. First, it is shown that the least reliable basis (LRB) and the most reliable basis (MRB) are dual of each other. By exploiting this duality, an algorithm performing maximum-likelihood (ML) soft-decision syndrome decoding based on the LRB is presented. Contrarily to previous LRB-based ML syndrome decoding algorithms, this algorithm is more conveniently implementable for codes whose codimension is not small. New sufficient conditions for optimality are derived. These conditions exploit both the ordering associated with the LRB and the structure of the code considered. With respect to MRR-based sufficient conditions, they present the advantage of requiring no soft information and thus can be preprocessed and stored. Based on these conditions, low-complexity soft-decision syndrome decoding algorithms for particular classes of codes are proposed. Finally, a simple algorithm is analyzed. After the construction of the LRB, this algorithm computes the syndrome of smallest Hamming weight among o(K/sup i/) candidates, where K is the dimension of the code, for an order i of reprocessing. At practical bit-error rates, for codes of length N/spl les/128, this algorithm always outperforms any algebraic decoding algorithm capable of correcting up to t+1 errors with an order of reprocessing of at most 2, where t is the error-correcting capability of the code considered.

Efficient code-search maximum-likelihood decoding algorithms, based on reliability information, are presented for binary Linear block codes. The codewords examined are obtained via encoding. The information set utilized for encoding comprises the positions of those columns of a generator matrix G of the code which, for a given received sequence, constitute the most reliable basis for the column space of G. Substantially reduced computational complexity of decoding is achieved by exploiting the ordering of the positions within this information set. The search procedures do not require memory; the codeword to be examined is constructed from the previously examined codeword according to a fixed rule. Consequently, the search algorithms are applicable to codes of relatively large size. They are also conveniently modifiable to achieve efficient nearly optimum decoding of particularly large codes.

A [6,3,4] code E/sub 6/ over an Abelian group A/sub 4/ with four elements is presented. E/sub 6/ is cyclic, unlike the [6,3,4] hexacode H/sub 6/ over GF(4). However, E/sub 6/ and H/sub 6/ are isomorphic when the latter is viewed as a group code. Differences and similarities between E/sub 6/ and H/sub 6/ are discussed. A dual code of E/sub 6/ is presented. Some binary codes, among them the [24,12,8] Golay, are derived with the aid of E/sub 6/. A related cyclic [4,2,3] code E/sub 4/* is applied to construct the Nordstrom-Robinson code. E/sub 6/ is the smallest member of a class of [2k,k,4] cyclic and reversible codes over A/sub 4/. Another class of cyclic and reversible codes of length 2l+1; l/spl ges/2 and minimum distance 3 over A/sub 4/ is also presented.

We present an efficient recursive algorithm for accomplishing maximum likelihood (ML) soft syndrome decoding of binary convolutional codes. The algorithm consists of signal-by-signal hard decoding followed by a search for the most likely error sequence. The number of error sequences to be considered is substantially larger than in hard decoding, since the metric applied to the error bits is the magnitude of the log likelihood ratio rather than the Hamming weight. An error-trellis (alternatively, a decoding table) is employed for describing the recursion equations of the decoding procedure. The number of its states is determined by the states indicator, which is a modified version of the constraint length of the check matrix. Methods devised for eliminating error patterns and degenerating error-trellis sections enable accelerated ML decoding. In comparison with the Viterbi algorithm, the syndrome decoding algorithm achieves substantial reduction in the average computational complexity, particularly for moderately noisy channels.>

We present algorithms for maximum likelihood soft decoding of the second order Reed-Muller codes RM(2,m) and the extended (24,12,8) Golay code. The decoding procedures are based on a concise representation of appropriately selected cosets of a subcode of the code considered. Such representation enables application of certain elimination rules. A structure, called constrained design, is established to support the elimination procedures. Remarkably efficient algorithms are obtainable by this approach. The method of elimination is applicable also in combination with existing coset decoding schemes.>

Transmission of information through a multiple-access-modulo-2 adder channel is addressed for the situation that out of a fixed family of N potential users at most some m, m>

Encoding and decoding schemes for concatenated multilevel block codes are presented. By one of these structures, a real coding gain of 5.6-7.4 dB for the bit error range of 10/sup -6/ to 10/sup -9/ is achieved for transmission through the additive white Gaussian noise channel. Also, a rather large asymptotic coding gain is obtained. The new coding schemes have very low decoding complexity and increased coding gain in comparison with the conventional block and trellis coded modulation structures. A few design rules for concatenated (single and) multilevel block codes with large coding gain are also provided.>

Efficient algorithms are derived for maximum likelihood (ML) soft-decision decoding of some binary self-dual codes. A family of easily decodable self-dual codes is derived by modifying a known F/sub 24/, which has a weight distribution resembling that of the (24, 12, 8) Golay code G/sub 24/. The ML decoding of F/sub 24/ is accomplished by only 227 real additions, compared to 651 required for G/sub 24/, yet the error rates of the two decoders are similar for moderate noise conditions.>

Satellite communications modeled by a feedforward random multiple-access system are considered. The transmission times of the users are governed by protocol signals. The authors consider the model of a slot-synchronized collision channel without feedback, proposed by J.L. Massey and P. Mathys (1985), augmented by interleavers that are essential for enabling the use of practical short codes. They assess the throughput of the channel on the basis of a short-coding error parameter. The set of parameters of all users characterizes the rate region achievable by employing short block codes with nonideal interleaving. The short-coding error parameter corresponds to a bound on the probability of error which is tighter than the bound expressed with the aid of the conventional cut-off rate. The analysis takes into account practical communication aspects, such as the effect of interleaving span and noise in noninterfered slots.>

A short-coding error parameter (SCEP) that provides a bound on the average probability of decoding error for codes with length shorter than the memory length is presented. It is shown that this bound is tighter than the bound based on the conventional cutoff rate and that the SCEP is independent of the channel's memory length, provided the codeword length is shorter than the memory length.>

A method whereby a substantially reduced family of error patterns, called survivors, may be created for maximum likelihood soft decoding is introduced. The family of survivor depends on the received word. A decoder based on this approach first forms the survivors, then scores them. Rather than obtaining the survivors by online elimination of error patterns, the use of predetermined lists that represent all families of survivors is proposed.>

An efficient algorithm is presented for maximum-likelihood soft-decision decoding of the Leech lattice. The superiority of this decoder with respect to both computational and memory complexities is demonstrated in comparison with previously published decoding methods. Gain factors in the range of 2-10 are achieved. The authors conclude with some more advanced ideas for achieving a further reduction of the algorithm complexity based on a generalization of the Wagner decoding method to two parity constraints. A comparison with the complexity of some trellis-coded modulation schemes is discussed. The decoding algorithm presented seems to achieve a computational complexity comparable to that of the equivalent trellis codes.>

Maximum-likelihood soft-decision decoding of linear block codes is addressed. 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. Besides efficient soft decoding of small codes, the generalized rule enables utilization of subspaces of a wide variety, thereby yielding maximum-likelihood decoders with substantially reduced computational complexity for some larger binary codes. More sophisticated choice and exploitation of the structure of both a subspace and the coset representatives are demonstrated for the (24, 12) Golay code, yielding a computational gain factor of about 2 with respect to previous methods. A ternary single-check version of the Wagner rule is applied for efficient soft decoding of the (12, 6) ternary Golay code.>

An approach for efficient utilization of fast Hadamard transform in decoding binary linear block codes is presented. Computational gain is obtained by employing various types of concurring codewords, and memory reduction is also achieved by appropriately selecting rows for the generator matrix. The availability of these codewords in general, and particularly in some of the most frequently encountered codes, is discussed.

It is standard practice to assume that second-order stationary signal and noise processes involved in a linear estimation procedure have spectral densities. A heuristic justification may be based on the reasoning that the part of the signal having singular spectral distribution can be precisely determined, and the part of the noise having singular spectral distribution can be completely eliminated. Rigorous phrasing and proof of this claim are given here for the most general case, i.e., where the singular parts of the spectral distributions may contain continuous components, in which situation the intuitive picture is obscure. The discussion includes both discrete-time and continuous-time processes, and the multivariable case is also treated.

The error covariance matrix corresponding to optimal linear causal filtering of second-order stationary processes in additive noise is considered. Formulas expressing this error matrix in terms of the optimal transfer function are established, and in the nonsingular case the optimal transfer function is expressed in terms of the spectral densities. These are straightforward generalizations of previously published scalar results, and the derivation is similarly based on Hardy space theory. Explicit bounds on the minimal error (i.e., the trace of the optimal error covariance matrix) are obtained for filtering in white noise. Furthermore, an explicit expression for the error covariance matrix is derived for the case of transmitting the same signal over several white-noise channels.

Error expressions for optimal linear causal filtering of second-order stationary processes are derived by a method based on Hardy space theory. This method is applicable when one of the spectral densities is rational with a known structure. The operations involved in the computation of error expressions are mainly simple residue evaluations. Several examples are given.