Search

In this work, we analyze the problem of catastrophicity of encoders of convolutional codes over the Laurent series with coefficients in ℤ p r , ℤ p r ((d)). Kuijper and Pinto proved in [M. Kuijper and R. Pinto, On minimality of convolutional ring encoders, IEEE Trans. Autom. Control55(11) (2009) 4890–4897] that, contrary to what happens for codes over ((d)) , where is a field, when dealing with ℤ p r ((d)) there are convolutional codes that do not admit non-catastrophic encoders. Nevertheless it was conjectured that any catastrophic convolutional code admits another type of non-catastrophic encoder called p -encoder. In this paper we solve this conjecture for a class of (2 , 1) convolutional codes over ℤ p 2 and show that, in fact, these codes always admit a non-catastrophic p-encoder. We also describe a constructive procedure that allows us to obtain a non-catastrophic p -encoder. [ABSTRACT FROM AUTHOR]

In this paper we present a concrete algebraic construction of a novel class of convolutional codes. These codes are built upon generalized Vandermonde matrices and therefore can be seen as a natural extension of Reed–Solomon block codes to the context of convolutional codes. For this reason we call them weighted Reed–Solomon (WRS) convolutional codes. We show that under some constraints on the defining parameters these codes are Maximum Distance Profile (MDP), which means that they have the maximal possible growth in their column distance profile. We study the size of the field needed to obtain WRS convolutional codes which are MDP and compare it with the existing general constructions of MDP convolutional codes in the literature, showing that in many cases WRS convolutional codes require significantly smaller fields. [ABSTRACT FROM AUTHOR]

Noncatastrophic encoders are an important class of polynomial generator matrices of convolutional codes. When these polynomials have coefficients in a finite field, these encoders have been characterized as polynomial left prime matrices. In this paper, we study the notion of noncatastrophicity in the context of convolutional codes when the polynomial matrices have entries in the finite ring ℤ p r . In particular, we study the notion of zero left prime in order to fully characterize noncatastrophic encoders over the finite ring ℤ p r . The second part of the paper is devoted to investigate free and column distance of convolutional codes that are free finitely generated ℤ p r -modules. We introduce the notion of b -degree and provide new bounds on the free distances and column distance. We show that this class of convolutional codes is optimal with respect to the column distance and to the free distance if and only if its projection on ℤ p is. [ABSTRACT FROM AUTHOR]

In this paper we study finite support convolutional codes over Z p r by means of an input-state-output representation. We show that the set of finite weight input-state-output trajectories associated to this type of representations has the structure of a Z p r -submodule of Z p r n and therefore is a (finite support) convolutional code. Fundamental system-theoretical properties such as observability, reachability or minimality, are investigated in this context. [ABSTRACT FROM AUTHOR]

In this paper we address the problem of list decoding of linear codes over an integer residue ring Z q , where q is a power of a prime p. The proposed procedure exploits a particular matrix representation of the linear code over Z p r , called the standard form, and the p -adic expansion of the to-be-decoded vector. In particular, we focus on the erasure channel in which the location of the errors is known. This problem then boils down to solving a system of linear equations with coefficients in Z p r . From the parity-check matrix representations of the code we recursively select certain equations that a codeword must satisfy and have coefficients only in the field p r − 1 Z p r . This yields a step by step procedure obtaining a list of the closest codewords to a given received vector with some of its coordinates erased. We show that such an algorithm actually computes all possible erased coordinates, that is, the provided list is minimal. [ABSTRACT FROM AUTHOR]

