Comment transférer un fichier sur un stylo et du papier, avec correction d'erreurs

22

Je cherche un moyen de transférer un fichier en utilisant uniquement un stylo et du papier.

C'est un peu similaire à paperbak , sauf que la densité que je recherche est beaucoup, beaucoup plus faible et je ne veux pas utiliser d'imprimante ou de scanner.

De toute évidence, la première réponse est le codage Base64 . Mais l'écriture et la lecture d'un si grand nombre de caractères entraîneront inévitablement des erreurs. À mes fins, toute erreur est inacceptable.

La deuxième réponse pourrait être des codes de correction d'erreur Reed-Solomon (par exemple, en utilisant rsbep ). Cependant, c'est aussi un problème, car d'après ma compréhension, les codes Reed-Solomon ne corrigent pas les erreurs d'insertion / suppression, qui sont probablement plus susceptibles que les erreurs de substitution dans ce cas.

Existe-t-il un programme qui encodera / décodera des fichiers arbitraires avec des codes de correction d'erreur sensibles à l'insertion / suppression? De préférence, il devrait fonctionner sur Windows, Linux et Mac OS X

De toute évidence, toute autre solution au problème général est la bienvenue.

Jeremy Salwen
la source
Vous attendez-vous à des erreurs d'écriture ou de lecture?
Christian Mann
Je m'attends à des erreurs dans les deux, mais je m'attends également à ce qu'elles soient équivalentes ...
Jeremy Salwen
Oh pardon. J'ai mal lu et je pensais que vous imprimiez. Vous voulez l'écrire à la main?
Christian Mann
3
Combien de couleurs de stylos puis-je utiliser? :)
Der Hochstapler
1
Une seule plume de couleur, sinon la transcription sera trop difficile. Je transmets en fait du texte compressé, signé et crypté, donc en supposant même un taux de redondance de 50%, le montant total de l'écriture sera <1,5 fois plus que l'écriture réelle du texte d'origine (une fois que vous prenez en compte la compression ). Cependant, il y a le problème que la copie de caractères aléatoires est plus difficile que la copie de texte anglais. Donc, pour répondre à votre question, certainement seulement dans la plage de quelques ko.
Jeremy Salwen

Réponses:

4

Je doute que ça otherwise transcribing it will be too difficultva être un problème.

Disons que vous avez du rouge, du vert, du bleu et du noir. Vous pouvez écrire un script qui transforme vos données en une collection de lettres RGBY, par exemple: RGBYGBRYBGBYRYYBYBRYYG(ou même Red Green Blue Black Green Blue Red Black...dans une feuille Excel) et vice-versa. Il s'agit simplement de convertir vos données binaires de la base 2 (ou les données hexadécimales de la base 16) en base dans la quantité de couleurs que vous prenez (4 dans cet exemple).

Maintenant, l'approche la plus logique serait de vous procurer 16 couleurs. De cette façon, vous devez utiliser 4 fois moins de points, ce qui en vaut la peine. Cela vous permet d'écrire 4 fois plus de données sur le papier si vous en avez besoin, ou peut-être peut-être 4 fois moins précis lorsque vous placez vos points, la mise à l'échelle dépend de vous. Je déconseille vraiment de dessiner chaque bit.

Par exemple, il 5565 bytesfaudrait multiplier par deux pour obtenir la quantité d'hexadécimaux qui est 11130 hexadecimals(par opposition à 44520 bits) qui peut être mise dans une 106 x 106grille.

Selon le type de données, vous pouvez probablement apporter quelques optimisations ...

Astuce: Essayez de choisir les plus distinctes des couleurs (plus contrastées) ...

Alternatives pouvant utiliser un seul stylo:

  • Représenter les différents hexadécimaux par des symboles différents -, /, |, \, +, ...

  • Représentez les différents hexadécimaux par une petite police de pixels, voir mon avatar.

    Cela rend même utile d'utiliser quelque chose comme Base 32 (ou Base 36). Notez que le Qet 9sont les mêmes, vous voudrez donc que le pixel supérieur droit du Qsoit blanc pour une distinction claire. La base 32 nécessite uniquement une 53 x 53grille pour votre exemple, plus un petit espacement pour distinguer les lettres.

