DE69409418T2

DE69409418T2 - Vorrichtung und Verfahren zur Ableitung von Polynomialmengen

Info

Publication number: DE69409418T2
Application number: DE69409418T
Authority: DE
Inventors: Keiichi Iwamura
Original assignee: Canon Inc
Current assignee: Canon Inc
Priority date: 1993-01-22
Filing date: 1994-01-21
Publication date: 1998-08-20
Anticipated expiration: 2014-01-22
Also published as: US5535140A; EP0611054A3; DE69409418D1; EP0611054A2; EP0611054B1

Description

Diese Erfindung bezieht sich auf eine Fehlerkorrektur, bei der Fehler in einen digitalen Kommunikationssystem und einem digitalen Speichersystem, die in einem Kommunikationskanal oder Speichermedium erzeugt werden, an der Empfangsseite unter Verwendung von Fehlerkorrekturcodes korrigiert werden. Insbesondere bezieht sich die Erfindung auf eine Vorrichtung und ein Verfahren zur Ableitung von Polynommengen, wobei in einer Decodieroperation unter Verwendung algebraischer geometrischer Codes als Fehlerkorrekturcodes eine Menge minimaler Polynome zur Erzeugung einer gegebenen mehrdimensionalen Matrix entsprechend einem Syndrom in empfangenen Worten erhalten wird.
RS (Reed-Solomon codes) Codes und BCH (Bose-Chaudhuri- Hocquenghem) Codes sind als Fehlerkorrekturcodes zur Korrektur von Fehlern, die in einem Kommunikationskanal oder einem Speichermedium an der Empfangsseite in einem digitalen Kommunikationssystem und einem digitalen Speichersystem erzeugt werden, wohlbekannt. Diese Codes werden derzeit in Geräten verwendet, die mit Kompaktdisks, Satellitenkommunikation und dergleichen zu tun haben.
Kürzlich wurden jedoch Codes weitverbreitet studiert, die algebraische geometrische Codes genannt werden, die die algebraische Kurventheone verwenden (siehe Verweisungen (1)-(3)). Algebraisch geometrische Codes gehören zu einem Codesystem, das einen sehr breiten Anwendungsbereich hat und das die oben beschriebenen RS- Codes und BCH-Codes umfaßt. Es wurde allmählich klar, daß dieses System neue Codes umfaßt, die bessere Eigenschaften als diejenigen von herkömmlichen Codes haben (siehe Verweisung (4)).
Decodierverfahren waren immer ein Problem, obwohl solche hervorragenden Codes entdeckt wurden, und es wurde nach einer Entwicklung eines effizienten Decodieralgorithmus verlangt. Jedoch wurde überhaupt kein effizienter Decodieralgorithmus erhalten, bis Justesen et al einen generalisierten Peterson Algorithmus (Siehe Verweisung (5)) 1989 vorgeschlagen hatte. Justesen et al haben gezeigt, daß durch Anwendung des Sakataalgorithmus (Siehe Verweisung (6)), vorgeschlagen durch Sakata, auf deren generalisierten Petersonalgorithmus zur Schaffung eines effizienten Algorithmus zum Erhalten eines zweidimensionalen linearen Rückkopplungsverschieberegister (feedback shift register), der eine minimale Anzahl an Speicherelementen zur Erzeugung eines zweidimensionalen Feldes mit einer gegebenen finiten Größe hat, eine Fehlerlokalisierfunktion bei einer hohen Geschwindigkeit mit einem geringen Rechenaufwand abgeleitet werden kann.
Da jedoch der generalisierte Peterson Algorithmus in seiner Korrekturfähigkeit begrenzt ist, haben Skorobogatov et al einen modifizierten Decodieralgorithmus (Siehe Verweisung (7)) vorgeschlagen, der eine höhere Korrekturfähigkeit garantiert.
Da des weiteren der Sakataalgorithmus eine große Menge nutzloser Berechnung umfaßt, die sich nicht direkt auf den modifizierten Decodieralgorithmus bezieht, haben Kamiya ef al. 1992 einen Algorithmus vorgeschlagen, der durch Modifizieren des Sakataalgorlthmus erhalten wird, um ihn an den modifizierten Decodieralgorithmus anzupassen (Siehe Verweisungen (8) und (9)).
Andererseits sind der Berlekamp-Massey Algorithmus (EH- Verfahren) und der euklidische Algorithmus (Eu-Verfahren) als herkömmliche Decodierverfahren für RS Codes und BCH Codes wohlbekannt. Der oben beschriebene generalisierte Peterson Algorithmus ist eine Erweiterung des Peterson Verfahrens, das zur Decodierung von RS-Coden verwendet wird. Der Sakataalgorithmus wird auch zweidimensionales EM-Verfahren genannt und ist als Erstreckung des BM-Verfahrens wohlbekannt, das zur Decodierung von RS Codes verwendet wird (im nachfolgenden als eindimensionales BM-Verfahren bezeichnet).
Jedoch wurde vorher kein Algorithmus in Erwägung gezogen, der einer Erweiterung des Eu-Verfahrens entspricht, das zur Decodierung von RS-Codes verwendet wird (im nachfolgenden als eindimensionales Eu-Verfahren bezeichnet).
Obwohl auch Sakata ein mehrdimensionales BM-Verfahren als eine Erweiterung des zweidimensionalen BM-Verfahrens vorgeschlagen hat (Siehe Verweisung (8)), hatte man sich kein mehrdimensionales Eu-Verfahren ausgedacht, das jenem Verfahren entsprach.
Das mehrdimensionale BM-Verfahren wird durch einen Algorithmus ausgedrückt, der eine Struktur hat, wie sie in Fig. 2 gezeigt ist (Siehe Verweisungen (6) und (10) für ein Verfahren zur Bestimmung eines Definitionspunktes, rs, rt und dergleichen)
Der Punkt n, der in Fig. 2 gezeigt ist, wird durch Ordnen aktualisiert, das als Gesamtordnung bezeichnet wird (siehe Verweisungen (6) und (10)). In Fig. 2 werden die Berechnung von dfn(i) in Schritt S22 und die Aktualisierung von fn(i) unter Verwendung von h in Schritt S25 sequentiell durchgeführt. Der Grund dafür ist, daß die Berechnung von dfn(i) in Schritt S22 bei Punkt n unter Verwendung von h durchgeführt wird, das in Schritt S24 bei Punkt
n-1 erhalten wird, und daß das Aktualisieren von fn(i) unter Verwendung von h in Schritt S24 bei Punkt n unter Verwendung von
dfn(i) in Schritt S22 bei Punkt n berechnet wird. In diesen Fall wird, wie in Fig. 12 gezeigt ist, eine nutzlose Zeit in der Verarbeitungszeit erzeugt und deshalb ist ein solches Verfahren nicht effizient.
Andererseits wurde ein Verfahren vorgeschlagen, bei dem die Prozesse der Schritte S22 und S24 parallel ausgeführt werden unter Verwendung jenes Prozesses für eindimensionale Variablen in dem eindimensionalen BM-Verfahren, das ein Decodierverfahren für
RS-Codes und BCH-Codes ist, was sequentiell durchgeführt wird (Siehe Verweisung (11)). Da jedoch dieses Verfahren Verschieberegister verwendet, die eine fixierte Anzahl an Stufen haben, (t+1) (t ist der Maximalwert des Definitonspunktes am Endpunkt (n = p: Siehe Fig. 2) des Polynoms fn(i) sind immer Verarbeitungstaktpulse für einen einzelnen Aktualisiervorgang (Zyklus) von
fn(i) erforderlich.
Dementsprechend erfordert das Gerät aus Verweisung (9) nutzlose Verarbeitungstaktpulse in der mittleren Berechnung (n < p) von fn(i), was nicht der größte Definitionspunkt ist. Des weiteren berücksichtigt das Verfahren aus Verweisung (9) nicht das mehrdimensionale BM-Verfahren und ist deshalb für das mehrdimensionale BM-Verfahren in den folgenden Punkt ungeeignet:
1) Nur ein Polynom gehört zu allen Polynommengen F und G in dem eindimensionalen BM-Verfahren, aber eine Mehrzahl an Polynomen gehört zu allen Polynommengen F und G in dem mehrdimensionalen BM-Verfahren.
2) In dem eindimensionalen BM-Verfahren können jeweilige Koeffizienten sequentiell in einem eindimensionalen Speicher vom höchsten Grad gespeichert werden (ein Verschieberegister oder dergleichen), da der Grad der Polynome, die zu den Polynommengen F und G gehören, und die Anordnung eines gegebenen Feldes eindimensional sind (eine Variable). Da jedoch die Grade der Polynome und die Anordnung des Feldes in dem mehrdimensionalen BM-Verfahren nicht eindimensional sind, kann eine effiziente Verarbeitung mit einem eindimensionalen Speicher nicht durchgeführt werden.
3) In dem eindimensionalen BM-Verfahren ist eine Parallelverarbeitung von Polynomen sinnlos, da nur ein Polynom zu jeden der Polynommengen F und G gehört. Da jedoch in dem mulitdimensionalen BM-Verfahren eine Mehrzahl von Polynomen zu einer jeden der Polynommengen F und G gehört, hat eine Parallelverarbeitung der Berechnung der Polynome einen Sinn.
4) In dem eindimensionalen BM-Verfahren können die Prozesse der Schritte S22 und 523 nicht parallel durchgeführt werden, wenn die Berechnung für eine Variable parallel durchgeführt wird, da nur eine Variable in einem Polynom vorliegt, das zu jedem der Polynommengen F und G gehört. In dem mehrdimensionalen BM-Verfahren können jedoch die Prozesse der Schritte S22 und S24 parallel durchgeführt werden, wenn die Berechnung für eine Variable parallel durchgeführt wird, da eine Mehrzahl von Variablen in einem Polynom vorliegen, das zu jedem der Mengen an Polynome F und G gehört.

Verweisungen

