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

(59 ГОСУД А ПО ДЕЛ ПИСАНИЕ ИЗОБРЕТВТОРСКОМУ СВИДЕТЕЛЬСТВУ(57) Изобретентельной техникзовано в цифроФормационной нретения являетнальных возмож ИЛЕДОДЛЯ ОБНАРУЖЕБОК В КОДОВОЙ ится к т быть е отно и мож ых ЭВМ адежнос я расш остейвычислииспольной иню изоб-ункциоповыше и, Цел ирение а счет еспеТВЕННЫЙ НОМИТЕТ СССРМ ИЗОБРЕТЕНИЙ И ОТНЯТИИ чения возможности контроля кодовойпоследовательности, представленной всистеме счисления, отличной от остаточных классов, а также снижение избыточности кодовой последовательности. Устройство формирует код условных вычетов. Информационная часть исходного кода числа сопровождаетсяконтрольным признаком. Исходный кодусловно разбивается на группы разрядов и тем самым представляется в виде условного числа. Расчет контрольного признака исходного кода производится по известным соотношениям.Любое искажение исходного кода по од.ному из условных оснований переводитостаток от деления исходного кода изодного диапазона в другой. Этот фактислольяуется Лля обнаруяання и ис- Сеправления ошибок. 1 ил.Изобретение относится к вычислительной технике и предназначено дляиспользования в цифровых ЗВМ повышенной информационной надежнбсти.Цельюизобретения является расширение функциональных возможностейза счет обеспечения возможности контроля кодовой последовательности,представленной в системе счисления,отличной от остаточных классов, а Отакже снижение избыточности кодовойпоследовательности.Устройство для обнаружения и ис-,правления ошибок в кодовой последовательности реализует код условных вычетов (ВУ) - код, использование которого для контроля чисел заключаетсяв следующем. Информационная часть кода числа, представленного в любойсистеме счисления, в том числе двоичной., или любого кода, представленного в виде набора двоичных цифр, сопровождается, как и при известных спо-собах контроля по модулю, контроль.ным признаком, В отличие от известных 25способов расчет контрольного признака и процесс, обнаружения и исправления ошибок заключается в следующем,Исходный код условно разбиваетсяна определенное число групп разрядов, З 0каждая из которых рассматривается какостаток от деления некоторого числаА на набор взаимно простых оснований Р Р,. ,Рп. Таким образом, исходныи кодф например двоичное число 35А, представляется в виде условногочисла АА Ву Оуу кгпредставленного в системе остаточных 4 классов, где Ф, - остатки от деления условного числа А , двоичный код которого соответствует исходному числу А, на набор условных основанийР, (1 = 1,2п)..Из теории остаточных классов известно, что если имеется остаток от деления числа .А на контрольный модуль с 1, причем50где Р и Рд , - наибольшие условные основания из их совокупности, то возможно обнаружение и исправление ошибок любой кратности в одном из остат ков ю 1 представления числа А..Таким образом, расчет контрольного признака исходного кода А производится по известным в системе остаточных классов соотношениям, считаяусловно исходный код А числом в остаточных классах.Представление исходного кода Асовместно с контрольным признакоМ М,вычисленным по правилам системы оста"точных классов в виде условного слова в системе остаточных классов (ВУкод), позволяет использовать для обнаружения и исправления ошибок тотфакт, что любое искажение исходногокода по одному из условных оснований4Р переводит условное число А издйапаэона (О, Р) в диапазон (Р, Р),где Р=,Е Р;, При этом исходное условное число А увеличивается на величину , К, где К= Р/Р, т.е. искаженное число (А ) равно:лА =А + Рй (1)Величинаопределяется величинойошибки по основанию Р , т.е величинойЬМ = с, - Ж; РВ последнем выражении М (М ) - соответственно неискаженная и искаженнаячасти исходного кода, соответствующие условному основанию Р , а знак1 х Р означает вычисление остатка отделения величины Х на Р 1, Причем, какследует из выражения (1),К = к +=5 (2)Поскольку условные основания выбираются так, чтобы неискаженное условноечисло А удовлетворяло условию А ,то тогдалА - 112 Р, (3)Зто условие позволяет организовать контроль информации с определением как места, так и величины ошибки. Для этого представим контролируемое число А с помощью ортогональных базисов так, чтоА - Сс, В (4)где В = Р,В - ортогональные базисы выбранной системы остаточных классов, удовлетворяющие условиюш, К .ш, - вес 1-го оротогонального базиса, определяемый так, что=Г, 1238078го элемента задержки 16 группы, обеспечивают передачу содержимого сумматора 27 на один из шифраторов группы 36. Регистр 1 предназначен для5приема и хранения поступившего сообщения, включая контрольный признак.Регистр 1 имеет (К+1) групп выходов,содержащих информационную часть сообщения Е Е Е и контрольныйпризнак Е ,Регистр 19 предназначендля хранения выходной информации устройства. Регистр 18 предназначен дляхранения произведения, образовавшегося на умноителе 25 Регистр 18 15имеет две группы выходов, одна из которых предназначена для хранения целой части произведения ЕРД, а дру-.гая - дробной части ЕР,Регистр 2 предназначен для хранения целой части произведения ЕРГруппа блоков памяти 11 предназначены для хранения констант видаф ш Р . Блоки памяти 12, 13 и 14предйазначены для хранения константР, Э , К соответственно.,Койстанты В хранятся в обратномкоде, а Р и К - в прямом коде. Вкачестве группы блоков памяти 11 иблоков памяти 12 - 14 могут исполь 30зоваться, например, запоминающие устройства, построенные на элементахК .155 РУ 1 или К 155 РУ 2,Накапливающий сумматор 24 предназначен для суммирования констант, погупающих с первых блоков памяти 11,и образования величины Е.Умножитель 25 предназначен. дляобразования произведений ЕР иЕРиК,В качестве умножителя может быть использоЪана, например, микросхема,40входящая в .Микропроцессорный комплектсерии КР 1802,(умножитель 16 х 16). Вцелях повышения быстродействия можетиспользоваться, например, множительное устройство, в котором использованметод ускорения умножения 2-го порядка.Схема сравнения 26 предназначенадля сравнения двух величин Э и ЕРс целью проверки выполнения условия (7).В качестве схемы сравнения, можетбыть использован например, сумматоркомбинационного типа. Так как константа 0 поступает на схему сравнения в обратном коде, то по знаку суммы можно судить о .выполнении неравенства (7). Группа узла свертки 35 и группашифраторов 36 предназначены для получения свертки по шой Р РР,величин ЕР; К и (Е -6 Ю,) соответственно.Сумматор 27 предназначен .для образования разности Е -Ы.В качестве сумматора 27 можно использовать, например, сумматор комбинационного типа при подаче на еговходы величина Ы в обратном кодес блоков свертки 35.Элементы задержки 15 и 17 и группа элементов задержки 16 предназначены для задержки выходных сигналов относительно входных на 0,5 Т; 1, Т(Т - период следования тактовых импульсов) и на время, необходимое дляисправления ошибки образования разности на сумматоре (вычитателе) 27соответственно,Устройство работает следующим образом.В исходном состоянии счетчики 20и 21, триггер 33 находятся в нулевомсостоянии. На регистр 1 поступаетпринятое сообщение - кодовая последовательность (кодограмма). С инверсного выхода триггера 33 поступает сигнал "1" на элемент И 29, разрешающийпоступление тактовых импульсов насчетный вход счетчика 2 О. По тактовым импульсам распределитель, состоящий из счетчика 20 и дешифратора 22,последовательно вырабатывает сигналы,поступающие на коммутаторы группы 3,Эти сигналы разрешают передачу инфор-мации контролируемых, разрядных групп,на которые условно "разбито" поступившее сообщение (кодограмма), на соответствующие блоки памяти группы 11.Содержимое группы разрядов сообщенияпо основанию Вслужит адресомконстанты р ш /Р в каждом из соответствующйх блоков памяти группы 11.По этим адресам (Е) в блоках памяти группы 11 осуществляется выборка констант по всем основаниям .Р 1,РР Р ; Выбранная очереднаяконстанта поступает на накапливающийсумматор 24, на котором образуется,сумма Е, Образование величины Е осуществляется по тактовым импульсам ТИ,поступающим на сумматор 24 с элемента И 29.Информация последней (К+1)-й группы передается по сигналу с последне10 Счетчик 21 имеет модуль счетаМ = К (К - количество контролируеЧ,мых групп разрядов). Показание второго счетчика 2 1 служит адресом кон 20стант В, 0и Р, хранящихся в бло-ках памяти 12, 13 и 14 соответственно. Из блоков памяти 12 и 13 выбираются константы Р и 0 . Константа Р"поступает на умножитель 25, константа В на схему сравнения 26, С поступлением первого тактового импульсас элемента И 28 на коммутатор 4 величина Е, образованная на наканлнваю- .щем сумматоре 24, поступает на первыи вход умножителя 25, на второйЗОвход которого поступает константа Рс блока памяти 12. На умножителе 25образуется произведение ЕР;, котороес его выхода поступает на регистр 18.Дробная часть величины КР с груп-З 5пы выходов регистра 18 поступает насхему сравнения 26. На схеме сравнения образуется сумма величины В,Эпредставленной в обратном коде, идробной части величины ЕР. 40.При выполнении условия (7), т.екогда в данной группе разрядов сообщения нЕт ошибки, с выхода схемы сравнения 26 (со знакового разряда сум- .матора) снимается сигнал "О", На выходе элемента НЕ 34 сохраняется сигнал "1" разрешающий поступление последующих тактовых импульсов черезэлемент И 28 на счетный вход счетчика 21 для проверки следующей группыразрядов сообщения.Проверка последующих групп разрядов кодовой последовательности осуществляется аналогичным образом. Если ошибка не обнаружится ни в однойиз групп разрядов сообщения, то показание счетчика 21 равно К, при этомна последнем (К-м) выходе дешифратого (К+1)-го выхода дешифратора 22. Этим же сиги лом устанавливаются в н иО счетчик 20 и в единичное состояние триггер 33.С инверсного выхода триггера 33 снимаетея сигнал "0" на вход элемента И 29, запрещающий поступление тактовых импульсов ТИ на счетный вход счетчика 20.Сигналами "1" с прямого выхода ,триггера 33 и с выхода элемента НЕ 34 разрешается передача тактовых импульсов через элемент И 28 на счетный вход счетчика 21. ра 23 имеется сигнал "1", Этот сигналчерез элемент. задержки 17 и элементИЛИ 32 поступает на нулевой вход триггера 33 и устанавливает его в нулевоесостояние, С инверсного выхода триггера 33 на элемент И 29 поступаетсигнал "1" разрешающий прохождениечерез нее тактовых импульсов (ТИ)для проверки следующего сообщения. Спрямого выхода триггера 33 на элементИ 28 поступает сигнал "0", по которому прекращается подача тактовых импульсов ТИ на счетный вход счетчика 5 21. Задержка сигнала, который поступает с выхода дешифратора 23 на триггер 33, осуществляется для того, чтобы на счетчик 21 был подан К+1 тактовый импульс для сброса данного счетчика в ноль. Счетчик 21, таким образом, подготовлен для процесса проверки групп разрядов следующей кодовойпоследовательности.Если на выходе схемы сравнения 26при проверке 1-й группы разрядов сообщения появляется. сигнал "1", сви детельствующий о наличии ошибки вданной группе, то тем самым разрешается прохождение тактирующего импульса по сигналу ошибки через элементИ 31 на коммутаторы 5, 6, 9, элементы И 30, ИЛИ 32, элемент задержки. 15и через элемент НЕ 34 подключаетсяпрохождение тактовых импульсов черезэлемент И 28. При этом через коммутатор 9 разрешается передача показаниясчетчика 21 в блок памяти 14, в котором происходит выборка константы Ки передача ее на умножитель 25. Крометого, через коммутатор 6 с группывыходов регистра 18 на умножитель 25через регистр 2 поступает целая частьпроизведения ЕР 1. На умножителе 25образуется произведение ЕРД К,которое записывается в регистр 18.Сигнал ошибки, пройдя через элементзадержки 15, сбрасывает счетчик 2 1и ноль, Этот же сигнал поступаетчерез элемент ИЛИ 32 на нулевой входтриггера 33.Триггер 33 устанавливается в нулевое состояние, и с его инверсного выхода на элемент И 29 поступает сиг-нал, разрешающий подачу тактовых импульсов ТИ на счетчик 20 для обработки следующей кодовой последовательности, - сообщения.Сигнал ошибки поступает также науправляющий вход коммутатора 6, и со 123807825изобретения 1фар мула Устройство для обнаружения и исправления. ошибок в кодовой последовательности, содержащее два регистра, схему сравнения, триггер, первый дешифратор, элемент ИЛИ, первый элемент Ии элемент НЕ, причем группа выходов первого регистра является группой информационных выходов устройства, о т,л и ч а ю щ.е е. с я тем, .что, с целью расширения Фуйкциональных возможностей за счет обеспечения возможности контроля кодовой последовательности, представленной в системе счисде 40 ния, отличной от остаточных классов, а также снижения избыточности кодовой последовательности, оно содеряйт накапливающий сумматор, умножитель, сумматор, четыре группы коммутаторов, два регистра, группу блоков памяти,45 группу элементов И, группу узлов свертки, группу шифраторов, группу элементов задержки, два счетчика, четыре коммутатора, два элемента за дерзки, второй и третий элементы И и второй дешифратор, причем К групп информационных входов устройства соединены с группами информационных эхрдов первого регистра, К групп выходов которого где К - число групп 55 сообщений, соединены с группами информационньцс входов соответствующих К коммутатаров первой группы и инфордержимое регистра 1 без контрольного признака поступает на регистр 19.Информация одной из групп выходов регистра 19 по разрешающему сигналу с выхода дешифратора 23 поступает через соответствующий коммутатор 8 группы на вход сумматора 27, Результат свертки содержимого регистра 18 поступает на другой вход сумматора 10 27. Разрешающий сигнал с дешифратора 23 через. соответствующий элемент задержки 16 группы поступает на управляющий вход соответствующего коммутатора 10 группы. По этому сигналу 15 образовавшаяся на сумматоре 27 раз- ность поступает на шифраторы 36 групп, осуществляющие свертку по сосоответствующему мопулю, с шифратора группы 36 величина. (Е - ьо 1 Р пос3 3 тупает на соответствующую группу разрядов регистра 19, после чего в регистре 19 хранится исправленная инФормация. мационным входом первого коммутатора,. группа выходов контрольного признакапервого регистра соединена с группойинформационных входов (К+1)-го коммутатора первой группы, выходы коммутаторов первой группы соединены с адресными входами соответствующих блоков памяти группы, выходы которыхсоединены с информационными входами накапливающего сумматора,. выходы которого соединены с информационными входами второго коммутатора, выходы которого и выходы второго. регистраподключены к первой группе информационных входов умножителя, выход которого соединен с информационным входомтретьего регистра, первая и вторая группь выходов которого соединены сгруппой информационных входов третьего коммутатора и с первой группой инФормационных входов схемы сравнениясоответственно, а также с группамиинформационных; входов коммутаторовФвторой группы, выходы которых соедииены с входами соответствующих узлов свертки группы, выходы которых соединены с первой группой информационныхвходов сумматора, выходы которого соедицены с информационными входами коммутаторов третьей группы, выхбды которых через соответствующие шифра- , торы группы соединены с К-группами информационных входов четвертого регистра, К групп выходов которого соединены с соответствующими группами информационных входов коммутаторов четвертой группы, (К+1)-я группа выходов четвертого регистра является группой информационных выходов устройства, тактовый вход которого соединен с первыми входами первого, второго и третьего элементов И, выход первого элемента И соединен с входом синхронизации накапливающего сумматора и счетным входом первого счетчика, разрядные выходы которого соединены с информационными входами первого дешифратора, выходы которого с первого по (К+1)-й соединены с управляющими входами соответствующих коммутаторов первой, группы, а (К+1)-й выход первого дешифратора соединен с вхо" дом сброса первого счетчика и единичным входом триггера, инверсный и прямой выходы которого соединены с вторыми входами первого и второго элементов И соответственно, выход второгоэлемента И соединен с управляющим12 1238078 НИИПИ Заказ 3293/50 Тираж 67 Подписное оизв,-полигр. пр-тие, г. Ужгород, ул. Проек 4 входом второго коммутатора и счетнымвходом второ,",:о счетчика, разрядныевыходй которого соединены с адресными входами первого и второго блоковпамяти и с информационными входамивторог 6 дешифратора и четвертого коммутатора, выходы которого соединеныс адресными входами третьего блокапамяти, выходы которого и выходы пер Ового блока памяти соединены с второйгруппой информационных входов умножителя, группа выходов третьего блокапамяти соединена с второй группойинформационных входов схемы сравнения, выход которой соединен с вторымвходом третьего элемента И и черезэлемент НЕ с третьим входом второгоэлемента И, выхоц третьего элементаИ соединен с управляющим входом первого, второго и третьего коммутаторов,с первым входом элемента ИЛИ, с первыми входами элементов И группы и через первый элемент задержки с входом сброса второго счетчика, выходы второго дешифратора с первого .по К-й соединены свторыми входами,соответствующих элементов И группы, с управ/ ляющими входами соответствующих коммутаторов четвертой группы и череб соответствующие элементы задержки группы с управляющими входами соответствующих коммутаторов третьей группы, выходы элементов И группы соединены с управляющими входами соответствующих коммутаторов второй группы, К-й выход второго дешифратора через второй элемент задержки соединен с вторым входом элемента ИЛИ, выход которого соединен с нулевым входом триггера, группа выходов первого коммутатора соединена с К+1-й группой информационных входовчетвертого регистра.