# A Decoding Algorithm for Convolutional Codes
## 3 The Combined Algorithm
### The Algorithm
Indeed, since \(k\geq n-k\) and \(T>\Theta\), the best case bound (8) yields:

\[\mathcal{O}\bigg{(}\frac{1}{\Theta}\max\{((n-k)\Theta)^{3},(k(T- \Theta))^{3}\}\bigg{)}=\mathcal{O}\bigg{(}\frac{1}{\Theta}(k(T-\Theta))^{3} \bigg{)}\\ =\mathcal{O}\bigg{(}\frac{n-k}{\delta}\bigg{(}\frac{k\delta^{2}} {n-k}\bigg{)}^{3}\bigg{)}=\mathcal{O}\bigg{(}\frac{k^{3}\delta^{5}}{(n-k)^{2} }\bigg{)}. \tag{18}\]

For the worst case, the bound can be sharpened since \(\Theta\) codewords are decoded after \(\frac{T}{\Theta}\) iterations. Indeed, the cost per decoded codeword (9) is:

\[\mathcal{O}\bigg{(}\frac{T}{\Theta^{2}}\max\{((n-k)\Theta)^{3},(k (T-\Theta))^{3}\}\bigg{)}=\mathcal{O}\bigg{(}\frac{T}{\Theta^{2}}(k(T-\Theta) )^{3}\bigg{)}\\ =\mathcal{O}\bigg{(}(n-k)\bigg{(}\frac{k\delta^{2}}{n-k}\bigg{)} ^{3}\bigg{)}=\mathcal{O}\bigg{(}\frac{k^{3}\delta^{6}}{(n-k)^{2}}\bigg{)}. \tag{19}\]

**Remark 1**. : _Recalling the generalized Singleton bound for convolutional codes and (17), one gets the inequalities:_

\[d_{\text{free}}(\mathcal{C})\geq\delta+1. \tag{17}\]0

_so that one wonders if our algorithm could be adapted for greater values of \(\lambda\) in Assumption 7 Indeed, one should study how the linear codes \(\mathcal{C}^{\prime}\), \(\mathcal{C}^{\prime}_{h}\) and \(\mathcal{C}^{\prime\prime}\) behave when \(\mathcal{C}\) is assumed to be maximum distance separable; for instance, for those codes built in [18]. As a second approach, one could replace [PERSON]'s algorithm by the Sudan-Guruswami decoding algorithm (see [1], SS 5.4.4). This algorithm, which also applies to generalized Reed-Solomon codes, might correct more than \(\bigg{\lfloor}\frac{d_{\text{ring}}-1}{2}\bigg{\rfloor}\) errors, although its complexity is greater than that of [PERSON]._

**Example 1**. : _As an illustration of parameters satisfying the constraints of Section 4.4, we offer two examples, which are also related to the discussion of ([5], SS 5 Variation 2). First, we set \(n\geq 2\) and \(a\geq 2\) and define \(k:=n-1\), \(\delta:=(a-1)(n-k)+1=a\). Then, it holds that \(T=a^{2}\), \(\Theta=a\) and Algorithm 3 will correct errors of weight at most \(\lambda=\left\lfloor\frac{\delta}{2}\right\rfloor=\left\lfloor\frac{a}{2}\right\rfloor\) in any time window of length \(T=a^{2}\). It is worth noticing that, in this case, \(d^{\prime}=\delta+1=a+1\) and \(d^{\prime\prime}=(n-k)\Theta-\delta+1=a-a+1=1\)._

_The second example deals with \(n\) even and \(a\geq 2\). Define \(k:=\frac{n}{2}\), \(\delta:=(a-1)(n-k)+1=(a-1)k+1\). Since \(\left\lceil\frac{\delta}{n-k}\right\rceil=a\), it holds that \(T=((a-1)k+1)a\), \(\Theta=a\). Then, the algorithm will correct errors of weight at most \(\lambda=\left\lfloor\frac{\delta}{2}\right\rfloor=\left\lfloor\frac{(a-1)k+1 }{2}\right\rfloor\) in any time window of length \(T\). In this case, \(d^{\prime}=\delta+1=(a-1)k+2\) and \(d^{\prime\prime}=(n-k)\Theta-\delta+1=ka-(a-1)k-1+1=k\)._

## 5 Conclusions

We have offered a full and explicit implementation of a hard decoding algorithm for a class of convolutional codes based on algebraic techniques [5; 6], as well as an approach to the complexity of the resulting algorithm. For a given family of codes ([7], SS IV; [8]), we have checked that the parameters required for the algorithm can be chosen so that the assumptions are fulfilled. A detailed analysis of the computational complexity has allowed us to give lower and upper bounds for the computational cost per decoded codeword. These bounds are polynomial in the degree of the convolutional code. Further research must be carried out in, at least, three aspects. First, an appropriate model for the transmission channel (e.g., binary symmetric channel, additive white gaussian noise (AWGN) channel, erasure channel, etc.) must be found so that one can compute the expected complexity, that is, the complexity of the average case (see, for instance, [19]).