Cómo transferir un archivo sobre lápiz y papel, con corrección de errores

22

Estoy buscando una manera de transferir un archivo usando solo un bolígrafo y papel.

Esto es algo similar al paperbak , excepto que la densidad que estoy buscando es mucho, mucho menor, y no quiero usar una impresora o un escáner.

Obviamente, la primera respuesta es la codificación Base64 . Pero escribir y leer un número tan elevado de caracteres puede provocar errores. Para mis propósitos, cualquier error es inaceptable.

La segunda respuesta podría ser códigos de corrección de errores de Reed-Solomon (por ejemplo, usando rsbep ). Sin embargo, esto también es un problema, porque, según tengo entendido, los códigos Reed-Solomon no corrigen los errores de inserción / eliminación, que probablemente sean más probables que los errores de sustitución en este caso.

¿Hay algún programa que codifique / decodifique archivos arbitrarios con códigos de corrección de errores conscientes de inserción / eliminación? Preferiblemente debería funcionar en Windows, Linux y Mac OS X

Obviamente, cualquier otra solución al problema general es bienvenida.

Jeremy Salwen
fuente
¿Espera errores en la escritura o en la lectura?
Christian Mann
Espero errores en ambos, pero también espero que sean equivalentes ...
Jeremy Salwen
Oh, lo siento. Leí mal y pensé que estabas imprimiendo. ¿Quieres escribirlo a mano?
Christian Mann
3
¿Cuántos colores de bolígrafos puedo usar? :)
Der Hochstapler
1
Solo un bolígrafo de un solo color, de lo contrario transcribirlo será demasiado difícil. En realidad, estoy transmitiendo texto comprimido, firmado y encriptado, por lo que suponiendo que incluso una tasa de redundancia del 50%, la cantidad total de escritura será <1.5 veces más que escribir el texto original (una vez que tenga en cuenta la compresión ) Sin embargo, existe el problema de que copiar caracteres aleatorios es más difícil que copiar texto en inglés. Entonces, para responder a su pregunta, ciertamente solo en el rango de un par de kb.
Jeremy Salwen

Respuestas:

4

Dudo que otherwise transcribing it will be too difficultvaya a ser un problema.

Digamos que tienes rojo, verde, azul y negro. Puede escribir una secuencia de comandos que convierta sus datos en una colección de letras RGBY, por ejemplo: RGBYGBRYBGBYRYYBYBRYYG(o incluso Red Green Blue Black Green Blue Red Black...en una hoja de Excel) y viceversa. Es solo una cuestión de base convertir sus datos binarios de base 2 (o datos hexadecimales de base 16) a la base en la cantidad de colores que tome (4 en este ejemplo).

Ahora, el enfoque más lógico sería obtener 16 colores. De esta manera, debe usar 4 veces menos puntos, lo que hace que valga la pena cambiar entre los bolígrafos. Esto le permite escribir 4 veces más datos en el papel si lo necesita, o tal vez tenerlo puede ser 4 veces menos preciso al colocar los puntos, la escala depende de usted. Realmente recomendaría no dibujar cada bit.

Por ejemplo, 5565 bytestendría que multiplicarse por dos para obtener la cantidad de hexadecimales que es 11130 hexadecimals(en lugar de 44520 bits) que se pueden poner en una 106 x 106cuadrícula.

Dependiendo del tipo de datos, probablemente pueda venir con algunas optimizaciones ...

Sugerencia: Intente elegir los colores más distintos (más contrastantes) ...

Alternativas que pueden usar una sola pluma:

  • Representar los diferentes hexadecimales por diferentes símbolos -, /, |, \, +, ...

  • Representar los diferentes hexadecimales con una fuente de píxel pequeño, mira mi avatar.

    Esto hace que sea incluso útil usar algo como Base 32 (o Base 36). Tenga en cuenta que Qy 9son iguales, por lo que querrá que el píxel superior derecho del Qblanco sea blanco para una clara distinción. Base 32 solo requiere una 53 x 53cuadrícula para su ejemplo, más un pequeño espacio para distinguir entre letras.

Tamara Wijsman
fuente
Bueno, hay algunos problemas con esto. 1. Soy daltónico. 2. Requiere comprar un montón de bolígrafos. 3. No ayuda en absoluto con la corrección de errores. 4. Implica códigos de escritura en lugar de texto, en los que los humanos son peores.
Jeremy Salwen
@JeremySalwen: Uhm, escribir caracteres en una cuadrícula no es realmente difícil. Y puede corregir errores escribiendo algunos números de verificación longitudinales adicionales o un CRC. Pero en realidad, es muy fácil escribir sobre letras de una cuadrícula a una cuadrícula, en el peor de los casos, simplemente repita para validar.
Tamara Wijsman
1
@ JeremySalwen: Y si eres daltónico, simplemente no tomas ninguno de los colores para los que eres daltónico.
Tamara Wijsman
1
El daltonismo es más una reducción de la dimensionalidad del espacio de color que una incapacidad selectiva para ver ciertos colores. Quiero decir, probablemente podría lograr Negro, Azul, Amarillo, Rojo, Verde, Gris, pero no mucho más
Jeremy Salwen
@Tom Probablemente deberías poner tu antiguo avatar para evitar confusiones :)
Nate Koppenhaver
2

