Les codes correcteurs d’erreurs sont largement utilisés dans des domaines allant de l’automobile aux communications sans fils. La complexité croissante des algorithmes implémentés et l’augmentation continue des débits applicatifs constituent des contraintes fortes pour la conception d’architectures matérielles. Un tel composant utilise (1) des éléments de calculs, (2) des mémoires et des modules de brassage de données (entrelaceur/désentrelaceur TurboCodes, blocs de redondance spatio-temporelle des systèmes OFDM/MIMO…). La complexité et le coût de ces systèmes sont très élevés; les concepteurs doivent pourtant parvenir à minimiser la consommation et la surface total du circuit, tout en garantissant les performances temporelles requises. Dans ce cadre nous nous intéressons à l’optimisation des architectures des modules de brassage de données. Différentes solutions sont proposées dans la littérature, nos travaux se focalisent sur la définition d’approches de placement de données en mémoire permettant d’optimiser le coût matériel de ces architectures. Ainsi, nous présentons deux approches méthodologiques. Premièrement, nous proposons deux solutions de placement mémoire s’appliquant au moment de la conception du système: (1) placement mémoire avec personnalisation de réseau (dite Relaxation de réseau); et (2) placement mémoire garantissant un placement des données dit in-place afin de générer architecture optimisée. Deuxièmement, nous présentons une approche se basant sur l’exécution des algorithmes de placement de données directement dans le système via l’intégration d’un composant matériel dédié. / Turbo and LDPC codes are two families of codes that are extensively used in current communication standards due to their excellent error correction capabilities. To achieve high performance, parallel architectures are required. However, these architectures suffer from memory conflict problems. These conflicts increase latency of memory accesses due to the presence of conflict management mechanisms in communication network, and unfortunately decreases system throughput with augmenting system cost.To tackle memory conflict problem, different types of approaches are used in literature. In this thesis, we aim to design optimized parallel architecture. For this purpose, we have presented two different categories of approaches. In first category, we have proposed design time off-chip approaches in which we have proposed two kinds of solution: a first one based on network customization; and a second approach based on in-place memory architecture in order to generate optimized architecture. In the second category, memory mapping algorithms is embedded on-chip in order to execute them at runtime to solve conflict problem. Dedicated architecture is composed of an embedded processor and RAM memory banks to store generated command words. Polynomial time memory mapping approach and routing algorithm (based on Benes network) is embedded on-chip to solve memory conflict problem. Different experiments have been performed by using memory mapping approaches executed on several embedded processors.

Nowadays, Turbo and LDPC codes are two families of codes that are extensively used in current communication standards due to their excellent error correction capabilities. However, hardware design of coders and decoders for high data rate applications is not a straightforward process. For high data rates, decoders are implemented on parallel architectures in which more than one processing elements decode the received data. To achieve high memory bandwidth, the main memory is divided into smaller memory banks so that multiple data values can be fetched from or stored to memory concurrently. However, due to scrambling caused by interleaving law, this parallelization results in communication or memory access conflicts which occur when multiple data values are fetched from or stored in the same memory bank at the same time. This problem is called Memory conflict Problem. It increases latency of memory accesses due to the presence of conflict management mechanisms in communication network and unfortunately decreases system throughput while augmenting system cost. To tackle the memory conflict problems, three different types of approaches are used in literature. In first type of approaches, different algorithms to construct conflict free interleaving law are proposed. The main reason to develop these techniques is to construct "architecture friendly" codes with good error correction capabilities in order to reduce hardware cost. However, architectural constraints applied during code design may impede error correction performance of the codes. In a second type of approaches, different design innovations are introduced to tackle memory conflict problem. Flexible and scalable interconnection network with sufficient path diversity and additional storing elements are introduced to handle memory conflicts. However, flexible networks require large silicon area and cost. In addition, delay introduced due to conflict management mechanisms degrades the maximum throughput and makes these approaches inefficient for high data rate and low power applications. In third type of approaches deals with algorithms that assign data in memory in such a manner that all the processing elements can access memory banks concurrently without any conflict. The benefit of this technique is that decoder implementation does not need any specific network and extra storage elements to support particular interleaving law. However, till now no algorithm exists that can solve memory mapping problem for both turbo and LDPC codes in polynomial time. The work presented in this thesis belongs to the last type of approaches. We propose several methods based on graph theory to solve memory mapping problem for both turbo and LDPC codes. Different formal models based on bipartite and tripartite graphs along with different algorithms to color the edges of these graphs are detailed. The complete path we followed before it is possible to solve mapping problem in polynomial time is hence presented. For the first two approaches, mapping problem is modeled as bipartite graph and then each graph is divided into different sub-graphs in order to facilitate the coloring of the edges. First approach deals with Turbo codes and uses transportation problem algorithms to divide and color the bipartite graph. It can find memory mapping that supports particular interconnection network if the interleaving rule of the application allows it. Second approach solves memory mapping problem for LDPC codes using two different complex algorithms to partition and color each partition. In the third algorithm, each time instance and edge is divided into two parts to model our problem as tripartite graph. Tripartite graph is partitioned into different sub-graphs by using an algorithm based on divide and conquer strategy. Then each subgraph is colored individually by using a simple algorithm to find a conflict free memory mapping for both Turbo and LDPC codes. Finally, in the last approach tripartite graph is transformed into bipartite graph on which coloring algorithm based on Euler partitioning principle is applied to find memory mapping in polynomial time. Several experiments have been performed using interleaving laws coming from different communication standards to show the interest of the proposed mapping methods. All the experiments have been done by using a software tool we developed. This tool first finds conflict free memory mapping and then generates VHDL files that can be synthesized to design complete architecture i.e. network, memory banks and associated controllers. In first experiment, bit interleaver used in Ultra Wide Band (UWB) interleaver is considered and a barrel shifter is used as constraint to design the interconnection network. Results are compared regarding area and runtime with state of the art solutions. In second experiments, a turbo interleaving law defined in High Speed Packet Access (HSPA) standard is used as test case. Memory mapping problems have been solved and associated architectures have been generated for this interleaving law which is not conflict free for any type of parallelism used in turbo decoding. Results are compared with techniques used in state of the art in terms of runtime and area. Third experiment focuses on LDPC. First, last algorithm we proposed is used to find conflict free memory mapping for non-binary LDPC codes defined in the DaVinci Codes FP7 ICT European project. Then, conflict free memory mapping have also been found for partially parallel architecture of LDPC codes used in WiMAX and WiFi for different level of parallelism. It is shown that the proposed algorithm can be used to map data in memory banks for any structured codes used in current and future standards for partially parallel architecture. In last experiment, thanks to the proposed approach we explored the design space of Quadratic Permutation Polynomial (QPP) interleaver that is used in 3GPP-LTE standard. The QPP interleaver is maximum contention-free i.e., for every window size W which is a factor of the interleaver length N, the interleaver is contention free. However, when trellis and recursive units parallelism are also included in each SISO, QPP interleaver is no more contention-free. Results highlight tradeoffs between area and performances based on for different radixes, parallelisms, scheduling (replica versus butterfly)...

