Королёв А.И. Коды и устройства помехоустойчивого кодирования

Подождите немного. Документ загружается.

5.2.2. Синтез кодека циклического кода с формированием системы свя-

занных проверок

Разработать кодек циклического кода, реализующего мажоритарный алго-

ритм декодирования и полностью реализующий минимальное кодовое расстояние

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

Это определяется условием, которое накладывается на систему раздельных про-

верочных подматриц (5.5), а именно: декодируемый информационный символ

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

проверочное уравнение.

Для кодов, которые не допускают формирование СРП, необходимо “осла-

бить” условие накладываемое на формируемые проверочные уравнения, т.е. до-

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

уравнения. Пусть каждый символ, кроме декодируемого а'

, может входить не бо-

лее чем в ε

проверочных уравнений. В этом случае одиночная ошибка исказит не

более ε

проверочных уравнений, а t (t≥2) – кратная ошибка исказит не более t·ε

проверочных уравнений. Параметр ε

называется коэффициентом связности про-

верочных уравнений, а сформированные соответствующие проверочные уравне-

ния образуют систему связанных проверочных уравнений (ССП).

При ε

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

содержит в i-ой строке только единичные символы, а в остальных строках –

не более ε

единичных символов. В общем ССП представляет собой обобщение

СРП, для которой ε

=1.

Для реализации кодового расстояния (d

) равного минимальному кодовому

расстоянию, т.е. d

= d

, достаточно иметь не более

mах

=ε

–2)+1 (5.9)

нетривиальных проверочных уравнений.

Минимально реализуемое кодовое расстояние при ССП равно или более

pmin

≥[(μ-1)/ ε

]+2, (5.10)

где [(μ-1)/ ε

]– означает ближайшее меньшее целое число.

Если при числе исправляемых ошибок t

исп

-1, кроме декодируемого сим-

вола a

существует t' символов, искажение которых вызывает нарушение t'·ε

про-

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

называемых, первого типа (ССП

), а в противном случае имеем систему связан-

ных проверок второго типа (ССП

). Для ССП

число искаженных проверочных

уравнений не больше, чем для ССП

при одинаковых значениях t и ε

; при ε

ССП

не существует. Потому условие (5.9), оставаясь достаточным, не является

необходимым. Действительно, если t–кратная ошибка нарушает менее t·ε

уравне-

ний, то при d

=2·t+1 для исправления t'≤t ошибок надо иметь μ<ε

-2)+1 прове-

рочных уравнений.

Далее выполним синтез только функциональной схемы декодера цикличе-

ского кода реализующего мажоритарный алгоритм декодирования при формиро-

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

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

вания.

В качестве ЦК выбираем (n,k,d

)=(7,4,3) – код Хэмминга с порождающим

полиномом P(x)=x

+1 для которого невозможно составить СРП.

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

т.е. ε

=2. Определяем проверочный полином

h(x)=(x

+1)/P(x)=(x

+1)/(x

+1)=x

+1=1+x

=10111.

Строим транспонированную проверочную матрицу следующим образом:

1) в качестве первого столбца записываем проверочный полином, пред-

ставленный в двоичной форме и дополняем его нулевыми символами до n=7;

2) производим (l-1)=(3-1)=2 последовательных циклических сдвига вниз

двоичных символов первого столбца. В результате получаем следующую транс-

понированную проверочную матрицу:













100

110

111

011

101

010

001

)(

3,7

(5.11)

Используя данную подматрицу строим проверочную подматрицу θ

1.1

(х)

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

1) первый столбец проверочной подматрицы θ

1.1

(х) повторяет первый стол-

бец матрицы (5.11);

2) символы второго и третьего столбцов формируются путем суммирования

по модулю два двоичных символов соответственно первого плюс второго и пер-

вого плюс третьего столбцов матрицы (5.11);

3) символы четвертого столбца формируются путем суммирования по мо-

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

(5.11);

В результате получаем следующую проверочную подматрицу:













1100

0110

1001

0101

0011

1010

