Bit-Mathematik

Wie geschicktes Coding Flash-Speicherfehler korrigiert

Schon wenn Flash-Chips das Werk verlassen, sind einige ihrer Zellen defekt. Lesefehler führen im Betrieb zu falschen Ergebnissen. Von beiden Effekten merkt man nichts, weil Mathematik die meisten Fehler korrigiert.

Von Antonia Wachter-Zeh und Alexander Zeh

Anwender erwarten, dass eine SSD ihre wertvollen Daten fehlerfrei speichert. Doch Flash-Speicher ist nicht fehlerfrei, irgendeine Zelle ist immer defekt. Dazu kommen noch Fehler durch den Betrieb des Flash-Speichers. Da die SSD-Hersteller jedoch um diese Fehler wissen, speichern sie zu jedem Datenblock eine gewisse Menge an Zusatzinformationen. Diese Redundanzdaten dienen im Fehlerfall ausgeklügelten Algorithmen zur Korrektur der Werte. So erreichen SSDs insgesamt eine sehr kleine Fehlerquote, deren Wert man in den Datenblättern als Unrecoverable Bit Error Ratio (UBER) findet.

Die UBER liegt bei den meisten SSDs bei nur einem fehlerhaften Sektor pro 10¹⁶ oder 10¹⁷ gelesenen Bits. Mehr als einen nicht-korrigierbaren Lesefehler muss man selbst bei Hunderten von Terabytes nicht befürchten, wie die Praxis beweist. In einem solchen Fall ist die betroffene Datei defekt und nicht mehr lesbar. Doch zunächst zu den möglichen Fehlerursachen, dann zu den Korrekturmethoden.

Fehlerursache Wearout

SSD-Controller lesen oder beschreiben immer ganze Pages, einen meist 16 KByte entsprechend 131.072 Bit großen Speicherblock; auf einzelne Bits können sie nicht zugreifen. Zum Beschreiben müssen diese Pages komplett frei sein. Damit die SSD auch große Datenmengen schnell speichern kann, sollten immer möglichst viele Pages frei sein.

Der Controller nutzt daher Ruhezeiten zum Aufräumen: Er sucht nach nicht vollständig gefüllten Pages und speichert die in mehreren Pages enthaltenen Daten zusammen in einer leeren Page ab. Die so frei gewordenen Pages löscht er, was jedoch die Zellen ein klein wenig schädigt. Man spricht in diesem Zusammenhang von Wearout (Abnutzung, Verschleiß).

Eine einzelne Flash-Zelle übersteht zwischen 1000 und 100.000 Löschzyklen, auch Write- oder Erase-Cycles genannt [1]. Die ersten Flash-Zellen konnten nur ein einziges Bit (1 oder 0) speichern, dieser SLC-Flash (Single Level Cell) vertrug rund 100.000 Löschzyklen. Bei MLC-Flash mit zwei Bit Speicherkapazität pro Zelle (Multi Level Cell) sank dieser Wert auf 3000 bis 10.000 Zyklen, bei TLC- und QLC-Flash geht man von 3000 beziehungsweise 1000 Zyklen aus (TLC steht für Triple Level Cell; Flash mit drei Bit Speicherfähigkeit pro Zelle, QLC-Flash speichert vier Bit und steht für Quadruple Level Cell). Um alle Zellen möglichst gleichmäßig abzunutzen, verteilt der Controller die Schreibzugriffe (Wear Leveling).

Fehlerursache Read Disturb

Die immer weiter verkleinerten physischen Strukturen der Flash-Speicher wirken sich auf deren Zuverlässigkeit aus, das Problem des Read Disturb tritt in Erscheinung. Dabei verändert das Lesen einer Zelle die Schwellspannung (Threshold Voltage) benachbarter Zellen, die gerade nicht gelesen werden, wodurch beim Auslesen dieser Zellen ein Fehler auftreten würde [2, 4].

Bei SLC-Flash treten Read-Disturb-Fehler so selten auf, dass sie kaum untersucht wurden. In der ersten Generation von MLC-Flash wurden sie auch erst nach etwa 100.000 Lesevorgängen beobachtet. Bei neuerem TLC- und QLC-Flash treten sie jedoch schon nach etwa 10.000 Lesevorgängen auf; bei ungleichmäßiger Verteilung der Lesezyklen sogar deutlich früher.

Fehlerursache Inter-Cell Interference

Das Verkleinern der Flash-Zellen bringt auch eine stärkere Kopplung der parasitären Kapazitäten zweier benachbarter Zellen mit sich. Diese Inter-Cell Interference (ICI) genannte Kopplung provoziert beim Schreiben bestimmter Datenmuster Fehler.

