Georgian Mathematical Journal Volume 8 (2001), Number 3, 553–570

CONVOLUTIONAL CODES AND FREQUENCY RESPONSES

V. LOMADZE

Abstract. Frequency responses are introduced as objects that are much finer than transfer functions, and their investigation is carried out via convolutional codes. In particular, a canonical one-to-one correspondence is established between frequency responses and equivalence classes of AR-models. These new objects are important because the study of linear dynamical systems can to a great extent be reduced to the study of them.

2000 Mathematics Subject Classification: 93B05, 95B25, 93B27, 94B10. Key words and phrases: Transfer function, convolutional encoder, ARmodel, convolutional code, frequency response, exact sequence, controllable.

1. Introduction

Throughout the paper k will be an arbitrary field, s an indeterminate, O the ring of proper rational functions over k. We adopt Willems’ [7] point of view that makes no distinction between inputs and outputs, and q will stand for the signal number.

By a transfer function we understand a k(s)-linear subspace in k(s)^{q} (i.e., exactly what Forney [1] calls a convolutional code.) Frequency responses are defined as k-linear subspaces in k(s)^{q} satisfying certain natural conditions. One condition is a finiteness condition according to which a frequency response must contain a transfer function and have finite dimension relative to it; other conditions require a frequency response to be invariant under taking the polynomial and strictly proper parts, and the forward and backward shift operators. There is a canonical nondegenerate symmetric k-bilinear form on k(s)^{q}, which is obtained by composing the standard k(s)-bilinear form with the residue map at infinity. It is easily seen that transfer functions are self-dual with respect to this form. Based on this simple fact, we show (see Theorem 1 and Theorem 2) that frequency responses are connected via a duality relation with convolutional codes. It is almost obvious that convolutional codes are in a bijective correspondence with equivalence classes of convolutional encoders. We therefore obtain that frequency responses correspond bijectively to equivalence classes of AR-models, which represents the main result of the paper.

The system-theoretic significance of the concept of a frequency response will become clear in [5]. It will be shown in that follow-up paper that knowledge of frequency responses is equivalent to that of linear dynamical systems. It

ISSN 1072-947X / $8.00 / \begin{matrix}c \\ ◯ \end{matrix} Heldermann Verlag www.heldermann.de

does not matter that linear dynamical systems are discrete-time or continuoustime. This emphasizes once more that the theory of linear dynamical systems is essentially algebraic in nature.

It should be noted that we treat here the general singular case; the classical regular case is derived easily from it. If the reader is interested in this latter case only, he should start with the bilinear form k[s]^{q} × s^{−1}O^{q} → k. An advantage in considering general frequency responses rather than “classical” frequency responses (as we call them) lies in the fact that the just mentioned bilinear form is not so easy to treat. Next, general frequency responses are related with general linear dynamical systems. And we know that linear dynamical systems having singularity also deserve to be studied.

The reader is referred to Willems [7] for linear systems, Forney [1] for convolutional codes, and Rosenthal et al. [6] for both of them.

2. Some Preliminaries

There are two important functions on k(s): ord_{∞} and Res_{∞}. Given a rational function f, ord_{∞}(f) is the least integer n such that s^{n}f ∈ O, and Res_{∞}(f) is the coefficient at s^{−1} in the representation of f as a power series in s^{−1}.

For each r ≥ 1, one has a canonical k-bilinear form

< −, − >: k(s)^{r} × k(s)^{r} → k,  (1)

which is defined by the formula

< f, g >= Res_{∞}(f^{tr}g).

(Here and below “tr” stands for “transpose”.) Clearly, this form is symmetric, and one can easily check that it is nondegenerate.

Lemma 1. We have

(k[s]^{r})^{⊥} = k[s]^{r} and (s^{−1}O^{r})^{⊥} = s^{−1}O^{r}.

Proof. Obvious.

For each rational function f, set

π_{−}(f) = polynomial part of f and π_{+}(f) = strictly proper part of f.

Lemma 2. For all f, g ∈ k(s)^{r},

< π_{−}f, g >=< f, π_{+}(g) > .

Proof. Obvious.

Lemma 3. Let X_{1} and X_{2} be k-linear subspaces in k(s)^{r}. Then

(X_{1} + X_{2})^{⊥} = X_{1}^{⊥} ∩ X_{2}^{⊥}.

Proof. Obvious.

Remark. The equality (X_{1} ∩ X_{2})^{⊥} = X_{1}^{⊥} + X_{2}^{⊥} is not always true (and this causes some problems). In general, we have only “⊇”.

Lemma 4. Let X and Y be k-linear subspaces in k(s)^{r} such that X ⊆ Y. If X^{⊥⊥} = X, then the canonical bilinear form

Y/X × X^{⊥}/Y^{⊥} → k

is nondegenerate.

Proof. This is obviously nondegenerate from the right. The hypothesis implies that this is nondegenerate from the left as well.

Lemma 5. Let l, m ≥ 1 and let A be a rational matrix of size l × m. If X is a k-linear subspace in k(s)^{l}, then

(A^{tr}X)^{⊥} = A^{−1}(X^{⊥}).

Proof. For all f ∈ k(s)^{l} and g ∈ k(s)^{m},

< A^{tr}f, g >=< f, Ag >,

and the lemma follows.

Lemma 6. If L is a k[s]-submodule in k(s)^{r}, then so is L^{⊥}. Likewise, if M is an O-submodule in k(s)^{r}, then so is L^{⊥}.

Proof. Left to the reader. (When L, M are finitely generated, the proof is immediate by the previous lemma and Lemma 1.)

