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

 

ОПИСАНИЕ

ИЗОБРЕТЕНИЯ

К АВТОРСКОМУ Св ЕТВЛЬСФВУ

Союз Советски»

Социалистически»

Реснублик (uj862143 (61) Дополнительное к авт. саид-ву

t53)e. К .3 (22) Заявлено 19336.79 (21) 2807659/18-24

G 06 F 11/10 с присоединением заявки йо (23) Приоритет

Государственный «омнтет

СССР ао делан изобретений и открытий

Опубликовано 070981. бюллетень Н9 33 (53) УДК 681. 3 (088 ° 8) Дата опубликования описания 070981 (71) Заявитель (54) УСТРОЙСТВО ДЛЯ ОБНАРУЖЕНИЯ И ИСПРАВЛЕНИЯ

ОШИБОК В СИСТЕМЕ ОСТАТОЧНЫХ КЛАССОВ

Изобретение относится к вычислительной технике и может быть использовано при построении надежных вычислительных устройств, функционирующих в системе остаточных классов (COK).

Известны устройства для обнаружения и исправления информации в СОК содержащие систему обнаружения и коррекции ошибок определение местопоЛо-. 1О жения ошибок производится с помощью контроля по четности, а обнаруженные ошибки корректируются методом вычетов), предсказывающее устройство устройство вычетов, вычислитель четности, вычислитель вычетов, блок сравнения, блок коррекции данных и вычислитель значения ошибки С11 и Г23 .

Наиболее близким техническим решением к изобретению является устройство для обнаружения и исправления ошибок в СОК, содержащее выходной регистр, выходные сигналы которого .подаются на входы хранения констант.С выходов блока хранения констант коды вычетов по контрольным основаниям поступают на входы сумматоров по конт,рольным основаниям, выходы которых подключены ко входам блока анализа на нуль остатка по контрольным основани ям и блока констант исправления. Коды

I констант, предназначенные для вычисления неточных рангов чисел, поступают иа входы одноразрядных сумматоров, находящихся в блоках вычисления нетОчноГо ранга чисел, выходы блоков подсоединены к сумматорам по контрольным основаниям, входы блока хранения констант исправления, подключены к выходному регистру, а выходы„ ко входам сумматоров по контрольным основаниям и входам блоков вычисления неточного ранга f33, Недостатком таких устройств является то, что при. высокбм бЫстродействии в нйх предусматриваются большие по величине контрольные основания,а быстродействие снижено при небольших по величине контрольных основаниях.

Кроме того,они не позволяют обнаруживать больше одной ошибки.

При величине контрольного основания Р + т ЄЄ». номеру интервала, в котором ошибка перемещает неправильное число,однозначно соответствует величина и местоположение ошибки.

При величине контрольного основанияРп. >РпФл+ номеру интервала соответствует не более двух ошибок.

Большая величина контрольного основания нежелательна так как.при

862143: этом затрудняется построение таблиц основных арифметических операций.

При величине контрольного основанияРд+„)р номеру интервала соответствует альтернативная совокупность ошибок, для стягивания которой воЗникает необходимостЬ несколько раз вычнслять комер интервала, что снижает,быстрОДействие устройства.

Целью изобретения является повышение быстродействия устройства.

Эта цель достигается тем, что .в устройство для обнаружения и исправ10 ления ошибок СОК, содержащее +1 группу входных регистров по > регистров в группе, первый и второй блоки вычисления номера интервала, первый и второй блоки памяти, причем выходы. входных регистров всех групп являются входами устройства, выходы входных регистров всех групп соединены с соответствующими входами первого блока вычисления номера интервала, выход которого соединен с адресным вхо дом первого блока памяти. Выход второго блока вычисления номера интервала соединен с адресным входом второго блока памяти. В устройство введены и+- блоков анализа, коммутатор, блок определения вида ошибки, первый и второй элементы И. Выходы входных регистров каждой группы соединены с соответствующими входами соответствующего блока анализа, инверсныЕ выходы каждого блока анализа соединены с соответствующим входом групп управляющих входов коммутатора с соответствующим входом блока определения вида ошибки и с соответствующим входом группы адресных входов первого блока памяти, выход которого coe" динен с первым входом первого элемента И. Выход второго блока памяти 40 соединен со вторым входом первого элемента И, выход которого является первым выходом устройства.

Прямые выходы всех блоков анализа соединены с соответствующими входами второго элемента И, выход которого является вторым выходом устройства. Первый выход блока определения вида ошибки является выходом устройства, второй выход соединен с управляющим входом коммутатора с управляющим входом первого блока вычисления и является четвертым выходом устройства. Выходы всех регистров соедннены с соответствующими входами коммутатора, выходы которого соединены со входами второго блока вычисления номера интервала. Блок определения вида ошибки .содержит и 1 элементов . И, первый и второй элементы ИЛИ и элемент НЕ. ЬО

