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

поэлементно:

1 1 2 3

r i i i = ⊕ ⊕ ,

1 1 3 4

r i i i = ⊕ ⊕ ,

2 2 3 4

r i i i = ⊕ ⊕ ,

2 1 2 3

r i i i = ⊕ ⊕ ,

3 1 2 4

r i i i = ⊕ ⊕ ,

3 2 3 4

r i i i = ⊕ ⊕ .

(1.35)Обратим внимание на то, что алгоритм (1.35) просто получается из рассмотрения

порождающих коды Хемминга матриц (1.33), в которых проверочные подматрицы,

содержащие 3 столбца (r1, r2, r3), имеют символы «1» в тех строках, номера которых

совпадают с маркировкой информационных символов i в равенствах (1.35) [см. (1.28)].

При матричном варианте обработки принятых кодов на стороне получателя

сообщений для получения синдрома

→

S необходимо принятую, возможно искаженную в

канале, кодовую комбинацию ( )

'

Bi X умножить на проверочную матрицу Н(Х):

'

( ) ( ).

i

S B X H X =

ur uur

(1.36)

1.5.5. СТРУКТУРНЫЙ СОСТАВ ЛИНЕЙНЫХ ПЕРЕКЛЮЧАТЕЛЬНЫХ СХЕМ

Цикличность перестановок при формировании разрешенных кодовых комбинаций

ЦК лежит в основе техники построения кодирующих устройств (КУ) и декодирующих

устройств (ДУ) циклических кодов. Эта техника применяет сдвигающие регистры (СР) в виде

триггерных цепочек с теми или иными обратными связями. Такие СР называют также

многотактными Линейными Переключательными Схемами (ЛПС) и линейными кодовыми

фильтрами Хафмена, который первым начал изучение ЛПС с точки зрения линейных

фильтров. Кстати, Д. Хафмен является и автором принципа, состоящего в том, что «две

точки зрения лучше, чем одна», получившего широкое применение в настоящее ком-

промиссное время.

При построении ЛПС используется три вида элементарных устройств:

Линейными переключательными схемами с конечным числом состояний называются

любые схемы, содержащие конечное число сумматоров, устройств памяти и устройств

умножения на константу, соединенных любым допустимым способом.

В бинарном случае сумматор (равно как и вычитатель) представляет собой

логический элемент «исключающее ИЛИ», а устройство памяти является устройством

⊕

Cумматор имеет, как правило, два входа и один выход,

причем для двоичных кодов суммирование

осуществляется «по модулю 2»

Запоминающее Устройство имеет один вход и один выход

и представляет собой одну триггерную ячейку (один

разряд) СР

Устройство умножения на постоянную величину, имеет

один вход и один выход.

g задержки (D-триггером). Устройства задержки, включенные последовательно, составляют

сдвигающий регистр (СР), в ячейках которого выходной символ совпадает с входным

символом в предшествующий момент времени. К СР подводится шина сдвига, с помощью

которой тактовыми импульсами (ТИ) осуществляется продвижение по разрядам СР

записанной кодовой информации. Как правило, шина сдвига не показывается на схемах с

изображениями ЛПС.

При формировании и обработке двоичных ЦК введение в схему ЛПС умножителя на

константу, равную 1, эквивалентно введению дополнительного соединения, а умножитель

на константу, равную 0, соответствует отсутствию такого соединения.

Предполагается, что на вход СР, входящего в состав ЛПС, кодовая комбинация

подается последовательно, с периодичностью, равной периоду следования ТИ в шине

сдвига. Аналогично, последовательно во времени, появляются кодовые символы на выходе

СР. Когда входом или выходом является многочлен, представляющий при двоичной

обработке набор «1» и «0», то на входном или выходном конце СР появляются только

коэффициенты («1» или «0»), начиная с коэффициентов высших порядков. Это

обусловливается тем, что при делении у делителя сначала должны быть обработаны

коэффициенты высших порядков.

1.5.6. УМНОЖЕНИЕ ПОЛИНОМОВ НА БАЗЕ ЛПС

Схема, изображенная на рис. 1.5, используется для умножения любого полинома на

входе A(X) = a0 + a1 X + a2 X

2

