Receivers for wireless local area networks based on the IEEE 802.11b standard are required to operate well in heavy multipath, as well as additive noise impairments. This paper discusses a practical approach to combined equalizing and decoding for IEEE 802.11b systems, based on the Fano sequential decoding algorithm. Simulation results are presented demonstrating the greatly improved performance attained using this algorithm to the performance obtained using separate equalization and decoding blocks. This method has been implemented in TI's ACX100 chip. Measured laboratory results are presented that demonstrate superior throughput results obtained from this device compared with throughputs obtained by competitive devices available on the market.

This paper describes a method for packet synchronization and error detection for use in a synchronous digital communications system. The method relies upon a class of linear block codes that have parity checks that are expressed in terms of a finite-impulse response (FIR) filter. This system is incorporated in the newly established ITU standard of digital cable television standard, J.83 appendix B, which is based on an MPEG 2 transport packet data stream. This technique is also the basis for cable modem downstream transmission defined in the IEEE 802.14 and MCNS standards. The parity check structure is based on a pseudonoise sequence generated by a (binary) primitive polynomial. This structure allows for a computationally efficient implementation of the parity check FIR filter, in a recursive manner, that is none the less self-synchronizing. The FIR parity check codes that are described are characterized as the dual of a CRC-type, shortened cyclic code. The theory and computational structure of these codes are presented here; the J.83R code is used as an example of the general theory.

The theory of error-correcting codes derived from curves in an algebraic geometry was initiated by the work of Goppa as generalizations of Bose-Chaudhuri-Hocquenghem (BCH), Reed-Solomon (RS), and Goppa codes. The development of the theory has received intense consideration since that time and the purpose of the paper is to review this work. Elements of the theory of algebraic curves, at a level sufficient to understand the code constructions and decoding algorithms, are introduced. Code constructions from particular classes of curves, including the Klein quartic, elliptic, and hyperelliptic curves, and Hermitian curves, are presented. Decoding algorithms for these classes of codes, and others, are considered. The construction of classes of asymptotically good codes using modular curves is also discussed.

Any linear code with a nontrivial automorphism has the structure of a module over a polynomial ring. The theory of Grobner bases for modules gives a compact description and implementation of a systematic encoder. We present examples of algebraic-geometric Goppa codes that can be encoded by these methods, including the one-point Hermitian codes.

In this paper, trellis group codes are introduced as an extension of Slepian group codes to codes over sequence spaces. A trellis group code is defined over R/sup n/ as the orbit of a bi-infinite "seed sequence", x/sub 0//spl isin/(R/sup n/)/sup Z/, under an infinite, defining group of transformations. This group of transformations is generated by a symbolic system. The theory is developed by combining a nontrivial extension of the notion of an isometric labeling, with results from the theory of symbolic dynamics over groups. New results presented here include a useful characterization of uniform partitions and a symbolic dynamic classification of trellis group codes. The theory is used to develop a class of rotationally invariant, nonabelian trellis group codes for QAM modulation. It is also shown that the 8-state, rotationally invariant trellis code designed by Wei (1984), used in the V.32 (and V.32 bis) international modem standard, belongs to this class.>

It is proved that any algebraic-geometric (AG) code can be expressed as a cross section of an extended multidimensional cyclic code. Both AG codes and multidimensional cyclic codes are described by a unified theory of linear block codes defined over point sets: AG codes are defined over the points of an algebraic curve, and an m-dimensional cyclic code is defined over the points in m-dimensional space. The power of the unified theory is in its description of decoding techniques using Grobner bases. In order to fit an AG code into this theory, a change of coordinates must be applied to the curve over which the code is defined so that the curve is in special position. For curves in special position, all computations can be performed with polynomials and this also makes it possible to use the theory of Grobner bases. Next, a transform is defined for AG codes which generalizes the discrete Fourier transform. The transform is also related to a Grobner basis, and is useful in setting up the decoding problem. In the decoding problem, a key step is finding a Grobner basis for an error locator ideal. For AG codes, multidimensional cyclic codes, and indeed, any cross section of an extended multidimensional cyclic code, Sakata's algorithm can be used to find linear recursion relations which hold on the syndrome array. In this general context, the authors give a self-contained and simplified presentation of Sakata's algorithm, and present a general framework for decoding algorithms for this family of codes, in which the use of Sakata's algorithm is supplemented by a procedure for extending the syndrome array.

