Minimal Realizations of Syndrome Formers of a Special Class of 2D Codes

Abstract

In this paper we consider a special class of 2D convolutional codes (composition codes) with encoders G(d ₁, d ₂) that can be decomposed as the product of two 1D encoders, i.e., $G(d_{1},d_{2}) = G_{2}(d_{2})G_{1}(d_{1})$. In case that $G_{1}(d_{1})$ and $G_{2}(d_{2})$ are prime we provide constructions of syndrome formers of the code, directly from $G_{1}(d_{1})$ and $G_{2}(d_{2})$. Moreover we investigate the minimality of 2D state-space realization by means of a separable Roesser model of syndrome formers of composition codes, where $G_{2}(d_{2})$ is a quasi-systematic encoder.

1 Introduction and Preliminary Concepts

Minimal state-space realization of convolutional codes play an important role in efficient code generation and verification. This question has been widely investigated in the literature for 1D codes [3, 6], however it is still open for the 2D case. Preliminary results concerning 2D encoder and code realizations have been presented in [10]. In this paper we study the syndrome former realization problem for a special class of 2D codes.

We consider 2D convolutional codes constituted by sequences indexed by $\mathbb{Z}^{2}$ and taking values in $\mathbb{F}^{n}$, where $\mathbb{F}$ is a field. Such sequences $\{w(i,j)\}_{(i,j)\in \mathbb{Z}^{2}}$ can be represented by bilateral formal power series

$$\displaystyle{\hat{w}(d_{1},d_{2}) =\sum _{(i,j)\in \mathbb{Z}^{2}}w(i,j)d_{1}^{i}d_{ 2}^{j}.}$$

For $n \in \mathbb{N}$, the set of 2D bilateral formal power series over $\mathbb{F}^{n}$ is denoted by $\mathcal{F}_{2D}^{n}$. This set is a module over the ring $\mathbb{F}[d_{1},d_{2}]$ of 2D polynomials over $\mathbb{F}$. The set of matrices of size n × k with elements in $\mathbb{F}[d_{1},d_{2}]$ will be denoted by $\mathbb{F}^{n\times k}[d_{1},d_{2}]$.

Given a subset $\mathcal{C}$ of sequences indexed by $\mathbb{Z}^{2}$, taking values in $\mathbb{F}^{n}$, we denote by $\hat{\mathcal{C}}$ the subset of $\mathcal{F}_{2D}^{n}$ defined by $\hat{\mathcal{C}} =\{\hat{ w}\mid w \in \mathcal{C}\}$.

Definition 1

A 2D convolutional code is a subset $\mathcal{C}$ of sequences indexed by $\mathbb{Z}^{2}$ such that $\hat{\mathcal{C}}$ is a submodule of $\mathcal{F}_{2D}^{n}$ which coincides with the image of $\mathcal{F}_{2D}^{k}$ (for some $k \in \mathbb{N}$) by a polynomial matrix G(d ₁, d ₂), i.e.,

$$\displaystyle{ \hat{\mathcal{C}} =\mathop{ \mathrm{im}}\nolimits G(d_{1},d_{2}) =\{\hat{ w}(d_{1},d_{2})\mid \hat{w}(d_{1},d_{2}) = G(d_{1},d_{2})\hat{u}(d_{1},d_{2}),\;\hat{u}(d_{1},d_{2}) \in \mathcal{F}_{2D}^{k}\}. }$$

It follows, as a consequence of [Theorem 2.2, [7]], that a 2D convolutional code can always be given as the image of a full column rank polynomial matrix $G(d_{1},d_{2}) \in \mathbb{F}^{n\times k}[d_{1},d_{2}]$. Such polynomial matrix is called an encoder of $\mathcal{C}$. A code with encoders of size n × k is said to have rate k∕n.

A 2D convolutional code $\mathcal{C}$ of rate k∕n can also be represented as the kernel of a (n − k) × n left-factor prime polynomial matrix (i.e. a matrix without left nonunimodular factors), as follows from [Theorem 1, [12]].

Definition 2

Let $\mathcal{C}$ be a 2D convolutional code of rate k∕n. A left-factor prime matrix $H(d_{1},d_{2}) \in \mathbb{F}^{(n-k)\times n}[d_{1},d_{2}]$ such that

