FR2831970A1

FR2831970A1 - Procede de memorisation de donnees avec correction d'erreur

Info

Publication number: FR2831970A1
Application number: FR0114231A
Authority: FR
Inventors: Michael Nicolaidis
Original assignee: Iroc Technologies SA
Current assignee: Iroc Technologies SA
Priority date: 2001-11-02
Filing date: 2001-11-02
Publication date: 2003-05-09

Abstract

L'invention concerne un procédé de mémorisation de données permettant des détections et corrections d'erreur dans une mémoire organisée pour lire et écrire des mots d'un premier nombre (m) de bits et éventuellement pour modifier une partie seulement d'un tel mot, comprenant les étapes suivantes :associer un code de détection et de correction d'erreur à un groupe d'un deuxième nombre k >= 1 de mots; etassocier à chaque écriture une opération de vérification et, s'il y a lieu de correction d'erreur dans le groupe de mots associé au mot dans lequel on réalise une opération d'écriture totale ou partielle.

Description

1 PROCÉDÉ DE MÉMORISATION DE DONNÉES AVEC CORRECTION D'ERREUR

La présente invention concerne l'organisation d'une mémoire associée à des moyens de correction d'erreur.

Etant donné la miniaturisation actuelle des circuits intégrés et notamment des circuits de mémoire, les points mémoire assurent la mémorisation de bits de données en agissant sur un nombre de porteurs de plus en plus petit. En conséquence, chaque point mémoire est de plus en plus susceptible d'être affecté d'une erreur, c'est-à-dire d'une inversion de la donnée mémorisée (passage de 0 à 1 ou de 1 à 0), notamment par suite d'une irradiation par des particules. Pour remédier à cet inconvénient on a développé des codes de correction d'erreur, chaque mot mémoire étant associé à un code de correction d'erreur. Quand on lit le contenu d'un mot et le code de correction d'erreur associé, et que l'on calcule un syndrome entre le mot mémorisé et le code de correction d'erreur, ce syndrome permet de déterminer si le mot est affecté d'une erreur ou non, de déterminer l'emplacement de l'erreur et de corriger cette erreur.

Des exemples de codes de correction d'erreur connus sont le code de Hamming et le code de Reed-Solomon. En calculant un syndrome entre le mot mémorisé et le code de correction d'erreur, on peut retrouver si le mot mémorisé est affecté d'une

erreur et l'emplacement de l'erreur. Il est alors possible de corriger le mot mémorisé. On notera que l'on distingue les simples codes de détection d'erreur, par exemple l'association à un mot d'un bit de parité, qui permettent de détecter l'existence d'une erreur, des codes de correction d'erreur qui permettent de déterminer l'emplacement de l'erreur et donc de la corriger.

Un inconvénient évident de l'utilisation de codes de correction d'erreur réside dans la quantité de bits qu'ils nécessitent. Par exemple, pour des mots de plus de quatre bits, un code de Hamming nécessite n+1 bits pour permettre la correction d'une erreur, et seulement d'une erreur, dans un mot de 2n bits. Ceci signifie que, pour un mot de huit (23) bits, il faudra quatre bits de code, et même cinq bits si l'on ajoute au code de correction d'erreur un code de parité. Pour un mot de 64 (25) bits, il faudra cinq ou six bits de code de correction d'erreur. Il est clair que la surface occupée par la partie de la mémoire allouée au code de correction d'erreur dépend de la longueur des mots mémorisés et diminue quand cette longueur augmente.

Par contre, de nombreuses mémoires sont prévues pour faire des opérations sur des mots relativement courts.

D'autre part, on utilise souvent dans les mémoires des organisations dans lesquelles il est possible de changer seulement une portion d'un mot. C'est ce que l'on appelle des opérations masquables, c'est-à-dire que l'on prévoit un masque lors d'une opération d'écriture pour n'affecter que certains des bits d'un mot. Il se pose alors un problème qui est que le code de correction d'erreur du mot modifié ne correspond plus à ce mot. Ceci amène à associer un code de correction d'erreur à chaque bit d'un mot, ce qui nécessite comme on l'a vu ci-dessus une utilisation de mots de code extrêmement longs par rapport aux mots mémorisés.

