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

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

 

Да, согласен, что такая ситуация как сдвиг будет воспринята (кодами, о которых мы говорим) как сбой во всех блоках и ничего не декодируется. Я просто пояснил, что коды, которые Вы делаете в части RS-кодов - это как раз и есть MDS-коды (по своим предельным свойствам). Мне они нравятся. И именно в варианте erasures, так как их исправляющая способность в варианте errors проигрывает современным не-MDS кодам типа турбо-кодов. Но когда мы имеем дело с erasures - их никто не побил ни по корректирующей способности, ни по другим характеристикам (кроме быстродействия).
Что в принципе плохо в erasures режиме – это то, что мы имеем шанс пропустить ошибку из-за случайного совпадения проверочного внешнего кода (типа CRC-32), который мы будем использовать для поиска сбойных блоков. Решение - или использовать очень длинные внешние контрольные коды, или же пытаться найти способ декодировать RS за пределами t/2 ошибок не зная их положения. Нахождение быстрого алгоритма для декодирования RS-подобных кодов с неизвестным заранее положением ошибок за пределами t/2 ошибок это задача, которую никто не решил. Есть подходы, но они медленные по сравнению тем, что дают другие коды (типа турбо-кодов). Есть и другие интересные направления для исследований.

 

Ух, стоило на минутку вздремнуть у экрана - и столько отзывов сразу!
persicum

Последние две ссылки в первом посте: rr-1.24.extra.zip, rr-1.29.update.zip - в main'е exe'шки и nano-HOWTO, а в extra - крошечный примерчик и утилька (изначально не моя) для изготовления XCD.

Нет, конечно. В последующих постах - полная (какая есть) дока на софтинку; в частности, есть и список способов использования: защита готового ISO'вого диска, создание ISO с защитой, создание XCD с защитой, особенности восстановления для каждого варианта...

Ничего "мучительного" в XCD нет - это не перепрожиг, а использование с толком тех 15% ёмкости сектора, которые в нормальных ISO-9660 уходят под посекторную избыточность (ECC). Т.е. лишняя сотня метров просто так, на халяву, безо всяких overburn'ов и коротких lead-out'ов. А избыточность - 1% (8 метров == 3600 секторов) с головой покрывает отсутствие 15-процентного ECC. Итого - 90 мегабайт чистого выигрыша.
Кроме того, у XCD ещё одно достоинство - в приводе он себя ведёт как VCD (которому родственник - тоже ж mode2-form2): на сбойных секторах не топчется десятки секунд, а быренько-быренько отдаёт то, что прочитал, и чешет дальше; а уже задача секторополучателя - просчитать EDC, сравнить с имеющейся и решить, годен сектор или надо восстанавливать.

Почему же? И какая принципиально-алгоритмическая разница - юзать GF(2^8) и обрабатывать аж до 255 томов, или GF(2^16) на 65535 томов?

