Weight-2 input sequences of $1/n$ convolutional codes from linear systems point of view

1.   Introduction

In this work we are interested in investigating codewords of $1/n$ convolutional codes that are produced by weight-2 information sequences. These codewords play an important role in the computation of the effective free distance in the context of Turbo codes (see ^[14]) and therefore a better understanding of this particular set of codewords may lead to improvements in the construction of Turbo codes. In this work we focus on the mathematical analysis of these set rather than on possible direct consequences in the performance of Turbo codes. We perform this mathematical investigation within the so-called input state output representations.

Convolutional codes can be modelled by means of input state output representations in the framework of linear time-invariant systems (see ^{[3,5,6,8,16,27,30]} for an introduction of the basic theory of this approach). The main advantage of this approach is that the dynamics of the state (memory) of the system (convolutional code) are explicit in this representation. Moreover this enables the application of the huge and powerful machine of systems theory problems in the context of coding theory.

In ^[14] Divsalar and McEliece studied codewords of convolutional codes that are produced by weight-2 information sequences, derived some theoretical bounds for the effective free distance and posed a conjecture. In this paper, we also make use of a state-space representations but choose representations as introduced in ^[30] which are slightly different to the driven variable representations used in ^[14]. These representations led to several important theoretical and practical results of convolutional codes (see ^{[7,8,10,18,21,25,26]}) and we continue the study in ^[19] using the $(A, B, C, D)$ input state output representation of finite-weight convolutional codes. In ^[19], an upper bound on the effective free distance distance was provided for the particular case in which the matrix $A$ in the input state output representation is an invertible matrix. In this paper we consider the case in which the matrix $A$ is singular. Thus, this work can be considered as an extension of previous results. When the matrix $A$, that represents the update of the state of the system, is nonsingular, the last input entering into the system must immediately steer the state vector to the zero vector in order to obtain a finite-weight codeword. However, when $A$ is singular, this is not necessarily true, and the state vector might remain nonzero some time after the last input has been introduced into the system. For this reason the extension of the results in ^[19] to the general case is not straightforward as we show in this work. Nevertheless, we present new characterizations of this set of codewords and provide an upper-bound on the effective free distance. As we show in the this paper, the analysis of these systems (with $A$ singular) turned out to be highly nontrival and so the optimally of the upper-bound could not be formally proven.

The paper is organized as follows: In Section 2 we briefly introduce finite-weight convolutional codes defined over any Galois field and a particular input-state-output representation of such codes. We also recall the relevance of codewords generated by weight-2 inputs and their relation to turbo codes. Section 3 is devoted to provide the main results of the paper. In particular, for a given convolutional code $\mathcal{C}$ of dimension one defined over any finite field with an input-state-output representation given by $(A, B, C, D)$ and $A$ a singular matrix, we analyse the dynamics that can occur between the input and the state of the system in this case. We present a conjecture and a novel upper bound on $\operatorname{z_{min}}(\mathcal{C})$ based on this conjecture and, in turn, an upper bound on the effective free distance of $\mathcal{C}$. Finally, we present and study a concrete construction of a class of convolutional codes for which we can compute $\operatorname{z_{min}}(\mathcal{C})$ up to a difference of one value and provide an example to illustrate the results. We conclude the paper by presenting some conclusion and possible future work within this thread of research.

2.   Basic definitions and properties of Turbo codes and linear systems

In this paper, we denote by ${{\mathbb{F}}} = GF(q)$ the Galois field of $q$ elements and ${{\mathbb{F}}}[z]$ the polynomial ring on the variable $z$ with coefficients in ${{\mathbb{F}}}$.

Consider the matrices $A\in{{\mathbb{F}}}^{\delta\times\delta}$, $B\in{{\mathbb{F}}}^{\delta\times k}$, $C\in{{\mathbb{F}}}^{(n-k)\times \delta}$ and $D\in{{\mathbb{F}}}^{(n-k)\times k}$. Following ^[30] and ^[28], a rate $k/n$ convolutional code $\mathcal{C}$ of complexity $\delta$ can be described by the linear system governed by the equations

where for each time instant $t$, $\vec{x}_{t} \in {{\mathbb{F}}}^{\delta}$ is the state vector, $\vec{u}_{t} \in {{\mathbb{F}}}^{k}$ is the input (also call information vector) and $\vec{y}_{t} \in {{\mathbb{F}}}^{n-k}$ is the parity vector. In linear systems theory, this representation is known as the input-state-output representation. This representation was introduced by Rosenthal, York and Schumacher (see ^[28]) and it has been widely used in the last years to analyze and construct convolutional codes ^[8,9,29,30]. In terms of Linear Systems, the complexity $\delta$, is the McMillan degree of the linear system (2.2). In the following, we adopt the notation used by McEliece ^[24] and we call a convolutional code of rate $k/n$ and complexity $\delta$ an $(n, k, \delta)$-code.

Note that the description given by expression (2.2) is in general not unique. But if $\mathcal{C}$ has complexity $\delta$, then it is possible to choose the matrices $A$, $B$, $C$, and $D$ of sizes $\delta \times \delta$, $\delta \times k$, $(n-k) \times \delta$ and $(n-k) \times k$, respectively. In convolutional coding theory, an input-state-output representation $(A, B, C, D)$, having the above sizes, is called a minimal representation and it is characterized through the condition that the pair $(A, B)$ is controllable, that is (see ^[29]), the controllability matrix has full rank, $\operatorname{rank} \Phi_{\delta}(A, B) = \delta$, where

The controllablility matrix is a well-known matrix in the area of system theory as it allows to characterized the controlability of the linear system. If $(A, B)$ is a controllable pair, then we call the smallest integer $\kappa$ having the property that $\operatorname{rank} \Phi_{\kappa}(A, B) = \delta$ the controllability index of $(A, B)$. On the other hand, we say that $(A, C)$ is an observable pair if $(A^{T}, C^{T})$ is a controllable pair (see ^[29]). If the pair $(A, B)$ is controllable, it means that, by an appropriate choice of input vectors, it is possible to drive a given state vector to any other state vector in finite time. Analogously, the observability of the pair $(A, C)$ means that it is possible to determine the state vector at a given time $t_{0}$ by observing the output vectors for a finite number of time steps beginning with $t_{0}$ (see, for example, ^[28,30]).

