Устройство для декодирования кодов

1,"г.биСмстме. МЕвОПИСАНИЕИЗОБРЕТЕН ИЯК АВТОРСКОМУ СВИДЕТЕЛЬСТВУ 11508290 Союз Советских Социалистических Республик(22) Заявлено 12.02,74 (21) 1998325/18-24с присоединением заявки-Гвсударственныи комитет Совета Министров СССР(43) Опубликовано 30.03,76. Бюллетень145) Дата опубликования описания 02.02.77(72) Авторы изобретения А. Давыдов, Г. М, Тененгольц, В. И, Эзакели, А. Бунатян, Э. М. Гендлер и Л, В. Тепляптина Заявитель Ордена Ленина институт проблем управлен 54) УСТРОЙСТВОКОДИРОВАНИЯ КОД Изобретение относится к электронным дискретным устройствам систем автоматики, телемеханики, вычислительной техники и связи. Оно предназначено для использования в системах передачи и хранения дискретной ин формации в качестве устройства для декодирования кодов, исправляющих одиночные выпадения символов и ошибку в символе, предшествующем выпавшему. Кроме того, в том случае, когда, выпадения отсутствуют, пред О лагаемое устройство исправляет две смежные несимметрические ошибки, т. е. ошибки типа 1 -+ 0 (или наоборот). Такие ошибки возникают, например, при перфсрировании на ленту из-за неисправности в устройстве, 15 осуществляющем протяжку ленты.Известны устройства для декодирования кодов, исправляющих одиночные выпадения символов, содержащие анализатор, вход которого соединен с входом устройства, а пер вый выход - с входом схемы сравнения, Первый выход схемы сравнения подключен к первому входу блока определения вычета и к первому входу блока локализации ошибки, выход которого связан с первым входом блока коррекции, а второй выход схемы сравнения - к первому входу блока выделения информационной части сообщения, выход которого соединен с выходом блока коррекции.30 Цель изобретения - повышение исправ ляющей способности, устройства, исправление сшибки в символе, предшествующем выпавшему, и двух смежных несимметричных ошибок (в случае отсутствия выпадений).Это достигается тем, что в устройство дополнительно введены блок выделения четных н нечетных позиций, блок контроля на четность, блок определения искажений в конт. рольной части сообщения, коммутатор, эле мент И, три схемы сравнения, блок итеративного вычисления суммы, блок подсчета количества едичиц, блок вычитания, блок. определения начала пакета ошибок и блок определения вида искажения.Вход устройства соединен с,первым входом блока выделения четных и нечетных позиций и с вторым входом блока выделения информационной части сообщения, второй выход анализатора - с первым входом блока определения вида искажения и с вторым входом блока выделения четных и нечетных позиций, оба выхода которого через блок контроля на четнссть связаны с вторым входом блока определения вида искажения, а третий выход анализатора - с вторыми входамп блока слределения вычета и блока локализации ошибок и через блок определения искажений в контрольной части сообщения с третьим входом блока определения видаискажения. Первый выход схемы сравнения подключен,к первому входу блока итеративного вычисления суммы и через блок подсчета количества единиц к первому входу блока вычитания и первому входу первой дополнительной схемы сравнения, выход блока определения вычета - к вторым входам блока вычитания и первой дополнительной схемы сравнения, к входу блока определения начала пакета ошибокк первым входам коммутатора и второй дополнительной схемы сравнения и через третью дополнительную схему сравнения к четвертому входу блока определения, вида искажения, пятый и шестой входы которого связаны с выходами первой дополнительной схемы сравнения. Первый выход блока определения вида искажения соединен с третьим входом блока выделения информационной части сообщения, второй выход блока определения вида искажения с вторыми входами блока итеративного вычисления суммы, блока коррекции и коммутатора, третий вход которого подсоединен к выходу блока, вычитания, а четвертый и пя. тый входы - к выходам блока определения начала пакета ошибок. Второй вход и первый и второй выходы второй дополнительной схемы сравнения подключены соответственно к первому выходу и третьему и четвертому входам блока итеративного вычисления суммы, второй выход которого соединен с первым входом элемента И, третий выход второй дополнительной схемы сравнения - к второму входу элемента И, выход которого соединен с шестым входом коммутатора, а выход коммутатора - к третьему входу блока коррекции, выход которого соединен с выхо,дом устройства. 10 15 20 25 Зо 35 40 45 50 55 60 65 Функциональная схема предлагаемого устройства представлена на чертеже, где: 1 анализатор; 2 - блок выделения информационной части сообщения; 3 - схема сравнения; 4 - блок определения вычета; б - блок локализации ошибки; б - блок коррекции;7 - блок выделения четных и нечетных позиций; 8 - блок контроля на четность; 9 - блок подсчета. количества единиц; 10 - блок определения искажений в контрольной части сообщения; 11 - блок итеративого вычисления суммы; 12 - блок вычитания; 13 - первая дополнительная схема сравнения;14 - третья дополнительная схема сравнения; 15 - вторая дополнительная схема сравнения; 1 б - элемент И, 17 - блок определения начала пакета ошибок; 18 блок определения вида искажения; 19 - коммутатор; 20, 21 - выходы блока 7; 22 - выход Больше схемы 13; 23 - выход Меньше схемы 13; 24 - первый выход схемы 1 б (выход Больше); 25 - второй выход схемы 15 (выход Меньше); 2 б - третий выход схемы 1 б (выходРавно); 27, 28 - выходы блока 17; 29 - выход блока 18, выдающий информацию о виде искажения. Устройство работает следующим образом.На вход устройства из канала связи или из запоминающего устройства подается последовательность двоичных символов. Эта последовательность в момент поступления В канал связи или В запоминающее устройство имеет структуруХ ХХ 1 г Х 1 г Х/г+3/г+т2 Х lг+т+2 т":Х 1 г+т+4 Х+т+5 10ЗДЕСЬ Хг . НЮКОТОРЫИ ДВОИЧНЪИ СИМВОЛ Х 1х 1, - информационные символы; хгг+з, , х+;+2 - двоичная запись наименьшего неотрицательного вычета 1 обобщенного весаХг последовательности информационных г=символов (вычет определяется по модулю 2, 4 - ); х.1.т+4 и х+,+; - суммы по модулю два информационных символов, стоящих на нечетных и четных позициях соответственно.Принимаемая устройством двоичная последовательность одновременно поступает в анализатор 1 и в блоки 2 и 7. Анализатор 1 анализирует й+г+6-й символ последовательности. Когда этот символ равен 1, то выпадений нет и возможны только несимметрические ошибки. Если указанный символ равен 0, то произошло одиночное выпаде. пие символа.,Рассмотрим работу устройства в обоих отмеченных случаях.П е р в ы й сл уч а й. 1(+г+6-Й символ принятой последовательности равен единице.Первые й+г+5 символов принятой последовательности с выхода анализатора 1 посту. пают в блоки 4, б и 10. В блоке 10 проверяетсяпротивоположны ли друг другу значения Й+г+2-го и Й+г+3-го символов последовательности. Если эти значения совпадают, то имеют место ошибки в контрольной части сообщения, а в информационной части ошибок нет. Если указанные значения противоположны, то й+г+2-Й символ последовательности не искажен, и ошибки в информационной части возможны. Информация о результате сравнения Й+г+2-го и Й+г+3-го символов и информация о результате анализа й+г+6-го символа гиоступают соответственно из блока 10 и анализатора 1 в блок 18. Блок б выделяет из сообщения информационную часть, в которой возможны ошибки, и передает ее в блок б. Блок 4 подсчитывает наименьший по абсолютной величине вычет з выражения1 гт- Х гХ+ Х 1 г, 2, 2- ПО МОдуЛЮ 2 тг= 1=1(х, - 1-й символ принятой ,последовательности). Вычет з с выхода блока 4 подается в блоки 12 и 17, в схемы 13, 14, 1 б и в коммутатор И Для рассматриваемого случая важна работа блока 17, схемы 14 и коммутаТаблица 1 й х О о % Я Я оо Условия, при которыхимеет место искажение данного вида Вид искажения 1, Одна ошибка типа 1-+О, 51)0, 5=1 Одна ошибка типа О5,(0, 5=1 Две смежные несимметрические ошибки типа 1-О Две смежные несимметрические ошибки типа О - 1 5,(0, 5=2 тора 19. Схема 14 вычет з, сравнивает с ну-. лем, и информация о результате сравнения поступает из схемы 14 в блок 18, В блоке 17)5, - 1 вычисляются две величины:8,иЭти величины соответственно с выходов 27 и 28 блока 17 поотупают в коммутатор 19. Блок 7, получив из анализатора 1 информацию о результате анализа й+г+6-го символа, выделяют среди первых Й символов принимаемой последовательности символы, стоящие на четных и нечетных, позициях. Четные символы попадают на выход 20, нечетные символы - на выход 21. Кроме того, на,выход 20 проходит 1 з+г+5-й символ принимаемой последовательности, а на выход 21 й+г+4-й символ. Блок 8 вычисляет две суммы по модулю два: з, и зз, причем з, - сумма двоичных символов, появившихся на выходе 20 блока 7, зз - сумма двоичных символов, появившихся на выходе 21 блока 7. Значения з, и зз передаются из блока 8 в блок 18.,В блоке 18 на основе ниформации, поступающей из блоков 8 и 10, из анализатора 1,и схемы 14, определяется вид искажения. При этом логические блоки, входящие в состав блока 18, реализуют следующий алгоритм.Поскольку 1 з+г+6-й символ, принятой последовательности равен единице, то,выпаде,ний нет. Вычисляется сумма з=з,+зз. Ошибок в ниформационной части нет, если выполняется любое из условий: значения й+г+2-го и й+г+3-го символов принятой последовательности совпадают; з=з,=О; з,=О, зФ О; з,с О, э=О,Сигнал об отсутствии ошибок в информационной части поступает из блока 18 в блок 2, который выделяя первые 1 з символов принятой последовательности, выдает их на выход устройства. На этом процесс декодирования заканчивается.Если значения й+г+2-го,и Уг+г+3-го символов принятой последовательности противоположны и зО, з, эО, то ошибки в информационной части есть. Блок 18 определяет ,номер и вид искажения в информационной части в соответствии с табл. 1,Номер искажения поступает с выхода 29блока 18 в блоки 6 и коммутатор 19, Если в информационной части одна ошибка (т. е. искажение1,или 2), то коммутатор 19 про- Б пускает в блоки 6 информацию с выхода 27блока 17, т. е. /5,/. Когда в информационной части две смежные несимметрические ошибки (т. е. искажение3 или 4), коммутатор 19 пропускает в блок 6 информацию с выхода 28 1 О 1 5, - 1блока 17 т. е. 2 /, Искаженная информационная часть сообщения, поступившая в блок 6 из блока 5, исправляется в блоке б в 15соответствии с данными, попавшими в блок 6 из блока 18 и коммутатора 19. При этом данные из коммутатора 19 рассматриваются как номер начала пакета ошибок. Исправленная информационная последовательность выдается из блока 6 на выход устройства,В то р о й сл уч ай. К+г+6-й символпринятой последовательности равен нулю.Информация из анализатора 1 на входыблоков 4, 5 и 10 не поступает. Первые 1+1 символов принятой, последовательности из анализатора 1 передаются в схему,3, которая сравнивает между собой й-й и 1+1-й символы, Если эти,символы противоположны, то ошибки в информационной части не произошло, и последовательность из схемы 3 передается в блок 2, выделяющий первые Й символов принятого сообщения, которые выдаются на выход декодирующего устройства. В случае, если Й-й и 1+1-й символы принятой последовательности совпадают, то ошибка,произошла в информационной части, и сообщение из схемы 3 передается в блоки 4, 5, 9 и 11. Блок 5 выделяет из сообщения искаженную информационную часть и передает ее в 4 О блок 6, Блок 4 подсчитывает наименьший неотрицательный вычет з, выражениягг - 1 Г- , 1 х,+ У х+,+; 2 -по модулю 2.=1 =145Этот вычет с выхода блока 4 поступает вблоки 12 и 17, в схемы 13, 14, 15 и в коммутатор 19. Для рассматриваемого случая важна работа блока 12, схем 13, 15 и коммутатора 50 19. На входы блока 12,и схемы 13, кромевычета з, подается из блока 9 число ы, равное количеству единиц в,первых символах принятой последовательности. В блоке 12 подсчитывается разность и, = з, - а - 1. Значение ао этой разности из блока 12 передается в коммутатор 19. Схема 13 сравнивает числа з, и ы, Если з,)ы, то выдается сигнал на выходе 22, а если з,(в, то появляется сигнал на выходе 23. Эти сигналы поступают в блок 18.6 О Из анализатора 1 информация о результатеанализа А+г+6-го символа принятой последовательности попадает в блоки 18 и 7. Блок 7, получив указанную информацию, выделяет среди первых Й - 1 символов принимаемой бо последовательности символы, стоящие на чет508790 выпадение символа имеет место. Факт,наличия сигналов на выходах 22, 23 означает, что на выходы схемы 13, а, следовательно, и на входы блоков 4 и 9, информация поступила, Последнее означает, что имеет место выпадение символа в,информационной части, так как в противном случае из схемы 3 в блоки 4 и 9 сигналы не подаются. Вычисляется сумма 1 О по модулю два з=згРзз, а затем определяется в соответствии с табл. 2 вид и номер искажения в информационной части (Через и; в табл. 2 обозначено количество единиц в последовательности х хх 1, расположен ных правее- 1-й позиции). Таблица 2 Условия, прн которыхилеет место искажениеданного вида Номер иска- жения Вид искажения 5=1а - 5,) 1 к Выпадение единицы, слева от которой в после.г РГдовательностп ххгх размещено понулей Выпадение нуля на -й позиции и одновременно ошибка типа С в 1 на- 1-й позиции. Номерудовлетворяет условиям:х- 1 - ( - 1) + и; = 5: где 55, если 5, с о15 - 2 л, если 5, ) п 5(Ж или5)и 5=05(У Выпадение нуля, справа от которого в последовательности х х гхвразмещено 5, единиц Выпадение единицы на -й позиции и одновременно ошибка типа 1 -+ 0 на -й позиции.Номерудовлетворяет условиям:х= О; 2 - 1+ и = 5 5 ) 1 к Отметим, что искажение вида выпадение нуля на г-й позиции и одновременно ошибка типа 1 - О на- 1-й позиции сводится к искажению5. А искажение вида квыпадение единицы на 1-й позиции и одновременно 20 ошибка типа О -+ 1 на1-й позиции сводится к искажению7. Поэтому отмеченные искажения отдельно:в таблице не рассматриваются.Номер искажения поступает с,выхода 29 25 блока 18 в блоки 11, б и коммутатор 19. Если произошло искажение6 или 8, то включается блок 11.Рассмотрим вначале работу блока 11 при наличии искажения6. В этом случае блок зО 11 итеративно вычисляет сумму вида ср = = - (ь - 1) +. а; йо следующему алгоритму.В последовательности х, хгх ,поочередно выбираются позиции, на которых расположены единицы. Выбор позиций осущест- З 5 вляется слева, направо. Каждая выбранная ных и,нечетных позициях, Четные символы поступают на выход,20 нечетные символы - на выход 21, Кроме того, на выход 20 проходит 1 е+г+3-й символ принимаемой последовательности, а на выход 21 - й+г+4-й символ, Блок 8, как и в предыдущем случае, вычисляет две суммы по модулю два; зг и зз - и передает значения этих сумм в блок 18. В блоке 18 на основе, информации, поступившей из блока 8, анализатора 1 и схемы 13, определяется вид искажения. При этом логические блоки, входящие,в состав блока 18, реализуют следующии алгоритм,Поскольку й+ г+ 6-й символ принятой последовательности равен нулю, то одиночное позиция рассматривается в качестве г - 1-й позиции и для каждой выбранной позиции вычисляется сумма гр(1). Значение г - 1 проходит на информационный, вход элемента б, а значение гр - в схему 15, где сравнивается со значением 5 поступивщим в схему 15 из блока 4. Если гр(г 5 то с выхода 24 схемы 15 на вход блока 11 поступает сигнал, свидетельствующий о необходимости выбрать новую позицию и вычислить для этой новой позиции сумму гр. Работа блока 11 продолжается. Если же ср(1) =5 то сигнал с выхода 2 б схемы 15 поступает,на управляющий вход элемента 1 б. Элемент 1 б открывается и пропускает значение- 1 на вход коммутатора 19. Работа блока 11 закончена.Рассмотрим теперь работу блока 11 при наличии искажения8. В этом случае блок 11 итеративно вычисляет сумму вида 1(г) =2;+ д; по алгоритму, аналогичному алгоритму вычисления суммы р(1). Отличие35 40 45 50 в том, что в качестве- 1-й позиции выбираются позиции с символом 0, а сигналом для продолжения работы блока 11 и выбора новой позиции является сигнал с выхода 2 б схемы 15. Выбор позиций при вычислении суммытакже осуществляется слева направо, а значение- 1 через элемент 1 б также,поступает в коммутатор 19. Коммутатор 19, получив,из блока 18 информацию о виде искажения, пропускает в блок б либо число а, (в случае искажения5), либо число ь - 1 (при искажениях6, 8), либо число Я, (если, искажение7). Блок б, приняв от коммутатора указанные числа,и получив из блока 1 В номер искажения, осуществляет коррекцию, искаженной информационной части сообщения, поступившей в блок б,из блока б. Коррекция проводится в соответствии с табл. 2. Исправленная информационная последовательность выдается,из блока 6 на выход устройства. Формула изобретения Устройство для декодирования кодов, содержащее анализатор, вход которого соединен с входом устройства, а первый выход - с входом схемы сравнения, первый выход схемы сравнения соединен с,первым входом блока определения вычета и с первым входом блока локализации ошибки, выход которого соединен с первым входом блока коррекции, второй выход схемы сравнения соединен с первым входом блока выделения,информационной части сообщения, выход которого соединен с выходом блока коррекции, о тл ич а ю щ е е с я тем, что, с целью повышения исправляющей способности устройства, в него дополнительно введены блок выделения четных,и нечетных позиций, блок контроля на четность, блок определения искажений в контрольной части сообщения, коммутатор, элемент И, три схемы сравнения, блок итеративного вычисления суммы, блок подсчета количества единиц, блок вычитания, блок определения начала пакета ошибок и блок определения вида искажения, причем вход уст,ройства соединен с первым входом блока выделения четных и нечетных позиций и с вторым входом блока выделения информацион 1 О 15 20 25 зо ной части сообщения, второй выход анализатора соединен с первым входом блока определения вида искажения и с вторым входом блока, выделения четных и нечетных позиций, оба выхода которого через блок контроля на четность соединены с вторым входом блока определения вида искажения, третий выход анализатора соединен со вторыми .входами блока определения вычета и блока локализации ошибки ,и через блок определения искажений в контрольной части сообщения с третьим входом блока определения вида искажения, первый выход схемы сравнения соединен с,первым входом блока итеративного вычисления суммы и через блок подсчета количества единиц с первым входом блока вычитания и с,первым входом первой дополнительной схемы сравнения, выход блока определения вычета соединен с вторыми входами блока вычитания и первой дополнительной схемы сравнения, со входом блока определения начала пакета ошибок, с первыми входами коммутатора,и,второй дополнительной схемы сравнения и через третью дополнительную схему сравнения с четвертым входом блока определения вида искажений, пятый и шестой входы которого соединены с выходами первой дополнительной схемы сравнения, первый выход блока определения вида, искажения соединен с третьим входом блока выделения информационной части сообщения, второй выход блока определения вида искажения соединен с,вторыми входами блока итеративного вычисления суммы, блока ,коррекции и коммутатора, третий вход которого соединен с выходом блока вычитания, а четвертый и пятый входы соединены с выходами блока определения начала пакета ошибок второй вход и первый и второй выходы второй дополнительной схемы сравнения соединены соответственно с первым выходом и третьим,и четвертым входами блока итеративного вычисления суммы, второй выход которого соединен с первым входом элемента И, третий выход второй дополнительной схемы сравнения соединен с вторым входом элемента И, выход которого соединен с шестым входом коммутатора, выход коммутатора соединен с третьим, входом блока коррекции, выход которого соединен с выходом устройства.Корректор Л. Орлова Редактор И. Грузова Тираж 830 ПодписноеСовета Министров СССРи открытийнаб., д. 4/5 Заказ 1086/1649 Изд. Мв 1789 ЦНИИПИ Государственного комитета по делам изобретений Москва, ЖРаушская