А если б было 360000 томов - то почему бы не считать том == сектору и прикрывать каждый?
У меня, правда, тоже не чисто глобальная защита. Шесть наборов; в первый входят сектора 0, 6, 12, ... 359994; во второй - 1, 7, 13, ...; в третий... пятый... шестой - сектора 5, 11, 17, ... 359999. При том же 1% избыточности можно восстановить до 600 секторов в каждом наборе, т.е. при максимальном везении - 3600 секторов, при макcимальном невезении - восстановление накроется на 601-м сбойном секторе.
(Можно было, конечно, просто объединить по 6 секторов в томе, но тогда софт упрощается крайне незначительно, а критический объём erasure'ов снижается вшестеро.)
А использование Рида-Соломона в rar'е достаточно простенькое - вот rs.hpp и rs.cpp? меньше двух сотен строк на C++. Ни графов, ни итераций - всё чинно-благородно, сплошные умножения чего-то на что-то.

Да это я и сам вижу. Нужна мелочь - описание алгоритма псевдокодом (ну, или иным способом - а то матричную математику я забыл давно и прочно), но не оптимизированным под таблицы, двоичные полиномы и т.д., а чтобы видны были отдельные операции. Вот у меня такого описания и нету.

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

sysprg

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

Ну, я ещё на каждый диск записываю MD5-суммы файлов. А в качестве проверки "целый-битый" вполне можно использовать возвращаемый read()'ом код ошибки.

 

Если речь идет о потерях (erasures), то будет использоваться алгоритм на умножении матриц. Ну и соответственно там естественным путем получается столько строк в матрице, сколько у нас пропавших данных.
Если же Вы собираетесь реализовать классический алгоритм, сам находящий ошибки - то как минимум после поиска полинома-локатора ошибок с помощью алгоритма Berlekamp-Massey степень найденного полинома дает количество ошибок (берем случай восстановимой ошибки, когда количество корней полинома найденных в Chien search совпало с этой степенью) и дальше уже все вычисления привязаны к фактическому количеству ошибок, а не к предельному случаю.

Сам лично наблюдал ситуацию, когда давно хранившийся на HDD файл распался битовым распадом в одном байте и ECC-контроль диска этого не обнаружил!
Может быть глюкнул Windows и записал как-то байт не тот, может на диске был реальный сбой (я думаю именно это, файл не трогался годами) - кто его знает? Факт, что нельзя доверять безгранично детектированию ошибок в железе, сбои в простых и коротких контрольных суммах тоже бывают.
Даже сбои не нарушающие CRC-32 изредка случаются - по статистике магистральных провайдеров. Это редкость огромная, но бывали реальные случаи (не только в теории), когда CRC-32 контроль на L2 срабатывал успешно, а на других уровнях протоколов ловилось нарушение целостности, которого не было на отправляющей стороне.

 

А это только на CD возможно, или на DVD тоже возможен такой режим записи?

 

На DVD режимов RAW и mode2 с размером сектора 2552>2048 нет. Соответственно, если это только не бытовой плейер, быстрый пропуск испорченных секторов невозможен, имхо

Щас прикинем быстродействие для 10% избытка при кодировании 800 мегабайт. Замерим для 3600 томов а потом умножим на 100.
crc32 -wrr3600-360 -tm3 -mu1.5g
получилось 2 минуты, что при умножении на 100 дает три часа!.
Это у меня, когда вся матрица лежит готовенькая и выровненная для SSE2. А с полиномами убежден на порядок медленнее будет.

Мой LDPC как он есть у меня поддерживает только 200000 томов, поэтому защита будет полностью глобальной, но 3 секторной. Один том равен трем секторам.

crc32 -wrr150000-15000 -tm2 -mu1.5g
На кодирование ушло только лишь 7 минут.
При декодировании ушло 20 минут на матрицу и 30 минут на само декодирование.
Не слишком быстро, но осуществимо...

Никаких недостатков у LDPC перед совершенными кодами не вижу, если нужно много томов - самое милое дело.
Не знаю даже, сумеет ли FFT его догнать. С FFT проблемы пока, одна из надстроек оказалась замаскированным Горнером за O(n^2) =(((. Но теорема существования решения вселяет надежду.

 

Ага, теперь понятна Ваша цель! Вы отказываетесь от встроенной в CD системы коррекции ошибок с избыточностью 15% в пользу собственной 1% для экономии места =)))

Ну а я наоборот к уже имеющейся у DVD добавляю еще 20% глобальных кодов.

1% избытка на CD можно видимо и без интерлива закодить =))). Но у DVD секторов пара лимонов!
На одну только матрицу уйдет 2000000^2*0.01*4 = 160 Гигов

 

Кстати эти 15% избыточности являются отличным контрольным кодом для выявления самого факта наличия сбоя и если их убрать, то сильно растет вероятность недетектируемой ошибки (кроме того, существенно снижается общая корректирующая способность).
Теперь вопрос к Вам - основана ли идея добавить, скажем, 20% на блочном уровне на реальной практике? Дело в том, что CD/DVD имеют довольно мощный встроенный контрольный код, хорошо продуманный комитетами, принимавшими стандарты. Он борется и с индивидуальной нечитаемостью отдельных битов, и с ошибками типа царапин на поверхности диска. В чем смысл в задаче размещения данных на DVD добавлять туда (внутри одного диска) еще и свой дополнительный код c большими блоками? Я не утверждаю, что смысла нет - я задаю вопрос, основано ли это на практическом опыте?
Дважды я сталкивался с нечитаемостью нужных мне дисков. Но оба раза сбои носили массовый и рассеянный по всему диску характер - куча секторов вылетела. Фактически нехватило корректирующей способности встроенного кода. Но надо заметить - этот код микро-блочный, даже вообще байтовый. Фактически то, что я наблюдал на практике (при нечитаемости дисков) - это массовые сбои в случайных байтах. Как бы тут помог крупноблочный код? У него бы все блоки побились бы.

 