Following the approach adopted in ^[29] we only consider $\{\vec{v}_{t}\}_{t\geq 0}$ in Eq (2.2) to be a finite-weight codeword (see ^[29] for more details of the algebraic reasons to do so), that is, Equation (2.2) holds for all $t = 0, 1, 2, \ldots$ and there is an integer $\gamma$ such that $\vec{x}_{\gamma+1} = 0$, $\vec{u}_{t} = 0$, for $t\ge \gamma+1$, and therefore, $\vec{y}_{t} = 0$ for $t \ge \gamma+1$, so the code sequence has finite weight. In this work we denote such a finite-weight codeword by $\mathcal{V}_{\gamma}$.

Hence, it follows that both the input and the state sequence (and hence the output) must to have finite support in a finite-weight codeword. The set of finite-weight codewords has a module structure over the polynomial ring ${{\mathbb{F}}}[z]$ (see ^[29]). By abuse of notation, we will denote this module by $\mathcal{C}(A, B, C, D)$ and we refer to it as the finite-weight convolutional code generated by the matrices $A$, $B$, $C$, $D$. Proposition 2.4 of ^[29] gives us a characterization of finite-weight codewords. Let us denote by $\mathcal{V}_{\gamma}$ a finite-weight codeword sequence constituted by $\begin{pmatrix} \vec{y}_{0}\\ \vec{u}_{0} \end{pmatrix}, \begin{pmatrix} \vec{y}_{1}\\ \vec{u}_{1} \end{pmatrix}, \dots, \begin{pmatrix} \vec{y}_{\gamma}\\ \vec{u}_{\gamma} \end{pmatrix} \in \mathbb{F}^n$ represents with $\begin{pmatrix} \vec{y}_{0}\\ \vec{u}_{0} \end{pmatrix}$ and $\begin{pmatrix} \vec{y}_{\gamma}\\ \vec{u}_{\gamma} \end{pmatrix} \neq 0$. Hence, the Eqs of (2.2) are satisfied for all $t\geq 0$ and

Remark 2.1. Notice that it is easy to check that if $S$ is an invertible matrix, then it holds that

The representation considered here, i.e., (2.2), is indeed the description of the dynamics of a rational and systematic encoder, since by Lemma 2.14 of ^[29], if $\mathcal{C}(A, B, C, D)$ is an $(n, k, \delta)$-code, then, the matrices $A$, $B$, $C$ and $D$ describe a proper rational transfer function of $\mathcal{C}(A, B, C, D)$, given by

Furthermore, $G(z) = \begin{pmatrix} T(z)\\ I_{k} \end{pmatrix}$ is a systematic encoder of $\mathcal{C}(A, B, C, D)$.

Remark 2.2. We note that the state-space realizations considered in this work are different from the driving variable realizations often found in the coding literature ^[15,23], given by

where $\vec{u}_{t}\in{{\mathbb{F}}}^{k}$ is the information vector, $\vec{v}_{t}\in{{\mathbb{F}}}^{n}$ the codewords that are, in this case, the outputs of the linear system and $\vec{x}_{t}\in{{\mathbb{F}}}^{\delta}$ as above. Although driving-variable representations have been considered the standard way in which convolutional codes were presented in terms of linear systems, many authors have considered linear systems as described in (2.1) and (2.2) in the last decades as they have many advantages when analyzing convolutional codes ^[28,29,33]. One of these advantages is that in the driving variable representations, the matrix $\mathcal A$ has to be nilpotent whereas in the one described in (2.1) and (2.2) the matrix $A$ does not have such a restriction. This fact facilitates the construction of optimal input state output representations of convolutional codes (see ^[29,32,33]). Another advantage of the setting considered in this paper is that these representations are particularly suitable not only for constructing convolutional codes but also for dealing with finite-weight codewords, see ^[29,30] for more details. These properties allow us to derive new results regarding lowest weight of the parity vectors of the convolutional code $\mathcal C$ generated by information sequences of weight two.

Block codes having optimal error correcting capabilities, i.e., with maximum minimum, are quite well-understood, e.g. the class of Reed-Solomon codes ^[20,34]. However, in order to derive codes with efficient performance, i.e., codes coming closest to the Shannon limit, having large minimum distance it is same times not enough. To achieve optimal performance parallel concatenation of convolutional codes, known as Turbo Codes, were presented by Glavieux and Thitimajshima, see ^[2]. In a turbo code $\mathcal{TC}$ two convolutional codes, $\mathcal{C}_1$ and $\mathcal{C}_2$ of rates $k/n_1$ and $k/n_2$, respectively, are connected via an inter-leaver in such a way that the first encoder, $\mathcal{C}_1$, operates directly on the input information $\vec{u}_{t}$ ($t = 0, 1, 2, \ldots$) and the second one, $\mathcal{C}_2$, encodes the interleaved input information, denoted by $P\vec{u}_{t}$ ($t = 0, 1, 2, \ldots$), where $P$ is a permutation matrix of order $k$. Therefore, a codeword of these code in divided in the parity vectors of both encoders followed by the information vector. In ^[4] the input-state-output representation for the turbo code $\mathcal{TC}$ was introduced from the state representation of the constituent encoders. For more results on these concatenated (convolutional) codes within a linear systems approach the reader is reffered to ^[8], ^[9], ^[11], ^[15] and ^[17].

The most important parameter through which the constituent convolutional codes influence the turbo code performance is $\operatorname{z_{min}}(\mathcal{C})$ (see ^[1], ^[12], ^[13] and ^[14]), which it is defined below.

Definition 2.1. Let $\mathcal{C}$ be a convolutional code. We define $\operatorname{z_{min}}(\mathcal{C})$ as the lowest weight of the parity vectors of the convolutional code $\mathcal{C}$ generated by information sequences of weight two.