(1) V.D. Goppa: "Codes on Algebraic Curves", Soviet Math. Dokl., 24, Seiten 170 - 172, 1981.
(2) V.D. Goppa: " Algebraic-geometric Codes", Math. U.S.S.R. Izvestiya, vol. 21, Nr. 1, Seiten 75 - 91, 1983.
(3) V.D. Goppa: "Geometry and Codes", Kluwer Academic Publishers, 1988.
(4) M.A. Tsfasman and S.G. Vladut: "Algebraic-geometric Codes", Kluwer Academic Publishers, 1991.
(5) J. Justesen, K.J. Larsen, E. Jensen, A. Havemose and T. Hoholdt: "Construction and Decoding of a Class of Algebraic Geometry Codes", IEEB Trans. Inform. Theory, vol. 35, Nr. 4, Seiten 311 - 821, Juli 1989.
(6) Sakata: "Synthesis of a Two-dimentional Linear Feedback Shift Register for Generating a Given Twodimensional Array", Übersetzung des Instituts der japanischen Elektro- und Kommunikationsingenieure (A), vol. J-70A, Seiten 903 - 910, 1987.
(7) A.N. Skorobogatov und S.G. Vladut: "On the Decoding of Algebraic Geometric Codes", LEBE Trans. Inform. Theory, vol. 36, Nr. 5, Seiten 1051 - 1060, Sept. 1990.
(8) S. Sakata: "Extension of the Berlekamp-Massey Algorithm to N Dimensions", Information and Computation, Vol 84, Seiten 207 - 239, 1990.
(9) Kamiya und Niura: "On the Application of the Sakata Algorithm for the Modified Decoding Algorithm Relating to Some Sort of Algebraic Curve Codes", technischer Bericht des Instituts der japanischen Elektro- und Kommunikationsingenieure, vol. IT91, Nr. 435, IT91 - 96, Seiten 47 - 54, 1992.
(10) Kamiya und Miura: "A Recurrent Decoding Algorithm Relating to Some Sort of Algebraic Curbe Codes", technischer Bericht des Instituts der japanischen Elektro- und Kommunikati onsingenieure, vol. IT91, Nr. 505, IT91 - 116, Seiten 89 - 96, 1992.
(11) Youzhi Xu: "Constributions to the Decoding of Reed- Solomon and Related Codes" Linkoping Studies in Science and Technology. Dissertationen Nr. 257, 1991.
Es ist eine Aufgabe der vorliegenden Erfindung, alternative Verfahren zur Ableitung einer Menge minimaler Polynome zur Erzeugung einer gegebenen mehrdimensionalen Matrix zu schaffen. Die vorliegende Erfindung zielt darauf ab, die gesamte Verarbeitungszeit, die erforderlich ist, um eine Menge minimaler Polynome zu erzeugen, durch ein Berechnungsverfahren zu reduzieren,
durch das Parallelverarbeitung ermöglicht wird.
Unterschiedliche Aspekte der vorliegenden Erfindung schaffen ein zweidimensionales Eu Verfahren, entsprechend einer Erweiterung des eindimensionalen Eu Verfahrens, und schaffen ein mehrdimensionales Eu Verfahren, entsprechend dem mehrdimensionalen BM-Verfahren durch Erweiterung dieses zweidimensionalen Eu Verfahren.
In bestimmten Aspekten schafft die Erfindung ein Verfahren zur effizienten Durchführung paralleler Verarbeitungsschritte einer Mehrzahl an Prozessen in dem mehrdimensionalen BM-Verfahren und eine Vorrichtung zur Verwirklichung dieses Verfahrens.
Ein Ausführungsbeispiel der vorliegenden Erfindung bezieht sich auf eine Vorrichtung zur Ableitung von Polynommengen zur Erzielung einer Menge minimaler Polynome zur Erzeugung einer gegebenen mehrdimensionalen Matrix, aufweisend
eine erste Speichervorrichtung zur Speicherung einer ersten Menge zu erhaltender Polynome;
eine zweite Speichervorrichtung zum Speichern einer ersten Menge von Hilfspolynomen für die erste Polynommenge;
eine dritte Speichervorrichtung zur Speicherung einer zweiten Menge an Polynomen, die unterschiedlich zur ersten Polynommenge sind;
eine vierte Speichervorrichtung zur Speicherung einer zweiten Menge von Hilfspolynomen für die zweite Polynommenge;
eine erste Unterscheidungsvorrichtung zur Unterscheidung, ob der Koeffizient eines vorbestimmten Grades eines jeden Polynoms der in der dritten Speichervorrichtung gespeicherten zweiten Polynommenge gleich Null ist;
eine Bestimmungsvorrichtung zur erneuten Bestimmung eines Definitionspunktes, wenn ein Polynom, bei dem der Koeffizient eines vorbestimmten Grades nicht gleich Null ist, als ein Ergebnis der Unterscheidung durch die erste Unterscheidungsvorrichtung vorliegt;
eine erste Ableitungsvorrichtung zum Ableiten von Polynomen, die zur zweiten Polynommenge gehören, basierend auf dem Wert des Def initonspunktes, der durch die Bestimmungsvorrichtung bestimmt wurde, auf der in der dritten Speichervorrichtung gespeicherten zweiten Polynommenge und auf der in der vierten Speichervorrichtung gespeicherten zweiten Menge an Hilfspolynomen;
eine erste Aktualisiervorrichtung zur Löschung aller Poly nome, in denen der Koeffizient eines vorbestimmten Grades nicht gleich Null ist aus der dritten Speichervorrichtung, und zur Speicherung der Polynome, die durch die erste Ableitungsvorrichtung in der dritten Speichervorrichtung abgeleitet wurden,
eine zweite Ableitungsvorrichtung zum Ableiten von Polynomen, die zur ersten Polynommenge gehören, basierend auf dem Wert des Definitonspunktes, der durch die Bestimmungsvorrichtung bestimmt wurde, auf der in der ersten Speichervorrichtung gespeicherten ersten Polynommenge, auf der ersten Menge an in der zweiten Speichervorrichtung gespeicherten Hilfspolynome und dem Koeffizienten eines Polynoms der zweiten Polynommenge, der sich auf den festgestellten Definitionspunkt bezieht;
eine zweite Aktualisiervorrichtung zur Löschung aller Polynome, die den Polynomen entsprechen, die durch die erste Aktualisiervorrichtung aus der ersten Speichervorrichtung gelöscht wurden, und zur Speicherung der Polynome, die durch die zweite Ableitungsvorrichtung in der ersten Speichervorrichtung abgeleitet wurden;
eine zweite unterscheidungsvorrichtung zum Unterscheiden des Vorliegens einer Änderung des Definitionspunktes;
eine dritte Aktualisiervorrichtung zur Aktualisierung der ersten Menge an Hilfspolynomen, die in der zweiten Speichervorrichtung gespeichert sind, basierend auf der ersten Menge an Hilfspolynomen, die in der zweiten Speichervorrichtung gespeichert sind, und der Polynome, die durch die zweite Aktualisiervorrichtung gelöscht wurden, wenn die zweite Unterscheidungsvorrichtung das Vorliegen einer Veränderung des Definitionspunktes unterschieden hat; und
eine vierte Aktualisiervorrichtung zur Aktualisierung der ersten Menge an Hilfspolynomen, die in der zweiten Speichervorrichtung gespeichert sind, basierend auf der zweiten Menge an Hilfspolynomen, die in der vierten Speichervorrichtung gespeichert sind, und der Polynome, die durch die erste Aktualisiervorrichtung gelöscht wurden, wenn die zweite Unterscheidungsvorrichtung das Vorliegen einer Veränderung des Definitionspunktes unterschieden hat.
Ein anderes Ausführungsbeispiel bezieht sich auf ein Verfahren zum Erhalten von Mengen an minimalen Polynemen zur Erzeugung einer gegebenen mehrdimensionalen Matrix, wobei das Verfahren die folgenden Schritte aufweist:
Setzen von Anfangswerten für einen ersten Speicher zur Speicherung einer ersten Polynommenge, die erhalten werden soll, einen zweiten Speicher zur Speicherung einer ersten Menge an Hilispolynomen für die erste Polynommenge, einen dritten Speicher zur Speicherung einer zweiten Menge an Polynomen, die sich von der ersten Menge Polynome unterscheidet, und einen vierten Speicher zur Speicherung einer zweiten Menge an Hilfspolynomen für die zweite Menge an Polynomen;
Unterscheiden, ob der Koeffizient eines vorbestimmten Grades eines jeden Polynoms der zweiten Menge an Polynome, die im dritten Speicher gespeichert sind, gleich Null ist;
erneutes Bestimmen eines Definitionspunktes, wenn ein Polynom, in dem der Koeffizient eines vorbestimmten Grades nicht gleich Null ist, als ein Ergebnis der Unterscheidung vorliegt;
Ableiten von Polynomen, die zur zweiten Menge an Polynomen gehören, basierend auf dem Wert des festgestellten Definitionspunktes, der zweiten Menge an Polynomen, die in dem dritten Speicher gespeichert sind, und der zweiten Menge an Hilfspolynomen, die im vierten Speicher gespeichert sind;
Löschen aller Polynome, in denen der Koeffizient eines vorbestimmten Grades nicht gleich Null ist, und Aktualisieren des dritten Speichers durch Speicherung der Polynome, die durch die erste Ableitungsvorrichtung abgeleitet wurden;
Ableiten von Polynomen, die zur ersten Menge an Polynomen gehören, basierend auf dem Wert des festgestellten Definitions punktes, der ersten Menge an Polynomen, die in dem ersten Speicher gespeichert sind, der ersten Menge an Hilfspolynomen, die in den zweiten Speicher gespeichert sind, und dem Koeffizient eines Polynoms der zweiten Menge an Polynome, der sich auf den festgesetzten Definitionspunkt bezieht;
Löschen aller Polynome, die den Polynomen entsprechen, die durch den Aktualisiervorgang des dritten Speichers gelöscht wurden, und Aktualisieren des ersten Speichers durch Speicherung der abgeleiteten Polynome;
Unterscheiden des Vorliegens einer Veränderung des Definitionspunktes;
Aktualisieren der ersten Menge an Hilfspolynomen, die in dem
zweiten Speicher gespeichert sind, basierend auf der ersten Menge an Hilfspolynomen, die in dem zweiten Speicher gespeichert sind, und den Polynomen, die durch den Aktualisiervorgang des ersten Speichers gelöscht wurden, wenn unterschieden wurde, daß der Definitionspunkt durch den Unterscheidungsvorgang verändert wurde; und
Aktualisieren der ersten Menge an Hilfspolynomen, die in dem zweiten Speicher gespeichert sind, basierend auf der zweiten Menge an Hilfspolynomen, die in dem vierten Speicher gespeichert sind, und den Polynomen, die durch den Aktualisiervorgang des dritten Speichers gelöscht wurden, wenn unterschieden wurde, daß sich der Definitionspunkt verändert hat.
Ein noch anderes Ausführungsbeispiel bezieht sich auf eine Vorrichtung zur Ableitung von Polynommengen zur Erhaltung einer Menge minimaler Polynome zur Erzeugung einer gegebenen mehrdimensionalen Matrix, wobei die Vorrichtung folgendes aufweist:
eine Matrixspeichervorrichtung zum Speichern einer gegebenen mehrdimensionalen Matrix u;
eine erste Polynomspeichervorrichtung zur Speicherung einer Menge an Polynome F, die erhalten werden sollen;
eine zweite Polynomspeichervorrichtung zur Speicherung einer Menge an Hilfspolynomen G für die Menge der Polynome F;
eine erste Berechnungsvorrichtung zur Erhaltung von Polynomen f(k), die zu der Menge der Polynome F gehören, basierend auf den Polynomen f(i), die in der ersten Polynomspeichervorrichtung gespeichert sind, von Polynomen g(j), die in der zweiten Polynomspeichervorrichtung gespeichert sind, und von Ableitungen der Polynome dfn(i);
eine zweite Berechnungsvorrichtung zur Erhaltung von Abweichungen der Polynome dfn+1(k), basierend auf den Koeffizienten der Polynome f(k), die durch die erste Bereohnungsvorrichtung berechnet wurden und auf der nehrdimensionalen Matrix u, die in der Matrixspeichervorrichtung gespeichert wurden; und
eine Steuervorrichtung zur parallelen Steuerung von Zugriffsvorgängen für die erste Polynomspeichervorrichtung und die zweite Polynomspeichervorrichtung und zugegriffener Adressen, in Abhängigkeit von den Graden der Polynome f(k). Die Berechnung durch die erste Berechnungsvorrichtung und die Berech nung durch die zweite Berechnungsvorrichtung werden parallel ausgeführt.
Noch ein anderes Ausführungsbeispiel bezieht sich auf ein Verfahren zur Erhaltung einer Menge minimaler Polynome zur Erzeugung einer gegebenen mehrdimensionalen Matrix, wobei das Verfahren die folgenden Schritte aufweist:
Speichern einer gegebenen mehrdimensionalen Matrix u in einem Matrixspeicher;
Erhalten von Polynomen f(k), die zu einer Menge von Polynomen F gehört, die erhalten werden sollen, basierend auf Polynomen f(i), die in einem ersten Polynomspeicher zur Speicherung der Menge von Polynomen F gespeichert sind, auf Polynomen g(j), die in einem zweiten Polynomspeicher zur Speicherung einer Menge von Polynomen G gespeichert sind, die unterschiedlich zu der Menge von Polynomen F sind, und auf Abweichungen der Polynome
Erhalten von Abweichungen von Polynomen dfn+1(k), basierend auf den Polynomen f(k), die durch die erste Berechnungsvorrichtung und die mehrdimensionale Matrix u, die in dem Matrixspeicher gespeichert sind, erhalten werden; und paralleles Steuern von Zugangsvorgängen für den ersten Polynomspeicher, den zweiten Polynomspeicher und zugegriffenen Adressen, in Abhängigkeit von Graden von den Polynomen f(k), und paralleles Ausführen der ersten und zweiten Berechnungsvorgänge.
Andere Aufgaben und Vorteile neben denjenigen, die oben diskutiert wurden, sollen den Fachleuten aus der Beschreibung der spezifischen Ausführungsbeispiele der Erfindung, die nun folgt, klar werden. In der Beschreibung wird auf die beigefügten Zeichnungen Bezug genommen, die einen Teil davon bilden und die Beispiele der Erfindung veranschaulichen. Solche Beispiele sind jedoch nicht erschöpfend an verschiedenen Ausführungsbeispielen der Erfindung und deshalb wird auf die Ansprüche Bezug genommen, die der Beschreibung folgen, zur Bestimmung des Umfangs der Erfindung.

Kurze Beschreibung der Zeichnungen

Fig. 1 ist ein mehrdimensionaler Matrix Erzeugungskreislauf gemäß der vorliegenden Erfindung;
Fig. 2 ist ein mehrdimensionaler Matrix- Erzeugungsalgorithmus gemäß einem herkömmlichen BM-Verfahren;
Fig. 3 ist ein mehrdimensionaler Matrix- Erzeugungsalgorithmus gemäß dem Eu Verfahren der vorliegenden Erfindung;
die Figuren 4(a) und 4(b) sind Diagramme, die die Funktion des herkömmlichen EH-Verfahrens veranschaulichen;
die Figuren 5(a) und 5(b) sind Diagramme, die die Funktion des Eu Verfahrens der vorliegenden Erfindung veranschaulichen;
Fig. 6 ist ein Algorithmus eines mehrdimensionalen BM- Verfahrens gemäß der vorliegenden Erfindung;
die Figuren 7(a) bis 7(c) sind Diagramme, die die Funktion veranschaulichen, wenn der Algorithmus, der in Fig. 6 gezeigt ist, ausgeführt wird;
Fig. 8 veranschaulicht ein erstes Ausführungsbeispiel des Algorithmus der in Fig. 6 gezeigt ist;
Fig. 9 veranschaulicht ein zweites Ausführungsbeispiel des Algorithmus, der in Fig. 6 gezeigt ist;
Fig. 10 ist ein Diagramm, das eine Adressaufteilung in einem Speicher veranschaulicht;
Fig. 11 ist ein drittes Ausführungsbeispiel des Algorithmus, der in Fig. 6 gezeigt ist;
Fig. 12 ist ein Diagramm, das die Funktion veranschaulicht, wenn der Algorithmus, der in Fig. 2 gezeigt ist, ausgeführt wird;
Fig. 13 ist ein Diagramm, das die Konfiguration eines Gerätes zur Decodierung algebraisch geometrischer Codes veranschaulicht; und
Fig. 14 ist ein Flußdiagramm, das eine Decodierprozedur der Decodierverarbeitungseinheit, die in Fig. 13 gezeigt ist, zeigt.

Beschreibung der bevorzugten Ausführungsbeispiele

