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

sysprg
А у Вас матрица совсем случайная, или свободная от перекрестий или с иными специальными свойствами?

 

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

 

Я не спорю, что LDPC коды на практике крайне надежны. Но из-за того, что те коды, которые я понимаю и использую, включают далеко не каждый входной блок в далеко не каждый выходной блок (собственно за счет этого и достигается огромное быстродействие) то в результате если СПЕЦИАЛЬНО знать, какие блоки нужно уничтожить - то запороть весь код можно убив ну скажем несколько десятков тщательно отобранных блоков (из десятков тысяч). Да, без "злого умысла" вероятность такого события ничтожна - но нулю она тождественно не равна и НИКОГДА не будет равна. К нулю ее можно свести только для какие-то плотных и очень специально построенных матриц. Но тогда быстродействие будет уже не намного лучше RS и кроме того я не знаю как такие матрицы целенаправленно строить под заданные параметры кода.
А Вы какие матрицы используете, чтобы именно гарантировать, что скажем 30 или 100 блоков будет достаточно? Или у Вас нет тождественно равной единице гарантии?

 

Какие могут быть гарантии у любителя-дилетанта? Но вероятности отказа exp(-30) или exp(-100) должно хватить =)))
Более того, у меня в востановлении участвует не 30 лишних блоков, а все имеющиеся, если их 500, то будет exp(-500) соответственно. Вероятность в моей программе пропечатывается, это тождественная МАШИННАЯ единица =)))
Поэтому я и говорю, отличие от RS только когда уж совсем все впритык. Но и тут разница не принципиальная. RS декодирование обламывается скачкообразно когда не хватает одного блока коррекции. А у LDPC начинает плавно спадать от 1-exp(-30) до нуля когда есть 30 лишних блоков коррекции и меньше

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

Кодить нужно ключами -wrr1000-1030 -tm2 или -wrr10000-10030 -tm2.
Декодирование у меня включает обращение матрицы, можно включать его в общее время, а можно не включать...
Это зависит от того, какую долю оно занимает относительно самого процесса декодирования.

Вот я и говорю, если СПЕЦИАЛЬНО знать какие биты занулить то можно подогнать CRC64 у огромного файла =)))

 

Обязательно сравним, но немного позже - у меня сейчас нет чистой программы для LDPC, выделенной из коммуникационного протокола, где это используется. В коммуникационной программе LDPC самое место, если нужно передавать большие объемы данных - там нет проблемы дослать еще несколько блоков в том случае, если даже декодирование все-таки "прокололось" из-за неидеальности матриц у кода. У меня сейчас очень много дел, связанных как раз с организацией бизнеса кодов коррекции, но через какое-то время как раз планируется сделать demo и benchmark, поэтому можно будет сравнивать скорость.

 

Выкладываю версию 1.81 своей скромной проги с реализацией 32-битного FFT. На практике оказался чрезвычайно приятным алгоритмом и весьма быстрым. Скорость в сравнении с обычным квадратичным RS имеет вид примерно N/500,
где N - размер кодового слова. Из чего следует, что уже на 500 блоках скорости сравнимы, а для 10000 блоков скорость будет уже в 20 раз выше.

Но сначала нужно проверить, как там дела у ICEECC, не опередило ли оно меня? Ага, последняя версия 2.6, самоуверенное и агрессивное мракобесие продолжает цвести пышным цветом

ICE-GRAPHICS

Ну раз так, то непомешает устроить бенчмарк. "В случае победы гиппард съедает Мука, будет этому Муку наука. Но и Айсу даются такие же права... =)) "

1 Гиг данных, конфигурация 2000-500
ICEECC – 6 минут
FFT32 – 1 мин

1 Гиг данных, конфигурация 20000-5000
ICEECC – 1 час
FFT32 – 1 мин 30 сек

1 Гиг данных, конфигурация 40000-10000
ICEECC – Сдохх…
FFT32 – 1 мин 40 сек

ICE-GRAPHICS

Не существует говоришь? Не надоело писать бред из года в год с умным видом? Вот тебе миллион вскладчину с поросенком Фунтиком! =)))