In ^[1] and ^[14] it was shown that the performance of turbo codes is primarily driven by the weight-2 input minimum distance, which is directly related to the minimum weight among the set of codeword sequences generated by input sequences of weight two. Hence, if one considers a $\mathcal{TC}$ with $\mathcal{C}_1 = \mathcal{C}_2 = \mathcal{C}$, its weight-2 input minimum distance, which is also referred to as the effective free distance of $\mathcal{TC}$ ^[1], $\operatorname{d_{free, eff}}(\mathcal{TC})$, is described as

3.   Upper bounds on the effective free distance of $1/n$ turbo codes

On a AWGN cannel, code performance is determined largely by the effective free distance. In this section, we get bounds on this distance. Moreover, the design objective for the constituent recursive convolutional encoders of a turbo code is to obtain $\operatorname{z_{min}}$ as large as possible. In ^[1] it was shown that in the binary case there exists a rate $1/n$ recursive systematic convolutional code $\mathcal{C}$ with complexity $\delta$ that achieve the maximum value of $\operatorname{z_{min}}(\mathcal{C})$, described by

Consequently, for a turbo code $\mathcal{TC}$ with two equal systematic convolutional codes, they obtain the following upper bound on the effective free distance of $\mathcal{TC}$

Recently, in ^[19] turbo codes were again studied within a linear systems point of view, over finite field. In particular, they consider a turbo code obtained by the concatenation of two identical $1/n$ recursive systematic convolutional codes $\mathcal{C}$ given by its input-state-output representation $(A, B, C, D)$ where the matrix $A$ is invertible. They studied how to obtain the value of $\operatorname{z_{min}}(\mathcal{C})$, and derived an upper bound that we present next. First, we need to introduce the following definition, which refers to the minimum time instant at which the last nonzero input is introduced into the system.

As at each time instant the input belongs to the field, in the case the rate is $1/n$, we use the typography $u_t$ rather than $\vec{u}_t$, to distinguish between scalars and vectors.

Definition 3.1. We define $\hat{s}$ to be the least $s$ for which there exists a finite-weight codeword $\mathcal{V}_{\gamma}$ of a convolutional code $\mathcal{C}$ generated by a vector $(u_{0}, u_{1}, \ldots, u_{s}, u_{s+1}, \ldots, u_{\gamma})$ with weight equal to two and $u_{0}$, $u_{s}\neq 0$. Such an $\hat{s}$ is called the minimum effective index of $\mathcal{C}$.

In ^[19] an upper bound on the value of $\operatorname{z_{min}}(\mathcal{C})$ among all convolutional codes with equal set of parameters $(n, 1, \delta)$ was introduced, as we show in the following theorem.

Theorem 3.1. [Corollary 1 of ^[19]] Let $\mathcal{C}(A, B, C, D)$ be an $(n, 1, \delta)$-code, in such a way that the pair $(A, B)$ is controllable and $A$ is an invertible matrix. Let $\hat{s}$ be the minimum effective index of $\mathcal{C}$. Then,

and, in turn, the effective free distance of $\mathcal{TC}$ satisfies

The authors of ^[19] give conditions for an $(n, 1, \delta)$-code to achieve such a bound and they moreover present a concrete construction of an $1/n$ recursive systematic convolutional code $\mathcal{C}$ whose $\operatorname{z_{min}}(\mathcal{C})$ is as maximum as possible for these parameters.

Remark 3.1. If we consider that case in which the matrix $A$ is nonsingular, we get $\operatorname{z_{min}}(\mathcal{C})$ over the parity vectors of finite-weight codewords $\mathcal{V}_{\gamma}$ generated by input vectors $(u_{0}, u_{1}, \ldots, u_{s})$ of weight two with $u_{0}$, $u_{s}\neq 0$, with $\gamma = s$, since at time instant $s$ the state of the system must go to zero. Thus, the last input $u_s$ entering into the system has to yield $x_{s+1} = 0$. More concretely, let $\mathcal{V}_{\gamma}$ be a finite-weight codeword generated by an information vector $(u_{0}, u_{1}, \ldots, u_{s}, u_{s+1}, \ldots, u_{\gamma})$ of weight two with $u_{0}$, $u_{s}\neq 0$. Then,

implies

since $A$ is nonsingular. In other words, if $A$ is nonsingular, it follows that the minimum effective index $\hat{s}$ of $\mathcal{C}$ is obtained by the minimum of the integers $s$ that satisfy the conditions indicated at the beginning of the remark. Moreover, Theorem 1 of ^[19] indicates that $\operatorname{z_{min}}(\mathcal{C})$ is derived only by the weight of the parity vectors of any finite-weight codeword $\mathcal{V}_{\hat{s}}$ of the convolutional code produced by sequences with length $\hat{s}+1\geq\delta +1$ where the two nonzero inputs are the first and the last ones.

When the matrix $A$ is singular we may have that

but relation (3.1) holds. This intuitively means that the state of the system $(A, B, C, D)$ does not necessarily vanish at instant $s$ and could remains nonzero for some time after the second (that is, the last) input $u_{s}\neq 0$ enters into the system. Moreover, let $\mathcal{V}_{\gamma}$ and $\mathcal{\tilde{V}}_{\tilde{\gamma}}$ be two finite-weight codewords with input vectors $(u_{0}, u_{1}, \ldots, u_{s}, u_{s+1}\ldots, u_{\gamma})$ and $(\tilde{u}_{0}, \tilde{u}_{1}, \ldots, \tilde{u}_{\tilde{s}}, \tilde{u}_{\tilde{s}+1}\ldots, \tilde{u}_{\tilde{\gamma}})$ of weight two with $u_{0}$, $u_{s}$, $\tilde{u}_{0}$, $\tilde{u}_{\tilde{s}}\neq 0$ and such that $\tilde{s} > s$. As opposed to the case in which $A$ is nonsingular, in this case we cannot ensure that

that is, the minimum effective index $\hat{s}$ given in Definition 3.1 is not directly related to $\operatorname{z_{min}}(\mathcal{C})$ is in the case where the matrix $A$ is singular. Therefore, the ideas used to show Theorem 3.1 for $A$ nonsingular cannot be straightforward applied in this case and we need to use a different approach.

3.1.   $\operatorname{z_{min}}$ of a rate $1/n$ recursive systematic convolutional code $\mathcal{C}(A, B, C, D)$ with $A$ singular.

Next, we investigate the set of finite-weight codewords generated by input vectors of weight two which give us the value of $\operatorname{z_{min}}$ when an $(n, 1, \delta)$-code $\mathcal{C}$ is given by an input-state-output representation $(A, B, C, D)$ such that the matrix $A$ that updates the state vector of the system is singular. As noted in Remark 3.1 the length $\gamma+1$ of the finite-weight codeword $\mathcal{V}_{\gamma}$ can be much larger than the minimum time instant of the last nonzero input, denoted by $s$. Note that in these $\gamma - s$ instants, the corresponding input is zero but the state is nonzero and continues to generates outputs vectors $y_i = C x_i$, $i = s+1, \dots, \gamma$. This makes it difficult to obtain an upper bound on $\operatorname{z_{min}}$ in terms of the minimum effective index. Nevertheless, we can delimit the inputs that will generate the finite-weight codewords where $\operatorname{z_{min}}$ will be reached, as we will see at the end of this section.

Now suppose that $\mathcal{C}(A, B, C, D)$ is a rate $1/n$ convolutional code with complexity $\delta$. Then, the matrices $(A, B)$ form a controllable pair, so

where $\kappa$ is the so-called controllability index of $(A, B)$. Also, in the case that $\mathcal{C}(A, B, C, D)$ is an $(n, 1, \delta)$-code with $(A, B)$ controllable, it follows that the controllability index $\kappa$ is equal to the complexity $\delta$, $\kappa = \delta$.

Now, let $\mathcal{V}_{\gamma}$ be a finite-weight codeword with $u_{0}\neq 0$. Then, relations (2.3) and (3.2), imply necessarily $\gamma > \kappa-1$ and therefore, we get the following result.

Lemma 3.1. Let $\mathcal{C}(A, B, C, D)$, with $(A, B)$ controllable, be an $(n, 1, \delta)$-code. It holds that the length $\gamma +1$ of a finite-weight codeword with input weight $2$ satisfies that $\gamma\geq \delta$.

Among all the parity vectors of finite-weight codewords generated by input vectors of weight two we can restrict ourselves to a smaller set in order to compute $\operatorname{z_{min}}(\mathcal{C})$, as stated in the following lemma.

Lemma 3.2. Let $\mathcal{C}(A, B, C, D)$ be an $(n, 1, \delta)$-code with the pair $(A, B)$ controllable. Let $\mathcal{V}_{\gamma}$ be a finite-weight codeword generated by the input vector $(u_{0}, u_{1}, \ldots, u_{s}, u_{s+1}\ldots, u_{\gamma})$ of weight two with $u_{0}$, $u_{s}\neq 0$. Then, the codeword $\mathcal{V}_{\gamma+m}$ generated by the input vector $(u_{0}, u_{1}, \ldots, u_{s}, u_{s+1}\ldots, u_{\gamma}, u_{\gamma+1}, \ldots, u_{\gamma+m})$ of weight two with $u_{0}$, $u_{s}\neq 0$ is a finite-weight codeword for all $m\in\mathbb{N}$. Moreover,

Proof. Since $\mathcal{V}_{\gamma}$ is a finite-weight codeword, taking into account relation (2.3), we know that $A^{\gamma}u_{0}+A^{\gamma-s}u_{s} = 0$. In particular, $A^{m}(A^{\gamma}u_{0}+A^{\gamma-s}u_{s}) = A^{\gamma+m}u_{0}+A^{\gamma+m-s}u_{s} = 0$, so $\mathcal{V}_{\gamma+m}$ is a finite-weight codeword. Now, observe that the components of the parity vector $(\vec{y}_{0}, \vec{y}_{1}, \ldots, \vec{y}_{s})$ of $\mathcal{V}_{\gamma}$ are given by the following relations

and the components of the parity vector $(\vec{\tilde{y}}_{0}, \vec{\tilde{y}}_{1}, \ldots, \vec{\tilde{y}}_{s}, \vec{y}_{s+1}, \ldots, \vec{\tilde{y}}_{\gamma}, \ldots, \vec{\tilde{y}}_{\gamma+m})$ of $\mathcal{V}_{\gamma+m}$ are in fact

So,

Assume now that $\mathcal{C}(A, B, C, D)$ is a rate $1/n$ convolutional code with $A$ singular. It is well-known that if $(A, B)$ is a controllable pair, we can assume without loss of generality (see Remark 2.1) that

(the so-called controllable canonical realization ^[22]). If $A$ is a singular matrix, then there exists an integer $\tau\geq 1$ such that $p_{\delta-j} = 0$ for $j = 1, 2, \ldots, \tau$ and $p_{\delta-\tau-1}\neq 0$.

In the remain of this section, we work with the controllable canonical form of $(A, B)$ with $A$ singular. Let $\mathcal{V}_{\gamma}$ be a finite-weight codeword generated by an information vector $(u_{0}, u_{1}, \ldots, u_{s}, u_{s+1}, \ldots, u_{\gamma})$ of weight two, with only $u_{0}, u_{s}\neq 0$. From (2.3) we have that

that is,

So we focus our attention in the kernel of the matrix $A^{\eta}$, for $\eta\geq 1$.

The following result provide us with the structure of the $\eta$-th power of the matrix $A$, that we will need later on. Throughout all the paper, we denote by $O_{\alpha\times\beta}$ the $\alpha\times\beta$ zero matrix and by $I_{m}$ the identity matrix of size $m$.

