We consider a new formulation of a class of synchronization error channels and derive analytical bounds and numerical estimates for the capacity of these channels. For the binary channel with only deletions, we obtain an expression for the symmetric information rate in terms of subsequence weights, which reduces to a tight lower bound for small deletion probabilities. We are also able to exactly characterize the Markov-1 rate for the binary channel with only replications. For a channel that introduces deletions as well as replications of input symbols, we design approximating channels that parameterize the state space and show that the information rates of these approximate channels approach that of the deletion-replication channel as the state space grows. For the case of the channel where deletions and replications occur with the same probabilities, a stronger result in the convergence of mutual information rates is shown. The numerous advantages this new formulation presents are explored.

Flash memory is a nonvolatile computer memory comprising blocks of cells, wherein each cell can take on$q$different values or levels. While increasing the cell level is easy, reducing the level of a cell can be accomplished only by erasing an entire block. Since block erasures are highly undesirable, coding schemes—known as floating codes (or flash codes) and buffer codes—have been designed in order to maximize the number of times that information stored in a flash memory can be written (and rewritten) prior to incurring a block erasure. An$(n,k,t)_{q}$flash code$\BBC$is a coding scheme for storing$k$information bits in$n$cells in such a way that any sequence of up to$t$writes can be accommodated without a block erasure. The total number of available level transitions in$n$cells is$n(q{-}1)$, and the write deficiency of$\BBC$, defined as$\delta (\BBC)=n(q{-}1)-t$, is a measure of how close the code comes to perfectly utilizing all these transitions. In this paper, we show a construction of flash codes with write deficiency$O(qk\log k)$if$q\geqslant\log_{2}k$, and at most$O(k\log^{2}k)$otherwise. An$(n,r,\ell,t)_{q}$buffer code is a coding scheme for storing a buffer of$r~\ell$-ary symbols such that for any sequence of$t$symbols, it is possible to successfully decode the last$r$symbols that were written. We improve upon a previous upper bound on the maximum number of writes$t$in the case where there is a single cell to store the buffer. Then, we show how to improve a construction by Jiangthat uses multiple cells, where$n\geqslant 2r$.

Spatially coupled codes have been of interest recently owing to their superior performance over memoryless binary-input channels. The performance is good both asymptotically, since the belief propagation thresholds approach the Shannon limit, as well as for finite lengths, since degree-2 variable nodes that result in high error floors can be completely avoided. However, to realize the promised good performance, one needs large blocklengths. This in turn implies a large latency and decoding complexity. For the memoryless binary erasure channel, we consider the decoding of spatially coupled codes through a windowed decoder that aims to retain many of the attractive features of belief propagation, while trying to reduce complexity further. We characterize the performance of this scheme by defining thresholds on channel erasure rates that guarantee a target erasure rate. We give analytical lower bounds on these thresholds and show that the performance approaches that of belief propagation exponentially fast in the window size. We give numerical results including the thresholds computed using density evolution and the erasure rate curves for finite-length spatially coupled codes.

We consider a windowed decoding scheme for LDPC convolutional codes that is based on the belief-propagation (BP) algorithm. We discuss the advantages of this decoding scheme and identify certain characteristics of LDPC convolutional code ensembles that exhibit good performance with the windowed decoder. We will consider the performance of these ensembles and codes over erasure channels with and without memory. We show that the structure of LDPC convolutional code ensembles is suitable to obtain performance close to the theoretical limits over the memoryless erasure channel, both for the BP decoder and windowed decoding. However, the same structure imposes limitations on the performance over erasure channels with memory.

A write-once memory (WOM) is a storage device that consists of cells that can take on$q$values, with the added constraint that rewrites can only increase a cell's value. A length-$n$,$t$-write WOM-code is a coding scheme that allows$t$messages to be stored in$n$cells. If on the$i$th write we write one of$M_{i}$messages, then the rate of this write is the ratio of the number of written bits to the total number of cells, i.e.,$\log_{2}M_{i}/n$. The sum-rate of the WOM-code is the sum of all individual rates on all writes. A WOM-code is called a fixed-rate WOM-code if the rates on all writes are the same, and otherwise, it is called a variable-rate WOM-code. We address two different problems when analyzing the sum-rate of WOM-codes. In the first one, called the fixed-rate WOM-code problem, the sum-rate is analyzed over all fixed-rate WOM-codes, and in the second problem, called the unrestricted-rate WOM-code problem, the sum-rate is analyzed over all fixed-rate and variable-rate WOM-codes. In this paper, we first present a family of two-write WOM-codes. The construction is inspired by the coset coding scheme, which was used to construct multiple-write WOM-codes by Cohenand recently by Wu, in order to construct from each linear code a two-write WOM-code. This construction improves the best known sum-rates for the fixed- and unrestricted-rate WOM-code problems. We also show how to take advantage of two-write WOM-codes in order to construct codes for the Blackwell channel. The two-write construction is generalized for two-write WOM-codes with$q$levels per cell, which is used with ternary cells to construct three- and four-write binary WOM-codes. This construction is used recursively in order to generate a family of$t$-write WOM-codes for all$t$. A further generalization of these$t$-write WOM-codes yields additional families of efficient WOM-codes. Finally, we show a recursive method that uses the previously constructed WOM-codes in order to construct fixed-rate WOM-codes. We conclude and show that the WOM-codes constructed here outperform all previously known WOM-codes for$2\leqslant t\leqslant 10$for both the fixed- and unrestricted-rate WOM-code problems.

A Write Once Memory (WOM) is a storage medium with binary memory elements, called cells, that can change from the zero state to the one state only once. Examples of WOMs include punch cards and optical disks. WOM-codes, introduced by Rivest and Shamir, permit the reuse of a WOM by taking into account the location of cells that have already been changed to the one state. The objective in designing WOM-codes is to use the fewest number of cells to store a specified number of information bits in each of several reuses of the memory. An [n,k,t] WOM-code C is a coding scheme for storing k information bits in n cells t times. At each write, the state of each cell can be changed, provided that the cell is changed from the zero state to the one state. The rate of C, defined by R(C) = kt/n, indicates the total amount of information that is possible to store in a cell in t writes. Two WOM-code constructions correcting a single cell-error were presented by Zemor and Cohen. In this paper, we present another construction of a single-error-correcting WOM-code with a better rate. Our construction can be adapted also for single-error-detection, double-error-correction, and triple-error-correction. For the last case, we use triple-error-correcting BCH-like codes, which were presented by Kasami and more recently described again by Bracken and Helleseth. Finally, we show two constructions that can be combined for the correction of an arbitrary number of errors.

We study windowed decoding of spatially coupled codes when the transmission occurs over the binary erasure channel. We characterize the performance of this scheme by defining thresholds on channel erasure rates that guarantee a target bit erasure rate. We give analytical lower bounds on these thresholds and show that the performance approaches that of belief propagation exponentially fast in the window size. We give numerical results including the thresholds computed using density evolution and the erasure rate curves for finite-length spatially coupled codes.

We propose a new channel model for channels with synchronization errors. Using this model, we give simple, non-trivial and, in some cases, tight lower bounds on the capacity for certain synchronization error channels.

In multi-level flash memories, the dominant cell errors are asymmetric with limited-magnitude. With such an error model in mind, Cassuto et al. recently developed bounds and constructions for codes correcting t asymmetric errors with magnitude no more than ℓ. However, a more refined model of these memory devices reflects the fact that typically only a small number of errors have large magnitude while the remainder are of smaller magnitude. In this work, we study such an error model, in which at most t1errors of maximum magnitude ℓ1and at most t2errors of maximum magnitude ℓ2, with ℓ12, can occur. We adapt the analysis and code construction of Cassuto, et al. for the refined error model and assess the relative efficiency of the new codes. We then consider in more detail specific constructions for the case where t1= t2= 1, ℓ1= 1, and ℓ2>; 1.

