Search

The Singleton-type bound that offers an upper limit on the minimum Hamming distance for locally repairable codes (LRCs) has been studied by a lot of literatures. However, the work to determine tight Singleton-type bound for LRCs under all parameters is still incomplete. This paper focuses on the tightness of Singleton-type bound for general LRCs (linear and nonlinear). By exploring how the structure of repair sets affects the minimum Hamming distance, some properties for minimum Hamming distance of LRCs are derived. Through these properties, the following results are obtained: 1. The necessary conditions for LRCs whose minimum Hamming distance reaches the previous Singleton-type bound are provided. Due to these necessary conditions, the previous Singleton-type bound is proved to be unreachable under a number of parameters, and the tight Singleton-type bounds are given under some of these parameters. 2. Under a class of parameters where the previous Singleton-type bound for linear LRCs has been proved unreachable in the literatures, we improve Singleton-type bound and show that the new Singleton-type bound is tight. In addition, based on the existing LRC constructions, the previous Singleton-type bound for LRCs is shown to be tight under some other parameters. Finally, for an importance case of LRCs (i.e., every repair set is a 1-erasure correcting code), the Singleton-type bound under three classes of parameters is further improved. [ABSTRACT FROM AUTHOR]

This paper mainly focuses on cones whose basis is a maximum h -scattered linear set. We start by investigating the intersection numbers of such cones with respect to the hyperplanes. Then we analyze two constructions of point sets with few intersection numbers with respect to the hyperplanes. In particular, the second one extends the construction of translation KM-arcs in projective spaces, having as part at infinity a cone with basis a maximum h -scattered linear set. As an instance of the second construction we obtain cylinders with a hyperoval as basis, which we call hypercylinders , for which we are able to provide a stability result. The main motivation for these problems is related to the connections with both Hamming and rank distance codes. Indeed, we are able to construct codes with few weights and to provide a stability result for the codes associated with hypercylinders. [ABSTRACT FROM AUTHOR]

Let p ≠ 3 be any prime. The algebraic structures of all λ -constacyclic codes of length 3 p s over the finite commutative chain ring R = F p m + u F p m are provided by classifying all ideals of the local ring R [ x ] 〈 x 3 p s − λ 〉. Using these structures, in this paper, the exact values of Hamming distances of all such λ -constacyclic codes of length 3 p s are established. As an application, we identify all maximal distance separable λ -constacyclic codes of length 3 p s. [ABSTRACT FROM AUTHOR]

Let p be an odd prime, and λ be a nonzero element of the finite field F p m . The λ -constacyclic codes of length 2 p s over F p m are classified as the ideals of quotient ring F p m [ x ] 〈 x 2 p s − λ 〉 in terms of their generator polynomials. Based on these generator polynomials, the symbol-pair distances of all such λ -constacyclic codes of length 2 p s are obtained in this paper. As an application, all MDS symbol-pair constacyclic codes of length 2 p s over F p m are established, which produce many new MDS symbol-pair codes with good parameters. [ABSTRACT FROM AUTHOR]

In this paper, we consider q -ary codes of length n and minimum Hamming distance d , which have two weights w 1 and w 2. These codes are denoted by (n , d , { w 1 , w 2 }) q codes. Let A q (n , d , { w 1 , w 2 }) denote the largest possible number of codewords in an (n , d , { w 1 , w 2 }) q code and we simply write A (n , d , { w 1 , w 2 }) for A 2 (n , d , { w 1 , w 2 }). Some upper bounds on A q (n , d , { w 1 , w 2 }) are given. The equivalences between binarytwo-weight codes and special combinatorial configurations with certain properties are established and then new upper bounds on A (n , d , { w 1 , w 2 }) are derived. For w 1 , w 2 ∈ { 2 , 3 , 4 } , optimal constructions of (n , d , { w 1 , w 2 }) 2 codes are presented. The exact value of A (n , d , { 2 , 3 }) is completely determined for all n and d. We determine the exact value of A (n , d , { 2 , 4 }) for any positive integer n ≡ 2 , 4 (mod 6) and d ∈ { 3 , 4 }. The exact value of A (n , d , { 3 , 4 }) is determined for any integer n and d ∈ { 6 , 7 } , or d = 5 and n ≡ 0 , 2 , 3 , 11 (mod 12). [ABSTRACT FROM AUTHOR]

Abstract Let p be an odd prime, s , m be positive integers, γ , λ be nonzero elements of the finite field F p m such that γ p s = λ. In this paper, we show that, for any positive integer η , the Hamming distances of all repeated-root λ -constacyclic codes of length η p s can be determined by those of certain simple-root γ -constacyclic codes of length η. Using this result, Hamming distances of all constacyclic codes of length 4 p s are obtained. As an application, we identify all MDS λ -constacyclic codes of length 4 p s. [ABSTRACT FROM AUTHOR]