Lemma 3.3. Let $(A, B, C, D)$ be the controllable canonical realization of an $(n, 1, \delta)$ convolutional code $\mathcal{C}$, that is, $A$ and $B$ are matrices as in (3.3). Assume that $A$ is singular and let $\tau$ be the integer such that $p_{\delta-j} = 0$ for $j = 1, 2, \ldots, \tau$ and $p_{\delta-\tau-1}\neq 0$. Denote by $A^{\eta}$ the $\eta$-th power of $A$ for $\eta\geq 1$ and by $a(\eta)_{ij}$ the element of $A^{\eta}$ corresponding to the row $i$ and the column $j$. Then:

1. If $\eta\leq\delta-1$, then

where $A(\eta)_{12} = I_{(\delta-\eta)}$ and $A(\eta)_{21}$ and $A(\eta)_{22}$ are matrices of sizes $\eta\times\eta$, and $\eta\times(\delta-\eta)$, respectively. Furthermore, the matrix $A(\eta)_{21}$ is a square matrix such that

● If $\eta\leq \tau$, then $A(\eta)_{21} = O_{(\delta-\eta)\times (\delta-\eta)}$

● If $\eta > \tau$, then the elements $(a(\eta)_{ij})_{ \begin{array}{l} i = \delta-\eta+1, \ldots, \delta\\ j = 1, \ldots, \delta \end{array} }$ are given by

and the elements $(a(\eta)_{ij})_{ \begin{array}{l} i = \delta-\eta+1, \ldots, \delta\\ j = \eta+1, \ldots, \delta \end{array} }$ of the matrix $A(\eta)_{22}$ are given by

● If $\eta\leq\tau$, then

● If $\eta > \tau$, then

2. If $\eta\geq\delta$, then

where $A(\eta)_{12}$ and $A(\eta)_{22}$ are matrices of sizes $(\delta-1)\times (\delta-\tau)$ and $1\times (\delta-\tau)$, whose elements are given by

● For the matrix $A(\eta)_{12}$, $a(\eta)_{ij} = a(\eta-1)_{i+1, j}$, for $i = 1, \ldots, \delta-1$ and $j = \tau+1\ldots, \delta$.

● For the matrix $A(\eta)_{22}$,

Proof. We can consider that the $\eta$-th power of $A$ can be expressed in matrix blocks as follows:

where $A(\eta)_{11}$, $A(\eta)_{12}$, $A(\eta)_{21}$ and $A(\eta)_{22}$ are matrices of sizes $(\delta-\eta)\times \eta$, $(\delta-\eta)\times(\delta-\eta)$, $\eta\times\eta$, and $\eta\times(\delta-\eta)$, respectively.

We will make the proof using the induction method on the power $\eta$ of $A$.

By computation, we get that

where the matrix $A(2)_{21}$ is of size $2\times 2$ such that

● If $\tau = 1$, then

● If $\tau\geq 2$, then $A(2)_{21} = O_{2\times 2}$.

On the other hand, the matrix $A(2)_{22}$ is a matrix of size $2\times (\delta-2)$ given by

● If $\tau = 1$, then

● If $\tau\geq 1$, then

Now, assume that $A^{\eta} = (a(\eta)_{ij})_{ \begin{array}{l} i = 1, \ldots, \delta\\ j = 1, \ldots, \delta \end{array} }$ is given by the statement of the lemma.

If $\eta < \delta$, then,

where the matrices $A(\eta+1)_{21}$ and $A(\eta+1)_{22}$ are of sizes $(\eta+1)\times (\eta+1)$ and $(\eta +1)\times (\delta-\eta-1)$, respectively, whose elements are given by

● For the matrix $A(\eta+1)_{21}$:

- If $\eta+1\leq \tau$, then $a(\eta+1)_{ij} = 0$ for all $i = \delta-\eta, \ldots, \delta$ and $j = 1, \ldots, \eta+1$,

- If $\eta+1 > \tau$, then

● For the matrix $A(\eta+1)_{22}$:

- If $\eta+1\leq\tau$, then

- If $\eta+1 > \tau$, then

Assume now that $\eta\geq\delta$ and that matrix $A^{\eta}$ is given by relation (3.5). Observe that the matrix $A$ contains the identity matrix of size $(\delta-1)\times (\delta-1)$ (see (3.3)) and the last row of it is

In particular, $A = \begin{pmatrix} O_{(\delta-1)\times 1} & I_{\delta-1}\\ 0 & A(1)_{22} \end{pmatrix}$. For the above reasoning, we can consider that $A^{\eta}$ has the following structure

Consequently,

where the matrices $A(\eta+1)_{12}$ and $A(\eta+1)_{22}$ are of sizes $(\delta-1)\times (\delta-\tau)$ and $1\times (\delta-\tau)$, respectively, satisfying

● $A(\eta+1)_{12} = A(\eta)_{22}$

● $A(\eta+1)_{22} = (a(\eta+1)_{\delta, j})_{ j = \tau+1, \ldots, \delta }$ with

So we have proof by the induction method that the $\eta$-th power of $A$ is given by the statement of the lemma.

Now, let $\mathcal{V}_{\gamma}$ be a finite-weight codeword generated by the input vector $(u_{0}, u_{1}, \ldots, u_{s}, u_{s+1}\ldots, u_{\gamma})$ of weight two with $u_{0}$, $u_{s}\neq 0$. From relation (3.4) we know that $A^{s}Bu_{0}+Bu_{s}\in\ker (A^{\gamma-s})$. Next result give us the dimension of the kernel of the the $\eta$-th power of $A$. Such a kernel we will need later on.

Lemma 3.4. Let $(A, B, C, D)$ be the the controllable canonical realization of an $(n, 1, \delta)$ convolutional code $\mathcal{C}$, that is, $A$ and $B$ are matrices as in (3.3). Assume that $A$ is singular and let $\tau$ be the integer such that $p_{\delta-j} = 0$ for $j = 1, 2, \ldots, \tau$ and $p_{\delta-\tau-1}\neq 0$. Denote by $a^{(\eta)}_{j}$ the j-th column of the matrix $A^{\eta}$, for each $\eta\geq 1$, that is,