Ainsi, un objet de la présente invention est de prévoir une organisation de mémoire associée à un système de correction d'erreur dans laquelle on puisse utiliser des mots de

courte longueur tout en utilisant un nombre de bits de code de correction d'erreur raisonnable, sans augmenter excessivement la complexité ou la consommation du circuit.

Un autre objet de la présente invention est de prévoir une organisation de mémoire dans laquelle on puisse réaliser des opérations masquables et utiliser de façon simple un système de correction d'erreur.

Pour atteindre ces objets, la présente invention prévoit un procédé de mémorisation de données permettant des détections et corrections d'erreur dans une mémoire organisée pour lire et écrire des mots d'un premier nombre (m) de bits et éventuellement pour modifier une partie seulement d'un tel mot, comprenant les étapes suivantes : associer un code de détection et de correction d'erreur à un groupe d'un deuxième nombre k > l de mots ; et associer à chaque écriture une opération de vérification et, s'il y a lieu, de correction d'erreur dans le groupe de mots associé au mot dans lequel on réalise une opération d'écriture totale ou partielle.

Selon un mode de réalisation de la présente invention, chaque mot est un mot long de M bits comprenant un troisième nombre déterminé r de mots élémentaires à m bits.

Selon un mode de réalisation de la présente invention, un code de détection d'erreur est associé à chaque mot ; et chaque opération d'écriture est précédée d'une lecture du mot considéré et de son code de détection d'erreur et, en cas d'erreur, de la lecture du groupe de mots et du code de correction d'erreur en vue de la correction des erreurs et de la modification du code de correction d'erreur.

Selon un mode de réalisation de la présente invention, on effectue une écriture dans seulement au moins un bit d'un mot, ou dans seulement les m bits d'un mot élémentaire d'un mot long, et on procède aux étapes suivantes : lire les autres bits du groupe de mots, calculer les codes de correction d'erreur pour ces autres bits et pour toutes

les valeurs possibles des positions de bits dans lesquelles on écrit, et déterminer celle des valeurs possibles pour laquelle on obtient une erreur minimale ; et si cette erreur minimale est nulle, considérer que l'écriture a réussi et calculer un nouveau code de correction d'erreur ; si cette erreur minimale est non nulle, corriger les bits en erreur aux positions autres que celles où on a écrit et calculer un nouveau code de correction d'erreur.

Selon un mode de réalisation de la présente invention, le procédé est appliqué à un mot constituant à lui seul le groupe de mots.

Selon un mode de réalisation de la présente invention, des erreurs sont susceptibles de survenir dans un seul mot d'un groupe de mots, un code de détection d'erreur est associé à chaque mot, et le code de correction d'erreur est calculé sous forme d'un OU Exclusif des codes de correction d'erreur de chaque mot.

Selon un mode de réalisation de la présente invention, on effectue une écriture dans seulement au moins un bit d'un mot d'un groupe de mots, et on associe au groupe de mots un code de calcul susceptible de reconstituer les bits du mot dans lequel on écrit à partir des valeurs des autres mots du groupe de mots et un code de correction capable de corriger des erreurs éventuelles dans le groupe de mots comprenant le mot reconstitué, ces erreurs éventuelles comprenant les erreurs affectant un des mots du groupe de mots initial ainsi que les erreurs induites par ces erreurs dans le mot reconstitué.

La présente invention prévoit aussi une mémoire pour la mise en oeuvre du procédé comprenant des moyens pour simultanément écrire dans des portions d'un mot ou dans un mot élémentaire d'un mot long et lire le reste des bits du mot long ou du groupe de mots.

Ces objets, caractéristiques et avantages, ainsi que d'autres de la présente invention seront exposés en détail dans

la description suivante de modes de réalisation particuliers faite à titre non-limitatif en relation avec les figures jointes parmi lesquelles : les figures 1 à 3 illustrent des structures de blocs mémoire selon la présente invention.

