Устройство для обнаружения и исправления ошибок Советский патент 1980 года по МПК H04L12/26 H03M13/51 

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

корректируемого разряда и со вторым входом блока коррекции контрольного разряда байта.

На чертеже представлена структурная электрическая схема описываемого устройства.

Устройство содержит регистр 1 приема информационнЕлх разрядов, блок 2 свертки, блок 3 сравнения, регистр

4приема проверочных разрядов, блок

5коррекции проверочных разрядов, дешифратор 6 кода номера корректируемого разряда, блок 7 коррекции информационных разрядов, формирователь 8 контрольного разряда байта,блок 9 коррекции контрольного разряда байта дешифратор 10 кода номера байта и дещифратор 11 кода номера разряда в байте.

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

При операциях чтения информации заносится в регистр 1. Блок 2 свертки формирует контрольные разряды по коду Хэмминга, которые затем в блоке 3 сравниваются с проверочными разрядами. При совпадении сравниваемых кодов на выходе блока 3 устанавливаются уровни сигналов, которые дешифратором 6 воспринимаются как отсутствие ошибок, и сигналы на его выходе разрешают пройти без изменения информационным и проверочным разрядам через блоки 5 и 7 коррекции проверочных и информационных разрядов.

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

Если при выборке из памяти произошло искажение информации в одном разряде, то блок 3 сравнения обнаруживает несовпадение кодов,поступающи из блока 2 свертки и с выхода регистра 4 и вырабатывает на своих выходах соответствующий код. Дешифратор 10 дешифрирует код номера байта, в который входит информационный разряд, выбранный с искажением. При искажении информации в контрольном разряде по коду.Хэмминга на выходе в дешифраторе 10 устанавливаются уровни си: налов, сбответствующие отсутствию .ок.

Дешифратор 11 дешифрует код номера информационного разряда в пределах байта или код номера контрольного разряда по коду Хэмминга, в которых произошло искажение информации, и вырабатывает сигналы, которые управляют инвертированием искаженной информации в разряде при прохождении через блок 7 коррекции информационных разрядов или блок 5 коррекции

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

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

Если при выборке из памяти произошло нечетное число искажений,превышающих один разряд, то блок 3 сравнения выдает на дешифратор бив процессор сигналы о коррекции. При этом.для разряда случаев сигналы, поступающие на дешифратор 6, вызовут на выходе -дешифратора 10 дешифрацию кода номера байта, в котором якобы произошла ошибка, а на выходе дешифратора 11 - код-номера разряда в байте, который не предусмотрен выбранным методом кодирования номеров разрядов . Тогда выходные сигналы дешифратора 6 не приведут к коррекции информации в блоках 7 и 5 коррекции информационных и проверочных разрядов , а контрольный разряд по нечетности в байте, заданном дешифратором 10, будет проинвертирован. Таким образом будет вызвано несоответствие между информацией, посылаемой в процессор, и. контрольными разрядами байтов по нечетности. Это несоответствие будет обнаружено при приеме информации в процессоре, т.е случаи нечетного числа искажений в информации, превышающие один разряд, будут обнаружены. Сигналы, уведомляющий о коррекции, поступая в процессор из памяти, обеспечивает возможность отличить данную ситуацию от ошибки, которая могла возникнуть при пересылке информации из памяти в процессор. Покажем, как избыточность в,кодировке номера разряда,вытекающая из разрядности памяти, используется для обнаружения многократных ошибок.

Количество контрольных разрядов по коду Хэмминга для 64 информационных разрядов должно определяться по приведенному неравенству

. ,

где k - число информационных разрядов ;

т - число контрольных ра&рядов и составляет /г 7.

Для обнаружения двойных ошибок добавляется еще один контрольный разряд. Семь контрольных разрядов позволяют корректировать одиночную ошибку в 120 информационных разрядах При наличии 64 информационных разрядов можно использовать избыток в кодах номера позиций для присвоения информационным разрядам в пределах каждого байта одинаковых номеров позиций.

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

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

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

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

43%, что подтверждается следующей формулой:

л - -(.«-1)

д. - -ipocyo

где Л - .средняя вероятность обнаруе жения ложной коррекции;

п - число разрядов, обеспечивающих кодировкой 2 128; (т + К + 1)- 72- число информационных и контрольных разрядов, подлежащих коррекции.

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

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

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

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

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

кода номера разряда в байте, при

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

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

1. Патент США W 3568153, кл. 340-146.1. 1971 (прототип).