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

http://file.qip.ru/file/109465225/ed7e7ff/crc32.html

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

 

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

Я бы не сказал, что проблем нет, их много и они были преодолены так или иначе, ценой времени перевода из 2^n -> prime (существует кстати много подходов, иногда жалеешь, можно по другому было сделать), ценой бОльших затрат диского пространства, ценой предобработки и постобработки - большая дрянь. Ну да, умножение можно векторизовать (раза в два только для целых?), но можно и сложение также и 4 и в 8 раз. Но в GF(2^n) другая беда - нужны часто и в огромных количествах логарифмы и непонятно откуда их брать, если поле большое.

Возникла интересная идея. Если рассматривать скажем сортировку, то кажется что быстрее n log n ее нельзя сделать, но цифровая для ограниченного набора разрядов имеет еще лучшую сложность n.

Видимо и коды Рида-соломона можно за O(n) придумать, тем более что есть БП-Хаара за O(n), вейвлеты типа.

 

А зачем скользящие-то нужны? Кстати на счет контрольных сумм - как это ни удивительно, но CRC можно считать в нескольких параллельных потоках, не только строго последовательно (байт за байтом). Для меня это тоже было в свое время удивительным открытием.

 

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

 

Это все происходит из-за того, что Intel вместо умножителя в GF(2^n) добавляет в процессоры всякую чешую мало кому нужную. Хотя иногда и что-то полезное добавляют - вот добавили, например, команду для подсчета CRC-32. Правда только с одним фиксированным полиномом (iSCSI).

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

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

 

При raw-чтении с диска что ли?

 

>При raw-чтении с диска что ли?
Да не, скользящие суммы используются для вылавливания пакетов без заголовков из сплошного потока. Только надо быть внимательным, казалось бы непробиваемая crc32 будет лажать как 2^(-16) из за эффекта Дни рождения.
Короче для контекстного поиска за O(n) вместо квадрата.

 

>Это все происходит из-за того, что Intel вместо умножителя в GF(2^n) добавляет в процессоры всякую чешую мало кому нужную.

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

 

потестил сегодня коды ридасоломона на плавающей точке SSE2. А фигли, кто разделяет расхожее мнение что таких не может существовать? Соблазн был велик, поскольку используется арифметика в чистом виде без всяких модулей. Однако превысить скорость того что у меня уже есть не удалось а это 10 метров/с, но наверняка можно. Eсли сумеете раза в три, будет смысл вставить ко мне в прогу.

 

persicum
любопытно, а почему бы не использовать, пожалуй, самый простой способ: файл разбивается на части и записывается в виде "лапши" блоков с заданным законом случайного распределения, каждый блок записан в "лапше" в среднем 2 раза. для восстановления записи держим битовую карту расположения блоков.

 

точней сказать 3 вхождения будет лучше, тогда первым делом буит восстановление по принципу: (copy_block1(i) xor copy_block2(i)) && (copy_block3(i) xor copy_block2(i)) ==> copy_block2 is failed. а затем более совершенные методы, если надо.

 

Вот так часто бывает, самое простое на деле оказывается самым сложным и наоборот. Имхо коды Рида-Соломона это самый простой метод помехоустойчивого кодирования, проще идеологически даже чем коды Хэмминга.
1) имеем k точек
2) проводим по ним полином k-1 степени, или вычисляем k коэффициентов
3) имея полином, вычисляем его в n-k дополнительных точках
4) имеем таким образом кодовое слово (n,k) т.е. длиной n символов
5) теперь имеем k любых символов, которые остались неповрежденными
6) восстанавливаем по ним тот же самый полином k-1 степени
7) вычисляем потерянные символы как значения полинома в потерянных точках
Как видно, метод абсолютно 100-пудовый и не имеет никаких подводных камней.

То что ты предлагаешь это самый современный и быстрый тип кодов – LT–коды, трансформация Лаби. Насколько я себе представляю, для 10000 символов там нужно порядка 12000 символов только чтобы достичь вероятности восстановления в 50%. Для 100000 блоков нужно будет 5000 дополнительных символов, или 5%, что уже приемлимо. Однако, вопрос об оптимальном распределении эти “2-3” ненулей в строке матрицы чрезвычайно сложный и запутанный. Теоретически пролученное самим Лаби распределение работает только в бесконечном пределе и плохо приспособлено для реальных конечных матриц. Поэтому используют огрубленное Robust распределение. Систематические коды LT еще более сложны и требуют уже пару LT-трансформаций сложным образом взаимосвязанных. И вообще, они рассчитаны на вероятность восстановления 50%, и если случается облом то реципиент должен попросить у сендера новые блоки для закача. Мне непонятно, сколько например нужно лишних блоков чтобы получить не 50%, а 99.9999999% восстановления инфы из файлов.

