Устройство для обнаружения ошибок в несистематическом сверточном коде

СОВЕТСКИХСОЦИАЛИСТИЧЕСКИХРЕСПУБЛИК А 1 1)5 НОЗМ 1 Я ОБРЕТ ПИ К АВТ 8)тельство СССРМ 13/12, 29.03,89.тельство СССРМ 13/12, 1987,ДЛЯ ОБНАРУЖЕНИИСТЕМАТИЧЕСКО сится к вычислитель- связи. Его использоГОСУДАРСТВЕННЫЙ КОМИТЕТПО ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМПРИ ГКНТ СССР ОМУ СВИДЕТЕЛЬ(21) 4471959/24 (22) 07,07.88 (46) 07,07.91. Бюл. М (72) Б.М.Злотник (53) 621,391,256 (088 (56) Авторское свиде М 1580567, кл. Н 03Авторское саиде М 1443180, кл. Н,ОЗ (54) УСТРОЙСТВО ОШИБОК В НЕС СВЕРТОЧНОМ КОД (57) Изобретение от ной технике и техни вание в системах передачи данных позволяет повысить достоверность декодирования и упростить устройство за счет сокращения числа операций. Устройство содержит блок 1 оперативной памяти, коммутирующий элемент 7, элемент ИСКЛЮЧАЮЩЕЕ ИЛИ 9, элемент И 10, блок 12 синхронизации и счетчик 13 импульсов, Благодаря введению формирователя 2 адресов записи, ключевых элементов 3, 4, счетных триггеров 5, 6, коммутирующего элемента 8, элемента 11 задержки, дещифратора 14 и блока 15 постоянной памяти в устройстве реализуется новый алгоритм. 3 ил,Изобретение относится к вычислительной технике и технике связи и может быть использовано в системах передачи данных,На фиг,2 а - в показаны сигналы на выходах 18 - 20 блока 12 синхронизации соответственно,В основе работы устройства лежит новый принцип аналитического представления любого информационного сигнала х) несистематическогЬ сверточного кода системой нелинейных УРавнений х = 1 Ус), где ус, ус+1 - СИГНаЛЫ, ОбраэуЮщИЕ ЭЛЕМЕНтарный блок кода при скорости кода 1/2, В общем случае информация передается последовательностью элементарных блоков с длиной кодового ограничения 1, причем каждый элементарный блок состоит из и сигналов уь у+п, Из полной системы уравнений для цели обнаружения ошибки и дешифрации кода выбирают два уравнения с наименьшим числомэлементарных блоков, причем= 1, ., 2 У -3, Для кодов со скоростью передачи 1/2, в которых элементарный блок обраЗУЮт дВа СИГНаЛа УК, ус+1 С дЛИНОй КОдОВО- го ограничения ю = 3 и 5, системы уравнений имеют вид Ус+ Ус+1+ Ус+3 =Р;Ус+4 + Ус+5 =ЙУс+2 + Ус+3+ Ус+4+ Ус+5+ Ус+7 =,Ус+7+ Ус+8+ Ус+9 =4 Х 1= Р=3 Цель изобретения - повышение достоверности декодирования и упрощение устройства за счет сокращения числа операций.На фиг.1 приведена функциональная схема устройства; на фиг.2 - выходные сигналы блока синхронизации; на фиг.З - алгоритм работы устройства,Устройство содержит блок 1 оперативной памяти, формирователь 2 адресов записи, первый 3 и второй 4 ключевые элементы, первый 5 и второй 6 счетные триггеры, первый 7 и второй 8 коммутирующие элементы, элемент ИСКЛЮЧАЮЩЕЕ ИЛИ 9, элемент И 10 элемент 11 задержки, блок 12 синхронизации, счетчик 13 импульсов, дешифратор 14 и блок 15 постоянной памяти. На фиг,1 обозначены выход 16 ошибки, информационный выход 17, а также первый - третий выходы 18 - 20 блока 12 синхронизации, первые 21, второй 22, третий 23 и четвертый 24 выходы дешифратора 14.+ УК+гг + Ус+г 3 = 20 Наименьшее числоэлементарных блоков охватывают пары Уравнений: при и = 3",УР,и=3, при и= 5 Я= 6, Если и= 7, то= 11,если и = 12, то= 19, Два отобранных уравнения называют проверками и Обозначают25 Я 1, Яг, На фиг.З для сверточного кода с длиной кодового ограниченИя и = 3 приведеныпоследовател ь ности ин форм ацион н ых сигналов и соответствующих им элементарныхблоков: беэ ошибок у и с ошибками у, а также30 показаны операции обнаружения ошибок идешифрации кода, х - последовательностьдешифрованных символов. Последовательность у определяется двумя порождающимимногочленами:35 91 = х; + х+1+ х+г: 9 г = х + х+г,Операции обнаружения ошибок и дешифрации коДа выполняют следующим образом; запоминаютпоследовательныхэлементарных блоков принятой последо 40 вательности у; выбирают из них путемпоследовательного считывания сигналыуь , Ур, входящие в проверки 31, Яг;. проверяют на четность число единиц всигналах у, входящих в каждую провер 45 ку; если число единиц четно, значение 31или Бг устанавливают равным О, если число единиц нечетно, значение 31 или Ягустанавливают равным 1; после полученийзначений 31, Яг проверяют выполнение ра 50 венства 31 = Яг = Я; если равенство имеетместо на ипоследовательных элементарных блоках, ошибок нет и значениеинформационного сигнала х устанавливают равным значению Я; если 31 ФЯг, сигнал55 х заменяют символом стирания е, фиксируя наличие ошибок. Выполнение (ю - 1)- кратного равенства необходимого дляповышения надежности дешифрациикода.10 Устройство работает следующим образом,Принимаемая. последовательность у элементарных блоков сигналов поступает в блок 1 оперативной памяти. Два проверочных уравнения в виде номеров позиций, в которых расположены ненулевые проверяемые сигналы, хранятся в блоке 15 постоянной памяти. Проверочные уравнения хранятся в виде прошивок ПЗУ по адресам, соответствующим номерам позиций проверок. Все адреса считываются последовательно в течение каждого интервала элементарного блока и начало считывания (проверки) определяется импульсом частоты следования элементарных блоков. Блок 12 синхронизации обеспечивает синфазное считывание сигналов с блока 1 памяти и дешифратора 14 для формирования проверок )1, 52.Блок 12 синхронизации выдает последовательности тактовых импульсов на первый выход 18, импульсы с частотой следования элементарных блоков - на второй выход 19, импульсы адресов считывания - на третий выход 20 (фиг,2), Импульсы на выходе 19 обеспечивают запись входных данных в блок 1. Счетчик 13 ведет последовательный счет импульсов с выхода 20 до тех пор, пока дешифратор 14 после формирования последнего адреса считывания сбросит счетчик 13 в исходное состояние сигналом на четвертом выходе 24. Дешифратор 14 выдает на первые выходы 21 последовательность чисел-адресов считывания блока 15, Блок 15 выдает адреса считывания блока 1, Одновременно дешифратор 14 по выходам 22 и 23 управляет ключевыми элементами 3 и 4, которые направляют выходные данные блока 1 в триггеры 5 и 6, соответствующие двум проверкам Я 1, Я 2. Выходы триггеров 5 и 6 соединены через коммутирующие элементы 7 и 8 с элементами 9 и 10, При 51 Ф 52 элемент ИСКЛЮЧАЮЩЕЕ ИЛИ 9 возбуждает выход 16, формируя сигнал ошибки, если 51 = 32, элемент И 10 возбуждает выход 17, Элементами 7 и 8 управляют импульсы, подфазированные в элементе 11 задержки,Работу устройства рассмотрим на примере несистематического сверточного кода с длиной кодового ограничения и = 5 и скоростью кода 12. Предполагают,. что передана последовательность У = 00000110101101100000000,а принята последовательностьУ = 000000101000100000000000Ц -элементарный блок (ЭБ) 20 25 30 35 40 45 50 Символы У поступают в блок 1 в ячейки памяти с адресами О, 1, 211, причем левые символы ЭБ поступают раньше, чем правые, За интервал каждого ЭБ блока 12 синхронизации выдает 12 импульсов для формирования адресов считывания, которые в процессе работы счетчика 13 и дешифратора 14, а также блока 15 выдают в следующем порядке адреса считывания блока 1 и сигналы пропускания (П) и непропускания (Н) ключевых элементов 3 и 4. Адреса считывания блока 101234567891011Ключевые элементы 3ППНППНППНН Н Н4ПППНППНППН П ПК концу интервала ЭБ триггеры 5 и б хранят результаты проверок 51, 52, До записи в блок 1 ЭБ, содержащего первую единицу в последовательности У, триггеры 5 и б в конце каждого ЭБ хранят сигналы 51 = 52 = О, Импульс ЭБ на выходе 19 блока 12 считывает сигналы Я 1, Я 2 через элементы 7 и 8 и, так как 51 =- Яз =- О, то на выходах 16 и 17 на интервале ЭБ появляются сигналы,со значением О,После записи сигналов ЭБ, содержащего первую единицу в последовательности У, по адресам элементов 10 и 11 блока 1 к концу интервала ЭБ в триггере 5 хранится сигнал со значением О, в триггере 6 - сигнал со значением 1, на. выходе 17 - сигнал со значением О. Единичный сигнал на выходе 16 фиксирует обнаружение ошибки.Высокая эффективность рассмотренного алгоритма проверена и подтверждена на сверточном коде со скоростью 1/2 и с длиной кодового ограничения 1 = 12, в котором две проверки 51, 52, охватывающие 19 элементарных блоков сигналов у, обнаруживали ошибки кратностью, превышающей гарантированную кратность в 14 ошибок. Для того же, чтобы обнаружить ошибки любой, даже небольшой кратности по алгоритму Витерби, необходимо в этом коде последовательно генерировать 2046 элементарных блоков для того, чтобы произвести сравнение только с одним принятым элементарным блоком,Формула изобретения Устройство для обнаружения ошибок в несистематическом сверточном коде. содержащее блок оперативной памяти, блок синхронизации, счетчик импульсов, первый коммутирующий элемент, элемент И и элемент ИСКЛЮЧАЮЩЕЕ ИЛИ. выход которого является выходом ошибки устройст1662012 управляющим входам первого и второго ключевых элементов и входу обнуления счетчика импульсов, выходы блока постоянной памяти соединены с вторыми адресны ми входами блока оперативной памяти,выход которого подключен к информационным входам первого и второго ключевых элементов, выходы которых соединены с входами одноименных счетных триггеров, 10 выходы которых подключены к информационным входам одноименных коммутирующих элементов, выход элемента задержки соединен с управляющими входами коммутирующих элементов, первые и вторые вы ходы первого и второго коммутирующихэлементов подключены соответственно к первым и вторым входам элемента ИСКЛЮЧАЮЩЕЕ ИЛИ и элемента И, выход которого является информационным выхо дом устройства,Фиг,Г а а У а а а жибао а а а а ююбаг Обнаружено ошибка Е с с я а Неопределенные а Зб Зб Зб зноченияРигЗ Составитель О. Реви Техред М,Моргентал ий Корректор С,актор Н, Рогулич и аказ 2137 Тираж 458 ВНИИПИ Государственного комитета по изоб 113035, Москва, Ж, Раьский комбинат "Патент", г, Ужгород, ул.Гагарина, 101 изводственно-из ва, о т л и ч а ю щ е е с я тем, что, с целью повышения достоверности декодирования и упрощения устройства за счет сокращения числа операций, в устройство введены ключевые элементы, элемент задержки, второй коммутирующий элемент, счетные триггеры, дешифратор, блок постоянной памяти и формирователь адресов записи, выходы которого соединены с первыми адресными входами блока оперативной памяти, информационный вход которого является входом устройства, первый - третий выходы блока синхронизации подключены соответственно к входу формирователя адресов записи, входу элемента задержки и счетному входу счетчика импульсов выходы которого соединены с входами дешифратора, первые, второй, третий и четвертый выходы которого подключены соответственно к входам блока постоянной памяти,Подписноетениям и открытиям при ГКНТ С ская наб., 4/5