A new adaptive algorithm for lossless compression of digital audio is presented. The algorithm is derived from ideas from both dictionary coding and source-modeling. An adaptive Lempel-Ziv (1977) style fixed dictionary coder is used to build a source model that fuels an arithmetic coder. As a result, variable length strings drawn from the source alphabet are mapped onto variable length strings that are on average shorter. The authors show that this algorithm outperforms arithmetic coding or Lempel-Ziv coding working alone on the same source (in their experiments the source is an ADPCM quantizer). Adaptation heuristics for the Lempel-Ziv coder, relevant data structures, and a discussion of audio source modeling (entropy estimation) experiments are described. While the algorithm presented herein is designed to be used as a post-compressor in a lossy audio transform coding system, it is well suited for any instance where non-stationary source outputs must be compressed.>

It is demonstrated how modulation schemes based on QPSK can be directly incorporated into QAM-based systems. It is argued that this leads directly to an easily implementable structure that is both efficient in bandwidth and data reliability. It is contended that the correct solution to the concatenated coding problem for HDTV transmission is to simply extend the modulation codes developed for QPSK-to-QAM modulation. In nonconcatenated situations, a trellis code based on a binary code at rate 2/3 is usually best. However, this is not the case for higher error rates at the output of the trellis decoder (e.g., when a symbol error correcting decoder follows as a concatenated code). The reason for this follows from an analysis of the effect of the number of nearest neighbors on the error rate. A four-way partition of QAM is a natural extension of QPSK modulation; it is a simple matter to incorporate any good QPSK code into a trellis coding scheme for QAM modulation. A concatenated coding scheme based on QPSK trellis codes and symbol error correcting coding is proposed. An example is presented to show the advantages of this approach.>

Real-time algorithms for the compression of high-fidelity audio are under study. The goal of these algorithms is to provide a compact digital representation for an input stream of audio sample. A subband coding system that performs this is presented. This modular system combines a wavelet-based signal transformation block with adaptive quantization and lossless compression blocks. The design of the signal transformation block is examined. Designs are presented for filter structures that generate fractional octave and geometric subband partitionings of the input frequency band. In particular, designs for 1/2-octave, 1/3-octave and some geometric band partitionings are presented.>

The authors consider the problem of bounding the information capacity of saturation recording. The superposition channel with additive Gaussian noise is used as a model for recording. This model says that for a saturation input signal, x(t) (i.e., one that can assume only one of two levels), the output can be expressed as y(t)=x(t)+z(t) where x(t) is a filtered version of the input x(t) and z(t) is additive Gaussian noise. The channel is described by the impulse response of the channel filter, h(t), and by the autocorrelation function of the noise. A specific example of such a channel is the differentiated Lorentz channel. Certain autocorrelation and spectrum expressions for a general Lorentz channel are derived. Upper and lower bounds on the capacity of saturation recording channels are described. The bounds are explicitly computed for the differentiated Lorentz channel model. Finally, it is indicated how the derived bounds can be applied in practice using physical measurements from a recording channel.>

The authors present a study of run-length-limiting codes that have a null at zero frequency or DC. The class of codes or sequences considered is specified by three parameters: (d, k, c). The first two constraints, d and k, put lower and upper bounds on the run-lengths, while the charge constraint, c, is responsible for the spectral null. A description of the combined (d, k, c) constraints, in terms of a variable length graph, and its adjacency matrix, A(D), are presented. The maximum entropy description of the constraint described by a run-length graph is presented as well as the power spectral density. The results are used to study several examples of (d, k, c) constraints. The eigenvalues and eigenvectors of the classes of (d, k=2c-1, c) and (d, k=d+1, c) constraints for (c=1,2,. . .), are shown to satisfy certain second-order recursive equations. These equations are solved using the theory of Chebyshev polynomials.>

The authors consider the model for runlength coded systems of P.H. Siegel (1982) that is based on peak or edge detection. The model does not attempt to account for failures of the qualifying circuit; it is assumed that every transition is successfully declared (i.e., no missing or false qualifiers). In this model it is the error in the estimate of the location of the transition that introduces uncertainty at the channel output. The model is motivated by the problem of pulse location in white Gaussian noise. Through a series of lemmas and theorems, bounds on the capacity of this model are obtained. These bounds are evaluated and used to suggest that improvements in storage capacity are possible through the use of codes with designed noise tolerance.>

