Next Article in Journal
Overview in Summabilities: Summation Methods for Divergent Series, Ramanujan Summation and Fractional Finite Sums
Next Article in Special Issue
Extremal Binary and Ternary Codes of Length 60 with an Automorphism of Order 29 and a Generalization
Previous Article in Journal
The Distributed and Centralized Fusion Filtering Problems of Tessarine Signals from Multi-Sensor Randomly Delayed and Missing Observations under Tk-Properness Conditions
 
 
Font Type:
Arial Georgia Verdana
Font Size:
Aa Aa Aa
Line Spacing:
Column Width:
Background:
Article

On the State Approach Representations of Convolutional Codes over Rings of Modular Integers

Department of Mathematics, Universidad de León, 24007 León, Spain
*
Author to whom correspondence should be addressed.
Submission received: 19 October 2021 / Revised: 10 November 2021 / Accepted: 11 November 2021 / Published: 20 November 2021
(This article belongs to the Special Issue Advances in Contemporary Coding Theory)

Abstract

:
In this study, we prove the existence of minimal first-order representations for convolutional codes with the predictable degree property over principal ideal artinian rings. Further, we prove that any such first-order representation leads to an input/state/output representation of the code provided the base ring is local. When the base ring is a finite field, we recover the classical construction, studied in depth by J. Rosenthal and E. V. York. This allows us to construct observable convolutional codes over such rings in the same way as is carried out in classical convolutional coding theory. Furthermore, we prove the minimality of the obtained representations. This completes the study of the existence of input/state/output representations of convolutional codes over rings of modular integers.

1. Introduction

The relation between convolutional codes and linear dynamical systems has been and still is largely studied. This relationship appears when one considers studying the coding dynamics of a convolutional code, and it depends, to some degree, on the notion of convolutional code used. If we describe a convolutional code as a linear subspace, C F q ( z ) n , the linear system associated with the code is known as driving input/output representation ([1,2]). If we describe a convolutional code as a submodule, C F q [ z ] n , the coding dynamics can be modeled by a linear dynamical system known as input/state/output (I/S/O) representation [3,4,5,6], since k components of the output drive the remaining n k components. One can also define a convolutional code as a time-invariant complete behavior. In such a case, there is also a representation theory ([7,8,9]). Another perspective deals, for instance, with the dynamic symbolic point of view ([10]).
The case we are interested in is that of submodules and I/S/O representations. I/S/O representations are useful because, among other reasons, they allow one to construct convolutional codes with desirable properties (such as observability and good distances), to define (algebraic) decoding algorithms, to study concatenated convolutional codes, and to study finite support 2 D convolutional codes, periodically time-invariant convolutional codes and product convolutional codes ([11,12,13,14,15,16,17]).
Massey and Mittleholzer introduced convolutional codes over rings to model the phase modulation problem ([18,19]) and, currently, they are also used for decoding, steganography, and networks models, among other applications. The study of their algebraic structure was focused on in [20] for general base rings, and completed in [21] for convolutional codes over the ring Z p r , where r is a positive integer and p is a prime number.
Although the mathematical formalism of the theory of convolutional codes over general rings is very similar to that of fields, their properties may be quite different, and they need to be studied for particular rings ([22,23,24]). Despite their importance, the extension of the relation between minimal I/S/O representations and convolutional codes to an arbitrary commutative ring may not be that close. In the case of the module-theoretic approach, it has only been extended, to the knowledge of the authors, to noetherian von Neumann regular rings, that is, finite product of fields ([25,26]).
In this work, we address the problem of the existence of first-order and I/S/O representations for convolutional codes over principal ideal artinian rings, such as Z M with M a natural number. Furthermore, we study the minimality conditions of these representations through control properties of the associated linear systems.
This article is organized as follows: in Section 2, we give an overview of basic notions concerning convolutional codes and their first-order and I/S/O representations. In Section 3, we recall and prove some results about the predictable degree property of a convolutional encoder. In Section 4, we prove the existence of first-order representations for convolutional codes with the predictable degree property over principal artinian rings. Then, the existence of I/S/O representations is also studied. In Section 5, we prove that the obtained I/S/O representations are minimal. Furthermore, we study the relation between the observability of a convolutional code and the observability of the corresponding I/S/O representations. Finally, we give some conclusions concerning these results.

2. Convolutional Codes and Linear Systems

In this section, we review the basic definitions and properties of convolutional codes over rings. In addition, we recall the notions of first-order and I/S/O representations of convolutional codes over rings, as stated in [27].

2.1. Algebraic Preliminaries about Convolutional Codes

