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

Так это и оправдано: RSCoder используется для восстановления томов многотомного архива (см. его использование в recvol.cpp), когда уже известно, какие именно тома битые или отсутствуют.

Ага. Массив PolB, да? Сенькс, буду иметь в виду.

Ага. Гугля упоминает, но цена под 200 баков... У вас случайно pdf или djvu не завалялся?

 

Вообще evaluation это ничто иное, как тривиальное вычисление значения многочлена - подставляем в него нужный нам "x" и последовательно вычисляем, домножая и складывая, домножая и складывая - в простейшем случае по "школьной" схеме Горнера. Но если это нужно сделать в N точках - у нас будет (N-1)*N операций. Как это сделать быстро, через FFT - скажу честно, я не знаю, не въехал в это так хорошо, чтобы избежать квадратов. Само FFT я применил, когда с ним экспериментировал - по статьям заумным до жути. Но в обвязке всей этой у меня кое-где вылезали все равно квадраты и я их не извел до конца.

Как делить полиномы с остатком описано, например, во втором томе Кнута. Для двоичных полиномов - отличная иллюстрация процесса деления это CRC-коды, и классическая статья "A Painless Guide to CRC Error Detection Algorithms".

 

Увы, у меня она бумажная.

 

to persicum:
Кстати, если у Вас есть свой контроль целостности блоков, то советую там (для улучшения Вашей программы) вставить вычисление CRC-32 по другому полиному, не по стандартному, взятому из Ethernet. Есть полиномы, которые для крупных блоков имеют больше расстояние по Хэммингу, при котором ошибка будет гарантировано выявлена -> снижают вероятность необнаружимой ошибки. Например, один из них используется в стандарте iSCSI (для всяких Storage Area Network – прямо то, что нам нужно). Это полином 0x1EDC6F41. Например, он работает с расстоянием по Хэммингу = 6 вплоть до 5243 битов, в то время как стандартный полином - только до 268 битов. Стандартный полином оптимизирован под короткие пакеты. А полином 0xF4ACFB13 держит HD = 6 до 32736 битов, но на более длинных пакетах проигрывает полиному из iSCSI. Многие же люди считают, что CRC-32 всегда бывает только по одному полиному или что все они примерно равнозначны по свойствам.

 

Есть интересная статья - http://www.lshift.net/blog/2006/11/29/gf232-5, в ней предлагается пара способов борьбы с переполнениями. Но они все годятся для передачи-приёма, а в нашем случае данные на компакте корёжить не стоит - чтобы можно было ими воспользоваться без декодирования.
Я пока придумал проще - делать битовую карту, на ней единичками отмечать числа, равные или больше FFFFFFB. Поступать с ними можно просто - уменьшать на FFFFFFFB, отмечать на карте, карту сжимать и тоже включать в защитные файлы; при восстановлении - для живых блоков опять же уменьшать, в восстановленных - перед сбросом на винт увеличивать. Правда, несжатая карта - это лишних 3%, а сжатая - геморрои со сжатием/распаковкой.

 

Очень интересная идея, жалко только что несвоевременная... Напоминает запись на 81 трек флоппи...
Сейчас это едва ли кому нужно, а на DVD нет чтения в RAW, иначе бы оно было бы в Дизастере, Алкоголе или Изобастере. Но проект ни в коем случае не забрасывайте и обязательно развивайте дальше. То что есть сейчас в напрявлении защиты ISO - это Дизастер, а он локально-восьмибитный, совсем убожество если не по потребительским свойствам, то по базовой идее по крайней мере. Не могли дурашки туда 16 бит хотя бы поставить.

