Error-Correcting Codes over an Alphabet of Four Elements

The problem of finding the values of A_q(n,d)—the maximum size of a code of length n and minimum distance d over an alphabet of q elements—is considered. Upper and lower bounds on A₄(n,d) are presented and some values of this function are settled. A table of best known bounds on A₄(n,d) is given for n 12. When q M < 2q, all parameters for which A_q(n,d) = M are determined.     

Fq-linear Cyclic Codes over $$ F{_q^m}$$ : D FT Approach

Codes over that are closed under addition, and multiplication with elements from F_q are called F_q-linear codes over . For m 1, this class of codes is a subclass of nonlinear codes. Among F_q-linear codes, we consider only cyclic codes and call them F_q-linear cyclic codes (F_q LC codes) over The class of F_q LC codes includes as special cases (i) group cyclic codes over elementary abelian groups (q=p, a prime), (ii) subspace subcodes of Reed–Solomon codes (n=q^m–1) studied by Hattori, McEliece and Solomon, (iii) linear cyclic codes over F_q (m=1) and (iv) twisted BCH codes. Moreover, with respect to any particular F_q-basis of , any F_qLC code over can be viewed as an m-quasi-cyclic code of length mn over F_q. In this correspondence, we obtain transform domain characterization of F_q LC codes, using Discrete Fourier Transform (DFT) over an extension field of The characterization is in terms of any decomposition of the code into certain subcodes and linearized polynomials over . We show how one can use this transform domain characterization to obtain a minimum distance bound for the corresponding quasi-cyclic code. We also prove nonexistence of self dual F_q LC codes and self dual quasi-cyclic codes of certain parameters using the transform domain characterization.AMS classification 94B05     

An Extension Theorem for Linear Codes

One of the first results one meets in coding theory is that a binary linear [n,k,d] code, whose minimum distance is odd, can be extended to an [n + 1, k, d + 1] code. This is one of the few elementary results about binary codes which does not obviously generalise to q-ary codes. The aim of this paper is to give a simple sufficient condition for a q-ary [n, k, d] code to be extendable to an [n + 1, k, d + 1] code. Applications will be given to the construction and classification of good codes, to proving the non- existence of certain codes, and also an application in finite geometry.     

Subcodes of the Projective Generalized Reed-Muller Codes Spanned by Minimum-Weight Vectors

We use methods of Mortimer [19] to examine the subcodes spanned by minimum-weight vectors of the projective generalized Reed-Muller codes and their duals. These methods provide a proof, alternative to a dimension argument, that neither the projective generalized Reed-Muller code of order r and of length over the finite field F _q of prime-power order q, nor its dual, is spanned by its minimum-weight vectors for 0<r<m–1 unless q is prime. The methods of proof are the projective analogue of those developed in [17], and show that the codes spanned by the minimum-weight vectors are spanned over F _q by monomial functions in the m variables. We examine the same question for the subfield subcodes and their duals, and make a conjecture for the generators of the dual of the binary subfield subcode when the order r of the code is 1.     

On Intersection Problem for Perfect Binary Codes

The main result is that to any even integer q in the interval 0 ≤ q ≤ 2^{n+1-2log(n+1)}, there are two perfect codes C₁ and C₂ of length n = 2^m − 1, m ≥ 4, such that |C₁ ∩ C₂| = q.     

Self-dual 2-quasi-cyclic codes and dihedral codes

We characterize the structure of 2-quasi-cyclic codes over a finite field F by the so-called Goursat Lemma. With the characterization, we exhibit a necessary and sufficient condition for a 2-quasi-cyclic code being a dihedral code. And we obtain a necessary and sufficient condition for a self-dual 2-quasi-cyclic code being a dihedral code (if $\mathrm{char}F=2$), or a consta-dihedral code (if $\mathrm{char}F\ne 2$). As a consequence, any self-dual 2-quasi-cyclic code generated by one element must be (consta-)dihedral. In particular, any self-dual double circulant code must be (consta-)dihedral. We also obtain necessary and sufficient conditions under which the three classes (the self-dual double circulant codes, the self-dual 2-quasi-cyclic codes, and the self-dual (consta-)dihedral codes) of codes coincide with each other.     

