Linear representations of convolutional codes over rings ∗
Miguel V. Carriegos†

Noemı́ DeCastro‡

Ángel Luis Muñoz Castañeda§

arXiv:1609.05043v1 [math.OC] 28 Jul 2016

March 21, 2018

Abstract
In this paper we extend the relation between convolutional codes and linear systems
over finite fields to certain commutative rings through first order representations .
We introduce the definition of rings with representations as those for which these
representations always exist, and we show that finite products of finite fields belong to
this class. We develop the input/state/output representations for convolutional codes
over these rings, and we show how to use them to construct observable convolutional
codes as in the classical case.

Keywords: convolutional codes; linear systems; finite rings
2010 MSC: 93B05, 93B07, 93B20; 13M99

1

Introduction

Convolutional codes are error-correcting codes used to detect and correct sets of digital
data. Convolutional codes over finite fields were introduced by Peter Elias in 1955 and, in
the current context, a considerable research in this field is developed by using algebraic,
combinatorics, computer science, control theoretic or algebro-geometric tools among others
(see [4], [6], [7], [14], [15] or [20]).
The first approach to convolutional codes over rings was given by Massey and Mittelholzer in [12, 13]. There is a considerable body of literature about convolutional codes over
rings where generator matrices, minimal encoders and their properties have been studied
(see [3, 8]). Moreover, trellis representations and properties of convolutional codes over
Z/pr Z are developed in [10, 11].
We are interested in the approach to convolutional codes over finite fields by linear
systems. This relation is given in terms of first order representations of the code, that is,
∗

Partially supported by INCIBE. Ministerio de Industria, Spain.
RIASC, Universidad de León, SPAIN, mail to: miguel.carriegos@unileon.es
‡
Departamento de Matemáticas, Universidad de León, SPAIN, mail to: ncasg@unileon.es
§
Institut für Mathematik, Freie Universität, Berlin, GERMANY, mail to: angel@math.fu-berlin.de
†

1

2

Carriegos, DeCastro-Garcı́a & Muñoz Castañeda

triples of matrices (K, L, M ) that allow us to obtain another set of matrices (A, B, C, D)
that forms a reachable (controllable) input/state/output (I/S/O) representation of the
convolutional code, where the inputs and outputs of a system are part of the codeword
(the main results can be found in [9], [16], [17], and [19]). Moreover, in [5] it is shown that
the decoder process of the code is given by the output controllability matrix (the matrix
which solves the associated linear dynamical system).
The natural question is whether we can generalize the above duality to certain commutative rings with identity. Within this goal, we introduce the definition of rings with
representations generalizing the above described relation between codes and systems to
this class of rings and their finite products.
This paper is organized as follows. In section 2 we give some algebraic preliminaries
that are needed in the rest of the paper. In section 3 we define the concept of family
of convolutional codes over a ring R, and we develop for them the basic theory of first
order representations generalizing the classical case. We then define the class of rings
with representations and we show that finite products of finite fields belong to this class.
In section 4 we show the existence of I/S/O representations for families of convolutional
codes over finite products of finite fields and their reachability properties. In section 5 we
use the above results to construct observable families of convolutional codes from linear
system point of view. Finally we give our conclusions and further research.

2

Preliminaries

We first give a brief overview of the theory of convolutional codes over a finite field. Finally
we state the basic algebraic preliminaries that will be used in the rest of the paper.

2.1

Convolutional Codes over Finite Fields

Let us start by recalling some basic definitions and known results regarding convolutional
codes and their representations, the reader can see [16], [17] and [19] as main references
on the topic.
Let F be a finite field and k ≤ n ∈ N. A (n, k) convolutional code over F is a rank
k submodule C ⊂ F[z]n . Any matrix G(z) ∈ M atn×l (F[z]), with l ≥ n, whose columns
generate C is called a generator matrix of C. A generator matrix G(z) of C of size n × k
is called an encoder of C. Note that any encoder is necessarily injective.
Let G(z) be an encoder for a (n, k) convolutional code C and denote g j (z) = (gi,j (z))i=1,...n
the jth column of G(z). The column degree of the encoder is defined as the maximum
degree of its coordinates, νj := max{deg(gi,j (z))|i = 1, . . . n}. Reordering the columns if
were necessary, we may assume that ν1 ≥ . . . ≥ νk . The complexity, or degree, of the en-

3

Linear representations of convolutional codes over rings
coder is then defined as δ(G(z)) :=

Pk

j=1 νj

while the memory is defined as the maximum

