Search

In this paper we consider the problem of encoding data into repeat-free sequences in which sequences are imposed to contain any k-tuple at most once (for predefined k). First, the capacity of the repeat-free constraint are calculated. Then, an efficient algorithm, which uses two bits of redundancy, is presented to encode length-n sequences for k = 2 + 2 log (n). This algorithm is then improved to support any value of k of the form k = a log (n), for 1 < a, while its redundancy is o(n). We also calculate the capacity of repeat-free sequences when combined with local constraints which are given by a constrained system, and the capacity of multi-dimensional repeat-free codes. [ABSTRACT FROM AUTHOR]

Costa has proved that for noncausally known Gaussian interference at a power constrained transmitter communicating over an additive white Gaussian noise channel there is no capacity loss when compared to a scenario where interference is not present. For the case of a transmitter communicating over a quasistatic (i.e., nonergodic) fading channel, his method does not apply. In this correspondence, we derive upper and lower bounds on the capacity of compound channels with side information at the transmitter, first for finite alphabet channels and then, based on this result, for channels on standard alphabets (this includes real alphabets). For the special case of a degenerate compound channel with only one possible realization, our bounds are equivalent to the well-known capacity with side-information formula of Gel'fand and Pinsker. For the quasistatic fading channel, when fading is Ricean, we suggest a scheme based on our lower bound for which the performance is found to be relatively good even for moderate K-factor. As K → ∞, the uncertainty on the channel vanishes and our scheme obtains the performance of dirty paper coding, namely that the interference is perfectly mitigated. As K → 0, the proposed scheme treats the interferer as additional noise. These results may be of importance for the emerging field of cognitive radios where one user may be aware of another user's intended message to a common receiver, but is unaware of the channel path gains. [ABSTRACT FROM AUTHOR]

Binary sequences with low odd correlation have important applications in communication systems to reduce interference. In this paper, using the interleaving technique, we present a generic connection between binary sequences with low odd correlation and quaternary sequences with low even correlation. As a result, some new binary sequences with optimal odd auto-correlation magnitude are obtained. Besides, two sets consisting of 2^n+1 binary sequences of period 2(2^n-1) with the maximum odd correlation magnitude 2^((n+1)/ 2)+2 are derived, which are the first two optimal classes of binary sequence sets achieving the Sarwate bound on the odd correlation magnitude in the literature. [ABSTRACT FROM PUBLISHER]

This paper considers the relationship between code-rate selection and queueing performance for communication systems subject to time-varying channel conditions. While error-correcting codes offer protection against channel uncertainties, there exists a natural tradeoff between the enhanced protection of low-rate codes and the rate penalty imposed by additional redundancy. In the limiting regime where codewords are asymptotically long, this tradeoff is well understood and characterized by the Shannon capacity. However, for delay-sensitive communication systems and finite block lengths, a complete characterization of this tradeoff is not fully developed. This paper offers a new perspective on the queueing performance of communication systems with finite block lengths operating over correlated erasure channels. A rigorous framework that links code rate to overall system performance for random codes is presented. Guidelines for code-rate selection in delay-sensitive systems are identified. These findings are supported by a numerical study. [ABSTRACT FROM AUTHOR]

In this paper, we prove that Schubert union codes are Tanner codes constructed from the point–line incidence geometry inherited from the Grassmannian. Our proof is based on an iterative encoding algorithm for Tanner codes. This encoder determines the entries of a code word of a Tanner code from the entries in a given subset of its positions. As a result, we find sufficient conditions on the initial positions such that a code word is determined from the component codes only. This algorithm has linear complexity in the code length. We also use this encoder to determine the minimum distance of Schubert union codes in terms of the minimum distance of the Schubert varieties contained therein. [ABSTRACT FROM PUBLISHER]

In this paper, we revisit the problem of characterizing the secrecy capacity of minimum storage regenerating (MSR) codes under the passive (l1,l2) -eavesdropper model, where the eavesdropper has access to data stored on l1 nodes and the repair data for an additional l2 nodes. We study it from the information-theoretic perspective. First, some general properties of MSR codes as well as a simple and generally applicable upper bound on secrecy capacity are given. Second, a new concept of stable MSR codes is introduced, where the stable property is shown to be closely linked with secrecy capacity. Finally, a comprehensive and explicit result on secrecy capacity in the linear MSR scenario is present, which generalizes all related works in the literature and also predicts certain results for some unexplored linear MSR codes. [ABSTRACT FROM PUBLISHER]

Lee codes have been intensively studied for more than 40 years. Interest in these codes has been triggered by the Golomb–Welch conjecture on the existence of the perfect error-correcting Lee codes. In this paper, we deal with the existence and enumeration of diameter perfect Lee codes. As main results, we determine all q for which there exists a linear diameter-4 perfect Lee code of word length n over Zq, and prove that for each n\geq 3, there are uncountable many diameter-4 perfect Lee codes of word length n over Z. This is in a strict contrast with perfect error-correcting Lee codes of word length n over Z as there is a unique such code for n=3, and its is conjectured that this is always the case when 2n+1 is a prime. We produce diameter perfect Lee codes by an algebraic construction that is based on a group homomorphism. This will allow us to design an efficient algorithm for their decoding. We hope that this construction will turn out to be useful far beyond the scope of this paper. [ABSTRACT FROM PUBLISHER]