Then, the following holds:

a) If $1\leq \eta \leq \tau-1$, then $a^{(\eta)}_{j} = 0$ for $j = 1, 2, \ldots, \eta$ and the column vectors $\{a^{(\eta)}_{\eta+1}, \ldots, a^{(\eta)}_{\tau}, \ldots, a^{(\eta)}_{\delta}\}$ are linearly independent. In particular, $\mathit{\text{dim}}(\ker A^{\eta}) = \eta$.

b) If $\tau \leq\eta\leq \delta-1$, then $a^{(\eta)}_{j} = 0$ for $j = 1, 2, \ldots, \tau$ and the column vectors $\{a^{(\eta)}_{\tau+1}, \ldots, a^{(\eta)}_{\delta}\}$ are linearly independent. In particular, $\mathit{\text{dim}}(\ker A^{\eta}) = \tau$.

c) If $\eta\geq \delta$, then $a^{(\eta)}_{j} = 0$ for $j = 1, 2, \ldots, \tau$ and $\mathit{\text{dim}}(\ker A^{\eta})\geq\tau$.

Proof. Taking into account Lemma 3.3, which give us the structure of $A^{\eta}$, we obtain that

a) If $\eta = 1, 2, \ldots, \tau-1$, then the first $\eta$ columns of $A^{\eta}$ are zero and the column vectors $\{a^{(\eta)}_{\eta+1}, \ldots, a^{(\eta)}_{\tau}, \ldots, a^{(\eta)}_{\delta}\}$ are linearly independent, since they contains the identity matrix of size $\delta-\eta$. Consequently, $\text{dim}(\ker A^{\eta}) = \eta$.

b) If $\tau\leq\eta\leq \delta$, then the first $\tau$ columns of $A^{\eta}$ are zero and the column vectors $\{a^{(\eta)}_{\tau+1}, \ldots, a^{(\eta)}_{\delta}\}$ are linearly independent, since they contains the identity matrix of size $\delta-\tau$. So $\text{dim}(\ker A^{\eta}) = \tau$.

c) If $\eta\geq\delta$, then the first $\tau$ columns of $A^{\eta}$ are zero but we cannot know which columns of the $\delta-\tau$ last columns of $A^{\eta}$ are linearly independent. In particular, $\text{dim}(\ker A^{\eta})\geq\tau$.

Remark 3.2. Observe that if $\eta\geq\tau$, the dimension, and in particular, a basis of the subspace $\ker (A^{\eta})$, is independent of $\eta$.

Remark 3.3. Lemma 3.3 also shows the relation of recurrence existing between the last column of the different powers of the matrix A. Indeed, if $C(A, B, C, D)$ is an $(n, 1, \delta)$-code with the conditions of Lemma 3.3, and we write $a^{(\eta)}_{\delta} = \begin{pmatrix} a(\eta)_{1, \delta}\\ a(\eta)_{2, \delta}\\ \vdots\\ a(\eta)_{\delta-1, \delta}\\ a(\eta)_{\delta, \delta} \end{pmatrix}$ for the last column of $A^{\eta}$, $\eta = 2, 3, \ldots$.Then:

and

Next we investigate how are the codewords that need to be considered to compute $\operatorname{z_{min}}(\mathcal{C})$. We shall analyse several sets of finite-weight codewords $\mathcal{V}_{\gamma}$ sorted by their length $\gamma$ in order to restrict the set of possible codewords that we need to considered to find the minimum of the weight of its parity vectors that yield $\operatorname{z_{min}}(\mathcal{C})$. This, of course, will optimize the computations required to compute the exact value of $\operatorname{z_{min}}(\mathcal{C})$.

Theorem 3.2. Let $\mathcal{C}(A, B, C, D)$ be an $(n, 1, \delta)$-code with $(A, B)$ in canonical controllable form and $A$ singular. Let $\tau$ be the integer as in Lemma 3.3. Let $\mathcal{V}_{\gamma}$ be the set of finite-weight codewords of $\mathcal{C}$ generated by an information vector $(u_{0}, u_{1}, \ldots, u_{s}, u_{s+1}, \ldots, u_{\gamma})$ with $u_{0}, u_{s}\neq 0$ and $u_{i} = 0$ for $i\notin \{ 0, s\}$. Then, the lowest weight of the parity vectors of $\mathcal{V}_{\gamma}$ with $s+\tau\leq\gamma \leq s + \delta-1$ is achieved for $s\leq q^{\delta}-(q^{\tau}(q-1))$.

Proof. Let $\mathcal{V}_{\gamma}$ be a finite-weight codeword of $\mathcal{C}$ generated by an information vector $(u_{0}, u_{1}, \ldots, u_{s}, \ldots, u_{\gamma})$ of weight two with $u_{0}$, $u_{s}\neq 0$. Then,

so $\begin{pmatrix} A^{s}B u_{0}+Bu_{s} \end{pmatrix}\in\ker A^{\gamma-s}$. It follows from Remark 3.2 that $\ker A^{\gamma-s}$ is the same subspace for any $\gamma$ and $s$, provided $\tau\leq\gamma-s\leq \delta-1$. As we consider the case in which $s+\tau\leq\gamma \leq s + \delta-1$ it follows from statement b) of Lemma 3.4 that $\text{dim} (\ker A^{\gamma-s}) = \tau$ and a basis for $\ker A^{\gamma-s}\subseteq {{\mathbb{F}}}^{\delta\times 1}$ is given by the column vectors:

where $e_{i}$ denotes the $i$-th vector of the canonical basis of ${{\mathbb{F}}}^{\delta\times 1}$, for $i = 1, 2, \ldots, \tau$. Therefore, one has that $A^{s}Bu_{0}+Bu_{\hat{s}}$ must be of the form $(d_{1}, d_{2}, \ldots, d_{\tau}, 0, \ldots, 0)^{T}$ or, equivalently (observe the structure of matrix $B$ given by (3.3)),

