Como transferir um arquivo em papel e caneta, com correção de erros

22

Estou procurando uma maneira de transferir um arquivo usando apenas caneta e papel.

Isso é um pouco semelhante ao paperbak , exceto que a densidade que estou procurando é muito, muito menor, e eu não quero usar uma impressora ou um scanner.

Obviamente, a primeira resposta é a codificação Base64 . Mas escrever e ler um número tão alto de caracteres pode resultar em erros. Para meus propósitos, qualquer erro é inaceitável.

A segunda resposta pode ser códigos de correção de erros de Reed-Solomon (por exemplo, usando o rsbep ). No entanto, isso também é um problema, porque, pelo meu entendimento, os códigos Reed-Solomon não corrigem erros de inserção / exclusão, que provavelmente são mais prováveis ​​do que erros de substituição nesse caso.

Existe algum programa que codifique / decodifique arquivos arbitrários com códigos de correção de erros de inserção / exclusão? De preferência, ele deve funcionar no Windows, Linux e Mac OS X

Obviamente, qualquer outra solução para o problema geral é bem-vinda.

Jeremy Salwen
fonte
Você espera erros por escrito ou apenas lendo?
Christian Mann
Espero erros em ambos, mas eu também esperar que eles sejam equivalentes ...
Jeremy Salwen
Oh, desculpe. Eu interpretei mal e pensei que você estava imprimindo. Você quer escrever à mão?
Christian Mann
3
Quantas cores de canetas posso usar? :)
Der Hochstapler
1
Apenas uma caneta de uma cor, caso contrário, a transcrição será muito difícil. Na verdade, estou transmitindo texto compactado, assinado e criptografado, portanto, assumindo uma taxa de redundância de 50%, a quantidade total de escrita será <1,5 vezes mais do que realmente seria a escrita do texto original (depois de considerar a compactação ) No entanto, existe o problema de que copiar caracteres aleatórios é mais difícil do que copiar texto em inglês. Portanto, para responder à sua pergunta, certamente apenas no intervalo de kb.
Jeremy Salwen

Respostas:

4

Duvido que otherwise transcribing it will be too difficultisso seja um problema.

Digamos que você tenha vermelho, verde, azul e preto. Você pode escrever um script que transforma seus dados em uma coleção de cartas de RGBY, por exemplo: RGBYGBRYBGBYRYYBYBRYYG(ou mesmo Red Green Blue Black Green Blue Red Black...em uma planilha do Excel) e vice-versa. É apenas uma questão de converter os dados binários da base 2 (ou dados hexadecimais da base 16) para a base na quantidade de cores que você usa (4 neste exemplo).

Agora, a abordagem mais lógica seria obter 16 cores. Dessa forma, você deve usar 4 vezes menos pontos, o que faz com que a troca entre as canetas valha a pena. Isso permite que você escreva 4 vezes mais dados no papel, se necessário, ou talvez seja 4 vezes menos preciso ao colocar seus pontos, a escala depende de você. Eu realmente desaconselharia desenhar cada pedaço.

Por exemplo, 5565 bytesteria que ser multiplicado por dois para obter a quantidade de hexadecimais que é 11130 hexadecimals(em oposição a 44520 bits) que pode ser colocada em uma 106 x 106grade.

Dependendo do tipo de dados, você provavelmente pode vir com algumas otimizações ...

Dica: tente escolher as cores mais distintas (mais contrastantes) ...

Alternativas que podem usar uma única caneta:

  • Representar os diferentes hexadecimais por diferentes símbolos -, /, |, \, +, ...

  • Represente os diferentes hexadecimais por uma fonte de pixel pequeno, veja meu avatar.

    Isso torna ainda útil usar algo como Base 32 (ou Base 36). Observe que Qe 9são iguais, portanto, você desejará que o pixel superior direito Qseja Branco para uma distinção clara. A base 32 requer apenas uma 53 x 53grade para o seu exemplo, além de um pequeno espaçamento para diferenciar as letras.

Tamara Wijsman
fonte
Bem, há alguns problemas com isso. 1. Eu sou daltônico. 2. Requer a compra de um monte de canetas. 3. Não ajuda em nada com a correção de erros. 4. Envolve códigos de escrita em vez de texto, no qual os humanos são piores.
Jeremy Salwen
@ JeremySalwen: Uhm, escrever caracteres em uma grade não é realmente difícil. E você pode corrigir erros escrevendo alguns números de verificação longitudinais extras ou um CRC. Mas, na verdade, é muito fácil escrever sobre letras de uma grade para outra; no pior caso, basta revisar novamente para validar.
Tamara Wijsman
1
@ JeremySalwen: E se você é daltônico, simplesmente não pega nenhuma das cores pelas quais é daltônico.
Tamara Wijsman
1
O daltonismo é mais uma redução de dimensionalidade do espaço de cores do que uma incapacidade seletiva de ver determinadas cores. Quer dizer, eu provavelmente poderia retirar Preto, Azul, Amarelo, Vermelho, Verde, Cinza, mas não muito mais
Jeremy Salwen
@ Tom Você provavelmente deve colocar o seu antigo avatar para evitar confusão :)
Nate Koppenhaver
2