column degree, i.e. ν1 . Note that a memoryless convolutional code is a block code. The
complexity, or the degree, of the code C, δ(C), is the highest degree of the full size minors
of any encoder G(z) of C. An encoder G(z) is called minimal if δ(G(z)) = δ(C).
Let C be a (n, k) convolutional code over F with degree δ. A first order representation of
C is a triple of matrices (K, L, M ) with K, L ∈ M atδ+n−k×δ (F) and M ∈ M atn−k+δ×n (F)
such that
C = {v(z) ∈ F[z]n | ∃x(z) ∈ F[z]δ such that zKx(z) + Lx(z) + M v(z) = 0}
Moreover, if the representation satisfies the following conditions,
1. K has column full size rank,
2. (K, M ) has row full size rank,
3. rk(z0 K + L, M ) = δ + n − k for all z0 ∈ F, being F the algebraic clousure
then it is called minimal. And, on the other hand, two first order representations (K, L, M )
and (K ′ , L′ , M ′ ) are equivalent if there exist (unique) invertible matrices T, S of the adequate sizes such that (K ′ , L′ , M ′ ) = (T KS −1 , T LS −1 , T M ). The main theorem regarding
first order representations is
Theorem 2.1. ([19, Th. 5.1.1, Th. 5.1.4], [17, Th. 3.1, Th. 3.4]) Every convolutional
code C admits a unique (up to equivalence) minimal first order representation (K, L, M ).
Let C ∈ F[z]n be a (n, k) convolutional code of degree δ and (K, L, M ) a minimal
first order representation. We know that the matrix (K, L, M ) has full rank so there is
an invertible matrix W of rank δ + n − k such that, reordering the code words if were
necessary, it holds
W (K, L, M ) = (K, L, M)
where
K=

−Idδ
O

!

A

,L =

C

!

and M =

O

B

−Id(n−k) D

!

(1)

The matrices A, B, C and D over R obtained from (1) form an I/S/O representation of C,
that is, they define a linear system with state-space realization given by

→
−
→
→

x t+1 = A−
x t + B−
ut



→
→
−
→
−
 −
y t = C xt+Dut
!
−
→

y

t
→
−
→


, x0 = 0, ∃γ : −
x γ+1 = 0.
 vt=
−
→
u

(2)

t

→
−
→
where −
x (t) is the n-state vector, →
y (t) the p-vector output and −
u (t) the m-vector control.
We also give an initial state xt0 = x0 in time t0 .

4

Carriegos, DeCastro-Garcı́a & Muñoz Castañeda

Remark 2.2. Note that this linear system is reachable (by minimality conditions of first
order representations). Conversely if such a reachable linear system is also observable then
the associated convolutional code is observable (see [17, 16]).

2.2

Kernel of a Pair of Morphisms

Let us recall some definitions and properties from [2]. These allow us to study systematically R-modules defined in the same manner as in property (4) stated above.
Let R be a commutative ring (with unit), and let M1 , M2 , N be R-modules. Let
fi : Mi → N be two R-linear maps. We define the kernel Ker(f1 |f2 ) as
Ker(f1 |f2 ) := {m2 ∈ M2 |∃m1 ∈ M1 : f1 (m1 ) + f2 (m2 ) = 0}
There are three different ways to present the kernel of two R-linear maps,
1. Ker(f1 |f2 ) = f2−1 (Im(f1 ))
2. Ker(f1 |f2 ) ≃ Coker(Ker(f1 ) ֒→ Ker(f1 , f2 ))
3. Ker(f1 |f2 ) = Ker(p1 ◦ f2 : M2 → N/Im(f1 ))
(being the projection p1 : N → N/Im(f1 )) from which the main properties are derived. For
instance, Ker(f1 |f2 ) behaves well with respect to flat base change. As direct consequence,
we have the following particular situation,
Corollary 2.3. ([2, Corollary 5.5]) Consider matrices A(z), B(z) of adequate sizes, p × q1
and p × q2 respectively, and entries in R[z] where R = R1 × · · · × Rt is a product ring with
structural idempotents ei ∈ R. Then one has
Ker(A(z) | B(z)) = {u(z) | ∃x(z) : A(z)x(z) + B(z)u(z) = 0} =
= e1 Ker(π1 (A)(z) | π1 (B)(z)) + · · · + et Ker(πt (A)(z) | πt (B)(z))
being πi the ith projection of R onto Ri .

2.3

Rank of a Matrix with Coefficients in a Ring

We assume that any commutative ring is a ring with unit and any morphism of rings
φ : R → S maps the identity to the identity.
Let R be a commutative ring and let A ∈ M atn×m (R) be a matrix with coefficients in
R. For any positive integer 0 < i ≤ r := min{n, m}, we define
Ui (A) := ideal generated by the i × i minors of A

Linear representations of convolutional codes over rings

5