Это я к тому, сколько бы памяти заняла такая задача в моем случае. В настоящее время моя прога реализует только явные матричные методы кодирования, при этом под матрицу отводится первый Гиг памяти. В конце кодирования память тестируется. В принципе, реализовывать квадратичный алгоритм, который не требует памяти под матрицу, смысла не вижу, поскольку асимптотика все равно плохая, а быстродействие шипко хуже будет.
(К примеру RAR исправляет CD в конфигурации 200-50 за 5 мин, а мой прог за 15с)
Я понял, Вас интересует глобальное кодирование 2 млн. блоков с избыточностью 1%. Щас прикинем время, необходимое квадратичному алгоритму.
Исполняем crc32 -wrr20000-200 -tm3 -mu1g
Чистое время кодирования - 10 минут. При умножении на 100 (для перехода от 20 тыс к 2 млн блокам) имеем 16 часов на один DVD диск. Такое удовольствие даром никому не нужно. Поэтому переход на 32 бита без применения FFT - это пустая затея, советую сразу заняться адаптированием алгоритма RAR_RS под FFT32.

К сожалению, не в коня корм. Для меня все это метание бисера. Действительно, для меня все CRC32 - одинаковы. Я понимаю, что Вас интересуют скорее базовые математические идеи, чем моя скромная программка, но все же немного раскрою ее возможности.

Для контроля целостности файлов действительно используется стандартный архиваторный полином как в ZIP и RAR. Но если этого мало, можно выбрать MD5, SHA1, или батарею 5-битных полиномов CRC32 (ключ -n). Полиномы повязаны наподобие колес Энигмы, поэтому если к файлу прицепить 4G нулей, то показания младшего колесика не изменятся, но остальные поплывут. Ну то есть они пробегают не 2^32 значений, а все 2^(N*32).

Для контроля целостности блоков используется 256-битная сигнатура, которая подразделяется на 6(!) иерархий, самые быстрые служат целям фальсификации, самые медленные - целям верификации блоков. В основном это сделано от того, что данные могут переть со сдвигом, все время считать скажем MD5 для куска памяти - офигеешь.

Возвращаясь к полиномам CRC32 - для них ведь важно иметь поменьше коллизий.
Нельзя ли понятие Hamming Distance привязать поближе к коллизиям?
Не так давно RElf рассказывал про полиномы, которые гарантированно не могут иметь коллизий при изменении 1 бита в блоке.

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

В принципе, можно улучшить проги уже написанные или которые только планируются, если вспомнить, что число FFFFFFB это 2^32-2^2-2^0 - т.е. по сути Мерсеновское, хотя так сразу этого не заметно. Только три веса отличны от нуля. поэтому возможно быстрое взятие остатка на одних шифтах. А поскоку форум тут всежтаки для асмеров, то милости прошу, на входе пара регистров EAX, EDX на выходе остаток mod FFFFFFFB. Мне было в патлу этим заниматься пока, сейчас в проге стоит DIV, и построение матрицы возможно ускорить если отказаться от этого DIVа. Хотя на производительность кодирования это никак не повлияет, я еще не совсем дебил, чтобы после каждой операции скорее бежать вычислять остаток.

 

Кстати, функции из RAR, которые тут приводились - они байт-ориентированные, не только в смысле разрядности полиномов, но и в смысле обработки - она там идей по байтам, а не блоками. Это ни плохо, ни хорошо само по себе. Смотря какие задачи решаются. Но понятно, что при массовой обработке данных в задачах хранения больших объемов на современных машинах - это неудачное решение.

На счет MD5 согласен и размер в 256 битов более чем достаточен. Вопрос в том, что там внутри используется. Если CRC-32 или CRC-64, то хороший подбор полинома не скажется на быстродействии и повысит надежность.

Расстояние по Хеммингу о котором я говорил выше - это максимальное количество битов, изменение которых еще будет гарантировано обнаружено. Если стандартный полином держит HD=6 до 268 битов, то это означает, что он гарантировано обнаружит любую 6-битную ошибку в блоке длиной в 268 битов. Но! Полином условно используемый в iSCSI способен поймать 6-битовую ошибку в блоке длиной 5243 битов, а третий полином, который я привел - в блоке длиной до 32736 битов, то есть практически 8KB (но дальше его характеристики будут падать быстрее, чем у полинома iSCSI). Поэтому совсем не пофик для качества отлова ошибок какие полиномы использованы.

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

 

