Как перенести файл поверх ручки и бумаги, с исправлением ошибок

22

Я ищу способ передачи файла, используя только ручку и бумагу.

Это немного похоже на бумажный пакет , за исключением того, что плотность, которую я ищу, намного, намного ниже, и я не хочу использовать принтер или сканер.

Очевидно, первый ответ - кодировка Base64 . Но написание и чтение такого большого количества символов обязательно приведет к ошибкам. Для моих целей любая ошибка недопустима.

Второй ответ может быть кодами исправления ошибок Рида-Соломона (например, с использованием rsbep ). Однако это также проблема, потому что, насколько я понимаю, коды Рида-Соломона не исправляют ошибки вставки / удаления, которые в данном случае, вероятно, более вероятны, чем ошибки замещения.

Существует ли какая-либо программа, которая будет кодировать / декодировать произвольные файлы с помощью кодов, исправляющих ошибки с учетом вставки / удаления? Предпочтительно это должно работать на Windows, Linux и Mac OS X

Очевидно, что любое другое решение общей проблемы приветствуется.

Джереми Салвен
источник
Ожидаете ли вы ошибки в письме или просто в чтении?
Кристиан Манн
Я ожидаю ошибки в обоих случаях, но я также ожидаю, что они будут эквивалентны ...
Джереми Сальвен,
Ой, извини. Я неправильно прочитал и подумал, что вы печатаете. Вы хотите написать это вручную?
Кристиан Манн
3
Сколько цветов ручек я могу использовать? :)
Der Hochstapler
1
Только одноцветное перо, иначе расшифровать его будет слишком сложно. Я на самом деле передаю сжатый, подписанный, зашифрованный текст, поэтому при условии, что даже коэффициент избыточности составляет 50%, общий объем записи будет <в 1,5 раза больше, чем будет фактически выписывать исходный текст (если учесть сжатие ). Однако существует проблема, заключающаяся в том, что копирование случайных символов сложнее, чем копирование текста на английском языке. Таким образом, чтобы ответить на ваш вопрос, конечно, только в диапазоне пару кб.
Джереми Сальвен

Ответы:

4

Я сомневаюсь, otherwise transcribing it will be too difficultбудет ли проблема.

Допустим, у вас есть красный, зеленый, синий и черный. Вы можете написать скрипт, который превращает ваши данные в набор писем RGBY, например: RGBYGBRYBGBYRYYBYBRYYG(или даже Red Green Blue Black Green Blue Red Black...в лист Excel) и обратно. Это просто вопрос базового преобразования ваших двоичных данных из базы 2 (или шестнадцатеричных данных из базы 16) в базу в количестве цветов, которые вы выбираете (4 в этом примере).

Теперь самым логичным подходом было бы получить себе 16 цветов. Таким образом, вы должны использовать в 4 раза меньше точек, что делает переключение между ручками того стоит. Это позволяет вам записывать в 4 раза больше данных на бумаге, если вам нужно или, возможно, иметь, может быть в 4 раза менее точно при нанесении точек, масштабирование зависит от вас. Я бы действительно советовал не рисовать каждый бит.

Например, 5565 bytesпришлось бы умножить на два, чтобы получить количество шестнадцатеричных чисел, которое 11130 hexadecimals(в отличие от 44520 bits), которое можно поместить в 106 x 106сетку.

В зависимости от типа данных вы можете прийти с некоторыми оптимизациями ...

Подсказка: попытайтесь выбрать наиболее четкие (наиболее контрастные) цвета ...

Альтернативы, которые могут использовать одну ручку:

  • Представляет различные шестнадцатеричные разными символы -, /, |, \, +, ...

  • Представьте различные шестнадцатеричные числа маленьким пиксельным шрифтом, см. Мой аватар.

    Это делает даже полезным использовать что-то вроде Base 32 (или Base 36). Обратите внимание, что Qи 9совпадают, поэтому вам нужно, чтобы верхний правый пиксель Qбыл белым для четкого различия. Base 32 требует только 53 x 53сетку для вашего примера, плюс небольшой интервал между буквами.

Тамара Вийсман
источник
Ну, есть несколько проблем с этим. 1. Я дальтоник 2. Требуется купить кучу ручек. 3. Это совсем не помогает с исправлением ошибок. 4. Это включает в себя написание кодов вместо текста, что людям хуже.
Джереми Сальвен
@JeremySalwen: Хм, написание символов в сетке не очень сложно. И вы можете исправить ошибки, написав несколько дополнительных продольных контрольных номеров или CRC. Но на самом деле, очень легко записывать буквы из сетки в сетку, в худшем случае вы просто повторяете это для подтверждения.
Тамара Вийсман
1
@JeremySalwen: И если вы дальтоник, вы просто не берете цвета, для которых вы дальтоник.
Тамара Вийсман
1
Дальтонизм - это скорее уменьшение размерности цветового пространства, чем избирательная неспособность видеть определенные цвета. Я имею в виду, что я, вероятно, мог бы снять черный, синий, желтый, красный, зеленый, серый, но не намного
Джереми Сальвен
@Tom Тебе, вероятно, стоит положить свой старый аватар, чтобы избежать путаницы :)
Нейт Коппенхейвер,
2