A Write-Once Memory (WOM)-code is a coding scheme that allows information to be written in a memory block multiple times, but in a way that the stored values are not decreased across writes. This work studies non-binary WOM-codes with applications to flash memory. We present two constructions of non-binary WOM-codes that leverage existing high sum-rate WOM-codes defined over smaller alphabets. In many instances, these constructions provide the highest known sum-rates of the non-binary WOM-codes. In addition, we introduce a new class of codes, called level distance WOM-codes, which mitigate the difficulty of programming a flash memory cell by eliminating all small-magnitude level increases. We show how to construct such codes and state an upper bound on their sum-rate.

We consider terminated LDPC convolutional codes (LDPC-CC) constructed from photographs and explore the performance of these codes on correlated erasure channels including a single-burst channel (SBC) and Gilbert-Elliott channel (GEC). We consider code performance with a latency-constrained message passing decoder and the belief propagation decoder. We give theoretical bounds on the code efficiency over the SBC and describe a construction that achieves this bound.We show that the designed codes with belief propagation (BP) decoding perform as well as the regular LDPC-CCs presented in the literature on the binary erasure channel (BEC) and the GEC, while achieving significant gains on the SBC. In the case of windowed decoding, our codes perform much better than the best known regular LDPC-CCs over the BEC and the GEC, with very low decoding latencies.

We propose a new channel model for the write channel in Magnetic Recording with Bit-Patterned Media. We study information theoretic propoerties of this channel and suggest a simplistic rate-1/2 coding scheme that achieves zero error. Based on this channel model, we propose a channel with insertion and deletion errors.

A Write Once Memory (WOM) is a storage medium with binary memory elements, called cells, that can change from the zero state to the one state only once. Examples of WOMs are punch cards, optical disks, and more recently flash memories. WOM-codes were first presented by Rivest and Shamir and are designed for efficiently storing and updating data in the WOM. A WC[n, k, t] WOM-Code CWis a coding scheme for storing k information bits in n cells t times. At each write, the state of each cell can be changed, provided that the cell is changed from the zero state to the one state. The WOM-Rate of CW, defined to be Rt(CW) = kt/n, indicates the total amount of information that is possible to store in a cell in t writes. Two WOM-code constructions that can correct a single cell-error were presented by Zémor and Cohen. In this paper, we present another construction of a single-error-correcting WOM-codes with a better WOM-rate. Our construction can be adjusted also for single-error-detection, double-error-correction, and triple-error-correction. For the latter case, we use triple-error-correcting BCH-like codes, which were showed by Kasami and more recently described again by Bracken and Helleseth.

Parallel programming is an important tool used in flash memories to achieve high write speed. In parallel programming, a common programm voltage is applied to many cells for simultaneous charge injection. This property significantly simplifies the complexity of the memory hardware, and is a constraint that limits the storage capacity of flash memories. Another important property is that cells have different hardness for charge injection. It makes the charge injected into cells differ even when the same program voltage is applied to them. In this paper, we study the parallel programming of flash memory cells, focusing on the above two properties. We present algorithms for parallel programming when there is information on the cells' hardness for charge injection, but there is no feedback information on cell levels during programming. We then proceed to the programming model with feedback information on cell levels, and study how well the information on the cells' hardness for charge injection can be obtained. The results can be useful for understanding the storage capacity of flash memories with parallel programming.

A Write Once Memory (WOM) is a storage medium with binary memory elements, called cells, that can change from the zero state to the one state only once. Examples of WOMs are punch cards, optical disks, and more recently flash memories. A t-write WOM-code is a coding scheme for storing t messages in n cells in such a way that each cell can change its value only from the zero state to the one state. The WOM-rate of a t-write WOM-code is the ratio of the total amount of information written to the WOM in t writes to the number of cells. In this paper we present a family of 2-write WOM-codes. It is shown how to construct from each linear code C a 2-write WOM-code. Then, we find 2-write WOM-codes that improve the best known WOM-rate with two writes. This scheme is proved to be capacity achieving when the parity check matrix of the linear code C is chosen uniformly at random. Finally, we show how to take advantage of 2-write WOM-codes in order to construct codes for the Blackwell channel.

In high density perpendicular magnetic recording channels, nonlinear transition shift (NLTS) is one of the distortions that can degrade the system performance. Write precompensation is a standard method used to combat the negative effect of NLTS. In this paper, we present an analysis of the bit-error-rate (BER) for perpendicular recording systems with NLTS and write precompensation. Media jitter noise and additive white Gaussian noise are also considered in the model. A BER lower bound is derived, as well as a more easily computed estimate of the bound. The write precompensation values that numerically minimize the estimate of the BER lower bound prove to be very close to those found using Monte-Carlo channel simulation. We then apply these methods to the design of multilevel precompensation schemes, for which the optimization of precompensation values by Monte-Carlo channel simulation is computationally infeasible. The results show that for higher recording densities subject to increased ISI and noise, the use of more complex precompensation schemes does not significantly improve the system performance.

Flash memory is a nonvolatile computer memory comprised of blocks of cells, wherein each cell is implemented as either NAND or NOR floating gate. NAND flash is currently the most widely used type of flash memory. In a NAND flash memory, every block of cells consists of numerous pages; rewriting even a single page requires the whole block to be erased and reprogrammed. Block erasures determine both the longevity and the efficiency of a flash memory. Therefore, when data in a NAND flash memory are reorganized, minimizing the total number of block erasures required to achieve the desired data movement is an important goal. This leads to the flash data movement problem studied in this paper. We show that coding can significantly reduce the number of block erasures required for data movement, and present several optimal or nearly optimal data-movement algorithms based upon ideas from coding theory and combinatorics. In particular, we show that the sorting-based (noncoding) schemes require$O(n\log n)$erasures to move data among$n$blocks, whereas coding-based schemes require only$O(n)$erasures. Furthermore, coding-based schemes use only one auxiliary block, which is the best possible and achieve a good balance between the number of erasures in each of the$n+1$blocks.

NAND flash memories are currently the most widely used flash memories. In a NAND flash memory, although a cell block consists of many pages, to rewrite one page, the whole block needs to be erased and reprogrammed. Block erasures determine the longevity and efficiency of flash memories. So when data is frequently reorganized, which can be characterized as a data movement process, how to minimize block erasures becomes an important challenge. In this paper, we show that coding can significantly reduce block erasures for data movement, and present several optimal or nearly optimal algorithms. While the sorting-based non-coding schemes require O(n log n) erasures to move data among n blocks, coding-based schemes use only O(n) erasures and also optimize the utilization of storage space.

Flash memory is a non-volatile computer memory comprised of blocks of cells, wherein each cell can take on q different values or levels. While increasing the cell level is easy, reducing the level of a cell can be accomplished only by erasing an entire block. Since block erasures are highly undesirable, coding schemes - known as floating codes or flash codes - have been designed in order to maximize the number of times that information stored in a flash memory can be written (and re-written) prior to incurring a block erasure. An (n, k, t)qflash code ¿ is a coding scheme for storing k information bits in n cells in such a way that any sequence of up to t writes (where a write is a transition 0 ¿ 1 or 1 ¿ 0 in any one of the k bits) can be accommodated without a block erasure. The total number of available level transitions in n cells is n(q-1), and the write deficiency of ¿, defined as ¿(¿) = n(q-1)-t, is a measure of how close the code comes to perfectly utilizing all these transitions. For k > 6 and large n, the best previously known construction of flash codes achieves a write defficiency of O(qk2). On the other hand, the best known lower bound on write deficiency is ¿(qk). In this paper, we present a new construction of flash codes that approaches this lower bound to within a factor logarithmic in k. To this end, we first improve upon the so-called ¿indexed¿ flash codes, due to Jiang and Bruck, by eliminating the need for index cells in the Jiang-Bruck construction. Next, we further increase the number of writes by introducing a new multi-stage (recursive) indexing scheme. We then show that the write defficiency of the resulting flash codes is O(qk log k) if q ¿ log2k, and at most O(k log2k) otherwise.