Hence, $s$ is in fact the smallest integer such that the last column of $A^{s}$ is a vector like

Remark 3.3 provides the structure of the elements of the last column of $A^{s}$, that it can be seen as a feedback polynomial of a Linear Feedback Shift Register (LFSR). The maximum cycle of a LFSR of length $\delta$ is $q^{\delta}$ if the associated polynomial is primitive.

The number of states of the form (3.6) is $q^{\text{dim}(\ker A^{\gamma-s})} = q^{\tau}$ times the $(q-1)$ possible nonzero elements for the last row of $A^{s}B$. This leads to the following upper-bound on $s$:

which concludes the proof.

In the following result we study the set of codewords with length $\gamma+1$ such that $\gamma < s + \tau$.

Theorem 3.3. Let $\mathcal{C}(A, B, C, D)$ be an $(n, 1, \delta)$-code with $(A, B)$ in canonical controllable form and $A$ singular. Let $\tau$ be the integer as in Lemma 3.3. Let $\mathcal{V}_{\gamma}$ be the set of finite-weight codewords of $\mathcal{C}$ generated by an information vector $(u_{0}, u_{1}, \ldots, u_{s}, u_{s+1}, \ldots, u_{\gamma})$ with $u_{0}, u_{s}\neq 0$ and $u_{i} = 0$ for $i\notin \{ 0, s\}$. Then, the lowest weight of the parity vectors of $\mathcal{V}_{\gamma}$ with $\gamma < s + \tau$, is achieved for $s\leq q^{\delta}-(q^{(\gamma-s)}(q-1))$.

Proof. The proof follows the same idea used in the proof of Theorem 3.2. Note that by Lemma 3.1 we have that $\gamma \geq \delta$. Also it holds from Lemma 3.4 that dim($\ker A^{\gamma -s}) = \gamma -s < \tau$. Hence, for each value of $\gamma$ and $s$ such that $\gamma -s < \tau$ we have that $s$ is the smallest integer such that the last column of $A^s$ is a vector of the form

As there are $q^\delta$ possible states and $q^{(\gamma-s)}(q-1)$ different states are of the form (3.7), the maximum value of $s$ such that $A^sBu_0 - Bu_s$ is not in the kernel of $A^{\gamma -s}$ is $q^{\delta}-(q^{(\gamma-s)}(q-1))$ which yields the result.

4.   Optimal upper-bound on $\operatorname{z_{min}}$ for a class of $(n, 1, \delta)$ recursive systematic convolutional codes

In this section we present a concrete construction of a class of convolutional codes with $\delta \ge 2$ for which we can compute the minimum effective index and the exact value of $\operatorname{z_{min}}$ up to a difference of one value. Furthermore, we can show that such upper-bound is optimal and we do that by presenting a particular example that reaches the provided upper-bound. To this end we need a class of matrices that have been very useful for the construction of convolutional codes with large Hamming distance, namely, the so-called superregular matrices.

Definition 4.1 (Page 1314 of ^[31]). Let $A$ be an $n \times \ell$ matrix over a finite field $\mathbb{F}$. We say that $A$ is a superregular matrix if every square submatrix of $A$ is nonsingular.

The following Lemma is an immediate consequence of Definition 4.1 and it gives a lower bound on the weight of a linear combination of columns of a superregular matrix.

Lemma 4.1 (Lemma 3.3 of ^[10]). Let $A$ be a superregular matrix over a finite field $\mathbb{F}$ of size $n \times \ell$, with $n \geq \ell$. It follows that any nontrivial linear combination of $m$ different columns of $A$ cannot have more than $m-1$ entries equal to zero.

In the following result we present a particular construction based on a input-state-output representation where the pair $(A, B)$ is in canonical controllable form with $A$ singular, $C$ a superregular matrix and $D$ a column of $C$. We establish that the lowest weight of the parity vectors of $\mathcal{V}_{\gamma}$ is achieved in fact by the ones generated by weight-2 input sequences $(u_{0}, u_{1}, \ldots, u_{\gamma})$ with $u_{0}\neq 0$ and $u_{1}\neq 0$. Furthermore, we establish a lower and an upper bound of $\operatorname{z_{min}}(\mathcal{C})$ for these case.

Theorem 4.1. Let $\delta$ and $n$ be any positive integers with $\delta\ge 2$, $n\geq\delta+1$ and $q \ge n+ \delta$. Let $\mathcal{C}(A, B, C, D)$ be an $(n, 1, \delta)$-code described by the matrices

of sizes $\delta \times \delta$, $\delta \times 1$, $(n-1)\times \delta$ and $(n-1) \times 1$ respectively and where $C$ is a superregular matrix. Then we have that

Moreover, the minimum effective index $\hat{s}$ achieves its minimum possible value, i.e., $\hat{s} = 1$ and so the value of $\operatorname{z_{min}}(\mathcal{C})$ is reached in finite-weight codewords of minimum length $\gamma = \delta$ and it is calculate as

Proof. Taking into account the structure of the matrices $A$ and $B$ of (4.1) and Lemma 3.3, the finite-weight codeword of minimal length generated by input of weight two is $\mathcal{V}_{\delta}$. Furthermore, in this case we have that $u_1 = -u_0$ and $u_2 = u_3 = \cdots = u_\delta = 0$. Then, the parity check vectors of $\mathcal{V}_{\delta}$ are of the form:

where

for $j = 2, 3, \ldots, \delta$. Furthermore, $n-2\leq \operatorname{wt}(\vec{y}_{1})\leq n-1$ since $C$ is a superregular matrix and by Lemma 4.1 any nontrivial linear combination of two different columns of $C$ cannot have more than $1$ entry equal to zero. Similarly, we can ensure that $\operatorname{wt}(\vec{y}_{j}) = n-1$, since $C$ is superregular. So we obtain the following bounds on the weigth of the parity vectors $\vec{y}_{j}$ of $\mathcal{V}_{\delta}$.