Fig. 13 ist ein Diagramm, das die Konfiguration einer Vorrichtung zur Decodierung algebraisch geometrischer Codes veranschaulicht. In Fig. 13 umfaßt eine Eingangseinheit 131 eine Empfangsvorrichtung zum Empfang von Daten von einer Satelliten sendung oder einem Kommunikatiosnetzwerk, einen Lesekreislauf zum Lesen von Daten aus einem Speichermedium wie einer CD (Kompakt-Disk) oder dergleichen, und dergleichen, und gibt empfangene Wörter, die Bilddaten oder Stimmendaten entsprechen, ein. Eine Decodierverarbeitungseinheit 132 decodiert die empfangenen Wörter, die in die Eingangseinheit 131 eingegeben wurden. Eine Ausgabeeinheit 133 gibt decodierte Daten aus und umfaßt eine Anzeige zum Anzeigen von Bilddaten, einen Lautsprecher zum Ausgeben decodierter Stimmendaten und dergleichen.
Fig. 14 ist ein Flußdiagramm, das eine Decodierprozedur einer Decodierverarbeitungseinheit 132 veranschaulicht. In dem vorliegenden Ausführungsbeispiel, wie in dem Fall der Decodier RS- Codes, wird das Decodieren algebraisch geometrischer Codes durch die nachfolgende Prozedur durchgeführt, wenn eine Löschkorrektur nicht enthalten ist. Zuerst wird in Schritt S141 eine Serie empfangener Worte, die eine vorbestimmte Größe haben, die als eine Decodiereinheit dienen, eingegeben. Im Schritt S142 wird aus den empfangenen Wortserien ein Syndrompolynom u (z) erzeugt. In diesem Schritt wird eine mehrdimensionale Matrix u entsprechend den Koeffizienten des Polynoms erzeugt. In Schritt S143 werden eine Menge an Fehlerlokalisierpolynomen F und eine Menge an Fehlerwertpolynomen B von der mehrdimensionalen Matrix u abgeleitet. Beim Schritt S144 wird ein Fehler an der Stelle des Fehlers in den empfangenen Wörtern korrigiert, der von der Menge der Fehlerlokalisierpolynome F erhalten wird, basierend auf dem Wert oder dem Fehler, der von der Menge der Fehlerwertpolynome B erhalten wurde.
Nun wird ein Verfahren und eine Vorrichtung zur Ableitung der Menge an Fehlerlokalisierpolynomen F und der Menge an Fehlerwertpolynomen B aus der mehrdimensionalen Matrix u beschrieben.
Zu diesem Zweck wird ein zweidimensionales Eu Verfahren entsprechend einer Ausdehnung des eindimensionalen Eu Verfahrens vorgeschlagen.
Es wird gezeigt, daß das zweidimensionale Eu Verfahren Resultate ausgibt, die äquivalent zu denjenigen des Sakataalgorithmus sind, der das zweidimensionale BM-Verfahren ist, und des Kamiyaalgorithmus, der ein modifizierter Algorithmus des Sakataalgorithmus ist. Desweiteren wird durch Ausdehnung des zweidimensionalen Eu Verfahrens ein mehrdimensionales Eu Verfahren entsprechend dem mehrdimensionalen EH-Verfahren vorgeschlagen.
Es wird auch gezeigt, daß das mehrdimensionale Eu Verfahren der vorliegenden Erfindung ein Algorithmus ist, der Effekte hat, die zu denjenigen des herkömmlichen mehrdimensionalen BM- Verfahrens unterschiedlich sind, beim Vorsehen eines Gerätes und hoher Geschwindigkeit, und Unterschiede zwischen diesen zwei Verfahren werden beschrieben.
Der bekannte herkömmliche Algorithmus des mehrdinensionalen BM-Verfahrens hat die Struktur, wie sie in Fig. 2 gezeigt ist. Andererseits hat der Algorithmus des mehrdimensionalen Eu- Verfahrens der vorliegenden Erfindung die Struktur, die in Fig. 3 gezeigt ist. Das mehrdimensionale BM-Verfahren unterscheidet sich von dem mehrdimensionalen Eu Verfahren dadurch, daß bei dem mehrdimensionalen BM-Verfahren dfn(i) in Schritt S22 direkt berechnet werden und die Polynommenge F unter Verwendung der berechneten Werte in Schritt S25 aktualisiert wird, während dfn(i) in dem mehrdimensionalen Eu Verfahren nicht direkt berechnet wird und die Polynommenge B im Schritt S34 aktualisiert wird und die Polynommenge F in Schritt S35 aktualisiert wird, unter Verwendung des Koeffizienten des höchsten Grades di der Polynome, die zur neu eingeführten Menge an Polynomen B gehören.
Die oben beschriebenen Verweisungen (8) und (13) haben nachgewiesen, daß das vorstehend beschriebene herkömmliche mehrdimensionale BH-Verfahren eine Menge minimaler Polynome F zur Erzeugung einer gegebenen mehrdimensionalen Matrix u ableitet. Dementsprechend wird durch Nachweisen, daß das mehrdimensionale Eu Verfahren der vorliegenden Erfindung die selbe Menge an Polynomen F ableitet, wie jenes des mehrdimensionalen BM-Verfahrens durch die folgenden Theoreme 1 bis 3, gezeigt werden, daß die Menge an Polynomen F, die durch das mehrdimensionale Eu Verfahren erhalten wird, das in Fig. 3 gezeigt ist, auch eine Menge minimaler Polynome zur Erzeugung einer gegebenen mehrdimensionalen Matrix u ist. Das mehrdimensionale Eu Verfahren der vorliegenden Erfindung wird nun spezifischer beschrieben, wobei das bekannte herkömmliche zweidimensionale BM-Verfahren und das mehrdimensionale BM-Verfahren veranschaulicht wird.

1. Ausführungsbeispiel

Zuerst wird der Sakata Algorithmus nach der folgenden Vorbereitung (Erläuterung der Terme) gezeigt. Da der Nachweis, daß dieser Algorithmus eine Menge an Polynomen F zur Synthese eines zweidimensionalen linearen Verschieberegisters ableitet, der eine minimale Anzahl an Speicherelementen zur Erzeugung einer gegebenen finiten zweidimensionalen Matrix u hat, in der oben beschriebenen Verweisung (8) erbracht wurde, wird eine Erläuterung des Nachweises weggelassenen.
Vorbereitung 1 (für Details, siehe Verweisung (8)
Σ: Eine Menge Paare n = (n1, n2) aller nicht negativen ganzen Zahlen n1 und n2.
n: Diese Bezeichnung wird Punkt genannt, der mit einem Punkt identifiziert wird, der Koordinaten (n1, n2) auf der X-Y Ebene hat.
< T: Diese Bezeichnung wird Gesamtordnung genannt und bestimmt das Größenverhältnis des Punktes n auf der Menge Σ. Der Punkt, der dem Punkt n = (n1, n2) in Bezug zu < T am nächsten liegt, wird in der folgenden Art und Weise definiert:
n + 1: = (n1 - 1, n2 + 1) (wenn n1 > 0)
: = (n2 + 1, 0) (wenn n1 = 0).
< p: Diese Bezeichnung wird als Halbordnung bezeichnet, die wie folgt definiert ist:
m ≤p n wenn und nur wenn m1 ≤ n1, m2 ≤ n2,
wobei m = (m1, m2) und n = (n1, n2)
m < p n zeigt an, daß m ≤ p n und m ≠ n.
Σtp: = {m Σ t ≤p m, m < T p}
u: u ist eine finite zweidimensionale Teilmatrix, die eine Größe q hat und wird als Abbildung auf das Feld K von Σoq definiert.
F: bivariate Polynome auf dem Feld K werden durch f = Σ fm . zm ausgedrückt.
m Γ f,
und zm = xm1 . ym2, Γ f = {m Σ fm ≠ 0}
s = LP (f) = max {m/m Γ f}.
Eine Menge Polynome wird durch folgendes ausgedrückt:
F = {f(0),..., f(1-1)}.
dfn(i): Wenn die Abbildung von n auf die Menge Σ auf dem Feld K durch Un dargestellt wird, ist dfn(i) = Σfm(i). Um+n-s für Polynome f(i), die LP(f(i)) = s(i) erfüllen.
m Γ f.
V(u): Wenn die Menge von un für p ≤T q durch folgendes ausgedrückt wird:
up = {Un n Σop}, und wenn dfn(i) = 0 (0 ≤ n < p) für up, f[Up] = 0. Zu dieser Zeit wird angenommen, daß:
V(Up) = {f(Polynome) f [up] = 0}.
Definitionspunkt: Wenn die Menge an Polynomen F eine Menge minimaler Polynome ist, die eine gegebene zweidimensionale Matrix erzeugen können, wird LP(f(i)) = s(i) als Definitionspunkt bezeichnet. Eine Menge minimaler Polynome erfüllt die folgenden Bedingungen:
i) F V (up)
ii) i und j erfüllen die Bedingungen, daß 1 ≤ i, j ≤ 1,
i ≠ j, und LP(f(i)) ≥p LP(f(j)) nicht vorliegen.
iii) Ein Polynom g erfüllt die Bedingungen, daß g V(u) und LP(g) ΔF nicht vorliegen, wobei
Δ: Dieses Symbol beschreibt ΔF, wenn die vorstehend beschriebenen Bedingungen erfüllt werden und wird in der folgenden Art und Weise erhalten:
Δ = UΔq-s
q, s Σop,
und Δq-s = {m Σ m ≤ p q-s} wenn f V(uq) die Bedingungen
erfüllen, daß dfq ≠ 0 und daß LP(f) = s vorliegt. Δq - s = in anderen Bedingungen.
h1: h1 des Typs < i, j> wird wie folgt definiert:
h1 = zr - s(i) f(i) - (di/dj) zr-n+m-t(j) g(j),
wobei r = (r1, r2).
r1 = max{s1(i), n1 - s1(j) + 1},
r2 = max{s2(i), n2 - s2(j+1) + 1}, t(j) = Lp(g(j)),
f(i) V(un), g(j) V(um), di = dfn(i), und dj = dgm(j).
G: Diese Bezeichnung wird als eine Menge von Hilfspolynomen von F bezeichnet und ist eine Menge aus Polynomen
G {g(0), ..., g(1 - 2)}.
Lemma 1: j des Typs, der durch bestimmt wird, ist j, das die Bedingung von LP(f(j)) = s(j)) erfüllt, und
p - s(i) ≤p (s1(j) - 1, s2(j + 1) - 1).
Lemma 2: k des Typs, der durch bestimmt wird, ist k, der die Bedingung von LP(f(k)) < p t.

Sakata Algorithmus

1) n = (0, 0), F = {1}, und G = .
2) Berechne dfn(i) für alle Polynome von F.
3) Wenn f(i) erfüllt, daß dfn(i) ≠ 0 vorliegt, werden ein neues Δ und ein neuer Definitionspunkt t bestimmt.
4) Die folgende Prozedur wird für alle Definitionspunkte t durchgeführt:
t = (s1(i), s2(i)) f T Beschaffe Polynom h1 von Lemma 1.
t = (n1 - s1(i) + 1, n2 T s2(i + 1) + 1) T Beschaffe h1 des
Typs < k, i> von Lemma 2.
t = (n1 - s1(i) + 1, s2(j), 1 ≤ i ≤ - 1, T Beschaffe h1
des Typs < j, 1> .
t = (s1(i), n2 - s2(j) + 1), 2 ≤ j ≤ 1 T Beschaffe h1 des Typs < i, j-1> .
t = (n1 + 1, s2(j)) T h1 = xn1 - s1 (j) + 1 f(i)
t = (s1(i), n2 + 1) T h1 = yn2 - s2 (i) + 1 f(i).
Alle Polynome, die die Bedingung dfn(i) ≠ 0 von F erfüllen und alle neu erhaltenen h1 werden in F eingesetzt.
5) Wenn Δ geändert wurde, werden Polynome von der Menge an Hilfspolynomen G für das neue F von den Polynomen des alten G und den Polynomen, die von F entfernt wurden, ausgewählt.
6) Der Prozeß wird beendet, wenn n = n + 1; n = p. Der Prozeß geht in anderen Fällen zu 2).
Nun wird ein neuer Algorithmus gemäß der vorliegenden Erfindung beschrieben, der denselben Ausgang wie beim Sakata Algorithmus ableitet.

Algorithmus 1

1) n = (0, 0), F= {1}, G = , A = {x - 1} und B = {u}.
2) Wenn der Koeffizient vom höchsten Grad aller Polynome von B nicht gleich Null ist, werden ein neues Δ und ein neuer Definitionspunkt t bestimmt.
3) Die folgende Prozedur wird für alle Definitionspunkte t durchgeführt.
t = (s1(i), s2(i)) T Beschaffe Polymon h2, das den Typ Lemma 1 hat.
t = (n1 - s1(i) + 1, n2 - s2(i + 1) + 1) T Beschaffe h2 des
Typs < k, i> von Lemma 2.
t = (n1 - s1(i) + 1, s2(j), 1 ≤ i ≤ 1 - 1 T Beschaffe h2 des Typs < j, i> .
t = (s1(i), n2 - s2(j) + 1), 2 ≤ j ≤ 1 T Beschaffe h2 des Typs < i, j-1> .
t = (n1 + 1, s2(j)) T h2 = x-(n1 - s1(j) + 1) b(j).
t = (s1(i), n2 + 1) T h2 = yn2 - s2(i) + 1 b(i).
Alle Polynome, bei denen der Koeffizient der höchsten Ordnung nicht gleich Null ist, werden von B entfernt und alle neu erhaltenen h2 werden in B eingesetzt.
4) Das Polynom h1 des Typs, das in 3) bestimmt wurde, wird, vorgesehen. Polynome, die den Polynomen entsprechen, die von B entfernt wurden, werden von F entfernt und das neu erhaltene h1 wird in F eingesetzt.
5) Wenn Δ verändert wurde, werden Polynome der Menge an Hilfspolynomen G für das neue F von den Polynomen des alten G und der Polynome, die von F entfernt wurden, ausgewählt. Polynome der Menge an Hilfspolynomen A für das neue B werden von den Polynomen des alten G und den Polynomen, die von B entfernt wurden, ausgewählt.
6) Der Prozeß wird beendet, wenn n = n + 1; n = p. Der Prozeß geht unter anderen Bedingungen zu 2), wobei A und B Mengen von Polynomen sind, wie A = {a(C) , ..., a(1 - 2)} und B = {b(0), ...,b(1 - 1)}.
h2: h2 des Typs < i, j> wird wie folgt definiert:
h2 = zr - s(i) b(i) - (di/dj) zr - n + m - t(j) a(j).
Ein großer Unterschied zwischen dem Algorithmus 1 und dem Sakata Algorithmus liegt darin, daß in dem Sakata Algorithmus dfn(i) direkt berechnet wird und nachgeprüft wird ob alle von diesen gleich Null sind, während in dem Algorithmus 1 dfn(i) nicht direkt berechnet wird, sondern es wird geprüft, ob der Koeffizi ent vom höchsten Grad an Polynomen b(i), der zu B gehört, gleich Null ist. Zu diesem Zweck führt der Algorithmus 1 Mengen A und B an Polynomen ein, die in dem Sakata Algorithmus nicht vorkommen.
Die Tatsache, daß die Menge F, die durch den Algorithmus 1 erhalten wird, dieselbe Menge ist wie die Menge F, die durch den Sakata Algorithmus erhalten wird, kann in der folgenden Art und Weise nachgewiesen werden:

