VI-2类5维q元线性码的汉明重量谱的确定

上 线性码c的汉明重量谱为序列 ,其中,dr是c的r维子码的最小支撑重量。第VI类5维q元线性码的汉明重量谱,按照新的必要条件可以分成6个子类。运用有限射影几何方法研究VI-2类的5维q元线性码的汉明重量谱,确定VI-2类5维q元线性码的几乎所有汉明重量谱。     

Weight hierarchies of extremal non-chain binary codes of dimension4

The weight hierarchy of a linear [n,k;q] code C over GF(q) is the sequence (d₁,d₂,···,d_k ) where d_r is the smallest support of an r-dimensional subcode of C. An [n,k;q] code is extremal nonchain if, for any r and s, where 1⩽rS(D)=d_r, and w_S (E)=d_s. The possible weight hierarchies of such binary codes of dimension 4 are determined     

Stopping Set Analysis of Iterative Row-Column Decoding of Product Codes

In this paper, we introduce stopping sets for iterative row-column decoding of product codes using optimal constituent decoders. When transmitting over the binary erasure channel (BEC), iterative row-column decoding of product codes using optimal constituent decoders will either be successful, or stop in the unique maximum-size stopping set that is contained in the (initial) set of erased positions. Let C_p denote the product code of two binary linear codes C_c and C_r of minimum distances dc and d_r and second generalized Hamming weights d₂(C_c) and d₂(C_r), respectively. We show that the size s_min of the smallest noncode- word stopping set is at least mm(d_rd₂(C_c),d_cd₂(C_r)) > d_rd_c, where the inequality follows from the Griesmer bound. If there are no codewords in C_p with support set S, where S is a stopping set, then S is said to be a noncodeword stopping set. An immediate consequence is that the erasure probability after iterative row-column decoding using optimal constituent decoders of (finite-length) product codes on the BEC, approaches the erasure probability after maximum-likelihood decoding as the channel erasure probability decreases. We also give an explicit formula for the number of noncodeword stopping sets of size s_min, which depends only on the first nonzero coefficient of the constituent (row and column) first and second support weight enumerators, for the case when d₂(C_r) < 2d_r and d₂(C_c) < 2d_c. Finally, as an example, we apply the derived results to the product of two (extended) Hamming codes and two Golay codes.     

Optimal quaternary linear codes of dimension five

Let d_q(n,k) be the maximum possible minimum Hamming distance of a q-ary [n,k,d]-code for given values of n and k. It is proved that d₄ (33,5)=22, d₄(49,5)=34, d₄ (131,5)=96, d₄(142,5)=104, d₄(147,5)=108, d ₄(152,5)=112, d₄(158,5)=116, d₄(176,5)⩾129, d₄(180,5)⩾132, d₄(190,5)⩾140, d₄(195,5)=144, d₄(200,5)=148, d₄(205,5)=152, d₄(216,5)=160, d₄(227,5)=168, d₄(232,5)=172, d₄(237,5)=176, d₄(240,5)=178, d₄(242,5)=180, and d₄(247,5)=184. A survey of the results of recent work on bounds for quaternary linear codes in dimensions four and five is made and a table with lower and upper bounds for d₄(n,5) is presented     

Further results on generalized Hamming weights for Goethals andPreparata codes over Z4

This article contains results on the generalized Hamming weights (GHW) for the Goethals and Preparata codes over Z₄. We give an upper bound on the rth generalized Hamming weights d_r(m,j) for the Goethals code G_m(j) of length 2^m over Z ₄, when m is odd. We also determine d_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_r(m) for the Preparata code of length 2^m over Z₄ when r=3.5 and r=4     

Bounds on the minimum support weights

The minimum support weight, d_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_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_r/d₁ is lower bounded by a number ranging from (q^r-1)/(q^r -q^r-1) to r, depending on R     

On the weight hierarchy of Preparata codes over Z4

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₄, the so called Preparata code over Z₄. We consider the rth generalized Hamming weight d_r(m) of the Preparata code of length 2^m over Z₄. For any m⩾3, d_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_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₄(7)     

The Z4-linearity of Kerdock, Preparata, Goethals, andrelated codes

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₄, 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₄ domain implies that the binary images have dual weight distributions. The Kerdock and “Preparata” codes are duals over Z₄-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₄-analogues of first-order Reed-Muller and extended Hamming codes, respectively. All these codes are extended cyclic codes over Z₄, 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₄ , but extended Hamming codes of length n⩾32 and the Golay code are not. Using Z₄-linearity, a new family of distance regular graphs are constructed on the cosets of the “Preparata” code     

