Оперативное запоминающее устройство с коррекцией информации

(д) С 11 С 29/00 ЕТЕНИ В ГОСУДАРСТВЕННЫЙ НОМИТЕТ СССРПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТИЙ ОПИСАНИЕ ИЗ АВТОРСКОМУ СВИДЯТ(56) 1. Патент США Ф 3573728,кл. 340-172.5, опублик. 1972.2. Авторское свидетельство СССРУ 763975, кл, С 11 С 29/00, 1978(54)(57) ОПЕРАТИВНОЕ ЗАПОМИНАЮЩЕЕУСТРОЙСТВО С КОРРЕКЦИЕЙ ИНФОРМАЦИИ,содержащее накопитель основной инфор-.мации и накопитель контрольной информации, одни из входов которых являются соответственно адресным иуправляющим входами устройства, первую и вторую группы сумматоров по модулю два, о т л и ч а ю щ е е с ятем, что, с целью повьппения надежности устройства, в него введены постоянные накопители, элемент И-НЕ и коммутатор, один из входов которого явГ ляется информационным входом устройства, другие входы подключены соот - ветственно к выходу накопителя основной информации и управляющему входу устройства, а выход соединен с информационным входом накопителя основной информации и входом первого постоянного накопителя, выход которого подключен к первым входам сумматоров по модулю два первой группы и информационному входу накопителя контрольной информации, выход которого соединен с вторыми входами сумматоров по модулю два первой группы, выходы которых подключены к входу второго посто янного накопителя, выход которогоподключен к входам элемента И-НЕ и одним из входов сумматоров по моду. лю два второй группы, другие входы которых подключены к выходу накопите" ля основной информации, а выходы явля р ются информационным выходом устройства, контрольным выходом которого является выход элемента И-НЕ.Изобретение относится к вычислительной технике и может быть использовано в качестве оперативного запоминающего устройства с повышеннымикорректирующими способностями.Известно запоминающее устройство,содержащее блоки памяти, формирователи контрольных разрядо кода Хемминга, формирователь проверочногослова, дешифраторы 1.Недостатком этого устройства является то, что в нем исправляетсятолько одна ошибка,Наиболее близким к данному изоб 1 О ретению является запоминающее устройство с обнаружением и исправлением ошибок, содержащее накопитель, подключенный к адресному блоку, блоку управления и блоку записи-считывания, входы и выходы которого соединены20 соответственно с выходами основного регистра слова и первыми входами элементов ИЛИ первой группы, основные сумматоры по модулю два, подключен 25 ные к основному регистру слова, основ ную схему сравнения, вторую группу элементов ИЛИ, элементы И и дополнительные регистр слова, схему сравнения и сумматоры по модулю два, причем одни из выходов основного регистра слова и выходы сумматоров по модулю два подключены ко вторым входам элементов ИЛИ первой группы, выходы сумматоров по модулю два соединены со входами дополнительной схемы сравне ния, выходы которой соединены с одним из входов элементов И, другие входы которых подключены к выходам основной схемы сравнения, выходы основного регистра слова соединены с одними 10 из входов элементов ИЛИ второй группы, другие входы которых подключены к выходам элементов И, а выходы - ко входам дополнительного регистра слова, выходы которого соединены со вторыми входами элементов ИЛИ первой группы и одними из входов основной схемы сравнения, другие входы которой подключены к выходам основного регистра слова, входы дополнительных 50 сумматоров по модулю два соединены с выхолами основного регистра слова, 21 .Недостатками этого устройства являются его малая обнаруживающая и корректирующая способность и большие затраты оборудования, что снижает надежность устройства. Цельк изобретения является повышение надежности устройства,Поставленная цель достигается тем,что в оперативное запоминающее устройство с коррекцией информации, содержащее накопитель основной информации и накопитель контрольной инфор.мации, одни из входов которых явля -ются соответственно адресным и управ.ляющим входами устройства, первую ивторую группы сумматоров по модулюдва, введены постоянные накопители,элемент И-НЕ и коммутатор, один извходов которого является информационным входом устройства другие вхо 7ды подключены соответственно к выходу накопителя основной информациии управляющему входу устройства,а выход соединен с информационнымвходом накопителя основной информациии входом первого постоянного накопителя, выход которого подключен к первым входам сумматоров по модулю двапервой группы и информационному входу накопителя контрольной информации,выход которого соединен со вторымивходами сумматоров по модулю два первой группы, выходы которых подключены ко входу второго постоянного накопителя, выход которого подключен ковходам элемента И-НЕ и одним из входов сумматоров по модулю два второйгруппы, другие входы которых подключены к выходу накопителя основнойинформации, а выходы являются информационным выходом устройства, контрольным выходом которого являетсявыход элемента И-НЕ.На чертеже изображена структурнаясхема оперативного запоминающегоустройства с коррекцией информации.Устройство содержит коммутатор 1,первый постоянный накопитель 2, накопитель 3 основной информации, накопитель 4 контрольной информации, первуюгруппу сумматоров 5 по модулю два,второй постоянный накопитель 6, вторую группу сумматоров 7 по модулю дваи элемент И-НЕ 8.Дйя устройства, способного исправлять до трех ошибок, накопители 3 и 4выбраны соответственно восьми- иодиннадцатиразрядными, а акопители 2и 6 имеют соответственно организацию256 х 11 разрядов и 2048 х 8 разрядов.В качестве корректирующего кодадля данного устройства выбран кодГолея. Код Голея является совремел в .ным систематическим циклическим бло35 Контрольныеразряды Информационныеразряды 3 11112коным кодом (23,11). Таким ооразом,для 12 информационных разрядов необходимо 11 контрольных, В связис тем, что в подавляющем большинствесовременных ЭРМ информационные форматы кратны восьми разрядам (Гайт - 8 р.,полуслово - 1 бр, слова - 32 р,и т.д,), для контроля информации былприменен укороченный код Голея(19, 11), содержащий 8 информационных и 11 контрольных разрядов. Этоткод сохраняет все корректирующиесвойства кода Голея. Закодированное словО в кодс Голея имеет видГ(х)=Я(х) Х +К(х), (1) 15где С 1(х) - восьмиразрядное информационное слово;х - одночлен одиннадцатой1степени;К(х) - остаток от деления информационного слова Я(х)на порождающий полиномР (х),Порождающий полином кода ГолеяР(х) =11000110101.25Таким образом, разделив все возможные (всего 256) комбинации 8-разрядных информационных слов Я(х) напорождающий полином кода Голея Р(х),получим 256 остатков К(х),которые явля- З 0ются контрольными разрядами кода Голея.Производящая матрица кода Голеяв канонической форме (в которой информационные слова содержат единицутолько в одном разряде) показанав таблице. 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0.000000011000 11010145 О О О О О О 1 О 1 О О 1 О О 1 1 1 1 1 О О О О О 1 О О 1 О 1 О 1 О О 1 О 1 10 0 0 0 1 0 0 0 1 1 0 1 1 1 0 0 01 50 00010000001 О 10011 О О 1 О О О О О О 1 1 О 1 1 О О 1 1 055 0 1 О О О О О О 1 1 О 1 1 О О 1 1 О О00000000011 10 101 оь 4 Любую строку полной производящей матрицы можно получить путем суммирования по модулю два строк канонической матрицы, в которых информационные единицы находятся в тех же позициях, что и в полной производящей матрице.Для определения возникновения ошибки, а также для ее коррекции, в коде Голея, как и в любом другом систематическом блоковом коде, исполь зуется синдром ошибок Б(х). Синдром ошибок определяется как сумма по модулю два между контрольными разрядами, записанными в устройстве К(х) и контрольными разрядами, полученными по считанному информационному слову К(х), т.с .Б (х) =К(х)9 К (х) .Для того, чтобы получить исправляющее кодовое слово И(х), которое необходимо прибавить к считанному информационному слову 1 (х) с возможными ошибками, чтобы получить исходное информационное слово Я(х)=О "(х)ЙИ 1(х), необходимо сопоставить синдром ошибок Б(х) исправляющий кодовое слово М(х), т.е. задать проверочную матрицу. Так как код Голея исправляет три и менее ошибки, то можно показать, что число исправляемых комбинаций ошибок, которые могут возникнуть в 19-разрядных (8 информационных +11 контрольных), составляет 1161.Но для нормального Функционирования устройства необходимо исправлять только информационные разряды, которые несут полезную информацию. Общее количество исправляемых ошибок, которые могут возникать в 8 информационных разрядах, равно 92. Для того, чтобы полученное кодовое слово было исправлено, необходимо выполнение следующих условий:в контрольных разрядах, соответствующих информационным разрядам, которые не поражены ошибками (одна комбинация), может быть до трех ошибок; поэтому этому информационному слову может соответствовать 221 возможная одиночная, двойная или тройная ошибка в контрольных разрядах;в контрольных разрядах, которые соответствуют информационным разрядам пораженным одной ошибкой (восемь комбинаций), может. быть не больше двух ошибок; поэтому каждому такому информационному слову может соотнет 1111206ствовать 66 возможных огиночных и двойных ошибок в контрольных разрядах;в контрольных разрядах (и, следовательно, в разрядах синдрома), кото 5 рые соответствуют информационным разрядам, пораженным двумя ошибками (двадцать восемь комбинаций), может быть не больше одной ошибки; поэтому каждому этому информационному слову может соответствовать 11 возможных одиночных ошибок;в разрядах синдрома, которые соот,ветствуют информационным разрядам, пораженным тремя ошибками (56 комби наций), не может быть ошибок; поэтому каждому этому информационному сло. ву, при условии, что оно может быть исправлено кодом Голея, должна соответствовать комбинация контрольных 20 разрядов, не содержащая ни одной ошибки.Предлагаемое запоминающее устройство работает в двух режимах: записи и чтения.Режим записи,В этом режиме на входы коммутато- ра 1 поступает записываемое восьмираэрядное информационное слово. Одно временно на управляющий вход коммутатора 1 проходит управляющий сигнал записи, который разрешает передачу этого слова через коммутатор 1 на входы накопителя 3, а также на вхо 35 ды накопителя 2. Для 8-разрядного информационногослова имеется 256 различных 11-разрядных кодовых комби наций контрольных разрядов кода Голея. Таким образом, с выхода накопи.40 теля 2 на информационные входы нако- пителя 4 поступает 11-тиразрядная кодовая комбинация контрольных разрядов, соответствующая 8 информационным разрядам, которые уже находят 45 ся на входах накопителя 3. По сигналу записи, поступившему на управляющие входы накопителей 3 и 4, происходит запись информационных и контрольных разрядов в накопители 3 и 450 по соответствующему адресу. На этом цикл записи заканчивается.Режим чтения.В этом режиме на управляющие входы накопителей 3 и 4 поступает сигнал55 чтения, на адресные входы - адрес чтения. Считанное с выходов накопителя 3 восьмиразрядное информационное слово поступает на входы коммутатора 1, на управляющий вход которогоприходит управляющий сигнал чтения,который разрешает передачу информационного слова через этот коммутаторна входы накопителя 2. При этом 11контрольных разрядов (см. режим записи), соответствующих считанныминформационным, поступают на одни извходов сумматоров 5, на другиевходы которой поступают 11 контрольных разрядов непосредственно с выходов накопителя 4, На выходе сумматоров 5 формируется синдром ошибки,указывающийрпроизошла ли ошибкав процессе записи или считывания,При этом, если синдром ошибки на выходе сумматоров 5 равен нулю, т.е.контрольные разряды, полученные с выхода накопителя 2, по считанныминформационным совпадают с контрольными разрядами, считанными непосредственно из накопителя 4, то ошибкаотсутствует. В случае, если имеетсяодна, две или три ошибки, возникающих при чтении или записи, синдромошибки не равен нулю. Этот синдромпоступает на входы накопителя 6.В этом накопителе "защита" - проверочная матрица кода Голея, которая позаданному синдрому ошибки формируетисправляющее кодовое слово, содержащее единицы в разрядах, которыев информационном слове поражены ошибками, С выхода накопителя 6 восьмиразрядное исправляющее кодовое слово, содержащее единицы в тех разрядах, которые поражены ошибками в информационном слове (или все нули,если ошибок в информационном словенет), поступает на одни из входовсумматоров 7, на другие входы которойподаны восемь информационных разрядов с выхода накопителя 3. В результате сложения по модулю два информационного слова и исправляющего слована информационном выходе устройствапоявляется исправленное считанноеинформационное слово, В случае возникновения более трех ошибок на выходе накопителя 6 появляется исправляющее слово из всех единиц, которое,поступая на входы элемента И-НЕ 8,вызывает появление на его выходе сигнала ошибки низким логическим уровнем, свидетельствующим онекорректируемости, считанной информации.Иа этом цикл чтения заканчивается.Заказ 6318/41 Тираж 574 Подписное ВНИИПИ Государственного комитета СССР по делам изобретений и открытий 113035, Москва, Ж, Раушская наб., д. 4/5Филиал ППП "Патент", г.ужгород, ул.Проектная, 4 Таким образом, в предлагаемом устройстве исправляется не менее трех ошибок,а при большем числе ошибок выдается сигнал о некорр ектируемости информации,1