Search

Motivated by an application to database linear querying, such as private information-retrieval protocols, we suggest a fundamental property of linear codes– the generalized covering radius. The generalized covering-radius hierarchy of a linear code characterizes the trade-off between storage amount, latency, and access complexity, in such database systems. Several equivalent definitions are provided, showing this as a combinatorial, geometric, and algebraic notion. We derive bounds on the code parameters in relation with the generalized covering radii, study the effect of simple code operations, and describe a connection with generalized Hamming weights. [ABSTRACT FROM AUTHOR]

The notion of Generalized Hamming weights of block codes has been investigated since the nineties due to its significant role in coding theory and cryptography. In this paper we extend this concept to the context of convolutional codes. In particular, we focus on column distances and introduce the novel notion of generalized column distances (GCD). We first show that the hierarchy of GCD is strictly increasing. We then provide characterizations of such distances in terms of the truncated parity-check matrix of the code, that will allow us to determine their values. Finally, the case in which the parity-check matrix is in systematic form is treated. [ABSTRACT FROM AUTHOR]

A tiling of $\mathbb {F}_{2}^{n}$ (considered as a graph) gives rise to a perfect code (according to a given metric) if the basic tile is a metric ball. We are concerned with metrics on $\mathbb {F}_{2}^{n}$ that are determined by a weight which respects the support of vectors (TS-metrics) and in this case, a perfect code is called TS-perfect. We consider all the tilings of $\mathbb {F}_{2}^{n}$ by tiles with up to 8 elements (which are classified in the literature) and determine which of them give rise to a TS-perfect code. In the sequence, for those tilings that give rise to a perfect code for some TS-metric, we classify the TS-metrics (up to equivalence) that turn it into a perfect code. Also, we give a general construction to obtain TS-perfect codes out of given TS-perfect codes, by proving that concatenation of two TS-perfect codes is by itself a TS-perfect code. [ABSTRACT FROM AUTHOR]

In this work we explore a family of metrics over a finite field $\mathbb {F}_{q}$ which respect the support of vectors. We show how these metrics can be obtained from the edge-labeled Hamming cube and, based on this representation, we give a description of the group of linear isometries (for $q>2$). Next, we introduce the concept of conditional sum of metrics and determine what are the conditions that, out of two metrics respecting the support, give rise to a new such metric. Finally, we introduce the labeled-poset block metrics, a new family of metrics which respects support of vectors, filling a gap existing in the known universe of such metrics. For this family, we give a full description of the group of linear isometries and determine sufficient conditions to ensure the existence of a MacWilliams’ identity. [ABSTRACT FROM AUTHOR]

We present an algorithm that, given a channel, determines if there is a distance for it such that the maximum likelihood decoder coincides with the minimum distance decoder. We also show that any metric, up to a decoding equivalence, can be isometrically embedded into the hypercube with the Hamming metric, and thus, in terms of decoding, the Hamming metric is universal. [ABSTRACT FROM AUTHOR]

Given a finite directed graph with n vertices, we define a metric d_{G} on \mathbb {F}_{q}^{n} , where \mathbb Fq is the finite field with q elements. The weight of a word is defined as the number of vertices that can be reached by a directed path from a vertex within the support of the vector. Two canonical forms, which do not affect the metric, are given to each graph. Based on these forms we characterize each such metric. We further use these forms to prove that two graphs with different canonical forms yield different metrics. Efficient algorithms to check if a set of metric weights define a metric based on a graph are given. We provide tight bounds on the number of metric weights required to reconstruct the metric. Furthermore, we give a complete description of the group of linear isometries of the graph metrics and a characterization of the graphs for which every linear code admits a $G$ -canonical decomposition. Considering those graphs, we are able to derive an expression of the packing radius of linear codes in such metric spaces. Finally, given a directed graph which determines a hierarchical poset, we present sufficient and necessary conditions to ensure the validity of the MacWilliams identity and the MacWilliams extension property. [ABSTRACT FROM AUTHOR]

The most common decision criteria for decoding are maximum likelihood decoding and nearest neighbor decoding. It is well known that maximum likelihood decoding coincides with nearest neighbor decoding with respect to the Hamming metric on the binary symmetric channel. In this paper, we study channels and metrics for which those two criteria do and do not coincide for general codes. [ABSTRACT FROM AUTHOR]