Comme le représente la figure 1, étant donné une mémoire prévue pour lire et écrire normalement des mots de m bits, la présente invention prévoit d'associer à un groupe de k mots, c'est-à-dire un ensemble de k. m bits, un code de correction d'erreur unique EC. Ainsi, on utilise un code de correction d'erreur pour un ensemble de k. m bits et non plus k codes de correction d'erreur dont chacun correspond à un ensemble de m bits. Comme on le déduira des exemples numériques donnés cidessus, ceci réduit beaucoup la dimension occupée en mémoire pour la correction d'erreur. Bien entendu, ceci se fait au prix d'une légère augmentation de la surface occupée par les moyens de calcul du code de correction d'erreur. Néanmoins cette augmentation est négligeable puisque les mêmes moyens de calcul sont utilisés et déterminent les codes de correction pour tous les blocs mémoire.

En outre, selon un mode de réalisation de la présente invention, on adjoint à chaque mot de m bits, un code de détection d'erreur ED, par exemple, dans le cas où il ne peut pas y avoir plus d'une erreur par mot, un simple bit de parité.

Selon une variante de la présente invention, illustrée en figure 2, dans le cas de mots courts, par exemple des mots de 4 bits (m=4), on groupera de préférence les mots courts en mots longs de r. m = M bits (par exemple 64 bits) et on associera un code de détection d'erreur, par exemple un code de parité, ED, seulement à chaque mot long. k mots longs seront alors assemblés en un groupe de mots de k. M bits auquel est associé un code de correction d'erreur EC. Dans ce qui suit, sauf indication spécifique, le terme "mot" pourra être interprété comme désignant un mot court ou un mot long.

Par exemple, si dans un système on est supposé utiliser une mémoire dont le mot est de 4 bits, on doit prévoir 3 bits supplémentaires par mot pour implémenter le code de Hamming. Pour réduire ce coût, on a intérêt à introduire des mots longs et à maximiser leur taille pour minimiser le coût du code, mais on ne veut pas utiliser des mots longs de très grande taille pour éviter une consommation très élevée lors d'une lecture. On peut choisir par exemple des mots longs de 64 bits (r = 16). Ensuite, on peut choisir des groupes d'une taille encore plus grande (par exemple des groupes de 4 mots longs). Dans ce cas, on va associer un bit de parité par mot long, et un code de Hamming (9 bits) par groupe de mots. Ceci donne un coût égal à 1/64 + 9/256 = 9,75% au lieu de 75% pour un code de Hamming par mot de 4 bits.

Le nombre de bits d'un mot d'une mémoire est généralement déterminé selon des contraintes fonctionnelles et de vitesse d'opération du système dans lequel la mémoire est insérée. Pour la mise en oeuvre de la présente invention, on va modifier la mémoire pour augmenter la taille du mot qu'on va pouvoir lire dans un cycle de lecture. On obtient ainsi des mots longs composés de r mots de m bits que l'on pourra lire en un seul cycle. Ainsi, quand le système active un cycle de lecture destiné à un mot de m bits, on va lire un mot long de r. m bits qui contient le mot auquel la lecture est destinée, on va fournir au système ce mot de m bits, et on va utiliser localement le mot long de r. m bits pour les besoins de détection et/ou de correction des erreurs.

Une mémoire normalement prévue pour des mots de m bits ne peut pas faire des lectures sur r mots de m bits, ce qui est nécessaire si on veut utiliser des mots longs. Il faut donc modifier la mémoire ce qui entraîne normalement un rallongement du temps de conception du système. Néanmoins, on trouve de plus en plus, dans des générateurs de mémoire connus, des mémoires à opérations masquables. On peut alors choisir une telle mémoire utilisant des mots de r. m bits, de façon à pouvoir faire la

lecture sur le mot long, ainsi que des opérations d'écriture masquable qui permettront d'écrire sur les m bits d'un mot court ou sur un sous-ensemble de ces bits dans le cas où la mémoire d'origine permet de faire des opérations masquables sur un sousensemble des m bits du mot.

