We compute the weight distribution of binary cyclic codes with arbitrarily many generalized Niho-type nonzeroes, where the exponents of the nonzeroes nearly form a long arithmetic progression. Determining their weight distribution requires two distinct techniques. The first involves using the polar representation associated with generalized Niho-type exponents and leveraging the subtle structure of the nonzeroes whose exponents are close to an arithmetic progression. The second applies the weight distribution of binary Zetterberg codes to address certain counting problems. This resolves two open questions raised by Li and Zeng.

Abstract In this paper we carry out an in-depth study on the average decoding error probability of the random parity-check matrix ensemble over the erasure channel under three decoding principles, namely unambiguous decoding, maximum likelihood decoding and list decoding. We obtain explicit formulas for the average decoding error probabilities of the random parity-check matrix ensemble under these three decoding principles and compute the error exponents. Moreover, for unambiguous decoding, we compute the variance of the decoding error probability of the random parity-check matrix ensemble and the error exponent of the variance, which implies a strong concentration result, that is, roughly speaking, the ratio of the decoding error probability of a random linear code in the ensemble and the average decoding error probability of the ensemble converges to 1 with high probability when the code length goes to infinity.

Abstract Given a polynomial f over the finite field $$\mathbb {F}_q$$ F q , its intersection distribution provides fruitful information on how lines in the affine plane intersect the graph of f over $$\mathbb {F}_q$$ F q . The intersection distribution in its simplest cases gives rise to oval polynomials in finite geometry and Steiner triple systems in design theory. Previously, the intersection distribution of degree two and degree three polynomials has been computed. In this paper, we determine the intersection distribution of all degree four polynomials over finite fields. As an application, we present a direct construction of Steiner systems using polynomials with prescribed intersection distribution.

The cross-correlation problem is a classic problem in sequence design. In this paper we compute the cross-correlation distribution of the Niho-type decimation$d=3(p^{m}-1)+1$over${\mathrm {GF}}(p^{2m})$for any prime$p \ge 5$. Previously this problem was solved by Xia et al. only for$p=2$and$p=3$in a series of papers. The main difficulty of this problem for$p \ge 5$, as pointed out by Xia et al., is to count the number of codewords of “pure weight” 5 in p-ary Zetterberg codes. It turns out this counting problem can be transformed by the MacWilliams identity into counting codewords of weight at most 5 in p-ary Melas codes, the most difficult of which is related to a K3 surface well studied in the literature and can be computed. When$p \ge 7$, the theory of elliptic curves over finite fields also plays an important role in the resolution of this problem.

Let$n$be a positive integer and$p$a prime. The power mapping$x^{p^{n}-3}$over${\mathbb {F}}_{p^{n}}$has desirable differential properties, and its differential spectra for$p=2,\,3$have been determined. In this paper, for any odd prime$p$, by investigating certain quadratic character sums and some equations over${\mathbb {F}}_{p^{n}}$, we determine the differential spectrum of$x^{p^{n}-3}$with a unified approach. The obtained result shows that for any given odd prime$p$, the differential spectrum can be expressed explicitly in terms of$n$. Compared with previous results, a special elliptic curve over${\mathbb {F}}_{p}$plays an important role in our computation for the general case$p \ge 5$.

Let m be an even positive integer. A Boolean bent function f on F(2m-1)×F2is called a cyclic bent function if for any a≠b∈F(2m-1) and ε∈F2, f( ax1,x2)+f( bx1,x2+ε) is always bent, where x1∈F(2m-1),x2∈F2. Cyclic bent functions look extremely rare. This paper focuses on cyclic bent functions on F(2m-1)×F2and their applications. The first objective of this paper is to establish a link between quadratic cyclic bent functions and a special type of prequasifields, and construct a class of quadratic cyclic bent functions from the Kantor-Williams prequasifields. The second objective is to use cyclic bent functions to construct families of optimal sequences. The results of this paper show that cyclic bent functions have nice applications in several fields such as coding theory, symmetric cryptography, and CDMA communication.

