# A Decoding Algorithm for Convolutional Codes
## 2 Preliminaries and Notations
### Convolutional Codes and ISO Representations  
In order to enhance the correcting capabilities of a code against burst errors, one may consider codes where the transmitted block depends on those sent previously. Among these codes, in this paper we focus on convolutional codes. In the next paragraphs, we recap some facts on convolutional codes (e.g., [5], SS 2; [1], Ch. 14; and [10, 11]). In this case, the entries of the encoder matrix are polynomials, and an _\((n,k)\)-convolutional code_\(\mathcal{C}\) is the subspace generated by the image of the linear monomorphism:  
\[G(z):\mathbb{F}_{q}[z]^{k} \hookrightarrow\mathbb{F}_{q}[z]^{n}\] \[u(z) \mapsto v(z)=u(z)G(z);\]  
that is, \(\mathcal{C}=\mathrm{Im}\,G(z)\). The words are considered as polynomials and the independent variable represents the delay operator. In this setup, \(n\) is called the _length_ and \(k\) the _dimension_ of \(\mathcal{C}\). The _degree_, which is denoted by \(\delta\), is the highest (polynomial) degree of the \(k\times k\) minors of \(G(z)\) or, equivalently, of any encoder matrix. Finally, the _free distance_, \(d_{\text{free}}\) is the minimum among the weights of its non-zero codewords and it is an analogous to the minimum distance of linear codes. The free distance is a code property and indicates the error-correcting capability of a code, since a convolutional code can correct all errors of weight at most \(e\) if and only if \(d_{\text{free}}>2e\) (see [4], Theorem 3.3). Occasionally, alternative representations of these codes allows us to operate with them more easily. In this paper, motivated by the origin of these codes, we consider the _minimal Input/State/Output representation_ (see [5; 12]), or mISO for short, of an \((n,k)\)-convolutional code \(\mathcal{C}\), which is defined by the linear system:  
\[ \begin{cases}x_{t+1}=Ax_{t}+Bu_{t}\\ y_{t}=Cx_{t}+Du_{t}\\ v_{t}=\left(\begin{smallmatrix}y_{t}\\ u_{t}\end{smallmatrix}\right),\ x_{0}=0,\end{cases}  \tag{4}\]  
where \(x_{t},y_{t}\), \(u_{t}\) and \(v_{t}\) are column vectors, \(A\in\mathbb{F}_{q}^{\delta\times\delta}\), \(B\in\mathbb{F}_{q}^{\delta\times k},C\in\mathbb{F}_{q}^{(n-k)\times\delta}\), \(D\in\mathbb{F}_{q}^{(n-k)\times k}\) and \(t\) denote the time unit. In this characterization, the sequence of vectors \(u_{t}\) represents the information vectors, the sequence of \(y_{t}\) represents the parity vectors and the sequence of \(v_{t}\) represents the code vectors. We can also observe that the system (4) provides us a state space realization of a _systematic encoder_; that is, the code vectors are built as the concatenation of the parity vectors and the information vectors. The relationships between properties of a convolutional code and those of the associated mISO representation can be found in ([13], SS 2; [8; 12]). In particular, we are only interested in mISO representations that are reachable and observable as linear systems. In terms of the corresponding convolutional code, this means that it is non-catastrophic or, equivalently, that it admits a polynomial parity check matrix. The following proposition, proved in ([8], Prop. 6.1.1), provides a characterization of codewords. **Proposition 1** (Local Description of Trajectories). : _Let \(\mathcal{C}\) be an \((n,k)\)-convolutional code and consider its mISO representation. Let \(\tau\), \(\gamma\in\mathbb{Z}_{+}\) be positive integers such that \(\tau<\gamma\). Assume that the encoder is at state \(x_{\tau}\) at time unit \(t=\tau\). Then, any sequence \(\left\{\left( \begin{smallmatrix}y_{t}\\ u_{t}\end{smallmatrix} \right)\right\}_{t\geq 0}\) must satisfy:_  
\[ \begin{pmatrix}y_{\tau}\\ y_{\tau+1}\\ \vdots\\ \vdots\\ y_{\gamma}\end{pmatrix} = \begin{pmatrix}C\\ CA\\ \vdots\\ \vdots\\ CA^{\gamma-\tau}\end{pmatrix} x_{\tau}+ \begin{pmatrix}D&0&\ldots&\ldots&0\\ CB&D&\ldots&\ldots&\vdots\\ CAB&CB&\ldots&\ldots&\vdots\\ \vdots&\vdots&0\\ CA^{\gamma-\tau-1}B&CA^{\gamma-\tau-2}B&\ldots&CB&D\end{pmatrix}\begin{pmatrix}u _{\tau}\\ u_{\tau+1}\\ \vdots\\ \vdots\\ u_{\gamma}\end{pmatrix} .