Christophe Jego

Patrick Adde

Camille Leroux

DATA TRANSMISSION USING FULL-PARALLEL BLOCK TURBO DECODER

Keywords: correcteur d'erreurs, Turbocodes en blocs, Décodage entièrement parallèle, Architecture à très haut débit Forward error correction, Block turbo codes, Full-parallel decoding, Ultra high-speed architecture

Cet article présente une nouvelle architecture atteignant de très haut débit pour le turbo décodage de codes produits. Ce type d'architecture est capable de décoder des codes produits reposant sur des codes binaires de type BCH ou des codes m_aire de type Reed Solomon. Son principal atout est qu'elle permet l'élimination des plans mémoires associés aux matrices générées par un code produit entre les différentes demi-itérations pour le turbo décodage. En fait, la solution architecturale que nous détaillons dans ce papier offre de nouvelles opportunités pour l'application des turbocodes dans des systèmes nécessitant des débits supérieurs au Gbit/s comme les systèmes de transmission sur fibre optique.

Sommaire

I. INTRODUCTION

Les codes correcteurs d'erreurs (codage canal) sont une des solutions permettant d'améliorer la qualité des communications numériques. Le principe du codage canal est d'introduire de la redondance dans la séquence d'information binaire afin de corriger les erreurs de transmission durant la réception de l'information. Deux grandes classes de code correcteur d'erreurs existent : les codes convolutifs et les codes en blocs. Au début des années 90, une nouvelle famille de code correcteur d'erreurs a été découverte par C. Berrou [START_REF] Berrou | Near Shannon limit error correcting coding and decoding: Turbo Codes[END_REF] : les turbocodes. Cette famille de codes correcteurs d'erreurs est construite par concaténation de codes élémentaires. Les turbocodes sont le résultat de deux innovations majeures : la concaténation de deux codes pour le codage et le décodage itératif. Le décodage itératif est appliqué à des décodeurs élémentaires à entrées et sorties pondérées (EPSP). Ce type de décodage est une solution qui fournit de bonnes performances tout en nécessitant un niveau de complexité raisonnable. Le concept général de décodage itératif appliqué à des décodeurs élémentaires EPSP a ensuite été appliqué aux codes produits [START_REF] Pyndiah | Near optimum decoding of product codes[END_REF] et aux codes LDPC [START_REF] Gallager | Low Density Parity Check Codes[END_REF]. De plus, le principe turbo a été étendu à l'ensemble des fonctionnalités constituant le récepteur d'un système de communications numériques telles que la turbo-détection dans les domaines des canaux sélectifs en fréquence ou des canaux MIMO, la turbo-égalisation ou la turbo-modulation.

Depuis le début des années 2000, les turbocodes ont été adoptés par de nombreuses applications. Ce type de codes est par exemple particulièrement intéressant pour les systèmes de communications cellulaires. Les turbocodes font ainsi partie intégrante des normes UMTS, CDMA2000, DVB-RCS, IEEE802. [START_REF] Adde | Module, dispositif et procédé de décodage à haut débit, d'un code concaténé[END_REF] et HyperMAN. Ils favorisent l'augmentation des débits de transmission et l'amélioration de la qualité de service. Par ailleurs, des études sont actuellement en cours pour introduire des turbocodes dans des systèmes de stockage de l'information tels que les disques durs ou les DVD ou dans des systèmes de transmission sur fibre optique. Dans un contexte d'évolution vers le haut débit, la transmission sur fibre optique est une technologie de pointe qui favorise l'évolution de l'infrastructure de desserte des contenus. Les codes correcteurs d'erreurs sont utilisés dans les systèmes de communication optiques pour corriger la dégradation en terme de taux d'erreur binaire due aux phénomènes de dispersion et de non-linéarité de la fibre optique. Les premiers codes correcteurs d'erreurs utilisés dans les communications optiques [START_REF] Azadet | Equalization and FEC techniques for optical transceivers, Solid-State Circuits[END_REF] sont les codes Reed Solomon. Par exemple, la norme ITU-T G.709 [START_REF]Interface ofr the Optical Transport Networks[END_REF] (18 réf.) capacité de correction maximale est de 8 octets et la capacité de détection est de 16 octets. Dans ce cas, le gain de codage est alors d'environ 6 dB. Ces dernières années d'autres codes correcteurs d'erreurs plus puissants ont été proposés pour améliorer le gain de codage. Parmi eux, les turbocodes en blocs ont un gain de codage potentiel autour de 10 dB [START_REF] Ait Sab | Block turbo code performances for long-haul DWDM optical transmission systems[END_REF][START_REF] Mizuochi | Recent Progress in Forward Error Correction for Optical Communication Systems[END_REF]. Typiquement, les turbocodes en blocs ont des performances se situant environ à 1 dB de la limite de Shannon.

Les nouvelles générations de réseaux d'accès optique qui se caractérisent par une montée en débit en ligne impliquent l'implémentation d'architectures de codes correcteurs d'erreurs atteignant des débits très élevés. Des solutions architecturales de décodeur Reed Solomon (255, 239) ont été proposées pour des débits de 40 Gbit/s [START_REF] Song | 10-and 40-Gb/s forward error correction devices for optical communications[END_REF] et de 80 Gbit/s [START_REF] Lee | A high-speed low-complexity Reed-Solomon decoder for optical communications, Circuits and Systems II : Express Briefs[END_REF]. En 2002, une nouvelle architecture pour le turbo décodage de codes produits a été présentée [START_REF] Cuevas | New architecture for high data rate turbo decoding of product codes[END_REF]. Cette solution architecturale permet d'atteindre des débits autour de 6 Gbit/s. En 2005, Mitsubishi Electric a annoncé le développement d'un circuit de turbo décodage de codes produits pour des transmissions optiques à 10 Gbit/s [START_REF] Tagami | A 3-bit soft-decision IC for powerful forward error correction in 10-Gb/s optical communication systems, Solid-State Circuits[END_REF]. Dans ce contexte, nous présentons dans cet article, un nouveau type d'architecture pour le turbo décodage de codes produits. Ce type d'architecture élimine les plans mémoires associés aux matrices générées par le code produit. En effet dans les architectures traditionnelles, des plans mémoires sont nécessaires pour sauvegarder les informations échangées au cours des itérations du processus de turbo décodage. Ainsi, les architectures obtenues traitent des données à très haut débit pouvant dépasser le 10 Gbit/s avec une latence d'exécution bien inférieure aux architectures proposées jusqu'alors. Enfin, il est à noter que ce type d'architecture peut s'appliquer pour le turbo décodage de codes produits utilisant des codes binaires de type BCH ou des codes m_aire de type Reed Solomon [START_REF] Piriou | Efficient Architecture For Reed Solomon Block Turbo Code[END_REF].

Dans une première partie, nous allons rappeler le principe de turbo décodage des codes produits. Puis, nous présentons un état de l'art sur les architectures de turbo décodeurs dédiées aux codes produits. Nous détaillons ensuite notre solution architecturale reposant sur un turbo décodage entièrement parallèle. De plus, le lecteur peut consulter la référence [13] qui décrit brièvement le principe sur lequel repose notre approche. Enfin, nous proposons une architecture de turbo décodeur de codes produits pour le très haut débit (>10 Gbit/s). Cette solution architecturale repose sur un traitement entièrement parallèle que nous allons détailler mais également sur les précédentes innovations architecturales proposées par l'ENST Bretagne à savoir le traitement pipeline au sein du turbo décodeur [START_REF] Kerouedan | How we implemented Block Turbo Codes[END_REF] et le traitement simultané de plusieurs symboles d'une ligne ou d'une colonne au sein du décodeur élémentaire [START_REF] Cuevas | New architecture for high data rate turbo decoding of product codes[END_REF].

II. LE TURBO DÉCODAGE DES CODES PRODUITS

Un code produit est un code performant obtenu à partir de deux codes en blocs simples ayant de faibles distances de Hamming minimales δi. En effet, sa distance de Hamming minimale est alors égale au produit des distances de Hamming minimales des codes élémentaires utilisés, et son rendement au produit des rendements élémentaires.

