Устройство для обнаружения и коррекции ошибок памяти

(5 ц 4 О 11 С 29/ с.с иссс СПИКАВ ОБРЕТЕНИЯ 1."3,", НВЮ,;с ТЕПЬСТ КОМУ С(56) Авторское свидетельство СССРУ 1026165, кл. О 11 С 29/00, 1982Авторское свидетельство СССР9 1149318. кл. 0 11 С 29/00, 1983 УЖЕНИЯ к вычисыть исодиночныошибок в яв аво и даннь овышени роиство со"онтрольных ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССРПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИ(54) УСТРОЙСТВО ДЛЯ ОБНАР И КОРРЕКЦИИ ОШИБОК ПАМЯТИ (57) Изобретение относитс лительной технике и может пользовано для исправлени и обнаружения многократны памяти и магистралях пере Целью изобретения являетс надежности устройства. Ус держит блок формирования сигналов, состоящии из сумматоров помодулю два по числу контрольных разрядов корректирующего кода, коммутаторы-корректоры по числу информационных разрядов и формирова; ель кодаошибки. В устройстве реализован треугольный (С , +ш, С ) код с модиФицированным алгоритмом построениякодирующей Н-матрицы, согласно кото"рой разряд общей четности исходногосообщения участвует в формированииконтрольных разрядов наравне с информационными разрядами. Повышениенадежности устройства достигаетсяраспараллеливанием схемы декодирования, при этом все ветви декадераляются равнонадежными, а количестоборудования, необходимого для обработки одного искаженного символа,не зависит от разрядности входногосообщения. 4 ил.Изобретение относится к вычислительной технике и может быть использовано для исправления одиночных иобнаружения многократных ошибок впамяти и магистралях передачи данных.Целью изобретения является повышение надежности устройства.На фиг.1 представлена структурнаясхема устройства для обнаружения и 1 Окоррекции ошибок памяти; на фиг.2и 3 - геометрическая интерпретациякодирующей Н-матрицы для (5,0).и(21,15) модифицированных треугольныхкодов с параметрами, соответственно5равными: ш = 5, К = С, = 10 (для 15,г10 кода) и ш=б, К=С 6=15 (для21,15 кода); на фиг.4 - вариант схемного выполнения устройства для одногоконкретного случая его применения 20(декодирования 21,15 треугольного кода,Устройство (фиг,1 ) содержит блок 1формирования контрольных сигналов,состоящий из а (по числу контрольныхразрядов входного корректирующего кода) и"входовых сумматоров 2 -2 по :модулю два, ш-входовый формирова"тель 3 кода ошибки и К (по числу ин-.формационных разрядов входного корректирующего кода) коммутаторов-корректоров 4, - 4 одиночных ошибок,каждый из которых имеет три адресныхвхода. Число сумматоров и число коммутаторов в устройстве всегда связагно соотношением К=С ,Устройство имеет информационныевходы 5, 6 и выходы 7 контрольных разрядов, информационные выходы 8 иконтрольные выходы 9 и 10, 40Блокформирования контрольныхсигналов служит для формирования конт"рольных разрядов С- С треугольногокода (в режиме записи в память) иформирования разрядов синдрома Я,-Я ,15(в режиме считывания из памяти) длядекодирования треугольного кода.Формирователь 3 кода ошибки служит,для формирования на выходах 9 и 10устройства парафазного (01 или 1 О)кода ошибки в случае возникновенияошибок на входах 5 и 6 устройства,или в самих сумматорах 2,-2, формирующих номер позиции искаженногоинформационного символа 55Коммутаторы-корректоры 4,-4одиночных ошибок служат для непосредственной коррекции искаженных информационных символов входа 5 устройства и формирования на выходах 8 выходного К-разрядного сообщения, при этом коммутатор 4 формирует (и корректирует при необходимости) контрольный символ С, который является разрядом общей четности выходного К-разрядного сообщения.Схема подключения входов 5 и 6 устройства к входам сумматоров 2-2 блока 1 формирования контрольных сигналов, а также информационных входов 5 устройства и первых выходов сумматоровк трем адресным входам коммутаторов 4," 4 определяется кодирующей.Н-матрицей"примененного в устройстве треугольного кода, основное свойство которого заключается в том, что параметры его (число контрольных разрядов т и число информационных разрядов К) всегда связаны соотношением: К равно числу сочетаний ш по два, что наглядно иллюстрируется (фиг.2 и 3) на примере построенния 15, 10 (К = С )и 21,15 (К = Сг) треугольных кодов,На фиг,2 и 3 цифрами 1-15 обозначены информационные разряды треугольного кода, С, - разряд общей четности и одновременно первый информационный разряд исходного К"разрядногосообщения, С 1. - С 6 - контрольные разряды формируемого для устройства кода,На фиг.4 информационные разрядывхода 5 устройства обозначены 1 рр,информационные разряды выхода в устройстве обозначены 1 разряд - 15 разряд. Первый разряд выхода 8 (1 разряд) является одновременно разрядомобщей четности С- выходного пятнадцатиразрядного сообщенияУстройство реализует (С +ш, С, )модифицированный треугольный код скодовым расстоянием 4, с числом контрольных разрядов ш5, числом инфоргмационных разрядов К = С (т.е, равным числу сочетаний из ш по два) ичислом позиционных разрядов и = К +г+ ш = С , геометрическая структурапостроения кодирующей Н-матрицы которого позволяет реализовать в устройстве простой алгоритм декодирования,так как при любой разрядности К входного сообщения двоичный код номерапозиции каждого информационного символа содержит ровно две единицы",соответствующие двумерной координатеС. = 1+2+4+7; С 2 = 3+5+8+7; СЗ = 6+9+4+8; С 4 = 0+2+5+9; С 5 = +3+6+10,Из данного примера видно, дый из десяти информационных лов участвует в формировании 50 55что кажсимво равно этого символа, что позволяет уменьшить число сумматоров по модулю два в устройстве (в пересчете на один корректируемый разряд информации), заменить а-адресновходовые коммутаторы, примененные в известном устройстве на трехадресновходовые и выдавать на выходную магистраль данных информацию в соответствующем коррек О тирующем коде.Входной корректирующий код для устройства формируется из исходного К-разрядного сообщения, состоящего из Кинформационных разрядов и од ного контрольного разряда С, по общей четности исходного сообщения по следующему алгоритму (фиг.2,3): контрольный символ С исходного К-разрядного сообщения, рассматриваемый при 20 построении кода как первый информационный символ, помещается в вершине прямоугольного треугольника, остальные информационные символы исход ного сообщения размещаются в соответ ствующих фиксированных позициях прямоугольного треугольника, а контрольные символы С 1-Сш формируемого кода располагаются на гипотенузе этого триугольника в местах пересечения строк и столбцов соответствующих символов, чем и определяется простое правило вычисления значений контрольных разрядов С 1-Сп треугольного кода: значение каждого контрольного симво 35 ла, расположенного на гипотенузе, образуется сверткой по модулю два определенной подгруппы информационных символов, входящих в соответствующий столбец и строку прямоугольного тре угольника, на пересечении которых этот контрольный символ расположен, Это правило наглядно иллюстрируется на примере построения двух треугольных кодов:5,10 (К = 1 О, ш=5) и 21,15 45 (К = 15, ш =6). Например, (Фиг,2); контрольные разряды С - С 5 треуголь" ного 1 5, 10 кода вычисляются по формулам: двух контрольных символов С 1 - С 5 (и, следовательно, в формировании равно двух соответствующих разрядов синдрома Я, - Я при декодировании треугольного 15, 10 кода. Например, девятый информационный символ (подчеркнут) участвует в формировании контрольных символов СЗ и С 4. Это правило распространяется на треугольные коды с любой разрядностью К исходного сообщения: (21,15), (28,21 ) ,(36,28), (45,36), (55,45) и т.,д., параметры которых всегда связаны соотношением К = С . Например, проверочные (фиг.3) соотношения для вычисления разрядов синдрома Я - Я 6 треугольного кода 2У 15 кода (15 = С ) формируются следующим образом:Б = С 1 +Ф 2 + 4 + 7 + 1 1;Б 2 = С 2+3+ 5+ 8+ 2+ 1 У Бз = СЗ + 6 + 9 + 3 + 7 + 12 Б = С 4 + 1 О + 14 + 4 + 8 + 13; Б = С 5 + 15 + 2 + 5 + 9 + 14;Бв = Сб + 1 + 3 + 6 + 10 + 15, При заданной структуре построения код синдрома Б, - Я любого "треугольного" кода формируется в корректирующем коде "2 из ш" (так называемом, "штриховом коде), Это означает, что номер позиции каждого информационного символа (включая символ С ) определяется его двумерной координатой на плоскости (Б;,Я),где 1, - соответственно номер столбца и строки, в котором расположен информационный символ. Например (фиг.З) первый информационный разряд (символ С ) треугольного 21,15 кода имеет координаты Б, Б , так как расположен в первом столбце и шестой строке прямоугольного треугольника, а девятый информационный разряд 21,15 кода имеет координаты Б,Б (входит в третье и пятое проверочное соотношение), так как он расположен в третьем столбце и пятой строке этого треугольника. Аналогично определяется и двумерная координата каждого информационного символа треугольного кода при любой разрядности К15. Так девятый информационный символ 28,21 треугольного кода (кодирующая Н-матрица не показана) имеет координаты Б, Б , так как он расположен соответственно в третьем столбце и шестой строке данной треугольной матрицы.В общем случае сформированный для устройства (С , + ш, Сп 1 )треугольныйкод с модифицированным алгоритмом построения кодирующей Н-матрицы, согласно которой разряд общей четности исходного сообщения С, участвует в Формировании контрольных разрядов треугольного кода наравне с остальными информационными разрядами, имеет кодовое расстояние й = 4, при этом разряд общей четности С, исходного 10 сообщения будет и разрядом общей четкости для сформированного корректирующего кода. Кроме того, при декодиро вании модифицированного треугольного кода независимо от других разрядов 15 вырабатывается (и при необходимости корректируется ) разряд общей четности С, выходного К-разрядного сообщенияТаким образом, выходная информа ция вырабатывается устройством также в корректирующем коде, что позволяет обнаружить ошибки в выходной инФормации при дальнейшем прохождении этой информации по магистрали (схе мой контроля передач по магистрали).Рассмотрим работу устройства на примере реализации одного конкретно-. го, например 21,15, модифицированного треугольного кода с параметрами: 30 число контрольных разрядов т = 6, число информационных разрядов К = 15 (числу сочетаний из шести по два), треугольная Н-матрица которого предс-,тавлена на фиг,З).Для реализации данного конкретного 21,15 треугольного кода устройство для коррекции.и обнаружения ошибок (фиг.4) содержит блок 1 формирования контрольных сигналов треугольного 40 21,15 кода, состоящий соответственно из шести (ш=б) шестивходовых сумматоров 2- 2 по модулю два и шести элементов НЕ .11 шестивходовый формирователь 3 Одиноч ых и двойн х оши бох, а также пятнадцать (К=15) коммутаторов-корректоров 4,-4, одиночных ошибок, число адресных входов каждо" го из которых равно трем. Количество коммутаторов 4 и количество суммаг торов 2 связаны соотношением К = С,. Схема подключения входов 5 и б устройства к входам сумматоров 2-2. а также схема подключения информационных входов 5 устройства и первых55 выходов сумматоров 2- 2 к трем адресным и трем информационным входам каждого коммутатора определяется треугольной Н-матрицей реализованного вустройстве кода (Фиг,З),При этом каждый сумматор 2,- 2блока 1 формирования контрольных сигналов подключен соответствующим образом к одному (одноименному) контрольному разряду входа 6 устройстваи к пяти информационным разрядам входа 5 устройства.Каждый коммутатор-корректор 4,-4,подключен соответствующим образом кодному одноименному информационномуразряду входа 5 устройства и двум(из шести) сумматорам 2,- 2 а блока 1формирования контрольных сигналов;каждый информационный разряд (1 рр)входа 5 устройства подключен к входуодноименного коммутатора-корректора 4- 4, и к входам двух (из шести)соответствующих сумматоров 2,- 2,формирующих номер позиции, которуюзанимает данный информационный разрядв треугольной Н-матрице 21,15 кода(фиг.З). Формирователь 3 кода ошибки подключен к инверсным выходам сумматоров 2,-26 блока 1 формированияконтрольных сигналов.Таким образом, оборудование, необходимое для схемной реализации одной декодирующей ветви устройства(всего в предлагаемом устройстве можно выделить пятнадцать таких ветвей),состоит из двух сумматоров по модулюдва и одного коммутатора, соединенных соответствующим образом с одниминформационным разрядом входа 5 и выхода 8 устройства.На Фиг.4 показаны три декодирующие ветви устройства, т.е. схемнаяреализация декодирования трех разрядов информацж.Б общем случае для реализации любого треугольного кода, параметры которого связаны соотношением К=Сгоборудование одной декодирующей ветви устройства, необходимое для обработки одного искаженного информацион ного символа (определения его местоположения и соответствующей коррекции) всегда состоит из двух ш-вхоцовых сумматоров и одного коммутаторас тремя адресными входами, соединенных соответствующим образом с одниминформационным разрядом входа 5 и выхода 8 устройства.Таким образом, при реализации вустройстве треугольного кода с информационной разрядностью К15 усложне 1377918, ние устройства выразится только в увеличении числа входов (ш 6) каждого сумматора 2, -2по модулю два, где ш - число контрольных разрядов соот ветствующего треугольного кода, а число адресных входов коммутаторов-корректоров 4,-4 не увеличивается и всегда равно трем. Например, в случае реализации в устройстве 36, 28 тре угольного кода с параметрами: К = 28, ш = 8, оборудование одной декодирующей ветви устройства состоит соответ.- ственно из двух восьмивходовых сумматоров и одного коммутатора с тремя 15 адресными входами.Устройство (фиг.4) работает следующим образом.Элементы НЕ 11 при записи информации в память обнуляют входы суммато ров.2,- 2 ь, на которые в режиме чтения поступают контрольные разряды С 1 - Сб, Одновременно высокий уровень управляющего сигнала Зал" блокирует работу коммутаторов-корректоров 4 -4 25 на которых в режиме чтения происходит коррекция искаженных информационных сигналов входа 5 устройства.Перед записью в память (не показана) на входы 5 устройства в блок 1 30 формирования контрольных сигналов поступает исходное пятнадцатираэрядное сообщение, первым информационным разрядом (1 р) которого является разряд общей четности С исходного сообщенияВ блоке 1 формирования контрольных сигналов происходит формирование шести контрольных разрядов С 1 - Сб иэ пятнадцати разрядов исходной информации согласно треугольной Н-матрице 40 21,15 кода (фиг.З). Сформированные разряды С 1 - Сб поступают на выход 7 устройства для записи в память. В режиме чтения (низкий уровень управляющего сигнала Эап ) из памя 11 й 45 ти на входы 5 и 6 устройства параллельно поступает очередное 21-разрядное сообщение, записанное в модифицированном треугольном коде, В сумматорах 2,-2 блока 1 формирования. конт рольных сигналов осуществляется операция свертки по модулю два соответствующих информационных расходов входа 5 и контрольных разрядов входа 6 устройства в шестираэрядный код синд рома Б,-Б 6 согласно треугольноймат-: рице 21,15 корректирующего кода (фиг,З),На первых выходах сумматора 2, -2 блока 1 формируются разряды синдрома Я-Б 6, каждые два из которых в сочетании являются двумерной координатой позиции определенного искаженного информационного символа (1 р - 15 р) входа 5. На вторых (инверсных) выходах сумматоров 2, - 26 блока 1 формируются соответственно инверсные значения разрядов синдрома Б-Б . Сформированные в блоке 1 разряды синдрома Я 1- Б попарно поступают на второй (В) и третий (С) адресный вход каждого коммутатора-корректора 4,- 4, одиночной ошибки и одновременно. с ин версных выходов блока 3 на вход формирователя 3 кода ошибки поступает для анализа инверсный код синдрома Я- Б . На первый (А) адресный вход каждого коммутатора-корректора 4 - 4, поступает одноименный информационный разряд (1 р - 15 р) входа 5 устройства,Кажцьм коммутатор-корректор 4, - 4, анализирует два из шести соответствующих разрядов синдрома Я; и Б , поступающие на его входы В и С как старшие разряды адреса, и один информационный разряд, поступающий на вход А как младший разряд адреса, причем этот информационный разряд рас-. положен именно в 1-м столбце и 1-й строке треугольной Н-матрицы (фиг.З), Так, первый (1 р = С ) информационный разряд входа 5 устройства, расположенный согласно треугольной Н-матрице.в первом столбце и шестой строке, поступает вместе с разрядами синдрома Я, и Б , в формировании которых он участвует, на три адресных входа коммутатора 4 как двоичный код адреса СВА, младшим разрядом которого является значение первого (1 р) информационного разряда 5.Второй (2 р) информационный разряд, расположенный в первом столбце и пятой строке, поступает вместе с разрядами синдрома Я и Б на три адресных входа коммутатора 4 а пятнадцатый (15 р) информационный разряд, расположенный в пятом столбце и шестой строке треугольной матрицы, поступает вместе с разрядами синдрома Б и Я на три адресных входа коммутатора 4.Каждый коммутатор-корректор 4, - 4 воспринимает три разряда, поступившие на его адресные входы, как обычное двоичное число, соответствующее1377918номеру одного из восьми информационного входа данного коммутатора, зна-чение которого пропускается на вы-,ход 8 устройства. Когда на адресныевходы СВА одного из коммутаторов поступает двоичное число 110 или 111,соответствующее шестому или седьмомуинформационному входу данного коммутатора, на выход 8 устройства передается значение, инверсное младшемуразряду адреса (по шестому адресномувходу передается значение С = 1, поседьмому - "0"). Это равносильно исправлению искаженного информационного символа входа 5 устройства,При поступлении на адресные входылюбого коммутатора-Корректора 4, - 4,двоичного числа 000-101 (т.е. еслиадрес коммутатора СВА не равен 6или 7) на выход 8 устройства пропускается или младший разряд адреса (А)или один иэ старших разрядов адреса(С или В), значение которого совпадает со значением младшего разрядаадреса А, т,е, истинное значение одноименного информационного символавхода 5 устройства.Таким образом, каждый коммутатор-корректор 4, - 4 настроенный надвумерную координату соответствующего информационного символа, каждыйраэ при считывании информации из памяти анализирует два старших разрядасвоего адреса С и В и при поступлении адреса 6 или 7 производит "исправление" одноименного информационного символа входа 5 устройства.формирователь 3 кода ошибки анализирует инверсный код синдрома Ы, сформированный в блоке 1, и вырабатывает на выходах 9 и 10 устройства парафазный код ошибки (01 или 10) по следующему пРавилУ при 45 отсутствии ошибок на входы формирователя 3 поступает единичный код синдрома, что соответствует нулевому синдрому 8,- Б на первых выходах блока 1. В этом случае сигналы навыходах 9 и 10 не вырабатываются (код ошибки00), Инверсный код синдро 1 1 ма, содержащий только один нулевой символ, Формирователь 3 расшифровывает как одиночную ошибку в контроль 55 ном символе С 1 - Сб входа б устройства или как одиночную неисправность 10одного из сумматоров 2,- 26,При этом на выходе 9 устройства появляется . сигнал "Исправляемая ошибка" (код ошибки = 10), Инверсный код синдрома, содержащий ровно два "Нулевых" символа, формирователь 3 расшифровывает как одиночную ошибку на информационном входе 5 устройства, при этом также появляется сигнал на выходе 9 устройства (код ошибки = 10), При поступлении на вход формирователя 3 инверсного кода "запрещенного" синдрома, содержащего более чем два "нулевых" символа, формирователь 3 формирует на выходе 10 устройства сигналНеисправляемая ошибка" . (код ошибки = 01), поступающий от пользователя как сигнал "Отказ от декодирования", В данном случае в информации, считанной изпамяти, или в самом устройстве, произошли многобитовые ошибки кратности 11, исправить которые устройство не может.Формула изобретенияУстройство для обнаружения и коррекции ошибок памяти, содержащее блок формирования контрольных сигналов, состоящий из сумматоров помодулю два по числу контрольных разрядов корректирующего кода, причем одни входы сумматоров по модулю два являются информационными входами устройства и соединены с одними информационными входами коммутаторов-корректоров, выходы которых являются информационными выходами устройства, о т л и ч а ющ е е с я тем, что, с целью повыше ния надежности устройства, в него введен формирователь кода ошибки, выходы которого являются контрольными выходами устройства, а входы соединены с инверсными выходами сумматоров по модулю два, другие входы которых являются входами контрольных разрядов устройства, а прямые выходы являются выходами контрольных разрядов устройства, первый адресный вход каждого коммутатора-корректора подключен к со" ответствующему информационному входу устройства, а второй и третий адресные входы и другие информационные входы каждого коммутатора-корректора соединены с прямыми выходами двух соответствующих сумматоров по модулю два, 1379181377918 Составитель О,ИсаевТехред И.Попович Корректор М. Редактор В.Слободян Заказ 880/4 исноССР Производственно-полиграфическое предприятие, г.ужгород, ул НИИПИпо130 Тираж 590 Подлосударственного комитета См изобретений и открытийМосква, Ж, Раушская наб.