Search

In this correspondence, we present an interleaving scheme that yields quasi-cyclic turbo codes. We prove that randomly chosen members of this family yield with probability almost 1 turbo codes with asymptotically optimum minimum distance, i.e., growing as a logarithm of the interleaver size. These interleavers are also very practical in terms of memory requirements and their decoding error probabilities for small block lengths compare favorably with previous interleaving schemes. Index Terms--Convolutional codes, iterative decoding, minimum distance, quasi-cyclic codes, turbo codes.

In this correspondence, we introduce a new class of low-rate error correction codes called zigzag Hadamard (ZH) codes and their concatenation schemes. Each member of this class of codes is specified by a highly structured zigzag graph with each segment being a Hadamard codeword. The ZH codes enjoy extremely simple encoding and very low-complexity soft-input-soft-output (SISO) decoding based on a posteriori probability (APP) fast Hadamard transform (FHT) technique. We present an asymptotic performance analysis of the proposed concatenated ZH codes using the extrinsic mutual information transfer (EXIT) chart for infinite-length codes. We also provide a union bound analysis of the error performance for finite-length codes. Furthermore, the concatenated ZH codes are shown to be a good class of codes in the low-rate region. Specifically, a rate-0.0107 concatenated code with three ZH components and an interleaver size of 65536 can achieve the bit error rate (BER) performance of [10.-sup.-5] at -1.15 dB, which is only 0.44 dB away from the ultimate Shannon limit. The proposed concatenated ZH codes offer similar performance as another class of low-rate codes-the turbo-Hadamard codes, and better performance than superorthogonal turbo codes, with much lower encoding and decoding complexities. Index Terms--Extrinsic mutual information transfer (EXIT) chart, Hadamard codes, low-complexity decoding, low rate, parallel concatenation, union bound, zigzag codes.

We generalize a characterization of p-ary (p is a prime) quantum codes given by Feng and Xing to q-ary (q is a prime power) quantum codes. This characterization makes it possible to convert an asymptotic bound of Stichtenoth and Xing for nonlinear algebraic geometry codes to a quantum asymptotic bound. Besides, we also investigate the asymptotic behavior of quantum codes. Index Terms--Algebraic-geometry codes, asymptotic behavior, propagation rules.

The rank and kernel of 1-perfect additive codes is determined. Additive codes could be seen as translation-invariant propelinear codes and, in this correspondence, a characterization of propelinear codes as codes having a regular subgroup of the full group of isometries of the code is established. A characterization of the automorphism group of a 1-perfect additive code is given and also the cardinality of this group is computed. Finally, an efficiently computable characterization of the Steiner triple systems associated with a 1-perfect binary additive code is also established. Index Terms--Additive codes, automorphism group, kernel, 1-perfect codes, rank.

Bounds on the redundancy of the recency-rank and block-sorting universal lossless data compression algorithms for finite-length sequences are presented. These algorithms are asymptotically optimal for infinite-length sequences, stationary ergodic sources in the almost-sure sense, and asymptotically mean stationary sources in the average and almost-sure sense. Index Terms--Block-sorting algorithm, book-stack algorithm, Burrows-Wheeler transform, lossless data compression, move-to-front algorithm, recency-rank algorithm, universal code.

We consider the search problem in which one finds a binary word among m words chosen randomly from the set of all words of fixed length n. It is well known that the optimal search is equivalent to the Huffman coding that requires on average [log.sub.2] m bits to be checked plus a small additional cost called the average redundancy. The latter is an oscillating function of m and is bounded between zero and 1 - (1 + ln ln 2)/ln 2 [approximately equal to] 0.0860713320. As a matter of fact, it is known that finding the optimal strategy for this problem is NP-hard. We propose here several simple randomized search strategies leading, respectively, to the following average redundancies: 1.332746177, 0.6113986565, 0.4310617764, and 0.332746177, plus some small oscillations that we precisely characterize. These results should be compared to the optimal, but NP-hard, search algorithm. Our findings extend and make more precise recent results of Fedotov and Ryabko. Index Terms--Generating functions, Huffman code, PATRICIA trie, search problem, Shannon source coding theorem, tries.