Если вы хотите, чтобы люди могли читать и записывать данные, проблема с Base64 и многими кодировками текста заключается в том, что они используют такие символы, как I, l, 1, |, /, 0, O, o и т. Д., Что люди путают друг с другом.

Исследуйте кодировку Base32 Дугласа Крокфорда . Его алфавит был специально выбран, чтобы избежать подобных символов, и он включает в себя обнаружение ошибок.

Dour High Arch
источник
Спасибо, я, вероятно, буду использовать это, но это все еще не решает проблему исправления ошибок.
Джереми Сальвен
@ Джереми, реализация Крокфорда включает обнаружение ошибок . Если вам нужно исправить ошибки, изучите исправление ошибок вперед ( en.wikipedia.org/wiki/Forward_error_correction ).
Dour High Arch
1

После прочтения ваших комментариев это звучит более разумно. Я просто не был уверен, что вы собираетесь кодировать мегабайты таких данных.

Я бы порекомендовал, в соответствии с предложением Оливера, увеличить плотность данных, заимствуя страницу из шифра Бэкона , которую тюремные банды часто используют для кодирования скрытых сообщений в сообщениях, написанных в 2 разных стилях сценария - обычно либо верхний, либо верхний строчные или печатные или рукописные символы, например

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

Однако, поскольку ваша цель - не стегнография, вы просто используете это, чтобы расширить набор глифов. При этом вы можете получить до 114 глифов, используя только печатные и курсивные буквенно-цифровые символы, или 12996 кодовых точек с использованием двухсимвольного кодирования.

Однако, поскольку все числа глифов больше 15 и меньше 256, по существу, одинаковы для прямого шифра двоичных данных (то есть вам по-прежнему нужно 2 символа для представления каждого байта, что дает плотность данных 4 бита на символ в во всех случаях), вы можете использовать дополнительные 98 глифов / 12740 кодовых точек для обнаружения / исправления ошибок.

Способы сделать это включают в себя:

  • Выберите набор из 256 самых простых для чтения / записи комбинаций символов. Если происходит комбо другого символа, вы знаете, что это ошибка копирования.
  • Используйте две версии конечного символа в качестве бита четности.
  • Создайте 50 различных 16-символьных наборов глифов. Затем вы можете использовать их для шифрования данных для исправления ошибок.

    Например, {set 1}{set 1}следующие 3 полубайта равны 0x000, {set 1}{set 2}равны 0x001и т. Д.

    Вы можете использовать это для представления 2500+ из 4096 возможных 1,5-байтовых значений. Точно так же вы можете использовать только 16 наборов для представления всех значений следующего байта, что дает вам 100% избыточность без увеличения длины закодированных данных.

В качестве альтернативы, вы можете использовать дополнительные глифы для дополнительного сжатия:

  • Реализуйте кодирование переменной ширины, выбрав 98 односимвольных кодовых точек. Это уменьшит средний размер закодированного контента примерно на 20%.
  • Реализуйте что-то похожее на кодирование по длине прогона, используя разные наборы глифов или комбинации наборов глифов для представления повторяющихся кусков / байтов. Например, Ab= aba; aB= abab; AB= ababab...
  • Используйте дополнительные символы или кодовые точки для представления «слов» и «фраз», которые повторяются в ваших данных. Хотя предварительно сжатые данные, вероятно, будут иметь высокий уровень энтропии, поэтому я не знаю, насколько это будет эффективно.


Чтобы еще больше уменьшить количество ошибок при копировании, я бы отображал закодированный контент в виде линий сетки и копировал их на графическую бумагу. Если вы можете использовать нестандартный бланк, который имеет чередующиеся цвета столбцов / строк, или клетчатую сетку в шахматном стиле с буквенными столбцами и пронумерованными рядами для быстрого поиска, это еще больше повысит точность копирования.

Вы также можете комбинировать чередующийся макет сетки с чередующимися стилями символов в качестве простой формы обнаружения ошибок. Т.е. если нечетные столбцы всегда пишутся с большой буквы, если транскрибер обнаруживает, что пишет строчные буквы в нечетных столбцах, он знает, что допустил ошибку, и может начать отслеживать, чтобы увидеть, где это произошло.


