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

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

соответствии с проверочной матрицей (5.14). Сформированные проверочные сим-

волы поступают на соответствующие входы ФСС, на другие входы которого по-

ступают принятые проверочные символы b

'… b

'. Синдромные символы S

формируются по правилу: S

= b

⊕b

'; S

= b

⊕b

'; S

= b

⊕b

'.Следовательно, син-

дромный вектор или синдром S

(x) в данном случае будет содержать три двоич-

ных символа, т.е. S(x)= S

, S

При отсутствии ошибок в принятой кодовой последовательности F′(x) син-

дром будет нулевым, т.е. S(x) = S

, S

= 000. При наличии ошибок синдром бу-

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

в кодовой последовательности F′(x). Так как рассматриваемый ЦК Хэмминга ис-

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

информационным символам a

'… a

' структура синдрома S

(x) соответствует

структуре столбцов проверочной матрицы (5.14), т.е. Sa

(x) = 011 соответствует

ошибочно принятому символу a

, Sa

(x) = 101 – ошибочному a

, Sa

(x) = 110 –

ошибочному а

и Sa

(x) = 111 – ошибочному а

Сформированные символы синдрома S

(x) поступают на соответствующие

входы АС, который формирует четыре сигнала коррекции СК

… СК

, поступаю-

щие на соответствующие входы КО. Условно можно принять, что СК

соответст-

вует коррекции информационного символа а

, СК

- символу а

и т.д. После со-

ответствующей коррекции информационные символы поступают на соответст-

вующие входы КОИ – 4/1 и где преобразуются из параллельного кода в последо-

вательный код и в виде информационного блока Q(х) выдается получателю.

Синтез функциональных схем кодека, реализующего синдромный алгоритм

декодирования ЦК, выполняем по методике, рассмотренной при синтезе функ-

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

вания.

Синтез функциональной схемы кодера. Из алгоритма работы кодера следует,

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

аналогичными принципам построения функциональных блоков кодера с мажори-

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

КРИ – 1/4 выполняется в виде последовательного (RG

) и параллельного

(RG

) регистров сдвига;

КРИ – 7/1 – выполняется в виде синхронного мультиплексора;

ФПС

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

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

матрицей (5.14)

ФСУ

– состоит из делителя частоты на четыре и кольцевого счетчика на

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

Функциональная схема кодера приведена на рис.5.10

Рис.5.10. Функциональная схема кодера с синдромным алгоритмом кодиро-

вания

Синтез функциональной схемы декодера выполняем по следующей методи-

ке: блоки декодера, реализующие одинаковые функции с блоками кодера, выпол-

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

ются: КРИ – 1/7, КОИ – 4/1, ФПС

и ФСУ

;

Bых.

ДШ Дв.сч.

=nf

Bx.

Q(x)

F(x)

ФСС и КО выполняются в виде совокупности сумматоров по модулю два;

АС выполняется в виде четырех дешифраторов (ДШ1…ДШ4), настраивае-

мые соответственно на комбинации синдрома: 011(ДШ1); 101(ДШ2); 110(ДШ3);

111(ДШ4).

Функциональная схема декодера, реализующего синдромный алгоритм деко-

дирования, приведена на рис. 5.11.

Рис.5.11. Функциональная схема декодера, реализующего синдромный алго-

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

Корректирующую способность разработанного кодека проверим при сле-

дующих условиях:

информационный блок символов Q(х), поступающих на вход кодера, пред-

ставляет собой нулевую последовательность, т.е. Q

(х) = a

=0000. Следова-

тельно, сформированная кодовая последовательность F(x) также будет нулевой

последовательностью, т.е. F(x) = b

=0000000;

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

вол а

, т.е. принята кодовая последовательность следующей структуры

Вх.

ДШ Дв.сч.

Вх.

ДШ1

ДШ2

ДШ3

ДШ4

Q(x)

Вых.

F(x)

Вх.

RG1

RG2

СК

F′(x) = b′

b′

a′

= 0000001;

ДШ1 настроен на сидром S (x) = 011.

В декодере из принятых информационных символов a

′, a

′= 0001, в

соответствии с проверочной матрицей (5.14), формируются следующие прове-

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

= а′

⊕ а′

= 0⊕0⊕0 = 0, b′

= а′

⊕ а′

= 1⊕0⊕0 = 1,

b′

= а′

⊕ а′

= 1⊕0⊕0 =1. Соответственно синдромные символы будут равны:

= b

⊕b

'= 0⊕0 = 0, S

= b

⊕b

'= 0⊕1= 1, S

= b

⊕b

'= 0⊕1 = 1. Следовательно,

синдром будет иметь следующую структуру: S(x) = 011. Данные символы син-

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

выходе ДШ1 будет сформирован сигнал коррекции (СК1) с уровнем логической

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

