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

Ищу статью на http://vx.netlux.org/ , там был расписан пример , что то не могу найти. Кто помнит название статьи ?

 

http://mirror.sweon.net/z0mbie/selfcorr.html

 

blast, ну это совсем ясельки... Хотя именно так работает система коррекции ошибок всех известных архиваторов, RAR, FreeArc и т.д. Беда в том, что не все комбинации ошибок можно исправить таким способом. Однако, некоторые программеры умудряются закодить этот простейший XOR в виде многомерных кубов, а это видимо уже кое-что.

Всем для начала рекомендуется к прочтению статься известного хацкера Хриса Касперски:
http://www.insidepro.com/kk/027/027r.shtml

 

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

А между тем кодирование Рида-Соломона можно представить как умножение сообщения на матрицу кодирования, а декодирование - как решение системы уравнений или обращение матрицы кодирования. Это все не выходит за рамки простейших представлений по линейной алгебре, которую проходят на первом курсе любого ВУЗа. Сырец для 16-битного кодека есть в архиве моей проги, для него нет неразрешимых комбинаций ошибок которые он не смог бы исправить.

 

persicum
на чем писал ?

 

На Ся легко и просто , подстрочно переводится... Вместо while юзай for

 

У меня возникло сомнение в "безматричности" классического Рида-Соломона, если реализовывать его не в железе, а софтовым методом. Табличный метод CRC32 к примеру требует таблицу 256*4 для быстрого вычисления остатков. Применяя табличный метод взятия остатков скажем для 16-битного кода и полинома 1000-ной степени, для быстрого взятия остатка мы должны завести таблицу 65536*1000*2 и лазить туда последовательно он головы к хвосту, прибавляя затабулированные остатки O(N^2) раз. Чем не матрица?

 

На счет использования FFT для кода Рида-Соломона: это очень интересная идея и мне будет очень интересно узнать, что у Вас в итоге получится.
Я не уверен в том, что итоговый код будет работать быстрее обычной реализации на классическом “квадратичном" умножении матриц. Возможно, что я чего-то недогоняю, так как мне недостает фундаментального математического образования, но когда я реализовал прототип алгоритма RS на FFT, в нем количество умножений действительно уменьшилось до вроде как O(n log^2 (n)). Но количество сложений (XOR) по-прежнему в моей реализации оставалось квадратом от "n". Плюс добавилось множество разных конверсий и перебросок данных. Конечно, это была программа-прототип, чисто для проверки алгоритма, написанная напрямую по научной математической статье, через рекурсию. И ее можно было существенно улучшить, избавившись от рекурсии в реализации, разнесение четных и нечетных элементов вектора реализовать через битовые инверсии индексов и так далее, но сдается мне, что количество сложений все равно останется квадратичным. Конечно, я могу и ошибаться, возможно, что у меня неоптимальная реализация. Поэтому мне будет очень интересно узнать Ваше мнение о количестве сложений/перемещений данных в случае применения FFT над конечным полем.
Второй вопрос, связанный с FFT - это нарушение патентов. По-моему невозможно реализовать RS с FFT не нарушив несколько патентов. Ну и соответственно реализация имеет чисто исследовательский интерес, а коммерчески она бесперспективна без покупки патентных лицензий за миллионы $. Боюсь, что при использовании FFT при любой коммерциализации проекта последуют судебные иски или к тебе, или к твоим клиентам. Аналогичные проблемы возможны и с некоторыми видами LDPC. Не знаю, какие конкретно коды Вы используете - не все, но ряд видов LDPC тоже покрыт патентами.

 

Идея мягко говоря не моя. =))) Насколько я помню, Cooley-Tukey изобрели FFT в 1965, а уже в семидесятых его использовали по назначению.

I. S. Reed, T. K. Truong, and L. R. Welch, "The Fast Decoding of Reed-
Solomon Codes Using Fermat Transforms," IEEE Trans. Information Theory,
vol. IT-24, no. 4, pp. 497-499, July 1978.

Недогоняете понятие Complexity т.е. сложность (я люблю называть ее трудоемкость).
Если у одного O(N^2) а у другого O(n log n), то начиная с некоторого N второй будет обязательно быстрее. Это точь-в-точь как с пузырьковой и быстрой сортировками. Для маленьких N первая быстрей, а для больших N – вторая быстрей.

