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.

Kommentar hinzufügen (via Github ) Kommentare ansehen (via Github )

Kommentar hinzufügen (via ) Kommentare ansehen (via )

Vor 5 Jahren hier im Blog

Alte Rechner zukunftsfähig (?)

01.05.2019

Ich mache immer wieder gerne Experimente mit Terminalsessions - meistens wegen der zentral möglichen Administration. Nunhabe ich das Thema von neuem angepackt: wegen einem alten(sehr alten) Laptop, der bei mir schon so lange im Schrank lag, dass sogar die BIOS-Batterie inzwischen leer war...
Weiterlesen...

Neueste Artikel

Graphics2D Implementierung für Java mit verlegtem Koordinatenursprung

Es gibt seit vielen Jahren immer mal wieder Leute, die im Internet fragen, ob man in Javas diversen Methoden zum Zeichnen von Graphiken das Koordinatensystem so ändern könnte, dass sich der Koordinatenursprung links unten befindet und die positive y-Achse nach oben weist. Meist sind die Antworten dann, dass eine Affine Transformation eingeschaltet werden solle, die das Bild spiegelt.
Weiterlesen...
Unerwartete Probleme bei der Software Raid5 Erweiterung

Ich bin an die Grenzen meiner Storagelösung gestoßen - es musste mehr Platz her...
Weiterlesen...
Die sQLshell ist nun cloudnative!

Die sQLshell hat eine weitere Integration erfahren - obwohl ich eigentlich selber nicht viel dazu tun musste: Es existiert ein Projekt/Produkt namens steampipe, dessen Slogan ist select * from cloud; - Im Prinzip eine Wrapperschicht um diverse (laut Eigenwerbung mehr als 140) (cloud) data sources.
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 - meine öffentlichen GitLab-Repositories finden sich dagegen hier.