+ … + ak X

k

на фиксированный полином, в частности,

порождающий: G(X) = g0 + g1 X + g2 X2 + … + gm X

m

.

Предполагается, что первоначально все разряды СР содержат нули, а на вход

коэффициенты полинома А(Х) поступают, начиная с коэффициентов высших порядков (со

старших разрядов), после чего следует m нулей.

OUT

gr

gr-1 gr-2 gr-3 g1 g0

. . .

. . .

IN

Рис. 1.5. Первый вариант схемы умножителя полиномов Произведение полиномов

A(X)G(X) = a0 g0 + (ao g1 + a1 g0)X + ... + akgmX

k+m

. (1.37)

Когда на входе ЛПС появляется первый (старший) коэффициент полинома А(Х), то он

умножится в первом устройстве умножения на gr

и появится на выходе уже как результат

перемножения akgr

, проследовав «транзитом» через все схемы суммирования «по модулю

2». Кроме того, ak запишется в первом разряде СР, а все остальные разряды СР будут

содержать нули. Спустя единицу времени, с появлением в шине сдвига 2-го ТИ, на входе

появится ak-1, который перемножается с gm и сложится в первой схеме суммирования «по

модулю 2» с akgr–1, сформировав на выходе сумму ak–1gr

+ akgr-1, т. е. второй коэффициент

произведения A(X)G(X). Дальнейшие операции производятся аналогичным образом. После

m + k сдвигов СР полностью обнуляется и на выходе появляется значение a0g0, равное

первому коэффициенту произведения (1.43), так что произведение на выходе ЛПС

последовательно получается в полном составе. Второй вариант ЛПС для умножения

полиномов показан на рис. 1.6.

Коэффициенты произведения формируются непосредственно в СР. После того, как

первый символ подается на вход, на выходе появляется последний коэффициент (1.37)

ak gm

, а разряды СР содержат только нули. После одного сдвига ячейки СР содержат

элементы ak g0, ak g1, ..., ak gm-1, a вход равен ak-1. При этом выход СР равен ak gm-1 + ak-1 gm, т. е.

равен второму коэффициенту (1.37). После появления очередного ТИ в шине сдвига (не

показана на рис. 1.5 и 1.6) на выходе появляется третий коэффициент (1.37). Дальнейшие

операции производятся аналогичным образом.

Схемы умножения могут иметь более чем один вход, если добавить к ЛПС,

изображенной на рис. 1.7, вторую шину с цепочкой устройств умножения, связанных с

соответствующими схемами суммирования «по модулю 2». Тогда схема будет

реализовывать процедуру суммирования произведений двух пар полиномов

C(X) = A1(X) G1(X) + A2(X)G2(X) , (1.38)

причем ЗУ в виде СР – только одно.

1.5.7. ДЕЛЕНИЕ ПОЛИНОМОВ НА БАЗЕ ЛПС

OUT

g0 g1 g2 gr-2 gr-1 gr

IN

…

…

Рис. 1.6. Второй вариант схемы умножителя полиномов Схема для деления полинома A(X) = a0 + a1 X + a2 X

2

+ … + ak X

k

на полином G(X) = g0 +

g1 X + g2 X

2

+ … + gm X

m

показана на рис. 1.8. Динамическое ЗУ в виде СР вначале должно

содержать все нули. Для деления полиномов СР охвачен обратной связью, т. е. выход СР

соединяется с входом. Для подчеркивания противоположного направления шины обратной

связи коэффициент умножителя обозначается как gm–1. Однако для двоичных кодов

результат умножения и деления на единицу одинаков, поэтому указанное обозначение в

дальнейшем использоваться не будет. Первый вариант ЛПС для деления полиномов (рис.

1.7).

Для первых m-сдвигов, т. е. до тех пор, пока первый входной символ не достигнет

конца PC, выход принимает значения, равные «0». После этого на выходе появляется

первый ненулевой выход, который равен akgm–1 – первому коэффициенту частного. Для

каждого коэффициента частного gj

необходимо вычесть из делимого полином G(X). Это

вычитание производится с помощью обратной связи. После k сдвигов на выходе появится

частное от деления, а остаток от деления будет находиться в СР.