Les applications du traitement du signal (TDSI) sont maintenant largement utilisées dans des domaines variés allant de l'automobile aux communications sans fils, en passant par les applications multimédias et les télécommunications. La complexité croissante des algorithmes implémentés et l'augmentation continue des volumes de données et des débits applicatifs requièrent souvent la conception de circuits intégrés dédiés (ASIC). Typiquement l'architecture d'un composant complexe du TDSI utilise (1) des éléments de calculs de plus en plus complexes, (2) des mémoires et des modules de brassage de données (entrelaceur/désentrelaceur pour les TurboCodes, blocs de redondance spatio-temporelle dans les systèmes OFDM1/MIMO, ...). Aujourd'hui, la complexité et le coût de ces systèmes sont très élevés; les concepteurs doivent pourtant parvenir à minimiser la consommation et la surface total du circuit, tout en garantissant les performances temporelles requises. Sur cette problématique globale, nous nous intéressons à l'optimisation des architectures des modules de brassage de données (réseau d'interconnexion, contrôleur...) devant réaliser une règle d'entrelacement définie par l'application et ayant pour objectif d'utiliser un réseau d'interconnexion défini par le concepteur. L'architecture que nous ciblons se compose d'éléments de calculs (PE0,...PEn), de mémoires de données utilisées pour stocker les opérandes et les résultats produits par les éléments de calculs (Mem0,...Memm), d'un réseau d'interconnexion reliant les éléments de calculs aux mémoires et d'une unité de contrôle. Le réseau d'interconnexion est défini par l'utilisateur et peut être basé sur différent modèles : cross-bar, réseaux de Benes, réseau de Bruinj, barrière de multiplexeurs, barrel-shifters (barillets), papillons... L'unité de contrôle est composée de deux parties : un contrôleur de réseau et un contrôleur de mémoires. Ces contrôleurs sont basés sur un ensemble de mémoires de contrôle (une ROM de contrôle par banc mémoire Mem dans l'architecture cible) contenant les mots de commande relatifs au fonctionnement du système. L'approche que nous proposons est à même d'optimiser cette partie de contrôle de l'architecture. Nous proposons plusieurs méthodologies d'exploration et de conception permettant de générer automatiquement une architecture d'entrelacement optimisée réalisant une règle de brassage de données, ou entrelacement, tel que définie par exemple dans un standard de communication. Les approches que nous proposons prennent en entrée (1) des diagrammes temporels (générés à partir de la règle d'entrelacement et de contraintes spécifiant les séquences d'accès parallèles aux données) et (2) une contrainte utilisateur sur le réseau d'interconnexion que doit utiliser l'architecture. Ce flot formalise ensuite ces contraintes de brassage des données sous la forme (1) d'un modèle matriciel des séquences de données qui devront être traitées par chaque processeur et (2) d'un Graphe de Conflit d'Adressage (ACG), dont les propriétés permettent une exploration efficace de l'espace des solutions architecturales. L'objectif est ensuite de générer une architecture cible, en garantissant un fonctionnement sans conflit d'accès mémoire (lorsque plusieurs processeurs veulent accéder en même temps à un même banc mémoire mais pour traiter des données différentes), en respectant la contrainte de réseau et en optimisant l'architecture obtenue (notamment concernant l'architecture de son contrôleur). Cette approche a été mise en oeuvre au sein d'un d'outil et appliquée sur plusieurs cas d'étude : High Speed Packet Access (HSPA), Ultra-WideBand (UWB) et une application Wimax. Ces expériences montrent qu'en comparaison aux approches de l'état de l'art nos approches permettent d'atteindre des gains en surface significatifs. Notamment, pour des applications Turbo Codes pour lesquels les gains sont très importants.