DE19963683A1

DE19963683A1 - Architektur zum Decodieren von linearen Blockfehler-Korrekturcodes mit Soft Decision

Info

Publication number: DE19963683A1
Application number: DE19963683A
Authority: DE
Inventors: Lih-Jyh Weng
Original assignee: Quantum Corp
Current assignee: Quantum Corp
Priority date: 1999-01-04
Filing date: 1999-12-29
Publication date: 2000-10-05
Also published as: GB9930871D0; US6381726B1; GB2348990A; JP2000232379A; JP4486198B2

Abstract

Ein Verfahren und eine Vorrichtung zum Decodieren eines beschädigten Codewortes wird beschrieben. Die Decodierung wird unter Verwendung eines Decoders bewerkstelligt, der ein gemeinsames Zuverlässigkeitsmaß für jedes Symbol des beschädigten Codewortes verwendet und es wird ermittelt, ob ein brauchbares Ergebnis von dem ersten Decoder erhalten werden kann. Wenn ein brauchbares Ergebnis nicht erhalten werden kann, wird die Decodierung des beschädigten Codewortes mit einem zweiten Decoder durchgeführt, der spezielle Zuverlässigkeitswerte für jedes Symbol des beschädigten Codewortes verwendet.

Description

Hintergrund

Diese Erfindung betrifft Fehlerkorrekturcodeverfahren.

Fehlerkorrekturcodeverfahren werden bei digitalen Systemen verwendet, um Fehler in digitalen Daten zu korrigieren und detektieren. Derartige Verfahren werden insbesondere bei Magnetplatten verwendet, die aufgrund von Herstellungsfehlern usw. relativ hohe Fehlerraten aufweisen können. Es sind verschiedene Typen von Fehlerkorrekturverfah ren bekannt. Eine Art von Fehlerkorrekturverfahren verwendet sogenannte "Blockcodes". Ein Beispiel für einen Blockcode ist der sogenannte "Reed Solomon (RS) Code". Block codes in der Art des Reed-Solomon-Blockcodes arbeiten mit Datensymbolen. Datensym bole sind Vektoren von Binärbits von Daten. Symbole werden dadurch erzeugt, daß Bits an einer speziellen Bitposition für eine Gruppe von Worten in einen Vektor gruppiert wer den. Wenn bei einem Plattenlaufwerk Blockcodes verwendet werden, wird vor dem Auf zeichnen eines Strings von Datensymbolen auf eine Platte der String mathematisch co diert, wodurch Fehlerkorrekturcode-Symbole erzeugt werden, die an die Datensymbole angehängt werden, um Codeworte zu bilden. Diese Codeworte, das heißt Datensymbole und Fehlerkorrekturcodesymbole werden auf der Platte gespeichert. Wenn die gespei cherten Daten von der Platte wiedergewonnen bzw. gelesen werden, werden die Code worte mathematisch decodiert, um decodierte Codeworte zu bilden.

Es können mehrere Datenfehler in den Datensymbolen korrigiert werden, wenn die An zahl dieser Datenfehler nicht die maximale Fehleranzahl übersteigt, für die der Algorith mus entworfen wurde. Zur Zeit verwenden die meisten Decodierschemata eine soge nannte "harte Decodierung". Die harte Decodierung ist ein Verfahren, bei dem jedes Symbol eines beschädigten Codeworts genau das gleiche Maß von Zuverlässigkeit be sitzt wie jedes andere Symbol. Der Bequemlichkeit halber wird im allgemeinen dem Zu verlässigkeitsmaß eines jeden Symbols der Wert Eins zugeordnet. Ein zweites Verfahren, das sogenannte "Soft Decision Decoding" verwendet ein spezielles Maß der Zuverlässig keit für jedes Symbol. Jedem Symbol ist ein eigener bzw. spezieller Wert zwischen Null und Eins oder aus irgendeinem Wertebereich zugeordnet. Die mit Soft Decision Deco ding arbeitenden Algorithmen sind zwar in der Lage, mehr Fehler zu korrigieren und sind daher robuster und besitzen eine bessere Performance, haben aber die Tendenz, sehr kompliziert zu sein. Daher haben praktische Realisierungen der Soft Decision Decodie rung die Tendenz, langsam zu sein, oder, wenn ausreichend Hardware verwendet wird, um die Geschwindigkeit zu erhöhen, teuer und somit häufig nicht anwendbar zu sein.

Zusammenfassung

Gemäß einem Gesichtspunkt der vorliegenden Erfindung umfassen ein Verfahren und eine Vorrichtung zum Decodieren eines beschädigten Codewortes eine Decodierung des beschädigten Codewortes mit einem Decoder, der ein gemeinsames Zuverlässigkeits maß für jedes Symbol des Codeworts besitzt, und, eine Ermittelung, ob ein brauchbares Ergebnis von dem ersten Decoder erhalten werden kann. Wenn ein brauchbares Ergeb nis nicht erhalten werden kann, wird das beschädigte Codewort mit einem zweiten De coder decodiert, der jeweils eigene Zuverlässigkeitswerte für jedes Symbol des beschä digten Codeworts verwendet.

Einer oder mehrere der folgenden Vorteile werden erreicht. Die "harte" Decodierung kann für die meisten Fehlerereignisse verwendet werden und die langsamere "Soft-Decision" Decodierung kann für die weniger häufigen Ereignisse verwendet werden. Dies verbes sert das Gesamtverhalten. Gewünschtenfalls kann die harte Decodierung so aufgebaut werden, daß sie weniger Fehler behandelt, als ihrer Maximalzahl entspricht. Mit anderen Worten, der verwendete "harte" Decoder muß nicht vollständig oder komplett die Fehler korrektur-Möglichkeiten eines ausgewählten "harten" Decodieralgorithmus realisieren. Der "harte" Decoder muß nur die wahrscheinlichste Anzahl von Fehlern korrigieren, das heißt einen oder zwei Fehler pro Symbol, und die weniger wahrscheinliche größere Feh leranzahl für die "Soft Decision" Decodierung übrig lassen. Dadurch, daß nur ein Bruch teil der Symbolfehler durch eine vollständig "harte" Decoder-Realisierung korrigierbar ist, wird Hardware gespart und eine höhere Gesamtgeschwindigkeit erreicht, indem man die "Soft Decision" Decodierung die weniger häufigen aber höheren Fehlerzahlen korrigieren läßt.

