/*#####################################################*/ /*# Author: Julien #*/ /*# Description: Forward-Backward algorithm #*/ /*# ( choice of registers number, of output number #*/ /*# and polynom generator choice ) #*/ /*# There is only one bit at the encode entry. #*/ /*# Date: 15/05/20000 #*/ /*#####################################################*/ There are different architectures to describe the Forward-Backward algorithm. These architectures can be different according to several criteria. /*#####################################################*/ I) Different parameters to define an architecture /*#####################################################*/ Actually, the different architectures are defined in different main, but the following parameters can be used to define different architectures and to define one single main . 1) Firstly, you must choose the RU (Recursion Unit) number for the Forward and Backward recursions. na = number of Forward RU nb = number of Backward RU 2) Secondly, the Forward-Backward architecture is different if the Ak vectors or the Bk vectors or both are stored. The memory type is defined thanks to the M parameter : M = 0 = ma = Ak vectors are stored M = 1 = mb = Bk vectors are stored M = 2 = mx = Ak and Bk vectors are stored 3) Then, you choose if you use pointers. The pointer use is defined thanks to the Pt parameter. Pt = 0 : no pointer use Pt = number (>0) : use of pointer and there are "number" pointers. Furthermore, if Pt is different from 0, the pointer type must be defined. The type parameter is defined: type = 0 : Pt Ak vectors memorised type = 1 : Pt Bk vectors memorised 4) Finally, you can change the ratio between the hardware clock and the symbol clock. We can define this new parameter with the letter p. At this moment, these parameters have been used to describe the chosen architecture. /*#####################################################*/ II) Description of different architectures /*#####################################################*/ 1) na=1, nb=2, M=0 ________________ To decode the received symbols, the following steps must be respected for the LLR computation : I) initialisations - - - - - - - - This initialisation is different for each architecture. For this one, the initialisation begins after the reception of the 2L first symbols: Firstly, you have to compute the branchmetrics values: * branchmetrics1 between 0 and L. * branchmetrics2 between L and 2L. Secondly, you have to compute the first Forward metric nodes. So, you have to compute one Forward RU between 0 and L: - you define the first node metric: Ao(0) = 0 and Ao(s) = -infinite if s isn't equal to 0. - you compute one Forward RU thanks to the Recursion_Forward function. The last computed value thanks to the Recursion_Forward function is stored in the final_forward_metric variable. Finally, you have to compute the first Backward1 metric nodes. So, you have to compute one Backward1 RU between 2L and L: - you define the first node metric: B[2L-1](0) = 0 and B[2L-1](s) = -infinite if s isn't equal to 0. - you compute one Backward1 RU thanks to the Recursion_Backward function. NOTICE: The Backward1 RU performs L recursions to obtain the convergence ------ lenght.The last computed value thanks to the Recursion_Backward function is stored in the final_backward_metric variable. II) beginning of the loop: - - - - - - - - - - - - The loop computes L received symbols in one cycle. So, the loop is defined as: for (i=0; i<([size of the message/L]-1); i++) The loop begins with the initialisation of the second Backward RU. In fact, the convergence length is reached thanks to the Backward1 RU. The last value of this RU1 is, for each cycle, the value which allows the computation of the Backward node metrics of the second backward recursion. So, at the beginning of the loop, there is: - Backward2_MN [L-1] = final_backward_metric - one Backward2 RU between L-1 and 0. III) LLR computation: - - - - - - - - - The LLR computation needs the L values of the Backward2 and the Forward RU and the values of the branch metrics1. The LLR function computes the ratio and it gives the reliability of each decoded bit. - LLR between iL and (i+1)L IV) A new sequence begins: - - - - - - - - - - - - Now, the LLR of the L symbols is computed and the L symbols of the input message are known. Then, a new sequence can begin. So, there are: - a computation of the Forward node metrics between (i+1)L and (i+2)L. This time, we use the branchmetrics2 in the Forward_Recursion function to compute the node metrics. The initialisation is obtained thanks to final_forward_metric. - a computation of the branch_metrics3. - a computation of the Backward1 node metrics between (i+2)L and (i+3)L thanks to branch_metrics3 and the following initialisation: B(i+3)[L-1](0) = 0 and B(i+3)[L-1](s) = -infinite if s isn't equal to 0. - updating of the branchmetrics: tampon <= branchmetrics1 branchmetrics1 <= branchmetrics2 branchmetrics2 <= branchmetrics3 Now, it is possible to compute the L next values of the Backward2 RU as it was described in II). The LLR computation can decode a new sequence. NOTICE: We decode the last L bits outside the loop with the same process, ------ but we don't compute a new sequence. So, only steps II) and III) are treated. /*#################################################################################*/ When another architecture is chosen, the same procedure is used with different orders. Furthermore, the initialisation is different. /*#################################################################################*/ 2) na=1, nb=2, M=1 ________________ To decode the received symbols, the following steps must be respected for the LLR computation (notice: the initialisation is not treated): I) loop: - - - The loop computes L received symbols in one cycle. The loop is defined as: for (i=0; i<([size of the message-3L]/L); i++) A) initialisation and computation of the Forward recursion The initialisation of the Forward RU is : Ao(0) = 0 and Ao(s) = -infinite if s isn't equal to 0. To compute the forward node metrics, we use the Recursion_Forward function and the branchmetrics1 values. NOTICE: this initialisation begins if i>3. B) LLR computation The LLR computation needs the L values of the Backward2 and the Forward RU and the values of the branch metrics1. The LLR function computes the ratio and it gives the reliability of each decoded bit. C) initialisation of the backward2 recursion We obtain the first value of the backward2 recursion thanks to the final_backward metric1 value. So: Backward2_MN [L-1] = final_backward_metric1 To compute the backward node metrics, we use the Recursion_Backward function and the branchmetrics2 values. D) updating of the branch_metrics We have to permute now the branchmetrics: tampon = branch_metrics1 branch_metrics1 = branch_metrics2 branch_metrics2 = branch_metrics3 branch_metrics3 = tampon E) initialisation of branchmetrics4 You have to compute the branchmetric values with the new received data sequence. F) initialisation of the backward1 recursion The first value is: B[L-1](0) = 0 and B[L-1](s) = -infinite if s isn't equal to 0. To compute the backward node metrics, we use the Recursion_Backward function and the branchmetrics3 values. II) When the loop is finished: After the loop, you have to compute the last 2L bits between (count - 3L) and (count - L). You have to compute firstly the forward metrics nodes and the LLR. Then, you have to compute the backward2 metric nodes and permute the branchmetrics2 values in the branchmetrics1 values. Then, you compute the forward recursion and LLR. NOTICE: We cannot decode the last L bits. 3) na=1, nb=3, M=1, Pt=3, type=1 _______________________________ To decode the received symbols, the following steps must be respected for the LLR computation : I) the size of the convergence lenght: if K, the constraint lenght, is even, L = 6*K if K is odd, L must be a multiple of 4 Notice: initialisation is not treated II) loop: - - - The loop computes L received symbols in one cycle. The loop is defined as: for (i=1; i<([size of the message/L]+1); i++) A) initialisation of branchmetrics4 Firstly, you have to compute the branchmetric4 values between (i-1)*L and i*L. B) initialisation of the backward1 recursion The first value is: B[L-1](0) = 0 and B[L-1](s) = -infinite if s isn't equal to 0. To compute the backward node metrics, we use the Recursion_Backward function and the branchmetrics4 values. C) initialisation and computation of the Forward recursion The initialisation of the first Forward RU is : Ao(0) = 0 and Ao(s) = -infinite if s isn't equal to 0. For the initialisation of the other Forward recursions, we use the final_forward_metric value as: forward_metric[0][s] = final_forward_metric[s] with s, the different state values To compute the forward node metrics, we use the Recursion_Forward function and the branchmetrics1 values. NOTICE: this initialisation begins if i>3 and there is an internal loop for each L/4 cycle. D) LLR computation The LLR computation needs the L values of the Backward2 and the Forward RU and the values of the branch metrics1. The LLR function computes the ratio and it gives the reliability of each decoded bit. E) initialisation of the backward3 recursion We initialise each backward3 recursion thanks to the pointers values. Then, we compute the Backward3 values thanks to the "Recursion_Backward_Pt3" function. F) initialisation of the backward2 recursion We obtain the first value of the backward2 recursion thanks to the final_backward metric1 value. So: Backward2_MN [L-1] = final_backward_metric1 To compute the backward node metrics, we use the Recursion_Backward function and the branchmetrics2 values. Thanks to these values, we can define the pointers values. The first L/4 values of the backward metrics2 are stored in backward metrics3. Then, we update the final_backward_metric1 writing: final_backward_metric1 = final_backward_metric NOTICE: this initialisation begins if i>2. G) updating of the branchmetrics We have to updatete now the branchmetrics: tampon = branch_metrics1 branch_metrics1 = branch_metrics2 branch_metrics2 = branch_metrics3 branch_metrics3 = branch_metrics4 branch_metrics4 = tampon II) When the loop is finished: After the loop, you have to compute the last 2L bits between (count - 3L) and (count - L) using the same process but you don't need to follow all the steps. NOTICE: We cannot decode the last L bits.