Balancing sets of vectors

For n>0, d⩾0, n≡d (mod 2), let K(n, d) denote the minimal cardinality of a family V of ±1 vectors of dimension n, such that for any ±1 vector w of dimension n there is a v∈V such that |v- w|⩽d, where v-w is the usual scalar product of v and w. A generalization of a simple construction due to D.E. Knuth (1986) shows that K(n , d)⩽[n/(d+1)]. A linear algebra proof is given here that this construction is optimal, so that K(n, d)-[n/(d+1)] for all n≡d (mod 2). This construction and its extensions have applications to communication theory, especially to the construction of signal sets for optical data links     

Constructions of error-correcting DC-free block codes

Two DC-free codes are presented with distance 2d, b ⩾1 length 2n+2r(d-1) for d⩽3 and length 2n+2r(d-1)(2d -1) for d>3, where r is the least integer ⩾log₂ (2n+1). For the first code l=4, c=2, and the asymptotic rate of this code is 0.7925. For the second code l=6, c=3, and the asymptotic rate of this code is 0.8858. Asymptotically, these rates achieve the channel capacity. For small values of n these codes do not achieve the best rate. As an example of codes of short length with good rate, the author presents a (30, 10, 6, 4) DC-free block code with 2²¹ codewords. A construction is presented for which from a given code C ₁ of length n, even weight, and distance 4, the author obtains a (4n, l, c, 4) DC-free block code C₂, where l is 4, 5 or 6, and c is not greater than n+1 (but usually significantly smaller). The codes obtained by this method have good rates for small lengths. The encoding and decoding procedures for all the codes are discussed     

Limiting efficiencies of burst-correcting array codes

The author evaluates the limiting efficiencies e(-S ) of burst-correcting array codes A(n₁,n₂, -s) for all negative readouts -s as n₂ tends to infinity and n₁ is properly chosen to maximize the efficiency. Specializing the result to the products of the first i primes donated by s_i (1⩽i<∞), which are optimal choices for readouts, gives the expression e(-s_i)=(2p_i+1 -2)/(2p_i+1-1) where p_i+1 is the next prime. Previously, it was known only that e(-2)⩾4/5 and e(-1)⩾2/3. This result reveals the existence of burst-correcting array codes with efficiencies arbitrarily close to 1 and with rates also arbitrarily close to 1     

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     

Optimality property of the Gaussian window spectrogram

It is shown that for any signal x(t) the minimum of ∫_-∞^∞∫_-∞ ^∞ [(t-t_x)²+(f-f _x)²] S_x^(w)(t , f) dt df over all normalized time-windows w(t) is achieved by the Gaussian window w(t)=2^1/4 exp (-πt²). Here (t_x, f _x) is the center of gravity of the signal x(t ), S_x^(w) (t, f) is the spectrogram of x(t) due to the window w( t), and the double integral is a measure of the spread of S _x^(w) (t, f) around (t _x, f_X) in the time-frequency plane     

Capacity of the Gaussian arbitrarily varying channel

The Gaussian arbitrarily varying channel with input constraint Γ and state constraint Λ admits input sequences x=(x₁,---,X_n) of real numbers with Σx_i²⩽nΓ and state sequences s=(S₁,---,s_n ) of real numbers with Σs_i²⩽nΛ; the output sequence x+s+V, where V=(V₁,---,V_n) is a sequence of independent and identically distributed Gaussian random variables with mean 0 and variance σ². It is proved that the capacity of this arbitrarily varying channel for deterministic codes and the average probability of error criterion equals 1/2 log (1+Γ/(Λ+σ²)) if Λ<Γ and is 0 otherwise     

Bounds on the undetected error probabilities of linear codes forboth error correction and detection

The author investigates the (n, k, d⩾2t+1) binary linear codes, which are used for correcting error patterns of weight at most t and detecting other error patterns over a binary symmetric channel. In particular, for t=1, it is shown that there exists one code whose probability of undetected errors is upper-bounded by (n+1) [2^n-k-n]^-1 when used on a binary symmetric channel with transition probability less than 2/n     

Bayes estimation of reliability under a random environment governedby a Dirichlet prior

The reliability function of a component whose lifetime is exponentially distributed with a known parameter λ>0 is R (t|λ)=exp (-λt). If an environmental effect multiplies the parameter by a positive factor η, then the reliability function becomes R(t|η,λ)=exp(-ηλt). The authors assume that η itself is random, and its uncertainty is described by a Dirichlet process prior D(α) with parameter α=MG₀, where M>O represents an intensity of assurance in the prior guess, G₀, of the (unknown) distribution of η. Under squared error loss, the Bayes estimator of R(t|η,λ) is derived both for the no-sample problem and for a sample of size n. Using Monte Carlo simulation, the effects of n, M, G₀ on the estimator are studied. These examples show that: (a) large values of n lead to estimates where the data outweigh the prior, and (b) large values of M increase the contribution of the prior to the estimates. These simulation results support intuitive ideas about the effect of environment and lifetime parameters on reliability     

Optimum codes of dimension 3 and 4 over GF(4)

n_q(k,d), the length of a q-ary optimum code for given k and d, for q=4 and k=3, 4 is discussed. The problem is completely solved for k=3, and the exact value of n₄(4,d) is determined for all but 52 values of d     