LECTURE D'UN MOT
Pour lire un mot (court ou long), on procède de façon usuelle, à savoir que l'on commence par analyser son code de détection d'erreur. Dans la majorité des cas, il n'y aura pas d'erreur et le mot est lu normalement. S'il y a une erreur, on lit tous les mots du groupe de mots et on identifie la position de l'erreur en calculant le syndrome avec le code de correction d'erreur. L'erreur est alors corrigée à la position indiquée. On évite ainsi de lire un groupe complet à chaque lecture et, en temps normal, une lecture n'est pas plus longue qu'avec une organisation de mémoire classique.

Dans le cas de certains types de mémoires, on pourra préférer ne pas adjoindre de bit de détection d'erreur à chaque mot et on lira systématiquement un groupe de mots à chaque lecture.

ECRITURE D'UN MOT
Le problème est un peu plus complexe lors d'une écriture. En effet, à chaque écriture d'un nouveau mot, il faut modifier le code de correction d'erreur du groupe de mots pour adapter ce code de correction d'erreur du groupe au mot modifié du groupe. On va proposer ci-après deux modes de réalisation de l'invention pour résoudre ce problème.

Premier mode de réalisation d'une écriture
Avant chaque écriture, on commence par lire le mot considéré, et on examine si son code de détection ED indique une erreur ou non. Si un code de détection d'erreur n'est pas associé à chaque mot, on lira le groupe de mots et le code de correction d'erreur correspondant. S'il y a une erreur, on commence par corriger le mot lu de la façon indiquée ci-dessus en relation avec l'opération de lecture. Ensuite, le mot lu

initial ou le mot lu corrigé ayant été mémorisé temporairement dans un registre, on modifie le code de correction d'erreur en tenant compte de la comparaison entre chaque bit du mot initial ou du mot corrigé et chaque bit du mot nouvellement écrit. Ceci peut être fait de façon classique par des réseaux de portes OU Exclusif (XOR). On notera que ce procédé convient que l'on réécrive un mot complet à la place du mot préexistant ou que l'on réécrive seulement quelques bits d'un mot (écriture masquée).

L'opération de modification du code de correction d'erreur peut se faire en même temps que la réécriture du mot sans perdre un temps de cycle. Toutefois, cette opération nécessite que l'on procède à une lecture (au moins d'un mot, dans le cas où il n'y a pas d'erreur) avant chaque écriture.

En pratique l'augmentation du temps de cycle liée à la nécessité de réaliser la lecture d'un mot avant une écriture n'est dans de nombreux cas pas une pénalité car de nombreuses mémoires prévoient systématiquement la réalisation d'une lecture avant une écriture ou un temps de cycle mort après ou avant chaque écriture.

Par ailleurs, certaines mémoires, par exemple des mémoires cache, utilisent de façon standard un cycle de lecture avant un cycle d'écriture. Dans ce cas, les techniques présentées n'introduisent pas de réduction des performances du système. D'autre part, lire plusieurs mots avant une écriture est intéressant parce qu'on peut stocker ces mots dans un tampon, et si par la suite on vient de lire un de ces mots, on pourra faire une lecture très rapide en lisant le mot dans le tampon. On pourra aussi écrire plusieurs mots dans le tampon avant d'écrire tout le mot long dans la mémoire. Cette technique est souvent utilisée pour augmenter la vitesse des opérations de lecture ou d'écriture. Ainsi, les impératifs de réduction du coût du code se combinent avec des impératifs d'augmentation de la vitesse.

Selon un aspect de la présente invention, on modifie le fonctionnement de la mémoire pour pouvoir lire et écrire un mot ou mot long ou une partie de celui-ci dans le même cycle d'accès mémoire. Ceci est possible, car, le mot ou le mot long étant sélectionné au début du cycle, on active d'abord les amplificateurs de lecture pour pouvoir lire le mot ou le mot long, et on active ensuite les amplificateurs d'écriture de tous les bits du mot ou du mot long ou une partie de celui, pour effectuer une écriture non masquable ou masquable. Cette modification élimine le cycle de lecture qui doit précéder un cycle d'écriture, mais la durée du cycle sera prolongée.

