# A Decoding Algorithm for Convolutional Codes
## 2 Preliminaries and Notations
### Linear Codes and Error-Correcting Pairs  
Let \(\mathbb{F}_{q}\) be the finite field of \(q\) elements and let \(G\) be a \(\mathbb{F}_{q}\)-linear monomorphism:  
\[G:\mathbb{F}_{q}^{k}\hookrightarrow\mathbb{F}_{q}^{n}. \tag{1}\]  
We say that \(\mathcal{C}=\operatorname{Im}G\) is an _\((n,k)\)-linear code_ over \(\mathbb{F}_{q}\) and \(G\) is an _encoder_ associated with \(\mathcal{C}\). Thus, the encoding process is given by:  
\[u\longmapsto v=uG,\]  
where \(u\) is called _information word_ and \(v\) is called _codeword_. Given a code, there is relevant numerical data associated with it. First, since \(u\in\mathbb{F}_{q}^{k}\) consists of \(k\) symbols, \(k(\mathcal{C}):=k\) will be called the _dimension_ of the linear code \(\mathcal{C}\). Similarly, \(v\in\mathbb{F}_{q}^{n}\) consists of \(n\) symbols and, thus, \(n(\mathcal{C}):=n\) will be called the _length_ of \(\mathcal{C}\). The _minimum distance_ of \(\mathcal{C}\) is the minimum among the weights of its non-zero codewords, and it will be denoted by \(d_{\min}(\mathcal{C})\) or, if no confusion arises, simply by \(d\). Moreover, there are also some maps and subspaces attached to \(\mathcal{C}\). The _dual code_ of the code \(\mathcal{C}\), denoted by \(\mathcal{C}^{\perp}\subseteq\mathbb{F}_{q}^{n}\), is given by:  
\[\mathcal{C}^{\perp}=\{v\in\mathbb{F}_{q}^{n}\,|\,\langle v,c\rangle=0\ \forall\,c\in\mathcal{C}\},\]  
where the bilinear form \(\langle\,,\,\rangle:\mathbb{F}_{q}^{n}\times\mathbb{F}_{q}^{n}\to\mathbb{F}_{q}\) is defined as follows:  
\[\langle a,b\rangle=a\cdot b^{\dagger}=\sum_{i=1}^{n}a_{i}b_{i}.\]  
Throughout the paper, the transpose of a matrix \(M\) will be denoted by \(M^{\dagger}\) since we want to preserve \(t\) and \(T\) for other tasks. The dual code \(\mathcal{C}^{\perp}\) is an \((n,n-k)\)-linear code and any generator matrix \(H\) of \(\mathcal{C}^{\perp}\) is called the _parity check matrix_ of the code \(\mathcal{C}\); that is, \(\mathcal{C}^{\perp}=\operatorname{Im}H\) for a given \(H:\mathbb{F}_{q}^{n-k}\hookrightarrow\mathbb{F}_{q}^{n}\) of maximal rank with \(G\cdot H^{\dagger}=0\). The _syndrome map_ of a fixed linear code \(\mathcal{C}\), denoted by \(\sigma\), is given by:  
\[\sigma:\mathbb{F}_{q}^{n} \longrightarrow\operatorname{Hom}_{\mathbb{F}_{q}}(\mathcal{C}^{ \perp},\mathbb{F}_{q}) \tag{2}\] \[a \longmapsto \sigma(a)\text{ where }\sigma(a)(b):=\langle a,b\rangle\]  
so that \(a\in\mathcal{C}\) if and only if \(\sigma(a)=0\). Next, we recall the notions of the _generalized Reed-Solomon code_ as well as of _error-correcting pair_, which turns out to be relevant when decoding linear codes (see [1], SS 5.3; [6; 9]). First, we define the _star multiplication_ of \(a,b\in\mathbb{F}_{q}^{n}\), denoted by \(a\ast b\), by coordinatewise multiplication \(a\ast b:=(a_{1}b_{1},\ldots,a_{n}b_{n})\in\mathbb{F}_{q}^{n}\). For any two subspaces, \(\mathcal{A}\) and \(\mathcal{B}\), we introduce the set \(\mathcal{A}\ast\mathcal{B}:=\{a\ast b\,|\,a\in\mathcal{A},b\in\mathcal{B}\}\). Given positive integers \(k\leq n\), \(\mathbf{a}\), an _nt_tuple of pairwise distinct elements of \(\mathbb{F}_{q}\) and \(\mathbf{b}\), an _nt_tuple of nonzero elements of \(\mathbb{F}_{q}\), the associated generalized Reed-Solomon code of dimension \(k\) is the following subspace of \(\mathbb{F}_{q}^{n}\):  
\[\operatorname{GRS}_{k}(\mathbf{a},\mathbf{b}):= \langle\{\mathbf{b}\ast f(\mathbf{a})\text{ where }f(z)=1,z,z^{2},\ldots,z^{k-1}\}\rangle\] \[= \langle\{(b_{1}a_{1}^{\dagger},\ldots,b_{n}a_{n}^{\dagger})\text{ where }i=0,1,\ldots,k-1\}\rangle.\]For the sake of brevity, we say that \(\mathcal{C}\) is GRS, if \(\mathbf{a}\) and \(\mathbf{b}\) exist as above, such that \(\mathcal{C}=\mathrm{GRS}_{\mathcal{H}}(\mathbf{a},\mathbf{b})\). In this situation, it is proved in [1] (Thm. 5.3.3.) that \(\mathrm{GRS}_{k}(\mathbf{a},\mathbf{b})^{\perp}=\mathrm{GRS}_{n-k}(\mathbf{a}, \mathbf{c})\), where \(\mathbf{c}\) is any nonzero codeword in the 1-dimensional code \(\mathrm{GRS}_{n-1}(\mathbf{a},\mathbf{b})^{\perp}\).