PatentDe  


Dokumentenidentifikation DE102004018235A1 03.11.2005
Titel Verfahren zur Verwendung eines teilweise defekten Speichermediums mit reduzierter Kapazität
Anmelder Raake, Walter, 32457 Porta Westfalica, DE
Erfinder Raake, Walter, 32457 Porta Westfalica, DE
DE-Anmeldedatum 15.04.2004
DE-Aktenzeichen 102004018235
Offenlegungstag 03.11.2005
Veröffentlichungstag im Patentblatt 03.11.2005
IPC-Hauptklasse G11C 29/00
IPC-Nebenklasse G11B 20/18   
Zusammenfassung Beschrieben wird ein adaptives Verfahren der Fehlererkennung und der Fehlerkorrektur, welches es ermöglicht, teilweise defekte Speicherbauelemente (z. B. FLASH Speicher, Magnetplatten und Magnetbänder) zumindest mit eingeschränkter Speicherkapazität wieder verwenden zu können.
Dem Speicherbauelement muss dazu ein Mikroprozessor gesteuerter Controller vorgeschaltet werden, der bei der Initialisierung eine Analyse der speicherinternen Fehlerstruktur vornimmt. Entsprechend der Struktur dieser Fehler wird entweder ein Reed-Solomon (RS) Code geringer Korrekturfähigkeit, ein RS Code hoher Korrekturfähigkeit oder ein RS Produkt Code eingesetzt, um die verbleibende Speicherkapazität optimal nutzen zu können.
Je nach Applikation können Fehlerdetektion und Fehlerkorrektur getrennt in Hardware- und Softwarekomponenten realisiert werden. Der Mikroprozessor gesteuerte Controller übernimmt dabei neben der allgemeinen Speicherverwaltung auch die seltener benötigten, aber komplexeren Algorithmen der RS Fehlerkorrektur. Einfachere, oft benötigte Routinen der RS Algorithmen zur Codierung und Fehlererkennung (Syndrombildung) werden in einer dedizierten Hardware realisiert.

Beschreibung[de]
Stand der Technik

Grundsätzlich muss man bei allen nicht perfekten Speichermedien wie z.B. Magnetplatten, Magnetband oder Halbleiterspeichern mit Fehlern im Produktionsprozess rechnen. Bis zu einem gewissen Grad werden dabei Fehler toleriert. Über einen spezifizierten Grenzwert hinaus gehende Fehlerdichten führen zu einem als defekt ausgesonderten Speichermedium, das normalerweise nicht mehr verwendet werden kann. Der spezifizierte Grenzwert der Fehlerdichte basiert meist auf sehr einfachen Fehlererkennungsverfahren, wie z.B. dem Paritäts Check. Datenblöcke mit erkannten Fehlern werden nach Paritätsprüfung einfach von der normalen Benutzung ausgenommen.

Da im Laufe der Zeit noch weitere Fehler sporadisch im Speichermedium entstehen können, wird bei z.B. bei FLASH Controllern meist ein Einzelbit Fehler korrigierender Paritätscode in Matrixanordnung verwendet. Die Bits an den Kreuzungsstellen von Paritätsfehlern müssen zwecks Korrektur invertiert werden, so dass ein sehr einfacher Korrekturmechanismus implementiert wird. Solche Lösungen stehen bereits als ECC Controller für NAND FLASH Speicher zur Verfügung.

Neben diesen Einzelbit korrigierenden Codes verwenden Hersteller großer Solid State Disks (SSD), die aus vielen einzelnen FLASH Speicher Modulen bestehen, RS Codes, um die Zuverlässigkeit des Gesamtsystems mittels multipler Einzelfehlerkorrektur stark zu erhöhen. Dabei basiert das SSD System aber immer auf sehr zuverläsigen, qualifizierten Halbleiterspeichern, bei denen nur in seltenen Fällen einzelne Fehler erwartet werden. Siehe dazu auch www.bitmicro.com Produkte Edisk.

Nicht bekannt aus der Literatur oder dem Internet sind adaptive Korrekturverfahren, die auch bei stark fehlerhaften Speichermedien (NAND (NOR) FLASH, Magnetplatten und Magnetbänder) zunächst die existierenden Fehlerstrukturen analysieren und danach versuchen, möglichst viel verbleibende Restspeicherkapazität auf dem Medium mit Hilfe von mathematischen Fehlerkorrekturmethoden auszunutzen.

Beschreibung

