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

UbIvItS
про оверхед забуть пока, коды РидаСоломона его не требуют, равно как и лишних символов, там все символы приделе.

 

persicum
хех, что-то я вообще перестал понимать -- давай-ка определимся
итак, есть файл с энтропией N, увеличение эн-ии до 2*N даёт нам возможность закодировать около 50% возможных повреждений файла, при коих можно вытянуть исконную инфу без искажений -- для 99,9% нам нужна эн-ия уже 1000*N. эт я к чему? к тому, что в пределе у всех способов кодирования оверхед будет и будет равным, все способы отличаются ток кол-вом накладных расходов на код и скоростью работы.

 

UbIvItS
Если места ошибок неизвестны, то для полного восстановления нужно 3N символов, а если места ошибок известны, достаточно 2N символов. Вот и вся рухтама. У РАЙДов места ошибок известны, это те устройства, которые ты грабанул. Вот и весь наказ.

 

UbIvItS
короче, схлифасофски, ничего в 1000 раз раздувать не нужно, если хочешь вылечить 100 метров файлов вычисляй 100 метров кодов к ним. Твой скептицизм насчет энтропии мне понятен. Этот парадокс снимается тем, что райды исправляют не все мыслимые ошибки а только те, которые покрываются паттерном независимых устройств. Исправляются в конечном итоге не произвольные биты, а именно устройства.

 

persicum
случайно наткнулся ещё на одну реализацию кодов Рида-Соломона (с исходниками)
schifra.com/features.html

P.S. добавил для кучи. заинтересует, а потом не найду )

 

Спасибо за либру!
t00x

Не знаю, правда, радоваться мне теперь или огорчаться?
Бесплатный вариант исходных кодов скачал, но готовых сборок под Win32 что-то не видать… В общем, перешлю этот продукт более опытным товарищам, и они сделают вывод о пригодности или непригодности этих коммуникационных кодов в деле защиты файлов. Уж очень там много всего наворочено. На первый взгляд для чисто подчисток там конкретных алгоритмов нет, только вместе с ошибками.

Мой прог обновился до версии 2.13. Реализованы коды РидаСоломона на плавающей точке с полезной шириной символа 16 или 32 бит, заложенная погрешность 1e-2. Для этого я подцепил либру FFTW, которая реализует многопоточные трансформации

 

sysprg

Как вариант можно оставить все как есть и юзировать плавучие коды РидаСоломона! Пусть матерые математики поработают для дела защиты файлов и закачек =))) .ЩАс я использую мультирадикс-2-3-5-7, очень приятная вещь по сравненнию с радикс-2-4-8 для GF(65537)