Эта практика идет от подрожания проектам QuickPAR, ICEECC и Recovery Star. Особенно ръяно отстаивает принцип крупных блоков, которые бесполезны при рассеянных ошибках, господин Айс. Ему на форуме этот вопрос тысячу раз задавали, и он на него неизменно тысячу раз отвечал, что крупные блоки это рулез и ошибки всегда идут огромными пачками.

С другой стороны, мои соображения тут таковы, и я с Айсом солидарен в этом смысле, что практическая польза от большого количества томов может расти медленно по логарифмическому закону. Что такое скажем 20000 томов? Это значит, что система коррекции может исправить 20000 равноотстоящих друг от друга независимых очагов плесени, как я это называю. Не важно, что внутри тома могут чередоваться множество битых секторов с небитыми, для тома это пофиг, он либо целый либо битый. Поэтому впечатление что ошибки очень мелкие и раздробленные, наполняют целый диск как песок, может быть просто психологической иллюзией. Диск может запороться с краю, или на середине, или поцарапаться локально. То есть всегда видимо можно выделить не то что там десатки тысяч, а скорее просто десятки областей поверхности, которые можно подразделить на целые и на проблемные. И того 20000 блоков позволяют исправить 20000 проблемных областей, без оглядки скока там каких секторов сдохло.

sysprg, Вы можете как профессионал прокомментировать код RAR_RS? От трех вышеупомянутых товарищей я слышал про него только плохое, но думаю что ситуация прямо противоположная, если только малешка расширить поле с 8-бит до 16- или дальше до 32. Кстати, если там процедуру перемножения полиномов void RSCoder::pnMult(int *p1,int *p2,int *r) заменить на банальное ifft(fft(a)*fft(b)), то можно будет видимо получить готовый логарифмический код? Не могли бы Вы это дело тщательно проанализировать, не остается ли там квадратичностей? Как вообще это все работает и где можно взять подробненькое описание доступное для понимания чайникам вроде меня и ginger_tigra?

 

Уж не знаю насколько я профессионал конкретно в этой области кодов, но четко видно, что это - классический синдромный декодер RS-кода. Отличие от более общепринятой реализации состоит в том, что за ненадобностью выкинута процедура поиска полинома локатора ошибок (Berlekamp-Massey). Дело в том, что как видно из процедуры - RAR тоже восстанавливает исключительно erasures, но не настоящие errors (“тихо” поврежденные данные). Поэтому автор RAR сократил те шаги, которые требуются в полномасштабном классическом синдромном декодере для определения местоположения ошибок, то есть BM алгоритм (или более медленный алгоритм Евклида, который иногда используют). Вместо этого в RAR реализовали упрощенную процедуру вычисления полинома-локатора при известных положениях ошибок (во всяком случае, так как я понимаю среднюю часть их кода), которая описана в литературе рассматривающей классический алгоритм декодера и ее часть предшествует обычно BM.
Где все это можно прочитать в подробностях? Честно скажу, хорошей книжки не знаю, я кое-какую информацию, которой владею, почерпнул из большого количества разрозненных статей и из книги Error Control Codings: Fundamental and Applications, Shu Lin/Daniel Costello. Книга, наверное, не самая лучшая в плане ясности изложения и как обычно в ней много отстраненной математики (нам на практике не нужной), но она дает представление о классических кодах и способах их декодирования.
Что касается возможности избавления от квадратов - да, это возможно судя по статьям на тему FFT и декодеров RS, но более глубокой переделкой данной процедуры. Посмотрите хотя бы начальный (синдромный) и конечный (окончательно корректирующий данные) циклы - там все равно останутся квадраты при "не творческой" замене (без переработки).

 

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

 

