Оперативное запоминающее устройство с коррекцией информации Советский патент 1984 года по МПК G11C29/00 

Изобретение относится к вычислительной техни1йе и может быть использовано в качестве оперативного запоминающего устройства с повышенными корректирующими способностями. Известно запоминающее устройство содержащее блоки памяти, формирователи контрольных разрядов кода Хемминга, формирователь проверочного слова, дешифраторы lJ . Недостатком этого устройства явля ется то, что в нем исправляется только одна ошибка. Наиболее близким к данному изобретению является запоминающее устройство с обнаружением и исправление ошибок, содержащее накопитель, подключенный к. адресному блоку, блоку управления и блоку записи-считывания входы и выходы которого соединены соответственно с выходами основного регистра слова и первыми входами эле ментов ИЛИ первой группы, основные сумматоры по модулю два, подключенные к основному регистру слова, осно ную схему сравнения, вторую группу элементов ИЛИ, элементы И и дополнительные регистр слова, схему сравнения и сумматоры по модулю два, приче одни из вьгходов основного регистра слова и выходы сумматоров по модулю два подключены ко вторым входам элементов ИЛИ первой группы, выходы сумматоров по модулю два соединены с входами дополнительной схемы сравнения, выходы которой соединены с одни из входов элементов И, другие входы которых подключены к выходам основной схемы сравнения, выходы основного регистра слова соединены с одними из входов элементов ИЛИ второй группы, другие входы которых подключены к выходам элементов И, а выходы - ко входам дополнительного регистра слова, выходы которого соединены со вторыми входами элементов ИЛИ первой группы и одними из входов основной схемы сравнения, другие входы которой подключены к выходам основного регистра слова, входы дополнительных сумматоров по модулю два соединены с выходами основного регистра елова 2. Недостатками этого устройства являются его малая обнаруживающая и корректирующая способность и большие затраты оборудования, что снижает надежность устройства. изобретения является повышение надежности устройства. Поставленная цель достигается тем, Что в оперативное запоминающее устройство с коррекцией информации, содержащее накопитель основной информации и накопитель контрольной информации, одни из входов которых являются соответственно адресным и управляющим входами устройства, первую и вторую группы сумматоров по модулю два, введены постоянные накопители, элемент И-НЕ и коммутатор, один из входов которого является информационным входом устройстваJ другие входы подключены соответственно к выходу накопителя основной информации и управляклцему входу устройства, а выход соединен с информационным входом накопителя основной информации и входом первого постоянного накопителя, выход которого подключен к первым входам сумматоров по модулю два первой группы и информационному входу накопителя контрольной информации, выход которого соединен со вторыми входами сумматоров по модулю два первой группы, выходы которых подключены ко входу второго -постоянного накопителя, выход которого подключен ко входам элемента И-НЕ и одним из входов сумматоров по модулю два второй группы, другие входы которых подключены к выходу накопителя основной информации, а выходы являются информационным выходом устройства, контрольным выходом которого является выход элемента И-НЕ, На чертеже изображена структурная схема оперативного запоминающего устройства с коррекцией информации. . Устройство содержит коммутатор 1, первьй постоянньй накопитель 2, накопитель 3 основной информации, накопитель 4 контрольной информации, первую группу сумматоров 5 по модулю два, второй постоянньй накопитель 6, вторую группу сумматоров 7 по модулю два и элемент И-НЕ 8. ДЛЯ устройства, способного исправлять до трех ошибок, накопители 3 и 4 выбраны соответственно восьми- и одиннадцатиразрядными, а накопители 2 и 6 имеют соответственно организацию 256x11 разрядов и 2048x8 разрядов. В качестве корректирующего кода для данного устройства выбран код Голея. Код Голея является современ-. ным систематическим циклическим блоконым кодом (23,11). Таким оЬразом, для 12 информационных разрядов необходимо 11 контрольных. В связи с тем, что в подавляющем большинстве современных ЭВМ информационные форма ты кратны восьми разрядам (байт - 8р полуслово - 16р, слова - 32 р. и т.д.), для контроля информации был применен укороченный код Голая (19, 11), содержащий 8 информационных и 11 контрольных разрядов. Этот код сохраняет все корректирующие свойства кода Голая. Закодированное слово в кодо Голея имеет вид F(x)Q(x)(x), (1) где Q(x) - восьмиразрядное информационное слово; X - одночлен одиннадцатой степени; R(x) - остаток от делания инфор. мационного слова Q(x) на порождагаций полином Р(х). Порождающий полином кода Голея Р(х) 110001110101. . Таким образом, разделив все возможные (всего 256) комбинации 8-разрядных информационных слов Q(x) на порождающий полином кода Голая Р(х), получим 256 остатков R(x), которые явля ются контрольными разрядами кода Голея Производящая матрица кода Голея в канонической форме (в которой информационные слова содержат единицу только в одном разряде) показана в таблице. Контрольные Информационные разряды разряды 000000000000000000 .000000011000111010 00. OOOOIOlOOlOOIltl OOOOOIOOIOIOIOOIOI 000010001 101 110 о oi о 0010000001 101 1001 0010000001 101 1001 1 о ) 0000001 1011001 10 1000000000 1 I 101 10 Любую строку ПОЛНОЙ производящей матрицы можно получить путем суммирования по модулю два строк канонической матрицы, в которых информационные единицы находятся в тех же позициях, что и в полной производящей матрице. Для.определения возникновения ошибки, а также для ее коррекции, в коде Голея, как и в любом другом систематическом блоковом коде, исполь зуется синдром ошибок S(x). Синдром ошибок определяется как сумма по модулю два между контрольными разрядами, записанными в устройстве R(x) и контрольными разрядами, полученными по считанному информационному слову R(к), т.с. S(X)R(X)@R(X). Для того, чтобы получить исправляющее кодовое слово N(x), которое наобходимо прибавить к считанному информационному слову О(х) с возможными ошибками, чтобы получить исходное информационное слово Q(x)Q4x)®N(x), необходимо сопоставить синдром ошибок S(x) исправляющий кодовое слово N(x), т.е. задать проверочную матрицу. Так как код Голая исправляет три и менее ошибки, то можно показать, что число исправляемых комбинаций ошибок, которые могут возникнуть в 19-разрядных (8 информационных +11 контрольных), составляет 1161. Но для нормального функционирова.ния устройства наобходимо исправлять только информационные разряды, которые несут полезную информацию. Общее количество исправляемых ошибок, которые могут возникать в 8 информационных разрядах, равно 92. Для того, чтобы получанное кодовое слово было исправлено, необходимо выполнение следующих условий: в контрольных, разрядах, соответствующих информационным разрядам, которые не поражены ошибками (одна комбинация) , может быть до трех ошибок; позтому этому информационному слову может соответствовать 221 возможная одиночная, двойная или тройная ошибка в контрольных разрядах в контрольных разрядах, которые соответствуют информационным разрядам поражанным одной ошибкой (восемь комбинаций), может быть не больше двух ошибок; поэтому каждому такому информационному слову может соответ$iствовать 66 возможных одиночных и двойных ошибок в контрольных разрядах ; в контрольньк разрядах (и, следовательно, в разрядах синдрома), кото рые соответствуют информационным разрядам, пораженным двумя ошибками (двадцать восемь комбинаций), может быть не больше одной ошибки; поэтому каждому этому информационному слову может соответствовать 11 возможньк одиночных ошибок; в разрядах синдрома, которые соот ,ветствуют информационным разрядам. пораженным тремя ошибками (56 комбинаций), не может быть ошибрк; поэтому каждому этому информационному сло ву, при условии, что оно может быть исправлено кодом Голая, должна соответствовать комбинация контрольных разрядов, не содержащая ни одной ошибки. Предлагаемое запоминающее устройство работает в двух режимах: записи и чтения. Режим записи. В этом режиме на входы коммутатора 1 поступает записываемое восьмиразрядное информационное слово. Одно временно на уцравляющий вход коммутатора 1 проходит управляющий сигнал записи, который разрешает передачу этого слова через коммутатор 1 на входы накопителя 3, а также на входы накопителя 2. Для 8-разрядного информационного слова имеется 256 различньк 11-разрядных кодовьгх комби наций контрольных разрядов кода Голея. Таким образом, с выхода накопителя 2 на информационные входы накопителя 4 поступает 11-тиразрядная кодовая комбинация контрольных разрядов, соответствующая 8 информациуже находятонным разрядам, которые 3. По сигнася на входах накопителя лу записи, поступившему на управляющие входы накопителей 3 и 4, происходит запись информационных и контрольных разрядов в накопители 3 и 4 по соответствующему адресу. На этом цикл записи заканчивается. Режим чтения. В этом режиме на управляющие вход накопителей 3 и 4 поступает сигнал чтения, на адресные входы - адрес чтения. Считанное с выходов накопителя 3 восьмиразрядное информацион6Ное слово поступает на входы коммутатора 1, на управляющий вход которого приходит управляющий сигнал чтения, которьш разрешает передачу информационного слова через этот коммутатор на входы накопителя 2. При этом 11 контрольных разрядов (см. режим записи) , соответствующих считанным информационным, поступают на одни из входов сумматоров 5, на другие входы которой поступают 11 контрольных разрядов непосредственно с выходов накопителя 4, На выходе сумматоров 5 формируется синдром ошибки. Указывающий произошла ли ошибка в процессе записи или считывания. При этом, если синдром ошибки на выходе сумматоров 5 равен нулю, т.е. контрольные разряды, полученные с выхода накопителя 2, по считанным информационным совпадают с контрольными разрядами, считанными непосредственно из накопителя 4, то ошибка отсутствует.. В случае, если имеется одна, две или три ошибки, возникающих при чтении или записи, синдром ошибки не равен нулю. Этот синдром поступает на входы накопителя 6. В этом накопителе защита - проверочная матрица кода Голея, которая по заданному синдрому ошибки формирует исправляющее кодовое слово, содержащее единицы в разрядах, которые в информационном слове поражены ошибками. С выхода накопителя 6 восьмиразрядное исправляющее кодовое слово, содержащее единицы в тех разрядах, которые поражены ощибками в информационном слове (или все нули, если ошибок в информационном слове нет), поступает на одни из входов сумматоров 7, на другие входы которой поданы восемь информационных разрядов с выхода накопителя 3. В результате сложения по модулю два информационного слова и исправляницего слова на информационном выходе устройства появляется исправленное считанное информационное слово. В случае возникновения более трех ошибок на выходе накопителя 6 появляется исправляющее слово из всех единиц, которое, поступая на входы элемента И-НЕ 8, вызывает появление на его выходе сигнала ошибки низким логическим уровнем, свидетельствующим о некорректируемости. считанной информации. На этом цикл чтения заканчивается .

.71111206

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

ОПЕРАТИВНОЕ ЗАПОМИНАЮЩЕЕ УСТРОЙСТВО С КОРРЕКЦИЕЙ ИНФОРМАЦИИ, содержащее накопитель основной информации и накопитель контрольной информации, одни из входов которых являются соответственно адресным и управляющим входами устройства, первую и вторую группы сумматоров по модулю два, отличающееся тем, что, с целью повьппения надежности устройства, в него введены постоянные накопители, элемент И-НЕ и коммутатор, один КЗ входов которого является информационным входом устройства, другие входы подключены соот ветственно к выходу накопителя основной информации и управляющему входу устройства, а выход соединен с информационным входом накопителя основной информации и входом первого постоянного накопителя, выход которого подключен к первым входам сумматоров по модулю два первой группы и информационному входу накопителя контрольной информации, выход которого соединен с вторыми входами сумматоров по модулю два первой группы, выходы которых подключены к входу второго постоянного накопителя, выход которого подключен к входам элемента И-НЕ и одним из входов сумматоров по модулю два второй группы, другие входы которых подключены к выходу накопите-I ля основной информации, а выходы явля ются информационным выходом устройст-, ва, контрольным выходом которого является выход элемента И-НЕ,