The fundamental task of group testing is to recover a small distinguished subset of items from a large population while efficiently reducing the total number of tests (measurements). The key contribution of this paper is in adopting a new information-theoretic perspective on group testing problems. We formulate the group testing problem as a channel coding/decoding problem and derive a single-letter characterization for the total number of tests used to identify the defective set. Although the focus of this paper is primarily on group testing, our main result is generally applicable to other compressive sensing models. [ABSTRACT FROM AUTHOR]

Consider the high-dimensional linear regression model y = X \beta^* + w, where y \in \BBR^n is an observation vector, X \in \BBR^n \times d is a design matrix with d > n, \beta^* \in \BBR^d is an unknown regression vector, and w \sim \cal N(0, \sigma^2 I) is additive Gaussian noise. This paper studies the minimax rates of convergence for estimating \beta^* in either \ell_2-loss and \ell_2-prediction loss, assuming that \beta^* belongs to an \ell_q-ball \BBB_q(R_q) for some q \in [0,1]. It is shown that under suitable regularity conditions on the design matrix X, the minimax optimal rate in \ell_2-loss and \ell_2-prediction loss scales as \Theta\left(R_q \left(\log d \over n\right)^1-q \over 2\right). The analysis in this paper reveals that conditions on the design matrix X enter into the rates for \ell_2-error and \ell_2-prediction error in complementary ways in the upper and lower bounds. Our proofs of the lower bounds are information theoretic in nature, based on Fano's inequality and results on the metric entropy of the balls \BBB_q(R_q), whereas our proofs of the upper bounds are constructive, involving direct analysis of least squares over \ell_q-balls. For the special case q=0, corresponding to models with an exact sparsity constraint, our results show that although computationally efficient \ell_1-based methods can achieve the minimax rates up to constant factors, they require slightly stronger assumptions on the design matrix X than optimal algorithms involving least-squares over the \ell_0-ball. [ABSTRACT FROM AUTHOR]

Recently, there were several papers on finding good linear codes. Various methods were introduced to make good linear codes. In this paper, we give a simple iterative algorithm to make good linear codes. Using our algorithm we construct 86 codes which improve the minimum distance of previously best known linear codes for fixed parameters n, k. [ABSTRACT FROM AUTHOR]

In this paper, we study upper and lower bounds on the error exponents for joint source-channel coding with decoder side-information. The results in the paper are nontrivial extensions of Csiszár's classical paper “Joint Source-Channel Error Exponent”, Problems of Control and Information Theory, 1980. Unlike the joint source-channel coding result in Csiszár's paper, it is not obvious whether the lower bound and the upper bound are equivalent even if the channel coding error exponent is known. For a class of channels, including symmetric channels, we apply a game-theoretic result to establish the existence of a saddle point and, hence, prove that the lower and upper bounds are the same if the channel coding error exponent is known. More interestingly, we show that encoder side-information does not increase the error exponents in this case. [ABSTRACT FROM AUTHOR]

This paper studies the capacity of single-source single-sink noiseless networks under adversarial or arbitrary errors on no more than z edges. Unlike prior papers, which assume equal capacities on all links, arbitrary link capacities are considered. Results include new upper bounds, network error-correction coding strategies, and examples of network families where our bounds are tight. An example is provided of a network where the capacity is 50% greater than the best rate that can be achieved with linear coding. While coding at the source and sink suffices in networks with equal link capacities, in networks with unequal link capacities, it is shown that intermediate nodes may have to do coding, nonlinear error detection, or error correction in order to achieve the network error-correction capacity. [ABSTRACT FROM AUTHOR]

The problem of optimum watermark embedding and detection was addressed in a recent paper by Merhav and Sabbag, where the optimality criterion was the maximum false-negative error exponent subject to a guaranteed false-positive error exponent. In particular, Merhav and Sabbag derived universal asymptotically optimum embedding and detection rules under the assumption that the detector relies solely on second-order joint empirical statistics of the received signal and the watermark. In the case of a Gaussian host signal and a Gaussian attack, however, closed-form expressions for the optimum embedding strategy and the false-negative error exponent were not obtained in that work. In this paper, we derive the false-negative error exponent for any given embedding strategy and use such a result to show that in general the optimum embedding rule depends on the variance of the host sequence and the variance of the attack noise. We then focus on high signal-to-noise ratio (SNR) regime, deriving the optimum embedding strategy for such a setup. In this case, a universally optimum embedding rule turns out to exist and to be very simple with an intuitively appealing geometrical interpretation. The effectiveness of the newly proposed embedding strategy is evaluated numerically. [ABSTRACT FROM AUTHOR]

