DE69429525T2

DE69429525T2 - Programmierbarer redundanz/syndromgenerator

Info

Publication number: DE69429525T2
Application number: DE69429525T
Authority: DE
Inventors: Neal Glover; P. Zook
Original assignee: Cirrus Logic Inc
Current assignee: Cirrus Logic Inc
Priority date: 1993-09-21
Filing date: 1994-09-20
Publication date: 2002-07-18
Anticipated expiration: 2014-09-21
Also published as: EP0720759A4; KR960705272A; JPH09505952A; WO1995008803A3; EP0720759A1; US5822337A; EP0720759B1; SG46513A1; DE69429525D1; WO1995008803A2; US5473620A

Description

GEBIET DER ERFINDUNG

Diese Erfindung bezieht sich allgemein auf digitale Datenkommunikationssysteme und insbesondere auf die Codierung und Decodietung von Fehlerkorrekturcodes.

HINTERGRUND DER ERFINDUNG

Bei einem digitalen Datenkommunikationssystem (mit Speicherung und Rückgewinnung von optischen oder magnetischen Medien) ist es notwendig, um die Übertragungsrate von Informationen zu erhöhen und zur gleichen Zeit die Fehlerrate beliebig niedrig zu machen, ein Fehlersteuersystem zu verwenden. Für feste Signalrauschabstände und feste Bandbreiten können Verbesserungen durch die Verwendung von Fehlerkorrekturcodes erzielt werden.
Mit einer Fehlerkorrekturcodierung werden die zu übertragenden oder zu speichernden Daten mathematisch verarbeitet, um zusätzliche Datensymbole zu erhalten, die Prüfsymbole oder Redundanzsymbole genannt werden. Die Daten und Prüfsymbole bilden zusammen ein Codewort. Nach der Übertragung oder Rückgewinnung wird das Codewort mathematisch verarbeitet, um Fehlersyndrome zu erhalten, die Information über Positionen und Werte von Fehlern enthalten.
Für viele Fehlerkorrekturcodes (z. B. Polynomcodes, wie beispielsweise, aber nicht begrenzt auf, Reed-Solomon -Codes) werden die Codewörter durch Anhängen eines Restpolynoms (Redundanzsymbole) an ein Datenpolynom gebildet, um das zusammengesetzte Polynom durch ein Generatorpolynom dividierbar zu machen. Das Restpolynom wird durch Dividieren des Datenpolynoms durch das Generatorpolynom und Behalten des Restpolynoms erhalten. Die Fehlersyndrome werden durch Dividieren des empfangenen Polynoms (ein Codewortpolynom, das ein ihm hinzuaddiertes Fehlerpolynom aufweisen kann) durch die einzelnen Faktoren des Generatorpolynoms erhalten.

STAND DER TECHNIK

Fig. 1 zeigt eine Schaltung, die Redundanzsymbole durch Durchführen einer Polynomdivision erzeugen kann.
Fig. 2 zeigt eine Mehrzahl von Dividierern erster Ordnung, wobei jeder eines der Fehlersyndrome erzeugen kann.

Einschränkungen des Stands der Technik