Despite flash memory's promise, it suffers from many idiosyncrasies such as limited durability, data integrity problems, and asymmetry in operation granularity. As architects, we aim to find ways to overcome these idiosyncrasies while exploiting flash memory's useful characteristics. To be successful, we must understand the trade-offs between the performance, cost (in both power and dollars), and reliability of flash memory. In addition, we must understand how different usage patterns affect these characteristics. Flash manufacturers provide conservative guidelines about these metrics, and this lack of detail makes it difficult to design systems that fully exploit flash memory's capabilities. We have empirically characterized flash memory technology from five manufacturers by directly measuring the performance, power, and reliability. We demonstrate that performance varies significantly between vendors, devices, and from publicly available datasheets. We also demonstrate and quantify some unexpected device characteristics and show how we can use them to improve responsiveness and energy consumption of solid state disks by 44% and 13%, respectively, as well as increase flash device lifetime by 5.2x.

In this paper, we analyze the distance properties of two-dimensional (2-D) intersymbol interference (ISI) channels, in particular the 2-D partial response class-1 (PR1) channel which is an extension of the one-dimensional (1-D) PR1 channel. The minimum squared-Euclidean distance of this channel is proved to be 4 and a complete characterization of the squared-Euclidean distance 4 error events is provided. As for 1-D channels, we can construct error-state diagrams for 2-D channels to help characterize error events. We propose an efficient error event search algorithm operating on the error-state diagram that is applicable to any 2-D channel.

The read-write process in perpendicular magnetic recording channels includes a number of nonlinear effects. Nonlinear transition shift (NLTS) arising from previously written transitions is one of these. The signal distortion induced by NLTS is reduced by use of write precompensation during data recording. In this paper, we numerically evaluate the effect of NLTS on the read-back signal by using the model proposed by Bertram and Nakamoto. By means of computer simulation, we examine the effectiveness of two write precompensation schemes in combating NLTS effects in a channel characterized by both transition jitter noise and additive white Gaussian electronics noise. We numerically optimize the precompensation schemes according to channel bit-error-rate, as well as more computationally tractable criteria. Our results suggest that a write-precompensation technique with as few as two adjustable parameters can be very effective against NLTS effects.

In this work, we present a novel construction for solving the linear multiuser detection problem using the Gaussian Belief Propagation algorithm. Our algorithm yields an efficient, iterative and distributed implementation of the MMSE detector. Compared to our previous formulation, the new algorithm offers a reduction in memory requirements, the number of computational steps, and the number of messages passed. We prove that a detection method recently proposed by Montanari et al. is an instance of ours, and we provide new convergence results applicable to both.

The canonical problem of solving a system of linear equations arises in numerous contexts in information theory, communication theory, and related fields. In this contribution, we develop a solution based upon Gaussian belief propagation (GaBP) that does not involve direct matrix inversion. The iterative nature of our approach allows for a distributed message-passing implementation of the solution algorithm. We also address some properties of the GaBP solver, including convergence, exactness, its max-product version and relation to classical solution methods. The application example of decorrelation in CDMA is used to demonstrate the faster convergence rate of the proposed solver in comparison to conventional linear-algebraic iterative solution methods.

We study coding schemes which encode unconstrained sequences into run-length-limited (d, k)-constrained sequences. We present a general framework for the construction of such (d, k)-codes from variable-length source codes. This framework is an extension of the previously suggested bit stuffing, bit flipping, and symbol sliding algorithms. We show that it gives rise to new code constructions which achieve improved performance over the three aforementioned algorithms. Therefore, we are interested in finding optimal codes under this framework, optimal in the sense of maximal achievable asymptotic rates. However, this appears to be a difficult problem. In an attempt to solve it, we are led to consider the encoding of unconstrained sequences of independent but biased (as opposed to equiprobable) bits. Here, our main result is that one can use the Tunstall source coding algorithm to generate optimal codes for a partial class of (d, k) constraints.

A two-dimensional (2-D) constrained system consists of 2-D binary sequences satisfying certain properties. Most of the 2-D constrained systems can be represented as a set of forbidden patterns, which should be avoided in the input sequences to the channel. This paper proposes a depth-first algorithm to search for single-state codes with rectangular codewords. The algorithm provides the optimal single-state codes, meaning that no other single-state code can have larger coding rate. For certain 2-D constraints, this algorithm has comparatively low complexity. The coding rate asymptotically approaches the capacity of the 2-D constrained system when the codeword size increases.

We study coding schemes which encode unconstrained sequences into run-length-limited (d, k)-constrained sequences. We present a general framework for the construction of such (d, k)-codes from variable-length source codes. This framework is an extension of the previously suggested bit stuffing, bit flipping and symbol sliding algorithms. We show that it gives rise to new code constructions which achieve improved performance over the three aforementioned algorithms. Therefore, we are interested in finding optimal codes under this framework, optimal in the sense of maximal achievable asymptotic rates. However, this appears to be a difficult problem. In an attempt to solve it, we are led to consider the encoding of unconstrained sequences of independent but biased (as opposed to equiprobable) bits. Here, our main result is that one can use the Tunstall source coding algorithm to generate optimal codes for a partial class of (d, k) constraints

For one-dimensional (1-D) recording channels, the detector performance can be assessed by the distance properties of the channel, which are defined in terms of the maximum-likelihood decoding trellis. Error events with minimum and near minimum distances play an important role in the performance of the recording system particularly at moderate to high signal-to-noise ratio (SNR). In this paper, we analyze the distance properties of two-dimensional (2-D) inter-symbol interference channels, in particular the 2-D PR1 channel which is an extension of the 1-D PR1 channel. The minimum distance of this channel is proved to be 2 and a complete characterization of the distance-2 error events is provided. Also, the error events with squared-Euclidean distance 6 are partially characterized. Analogous to 1-D channels, error-state diagrams for 2-D channels can be constructed to characterize the error events. We propose an efficient error event search algorithm operating on the error-state diagram that is applicable to any 2-D channel

In this paper we compare some aspects of the design and analysis of one-dimensional (1-D) and two-dimensional (2-D) storage systems. We show that for modulation codes and for the detection of signals corrupted by intersymbol interference and additive white Gaussian noise, the design and analysis is much more complicated in the 2-D case as compared with the 1-D case. However, we show that the reverse is true for the design of burst error correcting cyclic codes. That is, we show that one must carefully choose the generator polynomial to obtain a good 1-D burst error correcting code but using a cyclic product code, any arbitrary generator polynomials for the row code and for the column code can produce a good 2-D burst error correcting code.

We present bit-stuffing schemes which encode arbitrary data sequences into two-dimensional (2-D) constrained arrays. We consider the class of 2-D runlength-limited (RLL) (d, infin) constraints as well as the 'no isolated bits' (n.i.b.) constraint, both defined on the square lattice. The bit stuffing technique was previously introduced and applied to the class of 2-D (d, infin) constraints. Analytical lower bounds on the rate of these encoders were derived. For d = 1, a more general scheme was analyzed and shown to obtain improved performance. We extend the (1, infin)-construction to (d, infin) constraints where d ges 2. We then suggest a bit-stuffing scheme for the n.i.b. constraint, based on a capacity-achieving scheme for a one-dimensional RLL (0,3) constraint. Simulation results demonstrate the performance of the proposed schemes

The achievable information rates for multilevel coding (MLC) systems with multistage decoding (MSD) are examined on two-dimensional binary-input intersymbol interference (ISI) channels. One MSD scheme employs trellis-based detection, while another involves zero-forcing equalization and linear noise prediction. Information rates are determined by examining the output statistics at each stage of MSD. The first scheme is shown to achieve rates very close to known information-theoretic limits. Systems with low-density parity-check codes are then optimized to approach these rates