These ideals form a chain
(0) ⊆ Ur (A) ⊆ Ur−1 (A) ⊆ . . . ⊆ U1 (A) ⊆ R
The main property of the ideals Ui (A) is that they are stable under base change, i.e. if
g : R → S is a morphism of rings then
Ui (A ⊗ 1) = Ui (A) · S
As a trivial consequence we have
Lemma 2.4. Let g : R → S be a morphism of rings and let A ∈ M atn×m (R) be a matrix.
i) If Ui (A) = R then Ui (A ⊗ 1) = S.
ii) If n = m, then det(A ⊗ 1) is invertible in S if det(A) is invertible in R.
Proof. (i) If Ui (A) = R then 1S ∈ g(Ui (A)), so Ui (A ⊗ 1) = S holds. (ii) The second part
follows from the fact that A ⊗ 1 = g ∗ (A), and that g maps invertible elements to invertible
elements.
Consider the corresponding chain of annihilators
(0) = AnnR (R) ⊆ AnnR (U1 (A)) ⊂ . . . ⊆ AnnR (Ur (A)) ⊆ R
We define
Definition 2.5. The (determinantal) rank of the matrix A is defined as
rk(A) := max{i | AnnR (Ui (A)) = 0}
As in the classical case, if A ∈ M atn×n (R) then the equation AX = 0 has no non
zero solutions if and only if rk(A) = n (McCoy’s Theorem). Despite that, the condition
rk(A) = n does not mean A is invertible. In fact, it can be easily shown that rk(A) = n
if and only if det(A) is not a zero divisor. Therefore we have,
Lemma 2.6. ([1, Theorem 2.1]) Let A ∈ M atn×m (R) be a matrix with n ≥ m. Then
A is injective if and only if rk(A) = m. Let A ∈ M atn×m (R) be a matrix with n ≤ m.
Then A is surjective if and only if Un (A) = R.
For the sake of clarity, we fix first of all some notation. For any prime ideal p ∈ R we
denote k(p) = Rp /pRp the residue field and for any R[z]-module M we denote M (p) the
k(p)[z]-module M/pM = M ⊗R[z] k(p)[z].
Let A ∈ M atn×m (R) be a matrix with n ≤ m and M = Coker(A) then, by Nakayama’s
Lemma, we have
Mp = 0 ⇔ M (p) = 0 ⇔ rk(A(p)) = n
for any prime ideal p of R. Therefore,

6

Carriegos, DeCastro-Garcı́a & Muñoz Castañeda

Lemma 2.7. Let A ∈ M atn×m (R) be a matrix with n ≤ m. Then A is surjective if and
only if rk(A(p)) = n, ∀p ∈ Spec(R).
Recall that a local ring R has Krull dimension 0 if and only if every element of its maximal ideal is nilpotent, i.e. m = N il(R). We can show that many results regarding ranks
of matrices over fields can be easily translated to the case of matrices over a commutative
ring of dimension 0,
Proposition 2.8. Let R be a commutative ring of dimension 0. An element a ∈ R is
invertible if and only if a is not a zero divisor.
Proof. If a is not invertible then there is a maximal ideal m ⊂ R with a ∈ m and therefore
a/1 belongs to the maximal ideal of the local ring Rm , thus there is a natural number
n with an /1 = 0, so there exists an element b ∈ R \ m with ban = 0. Assume n is the
smallest satisfying this condition, so ban−1 6= 0. Then (ban−1 )a = 0, so a is a zero divisor.
The converse is trivial.
Corollary 2.9. Let R be a commutative ring of dimension 0 and let A ∈ M atn×n (R).
Then A is invertible if and only if rk(A) = n.
Proof. Since rk(A) = n if and only if det(A) is not a zero divisor, the result follows from
Proposition 2.8.
Another case of interest is R = F[z], being F a field. Since the units of the ring of
polynomials F[z] are the nonzero constants, we have
Proposition 2.10. Let A(z) ∈ M atn×m (F[z]) be a matrix with n ≤ m. Then A(z) is
surjective if and only if A(z0 ) has rank n fo all z0 ∈ F.
Proof. By Lemma 2.6, A(z) is surjective if and only if Un (A(z)) = F[z]. Let f1 (z), . . . , fl (z)
be the set of maximum size minors of A(z). Then the above condition is equivalent to
gcd(f1 (z), . . . , fl (z)) = 1, which is equivalent to the condition {f1 (z), . . . , fl (z)} have no
common roots in F.

3

Families of Convolutional Codes and their First Order
Representations

3.1

Families of Convolutional Codes

Let R be a commutative ring.
Definition 3.1. A (n, k) convolutional code over R is a free submodule C ⊂ R[z]n of rank
k, and such that R[z]n /C is flat over R.

7

Linear representations of convolutional codes over rings