Входы элементов И и первого элемента ИЛИ образуют входы устройства, выходы первого элемента И с первого по и соединены с соответствующим. входом второго элемента ИЛИ, выход которого через элемент НЕ соединЕн с первым входом (n+ ) -го элемента И, выход которого является первым выходом блока. Выходы первого и второго элементов ИЛИ соединены соответственно со вторым входом(п+ ) -го элемента ИЛИ и со вторым выходом блока.

Блок анализа содержит входные регистры, блок преобразования из СОК в полиадический код, схему сравнения, регистр констант и инвертор. Выходы регистров соединены со входами преобразователя иэ СОК в полиадический . код, выход которого соединей с первым входом схемы сравнения, второй вход которого соединен с выходом регистра констант. Выход схемы сравнения через инвертор соединен с первым выходом блока, выход схемы сравнения является четвертым выходом блока.

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

СОК основывается на применении многоступенчатой СОК.

Изобретение предназначено для обнаружения и исправления ошибсыс в двух-. ступенчатых стандартных непозиционных кодах. Такой код строится следующим образом. Выбираются основания СОК, удовлетворяющие заданному рабочему диапазону

Р„, Р ., Р (1)

Вводится контрольное основание

Р„+„, большее, чем каждое рабочее основание (B дальнейшем будем называть эти основания основаниями надсистемы) . Затем выбираются основания подсистемы.

9g ) %) ° 9g (2) с Диапазоном (p,g), такие, чтобы выполнялось условие

