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

22

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

Isso é um pouco semelhante ao paperbak , exceto que a densidade que estou procurando é muito, muito menor, e eu não deseja 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 os meus propósitos, qualquer erro é inaceitável.

A segunda resposta pode ser códigos de correção de erros Reed-Solomon (por exemplo, usando < href="http://manpages.ubuntu.com/manpages/natty/man1/rsbep.1.html"> rsbep ). No entanto, isso também é um problema, porque, do meu ponto de vista, 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 neste caso.

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

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

    
por Jeremy Salwen 22.04.2012 / 22:31

5 respostas

4

duvido que otherwise transcribing it will be too difficult seja um problema.

Digamos que você tenha vermelho, verde, azul e preto. Você pode escrever um script que transforme seus dados em uma coleção de letras 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 seus dados binários da base 2 (ou dados hexadecimais da base 16) para a base na quantidade de cores que você tira (4 neste exemplo).

Agora, a abordagem mais lógica seria obter 16 cores. Dessa forma, você precisa 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 precisar, ou talvez seja 4 vezes menos preciso ao colocar seus pontos, a escala é sua. Eu realmente aconselho contra desenhar cada pedacinho.

Por exemplo, 5565 bytes teria 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 grade 106 x 106 .

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:

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

  • Representa os diferentes hexadecimais por uma fonte pequena de pixels, veja meu avatar.

    Isso torna ainda mais útil usar algo como Base 32 (ou Base 36). Observe que os Q e 9 são os mesmos, então você desejará que o pixel superior direito de Q seja branco para uma clara distinção. A base 32 requer apenas uma grade 53 x 53 para o seu exemplo, além de um pequeno espaçamento entre letras.

por 23.04.2012 / 09:49
2

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

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

    
por 02.05.2012 / 20:47
1

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

Eu recomendaria, seguindo as linhas da sugestão de Oliver, que você aumentasse sua densidade de dados pegando emprestada uma página de a cifra de Bacon , que as gangues de prisões costumam usar para codificar mensagens ocultas em missivas escritas em 2 estilos diferentes de scripts - geralmente em caracteres maiúsculos em comparação com caracteres minúsculos ou em caracteres impressos versus 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 é stegnography, você simplesmente usaria isso para expandir seu conjunto de glifos. Fazendo isso, você pode ter até 114 glifos usando print & caracteres alfanuméricos cursivos ou 12996 pontos de código usando a codificação de caractere duplo.

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

As formas de fazer isso incluem:

  • Escolha um conjunto dos 256 mais fáceis de ler / escrever combos de caracteres. Se qualquer outro combo 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 de glifos de 16 caracteres diferentes. Você pode usá-los para codificar os dados de correção de erros.

    Por exemplo {set 1}{set 1} significa os próximos 3 nibbles iguais a 0x000 , {set 1}{set 2} igual a 0x001 , etc.

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

Como alternativa, você pode usar os glifos extras para uma 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 comprimento de execução usando conjuntos de glifos diferentes ou combinações de conjuntos de glifos para representar nibbles / bytes repetidos. Por exemplo. Ab = aba ; aB = abab ; AB = ababab ...
  • Use os glifos extras ou os pontos de código para representar "palavras" e "frases" que são repetidas em seus dados. Embora os dados pré-compactados provavelmente tenham um alto nível de entropia, não sei quão eficiente isso seria.

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

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

No entanto, se a sua principal prioridade for a precisão, usaria uma codificação binária + código Hamming . Usando um (12, 8) encurtado código Hamming 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 simples. Tacking em um bit de paridade extra (13, 8) forneceria SECDED (correção de erro simples, detecção de erro duplo). Usando um código padrão de hamming como (15, 11) ou (31, 26), você obtém eficiência ainda melhor com 137 e 156 bytes de dados por folha, respectivamente. Taxas de código ainda mais altas podem ser alcançadas, dependendo de quão preciso 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.

    
por 23.04.2012 / 21:24
1

Nós costumávamos usar S-Records para este propósito. Havia uma soma de verificação simples, por linha, para detecção de erros. Normalmente, todas as linhas, exceto a última, tinham comprimento fixo, portanto, o marcador de fim de linha servia como uma verificação de inserções e exclusões. Não havia verificação de linhas faltantes. Para isso, simplesmente contamos o número de linhas. Principalmente os arquivos eram curtos, menos de 100 linhas, mas eu lembro de pelo menos um que tinha 300 linhas ou mais. Foi muito tedioso digitando arquivos no sistema. Claro, entre os primeiros programas transferidos desta forma foi um downloader;)

    
por 16.02.2014 / 02:55
0

Reconhecimento de marca óptica tem sido usado há décadas para criar formulários manuscritos legíveis por máquina. A página da Wikipedia tem links para várias versões de código aberto.

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

    
por 29.04.2012 / 18:10