1111

)(θ

1.1

(5.12)

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

из одних ненулевых символов, т.е. 1, а все остальные строки содержат не

более двух единиц. Следовательно, данная проверочная подматрица образует

ССП с коэффициентом связности ε

=2 и позволяет сформировать следующую

ССП:

⊕а

. (5.13)

В данном случае μ=4 и на основании формулы (5.10) реализуемое кодовое

расстояние d

= d

= 3. Однако, согласно формуле (5.9), достаточно использовать

µ=3 проверочных уравнений и плюс тривиальное проверочное уравнение а

=а

Следовательно, одно проверочное уравнение из ССП (5.13) можно исключить.

Опустим проверочное уравнение вида а

⊕ а

Таким образом, для синтеза функциональной схемы декодера используем

следующую ССП:

= a

= а

⊕ а

= а

⊕ а

= а

⊕ а

Основными функциональными блоками декодера являются: последователь-

ный регистр сдвига, содержащего n = 7 ячеек памяти, блок формирования ССП

(совокупность сумматоров по модулю два), мажоритарный элемент (МЭ), комму-

татор (К), ключи управления (Кл) и формирователь сигналов управления ключа-

ми. В соответствии с этим обобщенная функциональная схема декодера будет

иметь следующее построение (рис.5.7).

Рис.5.7.Обобщенная функциональная схема декодера при формировании

ССП и ε

= 2

(x)

Вых.

Вх.

Q(x)

мэ

1 Т

Дв.сч

Отметим, что в ССП (5.13) данные уравнения линейно-зависимы (сумма их

по модулю два тождественно равны нулю). Поэтому любые три проверочных

уравнения содержат информацию о четвертом проверочном уравнении и отбра-

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

случае корректирующей способности кода, но упрощает реализацию декодера.

Однако не всегда можно исключать проверочные уравнения; в ряде случаев фор-

мируемые информационные символы на выходе мажоритарного элемента должны

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

пользоваться не полностью.

Наряду со существованием СРП и ССП могут быть квазираздельные и ква-

зисвязанные проверочные уравнения. Квазираздельные проверочные уравнения

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

модулю два) любых символов. Для этого “ν” (ν ≥1) в матрице θ

ν,1

, соответст-

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

элемента. Для данных уравнений также сохраняется свойство цикличности отно-

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

зисвязанные проверочные уравнения – это такие проверочные уравнения, при ко-

торых матрица θ

ν,

в ν (ν ≥1) строках содержит только единичные символы, а в

остальных строках – не более ε

единичных символов.

Кроме рассмотренных способов формирования проверочных уравнений раз-

работан способ ортогонализации проверочных уравнений в L (L≥2) шагов или

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

ной редукции кода. С данными алгоритмами декодирования можно познакомить-

ся в монографии [4]. Достоинством алгоритма мажоритарного декодирования яв-

ляется минимальная задержка информации при декодировании, которая составля-

ет (n+k) тактов; n тактов при записи информации в регистр сдвига декодера;

k тактов при выдаче информации.

5.2.3 Синтез кодека циклического кода, реализующего синдромный алго-

ритм декодирования

В соответствии с [1…4,6,7] достоинствами синдромного алгоритма декоди-

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

скорость обработки информации (отсутствие задержки информации при декоди-

ровании).

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

ставляет собой двоичный вектор S(x) длины l символов, который может быть по-

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

следовательности F'(х) на транспонированную проверочную матрицу H

l, n

(х), т.е.

S(x)= F'(х) · H

l, n

(х), или как результат деления F'(х) на образующий полином P(x),

т.е. S(x) = R(х) = F'(х)/ P(x). Структура синдрома S(x) зависит лишь от количества

и структуры ошибок в принятой кодовой последовательности F'(х).

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

дром) чаще всего сопоставляется со структурой проверочной матрицы H

l, n

(х).

Характерной особенностью проверочной матрицы линейных кодов является то,

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

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

(n,k,d

) модно построить 2

n-k

-1 = 2

-1 различных по структуре проверочных мат-

риц.

Проверочные матрицы могут быть построены с использованием как порож-

дающей матрицы G

k,n

(x), так и проверочного полинома h(x). Кроме того, прове-

рочную матрицу можно построить следующим способом: столбцы проверочной

матрицы H

l,n

(х) можно представить в виде полиномов от оператора “х” степени

(l –1), причем единичному элементу (логической единице) столбца, принадлежа-

щему первой нижней строке матрицы H

l,n

(х), соответствует член полинома “х

”,

а единичному элементу последней верхней строки матрицы соответствует член

полинома “х

l -1

”. Следовательно, все столбцы проверочной матрицы H

l,n

(х) могут

быть получены как остатки от деления х

на образующий полином P(x), где ί –

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

столбца проверочной матрицы минус единица, т.е. 0 ≤ ί ≤ (n-1). Например, для ЦК

Хэмминга с параметрами кода (n, k,d

) = (15,11,4) проверочная матрица, как один

из возможных вариантов, имеет следующую структуру.

4,15

(х) =













1 0 0 0 1 1 1 1 0 1 0 1 1 0 0

0 1 0 0 0 1 1 1 1 0 1 0 1 1 0

0 0 1 0 0 0 1 1 1 1 0 1 0 1 1

0 0 0 1 1 0 0 1 1 1 1 0 1 0 1

.....

12 11

....... ........

aaaaa

Первые “k” столбцов проверочной матрицы определяют информационные

