DE3855497T2

DE3855497T2 - Datenverarbeitungsgerät zur Berechnung eines multiplikativ invertierten Elements eines endigen Körpers

Info

Publication number: DE3855497T2
Application number: DE3855497T
Authority: DE
Inventors: Hendrik Dirk Lodewijk Hollmann
Original assignee: Philips Electronics NV
Current assignee: Koninklijke Philips NV
Priority date: 1988-10-18
Filing date: 1988-10-18
Publication date: 1997-03-13
Anticipated expiration: 2008-10-19
Also published as: JPH02148225A; KR100202206B1; US4989171A; EP0364627B1; DE3855497D1; JP2744091B2; KR900006851A; EP0364627A1

Description

HINTERGRUND DER ERFINDUNG

Die Erfindung betrifft das Berechnen der multiplikativen Inversion eines Galois-Feldelements in GF(qm), wenn dieses Element in Vektordarstellung vorliegt. Hierin ist q eine zur Potenz erhobene Primzahl, üblicherweise q=2¹=2. Für viele Anwendungen ist m gerade, und häufig ist m = 8. Solche Berechnungen stellen dann byte-weise Datenverarbeitung zur Kryptographie, für Fehlerschutz z.B. mit Hilfe von Reed-Solomon-Codes, schnelle Fouriertransformationen und anderes dar. Die Daten entsprechen dann Videodaten, Audiodaten, in denen ein mit "Compact Disc" oder "Digital Audio Tape" aufgezeichneter Audioabtastwert von 2 Bytes gebildet würde, oder Meßergebnissen. Als Referenz sei die US-Patentschrift 4.587.627 genannt. Im folgenden werden elementare Eigenschaften und Rechenoperationen in einem Galois-Feld als Standardwissen betrachtet. Allgemein kann ein Gabis-Feldelement mit Hilfe einer Übersetzungstabelle (PROM oder ROM) invertiert werden, die für sinnvolle Felder, wie GF(2&sup8;), eine sehr umfangreiche Hardware erfordert. Ein alternatives Verfahren, das beispielsweise einen programmierten Prozessor verwendet, würde erhebliches Pipelining benötigen und daher viel Rechenlaufzeit mit sich bringen. Die vorliegende Erfindung benutzt ein Konzept von Subfeldem und berechnet insbesondere das multiplikative Inverse eines vektoriell repräsentierten Elements eines endlichen Feldes, dem Hauptfeld, mit Hilfe von Inversion in einem Subfeld des Hauptfeldes. Ein endliches Feld GF(qm) enthält jetzt GF(qn) als Subfeld, wenn m =rn, wobei zur Beschreibung der vorliegenden Erfindung eine Beschränkung vorgenommen wird, nämlich r=2. Das Prinzip der Erfindung ist jedoch auch auf andere Werte von r anwendbar. Der Index des Hauptfeldes über dem Subfeld ist r. Weil jetzt eine Berechnung in einem Subfeld mit weniger Vektorkoeffizienten arbeitet, ist die erstgenannte Berechnung einfacher und/oder schneller.
WO 89/01660 (früheres Patentdokument, aber nach dem Anmeldedatum der vorliegenden Erfindung veröffentlicht) beschreibt ein Gerät zum Berechnen multiplikativer Inverser in Datencodier- und -decodiereinrichtungen. Hierbei werden zwei Elemente, X und Y, von GF(2m), mit m = 2n, dividiert. Die Operation Y/X wird ausgeführt, indem erst das multiplikative Inverse des Divisors X gefunden wird und dann das Inverse X&supmin;¹ mit dem Dividenden Y multipliziert wird.
Bei diesem Stand der Technik wird weiterhin beschrieben, daß eine herkömmliche Galois-Feld-Division erfordert, daß das multiplikative Inverse des Divisors in einer Nachschlagetabelle mit 2n Elementen gefunden wird.
Die Operationsfolge ist die folgende:
a. ein Konversionsfaktor D = X2n wird berechnet, wobei die Berechnung von D in einem Galois-Feld mit der Basis 2 relativ einfach erscheint;
b C, ein Element eines kleineren Galois-Feldes, GF(2n), das ein Subfeld von GF(2m) ist, wird berechnet: C = D X;
c. das multiplikative Inverse von C in GF(2n) wird aus einer Tabelle zurückgewonnen, die die 2n Elemente von GF(2N) enthält;
d. C&supmin;¹ D = X&supmin;¹ wird berechnet.
Die vorliegende Erfindung nutzt auch das Konzept von Subfeldern, aber benötigt nicht den komplizierten endlichen Feldmultiplizierer für Schritt d.