Abstract In frequency-hopping spread spectrum systems, frequency-hopping sequences (FHSs) are widely used to alleviate the interferences caused by the hits of frequencies. In this paper, based on the Zeng–Cai–Tang–Yang cyclotomy and the Chinese Remainder Theorem, a family of FHS sets with composite lengths is constructed and the Hamming correlations of the new FHS sets are derived by some basic properties of cyclotomic numbers. The results show that the proposed FHS sets are optimal with respect to the Peng–Fan bound. Furthermore, it generalizes some earlier cyclotomic constructions of optimal FHS sets and produces optimal FHS sets with new parameters which are not covered in the literature. [ABSTRACT FROM AUTHOR]

We introduce the notion of Levenshtein graphs, an analog to Hamming graphs but using the edit distance instead of the Hamming distance; in particular, vertices in Levenshtein graphs may be strings (i.e., words or sequences of characters in a reference alphabet) of possibly different lengths. We study various properties of these graphs, including a necessary and sufficient condition for their shortest path distance to be identical to the edit distance, and characterize their automorphism group and determining number. We also bound the metric dimension (i.e. minimum resolving set size) of Levenshtein graphs. Regarding the latter, recall that a run is a string composed of identical characters. We construct a resolving set of two-run strings and an algorithm that computes the edit distance between a string of length k and any single-run or two-run string in O (k) operations. [ABSTRACT FROM AUTHOR]

Let G = (V , E) be a graph with path-length distance function ∂ and diameter d. Let D ⊆ { 0 , 1 , ... , d } be a set of distances in G and let N D (x) = { y | ∂ (x , y) ∈ D } for a fixed vertex x ∈ V. A bijection φ : V → { 1 , 2 , ... , | V | } is called a D -magic labeling of G if there exists a constant k such that ∑ y ∈ N D (x) f (y) = k for any x ∈ V. In this paper, we will study D -magic labelings of the halved n -cube (n ≥ 2) that is on all binary strings of length n with even number of 1s as vertices and edges between any two strings of Hamming distance 2. We prove that the halved n -cube is {1}-magic if and only if n = m 2 where m ≥ 2 and m ≢ 0 (mod 4) , and is { 0 , 1 } -magic if and only if n = m 2 + 2 where m ≥ 0 and m ≢ 2 (mod 4). [ABSTRACT FROM AUTHOR]

The units of the chain ring R a = F p m [ u ] 〈 u a 〉 = F p m + u F p m + ⋯ + u a − 1 F p m are partitioned into a distinct types. It is shown that for any unit Λ of Type k , a unit λ of Type k ∗ can be constructed, such that the class of λ -constacyclic of length p s of Type k ∗ codes is one-to-one correspondent to the class of Λ -constacyclic codes of the same length of Type k via a ring isomorphism. The units of R a of the form Λ = Λ 0 + u Λ 1 + ⋯ + u a − 1 Λ a − 1 , where Λ 0 , Λ 1 , … , Λ a − 1 ∈ F p m , Λ 0 ≠ 0 , Λ 1 ≠ 0 , are considered in detail. The structure, duals, Hamming and homogeneous distances of Λ -constacyclic codes of length p s over R a are established. It is shown that self-dual Λ -constacyclic codes of length p s over R a exist if and only if a is even, and in such case, it is unique. Among other results, we discuss some conditions when a code is both α - and β -constacyclic over R a for different units α , β . [ABSTRACT FROM AUTHOR]

The covering radius of a subset C of the symmetric group S n is the maximal Hamming distance of an element of S n from C . This note determines the covering radii of the finite 2 -dimensional projective general linear groups. It turns out that the covering radius of PGL 2 ( q ) is q − 2 if q is even, and is q − 3 if q is odd. [ABSTRACT FROM AUTHOR]

The Hamming distance ham (u , v) between two equal-length words u , v is the number of positions where u and v differ. The words u and v are said to be conjugates if there exist non-empty words x , y such that u = x y and v = y x. The smallest value ham (x y , y x) can take on is 0, when x and y commute. But, interestingly, the next smallest value ham (x y , y x) can take on is 2 and not 1. In this paper, we consider conjugates u = x y and v = y x where ham (x y , y x) = 2. More specifically, we provide an efficient formula to count the number h (n) of length- n words u = x y over a k -letter alphabet that have a conjugate v = y x such that ham (x y , y x) = 2. We also provide efficient formulae for other quantities closely related to h (n). Finally, we show that h (n) grows erratically: cubically for n prime, but exponentially for n even. [ABSTRACT FROM AUTHOR]

The sizes of optimal constant-composition codes of weight three have been determined by Chee, Ge and Ling with four cases in doubt. Group divisible codes played an important role in their constructions. In this paper, we study the problem of constructing optimal ternary constant-composition codes with Hamming weight four and minimum distance six. The problem is solved with a small number of lengths undetermined. The previously known results are those with code length no greater than 10. [ABSTRACT FROM AUTHOR]