The following simple lemma will be very helpful in the sequel.

Lemma 7. If V is a k(s)-linear subspace in k(s)^{r}, then so is V^{⊥} and V^{⊥⊥} =V.

Proof. One can check easily that

V^{⊥} = {g | f^{tr}g = 0 for all f ∈ V };

whence follows the lemma.

Given k-linear spaces X and Y such that X ⊆ Y, we write [Y : X] to denote the dimension of the quotient space Y/X.

Lemma 8. Let X be a k-linear subspace in k(s)^{r}.

a) There exists at most one k(s)-linear subspace V in k(s)^{r} such that X ⊆ V and [X : V] < +∞.

b) There exists at most one k(s)-linear subspace V in k(s)^{r} such that V ⊆ X and [V : X] < +∞.

Proof. Assume that V_{1} and V_{2} are two k(s)-linear subspaces satisfying the desired property. Then V_{1} + V_{2} also has the same property, and clearly

[(V_{1} + V_{2}) : V_{1}] < +∞ and [(V_{1} + V_{2}) : V_{2}] < +∞.

It follows that V_{1} = V_{1} + V_{2} and V_{2} = V_{1} + V_{2}; whence V_{1} = V_{2}.

Given a polynomial (resp. a proper) matrix A, we say that A is left unimodular (resp. left biproper) if BA = I for some polynomial (resp. proper) matrix B.

Lemma 9.

a) Let L be a submodule in k[s]^{r}. Then the following are equivalent: 1) k[s]^{r}/L is torsion free; 2) L = E ∩ k[s]^{r} for some k(s)-linear subspace E ⊆ k(s)^{r};

3) L = P k[s]^{m} for some m ≥ 0 and left unimodular r × m matrix P. b) Let M be a submodule in O^{r}. Then the following are equivalent: 1) O^{r}/M

is torsion free; 2) M = E ∩ O^{r} for some k(s)-linear subspace E ⊆ k(s)^{r};

3) M = QO^{m} for some m ≥ 0 and left biproper r × m matrix Q.

Proof. The assertion a) is fairly well-known. We give a sketch proof for the assertion b).

Let E denote the k(s)-submodule of k(s)^{r} generated by M (that is, k(s)M). Then, k(s)^{r}/E is the fraction space of O^{r}/M, and hence the latter is torsion free if and only if the canonical map O^{r}/M → k(s)^{r}/E is injective. Since the kernel of this map is equal to (O^{r} ∩ E)/M, we obtain b1) ⟺ b2). Further, both b1) and b3) are equivalent to saying that O^{r} ≃ M ⊕ O^{r}/M, and hence we have b1) ⟺ b3).

Concluding the section, define k-linear operators τ : k[s] → k[s] and σ : O → O, the forward and backward shifts, respectively by

τ(a_{0}s^{n}+⋯+a_{n}) = a_{0}s^{n−1}+⋯+a_{n−1} and σ(b_{0}+b_{1}s^{−1}+…) = b_{1}+b_{2}s^{−1}+· · · .

3. Convolutional Encoders and AR-Models

We begin by recalling some basic definitions and facts concerning nonsingular (square) rational matrices as given in [3].

The cohomology spaces of a nonsingular rational matrix D are defined by

H^{0}(D) = k[s]^{r} ∩ DO^{r} and H^{1}(D) = k(s)^{r}/(k[s]^{r} + DO^{r}),

where r denotes the size of D. The Chern number is defined by the formula ch(D) = − ord_{∞}(det D), and the dual is defined to be D^{∗} = (D^{−1})^{tr}. Two nonsingular rational matrices D_{1} and D_{2} are called equivalent if there exists a unimodular matrix U such that D_{2}^{−1}UD_{1} is biproper. According to the Wiener– Hopf theorem (which is the most significant fact about rational matrices), if D is a nonsingular rational matrix of size r, then there exist integers n_{1}, …, n_{r} such that D is equivalent to the diagonal matrix with s^{n_{1}}, …, s^{n_{r}} on the diagonal. The integers n_{1}, …, n_{r} are uniquely determined up to permutation; they are called the Wiener–Hopf indices.

Lemma 10 (Serre’s formulas). Let n be an integer.

a) If n ≥ 0, then the canonical linear map k^{n+1} → H^{0}(s^{n}) given by

(a_{0}, …, a_{n}) ↦ a_{0}s^{n} + ⋯ + a_{n}

is bijective; if n < 0, then H^{0}(s^{n}) = 0.

b) If n ≥ 0, then the canonical linear map k^{n+1} → H^{1}(s^{−n−2}) given by

(b_{0}, …, b_{n}) → (b_{0}s^{−1} + ⋯ + b_{n}s^{−n−1}) mod(k[s] + s^{−n−2}O)

is bijective; if n < 0, then H^{1}(s^{−n−2}) = 0.

Lemma 11 (Finiteness theorem). Cohomology spaces have finite dimension.

Lemma 12 (Riemann–Roch theorem). If D is a nonsingular rational matrix, then

dim H^{0}(s^{−1}D) − dim H^{1}(s^{−1}D) = ch(D).

Lemma 13 (Serre’s duality theorem). If D is a nonsingular rational matrix of size r, then the canonical pairing (1) induces a nondegenerate pairing

H^{0}(s^{−1}D) × H^{1}(s^{−1}D^{∗}) → k.

Lemma 14.

a) If A is a nonsingular rational matrix, then its Wiener–Hopf indices are nonpositive if and only if there exists a full column rank rational matrix F such that F A is proper.

