Parity-Bit

Codetafel - dualergänztes gerades Paritätsbit (E = even = gerade)
Codetafel - dualergänztes ungerades Paritätsbit (O = odd = ungerade)

Die Paritätskontrolle dient der Erkennung fehlerhaft übertragener Informationswörter. Als Informationswort wird hier eine Folge von Bits bezeichnet. "Parität" bezeichnet die Anzahl der mit 1 belegten Bits im Informationswort und heißt gerade (engl. "even"), wenn die Anzahl dieser Bits gerade ist, andernfalls ungerade (engl. "odd"). Die Paritätskontrollcodierung hängt dem Informationswort ein Paritätskontrollbit, auch Paritybit genannt, an. Dies geschieht so, dass alle zu übertragenden Codewörter die gleiche Parität haben. Je nachdem, ob gerade oder ungerade Parität übertragen werden soll, erfolgt die Ergänzung mit E oder O, entsprechend den Beispielen in den Graphiken. Das Ergebnis, welches um ein Bit länger ist als das Informationswort, wird hier Codewort genannt. Die Methode der Fehlererkennung mittels Paritätsbits heißt Paritätsprüfung. Da nicht bekannt ist, wo innerhalb des Codewortes der Fehler aufgetreten ist, ist keine Fehlerkorrektur möglich. Außerdem ist bei einem Paritätsbit N = 1 nur eine ungerade Anzahl von Bitfehlern in einem Codewort feststellbar. Eine gerade Anzahl von Bitfehlern wird nicht festgestellt.

Für die Fehlerkorrektur gibt es Weiterentwicklungen wie das unten dargestellte mehrdimensionale Parityverfahren, den Hamming-Code oder das Fehlerkorrekturverfahren.

Inhaltsverzeichnis

Erzeugung N Paritätsbits

Beim Sender werden alle Bits eines Datenblocks (hier Informationswort) modulo N addiert. Entsprechend lassen sich bis zu N Bitfehler erkennen. Für N=1 wird die Summe der Einsen (Paritätssumme) im Informationswort berechnet. Ist diese Summe gerade wird bei Even-Parity das Paritätsbit zu Null. Entsprechend ergibt eine ungerade Summe des Informationswortes das Paritätsbit Eins. (Dies gilt umgekehrt bei Odd-Parity.)

Beispiel 1 (Even-Parity):

  • Ist für die Datenübertragung Even-Parity (Paritätssumme gerade → Paritybit: 0, Paritätssumme ungerade → Paritybit: 1) festgelegt, so gilt für die beiden nachfolgenden Beispiele:
  • Das Informationswort 0011.1010 hat vier Einsen. Vier ist eine gerade Zahl, das Paritätskontrollbit ist also die Null, und das resultierende Codewort ist 0011.1010 0.
  • Das Informationswort 1010.0100 hat hingegen eine ungerade Paritätssumme und wird in das Codewort 1010.0100 1 codiert.

Beispiel 2 (Odd-Parity):

  • Ist für die Datenübertragung Odd-Parity (Paritätssumme gerade → Paritybit: 1, Paritätssumme ungerade → Paritybit: 0) festgelegt, so gilt für die beiden nachfolgenden Beispiele:
  • Das Informationswort 0011.1010 hat vier Einsen. Vier ist eine gerade Zahl, das Paritätskontrollbit ist also die Eins, und das resultierende Codewort ist 0011.1010 1.
  • Das Informationswort 1010.0100 hat hingegen eine ungerade Paritätssumme und wird in das Codewort 1010.0100 0 codiert.
Summe der Einsen eines Codeworts Wert des Paritätbits bei Even-Parity Wert des Paritätbits bei Odd-Parity
gerade 0 1
ungerade 1 0

Praktisch kann das Paritätsbit sowohl per Hardware als auch per Software erzeugt werden, siehe Paritätsgenerator.

Empfang des Codewortes mit N Paritätsbits

Der Empfänger addiert die Bits des empfangenen Codewortes ebenfalls und überprüft, ob er denselben Code berechnet hat. N ist spezifisch für das jeweilige Datenübertragungsverfahren. Wenn N = 1, dann besteht der Parity-Check-Code aus genau einem Paritätsbit, bei N = 2 aus 2 Paritätsbit, etc.

Bei der asynchronen Datenübertragung über eine serielle RS232-Schnittstelle ist die Blockgröße gewöhnlich 8 Bit und N = 1. Sollte ein Bit verfälscht werden (eine Null in eine Eins oder eine Eins in eine Null), so ist die Paritätssumme des resultierenden Codewortes ungerade, und der Dekodierer erkennt, dass es zu einem Fehler gekommen ist. Es ist aber für den Dekodierer nicht möglich, den Fehler zu korrigieren, da nicht bekannt ist, welches Bit verfälscht wurde. Der Dekoder erkennt also maximal einen Fehler und kann maximal null Fehler korrigieren, denn falls mehr als ein Bit verfälscht wurde, so ist es eventuell gar nicht möglich, den Fehler zu erkennen, da die Paritätssumme dann auch gerade sein kann. Man sagt, der Paritätskontrollcode sei 1-fehlererkennend und 0-fehlerkorrigierend.

