• 专利附录
  • 专利说明
  • 权利要求
  • 类似技术
  • 同族专利
  • 引用文献
  • 法律状态
  • 优先权
    • 专利摘要:
    Ein Verfahren und ein System für platzsparende Fehlersteuercodierung zum Codieren von Daten in ein dreidimensionales Datenspeichermedium. Das Verfahren und das System ermöglichen die Erfassung und Korrektur einer begrenzten Anzahl von bestimmten Fehlertypen, die den bekannten Ausfallmodi einer Klasse von dreidimensionalen Datenspeichermedien entsprechen.
    公开号:DE102004006528A1
    申请号:DE200410006528
    申请日:2004-02-10
    公开日:2004-12-09
    发明作者:Ron M. Roth；Gadlel Cupertino Seroussl
    申请人:Hewlett Packard Development Co LP；
    IPC主号:G06F11-10
    专利说明:
    [0001] Dievorliegende Erfindung bezieht sich auf das Erfassen und Korrigierenvon Fehlern bei gespeicherten Daten und insbesondere auf ein raumeffizientesVerfahren zum Codieren von Daten in geschichteten dreidimensionalenSpeichern zum Ermöglichender Erfassung und Korrektur bestimmter Klassen von erwarteten Fehlern.
    [0002] Dievorliegende Erfindung bezieht sich auf eine Fehlerkorrektur, diees im allgemeinen ermöglicht,daß Fehler,die währendder Übertragung,Speicherung und Wiedergewinnung von elektronischen Daten auftreten, erfaßt und invielen Fällenkorrigiert werden. Viele Fehlersteuercodier-Verfahren und -Techniken mit linearer Blockcodierungsind gut bekannt zum Codieren seriell übertragener Daten, die in k-Länge-Mitteilungenunterteilt werden können.Im allgemeinen sind die Speichermodelle für Daten, an die die aktuellverfügbarenFehlersteuercodiertechniken angelegt werden, lineare und zweidimensionaleAnordnungen von Wörternin einer Speichervorrichtung. Es wurden Techniken entwickelt zumErkennen und Korrigieren bestimmter Typen von Fehlern in zweidimensionalenSpeichern, einschließlichKreuzfehlern (Criss-Cross-Fehlern), die in einem nachfolgenden Teilabschnittbeschrieben werden. Viele dieser Techniken verwenden systematischelineare Codes, die ebenfalls nachfolgend beschrieben sind. EineAnzahl dieser Verfahren sind beschrieben in „Theory of Codes with MaximumRank Distance",Gabidulin, Probl. Peredach. Inform., 21, S. 3–16 (1985); „OptimalArray Error-Correcting Codes",Gabidulin, Probl. Peredach. Inform., 21, S. 102–106 (1985); und „Reduced-Redundancy ProductCodes for Burst Error Correction",Roth und Seroussi, IEEE Trans. Inform. Theory, 44, S. 1.395–1.406 (1998).
    [0003] InjüngsterZeit wurde eine neue Klasse von dreidimensionalen Speichervorrichtungenentwickelt. Es wird erwartet, daß die Ausfallmodi für dieseKlasse von dreidimensionalen Speichervorrichtungen eine effizientedreidimensionale Datenfehlersteuercodiertechnik erfordern, die hoheVerhältnissevon Datenwörternzu der Gesamtzahl von Wörternvon codierten Daten, die in dem dreidimensionalen Datenspeichermediumgespeichert sind, liefern, um eine größere maximale Speicherkapazität in einerdreidimensionalen Datenspeichervorrichtung einer bestimmten Größe zu liefern.
    [0004] Esist die Aufgabe der vorliegenden Erfindung, ein verbessertes Verfahrenzum Codieren von Daten in ein dreidimensionales Datenspeichervolumen,Computerbefehle, die das Verfahren implementieren, und ein verbessertesVerfahren zum Decodieren von Daten in einem dreidimensionalen Datenspeichervolumenzu schaffen.
    [0005] DieseAufgabe wird durch ein Verfahren gemäß Anspruch 1, Befehle gemäß Anspruch9 sowie ein Verfahren gemäß Anspruch12 gelöst.
    [0006] EinAusführungsbeispielder vorliegenden Erfindung liefert eine raumsparende Fehlersteuercodiertechnikzum Codieren von Daten in ein dreidimensionales Datenspeichermediumunter Verwendung eines Produktcodes und mehrerer linearer Blockcodes.Diese Technik ermöglichtdie Erfassung und Korrektur einer begrenzten Anzahl von bestimmtenFehlertypen, die den bekannten wahrscheinlichen Fehlermodi einerKlasse von dreidimensionalen Datenspeichermedien entsprechen.
    [0007] BevorzugteAusführungsbeispieleder vorliegenden Erfindung werden nachfolgend Bezug nehmend aufdie beiliegenden Zeichnungen nähererläutert.Es zeigen:
    [0008] 1 ein dreidimensionalesDatenspeichermedium, in das Daten durch ein Verfahren codiert werden, dasein Ausführungsbeispielder vorliegenden Erfindung darstellt;
    [0009] 2 eine z-Zeile in dem dreidimensionalenDatenspeichervolumen V;
    [0010] 3 eine xy-Scheibe in demdreidimensionalen Datenspeichervolumen V;
    [0011] 4 ein Kreuz von Datenspeichereinheitenin dem Datenspeichervolumen V;
    [0012] 5 eine Datenspeichereinheitin einem Datenspeichervolumen, an dem ein Ausführungsbeispiel der vorliegendenErfindung praktiziert wird;
    [0013] 6 eine Datenspeichereinheitdes dreidimensionalen Datenspeichervolumens V, das ein Vier-Bit-Elementf des 16-Element-Felds F enthält;
    [0014] 7 die Codier- und Decodierprozesse;
    [0015] 8 das Layout eines Codearrays,das durch einen Produktcode erzeugt wird;
    [0016] 9 bis 13 die Füllung eines dreidimensionalenDatenspei chervolumens V mit nz – 1 xy-Scheiben;
    [0017] 14 und 15 die Speicherung additiver Inverserder Summen von z-Zeilenzellen in der xy-Scheibe des Volumens V mitder z-Koordinate „0";
    [0018] 16 die Inhalte des dreidimensionalenDatenspeichervolumens V nach der Ausführung von verschachtelten For-Schleifender Zeilen 11 – 24in einer Pseudocodeimplementierung eines Ausführungsbeispiels der vorliegendenErfindung;
    [0019] 17 und 18 das Füllen von Teil-yz-Scheiben undTeil-xz- Scheibendes Volumens V';
    [0020] 19 die Ergebnisse der Ausführung derverschachtelten For-Schleifen der Zeilen 25 – 30 und 31 – 36 derRoutine „Codieren";
    [0021] 20 die Berechnung einesProjektionsvektors;
    [0022] 21 die Verwendung der berechnetenProjektionsvektoren zum Speichern von Daten in z-Zeilen des dreidimensionalenDatenspeichervolumens V';
    [0023] 22 einen Dateneintrag indie am weitesten rechts liegende yz-Scheibe des dreidimensionalenDatenspeichervolumens V';
    [0024] 23 Paritätsprüfungssymbole in dem dreidimensionalenDatenspeichervolumen V';
    [0025] 24 den Betrieb von verschachteltenFor-Schleifen der Zeilen 51 – 55einer Pseudocodeimplementierung eines Ausführungsbeispiels der vorliegendenErfindung;
    [0026] 25 das Endergebnis der Codieroperation,die durch die Routine „Codieren" ausgeführt wurde;
    [0027] 26 die Berechnung einesSyndromvolumens Ŝx; und
    [0028] 27 auf ähnliche Weise wie 26 die Berechnung einesSyndromvolumens Ŝy.
    [0029] EinAusführungsbeispielder vorliegenden Erfindung ist eine raumsparende Technik zum Codierenvon Daten in ein dreidimensionales Datenspeichermedium. Ein Ausführungsbeispielder vorliegenden Erfindung, das nachfolgend beschrieben ist, umfaßt die Erkennungund Charakterisierung von Ausfallmodi einer Klasse von dreidimensionalenDatenspeichermedien, die Auswahl und Kombination von bestimmtenFehlersteuercodiertechniken und die Implementierung eines Verfahrensunter Verwendung der ausgewähltenund kombinierten Fehlersteuercodiertechniken zum Erfassen und Korrigierenbestimmter Ausfallmodi der Klasse von dreidimensionalen Datenspeichermedien.Folglich ist dieser Abschnitt in die folgenden drei Unterabschnitte unterteilt:(1) Beschreibung einer Klasse von dreidimensionalen Datenspeichermedienund Charakterisierung von Ausfallmodi der Klasse von dreidimensionalenDatenspeichermedien; (2) Mathematische Beschreibung von ausgewählten Fehlersteuercodiertechniken;und (3) Implementierung eines Verfahrens, das ein Ausführungsbeispielder vorliegenden Erfindung darstellt.
    [0030] 1 stellt ein dreidimensionalesDatenspeichermedium dar, in das Daten durch ein Verfahren codiert werden,das ein Ausführungsbeispielder vorliegenden Erfindung darstellt. Das Datenspeichermedium kann alsgefülltesRechteck angesehen werden, das eine Anzahl von Zellen oder Datenspeichereinheiten,wie z. B. eine Zelle 102, umfaßt. Das Datenspeichermediumist gekennzeichnet durch Abmessungen oder Anzahlen von Datenspeichereinheiten,entlang Kanten parallel zu den drei orthogonalen Achsen, x, y undz 104. Bei dieser und nachfolgenden Figuren und Beschreibungenwird ein unkonventionelles linksgerichtetes Koordinatensystem verwendet.Somit weist das in 1 dargestelltedreidimensionale Datenspeichermedium Abmessungen nx,ny und nz auf, wobeidie x-Achse nach links 106 gerichtet ist, die y-Achse nachoben 108 gerichtet ist, und die z-Achse von der Ebene desPapiers 110 nach außengerichtet ist. Bei den nachfolgenden Erörterungen kann ein dreidimensionalesDatenspeichervolumen V notationsmäßig mit den Indizes i, j undl als ein Satz von Datenspeichereinheiten beschrieben werden, wiefolgt: {[i, j, l) : 0 ≤ i < nx, 0 ≤ j < ny,0 ≤ l < nz
    [0031] Beieiner folgenden Pseudocodeimplementierung kann jedes Element desdreidimensionalen Datenspeichervolumens V durch Indizes x, y undz spezifiziert werden, die der x-Achse, der y-Achse und der z-Achse entsprechen,wie folgt: V[x][y][z]
    [0032] EinAusführungsbeispielder vorliegenden Erfindung ist bezüglich des Codierens von Datenin ein einzelnes dreidimensionales Datenspeichervolumen V beschrieben.Im allgemeinen umfaßtein tatsächliches dreidimensionalesDatenspeichermedium Hunderte von Tausenden, Millionen oder sogarMilliarden von einzelnen dreidimensionalen Datenvolumen, wie z.B. ein in 1 dargestelltesdreidimensionales Datenvolumen V, und das beschriebene Ausführungsbeispielder vorliegenden Erfindung kann nacheinander in einer gut definiertenReihenfolge an jedes der dreidimensionalen Datenvolumen innerhalbdes gesamten dreidimensionalen Datenspeichermediums angelegt werden.
    [0033] MehrereTypen von Teilsätzender Datenspeichereinheiten in einem einzelnen dreidimensionalenDatenspeichervolumen V werden bei der folgenden Erörterungund bei einer Pseudocodeimplementierung verwendet, die nachfolgendgeliefert wird. Der erste Teilsatztyp oder die erste Unterteilungwird als eine „z-Zeile" bezeichnet. 2 zeigt eine z-Zeile in dem dreidimensionalenDatenspeichervolumen V. Eine z-Zeile ist ein Satz von Datenspeichereinheiten,die alle identische x-Achsen- und y-Achsen-Koordinaten aufweisen,oder anders ausgedrückt,eine z-Zeile, die durch x- und y-Koordinaten „a" und „b" spezifiziert ist,kann notationsmäßig beschriebenwerden als: {(i, j, l) : i = a, j = b, 0 ≤ l < nz}.
    [0034] Einez-Zeile kann auch notationsmäßig als „Vxy" spezifiziert werden,und eine spezielle Datenspeichereinheit in einer z-Zeile kann inden Pseudocoderoutinen unter Verwendung der Notation „Vxy[z]" spezifiziert undauf dieselbe zugegriffen werden. Wie es in 2 ersichtlich ist, ist eine z-Zeile 202 imwesentlichen ein lineares Array von Datenspeichereinheiten, diein der Richtung der z-Achse ausgerichtet sind.
    [0035] Einzweiter Typ von Teilsatz oder Unterteilung von Datenspeichereinheitenwird als eine „xy-Scheibe" bezeichnet. 3 stellt eine xy-Scheibein dem dreidimensionalen Datenspeichervolumen V dar. Wie es in 3 gezeigt ist, ist einexy-Scheibe eine Ebene von Datenspeichereinheiten in dem Datenspeichervolumen Vsenkrecht zu der z-Achse. Alle Datenspeichereinheiten in einer xy-Scheibehaben identische z-Indizes. Somit kann eine xy-Scheibe an der z-Achsenkoordinate „c" spezifiziert werdenals: {[i, j, l) : 0 ≤ i < nx, 0 ≤ j < ny,l = c}oder alternativ als: Vz=c
    [0036] Beiden Pseudocoderoutinen, die ein Ausführungsbeispiel der vorliegendenErfindung beschreiben, kann ein Datenelement in einer xy-Scheibe über dieNotation „Vz[y][z]" spezifiziertund auf dasselbe zugegriffen werden. Zusätzliche Teilsätze umfassenyz-Scheiben, Vx, xz-Scheiben, Vy,x-Zeilen Vyz und y-Zeilen Vxz.
    [0037] Esgibt zwei unterschiedliche Typen von Ausfallmodi in einer Klassevon dreidimensionalen Datenspeichermedien, die über einen Fehlersteuercodeerfaßtund korrigiert werden müssen.Ein erster Ausfallmodus wird als ein „Kreuzfehler" bezeichnet. 4 stellt ein Kreuz von Datenspeichereinheitenin dem Datenspeichervolumen V dar. Wie es in 4 gezeigt ist, schneiden sich eine x-Zeile 402 undeine y-Zeile 404 indem dreidimensionalen Datenspeichervolumen an einer gemeinsamenDatenspeichereinheit 406. Die x-Zeile 402 unddie y-Zeile 404 treten in einer speziellen xy-Scheibe auf.Ein erster Typ von Ausfallmodus umfaßt den Ausfall von einer odermehreren Dateneinheiten in einem Kreuz, wie z. B. demjenigen, dasin 4 gezeigt ist. Einzweiter Typ von Ausfallmodus fürein dreidimensionales Datenspeichervolumen V ist der Ausfall einergesamten xy-Scheibe. Bei den folgenden Erörterungen werden diese beidenunterschiedlichen Typen von Ausfallmodi als „Kreuzausfälle" und „Scheibenausfälle" oder alternativ „Typ-1-Ausfälle" und „Typ-2-Ausfälle" bezeichnet. Kreuzausfälle erzeugenKreuz- oder Typ-1-Fehler und Scheibenausfälle erzeugen Scheiben- oder Typ-2-Fehler.Das beschriebene Ausführungsbeispielder vorliegenden Erfindung ist entworfen, um so viel wie möglich vont Kreuzfehlern und höchstenseinen einzelnen Scheibenfehler in einem dreidimensionalen DatenspeichervolumenV zu erfassen und zu korrigieren, die als die wahrscheinlichstenFehler identifiziert sind, die in einer Klasse von dreidimensionalenDatenspeichermedien auftreten können.
    [0038] Dasbeschriebene Ausführungsbeispielder vorliegenden Erfindung verwendet beim Fehlersteuercodieren eineAnzahl von gut bekannten Techniken. Eine exzellente Referenz für diesesGebiet ist das Lehrbuch „ErrorControl Coding: The Fundamentals and Applications", Lin und Costello,Prentice-Hall, Incorporated,New Jersey, 1983. In diesem Unterkapitel wird eine kurze Beschreibungder Fehlererfassungs- und Fehlerkorrekturtechniken gegeben, diebei der vorliegenden Erfindung verwendet werden. ZusätzlicheEinzelheiten könnenvon dem oben angemerkten Lehrbuch oder vielen anderen Lehrbüchern, Abhandlungenund Zeitschriftartikeln auf diesem Gebiet erhalten werden.
    [0039] BeimBeschreiben von Fehlererfassung und -korrektur ist es sinnvoll,die Daten, die übertragen,gespeichert und wiedergewonnen werden sollen, als eine oder mehrereMitteilungen zu beschreiben, wobei eine Mitteilung μ eine geordneteSequenz von Symbolen, μi, umfaßt,die Elemente eines Felds F sind. Eine Mitteilung μ kann ausgedrückt werdenals: μ =(μ0, μ1, ..., μk–1)wobei μi ∊ F.
    [0040] DasFeld F ist ein Satz, der unter Multiplikation und Addition geschlossenist und der multiplikative und additive Inverse umfaßt. Beider rechentechnischen Fehlererfassung und -korrektur ist es üblich, Felderzu verwenden, die einen Teilsatz von Ganzzahlen umfassen, mit Größen gleicheiner Primzahl, wobei die Additions- und Multiplikationsoperatorenals Moduloaddition und Modulomultiplikation modifiziert sind. Inder Praxis wird üblicherweisedas binäreFeld verwendet. Felder mit einer Größe gleich einer Potenz einerPrimzahl, meistens 2, werden ziemlich häufig verwendet. Für dieseFelder werden Additions- und Multiplikationsoperatoren mit unzerlegbarenModulopolynomen ausgeführt. Üblicherweisewird die ursprünglicheMitteilung in eine codierte Mitteilung c codiert, die auch einegeordnete Sequenz von Elementen des Felds F umfaßt, ausgedrückt wie folgt: c= (c0, c1, ...,cn–1)wobeici ∊ F.
    [0041] Dasbeschriebene Ausführungsbeispielder vorliegenden Erfindung verwendet Blockcodiertechniken, bei denenDaten in Blöckecodiert werden. Bei dieser Erörterungkann ein Block als eine Mitteilung μ betrachtet werden, die einefeste Anzahl von Symbolen k umfaßt, die in eine Mitteilungc codiert wird, die eine geordnete Sequenz von n Symbolen umfaßt. Diecodierte Mitteilung c enthältim allgemeinen eine größere Anzahlvon Symbolen als die ursprünglicheMitteilung μ unddaher ist n größer alsk. Die r Zusatzsymbole in der codierten Mitteilung, wobei r gleichn – kist, werden verwendet, um redundante Prüungsinformationen zu tragen,um es zu ermöglichen,daß Fehler,die während Übertragung,Speicherung und Wiedergewinnung entstehen, mit einer extrem hohenErfassungswahrscheinlichkeit erfaßt werden und in vielen Fällen korrigiertwerden.
    [0042] DasCodieren von Daten für Übertragung,Speicherung und Wiedergewinnung und nachfolgende Decodierung dercodierten Daten kann notationsmäßig wiefolgt beschrieben werden, wenn währendder Übertragung,Speicherung und Wiedergewinnung der Daten keine Fehler auftreten: μ → c(s) → c(r) → μwobeic(s) die codierte Mitteilung vor der Übertragung ist, und c(r) dieanfangs wiedergewonnene oder empfangene Mitteilung ist. Somit wirdeine Anfangsmitteilung μ codiert,um eine codierte Mitteilung c(s) zu erzeugen, die dann übertragenund gespeichert wird und dann nachfolgend als anfänglich empfangeneMitteilung c(r) wiedergewonnen oder empfangen wird. Wenn dieselbenicht verfälschtist, wird die anfangs empfangene Mitteilung c(r) dann decodiert,um die ursprünglicheMitteilung μ zuerzeugen. Wie es oben angemerkt wurde, wenn keine Fehler entstehen,ist die ursprünglichcodierte Mitteilung c(s) gleich der anfangs empfangenen Mitteilungc(r), und die anfangs empfangene Mitteilung c(r) wird einfach ohneFehlerkorrektur, zu der ursprünglichenMitteilung μ decodiert.
    [0043] Wennwährendder Übertragung,Speicherung oder Wiedergewinnung einer codierten Mitteilung Fehlerentstehen, kann die Mitteilungscodierung und -decodierung wie folgtausgedrücktwerden: μ(s) → c(s) → c(r) → μ(r)
    [0044] Somit,wie es oben angemerkt wurde, kann die Endmitteilung μr gleichoder nicht gleich der anfänglichenMitteilung μs sein, abhängig von der Genauigkeit derFehlererfassungs- undFehlerkorrekturtechniken, die verwendet werden, um die ursprünglicheMitteilung μs zu codieren, und die anfänglich empfangeneMitteilung c(r) zu decodieren oder zu rekonstruieren, um die alsletztes empfangene Mitteilung μr zu erzeugen. Die Fehlererfassung ist derProzeß desBestimmens, daß: c(r) ≠ c(s)während Fehlerkorrekturein Prozeß ist,der die anfänglichcodierte Mitteilung von einer verfälschten anfänglich empfangenen Mitteilungrekonstruiert: c(r) → c(s)
    [0045] DerCodierprozeß istein Prozeß,durch den Mitteilungen, die als μ symbolisiertsind, in codierte Mitteilungen c transformiert werden. Alternativkann eine Mitteilung μ alsein Wort angesehen werden, das einen geordneten Satz von Symbolenvon dem Alphabet umfaßt,das aus Elementen von F besteht, und die codierten Mitteilungenc könnenals ein Codewort angesehen werden, das auch einen geordneten Satz vonSymbolen von dem Alphabet von Elementen von F umfaßt. EinWort μ kannjede geordnete Kombination von k Symbolen sein, die aus den Elementenvon F ausgewähltsind, währendein Codewort c definiert ist als eine geordnete Sequenz von n Symbolen,die aus Elementen von F überden Codierprozeß ausgewählt werden: {c : μ → c}.
    [0046] LineareBlockcodiertechniken codieren Wörtermit der Längek, indem dieselben das Wort μ alseinen Vektor in einem k-dimensionalenVektorraum betrachten, und den Vektor μ mit einer Generatormatrix multiplizieren,wie folgt: c = μ·G
    [0047] Dasnotationsmäßige Erweiternder Symbole in der obigen Gleichung erzeugt eine der folgenden alternativenGleichungen:
    [0048] DieGeneratormatrix G füreinen linearen Blockcode kann die folgende Form aufweisen:
    [0049] Somitkann die Generatormatrix G in eine Form einer Matrix P plaziertwerden, die mit einer k mal k Identitätsmatrix Ik,k vergrößert ist.Ein Code, der durch einen Generator auf diese Weise erzeugt wird,wird als ein „systematischerCode" bezeichnet.Wenn diese Generatormatrix an ein Wort μ angelegt wird, hat das resultierendeCodewort c die folgende Form: c = (c0,c1, ..., cr–1, μ0, μ1,..., μk–1)wobeici = (μ0P0,i + μ1P1,i, ..., μk–1Pk–1,i).
    [0050] Somitumfassen bei einem systematischen linearen Blockcode die Codewörter r Paritätsprüfungssymboleci, gefolgt von den Symbolen, die das ursprünglicheWort μ umfassen.Wenn keine Fehler auftreten, erscheint das ursprüngliche Wort oder die Mitteilung μ in einerKlartextform innerhalb des entsprechenden Codeworts und kann ohneweiteres von demselben extrahiert werden. Die Paritätsprüfungssymbolesind lineare Kombinationen der Symbole der ursprünglichen Mitteilung oder desWorts μ.
    [0051] EineForm einer zweiten sinnvollen Matrix ist die ParitätsprüfungsmatrixHr,n, definiert als: Hr,n = [Ir,r| – PT]oder äquivalent
    [0052] DieParitätsprüfungsmatrixkann fürsystematische Fehlererfassung und Fehlerkorrektur verwendet werden.Fehlererfassung und -korrektur umfaßt das Berechnen eines SyndromsS aus einer anfangs empfangenen oder wiedergewonnenen Mitteilungc(r) wie folgt: S = (s0,s1, ..., Sn–k)= c(r)·HT wobei HT dieTransponierte der ParitätsprüfungsmatrixHr,n ist, ausgedrücktals:
    [0053] DieElemente des Syndromvektors S sind: si = (c(r)i – c(r)rp0,i – c(r)r+1p1,i – c(r)r+2p2,i – ... – c(r)n–1pk–1,i).
    [0054] DerFehlervektor e ist definiert als die Differenz zwischen oder dasErgebnis der Vektorsubtraktion von einer anfangs empfangenen Mitteilungc(r) und einem anfangs vorbereiteten und gesendeten Codewort c(s) wiefolgt: e@c(r) – c(s) ⇒ c(r) = c(s) + e.
    [0055] DerSyndromvektor S ist wie folgt mit dem Fehlervektor verwandt: S = c(r)HT = (c(s) +e)HT = c(s)HT +eHT = eHT.
    [0056] DieFehlerkorrektur umfaßtdas Identifizieren der Fehler, die sich nach der Vorbereitung desCodeworts c(s) und bis hin zum Empfang oder der Wiedergewinnungder anfangs empfangenen Mitteilung c(r) ergeben haben, und das Problemder Fehlerkorrektur ist das Problem des Findens eines Fehlervektorse, so daß eHT = c(r)HT.
    [0057] Dannwird eine Fehlerkorrektur ausgeführt,um ein korrigiertes Wort c zu erzeugen, das das wahrscheinlichsteanfangs übertrageneoder gespeicherte Codewort darstellt, durch: ĉ = c(r) – e
    [0058] Implementierungeines Verfahrens, das ein Ausführungsbeispielder vorliegenden Erfindung darstellt Bei dem beschriebenen Ausführungsbeispielist jede Datenspeichereinheit in einem dreidimensionalen DatenspeichervolumenV ein Element f eines Felds F mit q Elementen. Bei dem beschriebenenAusführungsbeispiel kannf jeder der Ganzzahlwerte in dem Bereich von 0 – 15 sein, äquivalent zu dem Bereich vonGanzzahlen, die in 4 Bits gespeichert sein können. 5 stellt eine Datenspeichereinheit ineinem Datenspeichervolumen dar, an dem ein Ausführungsbeispiel der vorliegendenErfindung praktiziert wird. 5A zeigt,daß eineeinzelne Datenspeichereinheit 502 so gesehen werden kann,daß dieselbevier getrennte Bits A – Dumfaßt. 5B stellt dar, daß jederder möglichenWerte der Datenspeichereinheit f als eine unterschiedlich geordnete Kombinationvon Bitwerten fürdie Bits A – Dgesehen werden kann. In 5B sinddie unterschiedlichen Elemente f des Felds F mit den Zeichen „a" – „p" gekennzeichnet, äquivalent zu den Ganzzahlen „0" – „15". Der Deutlichkeit halber stellt 6 dar, daß jede Datenspeichereinheitdes dreidimensionalen Datenspeichervolumens V ein Vier-Bit-Äquivalentelement f des 16-Element-FeldsF ist.
    [0059] Wiees oben erörtertwurde, umfaßtdas Codieren einer Mitteilung oder eines Worts unter Verwendung eineslinearen Blockcodes zum Erzeugen eines Codeworts, das Verwendender Mitteilung oder des Worts zum Erzeugen eines Codeworts, dasdie Mitteilung oder das Wort in Klartextform umfaßt, zusammenmit zusätzlichenParitätsprüfungssymbolen. 7 stellt die Codier- undDecodierprozesse dar. Wie es in 7 gezeigt ist,umfaßtjede Mitteilung und jedes Wort eine geordnete Sequenz von k Symbolen.Somit numeriert das linke Array 702 in 7 (wovon nur ein Teil in 7 gezeigt ist) die verschiedenen unterschiedlichenqk gültigen Mitteilungenoder Wörterder Längek. In dem Array 702 stellt jede Zeile eine bestimmte Mitteilungoder ein Wort dar. Bei dem in 7 gezeigtenBeispiel hat jedes Wort oder jede Mitteilung eine Länge k =4. Die Mitteilungen oder Wörterwerden in Codewörtercodiert, die in dem rechten Array 704 in 7 enthalten sind. In 7 ist jede Zeile des rechten Arrays 704 einbestimmtes Codewort, das der Mitteilung in der entsprechenden Zeiledes linken Arrays entspricht. Wie es in 7 ersichtlich ist, entsprechen die letztenvier Symbole in jedem Codewort der Klartextmitteilung, aus der dasCodewort erzeugt wurde. Somit beziehen sich für jedes spezielle Codier-/Decodierlinearblockschemadie Parameter k, n und r auf die Länge der Mitteilungen oder Wörter, dieLänge dercodierten Mitteilungen oder Codewörter bzw. den minimalen Hamming-Abstanddes Codes. Nachfolgend wird auf einen speziellen systematischenlinearen Blockcode verwiesen durch die Notation „C[n, k, r]", wobei C der Namedes Codes ist, n die Längeeines Codeworts ist, k die Längedes Wortes ist, aus dem ein Codewort der Länge n erzeugt wird, und r derminimale Hamming-Abstand des Codes ist.
    [0060] EinAusführungsbeispielder vorliegenden Erfindung ist nachfolgend mit gleichzeitiger Bezugnahme aufsowohl eine Pseudocodeimplementierung als auch eine große Anzahlvon Darstellungen beschrieben. Die Pseudocodeimplementierung istin einer höherenPseudoprogrammiersprache geschrieben, unter Verwendung bestimmterNotationsregeln und Elemente der Programmiersprache C++, aber auchunter Verwendung einer mathematischen Notation eines höheren Pegels,die zum genauen und eindeutigen Spezifizieren der Operationen einesVerfahrens geeignet ist, das ein Ausführungsbeispiel der vorliegendenErfindung darstellt. Es ist anzumerken, daß lokale Variablen und Umfangsregelnfür Subroutinenbei dem folgenden Pseudocode nicht verwendet werden, aus Gründen derKürze.Bei einer tatsächlichenImplementierung in einer normalen Programmiersprache, wie z. B.C++, würdeerwartet, daß normaleProgrammierregeln, wie z. B. Eliminieren globaler Variablen undSteuern von Datenaustausch zwischen Routinen durch gut strukturierteSchnittstellen, eingehalten werden.
    [0061] Zunächst isteine Routine „Codieren" vorgesehen. DieRoutine „Codieren" beginnt mit denfolgenden Erklärungen:
    [0062] DieRoutine „Codieren" umfaßt ein Verfahrenzum Codieren von Daten in ein dreidimensionales Datenspeichervolumen,das eine Anzahl von Datenspeichereinheiten umfaßt. Das Verfahren umfaßt folgende Schritte:Empfangen einer Datensequenz und Codieren der Datensequenz unterVerwendung eines linearen Produktcodes zum Codieren von Daten inCodearrays von Datenwerten, und Verwenden von zwei linearen Blockcodeszum Codieren von Daten in Vektoren von Datenwerten.
    [0063] DieRoutine „Codieren" empfängt undcodiert Wörter,die Elemente qi des Felds F enthalten, wiees oben in Zeile 3 erklärtist. Zwei verschiedene dreidimensionale Volumen von Datenspeichereinheitenwerden verwendet, Volumen V und V', wie es oben in Zeile 4 erklärt ist.Das beschriebene Ausführungsbeispielverwendet fünfunterschiedliche systematische lineare Blockcodes Cx,Cy, CxCy,Cz und C'z, die oben in den Zeilen 6–10 erklärt sind.Die Parameter k, n und r fürjeden der fünfunterschiedlichen systematischen linea ren Blockcodes sind in denErklärungenspezifiziert. Der systematische lineare Blockcode CxCy ist ein Produktcode. Ein Produktcode isteine Kombination aus zwei einfachen systematischen linearen Codes,die ein zweidimensionales Codearray erzeugt anstatt einem eindimensionalenCodewort. 8 stellt dasLayout eines Codearrays dar, der durch einen Produktcode erzeugtwird. Wie es in 8 gezeigtist, umfaßtdas Codearray kxky Klartextsymbolein einer Klartextregion des Codearrays 802 zusammen mitdrei Paritätsprüfungssymbolregionen 804–806,mit Abmessungen und Ausrichtungen, wie es in 8 gezeigt ist. Codearrays sind als Ebenenin einem dreidimensionalen Datenspeichervolumen gespeichert. Produktcodessind in dem Fehlersteuercodierfeld gut bekannt und werden in demoben erwähntenText „ErrorControl Coding: Fundamentals and Applications" beschrieben. Die Routine „Codieren" verwendet vier unterschiedlicheVektoren von Elementen des Felds F, v0, v1, v2 und v3, die obenin den Zeilen 11–13erklärtsind, die die in den Erklärungenspezifizierten Längenaufweisen. Die Variable „Summe", die oben in Zeile14 erklärtist, speichert ein Element des Felds F, das die Summe von zwei Elementendes Felds F darstellt. Die Routine „Codieren" verwendet vier unterschiedliche Ganzzahlvariablen „x", „y", „z" und „i", die oben in Zeile15 erklärtsind. Schließlichverwendet die Routine „Codieren" die Funktion „getInfo", die eine spezifizierteAnzahl von Informationselementen des Felds F von einem Eingangsstromzum Codieren erhält.Die Routine „Codieren" ruft die Funktion „getInfo" auf, die oben in Zeile16 erklärtist, um jeden nachfolgenden Satz von Informationselementen zu erhalten,der in dem dreidimensionalen Datenspeichervolumen V codiert werdensoll.
    [0064] Wiees nachfolgend gezeigt ist, verwendet die Routine „Codieren" die folgenden Notationsregeln:
    [0065] DieRoutine „Codieren" verwendet vier Subroutinen,die nachfolgend getrennt beschrieben werden. Die erste SubroutineSubtractZLineFromInfoVector wird nachfolgend geliefert:
    [0066] SubtractZLineFromInfoVectorruft k'z-Informationseinheitenvon dem Informationselementstrom ab, über die Funktion „getInfo" und subtrahiertvon denselben die aktuellen Inhalte einer z-Zeile von einem dreidimensionalenDatenspeichervolumen V. Die Ergebnisse werden in dem Vektor v1 belassen.
    [0067] Nachfolgendwird die Subroutine ComputeXZProjectionVector geliefert:
    [0068] ComputeXZProjectionVectorprojiziert die Inhalte einer xz-Scheibeoder xz-Ebene in einem dreidimensionalen Datenspeichervolumen V' in den Vektor „v0". Die SubroutineComputeYZProjectionVector berechnet einen Projektionsvektor ausyz-Scheiben in einem dreidimensionalen Datenspeichervolumen V' auf ähnliche Weisewie die obige Routine:
    [0069] DieSubroutine ComputeProjectionVolumeDifference wird als nächstes geliefert:
    [0070] DieseSubroutine addiert die Inhalte einer z-Zeile von einem dreidimensionalenDatenspeichervolumen V mit den Inhalten eines Vektors „v0" und plaziert dieSumme in den Vektor „v2".
    [0071] Schließlich wirdder Hauptabschnitt der Routine „Codieren" geliefert:
    [0072] DieseRoutine erhältgrundsätzlicheine Anzahl von Informationselementen von einem Eingangsstrom, wobeidie Anzahl oben auf Zeile 3 in einem Kommentar beschrieben ist,und codiert diese Informationselemente in ein dreidimensionalenDatenspeichervolumen V. Beim Abschluß der Codierung erscheinendiese Informationselemente in Klartextform in dem DatenspeichervolumenV, zusammen mit einer relativ kleinen Anzahl von Paritätsprüfungssymbolen.
    [0073] Zunächst ruftdie Routine in der For-Schleife der Zeilen 7 – 10 die Längen von kxky Informationselementen von dem Eingangsstromab und codiert denselben in Codearrays über den Produktcode CxCy, zum Bilden vonnz – 1xy-Scheiben in dem dreidimensionalen Datenspeichervolumen V. 9 – 13 stellendie Füllungdes dreidimensionalen Datenspeichervolumens V mit nz – 1 xy-Scheibendurch die For-Schleife der Zeilen 7 – 10 dar. Es ist anzumerken,daß diexy-Scheibe mit der z-Achsenkoordinate „0" bei diesem anfänglichen Schritt nicht in dasdreidimensionale Datenspeichervolumen V eingegeben wird. Wie esin 9 gezeigt ist, können dieParitätsprüfungssymbolefür dieZeilen der ersten xy-Scheibemit der z-Koordinate 1 so gesehen werden, daß dieselben durch Anlegen derParitätsprüfungsregelnfür Cx an die Zeilen der Informationssymbole 902 gefüllt werdenzum Erzeugen codierter Zeilen der Länge nx 904 undEingeben der codierten Zeilen, wie z. B. codierte Zeile 904,in das dreidimensionale Datenspeichervolumen V 100. Wie es in 10 gezeigt ist, kann einespezielle xy-Scheibe 1002 so gesehen werden, daß sie teilweiseaus ky Zeilen aufgebaut ist, durch Anlegeneines systematischen linearen Blockcodes Cx zumErhalten codierter Zeilen der Längenx. Wie es in 11 gezeigtist, besteht eine spezielle xy-Scheibe ferner aus Spalten 1102,die erhalten werden durch Anlegen des systematischen linearen BlockcodesCy an ky Informationselemente 1104.Die Inhalte der ersten kx Informationseinheitenin jeder Zeile und die ersten ky Informationseinheitenin jeder Spalte sind Klartextinformationssymbole, die von dem Informationseingangsstromerhalten werden. Wie es in 12 gezeigtist, ist die letzte xy-Scheibe 1002 ein Codearray, dasdas Produkt des Anlegens des Produktcodes CxCy an kxky Informationselementedarstellt. Es ist anzumerken, daß die xy-Scheibe 1002 kxky Klartextinformationseinheitenumfaßt(in 12 nicht schraffiert),zusammen mit vertikalen und horizontalen Regionen von Paritätsprüfungssymbolen (in 12 schraffiert) 1004 bzw. 1006.Wie es in 13 gezeigtist, verläuftdie For-Schleife der Zeilen 7 – 10 vonder z-Koordinate 1 zu der z-Koordinatenz – 1zum Erzeugen eines Volumens von Klartextinformationselementen 1302 über undnach links von den Volumen der Paritätsprüfungselemente 1304 und 1306 (dieParitätsprüfungselementesind schraffiert). Es ist anzumerken, daß der Produktcode verwendetwerden könnte, umdas dreidimensionale Datenspeichervolumen V zu füllen, und Fehlererfassungs-und Korrekturfähigkeiten zuliefern, die in Einklang sind mit der Anzahl von Paritätsprüfungssymbolennzrxry.Wie es nachfolgend ersichtlich ist, verwendet eine solche Technikje doch eine viel größere Anzahlvon Paritätsprüfungssymbolenals erforderlich ist, um Fehler zu erfassen und zu korrigieren,die sich aus den zwei Typen von wahrscheinlichen Ausfallmodi ergeben,die oben beschrieben sind. Somit wird das beschriebene Ausführungsbeispielder vorliegenden Erfindung verwendet, um einen größeren Anteilan Datenspeichereinheiten in einem dreidimensionalen DatenspeichervolumenV zum Speichern von Klartextinformationselementen zu verwenden,und zum entsprechenden Verringern des Anteils an Paritätsprüfungsinformationselementenin dem dreidimensionalen Datenspeichervolumen V.
    [0074] Nachfolgendberechnet die Routine „Codieren" in den verschachteltenFor-Schleifen der Zeilen 11 – 20die Summe der Datenspeichereinheiten in jeder z-Zeile des dreidimensionalenDatenspeichervolumens V, das in 13 gezeigtist, und speichert das additive Inverse dieser Summe in dem erstenElement jeder z-Zeile in dem dreidimensionalen DatenspeichervolumenV. Dieser Prozeß istin 14–15 dargestellt. Wie es in 14 gezeigt ist, wird eineerste z-Zeile 1402 mit x- und y-Koordinaten (0,0) in derersten Iteration der verschachtelten For-Schleifen der Zeilen 11 – 24 inBetracht gezogen. Die Dateneinheiten in der z-Zeile 1402 werdenunter Verwendung von Moduloaddition summiert und das additive Inversedieser Summe wird in der ersten Datenspeichereinheit 1404 derz-Zeile gespeichert. Als Folge der Ausführung der verschachtelten For-Schleifender Zeilen 11 – 20wird die erste xy-Scheibe des dreidimensionalen DatenspeichervolumensV 100 mit den additiven Inversen der Summen der z-Zeilengefüllt. 16 stellt die Inhalte desdreidimensionalen Datenspeichervolumens V nach der Ausführung derverschachtelten For-Schleifen der Zeilen 11 – 20 dar. Jede der z-Zeilenin den Paritätsprüfungsregionendes Volumens an der unteren und rechten Seite des Volumens, wiez. B. die z-Zeile 1602, enthalten nur Paritätsprüfungssymbole.Jede der internen z-Zeilen in dem überwiegend Klartextinformationssymbolabschnittdes Volumens, wie z. B. z-Zeile 1604, enthalten Klartextinformationssymbole inallen außerder ersten Datenspeichereinheit der z-Zeile. Die erste Datenspeichereinheit,wie z. B. die Datenspeichereinheit 1606 der z-Zeile 1604,enthältdas additive Inverse der Summe der Informationselemente, die inden verbleibenden Datenspeichereinheiten der z-Zeile gespeichertsind.
    [0075] Nachfolgendcodiert die Routine „Codieren" in den verschachteltenFor-Schleifen der Zeilen 21 – 26, zusätzlicheInformationssymbole in ein zweites dreidimensionales DatenspeichervolumenV'. Die zusätzlichen Informationssymbolewerden in z-Zeilen codiert, die eine Anzahl von vertikalen yz-Scheibenan der rechten Seite des dreidimensionalen DatenspeichervolumensV' bilden. Wie esin den For-Schleifenargumentenersichtlich ist, wird in den verschachtelten For-Schleifen der Zeilen21 – 26eine Anzahl von vertikalen yz-Scheiben erzeugt, die gleich einerweniger als rx der Anzahl von Paritätsprüfungssymbolensind, die durch den systematischen linearen Blockcode Cx erzeugtwerden, beginnend von der x-Achsenkoordinate 1 bis zu der x-Achsenkoordinaterx – 1.Das Codieren umfaßtdas Subtrahieren der aktuellen Inhalte des dreidimensionalen DatenspeichervolumensV für einespezielle z-Zeile von einem Vektor, der neu erhaltene Informationselemente enthält, undCodieren des resultierenden Vektors unter Verwendung des systematischenlinearen Blockcodes C'z auf der Zeile 29 zum Erzeugen eines Codeworts,das als z-Zeile in dem dreidimensionalen Datenspeichervolumen V' gespeichert ist.Dieser Prozeß istin 17–18 dargestellt. Wie es in 17 gezeigt ist, werden für die erstez-Zeile addiert mit dem dreidimensionalen Datenspeichervolumen V', k'z Informationselemente vondem Eingangsstrom erhalten und in den Vektor μ 1702 geladen. DieInhalte der entsprechenden z-Zeile von dem dreidimensionalen DatenspeichervolumenV 1704 werden von dem Vektor μ 1702 subtrahiert unddie Ergebnisse in den Vektor 1706 plaziert. Dieser Vektorwird dann unter Verwendung des Verwendung des systematischen linearenBlockcodes C'z auf der Zeile 29 der Routine „Codieren" codiert, um dasCodewort oder den Vektor 1708 zu erzeugen. Dieses Codewort 1708 wirddann in dem dreidimensionalen Datenspeichervolumen V' 1710 anden x,y-Koordinaten gespeichert, die den x,y-Koordinaten der z-Zeile des dreidimensionalen DatenspeichervolumensV 1704 entsprechen, subtrahiert von den erhaltenen Informationselementendes Vektor μ 1702.Als eine Folge der Ausführungder For-Schleife der Zeilen 21 – 26wird eine Anzahl von vertikalen yz-Scheiben, wie z. B. die yz-Scheibe 1802,in das dreidimensionale Datenspeichervolumen V' eingegeben. Obwohl in 18 nur eine yz-Scheibe gezeigt ist, plazierendie verschachtelten For-Schleifen der Zeilen 21 – 26 rx – 1 solcheryz-Scheiben in das dreidimensionale Datenspeichervolumen V'. Die verschachtelten For-Schleifender Zeilen 27 – 32führenauf ähnlicheWeise einen horizontalen Block von z-Zeilen, der durch den systematischenlinearen Blockcode „C'z" codiert wird, indas Datenspeichervolumen V ein. Das Ergebnis der Ausführung derverschachtelten For-Schleifen der Zeilen 21 – 26 und der Zeilen 27 – 32 isteine Spiegelbild-L-Form-Region von z-Zeilen in dem Datenspeichervolumen V'. 19 zeigt die Ergebnisse der Ausführung derverschachtelten For-Schleifen der Zeilen 21 – 26 und 27 – 32 derRoutine „Codieren". Obwohl in 19 nur eine einzelne yz-Scheibeund eine einzelne xz-Scheibe gezeigt sind, wie es oben beschriebenist, erzeugen die verschachtelten For-Schleifen der Zeilen 21 – 26 undder Zeilen 27 – 32im allgemeinen einen vertikalen und horizontalen Block von z-Zeilenin dem dreidimensionalen Datenspeichervolumen V'. Die vertikalen yz-Scheiben beginnen mit der x-Achsenkoordinate1 und setzen sich nach links durch die x-Achsenkoordinate rx – 1fort. Die horizontalen xz-Scheiben beginnen mit der y-Achsenkoordinate1 und fahren nach oben durch die y-Achsenkoordinate ry – 1 fort.Es ist anzumerken, daß dieam weitesten rechts liegende yz-Scheibe und die unterste xz-Scheibe des dreidimensionalenDatenspeichervolumens V' noch nichtgefülltsind nach der Ausführungder verschachtelten For-Schleifen der Zeilen 27 – 32.
    [0076] Nachfolgendwerden in den For-Schleifen der Zeilen 33 – 39 und 40 – 46 dierechteste yz-Scheibe und die unterste xz-Scheibe des dreidimensionalen DatenspeichervolumensV' aufgefüllt über eineeher komplexe Operation, die das Berechnen und Codieren von Projektionsvektorenumfaßt.Diese Operation wird durch die Untersuchung des obigen Pseudocodesverständlich,aber kann vielleicht am besten verstanden werden durch Untersuchendes Pseudocodes, der übereinstimmtmit 20–23. Die rechteste yz-Scheibeumfaßtdie Berechnung von xz-Projektionsvektoren. 20 stellt die Berechnung von Projektionsvektorendar. Wie es in 20 gezeigtist, wird der Projektionsvektor ĉ0,1 derLänge kz berechnet durch Summieren der Werte aller Datenspeichereinheitenin der xz-Ebene mit der y-Achsenkoordinate1 2002 und Plazieren der Summen in den Vektor ĉ0,1. Anders ausgedrückt, für jede spezielle z-Achsenkoordinateenthältdie Datenspeichereinheit des Projektionsvektors ĉ0,1 miteiner speziellen z-Achsenkoordinatez die Summe aller Datenspeichereinheiten in der xz-Ebene 2002 mitder z-Achsenkoordinate z. Gleichartig dazu stellt der Projektionsvektor ĉ0,2 2004 die Summe aller z-Zeilenin der xz-Scheibe dar, mit der y-Achsenkoordinate2 mit x-Achsenkoordinaten zwischen 1 und rx – 1. 21 stellt die Verwendungder berechneten Projektionsvektoren zum Erzeugen von z-Zeilen für die Speicherungin dem dreidimensionalen Datenspeichervolumen V' dar. Wie es in 21 gezeigt ist, wird die entsprechendez-Zeile von dem dreidimensionalen Datenspeichervolumen V 2102 vondem berechneten Projektionsvektor 2104 subtrahiert unddas Ergebnis wird zu kz Informationselementenaddiert, die von dem Eingangsstrom 2106 erhalten werden.Der resultierende Vektor wird codiert (auf den Zeilen 38 und 45der Routine „Codieren") durch den systematischenlinearen Code Cz zum Erzeugen eines Codewortvektors 2108,von dem der Projektionsvektor subtrahiert wird, der in dem dreidimensionalenDatenspeichervolumen V' gespeichertist, in einer z-Zeile mit der x-Achsenkoordinate 0 und der y-Achsenkoordinategleich der y-Achsenkoordinate der entsprechenden z-Zeile von demdreidimensionalen Datenspeichervolumen V 2102, subtrahiertvon dem berechneten Projektionsvektor.
    [0077] Wiees in 22 gezeigt ist,führt derAbschluß derFor-Schleifen derZeilen 33 – 39zum Auffüllender rechtesten yz-Scheibe 2202, außer der ersten z-Zeile in deryz-Scheibe, desdreidimensionalen Datenspeichervolumens V'. Die Ausführung der For-Schleife derZeilen 40 – 46führt zumSpeichern von z-Zeilen in der untersten horizontalen xz-Scheibedes dreidimensionalen Datenspeichervolumens V', das Codewörter des systematischen linearenBlockcodes Cz darstellt. Am Ende der Ausführung derFor-Schleife der Zeilen 40 – 46 enthält das dreidimensionaleDatenspeichervolumen V' yz-Scheibenmit x-Koordinaten zwischen 0 und rx – 1 undxz-Scheiben zwischen y-Achsenkoordinaten von 0 bis ry – 1. Wiees in 23 gezeigt ist,enthalten diese äußerstenz-Zeilen des dreidimensionalen Datenspeichervolumens V', wie z. B. die äußerste z-Zeile 2303,kz Klartextinformationssymbole und rz 2304 Paritätsprüfungssymbole (in 23 schraffiert), und dieinneren yz-Scheiben und xz-Scheibenenthalten z-Zeilen mit k'z Klartextinformationssymbolen 2306 undr'z Paritätsprüfungssymbolen 2308.
    [0078] Schließlich werdenin den verschachtelten For-Schleifen der Zeilen 47 – 51 diez-Zeilen des dreidimensionalen Datenspeichervolumens V' und V zusammenaddiertund in dem dreidimensionalen Datenspeichervolumen V gespeichert. 24 stellt den Betrieb derverschachtelten For-Schleifen der Zeilen 47 – 51 dar. 25 stellt das Endergebnis der Codierungsoperationdar, die durch die Routine „Codieren" ausgeführt wird. Wiees in 25 gezeigt ist,enthältdie großeMehrheit von Datenspeichereinheiten in dem dreidimensionalen DatenspeichervolumenV 100 Klartextinformationssymbole, nicht schraffiert in 25. Nur die xy-Scheibe mit derz-Achsenkoordinate „0" 2502, einekleine vertikale Region von Paritätsprüfungssymbolen 2504 undeine gleichermaßenkleine horizontale Region von Paritätsprüfungssymbolen (nicht sichtbarin 25) sind in dem dreidimensionalenDatenspeichervolumen V enthalten.
    [0079] Nachfolgendwird die Routine „Decodieren" beschrieben. DieseRoutine wird verwendet, um zu bestimmen, ob Fehler, die durch denTyp-1- und Typ-2-Ausfallmodus erzeugt wurden, die oben beschriebensind, in einem empfangenen oder wiedergewonnenen dreidimensionalenDatenspeichervolumen Γ ∼ aufgetreten sind oder nicht. Die Routine „Decodieren" liefert ein Verfahrenzum Decodieren von Daten in einem dreidimensionalen Datenspeichervolumen Γ ∼,das eine Anzahl von Datenspeichereinheiten umfaßt. Das Verfahren umfaßt folgendeSchritte: Berechnen von Anfangssyndromvolumen unter Verwendung vonTransponierten von Paritätsprüfungsmatrizen,die einem Produktcode zugeordnet sind, der verwendet wird, um Datenwertein dem dreidimensionalen Datenspeichervolumen Γ ∼ zu speichern; Berechnenvon Sekundärsyndromvolumenvon den Anfangssyndromvolumen durch Anlegen eines Decodierers anVektoren in den Anfangssyndromvolumen; Bestimmen einer Anzahl vonEbenenverfälschungsfehlernin dem dreidimensionalen Datenspeichervolumen Γ ∼ von den Sekundärsyndromvolumenund von einer Ebene von Γ ∼; und, wenn ein Ebenenverfälschungsfehlererfaßtwird, Korrigieren des Ebenenverfälschungsfehlersdurch Berechnen eines Fehlervolumens und Subtrahieren des Fehlervolumensvon dem dreidimensionalen Datenspeichervolumen Γ ∼.
    [0080] DieRoutine „Decodieren" umfaßt die folgendenErklärungen:
    [0081] DieKonstante t ist, wie es oben in Zeile 4 erklärt ist, die Anzahl von Kreuzfehlern,die die beschriebene Codiertechnik erfassen und korrigieren soll,durch das beschriebene Ausführungsbeispielder vorliegenden Erfindung. Die Syndromvolumen Sx, Ŝx, ΔSx, Sy, Ŝy und ΔSy, oben in Zeile 6 – 9 erklärt, sind alle Volumen von Datenspeichereinheiten,mit Abmessungen, die in den obigen Erklärungen spezifiziert sind, dieverwendet werden, um berechnete Syndrome für das empfangene dreidimensionaleDatenspeichervolumen Γ ∼ zu speichern, oben in den Zeilen 17 – 18 erklärt. Dasdreidimensionale Datenspeichervolumen E, das oben in den Zeilen10 – 11erklärtist, speichert ein Fehlervolumen, das ein 3-D-analog zu dem obenbeschriebenen Fehlervektor e ist. Der Satz L, der oben in den Zeilen12 – 16erklärtist, enthältz-Indizes von xy-Scheiben des empfangenen dreidimensional Datenspeichervolumens Γ ∼,von denen bestimmt ist, daß dieselbenFehler enthalten. Der Satz L verwendet Baugliedsfunktionen „Size", „getFirst" und „getNext" zum Berichten derAnzahl von enthaltenen z-Indizes und zum Zugreifen auf die enthaltenenz-Indizes. Eine Ebene von Zellen mit den Abmessungen nx malny wird als Zellarray „S" auf den Zeilen 19 – 20 erklärt. DiesesZellarray wird zum Summieren von z-Ebenen von Γ ∼ verwendet. Die DecodiererD1x, D1y, D1z, DtZ, D1'z undDt'z,die oben in den Zeilen 21 – 33erklärt sind,sind lineare Blockdecodierer, die den systematischen linearen Blockcodierernentsprechen, die in der oben beschriebenen Routine „Codieren" verwendet werden.Diese Decodierer sind in den begleitenden Kommentaren in den obigenErklärungenbeschrieben. In Zeile 34 sind Ganzzahlen x, y und z für die Verwendung inder Routine „Decodieren" erklärt. DieFunktion „getData", die oben in derZeile 35 erklärtist, erhältcodierte Informationselemente von einer Datenspeicherungs- oderDatenübertragungsquelleund plaziert dieselben in das dreidimensionale Datenspeichervolumen Γ ∼.Die Funktion „error", die oben in Zeile37 erklärtist, berichtet Decodierausfälle.Die Funktion „output", die oben in Zeile38 erklärtist, gibt korrigierte codierte Informationssymbole an einen Ausgangsstromaus.
    [0082] DieRoutine „Decodieren" verwendet die SubroutinecomputeE, die nachfolgend geliefert wird:
    [0083] DieseSubroutine berechnet ein Fehlervolumen xy-Scheibe Ez,das die beiden Matrixgleichungen erfüllt, die in Zeile 4 und 5 derRoutine geliefert werden. H T / x und H T / y werden erhalten durch Transponierender ParitätsprüfungsmatrizenHx und Hy für die systematischenlinearen Blockcodes Cx und Cy,die in der oben beschriebenen Routine „Codieren" verwendet werden. Das Berechnen einerFehlervolumen-xy-Scheibe,die die beiden Beschränkungsgleichungenerfüllt,ist ein gut bekanntes mathematisches Problem bei Fehlersteuercodierungund Decodierung und verschiedene gut bekannte Techniken können voneinem Durchschnittsfachmann auf diesem Gebiet geliefert werden.Diese Berechnung umfaßtdas Verwenden der Decodierer D1x und D1y. Dann berechnet D1x vonjeder x-Zeile in ΔSxz die jeweilige x-Zeile in Ez.Dann berechnet D1y von jeder y-Zeile in Ŝyz die jeweilige y-Zeile in Ez.Mit Bezugnahme auf 4 lasseEz die xy-Scheibe sein, die die Kreuzstrukturin dieser Figur enthält,wobei diese Struktur als eine Fehlerstruktur angesehen wird. Dajede x-Zeile in Ez, außer der x-Zeile 402 höchstenseinen Fehler enthält,rekonstruiert der Decodie rer D1X alle Einträge der y-Zeile 404 inEz außermöglicherweise 406,dennoch kann derselbe die x-Zeile 402 falsch decodieren.Dies läßt nur eineverfälschtex-Zeile in Ez, x-Zeile 402, übrig, diedann zu D1y korrigiert wird.
    [0084] DerHauptkörperder Routine „Decodieren" folgt:
    [0085] Zunächst werdenauf der obigen Zeile 3 die empfangenen oder wiedergewonnen codiertenInformationen erhalten und in das dreidimensionale Datenspeichervolumen Γ ∼ plaziert, über einenAufruf zu der Routine getData. Nachfolgend werden in der For-Schleifeder Zeilen 4 – 8die beiden Anfangssyndromvolumen Ŝxz und Ŝyz berechnet durch Matrixmultiplikation vonaufeinanderfolgenden xy-Scheiben in dem dreidimensionalen Datenspeichervolumen Γ ∼ durchdie Transponierten der ParitätsprüfungsmatrizenHx und Hy für die systematischenlinearen Blockcodes Cx und Cy,die in der oben beschriebenen Routine „Codieren" verwendet werden. 26 stellt die Berechnung des Syndromvolumens Ŝx dar. Jede xy-Scheibe, wie z. B. die xy-Scheibe 2602 indem dreidimensionalen Datenspeichervolumen Γ ∼ 2604 wird durchdie nx mal rx Transponierteder ParitätsprüfungsmatrixHx fürden Code Cx 2606 multipliziert,um eine ny mal rx xy-Scheibe 2608 indem Syndromvolumen Sx 2610 zu erzeugen. 27 stellt auf ähnlicheWeise wie 26 die Berechnungdes Syndromvolumens Sy dar.
    [0086] Aufder Zeile 9 ist das Fehlervolumen E eingestellt, um den Wert „0" in allen Datenspeichereinheiten zuenthalten. Dann werden die sekundären Syndromvolumen aus denAnfangssyndromvolumen berechnet, durch Anlegen eines Decodierersan die Vektoren in den Anfangssyndromvolumen. In der For-Schleife der Zeilen10 – 13werden z-Zeilen fürdas Syndromvolumen Sx berechnet durch Decodierenentsprechender z-Zeilen vondem Syndromvolumen Sx. Gleichartig dazuwerden z-Zeilen des Syndromvolumens Sy berechnetdurch Decodieren entsprechender z-Zeilen des Syndromvolumens Sy in der For-Schleife der Zeilen 14 – 17. Inder Zeile 19 wird der Satz L initialisiert, um keine z-Koordinatenzu enthalten. Nachfolgend wird in der For-Schleife der Zeilen 21 – 24 jedexy-Scheibe in den Syndromvolumen Sx undSy untersucht, um verfälschte xy-Scheiben zu erfassen,und jede Erfassung einer verfälschtenxy-Scheibe in einer z-Achsenkoordinate z führt dazu, daß die z-Achsenkoordinatez in den Satz L plaziert wird. Die Anzahl von Ebenenverfälschungsfehlernkann auf der Basis der Anzahl von z-Achsenkoordinaten, die in denSatz L plaziert werden, bestimmt werden.
    [0087] Inder Zeile 25 bestimmt die Routine „Decodieren", ob in der For-Schleifeder Zeile 21 – 24irgendwelche Fehler erfaßtwurden. Falls dies der Fall ist, dann stellt auf der Zeile 27 dieRoutine „Decodieren" das ZellenarrayS ein, um 0 Werte zu enthalten, und summiert dann in der For-Schleifeder Zeilen 28 – 31die xy-Scheiben von Γ ∼ in S. Nachfolgend bestimmt die Routine „Decodieren" in Zeile 32, obirgendwelche Paritätsfehlerin dem dreidimensionalen Datenspeichervolumen Γ ∼ vorliegen oder nicht,angezeigt durch Nicht-Null-Wertein S. Falls dies der Fall ist, wird, falls der Wert von t 1 ist,ein Decodierfehler auf der Zeile 36 zurückgesendet und die Routine „Decodieren" endet auf der Zeile37. Wenn t 1 ist, könnenkeine Fehler korrigiert werden. Nachfolgend werden in den verschachteltenFor-Schleifen derZeilen 39 – 43z-Zeilen der Syndromvolumen Ŝx und Ŝy geprüft,um Fehler zu erfassen, und falls Fehler gefunden werden, werdendie z-Achsenkoordinaten der xy-Scheibenin dem Satz L gespeichert. Falls der Satz L nun eine Größe aufweist,die sich von 1 unterscheidet, wie es durch die Routine „Decodieren" in Zeile 44 erfaßt wird,dann wird ein Fehler auf der Zeile 46 zurückgesendet und die Routine „Decodieren" endet in der Zeile47. Die Beendigung ist in diesem Fall angemessen, weil, wie es obenerörtertwurde, nicht mehr als eine verfälschtexy-Scheibe durch die Fehlersteuercodier- und Decodiertechnik korrigiertwerden kann, die ein Ausführungsbeispielder vorliegenden Erfindung darstellt. Andernfalls, wenn es keineerfaßtenFehler gibt, wie es oben in der Zeile 25 bestimmt wird, dann können diecodierten Informationssymbole in dem dreidimensionalen Datenspeichervolumen Γ ∼ ausgegebenwerden, in der Zeile 52, und die Routine „Decodieren" endet auf der Zeile53. Es ist anzumerken, daß dieKlartextinformationssymbole von den ausgegebenen codierten Informationssymbolenextrahiert werden können,durch einfaches Extrahieren der Klartextinformationssymbole in einerReihenfolge entgegengesetzt zu der Reihenfolge, in der sie während demCodieren durch die Routine „Codieren" gespeichert wurden.
    [0088] Nachfolgendbestimmt die Routine „Decodieren", ob ein einzelnerFehler erfaßtwurde, in der Zeile 56. Falls dies der Fall ist, wurde ein einzelnerEbenenverfälschungsfehlererfaßtund der Ebenenverfälschungsfehlerkann korrigiert werden durch Berechnen eines Fehlervolumens undSubtrahieren des Fehlervolumens von dem dreidimensionalen Datenspeichervolumen Γ ∼.Die xy-Scheibe in dem Fehlervolumen E kann berechnet werden durchSummieren aller xy-Scheiben in dem dreidimensionalen Datenspeichervolumen Γ ∼,und das Fehlervolumen kann von dem dreidimensionalen Datenspeichervolumen Γ ∼ berechnetund ausgegeben werden in der Zeile 59. Falls es mehr als einen undweniger oder gleich t erfaßteFehler gibt, wie es in Zeile 61 bestimmt wird, dann beendet dieRoutine „Decodieren" in den For-Schleifender Zeilen 63 – 67und 68 – 72die Berechnung der Syndromvolumen Sx undSy durch Decodieren entsprechender z-Zeilender Syndromvolumen Ŝx und Ŝy. Dann berechnet die Routine „Decodieren" in den Zeilen 73und 74 die Differenzsyndromvolumen ΔSx und ΔSy durch Subtrahieren der berechneten Anfangssyndromvolumenvon den berechneten sekundärenSyndromvolumen. Dann berechnet die Routine „Decodieren" in der while-Schleifeder Zeilen 76 – 80xy-Scheiben des Fehlervolumens E und gibt schließlich das Ergebnis des Subtrahierensdes Fehlervolumens E von dem dreidimensionalen Datenspeichervolumen Γ ∼ aus.Falls es jedoch mehr als t Fehler gibt, oder anders ausgedrückt, dieAnzahl von Fehlern die bestimmten Begrenzungen der Fehlerkorrekturtechnik überschreiten,die ein Ausführungsbeispielder vorliegenden Erfindung darstellt, wird ein Fehler in der Zeile83 zurückgesendet.
    [0089] Obwohldie vorliegende Erfindung bezüglicheines speziellen Ausführungsbeispielsbeschrieben wurde, ist nicht beabsichtigt, daß die Erfindung auf diesesAusführungsbeispielbegrenzt ist. Modifikationen innerhalb der Wesensart der Erfindungsind füreinen Fachmann auf diesem Gebiet offensichtlich. Beispielsweise kanndas Verfahren der vorliegen den Erfindung auf eine beinahe unbegrenzteAnzahl von Weisen implementiert werden, unter Verwendung jeder einergroßenVielzahl von Programmiersprachen und einer beinahe unbegrenztenAnzahl von unterschiedlichen Steuerstrukturen, modularen Organisationenund anderen solchen Charakteristika. In speziellen Fällen können bestimmteEffizienzen erhalten werden durch Kurzschließen von For-Schleifen und durchMultiplizieren und anderweitiges Verarbeiten von Teilmatrizen anstattvon vollen Matrizen. Die Techniken der vorliegenden Erfindung können andreidimensionale Datenspeichervolumen mit vielen unterschiedlichenAbmessungen angelegt werden, die Elemente von einer beinahe unbegrenztenAnzahl von unterschiedlichen Feldtypen enthalten. Eine große Vielzahlvon geeigneten systematischen linearen Blockcodierern und entsprechendenDecodierern könnendurch die vorliegende Erfindung verwendet werden. Selbstverständlich kanndie Ausrichtung der logischen x-, y- und z-Achsen und der anderenKomponenten und Teilkomponenten der dreidimensionalen Datenspeichervolumenbeliebig bezüglichdes physikalischen Datenspeichermediums ausgerichtet sein. SolltenzusätzlicheFehlererfassungs- und Korrekturfähigkeitenbenötigt werden,könnenalternative Verfahren innerhalb des Schutzbereichs der vorliegendenErfindung entwickelt werden. Beispielsweise können zwei oder mehr xy-Scheibenfehler korrigiertwerden, wenn eine größere Anzahlvon Paritätsprüfungssymbolenverwendet wird. Obwohl Verfahren, die Ausführungsbeispiele der vorliegendenErfindung darstellen, oben beschrieben sind, umfaßt die vorliegendeErfindung verschiedene Softwareimplementierungen dieser Verfahrenund Computersysteme, die diese Verfahren verwenden, um Informationenin dreidimensionale Speichervolumen zu codieren.
    权利要求:
    Claims (13)
    [1] Verfahren zum Codieren von Daten in ein dreidimensionalesDatenspeichervolumen (100), das eine Anzahl von Datenspeichereinheiten(102) umfaßt,wobei das Verfahren folgende Schritte umfaßt: Empfangen einer Datensequenz;und Codieren der Datensequenz unter Verwendung eines linearenProduktcodes (802, 804–806) zum Codieren vonDaten (902, 1104) in Codearrays von Datenwerten(1002), und Verwenden von zwei linearen Blockcodes (704)zum Codieren von Daten (1702, 2106) in Vektorenvon Datenwerten (1708, 2108).
    [2] Verfahren gemäß Anspruch1, bei dem das Empfangen einer Datensequenz ferner das Empfangeneiner geordneten Sequenz von Datenwerten umfaßt, wobei jeder Datenwert (502)ein Element ist, das von einem Feld ausgewählt ist.
    [3] Verfahren gemäß Anspruch1 oder 2, das ferner das Speichern des codierten Datenblocks indem dreidimensionalen Datenspeichervolumen (150) umfaßt, so daß die ursprünglich empfangenenDaten in Klartextform in einem Teilvolumen (1302) des dreidimensionalenDatenspeichervolumens erscheinen.
    [4] Verfahren gemäß einemder Ansprüche1 bis 3, bei dem die Codearrays (1002) als Ebenen in demdreidimensionalen Datenspeichervolumen gespeichert sind.
    [5] Verfahren gemäß einemder Ansprüche1 bis 4, bei dem die Vektoren (1708, 2108) inDatenspeichereinheiten gespeichert sind, die bereits Codearraydatenwerteenthalten.
    [6] Verfahren gemäß Anspruch4 oder 5, bei dem die Datenspeichereinheiten (102) desdreidimensionalen Datenspeichervolumens (100) bezüglich derdrei Koordinatenachsen x, y und z (106, 108, 110)indexiert sind, mit Datenspeicherindizes, die von 0 bis nx – 1in einer x-Richtung, 0 bis ny – 1 in einery-Richtung und 0bis nz – 1in einer z-Richtung reichen; und wobei die linearen Blockcodesfolgende Merkmale umfassen: einen Produktcode CxCy (802, 804–806) , der kxky Datenwerte in ein Codearray von Abmessungennxny mit rxry Paritätsprüfungswertencodiert, einen linearen Blockcode Cz (704),der kz Datenwerte (1706) in einenVektor (1708) mit der Längenz mit rz = nz – kz Paritätsprüfungswertencodiert, und einen linearen Blockcode C'z (704),der k'z Datenwerte(2106) in einen Vektor (2108) der Länge nz mit r'z Paritätsprüfungswertencodiert.
    [7] Verfahren gemäß einemder Ansprüche4 bis 6, bei dem kxky (nz – 1)Datenwerte in nz – 1 Ebenen (1002)codiert werden, senkrecht zu der z-Richtung beginnend mit der Ebenemit der z-Achsenkoordinate 0; wobei k'z(nxny – nx – ny + 1 – kxky) Datenwerte inEbenen (1802) codiert werden, die senkrecht zu der x-Richtung sind, mitx-Achsenkoordinaten von zwischen 1 und rx – 1 undEbenen (2002) senkrecht zu der y-Richtung mit y-Achsenkoordinaten vonzwischen 1 und ry – 1; und wobei kz(nx + ny +1) Datenwerte codiert werden in eine Ebene (2202) senkrechtzu der x-Richtung mit der x-Achsenkoordinate0 und einer Ebene senkrecht zu der y-Richtung mit der y-Achsenkoordinate0.
    [8] Computerbefehle, die das Verfahren gemäß einemder Ansprüche1 bis 7 implementieren, die in einem computerlesbaren Medium codiertsind.
    [9] Computer, der die Computerbefehle ausführt, diedas Verfahren gemäß einemder Ansprüche1 bis 8 implementieren, um Datenwerte in ein dreidimensionales Datenspeichervolumen(100) zu codieren.
    [10] Dreidimensionales Datenspeichervolumen, das Datenenthält,die durch das Verfahren gemäß einem derAnsprüche1 bis 8 codiert werden.
    [11] Verfahren zum Decodieren von Daten in einem dreidimensionalenDatenspeichervolumen Γ ∼ (2604), das eine Anzahl von Datenspeichereinheitenumfaßt,wobei das Verfahren folgende Schritte umfaßt: Berechnen von Anfangssyndromvolumen(2610) unter Verwendung von Transponierten von Paritätsprüfungsmatrizen(2606), die einem Produktcode (802, 804, 806)zugeordnet sind, der verwendet wird, um Datenwerte in dem dreidimensionalenDatenspeichervolumen Γ ∼ zu codieren; Berechnen von Sekundärsyndromvolumenaus den Anfangssyndromvolumen durch Anlegen eines Decodierers anVektoren in den Anfangssyndromvolumen; Bestimmen einer Anzahlvon Ebenenverfälschungsfehlernin dem dreidimensionalen Datenspeichervolumen Γ ∼ von dem sekundären Syndromvolumenund von einer Ebene von Γ ∼; und wenn ein Ebenenverfälschungsfehlererfaßtwird, Korrigieren des Ebenenverfälschungsfehlersdurch Berechnen eines Fehlervolumens und Subtrahieren des Fehlervolumensvon dem dreidimensionalen Datenspeichervolumen Γ ∼.
    [12] Verfahren gemäß Anspruch11, das ferner das Berechnen von Differenzsyndromvolumen aus denAnfangssyndromvolumen und den Sekundärsyndromvolumen umfaßt, dieunter Verwendung eines linearen Blockdecodierers abgeschlossen werden,und Korrigieren von Kreuzfehlern (402, 404, 406)in dem dreidimensionalen Datenspeichervolumen Γ ∼ durch Berechnen einesFehlervolumens aus den Differenzsyndromvolumen und Subtrahierendes Fehlervolumens von dem dreidimensionalen Datenspeichervolumen Γ ∼.
    [13] Verfahren gemäß Anspruch12, bei dem die Datenspeichereinheiten des dreidimensionalenDatenspeichervolumens Γ ∼z bezüglich derdrei Koordinatenachsen x, y und z (106, 108, 110)indexiert werden, mit Datenspeicherindizes, die von 0 bis nx – 1in einer x-Richtung, 0 bis ny – 1 in einery-Richtung und 0 bis nz – 1 in einer z-Richtung reichen; wobeiEbenen der Anfangssyndromvolumen Ŝx (2608)und Ŝy senkrecht zu der z-Richtung von Transponierten derParitätsprüfungsmatrizen(2606) berechnet werden durch Ŝxz = Γ ∼zH T / x und durch Ŝyz = Γ ∼zH T / y; wobei sekundäre Syndromvolumen Sx und Sy von denAnfangssyndromvolumen berechnet werden durch Decodieren von Vektorenin Sx und Sy inder z-Richtung unter Verwendung eines linearen BlockdecodierersDtz; wobei eine Anfangsanzahl von Ebenenverfälschungsfehlernbestimmt wird durch die Anzahl von Ebenen in Sx undSy senkrecht zu der z-Richtung, die Nicht-Null-Werte enthält; und wobei,wenn die Ebene von Γ ∼z senkrecht zu der z-Richtung mit derz-Achsenkoordinate 0 nicht Null ist, die Anzahl von Ebenenverfälschungsfehlernferner die Anzahl von Nicht-Null-Vektoren in der z-Richtung von Ŝx und Ŝy umfaßt,decodiert durch den linearen Blockdecodierer D1'z.
    类似技术:
    公开号 | 公开日 | 专利标题
    Blaum et al.1996|MDS array codes with independent parity symbols
    Plank2009|The raid-6 liber8tion code
    Gluesing-Luerssen et al.2006|Strongly-MDS convolutional codes
    Huffman et al.2010|Fundamentals of error-correcting codes
    US8522122B2|2013-08-27|Correcting memory device and memory channel failures in the presence of known memory device failures
    US4410989A|1983-10-18|Bit serial encoder
    ES2445116T3|2014-02-28|Descodificación de códigos de reacción en cadena por inactivación
    US4949342A|1990-08-14|Code error detecting method
    US6560747B1|2003-05-06|Error counting mechanism
    JP2580304B2|1997-02-12|デ−タ修正方法および装置
    KR100856129B1|2008-09-03|오정정 확률을 줄이는 에러 정정 회로, 그 방법 및 상기회로를 구비하는 반도체 메모리 장치
    JP3727938B2|2005-12-21|Ｌｄｐｃ復号化装置及びその方法
    JP5620973B2|2014-11-05|Search for optimum threshold in analog memory cells
    JP3328093B2|2002-09-24|エラー訂正装置
    US6438724B1|2002-08-20|Method and apparatus for deterministically altering cyclic redundancy check information for data storage
    US8874995B2|2014-10-28|Partial-maximum distance separable | erasure correcting codes for storage arrays
    Cross et al.2007|A comparative code study for quantum fault-tolerance
    US5099482A|1992-03-24|Apparatus for detecting uncorrectable error patterns when using Euclid&#39;s algorithm to decode Reed-Solomon | codes
    Gibson et al.1989|Coding techniques for handling failures in large disk arrays
    Cassuto et al.2010|Codes for asymmetric limited-magnitude errors with application to multilevel flash memories
    US7103825B2|2006-09-05|Decoding error-correcting codes based on finite geometries
    US20140380114A1|2014-12-25|Data encoding for data storage system based on generalized concatenated codes
    US5226043A|1993-07-06|Apparatus and method for data error detection and correction and address error detection in a memory system
    US8645799B2|2014-02-04|Storage codes for data recovery
    US7716566B2|2010-05-11|Data error control
    同族专利:
    公开号 | 公开日
    US7206987B2|2007-04-17|
    US20040221220A1|2004-11-04|
    JP2004334845A|2004-11-25|
    引用文献:
    公开号 | 申请日 | 公开日 | 申请人 | 专利标题
    法律状态:
    2004-12-09| OP8| Request for examination as to paragraph 44 patent law|
    2006-04-27| 8130| Withdrawal|
    优先权:
    申请号 | 申请日 | 专利标题
    [返回顶部]