Хотя, если ваш главный приоритет - точность, я бы использовал двоичное кодирование + код Хэмминга . Используя сокращенный (12, 8) код Хэмминга на стандартной графической бумаге, вы можете разместить только 187 байтов, кодируя только 124 байта данных. Но это может быть очень быстро расшифровано (косая черта для 1, ничто для 0) и обеспечить единственное исправление ошибки. Установка дополнительного бита четности (13, 8) обеспечит SECDED (исправление одиночной ошибки, обнаружение двойной ошибки). Используя стандартный код Хэмминга, такой как (15, 11) или (31, 26), вы получаете еще большую эффективность с 137 и 156 байтами данных на лист соответственно. В зависимости от того, насколько точным, по вашему мнению, может быть ваш транскрибер, можно достичь еще более высоких скоростей кодирования

Бинарное кодирование также будет легче читать (вслух) и OCR / OMR.

Lèse Majesté
источник
Очевидно, я планирую использовать и заглавные буквы. Из всех предложенных вами схем исправления ошибок я не вижу способа реализовать их без разработки нестандартного формата файла и т. Д. Неужели не существует прецедента для установки защиты файлов с исправлением ошибок? Возможно, я должен был также упомянуть, что создание пользовательских программ также крайне нежелательно? Кажется, я не могу найти какую-либо программу, которая просто защитит ваши файлы с помощью кодов, исправляющих ошибки.
Джереми Сальвен
Моя точка зрения заключалась не в том, чтобы использовать только заглавные буквы, а в том, чтобы использовать разные скрипты / шрифты. Если вы используете только прописные и строчные буквенно-цифровые символы, у вас будет только 62 символа или 3844 кодовых знака. Вы можете получить более чем в три раза больше кода, используя 2 сценария, воспользовавшись носителем данных, используемым для передачи, что и было целью моего ответа. Если вы не хотите использовать тот факт, что это письменный носитель, существует множество форматов файлов, в которых реализовано кодирование ошибок. Большинство форматов архивирования / сжатия имеют встроенное исправление ошибок.
Lèse majesté
Я не уверен, что вы имеете в виду, создавая новые форматы файлов, хотя. Все методы, которые я упомянул, предназначены для визуального кодирования произвольных двоичных данных в рукописный текст / метки. Вы не будете хранить их на компьютере таким образом (вы не можете сохранить отсканированное изображение). По сути, у вас есть программа для кодирования данных, выводящая изображение на экран, которое пользователь может скопировать. Затем, чтобы перенести его обратно на компьютер, вы должны использовать программу декодирования, которая либо OCR / OMR сканирует отсканированное изображение, либо принимает ввод с клавиатуры (например, alt+ aдля курсивного «а»).
Lèse Majesté
Видите, вот с чем у меня проблема: «у вас была бы программа для кодирования данных» ... нет, нет. У меня нет программы для этого, и я не знаю ни одной программы для этого. Я также не знаю ни о каком формате файла, который может корректно обрабатывать байт, удаленный (не стертый) из начала файла поверх других ошибок. Я определенно согласен с тем, что это методы для увеличения плотности данных, но сейчас это не моя главная задача, это простота чтения / записи и защита от ошибок.
Джереми Сальвен
@ Джереми: Как я уже сказал, большинство форматов архивов имеют встроенную коррекцию ошибок, которая, кажется, работает достаточно хорошо для большинства людей. Но если вы хотите что-то специально разработанное для ручной записи, вам нужно написать или попросить кого-то написать что-то для вас. В противном случае вам лучше всего взглянуть на существующие приложения, предназначенные для передачи по каналам с высоким уровнем шума. Хотя самый простой вариант без учета плотности данных - это просто использовать файл RAR с высоким уровнем исправления ошибок, а затем повторить раздел заголовка 3 раза для тройного модульного резервирования.
Lèse Majesté
1

Мы использовали S-Records для этой цели. В каждой строке была простая контрольная сумма для обнаружения ошибок. Обычно все строки, кроме последней, имели фиксированную длину, поэтому маркер конца строки служил проверкой для вставок и удалений. Там не было проверки на отсутствие строк, хотя. Для этого мы просто посчитали количество строк. В основном файлы были короткими, менее 100 строк, но я помню, по крайней мере, один, в котором было 300 или более строк. Было очень утомительно печатать файлы в системе. Конечно, среди первых программ перенесенных таким образом был загрузчик;)

Отставной шпион
источник
0

Оптическое распознавание меток использовалось десятилетиями для создания машиночитаемых рукописных форм. На странице Википедии есть ссылки на несколько версий с открытым исходным кодом.

Школы давно используют OMR для тестирования; формы просты в использовании и чтении, а точность, как правило, лучше, чем ввод с клавиатуры. Для более высокой точности коммерческие производители, такие как Scantron и ReMark, могут создавать собственные формы.

Dour High Arch
источник
Это интересно, к сожалению, для работы требуется сканер или какая-либо другая система обработки изображений, подключенная к компьютеру.
Джереми Сальвен