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

со vj

Изобретение относится к вычислительной технике и может быть использовано для исправления одиночных и обнаружения многократных ошибок в памяти и магистралях передачи данных. Целью изобретения является повышение надежности устройства. Устройство содержит блок формирования контрольных сигналов, состоящий из сумматоров по модулю два по числу контролышх разрядов корректирующего кода, коммутаторы-1 ;орректоры по числу информационных разрядов и формирова-. ель кода ошибки. В устройстве реализован треугольный (С, +mj С ) код с модифицированным алгоритмом построения кодирующей Н-матрицы, согласно которой разряд общей четности исходного сообщения участвует в формировании контрольных разрядов наравне с информационными разрядами. Повышение надежности устройства достигается распараллеливанием схемы декодирования, при этом все ветви декадера являются равнонадежнь ми, а количество оборудования, необходимого для обработки одного искаженного символа, не зависит от разрядности входного сообщения. 4 ил. с (О (Л

00

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

Целью изобретения является повышение надежности устройства.

На фиг.1 представлена структурная схема устройства для обнаружения и коррекции ошибок памяти; на фиг.2 и 3 геометрическая интерпретация кодирующей Н-матрицы для (15,10).и (21,15) модифицированных треугольных кодов с параметрами, соответственно равными: ю 5, К С 10 (для J5, 10 кода) и , (для 21,15 кода); на фиг.4 - вариант схемного выполнения устройства для одного конкретного случая его применения

декодирования 21,J 5 треугольного кода J.

Устройство (фиг,) содержит блок формирования контрольных сигналов, состоящий из m (по числу контрольных разрядов входного корректирующего кода) т-входовых сумматоров 2--2 по j; модулю два, т-входовый формироват : тель 3 кода ошибки и К (по числу ИН :- формационных разрядов входного кор- ректирующего кода) коммутаторов-корректоров 4,- 4к одиночных ошибок, каждый из которых имеет три адресных входа. Число сумматоров и число коммутаторов в устройстве всегда связа- но соотношением ,

Устройство имеет информационные входы 5, 6 и выходы 7 контрольных рарядов, информационные выходы 8 и контрольные выходы 9 и iO,

Блок 1 формирования контрольных сигналов служит для формирования конрольных разрядов С,- Cm треугольного кода (в режиме записи в память) и формирования разрядов синдрома Б,-Б,„ (в режиме считывания из памяти) для декодирования треугольного кода.

Формирователь 3 кода ошибки служи для фop шpoвaния на выходах 9 и 10 устройства парафазного (01 или 10) кода ошибки в случае возникновения ошибок на входах 5 и 6 устройства, или в самих сумматорах 2,-2т , формирующих номер позиции искаженного информационного символа.,,

Коммутаторы-корректоры 4,-4 одиночных ошибок служат для непосредственной коррекций искаженных информационных символов входа 5 устройства

и формирования на выходах. 8 выходного К-разрядного сообщения, при этом коммутатор 4 формирует (и корректирует при необходимости) контрольный символ Cjy, который является разрядом общей четности выходного К-разрядного сообщения,

Схема подключения входов 5 и 6 устройства к входам сумматоров 2,-2 блока формирования контрольных сигналов , а также информационных входов 5 устройства и первых выходов сумматоров к трем адресным входам коммутаторов 4,- определяется кодирующей, Н-матрицейьпримененного в устройстве треугольного кода, основное свойство которого заключается в том, что параметры его (число контрольных разрядов m и число информационных разрядов к) всегда связаны соотношением: К равно числу сочетаний m по два, что наглядно иллюстрируется (фиг,2 и З) на примере построен- ния 15, 10 (К Су) и 2J,5 (к С) треугольных кодов.

На фиг.2 и 3 цифрами 1-15 обозначены информационные разряды треугольного кода, Со - разряд общей четности и одновременно первый информаци- онньй разряд исходного К-разрядного сообщения, CJ. - Сб - контроль ные разряды формируемого для устройства кода.

На фиг,4 информационные разряды входа 5 устройства обозначены 1р-J5p информационные разряды выхода в устройстве обозначены J разряд - 15 разряд. Первый разряд выхода 8 (1 разряд) является одновременно разрядом общей четности Сд выходного пятнадцатиразрядного сообщения,.

Устройство реализует (С +т, С ) модифицированный треугольный код с кодовым расстоянием 4, с числом контрольных разрядов m 5: 5, числом информационных разрядов К С (т,е, равным числу сочетаний из m по два) и числом позиционных разрядов п К + + m Сг„,, геометрическая структура построения кодирующей Н-матрицы которого позволяет реализовать в устройстве простой алгоритм декодирования, так как при любой разрядности К входного сообщения двоичный код номера позиции каждого информационного символа содержит ровно две ецинии г, соответствующее двумерной координате

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

Входной корректирующий код для устройства формируется из исходного К-разрядного сообщения, состоящего из К-1 информационных разрядов и од- t5 ного контрольного разряда С по общей четности исходного сообщения по следующему алгоритму (фиг.2,3): контрольный символ Сд исходного К-разрядного сообщения, рассматриваемый при 20 построении кода как первый информа- ционньй символ, помещается в вершие прямоугольндго треугольника, остальные информационные символы исход- ного сообщения размещаются в соответ- 25 ствующих фиксированных позициях пряоугольного треугольника, а контрольные символы Cl-Cm формируемого кода располагаются на гипотенузе этого триугольника в местах пересечения ЗО строк и столбцов соответствующих симолов, чем и определяется простое равило вычисления значений контрольых разрядов Cl-Cm треугольного кода: значение каждого контрольного симвоа, расположенного на гипотенузе, обазуется сверткой по модулю два опеделенной подгруппы информационных символов, входящих в соответствующий столбец и строку прямоугольного тре- Q угольника, на пересечении которых этот контрольный символ расположен. Это правило наглядно иллюстрируется на примере построения двух треугольных кодов: 15,10 (К 10, ) и2Г,15 45 (к 15, m 6). Например, (фиг.2): контрольные разряды С1 - С5 треугольного J5, JO кода вычисляются по формулам:

50

CJ 1+2+4+7;

С2 3+5+8+7; 03 6+9+4+8; С4 J0+2+5+9; С5 1+3+6+10.

55

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

г ю

t5 0 5 О Q 5 0

5

двух контрольных символов CI - С5 (и, следовательно, в формировании равно двух соответствующих разрядов синдрома S,- $5 при декодировании треугольного 15, 10 кода. Например, девятьй информационный символ (подчеркнут) участвует в формировании контрольных символов СЗ и С4. Это правило распространяется на треугольные коды с любой разрядностью К исходного сообщения: (21,15), (28,21} ,(36,28), (45,36), (55,45) и т.,д., параметры которых всегда связаны соотношением К С. Например, проверочные (фиг.З) соотношения для вычисления разрядов синдрома S,- Бб треугольного кода 21, 15 кода (15 С) формируются следующим образом:

S, CJ+J+2+4+7+ll; Sj С2 + 3 + 5 + 8 + 12 + И; S, СЗ + 6 + 9 + 13 + 7 + 12; S С4 + 10 + J4 + 4 + 8 + 13; S5 С5 + 15 + 2 + 5 + 9 + 14; Sg С6 + 1 + 3 + 6 + 10 + 15. При заданной структуре построения код синдрома Б,- БГ„ любого треугольного кода формируется в корректирующем коде 2 из т (так называемом, штриховом коде. Это означает, что номер позиции каждого информационного символа (включая символ С) определяется его двумерной координатой на плоскости (В;,Б)),где i,j - соответственно .номер столбца и строки, в котором расположен информационньй символ. Например (фиг.З) первый информационный разряд (символ С) треугольного 21,15 кода имеет координаты S,, S, так как расположен в первом столбце и шестой строке прямоугольного треугольника, а девятый информационный разряд 21,15 кода имеет координаты 85,85 (входит в третье и пятое проверочное соотношение), так как он расположен в третьем столбце и пятой строке этого треугольника. Аналогично определяется и двумерная координата каждого информационного символа треугольного кода при любой разрядности К 15. Так девятьй информационный символ 28,21 треугольного ко- да (кодирующая Н-матрица не показана) имеет координаты Sj, S, так как он расположен соответственно в третьем столбце и шестой строке данной треугольной матрицы.

В общем случае сформированньш для устройства ( т, С )треуголькый

код с модифицированным алгоритмом цостроения кодирующей Н-матрицы, согласно которой разряд общей четности исходного сообщения С, участвует в формировании контрольных разрядов треугольного кода наравне с остальными ннформационныии разрядами, имеет кодовое расстояние d А, при этом разряд общей четности С,, исходного сообщения будет и разрядом общей четности для сформированного корректирующего кода. Кроме того, при декодиро вании модифицированного треугольного кода независимо от других разрядов вырабатывается (и при необходимости корректируется) разряд общей четности С о выходного К-разрядного сообщения. ;

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

Рассмотрим работу устройства на примере реализации одного конкретног-- го, например 21,J5, модифицированного треугольного кода с параметрами: число контрольных разрядов m 6, числоинформационных разрядов К J5 (числу сочетаний из шести по два), треугольная Н-матрица которого предс тавлена на фиг.З.

Для реализации данного конкретного 2,5 треугольного кода устройств для коррекции.и обнарз ения : ошибок (фиг.4) содержит блок 1 формировани контрольных сигналов треугольного 21,15 кода, состоящий соответственно из шести () шестивходовых сумматоров 2,- 25 по модулю два и шести элементов НЕ-JJ, шестивходовьй формирователь 3 одиночных и двойных оши бок, а также пятнадцать () коммутаторов-корректоров одиночных ошибок, число адресных входов каждого из которых равно ,трем. Количество коммутаторов 4 и количество сумма-

торов 2 связаны соотношением К С„.

Схема подключения входов 5 и 6 устройства к входам сумматоров а также схемй подключения информационных входов 5 устройства и первых выходов сумматоров 2,- 2 к трем адресным и трем информационным входам каждого коммутатора определяется треугольной Н-матрицей реализованного в устройстве кода (фиг.З),

При этом каждый сумматор 2,- 2 блока J формирования контрольных сигналов подключен соответствующем образом к одному (одноименному) контрольному разряду входа 6 устройства и к пяти информационным разрядам входа 5 устройства.

Каждый коммутатор-корректор 4,-4,5 подключен соответствующим образом к одному одноименному информационному разряду входа 5 устройства и двум (из щести) сумматорам 2,- 2 блока 1 формирования контрольных сигналов; каждый информационньй разряд (Jp-lSp) входа 5 устройства подключен к входу одноименного коммутатора-корректора 4,- 4,5-и к входам двух (из шести) соответствующих сумматоров 2,- 2, формирующих номер позиции, которую занимает данный информационный разряд в треугольной Н-матрице 21,15 кода (фиг.З). Формирователь 3 кода ошибки подключен к инверсным выходам сумматоров 2,-2g блока 1 формирования контрольных сигналов.

Таким образом, оборудование, необходимое для схемной реализации одной декодирующей ветви устройства (всего в предлагаемом устройстве можно выделить пятнадцать таких ветвей) состоит из двух сумматоров по модулю два и одного коммутатора, соединенных соответствзтощим образом с одним информационным разрядом входа 5 и вы- .хода 8 устройства.

На фиг.4 показаны три декодирук - щие ветви устройства, т.е. схемная .реализация декодирования трех разрядов информации.

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

Таким образом, при реализации в устройстве треугольного кода с информационной разрядностью К 15 усложне, ние устройства выразится только в увеличении числа входов () каждого сумматора 2,-2 по модулю два, где m - число контрольных разрядов соот-- ветствующего треугольного кодй, а число адресных входов коммутаторов-корректоров 4,-4 не увеличивается и всегда равно трем. Например, в случае реализации в устройстве 36, 28 тре- yroj bHoro кода с параметрами: К 28, m 8, оборудование одной декодирую- щей ветви устройства состоит соответ ственно из двух восьмивходовых сумматоров и одного коммутатора с тремя адресными входами.

Устройство (фиг.4) работает сл&цук щим образом.

Элементы НЕ 11 при записи информации в память обнуляют входы суммато- ров-2,- 2g, на которые в режиме чтения поступают контрольные разряды С1 - С6, Одновременно высокий уровень управляющего сигнала Зап блокирует работу коммутаторов-корректоров 4,-45 на которых в режиме чтения происходит коррекция искаженных информационных сигналов входа 5 устройства.

Перед записью в память (не показана) на входы 5 устройства в блок 1 формирования контрольных сигналов по- ступает исходное пятнадцатиразрядное сообщение, первым информационном разрядом (1р) которого является разряд общей четности С -исходного сообщения

В 1 формирования контрольных сигналов происходит формирование шести контрольных разрядов С1 - Сб из пятнадцати разрядов исходной информации согласно треугольной Н-матрице 21,15 кода (фиг.З). Сформированные разряды С1 - С6 поступают на выход 7 устройства для записи в память.

В режиме чтения (низкий уровеш управляющего сигнала Зап) из памяти на входы 5 и 6 устройства параллельно поступает очередное 21-разрядное сообщение, записанное в модифицированном треугольном коде. В сумматорах блока J формирования- контрольных сигналов осуществляется операция свертки по модулю два соответствующих информационных расходов входа 5 и контрольных разрядов входа 6 устройства в шестиразрядный код синд- рома 8(-5б согласно треугольной мат-- рице 21,15 корректирующего кода (фиг.З).

На первых выходах сумматора 2,-2 блока 1 формируются разряды синдрома , каждые два из которых в сочетании являются двумерной координатой позиции определенного искаженного информационного символа (Jp - 15р входа 5. На вторых (инверсных) выходах сумматоров 2,- 2g блока 1 формируются соответственно инверсные значения разрядов синдрома . Сформированные в блоке 1 разряды синдрома S,- Sg попарно поступают на второй IB) и третий (с) адресный вход каждого коммутатора-корректора 4,- 4, одиночной ошибки и одновременно с инверсных выходов блока J на вход формирователя 3 кода ошибки поступает для анализа инверсный код синдрома S,- Sg. На первый (А) адресный вход каждого коммутатора-корректора 4, - 4, поступает одноименный информационный разряд (1р-- 15р) входа 5 устройства.

Каждый коммутатор-корректор 4,- 4,5- анализирует два из шести соответст- вую1Щ1х разрядов синдрома S и S; , поступающие на его входы В и С как старшие разряды адреса, и один информационный разряд, поступающий ria вход А как младший разряд адреса, причем этот информационный разряд рас положен именно в i-м столбце и j-й строке треугольной Н-матрицы (фиг.З). Так, первый (1р С) информационньй разряд входа 5 устройства, располо- женньй согласно треугольной Н-матрице. в первом столбце и шестой строке, поступает вместе с разрядами синдрома S, и Sj,, в формировании которых он участвует, на три адресных входа коммутатора 4 как двоичньй код адреса СВА, младшим разрядом которого является значение первого (1р) информационного разряда 5. Второй (2р) инфор- мационньй разряд, расположенный в первом столбце и пятой строке, поступает вместе с разрядами синдрома Sj и Sy на три адресных входа коммутатора 42,..., а пятнадцатый (15р информационный разряд, расположенный в пятом столбце и шестой строке треугольной матрицы, поступает вместе с разрядами синдрома Sj и 8б на три адресных входа коммутатора 4,5.

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

91377

номеру одного из восьми информационного входа данного коммутатора, значение которого пропускается на выход 8 устройства. Когда на адресные входы СВА одного из коммутаторов поступает двоичное число 110 или 1П, соответствующее шестому или седьмому информационному входу данного коммутатора, иа выход 8 устройства пере- дается значение, инверсное младшему разряду адреса (по шестому адресному входу передается значение С J, по седьмому - О). Это равносильно исправлению искаженного информационно- го символа входа 5 устройства.

При поступлении на адресные входы любого коммутатора-корректора 4, - 4, двоичного числа 000-1OJ (т.е. есл и адрес коммутатора СВА не равен 6 или 7) на выход 8. устройства пропускается или младший разряд адреса (А) или один из старших разрядов адреса (с или в), значение которого совпадает со значением младшего разряда адреса А, т,е, истинное значение одноименного информационного символа входа 5 устройства.

Таким образом, каждый коммутатор-корректор 4(- 4,5, настроенньй на двумерную координату соответствующего информационного символа, каждый раз при считьшании информации из памяти анализирует два старших разряда своего адреса С и В и при поступлении адреса 6 или 7 производит исправление одноименного информационного символа входа 5 устройства.

Формирователь 3 кода ошибки ана- лизирует инверсньш код синдрома SJ- S6, сформированный в блоке 1, и вырабатывает на выходах 9 и 10 устройства парафазный код ошибки (OJ или 10) по следующему правилу: при отсутствии ошибок на входы формирователя 3 поступает единичный код синрома, что соответствует нулевому ,- синдрому S,- Sg-на первых выходах

блока 1, В этом случае сигналы на вы

ходах 9 и 10 не вырабатываются (код ошибки 00). Инверсный код синдрома, содержащий только один нулевой символ, формирователь 3 расшифровьша ет как одиночную ошибку в контрольном символе С1 - С6 входа 6 устройства или как одиночную неисправност

Q

Q

0

10

одного из сумматоров 2g.IIpH зток на выходе 9 устройства появляется . сигнал Исправляемая ошибка (код ошибки 10), Инверсный код синдрома, содержащий ровно два Нулевых символа, формирователь 3 расшифровьшает как одиночную ошибку на информационном входе 5 устройства, при этом также появляется сигнал на выходе 9 устройства (код ошибки JO). При поступлении на вход формирователя 3 инверсного кода запрещенного синдрома, содержащего более чем два нулевых символа, формирователь 3 формирует на выходе 10 устройства сигнал Неисправляемая ошибка (код ошибки 01 ), поступающий от : пользователя как сигнал Отказ от декодирования, В данном случае в информации, считанной из памяти, или в самом устройстве, произошли многобитовые ошибки кратности , исправить которые устройство не может,

Формула изобретения

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

Со-1 3 6 W Фиг. 2

Фиг.1

С

45 /J

С5

h

5 9 /4

3 б 10 15

Фцг.з

С6

фиг. if