In recent work, it has been shown that maintaining reliability in analog vector--matrix multipliers can be modeled as the following coding problem. Vectors in $\mathbb{R}^k$ are encoded into codewords of a linear $[n,k,d]$ code $C$ over $\mathbb{R}$. For prescribed positive reals $δ< Δ$, additive errors of magnitude at most $δ$ are tolerable and need no handling, yet outlying errors of magnitude greater than $Δ$ are to be located or detected. The trade-off between the ratio $Δ/δ$ and the number of outlying errors that can be handled is determined by the height profile of $C$; as such, the height profile provides a finer description of the error handling capability of $C$, compared to the minimum distance $d$, which only determines the number of correctable errors. This work contains a further study of the notion of the height profile. Several characterizations of the height profile are presented, thereby yielding methods for computing it. The starting point is formulating this computation as an optimization problem that is solved by a set of linear programs. This, in turn, leads to a combinatorial characterization of the height profile as a maximum (or max--min) over a certain finite set of codewords of $C$. Moreover, this characterization is shown to have a simple geometric interpretation when the columns of the generator matrix of $C$ all have the same $L_2$ norm. Through examples of several code families, it is demonstrated how the results herein can be used to compute the height profile explicitly.

Transformer models represent the cutting edge of Deep Neural Networks (DNNs) and excel in a wide range of machine learning tasks. However, processing these models demands significant computational resources and results in a substantial memory footprint. While In-memory Computing (IMC) offers promise for accelerating Vector-Matrix Multiplications (VMMs) with high computational parallelism and minimal data movement, employing it for other crucial DNN operators remains a formidable task. This challenge is exacerbated by the extensive use of complex activation functions, Softmax, and data-dependent matrix multiplications (DMMuls) within Transformer models. To address this challenge, we introduce a Reconfigurable Analog Computing Engine (RACE) by enhancing Analog Content Addressable Memories (ACAMs) to support broader operations. Based on the RACE, we propose the RACE-IT accelerator (meaning RACE for In-memory Transformers) to enable efficient analog-domain execution of all core operations of Transformer models. Given the flexibility of our proposed RACE in supporting arbitrary computations, RACE-IT is well-suited for adapting to emerging and non-traditional DNN architectures without requiring hardware modifications. We compare RACE-IT with various accelerators. Results show that RACE-IT increases performance by 453× and 15×, and reduces energy by 354× and 122× over the state-of-the-art GPUs and existing Transformer-specific IMC accelerators, respectively.

Differential Varshamov-Tenengolts (D-VT) codes, recently introduced by Nguyen et al. (2024), are q-ary codes that can correct a single deletion (or insertion) error with reduced redundancy compared to the Tenengolts q-ary single deletion correction codes. In this work, we completely determine the sizes of D-VT codes. We clarify the relationship between D-VT codes and Tenengolts codes, which implies a more efficient D-VT decoding algorithm. Finally, we present an alternative characterization of certain D-VT codes in terms of q-ary necklaces.

Nearly perfect covering codes are covering codes that meet the van Wee lower bound on their size. This work studies such codes with covering radius 1. It is shown that the set of these codes can be partitioned into three families, depending on the distribution of the Hamming distances between neighboring codewords. General properties of these code families are presented, including a characterization of their weight and distance distributions. Constructions of codes for each of the families are presented. Finally, extended perfect covering codes are considered. Their punctured codes yield a variety of nearly perfect covering codes.

In this work, we consider the problem of variable packet-error coding, which emerges in network communication scenarios where a source transmits information to a destination through multiple disjoint paths. The objective is to design codes with dynamic error-correcting capabilities that adapt to a varying number of errors. Specifically, we first provide a bound on the rate-distortion trade-off for general variable packet-error coding schemes. Then, we present a construction that uses higherorder MDS codes and provides a variable packet-error coding scheme that achieves a better rate-distortion trade-off compared to known results for general parameter regimes.

Nearly perfect packing codes are those codes that meet the Johnson upper bound on the size of errorcorrecting codes. This bound is an improvement to the sphere-packing bound. A related bound for covering codes is known as the van Wee bound. Codes that meet this bound will be called nearly perfect covering codes. In this paper, such codes with covering radius one will be considered. It will be proved that these codes can be partitioned into three families depending on the smallest distance between neighboring codewords. Some of the codes contained in these families will be completely characterized. Other properties of these codes will be considered too. Construction for codes for each such family will be presented, the weight distribution and the distance distribution of codes from these families are characterized. Finally, extended nearly perfect covering code will be considered and unexpected equivalence classes of codes of the three types will be defined based on the extended codes.

In-memory computing is, in current literature, the most common paradigm used to counteract the Von-Neumann bottleneck, proposing the use of memory elements to define complex input-output relations of the computing kernels. While in classical CMOS computing a similar paradigm can be implemented with look-up tables (LUT), this solution is power and area-hungry. This paper presents the use of Quaternary Content-Addressable Memories (QCAMs), a generalization of the Ternary Content-Addressable Memories (TCAMs), for implementing boolean functions. Content-Addressable Memories can be used as a building block for in-memory processing, using the states of the cells to define a ${\mathbb{B}^{\text{N}}} \to {\mathbb{B}^{\text{M}}}$ function which projects the search word into a new string of bits. The quaternary alphabet allows to represent a more complex function space with respect to the TCAMs while using the same number of cells, enhancing area, power consumption and latency performances achieved when representing arbitrary functions with the CAM hardware. For comparison, it can be demonstrated that QCAMs represent arbitrary Boolean functions with half the number of cells than that would be needed in a standard TCAM implementation, and a ×10 smaller area with respect to SRAM-based LUTs. Along with the table of states and a toy example where the QCAM states are used to define the product among two 2-bit precision real values, this paper presents multiple circuit schemes and encoding schemes for memristor-based QCAMs.