Dans certaines mémoires, par exemple des mémoires DRAM, le cycle comportant une lecture suivie d'une écriture existe de façon standard pour des raisons propres au fonctionnement de la mémoire. On pourra donc choisir d'utiliser une telle mémoire et éviter ainsi le temps et le coût nécessaires au développement d'une nouvelle famille de mémoires supportant un tel cycle.

Selon une variante de ce premier mode de réalisation de la présente invention, dans le cas où l'on suppose qu'il ne peut pas y avoir plus d'un mot affecté d'erreurs dans un groupe de k mots de m bits, plutôt que d'utiliser un code de correction d'erreur associé aux k. m bits, on pourra calculer un code de correction d'erreur pour chaque mot de m bits, et prendre comme code de correction d'erreur du groupe de mots la fonction OU Exclusif (XOR) des k codes calculés. L'indication des mots dans lesquels existera l'erreur éventuelle sera donnée par le code de détection d'erreur (ED) associé à chaque mot. Bien entendu, dans ce cas, si plus d'un code de détection d'erreur associé à plus d'un mot indique une erreur, on saura que l'on est en présence d'une erreur non corrigeable.

Deuxième mode de réalisation d'une écriture
Selon un deuxième mode de réalisation de la présente invention, on cherche à éviter de lire des bits à des positions