The bit stuffing algorithm is a technique for coding constrained sequences by the insertion of bits into an arbitrary data sequence. This approach was previously introduced and applied to (d,k) constrained codes. Results show that the maximum average rate of the bit stuffing code achieves capacity when k=d+1 or k=/spl infin/, while it is suboptimal for all other (d,k) pairs. Furthermore, this technique was generalized to produce codes with an average rate that achieves capacity for all (d,k) pairs. However, this extension results in a more complicated scheme. This correspondence proposes a modification to the bit stuffing algorithm that maintains its simplicity. We show analytically that the proposed algorithm achieves improved average rates over bit stuffing for most (d,k) constraints. We further determine all constraints for which this scheme produces codes with an average rate equal to the Shannon capacity.

The hard-square model is a two-dimensional (2-D) constrained system consisting of all binary arrays on a rectangular grid in which 1's are isolated both horizontally and vertically. This paper proposes algorithms to search for single-state and finite-state block codes with rectangular codewords that satisfy the hard-square constraint. Although the codeword size is small, single-state block codes with coding rates larger than 0.5 can be designed. Letting the 2-D constrained sequences have finite memory increases the achievable coding rate. A method for designing low-complexity encoders and decoders is also presented. When the codeword size increases, the coding rate asymptotically approaches the capacity but with rapidly increasing complexity of the encoder and decoder.

The bit stuffing algorithm is a technique for coding constrained sequences by the insertion of bits into an arbitrary data sequence. This approach was previously introduced and applied to (d, k) constrained codes. Results show that the maximum average rate of the bit stuffing code achieves capacity when k=d+1 or k=/spl infin/, while it is suboptimal for all other (d, k) pairs. We propose a modification to the bit stuffing algorithm. We show analytically that the proposed algorithm achieves improved average rates over bit stuffing for most (d, k) constraints.

The hard-square model is a two-dimensional (2D) constrained system consisting of all binary 2D rectangles in which 1's are isolated both horizontally and vertically. We propose 2D block codes with rectangular codewords which achieve coding rates larger than 0.5.

This paper describes the analysis of convolutional codes on the erasure channel. We compare the maximum likelihood (ML) sequence decision and the maximum a posteriori (MAP) symbol decision for codes, which are transmitted over the erasure channel. When a codeword from a linear error correcting code with elements from the field GF is transmitted over a q-ary erasure channel, the symbol error rate of the maximum likelihood (ML) sequence decision is the same as that of the symbol maximum a posteriori (MAP) probability decision. When decoding convolutional codes transmitted over an AWGN channel, it is widely known that the probability of symbol error for the Viterbi algorithm (which is a sequence ML decoder) is generally higher than that for the more complex BCJR algorithm (which is a symbol MAP decoder).

We derive lower bounds on the capacity of certain two-dimensional (2-D) constraints by considering bounds on the entropy of measures induced by bit-stuffing encoders. A more detailed analysis of a previously proposed bit-stuffing encoder for (d,/spl infin/)-runlength-limited (RLL) constraints on the square lattice yields improved lower bounds on the capacity for all d /spl ges/ 2. This encoding approach is extended to (d,/spl infin/)-RLL constraints on the hexagonal lattice, and a similar analysis yields lower bounds on the capacity for d /spl ges/ 2. For the hexagonal (1,/spl infin/)-RLL constraint, the exact coding ratio of the bit-stuffing encoder is calculated and is shown to be within 0.5% of the (known) capacity. Finally, a lower bound is presented on the coding ratio of a bit-stuffing encoder for the constraint on the square lattice where each bit is equal to at least one of its four closest neighbors, thereby providing a lower bound on the capacity of this constraint.

Analytic expressions for the exact probability of erasure for systematic, rate- 1/2 convolutional codes used to communicate over the binary erasure channel and decoded using the soft-input, soft-output (SISO) and a posteriori probability (APP) algorithms are given. An alternative forward-backward algorithm which produces the same result as the SISO algorithm is also given. This low-complexity implementation, based upon lookup tables, is of interest for systems which use convolutional codes, such as turbo codes.

The performance of iterative detection methods is evaluated for the binary-input two-dimensional (2D), linear inter-symbol interference (ISI) channel with additive white Gaussian noise (AWGN). All of the proposed detection schemes involve message passing between detectors operating iteratively on the rows and columns of the 2D channel observations. Simulation results indicate that both the constituent detector performance and the loopiness of the underlying graphical model affect the iterative detector performance. Results are presented for a class of 3-tap, 2D channels defined by a single parameter. These indicate that straightforward application of turbo equalization to the 2D ISI problem performs poorly, but with ad-hoc enhancements, maximum likelihood (ML) detection is approached, to within 0.5 dB.

Ideas of message passing are applied to the problem of removing the effects of intersymbol interference (ISI) from partial-response channels. Both bit-based and state-based parallel message-passing algorithms are proposed. For a fixed number of iterations less than the block length, the bit-error rate of the state-based algorithm approaches a nonzero constant as the signal-to-noise ratio (SNR) approaches infinity. This limitation can be removed by using a precoder. It is well known that low-density parity-check (LDPC) codes can be decoded using a message-passing algorithm. Here, a single message-passing detector/decoder matched to the combination of a partial-response channel and an LDPC code is investigated.

Three dependent users are physically separated but communicate with each other via a satellite. Each user generates data which it stores locally. In addition, each user sends a message to the satellite. The satellite processes the messages received from the users and broadcasts one common message to all three users. Each user must be capable of reconstructing the data of the other two users based upon the broadcast message and its own stored data. Our problem is to determine the minimum amount of information which must be transmitted to and from the satellite. The solution to this problem is obtained for the case where subsequent data triples that are produced by the users are independent and identically distributed. The three symbols within each triple are assumed to be dependent. Crucial for the solution is an achievability proof that involves cascaded Slepian-Wolf (1973) source coding.

Message-passing has been proposed for decoding parity check codes, especially low density parity check (LDPC) codes. We propose using message-passing detectors for partial response channels. Furthermore, we investigate how a single message-passing detector/decoder can be matched to a combination of a partial response channel and a LDPC code.

The MAP algorithm used in turbo decoders is very parallelizable. This property can be used to speed them up. The speedup is attained at the expense of increased complexity and processing hardware. The increase in processing hardware is linear with the speedup but the increase in complexity of the parallel implementation compared to the traditional implementation is extremely small and this is the main observation of this paper. We discuss the parallel implementation of the MAP algorithm, the increase in complexity and memory and contrast the behaviour with that of the Viterbi algorithm. The results given here also suggest a change in design methodology of the sliding window implementation of turbo decoders.

A new method of combating the effects of thermal asperities (TAs) in disk drives is proposed. In the classic method, changing a parameter in the equalizer modifies the duration of a TA but no attempt is made to modify the detector that follows the equalizer or to improve its performance. The proposed method involves modification of both the equalizer and the detector. Specifically, two channels are run in parallel. One channel is matched to the partial response polynomial P(D), whereas the other is matched to the partial response polynomial (1-D)P(D). P(D) is the target polynomial of the existing magnetic recording channel. The Viterbi detector in the (1-D)P(D) channel has better decoded bit error rate (BER) during a TA, and the Viterbi detector in the P(D) channel has better BER in the absence of a TA. The overall decoded bit stream is selected from these two Viterbi detectors in accordance as to whether a TA has been detected. The performance of the proposed method was studied via simulation for the magnetic recording channel with the target polynomial P(D)=(1-D)(1+D)/sup 2/ (EPR4). The proposed system was found to be superior to existing methods in the presence of TAs, while having the same performance in the presence of additive white Gaussian noise (AWGN).

