Interleaving

Der Begriff Verschränkung, Versatz oder englisch Interleaving (engl. to interleave „verschachteln, überlappen“) bezeichnet den Prozess, mehrere linear durchzählbare Objekte in einer speziellen Reihenfolge anzuordnen.

Verwendet wird Interleaving heute hauptsächlich bei der Datenkommunikation im Funk (zum Beispiel auf Satellitenstrecken), oder auch bei der ADSL-Technik im Internet. Früher war Interleaving auch bei der Anordnung von Blöcken auf Festplatten von Bedeutung.

Bit Interleaving für mehrdimensionale Datenstrukturen: siehe Z-Kurve.

Interleaving bei Disketten und Festplatten

links: nicht interleaved; rechts: interleaved mit Faktor 2

Die Technik des Interleaving wurde früher bei Festplatten angewendet, da sich die Platten zum Aufbau des notwendigen Luftpolsters zwischen Platte und Kopf schneller drehen mussten, als die gelesenen Daten verarbeitet werden konnten.

Bis ein Datenblock komplett übertragen war, waren schon weitere Blöcke unter dem Schreib-Lesekopf hinweggerauscht. Hätte man die Blöcke einfach in aufsteigender Reihenfolge von 1 bis n auf die Platten geschrieben, so müsste man nun nach dem Zugriff eines Blocks immer fast eine komplette Umdrehung warten, bis der nachfolgende Block wieder unter dem SL-Kopf erscheint. Da dies den Datendurchsatz extrem verlangsamen würde, hat man die Sektoren in einer anderen Reihenfolge beschrieben. Dabei wird mit dem so genannten Interleave-Faktor angegeben, wie viele Umdrehungen der Plattenstapel ausführen muss, um eine einzelne Datenspur einzulesen. Bei 8 Blöcken und einem Interleave-Faktor von 3 würden die Blöcke beispielsweise in der Reihenfolge 1 4 7 2 5 8 3 6 gespeichert, es liegen zwischen zwei logisch aufeinanderfolgenden Sektoren also stets zwei andere Blöcke. Dies gibt dem Festplattencontroller genug Zeit, die Daten eines Blockes zum Hauptspeicher zu übertragen bzw. die neuen Daten zu holen. Es benötigt drei Umdrehungen des Plattenstapels, bis die gesamte Datenspur eingelesen bzw. beschrieben ist.

Heute wird bei Festplatten ausschließlich der Interleave-Faktor 1 verwendet, das heißt, es findet kein Interleaving mehr statt. Die Festplattencontroller besitzen genug Pufferspeicher, um eine ganze Datenspur auf einmal zu lesen oder zu schreiben. Außerdem wird so genanntes "Double Buffering" verwendet, das heißt, während der Inhalt eines Pufferspeichers gerade zum Hauptspeicher übertragen wird, kann der andere Puffer mit Daten von der Festplatte gefüllt werden.

Interleaving beim Arbeitsspeicherzugriff

Beim Speicher-Interleave oder Speicherverschränkung werden abwechselnd zwei oder mehr Speicherbänke angesprochen. Allerdings ist darauf zu achten, dass die Speicher identischer Bauart sind. Bei Grafikkarten ist dies üblich. Dort wird das Problem gelöst, dass der Monitor lesend und das System schreibend zur gleichen Zeit auf die Daten im Speicher zugreifen müssen. Während der Monitor Bank 1 liest, schreibt zur gleichen Zeit das System auf Bank 2. Im nächsten Taktzyklus wird gewechselt.

Interleaving in der Datenübertragung

Heute wird das Interleaving in der digitalen Datenübertragung hauptsächlich deshalb angewendet, um die Datenübertragung vor sog. Burstfehlern abzusichern. Dabei macht man sich die Eigenschaft dieser Fehler zunutze, dass sie zwar, wenn sie auftreten, eine größere Anzahl zusammenhängender Bits zerstören, dafür aber relativ selten sind. Zu allen Daten werden (unabhängig vom Interleaving) zusätzliche Fehlerkorrekturinformationen mitübertragen, mit denen man Einzelbitfehler korrigieren kann. Tritt nun ein Burstfehler auf, ist aber nicht nur ein Bit sondern z.B. eine Gruppe von 10 Bits verändert. Diese Menge kann nicht mehr korrigiert werden. Durch das Interleaving macht man jetzt aus diesem Burstfehler künstlich eine größere Menge von Einzelbitfehlern, indem die zu übertragenden Daten bitweise in die Länge gezogen werden. Dafür werden mehrere unabhängige Daten parallel übertragen. Soll beispielsweise ein Datenpaket mit der Länge 512 Bit übertragen werden (inkl. Fehlerkorrekturdaten), so könnten diese zum Beispiel in 16 32 Bit-Gruppen geteilt werden. Nun wird nicht die erste Gruppe zuerst vollständig, und dann die zweite usw. übertragen, sondern es werden zuerst die ersten Bits aus allen Gruppen übertragen, dann alle zweiten Bits und so weiter. Fallen nun 10 zusammenhängende Bits aus, so fallen in 10 der 16 Datenpaketen je ein Bit aus, die aber rekonstruierbar sind, da alle übrigen 31 Bits in den Gruppen mit Fehler unverändert geblieben sind.

