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

=) дока

 

persicum
Спасибо за наводки по реализации кода РС в поле 2^32. Я наконец-то сделал синдромный декодер и для 2^32 и даже для 2^64.

Именно так и сделал умножение в поле. Оказалось просто и понятно.

В 32 раза-то я их раздул, но ведь там надо проверять биты, чтобы не ксорить попусту. Т.е. если бит 0 установлен - ксорим со значением из таблицы 0, а если нет - то нет (ксорим с нулем), я пока смог сделать только на обычных регистрах, без SSE2, т.к. использую там CMOV. Может потенциально это и быстрее, но на моих тестах пока что нет.

Вот это честно пока не осилил. Но вроде как там умножение выполняется одной единственной командой MUL, что радует (если научиться как-то жить с переполнениями).

Одну нашел и без подсказки . Да, код там 8 или 16 битный, зато используется FFT, что и дает логарифм. С другой стороны можно доделать и для 32-х разрядного кода, может займусь как-нибудь. Но FFT однозначно надо изучать в части перемножения матриц.

Но самое главное - потестировав столь длинный код в поле 2^32 в сочетании с матрицами, я пока что разачаровался в нем. Тормоз он страшный, возни с ним немеряно, а выигрыша я так и не увидел. Громадный интерливинг вместе с коротким кодом дают зависимость почти O(n). Ну а синдромный декодер нравится мне больше матричного, т.к. он самодостаточен: сам определяет и позиции ошибок и исправляет их, ну и позволяет делать "подсказки", увеличивая исправляющую способность кода. Причем в подсказках можно ошибаться, он не порушит данные, а вот если ошибиться с позицией ошибки в матричном декодере - может случится страшное (а может и нет, это как повезет).

p.s. мне в синдромном декодере пришлось еще вычислять мультипликативные обратные в поле и быстро выполнять "потенцирование", и тоже пришлось помучаться придумывая как это "затабличить" хитрыми алгоритмами, не вылезая в 16Гб памяти

 

Приятно осознавать, что моя сумасбродная деятельность кому-то принесла пользу

Для синдромного так и есть, а для матричного кодирования лучше XOR-based, но до тех пор, пока разжиревшие в m раз данные поля GF(2^m) не вылезут за размер кэша... Дальше будет нужна декомпозиция...

Имитация необыкновенно длинного XOR-регистра

Код (Text):

1.     @loop:
2.         bsf ebx,eax
3.         jz @quit
4.         mov edx,[esi+4*ebx]
5.         pxor xmm0,[edx]
6.         pxor xmm1,[edx+16]
7.         pxor xmm2,[edx+32]
8.         pxor xmm3,[edx+48]
9.         pxor xmm4,[edx+64]
10.         pxor xmm5,[edx+80]
11.         pxor xmm6,[edx+96]
12.         pxor xmm7,[edx+112]
13.         btc eax,ebx
14.         jmp @loop
15. @quit:

Легко до чрезвычайности, если знать как! =))) Рациональный подход ни в коем случае не требует наивного 3% избытка (32/31 или 33/32) ни в каком виде, даже в запакованном. Поскольку стандартный процессор не умеет перемножать полиномы, но зато менее чем за 10 тактов перемножает 32-разрядные числа, то почему бы и нет?

Эта работа мной уже проделана. Кодовое слово на миллион или может полмиллиона элементов в объеме DVD кодируется за 30мин без SSE2. Поддержку SSE2 реализовал сегодня, когда встрою ее в программу, надеюсь получить прирост скорости раза в 2.5-3, а это уже будет психологически комфортно.

Мои 32-разрядные коды как матричные так и FFT вообще не требуют никаких таблиц, ну может только пару десятков корней из единицы. Но мне проще, поскольку у Вас все кодовые слова декодируются независимо и нужно решать обратную задачу каждый раз по новой, а мне со стираниями достаточно ее один раз решить а потом получить вектор весов и на него домножать все время, пока идет обработка пакета

 

Это снижает статус алгоритма с детерминированного до вероятностного. Бодяжных кодов, наследников Геллагера, сейчас уйма развелось, там сложность n log (1/excess), полная глобальная защита на одном XOR и это круче, чем просто интерлив.

Интерлив - это блок-диагональная матрица
Геллагер - это разреженная матрица

 

А интересно, какое умножение в GF(2^32) быстрее, с помощью 7 таблиц или же в регистрах процессора типа этого?