Format XCD и mode2 берут свое происхождение от Audio-CD, вот там как раз были такие извратные длинные сектора и слабая коррекция ошибок. Т.е. по сути это режимы аналогичные Audio-CD. А на DVD нет такого.

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

Спасибо, учту на будущее

 

sysprg

Я что думаю, если рассматривать классические RS коды в режиме подчисток и ультрасовременные матричные, но и те и другие реализованные спектрально - через FFT, не являются ли они по сути тождественными? В обоих случаях требуется много работы с полиномами в расширенных полях, и вроде больше ничего. Сложность матричных k log k + n log n для кодирования и k log^2 k + n log n для декодирования для (n,n-k). У классического RS похуже будет? Что там пишут умные статьи-книжки? Есть опасение что возможно хуже, т.к. там для систематического кодирования нужно так прямо сразу делить...

Это я к чему, может за матрицами не гоняться и заняться классическим RS?

 

Думаю да, примерно так. По сути задача одна и как ее не решай детерминистичными алгебрарическими методами, итог будет примерно один и тот же. Чем больше мы сосредотачиваемся на erasures, тем больше два декодера становятся похожими, IMHO. Просто матричный изначально предельно заточен под erasures.

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

Вообще с моей точки зрения есть два направления перспективных в hard-decision алгебраическом декодировании RS-подобных кодов. Одно из них, это всякие FFT-подобные быстрые преобразования, то, над чем Вы работаете. Второе направление - это дальнейшая оптимизация "квадратичного" алгоритма. В этом направлении исследования дошли до полного вынесения всей работы с полями за рамки основной части декодера, который дальше уже работает только как исполнитель плана элементарных операций. В этом направлении работает несколько research групп академических и коммерческих компаний (включая IBM, например). Есть далекие продвижения для RAID-6 кодов с двумя ошибками, фактически там достигнуты теоретические пределы такого метода декодирования. В кодах общего вида в этом классе алгоритмов я продвинулся дальше всех опубликованных работ, но рассказывать алгоритм пока не буду, так как жду получения патента на него и продаю этот софт.

IMHO в итоге получится тоже самое, вид сбоку, если сосредоточится только на erasures. А если с поиском ошибок - там и так попробуй вообще разберись, когда начинают именно оптимизировать глубоко это дело (а не просто списывают с книжки первоначальную реализацию Берлекампа-Масси), а если туда еще и FFT добавить... Но фиг знает, может быть на каких-то этапах там и проще с FFT, так как больше работы в полиномиальном базисе.

 