модулю два первой информационной цепи, а на второй вход сумматора по моду-

лю два поступит ошибочный информационный символ a

'. В результате суммиро-

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

'⊕СК1=1⊕1=0. Аналогичным образом будет производиться декодирование по-

следующих кодовых последовательностей.

5.3. Коды Файра: основные свойства, определение, способы кодирования

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

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

Абрамсона, которые задаются образующим полиномом вида P(x)= ρ(x)(x+1), где

ρ(x) - примитивный полином степени ε, величина которой выбирается равной

кратности корректируемых ошибок. Длина “n” кодовых последовательностей ко-

дов Абрамсона определяется выражением n = 2

-1 двоичных символов, число “k”

информационных символов на длине “n” кодовых символов равно k=n-ε-1, а чис-

ло l = ε+1. Минимальное кодовое расстояние данных кодов равно четырем

= 4); данные коды исправляют все одиночные и смежные ошибки [1, 3, 8].

Циклическим кодом Файра, корректирующего одиночные пакеты ошибок

кратностью t

п.исп.

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

GF(2), задаваемый образующим полиномом вида

P(x)= ρ(x)(x

+1), (5.15)

где ρ(x) – примитивный полином над GF(2), степень ε которого не меньше

кратности корректируемого пакета ошибок (ε ≥ t

п.исп.

) и который не делит двучлен

+1),

с ≥ 2·t

п.исп.

или с ≥ t

п.исп.

+ t

п.обн.

-1 – максимальная степень двучлена; t

п.исп.

п.обн.

– кратности соответственно исправляемого и обнаруживаемого пакетов

ошибок.

Коды Файра обеспечивают одновременно коррекцию одиночных пакетов

ошибок кратностью t

п.исп.

двоичных символов и обнаружение одиночных

пакетов ошибок кратностью t

п.обн.

двоичных символов при условии, что

п.исп.

≤ ε и t

п.исп.

+ t

п.обн.

- 1 ≤ с. Положение пакетов ошибок в кодовой последова-

тельности F

(x) может быть произвольным, т.е. занимать любые позиции кодовых

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

способность кодов Файра к пакетным ошибкам существенно увеличивается.

Двучлен (x

+1) определяет правило формирования проверок на четность, а

именно “с” перемежающихся и равномерно расположенных проверок. Так как

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

расстоянии “с” друг от друга, то при возникновении пакета ошибок кратностью

п.исп

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

проверок, а в (с - t

п.исп

) последовательных проверках не будет искаженных сим-

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

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

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

мом ρ(x).

К достоинствам ЦК Файра следует отнести сравнительно простые алгоритмы

(правила) кодирования и декодирования данных кодов, а также минимальная

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

полним синтез функциональных схем кодека ЦК Файра, используя параметры ко-

да Файра из примера 3.7, а именно: (n, k, d

) = (42,33,8), P(x) = x

+ x

+x+1,

п.исп

≤3 двоичных символа и t

п.обн

≤4 двоичных символа.

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

следовательности F(x) при использовании кода Файра осуществляется по правилу

F(x)=

P(x)

xQ(x)

⋅

xQ(x)⋅ , то кодер будет содержать регистр сдвига со встроен-

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

l= 9 ячеек памяти, пять сумматоров по модулю два (на единицу меньше количест-

ва ненулевых членов образующего полинома), двухвходовой коммутатор (двух-

входовая схема ИЛИ), три ключа управления кодером (двухвходовые схемы И) и

формирователь сигналов управления ключами. В соответствии с этим обобщен-

ная функциональная схема кодера ЦК Файра будет иметь следующее построение

(рис.5.12)

Рис.5.

12. Обобщенная функциональная схема кодера ЦК Файра:

(n,k,d

)= (42,33,8) , P(x) = x

+ x

+x+1

На рис.5.13 приведены временные диаграммы, поясняющие принцип работы

кодера

Рис.5.13. Временные диаграммы сигналов управления ключами кодера

Кл.1

Вх.Q(x)

М2

СУ2

СУ1

ФСУ

ключами

Вх.

Кл.2

Кл.3

F(x)

33 42

СУ1

СУ2

Кл.1,Кл.2

Кл.3

…

Синтез функциональной схемы декодера. Сложность разработки функцио-

нальной схемы декодера ЦК Файра зависит от используемого алгоритма декоди-

рования. Принимаем, что критериями при выборе алгоритма декодирования яв-

ляются: обеспечение минимальной задержки информации при декодировании и

минимальная сложность реализации декодера. Такими достоинствами обладают

конвейерный декодер Меггитта и декодер, построенный на основе образующего

полинома, представленного в виде произведения нескольких полиномов. Недос-

татком последнего декодера является большой объем оборудования. В связи с

этим разрабатываем функциональную схему декодера ЦК Файра по схеме Мег-

