Telegraphy Golf: Baudot-Code entschlüsseln

31

Hintergrund

1870 erfand Émile Baudot den Baudot-Code , eine Zeichenkodierung mit fester Länge für die Telegraphie. Er entwarf den Code, der über eine manuelle Tastatur mit nur fünf Tasten eingegeben werden konnte. zwei mit der linken und drei mit der rechten Hand bedient:

Baudot-Tastatur mit 5 Tasten

Mit dem rechten Zeige-, Mittel- und Ringfinger werden die Tasten I , II und III betätigt , mit dem linken Zeige- und Mittelfinger die Tasten IV und . (Von nun an verwende ich die arabischen Ziffern ( 1 bis 5) .) Zeichen werden als Akkorde eingegeben. Um beispielsweise den Buchstaben "C" einzugeben, drückt der Bediener die Tasten 1 , 3 und 4Tasten gleichzeitig, woraufhin ein rotierender Bürstenarm jede Taste der Reihe nach liest und einen Strom oder bei nicht gedrückten Tasten keinen Strom überträgt. Das Ergebnis ist in modernen Begriffen eine 5-Bit-Binärcodierung mit dem niedrigsten Stellenwert und dem ersten Stellenwert, in der unser Beispiel "C" wie folgt codiert ist 10110.

5 bits ??

Sie könnten denken, dass 5 Bits, die höchstens 32 eindeutige Symbole ausdrücken können, nicht einmal für alle englischen Buchstaben und Ziffern ausreichen, um von Interpunktion ganz zu schweigen. Baudot hatte jedoch einen Trick im Ärmel: Sein Zeichensatz besteht eigentlich aus zwei unterschiedlichen Sätzen: Buchstaben und Zahlen , und er definierte zwei spezielle Codes, um zwischen ihnen zu wechseln. Die Buchstabenverschiebung , die in den Buchstabenmodus wechselt, wird durch Drücken der Taste 5 ( 00001) und die Ziffernverschiebung durch Drücken der Taste 4 ( 00010) aktiviert .

Herausforderung

Ihre Herausforderung besteht darin, ein Programm oder eine Funktion zu schreiben, die Baudot-Code-Übertragungen decodiert.

Eine echte Übertragung würde mit einigen Initialisierungsbits sowie einem Start- und Stoppbit vor und nach jedem Zeichen beginnen, aber wir werden diese überspringen und uns nur um die 5 eindeutigen Bits für jedes Zeichen kümmern. Eingabe- und Ausgabeformate werden unten erläutert.

Baudots Code

Es gibt zwei verschiedene Versionen von Baudot Code: Continental und UK Wir verwenden die UK-Version, die keine Zeichen wie "É" aus Baudots französischem Muttersprachler enthält. Wir werden auch alle Symbole in der britischen Version weglassen, die nicht zu den druckbaren ASCII-Zeichen gehören. Sie müssen nur die Zeichen in der folgenden Tabelle dekodieren. Mit Ausnahme der letzten drei Steuerzeichen, die unter der Tabelle erläutert werden, handelt es sich bei allen Zeichen um druckbare ASCII-Zeichen.

Die Spalte "Ltr" zeigt die Zeichen im Buchstabenmodus und "Fig" zeigt die Zeichen im Figurenmodus:

        Encoding             Encoding
Ltr Fig  12345       Ltr Fig  12345
--- --- --------     --- --- --------
 A   1   10000        P   +   11111
 B   8   00110        Q   /   10111
 C   9   10110        R   -   00111
 D   0   11110        S       00101
 E   2   01000        T       10101
 F       01110        U   4   10100
 G   7   01010        V   '   11101
 H       11010        W   ?   01101
 I       01100        X       01001
 J   6   10010        Y   3   00100
 K   (   10011        Z   :   11001
 L   =   11011        -   .   10001
 M   )   01011        ER  ER  00011
 N       01111        FS  SP  00010
 O   5   11100        SP  LS  00001
 /       11000