Anwendungsbereich

Paritätsbits finden u. a. in der DFÜ, Netzwerktechnik und bei Speichermodulen Verwendung.

Die ursprüngliche Form der ASCII-Tabelle besteht aus 128 Zeichen, jedes Zeichen ist durch eine Folge von sieben Bits eindeutig festgelegt. Da ein Rechner acht Bits zu einem Byte zusammenfasst, wurde dieses achte Bit gerne verwendet, um ein Paritätskontrollbit anzuhängen. Heute ist dies jedoch kaum noch üblich, stattdessen wird das achte Bit fast immer zur Erweiterung des Zeichensatzes über 128 Zeichen hinaus verwendet.

Gerade und ungerade Parität

Unterschieden wird zwischen zwei Paritätsprotokollen: even (gerade) und odd (ungerade). In beiden Fällen wird die Anzahl der Einsen innerhalb des zugeordneten Wortes ermittelt. Ist die Parität „even“ (gerade) eingestellt, so wird das Paritätsbit gesetzt, falls eine ungerade Anzahl Datenbits im Zeichen gesetzt ist. Im Falle „odd“ (ungerade) wird das Bit gesetzt, falls eine gerade Anzahl Datenbits innerhalb des Zeichens gesetzt ist. Mit „gerade“ oder „ungerade“ ist also die Anzahl gesetzter Datenbits inklusive des Paritätsbits gemeint.

Beispiel:
Im Beispiel soll eine ungerade („Odd“) Parität hergestellt werden:

„Wort“ Paritätsbit Bemerkungen
0100.1110 1 Das „Wort“ enthält bereits vier Einsen, das Paritätsbit wird gesetzt, um ein ungerades Codewort (fünf Einsen) herzustellen.
1011.0110 0 Die Parität ist mit fünf Einsen schon ungerade, das Paritätsbit wird nicht gesetzt.
0100.0000 1 Das gesamte Codewort hat hier zwei Einsen obwohl die Anzahl ungerade sein sollte. Ein Fehler ist aufgetreten. Entweder wurde das Paritätsbit falsch berechnet, oder das „Wort“ wurde falsch übertragen.

Ist das Paritätsbit immer 1, dann spricht man von einer Mark-Parität (es enthält keine Information); ist es immer 0, spricht man von Space-Parität (es stellt einen Leerraum dar).

Mehrdimensionale Paritätskontrolle

(auch: Kreuzparität oder Blockparität)

Als Erweiterung der oben dargestellten, eindimensionalen Paritätskontrolle lässt sich auch ein zwei-, bzw. höherdimensionales Paritätsverfahren erstellen, welches als Erweiterung nicht nur bestimmte Fehler erkennen kann sondern auch bestimmte Fehlerkombinationen korrigieren kann. Die Paritätskontrolle wird damit zu einem fehlererkennenden und fehlerkorrigierenden Verfahren.

Die Konstruktion soll anhand einer einfachen zweidimensionalen Paritätskontrolle für acht Bit lange Datenwörter dargestellt werden:

  • Es werden acht Nutzdatenwörter zu acht Bit Länge (ein Byte) in einem Quadrat (Array) zusammengefasst. Es umfasst somit jede Zeile und jede Spalte genau acht Bit.
  • Zu jeder Zeile wird nach dem Verfahren wie oben dargestellt ein Paritätsbit berechnet und als neuntes Datenbit jeder Zeile nachgestellt.
  • Zu jeder Spalte wird nach dem Verfahren wie oben dargestellt ein Paritätsbit berechnet und als neunte Zeile angeschrieben.

Das so entstandene Array umfasst neun mal neun Datenbits und kann geeignet, beispielsweise seriell, übertragen werden. Auf Empfängerseite wird der Datenblock zu neun Datenwörtern empfangen und als Array abgebildet. Tritt nun an einer bestimmten Stelle ein einzelner Bitfehler auf, so ist die Parität genau der betreffenden Zeile und Spalte fehlerhaft. Somit kann das fehlerhafte Bit eindeutig lokalisiert werden und durch Invertierung in den richtigen Zustand umgewandelt werden.

