Group codes form an important class of spherical codes, consisting of a single orbit under a subgroup of the orthogonal group. They have been studied by (Mittelholzer-Lahtonen, 1996) in the case of Coxeter groups for their packing radius. We study them here for the same groups, with respect to their covering radius. An exact algorithm to determine their covering radii is derived, based on geometric ideas, and applied to tabulate their values in dimensions up to 8. The values of the covering radii are compared to the sphere covering bound, and to the bounds in (Fazekas-Levenshtein, 1995) and (Boyvalenkov-Stoyanova, 2021) on the covering radius of spherical designs with given strength. For many sizes of codes, our codes are reasonably sparse sphere coverings, and the only known in these dimensions.

Abstract Let G be a primitive rank 3 permutation group acting on a set of size v. Binary codes of length v globally invariant under G are well-known to hold PBIBDs in their $$A_w$$ A w codewords of weight w. The parameters of these designs are $$\bigg (A_w,v,w,\frac{wA_w}{v},\lambda _1,\lambda _2\bigg ).$$ ( A w , v , w , w A w v , λ 1 , λ 2 ) . When $$\lambda _1=\lambda _2=\lambda ,$$ λ 1 = λ 2 = λ , the PBIBD becomes a 2- $$(v,w,\lambda )$$ ( v , w , λ ) design. We obtain computationally 111 such designs when G ranges over $$\textrm{L}_2(8){:}3, \textrm{U}_{4}(2), \textrm{U}_{3}(3){:}2, \textrm{A}_8, \textrm{S}_6(2),$$ L 2 ( 8 ) : 3 , U 4 ( 2 ) , U 3 ( 3 ) : 2 , A 8 , S 6 ( 2 ) , $$\textrm{S}_{4}(4), \textrm{U}_{5}(2), \textrm{M}_{11}, \textrm{M}_{22}, \textrm{HS}, \textrm{G}_2(4), \textrm{S}_{8}(2),\textrm{O}^{+}_{10}(2),$$ S 4 ( 4 ) , U 5 ( 2 ) , M 11 , M 22 , HS , G 2 ( 4 ) , S 8 ( 2 ) , O 10 + ( 2 ) , and $$\textrm{O}^{-}_{10}(2)$$ O 10 - ( 2 )

Abstract Strongly walk regular graphs (SWRGs or s-SWRGs) form a natural generalization of strongly regular graphs (SRGs) where paths of length 2 are replaced by paths of length s. They can be constructed as coset graphs of the duals of projective three-weight codes whose weights satisfy a certain equation. We provide classifications of the feasible parameters of these codes in the binary and ternary case for medium size code lengths. For the binary case, the divisibility of the weights of these codes is investigated and several general results are shown. It is known that an s-SWRG has at most 4 distinct eigenvalues $$k> \theta _1> \theta _2 > \theta _3$$ k > θ 1 > θ 2 > θ 3 , and that the triple $$(\theta _1, \theta _2, \theta _3)$$ ( θ 1 , θ 2 , θ 3 ) satisfies a certain homogeneous polynomial equation of degree $$s - 2$$ s - 2 (Van Dam, Omidi, 2013). This equation defines a plane algebraic curve; we use methods from algorithmic arithmetic geometry to show that for $$s = 5$$ s = 5 and $$s = 7$$ s = 7 , there are only the obvious solutions, and we conjecture this to remain true for all (odd) $$s \ge 9$$ s ≥ 9 .

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.

We study challenge codes for physically unclonable functions (PUFs). Starting from the classical Hadamard challenge code, we augment it by one vector. Numerical values suggest that the optimal choice of this vector for maximizing the entropy is to pick a vector the farthest away from the code formed by the challenges and their binary complements. This leads us to study the covering radius of Hadamard codes. A notion of bent sequence that generalizes the classical notion from Hadamard matrices of Sylvester type to general Hadamard matrices is given. Lower bounds for Paley-type Hadamard matrices are given.

We use linear programming (LP) to derive upper and lower bounds on the “kissing number” $A_{d}$ of any q-ary linear code C with distance distribution frequencies $A_{i}$, in terms of the given parameters $[n,\ k,\ d]$. In particular, a polynomial method gives explicit analytic bounds in a certain range of parameters, which are sharp for some low-rate codes like the first-order Reed-Muller codes. The general LP bounds are more suited to numerical estimates. Besides the classical estimation of the probability of decoding error and of undetected error, we outline recent applications in hardware protection against side-channel attacks using code-based masking countermeasures, where the protection is all the more efficient a s the kissing number is low.

We investigate fat projective linear codes over${\mathbb Z}_{p^{m}}$,$m\geqslant 2$, with two nonzero homogeneous weights (“two-weight codes”), building on the graph theory approach developed by Delsarte for codes over fields. Our main result is the classification of such codes under the additional assumption that the columns of a generator matrix of the code determine a cap in the projective Hjelmslev geometry$\mathop {\mathrm {PHG}}\nolimits (k-1, {\mathbb Z}_{p^{m}})$. This generalizes a result on projective two weight codes with dual distance at least four (Calderbank, 1982). The proof relies on a careful analysis of a certain strongly regular graph built on the cosets of the dual code, and on an interpretation of its parameters in terms of projective Hjelmslev geometry.

We study the codes of the title by the CRT method, that decomposes such codes into constituent codes, which are shorter codes over larger alphabets. Criteria on these constituent codes for self-duality and linear complementary duality of the decomposed codes are derived. The special class of the one-generator codes is given a polynomial representation and exactly enumerated. In particular, we present some illustrative examples of binary optimal linear codes with respect to the Griesmer bound derived from the$\mathbb {Z}_{2} \mathbb {Z}_{4}$-additive quasi-cyclic codes.

Symbol-pair codes were introduced by Cassuto and Blaum in 2010 to protect pair errors in symbol-pair read channels. Recently Yaakobi, Bruck and Siegel (2016) generalized this notion to b-symbol codes in order to consider consecutive b errors for a prescribed integer b ≥ 2, and they gave constructions and decoding algorithms. Cyclic codes were considered by various authors as candidates for symbol-pair codes and they established minimum distance bounds on (certain) cyclic codes. In this paper we use algebraic curves over finite fields in order to obtain tight lower and upper bounds on b-symbol Hamming weights of arbitrary cyclic codes over Fq. Here b ≥ 2 is an arbitrary prescribed positive integer and \mathbb Fqis an arbitrary finite field. We also present a stability theorem for an arbitrary cyclic code C of dimension k and length n: the b-symbol Hamming weight enumerator of C is the same as the k-symbol Hamming weight enumerator of C if k ≤ b ≤ n-1. Moreover, we give improved tight lower and upper bounds on b-symbol Hamming weights of some cyclic codes related to irreducible cyclic codes. Throughout the paper the length n is coprime to q.

The dual of the Kasami code of length q2- 1, with q a power of 2, is constructed by concatenating a cyclic MDS code of length q + 1 over Fq with a Simplex code of length q - 1. This yields a new derivation of the weight distribution of the Kasami code, a new description of its coset graph, and a new proof that the Kasami code is completely regular. The automorphism groups of the Kasami code and the related q-ary MDS code are determined. New cyclic completely regular codes over finite fields a power of 2, generalized Kasami codes, are constructed; they have coset graphs isomorphic to that of the Kasami codes. Another wide class of completely regular codes, including additive codes, as well as unrestricted codes, is obtained by combining cosets of the Kasami or generalized Kasami code.

Upper and lower bounds on the largest number of weights in a cyclic code of given length, dimension and alphabet are given. An application to irreducible cyclic codes is considered. Sharper upper bounds are given for the special cyclic codes (called here strongly cyclic), whose nonzero codewords have period equal to the length of the code. Asymptotics are derived on the function Γ(k, q), that is defined as the largest number of nonzero weights a cyclic code of dimension k over Fq can have, and an algorithm to compute it is sketched. The nonzero weights in some infinite families of Reed-Muller codes, either binary or q-ary, as well as in the q-ary Hamming code are determined, two difficult results of independent interest.

We investigate the largest number of nonzero weights of quasi-cyclic codes. In particular, we focus on the function ΓQ(n, ℓ, k, q), that is defined to be the largest number of nonzero weights a quasi-cyclic code of index gcd(ℓ, n), length n and dimension k over Fqcan have, and connect it to similar functions related to linear and cyclic codes. We provide several upper and lower bounds on this function, using different techniques and studying its asymptotic behavior. Moreover, we determine the smallest index for which a q-ary Reed-Muller code is quasi-cyclic, a result of independent interest.

We apply quantum Construction X on quasi-cyclic codes with large Hermitian hulls over F4and F9to derive good qubit and qutrit stabilizer codes, respectively. In several occasions we obtain quantum codes with stricly improved parameters than the current record. In numerous other occasions we obtain quantum codes with best-known performance. For the qutrit ones we supply a systematic construction to fill some gaps in the literature.

We show that puncturing the dodecacode, a nonlinear self-dual additive quaternary code of length 12, leads to a uniformly packed code of distance 5. The coset graph of this code is a diameter-3 distance-regular graph on 1024 vertices, with the intersection array {33,30,15;1,2,15}. We discuss the properties of the new distance-regular graph and related quaternary and binary completely-regular codes.

The dodecacode is a nonlinear additive quaternary code of length 12. By puncturing it at any of the twelve coordinates, we obtain a uniformly packed code of distance 5. In particular, this latter code is completely regular but not completely transitive. Its coset graph is distance-regular of diameter three on $$2^{10}$$ vertices, with new intersection array $$\{33,30,15;1,2,15\}$$ . The automorphism groups of the code, and of the graph, are determined. Connecting the vertices at distance two gives a strongly regular graph of (previously known) parameters $$(2^{10}, 495,238, 240)$$ . Another strongly regular graph with the same parameters is constructed on the codewords of the dual code. A non trivial completely regular binary code of length 33 is constructed.

The article “A new distance-regular graph of diameter 3 on 1024 vertices", written by Minjia Shi, Denis S. Krotov and Patrick Solé, was originally published electronically on the publisher's internet portal (currently SpringerLink) on 24 January 2019 without open access.