SLC-Flash etwa ist für ICI besonders bei der Programmierung von (1 0 1)-Mustern in horizontaler oder vertikaler Richtung anfällig. Die beiden Einsen „ziehen“ die Null tendenziell mit, sodass beim Lesen eine falsche (1 1 1)-Folge herauskommt. Bei modernerem Speicher mit vertikal gestapelten Zellenlagen (3D-Stacking) tritt ICI nicht nur in x- oder y-Richtung der Horizontalen auf, sondern zusätzlich auch in der Höhe. Die Auswirkungen horizontaler ICI lassen sich bei SLC-Flash durch Verwendung sogenannter Constraint Codes abschwächen, die keine (1 0 1)-Muster zulassen. Dieser Ansatz wirkt jedoch nicht gegen die vertikale ICI.

Fehlerursache Data Retention

Stromlos gelagerte Flash-Zellen verlieren mit der Zeit ihre Daten. Der Grund dafür ist das Elektronen-Detrapping, also das Tunneln der Ladungsträger aus der Zelle heraus, wobei die Verlustrate mit steigender absoluter Temperatur und mit zunehmender Lagerdauer exponentiell ansteigt. Auch die Abnutzung der Zellen spielt eine Rolle. Die Zeit, wie lange Daten etwa aus stromlos gelagerten SSDs noch fehlerfrei gelesen werden können, wird als Data Retention Time bezeichnet [3]; je nach Abnutzung der Zellen reicht sie von ein paar Wochen bis hin zu einigen Jahren.

Ziel fehlerkorrigierender Codes

Beim Übertragen oder Speichern von Daten treten ganz allgemein Störungen unterschiedlicher Art und Herkunft auf. Dazu gehören beispielsweise bei WLAN Interferenzen, also beispielsweise gleichzeitige Übertragungen anderer Nutzer, aber auch das unvermeidliche Rauschen der Bauteile.

Störungen lassen sich generell nicht vermeiden. Das Ziel fehlerkorrigierender Codes ist, trotzdem eine fehlerfreie Rekonstruktion der übertragenen oder gespeicherten Nachricht zu garantieren. Redundanz – das Einbauen zusätzlicher, algorithmisch errechneter Informationen – ist notwendig, um Fehler zu erkennen: mit mehr Redundanz kann man sie auch korrigieren. Bevor eine Bitfolge auf die Reise geht, ersetzt man sie deshalb durch ein längeres Codewort.

Sieht der Empfänger ein Wort, welches nicht in seinem Code-Wörterbuch steht, kam es offensichtlich zu einem Übertragungsfehler. Das Umsetzen der Daten in Codewörter heißt kodieren, der gegenteilige Vorgang beim Empfänger dekodieren. Die Tabelle auf der nächsten Seite veranschaulicht verschiedene Codes mit und ohne Redundanz.

Beim Übertragen ohne Redundanz muss der Empfänger glauben, was er bekommen hat. Er kann einen Fehler nicht erkennen, geschweige denn selbst beheben. Bei einer Übertragung mit Redundanz kann der Empfänger hingegen feststellen, ob die empfangene Sequenz gültig ist. Ein Beispiel hierfür ist unsere Sprache, welche natürliche Redundanz enthält. Weil nicht jede Buchstabenfolge Sinn ergibt, ist nicht jedes Wort ein gültiges Codewort, welches übertragen werden darf. Das ermöglicht es uns, Gesprochenes oft trotz Störgeräuschen zu verstehen.

Bemerkt der Empfänger einen Übertragungsfehler, dann muss er versuchen, das Original aus den fehlerhaft empfangenen Daten zu rekonstruieren.

Unter einem Übertragungskanal muss man sich im Übrigen kein physisches Medium wie einen Draht vorstellen. Auch die Datenspeicherung gilt als Übertragung über einen Kanal: Das Schreiben entspricht dem Senden der Daten, das Lesen dem Empfangen.

Kanalkodierung und -dekodierung

Im einfachsten Fall hängt man zusätzliche Redundanzbits an die Nachrichtenbits an. Die simpelste Idee dafür: Man sendet die Nachricht doppelt. Das Codewort hätte dann die doppelte Länge der Nachrichtenbitfolge. Tritt im ersten Teil des Codeworts ein Fehler auf, kann man die zweite, hoffentlich fehlerfreie Hälfte zur Rekonstruktion der Nachricht verwenden. Man weiß nur nie, welcher Teil korrekt übertragen wurde. Deshalb nutzt man in der Praxis komplexere Kodierungsverfahren, die eine bestimmte Anzahl von Fehlern sicher erkennen und eventuell auch korrigieren können.

Eigenschaften von Codes