Let R be a commutative ring and z an indeterminate. We consider the polynomial ring R [ z ] . Given a polynomial p ( z ) R [ z ] , its trailing coefficient is the coefficient of least degree. Consider the multiplicatively closed system
S : = { q ( z ) R [ z ] : trailing coefficient of q ( z ) R * } ,
with R * being the group of invertible elements of R. Then, the ring of rational functions is defined as the localized ring:
R ( z ) : = S 1 R [ z ] : = p ( z ) q ( z ) : q ( z ) S , p ( z ) R [ z ] .
The ring of realizable functions is defined as
R r ( z ) : = p ( z ) q ( z ) R ( z ) : q ( 0 ) R * = p ( z ) q ( z ) : q ( z ) S , q ( 0 ) R * and p ( z ) R [ z ] .
Let R [ [ z ] ] be the ring of formal power series with coefficients in R, and R ( ( z ) ) the ring of Laurent series with coefficients in R. Note that R r ( z ) R [ [ z ] ] R ( ( z ) ) and R r ( z ) R ( z ) R ( ( z ) ) . There are different definitions of convolutional codes, depending on what we demand to the message transmission process, i.e., if there is a time origin in the transmission process, if the transmission process can be extended infinitely, etc. This choice is reflected on the algebraic structure of the space of code words, A { R ( ( z ) ) , R [ [ z ] ] , R ( z ) } , and it provides us with different types of encoders.
In the following, when we refer to A as a space of code words, we mean that A can be one of the rings R ( ( z ) ) , R [ [ z ] ] or R ( z ) .
Definition 1
([19]). Let k n N . Let A be a space of code words. A ( k , n ) convolutional encoder over A is a realizable matrix G ( z ) R r ( z ) n × k whose columns are linearly independent as elements of A n .
G ( z ) defines, by left multiplication, an R-linear map G ( z ) · : A k A n . In the above definition, the condition imposed on the columns of G ( z ) means that the above R-linear map is injective. In some works such as [20], the above matrix G ( z ) is called a generator matrix.
Definition 2.
Let A be a space of code words and let G ( z ) R r ( z ) n × k be a ( k , n ) convolutional encoder over A . The A -submodule of A n given by
I m ( G ( z ) · ) = { G ( z ) · x ( z ) : x ( z ) A k }
is called a ( k , n ) convolutional code C over R. The elements of A k are called information words, while the elements of I m ( G ( z ) · ) are called code words.
There is a natural and well-known equivalence relation in the set of encoders once we fix a space of code words A .
Definition 3
(Definition 4, [20]). Let A be a space of code words and k n N . Two convolutional encoders, G ( z ) and G ( z ) R r ( z ) n × k , are equivalent if they generate the same convolutional code, C A n . This equivalence relation is denoted by G ( z ) G ( z ) .
Lemma 1
(Theorem 1, [20]). Let A be a space of code words and k n N . Two convolutional encoders, G ( z ) , G ( z ) R r ( z ) n × k , are equivalent if and only if there is an invertible matrix U ( z ) A k × k such that G ( z ) = G ( z ) · U ( z ) .
Note that any matrix
G ( z ) = p i j ( z ) q i j ( z ) R r ( z ) n × k ,
with q i j ( z ) S and q i j ( 0 ) R * , can be written in the form
G ( z ) = G ( z ) h ( z ) ,
with G ( z ) being a polynomial matrix and h ( z ) = q i j ( z ) R [ z ] a realizable polynomial, i.e., h ( 0 ) R * . In the case where the definition of convolutional code is taken over R ( ( z ) ) or R ( z ) , it follows from the above observation that any convolutional encoder is equivalent to a polynomial encoder, which, in turn, defines a submodule of R [ z ] n .
Definition 4.
Let k n N . The R [ z ] -submodule of R [ z ] n given by
I m ( G ( z ) · ) = { v ( z ) = G ( z ) · u ( z ) : u ( z ) R [ z ] k }
where G ( z ) is a ( k , n ) polynomial convolutional encoder whose rows are free over R [ z ] , is called a ( k , n ) (polynomial) convolutional code over R.
Any convolutional encoder over R ( ( z ) ) or R ( z ) defines a convolutional code in the sense of Definition 4 by erasing denominators and taking its image as a homomorphism of R [ z ] -modules. However, it is important to note that not every polynomial convolutional encoder over R ( ( z ) ) or R ( z ) of the same convolutional code defines the same polynomial convolutional code. This happens because two equivalent polynomial encoders G ( z ) , G ( z ) over R ( ( z ) ) or R ( z ) might not be equivalent as convolutional encoders for polynomial convolutional codes. For example, ( 1 + z ) and ( 1 ) are equivalent convolutional encoders over R ( ( z ) ) but not over R [ z ] .
In the sequel, we only consider polynomial convolutional encoders and Definition 4 for convolutional code over a ring R.
One of the main features of a polynomial convolutional encoder is its degree, δ , which is closely related to the number of memory containers needed to realize it. This concept was first defined for convolutional codes over finite fields in [28] and generalized to commutative rings in [29].
Definition 5.
Let k n N and let G ( z ) R [ z ] n × k be a polynomial convolutional encoder. Its i-th constraint length, ν i , is defined as the maximum degree of the components of its i-th column. Its degree or complexity is defined as δ G ( z ) : = i = 1 k ν i . The memory of G ( z ) is defined as the maximum among the ν i s. We may assume without loss of generality that ν 1 ν k .
Let G ( z ) be a ( k , n ) polynomial convolutional encoder, and let u ( z ) R [ z ] k be an information word, where u ( z ) = ( u 1 ( z ) , , u k ( z ) ) . Let us denote by θ ( v ( z ) ) the maximum degree of the components of the code word v ( z ) = G ( z ) · u ( z ) . For the sake of notation, we drop the dependency of v ( z ) on the above notation if there is no risk of confusion. Then, we clearly have θ max { deg ( u i ( z ) ) + ν i } , where d e g ( u i ) stands for the degree of each component of u ( z ) .
Finally, we recall several properties of polynomial convolutional encoders. The relation between some of these properties in a specific ring is shown in [20]. Here, we include the needed properties for general rings in order to show some results in the following sections. These definitions are the usual ones when the base ring is a finite field (Definitions 4 and 5 in [28]).
Definition 6
(Section IIIA, [21]). A polynomial convolutional encoder G ( z ) R [ z ] n × k is basic (or observable) if it has a polynomial right inverse, i.e., Coker ( G ( z ) · ) is a projective R [ z ] -module. Equivalently, if the following exact sequence
0 R [ z ] k G ( z ) · R [ z ] n Coker ( G ( z ) ) = R [ z ] n / C 0
splits.
Remark 1.
Note that the above property is equivalent to saying that a convolutional code C is observable if the quotient R [ z ] n / C is a flat R [ z ] -module of constant rank n k . If R is a principal ideal ring, then a ( k , n ) convolutional code over R, C R [ z ] n is observable if and only if there exists a surjection ψ : R [ z ] n R [ z ] n k 0 such that K e r ( ψ ) = C . This follows from [30].
Definition 7
([31]). A polynomial encoder G ( z ) is minimal if δ G ( z ) is the minimum among the degrees of its equivalent polynomial encoders. It is minimal–basic if it is both minimal and basic.
All the above definitions also make sense when we consider general polynomial matrices instead of just injective polynomial matrices, that is, polynomial convolutional encoders.

2.2. A Review of the Representations of Convolutional Codes over Finite Fields

Given a convolutional encoder G ( z ) R [ z ] n × k , a natural problem in convolutional coding theory is to find a linear dynamical control system Σ whose finite-support orbits coincide with the outputs of the encoder (the code words). That is, to find a dynamical system Σ that realizes the dynamics of the coding process.
To begin with, let us define what a state-space representation of a convolutional encoder is (see [21] for a more general definition).
Definition 8.
Let k n N and let G ( z ) R [ z ] n × k be a polynomial convolutional encoder of degree δ. A state-space representation of G ( z ) is a tuple of matrices A R δ × δ , B R δ × k , C R n × δ , D R n × k , such that, if u ( z ) = u t z t R [ z ] k and y ( z ) = y t z t R [ z ] n , then G ( z ) u ( z ) = y ( z ) if and only if there exists x ( z ) = x t z t R [ z ] δ with
x t + 1 = A · x t + B · u t v t = C · x t + D · u t x 0 = 0
A state-space representation of a convolutional encoder G ( z ) is minimal if among all possible state-space representations of the same G ( z ) , the dimension δ is the smallest possible.
In case the base ring is a finite field, a representation as defined in Equation (1) is sometimes known as driven variable representation, since the input u ( z ) drives the output v ( z ) . There is, however, another kind of representation in which k components of the output drive the remaining n k components, and it is called the input/state/output representation, or just I/S/O representation for short [6,32]. I/S/O representations have already been defined for convolutional codes over noetherian von Neumann rings (finite product of fields) and used to construct concatenated convolutional codes [26,27].
Definition 9
([27]). Let C R [ z ] n be a ( k , n ) convolutional code. An I/S/O representation of C is a tuple of matrices A R δ × δ , B R δ × k , C R n k × δ , D R n k × k , δ being the degree of any of the minimal encoders of C , such that
C = v ( z ) = y ( z ) u ( z ) R [ z ] ( n k ) + k : x ( z ) R [ z ] δ satisfying x t 1 = A · x t + B · u t y t = C · x t + D · u t x deg ( v ( z ) ) = 0 .
Observe that, defining the matrices
K : = Id 0 , L : = A C , M : = 0 B Id D ,
we can state:
(i)
C = { v ( z ) R [ z ] n : x ( z ) R [ z ] δ such that z K x ( z ) + L x ( z ) + M v ( z ) = 0 } .
(ii)
K is injective.
(iii)
( K , M ) is surjective.
Definition 10
([27]). A triple ( K , L , M ) satisfying properties (i), (ii) and (iii) is called a first-order representation of the code C . If ( K , L , M ) also satisfy the property (iv) ( z K + L , M ) is surjective, then it is said that it is minimal.
Remark 2.
There are some comments regarding first-order and I/S/O representations for convolutional codes, in the case the base ring is a finite field, that need to be pointed out.
1 
Let C R [ z ] n × k be a ( k , n ) convolutional code. When the base ring R is a field, there always exists a permutation σ S n of n elements such that C : = σ ( C ) admits an I/S/O representation ([32]). The way to find an I/S/O representation is as follows: first, one computes a first-order representation ( K , L , M ) (the proof of the existence theorem is constructive) and then, one makes elementary operations over the matrices ( K , L , M ) to obtain a triple of matrices ( K , L , M ) such that
K = I δ O , L = A C and M = O B I ( n k ) D .
The system Σ = ( A , B , C , D ) is an I/S/O representation of the convolutional code C = σ ( C ) for the permutation σ.
2 
If we consider a ( k , n ) convolutional code C F [ z ] n of complexity δ admitting a minimal first-order representation, then the convolutional code C is described by a minimal I/S/O representation, Σ, that is a reachable linear system. From this point of view, if we consider a reachable and observable linear system Σ over a finite field, we can obtain an observable convolutional code, that is usually denoted by C ( A , B , C , D ) = C ( Σ ) [3,6,32].
3 
The first-order representations for convolutional codes over finite fields are constructed from the fact that G h is injective. The matrix G h is defined as follows: regarding G ( z ) F [ z ] n × k as a polynomial with coefficients in the vector space of matrices of size n × k with coefficients in F , G h is the coefficient of higher order in G ( z ) . The above condition that G h is injective implies that G ( z ) is minimal in the case where the base ring is a field (Theorem 2.22, Theorem 2.28, [33]), but this is no longer true for a general ring.
4 
Given a linear dynamical system as in Equation (2), we define its transfer function matrix as T ( z ) = C ( z 1 · I A ) 1 · B + D , T ( z ) i j R r ( z ) . The importance of the transfer function matrix is that it determines the input–output relation of the linear dynamical system. Observe that the existence of an I/S/O representation for a given convolutional code implies that codewords can be represented as
v ( z ) = y ( z ) u ( z ) ,
with u ( z ) being an information word. In fact, if a convolutional code admits an I/S/O representation, then it admits a convolutional encoder G ( z ) that has a full-size minor which is invertible in the ring of total fractions Q ( R [ z ] ) , so that G ( z ) is equivalent (in the sense of Definition 3 for A = Q ( R [ z ] ) ) to
T ( z 1 ) I .
Any convolutional code admitting an encoder of the above type is called systematic. Note that the above remark concludes that the systematicity of the encoder of a convolutional code is a necessary condition for the code to admit an I/S/O representation. In the case of finite fields, every convolutional code is systematic (Appendix II, Theorem 9, [28]).
In order to obtain a minimal first-order representation for convolutional codes over rings, we have to take into account that, for a general ring R, not every convolutional code admits either a minimal–basic convolutional encoder nor a systematic convolutional encoder. These two properties are analyzed in the following sections.