ZUSAMMENFASSUNG DER ERFINDUNG

Der Erfindung liegt unter anderem die Aufgabe zugrunde, ein Datenverarbeitungsgerät zum Berechnen eines multiplikativ invertierten Elements in einem endlichen Feld zu verschaffen, das bei beschränkten Hardware-Anforderungen schnell arbeitet, indem es Inversionen in einem Subfeld verwendet, insbesondere in einem Subfeld vom Index 2, mit Hilfe einer vernünftigen Kombination quadratischer Formen, die bei dieser Reduktion eine Rolle spielen, zu Standardformen. Entsprechend einem Aspekt der Erfindung wird diese Aufgabe durch ein Gerät zum Berechnen der Komponenten X&supmin;¹k mit k = 0, 1, ..., 2n-1 eines Elements X&supmin;¹ gelöst, das das Inverse eines Eingangselements X des Hauptfeldes GF(2m) mit m =2n ist, wobei X durch ein Signal repräsentiert wird, das eine Menge von Vektorkoeffizienten (X&sub0;, X&sub1;; X&sub2;; ...; 2n-1) aufweist, und wobei (α&sup0;, α¹, ..., α2n-1) eine Basis in GF(2m) ist, so daß
gemäß der Gleichung:
wobei das genannte Gerät umfaßt:
a. erste Mittel (22), die zusammen die 2n Bits eines Signais empfangen, das das genannte Element X repräsentiert, zum Erzeugen einer ersten Matrix aus 2n² Linearformen Lj,i(X), mit j = 0, ..., n-1 und i =0, ..., 2n-1, und einer zweiten Matrix aus 2n² Linearformen Wjk(X), mit j = 0, ..., n-1 und k = 0,.. 2n-1,
wobei für bestimmte Zahlen cij und dijk GF(2) gilt:
und
b. zweite Mittel (28), die Signale empfangen, die die Linearformen Lj,i(X) repräsentieren, zum paarweise Kombinieren und Addieren der Linearformen, wobei alle Additionen modub 2 ausgeführt werden, zum Berechnen quadratischer Formen Qj(X), die Elemente von GF (2n) sind, gemäß der Gleichung:
fü rj = 0, 1, ... , n-1
c. dritte Mittel (30), die Signale empfangen, die die quadratischen Formen Qj(X) repräsentieren, zum Berechnen von Rj(X) in dem Subfeld GF(2n) durch Invertieren von Qj(X);
d. vierte Mittel (32), die für die inversen Formen Rj(X) und die Formen Wjk(X) repräsentative Signale empfangen, zum Berechnen der k-ten Komponente des Elements X&supmin;¹ gemäß der Gleichung:

KURZE BESCHREIBUNG DER ZEICHNUNG

Die Erfindung ist in der Zeichnung dargestellt und wird im folgenden näher beschrieben, und zwar erst die mathematischen Aspekte, dann die sich ergebende Operationsfolge der Schritte und die Hardware-Schaltung und schließlich ein spezielles Beispiel. Es zeigen:
Figur 1 ein Basis-Blockschaltbild eines erfindungsgemaßen Geräts und Tabelle 1A - 1E eine Gatter-Auflistung einer Inversionseinrichtung für GF(2&sup8;).

MATHEMATISCHE FORMULIERUNG DER ERFINDUNG

