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.

Alle Artikel rss Wochenübersicht Monatsübersicht Github Repositories Gitlab Repositories Mastodon Über mich home xmpp


Vor 5 Jahren hier im Blog

  • Virtuelles Netzwerklabor

    11.01.2017

    Nachdem ich hin und wieder vor der Herausforderung stehe, Anwendungen unter realen Netzwerkbedingungen zu testen, habe ich bereits vor längerer Zeit begonnen, ein virtuelles Netzwerklabor aufzubauen...

    Weiterlesen...

Neueste Artikel

  • Stratum-1-NTP-Server Links

    Ich habe meinen eigenen Stratum-1-NTP-Server mittels eines GPS-Empfängers, einer Adapterschaltung und einem Raspi gebaut. Hier fasse ich einige nützliche Links zu diesem Themengebiet zusammen

    Weiterlesen...
  • EBCMS threaded und mit mehr Markdown-Unterstützung

    Mein eigener Static Site Generator hat in den letzten Wochen einige größere Umbauten erfahren

    Weiterlesen...
  • Fork der BeanShell wegen Trojan Source

    Es gibt inzwischen einen von mir erstellten Fork des originalen Repository, in dem ich die Komponente zur Darstellung der Konsole gegen die ausgetauscht habe, die in der sQLshell in den Plugins MDIJavaEditor und MDISqlEditor zum Einsatz kommt - dadurch wird wenigstens durch das Syntax-Highlighting auf problematische Stellen im Code hingewiesen.

    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, muß 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 GitHub-Repositories findet man hier.