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

 

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

СОЮЗ СОВЕТСНИХ

СОЦИАЛИСТИЧЕСНИХ

РЕСГ1УБЛИН

09) Ol), (д) С 11 С 29/00

ОПИСАНИЕ ИЗОБРЕТЕНИЯ

ГОСУДАРСТВЕННЫЙ НОМИТЕТ СССР

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТИЙ

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (21) 3610961/24-24 (22) 24.06 ° 83 (46) 30.08.84. Вюл. № 32 (72) А.Г.Засыпкин, Г.М.Луцкий, А.Н.Долголенко и В.Д.Трунов (53) 681.327(088.8) (56) 1. Патент США ¹ 3573728, кл. 340-172.5, опублик. 1972.

2. Авторское свидетельство СССР

¹- 763975, кл. G 11 С 29/00, 1978 (прототип). (54)(57) ОПЕРАТИВНОЕ ЗАПОМИНАЮЩЕЕ

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

Г ляется информационным входом устройства, другие входы подключены соот— ветственно к выходу накопителя основной информации и управляющему входу устройства, а выход соединен с информационным входом накопителя основной информации и входом первого постоянного накопителя, выход которого подключен к первым входам сумматоров по модулю два первой группы и информационному входу накопителя контрольной информации, выход которого соединен с вторыми входами сумматоров по модулю два первой группы, выходы которых подключены к входу второго посто янного накопителя, выход которого Е подключен к входам элемента И-НЕ и одним из входов сумматоров по моду. лю два второй группы, другие входы которых подключены к выходу накопителя основной информации, а выходы явля ц ются информационным выходом устройства, контрольным выходом которого является выход элемента И-НЕ.

1111206

Изобретение относится к вычислительной технике и может быть использовано в качестве оперативного запоминающего устройства с повышенными корректирующими способностями.

Известно запоминающее устройство, содержащее блоки памяти, формирователи контрольных разрядо» кода Хемминга, формирователь проверочного слова, дешифраторы f1).

Недостатком этого устройства явля ется то, что в нем исправляется только одна ошибка.

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

20 соответственно с выходами основного регистра слова и первыми входами элементов ИЛИ первой группы, основные сумматоры по модулю два, подключен25 ные к основному регистру слова, основ ную схему сравнения, вторую группу элементов ИЛИ, элементы И и дополнительные регистр слова, схему сравнения и сумматоры по модулю два, причем одни из выходов основного регистра слова и выходы сумматоров по модулю два подключены ко вторым входам элементов ИЛИ первой группы, выходы сумматоров по модулю два соединены со входами дополнительной схемы сравне- З5 ния, выходы которой соединены с одним из входов элементов И, другие входы которых подключены к выходам основной схемы сравнения, выходы основного регистра слова соединены с одними из входов элементов ИЛИ второй группы, другие входы которых подключены к выходам элементов И, а выходы — ко входам дополнительного регистра слова, выходы которого соединены со вторыми входами элементов ИЛИ первой группы и одними из входов основной схемы сравнения, другие входы которой подключены к выходам основного регистра слова, входы дополнительных сумматоров по модулю два соединены с выходами основного регистра слова, (21 .

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

Поставленная цель достигается тем, что в оперативное запоминающее устройство с коррекцией информации, содержащее накопитель основной информации и накопитель контрольной инфор. мации, одни из входов которых явля— ются соответственно адресным и управляющим входами устройства, первую и вторую группы сумматоров по модулю два, введены постоянные накопители, элемент И-HE и коммутатор, один из вхопов которого является информационным входом устройства другие вхо7 ды подключены соответс твенно к выходу накопителя основной информации и управляющему входу устройства, а выход соединен с информационным входом накопителя основной информации и входом первого постоянного накопителя, выход которого подключен к первым входам сумматоров по модулю два первой группы и информационному входу накопителя контрольной информации, выход которого соединен со вторыми входами сумматоров по модулю два первой группы, выходы которых подключены ко входу второго .постоянного накопителя, выход которого подключен ко входам элемента И-НЕ и одним из входов сумматоров по модулю два второй группы, другие входы которых подключены к выходу накопителя основной информации, а выходы являются информационным выходом устройства, контрольным выходом которого является выход элемента И-НЕ.

На чертеже изображена структурная схема оперативного запоминающего устройства с коррекцией информации.

Устройство содержит коммутатор 1, первый постоянный накопитель 2, накопитель 3 основной информации, накопитель 4 контрольной информации, первую группу сумматоров 5 по модулю два, второй постоянный накопитель 6, вторую группу сумматоров 7 по модулю два и элемент И-НЕ 8.

Дпя устройства, способного исправлять до трех ошибок, накопители 3 и 4 выбраны соответственно восьми- и одиннадцатиразрядными, а акопители 2 и 6 имеют соответственно организацию

256х11 разрядов и 2048х8 разрядов.

В качестве корректирующего кода для данного устройства выбран код

Голея. Код Голея является совреме.. — . ным систематическим циклическим бло25

)в