Работу схемы легче всего понять с помощью примеров построения КУ и ДКУ на базе

ЛПС, рассматриваемых далее в разд. 1.5.8. Второй вариант ЛПС с делением на

генераторный полином (рис. 1.8).

При построении КУ ЦК, а также генераторов различных кодовых

последовательностей, в частности, последовательностей максимальной длины (М-

последовательностей), применяется в ряде случаев так называемый генераторный

полином Н(Х). Этот полином называют также проверочным, если он получается при

делении бинома 1

n

+ X на порождающий полином G(X):

1

( ) .

( )

n

X

H X

G X

+

= (1.39)

-g0 -g1 -g2

-gr-2 -gr-1 gr

-1

IN

…

OUT

…

Рис. 1.7. Первый вариант схемы делителя на генераторный полином При использовании этой схемы в качестве КУ ЦК, исходную кодовую комбинацию

А(Х) параллельно и одновременно записывают в k разрядов СР. С первым тактом на выход

будет выдан коэффициент bn – 1 = ak – 1, произойдет сдвиг вправо в СР, и в освободившуюся

ячейку памяти будет записано вычисленное значение проверочного бита mn – k – 1 = h0 ak – 1 +

h1 ak – 2 + ... + hk – 1 a0. Со вторым тактом на выход будет считан коэффициент bn – 2 = ak – 2,

произойдет сдвиг, и в освободившуюся первую ячейку СР запишется второй проверочный

бит mn – k – 2 = h0 ak – 2 + h1 ak – 3 + ... + hk – 1 mn –k – 1. Чеpез n – k тактов будут вычислены все n – k

проверочных символов r0, r1, …, mn – k – 1 и записаны в СР. После k тактов, т. е. после вывода

на выход всех информационных символов, станут выводиться проверочные символы в том

же порядке, в каком они вычислялись. На выходе получается блочный код. После k тактов

процесс кодирования одной комбинации Аi(Х) заканчивается, и СР принимает исходное

состояние. Для кодирования следующей комбинации необходимо стереть Аi(Х), ввести в СР

новую Аj(Х) и повторить цикл из n тактов.

Рассмотрим более конкретно работу этой схемы на примере использования ее в

качестве КУ с привязкой начальных условий к данным предыдущих примеров.

Пример

Построить схему КУ, обеспечивающего кодирование ЦК Хемминга (7,4) с

порождающим полиномом G(X) = 1 + X + Х

2

путем вычисления блока проверочных символов

«в целом», используя проверочный полином Н(Х). Проследить по тактам процесс

кодирования и состояние элементов схемы при кодировании исходной комбинации 1001 ~

1 + X

3

= A(X). Построение схемы КУ определяется проверочным полиномом (1.39)

7

2 4

3

1

( ) 1 .

1

X

H X X X X

X X

+

= = + + +

+ +

Ai(X)

OUT

hk-1 hk-2 hk-3 h1 h0

. . .

. . .

a0 a1 a2 ak-2 ak-1

Bi(X)

Рис. 1.8. Второй вариант схемы делителя на генераторный полином Так как k = 4, то число разрядов СР равно четырем. По виду проверочного полинома

определяем, что h0 = h1 = h2 = h4 = 1, h3 = 0.

Схема КУ для условий примера показана на рис. 1.9. Состояние ячеек СР и выхода

схемы по тактам – в табл. 1.6. В исходном положении в триггерные ячейки СР записываются

информационные символы Ai(X) = 1 + X

3

~ 1001. Учитывая наличие обратной связи в СР с

выхода на вход, суммирование «по модулю 2» выходов ячеек Х

1

, Х

2

и X

3

даст символ записи

в ячейку Х

0

. После первого сдвига в Х

0

будет записан символ проверочной группы r1,

который при последующих сдвигах продефилирует на выход СР. Из табл.1.6 видно, что

после n = 7 тактов на выходе образуется комбинация 0111001 (старшим разрядом вперед).

При этом триггерные ячейки СР принимают исходное значение 1001, и при

необходимости возможно повторение процедуры кодирования этой же кодовой

комбинации Ai(X) путем подачи очередных следующих n = 7 тактов. Таким образом, этот