A summing content-addressable memory ($\Sigma$-CAM) is a device which consists of an$\ell\times n$array of cells, where each cell can be programmed to one of two states, 0 or 1. The input to the array is a binary$\ell$-vector, and the output is an integer n-vector whose entries are the Hamming distances between the input vector and the contents of the columns. A summing ternary CAM ($\Sigma$-TCAM) is a variant of a$\Sigma$-CAM where the state/input alphabet is endowed with a third symbol (“don't care”) whose Hamming distance from any symbol is defined to be 0. The purpose of this work is to present coding schemes for on-access correction of errors in both$\Sigma$-CAMs and$\Sigma$-TCAMs. In the case of$\Sigma$-CAMs, our scheme builds upon schemes that have been proposed for discrete vector-matrix multipliers. The adaptation of such schemes to$\Sigma$-TCAMs, however, is more involved and requires a special type of positional binary representation of integer pairs where the representations of the two integers in a pair do not share a 1 in the same position.

Analog content-addressable memories (in short, a-CAMs) have been recently introduced as accelerators for machine-learning tasks, such as tree-based inference or implementation of nonlinear activation functions. The cells in these memories contain nanoscale memristive devices, which may be susceptible to various types of errors, such as manufacturing defects, inaccurate programming of the cells, or drifts in their contents over time.The objective of this work is to develop techniques for overcoming the reliability issues that are caused by such error events. To this end, several coding schemes are presented for the detection of errors in a-CAMs. These schemes consist of an encoding stage, a detection cycle (which is performed periodically), and some minor additions to the hardware. During encoding, redundancy symbols are programmed into a portion of the a-CAM (or, alternatively, are written into an external memory). During each detection cycle, a certain set of input vectors is applied to the a-CAM. The schemes differ in several ways, e.g., in the range of alphabet sizes that they are most suitable for, in the tradeoff that each provides between redundancy and hardware additions, or in the type of errors that they handle (Hamming metric versusL1metric).

Error-correcting codes over the real field are studied which can locate outlying computational errors when performing approximate computing of real vector-matrix multiplication on resistive crossbars. Prior work has concentrated on locating a single outlying error and, in this work, several classes of codes are presented which can handle multiple errors. It is first shown that one of the known constructions, which is based on spherical codes, can in fact handle multiple outlying errors. A second family of codes is then presented with 0–1 paritycheck matrices which are sparse and disjunct; such matrices have been used in other applications as well, especially in combinatorial group testing. In addition, a certain class of the codes that are obtained through this construction is shown to be efficiently decodable. As part of the study of sparse disjunct matrices, this work also contains improved lower and upper bounds on the maximum Hamming weight of the rows in such matrices.

Let [q〉 denote the integer set {0, 1, …, q − 1} and let ${\mathbb{B}} = \left\{ {0,1} \right\}$. The problem of implementing functions $\left[ {\left. q \right\rangle } \right. \to {\mathbb{B}}$ on content-addressable memories (CAMs) is considered. CAMs can be classified by the input alphabet and the state alphabet of their cells; for example, in binary CAMs, those alphabets are both ${\mathbb{B}}$, while in a ternary CAM (TCAM), both alphabets are endowed with a "don’t care" symbol.This work is motivated by recent proposals for using CAMs for fast inference on decision trees. In such learning models, the tree nodes carry out integer comparisons, such as testing equality (x = t ?) or inequality (x ≤ t ?), where x ∈ [q〉 is an input to the node and t ∈ [q〉 is a node parameter. A CAM implementation of such comparisons includes mapping (i.e., encoding) t into internal states of some number n of cells and mapping x into inputs to these cells, with the goal of minimizing n.Such mappings are presented for various comparison families, as well as for the set of all functions $\left[ {\left. q \right\rangle } \right. \to {\mathbb{B}}$, under several scenarios of input and state alphabets of the CAM cells. All those mappings are shown to be optimal in that they attain the smallest possible n for any given q.

In the above article[1],Lemma 2contained an error, which also affects the proof of Theorem 1 therein. Specifically, Theorem 1 holds only when$\sigma = 0$or when$\tau = 0$; otherwise, the “if” part in the theorem requires a stronger condition.

An improved Singleton-type upper bound is presented for the list decoding radius of linear codes, in terms of the code parameters$[n,k,d]$and the list size$L$.$L$-MDS codes are then defined as codes that attain this bound (under a slightly stronger notion of list decodability), with 1-MDS codes corresponding to ordinary linear MDS codes. Several properties of such codes are presented; in particular, it is shown that the 2-MDS property is preserved under duality. Finally, explicit constructions for 2-MDS codes are presented through generalized Reed–Solomon (GRS) codes.

Recent coding techniques are reviewed for protecting nano-scale crossbar architectures against faults and computational errors. Two computational paradigms are considered: exact computation over the integers, and approximate computation over the reals.

New asymptotic upper bounds are presented on the rate of sequences of locally repairable codes (LRCs) with a prescribed relative minimum distance and locality over a finite field$F$. The bounds apply to LRCs in which the recovery functions are linear; in particular, the bounds apply to linear LRCs over$F$. The new bounds are shown to improve on previously published results, especially when the repair groups are disjoint, namely, they form a partition of the set of coordinates.

Bi-modal (respectively, multi-modal) constrained coding refers to an encoding model whereby a user input block can be mapped to two (respectively, multiple) codewords. In current storage applications, such as optical disks, multi-modal coding allows to achieve DC control, in addition to satisfying the runlength limited (RLL) constraint specified by the recording channel. In this work, a study is initiated on bi-modal fixed-length constrained encoders. Necessary and sufficient conditions are presented for the existence of such encoders for a given constraint. It is also shown that under somewhat stronger conditions, one can guarantee a bi-modal encoder with finite decoding delay.

Previous work by the authors on parity-preserving fixed-length constrained encoders is extended to the variable-length case. Parity-preserving variable-length encoders are formally defined, and, to this end, Kraft conditions are developed for the parity-preserving variable-length setting. Then, a necessary and sufficient condition is presented for the existence of deterministic parity-preserving variable-length encoders for a given constraint. Examples are provided that show that there are coding ratios where parity-preserving variable-length encoders exist, while fixed-length encoders do not.

Motivated by coding applications, two enumeration problems are considered: the number of distinct divisors of a degree-m polynomial over F = GF(q), and the number of ways a polynomial can be written as a product of two polynomials of degree at most n over F. For the two problems, bounds are obtained on the maximum number of factorizations, and a characterization is presented for polynomials attaining that maximum. Finally, expressions are presented for the average and the variance of the number of factorizations, for any given m (resp., n).

Previous work by the authors on parity-preserving fixed-length constrained encoders is extended to the variable-length case. Parity-preserving variable-length encoders are formally defined, and a necessary and sufficient condition is presented for the existence of deterministic parity-preserving variable-length encoders for a given constraint. Examples are provided that show that there are coding ratios where parity-preserving variable-length encoders exist, while fixed-length encoders do not.

Coding schemes are presented that provide the ability to locate computational errors above a prescribed threshold while using analog resistive devices for approximate real vector-matrix multiplication. In such devices, the matrix is programmed into the device by setting an array of resistors to have conductances proportional to the respective entries in the matrix. In the coding scheme that is considered in this work, redundancy columns are appended so that each row in the programmed matrix forms a codeword of a prescribed linear code C over the real field; the result of the multiplication of any input real row vector by the matrix is then also a codeword of C. While error values within ±δ in the entries of the result are tolerable (for some prescribed δ > 0), outlying errors, with values outside the range ±Δ (for a prescribed Δ ≥ δ) should be located and corrected. As a design and analysis tool for such a setting, a certain functional is defined for the code C, through which a characterization is obtained for the number of outlying errors that can be handled, as a function of the ratio Δ/δ. Several code constructions are then presented, primarily for the case of single outlying error handling. For this case, the coding problem is shown to be related to certain extremal problems on convex polygons.

A Markov chain approach is applied to determine the capacity of a general class of q-ary ICI-free constrained systems that satisfy an arbitrary count constraint.

Coding schemes are presented that provide the ability to locate computational errors above a prescribed threshold while using analog devices for approximate real vector-matrix multiplication.

It is shown that when Arıkan's n-level polarization transformation is applied to the binary erasure channel, each of the resulting individual 2nsubchannels has a sharp threshold, for sufficiently large n.

A method is provided for constructing upper triangular square matrices over the univariate polynomial ring over a finite field, under certain constraints on the eigenvalues of the matrices. In some cases of interest, the degree of the determinant of such matrices is shown to be the smallest possible. The method is then applied to construct generator polynomial matrices of quasi-cyclic codes for correcting phased burst errors. Finally, an interpolation-based list decoding algorithm is presented for these codes, which, for a wide range of code parameters, is shown to outperform existing list decoding schemes.

Coding schemes are presented that provide the ability to correct and detect computational errors while using dotproduct engines for integer vector-matrix multiplication. Both the L1-metric and the Hamming metric are considered.

Necessary and sufficient conditions are presented for the existence of fixed-rate parity-preserving encoders for a given constraint. It is also shown that under somewhat stronger conditions, the stethering method guarantees an encoder that has finite anticipation.

A decoding algorithm is presented for a rank-metric array codes that are based on diagonal interleaving of maximum-distance separable codes. With respect to this metric, such array codes are known to be optimal when the underlying field is algebraically closed. It is also shown that for any list decoding radius that is smaller than the minimum rank distance, the list size can be bounded from above by an expression that is independent of the field.

A subspace of a finite extension field is called a Sidon space if the product of any two of its elements is unique up to a scalar multiplier from the base field. Sidon spaces were recently introduced by Bachoc et al. as a means to characterize multiplicative properties of subspaces, and yet no explicit constructions were given. In this paper, several constructions of Sidon spaces are provided. In particular, in some of the constructions the relation between k, the dimension of the Sidon space, and n, the dimension of the ambient extension field, is optimal. These constructions are shown to provide cyclic subspace codes, which are useful tools in network coding schemes. To the best of our knowledge, this constitutes the first set of constructions of nontrivial cyclic subspace codes in which the relation between k and n is polynomial, and in particular, linear. As a result, a conjecture by Trautmann et al. regarding the existence of non-trivial cyclic subspace codes is resolved for most parameters, and multi-orbit cyclic subspace codes are attained, whose cardinality is within a constant factor (close to 1/2) from the sphere-packing bound for subspace codes.

It is shown that when Ankan's n-level polarization transformation is applied to the binary erasure channel, each of the resulting individual 2nsubchannels has a sharp threshold, for sufficiently large n.

A decoding algorithm is presented for rank-metric array codes that are based on diagonal interleaving of MDS codes. W.r.t. this metric, such array codes are known to be optimal when the underlying field is algebraically closed. It is also shown that for any list decoding radius that is smaller than the minimum rank distance, the list size can be bounded from above by an expression that is independent of the field.

An explicit construction of an infinite family of cyclic codes is presented which, over GF(4) (resp., GF(8)), have approximately 8/9 (resp., 48/49) the redundancy of BCH codes of the same minimum distance and length. As such, the new codes are the best codes currently known in a regime where the minimum distance is fixed and the code length goes to infinity.

Nearly tight lower and upper bounds on the capacity of generalized Ising channels are presented. For the case where feedback is allowed, a closed-form expression for the capacity is found for channel error probability p ∈ [0, p0], where p0 ≈ 0.398324. A near-capacity-achieving family of encoders is presented for the values p ∈ [0, p0]. Two lower bounds on that capacity for larger values of p are presented, one of which is tight on the interval [p0, 0.5].

An explicit construction of an infinite family of cyclic codes is presented which, over GF(4) (resp., GF(8)), have approximately 8/9 (resp., 48/49) the redundancy of BCH codes of the same minimum distance and length. As such, the new codes are the best codes currently known in a regime where the minimum distance is fixed and the code length goes to infinity.

A method is provided for constructing upper-triangular square matrices over the univariate polynomial ring over a finite field, under certain constraints on the eigenvalues of the matrices. In some cases of interest, the degree of the determinant of such matrices is shown to be the smallest possible. The method is then applied to construct generator polynomial matrices of quasi-cyclic codes with a prescribed designed minimum distance.

Nearly tight lower and upper bounds on the capacity of generalized Ising channels are presented. For the case where feedback is allowed, a closed-form expression for the capacity is found for channel error probability p ∈ [0, p0], where p0≈ 0.398324. Two lower bounds on that capacity for larger values of p are presented.

An interpolation-based list decoding algorithm for ℓ-quasi-cyclic codes over finite fields is developed and its guaranteed decoding radius for ℓ-phased burst errors is proven. It is also shown that for this error model and for certain parameter ranges, this new approach is advantageous over existing schemes.

Improved lower and upper bounds on the size and the rate of grain-correcting codes are presented. The lower bound is Gilbert-Varshamov-like combined with a construction by Gabrys et al., and it improves on the previously best known lower bounds on the asymptotic rate of ⌈τn⌉-grain-correcting codes of length n on the interval [0, 0.0668]. One of the two newly presented upper bounds improves on the best known upper bounds on the asymptotic rate of ⌈τn⌉-grain-correcting codes of length n on the interval τ ∈ (0, 1/8] and meets the lower bound of 1/2 for τ ≥ 1/8. Moreover, in a nonasymptotic regime, both upper bounds improve on the previously best known results on the largest size of t-grain-correcting codes of length n, for certain values of n and t. Constructions of 1-grain-correcting codes based on a partitioning technique are presented for lengths up to 18. Finally, a lower bound of 1/2 log2n on the minimum redundancy of ∞-grain-detecting codes of length n is presented.

We initiate a study of constrained codes in which any codeword can be transformed into any other codeword by a sequence of single symbol changes such that the intermediate words (after each symbol change) all satisfy the underlying constraint. We shall refer to a set of constrained words with this property as being Hamming connected. Hamming connected constrained codes might be useful for encoding data in storage media when a constraint must be met upon writing data, as might be the case in some emerging storage technologies. The stated property would permit overwriting encoded data without violating the constraint during intermediate writes. We study the Hamming connectedness of (d, k)-run-length limited constraints and a few other special cases. We also consider the decidability of Hamming connectedness for finite memory constraints.

New upper bounds on the size and the rate of grain-correcting codes are presented. The new upper bound on the size of t-grain-correcting codes of length n improves on the best known upper bounds for certain values of n and t, whereas the new upper bound on the asymptotic rate of [τn]-grain-correcting codes of length n improves on the previously known upper bounds on the interval τ ∈ (0, ⅛]. A lower bound of 1/2 log2n on the minimum redundancy of ∞-grain-detecting codes of length n is presented.

It is shown that interleaved Reed–Solomon codes can be list-decoded for burst errors while attaining the generalized Reiger bound for list decoding. A respective decoding algorithm is presented that is (significantly) more efficient than a burst list decoder for a noninterleaved Reed–Solomon code with comparable parameters. Finally, it is shown through counterexamples that unlike the special case of Reed–Solomon codes, interleaving does not always preserve the list decoding properties of the constituent code.

We design low-complexity error correction coding schemes for channels that introduce different types of errors and erasures: on the one hand, the proposed schemes can successfully deal with symbol errors and erasures, and, on the other hand, they can also successfully handle phased burst errors and erasures.

Bounds on the rates of grain-correcting codes are presented. The lower bounds are Gilbert-Varshamov-like ones, whereas the upper bounds improve on the previously known result by Mazumdar Constructions of t-grain-correcting codes of length n for certain values of n and t are discussed. Finally, an infinite family of codes of rate approaching 1 that can detect an arbitrary number of grain errors is shown to exist.

We present a framework based on covering codes over the set of binary n-words for coding data into n × n binary arrays with a prescribed upper bound on the Hamming weight (i.e., number of 1's) in each row and column. We obtain previously presented schemes for the case when the upper bound is n/2 as special cases of this framework and we study also another potentially practically relevant specialization when the underlying covering code is the first-order Reed-Muller code. Like the previous schemes for the n/2 case, the proposed framework and schemes may have applications in improving the performance of a next-generation memory based on programmable resistive devices arranged in a crossbar architecture.

We design low-complexity error correction coding schemes for channels that introduce different types of errors and erasures: on the one hand, the proposed schemes can successfully deal with symbol errors and erasures, and, on the other hand, they can also successfully handle phased burst errors and erasures.

It is shown that interleaved Reed-Solomon codes can be list-decoded for burst errors while attaining the generalized Reiger bound for list decoding.

We define a g-ary antipodal matching to be a perfect matching in the bipartite graph with vertices corresponding to words of length ℓ over the integer alphabet Q = {0, 1, ..., q -1}, wherein the left and right vertices are those with respective component sums greater and smaller than ℓ(q -1)/2, and wherein two vertices are connected by an edge if one of the corresponding words dominates the other. We present two different constructions of efficiently computable g-ary antipodal matchings. We then show how such matchings can be used for encoding arbitrary data into n × n arrays over the alphabet Q all of whose row and column sums are at most n(q -1)/2. Such encoders might be useful for mitigating parasitic currents in a next generation memory technology based on crossbar arrays of resistive devices.

Let ${\mathcal{A}}_n$ be the set of all $n \times n$ binary matrices in which the number of $1$'s in each row and column is at most $n/2$. We show that $|{\mathcal{A}}_n| = 2^{n^2 - \rho n + \delta \sqrt{n}} \cdot n^{O(1)}$, for a constant $\rho \approx 1.42515$, and $\delta = \delta(n) \approx 1.46016$ for even $n$ and $0$ otherwise.

Two low complexity coding techniques are described for mapping arbitrary data to and from$ m\times n $binary arrays in which the Hamming weight of each row (respectively, column) is at most$ n/2 $(respectively,$ m/2 $). One technique is based on flipping rows and columns of an arbitrary binary array until the Hamming weight constraint is satisfied in all rows and columns, and the other is based on a certain explicitly constructed “antipodal” matching between layers of the Boolean lattice. Both codes have a redundancy of roughly$ m{+}n $and may have applications in next generation resistive memory technologies.

Consider the set Anof all n×n binary matrices in which the number of 1's in each row and column is at most n/2. We show that the redundancy, n2- log2|An|, of this set equals ρn + o(n), for a constant ρ ≈ 1.42515.

We describe two low complexity coding techniques for mapping arbitrary data to and from n × n binary arrays in which the Hamming weight of each row and column is at most n/2. One technique is based on flipping rows and columns of an arbitrary binary array until the Hamming weight constraint is satisfied in all rows and columns, and the other is based on a certain explicitly constructed “antipodal” matching between layers of the Boolean lattice. Both codes have a redundancy of roughly 2n and may have applications in next generation resistive memory technologies.

Bounds on the rate of grain-correcting codes are presented. The lower bounds are Gilbert-Varshamov-like ones, whereas the upper bounds improve on the previously known result by Mazumdar et al.. Constructions of t-grain-correcting codes of length n for certain values of n and t are discussed.

A 2-D version of the classical maximum-likelihood sequence detection (MLSD) problem is considered for a binary antipodal signal that is corrupted by linear intersymbol interference (ISI) and then passed through a memoryless channel. For 1-D signals and fixed ISI, this detection problem is well-known to be solved using the Viterbi algorithm in time complexity that is linear in the sequence length. It is shown here that, in contrast, the 2-D MLSD problem is NP hard. Specifically, a decision formulation of the problem is shown to be NP complete for a particular 2-D ISI cascaded with either of two memoryless channels: one involving errors and erasures and the other corresponding to additive white Gaussian noise. The proof for the latter case is obtained through a reduction from a still NP complete restricted version of the former. These results are applied to proving the NP completeness of multi user detection under a Toeplitz constraint-a problem known to be equivalent to a variant of 1-D MLSD with growing ISI. This proves a conjecture posed by Verdú in 1989.

The capacity of 1-D constraints is given by the entropy of a corresponding stationary maxentropic Markov chain. Namely, the entropy is maximized over a set of probability distributions, which is defined by some linear equalities and inequalities. In this paper, certain aspects of this characterization are extended to 2-D constraints. The result is a method for calculating an upper bound on the capacity of 2-D constraints. The key steps are as follows: The maxentropic stationary probability distribution on square configurations is considered; set of linear equalities and inequalities is derived from this stationarity; the result is then a convex program, which can be easily solved numerically. Our method improves upon previous upper bounds for the capacity of the 2-D “no isolated bits” constraint, as well as certain 2-D RLL constraints.

A new fixed-rate tiling-based coding scheme is presented for two-dimensional (2-D) constraints. The new scheme is shown to improve on the best known rates of formerly published fixed-rate encoders for certain constraints, such as the “no isolated bits” constraint and several 2-D runlength limited (RLL) constraints. Methods of efficient implementation of the suggested scheme are discussed.

A new variable-rate coding technique is presented for two-dimensional (2-D) constraints. For certain constraints, such as the(0, 2)-runlength-limited (RLL) and(3,¿)-RLL constraints, the technique is shown to improve on previously published lower bounds on the capacity of the constraint.

A method for bounding the rate of bit-stuffing encoders for 2-D constraints is presented. Instead of considering the original encoder, we consider a related one which is quasi-stationary. We use the quasi-stationary property in order to formulate linear requirements that must hold on the probabilities of the constrained arrays that are generated by the encoder. These requirements are used as part of a linear program. The minimum and maximum of the linear program bound the rate of the encoder from below and from above, respectively. A lower bound on the rate of an encoder is also a lower bound on the capacity of the corresponding constraint. For some constraints, our results lead to tighter lower bounds than what was previously known.

Ternary content-addressable memory (TCAM) devices are increasingly used for performing high-speed packet classification. A TCAM consists of an associative memory that compares a search key in parallel against all entries. TCAMs may suffer from error events that cause ternary cells to change their value to any symbol in the ternary alphabet {”0”,“1”,“*”}. Due to their parallel access feature, standard error detection schemes are not directly applicable to TCAMs; an additional difficulty is posed by the special semantic of the “*” symbol. This paper introduces PEDS, a novel parallel error detection scheme that locates the erroneous entries in a TCAM device. PEDS is based on applying an error-detecting code to each TCAM entry and utilizing the parallel capabilities of the TCAM by simultaneously checking the correctness of multiple TCAM entries. A key feature of PEDS is that the number of TCAM lookup operations required to locate all errors depends on the number of symbols per entry in a manner that is typically orders of magnitude smaller than the number of TCAM entries. For large TCAM devices, a specific instance of PEDS requires only 200 lookups for 100-symbol entries, while a naive approach may need hundreds of thousands of lookups. PEDS allows flexible and dynamic selection of tradeoff points between robustness, space complexity, and number of lookups.

Ternary content-addressable memory (TCAM) devices are increasingly used for performing high-speed packet classification. A TCAM consists of an associative memory that compares a search key in parallel against all entries. TCAMs may suffer from error events that cause ternary cells to change their value to any symbol in the ternary alphabet "0","1","*". Due to their parallel access feature, standard error detection schemes are not directly applicable to TCAMs; an additional difficulty is posed by the special semantic of the "*" symbol. This paper introduces PEDS, a novel parallel error detection scheme that locates the erroneous entries in a TCAM device. PEDS is based on applying an error-detection code to each TCAM entry, and utilizing the parallel capabilities of the TCAM, by simultaneously checking the correctness of multiple TCAM entries. A key feature of PEDS is that the number of TCAM lookup operations required to locate all errors depends on the number of symbols per entry rather than the (orders-of-magnitude larger) number of TCAM entries. For large TCAM devices, a specific instance of PEDS requires only 200 lookups for 100-symbol entries, while a naive approach may need hundreds of thousands lookups. PEDS allows flexible and dynamic selection of trade-off points between robustness, space complexity, and number of lookups.

Let n be an even positive integer and F be the field GF(2). A word in Fnis called balanced if its Hamming weight is n/2. A subset C ¿ Fnis called a balancing set if for every word y ¿ Fnthere is a word x ¿ C such that y + x is balanced. It is shown that most linear subspaces of Fnof dimension slightly larger than 3/2 log2n are balancing sets. An application of linear balancing sets is presented for designing efficient error-correcting coding schemes in which the codewords are balanced.

We show how to improve on the technique of approximate enumerative coding for a family of two-dimensional constraints by encoding according to lower bounds based on the worst-case behavior of certain ratios of matrix products. For the case of the two-dimensional (d = 2;infin) run-length limited (RLL) constraint, the improved approach yields a lower bound of 0.4453 on the capacity of the constraint.

The capacity of 1-D constraints is given by the entropy of a corresponding stationary maxentropic Markov chain. Namely, the entropy is maximized over a set of probability distributions, which is defined by some linear requirements. In this paper, certain aspects of this characterization are extended to 2-D constraints. The result is a method for calculating an upper bound on the capacity of 2-D constraints. The key steps are: The maxentropic stationary probability distribution on square configurations is considered. A set of linear equalities and inequalities is derived from this stationarity. The result is a concave program, which can be easily solved numerically. Our method improves upon previous upper bounds for the capacity of the 2-D ¿no independent bits¿ constraint, as well as certain 2-D RLL constraints.

For a linear block code C, its stopping redundancy is defined as the smallest number of check nodes in a Tanner graph for C, such that there exist no stopping sets of size smaller than the minimum distance of C. Schwartz and Vardy conjectured that the stopping redundancy of a maximum-distance separable (MDS) code should only depend on its length and minimum distance. We define the (n, t)-single-exclusion number, S(n, t) as the smallest number of i-subsets of an n-set, such that for each i-subset of the n-set, i =1,... ,t + 1, there exists a i-subset that contains all but one element of the i-subset. New upper bounds on the single-exclusion number are obtained via probabilistic methods, recurrent inequalities, as well as explicit constructions. The new bounds are used to better understand the stopping redundancy of MDS codes. In particular, it is shown that for [n, k = n - d + 1, d] MDS codes, as n rarr infin , the stopping redundancy is asymptotic to S(n, d - 2), if d = o(radic(n)), or if k = o(radic(n)), k rarr infin, thus giving partial confirmation of the Schwartz-Vardy conjecture in the asymptotic sense.

A generalization of the Reiger bound is presented for the list decoding of burst errors. It is then shown that Reed–Solomon codes attain this bound.

A constant-rate encoder–decoder pair is presented for a fairly large family of two-dimensional (2-D) constraints. Encoding and decoding is done in a row-by-row manner, and is sliding-block decodable.

A generalization of the Reiger bound is presented for the list decoding of burst errors. It is then shown that Reed-Solomon codes attain this bound.

A new variable-rate coding technique is presented for two-dimensional constraints. For certain constraints, such as the (0, 2)-RLL, (2, infin)-RLL, and the "no isolated bits" (n.i.b.) constraints, the technique is shown to improve on previously- published lower bounds on the capacity of the constraint.

A method for bounding the rate of bit-stuffing encoders for 2-D constraints is presented. Instead of considering the original encoder, we consider a related one which is quasi-stationary. We use the quasi-stationary property in order to formulate linear requirements that must hold on the probabilities of the constrained arrays that are generated by the encoder. These requirements are used as part of a linear program. The minimum and maximum of the linear program bound the rate of the encoder from below and from above, respectively. A lower bound on the rate of an encoder is also a lower bound on the capacity of the corresponding constraint. For some constraints, our results lead to tighter lower bounds than what was previously known.

The Gale-Berlekamp (in short, GB) code is the dual code of the binary product code in which the horizontal and vertical constituent codes are both the parity code. It is shown that the problem of deciding whether there is a codeword of the GB code within a prescribed distance from a given received word, is NP-complete. The problem remains hard (in a well-defined sense) even if the decoder is allowed unlimited preprocessing that depends only on the code length. While the intractability of maximum-likelihood decoding (MLD) for specific codes has already been shown by Bruck and Naor, Lobstein, and Guruswami and Vardy, the result herein seems to be the first that shows hardness for a "natural" code (in particular, without any tailoring of the definition or the parameters of the code to suit the hardness proof). In contrast, it is also shown that, with respect to any memoryless binary-symmetric channel (BSC) with crossover probability less than 1/2, MLD can be implemented in linear time for all error events except for a portion that occurs with vanishing probability.

New bounds on single-exclusion numbers are obtained via probabilistic arguments, recurrent relations, as well as explicit constructions. The new bounds are used to better understand the stopping redundancy of MDS codes. In particular, it is shown that for any fixed k, the stopping redundancy of a linear [n, k] MDS code is between 1/k+1(kn) and (1 + o(1))1/k (kn).

We present a general method for obtaining lower bounds on the capacities of two-dimensional (2-D) constraints. We apply our method to the 2-D (d=2, infin) run-length limited (RLL) constraint and obtain the best known lower bound, .4423, on the capacity of this constraint. Our lower bounds are shown to be achievable by a fixed-rate, polynomial-complexity encoding-decoding algorithm based on enumerative coding with approximate counts.

The Gale-Berlekamp (in short, GB) code is the dual code of the binary product code in which the horizontal and vertical constituent codes are both the parity code. It is shown that the problem of deciding whether there is a codeword of the GB code within a prescribed distance from a given received word, is NP-complete. The problem remains hard (in a well-defined sense) even if the decoder is allowed unlimited preprocessing that depends only on the code length. While the intractability of maximum-likelihood decoding for specific codes has already been shown by Bruck and Naor and Lobstein, the result herein seems to be the first that shows hardness for familiar (or "natural") codes. In contrast, it is also shown that, with respect to any memoryless binary symmetric channel with crossover probability less than 1/2, maximum-likelihood decoding can be implemented in linear time for all error events except for a portion that occurs with vanishing probability.

New lower bounds are presented on the second moment of the distance distribution of binary codes, in terms of the first moment of the distribution. These bounds are used to obtain upper bounds on the size of codes whose maximum distance is close to their minimum distance. It is then demonstrated how such bounds can be applied to bound from below the smallest attainable ratio between the maximum distance and the minimum distance of codes. Finally, counterparts of the bounds are derived for the special case of constant-weight codes.

A constant-rate encoder-decoder pair is presented for a fairly large family of two-dimensional (2-D) constraints. Encoding and decoding is done in a row-by-row manner, and is sliding-block decodable. Essentially, the 2-D constraint is turned into a set of independent and relatively simple one-dimensional (1-D) constraints; this is done by dividing the array into fixed-width vertical strips. Each row in the strip is seen as a symbol, and a graph presentation of the respective 1-D constraint is constructed. The maxentropic stationary Markov chain on this graph is next considered: a perturbed version of the corresponding probability distribution on the edges of the graph is used in order to build an encoder which operates in parallel on the strips. This perturbation is found by means of a network flow, with upper and lower bounds on the flow through the edges. A key part of the encoder is an enumerative coder for constant-weight binary words. A fast realization of this coder is shown, using floating-point arithmetic

Let F be a finite field and b be a positive integer. A construction is presented of codes over the alphabet F/sup b/ with the following three properties: i) the codes are maximum-distance separable (MDS) over F/sup b/, ii) they are linear over F, and iii) they have systematic generator and parity-check matrices over F with the smallest possible number of nonzero entries. Furthermore, for the case F=GF(2), the construction is the longest possible among all codes that satisfy properties i)-iii).

A construction of expander codes is presented with the following three properties: i) the codes lie close to the Singleton bound, ii) they can be encoded in time complexity that is linear in their code length, and iii) they have a linear-time bounded-distance decoder. By using a version of the decoder that corrects also erasures, the codes can replace maximum-distance separable (MDS) outer codes in concatenated constructions, thus resulting in linear-time encodable and decodable codes that approach the Zyablov bound or the capacity of memoryless channels. The presented construction improves on an earlier result by Guruswami and Indyk in that any rate and relative minimum distance that lies below the Singleton bound is attainable for a significantly smaller alphabet size

