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]

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 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]