Some results on the covering radii of Reed-Muller codes

Let R(r,m) be the rth-order Reed-Muller code of length 2^m and let ρ(r,m ) be its covering radius. R(2,7), R(2,8), R (3,7), and R(4,8) are among those smallest Reed-Muller codes whose covering radii are not known. New bounds for the covering radii of these four codes are obtained. The results are ρ(2,7)⩾40, ρ(2,8)⩾84, 20⩽ρ(3,7)⩽23, and ρ(4,8)⩾22. Noncomputer proofs for the known results that ρ(2,6)=18 and that R(1,5) is normal are given     

Optimal quaternary linear codes of dimension five

Let d_q(n,k) be the maximum possible minimum Hamming distance of a q-ary [n,k,d]-code for given values of n and k. It is proved that d₄ (33,5)=22, d₄(49,5)=34, d₄ (131,5)=96, d₄(142,5)=104, d₄(147,5)=108, d ₄(152,5)=112, d₄(158,5)=116, d₄(176,5)⩾129, d₄(180,5)⩾132, d₄(190,5)⩾140, d₄(195,5)=144, d₄(200,5)=148, d₄(205,5)=152, d₄(216,5)=160, d₄(227,5)=168, d₄(232,5)=172, d₄(237,5)=176, d₄(240,5)=178, d₄(242,5)=180, and d₄(247,5)=184. A survey of the results of recent work on bounds for quaternary linear codes in dimensions four and five is made and a table with lower and upper bounds for d₄(n,5) is presented     

Optimal binary one-error-correcting codes of length 10 have 72codewords

The maximum number of codewords in a binary code with length n and minimum distance d is denoted by A(n, d). By construction it is known that A(10, 3)⩾72 and A(11, 3)⩾144. These bounds have long been conjectured to be the exact values. This is here proved by classifying various codes of smaller length and lengthening these using backtracking and isomorphism rejection. There are 562 inequivalent codes attaining A(10, 3)=72 and 7398 inequivalent codes attaining A(11, 3)=144     

Constructions, families, and tables of binary linear covering codes

Presents constructions and infinite families of binary linear covering codes with covering radii R=2,3,4. Using these codes, the authors obtain a table of constructive upper bounds on the length function l(r,R) for r⩽64 and R=2,3,4, where l(r, R) is the smallest length of a binary linear code with given codimension r and covering radius R. They obtain also upper bounds on l(r, R) for r=21, 28, R=5. Parameters of the constructed codes are better than parameters of previously known codes     

The nonexistence of some five-dimensional quaternary linear codes

Let n₄(k, d) be the smallest integer n, such that a quaternary linear [n, k, d; 4]-code exists. It is proved that n₄ (5, 20)=30, n₄(5, 42)⩾59, n₄(5, 45)⩾63, n₄(5, 64)⩾88, n₄(5, 80)=109, n₄(5, 140)⩾189, n₄(5, 143)⩾193, n₄ (5, 168)⩾226, n₄(5, 180)⩾242, n₄(5, 183)⩾246, n₄(5, 187)=251     

End-to-end data paths: quickest or most reliable?

Let N=(V,E,c,l,p) be a network where V is the set of n vertices, E is the set of m edges, c(u,v)⩾0 is the capacity of edge {u,v}, l(u,v)⩾0 is the delay of edge {u,v}, p(u,v)∈[0,1] is the operational probability of edge {u,v}. In this letter, we present O(rm+rnlog n) time algorithms for the most reliable quickest path problem and the quickest most reliable path problem, where r is the number of different capacity values in the network     

Asymptotic bounds on optimal noisy channel quantization via randomcoding

Asymptotically optimal zero-delay vector quantization in the presence of channel noise is studied using random coding techniques. First, an upper bound is derived for the average rth-power distortion of channel optimized k-dimensional vector quantization at transmission rate R on a binary symmetric channel with bit error probability ϵ. The upper bound asymptotically equals 2/sup -rRg(ϵ,k,r/). where k/(k +r) [1 - log₂(l +2√(ϵ(1-ϵ))] ⩽g(ϵ,k,r)⩽1) for all ϵ⩾0, lim_ϵ→0 g(ϵ,k,r)=1, and lim_k→∞g(ϵ,k,r)=1. Numerical computations of g(ϵ,k,r) are also given. This result is analogous to Zador's (1982) asymptotic distortion rate of 2^-rR for quantization on noiseless channels. Next, using a random coding argument on nonredundant index assignments, a useful upper bound is derived in terms of point density functions, on the minimum mean squared error of high resolution, regular, vector quantizers in the presence of channel noise. The formula provides an accurate approximation to the distortion of a noisy channel quantizer whose codebook is arbitrarily ordered. Finally, it is shown that the minimum mean squared distortion of a regular, noisy channel VQ with a randomized nonredundant index assignment, is, in probability, asymptotically bounded away from zero     

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     