Si desea que las personas puedan leer y escribir los datos, el problema con Base64 y muchas codificaciones de texto es que usan caracteres como I, l, 1, |, /, 0, O, o, etc., que la gente confunde juntos.

Investigue la codificación Base32 de Douglas Crockford . Su alfabeto fue elegido específicamente para evitar caracteres similares, e incluye detección de errores.

Dour High Arch
fuente
Gracias, probablemente usaré esto, pero aún así no resuelve el problema de corrección de errores.
Jeremy Salwen
@Jeremy, la implementación de Crockford incluye detección de errores . Si necesita corregir errores, investigue la corrección de errores hacia adelante ( en.wikipedia.org/wiki/Forward_error_correction ).
Dour High Arch
1

Después de leer sus comentarios, eso suena más razonable. Simplemente no estaba seguro de si tenía la intención de codificar megabytes de datos como este.

Recomiendo, siguiendo la sugerencia de Oliver, que aumente su densidad de datos al tomar prestada una página del cifrado de Bacon , que las pandillas de la prisión a menudo usan para codificar mensajes ocultos en misivas escritas en 2 estilos de guión diferentes, generalmente superior o vs. caracteres en minúsculas o caracteres impresos o cursivos, por ejemplo

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

Sin embargo, dado que su objetivo no es la estegnografía, simplemente usaría esto para expandir su conjunto de glifos. Al hacer esto, podría tener hasta 114 glifos simplemente usando caracteres alfanuméricos impresos y cursivos, o 12996 puntos de código usando codificación de doble carácter.

Sin embargo, dado que todos los recuentos de glifos mayores de 15 y menores de 256 son esencialmente los mismos para un cifrado directo de datos binarios (es decir, aún necesitará 2 caracteres para representar cada byte, lo que le dará una densidad de datos de 4 bits por carácter en todos los casos), puede usar los 98 glifos adicionales / 12740 puntos de código para la detección / corrección de errores.

Las formas de hacer esto incluyen:

  • Elija un conjunto de los 256 combos de caracteres más fáciles de leer / escribir. Si se produce cualquier otro combo de caracteres, sabes que es un error de copia.
  • Use dos versiones del carácter final como un bit de paridad.
  • Crea 50 conjuntos de glifos de 16 caracteres diferentes. Luego puede usarlos para cifrar los datos de corrección de errores de codificación.

    Por ejemplo, {set 1}{set 1}significa que los siguientes 3 mordiscos son iguales 0x000, {set 1}{set 2}iguales 0x001, etc.

    Puede usar esto para representar más de 2500 de los 4096 posibles valores de 1,5 bytes. Del mismo modo, puede usar solo 16 conjuntos para representar todos los valores del siguiente byte, lo que le brinda una redundancia del 100% sin aumentar la longitud de los datos codificados.

Alternativamente, puede usar los glifos adicionales para una compresión adicional:

  • Implemente la codificación de ancho variable eligiendo 98 puntos de código de un solo carácter. Esto reduciría el tamaño promedio del contenido codificado en aproximadamente un 20%.
  • Implemente algo similar a la codificación de longitud de ejecución utilizando diferentes conjuntos de glifos o combinaciones de conjuntos de glifos para representar nibbles / bytes repetidos. Ej Ab= aba; aB= abab; AB= ababab...
  • Use los glifos o puntos de código adicionales para representar "palabras" y "frases" que se repiten en sus datos. Aunque los datos precomprimidos probablemente tengan un alto nivel de entropía, no sé qué tan efectivo sería.


Para reducir aún más los errores de copia, mostraría el contenido codificado en líneas de cuadrícula y lo copiaría en papel cuadriculado. Si puede usar estacionario personalizado que tiene colores alternos de columna / fila o una cuadrícula a cuadros estilo tablero de ajedrez con columnas con letras y filas numeradas para búsquedas rápidas, eso aumentaría aún más la precisión de la copia.

También puede combinar un diseño de cuadrícula alterna con estilos de caracteres alternativos como una forma fácil de detección de errores. Es decir, si las columnas impares siempre están en mayúscula, si el transcriptor se encuentra escribiendo letras minúsculas en columnas impares, entonces saben que han cometido un error y pueden comenzar a rastrear para ver dónde sucedió.