Note that flatness of the quotient R[z]n /C allow us to interpret C as a family of convolutional codes parametrized by Spec(R). Otherwise, C(p) might not be a submodule of
R[z]n anymore. In this setting, the complexity, or the degree, of the code C is no longer
an integer but a function δ : Spec(R) → N.
Remark 3.2. In the rest of the paper, we will assume that the degree function δ is a
constant.
Wen define generator matrices and encoders for families of convolutional codes, following the classical case.
Definition 3.3. A generator matrix G(z) of a (n, k) convolutional code over R, C, is a
matrix G(z) ∈ M atn×l (R[z]), with l ≥ k, such that Im(G(z)) = C. A generator matrix of
size n × k is called an encoder.
By [18, Prop. 1.3], it follows that any encoder is injective, as in the usual case.
Example 3.4. Consider the ring R = Z/6Z and the matrix

z+3
5

2

G(z) = 
3z + 1
−2z + 2
−z 2 + 4z − 1

3z − 3






Note that the full size minors are {z 2 + 2z + 1, 2z 2 + 4z + 2, z 3 + z 2 + 5z + 5}. Since
AnnR (U3 (G(z))) = 0, we conclude that G(z) is injective (see Lemma 2.6), so its image,
C ⊂ R[z]3 , is a free R[z]-module. Since R[z]3 /C is R-flat (R is an absolutely flat ring), we
deduce that C is a (3, 2) family of convolutional codes over R and G(z) is an encoder for
C.

3.2

Observability

A very important property for classical convolutional codes is observability. Recall that
given a (n, k) convolutional code C ⊂ F[z]n , we say that it is observable if there exists a
surjection (the so called syndrome Former) ψ : F[z]n ։ F[z]n−k such that Ker(ψ) = C
(see [19, Lemma 3.3.2]). Note that this is the same as saying that the quotient F[z]n /C is
a flat F[z]-module. Therefore we define
Definition 3.5. Let C ⊂ R[z]n be a family of convolutional codes over R. We say that C
is observable if the quotient R[z]n /C is flat over R[z].
Since flatness is preserved after base change it turns out from the definition that any
member C(p) of the family is observable.

8

Carriegos, DeCastro-Garcı́a & Muñoz Castañeda

Example 3.6. Consider the ring R = Z/6Z and let

z+3
5

2

G(z) = 
3z + 1
−2z + 2
−z 2 + 4z − 1

3z − 3






be the matrix considered in above example. As we have shown, the image defines a family
of convolutional codes and G(z) is an encoder. Let us show that the family of convolutional
codes defined by G(z) is not observable. Since flatness is preserved after base change, it
is enough to show that the restriction of the quotient R[z]3 /Im(G(z)) to Z/2Z is not flat.
Note that the restriction of G(z) modulo 2 is given by

z−1
1

2

G1 (z) =  z + 1
0



z2 + 1 z + 1

An easy computation shows that





U2 (G1 (z)) =< z 2 + 1, (z 2 + 1)(z + 1) >
Since gcd(z 2 + 1, (z 2 + 1)(z + 1)) = z 2 + 1, we have
U2 (G1 (z)) = (z 2 + 1) 6= R
so (Z/2Z)[z]3 /Im(G1 (z)) is not flat over (Z/2Z)[z]. Since R[z]3 /Im(G(z)) is R-flat,
(Z/2Z)[z]3 /Im(G1 (z)) ≃ R[z]3 /Im(G(z)) ⊗R Z/2Z
so, we conclude that R[z]3 /Im(G(z)) is not flat over R[z].
The particular case we are interested in is when R is a finite product of commutative
rings, R = R1 × . . . × Rt . In this case we have,
Proposition 3.7. C is observable ⇔ Cj is observable ∀ j.
Proof. The direct implication is clear. Let us show the converse. If Cj is observable, then
Rj [z]n /C is a Rj [z]- flat module for j = 1 . . . , t. For each j we can consider the following
exact sequence
0 −→ Cj ֒→ Rj [z]n −→ Rj [z]n /Cj −→ 0
and then we can construct the following exact sequence
Lt  
Lt
Lt
n
n
/
/
/
0
j Cj
j Rj [z]
j (Rj [z] /Cj )
0

/ C



/ R[z]n

Since flatness is stable under finite products,
R[z]n /C

/ R[z]n /C

L

n
j (Rj [z] /Cj )

is a flat R[z]-module and C is observable.

(3)

/0

/0

is a flat R[z]-module. So

Linear representations of convolutional codes over rings

3.3

9

Minimal First Order Representations of Families of Convolutional
Codes