В моей проге реализовано уже несколько кодов, работающих на XOR и AND, это все коды которые заканчиваются на “PC”. Они требуют 5-10 лишних символов (не процентов!) и восстанавливают на 99.99999999% (1e-9 заложенная ошибка). Понятное дело, они содержат не 2-3, а сотни-тысячи ненулей. Я ими увлекался, когда поставил себе задачу обогнать ICEECC и QuickPAR в 10 раз. Однако необходимость даже в пяти лишних блоках была воспринята ламерами-юзверями скептически, им понятна только жесткая модель заплаток, чтобы каждая заплатка латала ровно одну дыру. Модель клубков и штопания дыр, когда непонятно сколько нужно взять ниток для ровного счета, им уже не нравится. Они не готовы тратить лишнее место и время на коды, часть которых служит только для балласта и подстраховки несовершенства алгоритма.

В общем, я пока не могу потратить месяц жизни на эксперименты с Лаби кодами, может потом когда доживу до лучших времен. Одно уже ясно сейчас – для работы с умеренными, а не чрезвычайно большими матрицами они требуют большого оверхеда (может 100%) Пусть профи меня поправят если что.

 

persicum
а чему у тебя размер блока равен?

 

любой кратный четырем. Кодек файловый, к конкретным носителям не привязан, поэтому выставлять точно например 2048 нет смысла. Просто выбираешь число блоков, сколько нравится, а размер блока вычисляется автоматически.

 

persicum

то есть 4-е бита может быть иль ток дискретно по байтам?

проясни эту фразу, пожалуйста: '5-10 лишних символов' на блок? и какова длина символа?

 

UbIvItS
файлы пакуются в блоки вида
[a1 a2 a3 a4...]
[b1 b2 b3 b4...]
[c1 c2 c3 c4...]
...
Функционально связываются только срезы блоков,
например a1 b1 c1..., потом a2 b2 c2... и т.д.
Размер блока как раз и кратен четырем байтам, чтобы удобно считывать в 32 разрядные регистры. А вот a1 b1 и так далее, это символы, их размер скрыт от юзера и равен разрядности конечного поля Галуа, которое на данный момент используется. Если XOR, то размер символа будет один бит, хотя за раз обрабатывается целых 32 их штуки.
Если алгоритм требует пять лишних символа для восстановления, то из лишних символов слагаются в итоге пять лишних блоков. Предел (n+5)/n равен 1, так что с ростом размера задачи пятью лишними блоками можно принебречь

 

persicum
поправь меня, коль я неправ: на блок в 32 бита тебе нужно 5 лишних, чтобы получить вероятность восстановления на 99.99999999%? кстати, хотелось бы узнать как сильно у тебя пухнет файл на получения такого высокого процента. не уж-то на ~ 15.625%?

 

UbIvItS
Для начала скачай одну из фирменных прог типа quickpar или iceecc чтобы лучше представлять себе что такое блок, как происходит восстановление и зачем вообще нужны блоки, почему нельзя защитить скажем отдельные байты или биты.

Теперь отвечаю. Я ведь нарисовал тебе схему уже, блоки кодируются вертикальными срезами. Это значит, независимо от размера блока (твои 32 бита тут роли не играют) для некоторых методов нужно взять их на 5 больше.
На 100-105, а на 1000-1005, те. 0.5%

 

persicum
так какой процент зашумлённости ты сможешь вытянуть при оверхеде 0,5%?

да, можно защитить и отдельные байты и биты -- другой вопрос -- 'зачем это делать?', ибо всё упирается в распухание файла и скорость работы [де]кодера

 

UbIvItS
Я не разбираюсь в кодовых расстояниях, децибеллах и прочей фигне, за которую академики получают звездочки на погоны, пусть себе пишут трактаты, а на мне лежит честь написания реальной проги.
Проги нашего семейства - это РАЙДы!!! А блоки это виртуальные девайсы.
Вот и все что нужно знать , эффективность 100%, фсе запасные блоки исправляют любую комбинацию блоков с данными. Если грабанул скажем 10 блоков из 25, то достаточно взять 10 запасных и все исправится. Речь идет о любых 10 блоках с данными и 10 любых блоках с кодами. Когда ты вызываешь прогу например с ключем -wrr1000-200, это значит РАЙД на 1200 виртуальных блоков из них 200 проверочных.