So übertragen Sie eine Datei mit Fehlerkorrektur über Stift und Papier

22

Ich suche nach einer Möglichkeit, eine Datei nur mit Stift und Papier zu übertragen.

Dies ähnelt in gewisser Weise dem Paperbak , außer dass die gesuchte Dichte viel, viel niedriger ist und ich keinen Drucker oder Scanner verwenden möchte.

Offensichtlich lautet die erste Antwort Base64- Codierung. Das Schreiben und Lesen einer derart hohen Anzahl von Zeichen führt jedoch zwangsläufig zu Fehlern. Für meine Zwecke ist jeder Fehler inakzeptabel.

Die zweite Antwort könnte eine Reed-Solomon-Fehlerkorrektur sein (z. B. mit rsbep ). Dies ist jedoch auch ein Problem, da Reed-Solomon-Codes meines Wissens keine Einfüge- / Löschfehler korrigieren, die in diesem Fall wahrscheinlich wahrscheinlicher sind als Substitutionsfehler.

Gibt es ein Programm, das beliebige Dateien mit einfüge- / löschsicheren Fehlerkorrekturcodes codiert / decodiert? Vorzugsweise sollte es unter Windows, Linux und Mac OS X funktionieren

Natürlich ist jede andere Lösung des allgemeinen Problems willkommen.

Jeremy Salwen
quelle
Erwarten Sie Fehler beim Schreiben oder beim Lesen?
Christian Mann
Ich erwarte Fehler in beiden, aber ich würde auch erwarten, dass sie gleichwertig sind ...
Jeremy Salwen
Oh, Entschuldigung. Ich habe falsch verstanden und dachte, Sie würden drucken. Sie möchten es von Hand ausschreiben?
Christian Mann
3
Wie viele Farben von Stiften kann ich verwenden? :)
Der Hochstapler
1
Nur ein einziger Farbstift, sonst wird es zu schwierig sein, ihn zu transkribieren. Ich übertrage tatsächlich komprimierten, signierten und verschlüsselten Text. Unter der Annahme einer Redundanzrate von 50% ist die Gesamtschreibmenge also weniger als das 1,5-fache der tatsächlichen Schreibmenge des Originaltexts (wenn Sie die Komprimierung berücksichtigen) ). Es gibt jedoch das Problem, dass das Kopieren von zufälligen Zeichen schwieriger ist als das Kopieren von englischem Text. Also um deine Frage zu beantworten, sicherlich nur im paar kb Bereich.
Jeremy Salwen

Antworten:

4

Ich bezweifle, dass otherwise transcribing it will be too difficultdies ein Problem sein wird.

Angenommen, Sie haben Rot, Grün, Blau und Schwarz. Sie können ein Skript schreiben, das Ihre Daten in eine Sammlung von Buchstaben umwandelt RGBY, z. B .: RGBYGBRYBGBYRYYBYBRYYG(oder sogar Red Green Blue Black Green Blue Red Black...in einer Excel-Tabelle) und wieder zurück. Es ist nur eine Frage der Basis, wie Sie Ihre Binärdaten von Basis 2 (oder Hexadezimaldaten von Basis 16) in die Basis in der Anzahl der Farben konvertieren, die Sie verwenden (in diesem Beispiel 4).

Der logischste Ansatz wäre nun, sich 16 Farben zu sichern. Auf diese Weise müssen Sie viermal weniger Punkte verwenden, wodurch sich das Wechseln zwischen den Stiften lohnt. Auf diese Weise können Sie 4-mal so viele Daten auf das Papier schreiben, wenn dies erforderlich ist, oder es kann sein, dass die Skalierung beim Anbringen Ihrer Punkte 4-mal ungenauer ist. Ich würde wirklich davon abraten, jedes einzelne Bit zu zeichnen.

Müsste 5565 byteszum Beispiel mit zwei multipliziert werden, um die Hexadezimalzahl zu erhalten, die 11130 hexadecimals(im Gegensatz zu 44520 bits) in ein 106 x 106Raster eingefügt werden kann.

Abhängig von der Art der Daten können Sie wahrscheinlich mit einigen Optimierungen kommen ...

Tipp: Versuchen Sie, die deutlichsten (kontrastreichsten) Farben auszuwählen ...

Alternativen, die einen einzelnen Stift verwenden können:

  • Repräsentieren die verschiedenen hexadezimal durch verschiedene Symbole -, /, |, \, +, ...

  • Stellen Sie die verschiedenen Hexadezimalzahlen mit einer kleinen Pixelschrift dar, siehe meinen Avatar.

    Dies macht es sogar nützlich, etwas wie Base 32 (oder Base 36) zu verwenden. Beachten Sie, dass das Qund 9dasselbe ist. Sie möchten also, dass das Pixel oben rechts Qfür eine klare Unterscheidung weiß ist. Basis 32 erfordert nur ein 53 x 53Raster für Ihr Beispiel sowie einen kleinen Abstand zwischen den Buchstaben.

