Bitstrom-Repräsentation von Morse-Code

vorhergehende Artikel in: Rants

14.02.2016

In meinem Urlaub überlegte ich mir Ideen zur Veranschaulichung verschiedener Anforderungen und Qualitätsparameter beim Systemdesign. Dazu nutzte ich die Fragestellung: "Entwickeln sie eine Repräsentation zur Übermittlung von Morse-Zeichen"

Einleitung

Rufen wir uns zunächst die Festlegungen der Signalisierung mittels Morse ins Gedächtnis: Es gibt zwei Symbole: das "dit" ist kürzer als das "dah". Ein "dit" ist eine Zeiteinheit lang, ein "dah" drei Zeiteinheiten. "dits" und "dahs" werden durch Pausen voneinander getrennt, die innerhalb eines Buchstabens eine Zeiteinheit dauern, zwischen Buchstanben drei Zeiteinheiten und zwischen Worten 7 Zeiteinheiten. Daraus folgt, dass wir ein Alphabet mit 5 Zeichen kodieren müssen: eins steht für "dit", eins für "dah" und drei für die verschiedenen Pausen.

Wir legen des weiteren fest, dass wir nur den Grundzeichenvorrat berücksichtigen, der sich mit 5 Tönen kodieren lässt - die verschiedenen Länderspezifischen Erweiterungen lassen wir weg.

Die Länge des Bitstroms für die jeweilige Kodierung wird mittels der beiden Worte

PARIS: .--. .- .-. .. ...

und

OSCAR: --- ... -.-. .- .-.

veranschaulicht ("." ist dabei ein "dit" und "-" ein "dah").

Triviale Kodierung

Hierzu kodieren wir einfach die Töne mittels Einsen und die Pausen mittels Nullen - das bedeutet:

dit - 1
dah - 111
Pause zwischen Tönen - 0
Pause zwischen Buchstaben - 000
Pause zwischen Worten - 0000000

Diese Kodierung ist durch einen Transcoder besonders einfach in Töne oder Signale zur Übertragung umzusetzen. Sie geht allerdings auch sehr verschwenderisch mit der Kapazität des Übertragungskanals um. Das länste darzustellende Zeichen kommt dadurch auf eine Länge von 19 Bit. Das kürzeste darzustellende Zeichen kommt auf genau ein Bit. Da die Symbole so gewählt wurden, dass die am häufigsten benutzten durch kürzere Symbolgruppen dargestellt werden, liegt der tatsächliche Aufwand an Bits pro Zeichen für eine gesamte Botschaft irgendwo dazwischen.

PARIS: 10111011101000101110001011101000101000101010 (44 Bit)
OSCAR: 111011101110001010100011101011101000101110001011101 (51 Bit)

Triviale Kodierung trivial komprimiert

Diese Kodierung könnte man auf einfache Art und Weise ein wenig mehr in Richtung Datensparsamkeit trimmen:

dit - 1
dah - 11
Pause zwischen Tönen - 0
Pause zwischen Buchstaben - 00
Pause zwischen Worten - 000

Das verkürzt die Länge des längsten darzustellenden Buchstabens auf 14 Bit. Damit ist aber das Ende der Fahnenstange noch lange nicht erreicht.

PARIS: 101101101001011001011010010100101010 (36 Bit)
OSCAR: 1101101100101010011010110100101100101101 (40 Bit)

Kodierung mit impliziten Symbolen

Im Internet fand ich eine Idee, die Pausen zwischen den Tönen und den Buchstaben implizit zu kodieren: ein Zeichen wird dabei immer 8 Bit breit wie folgt dargestellt:

lllttttt
l kodiert die Länge der Symbolgruppe (Anzahl der "dits" und "dahs")
t kodiert die "dits" und "dahs": 1 bedeutet "dit" und 0 bedeutet "dah"

Damit ist ein Buchstabe nur noch 8 Bit lang. Die Pausen zwischen Tönen und zwischen Buchstaben müssen nicht mehr explizit kodiert werden. Die Pause zwischen Worten kann durch eine spezielle Länge kodiert werden: wir müssen nur 5 verschiedene Längen kodieren können, könnten aber mit den drei zur Verfügung stehenden l-Bits 8 verschiedene Muster kodieren: Wir erklären eines der nicht benötigten zum Marker für Wortgrenzen.

PARIS: 1001001001010000011101000101100001111100 (40 Bit)
OSCAR: 0110000001111100100010100101000001110100 (40 Bit)

Lauflängen-Kodierung mit impliziten Symbolen

