WikiDer > Blockcode

In dem Codierungstheorie ist ein Blockcode ein Fehlerkorrekturcode Sein Hauptmerkmal besteht darin, dass es die zu sendenden Daten in Blöcke einer festen Länge aufteilt, wonach jeder Block codiert wird. Blockcodes nehmen einen wichtigen Platz innerhalb der Fehlerkorrekturcodes ein. Es gibt alle Arten von Blockcodes mit vielen praktischen Anwendungen.

Einige Beispiele für Blockcodes sind Reed-Solomon-Codes, Hamming-Codes und Reed-Müller-Codes. Darüber hinaus sind diese Codes linear.

Blockcodes werden als abstraktes Konzept untersucht. Dadurch lassen sich beispielsweise gemeinsame Merkmale wie Begrenzungen der maximal erfassbaren oder behebbaren Fehleranzahl festlegen.

Der Begriff Blockcode wird manchmal für jeden Fehlerkorrekturcode verwendet, der eine feste Anzahl von Bits von Ausgangsdaten aus einem Block mit einer festen Anzahl von Bits von Eingangsdaten erzeugt. Mit dieser Definition zum Beispiel Turbo-Codes können auch als Blockcodes gezählt werden. Dieser Artikel befasst sich mit den "algebraischen Blockcodes", d. h. Blockcodes, bei denen Datenblöcke unabhängig voneinander codiert werden (was bei Turbocodes nicht der Fall ist).

Operation

Bei der Datenübertragung über a Kommunikationskanal der Sender sendet einen Datenstrom an die Empfänger. Jeder Kommunikationskanal leidet jedoch unter Unvollkommenheiten (zum Beispiel durch Tür Lärm), so dass die Übertragung nicht rund läuft. Mit einem Blockcode wird der Datenstrom aufgeteilt in Informationsblöcke oder Lebensmittel mit fester Länge ${displaystyle k}$. Jeder Block wird dann unabhängig von anderen Blöcken in einen umgewandelt (kodiert). Codewort, ein Block fester Länge ${displaystyle n}$. Bei dieser Konvertierung werden jedem Block zusätzliche Informationen hinzugefügt; Durch die Auswahl der hinzugefügten Informationen auf diese Weise können Fehler erkannt oder korrigiert werden. Ein einfaches Beispiel ist das Hinzufügen Paritätsbits zu jedem Block.

Beim Empfänger geschieht das Umgekehrte: Die empfangenen Codewörter, die möglicherweise verfälscht sind, werden so gut wie möglich dekodiert, um die Originaldaten zu finden.

Formale Beschreibung und Parameter

Ein Blockcode ist mathematisch a Injektion${displaystyle Ccolon Sigma ^{k} oder Sigma ^{n}}$. Hier ist ${Anzeigestil Sigma }$ eine endliche, nicht leere Menge und ihre ${displaystyle k}$ und ${displaystyle n}$ ganze Zahlen. Im Folgenden werden die Parameter im Detail erklärt.

Das Alphabet

Der zu verschlüsselnde Datenstrom wird wie folgt modelliert: Schnur von Zeichen aus einem Alphabet ${Anzeigestil Sigma }$. Die Größe des Alphabets ${Anzeigestil |Sigma |}$ wird oft als ${Anzeigestil q}$. wenn ${Anzeigestil q=2}$, dann spricht man von a binärer Blockcode. In vielen Anwendungen ist es wünschenswert, dass ${Anzeigestil q}$ eine Macht von a Primzahl verursacht ${Anzeigestil Sigma }$ kann als die endliches Feld/Körper${displaystyle mathbb {F}_{q}}$.

Die Nachrichtenlänge k

Jede Nachricht ${displaystyle m}$ ist ein Element von ${Displaystil Sigma ^{k}}$, d. h. eine Zeichenfolge bestehend aus Symbolen von ${Anzeigestil Sigma }$ der Länge ${displaystyle k}$. Das ${displaystyle k}$ wird daher der Informationslänge, Nachrichtenlänge oder Abmessungen des Blockcodes.

Die Blocklänge nein

Die Blocklänge ${displaystyle n}$ ist die Anzahl der Symbole in einem Codewort. Die Elemente ${Anzeigestil c}$ von ${Displaystil Sigma ^{n}}$ sind also Strings der Länge ${displaystyle n}$ und entsprechen einem Block, der vom Empfänger empfangen werden kann. Daher heißen sie auch empfangene Worte erwähnt. Das Ergebnis der Codierung einer Nachricht ${displaystyle m}$ ist das Codewort ${Anzeigestil c}$ dieser Nachricht. Mathematischer: ${Anzeigestil c=C(m)}$.

Der Datenfluss R

Die Datenrate eines Blockcodes ist definiert als das Verhältnis zwischen Nachrichtenlänge und Blocklänge: ${Anzeigestil R=k/n}$.