Negacyclic duadic codes

This paper extends the concepts from cyclic duadic codes to negacyclic codes over F_q (q an odd prime power) of oddly even length. Generalizations of defining sets, multipliers, splittings, even-like and odd-like codes are given. Necessary and sufficient conditions are given for the existence of self-dual negacyclic codes over F_q and the existence of splittings of 2N, where N is odd. Other negacyclic codes can be extended by two coordinates in a way to create self-dual codes with familiar parameters.     

The Classification of Some Perfect Codes

Perfect 1-error correcting codes C in Z ₂ ⁿ , where n=2 ^m–1, are considered. Let ; denote the linear span of the words of C and let the rank of C be the dimension of the vector space . It is shown that if the rank of C is n–m+2 then C is equivalent to a code given by a construction of Phelps. These codes are, in case of rank n–m+2, described by a Hamming code H and a set of MDS-codes D _h , h H, over an alphabet with four symbols. The case of rank n–m+1 is much simpler: Any such code is a Vasil'ev code.     

特征2的有限域中一些特殊元素的存在性(II)

设q=2s.s,n为正整数,Fqn为qn元素的有限域.在本文中,我们考虑Fqn中一些特殊元素的存在性.主要结果是:当下面的条件之一成立时,在Fqn中存在ξ使得ξ和ξ+ξ-1都是本原元并且ξ+ξ-1还是一个正规元:1.当n|(q-1)时,n37,s>6,或者2.当n|■(q-1)时,n≥34,s>6.进一步,如果n是奇数,则当下列条件之一成立时,存在ξ∈Fqn使得ξ和ξ+ξ-1都是Fqn的本原正规元:1.当n|(q-1)时,n≥257,s>9,或者2.当n■(q-1)时,n≥43,s≥9.     

Maximum IPP Codes of Length 3

Let Q be an alphabet with q elements. For any code C over Q of length n and for any two codewords a = (a ₁, . . . , a _n ) and b = (b ₁, . . . , b _n ) in C, let ${D({\bf a, b}) = \{(x_1, . . . , x_n) \in {Q^n} : {x_i} \in \{a_i, b_i\}\,{\rm for}\,1 \leq i \leq n\}}Let Q be an alphabet with q elements. For any code C over Q of length n and for any two codewords a = (a ₁, . . . , a _n ) and b = (b ₁, . . . , b _n ) in C, let D(a, b) = {(x₁, . . . , x_n) ? Qⁿ : x_i ? {a_i, b_i} for 1 ￡ i ￡ n}{D({\bf a, b}) = \{(x_1, . . . , x_n) \in {Q^n} : {x_i} \in \{a_i, b_i\}\,{\rm for}\,1 \leq i \leq n\}}. Let C^* = è_{a, b ? C}D(a, b){C^* = {{\bigcup}_{\rm {a,\,b}\in{C}}}D({\bf a, b})}. The code C is said to have the identifiable parent property (IPP) if, for any x ? C^*{{\rm {\bf x}} \in C^*}, ?_{x ? D(a, b)}{a, b} 1 ?{{\bigcap}_{{\rm x}{\in}D({\rm a,\,b})}\{{\bf a, b}\}\neq \emptyset} . Codes with the IPP were introduced by Hollmann et al [J. Combin. Theory Ser. A 82 (1998) 21–133]. Let F(n, q) = max{|C|: C is a q-ary code of length n with the IPP}.T? and Safavi-Naini [SIAM J. Discrete Math. 17 (2004) 548–570] showed that 3q + 6 - 6 é?{q+1}ù ￡ F(3, q) ￡ 3q + 6 - é6 ?{q+1}ù{3q + 6 - 6 \lceil\sqrt{q+1}\rceil \leq F(3, q) \leq 3q + 6 - \lceil 6 \sqrt{q+1}\rceil}, and determined F (3, q) precisely when q ≤ 48 or when q can be expressed as r ² + 2r or r ² + 3r +2 for r ≥ 2. In this paper, we establish a precise formula of F(3, q) for q ≥ 24. Moreover, we construct IPP codes of size F(3, q) for q ≥ 24 and show that, for any such code C and any x ? C^*{{\rm {\bf x}} \in C^*}, one can find, in constant time, a ? C{{\rm {\bf a}} \in C} such that if x ? D (c, d){{\rm {\bf x}} \in D ({\bf c, d})} then a ? {c, d}{{\rm {\bf a}} \in \{{\rm {\bf c, d}}\}}.     