We study linear complementary pairs (LCP) of codes (C, D), where both codes belong to the same algebraic code family. We especially investigate constacyclic and quasicyclic LCP of codes. We obtain characterizations for LCP of constacyclic codes and LCP of quasi-cyclic codes. Our result for the constacyclic complementary pairs extends the characterization of linear complementary dual (LCD) cyclic codes given by Yang and Massey. We observe that when C and D are complementary and constacyclic, the codes C and D⊥are equivalent to each other. Hence, the security parameter min(d(C), d(D⊥)) for LCP of codes is simply determined by one of the codes in this case. The same holds for a special class of quasi-cyclic codes, namely 2D cyclic codes, but not in general for all quasi-cyclic codes, since we have examples of LCP of double circulant codes not satisfying this conclusion for the security parameter. We present examples of binary LCP of quasi-cyclic codes and obtain several codes with better parameters than known binary LCD codes. Finally, a linear programming bound is obtained for binary LCP of codes and a table of values from this bound is presented in the case d(C) = d(D⊥). This extends the linear programming bound for LCD codes.

The construction of deletion codes for the editing metric is reduced to the construction of codes over the integers for the Manhattan metric by run length coding. The latter codes are constructed by expurgation of lattices' translates. These lattices, in turn, are obtained from Construction A applied to binary codes and Z4-codes. A lower bound on the size of our codes for the Manhattan distance are obtained through generalized theta series of the corresponding lattices. For any fixed number of deletions, provided the number of runs is large enough our method supplies a correction technique. For fixed number of runs and binary sequence length large our lattice construction is shown to be tight up to constants.

We construct two new infinite families of trace codes of dimension 2m, over the ring Fp+ uFp, with u2= u, when p is an odd prime. They have the algebraic structure of abelian codes. Their Lee weight distribution is computed by using Gauss sums. By Gray mapping, we obtain two infinite families of linear p-ary codes of respective lengths (pm-1)2and 2(pm-1)2. When m is singly even, the first family gives five-weight codes. When m is odd and p ≡ 3 (mod 4), the first family yields p-ary two-weight codes, which are shown to be optimal by application of the Griesmer bound. The second family consists of two-weight codes that are shown to be optimal, by the Griesmer bound, whenever p = 3 and m ≥ 3, or p ≥ 5 and m ≥ 4. Applications to secret sharing schemes are given.

A physically unclonable function (PUF) is a hardware device that can generate intrinsic responses from challenges. The responses serve as unique identifiers and it is required that they be as little predictable as possible. A loop-PUF is an architecture where n single-bit delay elements are chained. Each PUF generates one bit response per challenge. We model the relationship between responses and challenges in a loop-PUF using Gaussian random variables and give a closed-form expression of the total entropy of the responses. It is shown that n bits of entropy can be obtained with n challenges if and only if the challenges constitute a Hadamard code. Contrary to a previous belief, it is shown that adding more challenges results in an entropy strictly greater than n bits. A greedy code construction is provided for this purpose.

We consider the Gaussian wiretap channel, where two legitimate players Alice and Bob communicate over an additive white Gaussian noise (AWGN) channel, while Eve is eavesdropping, also through an AWGN channel. We propose a coding strategy based on lattice coset encoding. We define the secrecy gain as a design criterion for wiretap lattice codes, expressed in terms of the lattice theta series, which characterizes Eve's confusion as a function of the channel parameters. The secrecy gain is studied for even unimodular lattices, and an asymptotic analysis shows that it grows exponentially in the dimension of the lattice. Examples of wiretap lattice codes are given.

Binary matrix codes with restricted row and column weights are a desirable method of coded modulation for power line communication. In this work, we construct such matrix codes that are obtained as products of affine codes - cosets of binary linear codes. Additionally, the constructions have the property that they are systematic. Subsequently, we generalize our construction to irregular product of affine codes, where the component codes are affine codes of different rates.

We introduce complementary information set codes of higher order. A binary linear code of length tk and dimension k is called a complementary information set code of order t (t-CIS code for short) if it has t pairwise disjoint information sets. The duals of such codes permit to reduce the cost of masking cryptographic algorithms against side-channel attacks. As in the case of codes for error correction, given the length and the dimension of a t-CIS code, we look for the highest possible minimum distance. In this paper, this new class of codes is investigated. The existence of good long CIS codes of order 3 is derived by a counting argument. General constructions based on cyclic and quasi-cyclic codes and on the building up construction are given. A formula similar to a mass formula is given. A classification of 3-CIS codes of length ≤ 12 is given. Nonlinear codes better than linear codes are derived by taking binary images of Z4-codes. A general algorithm based on Edmonds' basis packing algorithm from matroid theory is developed with the following property: given a binary linear code of rate 1/t, it either provides t disjoint information sets or proves that the code is not t-CIS. Using this algorithm, all optimal or best known [tk, k] codes, where t = 3, 4, . . . , 256 and 1≤ k ≤⌊256/t⌋ are shown to be t-CIS for all such k and t, except for t = 3 with k = 44 and t = 4 with k = 37.

