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     

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     

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     

On optimum time-hopping patterns

Time-hopping patterns can be constructed from simple difference sets. By studying such constructions, it has been proven that whenever n-2, n-1, or n+1 is a prime power, then time-hopping patterns that have n terms can be constructed and are of length less than n². By computation it is shown that such patterns can have length less than n²-n^1.44 for all n⩽150. It is also shown that time-hopping patterns for n terms can have length less than n²+O(n^1.55) for all n     

Minimum distance of logarithmic and fractional partialm-sequences

Two results are presented concerning the partial periods (p-p's) of an m-sequence of period 2ⁿ-1. The first proves the existence of an m-sequence whose p-p's of length approximately (n+d log₂ n) have minimum distance between d and 2d for small d. The second result is of an asymptotic nature and proves that the normalized minimum distance of p-p's whose length is any fraction of the period of the m-sequence, approaches 1/2 as the period of m-sequence tends to infinity     

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     

On the LP which finds a MMAE stack filter

Two methods are proposed to modify the linear program (LP) developed by E.J. Coyle and J.-H. Lin (1988) to find a stack filter which minimizes the mean absolute error (MAE). In the first approach, the number of constraints is substantially reduced at the expense of requiring a zero-one LP to solve for an optimal filter. This scheme reduces the number of constraints from O(n2ⁿ) to O(28ⁿ), which is exactly the cardinality of the set of possible binary vectors which can appear in the window of the filter. In the second approach, the LP is transformed into a max-flow problem. This guarantees that the problem can be solved in time which is a polynomial function of the number of variables in the LP, as opposed to the worst-case exponential time that may occur with the simplex method. It also allows the many fast algorithms for the max-flow problem to be used to find an optimal stack filter. Recursive algorithms for construction of the window width n constraint matrix for both the original LP and the max-flow modification are also provided     

Optimal replacement policies for k-out-of-nsystems

The authors study a discrete-time, infinite-horizon, dynamic programming model for the replacement of components in a binary k -out-of-n:F system. The goal is to trade off the component replacement and system failure costs. Under the criterion of minimizing the long-run average cost per period, it is optimal to follow a critical component policy (CCP), viz., a policy specified by a critical component set and the rule: replace a component if and only if it is failed and is in the critical component set. Computing an optimal CCP is a binary nonlinear programming problem, which can be solved by searching through a set with O(n^k-1) points. This approach to finding an optimal CCP is practical when k is small. In particular, assuming s-independent components, it requires O(n^2k-1) calculations. The authors analyze in detail the two most important cases with small k: the series (1-out-of-n:F) system and the 2-out-of-n:F system     

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     

A (16, 9, 6, 5, 4) error-correcting DC free block code

A (2n, k, l, c, d) DC free binary block code is a code of length 2n, constant weight n, 2^k codewords, maximum runlength of a symbol l , maximum accumulated charge c, and minimum distance d . The purpose of this code is to achieve DC freeness and error correction at the same time. The goal is to keep the rate k/2 n and d large and l and c small. Of course, these are conflicting goals. H.C. Ferreira (IEEE Trans. Magn., vol.MAG-20, no.5, p.881-3, 1984) presented a (16, 8, 8, 5, 4) DC free code. Here, a (16, 9, 6, 5, 4) DC free code is presented. Easy encoding and decoding algorithms are also given     

Bounds for abnormal binary codes with covering radius one

The normality of binary codes is studied. The minimum cardinality of a binary code of length n with covering radius R is denoted by K(n,R). It is assumed that C is an (n,M)R code, that is, a binary code of length n with M codewords and covering radius R. It is shown that if C is an (n,M)1 code, then it is easy to find a normal (n ,M)1 code by changing C in a suitable way, and that all the optimal (n,M)1 codes (i.e. those for which M=K(n,1)) are normal and their every coordinate is acceptable. It is shown that if C is an abnormal (n,M) code, then n⩾9, and an abnormal (9118)1 code which is the smallest abnormal code known at present, is constructed. Lower bounds on the minimum cardinality of a binary abnormal code of length n with covering radius 1 are derived, and it is shown that if an (n,M)1 code is abnormal, then M⩾96     

Fast decoding of codes from algebraic plane curves

Improvement to an earlier decoding algorithm for codes from algebraic geometry is presented. For codes from an arbitrary regular plane curve the authors correct up to d*/2-m² /8+m/4-9/8 errors, where d* is the designed distance of the code and m is the degree of the curve. The complexity of finding the error locator is O(n^7/3 ), where n is the length of the code. For codes from Hermitian curves the complexity of finding the error values, given the error locator, is O(n²), and the same complexity can be obtained in the general case if only d*/2-m²/2 errors are corrected     

Repeated-root cyclic codes

In the theory of cyclic codes, it is common practice to require that (n,q)=1, where n is the word length and F_q is the alphabet. It is shown that the even weight subcodes of the shortened binary Hamming codes form a sequence of repeated-root cyclic codes that are optimal. In nearly all other cases, one does not find good cyclic codes by dropping the usual restriction that n and q must be relatively prime. This statement is based on an analysis for lengths up to 100. A theorem shows why this was to be expected, but it also leads to low-complexity decoding methods. This is an advantage, especially for the codes that are not much worse than corresponding codes of odd length. It is demonstrated that a binary cyclic code of length 2n (n odd) can be obtained from two cyclic codes of length n by the well-known | u|u+v| construction. This leads to an infinite sequence of optimal cyclic codes with distance 4. Furthermore, it is shown that low-complexity decoding methods can be used for these codes. The structure theorem generalizes to other characteristics and to other lengths. Some comparisons of the methods using earlier examples are given     

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)     