Aus Gründen der Vereinfachung wird die Erfindung für das endliche Feld GF(2n) beschrieben, mit m =2n. Der Fall q = 3 würde statt zu binären Elementen zu dreiwertigen Elementen führen, die im Prinzip mit Hilfe bekannter Logikschaltungen realisiert werden können. Das Hauptfeld GF(2m) hat für m=8 beispielsweise ein erzeugendes Polynom g(X) = X&sup8;+X&sup4;+X³+X²+1. Seine Elemente werden bezüglich einer Standardbasis (1,d...d&sup7;) ausgedrückt, die durch die Lösungen von g(d) =0 gegeben wird. Ausgangspunkt der Erfindung ist die Berechnung des multiplikativen inversen Elements X&supmin;¹ eines Elements X, das in GF(2m) durch X X&supmin;¹ =1 bestimmt wird, durch Verwendung des Ausdrucks: X&supmin;¹=(x2n+1)-1 X2n. Hierin ist der Ausdruck in Klammern ein Element des Subfeldes, während X ein Element des Hauptfeldes ist.
Wir definieren eine Linearform L(X) über GF(2m) als Funktion L(X)=L(0) X0+L1 X1+...+Lm-1 Xm-1, von GF(2m) bis GF(2m), wobei jedes Li ein Element von GF(2) ist. Eine solche Linearform wie hierin definiert ist eine Modulo-2- Summe selektierter Koeffizienten der Vektordarstellung von X. Eine quadratische Form Q(X) über GF(2m), von GF(2m) bis GF(2), wird definiert als Funktion:
wobei ci, aij GF(2). " " bedeutet hierbei "ist ein Element von". Daher ist eine solche quadratische Form, wie hier definiert, eine modulo-2-Summe selektierter Koeffizienten und selektierter, UND-verknüpfter Koeffizientenpaare der Vektordarstellung von X. In nahezu ähnlicher Weise könnten Formen höherer Ordnung definiert werden.
Jetzt kann für L(X)=X2n und Q(X)=X2n+1, mit X GF(2m=2n), L(X) geschrieben werden als L(X)=(L0(X), ...Lm-1(X)), bezüglich einer Basis in GF(2m), die nicht die Standardbasis (1...dm-1) zu sein braucht, die entsprechend einer Standardisierungskonvention festgelegt worden ist. Hierin ist jeder Koeffizient Li(x) eine Linearform. Tatsächlich gilt für X, Y GF(2m), (X+Y)²=X²+2XY+Y²=²+Y², weil XY+XY=0 und auch (X+Y)2n=X2n+y2n. Somit ist der Übergang von. X nach L(X) eine Linearoperation und jedes Li(X) ist eine Linearform.
Nun ist für X GF(2m) Q(X) in GF(2n). Tatsächlich genügen die Elemente X von GF(2m) X2m = X. Außerdem sind die Elemente Y von GF(2n) GF(2m) genau gleich denen, die y2n=y erfüllen. Jetzt gilt (Q(X))2n = X22n+2n + X22n X22n = X X2n = Q(X). Für eine Basis b0, b1, ...bn-1 in GF(2n) kann Q(X) geschrieben werden als Q(X) = (Q0(X), Q1(X), ..., Qn-1(X)), wobei die Wahl der Basis die Werte der Koeffizienten beeinflußt.
Jetzt ist jeder Koeffizient Qi(X) eine quadratische Form. Faktisch ist für
B(X,Y)=Q(X+Y)+Q(X)+Q(Y) offenbar
B(X,Y)=(X2n+Y2n(X+Y)+X2n+1+Y2n+1=X2n Y+X Y2n=L(X) Y+X L(Y), so daß B(X,Y) tatsächlich eine bilineare Operation definiert. Dies beweist die Behauptung zu Qj(X).

FINDEN VON DARSTELLUNGEN DER LINEAR- UND QUADRATISCHEN FORMEN Lj(X), Qk(X)

Für eine gegebene Basis α0..αm-1 in GF(2m) und β0..βn-1 in GF(2n) gibt es einfache Möglichkeiten, eher erwähnte Ausdrücke für die Linearformen Li(X), i=0..m-1, und die quadratischen Formen Qj(X), j=0,..n-1, zu berechnen. Somit kann eine solche Berechnung mit Hilfe eines Computerprogramms automatisch ausgeführt werden.
Für alle i, j gilt αi αj2n αj GF(2n); αi2n αj GF(2n); αi2n αj GF(2m). Dagegen gilt für alle i,j:
und
für bestimmte Zahlen cij, bik, aijk GF(2). Daher ist
Als Ergebnis wird erhalten:
In Fortsetzung zum Vorstehenden können die so definierten quadratischen Formen erneut in besser hantierbarer Darstellung ausgedrückt werden. Man betrachte jetzt M(X,Y), definiert als ( X2n Y ), wobei X GF(2m) und Y GF(2n).
Hierin gilt X2n = Lj(x) αj; Lj(X) = cij Xj;
Y = Yk βk. Daher gilt
M(X,Y) = Lj(X) Yj αj βk.
Man schreibe aj βk = djkl α1
Dann finden wir Setze
Jetzt kann bewiesen werden, daß wlk (X) eine Linearform über GF(2m) ist. Folglich hat M(X, Y) Komponenten (0, ..m-1):
Eine Funktion L(X) von GF(2m) bis GF(2) kann jetzt im wesentlichen linear genannt werden, wenn entweder L(X) selbst oder 1+L(X) eine Linearform ist. Es zeigt sich, daß folgendes zutrifft. Um Q(X) eine quadratische Form über GF(2m) werden zu lassen, können im wesentlichen lineare Formen Li(X) gefunden werden, so daß
Q(X)=L1(X) L2(X)+L2(X) L3(X)+..L2k-1(X) L2k(X), oder L1(X)...L2k(X)+1, wobei die geforderte Zahl 2k solcher für Q(X) benötigter Linearformen nur durch die Anzahl Nullstellen von Q(X) in GF(2m) beherrscht wird. Es hat sich gezeigt, daß die Anzahl Nullstellen der quadratischen Formen Qi(X) gleich 1+(2n+1)(2n-1-1) ist und unabhängig von den tatsächlich verwendeten Basen (aj) in GF(22n) und (βj) in GF(2n)
Tatsächlich würde eine solche Nullstelle für x2n+1=y2n+1 erzeugt werden, was der Fall ist, wenn entweder X=Y=0 oder (X/Y)2n+1=1. Da α in GF(2m) ein primitives Element ist, hat die Gleichung Z2n+1=1 tatsächlich genau 2n+1 Lösungen Zj=αj(2n-1) für j=0, .. 2n. Daher nimmt Q(X)=X2n+1 jeden von null unterschiedlichen Wert genau 2n+1-mal an. Da Q(X) GF(2n), hat GF(22n) 22n Elemente und hat GF(2n) 2nElemente, Q(X) nimmt jeden von null unterschiedlichen Wert in GF(2n) genau 2n+1-mal an und den Wert null genau einmal. Wenn jetzt Y alle Elemente von GF(2n) durchläuft, wird jeder Koeffizient von Y bezüglich irgendeiner festen Basis aus Symmetriegründen genau in der Hälfte der Fälle null sein. So wird irgendein bestimmter Koeffizient aller Elemente ungleich null in GF(2n) genau 2n-1-1-mal null sein.
Die Anzahl 2k von für die Ausdrücke für die quadratischen Formen Qi(X) notwendigen im wesentlichen linearen Formen wird durch die Zahl der Nullstellen einer quadratischen Form Q(X) über GF(2n) bestimmt, nämlich 1+(2k+1)+(2k-1-1) Im wesentlichen lineare Formen geben somit die quadratische Form als:
Qi(X) = Li,1(X) Li,2(X)+..+Li,2n-1(X) Li,2n(X).

ZUSAMMENFASSUNG DER ERGEBNISSE ALS FOLGE VON SCHRITTEN

Entsprechend dem Vorstehenden wird das multiplikative Inverse folgendermaßen berechnet:
X-1=X2n+1 X2n
Hierin, L(X):=X2n GF(2m),
Q(X):=X2n+1 GF(2n).
Zunächst werden zwei Basen gewählt, nämlich:
GF(2m) : α0, α1...α2n-1
GF(2n) : β0, β1...βn-1.
Insbesondere die Wahl für die zweite Basis ist willkürlich. Ausgedrückt in der ersten Basis gilt L(X)=((L0(X),...L2n-1(X)), wobei die Koeffizienten Linearformen sind, die jedoch nicht explizit berechnet werden. Außerdem gilt Q(X) = ((Q0(X),...Qn-1(X)), wobei die Koeffizienten quadratische Formen sind. Man beachte, daß die Basis für das zweite Galois-Feld frei gewählt werden kann.
Nun ist die erste Aufgabe, R(X)=((R0(X),...R2n-1(X)) zu berechnen, das das Inverse von Q(X) in dem Subfeld GF(2n) ist. Dann wird das folgende Produkt berechnet:
Definiert werde die Linearform
Dies sind die Linearformen, die insbesondere berechnet werden müssen.
Schließlich wird die k-Komponente der gesuchten inversen Größe gegeben durch
Von Rj(X)(j) muß jetzt die Größe Qj(X)(j) erzeugt werden. Im vorigen wurde gefunden, daß
wobei die Größen Lj, ... Linearformen sind. Folglich müssen die folgenden Größen erzeugt werden:
Ijs(X), für s=0..2n-1, j=0...n-1
wjk(X), für k=0..2n-j, j=0..n-1.
Wie in den Beispielen gezeigt, können im weiteren gewisse Teile dieser Berechnungen kombiniert werden. Als nächstes werden die Größen Qj(X) gebildet, die zusammen die Größe Q(X) ergeben. Danach wird in dem Subfeld mit Hilfe seiner Koeffizienten Rj(X) das Inverse von Q(X), R(X) genannt, berechnet. Diese Berechnung wird generell in klassischer Weise ausgeführt. Alternativ könnte das Subfeldinverse noch in einer weiteren Inversion in ein sekundäres Subfeld aufgespalten werden. Schließlich werden die Koeffizienten des inversen Wertes in dem Hauptfeld durch den Ausdruck für &supmin;¹k gegeben.

BESCHREIBUNG EINER HARDWARE-AUSFÜHRUNG

Figur list ein Basis-Blockschaltbild eines erfindungsgemäßen Geräts. Auf einem ersten Niveau werden die verschiedenen Teilsysteme nur als Blöcke beschrieben. Diese können einerseits als festverdrahtete Legik für superschnelles Arbeiten an einem einzigen Galois-Feld realisiert werden, wie es für das Hifi-Audio-Compact-Disc-System definiert worden ist, z.B. zum Ausführen von Fehlerkorrektur auf der Grundlage von "cross-interleaved Reed-Solomen "-Codes und anderen Signalverarbeitungsmöglichkeiten. Andererseits könnten die verschiedenen Blöcke mit Hilfe von Programmsteuerung allgemeinerer, anwendbarer Prozessorblöcke, wie einem 8 = Bit-Mikroprozessor realisiert werden. Im letztgenannten Fall w::je Time-Sharing verschiedener Blöcke unter einer Vielzahl von Funktionen noch möglich und würde die Chipfläche abnehmen, und/oder es würde andere Vorteile bieten. Natürlich werden Verarbeitungsleistung und Verarbeitungsgeschwindigkeit gegeneinander aufgewogen. Letztere Realisierung würde noch eine Verbesserung hinsichtlich des für direkte Inversion in einem Hauptfeld notwendigen längeren Pipelining bedeuten. Außerdem gibt es keine explizite Beschränkung, nur in einem einzigen Galois-Hauptfeld zu arbeiten, und Austausch zwischen verschiedenen Feldern und/oder verschiedenen Basen für entsprechende Felder wäre sehr gut möglich. Der Kürze halber ist die Beschreibung solcher Standardbausteine weggelassen worden.
Der Eingang 20 führt in der Schaltung die 2n Bits der Eingangsgröße parallel. In Block 22 erfolgt die Berechnung der Linearformen Lij(X) und wlk(X), wobei jede Kategorie 2n² Linearformen erzeugt. Im Falle unscharfer Logik beträgt die Gattertiefe der Anordnung höchstens (1+k), wobei k=2log n oder die nächsthöhere ganze Zahl ist. Somit ist für die Compact Disc k=3. Im vorstehenden ist der Effekt einer Kombination von Berechnungen für die Größen L und w nicht betrachtet worden. Die Linearformen werden auf der Verbindungsleitung 24 zu Block 24 hin ausgegeben; die Linearformen Lij(X) am Ausgang 26 direkt zum Block 32. Die Bitbreite der Verbindungsleitungen 24, 26 wird nicht explizit dargestellt.
Im Block 28 werden die Linearformen paarweise kombiniert und addiert, 10 um die Größen Qi(X) zu erzeugen, mit i=0, .. n-1, wobei alle Additionen modub 2 ausgeführt werden. Dies erfordert insgesamt n² UND-Operationen und n(n-1) XOR- Operationen bis zu einer Legikgattertiefe von 1+k. Das Ergebnis wird als n Bit breite Größe zu Block 30 hin ausgegeben.
In Block 30 wird die inverse Größe R(X)=Q(X)&supmin;¹ in dem Subfeld GF(2n) berechnet.beispielsweise mit Hilfe eines programmierten Tabellenspeichers. Das Ergebnis wird als n Bit breite Größe zu Block 32 hin ausgegeben.
In Block 32 wird das Inverse in dem Subfeld empfangen und auch die Linearformen wlk(X) zum Berechnen des Ausdrucks:
&supmin;¹1=M(X,R(X)01=R0(X) W10(X)+...+Rn-1(X) W1,n-1(X),
wobei 1=0, ..2n-1. Diese Operation erfordert insgesamt 2n² UND-Operationen und 2n(n-1) XOR-Operationen, mit einer gesamten Legikgattertiefe von (k+1). Die Gesamtzahl von Operationen beträgt 8n³-n-3n XOR-Operationen, die für sinnvolle Werte von n (≥ 4) ungefähr 8n³ ist. Außerdem sind 3n² UND-Operationen notwendig, was angesichts der einfacheren Struktur der UND-Operationen ziemlich vernachlässigbar ist. Die gesamte Logiktiefe beträgt 3+3k.
Die Struktur der oben genannten Konversionen kann festgelegt sein, aber es besteht noch immer eine beträchtliche Freiheit hinsichtlich der genauen Realisierung. Selbst wenn die Basis in dem Hauptfeld festgelegt worden ist, gibt es noch die folgenden Wahlmöglichkeiten:
a. Wahl der Basis β0..n-1 in GF(2n). Diese Wahl beeinflußt die Linearformen wlk(X), die quadratischen Formen Qi(X) und damit auch die Linearformen Lij(X);
b. selbst nach Wahl der Basis (β0..βn-1) in GF(2n) die Darstellungen für Qi(X) als Produkte von im wesentlichen Linearformen, d.h. die genaue Formulierung der Linearformen Lij(X) ist wahlfrei.
Insbesondere die zweite Wahl kann vorteilhaft sein. In vielen Fällen können die Linearformen so gewählt werden, das jede nur höchstens n der Koeffizienten benötigt (statt 2n). In diesem Fall wird die Logiktiefe um 1 verringert, und die Anzahl von XORs zum Berechnen der Lij(X) wird halbiert. Außerdem können verschiedene Berechnungen sich verschiedene Zwischenergebnisse teilen, sowohl zur Berechnung der Größen Lij(X) als auch der Größen wlk(X) zur noch weiteren Verringerung der Anzahl XOR-Operationen. Faktisch braucht die Anzahl XOR-Operationen nur (1...11/2) n³ zu betragen. In beiden Fällen sind α und β wahlfrei, wobei empfohlen wird, eine normale Basis zu wählen. In dem Fall kann genau die gleiche Hardware verwendet werden, um jeden der Koeffizienten des Inversen zu berechnen. Die Gesamtstruktur der Hardware würde dann regelmäßiger werden. Auch wenn die Koeffizienten des Inversen sequentiell berechnet werden können, kann die gleiche Hardware für jeden der aufeinanderfolgenden Koeffizienten verwendet werden.

BEISPIEL ZUR AUSFÜHRUNG DES VERFAHRENS

Im folgenden wird als Beispiel eine Inversion in GF(2&sup4;) beschrieben: m=2n=4. Das endliche Feld GF(2&sup4;) wird von dem nicht reduzierbaren Polynom g(X) = X&sup4;+X+1 über GF(2) erzeugt. Sei a eine formale Nullstelle von g(X), also: α&sup4; = α+1. Als Basis in GF(2&sup4;) nehmen wir: (1α,α²,α³). Jetzt enthält GF(2&sup4;) GF(2²). Tatsächlich können die Elemente von GF(2²) geschrieben werden als {0, 1,α&sup5;,α¹&sup0;} Als Basis in GF(2²) wird die normale Basis (α&sup5;,α¹&sup0;) gewählt.
Der zu invertierende Vektor ist jetzt:
X=(X0,X1,X2,X3)=X0+X1α+X2α²+X3α³.
Man schreibe Q(X)=Q0(X)α&sup5;+Q1(X)α¹&sup0;. Dies führt unmittelbar zu den Ausdrücken für die nur zwei, jetzt benötigten quadratischen Formen
Q0(X)=X0+X1+X3+X0X1+X0X2+X1X2+X1X3
Q1(X)=X0+X2+X3+X0X1+X0X2+X0X3+X2X3.
Hierin wird der Ausdruck Q(X)=X2n+1 verwendet, der dann in seine Grundelemente aufgelöst wird.
Das Inverse von Element Y1α&sup5;+Y2α¹&sup0; kann in diesem einfachen Subfeld direkt als Y2α&sup5;1+Y1α¹&sup0; geschrieben werden, so daß R1(X)=Q0(X) und R0(X) = Q1(X). In einem größeren Subfeld würde die Inversion selbst mit Hilfe eines Tabellen- ROM in herkömmlicher Weise erfolgen. Berechnung der Formen wlk(X) führt jetzt zu:
X0&supmin;¹=R0 (X2)+R1 (X0+X1+X3)
Xn&supmin;¹=R0 (X0+X1)+R1 (X0+X3)
X2&supmin;¹=R0 (X0+X2+X3)+R1 (X0)
X3&supmin;¹=R0 (X1+X2)=R1 (X1+X2+X3).
Eine alternative Darstellung für Q0(X), Q1(X) ist die folgende:
Hierin stellen die Ausdrücke in Klammern im wesentlichen lineare Formen dar, wobei die Überstreichung den inversen Logikwert andeutet. Die Teilglieder werden mehrmals verwendet und können mittels:
a1=X0+X1 a4=a1+X3=X0+X1+X3
a2=X0+X3 a5=a2+X2=X0+X2+X3
a3=X1+X2 a6=a3+X3=X1+X2+X3
miteinander geteilt werden.
Die erforderliche Anzahl XOR-Additionen ist viel kleiner als die eher festgelegte obere Grenze: 4n²(2n-1)=48.
In einem größeren Hauptfeld und damit größeren zugehörigen Subfeld umfassen die Berechnungen mehr Größen und haben somit die notwendigen Gatter mehr Eingänge, und auch die Logiktiefe ist größer. Alles in allem ist das Prinzip der Berechnung das gleiche und wird entsprechend den allgemeinen bereits beschriebenen Ansatzregeln ausgeführt.

BESCHREIBUNG EINER BEVORZUGTEN AUSFÜHRUNGSFORM

Tabelle 1 A-1 E gibt eine tabellenförmige Darstellung einer bevorzugten Ausführungsform zur Inversion in dem Compact-Disc-Galois-Feld, GF(2&sup8;). Die Stan-30 dardanzahl Gatter würde in der Größenordnung 4n²(2n-1)=448 liegen. Die Gatterdarstellung ist dreispaltig. Die erste Spalte listet den Namen des Gatters auf, der auch als Name für das Ausgangssignal des Gatters verwendet wird. Die zweite Spalte gibt die Funktion des Gatters an. Die dritte Spalte listet die Eingangssignale des betreffenden Gatters auf. Die oberen beiden Zeilen der Tabelle 1A definieren die acht Komponenten (I7, ...I0) des Eingangsvektors und die acht Komponenten (J7 ...J0) des Ausgangsvektors, der das multiplikative Inverse des Eingangsvektors ist.
35 D-Gatter bewirken jetzt die Inversion in dem Subfeld, das an sich faktisch dem Nachschlagen in einer Tabelle entspricht. Diese Inversion verwendet als Eingangssignale verschiedene C..-Signale, die im weiteren näher besprochen werden sollen, und auch verschiedene in der Inversionsmatrix selbst erzeugten Zwischensignale. Die Gatter-Bibliothek hat die folgenden bei der vorliegenden Inversion verwendeten Elemente:
QNOR2 ist ein NOR-Gatter mit zwei Eingängen
QNAND2 ist ein NAND-Gatter mit zwei Eingängen
QIN1 ist ein Inverter mit einem Eingang
QIN2 ist ein Inverter mit einem Eingang mit größerer Ausgangsauffächerung
QAND3 ist ein UND-Gatter mit drei Eingängen
QNOR3 ist ein NOR-Gatter mit drei Eingängen
QAND4 ist ein UND-Gatter mit vier Eingängen
QNAND3 ist ein NAND-Gatter mit drei Eingängen
QXNOR ist ein XNOR-Gatter mit zwei Eingängen
QOR3 ist ein ODER-Gatter mit drei Eingängen
QIN3 ist ein Inverter mit einem Eingang mit noch größerer Ausgangsauffächerung
QFO6 ist eine erste spezielle Funktion, die für eine Folge von vier Eingangssignalen a1...a4 folgendermaßen ausgedrückt wird: (a1+a2+a3 a4)
QF08 ist eine zweite spezielle Funktion, die für eine Folge von fünf Eingangssignalen a1...a5 folgendermaßen ausgedrückt wird: (a1+a2 a3+a4 a5).
Weitere Elemente der Bibliothek werden der Kürze halber nicht spezifiziert.
In Block 22 von Figur 1 werden jetzt die verschiedenen Linearformen berechnet. Dies geschieht mit Hilfe der Menge von Gattern, die mit Gatter N47 beginnt bis zu B256 (oder bis zu Gatter N5). Diese Formen sind nur XOR-Gatter, XNOR-Gatter und Inverter. In Block 28 werden die quadratischen Formen berechnet. Dies geschieht mit Hilfe der Menge von Gattern, die mit Gatter NC01 beginnt bis zu Gatter C3. Danach sind die notwendigen Vektorkomponenten C0...C3 bereit für die Verarbeitung in Block 30. Nach Ausführung der Inversion in dem Subfeld zum Erzeugen der Vektorkomponenten D0...D3 erfolgt die Multiplikation in Block 32. Dies geschieht mit Hilfe der Gitter, die mit Gitter NJ01 beginnen.
Die gesamte Gitteranzahl ist jetzt:
Block 22: 76
Block 28: 32
Block 30: 35
Block 32: 64
insgesamt: 207

ÜBERSICHT

Zur Verdeutlichung soll die folgende kurze Übersicht des im Vorstehenden gefolgten Verfahrens gegeben werden. Das Endergebnis sollte X&supmin;¹k sein, d.h. die k- te Komponente des inversen Vektors =
Um Rj(X) (j=0..n-1) zu erhalten, mußte die quadratische Form Qj(X) (j=0...n-1) berechnet werden. Hierzu wurde geschrieben:
wobei beide L Linearformen sind. Faktisch waren die Linearformen
Ljs(X) s=0...2n-1, j=0...n-1
wjk(X) k=0...2n-1 j=0...n-1
zu berechnen.
Qj(X) folgt aus Gleichung (B), mit dem Ergebnis Q(X). Rj(X) (j=0...n-1) wird durch Invertieren von Q(X) erhalten. Schließlich folgt &supmin;¹ aus Gleichung (A).

Claims

1. Gerät zum Berechnen der Komponenten X&supmin;¹k mit k 0, 1, ..., 2n-1 eines Elements X&supmin;¹, das das Inverse eines Eingangselements X des Hauptfeldes GF(2m) mit m=2n ist, wobei X durch ein Signal repräsentiert wird, das eine Menge von Vektorkoeffizienten (X&sub0;, X&sub1;; X&sub2;; ...; X2n-1) aufweist, und wobei (α&sup0;, α¹, ..., α2n-1) eine Basis in GF (2m) ist, so daß

gemaß der Gleichung:

wobei das genannte Gerät umfaßt:

a. erste Mittel (22), die zusammen die 2n Bits eines Signais empfangen, das das genannte Element X repräsentiert, zum Erzeugen einer ersten Matrix aus 2n² Linearformen Lj,i(X) mitj = 0, ..., n-1 und i = 0, ..., 2n-1, und einer zweiten Matrix aus 2n² Linearformen Wjk(X) mitj = 0, ..., n-1 und k = 0, ..., 2n-1, wobei für bestimmte Zahlen cij und dijk E GF(2) gilt:

und

b. zweite Mittel (28), die Signale empfangen, die die Linearformen Lj,i(X) repräsentieren, zum paarweise Kombinieren und Addieren der Linearformen, wobei alle Additionen modub 2 ausgeführt werden, zum Berechnen quadratischer

Formen Qj(X), die Elemente von GF (2(X) sind, gemäß der Gleichung:

für j = 0, 1, ... , n-1

c. dritte Mittel (30), die Signale empfangen, die die quadratischen Formen Qj(X) repräsentieren, zum Berechnen von Rj(X) in dem Subfeld GF(2(X) durch Invertieren von (Qj(X);

d. vierte Mittel (32), die für die inversen Formen Rj(X) und die Formen Wjk(X) repräsentative Signale empfangen, zum Berechnen der k-ten Komponente des Elements X&supmin;¹ gemäß der Gleichung:

2. Gerät nach Anspruch 1, in dem der genannte Eingang 2n Bits breit ist, mit einem Matrixevaluierer, der einen weiteren Ausgang hat, der 2n Bits breit ist.