Übertragen einer Datei über Stift und Papier mit Fehlerkorrektur

Question

Übertragen einer Datei über Stift und Papier mit Fehlerkorrektur

2145

Jeremy Salwen 2012-04-22 в 20:31

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

Dies ähnelt Paperbak etwas, mit der Ausnahme, dass die Dichte, nach der ich suche, viel niedriger ist und ich keinen Drucker oder Scanner verwenden möchte.

Natürlich ist die erste Antwort die Base64- Codierung. Das Schreiben und Lesen einer so großen Anzahl von Zeichen führt jedoch zu Fehlern. Für meine Zwecke ist jeder Fehler inakzeptabel.

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

Gibt es ein Programm, das willkürliche Dateien mit einfügbaren / löschbaren Fehlern korrigierenden Code codiert / decodiert? Vorzugsweise sollte es unter Windows, Linux und Mac OS X funktionieren

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

22

Erwarten Sie Fehler beim Schreiben oder Lesen? Christian Mann vor 12 Jahren 0

Ich erwarte Fehler in beiden, aber ich würde auch erwarten, dass sie gleichwertig sind ... Jeremy Salwen vor 12 Jahren 0

Oh, Entschuldigung. Ich habe falsch gelesen und dachte, Sie drucken. Sie wollen es von Hand schreiben? Christian Mann vor 12 Jahren 0

ja, von Hand (Zeichenbegrenzung mit dieser parathentischen Bemerkung) Jeremy Salwen vor 12 Jahren 0

Wie viele Daten möchten Sie auf diese Weise verschlüsseln? Um Kopierfehler zu minimieren, müssen Sie die Daten mit einfach zu identifizierenden alphanumerischen Zeichen codieren. Das bedeutet, dass Sie mindestens 2 Zeichen verwenden müssen, um jedes Byte darzustellen. Angenommen, Sie können 400 Wörter pro Seite mit einer durchschnittlichen Wortlänge von 5 Zeichen einfügen. Auf einem Blatt A4-Papier werden nur etwa 1 KB Daten angezeigt. Die durchschnittliche Person kopiert bei 22 Wörtern (110 Zeichen) pro Minute. Es würde also etwa 18 Minuten dauern, um 1 KB Daten zu kopieren, oder etwa 13 Tage (kein Schlaf), um 1 MB Daten zu kopieren. Und das ist ohne Fehlerkorrektur. Lèse majesté vor 12 Jahren 0

Wie viele Stiftfarben kann ich verwenden? :) Der Hochstapler vor 12 Jahren 3

Nur ein einfarbiger Stift, sonst wird das Abschrift zu schwierig. Ich übertrage tatsächlich komprimierten, signierten, verschlüsselten Text. Wenn Sie also sogar eine Redundanz von 50% annehmen, wird der gesamte Schreibaufwand <1,5-mal so hoch sein wie der ursprüngliche Text (wenn Sie die Komprimierung in Betracht ziehen) ). 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 von kb. Jeremy Salwen vor 12 Jahren 1

Hmmm, ich habe tatsächlich einen kleinen Test mit einem Aufsatz von mir gemacht. Ursprünglicher Aufsatz: 14.116 Bytes => nanozip komprimiert: 4.118 Bytes => base64 codiert: 5565 Bytes. Bei fast 50% Redundanz haben wir immer noch die Anzahl der zu kopierenden Zeichen in * half * reduziert. Wenn Sie keine Zeichen kopieren möchten, sondern Text kopieren möchten, erhöht die stenografische Kodierung mithilfe von http://www.fourmilab.ch/javascrypt/stego.html die Größe immer noch um etwa den Faktor vier. So bleibt uns ein Essay, der nur doppelt so groß ist wie unser Original. Ziemlich gut, oder? Jeremy Salwen vor 12 Jahren 0

5 Antworten auf die Frage

4

2

Dour High Arch 2012-05-02 в 18:47

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

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

Danke, ich werde das wahrscheinlich verwenden, aber das Fehlerbehebungsproblem wird dadurch immer noch nicht gelöst. Jeremy Salwen vor 12 Jahren 0

