28
Studienarbeit Heiko Hund Juni 2003 Fachbereich Informatik Fachhochschule Karlsruhe Arithmetische Kodierung

Arithmetische Kodierung - heiko.exit0.netheiko.exit0.net/ArithCode.pdf · ner Nachricht besser möglich ist als mit Verfahren, wie beispielsweise der Huffman-Kodierung, ... Kode zugewiesen

Embed Size (px)

Citation preview

Page 1: Arithmetische Kodierung - heiko.exit0.netheiko.exit0.net/ArithCode.pdf · ner Nachricht besser möglich ist als mit Verfahren, wie beispielsweise der Huffman-Kodierung, ... Kode zugewiesen

Studienarbeit Heiko Hund

Juni 2003

Fachbereich Informatik Fachhochschule Karlsruhe

Arithmetische Kodierung

Page 2: Arithmetische Kodierung - heiko.exit0.netheiko.exit0.net/ArithCode.pdf · ner Nachricht besser möglich ist als mit Verfahren, wie beispielsweise der Huffman-Kodierung, ... Kode zugewiesen

Inhaltsverzeichnis

Heiko Hund 2

Inhaltsverzeichnis

Inhaltsverzeichnis ........................................................................................................................... 2

1 Einführung............................................................................................................................. 3

2 Grundlagen ............................................................................................................................ 4 2.1 Alphabet, Symbol, Sequenz ................................................................................................ 4 2.2 Wahrscheinlichkeit ............................................................................................................... 4 2.3 Modell..................................................................................................................................... 4 2.4 Entropie ................................................................................................................................. 5

3 Arithmetische Kodierung.................................................................................................... 6 3.1 Kodierung .............................................................................................................................. 6 3.2 Dekodierung.......................................................................................................................... 7 3.3 Beispiel ................................................................................................................................... 8

4 Festkomma Implementierung .......................................................................................... 12 4.1 Kodierung ............................................................................................................................ 12 4.2 Dekodierung........................................................................................................................ 18 4.3 Beispiel ................................................................................................................................. 19

5 Das Programm ArithCode................................................................................................ 24

Abbildungsverzeichnis................................................................................................................. 28

Tabellenverzeichnis ...................................................................................................................... 28

Literaturverzeichnis ...................................................................................................................... 28

Page 3: Arithmetische Kodierung - heiko.exit0.netheiko.exit0.net/ArithCode.pdf · ner Nachricht besser möglich ist als mit Verfahren, wie beispielsweise der Huffman-Kodierung, ... Kode zugewiesen

Kapitel 1 - Einführung

Heiko Hund 3

1 Einführung

Die vorliegende Arbeit befasst sich mit der Arithmetischen Kodierung, einem Verfah-ren zur verlustfreien Datenkompression. Verlustfreie Datenkompression wird immer dann eingesetzt, wenn der Umfang von Daten zur Speicherung oder Übertragung verrin-gert werden soll, die darin enthaltene Information jedoch vollständig erhalten werden soll. Im Gegensatz dazu stehen die verlustbehafteten Kompressionsverfahren, die sich im Allgemeinen Schwächen der menschlichen Wahrnehmungsorgane zu Nutze machen um Audio und Video Signale zu komprimieren. Die Teile der Daten, die für den Menschen nicht wahrnehmbar sind werden dabei entfernt, was zum Effekt hat, dass die Datenmen-ge geringer wird. Meist arbeiten verlustbehaftete Verfahren jedoch hybrid, so dass nach einer solchen Kompression eine weitere verlustfreie stattfindet, mit der der Umfang der Daten nochmals verringert wird.

Erste Ansätze der Arithmetischen Kodierung wurden bereits in den Frühen 60er Jah-ren von Elias und Abramson vorgestellt, jedoch dauerte es bis in die später 80er Jahre, bis ein für Digitalrechner geeigneter Algorithmus veröffentlicht wurde [4]. Der Grund dafür lag jedoch nicht an der Komplexität des Verfahrens, sondern darin, dass in Digital-rechnern die arithmetische Genauigkeit beim Rechnen mit reellen Zahlen begrenzt ist. Dies wird im Kapitel 3 nochmals aufgegriffen und genauer betrachtet werden, wenn die Idee der Arithmetischen Kodierung besprochen wird.

Die Arithmetische Kodierung erreicht im Allgemeinen einen höheren Kompressions-faktor als andere bekannte Verfahren zur Entropiekodierung. Diesen Vorteil verschafft sich die Arithmetische Kodierung dadurch, dass sie nicht einzelnen Zeichen Kodes zu-weist, sondern die Nachricht als Ganzes kodiert. Dadurch wird es möglich, dass ein Symbol, über die gesamte Nachricht betrachtet, mit einer gebrochenen Anzahl von Bits kodiert werden kann, was eine bessere Annäherung an die tatsächliche Entropie einer Nachricht ermöglicht.

Die vorliegende Arbeit hatte zum Ziel ein Programm zu erstellen, welches die Arithme-tische Kodierung implementiert. Dieses Programm wird vorgestellt, nach dem auf die Grundlagen der Arithmetischen Kodierung, sowie eines daraus abgeleiteten Algorithmus der ausschließlich Integeroperationen verwendet [4] eingegangen wurde. Die Informatio-nen für diese Ausarbeitung stammen größtenteils aus [1] und [3].

Page 4: Arithmetische Kodierung - heiko.exit0.netheiko.exit0.net/ArithCode.pdf · ner Nachricht besser möglich ist als mit Verfahren, wie beispielsweise der Huffman-Kodierung, ... Kode zugewiesen

Kapitel 2 - Grundlagen

Heiko Hund 4

2 Grundlagen

Vor der Vorstellung des eigentlichen Verfahrens zur Arithmetischen Kodierung, sollen hier noch einige grundlegende Begriffe aus dem Gebiet der Datenkompression erläutert werden. Sie sind zum Verständnis der darauf folgenden Erläuterungen von Nutzen.

2.1 Alphabet, Symbol, Sequenz

Ein Alphabet A ist eine nichtleere, endliche Menge von Symbolen a. Notiert wird eine Solche Menge als A = {a1, a2, …,am}. Die Anordnung der Symbole in dieser Menge ist festgelegt, so dass einer Position in einem Alphabet bijektiv ein Symbol zugeordnet wird. Ein Beispiel für ein im Computerbereich verwendetes Alphabet ist der UNICODE Zei-chensatz.

Eine Sequenz S ist eine festgelegte Folge von Symbolen aus einem Alphabet. Notiert wird eine Sequenz als S = {s1, s2, …, sn}. |S| bezeichnet die Länge der Sequenz in Sym-bolen. Ein Symbol kann innerhalb einer Sequenz mehrmals an verschiedenen Positionen vorkommen. Es kann aber auch gar nicht vorkommen. So könnte zum Beispiel dieser Text als Sequenz von Symbolen aus dem Alphabet von Satzzeichen und deutschen Buch-staben aufgefasst werden.

2.2 Wahrscheinlichkeit

Die Wahrscheinlichkeit eines Symbols innerhalb einer Sequenz p(ai) ergibt sich aus der Anzahl dieses Symbols innerhalb der Sequenz |S|ai im Bezug auf die Länge der Se-quenz n. In einer Formel ausgedrückt formuliert sich das wie folgt.

nS

ap iai

