The main concern of this article is to find linear codes which will correct a set of arbitrary error patterns. Although linear codes which have been designed for correcting random error patterns and burst error patterns can be used, we would like to find codes which will correct a specified set of error patterns with the fewest possible redundant bits. Here, to reduce the complexity involved in finding the code with the smallest redundancy which can correct a specified set of error patterns, algebraic codes whose parity check matrix exhibits a particular structure are considered. If the number of redundant bits is T, the columns of the parity check matrix must be increasing powers of a field element in GF(2/sup T/). Given a set of error patterns to be corrected, computations to determine the code rates possible for these type of codes and hence the redundancy for different codeword lengths are presented. Results for various sets of error patterns suggest that the redundancy of these algebraic codes is close to the minimum redundancy possible for the set of error patterns specified and for any codeword length.>

In this paper we construct a new family of nonlinear binary signal sets which achieve Welch's lower bound on simultaneous cross correlation and autocorrelation magnitudes. Given a parameternwithn=0 \pmod{4}, the period of the sequences is2^{n}-1, the number of sequences in the set is2^{n/2}, and the cross/auto correlation function has three values with magnitudes\leq 2^{n/2}+1. The equivalent linear span of the codes is bound above by\sum_{i=1}^{n/4}\left(\stackrel{n}{i} \right). These new signal sets have the same size and correlation properties as the small set of Kasami codes, but they have important advantages for use in spread spectrum multiple access communications systems. First, the sequences are "balances," which represents only a slight advantage. Second, the sequence generators are easy to randomly initialize into any assigned code and hence can be rapidly "hopped" from sequence to sequence for code division multiple access operation. Most importantly, the codes are nonlinear in that the order of the linear difference equation satisfied by the sequence can be orders of magnitude larger than the number of memory elements in the generator that produced it. This high equivalent linear span assures that the code sequence cannot be readily analyzed by a sophisticated enemy and then used to neutralize the advantages of the spread spectrum processing.

Burst-error channels have been used to model a large class of modern communication media, and the problem of communicating reliably through such media has received much study [1]-[9]. Existing techniques include two-way communication schemes that involve error detection and retransmission, and schemes that utilize error correcting codes in code interleaving. The error-detection and retransmission scheme is simple, but its applicability has been restricted to limited environments. On the other hand, the concept of code interleaving has proved to be versatile and effective. Code interleaving distributes the error detection and correction burden among the component codes and thus lowers the overall redundancy requirement. However, the memory characteristics of the burst-error channel have not been used. This omission has prompted the investigation presented in this paper to utilize the inherent information embedded in the code interleaving scheme when used with burst-error channels. The concept of erasure decoding is introduced, leading to some useful coding and decoding strategies. Theoretical formulations are devised to predict code performance, and their validity is verified with computer simulations.

Theorems are presented concerning the optimality of rational approximations using non-Archimedean norms. The algorithm for developing the rational approximations is based on continued fraction techniques and is virtually equivalent to an algorithm employed by Berlekamp for decoding BCH codes. Several variations of the continued fraction technique and Berlekamp's algorithm are illustrated on a common example.

It is shown that Reed-Solomon (RS) codes can be decoded by using a fast Fourier transform (FFT) algorithm over finite fieldsGF(F_{n}), whereF_{n}is a Fermat prime, and continued fractions. This new transform decoding method is simpler than the standard method for RS codes. The computing time of this new decoding algorithm in software can be faster than the standard decoding method for RS codes.

It is shown that\sqrt\[8]{2}is an element of order2^{n+4}inGF(F_{n}), whereF_{n}=2^{2^{n}}+1is a Fermat prime forn=3,4. Hence it can be used to define a fast Fourier transform (FFT) of as many as2^{n+4}symbols inGF(F_{n}). Since\sqrt[8]{2}is a root of unity of order2^{n+4}inGF(F_{n}), this transform requires fewer muitiplications than the conventional FFT algorithm. Moreover, as Justesen points out [1], such an FFT can be used to decode certain Reed-Solomon codes. An example of such a transform decoder for the casen=2, where\sqrt{2}is inGF(F_{2})=GF(17), is given.

The structure of the group of integers relatively prime tonunder multiplication modulonis reviewed, and the basic properties of characters defined on that group is developed. Appropriately chosen subcollections of the characters when viewed as periodic sequences are then shown to have relatively ideal autocorrelation and cross correlation properties. The results of a computer study indicate that the same subcollections when viewed as finite length sequences also have very good aperiodic autocorrelation and cross correlation properties.

With the Delsarte-MacWilliams inequalities as a starting point, an upper bound is obtained on the rate of a binary code as a function of its minimum distance. This upper bound is asymptotically less than Levenshtein's bound, and so also Elias's.

Encoding and decoding algorithms for Reed-Solomon codes based on Fourier-like transforms on finite field and finite rings are discussed. Classes of codes are proposed for two different types of multiple-user communication systems: a multichannel communication system and a multiaccess communication system. For the first system, a fast decoding algorithm is developed that uses transforms on a finite ring which is isomorphic to a direct sum of Galois fields. For the second system, an efficient (in terms of information rate) coding scheme is proposed which utilizes a direct sum of Galois fields.

A new unitary transform called the slant transform, specifically designed for image coding, has been developed. The transformation possesses a discrete sawtoothlike basis vector which efficiently represents linear brightness variations along an image line. A fast computational algorithm has been found for the transformation. The slant transformation has been utilized in several transform image-coding systems for monochrome and color images. Computer simulation results indicate that good quality coding can be accomplished with about 1 to 2 bits/pixel for monochrome images and 2 to 3 bits/pixel for color images.

Some communication systems require sets of signals with impulse-like autocorrelation functions and small cross correlation. There is considerable literature on signals with impulse-like autocorrelation functions hut little on sets of signals with small cross correlation. A possible reason is that designers put too severe a restriction on cross correlation magnitudes. This correspondence establishes lower bounds on how small the cross correlation and autocorrelation can simultaneously be.

An upper bound on the minimum distance of binary blocks codes, which is superior to Elias' bound for R < 0.0509^+, is obtained. The new bound has the same derivative(-infty) at R = 0 as Gilbert's lower bound. (Elias' bound has derivative-ln 2 at R = 0).

In this paper we present the weight distribution of all2^26cosets of the (32,6) first-order Reed-Muller code. The code is invariant under the complete affine group, of order32 \times 31 \times 30 \times 28 \times 24 \times16. In the Appendix we show (by hand computations) that this group partitions the2^26cosets into only 48 equivalence classes, and we obtain the number of cosets in each class. A simple computer program then enumerated the weights of the 32 vectors ih each of the 48 cosets. These coset enumerations also answer this equivalent problem: how well are the2^32Boolean functions of five variables approximated by the2^5linear functions and their complements?

Bounded synchronization delay codes have the property that no proper cyclic rearrangement of the letters of a codeword is another codeword. Because of this property research in code design has centered on criteria for selecting one word from each nonperiodic cyclic equivalence class to satisfy various additional constraints. This is all that is necessary when it is feasible for the encoder and decoder to use table look-up procedures. However, even for moderate word length, the dictionary size can be quite large and prove a major obstacle in practical applications. This paper describes a systematic procedure for mapping data sequences into nonperiodic cyclic equivalence classes and for performing the inverse mapping. The scheme is arithmetic in nature and does not require large tables.