We introduce the class of multiply constant-weight codes to improve the reliability of certain physically unclonable function response, and extend classical coding methods to construct multiply constant-weight codes from known \(q\) -ary and constant-weight codes. We derive analogs of Johnson bounds and give constructions showing these bounds to be asymptotically tight up to a constant factor under certain conditions. We also examine the rates of multiply constant-weight codes and demonstrate that these rates are the same as those of constant-weight codes of corresponding parameters.

Hermitian self-dual abelian codes in a group ring Fq2[G], where Fq2is a finite field of order q2and G is a finite abelian group, are studied. Using the well-known discrete Fourier transform decomposition for a semisimple group ring, a characterization of Hermitian self-dual abelian codes in Fq2[G] is given, together with an alternative proof of necessary and sufficient conditions for the existence of such a code in Fq2[G], i.e., there exists a Hermitian self-dual abelian code in Fq2[G] if and only if the order of G is even and q = 2lfor some positive integer l. Later on, the study is further restricted to the case where F22l[G] is a principal ideal group ring, or equivalently, G ≅ A⊕Z2k with 2 ≠ |A|. Based on the characterization obtained, the number of Hermitian self-dual abelian codes in F22l [A⊕Z2k] can be determined easily. When A is cyclic, this result answers an open problem of Jia et al. concerning Hermitian self-dual cyclic codes. In many cases, F22l [A⊕Z2k] contains a unique Hermitian self-dual abelian code. The criteria for such cases are determined in terms of l and the order of A. Finally, the distribution of finite abelian groups A such that a unique Hermitian self-dual abelian code exists in F22l [A ⊕ Z2] is established, together with the distribution of odd integers m such that a unique Hermitian self-dual cyclic code of length 2 m over F22l exists.

The function M(m, n, d, w), the largest size of an unrestricted binary code made of m by n arrays, with constant row weight w, and minimum distance d is introduced and compared to the classical functions of combinatorial coding theory Aq(n, d) and A(n, d, w). The analogues for systematic codes of A(n, d) and A(n, d, w) are introduced apparently for the first time. An application to the security of embedded systems is given: these codes happen to be efficient challenges for physically unclonable functions.

This paper considers cyclic DNA codes of arbitrary length over the ring R = F2[u]/(u4- 1). A mapping is given between the elements of R and the alphabet {A, C, G, T} which allows the additive stem distance to be extended to this ring. Then, cyclic codes over R are designed such that their images under the mapping are also cyclic or quasi-cyclic of index 2 with designed hybridization energy. The hybridization energy and additive distance are shown to be functions of the neighborhood energy.

Insertion/Deletion codes for the Levenshtein distance are constructed by truncation of lattices for the L1metric. These lattices are obtained from Construction A applied to binary codes and Z4-codes. Finally, Gilbert and Hamming type of bounds are derived.

In this paper, we present an analog of the Singleton bound for convolutional codes over finite rings. Codes meeting that bound are called MDS. A constructive method for the MDS codes, restricted to free codes, is presented via cyclic codes over finite rings. Examples of nonfree MDS codes are provided.

We introduce a new class of rate one-half binary codes: complementary information set codes. A binary linear code of length$2n$and dimension$n$is called a complementary information set code (CIS code for short) if it has two disjoint information sets. This class of codes contains self-dual codes as a subclass. It is connected to graph correlation immune vectorial Boolean functions of use in the security of hardware implementations of cryptographic primitives. Such codes permit to improve the cost of masking cryptographic algorithms against side channel attacks. In this paper, we investigate this new class of codes: we give optimal or best known CIS codes of length$ < 132$. We derive general constructions based on cyclic codes and on double circulant codes. We derive a Varshamov–Gilbert bound for long CIS codes, and show that they can all be classified in small lengths$\leq 12$by the building up construction. Some nonlinear permutations are constructed by using${\BBZ}_{4}$-codes, based on the notion of dual distance of a possibly nonlinear code.

In this paper we classify all extremal and s-extremal binary self-dual codes of length 38. There are exactly 2744 extremal self-dual codes, two s-extremal codes, and 1730 s-extremal codes. We obtain our results from the use of a recursive algorithm used in the recent classification of all extremal self-dual codes of length 36, and from a generalization of this recursive algorithm for the shadow. The classification of -extremal codes permits to achieve the classification of all -extremal codes with .

It is known that, for transmission over quasi-static MIMO fading channels with n transmit antennas, diversity can be obtained by using an inner fully diverse space-time block code while coding gain, derived from the determinant criterion, comes from an appropriate outer code. When the inner code has a cyclic algebra structure over a number field, as for perfect space-time codes, an outer code can be designed via coset coding, more precisely, by taking the quotient of the algebra by a two-sided ideal which leads to matrices over finite alphabets for the outer code. In this paper, we show that the determinant criterion induces various metrics on the outer code, such as the Hamming and Bachoc distances. When n = 2, partitioning the 2×2 Golden code by using an ideal above the prime 2 leads to consider codes over either M2(F2) or M2(F2[i]), both being noncommutative alphabets. By identifying them as algebras over a finite field or a finite ring respectively, we establish an unexpected connection with classical error-correcting codes over F4and F4[i]. Matrix rings of higher dimension, suitable for 3×3 and 4×4 perfect codes, give rise to more complex examples.

