Участник:Nikz — различия между версиями
NikZ (обсуждение | вклад) |
NikZ (обсуждение | вклад) |
||
| Строка 125: | Строка 125: | ||
Кодирование Рида-Соломона будем производить систематическим кодом, это означает, что в закодированное сообщение будет содержать в себе в явном виде исходное сообщение. Каким образом это делается: | Кодирование Рида-Соломона будем производить систематическим кодом, это означает, что в закодированное сообщение будет содержать в себе в явном виде исходное сообщение. Каким образом это делается: | ||
Сначала полином сдвигается на <math>N-K</math> коэффициентов влево <br /> | Сначала полином сдвигается на <math>N-K</math> коэффициентов влево <br /> | ||
| − | <math> | + | <math>p'(x)=p(x)x^{N-K}</math> ,а потом вычисляется остаток от деления на порождающий полином и прибавляется к <math>p'(x)</math>: <math>C(x)=p'(x)+p'(x)mod g(x)</math>. <br /> |
| − | ,а потом вычисляется остаток от деления на порождающий полином и прибавляется к | + | Для систематического кого очевидно, что <math>K</math> старших коэффициентов полученного кода <math>C(x)</math> содержат исходное сообщение. Это удобно при декодировании. |
| + | Закодированное сообщение <math>C(x)</math> обладает очень важным свойством: оно без остатка делится на порождающий многочлен <math>g(x)</math>.<br /> | ||
| + | '''Докажем это свойство:''' <br /> | ||
| + | Пусь <math>r(x)</math>-остаток от деления <math>p'(x)</math> на <math>g(x)</math>.<br /> | ||
| + | Тогда,<br /> | ||
| + | <math>p'(x)=g(x)u(x)+r(x)</math> <br /> | ||
| + | Итак,<br /> | ||
| + | <math>r(x)=p'(x)mod g(x)</math><br /> | ||
| + | Тогда<br /> | ||
| + | <math>C(x)=p'(x)+p'(x)mod g(x)=g(x)u(x)+r(x)+r(x)</math><br /> | ||
| + | Вспомним, что в арифметике поля Галуа сложения являются одновременно и вычитанием, тогда <math>r(x)+r(x)=0</math>!Следовательно <math>C(x)</math> делится на <math>g(x)</math> без остатка.<br /> | ||
| + | Таким образом, <br /> | ||
| + | <math>C(x) mod g(x)=0</math><br /> | ||
| + | В случае, если закодированное сообщение будет изменено, то это равенство будет нарушенным, не считая случая, когда ошибка окажется кратной <math>g(x)</math>. Факт искажения можно рассматривать как прибавление к <math>C(x)</math> некоторого полинома ошибки <math>E(x)</math>.<br /> | ||
| + | '''Пример:''' | ||
| + | <br /> | ||
| + | == Декодирование Рида-Соломона == | ||
Версия 14:19, 15 июня 2014
Содержание
Пример коррекции ошибки с помощью кодов Рида - Соломона
Постановка задачи
В данной статье разбирается пример работы алгоритма коррекции ошибки для 16-битных строк. Строка разбивает на блоки длиной 4 бита и каждый блок представляет собой элемент поля Галуа GF16. Необходимо отследить и исправить одиночную ошибку, внесённую в один из блоков.
Теоретические основы алгоритма
Поля Галуа
Операцию сложения определим как "исключающее ИЛИ" 
.Очевидно, что в таком случае операция сложения является обратной самой себе. Тогда операция умножения в двоичном виде будет выглядеть так:
Так можно умножать полиномы, в данном случае мы умножили:
.
Определим также операцию деления чисел(или полиномов) с остатком – по аналогичным правилам, например:
или 
Теперь построим поле из 16 элементов 
. Операцию сложения определена на XOR, Операция деления дополнена получением остатка по некоторому модулю.
Выберем в качестве модуля неприводимый полином 
.
Возьмем единицу и будем последовательно умножать ее на 2 и рассмотрим числа, которые будут при этом
и так далее.
Составим таблицу умножения
| Степень | Результат | |
|---|---|---|
| 0 | 1 | 0001 |
| 1 | 2 | 0010 |
| 2 | 4 | 0100 |
| 3 | 8 | 1000 |
| 4 | 3 | 0011 |
| 5 | 6 | 0110 |
| 6 | 12 | 1100 |
| 7 | 11 | 1011 |
| 8 | 5 | 0101 |
| 9 | 10 | 1010 |
| 10 | 7 | 0111 |
| 11 | 14 | 1110 |
| 12 | 15 | 1111 |
| 13 | 13 | 1101 |
| 14 | 9 | 1001 |
| 15 | 1 | 0001 |
Таким образом, при дальнейшем умножении весь цикл повторится снова. Полученные степени двойки не сложно умножать между собой, например: 
. Можно проверить результат,разделив 
.
Таким образом, получили поле , то есть для двоичных 4-разрядных чисел.
Коды Рида - Соломона
При построении кода Рида-Соломона задается пара чисел N,K, где N-Общее количество символов, а К- «полезное» количество символов, N-K символов задают избыточный код, предназначенный для восстановления ошибок.
Такой код Рида-Соломона будет иметь «расстояние Хемминга» 
.
В соответствии с теорией кодирования, код, имеющий расстояние Хемминга 
, позволяет восстанавливать t ошибок. Таким образом, если нам необходимо восстановить t ошибок, то общее количество символов сообщения 
.
Сообщения при кодировании Рида-Соломона представляются полиномами.
Исходное сообщение представляется как коэффициенты полинома 
степени 
, имеющего 
коэффициентов.
Порождающий многочлен Рида-Соломона,
, строится следующий образом:
, 
примитивный член поля. Нетрудно понять, что 
- корни этого многочлена.
Например, построим порождающий многочлен кода Рида-Соломона с 
, способного исправлять до 3 ошибок 
:
. (Возведение в степень и умножения выполнены над полем GF16 )!
Кодирование Рида-Соломона
Кодирование Рида-Соломона будем производить систематическим кодом, это означает, что в закодированное сообщение будет содержать в себе в явном виде исходное сообщение. Каким образом это делается:
Сначала полином сдвигается на 
коэффициентов влево
,а потом вычисляется остаток от деления на порождающий полином и прибавляется к 
: 
.
Для систематического кого очевидно, что старших коэффициентов полученного кода 
содержат исходное сообщение. Это удобно при декодировании.
Закодированное сообщение обладает очень важным свойством: оно без остатка делится на порождающий многочлен .
Докажем это свойство:
Пусь 
-остаток от деления на .
Тогда,
Итак,
Тогда
Вспомним, что в арифметике поля Галуа сложения являются одновременно и вычитанием, тогда 
!Следовательно делится на без остатка.
Таким образом,
В случае, если закодированное сообщение будет изменено, то это равенство будет нарушенным, не считая случая, когда ошибка окажется кратной . Факт искажения можно рассматривать как прибавление к некоторого полинома ошибки 
.
Пример:
