-
Die
vorliegende Erfindung bezieht sich auf eine Vorrichtung und ein
Verfahren zum Auslesen eines vorbestimmten Datenwortes aus einem
Speicher und auf eine Vorrichtung und ein Verfahren zum Speichern
eines Datenblocks in einen Speicher, insbesondere auf einen Speicher,
bei dem es sporadisch zu Einbitfehlern kommen kann, wie z. B. Flash-Speichern.
-
Viele
Speichertechnologien haben heute das Problem, dass es sporadisch
zu einzelnen Bitfehlern kommen kann. Dies ist unvermeidbar. Jedoch
ist das Problem im Allgemeinen auf einzelne, weit verstreute Bits
beschränkt.
Mehrbitfehler in einem beschränkten Datenbereich,
kommen zwar vor, ihr Auftreten ist jedoch so selten, dass diese
im Allgemeinen kein Zuverlässigkeitsproblem
darstellen. Durch die Einzelfehler bzw. Einzelbitfehler leidet jedoch
die Zuverlässigkeit
vieler Speicherprodukte. Aus diesem Grund werden in Speicherbausteinen
gespeicherte Daten mit Redundanzinformationen versehen, die eine
Erkennung und gegebenenfalls auch Korrektur dieser Fehler erlauben.
Betroffen hiervon ist eine Vielzahl von Speichertechnologien, zu
denen beispielsweise spezielle Flash-Speichertechnologien und andere nicht-flüchtige Speichertypen
(NVM = non-volatile Memory), aber auch andere Speichertypen gehören.
-
Gerade
im Bereich der nicht-flüchtigen
Speichertypen, insbesondere bei Flashspeicherprodukten und Flashspeichertechnologien,
kann es so aufgrund der internen Verschaltung dieser Speicher beispielsweise
aufgrund eines als „Drain-Disturb" bekannten Mechanismus
bei wiederholten schreibenden Speicherzugriffen zu einzelnen Bitfehlern
kommen. Neben Flashspeichern tritt dieses Problem auch bei anderen
Speichertypen auf. Ein Beispiel stellen hierfür beispielsweise die als Arbeitsspeicher verwendeten
RAM-Speicher (RAM = random access memory = Speicher mit wahlfreiem
Zugriff) dar. So kommt es im Bereich von RAM-Speichern ebenfalls aufgrund
von α-Teilchen,
die beispielsweise aus der Vergussmasse eines solchen Speicherbausteins stammen
können,
zu sporadischen Einzelbitfehlern.
-
Bisher
wurde dieses Problem durch das Hinzufügen eines Fehlercodes pro Speicherblock
gelöst, wobei
der Speicher in einzelnen Speicherblöcken organisiert ist und jeder
Speicherblock ein oder mehrere Datenwörter umfasst. Als Fehlercode
kommen hierbei sowohl Fehlererkennungswerte (EDC = error detecting
codes), wie auch Fehlerkorrekturwerte (ECC = error correcting codes)
zum Einsatz. Zum überprüfen der
Korrektheit eines in einem Speicherblock abgespeicherten Datums
muss in diesem Fall jedoch der gesamte Speicherblock zuerst ausgelesen
werden, um mit Hilfe des dem Speicherblock zugeordneten Fehlercodes
das Datum bzw. den Code auf Fehler prüfen zu können. Dieses Vorgehen hat jedoch
einige Nachteile.
-
Wählt man
einen sehr kleinen Speicherblock als Basiseinheit, ist der Codeaufwand,
also insbesondere der Speicherplatz, der zum Speichern des Fehlerkorrekturwertes
notwendig ist, im Vergleich zu der Größe eines Speicherblocks sehr
groß.
Wie beispielsweise in dem Buch „Halbleiterschaltungstechnik" von U. Tietze und
Ch. Schenk (Springer-Verlag, Berlin 1990, 9. Auflage) erläutert ist,
beträgt
die minimale Zahl der Bits eines Fehlerkorrekturwertes, der die
Korrektur eines beliebigen Einbitfehlers zulässt, für ein Datum mit einer Länge zwischen
einem und 4 Bit 3 Bit, für
ein Datum mit einer Länge
zwischen 5 und 11 Bit 4 Bit, für
ein Datum mit einer Länge
zwischen 12 und 26 Bits 5 Bit, für
ein Datum mit einer Länge
zwischen 27 und 57 Bit 6 Bit, für
ein Datum mit einer Länge
zwischen 58 und 120 Bit 7 Bit und für ein Datum mit einer Länge zwischen
121 und 247 Bit 8 Bit. Diese Zahlen verdeutlichen, dass der Speicheraufwand
für das
Speichern eines Fehlerkorrekturwertes als Fehlercode für kleine
Speicherblöcke mit
einem verhältnismäßig hohen
Speicheraufwand, also einem Verhältnis
der benötigten
Speicherlänge
zum Speichern des Fehlercodes im Verhältnis zu der Größe des zugrundeliegenden
Datums, verbunden ist. Andererseits kann jedoch auf eine kleine
Speichereinheit schnell und energieeffizient zugegriffen werden.
-
Wählt man
jedoch eine größere Blockeinheit bzw.
Größe des zugrundeliegenden
Speicherblocks, so wird zwar der Mehraufwand für den Fehlercode bzw. den Fehlerkorrekturwert
erträglich,
doch durch die Notwendigkeit, den gesamten Block zu lesen, selbst
wenn nur ein einzelnes Byte benötigt
wird, wird der Zugriff jedoch sehr langsam und stromhungrig bzw.
energieintensiv.
-
Weist
beispielsweise ein Datenblock eine Netto-Datenblockgröße von 16 Byte bzw. 128 Bit
mit jeweils 4 Byte umfassenden Teilwörtern bzw. Datenwörtern auf,
müssen
für einen
Zugriff auf ein einzelnes Byte immer zuvor die kompletten 16 Byte
gelesen werden, um das einzelne Byte auf einen Fehler überprüfen zu können. Dies
erzeugt eine zeitliche Verzögerung
von mindestens 3 bzw. 4 Takten für
das Lesen der 3 Datenwörter,
die das einzelne Byte nicht umfassen.
-
Eine
Möglchkeit,
die Problematik des langsamen Zugriffs im Falle eines größeren Speicherblocks zu
kompensieren, besteht in dem Einbau und der Verwendung eines Cache-Speichers.
Cache-Speicher können
jedoch diesen Nachteil nicht immer kompensieren, was insbesondere
im Fall einer schlechten Hitrate zutrifft. In dem Fall einer schlechten
Hitrate werden von einem Prozessor oder einer anderen Komponente
des Gesamtsystems, das den Speicher umfasst, benötigte Daten angefordert, die in
dem Cache-Speicher häufig
nicht zwischengespeichert bzw. abgelegt sind. In diesem Fall kann
die Verwendung eines Cache-Speichers den Datenzugriff nicht beschleunigen,
da in diesem Fall für
die Lieferung des gewünschten
Datums auch weiterhin der gesamte Speicherblock des Speichers gelesen
werden muss, um einen Fehler auszuschließen.
-
Ausgehend
von diesem Stand der Technik besteht die Aufgabe der vorliegenden
Erfindung darin, eine Vorrichtung und ein Verfahren zum Auslesen aus
einem Speicher oder eine Vorrichtung und ein Verfahren zum Speichern
in einen Speicher zu schaffen, die ein schnelles Auslesen und Überprüfen auf einen
Fehler, sowie eine Korrektur bei einem gleichzeitig verhältnismäßig geringem
Speicheraufwand ermöglichen.
-
Diese
Aufgabe wird durch eine Vorrichtung gemäß Anspruch 1 oder 12, ein Verfahren
gemäß Anspruch
22 oder 23 und durch ein Computerprogramm gemäß Anspruch 24 gelöst.
-
Gemäß einem
ersten Aspekt umfasst die erfindungsgemäße Vorrichtung zum Auslesen
eines vorbestimmten Datenwortes aus einem Speicher, in dem ein Datenblock,
der in eine Mehrzahl von Datenwörtern,
die das vorbestimmte Datenwort umfassen, gegliedert ist, pro Datenwort
der Mehrzahl von Datenwörtern
ein dem jeweiligen Datenwort zugeordneter Fehlerkennungswert und
ein dem Datenblock zugeordneter Korrekturwert gespeichert ist, eine
Fehlererkennungseinrichtung, die ausgebildet ist, um zu überprüfen, ob
das vorbestimmte Datenwort eine vorbestimmte Beziehung zu dem zugeordneten
Fehlererkennungswert aufweist, um bei einem Nicht-Vorliegen der
vorbestimmten Beziehung auf einen Fehler zu schließen, und
eine Fehlerkorrektureinrichtung, die ausgebildet ist, um, falls
das vorbestimmte Datenwort die vorbestimmte Beziehung zu dem zugeordneten
Fehlererkennungswert nicht aufweist, unter Verwendung des Korrekturwertes
den Fehler zu korrigieren, wobei die Fehlerkorrektureinrichtung ausgebildet
ist, um den Korrekturwert unabhängig davon
zur Fehlerkorrektur zu verwenden, welches Datenwort der Mehrzahl
von Datenwörtern
das vorbestimmte Datenwort ist.
-
Gemäß einem
zweiten Aspekt umfasst die erfindungsgemäße Vorrichtung zum Speichern
eines Datenblocks aus einer Mehrzahl von Datenwörtern in einen Speicher eine
Fehlererkennungswerterzeugungseinrichtung, die ausgelegt ist, um
für jedes
Datenwort der Mehrzahl von Datenwörtern einen Fehlererkennungswert
zu erzeugen, der eine vorbestimmte Beziehung zu dem jeweiligen Datenwort
aufweist, und eine Fehlerkorrekturwerterzeugungseinrichtung, die
ausgebildet ist, um für
den Datenblock einen Korrekturwert zu erzeugen, aus dem ein Fehler,
der zu einem Nicht-Vorliegen der vorbestimmten Beziehung zwischen
einem vorbestimmten Datenwort und dem zugeordneten Fehlererkennungswert führt, unabhängig davon
korrigierbar ist, welches der Datenwörter dem vorbestimmten Datenwort
entspricht.
-
Der
vorliegenden Erfindung liegt die Erkenntnis zugrunde, dass ein schnelles
Auslesen eines Datenwortes aus einem Speicher und die Überprüfung desselben
auf einen Fehler mit der Möglichkeit,
einen solchen Fehler basierend auf einem nur einen verhältnismäßig geringen
Speicherplatz erfordernden Korrekturwert zu korrigieren, dadurch
erreicht werden kann, dass jedem Datenwort ein Fehlererkennungswert
zugeordnet wird und dass einem Datenblock, der eine Mehrzahl von
Datenworten umfasst, ein Korrekturwert zugeordnet wird, der eine
Korrektur eines Fehlers ermöglicht,
unabhängig
davon, welches Datenwort der Mehrzahl von Datenworten in dem Datenblock
den Fehler aufweist.
-
Besonders
vorteilhaft hieran ist, dass aufgrund des jedem Datenwort zugeordneten
Fehlererkennungswertes eine schnelle Überprüfung auf das Vorliegen eines
Fehlers möglich
ist, während
der zu einer Korrektur notwendige Korrekturwert sich auf einen gesamten
Datenblock bezieht und daher einen geringeren Speicherplatzbedarf
aufweist, als es ein Korrekturwert erfordern würde, der sich auf ein einzelnes
Datenwort bezieht. Dies liegt daran, dass ein Datenblock eine Mehrzahl
von Datenwörtern
umfasst, und dass mit wachsender Datenblock länge der Speicherbedarf des
Korrekturwertes bezogen auf die Länge des Datenblocks abnimmt.
-
Besonders
vorteilhaft ist es darüber
hinaus, wenn die Fehlererkennungswerte, die den Datenwörtern zugeordnet
sind, jeweils eine Länge
von genau einem Bit haben, also den geringstmöglichen zusätzlichen Speicheraufwand erfordern.
Darüber
hinaus ermöglicht
die Verwendung von Paritätsbits
als Fehlererkennungswerte, also eine Überprüfung der Parität der einzelnen
Datenwörter
aufgrund des jeweils zugeordneten Paritätsbits, eine sehr schnelle Überprüfung auf
einen Fehler, da eine Paritätsüberprüfung parallel
in einem Taktzyklus des Systems, das den Speicher umfasst, möglich ist.
-
Ein
weiterer Vorteil besteht darin, dass der Korrekturwert dazu verwendet
werden kann, einerseits einen beliebigen Einbitfehler in dem Datenblock oder
aber andererseits einen beliebigen Einbitfehler in einem Datenwort
bzw. in einem Datenwort und dem zugeordneten Fehlererkennungswert
zu korrigieren, wie die detaillierten Ausführungsbeispiele zeigen werden.
Je nach Maßgabe
der Randbedingungen an das System, das den Speicher umfasst, kann es
vorteilhafter sein, den Korrekturwert so auszulegen, dass ein beliebiger
Einbitfehler in dem Datenblock oder aber in einem Datenwort bzw.
in einem Datenwort und dem zugeordneten Fehlererkennungswert korrigierbar
ist.
-
Ein
weiterer Vorteil der vorliegenden Erfindung besteht darin, dass
die Länge,
die zur Speicherung des Korrekturwertes benötigt wird, dadurch reduziert
werden kann, dass auf Basis jedes Datenwortes, das der Datenblock
umfasst, ein Teilkorrekturwert berechnet wird, aus dem wiederum
durch Anwenden einer Verknüpfung,
beispielsweise einer bitweisen XOR-Verknüpfung (XOR = exclusive-or =
exklusiv-oder), der Korrekturwert erzeugt wird. Tritt bei einem
Auslesen nun ein Fehler auf, so wird auf Basis des Korrekturwertes
und der Teilkorrekturwerte, die aus dem Datenwörtern berechnet wer den, die
nicht das auszulesende Datenwort sind, ein rekonstruierter Teilkorrekturwert
für das
auszulesende Datenwort bestimmt, auf Basis dessen die Korrektur
durchgeführt
wird. Dies hat den besonderen Vorteil, dass die Länge des
Korrekturwertes nicht mehr bezogen auf die Länge des Datenblocks ist, sondern
vielmehr der Länge
eines Korrekturwertes entsprechen kann, der sich nur auf ein Datenwort
bezieht. Hierdurch kann erneut der Speicherbedarf für die Korrekturwerte
gesenkt werden, ohne dass die Möglichkeit
eines schnellen Auslesens eines vorbestimmten Datenwortes beeinträchtigt wird.
-
Die
Erfindung ermöglicht
somit gleichzeitig ein schnelles Auslesen eines Datenwortes und
die Überprüfung auf
einen Fehler bei einem gleichzeitig verhältnismäßig geringen Speicherbedarf
für den
zur Korrektur notwendigen Korrekturwert.
-
Bevorzugte
Ausführungsbeispiele
der vorliegenden Erfindung werden nachfolgend unter Bezugnahme auf
die beiliegenden Zeichnungen näher
erläutert.
Es zeigen:
-
1 ein
schematisches Blockschaltbild einer erfindungsgemäßen Vorrichtung
zum Auslesen eines vorbestimmten Datenworts aus einem Speicher;
-
2 ein
Flussdiagramm eines ersten Ausführungsbeispiels
des erfindungsgemäßen Verfahrens
zum Speichern eines Datenblocks in einen Speicher;
-
3 ein
Flussdiagramm eines ersten Ausführungsbeispiels
des erfindungsgemäßen Verfahrens
zum Auslesen eines vorbestimmten Datenwortes aus einem Speicher;
-
4 ein
Flussdiagramm eines zweiten Ausführungsbeispiels
des erfindungsgemäßen Verfahrens
zum Schreibe eines Datenblocks in einen Speicher;
-
5 ein
Flussdiagramm eines zweiten Ausführungsbeispiels
des erfindungsgemäßen Verfahrens
zum Auslesen eines vorbestimmten Datenwortes aus einem Speicher;
-
6 ein
Flussdiagramm eines dritten Ausführungsbeispiels
des erfindungsgemäßen Verfahrens
zum Auslesen eines vorbestimmten Datenwortes aus einem Speicher;
und
-
7 ein
Flussdiagramm eines vierten Ausführungsbeispiels
des erfindungsgemäßen Verfahrens
zum Auslesen eines vorbestimmten Datenwortes aus einem Speicher.
-
Bezug
nehmend auf die 1 bis 7 wird nun
ein Ausführungsbeispiel
einer erfindungsgemäßen Vorrichtung
zum Auslesen eines vorbestimmten Datenworts aus einem Speicher beschrieben.
In den 1 bis 7 werden für ähnliche Objekte und Verfahrensschritte ähnliche
Bezugszeichen verwendet. Darüber
hinaus werden gleiche Objekte und Verfahrensschritte mit gleichen
Bezugszeichen bezeichnet.
-
1 zeigt
ein schematisches Blockschaltbilds eines Ausführungsbeispiels einer erfindungsgemäßen Vorrichtung
zum Auslesen eines vorbestimmten Datenwortes aus einem Speicher 100.
In dem Speicher 100 ist ein Datenblock 110 gespeichert,
der eine Mehrzahl von Datenwörtern 120-1,
..., 120-n und einer Mehrzahl von Fehlererkennungswerten 130-1,
..., 130-n, die jedem einem der Datenwörter 120-1, ..., 120-n zugeordnet
sind, und einen Korrekturwert 140 umfasst. Mit anderen
Worten ist der Datenblock 110 in n Unterwörter bzw.
Datenwörter 120-1,
..., 120-n aufgeteilt. Der Speicher 100 ist mit einer
Fehlererkennungseinrichtung 150 und mit einer Fehlerkorrektureinrichtung 160 gekoppelt.
Die Fehlererkennungseinrichtung 150 ist darüber hinaus
mit der Fehlerkorrektureinrichtung 160 gekoppelt. Die Fehlererkennungseinrichtung 150 ist
weiter über
einen beispielsweise bidirektionalen Bus 170 mit einer externen
Komponente 180, bei der es sich beispielsweise um eine
CPU (CPU = central processing unit = Zentralprozessor), einen Speicher,
einen Spezialprozessor, einen Kryptoprozessor oder eine andere Einrichtung
handeln kann, verbunden. Die Fehlererkennungseinrichtung 150 und
die Fehlerkorrektureinrichtung 160 sind häufig als
Teil einer Speichersteuereinheit ausgeführt, die jedoch in 1 nicht
gezeigt ist.
-
Wie
in den einführenden
Abschnitten der vorliegenden Anmeldung erläutert wurde, können Mehrbitfehler
in einem Datenbereich prinzipiell zwar vorkommen, treten jedoch
so selten auf, dass sie die Zuverlässigkeit von Speichern 100 im
Allgemeinen nicht negativ beeinflussen. Da Einbitfehler ein größeres Zuverlässigkeitsproblem
darstellen, wird im weiteren Verlauf der Anmeldung von der Annahme
bzw. der Voraussetzung ausgegangen, dass ein Datenblock 110 zwar
einen Einbitfehler aufweisen kann, nicht jedoch einen Mehrbitfehler,
es sei denn, es wird ein solcher ausdrücklich im Rahmen der vorliegenden
Anmeldung angenommen. Die Fehlererkennungswerte 130-1,
..., 130-n stellen somit für die n Datenwörter bzw.
Unterwörter 120-1,
..., 120-n, in die der vor einem einzelnen Bitfehler zu
schützende
Datenblock 110 aufgeteilt ist, sicher bzw. pro Datenwort 120-1,
..., 120-n die Einbitfehlererkennungsmöglichkeit dar.
-
Greift
die externen Komponente 180 über den bidirektionalen Bus 170 beispielsweise
im Rahmen eines Lesebefehls bzw. Auslesebefehls auf ein bestimmtes
Datenwort aus dem Speicher zu, so erhält die Fehlererkennungseinrichtung 150 das
betreffende Datenwort, beispielsweise das Datenwort 120-2,
und den zugeordneten Fehlererkennungswert, also den Fehlererkennungswert 130-2,
und überprüft das Datenwort 120-2 auf
Basis des Fehlererkennungswertes 130-2 auf ein Vorliegen
eines Fehlers. Alternativ kann auch die Fehlererkennungseinrichtung 150 über den
bidirektionalen Bus 170 von der externen Komponente 180 den
Befehl erhalten, ein bestimmtes Datenwort aus dem Spei cher 100 auszulesen,
also einen Lesebefehl bzw. Auslesebefehl. In diesem Fall greift
die Fehlererkennungseinrichtung 150 auf den Speicher 100 zu
und liest das betreffende Datenwort, also im Beispiel oben das Datenwort 120-2,
und den zugeordneten Fehlererkennungswert, also den Fehlererkennungswert 130-2, aus
und überprüft dann
das Datenwort 120-2 auf Basis des Fehlererkennungswertes 130-2 auf
ein Vorliegen eines Fehlers.
-
Stellt
die Fehlererkennungseinrichtung 150 unabhängig davon,
ob sie selbst den Lesebefehl ausgeführt hat oder nur die Überprüfung auf
ein Vorliegen eines Fehlers durchgeführt hat, keinen Fehler fest,
so wird das Datenwort 120-2 oder auch nur ein Teil über den
bidirektionalen Bus 170 an die externe Komponente 180 ausgegeben.
-
Stellt
die Fehlererkennungseinrichtung 150 im Rahmen des Beispiels
oben bei der Überprüfung des
Datenwortes 120-2 einen Fehler fest, handelt es sich aufgrund
der weiter oben angegebenen Vorraussetzungen um einen Einbitfehler.
In diesem Fall weist die Fehlererkennungseinrichtung 150 die
Fehlerkorrektureinrichtung 160 an, den dem Datenblock 110, der
das Datenwort 120-2 umfasst, zugeordneten Korrekturwert 140 auszulesen
und auf Basis des Korrekturwertes 140 den Datenblock 110 entsprechend
zu korrigieren. Nach dem Abschluss der Korrektur des Datenblocks 110 übermittelt
die Fehlerkorrektureinrichtung 160 der Fehlererkennungseinrichtung 150 ein
Signal, woraufhin die Fehlererkennungseinrichtung 150 erneut
das entsprechende Datenwort, im Beispiel oben also das Datenwort 120-2,
zusammen mit dem zugehörigen
Fehlererkennungswert 130-2, ausliest, erneut auf Fehler überprüft und im
Falle der Fehlerfreiheit des Datenworts 120-2 dieses über den bidirektionalen
Bus 170 an die externe Komponente 180 ausgibt.
-
Um
nun eine möglichst
schnelle Einzelbitfehlererkennung kombiniert mit einer Speicherplatz
sparenden Fehlerkorrektur zu ermöglichen,
wird für
die Fehlererkennungswerte 130-1, ..., 130-n häufig ein Paritätsbit verwendet,
so dass die Überprüfung auf das
Vorliegen eines Fehlers durch einen Vergleich der Parität eines
der Datenwörter 120-1,
..., 120-n mit dem zugeordneten Paritätsbit 130-1, ..., 130-n erfolgt,
da eine Überprüfung der
Parität
eines Datenwortes 120-1, ..., 120-n durch eine
parallele Operation über
alle Datenbits sehr schnell durchgeführt werden kann. Hierbei ist
es unerheblich, ob als Fehlererkennungswert eine gerade oder eine
ungerade Parität
verwendet wird, ob also die Zahl der gesetzten Bits des Datenwortes
gerade oder ungerade ist. Grundsätzlich
kann jedoch jedes Verfahren zur Fehlererkennung herangezogen werden,
so dass die Verwendung eines Paritätsbits im Rahmen der folgenden
Ausführungsbeispiele
nicht einschränkend zu
verstehen ist. Vorteilhaft ist hier allerdings die Verwendung eines
schnellen und Speicherplatz sparenden Fehlererkennungsverfahren,
wie eine Paritätsüberprüfung anhand
von den Datenwörtern 120-1,
..., 120-n zugeordneten Paritätsbits 130-1, ..., 130-n. Die
Paritätsüberprüfung bietet
so den Vorteil der schnellen Ausführbarkeit, sowie den weiteren
Vorteil, dass der zusätzlich
notwendige Speicherplatz für
die Paritätsbits 130-1,
..., 130-n sehr gering ist, ohne dass die Möglichkeit,
einen beliebigen Einbitfehler zu erkennen, verloren wird.
-
Dadurch
dass jedem der n Datenwörter 120-1,
..., 120-n jeweils genau ein einzelnes Paritätsbit 130-1,
..., 130-n zugeordnet ist und dass der Fehlerkorrekturcode
bzw. Korrekturwert 140 über
den gesamten Datenblock 110 ermittelt wird, ermöglicht nun
einerseits eine schnelle Überprüfung eines
einzelnen Datenwortes auf einen Fehler und andererseits einen im
Vergleich geringen Aufwand bzw. Speicherplatzbedarf für das Speichern
des Korrekturwerts 140. Mit anderen Worten ermöglicht die
vorliegende Erfindung den zur Speicherung des erforderlichen Fehlerkorrekturwerts
erforderlichen Speicherplatz gering zu halten bzw. zu minimieren,
indem das Fehlererkennungsverfahren auf jedes der Datenwörter 120-1,
..., 120-n separat angewendet werden kann, während das
Fehlerkorrekturverfahren auf die Mehrzahl von Datenwörter 120-1,
..., 120-n bzw. auf den Datenblock 110 angewendet
wird. Somit kann die Länge
des Korrekturwertes 140 unter Ausnutzung der Paritätsbits 130-1,
..., 130-n minimiert werden, während die Paritätsbits 130-1,
..., 130-n eine schnelle Überprüfung eines der Datenwörter 120-1, ..., 120-n auf
das Vorliegen eines Fehlers und damit eine quasi-sofortige Lieferung
des betreffenden Datenwortes an die nachgeschaltete Empfängereinheit bzw.
die externe Komponente 180 ermöglicht, solange kein Fehler
vorliegt. Die Fehlerkorrektur wird also durch Einführen eines
entsprechenden Codes 140 über den gesamten Datenblock 110,
also durch Einführen
eines Korrekturwerts 140, der sich auf den gesamten Datenblock 110 bezieht,
realisiert.
-
Unter
den oben genannten Voraussetzung, dass es pro Datenblock 110 maximal
genau einen Einbitfehler gibt, kann somit schon beim Lesen des gewünschten
Teildatenwortes bzw. Datenwortes sofort entschieden werden, ob das
Teildatenwort oder auch das Datenwort korrekt ist oder nicht. Falls
es korrekt ist, kann es sofort einer nachgeschalteten Einheit 180 ausgegeben
und von dieser bearbeitet werden. In diesem Fall muss der übrige Datenblock nicht
mehr ausgelesen werden. Somit ergibt sich als wesentlicher Vorteil
der vorliegenden Erfindung eine deutliche Steigerung der Ausführungszeit
einer Leseoperation und eine damit einhergehende erhebliche Reduzierung
des Energieaufwands, wenn auf Einzelworte, anstatt des gesamten
Datenblocks 110 für
einen Zugriff (Blockzugriff) zurückgegriffen
werden kann.
-
Liegt
ein Fehler vor, so kann mit Hilfe des Korrekturwerts 140 der
Fehler jedoch behoben werden, so dass nach einer erfolgten Korrektur
das nunmehr korrekte Datenwort geliefert bzw. ausgegeben werden
kann. Die vorliegende Erfindung erlaubt somit die Wahl einer großen Blockeinheit
bzw. eines Datenblocks 110, um den Codeaufwand für das Speichern
eines Korrekturwertes 140 gering zu halten, und gleichzeitig
einen schnellen Zugriff auf ein Datum bzw. ein Datenwort und seine Überprüfung auf
einen Fehler. Im Rahmen eines lesenden Zugriffs auf eine Datum bzw.
ein Datenwort kann, muss aber nicht der gesamte Datenblock 110 gelesen
werden.
-
Anhand
der 2 bis 7 werden im weiteren Verlauf
der vorliegenden Anmeldung zum einen das erfindungsgemäße Verfahren
zum Auslesen eines vorbestimmten Datenwortes aus einem Speicher 100 anhand
vier Ausführungsbeispielen
und das erfindungsgemäße Verfahren
zum Speichern eines Datenblocks 110 in einen Speicher 100 anhand
von zwei Ausführungsbeispielen
näher erläutert und
die Vorteile diskutiert.
-
2 zeigt
so ein Flussdiagramm eines ersten Ausführungsbeispiels des erfindungsgemäßen Verfahrens
zum Speichern eines Datenblocks 110 in einen Speicher 100.
Nach dem Start S200 des Verfahrens werden zunächst die n Datenwörter 120-1, ..., 120-n eingelesen
(Schritt S210). In einem nächsten
Schritt S220 werden die den Datenwörtern 120-1, ..., 120-n zugeordneten
Paritätsbits 130-1,
..., 130-n erzeugt. In einem darauffolgenden Schritt S230
werden über
die einzelnen Datenwörter 120-1,
..., 120-n n Teilkorrekturwerte bzw. Teilfehlercodes berechnet. Anschließend werden
die n Teilkorrekturwerte im Rahmen eines nächsten Schritts S240 durch
eine bitweise XOR-Verknüpfung
verknüpft
bzw. über
eine bitweise XOR-Struktur (XOR = exclusive-or = exklusiv-oder)
aufsummiert, wobei das Ergebnis dieser Verknüpfung bzw. Aufsummation, als
Summencode bzw. Korrekturwert 140 dem Datenblock 110 zugeordnet
wird. In einem nächsten
Schritt S250 wird der Datenblock 110, also die einzelnen
Datenwörter 120-1,
..., 120-n, die Paritätsbits 130-1,
..., 130-n und der Korrekturwert 140 in dem Speicher 100 gespeichert,
womit dieser Schreibvorgang beendet wird (Schritt S260).
-
Dadurch
dass individuelle Fehlerkorrekturcodes n-mal jeweils unabhängig voneinander über die
einzelnen Datenwörter 120-1,
..., 120-n berechnet werden, diese n Teilfehlercodes anschließend über eine
XOR-Struktur bitweise aufsummiert und der daraus resultierende Summencode
als Korrekturwert 140 mit dem Datenblock 110 gespeichert
wird, können
im Vergleich zu einem Korrekturwert 140, der sich auf den
gesamten Datenblock 110 bezieht, einige Bits an Länge als
Differenzbits eingespart werden. Ausgehend beispielsweise von einer
Netto-Datenblockgröße von 16
Byte, also 128 Bit, die aufgrund der Breite des Bussystems bzw.
des bidirektionalen Busses 170 oder anderer Randbedingungen
in Teilwörter
bzw. Datenwörter
von jeweils 4 Byte, also 32 Bit, gegeben sind, folgt, dass der Datenblock 110 4 Datenwörter 120-1,
..., 120-n umfasst, dass also n = 4 ist. Wie schon in den
einleitenden Abschnitten der vorliegenden Anmeldung erläutert wurde,
ergibt sich ursprünglich
bezogen auf den ganzen Datenblock 110 in diesem Fall ein
Fehlercode der Länge
8 Bit für einen
reinen Fehlerkorrekturalgorithmus bzw. 9 Bit für eine Kombination aus Fehlerkorrektur-
und Fehlererkennungsalgorithmen, wobei der Fehlererkennungsalgorithmus
in Form eines Paritätsvergleichs mit
einem Paritätsbit
für den
Datenblock 110 implementiert ist. Wie ebenfalls bereits
in den einleitenden Abschnitten der vorliegenden Anmeldung erläutert wurde,
müssen
ohne das weiter unten beschriebene erfindungsgemäße Verfahren für einen
Zugriff auf ein einzelnes Byte immer zuvor die kompletten 16 Bytes gelesen
werden, was zu einer zeitlichen Verzögerung von mindestens 3 bzw.
4 Takten führt.
Durch das erfindungsgemäße Verfahren
ist es nun möglich,
einen gezielten Bytezugriff in einem einzigen Takt zu vollziehen,
in dem direkt das adressierte 4 Byte lange Wort gelesen wird. Der
Codeüberhang
bzw. die gesamte Codebreite, also der zusätzliche Speicherbedarf für die Durchführung der
erfindungsgemäßen Verfahren
beträgt
in diesem Fall 10 Bit, die sich aus den 4 den Datenwörtern 120-1,
..., 120-n zugeordneten Paritätsbits 130-1, ..., 130-n und
einem 6 Bit langen Fehlerkorrekturcode bzw. Teilkorrekturwert für ein 33
Bit umfassendes Datenpaket ergibt. Neben den 32 Datenbits des 4
Byte umfassenden Datenwortes weist das Datenpaket zusätzlich noch
das dem Datenwort zugeordnete Paritätsbit auf. Da aufgrund der
Bitweisen XOR-Verknüpfung der
Teilkorrekturwerte zu dem dem Datenblock 110 zugeordneten Korrekturwert 140 dessen
Länge unverändert bleibt, ergibt
sich eine Gesamtcodebreite bzw. eine Länge für den Korrekturwert 140 und
die Paritätsbits 130-1, ..., 130-n von
insgesamt 10 Bit. Gegenüber
einer möglichen
Lösung,
wie sie in den einführenden
Abschnitten der vorliegenden Anmeldung diskutiert wurde, beträgt der zusätzliche
Codeüberhang,
also der zusätzliche
Speicherplatzbedarf nur 1 bzw. 2 Bit Längen, was aufgrund der höheren Auslesegeschwindigkeit
im Rahmen des erfindungsgemäßen Verfahrens zum
Auslesen eines vorbestimmten Datenworts, das weiter unten näher beschrieben
wird, einen zu dem erzielbaren Geschwindigkeitszuwachs vernachlässigbaren
Nachteil darstellt.
-
3 zeigt
ein Flussdiagramm eines ersten Ausführungsbeispiels des erfindungsgemäßen Verfahrens
zum Auslesen eines vorbestimmten Datenworts aus einem Speicher 100,
das das in 2 gezeigte Ausführungsbeispiel
eines Schreibvorgangs ergänzt.
Nach einem Start L200 wird zunächst
in einem ersten Schritt L210 das vorbestimmte Datenwort auf Basis
seiner Adresse aus dem Speicher 100 ausgelesen. In einem
zweiten Schritt L220 wird das zugeordnete Paritätsbit ebenfalls ausgelesen
und in einem dritten Schritt L230 die Parität des vorbestimmten Datenworts
mit dem Wert des zugeordneten Paritätsbits verglichen. Stimmen
beide überein,
wird in einem Schritt L240 das vorbestimmte Datenwort über den
bidirektionalen Bus 170 ausgegeben und in einem Schritt
L250 der Leseprozess beendet.
-
Stimmen
beide Wert, also die Parität
des ausgelesenen Datenworts und der Wert des zugeordneten Paritätsbits,
nicht überein,
was auf einen Einbitfehler hindeutet, so wird in einem Schritt L260 zunächst der
Korrekturwert 140 des Datenblocks 110 ausgelesen.
Darüber
hinaus werden in einem nächsten
Schritt L270 die anderen Datenwörter
ebenfalls ausgelesen. In einem folgenden Schritt L280 werden auf
Basis der anderen Datenwörter
die zugehörigen Teilkorrekturwerte
berechnet und zusammen mit dem Korrekturwert 140 in einem
Schritt L290 zu dem Teilkorrekturwert des vorbestimmten Datenwortes
verknüpft.
In einem Schritt L300 wird der so gewonnene Teilkorrekturwert analysiert
und bewertet. Ergibt diese Analyse, dass eine Korrektur des Datenwortes möglich ist,
wird diese Korrektur im Rahmen eines Schrittes L310 durchgeführt und
der Prozess mit dem Schritt L210 fortgesetzt. Ergibt die Analyse
des Teilkorrekturwertes hingegen, dass keine Korrektur möglich ist,
wird im Rahmen eines Schrittes L320 beispielsweise über die
Fehlererkennungseinrichtung 150 und über den bidirektionalen Bus 170 an
die externe Komponente 180 eine Fehlermeldung ausgegeben
und der Leseprozess in einem Schritt L330 mit einem Fehler beendet.
-
Die
in dem Teilschritt L290 durchgeführte Verknüpfung der
Teilkorrekturwerte der anderen Datenwörter und des Korrekturwertes 140,
der dem Datenblock 110 zugeordnet ist, wird wiederum, wie
dies bereits bei dem in 2 gezeigten Ausführungsbeispiel
der Fall war, eine bitweise XOR-Verknüpfung durchgeführt. Aufgrund
der Eigenschaften der bitweisen XOR-Verknüpfung und im Zusammenhang mit
in 2 beschriebenen Ausführungsbeispiels zum Speichern
des Datenblocks 110 in dem Speicher 100 ist das
Ergebnis dieser Verknüpfung
gerade der Fehlerkorrekturcode bzw. der Teilkorrekturwert des von dem
Paritätsfehler
betroffenen, vorbestimmten Datenworts.
-
Die
vorliegende Erfindung kann ebenfalls zusammen mit einem Cache-Speicher
eingesetzt werden, wenn ein solcher Einsatz gewünscht oder benötigt wird,
um beispielsweise eine noch schnellere Lieferung eines Datums zu
ermöglichen.
Selbst wenn ein solcher Cache-Speicher eine schlechte Cachetrefferrate
bzw. Hitrate aufweisen sollte, wenn also beispielsweise ein auf
einem Prozessor ablaufendes Programm eine Vielzahl verschiedener
Daten aus dem Speicher anfordert, die nicht in dem Cache bzw. Cache-Speicher
zwischengespeichert sind, kann die vorliegende Erfindung dies ganz
oder zumindest teilweise kompensieren.
-
Im
Fall, dass ein Cache-Speicher Verwendung findet, kann im Zusammenhang
mit dem Cache-Speicher ein sogenannter „Wrapping Burst Fill"-Prozess angewendet
werden. Dies bedeutet, dass zuerst das eigentlich benötigte Datenwort
aus dem Speicher in den Cache-Speicher eingelagert wird, wobei mit
Hilfe des dem Datenwort zugeordneten Fehlererkennungswertes unmittelbar
im Zuge des Einlagerns in den Cache-Speicher die Integrität bzw. die
Fehlerfreiheit des betreffenden Datenwortes überprüft werden kann. Somit erlaubt
der Fehlererkennungswert die sofortige Lieferung des Datenwortes
an eine externe Komponente bzw. eine nachgeschaltete Empfängereinheit 180,
beispielsweise eine CPU (CPU = central processing unit = Zentralprozessor),
einen anderen Speicher, eine Ein-/Ausgabeeinheit, einen Spezialprozessor,
einen Kryptoprozessor oder eine andere Einheit. Während das
benötigte
Datenwort bereits der nachgeschalteten Empfängereinheit 180 zur
Verfügung
gestellt wurde, können
die übrigen
fehlende Datenwörter 120-1,
..., 120-n des Datenblocks 110 in den Cache-Speicher,
der üblicherweise
blockorganisiert aufgebaut ist, eingelagert werden. Somit erlauben
die erfindungsgemäßen Verfahren
ebenfalls eine deutliche Steigerung der Ausführungsgeschwindigkeiten und
eine erhebliche Reduzierung des Energieaufwands, was insbesondere
für mobile
Anwendungen, wie beispielsweise Handys, PDAs (PDA = personal data
assistant = persönlicher Datenassistent)
und andere tragbare Geräte,
von Vorteil ist.
-
Mit
anderen Worten, falls nun eines der Datenwörter 120-1, ..., 120-n des
Gesamtblocks bzw. des Datenblocks 110 eine Paritätsfehler
aufweist, so kommt der folgende Korrekturalgorithmus zur Anwendung:
Es werden jeweils die Teilfehlerkorrekturcodes der nicht von dem
Paritätsfehler
betroffenen Datenwörter
berechnet. Sodann wird die XOR-Summe über diese gebildet und das
Ergebnis mit dem gespeicherten Summenfehlerkorrekturcode bzw. Korrekturwert 140 ebenfalls über eine
XOR-Verknüpfung summiert.
Das Ergebnis ist der Fehlerkorrekturcode des von dem Paritätsfehler
betroffenen Datenworts, mit dessen Hilfe sich nun der einzelne Bitfehler
korrigieren lässt.
-
Die
in den 2 und 3 gezeigten Ausführungsbeispiele
der erfindungsgemäßen Verfahren basieren
so darauf, dass die Fehlerkorrekturcodes nicht über den gesamten Datenblock 110 berechnet werden,
sondern jeweils unabhängig
voneinander über
die einzelnen Datenwörter 120-1,
..., 120-n. Die so erhaltenen Teilfehlercodes bzw. Teilkorrekturwerte werden
sodann miteinander verknüpft
und zusammen mit dem Datenblock 110 als Korrekturwert 140 gespeichert.
Da der Fehlerkorrekturcode für
ein Teildatenwort bzw. Datenwort häufig eine geringere Bitbreite
als ein Korrekturwert 140 über den gesamten Datenblock
aufweist, kann, eine geeignete Verknüpfung vorrausgesetzt, wie die
bitweise XOR-Verknüpfung
(XOR = exclusive-or = exklusiv-oder), der benötigte Speicherplatz zum Speichern
des Korrekturwerts 140 weiter reduziert werden. Kommt es
hier dann zu einem Fehler, der eine Korrektur eines Datenwortes
notwendig macht, müssen
in diesem Fall die Teilkorrekturwerte der nicht von dem Fehler betroffenen
Datenwörter
berechnet 120-1, ..., 120-n und mit dem abgespeicherten
Korrekturwert 140 verknüpft
werden, um den Teilkorrekturwert zu dem angeforderten Datenwort
zu erhalten. Mit seiner Hilfe lässt
sich nun der einzelne Bitfehler in dem angeforderten Datenwort korrigieren.
-
Bei
den in den 2 und 3 beschriebenen
Ausführungsbeispielen
der erfindungsgemäßen Verfahren
zum Auslesen und Speichern kann neben einer Korrektur der eigentlichen
Datenworte 120-1, ..., 120-n auch eine Korrektur
eines eventuell im Bereich der Paritätsbits 130-1, ..., 130-n auftretenden Einbitfehler
durchgeführt
werden. Diese Möglichkeit, Fehler
auch im Bereich der Paritätsbits
bzw. der Fehlererkennungswerte 130-1, ..., 130-n zu
korrigieren, muss allerdings nicht zwingend implementiert werden.
So ist es im Prinzip durchaus denkbar, dass die zusätzliche
Absicherung gegenüber
einem Fehler im Bereich der Paritätsbits 130-1, ..., 130-n die Länge des
Korrekturwertes 140 unvorteilhaft um ein Bit vergrößern kann,
wenn beispielsweise ein Datenwort nur ein Länge von 4 Bit aufweisen sollte.
In diesem Fall wäre
zur Absicherung gegenüber
einem Einbitfehler ein Fehlerkorrekturwert mit einer Länge von
3 Bit notwendig. Wird jedoch zusätzlich
das zugeordnete Paritätsbit
ebenfalls gegen Fehler abgesichert, beträgt die Länge der abzusichernden Bits
5, was ein zusätzliches
Fehlerkorrekturbit erforderlich machen würde. Die in den 2 und 3 beschriebenen Verfahren
sind insbesondere also dann vorteilhaft, wenn nur ein geringer Speicherplatz
zur Verfügung steht,
wie dies bei Spezialchips, Chipkarten, integrierten Schaltungen
oder anderen kleinen, speicherplatzoptimierten Anwendungen der Fall
ist.
-
4 zeigt
ein Flussdiagramm eines zweiten Ausführungsbeispiels des erfindungsgemäßen Verfahrens
zum Speichern eines Datenblocks 110 in den Speicher 100.
Bei diesem Ausführungsbeispiel handelt
es sich im Vergleich zu dem in 2 gezeigten
ersten Ausführungsbeispiel
um eine leicht abgewandelte Version, bei der der Korrekturwert 140 bzw. ein
aus ihm abgeleiteter Teilkorrekturwert nicht mehr nur zur Korrektur
eines einzigen Datenwortes der Mehrzahl von Datenwörtern 120-1 ,..., 120-n herangezogen
werden kann, sondern sich auf den vollständigen Datenblock 110 bezieht.
Das in 4 gezeigte Ausführungsbeispiel unterscheidet
sich von dem in 2 gezeigten Ausführungsbeispiel
im Wesentlichen nur in zwei Punkten, die die Erzeugung des Kontrollwertes 140 betreffen.
Beide Ausführungsbeispiele
verlaufen bis zu dem Schritt S220, bei dem die Paritätsbits 130-1,
..., 130-n erzeugt werden, parallel. Im Unterschied zu
dem in 2 gezeigten Ausführungsbeispiel wird jedoch
der Schritt S230, bei dem in 3 die Teilkorrekturwerte
berechnet wurden, nicht ausgeführt.
Statt dessen werden im Rahmen eines modifizierten Schrittes S240', der den Schritt S240
in dem in 2 gezeigten Ausführungsbeispiel ersetzt,
der Kontrollwert 140 auf Basis des gesamten Datenblocks 110 erzeugt.
Auch dieses Ausführungsbeispiel
des erfindungsgemäßen Verfahrens
zum Speichern eines Datenblocks 110 wird mit den beiden
Schritten S250, bei dem der Datenblock 110 gespeichert
wird, und dem Schritt S260 beendet.
-
Das
zu dem in 4 gezeigten Ausführungsbeispiel
des erfindungsgemäßen Verfahrens zum
Speichern eines Datenblocks 110 gehörende Ausführungsbeispiel zum Auslesen
eines vorbestimmten Datenwortes ist in Form eines Flussdiagramms
in 5 illustriert und unterscheidet sich ebenfalls
nur geringfügig
von dem Ausführungsbeispiel
zum Auslesen eines vorbestimmten Datenwortes, das in 3 gezeigt
ist. Auch hier betreffen die Unterschiede im Wesentlichen nur die
vorbereitenden Schritte, die zu der Durchführung der eigentlichen Korrektur
im Fall des Vorliegens eines Fehlers (Schritt L310) führen. Das
in 5 gezeigte Ausführungsbeispiel unterscheidet
sich von dem in 3 gezeigten Ausführungsbeispiel
bis einschließlich
des Schrittes des Auslesens des Korrekturwertes 140 in Schritt
L260 nicht. Im Unterschied allerdings zu dem in 3 gezeigten
Ausführungsbeispiel
werden die Schritte L270, L280 und L290 nicht ausgeführt. Der Schritt
L300 des in 3 gezeigten Ausführungsbeispiels
wird durch einen modifizierten Schritt L300' ersetzt, bei dem der in Schritt L260
ausgelesenen Korrekturwert 140 dahingehend analysiert wird,
um zu beurteilen, ob im Falle eines Vorliegens eines Fehlers eine
Korrektur grundsätzlich
möglich
ist. Ist eine solche Korrektur nicht möglich, wird das erfindungsgemäße Verfahren
analog zu dem Vorgehen im Rahmen des in 3 gezeigten
Ausführungsbeispiels mit
dem Schritt L320, nämlich
der Ausgabe einer Fehlermeldung, fortgesetzt. Ist eine Korrektur
möglich,
so wird diese im Rahme des Schrittes L310 analog zu dem in 3 gezeigten
Ausführungsbeispiel ebenfalls
durchgeführt
und die Ausleseoperation anschließend mit dem Schritt L210,
also analog zu dem in 3 gezeigten Ausführungsbeispiel,
fortgesetzt.
-
Die
in den 4 und 5 gezeigten Ausführungsbeispiele
der erfindungsgemäßen Verfahren zum
Speichern eines Datenblocks und zum Auslesen eines vorbestimmten
Datenwortes aus einem Speicher 100 unterscheiden sich also
im Wesentlichen von den beiden Ausführungsbeispielen, die in den 2 und 3 gezeigt
sind, nur dadurch, dass sie ohne das beschriebene Teilfehlercodesummieren
mit Hilfe einer XOR-Verknüpfung
auskommen. Ausgehend von dem bereits oben angegebenen Beispiel einer
Netto-Datenblockgröße von 16
Bytes, die beispielsweise aufgrund des Bussystems in n = 4 Teilwörter bzw.
Datenwörter 120-1,
..., 120-n mit jeweils 4 Byte aufgeteilt werden, ergibt
sich somit schon aufgrund der Netto-Datenblockgröße von 128 Bit ein Fehlerkorrekturcode
bzw. ein Korrekturwert 140 mit einer Breite von mindestens
8 Bit. Damit wäre
der Gesamtcode für
die Fehlererkennung und die Fehlerkorrektur inklusive der 4 Paritätsbits 130-1,
..., 130-n der 4 Datenwörter 120-1,
..., 120-n bei einem Speicheraufwand von 12 Bit. Im Vergleich
zu einer in den einführenden
Abschnitten der vorliegenden Anmeldung skizzierten möglichen
Lösung
mit einer ursprünglichen,
geplanten Fehlercodelänge
von 8 Bit bzw. 9 Bit ist diese Lösung
jedoch nur bedingt konkurrenzfähig.
Trotzdem können
auch diese, auf den ersten Blick unvorteilhaft erscheinenden Ausführungsbeispiele
der erfindungsgemäßen Verfahren zum
Speichern eines Datenblocks bzw. zum Auslesen eines vorbestimmten
Datenwortes enorme Vorteile aufweisen. Können beispielsweise aufgrund
von konstruktiven Beschränkungen,
Sicherheitsanforderung oder anderen Gründen einige Schritte des in 3 gezeigten
Ausführungsbeispiels
nicht schnell, also in einem oder wenigen Taktzyklen erfolgen, so kann
es je nach Maßgabe
von Randbedingungen vorteilhaft sein, auf die zusätzlichen
Berechnungs-, Auslese- und Verknüpfungsschritte
zugunsten eines höheren
Speicherplatzbedarfs zu verzichten, da hierdurch die Korrekturzeit
eventuell verkürzt
werden kann. Im Vergleich zu einer auch in den einführenden Abschnitten
der vorliegenden Anmeldung skizzierten Lösung bleibt der Vorteil einer
schnellen Auslesung und schnellen Überprüfung auf das Vorliegen eines Fehlers
auch bei dem in 5 gezeigten Ausführungsbeispiel
bestehen, so dass zumindest in dem Fall, wenn kein Fehler vorliegt,
ein schnelleres Auslesen eines vorbestimmten Datenwortes ermöglicht wird.
-
Eine
weitere Möglichkeit,
dass erfindungsgemäße Verfahren
zum Auslesen eines vorbestimmten Datenwortes einzusetzen, besteht
im Bereich von Sicherheitsapplikationen mit größeren Schutzcodewörtern bzw.
erweiterten Korrekturwerten 140. Die Paritätsbits bzw.
Fehlererkennungswerte 130-1, ..., 130-n werden
dazu verwendet, Einbitfehler auszuschließen bzw. zu detektieren. Im
Rahmen einer Sicherheitsüberprüfung werden
jedoch trotzdem alle Datenwörter 120-1,
..., 120-n ausgelesen, um den Fehlercode bzw. den Korrekturwert 140 am
Ende überprüfen zu können. Diese
Vorgehen erlaubt immer noch die schnelle Lieferung des eigentlich
gewünschten
Datenworts, ermöglicht
aber auf der anderen Seite eine Überprüfung des
Speichers auf einen Angriff hin. Im Falle beispielsweise eines Mehrbitfehlers,
der mit Hilfe eines Paritätsbits
im Allgemeinen nicht mehr detektierbar ist und der in der Regel von
Sicherheitsbausteinen als Angriff gewertet wird, kann so die Speichersteuereinheit
beispielsweise durch die Fehlererkennungseinrichtung 150 oder
die Fehlerkorrektureinrichtung 160 durch Ausgeben eines
Alarmsignals einen Abbruch der laufenden Aktion, beispielsweise
in Form eines Sicherheitsresets, initiieren. Im Weiteren Verlauf
der vorliegenden Anmeldung werden so zwei Ausführungsbeispiele des erfindungsgemäßen Verfahrens
zum Auslesen eines vorbestimmten Datenworts beschrieben, wie sie
im Bereich von Sicherheitsapplikationen eingesetzt werden können. Diese
beiden Ausführungsbeispiele stellen
hierbei Modifikationen der in den 3 und 5 gezeigten
Ausführungsbeispiele
des erfindungsgemäßen Verfahrens
zum Auslesen eines vorbestimmten Datenworts dar.
-
6 zeigt
so ein drittes Ausführungsbeispiel
des erfindungsgemäßen Verfahrens
zum Auslesen eins vorbestimmten Datenwortes aus einem Speicher 100,
das für
den Einsatz im Rahmen einer Sicherheitsapplikation modifiziert ist
und auf dem in 5 gezeigten Ausführungsbeispiel
basiert. Dieses Ausführungsbeispiel
unterscheidet sich von dem in 5 gezeigten
Ausführungsbeispiel
nur in dem Fall, dass der Vergleich der Parität des ausgelesenen Datenwortes
mit dem zugeordneten Wert des Paritätsbits in Schritt L230 übereinstimmt.
In diesem Fall wird auch bei dem in 6 gezeigten
Ausführungsbeispiel
im Rahmen von Schritt L240 das Datenwort ausgegeben. In einem daraufhin
folgenden Schritt L242 werden die anderen Datenwörter 120-1, ..., 120-n ausgelesen.
In Schritt L245 wird daraufhin der Korrekturwert 140 ausgelesen
und in Schritt L247 analysiert. Wird im Rahmen dieser Analyse kein
Fehler gefunden, wird das Ausleseverfahren in Schritt L250' beendet. Wird jedoch
im Rahmen von Schritt L247 ein Fehler festgestellt, so wird in Schritt
L248 ein Alarmsignal ausgegeben und in Schritt L250'' das Verfahren beendet. Das Alarmsignal
zeigt in diesem Fall einen Mehrbitfehler an, da ein Einbitfehler
bereits durch die vorangegangene Überprüfung der Paritätsbits 130-1,
..., 130-n in Schritt L230 hätte erkannt werden müssen. Da,
wie in den einleitenden Abschnitten der vorliegenden Anmeldung erläutert wurde,
Mehrbitfehler kaum vorkommen, werden diese von Sicherheitsbausteinen
oder Security-Controllern in der Regel als Angriff gewertet, so
dass als Gegenmaßnahme
nur der Abbruch der laufenden Aktion, beispielsweise in Form eines
Sicherheitsresets, bleibt, der dann von dem Alarmsignal beispielsweise ausgelöst werden
kann.
-
7 zeigt
ein Flussdiagramm eines vierten Ausführungsbeispiels des erfindungsgemäßen Verfahrens
zum Auslesen eins vorbestimmten Datenwortes aus einem Speicher 100,
das auf Basis des in 3 gezeigten Ausführungsbeispiels
für den
Einsatz im Rahmen einer Sicherheitsapplikation modifiziert wurde. Ähnlich dem
in 6 gezeigten Ausführungsbeispiel unterscheidet
sich das in 7 gezeigten Ausführungsbeispiel
von dem in 3 gezeigten nur in Bezug auf
die Schritte, die nach dem in Schritt L230 erfolgten Vergleich der
Parität
des ausgelesenen Datenwortes und des Werts des zugeordneten Paritätsbits ausgeführt werden,
wenn bei diesem Vergleich kein Unterschied festgestellt wird. Auch
in diesem Fall wird zunächst
in dem Schritt L240 das Datenwort ausgegeben. Anschließend werden
in dem Schritt L242 die anderen Datenwörter aus dem Speicher 100 ausgelesen.
In einem Schritt L244 werden auf Basis der in Schritt L242 ausgelesenen
Datenwörter
die Teilkorrekturwerte berechnet. In Schritt L245 wird der Korrekturwert 140 aus
dem Speicher 100 ausgelesen und in einem folgenden Schritt
L246 zusammen mit den in dem Schritt L244 berechneten Teilkorrekturwerten
zu dem Teilkorrekturwert des ursprünglich in Schritt L210 ausgelesenen
Datenwortes verknüpft.
In Schritt L270' wird
dieser Teilkorrekturwert analysiert. Wir auf Basis dieser Analyse
ein Fehler festgestellt, so wird in Schritt L248 ein einen Mehrbitfehler
anzeigendes Alarmsignal ausgegeben und in Schritt L250'' das Verfahren zum Auslesen beendet.
Wird hingegen im Rahmen von Schritt L247' kein Fehler festgestellt, so wird das
Verfahren mit Schritt L250' sofort
beendet. Auch hier kann das Alarmsignal von einem Sicherheitsbaustein
wieder als Anzeichen für
einen erfolgten Angriff gewertet werden und zu entsprechenden Gegenmaßnahmen, wie
dem schon erwähnten
Sicherheitsreset, dem Löschen
sensibler Daten, der gezielten Zerstörung einzelner Komponenten
oder anderer Gegenmaßnahmen,
führen.
-
Abweichend
zu dem in 7 gezeigten Ausführungsbeispiel
kann alternativ beispielsweise auch auf Basis aller Datenwörter 120-1,
..., 120-n eine Berechnung der jeweiligen Teilkorrekturwerte
durchgeführt
werden, die anschließend
zu einem Zwischenkorrekturwert verknüpft werden, der wiederum mit dem
in dem Datenblock 110 gespeicherten Korrekturwert 140 verglichen
wird. Auf Basis dieses Vergleichs kann dann ebenfalls eine Entscheidung
stattfinden, ob der Speicher 100 einem Angriff unterworfen
wurde, so dass ein Alarmsignal in Schritt L248 ausgegeben werden
muss, oder ob kein Angriff auf den Speicher 100 stattgefunden
hat.
-
Darüber hinaus
können
die in den 6 und 7 gezeigten
Ausführungsbeispiele
auch dahingehend modifiziert werden, dass das vorbestimmte Datenwort
erst dann ausgegeben wird, wenn im Rahmen einer Überprüfung auf einen Angriff hin
ein solcher nicht festgestellt wurde. Nachteilig an dieser Lösung ist
jedoch der Verlust der Steigerung der Geschwindigkeit der Ausleseoperation,
die gerade die in 6 und 7 gezeigten
Ausführungsbeispiele
ermöglichen.
Darüber
hinaus bietet es sich an, im Rahmen einer Sicherheitsapplikation
den in dem Datenblock 110 gespeicherten Korrekturwert 140 dahingehend
zu erweitern oder zu modifizieren, dass dieser gegenüber einer
Manipulation resistenter gemacht wird. Neben einer Verschlüsselung
des entsprechenden Korrekturwertes 140 ist es auch möglich, als
Korrekturwert 140 einen für eine mögliche Korrektur notwendigen
Fehlerkorrekturcode um einen aus dem Datenblock 110 abgeleiteten
Einweg-Hash-Funktionswert erweiterten Wert abzuspeichern. Als Einweg-Hash-Funktionen
kommen hier beispielsweise die Funktionen bzw. Algorithmen MD2,
MD5, SHA (mit Unterversionen) oder RIPEMD-160 in Frage.
-
Als
weitere mögliche
Ausgestaltung der in den 3, 5, 6 und 7 gezeigten
Ausführungsbeispiele
des erfindungsgemäßen Verfahren
zum Auslesen eines vorbestimmten Datenwortes kann nach dem Durchführen der
Korrektur in Schritt L310 alternativ das vorbestimmte Datenwort
korrigiert und ausgegeben werden, ohne dass eine erneute Prüfung des
gespeicherten Datenwortes durch einen erneuten Durchlauf der Schritte
L210 bis L230 stattfindet. Ebenso ist es möglich, nach der Korrektur in
Schritt L310 das Datenwort auszugeben und erst im Anschluss daran
den korrigierten Datenblock 110 in den Speicher 100 zu
speichern.
-
Als
Fehlererkennungsalgorithmus kann neben einem eine gerade oder ungerade
Parität
eines Datenwortes anzeigenden Paritätsbit im Rahmen einer Paritätsüberprüfung, also
der Überprüfung, ob die
Zahl der gesetzten Bits der Datenwörter gerade oder ungerade ist,
auch jeder andere Algorithmus verwendet werden, der eine Erkennung
eines Fehlers zulässt.
Besonders vorteilhaft ist die Verwendung eines Paritätsbits im
Zusam menhang mit einer Paritätsüberprüfung jedoch,
da diese im Allgemeinen sehr schnell, also innerhalb eines Taktes
des Systems, durchgeführt
werden kann und der notwendige Speicherplatz für die Fehlererkennungswerte 130-1, ..., 130-n minimal
ist. Ebenso können
verschiedene Fehlerkorrekturalgorithmen bzw. Korrekturalgorithmen
eingesetzt werden. Nur ein Beispiel stellt der in dem Buch von U.
Tietze und Ch. Schenk dargestellte Hamming-Code dar.
-
Grundsätzlich ist
die vorliegende Erfindung natürlich
auf alle Speichertypen anwendbar, die einen lesenden und einen schreibenden
Zugriff ermöglichen.
Neben magnetischen und optischen Speichermedien, wie beispielsweise
Festplatten, Magnetbänder,
CD-R, CD-RW, DVD+R, DVD-R, DVD+RW, DVD-RW und anderen optischen
Speichermedien kommen hier auch nicht-flüchtige
Speichertypen (NVM = non-volatile memory), wie beispielsweise alle flash-basierten
Produkte, sowie RAM-Speichertypen (RAM
= random access memory = Speicher mit wahlfreiem Zugriff) in Frage.
Besonders vorteilhaft kann die vorliegende Erfindung im Zusammenhang
mit Speichertypen eingesetzt werden, die einen schnellen Datenzugriff
ermöglichen
sollen. Zu diesen Speichertypen zählen insbesondere die nicht-flüchtigen Speicher
und die RAM-Speichertypen, sowie Cache-Speicher. Grundsätzlich ist
auch der Einsatz der vorliegenden Erfindung im Rahmen von ROM-Speichertypen
(ROM = read-only memory = Nur-Lese-Speicher) denkbar, wenn auch
in diesem Fall die erfindungsgemäßen Verfahren
zum Speichern von Datenblöcken
während
des Betriebs nicht bzw. kaum, sondern nur im Rahmen der Programmierung bzw.
Herstellung eingesetzt werden können.
-
Abhängig von
den Gegebenheiten können das
erfindungsgemäße Verfahren
zum Auslesen eines vorbestimmten Datenwortes und das erfindungsgemäße Verfahren
zum Speichern eines Datenblocks in einen Speicher in Hardware oder
in Software implementiert werden. Die Implementation kann auf einem
digitalen Speichermedium, insbesondere einer Diskette, CD oder DVD
mit elektronisch auslesbaren Steuersignalen erfolgen, die so mit
einem programmierbaren Computersystem zusammenwirken können, dass
das erfindungsgemäße Verfahren
zum Auslesen eines vorbestimmten Datenwortes aus einem Speicher
oder das erfindungsgemäße Verfahren zum
Speichern eines Datenblocks in einen Speicher ausgeführt werden.
Allgemein besteht die Erfindung somit auch in einem Computer-Programm-Produkt mit
einem auf einem maschinenlesbaren Träger gespeicherten Programmcode
zur Durchführung
eines der erfindungsgemäßen Verfahren,
wenn das Computer-Programm-Produkt auf einem Rechner abläuft. In
andern Worten ausgedrückt
kann die Erfindung somit als ein Computer-Programm mit einem Programmcode
zur Durchführung
eines der Verfahren realisiert werden, wenn das Computer-Programm auf einem
Computer abläuft.
-
- 100
- Speicher
- 110
- Datenblock
- 120-1
- Datenwort
- 120-n
- Datenwort
- 130-1
- Fehlererkennungswert
- 130-n
- Fehlererkennungswert
- 140
- Korrekturwert
- 150
- Fehlererkennungseinrichtung
- 160
- Fehlerkorrektureinrichtung
- 170
- bidirektionaler
Bus
- 180
- externe
Komponente