Автор работы: Пользователь скрыл имя, 20 Февраля 2012 в 12:05, доклад
Коды Рида — Соломона — недвоичные циклические коды, позволяющие исправлять ошибки в блоках данных. Элементами кодового вектора являются не биты, а группы битов (блоки). Очень распространены коды Рида — Соломона, работающие с байтами (октетами).
Код Рида — Соломона является частным случаем БЧХ-кода.
Шмаргунов 492. ИДЗ.
Код Рида-Соломона.
Коды Рида — Соломона — недвоичные циклические коды, позволяющие исправлять ошибки в блоках данных. Элементами кодового вектора являются не биты, а группы битов (блоки). Очень распространены коды Рида — Соломона, работающие с байтами (октетами).
Код Рида — Соломона является частным случаем БЧХ-кода.
В настоящее время
широко используется в системах восстановления
данных с компакт-дисков, при создании архивов с информацией
для восстановления в случае повреждений,
в помехоустойчивом кодировании.
Коды Рида — Соломона
являются важным частным случаем БЧХ-кода, корн
где l0 — некоторое целое число (в том числе 0 и 1), с помощью которого иногда удается упростить кодер. Обычно полагается l0 = 1. Степень многочлена равна d − 1.
Длина полученного кода n, минимальное расстояние d (минимальное расстояние d линейного кода является минимальным из всех расстояний Хемминга всех пар кодовых слов, см.Линейный код). Код содержит r = d − 1 = deg(g(x)) проверочных символов, где deg() обозначает степень полинома; число информационных символов k = n − r = n − d + 1. Таким образом и код Рида — Соломона является разделимым кодом с максимальным расстоянием (является оптимальным в смысле границы Синглтона).
Кодовый полином c(x) может быть получен из информационного полинома m(x), , путем перемножения m(x) и g(x):
c(x) = m(x)g(x).
Код Рида — Соломона над , исправляющий t ошибок, требует 2t проверочных символов и с его помощью исправляются произвольные пакеты ошибок длиной t и меньше. Согласно теореме о границе Рейгера, коды Рида — Соломона являются оптимальными с точки зрения соотношения длины пакета и возможности исправления ошибок — используя 2tдополнительных проверочных символов исправляется t ошибок (и менее).
Теорема (граница Рейгера). Каждый линейный блоковый код, исправляющий все пакеты длиной t и менее, должен содержать, по меньшей мере, 2t проверочных символов.
Код, двойственный коду Рида — Соломона, есть также код Рида-Соломона. Двойственным кодом для циклического кода называется код, порожденный его проверочным многочленом.
Матрица порождает код Рида — Соломона тогда и только тогда когда любой минор матрицы Pk * (n − k) отличен от нуля.
При выкалывании или
Примеры.
16-ричный (15,11) код Рида — Соломона
Пусть t = 2,l0 = 1. Тогда
g(x) = (x − α)(x − α2)(x − α3)(x − α4) = x4 + α13x3 + α6x2 + α3x + α10
.
Степень g(x) равна 4, n − k = 4 и k = 11. Каждому элементу поля GF(16) можно сопоставить 4 бита. Информационный многочлен является последовательностью 11 символов из GF(16), что эквивалентно 44 битам, а все кодовое слово является набором из 60 бит.
8-ричный (7,3) код Рида — Соломона
Пусть t = 2,l0 = 4. Тогда
g(x) = (x − α4)(x − α5)(x − α6)(x − α0) = x4 + α6x3 + α6x2 + α3x + α
.
Пусть информационный многочлен имеет вид
m(x) = α4x2 + x + α3
.
Кодовое слово несистематического кода запишется в виде
c(x) = m(x)g(x) = (α4x2 + x + α3)(x4 + α6x3 + α6x2 + α3x + α) = α4x6 + αx5 + α6x4 + 0x3 + 0x2 + α5x + α4
что представляет собой
последовательность семи восьмеричных
символов.