8.8. Коды Юстесена 91
Построим из кода Рида-Соломона двоичный код с большим кодовым расстояни-
ем. Пусть вектор c = (c
0
, . . . , c
n−1
) принадлежит [n, k, d]-коду Рида-Соломона над
GF (2
m
). Заменим элементы c
i
соответствующими двоичными m-векторами и к каж-
дому такому m-вектору добавим общую проверку на четность. Получим двоичный
код с параметрами
[n
0
= (m + 1)(2
m
− 1), k
0
= mk, d
0
≥ 2d = 2(2
m
− k)].
Аналогичное преобразование можно применить к расширенному коду Рида-Соломона,
что приводит к двоичному коду с параметрами
[(m + 1)2
m
, mk, d
0
≥ 2(2
m
− k + 1)].
Полученный код является каскадным кодом.
Каскадные коды имеют широкое применение на практике, например, использу-
ются при записи информации на компакт дисках. Повреждения в компакт дисках
могут вызвать длинные последовательности ошибок. Ошибки в цифровой записи и
воспроизведении бывают двух типов:
1) случайные (в несколько бит, обычно разбросаны по диску, их можно легко ис-
править);
2) ошибки типа "потеря пакета".
Определение. Пакетом длины s называется вектор, все ненулевые элементы
которого расположены среди s подряд идущих компонент, из которых первая и по-
следняя являются ненулевыми.
Иначе говоря, ошибка составляет большое число последовательно расположенных
бит. Например, в компакт дисках такая ошибка может быть вызвана физическим по-
вреждением диска или крупным дефектом ленты. Эффект, вызванный таким дефек-
том, может быть существенно уменьшен, если биты, составляющие посылку, распо-
лагать не последовательно, а дискретно через некоторые интервалы (кадры). Тогда
потерю сравнительно большого пакета ошибок можно рассматривать как случайную.
Такой метод передачи данных использует код Рида-Соломона, а точнее двоичный
код, полученный из кода Рида-Соломона. Иногда рассматриваются более сложные
преобразования кода Рида-Соломона в двоичный с помощью процедуры перемеже-
ния, с применением двух кодеров, например, при использовании функции четности
для любого двоичного набора длины m либо каскадирования. Однако двоичный код,
полученный из кода Рида-Соломона, все же довольно плохо исправляет случайные
ошибки. В этом случае может быть использован код Юстесена.
8.8. Коды Юстесена
Рассмотрим код Рида-Соломона над полем GF (2
m
) с параметрами
[n = 2
m
− 1, k, d = n − k + 1]
2
m
.