Error-correcting codes and matroids have been widely used in the study of ordinary secret sharing schemes. In this paper, the connections between codes, matroids, and a special class of secret sharing schemes, namely, multiplicative linear secret sharing schemes (LSSSs), are studied. Such schemes are known to enable multiparty computation protocols secure against general (nonthreshold) adversaries. Two open problems related to the complexity of multiplicative LSSSs are considered in this paper. The first one deals with strongly multiplicative LSSSs. As opposed to the case of multiplicative LSSSs, it is not known whether there is an efficient method to transform an LSSS into a strongly multiplicative LSSS for the same access structure with a polynomial increase of the complexity. A property of strongly multiplicative LSSSs that could be useful in solving this problem is proved. Namely, using a suitable generalization of the well-known Berlekamp-Welch decoder, it is shown that all strongly multiplicative LSSSs enable efficient reconstruction of a shared secret in the presence of malicious faults. The second one is to characterize the access structures of ideal multiplicative LSSSs. Specifically, the considered open problem is to determine whether all self-dual vector space access structures are in this situation. By the aforementioned connection, this in fact constitutes an open problem about matroid theory, since it can be restated in terms of representability of identically self-dual matroids by self-dual codes. A new concept is introduced, the fiat-partition, that provides a useful classification of identically self-dual matroids. Uniform identically self-dual matroids, which are known to be representable by self-dual codes, form one of the classes. It is proved that this property also holds for the family of matroids that, in a natural way, is the next class in the above classification: the identically self-dual bipartite matroids. [ABSTRACT FROM AUTHOR]

This paper derives an improved sphere-packing (ISP) bound for finite-length error-correcting codes whose transmission takes place over symmetric memoryless channels, and the codes are decoded with an arbitrary list decoder. We first review classical results, i.e., the 1959 sphere-packing (SP59) bound of Shannon for the Gaussian channel, and the 1967 sphere-packing (SP67) bound of Shannon et al. for discrete memoryless channels. An improvement on the SP67 bound, as suggested by Valembois and Fossorier, is also discussed. These concepts are used for the derivation of a new lower bound on the error probability of list decoding (referred to as the ISP bound) which is uniformly tighter than the SP67 bound and its improved version. The ISP bound is applicable to symmetric memoryless channels, and some of its applications are presented. Its tightness under maximum-likelihood (ML) decoding is studied by comparing the ISP bound to previously reported upper and lower bounds on the ML decoding error probability, and also to computer simulations of iteratively decoded turbo-like codes. This paper also presents a technique which performs the entire calculation of the SP59 bound in the logarithmic domain, thus facilitating the exact calculation of this bound for moderate to large block lengths without the need for the asymptotic approximations provided by Shannon. [ABSTRACT FROM AUTHOR]

In this paper, the average coset weight distribution (ACWD) of structured ensembles of low-density parity-check (LDPC) matrices, which are called combined ensembles, is discussed. A combined ensemble is composed of a set of simpler ensembles such as a regular bipartite ensemble. Two classes of combined ensembles have prime importance; a stacked ensemble and a concatenated ensemble. The ACWD formulas of these ensembles are shown in this paper. Such formulas play a key role to evaluate the average weight distribution of some classes of combined ensembles. [ABSTRACT FROM AUTHOR]

Binary primitive triple-error-correcting Bose--Chaudhuri-Hocquenghem (BCH) codes of length n = 2m - 1 have been the object of intensive studies for several decades. In the 1970s, their covering radius was determined in a series of papers to be ρ = 5. However, one problem for these codes that has been open up to now is to find their coset distribution. In this paper this problem is solved and the number of cosets of each weight in any binary primitive triple-error-correcting BCH code is determined. As a consequence this also gives the coset distribution of the extended codes of length N = 2m with minimum distance 8. [ABSTRACT FROM AUTHOR]

This paper introduces the covering dimension of a linear code over a finite field, which is analogous to the critical exponent of a representable matroid and, thus, generalizes invariants that lie at the heart of several fundamental problems in a coding theory. An upper bound on the covering dimension is proved, improving Kung’s classical bound for the critical exponent. In addition, a construction is given for linear codes that attain equality in this covering dimension bound. [ABSTRACT FROM AUTHOR]

Linear network coding transmits data through networks by letting the intermediate nodes combine the messages they receive and forward the combinations toward their destinations. The solvability problem asks whether the demands of all the destinations can be simultaneously satisfied by using linear network coding. The guessing number approach converts this problem into determining the number of fixed points of coding functions f:A^n\to A^n over a finite alphabet $A$ (usually referred to as Boolean networks if A = \{0,1\} ) with a given interaction graph that describes which local functions depend on which variables. In this paper, we generalize the so-called reduction of coding functions in order to eliminate variables. We then determine the maximum number of fixed points of a fully reduced coding function, whose interaction graph has a loop on every vertex. Since the reduction preserves the number of fixed points, we then apply these ideas and results to obtain four main results on the linear network coding solvability problem. First, we prove that non-decreasing coding functions cannot solve any more instances than routing already does. Second, we show that the triangle-free undirected graphs are linearly solvable if and only if they are solvable by routing. This is the first classification result for the linear network coding solvability problem. Third, we exhibit a new class of non-linearly solvable graphs. Fourth, we determine large classes of strictly linearly solvable graphs. [ABSTRACT FROM AUTHOR]