de bit où l'on doit ensuite écrire pour éviter les inconvénients susmentionnés du premier mode de réalisation. Pour cela, on calcule le nouveau code correcteur d'erreur (et le nouveau code détecteur d'erreur le cas échéant), en utilisant la valeur des bits à écrire, la valeur des autres bits du mot, du mot long ou du groupe de mots, et la valeur du code correcteur d'erreur (et du code détecteur d'erreur le cas échéant). L'invention prévoit aussi de détecter et corriger une erreur dans les bits lus avant de les utiliser pour calculer le nouveau code.

Ce deuxième mode de réalisation s'applique plus particulièrement dans le cas où les mots sont courts et/ou où on fait une écriture masquée, c'est-à-dire où on fait une écriture seulement dans certains bits d'un mot. Par exemple, comme l'illustre la figure 3, on veut faire une écriture dans les deux positions de bits marquées d'une croix du deuxième mot, ou dans un"mot court"constituant un élément d'un"mot long".

Selon ce deuxième mode de réalisation, chaque fois que l'on veut faire une écriture masquée dans un mot, on effectue simultanément l'écriture des positions de bits choisies et la lecture des autres positions de bits du mot considéré et des autres mots du groupe de mots correspondant. On pourra adapter de nombreuses mémoires existantes à la mise en oeuvre de la présente invention. Par exemple, il est relativement simple de modifier une mémoire existante pour, chaque fois qu'on adresse un mot, connecter les positions de bits dans lesquelles on veut écrire à un amplificateur d'écriture et les autres positions de bits du même mot à un amplificateur de lecture.

Selon une première variante de ce deuxième mode de réalisation, on considère les bits lus et on donne toutes les valeurs possibles aux bits modifiés par l'opération d'écriture. Pour chacune de ces valeurs, on détermine le syndrome du groupe de mots considéré avec le code de correction d'erreur. Il est clair que, parmi toutes les valeurs possibles, il y a la valeur des bits initiaux. Alors, pour cette valeur, s'il n'y a d'erreur dans aucun des bits lus du groupe, on aura une indication

d'erreur nulle. On saura alors que le nouveau code de correction d'erreur peut être calculé valablement à partir des bits nouvellement écrits et des bits lus. Si le minimum du nombre d'erreurs détecté est non nul, on saura qu'il y a une erreur dans les bits non écrits du mot ou dans les autres mots courts d'un mot long, et pour cette valeur minimum, on procédera à une correction d'erreur avant de procéder de la façon indiquée ci-dessus.

Ceci implique bien entendu d'utiliser un code de correction d'erreur qui permet de détecter des erreurs multiples ou au moins de détecter si le nombre d'erreurs est supérieur ou inférieur à un seuil déterminé. On notera que ceci permet de détecter une erreur ou bien dans le mot dans lequel on fait une écriture partielle ou bien dans un autre mot du même groupe de mots.

Le deuxième mode de réalisation de l'invention s'applique aussi avantageusement au cas où l'on réalise des opérations d'écriture masquée sur des groupes de mots constitués d'un seul (k=l) mot long, tel que défini précédemment.

Selon une deuxième variante de ce deuxième mode de réalisation, le code associé au mot ou au mot long est capable de détecter une erreur dans les bits lus du mot ou du mot long, combinée avec n'importe quelle erreur dans les bits visés par l'écriture, et de distinguer le mot ou le mot long qui contient uniquement l'erreur dans les bits lus, des mots ou mots longs qui contiennent l'erreur dans les bits lus ainsi que des erreurs quelconques dans les bits du mot ou du mot long visés par l'écriture.

Si 11 erreur dans les bits lus du mot ou du mot long peut affecter au maximum t bits, si le nombre maximum de bits du mot affectés par une écriture est q, on prévoit que le code associé au mot ou au mot long peut détecter toute erreur de multiplicité inférieure ou égale à q+t, et parmi tout groupe d'erreurs dont les multiplicités sont supérieures à 0 et inférieurs ou égales à q+t, peut distinguer l'erreur ayant la plus

petite multiplicité, et peut corriger dans un mot ou mot long toute erreur dont la multiplicité ne dépasse pas t.

Selon un aspect de la présente invention, pendant une écriture sur certains bits d'un mot ou d'un mot long, on utilise le code du mot ou du mot long pour vérifier tous les mots ou mots longs formés en utilisant toutes les valeurs possibles pour les positions du mot ou du mot long visées par l'écriture ainsi que les valeurs lues dans les autres positions du mot ou du mot long. Si cette vérification indique un mot ou mot long sans erreur, alors les bits lus ne contiennent pas d'erreur. On utilise donc les valeurs des bits lus, les valeurs des bits écrits et le code lu pour calculer le nouveau code. Si par contre cette vérification ne trouve pas de mot ou mot long sans erreur, alors il y a une erreur dans les bits lus et on doit la corriger avant de calculer le nouveau code. Le mot contenant des erreurs uniquement dans les positions lus étant distingué par le code, on utilisera le code pour corriger l'erreur dans ce mot et obtenir ainsi les valeurs correctes dans les bits lus.

Dans un mode de réalisation de la présente invention, nous considérons des mémoires telles que à chaque cycle d'écriture on écrit soit sur un seul bit du mot ou du mot long soit sur tous les bits du mot (cas des mémoires ayant des mots à un bit dans lesquelles on forme des mots longs comportant r mots d'un bit, r > l, ou cas des mémoires utilisant des mots à m bits, comportant soit des écritures opérant sur tous les bits du mot, soit des écritures masquables opérant sur un seul bit du mot).

Les erreurs prises en compte sont des erreurs affectant un seul bit du mot ou du mot long. Selon ce mode de réalisation, le code correcteur d'erreurs associé au mot ou au mot long est un code correcteur d'erreurs simples capable de distinguer les erreurs doubles des erreurs simples (par exemple, code de Hamming augmenté par le bit de parité du mot ou du mot long et de son code). Quand on écrit sur tous les bits du mot ou du mot long, le nouveau code du mot ou du mot long est calculé de façon standard. Quand on écrit sur un seul bit, on vérifie avec le

code deux mots ou mots longs, l'un est formé en associant aux bits lus la valeur 0 pour le bit à écrire, l'autre est formé en associant aux bits lus la valeur 1 pour le bit à écrire. Si l'une de ces vérifications ne détecte pas d'erreur, alors les bits lus sont corrects et peuvent être utilisés pour calculer le code. Si on détecte des erreurs sur les deux mots, alors le mot pour lequel on a détecté une erreur simple contient la bonne valeur pour le bit visé par l'écriture. On utilise le code pour corriger l'erreur dans ce mot. On utilise alors les bits lus obtenus dans le mot corrigé, les valeurs à écrire dans les bits visés par l'écriture et l'ancien code, pour calculer le nouveau code.

Selon un aspect de la présente invention, les écritures peuvent se faire sur tous les bits d'un mot à m bits d'un mot long, ou sur un sous-ensemble de ces bits (écriture masquée). Les erreurs prises en compte peuvent affecter un seul mot d'un mot long. On associe à chaque mot long un code appelé "code de calcul", capable de calculer les valeurs des bits d'un mot, en utilisant les valeurs des bits des autres mots du mot long, ainsi qu'un code appelé"code de correction"capable de détecter et de corriger une erreur dans un mot du mot long combinée avec l'erreur introduite dans un autre mot du mot long (le mot à écrire) quand ce mot est calculé en utilisant le code de calcul et les autres mots du mot long qui incluent alors le mot erroné.

On prévoit que le code de calcul peut détecter ses propres erreurs. En cas de détection d'erreurs dans ce code, nous allons considérer qu'il n'y a pas d'erreur dans les mots lus du mot long (étant donné qu'on suppose qu'une erreur ne peut pas affecter deux mots du mot long ni un mot et le code). On évite ainsi d'introduire une erreur dans les bits lus en essayant de les corriger avec un code de calcul erroné.

On considère le cas où les erreurs prises en compte sont des erreurs susceptibles d'affecter un seul bit d'un mot long. Le code de calcul comporte m bits. Le bit de position i de

ce code est égal à la parité des bits de position i de tous les mots du mot long. Afin de pouvoir détecter des erreurs dans ce code, on lui associe un bit qui calcule sa parité (on peut observer que la parité du code de calcul est aussi la parité du mot long). La nature du code de correction sera spécifiée plus loin. Lors d'une écriture masquée ou non masquée d'un mot, on lit en même temps tous les bits non écrits du mot long associé au mot écrit, ainsi que le code de calcul avec sa parité et le code de correction. On vérifie le code de calcul en utilisant sa parité. Si on détecte une erreur, on considère qu'il n'y a pas d'autres erreurs dans le mot long (hypothèse d'une erreur simple), on utilise alors la valeur des bits lus et des bits écrits pour calculer le nouveau code de calcul avec sa parité et le nouveau code de correction. Si on ne détecte pas d'erreurs dans le code de calcul, on calcule les bits du mot visé par l'écriture, en utilisant le code de calcul et les mots du mot long non visés par l'écriture. On a alors un mot long complet et on peut utiliser le code de correction pour détecter les erreurs dans ce mot long et les corriger. Le mot long sera erroné s'il y a une erreur (par hypothèse simple) sur un mot lu. Comme la valeur des bits du mot visé par l'écriture est calculée en utilisant entre autres le mot lu erroné, on aura aussi une erreur sur le mot visé par l'écriture à la même position que l'erreur sur le mot lu erroné. On peut utiliser un code correcteur d'erreurs doubles en tant que code de correction. Ce code permet de détecter une erreur double et le cas échéant de la corriger.