Ein hoher Durchsatz bedeutet, dass ein Großteil des Codeworts aus der Nachricht besteht. In diesem Sinne misst der Durchfluss die Übertragungsrate und gibt ${Anzeigestil 1-R}$ das Überkopf was auftritt, weil die resultierenden Codewörter länger sind als die Nachricht. Von dem Informationstheorie Daraus folgt, dass die Durchflussmenge nie größer sein kann als ${Anzeigestil 1}$, da Daten im Allgemeinen nicht verlustfrei komprimiert werden können. Dies folgt auch daraus, dass ${Anzeigestil C}$ ist eine Spritze.

Die Distanz d und das gewicht w

Der (Mindest-)Abstand ${displaystyle d}$ eines Blockcodes ist die minimale Anzahl von Positionen, die sich zwischen zwei beliebigen Codewörtern unterscheiden, und der relative Abstand ${Anzeigestil-Delta }$ ist der Bruch ${displaystyle d/n}$. Paar ${Anzeigestil Delta(c_{1},c_{2})}$ das Hamming-Abstand zwischen den beiden Codewörtern ${displaystyle c_{1},c_{2}in Sigma ^{n}}$. Der Mindestabstand ${displaystyle d}$ des Codes ${Anzeigestil C}$ ist dann gegeben durch:

${displaystyle d:=min _{m_{1},m_{2}in Sigma ^{k} auf m_{1}eq m_{2}}Delta [C(m_{1}),C(m_{2} )]}$

Da jeder Code injektiv sein muss, unterscheidet sich jedes Codewort mindestens in einer Position von allen anderen Codewörtern, also ${displaystyle dgeq 1}$.

Das Gewicht ${Anzeigestil w}$ eines Codeworts ist die Anzahl der Nicht-Null-Stellen. Das Mindestgewicht ${displaystyle w_{min }}$ ist das kleinste Gewicht aller Codewörter oder das Gewicht des Codeworts mit der geringsten Anzahl von Nullen. Bei linearen Blockcodes entspricht der Mindestabstand dem Mindestgewicht:

${displaystyle min _{m_{1},m_{2}in Sigma ^{k} auf m_{1}eq m_{2}}Delta [C(m_{1}),C(m_{2})]= min _{m_{1},m_{2}in Sigma ^{k} auf m_{1}eq m_{2}}Delta [mathbf {0} ,C(m_{1}) C(m_{2}) ]=min _{min Sigma ^{k} auf meq mathbf {0} }w[C(m)]=w_{min }}$

Ein größerer Abstand ermöglicht mehr Fehlererkennung und -korrektur. Betrachten Sie beispielsweise nur Fehler, die Symbole der Codewörter ändern, aber niemals löschen oder hinzufügen (damit die Codewörter immer gleich lang bleiben). Dann ist die Anzahl der Fehler gleich der Anzahl der Stellen, an denen sich das gesendete und das empfangene Codewort unterscheiden. Ein Code mit Distanz ${displaystyle d}$ erlaubt ${Anzeigestil d-1}$ Fehler erkennen, da ${Anzeigestil d-1}$ Ein Positionswechsel führt nie zu einem anderen Codewort. Außerdem, wenn es nicht mehr als ${displaystyle(d-1)/2}$ Wenn während der Übertragung Fehler auftreten, kann der Empfänger das Codewort eindeutig decodieren. Denn für jedes empfangene Wort gibt es eine Distanz ${displaystyle(d-1)/2}$ ist höchstens ein Codewort. Wenn mehr Fehler auftreten, kann der Empfänger das empfangene Wort nicht eindeutig decodieren, da mehrere Codewörter übereinstimmen können.

Notation

Die Notation ${Anzeigestil (n,k,d)_{q}}$ beschreibt einen Blockcode über einem Alphabet ${Anzeigestil Sigma }$ der Größe ${Anzeigestil q}$, mit einer Blocklänge ${displaystyle n}$, Nachrichtenlänge ${displaystyle m}$ und Distanz ${displaystyle d}$. Wenn der Blockcode linear ist, können Klammern verwendet werden, um dies anzuzeigen: ${displaystyle [n,k,d]_{q}}$. Beide ${Anzeigestil q}$ als die ${displaystyle d}$ werden oft weggelassen: die ${Anzeigestil q}$ wenn es sich um einen Binärcode handelt (also ${Anzeigestil q=2}$) und der ${displaystyle d}$ wenn die Entfernung nicht wichtig, unbekannt oder schwer zu bestimmen ist.

Beispiele

Die meisten Fehlerkorrekturcodes sind Blockcodes.