Tamara Wijsman
quelle
Nun, es gibt ein paar Probleme damit. 1. Ich bin farbenblind. 2. Es erfordert den Kauf einer Reihe von Stiften. 3. Es hilft überhaupt nicht bei der Fehlerkorrektur. 4. Es geht darum, Codes anstelle von Text zu schreiben, in denen Menschen schlechter abschneiden.
Jeremy Salwen
@ JeremySalwen: Ähm, Zeichen in ein Raster zu schreiben ist nicht wirklich schwer. Und Sie können Fehler korrigieren, indem Sie einige zusätzliche Längsschnittprüfnummern oder eine CRC schreiben. Aber es ist wirklich sehr einfach, Buchstaben von einem Raster zu einem anderen zu schreiben. Im schlimmsten Fall müssen Sie es nur noch einmal durchgehen, um die Gültigkeit zu überprüfen.
Tamara Wijsman
1
@ JeremySalwen: Und wenn Sie farbenblind sind, nehmen Sie einfach keine der Farben, für die Sie farbenblind sind.
Tamara Wijsman
1
Farbenblindheit ist eher eine Verringerung der Dimensionalität des Farbraums als eine selektive Unfähigkeit, bestimmte Farben zu sehen. Ich meine, ich könnte wahrscheinlich Schwarz, Blau, Gelb, Rot, Grün, Grau abziehen, aber nicht viel mehr
Jeremy Salwen
@ Tom Du solltest wahrscheinlich deinen alten Avatar einbauen, um Verwirrung zu vermeiden :)
Nate Koppenhaver
2

Wenn Sie möchten, dass Benutzer die Daten lesen und schreiben können, besteht das Problem mit Base64 und vielen Textkodierungen darin, dass sie Zeichen wie I, I, 1, |, /, 0, O, O usw. verwenden, die die Benutzer verwirren miteinander.

Untersuchen Sie die Base32- Codierung von Douglas Crockford . Sein Alphabet wurde speziell ausgewählt, um ähnliche Zeichen zu vermeiden, und es enthält eine Fehlererkennung.

Dour High Arch
quelle
Danke, ich werde das wahrscheinlich benutzen, aber es löst immer noch nicht das Problem der Fehlerkorrektur.
Jeremy Salwen
@ Jeremy, Crockfords Implementierung beinhaltet die Fehlererkennung . Wenn Sie Fehler korrigieren müssen, untersuchen Sie die Vorwärtsfehlerkorrektur ( en.wikipedia.org/wiki/Forward_error_correction ).
Dour High Arch
1

Nachdem Sie Ihre Kommentare gelesen haben, klingt dies vernünftiger. Ich war mir nur nicht sicher, ob Sie Megabyte an Daten wie diese codieren wollten.

In Anlehnung an Olivers Vorschlag würde ich empfehlen, dass Sie Ihre Datendichte erhöhen, indem Sie eine Seite aus Bacons Chiffre ausleihen, die Gefängnisbanden häufig verwenden, um versteckte Nachrichten in Missiven zu verschlüsseln, die in zwei verschiedenen Skriptstilen geschrieben sind - normalerweise entweder Upper vs. Kleinbuchstaben oder gedruckte oder kursive Zeichen, z

Hey mOM, WHAT's FOR diNNeR TODAY? = ABBBA AAAAA BAAAB BAABA AAAAA
                                  =   P     A     S     T     A

Da Ihr Ziel jedoch nicht die Stegnographie ist, würden Sie dies einfach zum Erweitern Ihres Glyphensatzes verwenden. Auf diese Weise können Sie bis zu 114 Glyphen nur mit alphanumerischen Druck- und Kursivzeichen oder 12996 Codepunkten mit Doppelzeichencodierung verwenden.

