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

ОПИСАНИЕ ИЗОБРЕТЕНИЯ Союз Советски Социалистически Реснублмк(22) Заявлено 193679 (21) 2807659/18-24 (53 М. КЛ. С 06 Г 11/10 с присоединением заявки йо(23) Приоритет Государственный омитет СССР ао делам изобретений и открытий(0888) Дата опубликования описанмя 070981 1 Заявител 54) УСТРОЙСТВО ДЛЯ ОБНАРУЖЕНИЯ И ИСПРАВЛЕНИЯ ОШИБОК В СИСТЕМЕ ОСТАТОЧНЫХ КЛАССОВбыКжи а нааниКоды О Изобретение относится к вычислительной технике и может быть использовано при построении надежных вычислительных устройств, функционируюЮих в системе остаточных классов (СОК),Известны устройства для обнаружения и исправления информации в СОК содержащие систему обнаружения и коррекции ошибок определение местопопо-. 1 О жения ошибок производится с помощью контроля по четности, а обнаруженные ошибки корректируются методом вычетов), предсказывающее устройство устройство вычетов, вычислитель четности, вычислитель вычетов, блок сравнения, блок коррекции данных и вычислитель значения ошибки 11 и Г 21 .Наиболее близким техническим решением к изобретению является устройсТВо для обнаружения и исправления ошибок в СОК, содержащее выходной регистр, выходные сигналы которого .подаются на входы хранения констант.С выходов блока хранения констант коды вычетов по контрольным основанйям поступают на входы сумматоров по конт,рольным основаниям, выходы которых подключены ко входам блока анализ нуль остатка по контрольным основ ям и блока констант исправления. констант, предназначенные для вычисления неточных рангов чисел, поступают иа входы одноразрядных сумматоров, находящихся в блоках вычисления неточноГо ранга чисел, выходы блоков подсоединены к сумматорам по контрольным основаниям, входы блока хранения констант исправления, подключены к выходному регистру, а выходы ко входам сумматоров по контрольным основаниям и входам блоков вычисления неточного ранга 133.Недостатком таких устройств является то, что при высокбм бЫстродействии в нйх предусматриваются большие по величине контрольные основания,астродействяе снижено при небольших о величине контрольных основаниях. роме того,они не позволяют обнарувать больше одной ошибки.При величине контрольного основания Ри т РР . номеру интервала, в котором ошибКа перемещает неправильное число,однозначно соответствует величина и местоположение ошибки.При величине контрольного основанияРп, 7 рп 9 л+ номеру интервала соответствует не более двух ошибок.Большая величина контрольного основания нежелательна так как при862143 йечто иное как сложение правйльиогочисла с ортогональным числом.При условии (3) минимальным ортогональным числом будет число а максимальным ортогональным числомбудет число1 й 3-1Таким образом, при сложении правильного числа с любым ортогональным .числом подсистемы сумма (т.е. неправильное число Х буцет больше величины Р и меньше диапазона Й ),В то же время любая одиночнаяошибка выводит правильное число издиапазона (4). Следовательно, условие5 п 140 (7)где)- номер интервала по модулюР и+также будет признаком наличия ошнб-.ки.В надсистеме возможными ошибкамимогут быть числаСОО,М 00) (В)Каждая из этих ошибок может помес-.тить неправильное число в интервал,который определяется формулой1д 1 Ф 1 Р,и,О+ Р (щ "н)+б У Л) где 5 может принимать значение 0или 1 Г 11 .Но так как мы оперируем числами, представленными в подсистеме; и предполагаем, что ошибка может возникнуть лишь в одном основании подсистем, то возможными ошибками могут быть лишь числа0О,ЬЬ;,0О), (Ю)Таким образом, количество возможных ошибок при переходе к подсиСтемам уменьшается.Приведем теперь алгоритм коррекции одиночных ошибок.Вычисляется номер интервала 1 по модулю для каждой из подсистем.сли 3;4=0(=,2, и+1), то ошибки не произошло. Если же какое-нибудь Д е 9, где 3 Ф О, 1 ( оп+1, то ошибка йроизошла. Это значит, что ошибка переместила правильное число к Ъс,сЕк,д,Кэ) в 8 -й интеРвал и ошибка находйтся в-й строке таблицы возможных ошибок подсистемы.Так как ошибка уже обнаружена,вычисляем номер интервала в надсистеме по модулю Рп+ . Получим у,:В .Это значит, что ошибка переместила правильное число А в 5 -й интервал и ошибка находится в Б -й строке., К-м столбце таблицы возможных ошибок надсистемы.Находим пересечение полученных альтернативных совокупностей, которое однозначно определит величину и местоположение ошибки, так как в К-м столбце 6 -й строки может быть всего одно число (ошибка), вводящее Ь в нулевой интервал. Вычитая из принятого числа А ошибкудЬФЭ, получимправильное число А.На фиг. 1 изображена структурная; схема устройства для обнаружения иисправления ошибок в СОП,Оно содержит(п+) группу входныхрегистров порегистров 1 в группе(м 1) блоков 2 анализа, которые осуществляют проверку условия (6), коммутатор 3, который при наличии сигнала с выхода блока 10 пропускает искаженный операнд надсистемы интервала,первый б блок памяти, первый элементИ 7, второй блок памяти 8, второйэлемент И 9 и блок определения вида15 ошибки 10.На. фиг. 2 изображена схема блокаопределения вида ошибки 10, содержащего (о+) элементов И 11-14 (прнв -4), на которые подключаются соот 20 ветствующие прямые и инверсные выходы блоков 2, первый элемент ИЛИ 15 нвторой элемЕнт ИЛИ 16, входы которого соединены с выходами элементов И11"14.Выход элемента ИЛИ 16 (признакодиночной ошибки) соединен со входомэлемента НЕ 17. Входы(+) -го элемента И 18 соединены с выходами элемента НЕ 17 и элемента ИЛИ 15. Выход(и +1)-го элемента И 18 является признаком фйногократная ошибка",На фиг. 3 изображена структурнаясхема блока 2 анализа.Она содержит входные регистры 19,в которых хранится принятое число,схему 20 преобразования нз СОК в полиаднческий код, схему сравнения 21,регистр 22, констант, в котором хранится константа Р 1., записанная в полиадическомфкоде, и инвертор 23.40 Блок 2 анализа работает следующимобразом. Принятое число преобразуется в полиадический код блоком 20.Схема сравнения 21 сравнивает полиадическнй код числас полиадичес 4ким кодом числа Р 1При с;Р; выходной сигнал появится на выходе схемы сравнения, приА 3 Р - на выходе инвертора 23.Устройство работает следующим образом.Принятое. число через регистры 1поступает на блоки анализа 2,. которыепроверяют .выполнение условия (6).Если условие (6) выполняется для всехоснований надсистемы, то на всех прямых Выходах блоков.2 появляются выходные сигналы, которые поступают навход элемента И 9. Выход под сигналэлемента И 9 является признаком правильности числа. Если же в. каком К -мя основании надсистему произошла ошибнка, то на инверсном выходе К -го блока 2 появится выходной сигнал, который пройдя через блок 10, явитсяпризнаком наличия одиночной ошибки,Я Сигнал "Одиночная ошибка" даст раз30:(0,0,2),60=(0,0,4),90= 0,0,6)120=(0,0,1),150=(0,0,3),180=(0,0,5)35=(0,5,0),70=(0,4,0),105=(0,3,0) 45140=(0,2,0),175=(Ою 1,0),42=(2,0,0)84=(4,0,0),126=(1,0,0),168=(3,0,0) Таблица возможных ошибок в подсистеме имеет вид 50а д.1. 5 2 5,4 4 3,4 б3,2 11,2 3 1 5 2,4 3 4 5 б 1,33 7 8621решение блоку 4 на вычисление номераинтервала по основанию Р , а также разрешение на прохождение искаженного операнда через коммутатор З.Вторым разрешакщим сигналом для коммутатора 3 будет сйгнал с инверсного вцхода к -го блока 2.Блок 5 вычисляет номер интервалапо основанию Ф для искаженного числак=(дк к;оЬк 4) . На выходе блока5 появится чйсло 6., которое являетая номером интервала в подсистемеи дает разрешение на выборку альтер"нативной совокупности из 8 -й строкитаблицы второго блока памяти 8,В то же время на выходе блока 4появится число 5 , которое являетсяномером интервала надсистемы. Выход-.ной сигнал с инверсного выхода к -гоблока 2 и число ь дадут разрешениена выборку альтернативной совокупности иэ З -й строки К -Го столбца.таблицы первого блока памяти.Элемент И 7 из полученных альтернативных.совокупностей выявляетвеличину и местоположение ошибки,ко-торую необходимо вычесть из принятого числа,Если выходные сигналы появятся надвух и более инверсных выходах блоков 2, то блок 10 выдаст .сигнал"Многократная ошибка"., который не З 0пропустит через коммутатор 3 искаженные операнды и не даст разрешениена вычисление номера интервала бло.ку 4Рассмотрим в качестве примера ра- З 5боту устройства при Р = 26, Р 0= 27,Р 9: 29, Р = 20358, Р - 702,т 1 = 9,13 т пЬ= 5 ф В = 7047 у Ь= 3510.Основаниями подсистемы выбираемчисла Ч,= 5, Я = б, = 7, а99 лЯ5.6.7 = 210,40Возможными ошибками будут числа 43допустим, что правильное число500 = (бг 14 ю 7) = (1 фОбт 42 юОк2,1,0) исказилось и вместо числа Априняли число А = (0,0,6,4,2,0,2,1,0)Вычислимо, для числа .,(2,1,0), получим ус = О.Таким образом, мы установили,чтоошибка произошла по первому основаниюнадсистемы. Величине = 3 соответствует следующая альтернативная совокупность: ь,.;- 4, ЬА х З,ьб = 4,А= б в таблице.Вычисляем у для принятого числаА, получим 7= 2. Находим н таблицеошибки, выводящие число во 2-й интервал по первому оснонанию надсистемы,совпадающие с.полученной альтернативной совокупностью. Такой ошибкойможет быть только ЬА 1= 4. ВычтемА А ц= 4 иэ принятого числа и получимперноначальное число, т.е. исправимошибку.Таким образом, с применением новых блокон и связей увеличивается быстродейстние устройства и уменьшается величина контрольного основания.Это обусловлено тем, что вычисление позиционных характеристик в сис-темах низкого порядка и с малыми повеличине основаниями не затруднено ин предложенном алгоритме, который реализует данное устройство, позиционную характеристику числа в надсистеме нужно вычислять только один раз.ИсПользование предлагаемого устройства обеспечит .существенный экономический эффект при серийном его использовании.Формула изобретенияУстройство для обнаружения и исправления ошибок н системе остаточных классов, содержащее(и 1) группу входных регисторов по 1 регистров в группе, первый и второй блоки вычисления номера интервала, первый и второй .блоки памяти, причем выходы входных регистров всех групп являются входами устройства, ныходы входных .регистров всех групп соединены с соответствующими входами первого блока вычисления номера интервала, выход которого соединен с адресным входом блока первого блока памяти, выход нтороГо блока вычисления номера интервала соединен с адресным входом второго блока памяти, о т л и ч а ющ е е с я тем, что, с целью увеличения быстродействия в устройство введены(п 1) блоков анализа, коммутатор, блок опредеЛения вида ошибки, первый и второй элементы И, причем выходы входных регистров каждой группы соеВ 62143 10 9динены с соответствующими входами со- элементов И н(первого элемента ИЛИответствующего блока анализа,извест- образуют входы устройства, выходыные выходы каждого блоха.аиалйз 4 сое- первого элемента И, с первого по идинены с соответствующим входом:груп- соединены с соответствующим входомпы управляющих входов ксеечутатора;с. второго элемента ИЛИ, выхсд кОторОГОсоответствующим входом блока опрейте- з через элемент ИЕ соединен с первымленин вида ошибки и с соответствую входом (п+ю) -го элемента И, выход ко-.щим входом группы адресных входов . торого является первым выходом блопервого блока памяти, выход которого , ка, выходы первого и второго элемеи-.соединен с первым входом первого эле- тов иЛИ соединены соответственно сомента и, выход второго блока памятивторым входом (в+1)"го элемента или)соединен со вторым входом первого и со вторым выходОм блока.элемента и, выход которого является 3 уст:буйство по и. 1, о т л ипервым выходом, устройства, прямые ч а ю щ е е с.я тЕм, что блок айнливыходы всех блоков анализа соединены за содержит вторые регистры, блокс соответствующими входами второго преобразования из. СОХ в полиадическнйэлемента И, выход которого является. ф код, схему сравнения, регистр конвторым выходом устройства, первый вы-. стант, в ннвертор причем выходы реги-,ход блока определения вида маибкн яв- стров соединены со входами преобразоляется третьим выходом устройства , вателя из СОИ в полиадический код,второй выход блока ооределення вида выход которого. соединен.с первым эхо .ошибки соединен с управляющим входом 29 дом схемы сравнения второй вход котокоммутатора, с управляйхцнм входом . рой соединен с выходой регистра конпервого блока вычисления:номера ин- . стант, вваищ:сВеьн сравнения черезтервала, и является четвертым выхо- инввртор еМднйен с первым выходомдом устройства, выходы всех вторых. блока, ньиве: схем сравнения являет"регистров соединены с соответстВующи- д ся вторым выходом блока,ми инФормационными входамикоюцюта- Воточникн инФормацин,тора выходы которого соединены со прннятыв ва внимание прн экспертизевходами второго блока вычисления. нб- . 1 Валент сВи 9 3659089,мера интервала. кл 253- 153, 1977,2. Устройство по п. 1, о т л и-,2, . Йатейт Франции В 2191700,ч а ю щ ее с я тем, что блок оп-. кл. 6 06 Г. 11/10, 1976.ределения вида Ьшнбок содержит(п+) . 3;. Ааторское свидетельство СссРэлементов И, первый и второй. элемен 393950, кл. ь Об Р 11/10, 1974ты ИЛИ, и элемент НЕ причем, .входы (прототип).862143 Составитель И,Сигактор Л.утехина Техред С. Мигунов в ктор О, Бил аказ Филиал ППП "Патент", г. Ужгород, ул. Проектная 13/4 3 Тираж 74 ВНИИПИ. Государствен по делам изобрете 113035, Москва, Ж