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

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

Иллюстрации

Показать все

Реферат

 

Союз CoooTcKNx

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

Республик

ОПИСАНИЕ

ИЗОБРЕТЕНИЯ

К АВТОРСХОМУ СВИДЕТЕЛЬСТВУ

<>786037 (61) Дополнительное к авт. свид-ву (22) Заявлено 0305„78 (21) 2611148/1S-ОЭ (51)М. Кл З

Н 04 L 11/08

Н 03 К 13/32 с присоединением заявки ¹

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

СССР но делам изобретений н открытий (23) Приоритет (53) УДК 681.326..75(088.8) Опубликовано 07.1280 Áþëëåòåíü ¹ 45

Дата опубликования описания 07.12.80 (72) Авторы изобретения

Е.Я. Белалов, Я.М. Лихтер и B H. Харитонов

Киевский ордена Трудового Красного Знамени завод вычислительных и управляющих машин (71) Заявитель (54) УСТРОЙСТВО ДЛЯ ОБНАРУЖЕНИЯ И ИСПРАВЛЕНИЯ

ОШИБОК

Изобретение относится к вычислительной технике и может быть использовано при разработке ЭЦВМ.

Известно устройство для обнаруже- 5 ния и исправления ошибок, содержащее последовательно соединенные регистр приема информационных разрядов, блок свертки и блок сравнения, второй вход которого соединен с выходом ре- 10 гистра приема проверочных разрядов и с первым входом блока коррекции проверочных разрядов, второй вход которого соединен с выходом дешифратоРа кода номера коррек ируемого 15 разряда и первым входом блока коррекции информационных Разрядов, второй вход которого соединен со входом блока свертки и со входом формирователя контрольного разряда байта, вы- „-20 ход которого соединен с первым входом блока коррекции контрольного разряда датчика. 11 .

Однако вероятность обнаружения ошибки в таком устройстве недостаточ-25 на.

Цель изобретения — повышение вероятности обнаружения ошибок эа счет дополнительного использования имеющейся иэбыточностй кода. 30

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

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

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

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

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

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

8 контрольного разряда байта, блок 9 коррекции контрольного разряда байта, дешифратор 10 кода номера байта и де- 3$ щифратор 11 кода номера разряда в байте.

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

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

Формирователь 8 формирует контрольные разряды байтов по нечетности. З5

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

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

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

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

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

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

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

40 ных разрядов должно определяться по приведенному неравенству

kim+1a 2 где I — число информационных разрядов; т — число контрольных разрядов и составляет ю = 7.

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

При наличии 64 информационных разрядов можно испольэовать избыток в кодах номера позиций для присвоения информационным разрядам в пределах каждого байта одинаковых номеров позиций.

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

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

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

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

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

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

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

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

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

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

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

786037

Составитель В. Лякишев

Редактор Л. Утехина Техред С.Мигунова Корректор Н. Бабинец

Заказ 8866/61 Тираж 729 Подписное

ВНИИПИ Государственного комитета СССР по делам изобретений и открытий

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

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