Lower bounds for q-ary covering codes

The authors prove combinatorial lower bounds for K_q (n,R), the minimal cardinality of any q-ary code of length n and covering radius R. Tables of lower bounds for K_q(n,R) are presented for q=3, 4, 5     

Confidence bounds for Pr{X>Y} in 1-way ANOVArandom model

Approximate confidence bounds for reliability, R=Pr{X >Y|X,Y}, are obtained, where X and Y are independent normal (Gaussian) random variables, and X and Y are vectors of measurements for X and Y, respectively. Balanced 1-way ANOVA (analysis of variants) random effect models are assumed for the populations of X and Y. Confidence bounds are derived for R under three cases for standard deviations, σ_x and σ_y. An example shows how the results are used     

Error-correcting codes for list decoding

In the list-of-L decoding of a block code the receiver of a noisy sequence lists L possible transmitted messages, and is in error only if the correct message is not on the list. Consideration is given to (n,e,L) codes, which correct all sets of e or fewer errors in a block of n bits under list-of-L decoding. New geometric relations between the number of errors corrected under list-of-1 decoding and the (larger) number corrected under list-of-L decoding of the same code lead to new lower bounds on the maximum rate of (n,e,L) codes. They show that a jammer who can change a fixed fraction p<1/2 of the bits in an n-bit linear block code cannot prevent reliable communication at a positive rate using list-of- L decoding for sufficiently large n and an L⩽n. The new bounds are stronger for small n , but weaker for fixed e/n in the limit of large n and L than known random coding bounds     

New lower bounds for covering codes

Some new lower bounds on |C| for a binary linear [n, k]R code C with n+1=t(R +1)-r(0⩽r<R+1, t>2 odd) or with n+1=t(R+1)-1(t>2 even) are obtained. These bounds improve the sphere covering bound considerably and give several new values and lower bounds for the function t[n, k], the smallest covering radius of any [n, k] code     

Counting the number of minimum cuts in undirected multigraphs

The problem of counting the number of cuts with the minimum cardinality in an undirected multigraph arises in various applications, such as testing the super-λ-ness of a graph, as described by F.T. Boesch (1986), and calculating upper and lower bounds on the probabilistic connectedness of a stochastic graph G in which edges are subject to failure. It is shown that the number |C( G)| of cuts with the minimum cardinality λ(G) in a multiple graph G=(V,E) can be computed in O(|E|+λ(G)|V|² +λ(G)|C(G)||V|) time     

Secret key agreement by public discussion from common information

The problem of generating a shared secret key S by two parties knowing dependent random variables X and Y, respectively, but not sharing a secret key initially, is considered. An enemy who knows the random variable Z, jointly distributed with X and Y according to some probability distribution P_XYZ, can also receive all messages exchanged by the two parties over a public channel. The goal of a protocol is that the enemy obtains at most a negligible amount of information about S. Upper bounds on H(S) as a function of P_XYZ are presented. Lower bounds on the rate H (S)/N (as N→∞) are derived for the case in which X=[X₁, . . ., X _N], Y=[Y₁, . . ., Y_N] and Z=[Z₁, . . ., Z_N] result from N independent executions of a random experiment generating X_i, Y_i and Z_i for i=1, . . ., N. It is shown that such a secret key agreement is possible for a scenario in which all three parties receive the output of a binary symmetric source over independent binary symmetric channels, even when the enemy's channel is superior to the other two channels     

Lower bounds on the capacities of binary and ternary networksstoring sparse random vectors

It is shown that the memory capacity of networks of binary neurons storing, by the Hebbian rule, sparse random vectors over the field {0, 1}^N is at least c(N/p log N ), where c is a positive scalar involving input error probabilities probability of an element being nonzero. A similar bound is derived for networks of ternary neurons, storing sparse vectors over {-1,0,1}^N. These results, pertaining to stability and error correction with probability tending to one as the number of neurons tends to infinity, generalize and extend previously known capacity bounds for binary networks storing vectors of equally probable {±1} bits. Lower bounds on the capacities of binary and ternary networks of finite sizes are also derived. These bounds suggest critical network sizes that guarantee high gains in capacity per neuron for given sparsites     

Bounds and constructions of disjoint sets of distinct differencesets

An (I,J)-DDD is a set of I disjoint sets of distinct difference sets each having J elements. A number of constructions are given. Upper and lower bounds on the maximal element in a DDD (disjoint distinct difference) set are given. It is shown that regular DDD sets exist for I≳4J     

Bounding the capacity of saturation recording: the Lorentz modeland applications

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

Index system and separability of constant weight Gray codes

A number system is developed for the conversion of natural numbers to the codewords of the Gray code G(n,k) of length n and weight k, and vice versa. The focus is on the subcode G(n,k) of G(n) consisting of those words of G(n) with precisely k 1-bits, 0<k<n. This code is called the constant weight Gray code of length n and weight k. As an application sharp lower and upper bounds are derived for the value of |i-j|, where i and j are indices of codewords g_i and g_j of G(n,k) such that they differ in precisely 2 m bits     

Simple bounds on the extreme eigenvalues of Toeplitz matrices

Simple bounds are presented on the extreme eigenvalues of n ×n-dimensional Hermitian Toeplitz matrices. Such a matrix, say T_n, is determined by its first row. The proposed bounds have low complexity O(n); furthermore, examples are presented for which the proposed bounds are tighter than the Slepian-Landau bounds at their best, i.e. when the extreme eigenvalues of the submatrix obtained by deleting the first row and first column of T_n are known exactly. The bounds are first presented on the extreme eigenvalues of Hermitian Toeplitz matrices: the corresponding bounds for real symmetric Toeplitz matrices follow as a special case. Then, these bounds are extended to Hermitian Toeplitz interval matrices     

