Помехоустойчивое кодирование

Проблема в том, что RS допускает движение корректирующих блоков в восходящем порядке, от малого числа к большому, например подгрузка по FTP.

А LDPC допускает движение корректирующих блоков исключительно в нисходящем порядке, от большого числа к меньшему, например вследствие порчи части их на DVD диске.

Поэтому быстрый RS для большого числа блоков является желанным.

 

Рыжий Тигер, если ты реализуешь RS32, то сможешь существенно ускорить свое кодирование - но только в таком виде как оно есть, ну может с интерливом 3 вместо 6 отсилы. А если хочешь защищать сектора глобально, копай в сторону LDPC и родственных методов.

Пример реализации алгоритма в моей программе (только штобы протащиться, для такого кодирования как тебе нужно заголовки будут слишком велики. Но в твоем случае ты можешь определять сектора просто по факту их читабельности на CD)

crc32 -wrr400000-6000 -tm2

Твоя вожделенная задача ГЛОБАЛЬНОГО кодирования CD занимает всего 1.5 минуты у LDPC.

 

[---]

 

[---]

 

Дык, наконец сообразил, что Вам ответить. Вы юзируюте XOR-овые RAID-библиотеки, в которых размер GF динамически подстраивается под размер матрицы и определяет, сколько раз нужно XOR-ить для получения произведения элементов поля Галуа. Для GF(2^4) нужно ксорить 4 раза, для GF(2^16) нужно ксорить уже 16 раз, а для GF(2^32) - все 32 раза! Поэтому получаете значительное замедление для больших матриц.

Математика несложная, но везде разная (самая разнообразная!) и такая, чтобы в каждом из используемых мной полей произведение элементов Галуа выполнялось ЗА ОДНУ машинную инструкцию. Вот как все просто... =))) А Вы говорите о превосходной работе с кэшем, памятью - чего там и в помине нет...

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

 

Да, это примерно так и есть. Я не пишу потому, что уже и сам разобрался в причинах быстродействия Вашей программы с помощью профайлера памяти который следит за performance counters CPU и сообщает о числе операций с памятью, обращений к регистрам и т.п. - чтобы понять причины быстродействия превышающего в разы RAID-подобные библиотеки (на XOR-ах). Все дело в том, что обычная RAID-библиотека действительно читает 32 раза блок и XOR-ит его с данными - в 32 этапа для поля GF(2^32), точно как Вы говорите. На этом она несет большие потери в быстродействии. У Вас же судя по отчетам профайлера все содержательные вычисления идут в 128-битных XMM-регистрах без обращений к памяти и последовательно получается по одному 32-битному слову выходной контрольной суммы, которое ОДНОКРАТНО пишется в память. Нет чтений из памяти промежуточных результатов и перезаписей много раз, как в (условно назовем их) RAID-библиотеках. Запись одна, а в RAID-библиотеках их много. Поэтому им нужен аппаратный свехдлинный XOR, иначе они Вам проигрывают в быстродействии.

 

Разница в том, что interleave вообще не повышает корректирующую способность (в пересчете на объем поврежденных данных), а только снижает ВЕРОЯТНОСТЬ потери, за счет распределения блоков. Повысить же корректирующую способность истинную можно либо за счет каскадирования корректирующих кодов, либо за счет увеличения разрядности поля (для обсуждаемых нами методов). Но повышение разрядности для MDS-кодов ведет к сильному замедлению, поэтому и применяют другие, "неидеальные" коды, в частности LDPC. Они обладают большей корректирующей способностью, чем 8-битный RS + interleave. Но не удивительно, что подавляющее большинство не специалистов толком в этом не разбирается.
Что касается сотен и тысяч дополнительных блоков, так это зависит от многих факторов. Во-первых, есть много разных кодов, по своим математическим свойствам относимых к семейству Low Density Parity Check. Есть такие, которые гарантируют восстановление имея фиксированное "N" дополнительных блоков. Есть "вероятностные" конструкции, которые дают только оценку вероятности восстановления, без жестких 100% гарантий. Во-вторых, число дополнительных блоков варьируется в зависимости от желаемого быстродействия и вероятности невосстановимой ошибки. Можно сделать действительно тысячи дополнительных блоков - для миллионов исходных.

 