Kurze Beschreibung der Zeichnung

In der Zeichnung zeigen:

Fig. 1 ein Blockdiagramm eines Computers einschließlich eines Speicher geräts,

Fig. 2 ein Blockdiagramm einer Architektur eines Codewort-Decodier- Schemas,

Fig. 3 ein Blockdiagramm einer Fehler-Korrektur-Einrichtung des Spei chergeräts aus Fig. 1,

Fig. 4 ein Blockdiagramm einer Architektur eines Fehler-Decodier-Sche mas und

Fig. 5 Flußdiagramme beispielhafter Verfahren zur Erzeugung von Zuver lässigkeits-Schwellenwerten für das Decodierschema aus Fig. 4.

Detaillierte Beschreibung

Gemäß Fig. 1 umfaßt ein Computersystem 10 einen Prozessor 12, einen Hauptspeicher 14 und ein Speicher-Subsystem 15, die alle über einen Computerbus 16 miteinander verbunden sind. Das Speicher-Subsystem 15 umfaßt einen Busadapter 18, einen Spei cherbus 19 und ein Speichergerät 20. Ein bevorzugtes Beispiel für das Speichergerät 20 ist eine Magnetplatte. Andere Beispiele umfassen eine optische Platte, ein Magnetband und eine Festkörper-Platte. Das Speichergerät 20 umfaßt einen Fehler-Korrektur-Codie rer 22 und eine Fehler-Decodier-Schaltung 30.

In Fig. 2 ist ein Teil des Speichersubsystems 15 einschließlich des Fehlerkorrekturcode- Codierers 22 gezeigt, dem während eines Plattenschreibvorganges Eingangsdaten vom Busadapter 18 zugeführt werden und der Fehlerkorrekturcode-Symbole erzeugt, die mit Datensymbolen verbunden oder diesen zugeordnet und einer Plattenschnittstelle 23 für eine Speicherung auf dem Plattenlaufwerk 26 (Fig. 1) zugeführt werden. Während eines Lesevorganges von der Platte werden die Datensymbole und Prüfsymbole von dem Speichergerät 20 wieder gewonnen. Die Datensymbole werden der Plattenschnittstelle 23 und der Fehlerkorrektur-Decodierschaltung 30 zugeführt. Die Fehlerkorrektur Deco dierschaltung 30 erzeugt einen Satz von Fehlerkorrekturcodesymbolen aus dem wieder gewonnenen Datensymbolen. Die erzeugten Symbole werden mit den Fehlerkorrektur Prüfsymbolen verglichen, die vom Speichergerät 20 wiedergewonnen worden sind. Die Fehlerdecodierschaltung 30 korrigiert solche Fehler unter der Voraussetzung, daß sie die Fehlerkorrekturfähigkeit des Fehlerdecoders 30 nicht übersteigen. Die Fehlerdecodier schaltung 30 umfaßt einen "harten" Decoder und einen "Soft Decision" Decoder, um ein beschädigtes Wort zu decodieren und eine Entscheidungslogik, die entscheidet, ob der Decoder die "harte" oder "Soft Decision" Decodierung verwenden soll.

Gemäß Fig. 3 umfaßt ein Decoder 30 für lineare Block-Fehlerkorrektur-Codes einen "harten" Decoder 32, der entsprechend irgendeinem aus einer Reihe von allgemein be kannten "harten" Decodieralgorithmen arbeitet. Der "harte" Decoder 32 realisiert ein schnelles, "hartes" Decodierverfahren, um das Hauptverfahren zum Decodieren von be schädigten Codewörtern c(j) zu liefern, die dem Decoder 30 zugeführt werden. Der De coder 30 umfaßt auch die Entscheidungslogik 33. Die Entscheidungslogik 33 prüft die Ausgangssignale des "harten" Decoders 32 um zu ermitteln, ob das Ausgangssignal vom "harten" Decoder als Ausgangssignal des Decoders 30 akzeptiert werden kann. Wenn das Ausgangssignal vom "harten" Decoder nicht akzeptiert werden kann, ruft die Ent scheidungsschaltung 33 ein "Soft Decision" Decodierverfahren auf, um das decodierte Ausgangssignal des Decoders 30 zu liefern.

Die beschädigten Wörter c(j) werden dem "harten" Decoder 32 zugeführt. Aus den be schädigten Wörtern c(j) erzeugt der "harte" Decoder 32 ein Fehlermuster von insgesamt e von null verschiedenen Symbolen, die als b(1), b(2),.., b(e) dargestellt werden, wobei e < d/2 ist. Das Fehlermuster b(1), b(2), . . . b(e) wird einer Fehlermuster-Zuverlässigkeits- Berechnungsschaltung 34 zugeführt. Eine Schaltung 36 speichert die Anzahl der Fehler in dem beschädigten Wort, wie sie von dem "harten" Decoder 32 ermittelt worden ist.

Den beschädigten Codeworten c(j) sind entsprechende Zuverlässigkeiten r(j) zugeordnet, die von einem Kanalprozessor (nicht dargestellt) erzeugt oder geliefert werden. Die Werte dieser Zuverlässigkeitsmaße werden zusammen mit den Fehlermustersymbolen b(j) einer Fehlermuster-Zuverlässigkeits-Schaltung 34 zugeführt. Die Fehlermuster-Zu verlässigkeits-Schaltung 34 registriert die Zuverlässigkeit der Fehlermustersymbole b(j) als

S = s(1) + s(2) + . . . + s(e),

wobei s(j) die Zuverlässigkeit für die b(j) zugeordnete Stelle ist.