Der Sender muss die Daten erst in diese verschachtelte Form bringen. Dazu müssen aber alle Daten, die ineinander verschachtelt werden sollen, vorliegen. Im Beispiel von oben kann man das 16. Bit erst dann senden, wenn der Datenblock vollständig im Sendepuffer angekommen ist. Entsprechend kann der Empfänger die Daten erst dann wieder in die richtige Reihenfolge bringen, wenn das Paket komplett angekommen ist. Da dies insgesamt nur doppelt so lange verzögert, wie das Senden bzw. Empfangen des Datenpakets dauert, ist dieser Nachteil für die meisten praktischen Situationen irrelevant. Wo es allerdings auf geringe Latenzen ankommt, kann sich Interleaving als enormer Nachteil herausstellen.

Ein bekanntes Beispiel für diese Art der Kodierung wird bei der CD benutzt. Kratzer auf der CD-Oberfläche verursachen Burstfehler, die durch Interleaving zu korrigieren sind. Für diesen sog. Cross Interleaved Reed Solomon Code (CIRC) siehe Compact Disc im Artikel „Fehlerkorrektur“.

Es sei ein Datenblock mit dem Inhalt aaaabbbbccccddddeeeeffffgggg gegeben. Zuerst die Übertragung ohne Interleaving:

Fehlerfreie Übertragung:                            aaaabbbbccccddddeeeeffffgggg
Übertragung mit einem Burstfehler:                  aaaabbbbccc____deeeeffffgggg

Nun die gleichen Daten mit Interleaving:

Fehlerfreie Übertragung:                            abcdefgabcdefgabcdefgabcdefg
Übertragung mit einem Burstfehler:                  abcdefgabcd____bcdefgabcdefg

De-Interleavte Übertragung mit einem Burstfehler:   aa_abbbbccccdddde_eef_ffg_gg

Jetzt fehlen zwar von a, e, f und g je ein Bit, aber das kann korrigiert werden, weil jeweils nur ein Bit und nicht die ganzen Sequenzen cccc und dddd verloren sind.

Beim Codieren des Interleavings muss auf das erste g gewartet werden, bevor der erste 7er Zyklus abgeschlossen werden kann:

Original:            aaaabbbbccccddddeeeeffffgggg
                     ^   ^   ^   ^   ^   ^   ^

Die hier markierten Zeichen sind die ersten, die gesendet werden müssen. Das g kann aber nicht gesendet werden, bevor es beim Encoder angekommen ist. Analog beim Decodieren:

Interleaved        : abcdefgabcdefgabcdefgabcdefg
                     ^      ^      ^      ^

Bis aaaa komplett dekodiert werden kann, muss man bis zum letzten marktierten "a" warten, weil die Information vorher ja noch nicht komplett übertragen wurde.

Das Interleavingverfahren ist sehr verwandt mit dem Multiplexverfahren. Der Hauptunterschied besteht darin, dass das Multiplexverfahren Daten mehrerer Datenquellen meist zur Kostenersparnis über eine Leitung überträgt, während beim Interleaving nur logische Dateneinheiten derselben Datenquelle ansonsten in gleicher Weise wie beim Multiplexing verschachtelt über die Leitung transportiert werden.

Siehe auch graphische Darstellung von Interleaving

Vorteile durch das Interleaving

• Die Kommunikation wird gegen seltene Burstfehler abgesichert.
  • Daher kann der Bitfehlerschutz auf wenige Bits reduziert werden, da sich Burstfehler bei einem interleavten Datenstrom nur gering auf die Nutzdaten auswirken (s. o.). Auf diese Weise wird die Redundanz reduziert (je mehr Bitfehler ein Code korrigieren können soll, desto mehr redundante Stellen müssen eingefügt werden, vgl. Hamming-Abstand).
• Es müssen für diese Sicherung keine zusätzlichen Daten übertragen werden, die Datenrate bleibt also erhalten.

Nachteile durch das Interleaving

• Die Latenz erhöht sich.
• Beim Dekodieren wird ein ausreichend großer Puffer benötigt.

Latenzkritische Anwendungen

Vor allem Echtzeitsysteme werden durch das Interleaving negativ beeinflusst, da sich Reaktionszeiten zusätzlich zu anderen Faktoren nun auch noch durch das Interleaving verlängern. Dies spüren vor allem Online-Spieler in actionlastigen Spielen, da bei der ADSL-Technik für die Übertragung zwischen dem DSLAM und dem Modem des Benutzers normalerweise ein Interleaving stattfindet. Dieses Interleaving kann der Internet Service Provider auf Wunsch des Kunden für diesen abschalten, diese Option nennt sich i. A. FastPath. Dadurch treten zwar häufiger Paketverluste auf, dafür kommen die, die durchkommen, umso schneller an. Bei Dateidownloads können sich die Vor- und Nachteile in etwa gegenseitig aufheben, da durch die geringere Latenz angekommene Datenpakete einer TCP-Verbindung bereits früher bestätigt werden können, allerdings wird dieser Vorteil durch die geringfügig höhere Paketverlustrate mehr als ausgeglichen.