1

Synthèse abstraite d’éléments de turbo décodeur en bloc pour un circuit reconfigurable

Caaliph ANDRIAMISAINA, Catherine DEZAN Christophe JEGO, Bernard POTTIER

par

Laboratoires Architectures et Systèmes LESTER-UBO et

TAMCIC ENST-Bretagne

2

Motivation

Modéliser 2 blocs d’un turbo décodeur BCH étendu (128,120,4)

Avoir un gain en compléxité et en temps de conception

Exploiter l’utilisation des corps de Galois

3

Plan

Turbo code en bloc

Madeo

Modélisation et synthèse de 2 fonctions du turbo décodeur en bloc BCH (128,120,4)2

4

Turbocode Construits par concaténation de 2 codes élémentaires

Gain de codage de 2 à 4 dB par rapport aux codes correcteurs d’erreurs classiques

Dans le cas des turbo codes en bloc, les codes concatenés sont des codes de types BCH ou RS

Construction d’un code BCH à partir des éléments du corps de Galois

5

Principe de décodage Décodage reposant sur un processus itératif Décodage des lignes suivi des décodages des

colonnes à l’aide d’un décodeur élémentaire EPSP Le décodeur élémentaire prend en entrées le mot

d’information du décodage précédent et le mot reçuDécodage des colonnes (demi-itération)

Décodage des lignes (demi-itération)

Décodage des colonnes (demi-itération)

Matrice reçue

Reconstruction de la matrice

Reconstruction de la matrice

Décodeur

Delay

+ * +R'k

Rk

Dk

Fk +- Wk

R'k+

6

Algorithme de décodage d'un turbocode en bloc BCH(128,120,4)2

Réception du mot R’k : 1 bit de signe et 4 bits de fiabilités

Recherche des symboles les moins fiables: 5 symboles les moins fiables parmi les 128 symboles

Construction des 16 vecteurs tests: à partir des inversions de bits les moins fiables

Calcul du syndrome du 1er vecteur de test

Calcul des syndromes pour les 15 autres vecteurs de test

Correction des 16 vecteurs de test

Calcul des métriques: distance euclidienne entre 2 mots

Séléction du mot décidé et des mots concurrents

Calcul de la nouvelle fiabilité de chacun des symboles du mot

Calcul de l'information extrinsèque: apportée par le décodeur

Addition avec le mot reçu du canal

7

Outil générique permettant de modéliser une architecture quelconque de FPGA

Outils basiques: placement-routage/floor-planner/éditeur

Deux parties: Madeo-FET/Madeo-BET

MADEO: chaîne de CAO pour les architectures reconfigurables

8

Flot de MADEO

Madeo-BET

Madeo-FET

9

Spécifications de l’application dans MADEO

Description initiale en Smalltatlk de l’application

Codes génériques pouvant s’utiliser avec des contextes différents: entiers, flottants, matrices, …

Exemple:

addprod: x with:y

^x*2 + (y*3)

x et y peuvent être des entiers, flottants

10

Modélisation du corps de Galois GF(2n)

Eléments pouvant être représentés par des polynômes de degré n-1.

Addition/soustraction modélisées en ou-exclusif Multiplication/division utilisent des tables de

logarithmes les transformant en addition/soustraction

Création d’une classe génératrice des corps de Galois GF(2n)

11

Modélisation du syndrome

Transformation de l’équation du calcul de syndrome:

α: éléments du corps de Galois GF(128) de polynôme générateur r’j: les bits du mot reçu n: nombre de bit de découpage

k: niveau d’hiérarchie

2 types de modélisations étudiées en fonction de k:

Modélisation à plat pour k=1

Modélisation hiérarchique pour k>1

137 xx

12

Exemple: Modélisation à plat k=1 et n=4

0 1 2 3 4 5 6 7 123 124 126 127

motRecu:

syndrome

motRecu: motRecu:

+

+

…………...

13

motRecu: r a0:a0 a1:a1 a2:a2 a3:a3| r0 r1 r2 r3 syndrome |

syndrome:= MonGF128 on: 0.r0:= (r bitAnd: 2r1000)~=0.r1:= (r bitAnd: 2r0100)~=0.r2:= (r bitAnd: 2r0010)~=0.r3:= (r bitAnd: 2r0001)~=0.r0 ifTrue: [syndrome:=syndrome + a0].r1 ifTrue: [syndrome:=syndrome + a1].r2 ifTrue: [syndrome:=syndrome + a2].r3 ifTrue: [syndrome:=syndrome + a3].^syndrome

entrée sur 4 bits

éléments du corps de Galois GF(128)

S1

motRecu:

0 1 2 3

Modélisation d'une somme partielle

14

2 types de comparaisons étudiées:

Type arbre arborescent:

• Plusieurs blocs de comparaison appelés dans chaque niveau• Chaque bloc de comparaison prenait en entrée des fiabilités et

leurs positions associées

Type tri à bulles:

• La comparaison se fait en poussant, vers la sortie par permutations successives, la plus petite valeur parmi les entrées

Modélisation de la recherche des 5 symboles les moins fiables

15

v1:v1 pos1:pos1 v2:v2 pos2:pos2v1>v2 ifTrue :[^Array with:v2 with:pos2]

ifFalse :[^Array with:v1 with:pos1]

v pos

0 1 2 3 4 5 6 7 123 124 126 127

.

.

.

Modélisation en Smalltalk:

Modélisation d'un bloc de comparaison

16

Optimisations et Synthèse

On a utilisé l’inférence de type simple avec les optimisations suivantes:

propagation des constantes suppression des codes morts no-op removal

Pour la synthèse, on a utilisé des architectures 4-LUT à une sortie

17

Résultats

fonctions ModélisationsDécoupages

(bits)

Tempsd’optimisation

et de synthèse

Nombres de

LUT

Syndrome

plat

2 (k=1,n=2) 2 mn 10 s 424

4 (k=1,n=4) 10 mn 217

8 (k=1,n=8) 2 h 23 mn 502

hiérarchique2 (k=8,n=2) 12 h 08 mn 725

4 (k=4,n=4) 13 h 30 mn 2311

Fiabilité

plat : arbre arborescen

t 2 (n=2) - 4117

plat : tri à bulles

2 (n=2) - 5234

18

Comparaison avec l’ENSTB

Fonctions Madeo ENSTB

Syndrome 217 LUT (k=1,n=4) 580 LUT

Fiabilité 4117 LUT (n=2)

896 comparaisons à 4 bits 508 décalages de 2 registres

Modélisation en SystemC dans CoCentric System Studio Pour le calcul de syndrome, l’ENSTB a adopté un traitement

parallèle des mots reçus. Pour la fiabilité, un traitement complètement séquentiel

19

Conclusions

La réduction de complexité dans Madéo est due essentiellement aux optimisations de haut niveau

Le gain pour le calcul de syndrome est surtout obtenu par propagation des éléments du corps de Galois

Les types d’applications à gros calculs offrent un contexte favorable d’utilisation de Madéo.

20

Perspectives

Appliquer le même mode de traitement sur d’autres applications en télécommunications

Implémenter les autres blocs du turbo décodeur