b) If B is a nonsingular rational matrix, then its Wiener–Hopf indices are nonnegative if and only if there exists a full row rank rational matrix G such that B^{−1}G is proper.

Two nonsingular rational matrices are said to be congruent if they are connected via right multiplication by a biproper matrix. We define a linear bundle as a congruence class of nonsingular rational matrices. The rank of a linear bundle is the size of any its representative. The cohomology spaces, the Chern number, the Wiener–Hopf indices, and the dual of a linear bundle are defined obviously.

As noted in Introduction, by a transfer function we mean any k(s)-linear subspace in k(s)^{q}.

A convolutional encoder is a pair (α, F), where α is a linear bundle and F a full column rank polynomial matrix, with q rows, such that F A is proper for any representative A of α. The rank of α is called the input number, the number − ch(α) the complexity, the space H^{1}(s^{−1}α) the state space. The space Im F = F k(s)^{m}, where m is the input number, is called the transfer function. By Lemma 14a), the Wiener–Hopf indices of α must be nonpositive. These indices, taken with minus, are called the constraint lengths. By Serre’s formulas and the Riemann–Roch theorem, their sum is equal to the complexity. Two convolutional encoders (α_{1}, F_{1}) and (α_{2}, F_{2}) are said to be equivalent if there exists a unimodular matrix U such that A_{1}^{−1}UA_{2}, where A_{1} ∈ α_{1} and A_{2} ∈ α_{2}, is biproper and F_{2} = F_{1}U.

An AR-model is a pair (β, G), where β is a linear bundle and G a full row rank polynomial matrix, with q columns, such that B^{−1}G is proper for any representative B of β. The rank of β is called the output number, the number ch(β) the McMillan degree, the space H^{0}(s^{−1}β) the state space. The space Ker G = G^{−1}{0} is called the transfer function. The Wiener–Hopf indices, which are nonnegative by Lemma 14b), are called the lag indices. By Serre’s formulas and the Riemann–Roch theorem, their sum is equal to the McMillan degree. Two AR-models (β_{1}, G_{1}) and (β_{2}, G_{2}) are said to be equivalent if there exists a unimodular matrix U such that B_{2}^{−1}UB_{1}, where B_{1} ∈ β_{1} and B_{2} ∈ β_{2}, is biproper and G_{2} = UG_{1}.

There is an evident one-to-one correspondence between convolutional encoders and AR-models, which is given by

(α, F) ↦ (α^{∗}, F^{tr}).

A convolutional encoder (α, F) is said to be controllable if F is left unimodular and F A, where A is any representative of α, is left biproper. An AR-model (β, G) is said to be controllable if G is right unimodular and B^{−1}G, where B is any representative of β, is right biproper. Certainly, controllable convolutional encoders and controllable AR-models correspond to each other.

Let (α, F) be a controllable convolutional encoder with input number m, and (β, G) a controllable AR-model with output number p. Let A ∈ α and B ∈ β. We say that (α, F) and (β, G) form an exact pair if the sequences

0 → k[s]^{m} →^{F} k[s]^{q} →^{G} k[s]^{p} → 0 and 0 → O^{m} →^{F A} O^{q} →^{B^{−1}G} O^{p} → 0 (2)

are exact. We then say also that (α, F) is a kernel description of (β, G) and (β, G) a cokernel description of (α, F).

Lemma 15. Let (α, F) be an controllable convolutional encoder and (β, G) a controllable AR-model, and suppose that they form an exact pair. Then, for each integer n, there is a “long” cohomological exact sequence

0 → H^{0}(s^{n}α) → H^{0}(s^{n}I_{q}) → H^{0}(s^{n}β) → H^{1}(s^{n}α)
→ H^{1}(s^{n}I_{q}) → H^{1}(s^{n}β) → 0.

Proof. Left to the reader.

Corollary 1. There is a canonical isomorphism

H^{1}(s^{−1}α) ≃ H^{0}(s^{−1}β),

and hence the complexity of (α, F) and the McMillan degree of (β, G) are equal to each other.

Lemma 16.

a) Every controllable convolutional encoder possesses a cokernel description, and the latter is determined uniquely up to equivalence.

b) Every controllable AR-model possesses a kernel description, and the latter is determined uniquely up to equivalence.

Proof. Left to the reader.

Proposition 1. Let (α, F) be a convolutional encoder with complexity d, and let n ≥ max{d − 1, 0}. Then (α, F) is controllable if and only if the linear map

H^{1}(s^{−n−2}α) → H^{1}(s^{−n−2}I_{q})

is injective.

Proof.

Proof. Follows from the following proposition by Serre’s duality theorem.

Proposition 2. Let (β, G) be an AR-model with McMillan degree d, and let n ≥ max{d − 1, 0}. Then (β, G) is controllable if and only if the linear map

H^{0}(s^{n}I_{q}) → H^{0}(s^{n}β)

is surjective.

Proof. “If”. Note that if l ≥ 0, then H^{0}(s^{l+1}) = H^{0}(s^{l}) + sH^{0}(s^{l}). From this, using the Wiener–Hopf theorem, we obtain that

∀i ≥ 0, H^{0}(s^{l+1}β) = H^{0}(s^{l}β) + sH^{0}(s^{l}β).

It follows by induction that

H^{0}(s^{i}I_{q}) → H^{0}(s^{i}β)

is surjective for each i ≥ n. Using now Lemma 4 in [3], we see that the homomorphisms

k[s]^{q} → k[s]^{p} and O^{q} → BO^{p}

are surjective.

“Only if”. Let (α, F) be a kernel description. By Lemma 15, we have an exact sequence