Die letzten drei Zeilen in der rechten Spalte sind Steuerzeichen:

  • ERist Löschen . Baudots Telegraphiemaschinen würden ein Sternchen-ähnliches Symbol für dieses Zeichen drucken, um dem Leser mitzuteilen, dass das vorangegangene Zeichen ignoriert werden sollte, aber wir werden dem Leser noch netter sein und das vorangegangene Zeichen weglassen (nicht drucken) . Es verhält sich sowohl im Buchstaben- als auch im Zahlenmodus gleich.

  • FSist Figure Shift . Dies schaltet den Zeichensatz von Buchstaben auf Zahlen um. Wenn die Decodierer bereits in Figur Modus wird als FS behandelt Raum (ergo SPin der „ltr“ Spalte). Wenn sich der Decoder im Figurenmodus befindet, bleibt er im Figurenmodus, bis ein LS-Zeichen empfangen wird.

  • LSist die Buchstabenverschiebung . Es wechselt den Zeichensatz von Figuren zu Buchstaben. Wenn der Decoder bereits im Textmodus ist, wird LS als behandeltes Raum . Im Letter-Modus bleibt der Decoder im Letter-Modus, bis ein FS-Zeichen empfangen wird.

Der Decoder startet immer im Letter-Modus.

Hier ist ein Beispiel mit Figure Shift, Letter Shift und Space:

01011 10000 00100 00001 00010 10000 11100 00001 10101 11010
  M     A     Y   LS/SP FS/SP   1     5   LS/SP   T     H

Dies ergibt die Nachricht MAY 15TH. Wie Sie sehen, fungiert das erste 00001Zeichen (Buchstabenverschiebung / Leerzeichen) als Leerzeichen, da sich der Decoder bereits im Buchstabenmodus befindet. Das nächste Zeichen 00010(Figure Shift / Space) schaltet den Decoder zum Drucken in den Figure-Modus 15. Dann 00001erscheint wieder, aber dieses Mal ist es als Brief Verschiebung wirkt , um den Decoder zurück in Brief - Modus zu schalten.

Im Folgenden finden Sie die Zeichen in einem Format, das in einem Editor möglicherweise einfacher zu verarbeiten ist, sortiert nach Code:

A,1,10000|E,2,01000|/,,11000|Y,3,00100|U,4,10100|I,,01100|O,5,11100|FS,SP,00010|J,6,10010|G,7,01010|H,,11010|B,8,00110|C,9,10110|F,,01110|D,0,11110|SP,LS,00001|-,.,10001|X,,01001|Z,:,11001|S,,00101|T,,10101|W,?,01101|V,',11101|ER,ER,00011|K,(,10011|M,),01011|L,=,11011|R,-,00111|Q,/,10111|N,,01111|P,+,11111

Eingang

Die Eingabe ist eine Zeichenfolge, ein Array oder eine Liste von Bits in der niedrigstwertigen Bit-First-Reihenfolge. Jedes Zeichen wird durch ein Quintett von 5 Bits dargestellt. Bits können in jedem vernünftigen Format vorliegen, z. B. als Binärzeichenfolge, als Array von 0s und 1s, als Zeichenfolge "0"und "1" Zeichen, als einzelne sehr große Zahl usw., sofern sie den Bits der Übertragung direkt zugeordnet sind.

Jede Übertragung hat mindestens ein druckbares Quintett und höchstens 255 Quintette (druckbar oder auf andere Weise), dh 5 bis einschließlich 1.275 Bit.

Die Eingabe kann nur die Bits der Übertragung enthalten, mit zwei zulässigen Ausnahmen: Der Übertragung kann eine beliebige Anzahl von führenden oder nachfolgenden 0Bits und / oder für die Zeichenfolgeeingabe eine einzelne nachfolgende neue Zeile hinzugefügt werden. Führende oder nachfolgende Bits oder Zeichen können nicht vor oder nach jedem Quintett hinzugefügt werden, dh, Sie können nicht jedes Quintett mit 8 Bits auffüllen (oder jedes Quintett als einzelne Zahl in einem Array annehmen - es sei denn, Ihre Sprache hat einen 5-Bit-Integer-Typ) oder separat Quintette mit zusätzlichen Bits, z "01111\n11100".