3. On the Predictable Degree Property of Polynomial Encoders

The predictable degree (PDP) of a polynomial matrix G ( z ) R [ z ] n × k was introduced by G. D. Forney in [34]. In general, deg ( G ( z ) u ( z ) ) max { deg ( u i ( z ) ) + deg ( G i ( z ) ) } . Here, the degree of a polynomial vector means the maximum degree of its components, and G i ( z ) denotes the i-th column of G ( z ) . Saying that G ( z ) has the PDP means that the above inequality is an equality for any u ( z ) . In terms of convolutional coding theory, this means that the degree of a code word G ( z ) u ( z ) can be predicted from the degrees of the components of the information word u ( z ) and the constraint lengths of G ( z ) .
Remark 3.
If G ( z ) is a polynomial convolutional encoder over a finite field, then the following statements are equivalent (Theorem 2.22, Theorem 2.28, [33]):
1 
G ( z ) has the PDP; that is,
θ = m a x { d e g ( u i ( z ) ) + ν i }
for every information word u ( z ) with finite-support (Section 2.5, [33]).
2 
It is minimal–basic, i.e., it is minimal and it is also basic.
3 
G h is injective.
4 
δ G ( z ) = the maximum degree of the full-size minors of G ( z ) .
When we work over a general base ring, the above characterization of the PDP is not true. One can find easy examples of convolutional encoders with PDP which are not minimal–basic and vice versa.
Example 1.
1 
In the case where R is not a field, we can find easy examples of minimal–basic convolutional encoders that do not have PDP. For instance, consider the convolutional encoder G ( z ) = 2 z 1 over R = Z 4 . It is clearly basic, since r = ( 2 , 1 ) : R [ z ] 2 R [ z ] is a retract for G ( z ) , and it is obviously minimal. However, G h = 2 0 is not injective.
2 
We can also find easy examples of convolutional encoders with PDP that are not basic. Consider the following: over R = Z 4 the convolutional encoder with PDP given by G ( z ) = 2 2 + z . If G ( z ) were basic, then we could find a matrix H ( z ) = ( s ( z ) , t ( z ) ) : R [ z ] 2 R [ z ] such that H ( z ) G ( z ) = 1 . This would mean, in particular, that 2 · s 0 + 2 · t 0 = 1 , and this would imply that 2 R is invertible, which is not true. Thus, G ( z ) is not basic.
Although the property of being minimal–basic does not imply the PDP when R is a general ring, we can prove an equivalence between this last property and the injectivity of G h .
Theorem 1.
Let k n N , G ( z ) R [ z ] n × k a polynomial matrix and G h the matrix of column-wise maximum degree coefficients. Then, G ( z ) has PDP if and only if G h is injective.
Proof. 
The direct implication can be proved as in the case of fields (see (Theorem 2.22, Theorem 2.28, [33])). Let us prove the inverse implication. Suppose that G ( z ) does not have the PDP, i.e., there is u ( z ) R [ z ] k such that
( deg ( v i ( z ) ) ) deg ( v ( z ) ) < max i { θ i + ν i }
where θ i : = deg ( u i ( z ) ) . Let ν 1 , , ν k be the constraint lengths of G ( z ) . Then,
v i ( z ) = g i 1 ( z ) u 1 ( z ) + + g i k ( z ) u k ( z ) = ( g i 1 ν 1 u 1 θ 1 ) z ν 1 + θ 1 + { lower degree terms } + + ( g i k ν k u k θ k ) z ν k + θ k + { lower degree terms } ,
where the g i t ν t may be zero or not. Suppose that
ν j 1 θ j 1 = = ν j l θ j l = max i { θ i + ν i }
Then, from Equations (5) and (6), we deduce that
g i j 1 ν j 1 u j 1 θ j 1 + + g i j l ν j l u j l θ j l = 0 , i = 1 , , n
Let u = ( 0 , , u j 1 θ j 1 , , 0 , , u j l θ j l , , 0 ) R k , which is non zero. Then, by Equation (7), we find that G h u = 0 , that is, G h is not injective. □
Corollary 1.
Let k n N , and G ( z ) = ( g i j ( z ) ) R [ z ] k × n be a polynomial matrix with PDP. Then, G ( z ) is injective, that is, it is a convolutional encoder.
Proof. 
Suppose G ( z ) is not injective. Then, there is a non-zero polynomial vector u ( z ) R [ z ] k such that 0 = G ( z ) u ( z ) . Let 1 t 1 , , t l k be those subindices such that deg ( u t j ( z ) ) + ν t j = max { deg ( u i ( z ) ) + ν i } for all j = 1 , , l . Denote d i = deg ( u i ( z ) ) , and let u = ( 0 , , u d t 1 , , 0 , , u d t l , , 0 ) R [ z ] k 0 , where u d t j is the maximum degree coefficient of u t j ( z ) . Then, we have G h u = 0 , which implies that u = 0 by Theorem 1, and this is not possible. □

4. On the Existence of Representations over Principal Ideal Artinian Rings