Theorem 1

Wenn ein Polynom, das durch ein Multiplizieren vom Polynom u erhalten wird, das den Koeffizienten Un (n Σ&sub0;p) hat, der durch den Ausdruck (1) durch das Polynom f definiert wird, in dem LP() = s durch b dargestellt wird, wird der Koeffizient bv - n + s vom zv - n + s-Grad des Polynoms b durch den folgenden Ausdruck (2) ausgedrückt:
wobei v eine willkürliche ganze Zahl ist. Beweis:
aus dem Ausdruck (1).
Daher wird der Koeffizient bv -n + s von zv - n + s vom Polynom b wie im Ausdruck (2) gezeigt ist, weil i = m + n - s von v - i + m = v - n + s ist.

(Beweis beendet)

Anhand dieses Theorems kann verstanden werden, daß der Koeffizient von zv - n + s von b(i) = f(i) u, das f(i) F entspricht, gleich dfn(i) des Sakata Algorithmus ist.
Wenn das Polynom f(i), das V(un) ist, durch fn(i) dargestellt wird, gilt das folgende Theorem:

Theorem 2

Wenn Polynome, die durch die Ausdrücke (3) und (4) aktualisiert werden, durch lq(k) und cq(k) dargestellt werden (q > T n > T m) und das Polynom wq(k) durch den Ausdruck (5) definiert werden kann, kann wq(k) durch den Ausdruck (6) aktualisiert werden:
lq(k) = zrs ln(i) - (di/dj) zrt lm(j) (3)
cq(k) = zrs cn(i) - (di/dj) zrt cm(i) (4)
wq(k) = lq(k) e - cq(k) d (d und e sind willkürliche Polynome) (5)
wq(k) = zrs wn(i) - (di/dj) zrt wm(j) (6),
wobei rs und rt willkürliche ganze Zahlen sind und die Anfangswerte von ln(i), lm(j), cn(i) und cm(j) willkürliche Polynome sind.

Beweis:

Da der Ausdruck (6) für willkürliche q und k steht, gelten die folgenden Ausdrücke:
wn(i) = ln(i) e - cn(i) d
wm(i) = lm(i) e - cm(i) d.
Demgemäß gilt der folgende Ausdruck:
wq(k) = lq(k) e - cq(k) d = (zrs ln(i) - (di/dj) zrt lm(j)).e = (zrs cn(i) - (di/dj) zrt cm(j)) d = zrs wn(i) - (di/dj) zrt wm(j).

(Beweis beendet)

In dem Sakata Algorithmus wird f(k) = fq(k) F, das V(uq) wird, durch h1 aktualisiert und g(j) wird gleich f(j) = fm(j), das V(um) wird. Daher kann h1 in der Gestalt des Ausdrucks (3) ausgedrückt werden.
Das folgende Theorem gilt auch:

Theorem 3

Wenn lq(k) = fq(k), e = u, d = zv x, c&submin;&sub1;(j) = 1 und c&sub0;(i) = 0 im Ausdruck (5), wg(k) = bq(k) bei deg wq(k) ≤ V.
Zu dieser Zeit ist bq(k) das Polynom (v - q + s(k))-ten Grades.

Beweis:

Da lq(k) = fg(k) und e = u, wird der Ausdruck (5) wq(k) = bq(k) - cq(k) d. Wenn deg c - 1(j) ≤ 0 und deg c&sub0;(i) ≤ 0, ist cq(k) ein Polynom vom positiven Grad vom Ausdruck (4) und d = zv x und deshalb ist deg cq(k) d > v. Daher, wenn deg wq(k) ≤ v, wq(k) = bq(k).
Anhand dieser Definition ist der höchste Grad von bq(k) = u fq(k) gleich v + s(k). Da zu jener Zeit fq(k) fq(k) V(uq) ist, ist dfi(k) = 0
(i = 0,...,q - 1). Von dem Theorem 1 ist dfi(k) der Koeffizient von zv - 1 + s(k). Daher wird der (v - i + s(k))- Grad (i = 0,..., q - 1) Koeffizient von bq(k) zu 0 und der höchste Grad von bq(k) wird v - q + s(k).

(Beweis beendet)

Demgemäß kann bq (k) = wq(k) durch den Ausdruck (6) aktualisiert werden. D.h. bq(k) kann durch h2 aktualisiert werden. In diesem Fall sind di und dj von dem Theorem 1 und dem Theorem 3 jeweils die Koeffizienten von zv - m + s(i) und zv - m + s(j) der Polynome bn(i) und bm(k), d.h., die Koeffizienten höchsten Grades.
Wie vorstehend beschrieben wurde, wurde nachgewiesen, daß F, das durch den Algorithmus 1 erhalten wird, dieselbe Polynommenge wie F, die durch den Sakata Algorithmus erhalten wird, ist. Da es in der Verweisung (8) nachgewiesen wurde, daß die Polynommenge F, die durch den Sakata Algorithmus erhalten wird, eine Menge minimaler Polynome zur Erzeugung einer gegebenen zweidimensionalen Matrix u ist, kann gesagt werden, daß die Menge an Polynomen F, die durch den Algorithmus 1 erhalten wird, auch eine Menge minimaler Polynome zur Erzeugung einer gegebenen zweidimensionalen Matrix u ist.
Demgemäß kann dieser Algorithmus z.B. durch die Vorrichtung, die in Fig. 1 gezeigt ist, realisiert werden. Zuerst wird bestimmt, ob der Koeffizient höchsten Grades der Polynome B, die im Speicher 13 zur Speicherung der Anfangswerte und der aktualisierten Werte, die unter Punkt 1) des Algorithmus 1 gesetzt wurden, gespeichert sind gleich 0 ist. Wenn das Ergebnis der Bestimmung bestätigend ist, wird Punkt 6) ausgeführt. Wenn das Ergebnis der Bestimmung negativ ist, führt der Steuerkreis 11 den Punkt 2) zur Berechnung eines neues Definitionspunktes und zur Bestimmung von dem Typ aus und der Prozeßkreislauf 12 führt die Berechnung von h2 und h1 aus, wie in den Punkten 3) und 4) jeweils gezeigt ist, in Abhängigkeit des Typs. Wenn der Definitionspunkt aktualisiert wurde, wählt der Steuerkreis 11 erneut Polynome von A und G im Speicher 13 aus und aktualisiert diese, wie in Punkt 5) gezeigt ist.
Der Steuerkreis 11 und der Prozeßkreislauf 12 müssen nicht getrennt sein, da die oben beschriebene Verarbeitung durch eine Softwaremethode ausgeführt werden kann, indem die CPU dazu gebracht wird, Programme auszuführen, die den jeweiligen Steuerprozeduren und dem oben beschriebenen Algorithmus entsprechen. Da die Berechnung, die für die oben beschriebene Steuerung und Verarbeitung notwendig ist, Multiplikation, Division, Addition und Subtraktion einfacher ganzer Zahlen aufweist, ist kein spezieller Kreislauf und keine spezielle Verarbeitung erforderlich. Die oben beschriebenen Operationen können vereinfacht werden, wenn die Bestimmung des Typs und des Ablaufs der Prozedur in der Steuerung vorher in einen ROM-Speicher (Nur-Lese- Speicher) programmiert oder eingegeben werden und bei Bedarf wieder geholt werden (durch Durchsehen einer Tabelle)
Da h1 und h2 gleichzeitig verarbeitet werden können, können unabhängige Verarbeitungskreise für h1 und h2 vorgesehen werden. Da des weiteren h1 und h2 in derselben Art und Weise verarbeitet werden, kann h1 und h2 durch einen einzigen Kreis verarbeitet werden. Wie später unter Bezugnahme auf die Auswirkungen der Erfindung beschrieben wird, ist eine der Eigenschaften dieses Algorithmus die Leichtigkeit der Durchführung paralleler Verarbeitung, und eine Mehrzahl an Verarbeitungskreisen kann vorgesehen werden. Wie vorstehend beschrieben wurde, kann der Kreislauf zur Ausführung des Algorithmus 1 leicht realisiert werden.

Zweites Ausführungsbeispiel

Als nächstes wird ein Algorithmus untersucht, der äquivalent zu dem Algorithmus ist, der für den modifizierten Dekodieralgorithmus geeignet ist, der durch Kamiya et al. vorgestellt wurde. Zuerst wird nach der folgenden Vorbereitung der Algorithmus gezeigt, der durch Kamiya et al. vorgestellt wurde. Aspekte, die nicht in der folgenden Vorbereitung beschrieben werden, sind dieselben wie im ersten Ausführungsbeispiel

Vorbereitung 2 (für Details siehe Verweisung (12))

< T: In dem vorliegenden Ausführungsbeispiel ist die Gesamtordnung wie folgt definiert:
Q(i) = a i1 + b i2 (a und b sind natürliche Zahlen, die teilerfremde Primzahlen sind, i = (i1, i2))
m ≤ T n,
Wenn Q(m) < Q(n) erfüllt ist, oder
nur wenn Q(m) = Q(n) und m2 ≤ n2, und
der Punkt, der dem Punkt m am nächsten ist, durch m + 1 dargestellt wird in Bezug auf diese Gesamtordnung < T.
Σtp(n): = {m Σ m2 ≤ n, t ≤p m, m < T p}
u: u ist eine finite zweidimensionale Teilmatrix, die eine Größe q hat und als Abbildung von Σoq (2 (a-1)) auf dem Feld K definiert ist.
F: Bivariate Polynome auf dem Feld K werden durch folgendes ausgedrückt
f =Σ fm zm
m Γf,
wobei zm = xm1 ym2, Γf = {m Σ(a-1) fm ≠ 0}
s = LP(f) = max{m m Γf}
Eine Menge an Polynomen wird wie folgt ausgedrückt
f = {f(0) ,..., f(a-1)}.
V (u): Wenn die Menge von Un für Q(p) < q durch {Un n Σ&sub0;p(2 (a - 1))} dargestellt wird, und wenn dfn(i) = 0 (n Σsp(a-1+s2)) für up dargestellt wird, ist f[up] = 0. Zu jener Zeit ist V(up) = {f (ein polynom) f[Up] = 0}.
Δ:Δ wird auf die folgende Art und Weise erhalten:
Δ= UΔq-s
q,s Σ&sub0;p(2 (a-1)),
wobei Δq-s = {m Σ(a-1) m1 ≤ q1 - s1, m2 = q2 - s2} ist, wenn zutrufft, daß f V(uq) folgendes erfüllt, dfq ≠ 0 und LP(f) = s und
Δq-s = in anderen Fällen.
h3: h3 des Typs (i, j) wird wie folgt definiert:
h3 = xr1-s1(i) f(i) - (di/dj) xr1-n1+m1-t1(i) g(j)
G: Diese Bezeichnung wird als Menge von Hilfspolynomen von
F bezeichnet und ist eine Menge an Polynomen:
G = {g(0), ..., g(a-1)}

Kamiya Algorithmus

1) n =(0, 0), F = {1, y, y², ..., ya-1}, G = .
2) Berechne dfn (i) aller Polynome von F.
3) Wenn f(i) erfüllt, daß dfn(i) # 0 ist, werden ein neues A und ein neuer Definitionspunkt t bestimmt.
4) Die folgende Prozedur wird für alle Definitionspunkte t ausgeführt:
t = (s1(i), s2(i)) T Beschaffe h3 vom Typ < i, n2 - 1> .
t = (n1 - s1(i) + 1, n2 - s2(i) T Beschaffe h3 vom Typ < n2 - i, i> .
t = (n1 + 1, n2 - s2)(i) T h3 = xn1-s1(n2-i)+1 f(n2-1).
Alle Polynome, die dfn(i) ≠ 0 erfüllen, werden von F entfernt und alle neu erhaltenen h3 werden in F eingesetzt.
5) Wenn A geändert wurde, werden Polynome der Menge an Hilfspolynomen G für das neue F von den Polynomen des alten G und der entfernten Polynome von F ausgewählt.
6) Der Prozeß wird beendet, wenn n = n + 1; n = p. Der Prozeß geht in anderen Fällen zu Punkt 2).
Nun wird ein Algorithmus gezeigt, der äquivalent zum Kamiya Algorithmus ist.

Algorithmus 2