Notizen & Rand Fällen

  1. Die Übertragung enthält nur die Zeichen in den Spalten "Ltr" und "Fig" in der obigen Tabelle. Sie werden zB 01110im Figurenmodus nie empfangen , da es in der "Fig" -Spalte fehlt.

  2. Es wird davon ausgegangen, dass sich der Decoder zu Beginn einer Übertragung immer im Letter-Modus befindet. Das erste Zeichen kann jedoch ein FS-Zeichen sein, um sofort in den Figurenmodus zu wechseln.

  3. Wenn sich der Decoder im Buchstabenmodus befindet, kann er ein LS-Zeichen empfangen, und wenn er sich im Figurenmodus befindet, kann er ein FS-Zeichen empfangen. In beiden Fällen muss ein Leerzeichen gedruckt werden (siehe Ausgabe).

  4. Das ER-Zeichen ist niemals das erste Zeichen in einer Übertragung und folgt niemals unmittelbar einem LS, FS oder einem anderen ER.

  5. Ein FS-Zeichen kann unmittelbar auf ein LS-Zeichen folgen und umgekehrt.

  6. Weder das LS- noch das FS-Zeichen ist das letzte Zeichen in einer Übertragung.

  7. Die /und -Zeichen kann in jedem Textmodus (Codes empfangen werden 11000und 10001, jeweils) oder Fig Modus ( 10111 und 00111).

Ausgabe

Die Ausgabe kann in jedem vernünftigen Format erfolgen, wobei ASCII (oder UTF-8, bei dem alle dargestellten Zeichen mit ASCII identisch sind) am vernünftigsten ist. Bitte geben Sie in Ihrer Antwort an, ob Ihre Ausgabe in einer anderen Codierung oder einem anderen Format vorliegt.

Anmerkungen

  • Das Leerzeichen (siehe 3. oben) sollte ein ASCII-Leerzeichen (0x20) oder das Äquivalent Ihrer Kodierung sein, dh was Sie erhalten, wenn Sie die Leertaste drücken.

Gewinnen

Das ist . Der kürzeste Code in Bytes gewinnt.

Beschränkungen

  • Standardlücken sind verboten.

  • Nachgestellte Leerzeichen und / oder eine einzelne nachgestellte Zeile sind zulässig. Führende Leerzeichen oder andere Zeichen (die nicht Teil der Übertragung sind) sind nicht zulässig.

  • Sie dürfen keine eingebauten oder Bibliotheksfunktionen verwenden, die Baudot-Code (oder einen seiner Nachkommen, z. B. Murray-Code, ITA-1 usw.) dekodieren.

Testfälle

