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

) (1) 51)5 Н 03 М 13 00 его,ОПИСАНИЕ ИЗОБРЕТЕНИЯ каждом из остатков по аниям, упрощения струк быстродействия устрой во содержит входы 1 и ых и контрольных разр нтов ИЛИ, блок 4 элем ра по модулю в бочим основ и повышения ва. Устройс информацион блок 3 элем урыт 2 до нГОСУДАРСТВЕННЫЙ КОМИТЕТПО ИЗОБРЕТЕНИЯМ И ОТНРЫ 7 ИЯМПРИ ГКНТ СССР АВТОРСКОМУ СВИДЕТЕЛЬСТВ(56) Авторское свидетельство СССРВ 960823, кл. С 06 Р 11/08, 1980.Авторское свидетельство СССРВ 1238078, кл. С 06 Р 11/08, 1984.(54) УСТРОЙСТВО ДЛЯ ОБНАРУЖЕНИЯ ИИСПРАВЛЕНИЯ ОПИВОК В КОДОВОЙ ПОСЛЕВАТЕЛЬНОСТИ(57) Изобретение относится к вычислительной технике и может быть использовано в цифровых ЗВМ повышенной информационной надежности. Целью изобретения является расширение функциональных возможностей за счет контроля тов сравнения, блок 5 элементов ИЛИ, блок 6 памяти, группу 7 регистров, группу 8 блоков памяти, пирамидальный сумматор 9, группу О коммутаторов, группу 11 блоков памяти, блоки 12 и 13 элементов ИЛИ, блок 14 памяти, блок 15 сравнения, элемент НЕ 16, элемент И 17, элемент 18 задержки, элемент ИЛИ 19, элемент И 20, элемент ИЛИ 21, блок 22 модульной свертки, блок 23 памяти, дешифратор 24, умно- житель 25, блок 26 памяти, коммутатор 27, информационные и сигнальный выходы 28 и 29. Устройство обнаружения позволяет определить количество возникших ошибок, Если в пакете ичфор- сЯ мации имеется ошибка такой кратности, что превышается возможность устройства по исправлению, то исправление не производится, если кратность ошибки С не больше допустимой, то она исправляется, и скорректированная информация выдается параллельным кодом. Таким образом, на выход устройства поступает только неискаженная информация; 1 ил.Изобретение относится к вычислительной технике и может быть испольщовано в цифровой ЭВМ повышенной информационной надежности.Целью изобретения является расширение функциональных воэможностей эасчет контроля по модулю в каждом изостатков по рабочим основаниям, упрощения структуры и повышения быстродействия устройства.На чертеже представлено предлагаемое устройство.Устройство содержит входы 1 и 2информационных и контрольных разрядов, блок 3 элементов ИЛИ, блок 4элементов сравнения, блок 5 элементов ИЛИ, блок 6 памяти, группу 7 регистров, группу 8 блоков памяти, пирамидальный сумматор 9, группу 10коммутаторов, группу 11 блоков памяти, блоки 12 и 13 элементов ИЛИ,блок 14 памяти, блок 15 сравнения,элементы НЕ 16, И 17, элемент 18 задержки, элементы ИЛИ 19, И 20,ИЛИ 21, 25блоки модульной свертки 22 и памяти 23, дешифратор 24, умножитель 25,блок 26 памяти, коммутатор 27, информационные 28 и сигнальный 29 выходы, 30Устройство для обнаружения и исправления ошибок и кодовой последовательности реализует код условных вычетов (ВУ-код) в сочетании с контролем по модулю, использование кото 35рого для контроля чисел заключаетсяв следующем. Информационная частькода числа, представленного в любойсистеме счисления, в том числе двоичной, или любого кода, представленно го в виде набора двоичных цифр, сопровождается, как и при известныхспособах контроля по модулю, контрольным признаком и процесс обнаружения и исправления ошибок заключаетсяв следующем.Исходный код условно разбиваетсяна определенное число групп разрядов, каждая из которых условно рассматривается как остаток от делениянекоторого числа А на набор взаимнопростых оснований Р 1%Р 1,рп Таким образом, исходный код, напримерисходное числФ А, представляется ввиде условного числа А55А = Ы Ы,.,Ы),в системе остаточных классов, гдеМ; - остатки от деления условногочисла А , двоичный код которого соот ц) Ри,где Р - наибольшее условное основание из их совокупности, то возможноисправление ошибок любой кратностив одном из остатков представлениячисла А при условии, что известно,по какому иэ оснований Р:,(1=1,п)произошло искажение. Исправление может осуществлятьсяпо формуле л Мисп = )1; 60(11 Р.где х 1 - вычисление остатка от де)Р;ления х на Р8;я - остаток по основанию Р; -исправленный;М; - остаток по основанию Р,в котором произошло искажение;64) - величина ошибкиВ свою очередь Ь Ы; определяется из выражения: Йм; е РД 1- - ., (2) где Р - диапазон представления чисел в системе остаточных классов с заданными основаниями Р. (1=1,п)й1 2 - величина, определяемая по фор- муле п(2 =- -Д,(3) где 1 х 1 - вычисление дробной частивеличины х;Ы, -(4)Р 1 Р;Обнаружение ошибок осуществляется путем введения контроля по модулю 1 в каждой из -х групп (=1,п) и введением остатка Ы,1 по контрольному основанию с 1, который используется ветствует исходному числ А на набор условнь)х оснований Р .=1,и).Иэ теории остаточнь)х классов известно, что если меется остаток от деления числа А на контрольный модуль, причем16334 как при обнаружении, так и при исправлении ошибокПредставление исходного кода А совместно с контрольным признаком М. = = 4 и в, вычисленным по Ву-коду, позволяет испольэовать для обнаружения ошибок тот факт, что любое искажение исходного кода по одному иэ условных оснований Р; переводит условное чис 1 О ло А из диапазона ( 0,9 ) в диапазон ( У вР), гдеи Р - величины рабочего и полного диапазонов представления чисел в системе остаточных классов соответственно, т.е. если будет выполняться неравенство.А У, (5) то А искажено.Из теории системы остаточных классов известно, что 20 Х, с(;В;(б)25 где В; - ортогональные базисы выбранной системы остаточных классов, удовлетворяющих условиюшРВр Эгде Р - диапазон представления чиселв СОК.После несложных преобразований, с учетом (4) и (3) неравенство (5) примет вид12 ) --Ч 30(7) Это условие реализуется в предлагаемом устройстве для обнаруженияошибок с использованием ВУ-кода. 40Для увеличения вероятности обнаружения ошибок и для определения номера искаженной группы (д = 1,и), вкоторой произошло искажение, вводится контроль по модулю 1 в каждой из 45групп представления. Обозначим черезг - разрядность 1, тогдаг = Д 1 од 1,гдеУ - вычисление ближайшего50большего целого У.Тогда общее количество разрядов 1отводимых под контроль по модулю 1,определяется какОв ги7где и - число контролируемых групп,а общая избыточность 0 0 + 1 оаа 3+ 1 97 6Группа 8 блоков памяти предназначена для табличного вычисления велиь; в,чинпо приходящей на адресныевходы величине Ы; . Пирамидальныйсумматор 9 выполняет вычисление сум - о(; ш;мы - в, дробная часть которой:4 Р;подается на блок 15 сравнения, предназначенный для сравнении ее с числом 1/Ч, которое постоянно хранитсяв блоке 14 памяти, и выдачи сигналаошибки, выявленной контролем с испопьзованием Ву-кода.Блок 23 памяти предназначен длявыбора величины Р по номеру 1, поступившему на его адресный вход. Умножитель 25 перемножается на величину Р; с числом 2,сформированным навыходе пирамидального сумматора 9 иподает результат на вход блока 26памяти.Устройство работает следующим образом.В исходном состоянии на выходахгруппы 11 блоков памяти номера группотсутствуют, поэт му возбуждается ну-,левая шина дешифратора 24 и этот сигнал разрешает запись информации свхода 1 через блок 3 элементов ИЛИв регистры группы 7Поступающая информация может быть верной, можетиметь одну или более ошибок. Рассмотрим по порядку все возможные варианты,Рассмотрим работу устройства, когда полученная информация не искажена,Кроме регистров группы 7, входнаяинформация по К-разрядной шине совходов 1 поступает на блок 22 модульной свертки, где вычисляются ее свертки по модулю 1, которые в блоке 4элементов сравнения сравниваются сисходными свертками, полученными пог-разрядным шинам с входов 2. Таккак по условию ошибок нет, то на всехвыходах блока 4 будет логический ноль.При этом возбуждается первый выходблока 6 памяти, сигнал с выхода которого имеет единичный уровень и подается на входы элементов И 7 и 20. В устройстве производится и конт, роль с использованием ВУ-кода. Для этого информация с выходов регистров группы 7 подается на адресные входы группы 8 блоков памяти. По этим адресам из группы 8 блоков памяти выби 1633497П 1;раются величиныкоторые складыРваются на пирамидальном сумматоре 9 идробная часть полученной суммы пода 5ется на блок 15 сравнения, где онасравнивается с пороговой константой1/с 1, выбираемой иэ блока 14 памяти,При отсутствии ошибок на выходе блока 5 сравнения будет логический ноль,10Иннертируясь на логическом элементеНЕ 16, этот сигнал подается на входлогического элемента И 17, на второйвход которого подана логическая единица с первого выхода блока 6 памяти.На выходе логического элемента И 17формируется единичный сигнал, которыйпроходит через логический элементИЛИ 19 и подается на первый вход коммутаторов группы 10. Этот сигнал подключает выходы всех регистров группы 7 ко всем информационным выходамустройства 28 и информация выдаетсяпотребителю,Второй вариант - принятая информация содержит одну ошибку. На одном из выходов блока 4 сравнения появляется логическая единица, свидетельствующая о наличии ошибки вданной группе разрядов.30Сигнал единичного уровня, поступающий на второй вход коммутаторагруппы 10, разрешает подключение выхода соответствующего регистра группы 7 к входам блока 12 элементов ИПИ,обеспечивает выборку номера искаженной группы 1 из группы 11 блоков памяти и, попадая на адресный входблока 6 памяти, возбуждает его второй выход. С второго выхода блока 6 40памяти сигнал логической единицыпоступает на элемент 18 задержки,где задерживается на время, необходимое для исправления ошибки и записи исправленного остатка в соотнетствующий регистр группы 7,Исправление происходит следующимобразом.На входы блока 12 элементов ИЛИпоступает искаженная группа, а на входы блока 13 элементов ИЛИ поступает ее номер 1.Номер группы 1, пройдя через блок 13 элементов ИЛИ, поступает на адресный вход блока 23 памяти, из которого выбирается величи 55 ца условного основания Р;, поступающая на дешифратор 24, возбуждая соот;нетстнующий вход, а такыре на адресные входы блока 26 памяти, где является частью адреса. Тем,временем навыходе пирамидального сумматор,; 93 н 1уже формируется величина 2 =р,;.лкоторая, поступая на вход умножителя 25, перемножается с величиной Р;и целая часть этого произведения поступает на адресные входы блока 26памяти, где также составляет частьадреса. Заключительной частью адресаблока 26 памяти является код искаженного остатка, который попадает на адресный вход этого блока памяти, приходя через блок 12 элементов ИЛИ, Таким образом, Формируется адрес блока 26 памяти, из которого на основании формулы (1) выбирается неправильная группа И, через коммутатор 27,открытый при отсутствии сигнала с выхода логического элемента ИЛИ 21, подается на входы всех регистров группы 7. Но запись происходит тольков -й регистр, так как сигнал логической единицы появляется на 1-м выходе дешифратора 24 и, проходя черезэлемент ИЛИ блока 5, разрешает запись только в этот 1-й регистр группы 7После записи исправленного остатка н 1-й регистр группы 7 на выходеэлемента 18 задержки появляется сигнал, который, проходя через элементИЛИ 19, подается на вход коммутаторон группы О. Коммутаторы группы 1 Ообеспечивают подключение выходов регистров группы 7 к информационным выходам 28 устройства. Таким образом,исправленная информация выдается потребителю.Если при контроле по модулю 1 вблоке 22 модульной свертки обнаруи 1ваются дне и более ошибок, то возбуж 9дается третий выход блока 6 памяти.Сигнал единичного уровня на его выходе проходит через логический элемент ИЛИ 21 и подается на сигнальныйвыход 29 устройства, Уровень логической единицы на этом выходе свидетельствует о невозможности исправленияустройством принятой информации, Вэтой ситуации на выходе блока 26 памяти возникает случайная информация,которая может, при записи ее в регистры группы 7, вызвать дополнительныеискажения принятого сообщения, Дляисключения подобной ситуации уровеньлогической единицы подается на управляющий вход коммутатора 27 и запреща 633497 0ет передачу информации через цего на входы блока элементов ИЛИ 3.В случае когда обнаруживающие способности кода по модулю недоста 5 точны для обнаружения ошибки, но ошибка обнаруживается при контроле ВУ-кодов, устройство работает аналогично. В этой ситуации на вьгходе блока 5 сравнения будет сигцал логичес О кой единицы, который в блоке 6 памяти возбудит первый выход. Оба этих сигнала подаются на вход элемента И 20, единичный сигнал с выхода которого поступает на вход логического элемен-15 та ИЛИ 21 и с его выхода на вход коммутатора 27 и сигнальный выход 29 устройства.Формула изобретенияУстройство для обнаружения и исправления ошибок в кодовой последовательности,содержащее первый блок памяти, выходы которого подключены к 25первым входам блока сравнения, выход которого подключен непосредственно к первому входу первого элемента Ии через элемент НЕ к первому входувторого элемента И, группу регистров,выходы которых подключены соответственно к первым входам коммутаторовгрупп, второй блок памяти, выходы которого подключены к первым входам умножителя, дешифратор, блок модульнойсвертки, элемент задержки, первуюгруппу блоков памяти, третий блокпамяти, коммутатор, первый элементИЛИ, о т л и ч а ю щ е е с я тем,что, с целью расширения функциональных40воэможностей за счет контроля по модулю в каждом иэ остатков по рабочимоснованиям, упрощения структуры и повышения быстродействия устройства,в него введенЬц первый-четвертый блоки45элементов ИЛИ, второй элемент ИЛИ, пирамидальный сумматор, вторая группаблоков памяти, четвертый блок памяти и блок элементов сравнения,первые входы которых являются входами контрольных разрядов устройства,первые входы первого блока элементов ИЛИ объединены с входами блокамодульной свертки и являются входами информационных разрядов устройства, выходы бс ка модульцой свертки подключены соответственцо к вторымЪ входам элементов сравнения блока, выходы которых подключены к вторым входам коммутаторов группы, входам блоков памяти второй группы и входам четвертого блока памяти, первый выход которого подключец к вторым входам первого и второго элементов И, выходы которых подключены состветственцо к первым входам опцоцмеццых эле - ментов ИЛ 1, цгорой выход четвертого блока памяти через лемецт задержки подключен к второлу вхою второго элемента ИЛ 1 выход которого подклю чец к третьил 1 входам коммутаторов группы, первые ц вторые выходыкоторых подключены соответственно к входам второго блока элементов ИЛИ и являются ццформациоцнымц выходами устроиства, выходы блоксв памяти второй группы подключены к входам третьего блока элементов ИЛИ, выходы которого подключены к входам второго блока памяти, первым входам третьего блока памяти и входам дешифрато-.тора, нулевой вых ц которого подключен к первыл 1 входа; клементов ИЛИ четвертого блока, остал.,ные выходы дешифратора подключены к вторым входам соответствующих элементов ИЛИ четвертого блока, выходы которых подключены к первым входам соответствующих регистров группы, входы и выходы блоков памяти первой группы подключены соответственно к выходам регистров группы и входам пирамидального сумматора, выходы которого подключены к вторым входам блока сравнения и умножителя, выходы которого и выходы второго блока элементов ИЛ подключены соответственно к вторым и третьим входам третьего блока памяти, выходы которого соединены с информационными входами коммутатора, третий выход четвертого блока памяти подключен к второму входу первого элемента ИЛ 1, выход которого является сигнальным выходом устройства и подключен куправляющему входу коммутатора, выход которого подключен к вторым входам элементов ИЛИ первого блока, выходы которых подключены к вторым входам регистров группы.