H^{0}(s^{n}I_{q}) → H^{0}(s^{n}β) → H^{1}(s^{n}α).

We know (see Lemma 14(a)) that the Wiener–Hopf indices of α are nonpositive. On the other hand, their sum is equal to ch(α) = − ch(β). Hence these indices are greater than or equal to −d. We see that every index of s^{n}α is greater than or equal to −1, and therefore its one-dimensional cohomologies are trivial.

4. Convolutional Codes

A convolutional code is a k-linear subspace C in k(s)^{q} satisfying the following conditions:

(CC1) There is a transfer function E such that C ⊆ E and [E : C] < +∞. (CC2) C is invariant with respect to π_{−} and π_{+}; (CC3) C ∩ k[s]^{q} and sC ∩ O^{q} are submodules in k[s]^{q} and O^{q}, respectively.

By Lemma 8(a) , the “E” is uniquely determined, and we call it the transfer function of C. The number [E : C] is called the complexity. By the property (CC2), we have

C = (C ∩ k[s]^{q}) + (C ∩ s^{−1}O^{q}).

Remarks. 1) As remarked in Introduction, Forney [1] defines a convolutional code as a k(s)-linear subspace of k(s)^{q}. In Rosenthal et al. [6] a convolutional code is defined as a k[s]-submodule of k[s]^{q}. The relationships of these definitions with the definition above are explained respectively in Proposition 6 and Lemma 22.

2) Our definition has been motivated by the purpose to make obvious the connection with the definition of a frequency response given below, and it is equivalent to that provided in [4]. In the cited paper a convolutional code is defined as a pair (L, M), where L and M are submodules in k[s]^{q} and O^{q}, respectively, such that k(s)L = k(s)M. That the two definitions are equivalent follows from the next lemma. The relation is established as follows. If (L, M) is a convolutional code in the sense of [4], then L + s^{−1}M is a convolutional code in the sense of the present paper. Conversely, if C is a convolutional code in the sense of this paper, then (C ∩ k[s]^{q}, sC ∩ O^{q}) is a convolutional code in the sense of [4].

Lemma 17. If L and M are submodules in k[s]^{q} and O^{q}, respectively, then k(s)L = k(s)M if and only if there exists a transfer function E such that

L, M ⊆ E and [E : (L + s^{−1}M)] < +∞.

Proof. “If”. The hypothesis implies that the modules L and M have the same rank, say, m. There exist a polynomial matrix F and a proper rational matrix Q, both of size q × m, such that

L = F k[s]^{m} and M = QO^{m}.

Then F k(s)^{m} = Qk(s)^{m}, and consequently Q = A^{−1}F for some nonsingular rational matrix A. Putting E = k(s)M, we have a bijective linear map F : k(s)^{m} → E. This induces an isomorphism

H^{0}(s^{−1}A) ≃ E/(L + s^{−1}M).

It remains now to apply the Finiteness theorem.

“Only if”. It is clear that k(s)L, k(s)M ⊆ E. We claim that in fact we have equalities. Indeed, assume that, say, k(s)L ≠ E. We then have an exact sequence

0 → (M + k(s)L)/k(s)L → E/k(s)L → E/(k(s)L + M) → 0.

Clearly, (M + k(s)L)/k(s)L is a finitely generated O-submodule in E/k(s)L and therefore has infinite codimension (as a k-linear subspace). On the other hand, the hypothesis implies that E/(k(s)L + M) has finite dimension. A contradiction.

Let (α, F) be a convolutional encoder, with input number m, and let A be a representative of α. We define the convolutional code of (α, F) by the formula

CC(α, F) = F k[s]^{m} + s^{−1}F AO^{m}.

It is easily seen that this indeed is a convolutional code. Its transfer function certanly is equal to F k(s)^{m}.

Notice that two equivalent convolutional encoders generate the same convolutional code.

Proposition 3. The mapping (α, F) ↦ CC(α, F) induces a one-to-one correspondence between the equivalence classes of convolutional encoders and the convolutional codes.

Proof. Suppose that (α_{1}, F_{1}) and (α_{2}, F_{2}) generate the same code, i.e.,

F_{1}k[s]^{m} + s^{−1}F_{1}A_{1}O^{m} = F_{2}k[s]^{m} + s^{−1}F_{2}A_{2}O^{m}.

We clearly have

F_{1}k[s]^{m} = F_{2}k[s]^{m} and F_{1}A_{1}O^{m} = F_{2}A_{2}O^{m}.

It follows that

F_{2} = F_{1}U and F_{2}A_{2} = F_{1}A_{1}V

for some unimodular matrix U and biproper matrix V. It is easily seen that V = A_{1}^{−1}UA_{2}, and so the encoders are equivalent.

The rest follows from the proof of the “if” part of Lemma 17. Indeed, suppose that C is a convolutional code. Put L = C ∩ k[s]^{q} and M = sC ∩ O^{q}, and let A and F be as in that proof. Then (α, F), where α is the congruence class of A, generates C.

Lemma 18. Let C be a convolutional code with transfer function E. Then

[C^{⊥} : E^{⊥}] = [E : C].

Proof. Let m be the input number and (α, F) a convolutional encoder generating C.

Choose any representative A of α, and put G = F^{tr}. Applying Lemmas 3 and 5, we obtain

C^{⊥} = (F k[s]^{m} + s^{−1}F AO^{p})^{⊥} = (F k[s]^{m})^{⊥} ∩ (s^{−1}F AO^{m})^{⊥}
= G^{−1}k[s]^{m} ∩ G^{−1}(s^{−1}A^{∗}O^{m}) = G^{−1}H^{0}(s^{−1}A^{∗}).

