Lower bounds on the minimum average distance of binary codes

Let β(n,M) denote the minimum average Hamming distance of a binary code of length n and cardinality M. In this paper we consider lower bounds on β(n,M). All the known lower bounds on β(n,M) are useful when M is at least of size about 2ⁿ⁻¹/n. We derive new lower bounds which give good estimations when size of M is about n. These bounds are obtained using a linear programming approach. In particular, it is proved that lim_n→∞β(n,2n)=5/2. We also give a new recursive inequality for β(n,M).     

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.     

An improvement of the Griesmer bound for some small minimum distances

In this paper we give some lower and upper bounds for the smallest length n(k, d) of a binary linear code with dimension k and minimum distance d. The lower bounds improve the known ones for small d. In the last section we summarize what we know about n(8, d).     

Optimal doubly constant weight codes

A doubly constant weight code is a binary code of length n₁ + n₂, with constant weight w₁ + w₂, such that the weight of a codeword in the first n₁ coordinates is w₁. Such codes have applications in obtaining bounds on the sizes of constant weight codes with given minimum distance. Lower and upper bounds on the sizes of such codes are derived. In particular, we show tight connections between optimal codes and some known designs such as Howell designs, Kirkman squares, orthogonal arrays, Steiner systems, and large sets of Steiner systems. These optimal codes are natural generalization of Steiner systems and they are also called doubly Steiner systems. © 2007 Wiley Periodicals, Inc. J Combin Designs 16: 137–151, 2008     

Constructing permutation arrays from groups

Let M(n, d) be the maximum size of a permutation array on n symbols with pairwise Hamming distance at least d. We use various combinatorial, algebraic, and computational methods to improve lower bounds for M(n, d). We compute the Hamming distances of affine semilinear groups and projective semilinear groups, and unions of cosets of AGL(1, q) and PGL(2, q) with Frobenius maps to obtain new, improved lower bounds for M(n, d). We give new randomized algorithms. We give better lower bounds for M(n, d) also using new theorems concerning the contraction operation. For example, we prove a quadratic lower bound for \(M(n,n-2)\) for all \(n\equiv 2 \pmod 3\) such that \(n+1\) is a prime power.     

A geometric approach to finding new lower bounds of A(n, d, w)

Certain classes of binary constant weight codes can be represented geometrically using linear structures in Euclidean space. The geometric treatment is concerned mostly with codes with minimum distance 2(w ? 1), that is, where any two codewords coincide in at most one entry; an algebraic generalization of parts of the theory also applies to some codes without this property. The presented theorems lead to several improvements of the tables of lower bounds on A(n, d, w) maintained by E. M. Rains and N. J. A. Sloane, and the ones recently published by D. H. Smith, L. A. Hughes and S. Perkins. Some of these new codes can be proven optimal.     

Code constructions and existence bounds for relative generalized Hamming weight

The relative generalized Hamming weight (RGHW) of a linear code C and a subcode C ¹ is an extension of generalized Hamming weight. The concept was firstly used to protect messages from an adversary in the wiretap channel of type II with illegitimate parties. It was also applied to the wiretap network II for secrecy control of network coding and to trellis-based decoding algorithms for complexity estimation. For RGHW, bounds and code constructions are two related issues. Upper bounds on RGHW show the possible optimality for the applications, and code constructions meeting upper bounds are for designing optimal schemes. In this article, we show indirect and direct code constructions for known upper bounds on RGHW. When upper bounds are not tight or constructions are hard to find, we provide two asymptotically equivalent existence bounds about good code pairs for designing suboptimal schemes. Particularly, most code pairs (C, C ¹) are good when the length n of C is sufficiently large, the dimension k of C is proportional to n and other parameters are fixed. Moreover, the first existence bound yields an implicit lower bound on RGHW, and the asymptotic form of this existence bound generalizes the usual asymptotic Gilbert–Varshamov bound.     

On the binary codes with parameters of triply-shortened 1-perfect codes

We study properties of binary codes with parameters close to the parameters of 1-perfect codes. An arbitrary binary (n?=?2 ^m ? 3, 2 ^n-m-1, 4) code C, i.e., a code with parameters of a triply-shortened extended Hamming code, is a cell of an equitable partition of the n-cube into six cells. An arbitrary binary (n?=?2 ^m ? 4, 2 ^n-m , 3) code D, i.e., a code with parameters of a triply-shortened Hamming code, is a cell of an equitable family (but not a partition) with six cells. As a corollary, the codes C and D are completely semiregular; i.e., the weight distribution of such codes depends only on the minimal and maximal codeword weights and the code parameters. Moreover, if D is self-complementary, then it is completely regular. As an intermediate result, we prove, in terms of distance distributions, a general criterion for a partition of the vertices of a graph (from rather general class of graphs, including the distance-regular graphs) to be equitable.     

