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.

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.

A tiling of F2n(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 F2nthat 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 F2nby 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.

In this work we introduce the concept of Unrestricted Generalized Column Distance (UGCD) for convolutional codes. This is the concept equivalent to the generalized Hamming weights for block codes. We show that the hierarchy of UGCD is strictly increasing and show how to compute it of parity-check matrix in general form. We also provide a way to compute it out of a systematic parity-check matrix.

In this work we explore a family of metrics over a finite field Fqwhich respect the support of vectors. We show how these metrics can be obtained from the edge-weighted 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, gives 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 for the existence of a MacWilliams' identity.

In this work, we consider tilings of the Hamming cube and look for metrics which turn the tilings into a perfect code. We consider the family of metrics which are determined by a weight and are compatible with the support of vectors (TS-metrics). We determine which of the tilings with small tiles or high rank can be a perfect code for some TS-metric and we characterize all such metrics. Finally, we show some procedures to obtain new perfect codes (relatively to TS-metrics) out of existing ones.

Given a finite directed graph with n vertices, we define a metric dG on Fnq, where 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.

We study the problem of characterizing when two memoryless binary asymmetric channels, described by their transition probabilities (p, q) and (p', q'), 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.

In this work, we adapt the notion of generalized Hamming weight of block codes to introduce the novel concept of generalized column distances for convolutional codes. This can be considered as an extension of the work done in [18] on the generalized Hamming weights for free distance of convolutional codes. We also introduce the concept of Almost-MDP and Near-MDP convolutional code. The problem of constructing convolutional codes with design generalized column distances remains an interesting open problem that requires further research.

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.

Given a finite directed graph G with n vertices, the metric m(G) is naturally defined over Fqn, where the weight of a word which has its nonzero entries in positions i1,..., ir, is equal to the number of vertices in all the directed paths starting in the vertices vi1,..., vir. Two canonical forms, which do not affect the metric, are given to each graph. Based on these canonical forms we characterize each such metric. We further use these forms to prove that two graphs with different canonical forms yield two different metrics. Efficient algorithms to check if a given 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 whole metric. Finally, we discuss the group of linear isometries of the graph metrics and the connection of the work to coding theory.

Considering metrics based on finite directed graph, introduced by Etzion and Firer, we characterize the graphs such that every linear code admits a G-canonical decomposition. This decomposition will play an important role in this work, since it will be the main tool to give a sufficient condition for a finite directed graph to satisfy both the MacWilliams Identity and the MacWilliams Extension Property.

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.

In this work we show how to decompose a linear code relatively to any given poset metric. We prove that the complexity of syndrome decoding is determined by a maximal (primary) such decomposition and then show that a refinement of a partial order leads to a refinement of the primary decomposition. Using this and considering already known results about hierarchical posets, we can establish upper and lower bounds for the complexity of syndrome decoding relatively to a poset metric.

Considering a poset metric as a generalization of Hamming's metric, the packing radius of a code is not necessarily a function of the minimal distance. In this work we show, without any restriction on the poset, that the relation between the weight and the packing radius of a vector is equivalent to a generalization of the classical partition problem. We also generalize the well renown heuristic and deterministic algorithms of Karmakar-Karp and Korf, respectively, using an algebraic approach to the Differencing Method.

Poset metrics form a generalization of the Hamming metric on the space Fnq. Orbits of the group of linear isometries of the space give rise to a translation association scheme. The structure of the dual scheme is important in studying duality of linear codes; this study is facilitated if the scheme is self-dual. We study the relation between self-duality of the scheme and that of the poset. We also give new examples of poset metric spaces and describe the association schemes that arise from linear isometries.

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.

In this work 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.

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.

Poset and block metrics were introduced in recent years as alternative metrics to study error correcting codes. Poset-block codes were introduced in 2008, encompassing both poset and block metrics. In this paper, we study a family of such metrics, the Niederreiter-Rosenbloom-Tsfasman block metrics. In this context, we classify the classes of equivalent codes, describe canonical representatives of each class and develop much of the classical theory of error correcting codes for Niederreiter-Rosenbloom-Tsfasman block codes, including determination of packing radius and classification of MDS and perfect codes, determination of covering radius and characterization of quasi-perfect codes, and the description of an algorithm for syndrome decoding.