Da jedoch alle Glyphenzahlen größer als 15 und kleiner als 256 für eine direkte Verschlüsselung von Binärdaten im Wesentlichen gleich sind (dh, Sie benötigen immer noch 2 Zeichen, um jedes Byte darzustellen, sodass Sie eine Datendichte von 4 Bit pro Zeichen in erhalten In allen Fällen können Sie die zusätzlichen 98 Glyphen / 12740 Codepunkte zur Fehlererkennung / -korrektur verwenden.

Möglichkeiten, dies zu tun, umfassen:

  • Wählen Sie einen Satz der 256 am einfachsten zu lesenden / zu schreibenden Zeichenkombinationen. Wenn eine andere Zeichenkombination auftritt, liegt ein Kopierfehler vor.
  • Verwenden Sie zwei Versionen des Endzeichens als Paritätsbit.
  • Erstellen Sie 50 verschiedene 16-stellige Glyphensätze. Sie können sie dann zum Verschlüsseln von Fehlerkorrekturdaten verwenden.

    ZB {set 1}{set 1}bedeutet, dass die nächsten 3 Knabbereien gleich 0x000, {set 1}{set 2}gleich 0x001usw. sind.

    Sie können dies verwenden, um 2500+ der 4096 möglichen 1,5-Byte-Werte darzustellen. In ähnlicher Weise könnten Sie nur 16 Sätze verwenden, um alle Werte des folgenden Bytes darzustellen, wodurch Sie 100% Redundanz erhalten, ohne Ihre codierte Datenlänge zu erhöhen.

Alternativ können Sie die zusätzlichen Glyphen für zusätzliche Komprimierung verwenden:

  • Implementieren Sie eine Codierung mit variabler Breite, indem Sie 98 Codepunkte mit einem Zeichen auswählen. Dies würde die durchschnittliche Größe des codierten Inhalts um etwa 20% reduzieren.
  • Implementieren Sie etwas, das der Lauflängencodierung ähnelt, indem Sie verschiedene Glyphensätze oder Glyphensatzkombinationen verwenden, um sich wiederholende Halbbytes / Bytes darzustellen. ZB Ab= aba; aB= abab; AB= ababab...
  • Verwenden Sie die zusätzlichen Glyphen oder Codepunkte, um "Wörter" und "Phrasen" darzustellen, die in Ihren Daten wiederholt werden. Obwohl vorkomprimierte Daten wahrscheinlich ein hohes Maß an Entropie aufweisen werden, weiß ich nicht, wie effektiv dies sein würde.


Um Kopierfehler weiter zu reduzieren, würde ich den codierten Inhalt in Gitternetzlinien anzeigen und auf Millimeterpapier kopieren. Wenn Sie benutzerdefiniertes stationäres Material mit abwechselnden Spalten- / Zeilenfarben oder ein schachbrettartiges Schachbrettmuster mit beschrifteten Spalten und nummerierten Zeilen für eine schnelle Suche verwenden können, wird die Kopiergenauigkeit weiter erhöht.

Sie können auch ein abwechselndes Rasterlayout mit abwechselnden Zeichenstilen als einfache Form der Fehlererkennung kombinieren. Das heißt, wenn ungerade Spalten immer in Großbuchstaben geschrieben werden und der Transkriptor Kleinbuchstaben in ungeraden Spalten schreibt, weiß er, dass er einen Fehler gemacht hat, und kann zurückverfolgen, um zu sehen, wo es passiert ist.


Obwohl, wenn Ihre Hauptpriorität Genauigkeit ist, würde ich eine binäre Kodierung + Hamming Code verwenden . Bei Verwendung eines (12, 8) gekürzten Hamming-Codes auf Standard-Grafikpapier passen Sie möglicherweise nur auf 187 Byte, wobei nur 124 Byte Daten codiert werden. Aber es könnte sehr schnell transkribiert werden (ein Schrägstrich für 1, nichts für 0) und eine einzelne Fehlerkorrektur liefern. Das Anheften eines zusätzlichen Paritätsbits (13, 8) würde SECDED (Einzelfehlerkorrektur, Doppelfehlererkennung) ergeben. Mit einem Standard-Hamming-Code wie (15, 11) oder (31, 26) erzielen Sie mit 137 bzw. 156 Byte Daten pro Blatt eine noch höhere Effizienz. Es können sogar noch höhere Coderaten erzielt werden, je nachdem, wie genau Sie glauben, dass Ihr Transkribent sein kann.

Eine binäre Codierung wäre auch einfacher zu lesen (laut) und OCR / OMR.

Majestätsbeleidigung
quelle
Natürlich plane ich auch, Großbuchstaben zu verwenden. Unter all den von Ihnen vorgeschlagenen Fehlerkorrekturschemata sehe ich keine Möglichkeit, sie zu implementieren, ohne ein benutzerdefiniertes Dateiformat usw. zu entwerfen. Gibt es wirklich keinen Präzedenzfall, um den Fehlerkorrekturschutz auf Dateien anzuwenden? Vielleicht hätte ich auch erwähnen sollen, dass das Erstellen von benutzerdefinierten Programmen ebenfalls höchst unerwünscht ist? Ich kann anscheinend kein Programm finden, das Ihre Dateien nur mit Fehlerkorrekturcodes schützt.
Jeremy Salwen
Ich wollte nicht nur Großbuchstaben verwenden, sondern auch verschiedene Skripte / Schriftarten. Wenn Sie nur alphanumerische Groß- und Kleinbuchstaben verwenden, haben Sie nur 62 Glyphen oder 3844 Codepunkte. Sie können die Anzahl der Codepunkte mit 2 Skripten mehr als verdreifachen, indem Sie das Speichermedium verwenden, das für die Übertragung verwendet wird. Dies war der Zweck meiner Antwort. Wenn Sie die Tatsache, dass es sich um ein geschriebenes Medium handelt, nicht ausnutzen möchten, gibt es zahlreiche Dateiformate, die eine Fehlerkodierung implementieren. In den meisten Archiv- / Komprimierungsformaten ist eine Fehlerkorrektur integriert.
Lèse majesté
Ich bin mir nicht sicher, was Sie mit dem Erstellen neuer Dateiformate meinen. Alle Techniken, die ich erwähnt habe, sind für die visuelle Codierung beliebiger Binärdaten in handgeschriebenen Texten / Marken gedacht. Sie würden sie nicht so auf dem Computer speichern (Sie könnten nicht mehr als ein gescanntes Bild speichern). Grundsätzlich hätten Sie ein Programm, um die Daten zu kodieren und ein Bild auf dem Bildschirm auszugeben, das der Benutzer kopieren kann. Um es dann wieder auf einen Computer zu übertragen, würden Sie ein Dekodierungsprogramm verwenden, das entweder das gescannte Bild mit OCR / OMR erkennt oder die Eingabe über die Tastatur akzeptiert (z. B. alt+ afür kursives "a").
Majestätsbeleidigung
Sehen Sie, das ist es, womit ich ein Problem habe: "Sie hätten ein Programm zum Codieren der Daten" ... nein, das tue ich nicht. Ich habe kein Programm, um dies zu tun, und ich kenne kein Programm, um dies zu tun. Mir ist auch kein Dateiformat bekannt, das ein Byte ordnungsgemäß verarbeiten kann, das - neben anderen Fehlern - vom Anfang der Datei entfernt (nicht gelöscht) wurde. Ich stimme definitiv zu, dass dies Methoden zur Erhöhung der Datendichte sind, aber das ist jetzt nicht mein Hauptanliegen, es ist das einfache Lesen / Schreiben und der Fehlerschutz.
Jeremy Salwen
@ Jeremy: Wie gesagt, in den meisten Archivformaten ist eine Fehlerkorrektur eingebaut, die für die meisten Leute gut genug zu funktionieren scheint. Aber wenn Sie etwas speziell für das Transkribieren von Hand haben möchten, müssen Sie schreiben oder jemanden etwas für Sie schreiben lassen. Ansonsten sollten Sie sich die vorhandenen Anwendungen ansehen, die für die Übertragung über Kanäle mit hohem Rauschen ausgelegt sind. Die einfachste Option, bei der die Datendichte keine Rolle spielt, ist die Verwendung einer RAR-Datei mit einem hohen Grad an Fehlerkorrektur. Wiederholen Sie dann den Header-Abschnitt dreimal, um eine dreifache modulare Redundanz zu erzielen.
Majestätsbeleidigung
1

Zu diesem Zweck haben wir S-Records verwendet. Es gab eine einfache Prüfsumme pro Zeile für die Fehlererkennung. Normalerweise hatten alle Zeilen bis auf die letzte eine feste Länge, daher diente die Zeilenende-Markierung als Kontrolle für Einfügungen und Löschungen. Es wurde jedoch nicht nach fehlenden Zeilen gesucht. Dazu haben wir einfach die Anzahl der Zeilen gezählt. Die meisten Dateien waren kurz, weniger als 100 Zeilen, aber ich erinnere mich an mindestens eine Datei mit 300 Zeilen oder mehr. Es war sehr mühsam, Dateien in das System einzugeben. Natürlich gehörte zu den ersten Programmen, die auf diese Weise übertragen wurden, ein Downloader;)

Pensionierter Spion
quelle
0

Die optische Markenerkennung wird seit Jahrzehnten verwendet, um maschinenlesbare handschriftliche Formulare zu erstellen. Die Wikipedia-Seite enthält Links zu verschiedenen Open Source-Versionen.

Schulen haben OMR lange Zeit zum Testen verwendet. Die Formulare sind einfach zu verwenden und zu lesen, und die Genauigkeit ist in der Regel besser als die Tastatureingabe. Für eine höhere Genauigkeit können kommerzielle Hersteller wie Scantron und ReMark benutzerdefinierte Formulare erstellen.

Dour High Arch
quelle
Das ist interessant, leider erfordert dies einen Scanner oder ein anderes Bildgebungssystem, das an den Computer angeschlossen ist, um zu funktionieren.
Jeremy Salwen