$$\displaystyle{\hat{\mathcal{C}} =\ker H(d_{1},d_{2}),}$$

is called a syndrome former of $\mathcal{C}$.

Note that w is in $\mathcal{C}$ if and only if $H(d_{1},d_{2})\hat{w} = 0$.

Remark 3

This means that whereas codewords are output sequences of an encoder, they constitute the output-nulling inputs of a syndrome former of the code.

Given an encoder G(d ₁, d ₂) of $\mathcal{C}$, a syndrome former of $\mathcal{C}$ can be obtained by constructing a (n − k) × n left-factor prime matrix H(d ₁, d ₂) such that H(d ₁, d ₂)G(d ₁, d ₂) = 0. Moreover all syndrome formers of $\mathcal{C}$ are of the form U(d ₁, d ₂)H(d ₁, d ₂), where $U(d_{1},d_{2}) \in \mathbb{F}^{(n-k)\times (n-k)}[d_{1},d_{2}]$ is unimodular.

2 Composition Codes and Their Syndrome Formers

In this section we consider a particular class of 2D convolutional codes generated by 2D polynomial encoders that are obtained from the composition of two 1D polynomial encoders. Such encoders/codes will be called composition encoders/codes. Our goal is to characterize the syndrome formers of such codes. The formal definition of composition encoders is as follows.

Definition 4

An encoder $G(d_{1},d_{2}) \in \mathbb{F}^{n\times k}[d_{1},d_{2}]$ such that

$$\displaystyle{ G(d_{1},d_{2}) = G_{2}(d_{2})G_{1}(d_{1}), }$$

(1)

where $G_{1}(d_{1}) \in \mathbb{F}^{p\times k}[d_{1}]$ and $G_{2}(d_{2}) \in \mathbb{F}^{n\times p}[d_{2}]$ are 1D encoders, is said to be a composition encoder.

Note that the requirement that $G_{i}(d_{i})$, for i = 1, 2, is a 1D encoder implies the condition that $G_{i}(d_{i})$ is a full column rank matrix. Moreover this requirement clearly implies that $G_{2}(d_{2})G_{1}(d_{1})$ has full column rank, hence the composition $G_{2}(d_{2})G_{1}(d_{2})$ of two 1D encoders is indeed a 2D encoder.

The 2D composition code $\mathcal{C}$ associated with G(d ₁, d ₂) is such that

$$\displaystyle\begin{array}{rcl} \hat{\mathcal{C}}& =& \mathop{\mathrm{im}}\nolimits G(d_{1},d_{2}) = G_{2}(d_{2})(\mathop{\mathrm{im}}\nolimits G_{1}(d_{1})) {}\\ & =& \{\hat{w}(d_{1},d_{2})\mid \exists \;\hat{z}(d_{1},d_{2}) \in \mathop{\mathrm{im}}\nolimits (G_{1}(d_{1}))\mbox{ such that }\;\hat{w}(d_{1},d_{2}) = G_{2}(d_{2})\hat{z}(d_{1},d_{2})\}.{}\\ \end{array}$$

We shall concentrate on a particular class of composition codes, namely on those that admit a composition encoder G(d ₁, d ₂) as in (1) with $G_{2}(d_{2})$ and $G_{1}(d_{1})$ both right-prime encoders (i.e., they admit a left polynomial inverse), and derive a procedure for constructing the corresponding syndrome formers based on 1D polynomial methods. This procedure will be useful later on for the study of state-space realizations.

It is important to observe that as $G_{2}(d_{2})$ and $G_{1}(d_{1})$ are both assumed to have polynomial inverses, then $G(d_{1},d_{2})$ also has a 2D polynomial left inverse (given by the product of the left inverses of $G_{1}(d_{1})$ and $G_{2}(d_{2})$) and therefore $G(d_{1},d_{2})$ is right-zero prime¹(rZP). Recall that if a 2D convolutional code admits a right-zero prime encoder then all its rFP encoders are rZP. Moreover, the corresponding syndrome formers are also lZP (see Prop. A.4 of [4]).

