Подскажите алгоритм кодирования с избыточностью

[Питерский2]

Доброго времени суток!
Буду очень благодарен за помощь. Стоит следующая задача: есть некий большой массив информации, допустим файл. Он разделен на достаточно большие фрагменты по 32КБ. Эти фрагменты могут теряться безвозвратно (не портится, а именно теряться; т.е. если информация есть, то она обязательно корректна, либо её нет). Нужен алгоритм, который будет для заданной входной совокупности корректных данных и максимально допустимого количества потерянных блоков генерировать информацию для восстановления, по которой эти потерянные блоки (заданные по порядковому номеру например) можно будет восстановить. Притом объем этой "информации для восстановления" должен быть как можно ближе к теоретическому минимуму (т.е. главное эффективность использования энергонезависимой памяти, быстродействие и расход ОЗУ роли не играет).
Быстрый гуглеж рассказал мне о кодах Рида-Соломона, но после краткого прочтения статьи в Википедии появились сомнения что это именно то что мне надо. Может есть готовые специализированные алгоритмы под мою задачу, используемые в архиваторах например?
С уважением!

[Pavia]

Матричное кодирование. С длинной блока допустим 256х8
256 бит=32 байта распределяем по блокам, как при раздаче колоды карт, как то принято в RAID6

Избыточные коды и коды чётности триплировать и распределить ленточно по блокам.

(25+256)/256=1,097

Если потерянных блоков может быть больше 1 то соотвественно увеличиваем размер матрицы 256x16 и так далее. При размере 256x256 получим полное дублирование.

[Pavia]

Питерский2
Короче я бы реализовал коды Хэмминга как самые простые и перетосовал бы как на картинке (или около того).





Пример сортировки


Тут немного подробнее с примерами в кодах Рида-Соломона,
http://computersciencelabs.blogspot....-of-raid6.html

[Питерский2]

Привет Pavia!
Спасибо за развернутые ответы!
Завтра я изучу все написанное тобой подробнее, потому что в пять утра уже голова не варит) Касательно кодов Хэмминга, то перетасовывать наоборот не надо, информация для восстановления типа передается по другому каналу, который считается 100% надежным, но я думаю что это уже детали реализации...
Что касается кодов Рида-Соломона, то я пока отверг их потому, что применение их "влоб" в моем случае не отвечает условию:

Притом объем этой "информации для восстановления" должен быть как можно ближе к теоретическому минимуму (т.е. главное эффективность использования энергонезависимой памяти, быстродействие и расход ОЗУ роли не играет).

Рассмотрим случай, когда допустима потеря одного 32КБ блока информации. Из свойств кодов Р-С (цитата из Википедии)

Код Рида — Соломона над G F ( q m ), исправляющий t ошибок, требует 2t проверочных символов и с его помощью исправляются произвольные пакеты ошибок длиной t и меньше

следует, что потребуется 64КБ дополнительно. Контрпример: посчитаем XOR всех 32КБ блоков и получим контрольный 32КБ блок. При потере одного из блоков (по условию задачи находить какой именно блок поврежден не надо, это станет известно из третьих источников, например контрольной суммы которая передается по защищенному каналу) XOR этого контрольного блока и всех оставшихся даст потерянный. Итого информация для восстановления занимает 32КБ против 64КБ у Рида-Соломона. К сожалению, я не представляю как распространить подобный подход на допустимое количество потерянных блоков больше 1. Интуитивно понятно, почему коды Р-С. в данном примере менее эффективны - потому что они позволяют отыскать и исправить 32КБ (32*1024*8 = 262144) произвольных ошибочных битов, но условия моей задачи таковы что эти 262144 ошибочных битов идут строго по очереди (фрагмент 32КБ),а не произвольным образом, и кроме того не нужно определять какие именно биты повреждены, следовательно коды Рида-Соломона оказываются избыточны. Вот если бы был алгоритм вроде кодов Р-С для которых "элементарной единицей" информации был бы не бит, а блок битов, то возможно это было бы то что нужно. Но мои познания в математике не позволяют додуматься до этого самому, да и велосипед изобретать не хочется, наверняка уже придумано до нас множество годных алгоритмов, но так как для меня эта область новая, я не в курсе где что искать))
Спасибо ещё раз за информацию, завтра отпишусь.
Хорошего дня!

[kvitaliy]

Сообщение от Питерский2

Эти фрагменты могут теряться безвозвратно (не портится, а именно теряться; т.е. если информация есть, то она обязательно корректна, либо её нет).

если вопрос стоит в восстановлении утерянной информации, а не именно написании алгоритма кодирования с избыточностью, то зачем информацию восстанавливать?
Передаёте нумерованные пакеты, если конкретный пакет потерялся безвозвратно, то не проще ли его передать заново?

[Питерский2]

kvitaliy, конечно проще повторить передачу, но задание именно в алгоритме)