1 Гиг данных, конфигурация 500000-500000
CRC32.exe -wrr500000-500000 -va4 -tm7 -mu1.5g
FFT32 – полное время 8 минут (2.5 минуты чистого)

У Айса много разных грамот и наград… По результатам тестирования Айсу как занявшему почетное второе место присуждается грамота За самую быструю и вылизанную до блеска многопроцессорную пузырьковую сортировку в мире =)))

 

ginger_tigra
Теперь твоя голубая мечта - полное глобальное кодирование CD c небольшой избыточностью (для FFT кстати это значения не имеет, 1 блок или миллион):
CRC32.exe -wrr400000-10000 -tm7 -mu1g

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

Для этого и LDPC был не плох - но FFT32 код идеальный и совершенный, никакого OVERHEAD ему не нужно.

 

Отлично! А что за FFT там используется? Как я понимаю в обычной арифметике по модулю (mod p) как в Вашей программе было до этого? Если так, то придется выносить за блок одно слово для устранения в блоке всех исходных чисел >= p. Или FFT поверх какого-то особого поля, типа в настоящем поле Галуа? Это очень ведь разные вещи в реализации.
Еще интересно FFT целое или на fp? Если целое - то как добиваетесь 32-битной точности счета в арифметическом-то FFT? Или 32-битность в названии - это от разрядности регистров, но не данных внутри преобразования.
Отдельный вопрос – количество блоков не кратное 2^n – дополнение нулями?

 

Обычный мультипликативный Radix-2 FFT над "почти" 32-битным арифметическим полем. Разумеется не truncated и не irrational based, поэтому zero-padding там хватает. Разумеется, требуется transform входных данных чтобы избежать overflow.

Точное в смысле разрядности аддитивное FFT GF(2^32) тоже существует, но насколько я знаю требует на просто 2^n, а 2^2^n точек, да и будет тормозом страшным без всяких преимуществ применительно к архитектуре x86.

Даже в таком несложном виде как у меня время обсчета DVD практически не зависит от конфигурации и составляет 5 минут. При использовании 1.7G RAM каждый сеанс подкачки требует 1.5 минуты, таким образом общее время защиты DVD составляет 10 минут.

Прога использует, как и QuickPAR, простейшую модель подкачки "целые вектора, частичные блоки". У ICEECC более изощренная схема - "целые блоки, частичные вектора". Но я не уверен, что эта прогрессивная схема пригодна для FFT, вернее оно и так само по себе непростое дело, а тут еще обрабатывать по кусочкам...

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

 

Где она выложена ? =) persicum
ты один тут пишешь , сразу вижно увлечен этой тематикой ...я только книг скачал по теме побольше )

 

nothing, sysprg - профессионалы, занимаются протоколами, а не ПАРаноидальной защитой файлов. рыжий тигер расширил код WinRAR и защищает CD-800, это интересная и оправданная трата времени.
calidus, если доведешь свои познания до реальной проги, милости просим.

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

 

persicum так где твоя программа ? Да вот попробую ... может чтонибудь и наваяю ..

 

Это для него Вы ищите быстрый алгоритм деления на 7*2^20+1? Если да, то не думаю, что таковой существует. У меня есть программа для поиска оптимальных алгоритмов для 4 разных методов - но все магические константы под все методы получаются внутренне красивыми, но как мне кажется не разложимыми ни во что короткое по счету числами с разрядностью больше 32 бит -> будет два, а может и три умножения 32x32 -> 64 в имплементации.

 

А тебе зачем?

А чего мне искать, если я и так знаю, два или три лишних МУЛя совсем не страшны, страшен и чудовищен - это DIV.

 

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

 

Обычно везде и всюду используют модуль 65537, посмотрел библиотеку длинных чисел GMP - и там тоже 2^16+1.
Cамо-собой, там остаток берется чрезвычайно просто: a - b. Но мне уж очень хотелось преодолеть барьер 64К и иметь возможность кодировать хотя бы 100,000 блоков. Работая над проблемой несколько месяцев, я до последнего боялся, что задуманное неосуществимо из-за необходимости/невозможности хранить в памяти огромные таблицы и бысто вычислять обратные элементы. Понятно, что для 2^16+1 это как раз делается через таблицы. Но слава богу, оказалось возможным совсем отказаться от таблиц, а обратные элементы нужны, но не часто, и на производительность не влияют.

 

