The existence of optimal binary self-orthogonal codes has been well characterized. In this paper, we develop general methods involving residual codes and the MacWilliams identities to prove the nonexistence of several infinite families of binary self-orthogonal codes, despite the existence of binary linear codes with the same parameters. In particular, we focus on the largest minimum distances of optimal binary self-orthogonal codes with dimension eight.

For integersu≥ 2 ands≥ 1, letq0 = 2u, and letCs(q0) be the generalized Zetterberg code of lengthn= qs0 + 1 over the finite field Fq0of characteristic 2. For odd characteristic, the covering radius ofCs(q0) was determined recently, whereas the case of even characteristic remained open. In this paper, we determine the covering radius of generalized Zetterberg codes over finite fields of characteristic 2, thereby solving this open problem. Our approach uses methods from the theory of algebraic curves over finite fields. As an application, we obtain an infinite family of quasi-perfect codes.

We propose a new coded space shift keying (CSSK) signaling technique for multi-user (MU), multiple-input multiple-output (MIMO) communication systems incorporating physical layer security (PLS). Besides its error correction ability, the designed linear code is capable of choosing transmit antenna indices automatically and selecting the best set of antenna combinations that minimizes the bit error rate (BER). Results obtained for the single-user (SU) schemes are then extended to a general single-cell downlink MU CSSK setting. A precoder design is proposed with a maximum ratio combining (MRC) technique to eliminate the multi-user interference (MUI) entirely by taking advantage of channel state information (CSI) at the transmitter. It is shown that the same precoding provides a very effective jamming signal for the PLS against passive eavesdroppers, degrading their signal-to-interference-plus-noise ratio (SINR) severely. A closed-form expression for the achievable secrecy rates is derived and it is maximized by the proposed power allocation algorithm. Finally, it is shown analytically and by computer simulations that substantially better BER performance is achieved by each user over interference-free transmission compared to an SU transmission with a maximum likelihood (ML) detector.

For an integer$s\ge 1$, let${\mathcal {C}}_{s}(q_{0})$be the generalized Zetterberg code of length$q_{0}^{s}+1$over the finite field${\mathbb {F}}_{q_{0}}$of odd characteristic. Recently, Shi et al. determined the covering radius of${\mathcal {C}}_{s}(q_{0})$for$q_{0}^{s} \cancel {\equiv }7 \pmod {8}$, and left the remaining case as an open problem. In this paper, we develop a general technique involving arithmetic of finite fields and algebraic curves over finite fields to determine the covering radius of all generalized Zetterberg codes for$q_{0}^{s} \equiv 7 \pmod {8}$, which therefore solves this open problem. We also introduce the concept of twisted half generalized Zetterberg codes of length$\frac {q_{0}^{s}+1}{2}$, and show the same results hold for them. As a result, we obtain some quasi-perfect codes.

The symbol-pair coding theory was put forward by Cassuto and Blaum [IEEE TIT, 2011] to be applicable in high-density storage situations. Yaakobiet al. [IEEE TIT, 2016] extended the concept of symbol-pair metric tob-symbol metric whenb≥ 2. The extensive research on theb-symbol Hamming weight spectra of cyclic codes has been centered on the case where the alphabet is a finite field. The case of cyclic codes over Z4, an extremely important class of codes, has been overlooked for a long time in the exploration of theb-symbol Hamming weight spectra. In this paper, we study theb-symbol Hamming weight spectra of the shortened Kerdock codesK−mand the Kerdock codesKmover Z4. The formulas for calculating the symbol-pair Hamming weight of the codewords inK−mandKmare given, and their values hinge on the trace-like function values of specific elements in the Teichmüller set. In particular, we present a class of Z4-cyclic codes with three non-zerob-symbol Hamming weights. As by-products, theb-symbol Hamming weight hierarchies of the Preparata codes and the Goethals codes are provided.

Determining the weight distribution of a code is an old and fundamental topic in coding theory that has been thoroughly studied. In 1977, Helleseth, Kløve, and Mykkeltveit presented a weight enumerator polynomial of the lifted code over${\mathbb {F}}_{q^{\ell } }$of a q-ary linear code with significant combinatorial properties, which can determine the support weight distribution of this linear code. The Solomon-Stiffler codes are a family of famous Griesmer codes, which were proposed by Solomon and Stiffler in 1965. In this paper, we determine the weight enumerator polynomials of the lifted codes of the projective Solomon-Stiffler codes using some combinatorial properties of subspaces. As a result, we determine the support weight distributions of the projective Solomon-Stiffler codes. In particular, we determine the weight hierarchies of the projective Solomon-Stiffler codes.

Let n ≥ 3 be an odd integer,d1=3n-1/2-1, d2=3n-2 andube an element of the finite field F3n. This paper shows thatfu(x)=uxd1+xd2is an almost perfect nonlinear (APN) function on F3n if and only if χ(u+1)= χ(u-1)=χ(u), where χ(∙) denotes the quadratic character of F3n. This settles the open problem raised by Ness and Helleseth in IEEE Trans. Inf. Theory 53(7): 2581-2586, 2007, where only the sufficiency part of the result was proved. Furthermore, we investigate the differential spectra offu(x)for elements u satisfying χ(u+1)=χ(u-1) and express them in terms of several quadratic character sums of cubic polynomials.

Nonlinear complexity is an important measure for assessing the randomness of sequences. In this paper we investigate how circular shifts affect the nonlinear complexities of finite-length binary sequences and then reveal a more explicit relation between nonlinear complexities of finite-length binary sequences and their corresponding periodic sequences. Based on the relation, we propose two algorithms that can generate all periodic binary sequences with any prescribed nonlinear complexity.

Let$ {\mathbb F}_{q_{0}}$be a finite field of odd characteristic. For an integer$s\ge 1$, let$\mathcal {C}_{s}(q_{0})$be the generalized Zetterberg code of length$q_{0}^{s}+1$over$ {\mathbb F}_{q_{0}}$. If$s$is even, then we prove that the covering radius of$\mathcal {C}_{s}(q_{0})$is 3. Put$q=q_{0}^{s}$. If$s$is odd and$q \not \equiv 7 \mod 8$, then we present an explicit lower bound$N_{1}(q_{0})$so that if$s \ge N_{1}(q_{0})$, then the covering radius of$\mathcal {C}_{s}(q_{0})$is 3. We also show that the covering radius of$\mathcal {C}_{1}(q_{0})$is 2. Moreover we study some cases when$s$is an odd integer with$3 \le s \le N_{1}(q_{0})$and, rather unexpectedly, we present concrete examples with covering radius 2 in that range. We introduce half generalized Zetterberg codes of length$(q_{0}^{s}+1)/2$if$q \equiv 1 \mod 4$. Similarly we introduce twisted half generalized Zetterberg codes of length$(q_{0}^{s}+1)/2$if$q \equiv 3 \mod 4$. We show that the same results hold for the half and twisted half generalized Zetterberg codes.

The$r$-th generalized Hamming metric and the$b$-symbol metric are two different generalizations of Hamming metric. The former is used on the wire-tap channel of Type II, and the latter is motivated by the limitations of the reading process in high-density data storage systems and applied to a read channel that outputs overlapping symbols. In this paper, we study the connections among the three metrics (that is, Hamming metric,$b$-symbol metric, and$r$-th generalized Hamming metric) mentioned above and give a conjecture about the$b$-symbol Griesmer Bound for cyclic codes.

The cross-correlation between two maximum length sequences ($m$-sequences) of the same period has been studied since the end of 1960s. One open conjecture by Helleseth states that the cross-correlation between any two$p$-ary$m$-sequences takes on the value −1 for at least one shift provided that the decimation$d$obeys$d\equiv 1\,({\mathrm{ mod}}\, p-1)$. This was known as the −1 conjecture. Up to now, the −1 conjecture was confirmed for the following decimations: (1) Niho-type decimations, i.e.,$d=s(p^{n/{2}}-1)+1$, where$s$is an integer; (2) all the complete permutation polynomial (CPP) exponents$d$satisfying$d\equiv 1\, ({\mathrm{ mod}}\, p-1) $; and (3) the additional families of decimations tabulated in this paper. In this paper, we first discuss the connection between the −1 conjecture on cross-correlation of$m$-sequences and CPP exponents, then we confirm the −1 conjecture for a new type of decimations by giving a new class of CPP exponents. The decimations are of the type$d=1+l{(p^{rtm}-1)}/{(r+1)}$over${\mathbb F}_{p^{rtm}}$, where$p$is a prime,$r+1$is an odd prime satisfying$p^{r/{2}} \equiv -1\,({\mathrm{ mod}}\, r+1)$,$t$is an odd integer ($t>2$if$p=2$) with$\gcd (t,r)=1$, and$m$is a positive integer. We transform the problem of determining whether$d$is a CPP exponent into that of investigating the existence of irreducible polynomials over$\mathbb {F}_{p}$with degree$t$satisfying a congruence equation. By a theorem given by Rosen that considered the number of irreducible polynomials with a special congruence relation, we prove that$d$is a CPP exponent over${\mathbb F}_{p^{rtm}}$for sufficiently large$t$. When$m$is odd, our new CPP exponents are of Niho type; thus, we give a new class of CPP exponents of Niho type. When$m$is even, we obtain a new class of CPP exponents which are not of Niho type. As a consequence, we show that the −1 conjecture is true for$d=1+l{(p^{rtm}-1)}/{(r+1)}$when$t$is a sufficiently large integer.

We prove that the covering radius of the Melas code$M(m,q)$of length$n=q^{m}-1$over$\mathbb {F}_{q}$is 2 if$q > 3$. We also prove that the covering radius of$M(m,3)$is 3 is$m \ge 3$, the covering radius of$M(2,3)$is 4, and the covering radii of$M(1,2)$and$M(1,3)$are 1.

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$.

