Brevet FR2983665A1 — publié le 20130607

Procédé de génération d'un code correcteur linéaire maximisé, procédé et dispositif de décodage d'un tel code L'invention a pour objets un procédé de génération d'un code correcteur linéaire maximisé, un procédé et dispositif de décodage d'un tel code. Elle s'applique notamment aux domaines des codes correcteurs d'erreurs et des technologies nanométriques. Dans un système numérique, les données sont habituellement enregistrées dans une mémoire numérique sous forme de valeurs binaires appelées bits. Des erreurs peuvent apparaître sur les données mémorisées et peuvent être transitoires ou permanentes, comme explicité ci-après. Si ces erreurs ne sont pas corrigées ou masquées, elles peuvent engendrer des erreurs de fonctionnement et finalement la défaillance du système. Les erreurs transitoires sont produites par des interférences avec l'environnement ou sont dues aux caractéristiques intrinsèques des mémoires produites à l'aide des technologies nanométriques. Les erreurs permanentes sont la conséquence de défauts de la structure physique des circuits, ces défauts apparaissant pendant la production des circuits et/ou à cause du vieillissement. Une densité élevée de défauts matériels dans un système de mémorisation se traduit par un nombre important d'erreurs permanentes. Afin de garantir un niveau d'intégrité des données mémorisées acceptable et/ou pour augmenter le rendement de production, certains systèmes électroniques utilisent des codes, désignés habituellement par l'acronyme ECC venant de l'expression anglo-saxonne « Error Correcting Codes » ou EDAC pour « Error Detection And Correction » codes. Dans des mémoires numériques bénéficiant d'une protection de type ECC, les données sont encodées lors de l'écriture desdites données dans la mémoire. Lors de l'encodage de données avec un code ECC, des bits de vérification appelés aussi bits de redondance, sont ajoutés aux bits de données afin de former des mots de code. Les mots de code d'un code correcteur linéaire sont définis à l'aide d'une matrice de parité H. Un vecteur binaire V est un mot de code seulement si son produit avec la matrice H génère un vecteur nul. Lors de la lecture des données présentes dans une mémoire, chaque mot de code linéaire V est vérifié en évaluant le produit matriciel H.V. Le résultat de cette opération est un vecteur appelé aussi syndrome. Si le syndrome est un vecteur nul, le mot de code est considéré comme correct. Un syndrome non-nul indique la présence d'au moins une erreur. Si le syndrome permet d'identifier les positions des bits affectés, le mot de code est corrigé. Différents codes ECC linéaires peuvent être mis en oeuvre avec des capacités de détection et de correction d'erreurs différentes. A titre d'exemple, le codage de Hamming permet de corriger une erreur simple, c'est-à-dire une erreur qui affecte un seul bit. Cette capacité de correction est qualifiée de SEC, acronyme venant de l'expression anglo-saxonne « Single Error Correction ». Un autre exemple de code ECC est le code DEC, acronyme venant de l'expression anglo-saxonne «Double Error Correction». Un code DEC permet la correction d'erreurs doubles, c'est-à-dire d'erreurs affectant deux bits dans un mot de code. Bien évidement, les codes de cette famille sont aussi capables de corriger une erreur simple. La capacité de correction théoriquement atteignable des codes ECC habituellement utilisés est rarement utilisée. Cela est dû au fait que le nombre N de bits de données dans un mot de code stocké dans une mémoire est habituellement une puissance de 2. En d'autres termes, N=k*2`1 expression dans laquelle n et k sont des entiers. N est donc un multiple d'une puissance de 2. A titre d'illustration, si un code SEC est utilisé, le nombre c de bits de vérification doit remplir la condition suivante : 2c - 1 > N + c (1) Si les mots de données à protéger sont tels que N = 32, alors le nombre de bits de vérification requis est c = 6. Le nombre A de syndromes non utilisés par un code SEC linéaire pour la correction d'erreurs simples peut être déterminé en utilisant l'expression suivante :35 A= 2c-N-c- 1 (2) Dans le cas du code SEC pris en exemple, ce nombre de syndromes non utilisés est A = 25. Ce nombre A de syndromes non utilisés signifie que jusqu'à A erreurs multiples différentes peuvent être corrigées en plus des erreurs simples pouvant être corrigées par le code SEC. Plus généralement, le nombre A de syndromes non utilisés par un code ECC linéaire en tant que syndromes permettant la correction d'un nombre EC d'erreurs simples ou multiples peut être déterminé en utilisant l'expression suivante : A = 2c - EC - 1 (3) Dans le cas d'un code DEC utilisé pour protéger des mots comprenant N = 32 bits de données, l'utilisation de 12 bits de vérification est nécessaire. Un mot de code a donc une taille de 44 bits. En conséquence, un code DEC doit pouvoir corriger 44 erreurs simples et (43 x 44)/2 = 946 erreurs doubles. Par conséquent, un nombre de EC = 990 erreurs simples et doubles sont corrigeable et l'expression (3) indique que la capacité de correction non-utilisée est de A. = 212 _ 990 - 1 = 3105 erreurs. Pour un nombre de bits de vérification donné, la capacité de correction théoriquement atteignable n'étant pas entièrement utilisée. Ainsi, la marge restante peut être exploitée afin de permettre la correction de certaines erreurs supplémentaires. Dans la description, l'expression code de base désigne un code linéaire ECC que l'on cherche à modifier en améliorant sa capacité de correction. Cette amélioration est rendue possible en mettant en oeuvre un mécanisme de correction d'erreurs dites supplémentaires. Une erreur supplémentaire désigne une erreur qui n'est pas corrigée par le code de base mais qui l'est une fois que ledit code a été amélioré. Ainsi, certaines erreurs doubles peuvent être corrigées dans le cas des codes SEC et certaines erreurs triples peuvent être corrigées dans le cas des codes DEC. Des codes SEC permettant la correction d'erreurs simples ainsi que la correction d'un nombre restreint d'erreurs doubles ont fait notamment l'objet de plusieurs brevets. On peut citer à titre d'exemple les brevets US3755779 et US3328759 dans lesquels sont décrits des méthodes de codage où un bit supplémentaire de vérification est ajouté par rapport au nombre de bits de vérification nécessaire à l'implémentation d'un code SEC traditionnel. Dans ces exemples, les erreurs doubles affectant des paires de bits de positions adjacentes sont corrigées. La capacité de correction théoriquement atteignable est cependant loin d'être entièrement utilisée. Des codes DEC permettant la correction d'erreurs simples, doubles ainsi que la correction d'un nombre restreint d'erreurs affectant plus de deux bits ont été proposés dans l'article de S. Shamshiri et K.-T. Cheng Error-locality-aware linear coding to correct multi-bit upsets in SRAM, IEEE International Test Conference, 2010. L'utilisation de ce type de codes permet la correction d'erreurs impliquant plus de deux bits de positions adjacentes dans le mot de code ou d'erreurs présentes dans un groupe restreint de bits de positions adjacentes. La aussi, la capacité de correction théoriquement atteignable est loin d'être atteinte. Un but de l'invention est notamment de pallier les inconvénients précités. A cet effet l'invention a pour objet un procédé de génération d'un code correcteur linéaire maximisé à partir d'un code correcteur linéaire de base, le code correcteur de base et le code correcteur linéaire maximisé étant associés à une même matrice de parité H, ladite matrice étant utilisée pour générer des syndromes, lesdits syndromes étant utilisés pour le décodage de mots de code. Le procédé comprend une étape d'identification des syndromes non utilisés pour le décodage du code correcteur linéaire de base, une étape d'identification des erreurs pouvant affecter les mots de codes et permettant d'obtenir lesdits syndromes non utilisés lorsqu'un mot de code est multiplié par la matrice H, une étape de sélection d'une unique erreur pour chaque syndrome non utilisé parmi les erreurs identifiées, ladite erreur étant appelée erreur supplémentaire. Selon un aspect de l'invention, l'étape de sélection peut utiliser un critère de choix d'au moins une erreur par syndrome non utilisé, l'erreur sélectionnée étant associée à une probabilité d'occurrence plus importante que la probabilité d'occurrence des autres erreurs associées au même syndrome non utilisé. Selon un autre aspect de l'invention, l'étape de sélection peut utiliser un critère de choix d'au moins une erreur par syndrome non utilisé, l'erreur sélectionnée étant choisie parmi les erreurs associées à un même syndrome non utilisé de sorte que le nombre de bits du mot de code affecté par cette erreur soit minimal. Selon un autre aspect de l'invention, l'étape de sélection peut utiliser un critère de choix d'au moins une erreur parmi les erreurs associées à un même syndrome non utilisé de sorte que le nombre de bits de données du mot de code affecté par cette combinaison soit minimal. Dans un mode de réalisation, l'étape de sélection utilise un critère de choix d'une erreur parmi les erreurs associées à un même syndrome non utilisé de manière à ce que tous les bits de données ou tous les bits du mot de code soient affectés par le même nombre d'erreurs. L'invention a aussi pour objet un procédé de décodage de mots de code générés en utilisant un code correcteur linéaire maximisé obtenu par le procédé décrit précédemment et comportant une étape de détermination d'un syndrome à partir d'un mot de code, une étape vérifiant si ledit syndrome est un syndrome supplémentaire et de détermination de l'erreur supplémentaire associée à ce syndrome non utilisé lorsqu'un tel syndrome est identifié, une étape de correction de l'erreur identifiée. L'invention a aussi pour objet un dispositif de décodage de mots de code générés en utilisant un code correcteur linéaire maximisé obtenu par le procédé décrit précédemment, ledit dispositif comportant des moyens pour déterminer un syndrome à partir d'un mot de code, des moyens pour identifier si ledit syndrome est un syndrome non utilisé, des moyens pour déterminer quelle est l'erreur supplémentaire associée au syndrome non utilisé et pour la corriger lorsqu'un tel syndrome est identifié. L'invention a notamment comme avantage d'améliorer la capacité de correction des codes linéaires ECC utilisés habituellement pour protéger les données stockées dans une mémoire sans que le nombre de bits de vérification soit augmenté. D'autres caractéristiques et avantages de l'invention apparaîtront à l'aide de la description qui suit, donnée à titre illustratif et non limitatif et faite en regard des dessins annexés parmi lesquels : - la figure 1 donne un exemple de matrice de parité H associée à un code correcteur de type SEC et des syndromes non utilisés pour la correction des erreurs simples ; - la figure 2 donne un exemple de matrice de parité H associée à un code correcteur d'erreur de type DEC et d'un syndrome non-utilisé pour la correction des erreurs simples ou doubles ; - la figure 3 donne un exemple de procédé de génération d'un code correcteur linéaire maximisé ; - la figure 4 donne un exemple de dispositif de décodage d'un code correcteur linéaire maximisé. La figure 1 donne un exemple de matrice de parité H 100 associée à un code correcteur de type SEC et des syndromes non utilisés pour la correction des erreurs simples. Le code mis en oeuvre à l'aide de cette matrice assure la correction des erreurs simples pouvant survenir sur tous les bits du mot de code. Chacune des colonnes de la matrice correspond au syndrome d'une erreur simple affectant le bit du mot de code ayant la position correspondante, c'est-à-dire le bit du mot de code avec le même index que la colonne de la matrice. Dans cet exemple, un mot de code comprend c = 4 bits de vérification et N = 8 bits de données. Les huit bits de données d'un mot de code sont notés de Vo à V7 et les quatre bits de vérification de V8 à V11 . L'utilisation de l'expression (2) montre qu'il est possible de corriger jusqu'à A = 3 erreurs multiples supplémentaires en plus des erreurs simples pouvant être déjà corrigées. Il est par exemple possible de choisir de corriger les erreurs supplémentaires suivantes : - l'erreur double affectant les bits V9 et V10 et correspondant à l'un des trois syndromes non utilisés 101 ; - l'erreur double affectant les bits V9 et V11 et correspondant à un autre des trois syndromes non utilisés 102 ; - l'erreur double affectant les bits V10 et V11 et correspondant à un autre des trois syndromes non utilisés 103. En résumé, en plus de la correction d'erreurs simples affectant le mot de code, trois erreurs doubles sont corrigeables sur les soixante six erreurs doubles possibles. La figure 2 donne un exemple de matrice de parité H 200 associée à un code correcteur d'erreur de type DEC et d'un syndrome non-utilisé pour la correction des erreurs simples ou doubles. Ce code permet la correction d'erreurs simples et d'erreurs doubles pouvant affecter tous les bits des mots de code. Dans cet exemple, les mots de code ont une longueur de seize bits et comprennent N = 8 bits de données Vo à V7 et c = 8 bits de vérification V8 à V15. Il y a donc seize erreurs simples et cent-vingt erreurs doubles possibles. Chacune des colonnes de la matrice 200 correspond au syndrome de l'erreur simple qui peut affecter un des seize bits du mot de code. Les syndromes permettant d'identifier les erreurs multiples sont donnés par la somme modulo-2, c'est-à-dire bit par bit, des colonnes de la matrice 200 correspondant aux positions des bits corrompus. A partir de l'expression (3), on peut calculer pour ce type de code la différence A = 28 - 136 - 1 = 119 qui correspond aux syndromes non utilisés en tant que syndromes visant à corriger les seize erreurs simples et les cent-vingt erreurs doubles ou à identifier le cas sans erreur. Ainsi jusqu'à A. = 119 erreurs multiples différentes peuvent être potentiellement corrigées sur les cinq cent soixante erreurs triples possibles. Parmi ces erreurs, on peut par exemple choisir de corriger l'erreur triple pouvant affecter les bits V8, V9 et V11 et correspondant au syndrome 201. La figure 3 donne un exemple de procédé de génération d'un code correcteur linéaire maximisé à partir d'une matrice de parité H donnée. Ce procédé permet d'améliorer la capacité de correction d'un code de base. La capacité de correction du code avant amélioration est appelé capacité de correction de base. Le principe essentiel de ce procédé est d'associer des erreurs supplémentaires à corriger à toutes ou une partie des syndromes qui ne sont pas utilisés par le code de base. La manière d'associer un syndrome non utilisé à une erreur supplémentaire à corriger peut s'appuyer sur l'utilisation d'un ou plusieurs critères de choix. En effet, des erreurs différentes affectant un mot de code peuvent mener après multiplication dudit mot avec la matrice de parité H au même syndrome non utilisé. Pour que ce syndrome soit utilisé une de ces erreurs supplémentaires devra être sélectionnée en utilisant par exemple un ou plusieurs critères définis par la suite. Le procédé utilise comme entrées 300 la matrice de parité H du code de base pour lequel l'on veut étendre la capacité de correction ainsi que des informations relatives à ce code, comme par exemple la capacité de correction de base et la liste des erreurs déjà corrigeables. Une première étape 301 du procédé vise à identifier les syndromes utilisés par le code de base et à identifier les syndromes non utilisés en vue de la correction d'erreurs supplémentaires. Lesdits syndromes non utilisés peuvent être mémorisés 301 dans une liste Lsynd par exemple. Dans une deuxième étape 302 du procédé, pour chaque syndrome de la liste Lsynd, une liste Lerr des erreurs supplémentaires générant ce syndrome est construite. Il y a donc autant de liste Lerr que de syndromes non utilisés contenus dans la liste Lynd. Pour chaque syndrome de la liste Lsynd, l'une des erreurs identifiée dans la liste Lerr correspondante est ensuite sélectionnée, l'erreur ainsi sélectionnée correspondant à une erreur supplémentaire corrigeable. Cette sélection peut être réalisée en utilisant différents critères. Il est possible d'appliquer un unique critère ou plusieurs critères de sélection combinés entre eux, ces critères devant être appliqués de manière à identifier une unique erreur supplémentaire pour chaque syndrome non utilisé. Ainsi, lors du décodage, les syndromes non utilisés permettent de corriger des erreurs qui n'étaient pas prises en compte par le code de base. Le code de base linéaire ECC est alors maximisé, c'est-à-dire que le code ainsi dérivé dudit code de base présente une capacité de correction optimisée proche du maximum théorique. Des exemples de critères pouvant être appliqués sont donnés ci- après. Un premier critère de sélection d'une ou plusieurs erreurs associées à un syndrome non utilisé présent dans la liste Lsynd est de trouver la ou les erreurs dans la liste Lerr qui ont la plus grande probabilité d'apparition. L'utilisation de ce critère présuppose que l'on possède des informations statistiques sur l'occurrence des erreurs. Un deuxième critère de sélection d'une ou plusieurs erreurs associées à un syndrome non utilisé dans la liste Lsynd est de garder dans la liste Lerr seulement les erreurs qui affectent un nombre minimum de bits du mot de code. Un troisième critère de sélection d'une ou plusieurs erreurs associées à un syndrome non utilisé est de ne sélectionner que les erreurs de la liste Lerr qui affectent le moins de bits de données possible. Les erreurs qui ne sont pas prises en compte par le code de base et affectant seulement les bits de vérification peuvent être ignorées. Un quatrième critère de sélection des erreurs associées aux syndromes non utilisés est de choisir une erreur dans chaque liste Lerr de manière à ce que tous les bits de données ou tous les bits du mot de code soient affectés par le même nombre d'erreurs. Comme le troisième critère, le but est de minimiser la latence du décodeur du code ECC maximisé. Dans l'exemple de la figure 3, deux étapes 303, 304 sont appliquées de manière à appliquer successivement deux critères de sélection d'erreurs supplémentaires. Ces deux critères consistent par exemple dans un premier temps 303 à la sélection des erreurs qui affectent un nombre minimum de bits du mot de code, puis dans un second temps 304 en une sélection parmi les erreurs restantes des erreurs ou de l'erreur affectant un nombre minimum de bits de données. Le quatrième critère peut ensuite être appliqué aux listes Lerr qui ont plus d'un élément. Le résultat de l'application du procédé est une liste de syndromes non utilisés auxquels sont associées des erreurs supplémentaires corrigeables. Un code correcteur ECC maximisé a ainsi été construit. Avantageusement, les erreurs supplémentaires associées aux syndromes non utilisés peuvent être des erreurs qui affectent plus de bits que les erreurs multiples déjà corrigeables par le code ECC de base. Le code peut être construit en sélectionnant une matrice H de manière à ce qu'une classe particulière d'erreurs multiples corresponde à des syndromes non-utilisés par le code ECC de base. Ainsi, lorsque le procédé de génération d'un code correcteur linéaire ECC maximisé est utilisé, ces erreurs multiples vont se retrouver dans les listes Lerr, ce qui permettra leur sélection, selon les critères de sélections utilisés. Avantageusement, l'architecture d'un composant mémoire utilisant un code de base pour protéger ses données mémorisées ne nécessite pas de modification pour mettre en oeuvre le code ECC maximisé. La figure 4 donne un exemple de dispositif de décodage d'un code correcteur linéaire ECC maximisé. Les bits des mots de code 400 sont utilisés en entrée du dispositif pour la génération 401 des syndromes d'erreur 402. Les bits des syndromes 402 sont ensuite utilisés pour l'identification 403 des erreurs à corriger. Un syndrome 402 peut être un syndrome classique, c'est-à-dire un syndrome permettant la correction d'une erreur corrigeable par le code de base. Un syndrome 402 peut aussi être un syndrome non utilisé. Ainsi, le dispositif de décodage comprend des moyens pour identifier si le syndrome est un syndrome non utilisé par un code de base et donc d'identifier si le mot de code comprend une erreur classique 407 ou bien une erreur supplémentaire 408. Cette identification se traduit par un mot 404 dont les bits indiquent les inversions de valeur des bits à réaliser 405 sur le mot de code 400 afin d'obtenir un mot de code corrigé 406 ou seulement des bits de données corrigés. Dans un tel dispositif, tous ou seulement une partie des 30 syndromes non utilisés par le code de base peuvent être employés afin de permettre la correction des erreurs supplémentaires. REVENDICATIONS1- Procédé de génération d'un code correcteur linéaire amélioré à partir d'un code correcteur linéaire de base, le code correcteur de base et le code correcteur linéaire maximisé étant associés à une même matrice de parité H, ladite matrice étant utilisée pour générer des syndromes, lesdits syndromes étant utilisés pour le décodage de mots de code, ledit procédé étant caractérisé en ce qu'il comprend : - une étape (301) d'identification des syndromes non utilisés pour le décodage du code correcteur linéaire de base; - une étape (302) d'identification des erreurs pouvant affecter les mots de codes et permettant d'obtenir lesdits syndromes non utilisés lorsqu'un mot de code est multiplié par la matrice H ; - une étape de sélection (303, 304) d'une unique erreur pour chaque syndrome non utilisé parmi les erreurs identifiées (302), ladite erreur étant appelée erreur supplémentaire. 2- Procédé selon la revendication 1 dans lequel l'étape de sélection utilise un critère de choix d'au moins une erreur par syndrome non utilisé, l'erreur sélectionnée étant associée à une probabilité d'occurrence plus importante que la probabilité d'occurrence des autres erreurs associées au même syndrome non utilisé. 3- Procédé selon l'une des revendications précédentes dans lequel l'étape de sélection utilise un critère de choix d'au moins une erreur par syndrome non utilisé, l'erreur sélectionnée étant choisie parmi les erreurs associées à un même syndrome non utilisé de sorte que le nombre de bits du mot de code affecté par cette erreur soit minimal. 4- Procédé selon l'une des revendications précédentes dans lequel l'étape de sélection utilise un critère de choix d'au moins une erreur parmi les erreurs associées à un même syndrome nonutilisé de sorte que le nombre de bits de données du mot de code affecté par cette combinaison soit minimal. 5- Procédé selon l'une des revendications précédentes dans lequel l'étape de sélection utilise un critère de choix d'une erreur parmi les erreurs associées à un même syndrome non utilisé de manière à ce que tous les bits de données ou tous les bits du mot de code soient affectés par le même nombre d'erreurs. 6- Procédé de décodage de mots de code générés en utilisant un code correcteur linéaire maximisé obtenu par le procédé selon l'une des revendications 1 à 6 et comportant : - une étape (401) de détermination d'un syndrome à partir d'un mot de code (400) ; - une étape (403) vérifiant si ledit syndrome est un syndrome supplémentaire (408) et de détermination de l'erreur supplémentaire associée à ce syndrome non utilisé lorsqu'un tel syndrome est identifié ; - une étape (405) de correction de l'erreur identifiée. 7- Dispositif de décodage de mots de code générés en utilisant un code correcteur linéaire maximisé obtenu par le procédé selon l'une des revendications 1 à 6, ledit dispositif comportant des moyens (401) pour déterminer un syndrome à partir d'un mot de code, des moyens (403, 408) pour identifier si ledit syndrome est un syndrome non utilisé, des moyens pour déterminer quelle est l'erreur supplémentaire associée au syndrome non utilisé et pour la corriger (405) lorsqu'un tel syndrome est identifié.30