Interleaving

Verschränkung, Versatz oder englisch Interleaving (von englisch to interleave ‚verschachteln‘, ‚überlappen‘) ist eine Optimierungstechnik bei der Datenübertragung oder -speicherung. Dabei werden die Daten in einer bestimmten Reihenfolge angeordnet, um einen höheren Durchsatz zu erreichen.

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

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

Interleaving in der Datenübertragung

Heute wird das Interleaving in der digitalen Datenübertragung hauptsächlich angewendet, um die Datenübertragung vor Burstfehlern zu sichern. 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 Fehlerkorrektur-Informationen mitübertragen, mit denen man einzelne Bitfehler korrigieren kann.

Tritt nun ein Burstfehler auf, so ist nicht nur ein Bit verändert, sondern eine Gruppe von zum Beispiel zehn Bits. Diese Menge kann nicht mehr korrigiert werden. Durch das Interleaving macht man 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önnte dieses zum Beispiel in 16 Gruppen à 32 Bit geteilt werden. Nun wird nicht zuerst die erste Gruppe vollständig übertragen, dann die zweite usw., sondern es werden zuerst die ersten Bits aus allen Gruppen übertragen, dann alle zweiten Bits usw. Fallen nun zehn zusammenhängende Bits aus, so fällt in 10 der 16 Datenpakete je ein Bit aus, die aber alle rekonstruierbar sind, da jeweils die ü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 alle Daten vorliegen, die ineinander verschachtelt werden sollen. 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 das 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. Wenn 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 Cross Interleaved Reed Solomon Code (CIRC) siehe Compact Disc im Artikel „Fehlerkorrektur“.

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

Beispiel

Gegeben sei ein Datenblock mit dem Inhalt aaaabbbbccccddddeeeeffffgggg.

Zuerst die Übertragung ohne Interleaving:

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

Nun die gleichen Daten mit Interleaving (Burstfehler an gleicher Stelle im Sendeverlauf):

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 Interleaving 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 markierten „a“ warten, weil die Information vorher ja noch nicht komplett übertragen wurde.

Vorteile

• 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 (siehe oben). 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).
• Für diese Sicherung müssen keine zusätzlichen Daten übertragen werden, die Datenübertragungsrate bleibt erhalten.

Nachteile

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

Latenzkritische Anwendungen

Vor allem Echtzeitsysteme werden durch Interleaving negativ beeinflusst, da es die Reaktionszeiten verlängert. Das wirkt sich zum Beispiel in der ADSL-Technik bei actionlastigen Onlinespielen aus, da für die Übertragung zwischen dem DSLAM und dem Modem des Benutzers normalerweise Interleaving verwendet wird. Auf Wunsch eines Kunden kann der Internet-Provider das Interleaving für diesen abschalten, diese Option nennt sich im Allgemeinen 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: durch die geringere Latenz angekommene Datenpakete einer TCP-Verbindung können bereits früher bestätigt werden, allerdings besteht eine geringfügig höhere Paketverlustrate.

Interleaving bei Disketten und Festplatten

Links: nicht interleaved; rechts: interleaved mit Faktor 2

Die Technik des Interleaving wurde früher bei Festplatten und Disketten angewendet, da sich die Platten zum Aufbau des notwendigen Luftpolsters zwischen Platte und Kopf schneller drehen mussten, als die gelesenen Daten verarbeitet werden konnten. Denn noch vor der kompletten Übertragung eines Datenblocks waren schon weitere Blöcke unter dem Schreib-Lese-Kopf hinweggerauscht. Hätte man die Blöcke einfach in aufsteigender Reihenfolge von 1 bis n auf die Platten geschrieben, so müsste man nach dem Zugriff eines Blocks immer fast eine komplette Umdrehung warten, bis der nachfolgende Block wieder unter dem SL-Kopf erscheint. Da das den Datendurchsatz extrem verlangsamen würde, hat man die Sektoren in einer anderen Reihenfolge beschrieben. Dabei wird mit dem 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 zum Beispiel in der Reihenfolge 1 4 7 2 5 8 3 6 gespeichert, zwischen zwei logisch aufeinanderfolgenden Sektoren liegen also stets zwei andere Blöcke. Das 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 Double Buffering verwendet, das heißt, während der Inhalt des einen Pufferspeichers gerade zum Hauptspeicher übertragen wird, kann der andere Puffer mit Daten von der Festplatte gefüllt werden.

Für das sehr schnelle Speichern von Daten auf DDR-Controllern wird das Interleave-Verfahren verwendet, um die Antwortdichte des Gesamtsystems zu erhöhen. Dabei werden mehrere Controller parallel gefragt und die rückgewonnenen Daten wieder zu einem seriellen Datenstrom zusammengefasst. Beispielsweise können gerade und ungerade Datenworte auf 2 Speicher verteilt werden.