The average radius of a block code is a parameter that occurs naturally in quantization and steganography. We give asymptotic upper and lower bounds on this parameter. In particular we show that for almost all long codes the normalized average radius equals the normalized covering radius. We survey some special graph-theoretic lower bounds.

The maximum size of a binary code is studied as a function of its lengthn, minimum distanced, and minimum codeword weight \ssiw. This functionB(n,d,w) is first characterized in terms of its exponential growth rate in the limitn→∞ for fixed δ =d/nand ω =w/n. The exponential growth rate ofB(n,d,w) is shown to be equal to the exponential growth rate ofA(n,d) for 0 ≤ ω ≤ 1/2, and equal to the exponential growth rate ofA(n,d,w) for 1/2B(n,d,w) are derived using the semidefinite programming (SDP) method. These bounds yield a nonasymptotic improvement of the second Johnson bound and are tight for certain values of the parameters.

The weights in maximum distance separable (MDS) codes of length n and dimension k over the finite field GF(q) are studied. Up to some explicit exceptional cases, the MDS codes with parameters given by the MDS conjecture are shown to contain all k weights in the range n - k + 1 to n. The proof uses the covering radius of the dual code.

We present a general construction of asymmetric quantum codes based on additive codes under the trace Hermitian inner product. Various families of additive codes over F4are used in the construction of many asymmetric quantum codes over F4.

Motivated by certain recent problems in asynchronous communication, we introduce and study B(n, d, w), defined as the maximum number of length n binary sequences with minimum distance d, and such that each sequence has weight at least w. Specifically, we investigate the asymptotic exponential growth rate of B(n, d, w) with respect to n and with fixed ratios δ = d/n and ω = w/n. For ω ∈ [0, 1/2], this growth rate function b(δ, ω) is shown to be equal to a(δ), the asymptotic exponential growth rate of A(n, d)-the maximum number of length n binary sequences with minimum distance d. For ω ∈ (1/2, 1), we show that b(δ, ω) ≤ a(δ, ω) + f(ω), where a(δ, ω) denotes the asymptotic exponential growth rate of A(n, d, w), the maximum number of length n binary sequences with minimum distance d and constant weight w, and where f(w) is a certain function that satisfies 0ω→1f(ω) = limω→1/2f(ω) = 0. Based on numerical evidence, we conjecture that b(δ, ω) is actually equal to a(δ, ω) for ω ∈ (1/2, 1). Finally, lower bounds on B(n, d, w) are obtained via explicit code constructions.

In the authors introduced a lattice invariant called “Secrecy Gain” which measures the confusion experienced by a passive eavesdropper on the Gaussian Wiretap Channel. We study, here, the behavior of this invariant for unimodular lattices by using tools from Modular Forms and show that, for some families of unimodular lattices, indexed by the dimension, the secrecy gain exponentially goes to infinity with the dimension.

We consider an extension of Massey's construction of secret sharing schemes using linear codes. We describe the access structure of the scheme and show its connection to the dual code. We use the g-fold joint weight enumerator and invariant theory to study the access structure.

In this paper, we study code constructions over the finite ring M2(F2), the ring of 2times2 matrices with coefficients in the finite field F2. We show how they can be related to classical codes over F4. We provide as application the design of outer codes for 2 times 2 space-time coded modulation, when the inner code is the so-called Golden code.

Secret sharing is an important topic in cryptography and has applications in information security. We use self-dual codes to construct secret-sharing schemes. We use combinatorial properties and invariant theory to understand the access structure of these secret-sharing schemes. We describe two techniques to determine the access structure of the scheme, the first arising from design properties in codes and the second from the Jacobi weight enumerator, and invariant theory.

Skew Hadamard designs (4 n – 1, 2 n – 1, n – 1) are associated to order 4 n skew Hadamard matrices in the natural way. We study the codes spanned by their incidence matrices A and by I + A and show that they are self-dual after extension (resp. extension and augmentation) over fields of characteristic dividing n . Quadratic Residues codes are obtained in the case of the Paley matrix. Results on the p -rank of skew Hadamard designs are rederived in that way. Codes from skew Hadamard designs are classified. An optimal self-dual code over GF (5) is rediscovered in length 20. Six new inequivalent [56, 28, 16] self-dual codes over GF (7) are obtained from skew Hadamard matrices of order 56, improving the only known quadratic double circulant code of length 56 over GF (7).

In this paper, bounds are derived on the minimum homogeneous distance of the image of a linear block code over the Galois ring GR(pr,m), with respect to any basis of GR(pr, m). These bounds depend on the parameters of GR(pr, m), the minimum Hamming distance of the block code, and the average value of the homogeneous weight applied on the base ring Zpr. Examples are given of Galois ring codes that meet these bounds.

From a linear block code B over the Galois ring GR(4, to) with a k x n generator matrix and minimum Hamming distance d, a rate-k/n convolutional code over the ring Z4with squared Euclidean free distance at least 2d and a non-recursive encoder with memory at most to m-1 is constructed. When the generator matrix of B is systematic, the convolutional encoder is systematic, basic, non-catastrophic and minimal. Long codes constructed in this manner are shown to satisfy a Gilbert-Varshamov bound.