The design of finite-length decision-feedback equalization (DFE) forward and feedback filters under the assumption of genie-aided feedback and independent and equally likely transmitted symbols is considered. It is shown that the problem of determining DFE filters that minimize the probability of symbol error at high signal-to-noise ratio (SNR) is equivalent to finding the hyperplane that maximally separates two given finite groups of points in a finite-dimensional Euclidean space. The latter task can be formulated as a quadratic program which is readily solved numerically. It is also shown that the problem of finding finite-length DFE filters that minimize the probability of symbol error at any SNR subject to a certain separation condition is a convex optimization problem. The case where the transmitted data is coded using a runlength-limited code is also investigated. Examples show that this criterion yields a performance that is better than zero-forcing DFE on severely distorted channels at high SNR.

The hard-square model, also known as the two-dimensional (2-D) (1, /spl infin/)-RLL constraint, consists of all binary arrays in which the 1's are isolated both horizontally and vertically. Based on a certain probability measure defined on those arrays, an efficient variable-to-fixed encoder scheme is presented that maps unconstrained binary words into arrays that satisfy the hard-square model. For sufficiently large arrays, the average rate of the encoder approaches a value which is only 0.1% below the capacity of the constraint. A second, fixed-rate encoder is presented whose rate for large arrays is within 1.2% of the capacity value.

The partial response channel can be viewed as a rate-1 encoder in which the output alphabet differs from the input alphabet. In serially concatenated coding schemes, the partial response channel can serve as the inner encoder. Previous work on the application of turbo decoding techniques to partial response channels has focused on using a parallel concatenation of convolutional encoders as the outer code and the partial response channel as the inner code. This system requires three a posteriori probability (APP) detectors-one matched to the channel and two matched to the constituent encoders. A simplified system is presented that uses as its outer code a single convolutional code and as its inner code the partial response channel. The simplified system requires only two APP detectors, offering significant savings in complexity and computation time. This single convolutional code system is shown to perform as well as the more complicated system, offering substantial gains over uncoded systems. Simulation results for three magnetic recording channel models are presented: a partial response channel with additive white Gaussian noise, an equalized Lorentzian channel model, and a media noise model called the microtrack model. Since the use of an outer Reed-Solomon code is anticipated in an actual system, the burst-error statistics are investigated. System performance with various interleaver designs and precoders is also investigated.

Recent work on the application of turbo decoding techniques to partial response class 4 (PR4) channels has focused on parallel concatenation systems that require three a posteriori (APP) detectors. A simplified serial concatenation system is presented that uses as its outer code a single convolutional code and as its inner code the partial response channel. An extension of this serial concatenation system is also presented that combines a second code with the channel, forming a more powerful inner code. Both proposed systems require only two APP detectors, offering significant savings in complexity and computation time. These serial concatenation systems are shown to perform as well as the more complicated parallel concatenation systems, offering substantial gains over uncoded systems. Additionally, the effect of precoding is investigated. Simulation results comparing the parallel and serial concatenation systems are also presented.

Two algorithms for characterization of input error events producing specified distance at the output of certain binary-input partial-response (PR) channels are presented. Lists of error events are tabulated for PR channels of interest in digital recording.

The microtrack model for transition noise with partial erasure in thin film media has been shown to be a useful tool for simulating and analyzing detector performance under realistic conditions. However, several effects resulting from interactions between neighboring transitions are not accounted for in this model. These effects include transition broadening, increased transition noise, and nonlinear transition shift (NLTS). A simple modification to the microtrack model to incorporate the demagnetization field of neighboring transitions is presented. NLTS, transition broadening and increased transition noise as well as their interaction with the partial erasure effect directly result. The resulting effects are shown to agree with those seen in an experiment.

Constrained codes are a key component in digital recording devices that have become ubiquitous in computer data storage and electronic entertainment applications. This paper surveys the theory and practice of constrained coding, tracing the evolution of the subject from its origins in Shannon's classic 1948 paper to present-day applications in high-density digital recorders. Open problems and future research directions are also addressed.

We explain how to obtain the weight enumerator and the performance of linear block codes formed in several distinct ways from a convolutional code.

A hardware device for efficiently evaluating the probability of undetected error for a class of CRC error detection codes with a large number of parity check digits is described. The generator polynomial for the codes in this class are of the form g(x)=(1+x)p(x) where p(x) is a primitive irreducible polynomial. The degree of g(x), R, is the number of parity check digits. Using this hardware, a search was conducted for codes in this class (for 8/spl les/R/spl les/39) which are "proper" for shortened block lengths. A table of codes satisfying this condition is included.>

Using a new statistical model for burst errors, the authors calculate the conditional probability of undetected error for CRC codes with generator polynomials of the form g(x)=(1+x)p(x), p(x) a primitive polynomial. They show that the choice of p(x) affects the performance of these codes.>

A systematic way to design nonuniformly spaced tapped-delay-line (TDL) equalizers is described, and the performance of such equalizers is compared to that of uniformly spaced TDL equalizers with the same number of tap coefficients. It is shown that the signal-to-mean-squared-error ratio at the output of a TDL equalizer can be improved by optimally choosing the positions of the tap weights. An algorithm to find both the tap positions and the corresponding tap weights for a given delay span and a given minimum tap spacing of the equalizer is presented. Typical results are illustrated by using, as an example, the magnetic recording channel. For two target waveforms at different densities of recording, it is shown that there is a potential for saving up to seven equalizer taps.>

The performance of finite intersymbol interference (ISI) channels in the presence of additive white Gaussian noise is evaluated by interpreting the ISI channel as a trellis code. Closed form results are obtained for ISI channels with one and two symbols of interference. An efficient algorithm is also introduced to evaluate the minimum free Euclidean distance of any ISI channel.>

The authors provide a self-contained exposition of modulation code design methods based upon the state splitting algorithm. They review the necessary background on finite state transition diagrams, constrained systems, and Shannon (1948) capacity. The state splitting algorithm for constructing finite state encoders is presented and summarized in a step-by-step fashion. These encoders automatically have state-dependent decoders. It is shown that for the class of finite-type constrained systems, the encoders constructed can be made to have sliding-block decoders. The authors consider practical techniques for reducing the number of encoder states as well as the size of the sliding-block decoder window. They discuss the class of almost-finite-type systems and state the general results which yield noncatastrophic encoders. The techniques are applied to the design of several codes of interest in digital data recording.>

The cutoff rate of a discrete memoryless channel whose output sequences are from a (d, k) encoder is investigated. A rational rate (d, k) encoder is considered as a finite state machine and maximum-likelihood decoding is used to compute the cutoff rate. Some commonly used (d, k) codes, such as the rate 1/2 (1, 3) code with a two-state encoder, the IBM rate 2/3 (1, 7) code having a five-state encoder, and the IBM rate 1/2 (2, 7) code with a seven-state encoder, are used to illustrate the cutoff rate computation. Results are presented for both the binary symmetric channel (BSC) and the Gaussian noise channel. The performance of a decoder designed for noiseless transmission of (1, 3) code is compared to that of a maximum-likelihood decoder for the (1, 3) code. It is also shown that for the case of the Gaussian noise channel, a gain of about 1.7 dB in signal-to-noise ratio is possible by using 3-bit soft decisions over hard decisions.>

New results, which follow from a data compression algorithm proposed by A. Lempel and J. Ziv (1977), are presented. The authors describe the original Lempel-Ziv algorithm, and present an improved Lempel-Ziv data compression algorithm. They state and prove some asymptotic bounds on the compression ratio that the improved algorithm achieves. For completeness, they describe the Lempel-Ziv-Welch data compression algorithm presented by T. A. Welch (1984). A software implementation for both the original and the improved Lempel-Ziv algorithms is given, and the algorithms are compared with each other as well as with the Lempel-Ziv-Welch algorithm.>