способ кодирования так же, как и первый вариант схемы для деления полиномов,

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

Рассмотрение вариантов построения ЛПС, выполняющих операции умножения и

деления полиномов, с целью использования в кодеках ЦК, позволяет сделать следующие

выводы:

1) В КУ ЦК процедура умножения полиномов приводит к получению неразделимых

кодов, что усложняет их последующее декодирование. Поэтому операция

умножения редко используется в устройствах формирования и обработки ЦК.

2) При делении на порождающий полином G(X) код на выходе КУ получается

разделимым и СР содержит r разрядов. Так как в большинстве случаев

используются ЦК, у которых число проверочных символов r существенно меньше

числа информационных (m < k), то СР в этом случае будет иметь меньшее число

разрядов, чем при делении на генераторный полином.

Таблица 1.6. Состояния КУ

Номер

такта

Состояния ячеек Выход

X

0

X

1

X

2

X

3

A(X) 1 0 0 1 −

1 1 1 0 0 1

2 1 1 1 0 0

3 0 1 1 1 0

4 1 0 1 1 1

5 0 1 0 1 1

6 0 0 1 0 1

7 1 0 0 1 0

OUT

X

0

X

1

X

2

X

3

h4=1 h3=0 h2=1 h1=1 h0=1

a0=1 a1=0 a2=0 a3=1

Bi(X)

Ai(X) 3) При делении в КУ исходной кодовой комбинации на генераторный многочлен ЦК

также получается разделимым, но в СР требуется использовать не m, а k разрядов,

которых, как правило, больше.

1.5.8. КОДИРУЮЩЕЕ И ДЕКОДИРУЮЩЕЕ УСТРОЙСТВО ДЛЯ КОДА ХЕММИНГА (7, 4)

Покажем, как реализуются схемы с учетом того, что коды Хемминга относятся и к

классу ЦК.

Кодер для кода Хемминга (7,4). Для построения КУ по классической схеме деления (см.

рис. 1.7), так как кодирование путем вычисления остатка «в целом» требует

предварительного выполнения операции умножения на оператор сдвига

m

X и сложения

полинома – остатка с полиномом – произведением ( )

m

A X X i

(1.29), требуется

предварительно видоизменить структуру схемы. Для выполнения операции умножения

следует разместить сумматор, на который подключен вход, в конце СР, перед обратной

связью

m 1

g

−

. Такое подключение входа эквивалентно умножению на

m

X , так как

исключается задержка на m ТИ.

Для выполнения операции сложения остатка Ri(X) с полиномом Ai(X)X

m

(1.29)

необходимо выход КУ подключить к одному из входов схемы логического сложения (ИЛИ),

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

информационной кодовой комбинации Ai(X) (старшим разрядом вперед). Подробнее

рассмотрим работу схемы на конкретном примере.

Пример

Построить схему КУ, обеспечивающего кодирование ЦК (7,4) с порождающим

полиномом G(X) = 1 + X + X

3

путем определения проверочной группы методом деления

полиномов и определения остатка R(X). Проследить по тактам процесс кодирования и

состояние элементов схемы при кодировании исходного полинома

3

( ) 1 1001. A X X i = +

X

0

X

1

X

2

AND2

AND2

OR2

Ai(X)

Bi(X)

(1-4)TИ

(5-7)TИ

IN

OUT

DD1

DD2

g0=1 g1=1 g2=0 g3=1

Рис. 1.10. Схема кодера для (7,4)-кода Хемминга.Схема кодера для условий примера изображена на рис. 1.10, состояние ячеек СР и

выхода схемы по тактам — в табл. 1.7. Наряду с особенностями построения схемы, КУ

дополнено двумя ключевыми схемами, роль которых выполняют схемы логического

умножения DD1 и DD2 соответственно. В течение первых k = 4 тактов на второй вход схемы

DD1 поступают ТИ, обеспечивая прохождение символов от выходного сумматора в шину

обратной связи СР. Начиная с 5-го по 7-й такт, ТИ на второй вход схемы DD1 не поступают, и

обратная связь разрывается. В это время поступают ТИ на второй вход схемы DD2,

благодаря чему выход СР подключается к выходу всего КУ, обеспечивая выдачу остатка от