A new class of constrained systems average runlength constraints (ARCs), is defined by requiring that the sum of n consecutive run lengths be bounded above by a linear function of n. In particular, the running average runlength of every sequence in the system is bounded above by a constant. A general result is given on the capacity of ARC systems. The state splitting algorithm is then improved for variable-length graphs. This is then applied to obtain high, fixed-rate codes from the free binary source to ARC systems. As an example, a rate 1/2, (d,k)=

Consider a channel with inputs and outputs in the field F/sub q/(q>2). It is said that the channel is skewed on a set B contained in/implied by F/sub q/* if the additive noise generated by the channel is likely to lie in B, i.e. B is a set of common errors. The concern is the construction of focused codes that are appropriate for such channels. It is said that a code is (t/sub 1/,t/sub 2/)-focused on B if it can correct up to t/sub 1/+t/sub 2/ errors provided at most t/sub 1/ of those errors lie outside of B; the strategy is to offer different levels of protection against common and uncommon errors and so provide novel tradeoffs between performance and rate. Techniques for constructing focused codes and bounds on their rates are described.>

The authors delayed-decision-feedback sequence estimation (DDFSE) for uncoded PAM signals is considered. Estimates on the performance of the algorithm are given, and simulation results are provided for several examples. A more general form of DDFSE applicable to coded modulation systems is also presented. As an example, detection of trellis-coded QPSK (quadrature phase-shift keyed) signals over intersymbol interference channels is discussed.>

A novel method is developed for computing formulas for power spectra associated with run-length-limited (RLL) codes. Explicit use is made of a compact description of the run-length process associated with the RLL code. This association simplifies the general derivation of the power spectrum. The calculation of the spectra of several RLL codes popular in data storage applications is presented. Some of the closed-form expressions for the spectra of these widely used codes are new.>

A class of convolutional codes called cross parity check (CPC) codes, which are useful for the protection of data stored on magnetic tape, is described and analyzed. CPC codes are first explained geometrically; their construction is described in terms of constraining data written onto a tape in such a way that when lines of varying slope are drawn across the tape, the bits falling on those lines sum to zero modulo two. This geometric interpretation is then formalized by the construction of canonical parity check matrices and systematic generator matrices for CPC codes and by computing their constraint lengths. The distance properties of CPC codes are analyzed, and it is shown that these codes are maximum distance separable convolutional codes. In addition, examples are given of both error and erasure decoding algorithms that take advantage of the geometric regularity of CPC codes. The technique of parity check matrix reduction, which is useful for reducing the inherent decoding delay of CPC codes, is described. The technique consists of dividing each term of the parity check matrix by some polynomial and retaining only the remainder. A class of polynomials that are particularly attractive for this purpose if identified.>

Linear sum codes (LSCs) form a class of error control codes designed to provide on-chip error correction to semiconductor random access memories (RAMs). They use the natural addressing scheme found on RAMs to form and access codewords with a minimum of overhead. The authors formally define linear sum codes and examine some of their characteristics. Specifically, they examine their minimum distance characteristics, their error correcting capabilities, and the complexity involved in their implementation. In addition, detailed consideration is given to an easily implemented class of single-, double-, and triple-error correcting LSCs.>

We describe and analyze row/column replacement, the technique currently used to control hard cell defects in semiconductor RAM's during manufacture. This strategy is shown to be asymptotically ineffective; it is demonstrated that this ineffectiveness may become a limiting issue for very large memory arrays.

Calderbank, Heegard, and Ozarow [1] have suggested a method of designing codes for channels with intersymbol interference, such as the magnetic recording channel. These codes are designed to exploit intersymbol interference. The standard method is to minimize intersymbol interference by constraining the input to the channel using run-length limited sequences. Calderbank, Heegard, and Ozarow considered an idealized model of an intersymbol interference channel that leads to the problem of designing codes for a partial response channel with transfer function(1 - D^{N}) /2, where the channel inputs are constrained to be\pm 1. This problem is considered here. Channel inputs are generated using a nontrivial coset of a binary convolutional code. The coset is chosen to limit the zero-run length of the output of the channel and so maintain clock synchronization. The minimum squared Euclidean distance between outputs corresponding to distinct inputs is bounded below by the free distance of a second convolutional code which we call the magnitude code. An interesting feature of the analysis is that magnitude codes that are catastrophic may perform better than those that are noncatastrophic.

Many forms of digital memory have been developed for the permanent storage of information. These include keypunch cards, paper tapes, PROMs, photographic film and, more recently, digital optical disks. All these "write-once" memories have the property that once a "one" is written in a particular cell, this cell becomes irreversibly set at one. Thus, the ability to rewrite information in the memory is hampered by the existence of previously written ones. The problem of storing temporary data in permanent memory is examined here. Consider storing a sequence oftmessagesW_{1}, W_{2}, \cdots , W_{t}in such a device. Let each messageW_{i}consist ofk_{i}bits and let the memory contain n cells. We say that a ratet-tuple(R_{1} = k_{1} / n, R_{2} = k_{2} / n, \cdots , R_{t} = k_{t} / n)is achievable if we can store a sequence of messages at these rates for somen. The capacityC_{t}^{\ast} \subset R_{+}^{t}is the closure of the set of achievable rates. The capacityC_{t}^{\ast}for an optical disk-type memory is determined. This result is related to the work of Rivest and Shamir. A more general model for permanent memory is introduced. This model allows for the possibility of random disturbances (noise), larger input and output alphabets, more possible cell states, and a more flexible set of state transitions. An inner bound on the capacity regionC_{t}^{\ast}for this model is presented. It is shown that this bound describesC_{t}^{\ast}in several instances.

The problem is considered of encoding a discrete memoryless source when correlated side information may or may not be available to the decoder. It is assumed that the side information is not available to the encoder. The rate-distortion functionR (D_{l}, D_{2})is determined whereD_{1}is the distortion achieved with side information andD_{2}is the distortion achieved without it. A generalization is made to the case ofmdecoders, each of which is privy to its own side information. An appropriately definedD-admissible rate for this general case is shown to equalR(D)when the side information sources satisfy a specified degradedness condition. Explicit results are obtained in the quadratic Gaussian case and in the binary Hamming case.

An original adaptive, infinite-impulse-response (IIR) feedback, line-enhancer structure is proposed as an adaptive differential pulse code modulation (ADPCM) algorithm. The underlying parameter estimation problem is formulated and a minor variation on the recursive maximum likelihood (RML) algorithm is suggested. Simulated tests measuring SNR improvement provide preliminary support of the feasibility of such a scheme.

Linear block codes are studied for improving the reliability of message storage in computer memory with stuck-at defects and noise. The case when the side information about the state of the defects is available to the decoder or to the encoder is considered. In the former case, stuck-at cells act as erasures so that techniques for decoding linear block codes for erasures and errors can be directly applied. We concentrate on the complimentary problem of incorporating stuck-at information in the encoding of linear block codes. An algebraic model for stuck-at defects and additive errors is presented. The notion of a "partitioned" linear block code is introduced to mask defects known at the encoder and to correct random errors at the decoder. The defect and error correction capability of partitioned linear block codes is characterized in terms of minimum distances. A class of partitioned cyclic codes is introduced. A BCH-type bound for these cyclic codes is derived and employed to construct partitioned linear block codes with specified bounds on the minimum distances. Finally, a probabilistic model for the generation of stuck-at cells is presented. It is shown that partitioned linear block codes achieve the Shannon capacity for a computer memory with symmetric defects and errors.

A computer memory with defects is modeled as a discrete memoryless channel with states that are statistically determined. The storage capacity is found when complete defect information is given to the encoder or to the decoder, and when the defect information is given completely to the decoder but only partially to the encoder. Achievable storage rates are established when partial defect information is provided at varying rates to both the encoder and the decoder. Arimoto-Blahut type algorithms are used to compute the storage capacity.

This paper describes a microprocessor-based modem developed for use in a packet switching network over satellite channels. This digital modem can process both BPSK and QPSK packets with near optimum error rate performance over channels with marginal signal energy-to-noise density ratio. Of principal concern is the development of the discrete time algorithms which form the basis of the microinstruction program. The processing of a packet can be decomposed into two basic stages: (1) the detection of the packet preamble and the rapid estimation of signal parameters (symbol timing and carrier frequency offset) for the specific packet, and (2) the demodulation of the data portion of the packet including the tracking of both symbol timing and carrier offset phase, phase ambiguity resolution and data symbol estimation. The paper concludes with details on the performance of the modem under operational conditions and a brief discussion of implementation of the processor.

A deterministic coding scheme for reliable transmission over the Gaussian broadcast channel with two receivers is considered. The coding scheme is based upon Slepian's permutation mudulation codes. It is shown that it is relatively easy for both receivers to accomplish maximum likelihood detection even though one receiver must instrument a composite hypothesis test. Bounds on the performance of various codes are given. The parameters of the codes are chosen in order to achieve the best performance. The performance of these best codes are compared with results predicted by random coding and with time sharing of ordinary permutation codes.