An input-output characterization for a digital magnetic recording system is presented. The most common modulation and coding techniques used in current products are surveyed. Some techniques for signal processing in magnetic recording are then discussed. The author concludes with a brief introduction to signal processing for arrays of magnetic disk drives.>

A parity check matrix is given for a systematic (12,8) binary code which connects all single errors and detects eight of the nine double adjacent errors within any of the three 4-b nibbles. It is shown that no (12,8) binary systematic parity check code can correct all 12 single errors and simultaneously detect all nine double adjacent errors within 4-b nibbles. A (12,8) binary systematic parity check code is given that corrects all 12 single errors and simultaneously detects eight of the nine double adjacent errors within 4-b nibbles.>

A random multiple-access system which employs a collision resolution algorithm for accessing a common time-varying channel is considered. The channel is assumed to be in one of two states. In each state, the channel is characterized by a general discrete memoryless channel and the transitions between the two states are assumed to be Markovian. A set of sufficient conditions for the ergodicity (stability) of the system is established. As an example, the case when the Capetanakis tree algorithm operates with a time-varying noisy channel is examined. The stability of this system is analyzed, and the throughput is evaluated.>

A model is proposed for errors that occur in estimating frequency offset between oscillators driving two clocks that are synchronized with a digital control loop. Three specific estimators are analyzed. One, the maximum-likelihood estimator, yields a minimum-mean-square estimate for Gaussian errors. A second offers convenient implementation and provides performance close to that of the maximum-likelihood estimator.>

The diameter of a class of random directed graphs in which the outdegree of each vertex is constrained to be exactly k is examined. Vertices connect themselves to k other distinct vertices with outwardly directed edges, all possible sets of k vertices being chosen with equal probability. It is shown that the diameter of such a random graph almost surely takes on only one of two values.>

A random multiple-access system which uses a collision resolution algorithm for accessing a common time-varying channel is considered. The channel is assumed to be in one of two states. In each state the channel is characterized by a general discrete memoryless channel, and the transitions between the two states are assumed to be Markovian. A set of sufficient conditions for the ergodicity (stability) of the system is established. As an example, the case when the Capetanakis tree algorithm operates with a time-varying noisy channel is examined. The stability of this system is analyzed and the throughput is evaluated.>

A general method is presented for constructing a single-error-correcting, run-length-limited code for the class of input-restricted, binary symmetric channels described by the parameters (d,k), where d is the minimum and k the maximum number of consecutive zeros in any allowable channel input sequence. Upper and lower bounds on the rates of these codes are derived.>

A class-constrained resource allocation problem is considered. In this problem, a set of M heterogeneous resources is to be allocated optimally among a set of L users belonging to K user classes. A set of class allocation constraints, which limit the number of users of a given class that could be allocated to a given resource, is imposed. An algorithm with worst case time complexity O(M (LM + M2 + LK)) is presented along with a proof of its correctness. This problem arises in many areas of resource management in computer systems, such as load balancing in distributed systems, transaction processing in distributed database systems, and session allocation in time-shared computer systems. We illustrate the behavior of this algorithm with an example where file servers are to be allocated to workstations of multiple classes.

Many problems can be modeled as single-server queues with impatient customers. An example is that of the transmission of voice packets over a packet-switched network. If the voice packets do not reach their destination within a certain time interval of their transmission, they are useless to the receiver and considered lost. It is therefore desirable to schedule the customers such that the fraction of customers served within their respective deadlines is maximized. For this measure of performance, it is shown that the shortest time to extinction (STE) policy is optimal for a class of continuous and discrete time nonpreemptive M/G/1 queues that do not allow unforced idle times. When unforced idle times are allowed, the best policies belong to the class of shortest time to extinction with inserted idle time (STEI) policies. An STEI policy requires that the customer closest to his or her deadline be scheduled whenever it schedules a customer. It also has the choice of inserting idle times while the queue is nonempty. It is also shown that the STE policy is optimal for the discrete time G/D/1 queue where all customers receive one unit of service. The paper concludes with a comparison of the expected customer loss using an STE policy with that of the first-come, first-served (FCFS) scheduling policy for one specific queue.

It is shown that under certain conditions, when convolutional codes with precoding are used in conjunction with a partial response channel, the number of decoder states in a maximum-likelihood decoder matched to both the code and channel is 1/2 of that predicted by J.K. Wolf and G. Ungerboeck (ibid., vol.COM-34, no.7, p.751-72, 1986).>

Several results on binary (d, k) codes are given. First, a novel derivation for the capacity of these codes based on information-theoretic principles is given. Based on this result the spectrum of a (d, k) code is computed. Finally, the problem of computing the capacity of the binary symmetric channel under the condition that the input sequences satisfy the (d, k) constraint is considered. Lower bounds on the capacity of such a channel are derived.>

A class of binary quasi-cyclic burst error-correcting codes based upon product codes is studied. An expression for the maximum burst error-correcting capability for each code in the class is given. In certain cases, the codes exist in the class which have the same block length and number of check bits as the Gilbert codes, but correct longer bursts of errors than Gilbert codes. By shortening the codes, it is possible to design codes which achieve the Reiger bound.>

A new design procedure is described for constructing rate 1/2 and rate 2/3 majority logical decodable burst error-correcting codes. The rate 1/2 codes are closely related to the codes of Srinivasan [1].

Generating function techniques for analyzing the error event and the bit-error probabilities for trellis codes are considered. The conventional state diagram approach for linear codes where the number of states is equal to the number of trellis states cannot be applied directly to arbitrary trellis codes, and instead, a state diagram where the number of states is equal to the square of the number of trellis states must be used. It is shown that for an interesting class of trellis codes a modified generating function can be defined for which the number of states {\em is equal to} the number of trellis states. The class of codes considered includes trellis codes of rateR=(n-1)/nbased upon set partitioning whenever the first partition breaks the signal constellation into two subsets which have the same "configuration matrix," i.e., the same ordered set of mutual distances. The complexity of calculating this modified generating function is the same as for the ordinary generating function of a convolutional code with the same number of trellis states. Bounds on the performance of some interesting codes are given based upon this method.

In this paper, we introduce generalized tail biting encoding as a means to ameliorate the rate deficiency caused by zero-tail convolutional encoding. This technique provides an important link between quasi-cyclic block and convolutional codes. Optimum and suboptimum decoding algorithms for these codes are described and their performance determined by analytical and simulation techniques.

Channel coding combined with expanded signal sets has been shown [1] to improve error performance over uncoded modulation without expanding the bandwidth of the transmitted signals. In this paper, new coded modulation formats defined over an expanded set of signals varying both in phase and frequency are presented. The new schemes combine FSK and PSK modulation and make use of trellis coding and Viterbi decoding to improve error performance over uncoded modulation. The free Euclidean distance is calculated for several classes of codes, and upper bounds and simulation results are also presented for some simple codes. The spectral characteristics of the proposed coded modulation formats are evaluated and compared to conventional two-dimensional modulation formats. Differential encoding and various extensions of the basic scheme are also discussed.

We consider trellis-coding techniques for improving the reliability of digital transmission over noisy partial-response channels. Such channels are commonly encountered in digital communication systems, and also play a role in devices for data recording. Concentrating on the channels with characteristics(1 \mp D), we study methods to obtain codes which increase free Euclidean distance between permitted sequences of channel outputs and avoid the occurrence of unlimited runs of identical outputs at the expense of some loss in data rate. One technique employs the concept of set partitioning. The other is based on using convolutional codes designed for maximum free Hamming distance in conjunction with a precoder. Both methods lead to essentially equivalent codes.

A design procedure is presented for synthesizing threshold decodable rate1/nand(n - 1)/nself-orthogonal block codes obtained from truncating convolutional codes by generalized tail-biting (GTB). When GTB is applied to an equal error-protection threshold decodable convolutional code, the result is a class of unequal error-protection threshold decodable block codes. These codes are related to unequal error-protection codes previously described by Mandelbaum [1]. Furthermore, the codes of Mandelbaum are generalized.