деления кодовой комбинации

Ai

(X) на порождающий полином G(X) на выход, для подстыковки проверочных символов к

Ai(X).

Из табл.1.7 видно, что после 4-го такта в СР образуется остаток 011, т. е.

2

R X X X ( ) = + , а в течение n тактов на выход поступает кодовая комбинация

2 3 6

0111001 ~ X X X X + + + (старшим разрядом вперед).

Декодер для кода Хемминга (7,4). При аппаратурной реализации декодеров ЦК для

определения синдрома используют схему, осуществляющую процедуру деления полинома

на полином (см. рис. 1.7). При построении ДУ следует дополнительно включать ЗУ на k

элементов и схему опроса остатка при делении.

Таблица 1.7. Состояния КУ обеспечивающего кодирование ЦК (7,4)

Номер

такта

Выход

Состояние

ячеек ключей

X

0

X

1

X

2

Выход DD1 DD2

0 − 0 0 0 −

1 1 1 1 0 1 Замкнут Разомкнут

2 0 0 1 1 0

3 0 1 1 1 0

4 1 0 1 1 1

5 − 0 0 1 1

Разомкнут

6 − 0 0 0 1 Замкнут

7 − 0 0 0 0

Эта схема состоит из схемы логического сложения (OR) на m входов и схемы

логического умножения (AND) на два входа; СР и обратные связи должны соответствовать

структуре порождающего полинома G(X), т. е. число ячеек СР должно быть равным m, а

замкнутая обратная связь должна соответствовать ненулевым коэффициентам полинома

G(X).Пример

Построить схему ДУ для ЦК Хемминга (7,4) с порождающим полиномом G(X) = 1 +

X + X3 и по тактам сдвигающих импульсов проследить за его работой. Схема ДУ должна

решать задачу обнаружения ошибок. На рис. 1.11 приведена схема ДУ, в табл. 1.8

представлены состояния ячеек СР при декодировании входной кодовой комбинации Bi(X) =

X + X

2

+ Х

3

+ Х

6

~ 0111001, принимаемой без ошибок. Декодирующее устройство работает

следующим образом.

Таблица 1.8. Состояния ДУ для ЦК Хемминга (7, 4)

Вход B(X) Номер такта Состояние ячеек Выход

X СР

0

X

1

X

2

− Исходное

состояние

0 0 0 −

1 1 1 0 0 0

0 2 0 1 0 0

0 3 0 0 1 0

1 4 0 1 0 1

1 5 1 0 1 0

1 6 0 0 0 1

0 7 0 0 0 0

Кодовая комбинация Bi(X) старшим разрядом вперед поступает на СР для

определения остатка при делении и в ЗУ на k элементов через открытую схему DD1, которая

через k тактов закрывается, так как прекращается подача из синхронизатора ТИ на один из

входов схемы DD1.

При этом в ЗУ запоминаются k информационных символов принимаемой кодовой

комбинации Bi(X). В СР поступают все n элементов Bi(X), и после n тактов происходит опрос

состояния ячеек СР путем подачи циклового импульса с синхронизатора на схему AND2. .

Если R(X)≠0 , то на выходе схемы AND2 импульс не появится и считывания с ЗУ принятых

X

0

AND2

1 2 3 4

X

1

X

2

OR3

AND2

(1-4)TИ

g0=1 g1=1 g2=0 g3=1

IN

Bi(X)

(5-7)TИ

DD2

DD1

OUT

Рис. 1.11. Схема ДУ для ЦК Хемминга (7, 4) информационных символов не произойдет. Если R(X) = 0, то появившийся на выходе AND2

импульс считывает Ai(X) на выход и выдает четыре информационные бита получателю

сообщений.

1.5.9. ПРИНЦИПЫ ПОСТРОЕНИЯ ДЕКОДИРУЮЩИХ УСТРОЙСТВ ДЛЯ ЦИКЛИЧЕСКИХ

КОДОВ С ИСПРАВЛЕНИЕМ ОШИБОК

Декодирование принятых комбинаций ЦК можно производить различными

методами. Наряду с синдромным методом декодирования, основанным на вычислении

остатка от деления принятой комбинации на порождающий код полином, существует

