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

Имею честь предложить для тестирования и для игрищ свою незатейливую консолевую программу для помехоустойчивого кодирования файлов.
http://persicum.front.ru /flashcard/crc32.rar

Высокопрофессиональные виндовые мультипроцессорные-мультипоточные “конкуренты” для каждодневного использования с форумом и техподдержкой живут здесь:
www.ice-graphics.com/ICEECC/IndexR.html
http://quickpar.org.uk/
Так что вопрос что лучше, юзать или не юзать не ставится.
Конечно хуже и конечно не юзать =)))

Недостатки:
1) Консольное приложение без GUI, три страницы ключей для вызова =)))
2) Однопроцессорная
3) Однопоточная, загрузка и счет не разделены на разные потоки, в результате чего при кодировании DVD теряется 5-10 минут на подкачку, когда вычисления прерываются
4) Простейшая “модель памяти” – матрица сидит в памяти целиком, а вектора-сообщения забивают оставшуюся память под завязку, никакой фрагментации матрицы-векторов с учетом размера доступного RAM, КЕШ-памяти, размера блока и файлов не происходит. Самоадаптации проги к количеству наличийствующих разных иерархий памяти тоже не происходит.
5) Программа использует файлы подкачки гигантских размеров, подстать нужен второй пустой HDD

Достоинства:
1) Консоль запрограммирована на распознание отдельной клавиши, Enter жать не придется =)))
2) Программа использует SSE2 и существенно ускоряется от его присутствия в процессоре
3) Реализован не один как у Айса и Пара алгоритм RS16V, а целых пять алгоритмов, из которых четыре полностью независимы и используют совершенно разный код, а один различается только матрицей. Их скорость работы в разы и в десятки раз превышает RS16V. Но они нужны все, т.к. каждый из них лучше для каких-то определенных целей, нельзя оставить только один алгоритм и упразднить все остальные.
4) Наконец-то реализован Reed-Solomon 32-бит вместо 16-битного RS16V. Теперь мощь одного проца используется целиком, а не на половину. Формальное требование в 16Гигов RAMа успешно преодолено. И конечно, RS32 ничего бы не стоил, если бы он тормозил в сравнении с RS16. Как и полагается, реализованный RS32 работает в ДВА раза быстрее элементарно из-за размерности шины-регистра. Самый быстрый в мире релиз кодов Рида-Соломона теперь у меня, а не у Айса.
5) Хотя прога и использует файлы подкачки, но зато открыто и можно указать путь для временных рабочих файлов. А вот Айс и Пар используют файлы подкачки не всегда, но зато втихоря и не известно где они лежат и хватит ли там места.


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

Но она будет развиваться в направлении безошибочности и устойчивости.
Все воспроизводимые глюки, которые можно словить с небольшим набором файлов под отладчиком, будут по возможности исправлены. Так что тестируйте, играйтесь так сказать. Бенч-марки прилагаются, не все так плохо. В сравнении с Айсом и Паром можно получить выигрыш в разы и в десятки раз даже на живых многогиговых тестах. Торопитесь с тестированием! Не пройдет и полугода, как Айсы и Пары спиндюрят все представленные новые алгоритмы без всякой благодарности и указания первоисточника. Тогда тестировать будет уже нечего…

Для работы с подобными программами необходимо иметь представление о томах.
Том (или блок) – наименьшая единица информации, целостность которой контролируется целиком и которая также подлежит полному исправлению без конкретизации, сколько именно, какой инфы там искажено или утрачено. Изменен ли один бит, или том потерян целиком – результат совершенно один и тот же – том считается полностью утраченным. Обычный размер тома – несколько метров.
Том данных – возникает при виртуальном разбиении исходных файлов на участки по размеру тома
Том коррекции – возникает при умножении томов данных на матрицу кодирования.
При декодировании любой том коррекции может заменить утраченный том данных.
Экстра-Том, Лишний том коррекции, запасной том коррекции – сохранный том коррекции, найденный сверх необходимого числа утраченных блоков данных. Если утрачено к примеру 5 блоков данных, а найдено 7 блоков коррекции, то мы будем иметь 2 экстра-блока. Экстра блоки требуются для некоторых алгоритмов включенных в программу, обычно 30 штук. Много это или мало? Если вместо 500 блоков коррекции произвести 530 их штук так чтобы 30 штук было запасных – и при этом быстродействие возрастет в 4 раза – то почему бы и нет если есть место?

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