It is shown that, for a ternary feedback random access channel with a Poisson arrival process,0.5is an upper bound to the throughput for all "degenerate intersection" algorithms (DIA's) and first-come first-served algorithms (FCFSA's). As a by-product, the nested FCFSA with the largest throughput is found for the random access channel with a Bernoulli arrival process with parameterp. Forp \geq 0.018, this algorithm has the highest throughput over all DIA's and FCFSA's. Lastly, it is shown that. for some values ofp, a non-DIA, non-FCFSA has a higher throughput than the optimum DIA or FCFSA.

A brief summary of the basic notions of group testing is presented together with a brief historical account. One of the early papers on group testing is shown to include a description of the tree-search polling algorithm of Hayes. The classical group testing problem is formulated, including a criterion for optimality of test plans. A restricted class of tests, called nested testing, is described, and a complete description for an optimal nested strategy is given for both a finite number and an infinite number of Bernoulli distributed random variables. A generalization of group testing applicable to the random access communications problem is presented.

We study the application of group testing to the design of efficient algorithms for random multiple-access communication systems. Both direct transmission and reservation systems are considered for various types of channel feedback. We propose and analyze algorithms based on conventional and generalized group testing techniques. The proposed algorithms outperform TDMA and algorithms based on binary tree search and possess certain optimality properties.

This paper proposes three different algorithms for polling a finite set of users to determine the binary state of each user. The states are assumed to be described by i.i.d. Bernoulli random variables with parameterp. The algorithms differ in the responses offered by the users to queries and how the responses from several users are combined by the channel to produce a composite feedback signal which is received by all users. For each algorithm, the average number of transmissions required to determine the states of all users is determined as a function of the parameterp.

We show that binary group codes that do not satisfy the asymptotic Varshamov-Gilbert bound have an undesirable characteristic when used as error detection codes for transmission over the binary symmetric channel.

The relationship between the discrete Fourier transform and error-control codes is examined. Under certain conditions we show that discrete-time sequences carry redundant information which then allow for the detection and correction of errors. An application of this technique to impulse noise cancellation for pulse amplitude modulation transmission is described.

The problem of computing the probability of undetected error is considered for linear block codes used for error detection. The recent literature is first reviewed and several results are extended. It is pointed out that an exact calculation can be based on either the weight distribution of a code or its dual. Using the dual code formulation, the probability of undetected error for the ensemble of all nonbinary linear block codes is derived as well as a theorem that shows why the probability of undetected error may not be a monotonic function of channel error rate for some poor codes. Several bounds on the undetected error probability are then presented. We conclude with detailed examples of binary and nonbinary codes for which exact results can be obtained. An efficient technique for measuring an unknown weight distribution is suggested and exact results are compared with experimental results.

Two specific noiseless multiple-access channel models, theT-userM-frequency multiple-access channel with and without intensity information, are studied in this paper. Information-theoretic bounds on the transmission rate for both models are presented. Constructive coding schemes are given for both channels which achieve zero error probability and whose rate sum is close to the information-theoretic bounds. Although the problem is formulated in terms of frequencies, the results are applicable to any signaling scheme where M orthogonal signals are used in each signaling interval including time partitioning of the interval.

A simple derivation is given of the MacWilliams' identity relating the weight distribution of the codewords in a linear code and the weight distribution of the dual code. The derivation is based upon elementary probabilistic arguments.

The stop-and-wait and continuous error detection retransmission schemes are widely used to control errors in many computercommunication systems. In this paper a model is developed which describes the statistical behavior of the multiplexer using these error detection and retransmission schemes. The model is applied to the case where errors are independent and can occur during data and/or acknowledgment transmission. Numerical results for the mean waiting time and mean queue occupancy are presented for the case of independent errors.

An algorithm for maximum likelihood decoding of terminated rate-1/Nconvolutional codes with hard decisions is presented which is based upon, but is simpler than, the Viterbi algorithm. The algorithm makes use of an algebraic description of convolutional codes introduced by Massey et al. For reasonable values of the probability of error, the algorithm is shown to produce substantial savings in decoding complexity compared with the Viterbi algorithm.

Some very simple codes are given for the two-user multiple-access adder channel with binary inputs that do not require word or bit synchronism between the encoders nor between the decoder and the encoders.

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.

The design of a coding/modulation structure for digital communications over a Rayleigh fading channel, the structure of the corresponding decoder, and the error rate performance of the resulting system are considered. Emphasis is on the use of constant weight codes for constructing equal energy waveforms for transmission over the channel. The performance gains that are achieved by the integrated coding/modulation approach relative to conventional methods for obtaining diversity are illustrated via some examples. Of special interest is the use of a concatenated coding technique for forming codes of large distance and hence high diversity. A new decoding algorithm is applied to enable efficient decoding of the concatenated code. An example is included that shows a performance increase of several dB resulting from concatenation.

It is shown that soft decision maximum likelihood decoding of any(n,k)linear block code overGF(q)can be accomplished using the Viterbi algorithm applied to a trellis with no more thanq^{(n-k)}states. For cyclic codes, the trellis is periodic. When this technique is applied to the decoding of product codes, the number of states in the trellis can be much fewer thanq^{n-k}. For a binary(n,n - 1)single parity check code, the Viterbi algorithm is equivalent to the Wagner decoding algorithm.

The capacity of a single-input single-output discrete memoryless channel is not increased by the use of a noiseless feedback link. It is shown, by example, that this is not the case for a multiple-access discrete memoryless channel. That is, it is shown that the capacity region for such a channel is enlarged if a noiseless feedback link is utilized.

Correlated information sequences\cdots ,X_{-1},X_0,X_1, \cdotsand\cdots,Y_{-1},Y_0,Y_1, \cdotsare generated by repeated independent drawings of a pair of discrete random variablesX, Yfrom a given bivariate distributionP_{XY} (x,y). We determine the minimum number of bits per characterR_XandR_Yneeded to encode these sequences so that they can be faithfully reproduced under a variety of assumptions regarding the encoders and decoders. The results, some of which are not at all obvious, are presented as an admissible rate region\mathcal{R}in theR_X - R_Yplane. They generalize a similar and well-known result for a single information sequence, namelyR_X \geq H (X)for faithful reproduction.

The coding theory literature for the period 1967-1972 is surveyed. Four contributions considered to be of special merit are identified. A brief description of several books solely concerned with coding theory is presented. The major themes reflected in selected English-language journals are outlined. More than 100 references are cited to illustrate these themes.

Source encoding techniques based on permutation codes are investigated. For a broad class of distortion measures it is shown that optimum encoding of a source permutation code is easy to instrument even for very long block lengths. Also, the nonparametric nature of permutation encoding is well suited to situations involving unknown source statistics. For the squared-error distortion measure a procedure for generating good permutation codes of a given rate and block length is described. The performance of such codes for a memoryless Gaussian source is compared both with the rate-distortion function bound and with the performance of various quantization schemes. The comparison reveals that permutation codes are asymptotically ideal for small rates and perform as well as the best entropy-coded quantizers presently known for intermediate rates. They can be made to compare favorably at high rates, too, provided the coding delay associated with extremely long block lengths is tolerable.

It is shown that the mixture of two codes of block lengthncan have a distortion strictly less than the distortion of the best possible code of block lengthnhaving the same rate. The seeming contradiction is explained by offering two interpretations for the mixture of two codes and then explaining why the bound for the performance of the best code cannot be applied directly to the mixture.

The burst-bdistance between two binary vectors is defined and shown to be a metric. This definition is applied to a binary-input,Q-ary output channel where errors occur in bursts. A decoding algorithm is presented for such a channel that is an extension of Weldon's [2] weighted erasure decoding. Examples are presented illustrating the techniques.