Блин, самое сложное во всей этой головомойке это даже не коды Ридасоломона, а зачитывание больших объемов скажем 20G в программу (частная задача фрагментации). ICE и QuickPAR с этой задачей блестяще справились, а я кроме свапа ничего больще придумать не смог =((( Если только начинаю seek-ать по файлам скорость подкачки падает до 2 метров/c и ничего с этим поделать не могу. Решил от безысходности оставить полный свапинг файлов с удвоением-утроением дисковых требований =(((

 

t00x
вот кста, если тебя интересуют коды то можешь откомпилить эту кашерную обетованную Шифрину и сравнить быстродействие имеющихся там различных алгоритмов с моими для разных кодовых слов 128x128, 1024x1024, 16384x16384 (привожу матричную номенклатуру т.к. плохо разбираюсь в (n,k) )

 

http://art-drobanov.narod.ru/
Что-то похожее вроде нашел.

 

Знакомая вещь! Четыре года назад я с нее начинал, однако этот проект как и ICEECC является клоном PAR2 и повторяет все его ошибки и недочеты: медленные из-за большой вычислительной сложности коды, кубическое обращение матрицы, ошибочная сама по себе матрица с сингулярностями(невозможность обращения). Короче бред.
Моя прога сейчас пашет буквально в тысячи раз быстрее при идентичной восстанавливающей способности.

 

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

продолжаю неспешно блогить на Васм. За последние полгода быстродействие проги выросло раз в восемь за счет многих факторов, каждый из которых добавил быстродействия раза в полтора-два, включая обновленные коды, обновленные поля, многопоточность и т.д. Зачитывание выделено в отдельный поток и происходит в фоновом режиме. Свапеж то появлялся, то минимизировался, то исчезал, то опять появлялся... К сожалению, сейчас свапеж идет по полной и это видимо очень на долго.
Из удобств только меню FAR, persicum умеет прогать только с базовыми типами и аски строками... Вопщем щас глобальная защита DVD с 256000 блоками занимает 5 мин на core2duo

 

а повторите плиз - ссылка устарела

 

http://file.qip.ru/file/-Tw9bAvE/rsc32.html

Прога теперь здесь живет...
Заботиться о совместимости с предыдущей версией было бы слишком круто, поэтому проект можно сказать новый. Добавлена возможность базовых имен, т.е. имена формируются как
BaseName.FHash.RSC32
BaseName.s00_volXXXXXX.RSE32
...
BaseName.VHash.RSE32

Доки и инструкции сознательно удалены, только для умудренных пользователей которые уже юзали похожие проги как то ICEECC/QuickPAR/DVDisaster...

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

 

Использовал долгое время прогу CRC32, за все это время, я так понял, прога претерпела массу изменений, будучи даже переименованной в RSC32 для пущей убедительности =))

Интересует старый вопрос, но с новыми дополнениями. Как (какими ключами) можно сделать RAID на DVD, когда, например, на 5 DVD болванок идет 1-а, 6-ая чисто под коды восстановления, так чтобы эта волшебная болвнка могла, в случае чего, восстановить любую из предыдущих 5-ти с данными (на случай если болванка с данными потеряется, исцарапается или взорвется в недрах привода)!!
Как реализовать это, какие ключики у проги крутить и на что обращать внимание?
Сколько лучше блоков выбрать для надежной защиты и как это будет влиять на скорость кодирования?

У проги по прежнему есть выбор между кодами Рида-соломона и "альтернативными" или теперь она работает с каким-то одним видом кодов?

 

Напомню что раньше алгоритм действий для вышеописанной мной операции был следующий:

Попробуем замерить чистое время кодирования для 30G данных, 15% избытка:
RS32, 5000 блоков – 2ч 40мин
LDPC, 30000 блоков – 50 мин

Порядок действий таков:
1) Создаем директории Disk1, Disk2, Disk3…, копируем туда диски.
2) Рассчитываем контрольные суммы-64бит
сrc32 –wt –r –n2
3) Если отдаем предпочтение Риду-Соломону и 5000 блокам, тогда
crc32 -wrr5000-fittodvd -ed -mu1.5g -sn10 -hr10 -tm3
4) Если отдаем предпочтение LDPC и 30000 блокам, тогда
crc32 –wrr30000-fittodvd -ed -mu1.5g -sn10 -hr10 –tm2
5) После кодирования проверяем, что все файлы на месте
сrc32 –rt
6) Проверяем еще, что все блоки тоже на месте
сrc32 –crr

Ключики все те же или теперь "что-то новенькое"? =))

 

NightKeeper
принцип прост -

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

 

NightKeeper
За последнее время медленные квадратичные и вероятностные алгоритмы были заменены на быстрые линейные(!) и при этом детерминированные(!). Это позволяет в реальном времени скажем 100 метров/c кодировать миллион блоков с эффективностью ровно 100%. Актуальные ключи в менюшке ФАРа.

 

а где скачать последнюю версию ?

 

ссылка на руборде
http://forum.ru-board.com/topic.cgi?forum=5&bm=1&topic=24050&start=0

там еще Ютюб есть =)))

 

persicum можете помочь с расчетом ЕСС для карты памяти Memory stick ?