THIS SECTION IS UNDER CONSTRUCTION
Коды Рида-Соломона (Reed-Solomon code, RS-code) Пусть I - информация, которую надо передать G - порождающий полином, степень полинома равна числу дополнительных символов Для исправления ошибок надо 2 дополнительных символа на одну ошибку. (т.е. для исправления 4 ошибок надо 4*2 = 8 доп символов) плюс один символ. (не стоит забывать что длинна G так же должна включать все комбинации места, где произошла ошибка). тогда C - данные которые надо передать (wire) C = I * G +-------------------------+ on wire | C | +-------------------------+ | | | +- - - - - - - - - -+- - -+ I бит G бит Пусть при передаче произошла ошибка: в результате мы получили вместо C: V = C + E, где E - вектор ошибки Вычисляем синдром: S = V mod G если S = 0, то ошибки нет если S != 0, то каждый S можно однозначно соотнести с E (конечно при условии, что E входит в класс ошибок которые мы защищаем и опять таки нужен правильный выбор многочлена). Пример: пусть полином G = X^3 + X^2 + 1 (G = 1101) степень 3 (исправляет одну ошибку, на длинне данных = 4). I данные = 1011 C = 1011 * 111 1011 * 1101 --------- 1011 0000 1011 1011 ----------- C= 1111111 Ecли все верно то: 1111111 mod 1101 1101 ------- 1011 1101 ------- 1101 1101 ------- 0
V mod G = (C mod G) + (E mod G) = 0 V mod G = E mod G = S надо брать такой G, что бы S был уникальный для всех синдромов: Считаем синдром для ошибки: 1 2 3 4 5 6 7 1000000 0100000 0010000 0001000 0000100 0000010 0000001 1101 1101 1101 1101 ------- ------- ------- ------- ------- ------- ------- 100 010 001 1010 1010 1010 101 1101 1101 1101 ------- ------- ------- 1110 1110 111 1101 1101 ------- ------- 110 011 (если код исправляет также двойные и выше ошибки - синдромов будет больше и они будут иметь вид (для двойной ошибки)): 1000001 1000010 1000100 ... ... 0100001 0100010 0100100 ... .... 0000101 0000110 0000011 Теперь попробуем для нашего сообщения 1111111. Пусть в нем возникла ошибка в бите 2 cверху: 1011111 Делим на прождающий многочлен: 1011111 1101 ------- 1101 1101 ------- 011 => смотрим таблицу синдромов - ошибка 0100000, те в бите 2. Корректируем, затем вычисляем результат.
Другой метод - Систематическое кодирование. Он более удобен так как пересылаются реальные данные. сообщение состоит из информационных битов, за ними следует ECC (т.е. как в CRC). +-------------------------+ on wire | I | ECC | +-------------------------+ | | | +- - - - - - - - - -+- - -+ I бит G бит наш полином G = X^3 + X^2 + 1 (G = 1101) те же данные = 1011 дополняем 3 нулевыми битами (т.к. порождающий полином степени 3) CRC = 1011000 mod 1101 1101 ------- 1100 1101 ------- 100 = это CRC (Реально уже ECC). Пересылаем: 1011 100 ---- --- данные CRC Проверка: 1011100 mod 1101 1101 ------- 1101 1101 ------- нет ошибки Пусть ошибка в бите 2 справа (как и в прошлый раз): 1111100 mod 1101 1101 ------- 1010 1101 ------- 1110 1101 -------- 011 => смотрим таблицу синдромов - ошибка 0100000, те в бите 2.
Все опять таки происходит на полях Галуа: Поля Галуа существуют только для числа элементов равного Простое_Число^Целая_Степень Для поля GF(2) имеем: сиволы: 0 и 1 правила: 0 + 0 = 0 0 + 1 = 1 1 + 1 = 0 0 - 0 = 0 1 - 1 = 0 1 - 0 = 1 0 - 1 = 1 0 * 1 = 0 1 * 1 = 1 0 / 1 = 0 1 / 1 = 1
Пример порождающих полиномов степень полином n k 1 11 3 2 Контроль четности 2 111 3 1 Код с повторением 3 1101 7 4 Хэмминг 1011 7 4 Xэмминг 4 11001 15 11 Хэмминг 10011 15 11 Хэмминг 10111 7 3 Файр-Абрамсон 11101 7 3 Файр-Абрамсон 5 100101 31 26 Хэмминг 101001 31 26 Хэмминг .... где n - длинна кодового слова k - длинна блока исходного сообщения мы наблюдаем сразу пары - это двойственность. Если ab...yz - порождающий многочлен, то zy...ba - тоже. Код Хэмминга - частный случай кода Рида-Соломона (но самый продвинутый). Коды Боуза-Чоудхури-Хоквенгема (Bose-Chadhuri-Hocquenghem - BCH) - обобщение кодов Хэмминга, которое позволяет исправлять множественные ошибки. n k t g(x) 7 4 1 13 15 11 1 23 7 2 721 5 3 2467 31 26 1 45 21 2 3551 16 3 107657 11 5 5423325 6 7 313365047 63 57 1 103 51 2 12471 45 3 1701317 39 4 166623567 36 5 30 6 24 7 18 10 16 11 10 13 7 15 127 120 1 211 113 2 41567 106 3 11554743 99 4 92 5 85 6 78 7 71 9 64 10 57 11 50 13 43 14 36 15 29 21 22 23 15 27 8 31 255 247 1 435 239 2 267543 231 3 223 4 215 5 207 6 199 7 191 8 187 9 179 10 171 11 163 12 155 13 147 14 139 15 131 18 123 19 115 21 107 22 99 23 91 25 87 26 79 27 71 29 63 30 55 31 47 42 45 43 37 45 29 47 21 55 13 59 9 63
Мы можем использовать MATLab для выбора порождающих полиномов pol = cycpoly(n,k) где n - длинна кодового слова k - длинна блока исходного сообщения
CIRC
В результате пакетная ошибка расслаивается на простые, которые легко устраняются:
К примеру так устроена Error correction на компакт-дисках (CD).
Коды Рида-Соломона с точки зрения математики
Cauchy Reed-Solomon code
