On certain projective geometry codes (Corresp.)

LetVbe an(n, k, d)binary projective geometry code withn = (q^{m}-1)/(q - 1), q = 2^{s}, andd geq [(q^{m-r}-1)/(q - 1)] + 1. This code isr-step majority-logic decodable. With reference to the GF(q^{m}) = {0, 1, alpha , alpha^{2} , cdots , alpha^{n(q-1)-1} }, the generator polynomialg(X), ofV, hasalpha^{nu}as a root if and only ifnuhas the formnu = i(q - 1)andmax_{0 leq l < s} W_{q}(2^{l} nu) leq (m - r - 1)(q - 1), whereW_{q}(x)indicates the weight of the radix-qrepresentation of the numberx. LetSbe the set of nonzero numbersnu, such thatalpha^{nu}is a root ofg(X). LetC_{1}, C_{2}, cdots, C_{nu}be the cyclotomic cosets such thatSis the union of these cosets. It is clear that the process of findingg(X)becomes simpler if we can find a representative from eachC_{i}, since we can then refer to a table, of irreducible factors, as given by, say, Peterson and Weldon. In this correspondence it was determined that the coset representatives for the cases ofm-r = 2, withs = 2, 3, andm-r=3, withs=2.     

On MDS extensions of generalized Reed- Solomon codes

An(n, k, d)linear code overF=GF(q)is said to be {em maximum distance separable} (MDS) ifd = n - k + 1. It is shown that an(n, k, n - k + 1)generalized Reed-Solomon code such that2leq k leq n - lfloor (q - 1)/2 rfloor (k neq 3 {rm if} qis even) can be extended by one digit while preserving the MDS property if and only if the resulting extended code is also a generalized Reed-Solomon code. It follows that a generalized Reed-Solomon code withkin the above range can be {em uniquely} extended to a maximal MDS code of lengthq + 1, and that generalized Reed-Solomon codes of lengthq + 1and dimension2leq k leq lfloor q/2 rfloor + 2 (k neq 3 {rm if} qis even) do not have MDS extensions. Hence, in cases where the(q + 1, k)MDS code is essentially unique,(n, k)MDS codes withn > q + 1do not exist.     

On cyclic MDS codes of length q over GF(q) (Corresp.)

It is shown that a cyclic codeCof lengthqover GF(q)is the maximum distance separable if and only if either1) qis a prime, in which caseCis equivalent, up to a coordinate permutation, to an extended Reed-Solomon code, or2) Cis a trivial code of dimensionk in {1, q - 1, q }. Hence there exists a nontrivial cyclic extended Reed-Solomon code of lengthqover GF(q)if and only ifqis a prime.     

Using codes for error correction and detection (Corresp.)

A linear codeCover GF(q)is good fort-error-correction and error detection ifP(C,t;epsilon) leq P(C,t;(q - 1)/q)for allepsilon, 0 leq epsilon leq (q - 1)/q, whereP(C, t; epsilon)is the probability of an undetected error after a codeword inCis transmitted over aq-ary symmetric channel with error probabilityepsilonand correction is performed for all error patterns withtor fewer errors. A sufficient condition for a code to be good is derived. This sufficient condition is easy to check, and examples to illustrate the method are given.     

Dual product constructions of Reed - Muller type codes (Corresp.)

Various linear and nonlinearR(r,m)codes having parameters(2^{m}, 2^{k}, 2^{m-r})withk=sum_{i=0}^{r}left(^{m}_{i}right)are constructed fromR(r,q)andR(r,p)codes,m=p+q. A dual construction forR(m-r,m)codes fromR(p-r,p)andR(q-r,q)codes is also presented,m=p+q. As a simple corollary we have that the number of nonequivalentR(r,m)codes is at least exponential in the length (forr>1). ForR(m-r,m)codes, the lower bound is doubly exponential in the length (forr>1).     

Weight hierarchies of extremal non-chain binary codes of dimension4

The weight hierarchy of a linear [n,k;q] code C over GF(q) is the sequence (d₁,d₂,···,d_k ) where d_r is the smallest support of an r-dimensional subcode of C. An [n,k;q] code is extremal nonchain if, for any r and s, where 1⩽rS(D)=d_r, and w_S (E)=d_s. The possible weight hierarchies of such binary codes of dimension 4 are determined     

The geometry of quadrics and correlations of sequences (Corresp.)

Nondegenerate quadrics of PG(2l, 2^{s})have been used to construct ternary sequences of length(2^{2sl+1} - 1)/(2^{s} - 1)with perfect autocorrelation function. The same construction can be used for degenerate quadrics for this case as well as quadrics of PG(N,q), withNarbitrary andq = p^{s}, for any primep. This is possible because it is shown that ifQ subseteq {rm PG} (N, q)is a quadric, possibly degenerate, that has the same size as a hyperplane, then, providedQitself is not a hyperplane, the hyperplanes of PG(N,q)intersectQin three sizes. These sizes depend on whetherNis even or odd and the degeneracy ofQ. Finally, a connection to maximum period linear recursive sequences is made.     