Lower bounds are presented on the second moment of the distance distribution of binary codes. These bounds are used to obtain upper bounds on the size of codes whose maximum distance is close to their minimum distance. It is shown how such results can be applied to bound from below the smallest attainable ratio between the maximum distance and the minimum distance of codes. Improved bounds are then provided for the special case of constant-weight codes

We consider codes consisting of arrays over an alphabet F, in which certain intersecting subsets of n/spl times/m coordinates are required to form codewords of length n in prescribed codes over the alphabet F/sup m/. Two specific cases are studied. In the first case, referred to as a singly-intersecting coding scheme, the user data is mapped into n/spl times/(2m-1) arrays over an alphabet F, such that the n/spl times/m subarray that consists of the left (respectively, right) m columns forms a codeword of a prescribed code of length n over F/sup m/; in particular, the center column is shared by the left and right subarrays. Bounds are obtained on the achievable redundancy region of singly-intersecting coding schemes, and constructions are presented that approach-and sometimes meet-these bounds. It is shown that singly-intersecting coding schemes can be applied in a certain model of broadcast channels to guarantee reliable communication. The second setting, referred to as a fully-intersecting coding scheme, maps the user data into n/spl times/m/spl times/m three-dimensional arrays in which parallel n/spl times/m subarrays are all codewords of the same prescribed code over F/sup m/. Bounds and constructions are presented for these codes, with the analysis based on representing the n/spl times/m/spl times/m arrays as vectors over certain algebras on m/spl times/m matrices.