символы (а

…а

), которые входят во все проверочные уравнения, а l = n – k

столбцов образуют единичную подматрицу (а

…а

Кодовая последовательность F'(х) будет принадлежать (n,k,d

) – коду, если

F'(х) · H

l, n

(х) = 0. Следовательно, для реализации синдромного алгоритма деко-

дирования необходимо “связать” полученную структуру синдрома S

(x) со струк-

турой столбцов проверочной матрицы H

l,n

(х), принадлежащих информационным

символам, т.е.













(x)S

























(x)

Таким образом, позиция столбца проверочной матрицы H

l,n

(х), совпадающая

со структурой синдромного вектора S

(x), определяет позицию ошибочного ин-

формационного символа, а соответствующий дешифратор декодера, настроенный

на данную структуру синдрома, сформирует и выдаст сигнал коррекции.

С целью упрощения рассмотрения способа построения и функционирования

кодека, реализующего синдромный алгоритм декодирования выбираем ЦК

Хэмминга с параметрами (n,k,d

) = (7,4,3) и один из вариантов проверочной мат-

рицы кода следующего вида:













=3,7Η=

1 0 0 1 0 1 1

0 1 0 1 1 0 1

0 0 1 1 1 1 0

a a a a a a a

b b b

)()(,

7 654 321

321

xxnHl

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

функции, выполняемые соответственно кодером и декодером.

Основными функциями кодера являются:

1) преобразование входной информации Q(х) из последовательного кода в

параллельный код;

2) формирование проверочных символов;

3) формирование кодовой последовательности F(х) путем последовательно-

го объединения “k” информационных символов и l = n-k проверочных символов в

единый кодовый поток.

Для реализации данных функций в кодере необходимы следующие функ-

циональные блоки:

КРИ – 1/ k (КРИ – 1/4) – коммутатор распределения входной информации

на “ k ” (k = 4) подпотокав;

ФПС

– формирователь проверочных символов кодера;

КОИ – n/1 (КОИ – 7/1) –коммутатор объединения информации “n” (n =7) па-

раллельных подпотоков в единый поток;

ФСУ

– формирователь сигналов управления КРИ – 1/4 и КОИ – 7/1 кодера.

В соответствии с этим обобщенная структурная схема кодера будет иметь

следующее построение (рис.5.8)

(5.14)

Рис.5.8. Обобщенная структурная схема кодера с синдромным алгоритмом

декодирования

В кодере, в соответствии с проверочной матрицей (5.14), ФПС

формирует

проверочные символы b

, которые поступают на соответствующие входы

КОИ – 7/1 и далее передается вслед за информационными символами в канал свя-

зи, образуя тем самым кодовую последовательность F(x).

Основными функциями декодера являются:

1) преобразование кодовой последовательности F'(х) из последовательного

кода в параллельный код;

2) формирование проверочных символов (b

',b

') из принятых информа-

ционных символов a

'… a

' в соответствии с матрицей (5.14);

3) формирование символов синдромной последовательности (синдрома)

… S

;

4) дешифрация (анализ) синдрома и принятие решения о достоверности

принятых информационных символов;

5) преобразование информационных символов из параллельного кода в по-

следовательный код и выдача информационного блока символов θ

(х) получате-

лю.

Для реализации данных функций в декодере необходимы следующие функ-

циональные блоки:

Q(x)

(х)

Вых.

Вх.

КРИ-

-1/4

КОИ-

-7/1

ФПС

КРИ – 1/n (КРИ - 1/7) – коммутатор распределения информации на n (n=7)

параллельных подпотоков;

КОИ - k /1 (КОИ – 4/1) – коммутатор объединения информации к (к=4) па-

раллельных подпотоков в последовательный поток;

ФПС

– формирователь проверочных символов декодера;

ФСС – формирователь синдромных символов;

АС – анализатор (дешифратор) синдрома;

ФСУ

– формирователь сигналов управления (КРИ - 1/7) и (КОИ – 4/1) деко-

дера.

В соответствии с этим обобщенная структурная схема декодера,

реализующего синдромный алгоритм декодирования, будет иметь следующее

построение (рис.5.9).

Рис.5.9. Обобщенная структурная схема декодера, реализующего синдром-

ный алгоритм декодирования

Декодер работает следующим образом. Входные символы принятой

кодовой последовательности F

′

(x) в КРИ –1/7 распределяется на семь

параллельных подпотоков. Информационные символы a

'… a

' одновременно

поступают на соответствующие входы КО и ФПС

ФПС

формирует

проверочные символы b

… b

из принятых информационных символов в

ск

а'

F'(

х)

Вх.

КРИ-

-1/7

(х)

Вых.

ФСУ

Вх.

КОИ-

-4/1

ФПС

АС ФСС

КО