# A Decoding Algorithm for Convolutional Codes
## 3 The Combined Algorithm
### The Algorithm
Thus, in order to simulate the performance of our algorithm, we have to choose a fixed convolutional as well as a transmission channel (e.g., binary erasure channel (BEC), binary symmetric channel (BSC) and additive white Gaussian noise (AWGN), among others). Future research must be conducted towards this study following the ideas of [16; 17]. ## 4 A Case Study

Next, as an illustration, we show that the combined algorithm detailed in Section 3 can be used to decode received messages that have been previously encoded by the convolutional code studied in ([7], SS IV; [8], SS 6.3). To do this, it must be checked if the code verifies the required hypotheses. ### The Convolutional Code

Thus, let \(\alpha\) be a primitive element of \(\mathbb{F}_{q}\) and let \(n\), \(k\) be positive integers such that \(k\geq\frac{n}{2}\). Let \(\mathcal{C}\) be the \((n,k)\)-convolutional code \(\mathcal{C}\) of degree \(\delta\) corresponding to the following mISO representation:

\[ \begin{cases}A=(a_{ij})\in\mathbb{F}_{q}^{\delta\times\delta}&\text{ where }a_{ij}=\alpha^{ik}\text{ for }i=j\text{ and }0\text{ otherwise,}\\ B=(b_{ij})\in\mathbb{F}_{q}^{\delta\times k}&\text{ where }b_{ij}=\alpha^{i(j-1)},\\ C=(c_{ij})\in\mathbb{F}_{q}^{(n-k)\times\delta}&\text{ where }c_{ij}=\alpha^{(i-1)j},\\ D=(d_{ij})\in\mathbb{F}_{q}^{(n-k)\times k}&\text{ where }d_{ij}=\alpha^{(i-1)j}. \end{cases}  \tag{10}\]

There are, indeed, some constraints that \(q,\delta,k,n\) must satisfy in order to fulfill the Assumptions of Section 3.1. We will postpone this issue until Section 4.4. ### The Linear Codes \(\mathcal{C}^{\prime}_{h}\)

Initially, we study the linear code \(\mathcal{C}^{\prime}\) whose parity check matrix consists of the rows of (see Assumption 2):

\[H^{\prime}:=\Psi(A,B)= \begin{pmatrix}B&AB&\ldots&A^{T-1}B\end{pmatrix}  \tag{11}\]

which explicitly yields:

\[H^{\prime}= \begin{pmatrix}1&\alpha&\ldots&\alpha^{k(T-1)+k-1}\\ 1&\alpha^{2}&\ldots&\alpha^{2k(T-1)+2(k-1)}\\ \vdots&\vdots&&\vdots\\ 1&\alpha^{\delta}&\ldots&\alpha^{k(T-1)+\delta(k-1)}\end{pmatrix} . \tag{12}\]

In order to prove that \(\mathcal{C}^{\prime}\) is GRS, by the facts of Section 2.1, it suffices to show that \((\mathcal{C}^{\prime})^{\perp}\) is GRS. Looking at the expression of (12), it is clear that \(H^{\prime}\in\mathbb{F}_{q}^{\delta\times kT}\) is the matrix whose \((i,j)\)-entry is \(\alpha^{i(j-1)}\) and thus \((\mathcal{C}^{\prime})^{\perp}=\operatorname{GRS}_{\delta}(\mathbf{a}, \mathbf{b})\), where \(a_{j}=\alpha^{j-1}\) and \(b_{j}=1\) for \(j=1,\ldots,kT\). Note that \(\mathcal{C}^{\prime}\) has length \(kT\) and dimension \(kT-\delta\). Now, since GRS codes are MDS (see [1], Thm. 5.3.1. (i)), it follows that the minimum distance of \(\mathcal{C}^{\prime}\) is equal to the Singleton Bound, namely:

\[d^{\prime}=d_{\min}(\mathcal{C}^{\prime})=kT-kT+\delta+1=\delta+1. \tag{13}\]

Once this code has been studied, we turn to the linear codes \(\mathcal{C}^{\prime}_{h}\) defined in step 5.1 of the Algorithm. The same reasoning shows that \(\mathcal{C}^{\prime}_{h}\) is GRS as long as it has maximal rank \(\delta\). Note that \(\mathcal{C}^{\prime}_{h}\), being MDS, has minimum distance equal to \(d^{\prime}_{h}:=n^{\prime}_{h}-k^{\prime}_{h}+1=k(T-h\Theta)-\delta+1\). Finally, (3) would allow us to record explicit expressions for an \(\left\lfloor\frac{n^{\prime}_{h}-k^{\prime}_{h}}{2}\right\rfloor\)-error-correcting pair \((\mathcal{A}^{\prime}_{h},\mathcal{B}^{\prime}_{h})\). ### The Linear Code \(\mathcal{C}^{\prime\prime}\)

Now we focus on the linear code \(\mathcal{C}^{\prime\prime}\) that is generated by the columns of the matrix (see Assumption 4):

\[\Phi(A,C)= \begin{pmatrix}C\\ CA\\ \vdots\\ CA^{\Theta-1}\end{pmatrix} =(G^{\prime\prime})^{\dagger}. \tag{14}\]Upon carrying out the computations, we deduce that the generator matrix of the \(((n-k)\Theta,\delta)\)-linear code \(\mathcal{C}^{\prime\prime}\) is given by the following matrix:

\[\left(\mathcal{G}^{\prime\prime}\right)^{\ddagger}=\left(