Mit Magnetplatten oder FLASH Halbleiterspeichern können heute sehr große Speicherkapazitäten bis in den Gigabyte Bereich erreicht werden. Dabei geht man nur von einer geringen Menge tolerierbarer Fehler aus. Beispielsweise wird ein Maximum von 20 teilweise defekten Blöcken je Chip mit 1024 Blöcken Kapazität vom Halbleiterhersteller Samsung für NAND FLASH Memories des Typs K9F1G08x0M als garantierte Speicherkapazität spezifiziert. FLASH Speicher mit 21 defekten Blöcken oder mehr werden markiert und ausgesondert. Eine kommerzielle Nutzung solcher Ausschussteile aus der Produktion mit reduzierter Speicherkapazität ist Hintergrund der Erfindung.

Ein Verfahren entsprechend der Erfindung arbeitet mit einem Software gesteuerten Controller (Microprozessor) sowie einem mehrstufigen Fehlererkennungs- und Fehlerkorrektursystem auf einem fehlerhaften Speichermedium. Die Datenspeicherung wird mit adaptiver Redundanz zur Fehlerkorrektur an die Fehlerstruktur im einzelnen Datenblock eines Speichermediums anpasst. Physikalische Ortsveränderungen der Daten werden dynamisch entsprechend der Auslesehäufigkeit der Daten vorgenommen, damit die am meisten nachgefragten Daten in den fehlerfreien Blöcken des Mediums abgelegt und zeitaufwendige Korrekturen vermieden werden.

Die Anwendung von Reed-Solomon (RS) Codes, deren Fähigkeiten und die erreichbaren Korrekturfähigkeiten, werden dabei im Rahmen des beschriebenen Verfahrens für den durchschnittlichen Fachmann als bekannt vorausgesetzt.

Beispiele: Daten bleiben bei RS Codes unverändert, nur Prüfsymbole werden am Ende eines Blocks hinzugefügt. Erwähnt sei auch die Eigenschaft der RS Codes, dass es keinen Unterschied für die Decodierung gibt, ob die Fehler Bereiche der Daten- oder Prüfsymbole betreffen. Weiterhin zu nennen ist die Eigenschaft, dass zur Erkennung der Fehlerfreiheit eines Blocks einfach alle Syndrome den Wert Null haben müssen. Für die Spezifikation der Korrekturfähigkeit ist zu sagen, dass die Beseitigung eines Fehlers mit unbekanntem Ort zwei Prüfsymbole und die Beseitigung eines Fehlers mit bekanntem Ort (Error Pointer, Error Flag) nur ein Prüfsymbol erfordert.

Insbesondere sind mit mehrdimensionalen RS Codes größere und zusammenhängende Speicherfehler korrigierbar, wie etwa der Totalausfall eines oder mehrerer Datenbits (–1/8 Kapazität bei Byte weiser Organisation) oder eines Adressbits (–50% Kapazität) in allen Speicherebenen. Wesentlich ist, dass entsprechend des aufgezeigten Verfahrens die Reduktion der Speicherkapazität in der Größenordnung der tatsächlich ausgefallenen Speicherzellen liegt. Das heisst, für jedes fehlerhafte Bit ist inetwa ein intaktes Bit zur Kompensation notwendig. Die Redundanz der adaptiv eingesetzten fehlerkorrigierenden Codes entspricht damit cirka der Menge der fehlerhaften Bits. Infolge von nicht ganzzahlig teilbaren Blockgrößen und Fehlergrößen sowie anderer technischen Unzulänglichkeiten ist jedoch maximal von der doppelten Menge der defekten Bits als zusätzliche Redundanz zum Zwecke der Korrektur auszugehen.

Typischerweise werden die RS Codes mit einem aus Flip-Flops und Exor Gattern bestehenden Encoder codiert und mit einem ähnlichen Syndrom Generator decodiert. Ist das Syndrom bei der Decodierung ungleich Null, in zumindest einem Bit, so muss eine Fehlerkorrektur durchgeführt werden. Diese erfolgt am einfachsten in Software entsprechend der vielfältig veröffentlichten mathematischen Algorithmen zur Fehlerkorrektur mit RS Codes. Vorteilhafter Weise können auch ganze Rechensequenzen in Tabellen vorab gebildet und abgelegt sein. Damit werden von den Korrekturalgorithmen des Controllers nur noch Resultate nachgeschlagen, nicht aber Rechnungen in Echtzeit durchgeführt, um Rechenzeit zu sparen.

Die Klassifizierung von Fehlerstrukturen auf dem Speichermedium erfolgt bei der Initialisierung des Speichers mit dem Software gesteuerten Controller nach folgenden Kriterien:

  • a) Datenblöcke ohne Fehler
  • b) Datenblöcke mit Einzelfehlern
  • c) Datenblöcke mit Bündelfehlern,

    wie etwa 1 oder mehrere konstante Datenbits bei Halbleiterspeichern oder zeitweisen Datenausfällen (Drop Outs) bei magnetischen Medien
  • d) Datenblöcke mit konstanten Werten in allen Bits, die letztlich vollständig unbrauchbar sind.
  • e) Datenblöcke mit Veränderungen von Bits in anderen Datenblöcken, die nicht benutzt werden dürfen.