Tamara Wijsman
la source
Eh bien, il y a quelques problèmes avec cela. 1. Je suis daltonien. 2. Il faut acheter un tas de stylos. 3. Cela n'aide pas du tout avec la correction d'erreur. 4. Elle implique des codes écrits au lieu de texte, ce qui est pire pour les humains.
Jeremy Salwen
@JeremySalwen: Uhm, écrire des caractères dans une grille n'est pas vraiment difficile. Et vous pouvez corriger les erreurs en écrivant des numéros de contrôle longitudinal supplémentaires ou un CRC. Mais vraiment, il est très facile d'écrire sur des lettres d'une grille à une autre, dans le pire des cas, il suffit de le refaire pour valider.
Tamara Wijsman le
1
@JeremySalwen: Et si vous êtes daltonien, vous ne prenez simplement aucune des couleurs pour lesquelles vous êtes daltonien.
Tamara Wijsman le
1
Le daltonisme est davantage une réduction dimensionnelle de l'espace colorimétrique qu'une incapacité sélective à voir certaines couleurs. Je veux dire, je pourrais probablement retirer noir, bleu, jaune, rouge, vert, gris, mais pas beaucoup plus
Jeremy Salwen
@Tom Vous devriez probablement mettre votre ancien avatar pour éviter toute confusion :)
Nate Koppenhaver
2

Si vous voulez que les gens puissent lire et écrire les données, le problème avec Base64 et de nombreux encodages de texte est qu'ils utilisent des caractères comme I, l, 1, |, /, 0, O, o, etc. avec l'un l'autre.

Examinez le codage Base32 de Douglas Crockford . Son alphabet a été spécialement choisi pour éviter les caractères similaires, et il inclut la détection d'erreurs.

Dour High Arch
la source
Merci, je vais probablement l'utiliser, mais cela ne résout toujours pas le problème de correction d'erreur.
Jeremy Salwen
@Jeremy, l'implémentation de Crockford inclut la détection d' erreurs . Si vous devez corriger des erreurs, étudiez la correction des erreurs directes ( en.wikipedia.org/wiki/Forward_error_correction ).
Dour High Arch
1

Après avoir lu vos commentaires, cela semble plus raisonnable. Je ne savais tout simplement pas si vous aviez l'intention d'encoder des mégaoctets de données comme celui-ci.

Je recommanderais, dans le sens de la suggestion d'Oliver, que vous augmentiez la densité de vos données en empruntant une page au chiffre de Bacon , que les gangs de prison utilisent souvent pour coder les messages cachés dans des missives écrites dans 2 styles de script différents - généralement soit supérieur soit vs. caractères en minuscules ou caractères imprimés ou cursifs, p.ex.

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

Cependant, puisque votre objectif n'est pas la stégnographie, vous pouvez simplement l'utiliser pour étendre votre ensemble de glyphes. Pour ce faire, vous pouvez avoir jusqu'à 114 glyphes en utilisant uniquement des caractères alphanumériques imprimés et cursifs, ou 12996 points de code en utilisant un codage à deux caractères.

Cependant, puisque tous les décomptes de glyphes supérieurs à 15 et inférieurs à 256 sont essentiellement les mêmes pour un chiffrement direct de données binaires (ce qui signifie que vous aurez toujours besoin de 2 caractères pour représenter chaque octet, ce qui vous donne une densité de données de 4 bits par caractère dans tous les cas), vous pouvez utiliser les 98 glyphes supplémentaires / 12740 points de code pour la détection / correction des erreurs.

