Систематический вид циклического кода.
На практике иногда требуется закодировать в БЧХ- коде одну или несколько информационных посылок, для этого поступаем следующим образом:
1) выбираем образующий полином (методика выбора образующего полинома описана выше);
2) информационную комбинацию умножаем на одночлен той же степени, что и образующий полином;
3) делим полученную комбинацию на образующий полином;
4) суммируем остаток от деления с информационной комбинацией, умноженной на одночлен той же степени, что и образующий полином.
Например: информационную комбинацию вида 1001101 закодировать в БЧХ -коде, так чтобы код был способен исправлять ошибки кратности 2.
1. информационное слово семиразрядное и корректирующие способности кода равны 2, следовательно для этого случая подходит полином, выбранный в предыдущем примере.
2. Умножаем 1001101 на Х8 (100000000), имеем 1001101*100000000=100110100000000
3.Делим 100110100000000 на 111010001, в результате деления по модулю два получаем остаток равный 11000010
4. Суммируем
100110100000000
+ 11000010
100110111000010-искомая комбинация.
Причем старшие 7 разрядов информационные, а оставшиеся 8 - контрольные.
Таблица.Разложение бинома хn+1 на неприводимые сомножители
Степень бинома | Последовательности степеней корней неприводимых сомножителей | Неприводимые сомножители |
1 2 4 3 6 5 | 13 15 | |
01 02 04 08 03 06 12 09 05 10 07 14 13 11 | 023 037 007 031 | |
01 02 04 08 16 03 06 12 24 17 05 10 20 09 18 07 14 28 25 19 11 22 13 26 21 15 30 29 27 23 | 045 075 067 057 073 051 | |
01 02 04 08 16 32 03 06 12 24 48 33 05 10 20 40 17 34 07 14 28 56 49 35 09 18 36 11 22 44 25 50 37 13 26 52 41 19 38 15 30 60 57 51 39 21 42 23 46 29 58 53 43 27 54 45 31 62 61 59 55 47 | 103 127 147 111 015 155 133 165 007 163 013 141 |
9.4 Коды Рида–Соломона и их применение.
Широко используемым подмножеством кодов БЧХ являются коды Рида-Соломона, которые позволяют исправлять пакеты ошибок. Пакет ошибок длины b представляет собой последовательность из таких b ошибочных символов, что первый и последний из них отличны от нуля. Существуют классы кодов Рида-Соломона, позволяющие исправлять многократные пакеты ошибок.
Коды Рида-Соломона (РС) в качестве двоичных элементов (1 или 0) ) используют двоичные векторы V длиной 8 бит(байт) или иногда 4 бита (полубайт). Коды РС, таким образом, это не двоичные, а 8ми- ричные коды БЧХ длины N=2m-1 .
Они являются циклическими кодами с образующим полиномом
G(x)=M1(х)*M2(x)* …*Mi(X),
где полином G(X) перед степенями Xi имеет множитель в виде двоичного вектора длиной в 8 бит.
Выбор длины кода N=2m-1 гарантирует, что полином G(X) является делителем XN-1 , и следовательно, всегда будет выполнено требование к образующему полиному циклического кода.
Слово кода Рида-Соломона имеет вид:
A1A2… AkB1B2…BN-k ,
где Ai и Bj– соответственно информационные и избыточные символы, которые могут быть представлены m- разрядными двоичными векторами. Число информационных символов – K=(N-ст.G(x)) , где ст.G(x) степень образующего полинома G(x).
Коды РС являются систематическими кодами с максимальным кодовым расстоянием .
d=N-K+1.
Коды РС являются линейными кодами, поэтому, кроме задания с помощью образующего полинома G(X), они могут быть заданы также образующей ||ОМ|| матрицей.
Пример 8-ричного (7,3) кода Рида - Соломона
Образующий полином в поле Галуа GF(23)
g(x) = x4 + α6x3 + α6x2 + α3x + α,
где α -первообразный элемент поля Галуа GF(23). Это восьмеричное или 3-х значное двоичное число, такое, что αi пробегают все значения элементов поля GF(23).
Пусть исходное кодовое слово, состоящее из восьмеричных чисел имеет вид
ИС = α4 , α0 , α3.
Образующий полином, взят из таблички первообразных полиномов имеет вид
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 =(α4, α, α6, 0, 0, α5, α4 )
что представляет собой последовательность семи восьмеричных символов
Применение кодов Рида–Соломона
Сразу после появления (60-ые годы 20ого века) коды Рида - Соломона стали применяться в качестве внешних кодов спутниковой связи. В настоящий момент коды Рида — Соломона имеют очень широкую область применения благодаря их способности находить и исправлять многократные пакеты ошибок.
Запись и хранение информации
Код Рида — Соломона используется при записи и чтении в контроллерах оперативной памяти, при архивировании данных, записи информации на магнитные жесткие диски . Даже если поврежден значительный объем информации, испорчено несколько секторов дискового носителя, то коды Рида — Соломона позволяют восстановить большую часть потерянной информации.
Коды Рида-Соломона широко используются в устройствах цифровой записи звука, в том числе на компакт-диски. Данные, состоящие из отсчетов объединяются в кадр, представляющий кодовое слово. Кадры разбиваются на блоки по 8 бит. Часть блоков являются контрольными.
Обычно 1 кадр (кодовое слово) = 32 блока *8(биты данных +сигнальные биты + контрольных биты)= 256 бит.
Сигнальные символы это вспомогательные данные, облегчающие декодирование: служебные сигналы, сигналы синхронизации и т. д.
При передаче данных производится перемежение (изменение порядка следования по длине носителя и во времени) блоков с различным сдвигом во времени, в результате чего расчленяются сдвоенные ошибки, что облегчает их локализацию и коррекцию. При этом используются коды Рида-Соломона с неприводимым кодовым расстоянием d0 = 5. Это означает, что они способны исправить две байтовые ошибки в каждом кодовом слове кадра в 256 бит.