Locally repairable convolutional codes (LRCCs) for distributed storage systems (DSSs) are introduced in this work. They enable local repair, for a single node erasure (or more generally, $\partial - 1$ erasures per local group), and sliding-window global repair, which can correct erasure patterns with up to ${\mathrm{d}}_{j}^{c} - 1$ erasures in every window of $j+1$ consecutive blocks of $n$ nodes, where ${\mathrm{d}}_{j}^{c} - 1$ is the $j$ th column distance of the code. The parameter $j$ can be adjusted, for a fixed LRCC, according to different catastrophic erasure patterns, requiring only to contact $n(j+1) - {\mathrm{d}}_{j}^{c} + 1$ nodes, plus less than $\mu n$ other nodes, in the storage system, where $\mu$ is the memory of the code. A Singleton-type bound is provided for ${\mathrm{d}}_{j}^{c} - 1$. If it attains such a bound, an LRCC can correct the same number of catastrophic erasures in a window of length $n(j+1)$ as an optimal locally repairable block code of the same rate and locality, and with block length $n(j+1)$. In addition, the LRCC is able to perform the flexible and somehow local sliding-window repair by adjusting $j$. Furthermore, by adjusting and/or sliding the window, the LRCC can potentially correct more erasures in the original window of $n(j+1)$ nodes than an optimal locally repairable block code of the same rate and locality, and length $n(j+1)$. Finally, the concept of partial maximum distance profile (partial MDP) codes is introduced. Partial MDP codes can correct all information-theoretically correctable erasure patterns for a given locality, local distance and information rate. An explicit construction of partial MDP codes whose column distances attain the provided Singleton-type bound, up to certain parameter $j=L$ , is obtained based on known maximum sum-rank distance convolutional codes. [ABSTRACT FROM AUTHOR]

Maximum distance profile codes over finite non-binary fields have been introduced and thoroughly studied in the last decade. These codes have the property that their column distances are maximal among all codes of the same rate and degree. In this paper, we aim at studying this fundamental concept in the context of convolutional codes over a finite ring. We extensively use the concept of $p$ -encoder to establish the theoretical framework and derive several bounds on the column distances. In particular, a method for constructing (not necessarily free) maximum distance profile convolutional codes over ${\mathbb Z}_{p^{r}}$ is presented. [ABSTRACT FROM AUTHOR]

Abstract A convolutional code C over Z p r ((D)) is a Z p r ((D)) -submodule of Z p r n ((D)) that admits a polynomial set of generators, where Z p r ((D)) stands for the ring of (semi-infinity) Laurent series. In this paper we study several structural properties of its dual C ⊥. We use these results to provide a constructive algorithm to build an explicit generator matrix of C ⊥. Moreover, we show that the transpose of such a matrix is a parity-check matrix (also called syndrome former) of C. [ABSTRACT FROM AUTHOR]

In this paper, we investigate the properties of two-dimensional (2D) convolutional codes which are obtained from series concatenation of two 2D convolutional codes. For this purpose, we confine ourselves to dealing with finite-support 2D convolutional codes and make use of the Fornasini-Marchesini input-state-output (ISO) model representations. Within these ISO representations, we study when the structural properties of modal reachability and modal observability of the two given ISO representations carry over to the resulting 2D convolutional code. Moreover, we provide necessary conditions for obtaining a systematic concatenated convolutional code. Finally, we present a lower bound on its free distance. [ABSTRACT FROM AUTHOR]

Maximum distance separable (MDS) block codes and MDS 1D convolutional codes are the most robust codes for error correction within the class of block codes of a fixed rate and 1D convolutional codes of a certain rate and degree, respectively. In this paper, we generalize this concept to the class of 2D convolutional codes. For that, we introduce a natural bound on the distance of a 2D convolutional code of rate k/n and degree \delta , which generalizes the Singleton bound for block codes and the generalized Singleton bound for 1D convolutional codes. Then, we prove the existence of 2D convolutional codes of rate k/n and degree \delta if k {\nmid } \delta , or n \geq k (({(({\delta }/{k}) + 1)(({\delta }/{k}) + 2)})/{2})$ if $k \mid \delta $ , by presenting a concrete constructive procedure. [ABSTRACT FROM AUTHOR]

Abstract: In this paper we present an efficient approach to the analysis of discrete positive singular systems. One of our main objectives is to investigate the problem of characterizing positivity of such systems. Previously, this issue was not completely addressed. We provide easily checkable necessary and sufficient conditions for such problem to be solved. On the other hand, we study the stability of discrete positive singular systems. Note that this is not a trivial problem since the set of admissible initial conditions is not the whole space but it is represented by a special cone. All the conditions we provide are necessary and sufficient and are based on a reliable computational approach via linear programming. [Copyright &y& Elsevier]