FFT – это не проблема. У меня есть как рекурсивная, так и нерекурсивная процедуры.
Есть еще также не бинарная, а квадро-процедура. Она будучи рекурсивной работает быстрее в три раза чем бинарная нерекурсивная.

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

Да не боись ты! Метод разделяй-и-властвуй работает за N log N по определению. Хочешь чуда – ты его получишь. В моей проге уже есть пару чудес, которые и не снились Айсу – мгновенное кодирование LDPC и мгновенное обращение матрицы RS32. Что касается обращения матрицы у LDPC – оно наивно-кубическое, но в 2000 раз более быстрое чем у ICEECC.

При этом есть еще один приятный момент. Сложность кодирования фиксированного объема информации имеет сложность на единицу меньшую чем перемножение матриц,
Стало быть если при квадратичном умножении время растет линейно в зависимости от числа блоков разбиения, то при линейном умножении оно будет не зависеть от числа блоков разбиения. В ICEECC это называется Source Block Count. Так вот, можно будет выставлять хоть 10000, хоть миллион блоков, а время кодирования в первом приближении будет меняться слабо.

ИМХО Вы путаете это с Быстрым преобразованием Хартли

А откуда их достают, эти четырре сольда?

 

Понятное дело, что не Ваша, мне просто интересно будет увидеть в действии Вашу реализацию.

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

Вот чтобы реализовать это все мне пришлось конвертировать сами данные, а не только коэффиенты в матрицах. Возможно, я стормозил и можно было оставить данные в покое. Но в итоге данные у меня восстановились и теперь меня интригует вопрос - а можно ли было достичь того же результата, но делая все конверсии между базисами только в матрицах, и не трогая сами данные?

А что, разве время обращения матрицы существенно влияет на общее быстродействие? Это ведь не связь, тут блоки большие. Я думаю, что расходы времени на обращение матрицы будут составлять малую долю от общего объема работы. Это не так?
Кстати, а что за LDPC Вы используете - на матрицах какой формы? Псевдо-рандомные или какие-то осмысленные?

Что такое линейное умножение? Линейное умножение существует вроде как только для матриц Коши в вещественных числах (multi-pole method), и оно приближенное. Умножение через FFT не линейное, оно логарифмическое все-таки. У нас разные термины или Вы знаете какой-то на самом деле линейный алгоритм?

Я знаю точно, что есть патент на чипы использующие FFT для RS. Есть так же куча патентов, где упоминается использование FFT для быстрого умножения матриц. Но я не берусь утверждать, что хоть один из них закрывает алгоритм для RS, а не какие-то узкие частные случаи в определенных системах. Буду только рад, если там нет такого патента.

 

Это не так страшно. Глубокое невежество, отсутствие специального образования, резюме и рекомендаций – это непременный залог успеха в деле создания файловых RAID-подобных кодеров, ибо так появляется хобби. Я знаю всю эту публику так сказать в лицо, точнее по переписке. Никто не уполномочивал этих черных копателей на разработку ПО, исправляющего ошибки. Они сами решили, что знают все, в результате нарыли хлам в виде матрицы Вандермонда, которая сингулярна в конечном поле, и обращение по Жордану за кубическое время. Я копнул чуть глубже и откапал нечто лучшее. В свою очередь, серьезные специалисты в этом деле занимаются по преимуществу коммуникациями и микросхемами, до файловых кодеров им дела нет.

Читайте правильную литературу, ищите правильные источники по перемножению матриц через FFT. Отличайте по настоящему быстрые алгоритмы от суб-квадратичных тормозов. Шаги по переводу данных “в другой формат” вполне могут иметь место, но они не могут осуществляться за время O(n^2), это было бы верхом абсурда. Лично у меня прежде чем вектор данных превратится в parity-символы, он проходит шесть(!) кругов вращения при смене базиса. Ну что с того, шесть раз вызвать FFT? Оно от этого квадратичным не станет.