Les moyens d'y parvenir comprennent:

  • Choisissez un ensemble des 256 combinaisons de caractères les plus faciles à lire / écrire. Si un autre combo de caractères se produit, vous savez que c'est une erreur de copie.
  • Utilisez deux versions du caractère de fin comme bit de parité.
  • Créez 50 ensembles de glyphes de 16 caractères différents. Vous pouvez ensuite les utiliser pour chiffrer les données de correction d'erreur de codage.

    Par exemple {set 1}{set 1}, les 3 grignotages suivants sont égaux 0x000, {set 1}{set 2}égaux 0x001, etc.

    Vous pouvez l'utiliser pour représenter 2500+ des 4096 valeurs possibles de 1,5 octet. De même, vous pouvez utiliser seulement 16 ensembles pour représenter toutes les valeurs de l'octet suivant, vous offrant une redondance de 100% sans augmenter la longueur de vos données codées.

Vous pouvez également utiliser les glyphes supplémentaires pour une compression supplémentaire:

  • Implémentez un codage à largeur variable en choisissant 98 points de code à un caractère. Cela réduirait la taille moyenne du contenu codé d'environ 20%.
  • Implémentez quelque chose de similaire au codage de longueur en utilisant différents jeux de glyphes ou combinaisons de jeux de glyphes pour représenter des grignotages / octets répétitifs. Par exemple Ab= aba; aB= abab; AB= ababab...
  • Utilisez les glyphes supplémentaires ou les points de code pour représenter les "mots" et les "phrases" qui sont répétés dans vos données. Bien que les données précompressées aient probablement un niveau d'entropie élevé, je ne sais pas si cela serait efficace.


Pour réduire davantage les erreurs de copie, j'afficherais le contenu encodé en quadrillage et le copierais sur du papier graphique. Si vous pouvez utiliser des articles fixes personnalisés qui ont des couleurs de colonne / ligne alternées ou une grille à damiers de type échiquier avec des colonnes lettrées et des lignes numérotées pour des recherches rapides, cela augmenterait encore la précision de copie.

Vous pouvez également combiner une disposition de grille alternée avec des styles de caractères alternés comme forme facile de détection d'erreurs. C'est-à-dire que si les colonnes impaires sont toujours en majuscule, si le transcripteur se retrouve à écrire des lettres minuscules dans les colonnes impaires, alors il sait qu'il a fait une erreur et peut commencer à remonter pour voir où cela s'est produit.


Bien que si votre priorité principale est la précision, j'utiliserais un codage binaire + un code de Hamming . En utilisant un code Hamming (12, 8) raccourci sur du papier graphique standard, vous pourriez ne tenir que 187 octets, encodant seulement 124 octets de données. Mais il pourrait être transcrit très rapidement (une barre oblique pour 1, rien pour 0) et fournir une correction d'erreur unique. Le virement sur un bit de parité supplémentaire (13, 8) fournirait SECDED (correction d'erreur simple, détection d'erreur double). En utilisant un code de brouillage standard comme (15, 11) ou (31, 26), vous obtenez une efficacité encore meilleure avec 137 et 156 octets de données par feuille, respectivement. Des taux de codage encore plus élevés peuvent être atteints, selon la précision que vous pensez que votre transcripteur peut être.

Un codage binaire serait également plus facile à lire (à haute voix) et OCR / OMR.