гитта.

В соответствии с [3] конвейерный декодер Меггитта содержит следующие

функциональные блоки: три генератора синдрома (RG1…RG3), выполняемых в

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

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

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

(БУ); ключи управления; блок формирования сигналов управления ключами; два

дешифратора (ДШ), один из которых осуществляет проверку на наличие не более

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

на все нули во втором генераторе синдрома и два пороговых элемента. Обобщен-

ная функциональная схема декодера ЦК Файра приведена на рис.5.14, а на

рис.5.15 приведены временные диаграммы, поясняющие принцип работы декоде-

ра.

Рис.5.15. Временные диаграммы сигналов управления ключами декодера

… …

СУ1

t СУ2

СУ3

t СУ4

117

… …

…

Декодер функционирует следующим образом. В течение 42 тактов ключ

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

менно запись кодовых символов принятой кодовой последовательности F′(x) в

буферное устройство (БУ) и формирование синдромных символов

(x)

P(x)

(x)'

Синдромные символы фиксируются регистром сдвига RG

первого

генератора синдрома. По окончании 42 такта синдромные символы из RG

запи-

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

второго генератора синдро-

ма.

Затем в течение 42 тактов осуществляется одновременно анализ структуры

синдромных символов RG

(“вылавливание” первой ошибки) и коррекция

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

вторую часть БУ. По окончании 2n = 2· 42 = 84 такта содержимое регистра

сдвига RG

переписывается в регистр сдвига RG

третьего генератора синдрома и

далее в течение к = 33–х тактов осуществляется выдача информации получателю

с одновременной коррекцией второй ошибки или второго ошибочного информа-

ционного символа. Запись кодовых символов следующей кодовой последователь-

ности осуществляется после окончания 2·n = 2·42 = 84 такта декодирования.

5.4. БЧХ – коды: определение, матричное представление, способы коди-

рования и декодирования, синтез структурных схем кодека

Коды Боузе-Чоудхури-Хоквингема (БЧХ-коды) являются дальнейшим разви-

тием линейных блоковых кодов Хэмминга, относятся к классу циклических кодов

и обеспечивают коррекцию как независимых, так и группирующихся (пакетных)

ошибок.

В соответствии с [1, 3, 7, 8] циклический двоичный код длины n = 2

– 1

двоичных символов называется примитивным БЧХ-кодом с конструктивным ко-

довым расстоянием d = 2·t + 1, если его образующий полином равен

P(x) = НОК[m

(x), m

(x), …, m

2t-1

(x)], где m

(x) – минимальный примитивный по-

лином степени ε = log

(n + 1). Максимальная степень P(x) и, следовательно, число

проверочных символов не более l < ε·t

исп.

двоичных символов (t

исп

– кратность ис-

правляемых ошибок), а число информационных символов равно k = n – ε · t

исп.

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

Из определения БЧХ-кода следует, что корнями P(x) являются элемен-

ты

исп.

α,...,α,αα,

−

⋅

, а также

исп.

642

α,...,α,α,α

⋅

, т.е. 2· t

исп.

последовательных

степей

. Поэтому конструктивное кодовое расстояние кода равно

исп.

⋅

Так, например, для БЧХ-кода корректирующего двукратные ошибки (t

исп.

=2), кор-

нями образующего полинома P(x) являются элементы ,α,α

а также

α,α и

= 2·t

исп.

+ 1 = 2 ·2 + 1 = 5. Образующий полином P(x) для данного БЧХ-кода ра-

вен P(x) = m

(x)· m

(x), где m

(x) и m

(x) – минимальные полиномы

соответственно элементов

α,α . Проверочная матрица данного кода имеет вид













−

1)2(n963

1n32

...αα α α 1

)(xH

Учитывая основное свойство линейных кодов F(х) · H

(х) = 0 или

H(х) ·F'(х) = 0 следует, что элементы α

и α

являются корнями F(x), т.е.

F(α

) = F(α

) =0.

Для коррекции ошибок произвольной кратности (t, двоичных символов)

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

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

полинома P(x) являются δ-1 последовательных степеней α

(P(α

) = P(α

e+1

) = P(α

e+2

) = …=P(α

e+δ-2

) = 0, e ≥ 0, δ ≥ 1) имеет кодовое расстояние

≥δ. Число δ называется конструктивным кодовым расстоянием и является ниж-

ней границей кодового расстояния. Поэтому для коррекции всех конфигураций

ошибок кратности t надо выбирать образующий полином P(x) с 2 · t

последовательными корнями. Так как кодовые последовательности F

(x) циклич-

ного кода делятся без остатка на P(x), то элементы

исп.

α,...,α,αα,

−

⋅

, а также

t242

α,...,α,αα,

⋅

, являясь корнями P(x), являются корнями полиномов F

(x).

(5.16)