Let us define now first order representations of convolutional codes over a commutative
ring R,
Definition 3.8. A first order representation of a (n, k) family of convolutional codes
of degree δ over R is a triple of matrices (K, L, M ) with K, L ∈ M atδ+n−k×δ (R) and
M ∈ M atδ+n−k×n (R) satisfying C = Ker(f1 |f2 ) (where f2 = zK + L and f1 = M ).
Moreover, if the following conditions are verified,
1. the matrix K : Rδ → Rδ+n−k is injective with flat cokernel
2. the matrix (K, M ) : Rδ+n → Rδ+n−k is surjective
3. the matrix (zK + L, M ) : R[z]δ+n → R[z]δ+n−k is surjective
then it is called minimal.
Remark 3.9. Note that in case R = F, above conditions agree with the classical ones:
(1) and (2) are trivial and (3) follows easily by Proposition 2.10. Note also that the
equivalence relation we had for fields can be adapted to this general setting in the obvious
way.
The central definition of this paper is the following,
Definition 3.10. A commutative ring R is a ring with representations if every convolutional codes C over R has a unique (up to equivalence) minimal first order representation.
After giving these definitions an important question comes up: what conditions on
the base ring R ensure us the existence of minimal first order representations for a fixed
convolutional code? It is well known the existence for classical convolutional codes, i.e.,
for R = F a finite field.
In this section we will show that if R is a finite product of rings, R1 , . . . , Rt , then it is
enough to prove the existence (and uniqueness) of minimal first order representations for
each Ri .
Let R be a commutative ring splitting into a finite product of rings R ≃ R1 × . . . × Rt
and denote by
b j × . . . × Rt
I j = R1 × . . . × R

the ideal generated by all the components except Rj . Then we have an exact sequence
0 → Ij ֒→ R → Rj → 0
for all j = 1, . . . , t. First we have the following basic properties:

10

Carriegos, DeCastro-Garcı́a & Muñoz Castañeda

Lemma 3.11. We consider the ring R = R1 × . . . × Rt and let A be a matrix over R. Let
us denote by Aj := A mod(Ij ). Then, the following holds:
1. Aj = ej A.
2. There are isomorphisms M atn×m (R) ≃
given by A → (ej A)j=1,...,t .

Qt

j=1 M atn×m (Rj )

and Gln (R) ≃

Qt

j=1 Gln (Rj )

3. If Aj are matrices whose rows are free over Rj for each j, then A is a matrix whose
rows are free over R.
4. If Aj are matrices whose columns are free over Rj for each j, then A is a matrix
whose columns are free over R.
Proposition 3.12. (Existence) Let R be a commutative ring and assume that there is a
decomposition R ≃ R1 × . . . × Rt such that Rj is a ring with representations for all j.
Then there exists a minimal first order representation for any (n, k) family of convolutional
codes, C ⊂ Rn [z], of degree δ.
Proof. Let Cj ≃ C⊗R Rj be the restriction of C to Rj . From the definition of C we know that
Cj is a (n, k)- convolutional code over Rj with constant degree δ. Then, there are matrices
Kj , Lj ∈ M at(δ+n−k)×δ (Rj ) and Mj ∈ M at(δ+n−k)×n (Rj ) such that Cj = ker(f1j |f2j ) where
f1j = zKj + Lj and f2j = Mj . Let e1 , . . . , et be the structural idempotents and consider
Pt
Pt
P
K = tj=1 Kj ej , L =
j=1 Mj ej . We define f1 = zK + L and
j=1 Lj ej and M =
f2 = M . Then, we clearly have Cj = ker(f1 ⊗ ej |f2 ⊗ ej ) (see Corollary 2.3). Since
C ≃ ⊕tj=1 Cj ej we finally get
C = ker(f1 |f2 )
The fact that K, L, M satisfy minimality conditions 1) and 2) follows from Lemma 3.11.
The third condition of minimality is trivial since the matrix (f1 , f2 ) is surjective on each
component Rj .
Proposition 3.13. (Uniqueness) Let R be a commutative ring as in Proposition 3.12.
Moreover, assume that first order representations of each Cj are unique up to equivalence
over all Rj . Then for any (n, k) family of convolutional codes C over R of degree δ and
any two first order representations (K, L, M ) and (K ′ , L′ , M ′ ) of C there exist invertible
matrices over R, S and T , such that
(K ′ , L′ , M ′ ) = (T KS 1 , T LS 1 , T M )
Proof. Let (K, L, M ) and (K ′ , L′ , M ′ ) be first order representations of the family of convolutional codes C ⊂ Rn [z] and (Kj , Lj , Mj ), (Kj′ , L′j , Mj′ ) their restrictions to Rj . By
Corollary 2.3 and by the fact that minimality conditions (1), (2), (3) are stable under base

11

Linear representations of convolutional codes over rings