This paper is devoted to studying two main problems: 1) computing the apparent distance of an Abelian code and 2) giving a notion of Bose, Ray-Chaudhuri, Hocquenghem (BCH) multivariate code. To do this, we first strengthen the notion of an apparent distance by introducing the notion of a strong apparent distance; then, we present an algorithm to compute the strong apparent distance of an Abelian code, based on some manipulations of hypermatrices associated with its generating idempotent. Our method uses less computations than those given by Camion and Sabin; furthermore, in the bivariate case, the order of computation complexity is reduced from exponential to linear. Then, we use our techniques to develop a notion of a BCH code in the multivariate case, and we extend most of the classical results on cyclic BCH codes. Finally, we apply our method to the design of Abelian codes with maximum dimension with respect to a fixed apparent distance and a fixed length. [ABSTRACT FROM AUTHOR]

In this paper, some questions on the distribution of the peak-to-mean envelope power ratio (PMEPR) of standard binary Golay sequences are solved. For n odd, we prove that the PMEPR of each standard binary Golay sequence of length 2^n is exactly 2, and determine the location(s), where peaks occur for each sequence. For n even, we prove that the envelope power of such sequences can never reach 2^n+1 at time points t\in\(v/2^u)\vert 0\leqslant v\leqslant 2^u, v,u\in\BBN\. We further identify eight sequences of length 2^4 and eight sequences of length 2^6 that have PMEPR exactly 2, and raise the question whether, asymptotically, it is possible for standard binary Golay sequences to have PMEPR less than 2-\epsilon, where \epsilon>0. [ABSTRACT FROM PUBLISHER]

We consider communication over the binary erasure channel (BEC) using low-density parity-check (LDPC) codes and belief propagation (BP) decoding. For fixed numbers of BP iterations, the bit error probability approaches a limit as the blocklength tends to infinity, and the limit is obtained via density evolution. The finite-blocklength correction behaves like \alpha(\epsilon,t)/n+\Theta(n^-2) as the blocklength n tends to infinity where \alpha(\epsilon,t) denotes a specific constant determined by the code ensemble considered, the number t of iterations, and the erasure probability \epsilon of the BEC. In this paper, we derive a set of recursive formulas which allows the evaluation of the constant \alpha(\epsilon,t) for standard irregular ensembles. The dominant difference \alpha(\epsilon,t)/n can be considered as effects of cycle-free and single-cycle structures of local graphs. Furthermore, it is confirmed via numerical simulations that estimation of the bit error probability using \alpha(\epsilon,t) is accurate even for small blocklengths. [ABSTRACT FROM AUTHOR]

Consider a linear [n,k,d]q code \cal C. We say that the ith coordinate of \cal C has locality r, if the value at this coordinate can be recovered from accessing some other r coordinates of \cal C. Data storage applications require codes with small redundancy, low locality for information coordinates, large distance, and low locality for parity coordinates. In this paper, we carry out an in-depth study of the relations between these parameters. We establish a tight bound for the redundancy n-k in terms of the message length, the distance, and the locality of information coordinates. We refer to codes attaining the bound as optimal. We prove some structure theorems about optimal codes, which are particularly strong for small distances. This gives a fairly complete picture of the tradeoffs between codewords length, worst case distance, and locality of information symbols. We then consider the locality of parity check symbols and erasure correction beyond worst case distance for optimal codes. Using our structure theorem, we obtain a tight bound for the locality of parity symbols possible in such codes for a broad class of parameter settings. We prove that there is a tradeoff between having good locality and the ability to correct erasures beyond the minimum distance. [ABSTRACT FROM PUBLISHER]

In this paper, a new but simple construction of stabilizer codes and related entanglement-assisted quantum error-correcting codes is proposed based on syndrome assignment by classical parity-check matrices. This method turns the construction of quantum stabilizer codes to the construction of classical parity-check matrices satisfying a specific commutative condition. The designed minimum distance 2t^*+1 of the constructed quantum stabilizer codes can be achieved by a commutative classical parity-check matrix with classical minimum distance 4t^*-m, where the parameter m, 0\leq m\leq 2t^*, depends on a property of the parity-check matrix. As m decreases, there is an increasing set of additional correctable error operators beyond the designed error correcting capability t^*. The (asymptotic) coding efficiency is at least comparable to that of CSS codes. A class of quantum Reed–Muller codes is constructed and codes in this class have a larger set of correctable error operators than that of the quantum Reed–Muller codes previously developed in the literature. Quantum circulant codes are also constructed and many of them are optimal in terms of their coding parameters. [ABSTRACT FROM AUTHOR]

While linear programming (LP) decoding provides more flexibility for finite-length performance analysis than iterative message-passing (IMP) decoding, it is computationally more complex to implement in its original form, due to both the large size of the relaxed LP problem and the inefficiency of using general-purpose LP solvers. This paper explores ideas for fast LP decoding of low-density parity-check (LDPC) codes. By modifying the previously reported Adaptive LP decoding scheme to allow removal of unnecessary constraints, we first prove that LP decoding can be performed by solving a number of LP problems that each contains at most one linear constraint derived from each of the parity-check constraints. By exploiting this property, we study a sparse interior-point implementation for solving this sequence of linear programs. Since the most complex part of each iteration of the interior-point algorithm is the solution of a (usually ill-conditioned) system of linear equations for finding the step direction, we propose a preconditioning algorithm to facilitate solving such systems iteratively. The proposed preconditioning algorithm is similar to the encoding procedure of LDPC codes, and we demonstrate its effectiveness via both analytical methods and computer simulation results. [ABSTRACT FROM AUTHOR]