1) n = (0, 0), F = {1, y,..., ya-1}, G = , A = { }, B = {u}.
2) Wenn die Koeffizienten vom höchsten Grad von allen Polynomen von B nicht gleich 0 sind, werden ein neues A und ein neuer Definitionspunkt t bestimmt.
3) Die folgende Prozedur wird bei allen Definitionspunkten t ausgeführt.
1 t = (s1(i), s2(i)) T Beschaffe h4 vom Typ < i, n2 - i> .
2 t + (n1 - s1(i) + 1, n2 - s2(i)) T Beschaffe h4 vom Typ < n2 - i, i> .
3 t = (n1 + 1, n2 - s2(i)) T h4 = xs1(n2-i)-n1-1 f(n2-i).
Alle Polynome, in denen der Koeffizient von höchsten Grad nicht gleich 0 ist, werden von B entfernt und alle neu erhaltenen h4 werden in B eingesetzt.
4) Polynome h3 vom Typ, der in Punkt 3) bestimmt wird, werden beschafft. Polynome, die den Polynomen entsprechen, die von B entfernt werden, werden von F entfernt und das neu erhaltene h3 wird in F eingesetzt.
5) Wenn sich Δ geändert hat, werden Polynome von der Menge an Hilfspolynomen G für das neue F von den Polynomen des alten G und den Polynomen, die von F entfernt wurden, ausgewählt. Die Polynome der Menge an Hilfspolynomen A für das neue B werden von den Polynomen des alten A und den Polynomen, die von B entfernt wurden, ausgewählt.
6) Der Prozeß wird beendet, wenn n = n+1; n = p. Der Prozeß geht in anderen Fällen zu Schritt 2) weiter.
h4: h4 vom Typ < i, j> wird wie folgt definiert:
h4 = xr1-s1(i) b(i) - (di/dj) xr1-m1+m1-t1(i) a(j).
Wie in dem Fall von Algorithmus 1 und dem Sakata Algorithmus liegen Unterschiede zwischen dem Algorithmus 2 und dem Ka miya Algorithmus darin, ob dfn(i) direkt berechnet wird oder der Koeffizient vom höchsten Grad von Polynom b (i), der zu B gehört, dazu gemacht wird, dfn(i) zu sein. Wenn das Verhältnis, das zwischen dem Algorithmus 1 und dem Sakata Algorithmus gilt, zwischen dem Algorithmus 2 und dem Kamiya Algorithmus gilt, kann demgemäß auf die folgende Art und Weise nachgewiesen werden, daß das F, das durch den Algorithmus 2 erhalten wurde, dieselbe Menge an Polynomen wie das F, das durch den Kamiya Algorithmus erhalten wurde, ist.
Wenn angenommen wird, daß f(i) F vom Theorem 1 gleich f(i) vom Kamiya Algorithmus ist, kann gesagt werden, daß der Koeffizient von z des entsprechenden Polynoms b(i) = f(i) u gleich dfn(i) vom Kamiya Algorithmus ist. Daher gilt das Theoren 1 auch in diesem Ausführungsbeispiel.
Theorem 2 gilt allgemein.
Da fq(k) vom Theorem 3 gleich f(i) vom Kamiya Algorithmus ist, gilt auch Theoren 3.
Wie in dem Fall vom Sakata Algorithmus kann bq(k) demgemäß durch h4 aktualisiert werden, da gesagt werden kann, daß wq(k) = bq(k) ist. Auch in diesem Fall sind di und dj vom Theorem 1 jeweils die Koeffizienten vom höchsten Grad der Polynome bn(i) und bm(k).
Wie oben beschrieben wurde, wurde nachgewiesen, daß das F, das durch den Algorithmus 2 erhalten wurde, dieselbe Menge an Polynomen ist wie das F, das durch den Kamiya Algorithmus erhalten wurde.
Demgemäß kann der Algorithmus 2 auch die Vorrichtung, die in Fig. 1 gezeigt ist, realisiert werden. Jedoch sind die Steuerung und die Verarbeitung unterschiedlich zu denjenigen des Algorithmus 1. (Bei der Verarbeitung werden h3 und h4 berechnet. In der Steuerung ist die Bestimmung des Typs vereinfacht. Im Speicher 13 werden die Polynome, die in Punkt 1) gespeichert sind als Anfangswerte für die A, B, F und G gespeichert.) Da der Algorithmus 2 auch für eine Parallelverarbeitung geeignet ist, kann eine Mehrzahl von Verarbeitungskreisläufen verwendet werden. Wie oben beschrieben wurde kann verstanden werden, daß der Kreislauf zur Ausführung des Algorithmus 2 leicht realisiert werden kann.

Drittes Ausführungsbeispiel