A construction of expander codes is presented with the following three properties: (i) the codes lie close to the Singleton bound, (ii) they can be encoded in time complexity that is linear in their code length, and (iii) they have a linear-time bounded-distance decoder. By using a version of the decoder that corrects also erasures, the codes can replace MDS outer codes in concatenated constructions, thus resulting in linear-time encodable and decodable codes that approach the Zyablov bound or the capacity of memoryless channels. The presented construction improves on an earlier result by Guruswami and Indyk in that any rate and relative minimum distance that lies below the Singleton bound is attainable for a significantly smaller alphabet size.

The problem of constructing three-dimensional, ntimesmtimesm arrays over GF(q) is studied, where each ntimesm subarray in one direction contains a codeword of a code Copf1over GF(qm), while each ntimesm subarray in the perpendicular direction contains a codeword of a code Copf2over GF(qm)

Let G be a t-uniform s-regular linear hypergraph with r vertices. It is shown that the number of independent sets $\IS(\hgraph)$ in $\hgraph$ satisfies \[ \log_2 \IS(\hgraph) \le \frac{r}{t} \left( 1 + O \biggl( \frac{\log^2(ts)}{s} \biggr) \right) . \] This leads to an improvement of a previous bound by Alon obtained for t = 2 (i.e., for regular ordinary graphs). It is also shown that for the Hamming graph $\Hamming(n,q)$ (with vertices consisting of all n-tuples over an alphabet of size q and edges connecting pairs of vertices with Hamming distance 1), \[ \frac{\log_2 \IS(\Hamming(n,q))}{q^n} = \frac{1}{q} + O \biggl(\frac{\log^2 (q n)}{q n} \biggr). \] The latter result is then applied to show that the Shannon capacity of the n-dimensional $(d,\infty)$-runlength-limited (RLL) constraint converges to 1/(d+1) as n goes to infinity.

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.

