Search

In this paper we study array-based codes over graphs for correcting multiple node failures. These codes have applications to neural networks, associative memories, and distributed storage systems. We assume that the information is stored on the edges of a complete undirected graph and a node failure is the event where all the edges in the neighborhood of a given node have been erased. A code over graphs is called $\rho $ -node-erasure-correcting if it allows to reconstruct the erased edges upon the failure of any $\rho $ nodes or less. We present a binary optimal construction for double-node-erasure correction together with an efficient decoding algorithm, when the number of nodes is a prime number. Furthermore, we extend this construction for triple-node-erasure-correcting codes when the number of nodes is a prime number and two is a primitive element in $\mathbb {Z}_{n}$ . These codes are at most a single bit away from optimality.

Let q=pm where p is an odd prime, mges2, and 1lesklesm-1. Let Tr be the trace mapping from Fq to Fp and zetap=e2pii/p be a primitive pth root of unity. In this paper, we determine the value distribution of the following exponential sums: SigmaxisinF qchi(alphaxp k +1+betax2) (alpha, betaisinFq) where chi(x)=zetap Tr(x) is the canonical additive character of Fq. As applications, we have the following. 1) We determine the weight distribution of the cyclic codes C1 and C2 over Fpt with parity-check polynomial h2(x)h3(x) and h1(x)h2(x)h3(x), respectively, where t is a divisor of d=gcd(m, k), and h1(x), h2(x) , and h3(x) are the minimal polynomials of pi-1, pi-2, and pi-(p k +1) over Fpt, respectively, for a primitive element pi of Fq. 2) We determine the correlation distribution between two m-sequences of period q-1. Moreover, we find a new class of p-ary bent functions. This paper extends the results in Feng and Luo (2008).

In this paper we present a unified way to determine the values and their multiplicities of the exponential sums SigmaxisinF(q)zetap Tr(af(x)+bx)(a,bisinFq,q=pm,pges3) for all perfect nonlinear functions f which is a Dembowski-Ostrom polynomial or p = 3,f=x(3(k)+1)/2 where k is odd and (k,m)=1. As applications, we determine (1) the correlation distribution of the m-sequence {alambda=Tr(gammalambda)}(lambda=0,1,...) and the sequence {blambda=Tr(f(gammalambda))}(lambda=0,1,...) over Fp where gamma is a primitive element of Fq and (2) the weight distributions of the linear codes over Fp defined by f.

Let be the integer residue ring with odd prime and integer . For a sequence over , there is an unique -adic expansion , where each is a sequence over , and can be regarded as a sequence over the prime field GF naturally. Let be a strongly primitive polynomial over , and the set of all primitive sequences generated by over . Suppose that GF GF . It is shown that any function in is an injective map from to GF, and the derived sequences of different functions are also different. That is, if and only if and for and . These injective functions in can be considered as good candidates for the keys of a stream cipher.

If R = F/sub q/[x/spl rceil/]/(x/sup m/ - 1), S = F/sub qn/[x]/(x/sup m/ - 1), we define the mapping a_(x) /spl rarr/ A(x) =/spl sigma//sub 0//sup n-1/a/sub i/(x)/spl alpha//sub i/ from R/sup n/ onto S, where (/spl alpha//sub 0/, /spl alpha//sub i/,..., /spl alpha//sub n-1/) is a basis for F/sub qn/ over F/sub q/. This carries the q-ray 1-generator quasicyclic (QC) code R a_(x) onto the code RA(x) in S whose parity-check polynomial (p.c.p.) is defined as the monic polynomial h(x) over F/sub q/ of least degree such that h(x)A(x) = 0. In the special case, where gcd(q, m) = 1 and where the prime factorizations of x/sub m/ 1 over F/sub q/ and F/sub qn/ are the same we show that there exists a one-to-one correspondence between the q-ary 1-generator quasis-cyclic codes with p.c.p. h(x) and the elements of the factor group J* /I* where J is the ideal in S with p.c.p. h(x) and I the corresponding quantity in R. We then describe an algorithm for generating the elements of J*/I*. Next, we show that if we choose a normal basis for F/sub qn/ over F/sub q/, then we can modify the aforementioned algorithm to eliminate a certain number of equivalent codes, thereby rending the algorithm more attractive from a computational point of view. Finally in Section IV, we show how to modify the above algorithm in order to generate all the binary self-dual 1-generator QC codes.