Ein Problem, das bei der Verwendung dieser Codes auftritt, ist die erhebliche Menge an Schaltungen, die bei Hochgeschwindigkeits-Implementierungen von Generatoren hoher Ordnung (die imstande sind, viele Fehler zu korrigieren) für die Redundanzsymbole und die Fehlersyndrome benötigt wird. Für Systeme, die die Fähigkeit benötigen, sowohl die Codierung als auch Decodierung durchzuführen, obgleich nicht gleichzeitig, ist es eine wünschenswerte Eigenschaft, eine Schaltung aufzuweisen, die imstande ist, beide Sätze von Symbolen zu erzeugen. Es ist ebenfalls eine wünschenswerte Eigenschaft für den Codierer, programmierbar zu sein, um imstande zu sein, Codes unterschiedlicher Ordnung (Codewörter mit unterschiedlichen Anzahlen von Redundanz-Bytes) zu erzeugen. Das gewöhnliche Verfahren weist keine dieser Eigenschaften auf.
Das US-Patent Nr. 4 777 635 mit dem Titel "Reed-Solomon Code Encoder and Syndrome Generator Circuit", erteilt an Neal Glover, offenbart eine Schaltung, die sowohl Redundanz- als auch Syndromsymbole erzeugen kann, jedoch nicht ordnungs-programmierbar ist.
Der Berlekamp-Welch-Algorithmus ist ein allgemeiner Decodierungs-Algorithmus, der keine Syndrome sondern stattdessen die Codiererschaltung verwendet, um einen Rest aus den empfangenen Polynom zu berechnen. Der Algorithmus ist jedoch etwas komplizierter als derjenige, der Syndrome verarbeitet, und er ist nicht ordnungs-programmierbar. Es ist ferner möglich, den Rest in Syndrome umzuwandeln, wobei dies jedoch eine erhebliche zusätzliche Schaltungsanordnung erfordert.
Das US-Patent Nr. 5 325 373, erteilt an Iwamura u. a., mit dem Titel "Apparatus for Encoding and Decoding Reed-Solomon Code" offenbart ein Verfahren zum Erzeugen von Redundanzsymbolen während des Codiervorgangs eines EC-Codeworts. Der Codiervorgang wird dargestellt als:
R(x) = D(x)·xn-k mod(G(x))
Das bei Iwamura offenbarte Verfahren zum Implementieren dieser Gleichung wird ausgedrückt als:
Z0 = I(x)
Zi-gm·Z'i-1 + Zm·g'(x) (I-1, ..., k); P(x) = Zk (2)
wobei I(x) das eingegebene Datenpolynom, g(x) das Generatorpolynom und P(x) das Restpolynom (R(x)oben) ist. Die Schaltung zum Implementieren der obigen Gleichung (2) wird von Iwamura in Fig. 92 offenbart.

ZUSAMMENFASSUNG DER ERFINDUNG

Es ist eine Aufgabe der vorliegenden Erfindung, die Größe der Schaltungsanordnung bei einer Hardware-Implementierung eines Fehlerkorrektur-Codierers/Decodierers zu verringern, indem eine einzige Schaltung verwendet wird, um Prüfsymbole während des Übertragungsvorgangs und ferner um Syndrome während eines Empfangsvorgangs zu erzeugen.
Eine weitere Aufgabe ist es, die Größe der Schaltungsanordnung bei einer Hardware-Implementierung eines Fehlerkorrektur-Codierers/Decodierers zu verringern, indem eine einzige Schaltung verwendet wird, um Prüfsymbole für Codewörter mit unterschiedlichen Anzahlen von Prüfsymbolen zu erzeugen.
Die oben erwähnten Aufgaben werden von der detailliert in den Ansprüchen 1 und 4 definierten Erfindung gelöst.

KURZBESCHREIBUNG DER ZEICHNUNGEN

Fig. 1 zeigt die vorbekannte Lösung zum Erzeugen von Redundanzsymbolen.
Fig. 2 zeigt die vorbekannte Lösung zum Erzeugen von Syndromen.
Fig. 3 stellt das Grundprinzip dar, das bei der vorliegenden Erfindung verwendet wird.
Fig. 4 zeigt ein Blockschaltbild der bevorzugten Ausführungsform der vorliegenden Erfindung.
Fig. 5 zeigt ein Blockschaltbild einer alternativen Ausführungsform der vorliegenden Erfindung.
Fig. 6 zeigt ein Blockschaltbild einer weiteren alternativen Ausführungsform der vorliegenden Erfindung.
Fig. 7 zeigt ein Blockschaltbild einer weiteren alternativen Ausführungsform der vorliegenden Erfindung.

AUSFÜHRLICHE BESCHREIBUNG DER ERFINDUNG

Diese Erfindung umfasst ein Verfahren und eine Einrichtung, die imstande sind, Redundanzsymbole und Syndrome zu erzeugen, und ordnungs-programmierbar sind. Die Theorie der Betriebsweise dieser Erfindung ist wie folgt: Polynomcodes bestehen aus Codewörtern, die Mehrfache eines Generatorpolynoms sind. Ein Codewort c(x) wird durch Dividieren eines Datenpolynoms D(x) eines Grades weniger als k durch ein Generatorpolynom g(x) eines Grades n-k gebildet, um ein Redundanzpolynom r(x) eines Grades weniger als n-k zu erhalten. Anhängen von r(x) an D(x) ergibt c(x) eines Grades weniger als n (d. h. es gibt k Datensymbole und n-k Redundanzsymbole und n Gesamtsymbole, wobei jedes Symbol eine vorbestimmte Mehrzahl von Bits m aufweist).
g(x) = (x + rj)
r(x) = D(x)·xn-kmod (g(x))
c(x) = D(x)·xn-k + r(x)
Die folgende Erläuterung zeigt, dass es möglich ist, D(x) in eine Kaskade von Dividieren erster Ordnung zu speisen (wobei jeder Dividierer durch einen Faktor (x + rj) dividiert), um r(x) zu erzeugen. Diese Dividierer erster Ordnung können dann verwendet werden, um Syndrome während Lesevorgängen (Decodierung) zu erzeugen.
Fig. 3 zeigt eine Kaskade von Polynomdividierern erster Ordnung gefolgt von einer Kaskade von Polynommultiplizierern erster Ordnung. Jeder Polynomdividierer ist aus einem Register 200, einem Konstanten-Multiplizierer 201 und einem Addierer 202 aufgebaut, die jeweils ein Symbol breit sind. Die Ausgabe jedes Polynomdividierers ist das mit x multiplizierte und durch (x + rj) dividierte Eingangspolynom. Jeder Polynommultiplizierer multipliziert seine Eingabe mit (x + rj). Bei jedem Operationsschritt (gleichzeitiges Takten aller Register und Eingeben eines weiteren Symbols) stimmt die Ausgabe jedes Dividierers mit der Eingabe in den entsprechenden Multiplizierer überein, z. B. 203&sub0; stimmt mit 2131 überein. Ferner stimmt jedes Dividiererregister mit dem entsprechenden Multipliziererregister überein, z. B. Aj stimmt mit Bj überein. Die Ausgabe der Dividiererkaskade 203n-k-1 ist:
und
xn-kD(x)-q(x)·g(x) = xn-kD(x)mod (g(x))
daher
q(x) = xn-kD(x)-xn-kD(x)mod(g(x))/g(x)
Die Ausgabe der Multipliziererkaskade ist q(x)g(x). Die ersten k Glieder (Symbole), die an 203n-k-1 erscheinen, ist q(x), und die ersten k Glieder (Symbole), die an 213&sub0; erscheinen, ist D(x). Um den Rest von q(x)g(x) zu halten, wird die Eingabe in die Multipliziererkaskade durch das Gatter 214 auf Null gesetzt, und die Schaltung wird n-k mehrmals getaktet. Die Ausgabe der Multipliziererkaskade 213&sub0; während dieser Takte ist xn-kD(x)mod(g(x)), was die Reihe von Redundanzsymbolen in einem Polynomcode ist.

Implementierung

Da die Multipliziererregister in Fig. 3 immer mit den Dividiererregistern übereinstimmen, kann die Multipliziererkaskade verworfen werden, und während der letzten n-k Takte kann der Dividierer als eine Multipliziererkaskade zusammengeschaltet werden, um Redundanzsymbole zu hervorzubringen. Dies ist in Fig. 4 dargestellt. Dann, wenn REDUNDANZZEIT EIN ist, veranlassen die MUX 102 und 103, dass die Register und Konstantenmultiplizierer zusammengeschaltet werden, um eine Kaskade von Dividierern von links nach rechts zu bilden (die Addierer 106 addieren von links nach rechts). Wenn REDUNDANZZEIT AN ist, veranlassen die MUX 102 und 103, dass die Register und Konstantenmultiplizierer zusammengeschaltet werden, um eine Kaskade von Multiplizierern von rechts nach links zu bilden (die Addierer addieren von rechts nach links). Die Funktion der MUX 101 besteht darin, getrennte Dividierer (nicht in einer Kaskade) zur Syndromerzeugung zu bilden.
SCHREIBMODUS ist während eines Schreibvorgangs (Codierung) EIN. REDUNDANZZEIT ist für die ersten k Taktzeiten AUS, und die eingegangenen Daten-Bytes werden zu dem Ausgang des MUX 105 durchgeleitet. Für die letzten n-k Taktzeiten ist REDUNDANZZEIT EIN, und die Redundanzsymbole sind an dem Ausgang des MUX 105 vorhanden.
Während eines Lesevorgangs ist SCHREIBMODUS AUS und REDUNDANZZEIT ist AUS und das gesamte empfangene, aus Daten und Redundanz bestehende Polynom wird für n Taktzeiten eingegeben. Während der letzten Taktzeit sind die Syndrome an dem Ausgang des MUX 103 verfügbar.
Durch Halten der Rücksetz-Eingabe an einem Register während der Redundanzerzeugung auf EIN wird die entsprechende Wurzel für dieses Register aus der Redundanzberechnung weggelassen. Dies ermöglicht, dass die Auswahl von Wurzeln vollständig programmierbar ist, und ermöglicht insbesondere, dass die Anzahl von Wurzeln (Codeordnung) programmierbar ist.
Der in Fig. 4 gezeigte Generator ist für ein Reed-Solomon-Code (d. h. die Wurzeln, wie sie bei den konstanten Multiplizierern 104 gezeigt sind, sind aufeinanderfolgende Potenzen von Alpha, einer primitiven Wurzel des Feldes). Die Erfindung ist jedoch auf einen beliebigen Polynomcode mit einer beliebigen Auswahl von Wurzeln anwendbar. Die Rücksetzungen der Register sind "ORDNUNG< j", was das Auswahlkriterium für Reed-Solomon-Codes ist (d. h. ORDNUNG aufeinanderfolgende Wurzeln sind enthalten und der Rest wird weggelassen, wobei ORDNUNG die Anzahl von Wurzeln in dem Generator ist). Es kann jedoch ein beliebiges Auswahlkriterium verwendet werden.
Fig. 5 zeigt eine alternative Implementierung, bei der ein Satz von Multiplexern aus der Addiererkette von Fig. 4 entfernt und eine zweite Addiererkette hinzugefügt ist. Die obere Addiererkette 306 addiert nur von links nach rechts. (für Datenzeit) und die untere Addiererkette 302 addiert nur von rechts nach links (für Redundanzzeit). Dies ermöglicht einen schnelleren Betrieb auf Kosten von mehr Gattern (Austauschen von MUX gegen Addierer). Die Multiplexer 303 schalten zwischen einer Dividiererkaskade für Datenzeit oder einer Multipliziererkaskade für Redundanzzeit um. Die MUX 301 schalten zwischen einer Kaskade von Dividierern/Multiplizierern zur Codierung und getrennten Dividierern für die Syndromerzeugung um.
Fig. 6 zeigt eine alternative Implementierung, bei der der Satz von Multiplexern aus der oberen Addiererkette in Fig. 5 entfernt ist, wobei ihre Funktion des Ermöglichens einer Syndromerzeugung durch Aufnehmen des Satzes von Addierern 401 und eines MUX 407 durchgeführt wird. Während des Lesemodus ermöglicht der MUX 407, dass Lesedaten eingegeben werden, und die Addiererkette 401 wird freigegeben, die veranlasst, dass die Registerausgabe für jede Stufe zu der nächsten Stufe zweimal durch die Addierer 401 und 406 hinzugefügt wird. Dies koppelt wirksam jede Stufe, da in dem endlichen Feld von GF(2m) das Addieren eines Elements zu sich selber zu Null führt. Dies ermöglicht den schnellsten Betrieb auf Kosten von mehr Gattern (Austauschen von MUX gegen Addierer), wenn die Addiererkette 406 nicht länger irgendwelche Multiplexer enthält.
Fig. 7 zeigt eine alternative Implementierung, bei der die Multiplexer in Fig. 6 eliminiert wurden. Diese Abschnitte bleiben in der Dividiererkonfiguration während der Redundanz-Zeit, wobei jedoch der Eingang von Daten auf Redundanz durch MUX 505 und 507 umschaltet. Aufgrund der Löschung, die auftritt, wenn Elemente zu sich selbst addiert werden, weist das Addieren der Ausgabe der unteren Addiererkette, die gleich der Summe des Inhalts dieser Register ist, zu der Eingabe der oberen Addiererkette die gleiche Funktion auf und führt zu einem tatsächlichen Ändern der Konfiguration von Links-nach rechts-Dividierern zu Rechts-nach-links- Multiplizierern wie bei den anderen Implementierungen.
Während die bevorzugte Ausführungsform und verschiedene alternative Ausführungsformen der Erfindung offenbart und hier ausführlich beschrieben wurden, ist es für Fachleute offensichtlich, dass verschiedene Änderungen in Form und Detail darin durchgeführt werden können, ohne von dem Schutzumfang derselben abzuweichen.

Claims

1. Einrichtung zum Erzeugen von Redundanzsymbolen während der Codierung von aus Gruppen von binären Bits bestehenden Datensymbolen in Codeworte von Polynomcodes, wobei jedes Codewort c(x) gebildet wird durch Dividieren eines Datenpolynoms D(x) eines Grades von weniger als k durch ein Generatorpolynom g(x) eines Grades n-k, um ein Redundanzpolynom r(x) eines Grades weniger als n-k zu gewinnen, und durch Anhängen von r(x) an D(x), um c(x) eines Grades von weniger als n zu gewinnen, wobei jedes Symbol eine vorgegebene Mehrzahl von binären Bits m aufweist, gekennzeichnet durch:

eine Mehrzahl von Zellen, die ein Register (200), einen Endliches-Feld-Multiplizierer (201) und einen Addierer (202) aufweisen, wobei jede Zelle selektiv als Polynomdividierer erster Ordnung und als Polynommultiplizierer erster Ordnung verbindbar ist;

Mittel (102, 103) zum Zusammenschalten jeder Zelle derart, daß sie einen Polynomdividierer erster Ordnung bildet, und zum Koppeln der Polynomdividierer erster Ordnung miteinander derart, daß sie eine Kaskade von Polynomdividierern erster Ordnung bilden;

Mittel zum sequentiellen Eingeben von Datensymbolen für ein Codewort in die Kaskade der Polynomdividierer erster Ordnung;

Mittel (102, 103) zum Zusammenschalten jeder Zelle derart, daß sie einen Polynommultiplizierer erster Ordnung bildet, und zum Koppeln der Polynommultiplizierer erster Ordnung miteinander derart, daß sie eine Kaskade von Polynommultiplizierern erster Ordnung bilden, wobei die Register in der Kaskade der Polynommultiplizierer erster Ordnung in entgegengesetzter Reihenfolge im Vergleich zu ihrer jeweiligen Reihenfolge in der Kaskade von Polynomdividierern erster Ordnung geordnet sind; und

Mittel (214) zum Halten der Eingabe in die Multipliziererkaskade auf Null und zum Takten der Register, um die den Datensymbolen zugeordneten Redundanzsymbole hinauszutakten.

2. Einrichtung zum Erzeugen von Redundanzsymbolen während der Codierung von Datensymbolen und zum Erzeugen von Syndromen während der Decodierung von Codeworten, welche Fehler enthalten können, aufweisend die Einrichtung nach Anspruch 1 und ferner aufweisend:

Mittel zum Zusammenschalten jeder Zelle derart, daß sie einen separaten Polynomdividierer erster Ordnung bildet; und

Mittel zum Bereitstellen der Codeworte, die Fehler enthalten können, an die separaten Dividierer, um die empfangenen Codeworte durch das erzeugende Polynom zu dividieren, um eines der Syndrome zu erzeugen.

3. Die Einrichtung nach Anspruch 1, wobei das Register einer Zelle zurückgesetzt gehalten wird, wenn die Wurzel (root) der Zelle nicht in dem gewünschten Codewortgenerator enthalten sein soll.

4. Ein Verfahren zum Erzeugen von Redundanzsymbolen während der Codierung von aus Gruppen binärer Bits bestehenden Datensymbolen in Codeworte von Polynomcodes, wobei jedes Codewort c(x) gebildet wird, indem ein Datenpolynom D(x) eines Grades von weniger als k durch ein Generatorpolynom g(x) eines Grades von n-k dividiert wird, um ein Redundanzpolynom r(x) des Grades von weniger als n-k zu gewinnen, und indem r(x) an D(x) angehängt wird, um c(x) des Grades von weniger als n zu bilden, wobei jedes Symbol eine vorgegebene Mehrzahl von binären Bits m aufweist, gekennzeichnet durch die Schritte:

(a) Bereitstellen einer Mehrzahl von Zellen, die ein Register (200), einen Endliche-Felder-Multiplizierer (201) und einen Addierer (202) aufweisen, wobei jede Zelle selektiv als Polynomdividierer erster Ordnung und als Polynommultiplizierer erster Ordnung schaltbar ist;

(b) Schalten (102, 103) jeder Zelle derart, daß sie einen Polynomdividierer erster Ordnung bildet, und Koppeln der Polynomdividierer erster Ordnung miteinander derart, daß sie eine Kaskade von Polynomdividierern erster Ordnung bilden;

(c) Sequentielles Eingeben von Datensymbolen für ein Codewort in die im Schritt (b) gebildete Kaskade von Polynomdividierern erster Ordnung;

(d) Schalten (102, 103) jeder Zelle derart, daß sie einen Polynommultiplizierer erster Ordnung bildet, und Koppeln der Polynommultiplizierer erster Ordnung miteinander derart, daß sie eine Kaskade von Polynommultiplizierern erster Ordnung bilden, wobei die Register in der Kaskade der Polynommultiplizierer erster Ordnung in entgegengesetzter Reihenfolge im Vergleich zu ihrer jeweiligen Reihenfolge in der Kaskade der Polynomdividierer erster Ordnung geordnet werden; und

(e) Halten (214) der Eingabe in die Multipliziererkaskade auf Null und Takten der Register, um die den Datensymbolen des Schrittes (c) zugeordneten Redundanzsymbole hinauszutakten.

5. Das Verfahren zum Erzeugen von Redundanzsymbolen während der Codierung von Datensymbolen und zum Erzeugen von Syndromen während der Decodierung von Codeworten, welche Fehler enthalten können, umfassend die Schritte des Anspruchs 4 und ferner umfassend die Schritte:

(f) Schälten jeder Zelle zu einem m Bits breiten Addierer, wobei jede Zelle einen separaten Polynomdividierer erster Ordnung bildet; und

(g) Bereitstellen von Codeworten, die Fehler enthalten können, an die Dividierer des Schrittes (f), um das empfangene Codewort durch die Faktoren des erzeugenden Polynoms zu dividieren, um die Syndrome zu erzeugen.

6. Das Verfahren nach Anspruch 4, wobei die Addierer, die im Schritt (d) verwendet werden, die gleichen Addierer sind, wie sie im Schritt (b) verwendet werden.

7. Das Verfahren nach Anspruch 4, wobei die im Schritt (d) verwendeten Addierer sich von den im Schritt (b) verwendeten Addierern unterscheiden.

8. Das Verfahren des Erzeugens von Redundanzsymbolen während der Codierung von Datensymbolen und zum Erzeugen von Syndromen während der Decodierung von Codeworten, welche Fehler enthalten können, umfassend die Schritte des Anspruchs 4 und ferner umfassend die Schritte:

(f) Verbinden jeder Zelle mit einem Paar von m Bit breiten Addierern, so daß die Ausgabe jeder Zelle zu der Eingabe zu der nächsten Zelle zweimal addiert wird, wobei jede Zelle einen separaten Polynomdividierer erster Ordnung bildet; und

9. Das Verfahren nach Anspruch 4, wobei das rücksetzbare Register einer Zelle zurückgesetzt gehalten wird, wenn die Wurzel (root) der Zelle nicht in dem gewünschten Codewortgenerator enthalten sein soll.