Total palindrome complexity of finite words

The palindrome complexity function pal_w of a word w attaches to each n∈N the number of palindromes (factors equal to their mirror images) of length n contained in w. The number of all the nonempty palindromes in a finite word is called the total palindrome complexity of that word. We present exact bounds for the total palindrome complexity and construct words which have any palindrome complexity between these bounds, for binary alphabets as well as for alphabets with the cardinal greater than 2. Denoting by M_q(n) the average number of palindromes in all words of length n over an alphabet with q letters, we present an upper bound for M_q(n) and prove that the limit of M_q(n)/n is 0. A more elaborate estimation leads to .     

Coding with injections

A permutation code of length n and minimum distance d is a set Γ of permutations from some fixed set of n symbols such that the Hamming distance between any distinct ${u,v \in \Gamma}$ is at least d. As a generalization, we introduce the problem of packing injections from an m-set, m ≤?n, sometimes called m-arrangements, relative to Hamming distance. We offer some preliminary coding-theoretic bounds, a few design-theoretic connections, and a short discussion on possible applications.     

New bounds of permutation codes under Hamming metric and Kendall’s $$\tau $$-metric

Permutation codes are widely studied objects due to their numerous applications in various areas, such as power line communications, block ciphers, and the rank modulation scheme for flash memories. Several kinds of metrics are considered for permutation codes according to their specific applications. This paper concerns some improvements on the bounds of permutation codes under Hamming metric and Kendall’s \(\tau \)-metric respectively, using mainly a graph coloring approach. Specifically, under Hamming metric, we improve the Gilbert–Varshamov bound asymptotically by a factor n, when the minimum Hamming distance d is fixed and the code length n goes to infinity. Under Kendall’s \(\tau \)-metric, we narrow the gap between the known lower bounds and upper bounds. Besides, we also obtain some sporadic results under Kendall’s \(\tau \)-metric for small parameters.     

Optimal constant weight covering codes and nonuniform group divisible 3-designs with block size four

Let K _q (n, w, t, d) be the minimum size of a code over Z _q of length n, constant weight w, such that every word with weight t is within Hamming distance d of at least one codeword. In this article, we determine K _q (n, 4, 3, 1) for all n ≥ 4, q = 3, 4 or q = 2 ^m  + 1 with m ≥ 2, leaving the only case (q, n) = (3, 5) in doubt. Our construction method is mainly based on the auxiliary designs, H-frames, which play a crucial role in the recursive constructions of group divisible 3-designs similar to that of candelabra systems in the constructions of 3-wise balanced designs. As an application of this approach, several new infinite classes of nonuniform group divisible 3-designs with block size four are also constructed.     

Weighted inverse maximum perfect matching problems under the Hamming distance

Given an undirected network G(V, E, c) and a perfect matching M ⁰, the inverse maximum perfect matching problem is to modify the cost vector as little as possible such that the given perfect matching M ⁰ can form a maximum perfect matching. The modification can be measured by different norms. In this paper, we consider the weighted inverse maximum perfect matching problems under the Hamming distance, where we use the weighted Hamming distance to measure the modification of the edges. We consider both of the sum-type and the bottleneck-type problems. For the general case of the sum-type case, we show it is NP-hard. For the bottleneck-type, we present a strongly polynomial algorithm which can be done in O(m · n ³).     

Constructions for Permutation Codes in Powerline Communications

A permutation array (or code) of length n and distance d is a set Γ of permutations from some fixed set of n symbols such that the Hamming distance between each distinct x, y ∈ Γ is at least d. One motivation for coding with permutations is powerline communication. After summarizing known results, it is shown here that certain families of polynomials over finite fields give rise to permutation arrays. Additionally, several new computational constructions are given, often making use of automorphism groups. Finally, a recursive construction for permutation arrays is presented, using and motivating the more general notion of codes with constant weight composition.     

On the Generalized Weights of a Class of Trace Codes