Using again Lemma 5, we have

E^{⊥} = (F k(s)^{m})^{⊥} = G^{−1}{0}.

Since G has a full row rank, it induces a surjective linear map of G^{−1}H^{0}(s^{−1}A^{∗}) onto H^{0}(s^{−1}A^{∗}). The kernel is equal to G^{−1}{0}, and consequently we have a canonical isomorphism

C^{⊥}/E^{⊥} ≃ H^{0}(s^{−1}A^{∗}).

There is also a canonical isomorphism

H^{1}(s^{−1}A) ≃ E/C,

which is determined by the bijective linear map k(s)^{m} → E. It remains now to apply Serre’s duality theorem.

5. Frequency Responses

A frequency response is a linear subspace R in k(s)^{q} satisfying the following conditions:

(FR1) There is a transfer function T such that T ⊆ R and [R : T] < +∞; (FR2) R is invariant with respect to π_{−} and π_{+}; (FR3) R∩k[s]^{q} and sR∩O^{q} are invariant with respect to τ and σ, respectively.

By Lemma 8(b), the “T ” is determined uniquely, and we call it the transfer function of R. The number [R : T] is called the McMillan degree. By the property (FR2), we have

R = (R ∩ k[s]^{q}) + (R ∩ s^{−1}O^{q}).

Proposition 4. Let (β, G) be an AR-model with state space X. Then G^{−1}(X) is a frequency response.

Proof. Put R = G^{−1}X, and let p be the output number and B a representative of β.

The space R satisfies (FR1). Indeed, if T = G^{−1}{0} is the transfer function of our AR-model, then we have a short exact sequence

0 → T → R → X → 0,

and this implies that [R : T] < +∞.

Take f ∈ k[s]^{q} and g ∈ s^{−1}O^{q}. We have Gf ∈ k[s]^{p} and Gg ∈ s^{−1}BO^{p}. Therefore G(f + g) ∈ X if and only if Gf ∈ X and Gg ∈ X. Hence R satisfies (FR2).

Let f ∈ R ∩ k[s]^{q}, and let a be the free coefficient of f. We then have τf = s^{−1}f − as^{−1}. Since Gf ∈ s^{−1}BO^{p} and Ga ∈ BO^{p}, it follows that G(τf) ∈ s^{−1}BO^{p}. On the other hand, G(τf) ∈ k[s]^{p} because τf ∈ k[s]^{q}. Consequently G(τf) ∈ X; whence τf ∈ R ∩ k[s]^{q}. Let now g ∈ sR ∩ O^{q}, and let b be the free coefficient of g. We then have σg = sg − sb. Since Gg ∈ sk[s]^{p} and Gb ∈ k[s]^{p}, it follows that G(σg) ∈ sk[s]^{p}. On the other hand, G(σg) ∈ BO^{p} because σg ∈ O^{q}. Consequently G(σg) ∈ sX; whence σg ∈ sR ∩ O^{q}. We see that R satisfies (FR3).

We shall write F R(β, G) to denote the frequency response associated to an AR-model (β, G).

Proposition 5. If (β, G) is an AR-model, then

F R(β, G) = CC(β^{∗}, G^{tr})^{⊥}.

Proof. Let p be the output number of (β, G) and B a representative of β. Applying Lemmas 1, 3 and 5, we have

F R(β, G) = G^{−1}(k[s]^{p} ∩ s^{−1}BO^{p}) = G^{−1}k[s]^{p} ∩ s^{−1}(B^{−1}G)^{−1}O^{p}
= (G^{tr}k[s]^{p})^{⊥} ∩ (s^{−1}(B^{−1}G)^{tr}O^{p})^{⊥} = (G^{tr}k[s]^{p} + s^{−1}(B^{−1}G)^{tr}O^{p})^{⊥}
= CC(β^{∗}, G^{tr})^{⊥}.

Theorem 1.

a) If C is a convolutional code, then C^{⊥} is a frequency response.

b) If R is a frequency response, then R^{⊥} is a convolutional code.

Proof. a) Follows from the previous two propositions and the fact that C is representable as the convolutional code of some convolutional encoder.

b) By Lemmas 7 and 4, we have a nondegenerate bilinear form

R/T × T^{⊥}/R^{⊥} → k.  (3)

This implies that [T^{⊥} : R^{⊥}] < +∞, and thus R^{⊥} satisfies (CC1).

Using Lemmas 1 and 3, we can easily see that R^{⊥} satisfies the property (CC2). Let us show that R + k[s]^{q} and s^{−1}R + s^{−2}O^{q} are modules over k[s] and O,

respectively. Suppose first w ∈ R + k[s]^{q}. By (FR2), w = f + s^{−1}g, where f ∈ k[s]^{q} and g ∈ sR ∩ O^{q}. Let g = b_{0} + b_{1}s^{−1} + . . .. Then, for each i ≥ 0, we have

s^{i}w = s^{i}f + s^{i−1}g = (s^{i}f + b_{0}s^{i−1} + ⋯ + b_{i−1}) + σ^{i}g ∈ R + k[s]^{q}.

It follows that R + k[s]^{q} is a k[s]-submodule. Now, suppose that w ∈ s^{−1}R + s^{−2}O^{q}. By (FR2), w = s^{−1}f + s^{−2}g, where f ∈ R ∩ k[s]^{q} and g ∈ O^{q}. Let f = a_{0}s^{n} + ⋯ + a_{n}. Then, for each n ≥ i ≥ 0, we have

