1 2 3 4 5 6 7 8 9

из

DC Приёмный распределитель

S T

C

S T

C

S T Выход к получателю

C

S T

C

S T

C

Рис.4.10

В приемном распределителе происходит преобразование из последовательного кода в параллельный. В сумматорах по модулю 2 производится вычисление синдрома по уравнениям проверок:

с₁= а₁ а₂ а₄ а₅ а₆

с₂= а₁ а₃ а₄ а₇

с₃= а₂ а₃ а₄ а₈

с₄= а₅ а₉

В дешифраторе производится преобразование синдрома из двоичного кода в десятичный.

Информационные разряды поступают в накопитель если синдром пулевой, т.е. ошибки нет, или она не обнаружена, то из накопителя КК простого кода выдается получателю. Если ошибка обнаружена, то исправляется подачей сигнала на соответствующий счетный вход триггера накопителя. Исправляются только информационные разряды, поскольку исправлять проверочные разряды бессмысленно – они получателю не выдаются.

4.11. Циклические коды

Наиболее простыми с точки зрения технической реализации являются именно циклические коды. Поэтому они получили наибольшее практическое применение, в тех случаях, когда требуется значительное повышение достоверности. Так во всех промышленных моделях АПД применяются только циклические коды.

Циклические коды относятся к классу линейных, систематических, групповых, разделимых кодов и обладают всеми их свойствами.

Для записи КК циклического кода используются степенные полиномы. Так n-разрядная КК записывается в виде:

F(x)=a_n-1x^n-1+a_n-2x^n-2+…+a₁x+a₀ (4.34)

Например, КК вида:

1 1 0 1 1 0 1

2⁶ 2⁵ 2⁴ 2³ 2² 2¹ 2⁰ можно записать в виде полинома х⁶+х⁵+х³+х²+1 относительно некоторой фиктивной переменной.

Над подобными полиномами можно производить все обычные операции (деление, умножение), только сложение и вычитание заменяются сложением по модулю 2.

ПРИМЕРЫ:

Сложение х³+х²+1 х⁵+х²+х

х+1 х²+1

х³+х²+х х⁵+х+1

Умножение

(х³+х²+1)(х+1)= х⁴+х³ +х+х³+х²+1= х⁴ + х² +х+1

т.к. х³+х³= х³(1 1)=0

(х⁴+х³ +х+1)х³=х⁷+х⁶+ х⁴+х³ или 11011000 ,а было 11011, т.е сдвиг на 3 разряда влево

Деление

х⁷+х⁵+ х⁴ + х²+1 х³+х²+1

х⁷+х⁶+ х⁴ х⁴+х³+1

х⁶+ х⁵+х²

х⁶+ х⁵+ х³

х³+х²+1

х³+х²+1

0 0 0

Разрешение КК циклического кода обладают двумя очень важными свойствами:

- циклический сдвиг разрешенной КК вправо или влево также приводит к разрешенной КК;

- все разрешенные КК делятся без остатка на некоторый полином Р(х), называемый образующим.

Из второго свойства вытекает следствие:

- при делении неразрешенных КК циклического кода не образующий полином обязательно получается остаток, который и является синдромом данного кода.

Т.е. в циклических кодах остаток от деления КК на образующий полином Р(х) должен указывать где произошла ошибка.

Найдем алгоритм построения циклического кода, удовлетворяющего перечисленным выше требованиям. Пусть задан некоторый образующий полином Р(х) степени r. Как мы увидим в дальнейшем он полностью определяет корректирующую способность циклического кода. Пусть задана также КК исходного простого кода Q(x)

1.Возьмем произведение Q(x)*х^r (т.е. осуществим сдвиг на r разрядов влево)

2.Разделим произведение Q(x)*х^r на образующий полином Р(х) степени r. В результате получим многочлен А(х) и остаток R(x)/P(x):

(4.33)

3. Умножим левую и правую части этого уравнения на Р(х), тогда получим:

(4.34)

4. Перепишем это равенство в виде:

(4.35)

Очевидно, что левая часть (4.35) делится без остатка на Р(х), значит без остатка делится и правая часть.

Т.о. из (4.35) вытекают 2 способа формирования КК циклического кода.

1 способ. Заметим, что в результате умножения исходной КК - Q(x) на х^r степень каждого члена, входящего в Q(x) повышается на r. При делении Q(x)* х^r на образующий полином степени r получаем частное А(х), естественно, такой же степени, что и Q(x). Поэтому А(х) можно рассматривать как некоторую исходную КК простого кода. Следовательно, алгоритм первого способа состоит в следующем:

1. Берется исходная КК простого кода - Q(x)

2. Умножается на образующий полином Р(х), степени r. Получаем КК циклического кода:

F(x)= Q(x)*P(x)

Эта комбинация делится на Р(х) без остатка и является разрешенной КК циклического кода.

Недостаток: Информационные и проверочные разряды не отделены друг от друга - трудно реализовать аппаратуру.

2 способ Используем правую часть выражения (4.35).

1. Берется исходная КК простого кода - Q(x)

2. УмножаемQ(x) на х^r (сдвигаем Q(x) на r разрядов влево)

Q(x)*х^r

3. Делим Q(x)*х^r на образующий полином Р(х) степени r и находим остаток от деления – R(x)

4. Приписываем и суммируем по модулю 2 к полиному Q(x)*х^r остаток R(x), т.е.:

F(x)= Q(x)* х^r R(x)

Эта комбинация делится без остатка на Р(х) и является разрешенной КК циклического кода. Кроме того, эта КК состоит из двух частей – информационной части Q(x)* х^r и проверочной R(x).

Последний способ и реализуется в технике ПДС.

Пример: Дана КК простого кода 1010, т.е. Q(x)=1010. Построить КК циклического кода с d₀=3

1. определяем r:

r ≥ log (n+1) k=4, тогда r=3

Требуемый код (7,4).

2. определяем образующий полином Р(х) степени r.

Обычно Р(х) выбирают из таблицы:

Р(х)= х³+х²+1 1101

1 способ Можно записать:

1.Q(x)= 1010 х³ +х

2. Умножаем Q(x)*P(x):

(х³ +х)( х³+х²+1)= х⁶+х⁴+х⁵+ х³+ х³+х= х⁶+ х⁵+ х⁴+х

F(x)= х⁶+ х⁵+ х⁴+х 1110010 - КК циклического кода

Проверим, делится ли F(x) на Р(х) без остатка:

х⁶+ х⁵+ х⁴+х

х⁶+ х⁵+ х³ х³+ х²+1

х⁴+ х³+х х³+х

х⁴+ х³+х

0 0 0 - условие выполняется

Можно выполнять эти действия и над цифровой записью:

1110010 1101

1101

1101 1010

1101 - условие выполняется

0

2 способ

1. Умножаем Q(x)*х^r , т.е. на х³ , т.к. r =3

(х³ +х)х³ = х⁶+х⁴ 1010000

2. Делим Q(x)*х^r на Р(х) и определяем остаток R(x).

х⁶+ х⁴ х³+ х²+1

х⁶+ х⁵+х³

х⁵+ х⁴+ х³ х³+ х²+1

х⁵+ х⁴+ х²

х³+ х²

х³+ х²+1

1

ОстатокR(x)=1 001

3.Формируем КК циклического кода, т.е.

Q(x)*х^r R(x) или

х⁶+ х⁴+1 1010001

Проверим, делится лиF(x) на Р(х) без остатка:

х⁶+ х⁴+1 х³+ х²+1

х⁶+ х⁵+х³

х⁵+ х⁴+ х³+1 х³+ х²+1

х⁵+ х⁴+ х²

х³+ х²+1

х³+ х²+1

0 - условие выполняется