# A Decoding Algorithm for Convolutional Codes
## 3 The Combined Algorithm
### The Algorithm
\begin{array}{cccc}1& 1&\ldots&1\\ \alpha&\alpha^{2}&\ldots&\alpha^{\delta}\\ \vdots&&&\vdots\\ \alpha^{n-k-1}&\alpha^{2(n-k-1)}&\ldots&\alpha^{\delta(n-k-1)}\\ \alpha^{k}&\alpha^{2k}&\ldots&\alpha^{\delta k}\\ \alpha^{k+1}&\alpha^{2k+2}&\ldots&\alpha^{\delta k+\delta}\\ \vdots&&&\vdots\\ \alpha^{n-k-1+k}&\alpha^{2(n-k-1)}&\ldots&\alpha^{\delta(n-k-1)+\delta k}\\ \vdots&&&\vdots\\ \vdots&&&\vdots\\ \alpha^{k(\Theta-1)}&\alpha^{2k(\Theta-1)}&\ldots&\alpha^{\delta k(\Theta-1) }\\ \alpha^{k(\Theta-1)+1}&\alpha^{2k(\Theta-1)+2}&\ldots&\alpha^{\delta k(\Theta-1) +\delta}\\ \vdots&&&\vdots\\ \alpha^{k(\Theta-1)+n-k-1}&\alpha^{2k(\Theta-1)+2(n-k-1)}&\ldots&\alpha^{ \delta k(\Theta-1)+\delta(n-k-1)}\end{array} \right). \tag{15}\]

Thus, considering \(b_{j}=1\) and:

\[a_{j}=\left\{ \begin{array}{ll}\alpha^{j-1}&\text{if }1\leq j\leq n-k\\ \alpha^{k+j-1-(n-k)}&\text{if }n-k+1\leq j\leq 2(n-k)\\ \vdots&\vdots\\ \alpha^{k(\Theta-1)+j-1-(\Theta-1)(n-k)}&\text{if }(\Theta-1)(n-k)+1\leq j \leq\Theta(n-k)\end{array} \right.\]

it follows that \(\mathcal{C}^{\prime\prime}=\operatorname{GRS}_{\delta}(\mathbf{a},\mathbf{b})\). As \(\mathcal{C}^{\prime\prime}\) is a GRS, it is also MDS, and its minimum distance is given by the Singleton Bound:

\[d^{\prime\prime}=d_{\min}(\mathcal{C}^{\prime\prime})=(n-k)\Theta-\delta+1. \tag{16}\]

Furthermore, it admits an error-correcting pair \((\mathcal{A}^{\prime\prime},\mathcal{B}^{\prime\prime})\) (see (3)). ### Parameters, Assumptions and Complexity

Throughout this section, we have dealt with the convolutional code \(\mathcal{C}\) as well as with the linear codes \(\mathcal{C}^{\prime}\), \(\mathcal{C}^{\prime}_{h}\) and \(\mathcal{C}^{\prime\prime}\). However, it remains to check whether all the assumptions of Section 3.1 hold. This is achieved using the following choice of parameters:

**1. **: \(\frac{n}{2}\leq k<n\);
**2. **: \(\delta>\frac{1}{2k-n}(n-k)(2k-n+1)\) if \(n\
eq 2k\) and \(\delta>1\) if \(n=2k\);
**3. **: \(\left\lvert\mathbb{F}_{q}\right\rvert=q>\delta k\left\lvert\frac{\delta}{n-k}\right\rvert\); and
**4. **: \(T:=\delta\left\lvert\frac{\delta}{n-k}\right\rvert\) and \(\Theta:=\left\lvert\frac{\delta}{n-k}\right\rvert\). The second condition implies that \(T>\Theta\), i.e., Assumption 1 is fulfilled. The first and third conditions imply, by ([13], Cor. 3.2; [8], Thm. 6.3.2; [12], SS 3), that the convolutional code \(\mathcal{C}\) corresponding to the mISO representation (10) is a non-catastrophic \((n,k)\)-convolutional code with degree \(\delta\) and free distance:

\[d_{\text{free}}(\mathcal{C})\geq\delta+1. \tag{17}\]Let us check that Assumption 2 is satisfied. First, from the choice of the parameters, one has:

\[k(T-1)+k-1=kT-1=k\delta\bigg{\lceil}\frac{\delta}{n-k}\bigg{\rceil} -1<q\] \[k(T-1)+k-1=k\delta\bigg{\lceil}\frac{\delta}{n-k}\bigg{\rceil}-1 \geq\delta^{2}-1\geq\delta,\]

and, thus, the rank of \(H^{\prime}\) is \(\delta\) (see (12)). Similarly,

\[k(\Theta-1)+n-k-1<k(T-1)+k-1=kT-1<q\] \[k(\Theta-1)+n-k-1=k\bigg{\lceil}\frac{\delta}{n-k}\bigg{\rceil}- k+(n-k-1)\geq\] \[k\bigg{(}\frac{\delta}{n-k}\bigg{)}+(n-2k-1)>k\bigg{(}\frac{ \delta}{n-k}\bigg{)}+\frac{\delta(n-2k)}{n-k}=\delta,\]

where the last inequality follows from the bound on \(\delta\) imposed by the second condition. Hence, the rank of \(G^{\prime\prime}\) is \(\delta\) (see (15)) and Assumption 4 is also fulfilled. Since Sections 4.2 and 4.3 provide explicit error-correcting pairs for \(\mathcal{C}^{\prime}\), \(\mathcal{C}^{\prime}_{h}\) and \(\mathcal{C}^{\prime\prime}\), Assumptions 3 and 5 are true. Regarding Assumption 7, let us compute \(\lambda\) in (7). In fact, from (13) and the choices of \(T\) and \(\Theta\), one obtains:

\[\lambda:=\min\bigg{(}\bigg{\lfloor}\frac{d^{\prime}-1}{2}\bigg{\rfloor},\bigg{ \lfloor}\frac{T}{2\Theta}\bigg{\rfloor}\bigg{)}=\bigg{\lfloor}\frac{\delta}{2 }\bigg{\rfloor}.\]

Finally, we may write down the bounds on the complexity for this situation.