Gute Codes sollen einerseits in der Lage sein, möglichst viele Fehler im Empfangswort zu erkennen und zu korrigieren. Andererseits sollen die Codewörter im Verhältnis zur kodierten Nachricht für eine effiziente Übertragung nicht zu lang sein.

Um möglichst viele Fehler erkennen und korrigieren zu können, sollten die Codewörter sich möglichst stark unterscheiden. Als Hamming-Distanz zwischen zwei Sequenzen wird die Anzahl der Stellen bezeichnet, an welchen die beiden Sequenzen unterschiedlich sind. Je größer die Distanz zwischen zwei Codewörtern ist, desto geringer ist die Gefahr, die Codewörter nach einer fehlerbehafteten Übertragung zu verwechseln. Bei geringer Distanz führen schon wenige Fehler in einem Codewort zu einem anderen zulässigen Codewort.

Fehlerkorrekturcodes benötigen Speicherplatz für die Redundanzdaten. Der zusätzliche Platzbedarf steigt mit der Anzahl der Bit pro Zelle und liegt bei QLC-Speicher bei bis zu 320 Byte pro 1024-Byte-Block.

Hamming-Code

Der Hamming-Code (siehe unten) ist eines der bekanntesten und ältesten Fehlerkorrekturverfahren. Er kodiert und dekodiert einfach und effizient.

Allerdings ist der einfache Hamming-Code nur für wenige Kombinationen aus Nutz- und Redundanzbits definiert und auf die Korrektur eines einzelnen Bitfehlers beschränkt. Daher werden diese Codes normalerweise nur in Szenarien verwendet, in denen die Wahrscheinlichkeit von mehr als einem Fehler sehr gering ist. Ein Hamming-Code mit einer Hamming-Distanz von d = 3 wie im Beispiel unten kann alternativ einen 2-Bit-Fehler erkennen. Die Länge des Beispiels beträgt 2^r-1 = 7, dieser Code benötigt r = 3 Redundanzbits.

Beispielsweise wird bei SLC-Flash mit Strukturgrößen über 40 nm häufig ein Hamming-Code mit 256 Bytes (2048 Bits) eingesetzt. Die Redundanz beträgt dann 11 Bit und die Codewortlänge n = 2047 = 2¹¹-1. In der Praxis sichert man die Daten über weitere Parity-Bits in Spalten und Zeilen ab, sodass sich insgesamt eine Redundanz von 22 bis 24 Bit ergibt. Für modernere Flash-Versionen ist der Hamming-Code aufgrund seiner eingeschränkten Korrekturfähigkeit nicht mehr geeignet.

SEC-DED-Codes

In der Praxis nutzt man häufig Verfahren, die Fehler von ein und zwei Bits gleichzeitig erkennen können und außerdem 1-Bit-Fehler korrigieren. Kommt dabei ein Hamming-Code mit einer Mindest-Distanz von d = 3 zum Einsatz, überfordert das den Dekoder; er korrigiert fälschlicherweise einen 1-Bit-Fehler statt eines 2-Bit-Fehlers, das resultierende Ergebnis stimmt nicht mit dem Original überein.

Erweiterte Hamming-Codes, auch SEC-DED (Single Error Correction, Double Error Detection) genannt, vermeiden solch unerwünschte Datenverfälschungen. Ein erweiterter Hamming-Code hat in der Regel die Länge von 2^r, die Redundanz r+1 und die Mindest-Distanz d = 4. Im Venn-Diagramm fügt man ein weiteres Paritätsbit hinzu, welches aus den Paritätsbits des einfachen Venn-Diagramms gebildet wird. Das garantiert, dass der Dekoder alle 2-Bit-Fehler detektiert und gleichzeitig alle 1-Bit-Fehler korrigiert.

Eine abgeleitete Form des erweiterten Hamming-Codes ist der Hsiao-Code, der sich sehr schlank in Hardware realisieren lässt und vor allem in sicherheitskritischen Anwendungen zum Einsatz kommt, etwa in der Automobilelektronik.

BCH-Codes

Mit zunehmender Dichte und damit abnehmender Zuverlässigkeit des Flash-Speichers stieg die Notwendigkeit, mehr als einen Bitfehler pro Block zu korrigieren. Eine Zeit lang wurden dafür sogenannte BCH-Codes verwendet, die zwischen 20 und 200 Bitfehler pro KByte korrigieren können. Der Name des Codes leitet sich aus den Namen der Entwickler R. C. Bose, D. K. Ray-Chaudhuri und A. Hocquenghem ab.