Since $G_{2}(d_{2}) \in \mathbb{F}^{n\times p}[d_{2}]$ is right-prime there exists a unimodular matrix $U(d_{2}) \in \mathbb{F}^{n\times n}[d_{2}]$ such that

$$\displaystyle{U(d_{2})G_{2}(d_{2}) = \left [\begin{array}{*{10}c} I_{p} \\ 0 \end{array} \right ].}$$

We shall partition U(d ₂) as

$$\displaystyle{ U(d_{2}) = \left [\begin{array}{*{10}c} L_{2}(d_{2}) \\ H_{2}(d_{2}) \end{array} \right ], }$$

(2)

where $L_{2}(d_{2})$ has p rows.

It is easy to check that, if $H_{1}(d_{1}) \in \mathbb{F}^{(p-k)\times p}[d_{1}]$ is a syndrome former of the 1D convolutional code $\mathop{\mathrm{im}}\nolimits G_{1}(d_{1})$ (i.e., $H_{1}(d_{1})$ is left-prime and is such that $H_{1}(d_{1})G_{1}(d_{1}) = 0$), then

$$\displaystyle{ \left [\begin{array}{*{10}c} H_{1}(d_{1})L_{2}(d_{2}) \\ H_{2}(d_{2}) \end{array} \right ]G_{2}(d_{2})G_{1}(d_{1}) = 0. }$$

(3)

This reasoning leads to the following proposition.

Proposition 5

Let $\mathcal{C}$ , with $\hat{\mathcal{C}}\! =\!\mathop{ \mathrm{im}}\nolimits G(d_{1},d_{2})$ , be a composition code with $G(d_{1},d_{2})\! \in \mathbb{F}^{n\times k}[d_{1},d_{2}]$ such that $G(d_{1},d_{2}) = G_{2}(d_{2})G_{1}(d_{1})$ , where $G_{2}(d_{2}) \in \mathbb{F}^{n\times p}[d_{2}]$ and $G_{1}(d_{1}) \in \mathbb{F}^{p\times k}[d_{1}]$ are both right-prime 1D encoders. Let further $H_{1}(d_{1})$ be a (p − k) × p 1D syndrome former of $\mathop{\mathrm{im}}\nolimits G_{1}(d_{1})$ and define $\left [\begin{array}{*{10}c} L_{2}(d_{2}) \\ H_{2}(d_{2}) \end{array} \right ]$ as in (2). Then

$$\displaystyle{ H(d_{1},d_{2}) = \left [\begin{array}{*{10}c} H_{1}(d_{1})L_{2}(d_{2}) \\ H_{2}(d_{2}) \end{array} \right ] }$$

is a syndrome former of $\mathcal{C}$ .

Proof

Since (3) is obviously satisfied and H(d ₁, d ₂) has size (n − k) × n, we only have to prove that H(d ₁, d ₂) is left-factor prime. Note that as $H_{1}(d_{1})$ is left-prime, there exists $R_{1}(d_{1}) \in \mathbb{F}^{p\times (p-k)}[d_{1}]$ such that $H_{1}(d_{1})R_{1}(d_{1}) = I_{p-k}$. Now it is easy to see that

$$\displaystyle{ R(d_{1},d_{2}) = U(d_{2})^{-1}\left [\begin{array}{*{10}c} R_{1}(d_{1})& 0 \\ 0 &I_{n-p} \end{array} \right ]. }$$

constitutes a polynomial right inverse of H(d ₁, d ₂). Consequently H(d ₁, d ₂) is left-zero prime which implies that it is left-factor prime as we wish to prove. □ 

3 State-Space Realizations of Encoders and Syndrome Formers

In this section we recall some fundamental concepts concerning 1D and 2D state-space realizations of transfer functions, having in mind the realizations of encoders and syndrome formers.

A 1D state-space model