Recently, G. Zemor (see IEEE Trans. Inf. Theory, vol.47, p.835-7, 2001) proposed an improvement on the Sipser-Spielman analysis of expander codes (Sipser, M. and Spielman, D.A., IEEE Trans. Inf. Theory, vol.42 , p.1710-22, 1996) and presented a linear-time iterative decoder that can correct a number of errors up to approximately 1/4 the known lower bound on the minimum distance of the code. We propose an improvement on Zemor's decoder for F=GF(2), with the number of correctable errors becoming close to half the lower bound on the minimum distance. The improvement is obtained by inserting into the decoding algorithm features akin to generalized minimum distance decoding of concatenated codes.

Techniques are presented for computing upper and lower bounds on the number of errors that can be corrected by list decoders for general block codes and, specifically, for Reed--Solomon (RS) codes. The list decoder of Guruswami and Sudan implies such a lower bound (referred to here as the GS bound) for RS codes. It is shown that this lower bound, given by means of the code's length, the minimum Hamming distance, and the maximal allowed list size, in fact applies to all block codes. Ranges of code parameters are identified where the GS bound is tight for worst-case RS codes, in which case the list decoder of Guruswami and Sudan provably corrects the largest possible number of errors. On the other hand, ranges of parameters are provided for which the GS lower bound can be strictly improved. In some cases the improvement applies to all block codes with a given minimum Hamming distance, while in others it applies only to RS codes.

A parallel constrained coding scheme is considered where p-blocks of raw data are encoded simultaneously into q tracks such that the contents of each track belong to a given constraint S. It is shown that as q increases, there are parallel block-decodable encoders for S whose coding ratio p/q converges to the capacity of S. Examples are provided where parallel coding allows block-decodable encoders, while conventional coding, at the same rate, does not. Parallel encoders are then applied as building blocks in the construction of block-decodable encoders for certain families of two-dimensional constraints.

Consider a (d/sub 1/, k/sub 1/)-runlength-limited (RLL) constraint that is contained in a (d/sub 2/, k/sub 2/)-RLL constraint, where k/sub 1//spl ges/2d/sub 1/ and d/sub 2/>0, and fix a codeword length q>k/sub 2/. It is shown that whenever there exist block-decodable encoders with codeword length q for those two constraints, there exist such encoders where one is a subgraph of the other: furthermore, both encoders can be decoded by essentially the same decoder. Specifically, a (d/sub 1/, k/sub 1/)-RLL constrained word is decoded by first using a block decoder of the (d/sub 2/, k/sub 2/)-RLL encoder, and then applying a certain function to the output of that decoder.

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.

