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

Откуда там логарифм? Логарифм берется от техники разделяй-и-властвуй, а там делить вроде нечего. LDPС должен чисто работать за O(n).

Я вот надыбал статей из инета про матричный LDPC за O(n), матрица обращается тоже за O(n) и остается при этом разреженной(!), так что и декодирование за O(n). Фантастика, накаких тебе belief prolongation, beparite graph и прочих заумов!

Единственная проблема, пока не знаю, как приспособить это для защиты файлов. Ситуация повторяет ту, что была с FFT - его я смастерил сразу, а как применять - это был большой вопрос...

 

Мои дорогие специалисты, надеюсь когда-нибудь у вас появится возможность и желание отдохнуть от заработков и ответить на пару персональных вопросов:

sysprg
уважаемый nothing неоднократно утверждал и утверждает, что короткий интерливный код по свойствам эквивалентем широкому. Как хоть такое может быть? o:

nothing
Walsh matrix прикольная оказалась матрица, состоит только из 1 и (-1) и поэтому обещает быть существенно быстрее FFT, т.к. умножений не требуется. Непонятно только ее использование в GF(2^m), что подразумевается под произведением (-1) на двоичный полином?

 

nothing

И еще, чего-то свертка у меня с FWT не получается... Там как-то хитрее нужно.
Если сверкта через FFT вычисляется как iFFT(FFT(a)*FFT(b)), то 1/N*FWT(FWT(a)*FWT(b)) почемуто не работает =(((

 

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

Walsh matrix аналогична по свойствам матрице Адамара, а известно, что кодовое расстояние у кодов Адамара = n / 2, поэтому не факт, что использование Walsh matrix перспективнее, чем FFT над мультипликативной группой - придется вводить много дополнительных фиктивных данных = 0 и отбрасывать часть вычисленных кодовых слов.

Вообще с FFT over GF(2^m) дела обстоят намного сложнее, чем с FFT over GF(p), где p - простое число. Собственно об этом я и говорил в начале нашего общения. В поле GF(2^m) нет операции отрицания: x = -x. Это создает трудности с реализацией классических FFT-подобных преобразований. Честно говоря я пока не знаю, как практическим алгоритмом именно в GF(2^m) сделать FFT-подобное преобразование за n * log(n), а не медленее. Это не тоже самое, что сделать его в поле GF(p), где p - простое число. Алгоритмы для работы в мультипликативных полях широко известны, по ним есть сотни статей и реализаций, от целочисленных до использующих FP-арифметику. Мне они не нравятся тем, что требуют предварительной или пост-обработки данных из-за того, что p < 2^m или p > 2^m и мы должны избегать определенных символов или во входных, или в выходных блоках и хранить дополнительную информацию вместе с блоком. Да и для аппаратной реализации они менее удобны, чем алгоритмы над GF(2^m). У меня есть реализация быстрого преобразования (не FFT), которая делает вычисления именно в GF(2^m) за n^log(3, 2) (как в алгоритме Карацубы), но как быть с FFT (NTT) за n*log(n) именно и конкретно в GF(2^m) - пока не знаю.

 

внимательно прочитал все 7 страниц
подскажите
CRC32.exe -wt имя файла - создает таблицу, а как потом создать избыточность ?
приминительно к хранению на usb-флеш с размером кластера 4096, чтобы информация выдержала полное уничтожение файловой системы ?
в ICEECC.exe резал на кусочки по 4096 - потом можно собрать в виде файлов и востановить.
как в crc32 сделать подобное ? (я так понимаю это будет намного быстрее ?)

 

вот так ?
crc32 -wrr1000-1000 -mu1g -pow10 -tm7 -va4

не понятна строчка
-wrr[nn-<mm,FitTo<CD,DVD,DVD2,Disk>>][-Path] write recovery record;

как создать 100% избыточность ?
не могу написать ключ для создания файлов по 4096

 

nn - число блоков данных
mm - число блоков восстановления

Никак не могу понять, под числом 4096 у Вас скрывается желание иметь 4096 байт в блоке или 4096 блоков в проекте? С ключами помогу, но после этого уточнения

 

Вы там какой ползунок конкретно в 4096 устанавливаете? Для 500 мегов 4096 байт на блок не слишком ли дофига блоков получается? 120000 для Айса совершенно не подъемны. 100% избыточности для лечения полного краха файловой системы не обязательно, можно и 10% взять. Просто прога должна уметь искать данные со сдвигом.
Достаточно снять образ диска и вскрыть его просто в режиме поиска со сдвигом. И Айс, и Пар, и my prog это умеют

 

persicum
4096 это размер кластера на файловой системе, я считаю что в самом худшем случае при падении носителя соберу много файлов по 4096. Файлы большего размера могут быть битые (фрагментированы).
или я не правильно решаю задачу надежного хранения архивов по 100Мб ?
(был случай когда HDD умер - причем сильно ~8000 секторов очень плохо считались (неизвестно то ли считалось что ранее писалось) и ~13000 просто не прочитались; а там и данные и backup на разных логических хотелось бы панацею от подобного случая)

 

то есть взять размер кластера по 16384 и крах файловой системы не страшен ?

 

dimsoft

Должен Вас огорчить – PAR-подобные программы, ICEECC-QuickPAR-persicum’s CRC32 не предназначены для посекторной защиты носителей по многим причинам:
1) Огромное время счета (кроме persicum’s CRC32), вплоть до десятков часов или суток
2) Заголовки не оптимизированы под такое большое число блоков, гигантские по размеру – могут занимать 50% и более от избыточности (это называется Efficiency в этих прогах). Неизвестно, смогут ли заголовки выдержать нарезку на кусочки секторного размера и сохранить при этом работоспособность.
3) Нет синхронизации блоков с синхронизацией секторов, один неисправный физический сектор будет уносить два блока. Файлы стыкуются голова-к-хвосту без выравнивания под начало каждого файла, в результате логические блоки смещаются по отношению к физическим. Это не относится к QuickPAR, там идет набивка каждого файла до размера блока, но в любом случае QuickPAR просто чумеет от большого числа файлов-блоков.
4) Кроме того, в программе persicum’s CRC32 отсутствует явное задание размера блока – за ненадобностью. Присутствует только выравнивание блоков под заданный размер (по умолчанию 2048 байт). Предполагается, что юзер задаст какое нибудь круглое число блоков, скажем 1000 или 20000, а прога сама выберет подходящий размер блока с учетом выравнивания.

