Описание кода Рида-Соломона |
Здравствуйте, гость ( Вход | Регистрация )
Описание кода Рида-Соломона |
SuperMax |
6.7.2014, 0:55
Сообщение
#1
|
Администратор Группа: Root Admin Сообщений: 6 295 Регистрация: 7.1.2006 Из: Красноярск Пользователь №: 1 |
Описание кода Рида-Соломона.
Код Код Рида-Соломона как он описан здесь позволяет скорректировать одну ошибку в одном блоке данных. При его использовании к каждому блоку информации прибавляются дополнительные два элемента X и Y, значение которых находятся исходя из условий: для трёх единиц информации (байт): байт1 + байт2 + байт3 + X + Y = 0 байт1 + 2 * байт2 + 3 * байт3 + 4 * X + 5 * Y = 0 для рассчёта конкретных значений X и Y для кодирования трёх байт: Y = 3 * байт1 + 2 * байт2 + байт3 X = -4 * байт1 - 3 * байт2 - 2 * байт3 Теперь для выяснения ошибки и её коррекции применяем следующие рассчёты: ЗHАЧЕHИЕ_ОШИБКИ = байт1 + байт2 + байт3 + X + Y так как ранее (до возникновения ошибки) эта сумма была равна 0, то теперь она равна непосредственно значению ошибки, которое достаточно просто вычесть из недоброкачественного байта. В случае если блок принят безошибочно, то ЗHАЧЕHИЕ_ОШИБКИ = 0. Теперь найдём байт который надо исправлять: N = байт1 + 2 * байт2 + 3 * байт3 + 4 * X + 5 * Y HОМЕР_ОШИБОЧHОГО_БАЙТА = N / ЗHАЧЕHИЕ_ОШИБКИ При реализации этого в реальный алгоритм необходимо обязательно осуществлять проверку на то существует ошибка в блоке или нет, тоесть ЗHАЧЕHИЕ_ОШИБКИ = 0 или нет, иначе мы получаем смачный гимор с делением на ноль (согласитесь ведь до этого трудно не догадаться;). Если необходимо защитить кодом Рида-Соломона блок данных более 3х байт, то формулы рассчёта корректирующих значений лишь немного изменяются (для 16 байт): Y = 16 * байт1 + 15 * байт2 + 14 * байт3 + ... + байт16 X = -17 * байт1 - 16 * байт2 - 15 * байт3 - ... - 2 * байт16 ЗHАЧЕHИЕ_ОШИБКИ = байт1 + байт2 + байт3 + ... + X + Y N = байт1 + 2 * байт2 + 3 * байт3 + ... + 16 * байт16 + 17 * X + 18 * Y Теперь немного практики для восьми байт (на Васике): --------------понесло комманды васика----------------- CLS REM наш блок из 8 байт. LET a1 = 0 LET a2 = 0 LET a3 = 0 LET a4 = 0 LET a5 = 0 LET a6 = 0 LET a7 = 0 LET a8 = 0 REM Рассчитаем значения Y и X LET y = 8 * a1 + 7 * a2 + 6 * a3 + 5 * a4 + 4 * a5 + 3 * a6 + 2 * a7 + a8 LET x = -9 * a1 - 8 * a2 - 7 * a3 - 6 * a4 - 5 * a5 - 4 * a6 - 3 * a7 - 2 * a8 REM Покажем Y и X PRINT "x="; x PRINT "y="; y REM Вносим ошибку в байт a3 (ведь до этого места он был равен 0) LET a3 = 1 REM Пытаемся понять какова величина ошибки, и есть ли оно вообще? LET e = a1 + a2 + a3 + a4 + a5 + a6 + a7 + a8 + x + y IF e = 0 THEN PRINT "no error :-)": GOTO 1000 : REM если нет ошибок говорим REM Hаходим в каком байте ошибка LET i = a1 + 2 * a2 + 3 * a3 + 4 * a4 + 5 * a5 + 6 * a6 + 7 * a7 + 8 * a8 + 9 * x + 10 * y LET ind = i / e PRINT "Corrector = "; e : REM Покажем величину ошибки PRINT "Error in: a"; ind : REM Покажем в каком байте ошибка 1000 REM чисто выход из программы ввон ! --------------пронесло комманды васика---------------- Данным кодом не выгодно защищать блоки информации менее 4 байт, так как длинна контрольных параметров X и Y должна быть как минимум 4 байта - 2 байта (DW) для X и 2 байта на Y, тоесть получается что к блоку данных из 4 байт будет добавлен корректирующий блок из 4 байт, что ни в какие ворота не лезет (проще уж тогда каждый байт дублировать трижды, и иметь возможность скорректировать хоть все байты по двум совпадениям;-) Всё то хорошо, что хорошо кончает, но что делать если возникло две или более ошибок в блоке ? Как один из признаков возникновения двух ошибок можно считать получения в качестве HОМЕР_ОШИБОЧHОГО_БАЙТА дробного числа, например если в блоке из нулей встретится 2 единицы (две ошибки), в третьем и четвёртом байтах, то HОМЕР_ОШИБОЧHОГО_БАЙТА = 3.5 но если 4 единицы, соответственно в 3, 4 и 5 байтах то HОМЕР_ОШИБОЧHОГО_БАЙТА = 4, и вот попробуй это победи... Впрочем в данный текст не входит описание методов нахождения ошибок, как один из них могу предложить лишь сохранять контрольную сумму всех байт блока, и после попытки восстановления проверять онную. Я думаю что для блока из 16 байт вполне достаточно однобайтной контрольной суммы, посчитать можно например так: Summ = байт1 + байт2 + байт3 + ... + байт16 + 144 причём при суммировании переполнения игнорировать. Вообщем при всех раскладах получается увеличение длинны защищаемого блока на 5 байт, что не так уж и криво. Кстати в компакт дисках (CD-ROM) применяется код с длинной блока 10 элементов, правда там ещё кроме Рида-Соломона применен ещё и код Хемминга. Если в вас живёт желание понять другие коды восстановления ошибок, такие как коды Хемминга(применяется в пейджерах), коды Голея и другое, то рекомендую прочесть книгу: У.Питерсон, Э.Уэлдон "КОДЫ, исправляющие ошибки" перевод с английского, издательство "МИР" Москва 1976. В той книге, равно как и в другой литературе вы сможете найти более правильную информацию по кодам поиска и коррекции ошибок, здесь же я изложил материал так как понимает его мой мозг и не более чем. NOP Electronic System Corp. -------------------- Живы будем - Не помрем !
|
Текстовая версия | Сейчас: 26.9.2024, 0:06 |