-
1. Bereich der Erfindung
-
Die
vorliegende Erfindung bezieht sich im Allgemeinen auf Reed Solomon
Decoder, und insbesondere auf einen verbesserten Fehlerberechnungsprozessor
zum Berechnen der Fehlerstellen und Größen davon in großen Datenblöcken.
-
2. Beschreibung des Standes
der Technik
-
Eines
der wichtigsten Verfahren der Fehlerdetektion und Fehlerkorrektur
bei digitalen Datenübertragungs-
und -speichersystemen benutzt die Klasse der Fehlerkorrekturcodes,
bekannt als Reed Solomon Codes. Zwei derartige Reed Solomon Systeme
sind in dem Abschnitt 6 von: "Error
Control Coding: Fundamentals and Applications" von S. Lin und D.J. Costello, Jr (Prentice-Hall,
Inc., Englewood Cliffs, N.J. 1983) (nachstehend als "Error Control Coding" bezeichnet) und
in dem Abschnitt 7 von: "Theory
and Practice of Error Control Codes" von R.E. Blhut (Addison-Wesley Publishing
Co., Reading, Mass., 1983) (nachstehend als "Theory and Practice of Error Control
Codes" bezeichnet,
beschrieben. Die Theorie hinter den Codierungs- und Decodierungsverfahren
bei den bekannten Systemen ist dem Fachmann vollkommen klar, da
es einige Decodieralgorithmen zum Detektieren und Korrigieren von
Fehlern in den empfangenen oder abgerufenen Daten gibt. Im Allgemeinen
ist der Decodierprozess komplizierter als der Codierprozess.
-
EP-A
0 748 124 beschreibt eine Signalverarbeitungsanordnung und ein verfahren,
wobei ein MPEG-2 Datenstrom übertragen
wird, bei dem Reed Solomon Codes verwendet werden. En dem Empfangsende
wird das Signal einer Reed Solomon Decodierung und einer Fehlerkorrektur
ausgesetzt, und zwar unter Verwendung einer Fehlerkorrekturschaltung.
Diese Schaltungsanordnung berechnet ein Fehlerortungspolynom und
ein Fehlerbewertungspolynom, und berechnet nach Anwendung einer
Chien Suche, die Größe der Fehler
an Stellen, von denen festgestellt wurde, dass sie fehlerhaft waren.
-
US 5.537.426 beschreibt
die Anordnung zum herleiten eines Fehlerlagenpolynoms und eines
Forney-Syndrompolynoms eines Galois-Feldes. Dazu ist nur ein einziger
Multiplizierer und ein einziger Addierer zur Multiplikation über das
Galois-Feld erforderlich.
-
Eine
derartige Anwendung des bekannten Reed Solomon Decoders findet sich
in der Übertragung
von digitalem komprimiertem Video über eine terrestrische Sendung, über einen
Kabelkanal oder einen Satellitenkanal. So kündigte beispielsweise die "Grand Alliance" (GA) weinen Standard
für digitale HDTV
Sendungen über
derartige Kanäle
an. Das GA HDTV Übertragungssystem
benutzt einen spezifischen (207, 187) Reed Solomon Code (nachstehend als "R-S" bezeichnet) zur
Vorwärtsfehlerkorrektur.
In diesem Code bilden 187 Bytes "Ladungs"-Daten und zusätzliche
20 Bytes Fehlerprüfdaten
einen Reed Solomon Block von 207 Bytes.
-
In
dem oben stehenden Beispiel bestehen etwa 10 Prozent des R-S-Blocks
aus Fehlerprüfdaten;
dies ist ein relativ kleiner Prozentsatz der Blockdaten. Im Allgemeinen
gilt, je größer die
Blockgröße, umso
kleiner der Blockprozentsatz an Fehlerprüfdaten, die erforderlich sind
zum Erfüllen
einer bestimmten Leistungsanforderung. Da die Durchführungszeit des
Decodierungsprozesses nur von dem Betrag an Fehlerprüfdaten abhängig ist,
ein größeres Blockformat
ermöglicht
es, dass bei einer bestimmten Verarbeitungsrate ein kleinerer Prozentsatz
der Blockverarbeitungszeit für
Fehlerdetektion und -korrektur verwendet werden kann. Dagegen kann
die Verarbeitung mit einer geringern Rate durchgeführt werden. Dies
wieder ermöglicht
ein Kompromiss der Verarbeitungsgeschwindigkeit im Tausch für einfachere,
wirtschaftlichere Hardware, die auf effizientere Art und Weise an
einer integrierten Schaltung implementiert werden kann.
-
In
einer typischen Senderübertragung
oder einem archivarischen Datenspeichersystem braucht jeder Empfänger oder
Retriever einen derartigen Decoder, und da diese als Konsumentenprodukte
verkauft werden, ist es erwünscht,
dass der Entwurf des Decoders möglichst
einfach, effizient und wirtschaftlich ist.
-
Deswegen
ist, während
die bekannten Reed Solomon Decoder einigermaßen befriedigend waren, ein
noch einfacherer und effizienterer Reed Solomon Decoder erwünscht, der
eine mehr Hardware-effiziente und noch allgemeinere Architektur
benutzt als in dem Stand der Technik gefunden wurde für Situationen,
in denen der R-S Datenblock eine bestimmte Länge übersteigt, wie dies in dem
GS Standard der Fall ist.
-
Zusammenfassung der Erfindung
-
Es
ist nun u. a. eine Aufgabe der vorliegenden Erfindung, einen Fehlerberechnungsprozessor zu
schaffen, der die Berechnungen von Datenfehlerstellen und -größen auf
eine sehr Hardware-effiziente Weise implementiert.
-
Diese
Aufgabe wird nach der vorliegenden Erfindung in einem Prozessor
nach Anspruch 1 erfüllt.
-
In
dem allgemeinen Verfahren der Reed Solomon Decodierung wird ein
Satz kumulativer "Summen" der Daten in einem
bestimmten R-S Block berechnet; diese werden als "Syndrome" bezeichnet und entsprechen
in ihrer Zahl den Fehlerprüfbytes
in dem Block. Die Stelle und die Größe jedes Fehlers in dem Block
wird unter Verwendung nur der Syndrome ermittelt und wird für jeden
Block korrigiert, in dem die Anzahl fehlerhafter Bytes die Hälfte der
Anzahl Fehlerprüfbytes
nicht übersteigt.
Mit diesen Kenntnissen können
die fehlerhaften Bytes innerhalb des Blocks lokalisiert werden,
und, da jedes Byte identifiziert wird, kann die Fehlergröße zu den
beschädigten
Daten hinzugefügt
werden um den ursprünglichen
Wert zu reproduzieren. Die Syndromberechnung muss für jeden
Datenblock erledigt werden und kann erfolgen, wenn die Daten unter
Anwendung von Standard-Verfahren
in den Decoder eingegeben werden. Die finale Korrektur muss auch
für den
ganzen Block durchgeführt
werden und kann wieder gemacht werden, wenn die Daten aus dem Decoder
ausgeliefert werden, nachdem die Fehlerstellen und -größen ermittelt worden
sind. Diese Berechnungen bilden aber den schwierigsten Teil des
Reed Solomon Decodierungsprozesses und erfordern typischerweise
komplizierte Hardware zur Durchführung
derselben.
-
Deswegen
wird nach der vorliegenden Erfindung eine Reed Solomon Decoderarchitektur
geschaffen, welche die Berechnungen von Datenfehlerstellen und -größen implementiert,
gegeben die Syndrome für
diesen Block, auf eine sehr Hardware-effiziente Weise vorgesehen.
Diese Architektur solle eine breite Skala an mathematischen Vorgängen durchführen, was
als "Galois Field" (GF) Arithmetik bezeichnet
wird, die zur Reed Solomon Decodierung erforderlich sind. Diese
sind unabhängig
von den Syndromberechnungsmitteln und können mit wenigstens zwei durchaus
bekannten Fehlerkorrekturverfahren angewandt werden.
-
In
einer bevorzugten Ausführungsform
kann der Fehlerberechnungsprozessor das Fehlerortungspolynom, das
Fehlerbewertungspolynom und die Werte der Fehler, deren Stelle als
fehlerhaft ermittelt wurde, berechnen, und zwar unter Verwendung
zweier Polynomspeicherregister, zweier Elementspeicherregister,
eines Multiplizierers zum Durchführen selektierter
Multiplikation und Division, eines einzigen Addierers zum Durchführen selektierter
Addition und Subtraktion, eines einzigen Fehlerortungsstapelspeichers,
eines einzigen Fehlerwertstapelspeichers und eines Syndromregisters
zur Speicherung der Syndrome des großen Datenblocks.
-
Insbesondere
kann das erste Polynomspeicherregister zur Speicherung bis zu t
+ 1 Bytes der Koeffizienten des Fehlerortungspolynoms benutzt werden;
das zweite Polynomspeicherregister kann zur Speicherung bis zu 2t
Bytes der Koeffizienten des Fehlerbewertungspolynoms und zur Speicherung
der Koeffizienten des B(x) Polynoms verwendet werden, das in dem
Berlekamp-Massey Algorithmus verwendet wird, während der Durchführung des
genannten Berlekamp-Massey Algorithmus; das erste Elementspeicherregister
kann zum Berechnen der Diskrepanz verwendet werden, zur Speicherung
des normalisierten Wertes der Diskrepanz, zur Speicherung von Zwischenwerten
während
der Berechnung der einzelnen Koeffizienten des Fehlerbewertungspolynoms
und zur Speicherung der Ergebnisse der Bewertung des Fehlerbewertungspolynoms;
das zweite Elementspeicherregister kann zur Speicherung eines vorhergehenden
Nicht-Null-Wertes der Diskrepanz verwendet werden; der Fehlerortungsstapelspeicher kann
zur Speicherung der Wurzeln des Fehlerortungspolynoms verwendet
werden; und der Fehlerwertstapelspeicher kann zur Speicherung der
Größe jedes
Fehlers und zur Speicherung der Abgeleiteten des Fehlerortungspolynoms
während
der "Chien Search" benutzt werden.
-
Auf
entsprechende Weise ist es eine Aufgabe der vorliegenden Erfindung,
einen verbesserten Reed Solomon Decoder zu schaffen, der einen maximalen
Betrag an Verarbeitungsfunktionen mit einem minimalen Betrag an
Hardware durchführt.
-
Eine
andere Aufgabe der vorliegenden Erfindung ist es, eine verbesserte
Reed Solomon Decoderarchitektur zu schaffen, die auf einfache Weise
in eine integrierte Schaltung integriert werden kann.
-
Noch
eine andere Aufgabe der vorliegenden Erfindung ist es, einen verbesserten
Reed Solomon Decoder zu schaffen, der eine Höhere Verarbeitungsgeschwindigkeit
schafft.
-
Noch
eine andere, weitere Aufgabe der vorliegenden Erfindung wird teilweise
ersichtlich sein und wird teilweise aus der Spezifikation hervorgehen.
-
Kurze Beschreibung der
Zeichnung
-
Ausführungsbeispiele
der Erfindung sind in der Zeichnung dargestellt und werden im Folgenden näher beschrieben.
Es zeigen:
-
1 eine
Darstellung des Reed Solomon Codes, spezifiziert in dem Grand Alliance
(GA) Standard,
-
2 ein
Blockschaltbild eines Reed Solomon Decoders, konstruiert nach der
vorliegenden Erfindung,
-
3 ein
Zeitdiagramm für
einen Reed Solomon Decoder, konstruiert nach der vorliegenden Erfindung,
-
4A eine
Darstellung eines Galois-Feldes (GF) Polynomprozessors, konstruiert
nach der vorliegenden Erfindung,
-
4B eine
Darstellung einer Konfiguration nach der vorliegenden Erfindung
zur Berechnung der Diskrepanz (Δ),
-
4C eine
Darstellung einer Konfiguration nach der vorliegenden Erfindung
zur Normalisierung der Diskrepanz (Δ),
-
4D eine
Darstellung einer Konfiguration nach der vorliegenden Erfindung
zur Berechnung des Fehlerortungspolynoms Λ(x),
-
4E eine
Darstellung einer Konfiguration der vorliegenden Erfindung zur Berechnung
des Fehlerbewertungspolynoms Ω(x),
-
4F eine
Darstellung einer Konfiguration der vorliegenden Erfindung zur Bewertung
des Fehlerbeweriungspolynoms Ω(x),
-
4G eine
Darstellung einer Konfiguration der vorliegenden Erfindung zur Bewertung
der Größe der detektierten
Fehler,
-
4H eine
Darstellung eines Polynomregisterspeicherelementes (d.h. ein (1)
Bit) konstruiert nach der vorliegenden Erfindung,
-
5A-B
eine Darstellung einer bekannten Chien Suchschaltung für Polynomwurzelstellen,
und
-
5C eine
Darstellung der gegenseitigen Beziehung zwischen dem Prozessor,
konstruiert nach der vorliegenden Erfindung und der Chien Sucharchitektur,
-
6 eine
Darstellung eines Blockschaltbildes einer Korrekturschaltung, die
in Kombination mit der vorliegenden Erfindung verwendet wird, und
-
7 eine
Darstellung einer bekannten Korrekturschaltung, in der Fehler an
dem Ausgang berechnet werden.
-
Detaillierte Beschreibung
der bevorzugten Ausführungsformen
-
Der
in dem Grand Alliance (GA) Standard spezifizierte Reed Solomon Code
ist in 1 dargestellt. Er verwendet eine Blocklänge von
207 Bytes, von denen 187 aus einem MPEG Transportpaket bestehen,
das die "Belastungs" Daten bildet, wobei
die restlichen 20 Bytes, die von der Codierschaltung in dem Sender
(nicht dargestellt) erzeugt werden. Diese Codierschaltung führt im Wesentlichen
eine "Teilung" des Datenblocks
durch, der als ein Grad-206 Polynom über das Galois-Feld GF (256)
behandelt wird, durch ein "Generator" Polynom (spezifiziert
für den
bestimmten R-S Code) zum Erzeugen eines "Rest" Polynoms,
das die 20 Fehlerprüfbytes
am Ende des Blocks bildet. Obschon die Schaltungsanordnung für den R-S
Code spezifisch ist, der in dem GA Standard verwendet wird, illustriert
sie dennoch die allgemeine Struktur und Wirkungsweise eines bekannten
Reed Solomon Codierers; nur die Blocklänge, die Anzahl Prüfbytes,
und das Generatorpolynom werden anders sein.
-
2 zeigt
einen Reed Solomon Decoder, allgemein durch 20 bezeichnet.
Wie in 2 dargestellt, werden Daten, die in den Decoder 20 eingegeben
werden, einem Syndromberechner 22 und einer Reed Solomon
Blockdatenverzögerungsleitung 24 zugeführt. Die
resultierenden berechneten Syndrome werden von dem Syndromberechner 22 einem
Fehlerberechner 26 zugeführt. Der Fehlerberechner 26 bestimmt
die Fehlerstellen und die Größen, wie
nachstehend detailliert beschrieben. Es ist eine Fehlerkorrekturschaltung 28 vorgesehen.
Die Fehlerkorrekturschaltung 28 empfängt als Eingangssignale die
Fehlerstellen und die Fehlergrößen von
dem Fehlerberechner 26 und die verzögerten Daten von der Reed Solomon
Blockdatenverzögerungsleitung 24.
-
Der
erste Schritt in dem Decodierprozess ist die Syndromberechnung.
Dies erfordert die Verarbeitung des ganzen R-S Blocks, unabhängig von
der Größe des Blocks
oder der Anzahl Prüfbytes.
Die Anzahl Syndrome aber entspricht der Anzahl Prüfbytes, die
an sich wieder mit der Größe des Blocks
zunimmt aber ein kleinerer Prozentsatz der Blockgröße wird, wenn
dies geschieht. Die resultierenden Syndrome werden danach benutzt
um die Fehlerstellen und die Größe der Fehler
in dem Block zu ermitteln. Eine genormte durchaus bekannte Schaltungsanordnung zum
Durchführen
einer Syndromberechnung ist in "Error
Control Coding" in
Abschnitt 6 und insbesondere auf Seite 174 beschrieben.
Ein Decoder für
einen R-S Code, der imstande ist, bis zu t Fehler (t = 10 in der
GA Norm) zu korrigieren, wird 2t derartige Schaltungsanordnungen
erfordern, eine für
jedes Syndrom.
-
Die
Werte der Syndrome werden erst dann bekannt sein, wenn ein ganzer
Block in den Decoder 20 eingegeben worden ist und die eingegebenen
Daten müssen
von der Reed Solomon Blockdatenverzögerungsleitung 24 um
ein einziges Blockintervall verzögert
werden um das nachzuweisen. Die Fehlerberechnung wird danach von
dem Fehlerrechner 26 durchgeführt und der Datenausgang von
dem Decoder wird korrigiert. Die Fehlerkorrektur erfordert ein komplettes
Blockintervall. Eine "Pipeline"-Verarbeitung von
R-S Blöcken
kann erreicht werden, wenn die Fehlerberechnung in einem einzigen
Blockintervall vollendet wird und die Daten abermals um ein zweites
Intervall verzögert
werden. Ein Systemzeitdiagramm für
den Decoder 20 ist in 3 dargestellt.
-
Wie
oben erwähnt,
bestimmt der Fehlerrechner 26 die Fehlerstellen und die
Fehlergrößen mit
Hilfe der Berechnungen, die Polynomarithmetische Vorgänge über ein
Galois-Feld benutzen, zugehörend
zu den Daten, die übertragen
werden (GF(256) im Falle von 8-Bit Bytes). Erstens muss ein Fehlerortungspolynom
erzeugt werden, dessen Wurzeln über GF(256)
der Stelle jedes detektierten Fehlers innerhalb des R-S Blocks entsprechen.
Dies kann geschehen unter Verwendung jedes beliebigen Algorithmus einer
Anzahl Standardalgorithmen, von denen der euklidische und der Berlekamp-Massey
am bekanntesten sind. Die meisten bekannten Reed Solomon Decoder
hoher Geschwindigkeit benutzen den euklidischen Algorithmus, weil
dieser imstande ist eine schnellere Berechnung des erforderlichen
Polynoms durchzuführen.
Der euklidische Algorithmus hat den Nachteil aber, dass ein großer Betrag
an Hardware für
die Implementierung erforderlich ist. Andererseits kann der Berlekamp-Massey-Algorithmus,
obschon nicht so schnell, mit viel weniger Hardware implementiert
werden, weil dieser weniger arithmetische Logik und Datenspeicherung
erfordert als für
den euklidischen Algorithmus erforderlich ist. Folglich wird durch
Anwendung des Berlekamp-Massey Algorithmus ein effizienterer Entwurf
erzielt. Die Architektur zum Implementieren des Berlekamp-Massey
Algorithmus wird nachstehen detailliert beschrieben, was ein Mittel
ist zum Optimieren der Architektur zum Reduzieren der Durchführungszeit
des Algorithmus.
-
Assoziiert
mit dem Fehlerortungspolynom ist das Fehlerbewertungspolynom, das
unter Anwendung des Fehlerortungspolynoms und der Syndromwerte für den R-S Block
berechnet wird. Die zwei Polynome werden nacheinander verwendet
zum berechnen der Fehlergrößen, wenn
die Fehlerstellen einmal ermittelt worden sind. Dies geschieht dadurch,
dass die Wurzeln des Fehlerortungspolynoms gefunden werden (d.h.
die primitiven Werte in GF(256), die, wenn für die Polynomvariable ersetzt, ein
Ergebnis gleich Null liefern), die je der Stelle eines Fehlers in
dem Block entsprechen. Das Finden der Wurzeln erfolgt durch Anwendung
eines gründlichen
Suchverfahrens, das als die Chien Suche bekannt ist, wobei alle
möglichen
Blockstellenwerte in dem Polynom ersetzt werden um zu ermitteln,
welche ein Ergebnis Null liefern. Die Wurzeln des Polynoms werden
danach wie nachstehend beschrieben, gespeichert und der durchaus
bekannte Forney Algorithmus wird zum Berechnen der Fehlergröße für jede Wurzel
angewandt, und zwar unter Anwendung des Fehlerortungspolynoms und
des Fehlerbewertungspolynoms. Alle oben genannten Vorgänge, ausgenommen
die Chien Suche, die spezielle Hardware erfordert, können unter
Anwendung der Architektur durchgeführt werden, die nach der vorliegenden
Erfindung konstruiert und nachstehend beschrieben worden ist.
-
Ein
Flussdiagramm für
den Berlekamp-Massey Algorithmus, der das Fehlerortungspolynom berechnet
ist in "Theory and
Practice of Error Control Codes",
Kapitel 7 und insbesondere Seite 186 beschrieben.
-
Im
Allgemeinen entspricht in dem Berlekamp-Massey Algorithmus die maximale
Länge der zwei
Polynome Λ(x)
und B(x) während
einer bestimmten Wiederholung des Algorithmus dem Wert des Registerlängenparameters
L während
dieser Wiederholung, und nicht unbedingt der maximalen Länge t +
1 der Register. In praktischen Entwürfen aber haben Polynomschieberegister,
die zum Implementieren dieses Algorithmus verwendet werden, immer
die maximale Länge.
Dies bedeutet, dass während
jeder Wiederholung die Anzahl Taktzyklen, die zum Durchführen eines
Polynomvorgangs erforderlich sind, immer t + 1 sein wird, ungeachtet
der wirklichen Länge
des Polynoms in dieser Wiederholung. Da es zwei derartige Vorgänge während jeder
Wiederholung des Algorithmus gibt, ist das Ergebnis, dass 2(t +
1) Taktzyklen verwendet werden, wenn im Wesentlichen viel weniger
ausreichen würden.
Dies beeinträchtigt
die Geschwindigkeit der Decodierung wesentlich, wenn die Taktrate
durch die Hardware begrenzt wird, oder sonst wird ein schnellerer
Taktgeber erforderlich sein um die gewünschte Decodierrate zu erzielen.
-
Der
Polynomprozessor 60 kann diese Begrenzung dadurch überwinden,
dass der Registerlängenparameter
L angewandt wird zum Einstellen der Länge der zwei Register und dass
danach ein "Kurzschluss' von dem Eingang
zu dem Ausgang jedes Registerelementes geschaffen wird, das einen
Koeffizienten mit einem Gradwert höher als L speichert. Unter
Verwendung von Registern konstanter Länge ist die Anzahl Taktzyklen,
erforderlich für
die 2t Durchgänge
des Algorithmus 4t(t + 1); Bei Verwendung von Registern variabler
Länge übersteigt
aber L niemals die hälfte
der Anzahl der aktuellen Wiederholungen. Die maximale Anzahl Zyklen
für einen
bestimmten Durchgang wird 2(L + 1), und die gesamte Anzahl Zyklen
für den
Algorithmus ist nun die Summe einer arithmetischen Reihe und entspricht
2t(t + 3). Eine Reduktion der Durchführungszeit um höchstens einen
Faktor zwei wird auf diese Art und Weise erzielt. Für die GA
Norm entspricht dies 260 Taktzyklen.
-
Das
Fehlerbewertungspolynom Ω(x)
ist das Modulo 2t Produkt aus dem oben berechneten Fehlerortungspolynom
und dem Syndrompolynom. Der Polynomprozessor ist imstande, diese
Berechnung durchzuführen,
insbesondere da das Fehlerortungspolynom bereits in einem der zwei
Speicherregister 61 und 62 vorhanden ist, wie
nachstehend noch beschrieben wird (siehe 4A), und
das Fehlerbewertungspolynom kann in das zweite Register 62 (mit der
Länge von
2t) eingeschrieben werden. Jeder Produktkoeffizient benutzt jeden
Term des Fehlerortungspolynoms und erfordert auf diese Weise zur
Berechnung t + 1 Taktzyklen. Das Fehlerbewertungspolynom wird auf
diese Weise in 2t(t + 1) Taktzyklen berechnet, was, für die GA
Norm gleich 220 ist.
-
Es
dürfte
dem Fachmann einleuchten, dass der Berlekamp-Massey Algorithmus
zwei Polynome T(x) und B(x) erfordert (wobei T(x) zur einstweiligen Speicherung
benutzt wird und deswegen in einer wirklichen Implementierung nicht
notwendig ist), und führt
2t Wiederholungen durch. Eine Schieberegisterarchitektur, die den
Algorithmus durchführt,
und sich auf Seite 186 von "Theory
and Practice of Error Control Codes" finden lässt, ist auch darin auf Seite
189 beschrieben. Ein Flussdiagramm eines kompletten Reed Solomon
Decodierungsprozesses ist ebenfalls in dem oben genannten Text auf
Seite 190 beschrieben.
-
In 4A ist
ein Fehlerberechnungsprozessor 60 für Reed Solomon Decodierung
nach der vorliegenden Erfindung dargestellt. In der bevorzugten Ausführungsform
führt der
Prozessor 60 die Galois-Feld Arithmetik an Polynomen durch,
die eine maximale Länge
von t + 1 und 2t haben. Wie hier beschrieben wird und was dem Fachmann
einleuchten dürfte,
ist der Prozessor 60, da konstruiert nach der vorliegenden
Erfindung, für
minimale Hardware und minimale Rechenzeit optimiert. Insbesondere
ist der Prozessor 60 ent worfen zum Speichern und zum Durchführen mathematischer
Vorgänge
an Arithmetikelementen von einem, sowie Polynomen über ein Galois-Feld.
Ein derartiges Element kann unter Anwendung von Standard-Bits dargestellt
werden, so kann beispielsweise ein Element in GF(256) unter Verwendung
von 8 Bits, oder einem Byte dargestellt werden. Ein Polynom über ein
GF kann durch seine Koeffizienten dargestellt werden, die je an
sich wieder ein Element des GF sind, dadurch kann ein Polynom n.
Grades durch n + 1 derartige Elemente dargestellt werden. Im Falle
von GF(256), wobei eine binäre
Darstellung verwendet wird, wird dies gleich n + 1 Bytes.
-
Dies
ermöglicht
es, dass Elemente des GF in genormten digitalen Datenregistern gespeichert
werden, dass Polynome in Registergruppen gespeichert werden, und
dass eine Manipulation von und arithmetische Vorgänge an Elementen
und Polynomen unter Anwendung herkömmlicher digitaler Logik durchgeführt werden.
-
In 4A werden
die 2t Syndrome für
einen Reed Solomon Block in dem Syndromrechner 22 berechnet
und werden in dem Syndromregistern 74 abgelagert. Jedes
dieser 2t Register 74 speichert ein einziges Syndrom, was
gerade ein GF Element ist. Die GF(256) Syndromregister bestehen
auf diese Weise aus 2t Byteregistern. Wenn zwischen R-S Blöcken keine
Zeitlücken
erlaubt sind, müssen
diese Register die Ergebnisse aller 2t Syndromberechnungen gleichzeitig
empfangen; in diesem Fall sind 2t eindeutige Register erforderlich.
Der Grund dazu ist, wie dies aus dem Zeitdiagramm nach 3 hervorgehen dürfte, dass
die Syndrome für
den R-S Block n + 1 zu derselben Zeit berechnet werden, wo die Fehlerberechnung
für R-S
Block n durchgeführt
wird, und die Syndromwerte sind erst nach der Durchführung der Berechnungen
für den
ganzen Block verfügbar
(d.h. am Ende des Blocks. Außerdem
müssen
die Syndromwerte am Anfang des nächsten
Blocks gelöscht werden,
damit ein neuer Satz von Syndromberechnungen gestartet wird. Dies
bedeutet, dass weniger als 2t Taktzyklen verfügbar sein werden um die Syndromwerte
in ihre Speicherregister zu übertragen, und
sie müssen
folglich gleichzeitig übertragen
werden, was das gleichzeitige Schreiben der 2t Syndrome in die 2t
Register erfordert. Für
Fehlerberechnung aber ist es nur erforderlich, den Inhalt eines
einzigen Registers zu einem bestimmten Zeitpunkt auszulesen. Wenn
in der Zeit Lücken
erlaubt sind, dass ist es möglich
die Endergebnisse der 2t Syndromberechnungen sequentiell während des
Lückenintervalls
zu übertragen
und die Syndromregister können
dann unter Verwendung einer Registerdatei, oder sogar eines kleinen
Speichers, mit 2t Bytestellen, implementiert werden. Die Syndromberechnun gen
können
unter Anwendung jedes beliebigen Verfahrens einer Anzahl durchaus
bekannter Verfahren, wie diese in dem Kapitel 6 von "Error Control Coding" beschrieben sind,
durchgeführt
werden.
-
Die
drei GF Algorithmen, die von dem Prozessor 60 durchgeführt werden,
sind der Berlekamp-Massey (B-M) Algorithmus zum Berechnen des Fehlerortungspolynoms,
die Berechnung des Fehlerbewertungspolynoms, und der Forney Algorithmus
zum Berechnen der Fehlerwerte (die Chien Suche zum Berechnen der
Fehlerstellen wird vorzugsweise durch das Verfahren und die Konstruktion durchgeführt, wie
diese in den 5A-C dargestellt sind. Die Reihenfolge,
in der diese Algorithmen durchgeführ werden, ist auf Seite 190
von "Theory and
Practice of Error Control Codes" beschrieben. Die
drei Algorithmen betreffen alle arithmetische Berechnungen an GF
Elementen und Polynomen. Untersuchung der Algorithmen zeigt, dass
nur ein begrenzter Satz von Manipulationen und arithmetischen Vorgängen durchgeführt wird
und dass eine maximale Anzahl Elemente und Polynome zu einem bestimmten
Zeitpunkt gespeichert zu werden brauchen für jeden dieser drei Algorithmen,
wodurch die neue und effizientere architektonische Konfiguration aus
den 4A-G erzielt wird.
-
Wie
in 4A dargestellt, umfasst der Prozessor 60 zwei
Speicherregister 61 und 62 (nachstehend als Register
A und B bezeichnet) zur Speicherung von GF Polynomen, zwei Register 71 und 72 (nachstehend
als Register X und Y bezeichnet) zur Speicherung von GF Elementen,
einen GF Multiplizierer 78, dem ein GF Addierer 80 folgt,
und Datenbusse, die eine Verbindung mit jeder Datenquelle und mit
jedem Ziel ermöglichen.
Ein Merkmal dieser Architektur ist, dass es zwei komplette Sätze von
Datenbussen gibt, die es ermöglichen,
dass zwei simultane Datenübertragungen
zwischen Quelle und Ziel durchgeführt werden können; dies
ermöglicht
es, dass bestimmte Algorithmen, wie nachstehend beschrieben, in
weniger Zeit d.h. in weniger Taktzyklen komplett durchgeführt werden
können.
-
Für den Fall
von GF(256), in dem jedes GF Element durch eine 8-Bit binäre Zahl
dargestellt wird, kann jedes der zwei Elementregister 70, 72 unter Verwendung
von Byte-Speicherregistern implementiert werden. Die zwei Polynomregister 61, 62 können unter
Verwendung von Viel-Byte-Speicherung implementiert werden, mit einem
einzigen Byte für
jeden Koeffizienten des gespeicherten Polynoms.
-
Für einen
R-S Code mit einer Fehlerkorrekturfähigkeit von t Byte-Fehlern
besteht die minimale Polynomspeicheranforderung für die drei
von dem Fehlerberechnungsprozessor durchgeführten Algorithmen aus einem
einzigen Polynom des Grades t (wobei t + 1 Bytes an Registerspeicherraum
erforderlich ist), und einem einzigen des Grades 2t – 1 (wobei 2t
Bytes an Speicherraum erforderlich sind). Die Datenbusse in der
bevorzugten Ausführungsform
sind 8-Bit Busse. Der Multiplizierer 78 und der Addierer 80 haben
je zwei 8-Bit Dateneingänge
und einen einzigen 8-Bit Ausgang, und sind unter Anwendung von genormten
kombinatorischer Logik implementiert, die ihre betreffenden Vorgänge in GF(256)
arithmetisch implementiert.
-
Da
GF arithmetische Vorgänge
(Addition, Multiplikation und Division) und Datenüberragungen an
jedem einzelnen Element eines Polynoms durchgeführt werden sollen, ob das Endergebnis
ein Element oder ein anderes Polynom ist, ist ein Mechanismus zum
Schnellen aufeinander folgenden Zugriff auf die einzelnen Polynomkoeffizientenbyteregister erforderlich.
Dies wird dadurch erreicht, dass die Polynomspeicherregister als
Schieberegister von Koeffizientenbytes implementiert werden, versehen
mit dem Koeffizienten höchster
Ordnung am Anfang (Ausgang) des Registers, und mit dem Koeffizienten niedrigster
Ordnung an dem Ende (Eingang). Ein Vorgang an einem Polynom erfordert
dann, dass die Koeffizienten in dem Speicherregister "umlaufen", so dass jeden Taktzyklus
ein neuer Koeffizient ausgeliefert wird und/oder eingegeben wird
in das Register (abhängig
von der Frage, ob das Polynomregister eine Quelle oder ein Ziel
ist oder aber beides) und nach einer Anzahl Taktzyklen gleich der
Länge des Registers,
befinden sich die Koeffizienten an ihren ursprünglichen Stellen in dem Register.
-
Nebst
Datenübertragungen
zwischen den Speicherregistern sind die an den gespeicherten Daten
durchgeführten
Vorgänge
Multiplikation, Division und Addition. Die ersten zwei Vorgänge werden durch
den GF Multiplizierer 78 durchgeführt (es versteht sich, dass
Division durch den Multiplizierer 78 erreicht wird, der
als Teiler dadurch verwendet werden kann, dass einfach eine Inversion über den
GF an dem Divisor durchgeführt
wird und dass eine Multiplikation des Ergebnisses mit dem Dividenden durchgeführt wird).
Addition, durchgeführt
durch den Addierer 80, der für GF(256) oder für jeden
anderen beliebigen interessanten GF, aus einem bitweisen Exklusiv-Oder-Element
der zwei Byteelemente besteht, die den Summanden und den Augenden
bilden. Die Konfiguration des Prozessors 60 ermöglicht, nebst
den oben genannten einzelnen Vorgängen die Multiplikation oder
Division von zwei Elementen eine nachfolgende Addition eines dritten
Elementes. Dies ist der Fall, in dem diese Kombinationen alle arithmetischen
Vorgänge
an GF Elementen bilden, die für
jeden der durch diese Architektur durchgeführten drei Algorithmen erforderlich
sind.
-
Nun
folgt eine Beschreibung der 4B-4G für ein besseres
Verständnis,
wie die jeweiligen Teile des vorhergehenden Algorithmen berechnet
werden.
-
Der
Berlekamp-Massey-Algorithmus besteht aus drei einzelnen Vorgängen, die
für jede
der 2t Wiederholungen des Algorithmus durchgeführt werden. Der erste dieser
Vorgänge
ist die Berechnung der sog. Diskrepanz (durch Δ bezeichnet), die durch den
Wert des Fehlerortungspolynoms bestimmt wird (bezeichnet durch Λ(x)) bei
der aktuellen Wiederholung (dieses Polynom bildet das Endergebnis
des Algorithmus bei der letzten Wiederholung, und wird sukzessiv
im Laufe des B-M Algorithmus "aufgebaut"), und der 2t Syndrome.
Die Syndrome werden in den 2t Syndromspeicherregistern 74 gespeichert und
die Koeffizienten von Λ(x)
werden in dem Polynomspeicherregister 61 gespeichert. Der
Wert von Δ wird,
in einer bestimmten Wiederholung, durch Erzeugung einer akkumulierten
Summe von Produkten einzelner Λ(x)
Koeffizienten (gespeichert in dem Register 61) und Syndromen
(gespeichert in dem Register 74), und wird in dem Elementregister 70 gespeichert.
Da der Wert von Λ(x)
nicht durch diesen Vorgang geändert
wird, werden die Koeffizienten aus dem Register 61 ausgelesen
und danach in das Register zurück
eingeschrieben oder "in
Umlauf gebracht";
dies ermöglicht
es, dass auf alle einzelnen Koeffizienten nacheinander eingegriffen
wird, dass sie alle mit dem geeigneten Syndrom multipliziert werden
und zu der akkumulierten Summe addiert werden, deren Endwert am
Ende des Umlaufs den gewünschten
Wert von Δ bildet.
In diesem Vorgang wird die Polynomregisterumlauftechnik angewandt um
die erwünschten
Ergebnisse zu erzielen. In dem bevorzugten Verfahren wird das Register 61 als Quellen-
und als Zielpolynomregister verwendet, während das Register 70 als
Quellen- und als Zielelementregister benutzt wird.
-
Der
zweite Schritt, der in einer Wiederholung des B-M Algorithmus auftritt,
wenn die oben genannte Diskrepanz Δ nicht gleich Null ist, ist
die Normalisierung oder Teilung durch den vorhergehenden Nicht-Null-Wert,
der in dem Register 72 (siehe 4C) gespeichert
ist. Der neue normalisierte Wert wird in dem Register 70 gespeichert
und der alte nicht normalisierte Wert wird nun in dem Register 72 gespeichert,
und zwar zur Verwendung bei der nachfolgenden Normalisierung.
-
Der
dritte und letzte Schritt der B-M Algorithmuswiederholung, der auch
hier wieder nur dann auftritt, wenn die Diskrepanz Δ nicht Null
ist, ist die Berechnung des aktualisierten Wertes des Polynoms Λ(x), der
noch immer in dem Register 61 gespeichert ist, auf Basis
des aktuellen Wertes, des neuen Wertes von Δ (gespeichert in dem Register 70),
und eines Hilfspolynoms, das als B(x) bezeichnet wird, das in dem
Register 62 gespeichert ist. Unter bestimmten Bedingungen
wird das Polynom B(x) derart aktualisiert, dass dieser der aktuelle
(obschon nicht aktualisierte) Wert von Λ(x) ist; unter anderen Bedingungen (spezifiziert
in dem Berlekamp-Massey-Algorithmus) wird er nicht aktualisiert
und in das Register 62 neu in Umlauf gebracht. In beiden
Fällen
werden die zwei Polynome in den betreffenden Registers (61 und 62) in
Umlauf gebracht und jeder einzelne Koeffizient wird ausgelesen uns
in einen einzigen Taktzyklus eingeschrieben. Die Berechnung des
aktualisierten Λ(x) besteht
aus der Multiplikation jedes Koeffizienten des Hilfspolynoms B(x)
(in dem Register 62) mit der normalisierten Δ (in dem
Register 70), und aus der Addition des entsprechenden Koeffizienten
(d.h. zu derselben Potenz von x) der aktuellen Λ(x) (in dem Register 61).
Dies geschieht für
jeden Koeffizienten von Λ(x)
und die resultierenden aktualisierten Koeffizienten werden in das
Register 61 zurück
in Umlauf gebracht.
-
4E zeigt,
wie die Berechnung des Fehlerbewertungspolynoms Ω(x) durchgeführt wird,
und zwar unter Verwendung des vorher durch den B-M Algorithmus berechneten
Fehlerortungspolynoms Λ(x),
das sich noch immer in dem Register 61 befindet, und der
2t Syndrome, die sich noch immer in den Syndromregistern 74 befinden.
Wie bei dem vorhergehenden Polynom wird der Fehlerbewerter nacheinander über 2t Wiederholungen "aufgebaut", wobei jeder Koeffizient
von Ω(x)
aus einer akkumulierten Summe der Produkte aus selektierten Koeffizienten von Λ(x) und selektierten
Syndromen besteht. Das Endergebnis ist ein Polynom der Ordnung 2t – 1 mit 2t
Koeffizienten, das in dem Register 62 gespeichert ist.
An dieser Stelle speichert das Register 61 (bestehend aus
t + 1 Elementregistern) das Fehlerortungspolynom Λ(x) und das
Register 62 (bestehend aus 2t Elementregistern) speichert
das Fehlerbewertungspolynom Ω(x).
-
Bestimmung
der wirklichen Stellen der Datenfehler in einem R-S Block erfolgt
dadurch, dass die Wurzeln des Fehlerortungspolynoms Λ(x) gefunden
werden, die je unmittelbar mit einer Fehlerstelle übereinstimmen.
Dies geschieht nicht durch den Fehlerberechnungsprozessor 60,
erfolgt stattdessen jedoch durch die Chien Suche, die das Polynom Λ(x) bei allen
möglichen
Datenstellenwerten bewertet, so dass alles, was zu einem Ergebnis
von Null führt
(d.h. Wurzeln des Polynoms) Blockfehlern entsprechen und gespeichert
werden, oder auf den Fehlerortungsstapelspeicher "gedrückt" werden. Auch hier
sind die Wurzeln GF Elemente, die in GF(256) als Datenbytes dargestellt
sind. Da der R-S Code imstande ist, höchstens t Fehler zu korrigieren,
hat der Fehlerortungsstapelspeicher eine Tiefe t und eine Breite
von 8 Bits (1 Byte).
-
Im
Allgemeinen besteht die Chien Suche für die Wurzeln des Fehlerortungspolynoms
aus den Bewertungen für
n Werte, wobei n der Länge
des R-S Blocks entspricht (207 in der GA Norm). Dies bedeutet, dass
jede Bewertung sehr schnell durchgeführt werden muss, folglich kann
der Polynomprozessor nicht verwendet werden, da dieser t + 1 Taktryklen
je Wert erfordern würde,
und zwar unter Anwendung der oben beschriebenen Regel von Horner;
es bedeutet auch, dass Hardware erforderlich ist um jede Bewertung
in einem einzigen Zyklus durchzuführen, so dass die Suche in
n Zyklen erledigt werden kann. Die in den 5A-B detailliert
dargestellt Schaltungsanordnung besteht aus einem Satz von Registern,
in welche die Koeffizienten des Fehlerortungspolynoms zur Initialisierung
geladen werden, und in jedem nachfolgenden Zyklus wird der Inhalt
des i. Koeffizientenregisters mit der i. Potenz der Primitiven α von GF(256)
multipliziert. Einzelheiten der Chien Suche lassen sich auch auf
den Seiten 159-160 von "Error
Control Coding" finden.
Die GF(256) Summe aller t Register wird danach erzeugt um zu ermitteln,
ob eine Wurzel gefunden wurde. Sollt dies der Fall sein, so wird
die Wurzel zur nachfolgenden Verwendung oben auf den Stapelspeicher
gedrückt.
Die Berechnung des Fehlerbewertungspolynoms verwendet nicht diese
Wurzeln und kann deswegen gleichzeitig mit der Chien Suche nach
Vollendung des Berlekamp-Massey Algorithmus durchgeführt werden.
Für die
GA Norm ist die betreffende Anzahl erforderlicher Taktzyklen nahezu
gleich (220 gegenüber
207). Wenn die Anzahl gefundener Wurzeln nicht gleich dem Grad des
Polynoms ist, gibt es einen nicht korrigierbaren Fehlerzustand.
Dies bedeutet, dass die Anzahl Fehler in dem Block den Wert t überstieg,
und der Block nicht korrigiert werden kann. Das Vorhandensein eines
derartigen Zustandes gibt an, dass der Block nicht gültig ist.
Der Fehlerortungsstapelspeicher 66 ist erforderlich, weil
die Suche mit einem GF Element ausgelöst wird, das der letzten Stelle
in dem R-S Block entspricht; Folglich wird, wenn die Blockdaten
in der Reihenfolge erste-bis-letzte verarbeitet (und korrigiert)
werden sollen, ist es notwendig, dass die Reihenfolge der Polynomwurzeln
gegenüber
derjenigen, in der sie während
der Suche bewertet wurden, umgekehrt wird.
-
Der
durchzuführende
Endalgorithmus ist der Forney Algorithmus, der die erste Hergeleitete
(im Sinne von GF) des Fehlerortungspolynoms, sowie des Fehlerbewertungspolynoms
benutzt, beide bewertet auf Fehlerortungswurzel, die durch die Chien Suche
gefunden und in dem Fehleroriungsregister 66 gespeichert
wurde.
-
Auch
hier wird im Allgemeinen der Forney Algorithmus, der benutzt wird
zum Berechnen der Fehlergrößen, welche
die oben genannten Wurzeln und die zwei Polynome ergeben, durch
die Formel gegeben, die auf Seite 190 von "Theory and Practice of Error Control
Codes" beschrieben
worden ist. Ω(x) muss
für jede
Wurzel x, die während
der Chien Suche gefunden wurde, bewertet werden. In der GF(256) Arithmetik
aber wird die Hergeleitete von Λ(x)
dadurch gefunden, dass die Summe der ungeraden Potenzterme des bei
x bewerteten Polynoms genommen wird und diese durch x geteilt wird.
Da jeder Term von Λ(x)
während
der Suche bewertet wird, ist es eine sehr einfache Angelegenheit
die Summe nur der ungeraden Potenzterme zu erzeugen und diese gleichzeitig
mit der Wurzel in einem zweiten Stapelspeicher zu speichern, wenn
eine gefunden wird. Dies eliminiert die Zeit, die zum Bewerten der
Hergeleiteten erforderlich ist, und weil dieser zweite Stapelspeicher
zur nachfolgenden Speicherung der Fehlergrößen erforderlich sein wird,
ist wenig zusätzlicher Hardware
und keine zusätzliche
Speicherung erforderlich. Für
jede Wurzel in dem Stapelspeicher, deren Zeiger auf am Anfang des
Algorithmus rückgestellt
wird, wird unter Anwendung der Regel von Horner, wie nachstehend
beschrieben, Ω(x)
bewertet, wobei diese Regel 2t Taktzyklen erfordert und xΛ'(x) wird aus dem
zweiten Stapelspeicher zur erforderlichen Teilung angerufen, die
einen einzigen Zyklus erfordert. In dem allgemeinen Fall ist eine
Teilung durch eine Potenz der Wurzel erforderlich, aber in der GA Norm
ist diese Potenz Eins, wodurch auf diese Weise die Teilung von xΛ'(x) durch x eliminiert
wird, die nicht vorher durchgeführt
wurde. Das Ergebnis ist, dass dieser Algorithmus, der anfängt, wenn
die Chien Suche und die Fehlerbewertungspolynomberechnung beendet
worden sind, im schlimmsten Fall von t Wurzeln t(2t + 1) Taktzyklen
erfordert, was 210 für
die GA Norm entspricht. Die erste. Hergeleitete eines Polynoms über eine
GF ist die Summe der ungeraden Terme dieses Polynoms. Da die Chien
Suche erfordert, dass alle Polynomterme bewertet werden, ungerade
und gerade, werden die gewünschten
ungeraden Terme für
jede Stellenwurzel aus dem kompletten Polynom für diese Wurzel selektiert,
und die Summe wird berechnet (als wäre diese für alle Terme um die Wurzel
zu finden) und wird zu dem oben genannten zweiten Stapelspeicher 68 gedrückt, der
als Fehlerwertstapel speicher bezeichnet wird, der ebenfalls eine
Tiefe von t Stellen hat. Die Stellenwurzeln und die assoziierten
Polynomhergeleiteten werden nun in den zwei Stapelspeichern gespeichert,
und werden zum Berechnen der wirklichen Werte der Fehler entsprechend
jeder Stelle benutzt.
-
Es
sei nun auf 4F verwiesen, welche die Konfiguration
zur Bewertung des Fehlerbewertungspolynoms Ω(x) bei jedem der durch die
Chien Suche gefundenen Werte darstellt. Diese Bewertung erfolgt durch
den Fehlerberechnungsprozessor 60, wobei die Polynomkoeffizienten
verwendet werden, die in dem Register 62 gespeichert sind,
und der Stellenwurzeln, die in dem Fehlerstellenstapelspeicher 66 gespeichert
sind. Dies geschieht für
jede Wurzel dadurch, dass nacheinander das in dem Register 70 gespeicherte
akkumulierte Produkt mit dem Wurzelwert in dem Stapelspeicher gespeichert
wird, dass das Ergebnis zu dem in dem Register 62 gespeicherten
aktuellen Polynomkoeffizienten hinzuaddiert wird und dass das resultierende
neu akkumulierte Produkt in das Register 70 zurück gespeichert
wird. Dies wird für
alle 2t Koeffizienten von Ω(x)
wiederholt und das Endergebnis der letzten Wiederholung ist der
Wert von Ω(x),
bewertet für
die Stellenwurzel und wird in dem Register 70 gespeichert.
Dieser Algorithmus zur Polynombewertung ist als Regel von Herner
bekannt.
-
Nun
wird insbesondere auf 4G hingewiesen, und zwar zur
Beschreibung der Bewertung der Fehlergröße. Insbesondere erfordert
der Forney Algorithmus, dass der oben stehende Wert von Ω(x) für eine bestimmte
Wurzel durch die Abgeleitete von Λ(x),
bewertet mit derselben Wurzel, geteilt wird. Die Abgeleitete von Λ(x) wurde
aber als Nebenprodukt bei der Chien Suche erhalten, und nebst der
Wurzel in dem Fehlerwertstapelspeicher 68 gespeichert. Folglich
sind nun die Werte der beiden Polynome, bewertet mit der Wurzel,
leicht verfügbar
und können durch
den GF Multiplizierer/Teiler 78 geteilt werden, und zwar
zum Erhalten des gewünschten
Fehlerwertes. Dieses Ergebnis wird nun in dem Fehlerwertstapelspeicher 66 nebst
dem Wurzelwert gespeichert, wodurch die erste Abgeleitete von Λ(x) ersetzt
wird. Diese Prozedur wird, einschließlich der Bewertung des Ω(x) Polynoms
durch die Regel von Horner, für jede
Wurzel von Λ(x)
wiederholt, die durch die Chien Suche entdeckt wurde. Die zwei Stapelspeicher
enthalten dann die t Fehlerwerte und ihre Stellen, wobei beide für die Fehlerkorrekturschaltung 28 gebraucht werden
um die wirkliche Fehlerkorrektur durchzuführen.
-
Die
wirkliche Fehlerkorrektur, die stattfindet, nachdem alle Fehlerstellen
und Fehlergrößen ermittelt
worden sind, wird von einer Schaltungsanordnung durchgeführt, wie
diese in 6 dargestellt ist. Diese Schaltungsanordnung
verzögert
die eingehenden R-S
Blockdaten um zwei Blockintervalle, wie oben beschrieben, und benutzt
die Fehler und ihre in dem Fehlerberechnungsteil gefundene und in
den zwei Stapelspeichern gespeicherte Größe zum Durchführen der
Korrekturen. Wenn die Chien Suche durchgeführt wurde, erforderte die Auslösung der Chien
Suche, dass dies in der umgekehrten Reihenfolge der Blockstellen
gegenüber
derjenigen, in der die Daten eingetroffen sind, durchgeführt wird.
Deswegen wurden Stapelspeicher verwendet zum Speichern der Fehlerinformation,
und diese Stapelspeicher sind erforderlich zum Speichern der Fehlerstellen
und der Fehlerwerte in dem Fehlerberechnungsteil sowie in dem Fehlerkorrekturteil
des R-S Decoders (Daten müssen
in den Fehlerberechnungsschritten auf die Stapelspeicher "gedrückt" werden und in den
Fehlerkorrekturschritten aus den Stapelspeichern "hervorgeholt" werden). Wenn die
betreffenden Teile ihren Vorgang an dem R-S Block erledigt haben,
müssen
die Ergebnisse der Fehlerberechnung unmittelbar zu dem Fehlerkorrekturteil übertragen
werden. Da der Fehlerkorrekturteil nicht länger den Fehlerspeicherinhalt
braucht, wenn die Korrektur des ganzen Block beendet ist, können die
zwei Teile ihre betreffenden Fehlerstelle- und Fehlerwertstapelspeicher "Ping-Pong-artig" austauschen, so
dass die Fehlerkorrekturschaltung 28 die Ergebnisse der jüngsten Fehlerberechnung
empfängt
und danach mit der Korrektur eines neuen Blocks anfangen kann, und
der Fehlerberechnungsprozessor 60 empfängt seinerseits abgelegte Fehlerdaten,
die gelöscht
werden können,
damit für
neue Daten Raum geschaffen wird.
-
Die
GF Elemente, die mit jeder R-S Blockdatenstelle übereinstimmen, anfangend mit
der ersten Stelle in dem Datenblock, werden von einem Zähler erzeugt,
der zu dem Wert ausgelöst
wird, der mit dem Anfang des Blocks übereinstimmt, und zählt durch alle
Blockstellen in der richtigen (d.h. nicht umgekehrten) Reihenfolge.
Dies geschieht durch einen Vergleich jedes Stellenwertes mit dem
Inhalt der Spitze des Fehlerstellenstapelspeichers 66.
Wenn die zwei Werte einander gleich sind, entspricht die Λ(x) Wurzel
oben in dem Stapelspeicher der aktuellen Bytestelle in dem R-S Block.
Der Inhalt der Spitze des Datenwertstapelspeichers wird danach zu
dem Datenbyte an dieser Blockstelle hinzugefügt und in der GF(256) Arithmetik
besteht diese aus einem bitweisen Exklusiv-Oder-Gate der 8 Bits des Fehlerwertes mit
denen des Datenbytes. Die zwei Stapelspe3icher wer den danach hervorgeholt,
so dass das nächste Fehlerstelle-
und Fehlerwertpaar oben in dem Speicher ist und die Prozedur wiederholt
wird. Dies geschieht für
jedes Fehlerstelle- und Fehlerwertpaar, das in den Stapelspeichern
gespeichert ist, bis die Stapelspeicher leer sind, wobei zu diesem
betreffenden Zeitpunkt alle detektierten Fehler in dem R-S Block
korrigiert worden sind.
-
Zu
guter letzt dürfte
es einleuchten, dass die oben stehende Beschreibung nicht erschöpft ist
und dass im Rahmen der vorliegenden Erfindung Abwandlungen und Modifikationen
von dem Prozessor 60 durchgeführt werden können. So
ist beispielsweise die Länge
der Polynomspeicherregister als eine Länge gleich t + 1 für Λ(x) sowie
für das
Hilfspolynom B(x) und eine Länge
von 2t für Ω(x) beschrieben
worden. Dies bedeutet, dass das Polynomspeicherregister 61,
das Λ(x)
speichert, aus t + 1 Elementregistern für die t + 1 Koeffizienten von Λ(x) besteht.
Das Register 62 hat aber eine Länge von t + 1 Elementregistern,
wenn dies zum Speichern des Hilfspolynoms B(x) verwendet wird, braucht
aber 2t Elemente zum Speichern von Ω(x); folglich muss es die Fähigkeit haben,
für beide
Längen
konfiguriert zu sein; dies kann dadurch erfolgen, dass ein Multiplexer
verwendet wird, der das Elementregister selektiert, das mit dem
Koeffizienten übereinstimmt,
der die Polynomreihenfolge der gewünschten Länge hat.
-
Die
Fähigkeit,
die Länge
eines Polynomspeicherregisters zu modifizieren ist erforderlich
um die Notwendigkeit eines dritten Registers zu eliminieren (d.h.
zwei mit einer Länge
t + 1 für Λ(x) und B(x)
und ein drittes für Ω(x) und
für die
Möglichkeit,
ein Polynomspeicherregister zu jeder gewünschten Länge zu konfigurieren. Dies
könnte
in dem B-M Algorithmus verwendet werden, der Registerlänge als
einen Parameter spezifiziert, der sich im Laufe des Algorithmus ändert. Obschon
dies im Allgemeinen in der Praxis für Softwareimplementierung von
R-S Decodern verwendet wird, da dies ermöglicht, dass der Algorithmus
in weniger Durchgängen
vollendet wird, benutzen bekannte Hardwareimplementierungen Festlänge-Schieberegister.
-
Die
Anwendung eines derartigen verallgemeinerten Verfahrens zur Polynomspeicherregisterlängenmodifikation
in der Fehlerberechnungsprozessorarchitektur nach 4A,
die bereits für
minimale Hardware und für
maximale Datenübertragungsfähigkeit
optimiert worden ist, (d.h. alle zwei gewünschten Datenübertragungen
können
gleichzeitig stattfinden), wird ermöglichen, dass die erforderlichen
Fehlerberechnungen in noch weniger Taktzyklen als oben beschrieben
durchgeführt
werden können.
Der Grund dazu ist, dass jeder Vorgang, der ein Polynom erfordert,
einen Umlauf des kompletten Polynoms durch das Register erfordert
und dies wird aus den beiden Koeffizienten t + 1 oder 2t Koeffizienten
bestehen, sogar wenn die wirkliche Polynomlänge viel weniger ist als t
+ 1 oder 2t und viele dieser Koeffizienten sind deswegen Null; dies
bedeutet, dass die gleiche Anzahl (t + 1 oder 2t) Taktzyklen für jeden
Polynomvorgang erforderlich ist, ungeachtet der wirklichen Länge des
Polynoms.
-
Nun
wird die 4H näher betrachtet, die ein bevorzugtes
Polynomregisterspeicherelement zeigt, das, wegen der einzigartigen
Schaltungsanordnung die Einstellung der Polynomspeicherregisterlänge ermöglicht.
Insbesondere umfasst die Schaltungsanordnung vorzugsweise eine Flip-Flop-Schaltung 91 und
einen Multiplexer mit einem Inverter 92, zwei UND-Gattern 93, 94 und
einem ODER-Gatter 95. Diese Konfiguration ermöglicht es,
dass jedes beliebige Speicherelement in dem Polynomregister auf effektive
Weise "kurzgeschlossen" wird, wodurch die effektive
Länge des
Registers reduziert wird. Je nachdem die Durchführung des B-M Algorithmus fortschreitet,
werden weniger dieser Elemente "kurzgeschlossen", und das Polynomregister "wächst" dadurch in Länge, je nachdem der Registerlängenparameter
des B-M Algorithmus im Wert ansteigt. Steuerung der Registerlänge erfolgt
durch die (nicht dargestellte) Steuerschaltung des Fehlerberechnungsprozessors 60,
der alle Steuerfunktionen der Speicherregister, der arithmetischen
Einheiten (Multiplizierer/Teiler und Addierer) implementiert, und
die Datenstrecken, die durchgeführt
werden müssen
um die jeweiligen Algorithmen zu implementieren. Für den B-M
Algorithmus resultiert die Fähigkeit
zum Modifizieren der Polynomspeicherregisterlängen zu einer Reduktion der
erforderlichen Anzahl Taktzyklen um nahezu die Hälfte. Sie reduziert auch die
Anzahl Taktzyklen, die erforderlich sind zum Berechnen des Fehlerbewertungspolynoms Ω(x) um etwa
ein Drittel. Ein Nachteil dieser Fähigkeit ist aber, dass es sein
kann, dass durch die zusätzliche
Komplexität
der und der Fortpflanzungsverzögerungen
in den Datenstrecken die maximale Taktfrequenz, bei der der Prozessor
betrieben werden kann, reduziert wird.
-
Ein
alternatives Verfahren zum Durchführen der Fehlerkorrektur, das
angewandt wird, ist in 7 dargestellt. In diesem Schema
besteht die Fehlerberechnung nur aus der Berechnung von Fehlerortungs-
und Fehlerbewertungspolynomen, und zwar unter Verwendung entweder
des B-M Logarithmus oder anderer Mittel (wie des euklidischen Logarithmus),
und die Chien Suche wird während
der wirklichen Fehlerkorrektur unter Verwendung von Hardware entsprechend
der aus den 5A-5B. Auch
hier kann die4ee Schaltungsanordnung wieder zum Bewerten von Λ(x) und der
Abgeleiteten xΛ'(x) gleichzeitig
verwendet werden. Eine ähnliche
Schaltungsanordnung, die aus 2t – 1 Registern und GF Konstante-Multiplizierern
besteht, wird zum gleichzeitigen Bewerten von Ω(x) verwendet. Wenn eine Wurzel
von Λ(x)
gefunden wird, werden die Werte von xΛ'(x) und Ω(x), die der Wurzel entsprechen,
in einen GF Teiler eingegeben, der den Forney Algorithmus implementiert
und die Fehlergröße ausliefert. Diese
Größe wird
danach zu dem fehlerhaften Datenbyte hinzuaddiert, und zwar auf
dieselbe Art und Weise wie oben beschrieben, zum Durchführen der
Korrektur. Ein großer
Nachteil dieser Technik ist, dass, da die Chien Suche mit dem Wert
der letzten R-S Blockstelle ausgelöst werden muss, werden die
Suche und die Bewertungen in umgekehrter Blockreihenfolge durchgeführt. Dies
erfordert, dass eine Umkehrung des R-S Blocks für die Korrektur durchgeführt wird,
sowie eine zweite Umkehrung nachher, wenn eine nachfolgende Datenverarbeitung
erfordert, dass der Block in der ursprünglichen Reihenfolge ist.
-
Das
Verfahren nach 7 hat den Vorteil aber, dass
alle Fehlerberechnungen nach der Erzeugung der Fehlerortungs- und
Fehlerbewertungspolynome während
der Fehlerkorrekturphase und deswegen in Echtzeit durchgeführt werden.
Dies bedeutet, dass die Fehlerberechnungsphase in weniger Zeit durchgeführt werden
kann (d.h. in weniger Taktzyklen), da die Bewertung des Fehlerbewertungspolynoms
und des Forney Algorithmus nicht länger in dem Fehlerberechnungsteil
durchgeführt
werden.
-
Der
Prozessor 60 kann verwendet werden zum Berechnen der erforderlichen
Polynome, und zwar auf die oben beschriebene Art und Weise, wobei
auch hier wieder ein minimaler Betrag an Hardware und Taktzyklen
verwendet wird. Wegen der Fähigkeit
dieser Architektur zum Durchführen
eines breiten Bereichs an GF Vorgängen aber, kann sie auch dazu
verwendet werden, alle einzelnen Terme der beiden Polynome für den R-S
Blockstellenwert zu bewerten, der dem Anfang des Blocks entspricht,
die Chien Suche kann an dieser Stelle gestartet werden und kann
in der wirklichen Blockreihenfolge durchgeführt werden, ohne dass eine
Umkehrung erforderlich ist. Berechnung der Polynomterme besteht
aus Gf Multiplikation jedes Koeffizienten mit der entsprechenden
Potenz der Polynomvariablen, was in diesem Fall der ersten Stelle
des R-S Blocks entspricht. Da die Größe des Blocks fest ist, können die
ersten 2t Potenzen dieses ersten Stellenwertes während des Entwurfs des Decoders
berechnet und als die Polynomargumente in dem Speicher 76 (4A) gespeichert
werden. Diese Werte sind vorzugsweise "hart" und
können
auf diese Weise in einem kleinen (2t Byte) Festwertspeicher gespeichert
werden. Wie oben, werden die Polynomkoeffizienten in ihren betreffenden
Speicherregistern (61 und 62) gespeichert, so
dass die t + 1 Terme des Λ(x)
Polynoms und die 2t Terme des Ω(x)
Polynoms durch Multiplikation jedes Koeffizienten mit dem entsprechenden
Polynomargument in dem Speicher 76 berechnet werden können. Für diese
zwei Polynome sind 3t – 1
Taktzyklen erforderlich, was viel weniger ist als die t(2t + 1) Fehlerberechnungstaktzyklen,
die durch Anwendung dieses Verfahrens eliminiert sind. Die resultierenden Polynomterme
werden danach benutzt zum Auslösen
der Chien Suche und der Bewertung, die in dieser Anordnung die wirkliche
Suche nach und die Korrektur von Fehlern gleichzeitig durchführt, wie
oben beschrieben. Diese Auslösung
erfolgt5 durch Übertragung
der Anfangspolynomterme zu der Hardware für die Chien Suche/Fehlerkorrektur
nach 7.
-
Die
Anwendung der Polynomprozessorarchitektur in dem Fehlerberechnungsteil
schafft ein Mittel zum Eliminieren der Notwendigkeit einer R-S Blockumkehrung,
insbesondere in dem Fall, dass der Decoder für einen bestimmten R-S Code
entworfen worden ist (wie für
die GA-Norm). Sie dient auch zur Erläuterung der Flexibilität und im
Allgemeinen zur Erläuterung
dieser Architektur.
-
Der
Vorteil dieses Verfahrens ist, dass, da der Forney Algorithmus nicht
als Teil der Fehlerberechnung durchgeführt wird, weniger Taktzyklen
erforderlich sind; dies kann wertvoll sein in Fällen, in denen der R-S Block
nicht sehr groß ist,
sowie wenn Zeitlücken
zwischen R-S Blöcken
nicht erlaubt sind. Ein Nachteil ist, dass dies zusätzliche
Hardware für eine
schnelle Bewertung des Ω(x)
Polynoms und für die
Auslösung
von Λ(x)
und Ω(x)
erfordert, nebst einem zweiten Teiler für den Forney Algorithmus. Deswegen
ist es nur unter begrenzten Umständen
wertvoll, aber in einigen Fällen
kann die Verbesserung in der Leistung ausreichen um die zusätzliche
Hardware zu rechtfertigen.
-
Die
vorliegende Erfindung eignet sich zur effizienten Implementierung
in einer integrierten Schaltung, und kann im Falle großer Datenblöcke ein
Fortschritt in dem Stand der Technik des Reed Solomon Decoders darstellen.