This paper describes the asymptotic behavior of normalized linear complexity of ultimately nonperiodic binary sequence. The linear complexity of s/sup n/, L/sub s/(n), is defined as the length of the shortest linear feedback shift register which generates s/sup n/. The research method and results studied in this paper seem to be very useful in characterizing the purely random sequence and distinguishing a key stream generator from a uniformly random sequence.

For an ultimately nonperiodic binary sequence s={s/sub t/}/sub t/spl ges/0/, it is shown that the set of the accumulation values of the normalized linear complexity, L/sub s/(n)/n, is a closed interval centered at 1/2, where L/sub s/(n) is the linear complexity of the length n prefix s/sup n/=(s/sub 0/,s/sub 1/,...,s/sub n-1/) of the sequence s. It was known that the limit value of the normalized linear complexity is equal to 0 or 1/2 if it exists. A method is also given for constructing a sequence to have the closed interval [1/2-/spl Delta/, 1/2+/spl Delta/](0/spl les//spl Delta//spl les/1/2) as the set of the accumulation values of its normalized linear complexity.

A unified derivation of the bounds of the linear complexity is given for a sequence obtained from a periodic sequence over GF(q) by either substituting, inserting, or deleting k symbols within one period. The lower bounds are useful in case of n

This correspondence tries to construct a direct-sequence spread-spectrum multiple-access communication system, so that the difficulty of wiretapping from insiders' and outsiders' attacks increases and the worst case error probability decreases, as much as possible. Bent sequences with optimal periodic correlation properties are assigned to users, as spreading sequences corresponding to secret keys.

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

It is shown that the linear complexity for one-symbol substitution of any periodic sequence over GF(q) can be computed without any condition on the minimal polynomial of the sequence.

Kumar and Moreno (see ibid., vol.37, no.3, p.603, 1991) presented a new family of nonbinary sequences which has not only good periodic correlation properties but also the largest family size. First, the unbalanced properties for Kumar-Moreno sequences are pointed out. Second, a new family of balanced nonbinary sequences obtained from modified Kumar-Moreno sequences is proposed, and it is shown that the new family has the same optimal periodic nontrivial correlation as the family of Kumar-Moreno sequences and consists of the balanced nonbinary sequences. It is also shown that the cost of making sequences balanced is a decrease of the family size in addition to the condition that n is an even number. In particular, let the length of Kumar-Moreno sequences and the new sequences be the same and equal to p/sup n/-1 with n even, then the family size of the new sequences is p/sup n/2/ which is much smaller than p/sup n/, that of Kumar-Moreno sequences.>

The real-valued bent function was previously introduced by the authors (1991) as a generalization of the usual p-ary bent function, p a prime, in such a way that the range of the function is the set of real numbers, i.e. not restricted to GF(p). The real-valued bent function was used to construct a family of 2/sup n/2/ balanced quadriphase sequences of period 2/sup n/-1 with optimal periodic correlation properties, where n is a multiple of four. A class of real-valued bent functions that map the set of all the m-tuples over GF(2) into the set (0,1/2,1,3/2) for an arbitrary m is given. This is applied to generalize a previous construction to the case where n is even, i.e. not restricted to a multiple of four. It is also shown that the quadriphase sequences given by T. Novosad can be considered as one kind of sequence constructed by real-valued bent functions. Conditions are given for some families of the quadriphase sequences constructed by some real-valued bent functions to be balanced. The exact distributions of the periodic correlation values are derived for the families of the balanced quadriphase sequences.>

Another viewpoint is presented on the derivation of the Berlekamp-Massey algorithm. Our approach differs from previous ones in the following manner. The properties of the shortest linear feedback shift register that generates a given sequence are first derived Without reference to the Berlekamp-Massey algorithm. The Berlekamp-Massey algorithm is then derived using these properties. Our approach has the advantage of being easier to understand.

Conway showed that a table of Zech's logarithms is useful to perform addition in GF(p^{n})when the elements are represented as powers of a primitive element. The Zech's logarithmZ(x)ofxis defined by the equation\alpha^{z(x)}=\alpha^{x} + 1, where\alphais a primitive element, zero is written as\alpha^{\ast}, andx=\ast,O,1, \cdots ,p^{n}-2. A simple algorithm for making a table of Zech's logarithms is presented.