In this section, we prove that convolutional codes over principal ideal artinian rings admit minimal first-order representations, such as those defined in Section 2.
Before this, we need to recall some algebraic properties of this class of rings.
A commutative ring, R, is an artinian ring if it is a noetherian ring with Krull dimension zero. As a consequence, it has finitely many prime ideals, all of them being maximal. By the Structure Theorem of artinian rings, we know that
R = i = 1 t R m i
where R m i are local artinian rings. Observe that local artinian rings are noetherian rings with only one prime (therefore maximal) ideal. The rings Z p r , with p being a prime number, are typical examples of local artinian rings.
Artinian local rings can be easily characterized in terms of their nilradicals. More precisely, if R is a commutative ring with nilradical N , the following statements are equivalent:
1
R only has one prime ideal.
2
N is a maximal ideal.
3
Every element of R is either invertible or nilpotent.
This follows directly from the equality N = p R minimal       p .
This characterization shows that artinian local rings are those noetherian rings in which every element is either invertible or nilpotent.
Proposition 1.
Let R be an artinian ring. The following statements hold:
C1 
If P is a finitely generated projective module of constant rank n, then it is free.
C2 
If R is a principal ideal ring and G : R k R n is an injective matrix, then Coker ( G ) is flat.
Proof. 
1
By Equation (8), we know that P = P m 1 × × P m t . Now, the result follows from (Theorem 2, [35]).
2
Since flatness is a local property, we may assume that R is local. Let G = ( g i j ) : R k R n be an injective matrix. Injectivity implies that Ann R ( < M 1 , , M t > ) = ( 0 ) , where M 1 , , M t are the full-size minors of G. Since every ideal of R is principal, we deduce that Ann R ( < M > ) = ( 0 ) , where < M 1 , , M t > = < M > , and M R . This implies that M is not a zero divisor and, therefore, is invertible in R, so < M 1 , , M t > = R . By Proposition 1.1, [36], this implies that Coker ( G ) is flat of rank n k .
Given a polynomial matrix G ( z ) R [ z ] n × k and a prime ideal p R , we denote by G ( p ) ( z ) the restriction of G ( z ) to p , which is the matrix whose ( i , j ) entry is given by
G ( p ) ( z ) i j = g i j ( z ) 1 mod ( p R p ) k ( p ) [ z ] ,
where k ( p ) = R p / p R p is the residue field of p .
The following result generalizes the Existence Theorem for first-order representations over finite fields (Theorem 5.1.1, [32]).
Theorem 2.
Let k n N , R a principal ideal artinian ring and G ( z ) R [ z ] n × k a convolutional encoder with PDP. Then, the convolutional code C : = I m ( G ( z ) ) admits a minimal first-order representation.
Proof. 
For any polynomial p ( x ) = a 0 + a 1 z + + a l z l R [ z ] , we will use the following notation p ( x ) = ( a 0 , a 1 , , a l ) R 1 × ( l + 1 ) . Consider the matrix X ( z ) R [ z ] δ × k given by
X ( z ) = e 1 0 0 0 e 2 0 0 0 e k , where e i = 1 z z 2 z ν i 1 ,
and let Δ R ( 2 δ + n ) × ( δ + k ) be the matrix
Δ = z · X ( z ) X ( z ) G ( z ) R ( 2 δ + n ) × ( δ + k ) .
The matrix Δ is surjective, so we can form the exact sequence
0 Ker ( · Δ ) R 2 δ + n · Δ R δ + k 0 .
This exact sequence always splits, so Ker ( · Δ ) is a finitely generated projective R-module of constant rank δ + n k . By property C 1 , we deduce that Ker ( · Δ ) is in fact free, so we can construct a matrix
K L M R ( δ + n k ) × ( 2 δ + n ) ,
formed by the ( δ + n k ) row vectors of a base of Ker ( · Δ ) , which can be expressed in pencil form
z · K + L , M X ( z ) G ( z ) .
We complete the proof in several steps.
Step 1: Let p R be a prime ideal and let k ( p ) = R p / p R p be its residue field. From Proposition 1, condition C2, the PDP and Remark 3, we deduce that G ( p ) ( z ) k ( p ) k × n is a convolutional encoder with PDP.
Step 2: From Equations (10) and (11), we can form the exact sequence
0 R δ + n k · ( K L M ) R 2 δ + n · Δ R δ + k 0 .
Since R δ + k is free, and therefore flat, this exact sequence remains exact after extending scalars R k ( p ) . This fact, together with the conclusion obtained in Step 1 and Theorem 5.1.1, [32], shows that ( K ( p ) , L ( p ) , M ( p ) ) is a minimal first-order representation for G ( p ) ( z ) . Therefore, K , L , M satisfy properties (ii) and (iii) and (iv) of Definition 10 over each residue field.
Step 3: Recall that a morphism of modules is surjective if and only if it is residually surjective, and that a residually injective morphism of modules is, in fact, injective. Therefore, K is injective because K ( p ) is injective for all prime ideals, ( K , M ) is surjective because ( K ( p ) , M ( p ) ) is surjective for all prime ideals, and ( z K + L , M ) is surjective because, for every primer ideal p R , its reduction modulo p is surjective.
Step 4: To complete the proof, it only remains to show the property (i) of Definition 10. To do so, let us start by pointing out a simple but important observation. The matrix X ( z ) | 0 k × n is a retract for the matrix X ( z ) G ( z ) , that is, S · X ( z ) G ( z ) = Id k . Since ( z · K + L , M ) is surjective, we can construct the diagram
Mathematics 09 02962 i002
Now, because of Equation (12), X ( z ) G ( z ) factorizes through Ker ( ( z · K + L , M ) ) , and we denote the resulting homomorphism by Ψ . Then,
( S ι ) Ψ = S ( ι Ψ ) = S · X ( z ) G ( z ) = Id k ,
which means that S ι : Ker ( ( z · K + L , M ) ) [ ] R [ z ] k is a retract for Ψ . Observe now, that the exact sequence in (13) splits, so Ker ( ( z · K + L , M ) ) is a finitely generated projective R [ z ] -module of constant rank k. Then, since S ι is surjective, we know that Ker ( S ι ) is finitely generated and projective, and for each maximal ideal M R [ z ] , Ker ( S ι ) / M Ker ( S ι ) = 0 . By Nakayama’s Lemma, Ker ( S ι ) M = 0 for all maximal ideals, so Ker ( S ι ) = 0 . We finally conclude that
Im X ( z ) G ( z ) = Ker ( z · K + L , M ) ,
from which, we obtain property (i) of Definition 10. Thus, ( K , L , M ) is a minimal first-order representation for G ( z ) . □
Remark 4.
Let k n N , R a principal ideal artinian ring and G ( z ) R [ z ] k × n a convolutional encoder with PDP. If ( K , L , M ) is a first-order representation of I m ( G ( z ) ) , then ( K ( p ) , L ( p ) , M ( p ) ) is a first-order representation of I m ( G ( p ) ( z ) ) for each p S p e c ( R )
Remark 5.
Observe that what we have proved is that the same construction method to find minimal first-order representations known in the case of fields ([32]) is also valid for commutative rings that satisfy the propertiesC1andC2. In particular, these properties are satisfied by any zero-dimensional ring, R, that satisfies one of the following conditions: (1) R is a noetherian, and therefore artinian, and principal ideal ring, or (2) R is a reduced ring, and hence von Neumann.
Now, our aim is to prove the existence of I/S/O representations for convolutional codes over a principal ideal artinian ring. Recall from the classical theory of convolutional codes that I/S/O representations are not assigned to convolutional codes but to equivalence classes of them. That is, given a convolutional code C F [ z ] n , there is a permutation σ S n such that the (equivalent) convolutional code σ ( C ) can be represented by an I/S/O representation. We show that the same result can be proved in the case that the principal ideal artinian ring R is local. If R is not local, the equivalence relation defined for codes (through permutations) has to be weakened in order to obtain an analogous result.
First, recall from Remark 2 that we have to show that every convolutional code over a principal ideal local ring is systematic.
Definition 11.
A systematic convolutional encoder is a convolutional encoder G ( z ) R [ z ] k × n that has a full-size minor which is invertible in the total ring of fractions Q ( R [ z ] ) . A systematic convolutional code C R [ z ] n is a convolutional code that admits a systematic convolutional encoder.
Proposition 2.
Any polynomial convolutional encoder G ( z ) R [ z ] n × k over a principal ideal artinian local ring R is systematic.
Proof. 
Let G ( z ) R [ z ] n × k be a ( k , n ) polynomial convolutional encoder. Since it is injective, we know that Ann R [ z ] ( < M 1 ( z ) , , M l ( z ) > ) = 0 , where M 1 ( z ) , M l ( z ) R [ z ] are the non-zero full-size minors of G ( z ) . Suppose that M i ( z ) is a zero divisor for every i = 1 , , l . Then, for every i = 1 , , l , there is an element r i R such that r i · M i ( z ) = 0 . Since R is a principal ideal artinian local ring, the nilradical is the unique prime ideal; it is generated by an element π R , and there is a natural number θ > 0 such that π θ = 0 . Then, r i · M i ( z ) = 0 implies that
r i = λ i π t i , λ i R * , t i > 0 , m i j = μ j π s i j , μ j R * , s i j 0 , t i + s i j θ .
Here m i j is the jth order coefficient of M i ( z ) . Let r R be the element among the r i s with maximum exponent t i . Then,
r · M i ( z ) = 0 , i = 1 , , l ,
which, in turn, implies that 0 r Ann R [ z ] ( < M 1 ( z ) , , M l ( z ) > ) . Since this is not possible, we deduce that there exists a full-size minor, M i ( z ) , which is not a zero divisor. □
Remark 6.
Note that Proposition 2 is not true if we drop the condition of being local. For instance, consider the ring R = Z 2 × Z 3 . This is a principal artinian non-local ring. Additionally, consider the matrix
G ( z ) = 2 z 3 z .
It is clearly a convolutional encoder with PDP. However, both 2 z and 3 z are zero divisors and, therefore, not invertible in Q ( R [ z ] ) , so G ( z ) is not systematic.
Before proving the main results, we give some definitions about equivalence between convolutional codes over R .
Definition 12.
Let R be a commutative ring. Two ( k , n ) convolutional codes, C , C R [ z ] n , are equivalent if there is a permutation σ S n of n elements such that σ ( C ) = C .
Definition 13.
Let R be a commutative ring. Two convolutional codes, C , C R [ z ] n , are locally equivalent if for any prime ideal p S p e c ( R ) , C p and C p are equivalent.
Definition 14.
Let R be a commutative ring. Two convolutional encoders, G ( z ) , G ( z ) R [ z ] n × k , are weakly (locally) equivalent if C : = I m ( G ( z ) ) is (locally) equivalent to C : = I m ( G ( z ) ) .
Accordingly, G ( z ) and G ( z ) are weakly equivalent if and only if there is a permutation σ S n of n elements and an invertible matrix P GL k ( R [ z ] ) such that G ( z ) = σ · G ( z ) · P .
Now, we prove the existence of I/S/O representations for principal ideal artinian rings.
Theorem 3.
For any convolutional encoder G ( z ) R [ z ] n × k with PDP over a principal ideal artinian local ring, there is a permutation σ S n such that σ ( Im ( G ( z ) ) ) admits an I/S/O representation.
Proof. 
Let G ( z ) R [ z ] n × k be a convolutional encoder with PDP and degree δ . By Theorem 2, we can find a minimal first-order representation ( K , L , M ) of Im ( G ( z ) ) . Moreover, we can assume that ( K ( m ) , L ( m ) , M ( m ) ) is a minimal first-order representation of the convolutional encoder G ( m ) ( z ) k ( m ) [ z ] n × k (see proof Remark 4), where m is the unique prime ideal of R. From Section 5.2, [32], we know that, after a permutation of the code words of G ( z ) (let us denote such a permutation by σ S n ), the full-size minor, det ( F ) , of ( K , M ) consisting of the first δ + n k columns, satisfies the condition that F mod ( m ) k ( m ) ( δ + n k ) × ( δ + n k ) is invertible, where k ( m ) = R / m is the residue field. This implies that det ( F ) m , which means that F R ( δ + n k ) × ( δ + n k ) is invertible because R is a principal ideal artinian ring. Then, the matrix F 1 ( K , L , M ) takes the form
Id δ A 0 B 0 C Id n k D ,
and clearly, A R δ × δ , B R δ × k , C R n k × δ , D R n k × k form an I/S/O representation of Im ( σ ( G ( z ) ) ) = σ ( Im ( G ( z ) ) ) . □
Remark 7.
Let k n N , R a principal ideal artinian ring and G ( z ) R [ z ] k × n a convolutional encoder with PDP. If Σ is an I/S/O representation of I m ( G ( z ) ) , then Σ ( p ) = ( A ( p ) , B ( p ) , C ( p ) , D ( p ) ) is an I/S/O representation of I m ( G ( p ) ( z ) ) for each p S p e c R ) . This follows from Remark 4.
Corollary 2.
For any convolutional encoder G ( z ) with PDP over a principal ideal artinian ring, there is a locally weakly equivalent encoder G ( z ) such that C : = I m ( G ( z ) ) admits I/S/O representation.
Proof. 
Let G ( z ) be a convolutional encoder with PDP and degree δ , and let Spec ( R ) = { m 1 , , m q } be the set of prime (in fact maximal) ideals. For each i = 1 , , q , R i : = R m i is a principal ideal local artinian ring, so, by Theorem 3, there are permutations σ m 1 , , σ m q S n such that the convolutional code over R m i defined by the convolutional encoder
σ m q ( G ( z ) ) 1 R m i [ z ] n × k
admits an I/S/O representation. Now, let σ GL n ( R ) be the unique invertible matrix such that σ m i = σ 1 GL n ( R m i ) . Then, Im ( σ · G ( z ) ) is locally equivalent to Im ( G ( z ) ) . □
The case of the ring of modular integers Z M is of particular interest in convolutional coding theory over commutative rings. These rings are principal ideal artinian rings. Observe that Theorem 3 (respectively, Corollary 2) shows, in particular, that any convolutional code with PDP over a ring of modular integers Z p r with p a prime number (respectively, Z M with M a natural number) is equivalent (respectively, locally equivalent) to a convolutional encoder with a I/S/O representation.
Example 2.
Let G ( z ) be the following PDP encoder of a ( n = 3 , k = 2 , δ = 4 ) convolutional code C over Z 8 .
G ( z ) = 1 + z 2 1 + z + 4 z 2 5 + 4 z 3 + 6 z + 3 z 2 2 z + z 2 z .
From G ( z ) we obtain the triple of matrices ( K L M ) .
K = 7 0 0 0 0 0 7 0 0 7 7 4 4 0 2 5 6 6 1 0 , L = 0 1 0 0 0 0 0 1 7 0 7 0 3 0 5 0 0 0 0 0 , M = 0 0 0 0 0 0 1 0 0 0 1 0 0 0 1
Since
7 0 0 0 0 0 0 7 0 0 0 7 7 4 1 4 0 2 5 0 6 6 1 0 0 = 6
and 6 Z 8 * , we can not obtain the I/S/O representation. We perform the permutation σ = 1 2 3 2 3 1 in G ( z ) ,
G ( z ) = 2 z + z 2 z 1 + z 2 1 + z + 4 z 2 5 + 4 z 3 + 6 z + 6 z 2 .
From G ( z ) , we obtain the triple of matrices ( K L M ) .
K = 7 0 0 0 0 0 7 0 6 7 7 0 0 7 7 4 4 0 2 5 , L = 0 1 0 0 0 0 0 1 0 0 0 0 7 0 7 0 3 0 5 0 , M = 0 0 0 0 0 0 1 0 0 0 1 0 0 0 1 .
Since
7 0 0 0 0 0 0 7 0 0 7 7 7 0 1 0 7 7 4 0 4 0 2 5 0 = 5 ,
and 5 Z 8 * , we can obtain the I/S/O representation. In fact, we compute
K = 7 0 0 0 0 7 0 0 0 0 7 0 0 0 0 7 0 0 0 0 , L = 0 1 0 0 3 0 3 7 0 0 0 1 1 4 7 6 3 2 3 0 , M = 0 0 0 0 1 4 0 0 0 0 0 3 7 1 4 .
From the above first-order representation, we obtain
Σ = A = 0 1 0 0 3 0 3 7 0 0 0 1 1 4 7 6 , B = 0 0 1 4 0 0 0 3 , C = 3 2 3 0 , D = 1 4 .
Example 3.
Let G ( z ) be the following PDP encoder of a ( n = 4 , k = 2 , δ = 6 ) convolutional code C over Z 4 .
G ( z ) = 1 + z + z 3 0 0 1 + z + z 3 1 + z 2 + z 3 1 + z + z 2 + z 3 1 + z 3 1 + z 2 .
From G ( z ) , we obtain the triple of matrices ( K L M ) .
K = 3 0 0 0 0 0 0 3 0 0 0 0 0 0 0 3 0 0 0 0 0 0 3 0 3 0 3 0 0 0 0 0 0 3 0 3 0 3 3 3 3 3 0 0 3 0 3 0 , L = 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 3 0 0 0 0 0 0 0 0 3 0 0 3 0 0 3 0 0 3 0 0 3 0 0 , M = 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1
Since
3 0 0 0 0 0 0 0 0 3 0 0 0 0 0 0 0 0 0 3 0 0 0 0 0 0 0 0 3 0 0 0 3 0 3 0 0 0 1 0 0 0 0 3 0 3 0 1 0 3 3 3 3 3 0 0 0 0 3 0 3 0 0 0 = 3
and 3 Z 4 * , we can obtain the I/S/O representation. In this case,
K = 3 0 0 0 0 0 0 3 0 0 0 0 0 0 3 0 0 0 0 0 0 3 0 0 0 0 0 0 3 0 0 0 0 0 0 3 0 0 0 0 0 0 0 0 0 0 0 0 , L = 0 1 0 0 0 0 0 0 1 0 0 0 3 0 0 3 0 3 0 0 0 0 1 0 0 0 0 0 0 1 0 0 3 0 3 0 0 1 0 3 0 3 0 0 3 3 0 0 , M = 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 3 3 0 0 1 0 3 1 3 .
From the above first-order representation, we obtain
Σ = A = 0 1 0 0 0 0 0 0 1 0 0 0 3 0 0 3 0 3 0 0 0 0 1 0 0 0 0 0 0 1 0 0 3 0 3 0 , B = 0 0 0 0 0 0 0 1 0 0 0 0 1 3 , C = 0 1 0 3 0 3 0 0 3 3 0 0 , D = 0 1 1 3 .