Контр ол ьные разряды

Инф орм аци он ны е разряды

3 11112 коным кодом (23,11). Таким ооразом, для 12 информационных разрядов необходимо 11 контрольных. В связи с тем, что в подавляющем большинстве современных ЭВМ информационные форма- 5 ты кратны восьми разрядам (Г>айт — 8р., полуслово — 1бр, слова — 32 р. и т.д.), для контроля информации был применен укороченный код Голея (19, 11), содержащий 8 информационных и 11 контрольных разрядов. Этот код сохраняет все корректирующие свойства кода Голея. Закодированное слово в код:. Голея имеет вид

F(x) =Q(x) Х" +к(х), (1) 15 где С)(х) — восьмиразрядное информационное слово; х — одночлен одиннадцатой

1! степени;

R(x) — остаток от деления информационного слова Q(x) на порождающий полином

Р(х) .

Порождающий полином кода Голея

P (x) =11000!110101.

Таким образом, разделив все возможные (всего 256) комбинации 8-разрядных информационных слов Q(x) на порождающий полином кода Голея P(x), получим 256 остатков R(x),êîòoðûå явля- ЗО ются контрольными разрядами кода Голея.

Производящая матрица кода Голея в канонической форме (в которой информационные слова содержат единицу только в одном разряде) показана в таблице. а )а,,аа аа аааа(а а, н,,н в, в )а в Р,)на)н,)в

О О О О О О О О О О О О О О О О О О О.0000000110001110101

0000001010010011111.

0000010010101001011

00001000110111000)150

000 1000000 1 10 1 1001 1

01000000 l l 011001)00! О О О О О О О О О 1 1 1 ) 0 I I О 1

ОЬ 4

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

Для,определения возникновения ошибки, а также для ее коррекции, в коде Голея, как и в любом другом систематическом блоковом коде, исполь зуется синдром ошибок S(x). Синдром ошибок определяется как сумма по модулю два между контрольными разрядами, записанными в устройстве R(x) и контрольными разрядами, полученными по считанному информационному слову R (х), т.с.

S (x) =R(x)9R (õ) .

Для того, чтобы получить исправляющее кодовое слово N(x), которое необходимо прибавить к считанному информационному слову 0 (х) с возможными ошибками, чтобы получить исходное инфорл>ационное слово

Q(x)=Q "(x)QN(x), необходимо сопоставить синдром ошибок S(x) исправляющий кодовое слово N(x), т.е. задать проверочную матрицу. Так как код Голея исправляет три и менее ошибки, то можно показать, что число исправляемых комбинаций ошибок, которые могут возникнуть в 19-разрядных (8 информационных +11 контрольных), составляет 1161.

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