An input-constrained channel S is defined as the set of words generated by a finite labeled directed graph. It is shown that every finite-state encoder with finite anticipation (i.e., with finite decoding delay) for S can be obtained through state-splitting rounds applied to some deterministic graph presentation of S, followed by a reduction of equivalent states. Furthermore, each splitting round can be restricted to follow a certain prescribed structure. This result, in turn, provides a necessary and sufficient condition on the existence of finite-state encoders for S with a given rate p:q and a given anticipation a. A second condition is derived on the existence of such encoders; this condition is only necessary, but it applies to every deterministic graph presentation of S. Based on these two conditions, lower bounds are derived on the anticipation of finite-state encoders. Those lower bounds improve on previously known bounds and, in particular, they are shown to be tight for the common rates used for the (1,7)-runlength-limited (RLL) and (2,7)-RLL constraints.

Constructions are presented of finite-state encoders for certain (d,k) runlength-limited (RLL) constraints with direct current control. In particular, an example is provided for a rate 8:16 encoder for the (2,10)-RLL constraint that requires no look-ahead in decoding, thus, performing favorably compared to the EFMPlus code used in the DVD standard.

A method is presented for designing lossless sliding-block compression schemes that map constrained sequences onto unconstrained ones. The new compression scheme is incorporated into a coding technique for noisy constrained channels, which has applications to magnetic and optical storage. As suggested previously by Immink (see ibid., vol.43, p.1389-99, 1997), the use of a lossless compression code can improve the performance of a modified concatenation scheme where the positions of the error-correcting code and constrained code are reversed (primarily in order to eliminate error propagation due to the constrained code). Examples are presented that demonstrate the advantage of using sliding-block compression over block compression in a noisy constrained setting.

An input-constrained channel, or simply a constraint, is a set S of words that is generated by a finite labeled directed graph. An encoder for S maps, in a lossless manner, sequences of unconstrained input blocks into sequences of channel blocks, the latter sequences being words of S. In most applications, the encoders are finite-state machines and, thus, presented by state diagrams. In the special case where the state diagram of the encoder is (output) deterministic, only the current encoder state and the current channel block are needed for the decoding of the current input block. In this work, the problem of designing coding schemes that can serve two constraints simultaneously is considered. Specifically, given two constraints S/sub 1/ and S/sub 2/ such that S/sub 1//spl sube/S/sub 2/ and two described rates, conditions are provided for the existence of respective deterministic finite-state encoders /spl epsi//sub 1/ and /spl epsi//sub 2/, at the given rates, such that (the state diagram of) /spl epsi//sub 1/ is a subgraph of /spl epsi//sub 2/ Such encoders are referred to as nested encoders. The provided conditions are also constructive in that they imply an algorithm for finding such encoders when they exist. The nesting structure allows to decode /spl epsi//sub 1/ while using the decoder of /spl epsi//sub 2/. Developments in optical recording suggest a potential application that can take a significant advantage of nested encoders.

For a rational /spl alpha//spl isin/(0,1), let /spl Ascr//sub n/spl times/m,/spl alpha// be the set of binary n/spl times/m arrays in which each row has Hamming weight /spl alpha/m and each column has Hamming weight /spl alpha/n, where /spl alpha/m and /spl alpha/n are integers. (The special case of two-dimensional balanced arrays corresponds to /spl alpha/=1/2 and even values for n and m.) The redundancy of /spl Ascr//sub n/spl times/m,/spl alpha// is defined by /spl rho//sub n/spl times/m,/spl alpha//=nmH(/spl alpha/)-log/sub 2/|/spl Ascr//sub n/spl times/m,/spl alpha//| where H(x)=-xlog/sub 2/x-(1-x)log/sub 2/(1-x). Bounds on /spl rho//sub n/spl times/m,/spl alpha// are obtained in terms of the redundancies of the sets /spl Ascr//sub /spl Lscr/,/spl alpha// of all binary /spl Lscr/-vectors with Hamming weight /spl alpha//spl Lscr/, /spl Lscr//spl isin/{n,m}. Specifically, it is shown that /spl rho//sub n/spl times/m,/spl alpha///spl les/n/spl rho//sub m,/spl alpha//+m/spl rho//sub n,/spl alpha// where /spl rho//sub /spl Lscr/,/spl alpha//=/spl Lscr/H(/spl alpha/)-log/sub 2/|/spl Ascr//sub /spl Lscr/,/spl alpha//| and that this bound is tight up to an additive term O(n+log m). A polynomial-time coding algorithm is presented that maps unconstrained input sequences into /spl Ascr//sub n/spl times/m,/spl alpha// at a rate H(/spl alpha/)-(/spl rho//sub m,/spl alpha///m).

A list decoding algorithm is presented for [n,k] Reed-Solomon (RS) codes over GF(q), which is capable of correcting more than [(n-k)/2] errors. Based on a previous work of Sudan (see J. Compl., vol.13, p.180-93, 1997), an extended key equation (EKE) is derived for RS codes, which reduces to the classical key equation when the number of errors is limited to [(n-k)/2]. Generalizing Massey's (1969) algorithm that finds the shortest recurrence that generates a given sequence, an algorithm is obtained for solving the EKE in time complexity O(l/spl middot/(n-k)/sup 2/), where l is a design parameter, typically a small constant, which s an upper bound on the size of the list of decoded codewords. (The case l=1 corresponds to classical decoding of up to [(n-k)/2] errors where the decoding ends with at most one codeword.) This improves on the time complexity O(n/sup 3/) needed for solving the equations of Sudan's algorithm by a naive Gaussian elimination. The polynomials found by solving the EKE are then used for reconstructing the codewords in time complexity O((llog/sup 2/l)k(n+llogq)) using root-finders of degree-l univariate polynomials.

Let F/sub q/ denote the finite field GF(q) and let h be a positive integer. MDS (maximum distance separable) codes over the symbol alphabet F/sub q//sup b/ are considered that are linear over F/sub q/ and have sparse ("low-density") parity-check and generator matrices over F/sub q/ that are systematic over F/sub q//sup b/. Lower bounds are presented on the number of nonzero elements in any systematic parity-check or generator matrix of an F/sub q/-linear MDS code over F/sub q//sup b/, along with upper bounds on the length of any MDS code that attains those lower bounds. A construction is presented that achieves those bounds for certain redundancy values. The building block of the construction is a set of sparse nonsingular matrices over F/sub q/ whose pairwise differences are also nonsingular. Bounds and constructions are presented also for the case where the systematic condition on the parity-check and generator matrices is relaxed to be over F/sub q/, rather than over F/sub q//sup b/.

Arikan and Merhav (1998) studied the problem of guessing a random vector X within distortion D, and characterized the best attainable exponent E(D,/spl rho/) of the /spl rho/th moment of the number of required guesses G(X) until the guessing error falls below D. We extend these results to a multistage, hierarchical guessing model, which allows for a faster search for a codeword vector at the encoder of a rate-distortion codebook. In the two-stage case of this model, if the target distortion level is D/sub 2/, the guesser first makes guesses with respect to (a higher) distortion level D/sub 1/, and then, upon his/her first success, directs the subsequent guesses to distortion D/sub 2/. As in the above-mentioned earlier paper, we provide a single-letter characterization of the best attainable guessing exponent, which relies heavily on well-known results on the successive refinement problem. We also relate this guessing exponent function to the source-coding error exponent function of the two-step coding process.

Efficient encoding algorithms are presented for two types of constraints on two-dimensional binary arrays. The first constraint considered is that of t-conservative arrays, where each row and each column has at least t transitions of the form '0'/spl rarr/'1' or '1'/spl rarr/'0.' The second constraint is that of two-dimensional DC-free arrays, where in each row and each column the number of '0's equals the number of '1's.

A feedback vertex set of an undirected graph is a subset of vertices that intersects with the vertex set of each cycle in the graph. Given an undirected graph G with n vertices and weights on its vertices, polynomial-time algorithms are provided for approximating the problem of finding a feedback vertex set of G with smallest weight. When the weights of all vertices in G are equal, the performance ratio attained by these algorithms is 4-(2/n). This improves a previous algorithm which achieved an approximation factor of $O(\sqrt{\log n})$ for this case. For general vertex weights, the performance ratio becomes $\min\{2\Delta^2, 4 \log_2 n\}$ where $\Delta$ denotes the maximum degree in G. For the special case of planar graphs this ratio is reduced to 10. An interesting special case of weighted graphs where a performance ratio of 4-(2/n) is achieved is the one where a prescribed subset of the vertices, so-called blackout vertices, is not allowed to participate in any feedback vertex set. It is shown how these algorithms can improve the search performance for constraint satisfaction problems. An application in the area of Bayesian inference of graphs with blackout vertices is also presented.