Abstract: In this paper two-dimensional convolutional codes with finite support are considered, i.e., convolutional codes whose codewords have compact support indexed in and take values in , where is a finite field. The main goal of this work is to analyze the (free) distance properties of this type of codes of rate and degree . We first establish an upper bound on the maximum possible distance for these codes. We then present particular constructions of two-dimensional convolutional codes with finite support of rate and degree that attain such a bound and therefore have the maximum distance among all two-dimensional convolutional codes with finite support with the same rate and degree. We call such codes maximum distance separable two-dimensional convolutional codes. [Copyright &y& Elsevier]

Abstract: For many 2D systems, one of the independent variables plays a distinct role in the evolution of the trajectories; since often this special independent variable is time, we call such systems ‘time-relevant’. In this paper, we introduce a stability notion for time-relevant systems described by higher-order difference equations. We give algebraic tests in terms of the location of the zeros of the determinant of a polynomial matrix describing the system. We also give an LMI characterization of time-relevant stability involving only constant matrices. [Copyright &y& Elsevier]

In this work, we consider linear, shift-invariant and complete two-dimensional (2D) discrete systems from a behavioral point of view. In particular, we examine behaviors with two types of variables: the variables that we are interested to control (the to-be-controlled variables) and the variables on which we are allowed to enforce restrictions (the control variables). The main purpose of this contribution is to derive necessary and sufficient conditions for the stabilization of the to-be-controlled variables by 'attaching' a controller to the control variables. This problem turns out to be related to the decomposition of a given behavior into the sum of two sub-behaviors. Moreover, we show that under certain conditions, it is possible to obtain a constructive solution and characterize the structure of the to-be-controlled behavior. [ABSTRACT FROM AUTHOR]

In this paper, we study product convolutional codes described by state-space representations. In particular, we investigate how to derive state-space representations of the product code from the horizontal and vertical convolutional codes. We present a systematic procedure to build such representation with minimal dimension, i.e., reachable and observable. [ABSTRACT FROM AUTHOR]

A convolutional code C over Z p r [ D ] is a Z p r [ D ] -submodule of Z p r n [ D ] where Z p r [ D ] stands for the ring of polynomials with coefficients in Z p r . In this paper, we study the list decoding problem of these codes when the transmission is performed over an erasure channel, that is, we study how much information one can recover from a codeword w ∈ C when some of its coefficients have been erased. We do that using the p -adic expansion of w and particular representations of the parity-check polynomial matrix of the code. From these matrix polynomial representations we recursively select certain equations that w must satisfy and have only coefficients in the field p r − 1 Z p r . We exploit the natural block Toeplitz structure of the sliding parity-check matrix to derive a step by step methodology to obtain a list of possible codewords for a given corrupted codeword w , that is, a list with the closest codewords to w. [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]

In the last decade there has been a great interest in extending results for codes equipped with the Hamming metric to analogous results for codes endowed with the rank metric. This work follows this thread of research and studies the characterization of systematic generator matrices (encoders) of codes with maximum rank distance. In the context of Hamming distance these codes are the so-called Maximum Distance Separable (MDS) codes and systematic encoders have been fully investigated. In this paper we investigate the algebraic properties and representation of encoders in systematic form of Maximum Rank Distance (MRD) codes and Maximum Sum Rank Distance (MSRD) codes. We address both block codes and convolutional codes separately and present necessary and sufficient conditions for an encoder in systematic form to generate a code with maximum (sum) rank distance. These characterizations are given in terms of certain matrices that must be superregular in a extension field and that preserve superregularity after some transformations performed over the base field. We conclude the work presenting some examples of Maximum Sum Rank convolutional codes over small fields. For the given parameters the examples obtained are over smaller fields than the examples obtained by other authors. [ABSTRACT FROM AUTHOR]