# A Decoding Algorithm for Convolutional Codes
## 3 The Combined Algorithm
### The Algorithm
9: The time window \(t=\tau,\ldots,\tau+\Theta-1\) has been correctly decoded. 10: If the end of the received sequence is not reached, then replace \(\tau\) by \(\tau+\Theta\) and return to \(1\). 11: END (decoding successful). ```

**Algorithm 1**_Cont_. ### Justification

Let us provide some explanation for each step of the algorithm. First, Step 2 warrantes that we increase \(h\) and that the code \(\mathcal{C}_{h}^{\prime}\) of 5.1 is well defined and can be decoded by [PERSON]'s algorithm. The computation of \(\hat{\tau}^{\prime\prime}\) of step 4 is correct thanks to the identity (5) (also see [5], Equations (4.3) and (4.4)) and, thus, concerns the code \(\mathcal{C}^{\prime\prime}\) (see Assumption 4). The other computations of step 4 are the implementation of [PERSON]'s algorithm for the code \(\mathcal{C}^{\prime\prime}\) in terms of the error-correcting pair \((\mathcal{A}^{\prime\prime},\mathcal{B}^{\prime\prime})\). Step 5 is related to identity (6) (also see [5], Equation (4.5)) and, thus, to the code \(\mathcal{C}_{h}^{\prime}\) (see Assumption 2 and [5], Equation (4.6)). The following parts of step 5 are the implementation of [PERSON]'s algorithm for the code \(\mathcal{C}_{h}^{\prime}\) in terms of the error-correcting pair \((\mathcal{A}_{h}^{\prime},\mathcal{B}_{h}^{\prime})\). Steps 6 and 7 are deduced from (4). Finally, step 8 is the translation of the last paragraph of page 11 of [5] while step 9 corresponds to the first one of page 12 of [5]. The next step deals with the successful decoding and proceeding to the next iteration that slides the time window forward. By contrast, the last step considers the case of an unsuccessful decoding that slides the time window backward. It should be pointed out that the algorithm will produce a correct answer as long as Assumption 7 holds. ### Complexity

Now, let us give some bounds for the complexity of our algorithm. Recall from ([6], Thm. 2.14) that, since the error-correcting pair is defined over the base field \(\mathbb{F}_{q}\), the algorithm proposed by [PERSON] has complexity \(\mathcal{O}(n^{3})\), where \(n\) is the length of the linear code we are decoding. Hence, the complexity of step 4 is \(\mathcal{O}\big{(}(n^{\prime\prime})^{3}\big{)}=\mathcal{O}\big{(}((n-k) \Theta)^{3}\big{)}\) and that of step 5 is \(\mathcal{O}\big{(}(n^{\prime}_{h})^{3}\big{)}=\mathcal{O}\big{(}(k(T-h\Theta) )^{3}\big{)}\). By computing the sizes of the matrices and applying well-known algorithms (e.g., [14; 15]), each matrix computation in the remaining steps has a complexity equal to or less than the complexity of [PERSON]'s algorithm. Thus, the \(h\)th iteration of the algorithm has complexity:

\[\mathcal{O}\Big{(}\max\{((n-k)\Theta)^{3},(k(T-h\Theta))^{3}\}\Big{)}.\]

In the best case, where the first iteration is able to decode \(\Theta\) codewords, the computational cost by codeword is:

\[\mathcal{O}\Big{(}\frac{1}{\Theta}\max\{((n-k)\Theta)^{3},(k(T-\Theta))^{3}\} \Big{)}. \tag{8}\]

In a worst case scenario and keeping Step 2 in mind, \(\lfloor\frac{T}{\Theta}\rfloor\) iterations are required to decode \(\Theta\) codewords since it may occur that \(T-\lfloor\frac{T}{\Theta}\rfloor\Theta=1\). Then, the computational cost by codeword is bound from above by:

\[\mathcal{O}\Big{(}\frac{T}{\Theta}\frac{1}{\Theta}\max\{((n-k)\Theta)^{3},(k( T-\Theta))^{3}\}\Big{)}. \tag{9}\]

### Performance

Let us briefly discuss the error correction capability of our approach. Let us point out that, since we are dealing with non-catastrophic encoders (see Section 3.1), a finite number of channel corruptions can not lead to an infinite sequence of errors after decoding. Furthermore, following ([5], Thm. 3.4), the correct decoding is possible if no more than \(\lambda\) errors occur in any time window of length \(T\) (see Assumption 7). The study of performance in terms of BER (_bit error rate_) and SNR (_signal to noise ratio_) is a must before implementing any transmission scheme. In fact, such study requires fixing the convolutional code, the channel and the algorithm.