Input: 001101000010100111101110010101
Output: BAUDOT
Input: 11010010001001100011110111101111100
Output: HELLO
Input: 01011100000010000001000101000011100000011010111010
Output: MAY 15TH
Input: 0001000100010000001000001011101110011100101010010110101010001111100101
Output: 32 FOOTSTEPS
Input: 10110000110101011100111100001111011010000001101110
Output: GOLF
Input: 000100011000001111100000100010110111001100010110010000111111
Output: 8D =( :P
Input: 0000100001000010000100010001111011111011000011100010001
Output (4 leading spaces):     -/=/-
Jordan
quelle
Verbunden.
Jordanien
1
Hinweis: Ich habe die Testfälle von Hand codiert. Wenn Sie etwas sehen, das falsch aussieht, melden Sie sich bitte.
Jordanien
1
In der Codetabelle und der damit verbundenen Digest, Code 00010als aufgelistet SPim Buchstabenmodus und FSin Figur Modus. Laut Beschreibung sollten wir, wenn wir uns im Buchstabenmodus befinden und Code erhalten 00010, in den Zahlenmodus wechseln, aber die Werte in der Tabelle scheinen umgekehrt zu sein. Auch umgekehrt für 00001.
Sok
3
Dieser Mann war verdammt schlau, ich wusste nie über die Kompression in der Telegraphie. Danke für die Geschichtsstunde Mann.
Magic Octopus Urn
4
@carusocomputing Richtig? Baudot hatte über die Grundschule hinaus keine formale Ausbildung, sondern erfand nicht nur den Baudot-Code, sondern auch ein Multiplexsystem, mit dem vier Betreiber gleichzeitig eine einzige Telegraphenleitung nutzen konnten. Ich fand diese Broschüre von 1919, die seine Erfindungen ausführlich beschreibt, sehr interessant: samhallas.co.uk/repository/telegraph/b6_baudot_multiplex.pdf
Jordan

Antworten:

6

Pyth, 98 97 95 93 90 83 80 Bytes

Der Code enthält nicht druckbare Zeichen. Hier ist ein umkehrbarer xxdHexdump:

00000000: 753f 7133 4a69 4832 5047 2b47 3f3c 334a  u?q3JiH2PG+G?<3J
00000010: 4040 6332 2e22 275a 75ae 5751 fb4e 3cd7  @@c2."'Zu.WQ.N<.
00000020: 02ce 8719 aac1 e0e0 fe1f 09e5 85bc a767  ...............g
00000030: 8e0c 1f47 508a cad1 1acb b26f 951e e5d6  ...GP......o....
00000040: 225a 4a2a 5c20 715a 3d5a 744a 637a 356b  "ZJ*\ qZ=ZtJcz5k

Probieren Sie es online aus. Testsuite.

Ziemlich lang, aber die Nachschlagetabelle belegt fast die Hälfte des Speicherplatzes.

Für 117 Bytes gilt dasselbe ohne nicht druckbare Dateien (benötigt jedoch ISO-8859-1):

u?q3JiH2PG+G?<3J@@c2."'Zu®WQûN<×\x02Î\x87\x19ªÁààþ\x1f\tå\x85¼§g\x8e\x0c\x1fGP\x8aÊÑ\x1a˲o\x95\x1eåÖ"ZJ*\ qZ=ZtJcz5k

Oder für 93 Bytes ohne Komprimierung in der Nachschlagetabelle:

u?q3JiH2PG+G?<3J@@c2"OVDPYSBREXGMIWFNA-JKUTCQ/ZHL5'0+3;8-2;7);?;;1.6(4;9/;:;="ZJ*\ qZ=ZtJcz5k
PurkkaKoodari
quelle
5

JavaScript (ES6), 160 158 153 Byte

let f =
    
s=>s.replace(/.{5}/g,s=>(n='0b'+s-1)<2?m-n?(m^=1,''):' ':"? !YSBREXGMIWFNA-JKUTCQ/ZHLOVDP? ?!3 8-2 7) ?  1.6(4 9/ : =5'0+"[n+m*32],m=0).replace(/.!/g,'')

console.log(f("001101000010100111101110010101"));
console.log(f("11010010001001100011110111101111100"));
console.log(f("01011100000010000001000101000011100000011010111010"));
console.log(f("0001000100010000001000001011101110011100101010010110101010001111100101"));
console.log(f("10110000110101011100111100001111011010000001101110"));
console.log(f("000100011000001111100000100010110111001100010110010000111111"));
console.log(f("0000100001000010000100010001111011111011000011100010001"));

Arnauld
quelle
5

Batch, 306 304 Bytes

@echo off
set/pc=
set r=
set d=! !!YSBREXGMIWFNA-JKUTCQ/ZHLOVDP!! !3!8-2!7)!?!!1.6(4!9/!:!=5'0+
set s=2
:l
set/an=(s^&32)+0%c:~,2%%%6*8+0x%c:~2,3%%%14
set c=%c:~5%
if %n%==%s% set/as^^=35&goto l
call set r=%%r%%%%d:~%n%,1%%
if %r:~-1%==! set r=%r:~,-2%&goto l
if not "%c%"=="" goto l
echo %r%

Übernimmt die Eingabe für STDIN. Da Batch keine Binärkonvertierung hat, muss ich es mit Oktal- und Hex-Konvertierung vortäuschen.

  • Die ersten beiden Ziffern werden von Oktal konvertiert (ich kann keine Dezimalzahl verwenden, da die erste Ziffer möglicherweise ist 0). Mögliche Werte sind 00, 01, 10und 11. Die beiden letzteren haben Wert 8und 9ich will 2oder aber3 so nehme ich den Rest modulo 6.
  • Die letzten drei Ziffern werden hexadezimal konvertiert. Ziffern sind entweder 14oder 252mal ihr gewünschter Wert, bis ich den Rest modulo 14( 252=14*18) nehme .
  • c ist die codierte Zeichenfolge
  • r ist das Ergebnis bisher
  • d ist das Dekodierungsarray
  • s ist der Index (unter Berücksichtigung des Umschaltzustands) des Zeichens, das den Umschaltzustand umschaltet
  • nist die binäre Dekodierung plus Bit 5 von s, das entweder dem Verschiebungszustand entspricht, in welchem ​​Fall der Verschiebungszustand umgeschaltet wird, oder in das Dekodierungsarray indiziert wird, um das nächste Zeichen zu finden (oder! zu löschen).
Neil
quelle
3

PHP, 206 Bytes

foreach(str_split($argv[1],5)as$s)($k="# f*YSBREXGMIWFNA-JKUTCQ/ZHLOVDP#l *3#8-2#7)#?##1.6(4#9/#:#=5'0+"[32*$f+bindec($s)])=="*"?array_pop($a):($k=="f"?$f=1:($k=="l"?$f=0:($k=="#"?:$a[]=$k)));echo join($a);
Jörg Hülsermann
quelle
2

Chip , 1069 Bytes

Es ist ein Riesenerfolg, aber es hat Spaß gemacht zu schreiben.

Nimmt Eingaben als Zeichenfolge von "1"'s und "0"' s. (Obwohl es wirklich nur auf das niedrige Bit aussieht.)

 AZZZZ,-o.AZZZZ  AZZZZ,o-.AZZZZ
*\\\\\]oo[\/\\\**//\\\]oo[/\\\\*
*\\\\/]oo[\/\\/**//\\/]oo[/\\\/*
*\\\//]oo[\/\//**//\//]oo[/\\//*
*\\\/\]oo[\/\/\**//\/\]oo[/\\/\*
*\\//\]oo[\///\**////\]oo[/\//\*
*\\///]oo[\////**/////]oo[/\///*
*\\/\/]oo[\//\/**///\/]oo[/\/\/*
*\\/\\]oo[\//\\**///\\]oo[/\/\\*
=
        o--------K-----o
      ,oo.   z---+~S  ,oo.
     ,LooR. !ZZZZ'   ,LooR.
    ,LLooRR.        ,LLooRR.
   ,LLLooRRR.      ,LLLooRRR.
  ,LLLLooRRRR.    ,LLLLooRRRR.
 ,LLLLLooRRRRR.  ,LLLLLooRRRRR. ,~Z
,LLLLLLooRRRRRR.,LLLLLLooRRRRRR.>m'
|||||||oo||||||||||||||oo||||||)/Rz.
xxxxxxxxxxxxxxx)xxxxxxxxxxxxxxxx\^-^S
x)x))))))))))))xx)))))))))))))xx\g
xx)xxxxxxxxxxxxxxxxxxxxxxxxxxx))\f
xxxxxx))xxxxxxxxxxxxx)))))))))xx\e
xx)x))x)xxxxx))x)))))xxxxxxx)))x\d
xx))x))xxx)))xxxxx)))xxxx)))xx)x\c
xx)xx)xx))x))x)xx)xx)xx))x))x)xx\b
x)))))))x)xx)xxxx)x)xx)x)xx)xx)x\a
x)x)x))))))x)x))x)))x)))xx))x))x/f
x)x)x))))))x)x)xxx)xxxxxxxx)x)xx/e
xxxxxxxx))xxxxxx))))x)))xxx)x))x/d
xxxxx))xxxxx)x)xxx)xxx))xx))xx)x/c
xxx)xxx)xxxx)x)xxxxxx))xxx))x))x/b
x)xxx)x)x)xx)xxxxx))x)))xx))xxxx/a

