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

Synchronisierung von Lorenz-Systemen III

23.10.2020

Nachdem ich in einem vorhergehenden Artikel auf das Problem des kleinen Parameterraums im Zusammenhang mit der Nutzung synchronisierter chaotischer Systeme hingewiesen hatte will ixch hier untersuchen, wie sensibel solche Systeme auf Abweichungen der Parameterwerte zwischen treibendem und getriebenen System reagieren
Weiterlesen

Neueste Artikel

Plugin zur Arbeit mit Markdown für NeoVim

Ich habe neulich beschrieben, dass ich aktuell mehr und mehr bemerke, dass Dinge, für die ich in meinem NeoVim-Setup Plugins benutzt habe sehr gut auch mit Bordmitteln funktionieren.
Weiterlesen
Raspbian Upgrade von 11 (Bullseye) nach 12 (Bookworm)

Ich habe neulich wieder einmal eine Upgrade- und Backup-Sitzung mit meinen diversen Linuxinstallationen veranstaltet. Der Zeitpunkt schien mir gekommen, da es eine neue stable Variante von Debian (Trixie) gibt.
Weiterlesen
Meine praktischen Erfahrungen mit ollama (llava)

Ich diskutiere immer wieder gern über das was heute Machine Intelligence oder Artificial Intelligence ( oder wie die ganzen anderen hohlen Phrasen heißen, die dafür heutzutage als Buzzwords missbraucht werden). Das geschieht online, in meinem $dayjob oder auch privat. Meine Meinung steht fest: das ist alles Quatsch und steht in keiner Relation zum Nutzen
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.