Si on considère deux codes en blocs élémentaires C 1 (n De manière générale, les informations échangées d'une demi-itération à une autre sont définies par le schéma suivant : R k correspond à l'information reçue du canal, R′ k à l'information qui vient de la demi-itération précédente et R′ k + à l'information envoyée à la demi-itération suivante. La sortie de chaque demi-itération est donc égale à R k plus l'information extrinsèque, W k multipliée par alpha. Cette information extrinsèque correspond à l'apport du décodeur. Elle est obtenue par différence entre la sortie pondérée F k du décodeur et l'entrée pondérée de ce même décodeur.

Nous considérons par la suite le décodeur à entrées et sorties pondérées comme un bloc ayant R k et R′ k (échantillonnés sur q bits) comme entrées, délivrant R′ k + et R k (échantillonnés sur q bits) à la sortie avec une certaine latence L (retard nécessaire pour mettre en oeuvre l'algorithme de décodage). Il prend le nom d'Unité de Traitement (UT). La structure interne du décodeur à entrées et sorties pondérées n'influence pas directement la structure du turbo décodeur. C'est pourquoi, nous ne présentons pas dans ce papier l'algorithme de Chase-Pyndiah et l'architecture associée que nous utilisons. Cependant, le lecteur peut le cas échéant consulter les références [START_REF] Pyndiah | Near optimum decoding of product codes[END_REF][START_REF] Kerouedan | How we implemented Block Turbo Codes[END_REF][START_REF] Pyndiah (r.) | Block Turbo Codes : Ten years later[END_REF] qui traitent de ces aspects.

En considérant une autre découpe de ce schéma bloc, R′ k peut être remplacé par W k qui devient entrée-sortie du bloc : R′ k est alors variable interne.

III. ÉTAT DE L'ART SUR LES ARCHITECTURES DE TURBO DÉCODEURS DE CODE PRODUIT

L'intégration d'un turbo décodeur peut être effectuée selon deux techniques :

• Technique séquentielle : structure où le décodeur élémentaire et le plan mémoire sont utilisés pour la totalité des demi-itérations ; • Technique pipeline : structure où un décodeur élémentaire et un plan mémoire sont utilisés pour chaque demi-itération.

Dans la suite de ce document, nous faisons des comparaisons entre les différentes architectures. Une des caractéristiques retenues pour les comparer est la latence introduite par l'architecture. Classiquement, la latence se définie comme le retard temporel induit par l'architecture entre ses entrées et ses sorties. Dans notre contexte, cette définition ne permet pas une comparaison entre les techniques séquentielle et pipeline. En effet, la latence doit être inférieure à une valeur pour la technique séquentielle. Cette valeur est indépendante de l'architecture de décodage comme nous allons le voir par la suite. Il s'agit alors plutôt d'une contrainte temporelle pour l'architecture de décodage. Par contre, l'expression de la latence pour la technique pipeline est directement dépendante de l'architecture de décodage. En fait, la comparaison possible entre les deux techniques concerne le nombre symboles considérés au cours du traitement complet d'un symbole. C'est la raison pour laquelle, nous avons choisi de définir la latence comme étant le nombre de symboles traités par le turbo décodeur avant qu'un nouveau symbole présent en entrée de l'architecture soit à son tour complètement traité.

III.1. Architecture séquentielle pour le turbo décodage

Dans ce type d'architecture, le circuit réalise l'ensemble des demi-itérations à partir d'un décodeur élémentaire et d'un plan mémoire. Un bouclage sur la structure de base est nécessaire comme indiqué sur la figure 5.

L'intérêt principal de cette architecture est le faible encombrement du turbo décodeur. Le circuit complet comporte un plan mémoire composé de quatre mémoires de taille qn 1 n 2 bits indépendamment du nombre d'itérations effectuées. Deux des quatre mémoires fonctionnent en mode lecture, les deux autres fonctionnent en mode écriture. Il y a une inversion des modes de fonctionnement (lecture/écriture) des mémoires R ′ k entre chaque demi-itération. Pour les mémoires R k , l'inversion du mode de fonctionnement intervient à la réception d'une nouvelle matrice d'information. Les mémoires sont des RAM classiques accessibles par adressage suivant les lignes et les colonnes.

Le décodage à partir de cette structure consiste à faire un décodage à entrées et à sorties pondérées de toutes les lignes puis de toutes les colonnes de la matrice C. Ce processus est réitéré autant de fois que nécessaire (fonction du nombre de demi-itérations). La latence globale (telle que nous l'avons définie) de l'architecture séquentielle est au maximum de :

(1)

L atence = 2*n 1 n 2
Les n 1 n 2 premiers symboles sont considérés lors du remplissage d'une matrice de données et les n 1 n 2 symboles suivants sont considérés lors du traitement itératif de cette matrice. Dans ce cas, la latence est une contrainte qui fixe en particulier le nombre maximum d'itérations possibles dans la configuration retenue pour l'architecture.

L'inconvénient majeur de l'architecture séquentielle pour le turbo décodage de code produit est le débit de traitement des données. En effet, le débit doit tenir compte de l'utilisation d'une structure de base (un décodeur élémentaire et un plan mémoire) pour toutes les demiitérations. Le débit maximal de traitement des données pour le turbo décodeur est donc au plus égal au débit de traitement d'un décodeur élémentaire divisé par le nombre de demiitérations. C'est pourquoi l'architecture séquentielle permet un débit de traitement des données limité. L'utilisation de cette architecture séquentielle dans un contexte haut débit est par conséquent impossible en l'état.

III.2. Architecture pipeline pour le turbo décodage

La technique pipeline pour l'intégration d'un turbo décodeur repose sur une architecture modulaire. Dans ce type d'architecture, un décodeur élémentaire et un plan mémoire sont associés. Cette structure de base est alors mise en cascade comme indiqué sur la figure 6.

L'architecture finale est donc constituée d'autant de structures de base (association décodeur élémentaire et plan mémoire) que de demi-itérations. Chaque plan mémoire est composé de quatre mémoires de taille qn 1 n 2 bits. Le fonctionnement des différentes mémoires est similaire au fonctionnement d'une architecture séquentielle (cf. III.1.). En fait, l'inconvénient majeur de l'architecture pipeline pour le turbo décodage de code produit est l'encombrement du turbo décodeur. En effet, la mise en cascade des structures de base peut rendre cette solution architecturale très coûteuse lorsque le nombre d'itérations augmente, suivant la longueur du code produit retenu et/ou suivant le pouvoir de correction.

Le décodage à partir d'une structure pipeline consiste à faire un décodage à entrées et à sorties pondérées de toutes les lignes ou de toutes les colonnes d'une matrice pour chacune des demi-itérations. Par exemple pour it itérations, l'architecture du turbo décodeur contient 2it décodeurs élémentaires et 8it mémoires de taille qn 1 n 2 bits. Dans ce cas, l'encombrement du circuit provient en grande partie des blocs mémoires. En effet, il est indispensable de (2)

L atence = {(n 1 n 2 *2it) + it*(L 1 + L 2 )} pour it itérations
L'intérêt de l'architecture pipeline est le débit de traitement des données. En effet, le débit obtenu est le débit de traitement d'un décodeur élémentaire. Cependant, elle entraîne un accroissement de l'encombrement du circuit de turbo décodage.

III.3. Architecture haut débit pour le turbo décodage

Les limitations en terme de débit de traitement des données se situent dans les décodeurs élémentaires pour les architectures de turbo décodage de code produit. Une solution pour augmenter le débit est de permettre au décodeur de traiter plusieurs symboles d'une ligne ou d'une colonne simultanément. Une solution architecturale reposant sur ce constat a été proposée dans le brevet de P. Adde et R. Pyndiah [START_REF] Adde | Module, dispositif et procédé de décodage à haut débit, d'un code concaténé[END_REF]. Nous décrivons dans la suite de ce paragraphe cette solution architecturale. L'idée principale est d'augmenter le débit de traitement des données tout en conservant une même vitesse de fonctionnement pour le plan mémoire. La solution consiste alors à mémoriser plusieurs données à la même adresse. Il faut, cependant, pouvoir utiliser ces données aussi bien suivant les lignes que les colonnes. C'est pourquoi une organisation particulière de l'accès à la mémoire est nécessaire. Considérons, par exemple, deux lignes adjacentes et deux colonnes adjacentes dans la matrice initiale.

Les quatre symboles (i, j), (i, j + 1), (i + 1, j) et (i + 1, j + 1) constituent alors une donnée de la nouvelle matrice qui a quatre fois moins d'adresses (I, J) mais des données quatre fois plus grandes. Pour le décodage ligne, les échantillons (i, j), (i, j + 1) sont affectés à un décodeur élémentaire DEC1, (i + 1, j) et (i + 1, j + 1) à un décodeur élémentaire DEC2. Pour le décodage colonne, il faut prendre (i, j), (i + 1, j) pour DEC1 et (i, j + 1), (i+1, j + 1) pour DEC2. Si les décodeurs élémentaires savent traiter en entrée (lecture de la RAM) et en sortie (écriture de la RAM) ces couples de symboles simultanément, alors le débit de traitement des données de la matrice sera quatre fois plus rapide que pour le décodeur classique. Le coût matériel de cette solution architecturale implique l'utilisation de deux décodeurs élémentaires traitant simultanément un couple de symboles d'une donnée de la matrice dans l'exemple considéré.

IV. ARCHITECTURES PARALLÈLES DE TURBO DÉCODEUR

Dans cette partie, nous présentons un nouveau type d'architecture pour les turbo décodeurs de code produit. Ce type d'architecture élimine les plans mémoires associés aux données du code produit entre les différentes demi-itérations. Il permet aussi de traiter des données à des débits bien supérieurs à ceux des architectures précédentes (cf partie III). Enfin, la latence d'exécution de ce type d'architecture est fortement réduite.

IV.1. Principe du décodage parallèle d'un code produit

Un code produit est un code performant obtenu à partir de deux codes en blocs simples ayant de faibles distances de Hamming minimales δi. En effet, sa distance de Hamming minimale est alors égale au produit des distances de Hamming minimales des codes élémentaires utilisés, et son rendement au produit des rendements élémentaires.

Si on considère deux codes en blocs élémentaires C 1 (n 1 , k 1 ) et C 2 (n 2 , k 2 ), le code produit se présente sous forme de matrice C à n 1 lignes et n 2 colonnes.

Le décodage d'un tel code consiste à faire un décodage à entrées et à sorties pondérées de toutes les lignes puis de toutes les colonnes de la matrice C. Le décodage des n 2 mots de code suivant les colonnes est réalisé après un décodage de l'ensemble des n 1 mots de code suivant les lignes dans les solutions architecturales existantes. Cette approche nécessite l'utilisation d'un plan mémoire entre le décodage ligne et le décodage colonne. La latence de l'architecture séquentielle est au maximum de 2*n 1 n 2 (cf paragraphe III.1) et celle d'une architecture pipeline est de {(n 1 n 2 *2t) + it*(L 1 + L 2 )} pour it itérations (cf paragraphe III.2).

Or, les n 1 lignes et les n 2 colonnes correspondent respectivement à n 1 et n 2 mots de code indépendants. C'est pourquoi le décodage des n 1 mots de code peut être effectué en parallèle si des ressources matérielles (décodeurs élémentaires) sont disponibles. De même, il est possible d'effectuer le décodage des n 2 mots de code en parallèle. Enfin, il est à noter que le traitement des symboles constituant un mot de code n'a pas d'ordre particulier. Il est juste nécessaire de traiter l'ensemble des symboles en repérant le symbole de parité lors du décodage.

En tenant compte de l'ensemble de ces propriétés, nous proposons un traitement parallèle de la matrice C. Pour chaque traitement de la matrice suivant les lignes ou les colonnes, tous les mots de code sont décodés en parallèle. Pour cela, nous supposons que nous disposons du nombre adéquat de décodeurs élémentaires.

De plus, si nous disposons des ressources matérielles pour décoder l'ensemble des lignes et des colonnes d'une matrice C, alors il devient possible de commencer le décodage des colonnes dès que des symboles composant les mots de code des lignes ont été traités. L'objectif est alors d'éliminer les plans mémoires. Or un traitement particulier de la matrice permet cette élimination. Nous allons dans la suite de ce paragraphe expliciter ce traitement en considérant tout d'abord une matrice carrée C à n lignes et n colonnes. Une généralisation de l'approche sera ensuite fournie pour une matrice C à n 1 lignes et n 2 colonnes. Nous définissons la latence d'un décodeur élémentaire comme le nombre de symboles traités par le décodeur avant qu'un nouveau symbole présent en entrée du circuit soit à son tour complètement traité. Cette latence dépend de la structure du décodeur élémentaire et en particulier du nombre x de mots de code traités en pipeline. Dans le cas de la matrice 8*8, la latence des décodages lignes ou colonnes est de 8x symboles. Enfin, la latence entre le décodage des lignes et le décodage des colonnes est nulle (absence de plan mémoire).

Généralisation : Si nous considérons deux codes en blocs élémentaires identiques C(n, k, δ), le code produit se présente sous forme d'une matrice C à n lignes et n colonnes. Si nous disposons de 2n décodeurs, il est possible de décoder n lignes et n colonnes en parallèle. Pour ce faire, si i est l'indice compris entre 1 et n des décodeurs lignes, alors un décodeur i commence le traitement d'un mot de code par le i ème symbole de ce mot de code. De plus, chaque décodeur ligne i traite les symboles d'un mot de code en incrémentant l'indice (i modulo n) associé aux symboles. La latence de décodage de la matrice C est alors de L = xn symboles.

De même, si j est l'indice compris entre 1 et n des décodeurs colonnes, alors un décodeur j commence le traitement d'un mot de code par le j ème symbole de ce mot de code. Par contre, chaque décodeur colonne j traite les symboles d'un mot de code en décrémentant l'indice (j modulo n) associé aux symboles. La latence de décodage de la matrice C est alors de L=xn symboles.

Enfin, si nous considérons une itération complète, la latence de décodage de la matrice C suivant les lignes puis les colonnes est de 2L symboles.

IV.1.2. Décodage parallèle d'une matrice C à n 1 lignes et n 2 colonnes

L'un des objectifs du décodage parallèle d'une matrice C est d'éliminer les plans mémoires. Cela implique d'avoir autant de décodeurs pour les lignes que pour les colonnes. Si les nombres de lignes et de colonnes d'une matrice C sont différents, alors il suffit de prendre 2n min décodeurs élémentaires tel que :

Généralisation : Si nous considérons deux codes en blocs élémentaires C

1 (n 1 , k 1 , δ 1 ) et C 2 (n 2 , k 2 , δ 2 )
, le code produit se présente sous forme d'une matrice C à n 1 lignes et n 2 colonnes.

Si nous disposons de 2n min décodeurs tel que n min = min(n 1 , n 2 ), il est possible de décoder n min lignes et n min colonnes en parallèle.

Pour ce faire, si i est l'indice compris entre 1 et n min des décodeurs lignes, alors un décodeur i commence le traitement d'un mot de code par le i ème symbole de ce mot de code. De plus, chaque décodeur ligne i traite les symboles d'un mot de code en incrémentant l'indice (i modulo n min ) associé aux symboles. La latence de décodage de la matrice C est alors de L 1 =xn 2 symboles.

De même, si j est l'indice compris entre 1 et n min des décodeurs colonnes, alors un décodeur j commence le traitement d'un mot de code par le j ème symbole de ce mot de code. Par contre, chaque décodeur colonne j traite les symboles d'un mot de code en décrémentant l'indice (j modulo n min ) associé aux symboles. La latence de décodage de la matrice C est alors de L 2 =xn 1 symboles.

Enfin, si nous considérons une itération complète, la latence de décodage de la matrice C suivant les lignes puis les colonnes est de L 1 + L 2 symboles.

IV.2. Application pour le turbo décodage des codes produits

Nous avons décrit dans le paragraphe précédent notre technique de décodage parallèle des codes produits. Cette technique peut être appliquée comme nous allons le voir à toutes les architectures de turbo décodeurs de code produit.

IV.2.1. Gestion des données de la matrice C entre les itérations

L'un des avantages de la technique de décodage parallèle des codes produits que nous proposons, est d'éliminer les plans mémoires associés aux matrices générées par un code produit entre les différentes demi-itérations. Une gestion de la communication des symboles des différents mots de code de la matrice entre le décodage des lignes et des colonnes est alors nécessaire. Une solution triviale consiste à placer un réseau d'interconnexion entre les décodeurs des lignes et des colonnes comme indiqué sur la figure 10.

Ce réseau d'interconnexion peut être matérialisé par de simples liaisons point à point ou par un réseau de type Crossbar. Cependant, nous proposons d'insérer un réseau d'interconnexion dynamique multi-étages de type Omega [START_REF] Lawrie | Access and alignment of data in an array processor[END_REF]. Un réseau dynamique est un réseau dont la topologie de connexion varie au cours du temps. Ce type de réseau répond à notre problématique car les symboles traités par les décodeurs élémentaires sont ensuite répartis sur l'ensemble des décodeurs de la demi-itération suivante selon un profil de communication de type permutation circulaire. De plus, le réseau d'interconnexion de notre architecture doit traiter n min communications simultanément. Cette caractéristique est un cas de figure typique d'un réseau dynamique. Le réseau dynamique que nous avons retenu est de type multiétages. L'intérêt de cette structure par rapport à une solution à base de liaisons point à point ou de type Crossbar est la limitation des connexions et des commutateurs. En effet, dans les réseaux multi-étages le nombre de liaisons et le nombre de commutateurs évoluent de manière logarithmique : Le débit de l'architecture parallèle séquentielle est intéressant. En effet, il est n min fois plus élevé que celui de l'architecture séquentielle classique. De plus, le débit peut encore être multiplié par deux si l'architecture est séquentielle au niveau itération (cf figure 13). Néanmoins, l'utilisation de l'architecture séquentielle parallèle dans un contexte très haut débit (> 10 Gbit/s) est impossible en l'état.

IV.2.3. Architecture pipeline parallèle

La technique pipeline pour l'intégration d'un turbo décodeur repose sur une architecture modulaire. Dans une architecture pipeline parallèle, 2n min décodeurs élémentaires et deux réseaux d'interconnexion sont associés. La structure permet le décodage de la matrice C suivant les lignes puis les colonnes. Cette structure de base est alors mise en cascade comme indiqué sur la figure 14.

L'architecture finale est donc constituée d'autant de structures de base (association de 2n min décodeurs élémentaires et deux réseaux d'interconnexion) que d'itérations. Cette solution architecturale ne nécessite alors au maximum que quatre mémoires de taille qn 1 n 2 bits. De plus, si le module de réception associé au turbo décodeur a des bus de transferts de données appropriés en entrée et/ou en sortie de l'architecture, alors certaines mémoires peuvent être supprimées. Au final, cette architecture pipeline parallèle a un encombrement qui dépend de la taille de la matrice C. En effet, 2n min décodeurs élémentaires sont nécessaires pour chaque itération. C'est pourquoi l'encombrement du circuit final peut s'avérer coûteux si la taille de la matrice à décoder est importante.

Le décodage à partir d'une structure pipeline parallèle consiste à faire un décodage à entrées et à sorties pondérées de toutes les lignes ou de toutes les colonnes d'une matrice pour chacune des demi-itérations selon le principe décrit dans le paragraphe IV.1. Dans ce cas, l'encombrement du circuit concerne essentiellement les décodeurs élémentaires. La complexité due aux plans mémoires est bien moindre que pour la solution architecturale pipeline classique. De plus, comme la mémorisation des matrices R k (information reçue du canal), R' k (information qui vient de la demi-itération antérieure) et R' k + (information envoyée à la demi-itération suivante) n'est plus nécessaire entre les demi-itérations, la latence globale est également bien moins importante. Nous définissons la latence globale comme le nombre de symboles traités par le turbo décodeur avant qu'un nouveau symbole présent en entrée du circuit soit à son tour complètement traité. La latence d'une itération complète est de (L 1 +L 2 ) symboles (cf paragraphe IV.1). La latence de traitement de la matrice C pour it itérations de ce type d'architecture est donc de : L'atout indéniable de l'architecture que nous proposons est le débit pouvant être atteint. Il est désormais possible d'intégrer des circuits de turbo décodeur de code produit ayant des débits supérieurs à 10 Gbit/s. Ainsi, le gain en débit est d'un facteur (n min /k)*k 2 par rapport à une architecture pipeline classique. De plus, ce gain en débit demeure élevé (n min /k) par rapport à la solution architecture pipeline proposée dans le brevet de P. Adde et R. Pyndiah. C'est pourquoi nous affirmons proposer une architecture de turbo décodeur de code produit pour les très hauts débit.

Pour illustrer l'apport de notre proposition d'architecture parallèle, nous allons comparer les performances pour un turbo décodeur étudié dans la thèse de J. Cuevas [START_REF] Cuevas | Turbo Décodage de Code Produit Haut Débit[END_REF]. Il s'agit du turbo décodeur de code produit utilisant deux codes BCH étendus (32,26,4). Le tableau I donne les performances en terme de débit et de latence de traitement du décodage de la matrice 32*32 pour une demi-itération. La complexité en nombre de portes logiques est également fournie. Il est à noter que pour les décodeurs haut débit et très haut débit, les décodeurs élémentaires traitent quatre symboles simultanément (4-UT). La technologie d'intégration est la CMOS 0,09 µm de chez STMicroelectronics. TABLEAU I. -Principales caractéristiques des différentes architectures pour une demi-itération.

Features of different architectures for a half-interation.

Nous constatons sur cet exemple que le débit de notre solution architecturale (12,8 Gbit/s) est 128 fois plus important que le débit de référence. De plus, ce débit est 8 fois plus élevé que celui obtenu par l'architecture de la thèse de J. Cuevas. La latence quant à elle, est divisée par quatre. Le coût matériel induit par notre proposition au niveau des décodeurs élémentaires est 64 fois plus élevé que l'architecture de référence et 8 fois plus élevé que l'architecture de la thèse de J. Cuevas

VI. BILAN RÉCAPITULATIF DES DIFFÉRENTES ARCHITECTURES POSSIBLES

Dans ce dernier paragraphe, nous dressons un bilan récapitulatif des architectures de turbo décodeur de code produit. Nous comparons les performances en terme de latence, de débit et de complexité des différentes solutions. Nous considérons deux familles d'architecture : les architectures classiques et les architectures parallèles. La famille des architectures classiques correspond à l'état de l'art sur les architectures de turbo décodeur de code produit. Elle se compose des architectures séquentielles et pipelines. Pour les structures pipelines, nous différencions les architectures composées de décodeurs élémentaires 1-UT ou k-UT. La famille des architectures parallèles correspond quant à elle aux architectures obtenues en appliquant la technique novatrice de décodage parallèle que nous avons décrit dans ce document. La définition des performances des différentes architectures dépend d'un certain nombre de grandeurs caractéristiques telles que :

n 1 : nombre de lignes de la matrice C, n 2 : nombre de colonnes de la matrice C, n min : minimum entre les nombres n 1 et n 2 , it : nombre d'itérations dans le processus turbo, q : nombre de bits de quantification des symboles de la matrice C, k : nombre de symboles d'une ligne ou d'une colonne traitée simultanément, x : nombre de mots de code traités en parallèle dans l'architecture pipeline, -L 1 = xn 2 : latence de décodage d'une ligne de la matrice C, -L 2 = xn 1 : latence de décodage d'une colonne de la matrice C.

Le tableau II est un tableau récapitulatif qui met en évidence les performances de la famille des architectures parallèles en terme de latence et de débit. De plus, cette famille élimine les plans mémoires associés aux matrices de données d'un code produit entre les demi-itérations pour les structures pipelines. Cette élimination des plans mémoires implique l'utilisation d'un réseau d'interconnexion entre les demi-itérations. Cependant, nous avons proposé une solution triviale et peu coûteuse en terme de complexité pour le réseau d'interconnexion. Naturellement, ces résultats ont un coût qui est la complexité au niveau des décodeurs élémentaires. Néanmoins, le coût matériel du Mbit/s pour les architectures parallèles est identique à celui des architectures classiques équivalentes.

TABLEAU II. -Récapitulatif des différentes architectures possibles.

Summary of all architectures.

Remarque : comme un décodeur élémentaire k-UT a une complexité environ k/2 fois plus importante qu'un décodeur élémentaire 1-UT d'après [START_REF] Cuevas | Turbo Décodage de Code Produit Haut Débit[END_REF], nous ajoutons un facteur k/2 dans le nombre de décodeurs élémentaires quand les décodeurs élémentaires k-UT sont utilisés.

VII. CONCLUSION

Nous avons décrit dans cet article un nouveau type d'architecture de décodage des codes produits à faible latence, pouvant fonctionner à très haut débit. Ces architectures reposent sur une technique de traitement parallèle suivant les lignes et les colonnes de la matrice du code produit. Le principe de traitement parallèle de la matrice du code produit constitue l'innovation majeure de notre proposition. Pour le turbo décodage, nous avons montré comment cette proposition peut s'appliquer aux solutions architecturales séquentielles et pipelines. Ainsi, le turbo décodage parallèle permet d'augmenter le débit de traitement des données tout en diminuant la latence globale du circuit de turbo décodage. De plus, cette approche élimine les plans mémoires entre les demi-itérations pour les architectures pipelines. Enfin, si nous appliquons notre technique de turbo décodage parallèle aux architectures décrites dans le brevet déposé par P. Adde et R. Pyndiah, les circuits de turbo décodeurs résultants peuvent atteindre des débits supérieurs à 10 Gbit/s. Un premier circuit de turbo décodage a été intégré sur une carte de prototypage contenant un FPGA Virtex II-Pro. Le turbo décodeur en question traite le code produit BCH(16,11) 2 . Il a été validé dans un environnement fonctionnant à 2,4 Gbit/s pour le débit en entrée et avec une fréquence de fonctionnement de 37,5 MHz pour le turbo décodeur. Cette première expérimentation a permis de valider le principe de traitement parallèle de la matrice du code produit. De plus, une étude visant à proposer un circuit de turbo décodage sur une cible FPGA pour la couche physique des réseaux d'accès optique ayant un débit ligne de 10 Gbit/s est en cours.

Manuscrit reçu le 26

-

  FIG 1. -Principe des codes produits.Principle of product codes.

  mémoriser les matrices R k (information reçue du canal) et R' k (information qui vient de la demi-itération antérieure). Pour ce type d'architecture, la latence est là encore définie comme le nombre de symboles traités par le turbo décodeur avant qu'un nouveau symbole présent en entrée du circuit soit à son tour complètement traité. Dès lors, la latence introduite par l'architecture pipeline est n 1 n 2 + L i symboles par demi-itération. Dans cette expression, les n 1 n 2 premiers symboles sont considérés lors du remplissage d'une matrice de données et les L i symboles suivants sont considérés lors du décodage proprement dit d'un symbole d'une ligne (L 1 = xn 2 ) ou d'un symbole d'une colonne (L 2 = xn 1 ) de cette matrice. La latence de décodage L i d'un symbole au sein d'un décodeur élémentaire dépend directement de sa structure interne. En fait, il s'agit d'un multiple x du nombre n 2 de symboles d'une ligne ou du nombre n 1 de symboles d'une colonne. La latence globale introduite par l'architecture pipeline est donc de :

  En généralisant, si une donnée de la nouvelle matrice contient m symboles d'une ligne et l symboles d'une colonne, le temps de traitement de la matrice est m.l fois plus rapide avec seulement m décodeurs élémentaires pour le traitement des lignes lors d'une demi-itération et l décodeurs élémentaires pour le traitement des colonnes lors d'une demi-itération. Si les codes C 1 et C 2 sont identiques, les « décodeurs lignes » et les « décodeurs colonnes » le sont aussi : alors, m = l et m décodeurs élémentaires sont nécessaires. Cette organisation des matrices de données ne requiert pas d'architectures de mémoires particulières, ni une horloge plus rapide. En fait, seul l'adressage de la mémoire est différent. La complexité matérielle de la solution triviale, consistant à décoder m 2 bits en parallèle, est de m 2 décodeurs élémentaires. Dans la solution architecturale proposée, la complexité matérielle du nouveau décodeur élémentaire est d'environ m/2 fois celle du décodeur élémentaire précédent [10]. Ainsi, une complexité de m 2 /2 décodeurs élémentaires permet l'obtention d'une vitesse m 2 fois plus élevée. Enfin pour une taille identique, la mémoire comporte m 2 fois moins de données que la matrice initiale C. A technologie équivalente, son temps d'accès sera donc moindre.

IV. 1 . 1 .

 11 FIG 8. -Les 64 symboles de la matrice 8*8. 64 symbols of the matrix 8*8.

( 3 ) n min = min(n 1 , n 2 )

 312 FIG 9. -Les 128 symboles de la matrice 8*16. 128 symbols of the matrix 8*16.

( 4 )IV. 2 . 2 .

 422 FIG 11. -Exemple de communication entre les décodeurs lignes et colonnes avec un réseau d'interconnexion dynamique multi-étages de type Omega.Communication example between row and column decoders with a multi-stages dynamical connection network Omega.

( 7 )

 7 L atence = (L 1 +L 2 )*it pour it itérations L'avantage principal de l'architecture pipeline parallèle est le débit de traitement des données qui peut être atteint. En effet, le débit obtenu est le débit de traitement d'une structure de base. Ce débit est n min supérieur à celui d'une architecture pipeline classique. De plus, il est possible d'augmenter encore ce débit en utilisant le principe du brevet décrit dans le paragraphe III.3. V. PROPOSITION D'UNE ARCHITECTURE PARALLÈLE DE TURBO DÉCODEUR DE CODE PRODUIT POUR LE TRÈS HAUT DÉBIT L'un des apports du brevet déposé par P. Adde et R. Pyndiah est d'augmenter le débit de traitement des données tout en conservant une fréquence constante pour le plan mémoire et le décodeur. Le décodeur élémentaire peut alors traiter plusieurs symboles d'un mot de code de la matrice simultanément. Dans la suite du document, nous utiliserons la notation k-UT pour indiquer que le décodeur élémentaire traite k données d'une même ligne (ou d'une même colonne) simultanément. Dès lors, des architectures de turbo décodeur de code produit de faible latence pour le très haut débit sont possibles. Pour ce faire, l'architecture du turbo décodeur doit permettre un traitement parallèle des différents mots de code de la matrice selon le principe que nous avons proposé. De plus, les décodeurs élémentaires doivent être capables de traiter plusieurs symboles d'un mot de code simultanément. Une architecture ayant ces propriétés est présentée dans la figure 15. L'architecture proposée comprend autant de structures de base (association de 2n min /k décodeurs et de deux réseaux d'interconnexion) que d'itérations. Chaque décodeur k-UT se décompose en k décodeurs élémentaires capables de traiter simultanément k symboles d'un même mot de code. Au final, la complexité en terme de nombre de décodeurs élémentaires est similaire à celle d'une structure pipeline parallèle pipeline classique, c'est-à-dire 2n min décodeurs élémentaires par itération. Cependant, la complexité du décodeur élémentaire k-UT est environ k/2 fois supérieure à celle d'un décodeur élémentaire classique 1-UT. Cette solution architecturale ne nécessite alors au maximum que quatre mémoires de taille qn 1 n 2 bits. L'encombrement du circuit final est essentiellement dû à l'encombrement des décodeurs élémentaires. Cet encombrement peut s'avérer là encore coûteux suivant la taille de la matrice. La latence d'une itération complète est de (L 1 /k+L 2 /k) symboles. Elle est inférieure à celle d'une architecture pipeline parallèle classique car le décodeur élémentaire traite k symboles d'un mot de code simultanément. La latence de traitement de la matrice C pour it itérations de ce type d'architecture est donc de : (8) L atence = (L 1 /k + L 2 /k)*it pour it itérations Cette latence est très faible si nous la comparons à celles obtenues dans les architectures classiques.

  qui spécifie les interfaçages et les rendements pour les réseaux d'accès optique, contient un code Reed Solomon comme code correcteur d'erreurs. Le code retenu est le code Reed Solomon (255,239) comprenant des symboles sous forme d'octets dont la

	I. Introduction	V. Proposition d'une architecture
	II. Le turbo décodage des codes produits	parallele de turbo décodeur de code
	III. État de l'art sur les architectures de	produit pour le très haut débit
	turbo décodeurs de code produit	VI. Bilan récapitulatif des différentes
	IV. Architectures parallèles de turbo	architectures possibles
	décodeur	VII. Conclusion
		Bibliographie

  . Il faut néanmoins se souvenir que notre proposition élimine les plans mémoires entre chaque demi-itération. Cette simplification est à mettre en regard à la complexité matérielle introduite au niveau des décodeurs élémentaires. De plus, si nous considérons le ratio nombre de portes du décodeur par Mbit/s, alors nous constatons qu'il est d'environ 55 pour l'architecture de référence et d'environ 27,5 pour les deux autres architectures. Le coût matériel du Mbit/s est donc divisé par deux.

	2046-Her/Teleco 62/1-2 5/01/07 9:07 Page 1778
	1778	C. JEGO -ARCHITECTURE DE TURBO DÉCODEUR EN BLOCS ENTIÈREMENT PARALLÈLE
			Débit	Latence	Complexité	Capacité	Complexité
	décodage 32*32	k-UT	(Mbit/s)	(nbre de	décodeur	mémoire	réseau connexion
				symboles)	(nbre de portes) (nbre de bits) (nbre de portes)
	architecture référence	1-UT	100	64	5 500	20480	0
	architecture haut débit [10, 18]	4-UT	1 600	16	44 000	20480	0
	architecture
	parallèle très haut	4-UT	12 800	16	352 000	0	1 000
	débit (IV.3)
	ANN. TÉLÉCOMMUN., 62, n°1-2, 2007				23/26

  1 n 2 + it* 2it*n 1 n 2 + it* n 1 n 2 +(it*(L 1 + L 2 )) it*(L 1 + L 2 )

	2046-Her/Teleco 62/1-2 5/01/07 11:48 Page 1780
	1780	C. JEGO -ARCHITECTURE DE TURBO DÉCODEUR EN BLOCS ENTIÈREMENT PARALLÈLE
						BIBLIOGRAPHIE
			Architecture classique		Architecture parallèle
		Séquentielle		Pipeline	Séquentielle		Pipeline
		1-UT	1-UT	k-UT	1-UT	1-UT	k-UT
	latence	< 2*n 1 n 2	2it*n it*((L 1 + L 2 )/k)
	(nbre symboles)		(L 1 + L 2 )	( ( L 1 + L 2 )/k)	< 2 * n 1 n 2
	débit (Mbits/s)	D ref	D ref *2it	D ref *2it*k 2	D ref *n min	D ref *2it*n min	D ref *2ti*(n min /k)*k 2
	nbre de décodeurs él.	1	2 it	2it*k*(k/2)	n min	n min *2it	(n min /k)*2it*k*(k/2)
	capacité mémoire	4qn 1 n 2	4qn 1 n 2 *2it	4qn 1 n 2 *2it	4qn 1 n 2	0	0
	(en bit)
	nbre de réseaux d'interconnexion	0	0	0	0	2 it-1	2it-1
							juin 2006
						Accepté le 25 octobre 2006
	ANN. TÉLÉCOMMUN., 62, n°1-2, 2007				25/26

2046-Her/Teleco 62/1-2 5/01/07 9:06 Page 1757

6/26 ANN. TÉLÉCOMMUN., 62, n°1-2, 2007 FIG 5. -Architecture séquentielle de turbo décodeur. Turbo decoder sequential architecture. 2046-Her/Teleco 62/1-2 5/01/07 9:06 Page 1761

ANN. TÉLÉCOMMUN., 62, n°1-2, 2007 7/26 2046-Her/Teleco 62/1-2 5/01/07 9:06 Page 1762

12/26 ANN. TÉLÉCOMMUN., 62, n°1-2, 2007 2046-Her/Teleco 62/1-2 5/01/07 9:06 Page 1767

ANN. TÉLÉCOMMUN., 62, n°1-2, 2007 13/26 2046-Her/Teleco 62/1-2 5/01/07 9:06 Page 1768

16/26 ANN. TÉLÉCOMMUN., 62, n°1-2, 2007 2046-Her/Teleco 62/1-2 5/01/07 9:06 Page 1771

24/26 ANN. TÉLÉCOMMUN., 62, n°1-2, 2007 2046-Her/Teleco 62/1-2 5/01/07 9:07 Page 1779

26/26 ANN. TÉLÉCOMMUN., 62, n°1-2, 2007 2046-Her/Teleco 62/1-2 5/01/07 9:07 Page 1781


Camille Leroux
email: camille.leroux@telecom-bretagne.eu

Christophe Jego
email: christophe.jego@telecom-bretagne.eu

Patrick Adde
email: patrick.adde@telecom-bretagne.eu

Deepak Gupta
email: deepak.gupta@telecom-bretagne.eu

Michel Jezequel
email: michel.jezequel@telecom-bretagne.eu

D C Metro Area

Turbo product code

Keywords: TPC decoding, Parallelism exploration, Ultra-high-speed integrated circuits

Introduction

Nowadays, high throughput telecommunication systems such as optical fiber transmission systems or passive optical networks require powerful error correcting codes in order to increase their optical budget. Iterative decoding [START_REF] Gallager | Low density parity check codes[END_REF][START_REF] Berrou | Near Shannon limit error-correcting coding and decoding: Turbocodes[END_REF] provides effective solutions for next generation optical systems. Recently, a (660,480) LDPC code decoder ASIC implementation was proposed. The throughput is 2.4 Gb/s while it could be enhanced to 10 Gb/s with a (2048,1723) LDPC code [START_REF] Darabiha | A 3.3-Gbps bit-serial block-interlaced min-sum LDPC decoder in 0.13-um CMOS[END_REF]. Turbo product codes [START_REF] Pyndiah | Near optimum decoding of product codes[END_REF] also tend to be good candidates for emerging optical systems [START_REF] Mizuochi | Next generation FEC for optical transmission systems[END_REF]. In [START_REF] Mizuochi | Experimental demonstration of net coding gain of 10.1 dB using 12.4 Gb/s block turbo code with 3-bit soft decision[END_REF], a TPC decoder is included in a 12.4 Gb/s optical experimental setup. Since only a part of the transmitted data is actually encoded, the throughput of the TPC turbo decoder is 156Mb/s.

The inherent parallel structure of the product code matrix confers to TPC a good ability for parallel decoding. Nevertheless, enhancing parallelism rate rapidly induces the use of a prohibitive amount of memory. Many solutions were proposed to efficiently exploit parallelism in TPC decoding. However, TPC decoding provides several level of parallelism and it is not always clear which level is the most efficient.

In [START_REF] Leroux | A highly parallel turbo product code decoder without interleaving resource[END_REF], we proposed a fully parallel turbo product code decoder without interleaving resource. In this paper, we set this architecture in the more general context of parallelism level exploration. We propose a parallelism level taxonomy that helps to classify and characterize parallelism in TPC decoding. Similarly to [START_REF] Muller | Exploring parallel processing levels for convolutional turbo decoding[END_REF], we provide insights on the benefits that each parallelism level can bring to the architecture performance. From this design space exploration, a parallelism level that has not been fully used in previous work is identified. Then, we propose an architecture of a highlyparallel TPC decoder that efficiently takes advantage of the exploited parallelism.

After a brief introduction of the TPC coding and decoding concept in Section 2, Section 3 defines and characterizes all the parallelism levels in TPC decoding. In Section 4, a review of existing solutions is given before the description of an innovative TPC decoder architecture without any interleaving resource. This original TPC decoder includes a novel fully-parallel SISO decoder architecture which is described in Section 5. Section 6 gives some synthesis results and demonstrates the efficiency of the proposed TPC decoder by comparison with current TPC and LDPC decoders. The interconnection issue is assessed and compared with an equivalent LDPC code decoder implementation.

TPC Coding and Decoding Principles

Product codes usually have high dimension which precludes Maximum-Likelihood (ML) soft-decision decoding. Yet, the particular structure of this code family lends itself to an efficient iterative "turbo" decoding algorithm offering close-to-optimum performance at high enough Signal-to-Noise-Ratios (SNRs).

Product Codes

The concept of product codes is a simple and efficient method to construct powerful codes with a large minimum Hamming distance d using cyclic linear block codes [START_REF] Elias | Error-free coding[END_REF]. Let us consider two systematic cyclic linear block codes C 1 having parameters (n 1 , k 1 , d 1 ) and C 2 having parameters (n 2 , k 2 , d 2 ) where n i , k i and d i (i = 1, 2) stand for code length, number of information symbols and minimum Hamming distance respectively. The product code P = C 1 × C 2 is obtained by placing (k 1 × k 2 ) information bits in a matrix of k 1 rows and k 2 columns, coding the k 1 rows using code C 2 and coding the n 2 columns using code C 1 , as shown on Fig. 1.

Considering that C 1 and C 2 are linear codes, n 1 rows are codewords of C 2 exactly as all n 2 columns are codewords of C 1 by construction. Furthermore, the parameters of the resulting product code P are given by

n p = n 1 × n 2 , k p = k 1 × k 2 , and d p = d 1 × d 2 and the code rate R p is given by R p = R 1 × R 2 .
Thus, it is possible to construct powerful product codes using linear block codes. In the following sections, we will consider a squared product code, meaning that n 1 = n 2 = n. The most commonly used component codes are Bose Chaudhuri Hocquenghem (BCH) codes. These codes are an infinite class of linear cyclic block codes that have capabilities for multiple error detection and correction. Product codes were adopted in 2001 as an optional correcting code system for both the uplink and downlink of the IEEE 802.16 standard (WiMAX) [10]. Reed-Solomon (RS) codes can also be used as component codes. RS codes are non-binary codes in which symbols are represented on M RS = log(n + 1) bits while M BCH = 1. It has been shown that they provide similar performance for a low decoding complexity [START_REF] Bidan | Reed-Solomon turbo product codes for optical communications: From code optimization to decoder design[END_REF][START_REF] Leroux | On the higher efficiency of parallel Reed-Solomon turbo-decoding[END_REF].

Iterative Decoding of Product Codes

TPC decoding involves successively alternate decoding rows and columns using SISO decoders. Repeating this soft decoding during several iterations enables the reduction of the Bit Error Rate (BER). It is known as the TPC decoding process. Each decoder has to compute soft information [R ] it+1 from the channel received information [R] and the information [R ] it computed during the previous half-iteration.

Despite the existence of several other decoding algorithms [START_REF] Forney | Generalized minimum distance decoding[END_REF], the Chase-Pyndiah algorithm is known to give the best tradeoff between performance and decoding complexity [START_REF] Adde | Performance and complexity of block turbo decoder circuits[END_REF]. The Chase-Pyndiah SISO algorithm for a t = 1 BCH code [START_REF] Pyndiah | Near optimum decoding of product codes[END_REF][START_REF] Chase | A class of algorithms for decoding block codes with channel measurement information[END_REF]

F it = ⎧ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎨ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎩ β it = (|R it | + L i=1 λ i )
min(M i ) when no competitor exists

F it = min 2 (M i ) -min(M i ) otherwise, -Compute extrinsic information W it = F it -R it , -Add extrinsic information (multiplied by α it ) to the channel received word, R it+1 = R + α it W it .
As explained in [START_REF] Leroux | Towards Gb/s turbo decoding of product code onto an FPGA device[END_REF], decoding parameters L, τ p , Cw and the number of quantization bits of the soft information q have a considerable effect on decoding performance and complexity. The α it coefficient allows decoding decisions to be damped during the first iterations. β it is an estimation of F it when no competitor exists. As detailed in [START_REF] Adde | Recent simplifications and improvements in block turbo codes[END_REF], it is based on the least reliable bits value.

Parallel Processing Levels in TPC Decoding

An architecture can be characterized by different metrics such as throughput, latency, hardware complexity, power consumption, routing density, etc. In this study, we aim at high speed architectures with low hardware complexity. Consequently, the performance is measured by throughput (T) while the cost function is the hardware complexity (C). In such a context, the efficiency of an architecture is defined as the throughput/complexity ratio : E = T/C. An efficient architecture would process a high data rate at a low hardware complexity.

The parallelism of an architecture can be defined as "the ability of the system to process several data in parallel". We formerly define the parallelism P of a decoder as the number of bit that can be processed/decoded in a single clock cycle. Parallelism directly influences the performance of an architecture. In order to quantify the benefit/disadvantage brought by the application of a parallelism P i to an architecture, we define three metrics, the speed gain G S , the computational ratio R C and the ef f iciency gain G E :

⎧ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎨ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎩ G S (P i = p) = T P i = p T P i =1 R C (P i = p) = C P i = p C P i =1 G E (P i = p) = E P i = p E P i =1 = G S (P i = p) R C (P i = p) A parallelism level P i is considered to be ef fective if G S (P i ) > 1, while it is ef f icient when G E (P i ) > 1 ⇐⇒ G S (P i ) > R C (P i ).
In the following of this section, all parallelism levels in TPC decoding are detailed and characterized.

Frame Parallelism

The highest level of parallelism can be observed at the frame level, this is known as frame parallelism. It is a form of spatial parallelism and is suitable to any decoding scheme. It consists in duplicating the processing resources, e.g. the turbo-decoder. By using this parallelism level in TPC decoding, P frame matrices can be decoded at the same time. Considering P frame turbodecoders that have the same throughput T 0 , the speed gain and complexity ratio are equivalent: G S = R C = P frame . Consequently the efficiency does not increase with P frame : G E = 1. Actually, this level of parallelism is only limited by the affordable silicon area. Although frame parallelism do make TPC decoder architecture more effective, it does not improve its efficiency.

Iteration Parallelism

In a sequential TPC decoder implementation, each iteration is performed by the same decoder that reads and writes data in the Interleaving Memories (IM). It is however possible to use the iteration parallelism by duplicating the elementary decoder in a pipelined structure. The maximum depth of such a structure equals to the maximum number of iteration it max . Iteration parallelism is a type of temporal parallelism. Here again, the throughput benefit equals to the complexity ratio: G S = R C = P it . It means that the iteration parallelism does not improve efficiency.

Sub-block Parallelism

In a product code matrix, each row (column) is obtained independently from the others (See Section 2.1). This interesting property can also be used during the decoding process, where each row (column) is decoded independently. In an implementation prospective, it means that more than one decoder can be assigned to row (column) decoding. Considering a product code matrix of size n 2 , a maximum number of n decoders can be duplicated for row (column) decoding. We designate this parallelism level as sub-block parallelism P sb . In a straightforward application of this parallelism level, one would simply duplicate the SISO decoders and the associated memory resources. It leads to a non-efficient parallelism exploitation, in particular due to the large size of the memory blocks that have to be duplicated P sb times. In [START_REF] Chi | High speed VLSI architecture design for block turbo decoder[END_REF][START_REF] Jego | Full-parallel architecture for turbo decoding of product codes[END_REF] solutions are proposed to avoid interleaving resource duplication when P sb increases. This makes the complexity ratio lower than the speed gain, which means that the ef f iciency gain of the architecture increases with P sb . G E can be expressed as:

G E = P sb (C SISO + C π ) P sb C SISO + C π G E > 1 ⇐⇒ P sb > 1
C SISO and C π are the hardware complexity of the SISO decoder and the interleaving resource respectively.

Symbol Parallelism

A finer-grained parallelism is the symbol parallelism. It can be defined as the ability of a SISO decoder, to process P sym symbols of the same sub-block (row or column) in parallel. In a sequential SISO decoder, input data is shifted in a serial manner. Every incoming symbol implies some internal metrics to be updated. By increasing P sym , some parts of the decoder datapath has to be duplicated, (e.g. the reliability computation stage). However, the other blocks, such as the test pattern metric computation, or the competitor vector determination block, remain identical when P sym increases. Consequently, the complexity ratio is lower than the speed gain: G E < 1. Increasing P sym also means that the interleaving memory should be able to read/write more than one data during the same clock cycle. Solutions were provided in [START_REF] Cuevas | New architecture for high data rate turbo decoding of product codes[END_REF] to exploit this parallelism while avoiding interleaving memory duplication. Synthesis results confirm that the efficiency increases with P sym . For an architecture that avoid interleaving resource duplication, G E can be expressed as:

G E > 1 ⇐⇒ C DEC (P sym = p) < p × C DEC (P sym = 1)
C DEC (P sym = p) is the hardware complexity of a SISO decoder with a symbol parallelism equals to p. In [START_REF] Cuevas | New architecture for high data rate turbo decoding of product codes[END_REF], this inequality has been verified by synthesis for P sym = {1; 2; 4; 8} for a BCH(32,26) 2 TPC decoder. In this paper, we propose to verify this inequality for the same code and for P sym = n = 32. This challenging architecture is described in Section 5.

Intra-symbol Parallelism

In TPC decoding, BCH codes are often used for their good decoding performance/complexity tradeoff. Recent work [START_REF] Bidan | Reed-Solomon turbo product codes for optical communications: From code optimization to decoder design[END_REF][START_REF] Piriou | Efficient architecture for Reed Solomon block turbo code[END_REF] has shown that using RS codes as component codes, can provide similar decoding performance at a reasonable computational complexity.

From an architectural point of view, the non-binary structure of RS codes enables to exploit an extra parallelism level, the intra-symbol parallelism P is . In a RS code of size n, a symbol consists in log(n + 1) bits (see Fig. 1). A RS-SISO decoder can either shift-in symbols bit by bit or symbol by symbol. It provides a maximal parallelism rate of max(P is ) = log(n + 1).

Similarly to the symbol parallelism, the resource sharing within the RS-SISO decoder increases the efficiency. However the ef f iciency gain provided by P is is hard to estimate because it is highly related to the internal architecture of the SISO decoder. Nevertheless, it is possible to give a condition that guarantees G E (P is ) > 1:

C(P is > 1) < P is × C(P is = 1)

Parallelism Levels Comparison

Table 1 summarizes benefits of parallelism levels in TPC decoding. For each parallelism P i , the maximum speed gain, the ef f iciency gain and the P i value that maximizes the efficiency are given. Frame parallelism is only limited by technological issues (e.g. silicon area). This parallelism improves the effectiveness of the archi-Table 1 Comparison of parallelism levels in TPC decoding.

P i max(G S ) G E arg(max(E)) P frame ∞ 1 [0; +∞[ P it IT c 1 IT c P sb n ≥ 1 n P sym n ≥ 1 n P is log(n + 1) ≥ 1 l o g (n + 1)
tecture; it is straightforward to implement but it does not improve efficiency. Iteration parallelism has the same impact but has an upper bound limited by the maximum number of iteration required by the decoding process.

Application of lower levels of parallelism (P sb , P sym and P is ) improves the architecture efficiency. It is even maximized for highest parallelism value. However, the use of these parallelism levels is not as straightforward as P frame and P it . It requires some specific scheduling and/or implementation strategies.

Parallel Decoding of Product Codes

Designing turbo-decoder architectures compatible with data rates higher than 10 Gb/s is a challenging issue. In this section we first introduce previous work. Then, the proposed Interleaving-Memory-free (IM-free) TPC decoder architecture is detailed. It jointly uses P sym and P sb and includes fully-parallel SISO decoders that are described in Section 5.

Previous Work

Many TPC decoder architectures were previously designed. In current architectures, the rebuilding of the product code matrix is necessary between each iteration: memory blocks are used at each half-iteration to read and store [R ] it and [R]. Each interleaving memory block is then composed of four memories of n 2 × (M × q)-bits data . This solution has several drawbacks. First, a large amount of memory is required which increases the global latency and the hardware complexity of the design. In addition, increasing the degree of parallelism at the sub-block level produces memory conflicts when several data have to be accessed at the same time. In Table 2, existing architectures are reviewed in terms of achieved parallelism P i and associated hardware complexity. The hardware complexity is given for interleaving resources (C π ) and decoding resources (C Dec ).

In [START_REF] Chi | High speed VLSI architecture design for block turbo decoder[END_REF], authors suggested to use a barrel shifter between decoding resources and the interleaving memory in order to avoid memory conflicts. This solution enables to use the sub-block parallelism at its highest rate: P sb = n. The extra-complexity consists in a simple barrel shifter with a complexity of O(n log(n)). However, it still includes a large amount of interleaving memory.

In [START_REF] Leroux | Towards Gb/s turbo decoding of product code onto an FPGA device[END_REF][START_REF] Jego | Full-parallel architecture for turbo decoding of product codes[END_REF]22], an IM-less architecture is detailed and prototyped onto an FPGA device. In this architecture, a particular scheduling of the product code matrix decoding enables the interleaving memories to be replaced by an interconnection network (omega network). This TPC decoder also has a maximal sub-block parallelism (P sb = n), while the hardware complexity of the interleaving resources is drastically reduced.

Moreover, in [START_REF] Cuevas | New architecture for high data rate turbo decoding of product codes[END_REF] an architecture that uses symbol parallelism in conjunction with sub-block parallelism, was proposed. The idea is to store several product code matrix symbols at the same address and to design elementary decoders able to process P sym = m symbols during the same clock period (denoted as m-decoders). A half-iteration structure includes m decoders each decoding m symbols in one clock period and an interleaving memory of size 4 × q × M × n 2 . This scheme actually exploits symbol parallelism on one dimension of the matrix and sub-block parallelism on the other dimension in such a way that P sb = P sym = m. The resulting throughput is O(m 2 ) while the overhead factor of the decoder complexity is ∼ m 2 2 . In this previous work, the maximum reached parallelism rate was m 2 = 64, with m = 8 SISO decoders.

These three architectures can reach high parallelism degrees (i.e. high throughput) for different hardware cost. A TPC decoder is composed of interleaving resources and decoding resources. More than 50% of the complexity is in the memory for IM-based architecture, while it represents less than 10% for omega networkbased structure [START_REF] Jego | Full-parallel architecture for turbo decoding of product codes[END_REF]22]. On the decoding resources side, increasing the parallelism rate by duplicating computation resources is inefficient since the reuse of available resources is not optimized. In the following section we propose a more efficient architecture that keeps a memory-less interleaver and uses both symbol and subblock parallelism in the decoding stage. Considering that one can design a P sym = n SISO decoder, a product code matrix can be decoded without any interleaving resource as shown in Fig. 2. At t = 0, the fully-parallel SISO decoder processes the column 1. During the next clock period, n sequential SISO decoders (P sym = 1) start decoding the first symbol of each row while the parallel decoder process the column 2. During the n th clock period, sequential decoders complete matrix decoding while the parallel decoder is already decoding the next matrix. Data generated by the parallel decoder is immediately used by a sequential decoder. Consequently, no IM or data routing resources are required between the fullyparallel decoder and sequential decoders. The resulting proposed architecture and the previous architectures [START_REF] Chi | High speed VLSI architecture design for block turbo decoder[END_REF][START_REF] Jego | Full-parallel architecture for turbo decoding of product codes[END_REF] for one iteration are depicted on Fig. 3.

P sb = n O (4qn 2 ) + O(n log(n)) O(n) [16, 19] P sb = n O (n log(n)) O(n) [20] P sb = m; P sym = m O (4qn 2 ) O(m 2 /2)
This architecture uses row-wise P sb and column-wise P sym . More specifically, we have:

P sym (col) = P sb (row) = n P sb (col) = P sym (row) = 1
One should notice that P sb (col) = P sym (row) can be further exploited.

Towards a Maximal Parallelism Rate

Starting from the IM-free architecture presented in the previous section, parallelism can be further enhanced. Figure 4 shows the alternate product code matrix parallel decoding scheme in which P sb (col) = P sym (row) = m and P sym (col) = P sb (row) = n. The TPC decoder consists in m× n-decoders for column decoding and n× m-decoders for row decoding. A m-decoder can process m symbols in one clock period and 1 ≤ m ≤ n. In such an architecture, the maximum reachable parallelism rate P = n 2 can be achieved by using n fully-parallel SISO decoders for column decoding and n fully-parallel SISO decoders for row decoding. Intrasymbol parallelism can also be used to increase the total parallelism to P = P sb × P sym × P is = n 2 log(n). All these new schemes however require to design a SISO decoder capable of processing n symbols in one clock period.

Architecture of a Fully-Parallel Combinatory SISO Decoder

The proposed IM-free TPC decoder architecture requires a fully-parallel combinatorial SISO decoder. To the best of our knowledge, only sequential SISO decoders able to process m ≤ n symbols in one clock period have been previously designed. The design of a fully-parallel combinatorial SISO decoder is a challenging issue for designer. In the following section, such an architecture is proposed and described.

Algorithmic Parameter Reduction

As explained earlier in Section 2, the Chase-Pyndiah algorithm includes parameters (L, τ p , Cw, q) which impact on both the performance and the complexity of the turbo decoding. BER simulation were performed with different parameters: L = {2; 3; 4; 5}, τ p = {4; 8; 16}, Cw = {0; 1; 2; 3}, q = {3; 4; 5}. Performing eight iterations, the parameter set P 0 = {L = 5, τ p = 16, Cw = 3, q = 5} gives the best performance for a maximal complexity [START_REF] Adde | Performance and complexity of block turbo decoder circuits[END_REF]. However, algorithmic simulations showed that the reduced parameter set P 1 = {L = 3, τ p = 8, Cw = 0, q = 5} only induce a performance loss of 0.25dB at BER= 10 -6 while it becomes null below BER = 10 -9 . Further reducing these parameters would induce a notable performance loss. For example by simply reducing the number of test patterns: P 2 = {L = 2, τ p = 4, Cw = 3, q = 5}, the performance loss reaches 0.5dB. Consequently, using P 1 enables the architecture to be simplified at very low performance lost below BER=10 -9 .

Figure 5 Combinatorial version of the fully-parallel SISO decoder.

5.2 Fully-Parallel SISO Decoder Architecture Figure 5 depicts the architecture of the fully-parallel SISO decoder. In the first attempt a purely combinatorial designed was conceived. Later, a critical path study mandated the insertion of pipeline stages within the structure. The SISO decoder is split in three stages, namely the reception stage, the test pattern processing stage and the soft output computation stage.

Reception Stage

The reception stage corresponds to steps (1-3) of the Chase-Pyndiah algorithm detailed in Section 2.

The syndrome of the incoming vector R it can be derived as S(R it ) = H × sign(R it ) where H is the parity check matrix of the BCH code. A straightforward implementation of such a matrix multiplication is depicted on Fig. 6. The H matrix, the corresponding parity check equations and the syndrome S(t 0 ) = [s 2 , s 1 , s 0 ] implementation of a BCH(7,4) code are detailed.

It can be noticed that some parity check equations have similar terms. For instance, the term (x 1 ⊕ x 0 ) is used in both s 1 and s 2 computation. This enables a reuse of computation resources for an even more efficient implementation. The parity of the incoming vector R it is computed with a similar structure by "xoring" (n -1) incoming bits. Selecting the least reliable bits among the incoming vector in parallel requires a sorting network. Such structures are composed of interconnected Compare and Select operators (CS). The interconnection scheme depends on the considered sorting algorithm. Many parallel sorting algorithm are conceivable [23]. However, most of them are optimized for a complete sorting, while the Chase-Pyndiah algorithm only requires a partial sorting (i.e. extracting L minima). Consequently we devised a network optimized, in terms of area and critical path, for the partial sorting of L = 3 values among n = 32, as depicted on Fig. 7. The structure is based on shuffle networks coupled with local minima computation blocks. After the first shuffle stage, min 1 is in the lower section while the upper section can either contain min 2 or min 3 or no minimum. The same reasoning is applied recursively. After five shuffle stages, the minimum is determined while five values can still be min 2 and min 3 . A local sorting of this five values enables the determination of min 2 and min 3 value. This partial sorting network requires 35 CS and 29 minimum elements. The critical path consists of nine comparison stages.

Test Pattern Processing Stage

The test pattern processing stage corresponds to steps (4-5) in the Chase-Pyndiah algorithm detailed in Section 2. Instead of being processed sequentially, test patterns are processed in parallel. The syndrome of each test pattern is computed by adding S(t 0 ) with the position of the inverted reliable bits. The parity management block computes the parity of R it+1 considering the parity of R it and the detection of an error which is the case when S(t i ) = 0. Metrics of each test pattern is then computed by adding the contribution of each inverted bit in the current test pattern (least reliable bits, syndrome corrected bits and, the new parity bit). The minimum metric is determined in the DW selection block. The structure is a simple minimum selection tree. The multiplexer selects R it (S(t i )) in order to compute test pattern metrics.

Soft Output Computation Stage

The last stage is a duplication of n soft output computation blocks. As shown in Fig. 8, this block first computes the new reliability F it of each symbol. Since, no competitor word is considered, the β value is automatically assigned. The β value is based on an estimation of the competitor word metric value. It is calculated from the reliability of the corrected bit and the least reliable bits. Then, the extrinsic information is computed and damped by the coefficient α it which is devised to be a power of 2 making the multiplication a simple bit shifting. Finally, the channel information is added to generate the soft output R it+1 . Within this block, all computation are performed in sign and magnitude format. Other arithmetic format were explored but the chosen one requires less computation resources than others.

Comparison with Existing TPC and LDPC Decoders

In classical iterative decoders, the hardware complexity corresponds to the cumulative area of computational resources and memory resources. In proposed IM-free architecture, only the hardware complexity of the SISO decoders have to be considered. Consequently, the following synthesis results will only focus on hardware complexity of SISO decoders. Moreover, some comparisons with current TPC and LDPC decoders are given to demonstrate the potential of the proposed TPC decoder.

BCH(32,26) SISO Decoder Logic Synthesis Results

In Section 3, we demonstrated that exploiting symbol parallelism is efficient if C DEC (P sym = p) < p × C DEC (P sym = 1). In order to verify this inequality, we compare one parallel (P sym = n) BCH SISO decoder vs n × sequential (P sym = 1) SISO decoders. Five versions of the BCH(32,26) parallel SISO decoder were designed and have from one to five pipeline stages. The one-pipeline stage version is a fully-combinatorial architecture with register banks only at the input and output stages. Table 3 summarizes synthesis results of the five different parallel SISO decoders and compare them with n = 32 duplicated sequential SISO decoders. s is the number of pipeline stages inserted in the SISO decoder, f max is the maximum frequency reached dur- 2.1 3.9 4.9 5.9 6.3 1 ing synthesis, the throughput T is calculated such as T = P × f max , A represents the area of the design in equivalent gate count and E is the efficiency: E = T A . Logic syntheses were performed using Synopsys Design Compiler with a ST-microelectronics 90 nm CMOS process. The area is transposed in logic gate count. One equivalent logic gate corresponds to the area of a two-input NAND gate. It enables a more technologyindependent measure of the hardware complexity.

As expected, the maximum frequency of the combinatorial decoder (s = 1) is lower than a sequential version. However, by inserting pipeline stages inside the combinatorial structure, the same frequency is reached with s = 5. For this last version, the throughput is even higher than n sequential SISO decoders. The hardware cost of the pipeline stages insertion depends on registers location in the decoder. This is the reason why A(s = 4) < A(s = 3). In this particular case, having s = 4 pipeline stages enables register stages to be assigned at regular intervals, for a lower hardware cost. In terms of efficiency, a parallel SISO decoder can reach the same throughput as n sequential SISO decoders with a six times lower complexity. The efficiency gain increases with s.

These synthesis results demonstrate the higher efficiency of parallel SISO decoding for the code BCH(32,26). Now, if one consider larger code with the same correction power (i.e. BCH(64,57), BCH(128,120)), the complexity of the reception stage and the soft output computation stage would grow linearly with the code size n. However the complexity of the test pattern processing stage would only increase linearly with τ p < n. Consequently, the overall complexity of the parallel SISO decoder is lower than a duplication of n sequential SISO decoders. It confirms that a fully-parallel SISO decoder enables a better reuse of computation and memory resources and makes the whole TPC decoder more efficient.

One should notice that, for higher correction power (t > 1), the algebraic decoding requires more complex algorithms such as Berlekamp-Massey algorithm [24, 25] which make the decoder complexity significantly higher. This is the reason why t = 1 codes were selected is this study. 4 compares performance of the proposed solution with current architectures in a ultra-highthroughput context (T > 10 Gb/s). For each solution, the decoder architecture main features, the targeted code, the levels of parallelism that were used in order to reach T = 10 Gb/s, the resulting total parallelism (P total = i P i ), the maximum number of iteration it max are given. We consider that one iteration is actually implemented. The resulting throughput is T = P total × f max /it max . Finally, the gate count (A), the efficiency (E = T/A) and the achieved coding gain at BER=10 -9 are given. Such a low BER is usually targeted in very high speed application (e.g. data transmission over Passive Optical Networks). For a fair comparison, architectures described in [START_REF] Bidan | Reed-Solomon turbo product codes for optical communications: From code optimization to decoder design[END_REF][START_REF] Chi | High speed VLSI architecture design for block turbo decoder[END_REF][START_REF] Jego | Full-parallel architecture for turbo decoding of product codes[END_REF][START_REF] Cuevas | New architecture for high data rate turbo decoding of product codes[END_REF] were synthesized with the same technology: ST Microelectronics, CMOS 90 nm with a target frequency f max = 500 MHz. For the remaining architectures, we gathered information from the published papers and technical reports.

Two versions of the proposed turbo decoder were synthesized. The first one consists in 4 parallel SISO decoders together with 32 P sym = 4-SISO decoders. The reached throughput is then sufficient for 10 Gb/s applications. The second version uses only fully-parallel SISO decoder, 32 of such decoders are duplicated for each half-iteration. The maximum throughput is 85 Gb/s for the best efficiency.

The barrel-shifter-based solution [START_REF] Chi | High speed VLSI architecture design for block turbo decoder[END_REF] can achieve 10 Gb/s with 2.6 Mgates. In order to reach a sufficient parallelism level, it was necessary to use frame parallelism. The efficiency of this solution is six times lower than the proposed architecture. This low efficiency is mainly due to the use of interleaving memory.

For the same reason, the TPC decoder with multiaccess data [START_REF] Cuevas | New architecture for high data rate turbo decoding of product codes[END_REF] has a low efficiency and also requires the use of frame parallelism to achieve 10 Gb/s.

In [START_REF] Jego | Full-parallel architecture for turbo decoding of product codes[END_REF], the elimination of interleaving memories improves the efficiency but the maximum parallelism rate is limited by the code size n, which makes the use of frame parallelism mandatory in a ultra high speed context. However, the proposed solution provides a maximum parallelism rate of n 2 .

The study in [START_REF] Bidan | Reed-Solomon turbo product codes for optical communications: From code optimization to decoder design[END_REF] shows that RS-TPC are a practical solution for 10 Gb/s transmission over optical networks. As we mentioned in Section 3, using RS codes enables the use of intra-symbol parallelism. With an omeganetwork-based architecture, this solution also presents good efficiency gain for similar decoding performance.

One should notice that the proposed fully-parallel architecture is applicable to RS decoding as well. We expect that the application of intra-symbol parallelism would further increase the overall efficiency of the TPC decoder. Moreover. when comparing a single iteration of RS-TPC decoding with a commercial RS(255,239) code decoder, one can observe that superior efficiency is achieved for slightly better decoding performance.

Mitsubishi has recently proposed a TPC decoder for 10 Gb/s optical transmissions. The component code is a BCH(144,128)×BCH(256,239). These codes are more powerful than t = 1 BCH codes that are used in this study, however the implementation is very costly in terms of hardware complexity. Indeed, 18 Mgates are necessary to implement such a decoder, which makes the efficiency very small. This is the cost that have to be paid for a 2dB extra coding gain provided by this TPC decoder.

Comparison with Current LDPC Decoders

As a matter of comparison, we gathered results from recent academic implementation of LDPC decoders. Since the code rates are different, the decoding performance comparison is not straightforward. However the architectural results help to locate the different decoders in the design space. Synthesis results show that a fully-parallel TPC decoder achieves higher throughput (85 Gb/s) than comparable LDPC decoders with a lower hardware complexity (2 Mgates).

However, placing and routing 2n parallel SISO decoders onto the same chip would reduce the maximum working frequency of the parallel SISO decoder. Nevertheless, with P total =1,024, throughput T=10 Gb/s is reached when f > 88 MHz which is a most probably achievable frequency on an ASIC target. Furthermore, a reasonable working frequency of f =300 MHz leads to a BCH(32,26) 2 product code turbo decoder with an throughput T =50 Gb/s. The total area of such a parallel turbo decoder is A = 2.2 Mgates= 10 μm 2 . In parallel LDPC code decoder, one of the main issues is the routing congestion induced by the Tanner graph implementation. The number of interconnections among the TPC decoder is I n (TPCD) = 2 × n 2 BCH × q while an equivalent fully parallel 1024-LDPC decoder would have I n (1024-LDPC) = n LDPC × q × d v where d v represents the variable node degree. Consequently, as long as d v > 2, the following inequation is verified: I n (T PCD) < I n (1024 -LDPC). Consequently, despite the high parallelism level that can be reached in TPC decoding, both area and routing congestions are in favor of TPC decoders.

Conclusion

TPC decoding is a realistic solution for next generation high throughput optical communications such as longhaul optical transmissions or passive optical networks. The structure of the product codes makes them very suitable for parallelisation, however the exploitation of some parallelism levels may not be efficient in terms of throughput/complexity ratio. This is particularly true when interleaving memory has to be duplicated.

In this paper we proposed to review and characterize all parallelism levels in TPC decoding. This analysis helps to better understand and classify existing TPC decoders. In previous TPC decoders, high throughput architecture complexity is made prohibitive by the amount of memory usually required for data interleaving and pipelining.

After this design space exploration, we propose an innovative architecture that jointly exploit sub-block parallelism and symbol parallelism. This novel structure enables any interleaving resource to be removed. The proposed TPC decoder requires a fully-parallel SISO decoder capable of processing n symbols in one clock period. Such a SISO decoder architecture is described and includes a new optimized parallel sorting network.

ASIC-based logic syntheses confirm the better efficiency of the proposed IM-free TPC decoder architecture compared to existing TPC decoders and recent LDPC decoders. Actually, when compared to previous work, the area is reduced while the same throughput is achieved. A BCH(32,26) 2 product code can be decoded at 33.7 Gb/s with an estimated silicon area of 10μm Michel Jezequel (M'02) was born in Saint Renan, France, on February 26, 1960. He received the degree of "Ingénieur" in electronics from the "École Nationale Supérieure de l'Électronique et de ses Applications", Paris, France in 1982. In the period 1983-1986 he was a design engineer at CIT ALCATEL in Lannion, France. Then, after an experience in a small company, he followed a one year course about software design. In 1988, he joined the TELECOM Bretagne, where he is currently Professor, head of the Electronics Department. His main research interest is circuit design for digital communications. He focuses his activities in the fields of Turbo codes, adaptation of the turbo principle to iterative correction of intersymbol interference, the design of interleavers and the interaction between modulation and error correcting codes.

Figure 1

 1 Figure 1 Product code matrix structure.

Figure 2

 2 Figure 2 Proposed parallel decoding scheduling of a product code matrix.

Figure 3

 3 Figure 3 Previous TPC decoder architecture (a) and proposed fully-parallel SISO based TPC decoder architecture (b).

Figure 4

 4 Figure 4 Alternative turbo decoding scheduling for enhanced parallelism rate.

Figure 6

 6 Figure 6 BCH(7,4) code: a Parity check matrix b Parity check equations c Syndrome parallel computation implementation.

Figure 7

 7 Figure 7Optimized sorting network for least reliable bits selection.

Camille

  Leroux was born in Vannes, France, in 1981. He received his M.S. in Electronics Design and Systems Architecture from the University of South Brittany in 2005. He performed his Ph.D. (2005-2008) in the Electronic Engineering Department at TELECOM Bretagne, France. He is currently a Postdoc fellow in the Department of Electrical and Computer Engineering at McGill University, Montréal, Canada. His research interest focus on hardware implementation of iterative decoding algorithms. Christophe Jego was born in Auray, France, in 1973. He received the M.S. and Ph.D. degrees from the Université Rennes 1, Rennes, France, in 1996 and 2000, respectively. He joined the Electronic Engineering Department of TELECOM Bretagne as a full-time Associate Professor in 2001. He was a visiting professor in the Department of Electrical and Computer Engineering at McGill University during 10 months (Sept. 2006 -June 2007). In 2009, he received Research Habilitation from University of Bretagne Sud. It is the highest French university diploma passed after a few years of active research and student supervision. His research activities are concerned with analysis and design of architectures for iterative processing in the digital communication systems. Patrick Adde was born in Caen, France, in 1953. He received the degree of "Ingénieur" from the "École Nationale d'ingénieur de Brest", Brest, France in 1974. In 1979, he joined the École Nationale Supérieure des Télécommunications de Bretagne, where he is currently Professor. His research interests are about the design of efficiency architectures for turbo decoding of product codes. Deepak Gupta was born in Haryana, India in 1983. He received his Bachelor of Technology degree from Guru Gobind Singh Indraprastha University, New Delhi, India in 2005. In 2008, he received M.Sc. degree in IC design and communications from TELECOM Bretagne, France during which he worked on channel coding and frequency multiplier architectures. Currently, he is working towards a Ph.D. in ultra-low power SoC design for biomedical applications in the Electronics department, Telecom Bretagne, France.

  is summarized below. t represents the maximum number of correctable errors. 1. Search for the L = |λ i | least reliable bits from the previous half-iteration output vector [R ] it such that min i (|[R ] it |) = λ i . min i (.) represents the i th minimum function. 2. Compute the syndrome S(t 0 ) of [R ] it , 3. Compute the parity of [R ] it , 4. Generate τ p test patterns τ i obtained by inverting some of the L least reliable bits (τ p ≤ 2 L ). 5. For each test pattern (1 ≤ τ i ≤ τ p -1)

	-Compute the syndrome S(τ i ),
	-Correct the potential error by inverting the bit
	position S(τ i ),
	-Recompute the parity considering the detec-
	tion of an error and the parity of [R ]

it , -Compute the square Euclidian distance (metric) M i between [R ] it and the considered test pattern τ i . 6. Select the Decided Word (DW) among test patterns having the minimal metric (M DW ) and choose Cw competitors codewords c i (1 < i < Cw) having the second minimum metric. 7. For each symbol of the DW, -Compute the new reliability F it :

Table 2

 2 Current TPC decoder architecture comparison.

	Architecture	P i	C π (1/2iter)	C Dec (1/2iter)
	[18]

8

  Soft output computation stage.

Table 3

 3

	Comparison of parallel and sequential BCH(32,26) SISO decoder	s	Parallel SISO decoder (P sym = 32) 1 2 3 4 5	32 sequential SISO decoders (P sym = 1) 3
	performance.	f max (Mhz)	125	333	500	500	714	700
		T(Gb/s)	4.0	10.7	16.0	16.0	22.9	22.4
		A ( K g a t e s )	1 8	2 6	3 1	2 6	3 4	2 0 0
		E (Mb/s/gate)	0.15	0.27	0.34	0.41	0.44	0.07
		G E

Table 4

 4 Comparisons with current TPC decoders and LDPC decoders.

	Decoder	Code	P i	P total it max T	A r e a	E	Coding gain (dB)
						(Gb/s) (Mgates) (Kb/s/gate) @BER=10 -9
	This work	BCH(32,26) 2	P sym = 4, P sb = 32		128 6	10.7	0.4	26.8	8.0
		BCH(32,26) 2	P sym = 32, P sb = 32 1,024 6	85.3	2.0	42.7	8.0
	Barrel shifter + IM [18]	BCH(32,26) 2	P sb = 32, P frame = 4		128 6	10.7	2.6	4.1	8.4
	Omega network +	BCH(32,26) 2	P sb = 32, P frame = 4		128 6	10.7	1.6	6.7	8.4
	no IM [19]	BCH(64,57) 2	P sb = 64, P frame = 2		128 6	10.7	2.0	5.4	8.6
		BCH(128,120) 2	P sb = 128		128 6	10.7	2.7	4.0	8.7
	Multi-data access IM [20] BCH(32,26) 2	P sym = 8, P sb = 8,		128 6	10.7	3.5	3.1	8.4
			P frame = 2
	Omega network +	RS(15,13) 2	P is = 4, P sb = 15,		120 6	10	0.3	33.3	8.4
	no IM [11]		P frame = 2
		RS(31,29) 2	P is = 5, P sb = 31		155 6	12.9	0.8	16.1	8.4
		RS(63,61) 2	P is = 3, P sb = 63		378 6	15.8	1.3	12.1	7.5
	Commercial RS decoder RS(255,239)	P is = 8, P frame = 4		32 X	10.7	0.12	89	5.0
	(ASICS ws)
	Omega network +	RS(31,29) 2	P is = 5, P sb = 31		155 1	35	0.4	95	5.2
	no IM [11]
	Commercial TPC decoder BCH(144,128)	?	?	4	10.0	18.0	0.6	10
	(Mitsubishi)	×BCH(256,239)
	LDPC decoder [3]	LDPC(2048,1723) ?		64 8	16.0	2.2	7.2	7.5
	LDPC decoder [26]	LDPC(1440,1344) ?		360 8	6.1	0.4	15.3	5.5

Table

  2 . 22. Leroux, C., Jego, C., Adde, P., & Jezequel, M. (2009). Highthroughput block turbo decoding: From full-parallel architecture to FPGA prototyping. Journal of Signal Processing Systems, 57, 349-361. 23. Akl, S. G. (1985). Parallel sorting algorithms. New York: Academic. 24. Berlekamp, E. R. (1984). Algebraic coding theory, revised edition. Laguna Hills: Aegean. 25. Massey, J. L. (1969). Shift-register synthesis and bch decoding. IEEE Transactions on Information Theory, IT, 122-127. 26. Yamagishi, H., & Noda, M. (2008). High throughput hardware architecture for (1440,1344) low-density parity-check code utilizing quasi-cyclic structure. In 2008 5th international symposium on turbo codes and related topics (pp. 78-83).