Abstract: In this paper, the explicit expressions for the generating idempotents, check polynomials and the parameters of all minimal cyclic codes of length over are obtained, where is an odd prime different from the characteristic of , and are positive integers with , and . Our results generalize the main results in Pruthi and Arora (1997) and Arora and Pruthi (1999), which considered the cases and respectively. We propose an approach different from those in Pruthi and Arora (1997) and Arora and Pruthi (1999) to obtain the generating idempotents. [Copyright &y& Elsevier]

Abstract: A graph is an -graph if its vertices can be labeled by binary vectors in such a way that the Hamming distance between the binary addresses is, up to scale, the distance in the graph between the corresponding vertices. In this note, we study when the result of gluing two -graphs along an edge is an -graph. If at least one of the constituent graphs is bipartite, then the resulting graph is also an -graph. For two nonbipartite -graphs, this is not always the case. [Copyright &y& Elsevier]

For finite groups G(∘) and G(*) define d(∘,*) as the number of pairs (u,v)∈G×G with u∘v≠u*v. If |G|=n is a power of two and d(∘,*), then there exists an isomorphism σ : G(∘)≅G(*) that fixes more than 7n/8 points of G. [Copyright &y& Elsevier]

In 1977, Ahlswede and Katona proposed the following isoperimetric problem: find a set S of n points in {0,1}k whose average Hamming distance is minimal—or equivalently find an n-vertex subgraph of the hypercube Qk whose average distance is minimal.We report on some recent results and conjecture that S can be chosen to be the set of all points in {0,1}k that are distance at most r from some point c∈Rk. We show that these “discrete balls” include all known good constructions and we provide additional evidence supporting the conjecture. [Copyright &y& Elsevier]

In this paper 1 1 An extended abstract of this paper appeared in Proceedings of 11th Annual International Conference on Combinatorial Optimization and Applications (COCOA 2017) (Glazik et al. 2017) [8]. we introduce a variant of Mastermind, which we call Static Permutation Mastermind and which is defined as follows. One player creates a secret code, called secret, consisting of n colors on n pegs, where each color is used exactly once. The second player tries to determine the secret with as few questions as possible, where each question is a possible secret and all questions are asked at once. After having asked all questions, he receives for each question the number of correctly placed colors and has one more try to determine the secret. The main result of this paper is an upper bound of O (n 1. 525) questions. It is proved by a distinction of pairs of possible secrets with low and high Hamming distance. For pairs with a low Hamming distance we construct questions using certain arithmetic progressions. For pairs with a high Hamming distance we estimate the size of a vertex cover in a suitable hypergraph. With a slight modification of the arguments of Doerr et al. (2016) we also give a lower bound of Ω (n log n). [ABSTRACT FROM AUTHOR]

Minimal linear codes have diverse applications in many areas such as secret sharing schemes and secure two-party computation. There are several construction methods for these codes, one of which is based on functions over finite fields. In this paper, to construct minimal codes with few weights, we make use of weakly regular plateaued balanced functions over F p , where p is an odd prime, in the second generic construction method. We obtain several three-weight and four-weight minimal codes with desirable parameters from these functions. The weight distributions of the obtained codes are completely determined with the help of the Walsh distributions of these functions. We then derive projective three-weight punctured codes from some obtained codes, by deleting some coordinates of the defining sets. It is worth noting that they may include the (almost) optimal codes. We finally analyze the minimum Hamming distances of the dual codes of our minimal codes for secret sharing schemes and association schemes. [ABSTRACT FROM AUTHOR]

Abstract: Let be strings of equal length. The Hamming distance between and is the number of positions in which and differ. If is a cyclic shift of , we say and are conjugates. We consider , the Hamming distance between the conjugates and . Over a binary alphabet is always even, and must satisfy a further technical condition. By contrast, over an alphabet of size 3 or greater, can take any value between 0 and , except 1; furthermore, we can always assume that the smaller string has only one type of letter. [Copyright &y& Elsevier]

Let p be a prime, s , m be positive integers, λ be a nonzero element of the finite field F p m . The b -distance generalizes the Hamming distance (b = 1) , and the symbol-pair distance (b = 2). While the Hamming and symbol-pair distances of all λ -constacyclic codes of length p s are completely determined, the general b -distance of such codes was left opened. In this paper, we provide a new technique to establish the b -distance of all λ -constacyclic codes of length p s , where 1 ≤ b ≤ ⌊ p 2 ⌋. As an application, all MDS b -symbol constacyclic codes of length p s over F p m are obtained. [ABSTRACT FROM AUTHOR]

For any prime number p , positive integers m , k , n , where n satisfies gcd (p , n) = 1 , and for any non-zero element λ 0 of the finite field F p m of cardinality p m , we prove that any λ 0 p k -constacyclic code of length p k n over the finite field F p m is monomially equivalent to a matrix-product code of a nested sequence of p k λ 0 -constacyclic codes with length n over F p m . As an application, we completely determine the Hamming distances of all negacyclic codes of length 7 ⋅ 2 l over F 7 for any integer l ≥ 3. [ABSTRACT FROM AUTHOR]

Abstract: The nonexistence of sharply t-transitive permutation sets of degree n with is proved. [Copyright &y& Elsevier]