Die Entscheidungslogik 33 umfaßt eine Schaltung 36, die die Anzahl von Fehlern (das heißt die Anzahl von b(j)-Termen) zählt, die im Ausgangssignal vom "harten" Decoder 32 vorhanden sind. Basierend auf der Anzahl der gezählten Fehler selektiert eine Selekti onsschaltung 40 einen aus einer Vielzahl von Zuverlässigkeits-Schwellenwerten. Die Zu verlässigkeits-Schwellenwerte werden von einem Zuverlässigkeits-Schwellenwert-Pro zessor 38 ermittelt. Der Zuverlässigkeits-Schwellenwert-Prozessor 38 arbeitet auf der Basis der Zuverlässigkeits-Eingangswerte r(j), um einen Satz von Ausgangs-Schwellen werten T(d - 1), T(d - 2), . . . T(d_max - 1) und T(d - e_max) entsprechend dem Wert e(max) zu erzeugen. Somit werden alle Schwellenwerte basierend auf der Anzahl von Fehlern be rechnet oder ermittelt, die in einem beschädigten Codewort auftreten können. Diese Schwellenwerte werden für jedes beschädigte Codewort vom Selektor 40 ausgewählt.

Gewünschtenfalls kann der maximale Wert von e, der durch e_max bezeichnet und vom "harten" Decoder geliefert wird, so gewählt werden, daß er wesentlich kleiner ist als (d - 1)/2. In anderen Worten, der realisierte "harte" Decoder muß nicht voll oder komplett die Fehlerkorrektur-Möglichkeit eines ausgewählten "harten" Decodieralgorithmus reali sieren. Es ist lediglich erforderlich, daß der "harte" Decoder die wahrscheinlichste Anzahl von Fehlern, das heißt einen oder zwei pro Symbol korrigiert und die weniger wahr scheinliche und größere Anzahl dem "Soft Decision" Decoder überläßt. Dadurch, daß nur ein Bruchteil der Symbolfehler korrigiert werden, die von einer vollständigen "harten" De codiererrealisierung korrigierbar wären, wird Hardware gespart und eine höhere Ge samtgeschwindigkeit dadurch erreicht, daß man den "Soft Decision" Decoder die weniger häufigen aber höheren Fehleranzahlen korrigieren läßt. In dem Fall, daß der "harte" De coder 32 nicht in der Lage ist, ein Fehlermuster zu liefern, wird das Zuverlässigkeitsmaß S willkürlich auf eine sehr große Zahl gesetzt. Dies stellt sicher, daß der "Soft Decision" Decodieralgorithmus aufgerufen wird.

Der ausgewählte Zuverlässigkeits-Schwellenwert 40 wird bei 42 mit den Fehlermuster Zuverlässigkeits-Ausgangssignalen S verglichen, um zu ermitteln, ob das Ausgangs signal des "harten" Decoders 32 als Ausgangssignal des Decoders 30 akzeptiert werden kann, oder ob ein "Soft Decision" Decodierprozeß 44 aufgerufen werden soll, um ein Ausgangssignal vom Decoder 30 zu liefern. Wenn das Zuverlässigkeitsmaß S kleiner oder gleich dem ausgewählten Schwellenwert (T) ist, wird das "harte" Decodiermuster als endgültiges Decodiermuster akzeptiert. Andernfalls wird der mehr Zeit in Anspruch neh mende oder komplexere "Soft Decision" Decodieralgorithmus aufgerufen, um das end gültige decodierte Fehlermuster zu erzeugen.

Es ist wichtig, daß die Schwellenwerte in der Weise berechnet werden, daß dann, wenn S kleiner oder gleich dem Schwellenwert ist, das Ausgangssignal des "harten" Decoders definitiv das gleiche ist wie das Ausgangssignal der "Soft Decision" Decodierung. Auf der anderen Seite kann dann, wenn S größer ist als der Schwellenwert, das Ausgangsfeh lermuster des "harten" Decoders gleich dem Ausgangssignal der "Soft Decision" Decodie rung oder von letzterem verschieden sein. Es kann jeder Algorithmus zur Erzeugung der artiger Schwellenwerte verwendet werden, um die Schwellenwerte zu berechnen; im fol genden werden aber zwei Beispiele angegeben.

Unter Bezugnahme auf Fig. 4 wird ein Verfahren 60 zur Erzeugung von Schwellenwer ten erläutert. Das Verfahren 60 (das als Vollspeicherverfahren (Full Storage Process) be zeichnet wird) weist bei 62 jedem der Zuverlässigkeitswerte von r(j) Speicherelemente zu. Anfangs werden alle Werte m(j) auf 1, das heißt den höchsten Zuverlässigkeitswert ge setzt. Das Vollspeicherverfahren 60 ordnet bei 64 die Zuverlässigkeitswerte nach ab nehmendem Zuverlässigkeitswert dadurch, daß es nach einer Zuverlässigkeit sucht, die kleiner ist als der anfangs gespeicherte Wert in den Speicherelementen. Wenn ein sol cher Wert gefunden wird, werden die Zuverlässigkeiten als die am wenigsten zuverlässi gen Maße von d - 1 Symbolen der Reihe nach sortiert, wobei m(1) das am wenigsten zu verlässige Maß speichert.

Für jedes neue r(j),
wenn r(j) < m(d - 1) führe nichts aus;
andernfalls vergleiche r(j) mit m(d - 1), m(d - 2), . . .,
bis r(j) < m(k) und r(j) < m(k - 1)
dann setze m(d - 1) = m(d - 2)
m(d - 2) = m(d - 3)
m(k+1) = m(k)
m(k) = r(j).

Nachdem die Werte der Reihe nach gespeichert worden sind, werden die Schwellen werte bei 66 dadurch bestimmt, daß einfach die Werte in jedem der Speicherelemente m(1) - m(k) für k = d - emax, . . ., d - 2, d - 1 summiert werden.