Sakata et al. (siehe Verweisung (13)) zeigt auch einen Algorithmus zur Ableitung einer Menge von Polynomen F zur Synthese eines mehrdimensionalen Verschieberegisters, das eine minimale Anzahl an Speicherelementen zur Erzeugung einer mehrdimensionalen Matrix hat. Dieser Algorithmus wird als mehrdimensionales BM Verfahren bezeichnet. In diesem Ausführungsbeispiel wird ein neuer Algorithmus, der dem mehrdimensionalen EM Verfahren entspricht, untersucht.
Da der detaillierte Algorithmus kompliziert ist, werden Charakteristika des Algorithmus, der das BM Verfahren genannt wird( in einem Diagramm gezeigt. Der durch Sakata vorgeschlagene Algorithmus (das mehrdimensionale BM Verfahren), der eine Ausdehnung des eindimensionalen BM Verfahrens ist, das das eindimensionale BM Verfahren umfaßt, hat die Struktur, die in Fig. 2 gezeigt ist. Ein diesem Algorithmus entsprechender Algorithmus ist in Fig. 3 gezeigt. Wie in den beiden oben beschriebenen Ausführungsbeispielen liegen die Unterschiede zwischen den Verfahren, die in den Figuren 2 und 3 gezeigt sind, darin, ob dfn(i) direkt berechnet wird, oder der Koeffizient vom höchsten Grad des Polynoms b(i), der zu B gehört, dazu gemacht wird, dfn(i) zu sein. Wenn die Theoreme 1 bis 3 auch in der mehrdimensionalen Matrix gelten, kann demgemäß nachgewiesen werden, daß das F, das durch das mehrdimensionale BM Verfahren, das in Fig. 2 gezeigt ist, erhalten wird, dieselbe Menge an Polynomen ist, wie das F, das durch den Algorithmus, der in Fig. 3 gezeigt ist, erhalten wird.
In den vorstehend beschriebenen Ausführungsbeispielen werden Punkte auf dem zweidimensionalen Raum definiert, wobei n = (n1, n2) ist, und jeder Koeffizient der Matrix und das Polynom eine Abbildung bei jenem Punkt ist. Wenn dieses Konzept auf den N-dimensionalen Raum ausgedehnt wird, werden Punkte als n = (n1, n2, ..., nN) definiert und jeder Koeffizient der Matrix und das Polynom sind eine Abbildung bei jedem Punkt. Ein solches Verhältnis ist unabhängig von der Dimension identisch. Daher ist es offensichtlich, daß die Theoreme 1 bis 3 auch für den N-dimensionalen Raum gelten.
Dementsprechend kann gesagt werden, daß das F, das von dem Algorithmus, der in Fig. 3 gezeigt ist, erzeugt wird, dasselbe ist, wie das F, das von dem Algorithmus, der in Fig. 2 gezeigt ist, erzeugt wurde. Daher kann der Algorithmus, der in Fig. 3 gezeigt ist, leicht durch die Vorrichtung, die in Fig. 1 gezeigt ist, realisiert werden.
Jedoch wird in dem Fall einer Dimension der Algorithmus, der in Fig. 3 gezeigt ist, zu dem oben beschriebenen Algorithmus, der als Eu Verfahren bezeichnet wurde, der beim Dekodieren von RS Codes und BCH Codes verwendet wird. Wie bei den Effekten der Erfindung beschrieben wird, dehnt der in Fig. 3 gezeigte Algorithmus das Eu Verfahren auf mehrere Dimensionen aus, ohne die Charakteristika des eindimensionalen Eu Verfahrens zu verlieren. Demgemäß wird der Algorithmus, der eine Konfiguration der Fig. 3 hat, die die Algorithmen 1 und 2 enthält, als mehrdimensionales Eu Verfahren bezeichnet, das dem mehrdimensionalen BM Verfahren entspricht.
Wie oben beschrieben wurde, wurden verschiedene Arten an modifizierten Algorithmen vorgeschlagen, da das eindimensionale BM Verfahren und das eindimensionale Eu Verfahren häufig für RS Codes und ECH Codes verwendet werden. Ein weitergeführtes Fraktionsverfahren (siehe L.R. Welch und R.A. Scholtz: "Continued Fractions and Berlekamp's Algorithm", LEBE Trans. Inf. Theory, IT-25, Seiten 19 - 27, Jan. 1979) ist ein wohlbekannter abgewandelter Algorithmus des eindimensionalen Eu Verfahrens. Bei diesem Verfahren wird die Berechnung des Ausdrucks (6) nicht am Ende ausgeführt und die Berechnung, die sich nicht auf das Endergebnis bezieht, wird weggelassen. Da dieses Verfahren jedoch dasselbe ist wie das eindimensionale Eu Verfahren, bei dem B durch die Berechnung des Ausdrucks (6) aktualisiert wird und dfn(i) nicht direkt berechnet wird, ist es offensichtlich, daß dieses Verfahren auch für verschiedene Arten an modifizierten Algorithmen wirksam ist, einschließlich dem kontinuierlichen Fraktionsverfahren.
Wie aus den Fällen der Algorithmen 1 und 2 verstanden werden kann, hängt dieses Verfahren nicht von dem Verfahren zur Klassifizierung der Typen ab. Demgemäß ist dieses Verfahren auch vollständig für ein Verfahren wirksam, bei dem dfn(i) nicht direkt für die mehrdimensionale Matrix berechnet wird, wie in dem BM Verfahren, und B wird durch die Berechnung des Ausdrucks (6) aktualisiert und dfn(i) wird als Koeffizient vom höchsten Grad der Polynome von B berechnet.
Obwohl Punkte und jeweilige Parameter (rs, rt und dergleichen) als ganze Zahlen angenommen werden und fn(i) und bn(i) als Polynome angenommen werden, ist es offensichtlich, daß dieses Verfahren sogar wirksam ist, wenn Punkte und jeweilige Parameter auf willkürliche komplexe Zahlen ausgedehnt werden und Polynome auf rationale Funktionen und dergleichen ausgedehnt werden.
Wenn die Grade der Polynome u und f invertiert werden (Dualpolynome), wird auch der Grad des Polynoms b = f u invertiert und di kann der Koeffizient vom niedrigsten Grad des Polynoms b sein.
Beim Theorem 3 wird angenommen, daß d = zv x ist. Jedoch sogar wenn d = zv+1 oder d = 0, wq(k) = bq(k) und es ist offensichtlich, daß das Ergebnis des Algorithmus, der die Konstruktion in Fig. 3 hat, nicht verändert wird.
Obwohl ih dem oben beschriebenen Ausführungsbeispiel die Berechnung, die in dem folgenden Ausdruck (7) gezeigt ist, zur Aktualisierung von B verwendet wird, kann dasselbe Ergebnis durch Verwendung der Berechnung, die in dem Ausdruck (8) gezeigt ist, erhalten werden, mit Ausnahme der Unterschiede in den konstanten Termen.
bn+1(k) = zrs bn(i) - (di/dj) zrt an(i) (7)
bn+1(k) = dj zrs bn(i) - di zrt an(j) (8)
wobei an(j) = bm(j).
Wie oben beschrieben wurde, können Unterschiede zwischen dem Eu Verfahren und dem BM Verfahren wie folgt beschrieben werden.
Das BM Verfahren: dfn(i) wird direkt berechnet und fn+1(k) wird unter Verwendung des erhaltenen Wertes erhalten.
Das Eu Verfahren: dfn(i) wird nicht direkt berechnet und bn+1(k) wird erhalten, wie in Ausdruck (7) gezeigt ist, unter Verwendung der jeweiligen Koeffizienten vom höchsten Grad di und dj der Polynome bn(i) und bn(j). fn+1(k) wird unter Verwendung der selben di und dj berechnet.
Von solchen Unterschieden werden die folgenden Unterschiede beim Vorsehen von Geräten und einer hohen Geschwindigkeit für das BM Verfahren und das Eu Verfahren erzeugt.
Das BM Verfahren: In dem BM Verfahren ist es schwierig, sowohl fn(i) als auch fn+1(k) parallel zu berechnen. Der Grund dafür ist der folgende: dfn(i) = di ist zur Berechnung von fn+1(k) notwendig und dfn(i) wird unter Verwendung aller Koeffizienten von berechnet. Demgemäß kann die Berechnung von fn+1(k) nur begonnen werden, nachdem die Berechnung von fn(i) beendet wurde, da dfn(i) nur erhalten werden kann, nachdem die Berechnung von fn(i) beendet wurde. Wie in Fig. 4 (a) gezeigt ist, werden demgemäß in dem BM Verfahren die Polynome fn(i) und fn+1(k) an den Punkten n und n+1 sequentiell berechnet. Zusätzlich kann die Berechnung von fn(k), fn+1(k) und dfn(i) in dem BM Verfahren nicht parallel ausgeführt werden, sogar wenn die Berechnung mit einem Taktpuls durchgeführt wird. Daher ist eine Berechnungszeit erforderlich, die ungefähr gleich 2p Taktpulse ist, wie in Fig. 4 (b) gezeigt ist. Dies ist das gemeinsame Merkmal zu dem eindimensionalen EH Verfahren und dem mehrdimensionalen EH Verfahren, wie in Fig. 2 gezeigt ist.
Das Eu Verfahren: Bei dem Eu Verfahren können fn(i) und fn+1(k) parallel berechnet werden. Der Grund dafür ist wie folgt: In dem Eu Verfahren ist di der Koeffizient vom höchsten Grad von bn(i) B und die Polynome, die zu B gehören, können durch die Gleichung (7) berechnet werden, indem sie nur die Polynome verwenden, die zu B gehören. Wenn angenommen wird, daß die Gleichung (7) sequentiell vom höchsten Grad zum niedrigsten Grad berechnet wird, unter Verwendung von bn(i) und an(i), wird die Ausgabe bn+1(k) sequentiell von dem Koeffizienten des höchsten Grades zu dem Koeffizienten der niedrigeren Grade erhalten. Daher kann die Berechnung des Polynoms bn+2(k) beim Punkt n+2 begonnen werden, wenn der Koeffizient vom höchsten Grad erhalten wurde (an+1(j) hat schone Polynome erzielt). Dies zeigt an, daß Polynome bei den Punkten n+1 und n+2 parallel berechnet werden können. Es ist offensichtlich, daß dies auch für Punkte n und n+1 gilt. Demgemäß kann die Berechnung zur Aktualisierung von B an den jeweiligen Punkten parallel ausgeführt werden. Die Berechnung von fn+2(k) und fn+1(k) kann begonnen werden, wenn die Koeffizienten vom höchsten Grad von bn+1(i) und bn(i) bekannt waren. Daher kann, wie in Fig. 5 (a) gezeigt ist, die Berechnung von fn+1(k) an den jeweiligen Punkten auch parallel ausgeführt werden. Als ein Ergebnis kann eine Hochgeschwindigkeitsoperation im Verhältnis zur Anzahl der Kreise in dem Eu Verfahren leicht durchgeführt werden, wenn eine Mehrzahl von Prozeßkreisläufen zur Durchführung der Berechnung von der Gleichung (7) vorgesehen sind. Diese Eigenschaft hat es gemeinsam zu den wohlbekannten eindimensionalen Eu Verfahren und dem mehrdimensionalen Eu Verfahren, das in Fig. 3 gezeigt ist, und liegt in dem oben beschriebenen BM Verfahren nicht vor. Wenn die Berechnung von bn(i), bn+1(k), fn(i) und fn+1(k) mit einem Taktpuls durchgeführt wird, wie in Fig. 5 (b) gezeigt ist, reicht eine Berechnungszeit aus, die gleich ungefähr p Taktpulsen ist, und deshalb kann eine Berechnung durchgeführt werden, die eine höhere Geschwindigkeit als das EH Verfahren hat. (In den Figuren 5(a) und 5(b) wird di bei Punkt n durch dn dargestellt.)
Im allgemeinen zeigt ein Hochgeschwindigkeitsalgorithmus einen Algorithmus an, der eine kleinere Berechnungsmenge hat. Jedoch zur Realisierung einer Hochgeschwindigkeitsoperation kann eine Annäherung zur Reduzierung der Menge der Berechnung des Algorithmus und eine Annäherung zur Erhöhung der Paralleloperationen des Algorithmus berücksichtigt werden. Der Grund dafür ist, daß die Verarbeitungszeit durch gleichzeitiges Ausführen von einer Mehrzahl an Verarbeitungsschritten durch paralleles Verarbeiten reduziert werden kann. Ein kürzlicher Fortschritt in der VLSI-Technik (very large scale integrated circuit (integrierter Schaltkreis mit sehr großem Umfang)) kann leicht einen Chip schaffen, der eine Paralellverarbeitung in großem Umfang durchführen kann. Demgemäß ist in vielen Fällen ein Algorithmus, der einen hohen Grad an Parallelverarbeitungen hat, zur Hochgeschwindigkeitsverarbeitung geeignet.
Wie vorstehend beschrieben wurde, kann das Eu Verfahren der vorliegenden Erfindung einen höheren Grad an Parallelverarbeitungen durchführen als das BM-Verfahren, und deshalb ist es für ein Hochgeschwindigkeitsverarbeiten geeignet. Während das BM- Verfahren zwei Berechnungsarten erfordert, d. h. die Berechnung von einem Polynom fn(i) und die Berechnung einer Skalarmenge dfn(i), ist in dem Eu Verfahren nur eine Berechnung vom selben Typ für fn(i) und bn(i) erforderlich, wie in der Gleichung (7) gezeigt ist. Daher kann in dem Eu Verfahren der Verarbeitungskreis leichter in der Gestalt einer Einheit vorgesehen werden und deshalb kann gesagt werden, daß das Eu Verfahren für Parallelverarbeitung geeigneter ist.
Als ein Ergebnis kann gemäß der vorliegenden Erfindung eine Hochgeschwindigkeitsverarbeitungsvorrichtung leicht konfiguriert werden, die Parallelverarbeitungen durchführt.

Viertes Ausführungsbeispiel

Als nächstes ist eine Beschreibung eines Ausführungsbeispiels vorgesehen, in dem ein N-dimensionales BH Verfahren verwendet wird. In dem N-dimensionalen EH Verfahren wird eine Addition/Subtraktion an zwei Punkten unabhängig für Variablen jeder Dimension durchgeführt. Zu diesem Zweck kann in dem N- dimensionalen EH Verfahren ein effizienteres Verarbeiten durch Verwendung von N-dimensionalen Speichern durchgeführt werden, von denen jeder mit Variablen der entsprechenden Dimension umgeht.
Sogar wenn die Berechnung bezüglich der (N - 1)-dimensionalen Variablen gleichzeitig durchgeführt wird, wird das Verarbeiten hinsichtlich der verbleibenden Variablen sequentiell durchgeführt. Daher können die Verarbeitungen der Schritte S22 und S24, die in Fig. 2 gezeigt sind, parallel ausgeführt werden. Um eine Berechnung hinsichtlich der (N - 1)-dimensionalen Variablen gleichzeitig durchzuführen, kann ein unabhängiger Speicher für jeden Grad der Variablen verwendet werden und es kann gleichzeitig auf jeweilige Speicher zugegriffen werden.
Demgemäß würden im vorliegenden Ausführungsbeispiel ein Verfahren und eine Vorrichtung zur Verwendung des Verfahrens vorgeschlagen, wobei unabhängige Speicher für jeweilige Polynome und jeweilige Grade an Variablen durch Aufteilen von Adressen eines Speichers oder durch Verwendung einer Mehrzahl von Speichern realisiert wird, wodurch ein Verarbeiten des mehrdimensionalen BM Verfahrens effizient durchgeführt wird.
Fig. 6 veranschaulicht einen Algorithmus der vorliegenden Erfindung, entsprechend dem Algorithmus, der in Fig. 2 gezeigt ist. Die Fig. 7(a) bis 7(c) veranschaulichen jeweils die Operationen des Algorithmus, entsprechend den folgenden vierten bis sechsten Ausführungsbeispielen In Fig. 6 werden die Prozesse der Schritte S64 und S65 parallel ausgeführt.
Zuerst wird das eindimensionale BH Verfahren untersucht. In Fig. 8 stellt das Symbol u einen Speicher zur Speicherung einer gegebenen eindimensionalen Matrix u dar (ui wird für die Adresse i gesetzt), das Symbol f stellt einen Speicher zur Speicherung eines minimalen Polynoms f dar (das den Anfangswert 1 hat) zur Erzeugung einer Matrix u, und das Symbol g stellt einen Speicher zur Speicherung eines Hilfspolynoms g dar (das den Anfangswert 0 hat) für das Polynom f. Die Adressen dieser Speicher werden von außerhalb gesteuert. Da das eindimensionale BM Verfahren untersucht wird, wird nur ein Polynom in jedem der Speicher f und g gespeichert. Der Koeffizient vom (s - 1)-Grad (s ist der höchste Grad des Polynoms) wird in die Adresse i des Speichers gesetzt. Das Symbol dfn stellt ein Register für die Berechnung von dfn(i) dar, das Symbol dfm stellt ein Register für das Halten des Werts dfn dar, das Symbol IN stellt einen Kreislauf zur Ausgabe der Umkehrung des Eingabewertes dar und das Symbol dd stellt ein Register zum Halten des Werts von (dfn (i) / dfm(j)) dar, (das den Anfangswert u0 hat). Das Symbol SW stellt einen Schalter zur Auswahl einer Ausgabe vom Speicher f dar, nur wenn sich der Definitionspunkt geändert hat. Der Schalter SW wird von außerhalb gesteuert. Die Symbole X und + stellen jeweils einen Multiplikator und Addierer dar.
Bei Punkt n wird der Definitionspunkt vom Polynom f durch s(i) dargestellt und der Definitionspunkt vom Polynom g wird durch s(j) dargestellt. Die Zahlen werden sequentiell von der Adresse 0 in den Speichern f und g addiert, die jeweils auf die Adressen s(i) und s(j) geschaltet werden. Zu jener Zeit vergleicht ein äußerer Kreislauf die Werte von rs + s(i) und rt + s(j), beginnt einen Speicher zu betätigen, der einen größeren Wert hat und betreibt den anderen Speicher nach einer Zeitdauer, die der Anzahl der Taktpulse entspricht, die gleich dem Unterschied ist. Wie oben beschrieben wurde, werden jeweilige Koeffizienten vom Polynom f bei Punkt n, die im Schritt S64 berechnet und durch h aktualisiert wurden, sequentiell in den Speicher f von der Adresse 0 bis zur Adresse s(k) eingegeben (s(k) ist der aktualisierte Definitionspunkt des Polynoms), da das Register dd den Wert (dfn(i)/dfm(j)) hält.
Zu jener Zeit wird der Speicher u gesteuert, so daß die Zahlen von der Adresse n + 1 bis zur Adresse n + 1 - s(k) in Abhängigkeit der jeweiligen Koeffizienten vom Polynom f sequentiell subtrahiert werden und die jeweiligen Elemente der eindimensionalen Matrix u, die darin gespeichert sind, werden sequentiell ausgegeben. Somit wird dfn + 1(k) beim Punkt n + 1 in 2) parallel mit f beim Punkt n im Schritt S64 berechnet. Zu jener Zeit wird das vorherige dfn(i) in das Register dfm eingegeben. Durch Multiplizieren des Kehrwertes des Werts, der durch IN durch dfn + 1(k) vorgesehen ist, kann der Wert (dfn + 1)(i)/dfn(i)) in dem Register dd für die nachfolgende Berechnung gehalten werden. Wenn sich jedoch der Definitionspunkt geändert hat, wird der Schalter SW geöffnet, die Ausgabe des Speichers f wird sequentiell in den Speicher g von der Adresse 0 bis zur Adresse s(i) eingegeben und das Polynom g wird aktualisiert.
Demgemäß sind in Fig. 8 Taktpulse gleich s(k) für eine Aktualisieroperation (ein Zyklus) des Polynoms f erforderlich. Durch p-maliges Wiederholen dieser Operation kann ein minimales Polynom f zur Erzeugung von u erhalten werden.
Das Symbol s(k) ist die minimale Anzahl an Taktpulsen, wenn dfn + 1(k) und die jeweiligen Koeffizienten des Polynoms f sequentiell verarbeitet werden. Daher sind in der vorliegenden Erfindung unnötige Verarbeitungstaktpulse nicht vorhanden, im Gegensatz zur Vorrichüung aus der Verweisung (11) und deshalb ist die Verarbeitungsgeschwindigkeit erhöht. Da die hohe Geschwindigkeit für die Bestimmung und den Vergleich des Definitionspunktes nicht erforderlich ist, werden diese Operationen durch eine gewöhnliche CPU realisiert. Dementsprechend kann ein äußerer Kreislauf durch eine CPU und einen Zählerkreislauf zur Durchführung der Adressensteuerung leicht realisiert werden.

Fünftes Ausführungsbeispiel

