Нужна блочно-ориентированная схема исправления ошибок
Я храню много файлов различной длины на блочно-ориентированном носителе (фиксированный размер, например, 1024 байта). При чтении файла каждый блок будет либо отсутствовать, либо исправляться (без битовых ошибок и т. П.). Пропущенные блоки являются случайными, и необязательно какая-либо последовательность к пропущенным блокам. Я хотел бы иметь возможность пересобрать весь файл, если количество отсутствующих блоков ниже некоторого порога, который, вероятно, зависит от схемы кодирования.
Большая часть литературы, которую я видел, имеет дело с последовательностями битовых ошибок в потоке данных, так что это, похоже, неприменимо.
Простой подход состоит в том, чтобы взять N блоков за раз, а затем сохранить блок, содержащий XOR из N блоков. Если один из N блоков отсутствует, а контрольный блок отсутствует, то отсутствующий блок может быть восстановлен.
Существуют ли схемы исправления ошибок, которые хорошо подходят для этой проблемы? Ссылки на литературу или кодекс приветствуются.
3 ответа
Посмотрите на коды Рида-Соломона:
http://en.wikipedia.org/wiki/Reed%E2%80%93Solomon_error_correction
Лучшее место для начала поиска - это спецификация Parity Volume Set. Самая большая проблема, с которой вы столкнетесь, - это дополнительные метаданные, необходимые для каждого блока. Плюс, эта спецификация ориентирована на сжатые архивные файлы.
Еще одна полезная ссылка - документация в формате parchive в формате 2.0 (на основе, но более ориентированной на блоки, чем в parchive 1.0). См. QuickPar для хорошего разбора того, как 2.0 улучшился на PAR 1.0.
Ознакомьтесь с кодами Raptor ( https://en.wikipedia.org/wiki/Raptor_code). На данный момент это самые передовые коды фонтанов.