5. Minimal I/S/O Representations: Reachability and Observability

Minimality is one of the most important properties of an I/S/O representation of a convolutional code. An I/S/O representation is minimal when it has the smallest dimension among all I/S/O representations of the code. These representations require less memory space in their implementations, which provides more efficiency. The problem of the existence of minimal representations was initially highlighted in the case of quaternary convolutional codes over Z 4 and their trellis representations ([29]). After this, the minimality problem of I/S/O representations over finite fields was solved in [3,6] through the reachability property (controllability in coding literature) of the associated linear system. In general, the minimality problem is hard to solve, and each case needs to be studied. In the case of convolutional codes over finite rings, the minimality of the I/S/O representation is achieved by the reachability of the system. For instance, the necessary and sufficient conditions for the minimality of the state-space model for basic 2D convolutional codes over finite fields were found by a property of strongly modally reachability in [37], or by separable Roesser models for 2D periodic convolutional codes in [38].
We review a result about reachability properties of systems over commutative rings with identity that let us prove the minimality of I/S/O representations of convolutional codes over principal ideal artinian rings.
Proposition 3
(Theorem 2.3, [39] and Proposition 2.1, [26]). Let Σ = ( A , B , C , D ) R δ × δ × R δ × k × R n × δ × R n × k be a linear system over R. The following statements are equivalent:
(1)
Σ is reachable.
(2)
The columns of Φ δ = B A B A δ 1 B generate R δ .
(3)
The map ϕ: R k δ R δ given by multiplication by Φ δ is residually surjective at each maximal ideal m of R.
(4)
The ideal U δ ( Φ δ ) generated by the δ × δ minors of Φ δ equals R.
(5)
The map ( z I A , B ) : R [ z ] δ + k R [ z ] δ is surjective.
Theorem 4.
Let C be a ( k , n , δ ) be a convolutional code over a principal ideal artinian ring R. Let Σ = ( A , B , C , D ) R δ × δ × R δ × k × R n k × δ × R n k × k be an I/S/O representation of C . Then, Σ is a reachable linear system.
Proof. 
Follows from Remark 4, Remark 7 and Proposition 3 (5). □
Example 4.
Let G ( z ) be the PDP encoder
G ( z ) = 1 + z 2 1 + z + 4 z 2 5 + 4 z 3 + 6 z + 3 z 2 2 z + z 2 z .
The encoder generates a ( n = 3 , k = 2 , δ = 4 ) convolutional code, C , over Z 8 , whose I/S/O representation was obtained in Example 2. Since
r a n k B A B A 2 B A 3 B = r a n k 0 0 1 4 0 5 7 3 1 4 0 5 7 3 3 4 0 0 0 3 4 2 1 1 0 3 4 2 1 1 6 5
is maximum because
| Φ 4 | = 0 0 1 4 1 4 0 5 0 0 0 3 0 3 4 2 = 7
is invertible in Z 8 , we deduce that Σ is reachable and, hence, a minimal I/S/O representation of C .
Example 5.
Consider now the encoder given in Example 3 and its I/S/O representation. Note that
B A B A 2 B A 3 B A 4 B A 5 B = 0 0 0 0 0 1 3 1 0 1 3 0 0 0 0 1 3 1 0 1 3 0 1 0 0 1 3 1 0 1 3 0 1 0 3 3 0 0 0 0 1 3 0 3 0 0 0 0 0 0 1 3 0 3 0 0 0 0 1 0 1 3 0 3 0 0 0 0 1 0 3 0 .
Since
| Φ 6 | = 0 0 0 0 0 1 0 0 0 1 3 1 0 1 3 1 0 1 0 0 0 0 1 3 0 0 1 3 0 3 1 3 0 3 0 0 = 1 ,
r a n k B A B A 2 B A 3 B A 4 B A 5 B is maximum, so the I/S/O representation given in Example 3 is minimal.

