Устройство для обнаружения и исправления ошибок в непозиционном коде Советский патент 1985 года по МПК G06F11/08 

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

Известно устройство для обнаружения и исправления ошибок в непозиционном код.е, содержащее входной регистр, входы которого являются входа ми устройства, блок свертки по контрольным модулям, входы которого подключены к nepisoMy выходу входного регистра, сумматоры по контрольным модулям, по входам подключенные к второму и третьему выходам входного регистра и выходам блока модульной свертки по контрольным модулям, блок памяти ошибок, входы которого соединены с выходами сумматоров по контрольным основаниям, и блок сумматоро коррекции по мoдyJlям непозиционной системы счисления, первый вход которого подклю1ен к вьтходу блока памяти ошибок, второй, третий и четвертый входы - соответственно к первому, второму и третьему выходам входного й г«1стра, а вькод является выходом устройства, которое при соответствующей структуре блока модульной свертк по контрольным основаниям осуществляет коррекцию однократных ошибок как по информадионныг-,, так и по контрольным модулям за к модульных операций, где К - количество информа ционных оснований, через Xt обозначается наименьшее целое число,не меньшее X f.

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

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

соединены с выходами регистра контрольной части кода, вторые входы - к выходам узла свертки по контрольным основаниям, а выходы - к соответствукщим входам таблицы поправок, первые входы сумматора коррекции соединены с выходами регистра информационной части кода, а вторые входы - с выходами вычитателя 2,

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

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

