Brevet FR2987527A1 — publié le 20130830

Domaine technique La présente invention concerne un dispositif d'entrelacement / désentrelacement de données numériques. L'invention se situe dans le domaine de la transmission de données à haut débit, par exemple de signaux audio et/ou vidéo. Une application particulièrement intéressante de l'invention concerne l'entrelacement et/ou désentrelacement de données pour le codage et le décodage de codes correcteurs d'erreur, notamment des codes LDPC (pour Low Density Parity-Check Code en langue anglaise) ou des Turbo-codes Etat de la technique Les codes correcteurs d'erreur de type LDPC et les Turbo-codes sont bien connus dans l'état de la technique. On pourra, par exemple, se référer au brevet français antérieur FR 2 675 970 qui décrit le principe général des 15 Turbo-codes. Ces techniques de codage et de décodage sont basées sur un traitement itératif des données, ces dernières étant mélangées ou entrelacées, à chaque étape de traitement, jusqu'à obtenir une complète décorrélation des erreurs susceptibles d'être véhiculées. Ces techniques 20 utilisent un entrelaceur qui réalise une permutation itérative des symboles d'un code d'entrée. On a représenté sur la figure 1 l'architecture d'un dispositif d'entrelacement ou désentrelacement connu. Ce dispositif est destiné à entrelacer ou désentrelacer des données délivrées par n éléments de 25 traitement, référencés Po à Pn_i, disposés en parallèle, lesdites données représentant des symboles. Le dispositif d'entrelacement ou désentrelacement comporte un ensemble de m bancs mémoires, référencés Bo à disposés en parallèle et destinés à stocker des données en provenance ou à 30 destination des n éléments de traitement et un réseau d'interconnexion INT qui est interposé entre les éléments de traitement et les bancs mémoires pour aiguiller à tout instant les données des éléments de traitement vers les bancs mémoires ou inversement. Les données stockées dans les bancs mémoires sont les opérandes et les résultats des opérations de traitement réalisées dans les éléments de traitement. Les données à stocker dans n des m bancs mémoires sont classiquement générées simultanément par les n éléments de traitement. Généralement, le nombre m de bancs mémoire est supérieur ou égal au nombre n d'éléments de traitement. Dans le cas contraire, les données doivent être fournies par sous ensemble dont la taille est inférieure ou égale au nombre de bancs mémoire. Le réseau d'interconnexion INT et les bancs mémoires sont pilotés par une unité de contrôle CTRL dédiée. Plus précisément, l'unité de contrôle est chargée de fournir, à chaque instant, un mot de commande au réseau d'interconnexion et des séquences d'adressage et de contrôle aux bancs mémoire pour accéder aux données en lecture ou en écriture. L'unité de contrôle comporte classiquement une pluralité de mémoires de contrôle de type ROM (pour Read-Only Memory en langue anglaise) et un circuit de contrôle pour lire le contenu de ces mémoires. L'unité de contrôle comprend classiquement au moins une mémoire 2 0 de contrôle pour stocker les mots de commande du réseau d'interconnexion et une mémoire de contrôle pour stocker les séquences d'adressage et de contrôle des bancs mémoires. Ces séquences et ces mots de commande sont fonction de la règle d'entrelacement ou de désentrelacement à appliquer, du nombre n d'éléments de traitement, du 25 nombre m de bancs mémoires, de la structure du réseau d'interconnexion et de la taille des trames de données (nombre de symboles dans la trame) à traiter. En général, les quatre premiers paramètres, à savoir la règle d'entrelacement ou de désentrelacement, les nombres n et m et la structure du réseau d'interconnexion, ne varient pas et sont fixés par 30 l'équipement comprenant le dispositif d'entrelacement ou désentrelacement. Notamment, la règle d'entrelacement ou de désentrelacement est imposée par le standard de transmission supporté par l'équipement. L'équipement doit cependant être en mesure de gérer plusieurs tailles de trame pour ce standard, typiquement une centaine de tailles de trame voire plus. A chacune de ces tailles de trame est alors associé un mode de fonctionnement particulier du dispositif d'entrelacement ou de désentrelacement. Pour la mise en oeuvre de ces différents modes de fonctionnement, l'unité de contrôle du dispositif d'entrelacement ou de désentrelacement comporte généralement deux mémoires de contrôle pour chacun des modes de fonctionnement, à savoir une mémoire dite de réseau pour stocker les mots de commande du réseau d'interconnexion et une mémoire dite de contrôle d'accès pour stocker les séquences d'adressage et de contrôle des bancs mémoires pour le mode de fonctionnement considéré. Il en résulte que l'unité de contrôle du dispositif comporte deux mémoires de contrôle pour chaque mode de fonctionnement, le contenu de ces mémoires étant généralement calculé hors ligne par un algorithme de placement mémoire avant d'y être stocké. De tels dispositifs d'entrelacement ou de désentrelacement sont donc relativement coûteux en termes de surface sur silicium puisque la plupart des standards de transmission actuels et à venir, par exemple WiMAX (pour Worldwide Interoperability for Microwave Access en langue anglaise) ou LTE (pour Long Term Evolution), sont prévus pour implémenter plusieurs centaines de modes de fonctionnement. Un autre problème lié à la mise en oeuvre de ce type d'architecture d'entrelacement concerne les conflits d'accès aux bancs mémoires Bo à Brro. En effet, comme on peut le voir sur les figures 2 et 3, avec ce type d'architecture, il est possible que deux ou plusieurs éléments de traitement parmi les éléments Po à Pu_i producteurs ou utilisateurs de données tentent d'écrire ou, au contraire, de lire en même temps des données différentes 3 0 dans ou à partir d'un même banc mémoire. Il se produit alors des collisions et, pour les éviter, il convient alors de décaler ou d'arbitrer soigneusement les accès aux bancs mémoires, ce qui ralentit alors le processus de codage ou décodage. Des solutions à ce problème de collision existent. Ces dernières consistent essentiellement à modifier la règle d'entrelacement ou de désentrelacement ou à introduire des éléments mémorisant dans le réseau d'interconnexion de sorte que les accès simultanés à un même banc mémoire soient sérialisés ou trouver une affectation des données dans les bancs mémoire de sorte qu'il n'y ait pas de conflits d'accès. Plusieurs techniques ont été développées dans ce sens. Une première famille de techniques est basée sur la définition d'une règle d'entrelacement reposant sur une ou des permutation(s) régulière(s), par exemple circulaire(s) permettant d'implémenter un entrelaceur ayant un haut degré de parallélisme avec des performances équivalentes ou meilleures que celles des entrelaceurs connus, tout en permettant de réduire la complexité de l'architecture du réseau d'interconnexion, en particulier pour des applications à très haut débit. Ce type de solution a aussi pour avantage de réduire le coût de l'unité de contrôle en minimisant le nombre total de mémoires de contrôle utilisées. Une première technique appartenant à cette famille et appelée «turbo-code à roulettes» est décrite en détail dans le document FR 2 838 581. L'inconvénient de cette technique est qu'elle est basée sur la définition d'une règle d'entrelacement qui n'est a priori pas conforme à un standard de communication. Les standards ont depuis évolué pour reposer sur des permutations régulières plus ou moins complexes permettant d'implémenter plus aisément des entrelaceurs matériels parallèles. Malheureusement, les règles de permutation proposées ne permettent pas de supprimer l'ensemble des conflits. En effet, des conflits d'accès aux mémoires persistent pour certains parallélismes et/ou tailles de trames. Une deuxième famille de techniques propose d'ajouter des mémoires dans le réseau d'interconnexion afin d'assurer une temporisation des données en cas de situation de conflit. Ce type d'approche a cependant 2 98752 7 5 pour inconvénients d'augmenter la latence du circuit et d'augmenter la complexité du réseau d'interconnexion. De plus, il est nécessaire de procéder par simulation pour déterminer le dimensionnement des mémoires ajoutées. Un exemple de technique de ce type est décrite dans 5 le document «SoC-Network for Interleaving in Wireless Communications» de N. Wehn, MPSoC, 2004. Une troisième famille de techniques consiste à ranger les données dans les bancs mémoires de manière à éviter les conflits. Cette approche consiste à identifier les données qui sont destinées à être consommées ou 10 produites en même temps dans une matrice d'affectation. Bien que cette famille permette de trouver une assignation des données dans les bancs mémoires qui ne génère pas de conflit quelle que soit la règle d'entrelacement, elle présente toutefois un certain nombre d'inconvénients. En effet, elle ne permet pas de générer un accès mémoire qui soit simple à 15 mettre en oeuvre en utilisant des composants simples dans le réseau d'interconnexion. Par ailleurs, cette famille nécessite l'utilisation de deux mémoires de contrôle par mode de fonctionnement pour mémoriser les ordres d'accès naturel et entrelacés, ce qui augmente encore le coût du dispositif. 20 Un premier exemple de technique appartenant à cette famille est décrit dans l'article «Mapping Interleaving Laws to Parallel Turbo-decoder Architectures» de A.Tarable, S.Benedetto et G.Montorsi, IEEE volume 8, mars 2004. L'approche proposée consiste à effectuer une première affectation naïve des données dans les bancs mémoires, sans générer de 25 conflit puis à attribuer un banc mémoire aux données non affectées en corrigeant les conflits à l'aide d'une méthode dite de «recuit-simule» ou de «raffinement itératif». L'algorithme de recuit-simulé est relativement complexe à mettre en oeuvre et ne permet pas de déterminer, a priori, le délai nécessaire à l'obtention de la solution bien que ce délai soit borné. 30 Un second exemple est présenté dans le document FR 2 915 641 intitulé «Procédé et dispositif d'entrelacement de données». Ce document décrit un procédé permettant de trouver pour n'importe quelle règle d'entrelacement un placement des données dans les bancs mémoires qui garantit un accès sans conflits aux mémoires et optimise le réseau d'interconnexion selon les besoins du concepteur si la règle d'entrelacement le permet. Avec cette technique, l'unité de contrôle n'est pas optimisée et son architecture finale comprend autant de mémoires de contrôle que de bancs mémoires et cela pour tous les modes de fonctionnement à implémenter. Résumé de l'invention Un but de l'invention est de pallier tout ou partie des inconvénients et limites de l'état de la technique cités précédemment. En particulier, un but de l'invention est de proposer un dispositif d'entrelacement ou de désentrelacement de données numériques qui soit apte à mettre en oeuvre sans conflit d'accès mémoire la règle d'entrelacement ou de désentrelacement de tout type de standard de communication et dans lequel l'unité de contrôle présente un espace mémoire et un nombre de mémoires de contrôle réduits. Un autre but de l'invention est de proposer un dispositif 2 0 d'entrelacement ou de désentrelacement de données numériques ayant une unité de contrôle de coût réduit. L'invention a également pour but de proposer un dispositif d'entrelacement ou de désentrelacement.qui soit applicable aussi bien aux turbo-codes qu'aux codes LDPC. 25 A cet effet, on propose, selon l'invention, de rajouter dans l'unité de contrôle du dispositif un circuit de calcul apte à exécuter un algorithme de placement mémoire à chaque changement de mode de fonctionnement du dispositif. Ainsi, selon l'invention, l'algorithme de placement mémoire est exécuté à la volée par le dispositif d'entrelacement ou désentrelacement. 30 L'invention a pour objet un dispositif d'entrelacement ou désentrelacement de trames de données numériques délivrées par n éléments de traitement disposés en parallèle, n étant un entier naturel supérieur à 1, ledit dispositif comprenant - m bancs mémoires pour stocker des données en provenance ou à destination desdits éléments de traitement, m étant un entier naturel supérieur à 1, - un réseau d'interconnexion pour aiguiller les données entre lesdits éléments de traitement et lesdits bancs mémoires, et - une unité de contrôle comportant une mémoire de contrôle dans laquelle sont stockés des mots de commande du réseau d'interconnexion et des séquences d'adressage et de contrôle destinées à commander les bancs mémoires, lesdits mots de commande et lesdites séquences d'adressage et de contrôle étant fonction d'une règle d'entrelacement ou de désentrelacement à appliquer, de la taille des trames de données numériques, des nombres m et n et du réseau d'interconnexion, et un circuit de contrôle pour commander le réseau d'interconnexion et les bancs mémoire avec les mots de commande et les séquences d'adressage et de contrôle stockés dans la ladite mémoire de contrôle, remarquable en ce que l'unité de contrôle comprend en outre un circuit de calcul apte à générer en ligne des mots de commande et des séquences d'adressage et de contrôle garantissant un accès mémoire sans conflit en fonction de la règle d'entrelacement à appliquer, de la taille des trames de données numériques, du nombre n d'unités de traitement, du nombre m de bancs mémoires et du réseau d'interconnexion, ledit circuit de contrôle étant apte à écrire les mots de commande et les séquences d'adressage et de contrôle générés par ledit circuit de calcul dans ladite mémoire de contrôle. Le circuit de calcul exécute un algorithme de placement mémoire garantissant un accès mémoire sans conflit à chaque fois qu'au moins l'un des paramètres suivants change: - taille de trame des données numériques, - règle d'entrelacement ou de désentrelacement à appliquer, - nombre n éléments de traitement du dispositif, - nombre m de bancs mémoires du dispositif, - réseau d'interconnexion. Les résultats sont placés dans la mémoire de contrôle par le circuit de contrôle. Ainsi, il n'est plus nécessaire d'avoir une mémoire de contrôle pour chacun des modes de fonctionnement possible du dispositif, ce qui contribue à réduire le coût du dispositif. Par ailleurs, l'algorithme de placement mémoire n'est plus exécuté hors ligne mais en ligne. Selon un mode de réalisation particulier, la mémoire de contrôle comporte une mémoire, dite de réseau, pour stocker les mots de commande du réseau d'interconnexion et une mémoire, dite de contrôle d'accès, pour stocker les séquences d'adressage et de contrôle des bancs mémoires. Selon un mode de réalisation particulier, la mémoire de réseau et la mémoire de contrôle d'accès sont des mémoires volatiles. Le dispositif de l'invention comprend en outre au moins une mémoire de calcul pour stocker des données intermédiaires générées par ledit circuit de calcul. Cette mémoire de calcul est par exemple une mémoire interne au circuit de calcul ou à l'unité de contrôle. Selon un mode de réalisation particulier, ladite mémoire de calcul est une portion mémoire 2 0 desdits bancs mémoires. L'invention concerne également un dispositif de codage ou de décodage de trames de données numériques comprenant n éléments de traitement disposés en parallèle, n étant un entier naturel supérieur à 1, et un dispositif d'entrelacement ou de désentrelacement tel que défini 25 précédemment pour entrelacer ou désentrelacer les trames de données produites les éléments de traitement. D'autres avantages pourront encore apparaître à l'homme du métier à la lecture des exemples ci-dessous, illustrés par les figures annexées, donnés à titre illustratif. 30 Brève description des figures - La figure 1, déjà décrite, représente le schéma fonctionnel d'un dispositif d'entrelacement ou de désentrelacement de l'art antérieur; - Les figures 2 et 3, déjà décrites, représentent des schémas illustrant les problèmes de collision avec le dispositif de la figure 1; et - La figure 4 représente le schéma fonctionnel d'un dispositif d'entrelacement ou de désentrelacement conforme à l'invention. DESCRIPTION DETAILLEE D'AU MOINS UN MODE DE REALISATION Selon l'invention, il est proposé d'implanter directement, dans l'unité de contrôle CTRL du dispositif d'entrelacement ou de désentrelacement, un circuit de calcul apte à exécuter à la volée un algorithme de placement des données numériques dans les bancs mémoires Bo à Bm_i sans conflit d'accès. L'unité de contrôle CTRL du dispositif d'entrelacement ou de désentrelacement conforme à l'invention est décrite en référence à la figure 4. L'unité de contrôle CTRL comprend une mémoire réseau M1 dans laquelle sont stockés des mots de commande du réseau d'interconnexion et une mémoire de contrôle d'accès M2 dans laquelle sont stockées des séquences d'adressage et de contrôle destinées à commander l'accès aux bancs mémoires. Les mémoires M1 et M2 sont commandées en lecture et en écriture par le circuit de contrôle CC. Les mots de commande et les séquences d'adressage et de contrôle stockés dans les mémoires M1 et M2 sont générés par un circuit de calcul CAL. Selon l'invention, le circuit de calcul CAL génère des mots de commande et des séquences d'adressage et de contrôle garantissant un accès en lecture et en écriture sans conflit aux bancs mémoire Bo à Bm_i en fonction de paramètres internes qui ne sont pas susceptibles d'être modifiés, tels que la règle d'entrelacement à appliquer, le nombre n d'éléments de traitement Pi travaillant en parallèle, la structure du réseau d'interconnexion (papillons, registres à décalage, réseau de Bénès, ...) et de paramètres externes tels que la taille des trames à traiter. Pour cela, le circuit de calcul CAL exécute à la volée un algorithme de placement mémoire garantissant un accès sans conflit en fonction desdits paramètres internes et externes et les résultats de cette exécution sont stockées dans les mémoires M1 et M2. Cet algorithme est exécuté à chaque fois que l'un des paramètres internes ou externes est modifié. Dans le cas d'un terminal de communication destiné à fonctionner selon un standard de communication donné, la règle d'entrelacement à appliquer est celle imposée par le standard de communication du terminal, le réseau d'interconnexion est celui du terminal et le nombre d'éléments de traitement travaillant en parallèle est généralement le nombre n d'éléments de traitement Po à Pu_i contenus dans le terminal pour effectuer le codage ou le décodage des trames. Le seul paramètre susceptible de varier est la taille des trames. Dans ce cas, l'algorithme de placement mémoire est alors exécuté à chaque fois que la taille de trame change. Cet exemple est illustré par la figure 4. Selon une variante, le terminal est capable de fonctionner selon un mode de fonctionnement dit dégradé dans lequel seule une partie des n éléments de traitement travaillent, par exemple n/2, les autres éléments de traitement étant éteints ou mis en veille pour limiter la consommation du terminal. Dans ce cas, l'algorithme de placement mémoire est exécuté à chaque fois que la taille de trame change ou que l'on passe à un mode de fonctionnement dégradé. D'une manière générale, l'algorithme de placement mémoire est exécuté à chaque fois que l'un des paramètres internes ou externes est modifié. Cet algorithme est par exemple l'algorithme de faible complexité décrit dans l'un des trois documents suivants: - le document IEEE intitulé "A memory marpping approach for parallel interleaver design with multiples read and write accesses" de Cyrille 2 98752 7 11 Chavet et Philippe Coussy, publié dans "IEEE International Symposium on Circuits and Systems (ISCAS), 2010, Paris (France); - le document IEEE intitulé "An approach based on edge coloring of tripartite graph for designing parallel LDPC interleaver architecture" de 5 Awais Sani, Philippe Coussy, Cyrille Chavet et Eric Martin, publié dans "IEEE International Symposium on Circuits and Systems (ISCAS), 2011, Rio de Janeiro (Brésil); - le document IEEE intitulé "A methodology based on transportation problem modeling for designing parallel interleaver architectures" de Awais 10 Sani, Philippe Coussy, Cyrille Chavet et Eric Martin, publié dans 36th IEEE International Conference on Acoustics, Speech and Signal Processing, 2011, Prague (République Tchèque). Lorsque le circuit de calcul CAL exécute l'algorithme de placement mémoire, les données intermédiaires sont stockées dans des mémoires 15 internes de l'unité de contrôle CTRL ou éventuellement dans les bancs mémoires. Au final, les mots de commande et les séquences d'adressage et de contrôle générés par le circuit de calcul sont placés dans les mémoires M1 et M2 par le circuit de contrôle CC. Selon un mode de réalisation particulier, les mémoires M1 et M2 sont deux portions d'une 2 0 même mémoire de contrôle. Le circuit de calcul CAL est capable de générer les mots de commande et les séquences d'adressage et de contrôle pour tous les modes de fonctionnement des nouveaux standards de communication, par exemple LTE ou WIMAX, si on lui fournit la règle d'entrelacement à 25 appliquer, le nombre d'éléments de traitement Pi travaillant en parallèle, la structure du réseau d'interconnexion à commander et la taille des trames. L'algorithme est ré-exécuté à chaque fois que l'un des ces paramètres est modifié. L'ensemble des modes de fonctionnement d'un standard de communication peuvent être mis en oeuvre sans avoir à utiliser des 30 dizaines, voire des centaines, de mémoires ROM dans le dispositif. Bien que l'invention ait été décrite en liaison avec un mode de réalisation particulier, il est bien évident qu'elle n'y est nullement limitée et qu'elle comprend tous les équivalents techniques des moyens décrits ainsi que leurs combinaisons si celles-ci entrent dans le cadre de l'invention.5 REVENDICATIONS1) Dispositif d'entrelacement ou désentrelacement de trames de données numériques délivrées par n éléments de traitement (Po... P,-,_1) disposés en parallèle, n étant un entier naturel supérieur à 1, ledit dispositif comprenant - m bancs mémoires (Bo... Bm_i) pour stocker des données en provenance ou à destination desdits éléments de traitement, m étant un entier naturel supérieur à 1, - un réseau d'interconnexion (INT) pour aiguiller les données entre lesdits éléments de traitement et lesdits bancs mémoires, et - une unité de contrôle (CTRL) comportant une mémoire de contrôle (M1,M2) dans laquelle sont stockés des mots de commande du réseau d'interconnexion et des séquences d'adressage et de contrôle destinées à commander les bancs mémoires, lesdits mots de commande et lesdites séquences d'adressage et de contrôle étant fonction d'une règle d'entrelacement ou de désentrelacement à appliquer, de la taille des trames de données numériques, des nombres m et n et du réseau d'interconnexion, et un circuit de contrôle (CC) pour commander le réseau 2 0 d'interconnexion et les bancs mémoire avec les mots de commande et les séquences d'adressage et de contrôle stockés dans la ladite mémoire de contrôle, caractérisé en ce que l'unité de contrôle (CTRL) comprend en outre un circuit de calcul (CAL) apte à générer des mots de commande et des 25 séquences d'adressage et de contrôle garantissant un accès mémoire sans conflit en fonction de la règle d'entrelacement à appliquer, de la taille des trames de données numériques, du nombre n d'unités de traitement, du nombre m de bancs mémoires et du réseau d'interconnexion, ledit circuit de contrôle (CC) étant apte à écrire les mots de commande et les 30 séquences d'adressage et de contrôle générés par ledit circuit de calcul dans ladite mémoire de contrôle. 2) Dispositif selon la revendication 1, caractérisé en ce que le circuit de calcul (CAL) est apte à exécuter un algorithme de placement mémoire garantissant un accès mémoire sans conflit à chaque changement d'au moins l'un des paramètres suivants: - taille de trame des données numériques, - règle d'entrelacement ou de désentrelacement à appliquer, - nombre n éléments de traitement du dispositif, - nombre m de bancs mémoires du dispositif, - réseau d'interconnexion. 10 3) Dispositif selon la revendication 1 ou 2, caractérisé en ce que la mémoire de contrôle comporte une mémoire, dite de réseau (M1), pour stocker les mots de commande du réseau d'interconnexion et une mémoire, dite de contrôle d'accès (M2), pour stocker les séquences 15 d'adressage et de contrôle des bancs mémoires. 4) Dispositif selon la revendication 3, caractérisé en ce que la mémoire de réseau et la mémoire de contrôle d'accès sont des mémoires volatiles. 20 5) Dispositif de codage ou de décodage de trames de données numériques comprenant n éléments de traitement disposés en parallèle, n étant un entier naturel supérieur à 1, caractérisé en ce qu'il comporte en outre un dispositif d'entrelacement ou de désentrelacement selon l'une 25 quelconque des revendications 1 à 4.