Успехов в тестировании!!!
Канонический сырец кодека Рида-Соломона RS16C прилагается для любознательных.
Канонический - без малейшей оптимизации.

 

Вот сижу и думаю... По уму написанная процедура перемножения матриц должна определять размер кэша первого и второго уровней и фрагментировать свой код в зависимости от этих размеров... Возможен и другой подход к проблеме фрагментации (иначе, декомпозиции) - произвести замер производительности и выбрать оптимальный код. Мда, когда-то на заре становления 32-разрядного режима казалось, что наличие свап-файла автоматически решит все проблемы с наличием свободной памяти... Решит-то оно решит, но не порадует, ибо свапеж и тормоза будут такими, что без явного задания в программе физической RAM все же не обойтись. Теперь те же проблемы встают с кешом, не известно даже, благо это или зло - его наличие. Почему для умножения вектора на матрицу нельзя написать просто:

for i:=1 to m do begin
b:=0;
for j:=1 to n do begin
b:=b + M[i,j]*a[j];
end;
end;

Потому что этот очевидный код будет работать в 20 раз медленнее неочевидного...
А если размер задачи настолько велик, что не помещается даже в RAM, что как раз и имеет место для обычного DVD диска, то встает вопрос об оптимальной фрагментации как матрицы, так и буферов подкачки...

Свапеж между различными иерархиями памяти, кешом разных уровней, кешом и пямятью, памятью и диском может съедать львиную долю времени, если программа написана не по уму.

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

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

Вышла в свет новая версия проги - уже 1.70
Реализован пятый независимый алгоритм кодирования - TBPC. Это очень быстрый вероятностный алгоритм кодирования, который требует для декодирования 15 запасных томов. Опять же встает вопрос - много это или мало? Для 10 томов иметь 15 запасных - это черезчур много, а для 500 - это лишних 3%, для тысячи - только лишь 1.5%. Поэтому в пределе его надежность не уступает гарантированному Риду-Соломону, который естественно не требует никаких запасных томов. Как я уже сказал, задача правильной фрагментации представляется мне неподъемной, но в новом методе применена упрощенная фрагментация, основанная на различном количестве используемых регистров mmx. А поскольку сами эти регистры нехилые по размеру, то и фрагментация получается неслабой с четко выраженным оптимумом и выигрышем в 4-5 раз.

Ну а теперь самое приятное, побенчим новый алгоритм с софтовым лидером помехоустойчивого кодирования - ICEECC. заодно поучимся работать с прогой, которая скажем прямо крайне недружелюбна и недоходчива.

Будем защищать 1Гиг файлов, всего 6000 штук разной мелочевки. Возьмем 10000 блоков данных и 1000 блоков коррекции. Машина класса coreduo.
Запускаем Айс, помечаем файлы в его браузере.
Нажимаем плюс-create
Source block count ставим 10000
Number of recovery blocks ставим 1000
Видим, что избыточность стала 10%
Жмем ОКей, процесс запустился...
По независимым часам на кодирование ушло 12 минут времени на двух ядрах.
Важно указать, что собственные часы Айса частенько подвирают раза в полтора,
им не следует доверять.

теперь мой прог.
сначала нужно создать таблицу контрольных сумм файлов - crc32.tab
обходим рекурсивно текущий каталог и все подкаталоги.
crc32.exe -wt -r
безусловно, это требует некоторого времени, но мы его замечать не будем, т.к. работа с таблицами непосредственно к кодированию не относится. их можно смотреть в Фаре, пополнять, тестировать задолго до принятия решения создать тома коррекции.