It is known that the empirical spectral distribution of random matrices obtained from linear codes of increasing length converges to the well-known Marchenko-Pastur law, if the Hamming distance of the dual codes is at least 5. In this paper, we prove that the convergence rate in probability is at least of the order$n^{-1/4}$where$n$is the length of the code.

Extending previous results, we study a class of general quadrinomials over the field of size 22mwith odd m and characterize conditions under which they are permutations with 4-uniform BCT, a new and important parameter related to boomerang-style attacks. These permutations are known to have the best known nonlinearity. Numerical data also show that the inverse of these functions all have large algebraic degree, making them desirable for applications.

In this paper, we provide two complementary results for cyclic codes of composite length. First, we give a general construction of cyclic codes of length nr from cyclic codes of length n and a lower bound on the minimum distance. Numerical data show that many cyclic codes of composite length with the best parameters can be obtained in this way. Second, in the other direction, we show that for cyclic codes of length n with a primitive n-th root of unity as a non-zero, the minimum distance is roughly bounded by the square-free part of n. This means that we shall not expect good cyclic codes of length n in general if, for example, the length n is divisible by a high power of a prime.

Boolean functions, coding theory and t-designs have close connections and interesting interplay. A standard approach to constructing t-designs is the use of linear codes with certain regularity. The Assmus-Mattson Theorem and the automorphism groups are two ways for proving that a code has sufficient regularity for supporting t-designs. However, some linear codes hold t-designs, although they do not satisfy the conditions in the Assmus-Mattson Theorem and do not admit a t-transitive or t-homogeneous group as a subgroup of their automorphisms. The major objective of this paper is to develop a theory for explaining such codes and obtaining such new codes and hence new t-designs. To this end, a general theory for punctured and shortened codes of linear codes supporting t-designs is established, a generalized Assmus-Mattson theorem is developed, and a link between 2-designs and differentially δ-uniform functions and 2-designs is built. With these general results, binary codes with new parameters and explicit weight distributions are obtained, new 2-designs and Steiner system S(2, 4, 2n) are produced in this paper.

In this paper, we consider a new normalization of matrices obtained by choosing distinct codewords at random from linear codes over finite fields and find that under some natural algebraic conditions of the codes their empirical spectral distribution converges to Wigner's semicircle law as the length of the codes goes to infinity. One such condition is that the dual distance of the codes is at least five. This is analogous to previous work on the empirical spectral distribution of similar matrices obtained in this fashion that converges to the Marchenko-Pastur law.

In this paper, we first study deviations of the complete weight distribution of a linear code from that of a random code. Then, we consider a large family of subfield subcodes of algebraic-geometric codes over prime fields which include BCH codes and Goppa codes and prove that the complete weight distribution is close to that of a random code if the code length is large compared with the genus of the curve and the degree of the divisor defining the code.

In an interesting paper, Prof. C. Ding provided three constructions of cyclic codes of length being a product of two primes. Numerical data shows that many codes from these constructions are best cyclic codes of the same length and dimension over the same finite field. However, not much is known about these codes. In this paper, we explain some of the numerical data by developing a general method on cyclic codes of composite length and on estimating the minimum distance. We also provide a general construction of cyclic codes of composite length which are related to Ding's constructions. Numerical data shows that it produces many best cyclic codes as well. Finally, we point out how these cyclic codes can be used to construct convolutional codes with large free distance.

Cyclic codes are widely employed in communication systems, storage devices, and consumer electronics, as they have efficient encoding and decoding algorithms. BCH codes, as a special subclass of cyclic codes, are in most cases among the best cyclic codes. A subclass of good BCH codes are the narrow-sense BCH codes over GF(q) with length n = (qm-1)/(q -1). Little is known about this class of BCH codes when q > 2. The objective of this paper is to study some of the codes within this class. In particular, the dimension, the minimum distance, and the weight distribution of some ternary BCH codes with length n = (3m- 1)/2 are determined in this paper. A class of ternary BCH codes meeting the Griesmer bound is identified. An application of some of the BCH codes in secret sharing is also investigated.