@Jeremy, Crockfords Implementierung beinhaltet Fehlererkennung *. Wenn Sie Fehler korrigieren müssen, überprüfen Sie die Forward-Error-Korrektur (http://en.wikipedia.org/wiki/Forward_error_correction). Dour High Arch vor 12 Jahren 0

1

Lèse majesté 2012-04-23 в 19:24

Nach dem Lesen Ihrer Kommentare klingt das vernünftiger. Ich war mir nur nicht sicher, ob Sie Megabytes an Daten wie diese kodieren wollten.

Im Sinne von Olivers Vorschlag empfehle ich Ihnen, Ihre Datendichte zu erhöhen, indem Sie sich eine Seite aus Bacons Chiffre leihen, die von Gefängnisbanden häufig verwendet wird, um versteckte Nachrichten in Missiven zu verschlüsseln, die in zwei verschiedenen Skriptstilen geschrieben sind. Kleinbuchstaben oder Druck- oder Kursivzeichen, z

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

Da Ihr Ziel jedoch keine Stegnographie ist, können Sie dies einfach verwenden, um Ihren Glyphensatz zu erweitern. Auf diese Weise könnten Sie bis zu 114 Glyphen verwenden, die nur alphanumerische Druck- und Kursivzeichen verwenden, oder 12996 Codepunkte, die die Kodierung mit zwei Zeichen verwenden.

Da jedoch alle Glyphenzahlen von mehr als 15 und weniger als 256 im Wesentlichen für eine gerade Verschlüsselung binärer Daten gleich sind (dh, Sie benötigen immer noch 2 Zeichen, um jedes Byte darzustellen, so dass Sie eine Datendichte von 4 Bits pro Zeichen 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 aus den 256 am einfachsten zu lesenden / schreibenden Zeichenkombinationen. Wenn eine andere Zeichenkombination auftritt, wissen Sie, dass es sich um einen Kopierfehler handelt.
Verwenden Sie zwei Versionen des Endzeichens als Paritätsbit.
Erstellen Sie 50 verschiedene 16-stellige Glyphensätze. Sie können sie dann verwenden, um Fehlerkorrekturdaten zu verschlüsseln.

ZB bedeutet, die nächsten 3 Nibbles gleich 0x000, gleich 0x001usw.

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 die kodierte Datenlänge zu erhöhen.

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

Implementieren Sie die Kodierung mit variabler Breite, indem Sie 98 Einzelzeichen-Codepunkte 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 Kombinationen von Glyphensätzen verwenden, um wiederholte Halbbytes / Bytes darzustellen. ZB Ab= aba; aB= abab; AB= ababab...
Verwenden Sie die zusätzlichen Glyphen oder Code-Punkte, um "Wörter" und "Phrasen" darzustellen, die in Ihren Daten wiederholt werden. Obwohl vorkomprimierte Daten wahrscheinlich einen hohen Entropiepegel aufweisen, weiß ich nicht, wie effektiv dies wäre.

Um Kopierfehler weiter zu reduzieren, würde ich den kodierten Inhalt in Gitternetzlinien anzeigen und auf Grafikpapier kopieren. Wenn Sie ein benutzerdefiniertes stationäres Gerät mit abwechselnden Spalten- / Zeilenfarben oder ein Schachbrettmuster im Schachbrettstil mit mit Buchstaben versehenen Spalten und nummerierten Zeilen für schnelle Suche verwenden können, würde dies die Kopiergenauigkeit weiter erhöhen.

Sie können auch ein abwechselndes Rasterlayout mit abwechselnden Zeichenstilen kombinieren, um die Fehlererkennung zu erleichtern. Das heißt, wenn ungerade Spalten immer großgeschrieben werden, wenn der Transcriber Kleinbuchstaben in ungeraden Spalten schreibt, wissen sie, dass sie einen Fehler gemacht haben, und können nachverfolgen, wo der Fehler aufgetreten ist.

Wenn Ihre Hauptpriorität auf Genauigkeit gerichtet ist, würde ich eine binäre Codierung + Hamming-Code verwenden . Wenn Sie einen (12, 8) gekürzten Hamming-Code auf Standard-Grafikpapier verwenden, passen Sie möglicherweise nur 187 Byte an und kodieren dabei nur 124 Byte. Es könnte jedoch sehr schnell transkribiert werden (ein Schrägstrich für 1, nichts für 0) und eine einzelne Fehlerkorrektur ermöglichen. Das Anpacken eines zusätzlichen Paritätsbits (13, 8) würde SECDED (Einzelfehlerkorrektur, Doppelfehlererkennung) bereitstellen. Bei Verwendung eines Standard-Hamming-Codes wie (15, 11) oder (31, 26) erzielen Sie mit 137 bzw. 156 Byte Daten pro Blatt eine noch bessere Effizienz. Je nachdem, wie genau Sie glauben, dass Ihr Transkription für Sie geeignet ist, können sogar noch höhere Codierraten erzielt werden.

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

Natürlich plane ich auch, Großbuchstaben zu verwenden. Von allen 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 für den Fehlerkorrekturschutz für Dateien? Vielleicht hätte ich auch erwähnen sollen, dass das Erstellen von benutzerdefinierten Programmen auch höchst unerwünscht ist? Ich kann anscheinend kein Programm finden, das Ihre Dateien lediglich mit fehlerkorrigierenden Codes schützt. Jeremy Salwen vor 12 Jahren 0

Es ging mir nicht nur darum, Großbuchstaben zu verwenden, sondern auch verschiedene Skripte / Schriften. Wenn Sie nur alphanumerische Groß- und Kleinbuchstaben verwenden, haben Sie nur 62 Glyphen oder 3844 Codepunkte. Sie können mehr als das Dreifache dieser Menge an Codepunkten erhalten, indem Sie zwei Skripts verwenden und dabei 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 nutzen möchten, gibt es viele Dateiformate, die die Fehlerkodierung implementieren. Die meisten Archiv- / Komprimierungsformate haben eine eingebaute Fehlerkorrektur. Lèse majesté vor 12 Jahren 0

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ärer Daten in handschriftlichem Text / Markierungen gedacht. Sie würden sie nicht auf dem Computer so speichern (Sie können ein gescanntes Bild nicht nur speichern). Grundsätzlich haben Sie ein Programm zum Kodieren der Daten, wobei ein Bild auf dem Bildschirm ausgegeben wird, damit der Benutzer es kopieren kann. Um es dann wieder auf einen Computer zu übertragen, würden Sie ein Dekodierungsprogramm verwenden, das entweder das gescannte Bild als OCR / OMR verwendet oder die Eingabe über die Tastatur akzeptiert (z. B. `alt` +` a` für kursives "a"). Lèse majesté vor 12 Jahren 0

Das ist, was ich habe das Problem mit: "Sie hätten ein Programm, um die Daten zu verschlüsseln" ... nein, ich nicht. Ich habe kein Programm, um dies zu tun, und ich kenne kein Programm, um dies zu tun. Ich kenne auch kein Dateiformat, das ein Byte *, das entfernt * (nicht gelöscht) ist, nahe dem Anfang der Datei und anderen Fehlern ordnungsgemäß verarbeiten kann. Ich stimme definitiv zu, dass dies Methoden zum Erhöhen der Datendichte sind, aber das ist jetzt nicht mein Hauptanliegen, da es einfach zu lesen / schreiben ist und Fehlerschutz bietet. Jeremy Salwen vor 12 Jahren 0

@Jeremy: Wie gesagt, die meisten Archivformate haben eine eingebaute Fehlerkorrektur, die für die meisten Leute gut zu funktionieren scheint. Wenn Sie jedoch etwas speziell für die Transkription von Hand entwickeltes Material benötigen, müssen Sie schreiben oder jemanden etwas für Sie schreiben lassen. Ansonsten ist es am besten, wenn Sie sich die vorhandenen Anwendungen ansehen, die für die Übertragung über Kanäle mit hohem Rauschen ausgelegt sind. Die einfachste Option ohne Bedenken hinsichtlich der Datendichte besteht jedoch darin, einfach eine RAR-Datei mit einem hohen Maß an Fehlerkorrektur zu verwenden und den Kopfabschnitt dreimal zu wiederholen, um dreifach modulare Redundanz zu erhalten. Lèse majesté vor 12 Jahren 0

Die einzigen Werkzeuge, die Sie dazu benötigen, sind ein RAR-Programm wie WinRAR und ein Hex-Editor wie Frhed. Lèse majesté vor 12 Jahren 0

Ich habe eine 28K-RAR-Datei erstellt. Wiederherstellungs-Volumes mit> 50% Recovery-Volumes hinzugefügt. Base64 hat es verschlüsselt. Sechs Zeichen aus dem Inhalt gelöscht und zwei hinzugefügt. Base64 hat es entschlüsselt. rar konnte die Datei NICHT wiederherstellen. Das ist für jede Art von Verwendung, die ich beschrieben habe, völlig inakzeptabel. Ich bin mir nicht sicher, was "gut genug für die meisten Leute" ist, aber wenn es eine Fehlerrate von 0,02% mit> 50% Redundanz nicht korrigieren kann, dann ist es sicherlich nicht gut genug für mich. Es ist mir egal, ob es etwas ist, das speziell für die Transkription von Hand entwickelt wurde, aber ja, meine Frage ist, was kann ich verwenden, um * zu funktionieren *. Jeremy Salwen vor 12 Jahren 0

1

Retired Spy 2014-02-16 в 01:55

Zu diesem Zweck haben wir S-Records verwendet. Pro Zeile gab es eine einfache Prüfsumme zur Fehlererkennung. Normalerweise waren alle, außer der letzten Zeile, feste Länge, daher diente der Zeilenende-Marker zur Prüfung auf Einfügungen und Löschungen. Es wurde jedoch keine Überprüfung auf fehlende Zeilen durchgeführt. Dafür 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 langwierig, Dateien in das System einzugeben. Natürlich war unter den ersten Programmen, die auf diese Weise übertragen wurden, ein Downloader;)

0

Dour High Arch 2012-04-29 в 16:10

Die optische Markierungserkennung wird seit Jahrzehnten zur Erstellung maschinenlesbarer handgeschriebener Formulare verwendet. Die Wikipedia-Seite enthält Links zu mehreren Open Source-Versionen.

Schulen haben OMR schon lange zum Testen verwendet; Die Formulare sind einfach zu verwenden und zu lesen, und die Genauigkeit ist normalerweise besser als die Tastatureingabe. Kommerzielle Hersteller wie Scantron und ReMark können für eine höhere Genauigkeit benutzerdefinierte Formulare erstellen.

Das ist interessant, leider erfordert dies einen Scanner oder ein anderes Bildgebungssystem, das an den Computer angeschlossen ist. Jeremy Salwen vor 12 Jahren 0

Accepted Answer · 2012-04-23 07:49:51

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

Nehmen wir an, Sie haben Rot, Grün, Blau und Schwarz. Sie können ein Skript schreiben, das Ihre Daten in eine Sammlung von Buchstaben umwandelt RGBY, zB: 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 Basiskonvertierung Ihrer Binärdaten von Basis 2 (oder von Hexadezimaldaten von Basis 16) in Basis in der Anzahl der Farben, die Sie verwenden (in diesem Beispiel 4).

Nun, der logischste Ansatz wäre, sich 16 Farben zu holen. Auf diese Weise müssen Sie viermal weniger Punkte verwenden, was das Wechseln zwischen den Stiften lohnt. Auf diese Weise können Sie 4-mal so viele Daten auf das Papier schreiben, wenn Sie dies tun müssen oder vielleicht 4-mal weniger genau sind, wenn Sie Ihre Punkte setzen. Die Skalierung liegt bei Ihnen. Ich würde wirklich davon abraten, jedes einzelne Stück zu zeichnen.

Müsste 5565 byteszum Beispiel mit zwei multipliziert werden, um die Anzahl der Hexadezimalzahlen zu erhalten, die 11130 hexadecimals(im Gegensatz zu 44520 bits) in ein 106 x 106Raster eingefügt werden können.

Abhängig von der Art der Daten können Sie wahrscheinlich einige Optimierungen mit sich bringen ...

Hinweis: 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 durch eine kleine Pixelschrift dar, siehe meinen Avatar.

Dies macht es sogar nützlich, so etwas wie Base 32 (oder Base 36) zu verwenden. Beachten Sie, dass das Qund 9das Gleiche sind, daher sollten Sie den oberen rechten Pixel des QWeiß als klare Unterscheidung wählen. Die Basis 32 erfordert nur ein 53 x 53Raster für Ihr Beispiel und einen kleinen Abstand, um zwischen den Buchstaben zu unterscheiden.

Übertragen einer Datei über Stift und Papier mit Fehlerkorrektur

5 Antworten auf die Frage

Verwandte Probleme