Lèse majesté
la source
De toute évidence, je prévois également d'utiliser des majuscules. Parmi tous les schémas de correction d'erreurs que vous avez suggérés, je ne vois aucun moyen de les implémenter sans concevoir un format de fichier personnalisé, etc. Peut-être aurais-je également dû mentionner que la création de programmes personnalisés est également très indésirable? Je n'arrive pas à trouver de programme qui protège simplement vos fichiers avec des codes de correction d'erreur.
Jeremy Salwen
Mon but n'était pas d'utiliser uniquement des caractères majuscules, mais également d'utiliser différents scripts / polices. Si vous utilisez uniquement des caractères alphanumériques en majuscules et en minuscules, vous ne disposez que de 62 glyphes ou 3844 points de code. Vous pouvez obtenir plus du triple de cette quantité de points de code en utilisant 2 scripts, en profitant du support de stockage utilisé pour le transfert, ce qui était le but de ma réponse. Si vous ne souhaitez pas profiter du fait qu'il s'agit d'un support écrit, il existe de nombreux formats de fichiers qui implémentent le codage d'erreur. La plupart des formats d'archivage / compression ont une correction d'erreur intégrée.
Lèse majesté
Je ne sais pas trop ce que vous entendez par créer de nouveaux formats de fichiers. Toutes les techniques que j'ai mentionnées sont destinées à coder visuellement des données binaires arbitraires en texte / marques manuscrites. Vous ne les stockeriez pas sur l'ordinateur comme ça (vous ne pouviez pas au-delà de stocker une image numérisée). Fondamentalement, vous auriez un programme pour encoder les données, produisant une image à l'écran pour que l'utilisateur la copie. Ensuite, pour le retransférer sur un ordinateur, vous utiliseriez un programme de décodage qui soit OCR / OMR soit l'image numérisée ou accepte l'entrée via le clavier (par exemple alt+ apour cursive "a").
Lèse majesté
Vous voyez, c'est ce qui me pose problème: "vous auriez un programme pour encoder les données" ... non, je ne sais pas. Je n'ai pas de programme pour le faire, et je ne connais aucun programme pour le faire. Je ne connais pas non plus de format de fichier capable de gérer gracieusement un octet supprimé (non effacé) depuis le début du fichier en plus d'autres erreurs. Je suis définitivement d'accord que ce sont des méthodes pour augmenter la densité des données, mais ce n'est pas ma principale préoccupation maintenant, c'est la facilité de lecture / écriture et la protection contre les erreurs.
Jeremy Salwen
@ Jeremy: Comme je l'ai dit, la plupart des formats d'archives ont une correction d'erreur intégrée qui semble fonctionner assez bien pour la plupart des gens. Mais si vous voulez quelque chose de spécialement conçu pour la transcription manuelle, alors vous devrez écrire ou demander à quelqu'un d'écrire quelque chose pour vous. Sinon, votre meilleur pari est d'examiner les applications existantes conçues pour la transmission sur des canaux à bruit élevé. Bien que l'option la plus simple sans souci de densité de données soit d'utiliser simplement un fichier RAR avec un niveau élevé de correction d'erreur, puis de répéter la section d'en-tête 3 fois pour une triple redondance modulaire.
Lèse majesté
1

Nous avions l'habitude d'utiliser S-Records à cet effet. Il y avait une simple somme de contrôle, par ligne, pour la détection des erreurs. Normalement, toutes les lignes sauf la dernière étaient de longueur fixe, de sorte que le marqueur de fin de ligne servait de contrôle pour les insertions et les suppressions. Il n'y avait cependant pas de vérification pour les lignes manquantes. Pour cela, nous avons simplement compté le nombre de lignes. La plupart des fichiers étaient courts, moins de 100 lignes, mais je me souviens d'au moins un qui avait 300 lignes ou plus. C'était très fastidieux de taper des fichiers dans le système. Bien sûr, parmi les premiers programmes transférés de cette façon, il y avait un téléchargeur;)

Espion retraité
la source
0

La reconnaissance optique des marques est utilisée depuis des décennies pour créer des formulaires manuscrits lisibles par machine. La page Wikipedia contient des liens vers plusieurs versions Open Source.

Les écoles utilisent depuis longtemps l'OMR pour les tests; les formulaires sont simples à utiliser et à lire, et la précision est généralement meilleure que la saisie au clavier. Pour une plus grande précision, les fabricants commerciaux comme Scantron et ReMark peuvent créer des formulaires personnalisés.

Dour High Arch
la source
C'est intéressant, malheureusement, cela nécessite un scanner ou un autre système d'imagerie connecté à l'ordinateur pour fonctionner.
Jeremy Salwen