Der äußere Kreislauf zur Durchführung der Adressensteuerung der Speicher, der in dem vierten Ausführungsbeispiel gezeigt ist, läßt nur nutzlose Verarbeitungstaktpulse in dem eindimensionalen BH Verfahren weg. In einem EH Verfahren für mindestens zwei Dimensionen hat ein solcher externer Kreislauf jedoch eine wichtige Rolle zur Realisierung der oben beschriebenen mehrdimensionalen Speicher zur Durchführung der Adressensteuerung und zur Ausführung eines effizienten mehrdimensionalen BM Verfahrens.
Um die Erläuterung zu vereinfachen wird zuerst ein zweidimensionales BM Verfahren untersucht. In Fig. 9 stellt das Symbol U einen Speicher zur Speicherung einer gegebenen mehrdimensionalen Matrix u dar, das Symbol f stellt einen Speicher zur Spei cherung einer Mehrzahl an Polynomen f(i) (i = 0, ..., 1 - 1) zur Erzeugung einer Matrix u dar und das Symbol G stellt einen Speicher zur Speicherung einer Mehrzahl an Hilfspolynomen g(j) (j = 0, ..., 1 - 2) für F dar. Das Symbol dfn(i) stellt ein Register zur Berechnung von dfn(i) dar und das Symbol dfm(j) stellt ein Register zum Halten des oben beschriebenen Werts dfn(i) dar. Es sind eine Mehrzahl solcher Register erforderlich, da eine Mehrzahl an Polynomen vorliegt. Andere Komponenten sind dieselben wie diejenigen, die im ersten Ausführungsbeispiel gezeigt sind.
Wenn angenommen wird, daß i die Anzahl an Polynomen f(i) darstellt, stellt j den Grad von yj dar und k stellt den Grad von xs (i) - k dar (s(i) ist der Definitionspunkt des Polynoms f(i)), die Speicher F und G können eine Adressenverteilung durchführen, wie in Fig. 10 gezeigt ist, und die Adresse kann durch (i, j, k) ausgedrückt werden. Das Symbol sj, das in Fig. 10 dargestellt ist, stellt den höchsten Grad von x für yj dar. Wenn zu jener Zeit angenommen wird, daß der Definitionspunkt eines Polynoms f(i) in der Menge an Polynomen F = s(i) = (s1(i), s2(i)) und a = (a1, a2) (a Σ&sub0;s(i)) eine Variable ist, wird das Polynom f)i) an der Position der Adresse (i, s1(i) - a1, a2) gespeichert.
Wenn angenommen wird, daß der Definitionspunkt eines Polynoms g(j) der Menge an Polynomen G gleich (s(j) = s1(j), s2(j)) ist, wird das Polynom g(j) in einer Adresse (j, s1(j) - a1, a2) für a Σ&sub0;s(j) gespeichert. In diesem Fall müssen die jeweiligen a's, die für die Speicher F und G verwendet werden, nicht an die Gesamtordnung angepaßt werden und a1 und a2 können unabhängig gesteuert werden.
Zum Beispiel kann es zuerst so eingestellt sein, daß a1 = a2 = 0 ist und nach dem Bearbeiten von al von 0 auf s0, kann a2 durch 1 übertragen werden und danach kann a1 wiederum von 0 auf s1 bearbeitet werden. Demgemäß können a1 und a2 leicht durch einen einfachen Aufwärtszähler gesteuert werden. Was den Speicher U anbetrifft kann die Adressenverteilung, die durch (j, k) dargestellt ist, durchgeführt werden, wenn die Abbildung von un vom Punkt n = (n1, n2) der Adresse (n1, n2) zugeordnet wird, und deshalb kann die Adressensteuerung leicht durchgeführt werden, wie in dem Fall der Speicher F und G.
Dementsprechend kann die Vorrichtung, die in Fig. 9 gezeigt ist, in der folgenden Art und Weise betrieben werden: zuerst vergleicht der äußere Kreis das Größenverhältnis zwischen rs + s(i) und rt + s(j) im Bezug zur Gesamtordnung, die von dem Definitionspunkt berechnet wird, betreibt einen Speicher, der einen größeren Wert hat und gibt Polynome aus, die in dem Speicher abgespeichert sind. Nach der Zeitdauer, die der Anzahl der Taktpulse entspricht, die gleich der Differenz ist, betreibt der äußere Kreis den anderen Speicher und gibt Polynome aus, die in jenem Speicher gespeichert sind.
Dä der Wert von (dfn(i)/dfm(j)) im Register dd gehalten wird, kann es verstanden werden, daß das Polynom f(k), das den Definitionspunkt s(k) = (s1(k), s2(k)) hat, der durch h im Schritt S64 berechnet und aktualisiert wurde, sequentiell in die Adresse (k, s1(k) - a1, a2) (a Σ&sub0;s(k)) des Speichers F eingegeben wird. Zu jener Zeit gibt der Speicher U jedes Element einer eindimensionalen Matrix u, die in der Adresse (n1' - a1, n2' - a2) (a Σ&sub0;s(k)) gespeichert ist, in Abhängigkeit von der Variablen "a" des aktualisierten Polynoms f(k) innerhalb der Adresse, wenn der Punkt, der dem Punkt n am Nächsten ist, in der Gesamtordnung durch n + 1 = n' = (n1', n2') dargestellt ist, aus, wenn der Punkt, der dem Punkt n in der Gesamtordnung am nächsten ist, durch n+1=n'=(n1', n2') ausgedrückt wird.
Somit wird dfn + 1(k) beim Punkt n + 1 im Schritt S62 parallel zu dem Polynom f(k) bei Punkt n im Schritt S64 berechnet. Zu jener Zeit ist dfn + 1(k), das im Schritt S62 berechnet wurde, im Register dfn(i) gespeichert und das vorhergehende dfn(i) wird im Register dfm gespeichert. Die gespeicherten Werte werden in der nachfolgenden Berechnung bei Bedarf verwendet. Deshalb wird der Wert von (dfn(i)/dfm(j)), der für die nächste Berechnung notwendig ist, im Register dd gehalten und der Algorithmus, der in Fig. 6 gezeigt ist, wird kontinuierlich ausgeführt. Wenn sich der Definitionspunkt geändert hat, wird der Schalter SW geöffnet, die Ausgabe vom Speicher F wird zu jener Zeit sequentiell zur Adresse (i, s1(i) -a1, a2) (a Σ&sub0;s(i)) des Speichers G eingegeben, wodurch die Menge an Polynomen G aktualisiert wird.
Demgemäß sind in Fig. 9 s(k) Taktpulse zum Aktualisieren eines Polynoms f(i) (ein Zyklus) erforderlich. In dem mehrdimensionalen BM Verfahren wird das Polynom f(k), das im Schritt S14 berechnet wird, und k, i und j der Polynome f(i) und g(j) die zur Berechnung verwendet werden, in Abhängigkeit vom Typ des Definitionspunktes bestimmt. Wenn eine Mehrzahl an Polynomen gespeichert ist, während die Adressenzuteilung in der vorstehend beschriebenen Art und Weise durchgeführt wird, können k, i und j der Polynome sequentiell durch Zuweisung von Adressen ausgewählt werden. Dementsprechend ist die Anzahl der Taktpulse erforderlich, die der Summe der jeweiligen s(k) entspricht, um al le Polynome f(k), die beim Punkt n zugewiesen sind, zu aktualisieren. Durch Wiederholen der vorstehend beschriebenen Operation bis zum Punkt p kann die Menge minimaler Polynome F zur Erzeugung einer zweidimensionalen Matrix u erhalten werden.
Es ist offensichtlich, daß die Auswahl der Polynome durch einen äußeren Kreis zur Bestimmung des Definitionspunktes ausgeführt werden kann. Dementsprechend kann das Problem 1), das in der herkömmlichen Vorrichtung von der Verweisung (11) schwierig gewesen ist, durch Auswählen einer Mehrzahl an Polynome durch Adressenaufteilung unter Verwendung eines äußeren Kreises zur Steuerung der Adressen gelöst werden . Des weiteren wird das Problem der Kompliziertheit des Speicherzugriffs hinsichtlich der mehrdimensionalen Variablen, wie in Punkt 2) beschrieben wurde, erleichtert und kann gelöst werden, indem eine Adressenzuteilung für jeden Grad von y durchgeführt wird, wie in Fig. 10 gezeigt ist.
Da jedes Polynom durch die minimale Anzahl an Taktpulsen s(k) aktualisiert wird, ist es offensichtlich, daß das effiziente Verarbeiten wie im ersten Ausführungsbeispiel, bei dem keine nutzlosen Verarbeitungstaktpulse vorgesehen sind, durchgeführt wird.
Es ist auch offensichtlich, daß der Kreis, der in Fig. 9 gezeigt ist, auch für das N-dimensionale BM Verfahren wirksam ist, wenn die Anzahl der Teilung der Adressen erhöht wird.

Sechstes Ausführungsbeispiel

Da in dem fünften Ausführungsbeispiel eine Mehrzahl an Polynomen gespeichert wird, während eine Adressenaufteilung eines einzelnen Speichers durchgeführt wird, kann nur ein Polynom und nur ein Grad ausgewählt werden und ein paralleles Verarbeiten von Polynomen und Variablen, das in den Problemen 3) und 4) gezeigt ist, wird nicht durchgeführt. Dementsprechend wird in dem vorliegenden Ausführungsbeispiel eine Vorrichtung zur Realisierung paralleler Verarbeitung von Polynomen und Variablen, wie in den Problemen 3) und 4) gezeigt ist, berücksichtigt.
Fig. 11 veranschaulicht ein Ausführungsbeispiel der vorliegenden Erfindung, bei dem eine Parallelverarbeitung der Polynome realisiert wird. In Fig. 11 weist jeder der Speicher F und G eine Mehrzahl an Speichern zur parallelen Speicherung einer Mehrzahl an Polynomen auf. Die dicke Linie, die in Fig. 11 gezeigt ist, zeigt eine Multiplex-Signalleitung, die der Anzahl der Mehrzahl an Speichern entspricht. Die Symbole + und x zeigen eine Vielzahl an jeweiligen Addierern und Multiplikatoren an, die in Abhängigkeit der Multiplex-Signalleitung parallel vorgesehen sind. Die Register dfn(i), dfm(j), dd und der reziproke Erzeugungskreis IN sind ferner in Abhängigkeit der Multiplex-Signalleitung parallel vorgesehen. Da jedoch nur eine Art von u in dem Speicher U gespeichert ist und einer Mehrzahl an Polynomen f(i) gemeinsam ist, weist die Eingangsleitung zum Speicher U eine einzelne Leitung auf und die Ausgabe vom Speicher U wird ähnlich den Multiplikatoren, die gemeinsam parallel vorgesehen sind, eingegeben.
Wenn zu jener Zeit die Adressen der Speicher F und G für Polynome gesteuert werden, die die größten Definitionspunkte bei jedem Punkt n haben, können andere Polynome durch die Adressensteuerung gesteuert werden. Dementsprechend kann ein Aktuah sieren aller Polynome beim Punkt n durch die Anzahl von Taktpulsen gleich s(k) durchgeführt werden, was der größte Definitionspunkt bei jenem Punkt ist. Durch p-maliges Wiederholen der vorstehend beschriebenen Operation kann die Menge minimaler Polynome F zur Erzeugung von u erhalten werden.
Eine Vorrichtung zur Durchführung paralleler Verarbeitung von Variablen kann auch gemäß dem Ausführungsbeispiel, das in Fig. 11 gezeigt ist, realisiert werden. Wenn in diesem Fall aufgeteilte Adressen für die jeweiligen Grade von y des Polynoms des fünften Ausführungsbeispiels parallel in einer Mehrzahl an Speichern gespeichert werden, kann eine Berechnung hinsichtlich der Variablen y innerhalb eines Polynoms parallel durchgeführt werden. Daher kann ein Parallelverarbeiten nicht nur für Polynome, sondern auch für Variablen innerhalb eines Polynoms realisiert werden.
Es ist offensichtlich, daß der Kreis, der in Fig. 11 gezeigt ist, auch für das N-dimensionale BM Verfahren wirksam ist, wenn die Anzahl an Speicher erhöht wird.
Die Anzahl an Speicher der Vorrichtung des sechsten Ausführungsbeispiels ist nicht notwendigerweise gleich der Anzahl an Polynomen oder der Anzahl an Graden, sondern es kann eine Mehrzahl an Speicher, die vorgesehen werden kann, einer Adressenaufteilung in Kombination mit dem Fall des zweiten Ausführungsbeispiels unterzogen werden.
Der Kreis zur Durchführung der Prozesse der Schritte S62 und S64 kann leicht durch eine CPU und dergleichen konfiguriert werden und ist nicht auf die Kreiskonfiguration beschränkt, die in dem vorliegenden Ausführungsbeispiel gezeigt ist.
Das Verfahren der Speicherung, das Verfahren für den Zugang zu den Speichern und dergleichen, die oben beschrieben wurden, sind natürlich nicht nur für das mehrdimensionale EH Verfahren wirksam, sondern auch für andere mehrdimensionale Matrizen und Verfahren zur Erzeugung mehrdimensionaler Polynome.
Da in dem vorliegenden Ausführungsbeispiel nur ein Zyklus mit einer minimalen Anzahl an Taktpulsen s(k) durchgeführt werden kann, die für das sequentielle Verarbeiten notwendig sind, sind keine nutzlosen Taktpulse vorgesehen und die Verarbeitungsgeschwindigkeit wird erhöht.
Durch Steuern einer Mehrzahl von Polynomen und Variablen davon kann unter Verwendung von Adressenaufteilung, die vorliegende Erfindung des weiteren auch leicht auf das mehrdimensionale BM Verfahren angewandt werden.
Durch das parallele Steuern einer Mehrzahl von Polynomen des mehrdimensionalen BM Verfahrens während dem Aufteilen der Polynome in eine Mehrzahl von Speicher, kann zusätzlich die Mehrzahl an Polynomen parallel verarbeitet werden und die Verarbeitungsgeschwindigkeit kann erhöht werden.
Darüber hinaus kann durch paralleles Speichern aufgeteilter Adressen für die jeweiligen Grade von Variablen innerhalb jedes Polynoms des mehrdimensionalen EH Verfahrens in eine Mehrzahl von Speichern die Verarbeitung für jeweiligen Variablen innerhalb eines Polynoms parallel durchgeführt werden und deshalb kann die Verarbeitungsgeschwindigkeit erhöht werden.

Claims

1. Eine Vorrichtung zur Ableitung von Polynommengen zur Erhaltung einer Menge minimaler Polynome zur Erzeugung einer gegebenen mehrdimensionalen Matrix, wobei die Vorrichtung folgendes aufweist:

eine erste Speichervorrichtung zur Speicherung einer ersten Menge zu erhaltender Polynome;

eine zweite Speichervorrichtung zum Speichern einer ersten Menge von Hilfspolynomen für die erste Polynommenge;

eine dritte Speichervorrichtung zur Speicherung einer zweiten Menge an Polynomen, die unterschiedlich zur ersten Polynommenge sind;

eine vierte Speichervorrichtung zur Speicherung einer zweiten Menge von Hilfspolynomen für die zweite Polynommenge;

eine erste Unterscheidungsvorrichtung zur Unterscheidung, ob der Koeffizient eines vorbestimmten Grades eines jeden Polynoms der in der dritten Speichervorrichtung gespeicherten zweiten Polynommenge gleich Null ist;

eine Bestimmungsvorrichtung zur erneuten Bestimmung eines Definitionspunktes, wenn ein Polynom, bei dem der Koeffizient eines vorbestimmten Grades nicht gleich Null ist, als ein Ergebnis der Unterscheidung durch die erste Unterscheidungsvorrichtung vorliegt;