Если, как Вы предлагаете, создать посекторную защиту с избыточностью 100-200%,
то тогда (при условии сохранности заголовков!!!) эти проги конечно смогут из нарезанной лапши по 4096 байт вернуть обратно файлы… Но, я не могу рекомендовать такой подход. В общем, обычно ICEECC-QuickPAR работают с метровыми блоками, в которых ТЫСЯЧИ секторов. Мой прог может довольно эффективно работать с блоками, в которых ДЕСЯТКИ секторов. Разница на лицо, но для посекторной защиты эти проги одинаково непригодны.

dimsoft

При серьезном подходе к делу я не вижу разницы в “наукоемкости” между FFT, FWT, GF(2^n), GF(p). Скачиваете статьи или abstracts, если PDF не имеет открытого доступа. Штурмуете публичные библиотеки, конспектируете работы или ксерокопируете. С годами приходит все более глубокое понимание. Публикаций и книг по RS-FWT-GF(2^n) я скачал достаточно, они легко гуглятся, есть например перевод “Ортогональные преобразования в цифровой обработке сигналов” и т.д.

При дилетантском подходе FFT-GF(p), действительно, несоизмеримо проще понять и реализовать. Достаточно взять уже имеющийся FP-FFT и повыкидывать оттудова нах комплексные числа и/или w-факторы. Пример есть даже на этом форуме в A&O. Однако таким путем мы получим лишь банально-работоспособный вариант очень далекий от максимальной эффективности. Ваши прошлые опасения справедливы – а если матрица не квадратная, а скажем 10x100? Считать для всех 100x100, а 90 значений выкидывать? А если нужна свертка по модулю x^n, набивать нулями до x^2n, а потом старшую половину произведения опять выкидывать? И так далее и так далее, Не зря существуют всякие там MultiRadix-Shifted-Twisted-Truncated FFT, понять и реализовать которые ИМХО ничуть не проще чем FWT-GF(2^n)