Dieses Verfahren erzeugt brauchbare Schwellenwerte, weil der "harte" Decoder 32 ein Fehlermuster mit einer Anzahl e von Fehlern und ein Zuverlässigkeitsmaß mit dem Wert S erzeugt. Ein anderes Fehlermuster enthält, wie unten gezeigt wird, wenigstens (d - e) von Null verschiedene Symbole. Jedes der d - e von Null verschiedenen Symbolen hat ein Zuverlässigkeitsmaß von wenigstens T(d - e). Mit einem Zuverlässigkeitsmaß S das klei ner oder gleich dem Schwellenwert ist, wäre es unmöglich, ein Fehlermuster mit einem Zuverlässigkeitsmaß kleiner als S zu finden. Daher ist dann, wenn S kleiner oder gleich dem Schwellenwert ist, das Ausgangssignal des "harten" Decoders 32 das gleiche wie das bestmögliche Ausgangssignal der "Soft Decision" Decodierung und somit ist es in Ordnung, das Ausgangssignal vom "harten" Decoder als das Ausgangssignal der Schal tung 30 zu wählen.

Gemäß Fig. 5 umfaßt ein anderes Verfahren 70 zur Ermittelung eines Zuverlässigkeits- Schwellenwertes (partielles Speicherverfahren) die bei 72 erfolgende Zuordnung einer partiellen Speicherung zum Speichern nur eines Teils der am wenigsten zuverlässigen Symbole. Diese Vorgehensweise verwendet nur k Speicherelemente, um die k Werte für die geringste Zuverlässigkeit zu speichern, die irgendeinen Wert zwischen 1 und d - 2 ha ben können. Die Schwellenwerte werden bei 74 bestimmt durch:

T(j) = m(1) + m(2) + . . . + m(j)

für alle j ≦ K und werden bei 76 für j < K bestimmt durch

T(j) = m(1) + m(2) + . . . + m(K - 1) + (j - K + 1).m(K).

Mit anderen Worten, die Werte von m(K + 1), m(K + 2), . . . m(d - 1) des Vollspeicherverfah rens 60 aus Fig. 4 werden bei diesem Teilspeicherverfahren 70 alle durch den gleichen Wert m(K) ersetzt. Die Schwellenwerte dieses partiellen Speicherverfahrens 70 sind identisch mit denen des Vollspeicherverfahrens 60 für Schwellenwerte von T(j), bei de nen j ≧ K ist. Für j < K sind bei diesem Teilspeicherverfahren 70 die Schwellenwerte klei ner als die, die beim Vollspeicherverfahren 60 gefunden werden. Folglich werden mehr Fehlermuster des "harten" Decoders zurückgewiesen, wenn dieses Teilspeicherverfahren 70 verwendet wird. Der Wert von K wird jedoch richtig gewählt. Die Werte von m, K und j sollten sehr nahe bei den Werten von m(K) liegen. In diesem Fall sind die Werte von al len Schwellenwerten in diesem Teilspeicherverfahren 70 praktisch die gleichen, wie die, die sich beim Vollspeicherverfahren 60 nach Fig. 4 ergeben. Dieses Teilspeicherverfah ren 70 weist jedoch weniger Vergleichs- und Einfüge-Operationen insbesondere dann auf, wenn der Wert von K klein ist.

Bei der "harten" Decodierung hat jedes Symbol des beschädigten Codeworts exakt das gleiche Zuverlässigkeitsmaß. Der Bequemlichkeit halber wird dem Zuverlässigkeitsmaß eines jeden Symbols der Wert 1 zugewiesen. Bei der "Soft Decision" Decodierung wird jedoch dem Zuverlässigkeitsmaß für jedes Symbol ein gesonderter Wert, beispielsweise zwischen 0 und 1 oder allgemein gesprochen aus irgendeinem Wertebereich zugewie sen, wie dies oben beschrieben wurde. Die "harte" Decodierung ist daher ein Sonderfall des allgemeineren "Soft Decision" Decodierverfahrens. Um verwendbar zu sein muß bei der "Soft Decision" Decodierung ein Zuverlässigkeitsmaß die Charakteristik haben, daß die Zuverlässigkeit eines Satzes von Symbolen aus den Zuverlässigkeiten der individu ellen Symbole im Satz erhalten werden kann. Daher können dann, wenn R das Zuverläs sigkeitsmaß des Satzes von Symbolen {a(1), a(2), . . . a(e)} und r(j) das Zuverlässigkeits maß von a(j) ist, die beiden einfachen Relationen erzielt werden.

R = r(1) + r(2) + . . . r(e), (1)

oder

R' = r'(1)*r'(2)* . . . *r'(e) (2).

Diese beiden Relationen stehen durch eine logarithmische Operation in Beziehung. So wie sie hier verwendet wird, wird Gleichung (1) verwendet, um das Zuverlässigkeitsmaß zu berechnen. Dieses Zuverlässigkeitsmaß arbeitet auf der Basis von Blockcodes. Ein Blockcode ist durch drei Parameter (n, k, d) charakterisiert, wobei n die Gesamtzahl von Symbolen pro Codewort, k die Zahl von Informationssymbolen pro Codewort und d die minimale Hamming-Distanz zwischen zwei beliebigen beschädigten Codeworten ist. Ein geeigneter "harter" Decodieralgorithmus kann bis zu einschließlich (d - 1)/2 Symbolfehler in einem beschädigten Codewort korrigieren.