Markov characterization of digital fading mobile VHF channels

We apply techniques for the modeling of error sequences on digital communication channels to results of experiments undertaken on mobile VHF channels. The experiments were carried out using four different modulation schemes at some of the different standardized signaling rates. The modulation schemes used were: FSK @ 300 baud, DPSK @ 1200 baud, QPSK @ 1200 baud, and 8-ary PSK @ 1600 baud, and in each case, subcarrier modulation was used. The experiments were undertaken for urban as well as freeway environments. Fritchman-partitioned Markov chain models were derived throughout, and from the models, block error probability distributions were derived. These block error probability distributions or P(m,n) give the probability that a block of n bits will contain exactly m errors. We present P(⩾m,n) for 7-, 15-, 31-, 63-, 127-, and 255-b blocks, for the above-mentioned modulation schemes, in the mobile VHF environments mentioned. P(⩾m,n) denotes the probability that at least m errors will occur in a block of n bits. Furthermore, the P(⩾m,n) information presented here, should give some indication of the performance to be expected from block error-correcting schemes     

On the trellis representation of the Delsarte-Goethals codes

In this correspondence, the trellis representation of the Kerdock and Delsarte-Goethals codes is addressed. It is shown that the states of a trellis representation of DG(m,δ) under any bit-order are either strict-sense nonmerging or strict-sense nonexpanding, except, maybe, at indices within the code's distance set. For δ⩾3 and for m⩾6, the state complexity, s_max[DG(m,δ)], is found. For all values of m and δ, a formula for the number of states and branches of the biproper trellis diagram of DG(m, δ) is given for some of the indices, and upper and lower bounds are given for the remaining indices. The formula and the bounds refer to the Delsarte-Goethals codes when arranged in the standard bit-order     

Three messages are not optimal in worst case interactivecommunication

Let X and Y be two jointly distributed random variables. Suppose person P_X, the informant, knows X, and person P_Y, the recipient, knows Y, and both know the joint probability distribution of the pair (X,Y). Using a predetermined protocol, they communicate over a binary error-free channel in order for P_Y to learn X, whereas P_X may or may not learn Y. Cˆm(X|Y) is the minimum number of bits required to be transmitted (by both persons) in the worst case when only m message exchanges are allowed. Cˆ∞(X|Y) is the number of bits required when P_X and P_Y can communicate back and forth an arbitrary number of times. Orlitsky proved that for all (X,Y) pairs, Cˆ₂(X|Y)⩽4Cˆ∞(X|Y)+3, and that for every positive c and ∈ with ∈<1, there exist (X,Y) pairs with Cˆ₂(X|Y)⩾(2-∈)Cˆ₃ (X|Y)⩾(2-∈)Cˆ-∞(X|Y)⩾c. These results show that two messages are almost optimal, but not optimal. A natural question, then, is whether three messages are asymptotically optimal. In this work, the authors prove that for any c and ∈ with 0<∈<1 and c>0, there exist some (X,Y) pairs for which Cˆ₃(X|Y)⩾(2-∈)Cˆ₄(X|Y)⩾c. That is, three messages are not optimal either     

New covering radius of Reed-Muller codes for t-resilient functions

In this paper, we introduce a new covering radius of RM(r,n) from cryptography viewpoint. It is defined as the maximum distance between t-resilient functions and the rth order Reed-Muller code RM(r,n). We next derive its lower and upper bounds. We further present a table of numerical data of our bounds.     

A note on the method of poles for code construction

The method of poles is a method for constructing a rate 1:1 finite state code from K-ary data into a constrained channel S, where S is recognized by a given local automaton and S has capacity at least log(k). We characterize those automata to which the method of poles applies in the case where h(S)=log(k). The code produced by the method of poles has a sliding-block decoder. We also give an upper bound on the window length of the decoder that applies when h(S)⩾log(k)     

Goppa codes and trace operator

We study Goppa codes, Γ(L,g), defined by the polynomial g(z)=a(z)TrF_pms:F_ps(b(z)). It is shown that the dimension of these codes never reaches the general, well-known, bound for Goppa codes. New bounds are proposed depending on the value of m and p. Furthermore, we prove that when p=2 these codes have only even weights     

