IPB

Здравствуйте, гость ( Вход | Регистрация )

 
Ответить в эту темуОткрыть новую тему
> Описание кода Рида-Соломона
SuperMax
сообщение 6.7.2014, 0:55
Сообщение #1


Администратор
*****

Группа: Root Admin
Сообщений: 5 863
Регистрация: 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
PRINT

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.


--------------------
Живы будем - Не помрем !
Пользователь в офлайнеКарточка пользователяОтправить личное сообщение
Вернуться в начало страницы
+Ответить с цитированием данного сообщения

Ответить в эту темуОткрыть новую тему
1 чел. читают эту тему (гостей: 1, скрытых пользователей: 0)
Пользователей: 0

 



Текстовая версия Сейчас: 20.11.2019, 8:11