Se você deseja que as pessoas possam ler e gravar os dados, o problema com o Base64 e muitas codificações de texto é que eles usam caracteres como I, l, 1, |, /, 0, O, o e assim por diante, que as pessoas confundem. um com o outro.

Investigue a codificação Base32 de Douglas Crockford . Seu alfabeto foi escolhido especificamente para evitar caracteres semelhantes e inclui detecção de erros.

Arco Alto de Dour
fonte
Obrigado, provavelmente vou usar isso, mas ainda não resolve o problema de correção de erros.
Jeremy Salwen
@ Jeremy, a implementação de Crockford inclui detecção de erros . Se você precisar corrigir erros, investigue a Correção de Erro de Avanço ( pt.wikipedia.org/wiki/Forward_error_correction ).
Dour High Arch
1

Depois de ler seus comentários, isso parece mais razoável. Só não tinha certeza se você pretendia codificar megabytes de dados como este.

Eu recomendaria, de acordo com a sugestão de Oliver, aumentar a densidade de dados emprestando uma página da cifra de Bacon , que as gangues de prisão costumam usar para codificar mensagens ocultas em missivas escritas em 2 estilos diferentes de script - geralmente superior vs. caracteres minúsculos ou caracteres vs. caracteres cursivos, por exemplo

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

No entanto, como seu objetivo não é a estegnografia, basta usá-lo para expandir seu conjunto de glifos. Com isso, você pode ter até 114 glifos usando caracteres alfanuméricos impressos e cursivos ou 12996 pontos de código usando codificação de caracteres duplos.

No entanto, como todas as contagens de glifos maiores que 15 e menores que 256 são essencialmente iguais para uma cifra direta de dados binários (ou seja, você ainda precisará de 2 caracteres para representar cada byte, oferecendo uma densidade de dados de 4 bits por caractere em todos os casos), você pode usar os 98 pontos de código extras / glifos / 12740 para detecção / correção de erros.

As maneiras de fazer isso incluem:

  • Escolha um conjunto dos 256 combos de caracteres mais fáceis de ler / gravar. Se qualquer outra combinação de caracteres ocorrer, você sabe que é um erro de cópia.
  • Use duas versões do caractere final como um bit de paridade.
  • Crie 50 conjuntos diferentes de glifos de 16 caracteres. Você pode usá-los para codificar codificar dados de correção de erros.

    Por exemplo, {set 1}{set 1}significa que os próximos 3 petiscos são iguais 0x000, {set 1}{set 2}iguais 0x001etc.

    Você pode usar isso para representar mais de 2500 dos 4096 possíveis valores de 1,5 byte. Da mesma forma, você pode usar apenas 16 conjuntos para representar todos os valores do byte a seguir, fornecendo 100% de redundância sem aumentar o comprimento dos dados codificados.

Como alternativa, você pode usar os glifos extras para compactação adicional:

  • Implemente a codificação de largura variável escolhendo 98 pontos de código de caractere único. Isso reduziria o tamanho médio do conteúdo codificado em cerca de 20%.
  • Implemente algo semelhante à codificação de execução usando diferentes conjuntos de glifos ou combinações de conjuntos de glifos para representar nibbles / bytes repetidos. Por exemplo Ab= aba; aB= abab; AB= ababab...
  • Use os glifos ou pontos de código extras para representar "palavras" e "frases" repetidas em seus dados. Embora os dados pré-compactados provavelmente tenham um alto nível de entropia, não sei quão eficaz isso seria.


Para reduzir ainda mais os erros de cópia, eu exibia o conteúdo codificado em linhas de grade e copiava em papel gráfico. Se você pode usar papel de carta personalizado com cores alternadas de coluna / linha ou uma grade quadriculada no estilo tabuleiro de xadrez com colunas com letras e linhas numeradas para pesquisas rápidas, isso aumentaria ainda mais a precisão da cópia.

Você também pode combinar um layout de grade alternativo com estilos de caracteres alternados como uma forma fácil de detecção de erros. Ou seja, se as colunas ímpares sempre estiverem em maiúsculas, se o transcritor estiver escrevendo letras minúsculas em colunas ímpares, eles saberão que cometeram um erro e poderão começar a rastrear novamente para ver onde aconteceu.