Some constructions of linearly optimal group codes

We continue here the research on (quasi)group codes over (quasi)group rings. We give some constructions of [n,n-3,3]_q-codes over F_q for n=2q and n=3q. These codes are linearly optimal, i.e. have maximal dimension among linear codes having a given length and distance. Although codes with such parameters are known, our main results state that we can construct such codes as (left) group codes. In the paper we use a construction of Reed-Solomon codes as ideals of the group ring F_qG where G is an elementary abelian group of order q.     

On the Minimum Size of Some Minihypers and Related Linear Codes

We denote by m_r,q(s) the minimum value of f for which an {f, _r-2+s ; r,q }-minihyper exists for r 3, 1 s q–1, where _j=(q^j+1–1)/(q–1). It is proved that m_3,q(s)=₁(₁+s) for many cases (e.g., for all q 4 when ) and that m_r,q(s) _r-1+s₁+q for 1 s q – 1,~q 3,~r 4. The nonexistence of some [n,k,n+s–q^k-2]_q codes attaining the Griesmer bound is given as an application.AMS classification: 94B27, 94B05, 51E22, 51E21     

Improved Bounds for Ternary Linear Codes of Dimension 8 Using Tabu Search

In this paper, new codes of dimension 8 are presented which give improved bounds on the maximum possible minimum distance of ternary linear codes. These codes belong to the class of quasi-twisted (QT) codes, and have been constructed using a stochastic optimization algorithm, tabu search. Twenty three codes are given which improve or establish the bounds for ternary codes. In addition, a table of upper and lower bounds for d ₃(n, 8) is presented for n 200.     

有限酉群作用下子空间轨道按和生成的格

设F_q2⁽ⁿ⁾是 F_q2上的 n 维行向量空间, U_n( F_q2)是 F_q2上的 n 阶酉群. 设M(m, r; n)是U_n(F_q2}作用下的一个子空间轨道, L(m, r; n)是 M (m, r; n)中子空间的和生成的集合.该文讨论了各个轨道生成的集合L(m, r; n)之间的包含关系, 给出了一个子空间是属于给定的由M(m, r; n)生成的集合L(m, r, n)中的一个元素的条件, 以及L}(m, r; n)做成几何格的条件.     

Enumeration of inequivalent irreducible Goppa codes

We consider irreducible Goppa codes over F_q of length qⁿ defined by polynomials of degree r, where q is a prime power and n,r are arbitrary positive integers. We obtain an upper bound on the number of such codes.     

Quasideterminant Characterization of MDS Group Codes over Abelian Groups

A group code defined over a group G is a subset of Gⁿ which forms a group under componentwise group operation. The well known matrix characterization of MDS (Maximum Distance Separable) linear codes over finite fields is generalized to MDS group codes over abelian groups, using the notion of quasideterminants defined for matrices over non-commutative rings.     

Spreads, arcs, and multiple wavelength codes

We present several new families of multiple wavelength (2-dimensional) optical orthogonal codes (2D-OOCs) with ideal auto-correlation λ_a=0 (codes with at most one pulse per wavelength). We also provide a construction which yields multiple weight codes. All of our constructions produce codes that are either optimal with respect to the Johnson bound (J-optimal), or are asymptotically optimal and maximal. The constructions are based on certain pointsets in finite projective spaces of dimension k over GF(q) denoted PG(k,q).     

Modular Counting of Rational Points over Finite Fields

Let F_q be the finite field of q elements, where q = p^h. Let f(x) be a polynomial over F_q in n variables with m nonzero terms. Let N(f) denote the number of solutions of f(x) = 0 with coordinates in F_q. In this paper we give a deterministic algorithm which computes the reduction of N(f) modulo p^b in O(n(8m)p^(h+b)p) bit operations. This is singly exponential in each of the parameters {h, b, p}, answering affirmatively an open problem proposed by Gopalan, Guruswami, and Lipton.