# A Decoding Algorithm for Convolutional Codes
## 3 The Combined Algorithm
### The Algorithm  
The Algorithm 1 goes as follows:  
```
1: Set \(h=0\). 2: If \(\tau+T-h\Theta+1<\tau+\Theta\) or \(\text{rk}\big{(}B\quad AB\quad\ldots\quad A^{T-(h+1)\Theta-1}B\big{)}<\delta\), then STOP (decoding unsuccessful). 3: Increase \(h\) by 1. 4:
5:
6:
7: Compute, \[\hat{r}^{\prime\prime}:=\left( \begin{smallmatrix}\hat{y}_{\tau+T-h\Theta+1}\\ \vdots\\ \hat{y}_{\tau+T-(h-1)\Theta}\end{smallmatrix} \right)-\left( \begin{smallmatrix} D&0&\ldots&0\\ \vdots&&\vdots\\ CA^{\Theta-2}B&CA^{\Theta-3}B&\ldots&D\end{smallmatrix} \right)\left( \begin{smallmatrix}\hat{u}_{\tau+T-h\Theta+1}\\ \vdots\\ \hat{u}_{\tau+T-(h-1)\Theta}\end{smallmatrix} \right)\]

from received vectors \(\left\{\left( \begin{smallmatrix}\hat{y}_{t}\\ \hat{u}_{t}\end{smallmatrix} \right)\right\}\). Note that \(\hat{r}^{\prime\prime}\) is a column vector with \(n^{\prime\prime}=(n-k)\Theta\). 8: If the morphism \(E_{\hat{r}^{\prime\prime}}:\mathcal{A}^{\prime\prime}\to\text{Hom}_{\mathbb{ F}_{q}}(\mathcal{B}^{\prime\prime},\mathbb{F}_{q})\) is injective, then go to 2. 9: Choose a nonzero element \(a\in\text{Ker}\ E_{\hat{r}^{\prime\prime}}\) and let \(J:=(a)_{0}\). 10: Compute the syndrome \(\sigma^{\prime\prime}(\hat{r}^{\prime\prime})\), where \(\sigma^{\prime\prime}\) is the syndrome map of \(\mathcal{C}^{\prime\prime}\). 11: If \(\sigma^{\prime\prime}_{J}(x)=\sigma^{\prime\prime}(\hat{r}^{\prime\prime})\) has no or more than one solution, then go to 2. 12: Let \(r^{\prime\prime}_{0}\) be the unique column vector such that \(\sigma^{\prime\prime}_{J}(r^{\prime\prime}_{0})=\sigma^{\prime\prime}(\hat{r} ^{\prime\prime})\) and let \(\omega(r^{\prime\prime}_{0})\) be its weight. 13: If \(\omega(r^{\prime\prime}_{0})>\left\lfloor\frac{d^{\prime\prime}-1}{2}\right\rfloor\), then go to 2. 14: Compute the state \(x_{\tau+T-h\Theta+1}\) with the help of the retraction \(R^{\prime\prime}\) of \(G^{\prime\prime}\) \[x_{\tau+T-h\Theta+1}=(R^{\prime\prime})^{\intercal}(\hat{r}^{\prime\prime}- \hat{r}^{\prime\prime}_{J}(r^{\prime\prime}_{0}))\]

and note that it is a column vector with \(k^{\prime\prime}=\delta\) rows. ```
5:
* Since \(\left(A^{T-h\Theta}B\quad\ldots\quad B\right)\) has full row rank \(\delta\), its rows form the parity check matrix of an \((n_{h}^{\prime},k_{h}^{\prime})\)-linear code \(\mathcal{C}_{h}^{\prime}\), where \(n_{h}^{\prime}=k(T-h\Theta)\) and \(k_{h}^{\prime}=\delta\). Let \(d_{h}^{\prime}\) its minimal distance and let \((\mathcal{A}_{h}^{\prime},\mathcal{B}_{h}^{\prime})\) be an error-correcting pair for \(\mathcal{C}_{h}^{\prime}\). 5: Set: \[\hat{u}:= \begin{pmatrix}\hat{u}_{\tau}\\ \vdots\\ \hat{u}_{\tau+T-h\Theta}\end{pmatrix} \] and compute: \[s:=\left(A^{T-h\Theta}B\quad\ldots\quad B\right)\hat{u}-x_{\tau+T-h\Theta+1} -A^{T-h\Theta+1}x_{\tau}.\] 5.3 If the morphism \(E_{h,h}:\mathcal{A}_{h}^{\prime}\to\operatorname{Hom}_{\mathbb{F}_{q}}( \mathcal{B}_{h}^{\prime},\mathbb{F}_{q})\) is injective, then go to 2. 5.4 Choose a nonzero element \(a\in\operatorname{Ker}E_{h,h}\) and let \(J:=(a)_{0}\). 5.5 If \(\sigma_{h,J}^{\prime}(x)=s\) has no or more than one solution, then go to 2. 5.6 Let \(s_{0}\) be the unique column vector such that \(\sigma_{h,J}^{\prime}(s_{0})=s\) and let \(\omega(s_{0})\) be its weight. 5.7 If \(\omega(s_{0})>\left\lfloor\frac{d_{h}^{\prime}-1}{2}\right\rfloor\), then go to 2. 5.8 Decode by: \[ \begin{pmatrix}u_{\tau}\\ \vdots\\ u_{\tau+T-h\Theta}\end{pmatrix} = \begin{pmatrix}\hat{u}_{\tau}\\ \vdots\\ \hat{u}_{\tau+T-h\Theta}\end{pmatrix} -t_{h,J}(s_{0}).\]
6: Compute the remaining states; i.e., \(x_{t}\) from time unit \(t=\tau+1\) to time unit \(t=\tau+T-h\Theta\) using the equation \(x_{t+1}=Ax_{t}+Bu_{t}\). 7: Compute the remaining parity vectors; i.e., \(y_{t}\) from time unit \(t=\tau\) to time unit \(t=\tau+T-h\Theta\), using the equation \(y_{t}=Cx_{t}+Du_{t}\). 8: If the resulting error sequence has weight: \[\sum_{t=\tau}^{\tau+T-h\Theta}\left(\omega(y_{t}-y_{t})+\omega(\hat{u}_{t}-u_ {t})\right)>\lambda-h+1\] then go to 2.