In this paper we derive an expression for the minimum-mean-square error achievable in encodingtsamples of a stationary correlated Gaussian source. It is assumed that the source output is not known exactly but is corrupted by correlated Gaussian noise. The expression is obtained in terms of the covariance matrices of the source and noise sequences. It is shown that ast \rightarrow \infty, the result agrees with a known asymptotic result, which is expressed in terms of the power spectra of the source and noise. The rate of convergence to the asymptotic results as a function of coding delay is investigated for the case where the source is first-order Markov and the noise is uncorrelated. WithDthe asymptotic minimum-mean-square error andD_tthe minimum-mean-square error achievable in transmittingtsamples, we find\mid D_t - D \mid \leq O((t^{-1} \log t) ^ {1/2})when we transmit the noisy source vectors over a noiseless channel and\mid D_t - D \mid \leq O((t^{-1} \log t)^ {1/3})when the channel is noisy.

Primitive BCH codes with symbols fromGF(q)and designed distancedhave parameter values \begin{align} \text{block length} &= n = q^m - 1 \\ \text{check symbols/block} &= r \leq m(d - 1) \end{align} wheremis any positive integer. For many nonbinary BCH codes (called maximally redundant codes), the maximum number of check symbols per block is required, i.e.r = m(d - 1). Conditions whereby a primitive nonbinary BCH code is maximally redundant are discussed. It is shown that a class of codes exists, with symbols fromGF(q), based upon doubly lengthened Reed-Solomon codes overGF(q^m), having parameter values \begin{align} \text{block length} &= n = m(q^m + 1) \\ \text{check symbols/block} &= r = m(d - 1) \\ \text{designed distance} &= d \end{align} where againmis any positive integer. Thus this class of codes extends the block length of maximally redundant codes by a multiplicative factor exceedingm, while retaining the same designed distance and same number of check symbols.

This paper is concerned with the transmission of information with a fidelity criterion where the source output may be distorted prior to encoding and, furthermore, where the output of the decoder may be distorted prior to its delivery to the final destination. The criterion for optimality is that the normalized average of the squared norm of the difference between theT- second undistorted source sample and the correspondingT-second sample delivered to the final destination be minimum. The optimal structure of the encoder and decoder is derived for anyT.

The use of extreme-value theory (EVT) in the detection of a binary signal in additive, but statistically unknown, noise is considered. It is shown that the optimum threshold and the probability of error of the system can be accurately estimated by using EVT to obtain properties of the initial probability density functions on their "tails." Both constant signals and slowly fading signals are considered. In the case of a fading signal, the detector becomes adaptive. Detection of the constant signal, both with and without an initial learning period, is studied by computer simulation.

The transmission of the linear sum ofmbiphase modulated signals in a time intervalTis considered for an additive Gaussian white noise channel of bandwidthW. Previous analyses consider the case wherem \leq n \equiv 2WT. In this paper, the probability of error is derived form > n, a situation which arises when the channel bandwidth is insufficient to support the data rate. Two distinct problems are considered. In the first, termed uncoded transmission, allmsignals are independently biphase modulated. It is shown, for this case, that if the channel signal-to-noise ratio increases linearly withn, the error probability can be made to go to zero approximately exponentially innfor any value ofm/n. In the second problem, termed ceded transmission, onlyk < mof the signals are independently modulated. (The remaining(m - k)signals carry redundant information.) By using a suboptimum receiver, it is shown that for a fixed channel signal-to-noise ratio the error probability goes to0exponentially innifk/nis less than some numberC^{\ast}. For high signal-to-noise ratio,C^{\ast}is greater than1, a situation which could not occur ifm \leq n.

We consider binary communication over the additive white Gaussian noise channel with no bandwidth constraint on the channel input signals, assuming the availability of a noiseless delayless feedback link. Although the signals at timetcan depend on the noise at times\tau < tand are therefore random functions, we require that the signal energy never exceed a fixed level. We show that the optimal probability of error is attainable without the use of the feedback channel by using antipodal signals.

The clustering of errors on real channels seriously complicates the task of evaluating the performance of error-control techniques. A model is introduced that, in addition to having the ability to match error distributions, greatly simplifies the task of code evaluations. Having selected the parameters of the model by matching the statistics recorded by Townsend and Watts on the switched telephone network, the model is shown to predict the results of tests of an interleaved burst-error-correcting code. The utility of the model is demonstrated in the analysis of error-detection codes with delayed retransmissions.

In this correspondence, we consider nonlinear binary error-correcting codes based upon then-fold interleaving of a periodic binary sequence of lengthLwith out-of-phase (normalized) autocorrelation-1/L. Examples of binary sequences with such out-of-phase autocorrelation (termed two-level sequences) are: 1) maximal-length linear shift-register \footnote[1]{sequences}, 2) twin-prime \footnote[2]{sequences}, 3) quadratic residue \footnote[3]{sequences}, and 4) Hall \foonote[4]{sequences}.

The class of codes discussed in this paper has the property that its error-correction capability is described in terms of correcting errors in specific digits of a code word even though other digits in the code may be decoded incorrectly. To each digit of the code words is assigned an error protection levelf_{i}. Then, ifferrors occur in the reception of a code word, all digits which have protectionf_{i}greater than or equal tofwill be decoded correctly even though the entire code word may not be decoded correctly. Methods for synthesizing these codes are described and illustrated by examples. One method of synthesis involves combining the parity check matrices of two or more ordinary random error-correcting codes to form the parity check matrix of the new code. A decoding algorithm based upon the decoding algorithms of the component codes is presented. A second method of code generation is described which follows from the observation that for a linear code, the columns of the parity check matrix corresponding to the check positions must span the column space of the matrix. Upper and lower bounds are derived for the number of check digits required for such codes. The lower bound is based upon counting the number of unique syndromes required for a specified error-correction capability. The upper bound is the result of a constructive procedure for forming the parity check matrices of these codes. Tables of numerical values for the upper and lower bounds are presented.

A class of codes is described having check matrices which are the tensor product of the check matrices of known nonbinary codes and binary codes. The error-correction, error-detection, and error-location capabilities of these codes are specified in terms of the properties of the component codes. The construction procedure allows for a class of codes with a wide variety of redundancies and error-control capabilities. Examples are given of codes from this class which correct random bursts of errors and bursts of bursts of errors.

A new coding technique is proposed lying midway between error-detection and error-correction coding. The block of received digits is regarded as subdivided into mutually exclusive sub-blocks. Errors occurring within particular sub-blocks are detected at the receiver and, in addition, the receiver is able to determine, by using the code redundancy, which particular sub-blocks contain errors. Such {\em error-locating} codes permit the location of digit errors to within a sub-block of the received message block without, in general, permitting the precise determination of erroneous digit positions. Two families of such codes are described, both of them limited to locating a single erroneous sub-block. One family permits the detection of up tot-1errors in any one sub-block of lengtht. The second family locates up to two errors per sub-block, but is generally more efficient in its use of redundancy than the first family. Upper and lower bounds are given for the number of check digits required with any error-locating code. Codes meeting the lower bound exactly are termed {\em optimum} error-locating codes. All the codes of the second family, as well as some isolated examples oft-1error-locating codes are optimum in this sense. The amount of redundancy required for such codes does not appear excessive and error location may provide an attractive alternative to conventional error detection in decision feedback communications.

The problem of detecting signals in noise is reviewed for the multiple input model, where each of the inputs can contain one of many possible signals. The detection procedure for this model becomes, in general, the testing of multiple hypotheses. Two detection criteria are examined for choosing among multiple hypotheses and it is found that, for both criteria, the decision is based on the likelihood functions for the various signals. Systems for computing likelihood ratios are examined in detail for the multiple input case. A multidimensional matched filter is considered and its relationship to the likelihood ratios is shown. Optimum signals are determined for the two-hypothesis problem.