Design of C-testable DCVS binary array dividers

Clocked differential cascode voltage switch (DCVS) circuits are dynamic CMOS circuits that have the advantage of being protected against test-set invalidation due to circuit delays and timing skews. The problem of testing nonrestoring and restoring DCVS binary array dividers is discussed. It is shown that a DCVS nonrestoring array divider can be made C-testable with only four or five vectors. These vectors detect all the detectable single stuck-at, stuck-open, and stuck-on faults in the circuit. The additional hardware required to achieve C-testability for an n×n nonrestoring array divider only consists of n-1 two-input XOR gates and one control input. It is also shown that a restoring DCVS binary array divider can be made C-testable with only six vectors, which also detect all the detectable single stuck-at, stuck-open, and stuck-on faults in the circuit. The hardware overhead required for the C-testable design of the n×n restoring array divider consists of n two-input XOR gates and one control input     

Studying the locator polynomials of minimum weight codewords of BCHcodes

Primitive binary cyclic codes of length n=2^m are considered. A BCH code with designed distance δ is denoted B(n,δ). A BCH code is always a narrow-sense BCH code. A codeword is identified with its locator polynomial, whose coefficients are the symmetric functions of the locators. The definition of the code by its zeros-set involves some properties for the power sums of the locators. Moreover, the symmetric functions and the power sums of the locators are related to Newton's identities. An algebraic point of view is presented in order to prove or disprove the existence of words of a given weight in a code. The principal result is the true minimum distance of some BCH codes of length 255 and 511. which were not known. The minimum weight codewords of the codes B(n2^h -1) are studied. It is proved that the set of the minimum weight codewords of the BCH code B(n,2^m-2-1) equals the set of the minimum weight codewords of the punctured Reed-Muller code of length n and order 2, for any m     

Binary [18,11]2 codes do not exist-Nor do [64,53]2 codes

A binary, linear block code C with block length n and dimension n is commonly denoted by [n, k] or, if its minimum distance is d, by [n, k,d]. The code's covering radius r(C) can be defined as the smallest number r such that any binary column vector of length (n-k) can be written as a sum of r or fewer columns of a parity-check matrix of C. An [n,k] code with covering radius r is denoted by [n,k]r. R.A. Brualdi et al., (1989) showed that l(m,r) is defined to be the smallest n such that an [n,n-m]r code exists. l(m,2) is known for m⩽6, while it is shown by Brualdi et al. that 17⩽l(7,2)⩽19. This lower bound is improved by A.R. Calderbank et al. (1988), where it is shown that [17,10]2 codes do not exist. The nonexistence of [18,11]2 codes is proved, so that l(7,2)=19. l[7.2)=19 is established by showing that [18,11]2 codes do not exist. It is also shown that [64,53]2 codes do not exist, implying that l(11,2)⩾65     

New minimum distance bounds for certain binary linear codes

Let an [n, k, d]-code denote a binary linear code of length n, dimension k, and minimum distance at least d. Define d(n, k) as the maximum value of d for which there exists a binary linear [n, k, d]-code. T. Verhoeff (1989) has provided an updated table of bounds on d(n, k) for 1⩽k⩽n⩽127. The authors improve on some of the upper bounds given in that table by proving the nonexistence of codes with certain parameters     

Reliability polynomial for a ring network

A mathematical model is developed for the reliability of a system made up of m unreliable nodes arranged in a ring. The model can be used to calculate the reliability of single-ring networks in which the network recovery mechanism depends on bypassing failed stations, but link signal power margins are inadequate to overcome losses due to more than n bypass switches in series. Computational complexity is 0(n²m+nm²/2) in time, and 0(m²/2) in memory requirements