Embora sua principal prioridade seja a precisão, eu usaria uma codificação binária + código Hamming . Usando um código Hamming (12, 8) reduzido em papel gráfico padrão, você pode caber apenas 187 bytes, codificando apenas 124 bytes de dados. Mas pode ser transcrito muito rapidamente (uma barra para 1, nada para 0) e fornecer uma correção de erro única. Aplicar um bit de paridade extra (13, 8) forneceria SECDED (correção de erro único, detecção de erro duplo). Usando um código hamming padrão como (15, 11) ou (31, 26), você obtém uma eficiência ainda melhor com 137 e 156 bytes de dados por folha, respectivamente. É possível obter taxas de código ainda mais altas, dependendo da precisão que você acha que seu transcritor pode ser.

Uma codificação binária também seria mais fácil de ler (em voz alta) e OCR / OMR.

Lèse majesté
fonte
Obviamente, também estou planejando usar caracteres maiúsculos. De todos os esquemas de correção de erros que você sugeriu, não vejo como implementá-los sem criar um formato de arquivo personalizado etc. Não há realmente nenhum precedente para colocar proteção de correção de erros nos arquivos? Talvez eu também devesse ter mencionado que criar programas personalizados também é altamente indesejável? Não consigo encontrar nenhum programa que apenas proteja seus arquivos com códigos de correção de erros.
Jeremy Salwen
Meu objetivo não era apenas usar caracteres maiúsculos, mas também usar scripts / fontes diferentes. Se você usar apenas caracteres alfanuméricos maiúsculos e minúsculos, terá apenas 62 glifos ou 3844 pontos de código. Você pode obter mais que o triplo dessa quantidade de pontos de código usando 2 scripts, aproveitando a mídia de armazenamento usada para a transferência, que foi o objetivo da minha resposta. Se você não quiser tirar proveito do fato de ser uma mídia gravada, existem muitos formatos de arquivo que implementam a codificação de erros. A maioria dos formatos de arquivo / compressão têm correção de erro embutido.
lesa majestade
Não sei ao certo o que você quer dizer com a criação de novos formatos de arquivo. Todas as técnicas que mencionei destinam-se à codificação visual de dados binários arbitrários em marcas / textos manuscritos. Você não os armazenaria no computador dessa maneira (você não poderia além de armazenar uma imagem digitalizada). Basicamente, você teria um programa para codificar os dados, exibindo uma imagem na tela para o usuário copiar. Em seguida, para transferi-lo de volta para um computador, você usaria um programa de decodificação que OCR / OMR é a imagem digitalizada ou aceita a entrada via teclado (por exemplo, alt+ apara "a" cursivo).
Lèse majesté
Veja, é com isso que eu tenho o problema: "você teria um programa para codificar os dados" ... não, não tenho. Não tenho um programa para fazer isso e não conheço nenhum programa para fazer isso. Também não estou ciente de nenhum formato de arquivo que possa manipular normalmente um byte removido (não apagado) perto do início do arquivo, além de outros erros. Definitivamente, concordo que esses são métodos para aumentar a densidade de dados, mas essa não é minha principal preocupação agora, é a facilidade de leitura / gravação e proteção contra erros.
Jeremy Salwen
@ Jeremy: Como eu disse, a maioria dos formatos de arquivo tem correção de erros, o que parece funcionar bem o suficiente para a maioria das pessoas. Mas se você quiser algo especialmente projetado para transcrição manual, precisará escrever ou mandar alguém escrever algo para você. Caso contrário, sua melhor aposta é procurar aplicativos existentes projetados para transmitir através de canais de alto ruído. Embora a opção mais fácil, sem preocupação com a densidade de dados, seja apenas usar um arquivo RAR com alto nível de correção de erros e repetir a seção do cabeçalho 3 vezes para obter redundância modular tripla.
Lèse majesté
1

Costumávamos usar S-Records para esse fim. Havia uma soma de verificação simples, por linha, para detecção de erros. Normalmente, exceto a última linha, o comprimento era fixo; portanto, o marcador de fim de linha servia como verificação de inserções e exclusões. Não houve verificação de falta de linhas. Para isso, contamos simplesmente o número de linhas. A maioria dos arquivos era curta, com menos de 100 linhas, mas eu me lembro de pelo menos um que tinha 300 linhas ou mais. Foi muito tedioso digitar arquivos no sistema. Obviamente, um dos primeiros programas transferidos dessa maneira foi um downloader;)

Espião aposentado
fonte
0

O reconhecimento óptico de marcas é usado há décadas para criar formulários manuscritos legíveis por máquina. A página da Wikipedia possui links para várias versões de código aberto.

As escolas há muito usam o OMR para testes; os formulários são simples de usar e ler, e a precisão geralmente é melhor que a entrada do teclado. Para maior precisão, fabricantes comerciais como Scantron e ReMark podem criar formulários personalizados.

Arco Alto de Dour
fonte
Isso é interessante, infelizmente, isso requer um scanner ou outro sistema de imagem conectado ao computador para funcionar.
Jeremy Salwen