Until this work, the packing radius of a poset code was only known in the cases where the poset was a chain, a hierarchy, a union of disjoint chains of the same size, and for some families of codes. Our objective is to approach the general case of any poset. To do this, we will divide the problem into two parts. The first part consists in finding the packing radius of a single vector. We will show that this is equivalent to a generalization of a well known NP-hard problem known as “the partition problem”. Then, we will review the main results known about this problem giving special attention to the algorithms to solve it. The main ingredient to these algorithms is what is known as the differentiating method, which we will extend to the general case. The second part consists in finding the vector that determines the packing radius of the code. For this, we will show how it is sometimes possible to compare the packing radius of two vectors without calculating them explicitly. [ABSTRACT FROM AUTHOR]

In this paper, we prove that a poset-block space admits a MacWilliams-type identity if and only if the poset is hierarchical, and at any level of the poset, all the blocks have the same dimension. When the poset-block admits the MacWilliams-type identity, we explicitly state the relation between the weight enumerators of a code and its dual. [ABSTRACT FROM AUTHOR]

Abstract: The flip operation on colored inner-triangle-free triangulations of a convex polygon is studied. It is shown that the affine Weyl group acts transitively on these triangulations by colored flips, and that the resulting colored flip graph is closely related to a lower interval in the weak order on . Lattice properties of this order are then applied to compute the diameter. [Copyright &y& Elsevier]

In this paper, we extend Wei's Duality Theorem, relating the generalized Hamming weight hierarchy of a code to the hierarchy of the dual code, to the scope of codes with poset metrics. As a consequence of this duality theorem, we prove some results concerning discrepancy of codes and chain condition for generalized weights. [ABSTRACT FROM AUTHOR]

Abstract: Let be the vector space of -tuples over a finite field and a poset that is the finite union of disjoint chains of length . We consider on the poset-metric introduced by Rosenbloom and Tsfasman. In this paper, we give a complete description of the symmetry group of the metric space . [Copyright &y& Elsevier]

We define a reflection in a tree to be an involutive automorphism whose set of fixed points is a geodesic, and we prove that, for the case of a homogeneous tree of even degree, the group of even automorphisms may be covered by at most seven reflections. [ABSTRACT FROM AUTHOR]

Abstract: Let V be an n-dimensional vector space over a finite field and a poset. We consider on V the poset-metric . In this paper, we give a complete description of groups of linear isometries of the metric space , for any poset-metric . [Copyright &y& Elsevier]

In this work we consider tessellations (or tilings) of the hyperbolic plane by copies of a semi-regular polygon with alternating angles and we study the behavior of the growth of the polygons, edges, and vertices when the distance increase from a fixed initial polygon. [ABSTRACT FROM AUTHOR]

In this paper, we consider metrics determined by hierarchical posets and give explicit formulas for the main parameters of a linear code: the minimum distance and the packing, covering, and Chebyshev radii of a code. We also present ten characterizations of hierarchical poset metrics, including new characterizations and simple new proofs to the known ones. [ABSTRACT FROM AUTHOR]

Abstract: We investigate linear and additive codes in partially ordered Hamming-like spaces that satisfy the extension property, meaning that automorphisms of ideals extend to automorphisms of the poset. The codes are naturally described in terms of translation association schemes that originate from the groups of linear isometries of the space. We address questions of duality and invariants of codes, establishing a connection between the dual association scheme and the scheme defined on the dual poset (they are isomorphic if and only if the poset is self-dual). We further discuss invariants that play the role of weight enumerators of codes in the poset case. In the case of regular rooted trees such invariants are linked to the classical problem of tree isomorphism. We also study the question of whether these invariants are preserved under standard operations on posets such as the ordinal sum and the like. [Copyright &y& Elsevier]

We study the problem of characterizing when two memoryless binary asymmetric channels, described by their transition probabilities $(p,q)$ and $(p^\prime,q^\prime)$ , are equivalent from the point of view of maximum likelihood decoding when restricted to $n$ -block binary codes. This equivalence of channels induces a partition (depending on $n$ ) on the space of parameters $(p,q)$ into regions associated with the equivalence classes. Explicit expressions for describing these regions, their number and areas are derived. Some perspectives of applications of our results to decoding problems are also presented. [ABSTRACT FROM PUBLISHER]