On utilisera alors les bits lus corrects et les bits écrits pour calculer les nouveaux codes. Néanmoins, un code correcteur d'erreurs doubles est beaucoup plus coûteux que le code de Hamming. Pour réduire le coût on utilisera le code de Hamming.

Il permet de détecter une erreur double, mais est en principe incapable de la corriger. Néanmoins, on observe que les erreurs doubles considérées affectent une position d'un mot connu (le mot visé par l'écriture) et la même position d'un mot inconnu.

On peut pour chaque mot visé par l'écriture calculer préalable-

ment les syndromes du code de Hamming pour toutes les erreurs doubles ayant cette propriété. Il y a m (r-l) couples d'erreurs et syndromes correspondants pour chaque mot visé par l'écriture.

On peut alors créer un tableau et stocker pour chaque syndrome l'erreur double correspondante. Alors, lors de la correction d'une erreur double, on calcule son syndrome et on recherche dans le tableau l'erreur double correspondante pour la corriger.

Néanmoins, quelques-unes de ces erreurs doubles peuvent avoir le même syndrome, on augmente alors le code de Hamming en rajoutant des bits supplémentaires permettant de différencier les syndromes pour ce couple. Souvent, un seul bit supplémentaire suffira, mais un plus grand nombre de bits peut être nécessaire dans certains cas.

Ces techniques ont été présentées dans le cadre de mémoires simple-accès mais l'homme de métier pourra facilement les adapter pour des mémoires à plusieurs accès (multi-ports) en les appliquant sur chaque accès d'une telle mémoire.