Comment. Remarks on the LUC public key system

The authors of [Remarks on the LUC public key system, see ibid., vol. 30, p. 123, 1994] consider the Lucas function on which the public cryptosystem LUC proposed by Smith and Lennon [1993] is based. For a finite field G with m∈G, the Lucas function V_n(m) is defined by the second order linear recurrence relation V_n(m)=mV_n-1(m)-V_n-2(m) where V_o (m)=2, V₁(m)=m. The characteristic polynomial f of the Lucas function is f(x)=x²-mx+1, and V_x(m)=α ^x+α^-x where α is a root of f. We now consider some of the results of and give concise proofs     

Improved multicovering bounds from linear inequalities and supercodes

The multicovering radii of a code are natural generalizations of the covering radius in which the goal is to cover all m-tuples of vectors for some m as cheaply as possible. In this correspondence, we describe several techniques for obtaining lower bounds on the sizes of codes achieving a given multicovering radius. Our main method is a generalization of the method of linear inequalities based on refined weight distributions of the code. We also obtain a linear upper bound on the 2-covering radius. We further study bounds on the sizes of codes with a given multicovering radius that are subcodes of a fixed code. We find, for example, constraints on parity checks for codes with small ordinary covering radius.     

On minimal α-mean error parameter transmission over a Poissonchannel

We consider the problem of one-dimensional parameter transmission over a Poisson channel when the input signal (intensity) obeys a peak energy constraint. We show that it is possible to choose input signals and an estimator in such a way that the mean-square error of parameter transmission will decrease exponentially with transmission time T→∞ and we find the best possible exponent. For more general loss functions of the type |x|α we find the best possible exponent if α⩾α₀=(1+√5)/2≈1.618. If 0<α<α₀ then some lower and upper bounds for the best possible exponent are established     

Quasi-perfect codes with small distance

The main purpose of this paper is to give bounds on the length of the shortest and longest binary quasi-perfect codes with a given Hamming distance, covering radius, and redundancy. We consider codes with Hamming distance 4 and 5 and covering radius 2 and 3, respectively. We discuss the blockwise direct sum (BDS) construction which has an important role in finding these bounds.     

Heterostructure devices using self-aligned p-type diffused ohmiccontacts

Describes the use of a p-type refractory ohmic contact in ohmic self-aligned devices. The contacts are based on self-aligned diffusion of zinc-doped tungsten film. The diffusion is nearly isotropic in the vicinity of silicon nitride sidewalls, allowing self-alignment of ohmic contacts with emitters and gates. Low-resistance contacts (<10^-6 Ω·cm²) are formed both to GaAs and GaAlAs, and the lifetime of the diffused region is superior to that obtained from implantation. Heterostructure bipolar transistors (HBTs) showing high current gains (⩾50 at 2×10³ A·cm^-2 and ⩾200 at 1×10⁵ A·cm^-2 with micrometer-sized emitter widths) and p-channel GaAs gate heterostructure field-effect transistors (HFETs) showing high transconductances (78 mS/mm at 2.2-μm gate length) have been fabricated using this contact     

Entropy/length profiles, bounds on the minimal covering ofbipartite graphs, and trellis complexity of nonlinear codes

The trellis representation of nonlinear codes is studied from a new perspective. We introduce the new concept of entropy/length profile (ELP). This profile can be considered as an extension of the dimension/length profile (DLP) to nonlinear codes. This elaboration of the DLP, the entropy/length profiles, appears to be suitable to the analysis of nonlinear codes. Additionally and independently, we use well-known information-theoretic measures to derive novel bounds on the minimal covering of a bipartite graph by complete subgraphs. We use these bounds in conjunction with the ELP notion to derive both lower and upper bounds on the state complexity and branch complexity profiles of (nonlinear) block codes represented by any trellis diagram. We lay down no restrictions on the trellis structure, and we do not confine the scope of our results to proper or one-to-one trellises only. The basic lower bound on the state complexity profile implies that the state complexity at any given level cannot be smaller than the mutual information between the past and the future portions of the code at this level under a uniform distribution of the codewords. We also devise a different probabilistic model to prove that the minimum achievable state complexity over all possible trellises is not larger than the maximum value of the above mutual information over all possible probability distributions of the codewords. This approach is pursued further to derive similar bounds on the branch complexity profile. To the best of our knowledge, the proposed upper bounds are the only upper bounds that address nonlinear codes. The novel lower bounds are tighter than the existing bounds. The new quantities and bounds reduce to well-known results when applied to linear codes