Теперь создаем тома коррекции
crc32.exe -wrr10000-1015 -mu1g -tm4
на все про все ушло 2 минуты на одном ядре, причем 1.5 минуты на счет и 30 секунд на подкачку. 1015 было набрано потому, что не забываем про 15 запасных резервных тома, которые требует алгоритм с ключем -tm4.

И того мой прог в шесть раз быстрее с SSE2 чем Айс на двух ядрах но с другим алгоритмом.

Если ты, Айс, будешь когда-нибудь читать эти строки, то хочу предостеречь тебя от заимствования чужих алгоритмов, ибо ты столько раз писал на русских и англоязычных форумах что 1024 томов данных - это самая оптимальныя защита для DVD дисков и ничего лучше не придумаешь для ошибок которые идут пачками, народ тебя просто не поймет, зачем нужно кодировать с 10000 блоками данных и что делать со стопками уже защищенных дисков.

 

Я для проверки целостности файла использую функцию из RtlComputeCrc32 ntdll.dll вроде-бы и не сложная но как тут понять, что она всё-таки вычисляет

Код (Text):

1. RtlComputeCrc32 proc Divider:DWORD, pData:DWORD, DataSize:DWORD  ;7C9614F1
2.    mov eax, Divider
3.    xor ecx, ecx
4.    not eax
5.    .if DataSize>ecx
6.       .repeat
7.          mov edx, pData
8.          movzx edx, byte ptr [ecx+edx]
9.          xor edx, eax
10.          and edx, 0FFh
11.          shr eax, 8
12.          xor eax, dword ptr [edx*4+offset TableCRC ]
13.          inc ecx
14.       .until ecx>=DataSize
15.    .endif
16.    not eax
17.    ret
18. RtlComputeCrc32 endp  ;7C961524
19. .data
20. TableCRC  dd 0     ;7C961528
21.           dd 77073096h, 0EE0E612Ch, 990951BAh, 76DC419h, 706AF48Fh
22.           dd 0E963A535h, 9E6495A3h, 0EDB8832h, 79DCB8A4h, 0E0D5E91Eh
23.           dd 97D2D988h, 9B64C2Bh, 7EB17CBDh, 0E7B82D07h, 90BF1D91h
24.           dd 1DB71064h, 6AB020F2h, 0F3B97148h, 84BE41DEh, 1ADAD47Dh
25.           dd 6DDDE4EBh, 0F4D4B551h, 83D385C7h, 136C9856h, 646BA8C0h
26.           dd 0FD62F97Ah, 8A65C9ECh, 14015C4Fh, 63066CD9h, 0FA0F3D63h
27.           dd 8D080DF5h, 3B6E20C8h, 4C69105Eh, 0D56041E4h, 0A2677172h
28.           dd 3C03E4D1h, 4B04D447h, 0D20D85FDh, 0A50AB56Bh, 35B5A8FAh
29.           dd 42B2986Ch, 0DBBBC9D6h, 0ACBCF940h, 32D86CE3h, 45DF5C75h
30.           dd 0DCD60DCFh, 0ABD13D59h, 26D930ACh, 51DE003Ah, 0C8D75180h
31.           dd 0BFD06116h, 21B4F4B5h, 56B3C423h, 0CFBA9599h, 0B8BDA50Fh
32.           dd 2802B89Eh, 5F058808h, 0C60CD9B2h, 0B10BE924h, 2F6F7C87h
33.           dd 58684C11h, 0C1611DABh, 0B6662D3Dh, 76DC4190h, 1DB7106h
34.           dd 98D220BCh, 0EFD5102Ah, 71B18589h, 6B6B51Fh, 9FBFE4A5h
35.           dd 0E8B8D433h, 7807C9A2h, 0F00F934h, 9609A88Eh, 0E10E9818h
36.           dd 7F6A0DBBh, 86D3D2Dh, 91646C97h, 0E6635C01h, 6B6B51F4h
37.           dd 1C6C6162h, 856530D8h, 0F262004Eh, 6C0695EDh, 1B01A57Bh
38.           dd 8208F4C1h, 0F50FC457h, 65B0D9C6h, 12B7E950h, 8BBEB8EAh
39.           dd 0FCB9887Ch, 62DD1DDFh, 15DA2D49h, 8CD37CF3h, 0FBD44C65h
40.           dd 4DB26158h, 3AB551CEh, 0A3BC0074h, 0D4BB30E2h, 4ADFA541h
41.           dd 3DD895D7h, 0A4D1C46Dh, 0D3D6F4FBh, 4369E96Ah, 346ED9FCh
42.           dd 0AD678846h, 0DA60B8D0h, 44042D73h, 33031DE5h, 0AA0A4C5Fh
43.           dd 0DD0D7CC9h, 5005713Ch, 270241AAh, 0BE0B1010h, 0C90C2086h
44.           dd 5768B525h, 206F85B3h, 0B966D409h, 0CE61E49Fh, 5EDEF90Eh
45.           dd 29D9C998h, 0B0D09822h, 0C7D7A8B4h, 59B33D17h, 2EB40D81h
46.           dd 0B7BD5C3Bh, 0C0BA6CADh, 0EDB88320h, 9ABFB3B6h, 3B6E20Ch
47.           dd 74B1D29Ah, 0EAD54739h, 9DD277AFh, 4DB2615h, 73DC1683h
48.           dd 0E3630B12h, 94643B84h, 0D6D6A3Eh, 7A6A5AA8h, 0E40ECF0Bh
49.           dd 9309FF9Dh, 0A00AE27h, 7D079EB1h, 0F00F9344h, 8708A3D2h
50.           dd 1E01F268h, 6906C2FEh, 0F762575Dh, 806567CBh, 196C3671h
51.           dd 6E6B06E7h, 0FED41B76h, 89D32BE0h, 10DA7A5Ah, 67DD4ACCh
52.           dd 0F9B9DF6Fh, 8EBEEFF9h, 17B7BE43h, 60B08ED5h, 0D6D6A3E8h
53.           dd 0A1D1937Eh, 38D8C2C4h, 4FDFF252h, 0D1BB67F1h, 0A6BC5767h
54.           dd 3FB506DDh, 48B2364Bh, 0D80D2BDAh, 0AF0A1B4Ch, 36034AF6h
55.           dd 41047A60h, 0DF60EFC3h, 0A867DF55h, 316E8EEFh, 4669BE79h
56.           dd 0CB61B38Ch, 0BC66831Ah, 256FD2A0h, 5268E236h, 0CC0C7795h
57.           dd 0BB0B4703h, 220216B9h, 5505262Fh, 0C5BA3BBEh, 0B2BD0B28h
58.           dd 2BB45A92h, 5CB36A04h, 0C2D7FFA7h, 0B5D0CF31h, 2CD99E8Bh
59.           dd 5BDEAE1Dh, 9B64C2B0h, 0EC63F226h, 756AA39Ch, 26D930Ah
60.           dd 9C0906A9h, 0EB0E363Fh, 72076785h, 5005713h, 95BF4A82h
61.           dd 0E2B87A14h, 7BB12BAEh, 0CB61B38h, 92D28E9Bh, 0E5D5BE0Dh
62.           dd 7CDCEFB7h, 0BDBDF21h, 86D3D2D4h, 0F1D4E242h, 68DDB3F8h
63.           dd 1FDA836Eh, 81BE16CDh, 0F6B9265Bh, 6FB077E1h, 18B74777h
64.           dd 88085AE6h, 0FF0F6A70h, 66063BCAh, 11010B5Ch, 8F659EFFh
65.           dd 0F862AE69h, 616BFFD3h, 166CCF45h, 0A00AE278h, 0D70DD2EEh
66.           dd 4E048354h, 3903B3C2h, 0A7672661h, 0D06016F7h, 4969474Dh
67.           dd 3E6E77DBh, 0AED16A4Ah, 0D9D65ADCh, 40DF0B66h, 37D83BF0h
68.           dd 0A9BCAE53h, 0DEBB9EC5h, 47B2CF7Fh, 30B5FFE9h, 0BDBDF21Ch
69.           dd 0CABAC28Ah, 53B39330h, 24B4A3A6h, 0BAD03605h, 0CDD70693h
70.           dd 54DE5729h, 23D967BFh, 0B3667A2Eh, 0C4614AB8h, 5D681B02h
71.           dd 2A6F2B94h, 0B40BBE37h, 0C30C8EA1h, 5A05DF1Bh, 2D02EF8Dh  ;7C96152C
72. .code

 

