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

 

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

СОЮЗ СОВЕТСКИХ

СОЦИАЛИСТИЧЕСНИХ

РЕСПУБЛИК (19) (И) А1 (g)) 4 G ll С 29/00

ГОСУДАРСТВЕННЫЙ НОМИТЕТ СССР

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИИ ф p(ai: .,-;, (сигналов, состоящий из сумматоров по модулю два по числу контрольных разрядов корректирующего кода, коммутаторы-корректоры по числу информационных разрядов и формирова; ель кода ошибки. В устройстве реализован тре2 т угольный (С, +m С ) код с модифицированным алгоритмом построения кодирующей Н-матрицы, согласно кото" рой разряд общей четности исходного сообщения участвует в формировании контрольных разрядов наравне с информационными разрядами. Повышение надежности устройства достигается распараллеливанием схемы декодирования, при этом все ветви декадера являются равнонадежными, а количество оборудования, необходимого для обработки одного искаженного символа, не зависит от разрядности входного сообщения. 4 ил. (21) 4143241/24-24 (22) 11.07.86 (46) 29.02.88. Бюл. ¹ 8 (72) В.З.Абрамов, А.А.Воловник и А.Б.Савинова. (53) 681.327.6(088.8) (56) Авторское свидетельство СССР

¹ 1026165, кл. G 11 С 29/00, 1982.

Авторское свидетельство СССР

¹ 1149318. кл. 0 ll С 29/00, 1983. (54) УСТРОЙСТВО ДЛЯ ОБНАРУЖЕНИЯ

И КОРРЕКЦИИ ОШИБОК ПАМЯТИ (» ) Изобретение относится к вычислительной технике и может быть использовано для исправления одиночных и обнаружения многократных ошибок в памяти и магистралях передачи данных, Целью изобретения является повышение надежности устройства. Устройство содержит блок формирования контрольных

ОПИСАНИЕ ИЗОБРЕТЕНИЯ ц " !

И А BT0PCH0IVIV СВИДЕТЕЛЬСТВУ Н%ЛN„

137? 918

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

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

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

10кода) и m=6, К=С =15 (для

2l,15 кода); на фиг.4 — вариант схемного выполнения устройства для одного конкретного случая его применения 20 (декодирования 21,15 треугольного кода1.

Устройство {фиг,1 ) содержит блок 1 формирования KOHTpoJI&HbIZ сигналов, состоящий из m (по числу контрольных разрядов входного корректирующего кода) m-входовых сумматоров 2 -2 по .: модулю два, m-входовый формирова тель 3 кода ошибки и К (по числу ин= формационных разрядов входного корректирующего кода) коммутаторов-корректоров 4, — 4„ одиночных ошибок, каждый из которых имеет три адресных входа. Число сумматоров и число коммутаторов в устройстве всегда связаг но соотношением К=С

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

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

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

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

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

m по два, что наглядно иллюстрируется (фиг.2 и 3) на примере построенния 15, 10 (К = С .)и 21,15 (К = С,) треугольных кодов.

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

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

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

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

1377918

Cl = 1+2+4+7;

С2 = 3+5+8+7;

СЗ = 6+9+4+8;

С4 = l0+2+5+9;

C5 = 1+3+6+10, 55

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

Входной корректирующий код для устройства формируется из исходного

К-разрядного сообщения, состоящего из К-1 информационных разрядов и од- 15 ного контрольного разряда С, по общей четности исходного сообщения по следующему алгоритму (фиг.2,3): контрольный символ С исходного К-разрядного сообщения, рассматриваемый при 20 построении кода как первый информационный символ, помещается в вершине прямоугольного треугольника, остальные информационные символы исход ного сообщения размещаются в соответ- 25 ствующих фиксированных позициях прямоугольного треугольника, а контрольные символы Cl-Cm формируемого кода располагаются на гипотенузе этого триугольника в местах пересечения строк и столбцов соответствующих символов, чем и определяется простое правило вычисления значений контрольных разрядов Cl-Cm треугольного кода: значение каждого контрольного симво35 ла, расположенного на гипотенузе, образуется сверткой по модулю два определенной подгруппы информационных символов, входящих в соответствующий столбец и строку прямоугольного тре- 40 угольника, на пересечении которых этот контрольный символ расположен, Эта правило наглядно иллюстрируется на примере построения двух треугольных кодов: l 5,10 (K = 10, m=5) и 21,15 45 (K = 15, m =6). Например, (фиг.2); контрольные разряды Cl — C5 треуголь" ного l 5, lO кода вычисляются по формулам: двух контрольных символов Cl — C5 (и, следовательно, в формировании равно двух соответствующих разрядов синдрома S, — S при декодировании треугольного 15, 10 кода. Например, девятый информационный символ (подчеркнут) участвует в формировании контрольных символов СЗ и С4. Это правило распространяется на треугольные коды с любой разрядностью К исходного сообщения: (21,15), (28,21 ),(36«28), (45,36), (55,45) и т.,д., параметры которых всегда связаны соотношением

К = С . Например, проверочные (фиг.3) соотношения для вычисления разрядов синдрома S, — 56 треугольного кода 21

15 кода (15 = С ) формируются следующим образом:

S„ = Cl + l + 2 + 4 + 7 + 1 1;

S = C2 + 3 + 5 + 8 + l2 + 11;, $, =СЗ+6+9+13+7+12;

S = С4 + 10 + 14 + 4 + 8 + 13;

5 = C5 + 15 + 2 + 5 + 9 + 14;

S = С6 + 1 + 3 + 6 + 10 + 15, При заданной структуре построения код синдрома Б, — Я любого "треугольного" кода формируется в корректирующем коде "2 из m" (так называемом, "штриховом" коде}. Это означает, что номер позиции каждого информационного символа (включая символ С ) определяется его двумерной координатой на плоскости (S;,S ),где f,g - соответственно номер столбца и строки, в котором расположен информационный символ. Например (фиг.3) первый информационный разряд (символ С ) треугольного 21,15 кода имеет координаты S<, S, так как расположен в первом столбце и шестой строке прямоугольного треугольника, а девятый информационный разряд 21 15 кода имеет координаты S,S {входит в третье и пятое проверочное соотношение), так как он расположен в третьем столбце и пятой строке этого треугольника. Аналогично определяется и двумерная координата каждого информационного символа треугольного кода при любой разрядности К > 15. Так девятый информационный символ 28,21 треугольного ко да (кодирующая Н-матрица не показана) имеет координаты S, S, так как он расположен соответственно в третьем столбце и шестой строке данной треугольной матрицы.

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

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

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

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

Для реализации данного конкретного 21,15 треугольного кода устройство для коррекции.и обнаружения ошибок (фиг.4) содержит блок 1 формирования контрольных сигналов треугольного 40

21,15 кода, состоящий соответственно из шести (ш=6) шестивходовых сумматоров 2 „- 2 по модулю два и шести элементов НЕ .11 шестивходовый формироват ь 3 од ноч х и двой 1х оен- 45 бох, а также пятнадцать (К=15) коммутаторов-корректоров 4,-4, одиночных ошибок, число адресных входов каждо" го из которых равно трем. Количество коммутаторов 4 и количество суммаг торов 2 связаны соотношением К = С,„.

Схема подключения входов 5 и б устройства к входам сумматоров 2„-2 . а также схема подключения информационных входов 5 устройства и первых

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

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

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

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

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

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

Таким образом, при реализации в устройстве треугольного кода с информационной разрядностью К > 15 усложне1377918, ние устройства выразится только в увеличении числа входов (ш>6) каждого сумматора 2, -2 по модулю два, где

m - число контрольных разрядов соот- 5 ветствующего треугольного кода, а число адресных входов коммутаторов-корректоров 4,-4„ не увеличивается и всегда равно трем. Например, в случае реализации в устройстве 36, 28 тре- 10 угольного кода с параметрами: К = 28, m = 8, оборудование одной декодирующей ветви устройства состоит соответ ственно из двух восьмивходовых сумматоров и одного коммутатора с тремя 15 адресными входами.

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

Элементы НЕ 11 при записи информации в память обнуляют входы суммато- 20 ров 2,- 2, на которые в режиме чтения поступают контрольные разряды

С1 — Сб, Одновременно высокий уровень управляющего сигнала Зап" блокирует работу коммутаторов-корректоров 4< -4 25 на которых в режиме чтения происходит коррекция искаженных информационных сигналов входа 5 устройства.

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

В блоке 1 формирования контрольных сигналов происходит формирование mecти контрольных разрядов С1 - Сб иэ пятнадцати разрядов исходной информации согласно треугольной Н-матрице 40

21,15 кода (фиг.3). Сформированные разряды С1 — Сб поступают на выход 7 устройства для записи в память.

В режиме чтения (низкий уровен . управляющего сигнала Зап ) из памяft u 45 ти на входы 5 и 6 устройства параллельно поступает очередное 21-разрядное сообщение, записанное в модифицированном треугольном коде. В сумматорах 2,-2 блока 1 формирования. конт- 50 рольных сигналов осуществляется операция свертки по модулю два соответствующих информационных расходов входа 5 и контрольных разрядов входа 6 устройства в шестираэрядный код синд- 55 рома S $6 согласно треугольной мат- " рице 21,15 корректирующего кода (фиг.3), На первых выходах сумматора 2,-2 блока 1 формируются разряды синдрома S„-$6, каждые два из которых в сочетании являются двумерной координатой позиции определенного искаженного информационного символа (1р - 15p) входа 5. На вторых (инверсных) выходах сумматоров 2, — 26 блока 1 формируются соответственно инверсные значения разрядов синдрома 5<-$ . Сформированные в блоке l разряды синдрома S - -SБ попарно поступают на второй (В) и третий (С) адресный вход каждого коммутатора-корректора 4,- 4, одиночной ошибки и одновременно. с инверсных выходов блока 1 на вход формирователя 3 кода ошибки поступает для анализа инверсный код синдрома

$„- S . На первый (А) адресный вход каждого коммутатора-корректора 4 - 4, поступает одноименный информационный разряд (1p- — 15p) входа 5 устройства.

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

Так, первый (1р = С -) информационный разряд входа 5 устройства, расположенный согласно треугольной Н-матрице.в первом столбце и шестой строке, поступает вместе с разрядами синдрома S, и $, в формировании которых он участвует, на три адресных входа коммутатора 4< как двоичный код адреса СВА, младшим разрядом которого является значение первого (1p) информационного разряда 5.Второй (2р) информационный разряд, расположенный в первом столбце и пятой строке, поступает вместе с разрядами синдрома S< и

$ на три адресных входа коммутатора 4,..., а пятнадцатый (15р) информационный разряд, расположенный в пятом столбце и шестой строке треугольной матрицы, поступает вместе с разрядами синдрома S и S на три адресных входа коммутатора 4 .

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

1377918 номеру одного из восьми информационного входа данного коммутатора, зна- чение которого пропускается на вы-. ход 8 устройства. Когда на адресные входы CBA одного из коммутаторов поступает двоичное число 110 или 111, соответствующее шестому или седьмому информационному входу данного коммутатора, на выход 8 устройства передается значение, инверсное младшему разряду адреса (по шестому адресному . входу передается значение С = 1, по седьмому — "0"). .Это равносильно исправлению искаженного информационного символа входа 5 устройства, При поступлении на адресные входы любого коммутатора-корректора 4, — 4, двоичного числа 000»»101 (т.е. если адрес коммутатора СВА не равен б или 7) на выход 8 устройства пропускается или младший разряд адреса (А) или один иэ старших разрядов адреса (C или В), значение которого совпадает со значением младшего разряда адреса А, т,е, истинное значение одноименного информационного символа входа 5 устройства.

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

Формирователь 3 кода ошибки анализирует инверсный код синдрома SlЯб, сформированный в блоке 1 и вырабатывает на выходах 9 и 10 устройства парафазный -код ошибки (01 или 10) по следующему правилу при 45 отсутствии ошибок на входы формирователя 3 поступает единичный код синдрома, что соответствует нулевому синдрому S Б -на первых выходах блока 1. В этом случае сигналы навыходах 9 и 10 не вырабатываются (код ошибки " 00), Инверсный код синдро1l ll ма, содержащий только один нулевой символ, формирователь 3 расшифровывает как одиночную ошибку в контроль55 ном символе С1 - Сб входа б устройства или как одиночную неисправность

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

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

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

1377918

1377918

Составитель О, Исаев

Техред И.Попович Корректор М. Пожо

Редактор В.Слободяник

Тираж 590 Подпи сно е

ВНИИПИ Государственного комитета СССР по делам изобретений и открытий

11.3035, Москва, Ж-35, Раушская наб., д.4/5

Заказ 880/49

Производственно-полиграфическое предприятие, г.Ужгород, ул.Проектная,4