change, we know that these are first order representations for Cj , so there are invertible
matrices Sj , Tj such that
(Kj′ , L′j , Mj′ ) = (Tj Kj Sj−1 , Tj Lj Sj−1 , Tj Mj )
By Lemma 3.11 (2) we know that there are unique invertible matrices over R, say S and
T , such that S mod(Ij ) = Sj and T mod(Ij ) = Tj . Obviously K ′ = T KS −1 , L′ = T LS −1
and M ′ = T M .
We conclude with our main result:
Theorem 3.14. Let R1 , . . . , Rt be a commutative rings. If Rj is a ring with representations for all j = 1, . . . , t then R = R1 × . . . × Rt is a ring with representations.
Proof. It is clear from Propositions 3.12 and 3.13.
Recall that the only rings with representations known so far are finite fields. Thus
Theorem 3.14 implies that finite products of finite fields (reduced noetherian rings with
Krull dimension 0) are also rings with representations.

4

Input/Space/Output Representations of Families of Convolutional Codes over Finite Products of Finite Fields

In this section, we specialize to the case Ri = Fi is a field for each i = 1, . . . , t. Let us show
that we can generalize the construction of I/S/O representations given in (1) to families
of convolutional codes over finite product of finite fields, R = F1 × . . . × Ft .
Theorem 4.1. Let C be a convolutional code over R. Let (K, L, M ) be a first order
representation of C. Then
i) We can make elementary transformations over (K, L, M ) and obtain (K, L, M) such
that
K=

−Idδ
O

!

,L =

A
C

!

and M =

O

B

−Id(n−k) D

!

where A ∈ Mδ×δ (R), B ∈ Mδ×k (R), C ∈ M(n−k)×δ (R) and D ∈ M(n−k)×k (R).
ii) Moreover, the triple of matrices obtained in i) verifies that
Ker(zK + L | M ) ≃ Ker(zK + L | M)

(4)

12

Carriegos, DeCastro-Garcı́a & Muñoz Castañeda

Proof. i) Since (K | L | M ) is surjective, we know that (Kj | Lj | Mj ) has full rank
(see Corollary 2.7) and therefore there exists an invertible matrix W of size (δ + n − k)
(see Lemma 3.11) such that if we multiply W −1 and (K | L | M ) and we reorder the
codewords of the local codes Cj , if it is necessary, we get a triple of matrices (K | L | M)
in the following way

K=

−Idδ
O

!

,L =

Aδ×δ
C(n−k)×δ

!

O

and M =

Bδ×k

−Id(n−k) D(n−k)×k

!

ii) Follows from [2, Proposition 2.5].
Proposition 4.2. The matrices (A, B, C, D) over R obtained in (4) can be constructed
from (Aj , Bj , Cj , Dj ) over Rj , the I/S/O representations of the convolutional codes Cj over
Fj .
Proof. Let W be the invertible matrix of size (δ + n − k) defined in Proof of i) of Theorem
4.1. Let Wj ≡ W (mod Ij ) be the square minor of size (δ + n − k) such that det(Wj ) ∈ F∗j .
We know that
W −1 (K | L | M ) = (K | L | M)

(5)

where (K | L | M ) and (K | L | M) are minimal first order representations of C.
If we apply mod Ij to both sides of above equation we get
[W

−1

· (K | L | M )](mod Ij ) = (Kj | Lj | Mj ) =

"

−Idj Aj
Cj

O

O

Bj

−Idj

Dj

#

(6)

On the other hand
(K | L | M)(mod Ij ) =

"

−Id A
O

O

B

C −Id D

#

(mod Ij )

(7)

and since the equation (5) is verified then we conclude the proof.
Recall that a a linear system Σ = (A, B, C, D) over a commutative ring R is reachable
(controllable from the origin) if the controllability matrix Φδ (A, B) := (B, AB, ..., Aδ−1 B)
is surjective. Let as show that the I/S/O representation constructed above is always
reachable.
Proposition 4.3. Let R = F1 × . . . × Ft be a commutative ring where Fj is a finite field
for all j = 1, . . . , t and let ΣC be the I/S/O representation of a family of convolutional
codes C over R. Then ΣC is a reachable linear system over R.

13

Linear representations of convolutional codes over rings

Proof. Let (A, B, C, D) be an I/S/O representation of a C over R. By Proposition 4.2 we
can consider these matrices such that
Aj ≡ A(mod Ij ), Bj ≡ B(mod Ij ), Cj ≡ C(mod Ij ) and Dj ≡ D(mod Ij ).
C

Now, by [19], each I/S/O representation of each convolutional code over Fj , Σj j , verifies
that rank Φδ (Aj , Bj ) = δ and so, they are reachable linear systems. Since R is a pointwise
ring, Φδ (A, B) is surjective (see Lemma 3.11) and we conclude that the I/S/O of C, ΣC ,
is a reachable linear system over R.
Example 4.4. In this example, we will raise two encoders with coefficients in Z/2Z and
Z/3Z, each one generating a dynamical linear system. We compute their first order and
I/S/O representations. Consider the encoder on Z/2Z

z−1
1

2

G1 (z) =  z + 1
0



z2 + 1 z + 1

Then there exist matrices

1 0

 1 0
K1 = 
 0 1