Поставленная цель достигается тем что в устройство для обнаружения и исправления ошибок в нетюзиционном коде, содержащее К+2 входных регистров, где К - число информационных оснований, и две группы сумматоров коррекции, при этом входы входных регистров являются информационными входами устройства, первые входы сумматоров коррекции первой и второй груп срответственно объединены, вторые входы сумматоров корекции первой группы объединены, вторые входы сумматоров коррекции второй группы объединены, введены дешифратор, К+2 элементов задержки, два блока суммирования вычетов, первая и вторая группы вспомогательных регистров, трехразрядный регистр, К элементов И, группы мультиплексоров, К+2 выходных регистров и элемент И, причем выходы К+2 входных регистров подключены ко входам К+2 элементов задержки соответственно и к соответствукяцим входам первого и второго блоков суммирования вычетов, первые выходы К+2 элементов задержки подключены соответственно к первым вхо дам сумматоров коррекции первой и второй групп, к вторым входам которых подключены выходы соответственно второго и первого блоков суммирования вычетов, подключенные также к входам дешифратора, первый, второй и третий выходы которого через трехразрядный регистр соединены соответственно с первыми входами мультиплексоров (К+1) -й и (К+2)-й групп и (К+1)-м входом элемента И, группа входов которого JJlCPnC nld rl, L у у ILLla ГЭЛ-и -ГО I J, подключена к выходам К элементов И и к первым входам мультиплексоров К групп, вторые входы которых соединены с первьми входами К элементов И и с выходами К вспомогательных регистров второй группы, а третьи входы - с вторыми входами К элементов задержки вторые выходы (К+1) и (К+2)-го элементов задержки соединены с вторыми входами мультиплексоров (К+1)-й и (К+2)-и групп, третьи входы которых соединены с выходами (К+1)-го и (К+2)-го регистров первой группы, выход i-ro () вспомогательного регистра первой группы подключен к второму входу i-ro элемента И, выходы мультиплексоров К+2 групп подключены соответственно ко входам К+2 вьрсодных регистров, выходы которых являются информационными выходами устройства, выход элемента И является выходом отказа от декодирования устройства, выходы сумматоров коррекции первой и :второй групп подключены соответственно к входам вспомогательных регистров первой и второй групп. На фиг.1 и 2 приведена структурная схема предлагаемого устройства для обнаружения и исправления ошибок в непозиционном коде. Устройство содержит информационные входы устройства 1.1, 1 .2,...,1 К+2 (к- количество информационных модулей) , входные регистры 2.1, 2.2,..., 2К+2, элементы задержки 3.1, 3.2 ЗК+2, блоки суммирования вычетов 4К+1 и 4К+2 соответственно по первому и втор.ому контрольным модулям системы, сумматоры коррекции первой группы 5.1, 5.2,...,5К+2, сумматоры коррекции второй группы 6.1, 6.2,...,6К, дешифратор 7, вспомогательные регистры первой группы 8.1, 8.2,..., 8К+2, вспомогательные регистры второй группы 9.1, 9.2, ..., 9К, трехразрядный регистр 10, элементы 11.1, 11.2,...., ПК, группы мультиплексоров 12.1, 12.2, ..., 12 К+2, выходные регистры 13.1, 13.2, ..., 13 , (К+1), входовый элемент И 14, информационные выходы устройства 15.1, 15.2, ..., 15 К+2, выход 16 отказа от декодирования устройства. Входные регистры устройств -2-. 1, 2.2, ..., 2К+2 предназначены для приема соответствующих цифр исходного непозиционного кода ( к K-f .,,,. . Если сл6во(о( .-1,к-, 3 K-1 К-1к4-5 - H4.7 к-1,.,.,)к-1, содержит ошибки, т.е. является кодовым, то его компоненты определяются следуници- ми соотношениями .,K-lHAM. ,2,.., К-1, -1 . -i.K- ,K-i +Ivc-i М.; к;/ |(.4г . LLtl. (i i 2 ,К-1), .кн п, Ь-,.. П И1 система информационных модулей; при т,.2р+К-2, р - некоторое фиксированное натуральное число т и к.41 контрольные основания, выбираемые из условия: (,2, К; j 1,2) А - число рабочего диапазона системы| D ( -рМ,,-рМ. + + 1,..., рМ(, 1 , через |X(f обозначается наименьший неотрицательный вычет, сравнимьй с величиной X по модулю т. Элемент задержки 31 (,2,...,К+ +2) представляет собой цепочку из Т+1 последовательно соединенных регистров (K+1)r , вход первого из которых является входом элемента задержки, а выходы Т-го и (Т+1)-го регистров - первым и вторым выходами соответственно. Вход элемента задержки 3.1 (, 2, ..., +2К) подключен к выходу регистра 2.1, первый выход одноименным входам сумматоров коррекции 5. 6.1 (, К+2, если ) ,а второй выход соединен с третьим входом группы мультиплексоров 12.1. Блок суммирования .вычетов 4.K+J по контрольному модулю (,2) име конвейерную структуру и служит для формирования за Т тактов j-й компоненты Sj- синдрома S(S,S) ие позиционного кода, определяемой по формуле . J- I-IK-/ (2) .J ;tj+ K4ji ™v:4j; I1 при этом r-й вход блока 4g+K+j (г ,2,...,К) подключен к выходу регисГра 2.г, (К+1)-й вход - к выходу регистра 2.K+J, а выход подключен ко вторьв4 входам сумматоров коррекций j-й группы и j-му входу дешифратора Дешифратор 7 предназначен для выделения значений синдрома S(S,i5) кода, соответствуюпщх си налам если , а в остальных случаях 1, если , а О в остальных случаях, если S 0 и S, /О 1, LО в остальных случаях. Элемент И 11.1 вырабатывает сигн 6 поразрядного совпадения входных величин Х и (о, 1,... ,т. 1 в со ответствии с формулой „ .(), где Х- и У - j-e цифры двоичных представлений вычетов X j и У соответственно ,2,...,K СИМВОЛОМ ® обозначается операция сл жени; по модулю 2. Элемент И 11.1 (,2,...,К) реа лизуется на сумматорах, по модулю 2 г. входовом элементе ИЛИ. (Первый вУод элемента 11.1 через вспомогательньй регистр 8 соединен выходом сумматора коррекции 5.1, второй вход соединен с вторым входо группы мультиплексоров 12.1 и через вспомогательньй регистр 9.1 с выхо дом сумматора коррекции 6.1, выход 11.1 подключен к первому входу груп пы мультиплексоров 12.1 и 1-му входу элемента И14, (К+1)-й вход которого подключен к третьему выходу трехразрядного регистра 10 (,2,...,К). Второй вход группы мультиплексоров 12.K+J соединен с выходом вспомогательного регистра 8.K+J, а первьш вход - с J-M выходом трехразрядного регистра 10, входы которого подключе ны к соответствуюпщм выходам дешифра тора 7 (,2). Выход группы мультиплексоров 12.1 соединен со входом выходного регистра устройства 13.1 для-всех ,2,..., к+2. 1 Предлагаемое устройство реализует способ обнаружения и исправления ошибок в непозиционном коде,, заключающийся в следующем. В соответствии с формулой (2) вычисляются компоненты S и S синдрома S(S, S) кода. Если при .этом , то декодируемое слово не искажено, т.е. является кодовым. Если Sjj П, а S,,,|)0 (,2), то ошибка произошла по j-му контрольному модулю. В этом случае истинное значение (К+з)-й цифры кода совпадает с вычетом тк+j+lt: LfjM, i, (.,,i-Sim Случай S;, и Sj 0 соответствует искажению одного из информационных символов. Для локализации и исправления такой ошибки достаточно: а) для каждого ,2,,..,К в формуле (2) заменить 1-ю цифру кода на неизвестное Z и затем найти его по контрольным модулям, используя (1) и (2) В результате получим вычеты oi,,.,M, К-1 Si га (8) Х. j при ,2,..., К-1; 11 1. +М., Sj m при , -1 1ог„1|К 1--М 8( при ,2,..., К-1;: |1,+М;% S, I т.при . б)если для некоторого б|1,2,..., К вьшолняется , то заключаем, что 9 -я цифра кода искажена. Исправленным ее значением является вычет .|),. в)случай, когда для всех ,2, ...,К выполняется неравенство , указывает на то, что произошла ошибка, кратность которой больше единицы, и в рамках используемого корректирующего кода она не может быть исправлена. I Рассмотрим как работает предлагае.мое устройство для обнаружения и исправления ошибок в непозиционном коде. Непбзиционньй код(о(. -(,t- 1 1 «- 2 K-,.., ,. 1 ,ч .,подлежащий контролю, через входы 1.1, 1.2, ..., 1.К+2 устройства принимается-на входные регистры 2.1, 2.2,..., 2.К+27 откуда он подается на элементы задержки 3.1, 3.2,,.., 3. К+2 и в блоки суммирования вьпетов 4К+1 и 4.К+2, которые по 71 истечении Т-го такта в соответствии с (2) сформируют синдром S(S,S2) непозиционного кода. На (Т+1)-м такте компонента Sj синдрома (j 1,2) с выхода блока суммирования вычетов 4.K+J подаётся на j-й вход дешифратора 7 и вторые вход сумматора коррекции 5+ji, на первый вход которого с одноименного выхода элемента задержки 3.1 поступает 1-я цифра исходного непозиционного кода f/l,((.-l,° «iK-i,.-,K-l,«-,( ,°K4i (,2, ;..,К+2; j 1,2, , К+2, если ), сумматоры коррекции 5.1 (,2,..., К+2) и 6.Д (,2,...,К получают соответственно вычеты Х и (см. формулы (7-9)), которые с выходов сумматоров поступают в регистры 8.1 и 9.1 соответственно, а дешифратор 7 в соответствии с формулами (3-5) формирует сигналы ,, d и Cj , которые с первого, второго и третьего выходов дешифратора передаются в трехразрядньй регистр 10. На (Т+2)-м такте работы устройств элемент И 11.1 (,2,...,К) произво дит анализ содержимых X;j и У, соответственно регистров 8.1 и 9.1, выра батьтая сигнал 6, , определяемый соотношением (6), который подается на первый вход группы мультиплексоров 12.1 и 1-й вход элемента И 14. Одновременно с этим на первый вход ;(К+3)-й группы мультиплексоров (j ,2) и (К+1)-й вход элемента И 14 с выходов j-ro и третьего разрядов регистра 10 подаются соответственно сигналы к4д и (3 , на вторые входы групп мультиплексоров 12.1 и 12К+j (,2,...,К; ,2) подаются соответственно содержимые регистров 9.1 и 8.K+j,T.e. вычеты У;) и X,,j, а на третий вход группы муль- иплексоров ,12.1 (,2К+2) со второго выхода элемента задержки 3.1 поступает 1-я цифра контролируемого непозиционного кода , v-,, д., .-. ,с., .,, к-1,,к4г- В результате на выходах группы мультиплексоров 12.1, 12.2, ..., 12.К+2, а слев выходных редовательно, гистрах устройства 13.1, 13.2,,,,, 13.К+2 сформируется искомый непозици онньй код, а на выходе 16 элемен- .та Н 14 вьфабатывается управляющий сигнал ,й,...с5к . Если для некоторого iu {1,2,..., К+2 / сигнал 18 , то в регистре 13.1 появится вычет Xj (в данном случае для К), если же сЗ 1, то в регистр 13.i поступит i-я цифра исходного кода. Перечень Bceic возможных ситуаций на выходах устройства представлен в табл.1. Нулевое значение сигнала У , вырабатываемого на выходе 16 отказа от декодирования устройства, свидетельствует о том, что исходный код либо бып правильным, либо .содержал ошибку по одному из модулей системы, которая исправлена, единичное значение сигнала соответствует ошибке, кратность которой больше единицы. В рамках используемого корректирующего кода такая ошибка не может быть исправлена. Непозиционный код, сформированный в регистрах 13.1, 13.2, ... 13.К+2 устройства (исходньй или исправленный) , снимается с выходов 15.1, 15.2, ...,15.К+2 устройства, и на этом операция обнаружения и исправления ошибок в непозиционном Коде заканчивается. 1 Быстродействие прототипа, главным образом, определяется скоростными характеристиками входящего в его состав блока преобразования остаточного кода в позиционный код. Теоретическая нижняя оценка времени работы прототипа составляет 2( К ) модульных операций. Перечень возможных ситуаций на выходах устройства Значения сигналов Содержание ситуации Ошибка отсутствует, на информационных выходах устройс гва формируется исходный код, V 0. Сд - :Л 1 Ошибка .произошла 1 1 I t+i ) ,,,1,й-0 по первому контрольному модулю, на информационных кыходах устройства 4 армируется исправленный код, V 0.

Значение сигналов

Содержание ситуации

,... , 1,(/ц. -0 Ошибка произошла

, . °

по второму контрольному модулю, на информационных . выходах устройст-jg ва формируется исправленный код, .

..-,

Ошибка произоиша

по -му информа- г j -6М ционному модулю, на информационных выходах устройства формируется исправленньш код,, .

Содержание ситуаЗначение сигналов ции

,--..2 -Произошла неоднократная ошибка,на информационных выходах устройства формируется исходньй код,

Время вьшолнения одной операции контроля непозиционного кода в предлагаемом устройстве занимает Z-t-llogjCK+l) тактов, что в два раза меньше указанной вьш1е нижней оценки для прототипа.

УСТРОЙСТВО ДЛЯ ОБНАРУЖЕНИЯ И ИСПРАВЛЕНА ОШИБОК В НЕПОЗИЦИОННОМ КОДЕ, содержащее К +2 входнык регистров, где Х- число информационных .оснований, и две группы сумматоров коррекции, при этом входы входных регистров являются информационными входами устройства, первые входы сумматоров коррекции первой и второй групп соответственно объединены, вторые входы сумматоров коррекции первой группы объединены, вторые входы сумматоров коррекции второй группы объединены, отличающееся тем, что, с целью повышения быстродействия, в устройство введены дешифратор, К +2 элементов задержки , два блока суммирования вычетов, первая и вторая группы вспомогательных регистров, трехразрядньй регистр, К элементов И, группы мультиплексоров, К +2 выходных регистров и элемент И,причем выходы К+2 входных регистров подключены к входам К+2 элементов задержки соответственно и к соответствующим входам первогои второго блоков суммирования вычетов, первые выходы И +2 элементов задержки подключены соответственно к первым входам сумматоров коррекции первой и второй групп, к вторым входам которых подключены выходы соответственно второго и первого блоков суммирования вычетов, подключенные также к входам дешифратора, первый, второй и третий выходы которого через трехразрядньй регистр соединены соответственно с первыми входами мультиплексоров (К+1)-й и (К+2)-и групп и (К+1)-м входам элемента И, группа входов которого подключена к выходам К элементов И и к первым входам мультиплексоров К групп, вторые входы которых соединены с первыми входами К элементов И и с выходами К вспомогательных регистров второй группы, а третьи входы - с вторыми входами К элементов задержки, вторые выходы (К+1)-го и (К+2)-го элементов задержки соединены с вторыми входами мультиплексоров (К+1)-й и (К+2)-и групп, СО 4 СО 4ii третьи входы которых соединены с выходами (К+1)-го и (К+2)-го регистров первой группы, выход / -го (i 1-К) iвспомогательного регистра первой группы подключен к второму входу -i-ro элемента И, выходы мультиплексоров К+2 групп подключены соответственно к входам К+2 выходных регис тров, выходы которых являются информационными выходами устройства, выход элемента И является выходом отказа от декодирования устройства, выходы сумматоров коррекции первой и второй групп подключены.соответственно к входам вспомогательных регистров первой и второй групп.