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

Как то раз я выкачивал RAR архив, и он все время шел битым. Стал тестировать первую копию, сбой был гдето в начале. Скачал еще копию. Стал тестировать, сбой был гдето в конце. Было две битые копии... Тогда я взял расколол архивы пополам, и взял конец первого и начало второго. Так я получил цельный архив всего из 2-х копий =)))

 

Вы конечно же правы, но дело в том, что это не курсач, а ДИПЛОМ, и к сажалению тема уже утверждена.

 

sysprg

Самая главная и первейшая уловка, насколько я понял, позволяющая сразу ускорить обычное FFT почти в два раза, это использование наряду с +1, -1 еще пары более глубоких радиксов, чисто мнимых i и -i. Умножение комплексного числа на чисто мнимую единицу не многим сложнее чем на 1 и -1 и очевидно сводится к обмену мнимой и реальной частей. И вот тут в GF(p) нас может поджидать облом. Скажем, в GF(A000001) мнимой единицей будет 3E3A2B0. Как можно быстро умножать на такую хрень, я себе не представляю.

В поле GF(65537) с этим дела обстоят намного лучше, там i = 256, поэтому примение четвертых и более глубоких радиксов весьма целесообразно. Однако поле GF(65537) будет проигрывать предыдущему по размерности данных и числу допустимых блоков, поэтому лично мне не очень интересно.

 

dimsoft
прога обновилась до версии 1.84

теперь можно явно задавать размер блока-тома-кластера, а также избыточность в процентах!
То есть, наряду с конструкцией -wrr15000-1500, что означает 15000 блоков данных и 1500 блоков коррекции

можно юзировать типа -wrr4096v-10% - это означает 4096 байт в блоке и 10% избыточных блоков.

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

 

dimsoft

теперь правильные ключи такие для твоих целей:
-wt -r
-wrr16384v-100%

 

persicum
а где скачать ?

 

нашел

 

Согласен - обидно, что 2^32+/-1, 2^64+/1 и даже 2^128+/-1 - не простые числа. Длины же которую дает GF(65537) на DVD никак не хватит.

 

Кстати к вопросу о том методе, который использует многократные FWT ради работы в GF(2^q). Долго думал, смотрел этот код, статьи всякие читал и т.п. в результате написал-таки свое FFT-подобное преобразование над чистым GF(2^q) в очень упрощенном прототипном виде - чтобы проверить вообще факт работы и количество основных операций, но не соревноваться в скорости. Получается что-то асимптотически близкое к n * log(n) * log(log(n)). Но как ни крути, на размерах за сотни (и тем более тысячи и более) этот метод все равно проиграет GF(простое число), где можно использовать векторный аппаратный умножитель. Поэтому пока что думаю, что к сожалению на больших матрицах GF(2^p) представляет интерес только для аппаратных реализаций (при нынешней архитектуре CPU, в которой нет умножения в GF(2^p) - хотя аппаратно такое умножение проще обычного).

 

Зато есть другие здоровые простые, на которых можно сделать radix-4, radix-8 и даже radix-16 =))) Но боюсь, на это у меня уже никогда не хватит пороха... Кроме выбора самих чисел, для реальной проги нужно еще решать вопросы упаковки и другие сопутствующие задачи.

Поздравляю, это тянет на публикацию или изобретение. Я не встречал таких быстрых оценок ранее

Очень обидно за отсутствие умножения в процессоре двоичных полиномов. На фоне уже имеющегося арифмитического умножения оно далось бы инженерам абсолютно даром. А польза могла бы быть в crypto и для псевдослучайных чисел помимо всего

Векторный аппаратный pXOR тоже заруливает... Вообще, табличный Look-up умножитель для 16-бит может составлять серьезную конкуренцию арифметическому умножению в GF(p). Кстати, ICEGraphics ICEECC обновился до 2.7 и еще больше ускорил Look-up-16 за счет применения MMX.

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

Я все думал как использовать FWT не в GF(2^n), а в GF(p), где ему легко и вольготно. Хотел заменить некоторые или даже все свои FFT на FWT, но пока на это у меня нет достаточных познаний. Уж больно хочется послать подальше все эти умножения и сделать все на +1 и -1. Вы пишите, что код Хадамара имеет дистанцию n/2, это значит MDS?
А разве не любой MDS можно приспособить для ERASURES и получить чистый n ?

 

Прога обновилась до версии 1.85 - что нового:

1) убрал безумный счетчик на заголовке окна, который перегружал ОС обновляясь 10000 раз в секунду
2) досрочный выход из процедуры поиска блоков, если найдено достаточно для восстановления - ключ -mf

 

b]sysprg[/b]

Сижу и думаю, а можно ли применить Walsh Transform непосредственно в GF(2^n). В Wiki написано, что группа (1,-1,x) изоморфна (0,1,^) и что можно построить матрицу Хадамара-Уолша для нулей и единиц, если стартовать
с [ 0 1], а затем выписывать все натуральные числа подряд в двоичном виде и снизу реккурентно добавлять две матрицы от предыдущего шага. Я думаю, результат будет такойже, как если бы взять матрицу [1...-1] и 1 заменить на 0, а -1 на 1, и использовать xor вместо умножения.

В общем, если вернуться опять к 1 и -1, то под единицей можно понимать "взять число как есть", а под -1 - "взять число и инвертировать все биты".

Никак не пойму, как сделать Уолш-преобразование даже для матрицы 2x2 =(((
Если взять
1 1
1 -1

или
[0 1]'*[0 1]=
0 0
0 1

что тоже самое, то не получается трансформация для вектора из пары бит, как не крути =((( Не знаю, по каким законам ее производить.

 

Nothing

Заколбасил сегодня умножение-деление в GF(2^32) вообще без малейших таблиц и потенциирования =)))
Будет желание, почищу код от JMP

Код (Text):

1. function GF32_Mult(a,b:Cardinal):Cardinal; //input in eax,edx
2. asm
3.  push esi
4.  push ebx
5.  
6.  mov esi,GF32_Prime;
7.  
8.  xor ebx,ebx
9.  mov ecx,32
10. @lll:
11.  shr edx,1
12.  jnc @nobit
13.  xor ebx,eax
14. @nobit:
15.  shl eax,1
16.  jnc @noreduct
17.  xor eax,esi
18. @noreduct:
19.  loop @lll
20.  
21.  mov eax,ebx //result
22.  
23.  pop ebx
24.  pop esi
25. end;
26.  
27. function GF32_Inv(a:Cardinal):Cardinal;
28. var i,s,x:Cardinal;
29. begin
30.  s:=1;
31.  x:=a;
32.  for i:=1 to 31 do begin
33.   x:=GF32_Mult(x,x);
34.   s:=GF32_Mult(s,x);
35.  end;
36.  Result:=s;
37. end;

 

Программулька обновилась до версии 1.96, обеспечивая тысячекратно более мощные и более быстрые коды РыдаСоломона, нежели ICEECC и QuickPAR. Хе-хе...

Достигнуто строго последовательное читение данных с винтака, теперь скорость не падает с 50м/c до 2м/c из-за случайного доступа. Однако, это сделано не за счет специальных инкрементальных кодов как в ICEECC, а за счет транспонирования данных на винте и сурового свапежа... Ну ни че, можно обождать несколько минут ради такого дела.

Ключики для глобальной защиты DVD скажем 10 секторов в томе-пакете такие
crc32 -wt -r
crc32 -wrr20480v-fittodvd

У меня занимает минут 7-семь

 

А какое там сейчас поле используется в самом быстром методе с интерполяцией Лагранжа - GF(2^q) или по модулю простого числа?

 

ИМХО Лагранжеву интерполяцию за n log n в GF(2^n) еще никто не делал. Можете смело доводить до ума, публиковать/патентовать. Векторизуемость там хорошая, лучше не бывает, pxor/paddw. То есть на языке логарифмов нужно только складывать/вычитать.

Правда, мне трудно представить релиз GF(2^24) без таблицы на 48/64 метров, но этот вопрос както урезонивается.

Нельзя ли Вас попросить побенчить мой прог с Вашими разработками, а также с известным кодом на пр-нии Уолша с SSE2, последний в режимах 16 и 24 бит. Хотя там вроде даже 31 бит был... Интересно просто.

 

Не волнуйтесь, я не занимаюсь reverse engineering-ом Вашей программы. Но с интересом наблюдаю за появлением в ней новых методов. Поэтому и интересуюсь, произошел ли переход обратно на GF(2^q) (с модулярной арифметики). Что касается патентования - могу Вам помочь с этим, конечно, если возможно найти с Вами взаимовыгодные условия, и если Ваш метод имеет какие-то принципиальные отличия от уже описанного в существующих статьях Didier и в прочих.
Кстати патентование занимает минимум два года и патент легко могут оспорить любые люди, кто имеет статьи с доказательством их приоритета. Поэтому патентованием есть смысл заниматся - но это дело рискованное и не гарантированное по результатам. Даже если патент будет получен, не факт, что он принесет хоть 1$ - так как есть куча альтернативных методов вычисления кодов Рида-Соломона. Конкруенты просто реализуют что-то другое. Разница в скорости в два раза никого не смутит. Выгода патентования таких вещей, где нельзя закрыть все пути обхода - это только делать себе имя (если речь идет об авторе) или увеличивать оценочную стоимость компании в глазах инвесторов на переговорах (если речь идет о владельце имущественных прав). С моей точки зрения и то, и другое важно и нужно - но нужно отдавать себе отчет, что прямых денег с таких патентов не заработаешь (точнее - только на удачу).

Из-за умножений?

Да, нужно будет сравнить с той программой.
Но с моими разработками нельзя сравнивать напрямую, потому, что они ориентированы на RAID-подобные системы, где используются матрицы 32 x 32 и еще меньше. В этом случае FFT-подобные методы (как и преобразование Уолша) дают больше накладных расходов, чем пользы. Плюс на практике матрицы не квадратные, а типа 8 x 2 или 24 x 8. В результате Ваши методы проигрывают моему квадратичному в декодере и патентованному логарифмическому в encoder-е методу, причем в разы. Но это совершенно нормально, учитывая, что для Ваших методов какая-нибудь матрица типа 8 x 2 (RAID-6) это вырожденный предельный да еще и truncated случай, а не нормальное явление.
Глядя на Ваши успехи с имплементацией разных видов FFT, я планирую написать программу с FFT, для больших матриц. Но никак не доходит дело до этого, так как это скорее важный задел на будущее, чем практическая потребность. Сейчас прямого применения для нее нет (у меня). В теории применения есть, но не такие, где можно было бы очевидным образом сделать бизнес. Защита DVD и тому подобное - это очень узкие ниши. И при наличии в Интернете свободных и бесплатных исходников с преобразованием Уолша под SSE - непонятно, как кому-то продать свои программы (пусть даже они будут в 2-10 раз быстрее - при наличии бесплатных "академических" исходников практически всегда выбирают последние).

 

Кое-что удалось сравнить... Моя прога c SSE2 раза в три быстрее чем академическая FWT-SSE2. То есть скорость обработки где-то 10 м/c против 3м/c. Секрета конечно нет, просто другой алгоритм.

 

sysprg

Новый век привнес новое понимание в кодирование Рида-Соломона. Если в 70-х годах прошлого века под ним понимался почти исключительно остаток от деления информационного полинома на другой, то в новом веке любой MDS код может быть назван кодом Рида-Соломона, и для его построения могут использоваться различные матрицы, а также разнообразные ортогональные преобразования. С быстрыми преобразованиями Фурье и Лагранжа-Ньютона я уже более-менее свыкся, а вот преобразование Уолша пока что за пределами моего понимания. Технически оно выполняется наиболее просто, но вот смысл и польза его покрыты густым туманом, хотя литература и примеры использования не испытывают недостатка.

Не могли бы Вы просветить засранца и вдохновить его на новые подвиги, растолковав подоходчивее пользу от FWT? Как правило, эти трансформаты не пригодны для циклической свертки, что вызывает у меня панические затруднения, но в некоторых случаях такая свертка осуществима, как и некоторые другие виды сверток. Скачал книгу “Ортогональные преобразования в цифровой обработке сигналов”, но толку от нее как от “Самоучителя игры на скрипке”, без хорошего гуру не обойтись =(((

 

Не совсем так - это известно очень давно, но только сейчас стало "модно" об этом говорить. Собственно сами создатели кода в 60-х годах уже описали его через FFT, в том числе с разными вариантами использующими Fermat Primes. Использование интерполяции Лагранжа это тоже можно сказать "классика", как минимум 80-е годы прошлого века она уже использовалась в обосновании патентованного алгоритма декодирования Berlekamp-Welch. Просто раньше все это было уделом одних только математиков, а сейчас начали появляться и программные реализации, например, Ваша.

Обычное Фурье в модулярной арифметике будет работать быстрее за счет аппаратного умножителя. Смысл FWT в том, что с его помощью можно сделать GF(2^m). Вашей программе это IMHO не нужно - нет проблемы "вынести" одно число за пределы блока для перехода между GF(prime) и 32-битными целыми. Вам ведь нужно быстродействие максимальное. А FWT в небезызвестных нам работах применено конкретно для работы в GF(2^m), что оправдано только когда жестко стоит задача использовать конкретно GF(2^m) и ничего другого. Есть и другие методы аналогичные FFT и при этом над GF(2^m), но они еще намного более непонятные, чем FWT (с моей точки зрения). Некоторые вообще настолько заумны и завязаны на последние достижения в области теории чисел, что я даже общего их смысла не улавливаю при просмотре статей.