Improved sphere bounds on the covering radius of codes

The sphere bound is a trivial lower bound on K(n,R), the minimal cardinality of any binary code of length n and with covering radius R. By simple arguments it is considerably improved, to K(n,1)⩾2 ⁿ/n for n even. A table of lower and upper bounds on K(n,R) for n⩽33, R ⩽10 is included     

Information rates for a discrete-time Gaussian channel withintersymbol interference and stationary inputs

Bounds are presented on I_i.i.d.-the achievable information rate for a discrete Gaussian Channel with intersymbol interference (ISI) present and i.i.d. channel input symbols governed by an arbitrary predetermined distribution p_x(x). The lower and upper bounds on I _i.i.d. and I are formulated. The bounds on I_i.i.d. are calculated for independent equiprobably binary channel symbols and for causal channels with ISI memory of degree one and two. The bounds on I_i.i.d. are compared to the approximated (by Monte Carlo methods) known value of I_i.i.d. and their tightness is considered. An application of the new lower bound on I_i.i.d. yields an improvement on previously reported lower bounds for the capacity of the continuous-time strictly bandlimited (or bandpass) Gaussian channel with either peak or simultaneously peak power and bandlimiting constraints imposed on the channel's input waveform     

Exact lower bounds on the codelength of three-steppermutation-decodable cyclic codes

The exact lower bounds on codelength n for three-step ( T, U) permutation decodable binary cyclic codes of even-valued error number t (t⩾4) are presented. Since the derivation of these results involves only the error position, the results are applicable to cyclic codes over GF(2^m)     

Information rates for magnetic recording channels with peak- andslope-limited magnetization

A model for magnetic recording is proposed which uses two parameters to describe the limitations on the remanent magnetization in the medium: the dimensionless peak value A_m and the steepest slope B(s^-1). A low-pass bandwidth restriction W(s^-1) due to read circuits is also included. Lower and upper bounds on the achievable transmission rates are derived in terms of the signal-to-noise ratio. For the case of ideal low-pass restriction with B≪W, the bounds increase linearly, logarithmically, and as the cube root, with low, medium, and large ρ_B, respectively. With B≪ W the problem reduces to the one with no restriction on the slope     

Bounds on maximum throughput for digital communications withfinite-precision and amplitude constraints

The problem of finding the maximum achievable data rate over a linear time-invariant channel is considered under constraints different from those typically assumed. The limiting factor is taken to be the accuracy with which the receiver can measure the channel output. More precisely, the following problem is considered. Given a channel with known impulse response h(t), a transmitter with an output amplitude constraint, and a receiver that can distinguish between two signals only if they are separated in amplitude at some time t ₀ by at least some small positive constant d, what is the maximum number of messages, N_max, that can be transmitted in a given time interval [0,T]? Lower bounds on N_max can be easily computed by constructing a particular set of inputs to the channel. The main result is an upper bound on N_max for arbitrary h(t). The upper bound depends on the spread of h(t), which is the maximum range of values the channel output may take at some time t₀>0 given that the output takes on a particular value α at time t=0. Numerical results are shown for different impulse responses, including two simulated telephone subscriber loop impulse responses     

Bounds for reliability of consecutivek-within-m-out-of-n:F systems

Upper and lower bounds for the reliability of a (linear or circular) consecutive k-within-m-out-of-n:F system with unequal component-failure probabilities are provided. Numerical calculations indicate that, for systems with components of good enough reliability, these bounds quite adequately estimate system reliability. The estimate is easy to calculate, having computational complexity O(m²×n). For identically distributed components, a Weibull limit theorem for system time-to-failure is proved     

On multilevel block modulation codes

The multilevel technique for combining block coding and modulation is investigated. A general formulation is presented for multilevel modulation codes in terms of component codes with appropriate distance measures. A specific method for constructing multilevel block modulation codes with interdependency among component codes is proposed. Given a multilevel block modulation code C with no interdependency among the binary component codes, the proposed method gives a multilevel block modulation code C' that has the same rate as C, a minimum squared Euclidean distance not less than that of C, a trellis diagram with the same number of states as that of C, and a smaller number of nearest neighbor codewords than that of C . Finally, a technique is presented for analyzing the error performance of block modulation codes for an additive white Gaussian noise (AWGN) channel based on soft-decision maximum likelihood decoding. Error probabilities of some specific codes are evaluated by simulation and upper bounds based on their Euclidean weight distributions     

Bounds and constructions for codes correcting unidirectional errors

A brief introduction is given on the theory of codes correcting unidirectional errors, in the context of symmetric and asymmetric error-correcting codes. Upper bounds on the size of a code of length n correcting t or fewer unidirectional errors are then derived. Methods in which codes correcting up to t unidirectional errors are constructed by expurgating t-fold asymmetric error-correcting codes or by expurgating and puncturing t -fold symmetric error-correcting codes are also presented. Finally, tables summarizing some results on the size of optimal unidirectional error-correcting codes which follow from these bounds and constructions are given     

New ternary line codes based on trellis structure

The trellis coding technique is applied to line-coded baseband digital transmission systems. For R=n/n+1(n=1,2,3) coding rates, a new codeword assignment model is proposed to accomplish basic requirements for line coding in which each length n binary data sequence is encoded into a length n+1 ternary (+,0,-) line codeword chosen among the code alphabet with 2ⁿ⁺² elements. Assuming Viterbi decoding, the system error performance is improved by increasing the free Euclidean distance between coded sequences. A new algorithm is given for the calculation of the free distance between line-coded sequences so obtained. For R=1/2 and R=3/4 rates, the analytical error performance upper bounds are derived. The power spectral densities of the new line codes are also calculated and compared with those of known line codes