a) Datenblöcke ohne Fehler

Datenblöcke ohne Fehler werden identifiziert über Null-Syndrome von RS Codes, mindestens der Länge 16 bit, um eine ausreichende Sicherheit bei der Detektion zu gewinnen. Dabei muss der Block mit einem Datenmuster sowie dem inversen Datenmuster beschreibbar sein. Wichtig ist, dass die fehlerfreien Datenblöcke in eine spezielle Tabelle des Controllers eingetragen werden, um die häufigsten Zugriffe in fehlerfreie Datenblöcke zu lenken. Damit wird Rechenarbeit für Fehlerkorrekturen gespart. Mit den RS Code Prüfsymbolen wird die Fehlerfreiheit der Blöcke im Betrieb stetig kontrolliert, da langfristig Datenblöcke auch fehlerhaft werden können. Dieser Effekt tritt beispielsweise bei Halbleiterspeichern auf, wenn die Anzahl zulässiger Schreibzyklen überschritten wird.

b) Datenblöcke mit Einzelfehlern

Zufällige Bit- und Symbolfehler sind entsprechend der Erfindung ebenfalls mit eindimensionalen RS Codes geschützt und nur mit erhöhter Redundanz zum Zwecke einer verbesserten Korrekturfähigkeit versehen. Vorteil von RS Codes ist dabei, dass der Ort des Fehlers und die fehlerhaften Bits im Daten- oder Paritätssymbol bei Anwendung eines Korrekturalgorithmus bekannt werden. Damit lässt sich in der Software des Controllers die Anzahl von Fehlern genau überwachen und die Qualität der Datenblöcke kontinuierlich messen.

Wichtig ist wiederum, dass jeder Block mit einem Datenmuster sowie dem inversen Datenmuster beschreibbar sein muss, um auf Null oder Eins festgelegte Bits des Speichermediums zu identifizieren. Aus diesem Grunde kann es auch vorteilhaft sein, den Daten und Redundanzen eine Pseudo Zufallsfolge zu überlagern. Damit wird erreicht, dass Blöcke mit ausschliesslich Nullen praktisch nie vorkommen können. Die Pseudo Zufallsfolge ist dem Controller bekannt, erstreckt sich über keine größere Länge als einen Datenblock und kann bei der Wiedergabe, also dem Lesen von Daten, durch einfache Exor Bildung eliminiert werden.

c) Datenblöcke mit Bündelfehlern

Datenblöcke mit Bündelfehlern treten auf, wenn einzelne Bits eines Halbleiterspeichers 'klemmen' oder wenn Magnetschichten von Magnetspeichern mechanisch beschädigt sind.

Durch den Einsatz von Produktcodes in zwei oder mehr Dimensionen können auch solche Fehler korrigiert werden, wie etwa der Ausfall eines einzelnen Bits über alle Datensymbole oder der Ausfall einer Adressleitung. RS Produktcodes sind auf einer n ·m Datensymbolmatrix definiert. Insgesamt gespeichert werden aber (n + a)·(m + b) Datensymbole auf dem Medium.

Bezeichnen wir die inneren Code Symbole mit (n + a) und die äußeren Code Symbole mit (m + b), so kann folgende Decodierstrategie angewandt werden:

  • 1.) Lesen des inneren Codes und Durchführung der Fehlerdetektion und Korrektur einzelner Bits oder Symbole. Ist die Korrektur nicht möglich, obwohl Fehler angezeigt werden, so wird der gesamte Block mit einem Fehlermarker (Error pointer, Error Flag) gekennzeichnet.
  • 2.) Fehlerkorrektur im äußeren Code unter Zuhilfenahle der Fehlermarker des inneren Codes. Je RS Prüfsymbol ist damit ein fehlerhaftes Symbol korrigierbar. Zusätzliche Redundanz kann zur Überprüfung einer erfolgreichen Korrektur herangezogen werden.
  • 3.) Optional können nach den Korrekturen des äußeren Codes auf der (n + a)·(m + b) Matrix die inneren Codes (n + a) erneut ausgewertet werden. Damit läßt sich eine erhöhte Sicherheit gegen Fehlkorrekturen des äußeren Codes gewinnen. Fehlkorrekturen treten bei RS Codes nur bei völliger Überlastung durch Fehler auf. Kennt man aber die Fehlerstrukturen aus der Initialisierungsphase, so können Überlastungen sicher vermieden werden und der Schritt 3 entfällt.

