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     

On the realization of band-limited power spectra from partialcovariance sequence

The set M(Ω) of all (discrete-time) power spectra supported on a known interval [-Ω, Ω], (with Ω<π) and whose first N+1 correlation coefficients coincide with a given sequence (γn)n=0,N is characterized. By using the results related to the trigonometric moment problem, it is shown that the positive real functions associated with the elements of M (Ω) are given by a linear fractional map of Schur functions satisfying certain properties     

A convolutional single-parity-check concatenated coding scheme forhigh-data-rate applications

The coding scheme uses a set of n convolutional codes multiplexed into an inner code and a (n,n-1) single-parity-check code serving as the outer code. Each of the inner convolutional codes is decoded independently, with maximum-likelihood decoding being achieved using n parallel implementations of the Viterbi algorithm. The Viterbi decoding is followed by additional outer soft-decision single-parity-check decoding. Considering n=12 and the set of short constraint length K=3, rate 1/2 convolutional codes, it is shown that the performance of the concatenated scheme is comparable to the performance of the constraint length K=7, rate 1/2 convolutional code with standard soft-decision Viterbi decoding. Simulation results are presented for the K=3, rate 1/2 as well as for the punctured K=3, rate 2/3 and rate 3/4 inner convolutional codes. The performance of the proposed concatenated scheme using a set of K=7, rate 1/2 inner convolutional codes is given     

Asymptotic performance of M-ary orthogonal signals inworst case partial-band interference and Rayleigh fading

It is shown that for worst-case partial-band jamming, the error probability performance (for fixed E_b/N_I) becomes worse with increasing M for (M>16). The asymptotic probability-of-error is not zero for any E_b/N _I(>ln 2), but decreases inverse linearly with respect to it. In the fading case, the error-probability performance (for fixed E_b/N₀) improves with M for noncoherent detection, but worsens with M for coherent detection. For large E_b/N₀ the performance of the Rayleigh fading channel asymptotically approaches the same limit as the worst case partial-band jammed channel. However, for values of M at least up to 4096, the partial-band jammed channel does better. While it is unlikely that an M-ary orthogonal signal set with M>1024 will be used in a practical situation, these results suggest an important theoretical problem; namely, what signal set achieves reliable communication     

Performance analysis of RS-coded M-ary FSK forfrequency-hopping spread spectrum mobile radios

Decoding performance of Reed-Solomon (RS) coded M-ary FSK with noncoherent detection in a frequency-hopping spread spectrum mobile radio channel is theoretically analyzed. Exact formulas and an approximate one for evaluating word error rates (WERs) of error correction and error-and-erasure correction schemes on decoding the RS codes are derived. It is shown that with K symbol erasure and C symbol error detection, RS coded M-ary FSK achieves the equivalent diversity order of (K+1)(C+1)     

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     

On the Hamming distance properties of group codes

Under certain mild conditions, the minimum Hamming distance D of an (N, K, D) group code C over a non-abelian group G is bounded by D⩽N -2K+2 if K⩽N/2, and is equal to 1 if K>N/2. Consequently, there exists no (N, K, N-K+1) group code C over an non-abelian group G if 1<K<N. Moreover, any normal code C with a non-abelian output space has minimum Hamming distance equal to D=1. These results follow from the fact that non-abelian groups have nontrivial commutator subgroups. Finally, if C is an (N, K, D) group code over an abelian group G that is not elementary abelian, then there exists an (N, K, D) group code over a smaller elementary abelian group G'. Thus, a group code over a general group G cannot have better parameters than a conventional linear code over a field of the same size as G     

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     

Error performance of a digitally processed binary ESK frequencyhopping receiver in the presence of large Doppler

Analysis is made of the effects of Doppler on the error rate performance of a low data rate binary FSK frequency hopping receiver, employing a discrete Fourier transform (DFT) technique for baseband detection. Bit detection decision is made by locating the maximum of the DFT outputs which, in the frequency domain, are assumed to be separated by 1/T where T is the bit period. Both the worst case and average error performances are obtained and presented as a function of E_b/N₀ for various values of M where E_b/N₀ is the signal bit energy-to-noise density ratio and M is the degree of freedom associated with the Doppler uncertainty window. The E _b/N₀ degradation as a function of M is also presented     

Pipelined recursive filter with minimum order augmentation

Pipelining is an efficient way for improving the average computation speed of an arithmetic processor. However, for an M-stage pipeline, the result of a given operation is available only M clock periods after initiating the computation. In a recursive filter, the computation of y(n) cannot be initiated before the computations of y(n-1) through y(n-N) are completed. H.B. Voelcker and E.E. Hartquist (1970) and P.M.Kogge and H.S. Stone (1973) independently devised augmentation techniques for resolving the dependence problem in the computation of y(n). However, the augmentation required to ensure stability may be excessively high, resulting in a very complex numerator realization. A technique which results in a minimum order augmentation is presented. The complexity of the resulting filter design is very much lower. Various pipelining architectures are presented. It is demonstrated by an example that when compared to the prototype filter, the augmented filter has a lower coefficient sensitivity and better roundoff noise performance     

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     

Optimization of signal sets for partial-response channels. I.Numerical techniques

Given a linear, time-invariant, discrete-time channel, the problem of constructing N input signals of finite length K that maximize minimum l₂ distance between pairs of outputs is considered. Two constraints on the input signals are considered: a power constraint on each of the N inputs (hard constraint) and an average power constraint over the entire set of inputs (soft constraint). The hard constraint, problem is equivalent to packing N points in an ellipsoid in min(K,N-1) dimensions to maximize the minimum Euclidean distance between pairs of points. Gradient-based numerical algorithms and a constructive technique based on dense lattices are used to find locally optimal solutions to the preceding signal design problems. Two numerical examples are shown for which the average spectrum of an optimized signal set resembles the water pouring spectrum that achieves Shannon capacity, assuming additive white Gaussian noise     