Sequences and their correlation properties have been extensively studied due to their broad applications. In this paper, we develop a connection between sequences and well-studied combinatorial objects, circular Florentine arrays. This connection allows us to derive two types of sequences with good correlation properties. The first type consists of sequences having optimal correlation with respect to the Sarwate bound. Our constructions are based on perfect polyphase sequences. The number of perfect sequences with optimal correlation depends on the existence of circular Florentine arrays, which improves the previous known results. The second type is about multiple ZCZ sequence sets with low inter-set cross-correlation. Each generated ZCZ sequence set is optimal with respect to the Tang-Fan-Matsufuji bound, and each sequence in each set is perfect. In addition, any two sequences from distinct ZCZ sequence sets possess optimal inter-set cross-correlation with respect to the Sarwate bound. Compared with the previous results, the number of ZCZ sequence sets with optimal inter-set cross-correlation property is improved, because of the existence of circular Florentine arrays.

It is well-known that cyclic codes have efficient encoding and decoding algorithms. In recent years, antiprimitive BCH codes have attracted a lot of attention. The objective of this paper is to study BCH codes of this type over finite fields and analyse their parameters. Some lower bounds on the minimum distance of antiprimitive BCH codes are given. The BCH codes presented in this paper have good parameters in general, containing many optimal linear codes. In particular, two open problems about the minimum distance of BCH codes of this type are partially solved in this paper.

A new method is used to resolve a long-standing conjecture of Niho concerning the crosscorrelation spectrum of a pair of maximum length linear recursive sequences of length 22m-1 with relative decimation d=2m+2-3, where m is even. The result indicates that there are at most five distinct crosscorrelation values. Equivalently, the result indicates that there are at most five distinct values in the Walsh spectrum of the power permutation f(x)=xdover a finite field of order 22mand at most five distinct nonzero weights in the cyclic code of length 22m-1 with two primitive nonzeros α and αd. The method used to obtain this result proves constraints on the number of roots that certain seventh degree polynomials can have on the unit circle of a finite field. The method also works when m is odd, in which case the associated crosscorrelation and Walsh spectra have at most six distinct values.

In this paper, we apply two-to-one functions over b F2nin two generic constructions of binary linear codes. We consider two-to-one functions in two forms: (1) generalized quadratic functions; and (2) (x2t+x)ewith gcd(t, n)=gcd(e, 2n-1)=1. Based on the study of the Walsh transforms of those functions or their variants, we present many classes of linear codes with few nonzero weights, including one weight, three weights, four weights, and five weights. The weight distributions of the proposed codes with one weight and with three weights are determined. In addition, we discuss the minimum distance of the dual of the constructed codes and show that some of them achieve the sphere packing bound. Moreover, examples show that some codes in this paper have best-known parameters.

In this paper, by the Hasse-Weil bound, we determine the necessary and sufficient condition on coefficients$a_{1},a_{2},a_{3}\in {\mathbb F} _{2^{n}}$with$n=2m$such that$f(x) = {x}^{3\cdot 2^{m}} + a_{1}x^{2^{m+1}+1} + a_{2} x^{2^{m}+2} + a_{3}x^{3}$is an APN function over${\mathbb F}_{2^{n}}$. Our work together with the follow-up work by Chase and Lisoněk indicates that all such APN quadrinomials$f(x)$are affine equivalent to two instances of Gold functions, which resolves the first half of an open problem by Carlet at the International Workshop on the Arithmetic of Finite Fields, 83-107, 2014.

Quasi-complementary sequence sets (QCSSs) play an important role in multi-carrier code-division multiple-access (MC-CDMA) systems. They can support more users than perfect complementary sequence sets in MC-CDMA systems. It is desirable to design QCSSs with good parameters that are a trade-off of large set size, small periodic maximum magnitude correlation and small alphabet size. The main results are to construct new infinite families of QCSSs that all have small alphabet size and asymptotically optimal periodic maximum magnitude correlation. In this paper, we propose three new constructions of QCSSs using additive characters over finite fields. Notably, these QCSSs have new parameters and small alphabet sizes. Using the properties of characters and character sums, we determine their maximum periodic correlation magnitudes and prove that these QCSSs are asymptotically optimal with respect to the lower bound.

Families of periodic sequences with some desirable auto-correlation and cross-correlation properties have applications in communications and radar systems for identification, synchronization, ranging, or interference mitigation. A sequence is said to be a polyphase sequence if all the coordinates are n-th roots of unity. In this paper, we develop a connection between generalised Frank sequences and well-studied combinatorial objects: circular Florentine arrays. From this connection, we can derive an optimal set of perfect polyphase sequences with respect to the Sarvate bound. Furthermore, the size of the optimal set is determined by the existence of circular Florentine arrays. As a result, the size of an optimal set of perfect sequences is increased, compared with the previous results, where the size depends on the smallest prime divisor of the period.

We investigate the differential properties of a vectorial Boolean function G obtained by modifying an APN function F . This generalizes previous constructions where a function is modified at a few points. We characterize the APN-ness of G via the derivatives of F, and deduce an algorithm for searching for APN functions whose values differ from those of F only on a given set U ⊆ F2n. We introduce a value ΠFassociated with any F, which is invariant under CCZ-equivalence. We express a lower bound on the distance between a given APN function F and the closest APN function in terms of ΠF. We show how ΠFcan be computed efficiently for F quadratic. We compute ΠFfor all known APN functions over F2n. up to n ≤ 8. his is the first new CCZ-invariant for APN functions to be introduced within the last ten years. We derive a mathematical formula for this lower bound for the Gold function F (x) = x3, and observe that it tends to infinity with n. Finally, we describe how to efficiently find all sets U such that, taking G(x) = F (x) + v for x ∈ U and G(x) = F (x) for x ∉ U,G(x) is APN.

The binomial B(x) = x3+βx36(where β is primitive in F22) over F210 is the first known example of an Almost Perfect Nonlinear (APN) function that is not CCZ-equivalent to a power function, and has remained unclassified into any infinite family of APN functions since its discovery in 2006. We generalize this binomial to an infinite family of APN quadrinomials of the form x3+a(x2i+1)2k+bx3·2m+c(x2i+m+2m)2kfrom which B(x) can be obtained by setting a = β, b = c = 0, i = 3, k = 2. We show that for any dimension n = 2m with m odd and 3 + m,setting(a, b, c)=(β, β2, 1) and i =m -2 or i = (m - 2)-1mod n yields an APN function, and verify that for n = 10 the quadrinomials obtained in this way for i = m - 2 and i = (m - 2)-1mod n are CCZ-inequivalent to each other, to B(x), and to any other known APN function over F210.

Functions with low differential uniformity have important applications in cryptography, coding theory, and sequence design. The differential spectrum of a cryptographic function is of great interest for estimating its resistance to some variants of differential cryptanalysis. Finding power permutations (i.e., monomial bijective mappings) over finite fields with low differential uniformity and determining their differential spectra have received a lot of attention over the past two decades. The objective of this paper is to study the differential properties of the well-known Kasami power permutations x p2k-pk+1 over GF(pn), where p is an odd prime and k is an integer with gcd(n, k) = 1. It turns out that this family of monomials is differentially (p + 1)-uniform. Our result in the case of p = 3 gives an affirmative solution to a recent conjecture by Xu, Cao, and Xu. Most notably, the differential spectrum of this family of power permutations is completely determined.

We study the problem of existence of APN functions of algebraic degree n over F2n. We characterize such functions by means of derivatives and power moments of the Walsh transform. We deduce several non-existence results which imply, in particular, that for most of the known APN functions F over F2n. the function x2n-1+ F(x) is not APN, and changing a value of F in a single point then results in non-APN functions. This leads us to conjectures that an APN function modified in one point cannot remain APN and that there exists no APN function of algebraic degree n.

In this paper, we present some fundamental concepts and theoretical advances attributable to Solomon Golomb, together with the history and applications of this paper to communications, coding, and cryptography, along with some long-standing conjectures. Examples include the first engineering problem relating to feedback shift-register sequences that Sol Golomb was asked to solve in the mid-1950s. This paper covers m-sequences and Golomb's three randomness postulates, the cross-correlation of m-sequences, the exp-Golomb code, the Golomb ruler, Costas arrays, Golomb invariants, polyominoes, the distribution of prime numbers, and irreducible polynomials.

Sequences with low correlation have important applications in communications, radar, and cryptography. In this paper, a simple construction of polyphase sequences using additive and multiplicative characters over the finite field Fqis proposed. The construction works for any finite field Fqwith q > 2 and generates a family of q - 1 sequences with period q - 1 and maximum correlation √q. This family is asymptotically optimal with respect to the well-known Welch bound. Most notably, the maximum autocorrelation magnitude of each sequence in this family is equal to 1, and every two distinct sequences are orthogonal to each other. The distribution of the correlation magnitudes of this family is also established.

Zero correlation zone (ZCZ) sequences are a class of spreading sequences having ideal auto-correlation and cross correlation in a zone around the origin. They have been extensively studied in recent years due to their important applications in quasi-synchronous code division multiple access systems. In this paper, a construction of ZCZ sequence sets is proposed based on perfect nonlinear functions. It generates multiple ZCZ sequence sets with the properties: 1) each sequence is perfect in the sense that its out-of-phase auto-correlation is always zero; 2) each ZCZ sequence set is optimal with respect to the Tang-Fan-Matsufuji bound in which all the sequences are pairwise cyclically distinct; and 3) the maximum inter-set cross correlation of multiple sequence sets achieves the well-known Sarwate bound.