Man sieht fast sofort eine Möglichkeit, die Kodiereffizienz zu steigern: Wenn man jedes Symbol nicht mehr auf eine Länge von 8 Bit festlegt, sondern so lang macht, wie es tatsächlich gebraucht wird, spart man einige Bits ein - das bedeutet, dass das Symbol für "e" nur noch vier Bytes einnehmen würde: 0011. Dabei stehen die ersten drei Bit für die Anzahl an Tönen: 001 bedeutet 1 und "dit": 1 bedeutet "dit". Dadurch, dass häufigere Zeichen durch kürzere Symbolfolgen kodiert werden, erreicht man eine deutliche Absenkung der Bits pro Zeichen für eine gesamte Message auf deutlich unter 8.

PARIS: 10010010101001110101011011111 (29 Bit)
OSCAR: 011000011111100010101010011101 (30 Bit)

Lauflängen-Kodierung mit variabel langen Längenangaben

Die Überschrift klingt erst einmal seltsam. Es geht dabei ganz einfach gesagt darum, dass die Zeichen, deren Symbolfolge sowieso schon kurz ist, noch ein Bit verlieren: Beginnt die Längenangabe mit einer "0", ist das Feld, das die Länge kodiert, nur zwei Bit lang, ansonsten drei. Das bedeutet folgendes für die Längen:

00 - 1 Bit
01 - 2 Bit
100 - 3 Bit
101 - 4 Bit
110 - 5 Bit

Das spezielle Längenfeld "111" würde auch bei dieser Methode wieder die Wortgrenze markieren. Damit senkt man die Anzahl der Bits pro Zeichen für eine gesamte Message nochmals deutlich ab.

PARIS: 101100101101001010111100111 (27 Bit)
OSCAR: 10000010011110101010110100101 (29 Bit)

Fazit

Wie man sehr schön sieht, muss man in der Informatik wie in allen anderen Lebensbereichen immer Kompromisse machen - hier ist es der klassische "Komplexität vs. Speicherbedarf": Je weniger Bits benötigt werden, desto komplexer wird die Kodierung und dementsprechend aufwendiger die Dekodierung. Wenn man aber nochmals klassisch durchrechnet, wie viele Bits man benötigen würde, wenn man ohne Morse kodiert, so kommt man auf:

Morse-Alphabet: 26 Buchstaben + 10 Zeichen + 1 Worttrenner - ergibt aufgerundet 6 Bit pro Zeichen (5 Bit ergeben 32 darstellbare Symbole - das reicht nicht)

Rechnet man nun für unsere beste Kodierung die Bits pro Zeichen aus, kommt man aufgerundet ebenfalls auf 6 - damit sind wir rein rechnerisch ziemlich nahe am Optimum, wenn man gebrochenzahlige Bits nicht beachtet.

Vor 5 Jahren hier im Blog

Multi-User-WebDAV, Docker, GitHub

17.11.2019

Nachdem ich mich in letzter Zeit verstärkt mit Docker und dem zugehörigen Ökosystem beschäftige, habe ich begonnen, verschiedenste Dienste in Containern zu testen um zu sehen, ob in manchen Fällen LXC oder KVM nicht doch die bessere Wahl wäre...
Weiterlesen...

Neueste Artikel

Migration der Webseite und aller OpenSource Projekte

In eigener Sache...
Weiterlesen...
AutoHideToolbar für Java Swing

Ich habe eine neue Java Swing Komponente erstellt: Es handelt sich um einen Wrapper für von JToolBar abgeleitete Klassen, die die Werkzeugleiste minimieren und sie nur dann einblenden, wenn der Mauszeiger über ihnen schwebt.
Weiterlesen...
Integration von EBMap4D in die sQLshell

Ich habe bereits in einem früheren Artikel über meine ersten Erfolge berichtet, der sQLshell auf Basis des bestehenden Codes aus dem Projekt EBMap4D eine bessere Integration für Geo-Daten zu spendieren und entsprechende Abfragen, bzw. deren Ergebnisse auf einer Kartenansicht zu visualisieren.
Weiterlesen...

Manche nennen es Blog, manche Web-Seite - ich schreibe hier hin und wieder über meine Erlebnisse, Rückschläge und Erleuchtungen bei meinen Hobbies.

Wer daran teilhaben und eventuell sogar davon profitieren möchte, muss damit leben, daß ich hin und wieder kleine Ausflüge in Bereiche mache, die nichts mit IT, Administration oder Softwareentwicklung zu tun haben.

Ich wünsche allen Lesern viel Spaß und hin und wieder einen kleinen AHA!-Effekt...

PS: Meine öffentlichen Codeberg-Repositories findet man hier.