Upper Bounds on the Dual Distance of BCH(255, k)

To obtain upper bounds on the distance of a binary linear code, many probabilistic algorithms have been proposed. The author presents a general variation to these algorithms, specific for cyclic codes, which is shown to be an improvement. As an example, the author optimizes Brouwer's algorithm to find the best upper bounds on the dual distance of BCH[255,k,d].     

Nonlinear codes with asymptotic parameters better than the Gilbert-Varshamov and the Xing Bounds

In this paper, we show that the Gilbert-Varshamov and the Xing bounds can be improved significantly around two points where these two bounds intersect by nonlinear codes from algebraic curves over finite fields.     

基于有限集[N]上相交关系构作的二元等重码

对于自然数s,r,k,N,0＜s≤r＜k≤N,根据基集[N]={1,2,…,N}上两个不同子集的相交关系构作了一个关联矩阵,证明了这个关联矩阵是一个二元等重码,给出了它成为最佳等重码的条件,研究了它的检错性.     

Exact Bounds on the Sizes of Covering Codes

A code c is a covering code of X with radius r if every element of X is within Hamming distance r from at least one codeword from c. The minimum size of such a c is denoted by c _r(X). Answering a question of Hämäläinen et al. [10], we show further connections between Turán theory and constant weight covering codes. Our main tool is the theory of supersaturated hypergraphs. In particular, for n > n ₀(r) we give the exact minimum number of Hamming balls of radius r required to cover a Hamming ball of radius r + 2 in {0, 1}ⁿ. We prove that c _r(B _n(0, r + 2)) = _{1 i r + 1} ( ^{(n + i – 1) / (r + 1) 2}) + n / (r + 1) and that the centers of the covering balls B(x, r) can be obtained by taking all pairs in the parts of an (r + 1)-partition of the n-set and by taking the singletons in one of the parts.     

Upper and Lower Bounds on Maximum Nonlinearity of n-input m-output Boolean Function

The paper presents lower and upper bounds on the maximumnonlinearity for an n-input m-output Booleanfunction. We show a systematic construction method for a highlynonlinear Boolean function based on binary linear codes whichcontain the first order Reed-Muller code as a subcode. We alsopresent a method to prove the nonexistence of some nonlinearBoolean functions by using nonexistence results on binary linearcodes. Such construction and nonexistence results can be regardedas lower and upper bounds on the maximum nonlinearity. For somen and m, these bounds are tighter than theconventional bounds. The techniques employed here indicate astrong connection between binary linear codes and nonlinear n-input m-output Boolean functions.     

Bounds in the Lee metric and optimal codes

In this paper we investigate known Singleton-like bounds in the Lee metric and characterize their extremal codes, which turn out to be very few. We then focus on Plotkin-like bounds in the Lee metric and present a new bound that extends and refines a previously known, and out-performs it in the case of non-free codes. We then compute the density of extremal codes with regard to the new bound. Finally we fill a gap in the characterization of Lee-equidistant codes.     

一种OLS/OOC二维光正交码的构造与性能分析

利用不同的序列作为波长跳频序列和时间扩频序列可以构造出不同的二维光正交码在众多文献中已有所报道.在经过正交拉丁方(OLS)与跳频序列的相关性研究之后.做了以下主要工作:首先,将正交拉丁方(OLS)序列作为波长跳频序列,结合一维时间扩频序列(OOC),构造了一种OLS/OOC二维光正交码.然后,本文对构造的OLS/OOC进行了多种性能仿真和分析.相对于PC/OOC、OCFHC/OOC等二维光正交码而言,OLS/OOC的波长数并不局限于素数,更能充分利用MWOCDMA系统中的有效波长数.仿真和分析表明:码字具有很好的相关性能,码字容量直逼理论极限,为一种渐近最优二维光正交码.     

Minihypers and Linear Codes Meeting the Griesmer Bound: Improvements to Results of Hamada, Helleseth and Maekawa

This article improves results of Hamada, Helleseth and Maekawa on minihypers in projective spaces and linear codes meeting the Griesmer bound.In [10,12],it was shown that any -minihyper, with , where , is the disjoint union of points, lines,..., -dimensional subspaces. For q large, we improve on this result by increasing the upper bound on non-square, to non-square, square, , and (4) for square, p prime, p<3, to . In the case q non-square, the conclusion is the same as written above; the minihyper is the disjoint union of subspaces. When q is square however, the minihyper is either the disjoint union of subspaces, or the disjoint union of subspaces and one subgeometry . For the coding-theoretical problem, our results classify the corresponding codes meeting the Griesmer bound.     

A Necessary and Sufficient Condition for the Existence of Some Ternary [n, k, d] Codes Meeting the Greismer Bound

Let k and d be any integers such that k 4 and . Then there exist two integers and in {0,1,2} such that . The purpose of this paper is to prove that (1) in the case k 5 and (,) = (0,1), there exists a ternary code meeting the Griesmer bound if and only if and (2) in the case k 4 and (,) = (0,2) or (1,1), there is no ternary code meeting the Griesmer bound for any integers k and d and (3) in the case k 5 and , there is no projective ternary code for any integers k and such that 1k-3, where and for any integer i 0. In the special case k=6, it follows from (1) that there is no ternary linear code with parameters [233,6,154] , [234,6,155] or [237,6,157] which are new results.     