d) Datenblöcke mit konstanten Werten in allen Bits

Diese Datenblöcke, die z.B. auf das Fehlen der magnetischen Beschichtung einer Magnetplatte in einem kleinen Bereich hindeuten, können nicht weiter korrigiert werden und müssen durch Eintrag in eine Tabelle von schlechten Blocks (Bad sector table) von der Verwendung ausgeschlossen werden.

e) Datenblöcke mit Veränderungen von anderen Datenblöcken

Diese Datenblöcke, die z.B. auf eine Verkopplung von Adressleitungen eines Halbleiterspeichers hindeuten, dürfen nicht weiter benutzt werden und müssen ebenso durch Eintrag in eine Tabelle von schlechten Blocks (Bad sector table) von der Verwendung ausgeschlossen werden.


Anspruch[de]
  1. Verfahren zur Verwendung eines teilweise defekten Speichermediums mit reduzierter Speicherkapazität, insbesondere bei Halbleiterspeichern, Magnetplatten und Magnetbandspeichern sowie anderen nicht perfekten Speichermedien dadurch gekennzeichnet, dass die Fehlerstruktur bei der Initialisierung des Mediums vermessen wird und notwendige Redundanzen zur Korrektur dieser Fehlerstrukturen blockweise adaptiv festgelegt werden.
  2. Verfahren zur Verwendung eines teilweise defekten Speichermediums mit reduzierter Speicherkapazität, insbesondere bei Halbleiterspeichern, Magnetplatten und Magnetbandspeichern sowie anderen nicht perfekten Speichermedien dadurch gekennzeichnet, dass eine dynamische Speicherverwaltung während des Betriebs die physikalische Lage eines Datenblocks dynamisch verändern kann, wenn eine unterschiedliche Häufigkeit der Zugriffe auf diesen Datenblock festgestellt wird, derart dass fehlerfreie Teile des Mediums die am häufigsten verwendeten Daten beherbergen und korrigierbare Teile des Mediums solche Daten tragen, die möglichst selten ausgelesen werden.
  3. Verfahren nach Anspruch 1 oder 2 dadurch gekennzeichnet, dass ein mittels Software programmierbarer Controller (Microprozessor) die adaptive und dynamische Speicherverwaltung durchführt.
  4. Verfahren nach Anspruch 1 oder 2 dadurch gekennzeichnet, dass zur Bestimmung der Fehlerstruktur im Speichermedium ein fehlerkorrigierender Reed-Solomon Code verwendet wird.
  5. Verfahren nach Anspruch 4 dadurch gekennzeichnet, dass zur Fehlerdetektion und Fehlerkorrektur ein Reed-Solomon Code verwendet wird, dessen Codierung und Syndromgenerierung in Hardware erfolgt und dessen Fehlerkorrektur durch Algorithmen in der Software eines Controllers (Microprozessor) durchgeführt wird.
  6. Verfahren nach Anspruch 1 oder 2 dadurch gekennzeichnet, dass zur Korrektur von systematischen Bündelfehlern (Media Drop Outs, Bitline Stuck at 0/1) ein fehlerkorrigierender Reed-Solomon Produktcode herangezogen wird, der eine mehrdimensionale Überlagerung von Reed-Solomon Codes über die zu schützenden Datensymbole darstellt.
  7. Verfahren nach Anspruch 4 oder 6 dadurch gekennzeichnet, dass die zur Fehlerkorrektur verwendete Redundanz höchstens die doppelte Menge der Speicherbits umfasst, die auf dem Speichermedium auch tatsächlich fehlerhaft sind.
  8. Verfahren nach Anspruch 1 oder 2 dadurch gekennzeichnet, dass die Daten vor der Aufzeichnung mit einer Pseudo Zufallsfolge überlagert werden, die bei der Wiedergabe durch eine Exor Verknüpfung mit der gleichen Pseudo Zufallsfolge wieder rückgängig gemacht wird.
  9. Verfahren nach Anspruch 1 oder 2 dadurch gekennzeichnet, dass der Programmcode des Controllers in dem gleichen Speichermedium gespeichert wird wie auch die zu speichernden externen Daten.
Es folgt kein Blatt Zeichnungen






IPC
A Täglicher Lebensbedarf
B Arbeitsverfahren; Transportieren
C Chemie; Hüttenwesen
D Textilien; Papier
E Bauwesen; Erdbohren; Bergbau
F Maschinenbau; Beleuchtung; Heizung; Waffen; Sprengen
G Physik
H Elektrotechnik

Anmelder
Datum

Patentrecherche

Patent Zeichnungen (PDF)

Copyright © 2008 Patent-De Alle Rechte vorbehalten. eMail: info@patent-de.com