The nonlinear complexity of a periodic sequence s is the length of the shortest feedback shift register that can generate s, and its value is upper bounded by the least period of s minus 1. In this paper, a recursive approach that generates all periodic sequences with maximum nonlinear complexity is presented, and the total number of such sequences is determined. The randomness properties of these sequences are also examined.

As a class of optimal combinatorial objects, bent functions have important applications in cryptography, sequence design, and coding theory. Bent idempotents are a subclass of bent functions and of great interest, since they can be stored in less space and allow faster computation of the Walsh-Hadamard transform. The objective of this paper is to present a generic construction of bent functions from known ones. It includes the previous constructions of bent functions by Mesnager and Xu et al. as special cases, and produces new bent functions, which cannot be produced by earlier ones. In particular, it also generates infinite families of bent idempotents over F22mof any algebraic degree between 2 and m. This together with a recent construction by Su and Tang gives a positive answer to an open problem on bent idempotents proposed by Carlet. In addition, an infinite family of anti-self-dual bent functions is obtained in which the sum of any three distinct functions is again an anti-self-dual bent function in this family. This solves an open problem recently proposed by Mesnager.

Let p be a prime, n = 2m and d = 3pm- 2 with m ≥ 2, and gcd(d, pn- 1) = 1. In this paper, the correlation distribution between a p-ary m-sequence of period pn- 1 and its d-decimation sequence is investigated in a unified approach. Some results for the binary case are extended to the general case. It is shown that the problem of determining the correlation distribution for d can be reduced to that of solving two combinatorial problems related to the unit circle of the finite field Fpn. For an arbitrary odd prime p, it seems difficult to solve these two problems. However, for p = 3, by studying the weight distribution of the ternary Zetterberg code and counting the numbers of solutions of some equations over F3n, the two problems are solved, and thus, the corresponding correlation distribution for d is completely determined. It is noteworthy that this is the first time that the correlation distribution for a non-binary Niho decimation has been determined since 1976.

We study the problem of existence of APN functions of algebraic degree n over F2n. We characterize such functions by means of derivatives and power moments of the Walsh transform. We deduce some non-existence results which mean, in particular, that for most of the known APN functions F over F2nthe function x2n-1+ F(x) is not APN, and changing a value of F in a single point results in non-APN functions.

The ternary function f(x) mapping F34kto F3and given by f(x) = Tr4k(a1x2(3k+1)+ a2x(3k+1)2), where a1is a nonsquare in F34kand a2is defined explicitly by a1, is proven to be a regular bent function of degree four belonging to the completed Maiorana-McFarland class. The proof is based on a new criterion that allows checking bentness by analyzing first- and second-order derivatives.

In this paper, we discover that univariate form of a Niho bent function is a sum of functions having the form of a Leander-Kholosha bent function taken with particular coefficients from F*(2n) for every term. We know that the Niho bent functions are related to o-polynomials. The power terms in the univariate Niho bent function can be derived by working, in a first step, on each monomial of the corresponding o-polynomial separately, and in a second step, adding them to obtain the global expression. This allows, knowing the monomials in an o-polynomial, to obtain the power terms of the polynomial representing corresponding bent function. However, the coefficients are not calculated explicitly. The explicit form is given for the bent functions obtained from quadratic and cubic o-polynomials. We also calculate the algebraic degree of any bent function in the Leander-Kholosha class.

In this paper, a family of new de Bruijn sequences is proposed through the construction of maximum-length nonlinear feedback shift registers (NFSRs). Let$k$be a positive integer and$p_{0}(x), p_{1}(x), \ldots , p_{k}(x)$be the primitive polynomials in$\mathbb {F}_{2}[x]$with their degrees strictly increasing and pairwise coprime. We determine the cycle structure and adjacency graphs of linear feedback shift registers (LFSRs) with characteristic polynomial$q(x)=\prod \nolimits _{i=0}^{k}p_{i}(x)$. In the case that$p_{0}(x)=1+x$, an algorithm is proposed to produce maximum-length NFSRs from these LFSRs, and it is shown that the algorithm can generate$O(2^{(2^{k}-1)n})~n$-stage maximum-length NFSRs with memory complexity$O(2^{k}kn)$and time complexity$O(2^{n-d_{k}}kn)$, where$n$and$d_{k}$are the degrees of$q(x)$and$p_{k}(x)$, respectively. Finally, we illustrate the proposed algorithm in the case of$k=2$. In this case, we prove that for any integer$n\geq 8$, the algorithm can produce$n$-stage maximum-length NFSRs with time complexity as low as$O(n^{{\rm {log}{log}}(n)}$).

Linear codes with a few weights have applications in consumer electronics, communication, data storage system, secret sharing, authentication codes, association schemes, and strongly regular graphs. This paper first generalizes the method of constructing two-weight and three-weight linear codes of Ding et al. and Zhou et al. to general weakly regular bent functions and determines the weight distributions of these linear codes. It solves an open problem proposed by Ding et al. Furthermore, this paper constructs new linear codes with two or three weights and presents their weight distributions. They contain some optimal codes meeting certain bound on linear codes.

In this paper, let n = 2k and d = 3 · 2k- 2 with k ≥ 3 and gcd(d, 2n- 1) = 1. Based on some analysis of certain equations over finite fields and the number of codewords with Hamming weight five in Zetterberg code, the correlation distribution between a binary m-sequence of period 2n- 1 and its d-decimation sequence is completely determined. This solves a ten-year-old open problem proposed by Dobbertin et al.

In this paper, we extend the class of Niho bent function consisting of 2rterms discovered by Leander and Kholosha. The extension is achieved by inserting coefficients of the power terms in the original function. Doing this, we obtain relation to all the existing quadratic o-monomials. We also calculate the algebraic degree of any function in the extended class.

In 1998, Lin presented a conjecture on a class of ternary sequences with ideal 2-level autocorrelation. Those sequences have a very simple structure, i.e., their trace representation has two trace monomial terms. In this paper, we present a proof for this conjecture. The mathematical tools employed are the second-order multiplexing decimation-Hadamard transform, Stickelberger's theorem, the Teichmüller character, and combinatorial techniques for enumerating the Hamming weights of ternary numbers. As a by-product, we also prove that the Lin conjectured ternary sequences are Hadamard equivalent to ternary m-sequences.

In this paper, a new class of (N, K) near-optimal partial Hadamard codebooks is proposed. The construction of the proposed codebooks from Hadamard matrices is based on binary row selection sequences, which are generated by quadratic have parameters N = pnand K = (p - 1/2 p)(N + √N) + 1 for an odd prime p and an even positive integer n. We prove that the maximum magnitude of inner products between the code vectors of the proposed codebooks asymptotically achieves the Welch bound equality for sufficiently large p and derive their inner product distribution.

In 1998, Lin presented a conjecture on a class of ternary sequences with ideal two-level autocorrelation. Those sequences have a very simple structure, i.e., their trace representation has two trace monomial terms. In this paper, we present a proof for the conjecture. The mathematical tools employed are the second-order multiplexing decimation-Hadamard transform, Stickelberger's theorem, the Teichmüller character, and combinatorial techniques for enumerating the Hamming weights of ternary numbers. As a by-product, we also prove that the ternary sequences conjectured by Lin are Hadamard equivalent to ternary m-sequences.

Let m ≥ 3 be an odd integer and p be an odd prime. In this paper, a number of classes of three-weight cyclic codes C(1,e) over Fp, which have parity-check polynomial m1(x)me(x), are presented by examining general conditions on the parameters p, m, and e, where mi(x) is the minimal polynomial of π-i over Fp for a primitive element π of Fpm. Furthermore, for p ≡ 3 (mod 4) and a positive integer e satisfying (pk+ 1) · e ≡ 2 (mod pm - 1) for some positive integer k with gcd(m, k) = 1, the value distributions of the exponential sums T(a, b) = Σx∈FpmωTr(ax+bxe)and S(a, b, c) = Σx∈FpmωTr(ax+bxe+cxs), where s = (pm- 1)/2, are determined. As an application, the value distribution of S(a, b, c) is utilized to derive the weight distribution of the cyclic codes C(1,e,s)with parity-check polynomial m1(x)me(x)ms(x). In the case of p = 3 and even e satisfying the above condition, the dual of the cyclic code C(1,e,s)has optimal minimum distance.

New quadratic bent functions in polynomial form are constructed in this paper. The constructions give new Boolean bent, generalized Boolean bent and p-ary bent functions. Based on Z4-valued quadratic forms, a simple method provides several new constructions of generalized Boolean bent functions. From these generalized Boolean bent functions a method is presented to transform them into Boolean bent and semi-bent functions. Moreover, many new p-ary bent functions can also be obtained by applying similar methods.

In this paper, the cycle structure and adjacency graphs of a class of linear feedback shift registers (LFSRs) are determined. By recursively applying the D-morphism to the maximum-length LFSRs and representing the cycles by generating functions, a new family of maximum-length nonlinear feedback shift registers (NFSRs) are proposed based on the properties of these LFSRs. The number of NFSRs in the proposed family is also considered.

In this paper, a class of linear feedback shift registers (LFSRs) with characteristic polynomial (1 + x3)p(x) is discussed, where p(x) is a primitive polynomial of degree n > 2. The cycle structure and adjacency graphs of the LFSRs are determined. A new class of de Bruijn sequences is constructed from these LFSRs, and the number of de Bruijn sequences in the class is also considered. To illustrate the efficiency of constructing de Bruijn sequences from these LFSRs, an algorithm for producing some corresponding maximum-length nonlinear feedback shift registers with time and memory complexity O(n) is also proposed.

For an odd prime p and two positive integers m, k such that m/gcd (k,m) ≥ 3 is odd, let d be a positive integer satisfying d(pk+1)=2(mod pm-1). In this paper, the cross-correlation between a p-ary m-sequence and its d-decimated sequences is investigated, and the cross correlation distribution is completely determined. The relationship between the decimations d considered in this paper and some known ones is also studied. This paper generalizes some previous results, and also gives new decimations, which lead to low cross correlation.

