Систематический вид циклического кода.

На практике иногда требуется закодировать в БЧХ- коде одну или несколько информационных посылок, для этого поступаем следующим образом:

 

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 бит.