Я думаю, что для RS-кодов сначала были придуманы именно синдромные декодеры, достоинство которых перед матричными - это умение находить (анализом этих самых синдромов) положение ошибок и определять их количество без привлечения внешних кодов. И применялись RS-коды сначала именно в режиме автоматического поиска и устранения ошибок - как самодостаточная вещь. Применялись в основном в системах связи с мелкими пакетами и жесткими требованиями к маленькой задержке, поэтому кодеры были в основном байт-ориентированные. Но затем, с развитием технологий, пошла работа с все более крупными блоками, а ошибки стали в основном ловить внешними кодами, от тривиальных CRC-32 до всяких convolution кодов (в той же связи часто применяемых совместно с RS). В результате, на первый план вышли матричные декодеры, которые ориентированы именно на erasures - с известным местоположением. В режиме erasures мы корректируем вдвое больше ошибок. Плюс матричные декодеры работают быстрее и требуют меньшую площадь при реализации на кристалле. Но для связи, для совместимости со стандартами и железными реализациями, осталось множество хорошо отлаженных реализаций синдромных декодеров. Во времена начала разработки RAR видимо такой алгоритм было легче найти в литературе/в сети.

 

О! Если вас не затруднит - "имя, сестра, имя!" И/или ссылку на описание, плиз!

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

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

 

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

 

Так, как там сделано - не быстрее, но это можно улучшить. У них в таблицы не введен фиктивный элемент нулевой и сделана явная проверка на нули в умножении. Если ввести - то фиг знает, может оказаться, что за счет компактности таблиц и лучшей укладки в кэш будет быстрее без прямой таблицы. В своих программах я не пользуюсь прямой таблицей для умножений никогда даже в GF(2^8). Но строю таблицу инверсий, она реально ускоряет работу. Понятно, что в GF(2^32) прямую таблицу для инверсии уже не построишь.

 

Еще хуже, там только Евклидом и можно...

Кстати, нет ли у Вас рабочей процедуры для Polynomial Evaluation, а именно для быстрого вычисления полинома N-1 степени в N точках одновременно через FFT за n log^2 n или за n log n в некоторых благоприятных ситуациях? Я так понял, это базисный примитив для всех быстрых матричных вычислений. Без него никуда.
И нужно его делать дофига и дофига раз...

Вроде для этого нужно делить полиномы с остатком, а этого я совершенно не просекаю, как делить, методом итераций Ньютона или где? Только вот разве что умножать полиномы научился=)))

 

таблицу инверсий можно построить очень просто и сверхбыстро, если есть функция [анти]логарифма, но, к сожалению, ее элементы при этом вычисляются в рандомном порядке и соответственно пользы от такой инверсии мало, таблица ведь заняла бы 2^32 * 4 = 16G. А вот быстро получить наперед заданный элемент этой таблицы или все элементы в порядке возрастания индекса - я не знаю как.

 

Пока трудно сказать. Копаю статью Криса Касперски "Информация, восставшая из пепла" - не исключено, что какой-ньдь из способов чтения сырых секторов даст нужный эффект. Но, конечно, нужна инфа об устройстве DVD'шных треков и секторов, пока что у меня такой нет.

Edit: сорри, взглючил - имел ввиду статью Касперски о чтении компакт-дисков, сама статья и её URL на работе остались.

 

Ну да. Отказываюсь от прожорливой локальной (по 2 кило!) избыточности в пользу экономичной глобальной. Итого - я в выигрыше. А то куда это годится: залетело два килобайта - и привет, 100 мегабайт избыточности не помогут.

Не уверен, что 20% - не слишком до фига. Впрочем, с DVD я до такой степени ещё не работал.

Не понял. Можно подробнее - что за матрица такая страшная? В rar-подобном алгоритме можно обойтись списком сдохших секторов (в самом пиковом случае около 100 кил) плюс собственно избыточностью (полсотни мегабайт).

 

Хмм... не думаю: сильно подозреваю, что приводы начинают использовать ECC только при несовпадении EDC (а это не CRC32, а adler32 - вычисляется быстрее, но вроде бы надёжность не хуже). Во всяком случае, восстанавливать с XCD сильно проще и быстрее, чем с ISO, а хорошая болванка на хорошем приводе и через 3 года после записи читается на ура.

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