Устройство для исправления ошибок в блоке памяти Советский патент 1981 года по МПК G11C29/00 

(54) УСТРОЙСТВО ДЛЯ ИСПРАВЖНИЯ ОШИБОК В БЛОТСЕ ПАМЯТИ

Изобретение относится к запоминающим устройствам и может быть использо вано для исправления единичных пачек ошибок в блоке памяти. Известно устройство для исправления ошибок в блоке памяти, содержащее сумматоры по модулю два и логические элементы Г Недостатком этого устройства является то, что оно рассчитано только на модули памяти с разрядностью от 2 до 5 и для случаев модулей памяти большей разрядности не пригодно. Наиболее близким к предлагаемому является устройство для исправления ошибок в блоке памяти, содержащее первую и вторую группы сумматоров по модулю два, индикаторы неисправнос тей и элементы И, причем входы сумматоров по модулю два первой группы и одни из входов сумматоров по Модулю два второй группы подключены ко входам устройства, выходы сумматоров пс модулю два первой группы соединены С одними из входов индикаторов неисправностей и первыми входами одних из элементов И, вторые входы элементов И подключены к выходам индикаторов неисправностей, выходы элементов И соединены с другими входами сумматоров по модулю два второй группы, выходы которых являются выходами устройства 2. Недостатком этого устройства является сложность сумматоров и индикаторов неисправностей и неоднородность различных трактов прохождения сигнала в них, что отрицательно сказывается на надежности устройства и его быстродействии. Цель изобретения - повьавение быстродействия и надежности устройства. Поставленная цель достигается тем, что устройство содержит третью группу сумматоров по модулю два, входы которых подключены ко. входам устройства, а выходы - к другим входам индикаторов Неисправностей и первым входам других элементов И. При этом каждый нндикатор неисправ ностей целесообразно выполнить таким образом, чтобы он содержал элемент НЕ-И и су1 04аторы по модулю два, выхода которых подключены ко входам эле мента НЕ-И, причем входы сумматоров по модулю два и выход элемента НЕ-И являются соответственно входами н вы ходом индикатора неисправностей. На чертеже изображена блок-схема предложенного устройства для случая, когда , N«4, где Ь - разряд.ность модулей, входящих в блок памяти Кблок памяти на чертеже не показан), а N - число модулей в блоке памяти, причем N i 2Ь « 1 Р , где р - tipocтое число. Устройство содержит 2Ь 1 суммато ров по модулю два 1-5, N индикаторов неисправностей 6-9, каждый из которых выполнен из двухвхрдош пс сумматоров по модулю два и одного элемента НЕ-И с Ь входами (не показаны), N групп по Ь элементов И 10-17 и N групп двухвхо довых сумматоров по модулю два 18-25 При этом сумматоры 1,3-5; 18-25 и 2 образуют соответственно первую, вто рую и третью группы сумматоров. Из 2Ь--1 сзмматоров I-5N содержат по N-1 входов (на чертеже - сумматоры 1, 3-5) и остальные по N входов ( чертеже - сумматор 2). Входа сумматоров -5 подключены к входам устройства в .соответствии с N подматрицами проверочной матрицы образованными циклической перестанов кой 2Ь+1 строк исходной подматрицы, составленной из двух перестановочных матриц порядка Ь с единицами на разШ)1Х диагоналях и разделяющей их стро ки из Ь нулей. При этом каждому моду лю памяти соответствует одна подматрица, каждой ее строке - сумматор с таким же порядковым номером, а пол жение единицы в строке указывает раз ряд модуля памяти, который должен быть подключен к одному из входов со ответствующего строке сумматора. Для изображенного на чертеже устройства проверочная матрица имеет вид: составляющие эту матрицу первая (исходная), вторая, третья и четверая подматрищ) (пары столбцов являтся проверочными подматрицами соответствующих модулей памяти. иникатора неисправностей для опредеенного модуля памяти, соответствующего одному сумматору (на чертеже для наглядности показаны расположеннь ш на равном удалении по обе стороны отмеченного пунктиром условного центра) стэединены с выходами сумматоров 1-5, равноудаленными от выхода, соответствующего центру симметрии, рассматриваемого как циркулянт синдрома ошибок этого модуля. Таким выходом является выход сумматора, соответствующего нулевой строке подматрицы этого модуля памяти. Индикаторы неисправностей 6, 7, 8 и 9 относятся соответственно к первому, второму, третьему и четвертому модулям памяти, центрам симметрии синдрома ошибок которых соответствуют выходы сумматоров 3, 4, 5 и 1. Первые входы группы элементов И 10-17, относящейся к определенному модулю памяти, соединешз с Ь смежными выходами сумматоров 1-5, расположенными по одну сторону от выхода, соответствую- щего центру симметрии синдрома ошибок этого МОДУЛЯ памяти, при этом, крайние выходы сумматоров 5-5 считаются смежными. А вторые входы указанных элементов И 10-17 подключены к выходу соответствующего индикатора неисправностей 6-9. Принцип действия устройства основан на использовании свойств кода, определенного проверочной матрицей указанного вида. Для обеспечения возможности исправления ошибок, каждое записанное в памяти слово содержит 2 избыточных, или контрольных, разряда, для которых отводятся два из общего числа N модулей памяти. Контрольная часть слова образуется в соответствии с информационной частью слова и проверочной матрицей, так, чтобы для каждой строки матрицы контрольная сумма по моду)йо два всех разрядов слова, указанных положением единиц в этой строке, при отсутствии ошибок была равна нулю. Вектор - столбец, образованный набором контрольных сумм для всех строк матрицы, - синдром ошибок в случае одиночной пачки ошибок содержит в себе информацию о месте и виде пачки, т.е. о номере неисправно5го Модуля памяти и положении в нем неверно считанных разрядов. В подматрицах проверочной матрицы каждая из 2Ъ+ строк, кроме нулевой,содержи одну единицу, а каждый из Ь столбцов точно две единицы, и, если рассматривать подматрицы как циркулянты, Т.е. считать их крайние строки смежными, то расположение единиц в строках симметрично относительно нулевой строки и одинаково для всех подматриц, а подматрицы отличаются только положением их центров симметрии - ну левых строк. Поэтому, при произвольной пачке ошибок в любом модуле, в векторе-столбце (синдроме ошибок) с.трока, соответствующая нулевой стро ке подматрицы проверок зтого модуля, содержит нуль и является центром.сим метрии синхрома, рассматриваемого ка циркулянт. Положение единиц в синдроме ошибок относительно центра симметрии соответствует ошибкам в определенных разрядах модуля.. Так как, па условию, шсло строк в подматрице равио простому чис лу, то, при любых ошибках в разрядах одного модуля, синдром ошибок может иметь только один центр симметрии. Поэтому любые ошибки в любом одном м дуле памяти определяются видом синдрома однозначно. Поскольку все подматрицы равноправны, для контрольных модулей памяти может быть выбрана лю бая пара из них. Б отличие от извест ного устройства контрольные разряды здесь взаимозависимы. Устройство работает следующим образом. Синдром ошибок Отображается сигна лами на выходах сумматоров 1-5. Поло жение центра симметрии синдрома ошибок распознается индикаторами неисправностей 6-9. Каждый из них реагирует только на свой синдром, т.е синдром с одним определенным положением центра симметрии. При неисправности в разрядах какого-либо одного модуля памяти, выходной сигнал соответствующего индикатора неисправноетей открывает все элементы И относящейся к модулю группы. Через них на одни из входов сумматоров 18-25, это же группы, подаются сигналы с смежны выходов сумматоров 1-5, отсчитываемых от выхода, соответствукицего цент ру синдрома. При этом, если на один из входов какого-либо сумматора 18-2 поступает единичный сигнал, что ука16зывает на ошибочность сигнала на его другом входе, на выходе этого сумматора образуется исправленный сигнал. Использование предлагаемого устройства, по сравнетло с известными техническими решениями позволяет существенно уменьшить число составляющих устройство элементов,повысить надежность устройства и увеличить его быстродействие. Это иллюстрируется следующим примером. При типичных для практики значениях и в известном устройстг ве требуется 364 двухвходовых сумматора, а в описанном устройстве тольi o 223, т.е. на 39% меньше. При этом, число таких сумматоров на пути сигнала в прототипе меняется от I до 8, а в предложенном устройстве только от 2до 5. Формула изобретения 1.Устройство для исправления ошит бок в блоке, памяти, содержащее первую и вторую группы сумматоров по модулю два индикаторы неисправностей и элементы И, причем входы сумматоров по модулю два первой группы и одни из входов сумматоров по модулю два второй группы подключены ко входам устройства, выходы сумматоров по модулю два первой группы соединены с одними из входов индикаторов неисправностей и первыми входами одних из элементов И, вторые входы элементов И подключены к выходам индикаторов неисправностей, выходы элементов И соединены с другими входами сумматоров по модулю два второй группы, выходы которых являются выходами устройства, отличающееся тем, что, с целью повышения быстродействия и (1адежности устройства, оно содержит третью группу.сумматоров по модулю два, входа которых подключены ко входам устройства, а выходы - к другим входам индикаторов неисправностей и первым входам других элементов И. 2.Устройство по п. 1, отличающееся тем, что индикатор неисправностей содержит элемент НЕ-И и сумматоры по модулю два выходы которых подключены ко входам элемента НЕ-И, причем входы, сумматоров по одулю два и выход элемента НБ-И являюгся соответственно входами и вы.ходом индикатора неисправностей. Источники информации, принятые BO внимание при экспертизе 8688418 1.Information and Control, 1973, V. 23, pp. 234-244. 2.IBM Journal of Research and Development 1970, v. 14, № 4, pp. 402j 408 (прототип).