Устройство для исправления дефектов и ошибок в запоминающем устройстве

(5)5 П НИЕ ИЗОБРЕТЕН К АВТОРСКО ВИДЕТЕЛЬС в О 0 р ГОСУДАРСТВЕННЫЙ КОМИТЕТПО ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМПРИ ГКНТ СССР(56) Авторское свидетельство СССРМ 1048520, кл. 6 11 С 29/00, 1983,Авторское свидетельство СССРМ 1536445, кл, 6 11 С 29/00, 1987,(54) УСТРОЙСТВО ДЛЯ ИСПРАВЛЕНИЯДЕФЕКТОВ И ОШИБОК В ЗАПОМИНАЮЩЕМ УСТРОЙСТВЕ(57) Изобретение относится к вычислительной технике и может быть использовано воперативных запоминающих устройствах,Цель изобретения - повышение быстродействия и достоверности работы устройства,Устройство содержит блок оперативной памяти 1, адресные входы 2, входной регистр 3, блок ключей 4, информационные входы- выходы 5, выходной регистр 6, блок постоянной памяти 7, блок 8 сумматоров по модулю два, блок кодирования-декодирования 9, входы группы задания режима 10, сигнальные выходы 11 первой группы, коммутатор 12, вход 13 задания режима, входы обращения 14 и записи-чтения 15, блок 16 ключей, блок 17 инверторов, входы задания режима 18-20, входы синхронизации 21 и 22, регистр 23, блок 24 сумматоров по модулю два, блок элементов И 25, блоки 26 выбора согласующего слова, формирователь 27 согласующего слова, блок 28 сумматоров по модулю два, сигнальные выходы 23, вход синхронизации 30, вход задания режима 31, сигнальный выход 32, вход синхронизации 33. Устройство обеспечивает исправления Х дефектов оперативного накопителя и одного сбоя, возникающего при сохранении информации, 5 ил 1 табл,5 10 15 20 25 30 35 40 45 50 55 следующим образом,Изобретение относится к вычислительной технике и может быть использовано в оперативных запоминающих устройствах.Цель изобретения - повышение быстродействия и достоверности работы устройства.На фиг,1 приведена структурная схема устройства; на фиг.2 - схема блока выбора согласующего слова; на фиг,3 - схема формирователя согласующего слова; на фиг.4 - схема коммутатора; на фиг.5 - временные диаграммы работы устройства.В таблице приведены матрицы элемента (Н и С) и примеры коррекции информации.Устройство для исправления дефектов и ошибок в запоминающем устройстве (фиг,1) содержит блок 1 оперативной памяти (накопитель), адресные входы 2, входной регистр 3, первый блок 4 ключей, информационные входы-выходы 5 устройства, выходной регистр 6, блок 7 постоянной памяти, первый блок 8 сумматоров по модулю два, блок 9 кодирования-декодирования, входы 10 группы задания режима, сигнальные выходы группы 11 первой, коммутатор 12, первый вход 13 задания режима, вход 14 обращения, вход 15 записи-чтения, блок 16 ключей, блок 17 инверторов, второй, третий и четвертый входы 18-20 задания режима, первый 21 и второй 22 входы синхронизации, регистр 23, второй блок 24 сумматоров по модулю два, блок 25 элементов И, блоки 26 выбора согласующего слова, формирователь 27 согласующего слова, третий блок 28 сумматоров по модулю два, сигнальные выходы 29 второй группы устройства, третий вход 30 синхронизации, пятый вход 31 задания режима, сигнальный выход 32 и четвертый вход 33 синхронизации.Блок выбора согласующего слова (фиг.2) содержит блоки 34-36 сумматоров по модулю два, блок 37 элементов И, элемент ИЛИ 38, регистр 39 и элемент И 40,Формирователь согласующего слова (фиг,3) содержит элемент ИЛИ 41, элементы НЕ 42, элемент И 43, элементы И-НЕ 44 и ключи 45Коммутатор (фиг.4) содержит блоки ключей 46 и 47 и элемент НЕ 48,Устройство работает следующим образом,В режиме записи в первом цикле записи информации на входах 2 устанавливается код адреса, а на информационных входах-выходах 5 информационное слово (например, шестнадцатиразрядное), подлежащее записи. Сигналом по входу 21 это слово записывается во входной регистр 3, С выхода регистра 3 информационное слово через блок 16 ключей (на вход управления блока 16 поступает сигнал разрешения с входа 19) поступает на вторые входы блока 9 кодирования-декодирования и регистра 23, на первые входы которых поступают сигналы логического нуля с первых входов блока 16 ключей (количество разрядов равно А).На входы 10 подается комбинация сигналов, соответствующая режиму кодирования входной информации, и на контрольных входах-выходах блока 9 появляются контрольные разряды соответствующего кода Хэмминга (в рассматриваемом примере шесть разрядов), которые поступают на входы регистра 23. Сигналом по входу 30 информация записывается в регистр 23.Таким образом, входное информационное слово (К = 16 разрядов), адресные информационные разряды - нули (А = 4 разряда) и контрольные разряды (К = 6 разрядов) с выходов. регистра 23 через вторые входы блока 24 сумматоров по модулю два (на первых входах присутствуют сигналы логического нуля) через блок 17 инверторов(режим неинвертирования) и через коммутатор 12 поступают на входы-выходы блока 1 оперативной памяти и под действием сигналов записи по входах 14 и 15 записываются в него по входу 2,Затем происходит первый цикл считывания информации, Снимается сигнал разрешения с входа 19. На вход 14 подается сигнал для считывания, и информация с выходов накопителя 1 через коммутатор 12 (на вход 13 задания режима поступает сигнал управления) поступает на первые входы блока 28 сумматоров по модулю два. На вторые входы блока 28 поступает информация записываемая, в накопитель 1. Сигналы несовпадения с выхода блока 28 (блок определяет любое количество ошибок) поступают на выходы 29, на первые входы блока 25 элементов И и блоков 26 выбора согласующего слова, на третьи входы блоков 26 поступают сигналы с выхода блока 25, навторые входы блоков 26 и блока 25 поступает записываемая в накопитель 1 информация. Если сигналы несовпадения(ошибки) на выходах 29 в момент считывания из накопителя 1 отсутствуют, то режим записи информации в запоминающее устройство заканчивается. Если на выходах 29 присутствуют сигналы ошибок, то сигналом по входу 33 фиксируется состояние блоков 26 выбора согласующего слова, С входа 13 снимается сигнал управления,Каждый из блоков 26 (фиг.2) работает40 45 50 55 Количество блоков 26 соответствует числу строк И согласующей матрицы С. В блоке 34 происходит сравнение записываемой информации и строки согласующего слова. Блоки 35 производят согласование типа ошибки при считывании из накопителя (нулевой сигнал вместо единичного или наоборот) с учетом записываемой информации производится в блоке 25 элементов И) и сигналов с выхода блока 34. Блоки 37 производят пропуск сигналов только в тех разрядах, где есть ошибки, и блоки 36 производят проверку наличия единицы на вторых входах в тех разрядах, где есть ошибки. Наличие единицы свидетельствует о согласовании в данном разряде записываемой информации с согласующим словом, При согласовании во всех разрядах на входах элемента ИЛИ 38 будут одни нули и сигналом по входу 33 в регистр 39 запишется единица.Далее устройство переходит к второму циклу записи-считывания информации. На вход 20 подается сигнал инвертирования. Инвертированная информация с выхода блока 17 инверторов через коммутатор 12 поступает на входы-выходы накопителя 1 и под действием сигналов записи по входам 14 и 15 записывается в него по тому же входу 2.Устройство переходит к второму циклу считывания.Второй цикл считывания и работа блоков 26 происходит аналогично первому циклу считывания, В тех блоках 26, где прямая и инверсная информация идефекты накопителя 1 согласуются с согласующим словом, в регистр 39 запишется две единицы, Элемент И 40 выдает единичный сигнал на выход блоков 26, который поступает на вход элемента ИЛИ 41 устройства 27 формирования согласующего слова, При наличии хотя бы одной единицы на входе элемента ИЛИ 41 на вход 32 устройства поступает единичный сигнал. Это свидетельствует о том, что имеется согласующее слово и возможна коррекция дефектов накопителя 1 по данному адресу.Устройство переходит к третьему, контрольному циклу записи-считывания.На вход 31 подается сигнал, который является разрешающим для выдачи формирователя 27 согласующего слова.Формирователь 27 (фиг.3) работает следующим образом.При отсутствии на входах и управляющем входе сигналов элемент И 43 нулевым выходным сигналом открывает первый ключ 45. На инверсные выходы этого ключа выдается нулевое слово, которое поступает на 5 10 15 20 25 30 35 первые входы блока 24 и не влияет на прохождение информации по вторым входам.Остальные ключи 45 в количестве, равном числу строк М согласующей матрицы С, за счет отсутствия сигнала на входе 31 находятся в отключенном (третьем) состоянии. После второго цикла записи-считывания на один или несколько входов формирователя 27 поступают сигналы (если найдено согласующее слово), На вход 31 устройства также подается сигнал, Первый ключ 45 закрывается (переходит в третье состояние). Если сигнал на входах формирователя 27 один, то соответствующий элемент И-НЕ 44 выходным сигналом открывает соответствующий ключ 45, На входы этого ключа 45 подаются постоянные инверсные сигналы (константы), Они соответствуют согласующему слову блока 26 и, соответственно, матрице С, с выхода которой поступаетданный сигнал на управляющий элемент И-НЕ 44 данного ключа 45. С инверсного выхода ключа 45 согласующее слово подается на первые входы блока 24.Если сигналов на входах формирователя 27 несколько, то открывается ключ 45, соответствующий сигналу (т.е, входу) с меньшим порядковым номером, Число входов формирователя 27 равно М - числу строк согласующей матрицы. Остальные ключи блокируются с помощью элементов НЕ 42, Таким образом выбирается одно из нескольких возможных согласующих слов.Третий, контрольный цикл записи.В блоке 24 входная информация суммируется с согласующим словом, Результирующая информация с выходов блока 24 через блок 17 инверторов (находится в режиме неинвертирования) и коммутатор 12 поступает на входы-выходы накопителя 1 и под действием сигналов записи по входам 14 и 15 записывается в него по тому же входу 2.Третий, контрольный цикл считывания происходит аналогично первому циклу, Если ошибки на входе 29 в момент считывания отсутствуют, то согласование имеющихся дефектов по данному адресу осуществлено правильно и запись данного информационного слова заканчивается.Таким образом, если матрица С рассчитана на Х ошибок и по данному адресу в накопителе 1 имелось не более Х дефектов, то гарантируется запись информации в согласованном с дефектами виде не более чем за три цикла записи-считывания. Кроме этого, возможно согласование большего, чем Х количества дефектов. Это произойдет, если код записываемой информации и код дефектов совпадает с согласующим словом, что показано на примере.При считывании информации с входа 2 в накопитель 1 поступает код адреса, На вход 14 поступает сигнал для считывания и информация с выходов накопителя 1 через коммутатор 12 ( на вход 13 поступает сигнал управления) поступает на входы блока 9 и записывается в него при поступлении соответствующих сигналов по входам 10, Затем на входы 10 поступают сигналы вывода с корректированной информации (исправляется один сбой, если он произошел при хранении информации в накопителе 1), Информация поступает на вторые входы блока 8 сумматоров по модулю два, а сигналы адресных информационных разрядов (А разрядов) поступают на адресные входы блока 7 постоянной памяти, Соответствующее согласующее слово из постоянного блока 7 (такое же, как использовалось при записи информации в оперативный накопитель 1) поступает на первые входы блока 8 сумматоров по модулю два, на выходе которого появляется исправленное информационное слово, которое записывается в выходной регистр 6 под воздействием сигнала на входе 22. Затем сигналом по входу 18 включается блок 4 ключей и считанная информация поступает на информационные входы-выходы 5,При отсутствии сигнала на входе 13 устройства выходы блока 17 инверторов подключены через блок 47 ключей к накопителю 1, появление сигнала на входе 13 открывает блок 46 ключей и информация с выхода накопителя 1 поступает на входы блока 28 и на другие входы.В таблице показаны примеры образующей матрицы модифицированного кода Хэмминга для двадцатиразрядного слова, шестнадцатиразрядного информационного слова 50 с четырехразрядной адресной информационной частью 51, Для кодирования данного двадцатиразрядного слова используются шесть контрольных разрядов 52,Особенностью данной матрицы Хэмминга является нечетность всех столбцов, что позволяет определять двух-четырехкратные ошибки и ошибки большей кратности.Согласующие слова записаны в виде матрицы С, которая обладает следующими свойствами: все строки матрицы являются кодовыми словами линейного кода, формируемого блоком 8 кодирования-декодирования в соответствии с матрицей Хэмминга 49.Коды адресов всех согласующих слов различны (первые четыре разряда А каждого согласующего слова), два любых столбца матрицы С должны содержать все сочета 10 15 20 25 30 35 40 45 50 55 ния 1 и 0 (00, 01, 10, 11), одна строка матрицыС должна быть единичной,Подобная матрица Стакова, что при наличии двух любых дефектов в накопителе 1 по любому адресу в ней найдется кодовое слово, которое при сложении с информационным словом будет храниться по этому адресу без ошибок,За счет построения блоков 26 выбора и формирователей 27 комбинационным способом возможно исправление и большегоколичества дефектов, как указывалось,П р и м е р. Предположим, что на входы 5 поступает для записи шестнадцатиразрядное слово 1110110001100011. На выходах будет добавлено 0000 и после кодирования в блоке 9 кодирования на выходах появятся контрольные разряды Р111110.В накопитель 1 запишется двадцатишестиразрядное слово Х 54. Если при считывании этого же слова У из накопителя 1 в немнет ошибок (55), то при сравнении в блоке28 на выхода 29 будут одни нули. Если вданной ячейке накопителя 1 есть дефекты,например в шестом разряде (помечен звездочкой) вместо "1" считывается постоянно"0", то при считывании слова У 56 на выходах 29 будет "1" в шестом разряде.В первом, втором, четвертом и шестомблоках 26 выбора согласующего слова в регистры 39 будет записана единица в соответствии с местом (шестой разряд) и видом("0" вместо "1") дефекта, Здесь имеется ввиду, что на вторые входы блоков 34 подаютсяпотенциальные сигналы в соответствии содной из строк матрицы С. В блоке 34первого блока 26 сигналы соответствуютпервой строке матрицы С, второго блока26 эти сигналы соответствуют второй строкеи т,дт.е, имеется девять блоков 26 и, соответственно, девять ключей 45 (не считаяпервого, на входы которого подаются "1"),на входы которых подаются инверсные сигналы, соответствующие строкам матрицы С 53,Процесс записи продолжается. Входное слово инвертируется блоком 17 инверторов и в виде слова Х 5711110001001110011100000001 записывается в накопитель 1,Если после считывания инверсногослова У 58 на выходах 29 будет "1" в тринадцатом разряде (вместо "1" постоянносчитывается "0"), то в регистры 39 второго ипятого блоков 26 будет записана вторая единица, Таким образом на выходе второго ипятого блоков 26 будут единичные сигналы.В формирователе 27 открыт ключ 45 соответствующий второму входу (т.е. второмувыходу блоков 26). За счет элемента НЕ 42 все ключи 45, начиная с ключа 45, соответствующего третьему входу, будут закрыты. В итоге с выходов 27 будет поступать слово С 59 11001110000000001101100001, в котором в шестом разряде будет единица, а в тринадцатом нуль.После сложения строки матрицы С и исходного слова Х в блоке 24 сумматоров по модулю два получим слово 60 1100000011000110111001111, которое запишется в накопитель 1 без ошибок,При считывании согласованного слова без возникновения при хранении сбоев У 61 декодер ошибок не обнаружит и синдром равен нулю (сигналы на выходах 11 нулевые),При считывании слова, в котором возник один сбой, например во втором разряде % 62, при декодировании синдром равен 111110, что указывает ошибку во втором разряде, На выходе одиночной ошибки 11-1 будет единичный сигнал (выход 11-2 многократной ошибки). После исправления во втором разряде информация будет восстановлена 63. Первые четыре разряда слова 1100 являются адресом строки (59) матрицы С, которая считывается из постоянного накопителя 7 (в накопителе прошита такая же матрица С), складывается с словом 63 и информационная часть записывается в выходной регистр 6.Это слово соответствует записываемому слову 54.Рассмотрим пример с исправлением ошибок в случае многократных дефектов, Предположим, в накопитель 1 записывается то же слово 54, а считывается слово У; 64 с дефектами в пятом - седьмом разрядах, В регистры 39 второго и четвертого блоков 26 будет записана единица, При считывании инверсного слова 65 У обнаруживаются дефекты в одиннадцатом-тринадцатом и шестнадцатом разрядах накопителя 1. В регистр 39 второго блока 26 будет записана вторая единица, В итоге с выходов 27 будет поступать слово 59 (соответствует второй строке матрицы С 53), в котором в пятом - седьмом разрядах будет единица, в одиннадцатом - тринадцатом и шестнадцатом разрядах - нули. В накопитель 1 запишется слово 60 без ошибок, Считывание происходит аналогично считыванию в приведенном примере. Формула изобретенияУстройство для исправления дефектов и ошибок в запоминающем устройстве, содержащее блок оперативной памяти, адресные входы которого являются одно 50 55 модулю два, выходы которого соединены с входами первой группы блока элементов И, входами первой группы блоков выбора согласующего слова и являются сигнальными выходами второй группы устройства, входы первой группы третьего сумматора по модулю два соединены с выходами первой, второй и третьей группы коммутатора, входывторой группы третьего блока сумматоров по модулю два соединены с входами второй группы блока элементов И, входами второй именными входами устройства, входной регистр, информационные входы которого соединены с выходами первого блока ключей и являются информационными входами-вы ходами устройства, информационные входыблока ключей соединены с выходами выходного регистра, блок постоянной памяти, выходы которого соединены с первыми входами первого блока сумматоров по моду лю два, выходы которого соединены с информационными входами выходного регистра, блок кодирования-декодирования, входы группы задания режима которого являются входами группы задания 15 режима устройства, первый и второй сигнальные выходы блока кодирования-декодирования являются сигнальными выходами первой группы устройства, первые и вторые информационные входы-выхо ды и контрольные входы-выходы блокакодирования-декодирования соединены соответственно с выходами первой, второй и третьей групп коммутатора, вход управления которого является первым входом зада ния режима устройства, входы-выходыкоммутатора соединены с информационными входами-выходами блока оперативной памяти, вход обращения которого является одноименным входом устройства, вход 30 записи-чтения блока оперативной памяти является соответствующим входом устройства, входы управления первого и второго блоков ключей и блока инверторов являются соответственно вторым, третьим и 35 четвертым входами задания режимов устройства, входы синхронизации входного и выходного регистров являются соответственно первым и вторым входами синхронизации устройства, входы второй группы 40 первого блока сумматоров по модулю двасоединены с вторыми входами-выходами группы блока кодирования-декодирования, о т л и ч а ю щ е е с я тем, что, с целью повышения быстродействия и достоверно сти работы устройства, в него введены регистр, второй блок сумматоров по модулюдва, блок элементов И, блоки выбора согласующего слова, формирователь согласующего слова, третий блок сумматоров по1735908 12 группы блоков выбора согласующего слова, информационными входами группы коммутатора и выходами блока инверторов, входы которого соединены с выходами второго блока сумматоров по модулю два, входы первой группы которого соединены с информационными выходами формирователя согласующего слова, входы второй группы второго сумматора по модулю два соединены с выходами регистра, вход синхронизации которого является третьим входом синхронизации устройства, информационные входы первой группы регистра соединены с информационными входами-выходами блока кодирования-декодирования, адресными входами блока постоянной памяти и выходами первой группы второго блока ключей, информационные входы второй группы регистра соединены с вторыми ин 5 10 вход которого является пятым входом задания режима устройства, выход формирова теля согласующего слова является 20 50зпаменты 1 2 3 4 5 б 7 8 9 10 11 12 13 матрицы о ао оо ооОоо о о о о о о 0 1 0 0 О 1 0о о оОоо О О 1о О1а о оо оо оо о о о а а о54 х;55 у;56 у 57 х;58 у,. 59 с;бах;+с;61 у; бгу"., 63 (н) 64 у 65 у 5 формационными входами-выходами блока кодирования-декодирования и выходами второй группы блока ключей, информационные входы третьей группы регистра соединены с контрольными входами-выходами блока кодирования-декодирования, входы второй группы регистра соединены с выходами входного регистра, выходы блока элементов И соединены с входами третьей группы блоков согласующего слова, выходы которых соединены с входами формирователя согласующего слова, управляющий сигнальным выходом устройства, входысинхронизации блоков выбора согласующего слова обьединены и являются четвертымвходом синхронизации устройства. 50 52 14 15 16 17 18 19 20 21 22 23 24 25 26.1 Л. г 1 Составитель Ю,СычевТехред М,Моргентал Корректор Яцола едак ик изводственно-издательский комбинат "Патент", г. Ужгород, ул,Гагарина, 1 аз 1819 Тираж ПодписноеВНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ СССР113035, Москва, Ж, Раушская наб., 4/5