0 1

K1 , L1 and M1 that


0 1
0




1 0
0 
, L1 = 


0 
 1 0
1 0
1





characterize the encoder


0 0
0




1 0
1 
and M1 = 


0 
 0 1
0 0
1

G1 (z).

0

0 

0 

1

Therefore we compute the matrices A1 , B1 , C1 and D1 , by which one gets the associated
linear system.


0 1 0





0 0











 , B1 =  1 0  , C1 = 1 1 1
and
D
=
A1 = 
0
0
1
0
0
1




0 0 1
1 1

Now note that

rk



B1 A1 B1 A21 B1

so, (A1 , B1 , C1 , D1 ) is reachable.





0 0 1 0 0 0




= rk 
 1 0 0 0 1 0 =3
1 1 1 1 1 1

Consider the encoder on Z/3Z



G2 (z) = 




z

−1




z−1 

2
−z + z − 1
0
1

14

Carriegos, DeCastro-Garcı́a & Muñoz Castañeda

Matrices K2 , L2 and M2 are obtained following:



−1 0 0
0 1



 −1 0 0 

 , L2 =  0 0
K2 = 
 0 0 −1 
 −1 0



−1 1 0
1 0

Then



0

1 0





0

0





0 0 0








1 
 and M2 =  1 0 0 
 0 1 0 
1 



0 0 1
0



0









 , B2 =  0 −1  , C2 = 0 1 −1 , and D2 = 0 0
A2 = 
−1
1
0




−1 0 1
1 0

Note again that

rk



B2 A2 B2 A22 B2





0 0 0 2 0 2






= rk 
 0 2 0 2 0 0 =3
1 0 1 0 1 1

so (A2 , B2 , C2 , D2 ) is also reachable.

Now, we obtain the corresponding matrices (A, B, C, D) over Z/6Z glueing the matrices
(A1 , B1 , C1 , D1 ) and (A2 , B2 , C2 , D2 )




0 0
0 1 0








 , B =  3 2  , C = 3 1 5 , andD = 0 0
A=
5
4
0




1 3
2 0 1

The associated I/S/O representation of C over Z/6Z is reachable too, since
3 2 2
U3 (Φ3 (A, B)) =<

3 0 2

0 2 0 , 0 3 0
1 3 1

>=< 2, 3 >= Z/6Z

1 1 1

We also perform matrices K, L and M in Z/6Z



−1 0
0
0 1



 0 −1 0 

,L =  5 4
K=

 0
 2 0
0 −1 


3 1
0
0
0

0





0

0 0




0 
 and M =  0 3 2

 0 1 3
1 

5
−1 0 0








(8)

Now we compute Ker(zK + L|M ) in order to obtain a encoder of a family of convolutional
codes over Z/6Z[z],




G(z) = 


z+3

5




−2z + 2 

−z 2 + 4z − 1 3z − 3
3z 2 + 1

(9)

Note that above encoder G(z) restricts to Z/2Z obtaining G1 (z) and Z/3Z getting G2 (z).

15

Linear representations of convolutional codes over rings

5

Construction of Observable Families of Convolutional Codes
over Finite Product of Finite Fields.

Let F1 , . . . , Ft be finite fields and consider the ring R =

Q

Fi which is a ring with rep-

resentations, as we have already shown. It is well known that if we consider a reachable
and observable I/S/O representations over a finite field then we get an observable convolutional code by minimal first order representation by the formula (1) (see [17] and [19]
for details). In this section we show that we can generalize this result to the case of I/S/O
representations of a family of convolutional codes over R.
Recall that a linear system Σ = (A, B, C, D) over a commutative ring R is observable if
the observability matrix Ωδ (A, C) := (C t , (CA)t , (CA2 )t , . . . , (CAδ−1 )t ) is injective. Now
we give the result that allow us to construct observable families of convolutional codes
from observable I/S/O representations over R.
Proposition 5.1. Let R = F1 × . . . × Ft be a commutative ring where Fj is a finite field
for all j = 1, . . . , t and let ΣC be the I/S/O representation of a family of convolutional
codes C over R. If ΣC is a reachable and observable linear system over R then C is an
observable family of convolutional codes over R
Proof. By hypothesis (A, B, C, D) is a reachable and observable linear system over R,
so Ωδ (A, C) is injective and Φδ (A, B) is surjective. Consider (Aj , Bj , Cj , Dj ), the linear
systems obtained over each Fj for j = 1, . . . , t. Clearly Φδ (Aj , Bj ) is also surjective for all
j. Since R is an absolutely flat ring, the cokernel of Ωδ (A, C) is flat over R. Therefore
Ωδ (Aj , Cj ) is also injective for all j. Thus, for all j the above systems are reachable
and observable too. Then, if we perform the convolutional codes Cj for each j from
(Aj , Bj , Cj , Dj ), by [19] Cj are observable convolutional codes for all j. By Lemma 3.7
then C is an observable family of convolutional codes over R.