Construction of Observable Convolutional Codes over R

We recall the following result regarding observability property.
Proposition 4
(Theorem 2.6, [39]). Let Σ = ( A , B , C , D ) R δ × δ × R δ × k × R n × δ × R n × k be a linear system over R. The following statements are equivalent.
(1)
Σ is observable.
(2)
Let Ω δ = [ C , C A , . . . , C A δ 1 ] t (here, we mean the block transpose of the matrix [ C , C A , . . . , C A δ 1 ] ) be the observability matrix. Then, r a n k ( Ω δ ) = δ .
(3)
The map τ: R δ R p δ given by multiplication by Ω δ is injective.
(4)
If U δ ( Ω δ ) is the ideal of R generated by the δ × δ minors of Ω δ , then the annihilator of U δ ( Ω δ ) is zero.
Theorem 5.
Let R be a principal ideal artinian ring. Let Σ = ( A , B , C , D ) R δ × δ × R δ × k × R n k × δ × R n k × k be a reachable and observable linear system over R. We construct the triple of matrices ( K , L , M ) as follows:
K = I δ O , L = A C   and   M = O B I ( n k ) D
and we consider the associated convolutional code C obtained by K e r ( z K + L M ) . Then, C is observable.
Proof. 
Follows from Remark 4, Remark 7, Proposition 1 (2), Proposition 4 (3) and Lemma 5.3.5 in [32]. □
Example 6.
Let Σ be the following linear systems over Z 8
Σ = A = 1 3 0 1 , B = 5 1 4 7 , C = 1 5 , D = 0 1 .
Since the two first columns of Φ 2 generate Z 8 2 because
Φ 2 = B A B = 5 1 1 6 4 7 4 7 ;
then, Σ is reachable. Furthermore, since
Ω 2 = C C A t = 1 1 5 0 ,
then, Σ is observable because Ω 2 = 3 Z 8 * . From Σ, we compute the first-order representation
K = 7 0 0 7 0 0 , L = 1 3 0 1 1 5 , M = 0 5 1 0 4 7 7 0 1 .
Finally, we obtain the associated ( 3 , 2 , 2 ) convolutional encoder by K e r ( z K + L M ) :
G ( z ) = 4 z 1 3 z + 6 z 1 z + 4 4 z 4 3 z + 1 .
This is an observable convolutional encoder since the full-size minors of G ( z ) , U i , generate the ring; that is, there exist λ 1 , λ 2 and λ 3 such that λ 1 · U 1 + λ 2 · U 2 + λ 3 · U 3 ( Z 8 [ z ] ) * : 1 · ( z 2 + 2 z + 2 ) + 4 · ( z + 5 ) + 1 · ( 7 z 2 + 2 z + 7 ) = 5.