Почему? На DVD писать не хочу - приличные болванки сильно дорогие и к нам в город их не возят, а дешёвые (как 2-3 CD-R'а) живут до первого сбоя пару месяцев. А скачанный 700-мегабайтный рип, как правило, сам просится, чтобы к нему прикрутили оригинальный саундтрек. А когда риплю сам - опять же сотня метров может весьма пригодиться.

В смысле - чтения секторов со всеми заголовками и прочими потрохами? Нуу, "Nero CD/DVD speed" таки ухитряется пробегать тест битого DVD, почти не снижая скорости, значит, что-то для этого таки есть - а на уровне SCSI, ASPI или прямо команд привода, пока несущественно.
Или в смысле заюзать дополнительное место? Так в dvdisaster'е этой фишки для CD я тоже не нашёл, XCD он не рюхает даже для снятия образа...

Ха, у меня первая версия 16-битки (той самой, по мотивам RSCoder'а) считала 600 блоков избыточности на 60000 блоков данных по 6 секторов по 2324 байта - чуть больше 11 часов! Нынешние 40 минут мне стоили не одну тысячу часов возни с оптимизацией. Dvdisaster вполне мог обломаться оптимизировать.

Дык я не защищаю ISO-образ, я защищаю файлы. Хотя в сторону защиты образа тоже поглядываю.

По моим прикидкам - где-то аналогично. (Хотя думаю, что на практике однопроцентной избыточности будет уж слишком до фига, если затачиваться только на плесень/выцветание и не заморачиваться восстановлением после массовых глубоких царапин или шлифовки болгаркой. ) Однако подозреваю, что SSE2'шное умножение сильно ускорит дело.

Что не умею, то не умею - в институте пару месяцев проболел как раз пока проходили Фурье, а потом так и не понадобилось. Кстати, а чем так хорош FFT, чем он тут может быть полезен? Подкиньте что-ньдь почитать!

Хм. Но тогда либо придётся как-то корёжить сохраняемые на диске файлы (что IMHO неприемлемо: ведь надо, чтобы диском могли пользоваться как таковым - с него грузиться, смотреть кино, вставлять по требованию игры и т.д.), либо всё равно сохранять карту "тайников". Или я что-то упустил?

Уже пробовал: получается чуть-чуть быстрее, чем тупым умножением на 5, т.е. будет существенно медленнее, чем умножать на SSE2. P4 всё ж здорово тормозит на сдвигах, как и его предки P2 и P3.

 

Ну... таки да: CD-DA был первым, а размер сектора и их кол-во в секунду (2352*75) подгонялись под тогдашнюю дискретизацию 44100 Гц. А остальные применения - уже под имеющийся стандарт диска, контроллеры чтения и т.д.

С DVD я не в курсе - до сих пор руки не доходили добраться почитать.
Кстати, а как с этим делом (т.е. размерами блоков, избыточностью и т.д.) у flash-памяти? А то я так до сих пор ничего и не нашёл, кроме базовых (т.е. аппаратных физических) принципов.

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

 

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

 

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

 

Обновил программу до версии 1.77
На количество блоков сняты все ограничения, лишь бы матрица помещалась в памяти. Это связано с желанием определенного контингента иметь возможность кодировать очень большое количество блоков с очень малой избыточностью. Правда, заголовки дико раздуваются, поэтому мой прог всеже не предназначен за охотой на отдельные сектора, все же я считаю, что не то шо там 300000 секторов, а 2000 штук их достаточно для DVD, у которого своя система коррекции. Для XCD ситуация может быть другая…

Правда чтоли? Ну тогда давай побенчимся…

Ваш прог и 3000 секторов защиты заказал 30 минут (которые я ждать не стал).

Total: 2 input files, 355476 sectors, 728007088 bytes
8.6%, elapsed 0:02:51, remains 0:30:17

Мой прог в режиме глобальных ШЕСТИ секторов, что по времени эквивалентно шести интерливным:
crc32 -wrr60000-500 -mu1.5g <-tm>
Reed-Solomon 16 бит - 10m
Reed-Solomon 32 бит - 3m

Вывод: Матричное кодирование гораздо быстрее полиномного. Хотя и у того и у другого есть свои достоинства и недостатки. Мой RS16 кстати никак особенно не оптимизирован, никаких 8 маленьких подматриц у меня нет, только две большие (одна учетверенная)

Мой прог в режиме глобальных Единичных секторов, что для Вас пока недостижимо:
crc32 -wrr360000-3000 -mu1.5g <-tm>
LDPC - 1min (требует 30 лечебных секторов свыше числа ошибок и допускает порчу 2800 лечащих (но не 2999))
TBPC - 12 min (требует 10 лечебных секторов свыше числа ошибок)

Это чистые времена кодирования без учета подготовки и дисковых операций.

Вывод: при большом количестве блоков нечего гоняться за совершенными кодами, чем больше блоков, тем менее статистически важен каждый байт. Совершенные коды нужны, когда байты пересчитываются поштучно, типа RS(255,223). А когда их многие тысячи, можно пожертвовать скажем десятком из них чтобы вылечить остальные тысячи

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

 

У меня - с дисковыми: каждый цикл - считывание пачки из нескольких тыщ секторов (не меньше, чем размер избыточности - не помню уже, зачем-то так понадобилось), затем обсчёт пачки, досчиталось - прикидка времени, его вывод и следующая пачка. Это обходится в лишних несколько минут, но мне влом было делать многопоточность и удваивать занимаемый буферами объём (тем более, что это делалось и отлаживалось на 128М ОЗУ).

Уже удалил. Кстати, те же Эгнер и Кроули советуют не заморачиваться остатками на ходу, а откладывать их на потом. Я пока следую их совету, а там видно будет.

Мне их идея не покатила: пришлось бы сохранять ещё и пару килобайт этих префиксов, притом что включить их в общую защиту нельзя - она без них не восстанавливает. Проще запоминать, где лежат "запрещённые" dword'ы, а вместо битовой карты вполне можно сохранить список их адресов где-ньдь в конце, перед собственно избыточностью, и т.о. защитить сам список.

О! Где можно почитать, как это сделать?

 

Ну сколько конец не оттягивай, а взять остаток все равно захочится... Вы все время собираетесь работать в RAR_RS c комплексным числом 64+64 бит?

Когда то это было вкусно, а теперь как черствый хлеб. У меня щас чужая FFT-шная прога решает эту задачу за 15 секунд, а не за 3 минуты плюс 2 Гига рама как у меня и не за 30 минут + 128 М рама как у ВАС. Раньше психи болтались в астральном плане, а теперь общаются в инете и годами шлифуют программы, у которых сам базовый принцип ошибочен, типа квадратуры круга или трисекции угла =)))

 