Optimal probability-of-error thresholds and performance for twoversions of the sign detector

Expressions are obtained for specifying the optimal error probability (minimum P_e) thresholds λ₀₁ and λ₀₂ for the traditional and modified sign detectors, respectively. These thresholds are shown to depend on the parameters p, P₁, and M where: M is the number of observations z_i used in the test statistic; P₁=P(H₁ ) is the prior probability for hypothesis H₁ that signal s₁ is present and 1-P₁ =P(H₀) corresponds to the hypothesis H₀ that signal s₀ is present; and p=Pr{z_i⩾0|H₁} with s₀=0 for the traditional sign detector and p=Pr{z_i⩾λ|H₁ }=Pr{z_i<λ|H₀} with λ =(s₀+s₁)/2 for the modified sign detector. The expressions for λ₀₁ and λ₀₂, are given explicitly, and shown to be independent of P₁ for sufficiently large M. Optimal P_e versus M performance curves, corresponding to both versions of the sign detector, are obtained for a representative range of values for p and P₁     

Focused codes for channels with skewed errors

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

A dispersion formula satisfying recent requirements in microstripCAD

A dispersion formula ϵ^*_eff(f)=ϵ^* -{ϵ^*-ϵ^*_eff(0)}/{1+( f/f₅₀)^m}, for the effective relative permittivity ϵ^*_eff(f) of an open microstrip line is derived for computer-aided design (CAD) use. The 50% dispersion point (the frequency f₅₀ at which ϵ^*_eff(f₅₀)={ϵ ^*+ϵ^*_eff(0)}/2}) is used a normalizing frequency in the proposed formula, and an expression for f₅₀ is derived. To obtain the best fit of ϵ ^*_eff(f) to the theoretical numerical model, the power m of the normalized frequency in the proposed formula is expressed as a function of width-to-height ratio w/ h for w/h⩾0.7 and as a function of w /h, f₅₀, and f for w/h⩽0.7. The present formula has a high degree of accuracy, better than 0.6% in the range 0.1<w/h⩽10, 1<ϵ^*⩽128, and any height-to-wavelength ratio h/λ₀     

Identities and approximations for the weight distribution of q-ary codes

An explicit formula is derived that enumerates the complete weight distribution of an (n, k, d) linear code using a partially known weight distribution. An approximation formula for the weight distribution of q-ary linear (n, k , d) codes is also derived. It is shown that, for a given q-ary linear (n, k, d) code, the ratio of the number of codewords of weight u to the number of words of weight u approaches the constant Q=q ^-(n-k) as u becomes large. The error term is a decreasing function of the minimum weight of the dual. The results are also valid for nonlinear (n, M, d) codes with the minimum weight of the dual replaced by the dual distance     

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     

New lower bounds for constant weight codes

Some new lower bounds are given for A(n,4,w ), the maximum number of codewords in a binary code of length n , minimum distance 4, and constant weight w. In a number of cases the results significantly improve on the best bounds previously known     

On the number of memories that can be perfectly stored in a neuralnet with Hebb weights

Let {w_ij} be the weights of the connections of a neural network with n nodes, calculated from m data vectors v¹, ···, v^m in {1,-1}ⁿ, according to the Hebb rule. The author proves that if m is not too large relative to n and the v^k are random, then the w_ij constitute, with high probability, a perfect representation of the v^k in the sense that the v ^k are completely determined by the w_ij up to their sign. The conditions under which this is established turn out to be less restrictive than those under which it has been shown that the v^k can actually be recovered by letting the network evolve until equilibrium is attained. In the specific case where the entries of the v^k are independent and equal to 1 or -1 with probability 1/2, the condition on m is that m should not exceed n/0.7 log n     

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     

A family of efficient burst-correcting array codes

A family of binary burst correcting array codes that are defined as follows is discussed: consider an n₁×n n₂ array with n₁=4u+ν+2 and n₂=6u+2ν+5, u⩾1, ν⩾0, ν≠1 where each row and column has even parity. The bits are read diagonally starting from the upper-left corner. The columns are viewed cyclically, i.e. the array is a cylinder. If one diagonal has been read out, one proceeds with the second diagonal preceding it. It is proven that the codes of this type can correct any burst of length up to n₁. The burst-correcting efficiency of this family tends to 4/5 as u→∞. As a comparison, the burst-correcting efficiency of other families of array codes tends to 2/3; the same is true for Fire codes. A simple decoding algorithm for the codes is also presented     

Decoding geometric Goppa codes using an extra place

Decoding geometric Goppa codes can be reduced to solving the key congruence of a received word in an affine ring. If the codelength is smaller than the number of rational points on the curve, then this method can correct up to 1.2 (d*-L)/2-s errors, where d* is the designed minimum distance of the code and s is the Clifford defect. The affine ring with respect to a place P is the set of all rational functions which have no poles except at P, and it is somehow similar to a polynomial ring. For a special kind of geometric Goppa code, namely C_Ω(D,mP), the decoding algorithm is reduced to solving the key equation in the affine ring, which can be carried out by the subresultant sequence in the affine ring with complexity O(n³), where n is the length of codewords