A geometric approach to root finding in GT(qm)

The problem of finding roots in F of polynomials in F [x] for F=GF(q^m), where q is a prime or prime power and m is a positive integer greater than 1 is considered. The problem is analyzed by making use of the finite affine geometry AG(m,q). A new method is proposed for finding roots of polynomials over finite extension fields. It is more efficient than previous algorithms when the degree of the polynomial whose roots are to be found is less than dimension m of the extension field. Implementation of the algorithm can be enhanced in cases in which optimal normal bases for the coefficient field are available     

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)     

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     

On the linear complexity of functions of periodic GF(q)sequences

It is proved that the product of arbitrary periodic GF(q) sequences attains maximum linear complexity if their periods are pairwise coprime. The necessary and sufficient conditions are derived for maximum linear complexity of the product of two periodic GF(q ) sequences with irreducible minimal characteristic polynomials. For a linear combination of products of arbitrary periodic GF(q) sequences, it is shown that maximum linear complexity is achieved if their periods are pairwise coprime and the polynomial x -1 does not divide any of their minimal characteristic polynomials; assuming only that their periods are pairwise coprime, the author establishes a lower bound on the linear complexity which is of the same order of magnitude as maximum linear complexity. Boolean functions are derived that are optimal with respect to the maximum linear complexity. Possible applications of the results in the design of sequence generators are discussed     

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     

1/f noise in MODFETs at low drain bias

The 1/f noise in normally-on MODFETs biased at low drain voltages is investigated. The experimentally observed relative noise in the drain current S_I/I² versus the effective gate voltage V_G=V_GS-V_off shows three regions which are explained. The observed dependencies are S_I/I²∝V_G ^m with the exponents m=-1, -3, 0 with increasing values of V_G. The model explains m =-1 as the region where the resistance and the 1/f noise stem from the 2-D electron gas under the gate electrode; the region with m=0 at large V_G or V_GS≅0 is due to the dominant contribution of the series resistance. In the region at intermediate V_G , m=-3, the 1/f noise stems from the channel under the gate electrode, and the drain-source resistance is already dominated by the series resistance     

Adaptive set-membership identification in O(m)time for linear-in-parameters models

Some fundamental contributions to the theory and applicability of optimal bounding ellipsoid (OBE) algorithms for signal processing are described. All reported OBE algorithms are placed in a general framework that demonstrates the relationship between the set-membership principles and least square error identification. Within this framework, flexible measures for adding explicit adaptation capability are formulated and demonstrated through simulation. Computational complexity analysis of OBE algorithms reveals that they are of O(m²) complexity per data sample with m the number of parameters identified. Two very different approaches are described for rendering a specific OBE algorithm, the set-membership weighted recursive least squares algorithm, of O(m) complexity. The first approach involves an algorithmic solution in which a suboptimal test for innovation is employed. The performance is demonstrated through simulation. The second method is an architectural approach in which complexity is reduced through parallel competition     

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     

Self-reciprocal polynomials and generalized Fermat numbers

Self-reciprocal polynomials (SRPs) over GF(q), where q is a prime power, q=p^k, are investigated. The maximum possible component for these polynomials is found for q odd. The construction of Fermat maximum exponent self-reciprocal polynomials (MRPs) over GF(2) is extended to GF(2^k ) with the aid of generalized Fermat numbers. These polynomials leads to a bound on the maximum possible exponent of SRPs over GF(2^k), and a simplified algorithm for finding these MRPs. Self-reciprocal polynomials have applications in cryptography, error-correction coding, and the synthesis of linear feedback shift registers. They are advantageous when available memory or hardware is restricted or when data can be read in either direction. Some results on quasi-self-reciprocal polynomials are also presented     

Effective recursive algorithm for computing multiplicative inversesin GF(2m)

Presents an effective recursive algorithm for computing multiplicative inverses in GF(2^m), where m=2^k, employing normal bases. The proposed algorithm requires m-1 cyclic shifts and two multiplications in GF (2^m) and in each subfield of GF(2^m): GF(2^m/2), GF(2^m/4),. . ., GF (2⁸) and GF(2⁴)     

l1-optimal estimation for discrete-time linearsystems

A linear multichannel estimation problem with discrete-time linear shift-invariant models is formulated in the time domain as a minimum l¹ norm approximation problem. It is shown, using some key results from optimization theory, that solving the approximation problem is equivalent to solving a sequence of linear programming problems which terminates when an optimal or near-optimal solution is reached. The motivation for considering an l¹ -optimal design versus l²- or H^∞-optimal designs is presented. A sample problem is solved to illustrate the computational procedure, as well as to compare the relative performances of the l¹-, l² and H^∞-optimal estimators in a practical situation     

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     

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     

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     

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     

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     

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     

New array codes for multiple phased burst correction

An optimal family of array codes over GF(q) for correcting multiple phased burst errors and erasures, where each phased burst corresponds to an erroneous or erased column in a code array, is introduced. As for erasures, these array codes have an efficient decoding algorithm which avoids multiplications (or divisions) over extension fields, replacing these operations with cyclic shifts of vectors over GF(q). The erasure decoding algorithm can be adapted easily to handle single column errors as well. The codes are characterized geometrically by means of parity constraints along certain diagonal lines in each code array, thus generalizing a previously known construction for the special case of two erasures. Algebraically, they can be interpreted as Reed-Solomon codes. When q is primitive in GF(q), the resulting codes become (conventional) Reed-Solomon codes of length P over GF(q^p-1), in which case the new erasure decoding technique can be incorporated into the Berlekamp-Massey algorithm, yielding a faster way to compute the values of any prescribed number of errors     

An O(kn)-time algorithm for computing thereliability of a circular consecutive-k-out-of-n:Fsystem

I. Antonopoulou and S. Papastavridis (1987) published an algorithm for computing the reliability of a circular consecutive-k-out-of-n:F system which claimed O (kn) time. J.S. Wu and R.J. Chen (1993) correctly pointed out that the algorithm achieved only O(kn²) time. The present study shows that the algorithm can be implemented for O(kn) time     

On (k, t)-subnormal covering codes

The concept of a (k, t)-subnormal covering code is defined. It is discussed how an amalgamated-direct-sumlike construction can be used to combine such codes. The existence of optimal (q, n, M) 1 codes C is discussed such that by puncturing the first coordinate of C one obtains a code with (q, 1)-subnorm 2