А нельзя ли в чистом виде измерить скорость кодера/декодера? Возьмем два примера - матрица 32x32 и матрица 128x128, блок размером 8 килобайтов, таких блоков 10240 штук (80 MB). Ваша программа (если ее запускать стандартно) читает с диска и пишет на диск, и фиг знает, сколько времени тратится на весь этот ввод-вывод, особенно принимая во внимание, что он идет параллельно (отложенная запись, упреждающее чтение). Я не смог понять, с какими ключами нужно запустить CRC32 и как можно измерить чистое время кодирования/декодирования для такого простейшего и в тоже время показательного примера, как описаный выше. Интересует только режим RS32, как самый быстрый из доступных RS-кодов в Вашей программе. Можно это измерить без ввода/вывода? Просто взять массив в памяти заполненный рандомной грязью/одинаковыми байтами типа 0x55, и замерить чистое время энкдера/декодера в однотредном режиме? Завтра Вы что-то поменяете в логике ввода/вывода, или у других людей будет другой диск, другой CPU с другим кэшем/количеством ядер (если Вы их используете) и все цифры, которые Вы приводите, будут "ни о чем".

 

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

 

Чистое время кодирования можно определить, если взглянуть на Remained Time в самом начале, когда первый слив буферов на HDD еще не произошел. Или, можно задать размер буфера в точности равным размеру блока (ключ –bsfit), тогда время стадии

Код (Text):

1.  Encoding User Data into 100 recovery volumes...
2.  [##------------------] 13%

будет представлять собой чистое время кодирования, при условии, что вся задача умещается в ОЗУ и Винда не свапит сама по себе.

Условия задачи противоречивые, матрица 128х128 задает 100% избыточность, Вам нужна матрица 10240x128. Размер тома у меня явно задать нельзя за ненадобностью, но можно задать выравнивание, по умолчанию 2048 байт.

1) Берем 80 метров любых файлов
2) Исполняем crc32 –wt
3) Исполняем crc32 -wrr10240-128 -tm3 –bsfit
4) Смотрим лог, прога урезала 10240 блока до 9888, но это не принципиально, размер буфера есть 100% от блока(тома), поэтому дисковой активности во время кодирования не будет.

Код (Text):

1. Encoding Method..............: RS32
2. Number of Data Volumes.......: 9888
3. Number of Recovery Volumes...: 128
4. Total Size...................: 81,000,000
5. Recovery Size................: 2,976,550
6. Overall Size.................: 83,976,550
7. Size of Volume...............: 8,192
8. Size of Buffer...............: 8,192 (100%)
9. Volume Alignment.............: 2,048
10. Redundancy...................: 1.294%
11. Header Redundancy............: 5
12. Efficiency...................: 35.23%
13. Memory Required..............: 87,121,920
14. SSE2 Support.................: Enabled
15. Sizing Scheme................: 5 Equal Files
16. Swapping.....................: Minimized

5) Нажимаем Yes, чистое время кодирования 4 секудны.