-
TECHNISCHES GEBIET
-
Die
vorliegende Erfindung bezieht sich auf ein Verfahren zur und eine
Vorrichtung zum Erkennen von Fehlern beim Schreiben in einen nichtflüchtigen
Speicher. Die Erfindung bezieht sich auch auf ein Verfahren zur
und einer Vorrichtung zum Korrigieren des Ergebnisses von solchen
Fehlern. Solche Techniken können
in eingebauten Systemen verwendet werden, und Beispiele von geeigneten
Anwendungen enthalten: Chipkarten, wie etwa Javakarten; aktive digitale
Speicher oder Sicherheitsvorrichtungen, wie etwa Chiptasten und
Chipdisketten; SIMs und USIMs für
Mobiltelefone; Datenerfassungsvorrichtungen; kleine Vorrichtungen,
welche Benutzervorgaben, Speichereinstellungen oder Meldeanwendungen
aufzeichnen; Computersysteme in Fahrzeugen; Digitalempfänger; und
Internetrouter. Solche Techniken sind für nichtflüchtige oder „permanente" Speicher der „erst schreiben,
dann im Gesamten löschen" Art, wie etwa Flash-Speicher,
und der „nur schreiben" Art.
-
HINTERGRUNDTECHNIK
-
Der
Begriff „nichtflüchtiges
Datenelement" oder „PDI", wie hierin verwendet,
ist definiert, um ein Datenelement zu sein, dem ein Wert zugeordnet
ist, der sich über
die Zeit verändert,
insbesondere, wenn er durch ein Anwendungsprogramm aktualisiert
wird, und das benötigt
wird, um seinen Status zwischen solchen Aktualisierungen beizubehalten,
insbesondere, wenn die Anwendung nicht läuft und wenn der Strom vorsätzlich ausgeschaltet
wird, wenn die Anwendung ausgeschaltet wird, oder unbeabsichtigt, beispielsweise
aufgrund eines Stromausfalles oder dem Entfernen von einer Stromquelle.
-
Computerprogramme
arbeiten durch das Lesen und Aktualisieren der Werte von Variablen.
Für Variable
in RAM stellt dies kaum eine Schwierigkeit dar, da die Werte so
oft wie notwendig erneut geschrieben werden können und das Lesen und Schreiben
schnell ist. Wenn das Programm nicht läuft, muss sein Status in mehr
dauerhaften Speicher gespeichert werden.
-
Auf
kleinen Computerplattformen, wie etwa Chipkarten, gibt es wenig
RAM und der nichtflüchtige Speicher
erhält
oftmals die Form von EEPROM oder Flash-Speicher. Dieser Speicher hat die Eigenschaft, dass,
sobald ein Bit verändert
worden ist, dieser nicht erneut verändert werden kann, bis das
gesamte Segment gelöscht
wird. In EEPROM kann die Segmentgröße so klein wie ein einzelnes
Byte (8 Bits) sein, und der Speicher kann notwendigerweise wie ein sehr
langsamer RAM behandelt werden. Im Flash-Speicher sind die Segmente
im Allgemeinen groß (zum
Beispiel 64 KB) für
die Nutzungseffizienz der Siliziumfläche, und die Löschbetriebsweise
ist langsam. Ebenso wird sich der Speicher eventuell nach einiger
Anzahl von Löschzyklen
(angenommen 100000 für
Flash mit hoher Qualität)
abnützen.
Der Vorteil von Flash-Speicher ist der, dass er schneller ist und
dass sehr viel mehr in einen gegebenen Chipbereich gepackt werden
kann, so dass mehr Speicherraum zur Verfügung steht, jedoch ist er schwieriger
ein EEPROM effizient auszunutzen.
-
Man
betrachte eine Chipkarten-Anwendung, welche eine Aufnahme von Datum
und Zeit (die vielleicht von einem Kartenleseterminal erhalten wird) bei
jedem Mal, an dem sie läuft,
erhält
und die das Intervall zwischen den Läufen überprüft. Dies könnte für eine Sicherheitsfunktion
verwendet werden, wie etwa zum Durchsetzen einer täglichen
Abbuchungsgrenze für
eine Geldkarte. Jedes Mal, wenn sie läuft, muss sie das alte Datum
lesen, es überprüfen und das
neue Datum speichern. Das Datum ist daher ein PDI. Wenn das Datum
in dem gleichen Ort gespeichert würde, jedes Mal, wenn es wechselt,
würde der gesamte
64 K Speicherblock aufgrund der physikalischen Speichergrenzen als
erstes gelöscht
werden müssen,
und dies würde
eine lange Zeit in Anspruch nehmen und den Flash-Speicher schnell
abnützen.
-
Statt
jedes Mal das neue Datum zu schreiben, muss es in einem neuen Bereich
des Speichers gespeichert werden. Es wird angenommen, das dieses
Programm den Flash-Speicher mit anderen Programmen teilen muss,
so dass es nicht effizient ist, einen großen Speicherblock vom Flash-Speicher
nur für
diese eine Anwendung im Vorhinein zu vergeben. Mit anderen Worten
können
viele PDIs in dem System sein und sie könnten abhängig von den laufenden Anwendungen
mit unterschiedlichen Raten aktualisiert werden.
-
Eine
bekannte Anordnung zum Speichern von PDIs bildet eine verknüpfte Kette
von Werten für jeden
PDI, wie es in 1 der beigefügten Zeichnungen dargestellt
ist. Das erste Element der Kette ist eine bekannte Adresse. Für die oben
genannte besondere Anwendung speichert jedes Element der Kette einen
Wert für
die Datumsaufnahme und hat einen Raum für einen Pointer zu dem nächsten Element
in der Kette. Das letzte Kettenelement wird einen Pointerwert gleich
dem gelöschten
Speichermuster (FFFF in hexadezimal in diesem Modell, wo der gelöschte Status
jedes Bits 1 oder in dem komplementären Modell 0000 ist, wobei
der gelöschte Status
jedes Bits 0 ist) haben. Um das gegenwärtige Datum zu lesen, startet
das Lesen an dem Anfang der Kette und folgt den Pointern bis einer
mit dem Wert FFFF erreicht ist. Um ein neues Datum hinzuzufügen, wird
ein neues Kettenelement mit dem neuen Wert und einem leeren Pointer
erzeugt. Die Adresse wird dann über
den Pointerteil des vorhergehenden letzten Elements gespeichert.
-
Wenn
der Speicherblock voll ist, müssen
nur die letzten Werte für
jeden PDI in einen frischen Speicherblock kopiert werden, nachdem
der alte Speicherblock gelöscht
wird. Dies wird als „Speicherbereinigung" bezeichnet. Während der
Speicherbereinigung wird der letzte Wert in der Kette in den neuen
Speicherblock kopiert und als der Anfang der neuen Kette verwendet.
-
Wenn
Strom von einem Flash-Speicher während
eines Schreibzyklus unterbrochen wird, besteht eine Gefahr, dass
der Vorgang unvollständig
sein wird und dass ein widersprüchlicher
Zustand erhalten wird, wenn Strom erneut zugeführt wird. In dem Fall einer
kontaktlosen Chipkarte mit Flash-Speicher hat die Karte selbst keine
Stromzufuhr, sondern verlässt sich
auf einen empfangenen Strom von einem Kartenleser, wenn sie daran
präsentiert.
Wenn die Karte von dem Leser während
eines Schreibvorgangs in dem Flash-Speicher entfernt wird, kann
die Stromversorgung während
des Schreibzyklus unterbrochen werden, so dass die aktuell gespeicherten
Daten sich von den Daten unterscheiden, welche gespeichert werden
sollten.
-
Beispielsweise
in einem typischen Flash-Speicher ist der gelöschte Status jedes Bit 1 und
jedes Bit kann während
eines Schreibzyklus in 0 verändert
werden, jedoch kann die umgekehrte Änderung von 0 in 1 nur durch
das Löschen
jeweils einer gesamten Seite oder Segmentes erreicht werden. Auch,
wenn ein Schreibzyklus unterbrochen wird, wird jedes Bit, das von
1 in 0 verwandelt werden soll, entweder in 0 verändert oder verbleibt bei 1.
Typischerweise wird ein gesamtes, 16 Bits umfassendes Wort parallel
zu dem Flash-Speicher geschrieben. Wenn ein Schreibvorgang durch
Stromverlust unterbrochen wird, können einige oder alle der benötigten Veränderungen
von 1 in 0 stattgefunden haben, jedoch ist es unmöglich, festzustellen,
welche Veränderungen
stattgefunden und welche (wenn überhaupt
eine) nicht stattgefunden haben. Wenn Strom wieder zugeführt wird,
kann die Chipkarte nicht mitteilen, ob die gespeicherten Daten aufgrund
des Stromverlustes während
eines Schreibzyklus unbrauchbar geworden sind.
-
Im
Fall der verknüpften
Kette, wie sie in
1 der beigefügten Zeichnungen dargestellt
ist und wie sie zuvor beschrieben ist, oder in dem Fall der Anordnung,
die in der
britischen Patentanmeldung
Nr. 0205573.9 (Veröffentlichungs-Nr.
GB-A-2386212 ) offenbart ist, welche
eine verbesserte Anordnung beschreibt, ist der gegenwärtige Wert jedes
Datenelements der Letzte in der verknüpften Kette oder Liste. Wenn
der Strom ausfüllt,
wenn der Pointer an den letzten Wert in dem Flash-Speicher geschrieben
wird, kann es nicht möglich
sein, den letzten Wert abzurufen, wenn der Strom wieder einsetzt.
Jede Anmeldung, die sich auf solch einen letzten Wert verlässt, wird
daher nicht korrekt funktionieren oder kann im Gesamten nicht funktionieren.
-
US 6,412,080 kann betrachtet
werden, um ein nicht flüchtiges
Speichersegment zu beschreiben, in dem Werte von wenigstens einem
Datenelement in zeitlich konsequent aufeinander folgenden Speicherorten
gespeichert werden, wobei jeder neue Speicherort an ein erstes Ende
eines Speicherblocks des Speichersegmentes mit ersten und zweiten
Enden hinzugefügt
wird, und ein Pointer zu jedem neuen Speicherort an einen alten
Speicherort in dem Speicherblock, der einen vorausgehenden Wert
des wenigstens eines Datenelementes enthält, hinzugefügt wird.
-
BESCHREIBUNG DER ERFINDUNG
-
Gemäß einem
ersten Aspekt der Erfindung wird hier ein Verfahren zur Erkennung
von Fehlern in einem nicht flüchtigen
Speichersegment bereitgestellt, in dem Werte von wenigstens einem
Datenelement in zeitweise aufeinander folgend angeordneten Speicherorten
gespeichert sind, wobei jeder neue Speicherort an ein erstes Ende
eines Speicherblocks des Speichersegmentes, das erste und zweite
Enden aufweist, hinzugefügt
wird, und in dem ein Pointer zu jedem neuen Speicherort an einem
alten Speicherort in dem Speicherblock, der einen vorhergehenden Wert
von wenigstens einem Datenelement beinhaltet, hinzugefügt wird,
wobei das Verfahren die Schritte umfasst:
- (a)
Bestimmen der Adresse, auf die der zuletzt hinzugefügte Pointer
zeigt;
- (b) Vergleichen der bestimmten Adresse mit einem Adressbereich
des Speicherblocks, der den letzten neuen Speicherort beinhaltet;
und
- (c) Durchführen
einer Aktion, wenn sich die bestimmte Adresse außerhalb des Adressbereichs befindet.
-
Die
Schritte (a) bis (c) können
jederzeit durchgeführt
werden, wenn Strom an das Speichersegment zugeführt wird.
-
Der
Schritt (a) kann das Bestimmen der Adresse umfassen, auf die alle
die Pointer zeigen, und das Auswählen
der höchsten
oder niedrigsten Adresse.
-
Der
Schritt (c) kann das Verändern
der Adresse des zuletzt hinzugefügten
Pointers in die Adresse des letzten neuen Speicherortes umfassen.
-
Jeder
neue Speicherort kann angrenzend an das erste Ende des Speicherblocks
hinzugefügt
werden.
-
Jeder
Pointer kann zu einer höchsten
oder niedrigsten Adresse des Speicherortes zeigen, auf die er zeigt.
-
Das
Speichersegment kann wenigstens ein Teil eines Festspeichers umfassen.
-
Jeder
Speicherort kann Raum für
einen einzelnen Wert des wenigstens einen Datenelement aufweisen.
-
Jedes
Bit des Speichersegments kann individuell nur von 1 auf 0 schaltbar
sein, und die Aktion kann durchgeführt werden, wenn die erkannte
Adresse größer ist
als die höchste
Adresse des Adressbereichs. Als eine Alternative kann jedes Bit
des Speichersegmentes individuell nur von 0 auf 1 schaltbar sein,
und die Aktion kann durchgeführt
werden, wenn die erkannte Adresse geringer ist als die niedrigste Adresse
des Adressbereichs.
-
Das
Speichersegment kann wenigstens einen Schreibzähler enthalten, in dem ein
entsprechendes Flag an dem Ende jedes Wertspeichervorganges gesetzt
ist und ein entsprechendes weiteres Flag an dem Ende jeder Pointer-Hinzufügung gesetzt ist,
und die Schritte (a) bis (c) können
nur durchgeführt
werden, wenn eine ungerade Anzahl von Flags und weiteren Flags gesetzt
ist. Der wenigstens eine Schreibzähler kann ein Datenelement
umfassen.
-
Das
Speichersegment kann wenigstens einen Schreibzähler beinhalten, in dem, wenn
eine Reihe von einem oder mehreren Datenelementenwerten gespeichert
werden, ein entsprechendes Flag vor der ersten Pointer-Hinzufügung in
der Reihe gesetzt wird und ein entsprechendes weiteres Flag nach
der letzten Pointer-Hinzufügung in
der Reihe gesetzt wird, und die Schritte (a) bis (c) können nur
durchgeführt werden,
wenn eine ungerade Anzahl von Flags und weiteren Flags gesetzt ist.
-
Gemäß einem
zweiten Aspekt der Erfindung, wird hier ein Programm zum Steuern
eines Computers bereitgestellt, um ein Verfahren gemäß dem ersten
Aspekt der Erfindung durchzuführen.
-
Gemäß einem
dritten Aspekt der Erfindung wird hier ein Computer bereitgestellt,
der durch ein Programm gemäß dem zweiten
Aspekt der Erfindung programmiert ist.
-
Gemäß einem
vierten Aspekt der Erfindung wird hier ein Speichermedium bereitgestellt,
das ein Programm gemäß dem zweiten
Aspekt der Erfindung beinhaltet.
-
Gemäß einem
fünften
Aspekt der Erfindung wird hier eine Vorrichtung bereitgestellt,
die ein nicht flüchtiges
Speichersegment, Mittel, um Werte von wenigstens einem Datenelement
in zeitweise aufeinander folgend angeordneten Speicherorten zu speichern,
wobei jeder neue Speicherort an einem ersten Ende eines Speicherblockes
des Speichersegmentes hinzugefügt
wird, das erste und zweite Enden aufweist, Mittel, um einen Pointer
hinzuzufügen,
der auf jeden neuen Speicherort auf einem alten Speicherort in dem
Speicherblock zeigt, der einen vorgegebenen Wert von wenigstens
einem Datenelement beinhaltet, Mittel, um die Adresse zu bestimmen,
auf die der zuletzt hinzugefügte
Pointer zeigt, Mittel, um die bestimmte Adresse mit einem Adressbereich
des Speicherblocks zu vergleichen, der den letzten neuen Speicherort
enthält,
und Mittel aufweist, um eine Aktion durchzuführen, wenn sich die bestimmte Adresse
außerhalb
des Adressbereichs befindet.
-
Die
Bestimmungsmittel, die Vergleichsmittel und die Ausführungsmittel
können
angeordnet werden, um jedes Mal betätigt zu werden, wenn Strom an
der Vorrichtung angelegt ist.
-
Die
Bestimmungsmittel können
angeordnet werden, um die Adressen zu bestimmen, auf die alle Pointer
zeigen, und um die höchste
oder niedrigste Adresse auszuwählen.
-
Die
Ausführungsmittel
können
angeordnet werden, um die Adresse des zuletzt hinzugefügten Pointers
in die Adresse des letzten neuen Speicherortes zu ändern.
-
Jeder
neue Speicherort kann angrenzend an das erste Ende des Speicherblocks
hinzugefügt
werden.
-
Jeder
Pointer kann auf eine höchste
oder niedrigste Adresse des Speicherortes zeigen, auf die er zeigt.
-
Das
Speichersegment kann wenigstens einen Teil des Flash-Speichers umfassen.
-
Jeder
Speicherort kann Raum für
einen einzelnen Wert von wenigstens einem Datenelement aufweisen.
-
Jedes
Bit des Speichersegmentes kann individuell nur von 1 oder 0 schaltbar
sein, und die Ausführungsmittel
können
angeordnet sein, um die Aktion durchzuführen, wenn die erkannte Adresse
größer ist
als die höchste
Adresse des Adressbereichs. Als eine Alternative kann jedes Bit
des Speichersegmentes individuell nur von 0 auf 1 schaltbar sein,
und das Ausführungsmittel
kann angeordnet sein, um die Aktion auszuführen, wenn die erkannte Adresse niedriger
ist als die niedrigste Adresse des Adressbereichs.
-
Die
Vorrichtung kann umfassen: Mittel, um in wenigstens einem Schreibzähler in
dem Speichersegment ein entsprechendes Flag an dem Anfang jedes
Wertspeichervorganges und ein entsprechendes weiters Flag an dem
Ende jeder Pointer-Hinzufügung zu
setzen; und Mittel, um zu beurteilen, ob die Anzahl der gesetzten
Flags und der weiteren Flags ungerade ist, wobei die Bestimmungsmittel,
die Vergleichsmittel und die Ausführungsmittel angeordnet sind,
um als Antwort auf die Beurteilungsmittel betrieben zu werden. Der
wenigstens eine Schreibzähler
kann ein Datenelement umfassen.
-
Die
Vorrichtung kann umfassen: Mittel, um in wenigstens einem Schreibzähler in
dem Speichersegment und, wenn eine Reihe von einem oder mehreren
Datenelementenwerten gespeichert werden, ein entsprechendes Flag
vor der ersten Pointer-Hinzufügung
in der Reihe und ein entsprechendes weiteres Flag nach der letzten
Pointer-Hinzufügung
in der Reihe zu setzen; und Mittel, um zu beurteilen, ob die Anzahl
der gesetzten Flags und der weiteren Flags ungerade ist, wobei die
Bestimmungsmittel, die Vergleichsmittel und die Ausführungsmittel
angeordnet sind, um als Antwort auf die Beurteilungsmittel betrieben
zu werden.
-
Die Vorrichtung kann eine
Chipkarte umfassen
-
Es
ist folglich möglich,
eine Anordnung bereitzustellen, die es ermöglicht, Fehler in Pointern von
verknüpften
Ketten von PDIs und ähnlichen Strukturen
zuverlässig
zu erkennen. Diese Technik ermöglicht
es auch, solche Fehler zu korrigieren. Folglich wird beispielsweise
jede Anwendung beruhend auf den im Flash-Speicher gespeicherten
PDIs oder ähnlichem
davor bewahrt, versehentlich falsche, aus dem Speicher gelesene
Daten zu verwenden.
-
KURZE BESCHREIBUNG DER ZEICHNUNGEN
-
Die
Erfindung wird ferner als Beispiel unter Bezugnahme auf die beigefügten Zeichnungen
beschrieben, in denen:
-
1 ein
Diagramm ist, das eine bekannte verknüpfte Kette von PDI-Werten darstellt;
-
2 ein
Diagramm ist, das eine Vorrichtung darstellt, die ein Ausführungsbeispiel
der Erfindung bildet;
-
3 ein
Diagramm ist, das die Betriebsweise der Vorrichtung von 2 zusammen
mit einem Verfahren darstellt, das ein Ausführungsbeispiel der Erfindung
bildet; und
-
4 ein
Flussdiagramm ist, das das Verfahren darstellt.
-
BESTE UND ART UND WEISE ZUM
DURCHFÜHREN
DER ERFINDUNG
-
2 stellt
eine Chipkarte der „kontaktlosen" Art dar, um mit
einem Kartenleser zusammenzuarbeiten, um Daten zu transferieren.
Die Karte 1 hat in sich eingebettet einen Computer 2 und
einen Flash-Speicher 3, die gezeigt sind, wie sie einige
Seiten oder Segmente umfassen. Der Computer 2 umfasst eine
zentrale Prozessoreinheit (CPU) 4, die mit einem Arbeits-Schreib-Lese-Speicher
(RAM) 5 und einer Eingabe/Ausgabe-Schnittstelle (I/O) 6 zur
kontaktlosen Kommunikation mit einem Kartenleser bereitgestellt
ist. Die Karte 1 weist keine interne Stromversorgung auf,
sondern verlässt
sich stattdessen auf eine externe Stromversorgung 7, die
innerhalb des Kartenlesers (nicht gezeigt) vorgesehen ist. Der Computer 2 und
der Speicher 3 werden folglich nur mit Strom versorgt,
wenn die Karte 1 korrekt in einen Kartenleser eingeführt ist.
-
Das
Flash-Speicher-Segment, das in 2 dargestellt
ist, ist konfiguriert, um als ein permanenter Speicher für nichtflüchtige Datenelemente
(PDIs) zu dienen. Folglich, wohingegen Daten, welche nicht bei Abwesenheit
von Strom gespeichert werden müssen,
den Arbeits-RAM 5 verwenden, welcher flüchtig ist, werden PDIs, dessen
Werte bei Abwesenheit von Strom erhalten werden müssen, in
dem Flash-Speicher-Segment
gespeichert.
-
Das
in 2 dargestellte Flash-Speicher-Segment ist konfiguriert,
um eine Seitenkennung und einen Status 8 zu speichern,
beispielsweise um anzuzeigen, ob die Seite in Verwendung ist oder
gelöscht
worden ist, und in Zukunft zur Verwendung fertig ist, eine PDI-Tabelle 9,
die einen Pointer für
jeden PDI zeigt, der an den Ort oder „Knoten" zeigt, der den ersten Wert des in dem
Segment gespeicherten PDI beinhaltet, einen Zähler 10 kritischer Schreibvorgänge, und
Knoten, in die Werte des PDIs bereits geschrieben worden sind. Das
Segment weist freien Raum auf, wie es in 11 dargestellt
ist, und welches derzeitig das zuletzt verwendete Speicherwort (LUM)
ist, das angeordnet werden sollte, wie es bei 12 gezeigt
ist.
-
Wenn
die Karte 1 anfänglich
konfiguriert wird, gibt der Computer 2 die Seitenkennung
und den Status 8 ein, und reserviert Raum in dem Speicher 3 für die PDI-Tabelle 9 und
den Zähler 10 kritischer Schreibvorgänge. Wenn
der erste Wert des ersten PDI in den Speicher 3 geschrieben
ist, wird für
den Wert des Elementes und für
einen Pointer in einen nächsten
Wert ausreichenden Raum an dem Anfang des Speichersegmentes bei
Knoten 15 angeordnet. Ein Pointer wird zusammen mit dem
ersten PDI in die Tabelle 9 eingefügt und zeigt zu dem letzten
Wort des Knotens 15, wie es durch den Pfeil 16 dargestellt
ist.
-
Der
Flash-Speicher 3 ist von der Art, bei der, wenn das Segment
gelöscht
wird, jedes seiner Bits auf 1 gesetzt wird. Folglich werden alle
Bits des Zählers 10 anfänglich auf
1 gesetzt. Ebenso werden die Bits des Wortes an dem Knoten 15,
der für
den Pointer zu dem nächsten
Wert des PDI reserviert ist, alle auf 1 gesetzt und warten auf das Überschreiben, wenn
der nächste
Wert ankommt.
-
In
dem in 2 dargestellten Beispiel ist der als nächstes zu
speichernde Wert in dem Speicher 3 ein zweiter Wert des
ersten PDI. An dem Anfang des Schreibzyklus wird ein neuer Knoten 17 zum
Speichern des zweiten PDI-Wertes zugeordnet. Beispielsweise hat
das letzte Wort des Knotens, welcher nachfolgend einen Pointer auf
einen Knoten für
einen letzteren Wert des PDI beinhalten wird, wenigsten sein wichtigstes
Bit auf 0 gesetzt. Da alle Pointer auf geradzahligen Adressen sind,
besteht hier kein Konflikt mit dem nachfolgenden Schreiben eines
Pointers in dieses Wort. Genügend
Speicherraum ist zwischen dem Wort für den Pointer und den vorhergehenden
Knoten 15 vorgesehen, um die zweiten Datenwerte des ersten
PDI zu beinhalten. Der Knoten kann derart zugeordnet sein, dass
er mit dem Knoten 15 angrenzend ist, beispielsweise so,
dass er die Verwendung des Speicherraumes maximiert, oder eine Lücke kann übrig bleiben,
beispielsweise um sicherzustellen, dass sein Pointer an einer geraden Adresse
ist, wenn der zweite Datenwert ungerade ist. Jedoch ist das Steuern
des Schreibens in das Speichersegment derart, dass Knoten immer
an dem Ende des Raumes hinzugefügt
werden, der zuvor angeordnete Knoten beinhaltet, und niemals zwischen bestehenden
Knoten eingefügt
werden.
-
In
dem nächsten
Schritt des Schreibzyklus wird der zweite Datenwert des ersten PDI
in dem Teil des Knotens 17, der für die Datenspeicherung erhältlich ist,
gespeichert. Das erste Bit des Zählers 10 wird auf
0 gesetzt, um die erfolgreiche Beendigung des Datenschreibvorgangs
anzuzeigen. Ein Pointer auf die Adresse des letzten Wortes des Knotens 17,
der einem nachfolgenden Pointer zugeordnet ist, wird dann in dem
Pointerfeld des Wortes 15 geschrieben. Das zweite Bit des
Zählers 10 wird
dann auf Null gesetzt, um die Beendigung des Schreibzyklus anzuzeigen.
-
Der
nächste
Wert, welcher in dem Speichersegment des Flash-Speichers 3 gespeichert
werden soll, ist der erste Wert eines zweiten PDI. An dem Anfang
des Schreibzyklus wird der nächste
erhältliche Knoten 18 zugeordnet,
nachdem der Wert in das Datenwertfeld des Knotens 18 geschrieben
ist. Ein Pointer auf das letzte Wort des Knotens 18 (das
heißt
jenes mit der höchsten
Adresse), welcher nachfolgend einen Pointer enthalten wird, wird
an dem zweiten Ort in der PDI-Tabelle 9 gespeichert.
-
Der
vierte, in dem Speicher 3 zu speichernde Wert ist der zweite
Wert des zweiten PDI. Wie es hierin zuvor beschrieben ist, wird
der nächste
erhältliche
Knoten 19 dadurch zugeordnet, dass das am wenigsten wichtigste
Bit seines letzten oder höchsten Adressenwortes
auf 0 gesetzt wird, wobei der Datenwert in das Wertefeld des Knotens 19 geschrieben wird,
das dritte Bit des Zählers 10 auf
0 gesetzt wird, wobei ein Pointer auf das letzte Wort des Knotens 19 in
dem Pointerfeld (das letzte oder höchste Adressenwort) des Knotens 18 geschrieben
wird, und das vierte Bit des Zählers 10 auf
Null gesetzt wird.
-
Dieser
Vorgang wird jedes Mal wiederholt, wenn ein neuer Wert von einem
der PDIs zum Schreiben in das Segment des Speichers 3 ankommt.
Insbesondere wird jeder neue Wert in einen Knoten geschrieben, der
dem Knoten, der den zuvor empfangenen Wert zum Speichern beinhaltet,
folgt (und angrenzend damit sein kann). Ein nächstes Bit des Zählers 10 wird
nach dem Schreiben des Wertes in den neuen Knoten auf Null gesetzt
und ein anderes Bit des Zählers
wird auf Null gesetzt, wenn der Pointer auf das neue Wort in das
Pointerfeld des Knotens, der den vorhergehenden Wert des gleichen
PDI beinhaltet, geschrieben worden ist.
-
In
dem Fall, wo die in der
britischen
Patentveröffentlichung
Nr. 0205573.9 offenbarten Technik verwendet wird, kann
der Pointer nicht in den Knoten geschrieben werden, der den direkt
vorhergehenden Wert des gleichen PDI beinhaltet, sondern kann stattdessen
in ein „entferntes
Feld" eines Knotens,
der einen früheren
Wert des gleichen PDI beinhaltet, geschrieben werden. Diese Patentanmeldung
beschreibt auch eine Technik, wo das Wertefeld jedes Knotens geeignet
ist, verschiedene Werte seines PDI zu speichern. Folglich wird ein
neuer Knoten für
das PDI nur zugeordnet, wenn jede der Wertefelder befüllt worden
sind. Wenn solch eine Technik verwendet wird, ist es für Werte
nach dem ersten, welche in den Knoten geschrieben sind nicht notwendig,
für einen Zwischenpointer
in einen vorhergehenden Knoten geschrieben zu werden. Es ist auch
für den
Zähler
10 kritischer
Schreibvorgänge
nicht nötig,
aktualisiert zu werden. Folglich wird der hierin zuvor beschriebene Vorgang
nur verwendet, wenn das Wertefeld des Knotens befüllt worden
ist und es notwendig ist, einen neuen Knoten für das PDI zuzuordnen. Solch eine
Anordnung kann zum Speichern des Zählers
10 verwendet
werden und kann eine effizientere Verwendung des Speicherraumes
bieten.
-
Tatsächlich und
wie es oben erwähnt
ist, wenn ein neuer Knoten für
einen neuen PDI-Wert zugeordnet wird, werden genügend Bytes zugeordnet, um den
Wert und den nächsten
Pointer zu speichern, und dies wird durch das Setzen eines Bits
durchgeführt,
mit dem, was nun der neue LUM ist. Wenn jeder Pointer innerhalb
des Speichersegmentes zwei Bytes verwendet und Wörter immer bei geraden Adressen
gespeichert werden, kann dann das niedrigste Bit in dem Pointerfeld
des neuen Knotens auf 0 gesetzt werden. Dies bietet eine Kennzeichnung
der höchsten
Adresse innerhalb des Speichersegments, welches zu jeder Zeit zugeordnet
worden ist, da alle Bits bei Adressen oberhalb jenem des LUM in
ihrem zurückgesetzten
1-Zustand sein werden.
-
Wenn
der Computer 2 den derzeitigen Wert von einem der PDIs
finden muss, folgt er dem Pfad, der durch die Pointer definiert
ist, der in dem zeitlich aufeinander folgend angeordneten Knoten
für den PDI
gespeichert ist. Folglich identifiziert der Computer 2 den
Pointer in der PDI-Tabelle 9 zu dem Knoten, der den ersten
Wert beinhaltet, und überprüft, ob der Pointer
in dem Knoten auf eine gültige
Adresse zeigt. In diesem Fall überprüft der Computer
den Knoten, auf den der Pointer zeigt. Wenn der Computer erkennt,
dass ein gespeicherter Pointer einen angeordneten Knoten darstellt,
aber keinen Pointer enthält, ist
der an dem Knoten gespeicherte Wert als der gegenwärtige Wert
des PDI bekannt, und er wird durch den Computer verwendet.
-
Wenn
die Stromzufuhr von der Karte 1 entfernt wird, während ein
Pointer in das entsprechend Wortfeld des Speichersegments geschrieben
wird, kann der Wert des Pointers, der gespeichert wird, falsch sein.
Da das Schreiben in den Speicher 3 das Umschalten der Bits
von 1 auf 0 involviert, führt
ein unvollständiger
Schreibzyklus dazu, dass der binäre Wert
des gespeicherten Bitmuster für
den Pointer größer ist
als der beabsichtigte Wert, da er mehr 1er aufweist, als er aufweisen
sollte. Dies ermöglicht
es einem Pointer, Schreibfehler zu erkennen und zu korrigieren.
-
4 stellt
ein Verfahren dar, welches jedes Mal durchgeführt wird, wenn Strom an die
Karte 1 angelegt wird. Das Verfahren oder die Routine wird
bei 20 gestartet, und bei 21 erreicht der Computer 2 das Speichersegment
für den
gegenwärtigen
LUM 12. Beispielsweise startet der Computer 2 von
der höchsten
Adresse in dem Speichersegment und arbeitet sich in Richtung der
niedrigsten Adresse durch, wobei es jedes Wort im Wechsel überprüft, bis
eines gefunden ist, wo nicht alle der Bits gleich 1 sind. Die Adresse
dieses Wortes wird dann die Adresse des LUM. Der Computer 2 speichert
dann die Adresse des LUM in das RAM 5.
-
Bei
Schritt 22 überprüft der Computer 4,
ob der Zähler 10 kritischer
Schreibvorgänge
eine gerade Anzahl von gesetzten Bits beinhaltet. Jedes Mal, wenn
ein neuer PDI-Wert in das Flash-Speicher-Segment erfolgreich geschrieben
wird, werden zwei Bits des Zählers 10 auf
0 gesetzt. Umgekehrter Weise, so oft ein Schreibvorgang angefangen
hat, jedoch nicht beendet ist, bevor der Strom von der Karte 1 entfernt ist,
wird nur 1 Bit auf 0 gesetzt, so das der Zähler 10 eine ungerade
Anzahl von gesetzten Bits beinhaltet. Demgemäß ist es möglich, durch das Zählen der
Anzahl von 0en indem Zähler 10 zu
erkennen, ob ein möglicher
Schreibfehler stattfand.
-
Wenn
der Zähler 10 eine
gerade Anzahl von 0en beinhaltet, ist kein weiteres Eingreifen erforderlich,
und die in 4 gezeigte Routine endet bei 23. Wenn
die Zahl ungerade ist, sucht dann der Computer 2 in einem
Schritt 24 nach einem Pointer in den Worten, die in dem
Speichersegment gespeichert sind, mit einem Wert, welcher größer ist
als die Adresse des LUM, die zuvor in dem RAM 5 in Schritt 21 gespeichert
ist. Jeder Pointer mit dem Wert FFFF oder FFFE wird ignoriert, da,
obwohl es auf eine Adresse zeigt, die größer ist als jene des gegenwärtigen LUM,
es einen Pointer darstellt, welcher jetzt nicht auf einen angeordneten
Knoten zeigt. Andererseits muss jeder falsche Pointer eine Adresse
haben, welche größer ist
als die Adresse des gegenwärtigen LUM.
Auch ist der korrekte Wert für
jeden solcher Pointer die Adresse des LUM.
-
In
einem Schritt 25 bestimmt der Computer 2, ob ein
falscher Pointer gefunden wurde. Wenn nicht, setzt ein Schritt 26 das
nächste
Bit des Zählers 10 auf
Null und die Routine endet bei 23. Wenn ein fehlerhafter
Pointerwert gefunden ist, korrigiert ein Schritt 27 den
Pointerwert in die Adresse des LUM, um so den Pointerwert zu korrigieren.
Der Schritt 26 wird dann vor dem Beenden bei 23 durchgeführt, so dass
der Zähler 10 eine
gerade Anzahl von 0en beinhaltet, die anzeigen, dass hier nicht
länger
ein Fehler besteht.
-
3 stellt
ein spezifisches Beispiel dar, wo ein Fehler aufgetreten war, der
erkannt und nachfolgend korrigiert wird. Der erste Wert (Datenwert
0) eines PDI wird an einem PDI-Knoten 30 gespeichert, dessen
letztes Wort oder Pointerfeld eine Adresse 0014 ist. Ein Pointer
auf das letzte Wort des Knotens 30 wird in der PDI-Tabelle 9 gespeichert.
Wenn der nächste
Wert (Datenwert 1) des PDI ankommt, findet Computer 2 den
Pointer für
den PDI in der Tabelle 9 und überprüft das Pointerfeld 31,
um festzustellen, dass der Knoten 30 den direkt vorhergehenden
Wert des PDI beinhaltet. Der nächste
Wert wird in das Wertefeld des Knotens 32 geschrieben,
und die Adresse 1234 wird in das Pointerfeld 31 an dem
Knoten 30 (alle Pointer werden hexadezimal ausgedrückt) eingegeben.
Der Zähler 10 wird
wie hierin zuvor beschrieben aktualisiert.
-
Wenn
der nächste
Wert (Datenwert 2) des gleichen PDI gespeichert werden soll, folgt
der Computer 2 dem Pfad der Pointer und bestimmt, dass
der Knoten 32 den direkt vorhergehenden Wert beinhaltet.
Der nächste
verfügbare
Raum für
einen Knoten in dem Speichersegment wird aufgesucht, und ein Knoten
wird mit seinem Pointerfeld bei Adresse 2200 angeordnet. Die Zuordnung
des Knotens wird durch das Verändern
des niedrigsten Bits der Adresse 2200 auf 0 und folglich durch das
Hinterlassen FFFE in dem Pointerfeld durchgeführt. Der Datenwert 2 wird
in dem Wertefeld des Knotens 33 gespeichert, und das nächste nicht-0
Bit des Zählers 10 wird
auf Null gesetzt. Es wird damit begonnen, einen Pointer auf den Knoten 33 in das
Pointerfeld des Knotens 32 zu schrieben, jedoch wird der
Strom unterbrochen, beispielsweise durch das Zurückziehen der Karte 1 von dem
Kartenleser, bevor dies beendet ist, so dass ein unvollständig geschriebener
Pointer 2274 in dem Pointerfeld des Wortes 32 vorhanden
ist. Insbesondere sollte der binäre
Wert 0010001000000000 in das Pointerfeld des Knotens 32 geschrieben
worden sein, jedoch wurde statt dessen der binäre Wert 0010001001110100 geschrieben,
da das Umschalten des dritten, fünften,
sechsten und siebten Bits von 1 auf 0 nicht durchgeführt wurde,
bevor der Strom unterbrochen wurde.
-
Wenn
der Strom als nächstes
an die Karte 1 angelegt wird, wird die in 4 gezeigte
Routine durchgeführt.
Diese bestimmt, dass das Adressenfeld des Knotens 33 bei
dem LUM gespeichert ist, und dass die Adresse des Pointers, die
in dem Pointerfeld des Knotens 32 gespeichert ist, einen
Wert hat, der höher
als die Adresse 2200 des LUM ist. Das Schreiben des korrekten Pointers
in dem Pointerfeld des Knotens 32 ist daher durch das Umschalten
der entsprechenden Bits in diesem Feld beendet, um die korrekte
Adresse 2200 darzustellen.
-
Es
ist folglich möglich,
falsch geschriebene Pointer zu erkennen und zu korrigieren. Der
nur zusätzlich,
innerhalb des Segmentes benötigte
Raum des Flash-Speichers 3 ist der, für den Zähler 10 kritischer
Schreibvorgänge.
Der Zähler 10 benötigt einen relativ
geringen Raum in dem Segment oder kann in einem unterschiedlichen
Segment gespeichert werden. Folglich können Pointerfehler erkannt
und mit geringem Aufwand im Hinblick auf den verminderten Speicherraum
in dem Speicher korrigiert werden.
-
In
einem Ausführungsbeispiel,
wie es oben beschrieben ist, beinhaltet ein Speichersegment einen
Zähler
kritischer Schreibvorgänge,
in dem ein Flag an dem Ende eines jeden Wertespeichervorganges gesetzt
wird und ein weiteres Flag an dem Ende jeder Pointer-Hinzufügung gesetzt
wird. Dies stellt sicher, dass, während einem kritischen Schreiben,
um die Pointer-Adresse zu aktualisieren, der Zähler kritischer Schreibvorgänge einen
ungeraden Wert anzeigt. Jedoch ist es auch möglich, dass, wo hier ein Satz
von Aktualisierungen an einem oder mehreren PDIs durchgeführt werden
muss, ein Flag in dem Zähler
kritischer Schreibvorgänge
vor der ersten Pointer-Hinzufügung
in dem Satz der Aktualisierungen und ein weiterer Flag nur nach
der letzten Pointer-Hinzufügung
in dem Satz von Aktualisierungen gesetzt werden kann. Wenn der Strom
zwischen den Sätzen
des Flags und dem Setzen des weiteren Flags ausfällt, wird eine Suche bei der
nächsten Stromzufuhr
stattfinden. Der Vorteil mit diesem Lösungsansatz ist der, dass der
Zähler
kritischer Schreibvorgänge
nur zwei mal während
dem Satz geschrieben wird, wobei folglich das System schneller wird,
wenigstens in dem Fall, wo der Strom nicht ausfällt.
-
In
einem alternativen Ausführungsbeispiel kann
der Zähler 10 kritischer
Schreibvorgänge
weggelassen werden. In diesem Fall kann der Computer 2 nicht
mitteilen, wenn der Strom erneut angelegt wird, ob irgendein Pointerfehler
aufgetreten sein könnte
und muss daher alle der gespeicherten Pointerwerte mit der Adresse
des LUM vergleichen. Wenn ein Pointerwert höher ist als die Adresse des
LUM, wird der Fehler erkannt und kann korrigiert werden, wie es
hierin zuvor beschrieben ist. Folglich, in dieser modifizierten
Technik, besteht kein Nachteil im Hinblick auf die verminderte Speicherkapazität, jedoch wird
durch den Computer 2 mehr Zeit benötigt, um nach irgendwelchen
Fehlern zu suchen.
-
In
dem Fall eines Flash-Speichers 3 mit mehr als einem Segment
zum Speichern von PDIs, kann die gleiche Technik für jedes
Segment verwendet werden. Insbesondere weist jedes Segment seinen eigenen
LUM auf, und wird verwendet, um eine Untermenge der PDIs zu speichern.
-
Es
ist auch möglich,
den Zähler 10 kritischer Schreibvorgänge durch
das Partitionieren des Raumes der PDIs in verschiedene Teile aufzuteilen,
wobei jeder Zähler
sich auf einen entsprechenden Teil bezieht. Beispielsweise, wo verschiedene
Seiten von Speicher vorliegen, kann ein entsprechender Zähler für jede aktive
Seite vorgesehen sein. Ebenso kann jede Seite mit einem separaten
Zähler
kritischer Schreibvorgänge
für jede
Partition aufgeteilt sein. Das Suchen und Korrigieren eines Fehlers
in jeder Partition ist schneller, jedoch wird mehr Speicherraum
durch verschiedene Zähler
kritischer Schreibvorgänge
benötigt
und jeder Zähler
muss überprüft werden,
wenn der Strom angelegt wird, um zu bestimmen, ob ein Fehler in
der entsprechenden Partition vorliegt.
-
Der
Zähler
kritischer Schreibvorgänge
kann auch wie ein PDI behandelt werden, dadurch, dass er in Segmenten
angeordnet wird. Das letzte Element in der Aktualisierungskette
ist dann der aktivierte Speicherblock des Zählers. Dies ermöglicht eine
kleinere Menge von Speicher, der anfänglich an dem Zähler angeordnet
werden soll, und, wenn das Segment nachfolgend mit einer kleineren
Anzahl von großen
PDIs füllt,
wird dann weniger Raum verbraucht.
-
Der
Zähler
kritischer Schreibvorgänge
kann in dem Segment gespeichert werden, auf das er sich bezieht,
oder kann in einem unterschiedlichen Segment gespeichert werden.
In dem vorhergehenden Fall ist es wichtig, sicherzustellen, dass
die neuen Segmente des Zählers
kritischer Schreibvorgänge nicht
in der Mitte einer anderen kritischen Aktualisierung angeordnet
sind. Andererseits hätte
das LUM, welches die andere Aktualisierung verwendet, sich geändert. Um
dies zu vermeiden, kann das neue Segment des Zählers kritischer Schreibvorgänge ein paar
Aktualisierungen früher
als benötigt
zugeordnet werden, und nicht dann, wenn eine kritische Aktualisierung
durchgeführt
wird.
-
Diese
Technik kann auf Flash-Speicher der Art angewendet werden, welche
derart zurückgesetzt werden,
dass alle ihre Bits auf 0 sind, und bei denen das Schreiben in dem
Speicher das Verändern
des Wertes eines Bits von 0 auf 1 involviert. Beispielsweise können alle
Pointer in umgekehrter oder komplementärer Form gespeichert werden
und sie können erneut
invertiert werden, wenn sie gelesen werden. Alternativ, wenn solch
ein Speicher verwendet wird, kann der erste zu speichernde Wert
an dem Knoten der höchsten
Adresse mit nachfolgenden Werten angeordnet werden, die an der nächst niedrigeren Adresse
angeordnet und gespeichert werden. Das Wort der niedrigsten Adresse
jedes Knotens wird als das Pointerfeld verwendet. In diesem Fall,
wenn ein Pointerwert falsch geschrieben ist, wird er auf eine Adresse
zeigen, welche niedriger ist als jene des LUM. Folglich kann ein
fehlerhafter Pointer erkannt werden und sein Wert korrigiert werden.
-
Diese
Techniken können
auch kombiniert werden, beispielsweise durch die Verwendung eines Flash-Speichers
der Art, wo Bits von 1 auf 0 geschrieben werden, wobei Speicher
von höheren
zu niedrigeren Adressen angeordnet und Pointer in ihrer umgekehrten
oder komplementären
Form gespeichert werden.
-
INDUSTRIELLE ANWENDBARKEIT
-
Die
vorliegende Erfindung bezieht sich auf ein Verfahren zur und einer
Vorrichtung zum Erkennen eines Fehlers beim Schreiben in einem nichtflüchtigen
Speicher. Die Erfindung bezieht sich auch auf ein Verfahren zur
und einer Vorrichtung zum Korrigieren des Ergebnisses solch eines
Fehlers. Solche Techniken können
in eingebetteten Systemen verwendet werden und Beispiele von geeigneten
Anwendungen enthalten: Chipkarten, wie etwa Java-Karten; aktive digitale
Speicher oder Sicherheitsvorrichtungen, wie etwa Chiptasten oder
Chipdisketten; SIMs und USIMs für
Mobiltelefone; Datenerfassungsvorrichtungen; kleine Vorrichtungen,
welche Benutzervorgaben, Speichereinstellungen oder Meldeanwendungen
speichern; Computersysteme in Fahrzeugen; Digitalempfänger und
Internetrouter. Solche Techniken sind für nichtflüchtige oder „permanente" Speicher der „erst schreiben
dann im Gesamten löschen" Art, wie etwa Flash-Speicher, und der „nur schreiben" Art nützlich.