This correspondence shows the equivalence of three previously proposed reduced-rank detection schemes for direct-sequence code-division multiple-access (DS-CDMA) communication systems. The auxiliary vector filtering (AVF) algorithm is simplified through a key observation on the construction of the auxiliary vectors. After simplification, it is shown that the AVF algorithm is equivalent to the multistage Wiener filtering (MWF) algorithm of Honig and Goldstein. Furthermore, these schemes can be shown to be equivalent to the multistage linear receiver scheme based on the Cayley-Hamilton (CH) theorem when the minimum mean-square error (MMSE) criterion is applied to the reduced dimensional space of the received signal.

We characterize codes over [Z.sub.p] which are the Gray images of (1 - [p.sup.k])-cyclic codes or cyclic codes over [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (k [greater than or equal to] 1). A necessary and sufficient condition for the Gray image of a [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]-linear (1 - p)-cyclic code to be linear is given. In many cases, this yields an explicit description of the Gray image of a linear (1 - p)-cyclic code over [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], of length relatively prime to p. Linear cyclic codes over [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] a whose Gray images are linear cyclic codes over [Z.sub.p] have been characterized. Some generalizations of these results to the case of [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], where k [greater than or equal to] 2, are also obtained. Index Terms--Constacyclic code, cyclic code, Gray map, linear code, quasi-cyclic code.

The slope of the active distances is an important parameter when investigating the error-correcting capability of convolutional codes and the distance behavior of concatenated convolutional codes. The slope of the active distances is equal to the minimum average weight cycle in the state-transition diagram of the encoder. A general upper bound on the slope depending on the free distance of the convolutional code and new upper bounds on the slope of special classes of binary convolutional codes are derived. Moreover, a search technique, resulting in new tables of rate R = 1/2 and rate R = 1/3 convolutional encoders with high memories and large active distance-slopes is presented. Furthermore, we show that convolutional codes with large slopes can be used to obtain new tailbiting block codes with large minimum distances. Tables of rate R = 1/2 and rate R = 1/3 tailbiting codes with larger minimum distances than the best previously known quasi-cyclic codes are given. Two new tailbiting codes also have larger minimum distances than the best previously known binary linear block codes with same size and length. One of them is also superior in terms of minimum distance to any previously known binary nonlinear block code with the same set of parameters. Index Terms--Active distances, convolutional codes, minimum distance, quasi-cyclic codes, tailbiting codes.

We derive upper bounds on the rate of low-density parity-check (LDPC) codes for which reliable communication is achievable. We first generalize Gallager's bound to a general binary-input symmetric-output channel. We then proceed to derive tighter bounds. We also derive upper bounds on the rate as a function of the minimum distance of the code. We consider both individual codes and ensembles of codes. Index Terms--Error probability, iterative decoding, low-density parity-check (LDPC) codes, maximum-likelihood (ML) decoding, minimum distance.

This paper focuses on jammed timing channels. Pure delay jammers with a maximum delay constraint, an average delay constraint, or a maximum buffer size constraint are explored, for continuous-time or discrete-time packet waveforms. Fluid waveform approximations of each of these classes of waveforms are employed to aid in analysis. Channel capacity is defined and an information-theoretic game based on mutual information rate is studied. Min-max optimal jammers and max-min optimal input processes are sought. Bounds on the min-max and max-min mutual information rates are described, and numerical examples are given. For maximum-delay-constrained (MDC) jammers with continuous-time packet waveforms, saddle-point input and jammer strategies are identified. The capacity of the maximum-delay constrained jamming channel with continuous-time packet waveforms is shown to equal the mutual information rate of the saddle point. For MDC jammers with discrete-time packet waveforms, saddle-point strategies are shown to exist. Jammers which have quantized batch departures at regular intervals are shown to perform well. Input processes with batches at regular intervals perform well for MDC or maximum-buffer-size-constrained jammers. Index Terms--Channel coding, covert timing channels, jamming, network security.

Recently, (linear) codes over [Z.sub.4] and quasi-cyclic (QC) codes (over fields) have been shown to yield useful results in coding theory. Combining these two ideas we study [Z.sub.4]-QC codes and obtain new binary codes using the usual Gray map. Among the new codes, the lift of the famous Golay code to [Z.sub.4] produces a new binary code, a (92, [2.sub.24], 28)-code, which is the best among all binary codes (linear or nonlinear). Moreover, we characterize cyclic codes corresponding to free modules in terms of their generator polynomials. Index Terms--Gray map, quasi-cyclic (QC) codes, [Z.sub.4] codes.

Binary prefix-free codes in which all codewords end with a "1" have been introduced by Berger and Yeung. A recursive method is given here for the construction of all optimal "1"-ended codes with n codewords. It is shown that the set of codes obtained by the construction contains only optimal codes. We also compute recursively the number of essentially different optimal "1"-ended codes with n codewords and show that their number grows faster than any polynomial in n. Index Terms--One-ended codes, optimal codes, prefix-free codes, variable-length coding.

In this correspondence, we evaluate the variance of the union performance bound for a rate-1/3 turbo code over all possible interleavers of length N, under the assumption of a maximum-likelihood (ML) decoder. Theoretical and simulation results for turbo codes with two-memory component codes indicate that the coefficient of variation of the bound increases with the signal-to-noise ratio and decreases with the interleaver length. Theoretical analysis for large interleaver lengths shows that the coefficient of variation asymptotically approaches a constant value. The results also demonstrate that the majority of the interleavers have performance bounds very close to the average value of the bound. This phenomenon is more palpable for larger interleaver lengths. Index Terms--Channel coding, concatenated codes, turbo codes, union performance bound.

In this correspondence, new extremal self-dual codes of length 62 are constructed with weight enumerators of three different types. Two of these types were not represented by any known code up till now. All these codes possess an automorphism of order 15. Some of them are used to construct extremal self-dual codes of length 60 by the method of subtracting.

Multiple-antenna systems that operate at high rates require simple yet effective space-time transmission schemes to handle the large traffic volume in real time. At rates of tens of bits per second per hertz, Vertical Bell Labs Layered Space-Time (V-BLAST), where every antenna transmits its own independent substream of data, has been shown to have good performance and simple encoding and decoding. Yet V-BLAST suffers from its inability to work with fewer receive antennas than transmit antennas--this deficiency is especially important for modern cellular systems, where a base station typically has more antennas than the mobile handsets. Furthermore, because V-BLAST transmits independent data streams on its antennas there is no built-in spatial coding to guard against deep fades from any given transmit antenna. On the other hand, there are many previously proposed space-time codes that have good fading resistance and simple decoding, but these codes generally have poor performance at high data rates or with many antennas. We propose a high-rate coding scheme that can handle any configuration of transmit and receive antennas and that subsumes both V-BLAST and many proposed space-time block codes as special cases. The scheme transmits substreams of data in linear combinations over space and time. The codes are designed to optimize the mutual information between the transmitted and received signals. Because of their linear structure, the codes retain the decoding simplicity of V-BLAST, and because of their information-theoretic optimality, they possess many coding advantages. We give examples of the codes and show that their performance is generally superior to earlier proposed methods over a wide range of rates and signal-to-noise ratios (SNRs). Index Terms--Bell Labs Layered Space-Time (BLAST), fading channels, multiple antennas, receive diversity, space-time codes, transmit diversity, wireless communications.

In this paper, we characterize the full automorphism groups of homogeneous and projective Reed-Muller (HRM and PRM) codes. These groups are respectively related to general and projective linear groups. Index Terms--Automorphism, projective linear group, projective Reed-Muller (PRM) codes.

A linear [[n, k, d].sub.q] code C is called near maximum-distance separable (NMDS) if d(C) = n - k and d([C.sup.[perpendicular to]]) = k. The maximum length of an NMDS [[n, k, d].sup.q] code is denoted by m'(k, q). In this correspondence, it has been verified by a computer-based proof that m'(5, 8) = 15, m'(4, 9) = 16, m'(5, 9) = 16, and 20 [less than or equal to] m'(4, 11) [less than or equal to] 21. Moreover, the NMDS codes of length m'(4.8), m'(5, 8), and m'(4, 9) have been classified. As the dual code of an NMDS code is NMDS, the values of m'(k, 8), k = 10, 11, 12, and of m'(k, 9),k = 12, 13, 14 have been also deduced. Index Terms--Galois fields, linear codes, near maximum-distance separable (NMDS) codes.

Let A(n, d) denote the maximum possible number of codewords in a binary code of length n and minimum Hamming distance d. For large values of n, the best known upper bound, for fixed d, is the Johnson bound. We give a new upper bound which is at least as good as the Johnson bound for all values of n and d, and for each d there are infinitely many values of n for which the new bound is better than the Johnson bound. For small values of n and d, the best known method to obtain upper bounds on A(n, d) is linear programming. We give new inequalities for the linear programming and show that with these new inequalities some of the known bounds on A(n, d) for n [less than or equal to] 28 are improved. Index Terms--A(n, d), holes, Johnson bound, linear programming bound.

Dougherty, Gaborit, Harada, Munemasa, and Sole have previously given an upper bound on the minimum Lee weight of a Type IV self-dual [Z.sub.4]-code, using a similar bound for the minimum distance of binary doubly even self-dual codes. We improve their bound, finding that the minimum Lee weight of a Type IV self-dual [Z.sub.4]-code of length n is at most 4[??]n/12[??], except when n = 4, and n = 8 when the bound is 4, and n = 16 when the bound is 8. We prove that the extremal binary doubly even self-dual codes of length n [greater than or equal to] 24, n [not equal to] 32 are not [Z.sub.4]-linear. We classify Type IV-I codes of length 16. We prove that all Type IV codes of length 24 have minimum Lee weight 4 and minimum Hamming weight 2, and the Euclidean-optimal Type IV-I codes of this length have minimum Euclidean weight 8. Index Terms--Type IV codes over rings, self-dual codes, [Z.sub.4]-linearity.

We prove that 23, 11, and 7 do not divide the order of the automorphism group of a binary [96, 48, 20] doubly-even self-dual code. We construct 25 new inequivalent binary [96, 48, 16] doubly-even self-dual codes via an automorphism of order 23. Index Terms--Automorphisms, doubly-even self-dual codes, weight enumerators.

In this correspondence, in extension of Piret's bound for codes over phase-shift keying (PSK) signal sets, we investigate the application of the Gilbert-Varshamov (GV) bound to a variety of distance-uniform (DU) signal sets in Euclidean space. It is shown that four-dimensional signal sets matched to binary tetrahedral, binary octahedral, and binary icosahedral groups lead to better bounds compared to the bounds for signal sets matched to dicyclic groups with the same number of signal points and comparable symmetric PSK signal sets. Index Terms--Euclidean space codes, Gilbert-Varshamov (GV) bound, group codes, multilevel construction, signal sets matched to groups, uniform signal sets.

Tailbiting codes encoded by feedback convolutional encoders are studied. A condition for when tailbiting will work is given and it is described how the encoder starting state can be obtained for feedback encoders in both controller and observer canonical forms. Finally, results from a search for systematic feedback encoders that encode tailbiting codes with good decoding bit error probabilities are presented. Index Terms--Convolutional codes, systematic feedback convolutional encoders, tailbiting trellis encoders.

We describe a simple technique for the numerical calculation, within any desired degree of accuracy, of the pairwise error probability (PEP) of space-time codes. This method applies also to the calculation of E[Q([square root of [xi]])] for any nonnegative random variable [xi] whose moment-generating function [[PHI].sub.[xi]](s) = E[exp(-s[xi])] is known. Index Terms--Multiple antennas, pairwise error probability (PEP), space-time codes.

Space-time block codes for providing transmit diversity in wireless communication systems are considered. Based on the principles of linearity and unitarity, a complete classification of linear codes is given in the case when the symbol constellations are complex, and the code is based on a square matrix or restriction of such by deleting columns (antennas). Maximal rate delay optimal codes are constructed within this category. The maximal rates allowed by linearity and unitarity fall off exponentially with the number of transmit antennas. Index Terms--Clifford algebras, multiple antennas, space-time block codes, transmit diversity.

In this correspondence, the statistical approach proposed by Agrawal and Vardy to evaluate the error performance of the generalized minimum distance (GMD) decoding is extended to other reliability-based decoding algorithms for binary linear block codes, namely Chase-type, combined GMD and Chase-type, and order statistic decodings (OSDs). In all cases, tighter and simpler bounds than those previously proposed have been obtained with this approach. Index Terms--Block codes, decoding, order statistics, reliability-based decoding, soft-decision decoding.

In an earlier work, Poor and Verdu established an upper bound for the reliability function of arbitrary single-user discrete-time channels with memory. They also conjectured that their bound is tight for all coding rates. In this note, we demonstrate via a counterexample involving memoryless binary erasure channels (BECs) that the Poor-Verdu upper bound is not tight at low rates. We conclude by examining possible improvements to this bound. Index Terms--Arbitrary channels with memory, binary erasure channels (BECs), channel coding, channel reliability function, information spectrum, probability of error.

In this correspondence, we present the results of the optimization applied to the design of interleavers for rate-1/n parallel concatenated convolutional codes (PCCC) tailored to specific recursive systematic convolutional (RSC) constituent codes. The emphasis is on low-latency codes associated with interleavers of block length less than or equal to 160. The error floors of the optimized codes are significantly lower than those associated with the use of random interleavers. The distance spectra of the equivalent block codes resulting from trellis termination applied to PCCC are evaluated and used to obtain asymptotic bit error rate (BER) curves for the optimized codes. Index Terms--Interleavers, iterative algorithms, optimization, permutations, turbo codes.

The synchronization recovery property of variable-length (VL) codes has been extensively studied. In the paper, the mean error propagation length (MEPL) and the variance of error propagation length (VEPL), which are the secondary performance criteria of a VL code, are introduced to measure the synchronization recovery capability of a VL code. For the same probability distribution, there exist many different VL codes which have the same redundancy as the Huffman code but quite different MEPLs and VEPLs. To find one of the VL codes which has the minimum MEPL is a very difficult problem. We present two design algorithms for finding minimum-redundancy VL codes with short MEPL and VEPL. These two algorithms are simple and have the property that the codewords are assigned one by one. The efficiency of the algorithms are tested extensively by comparing the algorithms with known construction methods available in literature. Actually, VL codes obtained by the two algorithms outperform almost all codes available. Index Terms--Error propagation length, synchronization, variable-length codes.

Tailbiting trellis representations of linear block codes with an arbitrary sectionalization of the time axis are studied. The notations of regular and irregular tailbiting codes are introduced and their maximal state complexities are lower-bounded. The asymptotic behavior of the derived bound is investigated. Furthermore, for regular tailbiting codes the product state complexity is lower-bounded. Tables of new tailbiting trellis representations of linear block codes of rates 1/2, 1/3, and 1/4 are presented. Almost all found trellises are optimal in the sense of the new bound on the state complexity and for most codes with nonoptimal trellises there exist time-varying trellises which are optimal. Five of our newly found tailbiting codes are better than the previously known linear codes with the same parameters. Four of them are also superior to any previously known nonlinear code with the same parameters. Also, more than 40 other quasi-cyclic codes have been found that improve the parameter set of previously known quasi-cyclic codes. Index Terms--Asymptotic complexity bounds, quasi-cyclic codes, state complexity, tailbiting codes, trellis.

The problem of determining the maximum size of a ternary code is considered, under the restriction that each symbol should appear a given number of times in each codeword. Upper and lower bounds on the size of such codes under Hamming metric are discussed, where the lower bounds follow from constructions of good codes. Some of the results are obtained by explicitly finding codes by computer search. A table of exact values and best known bounds on the maximum size for codes of length at most 10 is presented. Index Terms--Constant-weight codes, nonbinary codes, weight constraints.

We generalize constructions of lexicographic codes to produce locally optimal codes with a desired trellis decoding complexity. These constructions are efficient for high-rate codes and provide a means for automated code design. As a byproduct, we improve known bounds on the parameters of lexicodes. Index Terms--Code design, lexicographic codes (lexicodes), minimal trellises, trellis decoding.

A new construction method for codes correcting multiple localized burst errors is proposed. The codes obtained by this method improve upon codes presented by Larsson in size, while keeping the encoding and decoding complexity low. Like the Larsson codes, the proposed codes are asymptotically optimal when the number of bursts to be corrected is fixed and the correctable burst length grows linearly with the codelength. Unlike the Larsson codes, the proposed codes are also asymptotically optimal when the number of bursts to be corrected and the correctable burst length are both fixed. Index Terms - Burst errors, decoding, encoding, error correction, localized errors.

Minimal vectors in linear codes arise in numerous applications, particularly, in constructing decoding algorithms and studying linear secret sharing schemes. However, properties and structure of minimal vectors have been largely unknown. We prove basic properties of minimal vectors in general linear codes. Then we characterize minimal vectors of a given weight and compute their number in several classes of codes, including the Hamming codes and second-order Reed-Muller codes. Further, we extend the concept of minimal vectors to codes over rings and compute them for several examples. Turning to applications, we introduce a general gradient-like decoding algorithm of which minimal-vectors decoding is an example. The complexity of minimal-vectors decoding for long codes is determined by the size of the set of minimal vectors. Therefore, we compute this size for long randomly chosen codes. Another example of algorithms in this class is given by zero-neighbors decoding. We discuss relations between the two decoding methods. In particular, we show that for even codes the set of zero neighbors is strictly optimal in this class of algorithm. This also implies that general asymptotic improvements of the zero-neighbors algorithm in the frame of gradient-like approach are impossible. We also discuss a link to secret-sharing schemes. Index Terms - Minimal vectors, minimum distance decoding, Reed-Muller codes, secret sharing, zero neighbors.

Abstract - A splitting (M, S) of an additive Abelian group G consists of a set of integers M and a subset S [subset] G such that every nonzero element g [Epsilon] G can be uniquely written as m [center dot] h for some m [Epsilon] M and h [Epsilon] S. Splittings by M = {[+ or -]1, ..., [+ or -]k} correspond to perfect k-shift codes used in the analysis of run-length-limited codes correcting single peak shifts. We shall determine the set S for splittings of cyclic groups [Z.sub.p], p prime, by M = {1, a, ..., [a.sup.r], b, ..., [b.sup.s]} and M = {[+ or -]1, [+ or -]a, ..., [+ or -][a.sup.r], [+ or -]b, ..., [+ or -][b.sup.s]}. This yields new conditions on the existence of perfect 3- and 4-shift codes. Further, it can be shown that splittings of [Z.sub.p] by {[+ or -]1, [+ or -]2,+3} exist exactly if [Z.sub.p] is also split by {1, 2, 3}. Index Terms - Factorization of groups, peak-shift correction, perfect codes, shift codes, shift designs, splitting of groups, tiling of Euclidean space.

We derive several new lower bounds on the size of binary codes with covering radius one. In particular, we prove K(9. 1) [greater than or equal to] 57 (the best known lower bound was 55) and K(11, 1) [greater than or equal to] 180 (178). Index Terms - Covering codes, lower bounds.

In this correspondence, we first correct a mistake in a previous paper and then present a method to compute the exact probability of information bit error as a function of truncation length K for a rate 1/2, 2 state code. Finally, we generalize the method to compute the exact bit-error probability of the above convolutional code when the information bits are transmitted in blocks. The simulation results are compared with the analytical results and good agreement is observed. Index Terms - Convolutional codes, performance analysis, Viterbi algorithm.

We provide useful results on two classes of convolutional codes: binary codes and nonbinary codes. The best codes or the best known codes for these two classes of convolutional codes are found by computer search. Some of them are better than those found in the past. We specify these codes by their transfer function matrices, distance spectra, and information-weight spectra. Furthermore, we derive an upper bound on the free distances of binary-to-M-ary codes and q-ary-to-M-ary codes. Numerical values of this bound closely fit the computer-searched values. Index Terms - Codes, convolutional codes, distance spectra, information-weight spectra, linear codes.

In this correspondence we are concerned with the error rates contributed by component codes in a multilevel code, decoded by a multistage decoder. These error rates are required for estimating the performance of the structure, but more importantly, they can serve as a design tool for achieving high coding gain. The latter objective can be reached by approaching a balance among these error rates. For evaluating the error rate contributed by a component code, it is essential to calculate the corresponding spectrum of Euclidean distances. A method for computing this spectrum is developed in this correspondence. The method is general and applicable to any signal constellation, and convolutional as well as block component codes. The error coefficient, available in the literature for some multilevel codes with an infinite size signal constellation, is shown to be significantly different from that of a practical finite constellation. Note that the complete spectrum is essential when codewords (of a component code) with Hamming distance beyond the minimum distance affect the error rate (see, e.g., Turbo codes). Index Terms - Multilevel coding, multistage decoding, spectrum of Euclidean distances.

All extremal binary self-dual codes of lengths 42 and 44 which have an automorphism of order 5 with eight independent cycles are obtained up to equivalence. There are 109 inequivalent [42, 21, 8] codes with such an automorphism. All [44, 22, 8] codes that are obtained have 29 different weight enumerators. Index Terms - Automorphisms, self-dual codes.

Codes with decomposable structure allow the use of multistage decoding procedures to achieve suboptimum bounded-distance error performance with reduced decoding complexity. This correspondence presents some new decomposable codes, including a class of distance-8 codes, that are constructed based on the [absolute value of a + x] [absolute value of b + x] [absolute value of a + b + x] construction method. Some existing best codes are shown to be decomposable and hence can be decoded with multistage decoding. Index Terms - Block codes, decomposable codes, multistage decoding, trellis codes.

Let S be a constrained system of finite type, described in terms of a labeled graph M of finite type. Furthermore, let C be an irreducible constrained system of finite type, consisting of the collection of possible code sequences of some finite-state-encodable, sliding-block-decodable modulation code for S. It is known that this code could then be obtained by state splitting, using a suitable approximate eigenvector. ln this correspondence, we show that the collection of all approximate eigenvectors that could be used in such a construction of C contains a unique minimal element. Moreover, we show how to construct its linear span from knowledge of M and C only, thus providing a lower bound on the components of such vectors. For illustration we discuss an example showing that sometimes arbitrary large approximate eigenvectors are required to obtain the best code (in terms of decoding-window size) although a small vector is also available. Index Terms - Approximate eigenvector, constrained systems, sliding-block decodable, state splitting.

This correspondence presents a hybrid reliability-based decoding algorithm which combines the reprocessing method based on the most reliable basis and a generalized Chase-type algebraic decoder based on the least reliable positions. It is shown that reprocessing with a simple additional algebraic decoding effort achieves significant coding gain. For long codes, the order of reprocessing required to achieve asymptotic optimum error performance is reduced by approximately 1/3. This significantly reduces the computational complexity, especially for long codes. Also, a more efficient criterion for stopping the decoding process is derived based on the knowledge of the algebraic decoding solution. Index Terms - Block codes, maximum-likelihood decoding, ordered statistics, reliability information, soft-decision decoding.

We describe an alternative mechanism for approximate binary arithmetic coding. The quantity that is approximated is the ratio between the probabilities of the two symbols. Analysis is given to show that the inefficiency so introduced is less than 0.7% on average; and in practice the compression loss is negligible. Index Terms - Approximate arithmetic coding, bilevel coding, binary arithmetic coding, data compression.

Let [n, k, d: q]-codes be linear codes of length n, dimension k and minimum Hamming distance d over GF(q). The following quasi-cyclic codes are constructed in this paper: [44, 11, 20; 3], [55, 11, 26; 3], [66, 11, 32; 3], [48, 12, 21; 3], [60, 12, 28; 3], [56, 13, 24; 3], [65, 13, 29; 3], [56, 14, 23; 3], [60, 15, 23; 3], [64, 16, 25; 3], [36, 9, 19; 4], [90, 9, 55; 4], [99, 9, 61; 4], [30, 10, 14; 4], [50, 10, 27; 4], [55, 10, 30; 4], [33, 11, 15; 4], [55, 11, 29; 4], [36, 12, 16; 4], [48, 12, 23; 4], [60, 12, 31; 4] All of these codes have established or exceed the respective lower bounds on the minimum distance given by Brouwer. Index Terms - Quasi-cyclic codes, ternary and quaternary linear codes.

Constructions of nonlinear covering codes are given. Using any nonlinear starting code of covering radius R [greater than or equal to] 2 these constructions form an infinite family of codes with the same covering radius. A nonlinear code is treated as a union of cosets of a linear code. New infinite families of nonlinear covering codes are obtained. Concepts of R, I-objects, R, l-partitions, and R, l-length are described for nonlinear codes. Index Terms - Binary codes, covering codes, covering radius, nonbinary codes, nonlinear codes.

In this correspondence, new ternary codes of dimension 6 are presented which improve the bounds on optimal linear codes. These codes belong to the class of quasi-twisted (QT) codes, and have been constructed using a greedy algorithm. This work extends previous results on QT codes of dimension 6. In particular, several new two-weight QT codes are presented. Numerous new optimal codes which meet the Griesmer bound are given, as well as others which establish lower bounds on the maximum minimum distance. Index Terms - Optimal ternary linear codes, quasi-twisted codes.

New constant weight codes are found by considering certain linear permutation groups. A code is obtained as a collection of orbits of words under such a group. This leads to a difficult optimization problem, where a stochastic search heuristic, tabu search, is used to find good solutions in a feasible amount of time. Nearly 40 new codes of length at most 28 are presented. Index Terms - Combinatorial optimization, constant weight codes, permutation groups, tabu search.

We prove that, up to equivalence, there is a unique extremal quaternary Hermitian self-dual code of length 18, and that there are two inequivalent extremal quaternary Hermitian self-dual codes of length 20. Index Terms - Extremal codes, Hermitian self-dual codes, quaternary codes.

The techniques of algebraic geometry have been widely and successfully applied to the study of linear codes over finite fields since the early 1980's. Recently, there has been an increased interest in the study of linear codes over finite rings. In a previous paper, we combined these two approaches to coding theory by introducing and studying algebraic-geometric codes over rings. In this correspondence, we show that the Nordstrom-Robinson code is the image under the Gray mapping of an algebraic geometric code over Z/4Z. Index Terms - Algebraic geometry, codes, Nordstrom-Robinson code.