||)( = (1)

Man erkennt, dass die resultierende Wahrscheinlichkeit im halboffenen Intervall [0;1) liegt. Eine Wahrscheinlichkeit von 1 für ein Symbol kann deshalb ausgeschlossen werden, da die Kodierung einer Sequenz aus dem gleichen Zeichen offensichtlich unnötig ist, da ihr Inhalt schon bekannt ist. Die kumulative Wahrscheinlichkeit einer Sequenz sind die aufsummierten Wahrscheinlichkeiten der einzelnen Symbole in ihr und ist immer 1.

2.3 Modell

Ein Modell dient dazu einem Symbol ai einen Wahrscheinlichkeitswert zuzuordnen. Dies ist sinnvoll, da die Wahrscheinlichkeiten unter verschiedenen Randbedingungen auch verschieden ausgeprägt sein werden. So werden Texte in verschiedenen Sprachen

Page 5: Arithmetische Kodierung - heiko.exit0.netheiko.exit0.net/ArithCode.pdf · ner Nachricht besser möglich ist als mit Verfahren, wie beispielsweise der Huffman-Kodierung, ... Kode zugewiesen

Kapitel 2 - Grundlagen

Heiko Hund 5

genau so eine unterschiedliche Häufigkeitsverteilung aufweisen, wie Texte die für unter-schiedliche Zielgruppen verfasst wurden. Durch ein Modell lässt sich solch eine Häufig-keitsverteilung für eine bestimmte Anwendung definieren, ohne dass die tatsächlichen Wahrscheinlichkeiten bekannt sein müssen. Des weiteren ermöglicht ein Modell eine De-finition von Wahrscheinlichkeiten für Teilsequenzen bestehend aus verschiedenen Sym-bolen (sogenannten N-Grammen). Dadurch kann die Kodierungseffizienz erhöht wer-den, da so größere Blöcke der vorliegenden Daten mit einem Kode beschrieben werden können.

2.4 Entropie

Die Entropie als Begriff in der Informationstheorie wurde von Claude Shannon ge-prägt [5]. Sie beschreibt die minimale Anzahl von Bits, die pro Symbol notwendig sind um eine Information zu übertragen. Sie wird wie folgt definiert:

∑∈

⋅=Aa iM

iM apapSH

)(1log)()( 2 (2)

Aus der Formel wird ersichtlich, dass die Entropie abhängig vom Modell M ist. Mit dem Logarithmus Dualis wird berechnet, wie viele Bits nötig sind, um ein Symbol ai zu kodieren, welches mit der modellierten Wahrscheinlichkeit pM(ai) in der zu kodierenden Sequenz S auftritt. Diese Zahl wird dann nochmals mit der realen (gemessenen) Wahr-scheinlichkeit multipliziert. Die Entropie ist am geringsten, wenn die Modellwahrschein-lichkeit pM(ai) gleich der tatsächlichen Wahrscheinlichkeit p(ai) ist. Um effizient kodieren zu können ist es also nötig, sein Modell möglichst an der tatsächlichen Verhältnissen zu orientieren. Wählt man ein suboptimales Modell zur Kompression einer Sequenz, ist es sogar möglich, dass diese sich nach der Kompression vergrößert hat. Trotz dieser Tatsa-che: soll eine Sequenz S verlustfrei komprimiert werden, stellt die Entropie H(S) die un-tere Schranke der Kompression dar. Das heißt man benötigt immer mindestens |S|·H(S) Bits um sie zu kodieren.

Page 6: Arithmetische Kodierung - heiko.exit0.netheiko.exit0.net/ArithCode.pdf · ner Nachricht besser möglich ist als mit Verfahren, wie beispielsweise der Huffman-Kodierung, ... Kode zugewiesen

Kapitel 3 - Arithmetische Kodierung

Heiko Hund 6

3 Arithmetische Kodierung

Wie schon erwähnt ist die Arithmetische Kodierung ein Verfahren, bei dem nicht den einzelnen Symbolen einer Nachricht Kodewörter zugeordnet werden, sondern der gan-zen Nachricht. Dadurch ist es unter anderem möglich Symbole mit weniger als einem Bit zu kodieren. Im Allgemeinen kann man sagen, dass die Annäherung an die Entropie ei-ner Nachricht besser möglich ist als mit Verfahren, wie beispielsweise der Huffman-Kodierung, die nur Kodes aus ganzen Bits produzieren.

3.1 Kodierung

Anhand des Beispielalphabets A = {a, b, c, d} mit den Wahrscheinlichkeiten PM = {0,4; 0,2; 0,1; 0,3} soll die Funktionsweise der Arithmetische Kodierung erläutert werden. Aus Kapitel 2.2 ist bekannt, dass die einzelnen Wahrscheinlichkeiten im Intervall [0;1) liegen. Weiterhin ist bekannt, dass zwischen zwei beliebigen reellen Zahlen aus die-sem Intervall unendlich viele Zahlen liegen. Das Intervall [0;1) wird nun entsprechend den Wahrscheinlichkeiten in Teilintervalle untergliedert. In Abbildung 1 kann man sehen, wie das Intervall für die hier gewählten Wahrscheinlichkeiten aussieht.

a b c d0,0 0,4 0,6 0,7 1,0

Abbildung 1: Unterteilung des Startintervalls beim einem gegebenen Modell PM

Ebenso kann man erkennen, dass sich die Grenzen für ein Teilintervall aus den kumulier-ten Wahrscheinlichkeiten ergeben. Für die Berechnung der kumulierten Wahrscheinlich-keit für das k-te Symbol im Alphabet wird die Formel

∑=

=k

iiMkK apap

1)()( (3)

eingeführt. Daraus ergibt sich, dass pK(0) = 0,0 und pK(i+1) = pK(i) + p(i) gilt. Die obere und untere Grenze des Gesamtintervalls soll zu dem, ab sofort mit low beziehungsweise high bezeichnet werden. Zusammenfassend ergeben sich für das aktuelle Intervall also die Werte die in Tabelle 1 aufgeführt sind.

high 1,0 low 0,0

pK(a0) 0,0 pK(a1) 0,4

pK(a2) 0,6 pK(a3) 0,7

Tabelle 1: Kumulierte Häufigkeiten und Intervallgrenzen beim Modell PM

Page 7: Arithmetische Kodierung - heiko.exit0.netheiko.exit0.net/ArithCode.pdf · ner Nachricht besser möglich ist als mit Verfahren, wie beispielsweise der Huffman-Kodierung, ... Kode zugewiesen

Kapitel 3 - Arithmetische Kodierung

Heiko Hund 7

All diese Werte werden benötigt um einen Nachricht zu komprimieren. Das Prinzip der Arithmetischen Kodierung ist es nämlich, das Intervall mit jedem Symbol immer wei-ter zu verkleinern. Die neuen oberen und unteren Grenzen des Intervalls (low und high) werden dabei von der oberen und unteren Grenze des Teilintervalls des aktuell kodierten Symbols (pK(i-1) und pK(i)) bestimmt. Um dieses neue Intervall zu berechnen werden die Formeln

)()(' 1 lowhighaplowlow iK −⋅+= − (4)

)()(' lowhighaplowhigh iK −⋅+= (5)

eingeführt. Mit ihnen ist es möglich, unter Berücksichtigung der aktuellen Intervallgren-zen und des zu kodierenden Symbols ai die neuen Grenzen für das Gesamtintervall zu bestimmen. Sie mögen auf den ersten Blick vielleicht etwas komplex wirken, spätestens nachdem ihre Anwendung an einem konkreten Beispiel gezeigt wird, wird klar werden was sie bewirken.

Der eigentliche Kode einer Nachricht ist nun irgendeine Zahl aus dem Intervall, das nach Bearbeitung des letzten Symbols in der Nachricht festgelegt wurde. Deshalb spricht man bei der Arithmetischen Kodierung auch davon, dass der gesamten Nachricht ein Kode zugewiesen wird und nicht einzelnen Symbolen. Man kann sich vorstellen, dass beim Kodieren von langen Nachrichten diese Zahl relativ viele Nachkommastellen haben wird, da sich ja das Intervall mit jedem kodierten Symbol verkleinert.

Zur Übertragung bildet man das Zweierkomplement dieser reellen Zahl und erhält so einen Bitstring. Am besten man wählt also eine Zahl aus dem Intervall, die sich durch eine Zweierpotenz beschreiben lässt, um den Kode nicht unnötig lang werden zu lassen.

Wie bereits erwähnt gibt es jedoch einen Haken an diesem Verfahren, so dass es sich nicht ohne weiteres Implementieren lässt. Durch die Tatsache, dass die Intervallgrenzen immer weiter zusammenrücken, wird eine immer höhere Präzision der Rechenoperatio-nen notwendig. Die Fließkomma-Operationen in einem heutigen Rechner sind jedoch nur von beschränkter Genauigkeit, was bedeutet, dass man früher oder später an die Grenzen der Berechenbarkeit eines Intervalls stoßen wird. Ab diesem Punkt ist eine Ko-dierung dann nicht mehr machbar. Hinzu kommt, dass Fließkomma-Operationen ein Vielfaches der Ressourcen von Integer-Operationen beanspruchen. An eine Implemen-tierung für Digitalrechner ist also nicht zu denken. Dennoch soll hier auch noch der De-kodierungsvorgang besprochen werden. Eine Verwirklichung der Arithmetischen Kodie-rung die ausschließlich Integer-Operationen verwendet, wird in Kapitel 4 vorgestellt wer-den.

3.2 Dekodierung

Um eine mittels Arithmetischer Kodierung komprimierten Nachricht zu dekomprimie-ren, wird im Prinzip ähnlich vorgegangen. Lediglich die Voraussetzungen sind ein wenig

Page 8: Arithmetische Kodierung - heiko.exit0.netheiko.exit0.net/ArithCode.pdf · ner Nachricht besser möglich ist als mit Verfahren, wie beispielsweise der Huffman-Kodierung, ... Kode zugewiesen

Kapitel 3 - Arithmetische Kodierung

Heiko Hund 8

geändert, da man mit einer Zahl Z (dem Kode der Nachricht) und nicht mit einer Se-quenz beginnt.

Für die Dekodierung werden die kumulierten Wahrscheinlichkeiten der Symbole im Alphabet pK(ai) benötigt, da auch hier die Formeln (4) und (8) Anwendung finden. Man beginnt mit dem gleichen Intervall I = [0;1) wie bei der Kodierung und betrachtet, in wel-chen Teilintervall die Zahl Z hineinfällt. Anhand dieses Teilintervalls I’ = [pK(ai-1); pK(ai)) kann der Dekodierer dann das zugeordnete Symbol ai bestimmen. Danach werden unter Verwendung dieses Symbols und mittels der Formeln (4) und (8) die neuen Intervallgren-zen berechnet. Um das nächste Symbol der Nachricht zu bekommen, wird in dem neuen Intervall wieder das Teilintervall gesucht, in dem Z liegt. Die ganzen Schritte werden so-oft durchgeführt, bis man alle Zeichen der Nachricht extrahiert hat, also |S| mal.

Ein Problem gibt es bei der Dekodierung jedoch, auf das bisher nicht eingegangen wurde. Wird dem Dekodierer nicht die Länge der Nachricht mitgeteilt, so kann er prinzi-piell unendlich lange fortfahren zu dekodieren, da es ja immer wieder ein Teilintervall im aktuellen Intervall gefunden wird, in dem sich die Zahl Z befindet. Dies führt wiederum zu einem Symbol und neuen Werten für low und high, obwohl diese Symbole in der Se-quenz gar nicht vorhanden waren.

3.3 Beispiel

Um das Verfahren zu verdeutlichen soll hier noch eine kurze Sequenz aus dem Alpha-bet A arithmetisch kodiert und anschließend wieder dekodiert werden. Das Alphabet und die Wahrscheinlichkeiten der einzelnen Symbole sind bereits bekannt, bleibt also noch die Sequenz zu definieren als S = {a, d, b}, mit |S| = 3. Die Häufigkeit der Symbole entspricht dabei nicht den Wahrscheinlichkeiten aus dem Modell, was zur Folge haben wird, das der erstellte Kode sich nicht optimal an die Entropie der Nachricht nähert. Am Prinzip der Verarbeitung ändert die jedoch nichts.

Begonnen wird die Kodierung mit dem Intervall [0; 1) und dem ersten Symbol der Se-quenz. Da es sich dabei um ein ‚a’ handelt ergeben sich nach (4) und (8) folgende neuen Grenzen für das Intervall:

low’ = low + pK(ai-1) · (high – low) = 0 + 0 · 1 = 0

high’ = low + pK(ai) · (high – low) = 0 + 0,4 · 1 = 0,4

In dem neuen Intervall [0; 0,4) wird nun für das nächste Symbol ‚d’ das Teilintervall ge-sucht. Dazu werden wieder die Formeln zur Berechnung von low’ und high’ verwendet. Hier wird deutlich, dass sich das Teilintervall immer nur innerhalb des bestehenden In-tervalls befinden kann, da low’ nie kleiner als low sein kann und high’ nie größer als low + (high – low), also der unteren Grenze des aktuellen Intervalls plus seiner Breite

Page 9: Arithmetische Kodierung - heiko.exit0.netheiko.exit0.net/ArithCode.pdf · ner Nachricht besser möglich ist als mit Verfahren, wie beispielsweise der Huffman-Kodierung, ... Kode zugewiesen

Kapitel 3 - Arithmetische Kodierung

Heiko Hund 9

(high – low). Durch die Multiplikation der kumulierten Wahrscheinlichkeiten pK(ai), wird die Lage der oberen und unteren Grenze von ai auf das Intervall umgerechnet (siehe dazu auch Abbildung 2). Da per Definition die kumulierte Wahrscheinlichkeit pK(ai-1) immer kleiner als pK(ai) ist, ist auch immer erfüllt, dass low < high.

low’ = low + pK(ai-1) · (high – low) = 0 + 0,7 · 0,4 = 0,28

high’ = low + pK(ai) · (high – low) = 0 + 1 · 0,4 = 0,4

Nach der Kodierung von ‚d’ ist das Intervall nun [0,28; 0,4) und hat, nach nur zwei ko-dierten Symbolen, noch eine Breite von 0,12. Man kann sich vorstellen, dass es noch klei-ner wäre, hätte man ein Alphabet mit einer größeren Anzahl von Symbolen definiert. Die Wahrscheinlichkeiten der einzelnen Zeichen wären dann vermutlich geringer geworden und somit würden sich auch ihre Teilintervalle verkleinern. Nun soll auch noch das letzte Symbol der Nachricht kodiert werden, ein ‚b’.

low’ = low + pK(ai-1) · (high – low) = 0,28 + 0,4 · 0,12 = 0,328

high’ = low + pK(ai) · (high – low) = 0,28 + 0,6 · 0,12 = 0,352

Nachdem nun das Ende der Sequenz erreicht ist, steht auch das Intervall fest, in dem die Zahl Z liegen muss. Den Weg auf dem dieses Intervall gefunden wurde, stellt Abbildung 2 noch einmal bildlich dar. Für dieses Beispiel gilt also

0,328 ≤ Z < 0,352.

d

c

b

a

0,0

0,4

0,60,7

1,0

d

c

b

a

0,0

0,16

0,240,28

0,4

d

c

b

a

0,28

0,328

0,3520,364

0,4

Z

0,328

0,352

0,3376

0,34240,3448

Abbildung 2: Intervallbildung für die Sequenz {a, d, b}

Page 10: Arithmetische Kodierung - heiko.exit0.netheiko.exit0.net/ArithCode.pdf · ner Nachricht besser möglich ist als mit Verfahren, wie beispielsweise der Huffman-Kodierung, ... Kode zugewiesen

Kapitel 3 - Arithmetische Kodierung

Heiko Hund 10

Gesucht ist demnach eine Zahl, die in diesem Intervall liegt und sich mittels eines Zweierkomplements beschreiben lässt. Dazu sucht man einfach Bit für Bit, bis man eine solche Zahl gefunden hat.

Z = 0 · 2-1 + 1 · 2-2 + 0 · 2-3 + 1 · 2-4 + 1 · 2-5 = 0 · 0,5 + 1 · 0,25 + 0 · 0,125 + 1 · 0,0625 + 1 · 0,03125 = 0,34375

Die Nachricht kann also durch die Bitfolge 01011 beschrieben werden, was bedeutet dass pro Symbol 6,1 Bits zur Kodierung verwendet wurden. Die Entropie der Nachricht ist 58496,1)3(log2 ≈=H , eine Annäherung der Kodelänge an die Entropie ist also deut-lich zu erkennen. Das dies trotz des nicht angepassten Modells so ist, hat zum einen mit der Kürze der Nachricht und zum anderen damit zu tun, dass alle drei Symbole im Mo-dell „ungefähr“ eine Wahrscheinlichkeit von einem Drittel haben.

Wurde das Modell nicht schon im Vorfeld vereinbart, ist es notwendig, dem Dekodie-rer dieses zur Verfügung zu stellen. Mit dem Modell und der Bitfolge kann er nun die Nachricht wieder dekodieren. Er geht dabei genauso vor wie der Kodierer, nur dass er vor jeder Runde das Symbol anhand des aktuellen Intervalls und der Zahl Z bestimmt. Gestartet wird also ebenfalls mit dem Intervall [0; 1). Da

0,0 ≤ Z = 0,34375 < 0,4

liegt Z in ersten Teilintervall. Das erste Symbol der Nachricht muss demnach ein ‚a’ sein. Mit diesem Wissen wird das Intervall dann wiederum mittels (4) und (8) reskaliert.

low’ = low + pK(ai-1) · (high – low) = 0 + 0 · 1 = 0

high’ = low + pK(ai) · (high – low) = 0 + 0,4 · 1 = 0,4

Es werden also genau die selben Berechnungen wie auch schon bei der Kodierung der Nachricht verwendet, um sie Schritt für Schritt nachvollziehen zu können. Mit diesem neuen Intervall und den so bekannten neuen Teilintervallgrenzen (vgl. Abbildung 2) kann Z wieder einem Teilintervall zugeordnet werden. Das nächste Symbol ergibt sich dem-nach aus der Feststellung, dass

0,28 ≤ Z = 0,34375 < 0,4

und wird somit als ‚d’ identifiziert. Wiederum wird das Intervall reskaliert.

low’ = low + pK(ai-1) · (high – low) = 0 + 0,7 · 0,4 = 0,28

high’ = low + pK(ai) · (high – low) = 0 + 1 · 0,4 = 0,4

Page 11: Arithmetische Kodierung - heiko.exit0.netheiko.exit0.net/ArithCode.pdf · ner Nachricht besser möglich ist als mit Verfahren, wie beispielsweise der Huffman-Kodierung, ... Kode zugewiesen

Kapitel 3 - Arithmetische Kodierung

Heiko Hund 11

Um an das letzte Symbol der Nachricht zu gelangen, muss nun abermals das Teilinter-vall gefunden werden in dem Z liegt. In diesem Fall ist dies der Fall für

0,328 ≤ Z = 0,34375 < 0,352,

also dem Intervall, das dem ‚b’ zugeordnet ist. Betrachtet man noch einmal Abbildung 2, so wird klar warum es notwendig ist den Dekodierer von explizit zu terminieren. Ohne die Kenntnis der Länge der Sequenz oder einem vereinbarten Symbol, welches das Ende der Sequenz anzeigt, ist es dem Dekodierer nicht möglich festzustellen, wann diese kom-plett ist. Auch im resultierenden letzten Intervall gibt es nämlich wieder genau ein Teilin-tervall, in das die Zahl Z hinein passen würde. In diesem Fall würde dies das Intervall [0,3424; 0,3448), also ein ‚c’ sein. Aus der Tatsache, dass es unendlich viele Zahlen in je-dem Teilintervall gibt, lässt schließen, dass der Dekodierer nie an ein Ende kommen würde.

Page 12: Arithmetische Kodierung - heiko.exit0.netheiko.exit0.net/ArithCode.pdf · ner Nachricht besser möglich ist als mit Verfahren, wie beispielsweise der Huffman-Kodierung, ... Kode zugewiesen

Kapitel 4 - Festkomma-Implementierung

Heiko Hund 12

4 Festkomma-Implementierung

Wie bereits erwähnt, wurde eine effiziente Implementierung der Arithmetischen Ko-dierung erst viel später veröffentlicht, als die Idee selbst. Es dauerte bis 1987, bis Witten et al. [4] einen Algorithmus aufzeigten, mit dem die Arithmetische Kodierung nun auch auf kleineren Prozessoren effektiv implementiert werden konnte, da er lediglich Fest-komma-Operationen verwendete. Dieser Algorithmus war wesentlich einfacher zu imp-lementieren und ist meist auch immens schneller als der im vorigen Kapitel vorgestellte. Wie die Arithmetische Kodierung funktioniert, wenn nur Integer verwendet werden, soll in diesem Kapitel besprochen werden. Offensichtlich muss man nun davon ausgehen, dass nicht mehr unendlich viele Zahlen zur Kodierung zur Verfügung stehen, da ein end-liches Intervall in ù stets eine endliche Menge Zahlen beinhaltet.

4.1 Kodierung

Analog zum vorigen Algorithmus, muss auch bei der Festkomma-Implementierung ein Modell initialisiert werden. Da keine reellen Zahlen verwendet werden können, wird hier allerdings nicht mit Wahrscheinlichkeiten von Symbolen, sondern mit deren Häufigkeiten gearbeitet. Zum besseren Vergleich, wurden die Häufigkeiten entsprechend der Wahr-scheinlichkeiten in Kapitel 3.1 gewählt. Für eine Sequenz S mit |S| = 10, bestehend aus Symbolen des Alphabets A = {a, b, c, d}, wurden die Häufigkeiten also auf HM = {4, 2, 1, 3} festgelegt. Die kumulierten Häufigkeiten sind dem entsprechend HK = {0, 4, 6, 7, 10}. Die Anzahl der Symbole ist N = 4. Normiert man also die Häufig-keit eines Symbols mit der Summe aller Häufigkeiten hK(N), ergibt sich wieder die Wahr-scheinlichkeit dieses Symbols. Als Voraussetzung für den Algorithmus muss zudem gel-ten hM(s) ≥ 1, für alle s ∈ S, was für eine Sequenz in der nur Symbole aus A vorkommen somit erfüllt ist.

Die Größe des Intervalls wird über die Anzahl der zu verwendenden Bits B definiert, so dass die größte Zahl im Intervall M = 2B-1 ist. Das resultierende Intervall für die Ko-dierung ist also zunächst [0; M). Im Allgemeinen wählt man das Intervall – also B – so groß wie möglich, um die Teilintervallgrenzen, entsprechend den Häufigkeiten der Sym-bole, bestmöglich approximieren zu können. Hier soll die Implementierung für Prozesso-ren mit 32 Bit breiten Registern besprochen werden. Das größtmögliche B ist in diesem Fall 31. Warum das so ist wird später noch geklärt werden. Es kann also von einem M = 231-1 ausgegangen werden.

Wie auch bei der Fließkomma Variante des Algorithmus werden die untere und obere Grenze des Intervalls initialisiert mit

low = 0 und

high = M.

Page 13: Arithmetische Kodierung - heiko.exit0.netheiko.exit0.net/ArithCode.pdf · ner Nachricht besser möglich ist als mit Verfahren, wie beispielsweise der Huffman-Kodierung, ... Kode zugewiesen

Kapitel 4 - Festkomma-Implementierung

Heiko Hund 13

Zur Bestimmung der neuen Grenzen der Teilintervalle kommen die beiden Gleichun-gen (6) und (8) zum Einsatz. Ihre Ähnlichkeit mit (4) und (5) fällt sofort ins Auge. Das ist nicht weiter verwunderlich, denn sie sollen schließlich das Gleiche bewirken.

+−⋅+= − )(

1)(' 1 Nhlowhighahlowlow

KiK (6)

1)(

1)(' −

+−⋅+=

Nhlowhighahlowhigh

KiK (7)

Der einzige Unterschied ist die Anpassung auf die Berechnung mit Integern, in der Form, dass hier mit Häufigkeiten statt mit Wahrscheinlichkeiten gerechnet wird und des-halb auch eine Normierung mit der Summe aller Häufigkeiten hK(N) erfolgt. Statt jedoch die Häufigkeit des kodierten Symbols zu normieren, wird der aktuelle Intervallbereich dividiert. Der Grund dafür ist, dass eine Ganzzahl-Division immer abgerundet wird und so das Ergebnis der Division der Häufigkeit immer zum Ergebnis 0 haben würde. Zwar ist diese Umformung mathematisch vollkommen korrekt, wie man in den Formeln sieht wird aber natürlich auch das Ergebnis dieser Division abgerundet, was die Berechnung ungenau werden lässt. Diese Ungenauigkeit bewegt sich allerdings im Rahmen des Ver-tretbaren und wie später sehen wird, erreicht auch dieser Algorithmus eine gute Annähe-rung an die Entropie der kodierten Sequenz. Ein genaueres Ergebnis ließe sich erreichen, wenn man vor der Division zuerst die Multiplikation durchführen würde. Diese Vorge-hensweise ist in der Praxis jedoch nicht wirklich besser, da es durch die Multiplikation zu einem Register-Überlauf kommen kann, wenn die Breite des Intervalls (high – low + 1), beziehungsweise die Häufigkeit des kodierten Symbols hK(ai) groß sind.

Aus den beiden Formeln wird auch die Rahmenbedingung ersichtlich, dass die Breite des Intervalls nie kleiner als die Summe der Häufigkeiten hK(N) werden darf, da sonst einer der Faktoren zu 0 würde. Wie später deutlich werden wird, kann ein Intervall nie kleiner als Q1 werden, woraus sich die Bedingung hK(N) ≤ Q1 ergibt. Deshalb und auch um dem ständigen verkleinern der Intervalle entgegen zu wirken, werden drei Skalie-rungsfunktionen definiert. Sie vergrößern das Intervall bei drei unterschiedlichen Bedin-gungen auf verschiedene Arten. Diese drei Funktionen, E1, E2 und E3 genannt, sollen im Folgenden vorgestellt werden.

Für die Skalierungsfunktionen werden drei Hilfsvariablen eingeführt, die das Intervall vierteln. Sie werden entsprechend den Vierteln an deren Ende sie sich befinden als Q1 = M/4 + 1, Q2 = 2 · Q1 und Q3 = 3 · Q1 definiert.

Die Skalierungsfunktion E1 tritt immer dann in Kraft, wenn das mit (6) und (8) neu bestimmte Intervall komplett in der unteren Hälfte des aktuellen Intervalls liegt, also die Bedingung high < Q2 erfüllt ist. Da das neue Intervall in der unteren Hälfte liegt, das weiß man von der arithmetischen Kodierung mit reellen Zahlen, werden alle folgenden Teilin-tervalle ebenfalls in dieser Hälfte liegen. Mann kann also schon eine binäre ‚0’ in den Er-gebnis-Bitstrom schreiben, was die aus der Kodierung resultierende Binärzahl in der un-

Page 14: Arithmetische Kodierung - heiko.exit0.netheiko.exit0.net/ArithCode.pdf · ner Nachricht besser möglich ist als mit Verfahren, wie beispielsweise der Huffman-Kodierung, ... Kode zugewiesen

Kapitel 4 - Festkomma-Implementierung

Heiko Hund 14

teren Hälfte des Intervalls ansiedelt. Danach wird das Intervall vergrößert. Dieses neue Intervall stellt man sich am besten als die gezoomte Version des Intervalls vor. Die Gren-zen und die Breite gleichen vielleicht einem bereits vorangegangenen Intervall, in Wahr-heit befindet man sich aber nur in einem stark vergrößerten Teilintervall des Intervalls [0; M). Je öfter man Skaliert hat, umso kleiner ist dieses Intervall eigentlich, was sich auch dadurch ausdrückt, das die ausgegebene Zweierpotenz auf Grund der Position im Bit-string einen immer niedrigeren Wert hat. Möglich ist diese Skalierung und die damit ein-hergehende Überlappung der numerischen Grenzen, da hier, im Gegensatz zur Arithme-tischen Kodierung mit reellen Zahlen, nicht die Intervallgrenzen den Kode bestimmen, sondern die Lage des Teilintervalls innerhalb des aktuellen Intervalls. Dies wird deutli-cher, wenn man auch die Skalierungsfunktion E2 betrachtet.

Diese Funktion E2 wird nämlich immer dann aktiv, wenn das Teilintervall komplett in der oberen Hälfte des Intervalls liegt, also die Bedingung low ≥ Q2 zutrifft. Hier wird nun eine binäre ‚1’ ausgegeben, um anzuzeigen, dass das Teilintervall in der oberen Hälfte des aktuellen Intervalls liegt. Ein Beispiel: Das Intervall wurde noch nie skaliert, ist also noch [0; M). Nimmt man an, dass dieses Intervall [0; 1) entspricht, so ist ausgegebene ‚1’ so zu interpretieren, dass die aus der Kodierung resultierende binäre Zahl Z mindestens ‚1’ · 2-1, also auf jeden Fall größer als 0,5 ist. Z liegt also immer im Teilintervall [0,5; 1) bezie-hungsweise [Q2; M). Dies ist genau die gleiche Vorgehensweise, wie sie auch schon bei der Kodierung der reellen Zahl Z per Zweierkomplement erfolgt ist (siehe Kapitel 3.3), nur das dort Z erst binär kodiert wurde als das letzte Intervall bestimmt war. Hier wächst Z schon während der Kodierung.

Würde ein Intervall nie skaliert werden, würde es durch das Prinzip der Arithmetischen Kodierung immer kleiner werden. Auf Grund der schlechten Auflösung der natürlichen Zahlen, würde eine Kodierung recht bald nicht mehr möglich sein, da keine Teilintervalle mehr bestimmt werden könnten. Im Intervall [0; 10) liegen hier nämlich nicht mehr un-endlich viele Zahlen, sondern nur noch 10. Es wären schlichtweg zu wenige Zahlen vor-handen, um die Teilintervalle abbilden zu können. Die letzte Möglichkeit, wie ein Inter-vall sich verkleinern kann, behandelt die Funktion E3.

Die Skalierungsfunktion E3 wird immer dann aktiv, wenn sich die beiden Grenzen des Intervalls, low und high, von unten und oben der Mitte nähern. Auch in diesem Fall wäre der Intervallbereich bald zu klein um mit Integerzahlen kodieren zu können. Im Extrem-fall wäre sogar denkbar, dass low = Q2 - 1 und high = Q2 sind und weder E1 noch E2 würden darauf reagieren. Als Bedingung für die Anwendung von E3 muss der Ausdruck low ≥ Q1 und high < Q3 zutreffen. Das Teilintervall darf also maximal den Umfang des Intervalls [Q1; Q3) haben. Da in diesem Fall noch keine Entscheidung über die endgülti-ge Lage des Teilintervalls getroffen werden kann – im Moment erstreckt es sich noch über beide Hälften – wird diese Entscheidung aufgeschoben. Ein Zähler n für die ausge-führten E3-Skalierungen wird um Eins inkrementiert und das Intervall vergrößert. Erst wenn eine E1- oder E2-Skalierung erfolgt ist, werden n weitere Bits ausgegeben. Im Fall von E1 sind diese n Bits ‚1’ und im Fall von E2 ‚0’. Diese Regel kommt daher, dass eine E3- gefolgt von einer E1-Skalierung ausgedrückt werden kann als eine E1- gefolgt von

Page 15: Arithmetische Kodierung - heiko.exit0.netheiko.exit0.net/ArithCode.pdf · ner Nachricht besser möglich ist als mit Verfahren, wie beispielsweise der Huffman-Kodierung, ... Kode zugewiesen

Kapitel 4 - Festkomma-Implementierung

Heiko Hund 15

einer E2-Skalierung. Ebenso verhält es sich mit einer E3- gefolgt von einer E2-Skalierung. Diese können ausgedrückt werden kann als eine E2- gefolgt von einer E1-Skalierung. Abbildung 3 zeigt anhand einer E3-E1-Skalierung, dass die resultierenden Teilintervalle tatsächlich die Gleichen sind. Voraussetzung die E3-Skalierung ist, dass nur das zweite und dritte Viertel des Intervalls für das Teilintervall in Frage kommen. Diese werden skaliert und die E1-Funktion wählt davon wiederum die untere Hälfte aus. Als Ergebnis erhalt man das zweite Viertel des ursprünglichen Intervalls [Q1; Q2). Wird im Vergleich dazu zuerst die E1- gefolgt von der E2-Fuktion angewendet, ist das Ergebnis zwar identisch, die Vorgehensweise allerdings verschieden. Hier wird zuerst die untere Hälfte selektiert und danach von dieser wieder die obere Hälfte – also effektiv ebenfalls das zweite Viertel. Für die Folge E3-E2 verglichen mit E2-E1 gilt das Gleiche, nur dass hier die untere Hälfte der oberen Hälfte des Intervalls selektiert wird – also das dritte Viertel. Erfolgt also eine E3-Skalierung, wird nur n um Eins hochgezählt, damit bei der Kodierer entsprechend viele E2 beziehungsweise E1 „Bits“ anhängen kann, so dass das Intervall im Nachhinein der kodierten Sequenz entspricht.

0

Q1

Q2

Q3

M

Q1

Q2

Q3

Q1

Q2

E3 E1

0

Q1

Q2

Q3

M

0

Q1

Q2

Q1

Q2

E1 E2 Abbildung 3: Eine E3-E1 Skalierungsfolge im Vergleich mit einer E1-E2

Der Pseudoprogrammkode in Abbildung 5 zeigt nochmals in der Übersicht wie die Kodierung implementiert werden könnte. Man sieht, dass ein sehr geringer Program-mieraufwand notwendig ist, um die Arithmetische Kodierung mit Integern zu implemen-tieren. Will man jedoch verstehen, welche Konzepte und Ziele hinter jeder einzelnen Zei-le Kode stehen, so bedarf es doch einiger Erläuterungen. Dargestellt wird nur die innere Schleife, die für jedes Symbol in der zu kodierenden Sequenz durchlaufen werden muss.

Eine Kleinigkeit fehlt nun noch, um den Algorithmus zu vervollständigen. Die Bitse-quenz muss nämlich, nach dem das letzte Symbol aus der Sequenz bearbeitet wurde, ter-miniert werden. Damit wird erreicht, das die resultierende Zahl Z genau in das Endinter-vall fällt, das am Ende der Kodierung durch [low; high) definiert wird. Es werden also die Bits hinzugefügt, die fehlen um das Z eindeutig ein Intervall beschreiben zu lassen. In

Page 16: Arithmetische Kodierung - heiko.exit0.netheiko.exit0.net/ArithCode.pdf · ner Nachricht besser möglich ist als mit Verfahren, wie beispielsweise der Huffman-Kodierung, ... Kode zugewiesen

Kapitel 4 - Festkomma-Implementierung

Heiko Hund 16

Abbildung 4 wird in der rechten Hälfte gezeigt, welche Lagen für low und high nach der Kodierung möglich sind. Alle anderen Lagen werden bereits durch die Skalierungsfunkti-onen während der Kodierung behandelt. Dies wird in der linken Hälfte der Abbildung dargestellt. Wie bereits bei der Kodierung mit reellen Zahlen gezeigt wurde, genügt es irgendeine Zahl aus dem Intervall zu wählen um den Kode zu erstellen. Deshalb wird in dem Fall, dass low im unteren Viertel des Intervalls liegt, eine Zahl aus dem zweiten Vier-tel gewählt. Für die beiden möglichen Fälle von low < Q1, liegt Z so auf jeden Fall inner-halb des Intervalls. Das zweite Viertel kann, wie schon bei der E3-Skalierungen gezeigt, durch eine Kombination aus E1- und E2-Skalierung kodiert werden. Es werden also die beiden Bits ‚0’ und ‚1’ zum Kode hinzugefügt. Außerdem müssen noch alle unbehandel-ten E3-Skalierungen kodiert werden um den Kode zu vervollständigen. Dadurch werden zusätzlich noch n weitere ‚1’en ausgegeben. Dieses kodieren von E3-Funktionen ist im-mer dann erforderlich, wenn die letzte(n) Skalierung(en) ausschließlich E3 waren, da hier lediglich n inkrementiert wird und keine Bits ausgegeben werden.

Für den verbleibenden Fall, dass low ≥ Q1 ist, wird eine Zahl aus dem dritten Viertel gewählt um Z garantiert im Intervall zu wissen. Entsprechend dem dritten Viertel werden die Bits ‚1’ und ‚0’ hinzugefügt, was die untere Hälfte der oberen Hälfte kodiert. Wie auch im vorigen Fall werden noch n ausstehende E3-Skalierungen kodiert, in diesem Fall aller-dings durch ‚0’en. In Abbildung 6 wird Pseudokode vorgestellt, mit dem sich die Termi-nierung der Kodierung erreichen lässt.

E1 Lagen nach der KodierungE3E2

Abbildung 4: Mögliche Lagen der oberen und unteren Intervallgrenzen

Damit ist die Kodierung der Sequenz beendet und der Dekodierer ist – vorausgesetzt er kennt das zur Kodierung verwendete Modell – in der Lage aus der Zahl Z wieder die ursprüngliche Sequenz herzustellen. Wie er dies im Einzelnen macht, wir im nächsten Abschnitt erläutert.

Page 17: Arithmetische Kodierung - heiko.exit0.netheiko.exit0.net/ArithCode.pdf · ner Nachricht besser möglich ist als mit Verfahren, wie beispielsweise der Huffman-Kodierung, ... Kode zugewiesen

Kapitel 4 - Festkomma-Implementierung

Heiko Hund 17

high = low + hK(a) * [(high – low + 1) / hK(N)] - 1 low = low + hK(a-1) * [(high – low + 1) / hK(N)] loop { if ( high < Q2 ) // E1 Skalierung { Bit “0” ausgeben n mal Bit “1” ausgeben n = 0 low = 2 * low high = 2 * high + 1 } else if ( high > Q2 ) // E2 Skalierung { Bit “1” ausgeben n mal Bit “0” ausgeben n = 0 low = 2 * (low – Q2) high = 2 * (high – Q2) + 1 } else if (( low >= Q1 ) && ( high < Q3 )) // E3 Skalierung { n = n + 1 low = 2 * (low – Q1) high = 2 * (high – Q1) + 1 } else // Schleife verlassen wenn keine Skalierung mehr nötig { end loop } }

Abbildung 5: Pseudokode für die arithmetische Kodierung mit natürlichen Zahlen

n = n + 1 if ( low < Q1 ) { Bit “0” ausgeben n mal Bit “1” ausgeben } else { Bit “1” ausgeben n mal Bit “0” ausgeben }

Abbildung 6: Pseudokode zur Terminierung der Arithmetischen Kodierung

Page 18: Arithmetische Kodierung - heiko.exit0.netheiko.exit0.net/ArithCode.pdf · ner Nachricht besser möglich ist als mit Verfahren, wie beispielsweise der Huffman-Kodierung, ... Kode zugewiesen

Kapitel 4 - Festkomma-Implementierung

Heiko Hund 18

4.2 Dekodierung

Der Dekodierer muss auch hier die Operationen des Kodierers nachahmen. Dazu be-nötigt er die gleichen Variablen wie der Kodierer, also N, B, M, Q1, Q2, Q3, low und high. Zusätzlich benötigt er eine Variable, die die aktuelle Position der Zahl Z speichert. Diese Variable soll hier pos genannt werden. Sie wird vor Beginn der Dekodierung mit den ers-ten B Bits der Zahl Z initialisiert. Sollte |Z| kleiner B sein, so werden Nullen aufgefüllt, bis pos B Bits umfasst. Wäre zum Beispiel B = 5 und Z = 0110010, so würde pos mit dem Wert 12 (001100) initialisiert. Die Nullen und Einsen von pos sind dabei so zu interpretie-ren, dass sie nach dem obere/untere Hälfte Prinzip auf das Teilintervall zeigen, dem das erste Symbol der Nachricht zugeordnet ist. Mit der Formel

1

)(1+

+−−

=Nhlowhigh

lowposhK

K (8)

kann nun die kumulierte Häufigkeit die dem Intervall an der Position pos entspricht, be-rechnet werden, aus der sich wiederum das Symbol selbst bestimmen lässt. Pseudokode dazu zeigt Abbildung 7.

i = N while ( h_K < h_K[i-1] ) { i = i - 1 } s = a_M(i)

Abbildung 7: Pseudokode zur Bestimmung des Symbols s aus hK(a)

Ist das Symbol bekannt, kann der Dekodierer mit der Neuberechnung der Intervall-grenzen fortfahren. Dies geschieht analog zur Kodierung mittels der beiden Gleichungen (6) und (7). Auch die Skalierungsfunktionen E1, E2 und E3 finden hier Anwendung. Zusätzlich zum Intervall wird hier allerdings auch pos mitskaliert, damit es auch nach der Skalierung im richtigen Intervall liegt. Zusätzlich zur Skalierung wird zu pos auch das nächste Bit aus dem Kode hinzuaddiert, was eine weitere Einschränkung des skalierten Intervalls zur Folge hat. Wie der gesamte Vorgang als Pseudokode aussieht zeigt Abbildung 8. Wie nicht anders zu erwarten ist er größtenteils mit dem aus Abbildung 5 identisch. Lediglich die Zeilen zur Ausgabe der Bits werden durch Zeilen zum Einlesen von Bits ersetzt.

Ist der gesamte Bitstrom der kodierten Nachricht verarbeitet, wurden auch alle Symbo-le wieder hergestellt und die Dekodierung kann beendet werden.

Page 19: Arithmetische Kodierung - heiko.exit0.netheiko.exit0.net/ArithCode.pdf · ner Nachricht besser möglich ist als mit Verfahren, wie beispielsweise der Huffman-Kodierung, ... Kode zugewiesen

Kapitel 4 - Festkomma-Implementierung

Heiko Hund 19

high = low + hK(a) * [(high – low + 1) / hK(N)] - 1 low = low + hK(a-1) * [(high – low + 1) / hK(N)] loop { if ( high < Q2 ) // E1 Skalierung { low = 2 * low high = 2 * high + 1 pos = 2 * pos + next_bit() } else if ( high > Q2 ) // E2 Skalierung { low = 2 * (low – Q2) high = 2 * (high – Q2) + 1 pos = 2 * (pos - Q2) + next_bit() } else if (( low >= Q1 ) && ( high < Q3 )) // E3 Skalierung { low = 2 * (low – Q1) high = 2 * (high – Q1) + 1 pos = 2 * (pos - Q1) + next_bit() } else // Schleife verlassen wenn keine Skalierung mehr nötig { end loop } }

Abbildung 8: Pseudokode zur Aktualisierung des Intervalls und pos

4.3 Beispiel

Zur Verdeutlichung der, im Vergleich zur Arithmetischen Kodierung mit reellen Zah-len doch recht komplexen, Kodierung mit Ganzzahlen hier ein Beispiel. Um das Beispiel verständlicher zu halten, wird das Intervall allerdings auf eine relativ geringe Auflösung von B = 6 begrenzt. Um die Sequenz S = {a, d, b} zu kodieren reicht sie aus. Für kom-plexere Nachrichten sei auf das vom Autor im Rahmen der Studienarbeit erstellte Pro-gramm ArithCode verwiesen, das im Kapitel 5 vorgestellt wird.

Wird von B = 6 ausgegangen, hat dies zur Folge, dass das Intervall mit dem die Kodie-rung begonnen wird als [0; 26-1), also [0; 63) definiert ist. Q1 ist demnach 63/4 + 1, al-so 16. Daraus wiederum ergeben sich Q2 = 32 und Q3 = 48. N ist die Anzahl der Sym-bole im Alphabet A, also N = 4. Die beiden Grenzen werden mit low = 0 und high = 63 initialisiert. Zuletzt wird noch der Zähler für die E3-Skalierungen mit n = 0 initialisiert.

Page 20: Arithmetische Kodierung - heiko.exit0.netheiko.exit0.net/ArithCode.pdf · ner Nachricht besser möglich ist als mit Verfahren, wie beispielsweise der Huffman-Kodierung, ... Kode zugewiesen

Kapitel 4 - Festkomma-Implementierung

Heiko Hund 20

Gewappnet mit all diesen Werten kann die Kodierung los gehen. Um das erste Symbol ‚a’ zu kodieren werden zuerst die Grenzen des Intervalls neu bestimmt.

low’ = low + hK(ai-1) · [(high – low + 1) / hK(N)] = 0 + 0 · 6 = 0

high’ = low + hK(a) · [(high – low + 1) / hK(N)] – 1 = 0 + 4 · 6 – 1 = 23

Nun trifft die Bedingung high < Q2 zu und es erfolgt eine E1-Skalierung mit Ausgabe eines ‚0’ Bits.

low’ = 2 · low = 2 · 0 = 0

high’ = 2 · high + 1 = 2 · 23 + 1 = 47

kode = ‚0’ + n · ‚1’ = ‚0’

Da nun keine Skalierung des Intervalls mehr nötig ist, kann mit der Kodierung des nächsten Symbols ‚d’ fortgefahren werden. Wiederum werden die Intervallgrenzen neu berechnet.

low’ = low + hK(ai-1) · [(high – low + 1) / hK(N)] = 0 + 7 · 4 = 28

high’ = low + hK(a) · [(high – low + 1) / hK(N)] – 1 = 0 + 10 · 4 – 1 = 39

In diesem Fall ist nun eine E3-Skalierung notwendig, da die Grenzen des Intervalls sich Q2 nähern.

low’ = 2 · (low – Q1) = 2 · 12 = 24

high’ = 2 · (high – Q1) + 1 = 2 · 23 + 1 = 47

n = n + 1 = 1

Weder low noch high haben sich durch die Skalierung weit genug von Q2 entfernt, so dass abermals eine E3-Skalierung notwendig ist.

low’ = 2 · (low – Q1) = 2 · 8 = 16

Page 21: Arithmetische Kodierung - heiko.exit0.netheiko.exit0.net/ArithCode.pdf · ner Nachricht besser möglich ist als mit Verfahren, wie beispielsweise der Huffman-Kodierung, ... Kode zugewiesen

Kapitel 4 - Festkomma-Implementierung

Heiko Hund 21

high’ = 2 · (high – Q1) + 1 = 2 · 31 + 1 = 63

n = n + 1 = 2

Nun ist das Intervall groß genug, um mit der Kodierung des nächsten und letzten Sym-bols ‚b’ fortzufahren. Begonnen wird wie bei den anderen Symbolen auch mit der Neu-berechnung der Intervallgrenzen.

low’ = low + hK(ai-1) · [(high – low + 1) / hK(N)] = 16 + 4 · 4 = 32

high’ = low + hK(a) · [(high – low + 1) / hK(N)] – 1 = 16 + 6 · 4 – 1 = 39

Nun tritt zum ersten Mal der Fall ein, dass low ≥ Q2. Somit wird eine E2-Skalierung notwendig.

low’ = 2 · (low – Q2) = 2 · 0 = 0

high’ = 2 · (high – Q2) + 1 = 2 · 7 + 1 = 15

kode = kode + ‚1’ + n · ‚0’ = ‚0100’

n = 0

Nach dieser Skalierung hat low zwar wieder den kleinstmöglichen Wert, der Wert von high ist aber ebenfalls stark gefallen, so dass nun wieder high < Q2 gilt und dadurch eine E1-Skalierung notwendig ist.

low’ = 2 · low = 2 · 0 = 0

high’ = 2 · high + 1 = 2 · 15 + 1 = 31

kode = kode + ‚0’ + n · ‚1’ = ‚01000’

Wieder ist high < Q2, so dass nochmals eine E1-Skalierung angewandt wird.

low’ = 2 · low = 2 · 0 = 0

high’ = 2 · high + 1 = 2 · 31 + 1 = 63

Page 22: Arithmetische Kodierung - heiko.exit0.netheiko.exit0.net/ArithCode.pdf · ner Nachricht besser möglich ist als mit Verfahren, wie beispielsweise der Huffman-Kodierung, ... Kode zugewiesen

Kapitel 4 - Festkomma-Implementierung

Heiko Hund 22

kode = kode + ‚0’ + n · ‚1’ = ‚010000’

Da nun alle Symbole kodiert sind und auch keine Skalierungen mehr nötig sind, muss die Kodierung noch terminiert werden. Dies geschieht da n dem Wert Null hat und low < Q1 ist, mit den Bits ‚01’ (siehe Abbildung 6). Die Zahl Z die die Sequenz S kodiert, ist also binär ‚01000001’, was der dezimalen 0,25390625 entspricht. Die Tatsache, dass der Kode im Vergleich zu dem in Kapitel 3.3 berechneten um drei Bit länger ist, ist auf die sehr begrenzte Auflösung des Intervalls und die Kürze der Sequenz zurückzuführen. Tatsächlich ist die Annäherung an die Entropie einer Nachricht, auch mit diesem Verfah-ren gewährleistet, wenn die maximale Intervallbreite verwendet wird und die Nachrichten länger sind.

Um Z wieder dekodieren zu können muss zunächst pos mit den ersten sechs Bits des Kodes initialisiert werden (pos = 16). Die beiden Intervallgrenzen werden mit low = 0 und high = 63 initialisiert. Die Werte der anderen Variablen werden übernommen.

Zu Beginn wird die kumulierte Häufigkeit berechnet, die innerhalb des Intervalls liegt, das dem Symbol zugeordnet ist.

hK = (pos – low) /[(high – low + 1) / hK(N)] + 1 = 16 / 6 + 1 = 3

Die 3 liegt in dem Intervall [0; 4). Das Symbol das gerade dekodiert wurde ist demnach ein ‚a’. Mit dem ‚a’ beziehungsweise seiner kumulierten Häufigkeit kann man nun die Grenzen des Intervalls neu berechnen. Die Rechnung verläuft genau so ab, wie die, bei der Kodierung der Sequenz. low wird 0 bleiben und high nimmt den Wert 23 an. Deshalb wird eine E1-Skalierung durchgeführt, die zum Ergebnis hat, dass low = 0 und high = 47. Der einzige Unterschied ist, dass auch pos mitskaliert wird, also den Wert

pos’ = 2· pos + next_bit() = 2·16 + 0 = 32

annimmt. Mit dem neuen Wert von pos wird nun wieder die kumulative Häufigkeit be-rechnet, die im Intervall des Symbols liegt, welches dekodiert werden soll.

hK = (pos – low) /[(high – low + 1) / hK(N)] + 1 = 32 /4 + 1 = 9

Die 9 liegt eindeutig im Intervall [7; 10), was sie zum Symbol ‚d’ zuordnet. Mit diesem ‚d’ werden erneut die Intervallgrenzen neu berechnet. Das Ergebnis ist, wie auch schon bei der Kodierung low = 28 und high = 39. Es werden ebenfalls zwei E3-Skalierungen durchgeführt, die letztendlich zur Folge haben, dass low = 16, high = 63 und pos den Wert 34 annimmt:

pos’ = 2· (pos – Q1) + next_bit() = 2· (32 – 16) + 1 = 33

Page 23: Arithmetische Kodierung - heiko.exit0.netheiko.exit0.net/ArithCode.pdf · ner Nachricht besser möglich ist als mit Verfahren, wie beispielsweise der Huffman-Kodierung, ... Kode zugewiesen

Kapitel 4 - Festkomma-Implementierung

Heiko Hund 23

pos’ = 2· (pos – Q1) + next_bit() = 2· (33 – 16) + 0 = 34

Mit diesem neu berechneten pos kann man nun auch das letzte Symbol dekodieren. Man errechnet die kumulative Häufigkeit und betrachtet das Intervall in dem diese liegt. Entsprechend diesem Intervall wählt man das Symbol.

hK = (pos – low) /[(high – low + 1) / hK(N)] + 1 = 18 / 4 + 1 = 5

Die errechnete 5 ist innerhalb des Intervalls [4; 6) und wird demnach zum ‚b’ dekodiert. Damit wäre die gesamte Nachricht wieder aus dem Bitstrom extrahiert. In der Praxis funktioniert das genau so wie hier im Beispiel, bis auf die Tatsache, dass in der Regel mit einem B = 31 gearbeitet wird, was eine bessere Abbildung der Teilintervalle erlaubt. Die großen Zahlen, mit denen dabei gerechnet wird sind für ein Beispiel jedoch nicht wirklich dienlich. Wer Interesse hat die Berechnungen auch in diesen Regionen zu verfolgen, der kann dazu das Programm ArithCode verwenden, da es über alle Variablen und ihre Ver-änderungen während der Kodierung Auskunft gibt.

Page 24: Arithmetische Kodierung - heiko.exit0.netheiko.exit0.net/ArithCode.pdf · ner Nachricht besser möglich ist als mit Verfahren, wie beispielsweise der Huffman-Kodierung, ... Kode zugewiesen

Kapitel 5 - Das Programm ArithCode

Heiko Hund 24

5 Das Programm ArithCode

Im Programm ArithCode wurde die Arithmetische Kodierung mit Ganzzahlen imple-mentiert. Der Programmkode zur Kodierung und Dekodierung entspricht weitestgehend dem in Abbildung 5, Abbildung 6, Abbildung 7 und Abbildung 8 vorgestellten Kode. Zur Implementierung wurde die objektorientierte Sprache C++ verwendet. Um da Pro-gramm komfortabler Bedienen zu können, wurden Kodierer und Dekodierer in einem ausführbares Programm angesiedelt. So ist ein schnelles Vergleichen der Ergebnisse unter verschiedenen Rahmenbedingungen möglich. Es wurde eine graphische Benutzerschnitt-stelle entwickelt, mit der man das Programm unter Microsoft Windows bedienen kann. Im Folgenden sollen nun Kurz die drei Bildschirmmasken vorgestellt und die Bedienung des Programms erläutert werden.

Abbildung 9: Bildschirmmaske des Kodierers im Programm ArithCode

Startet man das Programm, so befindet man sich auf der Maske des Kodierers. Mit den Karteikarten (1) kann man zu den anderen Modulen des Programms wechseln. Auf dieser

Page 25: Arithmetische Kodierung - heiko.exit0.netheiko.exit0.net/ArithCode.pdf · ner Nachricht besser möglich ist als mit Verfahren, wie beispielsweise der Huffman-Kodierung, ... Kode zugewiesen

Kapitel 5 - Das Programm ArithCode

Heiko Hund 25

Seite befindet sich ein Eingabefeld (2), in das bis zu 30.000 Zeichen eingegeben werden können. Diese Zeichen dienen dem Arithmetischen Kodierer als zu kodierende Sequenz. Befindet sich in diesem Eingabefeld mindestens ein Zeichen, so kann man mit dem But-ton (3) die Kodierungsvorgang starten. Der aus der Kodierung resultierende Bitstring, wird im Feld (4) ausgegeben. Sollte er nicht vollständig in das Feld hineinpassen, sieht man nur das Ende des Bitstrings, kann aber mit Maus oder Cursor im Feld scrollen, wie man es von Eingabefeldern gewohnt ist. Das Feld (5) dient dem Kodierer Nachrichten an den Benutzer auszugeben. Für den Fall, dass die Checkbox (6) aktiviert ist, werden detaillierte Informationen über den Kodierungsvorgang ausgegeben während er im Gan-ge ist. Es empfiehlt sich nicht sich die Details der Kodierung einer längeren Nachricht anzeigen zu lassen, da sonst sehr viele Daten anfallen. Den Button (7) kann man dazu verwenden, die ausgegebenen Informationen zu löschen. Der Button (8) dient dazu, den Kodierer und den Dekodierer wieder in ihre Ausgangslage zurück zu versetzen, das Mo-dell ist davon nicht betroffen. Button (9) beendet das Programm. Die beiden letztgenann-ten Buttons und die Karteikarten (1) sind in jeder Maske sichtbar und haben immer die gleiche Funktionalität.

Abbildung 10: Bildschirmmaske des Dekodierers im Programm ArithCode

Page 26: Arithmetische Kodierung - heiko.exit0.netheiko.exit0.net/ArithCode.pdf · ner Nachricht besser möglich ist als mit Verfahren, wie beispielsweise der Huffman-Kodierung, ... Kode zugewiesen

Kapitel 5 - Das Programm ArithCode

Heiko Hund 26

Die Maske des Dekodierers ist ähnlich aufgebaut wie die des Kodierers. Das Feld (A) wird mit dem Ergebnis der letzten Kodierung gefüllt, sollte schon eine erfolgt sein. Ist dieses Feld leer, kann die Dekodierung auch nicht mit dem Button (B) gestartet werden. Andernfalls wird, nach dem die Dekodierung gestartet wurde die dekodierte Nachricht in das Feld (C) ausgegeben. Auch der Dekodierer verfügt über ein Informationsfeld (D), in dem, sollte die Checkbox (E) aktiviert sein, detaillierte Informationen über den Dekodie-rungsvorgang ausgegeben werden. Diese Informationen kann man mit dem Button (F) wieder löschen.

Abbildung 11: Bildschirmmaske für das Modell im Programm ArithCode

Normalerweise generiert der Kodierer, bevor er mit der Bearbeitung einer Nachricht anfängt ein Modell für die Kodierung. Dieses Modell initialisiert er mit den exakten Häu-figkeiten der Nachricht, so dass ein perfekter Kode die Folge ist. Will man die Auswir-kungen eines suboptimalen Modells betrachten, so wird man von der Maske für das Mo-dell dabei unterstützt. Ist die Checkbox (I) aktiviert, so generiert der Kodierer kein neues Modell, wenn die Kodierung gestartet wird, sondern verwendet die Werte für die Häufig-keiten der Symbole, die in der Liste (II) nach belieben verändert werden können. Passt

Page 27: Arithmetische Kodierung - heiko.exit0.netheiko.exit0.net/ArithCode.pdf · ner Nachricht besser möglich ist als mit Verfahren, wie beispielsweise der Huffman-Kodierung, ... Kode zugewiesen

Kapitel 5 - Das Programm ArithCode

Heiko Hund 27

das Modell jedoch nicht zum Text, so kommt es zwangsläufig zu Fehlern und die Kodie-rung bricht ab (diesbezüglich das Informationsfenster (5) beachten). Das ist immer dann der Fall, wenn ein Symbol mit der Häufigkeit 0 kodiert werden soll, was per Definition nicht gültig ist. Wird ein Modell von Kodierer erstellt, so finden sich die entsprechenden Häufigkeitswerte in der Liste (II) und können nachträglich verändert werden um zu se-hen, welchen Einfluss das Modell auf die Effizienz der Kodierung hat. Dies ist aber wie gesagt nur der Fall, wenn Checkbox (I) deaktiviert ist, während die Kodierung statt fin-det. Eine andere Möglichkeit an die genauen Häufigkeiten einer Nachricht zu gelangen bietet Button (III). Wird er gedrückt so initialisiert er das Modell nach den Daten im Ein-gabefeld des Kodierers (2). Liste (II) und Button (III) sind allerdings nur aktiviert, wenn auch Checkbox (I) aktiviert ist.

Außer der Beobachtung, wie ein suboptimales Modell die Kodiereffizienz beeinflusst, kann man mit einem manuell angepassten Modell auch noch überprüfen, das der Deko-dierer das gleiche Modell verwenden muss mit dem kodiert wurde, um erfolgreich die Nachricht aus dem Bitstrom zu erstellen. Lässt man nämlich den Kodierer ein Modell erstellen, indem Checkbox (I) deaktiviert ist, aktiviert sie dann bevor man dekodiert und verändert die Häufigkeit eines Symbols, so ist die anschließende Dekodierung nicht er-folgreich.

Page 28: Arithmetische Kodierung - heiko.exit0.netheiko.exit0.net/ArithCode.pdf · ner Nachricht besser möglich ist als mit Verfahren, wie beispielsweise der Huffman-Kodierung, ... Kode zugewiesen

Verzeichnisse

Heiko Hund 28

Abbildungsverzeichnis

Abbildung 1: Unterteilung des Startintervalls beim einem gegebenen Modell PM 6 Abbildung 2: Intervallbildung für die Sequenz {a, d, b} 9 Abbildung 3: Eine E3-E1 Skalierungsfolge im Vergleich mit einer E1-E2 15 Abbildung 4: Mögliche Lagen der oberen und unteren Intervallgrenzen 16 Abbildung 5: Pseudokode für die arithmetische Kodierung mit natürlichen Zahlen 17 Abbildung 6: Pseudokode zur Terminierung der Arithmetischen Kodierung 17 Abbildung 7: Pseudokode zur Bestimmung des Symbols s aus hK(a) 18 Abbildung 8: Pseudokode zur Aktualisierung des Intervalls und pos 19 Abbildung 9: Bildschirmmaske des Kodierers im Programm ArithCode 24 Abbildung 10: Bildschirmmaske des Dekodierers im Programm ArithCode 25 Abbildung 11: Bildschirmmaske für das Modell im Programm ArithCode 26

Tabellenverzeichnis

Tabelle 1: Kumulierte Häufigkeiten und Intervallgrenzen beim Modell PM 6

Literaturverzeichnis

[1] Tilo Strutz: Bilddatenkompression, pp 39–50, Vieweg Verlag, 2002 [2] Peter Henning: Taschenbuch Multimedia, pp 36–41, Fachbuchverlag Leipzig, 2000 [3] E. Bodden, M. Clasen, J. Kneis: Arithmetische Kodierung, Proseminararbeit,

RWTH Aachen, 2002 [4] I. Witten, R. Neal, J. Cleary: Arithmetic Coding for Datacompression, pp520–540,

Communications of the ACM, Vol. 30, No. 6, 1987 [5] Claude Shannon: A Mathematical Theory of Communication, Bell System Technical

Journal, Vol. 27, 1948