• Der erste Fehlerkorrekturcode war der (7.4)-Hamming-Code, entwickelt von Richard Hamming im 1950. Dieser Code wandelt einen 4-Bit-Informationsblock um 3 7 in ein 7-Bit-Codewort um Paritätsbits hinzufügen. Dies ist ebenfalls ein linearer Code mit Abstand 3. In der obigen Notation würden wir den (7.4)-Hammingcode also als a . schreiben ${Displaystil [7,4,3]_{2}}$-Code.

• Reed-Solomon-Codes sind eine serie ${displaystyle [n,k,d]_{q}}$Codes, wo ${Anzeigestil d=n-k 1}$ und ${Anzeigestil q}$ ist eine Primärmacht.
• Rangcodes sind eine serie ${displaystyle [n,k,d]_{q}}$Codes mit ${displaystyle dleq n-k 1}$.
• Hadamard-Codes sind eine Sequenz ${displaystyle [n,k,d]_{2}}$Codes, mit ${Anzeigestil n=2^{k-1}}$ und ${Anzeigestil d=2^{k-2}}$.

Fehlererkennung und -korrektur

Ein Codewort ${displaystyle cin Sigma ^{n}}$ kann als betrachtet werden Punkt in einem ${displaystyle n}$-dimensional Platz${Displaystil Sigma ^{n}}$, wo der Code ${Anzeigestil C}$ eine Teilmenge von ${Displaystil Sigma ^{n}}$ ist. Ein Code ${Anzeigestil C}$ mit Abstand ${displaystyle d}$ bedeutet das ${displaystyle forall cin C}$ gilt, dass die Hamming-Kugel auf den Punkt zentriert ist ${Anzeigestil c}$ mit Radius ${Anzeigestil d-1}$ ist leer. Der Hammingbal bedeutet hier die Sammlung von ${displaystyle n}$-dimensionale Wörter, deren Hamming-Abstand zu ${Anzeigestil c}$ maximal ${Anzeigestil d-1}$ ist. Ähnliches hat einen Code ${Anzeigestil C}$ mit Abstand ${displaystyle d}$ folgende Eigenschaften:

• ${Anzeigestil C}$ können ${Anzeigestil d-1}$ Fehler erkennen. Denn ein Codewort ${Anzeigestil c}$ das einzige Codewort ist im Hammingbal mit Radius auf sich selbst zentriert ${Anzeigestil d-1}$ ist ein Fehlermuster mit ${Anzeigestil d-1}$ Fehler oder weniger wandeln niemals ein Codewort in ein anderes Codewort um. Wenn der Empfänger ein empfangenes Wort erhält, das nicht mit einem Codewort von übereinstimmt ${Anzeigestil C}$, werden die Fehler erkannt (aber es gibt keine Garantien für die Fehlerkorrektur, d. h. der Empfänger weiß, dass das empfangene Wort falsch ist, weiß aber nicht, was das gesendete Codewort ist).
• ${Anzeigestil C}$ können ${displaystyle extstyle leftlfloor {{d-1} over 2}ightfloor }$ Fehler korrigieren. Denn ein Codewort ${Anzeigestil c}$ das einzige Codewort ist im Hammingbal mit Radius auf sich selbst zentriert ${Anzeigestil d-1}$ h., die Hammingballs können auf zwei andere Codewörter mit Radius zentriert werden ${displaystyle extstyle leftlfloor {{d-1} over 2}ightfloor }$ überschneiden sich nie. Ein Fehler kann dann durch das dem empfangenen Wort am nächsten liegende Codewort korrigiert werden ${Anzeigestil y}$ Suche, solange die Anzahl der Fehler kleiner ist als ${displaystyle extstyle leftlfloor {{d-1} over 2}ightfloor }$ ist: es gibt dann nur ein Codewort im Hammingbal zentriert auf ${Anzeigestil y}$ mit Radius ${displaystyle extstyle leftlfloor {{d-1} over 2}ightfloor }$.
• Um mehr als zu dekodieren ${displaystyle(d-1)/2}$ Fehler, kann verwenden Listendecodierung oder Maximum-Likelihood-Decodierung.
• ${Anzeigestil C}$ können ${Anzeigestil d-1}$ fehlende Symbole korrigieren. Es ist zu beachten, dass die Position des verschwundenen Symbols bekannt sein muss.

Literaturverzeichnis

• (und) van Lint, Jack H., Einführung in die Codierungstheorie, 3. Auflage. Springer-Verlag. DOI:10.1007/978-3-642-58575-3 (1999), p. 33. ISBN 978-3-540-64133-9 .
• (und) MacWilliams, Florence J.; Sloane, Neil J. A., Die Theorie der fehlerkorrigierenden Codes. Nordholland (1893), p. 35. ISBN 9780444851932 .
• (und) Berrou, Claude, Codes und Turbo-Codes. Springer-Verlag. DOI:10.1007/978-2-8178-0039-4 (2010), „Blockcodes“, S. 109-166. ISBN 9782817800387 .