A construction of non-Reed-Solomon type MDS codes

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

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     

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     

A linear bound for sliding-block decoder window size

The author gives an upper bound on the necessary length of a sliding-block decoder window for finite-state codes from arbitrary n -ary data into any constrained system Σ with capacity at least log(n) presented by a graph G with memory m and anticipation a. Specifically, it is shown that the ACH code construction algorithm can be used to construct a code with a sliding-block decoder at rate t:t and with window length m+a+2t, where t is upper-bounded by a linear function of the number of states of G. It is demonstrated that this is the best one can do in the sense that any general upper bound on the decoder window length for finite-state codes into systems Σ with finite memory must grow at least linearly with the number of states of the graph G presenting Σ     

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     

A replacement policy maximizing MTTF of a system with several spareunits

A replacement policy is considered that maximizes mean time-to-failure (MTTF) of a system with N spare units. The optimum replacement time of a system with k spares (k=1, 2, ..., N) is derived successively from MTTF with k-1 spares by induction. The maximum MTTF is approximately given by a reciprocal of the hazard rate     

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 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     

k-out-of-m system availability with minimum-costallocation spares

An optimization method for determining the number of spare units that should be allocated to a k-out-of-m system to minimize the system-spares cost yet attain the specified system availability is presented. The objective function for optimization is a nonlinear integer type. The optimization method is a variation of the simplex search technique used for continuous functions. The optimization problem is cast in a form that minimizes the system-spares cost, with the required system availability as an inequality constraint. Results obtained by using the proposed optimization technique, as well as the computation time required for optimization, are compared to those for methods developed specifically for dealing with nonlinear integer problems. The method is simple, easy to implement, and yet very effective in dealing with the spare allocation problem for k-out-of-m:F systems     

On the influence of coding on the mean time to failure fordegrading memories with defects

The application of a combined test-error-correcting procedure is studied to improve the mean time to failure (MTTF) for degrading memory systems with defects. The degradation is characterized by the probability p that within a unit of time a memory cell changes from the operational state to the permanent defect state. Bounds are given on the MTTF and it is shown that, for memories with N words of k information bits, coding gives an improvement in MTTF proportional to (k/n) N(d_min^-2)/(d_min ^-1), where d_min and (k/n) are the minimum distance and the efficiency of the code used, respectively. Thus the time gain for a simple minimum-distance-3 is proportional to N^-1. A memory word test is combined with a simple defect-matching code. This yields reliable operation with one defect in a word of length k+2 at a code efficiency k/(k+2)     

Distribution of the lifetime of consecutive k-within-m-out-of-n:F systems

The distribution of the lifetime (MTTF) of any consecutive k -within-m-out-of-n:F system, with independent exponentially distributed component lifetimes, is shown to be a convex combination of the distributions (MTTFs) of several convolutions of independent random variables, where each convolution represents a distinct path in the evolution of the system's history, and where in each convolution all but the last random variable is exponential. The last random variable in each convolution is either a zero lifetime or the lifetime of several disjoint consecutive k_i within m_i-out-of-n:F systems in series with each k_i<k, each m_i<m, and each n_i<n. This enables the calculations to proceed recursively. Calculations are facilitated by the symmetric nature of the convex combination     

A coding scheme for m-out-of-n codes

A scheme for the construction of m-out-of-n codes based on the arithmetic coding technique is described. For appropriate values of n, k, and m, the scheme can be used to construct an (n,k) block code in which all the codewords are of weight m. Such codes are useful, for example, in providing perfect error detection capability in asymmetric channels such as optical communication links and laser disks. The encoding and decoding algorithms of the scheme perform simple arithmetic operations recursively, thereby facilitating the construction of codes with relatively long block sizes. The scheme also allows the construction of optimal or nearly optimal m-out-of-n codes for a wide range of block sizes limited only by the arithmetic precision used     

Multireception probabilities for FH/SSMA communications

Exact expressions for the probabilities P(l,m-l/k) of l correct packet receptions and m-l erroneous ones, out of total k packets contending in a slot, are presented for the case of frequency-hopped spread-spectrum random-access slotted networks employing random frequency hopping patterns. These expressions are difficult to evaluate numerically for values of m>3. However, their numerical analysis indicates that under light traffic conditions these probability values are very close to the ones provided by the independent receiver operation assumption, under which the distribution of multireception obeys the binomial law     