s^{−i}w = s^{−i−1}f + s^{−i−2}g
= s^{−1}(τ^{i}f + a_{n−i+1}s^{−1} + ⋯ + a_{n}s^{−i}) + s^{−i−2}g ∈ s^{−1}R + s^{−2}O^{q}.

Further, hw ∈ s^{−2}O^{q} for each h ∈ s^{−n−1}O^{q}. It follows that s^{−1}R + s^{−2}O^{q} is an O-module. Using Lemmas 1 and 3, we see that

R^{⊥} ∩ k[s]^{q} = (R + k[s]^{q})^{⊥} and sR^{⊥} ∩ O^{q} = (s^{−1}R + s^{−2}O^{q})^{⊥}

are submodules in k[s]^{q} and O^{q}, respectively. Thus R^{⊥} has the property (CC3).

Theorem 2.

a) If C is a convolutional code, then C^{⊥⊥} = C.

b) If R is a frequency response, then R^{⊥⊥} = R.

Proof. The proofs for both statements are similar, and we restrict ourselves to showing, say, b).

Let T be the transfer function of R. Put C = R^{⊥} and E = T^{⊥}. From (3) and Lemma 18 (and Lemma 7) we obtain

[R : T] = [E : C] = [C^{⊥} : T].

Further, it is obvious that R ⊆ C^{⊥}. Hence there is a canonical exact sequence

0 → R/T → C^{⊥}/T → C^{⊥}/R → 0.

By the dimension argument, the second linear map in this sequence is bijective. So C^{⊥}/R = 0, and the theorem follows.

We can now state and prove our main result.

Theorem 3. The mapping (β, G) ↦ F R(β, G) induces a one-to-one correspondence between the equivalence classes of AR-models and the frequency responses.

Proof. Follows immediately from Proposition 3, and Theorems 1 and 2.

6. Controllability

A convolutional code C with transfer function E is called controllable if

E ∩ k[s]^{q} ⊆ C and E ∩ s^{−1}O^{q} ⊆ C.

Remark. In [4] we called the property above the observability property (we have done this following [7]). In view of Proposition 8, we feel that the term “controllable” is more appropriate.

Proposition 6. If E is a transfer function, then (E ∩ k[s]^{q}) + (E ∩ s^{−1}O^{q}) is a controllable convolutional code. The map

E ↦ (E ∩ k[s]^{q}) + (E ∩ s^{−1}O^{q})

establishes a one-to-one correspondence between transfer functions and controllable convolutional codes.

Proof. Let E be a transfer function. It is clear that E ∩ k[s]^{q} and sE ∩ O^{q} are submodules in k[s]^{q} and O^{q}, respectively. The fraction spaces of these modules clearly coincide with E. So (E ∩ k[s]^{q}) + (E ∩ s^{−1}O^{q}) is a convolutional code whose transfer function is E. It immediately follows from the definition that this code is controllable.

Let now C be a controllable convolutional code with transfer function E. By definition,

C ∩ k[s]^{q} = E ∩ k[s]^{q} and C ∩ s^{−1}O^{q} = E ∩ s^{−1}O^{q}.

Therefore C = (E ∩ k[s]^{q}) + (E ∩ s^{−1}O^{q}).

Proposition 7. Let (α, F) be a convolutional encoder and C its code. Then C is controllable if and only if so is (α, F).

Proof. Follows from Lemma 9.

A frequency response R with transfer function T is called controllable if

R ⊆ T + k[s]^{q} and R ⊆ T + s^{−1}O^{q}.

Lemma 19. Let E be a transfer function. Then

(E ∩ k[s]^{q})^{⊥} = E^{⊥} + k[s]^{q} and (E ∩ s^{−1}O^{q})^{⊥} = E^{⊥} + s^{−1}O^{q}.

Proof. Let m denote the dimension of E.

There exist a right unimodular polynomial matrix P such that E ∩ k[s]^{q} = P^{tr}k[s]^{m} and a right biproper matrix Q such that E ∩ O^{q} = Q^{tr}O^{m}. We clearly have P k[s]^{q} = k[s]^{m} and QO^{q} = O^{m}. Consequently,

P^{−1}(k[s]^{m}) = P^{−1}{0} + k[s]^{q} and Q^{−1}(s^{−1}O^{m}) = Q^{−1}{0} + s^{−1}O^{q}.

Lemma 5 completes the proof.

Proposition 8. Let R be a frequency response, and let C be the corresponding convolutional code. Then R is controllable if and only if C is controllable.

Proof. The “if” part follows from the previous lemma. The “only if” part is obvious by Lemma 3.

Proposition 9. If T is a transfer function, then (T + k[s]^{q}) ∩ (T + s^{−1}O^{q}) is a controllable frequency response. The map

T ↦ (T + k[s]^{q}) ∩ (T + s^{−1}O^{q})

establishes a one-to-one correspondence between transfer functions and controllable frequency responses.

Proof. Follows from Lemma 3 and the previous two propositions.

Remark. Transfer functions and controllable frequency responses are not the same objects. The equality T = (T + k[s]^{q}) ∩ (T + s^{−1}O^{q}) holds if and only if T is generated by a scalar matrix.

Proposition 10. Let (β, G) be an AR-model and R its frequency response. Then R is controllable if and only if so is (β, G).

Proof. Follows from Propositions 7 and 8.

We need the following

Lemma 20. Let D be a nonsingular rational r ×r matrix having nonpositive Wiener–Hopf indices. Let d be the Chern number of D^{−1}, and let n ≥ d. Then, for all f, g ∈ k(s)^{r}, there exists h ∈ k(s)^{r} such that