In a typical burst error correction application of a product code of n/sub v//spl times/n/sub h/ arrays, one uses an [n/sub h/, n/sub h/-r/sub h/] code C/sub h/ that detects corrupted rows, and an [n/sub v/, n/sub v/-r/sub v/] code C/sub v/ that is applied to the columns while regarding the detected corrupted rows as erasures. Although this conventional product code scheme offers very good error protection, it contains excessive redundancy, due to the fact that the code C/sub h/ provides the code C/sub v/ with information on many error patterns that exceed the correction capability of C/sub v/. A coding scheme is proposed in which this excess redundancy is eliminated, resulting in significant savings in the overall redundancy compared to the conventional case, while offering the same error protection. The redundancy of the proposed scheme is n/sub h/r/sub v/+r/sub h/(lnr/sub v/+O(1))+r/sub v/, where the parameters r/sub h/ and r/sub v/ are close in value to their counterparts in the conventional case, which has redundancy n/sub h/r/sub v/+n/sub v/r/sub h/-r/sub h/r/sub v/. In particular, when the codes C/sub h/ and C/sub v/ have the same rate and r/sub h//spl Lt/n/sub h/, the redundancy of the proposed scheme is close to one-half of that of the conventional product code counterpart. Variants of the scheme are presented for channels that are mostly bursty, and for channels with a combination of random errors and burst errors.

An efficient algorithm is presented for encoding unconstrained information sequences into a third-order spectral-null code of length n and redundancy 9log/sub 2/ n+O(log log n). The encoding can be implemented using O(n) integer additions and O(nlog n) counter increments.

We study the computational difficulty of deciding whether two matrices generate equivalent linear codes, i.e., codes that consist of the same codewords up to a fixed permutation on the codeword coordinates. We call this problem code equivalence. Using techniques from the area of interactive proofs, we show on the one hand, that under the assumption that the polynomial-time hierarchy does not collapse, code equivalence is not NP-complete. On the other hand, we present a polynomial-time reduction from the graph isomorphism problem to code equivalence. Thus if one could find an efficient (i.e., polynomial-time) algorithm for code equivalence, then one could settle the long-standing problem of determining whether there is an efficient algorithm for solving graph isomorphism.

The crisscross error model in data arrays is considered, where the corrupted symbols are confined to a prescribed number of rows or columns (or both). Under the additional assumption that the corrupted entries are uniformly distributed over the channel alphabet, and by allowing a small decoding error probability, a coding scheme is presented where the redundancy can get close to one half the redundancy required in minimum-distance decoding of crisscross errors.

Finite-state encoders that encode n-ary data into a constrained system S are considered. The anticipation, or decoding delay, of such an (S,n)-encoder is the number of symbols that a state-dependent decoder needs to look ahead in order to recover the current input symbol. Upper bounds are obtained on the smallest attainable number of states of any (S, n)-encoder with anticipation t. Those bounds can be explicitly computed from t and S, which implies that the problem of checking whether there is an (S, n)-encoder with anticipation t is decidable. It is also shown that if there is an (S,n)-encoder with anticipation t, then a version of the state-splitting algorithm can be applied to produce an (S, n) encoder with anticipation at most 2t-1. We also observe that the problem of checking whether there is an (S, n)-encoder having a sliding-block decoder with a given memory and anticipation is decidable.

Linear spaces of n/spl times/n/spl times/n tensors over finite fields are investigated where the rank of every nonzero tensor in the space is bounded from below by a prescribed number /spl mu/. Such linear spaces can recover any n/spl times/n/spl times/n error tensor of rank /spl les/ (/spl mu/-1)/2, and, as such, they can be used to correct three-way crisscross errors. Bounds on the dimensions of such spaces are given for /spl mu//spl les/2n+1, and constructions are provided for /spl mu//spl les/2n-1 with redundancy which is linear in n. These constructions can be generalized to spaces of n/spl times/n/spl times/.../spl times/n hyper-arrays.

We study codes over GF(q) that can correct t channel errors assuming the error values are known. This is a counterpart to the well-known problem of erasure correction, where error values are found assuming the locations are known. The correction capabilities of these so-called t-location correcting codes (t-LCCs) are characterized by a new metric, the decomposability distance, which plays a role analogous to that of the Hamming metric in conventional error-correcting codes (ECCs). Based on the new metric, we present bounds on the parameters of t-LCCs that are counterparts to the classical Singleton, sphere packing and Gilbert-Varshamov bounds for ECCs. In particular, we show examples of perfect LCCs, and we study optimal (MDS-Like) LCCs that attain the Singleton-type bound on the redundancy. We show that these optimal codes are generally much shorter than their erasure (or conventional ECC) analogs. The length n of any t-LCC that attains the Singleton-type bound for t>1 is bounded from above by t+O(/spl radic/(q)), compared to length q+1 which is attainable in the conventional ECC case. We show constructions of optimal t-LCCs for t/spl isin/{1, 2, n-2, n-1, n} that attain the asymptotic length upper bounds, and constructions for other values of t that are optimal, yet their lengths fall short of the upper bounds. The resulting asymptotic gap remains an open research problem. All the constructions presented can be efficiently decoded.

The following file distribution problem is considered: Given a network of processors represented by an undirected graph $G = (V, E)$ and a file size k, an arbitrary file ${\bf w}$ of k bits is to be distributed among all nodes of G. To this end, each node is assigned a memory device such that by accessing the memory of its own and of its adjacent nodes, the node can reconstruct the contents of ${\bf w}$. The objective is to minimize the total size of memory in the network. This paper presents a file distribution scheme which realizes this objective for $k \gg \log \Delta_{G}$, where $\Delta_{G}$ stands for the maximum degree in G: For this range of k, the total memory size required by the suggested scheme approaches an integer programming lower bound on that size. The scheme is also constructive in the sense that given G and k, the memory size at each node in G, as well as the mapping of any file ${\bf w}$ into the node memory devices, can be computed in time complexity which is polynomial in k and $|V|$. Furthermore, each node can reconstruct the contents of such a file ${\bf w}$ in $O(k^{2})$ bit operations. Finally, it is shown that the requirement of k being much larger than $\log \Delta_{G}$ is necessary in order to have total memory size close to the integer programming lower bound.

An input-constrained channel is defined as the set S of finite sequences generated by a finite labeled directed graph which defines the channel. A construction based on a result of Adler, Goodwyn, and Weiss (1977) is presented for finite-state encoders for input-constrained channels. Let G=(V, E) denote a smallest deterministic presentation of S. For a given input-constrained channel S and for any rate p: q up to the capacity c(S) of S, the construction provides finite-state encoders of fixed-rate p: q that can be implemented in hardware with a number of gates which is at most polynomially large in |V|. When p/q>

Shows that each code in a certain class of BCH codes over GF(p), specified by a code length n/spl les/p/sup m/-1 and a runlength r/spl les/(p-1)/2 of consecutive roots in GF(p/sup m/), has minimum Lee distance /spl ges/2r. For the very high-rate range these codes approach the sphere-packing bound on the minimum Lee distance. Furthermore, for a given r, the length range of these codes is twice as large as that attainable by Berlekamp's (1984) extended negacyclic codes. The authors present an efficient decoding procedure, based on Euclid's algorithm, for correcting up to r-1 errors and detecting r errors, that is, up to the number of Lee errors guaranteed by the designed minimum Lee distance 2r. Bounds on the minimum Lee distance for r/spl ges/(p+1)/2 are provided for the Reed-Solomon case, i.e., when the BCH code roots are in GF(p). The authors present two applications. First, Lee-metric BCH codes can be used for protecting against bitshift errors and synchronization errors caused by insertion and/or deletion of zeros in (d, k)-constrained channels. Second, the code construction with its decoding algorithm can be formulated over the integer ring, providing an algebraic approach to correcting errors in partial-response channels where matched spectral-null codes are used.>

Let /spl Sscr/(n.k) denote the set of all words of length n over the alphabet {+1,-1}, having a k th order spectral-null at zero frequency. A subset of /spl Sscr/(n,k) is a spectral-null code of length n and order k. Upper and lower bounds on the cardinality of /spl Sscr/(n,k) are derived. In particular we prove that (k-1) log/sub 2/ (n/k)/spl les/n-log/sub 2/|/spl Sscr/(n,k)|/spl les/O(2/sup k/log/sub 2/n) for infinitely many values of n. On the other hand, we show that /spl Sscr/(n.k) is empty unless n is divisible by 2/sup m/, where m=[log/sub 2/k]+1. Furthermore, bounds on the minimum Hamming distance d of /spl Sscr/(n,k) are provided, showing that 2k/spl les/d/spl les/k(k-1)+2 for infinitely many n. We also investigate the minimum number of sign changes in a word x/spl isin//spl Sscr/(n,k) and provide an equivalent definition of /spl Sscr/(n,k) in terms of the positions of these sign changes. An efficient algorithm for encoding arbitrary information sequences into a second-order spectral-null code of redundancy 3 log/sub 2/n+O(log log n) is presented. Furthermore, we prove that the first nonzero moment of any word in /spl Sscr/(n,k) is divisible by k!. This leads to an encoding scheme for spectral-null codes of length n and any fixed order k, with rate approaching unity as n/spl rarr//spl infin/.>