Похоже что CRC32 вычисляет...
Правда, готовые таблицы нужны как правило не для рассчета, а для взлома CRC.

Ну раз запостил сюда, можешь сравнить с тем, что моя прога вычисляет
параметры вызова:
crc32.exe имя_файла

 

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

несжатые:
энтропия <100%, хи-квадрат >> 1

сжатые:
100%, >> 1

шифрованные:
100%, ~1

 

Программа обновилась до версии 1.72
Включена пара новых методов кодирования.
Большого смысла в этом не было, разве для спортивного интереса, посмотреть на новое красивое поле.
Теперь сижу и думаю, какой метод юзать самому? =)))

Как раз на одном ядре Айс быстрее Пара в 1.5-2 раза из-за подстройки под интерлив памяти.

 

Ух ты, у нас сегодня юбилей - первая 1000-сяча просмотров. Сообщений об ошибках нет пока, это радует =)))

 

persicum
Приветствую.
В свое время делал коды Рида-Соломона над полями GF(255) и GF(65535). Но так и не осилил 32-битные коды, там уж больно большие таблицы перевода получаются, а без таблиц кодер шибко тормозной. Впрочем, основное достоинство длинных кодов я эмулировал громадным интерливингом. А как вам удалось реализовать их?
И еще где там можно использовать SSE2? У меня основной цикл кодера - это просто XOR двух областей памяти (как в матричном варианте, так и без него)... Правда области памяти не выравнены, ибо XORить надо с произвольного байта.
Насчет скорости кодера - не мерял с ICCECC, но у меня вроде не сильно медленнее . Но меня интересовала оптимизация декодера, ибо он сильно тормознее по определению.

 