In this paper, a new construction of zero-difference balanced functions defined on is given, where is an odd positive integer. Based on the generic constructions proposed by Ding, optimal constant composition codes and perfect difference systems of sets with new parameters can be generated from the zero-difference balanced functions constructed in this paper.

Cyclic codes are a subclass of linear codes and have applications in consumer electronics, data storage systems, and communication systems as they have efficient encoding and decoding algorithms. Perfect nonlinear monomials were employed to construct optimal ternary cyclic codes with parameters [3m-1, 3m-1-2m, 4] by Carlet, Ding, and Yuan in 2005. In this paper, almost perfect nonlinear monomials, and a number of other monomials over GF(3m) are used to construct optimal ternary cyclic codes with the same parameters. Nine open problems on such codes are also presented.

In this paper, a class of functions from Niho exponents with four-valued Walsh transform is obtained for any prime by a uniform method, and the distribution of the Walsh transform values is also completely determined. In particular, this class of functions is proven to be bent for a special case. Although it is shown that the obtained bent functions are equivalent to the Leander-Kholosha's class of bent functions, a direct and much simpler proof for the bentness of this kind of Niho functions is provided.

Several new classes of binary andp-ary regular bent functions are obtained in this paper. The bentness of all these functions is determined by some exponential sums over finite fields, most of which have close relations with the well-known Kloosterman sums.

In this paper, most of the known infinite classes of generalized bent functions are analyzed for their relation to the completed Maiorana-McFarland class. This is done using the criterion based on second-order derivatives of a function. In particular, it is shown that, unlike in the binary case, not all quadratic bent functions are EA-equivalent to a function of the Maiorana-McFarland type. This is the first attempt to rise this problem for the generalized bent functions.

In this paper, for an odd prime p and positive integers n, m and e, we present two families of p-ary sequences from decimated Helleseth-Gong sequences and m-sequences and examine their correlation properties. The proposed families of sequences possess low correlation and large linear complexity properties.

New quadratic bent functions in polynomial forms are constructed in this paper. The constructions give new boolean bent and generalized boolean bent functions. Based on Z4-valued quadratic forms, a simple method provides several new constructions of generalized boolean bent functions. From these generalized boolean bent functions a method is presented to transform them into binary bent and semi-bent functions.

Let m be odd and q = 22m. Let 5r ≡ 1 (mod 2m+ 1) and d = (2m- 1)r + 1. In this paper, the cross correlation distributions of an m-sequences with period q - 1 and its decimated sequences s(dt + l) with period (q - 1)/3 for 0 ≤ l ≤ 2 are determined. These cross correlations are shown to be four-valued with maximal magnitude 2√q - 1.

This paper consists of two main contributions. First, the Niho bent function consisting of 2rexponents (discovered by Leander and Kholosha) is studied. The dual of the function is found and it is shown that this new bent function is not of the Niho type. Second, all known univariate representations of Niho bent functions are analyzed for their relation to the completed Maiorana-McFarland classM. In particular, it is proven that two families do not belong to the completed classM. The latter result gives a positive answer to an open problem whether the classHof bent functions introduced by Dillon in his thesis of 1974 differs from the completed classM.

The Walsh transform of two-level autocorrelation sequences has played an important role in the construction of the set of sequences in which any two sequences are orthogonal. Forp-ary sequences, there are only two basic classes of two-level autocorrelation sequences with no subfield structures for an arbitrary odd primep. One is the class ofp-arym-sequences and the other is the class ofp-ary Helleseth-Gong sequences. In this paper, the Walsh transform of a subclass ofp-ary Helleseth-Gong sequences and the Walsh transform of their particular decimations are completely determined and are shown to be three-valued.

In 2006, Helleseth and Kholosha conjectured and partially proved the existence of a class of ternary weakly regular monomial bent functions and also the expression for the dual bent function up to the sign value. The bentness was finally proved later in 2009 using a complicated technique that employs Stickelberger's theorem. Extensively using the previously found results and approaches, in this paper, a surprisingly short proof for the conjectured expression of the dual is given but without resolving the sign ambiguity. Furthermore, we resolve the sign by finding the trace representation of the dual function.

This paper studies a class of binomial functions over the finite fields of odd characteristic and characterizes their bentness in terms of the Kloosterman sums. Numerical results show that the proposed class contains bent functions that are affinely inequivalent to all known monomial and binomial ones.

Computed is the dual of the Niho bent function consisting of 2rexponents that was found by Leander and Kholosha. The algebraic degree of the dual is calculated and it is shown that this new bent function is not of the Niho type. This note is a follow-up of the recent paper by Carlet and Mesnager.

In 1998, the second author, Charpin and Zinoviev characterized APN and AB (n, n)-functions by means of associated 2n-variable Boolean functions. In particular, they proved that a function F is AB if and only if the associated Boolean function γFis bent. This observation leads to potentially new bent functions associated to the known AB functions, or at least gives new insight on known bent functions. However, up to now, representations of γFare known only for Gold AB power functions and determining γFfor the rest of AB functions is an open problem. In the present paper we determine γFfor most of the known families of APN and AB functions.

In this paper, some new results are presented on the selective discrete Fourier spectra attack introduced first as the Rønjom-Helleseth attack and the modifications due to Rønjom, Gong, and Helleseth. The first part of this paper fills some gaps in the theory of analysis in terms of the discrete Fourier transform (DFT). The second part introduces the new fast selective DFT attacks, which are closely related to the fast algebraic attacks in the literature. However, in contrast to the classical view that successful algebraic cryptanalysis of LFSR-based stream cipher depends on the degree of certain annihilators, the analysis in terms of the DFT spectral properties of the sequences generated by these functions is far more refined. It is shown that the selective DFT attack is more efficient than known methods for the case when the number of observed consecutive bits of a filter generator is less than the linear complexity of the sequence. Thus, by utilizing the natural representation imposed by the underlying LFSRs, in certain cases, the analysis in terms of DFT spectra is more efficient and has more flexibility than classical and fast algebraic attacks. Consequently, the new attack imposes a new criterion for the design of cryptographic strong Boolean functions, which is defined as the spectral immunity of a sequence or a Boolean function.

Let$m$and$k$be positive integers with$m/{\rm gcd}(m,k)$being odd, for$a\in \BBR$and$b\in \BBL$, the exponential sum$\sum_{x\in \BBL}i^{Tr(ax+2bx^{2^{k}+1})}$is studied systematically in this paper, where$i=\sqrt {-1}$,$\BBR =\BBG \BBR (4,m)$is a Galois ring,$\BBL$is the Teichmüller set of$\BBR$and$Tr(\cdot)$is the trace function from the Galois ring$\BBR$to$\BBZ_{4}$. Through the discussions on the solutions of certain equations and the newly developed theory of$\BBZ_{4}$-valued quadratic forms, the distribution of the exponential sum is completely determined. As its applications, we can determine the Lee weight and Hamming weight distributions of a class of codes${\cal C}^{k}$over$\BBZ_{4}$and the correlation distribution of a quaternary sequence family${\cal U}^{k}$, respectively. Furthermore, the Hamming weight distributions of the binary codes obtained from${\cal C}^{k}$under the most significant bit (MSB) and Gray maps are also determined. For the MSB map sequences of${\cal U}^{k}$, the nontrivial maximal correlation value is given and the correlation distribution is determined for the Gray map sequences of${\cal U}^{k}$. It should be noted that the distribution of the exponential sum for the case$\gcd (m,k)\ne 1$is obtained for the first time, and then the corresponding codes and sequences are novel.

Constant composition codes are codes where the frequency distribution of the elements in a codeword is the same for all codewords. In this paper, three classes of constant composition codes are constructed. These codes are subcodes of cyclic codes which have few weights occurring among the codewords. The new codes are excellent asymptotically compared to the previously best known constant composition codes.

In this paper, a simple but generic method is proposed for transforming any family of quaternary sequences, with low correlation, of any odd periodNto another family of quaternary sequences of period 2N with low correlation. As an application of the generic method to sequence Family A, a new optimal quaternary sequence family with length 2(2n-1), family size 2n+1 , and maximal nontrivial correlation value 2[(n+1)/2]+2, wherenis an odd integer, is obtained. Most notably, unlike all the known optimal quaternary sequence families, the new family has a unique property that the odd integers 1, 3 and the even integers 0, 2 are allocated alternatively in all the sequences.

The Alternating Step(r, s) Generator, ASG(r, s), is a clock-controlled sequence generator which is recently proposed by A. Kanso. It consists of three registers of length l, m and n bits. The first register controls the clocking of the two others. The two other registers are clocked r times (or not clocked) (resp. s times or not clocked) depending on the clock-control bit in the first register. The special case r = s = 1 is the original and well known Alternating Step Generator. Kanso claims there is no efficient attack against the ASG(r, s) since r and s are kept secret. In this paper, we present an Alternating Step Generator, ASG, model for the ASG(r, s) and also we present a new and efficient algebraic attack on ASG(r, s) using 3(m + n) bits of the output sequence to find the secret key with O((m2+n2)2l+1+m32m-1+n32n-1) computational complexity. We show that this system is no more secure than the original ASG, in contrast to the claim of the ASG(r, s)'s constructor.

The p-ary binomial function f(x) mapping GF(p4k) to GF(p) given by f(x) = Tr4k(xp3k+p2k-pk+1 + x2)equations is proven to be a weakly regular bent function and the exact value of its Walsh transform coefficients is found. This is the first proven infinite class of nonquadratic generalized bent functions over the fields of an arbitrary odd characteristic. The proof is based on a few new results in the area of exponential sums and polynomials over finite fields that may also be interesting as independent problems. Finally, we characterize the size of a cyclotomic coset containing the exponent of a monomial bent functions (the same result holds in a binomial case) and provide numerical data.