Regarding convolutional codes as polynomial analogues of arithmetic lattices, we derive a Poisson Jacobi formula for their trivariate weight enumerator. The proof is based on harmonic analysis on locally compact abelian groups as developed in Tate's thesis to derive the functional equation of the zeta function.

From a linear block code B over the Galois ring GR(4, m) with a k times n generator matrix and minimum Hamming distance d, a rate-k/n convolutional code over the ring Z4with squared Euclidean free distance at least 2d and a nonrecursive encoder with memory at most m - 1 is constructed. When the generator matrix of B is systematic, the convolutional encoder is systematic, basic, noncatastrophic and minimal. Long codes constructed in this manner are shown to satisfy a Gilbert-Varshnmov bound.

In this correspondence, bounds are derived on the minimum homogeneous distance of the image of a linear block code over the Galois ring${\hbox{GR}}(p^{r},m)$, with respect to any basis of${\hbox{GR}}(p^{r},m)$. These bounds depend on the parameters of${\hbox{GR}}(p^{r},m)$, the minimum Hamming distance of the block code, and the average value of the homogeneous weight applied on the base ring$ {\BBZ }_{p^{r}}$. Examples are given of Galois ring codes that meet these bounds.

Families of binary low-correlation sequences with high nonlinearity (in relation with their Walsh Hadamard transform) are constructed by using the most significant bit of linear recurrence sequences over the ring Zopf2l, for lges3. The engineering motivation is the design of a multiple-code code-division multiple-access (CDMA) scheme with a control of low peak-to-average power ratio (PAPR). Proof techniques combine Galois ring theory (local Weil bound) with spectral analysis over the additive group of Zopf2l. New estimates on the size of weighted degree trace codes are derived. The parameters of the sequences families constructed are shown to lie above a modified Varshamov-Gilbert bound

Following Parts I and II, quasi-cyclic codes of given index are studied as codes over a finite polynomial ring. These latter codes are decomposed by the Chinese Remainder Theorem (CRT), or equivalently the Mattson-Solomon transform, into products of shorter codes over larger alphabets. We characterize and enumerate self-dual one-generator quasi-cyclic codes in that context. We give an algorithm to remove some equivalent codes from that enumeration. A generalization to multigenerator codes is sketched.

The imbalance and the autocorrelation of the binary sequences in the title are explored by combining the local Weil bound with spectral analysis. Recent estimates on these quantities are improved by a factor of order 2/sup l/2/, for large l.

We study binary self-dual codes with a fixed point free automorphism of order three. All binary codes of that type can be obtained by a cubic construction that generalizes Turyn's. We regard such "cubic" codes of length 3/spl lscr/ as codes of length /spl lscr/ over the ring F/sub 2//spl times/F/sub 4/. Classical notions of Type II codes, shadow codes, and weight enumerators are adapted to that ring. Two infinite families of cubic codes are introduced. New extremal binary codes in lengths /spl les/ 66 are constructed by a randomized algorithm. Necessary conditions for the existence of a cubic [72,36,16] Type II code are derived.

We show that there are long binary quasi-cyclic self-dual (either Type I or Type II) codes satisfying the Gilbert-Varshamov bound.

Duadic codes constitute a well-known family of binary cyclic codes. They are generalized in this correspondence to the setting of Abelian codes over the ring Z/sub 2k/. Self-duality, isoduality, and Type II properties are studied.

A new algebraic approach to quasi-cyclic codes is introduced. The key idea is to regard a quasi-cyclic code over a field as a linear code over an auxiliary ring. By the use of the Chinese remainder theorem (CRT), or of the discrete Fourier transform (DFT), that ring can be decomposed into a direct product of fields. That ring decomposition in turn yields a code construction from codes of lower lengths which turns out to be in some cases the celebrated squaring and cubing constructions and in other cases the (u+/spl upsi/|u-/spl upsi/) and Vandermonde constructions. All binary extended quadratic residue codes of length a multiple of three are shown to be attainable by the cubing construction. Quinting and septing constructions are introduced. Other results made possible by the ring decomposition are a characterization of self-dual quasi-cyclic codes, and a trace representation that generalizes that of cyclic codes.

In this paper we propose a method which enables us to construct almost optimal broadcast schemes on an n-dimensional hypercube in the circuit switched, /spl Delta/-port model. In this model, an initiator must inform all the nodes of the network in a sequence of rounds. During a round, vertices communicate along arc-disjoint dipaths. Our construction is based on particular sequences of nested binary codes having the property that each code can inform the next one in a single round. This last property is insured by a flow technique and results about symmetric flow networks. We apply the method to design new schemes improving and generalizing the previous results. Our schemes are the best possible algebraic schemes, and they are optimal in the case n=2/sup p/-1.

Towers of function fields meeting the Drinfeld-Vladut bound with equality were constructed by Gorcal-Stichtenoth (1995, 1996). Modular uniformizations thereof were pointed out by Elkies (1996). We connect this fact to hypergeometric analogs of the arithmetic-geometric mean and related theta series identities discovered by Borweins and Garven.