Die dafür notwendige Redundanz liegt zwischen 32 und 320 Bytes pro KByte. BCH-Codes wurden jedoch schnell von den LDPC-Codes abgelöst, die weniger Redundanz benötigen und zudem bei vielen Bitfehlern das korrekte Ergebnis schneller liefern.

LDPC-Codes

LDPC steht für Low-Density Parity-Check. Der Elektrotechniker Robert Gray Gallager hatte bereits in seiner Dissertation 1963 LDPC-Codes zur linearen Fehlerkorrektur vorgeschlagen, doch ihr Potenzial wurde erst deutlich später erkannt. Dies ist auch auf die damals noch unzureichende Rechenleistung der Computer zurückzuführen.

LDPC-Codes werden mittels eines bipartiten Graphen beschrieben und sind damit in mehreren sehr schnell durchführbaren Schritten dekodierbar. Für eine effiziente Dekodierung sollte der Graph nur wenige Verbindungen zwischen den Check Nodes und den Variable Nodes aufweisen, was man auch als „dünn besetzt“ bezeichnet und sich im Namensteil ,,Low Density“ widerspiegelt.

Die oberen roten Knoten im Beispiel auf der rechten Seite heißen Check Nodes, die unteren blauen Variable Nodes; jeder Node enthält 1 Bit. Die Dekodierung erfolgt iterativ in mehreren Schritten. Die Variable Nodes dienen als Ein- und Ausgang, sie sind über die gleiche Anzahl Graphen mit den Check Nodes verbunden, welche die Werte der eingehenden Variable Nodes aufsummieren. Die Summe modulo 2 muss immer Null ergeben; dies wird durch zusätzliche Paritätsbits garantiert.

Im Prinzip werden beim sogenannten Message Passing (auch Belief Propagation genannt) Nachrichten zwischen den Check Nodes und den Variable Nodes hin- und hergeschickt. Je weniger Fehler auftreten, desto weniger Iterationen benötigt der Decoder. Tritt kein Fehler auf, ist die Dekodierung sofort beendet.

Bei der Erklärung nehmen wir an, dass der Kanal ein Bit entweder komplett richtig überträgt oder auslöscht; in letzterem Fall erhält der Empfänger an dieser Stelle ein ungültiges Symbol X. Man spricht dann auch von einem Binary Erasure Channel.

In der Praxis liegen jedoch selten Auslöschungen vor, sondern eine ,,weichere“ Art von Zuverlässigkeit (eine Auslöschung kann als komplett unzuverlässig gesehen werden, bei der weicheren Art der Zuverlässigkeit aber gibt es eine Tendenz zu einem der beiden Werte). Somit wird angenommen, dass an den Variable Nodes kontinuierliche Werte, also die Ausgangswerte eines kontinuierlichen Kanals zur Verfügung stehen, alternativ interpretiert als Bitwerte und zugehörige Zuverlässigkeiten.

Über die Verbindungen werden diese Zuverlässigkeitswerte an die Check Nodes geschickt, welche hieraus wiederum sogenannte extrinsische Information berechnen und an die Variable Nodes zurückschicken. Die Variable Nodes berechnen basierend auf dieser extrinsischen Information (also Information, die ja von anderen Variable Nodes kommt) einen neuen Bitwert mit einer Zuverlässigkeit für jede Variable Node und schicken die Zuverlässigkeitsinformation wieder an die Check Nodes zurück. Dieser Prozess wird so lange wiederholt, bis die Bitwerte an den Variable Nodes ein gültiges Codewort ergeben.

SSD-Controller kombinieren das Message Passing häufig als Hardware- und Softwareimplementierung. Hardware kann wenige Fehler sehr schnell korrigieren, was in den meisten Fällen ausreicht. Treten ausnahmsweise viele Fehler auf, wechselt die Decodierung auf die deutlich langsamere Softwareimplementierung.

Ausblick

Die hier beschriebenen Verfahren eignen sich prinzipiell nicht nur für Flash-Speicher, sondern auch für die Signalübertragung über andere Kanäle. Doch jeder Anwendungsfall ist anders, die Entwickler wählen die jeweils passenden Codes aus.

Bei modernen SSDs kommen fast ausschließlich LDPC-Codes zum Einsatz, diese reichen auch für die kommende Generation von Flash-Zellen mit fünf Bit Speicherfähigkeit (PLC, Penta Level Cell) noch aus. Die Eignung für noch fehleranfälligeren Flash-Speicher ist jedoch noch nicht bewiesen. Unter Laborbedingungen haben Entwickler bereits Flash-Zellen mit sieben Bit Speicherfähigkeit getestet; dazu sind allerdings Temperaturen weit unter dem Gefrierpunkt notwendig. Seit einigen Jahren wird auch schon an Polar-Codes geforscht. (ll@ct.de)