# A Decoding Algorithm for Convolutional Codes
## 3 The Combined Algorithm
### Preparation and Assumptions  
For our algorithm to work correctly over an \((n,k)\)-convolutional code \(\mathcal{C}\), the matrices \(A\), \(B\), \(\mathcal{C}\) and \(D\) corresponding to the mISO representation of \(\mathcal{C}\) are assumed to satisfy some properties so that the hypothesis considered by both [PERSON] and [PERSON] are fulfilled.  
Let,  
\[\left\{\left(\begin{smallmatrix}y_{t}\\ u_{t}\end{smallmatrix}\right)\right\}_{t=0}^{\tau+T}\quad\left\{\left( \begin{smallmatrix}\hat{y}_{t}\\ \hat{u}_{t}\end{smallmatrix}\right)\right\}_{t=0}^{\tau+T}\]  
denote the transmitted and received sequences respectively where, from now on, \(\widehat{\ }\) will denote received words. Note that we only know \(\left\{\left(\begin{smallmatrix}\hat{y}_{t}\\ \hat{u}_{t}\end{smallmatrix}\right)\right\}\) and our task is to determine \(\left\{\left(\begin{smallmatrix}y_{t}\\ u_{t}\end{smallmatrix}\right)\right\}\).  
We suppose that the following assumptions are verified.  
**Assumption 1**.: \(T\)_, \(\Theta\in\mathbb{Z}_{+}\) are positive integers with \(T>\Theta\)._  
**Assumption 2**.: _A is invertible and the matrix:_  
\[\Psi(A,B)=\begin{pmatrix}B&AB&\ldots&A^{T-1}B\end{pmatrix}\]  
_has full row rank \(\delta\) and its rows form the parity check matrix of an \((n^{\prime},k^{\prime})\)-linear code \(\mathcal{C}^{\prime}\), where \(n^{\prime}=kT\) and \(k^{\prime}=\delta\). Let \(d^{\prime}\) be its minimum distance._  
**Assumption 3**.: \(\mathcal{G}^{\prime}\) _is an encoder for \(\mathcal{C}^{\prime}\). Moreover, the code \(\mathcal{C}^{\prime}\) is supposed to admit an error-correcting pair, say \((\mathcal{A}^{\prime},\mathcal{B}^{\prime})\)._  
**Assumption 4**.: _The matrix:_  
\[\Phi(A,C)=\begin{pmatrix}C\\ CA\\ \vdots\\ CA^{\Theta-1}\end{pmatrix}\]  
_has full column rank \(\delta\) and its columns define the generator matrix of an \((n^{\prime\prime},k^{\prime\prime})\)-linear code \(\mathcal{C}^{\prime\prime}\), where \(n^{\prime\prime}=(n-k)\Theta\) and \(k^{\prime\prime}=\delta\). Let \(d^{\prime\prime}\) be its minimum distance._  
**Assumption 5**.: \(G^{\prime\prime}\) _is an encoder for \(\mathcal{C}^{\prime\prime}\) and \(R^{\prime\prime}\) is a retraction of \(G^{\prime\prime}\); that is, a map \(R^{\prime\prime}:\mathbb{F}_{q}^{n^{\prime\prime}}\to\mathbb{F}_{q}^{k^{ \prime\prime}}\) such that, \(G^{\prime\prime}R^{\prime\prime}=\mathrm{Id}_{\mathbb{F}_{q}^{k^{\prime\prime}}}\). Moreover, the code \(\mathcal{C}^{\prime\prime}\) is supposed to admit an error-correcting pair, say \((\mathcal{A}^{\prime\prime},\mathcal{B}^{\prime\prime})\)._  
**Assumption 6**.: _From time unit \(t=0\) to time unit \(t=\tau-1\), the transmission is error free or, equivalently, has been correctly decoded; that is, \(\hat{y}_{t}=y_{t}\) and \(\hat{u}_{t}=u_{t}\) for \(0\leq t<\tau\)._  
**Assumption 7**.: _In any time interval of length \(T\), the error produced during the transmission has weight, at most:_  
\[\lambda:=\min\left(\left\lfloor\frac{d^{\prime}-1}{2}\right\rfloor,\left\lfloor \frac{T}{2\Theta}\right\rfloor\right) \tag{7}\]  
Let us briefly discuss why these assumptions are reasonable.  
The Assumptions 2 and 4 imply that \((A,B)\) forms a controllable pair and \((A,C)\) forms an observable pair and, from ([8], SS 5.3) one concludes that (4) forms a minimal state space representation of a non-catastrophic encoder (also see [12], Thm. 5).  
Similarly, Assumption 3 (resp. Assumption 5) allows us to apply [PERSON]'s decoding procedure to the linear code \(\mathcal{C}^{\prime}\) (resp. \(\mathcal{C}^{\prime\prime}\)).  
Since our algorithm is iterative and, as a result from the previous iteration, the Assumption 6 is taken for granted. Note that at the time unit \(t\), the error produced during the transmission is given by \(\left(\begin{smallmatrix}\hat{y}_{t}-y_{t}\\ \hat{u}_{t}-u_{t}\end{smallmatrix}\right)\). Finally, observe that the state \(x_{\tau}\) can be computed correctly from (4).