Das hier beschriebene Verfahren kann auf alle linearen Blockcodes (n, k, d) angewandt werden, die wenigstens einen bekannten "harten" Decodieralgorithmus besitzen, der in der Lage ist, ein einmaliges Fehlermuster zu erzeugen, das (d - 1)/2 oder weniger Sym bolfehler enthält. Ein linearer Blockcode hat die Eigenschaft, daß die Addition von zwei Codewörtern zu einem weiteren Codewort führt. Die Addition des Codeworts (a(1), a(2), . . ., a(n) und des Codeworts (b(1), b(2), . . ., b(n) ist definiert als (a(1) + b(1), a(2) + b(2), . . ., a(n) + b(n), wobei das +-Zeichen die Feldaddition für das zugrundeliegende Feld bezeichnet, über dem die Codesymbole a(j) und b(j) definiert sind.

Es sollten einige Beispiele genügen. Die folgenden zwei Beispiele dienen dem Zweck, die Wirkung der "harten" Decodierung und der "Soft Decision" Decodierung zu erläutern.

Beispiel 1

Ein Reed-Solomon-(7, 3, 5)-Codewort sei

(001, 011, 100, 110, 110, 001, 100),

und das beschädigte Codewort sei

(000, 011, 101, 100, 110, 001, 100),

und das Zuverlässigkeitsmaß sei

(0,1, 0,3, 0,2, 0,3, 0,5, 0,9, 0,9).

Im vorliegenden Zusammenhang ist die Notation für das n-Tupel (c(1), c(2), . . ., c(n) ein Codewort, ein beschädigtes Codewort oder ein Fehlermuster mit Symbolen c(j), die durch Kommata getrennt sind; ein n-Tupel (r(1), r(2), . . ., r(n) ist das Zuverlässigkeitsmaß, wobei r(j) das Zuverlässigkeitsmaß für c(j) ist. C(j) ist ein Symbol, das m Binärbits (im Beispiel 1 gilt m = 3) enthält und r(j) ist eine reelle Zahl. In diesem Beispiel ist 0,0 das am wenigsten zuverlässige Maß für ein Symbol und 1, 1 das zuverlässigste Maß.

Der Vergleich, das heißt die EXKLUSIV-ODER-Verarbeitung des Codeworts und des be schädigten Codeworts Symbol für Symbol erzeugt das Fehlermuster

(001, 000, 001, 010, 000, 000, 000).

Bei diesem Fehlermuster bedeutet ein nur aus Nullen bestehendes Symbol, daß das spezielle Symbol korrekt ist. Ein von Null abweichendes Symbol bezeichnet den Fehler wert dieses Symbols. Daher sind bei dem obigen Fehlermuster drei Fehler vorhanden.

Die Fehlerwerte und ihre jeweiligen Zuverlässigkeitsmaße sind: a(1) = 001, r(1) = 0,1; a(2) = 001, r(2) = 0,2; a(3) = 010, r(3) = 0,3. Unter Verwendung von Gleichung 1 ergibt sich R = 0,1 + 0,2 + 0,3 = 0,6. Daher ist das Zuverlässigkeitsmaß dieses Fehlermusters gleich 0,6.

Ein guter "Soft Decision" Decodieralgorithmus sollte dieses gleiche Fehlermuster an sei nem Ausgang erzeugen. Da es sich hier um einen Code mit einer minimalen Distanz von 5 handelt, ist die "harte" Decodierung in der Lage, zwei oder weniger Fehler zu korri gieren. Wenn ein "harte' Decodieralgorithmus auf das obige beschädigte Codewort an gewendet wird, ist das Ausgangsfehlermuster des "harten" Decoders (000, 011, 000, 000, 110, 000, 000) mit a'(1) = 011, r'(1) = 0,3; a'(2) = 110, r'(2) = 0,5. Gemäß Gleichung 1 wird die Zuverlässigkeit dieses "harten" Fehlermusters wiederum gegeben durch R' = 0,3 + 0,5 = 0,8 < 0,6 = R. Dies legt nahe, daß das vom "Soft Decision" Algorithmus gelieferte Fehlermuster eine höhere Wahrscheinlichkeit besitzt, das richtige Fehlermuster zu sein. Daher sollte das Fehlermuster, das vom "harten" Decoder geliefert wird, zurückgewiesen bzw. verworfen werden.

Das Vollspeicherverfahren 60 erzeugt Schwellenwerte in folgender Weise: Wenn der "harte" Decoder 32 ein Fehlermuster mit e Fehlern und einem Zuverlässigkeitsmaß S er zeugt, enthält ein anderes Fehlermuster, wie unten gezeigt, wenigstens (d - e) nicht nur aus Nullen bestehende Symbole. Jedes Muster mit (d - e) nicht nur aus Nullen bestehen den Symbolen hat ein Zuverlässigkeitsmaß von wenigstens T(d - e). Mit S ≦ T[d - e] ist es unmöglich, ein Fehlermuster mit einem Zuverlässigkeitsmaß kleiner als S zu finden. Da her ist dann, wenn S ≦ T[d - e] gilt, das Ausgangssignal des "harten" Decoders das gleiche wie das "beste" Ausgangssignal der "Soft Decision" Decodierung.

Im Beispiel 1 werden daher d = 5 und die Zuverlässigkeitsmaße gegeben durch:

(0,1, 0,3, 0,2, 0,3, 0,5, 0,9, 0,9).

Daher sind m[1] = 0,1, m[2] = 0,2, m[3] = 0,3 und m[4] = 0,3 die d - 1 oder 4 am wenigsten zuverlässigen Maße, die der Reihe nach gespeichert sind. Dann sind die Schwellen werte:

T[d - 1] = T[4] = m[1] + m[2] + m[3] + m[4] = 0,9

T[d - 2] = T[3] = m[1] + m[2] + m[3] = 0,6.

Wenn der "harte" Decoder das Fehlermuster (000, 011, 000, 000, 110, 000, 000) mit a'[1] = 011, r'[1] = 0,3; a'[2] = 110, r'[2] = 0,5 erzeugt und wenn gilt e = 2, dann wird die Zu verlässigkeit dieses Fehlermusters gegeben durch R' = 0,3 + 0,5 = 0,8 < T[d - e] = T[d - 2] = 0,6. Folglich sollte dieses decodierte Fehlermuster nicht sofort akzeptiert werden. Es be steht eine Chance, daß der Ausgang der "Soft Decision" Decodierung ein Fehlermuster mit einem kleineren Zuverlässigkeitsmaß produziert.

Beispiel 2

Das ursprüngliche Codewort sei das gleiche wie das oben im Beispiel 1 gegebene. Das Codewort sei jedoch jetzt so beschädigt, daß es gleich (001, 011, 100, 001, 110, 001, 100) mit dem Zuverlässigkeitsmaß (0,7, 0,8, 0,7, 0,9, 0,6, 0,6, 0,5) ist. Die "Soft Decision" Decodierung sollte das Fehlermuster (000, 000, 000, 111, 000, 000, 000) mit a(1) = 111 und r(1) = 0,9 erzeugen. Dies ist auch das Fehlermuster, das durch die "harte" Decodie rung erhalten wird. In diesem Fall sollte das Ausgangssignal des "harten" Decoders ohne die Notwendigkeit akzeptiert werden, zu einer "Soft Decision" Decodierung überzugehen. Aus den beiden obigen Beispielen kann man entnehmen, daß das Ergebnis einer "har ten" Decodierung identisch mit dem Ergebnis der "Soft Decision" Decodierung sein kann.

Dadurch, daß man wie oben erläutert, das einfache Kriterium aufstellt, daß ermittelt wird, ob das Ergebnis einer Ausgabe der "harten" Decodierung identisch mit dem Ergebnis ei ner Ausgabe mit "Soft Decision" Decodierung ist, kann dieses Kriterium verwendet wer den, um zu entscheiden, ob das komplexere und zeitraubende Verfahren der "Soft Deci sion" Decodierung ausgelöst werden soll oder nicht. In ähnlicher Weise liefert das Voll speicherverfahren 60 einen Schwellenwert in diesem Fall. Das Zuverlässigkeitsmaß des beschädigten Codeworts ist (0,7, 0,8, 0,7, 0,9, 0,6, 0,6, 0,5) wie oben dargestellt. Das Ausgangssignal der "harten" Decodierung liefert das Fehlermuster (000, 000, 000, 111, 000, 000, 000) mit a'(1) = 111, r'(1) = 0,9 und e = 1. Die m(j) sind m(1) = 0,5, m(2) = 0,6, m(3) = 0,6, m(4) = 0,7 und die Schwellenwerte werden gegeben durch:

T(d - 1) = m(1) + m(2) + m(3) + m(4) = 2,4

T(d - 2) = m(1) + m(2) + m(3) = 1,7.

Das "hart" decodierte Fehlermuster enthält nur einen Fehler, das heißt es gilt e = 1. Da her ist R' = r(1) = 0,9. Dieser Wert ist kleiner als T(d - e) = D(d - 1) = 2,4. Daher ist das "hart" decodierte Fehlermuster das gleiche als das beste Ausgangssignal der "Soft Decision" Decodierung. Folglich kann dieses Ausgangssignal als endgültiges Ausgangssignal ak zeptiert werden und es besteht keine Notwendigkeit, überhaupt zur "Soft Decision" Deco dierung überzugehen.

Da der Schwellenwert T(k) größer ist als T(k - 1) für alle k und da das Zuverlässigkeitsmaß von e decodierten "harten" Fehlern im Vergleich steht zu T(d - e) ist die Wahrscheinlich keit, daß ein Fehlermuster mit geringerem Gewicht den Schwellenwert übersteigt, we sentlich kleiner als die, daß dies durch das Fehlermuster mit dem höheren Gewicht ge schieht. Es sei auch darauf hingewiesen, daß das Zuverlässigkeitsmaß eines Fehlermu sters mit hohem Gewicht häufig größer ist als das eines Fehlermusters mit geringem Ge wicht. Dies erhöht weiterhin die Wahrscheinlichkeit, daß ein "hart" decodiertes Fehlermu ster mit niedrigem Gewicht identisch mit dem Fehlermuster der "Soft Decision" Decodie rung ist.

Das Ausgangssignal bzw. Ergebnis eines "harten" Decodieralgorithmus für einen (n, k, d)-Code erzeugt dann, wenn es erfolgreich ist, ein Fehlermuster mit e nicht nur aus Nul len bestehenden Symbolen, wobei e < d/2 ist. Wie unten gezeigt wird, hat jedes andere Fehlermuster wenigstens d-e nicht nur aus Nullen bestehende Symbole. Diese Eigen schaft wird verwendet, um die Basis für die Ermittelung zu bilden, ob ein "hart" decodier tes Fehlermuster die Chance hat, mit einem durch "Soft Decision" Decodierung erzeugten identisch zu sein oder nicht. Es ist wichtig, daß die Akzeptanzkriterien in einer Richtung fehlerhaft sein können. In anderen Worten, muß das Fehlermuster dann, wenn ein Krite rium das "hart" decodierte Fehlermuster akzeptiert, identisch mit dem Ausgangssignal ei ner "Soft Decision" Decodierung sein; andererseits kann dann, wenn das Kriterium ein "hart" decodiertes Fehlermuster zurückweist, das Fehlermuster dennoch mit dem Aus gangssignal der "Soft Decision" Decodierung identisch sein (die Strafe ist in diesem Fall der Durchsatz aber nicht die Performance). Ein gutes Kriterium sollte möglichst wenig Ausgangssignale des "harten" Decoders zurückweisen, wenn dieses Ausgangssignal mit dem Ausgangssignal des "Soft Decision" Decoders identisch ist.

Diese Architektur kann mit einem Fehler-und-Lösch-Decodieralgorithmus (error-and-era sure) verwendet werden. Ein Fehler-und-Lösch-Decodieralgorithmus klassifiziert jedes der Symbole eines beschädigten Codeworts in eine von zwei Klassen: eine Klasse, die als Löschungen bezeichnet wird, umfaßt Symbole mit geringerer Zuverlässigkeit und die andere Klasse enthält nicht gelöschte Symbole. Es gibt anderer Fehler-und-Lösch-Deco dieralgorithmen, die geringfügig komplexer sind als die nur Fehler betreffende "harte" De codierung. Das Vollspeicherverfahren 60 aus Fig. 4 kann die "harte" Decodierung ver wenden, um ein beschädigtes Codewort zu decodieren, das Löschungen enthält.

Die Decodierung weist jedem Nichtlöschungssymbol einen Zuverlässigkeitswert von 1 und jedem Löschungssymbol einen Zuverlässigkeitswert von 0,5 zu. Für "e_erasure" Lö schungssymbole im beschädigten Codewort gilt m[1] = 0,5, m[2] = 0,5, . . ., m[e_erasure] = 0,5, m[j] = 1 für j < e_erasure. Die Schwellenwerte sind dann gegeben durch

T[j] = 0,5*j

für j ≦ e_erasure, und

T[j] = 0,5*e_erasure + (j - e_erasure) = j - 0,5*e_erasure

für j < e_erasure.

Das Verfahren verwendet den "harten" Decoder 32, um ein Fehlermuster mit "e_hard" Fehlern zu erhalten und akzeptiert das Ausgangssignal des "harten" Decoders 32 als das endgültig decodierte Ausgangssignal des Decoders 30 wenn die für das Fehlermuster berechnete Zuverlässigkeit gleich oder kleiner ist als T[d - e_hard]. Andernfalls wird der Fehler-und-Lösch-Algorithmus aufgerufen, um das endgültige decodierte Codewort zu erhalten.

Es sei darauf hingewiesen, daß die Schwellenwerte T[j] für jeden Wert von e_erasure be rechnet werden können. Daher ist es nicht erforderlich, die Zuverlässigkeitsinformation für jedes Symbol zu verarbeiten. Bei dem "hart" decodierten Ausgangssignal wird die Zu verlässigkeit des Fehlermusters gegeben durch:

0,5*e 1 + (e_hard - e_1) = e_hard - 0,5*e_1,

wobei e_1 die Anzahl von erasure- bzw. Lösch-Symbolen in dem decodierten Fehlermu ster ist. Ein weiterer Punkt, der von Bedeutung sein kann, ist, daß jedes der erasure- Symbole dem "hart" decodierten so zugeführt werden kann wie es ist, oder es kann durch irgendeinen festen Wert ersetzt werden (beispielsweise durch das nur aus Nullen beste hende Symbol).

Es besteht eine Gewichtungsrelation zwischen Fehlermustern in linearen Blockcodes. Für einen linearen (n, k, d)-Blockcode existiert eine n X (n - k)-Paritätsmatrix H derart, daß gilt:

H*C ~ = 0,

wobei C~ die Transponierte eines 1 × n-Codeworts C ist. Nimmt man an, daß ein be schädigtes Codewort C' = C + E ist, wobei E ein Fehlermuster ist, so wird ein "harte" De codieralgorithmus E wiederherstellen, wenn das Hamming-Gewicht von E kleiner oder gleich (d - 1)/2 ist. (Das Hamming-Gewicht eines n-Tupels ist die Anzahl von nicht nur aus Nullen bestehenden Elementen in dem n-Tupel.) Ein "harter" Decodieralgorithmus be ginnt häufig mit der Berechnung eines Fehlersyndroms "Y" oder einer äquivalenten Be rechnung. Für einen Wert von Y gleich Null bedeutet dies, daß kein Fehler vorhanden ist. Für einen Wert von Y der nicht gleich Null ist, bedeutet dies einen Fehler und eine zu sätzliche Verarbeitung zur Korrektur des Fehlers.

Y = H*(C°)~

Durch eine geradlinige Expansion ist jedoch Y gegeben durch:

Y = H*(C~ + E~) = H*E~ Gleichung 3

Für jedes Fehlermuster E gibt es einen einzigen Wert für Y. Es gibt jedoch q^k Fehlermu ster, die den gleichen Wert von Y besitzen. Dies kann man der Gleichung 3 dadurch ent nehmen, daß irgendeines der q^k Codewörter als C angenommen wird. Für einen gegebe nen Wert von Y [ein (n - k)-Tupel] erzeugt ein "harter" Decodieralgorithmus ein n-Tupel mit (d - 1)/2 oder weniger nicht nur aus Nullen bestehenden Symbolen als das decodierte Fehlermuster.

Ein idealer "Soft Decision" Decodieralgorithmus liefert ein Fehlermuster E soft, das die Gleichung

H*E_soft~ = Y

erfüllt, und das Zuverlässigkeitsmaß von E_soft ist das kleinste aus allen der Fehlermu ster E, die die Gleichung

H*E~ = Y

erfüllen.

Wenn die "harte" Decodierung ein Fehlermuster E_hard mit e ≦ (d-1)12 Symbolfehlern er gibt, wird ein anderes Fehlermuster die Form E-hard + C besitzen, wobei C ein Codewort ist. Da der minimale Abstand des Codes d ist, enthält C wenigstens d' ≧ d nicht nur aus Nullen bestehende Symbole. Dies ist deswegen der Fall, weil das nur aus Nullen beste hende n-Tupel ein Codewort eines linearen (n, k, d)-Codes ist. Daher kann das Fehler muster ein Gewicht irgendwo von (d' - e) bis (d' + e) nicht nur aus Nullen bestehenden Symbolen haben. Wenn sich die nicht nur aus Nullen bestehenden Symbole von E_hard nicht mit irgendeinem der nicht nur aus Nullen bestehenden Symbole von C überlappen, hat (E_hard + C) (d' + e) nicht nur aus Nullen bestehende Symbole. Wenn die nicht nur aus Nullen bestehenden Symbole von E_hard von einer Auswahl von e nicht nur aus Nullen bestehenden Sub-Sätzen von C kommen, dann sind die nicht nur aus Nullen be stehenden Elemente von (E-hard + C) (d' - e). Der kleinste Wert von (d' - e) ist (d - e). Daher enthält jedes andere Fehlermuster wenigstens (d - e) nicht nur aus Nullen beste hende Symbole.

Andere Ausführungsformen

Es sei darauf hingewiesen, daß zwar die Erfindung in Verbindung mit ihrer detaillierten Beschreibung erläutert wurde, daß aber die vorausgehende Beschreibung nur zur Dar stellung dient und den Rahmen der Erfindung nicht einschränkt, der durch den Umfang der beigefügten Ansprüche definiert wird. Weitere Gesichtspunkte, Vorteile und Modifika tionen liegen im Umfang der folgenden Ansprüche.

Claims

1. Ein Verfahren zum Decodieren eines beschädigten Codeworts umfaßt folgende Schritte:
Decodieren des beschädigten Codeworts mit einem Decoder, der ein gemeinsames Zuverlässigkeitsmaß für jedes Symbol des beschädigten Codeworts besitzt,
Ermitteln, ob ein brauchbares Ergebnis vom ersten Decoder erhalten werden kann, und, wenn nicht
Decodieren des beschädigten Codeworts mit einem zweiten Decoder, der jeweils spezielle Zuverlässigkeitswerte für jedes Symbol des beschädigten Codeworts ver wendet.

2. Verfahren nach Anspruch 1, bei dem die Ermittelung weiterhin das Berechnen eines Zuverlässigkeits-Schwellenwertes umfaßt, der einem Fehler in dem beschädigten Codewort entspricht.

3. Verfahren nach Anspruch 2, bei dem die Ermittelung weiterhin
das Ermitteln einer zusammengesetzten Zuverlässigkeit der ersten Decodierung umfaßt sowie
das Vergleichen der zusammengesetzten Zuverlässigkeit der ersten Decodierung mit dem Zuverlässigkeits-Schwellenwert zur Ermittelung, ob ein brauchbares Ergeb nis aus der ersten Decodierung erzielt werden kann.

4. Verfahren nach Anspruch 1, bei dem die Ermittelung weiterhin die Ermittelung eines Satzes von Zuverlässigkeits-Schwellenwerten umfaßt.

5. Verfahren nach Anspruch 4, bei dem die Ermittelung weiterhin die Ermittelung einer zusammengesetzten Zuverlässigkeit der ersten Decodierung umfaßt.

6. Verfahren nach Anspruch 5, bei dem die Ermittelung folgende Schritte umfaßt:
Ermitteln der Anzahl der Fehler aus dem beschädigten Codewort,
Auswahl eines Fehlerschwellenwertes auf der Basis der Anzahl von Fehlern, und
Vergleichen der zusammengesetzten Zuverlässigkeit mit der Schwellenwert-Zuver lässigkeit um zu ermitteln, ob die erste Decodierung ein brauchbares Ergebnis aus der Decodierung des beschädigten Codewortes liefern kann.

7. Verfahren nach Anspruch 1, bei dem die Decodierung, die ein gemeinsames Maß verwendet, eine "harte" Decodierung ist.

8. Verfahren nach Anspruch 1, bei dem die Decodierung, die jeweils spezielle Werte verwendet, eine "Soft Decision" Decodierung ist.

9. Verfahren nach Anspruch 1, bei dem die Decodierung, die spezielle Werte verwen det, eine Fehler-und-Lösch-Decodierung ist.

10. Verfahren nach Anspruch 1, bei dem das beschädigte Codewort von einem linearen Blockcode erzeugt wird.

11. Verfahren nach Anspruch 1, bei dem dann, wenn die Ermittelung feststellt, daß die Decodierung mit dem Decoder, der ein gemeinsames Zuverlässigkeitsmaß verwen det, ein brauchbares Ergebnis liefert, das Ergebnis der Decodierung mit dem De coder, der das gemeinsame Zuverlässigkeitsmaß verwendet, als Decodierung des beschädigten Codeworts verwendet wird.

12. System zum Decodieren eines beschädigten Worts für einen linearen Block-Fehler-Korrekturcode, das folgende Bestandteile umfaßt:
einen "harten" Decodierer, der ein gemeinsames Zuverlässigkeitsmaß für jedes Symbol eines beschädigten Codewortes besitzt,
eine Logik, die ermittelt, ob ein brauchbares Ergebnis von dem "harten" Decodierer erhalten werden kann, und
einen "Soft Decision" Decoder, der spezielle Zuverlässigkeitswerte für jedes Symbol des beschädigten Codewortes verwendet.

13. System nach Anspruch 12, bei dem die Logik, die die Ermittelung durchführt, weiter hin einen Prozessor zum Berechnen eines Zuverlässigkeits-Schwellenwertes ent sprechend einem Fehler in dem beschädigten Codewort umfaßt.

14. System nach Anspruch 12, bei dem die Ermittelungslogik weiterhin folgende Be standteile umfaßt:
eine Logik zum Ermitteln einer zusammengesetzten Zuverlässigkeit vom "harten" Decoder, und
eine Vergleichslogik zum Vergleichen der zusammengesetzten Zuverlässigkeit des "harten" Decoders mit dem Zuverlässigkeits-Schwellenwert um zu ermitteln, ob ein brauchbares Ergebnis von dem "harten" Decoder erhalten werden kann.

15. System nach Anspruch 12, bei dem die Ermittelungslogik weiterhin eine Logik zum Ermitteln eines Satzes von Zuverlässigkeits-Schwellenwerten umfaßt.

16. System nach Anspruch 15, bei dem die Ermittelungslogik weiterhin eine Logik zum Ermitteln einer zusammengesetzten Zuverlässigkeit vom "harten" Decoder umfaßt.

17. System nach Anspruch 16, das weiterhin folgende Bestandteile umfaßt:
eine Auswahleinrichtung zum Selektieren eines Fehlerschwellenwertes basierend auf der Anzahl von Fehlern in dem beschädigten Codewort, und
eine Logik zum Vergleichen der zusammengesetzten Zuverlässigkeit mit der Schwellenwert-Zuverlässigkeit, um zu ermitteln, ob der "harte" Decoder ein brauch bares Ergebnis liefern kann.

18. System nach Anspruch 12, bei dem der zweite Decoder ein "Soft Decision" Decoder ist.

19. System nach Anspruch 12, bei dem der zweite Decoder ein Fehler-und-Lösch-De coder ist.

20. System nach Anspruch 12, bei dem das beschädigte Codewort von einem linearen Blockcode erzeugt wird.