N log (N) там вроде никто не обещал. За исключением некоторых особых случаев длины 2^2^N. Стандартная сложность там N log^2 N местами N log^3 N.
И по памяти кстати тоже!!! Отжирает много больше, чем единственный вектор для обычного FFT.
Reed-Solomon, скорость исправления которого больше для малых повреждений чем для максимально возможных, тоже имеет N log^2 N. В моей проге, это однако чистый N log N, потому что скорость исправления у меня всегда равна скорости создания и не зависит от фактических повреждений. Причины этого очевидны – так гораздо-гораздо проще было =)))

Все статьи в один голос утверждают значительное превосходство FWT-GF(2^n) над FFT-GF(p). Как я понимаю, там есть особая Dyadic-XOR-convolution, типа x(a xor b)*y(b). Потом берут интерполирующий полином Лагранжа и с помощью этой свертки быстро вычисляют факториальные выражения типа (x-a)(x-b)(x-b)…, и этой интерполяцией латают дыры. Вроде так. Якобы это все работает в реальном времени в отличие от FFT(GF(p)), который хорош только в асимптотике.

Пока мое понимание на этом и ограничивается. Я не знаю как скрестить (-1) и GF(2^n), в котором ее нет.

 

Если не гоняться за посекторной защитой, то с помощью проги CRC32 можно успешно защищать файлы на субсекторном уровне

Пример:
Защитить 200 мешков файлов на фляге:

Сначала
crc32 –wt
Если есть подкаталоги то
crc32 –wt –r

потом:
Допустим, 20% избыточности, 15000 блоков, выравнивание 4096 байт, разбить на 10 кусков и положить еще 10 копий хедеров:

crc32 –wrr15000-3000 –tm7 –va4096 –sn10 –hr10

Читаем:

Код (Text):

1. Encoding Method..............: RS32_FFT
2. Number of Data Volumes.......: 13536
3. Number of Recovery Volumes...: 3000
4. Total Size...................: 221,766,664
5. Recovery Size................: 55,570,192
6. Overall Size.................: 277,336,856
7. Size of Volume...............: 16,384
8. Size of Buffer...............: 16,384 (100%)
9. Volume Alignment.............: 4,096
10. Redundancy...................: 22.16%
11. Header Redundancy............: 10
12. Efficiency...................: 88.45%
13. Memory Required..............: 270,996,352
14. SSE2 Support.................: Enabled
15. Sizing Scheme................: 10 Equal Files
16. Swapping.....................: Minimized

Видим что все ништяк, в одном томе-блоке порядка 4 секторов, эффективность довольна велика, около 90%
Жмем YES!


Вопрос о том, как лечить в случае обвала файловой системы фляги это отдельная история

1) снять образ (а кстати, чем?)
2) вскрыть хедеры
3) вскрыть блоки и получить файлы

 

переместил все в один RAR архив БЕЗ сжатия, с понтом дела это якобы образ фляги

1) вскрываем хедеры
crc32 -shd -sa

2) нашла пару хедеров с одинаковыми номерами, переименовываем их в crc32.tab и crc32.sum

3) вскрываем блоки и лечим
crc32 -rrr -sa

 

persicum
провел эксперимент с ICEECC
400 метров данных + ecc файл до размера cd (программа написала 97%) записал - просверлил 2 дырки = удалось восстановить только 93,2% блоков => данные потеряны (а ковырялась прога 20 мин )

при этом в тестах с 200% избыточностью разрушал 50% файла и нормально востанавливало.

образ снимал isobuster, с HDD r-studio

а модное сейчас cuda не ускорит данную математику ?

 

Жаль, что Вы конфигурацию не указываете скока было блоков - у Айса наз sourceblockcount

Вот ключи для 50000 блоков данных
-wrr50000-fittocd -tm7

Пары минут должно хватить

 

С этим полностью согласен. Можно, конечно, взять готовые лучшие алгоритмы для всех этих multi-radix-twisted-truncated FFT отточенные математиками за десятилетия под их чисто счетные floating point-задачи, но их эффективная конверсия в GF(q), где q - простое число зачастую будет нетривиальной задачей, уж больно много тончайших уловок они используют и не все можно понять если ты не специалист в этой области математики (так, чтобы по-простому перенести это в целочисленную арифметику)... Если брать количество уловок и статей по извращенно-ускоренному "чистому" "математическому" FFT, то оно огромно и за разумное время понять все трюки не будучи профессиональным математиком вряд ли возможно, а там еще всякие трюки с правильной раскладкой по линиям кэшей и т.п. Однако пусть и не идеальный, но ХОРОШИЙ алгоритм сделать из классического FFT можно.

