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

Тема в разделе "WASM.PROJECTS", создана пользователем persicum, 14 ноя 2008.

  1. persicum

    persicum New Member

    Публикаций:
    0
    Регистрация:
    2 фев 2007
    Сообщения:
    947
    Как то раз я выкачивал RAR архив, и он все время шел битым. Стал тестировать первую копию, сбой был гдето в начале. Скачал еще копию. Стал тестировать, сбой был гдето в конце. Было две битые копии... Тогда я взял расколол архивы пополам, и взял конец первого и начало второго. Так я получил цельный архив всего из 2-х копий =)))
     
  2. hidon

    hidon New Member

    Публикаций:
    0
    Регистрация:
    3 июн 2009
    Сообщения:
    5
    Вы конечно же правы, но дело в том, что это не курсач, а ДИПЛОМ, и к сажалению тема уже утверждена.
     
  3. persicum

    persicum New Member

    Публикаций:
    0
    Регистрация:
    2 фев 2007
    Сообщения:
    947
    sysprg
    Самая главная и первейшая уловка, насколько я понял, позволяющая сразу ускорить обычное FFT почти в два раза, это использование наряду с +1, -1 еще пары более глубоких радиксов, чисто мнимых i и -i. Умножение комплексного числа на чисто мнимую единицу не многим сложнее чем на 1 и -1 и очевидно сводится к обмену мнимой и реальной частей. И вот тут в GF(p) нас может поджидать облом. Скажем, в GF(A000001) мнимой единицей будет 3E3A2B0. Как можно быстро умножать на такую хрень, я себе не представляю.

    В поле GF(65537) с этим дела обстоят намного лучше, там i = 256, поэтому примение четвертых и более глубоких радиксов весьма целесообразно. Однако поле GF(65537) будет проигрывать предыдущему по размерности данных и числу допустимых блоков, поэтому лично мне не очень интересно.
     
  4. persicum

    persicum New Member

    Публикаций:
    0
    Регистрация:
    2 фев 2007
    Сообщения:
    947
    dimsoft
    прога обновилась до версии 1.84

    теперь можно явно задавать размер блока-тома-кластера, а также избыточность в процентах!
    То есть, наряду с конструкцией -wrr15000-1500, что означает 15000 блоков данных и 1500 блоков коррекции

    можно юзировать типа -wrr4096v-10% - это означает 4096 байт в блоке и 10% избыточных блоков.

    Поскольку эти конструкции взаимозаменяемы, поначалу в проге не было второго варианта, то с выходом ее на субсекторный уровень защиты вторая конструкция не помешает.
     
  5. persicum

    persicum New Member

    Публикаций:
    0
    Регистрация:
    2 фев 2007
    Сообщения:
    947
    dimsoft

    теперь правильные ключи такие для твоих целей:
    -wt -r
    -wrr16384v-100%
     
  6. dimsoft

    dimsoft New Member

    Публикаций:
    0
    Регистрация:
    31 май 2009
    Сообщения:
    15
    persicum
    а где скачать ?
     
  7. dimsoft

    dimsoft New Member

    Публикаций:
    0
    Регистрация:
    31 май 2009
    Сообщения:
    15
    нашел :)
     
  8. sysprg

    sysprg New Member

    Публикаций:
    0
    Регистрация:
    6 мар 2009
    Сообщения:
    65
    Согласен - обидно, что 2^32+/-1, 2^64+/1 и даже 2^128+/-1 - не простые числа. Длины же которую дает GF(65537) на DVD никак не хватит. :dntknw:
     
  9. sysprg

    sysprg New Member

    Публикаций:
    0
    Регистрация:
    6 мар 2009
    Сообщения:
    65
    Кстати к вопросу о том методе, который использует многократные FWT ради работы в GF(2^q). Долго думал, смотрел этот код, статьи всякие читал и т.п. в результате написал-таки свое FFT-подобное преобразование над чистым GF(2^q) в очень упрощенном прототипном виде - чтобы проверить вообще факт работы и количество основных операций, но не соревноваться в скорости. Получается что-то асимптотически близкое к n * log(n) * log(log(n)). Но как ни крути, на размерах за сотни (и тем более тысячи и более) этот метод все равно проиграет GF(простое число), где можно использовать векторный аппаратный умножитель. Поэтому пока что думаю, что к сожалению на больших матрицах GF(2^p) представляет интерес только для аппаратных реализаций (при нынешней архитектуре CPU, в которой нет умножения в GF(2^p) - хотя аппаратно такое умножение проще обычного).
     
  10. persicum

    persicum New Member

    Публикаций:
    0
    Регистрация:
    2 фев 2007
    Сообщения:
    947
    Зато есть другие здоровые простые, на которых можно сделать 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 ?
     
  11. persicum

    persicum New Member

    Публикаций:
    0
    Регистрация:
    2 фев 2007
    Сообщения:
    947
    Прога обновилась до версии 1.85 - что нового:

    1) убрал безумный счетчик на заголовке окна, который перегружал ОС обновляясь 10000 раз в секунду
    2) досрочный выход из процедуры поиска блоков, если найдено достаточно для восстановления - ключ -mf
     
  12. persicum

    persicum New Member

    Публикаций:
    0
    Регистрация:
    2 фев 2007
    Сообщения:
    947
    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

    что тоже самое, то не получается трансформация для вектора из пары бит, как не крути =((( Не знаю, по каким законам ее производить.
     
  13. persicum

    persicum New Member

    Публикаций:
    0
    Регистрация:
    2 фев 2007
    Сообщения:
    947
    Nothing
    Заколбасил сегодня умножение-деление в GF(2^32) вообще без малейших таблиц и потенциирования =)))
    Будет желание, почищу код от JMP


    Код (Text):
    1. function GF32_Mult(a,b:Cardinal):Cardinal; //input in eax,edx
    2. asm
    3.  push esi
    4.  push ebx
    5.  
    6.  mov esi,GF32_Prime;
    7.  
    8.  xor ebx,ebx
    9.  mov ecx,32
    10. @lll:
    11.  shr edx,1
    12.  jnc @nobit
    13.  xor ebx,eax
    14. @nobit:
    15.  shl eax,1
    16.  jnc @noreduct
    17.  xor eax,esi
    18. @noreduct:
    19.  loop @lll
    20.  
    21.  mov eax,ebx //result
    22.  
    23.  pop ebx
    24.  pop esi
    25. end;
    26.  
    27. function GF32_Inv(a:Cardinal):Cardinal;
    28. var i,s,x:Cardinal;
    29. begin
    30.  s:=1;
    31.  x:=a;
    32.  for i:=1 to 31 do begin
    33.   x:=GF32_Mult(x,x);
    34.   s:=GF32_Mult(s,x);
    35.  end;
    36.  Result:=s;
    37. end;
     
  14. persicum

    persicum New Member

    Публикаций:
    0
    Регистрация:
    2 фев 2007
    Сообщения:
    947
    Программулька обновилась до версии 1.96, обеспечивая тысячекратно более мощные и более быстрые коды РыдаСоломона, нежели ICEECC и QuickPAR. Хе-хе...

    Достигнуто строго последовательное читение данных с винтака, теперь скорость не падает с 50м/c до 2м/c из-за случайного доступа. Однако, это сделано не за счет специальных инкрементальных кодов как в ICEECC, а за счет транспонирования данных на винте и сурового свапежа... Ну ни че, можно обождать несколько минут ради такого дела.

    Ключики для глобальной защиты DVD скажем 10 секторов в томе-пакете такие
    crc32 -wt -r
    crc32 -wrr20480v-fittodvd

    У меня занимает минут 7-семь
     
  15. sysprg

    sysprg New Member

    Публикаций:
    0
    Регистрация:
    6 мар 2009
    Сообщения:
    65
    А какое там сейчас поле используется в самом быстром методе с интерполяцией Лагранжа - GF(2^q) или по модулю простого числа?
     
  16. persicum

    persicum New Member

    Публикаций:
    0
    Регистрация:
    2 фев 2007
    Сообщения:
    947
    ИМХО Лагранжеву интерполяцию за n log n в GF(2^n) еще никто не делал. Можете смело доводить до ума, публиковать/патентовать. Векторизуемость там хорошая, лучше не бывает, pxor/paddw. То есть на языке логарифмов нужно только складывать/вычитать.

    Правда, мне трудно представить релиз GF(2^24) без таблицы на 48/64 метров, но этот вопрос както урезонивается.

    Нельзя ли Вас попросить побенчить мой прог с Вашими разработками, а также с известным кодом на пр-нии Уолша с SSE2, последний в режимах 16 и 24 бит. Хотя там вроде даже 31 бит был... Интересно просто.
     
  17. sysprg

    sysprg New Member

    Публикаций:
    0
    Регистрация:
    6 мар 2009
    Сообщения:
    65
    Не волнуйтесь, я не занимаюсь 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 раз быстрее - при наличии бесплатных "академических" исходников практически всегда выбирают последние).
     
  18. persicum

    persicum New Member

    Публикаций:
    0
    Регистрация:
    2 фев 2007
    Сообщения:
    947
    Кое-что удалось сравнить... Моя прога c SSE2 раза в три быстрее чем академическая FWT-SSE2. То есть скорость обработки где-то 10 м/c против 3м/c. Секрета конечно нет, просто другой алгоритм.
     
  19. persicum

    persicum New Member

    Публикаций:
    0
    Регистрация:
    2 фев 2007
    Сообщения:
    947
    sysprg
    Новый век привнес новое понимание в кодирование Рида-Соломона. Если в 70-х годах прошлого века под ним понимался почти исключительно остаток от деления информационного полинома на другой, то в новом веке любой MDS код может быть назван кодом Рида-Соломона, и для его построения могут использоваться различные матрицы, а также разнообразные ортогональные преобразования. С быстрыми преобразованиями Фурье и Лагранжа-Ньютона я уже более-менее свыкся, а вот преобразование Уолша пока что за пределами моего понимания. Технически оно выполняется наиболее просто, но вот смысл и польза его покрыты густым туманом, хотя литература и примеры использования не испытывают недостатка.

    Не могли бы Вы просветить засранца и вдохновить его на новые подвиги, растолковав подоходчивее пользу от FWT? Как правило, эти трансформаты не пригодны для циклической свертки, что вызывает у меня панические затруднения, но в некоторых случаях такая свертка осуществима, как и некоторые другие виды сверток. Скачал книгу “Ортогональные преобразования в цифровой обработке сигналов”, но толку от нее как от “Самоучителя игры на скрипке”, без хорошего гуру не обойтись =(((
     
  20. sysprg

    sysprg New Member

    Публикаций:
    0
    Регистрация:
    6 мар 2009
    Сообщения:
    65
    Не совсем так - это известно очень давно, но только сейчас стало "модно" об этом говорить. Собственно сами создатели кода в 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 (с моей точки зрения). Некоторые вообще настолько заумны и завязаны на последние достижения в области теории чисел, что я даже общего их смысла не улавливаю при просмотре статей.