Код (Text):

1.  xor ebx,ebx //результат
2.  mov ecx,32
3. @lll:
4.  shr edx,1 //второй множитель
5.  jnc @nobit
6.  xor ebx,eax //первый множитель
7. @nobit:
8.  shl eax,1
9.  jnc @noreduct
10.  xor eax,esi //редуцирующий полином
11. @noreduct:
12.  loop @lll

 

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

 

Как я уже говорил (эта справедливая критика первоначально принадлежит устам ICE-GRAPHICS), движение количества блоков может происходить не только в сторону уменьшения вследствие их порчи, но и в сторону увеличения вследствие их подкачки.

Допустим, у нас такой протокол, сначала передаем информационную часть и крохотные контрольные суммы, потом определяем число подчисток и докачиваем корректирующие пакеты. Так вот, выигрыш детерминированного кода будет в том, что установив уровень порчи в 3 блока из 10 тыс запаса к примеру, вы можете докачать эти три блока и исправить информацию. А с бодяжными и интерливными кодами очевидно будут проблемы. Скаченные 3 блока из общего избытка очевидно не смогут вылечить НИФИГА. Три скаченных блока равносильны потере остальных 99997, тут и интерлив и все эти LT и LDPC обламаются, поскольку они хорошо работают только с большой совокупностью блоков, но не с тремя.

Вот в этом то и выигрыш заключается.

 

Интерлив вообще лишен смысла для многих моделей канала с ошибками. А вот LT-подобные и LDPC коды не нужно ставить в один ряд с интерливом - они просто не ориентированы на такую ситуацию, когда принят почти весь файл и проблема в том, чтобы докачать 3 контрольные суммы. Их используют, например, для каналов, где высок процент потерь и где нет проблемы передать лишние блоки, где проблема именно в высоком проценте потерь и нужна высокая скорость кодирования и декодирования.
Все "детерминистические" идеальные коды в силу природы своей требуют, чтобы мы включили в каждый выходной блок КАЖДЫЙ входной блок (даже в самых изощренных алгоритмах все равно нужно выполнить это условие идеального кода). LDPC и LT-подобные коды нарушают это требование, теряют абсолютную надежность, становятся "вероятностными" - но зато они дают огромный выигрыш в скорости кодирования – так как далеко не каждый (!) входной блок используется для расчета каждого из выходных блоков.
И еще для LDPC есть soft-decision декодеры, а аналогичный по характеристикам soft-decision декодер для RS - это что-то из области мечтаний теоретиков, а не из области практики (правда soft-decision декодирование интересно только для аппаратных реализаций).

 

Как я уже сказал, мои 32-битки матричная и синдромная работают совсем без таблиц. Но интересно посмотреть, что такое Вы изобрели. В принципе, потенциирование можно было бы вычислить просто как бинарную степень pow(generator,a) и тут тоже можно обойтись совсем без таблицц. Но мне даже и потенциирование не нужно. Для FFT нужно только затабличить несколько n-th Root и все. Правда, многие источники советуют явно держать в памяти длинный вектор развернутых twiddle-factor'ов для ускорения, но мне и это лень.

 

sysprg

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

 

Согласен, что в пределе так и есть. Но наличие единиц, разумно расставленных за пределами этой диагонали, именно сильно снижает вероятность невосстановимой ошибки по сравнению с тривиальной структурой из единичных блоков. Хотя это и неочевидно (что снижение вероятности невосстановимой ошибки будет сильным при примерно том же суммарном количестве единиц, что и в матрице с квадратными единичными блоками на диагонали).
Согласен, что интерлив в принципе близок по свойствам к кодам коррекции на рассеянных матрицах. Есть даже коды (turbo-codes), которые по сути на нем базируются как на строительном блоке, но извлекают пользу при декодировании из обратной связи между несколькими простыми сверточными кодами связанными interleaver-ом.

 

Кстати замечу, что LDPC-коды в режиме декодирования, когда мы не знаем позиций ошибок и с soft-decision декодером намного превосходят RS-коды по восстанавливающей способности. Турбо-коды тоже превосходят RS в таких конфигурациях. Поэтому в нескольких стандартах связи приняли за основу турбо-коды вместо старой "классической" комбинации RS + Витерби, а в новых стандартах часто используют LDPC. Но RS-коды непобиваемые для конфигураций с hard-decision декодером и известными позициями ошибок. И когда хотят достичь предела, ставят комбинацию из какого-нибудь турбо-кода или LDPC и еще жесткого RS енкодера/декодера вдобавок к нему...

 

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