Для того, чтобы полученное кодовое слово было исправлено, необходимо выполнение следующих условий: в контрольных разрядах, соответствующих информационным разрядам, которые не поражены ошибками (одна комбинация), может быть до трех ошибок; поэтому этому информационному слову может соответствовать 221 возможная одиночная, двойная или тройная ошибка в контрольных разрядах; в контрольных разрядах, которые соответствуют информационным разрядам пораженным одной ошибкой (восемь комбинаций), может. быть не больше двух ошибок; поэтому каждому такому информационному слову может соотнет1111206 ствовать 66 возможных огиночных и двойных ошибок в контрольных разрядах; в контрольных разрядах (и, следовательно, в разрядах синдрома), кото S рые соответствуют информационным разрядам, пораженным двумя ошибками (двадцать восемь комбинаций), может быть не больше одной ошибки; поэтому каждому этому информационному слову может соответствовать 11 возможных одиночных ошибок; в разрядах синдрома, которые соот,ветствуют информационным разрядам, пораженным тремя ошибками (56 комби- 15 наций), не может быть ошибок; поэтому каждому этому информационному слову, при условии, что оно может быть исправлено кодом Голея, должна соответствовать комбинация контрольных 20 разрядов, не содержащая ни одной ошибки.

Предлагаемое запоминающее устройство работает в двух режимах: записи и чтения.

Режим записи.

В этом режиме на входы коммутато- ра 1 поступает записываемое восьмираэрядное информационное слово. Одно- 30 временно на управляющий вход коммутатора 1 проходит управляющий сигнал записи, который разрешает передачу этого слова через коммутатор 1 на входы накопителя 3, а также на вхо35 ды накопителя 2. Для 8-разрядного информационного слова имеется 256 различных 11-разрядных кодовых комби. наций контрольных разрядов кода Голея. Таким образом, с выхода накопи40 теля 2 на информационные входы нако- пителя 4 поступает 11-тиразрядная кодовая комбинация контрольных разрядов, соответствующая 8 информационным разрядам, которые уже находят45 ся на входах накопителя 3. По сигналу записи, поступившему на управляющие входы накопителей 3 и 4, происходит запись информационных и контрольных разрядов в накопители 3 и 4

50 по соответствующему адресу. На этом цикл записи заканчивается.

Режим чтения.

В этом режиме на управляющие входы накопителей 3 и 4 поступает сигнал

55 чтения, на адресные входы — адрес чтения. Считанное с выходов накопителя 3 восьмиразрядное информационное слово поступает на входы коммутатора 1, на управляющий вход которого приходит управляющий сигнал чтения, который разрешает передачу информационного слова через этот коммутатор на входы накопителя 2. При этом 11 контрольных разрядов (см. режим записи), соответствующих считанным информационным, поступают на одни из входов сумматоров 5, на другие входы которой поступают 11 контрольных разрядов непосредственно с выходов накопителя 4. На выходе сумматоров 5 формируется синдром ошибки, указывающийрпроизошла ли ошибка в процессе записи или считывания.

При этом, если синдром ошибки на выходе сумматоров 5 равен нулю, т.е. контрольные разряды, полученные с выхода накопителя 2, по считанным информационным совпадают с контрольными разрядами, считанными непосредственно из накопителя 4, то ошибка отсутствует. В случае, если имеется одна, две или три ошибки, возникающих при чтении или записи, синдром ошибки не равен нулю. Этот синдром поступает на входы накопителя 6.

В этом накопителе "защита" — проверочная матрица кода Голея, которая по заданному синдрому ошибки формирует исправляющее кодовое слово, содержащее единицы в разрядах, которые в информационном слове поражены ошибками. С выхода накопителя 6 восьмиразрядное исправляющее кодовое слово, содержащее единицы в тех разрядах, которые поражены ошибками в информационном слове (или все нули, если ошибок в информационном слове нет), поступает на одни из входов сумматоров 7, на другие входы которой поданы восемь информационных разрядов с выхода накопителя 3. В результате сложения по модулю два информационного слова и исправляющего слова на информационном выходе устройства появляется исправленное считанное информационное слово. В случае возникновения более трех ошибок на выходе накопителя 6 появляется исправляющее слово из всех единиц, которое, поступая на входы элемента И-НЕ 8, вызывает появление на его выходе сигнала ошибки низким логическим уровнем, свидетельствующим о некорректируемости, считанной информации.

На этом цикл чтения заканчивается.

1111206

Составитель В.Рудаков

Редактор С.Тимохина Техред А. Кикемезей КорректорЛ.Пилипенко

Заказ 6318/41 Тираж 574 Подписное

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

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

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

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