Departing from traditional communication theory where decoding algorithms are assumed to perform without error, a system where noise perturbs both computational devices and communication channels is considered here. This paper studies limits in processing noisy signals with noisy circuits by investigating the effect of noise on standard iterative decoders for low-density parity-check (LDPC) codes. Concentration of decoding performance around its average is shown to hold when noise is introduced into message-passing and local computation. Density evolution equations for simple faulty iterative decoders are derived. In one model, computing nonlinear estimation thresholds shows that performance degrades smoothly as decoder noise increases, but arbitrarily small probability of error is not achievable. Probability of error may be driven to zero in another system model; the decoding threshold again decreases smoothly with decoder noise. As an application of the methods developed, an achievability result for reliable memory systems constructed from unreliable components is provided. [ABSTRACT FROM AUTHOR]

This paper investigates the performance of frames for the linear, redundant encoding of vectors when consecutive frame coefficients are lost due to the occurrence of random burst errors. We assume that the distribution of bursts is invariant under cyclic shifts and that the burst-length statistics are known. In analogy with rate-distortion theory, we wish to find frames of a given size, which minimize the mean-square reconstruction error for the encoding of vectors in a complex finite-dimensional Hilbert space. We obtain an upper bound for the mean-square reconstruction error for a given Parseval frame and in the case of cyclic Parseval frames, we find a family of frames which minimizes this upper bound. Under certain conditions, these minimizers are identical to complex Bose–Chaudhuri–Hocquenghem codes discussed in the literature. The accuracy of our upper bounds for the mean-square error is substantiated by complementary lower bounds. All estimates are based on convexity arguments and a discrete rearrangement inequality. [ABSTRACT FROM AUTHOR]

The projective space of order n over the finite field \BBFq, denoted here as \cal P_q(n), is the set of all subspaces of the vector space \BBFq^n. The projective space can be endowed with the distance function d(U, V) = \dim U + \dim V -2 \dim(U \cap V) which turns \cal P_q(n) into a metric space. With this, an (n,M,d) code \BBC in projective space is a subset of \cal P_q(n) of size M such that the distance between any two codewords (subspaces) is at least d. Koetter and Kschischang recently showed that codes in projective space are precisely what is needed for error-correction in networks: an (n,M,d) code can correct t packet errors and \rho packet erasures introduced (adversarially) anywhere in the network as long as 2t + 2\rho\,<\,d. This motivates our interest in such codes. In this paper, we investigate certain basic aspects of “coding theory in projective space.” First, we present several new bounds on the size of codes in \cal P_q(n), which may be thought of as counterparts of the classical bounds in coding theory due to Johnson, Delsarte, and Gilbert-Varshamov. Some of these are stronger than all the previously known bounds, at least for certain code parameters. We also present several specific constructions of codes and code families in \cal P_q(n). Finally, we prove that nontrivial perfect codes in \cal P_q(n) do not exist. [ABSTRACT FROM AUTHOR]

Low-density parity-check (LDPC) convolutional codes are capable of achieving excellent performance with low encoding and decoding complexity. In this paper, we discuss several graph-cover-based methods for deriving families of time-invariant and time-varying LDPC convolutional codes from LDPC block codes and show how earlier proposed LDPC convolutional code constructions can be presented within this framework. Some of the constructed convolutional codes significantly outperform the underlying LDPC block codes. We investigate some possible reasons for this “convolutional gain,” and we also discuss the—mostly moderate—decoder cost increase that is incurred by going from LDPC block to LDPC convolutional codes. [ABSTRACT FROM AUTHOR]

Models for noncoherent error control in random linear network coding (RLNC) and store and forward (SAF) have been recently proposed. In this paper, we model different types of random network communications as the transmission of flats of matroids. This novel framework encompasses RLNC and SAF and allows us to introduce a novel protocol, referred to as random affine network coding (RANC), based on affine combinations of packets. Although the models previously proposed for RLNC and SAF only consider error control, using our framework, we first evaluate and compare the performance of different network protocols in the error-free case. We define and determine the rate, average delay, and throughput of such protocols, and we also investigate the possibilities of partial decoding before the entire message is received. We thus show that RANC outperforms RLNC in terms of data rate and throughput thanks to a more efficient encoding of messages into packets. Second, we model the possible alterations of a message by the network as an operator channel, which generalizes the channels proposed for RLNC and SAF. Error control is thus reduced to a coding-theoretic problem on flats of a matroid, where two distinct metrics can be used for error correction. We study the maximum cardinality of codes on flats in general, and codes for error correction in RANC in particular. We finally design a class of nearly optimal codes for RANC based on rank metric codes for which we propose a low-complexity decoding algorithm. The gain of RANC over RLNC is thus preserved with no additional cost in terms of complexity. [ABSTRACT FROM AUTHOR]

