8.7. Коды Рида-Соломона 89
Доказательство. Поскольку порождающий многочлен кода Рида-Соломона дли-
ны q − 1 имеет вид (8.3) для некоторых b ≥ 0, δ > 1, код Рида-Соломона — это
БЧХ-код с конструктивным расстоянием δ длины n = q −1, q 6= 2. Размерность этого
циклического кода равна k = n − deg g(x) = n −δ + 1. Согласно границе Синглтона
(см. теорему 4 разд. 1.2.), если B — (n, k, d)-код, то n − k ≥ d − 1. Иными словами,
d ≤ n −k + 1. Отсюда для кода Рида-Соломона имеем d = n −k + 1, а следовательно,
этот код является MDS-кодом. N
Достоинства кодов Рида-Соломона:
1. Коды Рида-Соломона удобно использовать, когда требуется код, длина которо-
го меньше, чем размер поля, так как, являясь MDS-кодами, они имеют наибольшее
возможное минимальное расстояние.
2. Они используются для получения двоичных кодов с очень большими мини-
мальными расстояниями.
3. Коды Рида-Соломона используются при построении каскадных кодов с хоро-
шими параметрами.
4. Они используются при построении кодов, исправляющих пакеты ошибок
(см. подробнее разд. 8.7.2.).
Пример 8. Рассмотрим код Рида-Соломона над GF (5) длины 4 с конструктив-
ным расстоянием 3. В качестве примитивного элемента поля GF(5) возьмем, на-
пример, α = 2, тогда g(x) = (x − α)(x − α
2
) = (x − 2)(x − 4) = x
2
+ 4x + 3. Код
Рида-Соломона имеет 5
2
= 25 кодовых слов длины 4, среди них например,
(3410), (2140), (0341), (3201) . . . .
Упражнение 43. Найти все 25 кодовых слов этого кода.
Добавление к коду общей проверки на четность не всегда увеличивает его мини-
мальное расстояние, если коды недвоичные и есть слова нечетного веса. Например,
добавление общей проверки на четность к коду над GF (3) с кодовой матрицей
µ
1 1 1 0 0
0 0 1 1 1
¶
не увеличивает кодовое расстояние. Однако для кодов Рида-Соломона с порождаю-
щим многочленом g(x) = (x −α) ·(x −α
2
) ·. . . ·(x − α
δ−1
) кодовое расстояние всегда
увеличивается на 1.
Теорема 50. Пусть P — [n = p
m
− 1, k, d]-код Рида-Соломона с порождающим
многочленом
g(x) = (x − α) · (x − α
2
) · . . . · (x − α
δ−1
).
Тогда расширение каждого кодового слова c = (c
0
, c
1
, . . . , c
n−1
) посредством добавле-
ния общей проверки на четность над GF (p)
c
n
= −
n−1
X
i=0
c
i
приводит к коду с параметрами [n + 1, k, d + 1].