Не утруждая себя выводом точных формул, чего я бы не смог проделать при всем желании, проделал натурный эксперимент, матлабовский исходник прилагается. Сравнивал вероятность восстановления кодового слова (40,20) над полем вещественных чисел для диагональной, интерливной и нерегулярной LDPC-шной матриц равной плотности в 1/5, и плотной. Плотная моделировала код Рида-Соломона

Код (Text):

1. % код (n,k)
2. clear all;
3. n=40;
4. k=n/2; % 100% избыток
5.  
6. m=diag(ones(k,1));  %матрица идентичности
7. c=diag(rand(k,1));  %проверочная матрица
8. m=[m; c];           %объединенная матрица
9.  
10. %Gallager LDPC(1/5) matrix
11. %for i=1:k,
12. % for j=1:k,
13. %  if randint(1,1,[1 5])==5,
14. %   c(i,j)=rand;
15. %  else
16. %   c(i,j)=0;
17. %  end;
18. % end;
19. %end;
20.  
21. fail=zeros(k,1); %отказы
22.  
23. for nl=1:k; %число потерянных символов
24.  nr=n-nl;   %число оставшихся символов
25.  
26.  disp(nl);
27.  
28.  for i=1:500; %набираем статистику путем 500 испытаний
29.  
30.   %выбор случайных неповторяющихся позиций
31.   ep=[];
32.   ep(1)=randint(1,1,[1 (n+1-nr)]);
33.   for j=2:nr;
34.    ep(j)=randint(1,1,[(1+ep(j-1)) (n+j-nr)]);
35.   end;
36.   d=m(ep,:); %выделение оставшихся символов
37.  
38.   %если ранг меньше k, то (полное) восстановление невозможно
39.   if rank(d)<k, fail(nl)=fail(nl)+1; end;
40.  
41.  end;
42.  
43. end;

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

 

А почему "несовершенство"? Для случая стираний матричное декодирование хорошо будет работать и по быстродействию (если поскипать умножения на 0), единственная пожалуй беда - придется инвертировать очень большую матрицу общим методом O(n^3), что ненужно даже для RS, так как там матрицы инвертируются за O(n^2). Матрицы, которые инвертируются быстрее, чем за O(n^3) в массе своей работают хуже "псевдослучайных" для большого количества блоков (и запатентованные обычно, но это не всех волнует). Как еще можно это декодировать, без итеративных алгоритмов типа believe propagation с soft-входом? Через biparite граф для всяких фонтанных кодов. Тогда можно все свести чисто к xor. Но опять-таки ваша же программа показывает, что на очень большом количестве блоков казалось бы "неправильные" методы с GF(p) работают быстрее "идеального" GF(2^m) из-за всяких долбанный кэшей современных CPU. Поэтому не факт, что декодирование через граф будет работать быстрее матричного метода. Другие же методы декодирования, о которых я читал - они ориентированы на soft-in (с вероятностями вместо символов на входе) или если даже они жесткие, то их задача попытаться избавится от ошибок, не зная где они, и скорость декодера не главное, а главное как близко к Shannon limit они подошли.
За картинку с вероятностью сбоя для interleave - спасибо!

 

окей, вы все такие умные тута, я смотрю; вот и попробуйте тогда мне объяснить: почему каждый раз когда я читаю http://www.wasm.ru/forum/search.php?action=show_new, натыкаясь взглядом на этот тред, я читаю: "Психоустойчивое шеллкодирование"? .\

меня это немного начинает беспокоить .\\

 

Напрасно иронизируете. Эта ветка является самым авторитетным и полным источником информации по помехоустойчивому кодированию, содержимое которого доступно для понимания неспециалистам, т.е. так называемым “хакерам”.
Вот здесь мужик докторскую защищает по сабжу

http://vak.ed.gov.ru/common/img/uploaded/files/vak/announcements/fiz_mat/14-04-2008/TormasovAG.doc

а тут мы говорим простым языком о весьма непростых вещах. А чем моя прога хуже?
Там есть и слайсы, и SIMD, и даже Reed-Solomon 32-разрядный, причем я знаю не один метод перемножения 32-разрядных полиномов как докторант, а по крайней мере пять =)))