环Fp+vFp上线性码的极小支座谱

基于环F_p+vF_p(v²=v)上线性码的一种直和分解,利用环F_p+vF_p上的线性码的Torsion码,把环F_p+vF_p上的线性码的极小支座谱的确定归结于有限域上的情形;进一步探讨了环F_p+vF_p上的线性码的校验矩阵,利用该校验矩阵确定了环F_p+vF_p上的线性码的对偶码的极小支座谱;最后利用环上的线性码的极小支座谱,探讨了环F_p+vF_p上线性码的最小Hamming距离,并且给出了一个环F_p+vF_p上最小Hamming距离为d的线性码的构造方法,这里p是任一个素数,d是一个正整数.     

环Fp+vFp+v2Fp上线性码的各种重量计数器及其MacWilliams恒等式

首先给出了环R=F_p+vF_p+v²F_p上线性码及其对偶码的结构及其Gray象的性质.定义了环R上线性码的各种重量计数器并讨论了它们之间的关系,特别的,确定了该环上线性码与其对偶码之间关于完全重量计数器的MacWilliams恒等式,利用该恒等式,进一步建立了该环上线性码与其对偶码之间的一种对称形式的MacWilliams恒等式.最后,利用该对称形式的MacWilliams恒等式得到了该环上的Hamming重量计数器和Lee重量计数器的MacWilliams恒等式,利用不同的方法推广了文献[7]中的结果.     

Combinatorial bounds for list decoding

Informally, an error-correcting code has "nice" list-decodability properties if every Hamming ball of "large" radius has a "small" number of codewords in it. We report linear codes with nontrivial list-decodability: i.e., codes of large rate that are nicely list-decodable, and codes of large distance that are not nicely list-decodable. Specifically, on the positive side, we show that there exist codes of rate R and block length n that have at most c codewords in every Hamming ball of radius H^-1(1-R-1/c)·n. This answers the main open question from the work of Elias (1957). This result also has consequences for the construction of concatenated codes of good rate that are list decodable from a large fraction of errors, improving previous results of Guruswami and Sudan (see IEEE Trans. Inform. Theory, vol.45, p.1757-67, Sept. 1999, and Proc. 32nd ACM Symp. Theory of Computing (STOC), Portland, OR, p. 181-190, May 2000) in this vein. Specifically, for every ε > 0, we present a polynomial time constructible asymptotically good family of binary codes of rate Ω(ε⁴) that can be list-decoded in polynomial time from up to a fraction (1/2-ε) of errors, using lists of size O(ε^-2). On the negative side, we show that for every δ and c, there exists τ < δ, c₁ > 0, and an infinite family of linear codes {C_i}_i such that if n_i denotes the block length of C_i, then C _i has minimum distance at least δ · n_i and contains more than c₁ · n_i^c codewords in some Hamming ball of radius τ · n_i. While this result is still far from known bounds on the list-decodability of linear codes, it is the first to bound the "radius for list-decodability by a polynomial-sized list" away from the minimum distance of the code     

A characterization of MMD codes

Let C be a linear [n,k,d]-code over GF(q) with k⩾2. If s=n-k+1-d denotes the defect of C, then by the Griesmer bound, d⩽(s+1)q. Now, for obvious reasons, we are interested in codes of given defect s for which the minimum distance is maximal, i.e., d=(s+1)q. We classify up to formal equivalence all such linear codes over GF(q). Remember that two codes over GF(q) are formally equivalent if they have the same weight distribution. It turns out that for k⩾3 such codes exist only in dimension 3 and 4 with the ternary extended Golay code, the ternary dual Golay code, and the binary even-weight code as exceptions. In dimension 4 they are related to ovoids in PG(3,q) except the binary extended Hamming code, and in dimension 3 to maximal arcs in PG(2,q)     

Negacyclic codes of length 2/sup s/ over galois rings

Codes over the ring of integers modulo 4 have been studied by many researchers. Negacyclic codes such that the length n of the code is odd have been characterized over the alphabet Zopf₄, and furthermore, have been generalized to the case of the alphabet being a finite commutative chain ring. In this paper, we investigate negacyclic codes of length 2^s over Galois rings. The structure of negacyclic codes of length 2^s over the Galois rings GR(2^a,m), as well as that of their duals, are completely obtained. The Hamming distances of negacyclic codes over GR(2^a,m) in general, and over Zopf₂ ^a in particular are studied. Among other more general results, the Hamming distances of all negacyclic codes over Zopf₂ ^a of length 4,8, and 16 are given. The weight distributions of such negacyclic codes are also discussed     