Protograph-based LDPC and generalized LDPC (G-LDPC) codes have the advantages of a simple design procedure and highly structured encoders and decoders. The design of such “protograph-based codes” relies on what is effectively a computer-based search. As such, following Gallager, it is prudent to restrict the search to a “good ensemble,” for example, an ensemble whose minimum distance grows linearly with codeword length. A good ensemble can also mean one with good stopping set, trapping set, or pseudocodeword properties. In this paper, ensemble codeword weight enumerators for finite-length LDPC and G-LDPC codes based on protographs were derived, and then the asymptotic case was considered. The asymptotic results allow us to determine whether or not the typical relative minimum distance in the ensemble grows linearly with codeword length. Then, the codeword weight enumerator technique is adapted to yield ensemble stopping set, trapping set, and pseudocodeword enumerators for protograph LDPC and G-LDPC codes. In this case, the asymptotic results allow us to determine whether or not the typical relative smallest stopping set size, trapping set size, and pseudoweight grows linearly with codeword length. Trapping set enumerators for G-LDPC code ensembles represent a more complex problem which we do not consider here. [ABSTRACT FROM AUTHOR]

In this paper, we study the zero-error capacity for finite state channels with feedback when channel state information is known to both the transmitter and the receiver. We prove that the zero-error capacity in this case can be obtained through the solution of a dynamic programming problem. Each iteration of the dynamic programming provides lower and upper bounds on the zero-error capacity, and in the limit, the lower bound coincides with the zero-error feedback capacity. Furthermore, a sufficient condition for solving the dynamic programming problem is provided through a fixed-point equation. Analytical solutions for several examples are provided. [ABSTRACT FROM AUTHOR]

In this paper, we consider the problem of coding for the half-duplex nonorthogonal amplify-and-forward (NAF) cooperative channel where the transmitter to relay and the interrelay links are highly reliable. We derive bounds on the diversity order of the NAF protocol that are achieved by a distributed space-time bit-interleaved coded modulation (D-ST-BICM) scheme under iterative APP detection and decoding. These bounds lead to the design of space-time precoders that ensure maximum diversity order and high coding gains. The word error rate performance of D-STBICM are also compared to outage probability limits. [ABSTRACT FROM AUTHOR]

The stabilizer method for constructing a class of asymmetric quantum codes (AQC), called additive AQC, has been established by Aly et al. In this paper, we present a new characterization of AQC, which generalizes a result of the symmetric case known previously. As an application of the characterization, we establish a relationship of AQC with classical error-correcting codes and show a few examples of good AQC with specific parameters. By using this relationship, we obtain an asymptotic bound on AQCs from algebraic geometry codes. [ABSTRACT FROM AUTHOR]

Codes in the projective space and codes in the Grassmannian over a finite field--referred to as subspace codes and constant-dimension codes (CDCs), respectively--have been proposed for error control in random linear network coding. For subspace codes and CDCs, a subspace metric was introduced to correct both errors and erasures, and an injection metric was proposed to correct adversarial errors. In this paper, we investigate the packing and covering properties of subspace codes with both metrics. We first determine some fundamental geometric properties of the projective space with both metrics. Using these properties, we then derive bounds on the cardinalities of packing and covering subspace codes, and determine the asymptotic rates of optimal packing and optimal covering subspace codes with both metrics. Our results not only provide guiding principles for the code design for error control in random linear network coding, but also illustrate the difference between the two metrics from a geometric perspective. In particular, our results show that optimal packing CDCs are optimal packing subspace codes up to a scalar for both metrics if and only if their dimension is half of their length (up to rounding). In this case, CDCs suffer from only limited rate loss as opposed to subspace codes with the same minimum distance. We also show that optimal covering CDCs can be used to construct asymptotically optimal covering subspace codes with the injection metric only. [ABSTRACT FROM AUTHOR]

In this paper, an ensemble analysis of the undetected error probability of a standard error detection scheme based on a sparse binary parity check matrix is presented. The Bernoulli ensemble, the members of which are considered to be matrices generated from an i.i.d. Bernoulli source, is primarily considered herein. The main contributions of the present study are (i) the derivation of the error exponent of the average undetected error probability and (ii) closed form expressions for the variance of the undetected error probability. The behavior of the exponent for an ensemble of sparse matrices is shown to be somewhat different from that for an ensemble of dense matrices. Furthermore, as a byproduct of the proof of the variance formula, a simple covariance formula of the weight distribution is derived. [ABSTRACT FROM AUTHOR]