Специфика любого кодирования такова, что эффективно оно может быть выполнено только на языке ассемблера, поэтому в моей проге очень много асма. Вместе с тем, мне покласть на Винду, MessageBoxA, InvokeProcess, WinAPI и системные вызовы, все это прячет от меня язык высокого уровня. Наверное, это психоз, не иначе =)))

Попытки Криса Касперски донести коды RS до широких масс особого успеха не имели, поскольку хацкеры в лице МЫЩЪХ предпочли выдрать готовую DLL из NERO, а не написать что-то свое. Да тут сам черт голову сломит с этим Бэрлекампом-Месси и авторегрессионным спектральным анализом… Касперски повторяет распространенную ошибку юзеров кода RS – использование полного арсенала математических средств для декодирования подчисток вместо банального решения системы линейных уравнений.

Был еще деятель DrAF,
http://art-drobanov.narod.ru/
но он быстро скис, поскольку его C# проект работает в десятки раз медленнее асмовых релизов для аналогичных алгоритмов, хе-хе вот тебе и хваленая JIT-компиляция… Вместо 15% получаем тормоза в десятки раз!!! =)))

 

sysprg
Кроме кубического обращения матрицы есть и другая беда для матричного LDPC. Дело в том, что матрица обратная разреженной является уже не разреженной, а плотной. Стало быть, скипать там уже больше нечего. Поэтому то LDPC исправляет ошибки не хуже RS, что обратная матрица плотная. Вот я и не стал включать в программу шипко разреженные матрицы, ибо тогда возможна ситуация, когда кодирование занимает 5 минут, а декодирование несколько суток. Хороший вариант для open key криптографии. =))) Я не знаю, как промышленные релизы обходят эту проблему.

 

Да, есть проблема. Я у себя использую обратную трассировку через biparite граф - нахожу блоки, где недостает одной операции и последовательно восстанавливаю их. Но эта техника хороша для фонтанных кодов с вероятностной структурой. Они надежны только вероятностно - на самом же деле точным прицельным ударом по маленькому (!) количеству блоков можно убить весь закодированный файл. Для этих кодов нельзя сказать, что "n" дополнительных блоков ГАРАНТИРОВАНО достаточно для восстановления. Можно говорить только о крайне низкой вероятности невосстановимой ошибки. Эти коды хороши для связи - когда можно дослать еще один блок и восстановить все. Особенно учитывая их свойство rateless, удобное для peer-to-peer сетей. Но для защиты CD такой код уже не так хорош - потому, что при неудачном раскладе маленькое повреждение выведет его из строя полностью. Зато декодируется и кодируется фантастически быстро...

 

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

 

У меня на этот счет как раз противоположная точка зрения. Я много сил потратил на понимание и вывод формулы для вероятности успешного декодирования LDPC, много статей скачал… Но когда уже знаешь что-либо, это кажется особенно простым. Так и формулу можно упростить и считать, что для вероятности неуспеха 10^(-10) требуется 23.03*Sparsity дополнительных блоков. Для 1/10 стало быть 250 блоков максимум, а с ростом размера матрицы число необходимых доп. блоков будет даже меньше (чудесным образом).

Так вот, “вероятностность” LDPC не является каким-то недостатком, можно задать код с любой заданной степенью вероятности на уровне обычных ХЭШей. Скажем, свалить такой код будет также невероятно, как подогнать CRC64 у файла на 1G, изменив случайно всего 64 каких-нибудь бит. Хотя это вполне возможно. Дело просто в более плавной, а не порогообразной как у RS границы декодирования. А если дополнительных символов достаточно, то разницы между RS и LDPC вообще нет. Тонкие различия в способности декодировать проявляют себя только когда уже совсем мало дополнительных блоков, когда уже все впритык.

Другое дело, что для связи могут использоваться не слишком неосуществимые вероятности, например 10^(-6), и очень разреженные графы… Я подозреваю, что линейная скорость O(n) может достигаться если только плотность матрицы падает с ее ростом, иначе, если число отведений остается постоянным несмотря на увеличение размеров матрицы. Тут действительно становится страшновато, когда в матрице на 10000 входов имеется всего лишь “three per column” ненулей. Но у меня в проге плотность фиксирована, чем больше матрица, тем надежность все выше и выше. Поэтому я пока остановился на 20000 блоков LDPC, но скоро буду кодировать через FFT тыщщ под 200000 и без всякой головной боли на счет вероятности. FFT32 уже готово, только житейский прессинг мешает все оформить и выложить.