In this correspondence, we investigate the covering radius of codes over Z/sub 4/ for the Lee and Euclidean distances in relation with those of binary nonlinear codes and lattices obtained by the Gray map and Construction A/sub 4/, respectively. We give several upper and lower bounds on covering radii, including Z/sub 4/-analogs of the sphere-covering bound, the packing radius bound, the Delsarte bound, and the redundancy bound. We show that any Euclidean-optimal Type II code of length 24 has covering radius 8 with respect to the Euclidean distance. We determine the covering radius of the Klemm codes with respect to the Lee distance. We derive lower bounds on the covering radii of the Niemeier lattices.

We study Type IV self-dual codes over the commutative rings of order 4. Gleason-type theorems of Type IV codes and their shadow codes are investigated. A mass formula of Type IV codes over these rings are given. We give a classification of Type TV codes over Z/sub 4/ and F2+uF/sub 2/ for reasonable lengths. We also construct a number of optimal Type TV codes.

The alphabet F/sub 2/+uF/sub 2/ is viewed here as a quotient of the Gaussian integers by the ideal (2). Self-dual F/sub 2/+uF/sub 2/ codes with Lee weights a multiple of 4 are called Type II. They give even unimodular Gaussian lattices by Construction A, while Type I codes yield unimodular Gaussian lattices. Construction B makes it possible to realize the Leech lattice as a Gaussian lattice. There is a Gray map which maps Type II codes into Type II binary codes with a fixed point free involution in their automorphism group. Combinatorial constructions use weighing matrices and strongly regular graphs. Gleason-type theorems for the symmetrized weight enumerators of Type II codes are derived. All self-dual codes are classified for length up to 8. The shadow of the Type I codes yields bounds on the highest minimum Hamming and Lee weights.

Type II Z/sub 4/-codes are introduced as self-dual codes over the integers modulo 4 containing the all-one vector and with Euclidean weights multiple of 8. Their weight enumerators are characterized by means of invariant theory. A notion of extremality for the Euclidean weight is introduced. Their binary images under the Gray map are formally self-dual with even weights. Extended quadratic residue Z/sub 4/-codes are the main example of this family of codes. They are obtained by Hensel lifting of the classical binary quadratic residue codes. Their binary images have good parameters. With every type II Z/sub 4/-code is associated via construction A modulo 4 an even unimodular lattice (type II lattice). In dimension 32, we construct two unimodular lattices of norm 4 with an automorphism of order 31. One of them is the Barnes-Wall lattice BW32.

We study geometrically the domain of linear binary codes and of unrestricted binary codes in the plane (normalized covering radius, normalized minimal distance).

We construct new self-dual and isodual codes over the integers module 4. The binary images of these codes under the Gray map are nonlinear, but formally self-dual. The construction involves Hensel lifting of binary cyclic codes. Quaternary quadratic residue codes are obtained by Hensel lifting of the classical binary quadratic residue codes. Repeated Hensel lifting produces a universal code defined over the 2-adic integers. We investigate the connections between this universal code and the codes defined over Z/sub 4/, the composition of the automorphism group, and the structure of idempotents over Z/sub 4/. We also derive a square root bound on the minimum Lee weight, and explore the connections with the finite Fourier transform. Certain self-dual codes over Z/sub 4/ are shown to determine even unimodular lattices, including the extended quadratic residue code of length q+1, where q/spl equiv/-1(mod8) is a prime power. When q=23, the quaternary Golay code determines the Leech lattice in this way. This is perhaps the simplest construction for this remarkable lattice that is known.>

Tietaivainen (1991) derived an upper bound on the covering radius of codes as a function of the dual distance. This was generalized to the minimum distance, and to Q-polynomial association schemes by Levenshtein and Fazekas. Both proofs use a linear programming approach. In particular, Levenshtein and Fazekas (1990) use linear programming bounds for codes and designs. In this article, proofs relying solely on the orthogonality relations of Krawtchouk (1929), Lloyd, and, more generally, Krawtchouk-adjacent orthogonal polynomials are derived. As a by-product upper bounds on the minimum distance of formally self-dual binary codes are derived.>

The cocycle code of an undirected graph $\Gamma $ is the linear span over ${\text{F}}_2 $ of the characteristic vectors of cutsets. (If $\Gamma $ is complete bipartite, this is the generalized Gale–Berlekamp code.) The natural bijection between the cosets of this code and the switching classes of signed graphs based on $\Gamma $ is used to show that the number of such classes is equal to the number of even-degree subgraphs of $\Gamma $ in both the labeled and unlabeled cases and to improve by coding theory previous bounds on $D( \Gamma )$, the maximum line index of imbalance of signings of $\Gamma $. Bounds on $D( \Gamma )$ are obtained in terms of the genus of $\Gamma $ and on the number of unlabeled even-degree subgraphs in terms of $D( \Gamma )$. Numerous examples are treated, including the “grid” (or “lattice”) graphs that are of interest in the Ising model of spin glasses.