Mit diesem Verfahren sind alle einzelnen Bitfehler pro Block eindeutig erkennbar und korrigierbar. Treten mehrere Bitfehler in einem Block auf, ist die Fehlerkorrektur nicht mehr in allen Fällen möglich. Allerdings sind fehlerhafte Blöcke unter Umständen noch als fehlerhaft erkennbar, was bei diesen Verfahren beispielsweise alle zweifachen Bitfehler pro Block umfasst.

Erweiterte Paritätskontrolle (Blockcodes)

Die Paritätskontrolle wird in erweiterter Form auch bei diversen Blockcodes wie dem Hamming-Code oder dem Low-Density-Parity-Check-Code sowohl zu Fehlererkennung als auch Fehlerkorrektur verwendet. Diese Codes basieren wie oben dargestellt auf einem Nutzdatenblock fixer Länge, an welchem aber nicht nur ein Paritybit, sondern mehrere Paritybits angehängt werden, um dann das eigentliche Codewort zu ergeben. Um nicht nur eine Fehlererkennung, sondern auch Fehlerkorrektur mit jenen Paritybits zu ermöglichen, werden in die einzelnen Parity-Bits pro Block unterschiedliche Stellen (Bits) des Nutzdatenblocks eingerechnet. Die Auswahl dieser Stellen pro Paritybit muss nach bestimmten Regeln erfolgen und bestimmte Kriterien wie die lineare Unabhängigkeit der einzelnen Paritystellen gewährleisten, um eine Fehlerkorrektur zu ermöglichen. Aufgrund dieser Codekonstruktionen ergeben sich Möglichkeiten, im Falle von Übertragungsfehlern die genaue Bitposition(en) der Fehler in den Nutzdatenblock zu bestimmen und die betroffenen fehlerhaften binären Stellen zu korrigieren.

Eine Erweiterung dieser auf der mehrstelligen Paritätskontrolle basierender Blockcodes stellen die sogenannten Turbo-Product-Codes (TPC) dar, welche einen erweiterten Parity-Blockcode wie den Hamming-Code mit der oben erwähnten mehrdimensionalen Paritätskontrolle in einer iterativen Dekodierung zwischen Zeilen und Spalten des zweidimensionalen Datenblockes verbindet.

Weblinks


Wikimedia Foundation.

Schlagen Sie auch in anderen Wörterbüchern nach:

  • parity bit — par i*ty bit , n. (Computers) The bit within a data structure which is assigned a value of 1 or 0 so as to make the parity[7] of the data structure odd or even. Data structures may or may not have parity bits, dpending on whether the system does… …   The Collaborative International Dictionary of English

  • Parity bit — 7 bits of data (number of 1s) 8 bits including parity even odd 0000000 (0) 00000000 10000000 1010001 (3) 11010001 01010001 1101001 (4) 01101001 11101001 1111111 (7) 11111111 …   Wikipedia

  • parity bit — Most modems have the capability to send an extra bit for every byte sent, which is used to help sense errors. This is called the parity bit. It can be set to no parity, mark parity, space parity, odd parity, or even parity. Most BBS s use do not… …   Dictionary of telecommunications

  • parity bit — lyginumo bitas statusas T sritis automatika atitikmenys: angl. parity bit; parity check bit vok. Paritätsbit, n; Paritätskontrollbit, n rus. бит четности, m; контрольный двоичный разряд четности, m; проверочный двоичный разряд четности, m pranc.… …   Automatikos terminų žodynas

  • parity bit — lyginumo bitas statusas T sritis informatika apibrėžtis ↑Bitas, papildantis ↑baitą, kompiuterio ↑žodį arba kitokią duomenų porciją taip, kad visų bitų, lygių vienetui, skaičius būtų lyginis. Naudojamas duomenų įrašymui ir persiuntimui patikrinti …   Enciklopedinis kompiuterijos žodynas

  • parity bit — bit that is transmitted along with the information that indicates whether it is odd or even …   English contemporary dictionary

  • parity bit — noun (computer science) a bit that is used in an error detection procedure in which a 0 or 1 is added to each group of bits so that it will have either an odd number of 1 s or an even number of 1 s; e.g., if the parity is odd then any group of… …   Useful english dictionary

  • Parity Bit — Prüfbit; zusätzliches ⇡ Bit, durch das jedes ⇡ Byte oder ⇡ Wort in der Weise ergänzt wird, dass die Anzahl aller dualen Einsen entweder immer ungerade (Odd Parity) oder immer gerade (Even Parity) ist. Auf diese Weise sollen einfache… …   Lexikon der Economics

  • parity bit — noun Date: 1957 a bit added to an array of bits (as on magnetic tape) to provide parity …   New Collegiate Dictionary

  • parity bit — noun A bit (binary digit) used to indicate whether the number of bits in a given set with value of one is even or odd. Parity bits are used as a simple error detection code …   Wiktionary


Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”

We are using cookies for the best presentation of our site. Continuing to use this site, you agree with this.