Опять мы наступаем на старые грабельки, забываем про Complexity.
Рассмотрим к примеру ICEECC. Матрица 1000x1000 там обращается моментом, матрица 5000х5000 требует уже целый час для своего обращения, ну а матрица 10000х10000 целых восемь часов! А ведь кодек там 16-битный, до насыщения ему далеко, он может потянуть и 32768/65536 блоков.

Теперь перейдем к моему релизу LDPC. Матрица 5000х5000 там обращается за 3 секунды, а вот для матрицы 50000х50000 потребует уже, как нетрудно прикинуть, целый час. А это приличное время, от асимптотики никуда не деться. Видимо, можно побыстрее сделать через обход графов, но тут у меня нет ни малейшего понятия как это делается. Тут Вы правы, это не коммуникация, можно и подождать.

То есть возможны ситуации, когда обращение матрицы будет лимитирующим фактором.

Встает вопрос, а зачем нужно так много блоков? Это вопрос очень сложный, на DVD диске миллионы секторов, так что и 20000 – это еще очень далеко, чтобы исправлять все возможные ошибки, а не только крупные пачки ошибок. Хотя обычной практикой в ICEECC является кодирование на уровне 2000 блоков. В общем, все зависит от ожидаемой модели повреждений.

А главное, возможно применение кодов Рида-Соломона для случаев, когда ошибки вносятся умышленно. Особенно интересно создание патчей-мутантов, которые способны превращать старые версии программ в более новые, т.е. апгрейдить версии, вылечивая старые в более новые. При этом сами патчи содержат только шумоподобный код, ни в явном виде ни в криптографическом никаких копирайтных материалов не содержат. Вот для этих целей число блоков должно исчисляться десятками тысяч минимум. Можно придумать еще много чего интересного, когда ошибки вносятся в файлы преднамеренно.

Допустим, у нас имеется мультипликативный элемент
0100
0010
0001
1000,
который при возведении в степень переходит сам в себя со сдвигом. Как можно приспособить это дело для кодирования большого количества блоков, тысяч или десятков тысяч?

Я так понял, в литературе между этими понятиями особой разницы не делают, противопоставляя квадратичному кодированию. Чисто линейной может быть например LDPC-шная матрица у которой число отведений (т.е. не нулей) фиксировано в процессе
роста размеров.

Вам это зачем нужно и какова цель Вашей деятельности?

 

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

Да, преимущественно это так, потому, что основные потребители этих кодов до недавнего времени - это компании работающие на сектор коммуникаций. Они используются в xDSL, WiMax и так далее, а еще раньше коды коррекции активно применяли для космической связи (кстати многие статьи по применению преобразований Фурье, чисел Ферма-Мерсенна и т.п. написаны людьми, связанными с JPL/NASA и компаниями, занимающимися спутниковым коммуникациями).

Это радует.
Но вот смотрите, допустим, что мы имеем коэффициент = 6 при применении FFT, и допустим, что сами итоговые операции у нас в 2 раза медленнее, чем в классическом квадратичном алгоритме (за счет комплексности нового алгоритма). Я предполагаю, что Вы используете "двоичное" FFT. Тогда у Вас скорость декодирования будет условно равна n*6*2*log2(n)*log2(n) (декодирование, насколько я помню теорию, требует логарифм в квадрате шагов, а не просто логарифм). Пусть n = 1024, мы получаем 1024*6*2*10*10=1024*1200 операций. "Тупой" квадратичный алгоритм потребовал бы 1024*1024 операций. Поэтому может так оказаться, что применение FFT оправдает себя только при очень больших n. Конечно, если Вы работаете в поле GF(2^32) и Вас интересуют сверхдлинные или вообще сверхбольшие матрицы, то FFT оправдано. Но на маленьких матрицах накладных расходов будет больше. Взять, например, 16x16, и возьмем чистое кодирование, там нет квадрата у логарифма. Что имеем? n*log(n)*6 (минимум, по вашей прикидке) -> 16*4*6 -> 16*24 вместо 16*16 операций.

Поэтому есть смысл искать особенные матрицы, которые можно обратить специальным алгоритмом, а не за время O(n^3). Или иные методы кодирования/декодирования, не матричные. Смотрите, например, LT-коды и все что от них пошло, но учтите - там куча патентов команды профессора Luby. Однако коды основанные на этих принципах работают фантастически быстро в реально существующих приложениях, могут быть rateless и вообще не используют матриц. Но, естественно, они все - не MDS.