s^{n}h ≡ f mod k[s]^{m} and h ≡ g mod s^{−1}DO^{m}.

Proof. If the assertion is true for D, then it is true for UD as well, where U is a unimodular matrix. Therefore, by the Wiener–Hopf factorization theorem, there will be no loss of generality if we assume that D = diag(s^{−d_{1}}, …, s^{−d_{r}}). The proof can be obviously reduced to the case where r = 1, which is easy. Indeed, let

f = (a_{1}s^{−1} + a_{2}s^{−2} + ⋯) mod k[s] and g = (b_{0}s^{−d} + b_{1}s^{−d+1} + ⋯) mod s^{−d−1}O,

where a_{i} and b_{i} are constants. Clearly,

h = s^{−n}(a_{1}s^{−1} + a_{2}s^{−2} + ⋯) + (b_{0}s^{−d} + b_{1}s^{−d+1} + ⋯)

has the required property.

We now present an interpretation of controllability that is analogous to that of Willems [7].

Theorem 4. Let R be a frequency response with transfer function T and McMillan degree d, and let n ≥ d. Then R is controllable if and only if, for all w_{−} ∈ R ∩ k[s]^{q} and w_{+} ∈ R ∩ s^{−1}O^{q}, there exists w ∈ T such that

π_{−}(w) = w_{−} and π_{+}(s^{n}w) = w_{+}.

Proof. The “if” part is obvious.

To prove the “only if” part consider an AR-model (β, G) generating R. Let (α, F) be its kernel description. We remark that the complexity of (α, F) is equal to the McMillan degree of (β, G) (see Corollary 1). Take w_{−} ∈ R ∩ k[s]^{q} and w_{+} ∈ R∩s^{−1}O^{q}. The exact sequences (2) imply that there exist f_{+} ∈ s^{−1}O^{q} and f_{−} ∈ k[s]^{q} such that Gf_{+} = Gw_{−} and Gf_{−} = Gw_{+}. We have w_{−} − f_{+} ∈ T and w_{+} − f_{−} ∈ T. Therefore we can choose u_{1}, u_{2} ∈ k(s)^{m} such that F u_{1} = w_{−} − f_{+}, F u_{2} = w_{+} − f_{−}. By the previous lemma, there exists u ∈ k(s)^{m} satisfying the condition

u ≡ u_{1} mod s^{−1}AO^{m} and s^{n}u ≡ u_{2} mod k[s]^{m}.

(Here A is a representative of α.) Set w = F u. Using again (2), we have

w ≡ (w_{−} − f_{+}) mod s^{−1}O^{q} and s^{n}w ≡ (w_{+} − f_{−}) mod k[s]^{q}.

It follows that w does the job.

7. “Classical” Case

A convolutional encoder (α, F) is regular if F A, where A is any representative of α, is left biproper.

Lemma 21. There is a canonical one-to-one correspondence between regular convolutional encoders and full column rank polynomial matrices which is given by

(α, F) → F.

Proof. Let F be a full column rank polynomial matrix of size m × q. The set

F^{−1}O^{q} = {u ∈ k(s)^{m}| F u ∈ O^{q}}

obviously is an O-submodule of k(s)^{m}. There is a canonical embedding F^{−1}O^{q} → O^{q}, and therefore this module must be finitely generated. We obtain that F^{−1}O^{q} = AO^{m} for some nonsingular rational matrix A. Clearly, F A is proper because F AO^{m} ⊆ O^{q}. By construction, F AO^{m} = F k(s)^{m} ∩ O^{q}, and therefore F A must be left biproper (see Lemma 9b)). We conclude that our mapping is surjective.

To show that our mapping is injective, assume that A′ is another nonsingular rational matrix such that F A′ is left biproper. Using again Lemma 9b), we have F A′O^{m} = F k(s)^{m} ∩ O^{q}. This implies that F A′O^{m} = F^{−1}O^{q}, and consequenly F A′O^{m} = F AO^{m}. It follows that A′O^{m} = AO^{m}, and thus A^{−1}A′ is biproper.

A convolutional code C with transfer function E is said to be regular if

E ∩ s^{−1}O^{q} ⊆ C.

We refer to convolutional codes as defined in Rosenthal et al. [6] as “classical” convolutional codes. These are submodules in k[s]^{q}.

Lemma 22. There is a canonical one-to-one correspondence between regular convolutional codes and “classical” ones; this is given by

C ↦ C ∩ k[s]^{q}.

Proof. We have a canonical mapping in the opposite direction. Indeed, if C ⊆ k[s]^{q} is a “classical” convolutional code, then

C + s^{−1}(E ∩ O^{q}),

where E = k(s)C, is a regular convolutional code. It is easily seen that the two mappings are inverse to each other.

Given a full column rank polynomial matrix (i.e., a “classical” convolutional encoder) F, one defines its code by the formula

CC(F) = F k[s]^{m},

where m is the column number of F. Clearly, if (α, F) is a regular convolutional encoder, then

CC(F) = CC(α, F) ∩ k[s]^{q}.

Proposition 3′. The mapping F ↦ CC(F) induces a one-to-one correspondence between equivalence classes of full column rank polynomial matrices and “classical” convolutional codes.

Proof. Follows from Proposition 3 and the previous two lemmas.

Remark. Of course the proposition above can be proved directly, and of course the direct proof is obvious.

An AR-model (β, G) is regular if B^{−1}G, where B is any representative of β, is right biproper.

Lemma 23. There is a canonical one-to-one correspondence between regular AR-models and full row rank polynomial matrices which is given by

(β, G) → G.

Proof. Follows from Lemma 21 by transposition.