32-разрядные коды Рида-Соломона можно реализовать по крайней мере одним из шести нижеперечисленных способов:

1) С использованием таблицы дискретных логарифмов на 16Гиг
2) Умножение полиномов в регистрах процессора на ASM, аналог обычного умножения для процессоров без встроенной операции, только вместо ADD там XOR
3) Через 16-битные умножения с таблицами. Карацуба требует три умножения, в столбик выходит четыре, а в литературе рекомендуют пять. В этом есть какой-то смысл, но я не знаю почему.
4) Через 8-битные умножения. Требуется семь таблиц размером 65536*4, и 16 XOR
5) Путем перехода от GF(2^32) к GF(2). При этом полином 2^32 представляется в виде матрицы 32x32. Перемножение требует в среднем 16 XOR, в худшем случае 32 XOR
6) Путем перехода от GF(2^32) к GF(p), где p - составное число Ферма-Мерсена на 33-бит или 32-бит, например FFF00001. Умножение - обычное арифметическое MUL. Однако изоморфизма нет, требуется учет переполнений.

Моя прога реализует методы 5 и 6, а поскольку таблиц совсем не требуется, то польза от SSE2 состоит в использовании pXOR, кучи регистров и двойного умножения.

ICEECC давно уже потерял лидерство, т.к. масштабирование в смысле многопроцессорности там очень слабое, только 15% прироста от второго процессора
MultiPAR к примеру от второго ядра ускоряется пропорционально и работает в два раза быстрее ICEECC

Алгоритмические реализации кодов Рида-Соломона можно разделить на три класса:

1) Наивные
Кодирование O(n^2), декодирование O(n^3)
Примеры: ICEECC, QuickPAR, MultiPAR, RecoveryStar

2) Квадратичные
Кодирование O(n^2), декодирование O(n^2)
Пример: моя прога с ключем -tm3