We build a class of codes using hermitian forms and the functional trace code. Then we give a general expression of the rth minimum distance of our code and compute general bounds for the weight hierarchy by using exponential sums. We also get the minimum distance and calculate the rth generalized Hamming weight d_r in some special cases.     

Good equidistant codes constructed from certain combinatorial designs

An (n,M,d;q) code is called equidistant code if the Hamming distance between any two codewords is d. It was proved that for any equidistant (n,M,d;q) code, d?nM(q-1)/(M-1)q(=d_opt, say). A necessary condition for the existence of an optimal equidistant code is that d_opt be an integer. If d_opt is not an integer, i.e. the equidistant code is not optimal, then the code with d=⌊d_opt⌋ is called good equidistant code, which is obviously the best possible one among equidistant codes with parameters n,M and q. In this paper, some constructions of good equidistant codes from balanced arrays and nested BIB designs are described.     

Algorithms for finding K-best perfect matchings

In the K-best perfect matching problem (KM) one wants to find K pairwise different, perfect matchings M₁,…,M_k such that w(M₁) ≥ w(M₂) ≥ ⋯ ≥ w(M_k) ≥ w(M), ∀M ≠ M₁, M₂,…, M_k. The procedure discussed in this paper is based on a binary partitioning of the matching solution space. We survey different algorithms to perform this partitioning. The best complexity bound of the resulting algorithms discussed is O(Kn³), where n is the number of nodes in the graph.     

Symmetric LDPC codes and local testing

Coding theoretic and complexity theoretic considerations naturally lead to the question of generating symmetric, sparse, redundant linear systems. This paper provides a new way of construction with better parameters and new lower bounds.Low Density Parity Check (LDPC) codes are linear codes defined by short constraints (a property essential for local testing of a code). Some of the best (theoretically and practically) used codes are LDPC. Symmetric codes are those in which all coordinates “look the same,” namely there is some transitive group acting on the coordinates which preserves the code. Some of the most commonly used locally testable codes (especially in PCPs and other proof systems), including all “low-degree” codes, are symmetric. Requiring that a symmetric binary code of length n has large (linear or near-linear) distance seems to suggest a “con ict” between 1/rate and density (constraint length). In known constructions, if one is constant, then the other is almost the worst possible - n/poly(logn).Our main positive result simultaneously achieves symmetric low density, constant rate codes generated by a single constraint. We present an explicit construction of a symmetric and transitive binary code of length n, near-linear distance n/(log logn)², of constant rate and with constraints of length (logn)⁴. The construction is in the spirit of Tanner codes, namely the codewords are indexed by the edges of a sparse regular expander graph. The main novelty is in our construction of a transitive (non Abelian!) group acting on these edges which preserves the code. Our construction is one instantiation of a framework we call Cayley Codes developed here, that may be viewed as extending zig-zag product to symmetric codes.Our main negative result is that the parameters obtained above cannot be significantly improved, as long as the acting group is solvable (like the one we use). More specifically, we show that in constant rate and linear distance codes (aka “good” codes) invariant under solvable groups, the density (length of generating constraints) cannot go down to a constant, and is bounded below by (log^(Ω(?)) n)(an Ω(?) iterated logarithm) if the group has a derived series of length ?. This negative result precludes natural local tests with constantly many queries for such solvable “good” codes.     

Some results on Hu's conjecture concerning binary trees

Given n weights, w₁, w₂,…, w_n, such that 0?w₁?w₂???w₁, we examine a property of permutation π¹, where π¹=(w₁, w_n, w₂, w_n?1,…), concerning alphabetical binary trees.For each permutation π of these n weights, there is an optimal alphabetical binary tree corresponding to π, we denote it's cost by V(π). There is also an optimal almost uniform alphabetical binary tree, corresponding to π, we denote it's cost by V_u(π).This paper asserts that V_u(π¹)?V_u(π)?V(π) for all π. This is a preliminary result concerning the conjecture of T.C. Hu. Hu's conjecture is V(π¹)?V(π) for all π.     

Weighted Hamming metric structures

It is known that the binary generalized Goppa codes are perfect codes for the weighted Hamming metrics. In this paper, we present the existence of a weighted Hamming metric that admits a binary Hamming code (resp. an extended binary Hamming code) to be perfect code. For a special weighted Hamming metric, we also give some structures of a 2-perfect code, show how to construct a 2-perfect linear code and obtain the weight distribution of a 2-perfect code from the partial information of the code.