6

Conclusions

We have proved the existence and uniqueness of minimal first order representations of
families of convolutional codes over certain commutative rings. This property defines the
class of rings that we have called rings with representations. For instance, we have shown
that finite products of finite fields belong to this class. Here a natural question comes
Q
up: are infinite products of finite fields Fi rings with representations? Show that these

are special cases of von Neumann regular rings. So the next natural question is: are von
Neumann regular rings rings with representations?
In the particular case of finite product of finite fields, we also generalize the existence

of I/S/O representations and we construct observable families of convolutional codes from

16

Carriegos, DeCastro-Garcı́a & Muñoz Castañeda

linear systems.
Our further research is focused on answering the above questions and to get I/S/O
representations for this type of rings.

References
[1] J. W. Brewer, J. W. Bunce, and F. S. Van Vleck, Linear Systems over commutative
Rings, Marcel Dekker, New York, (1986).
[2] Miguel V. Carriegos, Noemı́ DeCastro-Garcı́a, Angel Muñoz Castañeda, A note on
the kernel of a pair of linear maps, arXiv:1603.02730v1 (2016)
[3] Fagnani, F. and S. Zampieri, System-theoretic properties of convolutional codes over
rings,IEEE Trans. Inform. Theory, 47, (2001), 2256-2274 .
[4] C. Fragouli, R.D. Wesel, Convolutional Codes and Matrix Control Theory, Proc. of
the 7th ICACCI, Athens, Grece. (1999)
[5] M.I. Garcı́a-Planas, J.L. Domı́nguez- Garcı́a, Alternative tests for functional and
pointwise output-controllability of linear tome-invariant systems, Syst. Cont. Letters, 62,5, 382-387 (2013)
[6] Gluesing-Luerssen, H., J. Rosenthal, and P. A. Weiner, Duality between multidimensional convolutional codes and systems, Chapter of Book Ad. Math.l Systems
Theory, Colonius F. et al. (eds). Birkhauser, Boston (2000).
[7] R. Hutchinson, J. Rosenthal, R. Smarandache, Convolutional codes with maximum
distance profile, Systems Control Lett., 54, 1, 53-63 (2005)
[8] R. Johannesson, Z.Wan, and E. Wittenmark. Some structural properties of convolutional codes over rings. IEEE Trans. Inform. Theory, 44, 2, (1998), 839 - 845.
DOI: 10.1109/18.661532
[9] M. Kuijper, First Order Representations of Linear Systems. Boston, MA:
Birkhauser, (1994).
[10] M. Kuijper, R. Pinto, On minimality of convolutional ring encoders, IEEE Trans.
on Inform. Theory, 55, 11, (2009), 4890-4897.
[11] Kuijper, M., R. Pinto, J. W. Polderman, and P. Rocha, Autonomicity and the
absence of free variables for behaviors over finite rings, Proc. 7th Portuguese
Conf. Autom. Control, Lisbon, Portugal (2006).
[12] J.L. Massey and T. Mittelholzer. Convolutional codes over rings. Proc. Joint
Swedish-Soviet Int. Workshop on Inform. Theory, (1989), 14-18, Gotland, Sweeden.

Linear representations of convolutional codes over rings

17

[13] J.L. Massey and T. Mittelholzer. Systematicity and rotational invariance of con- volutional codes over rings. Proc. Int. Workshop on Alg. and Combinatorial Coding
Theory, (1990), 154-158, Leningrad.
[14] J.M. Muñoz Porras, J.I. Iglesias Curto, Classification of convolutional codes, Linear
Algebra and its Applications, 432(10):2701-2725..
[15] M. S. Ravi and J. Rosenthal. A general realization theory for higher order linear
differential equations. Syst. Control Lett., 25, 5, 351-360 (1995)
[16] J. Rosenthal, E. V. York, BCH Convolutional Codes, IEEE Trans. Inform. Theory,
45, 6, 1833-1844 (1999)
[17] Joachim Rosenthal, J. M. Schumacher, and E. V. York, On behaviors and convolutional codes, IEEE Trans. Inform. Theory, 42, 6, 1881-1891 (1996)
convolutional codes. IEEE Trans. Inform. Theory, 47, 5, 2045-2049 (2001)
[18] W. V. Vasconcelos, On finitely generated flat modules, Trans. Amer. Math. Soc.,
138, (1969)
[19] E. V. York, Algebraic description and construction of error correcting codes, a systems theory point of view., Ph.D. dissertation, Univ. Notre Dame (1997)
[20] E. Zerz, On multidimensional convolutional codes and controllability properties of
multidimensional systems over finite rings, Asian Journ. Control, 12, 2, 119-126
(2010)