Probieren Sie es online!

Hinweis: Beim Löschen wird das ASCII-Backspace-Zeichen ( \x08) verwendet, was bedeutet, dass sie in TIO lustig aussehen, in xterm jedoch gut aussehen.

Grundstruktur

Oben über der =Zeile befindet sich der Eingangsdecoder. Der Eingang wird in eines von 32 separaten Signalen umgewandelt. Diese werden von ooben =nach unten gesendet .

Die dreieckigen Berge von L's und R' s drehen das Muster einfach von getrennten Zeilen zu Spalten. Das Raster darunter übersetzt jede Spalte in ihr Ausgabezeichen. Für unbekannte Signale wird NUL ( \x00) erzeugt. Anstatt ein Zeichen zu drucken, ändert der kleine Fleck rechts den Modus für die Sonderverschiebungen.

Das Seilbahn-ähnliche Ding zwischen den beiden Bergen unterdrückt jegliches Drucken zwischen jedem Quintett, andernfalls würde dies versuchen, auch alle überlappenden Quintette zu decodieren. Versuchen Sie, das !durch ein Leerzeichen zu ersetzen , um dies selbst zu sehen. (Das Ausführen im ausführlichen Modus -vkann auch hier von Interesse sein.)

Ich bin mir nicht sicher, wie ich das im Moment verkleinern soll. es ist schon ziemlich dicht für seine Größe.