Долго не отвечал, был занят по работе.

Осилил и конечные поля GF(257), GF(65537). Скорость еще немножко подросла. Достал реализацию LDPC и посмотрел наконец-то что это такое живьем. Тормозит на создании и инвертировании матрицы, хотя по теории это нужно делать за O(n*log(n)).

Интересно, а как находить примитивные элементы к конечным полям? А то есть еще одно вроде как хорошее поле 3*2^30+1 = 0xc0000001.

А мне пока не удалось обойтись совсем без логарифмирования/потенцирования. Да и для всяких FFT они пока нужны. Но в целом, я ничего не придумывал: возведение в степень в поле затабличил по аналогии с умножением (по несколько бит за раз), логарифмирование сделал по алгоритму Шэнкса, обратные считал двоичным же возведением в степень. Просто пришлось повозиться, решая эти трудности. Интересно, а как обойтись совсем без логарифмирования и потенцирования в синдромном декодере?

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

Хм. Интерлив замечательно работает и по этому протоколу. Я докачаю ровно 3 блока и восстановлю все. Другое дело, что на коротких кодах блоки будут большие, и скачивать придется сильно больше.

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

Спасибо за все наводки! Я вот начал для себя шпаргалку писать, потому что боюсь забуду все это через годик-другой, увлекшись чем-нибудь еще. Но прогресс у меня очень скромный (как в шпаргалке, так и коде). Может объединить усилия и выпустить подобие статьи по практической оптимизации и реализации кодов?

 

Обычно перебирают все элементы, начиная с 2 и до упора, проверяя на первообразность (g первообразный, если и только если для всех простых делителей q|p-1 g^((p-1)/q) не равен 1) - на практике прекрасно работает, в теории в предположении расширенной гипотезы Римана наименьший первообразный корень есть O(ln(p)^2), так что всё это полиномиально по размеру p. В случае 0xc0000001 можно взять первообразный корень 5.

 

Для FFT этот Root не подходит, поскольку размер FFT для 3*2^30+1 ограничен 2^30 точками. Правильный Root-генератор должен давать g^(2^29)=(-1), берем 13, калькулятор Windows и, возводя в квадрат 10,10,9 раз получаем (-1), а последний 30-ый квадрат дает 1

Ну Вы наверное не просто три случайных пакета докачиваете, а специально зная какие нужны для данной клетки интерлива... sysprg писал уже, что интерлив это не мера и даже не полумера, иначе к чему всякие там каскады, турбокоды, LDPC и Трансформации Лабэ?

FFT, особенно дополненное нулями, считает для ВСЕХ корней сразу, а iFFT - для всех обратных корней, поэтому специально потенциировать или обращать ничего не нужно, FFT - прямо как квантовый компутер =))) - дает все-все-все одновременно для всех элементов сразу.

 

И тем самым облегчить жизнь Ice-Graphics и RecoveryStar? От меня они ничего не дождутся, пусть сами бьются головой об стенку месяцами... Я четко представляю, каких огромных усилий стоила реализация этих проектов их авторам, а реализовать им удалось пока только лишь детсадовские фуфельки, 16-битный RS с медленным универсальным обращением матрицы. Когда я реализовал фонтан на плотной матрице, который работал в 10 раз быстрее RS16, то Айс сказал мне, что это я разбодяжил матрицу нулями в 10 раз, и оттого она будет обладать очень слабой корректирующей способностью. Тогда я решил подыграть Айсу и действительно разбавил матрицу нулями в десять раз, но скорость была выше уже в 100 раз. Тут он совсем офигел и сказал, что меньше чем со 100 дополнительными блоками она ничего исправлять не будет. Каково же было его удивление, когда для практического случая исправления оказалось достаточно не 100, а только 10 дополнительных блоков. С тех пор много воды утекло, и в программе прибавились еще более удивительные и быстрые алгоритмы.