We investigate error-correcting codes for a the rank-modulation scheme with an application to flash memory devices. In this scheme, a set of n cells stores information in the permutation induced by the different charge levels of the individual cells. The resulting scheme eliminates the need for discrete cell levels, overcomes overshoot errors when programming cells (a serious problem that reduces the writing speed), and mitigates the problem of asymmetric errors. In this paper, we study the properties of error-correcting codes for charge-constrained errors in the rank-modulation scheme. In this error model the number of errors corresponds to the minimal number of adjacent transpositions required to change a given stored permutation to another erroneous one--a distance measure known as Kendall's τ-distance. We show bounds on the size of such codes, and use metric-embedding techniques to give constructions which translate a wealth of knowledge of codes in the Lee metric to codes over permutations in Kendall's τ-metric. Specifically, the one-error-correcting codes we construct are at least half the ball-packing upper bound. [ABSTRACT FROM AUTHOR]

Several physical effects that limit the reliability and performance of multilevel flash memories induce errors that have low magnitudes and are dominantly asymmetric. This paper studies block codes for asymmetric limited-magnitude errors over q-ary channels. We propose code constructions and bounds for such channels when the number of errors is bounded by t and the error magnitudes are bounded by l. The constructions utilize known codes for symmetric errors, over small alphabets, to protect large-alphabet symbols from asymmetric limited-magnitude errors. The encoding and decoding of these codes are performed over the small alphabet whose size depends only on the maximum error magnitude and is independent of the alphabet size of the outer code. Moreover, the size of the codes is shown to exceed the sizes of known codes (for related error models), and asymptotic rate-optimality results are proved. Extensions of the construction are proposed to accommodate variations on the error model and to include systematic codes as a benefit to practical implementation. [ABSTRACT FROM AUTHOR]

One way to find near-matches in large datasets is to use hash functions. In recent years locality-sensitive hash functions for various metrics have been given; for the Hamming metric projecting onto k bits is simple hash function that performs well. In this paper, we investigate alternatives to projection. For various parameters hash functions given by complete decoding algorithms for error-correcting codes work better, and asymptotically random codes perform better than projection. [ABSTRACT FROM AUTHOR]

This paper is motivated by the problem of error control in network coding when errors are introduced in a random fashion (rather than chosen by an adversary). An additive-multiplicative matrix channel is considered as a model for random network coding. The model assumes that n packets of length m are transmitted over the network, and up to t erroneous packets are randomly chosen and injected into the network. Upper and lower bounds on capacity are obtained for any channel parameters, and asymptotic expressions are provided in the limit of large field or matrix size. A simple coding scheme is presented that achieves capacity in both limiting cases. The scheme has decoding complexity O(n²m) and a probability of error that decreases exponentially both in the packet length and in the field size in bits. Extensions of these results for coherent network coding are also presented. [ABSTRACT FROM AUTHOR]

In this paper, we present a practical approach to the iterative decoding of Reed-Solomon (RS) codes. The presented methodology utilizes an architecture in which the output produced by steps of belief-propagation (BP) is successively applied to a legacy decoding algorithm. Due to the suboptimal performance of BP conducted on the inherently dense RS parity-check matrix, a method is first provided for the construction of reduced-density, binary, parity-check equations. Iterative decoding is then conducted utilizing a subset of a redundant set of parity-check equations to minimize the number of connections into the least-reliable bits. Simulation results show that performance comparable to (and exceeding) the best known practical RS decoding techniques is achievable with the presented methodology. The complexity of the proposed algorithm is significantly lower than these existing procedures and permits a practical implementation in hardware. [ABSTRACT FROM AUTHOR]

Codes for error detection on a q-ary symmetric channel are studied. Whether a code is good or not for error detection (in the technical sense) depends on the structure of the code. For some combinations of the main parameters length, size, and minimum distance, all code are good and for some other combinations all are ugly (stronger than not good). The purpose of this paper is to give bounds on the parameters for codes that are not good for error detection. In particular, it is shown that if the minimum distance is below some bound, which depends on the length and size of the code as well as a lower bound on the number of codewords of minimum distance, then the code is ugly and, hence, not good for error detection. [ABSTRACT FROM AUTHOR]

Randomized linear network code for single source muiticast was introduced and analyzed in Ho et ai. (IEEE Transactions on Information Theory, October 2006) where the main results are upper bounds for the failure probability of the code. In this paper, these bounds are improved and tightness of the new bounds is studied by analyzing the limiting behavior of the failure probability as the field size goes to infinity. In the linear random coding setting for single source multicast, the minimum distance of the code defined in Zhang, (IEEE Transactions on Information Theory, January 2008) is a random variable taking nonnegative integer values that satisfy the inequality in the Singleton bound recently established in Yeung and Cai (Communications in Information and Systems, 2006) for network error correction codes. We derive a bound on the probability mass function of the minimum distance of the random linear network code based on our improved upper bounds for the failure probability. Codes having the highest possible minimum distance in the Singleton bound are called maximum distance separable (MDS). The bound on the field size required for the existence of MDS codes reported in Zhang, (IEEE Transactions on Information Theory, January 2008) and Matsumoto (arXiv:cs.IT/0610121, Oct. 2006) suggests that such codes exist only when field size is large. Define the degradation of a code as the difference between the highest possible minimum distance in the Singleton bound and the actual minimum distance of the code. The bound for the probability mass function of the minimum distance leads to a bound on the field size required for the existence of network error correction codes with a given maximum degradation. The result shows that allowing minor degradation reduces the field size required dramatically. [ABSTRACT FROM AUTHOR]