$$\displaystyle{ \left \{\begin{array}{@{}l@{\quad }l@{}} x(t + 1) = Ax(t) + Bu(t)\quad \\ w(t) = Cx(t) + Du(t)\quad \end{array} \right. }$$

denoted by Σ ^1D(A, B, C, D) is a realization of dimension m of $M(d) \in \mathbb{F}^{s\times r}[d]$ if $M(d) = C(I_{m} - Ad)^{-1}Bd + D$. Moreover, it is a minimal realization if the size of the state x is minimal among all the realizations of M(d). The dimension of a minimal realization of M(d) is called the McMillan degree of M(d) and is given by $\mu (M) =\mathrm{ int}\deg \left [\begin{array}{*{10}c} M(d)\\ I_{ r} \end{array} \right ]$, where $\mathrm{int}\deg M(d)$ is the maximum degree of its r-order minors [11].

As for the 2D case, there exist several types of state-space models [1, 2]. In our study we shall consider separable Roesser models [13]. These models have the following form:

$$\displaystyle{ \left \{\begin{array}{@{}l@{\quad }l@{}} x_{1}(i + 1,j) = A_{11}x_{1}(i,j) + A_{12}x_{2}(i,j) + B_{1}u(i,j)\quad \\ x_{2}(i,j + 1) = A_{21}x_{1}(i,j) + A_{22}x_{2}(i,j) + B_{2}u(i,j)\quad \\ y(i,j) = C_{1}x_{1}(i,j) + C_{2}x_{2}(i,j) + Du(i,j) \quad \end{array} \right. }$$

(4)

where A ₁₁, A ₁₂, A ₂₁, A ₂₂, B ₁, B ₂, C ₁, C ₂ and D are matrices over $\mathbb{F}$, with suitable dimensions, u is the input-variable, y is the output-variable, and x = (x ₁, x ₂) is the state variable where x ₁ and x ₂ are the horizontal and the vertical state-variables, respectively. The dimension of the system described by (4) is given by the size of x. Moreover either A ₁₂ = 0 or A ₂₁ = 0. The separable Roesser model corresponding to Eqs. (4) with A ₁₂ = 0 is denoted by $\varSigma _{12}^{2D}(A_{11},A_{21},A_{22},B_{1},B_{2},C_{1},C_{2},D)$, whereas the one with A ₂₁ = 0 is denoted by $\varSigma _{21}^{2D}(A_{11},A_{12},A_{22},B_{1},B_{2},C_{1},C_{2},D)$.

The remaining considerations of this section can be stated for both cases when A ₁₂ = 0 or A ₂₁ = 0, however we just consider A ₁₂ = 0; the case A ₂₁ = 0 is completely analogous, with the obvious adaptations.

Definition 6

$\varSigma _{12}^{2D}(A_{11},A_{21},A_{22},B_{1},B_{2},C_{1},C_{2},D)$ is said to be a realization of the 2D polynomial matrix $M(d_{1},d_{2}) \in \mathbb{F}^{s\times r}[d_{1},d_{2}]$ if

$$\displaystyle{ M(d_{1},d_{2}) = \left [\begin{array}{*{10}c} C_{1} & C_{2} \end{array} \right ]\left [\begin{array}{*{10}c} I - A_{11}d_{1} & 0 \\ -A_{21}d_{2} & I - A_{22}d_{2} \end{array} \right ]^{-1}\left (\left [\begin{array}{*{10}c} B_{1} \\ 0 \end{array} \right ]d_{1} + \left [\begin{array}{*{10}c} 0\\ B_{2} \end{array} \right ]d_{2}\right )+D. }$$

As it is well known different realizations of M(d ₁, d ₂) may not have the same dimension. For the sake of efficient implementation, we are interested in studying the realizations of M(d ₁, d ₂) with minimal dimension. Such realizations are called minimal. The Roesser McMillan degree of M(d ₁, d ₂), μ _R (M), is defined as the dimension of a minimal realization of M(d ₁, d ₂).

Note that every polynomial matrix $M(d_{1},d_{2}) \in \mathbb{F}^{s\times r}[d_{1},d_{2}]$ can be factorized as follows:

$$\displaystyle{ M(d_{1},d_{2}) = M_{2}(d_{2})M_{1}(d_{1}), }$$

(5)

where $M_{2}(d_{2}) = \left [\begin{array}{*{10}c} I_{n}\mid \cdots \mid I_{n}d_{2}^{\ell_{2}} \end{array} \right ]N_{2} \in \mathbb{F}^{s\times p}[d_{ 2}]$ and $M_{1}(d_{1}) = N_{1}\left [\begin{array}{*{10}c} I_{k}&\mathop{\ldots }&I_{k}d_{1}^{\ell_{1}} \end{array} \right ]^{T} \in \mathbb{F}^{p\times r}[d_{ 1}]$, with N ₂ and N ₁ constant matrices.

If N ₂ has full column rank and N ₁ has full row rank we say that (5) is an optimal decomposition of M(d ₁, d ₂). As shown in [8, 9], if (5) is an optimal decomposition, given a minimal realization $\varSigma ^{1D}(A_{11},B_{1},\bar{C}_{1},\bar{D}_{1})$ of $M_{1}(d_{1})$ (of dimension μ(M ₁)) and a minimal realization $\varSigma ^{1D}(A_{22},\bar{B}_{2},C_{2},\bar{D}_{2})$ of $M_{2}(d_{2})$ (of dimension μ(M ₂)) then the 2D system $\varSigma _{12}^{2D}(A_{11},A_{21},A_{22},B_{1},B_{2},C_{1},C_{2},D)$, where $A_{21} =\bar{ B}_{2}\bar{C}_{1}$, $B_{2} =\bar{ B}_{2}\bar{D}_{1}$, $C_{1} =\bar{ D}_{2}\bar{C}_{1}$ and $D =\bar{ D}_{2}\bar{D}_{1}$, is a minimal realization of M(d ₁, d ₂) of dimension $\mu _{R}(M) =\mu (M_{1}) +\mu (M_{2})$. A similar reasoning can be made if we factorize $M(d_{1},d_{2}) =\bar{ M}_{1}(d_{1})\bar{M}_{2}(d_{2})$, where $\bar{M}_{1}(d_{1}) \in \mathbb{F}^{s\times \bar{p}}[d_{1}]$ and $\bar{M}_{2}(d_{2}) \in \mathbb{F}^{\bar{p}\times r}[d_{2}]$, for some $p \in \mathbb{N}$, to obtain a minimal realization $\varSigma _{21}^{2D}(A_{11},A_{12},A_{22},B_{1},B_{2},C_{1},C_{2},D)$ of M(d ₁, d ₂).

Note that, since both encoders and syndrome formers are (2D) polynomial matrices, they both can be realized by means of (4). However, when considering realizations of an encoder $G(d_{1},d_{2}) = G_{2}(d_{2})G_{1}(d_{1})$ we shall take A ₁₂ = 0 and y = w; on the other hand when considering realizations of a syndrome former $H(d_{1},d_{2}) = H_{1}(d_{1})H_{2}(d_{2})$, we shall take A ₂₁ = 0, u = w and y = 0, (cf. Remark 3).

4 Minimal Syndrome Former Realizations of a Special Class of Composition Codes

In the sequel the composition codes $\mathcal{C}$ to be considered are such that $\hat{\mathcal{C}} =\mathop{ \mathrm{im}}\nolimits G(d_{1},d_{2})$, where the encoder G(d ₁, d ₂) is as in (1) and satisfies the following properties:

(P1):

$G_{1}(d_{1})$ is a minimal 1D polynomial encoder² (for instance, prime and column reduced³), with full row rank over $\mathbb{F}$;

(P2):

$G_{2}(d_{2})$ is a quasi-systematic 1D polynomial encoder, i.e., there exists an invertible matrix $T \in \mathbb{F}^{n\times n}$ such that $TG_{2}(d_{2}) = \left [\begin{array}{*{10}c} I_{p} \\ \bar{G}_{2}(d_{2})\end{array} \right ]$, $\bar{G}_{2}(d_{2}) \in \mathbb{F}^{(n-p)\times p}[d_{2}]$.

Note that both $G_{1}(d_{1})$ and $G_{2}(d_{2})$ are minimal encoders of the corresponding 1D convolutional codes. Moreover, G(d ₁, d ₂) is a minimal encoder of $\mathcal{C}$, i.e., it has minimal Roesser McMillan degree among all encoders of $\mathcal{C}$, [9, 10], in the sequel we denote this minimal degree by $\mu (\mathcal{C})$.

In what follows, we shall derive a syndrome former construction for the code $\mathcal{C}$, based on Proposition 5. Define

$$\displaystyle{H_{1}(d_{1}) = \left [\begin{array}{*{10}c} L_{1}(d_{1})&0\\ 0 &I \end{array} \right ] \in \mathbb{F}^{(n-k)\times n}[d_{ 1}]\mbox{ and }H_{2}(d_{2}) = \left [\begin{array}{*{10}c} I &0 \\ -\bar{G}_{2}(d_{2})&I \end{array} \right ]T \in \mathbb{F}^{n\times n}[d_{ 2}],}$$

where $L_{1}(d_{1}) \in \mathbb{F}^{(p-k)\times p}[d_{1}]$ and $\left [\begin{array}{*{10}c} -\bar{G}_{2}(d_{2})&I \end{array} \right ] \in \mathbb{F}^{(n-p)\times n}[d_{2}]$ are 1D syndrome formers of the 1D convolutional codes $\mathop{\mathrm{im}}\nolimits G_{1}(d_{1})$ and $\mathop{\mathrm{im}}\nolimits G_{2}(d_{2})$, respectively. Let

$$\displaystyle\begin{array}{rcl} H(d_{1},d_{2})& =& H_{1}(d_{1})H_{2}(d_{2}){}\end{array}$$

(6)

$$\displaystyle\begin{array}{rcl} & =& \left [\begin{array}{*{10}c} L_{1}(d_{1}) &0 \\ -\bar{G}_{2}(d_{2})&I \end{array} \right ]T.{}\end{array}$$

(7)

It is easy to see that H(d ₁, d ₂) is a syndrome former of $\mathcal{C}$. It can be shown that it is possible to assume, without loss of generality, that (6) is an optimal decomposition of H(d ₁, d ₂). Then

$$\displaystyle{\mu _{R}(H) =\mu (H_{1}) +\mu (H_{2}) =\mu (L_{1}) +\mu (-\bar{G}_{2}) =\mu (L_{1}) +\mu (G_{2}).}$$

Note that since $L_{1}(d_{1})$ is a syndrome former of the 1D convolutional code $\mathop{\mathrm{im}}\nolimits G_{1}(d_{1})$ and $G_{1}(d_{1})$ is a minimal encoder of $\mathop{\mathrm{im}}\nolimits G_{1}(d_{1})$, it follows that μ(L ₁) ≥ μ(G ₁), [5, 6], and hence μ _R (H) ≥ μ _R (G). Moreover, μ(L ₁) = μ(G ₁) if $L_{1}(d_{1})$ has minimal McMillan degree among all syndrome formers of $\mathop{\mathrm{im}}\nolimits G_{1}(d_{1})$, for instance, if $L_{1}(d_{1})$ is row reduced, [5, 6], (which can always be assumed without loss of generality, since otherwise pre-multiplication of H(d ₁, d ₂) by a suitable unimodular matrix U(d ₁) yields another syndrome former for $\mathcal{C}$, with $L_{1}(d_{1})$ row reduced); in this case μ _R (H) = μ _R (G).

Thus given the encoder G(d ₁, d ₂) we have constructed a syndrome former H(d ₁, d ₂), as in Proposition 5. Moreover, based on the special properties of G(d ₁, d ₂), we have shown that the minimal realizations of H(d ₁, d ₂) have dimension $\mu _{R}(H) =\mu _{R}(G) =\mu (\mathcal{C})$ (recall that G(d ₁, d ₂) is a minimal encoder).

We next show that μ _R (H) is minimal among the McMillan degree of all syndrome formers of $\mathcal{C}$ with similar structure as H(d ₁, d ₂).

Theorem 7

Let $\mathcal{C}$ , with $\hat{\mathcal{C}} =\mathop{ \mathrm{im}}\nolimits G(d_{1},d_{2})$ , be a 2D composition code, and assume that $G(d_{1},d_{2}) = G_{2}(d_{2})G_{1}(d_{1})$ , where $G_{1}(d_{1})$ and $G_{2}(d_{2})$ satisfy properties (P1) and (P2), respectively. Let further $\tilde{H}(d_{1},d_{2}) = \left [\begin{array}{*{10}c} X_{1}(d_{1}) & 0 \\ X_{21}(d_{2})&X_{22}(d_{2}) \end{array} \right ]T$ be a syndrome former of $\mathcal{C}$ , where $X_{1}(d_{1}) \in \mathbb{F}^{(p-k)\times p}[d_{1}]$ , $X_{21}(d_{2}) \in \mathbb{F}^{(n-p)\times p}[d_{2}]$ , $X_{22}(d_{2}) \in \mathbb{F}^{(n-p)\times (n-p)}[d_{2}]$ and $T \in \mathbb{F}^{n\times n}$ as in (P2). Then $\mu _{R}(\tilde{H}) \geq \mu (\mathcal{C})$ .

Proof

Note that $\tilde{H}(d_{1},d_{2})G(d_{1},d_{2}) = 0$ if and only if

$$\displaystyle{ \left \{\begin{array}{@{}l@{\quad }l@{}} X_{1}(d_{1})G_{1}(d_{1}) = 0 \quad \\ \left (X_{21}(d_{2}) + X_{22}(d_{2})\bar{G}_{2}(d_{2})\right )G_{1}(d_{1}) = 0.\quad \end{array} \right. }$$

(8)

Then $X_{1}(d_{1})$ must be a syndrome former of the 1D convolutional code $\mathop{\mathrm{im}}\nolimits G_{1}(d_{1})$ and consequently $\mu (X_{1}) \geq \mu (G_{1})$ [6]. On the other hand we have that $X_{21}(d_{2}) + X_{22}(d_{2})\bar{G}_{2}(d_{2}) = 0$, that is equivalent to $\left [\begin{array}{*{10}c} X_{21}(d_{2})&X_{22}(d_{2}) \end{array} \right ]\left [\begin{array}{*{10}c} I\\ \bar{G}_{2 } (d_{2}) \end{array} \right ] = 0$, and therefore $\left [\begin{array}{*{10}c} X_{21}(d_{2})&X_{22}(d_{2}) \end{array} \right ]$ is a syndrome former of the 1D convolutional code $\left [\begin{array}{*{10}c} I\\ \bar{G}_{2 } (d_{2}) \end{array} \right ]$. Hence $\mu \left (\left [\begin{array}{*{10}c} X_{21} & X_{22} \end{array} \right ]\right ) \geq \mu \left (\left [\begin{array}{*{10}c} I\\ \bar{G}_{2} \end{array} \right ]\right )$, since $\left [\begin{array}{*{10}c} I\\ \bar{G}_{2 } (d_{2}) \end{array} \right ]$ is a minimal en- coder of $\mathop{\mathrm{im}}\nolimits \left [\begin{array}{*{10}c} I\\ \bar{G}_{2 } (d_{2}) \end{array} \right ]$. Now, since $\tilde{H}(d_{1},d_{2}) = \left [\begin{array}{*{10}c} X_{1}(d_{1})&0\\ 0 &I \end{array} \right ]\left [\begin{array}{*{10}c} I & 0\\ X_{21 } (d_{2 } ) &X_{22 } (d_{2}) \end{array} \right ]T$, it is not difficult to see that

$$\displaystyle\begin{array}{rcl} \mu _{R}(\tilde{H}) =\mu (X_{1}) +\mu \left (\left [\begin{array}{*{10}c} X_{21} & X_{22} \end{array} \right ]\right )& \geq & \mu (G_{1}) +\mu \left (\left [\begin{array}{*{10}c} I\\ \bar{G}_{2} \end{array} \right ]\right ) {}\\ & =& \mu (G_{1}) +\mu \left (T^{-1}\left [\begin{array}{*{10}c} I \\ \bar{G}_{2} \end{array} \right ]\right ) =\mu _{R}(G) =\mu (\mathcal{C}).{}\\ \end{array}$$

 □ 

Corollary 8

Using the notation and conditions of Theorem  7, the syndrome former of $\mathcal{C}$ given by (7) has minimal Roesser McMillan degree among all syndrome formers of the same structure.