Recursive updating the eigenvalue decomposition of a covariancematrix

The author addresses the problem of computing the eigensystem of the modified Hermitian matrix, given the prior knowledge of the eigensystem of the original Hermitian matrix. Specifically, an additive rank-k modification corresponding to adding and deleting blocks of data to and from the covariance matrix is considered. An efficient and parallel algorithm which makes use of a generalized spectrum-slicing theorem is derived for computing the eigenvalues. The eigenvector can be computed explicitly in terms of the solution of a much-reduced (k ×k) homogeneous Hermitian system. The overall computational complexity is shown to be improved by an order of magnitude from O(N³) to O(N ²k), where N×N is the size of the covariance matrix. It is pointed out that these ideas can be applied to adaptive signal processing applications, such as eigen-based techniques for frequency or angle-of-arrival estimation and tracking. Specifically, adaptive versions of the principal eigenvector method and the total least squares method are derived     

Asymptotic performance of M-ary orthogonal modulation ingeneralized fading channels

The asymptotic (M→∞) probability of symbol error P_e,_m for M-ary orthogonal modulation in a Nakagami-m fading channel is given by the incomplete gamma function P(m, mx) where x=In 2/(E_b/N₀) and E_b is the average energy per bit. For large signal-to-noise ratio this leads to a channel where the probability of symbol error varies as the inverse mth power of E_b/N₀. These channels exist for all m⩾1/2. The special case of m=1 corresponds to Rayleigh fading, an inverse linear channel     

Coset correlation of m-sequences

It is well-known that there exists a unique shift l of the m-sequence S(k) such that the value of S₀(k)=S(k+l) is only determined by the cyclotomic coset to which k belongs. A measure called the `coset correlation' is introduced. It is proven that the shift l can be determined by the coset correlation     

m-consecutive-k-out-of-n:F systems

An m-consecutive-k-out-of-n:F system, consists of n components ordered on a line; the system fails if and only if there are at least m nonoverlapping runs of k consecutive failed components. Three theorems concerning such systems are stated and proved. Theorem one is a recursive formula to compute the failure probability of such a system. Theorem two is an exact formula for the failure probability. Theorem three is a limit theorem for the failure probability     

Runlength-limited codes for mixed-error channels

The mixed-error channel (MC) combines the binary symmetric channel and the peak shift channel. The construction of (d, k) constrained t-MC-error-correcting block codes is described. It is demonstrated that these codes can achieve a code rate close to the ( d, k) capacity. The encoding and decoding procedures are described. The performance of the construction depends on a particular partitioning of (d, k) constrained block codes. This partitioning is discussed and various tables of codes are included. Examples on encoding/decoding and on code performance are given     

A generalization of consecutive-k-out-of-n:Fsystems

A linear (m, n)-lattice system consists of m ·n elements arranged like the elements of a (m ,n)-matrix, i.e. each of the m rows includes m elements, and each of the n columns includes m elements. A circular (m,n)-lattice system consists of m circles (centered at the same point) and n rays. The intersections of the circle and the rays represent the elements, i.e. each of the circles includes n elements and each of the rays has m elements. A (linear or circular) (m, n)-lattice system is a (linear or circular) connected-X-out-of-(m,n):F lattice system if it fails whenever at least one subset of connected failed components occurs which includes failed components connected in the meaning of connected-X. The paper presents some practical examples and the reliability formulas of simple systems using results of consecutive-k-out-of-n:F systems     

Maximal length sequences for frequency hopping

Normally, frequency hopping sequences for spread-spectrum communication systems are obtained by selecting groups of elements of binary m sequences. An alternative to using groups of binary m-sequence elements is developed. It involves obtaining nonbinary m sequences with the number of desired hopping frequencies equal to the number of symbols in the finite field which the nonbinary m sequence is over. The grouping of elements of binary m sequences does not necessarily have the m sequences. In addition, the autocorrelation function of the nonbinary m sequence has a maximal period, whereas the frequency hopping sequences obtained from the grouping of elements of binary m sequences may not have a maximal period