Устройство для обнаружения и исправления ошибок в системе остаточных классов Советский патент 1981 года по МПК G06F11/10 

Изобретение относится к вычислительной технике и может быть использовано при построении надежных вычис лительных устройств, функционирукядих в системе остаточных классов (СОК). Известны устройства для обнаружения и исправления информации в СОК содержащие систему обнаружения и коррекции ошибок определение местопоЛогжения ошибок производится с помощью контроля по четности, а обнаруженные ошибки корректируются методом вычетов) , предсказывающее устройство устройство вычетов вычислитель четности, вычислитель вычетов, блок срав нения, блок коррекции данных и вычислитель значения ошибки tO и Г23 . Наиболее близким техническим решением к изобретению является устройство для обнаружения и исправления ошибок в СОК, содержащее выходной регистр, выходные сигналы которого.подаются на входы хранения констант.С выходов блока хранения констант коды вычетов по контрольным основаниям поступают на входы сумматоров по конт .рольным основаниям, выходы которых подключены ко входам блока анализа на нуль остатка по контрольным основаниям и блока констант исправления. Коды констант, предназначенные для вычисления неточйЬйс рангов чисел, поступают на входы одноразрядных сумматоров, находящихся в блоках вычисления неточного ранга чис(вл, выходы блоков подсоединены к сумматорам по контрольным основаниям, входы блока хранения констант исправления, подключены к выходному регистру, а выходы..ко входам сумматоров по контрольный основаHUsiM и входам блоков вычисления неточного ранга Сз). Недостатком таких устройств является т6| при высоком быстродействии -в них предусматриваются.большие по величние контрольные основания,а быстродействие снижено при небольших по величине контрольных основаниях. Кроме того,оНн не позволяют обнаруживать больше одной ошибки. При величине контрольного Ьснования , aPnlf n-л номеру интервала, в котором ошибка переметает неправильное число, однозначно соответствует величина и местоположение ошибки. При величине контрольного основания Pf,, номеру интервала соответствует не более двух ошибок. Большая величина контрольного осцованнй Нежелательна так как при ЭТОМ затрудняется построение таблиц основных арифметических операций. При величине контрольного основания номеру интервала соотвэт ствует альтернативная совокупность ошибок, для стягивания которой возни кает необходимость несколько раз вычислять номер интервала, что снижает быстродействие устройства. Целью, изобретения является повьвие ние быстрЬдействия устройства. Эта цель достигается тем, что в устройство для обнаружения и исправления ошибок СОК, содержащееh+i груп пу входных регистров по 7 регистров в группе, первый и второй блоки вычисления номера интервала, первый и второй блоки памяти, причем выходы входных регистров всех групп являются входами устройства, выходы входных регистров всех групп соединены с соответствующими входами первого блока вычисления номера интервала, выход которого соединен с .адресным вх дом первого блока памяти. Выход второго блока вычисления номера интервала соединен с адресным входом второго блока памяти. В устройство введены п+н блоков анализа, коммутатор блок определения вида ошибки, первый и второй элементы И. Выходы входных регистров каждой группы соединены с соответствующими входами соответст-вующего блока анализа, инверсные выходы каждого блока анализа соединены с соответствующим входом групп управляющих входов коммутатора с соответствующим входом блока определения вида ошибки и с соответствующи входом группы гцдресных входов первого блока памяти, выход которого соединен с первым входом первого элемента И. Выход второго блока памяти соединен со вторым входом первого элемента И, выход которого является первым выходом устройства. Прямые выходы всех блоков анализа соединены с соответствугацими входами второго элемента И, выход которого является вторым выходом устройства. Первый выход блока определения вида ошибки является выходом устройства, второй выход соединен с управляющим входом коммутатора с управляю щим входом первого блока вычисления и является четвертым выходом устройства. Выходы всех регистров соединены с соответствугацими входами коммутатора, выходы которого соединены со входами второго блока вычисления номера интервала. Блок определения вида ошибки .содержит п-и элементов И, первый и второй элементы ИЛИ и элемент НЕ.. Входы элементов И и первого элемента ИЛИ образуют входы устройства, выходы первого элемента И с первого .по п соединены с соответствующим входом второго элемента ИЛИ, выход которого через элемент НЕ соединён с первым входом (n+-i; -го элемента И выход которого является первым выходом блока. Выходы первого и второго элементов ИЛИ соединены соответственно со вторым входом (n+-f -го элемента ИЛИ и со вторым выходом блока. Блок анализа содержит входные регистры, блок преобразования из СОК в полиадический код, схему сравнения, регистр констант и инвертор. Выходы регистров соединены со входами преобразователя из СОК в полиадический код, выход которого соединен с первым входом схема сравнения, второй вход которого соединен с выходом регистра констант. Выход схемы сравнения через инвертор соединен с первым выходом блока, выход схемы сравнения является четвертым выходом блока. Алгоритм работы устройства для обнаружения и исправлений ошибок в СОК основывается на применении многоступенчатой СОК. Изобретение предназначено для обнаружения и исправления ошибсж в двухступенчатых стандартных непозиционных кодах. Такой код строится следуницим образом. Выбираются основания СОК, удовлетворяющие заданному рабочему диапазону Р-,,Ра-.Ри (1) Вводится контрольное основание Prt , большее, чем каждое рабочее pc-i нование (в дальнейшем будем называть эти основания основаниями надсистеWbj) . Затем выбираются основания подсистемы. -,Ла. (2) диапазоном (0,Q), такие, чтобы выполнялось условие Произвольное число А(о1,с15,..;Дщ.-) из Интервала ГО,Рра53(4) записывается в виде . )1(|И)) (5) где oL; - вычеты числа А по модулям вычеты чисел по модулям (2). - Под одиночной ошибкой будем понимать искажение любого вычета в числе (5), счйибка может возникнуть как при ари 1 метической обработке,так и при передаче этих чисел. Правильными числами назовем числа, расположенные в диапазоне (4) иудовлетворяющие условию 4(ii-,,,d,-a),a,...,n+-f) (6) .Если основания подсистемы удовлетворяют условию (3), то очевидно,что любая одиночная ошибка в правильном числе приведет к нарушению условия (6), так как одиночная ошибка есть иное как сложение правильного числа с ортогональнЬ1м числом. При условии (3) минимальным ортогональным числом будет число , f а максимальные ортогональным числом будет число Таким образом, при сложении правильного числа с любым ортогональным числом подсистемы сумла (т.е. неправильное число больше величи вы Р} и меньше диапазона Gl) . В то же время любая одиночная {ошибка выводит правильное число из диапазона (4). Следовательно, услови (7; гяву - номер интервала по модулю также будет признаком наличия ошибки. . В надсистеме возможными ошибками могут быть числа (0,...,0,,0,...,0) (в) Каждая из этих ошибок может поме тить неправильное число в интервал, который определяется формулой rud..1 ПН 7modP,,)5, (9) где S может принимать значение О или 1 til .. Но так как мы оперируем числами, представленными в подсистеме, и пред полагаем, что ошибка может возникнуть лиш;ь в одном основании подсистем, то возможными -ошибками могут быть лишь числа tO,...,0,AcL.j,0,...,0) . (10) Таким образом, количество возмож ных ошибок при переходе к подсистемам уменьшается. Приведем теперь алгоритм коррекций одиночных ошибок. Вычисляется номер интервала модулю Vft для каждой из подсистем.Ес ли ,- 0(,a..., ) , то ошибки н произошло. Если же какое-нибудь Ttea ° оши ка произоош а. Это значитj что ошибк переместила правильное число Ак UK,dKa.) в е -и интервал и шш ка находится в ft -и строке таблицы возможных ошибок подсистемы. Так как ошибка уже обнаружена,вы числяем номер интервала в надсистем по модулю Pn+i . Получим-f„4.1 3 .Это значит, что ошибка переместила Правильное число А в 5 -и интервал и сх1Шбка находится в S -и строке, ц,-м столбце таблицы возможных ошибо надсистемы. Находим пересечение полученных альтернативных совокупностей, которое однозначно определит величину и местоположение ошибки, так как в К-м столбце S -и строки может быть всего одно число (ошибка), вводящее А в нулевой интервал. Вычитая из принятого числа А ошибку AdLjy , получим правильное число А. На фиг. 1 изображена структурная схема устройства для обнаружения и исправления ошибок в СОП. Оно содержит (n+-i7 группу входных регистров по j регистров 1 в группе ( блоков 2 анализа, которые осуществляют проверку условия (6), коммутатор 3, который при наличии сигнала с выхода блока 10 пропускает искаженный операнд надсистемы интервала, первый 6 блок памяти, первый элемент И 7, второй блок памяти 8, второй элемент И 9 и блок определения вида ошибки 10. На фиг. 2 изображена схема блока определения вида ошибки 10, содержащего () элементов И 11-14 (при п-4), на кото{ ые подключаются соответствующие прямые и инверсные выходы блоков 2, первый элемент ИЛИ 15 и второй элемент ИЛИ 16, входы которого соединены с выходами элементов И 11-14. Выход элемента ИЛИ 16 (признак одиночной ошибки) соединен со входом элемента НЕ 17. Входы ( -го элемента И 18 соединены с выходами элемента НЕ 17 и элемента ИЛИ 15. Выход (n-t-l)-ro элемента И 18 является признаком Многократная ошибка. На фиг. 3 изображена структурная схема блока 2 анализа. Она содержит входные регистры 19, в которых хранится принятое число, схему 20 преобразования из СОК в полиадический код, схему сравнения 21, регистр 22, констант, в котором хранится константа P-j. , записанная в поли ади чес комкоде, и инвертор 23. Блок 2 анализа работает следующим образом. Принятое число преобразуется в полиадический код блоком 20. Схема сравнения 21 сравнивает полиадический код числа oL с полиадичесКИМ кодом числа Р . При d р, выходной сигнал появится на выходе схеквы сравнения, при d.-T/Pj - на выходе инвертора 23. Устройство работает следующим образом. Принятое число через регистры 1 поступает на блоки анализа 2,- которые проверяют .выполнение условия (6).Если условие (6) выполняется для всех оснований нгщсистемы, то на всех прямых выходах блоков 2 появляются выходные сигналы, которые поступают на вход элемента.И 9. Выход под сигнеш элемента. И является признаком правильности числа. Если же в каком К.-м основании надсистемы произошла ошибг ка, то на инверсном выходе К-го блока 2 появится выходной сигнал, котоый пройдя через блок 10, явится признаком нгшичия одиночной ошибки. Сигнал Одиночная ошибка даст разрешение блоку 4 на вычисление номера интервала по основанию . , а также разрешение на прохождение искаженного операнда через коммутатор 3.Вторым разрешакяцим сигналом для коммутатора 3 будет сигнал с инверсного выхода vi. -то блока 2.

Блок 5 вычисляет номер и«тервала по основанию для искаженного числа Ац, (dL,, ioLt,j;oi.K«) На выходе блока 5 появится число в , которое является номером интервала в подсистеме и дает разрешение на выборку альтернативной совокупности из в -и строки таблицы второго блока памяти 8.

В то же время на выходе блока 4 появится число S , которое является номером интервала надсистемы. Выходной сигнал с инверсного выхода к-го блока 2 и число S дадут разрешение на выборку альтернативной совокупности из S-и строки К-го столбца.таблицы первого блока Пс1мяти,

Элемент- И 7 из полученных альтернативных совокупностей выявляет величину и местоположение ошибки,которую необходимо вычесть из принятого числа. ,

Если выходные сигналы появятся на двух и более инверсных вьюсодах блоков 2, то блок 10 выдаст сигнал Многократная ошибка, который не пропустит через коммутатор 3 искаженные операнды и не даст разрешение на вычисление номера интервала блоку 4.

Рассмотрим в качестве примера работу устройства при Р 26, Ра 27, РЗ 29, Р 20358, Р 702,тп 9, Y(r 13, 5, е. 7047, ва 3510.

Основаниями подсистемы выбираем числа q, 5, Ч;а 6, 4-$ 7, а

Q 9 92.9 3 21Q.

Возможны1 ш ошибками будут числа

30(О,О,2),60(О,О,4),90 0,0,6) ,0,1),150(0,0,3),180(0,0,5) 35(0,5,0),70(0,4,0),105(0,3,0) 140(и,2,0),175(О,1,0),42(2,0,0) ,0,0),126(1,0,0),168(3,0,0)

Таблица возможных ошибок в подсистеме имеет вид

Il5Zl i..l

.

Г

1Я

Допустим, что правильное число А 500 (6,14,7) (1,0,6,4,2,0, 2,1,0) исказил эсь и вместо числа А риняли число А (0,0,6,4,2,0,2,Т,0)

ВычислимjfJlij, для числа оС

(0,0,6), получим 3.

Вычислим для числа 2 (4,2,0), получим 7а ОВычислим числа Л (2,1,0), получим

таким образом, мы установили,что шибка произошла по первому основанию надсистемы. Величине-у е л 3 соответтвует следукидая альтернативная совокупность: 4, 6 в таблице.

Вычисляем f-, для принятого числа А, получим УЗ - Находим в таблице ошибки, выводящие число во 2-й интервал по первому основанию надсистемы, совпсщающие с полученной альтернативной совокупностью. Такой ошибкой . может быть только л ) 4. Вычтем А («41 4 из принятого числа и получим первоначальное число, т.е. исправим ошибку.g

Таким образом, с применением новых блоков и связей увеличивается быстродействие устройства И уменьшается величина контрольного основания. Это обусловлено тем, что вычисление позиционных характеристик в системах низкого порядка и с малыми по величине основаниями не затруднено и в предложенном гшгоритме, который реализует данное устройство, позиционную характеристику числа в наДсистеме нужно вычислять только один раз.

Использование предлагаемого устройства обеспечит .существенный зкономический эффект При серийном его использовании.

Формула изобретения

Устройство для обнаружения и исправления ошибок в системе остаточных классов, содержащее () группу входных регисторов по j регистров в группе, первый и второй блоки вычисления номера интервала, первый и второй блоки памяти, причем в ыходн входных регистров всех групп являются входами устройства, выходы входных регистров всех гРУПп соединены с соответствуиядими входами первого блока вычисления номера интервала, выход которого соединен с адресным входом блока первого блока памяти, выхрд второго блока вычисления номера интервала соединен с адресным входом второго блока памяти, отличающ е ее я тем, что, с целью увеличения быстродействия в устройство введены() блоков анализа, коммутатор, блок определения вида ошибки, первый и второй элементы И, причем выходы входных регистров каждой группы соединены с соответствующими входами соответствующего блока ансшиэа,известные выходы кёцкдого блока анализу соединены с соответствукщим входе группы управляющих входов коммутато а/б соответствующим входом блока рпрё деления вида ошибки и с соответствую щим ВХОДСМ4 группы адресных входоб первого блока памяти, вьрсод которого соединен с первым входс м первого элемента И, выход Btopprb блока памяти соединен со вторым входом первого элемента И, выход которого является выходом . устройств а, прЯАвае выходы всех блоков анализа соединены с соответствующими входами второх о элемента И, выход которого является вторым выходом устройства, первый вы.ход блока определения вида ошибки являетря третьим выходсил устройства, второй выход блока определения вида оишбки соединен с управляющим входом коммутатора, с управляихцим входом первого блока вычисления номера интервала, и является четвертым выходом устройства, выходы всех-вторых регистров соединены с соответствующими информационными входами кокФ утатора выходы которого соединены со входами второго блока вычислений н&мера интервала.2. Устройство по п. 1, о т л И-. чающееся, тем, что блок определения вида &ШИбок содержит( элементов И, первый и второй Элементы ИЛИ, и элемент НЕ причем, входы

элементов И и/первого элемента ШШ образуют входы устройства, выходцы первого элемента И, с первого по п соединены с соответствующим входом второго элемента ИЛИ,, выход которого через элемент НЕ соединен с первым входом (n-fi -го элемента И, ВЬЕХОД ког торого является первш выходом блока, выходы первого я второго элементов ИЛ11 соединены Ьортветственно со вторым входом (пч-1)-го элемента ИЛИ)

0 и со вьрсодм блока.

3« Устрэйстйо по п. 1, о тли чающееся тем, что блок анализа содержит втсфые регистры, блок преобразовайия из СОК в полиадический

5 код, схему сравнения, регистр констант, и кнберфсф п|ричем выходы регястров соединены со входами гфёобраао- аателя из СОК в полиадический код, ход Keitojpoiro соединен с первым вхо0дом схемы сравнения второй вход кото PQ8 соединен Ч: выходом регистра констант, 1м кщ;:С} е1«| сравнения через инвертор оЬедмйён с; первым выходом блока, dxeMJ сравнения является вTopfcO4 выхолен блока.

5

йдточнйки информации, прииятме во внимание экспертизе

1- Bayeftft Ж1А 3659089, кл. 253-153;, 1977.

2.. Йатенх Франции 2191700, К.п. G 06 F ii/lp, 1976.

3.Авtc CKoe свидетельство СССР 393950, кл. G 06 F 11/10, 1974 (прототип).

,

«k

с

wf-fi Omifff Ow&ff ff fr rgi/ff fm ffffoso- Brffifff&y / f

LZ-J

3e i/ytf ff

OOffffAff

2f

fS

/ff

cCf /

//

fff.J