Thep-ary functionf(x) mappingGF(p4k) toGF(p) and given byf(x)=Tr4k(xp3k+p2k-pk+1+x2) is proven to be a weakly regular bent function and the exact value of its Walsh transform coefficients is found. This is the first proven infinite class of nonquadratic generalized bent functions over the fields of an arbitrary odd characteristic. The proof is based on a few new results in the area of exponential sums and polynomials over finite fields that may also be interesting as independent problems.

The binary primitive triple-error-correcting BCH code is a cyclic code of minimum distance d = 7 with generator polynomial having zeros alpha, alpha3and alpha5where alpha is a primitive (2n- 1)-root of unity. The zero set of the code is said to be {1, 3, 5}. In the 1970's Kasami showed that one can construct similar triple-error-correcting codes using zero sets consisting of different triples than the BCH codes. Furthermore, in 2000 Chang et. al. found new triples leading to triple-error-correcting codes. In this paper a new such triple is presented. In addition a new method is presented that may be of interest in finding further such triples. The method is illustrated by giving a new and simpler proof of one of the known Kasami triples {1, 2k+ 1, 23k+ 1} where n is odd and gcd(k, n) = 1 as well as to find the new triple given by {1, 2k+ 1, 22k+ 1} for any n where gcd(k, n) = 1.

In this paper, we study ternary monomial functions of the formf(x) = Trn(axd), wherexisin \BBF3nandTrn: \BBF3nrarr \BBF3is the absolute trace function. Using a lemma of Hou, Stickelberger's theorem on Gauss sums, and certain ternary weight inequalities, we show that certain ternary monomial functions arising in the 2006IEEE Transactions on Information Theorypaper (vol. 52, pp. 2018-2032, 2006) are weakly regular bent, thus settling a conjecture of Helleseth and Kholosha. We also prove that the Coulter-Matthews bent functions are weakly regular.

This paper follows the recent work of Helleseth, Kholosha, Johansen, and Ness to study the cross correlation between an m -sequence of period 2m- 1 and the d-decimation of an m-sequence of a shorter period 2n- 1 for an even number m = 2n. Assuming that d satisfies d(2l+ 1) = 2i(mod 2n- 1) for some l > 0 and i > 0, it is proved that the cross correlation takes on either exactly three or four values depending on whether I and n are coprime or not. The distribution of the cross-correlation values is also completely determined. Our results theoretically confirm the numerical data by Ness and Helleseth. It is conjectured that there are no other decimations that give at most four-valued cross correlation apart from the ones proved here.

Finding the cross correlation between two m-sequences {st} and {sdt} of the same period 2m-1 , that differ by a decimation d, has been a popular research problem since the 1960s. Many cases with three- and four-valued correlation have been determined. Several values of d are known to lead to five-valued cross correlation but their exact correlation distribution has been open. The correlation distribution is completely determined for one of these families with five-valued cross correlation by using evaluations of certain exponential sums including Kloosterman sums. The decimation considered is the special decimation d = 22k+1/2k+1where m is odd and k=1, i.e., d=5/3 . The paper introduces some techniques that may be useful to obtain further results on related decimations.

Recently, the complete five-valued cross-correlation distribution has been determined between twom-sequences{st} and{sdt} of periods2m-1 that differ by the decimationd= [(22k+1)/(2k+1)] wheremis odd andk= 1, i.e.,d= 5/3 . In this paper, the correlation distribution is given in terms of some exponential sums for anykwhengcd(k,m) = 1 andmis odd. Furthermore, two new conjectures on exponential sums are presented that are of interest in their own right. Proving these conjectures would imply that the correlation distribution is independent ofkunder the conditions above and thus the same as for the casek= 1. The conjectures are proven formodd andk= 2 and the paper gives a new result that the correlation distribution ford=17/5 is the same as ford= 5/3.

In this paper, we present two optimal binary families of sequences of length 2n-1 and 2(2n-1) for odd integer n. They are obtained as the images of proposed optimal quaternary sequences under the most significant bit and the Gray maps. The first family has 2n+1 sequences of length 2n-1 and the identical correlation distribution to that of Gold sequences and Gold-like sequences, and the second family of sequences of length 2(2n-1) has 2nsequences and the same correlation values as those of Kerdock sequences.

Let K(a) be the so-called classical Kloosterman sums over F2m, where m is even. In this paper, we compute K(a) modulo 24, completing our previous results for odd m. We extensively study the links between K(a) and other exponential sums, in particular with the cubic sums. We point out (as we did for odd m) that the values K(a) are related with cosets of weight 4 of primitive narrow sense extended BCH codes of length n = 2mand minimum distance 8.

Considered is the distribution of the cross correlation between m-sequences of length 2m-1, where m is even, and m-sequences of shorter length 2m/2-1. The infinite family of pairs of m-sequences with four-valued cross correlation is constructed and the complete correlation distribution of this family is determined.

We give exact expressions for the number of coset leaders in the cosets of weight 4 of binary primitive narrow sense Bose–Chaudury–Hocquenghem (BCH) codes of length $n=2^m$ (m even) with minimum distance 8 in terms of several exponential sums, including cubic sums and Kloosterman sums. This allows us to bound the number of coset leaders in these cosets.

Family A is a family of sequences of period 2n- 1 over Zi, the ring of integers modulo 4. This family has optimal correlation properties and its correlation distribution is well known. Two related families of quaternary sequences are the families B and C. These are families of sequences over Z4of period 2(2n- 1). In recent years, new families of quaternary sequences of period 2(2n- 1) have been constructed by modifying the sequence families B and C in a nonlinear way. This has resulted in a new family D of sequences of period 2(2n- 1) which has optimal correlation properties, but until now the correlation distribution of this family has not been known. In this paper, we completely determine the correlation distribution of family D by making use of properties of exponential sums.

The exact expressions for the number of codewords of weight 4 in the cosets of weight 4 of binary primitive BCH codes of length n = 2m(m even) with minimum distance 8 is given in terms of several exponential sums, including cubic sums and Kloosterman sums. This provides a bound on the number of codewords of weight 4 in the cosets of weight 4 and also some limitations for possible values of Kloosterman sums over GF(2m), (m even).

In this paper, a coding-theory construction of Cartesian authentication codes is presented. The construction is a generalization of some known constructions. Within the framework of this generic construction, several classes of authentication codes using certain classes of error-correcting codes are described. The authentication codes presented in this paper are better than known ones with comparable parameters. It is demonstrated that the construction is related to certain combinatorial designs, such as difference matrices and generalized Hadamard matrices

Considered is the distribution of the cross correlation between in-sequences of length 22k-1, where m = 2k, and m-sequences of shorter length 2k-1. New pairs of m -sequences with three-valued cross correlation are found and the complete correlation distribution is determined. Finally, we conjecture that there are no more cases with a three-valued cross correlation apart from the ones proven here.

A mapping f(x) from GF(pn) to GF(pn) is differentially k-uniform if k is the maximum number of solutions x isin GF(pn) of f(x+a) - f(x) = b, where a, b isin GF(pn) and a ne 0. A 2-uniform mapping is called almost perfect nonlinear (APN). This correspondence describes new families of ternary APN mappings over GF(3n), n>3 odd, of the form f(x) = uxd+ xd2where d1= (3n-1)/2 - 1 and d2= 3n- 2.

The cross-correlation function between m-sequences of period 2m- 1, where m = 6k, and m-sequences of shorter period 2m/2- 1 is investigated. The first infinite family of pairs of m-sequences with four-valued cross correlation is constructed and the complete correlation distribution of this family is determined.

The filter generator is an important building block in many stream ciphers. The generator consists of a linear feedback shift register of length n that generates an m-sequence of period 2n-1 filtered through a Boolean function of degree d that combines bits from the shift register and creates an output bit ztat any time t. The previous best attacks aimed at reconstructing the initial state from an observed keystream, have essentially reduced the problem to solving a nonlinear system of D=Sigmai=1d(n/i) equations in n unknowns using techniques based on linear algebra. This attack needs about D bits of keystream and the system can be solved in complexity O(Domega), where omega can be taken to be Strassen's reduction exponent omega=log2(7)ap2.807. This paper describes a new algorithm that recovers the initial state of most filter generators after observing O(D) keystream bits with complexity O((D-n)/2)apO(D), after a pre-computation with complexity O(D(log2D)3)

A new upper bound on the cardinality of codes in the Hamming space with given minimum and maximum distances is proved. The bound is compared to some known bounds, and some classes of codes for which the new bound is tight are given

The crosscorrelation function between m-sequences of period 2m- 1, where m = 2k, and m-sequences of shorter period 2k- 1 is considered. A new pair of m-sequences with three-valued crosscorrelation is found and the complete correlation distribution is determined

For any integer q we present a new bound which is a q-ary combinatorial analog of the binary Grey-Rankin bound. For any prime power q we present two infinite classes of q-ary codes which meet this bound with integral equality. Moreover, we show how codes meeting this bound with equality are connected to several important classical combinatorial configurations, such as difference matrices and generalized Hadamard matrices.

Binary primitive triple-error-correcting Bose-Chaudhuri-Hocquenghem (BCH) codes of length n=2/sup m/-1 have been the object of intensive studies for several decades. In the 1970s, their covering radius was determined in a series of papers to be /spl rho/=5. However, one problem for these codes that has been open up to now is to find their coset distribution. In this paper this problem is solved and the number of cosets of each weight in any binary primitive triple-error-correcting BCH code is determined. As a consequence this also gives the coset distribution of the extended codes of length N=2/sup m/ with minimum distance 8.

