Reed-Solomon-Codes. Teil 2 - Arithmetik der Galoisfelder

    Hallo Freunde! Das letzte Mal haben wir darüber gesprochen, wie Reed-Solomon-Codes die erforderliche Zuverlässigkeit der Datenspeicherung gewährleisten. Heute beschäftigen wir uns etwas mehr mit der Arithmetik der Galoisfelder, die in den Berechnungen verwendet wird. Zunächst ein kurzer Ausflug in den letzten Teil




    . Wir haben herausgefunden: Um verlorene Daten wiederherstellen zu können, müssen Sie zunächst auf eine bestimmte Weise „redundante Daten“ generieren. Aus mathematischer Sicht reduziert sich dieses Problem (Codierung) darauf, eine Erzeugungsmatrix zu konstruieren und den Vorgang des Multiplizierens dieser Matrix mit dem Vektor der Quellendaten durchzuführen. Die Wiederherstellungsprozedur (Decodierungsprozedur) besteht wiederum darin, die Erzeugungsmatrix umzukehren und mit dem Vektor der gespeicherten Daten zu multiplizieren. Dies kann schematisch wie folgt dargestellt werden.

    Kodierungsverfahren



    : Dekodierungsverfahren:

    Bild

    Einschränkungen der Arithmetik rationaler Zahlen


    Wir haben bereits einige Schwierigkeiten festgestellt, die bei der Implementierung von Kodierungs- / Dekodierungsprozeduren auf bestimmten Hardwareplattformen auftreten müssen. So werden beispielsweise Zahlen im Computerspeicher normalerweise durch eine feste Anzahl von Bytes dargestellt. Infolgedessen kann man beim Multiplizieren der Elemente der Erzeugungsmatrix einen Überlauf von Bits erhalten. Oder wenn die erzeugende Matrix als ihre Elemente invertiert wird, können rationale Zahlen entstehen, deren Speicherung mit beliebiger Genauigkeit problematisch ist. Aus diesem Grund werden wir heute darüber sprechen, wie diese Verfahren implementiert werden können, um die oben genannten Probleme zu vermeiden. Die Galois-Feldtheorie, über die wir bereits in einem früheren Artikel gesprochen haben, wird uns dabei helfen.

    Ich werde gleich ein paar Kommentare abgeben. Erstens ist der Artikel in erster Linie für Ingenieure gedacht, daher habe ich versucht, strenge mathematische Definitionen zu vermeiden. Für diejenigen, die eine formalere Einführung in diesen Bereich wünschen, ist es sinnvoll, sich sofort an die einschlägige Literatur zu wenden. Ich für meinen Teil kann Ernest Borisovich Vinbergs Buch The Course of Algebra empfehlen. Zweitens reicht für die Implementierung redundanter Codierungsalgorithmen nur ein grundlegendes Verständnis der Theorie der endlichen Felder aus. Sie können einfach davon ausgehen, dass einige konsistente Tabellen für Multiplikation, Division, Addition, Subtraktion und alle Berechnungen unter Verwendung dieser Tabellen ausgeführt werden. Dies ist ein Hinweis für diejenigen, die nicht wirklich tief in diesen Abschnitt der Algebra eintauchen möchten.

    Felder und arithmetische Operationen in endlichen Mengen


    Bevor wir direkt zur Diskussion der Galois-Felder übergehen, wiederholen wir noch einmal, was wir erreichen wollen. Wir wollen in der Lage sein, Matrizen mit Vektoren zu multiplizieren, Matrizen zu invertieren. Und am wichtigsten ist, dass wir uns nur mit ganzen Zahlen befassen und uns keine Gedanken über einen Überlauf machen möchten, wenn wir Multiplikations- und Additionsoperationen ausführen.

    Um Verwirrung zu vermeiden, ist es auch sinnvoll, sich sofort mit der Terminologie zu befassen. Was ist ein Feld in Bezug auf die allgemeine Algebra? Wie Wikipedia sagt , "ist ein Feld eine Menge, für deren Elemente die Operationen Addition, Subtraktion, Multiplikation und Division (mit Ausnahme der Division durch Null) definiert sind und deren Eigenschaften den Eigenschaften gewöhnlicher numerischer Operationen nahe kommen". Was ist das Galoisfeld? Galois Field Ist ein beliebiges Feld, das aus einer endlichen Anzahl von Elementen besteht. $ Gf (p) $, $ Gf (p ^ n) $- die Standardbezeichnung von Galois-Feldern, wobei die Anzahl der Feldelemente in Klammern angegeben ist.

    In modernen Computern wird normalerweise eine feste Anzahl von Bits zum Speichern von Zahlen verwendet. Es ist leicht zu berechnen, dass alles existiert$ 2 ^ n $ verschiedene n-Bit-Zahlen von 0 bis $ (2 ^ n - 1) $. Mit anderen Worten, wir haben eine endliche Menge von Zahlen. An dieser Menge werden wir nun auf konsistente Weise versuchen, die Operationen der Multiplikation, Division, Addition und Subtraktion zu bestimmen. Darüber hinaus ist damit auch das Ergebnis einer Operation$ n $Bit Nummer! In diesem Fall wird gesagt, dass der Satz in Bezug auf die eingeführten Operationen geschlossen ist .

    Die Subtraktionsoperation in Systemen endlicher Mengen wird gewöhnlich durch das Konzept von Null und entgegengesetzten Elementen eingeführt. Nullelement$ 0 $ - Dies ist ein solches Element, für das die Gleichheit gilt: $ a + 0 = a $wo $ a $Ist ein beliebiges Element der Menge. Gegenstand$ b $ist das Gegenteil für$ a $wenn Gleichheit wahr ist $ a + b = 0 $. Normalerweise wird das entgegengesetzte Element als bezeichnet$ -a $. Wenn wir wollen von$ x $ subtrahieren $ y $wir finden das gegenteilige Element $ -y $ und stapeln es mit $ x $. Um also beliebige Elemente einer endlichen Menge subtrahieren zu können, muss jedes Element dieser Menge das Gegenteil haben.

    Ähnlich verhält es sich mit der Teilungsoperation. Das Konzept der Einheit und inversen Elemente wird eingeführt. Einzelelement$ 1 $ Ist ein Element, für das Gleichheit wahr ist $ a * 1 = a $wo $ a $Ist ein beliebiges Element der Menge. Gegenstand$ b $ (bezeichnet mit $ 1 / a $) heißt das Inverse von $ a $wenn $ a * b = 1 $. Wie bei der Subtraktion, wenn wir wollen$ x $ dividieren durch ungleich Null $ y $wir müssen das inverse Element finden $ 1 / y $ und multiplizieren Sie es mit $ x $. Um beliebige Elemente teilen zu können, muss jedes Element der Menge (mit Ausnahme der Null) das Gegenteil haben.

    Bau von Galoisfeldern GF (p)


    Wie können wir die angezeigten arithmetischen Operationen für eine endliche Menge von Zahlen bestimmen, so dass die Menge relativ zu ihnen geschlossen ist? Mit anderen Worten, wir wollen eine beliebige endliche Menge von Elementen in ein Galois-Feld verwandeln. Das erste, was mir einfällt, ist die Verwendung von modularer Arithmetik. Dann wenn unser Set enthält$ p $ Elemente, dann das Ergebnis des Produkts von Zahlen $ a * b $ wird eine Zahl sein $ (a * b) mod p $. Die Summe der Zahlen ist definiert als$ (a + b) mod p $.

    Stellen wir als Übung die Additions- und Multiplikationstabelle für eine Menge zusammen, bestehend aus$ p = 5 $ Elemente $ \ {0, 1, 2, 3, 4 \} $.


    In den unteren beiden Tabellen sind die entgegengesetzten und entgegengesetzten Werte für jedes Element unseres Sets aufgeführt. Mit diesen Tabellen können wir alle arithmetischen Operationen ausführen, die wir benötigen. Hurra!

    Gebäude Galois Felder $ Gf (p ^ n) $


    Wir scheinen auf dem richtigen Weg zum Erfolg zu sein. Das Einzige, was uns vielleicht noch nicht zusagt, ist die Größe unseres Fachgebiets - 5. Es ist klar, dass es zur Vereinfachung der Softwareimplementierung sinnvoll ist, mit Sets zu arbeiten, die Folgendes enthalten$ 2 ^ n $zahlen. Dann können wir mit Knabbereien, Bytes, Wörtern usw. arbeiten.

    Auf den ersten Blick sieht es so aus, als ob die Differenz 5 oder 256 Elemente in der Menge beträgt. Wir nehmen das Ergebnis der Multiplikation oder Addition mit dem entsprechenden Modul und sind fertig. Versuchen wir noch einmal, eine Multiplikationstabelle für eine Menge zu erstellen, aber diesmal mit$ 4 = 2 ^ 2 $ Element - $ \ {0, 1, 2, 3 \} $. Folgendes ist passiert:
    Multiplikationstabelle für {0,1,2,3}

    Wenn Sie sich die resultierende Tabelle genau ansehen, können Sie einen gravierenden Nachteil feststellen. Achten Sie auf die Zeile für Element 2. In dieser Zeile befindet sich kein einzelnes Element! Dies bedeutet, dass wir die anderen Elemente nicht durch 2 teilen können, da das Gegenteil dafür nicht existiert! Dies bedeutet, dass Additions- und Multiplikationstabellen auf andere Weise erstellt werden müssen. Modulare Arithmetik funktioniert leider nicht mehr.

    Also haben wir herausgefunden, dass wenn das Set enthält$ 4 = 2 ^ 2 $Objekt, dann können Sie mit modularer Arithmetik keine konsistenten Multiplikationsoperationen angeben. Tatsächlich ergeben sich ähnliche Probleme für jede Menge, die Anzahl der Elemente$ p $Das ist keine Primzahl. Aber woran können Sie noch denken?

    Zugabe zu GF (p ^ n)


    Nehmen wir der Einfachheit halber an, dass die Menge, für die wir arithmetische Operationen definieren möchten, enthält $ 2 ^ n $Elemente. Dies sind tatsächlich Zahlen$ \ {0, 1, 2, 3, ..., 2 ^ n - 1 \} $. Beliebige Nummer$ a $ aus dieser Menge kann als Zerlegung dargestellt werden:

    $ a = a_0 + a_12 ^ 1 + a_22 ^ 2 + ... + a_ {n-1} 2 ^ {n-1}, a_i \ in \ {0,1 \} $


    Im Wesentlichen ist dies die übliche binäre Darstellung einer Zahl. Wir können also auch eine beliebige Zahl aus unserer Menge als Längenvektor betrachten$ n $deren Elemente Nullen und Einsen sind:

    $ a = [a_0, a_1, a_2, ..., a_ {n-1}], a_i \ in \ {0,1 \} $


    Wir führen die Addition von zwei beliebigen Zahlen ein, indem wir die entsprechenden binären Zerlegungsvektoren addieren. Darüber hinaus erfolgt die Addition der Vektorkomponenten modulo 2 (im allgemeinen Fall, wenn die Anzahl der Elemente$ p ^ n $Modulo $ p $) Somit wird der resultierende Vektor auch eine binäre Darstellung einer bestimmten Zahl sein und infolgedessen zu unserer Menge gehören (die Menge wird in Bezug auf die Additionsoperation geschlossen).

    $ a = [a_0, a_1, a_2, ..., a_ {n-1}], a_i \ in \ {0,1 \} \\ b = [b_0, b_1, b_2, ..., b_ {n -1}], b_i \ in \ {0,1 \} \\ c = a + b = [(a_0 + b_0) mod2, ..., (a_ {n-1} + b_ {n-1}) mod2] $


    Es ist leicht zu erkennen, dass die von uns eingeführte Additionsoperation der bitweisen XOR-Operation entspricht. Das ist sehr gut, da moderne Prozessoren diesen Vorgang sehr schnell ausführen können. Das ist aber noch nicht alles. Offensichtlich$ a \ oplus a = 0 $ für eine beliebige Zahl $ a $. Dies bedeutet, dass das gegenteilige Element zu$ a $ ist er selbst $ a $. Also auf dem Feld$ Gf (2 ^ n) $ Addition ist das gleiche wie Subtraktion!

    Multiplikation in GF (p ^ n)


    Es bleibt die Multiplikationsoperation an unserem Set einzuführen. Dies geschieht wie folgt. Stellen wir uns für eine Weile vor, dass irgendeine Zahl$ a $ aus unserer Menge ist ein Polynom der folgenden Form:

    $ a (x) = a_0 + a_1x + a_2x ^ 2 + ... + a_ {n-1} x ^ {n-1}, a_i \ in {0,1} $


    Hier werden die Koeffizienten des Polynoms aus der binären Erweiterung der Zahl entnommen $ a $. Bei diesem Ansatz kann zum Beispiel die Nummer$ 100 = 01100100b $ wird einem Polynom zugeordnet $ x ^ 6 + x ^ 5 + x ^ 2 $.

    Die Operation der Multiplikation zweier Zahlen können wir durch Multiplikation von Polynomen bestimmen, die gegebenen Zahlen entsprechen:

    $ a × b = (a_0 + a_1x + ... + a_ {n-1} x ^ {n-1}) × (b_0 + b_1x + ... + b_ {n-1} x ^ {n-1}) $


    Darüber hinaus werden beim Multiplizieren alle Operationen mit Polynomkoeffizienten modulo 2 ausgeführt.

    Nun kann jedoch offensichtlich ein anderes Problem auftreten. Beim Multiplizieren von zwei Polynomen des Grades$ n-1 $können wir ein Polynom höheren Grades erhalten, das keiner der Zahlen in unserer Menge entspricht. Dies wird wie folgt gelöst. Es wird ein irreduzibles Gradpolynom gewählt$ n $. Grob gesagt ist dies ein solches Polynom, das nicht als Produkt anderer Polynome dargestellt werden kann, mehr im Artikel . Anschließend teilen wir das Ergebnis des Produkts mithilfe des Algorithmus zum Teilen von Polynomen durch eine Spalte , an die sich viele noch aus dem Lehrplan erinnern können, in ein irreduzibles Polynom. Wiederum werden beim Teilen durch eine Spalte Operationen mit Polynomkoeffizienten ebenfalls modulo 2 ausgeführt. Als Ergebnis erhalten wir ein Polynom mit einem Grad, der nicht höher als ist$ n-1 $, die wir als Ergebnis des Produkts von zwei Zahlen nehmen. Hier ist ein Beispiel für die Multiplikation zweier Zahlen über ein Feld$ Gf (2 ^ 8) $ mit irreduziblen Polynom $ x ^ 8 + x ^ 4 + x ^ 3 + x + 1 $. Dieses Polynom wird im AES / Rijndael-Verschlüsselungsalgorithmus verwendet.

    Wir haben das Feld untersucht$ Gf (2 ^ n) $. Benutzerdefinierte Felder$ Gf (p ^ n) $ werden in ähnlicher Weise aufgebaut, nur wird statt der binären Darstellung die Zahl verwendet $ p $-one und alle Berechnungen werden modulo durchgeführt $ p $.

    Isomorphismus von Feldern und Galoisfeldern beliebiger Größe


    Aber was passiert, wenn wir ein anderes irreduzibles Polynom wählen? Sie können sogar eine allgemeinere Frage stellen. Angenommen, ich mag all diese Polynome und Spaltenunterteilungen überhaupt nicht, dann sollte ich meine konsistente Multiplikationstabelle nach einem anderen Prinzip aufstellen. Wird dies etwas grundlegend Neues sein? Die Antwort lautet nein. Alle diese erhaltenen Felder sind isomorph .

    Aus der „mathematischen“ Sprache übersetzt bedeutet Isomorphismus, dass die Unterschiede nur in der Bezeichnung der Feldelemente liegen und eines durch Auswahl der entsprechenden Abbildungsregel auf das andere reduziert werden kann.

    Es gibt zwei Arten von endlichen Mengen von Elementen, die wir bisher untersucht haben. Die erste Art von Mengen hatte eine Anzahl von Elementen, die einer Primzahl entsprachen$ p $. In solchen Mengen konnten wir Multiplikations- und Additionstabellen nur mit modularer Arithmetik spezifizieren. Der zweite Typ umfasst Sätze mit$ p ^ n $, $ p $ - einfach $ n> 1 $Anzahl der Artikel. Bei solchen Mengen ist es möglich, die Multiplikation / Addition unter Verwendung eines Schemas mit Polynomen anzugeben. Ist es möglich, Multiplikation / Addition für Mengen beliebiger Größe, beispielsweise mit 6 Elementen, auf ähnliche Weise einzustellen? Die Antwort ist nein, es ist unmöglich.

    In der Tat werden endliche Felder Galois-Felder genannt, weil er ihre folgenden wichtigen Eigenschaften entdeckte:

    1. Die Anzahl der Elemente eines endlichen Feldes hat immer die Form $ p ^ n $wo $ p $ prime und $ n $ jede natürliche.
    2. Alle Größenfelder $ p ^ n $ sind isomorph.

    Fazit


    Der zweite Artikel des Zyklus geht zu Ende. Die ersten beiden Artikel enthielten kurze theoretische Informationen zu Reed-Solomon-Codes und Galois-Feldern. Im nächsten Teil werde ich näher auf die Merkmale der Software-Implementierung der obigen Algorithmen eingehen. Vielen Dank.

    Jetzt auch beliebt: