Запоминающее устройство с исправлением дефектов и ошибок Советский патент 1990 года по МПК G11C29/00 

кодирования-декодирования, блок 11 сумматоров по модулю два, второй коммутатор 13, шифратор 15, блок 16 постоянной памяти, выходной регистр

19, адресные входы-выходы 23 устройства, входы 24-35 управления, выходы одиночной 36 и многобитовой 37 ошибок. 3 ил.,1 табл.

Изобретение относится к вычислительной технике и может быть использовано в оперативных запоминающих устройствах для повышения надежности их работы. Цель изобретения - увеличение быстродействия. Устройство содержит информационные входы-выходы 1, входной регистр 2, блок 5 инверторов, дополнительный блок 7 ключей, первый коммутатор 9, блок 10 кодирования-декодирования, блок 11 сумматоров по модулю два, второй коммутатор 13, шифратор 15, блок 16 постоянной памяти, выходной регистр 19, адресные входы-выходы 23 устройства, входы 24-35 управления, выходы одиночной 36 и многобитовой 37 ошибок. 3 ил.

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

Цель изобретения - увеличение стродействия.

На фиг. 1 приведена структурная схема запоминающего устройства с исправлением дефектов и ошибок; на фиг. 2 - структурная схема шифратора; на фиг. 3 - структурная схема перво- го коммутатора.

Устройство (фиг. 1) содержит информационные входы-выходы 1, входной регистр 2, выходы блока 3 ключей, входы 4 второй группы блока 5 инверторов, входы 6 первой группы блока инверторов, дополнительный блок 7 ключей, выходы 8 второй группы дополнительного блока ключей, первый коммутатор 9, блок 10 кодирования-деко- дирования, блок 11 сумматоров по модулю два, выходы 12 первой группы дополнительного блока ключей, второй коммутатор 13, входы-выходы 14 второй группы блока кодирования-декоди- рования, шифратор 15, блок 16 постоянной памяти, входы 17 первой группы сумматора по модулю два, входы 18 первой группы первого коммутатора, выходной регистр 19, четвертые входы выходы 20 первого коммутатора, входы выходы 21 блока 22 оперативной памяти, адресные входы 23 устройства, первый вход 24 синхронизации, первый вход 25 задания режима, второй вход 26 задания режима, входы 27 задания режима группы, третий вход 28 задани режима, второй вход 29 синхронизации третий вход 30 синхронизации, четвертый вход 31 задания режима, четвер- тый вход 32 синхронизации, пятый вход 33 задания режима, вход 34 обращения, вход 35 записи-чтения, выходы одиночной 36 и многобитовой 37 ошибок.

Шифратор (фиг. 2) содержит регист 38 и 39 и второй блок 40 постоянной памяти.

5

5

0

0 5 0 0 5

5

Первый коммутатор (фиг. 3) содержит блок 41 ключей, блок 42 ключей и . блок 43 инверторов.

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

При первом цикле записи информации на шине 23 устанавливается код адреса, а на информационной шине 1 - информационное слово (например, шестнадцатиразрядное), подлежащее записи.

Сигналом по шине 24 это слово записывается во входной регистр 2. При отсутствии сигнала по шине 25 блок 5 инверторов не инвертирует информацию, поступающую на входы 4 и 6. Затем поступает сигнал по шине 26, открывает Олок 7 ключей и на выходах 8 появляется входное информационное слово (неинвертированное), а на выходах 12 - нули (в рассматриваемом примере четыре разряда).

На управляющих входах 27 появляется комбинация сигналов, соответствующая режиму кодирования входной информации, и на выходах 14 контрольных разрядов блока 10 появляются контрольные разряды соответствующего кода Хэмминга (в рассматриваемом примере шесть разрядов).

При отсутствии сигнала на шине 28 первый коммутатор 9 соединяет входы- выходы с входами-выходами 20.

Таким образом, входное информационное неинвертированное слово (16 разрядов), адресные информационные разряды - нули, (четыре разряда) и контрольные разряды Хэмминга (шесть разрядов) поступают через коммутатор .9 на входы-выходы 21 блока 22 оперативной памяти и под действием сигналов записи по шине 34 записываются в него по адресу 23.

Затем происходит первый цикл считывания информации.

Снимается сигнал с шины 26 и выключается блок 7 ключей. На шине 35 появляется сигнал считывания и инфор- мация с выходов 21 накопителя 22 через коммутатор 9 поступает на входы блока 10 декодирования. На входах 27

51

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

Затем выключается сигнал 35 и появляется сигнал по шине 28, при кото1 ром отключаются входы-выходы коммута тора 9 и соединяются входы 18 и входы-выходы 20. На входах 27 появляются сигналы, осуществляющие вывод . скорректированной информации, на выходах 14 - синдром ошибки, который под воздействием сигнала по шине 29 записывается в шифратор.

На выходах 36 и 37 ошибок появляются соответствующие сигналы. Если ошибки отсутствуют, то запись информации в запоминающее устройство заканчивается. Если на выходах 36 или 37 появляются сигналы ошибок, то устройство переходит к второму циклу записи-считывания информации. При этом на шине 25 появляется сигнал инвертирования, на шине 26 - сигнал включения блока ключей, на шинах 27- сигналы кодирования, с шины 28 снимается сигнал переключения. Инвертированная информация с выходов 8 поступает в блок 10 и через коммутатор 9 - на входы накопителя 22, с выходов 12 единичное слово также поступает в блок 10 и на входы накопителя 22, а с выходов 14 соответствующие контрольные разряды также поступают на входы накопителя. На шину 34 поступает сигнал записи и инвертированное информационное слово вместе с единичной информационной частью и соответствующими контрольными разрядами записывается в оперативный накопитель 22. Заканчиваются сигналы по шинам 34, 25, 26 и 27.

Устройство переходит к второму циклу считывания. На шине 35 появляется сигнал считывания и информация из накопителя 22 поступает на входы блока 10 и под воздействием сигналов по шинам 27 записывается в блок 10, затем на шине 28 появляется сигнал, переключающий коммутатор 9, на входы 27 поступает комбинация сигналов, осуществляющая вывод скорректированной информации из блока 10. На выходах 14 появляется синдром ошибок, который поступает на входы шифратора 15 и записывается в него под воздействием сигнала записи по шине 30. На выходах ошибок появляются соответствующие сигналы, поступающие на шины

36445

30 и 37, Если сигналы ошибок отсутствуют, то запись информации в запоминающее устройство заканчивается.

Если на шине 37 отсутствует сигнал многобитовой ошибки, ели на шине 36 присутствует сигнал одиночной ошибки и если в первом цикле считывания обнаружена лишь одиночная ошибЮ ка, то устройство переходит к третьему циклу записи-считывания (если в первом цикле записи-считывания были обнаружены многобитовые ошибки, а во втором цикле - однобитовые или много15 битовые, то это значит, что количество по данному адресу превышает корректирующую способность устройства - два дефекта).

Прекращаются сигналы по шинам 27

20 и 30.

В третьем цикле записи информации открывается блок 7 ключей сигналом по шине 25, на шинах 27 устанавливается комбинация сигналов кодирования и ин25 формация в прямом коде поступает на входы блока 10 кодирования и входы блока 11 сумматоров по модулю два вместе с нулевыми адресными информационными сигналами и соответствующи30 ми контрольными разрядами с выходов 14. Шифратор 15 по двум записанным в него синдромам одиночных ошибок прямого и инверсного информационных слов вырабатывает код адреса согла,, сующего слова, который поступает через второй коммутатор 13 на адресные входы постоянного накопителя 16, Согласующее слово (в данном примере двадцатишестиразрядное) поступает на

40 ДРУгие входы 17 блока I1 сумматоров по модулю два, где суммируется с информационным словом. С выхода блока 11 сумматоров информация поступает на входы 18 первого коммутатора 9 и

45 после прихода сигнала переключения по шине 28 поступает на входы-выходы 21 накопителя 22. По шине 34 поступает сигнал записи и суммированная информация записывается в накопитель 22.

5о Вместе с окончанием сигналов по шинам 34, 28 и 26 заканчивается цикл записи информации в запоминающее устройство.

Если по данному адресу в оперативном накопителе 22 имелось не более

55

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

При считывании итХфмдции с шин 23 в накопитель 22 поступает код адреса.

На шину 35 поступает сигнал считывания и информация с выхода 21 через первый коммутатор 9 поступает на входы блока 10 и записывается в него при поступлении соответствующих сигналов по шинам 2.

Затем на входы 27 поступают сигналы вывода скорректированной информации (исправляется один сбой, возникший при хранении информации в накопителе). Информация поступает на входы блока 11 сумматоров по модулю два, а сигналы адресных информационных разрядов поступают через второй коммутатор 13 при поступлении сигнала по шине 31 на адресные входы постоянного накопителя 16. Соответствующее согласующее слово из постоянного накопителя 16 (такое же, как использовалось при записи информации в оперативный накопитель) поступает на входы 17 блока сумматоров по модулю два,

4645

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

Согласующие слова записаны в виде матрицы С, которая обладает следующими свойствами: все строки матрицы являются кодовыми словами линейного кода, формируемого блоком 10 кодирования-декодирования в соответствии с матрицей Хэмминга 44.

5

0

5

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

Затем сигналом по шине 33 включается блок 3 ключей и считанная информация поступает на информационные шины 1.

В регистр 38 записывается синдром одиночной ошибки прямого слова, а в регистр 39 - синдром одиночной ошибки инверсного слова. Коды двух синдромов определяют адрес постоянного накопителя 40, где записан адрес согласующего слова матрицы С (см. таблицу), хранящийся в постоянном накопителе 16.

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

47

Коды адресов всех согласующих слов различны (первые четыре разряда каждого согласующего слова), два любых столбца матрицы С должны содержать все сочетания 1 и 0 (00, 01,10, 11), одна строка матрицы С должна быть единичной .

Подобная матрица С 48 такова, что при наличии двух любых дефектов в накопителе 22 по любому адресу в ней найдется кодовое слово, которое при сложении с информационным словом бусбоев у;

дет храниться по этому адресу без ошибок.

Пример. Предположим, что на входы 1 поступает для записи шестнадцатиразрядное слово 11)011000110001I. На выходах 12 будет добавлен адрес 0000 и после кодирования в блоке 10 кодирования на выходах 14 появятся контрольные разряды 1111JO.

3 накопитель 22 запишется двадцатишестиразрядное слово х. 49. Если при считывании этого же слова у из накопителя 22 в нем нет ошибок (50), то при декодировании в блоке 10 синд- 15 информационная часть записывается в ром 51 равен нулю (все разряды сннд- выходной регистр 19.

57 декодер ошибок не обнаруживает и синдром равен нулю.

При считывании слова, в котором 5 возник один сбой, например во второ разряде, у 58 при декодировании син ром равен 111110, что указывает оши ку во втором разряде. После исправления информация во втором разряде будет восстановлена (59). Первые че тыре разряда слова 1100 являются ад ресом строки матрицы С 55, которая считывается из постоянного накопителя 16, складывается со словом 59 и

10

рома равны нулю). Если в данной ячейке накопителя 22 есть дефекты, например в шестом разряде (помечен звездочкой), вместо 1 считывается постоянно О, то при считывании и декодировании слова у. (синдром ошибки 52) на выходах 14 блока 10 при-декодировании появляется синдром 110100 который записывается в шифратор 15. Процесс записи продолжается.Входное слово инвертируется блоком 5 инверторов и в виде слова х; 53 11П 0001001П 001I10000000 записывается в накопитель 22.

Если после считывания и декодирования инвертированного слова у 54 будет обнаружена одиночная ошибка, например в тринадцатом разряде (вместо единицы постоянно считывается ноль), то синдром будет равен 011010.

Коды разрядов синдромов считанного прямого 52 и инверсного 54 слов определяют строку матрицы С 48 (строка должна иметь ноль в шестом столбце и ноль в тринадцатом столбце матрицы С 48).

Данный подбор сочетаний синдромов и строк матрицы С делается заранее при программировании постоянного накопителя 40 шифратора 15. В данном случае нужной строкой матрицы С является слово 55 1100111000000000110110000J, в котором в шестом разряде будет единица, а в тринадцатом - ноль.

После сложения строки матрицы С; и исходного слова х; в блоке сумматоров 1 1 по модулю два получим слово 56 1100000011000110111001111, которое запишется в накопитель 22 без ошибок.

При считывании согласованного ело ва без возникновения при хранении

536445

сбоев у;

10

15 информационная часть записывается в выходной регистр 19.

57 декодер ошибок не обнаруживает и синдром равен нулю.

При считывании слова, в котором 5 возник один сбой, например во втором разряде, у 58 при декодировании синдром равен 111110, что указывает ошибку во втором разряде. После исправления информация во втором разряде будет восстановлена (59). Первые четыре разряда слова 1100 являются адресом строки матрицы С 55, которая считывается из постоянного накопителя 16, складывается со словом 59 и

10

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

изобретения

Формул

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

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

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

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

11

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

15

« 1053644512

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

20

30

устройства.

фиг.2

фигЗ