Тут может быть много вариантов действий:
- Применить MDS-коды (которые я тоже обожаю, так как мне нравится все совершенное), но тогда все будет работать медленно,
- Применить LDPC общего вида, скорость сильно вырастет, но это не MDS и уже есть опасность попасть на патенты,
- Применить LT-подобные коды, скорость будет огромной, но огромный трах - обойти все чужие патенты,
- Применить interleave, в результате снизится ВЕРОЯТНОСТЬ невосстановимой ошибки, но, к сожалению, уже нет гарантий,
И, наконец, последний вариант:
- Сделать какое-то открытие, которое даст принципиальный прорыв или, как минимум, код не худший существующих, но патентно-чистый.

Если правильно понял Вашу идею это называется block-circulant LDPC.

 

Теперь я понял, Ваша цель - это вероятно публикации и получение патента на изобретение.

Ну а мне достаточно просто защитить скажем собственное фото или видео на DVD. Да и просто интересно.

 

persicum
Здравствуйте!
С интересом читал вашу перестрелку на форуме айс-графикса. У меня тоже хобби - защита компакт-дисков; несколько лет назад сделал команд-лайную софтинку для защиты XCD'ей от сбоев (XCD - это такой способ запихать 800 мег на 80-минутную болванку). За образец взял кусочек unrar'а (rs.cpp, класс RSCoder), увеличил разрядность до 16 бит и пооптимизировал всё, что смог - где-то раз в 20, получилось вроде неплохо, расчёт одного процента избыточности == 250 миллиардов полиномских умножений - на northwood-celeron-2300 проскакивают за 40 минут. Но увы - восстановление идёт блоками по 6 секторов, а не по одному, как хотелось бы, ибо больше 64K блоков низзя - разрядности не хватает. Давно уже думал насчёт довести разрядность до 32 бит - чтобы можно было прикрывать каждый сектор независимо и/или DVD тоже обслуживать, но все попадающиеся реализации умножения были настооолько меееедленными...
А недавно попалась мне идея об использовании в кодах Рида-Соломона 32-битных простых чисел вместо двоичных полиномов: обычное сложение-вычитание вместо xor, умножение через mul вместо цикла из xor'ов и сдвигов, применение SSE2'шной арифметики и т.д. - это позволяет не только увеличить разрядность, но и существенно поднять скорострельность процесса.
Но переделка упёрлась в непонимание подробностей rar'ового алгоритма расчёта избыточности: непонятно, где операция XOR соответствует сложению, а где вычитанию; неясно, зачем ему столько таблиц (что-то аж 6 штук!), и т.д. Писал Рошалю просьбу о помощи - пролёт, он сам уже забыл, что это был за алгоритм и как назывался.
Так я к чему веду: может быть, вдруг вы этот алгоритм (в его первоначальном, безтабличном виде) знаете и можете посоветовать мне его более-менее словесное описание или псевдокод, или хоть название, чтобы можно было гуглю припахать? А пооптимизирую я уже потом сам...

Ха, если бы - это ж четверть века назад было, уже ничего не помню, и конспекты давно пошли на растопку.
Да, кстати, именно на rar'овом алгоритме обнаружил интересную фишку: если N слов данных прикрыть K словами избыточности, а затем полученные (N+K) слов - сверху ещё K2 словами (и K2<K), то все K2 слов "вторичной" избыточности получаются нулевыми. И, соответственно, если P из этих (N+K) слов - сбойные (и P<K), то для восстановления всех их с головой хватает только O((N+K)*P) операций вместо O((N+K)*K), а поскольку обычно P<<K, то восстановление занимает уже не десятки минут, а десятки секунд. Обнаружил случайно, офонарел, проверял много сотен раз - работает. Интересно, это свойство вообще кодов Рида-Соломона или присуще только rar'овому алгоритму? В литературе (в инете, собссно) нигде такой эффект не упоминается, а проконсультироваться в пределах досягаемости не с кем.

 

