Paritätsbit - Parity bit
| 7 Bit Daten |
(Zählung von 1-Bit) | 8 Bit inklusive Parität | |
|---|---|---|---|
| sogar | seltsam | ||
| 0000000 | 0 | 0000000 0 | 0000000 1 |
| 1010001 | 3 | 1010001 1 | 1010001 0 |
| 1101001 | 4 | 1101001 0 | 1101001 1 |
| 1111111 | 7 | 1111111 1 | 1111111 0 |
Ein Paritätsbit oder Prüfbit ist ein Bit , das einer Binärcodefolge hinzugefügt wird . Paritätsbits sind eine einfache Form von Fehlererkennungscode . Paritätsbits werden im Allgemeinen auf die kleinsten Einheiten eines Kommunikationsprotokolls angewendet, typischerweise 8-Bit- Oktette (Bytes), obwohl sie auch separat auf eine gesamte Nachrichtenfolge von Bits angewendet werden können.
Das Paritätsbit stellt sicher, dass die Gesamtzahl der 1-Bits im String gerade oder ungerade ist . Dementsprechend gibt es zwei Varianten von Paritätsbits: gerades Paritätsbit und ungerades Paritätsbit . Bei gerader Parität wird für einen gegebenen Satz von Bits das Auftreten von Bits gezählt, deren Wert 1 ist. Wenn dieser Zählwert ungerade ist, wird der Paritätsbitwert auf 1 gesetzt, wodurch die Gesamtzahl der Einsen im gesamten Satz (einschließlich des Paritätsbits) zu einer geraden Zahl wird. Wenn die Anzahl der Einsen in einem bestimmten Bitsatz bereits gerade ist, ist der Wert des Paritätsbits 0. Bei ungerader Parität wird die Codierung umgekehrt. Wenn für einen gegebenen Satz von Bits die Anzahl der Bits mit einem Wert von 1 gerade ist, wird der Paritätsbitwert auf 1 gesetzt, wodurch die Gesamtzahl von 1s im gesamten Satz (einschließlich des Paritätsbits) zu einer ungeraden Zahl wird. Wenn die Anzahl der Bits mit einem Wert von 1 ungerade ist, ist die Anzahl bereits ungerade, sodass der Wert des Paritätsbits 0 ist. Gerade Parität ist ein Sonderfall einer zyklischen Redundanzprüfung (CRC), bei der der 1-Bit-CRC von das Polynom x +1.
Wenn ein Bit an einem Punkt vorhanden ist, der ansonsten einem Paritätsbit zugeordnet ist, aber nicht für die Parität verwendet wird, kann es als Markierungs-Paritätsbit bezeichnet werden, wenn das Paritätsbit immer 1 ist, oder als Leerparitätsbit, wenn das Bit immer 0 ist In solchen Fällen, in denen der Wert des Bits konstant ist, kann es als Stick-Paritätsbit bezeichnet werden , obwohl seine Funktion nichts mit Parität zu tun hat. Die Funktion solcher Bits variiert mit dem Systemdesign, aber Beispiele für Funktionen für solche Bits umfassen die Zeitsteuerung oder die Identifizierung eines Pakets als Daten- oder Adressenbedeutung. Wenn sein tatsächlicher Bitwert für seine Funktion irrelevant ist, kommt das Bit einem egal-Term gleich .
Parität
In der Mathematik kann sich Parität auf die Gleichheit oder Ungeradheit einer ganzen Zahl beziehen, die, wenn sie in ihrer binären Form geschrieben wird , nur durch Untersuchung ihres niederwertigsten Bits bestimmt werden kann .
In der Informationstechnologie bezieht sich Parität auf die Gleichheit oder Ungeradheit der Anzahl dieser Bits mit dem Wert eins, wenn ein beliebiger Satz von Binärziffern gegeben ist. Da die Parität durch den Zustand jedes einzelnen Bits bestimmt wird, ermöglicht diese Eigenschaft der Parität – da sie von allen Bits abhängig ist und ihren Wert von gerader zu ungerader Parität ändert, wenn sich ein Bit ändert – ihre Verwendung in Fehlererkennungs- und -korrekturverfahren .
In der Telekommunikation dient die Parität, auf die sich einige Protokolle beziehen, der Fehlererkennung . Das Übertragungsmedium ist an beiden Endpunkten voreingestellt, um entweder ungerade Parität oder gerade Parität zu vereinbaren. Für jede übertragungsbereite Bitfolge (Datenpaket) berechnet der Sender sein Paritätsbit, Null oder Eins, damit es der vereinbarten Parität, gerade oder ungerade, entspricht. Der Empfänger dieses Pakets überprüft zuerst, ob die Parität des Pakets als Ganzes mit der voreingestellten Vereinbarung übereinstimmt, und fordert dann, wenn in diesem Paket ein Paritätsfehler aufgetreten ist, eine erneute Übertragung dieses Pakets an.
In der Informatik der Parität Streifen oder Paritätsplatte in einem RAID - Array bietet fehler- Korrektur . Paritätsbits werden mit einer Geschwindigkeit von einem Paritätsbit pro n Bits geschrieben, wobei n die Anzahl der Platten im Array ist. Wenn ein Lesefehler auftritt, wird jedes Bit im Fehlerbereich aus seinem Satz von n Bits neu berechnet . Auf diese Weise erzeugt die Verwendung eines Paritätsbits "Redunanz" für einen Bereich von der Größe eines Bits bis zur Größe einer Platte. Siehe § Redundantes Array unabhängiger Festplatten weiter unten.
In der Elektronik kann das Transkodieren von Daten mit Parität sehr effizient sein, da XOR- Gatter das ausgeben, was einem Prüfbit entspricht, das eine gerade Parität erzeugt, und das XOR-Logikdesign lässt sich leicht auf eine beliebige Anzahl von Eingängen skalieren. XOR- und UND-Strukturen umfassen den Großteil der meisten integrierten Schaltungen.
Fehlererkennung
Wenn eine ungerade Anzahl von Bits (einschließlich des Paritätsbits) falsch übertragen wird, ist das Paritätsbit falsch und zeigt damit an, dass bei der Übertragung ein Paritätsfehler aufgetreten ist. Das Paritätsbit ist nur zur Fehlererkennung geeignet; es kann keine Fehler korrigieren , da es keine Möglichkeit gibt, festzustellen, welches bestimmte Bit beschädigt ist. Die Daten müssen vollständig verworfen und von Grund auf neu übertragen werden . Auf einem verrauschten Übertragungsmedium kann eine erfolgreiche Übertragung daher lange dauern oder sogar nie stattfinden. Parität hat jedoch den Vorteil, dass sie nur ein einziges Bit verwendet und nur eine Anzahl von XOR-Gattern zur Erzeugung benötigt. Ein Beispiel für einen Fehlerkorrekturcode finden Sie unter Hamming -Code.
Die Paritätsbitprüfung wird gelegentlich für die Übertragung von ASCII- Zeichen verwendet, die 7 Bits haben, wobei das 8. Bit als Paritätsbit verbleibt.
Das Paritätsbit kann beispielsweise wie folgt berechnet werden. Angenommen, Alice und Bob kommunizieren und Alice möchte Bob die einfache 4-Bit-Nachricht 1001 senden.
| Art der Bitparität | Erfolgreiches Übertragungsszenario |
|---|---|
| Gleichmäßige Parität |
Alice möchte senden: 1001 Alice berechnet den Paritätsbitwert: 1+0+0+1 (mod 2) = 0 Alice fügt Paritätsbit hinzu und sendet: 10010 Bob erhält: 10010 Bob berechnet die Parität: 1+0+0+1+0 (mod 2) = 0 Bob meldet die korrekte Übertragung, nachdem er das erwartete gleichmäßige Ergebnis beobachtet hat. |
| Ungerade Parität |
Alice möchte senden: 1001 Alice berechnet den Paritätsbitwert: 1+0+0+1 (mod 2) = 0 Alice fügt Paritätsbit hinzu und sendet: 1001 1 Bob erhält: 10011 Bob berechnet die Gesamtparität: 1+0+0+1+1 (mod 2) = 1 Bob meldet die korrekte Übertragung, nachdem er das erwartete ungerade Ergebnis beobachtet hat. |
Dieser Mechanismus ermöglicht die Erkennung von Einzelbitfehlern, denn wenn ein Bit aufgrund von Leitungsrauschen umgedreht wird, gibt es eine falsche Anzahl von Einsen in den empfangenen Daten. In den beiden obigen Beispielen stimmt Bobs berechneter Paritätswert mit dem Paritätsbit in seinem empfangenen Wert überein, was anzeigt, dass keine Einzelbitfehler vorliegen. Betrachten Sie das folgende Beispiel mit einem Übertragungsfehler im zweiten Bit mit XOR:
| Art des Bitparitätsfehlers | Szenario einer fehlgeschlagenen Übertragung |
|---|---|
| Gleichmäßige Parität
Fehler im zweiten Bit |
Alice möchte senden: 1001
Alice berechnet den Paritätsbitwert: 1^0^0^1 = 0 Alice fügt Paritätsbit hinzu und sendet: 10010 ...ÜBERTRAGUNGSFEHLER... Bob erhält: 1 1 010 Bob berechnet die Gesamtparität: 1^1^0^1^0 = 1 Bob meldet eine falsche Übertragung, nachdem er ein unerwartetes ungerades Ergebnis beobachtet hat. |
| Gleichmäßige Parität
Fehler im Paritätsbit |
Alice möchte senden: 1001
Alice berechnet geraden Paritätswert: 1^0^0^1 = 0 Alice sendet: 10010 ...ÜBERTRAGUNGSFEHLER... Bob erhält: 1001 1 Bob berechnet die Gesamtparität: 1^0^0^1^1 = 1 Bob meldet eine falsche Übertragung, nachdem er ein unerwartetes ungerades Ergebnis beobachtet hat. |
Es gibt eine Beschränkung auf Paritätsschemata. Ein Paritätsbit erkennt garantiert nur eine ungerade Anzahl von Bitfehlern. Wenn eine gerade Anzahl von Bits Fehler aufweist, zeichnet das Paritätsbit die richtige Anzahl von Einsen auf, obwohl die Daten beschädigt sind. (Siehe auch Fehlererkennung und -korrektur .) Betrachten Sie dasselbe Beispiel wie zuvor mit einer geraden Anzahl von beschädigten Bits:
| Art des Bitparitätsfehlers | Szenario einer fehlgeschlagenen Übertragung |
|---|---|
| Gleichmäßige Parität
Zwei beschädigte Bits |
Alice möchte senden: 1001
Alice berechnet geraden Paritätswert: 1^0^0^1 = 0 Alice sendet: 10010 ...ÜBERTRAGUNGSFEHLER... Bob erhält: 1 1 01 1 Bob berechnet die Gesamtparität: 1^1^0^1^1 = 0 Bob meldet eine korrekte Übertragung, obwohl sie tatsächlich falsch ist. |
Bob beobachtet wie erwartet eine gerade Parität, wodurch er die zwei Bitfehler nicht abfangen kann.
Verwendungszweck
Wegen ihrer Einfachheit wird die Parität in vielen Hardwareanwendungen verwendet, bei denen eine Operation im Fall von Schwierigkeiten wiederholt werden kann oder wo die einfache Erkennung des Fehlers hilfreich ist. Zum Beispiel können die SCSI und PCI - Busse verwenden Paritätsübertragungsfehler, und viele zu detektieren Mikroprozessor Befehlscaches beinhalten Paritätsschutz. Da die I-Cache- Daten nur eine Kopie des Hauptspeichers sind , können sie ignoriert und erneut abgerufen werden, wenn sie beschädigt sind.
Bei der seriellen Datenübertragung sind 7 Datenbits, ein gerades Paritätsbit und ein oder zwei Stoppbits ein übliches Format . Dieses Format nimmt alle 7-Bit- ASCII- Zeichen in einem 8-Bit-Byte auf. Andere Formate sind möglich; 8 Datenbits plus ein Paritätsbit können alle 8-Bit-Bytewerte übertragen.
In seriellen Kommunikationszusammenhängen wird die Parität in der Regel erzeugt und durch Interface - Hardware überprüft (beispielsweise ein UART ) und zum Empfang handelt , das Ergebnis an einen verfügbaren Prozessor , wie beispielsweise die CPU (und so auch zum Beispiel das Betriebssystem ) über eine Statusbit in einem Hardwareregister in der Schnittstellenhardware . Die Behebung des Fehlers erfolgt normalerweise durch erneutes Übertragen der Daten, deren Details normalerweise durch Software (zB die E/A-Routinen des Betriebssystems) gehandhabt werden.
Wenn die Gesamtzahl der übertragenen Bits, einschließlich des Paritätsbits, gerade ist, hat die ungerade Parität den Vorteil, dass sowohl die Null- als auch die Eins-Muster als Fehler erkannt werden. Wenn die Gesamtzahl von Bits ungerade ist, wird nur eines der Muster als Fehler erkannt, und die Wahl kann basierend darauf getroffen werden, welcher der häufigere Fehler zu erwarten ist.
RAID-Array
Paritätsdaten werden von RAID-Arrays ( Redundant Array of Independent/Inexpensive Disks ) verwendet, um Redundanz zu erzielen . Wenn ein Laufwerk im Array ausfällt, können die verbleibenden Daten auf den anderen Laufwerken mit den Paritätsdaten (mithilfe der booleschen XOR- Funktion) kombiniert werden, um die fehlenden Daten zu rekonstruieren.
Angenommen, zwei Laufwerke in einem RAID 5- Array mit drei Laufwerken enthielten die folgenden Daten:
| Laufwerk 1: | 01101101 |
| Laufwerk 2: | 11010100 |
Um die Paritätsdaten für die beiden Laufwerke zu berechnen, wird ein XOR an ihren Daten durchgeführt:
| 01101101 | |
| XOR | 11010100 |
| 10111001 |
Die resultierenden Paritätsdaten 10111001 werden dann auf Laufwerk 3 gespeichert.
Sollte eines der drei Laufwerke ausfallen, kann der Inhalt des ausgefallenen Laufwerks auf einem Ersatzlaufwerk rekonstruiert werden, indem die Daten der verbleibenden Laufwerke derselben XOR-Operation unterzogen werden. Wenn Laufwerk 2 ausfallen sollte, könnten seine Daten mithilfe der XOR-Ergebnisse des Inhalts der beiden verbleibenden Laufwerke Laufwerk 1 und Laufwerk 3 wiederhergestellt werden:
| Laufwerk 1: | 01101101 |
| Laufwerk 3: | 10111001 |
wie folgt:
| 10111001 | |
| XOR | 01101101 |
| 11010100 |
Das Ergebnis dieser XOR-Berechnung ergibt den Inhalt von Laufwerk 2. 11010100 wird dann auf Laufwerk 2 gespeichert, wodurch das Array vollständig repariert wird.
XOR-Logik ist auch äquivalent zur geraden Parität (weil ein XOR b XOR c XOR ... als XOR ( a , b , c , ...) behandelt werden kann, was ein n-ärer Operator ist, der genau dann wahr ist, wenn an ungerade Anzahl von Argumenten ist wahr). Das obige XOR-Konzept gilt also in ähnlicher Weise für größere RAID-Arrays mit Parität, die eine beliebige Anzahl von Festplatten verwenden. Bei einem RAID 3-Array mit 12 Laufwerken nehmen 11 Laufwerke an der oben gezeigten XOR-Berechnung teil und ergeben einen Wert, der dann auf dem dedizierten Paritätslaufwerk gespeichert wird.
Bei RAID-DP werden Erweiterungen und Variationen des Paritätsbitmechanismus "doppelte", "duale" oder "diagonale" Parität verwendet .
Geschichte
Eine Paritätsspur war 1951 auf dem ersten Magnetband-Datenspeicher vorhanden . Eine Parität in dieser Form, die über mehrere parallele Signale angewendet wird, wird als Querredundanzprüfung bezeichnet . Dies kann mit einer Parität kombiniert werden, die über mehrere Bits berechnet wird, die auf einem einzelnen Signal gesendet werden, einer Längsredundanzprüfung . In einem parallelen Bus gibt es ein Längsredundanzprüfbit pro parallelem Signal.
Parität wurde auch bei zumindest einigen Papierband-( Lochband- )Dateneingabesystemen (die den Magnetbandsystemen vorausgingen) verwendet. Auf den Systemen, die von der britischen Firma ICL (ehemals ICT) verkauft wurden, hatte das 1 Zoll breite (25 mm) Papierband 8 Lochpositionen, die quer verlaufen, wobei die 8. für die Parität war. Für die Daten wurden 7 Stellen verwendet, zB 7-Bit-ASCII. In die 8. Position wurde je nach Anzahl der gestanzten Datenlöcher ein Loch gestanzt.