Lower bounds for binary covering codes

G.D. Chen et al. (ibid., vol.IT-32, p.680-94, 1986) presented two new lower bounds for K(n,R), where K(n,R) denotes the minimum cardinality of a binary code of length n and covering radius R. The author shows that a slight modification gives further improvements and some examples are given to confirm the argument. Codes that have a certain partitioning property are considered     

Asymptotic results for partial concentrators

Various switching network construction advantageously use modules known as partial concentrators. A partial concentrator is an n-input, m-output, single-stage switching device in which each input has access to some but not all of the outputs. A partial concentrator is said to have capacity c, if, for any k⩽c inputs, there exist k disjoint paths from the k inputs to some set of k outputs. Here, capacity values achievable for large n when each input has access to exactly M outputs, are considered. For a partial concentrator in which each input has access to exactly M outputs, it is shown that the cost ratio can be made arbitrarily small for any fixed M⩾2. In addition, it is shown that the rate of decrease of the cost ratio with increasing n is logarithmic for M=2, and polynomial for M⩾3     

Fast K-dimensional tree algorithms for nearest neighborsearch with application to vector quantization encoding

Fast search algorithms are proposed and studied for vector quantization encoding using the K-dimensional (K-d) tree structure. Here, the emphasis is on the optimal design of the K -d tree for efficient nearest neighbor search in multidimensional space under a bucket-Voronoi intersection search framework. Efficient optimization criteria and procedures are proposed for designing the K-d tree, for the case when the test data distribution is available (as in vector quantization application in the form of training data) as well as for the case when the test data distribution is not available and only the Voronoi intersection information is to be used. The criteria and bucket-Voronoi intersection search procedure are studied in the context of vector quantization encoding of speech waveform. They are empirically observed to achieve constant search complexity for O(log N) tree depths and are found to be more efficient in reducing the search complexity. A geometric interpretation is given for the maximum product criterion, explaining reasons for its inefficiency with respect to the optimization criteria     

Packet error probabilities in frequency-hopped spread-spectrumpacket radio networks-memoryless frequency-hopping patterns considered

The packet error probability induced in a frequency-hopped spread-spectrum packet radio network is computed. The frequency spectrum is divided into q frequency bins. Each packet is exactly one codeword from an (M, L) Reed-Solomon code [M=number of codeword symbols (bytes); L=number of information symbols (bytes)]. Every user in the network sends each of the M bytes of his packet at a frequency chosen among the q frequencies with equal probability and independently of the frequencies chosen for other bytes (i.e., memoryless frequency-hopping patterns). Statistically independent frequency-hopping patterns correspond to different users in the network. Provided that K users have simultaneously transmitted their packets on the channel and a receiver has locked on to one of these K packets, the probability that this packet is not decoded correctly is evaluated. It is also shown that although memoryless frequency-hopping patterns are utilized, the byte errors at the receiver are not statistically independent; instead they exhibit a Markovian structure     

Restoration of color images by multichannel Kalman filtering

A Kalman filter for optimal restoration of multichannel images is presented. This filter is derived using a multichannel semicausal image model that includes between-channel degradation. Both stationary and nonstationary image models are developed. This filter is implemented in the Fourier domain and computation is reduced from O(Λ ³N³M⁴) to O(Λ³N³M² ) for an M×M N-channel image with degradation length Λ. Color (red, green, and blue (RGB)) images are used as examples of multichannel images, and restoration in the RGB and YIQ domains is investigated. Simulations are presented in which the effectiveness of this filter is tested for different types of degradation and different image model estimates     

Upper bounds on the probability of sequences emitted byfinite-state sources and on the redundancy of the Lempel-Ziv algorithm

An upper bound on the probability of a sequence drawn from a finite-state source is derived. The bound is given in terms of the number of phrases obtained by parsing the sequence according to the Lempel-Ziv (L-Z) incremental parsing rule, and is universal in the sense that it does not depend on the statistical parameters that characterize the source. This bound is used to derive an upper bound on the redundance of the L-Z universal data compression algorithm applied to finite-state sources, that depends on the length N of the sequence, on the number K of states of the source, and, eventually, on the source entropy. A variation of the L-Z algorithm is presented, and an upper bound on its redundancy is derived for finite-state sources. A method to derive tighter implicit upper bounds on the redundancy of both algorithms is also given, and it is shown that for the proposed variation this bound is smaller than for the original L-Z algorithm, or every value of N and K     

Statistical inference under multiterminal rate restrictions: adifferential geometric approach

A statistical inference problem for a two-terminal information source emitting mutually correlated signals X and Y is treated. Let sequences Xⁿ and Yⁿ of n independent observations be encoded independently of each other into message sets M_X and M_Y at rates R₁ and R ₂ per letter, respectively. This compression causes a loss of the statistical information available for testing hypotheses concerning X and Y. The loss of statistical information is evaluated as a function of the amounts R₁ and R ₂ of the Shannon information. A complete solution is given in the case of asymptotically complete data compression, R₁, R₂→0 as n→∞. It is shown that the differential geometry of the manifold of all probability distributions plays a fundamental role in this type of multiterminal problem connecting Shannon information and statistical information. A brief introduction to the dually coupled e-affine and m-affine connections together with e -flatness and m-flatness is given     

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)