A New Upper Bound on the Block Error Probability After Decoding Over the Erasure Channel

Motivated by cryptographic applications, we derive a new upper bound on the block error probability after decoding over the erasure channel. The bound works for all linear codes and is in terms of the generalized Hamming weights. It turns out to be quite useful for Reed-Muller codes for which all the generalized Hamming weights are known whereas the full weight distribution is only partially known. For these codes, the error probability is related to the cryptographic notion of algebraic immunity. We use our bound to show that the algebraic immunity of a random balanced m-variable Boolean function is of order ^m/₂(1-o(1)) with probability tending to 1 as m goes to infinity     

Translates of linear codes over Z4

We give a method to compute the complete weight distribution of translates of linear codes over Z₄. The method follows known ideas that have already been used successfully by others for Hamming weight distributions. For the particular case of quaternary Preparata codes, we obtain that the number of distinct complete weights for the dual Preparata codes and the number of distinct complete coset weight enumerators for the Preparata codes are both equal to ten, independent of the code length     

Second-harmonic generation properties of2-amino-5-nitropyridinium-dihydrogenarsenate and -dihydrogenphosphateorganic-inorganic crystals

We present a comparative study of the linear and nonlinear optical properties of two isomorphous organic-inorganic crystals: the 2-amino 5-nitropyridinium-dihydrogenphosphate (2A5NPDP) and -dihydrogenarsenate (2A5NPDAs). We determine accurate equations for the dispersion in wavelength of their principal refractive indices from direct prism measurements and from angular noncritically phase-matched second-harmonic generation (SHG) experiments. We deduce the quadratic nonlinear coefficients d₁₅ and d₂₄ of each compound from the phase-matched conversion efficiency of SHG experiments and find that they are close to those of KTiOPO₄     

Improved coding techniques for preceded partial-response channels

A coset of a convolutional code may be used to generate a zero-run length limited trellis code for a 1-D partial-response channel. The free squared Euclidean distance, d_free², at the channel output is lower bounded by the free Hamming distance of the convolutional code. The lower bound suggests the use of a convolutional code with maximal free Hamming distance, d_max(R,N), for given rate R and number of decoder states N. In this paper we present cosets of convolutional codes that generate trellis codes with d_free ²>d_max(R,N) for rates 1/5⩽R⩽7/9 and (d _free²=d_max(R,N) for R=13/16,29/32,61/64, The tabulated convolutional codes with R⩽7/9 were not optimized for Hamming distance. Instead, a computer search was used to determine cosets of convolutional codes that exploit the memory of the 1-D channel to increase d_free² at the channel output. The search was limited by only considering cosets with certain structural properties. The R⩾13/16 codes were obtained using a new construction technique for convolutional codes with free Hamming distance 4. Newly developed bounds on the maximum zero-run lengths of cosets were used to ensure a short maximum run length at the 1-D channel output     

Optimal quinary cyclic codes with minimum distance four

Cyclic codes are an extremely important subclass of linear codes.They are widely used in the communication systems and data storage systems because they have efficient encoding and decoding algorithm.Until now,how to construct the optimal ternary cyclic codes has received a lot of attention and much progress has been made.However,there is less research about the optimal quinary cyclic codes.Firstly,an efficient method to determine if cyclic codes C_(1,e,t)were optimal codes was obtained.Secondly,based on the proposed method,when the equation e=5_k+1 or e=5_m?2hold,the theorem that the cyclic codes C_(1,e,t)were optimal quinary cyclic codes was proved.In addition,perfect nonlinear monomials were used to construct optimal quinary cyclic codes with parameters[5_m?1,5_m?2m?2,4]optimal quinary cyclic codes over $F_{5^m}$.     

On the second generalized Hamming weight of the dual code of adouble-error-correcting binary BCH code

The generalized Hamming weight of a linear code is a new notion of higher dimensional Hamming weights. Let C be an [n,k] linear code and D be a subcode. The support of D is the cardinality of the set of not-always-zero bit positions of D. The rth generalized Hamming weight of C, denoted by d_r(C), is defined as the minimum support of an r-dimensional subcode of C. It was shown by Wei (1991) that the generalized Hamming weight hierarchy of a linear code completely characterizes the performance of the code on the type II wire-tap channel defined by Ozarow and Wyner (1984). In the present paper the second generalized Hamming weight of the dual code of a double-error-correcting BCH code is derived and the authors prove that except for m=4, the second generalized Hamming weight of [2^m-1, 2m]-dual BCH codes achieves the Griesmer bound