Все хорошие алгоритмы восстановления в случае erasures работают за время, пропорциональное именно количеству фактических ошибок, а не максимально возможному. Алгоритмы, которые сами находят сбойные блоки (настоящий error correction code, а не erasure), тоже обычно могут оптимизироваться после какой-то стадии (в зависимости от алгоритма).

 

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

К сожалению, насчет RARа ничем помочь не могу. Чтобы алгоритм смог исправлять отдельные сектора, он должен быть интерливным, а я интерливом не занимаюсь. У меня не то что 6 секторов, а 1000 штук=2метра покрываются в лучшем случае каждым томом в моей терминологии. Какими-то методами декодирования, как то графы или итерационными (как в RARe) тоже не владею, кроме матричных. Увы-Увы... Пишите лучше все с нуля, а так конечно не разберетесь, где был плюс где минус вместо XOR. Существует еще одна серьезная засада - при работе с простыми числами часто требуется операция изменения знака - в полиномах она отсутствует, поэтому механически перейти от полиномов к простым числам не получится без полного переосмысления алгоритма. У меня на слуху следующие простые - FFFFFFFB, FFF00001, E0000001. Пару последних я припас для FFT, а первым можно работать с кватратичными алгоритмами. Но предется решать проблему - куда спрятать пять запрещенных переполнений в исходных данных, которые больше или равны FFFFFFFB. Для остальных видимо предется перепаковывать вектора на лету в 31 бит.

А как MDS лечат данные со сдвигом? Допустим затерли один байт и все данные сдвинулись? Имхо тут только ERASURES рулят.

 

Свое отношение к интерливу еще не выработал. У меня в программе он отсутствует как класс. В DVDisaster есть красная черта, которая показывает предел корректирующей способности RS(255,223). Если только перейти эту черту, хотя при огромном интерливе вероятность этого мала, мы получим неисправимую ошибку, и никакие другие избыточные данные или целые сектора не могут прийти на помощь. А в случае глобальных=безинтерливных алгоритмов либо диск вылечивается целиком, либо вообще не вылечивается. Если скажем вдруг не хватает данных для восстановления, можно поискать дубликаты некоторых файлов или попробовать поискать полезную инфу от балды скажем в c:\Program Files. Любые валидные данные могут прийти на помощь, проблема восстановления решается целиком, либо оно есть, либо нет его.

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

 

MDS - это Maximum Distance Separable, или коды, которые достигают Singleton bound, в переводе на человеческий язык - те, которые могут исправить столько же стираний, сколько вносят дополнительных символов (для блочных кодов), при максимальном количестве контрольных + исходных символов = 2^q. То есть, Reed-Solomon правильно реализованный - это MDS-код. А вот LDPC - не MDS-коды, так как требуют большее количество контрольных символов, чем количество исправляемых ошибок (в наихудшем случае).

 

Все это далеко от реальной практики работы с файлами. Вот допустим у меня файл с примочкой в виде кода MDS. Я один байт кильнул и все сдинулось. А MDS он ведь не имеет разметочных данных на сектора и прочее. Получили полную потерю всех данных. поэтому я тоже считаю Hamming Distance=MDS непригодной для защиты файлов, к тому же не представляю как можно найти ПОЧТИ неповрежденный сектор, чтобы поставить его на место. Это как б..., либо она есть, либо нет ее.

 

Одно другому не мешает. Вам прикольно - и это отлично, Вы уже перепробовали кучу алгоритмов и практически ускорили быстродействие, вполне возможно, что в какой-то момент придумаете вообще свой собственный вариант кода, нигде не описанный, даже у именитых авторов - и чем-то лучший остальных. Тогда можно не просто побить авторов free/shareware программ, но и заработать серьезные деньги, чтобы иметь возможность дальше заниматься исследованиями, не думая о хлебе насущном. Так что нет противоречия никакого между интересом к тематике для практических нужд и поиском патентно-пригодных алгоритмов. У Вас есть утилита, которая отлично и быстро работает - с практической точки зрения можно было бы и остановиться. Но хотите же ее еще ускорить? А максимальное ускорение даст алгоритм, который еще никто не открыл. То, что новые открытия в этой области продолжают происходить - говорит нам, что не все еще сделано до нас и есть шансы.