целый ряд других методов, упрощающих процедуру декодирования и не требующих

хранения в памяти ДУ большого числа синдромов при обработке длинных кодов. Для

длинных ЦК разработаны специальные итеративные процедуры декодирования с

исправлением нескольких ошибок, например, метод Берлекэмпа или более совершенный

итеративный алгоритм Тренча-Берлекэмпа-Месси (ТБМ-метод), оперирующий с

полиномами над полями Галуа. Различные методы декодирования так же, как и коды,

получают авторские наименования. Известны алгоритмы декодирования Хемминга,

Питерсона, Ченя, Мэггита, Витерби и других.

Декодирующие устройства для кодов, предназначенных только для обнаружения

ошибок, по существу, не отличаются от схем Кодирующего Устройства (см. 1.5.8). В них

добавляется лишь буферный регистр для хранения принятого сообщения на время

проведения операции деления. Если остаток–синдром при делении оказывается нулевым,

что свидетельствует об отсутствии ошибки, то информация с буферного регистра

считывается в дешифратор сообщения. Если остаток обнаружен, что свидетельствует о

наличии ошибки, то информация в буферном регистре уничтожается и на передающую

сторону к источнику сообщения посылается сигнал запроса повторной передачи по

обратному каналу связи.

В случае исправления ошибок схема Декодирующего Устройства, естественно,

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

вектора Z(X) (1.30), содержит, как и ранее, синдром, получаемый в результате деления

полиномов. Структурная схема ДУ, решающего задачу исправления ошибок, показана на

рис. 1.12.

Буферный регистр

Определитель синдрома

Анализатор синдрома

Локатор ошибки

IN OUT

. . .

. . .

Рис.1.12. Структурная схема декодирующего устройства Символы подлежащей декодированию кодовой комбинации, возможно,

содержащей ошибку, последовательно, начиная со старшего разряда, вводятся в n-

разрядный буферный регистр сдвига и одновременно в схему определителя синдрома, где

за n тактов деления определяется остаток, который в случае синхронной, непрерывной

передачи кодовых комбинаций сразу же переписывается в аналогичный СР схемы

анализатора синдрома.

В состав схемы анализатора синдрома может входить ПЗУ, в котором записаны все

возможные конфигурации синдромов с соответствующими им шумовыми векторами.

Кодовые комбинации шумовых векторов (1.30) содержат «единичные» символы на тех

позициях, которые в процессе передачи сообщения по каналу связи оказались

искаженными помехами.

Локатор ошибок (определитель места ошибок) представляет собой комбинаторно-

логическую схему, выдающую на выход единичные символы в те моменты времени, когда

каждый из ошибочных символов принятой кодовой комбинации занимает в буферном

регистре крайнюю правую ячейку. При последующем тактовом сдвиге локатор ошибки

(детектор ошибки) формирует символ «1», который поступает на сумматор коррекции,

представляющий собой схему суммирования «по модулю 2», где исправляется искаженный

символ.

Одновременно по цепи обратной связи с выхода локатора ошибки подается

единичный символ на анализатор синдрома, что в ряде конкретных схемных решений

построения анализатора упрощает его построение на базе ЛПС без использования ПЗУ.

Сложность анализатора синдрома и локатора ошибки зависит от гарантированного числа

исправляемых и обнаруживаемых ошибок. Естественно, простейшие схемные решения

получаются при обработке кодов, рассчитанных на исправление единичных ошибок.

Как видно из рассмотрения логики работы структурной схемы декодера (см. рис.

1.12), наиболее сложной частью его является необходимость запоминания заранее

вычисленных синдромных полиномов и соответствующих им векторов ошибок.

Достоинством ЦК как раз и является то, что анализатор синдрома можно значительно

упростить, воспользовавшись алгебраической структурой кода для отыскания связей между

синдромами при числе исправляемых ошибок gи > 1. Опираясь на эти связи, можно

запомнить в ПЗУ только полиномы ошибок, соответствующие некоторым типичным

синдромным полиномам, а вычисление остальных осуществить затем с помощью простых

вычислительных алгоритмов. Именно на таких принципах работают различные варианты

декодеров Мэггита.