A frequency response R with transfer function T is said to be regular if

R ⊆ T + s^{−1}O^{q}.

We call any k-linear subspace R ⊆ s^{−1}O^{q} such that

[sR : M] < +∞ for some “classical” transfer function M and σ(sR) ⊆ sR a “classical” frequency response. By a “classical” transfer function we mean any submodule M ⊆ O^{q} that satisfies the conditions of Lemma 9b).

Lemma 24. There is a canonical one-to-one correspondence between regular frequency responses and “classical” ones which is given by

R ↦ R ∩ s^{−1}O^{q}.

Proof. Let R be a regular frequency response, and let T be its transfer function. The canonical linear map

R ∩ s^{−1}O^{q} → R/T

is surjective. Indeed, if w ∈ R, then w = w_{0} + g, where w_{0} ∈ T and g ∈ s^{−1}O^{q}, and we clearly have g ∈ R∩s^{−1}O^{q} and g mod T = w mod T. Further, the kernel of this map is equal to T ∩s^{−1}O^{q}, and therefore there is a canonical isomorphism

(R ∩ s^{−1}O^{q})/(T ∩ s^{−1}O^{q}) ≃ R/T.

It immediately follows from this that R ∩ s^{−1}O^{q} is a “classical” frequency response.

Let now R be a “classical” frequency response, and let M be the “classical” transfer function that exists by definition. Put T = k(s)M. We claim that T + R is a regular frequency response.

Consider the canonical linear map

R → (T + R)/T, w ↦ w mod T.

It is easily seen that this map is surjective and its kernel is equal to T ∩ R. We have

s^{−1}M ⊆ T ∩ R ⊆ T ∩ s^{−1}O^{q} = s^{−1}M,

and consequently T ∩ R = s^{−1}M. It follows that [(T + R) : T] = [R : s^{−1}M]. Let n ≥ 1 and g ∈ M. If g = b_{0} + b_{1}s^{−1} + b_{2}s^{−2} + …, then

s^{n−1}g = (b_{0}s^{n−1} + ⋯ + b_{n−1}) + s^{−1}(b_{n} + b_{n+1}s^{−1} + …).

Consequently,

π_{−}(s^{n−1}g) = s^{n−1}g − s^{−1}σ^{n}(g) ∈ T + R.

Now the point is that modulo s^{−1}O^{q} any element of T is equal to a linear combination of elements of the form s^{n−1}g, with n ≥ 1 and g ∈ M. (Indeed, because T = k(s)M, every element in T is a sum of elements of the form ag, with a ∈ k(s) and g ∈ M. Therefore modulo s^{−1}O^{q} every element in T is a sum of elements of the form ag, with a ∈ k[s] and g ∈ M.) It follows that the polynomial parts of elements in T belong to T + R. Automatically, the same is true for the strictly proper parts. We conclude that T + R satisfies (FR2).

Notice that (T + R) ∩ k[s]^{q} consists just of the polynomial parts of elements in T. Take an arbitrary f ∈ (T + R) ∩ k[s]^{q}, and suppose that f = π_{−}(w), where w ∈ T. Then

τ(f) = π_{−}(s^{−1}w) ∈ (T + R) ∩ k[s]^{q}.

Hence (T + R) ∩ k[s]^{q} is invariant under τ. Further, it is easily seen that (T + R) ∩ s^{−1}O^{q} = R, and we conclude that T + R satisfies (FR3).

Obviously, T + R ⊆ T + s^{−1}O^{q}, and the proof is completed.

Given a full row rank polynomial matrix (i.e., a “classical” AR-model) G, we define its frequency response by the formula

F R(G) = {w ∈ s^{−1}O^{q}| Gw ∈ k[s]^{p}}.

This is exactly what Kuijper [2] calls the rational behavioral space. It is clear that if (β, G) is a regular AR-model, then

F R(G) = F R(β, G) ∩ s^{−1}O^{q}.

Theorem 3′. The mapping G ↦ F R(G) induces a one-to-one correspondence between equivalence classes of full row rank polynomial matrices and “classical” frequency responses.

Proof. Follows from Theorem 3 and the previous two lemmas.

Remark. One may want to deduce the above theorem directly from Proposition 3′. For this one should consider the bilinear form k[s]^{q} × s^{−1}O^{q} → k. But this consideration is not so easy.

Acknowledgement

The author wishes to express his gratitude to the referee for a very careful reading of the manuscript and indicating several errors.

References

1. G. D. Forney, Convolutional codes I: Algebraic structure. IEEE Trans. Inform. Theory 19(1970), 720–738.

2. M. Kuijper, First order representations of linear systems. Birkhäuser, Boston, 1994.

3. V. Lomadze, Singular linear behaviors and their AR-representations. Math. Control Signals Systems 14(2001), 194–211.

4. V. Lomadze, Convolutional codes and coherent sheaves. Appl. Algebra Engrg. Comm. Comput. (to appear).

5. V. Lomadze, Linear dynamical systems: An axiomatic approach. Georgian Math. J. (to appear).

6. J. Rosenthal, J. M. Schumacher, and E. V. York, On behaviors and convolutional codes. IEEE Trans. Inform. Theory 42(1996), 1881–1891.

7. J. C. Willems, Paradigms and puzzles in the theory of dynamical systems. IEEE Trans. Automat. Control 36(1991), 259–294.

(Received 25.06.2001; revised 24.07.2001)

Author’s address: A. Razmadze Mathematical Institute Georgian Academy of Sciences 1, M. Aleksidze St., Tbilisi 380093 Georgia E-mail: loma@rmi.acnet.ge