Phlarx
quelle
0

GNU sed, 334 + 1 = 335 Bytes

+1 Byte für -rFlag. Übernimmt die Eingabe für STDIN.

Als ich über alte Herausforderungen nachdachte, wurde mir klar, dass diese mit sed ziemlich einfach und gut zum Üben sein würden. Ich habe keine Komprimierung versucht, daher besteht die Nachschlagetabelle aus mehr als der Hälfte des Codes.

s|.*|#@&;01000E211000/%00100Y310100U401100I%11100O500010f 10010J601010G711010H%00110B810110C901110F%00001 l10001-.01001X%11001Z:00101S%10101T%01101W?11101V'00011<<10011K(01011M)11011L=00111R-10111Q/01111N%11111P+10000A111110D0|
:
s/@([01]{5})(.*;.*\1)(..)/\3@\2\3/
t
s/@;.*//
s/#f /@/
s/@ l/#/
s/#(.)./\1#/
s/@.(.)/\1@/
t
s/.<|[#@]//g

Probieren Sie es online!

Erläuterung

Der Code funktioniert in zwei Phasen: Erstens ersetzt er jede Folge von 5 Binärziffern durch die entsprechenden zwei Zeichen (Buchstaben und Zahlen) aus einer Nachschlagetabelle. Die Nachschlagetabelle hat das Format 𝟎𝟎𝟎𝟎𝟎𝐋𝐅𝟎𝟎𝟎𝟎𝟎𝐋𝐅… wobei 𝟎 eine Binärziffer ist und 𝐋 ​​und 𝐅 der entsprechende Buchstabe bzw. die entsprechende Ziffer sind. %steht für fehlende Zeichen (dies kann jedes andere Zeichen als Newline sein). FS/SPwird vertreten durch f<space>und SP/LSist <space>l. ERwird vertreten durch <<.

Dann durchläuft es jedes Paar mit einem "Cursor", der dem aktuellen #Modus entspricht - für den Buchstabenmodus, @für den Zahlenmodus . Der #Cursor entfernt das zweite Zeichen des Paares und rückt dann zum nächsten Paar vor, und der Cursor entfernt @das erste und rückt vor. Mit anderen Worten #A1B8wird A#B8und dann AB#und @A1B8wird 1@B8und dann 18@. Wenn der #Cursor auf f<space>ihn trifft, wird er gelöscht und durch den @Cursor ersetzt, und umgekehrt, wenn er auf ihn @trifft <space>l.

Wenn keine Paare mehr vorhanden sind, wird der letzte Cursor zusammen mit den nachfolgenden Zeichen entfernt <.

# Setup: Append a lookup table to the line.
# Also prepends "#" and "@" which we'll use as "cursors" later.
s|.*|#@&;01000E211000/%00100Y310100U401100I%11100O500010f 10010J601010G711010H%00110B810110C901110F%00001 l10001-.01001X%11001Z:00101S%10101T%01101W?11101V'00011<<10011K(01011M)11011L=00111R-10111Q/01111N%11111P+10000A111110D0|

# Phase 1
:
  # Using "@" as a "cursor", substitute for each run of 5 binary digits the
  # two corresponding characters from the lookup table.
  s/@([01]{5})(.*;.*\1)(..)/\3@\2\3/
  t   # Loop (branch to `:`) as long as substitutions are made.

s/@;.*//       # Delete the "@" and lookup table

# Phase 2
s/#f /@/       # FS (f ) in letter mode (#); delete and switch to figure mode (@ cursor).
s/@ l/#/       # LS ( l) in figure mode (@); delete and switch to letter mode (# cursor).
s/#(.)./\1#/   # Letter mode; replace pair with first of pair; advance cursor.
s/@.(.)/\1@/   # Figure mode; replace pair with second of pair; advance cursor.
t              # If any substitutions were made, branch (loop) to `:`.

# Teardown
s/.<|[#@]//g   # Delete characters followed by < (ER) and cursor.
Jordan
quelle