Maximum-distance separable (MDS) convolutional codes form an optimal family of convolutional codes, the study of which is of great importance. There are very few general algebraic constructions of MDS convolutional codes. In this paper, we construct a large family of partial-unit-memory MDS convolutional codes over Fqwith flexible parameters. Compared with the previous work, the field size q required to define these codes is much smaller. The construction also leads to many new strongly MDS convolutional codes, an important subclass of MDS convolutional codes. Some examples are presented at the end of this paper.

Constacyclic codes which generalize the classical cyclic codes have played important roles in recent constructions of many new quantum maximum distance separable (MDS) codes. However, the mathematical mechanism may not have been fully understood. In this paper, we use pseudo-cyclic codes, which is a further generalization of constacyclic codes, to construct the quantum MDS codes. We can not only provide a unified explanation of many previous constructions, but also produce some new quantum MDS codes.

The generalized Hamming weights (GHWs) of linear codes are fundamental parameters, the knowledge of which is of great interest in many applications. However, to determine the GHWs of linear codes is difficult in general. In this paper, we study the GHWs for a family of reducible cyclic codes and obtain the complete weight hierarchy in several cases. This is achieved by extending the idea of Yang et al. into higher dimension and by employing some interesting combinatorial arguments. It shall be noted that these cyclic codes may have arbitrary number of nonzeros.

In this paper, we extend two earlier works further in two directions and compute the weight distribution of these cyclic codes under more relaxed conditions. It is interesting to note that many cyclic codes in the family are optimal and have only a few non-zero weights. Besides using similar ideas, we carry out some subtle manipulation of certain exponential sums.

Zero-difference balanced (ZDB) functions integrate a number of subjects in combinatorics and algebra, and have many applications in coding theory, cryptography, and communications engineering. In this paper, three new families of ZDB functions are presented. The first construction gives ZDB functions defined on the abelian groups (GF(q1)×,...,×GF(qk),+) with new and flexible parameters. The other two constructions are based on 2-cyclotomic cosets and yield ZDB functions on \BBZn with new parameters. The parameters of optimal constant composition codes, optimal, and perfect difference systems of sets obtained from these new families of ZDB functions are also summarized.

In a series of remarkable papers, Babadi and Tarokh proved the randomness of matrices and product of two matrices arising from binary linear block codes with respect to the empirical spectral distribution, provided that their dual distances are sufficiently large. However, numerical experiments conducted by Babadi and Tarokh revealed that Gold codes, which have a dual distance of 5, also possess such a randomness property. Hence, the interesting question was raised as to whether or not the stringent requirement of large dual distances can be relaxed in the theorems in order to explain the mysterious randomness of Gold sequences. In this paper, we improve the results of Babadi and Tarokh on several fronts and provide an affirmative answer to this question.

Cyclic codes have been widely used in digital communication systems and consumer electronics as they have efficient encoding and decoding algorithms. The weight distribution of cyclic codes has been an important topic of study for many years. It is in general hard to determine the weight distribution of linear codes. In this paper, a class of cyclic codes with any number of zeros is described and their weight distributions are determined.

Cyclic codes are a subclass of linear codes and have wide applications in consumer electronics, data storage systems, and communication systems due to their efficient encoding and decoding algorithms. Cyclic codes with many zeros and their dual codes have been a subject of study for many years. However, their weight distributions are known only for a very small number of cases. In general, the calculation of the weight distribution of cyclic codes is heavily based on the evaluation of some exponential sums over finite fields. Very recently, Li studied a class of p-ary cyclic codes of length p2m-1, where p is a prime and m is odd. They determined the weight distribution of this class of cyclic codes by establishing a connection between the involved exponential sums with the spectrum of Hermitian forms graphs. In this paper, this class of p-ary cyclic codes is generalized and the weight distribution of the generalized cyclic codes is settled for both even m and odd m along with the idea of Li The weight distributions of two related families of cyclic codes are also determined.