Aunque si su prioridad principal es la precisión, usaría una codificación binaria + código de Hamming . Usando un código de Hamming acortado (12, 8) en un papel gráfico estándar, es posible que solo quepa 187 bytes, codificando solo 124 bytes de datos. Pero podría transcribirse muy rápidamente (una barra oblicua para 1, nada para 0) y proporcionar una corrección de error único. Agregar un bit de paridad adicional (13, 8) proporcionaría SECDED (corrección de error simple, detección de error doble). Usando un código de hamming estándar como (15, 11) o (31, 26), obtienes una eficiencia aún mejor con 137 y 156 bytes de datos por hoja, respectivamente. Se pueden lograr incluso tasas de código más altas, dependiendo de cuán preciso cree que puede ser su transcriptor.

Una codificación binaria también sería más fácil de leer (en voz alta) y OCR / OMR.

Lèse majesté
fuente
Obviamente, estoy planeando usar también mayúsculas. De todos los esquemas de corrección de errores que ha sugerido, no veo ninguna forma de implementarlos sin diseñar un formato de archivo personalizado, etc. ¿Realmente no hay precedente para poner protección de corrección de errores en los archivos? ¿Quizás debería haber mencionado que la creación de programas personalizados también es muy indeseable? Parece que no puedo encontrar ningún programa que solo proteja sus archivos con códigos de corrección de errores.
Jeremy Salwen
Mi punto no era solo usar mayúsculas, sino también usar diferentes scripts / fuentes. Si solo usa caracteres alfanuméricos en mayúsculas y minúsculas, solo tiene 62 glifos o 3844 puntos de código. Puede obtener más del triple de esa cantidad de puntos de código utilizando 2 scripts, aprovechando el medio de almacenamiento que se utiliza para la transferencia, que fue el propósito de mi respuesta. Si no quiere aprovechar el hecho de que este es un medio escrito, entonces hay muchos formatos de archivo que implementan codificación de error. La mayoría de los formatos de archivo / compresión tienen corrección de errores incorporada.
Lèse majesté
Sin embargo, no estoy seguro de lo que quieres decir con crear nuevos formatos de archivo. Todas las técnicas que mencioné están destinadas a codificar visualmente datos binarios arbitrarios en texto / marcas escritos a mano. No los almacenaría en la computadora de esa manera (no podría más allá de almacenar una imagen escaneada). Básicamente, tendría un programa para codificar los datos, generando una imagen en la pantalla para que el usuario la copie. Luego, para transferirlo nuevamente a una computadora, usaría un programa de decodificación que OCR / OMR es la imagen escaneada o acepta la entrada a través del teclado (por ejemplo, alt+ apara la "a" cursiva).
Lèse majesté
Mira, eso es con lo que tengo el problema: "tendrías un programa para codificar los datos" ... no, no lo tengo. No tengo un programa para hacer esto, y no conozco ningún programa para hacerlo. Tampoco conozco ningún formato de archivo que pueda manejar con gracia un byte eliminado (no borrado) cerca del comienzo del archivo además de otros errores. Definitivamente estoy de acuerdo en que estos son métodos para aumentar la densidad de datos, pero esa no es mi principal preocupación ahora, es la facilidad de lectura / escritura y la protección contra errores.
Jeremy Salwen
@Jeremy: Como dije, la mayoría de los formatos de archivo tienen una corrección de errores incorporada que parece funcionar lo suficientemente bien para la mayoría de las personas. Pero si quieres algo especialmente diseñado para la transcripción manual, entonces necesitarás escribir o que alguien escriba algo para ti. De lo contrario, lo mejor es buscar aplicaciones existentes diseñadas para transmitir a través de canales de alto ruido. Aunque la opción más fácil sin preocuparse por la densidad de datos es simplemente usar un archivo RAR con un alto nivel de corrección de errores, y luego repetir la sección del encabezado 3 veces para una redundancia modular triple.
Lèse majesté
1

Solíamos usar S-Records para este propósito. Había una suma de comprobación simple, por línea, para la detección de errores. Normalmente, excepto la última línea, tenía una longitud fija, por lo que el marcador de fin de línea servía como un control para las inserciones y eliminaciones. Sin embargo, no se verificaron las líneas faltantes. Para esto simplemente contamos el número de líneas. La mayoría de los archivos eran cortos, de menos de 100 líneas, pero recuerdo al menos uno que tenía 300 líneas o más. Fue muy tedioso escribir archivos en el sistema. Por supuesto, entre los primeros programas transferidos de esta manera se encontraba un descargador;)

Espía retirado
fuente
0

El reconocimiento óptico de marcas se ha utilizado durante décadas para crear formularios escritos a mano legibles por máquina. La página de Wikipedia tiene enlaces a varias versiones de código abierto.

Las escuelas han usado OMR durante mucho tiempo para las pruebas; los formularios son fáciles de usar y de leer, y la precisión suele ser mejor que la entrada del teclado. Para mayor precisión, los fabricantes comerciales como Scantron y ReMark pueden crear formularios personalizados.

Dour High Arch
fuente
Eso es interesante, desafortunadamente, esto requiere un escáner u otro sistema de imágenes conectado a la computadora para funcionar.
Jeremy Salwen