eine erste Ableitungsvorrichtung zum Ableiten von Polynomen, die zur zweiten Polynommenge gehören, basierend auf dem Wert des Definitionspunktes, der durch die Bestimmungsvorrichtung bestimmt wurde, auf der in der dritten Speichervorrichtung gespeicherten zweiten Polynommenge und auf der in der vierten Speichervorrichtung gespeicherten zweiten Menge an Hilfspolynomen;

eine erste Aktualisiervorrichtung zur Löschung aller Polynome, in denen der Koeffizient eines vorbestimmten Grades nicht gleich Null ist aus der dritten Speichervorrichtung, und zur Speicherung der Polynome, die durch die erste Ableitungsvorrichtung in der dritten Speichervorrichtung abgeleitet wurden;

eine zweite Ableitungsvorrichtung zum Ableiten von Polynomen, die zur ersten Polynommenge gehören, basierend auf dem Wert des Definitionspunktes, der durch die Bestimmungsvorrichtung bestimmt wurde, auf der in der ersten Speichervorrichtung gespeicherten ersten Polynommenge, auf der ersten Menge an in der zweiten Speichervorrichtung gespeicherten Hilfspolynome und dem Koeffizienten eines Polynoms der zweiten Polynommenge, der sich auf den festgestellten Definitionspunkt bezieht;

eine zweite Aktualisiervorrichtung zur Löschung aller Polynome, die den Polynomen entsprechen, die durch die erste Aktualisiervorrichtung aus der ersten Speichervorrichtung gelöscht wurden, und zur Speicherung der Polynome, die durch die zweite Ableitungsvorrichtung in der ersten Speichervorrichtung abgeleitet wurden;

eine zweite Unterscheidungsvorrichtung zum Unterscheiden des Vorliegens einer Änderung des Definitionspunktes;

eine dritte Aktualisiervorrichtung zur Aktualisierung der ersten Menge an Hilfspolynomen, die in der zweiten Speichervorrichtung gespeichert sind, basierend auf der ersten Menge an Hilfspolynomen, die in der zweiten Speichervorrichtung gespeichert sind, und der Polynome, die durch die zweite Aktualisiervorrichtung gelöscht wurden, wenn die zweite Unterscheidungsvorrichtung das Vorliegen einer Veränderung des Definitionspunktes unterschieden hat; und

eine vierte Aktualisiervorrichtung zur Aktualisierung der ersten Menge an Hilfspolynomen, die in der zweiten Speichervorrichtung gespeichert sind, basierend auf der zweiten Menge an Hilfspolynomen, die in der vierten Speichervorrichtung gespeichert sind, und der Polynome, die durch die erste Aktualisiervorrichtung gelöscht wurden, wenn die zweite Unterscheidungsvorrichtung das vorliegen einer veränderung des Definitionspunktes unterschieden hat.

2. Eine Vorrichtung zum Ableiten einer Polynommenge gemäß Anspruch 1, wobei der Aktualisiervorgang von der ersten Aktualisiervorrichtung und der Aktualisiervorgang von der zweiten Aktualisiervorrichtung parallel durchgeführt werden.

3. Eine Vorrichtung zur Ableitung von Polynommengen gemäß Anspruch 1 oder 2, wobei die erste Aktualisiervorrichtung und die zweite Aktualisiervorrichtung durch gemeinsame Schaltkreise verwirklicht sind.

4. Eine Vorrichtung zur Ableitung von Polynommengen gemäß Anspruch 1, 2 oder 3, wobei die zweite Aktualisiervorrichtung die folgende Berechnung durchführt:

bq(k) = zrs-bn(i) - (di/dj)&supmin;zrt-bm(j),

wobei bn(i) und bm(j) Polynome sind, die zur zweiten Polynommenge gehören und di und dj jeweils die Koeffizienten vorbestimmter Grade der entsprechenden Polynome bn(i) und bm(j) sind.

5. Eine Vorrichtung zur Ableitung von Polynommengen gemäß Anspruch 1, 2 oder 3, wobei die zweite Aktualisiervorrichtung die folgende Berechnung durchführt:

bq(k) = dj&supmin; Zrs-bn(i) - di&supmin;zrt-bm(j),

wobei bn(i) und bm(j) Polynome sind, die zur zweiten Polynommenge gehören und di und dj jeweils die Koeffizienten des höchsten Grades oder des niedrigsten Grades der entsprechenden Polynome b(i) und b(j) sind.

6. Ein Verfahren zur Erhaltung minimaler Polynome zur Erzeugung einer gegebenen mehrdimensionalen Matrix, wobei das verfahren die folgenden Schritte aufweist:

Setzen von Anfangswerten für einen ersten Speicher zur Speicherung einer ersten Polynommenge, die erhalten werden soll, einen zweiten Speicher zur Speicherung einer ersten Menge an Hilfspolynomen für die erste Polynommenge, einen dritten Speicher zur Speicherung einer zweiten Menge an Polynomen, die sich von der ersten Menge Polynome unterscheidet, und einen vierten Speicher zur Speicherung einer zweiten Menge an Hilfspolynomen für die zweite Menge an Polynomen;

Unterscheiden, ob der Koeffizient eines vorbestimmten Grades eines jeden Polynoms der zweiten Menge an Polynome, die im dritten Speicher gespeichert sind, gleich Null ist;

erneutes Bestimmen eines Definitionspunktes, wenn ein Polynom, in dem der Koeffizient eines vorbestimmten Grades nicht gleich Null ist, als ein Ergebnis der Unterscheidung vorliegt;

Ableiten von Polynomen, die zur zweiten Menge an Polynomen gehören, basierend auf dem Wert des festgestellten Definitionspunktes, der zweiten Menge an Polynomen, die in dem dritten Speicher gespeichert sind, und der zweiten Menge an Hilfspolynomen, die im vierten Speicher gespeichert sind;

Löschen aller Polynome, in denen der Koeffizient eines vorbestimmten Grades nicht gleich Null ist, und Aktualisieren des dritten Speichers durch Speicherung der Polynome, die durch die erste Ableitungsvorrichtung abgeleitet wurden;

Ableiten von Polynomen, die zur ersten Menge an Polynomen gehören, basierend auf dem Wert des festgestellten Definitionspunktes, der ersten Menge an Polynomen, die in dem ersten Speicher gespeichert sind, der ersten Menge an Hilfspolynomen, die in dem zweiten Speicher gespeichert sind, und dem Koeffizient eines Polynoms der zweiten Menge an Polynome, der sich auf den festgesetzten Definitionspunkt bezieht;

Löschen aller Polynome, die den Polynomen entsprechen, die durch den Aktualisiervorgang des dritten Speichers gelöscht wurden, und Aktualisieren des ersten Speichers durch Speicherung der abgeleiteten Polynome;

Unterscheiden des Vorliegens einer Veränderung des Definitionspunktes;

Aktualisieren der ersten Menge an Hilfspolynomen, die in dem zweiten Speicher gespeichert sind, basierend auf der ersten Menge an Hilfspolynomen, die in dem zweiten Speicher gespeichert sind, und den Polynomen, die durch den Aktualisiervorgang des ersten Speichers gelöscht wurden, wenn unterschieden wurde, daß der Definitionspunkt durch den Unterscheidungsvorgang verändert wurde; und

Aktualisieren der ersten Menge an Hilfspolynomen, die in dem zweiten Speicher gespeichert sind, basierend auf der zweiten Menge an Hilfspolynomen, die in dem vierten Speicher gespeichert sind, und den Polynomen, die durch den Aktualisiervorgang des dritten Speichers gelöscht wurden, wenn unterschieden wurde, daß sich der Definitionspunkt verändert hat.

7. Ein Verfahren zur Ableitung von Polynommengen gemäß Anspruch 6, wobei der Aktualisiervorgang der ersten Menge an Polynome und der Aktualisiervorgang der zweiten Menge an Polynome parallel durchgeführt werden.

8. Eine Vorrichtung zur Ableitung von Polynommengen zur Erhaltung einer Menge minimaler Polynome zur Erzeugung einer gegebenen mehrdimensionalen Matrix, wobei die Vorrichtung folgendes aufweist:

eine Matrixspeichervorrichtung zum Speichern einer gegebenen mehrdimensionalen Matrix u;

eine erste Polynomspeichervorrichtung zur Speicherung einer Menge an Polynome F, die erhalten werden sollen;

eine zweite Polynomspeichervorrichtung zur Speicherung einer Menge an Hilfspolynomen G für die Menge der Polynome F;

eine erste Berechnungsvorrichtung zur Erhaltung von Polynomen f(k), die zu der Menge der Polynome F gehören, basierend auf den Polynomen f(i), die in der ersten Polynomspeichervorrichtung gespeichert sind, von Polynomen g(j), die in der zweiten Polynomspeichervorrichtung gespeichert sind, und von Ableitungen der Polynome dfn(i);

eine zweite Berechnungsvorrichtung zur Erhaltung von Abweichungen der Polynome dfn+1(k), basierend auf den Koeffizienten der Polynome f(k), die durch die erste Berechnungsvorrichtung berechnet wurden und auf der mehrdimensionalen Matrix u, die in der Matrixspeichervorrichtung gespeichert wurden; und

eine Steuervorrichtung zur parallelen Steuerung von Zugriffsvorgängen für die erste Polynomspeichervorrichtung und die zweite Polynomspeichervorrichtung und zugegriffener Adressen, in Abhängigkeit von den Graden der Polynome f(k),

wobei die Berechnung durch die erste Berechnungsvorrichtung und die Berechnung durch die zweite Berechnungsvorrichtung parallel ausgeführt werden.

9. Eine Vorrichtung zur Ableitung von Polynommengen gemäß Anspruch 8, wobei die erste Polynomspeichervorrichtung oder die zweite Polynomspeichervorrichtung eine Vielzahl an Speichern umfaßt und wobei eine Vielzahl an Polynomen in unterschiedlichen Speichern gespeichert werden.

10. Eine Vorrichtung zur Ableitung von Polynommengen gemäß Anspruch 8, wobei die erste Polynomspeichervorrichtung oder die zweite Polynomspeichervorrichtung eine Vielzahl an Speichern umfaßt, und wobei jeweilige Variablen und jeweilige Grade einer Vielzahl von Polynomen in unterschiedlichen Speichern gespeichert werden

11. Eine Vorrichtung zur Ableitung von Polynommengen gemäß Anspruch 8 oder 9, wobei die Steuervorrichtung die erste Polynomspeichervorrichtung und die zweite Polynomspeichervorrichtung so steuert, daß eine Vielzahl an Polynomen in unterschiedlichen Adressen gespeichert werden.

. 12.Eine Vorrichtung zur Ableitung einer Polynommenge gemäß Anspruch 8 oder 10, wobei die Steuervorrichtung die erste Polynomspeichervorrichtung oder die zweite Polynomspeichervorrichtung so steuert, daß jeweilige Variablen und jeweilige Grade an einer Vielzahl von Polynomen in unterschiedlichen Adressen gespeichert werden.

13. Eine Vorrichtung zur Ableitung einer Polynommenge gemäß einem der Ansprüche 8 bis 12, wobei die erste Berechnungsvorrichtung die folgende Berechnung durchführt:

f(k) = zrs-f(i) - (dfn(i)/fdm(j))&supmin;zrt-g(j).

14. Eine Vorrichtung zur Ableitung einer Polynommenge gemäß einem der Ansprüche 8 bis 12, wobei die zweite Berechnungsvorrichtung die folgende Berechnung durchführt:

dfn + 1(k) = fm(k)-um + n + 1-s, basierend auf den Polynomen f(k) = Σfm(k)-zm, die durch die erste Berechnungsvorrichtung berechnet wurden und auf der mehrdimensionalen Matrix u, die in der Matrixspeichervorrichtung gespeichert ist.

15. Ein Verfahren zu Erhaltung einer Menge minimaler Polynome zur Erzeugung einer gegebenen mehrdimensionalen Matrix, wobei das Verfahren die folgenden Schritte aufweist:

Speichern einer gegebenen mehrdimensionalen Matrix in einem Matrixspeicher;

Erhalten von Polynomen f(k), die zu einer Menge von Polynomen F gehört, die erhalten werden sollen, basierend auf Polynomen f(i), die in einem ersten Polynomspeicher zur Speicherung der Menge von Polynomen F gespeichert sind, auf Polynomen g(j), die in einem zweiten Polynomspeicher zur Speicherung einer Menge von Polynomen G gespeichert sind, die unterschiedlich zu der Menge von Polynomen F sind, und auf Abweichungen der Polynome dfn(i);

Erhalten von Abweichungen von Polynomen dfn+1(k), basierend auf den Polynomen f(k), die durch die erste Berechnungsvorrichtung und die mehrdimensionale Matrix u, die in dem Matrixspeicher gespeichert sind, erhalten werden; und

Steuern von Zugangsvorgängen für den ersten Polynomspeicher, den zweiten Polynomspeicher und zugegriffenen Adressen, in Abhängigkeit von Graden von den Polynomen f(k), und paralleles Ausführen der ersten und zweiten Berechnungsvorgänge.

16. Ein Verfahren zum Dekodieren von empfangenen Daten aus einem Speichermedium oder einem Verbindungskanal, wobei das Verfahren das Ableiten einer Polynommenge umfaßt, das ein Verfahren oder eine Vorrichtung gemäß einem der vorhergehenden Ansprüche verwendet

17. Ein Gerät zum Dekodieren von Daten, die von dem Speichermedium oder dem Verbindungskanal empfangen wurden, wobei das Gerät eine Vorrichtung zur Ableitung einer Menge von Polynomen gemäß einem der Ansprüche 1 bis 15 umfaßt.