Products of linear recurring sequences with maximum complexity

Conditions are derived which guarantee that products of linear recurring sequences attain maximum linear complexity. It is shown that the product of any number of maximum-length GF(q)sequences has maximum linear complexity, provided only the degrees of the corresponding minimal polynomials are distinct and greater than two. It is also shown that if the roots of any number of (not necessarily irreducible) minimal polynomials are simple and lie in extension fields of pairwise relatively prime degrees, then the product of the corresponding GF(q)sequences attains maximum linear complexity, provided only that no two roots of any minimal polynomial are linearly dependent over the groundfield GF(q)(which is automatically satisfied whenq = 2). The results obtained for products are extended to arbitrary linear combinations of product sequences.     

On estimating spectral moments in the presence of colored noise

Let{q^(1) (t)}, the signal, be a complex Gaussian process corrupted by additive Gaussian noise{q^(2) (t) }. Observations onp(t)q(t)andp(t) q^(2) (t)are assumed to be available wherep(t)is a smooth weighting function andq = q^(1) + q^(2). Using the Fourier transform of the samples ofp(t)q(t)andp(t) q^(2) (t), estimators are derived for estimating the mean frequency and spectral width of the unknown power spectrum of the unweighted signal process. The means and variances of these statistics are computed in general, and explicitly for nontrivial practical examples. Asymptotic formulas for the moment estimators as a function of the number of realizations, frequency resolution, signal-to-noise ratio and spectral width, and consistency of the estimators are some of the results that are discussed in detail.     

Quadriphase sequences for spread- spectrum multiple-access communication

This paper studies constructions for quadriphase sequences that are suitable for use as signature sequences in quadriphase spread-spectrum multiple-access communications. Quadriphase sequences are closely related to biphase (i.e., binary) sequences, and many of the properties of the former can be expressed in terms of properties of the latter. Methods of construction are presented which obtain sets of quadriphase sequences from sets of biphase sequences. Methods of construction of quadriphase sequences are provided based upon the properties of the multiplicative characters of the finite field GF(q)whereq equiv 1 mod 4. These methods use codewords from low-rate Reed-Solomon codes, which are mapped onto the fourth roots of unity.2q + 2sequences of periodq - 1are constructed, for which the maximum magnitudes of the periodic cross correlation and the periodic out-of-phase autocorrelation are bounded by3 sqrt{q} + 5.     

Improving an algorithm for factoring polynomials over a finite field and constructing large irreducible polynomials

Letf(x)in {bf F}_{q}[X]be a polynomial with simple roots to be factored. The so-called Berlekamp subalgebraBspanned over{bf F}_{q}by the idempotents ofA={bf F}_{q}[X]/(f(X))is considered. An exponential technique introduced earlier is based upon taking elements from B at random and enables us to obtain idempotents and, from that, the factors of f(X). This algorithm is speeded up in three ways. The concept of a separating subset of B is introduced and the McEliece operator mapping A onto B is used to construct a small separating set. {em Factoring} subsets of{bf F}_{q}were defined and investigated previously. The algorithm and these subsets are used together with a process introduced by F. J. McWilliams for the rapid construction of primitive idempotents. Finally, an algorithm is introduced for constructing irreducible polynomials of{bf F}_{q}[X]of degreed, for large values ofd, in which the most expensive operation is the Euclidian algorithm applied to two polynomials of degree2d.     

Decoding of erasures and errors for certain RS codes by decreased redundancy

A method is presented for decoding erasures and errors in Reed-Solomon (RS) codes over GF(q). It uses fewer operations when the code is of medium or low rate, when the number of erasures is relatively large, and whenq-1is prime. This method can be used in conjunction with the customary method of decoding RS codes and can decrease the maximum number of operations needed to decode certain codes. This procedure is also applicable to generalized RS codes of lengthqover GF(q).     

VI-2 class of Hamming weight of -aryq linear codes with dimension 5

The Hamming weight hierarchy of a linear [n,k;q] code c over GF(q)is the sequence(d₁,d₂,…,d_k),where d_r is the smallest support weight of an r-dimensional subcode of c.According to some new necessary conditions,the VI class Hamming weight hierarchies of q -ary linear codes of dimension 5 can be divided into six subclasses. By using the finite projective geometry method, VI-2 subclass and determine were researched almost all weight hierarchies of the VI-2 subclass of weight hierarchies of q -ary linear codes with dimension 5.     

Resilient functions over finite fields

Resilient functions play an important role in the art of information security. In this correspondence, we discuss the existence, construction, and enumeration of resilient functions over finite fields. We show that, for each finite field GF(q) with q > 3, we can easily construct a large number of (q, n, 1, n - 1) resilient functions, most of which include mixing terms. We give a general structure for (q, m + 1, m, 1) resilient functions, and present an example which is not of this general structure. We prove that (q, m + 2, m, 2) resilient functions exist for any m such that 1 < m < q when q > 2. We prove that (q, m + t, m, t) resilient functions exist for any (m, t) such that 1 < m < q and 2 < t < q when q > 3. By making some simple generalizations of former results, we also provide some new methods for constructing resilient functions.     

