Lauflängencodierung ist ein Komprimierungsverfahren. Dieser Artikel beschreibt den einfachsten Fall von Lauflängencodierung, der Codierung binäre Signale, also zB. Nullen und Einsen.

Das Prinzip

In Folgen binärer Signale treten häufig lange Wiederholungen einzelner Bits auf. Diese Wiederholungen nennt man Läufe.

Beispiel 1:

011111011111111101111110011110

In Beispiel 1 treten lange Läufe von Einsen auf. Das Signale kann codiert werden, indem man statt aller Bits nur die Anzahl der Einsen schreibt. Beispiel 2 zeigt die Codierung des Signals, also die Lauflängen der Einsen, aus Beispiel 1 in dezimalen Zahlen.

Beispiel 2:

5 9 6 0 4

Die Null in Beispiel 2 sagt aus, dass sich hinter der vierten Null in Beispiel 1 keine Eins befindet.

Codierung der Lauflängen

Nun können wir in aller Regel leider kein dezimalen Zahlen, wie in Beispiel 2, darstellen, sondern müssen diese Zahlen wieder in binärer Schreibweise darstellen. Hierbei stellt sich nun die Frage, mit wievielen Bits wir die dezimalen Zahlen darstellen, damit wir auch hierbei möglichst wenig Speicherplatz verbrauchen. Man könnte 4 Bits zur Codierung der dezimalen Zahlen verwenden, weil die 9 nur mit vier oder mehr Bits codiert werden kann. Dadurch würde man aber bei den anderen Zahlen viel Speicherplatz verschwenden, weil hierbei weniger Bits zur Codierung nötig sind, aber immer vier Bits benutzt werden. Wenn man beispielsweise nur 3 Bits verwenden würde, würde diese Codierung für alle Zahlen, außer der 9 ausreichen. Die 9 kann man dann durch 2 Zahlen codieren, und zwar folgendermaßen.

5 => 101
9 => 111 001
6 => 110
0 => 000
4 => 100

Einsparung von Daten

Jetzt benötigen wir vier mal 3 Bits und, für die 9, zweimal 3 Bits, zusammen sind das 18 Bits. Das uncodierte Signal besteht aus 30 Bits. Wir haben das Signal um den Faktor 18/30 = 0,6 komprimiert.

101 | 111 | 001 | 110 | 000 | 100

Auffüllen mit einem 000-Codeblock

Es kann auch noch passieren, dass wir die Zahl 7 codieren müssen. Die 7 würde, genau wie der erste Codeblock der 9, auch mit drei Einsen codiert werden. Das bedeutet aber bei der Lauflängencodierung, dass der folgende Block noch die selbe dezimale Zahl codiert und zu dem Block, der aus drei Einsen besteht, hinzu addiert werden muss. Wir können deshalb nach dem Codeblock einer 7 nicht direkt mit dem Codeblock der nächsten Zahl fortfahren sondern müssen einen Codeblock, der komplett aus Nullen besteht, einfügen.

7 => 111 000 

Wenn also eine Zahl so komprimiert wird, dass der Codeblock, der sie darstellt, komplett aus Einsen besteht, muss nach diesem Codeblock ein zusätzlicher Codeblock, der nur aus Nullen besteht, eingefügt werden.

Verbesserung möglich?

Vielleicht geht es aber noch besser. Versuchen wir doch mal mit einer Codierung mit nur zwei Bits.

5 => 11 10
9 => 11 11 11 00
6 => 11 11 00
0 => 00
4 => 11 01

Man kann hier gut sehen, dass eine Zahl auch aus noch mehr als zwei Codeblöcken dargestellt werden kann. Die 6 wird hier beispielsweise als 3 + 3 + 0 dargestellt.

Die Codierung besteht aus 24 Bits⇒ Komprimierungsgrad = 0,8. Das ist zwar keine Verbesserung im Gegensatz zur vorherigen Codierung. Es sei an dieser Stelle aber nochmals darauf hingewiesen, dass das uncodierte Signal 30 Bits kostete. Also ist selbst die Codierung mit zwei Bits, die auf den ersten Blick einen etwas wirren Anschein macht, immer noch ressourcensparender als die uncodierte Version.

Codierung mit 4 Bits

5 => 0101
9 => 1001
6 => 0110
0 => 0000
4 => 0100

20 Bits ⇒ Komprimierungsgrad = 2/3, auch deutlich besser als das uncodierte Signal, aber nicht optimal.