Правда LDPC в другом. Можно сделать код, который при кодовом слове в миллион символов и разведении в 10000 раз будет требовать только один(!) лишний блок, а то и вообще ни одного. Вот в это как раз никто не верит. Но в целях быстродействия на практике число доп. блоков может быть и больше.

 

Чудес не бывает, если код не будет требовать лишних символов вообще (или будет требовать 1 символ), то время кодирования будет примерно такое же, как у RS-подобных кодов. Поэтому не зря сейчас LDPC коды используют в стандартах связи (LDPC коды уже стандартизованы ETSI/ITU-T в некоторых коммуникационных протоколах) именно в режиме, когда они порождают много дополнительных символов, но зато быстро кодируются/декодируются.

 

>Чудес не бывает

Ну вот, доктор, Вы тоже не верите...=)))

 

ginger_tigra, косяки со знаками в арифметических полях GF(p) начинаются уже сразу в момент систематического кодирования!

Если C=Q*G+R, то я ведь не могу к кодовому слову C просто приставить R в конец как в GF(2^m), похоже что нужно -R приставлять?

 

Что будет быстрее при прочих равных - не верю. Ведь производных кодов от RS много разных и их тоже можно по-разному кодировать и декодировать. Я думаю, что время O(n * log(n)) это теоретический предел для кода, который не требует дополнительных избыточных символов. RS коды могут достичь этого предела хотя бы в теории. Поэтому ускоряться там дальше некуда.

 

Добрый день всем!
Все это конечно замечательно, интересует как (какими ключами) можно сделать RAID на DVD, когда, например, на 5 DVD болванок идет 1-а, 6-ая чисто под коды восстановления, так чтобы эта волшебная болвнка могла, в случае чего, восстановить любую из предыдущих 5-ти с данными (на случай если болванка с данными потеряется, исцарапается или взорвется в недрах привода)!!
Как реализовать это, какие ключики у проги крутить?
Также хотелось бы что-нибудь услышать про плугин для FAR'а, о котором упоминалось в списке ключиков к проге...

 

Это хорошо, что нашлись наконец заинтересованные юзеры, а не только воришки моих идей и алгоритмов. =)))

В принципе, написать несложную прогу для кодирования дисков в RAID 5:1 проще простого, достаточно переXORить сектора в указанном порядке:

Disk1 [Sector1] [Sector2] [Sector3]….
Disk2 [Sector1] [Sector2] [Sector3]….
Disk3 [Sector1] [Sector2] [Sector3]….
….
Parity [Sector1] [Sector2] [Sector3]….

При этом
Parity [Sector1] = (Disk1 [Sector1]) xor (Disk2 [Sector1]) xor (Disk3 [Sector1])…
Parity [Sector2] = (Disk1 [Sector2]) xor (Disk2 [Sector2]) xor (Disk3 [Sector2])…

Все это будет замечательно и очень быстро работать, пока с некоторой малой вероятностью произойдет сбой в одной из колонок кратностью 2 или выше:

Disk1 [Sector1] [_Bad_] [Sector3]….
Disk2 [Sector1] [Sector2] [Sector3]….
Disk3 [Sector1] [_Bad_] [Sector3]….

Такая ошибка останется неисправленной.

Моя прога, как и ICEECC и QuickPAR, свободна от этой опасности, поскольку не использует ИНТЕРЛИВ, данные защищены ГЛОБАЛЬНО путем их разбиения на блоки. Однако, эти блоки не могут покрыть каждый конкретный сектор по отдельности, счет которых исчисляется на миллионы в случае DVD дисков. По крайней мере, не могут в текущих версиях этих программ, коль скоро они не доросли до использования FFT. У меня оно будет реализовано в ближайшую пару месяцев, надеюсь.
Стало быть, эти программы решают некоторые модельные задачи защиты данных без оглядки на то, каков истинный характер возможных повреждений DVD дисков имеет место быть в действительности. Айс советует кодить не более 2000 блоков, Рыжий_Тигер советует покрывать каждый сектор CD мощным 16-битным RS, 6x60000 блоков с интерливом ШЕСТЬ.