A product construction for perfect codes over arbitrary alphabets (Corresp.)

A general product construction for perfect single-error-correcting codes over an arbitrary alphabet is presented. Given perfect single-error-correcting codes of lengthsn, m, andq + 1over an alphabet of orderq, one can construct perfect single-error-correcting codes of length(q - 1)nm + n + mover the same alphabet. Moreover, if there exists a perfect single-error-correcting code of lengthq + 1over an alphabet of orderq, then there exist perfect single-error-correcting codes of lengthn,n = (q^{t} _ 1)/(q - 1), and(t > 0, an integer). Finally, connections between projective planes of orderqand perfect codes of lengthq + 1over an alphabet of orderqare discussed.     

On the Probability of Undetected Error for the Maximum Distance Separable Codes

In this paper we investigate the performance of maximum-distance-separable codes with symbols fromGF(q)when they are used for pure error detection or for simultaneous error correction and detection over aq-input andq-output discret memoryless channel with symbol error probability ε. First we show that the probability of undetected error for an MDS code used for pure error detection is upper bounded byq^{-r}and decreases monotonically as εdecreases from(q - 1)/qto 0, whereris the number of parity-check symbols of the code. Then we show that the probability of undetected error for an MDS code used for correctingtor fewer symbol errors is upper bounded byq^{-r} Summin{i=0}max{t}(min{i} max{n})(q - 1)^{i}and decreases monotonically as ε decreases from(q - 1)/qto 0. These results show that the MDS codes are effective for both pure error detection and simultaneous error correction and detection.     

A fast algorithm for determining the linear complexity of asequence with period pn over GF(q)

A fast algorithm is presented for determining the linear complexity of a sequence with period pⁿ over GF (q), where p is an odd prime, and where q is a prime and a primitive root (mod p²)     

General theory of doubly periodic arrays over an arbitrary finite field and its applications

A general theory of doubly periodic (DP) arrays over an arbitrary finite field GF(q)is presented. First the basic properties of DP arrays are examined. Next modules of linear recurring (LR) arrays are defined and their algebraic properties discussed in connection with ideals in an extension ringtilde{R}of the ringRof bivariate polynomials with coefficients in GF(q). A finitetilde{R}-module of DP arrays is shown to coincide with thetilde{R}-module of LR arrays dermed by a zero-dimensional ideal intilde{R}. Equivalence relations between DP arrays are explored, i.e., rearrangements of arrays by means of unimodular transformations. Decimation and interleaving of arrays are defined in a two-dimensional sense. The general theory is followed by application to irreducible LR arrays. Among irreducible arrays,M-arrays are a two-dimensional analog ofM-sequences and may be constructed fromM-sequences by means of unimodular transformations. The results of this paper are also important in studying properties of Abelian codes.     

On generator matrices of MDS codes (Corresp.)

It is shown that the family ofq-ary generalized Reed-Solomon codes is identical to the family ofq-ary linear codes generated by matrices of the form[I|A], whereIis the identity matrix, andAis a generalized Cauchy matrix. Using Cauchy matrices, a construction is shown of maximal triangular arrays over GF(q), which are constant along diagonals in a Hankel matrix fashion, and with the property that every square subarray is a nonsingular matrix. By taking rectangular subarrays of the described triangles, it is possible to construct generator matrices[I|A]of maximum distance separable codes, whereAis a Hankel matrix. The parameters of the codes are(n,k,d), for1 leq n leq q+ 1, 1 leq k leq n, andd=n-k+1.     

Temperature dependence of MOSFET characteristics in weak inversion

A knowledge of the MOSFET operating in weak inversion is important for circuits with low leakage specifications. This paper discusses the effect of temperature on the MOSFET in weak inversion. The reciprocal slopenof the log IDSversus VGSrelationship between source-drain current IDSand gate bias VGSmay be given byfrac{1}{(n - 1 - gamma)^{2}} = frac{2Cmin{ox}max{2}}{qepsilon_{s}N_{B}} [frac{3}{4} frac{E_{g^{0}}{q} - (frac{3}{2}alpha + frac{k}{q})T]withalpha equiv (k/q)(38.2 - ln N_{B} + (3/2) ln T)and γ ≡C_{ss}/C_{ox}, where Coxis the oxide capacitance per unit area, Cssthe surface states capacitance per unit area,qthe electronic charge, εsthe permittivity of silicon, NBthe bulk doping concentration,kthe Boltzmann's constant,Tthe absolute temperature, andE_{g0}the extrapolated value of the energy gap of lightly doped silicon atT = 0K. This theoretical formula was in good agreement with experimental results in a temperature range of interest.