Как то раз я выкачивал RAR архив, и он все время шел битым. Стал тестировать первую копию, сбой был гдето в начале. Скачал еще копию. Стал тестировать, сбой был гдето в конце. Было две битые копии... Тогда я взял расколол архивы пополам, и взял конец первого и начало второго. Так я получил цельный архив всего из 2-х копий =)))
sysprg Самая главная и первейшая уловка, насколько я понял, позволяющая сразу ускорить обычное FFT почти в два раза, это использование наряду с +1, -1 еще пары более глубоких радиксов, чисто мнимых i и -i. Умножение комплексного числа на чисто мнимую единицу не многим сложнее чем на 1 и -1 и очевидно сводится к обмену мнимой и реальной частей. И вот тут в GF(p) нас может поджидать облом. Скажем, в GF(A000001) мнимой единицей будет 3E3A2B0. Как можно быстро умножать на такую хрень, я себе не представляю. В поле GF(65537) с этим дела обстоят намного лучше, там i = 256, поэтому примение четвертых и более глубоких радиксов весьма целесообразно. Однако поле GF(65537) будет проигрывать предыдущему по размерности данных и числу допустимых блоков, поэтому лично мне не очень интересно.
dimsoft прога обновилась до версии 1.84 теперь можно явно задавать размер блока-тома-кластера, а также избыточность в процентах! То есть, наряду с конструкцией -wrr15000-1500, что означает 15000 блоков данных и 1500 блоков коррекции можно юзировать типа -wrr4096v-10% - это означает 4096 байт в блоке и 10% избыточных блоков. Поскольку эти конструкции взаимозаменяемы, поначалу в проге не было второго варианта, то с выходом ее на субсекторный уровень защиты вторая конструкция не помешает.
Согласен - обидно, что 2^32+/-1, 2^64+/1 и даже 2^128+/-1 - не простые числа. Длины же которую дает GF(65537) на DVD никак не хватит.
Кстати к вопросу о том методе, который использует многократные FWT ради работы в GF(2^q). Долго думал, смотрел этот код, статьи всякие читал и т.п. в результате написал-таки свое FFT-подобное преобразование над чистым GF(2^q) в очень упрощенном прототипном виде - чтобы проверить вообще факт работы и количество основных операций, но не соревноваться в скорости. Получается что-то асимптотически близкое к n * log(n) * log(log(n)). Но как ни крути, на размерах за сотни (и тем более тысячи и более) этот метод все равно проиграет GF(простое число), где можно использовать векторный аппаратный умножитель. Поэтому пока что думаю, что к сожалению на больших матрицах GF(2^p) представляет интерес только для аппаратных реализаций (при нынешней архитектуре CPU, в которой нет умножения в GF(2^p) - хотя аппаратно такое умножение проще обычного).
Зато есть другие здоровые простые, на которых можно сделать radix-4, radix-8 и даже radix-16 =))) Но боюсь, на это у меня уже никогда не хватит пороха... Кроме выбора самих чисел, для реальной проги нужно еще решать вопросы упаковки и другие сопутствующие задачи. Поздравляю, это тянет на публикацию или изобретение. Я не встречал таких быстрых оценок ранее Очень обидно за отсутствие умножения в процессоре двоичных полиномов. На фоне уже имеющегося арифмитического умножения оно далось бы инженерам абсолютно даром. А польза могла бы быть в crypto и для псевдослучайных чисел помимо всего Векторный аппаратный pXOR тоже заруливает... Вообще, табличный Look-up умножитель для 16-бит может составлять серьезную конкуренцию арифметическому умножению в GF(p). Кстати, ICEGraphics ICEECC обновился до 2.7 и еще больше ускорил Look-up-16 за счет применения MMX. А насчет аппаратного умножения - так это не совсем чистый сахар - нужно еще редуцировать результат, а это еще и еще умножения или деления... Я все думал как использовать FWT не в GF(2^n), а в GF(p), где ему легко и вольготно. Хотел заменить некоторые или даже все свои FFT на FWT, но пока на это у меня нет достаточных познаний. Уж больно хочется послать подальше все эти умножения и сделать все на +1 и -1. Вы пишите, что код Хадамара имеет дистанцию n/2, это значит MDS? А разве не любой MDS можно приспособить для ERASURES и получить чистый n ?
Прога обновилась до версии 1.85 - что нового: 1) убрал безумный счетчик на заголовке окна, который перегружал ОС обновляясь 10000 раз в секунду 2) досрочный выход из процедуры поиска блоков, если найдено достаточно для восстановления - ключ -mf
b]sysprg[/b] Сижу и думаю, а можно ли применить Walsh Transform непосредственно в GF(2^n). В Wiki написано, что группа (1,-1,x) изоморфна (0,1,^) и что можно построить матрицу Хадамара-Уолша для нулей и единиц, если стартовать с [ 0 1], а затем выписывать все натуральные числа подряд в двоичном виде и снизу реккурентно добавлять две матрицы от предыдущего шага. Я думаю, результат будет такойже, как если бы взять матрицу [1...-1] и 1 заменить на 0, а -1 на 1, и использовать xor вместо умножения. В общем, если вернуться опять к 1 и -1, то под единицей можно понимать "взять число как есть", а под -1 - "взять число и инвертировать все биты". Никак не пойму, как сделать Уолш-преобразование даже для матрицы 2x2 =((( Если взять 1 1 1 -1 или [0 1]'*[0 1]= 0 0 0 1 что тоже самое, то не получается трансформация для вектора из пары бит, как не крути =((( Не знаю, по каким законам ее производить.
Nothing Заколбасил сегодня умножение-деление в GF(2^32) вообще без малейших таблиц и потенциирования =))) Будет желание, почищу код от JMP Code (Text): function GF32_Mult(a,b:Cardinal):Cardinal; //input in eax,edx asm push esi push ebx mov esi,GF32_Prime; xor ebx,ebx mov ecx,32 @lll: shr edx,1 jnc @nobit xor ebx,eax @nobit: shl eax,1 jnc @noreduct xor eax,esi @noreduct: loop @lll mov eax,ebx //result pop ebx pop esi end; function GF32_Inv(a:Cardinal):Cardinal; var i,s,x:Cardinal; begin s:=1; x:=a; for i:=1 to 31 do begin x:=GF32_Mult(x,x); s:=GF32_Mult(s,x); end; Result:=s; end;
Программулька обновилась до версии 1.96, обеспечивая тысячекратно более мощные и более быстрые коды РыдаСоломона, нежели ICEECC и QuickPAR. Хе-хе... Достигнуто строго последовательное читение данных с винтака, теперь скорость не падает с 50м/c до 2м/c из-за случайного доступа. Однако, это сделано не за счет специальных инкрементальных кодов как в ICEECC, а за счет транспонирования данных на винте и сурового свапежа... Ну ни че, можно обождать несколько минут ради такого дела. Ключики для глобальной защиты DVD скажем 10 секторов в томе-пакете такие crc32 -wt -r crc32 -wrr20480v-fittodvd У меня занимает минут 7-семь
А какое там сейчас поле используется в самом быстром методе с интерполяцией Лагранжа - GF(2^q) или по модулю простого числа?
ИМХО Лагранжеву интерполяцию за n log n в GF(2^n) еще никто не делал. Можете смело доводить до ума, публиковать/патентовать. Векторизуемость там хорошая, лучше не бывает, pxor/paddw. То есть на языке логарифмов нужно только складывать/вычитать. Правда, мне трудно представить релиз GF(2^24) без таблицы на 48/64 метров, но этот вопрос както урезонивается. Нельзя ли Вас попросить побенчить мой прог с Вашими разработками, а также с известным кодом на пр-нии Уолша с SSE2, последний в режимах 16 и 24 бит. Хотя там вроде даже 31 бит был... Интересно просто.
Не волнуйтесь, я не занимаюсь reverse engineering-ом Вашей программы. Но с интересом наблюдаю за появлением в ней новых методов. Поэтому и интересуюсь, произошел ли переход обратно на GF(2^q) (с модулярной арифметики). Что касается патентования - могу Вам помочь с этим, конечно, если возможно найти с Вами взаимовыгодные условия, и если Ваш метод имеет какие-то принципиальные отличия от уже описанного в существующих статьях Didier и в прочих. Кстати патентование занимает минимум два года и патент легко могут оспорить любые люди, кто имеет статьи с доказательством их приоритета. Поэтому патентованием есть смысл заниматся - но это дело рискованное и не гарантированное по результатам. Даже если патент будет получен, не факт, что он принесет хоть 1$ - так как есть куча альтернативных методов вычисления кодов Рида-Соломона. Конкруенты просто реализуют что-то другое. Разница в скорости в два раза никого не смутит. Выгода патентования таких вещей, где нельзя закрыть все пути обхода - это только делать себе имя (если речь идет об авторе) или увеличивать оценочную стоимость компании в глазах инвесторов на переговорах (если речь идет о владельце имущественных прав). С моей точки зрения и то, и другое важно и нужно - но нужно отдавать себе отчет, что прямых денег с таких патентов не заработаешь (точнее - только на удачу). Из-за умножений? Да, нужно будет сравнить с той программой. Но с моими разработками нельзя сравнивать напрямую, потому, что они ориентированы на RAID-подобные системы, где используются матрицы 32 x 32 и еще меньше. В этом случае FFT-подобные методы (как и преобразование Уолша) дают больше накладных расходов, чем пользы. Плюс на практике матрицы не квадратные, а типа 8 x 2 или 24 x 8. В результате Ваши методы проигрывают моему квадратичному в декодере и патентованному логарифмическому в encoder-е методу, причем в разы. Но это совершенно нормально, учитывая, что для Ваших методов какая-нибудь матрица типа 8 x 2 (RAID-6) это вырожденный предельный да еще и truncated случай, а не нормальное явление. Глядя на Ваши успехи с имплементацией разных видов FFT, я планирую написать программу с FFT, для больших матриц. Но никак не доходит дело до этого, так как это скорее важный задел на будущее, чем практическая потребность. Сейчас прямого применения для нее нет (у меня). В теории применения есть, но не такие, где можно было бы очевидным образом сделать бизнес. Защита DVD и тому подобное - это очень узкие ниши. И при наличии в Интернете свободных и бесплатных исходников с преобразованием Уолша под SSE - непонятно, как кому-то продать свои программы (пусть даже они будут в 2-10 раз быстрее - при наличии бесплатных "академических" исходников практически всегда выбирают последние).
Кое-что удалось сравнить... Моя прога c SSE2 раза в три быстрее чем академическая FWT-SSE2. То есть скорость обработки где-то 10 м/c против 3м/c. Секрета конечно нет, просто другой алгоритм.
sysprg Новый век привнес новое понимание в кодирование Рида-Соломона. Если в 70-х годах прошлого века под ним понимался почти исключительно остаток от деления информационного полинома на другой, то в новом веке любой MDS код может быть назван кодом Рида-Соломона, и для его построения могут использоваться различные матрицы, а также разнообразные ортогональные преобразования. С быстрыми преобразованиями Фурье и Лагранжа-Ньютона я уже более-менее свыкся, а вот преобразование Уолша пока что за пределами моего понимания. Технически оно выполняется наиболее просто, но вот смысл и польза его покрыты густым туманом, хотя литература и примеры использования не испытывают недостатка. Не могли бы Вы просветить засранца и вдохновить его на новые подвиги, растолковав подоходчивее пользу от FWT? Как правило, эти трансформаты не пригодны для циклической свертки, что вызывает у меня панические затруднения, но в некоторых случаях такая свертка осуществима, как и некоторые другие виды сверток. Скачал книгу “Ортогональные преобразования в цифровой обработке сигналов”, но толку от нее как от “Самоучителя игры на скрипке”, без хорошего гуру не обойтись =(((
Не совсем так - это известно очень давно, но только сейчас стало "модно" об этом говорить. Собственно сами создатели кода в 60-х годах уже описали его через FFT, в том числе с разными вариантами использующими Fermat Primes. Использование интерполяции Лагранжа это тоже можно сказать "классика", как минимум 80-е годы прошлого века она уже использовалась в обосновании патентованного алгоритма декодирования Berlekamp-Welch. Просто раньше все это было уделом одних только математиков, а сейчас начали появляться и программные реализации, например, Ваша. Обычное Фурье в модулярной арифметике будет работать быстрее за счет аппаратного умножителя. Смысл FWT в том, что с его помощью можно сделать GF(2^m). Вашей программе это IMHO не нужно - нет проблемы "вынести" одно число за пределы блока для перехода между GF(prime) и 32-битными целыми. Вам ведь нужно быстродействие максимальное. А FWT в небезызвестных нам работах применено конкретно для работы в GF(2^m), что оправдано только когда жестко стоит задача использовать конкретно GF(2^m) и ничего другого. Есть и другие методы аналогичные FFT и при этом над GF(2^m), но они еще намного более непонятные, чем FWT (с моей точки зрения). Некоторые вообще настолько заумны и завязаны на последние достижения в области теории чисел, что я даже общего их смысла не улавливаю при просмотре статей.