In this paper, the error-correction capability of column-weight-three low-density parity-check (LDPC) codes when decoded using the Gallager A algorithm is investigated. It is proved that a necessary condition for a code to correct all error patterns with up to k ≥ 5 errors is to avoid cycles of length up to 2k in its Tanner graph. As a consequence of this result, it is shown that given any α > 0, ∃ N such that ∀ n > N, no code in the ensemble of column-weight-three codes can correct all αn or fewer errors. The results are extended to the bit flipping algorithms. [ABSTRACT FROM AUTHOR]

In an earlier work, the statistical physics associated with finite-temperature decoding of code ensembles, along with the relation to their random coding error exponents, were explored in a framework that is analogous to Derrida's random energy model (REM) of spin glasses, according to which the energy levels of the various spin configurations are independent random variables. The generalized REM (GREM) extends the REM in that it introduces correlations between energy levels in an hierarchical structure. In this paper, we explore some analogies between the behavior of the GREM and that of code ensembles which have parallel hierarchical structures. In particular, in analogy to the fact that the GREM may have different types of phase transition effects, depending on the parameters of the model, then the above-mentioned hierarchical code ensembles behave substantially differently in the various domains of the design parameters of these codes. We make an attempt to explore the insights that can be imported from the statistical mechanics of the GREM and be harnessed to serve for code design considerations and guidelines. [ABSTRACT FROM AUTHOR]

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. [ABSTRACT FROM AUTHOR]

The performance of bit-interleaved coded modulation (BICM) with (or without) iterative decoding (ID) is significantly influenced by the mapping of bits to the symbol constellation. Our main objective in this paper is to develop a systematic design approach for BICM-ID schemes, ensuring the best possible performance with iterative decoding. Although useful mappings for BICM-ID have been found based on various search strategies, no attempt has been made to systematically enumerate and classify all unique mappers for a given constellation. As the basis for a systematic enumeration and classification, we define the average bit-wise distance spectrum for a mapping from bits to symbols. Different bit-wise distance spectra are derived assuming no prior information or full prior information, respectively. The bit-wise distance spectra determine corresponding bit-wise error probability and bit-wise mutual information. The latter allows us to use the classification of mappings with unique bit-wise distance spectra to also classify mappings with unique extremal points in the corresponding extrinsic information transfer (EXIT) curves. As an example of our approach, we classify 8PSK mappings into 86 classes of unique mappings according to bit-wise distance spectra. The classification can be used to significantly reduce the complexity of the search for suitable mappers for BICM-ID. For 8PSK and a given encoder, only 86 different mappings need to be investigated. As examples of the systematic design approach, the best 8PSK mappings for minimizing the convergence threshold are found for concatenation with the rate 1/2 (5, 7)8 and (133,171)8 convolutional codes, and the rate 1/2 UMTS turbo code with identical constituent convolutional codes (15/ 13)8. [ABSTRACT FROM AUTHOR]

The iterative decoding threshold of low-density parity-check (LDPC) codes over the binary erasure channel (BEC) fulfills an upper bound depending only on the variable and check nodes with minimum distance 2. This bound is a consequence .of the stability condition, and is here referred to as stability bound. In this paper, a stability bound over the BEC is developed for doubly-generalized LDPC codes, where variable and check nodes can be generic linear block codes, assuming maximum a posteriori erasure correction at each node. It is proved that also in. this generalized context the bound depends only on the variable and check component codes with minimum distance 2. A condition is also developed, namely, the derivative matching condition, under which the bound is achieved with equality. The stability bound leads to consider single parity-check codes used as variable nodes as an appealing option to overcome common problems created by generalized check nodes. [ABSTRACT FROM AUTHOR]

The existence of a perfect 1-factorization of the complete graph with n nodes, namely, Kn, for arbitrary even number n, is a 40-year-old open problem in graph theory. So far, two infinite families of perfect 1-factorizations have been shown to exist, namely, the factorizations of Kp+1 and K2p, where p is an arbitrary prime number (p > 2). It was shown in previous work that finding a perfect 1-factorization of Kn is related to a problem in coding, specifically, it can be reduced to constructing an MDS (Minimum Distance Separable), lowest density array code. In this paper, a new method for shortening arbitrary array codes is introduced. It is then used to derive the Kp+1 family of perfect 1-factorization from the K2p family. Namely, techniques from coding theory are used to prove a new result in graph theory—that the two factorization families are related. [ABSTRACT FROM AUTHOR]

In this paper, we introduce a general framework for treating channels with memory and feedback. First, we prove a general feedback channel coding theorem based on Massey's concept of directed information. Second, we present coding results for Markov channels. This requires determining appropriate sufficient statistics at the encoder and decoder. We give a recursive characterization of these sufficient statistics. Third, a dynamic programming framework for computing the capacity of Markov channels is presented. Fourth, it is shown that the average cost optimality equation (ACOE) can be viewed as an implicit single-letter characterization of the capacity. Fifth, scenarios with simple sufficient statistics are described. Sixth, error exponents for channels with feedback are presented. [ABSTRACT FROM AUTHOR]