An optimal family of array codes over GF(q) for correcting multiple phased burst errors and erasures, where each phased burst corresponds to an erroneous or erased column in a code array, is introduced. As for erasures, these array codes have an efficient decoding algorithm which avoids multiplications (or divisions) over extension fields, replacing these operations with cyclic shifts of vectors over GF(q). The erasure decoding algorithm can be adapted easily to handle single column errors as well. The codes are characterized geometrically by means of parity constraints along certain diagonal lines in each code array, thus generalizing a previously known construction for the special case of two erasures. Algebraically, they can be interpreted as Reed-Solomon codes. When q is primitive in GF(q), the resulting codes become (conventional) Reed-Solomon codes of length P over GF(q/sup p-1/), in which case the new erasure decoding technique can be incorporated into the Berlekamp-Massey algorithm, yielding a faster way to compute the values of any prescribed number of errors.>

A novel technique, based on the pseudo-random properties of certain graphs known as expanders, is used to obtain novel simple explicit constructions of asymptotically good codes. In one of the constructions, the expanders are used to enhance Justesen codes by replicating, shuffling, and then regrouping the code coordinates. For any fixed (small) rate, and for a sufficiently large alphabet, the codes thus obtained lie above the Zyablov bound. Using these codes as outer codes in a concatenated scheme, a second asymptotic good construction is obtained which applies to small alphabets (say, GF(2)) as well. Although these concatenated codes lie below the Zyablov bound, they are still superior to previously known explicit constructions in the zero-rate neighborhood.

Nonconstructive existence results are obtained for block error-correcting codes whose codewords lie in a given constrained system. Each such system is defined as a set of words obtained by reading the labels of a finite directed labeled graph. For a prescribed constrained system and relative minimum distance delta , the new lower bounds on the rate of such codes improve on those derived recently by V.D. Kolesnik and V.Y. Krachkovsky (1991). The better bounds are achieved by considering a special subclass of sequences in the constrained system, namely, those having certain empirical statistics determined by delta .>

Given a distributed network of processors represented by an undirected graph G=(V, E) and a file size k, the problem of distributing an arbitrary file w of k bits among all nodes of the network G is considered. Memory devices are to be assigned to the node of G such that, by accessing the memory of its own and of its adjacent nodes, each node can reconstruct the contents of w. The objective is to minimize the total size memory in the network. A file distribution scheme that realizes this objective for k>>log Delta /sub G/, where Delta /sub G/, stands for the maximum degree in G, is presented. For this range of k, the total size of memory required by the suggested scheme approaches an integer programming lower bound on that size.>

A function $f:\{ 0,1\} ^n \to \{ 0,1\} $ is called t-sparse if the n-variable polynomial representation of f over $GF(2)$ contains at most t monomials. Such functions are uniquely determined by their values at the so-called critical set of all binary n-tuples of Hamming weight $ \geqq n - \lfloor \log _2 t \rfloor - 1$. An algorithm is presented for interpolating any t-sparse function f, given the values of f at the critical set. The time complexity of the proposed algorithm is proportional to n, t, and the size of the critical set. Then, the more general problem of approximating 1-sparse functions is considered, in which case the approximating function may differ from f at a fraction $\varepsilon $ of the space $\{ 0,1\} ^n $. It is shown that $O(({t / \varepsilon }) \cdot n)$ evaluation points are sufficient for the (deterministic) $\varepsilon $-approximation of any t-sparse function, and that an order $(t / \varepsilon )^{\alpha (t,\varepsilon )} \cdot \log n$ points are necessary for this purpose, where $\alpha (t,\varepsilon ) \geqq 0.694$ for a large range of t and $\varepsilon $. Similar bounds hold for the t-term DNF case as well. Finally, a probabilistic polynomial-time algorithm is presented for the $\varepsilon $-approximation of any t-sparse function.

The authors obtain general lower bounds on the number of states in any encoder for a given constrained system and rate. Lower bounds on the number of states are exhibited in a fixed-rate finite-state encoder that maps unconstrained n-ary sequences into a given set of constrained sequences, defined by a finite labeled graph G. In particular, one simple lower bound is given by min/sub x/max/sub v/x/sub v/ where x=(x/sub v/) ranges over certain (nonnegative integer) approximate eigenvectors of the adjacency matrix for G. In some sense, the bounds are close to what can be realized by the state splitting algorithm and in some cases, they are shown to be tight. In particular, these bounds are used to show that the smallest (in number of states) known encoders for the

A mu -(n*n,k) array code C over a field F is a k-dimensional linear space of n*n matrices over F such that every nonzero matrix in C has rank >or= mu . It is first shown that the dimension of such array codes must satisfy the Singleton-like bound k>

The Fourier transform technique is used to analyze and construct several families of double-circulant codes. The minimum distance of the resulting codes is lower-bounded by 2 square root r and can be decoded easily employing the standard BCH decoding algorithm or the majority-logic decoder of Reed-Muller codes. A decoding procedure for Reed-Solomon codes is presented, based on a representation of the parity-check matrix by circulant blocks. The decoding procedure inherits both the (relatively low) time complexity of the Berlekamp-Massey algorithm and the hardware simplicity characteristic of Blahut's algorithm. The procedure makes use of the encoding circuit together with a reduced version of Blahut's decoder.>

A construction is presented of long maximum-distance-separable (MDS) codes that are not generalized Reed-Solomon (GRS) type. The construction uses subsets S, mod S mod =m of a finite field F=GF(q) with the property that no t distinct elements of S add up to some fixed element of F. Large subsets of this kind are used to construct (n=m+2, k=t+1) non-GRS MDS codes over F.>

A special form of Cauchy matrix is used to obtain a tighter bound for the validity region of the maximum distance separable (MDS) conjecture and a new compact characterization of generalized Reed-Solomon codes. The latter is further used to obtain constructions and some existence results for long (2k, k) double-circulant MDS codes.>

It is shown that good linear (n,k,d) codes over a finite field GF(q) can be constructed by concatenating the generator matrices of Reed-Solomon codes. For the case of k=3, it is shown that many of the codes obtained using projective-geometry techniques can readily be obtained by the proposed algebraic approach.>

It is shown that every q-ary primitive Bose-Chaudhuri-Hocquenghen code of designed distance delta and sufficiently large length n contains a codeword c/sub 0/ of weight w=O( delta ) and degree deg(c/sub 0/)=o(n). Here, the standard asymptotic notation O( delta ) is used for a function f( delta ) bounded above by lambda delta for some constant lambda , and o(n) for a function h(n) such that lim/sub n/ to infinity h(n)/n=O. These so-called light and short codewords are used to describe encoding and decoding algorithms which run on sequential machines in time O( delta n), i.e., linear in n for fixed delta . For high-rate primitive BCH codes this is faster than the commonly used algorithms, which are nonlinear in n when run on sequential machines.>

It is shown that a cyclic codeCof lengthqover GF(q)is the maximum distance separable if and only if either1) qis a prime, in which caseCis equivalent, up to a coordinate permutation, to an extended Reed-Solomon code, or2) Cis a trivial code of dimensionk \in \{1, q - 1, q \}. Hence there exists a nontrivial cyclic extended Reed-Solomon code of lengthqover GF(q)if and only ifqis a prime.

An(n, k, d)linear code overF=GF(q)is said to be {\em maximum distance separable} (MDS) ifd = n - k + 1. It is shown that an(n, k, n - k + 1)generalized Reed-Solomon code such that2\leq k \leq n - \lfloor (q - 1)/2 \rfloor (k \neq 3 {\rm if} qis even) can be extended by one digit while preserving the MDS property if and only if the resulting extended code is also a generalized Reed-Solomon code. It follows that a generalized Reed-Solomon code withkin the above range can be {\em uniquely} extended to a maximal MDS code of lengthq + 1, and that generalized Reed-Solomon codes of lengthq + 1and dimension2\leq k \leq \lfloor q/2 \rfloor + 2 (k \neq 3 {\rm if} qis even) do not have MDS extensions. Hence, in cases where the(q + 1, k)MDS code is essentially unique,(n, k)MDS codes withn > q + 1do not exist.

It is shown that the family ofq-ary generalized Reed-Solomon codes is identical to the family ofq-ary linear codes generated by matrices of the form[I|A], whereIis the identity matrix, andAis a generalized Cauchy matrix. Using Cauchy matrices, a construction is shown of maximal triangular arrays over GF(q), which are constant along diagonals in a Hankel matrix fashion, and with the property that every square subarray is a nonsingular matrix. By taking rectangular subarrays of the described triangles, it is possible to construct generator matrices[I|A]of maximum distance separable codes, whereAis a Hankel matrix. The parameters of the codes are(n,k,d), for1 \leq n \leq q+ 1, 1 \leq k \leq n, andd=n-k+1.