Поэтому я не знаю, с чего даже начать, каково должно быть число используемых блоков?
Сейчас программы моя, ICEECC и QuickPAR способны потянуть от силы 10-20 тысяч блоков, не более.

Попробуем замерить чистое время кодирования для 30G данных, 15% избытка:
RS32, 5000 блоков – 2ч 40мин
LDPC, 30000 блоков – 50 мин

Порядок действий таков:
1) Создаем директории Disk1, Disk2, Disk3…, копируем туда диски.
2) Рассчитываем контрольные суммы-64бит
сrc32 –wt –r –n2
3) Если отдаем предпочтение Риду-Соломону и 5000 блокам, тогда
crc32 -wrr5000-fittodvd -ed -mu1.5g -sn10 -hr10 -tm3
4) Если отдаем предпочтение LDPC и 30000 блокам, тогда
crc32 –wrr30000-fittodvd -ed -mu1.5g -sn10 -hr10 –tm2
5) После кодирования проверяем, что все файлы на месте
сrc32 –rt
6) Проверяем еще, что все блоки тоже на месте
сrc32 –crr

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

Что касается простейшего FAR плагина, рекомендую его только для просмотра содержимого файла CRC32.TAB. Все остальные действия должны быть строго осмысленными, в крайнем случае юзайте ВАТ-файлы.

 

Таак, тогда еще вопрос созрел.

А есть у проги такой режим как у прог конкурентов (ICEECC etc.) когда вся инфа упаковывается в один или несколько файлов с защитой, а уже потом извлекается из них??

В ICEECC такой режим включается когда избыточность делаем больше 100%.

И если такой режим есть, то надо ли при этом самому заботиться о защите файлов
crc32.sum и crc32.tab?

 

Такого режима у меня нет, чтобы все провсе упаковать в один файл. Всегда отдельно лежат:
crc32.tab - контрольные суммы файлов
crc32.sum - контрольные суммы блоков
Директория CRC32_Vol, там лежат:
*.bkp - копии файлов TAB и SUM
*.bin - сырая избыточная информация без заголовков.

При желании запаковать все это в один файл можно использовать RAR без сжатия или ISO.
При сортировке файлов по именам, что имеет место в Неро, копии заголовков должны перемежаться с BIN-файлами и таким образом быть защищенными путем разнесения в пространстве(плоскости) диска.

Вот что есть у меня интересного, так это множество несовершенных кодов, которые работают быстрее совершенного Рида-Соломона. Например, в примере выше алгос с ключем -tm4 имеет чистое время кодирования всего 40 минут в сравнении с 2ч 40 мин для ключа -tm3. Но за это требует лишних ПЬЯТНАДЦАТЬ блоков на восстановление, т.е. эффективность сходится к чистому Риду-Соломону как N/(N+15), что в пределе равно единице.

Это круче, чем например у кодов с постоянным overhead на уровне 5%, как тут например:
http://www.telemultimedia.ru/art.php?id=56

 

sysprg

Скорее всего, так оно и есть. Квазилинейный RS требует n log n операций, линейный LDPC требует n log (1/excess) опереций. Но я бы не доверил свои файлы линейному LDPC. Хотя, он у меня на очереди после линейного RS в планах на реализацию. Что касается квадратичного LDPC как оно сейчас у меня есть, то он требует не относительный избыток в процентах, а абсолютный не слишком большой избыток между 30-300 блоками по ситуации. Поэтому в пределе сходится к RS, но имеет сложность k*O(n^2) со в сто раз меньшим k.

 

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

 

Я тоже за ручки, а где плугин можно скачать? :-P

 

Берешь Custom.ini из архива и добавляешь сюды:
C:\Program Files\Far\Plugins\MultiArc\Formats\Custom.ini