Suppose that n=2k is even. We study the cross-correlation function between two m-sequences for Niho type decimations d=(2/sup k/-1)s+1. We develop a new technique to study the value distribution of these cross-correlation functions, which makes use of Dickson polynomials. As a first application, we derive here the distribution of the six-valued cross-correlation function for s=3 and odd k, up to a term which depends on Kloosterman sums. In addition, applying simpler methods, we prove a theorem providing Niho type decimations with four-valued cross-correlation functions and their distribution. We conjecture that the latter result actually covers all such decimations.

Considered are p-ary bent functions having the form f(x)=Tr/sub n/(/spl sigma//sub i=0//sup s/a/sub i/x/sup di/). A new class of ternary monomial regular bent function with the Dillon exponent is discovered. The existence of Dillon bent functions in the general case is an open problem of deciding whether a certain Kloosterman sum can take on the value -1. Also described is the general Gold-like form of a bent function that covers all the previously known monomial quadratic cases. The (weak) regularity of the new as well as of known monomial bent functions is discussed and the first example of a not weakly regular bent function is given. Finally, some criteria for an arbitrary quadratic function to be bent are proven.

Linear equations have always been powerful tools in cryptanalysis. In this correspondence, we present a general linear equation of minimum weight 3 in F2that holds for all state lengths n and all shifts i of sequences generated by the T-function xi=xi-12orC+xi-1mod 2nproposed by Klimov and Shamir. It is surprising that these linear properties exist, and they indicate that the sequences generated by the T-functions have more structures than claimed by Klimov and Shamir

We consider the distribution of the cross correlation between m-sequences of period 2/sup m/-1, where m=2k and m-sequences of shorter period 2/sup k/-1. We present some general properties of the cross correlation between these m-sequences and we find some decimations with 3-valued cross correlation. We further present some numerical results and open problems.

The distribution of the cross correlation between m-sequences of period 2m-1, where m=2k, and m-sequences of shorter period 2k-1 is considered. A new pair of m-sequences with three-valued cross correlation is found and the complete correlation distribution is determined

The distribution of the cross correlation between the ternary m-sequence {s/sub t/} of period n=3/sup m/-1 and the decimated sequences {s/sub dt/} and {s/sub dt+1/} of period (3/sup m/-1)/2, where d=3/sup k/+1/2 with k odd and gcd(k,m)=1 is determined. The method to find this distribution is related to the result by Coulter and Matthews that f(x)=x/sup d/ is a planar function over GF(3/sup m/).

Binary primitive triple-error-correcting BCH codes have been the object of intensive studies for several decades. In the 1970s their covering radius were determined in a series of papers to be 5. However, one problem for these codes that has been open up to now is to find their coset distribution. In this paper we solve this problem and thus determine the number of cosets of each weight in binary primitive triple-error-correcting BCH codes. As a consequence this also gives the coset distribution of the extended codes with minimal distance 8

Linear equations have always been powerful tools in cryptanalysis. In this paper, we present a general linear equation in the binary alphabet of minimum weight 3 that holds for all state lengths and all shifts of sequences generated by the T-function proposed by Klimov and Shamir. It is surprising that these linear properties exist, and they indicate that the T-functions are not as 'wild' and non-algebraic as claimed by Klimov and Shamir. We also use the equation to propose a simple algebraic attack on cryptographic T-functions

We consider p-ary bent functions having the form f(x) = Tr/sub n/ (ax/sup d/). A new class of ternary monomial regular bent function with the Dillon exponent is discovered. The existence of Dillon bent functions in the general case is an open problem of deciding whether a certain Kloosterman sum can take on the value -1. Also described is the general Gold-like form of a bent function that covers all the previously known monomial quadratic cases. We also discuss the (weak) regularity of our new as well as of known monomial bent functions and give the first example of a not weakly regular bent function.

The monotone structure of correctable and uncorrectable errors given by the complete decoding for a binary linear code is investigated. New bounds on the error-correction capability of linear codes beyond half the minimum distance are presented, both for the best codes and for arbitrary codes under some restrictions on their parameters. It is proved that some known codes of low rate are as good as the best codes in an asymptotic sense.

For a prime power q, we show that a cyclic relative difference set with parameters (q/sup n/-1/q-1,q-1,q/sup n-1/,q/sup n-2/) can be constructed from a d-homogeneous function from F/sub q//sup n//spl bsol/{0} onto F/sub q/ with difference-balanced property, where F/sub q//sup n/ is the finite field with q/sup n/ elements. This construction method enables us to construct several new cyclic relative difference sets with parameters (p/sup n/-1/p/sup l/-1,p/sup l/-1,p/sup n-l/,p/sup n-2l/) from p-ary sequences of period p/sup n/-1 with ideal autocorrelation property introduced by Helleseth and Gong. Using a lifting idea, other new cyclic relative difference sets can be constructed from the Helleseth-Gong (HG) sequences. Also, the 3-ranks and the trace representation of the characteristic sequences of cyclic relative difference sets from a specific class of ternary HG sequences and ternary Lin sequences are derived.

We compute the second support weight distribution of the Kasami codes.

We consider the q-ary analog of the binary Grey-Rankin bound, recently suggested by Fu, Kloeve and Shen. For any prime power q/spl ges/2, we give an infinite family of codes which reach this bound with equality. If the outer and inner codes are chosen as linear, a linear resulting code is obtained by the concatenation construction.

Helleseth, Kim and No (2003) described the linear complexity over F/sub p/ of Sidel'nikov sequences of length p/sup m/ -1 for p = 3, 5 and 7. This result is generalized to all odd primes.

The probability of correct decoding on the binary-symmetric channel is studied. In particular, a class of codes with the same lengths and dimensions as the linear simplex codes, but with larger probability of correct decoding for all parameters p, 0 < p < 1/2, is given.

Helleseth, Kim, and No (2003) described the linear complexity over F/sub p/ of Sidel'nikov sequences of length p/sup m/-1 for p=3, 5, and 7. In this correspondence, the result is generalized to all odd primes.

Separating codes find applications in many fields including automata theory and digital fingerprinting. It is known that the Kerdock code of sufficient order is (2,1)- and (2,2)-separating, but the separating weight is only known by a lower bound due to Sagalovich. In this correspondence, we prove that the lower bound on the (2,1)-separating weight is met with equality.

We give a lower bound for the minimum distance of double circulant binary quadratic residue codes for primes p/spl equiv//spl plusmn/3(mod8). This bound improves on the square root bound obtained by Calderbank and Beenker, using a completely different technique. The key to our estimates is to apply a result by Helleseth, to which we give a new and shorter proof. Combining this result with the Weil bound leads to the improvement of the Calderbank and Beenker bound. For large primes p, their bound is of order /spl radic/(2p) while our new improved bound is of order 2/spl radic/p. The results can be extended to any prime power q and the modifications of the proofs are briefly indicated.

For an odd prime p and integers n, m, and k such that n=(2m+1)k, a new family of p-ary sequences of period p/sup n/-1 with optimal correlation property is constructed using the p-ary Helleseth-Gong sequences with ideal autocorrelation, where the size of the sequence family is p/sup n/. That is, the maximum nontrivial correlation value R/sub max/ of all pairs of distinct sequences in the family does not exceed p/sup n/2/+1, which means the family has optimal correlation in terms of Welch's lower bound. The symbol distribution of the sequences in the family is enumerated. It is also shown that the linear span of the sequences in the family is (m+2)n except for the m-sequence in the family.

The number of cosets of weight 2/sup k-2/ or less are determined for the [2/sup k/-1, k, 2/sup k-1/] simplex code and a [2/sup k/-1, k, 2/sup k-1/-1] code obtained by a simple modification of the simplex code. The result proves that the [2/sup k/-1, k] simplex codes are not optimal for error correction on the binary symmetric channel with small bit error probability, p, (for k/spl ges/3). A proof that the modified code is better for all p, 0<p<1/2, is sketched.

In this article, the linear complexity over F/sub p/ of Lempel-Cohn-Eastman (1977) sequences of period p/sup m/-1 for an odd prime p is determined. For p=3,5, and 7, the exact closed-form expressions for the linear complexity over F/sub p/ of LCE sequences of period p/sup m/-1 are derived. Further, the trace representations for LCE sequences of period p/sup m/-1 for p=3 and 5 are found by computing the values of all Fourier coefficients in F/sub p/ for the sequences.

For a prime q and an integer j/spl les/q, the code C(q,j) is a class of low-density parity-check (LDPC) codes from array codes which has a nice algebraic structure. In this correspondence, we investigate the minimum distance d(q,j) of the code in an algebraic way. We first prove that the code is invariant under a doubly transitive group of "affine" permutations. Then, we show that d(5,4)=8, d(7,4)=8, and d(q,4)/spl ges/10 for any prime q>7. In addition, we also analyze the codewords of weight 6 in the case of j=3 and the codewords of weight 8 in C(5,4) and C(7,4).

Irreducible cyclic codes have been an interesting subject of study for many years. The weight distribution of some of them have been determined. We determine the minimum distance and certain weights of the duals of binary irreducible cyclic codes. We show that the weight distribution of these codes is determined by the cyclotomic numbers of certain order. As a byproduct, we describe a class of double-error correcting codes.

We find new families of nonbinary sequences of period p/sup n/-1 with symbols from a finite field F/sub p/ for any prime p/spl ges/3. The sequences have two-level ideal autocorrelation and are generalizations of previously found ternary sequences with ideal autocorrelation. Difference sets with parameters ((p/sup n/-1)/(p-1), (p/sup n-1/-1)/(p-1), (p/sup n-2/-1)/(p-1)) can also be derived from these sequences in a natural way.

Almost difference sets have interesting applications in cryptography and coding theory. We give a well-rounded treatment of known families of almost difference sets, establish relations between some difference sets and some almost difference sets, and determine the numerical multiplier group of some families of almost difference sets. We also construct six new classes of almost difference sets, and four classes of binary sequences of period n/spl equiv/0 (mod 4) with optimal autocorrelation. We have also obtained two classes of relative difference sets and four classes of divisible difference sets (DDSs). We also point out that a result due to Jungnickel (1982) can be used to construct almost difference sets and sequences of period 4l with optimal autocorrelation.

In this correspondence we give several new families of binary sequences of period N with optimal three-level autocorrelation, where N/spl equiv/2 (mod 4). These sequences are either balanced or almost balanced. Our construction is based on cyclotomy.

We show that the cross correlation between two ternary m-sequences of period 3/sup n/-1 that differ by the decimation d=2/spl middot/3/sup m/+1, where n=2m+1, takes on three different values. We conjecture the same result for the decimation d=2/spl middot/3/sup r/+1, where n is odd and r is defined by the condition 4r+1/spl equiv/0 mod n. These two new cases form in a sense ternary counterparts of two previously confirmed binary cases, the conjectures of Welch and Niho (1972).

We study the coset weight distributions of the family of Z/sub 4/-linear Goethals-like codes of length N=2/sup m+1/, m/spl ges/3 odd, constructed by Helleseth, Kumar, and Shanbhag (see Designs, Codes and Cryptography, vol.17, no.1-3, p.246-62, 1999). These codes have the same Lee weight distribution as the Z/sub 4/-linear Goethals code /spl Gscr//sub 1/, and, therefore (taking into account the result of Hammons, Kumar, Sloane, Calderbank, and Sole), the binary images of all these codes by the Gray map have the same weight distribution as the binary Goethals code. We prove that all these codes have the same coset weight distributions as the Z/sub 4/-linear Goethals code, constructed by Hammons, Kumar, Sloane, Calderbank, and Sole (see ibid., vol.40, p.301-19, March 1994). The cosets of weight four is the most difficult case. In order to find the number of codewords of weight four in a coset of weight four we have to solve a nonlinear system of equations over the Galois field GF(2/sup m/). Such a system (the degree of one of the equations) depends on k. We prove that the distribution of solutions to such a system does not depend on k and, therefore, coincides with the case k=1 considered earlier by Helleseth and Zinoviev (see Designs, Codes and Cryptography, vol.17, no.1-3, p.246-62, 1999). For k=1, we solved this system in the following sense: for all cases (of cosets of weight four) we have either an exact expression, or an expression in terms of the Kloosterman sums.

We study the coset weight distributions of two well-known families of codes: the three-error-correcting binary Z/sub 4/-linear Goethals codes of length N=2/sup m+1/, m/spl ges/3 odd, and the Z/sub 4/-linear Goethals codes over Z/sub 4/ of length n=N/2=2/sup m/. The hard case is the weight distributions of cosets of weight 4. To know the weight distribution of the coset of weight 4 we have to know the number of codewords of weight 4 in such a coset. Altogether, there are nine different types of cosets of weight 4. For six cases, we give the exact expressions for the number of codewords of weight 4, and for three other cases, we give such expressions in terms of Kloosterman sums.

We present a construction for binary sequences {s(t)} of period N=p/sup m/-1 for an odd prime p based on the polynomial (z+1)/sup d/+az/sup d/+b, and discuss them in some cases of parameters p, m, d, a, and b. We show that new sequences from our construction are balanced or almost balanced and have optimal three-level autocorrelation for the case when the polynomial (z+1)/sup d/+z/sup d/+a can be transformed into the form z/sup 2/-c. We also derive the distribution of autocorrelation values they take on. The sequences satisfy constant-on-the-coset property, and we show that there are more than one characteristic phases with constant-on-the-coset property. Some other interesting properties of those sequences are presented. For the cases when the polynomial (z+1)/sup d/+z/sup d/+a cannot be transformed into the form z/sup 2/-c, we performed extensive computer search, and results are summarized. Based on these results, some open problems are formulated.

In a previous paper, No, Golomb, Gong, Lee and Gaal (see ibid., vol.44, p.814-17, 1998) conjectured that certain binary sequences having a simple trace description possess the ideal autocorrelation property. In the present paper it is shown that each such sequence is balanced and, moreover, that the dual of the linear cyclic code generated by the sequence and its cyclic shifts, is a triple-error correcting code having the same weight distribution as the triple-error correcting Bose-Chaudhuri-Hocquenghem (BCH) code. This cyclic code also contains a cyclic subcode that yields a new family of sequences having the same size and correlation parameters as does the family of Gold sequences.

The existence of a ternary [28, 6, 16] code is considered. We show that without loss of generality, a generator matrix of such a code must satisfy certain conditions. A computer search over all matrices that satisfy these conditions reveals that a ternary [28, 6, 16] code does not exist.

We first introduce a generalized cyclotomy of order 2 with respect to p/sub 1//sup e(1)/...p/sub t//sup e(t)/. We then present two classes of new error-correcting binary cyclic codes of length p/sub 1//sup e(1)/...p/sub t//sup e(t)/ based on this generalized cyclotomy. We prove either a square-root bound or a similar bound on the minimum odd weight of those codes with length n=p/sub 1//sup e(1)/ p/sub 2//sup e(2)/.

In this correspondence we describe several classes of binary sequences with three-level autocorrelation. Those classes of binary sequences are based on cyclic almost difference sets. Some classes of binary sequences have optimum autocorrelation.

This article contains results on the generalized Hamming weights (GHW) for the Goethals and Preparata codes over Z/sub 4/. We give an upper bound on the rth generalized Hamming weights d/sub r/(m,j) for the Goethals code G/sub m/(j) of length 2/sup m/ over Z/sub 4/, when m is odd. We also determine d/sub 3.5/(m,j) exactly. The upper bound is shown to be tight up to r=3.5. Furthermore, we determine the rth generalized Hamming weight d/sub r/(m) for the Preparata code of length 2/sup m/ over Z/sub 4/ when r=3.5 and r=4.

A power mapping f(x)=x/sup d/ over GF(p/sup n/) is said to be differentially k-uniform if k is the maximum number of solutions x/spl isin/GF(p/sup n/) of f(x+a)-f(x)=b where a, b/spl isin/GF(p/sup n/) and a/spl ne/0. A 2-uniform mapping is called almost perfect nonlinear (APN). We construct several new infinite families of nonbinary APN power mappings.

The quaternary Calderbank-McGuire (see Des., Codes Cryptogr., vol.10, no.2, 1997) code is a Z/sub 4/-linear code of length 32 which has 2/sup 37/ codewords and a minimum Lee distance of 12. The Gray map of this code is known to be a nonlinear binary (64, 2/sup 37/,12) code. The Z/sub 4/-linear Calderbank-McGuire code can correct all errors with Lee weight /spl les/5. An algebraic decoding algorithm for the code is presented in this paper. Furthermore, we discuss an alternative decoding method which takes advantage of the efficient BCH decoding algorithm.

We determine the linear complexity of all Legendre sequences and the (monic) feedback polynomial of the shortest linear feedback shift register that generates such a Legendre sequence. The result shows that Legendre sequences are quite good from the linear complexity viewpoint.

The rth generalized Hamming weight d/sub r/(m,j) of the Goethals code /spl Gscr//sub m/(j) of length 2/sup m/ over Z/sub 4/ is considered in this correspondence. In the case that m/spl ges/3 is an odd integer, d/sub r/(m,j) is exactly determined for r=0.5, 1, 1.5, 2, 2.5, and 3.0. For a composite m, we give an upper bound d/sub r/(m,j) using the lifting technique.

Constructions of [162,8,80] and [159,8,78] codes are given. This solves the open problems of finding the minimum length of binary codes of dimension S and minimum distances 78 and 80, respectively.

For a binary linear code C of minimum distance d, if t>(d-1)/2, then there are errors of weight t which are not uniquely correctable. However, in many cases there are also errors of weight t which are uniquely correctable. The Newton radius of a code is defined to be the largest weight of a uniquely correctable error. Bounds and exact values of the Newton radius are given for several classes of codes.

The information function e/sub h/ of a code is the average amount of information contained in h positions of the codewords. Upper and lower bounds on the information function of binary linear codes are given. The average value and variance of the information function over all [n, k] codes are determined,.

Hammons et al. (see ibid., vol.40, p.301-19, 1994) showed that, when properly defined, the binary nonlinear Preparata code can be considered as the Gray map of a linear code over Z/sub 4/, the so called Preparata code over Z/sub 4/. We consider the rth generalized Hamming weight d/sub r/(m) of the Preparata code of length 2/sup m/ over Z/sub 4/. For any m/spl ges/3, d/sub r/(m) is exactly determined for r=0.5, 1, 1.5, 2, 2.5 and 3.0. For a composite m, we give an upper bound on d/sub r/(m) using the lifting technique. For m=3, 4, 5, 6 and 8, the weight hierarchy is completely determined. In the case of m=7, the weight hierarchy is completely determined except for d/sub 4/(7).

Certain nonlinear binary codes contain more codewords than any comparable linear code presently known. These include the Kerdock (1972) and Preparata (1968) codes that can be very simply constructed as binary images, under the Gray map, of linear codes over Z/sub 4/ that are defined by means of parity checks involving Galois rings. This paper describes how Fourier transforms on Galois rings and elementary symmetric functions can be used to derive lower bounds on the minimum distance of such codes. These methods and techniques from algebraic geometry are applied to find the exact minimum distance of a family of Z/sub 4/. Linear codes with length 2/sup m/ (m, odd) and size 2(2/sup m+1/-5m-2). The Gray image of the code of length 32 is the best (64, 2/sup 37/) code that is presently known. This paper also determines the exact minimum Lee distance of the linear codes over Z/sub 4/ that are obtained from the extended binary two- and three-error-correcting BCH codes by Hensel lifting. The Gray image of the Hensel lift of the three-error-correcting BCH code of length 32 is the best (64, 2/sup 32/) code that is presently known. This code also determines an extremal 32-dimensional even unimodular lattice.

Bounds on the weight hierarchies of the product of two simplex codes, two first order Reed-Muller codes, and the product of a simplex code and a first-order Reed-Muller code are determined. The weight hierarchies of the product of two Hamming codes and the product of a Hamming code and an even-weight code are also discussed.

An upper hound for Weil-type exponential sums over Galois rings was derived by Kumar, Helleseth, and Calderbank (see ibid., vol.41, no.3, p.456, 1995). This bound leads directly to an estimate for the minimum distance of Z/sub 4/-linear trace codes. An improved minimum-distance estimate is presented. First, McEliece's result on the divisibility of the weights of binary cyclic codes is extended to Z/sub 4/ trace codes. The divisibility result is then combined with the techniques of Serre (1983) and of Moreno and Moreno (see ibid., vol.40, no.11, p.1101, 1994) to derive the improved minimum-distance estimate. The improved estimate is tight for the Kerdock code as well as for the Delsarte-Goethals codes.

A family of quaternary (Z/sub 4/-alphabet) sequences of length L=2/sup r/-1, size M/spl ges/L/sup 2/+3L+2, and maximum nontrivial correlation parameter C/sub max//spl les/2/spl radic/(L+1)+1 is presented. The sequence family always contains the four-phase family /spl Ascr/. When r is odd, it includes the family of binary Gold sequences. The sequence family is easily generated using two shift registers, one binary, the other quaternary. The distribution of correlation values is provided. The construction can be extended to produce a chain of sequence families, with each family in the chain containing the preceding family. This gives the design flexibility with respect to the number of intermittent users that can be supported, in a code-division multiple-access cellular radio system. When r is odd, the sequence families in the chain correspond to shortened Z/sub 4/-linear versions of the Delsarte-Goethals codes.

An upper bound for a hybrid exponential sum over Galois rings is derived. This bound is then used to obtain an upper bound for the maximum aperiodic correlation of some sequence families over Galois rings. The bound is of the order of /spl radic/qlnq where q-1 is the period of the sequences.

A bound on exponential sums over Galois rings is used to construct a nested chain of Z/sub 4/-linear binary codes and binary sequences. When compared with the chain of Delsarte-Goethals'(1975) codes, the codes in the new chain offer a larger minimum distance for the same code size. The binary sequence families constructed also make use of Nechaev's (1991) construction of a cyclic version of the Kerdock code. For a given value of maximum correlation, the binary sequences are shown to have a family size considerably larger than the best sequence families known.

The rth generalized Hamming weight d/sub r/ of the Kerdock code of length 2/sup m/ over Z/sub 4/ is considered. A lower bound on d/sub r/ is derived for any r, and d/sub r/ is exactly determined for r=0.5, 1, 1.5, 2, 2.5. In the case of length 2/sup 2m/, d/sub r/ is determined for any r, where 0/spl les/r/spl les/m and 2r is an integer. In addition, it is shown that it is sometimes possible to determine the generalized Hamming weights of the Kerdock codes of larger length using the results of d/sub r/ for a given length. The authors also provide a closed-form expression for the Lee weight of a Kerdock codeword in terms of the coefficients in its trace expansion.

The quaternary Goethals code is a Z/sub 4/-linear code of length 2/sup m/ which has 2(2/sup m+1)/(-3m-2) codewords and minimum Lee distance 8 for any odd integer m/spl ges/3. The Gray map of this code is known to be a nonlinear binary (2/sup m+1/, 2(2/sup m+1)/(-3m-2), 8) code. The covering radius of the Z/sub 4/-linear Goethals code is 6 and we present a complete decoding algorithm for the code.

The minimum support weight, d/sub r/(C), of a linear code C over GF(q) is the minimal size of the support of an r-dimensional subcode of C. A number of bounds on d/sub r/(C) are derived, generalizing the Plotkin bound and the Griesmer bound, as well as giving two new existential bounds. As the main result, it is shown that there exist codes of any given rate R whose ratio d/sub rd/sub 1/ is lower bounded by a number ranging from (q/sup r/-1)/(q/sup r/-q/sup r-1/) to r, depending on R.>

We present an analog of the well-known Weil-Carlitz-Uchiyama (1948, 1957) upper bound for exponential sums over finite fields for exponential sums over Galois rings. Some examples are given where the bound is tight. The bound has immediate application to the design of large families of phase-shift-keying sequences having low correlation and an alphabet of size p/sup e/. p, prime, e/spl ges/2. Some new constructions of eight-phase sequences are provided.>

This paper provides two theorems for decoding all types of cyclic codes. It is shown that from a polynomial ideal point of view, the decoding problems of cyclic codes are closely related to the monic generators of certain polynomial ideals. This conclusion is also generalized to the decoding problems of algebraic geometry codes.>

A general algebraic method for decoding all types of binary cyclic codes is presented. It is shown that such a method can correct t=[(d-1)/2] errors, where d is the true minimum distance of the given cyclic code. The key idea behind this decoding technique is a systematic application of the algorithmic procedures of Grobner bases to obtain the error-locator polynomial L(z). The discussion begins from a set of syndrome polynomials F and the ideal T(F) generated by F. It is proved here that the process of transforming F to the normalized reduced Grobner basis of I(F) with respect to the "purely lexicographical" ordering automatically converges to L(z). Furthermore, it is shown that L(z) can be derived from any normalized Grobner basis of I(F) with respect to any admissible total ordering. To illustrate this new approach, the procedures for decoding certain BCH codes and quadratic residue codes are demonstrated.>

The generalized Hamming weight, d/sub r/(C), of a binary linear code C is the size of the smallest support of any r-dimensional subcode of C. The parameter d/sub r/(C) determines the code's performance on the wire-tap channel of Type II. Bounds on d/sub r/(C), and in some cases exact expressions, are derived. In particular, a generalized Griesmer bound for d/sub r/(C) is presented and examples are given of codes meeting this bound with equality.>

It has been conjectured by T. Chang et al. (1990) that the number of cross-join pairs in a maximum length linear sequence equals (2/sup n-1/-1)(2/sup n-1/-2)/6. A maximum length linear sequence (an m-sequence) of length 2/sup n/-1 is a binary sequence which satisfies a linear recurrence whose characteristic polynomial is primitive of degree n. The number of primitive polynomials is given by phi (2/sup n/-1)/n, where phi is Euler's phi -function. A proof of the conjecture is given.>

The existence of a binary (25,8,10) code is considered. It is shown that such a code must have a generator matrix of a specific form. However, all generator matrices of this form were tested and none generated a (25,8,10) code. Thus, such a code does not exist.>

Letn(k,d)be the smallest integernsuch that a binary linear code of lengthn, dimensionk, and minimum distance at leastdexists. New results are given that improve the best previously known bounds onn(8,d).

For any(n, k, d)binary linear code, the Griesmer bound says thatn \geq \sum_{i=0}^{k-1} \lceil d/2^{i} \rceil, where\lceil x \rceildenotes the smallest integer\geq x. We consider codes meeting the Griesmer bound with equality. These codes have parametersleft( s(2^{k} - 1) - \sum_{i=1}^{p} (2^{u_{i}} - 1), k, s2^{k-1} - \sum_{i=1}^{p} 2^{u_{i} -1} \right), wherek > u_{1} > \cdots > u_{p} \geq 1. We characterize all such codes whenp = 2oru_{i-1}-u_{i} \geq 2for2 \leq i \leq p.

For any binary linear( n , k , d)code the Grfesmer bound says thatn \geq \sum_{i=0}^{k-1} \lceil d/2^{i} \rceil. We investigate codes that meet this bound with equality. We give new descriptions of(\sum_{i=0}^{k-1}\lceil d/2^{i} \rceil , k, d)codes that have earlier been constructed by Solomon and Stiffler, Belov, and Helleseth and van Tilborg. Finally we show how to construct several new families of such codes with parameters not obtainable by any previous known constructions.

An infinite sequence ofk-dimensional binary linear block codes is constructed with parametersn=2^{k}+2^{k-2}-15,d=2^{k-1}+2^{k-3}-8,k \geq 7. Fork \geq 8these codes are unique, while there are five nonisomorphic codes fork=7. By shortening these codes in an appropriate way, one finds codes meeting the Griesmer bound for2^{k-1}+2^{k-3}-15 \leq d \leq 2^{k-1}+2^{k-3}-8; k \geq 7.

Gorenstein, Peterson, and Zierler have conjectured that not-error-correcting BCH code of length2^{m} - 1witht > 2is quasi-perfect. This conjecture is proved. The covering radius of a code is defined as the smallest integer\rhosuch that the union of the spheres of radius ia about the codewords equals the containing space.

Van der Horst and Berger have conjectured that the covering radius of the binary 3-error-correcting Bose-Chaudhuri-Hocquenghem (BCH) code of length2^{m} - l, m \geq 4is 5. Their conjecture was proved earlier whenm \equiv 0, 1, or 3 (mod 4). Their conjecture is proved whenm \equiv 2(mod 4).

Upper bounds on the covering radius of binary codes are studied. In particular it is shown that the covering radiusr_{m}of the first-order Reed-Muller code of lenglh2^{m}satisfies2^{m-l}-2^{\lceil m/2 \rceil -1} r_{m} \leq 2^{m-1}-2^{m/2-1}.

The Hamming weight enumerator polynomials of some two-weight codes are presented. The codes have parity-check polynomials which are products of two irreducible polynomials.