Introduces a new image coding scheme using lattice vector quantization. The proposed method involves two steps: biorthogonal wavelet transform of the image, and lattice vector quantization of wavelet coefficients. In order to obtain a compromise between minimum distortion and bit rate, we must truncate and scale the lattice suitably. To meet this goal, we need to know how many lattice points lie within the truncated area. We investigate the case of Laplacian sources where surfaces of equal probability are spheres for the L(1) metric (pyramids) for arbitrary lattices. We give explicit generating functions for the codebook sizes for the most useful lattices like Z(n), D(n), E(s), wedge(16).

Certain notorious nonlinear binary codes contain more codewords than any known linear code. These include the codes constructed by Nordstrom-Robinson (1967), Kerdock (1972), Preparata (1968), Goethals (1974), and Delsarte-Goethals (1975). It is shown here that all these codes can be very simply constructed as binary images under the Gray map of linear codes over Z/sub 4/, the integers mod 4 (although this requires a slight modification of the Preparata and Goethals codes). The construction implies that all these binary codes are distance invariant. Duality in the Z/sub 4/ domain implies that the binary images have dual weight distributions. The Kerdock and "Preparata" codes are duals over Z/sub 4/-and the Nordstrom-Robinson code is self-dual-which explains why their weight distributions are dual to each other. The Kerdock and "Preparata" codes are Z/sub 4/-analogues of first-order Reed-Muller and extended Hamming codes, respectively. All these codes are extended cyclic codes over Z/sub 4/, which greatly simplifies encoding and decoding. An algebraic hard-decision decoding algorithm is given for the "Preparata" code and a Hadamard-transform soft-decision decoding algorithm for the I(Kerdock code. Binary first- and second-order Reed-Muller codes are also linear over Z/sub 4/, but extended Hamming codes of length n/spl ges/32 and the Golay code are not. Using Z/sub 4/-linearity, a new family of distance regular graphs are constructed on the cosets of the "Preparata" code.>

Upper bounds on the covering radius of codes with a given cardinality and a given dual-distance width are derived. Using an entirely new method, some results published by C. Delorme and P. Sole (1991) for linear codes are generalized, and results are derived for unrestricted codes that have no previous analogue. For some classes of codes, when the parameters lie within certain intervals, results improve asymptotically on the upper bounds published by A.A. Tietavainen (1990) relating the covering radius with the dual distance.>

The image coding scheme involves two steps: biorthogonal wavelet transform of the image and pyramidal lattice vector quantization of wavelet coefficients. In order to obtain a compromise between minimum distortion and bit rate, one must truncate and scale the lattice suitably. To meet this goal, one needs to know how many lattice points lie within the truncated area. The case of Laplacian sources where surfaces of equal probability are spheres for the L/sub 1/ metric (pyramids) for arbitrary lattices is investigated. Explicit generating functions for the codebook sizes of the most useful lattices are given.>

The following problem originated from interconnection network considerations: what is the graphical covering radius of a doubled 2-design in the antipodal double cover of the odd graph 2Ok? In particular, when k is even, we take this design to be a Hadamard design. We obtain upper and lower bounds on this parameter for large values of k. The upper bound is obtained by generalizing the concept of q-covering in Johnson graphs to the graphs 2Ok. We use probabilistic arguments analogous to the Norse bounds of coding theory.

The Norse bounds state that all codes of strength 1 and length n have covering radius at most n/2 and all self-complementary codes of strength 2 and length n have covering radius at most (n- square root n)/2. This is generalized to arbitrary even values of strength, still assuming self-complementarity, and to odd strengths without this hypothesis. The proof techniques used are probabilistic.>

An approximation is given of the distance distribution of a binary code by the binomial distribution with an exponentially decreasing error term. Specifically, the upper bound of the relative error term between the normalized distance distribution of a binary code and the binomial distribution has been asymptotically improved. In particular, the bound becomes exponentially small for large distances in families of codes with small sigma and rate >0.5. The approach used was based on an integral representation of Krawtchouk polynomials. Examples of interest are BCH codes of primitive length, duals of irreducible cyclic codes, and Preparata codes.>

Asymptotic covering properties of families of binary codes are studied. A Gaussian approximation to the weight distribution of translates for codes of high strength is used. From this an upper bound on the covering radius of these codes is deduced. Applications include Reed-Muller codes, quadratic residue codes, and BCH codes. Sufficient conditions for a family of codes to have best possible covering radius (asymptotically perfect codes) are derived.>

The concept of fault-tolerant self-diagnostics is introduced for distributed systems, and it is shown that there exists a performance tradeoff between the complexity of a self-diagnostic algorithm and the level of fault tolerance inherited by the algorithm. Hypercube systems are selected, and it is shown that designing an optimal algorithm for such systems has an equivalent coding theory formulation which belongs to the case of NP-hard problems. An efficient diagnostic scheme is proposed for these systems, and the performance tradeoff of the proposed algorithm, which is based on a combinatorial structure called the Hadamard matrix, is studied. The tradeoff between the fault tolerance and traffic complexity of the proposed diagnostic algorithm for hypercubes of small size is evaluated. An interesting compromise is exhibited for the hypercube with an arbitrary size.>