На практике зачастую будет еще хуже, потому, что там асимпточиески часто N * log^2(N), а практически может быть N*log^2(2^q). Понятно, что асимптотически при N -> 2^q это будет N * log^2(N), но на практике берешь 32-битный код и получаешь скорость N*1024.

Да, я прочитал одну статью об этом и посмотрел код программы с FWT, но там как раз неявная константа лезет от разрядности слова в 2(M - 1) = 62 для 32-битного кода. То есть этот метод хорош когда жестко нужно именно GF(2^m), но он не побьет Ваше FFT в GF(простое число) для которого у процессора есть команда умножения. Вспомните мое удивление, когда оказалось, что Ваша прежняя программа (квадратичная) на больших длинах обгоняет в разы мои асимптотически намного более продвинутые (субквадратичные) методы в GF(2^m) просто за счет того, что невозможно ручной имплементацией полиномиального умножения побить скорость аппаратного умножителя в SSE-регистрах.
IMHO используемый Вами подход с вычислениями в GF(простое число) + аппаратный умножитель + отсутствие требования работать жестко в GF(2^m) можно побить по скорости только более сильно оптимизированной имплементацией, или же на малых длинах. Или открытием новым в области теории кодирования.

 

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

 

sysprg
Не могли бы Вы объяснить мне на пальцах, как всетаки преодолевается противоречие с наличием -1 в Walsh matrix и отсутствием ее в GF(2^n)? Не понятны самые базовые принципы...

calidus
Моя скромная поделка не достойна изучения, портирования и оптимизации. Это просто затяжной психоз недалекого ламера. Для создания такого масштабного продукта, который чудовищным образом расходует ресурсы CPU, RAM и HDD, у меня нет ни малейшей квалификации.

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

Начни свой собственный открытый FASM проект. За спектральными заумами сразу не гонись, начинай с Матрицы Коши, она достаточно быстро работает до 2000-4000 блоков. Думаю, коллекция разных движков у sysprg не уступает по разнообразию твоей коллекции вирей и троянов... Любезно предоставленный движок от sysprg это будет кость, а мясо в виде открытия-закрытия файлов наростишь сам.

Вообще, чудеса с трансформацией файлов, волнующие воображение программистов, подразделяются на три категории:

1) шифрование, превращение файлов в нечитаемый вид и обратно
2) компрессия, уменьшение длины и обратная распаковка
3) помехоустойчивое кодирование, волшебные заплатки латают дыры в файлах так, что не остается никаких следов.

Чудо обратного преврашения шумообразной каши не в один какойто конкретный файл, как в пунктах 1-2, а в ЛЮБОЙ файл из заданной коллекции ИМХО несравненно более интригующее. Однакож шифрованием увлекаются тысячи, компрессией сотни любителей, и коррекцией ошибок - буквально единицы!

Так что войдешь в когорту самых избранных и выдающихся =)))

 

dimsoft
Всетаки убежден, что работая с ICEECC, ты путаешь длину с диаметром, как говориться...
Когда ты устанавливаешь падучий список SourceBlockCount в 4096, то для 400 метров данных это означает
4096 кластеров по 100000 байт каждый,
а вовсе не 100000 кластеров по 4096 каждый,
как тебе бы хотелось. Разберись с этим хорошенько

Ключи для 50000 блоков (кластеров как ты любишь их называть) я уже приводил

 

dimsoft
А, наконец понял как ты с ICEECC работаешь...
Если у тебя скажем, 100 метров, то ты вводишь BlockSize 4096.
А если у тебя 400 метров, то ты вводишь уже BlockSize 16384.

При этом SourceBlockCount автоматом устанавливается в 20000 блоков, что дает 30мин счета для 1 CD.
Только это бессмысленно, поскоку Айс объединяет файлы голова-к-хвосту вплотную, синхронизации между блоками и файлами там нет, один дохлый кластер на флешке будет уносить два блока ICEECC... Ну и страшно долго...