Bit-Stuffing
Englisch: bit stuffing
Einfügung von Informationsbits (Binärziffern) ohne Informationsgehalt in einen Datenstrom.
Bitstuffing: Nullen einfügen, um lange Bitfolgen zu unterbrechen
Bitstuffing ist das absichtliche Einfügen von zusätzlichen Bits in einen seriellen Datenstrom, um zu verhindern, dass lange Folgen identischer Bits bei der Übertragung natürlich auftreten. Die eingefügten Bits transportieren keine Information und werden vom Empfänger entfernt, wodurch die Originaldaten unversehrt bleiben. Diese Technik ist notwendig, um die Synchronisation in seriellen Kommunikationsleitungen aufrechtzuerhalten und zuverlässige Signalübergänge auf der physikalischen Schicht zu gewährleisten.
Die häufigste Anwendung erfolgt in asynchronen seriellen Protokollen wie RS-232, wo Bitstuffing verhindert, dass die Taktwiederherstellungsschaltkreise des Empfängers während längerer Pausen oder wiederholter Bitmuster die Synchronisation verlieren. In HDLC (High-Level Data Link Control) und ähnlichen synchronen Protokollen wird nach jeder Folge von fünf aufeinanderfolgenden Einsen ein Null-Bit eingefügt; der Empfänger entfernt diese eingefügten Nullen automatisch. Dies wird manchmal Null-Einfügung genannt, um es von anderen Stuffing-Methoden zu unterscheiden.
Stuffing wird notwendig, weil viele Kommunikationskanäle und Codierungsverfahren auf Übergänge im Signal angewiesen sind, um die Taktsynchronisation aufrechtzuerhalten. Eine lange Folge identischer Bits erzeugt keine Übergänge, weshalb der Phasenregelkreis des Empfängers abdriftet und nachfolgende Bitgrenzen verfehlt. Ein Datenstrom mit dreißig aufeinanderfolgenden Einsen stellt eine echte Synchronisationsgefahr dar; das Einfügen einer Null nach fünf Einsen garantiert, dass Übergänge regelmäßig auftreten und der Empfänger mit dem Takt des Senders synchron bleibt.
Auswirkungen auf Durchsatz und Komplexität
Der Overhead durch Bitstuffing hängt vom Datenmuster ab. Zufallsdaten aktivieren die Stuffing-Regel selten und verursachen minimalen Overhead, typischerweise unter 2 Prozent. Allerdings können Worst-Case-Datenströme, Dateien mit langen Einsfolgen, um 15 bis 20 Prozent wachsen. Dieser Overhead wird als Preis für zuverlässige Synchronisation akzeptiert und ist in den Protokollspezifikationen verankert. Konstrukteure müssen die maximale gestuffed-Frame-Länge berücksichtigen, wenn sie Pufferspeicher bemessen und die Leitungsauslastung berechnen.
Bitstuffing unterscheidet sich grundlegend von Vorwärtsfehlerkorrektionscodes, die Redundanz zur Fehlererkennung und Wiederherstellung hinzufügen. Gestuffed Bits sind für die Datenschicht transparent und erfüllen keine Fehlerprüfungsfunktion. Die Aufgabe des Empfängers ist mechanisch: Suche das verbotene Muster, entferne das eingefügte Bit und gebe den entstufften Strom an die oberen Schichten. Fehler beim Stuffing oder Unstuffing sind in Hardware-Implementierungen selten, aber in Software häufig, besonders wenn Entwickler gestuffed Bits mit Nutzlast verwechseln.