Our aim now is to proof that in fact, $\operatorname{z_{min}}(\mathcal{C})$ is obtained from the minimum of the parity vectors of all finite-weight codewords of lenght $\delta+1$. In order to do this, consider now a finite-weight codeword $\mathcal{V}_{\gamma}$ generated by a input vector $(\bar{u}_{0}, \bar{u}_{1}, \ldots, \bar{u}_{\gamma})$ of weight two with $\gamma > \delta$. Then, there exists a time instant $r\geq 1$ such that $\bar{u}_{0}\neq 0$, $\bar{u}_{r}\neq 0$ and $\bar{u}_{j} = 0$ for $j\neq 0, r$. From Lemma 3.2, we know that if $r = 1$, then we can ensure that the parity vector $(\vec{\bar{y}}_{0}, \vec{\bar{y}}_{1}, \ldots, \vec{\bar{y}}_{\gamma})$ of $\mathcal{V}_{\gamma}$ have weight greater or equal to the parity vector $(\vec{y}_{0}, \vec{y}_{1}, \ldots, \vec{y}_{\delta})$ of any finite-weight codeword $\mathcal{V}_{\delta}$ of lenght $\delta+1$. Furthermore, if $r > 1$, then from the structure of matrices $A, B, C, D$, Lemma 3 and taking into account that $C$ is superregular, then we obtain the following bounds on the weight of the parity vector $(\vec{\bar{y}}_{0}, \vec{\bar{y}}_{1}, \ldots, \vec{\bar{y}}_{\gamma})$

Taking into account relations (4.5) and (4.6) and the fact that $\delta < n$, we obtain

where $(\vec{y}_{0}, \vec{y}_{1}, \ldots, \vec{y}_{\delta})$ and $(\vec{\bar{y}}_{0}, \vec{\bar{y}}_{1}, \ldots, \vec{\bar{y}}_{\gamma})$ are the parity vectors of any codewords $\mathcal{V}_{\delta}$ and $\mathcal{V}{\gamma}$ with $\gamma > \delta$, respectively. So we can conclude that $\operatorname{z_{min}}(\mathcal{C})$ is obtained by the minimum of the weight of the parity vectors of all the finite-weight codewords $\mathcal{V}_{\delta}$ generated by input vectors with length $\delta+1$. Furthermore, from relation (4.4), we deduce that in fact

In the following example, we show a convolutional code whose $\operatorname{z_{min}}(\mathcal{C})$ reaches the upper bound of the relation (4.2).

Example 4.1. Let ${{\mathbb{F}}}$ be the Galois field of $7$ elements and let $\mathcal{C}(A, B, C, D)$ be an $(4, 1, 2)$-code described by the matrices

It is easy to see that the the $(4, 1, 2)$-code described by the above matrices $A, B, C$ and $D$ satisfy the hypothesis of Theorem 4.2. Then we know that the

That is in this case the code attains the maximal value.

In the example before the superregular matrix $C$ is a Cauchy matrix and it is a small example. If we need to construct a turbo code with a determinate $\operatorname{z_{min}}(\mathcal{C})$ we must to consider a bigger parameters and consequently a bigger field. Work with a big finite field increases computational costs. In order to minimize the size of the field we introduce a similar construction for a singular $A$ similar to Theorem 4.1 in which we make use of the so-called extended Cauchy matrices (see ^[31]).

Theorem 4.2. Let ${{\mathbb{F}}}$ be the Galois field of $q$ elements. Let $\delta$ and $n$ be any positive integers with $\delta\ge 2$, $n\geq\delta+1$ and $q \ge n+ \delta -1$. Let $\mathcal{C}(A, B, C, D)$ be an $(n, 1, \delta)$-code described by the matrices

of sizes $\delta \times \delta$, $\delta \times 1$, $(n-1)\times \delta$ and $(n-1) \times 1$ respectively and where $C$ is a extended Cauchy matrix with the first column $\vec{c}_{1} = (c_{11}, c_{21}, ldots, c_{(n-1), 1})$ of ones. Then we have that

Moreover, the value of $\operatorname{z_{min}}(\mathcal{C})$ is reached in a finite code word of minimum length $\gamma = \delta$ and it is calculate as

Proof. The proof is analogous of Theorem 4.1.

Example 4.2. Let ${{\mathbb{F}}}$ be the Galois field of $5$ elements and let $\mathcal{C}(A, B, C, D)$ be an $(4, 1, 2)$-code described by the matrices

It is easy to see that the the $(4, 1, 2)$-code described by the above matrices $A, B, C$ and $D$ satisfy the hypothesis of Theorem 4.2. Then we know that the

That is in this case also the code attains the maximal value.

5.   Conclusions and future work

In this work we study the lowest Hamming weight of the parity vectors generated by information sequences of weight two, that is, $\operatorname{z_{min}}$, of a $1/n$ convolutional code $\mathcal{C}(A, B, C, D)$ represented in terms of the input-state-output representation. We analyze how one can reduce the computations to derive this value which is, in general, difficult to compute as it is the minimum over the large set of codeword with inputs of weight two. In this work we reduce this set by studying the structure of the codewords produced by the input-state-output system. This will lead to reduce the compute search to obtain the exact value of $\operatorname{z_{min}}(\mathcal{C})$. We also presented a class of convolutional codes for which we know the form of the codewords that lead to the computation of $\operatorname{z_{min}}$ and therefore allow us to determine its exact value up to a difference of one unit.

It is left as an open problem to provide a specific lower and upper bounds on $\operatorname{z_{min}}(\mathcal{C})$, and consequently, lower and upper bounds on the effective free distance over general finite fields. Also it would be interesting to show that this hypothetical upper bound it tight by presenting a concrete construction of a Turbo Code whose effective free distance reaches this bound. Also interesting it would be to derive different constructions to the one given in Section 4 having better bounds.

Acknowledgments

The authors would like to thank the anonymous reviewers for the their comments. The research of the second author was supported by Spanish I+D+i project PID2019-108668GB-I00 of MCIN/AEI/10.13039/501100011033.

Conflict of interest

The authors declare that there is no conflict of interests in this paper.