Декодер сверточного кода

 

Изобретение относится к вычислительной технике и технике связи. Его использование в системах передачи информации позволяет повысить достоверность декодирования и быстродействие. Декодер содержит распределитель 1 информации, распределитель 3 блоков символов, формирователи 5,6 операционных векторов, умножитель 7 на матрицу декодирования, анализатор 14 текущего индекса декодирования и блок 15 памяти результатов декодирования. Благодаря введению буферного накопителя 2, тактового генератора 4, буферного блока 8 памяти, параллельно-последовательного преобразователя 9 кода, регистра 10 сдвига, элементов 11,12 И и блока 13 коммутации в декодере обеспечивается исправление одиночной ошибки независимо от ее местоположения. 2 з.п. ф-лы, 2 ил.

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

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

РЕСПУБЛИК

Я0 1й2ШЩ9 (gg 4 Н 03 М 13/12

ОПИСАНИЕ ИЗОБРЕТЕНИЯ

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

ПО ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМ

ПРИ ГКНТ СССР

К A ВТОРСКОМУ СВИДЕТЕЛЬСТВУ (21) 4402086/24-24 (22) 19.01.88 (46) 07.11.89. Бюл, I 41 (72) Н..Н. Левин и Л.Н. Угрик (53) 681,325:621.394.14 (088.8) (56) Некоторые вопросы теории кодирования,/Под ред. Э.Л. Блоха и N.Ñ. Пинскера. — М.: Мир, 1970, с. 142-165.

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

11 - 1403971, кл. Н 03 М 13/12, 1986. (54) ДЕКОДЕР СВЕРТОЧНОГО КОДА (57) Изобретение относится к вынислительной технике и технике связи.

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

2 достоверность декодирования и быстродействие. Декодер содержит распределитель 1 информации, распределитель

3 блоков символов, формирователи 5, 6 операционных векторов, умножитель

7 на матрицу декодирования, анализатор 14 текущего индекса декодирования и блок 15 памяти результатов декодирования. Благодаря введению буферного накопителя 2, тактового генератора 4, буферного блока 8 памяти, параллельно-последовательного преобразователя 9 кода, регистра 10 сдвига,. элементов И 11,12 и блока

13 коммутации в декодере обеспечивается исправление одиночной ошибки независимо от ее местоположения, 2 э.п. ф-лы, 2 ил.

1520669

1234 анализ

34567 8

4 5 6 7 8 9 н ц или

7 8 9 10 11 12

10 11 12 13 14 15

° °, а °

55

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

Цель изобретения — повьппение достоверности декодирования и.быстродействия.

На фиг ° 1 приведена функциональная схема декодера; на фиг.2 " пример выполнения анализатора текущего индекса декодирования.

Декодер сверточного кода содержит распределитель 1 информации, буфер ный накопитель 2, распределитель 3 блоков символов, тактовый генератор

4, первый 5 и второй 6 формирователи операционного вектора, умножитель 7 на матрицу декодирования, буферный блок 8 памяти, параллельно-последовательный преобразователь 9 кода, регистр 10 сдвига, первый 11 и второй

12 элементы И, блок 13 коммутации, анализатор 14 текущего индекса декодирования и блок 15 памяти результатов декодирования.

Распределитель 1 информации включает в себя коммутатор 16, первый 17 и второй 18 дешифраторы.

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

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

Формирователи 5 и 6 операционного вектора представляют собой шестиразрядные регистры сдвига.

123456

В (1) слева представлены отрезки исходного сообщения, поступающие на умножитель 7, справа - отрезки, получаемые в результате, умножения на матрицу декодирования. Цифры представляют собой номера позиций декодируемых знаков. Каждая нечетная строка соответствует обработке по первому каналу, каждая четная — по второму„ Каждая пара позиций в последовательностях, расположенных спра-.

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

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

Регистр 10 сдвига содержит три последовательные зоны, каждая из которых состоит из трех двухъячеечных сегментов (т.е. в данном случае этот регистр имеет восемнадцать разрядов).

Блок 13 коммутации включает в себя три коммутатора 19.

Анализатор 14 текущего индекса декодирования содержит (фиг.2, компа-. раторы 20, элементы И 21 и элемент

ИЛИ 22 и имеет информационные 23 и тактовый 24 входы и выходы 25.

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

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

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

0669 б

ЗО

5 152 второй вектор истинен при условии (в „= В ) и (В1 = в ) и (в

В ) ИЛИ,В < = В ) И (В1 ф Вэ) и (В ф Вэ), или (В, В ) и (В В ) и (в P в ); третий Вектор истинен

ПРИ (В, ф В И (В $ ф В 3) И (В ф в ); в случае (в, Ф вд) и {в, в )

3 и (в Ф в э ) выделить неискаженный вектор иэ трех анализируемых невоз-. можно. В то же время очевидно, что искажены два вектора из трех, следовательно, четвертый вектор истинен.

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

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

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

1 информации начала сообщения из канала связи оно дешифрируется первым дешифратором 17 { дешифратором начала). В случае дешифрации на одном из выходов последнего формируется импульс, запускающий блок 4 тактового генератора, а на другом выходе — импульс, обеспечивающий срабатывание коммутатора 16, который подключает вход декодера к распределителю 3 блоков и буферному накопителю 2.

Первых три символа сообщения запоминаются в буферном накопителе 2 и одновременно через распределитель

3 блоков символов поступают на первый формирователь 5 операционного вектора, Вторая тройка символов через распределитель 3 поступает как на первый 5, так и на второй 6 формирователи операционного вектора.

Работа распределителя 3 тактируется частотой Р,, поступающей от генератора 4 и соответствующей скважности поступающих из канала символов. Таким образом, через шесть тактов на умножитель 7 поступает опера- ционный вектор, сформированный в формирователе 5. В этот момент умно-. житель 7 тактируется частотой F,„/6, поступающей с одного из Выходов бло ка 4. В момент считывания первого вектора из формирователя 5 на его управляющем выходе генерируется управляющий импульс, переключающий Выход генератора 4, на котором имеется тактовая частота F „ /3, на вход тактирования умножителя 7. Таким образом, начиная с второго Вектора, умножитель 7 тактируется частотой

F Ä/3. Это связано с тем, что каждьnl последующий вектор поступает на вход умножителя с дискретностью в три знака см. (1)), Второй операционный вектор формируется из последовательности знаков с четвертого по девятый и поступает на вход умножителя 7 с формирователя 6 и т.д.

С выхода умножителя 7 преобразованный вектор в параллельном коде-. поступает одновременно в первую зону буферного блока 8 и на преобразователь 9 кода числа иэ параллельного в последовательный. В буферном блоке 8 две зоны обеспечивают запоминание двух первых последовательностей, поступающих от умножителя 7. Такое запоминание необходимо для последующего декодирования первых знаков сообщения, Преобразователь 9 преобразует код из параллельного в последовательный и посимвольно Выдает его в регистр

10. Первый шестизначный отрезок, поступающий в регистр 10 от преобразователя 9, записывается в третьей зоне. После поступления второго отрезка, первый перемещается во вторую зону, а в третьей записывается второй и т.д. После записи третьего отрезка регистр 10 заполняется полностью, При этом в первой зоне находится первый, во второй зоне — второй, в третьей — третий. После того, как в первой ячейке сегмента 1Н регистра 10 окажется знак первого отрезка, на последовательном выходе регистра !О формируется импульс, поступающий на один из входов второго элемента И 12. С приходом на второй его вход импульса с частотой F r/3, поступавшего от генератора 4, на выходе элемента И 12 формируется импульс, который является считывающим для сегмента 1К, 2С и 3Н в регистре

10. В этот момент в сегменте 1К находятся два знака конца первого отрезка, a сегменте 2С вЂ” два знака сере1520669 дины второго, в сегменте ЗК вЂ” два знака конца третьего отрезка. Эти знаки считываются в компараторы 20 акализатора 14 текущего индекса декодиро5

;вания, где происходит их сравнение между собой по укаэанному алгоритму.

После сравнения в анализаторе 14

1. в соответствии с алгоритмом выбора неискаженных знаков происходит 10 формирование разрешающего импульса, который в зависимости от результатов сравнения и совпадений поступает на управляющий вход одного из трех коммутаторов 19 блока 13. Поскольку анализатор 14 тактируется частотой F, второй элемент И 12 . частотой F /3, а знаки в регистре

10 сдвига продвигаются с тактовой .частотой 2F, то к моменту йоступ- 20 ления на один иэ коммутаторов 19 блока 13 разрешающего импульса от, анализатора 14 в зоне 1 регистра 10 записан второй отрезок, в зоне 2— третий, в зоне 3 — четвертый. При 25 этом в сегменте 1К,регистра 10 находятся два последних знака второго отрезка, в сегменте 2С вЂ” два средних знака третьего отрезка, в сегменте ЗК вЂ” два последних знака четвер- 30 того. Таким образом, в накопителе 2 считаны знаки только из того отрезка, который считаетея истинным согласно приведенному алгоритму (см. (1) ). До момента окончания сообщения декодер работает аналогичным обраII зом. После поступления сигнала Конец сообщения".второй дешифратор 18

:.(дешифратор конца) формирует управляющий сигнал, который одновременно 40 поступает на коммутатор 16 распределителя 1 информации, на считывающий вход буферного накопителя 2 и декодера от ..канала связи, считывание трех первых ранее записанных знаков 45 сообщения происходит в последние . три ячейки формирователей 5 и 6 для формирования последнего вектора. После того, как умножитель 7 сформирует из последнего вектора последний отрезок и тот через преобразователь 9 поступит в регистр 10, по сигналу от элемента И ll также через преобразоВатель 9 в регистр 10 переписываются и два первых отрезка сообщения, ранее находившиеся в буферном блоке 8.

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

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

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

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

l, Декодер сверточного кода, со.— держащий распределитель информации вход которого является входом декодера, а первый выход соединен с ин формационнЫм входом распределителя блоков символов, первый и второй..выходы которого подключены к информационным входам соответственно первого и второго формирователей операционного вектора, информационные выходы которых соединены соответственно с первыми и вторыми информационными входами умножителя на матрицу декодирования, анализатор текущего .. индекса декодирования и блок памяти результатов декодирования, о т л ич а ю шийся тем, что, с целью повышения достоверности декодирования и быстродействия декодера, в него введены буферный блок памяти, параллельно-последовательный преобразователь кода, регистр сдвига, блок коммутации, первый и второй элементы

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

15206б9

2. Декодер по п.1, о т л и ч а— ю шийся тем, что распределитель информации содержит коммутатор, первый и второй дешифраторы, входы которых объединены с информационным входом коммутатора и являются входом . распределителя, первый выход первого дешифратора соединен с первым управля>ощим входом коммутатора, выход которого является первым выходом распределителя, второй выход первого дешифратора является вторым выходом распределителя, выход второго дешифратора подключен к второму управляющему входу коммута40

И, третий выход распределителя информации соединен с первым входом первого элемента И и управляющим входом буферного накопителя выходы которо I 5 го подключены к установочным входам формирователей операционного вектора, управляющий выход первого формирователя операционного вектора соединен с управляющим входом тактового генератора, третий выход которого подключен к первому тактовому входу умножителя на матрицу декодирования и вторым входам первого и второго элементов И, выходы которых соединены с управляющими входами соответственно буферного блока памяти и регистра сдвига, четвертый выход тактового генератора подключен к второму тактовому входу умножителя на матри2У цу декодирования, выходы которого соединены с информационными входамивыходами блока буферной памяти и информационными входами параллельнопоследовательного преобразователя 25 кода, выход которого подключен к информационному входу регистра сдвига,-параллельные выходы которого соединены с одноименными информационными входами блока коммутации и анали- З< затора текущего индекса декодирования, выходы которого подключены к соответствующим управляющим входам блока коммутации, выходы которо го соединены с входами блока памяти результатов декодирова— ния. тора и является третьим выходом распределителя.

3. Декодер по п.1, о т л и ч а ю шийся тем, что анализатор текущего индекса декодирования содержит первый — восьмой элементы И, элемент ИЛИ и первый — третий компараторы, первые информационные входы первого и второго компараторов соответственно объединены и являются первыми информационными входами анали-затора, вторые информационные входы первого и первые информационные входы третьего компараторов соответственно объединены и являются вторыми информационными входами анализатора, вторые информационные входы второго и третьего компараторов соответственно объединены и являются третьимн информационными входами анализатора, тактовые входы компараторов объединены и являются тактовым входом анализатора, прямой выход первого компаратора соединен с первыми входа-. ми первого и третьего элементов И, инверсный выход первого компаратора подключен к первым входам второго и четвертого элементов И, прямой выход второго компаратора соединен с вторыми входами первого и второго элементов И, инверсный выход второго компаратора подключен к вторим входам третьего и четвертого элементов И, выходы первого — третьего элементов И соединены с первыми входами соответственно элемента ИЛИ, пятого и шестого элементов И,выход, четвертого элемента И подключен кпервым входам седьмого и восьмого элементов И, прямой выход третьего компаратора соединен с вторым входом седьмого элемента И, инверсный выход третьего компаратора подключен к вторым входам пятого, шестого и восьмого элементов И, выходы шестого и седьмого элементов И соединены с вторым и третьим входами элемента

ИЛИ, выход которого является первым выходом анализатора, выходы пятого и восьмого элементов К являются соответственно вторым и третьим выходами анализатора.

1520669 ПВ"

2ХЗ

Составитель О. Ревинский

Техред Л. Сердюкова

Корректор Т. Малец

Редактор И. Шмакова

Заказ 6769/57 Подписное

ВНИИПИ Государственного комитета по изобретениям и открьггиям при ГКНТ СССР

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

Тираж 884

Производственно — издательский комбинат "Патент", г. Ужгород, ул. Гагарина, 101