3) Линейные
Кодирование O(n log n), декодирование O(n log^2 n)
Пример: есть две проги в сети, не скажу какие =))) Но коды опять же 16-битные.

Линейное кодирование работает практически мгновенно, и время обсчета заданной группы файлов не зависит от числа блоков разбиения. Надеюсь реализовать у себя линейное 32-разрядное кодирование через два-три месяца, если не возникнет непреодолимых для меня преград. Очень сложная математика для профана... Хотя 32-разрядное FFT уже сделано, это вселяет надежду.

Сейчас моя прога persicum's CRC32 реализует следующие фичерсы:

1) 32-разрядное квадратичное кодирование, обращение матрицы не требуется!!! В принципе, число блоков можно было бы сделать очень большим, много больше чем 32768 для 16-разрядных кодов. Однако поскольку матрица сидит целиком в памяти и кодирование все же нелинейное, то ограничение на 32768 блока остается.

2) множесто суррогатных матриц с нулями, которые работают в 5,10,100 раз быстрее благородного Рида-Соломона-32,
но требуют за это 5,15 или 30 лишних тома для декодирования. Если счет томов идет на сотни и тысячи, то это совсем крохотная плата за повышенные скорости, поддерживается число блоков вплоть до 200000.

3) Подгонка кода под заданный размер, скажем как довесок к диску или на отдельный пустой диск

4) Адаптивное чтения диска с ошибками, высокоуровневое с виртуальным размером сектора. Если процедура встречает дефект поверхности, она не a bird его часами, а идет на противоположный конец диска и читает с конца к началу в обратном направлении. При встрече новых деффектов процедура дробит шаг и рекурсивно повторяется.

 

Аx да, про выравнивание... У меня выравнивание-16 везде и всюду. А если вдруг требуется стартовать со случайного байта, то сначала вызывается ALU -шная процедура. Если вдруг не позднее чем за 15 вызовов случайно возникает выравнивание, то происходит переключение на SSE2

 

Спасибо за информацию про 32-х битный код. Пока не до конца ясно как к нему подступиться, но буду разбираться в ваших наводках. Интересно, а что будет быстрее: обычный короткий код с громадным интерливингом или 32-х битный код без него? Просто интересно, действительно ли имеет смысл воевать за 32 бита, ведь суммарная исправляющая способность в обоих вариантах будет одинаковая, только по другому рспределена (но это решается подбором алгоритма интерливинга)?

Глянул в свой алгоритм. Для кода (n,k) кодер имеет сложность O(n*(n-k)), а декодер вроде как O(n*k), без учета интерливинга ес-но. С интерливингом в k зависимость надо умножить на k, но при больших k я использую очень короткие коды, типа (15,11), которые "затабличил" почти целиком, так что скорость кодера приближается к линейной на гигабайтных объемах.
А почему вы не стали приводить примеры программ с логарифмическими зависимостями? Было бы интересно почитать хотя бы описание алгоритма или ссылки на работы в которых эти описания приведены.

И еще, может подскажете, куда копнуть или чего почитать про суррогатные матрицы для ускорения декодирования RS в разы за счет добавления лишних кодов?

 

А чего там разбираться?

Метод №4 требует 7 таблиц для остатков от чисел вида AB,AB0,AB00,...,AB000000, всего лишь 7*65536*4 = 2 метра памяти вместо 16Гигов.

Метод №5 не требует вообще никаких таблиц и поэтому идеально подходит для MMX и SSE2, знай себе КСОРь и все дела. Однако требует предпроцессинга для перевода части проблемных данных в матричный вид 32х32, а на деле раздувания в 32 раза.

Метод №6 - это да, жестокий морально-нравственный трахаторий с числами Мерсена или Ферма, поскольку их размер точно не вписывается в 16- или 32-бит допустимых значений. Методы выхода из ситуации могут быть самые разные, от беспомощного оперирования с некруглыми 17-битными или 31-битными числами с записью их на диск до более изощренных (как у меня и в некоторых других прогах, есть приемы, вследствие которых переполнения просто не появляются в конечном результате)

Моя прога развивается строго последовательно, поэтому все мои последущие матрицы могли появиться на свет лишь после реализации предыдущих. Поэтому мне нужно было все.

Наверное мы говорим немного на разных языках. Меня интересуют только ERASURES и только огромные коды не менее GF(2^32) и GF(2^64), огромные матрицы. Поэтому мне перемеживания-интерливинг совершенно не нужны, что лучше,
100 слов перемешать 100 раз или сразу 10000 слов? Конечно, код который содержит 10000 слов будет несоизмеримо лучше. У меня нет задачи ловить уж совсем раздробленные ошибки, когда счет подчисток идет на сотни миллионов, как у вас. Как и ICEECC и QuickPAR, моя прога работает с секторами(в другой терминологии блоки или тома). Так что число подчисток в моем случае это десятки тысяч отсилы. Когда реализую линейный алгоритм, можно будет довести число подчисток до миллиона. Дальше наверное смысла нет, поскольку это число по порядку уже равно числу секторов на DVD.

Англисский термин это Linear Sparse Coding. Разбавляете свою матрицу нулями сколько не жалко и все дела. При этом есть чудесный математический момент - после некоторого критического размера разреженная матрица совершенно неотличима от плотной. Дополнительные коды нужны для достижения критического размера. Если критический размер не достигнут, то матрица ничего исправлять не может. Один разреженный блок вообще не может исправить нифига, поскольку там практически одни нули. Задача состоит в оценке критических размеров для матрицы заданной плотности над заданным полем.

 

Так потому-что я над этим упорно работаю и это очень сложно для неспециалиста!!!
Пока только просекаю, что Быстрое Преобразование Фурье FFT(x) это

1 1 1 1 1...
1 w1 w1^2 w1^3...
1 w2 w2^2 w2^3... * (x)
1 w3 w3^2 w3^3...

То есть по сути мгновенное умножение матрицы Вандермонда на вектор!
Чувствуете, какой потенциал там зарыт? =)))

 

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

111000000
111000000
111000000
000111000
000111000
000111000
000000111
000000111
000000111

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

Пример широко известной программы которая работает на 8-битном коде RS(255,223) c огромным интерливом - это DVDisaster

Пример программ безо всякого интерлива: ICEECC, QuickPAR, и конечно моя прожка persicum's CRC32
Программы без интерлива либо исправляют данные на все 100%, либо не исправляют ничего, не может быть частично восстановленных данных или частично вылеченных файлов. В этом смысле они лучше интерливных=локальных.

Программы на разреженных матрицах сочетают в себе скорость работы интерливных программ и глобальность(полное восстановление) безинтерливных программ. Пример: моя прога с некоторыми ключами.

 

