Запоминающее устройство с коррекцией групповых ошибок

(191 1 С 2900 науч 1 г 1 м 01 ь 11БАЬ 1 п. И ЕЬЛ 1 О,; т ам (ЗУ), и можетя построения вы-памятн с возможнакопителей вачи, Цель изобисо поминающим уст быть использов соконадежных ностью нт е решени роц ете ежности устритываемои ин повыш товер Устро оличе ия ва и до т одержит блоки торых должно е К 3 4, блок и, коммутатор, .РАВНОЗНАЧНОСТЬ иств формац памяти быть н ство ко К+3), гд задержк менты НГ о модулю д мажорита й элемент, оррекции, блок лементы И, эле локи свертки и локи сравнения енты, пороговы регистые элеычиск заий ин о м ОСУДАРСТВЕННЫЙ КОМИТЕТ0 ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМРИ ГКНТ СССР ОПИСАНИЕ ИЗОБР К АВТОРСКОМУ С 8 ИДЕТЕЛЬ(56) Авторское свидетельство СССРВ 955207, кл, С 11 С 29/00, 1980.Авторское свидетельство СССРМ 1092570, кл. С 11 С 29/ОО, 1983.(54) ЗАПОМИНАЮЩЕЕ УСТРОЙСТВО С КОРРЕКЦИЕЙ ГРУППОВЫХ ОШИБОК(57) Изобретение относится к влительной технике, в частности Изобретение относится к вычислительной технике, в частности к запоминающим устройствам (ЗУ), и может быть использовано для построения высоконадежных блоков памяти с возможностью ремонта накопителя в процессе решения задачи.Цель изобретения - повышение надежности устройства и достоверности считываемой информации.На фиг. 1 представлена функциональная схема ЗУ; на фиг. 2 и 3 - функциональная схема блока коррекции; на фиг. 4 и 5 - геометрическая интерпретация кодовой матрицы соответственно двух модифицированных трехмерных кодов, 28,16 (К=4) и 54,36 (К=6) с контролем по четности для всех К -разрядных комбинаций и с контролем по нечеткости для всех нечетных комбинац ф р ационногосообщения,Устройство содержит блоки 1-7 памяти, количество которых должно бытьнечетным (К+3), блок 8 коррекции,блок 9 задержки,. коммутатор 10, первый элемент И 11, элементы НЕРАВНОЗНАЧНОСТЬ 12-27, первую группу элементов И 28-43, вторую группу элементов И 44-46, причем выходы 47.-62блоков 1-4 и выходы 63-74 блоков 5-7соединены соответственно с информационными и контрольными входами.блока 8 коррекции, вход блока 9задержки является входом 75 запускаустройства,первый выход 76 блока 9задержкй соединен с первым информационным входом коммутатора 10, вто"рой выход 77 - с входами синхронизации блоков 1-7, третий выход 78 - с1481863 О О ОЫЗ ОЫФ Составитель В.РудаковРедактор И.Шмакова Техред А.Кравчук Ко ректор М.Василье Заказ 2699/55 Тираж 559 ВНИИПИ Государственного комитета по изоб 113035, Москва, Ж, Раодписн ри ГКНТ ССС ениям и открыти кая наб., д, 4/ роизводственно-издательский комбинат "Патент, г. Ужгород, ул. Гагарина О О О 050 вторым информационным входом коммутатора 10, четвертый выход 79 - свходом первого элемента И 11, а пятыйвыход 80 является выходом окончанияцикла обращения устройства, выходы581-96 блока 8 коррекции соединены содними из входов элементов НЕРАВНОЗНАЧНОСТЬ 12-27,Устройство имеет информационныевходы 97, информационные выходы 98,вход 99 записи, вход 100 считывания.Выход коммутатора 10 соединен с управляющим входом 101 блока 8, Выходы,102-104 блока 8 коррекции являются 5одними из информационных входов устройства, выходы 105-126 - индикатор-.ным выходом 27 устройства. Установоч.ные входы 128-131 являются установочными входами устройства, адресным 20входом 132 которого являются адресныевходы блоков 1-7 памяти.Блок 8 коррекции содержит регистр133, первую группу блоков 134-137,вторую группу блоков 138-141 и третью 25. группу блоков 142-145 свертки по модулю два,Блок 8 коррекции также содержитэлементы И 146-197, образующие третью 146-149, четвертую 150-153, пятую 158-161, шестую 162-165, седьмую:170-185, восьмую 186-189, девятую190-193, десятую 154-157, одиннадцатую 166-169,и двенадцатую 194-197группы элементов И, первый 198, второй 199 и третий 200 блоки сверткипо модулю два, первую 201, вторую202 и третью 203 группы блоковсрав"кения, первую 204-206 и вторую 207-.четырнадцатую 214-216 группы элементов И, с второго по шестой элементыИ 217-221, Регистр 133 имеет выходы222-252, блоки 134-141 - выходы 253-260.Блоки 198-200 служат для формирования в коде (3,1) контрольного разряда 8 общей четности: 8,для выходного К -разрядного сообщения.Мажоритарные элементы 204-206.и207-209 служат для коррекции одиночных ошибок в разрядах р , 8 , 34 а Экоторые для устройства являются информационными разрядами входного ивыходного сообщения, поступающимисоответственно с информационныхвыходов 239-241 регистра 133 (в режимезаписи в память) или с выходов блоков 198-200 по модулю два (н режимесчитывания из памяти). Блоки 134-145служат соответственно для Формирования координат А, В, С трехмерногокода (в режиме записи) и формирования трех групп разрядов синдромаЫ 1-й, 1-4, 1-4 (в режиме считывания) согласно кодовой матрице примененного в устройстве кода (фиг. 4и 5).Блоки 201-203 служат для анализаЗК-разрядного кода синдрома и Формирования координат К, 3и .оошибочных информационных символов81-816 (в рассматриваемом примере Кравно, например, четырем) в случаенеисправности одного из блоков 1-4памяти и Формирования сигналов некорректируемой ошибки при ошибке вразных блоках памяти или полном отказе одного из блоков 1-7, которыечерез пороговый элемент 210 и элементы И 220 и 221 выдаются на выходы120-122 устройства как сигналы НКО 1,НКО 2, НКОЗ (адрес соответствующеговектора прерывания). Схема подключения выходов 222-237 регистра и выходов элементов И 146-47, 211-216к входам блоков 134-145, а также выходов блоков 201-203 к входам элементов И 170-185 определяется кодовой матрицей примененного в устройстве трехмерного кода,На фиг. 4 и 5 обозначены: 81-816,817-836 -. информационные разрядытрехмерного кода; я 1, 82, 83 - контрольные разряды общей четности вход-ного и выходного сообщения в кодеЮ3,1, занимающие в кодовой матрицеФиктивные позиции (т,е, в кодовомслове в явном виде не присутствуюти, следовательно, в ячейки блоков памяти не записываются); а 1-а 1, Ь 1"ЬМ,с 1-сМ - контрольные разряды Формируемого для устройства кода (в режиме записи); ю 1 ъй, 1-1Рразряды формируемого в устройствесиндрома (в режиме чтения).Устройство работает следующим образом.В устройстве для коррекции одиночных групповых ошибок и обнаружения двух и более битовых ошибок реализован модифицированный код (К +ЗК,К ) с числом информационных разрядов К , с числом контрольных разря81863 6 50 55 5 14доп ЗК и беэ контрольного разрядаобщей четности, с помощью котороговозможна коррекция одиночной групповой ошибки в (К) разрядах информации, расположенных на одной иэ диагоналей кодовой матрицы, а также выявление любых двух и более битовыхошибок, расположеннь 1 х в разных диагоналях кодовой матрицы (а следовательно, в:разных блоках памяти), Геометрическая трехмерная структура данного кода и отсутствие в кодовом словеразряда я общей четности позволяютупростить алгоритм формирования контрольных разрядов, ибо в кодере отсутствует схема свертки по модулю двавсех К разрядов входного сообщения,Фреализовать в.устройстве очень простой алгоритм обнаружения ошибок вразных накопителях, ибо при декодировании данного кода на контрольных выходах в явном виде вырабатываетсяномер неисправных блоков памяти (третья координата ошибочных информационных символов), и выдавать выходнуюгК -разрядную информацию с тремя контрольными разрядами общей четности, ккоторь 1 е формируются (и при необходимости корректируются) в процессе декодирования трехмерного кода независимо от других разрядов выходного сообщения, что позволяет обнаружитьошибки, внесенные в выходную информацию неисправностями самого устройстваконтроля, при дальнейшем прохожденииэтой информации по магистрали (схемой контроля передачи по магистрали).Модифицированный трехмерный (АВС)код строится на основе двухмерного(АВ) итеративного кода с контрольнымразрядом я общей четности, примененного в известном устройстве, путеммодификации структуры его кодовойматрицы, в результате чего может бытьполучен двумерный интеративный код скодовым расстоянием 6=4, но без контрольного разряда ц,В результате данной модификацииполучается укороченный двумерный код(24, 16) с контролем по четности(=0) для всех четных комбинаций входного шестнадцатиразрядного сообщенияи с контролем по нечетности (я=1)для всех нечетных комбинаций входногошестнадцатиразрядного сообщения,Контрольные разряды С 1-С 4, соот ветствующие третьей координате С модифицированного трехмерного кода(28-16), примененного в предлагаемомустройстве, формируются аналогичнокоординатам А и В модифицированногодвумерного кода (24,16), т,е. проверкои на четность (р,=О) или нечетность(р=1) четырех соответствующих диагоналей кодовой матрицы (фиг. 4),В общем случае для числа информагционных разрядов К алгоритм построения контрольных разрядов модифици 2рованного трехмерного кода (К +ЗК,К )заключается в следующем: каждаякоордината А (а 1-аЕ), В (Ь 1-ЬК),С (с 1-сК) формируемого для устройства -кода образуется прбверкой начетность (я=0) или нечетность (д=1)соответственно каждой иэ К информационных строк, столбцов и диагоналейкодовой матрицы. Контрольные разряды, участвующие в Формировании контрольных разрядов трехмерного кода,поступают в режиме записи с входноймагистрали вместе с К информационными разрядами и, следовательно,воспринимаются устройством как тридополнительных информационньх разгряда входного (К +3)-разрядного сообщения. Затем при занесении кодового слова в блоки памяти контрольныеразряды отбрасываются, т,е. в кодовом слове, хранящемся в ячейке блокапамяти, не присутствуютВ режимечтения параллельно с декодированием 35кодового слова независимо формируются три разряда общей четности. Приэтом контрольный разряд общей четности р трехмерного кода формируется в коде (3,1). Затем эти контрольные разряды участвуют в формировании трех групп разрядов синдрома Ы 1-с(1, 1-1, 1-1 согласно кодовойматрице трехмерного кода и одновременно (после соответствующей коррекции) поступают на выход устройства,Таким образом на выходную магистральданных, как и с входной магистрали,также поступает (К +3)-раэрядноегсообщение,Работу устройства рассмотрим, например, для случая реализации трехмерного кода 28,16 (К=4), кодоваяматрица которого представлена на фиг, 4.В режиме "Запись" на вход 132 устройства поступает адрес выбранной ячейки блока памяти, на вход 97- очередное 19-разрядное сообщение, содержащее слово данных 81-516 и три(т.е. в коде 3,) контрольных разряда общей четности .я: 8 , ККкоторые для устройства являются соответственно информационными разрядами 817, 818, 819, на вход 99 - признак записи, а на вход 75 - сигнал"Запуск", который через коммутатор10 проходит на вход 101 блока 8,где заносит в регистр 133 информацию,находящуюся на входах 47-62 и 102104, После этого в блоке 8 начинается исправление на мажоритарных элементах 204-206 разрядов р 8, Г,общей четности входного сообщения иформирование координат А, В, С модифицированного трехмерного кода 28,16 согласно кодовой матрице (фиг,4).Контрольные разряды а 1-а 4 (коор дината А) формируются с помощью блоков 134-137, контрольные разрядыЬ-Ь (координата В) - с помощьюблоков 138-141, а контрольные разрядыс 1-с 4 (координата С) - с помощьюблоков 142-145.На входе 100 блока 8 присутствуетлогический нуль (низкий уровень напряжения), а на входе 99 - логическая единица (высокий уровень напряжения). В результате элементы И 146157 и 214-216 остаются закрытыми, ииа их выходах находятся логическиенули, а элементы И 211-213 открываются, пропуская на входы блоков 134145 исправленные значения трех контрольных разрядов 8 , я 8 . Одной Эвременно открываются блоки 158-169 исформированные значения контрольныхразрядов (координаты А, В, С трехмерного кода) поступают с их выходов навходы 63-74 блока 8 и на входы блоков5-7.С появлением сигнала на выходе 77блока 9 задержки производится записькодового слова в блоки 1-7. В каждыйиз блоков 1-7 записывается по К (вданном примере К=4) соответствующихразрядов кодового слова, причем в блоки 1-4 записываются информационныесимволы 81-316, а в блоки 5-7 - координаты А, В, С этих информационныхсимволов,По окончании записи на выход 80устройства выдается соответствующийсигнал,В режиме "Чтение" на вход 132устройства поступает адрес выбранной ячейки памяти, на вход 100 -признак считывания, а на вход 75 -сигнал "Запуск", С появлением сигнала на выходе 77 блока 9 адержки код вое слово считывается из блоков 1-7и поступает на входы блока 8, Таккак на управляющем входе коммутатора 10 присутствует логическая единица, поступающая с входа 100.устройства, то прохождение сигнала черезкоммутатор с выхода блока 9 задержки запрещается, Одновременно разрешается прохождение сигнала с выхода 78, поступающего позже сигнала с выхода 77 с задержкой, равной временивыборки информации из блоков 1-7.Пройдя коммутатор 10, этот сигнал поступает на управляющий вход 101 блока 8 и заносит считанное кодовое слово в регистр 133.Затем в блоке 8 начинается формирование трех групп разрядов кода синдрома, т.е. вычисление позиций ошибочных символов через координаты А, В, С трехмерного кода в следующей последовательности; В блоках .198-200 независимо друг,от друга (в коде 3,1) формируются изатем исправляются на мажоритарныхэлементах 207,-209 три значения контрольного разряда общей четности.Так какв это время на входе 100блока 8 присутствует логическая единица, то исправление значения разрядов через элементы И, 214-216, асчитанные значения контрольных разрядов с выходов 241-252 регистра 133через элементы И 146-157 поступаютна соответствующие входы блоков 134-145,В дальнейшем три группы разрядовсиндрома попарно анализируются вблоках 201-203,При отсутствии ошибок в считанном кодовом слове или при обнаружении 45 групповых ошибок в одном из контроль ных блоков 5-7 на выходах блоков 201203 .сохраняются логические нули(низкий. уровень напряжения). Это оз/ начает, что при обнаружении неисправности одного из блоков 5-7 ошибки в контрольных разрядах блоками 201-203 игнорируются, что равносильно их "исправлению", так как в данном случае никогда не произойдет "неправильной" коррекции какого-либо информационного символа 81-816, ибо работа элементов И 170-185, "настроенных" только на координаты К, /,искаженных информационных символов, блокиру 1481863 10ется (на входах каждого из них присутствует логический нуль),Одновременно разрешается работаэлементов И 186-197, "настроенных"только на унитарные координаты Кили Я , или Д искаженных контрольных символов а-а 4, или Ы-Ь 4,или с 1-с 4 одного из блоков 5-7,На выходах 81-96 и 120-122 присутствуют логические нули, На выходах123-126 логические единицы появляются только при неисправности блока 7(ошибки в разрядах С 1-С 4),Позиции ошибочных контрольныхсимволов (логические единицы на выходах 108-119 устройства) определяются с помощью элементов И 186-197.При обнаружении корректируемойошибки в одном из блоков 1-4 разрешается работа элементов И 170-185,каждый из которых настроен на трехмерные координаты сЫ, , 111 одногоинформационного символа Я 1-Я 6 (,1,Е - номер строки, столбца и диагонали кодовой матрицы), а работа элементов И 186-197 блокируется, таккак на выходе элементов И 217-218присутствуют логические нули, На выходах 81-96 вырабатываются сигналыкоррекции, .инвертирующие на элементахНЕРАВНОЗНАЧНОСТЬ 12-27 соответствующие информационные символы Я 1-816.На выходах 108-122 сохраняются логические нули, а на выходы 123-126выдается унитарный комер неисправного блока 1-4. Позиции ошибочных информационных символов (логическиеединицы на выходах 81-96 устройства)определяются с помощью элементовИ 170-185.В целом информация на выходах 81119 и 123-126 при возникновении корректируемой групповой ошибки в одномиз блоков 1-7 может быть использована в режиме периодической диагностики для индикации отказавших разрядови своевременного выявления и заменынеисправного блока памяти, а такжеустранения неисправностей самого устройства контроля еще до возникновения в устройстве некорректируемыхотказов.При отсутствии некорректируемыхотказов (на выходах 120-122 присутствуют логические нули)цикл "Чтение"заканчивается по сигналу с выхода.79 блока 9 задержки, проходящему че.рез элемент И 11, Информационные раэ 25 Запоминающее устройство с коррекцией групповых ошибок, содержащееблоки памяти, блок задержки, коммутатор, первый элемент И, элементы 30 НЕРАВНОЗНАЧНОСТЬ, первую и вторуюгруппь 1 элементов И и блок коррекции,содержащий регистр, первую и вторуюгруппы блоков свертки по модулю два,с третьей по девятую группы элементовИ, с первого по третий блоки сверткипо модулю два, причем входы первой ивторой групп информационных разрядоврегистра являются информационнымивходами устройства, выходы элементов 40 И первой и второй групп являются информационными выходами устройства,входы первой группы блоков свертки 45 50 55.5 10 15 20 ряды Я 1-Я 16, скорректированные принеобходимости на элементах НЕРАВНОЗНАЧНОСТЬ 12-27, и три разряда общейчетности 8 , р , рэ, скорректированные на мажоритарных элементах 207209, выдаются через элементы И 28-46на информационные выходы 98 устройства, Затем на выход 80 выдается соответствующий сигнал,При возникновении некорректируеГмых ошибок в одном или несколькихблоках памяти или некорректируемыхотказов в самом устройстве контроля(появление на выходах 120-122 логическйх единиц) дальнейшая работаустройства должна быть прервана, авыдача некорректной информации на выходы 98 устройства должна быть заблокирована, например, подачей логических нулей на установочные входы128-131,Формула изобретения по модулю два первой и второй групппоразрядно объединены и подключенык соответствующим выходам первойгруппы информационных разрядов регистра, первые выходы элементов И пятойи шестой групп соединены соответственно с прямымн выходами блоков свертки по модулю два первой и второйгрупп, вторые входы элементов И пятой и шестой групп и входы признака записи блоков памяти объединены и являются входом записи устройства,выходы элементов И пятой и шестойгрупп соединены соответственно с входами первой и второй групп контрольных разрядов регистра, первые входыэлементов И третьей и четвертойгрупп, входы признака считывания блоков памяти, управляющий вход коммутатора и первый вход первого элемента И объединены и являются входом считывания устройства, выход первого элемента И соединен с первыми входами элементов И.первой и второй групп, выходы элементов И седьмой группы соединены с первыми входами элементов 10 НЕРАВНОЗНАЧНОСТЬ, вторые входы которых соединены с выходами блоков памяти, выходы элементов НЕРАВНОЗНАЧНОСТЬ соединены с вторыми входами элементов И первой группы, первый выход блока задержки соединен с первым информационным входом коммутатора, второй выход блока задержки подключен к входам синхронизации блоков памяти, третий и четвертый выходы блока задержки соединены соответственно с вторым информационным входом коммутатора и вторым входом первого элемента И, пятый. выход блока задержки является выходом "Окончание цик ла обращения" устройства, выход коммутатора соединен с управляющим входом регистра, о т л и ч а ю щ ее с я тем,. что, с целью повышения надежности устройства и повышения 30 достоверности считываемой информации, в него введены третья группа свертки по модулю два, три группы блоков сравнения, первая и вторая группы мажоритарных элементов, пороговый .элемент, с десятой по четырнадцатую группы элементов И, с второго по шестой, элементы И, причем входы первой группы блоков свертки по модулю два третьей группы подключены к выходам первой группы информационных разрядов регистра, группы выходы, блоков свертки по модулю два третьей группы соединены с первыми входамиэлементов И одиннадцатой группы, выходы которых соединены с входами третьей группы контрольных разрядов регистра, входы второй группы блоков свертки по модулю два первой, второй и третьей групп соединены с соответ 50 ствующими выходами элементов И. третьей, четвертой, десятой, тринадцатой и четырнадцатой групп, вторые входы элементов И,третьей группы и входы первого блока свертки по модулю два объединены поразрядно и соединены с выходами первой группы контрольных разрядов регистра, вторые входы элементов И четвертой группы и входы второго блока свертки по модулю два объединены поразрядно и подключены к выходам второй группы контрольных разрядов регистра, первыевходы элементов И десятой группы ивходы третьего блока свертки по модулю два поразрядно объединены и соединены с выходами третьей группы контрольных разрядов регистра, одноименные входы мажоритарных элементов первой группы объединены и подключенык выходам второй группы информационных разрядов регистра, выходы мажоритарных элементов первой группы соединены с первыми входами элементовИ тринадцатой группы, вторые входыкоторых и вторые входы элементов Иодиннадцатой группы подключены к входу записи устройства, одноименныевходы мажоритарных элементов второйгруппы объединены и подключены соответственно к выходам первого, второго и третьего блоков свертки по модулю два, выходы мажоритарных элементов второй группы соединены с первыми входами элементов И четырнадцатой группы, вторые входы которых ивторые входы элементов И десятойгруппы подключены к входу считывания устройства, входы первой и второй групп блоков сравнения первойгруппы подключены соответственно кпервым выходам блоков свертки по модулю два первой и второй групп, входыпервой и второй групп блоков сравнения второй группы соединены соответственно с прямыми выходами блоковсвертки по модулю два первой и третьей групп, входы первой и второйгрупп блоков сравнения третьей группы подключены соответственно .к прямым выходам блоков свертки по модулюдва второй и третьей групп, выходыблоков сравнения первой, второй и1третьей групп подключены соответственно к входам порогового элемента,пятого и шестого элементов И, входыэлементов И седьмой группы соединеныс соответствующими выходами блоковсравнения первой, второй и третьейгрупп, первые входы элементов И восьмой, девятой и двенадцатой группподключены соответственно к первымвыходам блоков свертки по модулю двапервой, второй и третьей групп, инверсные выходы которых соединенысоответственно, с входами второго,третьего и четвертого элементов И, 11выхопы которых п лклкч пы к вторыми третьим входам элементов И восьмой, девятой и двенадцатой групп,выходы мажоритарных элементов второйгруппы соединены с вторыми входамиэлементов И второй группы, входыпервой группы информационных разрядов регистра и входы контрольныхраэрядов регистра соединены с выходами соответствующих блоков памяти, выходы элементов И седьмой, восьмой девятой и двенадцатой групп, выходы 5мажоритарных элементов второй группы, выходы блоков свертки по модулю два третьей группы, выходы порогового элемента и пятого и шестого элементов И являются индикаторными выходами устройства.