6. Conclusions

In this work, we proved several results that let us extend the relation between convolutional codes and I/S/O representations known in classical convolutional coding theory to convolutional codes defined over a principal ideal artinian rings, such as Z p r .
First of all, we demonstrated the existence of first-order representations for convolutional codes with the PDP over any principal ideal artinian ring. Secondly, this first-order representation allows us to obtain, when the base ring is local, an I/S/O representation Σ for the (equivalence class of the) code. The local property of the ring ensures that every polynomial convolutional encoder of the code is systematic, a necessary condition to obtain Σ . Since Σ determines a reachable linear system, we can conclude that the representation is minimal. Furthermore, we proved that we can weaken (in a natural way) the equivalence relation for codes in such a way that the same result obtained in the local case is also true in the non local case. Finally, we showed that we can construct observable convolutional codes over principal ideal artinian local rings from reachable and observable linear systems as is carried out in classical convolutional theory. All the results can be applied over Z M , where M is a positive integer.
There are two interesting applications of the existence of an I/S/O in classical convolutional coding theory. On the one hand, one can derive (algebraic) decoding algorithms for convolutional codes based on I/S/O representations. On the other hand, I/S/O representations have proven to be very useful in the study of the different notions of distances (free distances, column distances, etc.) in classical convolutional coding theory.
The results of this work suggest that these two problems, in the theory of convolutional codes over principal ideal artinian rings, could be tackled in the same way as has been done in classical theory.
Furthermore, it would be interesting to see if the results presented in this article can be used to design good component codes for Turbo codes.

Author Contributions

Conceptualization, Á.L.M.C., N.D.-G. and M.V.C.; methodology, Á.L.M.C., N.D.-G. and M.V.C.; investigation, Á.L.M.C., N.D.-G. and M.V.C.; writing–original draft preparation, Á.L.M.C., N.D.-G. and M.V.C.; writing–review and editing, Á.L.M.C., N.D.-G. and M.V.C.; visualization, Á.L.M.C., N.D.-G. and M.V.C.; supervision, Á.L.M.C., N.D.-G. and M.V.C.; project administration, Á.L.M.C., N.D.-G. and M.V.C.; funding acquisition, Á.L.M.C., N.D.-G. and M.V.C.; All authors have read and agreed to the published version of the manuscript.

Funding

This research received no external funding.

Institutional Review Board Statement

Not applicable.

Informed Consent Statement

Not applicable.

Data Availability Statement

Not applicable.

Conflicts of Interest

The authors declare no conflict of interest.

