Кодек каскадного блочного кода

 

Изобретение может использоваться для помехоустойчивого кодирования и декодирования информации в каналах дискретных систем связи и обеспечивает повьшение исправляющей способности и упрощение декодера. Кодек содержит кодеры 1, 2, сумматоры 3, 5, 8, 9, 15, канал 4 связи, блоки формирователей синдрома (ВФС) 6, 12. 00 со оо о. ел Фиг.1

СОЮЗ СОВЕТСКИХ

СОЦИАЛИСТИЧЕСКИХ

РЕСПУБЛИК

„„SU„„1338075 А1 д1) 4 Н 03 Г1 13/00

ОПИСАНИЕ И306РЕТЕНИЯ

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ

ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССР

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ (21) 3845405/24-09 (22! 21.01.85 (46! 15.09.87. Ьюл. М 34 (72) С.JI.Ïoðòíîé, JI.P.Àíêóäèíîâ и К.ll.голодкина (53) 621.394.14(088,8) (56) Питерсон У., Уэлдон Э. Коды, исправлявшие ошибки. И.: Мир, 1976.

Авторское снидетельстно СССР

М 965000, кл. Н 03 M 13/00, 1981. (54) КОДЕК КАСКАДНОГО Б110ЧНОГО КОДА (57) Изобретение может использоваться для помехоустойчивого кодирования и декодирования информации в каналах дискретных систем связи и обеспечивает повышение исправляющей способности и упрощение декодера. Кодек содержит кодеры 1, 2, сумматоры 3, 5, 8, 9, 15, канал 4 связи, блоки формирователей синдрома (БФС) 6, 12.

1338075 элементы задержки 7, 13, 14, блок 10 сумматоров, пороговый элемент 11, формирователь 16 элементов поля, формирователь 1/ локаторов ошибок и комбинационный узел 18. БФС 6 представляет собой два параллельно соединенных регистра с обратными связями и сумматорами по модулю два. Соединения в обратной связи соответствуют генераторному полиному первого внешнего кода, 3а первые и тактов в первом регистре формируется синдром, который в конце и-го такта переписывается во второй регистр, а в первом регистре формируется синдром следуюИзобретение относится к технике связи и может быть использовано для помехоустойчивого кодирования и декодирования информации в каналах дискретных систем связи, Цель изобретения — повышение исправляющей способности и упрощение декодера.

На фиг. 1 представлена структурная электрическая схема кодека каскадного блочного кода; на фиг. 2 формирователь эпементов поля; на фиг. 3 — формирователь локаторов ошибок; на фиг. 4 — комбинационный узел lr на фиг ° 5 — блок сравнения; на фиг. 6 — временные диаграммы работы кодека каскадного блочного кода.

Кодек каскадного блочного кода содержит первый 1 и второй 2 кодеры, 20 первый сумматор 3, канал 4 связи, второй сумматор 5, первый блок 6 формирователей синдрома, первый элемент

7 задержки, третий 8 и четвертый 9 сумматоры, блок 10 сумматоров, пороговый элемент il второй блок 12 формирователей синдрома, второй 13 и третий 14 элементы задержки, пятый сумматор 15, формирователь 16 элементов поля, формирователь 17 локаторов оши30 бок, комбинационный узел 18, формирователь 16 элементов поля, содержащий триггеры 16.1 — 16,6, сумматор 16,7, формирователь 17 локаторов ошибок, содержащий первый 17.1, второй 17 ° 2 и третий 17,3 регистры, комбинационный узел 18, содержащий блок 18.1 щего слова. Во время записи в первый регистр следующего слова во втором регистре осуществляются п сдвигов для исправления п символов слова. Сумматор 8 формирует скорректированные символы слова первого внешнего кода.

БФС 12 состоит из двух формирователей, вычисляющих значения синдромов двух слов второго внешнего кода, В комбинационном узле 18 происходит сравнение поступающих сигналов и формирование сигнала ошибки, который используется для корректировки слова второго внешнего кода. 6 ил. инверторов, блоки 18,2-18.12 сравнения, элемент И 18.13, решающий блок

18.14, блоки 18.2-18.12 сравнения содержат сумматоры 18.2.1 — 18.2.6, элемент И 18,2.7 °

Кодек каскадного блочного кода работает следующим образом.

Первый кодер 1 является кодером (п, k а,) кода, а второй кодер 2 кодером (и, k „ а,) кода; а2 а1. Кодеры 1 и 2 представляют со бой регистры с обратными связями и сумматорами по модулю два. Длина регистров: для кодера 1 — (п-k,), для кодера 2 — (п-k ). Соединения в обратных связях определяются генераторным полиномом кода.

Первый блок 6 формирователей синдрома представляет собой два параллельно соединенных регистра с обратными связями и сумматорами по модулю два.

Соединения в обратной связи соответствуют генераторному полиному первого внешнегО кода. 3а первые п тактов в первом регистре с обратными связями формируется синдром и в конце п-го такта переписывается во второй регистр с обратными связями, а в первом регистре формируется синдром следующего слова, таким образом обеспечивается непрерывное декодирование информации. Во время записи в первый регистр Следующего слова длиной и во втором регистре осуществчяются сдвигов для исправления и символов слова.

1338075

Второй блок 12 формирователей синдрома состоит из двух независимых пар формирователей синдромов второго внешнего кода, каждая из которых аналогична первому блоку 6 формирователей синдрома первого внешнего кода.

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

Формирователь 1Ь элементов поля представляет собой генератор псевдослучайной последовательности. Он последовательно формирует все ненулевые элементы поля GF(n), каждый из элементов представляется в виде (n-k )2 ° разрядного двоичного числа, поступающего на выход. Формирователь 16 эле- 20 ментов поля строится с помощью триггеров и сумматоров по модулю два.

Формирователь 16 элементов поля содержит шесть триггеров.

Все триггеры формирователя 16 25 предустанавливаются в исходное (единичное) состояние синхроимпульсами, поступающими на входы предустановки триггеров в единичное состояние. На тактовые входы триггеров 16.1-16.6 З0 поступают с генератора, не показанного на фиг. 1, тактовые импульсы приема. Таким образом,,с поступлением i-го тактового импульса на выходе формирователя 16 элементов поля формируется (n-k ) 6-разрядное дво35

2 ичное число, представляющее собой

i-й элемент поля GF(n).

Формирователь 17 локаторов ошибок строится с помощью а2 последовательно соединенных (n-k )-разрядных сдви2 говых регистров.

Регистры формирователя 17 локаторов ошибок предустанавливаются в исходное (нулевое I состояние синхроим45 пульсами, поступающими с генератора на входы сброса регистров, На тактовые входы регистров подаются с генератора тактовые импульсы приема. На второй вход формирователя 17 последовательно поступают элементы поля

GF(n).

По сигналу первой ошибки, поступающему на управляющие входы регистров формирователя 17 локаторов ошибок, в первый регистр 17.1 записывается (и-k )-разрядное двоичное чис2 ло а,, представляющее собой локатор первой ошибки. При поступлении сигнала второй ошибки локатор первой ошибки переписывается из первого

17.1 во второй 17.2 регистр, а в первый регистр 17.1 записывается локатор второй ошибки а . Таким образом, к моменту окончанйя декодирования первым внешним кодом в а регистрах фор2 мирователя 17 локаторов ошибок оказываются записанными локаторы а по2 следних ошибок, исправляемых декодером первого внешнего кода, которые поступают на выход формирователя 17.

Каждый блок 18.2-18.12 сравнения комбинационного узла 18 строится на (и-k ) сумматорах 18 ° 2.1-18.2.6 по уодулю два, с помощью которых осуществляется слржение соответствующих разрядов сравниваемых сигналов, а выходы сумматоров соединяются с (и-k )-входовым элементом И 18.2.7.

На первый и второй входы блока

18.2 сравнения параллельно поступают (и-k2) 6 разрядов сравниваемых сигналов. В случае равенства сравниваемых сигналов на выходах сумматоров

18,2.1-18.2.6.и элемента И 18.2.7 формируется .уровень логического нуля.

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

И 18.2.7 формируется уровень логической единицы.

Решающий блок 18.14 строится на основе инверторов, элементов И и элементов ИЛИ. На его входы поступают сигналы Cl, С2, СЗ, С4, С5, С6, С7, С8, С9, С10, Сll, С12. На выходе решающего блока 18.14 формируется сигнал ошибки Е; в соответствии со следую(2 щим логическим уравнением:

1 -(С,C,+Ñ,С,+С„С,+С„) С +(С,C,+

На входы комбинационного узла 18 поступают следующие сигналы: на первый вход — синдром S,, на второй вход — синдром Я, на третий вход— локаторы ошибок а, а, а, на четвертый вход последовательйо поступают все элементы А поля ОГ(п)..

В комбинационном узле 18 осуществляется сравнение синдромов S,, Я между собой и с каждым иэ локаторов ошибок а,, а, а, а также сравнение синдрома $ и локаторов ошибок со всеми элементами поля GF(n). Сравнение осуществляется в однотипных блоках сравнения.

1338075

Сравниваемые сигналы поступают на блоки 18,2-18.12 сравнения следующим образом:

18.2;

18.3;

18,4;

18.5;

18,6;

18,7;

18,8;

18;9;

18.10;

18.11;

18.12. блок блок блок блок блок блок блок блок блок блок блок

S, и

$, и а, S, и а

$, иа„

$ и а, S и а

$ и а

$ и А т а и А

1 а и А а — А ь — на — на — на — на на на — на — на — на — на на второго внешнего кода на позициях, номера котОрых соответствуют тем элементам поля GF(n), которые совпадают с результатом сравнения.

При отсутствии ошибок все локаторы ошибок и синдромы будут равны между собой (и равны нулю). В этом случае вектор ошибок н слове второго внешнего кода 1; (х=Г,n), Аормируемый на выходе комбинационного узла 18, будет равен нулю, так как среди элементов поля GF(nl, формируемых формирователем 16 элементов поля отсутствует нулевой.

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

18 для кода с а =3. Вектор ошибок

1 . (i=1 и) имеет единицы на позициях, номера которых соответствуют тем элементам поля GF(n), которые совпадают с результатом сравнения синдромов,";„, SI между собой и с каждым иэ локаторов ошибок: а,, а,, а„ °

На выходах блоков сравнения формируются соответствующие сигналы: Cl

С2, СЗ, С4, .С5, С6, С7, С8, С9, С10, Cll которые поступают на соответст вующие входы решающего блока 18.14.

Блок 18.1 инверторов содержит (n-k<) инверторов. Он предназначен для инвертирования разрядов синдрома

S на входе элемента И 18,13, на выходе которого формируется уровень логической единицы в случае равенства нули синдрома 5 и уровень логического нуля в противном случае, На выходе элемента И 18.13 формируется сигнал 12, поступающий на соответствующий вход решающего блока 18.14, В случае равенства сравниваемых величин (синдро11ов и локаторов ошибок) на выходе комбинационного узла

18 появляется сигнал ошибок в слове

Один цикл кодирования и декодирования осуществляется следующим образом.

На тактовый вход первого код ра

1 подаются с генератора, не показанного на фиг. 1, тактовые импульсы передачи, следующие с частотой передачи информации. На вход первого кодера 1 поступают k» а на вход второго кодера 2 — k информационных

2 символов. Каскадный код в целом имеет параметры (2п, k +1., мин (а,, 2а.)).

Пусть y," =(yl"1, yl ... т" ) — слово первого внешнего кода, ау =( э I,l

"1) — слово второ го внешнего кода на n

Э первом входе канала 4 связи AopMHpóется слово каскадного кода а " .= у .9

i 11

1 6

О+ 1,(i=1,n), на втором входе канала

4 связи формируется слово (i--l n) Q+- — здесь и далее символ суммы по модулю два, Канал 4 связи представляет собой последовательное соединение 4-фазного модулятора, собственно линии связи и 4-фазного демодулятора. На тактовые входы всех блоков декодера каскадного кода, кроме сумматоров 5, 8, 9 и 15, порогового элемента 11, блока 10 сумматоров и комбинационного узла 18, Подаются с генератора, не показанного на фиг. 1, тактовые импульсы приема, следующие с частотой приема информации.

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

6 и 12 формирователей синдрома, формирователя 16 элементов поля, а также формирователя 17 локаторов ошибок.

Все эти формирователи предусматриваются в исходное состояние последовательностью поступающих с тактового генератора (не показан на фиг. 1) синхроимпульсов, сфазированных с последовательностью тактовых импульсов приема (фиг. 6а,б).

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

Цифрами (1), (2),... на диаграммах (фиг. 6) обозначены временные интервалы обработки соответствующих кодовых слов. 1г1

Принимаемые символы 1(i=l,ni с первого выхода канала 4 связи поступают на вход второго элемента l3 ааЛ <11( держки и вместе с символами и .,i=

7 13380

=l,ò;), поступающими с второго выхода канала 4, — на первый и второй входы второго сумматора 5, на выходе которого формируется слово первого внеш5 него кода

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

Слово у ; (=1,п) поступает на вход первого блока 6 формирователей синдрома и на первый элемент 7 задержки (соответствующие временные интервалы показаны на фиг. Ьн), представляющий собой сдниговый регистр на (бит, в котором принято слово задерживается на время декодирования первым внешним кодом. С выхода первого блока 6 AQPMHPQBaTeJ синдрома сформированный синдром поступает на вход блока 10 сумматоров, в котором в соот нетствии с геометрической структурой первого внешнего кода (п, 1«, а )

19 1 осуществляется суммирование соотнет- 25 стнующих символов синдрома и тем самым формирование проверок, результаты которых с выхода блока 10 сумматоров поступают на вход порогового элемента 11, принимающего решение

"по большинству" об ошибочности или правильности декодируемого символа.

На выходе порогового элемента 11 формируется вектор (. "(i=1,n) ошибок н cJIQBe первого внешнего кода, который вместе с симноламц. „т(, слова первого внешнего кода, хранившимися в первом элементе 7 задержки, поступает на первый и второй входы третьего сумматора 8, на выходе которого полу40 чаются откорректированные символы слова первого внешнего кода постуУ лающие на первый выход кодека. Временные интервалы, соответствующие исправлению ошибок н слове первого внешнего кода, показаны на фиг. Ьг.

Декодирование вторым внешним кодом осуществляется следующим образом. (2)

Симноли e -, (=1,г() с выхода второго элемента 13 задержки (где они хранились н течение времени декодирования перногп внешнего кода) и символы вектора ошибок 1(".)(=Гп) с выхода порогоног(элемента 11 поступают на и рвы)(и второй входы четвертого сумматора 9, с выхода которого откоррек- 55 тнронанное слово второго внешнего кода = « " )" поступает на нто1 I рай нх (д второго блока 12 формирона75 телей синдрома, на перний вход кото"(Zl рого поступают символы ((i=-1,п) с выхода второго элемента 13 задержки.

Второй блок 12 формирователей синдрома состоит из двух формирователей, вычисляющих значения синдромов 8 и

S двух слов второго внешнего кода: (-(" и (« (, (i= l,ï) . Вычисленные значения синдромов поступают на первый и второй входы комбинационного узла

18, на третий вход которого последовательно поступают все ненулевые элементы, поля GF(n) с выхода формирователя 16 элементов поля, а на четвертий вход — локаторы ошибок с выхода формирователя 17 локаторов ошибок. Временные интервалы, соответствующие формированию синдромов слова второго внешнего кода,. формированию локаторов ошибок, элементов поля GF(n) и записи кодовых слов второго внешнего кода и третий элемент 14 задержки показаны на фиг. Ьг. Третий элемент

14 задержки задерживает слово второго внешнего кода на время декодирования нторого внешнего кода.

Исправление ошибок в слове второго внешнего кода происходит с помощью пятого сумматора 15 на второй вход которого поступают символы )(. л (i)

I слова второго внешнего кода, задержанные с помощью третьего элемента

14 задержки, а на первый вход поступают символы вектора ошибок (. . (i= (2)

=l,п), формируемые на выходе комбинационного узла 18. Таким образом, на виходе четвертого сумматора формируется откорректированное слово второго внешнего кода. Временные интервалы, соответствующие исправлению ошибок в слове второго внешнего кода, показаны на фиг. Ьд.

На этом цикл декодирования заканчивается.

Ф о р м у л а и з о б р е т е н и я

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

Вих

Фаа2

9 13380 второго кодера, а также первый, второй и третий элементы задержки и второй сумматор, выход которого подключен к входу первого блока формирователей синдрома и через первый

5 элемент задержки — к первому входу третьего сумматора, к второму входу которого и первому входу четвертого сумматора подключен выход порогового элемента, к входу которого через блок сумматоров подключен выход первого блока формирователей синдрома, при этом первый вход второго сумматора объединен с входом второго элемента задержки, выход которого подключен к первому входу второго блока формирователей синдрома и второму .входу четвертого сумматора, выход коТорого подключен к ВТоро входу 2О второго блока формирователей синдрома, отличающийся тем, что, с целью повышения исправляющей способности и упрощения декодера, введены пятый сумматор, формирова75 о тель элементов поля, формирователь локаторов ошибок и комбинационный узел, к первому и второму входам которого подключены выходы второго блока формирователей синдрома, при этом выход порогового элемента подключен к первому входу формирователя локаторов ошибок, к второму входу которого и третьему входу комбинационного узла подключен выход формирователя элементов поля, а выход локатора ошибок подключен к четвертому входу ком-. бинационного узла, выход которого подключен к первому входу пятого сумматора, к второму входу которого подключен выход третьего элемента задержки, к входу которого подключен выход второго элемента задержки, K входу которого и второму входу второго сумматора подключены соответственно первый и второй выходы канала связи, причем выходы третьего и пятого сумматоров являются соответственно пе pBblM и в торым выходами кодека.

1338075

Г (У) (с) Фиг 5

Фиг4

)4) Составитель Г.Лерантович

Редактор Л.Маковская Техред И.Попович корректор Г,Решетчик

Заказ ÷145/56

Тираж 901 Подписное

В11ИИПИ Государственного комитета СССР по делам изобретений и открытиЯ

113035, Москва, Ж-35, Раушская наб,, д. 4/5

11р >и в дстяенпо-полиграфическое предприятие, г. Ужгород, ул. 11роектная, 1

11

I1

1 ( — у Ремам