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

Союз Советсиик Социалистических РеспубликОПИСАНИЕИЗОБРЕТЕНИЯК АВТОРСХОМУ СВИДЕТЕЛЬСТВУ и 786037(51)М. Кл З Н 0 Ц . 11/08 Н 03 К 13/32 с присоединением заявки йо Государственный комитет СССР ло делам изобретений н открнтий(72) Авторы изобретения Е.Я. Белалов, Я.М. Лихтер и В.Н. Харитонов Киевский ордена Трудового Красного Знамени завод вычислительных и управляющих машин(54) УСТРОЙСТВО ДЛЯ ОБНАРУЖЕНИЯ И ИСПРАВЛЕНИЯОШИБОК Изобретение относится к вычислительной технике и может быть использовано при разработке ЭЦВМ. Известно устройство для обнаруже ния и исправления ошибок, содержащее последовательно соединенные регистр приема информационных разрядов, блок свертки и блок сравнения, второй вход которого соединен с выходом ре- О гистра приема проверочных разрядов и с первым входом блока коррекции проверочных разрядов, второй вход которого соединен с выходом дешифратоРа кода номера корректируемого 15 разряда и первым входом блока коррекции информационных разрядов, второй вход которого соединен со входом блока свертки и со входом формирователя контрольного разряда байта, вы ход которого соединен с первым входом блока коррекции контрольного разряда датчика. 11 .Однако вероятность обнаружения ошибки в таком устройстве недостаточна.Цель изобретения - повышение вероятности обнаружения ошибок эа счет дополнительного использования имеющейся иэбыточностй кода, 30 Цель достигается тем, что в устройство для обнаружения и исправления ошибок, содержащее последовательно соединенные регистр приема информационных разрядов, блок свертки и блок сравнения, второй вход которого соединен с выходом регистра приема проверочных разрядов и с,первым входом блока коррекции проверочных разрядов, второй вход которого соединен с выходом дешифратора кода номера корректируемого разряда и первым входом блока коррекции информационных разрядов, второй вход которого соединен со входом блока свертки и со входом формирователя контрольного разряда байта, выход которого соединен с первым входом блока коррекции контрольного разряда байта, введены дешифратор кода номера байта и дешифратор кода номера разряда в байте. Выход блока сравнения соединен с объединенными входами дешифратора кода номера разряда в байте, выход которого соединен с первым входом дешифратора кода номера корректируемого разряда,и дешифратора кода номера байта, первый выход которого соединен со вторым входом дешифратора кода номеракорректируемого разряда и со вторымвходбм блока коррекции контрольногоразряда байта,На чертеже представлена структурная электрическая схема описываемого устройства.Устройство содержит регистр 1 приема информационных разрядов, блок 2свертки, блок 3 сравнения, регистр4 приема проверочных разрядов, блок5 коррекции проверочных разрядов,дешифратор б кода. номера корректируемого разряда, блох 7 коррекции информационных разрядов, формирователь8 контрольного разряда байта, блок 9коррекции контрольного разряда байта,дешифратор 10 кода номера байта и дещифратор 11 кода номера разряда вбайте,Устройство работает следующим образом.При операциях чтения информации 2 Озаносится в регистр 1, Блок 2 свертки Формирует контрольные разрядыпо коду Хэмминга, которые затем вблоке 3 сравниваются с проверочнымиразрядами, При совпадении сравнивае.мых кодов на выходе блока 3 устанавливаются уровни сигналов, которыедешифратором б воспринимаются как отсутствие ошибок, и сигналы на еговыходе разрешают пройти беэ изменения информационным и проверочнымразрядам через блоки 5 и 7 коррекции проверочных и информационнь 1 хразрядов.Формирователь 8 формирует контрольные разряды байтов по нечетности, З 5При отсутствии ошибок дешифратор 10выдает сигналы, которые разрешаютконтрольным разрядам байтов по нечетности проходить беэ изменения черезблок 9 коррекции контролируемого разряда байта,Если при выборке иэ памяти произошло искажение информации в одномразряде, то блок 3 сравнения обнаруживает несовгадение кодов, поступающих 45из блока 2 свертки и с выхода регистра 4 и вырабатывает на своих выходахсоответствующий код. Дешифратор 10дешифрирует код номера байта, в который входит информационный разряд,выбранный с искажением. При искажении информации в контрольном разрядепо коду.Хэмминга на выходе в дешифраторе 10 устанавливаются уровнисигналов, сдответствующие отсутствиюош 6 Ок. 55Дешифратор 11 дешифрует код номера информационного разряда в пределах байта или код номера кснтрольного разряда по коду Хэмминга, в которых произошло искажение информации, Щи вырабатывает сигналы, которые управляют инвертированием искаженнойинформации в разряде при прохождениичерез блок 7 коррекции информационных разрядов или блок 5 коррекции 65 проверочных разрядов. Если искажениеинформации происходит в определенноминформационном разряде, то параллельно с инвертированием искаженнойинформации в блоке 7 происходит ин-.вертирование значения соответствующего контрольного разряда байта вблоке 9; Таким образом достигаетсясоответствие между информацией, которая корректируется, и контрольнымиразрядами байтов по нечетности,Если при выборке из памяти былообнаружено искажение информации вчетном количестве разрядов, то блок3 сравнения вырабатывает и передаетсигнал о .наличии некорректируемойошибки. При этом на дешифратор б кода номера корректируемого разрядавыдаются сигналы, которые соответст. -вуют отсутствию Коррекции и в памятьбез изменения будет записана информация, При некорректируемых ошибкахинформацию в память можно записатьв операциях записи, когда число записанных байтов равно числу байтовв физической ячейке,Если при выборке из памяти произошло нечетное число искажений,превышающих один разряд, то блок 3 сравнения выдает на дешифратор б и в процессор сигналы о коррекции. При этом.для разряда случаев сигналы, поступающие на дешифратор б, вызовут на выходе дешифратора 10 дешифрацию кода номера байта, в котором якобы произошла ошибка, а на выходе дешифратора 11 - код номера разряда в байте, который не предусмотрен выбранным методом кодирования номеров разрядов. Тогда выходные сигналы дешифратора б не приведут к коррекции инФормации в блоках 7 и 5 коррекции информационных и проверочных разрядов, а контрольный разряд по нечет- ности в байте, заданном дешифратором 10, будет проинвертирован. Таким образом будет вызвано несоответствие между информацией, посылаемой в процессор, и контрольными разрядами байтов по нечетности. Это несоответствие будет обнаружено при приеме информации в процессоре, т.е случаи нечетного числа искажений в информации, превышающие один разряд, будут обнаружены. Сигналы, уведомляющий о коррекции, поступая в процессор из памяти, обеспечивает возможность отличить данную ситуацию от ошибки, которая могла возникнуть при пересылке информации из памяти в процессор. Покажем, как избыточность в,кодировке номера разряда,вытекающая из разрядности памяти, используется для обнаружения многократных ошибок.Количество контрольных разрядов по коду Хэмминга для 64 информацион40 ных разрядов должно определяться поприведенному неравенству1 фт+Ы 2где- число информационных разрядов;т - число контрольных разрядови составляет ю = 7,5Для обнаружения двойных ошибокдобавляется еще один контрольныйразряд. Семь контрольных разрядовпозволяют корректировать одиночнуюошибку в 120 информационных разрядах.При наличии 64 информационных разрядов можно испольэовать избыток вкодах номера позиций для присвоенияинформационным разрядам в пределахкаждого байта одинаковых номеров позиций.При таком присвоении номеров позиций три старших разряда номерапозиции однозначно определяют код номера байта, а оставшиеся четыре раэряда - код номера разряда в пределах байта.Подобное назначение номеров позиций информационных разрядов обеспечивает простую схемную реализацию 25дешифраторов 10 и 11 кода номера байта и кода номера разряда в байте.При искажении информации в нечетном числе разрядов, превышающих один,код на выходе блока 3 сравнения будет всегда однозначно определять номер байта информации, а код номераразряда в пределах байта во многихслучаях будет указывать разряд, несоответствующий принятой кодировке,например, для кодов 0011, 0111,1011,При этой кодировке вторая ступеньдешифрации вырабатывает сигналы,покоторым выполняется коррекция, т,е.в тех случаях, когда суммарное искажение информации приводит к такимкодам, описываемое устройство обеспечивает несоответствие между информацией, пересылаемой из памяти впроцессор, и контрольными разрядами байтов по нечетности, которые ее 45сопровождают.Таким образом, увеличиваетсядостоверность контроля при обнаружении ложных коррекций в среднем на 43, что подтверждается следующейФормулой; Й 1 Ргде А - .средняя вероятность обнаружения ложной коррекции;П - число разрядов, обеспечивающих кодировксй 2 128;(щ + К + 1) = 72 - число информационных и контрольных разрядов,подлежащих коррекции.Формула изобретенияУстройство для обнаружения и исправления ошибок, содержащее последовательно соединенные регистр приема информационных разрядов, блоксвертки и блок сравнения, второйвход которого соединен с выходомрегистра приема проверОчных разрядови с первым входом блока коррекциипроверочных разрядов, второй входкоторого соединен с выходом дешифратора кода номера корректируемого разряда и первым входом блока коррекцииинформационных разрядов, второй входкоторого соединен со входом блокасвертки и со входом формирователяконтрольного разряда байта, выходкоторого соединен с первым входомблока коррекции контрольного разрядабайта, о т л и ч а ю щ е е с я тем,что, с целью повышения вероятностиобнаружения ошибок за счет дополни-,тельного использования имеющейсяизбыточности кода, введены дешифратор кода номера байта и дешифраторкода номера разряда в байте, приэтом выход блока сравнения соединенс объединенными входами дешифраторакода номера разряда в байте, выходкоторого соединен с первым входомдешифратора кода номера корректируемого разряда, и дешифратор кода номера байта, первый выход которогосоединен со вторым входом дешифратора кода номера корректируемого разряда и со вторым входом блока коррекции контрольного разряда байта.Источники информации,принятые во внимание при экспертизе1. Патент США М 3568153,кл. 340-146.1. 1971 (прототип).786037 СоставительВ. Лякишеведактор Л. Утехина Техред С.Мигунова Корректор Н. Ба бб Зака 113 филиал ППП "Патент", г, Ужгород, ул. Проектн Тираж 729 ИПИ Государственно о делам изобретени 035, Москва, Ж,Подписноео комитета СССРи открытийРаушская наб., д. 4/5