References

  1. McEliece, R.L. The algebraic theory of convolutional codes. In Handbook of Coding Theory I; Springer: Berlin, Germany, 1998; pp. 1065–1138. [Google Scholar]
  2. Massey, J.; Sain, M. Codes, automata, and continuous systems: Explicit interconnections. IEEE Trans. Autom. Control 1967, 12, 644–650. [Google Scholar] [CrossRef]
  3. Rosenthal, J.; York, F. BCH convolutional codes. IEEE Trans. Inf. Theory 1999, 45, 1833–1844. [Google Scholar] [CrossRef] [Green Version]
  4. Kuijper, M.; Polderman, J. Reed-Solomon list decoding from a system-theoretic perspective. IEEE Trans. Inf. Theory 2004, 50, 259–271. [Google Scholar] [CrossRef] [Green Version]
  5. Rosenthal, J. Connections Between Linear Systems and Convolutional Codes. In Codes, Systems, and Graphical Models; Marcus, B., Rosenthal, J., Eds.; Springer: New York, NY, USA, 2001; pp. 39–66. [Google Scholar]
  6. Rosenthal, J.; Schumacher, J.; York, E. On behaviors and convolutional codes. IEEE Trans. Inf. Theory 1996, 42, 1881–1891. [Google Scholar] [CrossRef]
  7. Kuijper, M. First Order Representations of Linear Systems; Systems & Control: Foundations & Applications; Birkhäuser: Basel, Switzerland, 1994. [Google Scholar]
  8. Kuijper, M.; Schumacher, J. Realization of Autoregressive Equations in Pencil and Descriptor Form. SIAM J. Control Optim. 1990, 28, 1162–1189. [Google Scholar] [CrossRef] [Green Version]
  9. Willems, J.C. From time series to linear systems Part I. Finite dimensional linear time invariant systems. Automatica 1986, 22, 561–580. [Google Scholar] [CrossRef]
  10. Kitchens, B. Symbolic Dynamics and Convolutional Codes. In Codes, Systems, and Graphical Models; Marcus, B., Rosenthal, J., Eds.; Springer: New York, NY, USA, 2001; pp. 347–360. [Google Scholar]
  11. Climent, J.; Herranz, V.; Perea, C. A first approximation of concatenated convolutional codes from linear systems theory viewpoint. Linear Algebra Its Appl. 2007, 425, 673–699. [Google Scholar] [CrossRef] [Green Version]
  12. Climent, J.; Napp, D.; Pinto, R.; Simões, R. Series concatenation of 2D convolutional codes by means of input-state-output representations. Int. J. Control 2018, 91, 2682–2691. [Google Scholar] [CrossRef] [Green Version]
  13. Napp, D.; Perea, C.; Pinto, R. Input-state-output representations and constructions of finite support 2D convolutional codes. Adv. Math. Commun. 2010, 4, 533–545. [Google Scholar] [CrossRef] [Green Version]
  14. Napp, D.; Pereira, R.; Rocha, P. A State Space Approach to Periodic Convolutional Codes. In Coding Theory and Applications; Barbero, Á.I., Skachek, V., Ytrehus, ∅., Eds.; Springer International Publishing: Cham, Switzerland, 2017; pp. 238–247. [Google Scholar]
  15. Climent, J.; Napp, D.; Pinto, R.; Requena, V. Minimal State-Space Representation of Convolutional Product Codes. Mathematics 2021, 9, 1410. [Google Scholar] [CrossRef]
  16. Rosenthal, J. An Algebraic Decoding Algorithm for Convolutional Codes. In Dynamical Systems, Control, Coding, Computer Vision; Picci, G., Gilliam, D.S., Eds.; Birkhäuser Basel: Basel, Switzerland, 1999; pp. 343–360. [Google Scholar]
  17. Muñoz Castañeda, A.L.; Muñoz Porras, J.M.; Plaza-Martín, F.J. Rosenthal’s Decoding Algorithm for Certain 1-Dimensional Convolutional Codes. IEEE Trans. Inf. Theory 2019, 65, 7736–7741. [Google Scholar] [CrossRef]
  18. Massey, J.; Mittelholzer, T. Convolutional codes over rings. In Proceedings of the Joint Swedish-Soviet International Workshop on Information Theory, Gotland, Sweeden, 27 August–1 September 1989; pp. 14–18. [Google Scholar]
  19. Massey, J.; Mittelholzer, T. Systematicity Furthermore, Rotational Invariance Of Convolutional Codes Over Rings. In Proceedings of the International Workshop on Algebraic and Combinatorial Coding Theory, Svetlogorsk, Russia, 2–8 September 1990; pp. 154–158. [Google Scholar]
  20. Johannesson, R.; Zhe-Xian, W.; Wittenmark, E. Some structural properties of convolutional codes over rings. IEEE Trans. Inf. Theory 1998, 44, 839–845. [Google Scholar] [CrossRef] [Green Version]
  21. Fagnani, F.; Zampieri, S. System-theoretic properties of convolutional codes over rings. IEEE Trans. Inf. Theory 2001, 47, 2256–2274. [Google Scholar] [CrossRef]
  22. El Oued, M.; Napp, D.; Pinto, R.; Toste, M. On duals and parity-checks of convolutional codes over Zpr. Finite Fields Their Appl. 2019, 55, 1–20. [Google Scholar] [CrossRef]
  23. Kuijper, M.; Pinto, R. On Minimality of Convolutional Ring Encoders. IEEE Trans. Inf. Theory 2009, 55, 4890–4897. [Google Scholar] [CrossRef] [Green Version]
  24. Napp, D.; Pinto, R.; Toste, M. Column Distances of Convolutional Codes Over Zpr. IEEE Trans. Inf. Theory 2019, 65, 1063–1071. [Google Scholar] [CrossRef]
  25. DeCastro-García, N. Feedback equivalence of convolutional codes over finite rings. Open Math. 2017, 15, 1495–1508. [Google Scholar] [CrossRef]
  26. DeCastro-García, N.; García-Planas, M.I. Concatenated linear systems over rings and their application to construction of concatenated families of convolutional codes. Linear Algebra Its Appl. 2018, 542, 624–647. [Google Scholar] [CrossRef] [Green Version]
  27. DeCastro-García, N. Feedback Classification of Linear Systems and Convolutional Codes. Applications in Cybernetics, Coding Theory and Cryptography. Ph.D. Thesis, Universidad de Len, León, Spain, 2016. [Google Scholar]
  28. Forney, G. Convolutional codes I: Algebraic structure. IEEE Trans. Inf. Theory 1970, 16, 720–738. [Google Scholar] [CrossRef]
  29. Sole, P.; Sison, V. Quaternary Convolutional Codes From Linear Block Codes Over Galois Rings. IEEE Trans. Inf. Theory 2007, 53, 2267–2270. [Google Scholar] [CrossRef]
  30. Seshadri, C.S. Triviality of Vector Bundles over the Affine Space K2. Proc. Natl. Acad. Sci. USA 1958, 44, 456–458. [Google Scholar] [CrossRef] [PubMed] [Green Version]
  31. Mittelholzer, T.; Honor, B.; Darnell, M.; Farell, P. Minimal encoders for convolutional codes over rings. In Communications Theory and Applications; HW Communications Ltd.: Lancaster, UK, 1993; pp. 30–36. [Google Scholar]
  32. York, E. Algebraic Description and Construction of Error Correcting Codes, a Systems Theory Point of View. Ph.D. Thesis, University of Notre Dame, Notre Dame, IN, USA, 1997. [Google Scholar]
  33. Johannesson, R.; Zigangirov, K.S. Fundamentals of Convolutional Coding, 2nd ed.; Wiley-IEEE Press: Hoboken, NJ, USA, 2015. [Google Scholar]
  34. Forney, J.; David, G. Minimal Bases of Rational Vector Spaces, with Applications to Multivariable Linear Systems. SIAM J. Control 1975, 13, 493–520. [Google Scholar] [CrossRef]
  35. Kaplansky, I. Projective Modules. Ann. Math. 1958, 68, 372–377. [Google Scholar] [CrossRef]
  36. Campillo, A.; Sánchez Giralda, T. Finitely generated projective modules and Fitting ideals. Collect. Math. 1979, 30, 97–102. [Google Scholar]
  37. Pinto, R.; Simões, R. On Minimality of ISO Representation of Basic 2D Convolutional Codes. In Coding Theory and Applications; Barbero, Á.I., Skachek, V., Ytrehus, ∅., Eds.; Springer International Publishing: Cham, Switzerland, 2017; pp. 257–271. [Google Scholar]
  38. Napp, D.; Pereira, R.; Pinto, R.; Rocha, P. Realization of 2D (2,2)–Periodic Encoders by Means of 2D Periodic Separable Roesser Models. Int. J. Appl. Math. Comput. Sci. 2019, 29, 527–539. [Google Scholar] [CrossRef] [Green Version]
  39. Brewer, J.W.; Bunce, J.W.; Van Vleck, F.S. Linear Systems over Commutative Rings; Dekker: New York, NY, USA, 1986. [Google Scholar]
Publisher’s Note: MDPI stays neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Share and Cite

MDPI and ACS Style

Muñoz Castañeda, Á.L.; DeCastro-García, N.; Carriegos, M.V. On the State Approach Representations of Convolutional Codes over Rings of Modular Integers. Mathematics 2021, 9, 2962. https://0-doi-org.brum.beds.ac.uk/10.3390/math9222962

AMA Style

Muñoz Castañeda ÁL, DeCastro-García N, Carriegos MV. On the State Approach Representations of Convolutional Codes over Rings of Modular Integers. Mathematics. 2021; 9(22):2962. https://0-doi-org.brum.beds.ac.uk/10.3390/math9222962

Chicago/Turabian Style

Muñoz Castañeda, Ángel Luis, Noemí DeCastro-García, and Miguel V. Carriegos. 2021. "On the State Approach Representations of Convolutional Codes over Rings of Modular Integers" Mathematics 9, no. 22: 2962. https://0-doi-org.brum.beds.ac.uk/10.3390/math9222962

Note that from the first issue of 2016, this journal uses article numbers instead of page numbers. See further details here.

Article Metrics

Back to TopTop