Codes over \mathbb{F}_3 + u\mathbb{F}_3 and Improvements to the Bounds on Ternary Linear Codes

New ternary linear codeswith parameters [208, 8, 127], [150, 10, 85],[160, 10, 91], [170, 10, 97], [180,10, 103], and [190, 10, 110], are found whichimprove the known lower bound on the maximum possible minimumHamming distance. These codes are constructed from codes over via a Gray map.     

Characterizing the Hermitian and Ree Unitals on 28 Points

We prove a conjecture of Brouwer, namely that a 2-(28,4,1) design has 2–rank at least 19, with equality occuring if and only if the design is the Ree unital. We give a similar characterization of the Hermitian unital.     

Sets of disjoint snakes based on a Reed-Muller code and covering the hypercube

A snake-in-the-box code (or snake) of word length n is a simple circuit in an n-dimensional cube Q _n , with the additional property that any two non-neighboring words in the circuit differ in at least two positions. To construct such snakes a straightforward, non-recursive method is developed based on special linear codes with minimum distance 4. An extension of this method is used for the construction of covers of Q _n consisting of 2 ^m-1 vertex-disjoint snakes, for 2 ^m-1 < n ≤ 2 ^m . These covers turn out to have a symmetry group of order 2 ^m .      

二元叠加码M_q(n,k,d)码的平均汉明距离和均方差

根据二元叠加码(Binary Superimposed Code)M_q(n,k,d)的定义及有限域F_q上n维向量空间的k维子空间的维数性质定义了一个高斯组合函数,利用这个组合函数研究了M_q(n,k,d)码的平均汉明(Hamming)距离和它的均方差问题,给出了计算公式.     

Some Upper Bounds on the Covering Radii of Linear Codes Over Fq and Their Applications

We show that the covering radius R of an [n,k,d] code over F_q is bounded above by R n-n _q(k, d/q). We strengthen this bound when R d and find conditions under which equality holds.As applications of this and other bounds, we show that all binary linear codes of lengths up to 15, or codimension up to 9, are normal. We also establish the normality of most codes of length 16 and many of codimension 10. These results have applications in the construction of codes that attain t[n,k,/it>], the smallest covering radius of any binary linear [n,k].We also prove some new results on the amalgamated direct sum (ADS) construction of Graham and Sloane. We find new conditions assuring normality of the ADS; covering radius 1 less than previously guaranteed for ADS of codes with even norms; good covering codes as ADS without the hypothesis of normality, from concepts p- stable and s- stable; codes with best known covering radii as ADS of two, often cyclic, codes (thus retaining structure so as to be suitable for practical applications).     

Lower Bounds on the Size of Maximum Independent Sets and Matchings in Hypergraphs of Rank Three

In this paper, we study lower bounds on the size of a maximum independent set and a maximum matching in a hypergraph of rank three. The rank in a hypergraph is the size of a maximum edge in the hypergraph. A hypergraph is simple if no two edges contain exactly the same vertices. Let H be a hypergraph and let and be the size of a maximum independent set and a maximum matching, respectively, in H, where a set of vertices in H is independent (also called strongly independent in the literature) if no two vertices in the set belong to a common edge. Let H be a hypergraph of rank at most three and maximum degree at most three. We show that with equality if and only if H is the Fano plane. In fact, we show that if H is connected and different from the Fano plane, then and we characterize the hypergraphs achieving equality in this bound. Using this result, we show that that if H is a simple connected 3‐uniform hypergraph of order at least 8 and with maximum degree at most three, then and there is a connected 3‐uniform hypergraph H of order 19 achieving this lower bound. Finally, we show that if H is a connected hypergraph of rank at most three that is not a complete hypergraph on vertices, where denotes the maximum degree in H, then and this bound is asymptotically best possible. © 2012 Wiley Periodicals, Inc. J. Graph Theory     

Order Structure on the Algebra of Permutations and of Planar Binary Trees

Let X _n be either the symmetric group on n letters, the set of planar binary n-trees or the set of vertices of the (n – 1)-dimensional cube. In each case there exists a graded associative product on _n0 K[X _n]. We prove that it can be described explicitly by using the weak Bruhat order on S _n, the left-to-right order on planar trees, the lexicographic order in the cube case.     

New upper bounds for nonbinary codes based on the Terwilliger algebra and semidefinite programming

We give a new upper bound on the maximum size Aq(n,d) of a code of word length n and minimum Hamming distance at least d over the alphabet of q?3 letters. By block-diagonalizing the Terwilliger algebra of the nonbinary Hamming scheme, the bound can be calculated in time polynomial in n using semidefinite programming. For q=3,4,5 this gives several improved upper bounds for concrete values of n and d. This work builds upon previous results of Schrijver [A. Schrijver, New code upper bounds from the Terwilliger algebra and semidefinite programming, IEEE Trans. Inform. Theory 51 (2005) 2859-2866] on the Terwilliger algebra of the binary Hamming scheme.