%.%,9 )Р((,a,.„. и+ ). (S),(3)

Произвольное число А =(с(,„;Д.,,,д,) из интервала (о,p,„„„) (4) записывается в виде

"=(и ч з« чт яз".

"Ф (в )1ФомаФ(пмя» (Ю где А - вычеты числа А по модулям (1) р д-; — вычеты чисел по модулям {2).

Под одиночной ошибкой будем понимать искажение любого вычета (,1 в числе (5), ошибка может возникнуть как при арифметической обработке,так и при передаче этих чисел, Правильными числами назовем числа, расположенные в диапазоне (4) и удовлетворяющие условию И (р "1 ) (1= Й . - и+1) (6) .Если основания подсистемы удовлетворяют условию (3), то очевидно,что любая одиночная ошибка в правильном числе приведет к нарушению условия (6), так как одиночная ошибка есть

862143 нечто иное как сложение правйльиого числа с ортогональным числом.

При условии (3) минимальным ортогональным числом будет число ц. а максимальным ортогональным числом будет число

2 5-1

Таким образом, при сложении правильного числа с любым ортогональным . числом подсистемы сумма (т.е. неправильное число Х. буцет больше -величины Р„ и меньше диапазона Й ).

В то же время любая одиночная (ошибка выводит правильное число иэ диапазона (4). Следовательно, условие

5п+. 4 ц (7) где,+, — номер интервала по модулю

Рn+ также будет признаком наличия ошнбки.

В надсистеме возможными ошибками могут быть числа (О,...,О,М О,...,0) (В)

Каждая из этих ошибок может помес-. тить неправильное число в интервал, который определяется формулой

Д4 т Рра

3 + » Р )(во Р n )+б Л)

3 где S может принимать значение 0 или 1 E1J °

Но так как мы опери.руем числами, представленными в подсистеме; и предполагаем, что ошибка может возникнуть лишь в одном основании подсистем, то возможными ошибками могут быть лишь числа (0,...,О,Ь.Ь„.;,0,...,О), (

Таким образом, количество возможных ошибок при переходе к подсиСтемам уменьшается.

Приведем теперь алгоритм коррекции одиночных ошибок.

Вычисляется номер интервалау q по модулю для каждой из подсистем.Если ;,„-Q(=a,2..., и+ ), то ошибки не произошло. Если же какое-нибудь д е Д, где 3 Ф О, 1 (6 4п+а, то ошибка йроизошла. Это значит, что ошибка переместила правильное число *» (ф,„,d. z,Ä.< } в 8 -й интервал и ошиб.ка находйтся в В -й строке таблицы возможных ошибок подсистемы.

Так как ошибка уже обнаружена,вычисляем номер интервала в надсистеме по модулю (n+q . Получим у.„,„=й .Это значит, что ошибка переместила правильное число A í S -й интервал и ошибка находится в S -й строке., К-м столбце таблицы возможных ошибок надсистемы.

Находим пересечение полученных альтернативных совокупностей, которое однозначно определит величину и местоположение ошибки, так как в

K.-м столбце S --й строки может быть всего одно число (ошибка), вводящее

Ь в нулевой интервал. Вычитая иэ принятого числа А ошибкудд.;, получим правильное число A.

На фиг. 1 изображена структурная

; схема устройства для обнаружения и исправления ошибок в СОП.

Оно содержит(п+ 7 группу входных регистров по j регистров 1 в группе (n+w) блоков 2 анализа, которые qcyществляют проверку условия (6), коммутатор 3, который при наличии сигнала с выхода блока 10 пропускает искаженный операнд надсистемы интервала, первый 6 блОк памятн, первый элемент

И 7, второй блок памяти 8, второй элемент И 9 и блок определения вида ошибки 10.

На. фиг. 2 изображена схема блока определения вида ошибки 10, содержащего (а+ ) элементов И 11-14 (прн п -4), на которые подключаются соот20 ветствующие прямые н инверсные выходы блоков 2, первый элемент ИЛИ 15 н второй элемЕнт ИЛИ 16, входы которого соединены с выходами элементов И

11-14.

Выход элемента ИЛИ 16 (признак одиночной ошибки) соединен со входом элемента НЕ 17. Входы(+ ) -го элемента И 18 соединены с выходами элемента НЕ 17 и элемента ИЛИ 15. Выход (и+1)-го элемента И 18 является признаком "Многократная ошибка".

Ra фиг. 3 изображена структурная схема блока 2 анализа.

Она содержит входные регистры 19, в которых хранится принятое число, схему 20 преобразования нз COK в полиаднческий код, схему сравнения 21, регистр 22, констант, в котором хранится константа ., записанная в полиадическом.коде, и инвертор 23.

49 Блок 2 анализа работает следующим образом. Принятое число преобразуется в полиадический код блоком 20.

Схема сравнения 21 сравнивает полиадический код числа * с полиадичес45 ким кодом числа Р

При <(; < Р; выходной сигнал появится на выходе схемы сравнения, при

Д..?j Р— на выходе инвертора 23.

Устройство работает следующим об,И, разом.

Принятое. число через регистры 1 поступает на блоки анализа 2,- которые проверяют .выполнение условия (6).Если условие (б) выполняется для всех оснований надсистемы, то на всех прямых Выходах блоков.2 появляются выходные сигналы, которые поступают на вход элемента И 9. Выход под сигнал элемента И 9 является признаком правильности числа. Если же в каком К -м ф) основании надсистему произошла ошиб 4 ка, то на инверсном выходе K-го блока 2 появится выходной сигнал, который пройдя через блок 10, явится признаком наличия одиночной ошибки.

65 Сигнал "Одиночная ошибка" даст раздопустим, что правильное число

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

Вычислимо, для числа d4., (0,0,6), получим у„ = 3.

Вычислимgy+ для числа .А< = (4,2,0), получим 7 . = О.

Вычислим с „ для числа <45 = (2,1,0), получим g = О.

Таким образом, мы установили,что ошибка произошла по первому основанию надсистемы. Величине = 3 соответствует следующая альтернативная совокупность: A*g 4, A+ g= 3,<+ =. 4, A* g-- б в таблице.

Вычисляем у для принятого числа

А, получим ф = 2. Находим в таблице ошибки, выводящие число во 2-й интервал по первому оснонанию надсистемы, совпадающие с.полученной альтернативной совокупностью. Такой ошибкой может быть только AÀ „= 4. Вычтем

A d = 4 иэ принятого числа и получим перноначальное число, т.е. исправим ошибку.

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

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

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

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

7 86214 решение блоку 4 на вычисление номера интервала по основанию Р„+, а также разрешение на прохождение искаженного операнда через коммутатор З.Вторым разрешакй им сигналом для коммутатора 3 будет снгнал с инверсного вЫхода к -го- блока 2.

Блок 5 вычисляет номер интервала по основанию Ф для искаженного числа Ак=(д.q,*ö,,д,к@) . На выходе блока

5 появится чйсло 6., которое являетая номером интервала в подсистеме и дает разрешение на выборку альтернативной совокупности из 8 -й строки таблицы второго блока памяти 8.

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

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

ro числа.

Если выходные сигналы появятся на двух и более инверсных выходах блоков 2, то блок 10 выдаст .сигнал

"Многократная ошибка", который не З0 пропустит через коммутатор 3 искаженные операнды и не даст разрешение на вычисление номера интервала бло.ку 4.

Рассмотрим в качестве примеРа Ра- З5 боту устройства при Р = 26, Р О = 27, Р9= 29, Р = 20358, Р - 702,m = 9, т = 13, п = 5, В„= 7047, Ь = 3510. .Основаниями подсистемы выбираем числа Ч,„= 5, Я, = 6, ф = 7, а

Q g gngq 5 ° 6 7 = 210 °

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

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, О)

140=(0,2,0),175=(0,1,0),42=(2,0,0)

84={4,0,0),126=(1,0,0),168=(3,0,0) Таблица возможных ошибок в подсистеме имеет вид 50 а cL< 4d.

5 2

2,4

1,3

4

5 б

5,4 4

3,4 б

° 3,2 1

1,2 3

1 5

Устройство для обнаружения и исправления ошибок н системе остаточных классов, содержащее(n+s) группу. входных регисторов по j регистров в группе, первый и второй блоки вычисления номера интервала, первый и второй .блоки памяти, причем выходы входных регистров всех групп являются входами устройства, ныходы входных регистров всех групп соединены с соответствующими входами первого блока вычисления номера интервала, выход которого соединен с адресным входом блока первого блока памяти, выход нтороГо блока вычисления номера интервала соединен с адресным входом второго блока памяти, о т л и ч а ющ е е с я тем, что, с целью увеличения быстродействия в устройство введены{п 1) блоков анализа, коммутатор, блок опредеЛения вида ошибки, первый и второй элементы И, причем выходы входных регистров каждой группы соеВ62И3

9 динены с соответствующими входащк со- элементов И н(первого элемента ИЛИ ответствующего блока анализа,извест- образуют входы устройства, выходы ные выходы каждого блоха.аиалйз4 сое- первого элемента И, с первого по и динены с соответствующим входом:груп- соединены с соответствующим входом пы управляющих входов ковееутатора;с. второго элемента ИЛИ, выхОд кОторОГО соответствующим входом блока оправе- > через элемент ИЕ соединен с первым ленин вида ошибки и с соответствую» входом (п+ю) -ro элемента И, выход ко-. щим входом группы адресных входов . торого является первым выходом блопервого блока памяти, выход которого, ка, выходы первого н второго элемеи-. соединен с первым входом первого эле- тов иЛИ соединены соответственно со мента и, выход второго блока памяти 1 вторым входом (в+1)го элемента или) соединен со вторым входом первого и со вторым выходОм блока. элемента и, выход которого является 3. уст :буйство по и. 1, о т л и первым выходом .Устройства, прямые ч а ю щ е е с.я тЕм, что блок айнливыходы всех блоков анализа соединены за содержит вторые регистры, блок с соответствующими входами второго преобразования из. COK в нолиадическнй элемента И, выход которого является. код, схему сравнения, регистр конвторым выходом устройства, первый вы-. . стант, н ннвертор причем выходы рега- .ход блока определения вида «маибкн яв- стров соединены со входами преобразоляется третьим выходом устройства, . вателя из СОИ в полиадический код, второй выход блока определения вида выход которого. соединен.с первым sxo ошибки соединен с управляющим входом 29 дом схемы сравнения второй вход котокоммутатора, с управлякнцим входом . poa соединен: с выходом регистра конпервого блока вычисления:номера ин- . стант, виаищ;:схемы сравнения через тервала, и является четвертым выхо- инверъор еМдннен с первым выходом дом устройства, выходы всех вторых блока, вымя: схемы сравнения являет" регистров соединены с соответстВующи- д5 ся вторым выходом блока. ми информационными входами коюц та- Моточникн информации, тора выходы которого соединейй со.. принятые- аа внимание при экспертизе. входами второго блока вычисления н0- . 1. БатенФ сюА 9 3659089, мера интервала. кл 253-153, 1977.

2. Устройство по п. 1, о т л и-., 2.. Йатейт Франции В 2191700, ч а ю щ е е с я тем, что блок on-. кл. G 06 F. 1Ъ/10, 1976. ределения вида Ьшнбок содержит(п+1) . 3;. Ааторское свидетельство СссР элементов И, первый и второй элемен- 9 393950, кл. 6 Об К 11/10, 1974 ты ИЛИ, и элемент НЕ причем, .входы (прототип).

862143

Составитель И.Сигалов

Редактор Л.Утехина Техред С. МигУнова КорреКтор О. Билак.

Заказ 6613/43 Тираж 745 Подписное

BHHHTIH. Государственного комнтета CCCP по делам изобретений и открытий

113035, Москва, Ж-35, Раушская наб., д. 4/5

Филиал ППП "Патент", r. Ужгород, ул. Проектная, 4