Le deuxième mode de réalisation de la présente invention présente l'avantage par rapport au premier de ne pas rajouter de temps de cycle dans le cas où aucune erreur n'est détectée. Bien entendu, si une erreur est détectée, il faudra effectuer la correction d'erreur mais ceci se produit également dans le cas d'une mémoire à code de correction d'erreur classique.

L'invention est susceptible de diverses variantes et modifications qui apparaîtront à l'homme de l'art. En particulier, la présente invention présente des avantages même si k=l pour améliorer les opérations d'écriture masquée dans des mémoires à code de correction d'erreur.

Claims

REVENDICATIONS

1. Procédé de mémorisation de données permettant des détections et corrections d'erreur dans une mémoire organisée pour lire et écrire des mots d'un premier nombre (m) de bits et éventuellement pour modifier une partie seulement d'un tel mot, comprenant les étapes suivantes : associer un code de détection et de correction d'erreur à un groupe d'un deuxième nombre k > -l de mots ; et associer à chaque écriture une opération de vérification et, s'il y a lieu, de correction d'erreur dans le groupe de mots associé au mot dans lequel on réalise une opération d'écriture totale ou partielle.

2. Procédé selon la revendication 1, caractérisé en ce que chaque mot est un mot long de M bits comprenant un troisième nombre déterminé r de mots élémentaires à m bits.

3. Procédé selon la revendication 1 ou 2, caractérisé en ce que : un code de détection d'erreur est associé à chaque mot ; et chaque opération d'écriture est précédée d'une lecture du mot considéré et de son code de détection d'erreur et, en cas d'erreur, de la lecture du groupe de mots et du code de correction d'erreur en vue de la correction des erreurs et de la modification du code de correction d'erreur.

4. Procédé selon la revendication 1 réalisé dans une mémoire à double accès.

5. Procédé selon la revendication 1 ou 2, dans lequel on effectue une écriture dans seulement au moins un bit d'un mot, ou dans seulement les m bits d'un mot élémentaire d'un mot long, caractérisé en ce qu'il comprend les étapes suivantes : lire les autres bits du groupe de mots, calculer les codes de correction d'erreur pour ces autres bits et pour toutes les valeurs possibles des positions de bits dans lesquelles on écrit, et déterminer celle des valeurs possibles pour laquelle on obtient une erreur minimale ; et

si cette erreur minimale est nulle, considérer que l'écriture a réussi et calculer un nouveau code de correction d'erreur ; si cette erreur minimale est non nulle, corriger les bits en erreur aux positions autres que celles où on a écrit et calculer un nouveau code de correction d'erreur.

6. Procédé selon la revendication 5, caractérisé en ce qu'il est appliqué à un mot constituant à lui seul le groupe de mots.

7. Procédé selon l'une quelconque des revendications 1 à 6, dans lequel des erreurs sont susceptibles de survenir dans un seul mot d'un groupe de mots, et dans lequel un code de détection d'erreur est associé à chaque mot, caractérisé en ce que le code de correction d'erreur est calculé sous forme d'un OU Exclusif des codes de correction d'erreur de chaque mot.

8. Procédé selon la revendication 1 ou 2, dans lequel on effectue une écriture dans seulement au moins un bit d'un mot d'un groupe de mots, et dans lequel on associe au groupe de mots un code de calcul susceptible de reconstituer les bits du mot dans lequel on écrit à partir des valeurs des autres mots du groupe de mots et un code de correction capable de corriger des erreurs éventuelles dans le groupe de mots comprenant le mot reconstitué, ces erreurs éventuelles comprenant les erreurs affectant un des mots du groupe de mots initial ainsi que les erreurs induites par ces erreurs dans le mot reconstitué.

9. Mémoire pour la mise en oeuvre du procédé selon l'une quelconque des revendications 5 à 8, caractérisée en ce qu'elle comprend des moyens pour simultanément écrire dans des portions d'un mot ou dans un mot élémentaire d'un mot long et lire le reste des bits du mot long ou du groupe de mots.