The determination of normal bases for finite fields, particularly over the finite field F/sub 2/, is of importance in applications such as coding and cryptography. This correspondence gives an explicit normal basis for a finite field F/sub 2/(p-1)p/sup m/ over F/sub 2/, when 2 is a primitive element module p/sup 2/. In the case when p=3, an explicit dual basis is also obtained.

Abramson and Bose and Chakravarti have constructed, simultaneously and independently, binary group codes which correct errors in bursts of three or less for even redundancy. In this paper the corresponding problem when the redundancy is odd is considered. Let r = 2m + 1, m \geqq 4 , and let A be an mxr matrix whose rows are the r -place binary vectors \alpha_1, \alpha_2, \cdots \alpha_n . We show that A satisfies the necessary and sufficient condition for being the parity check matrix of the required code if it is obtained in the following manner: Let x be a primitive element of GF (2^m) , y be a primitive element of GF (2^{m-1}) and z be a primitive element of GF (2^2) . Further suppose 1 + x = x^{\phi}, 1 + y = y^{\phi} where \theta \neq 2 (mod 3) if m is even and \phi \neq 2(mod 3) if m is odd. Let \beta_i be the coefficient vector of the (m-1) -th degree polynomial in x , which represents x^i and let \lambda_i and \rho^i have similar meanings with reference to y^i and z^i . Then \alpha_i = (\beta_i, \lambda_i, \rho_i), i = 0, 1, \cdots (2^m-l) (2^{m--1}-1)- l. Although this method does not yield an optimum n , it is easily shown that as m increases n = (2^m -1) (2^{m-1} -1) approaches the optimal value.

The analysis and synthesis of polynomials and sequences over GF(2) has received considerable attention in recent years with the increasing use of PN sequences. In this paper a new approach to the problem is presented in which the polynomial coefficients and the sequence digits are derived in terms of the values assumed by a special class of polynomials, called "cyclonomials," at an arbitrary primitive element of GF(2^n) . For each value of n the cyclonomials are determined by the partition of the set \{ 0,1,2, \cdots ,2^n - 2 \} into cyclotomic cosets. A method of deriving all primitive polynomials of degree n from a given one of the same degree is described. A short outline of an approach to the more difficult task of synthesizing an initial primitive polynomial is also presented.

Except for some elementary definitions and fundamentals, the theory of AN code is by and large the theory of binary (radix = 2) arithmetic codes. It is often believed (erroneously) that this theory can be readily generalized to any nonbinary radix. The very fundamental theorems of Brown and Peterson on single-error-correcting codes have been derived for the binary case only. Whereas a generalized version of Brown's theorem can be stated and proved relatively easily (as shown here), the one for Peterson's theorem is not forthcoming. However, we have succeeded in deriving a theorem for the ternary case (radix = 3) somewhat along the lines of the Peterson's theorem as follows. Let M_3 (A, d) denote the smallest positive integer such that the arithmetic weight of A M_3 (A, d) in ternary representation is less than d . Also ley A = 2p for some odd prime p . Then 3 is a primitive element of GF(p) if and only if \begin{equation} M_3 (A, 3)=(3^{(p-1)/2} + 1)/A. \end{equation}

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 logarithm Z(x) of x is defined by the equation \alpha^{z(x)}=\alpha^{x} + 1 , where \alpha is a primitive element, zero is written as \alpha^{\ast} , and x=\ast,O,1, \cdots ,p^{n}-2 . A simple algorithm for making a table of Zech's logarithms is presented.