Кстати, не подскажете как можно кодить за O(n^2) без явного построения матрицы в памяти, a то у меня на это уходит 1 Гиг?
Аналог ваших RS(15,11) это к примеру матрица 40000x10000, для кода-32 это чепуха, но матрица будет весить 1.6G =(((

 

Спасибо за ответы
Буду разбираться с полученными наводками, знаниями и подсказками по мере появления свободного времени. Ну и по мере появления вопросов буду спрашивать, надеюсь вы будете помогать. Тема-то интересная, но мало где описанная, увы.

Возможно у нас немного разные подходы к решению в общем-то близких задач по восстановлению данных. Я изначально реализовывал алгоритмы так, чтобы иметь возможность применить их в микроконтроллерах, где нет столько памяти, чтобы содержать огромные таблицы или десятки матриц. Упор в оптимизациях я делал на декодировании, т.к. это более сложный процесс по опредедению. Тем не менее, я понял, что ваш подход тоже вполне годится, и как только реализую код GF(2^32) (правда декодер для него писать - это та еще задачка) попробую применить и его, чтобы посмотреть насколько это хорошо. В свое время я отказался даже от кодов GF(2^8) на микроконтроллере и кодировал все в поле GF(2^4), что позволило мне обойтись вообще ~5 байтами памяти и 352 байтами неизменяемой таблицы (без учета интерливинга).

Почему? Это еще вопрос: что лучше частично восстановленные данные или не восстановленные вообще... Интерливинг - это лишь способ перераспределить восстанавливающую способность кода, только и всего. Даже линейный интерливинг позволяет восстанавливать 100% данных (разумеется, когда это теоретически возможно).

Ну если матрица получается большая, зачем ее вообще строить? Классический алгоритм кодера работает без таблиц и за O(n^2), и основан на вычислении остатка от деления входных данных на порожденный полином. И никаких матриц . На коротких кодах я использую только таблицу умножения в поле Галуа, которая генерируется на лету по параметрам кода (для кодов в GF(2^8) максимальный размер такой таблицы будет кажется 43520 байт, а вот максимальный размер матрицы, если ее использовать - 3699200 байт для любого кода). На длинных кодах, типа GF(2^16), я кодирую используя только таблицы перевода элементов поля в индексы и обратно - 262144 байта, это работает менее эффективно, т.к. умножение приходится делать "руками" и в цикле появляются лишние операции помимо XOR, но зависимость остается квадратичной. Что делать для кода GF(2^32), я честно пока не знаю. Да, для ускорения декодирования еще используется таблица деления (или таблица мультипликативных обратных для длинных кодов), чтобы ускорить главные циклы. Ну а в кодере для очень коротких кодов (15,11) разворачиваются все циклы, и подвергаются сквозной оптимизации.

 

Приятно иметь дело с человеком, профессионально сведущим в этой области. Буду восполнять пробелы в самообразовании... На ум приходят только коды, исправляющие по остатку один бит, ну пару максимум.

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

Я учился кодам Рида-Соломона по описанию Артема Дробанова к проекту Recovery Star. Там сказано, берешь срез=вектор, умножаешь на матрицу, получаешь корректирующие коды. Для декодирования инвертируешь матрицу по Жордану и все дела. Когда я уточнил, что при декодировании правильнее сосредоточиться не на полной матрице, а на подматрице, которая соответствует найденным коррекционным символам и потерянным информационным, то сразу получил статус математического консультанта проекта =))). Причем подматрица должна быть невырожденной, что не так то просто соблюсти для произвольной комбинации ошибок.

 

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

В самом простейшем случае так и есть. Посмотрите обычную crc-32 - она может исправить 1 бит данных. Но исправлять байты данных тоже несложно - возьмите оперирующий байтами код Хемминга (7, 4) - он исправляет любой 1 байт. А ведь его несложно расширить и до мегабайтов, и тогда он будет исправлять мегабайт ошибок! И реализуется он достаточно примитивно. Хотя я понимаю, что все это не чета кодам RS, ибо у них всех чудовищные ограничения

Классический алгоритм кодера - это просто алгоритм деления полиномов в поле Галуа, реализованный ес-но через умножение и сложение (чтоб быстрее было), и имеет сложность O(k*(n-k)) (я ошибся в прошлом сообщении, написав что n*(n-k)). Разумеется, умножение логично "затабличить", ну а сложение - это просто XOR. Самая главная засада в том, что деление нужно проводить до конца, ведь нужен же полный остаток. Впрочем, есть и другие методы реализации деления, например, последовательным подбором частного (порожденный полином ведь известен заранее, значит заранее можно подсчитать и его степени).
А вот классический декодер - это страшная конструкция, которую в одном сообщении просто так и не расписать.

 

=) Помехоустойчивое кодирование было в примере у зомби вроде , как по английски будет помехоустойчивое кодирование ?

 

Я знаю только про RAID - это Избыточный Массив Независимых Дисков. Так вот, почти все вышеупомянутые проги и моя в том числе реализуют не просто какие-то там коды Рида-Соломона, которые болтаются препарированной лягушкой в исходных кодах, а именно RAID. Причем железные райды могут иметь ну может несколько жестких дисков отсилы, а софтовый райд может иметь тысячи блоков. Если найдено тысяча неповрежденных блоков (как полезных так и избыточных в сумме), то может быть восстановлена тысяча информационных блоков.