Sliding block codes between constrained systems

The construction of finite-state codes between constrained systems called sofic systems introduced by R. Karabed and B. Marcus (1988) is continued. It is shown that if Σ is a shift of finite type and S is a sofic system with k/n=h(S )/h(Σ), where h denotes entropy, there is a noncatastrophic finite-state invertible code from Σ to S at rate k:n if Σ and S satisfy a certain algebraic condition involving dimension groups, and Σ and S satisfy a certain condition on their periodic points. Moreover, if S is an almost finite type sofic system, then the decoder can be sliding block     

On the average delay for routing subject to independent deflections

Consider a packet walking along a directed graph with each node having two edges directed out. The packet is headed towards one of N destinations, chosen according to a probability distribution p . At each step, the packet is forced to use a nonpreferred edge with some probability q, independently of past events. Using information theory and sequential analysis, it is shown that the mean number of steps required by the packet to reach the destination is roughly, at least H(p)/(1-h(q), where h is the binary entropy function and H(p) is the entropy (base two) of p. This lower bound is shown to be asymptotically achievable in the case where the packet always begins at a fixed node. Also considered is the maximum, over all pairs of nodes in a graph, of the mean transit time from one node to the other. The work is motivated by the search for graphs that work well in conjunction with deflection routing in communication networks     

Calculation of the binomial survivor function [reliabilityapplications]

A method is presented for calculating the binomial SF (cumulative binomial distribution), binfc(k;p,n), especially for a large n, beyond the range of existing tables, where conventional computer programs fail because of underflow and overflow, and Gaussian or Poisson approximations yield insufficient accuracy for the purpose at hand. This method is used to calculate and sum the individual binomial terms while using multiplication factors to avoid underflow; the factors are then divided out of the partial sum whenever it has the potential to overflow. A computer program uses this technique to calculate the binomial SF for arbitrary inputs of k, p, and n. Two other algorithms are presented to determine the value of p needed to yield a specified SF for given values of k and n and calculate the value where p=SF for a given k and n. Reliability applications of each algorithm/program are given, e.g. the value of p needed to achieve a stated k-out-of-n :G system reliability and the value of p for which k -out-of-n:G system reliability equals p     

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     

A fast signature scheme based on congruential polynomial operations

A novel digital signature scheme is proposed in which the computation time is much shorter than that of the Rivest-Shamir-Adelman (RSA) scheme, while the key length and signature length are comparable to those for the RSA scheme. Moreover, the proposed scheme can be implemented easily and is, therefore, more practical for many digital signature applications. The scheme is based on congruential polynomial operations whose degrees are more than three. The secret key consists of two large prime numbers, p and q, and the public key is their product, n=p²q. The security of this scheme depends on the difficulty of factorizing the number n. Variations using the number of zeros succeeding the significant bit are also proposed     

On the optimality and stability of exponential twisting in MonteCarlo estimation

Estimation of the large deviations probability p_n =P(S_n⩾γn) via importance sampling is considered, where S_n is a sum of n i.i.d. random variables. It has been previously shown that within the nonparametric candidate family of all i.i.d. (or, more generally, Markov) distributions, the optimized exponentially twisted distribution is the unique asymptotically optimal sampling distribution. As n→∞, the sampling cost required to stabilize the normalized variance grows with strictly positive exponential rate for any suboptimal sampling distribution, while this sampling cost for the optimal exponentially twisted distribution is only O(n ^1/2). Here, it is established that the optimality is actually much stronger. As n→∞, this solution simultaneously stabilizes all error moments of both the sample mean and the sample variance estimators with sampling cost O(n^1/2 ). In addition, it is shown that the embedded parametric family of exponentially twisted distributions has a certain uniform asymptotic stability property. The technique is stable even if the optimal twisting parameter(s) cannot be precisely determined     

Relationships between m-sequences over GF(q) andGF(qm)

It is shown that m-sequences over GF(q^m ) of length q^nm-1 corresponding to primitive polynomials in GF[q^m,x] of degree n can be generated from known m-sequences over GF(q) of length q^nm-1 obtained from primitive polynomials in GF[q,x] of degree mn. A procedure for generating the m-sequences over GF(q²) from m-sequences over GF(q) was given which enables the generation of m-sequences over GF( p²ⁿ). In addition it was shown that all of the primitive polynomials in GF[q,^m,x] can be obtained from a complete set of the primitive polynomials in GF[q ,x]     

Explicit formulas for self-complementary normal bases in certainfinite fields

Explicit formulas are given for sets of p elements forming a self-complementary normal basis of GF(q^p) over GF(q), where p is the characteristic of GF(q ). Using these formulas, a straightforward construction of self-complementary bases for GF(q^α) (where α=p^m) over GF(q) is also presented     

Pseudocyclic maximum-distance-separable codes

The (n, k) pseudocyclic maximum-distance-separable (MDS) codes modulo (xⁿ- a) over GF(q) are considered. Suppose that n is a divisor of q+1. If n is odd, pseudocyclic MDS codes exist for all k. However, if n is even, nontrivial pseudocyclic MDS codes exist for odd k (but not for even k) if a is a quadratic residue in GF(q), and they exist for even k (but not for odd k) if a is not a quadratic residue in GF(q). Also considered is the case when n is a divisor of q-1, and it is shown that pseudocyclic MDS codes exist if and only if the multiplicative order of a divides (q-1)/n, and that when this condition is satisfied, such codes exist for all k. If the condition is not satisfied, every pseudocyclic code of length n is the result of interleaving a shorter pseudocyclic code     

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     

New multilevel codes over GF(q)

Set partitioning is applied to multidimensional signal spaces over GF(q), i.e., GFⁿ¹(q) (n1⩽q ), and it is shown how to construct both multilevel block codes and multilevel trellis codes over GF(q). Multilevel (n, k, d) block codes over GF(q) with block length n, number of information symbols k, and minimum distance d_min⩾d are presented. These codes use Reed-Solomon codes as component codes. Longer multilevel block codes are also constructed using q-ary block codes with block length longer than q+1 as component codes. Some quaternary multilevel block codes are presented with the same length and number of information symbols as, but larger distance than, the best previously known quaternary one-level block codes. It is proved that if all the component block codes are linear. the multilevel block code is also linear. Low-rate q-ary convolutional codes, word-error-correcting convolutional codes, and binary-to-q-ary convolutional codes can also be used to construct multilevel trellis codes over GF(q) or binary-to-q-ary trellis codes     

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     

Stability analysis and numerical simulation of multideviceamplifiers

Stability analysis of multidevice amplifiers is made on a generalized circuit comprising two n-ports with S-matrices S (active devices) and S' (passive networks) connected at n interface ports. Open-loop transfer functions defined for a signal-flow graph and its (n-1) subgraphs of incident and reflected waves at the interface ports are expressed in terms of det M_n and its minors, where M_n=S'S-I_n and I_n is the n×n identity matrix. it is shown that the Nyquist plots of the n transfer functions completely characterize the number of right-half complex-frequency-plane zeros of det M_n, and hence the amplifier stability. Insertion of an ideal circulator and isolators at the interface ports enables one to calculate the Nyquist plots and voltage distributions of possible instabilities using commercially available linear circuit simulators. Numerical simulations for two types of parallel-operated GaAs FET amplifiers are performed to verify the usefulness of the analysis in design-phase check of multidevice amplifier stability     

Electromagnetic scattering from an infinite elliptic metalliccylinder coated by a circular dielectric one

The scattering from an infinite elliptic metallic cylinder coated by a circular dielectric one is considered. The electromagnetic field is expressed in terms of both circular and elliptical cylindrical wave functions, which are connected with one another by well-known expansion formulas. In the special case of small h=ka/2 (a being the interfocal distance of the elliptic conductor and k the wavenumber of the dielectric coating), exact, closed-form expressions of the form S (h)=S(0)[1+g "h²+O(h⁴)] are obtained for the scattered field and the various scattering cross sections of the problem. Both polarizations are considered for normal incidence. Graphical results for various values of the parameters are given     

Frequency-hopping code sequence designs having large linear span

In frequency-hopping spread-spectrum multiple-access communication systems, it is desirable to use sets of hopping patterns that, in addition to having good Hamming correlation properties and large period, are also derived from sequences having large linear span. Here, two such frequency hopping code sequence designs that are based on generalized bent functions and generalized bent sequences are presented. The Hamming correlation properties of the designs are optimal in the first case and close to optimal in the second. In terms of the alphabet size p (required to be prime in both cases), the period and family size of the two designs are given by (p², p) and (p ⁿ, p^n/2+1) (n an even integer), respectively. The finite field sequences underlying the patterns in the first design have linear span exceeding p, whereas still larger linear spans (when compared to the sequence period) can be obtained using the second design method     

Error detection in a class of decimal codes

Consideration is given to the problem of multiple parity checks for an n-digit number. Each check relates to specific digits, where the probability p of a particular digit being in error is fixed. The author proves that it is best, in the sense of minimizing the probability of an undetected error, to add either one or n parity checks, depending on the value of n and p     

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     

Reliability of a consecutivek-out-of-r-from-n:F system

The reliability of the consecutive k-out-of-r-from-n:F system is studied. For k=2 an explicit solution is given for n components in line or in cycle in the i.i.d. case. For k⩾3 sharp lower and upper bounds are given for the reliability of the system and demonstrated for different values of n, k, r, p. These bounds are exact for r=n, n-1, n-2, n-3, and for these values the exact analytic solution is also given     

On repeated-root cyclic codes

A parity-check matrix for a q-ary repeated-root cyclic code is derived using the Hasse derivative. Then the minimum distance of a q-ary repeated-root cyclic code is expressed in terms of the minimum distance of a certain simple-root cyclic code. With the help of this result, several binary repeated-root cyclic codes of lengths up to n=62 are shown to contain the largest known number of codewords for their given length and minimum distance. The relative minimum distance d_min/n of q-ary repeated-root cyclic codes of rate r⩾R is proven to tend to zero as the largest multiplicity of a root of the generator g(x) increases to infinity. It is further shown that repeated-root cycle codes cannot be asymptotically better than simple-root cyclic codes     

On the existence of optimum cyclic burst correcting codes over GF(q)

A cyclic b-burst correcting code over GF(q) of redundancy r and length n=(q^r-b+1-1)/(q-1) is said to be optimum. It is proved that a necessary condition for the existence of such a code is the existence of a square-free polynomial in GF(q)[x] of degree b-1 which is not divisible by x such that its period and the degrees of its irreducible factors are relatively prime to q-1. Moreover, if such a polynomial exists, then there are an infinite number of optimum cyclic b-burst correcting codes over GF(q)