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

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

Известно устройство для исправления ошибок в блоках памяти 1, содержащее (п -М)-входовый генератор кода ошибок (где п - разрядность блоков памяти, а N - их количество), блок коррекции ошибок, элементы И и М(2п+1)-входовых индикаторов неисправностей, N двухвходовых сумматоров по модулю два и (п-М)-входовыЙ сумматор по модулю два, причем входы (п М)-входового генератора кода ошибок подключены к первым входам блока коррекции ошибок и являются входами устройства, а N первых выходов (п NJ-входового генератора кода ошибок являются первыми контрольными выходами устройства, входы

(2п+1 входЪвых индикаторов неисправностей подключены к выходам (п М)-входово- го генератора кода ошибок и к одним из входов элементов И, другие входы которых соединены с выходами (2п+1)-входовых индикаторов неисправностей, а выходы элементов И подключены ко вторым входам блока коррекции ошибок, выходы которого являются выходами устройства, одни из входов двухвходовых сумматоров по модули два соединены с первыми выходами (n -N)- входового генератора кода ошибок, другие входы двухвходовых сумматоров по модулю

два и один из входов (п+1)-входового сумматора по модулю два подключены к другим выходам (п -Nj-входового генератора кода ошибок, а выходы двухвходовых сумматоров по модулю два подключены к другим входам (п+1)-входового сумматора по модулю два и являются совместно с выходом

(п-И)-входового сумматора по модулю два

VI 00

ся о

вторыми контрольными выходами устройства.

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

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

логического блока коррекции, входы второй группы первого и второго блоков коррекции ошибок подключены соответственно к первым и вторым контрольным входам 1-го логического блока коррекции, а выходы первого и второго блоков коррекции ошибок подключены соответственно к входам второй и третьей групп блока мажоритарных элементов, выходы которых подключены к

0 информационным выходам 1-го логического блока коррекции 2.

В данном устройстве реализован синд- ромно-мажоритарный алгоритм декодирования двумерного модифицированного

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

0 (2 - N) пакетов n-разрядных ошибок, одиночные групповые ошибки четного веса, а также обнаруживать одиночные ошибки, внесенные во входную информацию при записи в память.

5 Недостатками известного устройства являются его низкая надежность и ограниченные функциональные возможности.

Эти недостатки связаны с тем, что из-за низкой корректирующей возможности при-1

0 маненного в устройстве кода оно не может скорректировать даже две одиночные (или пакетные) ошибки, возникшие в разных блоках памяти, или групповую ошибку четного веса одного блока памяти, а также ошибки,

5 внесенные во входную информацию при записи в память.

Цель изобретения - расширение области применения устройства за счет обеспечения возможности исправления трех

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

5 информацию при записи в память.

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

5 и N блоков коррекции, состоящих соответственно из первого и второго блоков коррекции ошибок и блока мажоритарных элементов, причем п информационных входов каждого 1-го (I 1-N) логического блока коррекции объединены с 1-й группой входов

Ч

первого генератора кода ошибок и подключены к 1-й группе информационных вхЪДбв устройства, первые контрольные входы 1-го блока коррекции подключены соответственно к 1-му выходу первого генератора да ошибок, вторые контрольные входы блоков коррекции с первого по rrt-й, где m - количество блоков памяти первой группы, объединены между собой и подключены к первой группе выходов второго генератора кода ошибок, первый, третий и четвертый ды блока обнаруженич ошибок являю тся выходами некорректируемых ошибок уйт- ройства, второй выход- выходом руемых ошибок устройства, а первая и вторая группы входов блока обнаружения ошибок подключены соответственно Первой и второй группам контрольных выводов устройства, кроме того, в каждом i-м блоке коррекции входы первой группы первого блока коррекции ошибок объециненьГс вхо- дами первой группы второго блока коррекции ошибок и с входами первой группы блока мажоритарных элементов и по дкЛЮ- чены к информационным входам 1-го блока коррекции, входы второй группы первого и второго блоков коррекции ошибок подключены соответственно к первым и вторым контрольным входам 1-го блока коррекции, а выходы первого и второго блоков коррекции ошибок подключены соответственно к входам второй и третьей групп блока мажоритарных элеменетов, выходы которых подключены к информационным выходам 1-го логического блока коррекции, введены третий генератор кода ошибок, содержащий m групп из п блоков свертки по модулю два, блок из m индикаторов неисправностей, N блоков коммутаторов (где N т2) и группа из т элементов ИЛИ, кроме того, второй генератор кода ошибок дополнительно содержит со второй по гл-ю группы из п блоков свертки по модулю два, причем выхоД ПОр- вой и второй групп блока индикаторов нёис- правностей являются соответственно первой и второй группой контрольных выхо- доз устройства, а выходы элементов ИЛИ являются третьей группой контрольных выходов устройства и подключены соответственно к третьей группе входов блока обнаружения ошибок, при этом первый и второй выходы каждо о k-го (k 1 - m) индикатора неисправностей являются соответственно выходом некорректируемой ошибки и выходом корректируемой ошибки k-й контролируемой группы блоков пТЫЙтгИ, а каждый 1-й блок коррекции, где (к - 1)ггн-1, является соответственно I-м (i 1 - m) блоком коррекции k-й группы (где i - боот- ветствующий номер 1-го блока памяти в k-й

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

0 соответственно к 1-й n-рззрядной группе информационных выходов устройства, m сы- хбдов k-й группы выходов первого генератора кода ошибок и п выходов k-й группы выходов второго генератора кода

5 ошибок подключены соответственно к первой и второй группам входов k го индикатора неисправностей, первые п выходов 1-й группы выходов третьего генератора ко/эг ошибок подключены соответственно к вхо

0 дам 1-го элемента ИЛИ, а также к третьей группе информационных входов 1-го блока коммутаторов, вторые (инверсные) п выходов i-й группы выходов третьего генератора кода ошибок подключены соответственно к

5 четвертой группе информационных входов 1-го блока коммутаторов, вторая адресная группа входов которого подключена к первому выходу k-ro индикатора неисправностей, гторыс контрольные входи блоков

0 коррекции k и группы подключены к второй группе входов k-ro индикатора неисправностей, а управляющий вход устройства подключен соответственно к управляющему входу каждого индикатора неисправностей

5 с первого по т-й.

Введение в устройство третьего генератора кода ошибок, содержащего m групп из п блоков свертки по модулю два, блока из m индикаторов неисправностей, N блоков

0 коммутаторов и m n-входовых элементов ИЛИ с соответствующими связями, а также введение во второй генератор кода ошибок со второй по rh-io , состоящих из п блоков свертки по модулю два, и изменение

5 связей второго генератора кода ошибок с информационными входами устройства и контрольными входами логических блоков коррекции (при одновременном уменьшении в m раз числа входов каждого

0 блока свертки по модулю два второго генератора ,;ода ошибок) позволяет реализовать в устройстве корректирующий код с более высокими и более сложными (чем у прототипа) корректирующими свойствами.

5 При этом в заявленном устройстве обеспечивается возможность исправления трех пакетов n-разрядных ошибок и обнаружения (4 - N) пакетов n-разрядных ошибок, кроме того, в устройстве дополнительно обеспечивается возможность исправления

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

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

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

Декодирования с адаптацией трехмерного модифицированного итеративного кода.

На фиг. 1 представлена структурная схема устройства для обнаружения и исправления ошибок в N n-разрядных блоках памяти; на фиг. 2 - функциональная схема логического блока коррекции 9i (где I - номер блока памяти).

На фиг. 3 - геометрическая интерпретация кодовой матрицы трехмерного кода (84, 32) с параметрами: п 4, N 16, составленного из m 4 подматриц Hk двумерного кода (16,8), структура которого описана в на фиг. 4 - схема коррекции разрядов d(i,j,k) для одного (1-го) блока памяти, где i,j,k-координаты позиции каждого символа трехмерного кода в кодовой матрице (фиг. 3), I (K-1)m+i, (i,k 1 - m).

Устройство содержит (фиг. 1) первый 1 генератор кода ошибок, состоящий из блоков свертки 21-2ы по модулю два, второй 3 генератор кода ошибок, состоящий из групп 4i-4m блоков свертки 5i-5n по модулю два, и третий 6 генератор кода ошибок, состоящий из групп 7i-7m блоков свертки по модулю два (где m Vjxj), логические блоки коррекции 9r-9w (ЛБК), индикаторы неисправностей 1Qi-10m, блоки коммутаторов 11i-tlN, элементы ИЛИ 12i-12m и логический блок обнаружения ошибок 13 (ЛБО).

Устройство имеет информационные 14-|-14м группы входов, информационные 15i-15N гр уппы выходов, а также первую 16i-16m, вторую 17i-17m и третью 18i-18m группы контрольных выходов устройства, выходы 19i, 19з, 19 - некорректируемых ошибок устройства и выход 192 - корректируемых ошибок устройства, управляющий вход 20 устройства.

Генераторы 1, 3 и б кода ошибок имеют соответственно выходы 21, 22 и 23, 24, а логические блоки 9 коррекции - имеют выходы 25.

Каждый Логический блок 9i коррекции содержит (фиг.2) первый 26 и второй 27 блоки коррекции ошибок, каждый из которых

состоит из п сумматоров по модулю два, и блок 28 мажоритарных элементов, состоящий из п трехвходовых мажоритарных элементов, реализующих функцию ( 2),

причем информационные входы 14 каждого ЛБК9| подключены к входам первой группы блоков 26, 27 и 28, контрольные входы 21 и 22 каждого ЛБК 9| - к входам второй группы блоков 26 и 27, а информационные выходы

25 - к выходам блока 28, кроме того, в каждом ЛБК 9| выходы блоков 26 и 27 подключены к входам второй и третьей групп блока 28.

На фиг 1-4 Со, С, S-информационные

разряды трехмерного кода, поступающие в режиме Запись на информационные входы 14i-14N устройства;

а и b - контрольные разряды по нечетности для m строк и п столбцов каждой подматрицы HkJ двумерного кода (где К 1-т), формируемые в режиме Запись на информационных выходах 151-15N усгройсвта;

а Р 1 У разряды синдрома, формируемые в режиме Чтение соответственно на

выходах 21, 22 и 23 генераторов 1, 3, 6 кода ошибок.

На фиг. 3 стрелками (-), (i/), (ч) указаны группы разрядов, входящих в соответствующие строку, столбец и ребро кодовой матрицы трехмерного кода; на фиг. 4 1 d(i, j) - md(f, j) - одноименные |-е разряды одноименных i-x блоков памяти в каждой контролируемой группе блоков памяти.

Схема обнаружения некорректируемых

(НКО) и корректируемых (КО) ошибок устройства имеет пять каскадов и состоит из последовательно соединенных:

-первого 1 и второго 2 генераторов кода ошибок (первый каскад), формирующих соответственно на выходах 21 и 22 т (т + п)- разрядный код синдрома,

-индикаторов неисправностей 10i-10m (второй каскад), формирующих на контрольных выходах 16 и 17 устройства

2т-разрядный код ошибки (HKOi-HKOm. КСм-КОт), и блоков 9i-9w коррекции, независимо формирующих на выходах 25 исправленные значения разрядов соответственно для m контролируемых

групп блоков памяти,

-третьего 6 генератора кода ошибок (третий каскад), формирующего на выходах 23 (т- поразрядный код синдрома (1y1-1ynmyl-myn),

- элементов ИЛИ 12 (четвертый каскад), формирующих на контрольных выходах 18 устройства m-разрядный код ошибки, и блока 13 обнаружения ошибок (пятый каскад), анализирующего Зт-разрядный код ошибок

на контрольных выходах 16, 17 и 18 устройства и формирующего на выходах 19i-1-9 4 устройства четырехразрядный код - признак корректируемой (например, три пакетные ошибки в блоках памяти)ошибки устройства или некорректируемой (напримёр, четыре и (более пакетные ошибки в блоках памяти) ошибки устройства (ИКО. КО. Hn4m, НпЗп).

При отсутствии неисправностей в самой схеме обнаружения ошибок в каждом цикле работы устройства (как в режиме записи, так и в режиме чтения очередного (N -п)-разряд- ного кодового слова, поступившего на вхо- дьГ 14 устройства) на выходах 19г-194 устройства может появиться только одна из пяти разрешенных комбинаций, каждая из которых является кодом признака соответствующей ошибки устройства:. ,

1) 0000 - признак отсутствия ошибок в режиме Запись или Чтение ;

2) 010Г - признак корректируемой ошибки в режиме Запись ;, {. 3} 1001 - признак некорректируемой ошибки в режиме Запись ;,.

4) - признак корректируемой ошибки в режиме Чтение ;

5) - признак корректируемой ошибки в режиме Чтение.

Любая другая комбинация (кроме пяти перечисленных) является для устройства запрещенной и свидетельствует о неисправности в самой схеме контроля.

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

Устройство (фиг. 1) для обнаружения и исправления п-разрядных ошибок в m блоках памяти (где п и m - четные числа) реализует трехмерный модифицированный итеративный код. составленный из m двумерных итеративных кодов, структура и схемная реализация которых описана в 2.

Кодовая матрица трехмерного коДа (фиг. 3) состоит из m (m -поразрядных плоскостей (подматриц Hi-Hm двумерного кода) и имеет при этом три проверочные плоскости:

-плоскость А - составленную из m п контрольных разрядов по нечетности строк (ai),

-плоскость В - составленную из (т -п) контрольных разрядов по нечетнбсти столбцов (kbj);

- плоскость С - (подматрица Нт), составленную из (т -п)контрольных разрядов (Icj) для ребер кодовой матрицы трехмерного кода.

Каждый размер трехмерного кода имеет координаты (f, J, k), т.е. является J-м разрядом 1-й строки К-й подматрицы (Hk) и записывается в 1-й блок памяти устройства (где I (К-1)т + I), т.е. в 1-й блок памяти к-й контролируемой группы блоков памяти (где I, К - 1 - т).

Например, информационный разряд 2S6 трехмерного кода (64, 32). имеющий в кодовой матрице (фиг. 3) координаты (3, 2, 1), является соответственно первым 0 1) разрядом третьей (I 3) строки второй () подматрицы Н2 двумерного кода (16,8) и записывается в седьмой (I 7) блок памяти, т.е. 2S6 d(3,2.1).

Контрольные разряды a, kbj, icj. расположенные в трех проверочных плоскостях А, В, С трехмерного кода, имеют соответственно координаты 0,n,K), (mfj,K) и (i,j,m).

Например, контрольные разряды ау, 2Ы и Зс1, имеющие собственно координаты (3,4,2), (4.1.2) и (3.1,4), являются:

-четвертым разрядом третьей строки подматрицы Н2, т.е. ау с(3,4,2);

-первым разрядом четвертой строки подматрицы На, т.е. 2bt d(4,1,2);

-первым разрядом третьей строки подматрицы (Н4). т.е. 3d d(3,1,4).

При этом контрольные разряды ау. 2Ы и Set записываются соответственно в седьмой (I 7), восьмой (I 8) и 15-й (I 15) блоки памяти.

1 Первое (проверочное) ребро трехмерного кода (64,32) составлено из четырех контрольных разрядов; 1СОГ2СО, ЗСО и 1С1) по нечетности соответственно для четырех восьмиразрядных сообщений:

(1S1 - 1S8,2S1 -2S8,3S1 - 3S8 и 1С2 - ЗСЗ), поступающих на входы 14 устройства для кодирования и записи в четыре контролируемые группы блоков памяти.

При этом контрольные разряды 1СО, 2СО, ЗСО, 1С1 записываются соответственно в первый, пятый, девятый и тринадцатый блоки памяти.

Шестнадцатое (проверочное) ребро трехмерного кода (64,32), лежащее на пересечении проверочных Ьлрекостей А и В, составлено из четырёх конт рольных разрядив:

(а4 1Ь4, а8 2Ь4, а12 ЗЬ4 и а16 4Ь4) по четности соответственно для четырех сформированных 15-рэзрядных сообщений двумерного кода (16,8).

При этом контрольные разряды а4, а8, 5 а12 и а16 записываются соответственно в четвертый, весьмой, двенадцатый и шестнадцатый блоки памяти.

Каждый контрольный разряд ai (i,n,k) трехмерного кода является однобременно 10 контрольным разрядом kai в соответствующей подматрице Hkj двумерного кода.

Например (фиг. 3) контрольный разряд э7 является одновременно контрольным разрядом (2аЗ) подматрицы Н2.15

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

В обоих режимах работы (Запись или Чтение) используются все блоки устройства.20

Кодирование информации в режиме записи ее в N блоков памяти заключается в формирований контрольных разрядов at и kbj(l 1-N,, , m УКбдвух проверочных плоскостей А и В кодовой мат- 25 рицы трехмерного кода (фиг. 3) и происходит а два этапа:

в режмме запись на управляющий вход 20 устройства поступает логическая единица1 , а на информационные входы 14i - 14м 30 устройства со входной магистрали данных одновременно поступают N п-разрядных сообщений (где N т2).

На первом этапе цикла Запись каждая К-я подгруппа входов 14 устройства: 14i - 35

14m 14(N - m + 1) 14м, состоящая из m

смежных n-разрядных сообщений (инфор- мационные разряды подматрицы Hk), независимо обрабатываются соответствующей К-ой подгруппой блоков 2 свертки по моду- 40 лю два: 2т-2т,...,2(м - т + 1) - 2w первого генератора 1 кода ошибок, подгруппой 4k блоков 5 сверттки по модулю два второго генератора 3 кода ошибок, индикатором неисправностей 10k и К-й подгруппой ЛБК 9i 45 где (k-1)m i km.

При этом в каждом блоке 2i формируются контрольные разряды по нечетности строк а1 - aN, которые без изменения проходят через блоки 9i-9fj, и по их выходам 25 50 поступают на первый (младший) адресный вход соответствующих (n-х) коммутаторов блоков 111-11м (для дальнейшей обработ- . ки), а на выходах 22 блоков 5 каждой 4i-4m группы формируются группы контрольных 55 разрядов по нечетности столбцов: 1Ь1 - 1bn,..., mbl - mbn соответственно для m двумерных итеративных кодов, которые без изменения проходят через блоки 9(т),

9(2т)...., 9(М) И ПО ИХ ВЫХОДам 25(т), 25(2™),

25(м) поступают на первую группу адресных

входов блоков 11(т), 11(2т)11м(такжедля

дальнейшей обработки).

Одновременно гл групп контрольных разрядов, сформированных на выходах 21 и 22 первого 1 и второго 3 генераторов кода ошибок, поступают (для анализа) на первую а и вторую /3 группы входов индикаторов неисправностей 101-10™, а одноименные (i,J)-e контрольные разряды каждой подматрицы Hk, расположенные соответственно на одном ребре кодовой матрицы трехмерного кода (фиг. 3): 1bj, 2bj,..., mbj и ai, a(i+m)a(N-m+i). сформированные на выходах 25 логических блоков коррекции 9г-9м. по ступа ют (для исправления) на входы соответствующих блоков свертки 8 третьего б генератора кода ошибок.

Работа индикаторов неисправностей 10i-10m в режиме Запись начинается при поступлении на управляющий (т + т н 1)-й вход каждого из них логической единицы (высокого уровня напряжения) и запрограммирован по, формуле: 3п (Ка1 «-...-4 Кат) (КЫ ь ...+ КЬп).

При отсутствии ошибок b(N - m)- (n -1) - разрядной информации, поступающей в очередном цикле записи на информационные входы 14 устройства, каждое (т - 1)(п - 1) - разрядное сообщение (информационные разряды подматрицы Нк) должно содержать нечетное количество единиц, Поэтому (при отсутствии неисправностей в самих генераторах 1 и 3 кода ошибок) контрольные разряды по нечетности строк ( - Кат) и столбцов (КЫ - КЬп), сформированные в соответствующей (К-й) подгруппе блоков 2 и 5 и поступающие на первые (а) и вторые $} входы соответствующего индикатора неисправностей 10k, также должны содержать нечетное количество единиц. В данном случае на выходах 16 и 17 блока 10k формируется код 00 - признак отсутствия ошибок в контрольных разрядах (Kai) и (Kbj) подматрицы Hk, сформированных на выходах 25 соответствующей (К-й) подгруппы блоков 9.

Если же на первые а или вторые /3 входы любого блока 10k в режиме Запись поступает четная комбинация, (т.е. содержащее четное количество единиц), то на выходах 16 и 17 соответствующего блока 10k формируется код 1Г - признак ошибки записи, т.е. признак ошибки в контрольных разрядах (Kai) или (Kbj), сформированных на выходах 25 соответствующей (К-й) подгруппы блоков 9.

Например, если в режиме Запись на вход 14 поступит искаженный символ 2S6

(3,1,2), то на вход блока 102 поступят две четные комбинации, а на выходе 16 блока 102 появится код 11, в блоке 9 неправильно сформируется контрольный разряд а, а в блоке 9в неправильно сформируется конт- рольный разряд 2Ы.

Заканчивается первый этап цикла Запись :

-формированием на выходе 16 каждого индикатора неисправностей 101 управляю- щего сигнала (признака ошибки в сформированной подматрице Hk), который поступает на второй (старший) адресный вход соответствующих блоков коммутаторов 11). где (K-1)m I

-формированием на прямых 23 и инверсных 24 выходах третьего 6 генератора кода ошибок исправленных контрольных разрядов соответствующей подматриСЩ Нк: (аГ + I уп) и (kbj/+ m yj), поступающие на третьи (D2) и четвертые (D3) информйцион- ные входы соответствующих блоков коммутаторов 11|, и (по выходам 23) на эле ёнтьт ИЛИ 12;

-формированием на первых и Bforp btx контрольных выходах 16 и 17 устройства 2т - разрядного кода ошибки Заимей : НКСН - НКОт, K0i - КОт.

На втором этапе цикла Запись в устройстве работают блоки 11,12т и 13. Блоки коммутаторов 11f в зависимости от значений управляющих сигналов: (00. 01 или 10. 11) , поступивших на адресный вход соответствующего коммутатора блока 11|, пропускают на выход 15| устройства для записи в память: или знамения (Do, D1) контрольных разрядов (ai и kbj ) соответствующей подматрицы Hk, сформированные на выходах 25 блоков 91 (поступившие на младший (первый) разряд адреса, или значения (D2, D3) исправленных контрольных разрядов (а |Х + у п) и (kb/+ m yj) соответствующей подматрицы Hk, сформированные соответственно на выходах 23 или 24 генератора 6 кода ошибок.

Формирование на выходах 15 устройства третьей группы окончательно скорректированных значений контрольных разрядов а|(вых) и kbj(Bbix) происходит в соответству- ющих коммутаторах каждого блока 11 по формуле:

а|(вых) - сГ (.n,k) - HKOkAd 0,n,k)V V HKOkAd (i,n,k);

kbj(Bbix) - d11 (m,j,k) HKOkAd1 (m,j,k)V v HKOkAd(niJ.k).

где d (,n,k) и d (m.j.k) - первая группа значений контрольных разрядов (ai) и (kbj)

трехмерного кода, сформированная на выходах 25 блоков 9i-9N,

d (i,n,k) и d (m,j,k) - вторая (скорректированная) группа контрольных разрядов (а|) и (kbj) трехмерного кода, сформированная на выходах 23 и 24 генератора б кода ошибок, причем

d(l,n.k) d (l,n,k) + (iyn)

d {l,n.k)A (i у n)V d1 (I, n, k)A (I у n) ;

С (m,J.k) Id1 (m J.k) + )m у j)J - . d (m,j,kM(m yj) v d (m J,k)A (m, yj).

Последние две формулы поясняют алгоритм работы коммутатора, в случае, когда он реализует функцию сложение по модулю d d +y {сГ л уУЙ Л у), т.е. в случае формирования на выходе 15 устройства исправленного контрольного разряда: а(вых) d (i,n.k) или kbj(ebix) d (m,j,k), причем в режиме Чтение в каждом коммутаторе блоков 11 таким же образом реализуется (на втором этапе декодирования) исправление любого искаженного символа d ( J.k) трехмерно го кода, сформированного на выходах 25 ЛБК 91-9м.

Алгоритм работы коммутатора (как в режиме Запись, так и в режиме Чтение) в случае, когда он реализует функцию сложение по модулю (d d + j), заключается в следующем:

если разряд d (I, j, k), сформированный на соответствующем 0-м) выходе 25 блока 9|, искажен, то на выходе 16 соответствующего блока 10k присутствует логическая единица (HKOk 1), на соответствующем (|-м) выходе 23) блока 6 присутствует логическая единица) (ly j 1), а на соответствующем (-м) выходе 24i блока б присутствует логический нуль(у} 0).

В данном случае на адресный вход соответствующего 0-го) коммутатора поступает комбинация 10 (если искаженный символ d 0)или комбинация 11 (если искаженный символ d 1).

В первом случае (d 0) на выход 15 устройства пропускается логическая единица, т.к. на информационный вход (D2) данного коммутатора поступает значение разряда синдрома ( у J 1) - с выхода 231 блока 6.

Во втором случае (d1 1) на выход 15 устройства пропускается логический нуль, т.к. на информационный вход (D3) данного коммутатора поступает инверсное значение разряда синдрома (ly J 0) - с выхода 24| блока 6.

Таким образом в каждом коммутаторе блоков 11 исправление (на втором этапе) любого искаженного символа d (I, j, k),

сформированного на выходе 25 блоков 9 происходит по {юрмуле:

d(Bbix) (HKOk-d) HKOk-(d + iy j)

Алгоритм работы коммутатора (как в режиме Запись, так и в режиме Чтение) в случае, когда он реализует функцию: d(ebix) HKOk (о , заключается в следующем: если разряд d (i, j, k), сформированный на соответствующем (j-м) выходе 25 блока 9i, не искажен, то на выходе 16 соответствующего блока 10k присутствует логический нуль ЧНКО О).

В данном случае на адресный вход соответствующего Q-ro) коммутатора блока 11| поступает комбинация 00 (если неискаженный символ d 0) или комбинация 01 (если неискаженный символ d 1).

В первом случае (d1 0) на выход 15 пропускается логический нуль, т.к. на информационный вход (DO) данного коммутатора поступает значение младшего разряда адреса (d1 0) с выхода 25 блока 9.

Во втором случае (d1 1) на выход 15 устройства пропускается логическая единица, т.к. на информационный вход (D1) данного коммутатора (также как и в первом случае) поступает значение младшего разряда адреса (d1 1) с выхода 25 блока 9i.

В общем случае (на втором этапе кодирования или декодирования), работа каждого (j-ro) коммутатора блока 11| (фиг. 4) запрограммирована по формуле

d (IJ.k) HKOk л d (l,J,k) v/ HKOk A

(U,k) + lyJ, где: ly j d (iJ,1)+...+ d OJ,m).

Работа блока 13 в режиме Запись запрограммирована по формулам:

НпЗп (HKOr KHgfcvQHKOm- K0m); КО - (HKOk KOk-HnmKyKHKOiv KO|)A л (HKOk-1 -JCOk-iX (HKOk+1 КО k+i)A...A (HKOm v KOm);

НКО КТГ -(Hn3n v/ Hnm), Где:

Hnm my 1 v ... v my n.

При этом исправление искаженного символа d (i,j,k), сформированного (на первом этапе кодирования или декодирования) на выходе 25 блока 9i, реализуется в коммутаторах блока 11| методом адаптации 1

-отключением от выходов 15i устройства выходов 25 (d ) блока 9|, и подключением к выходам 15i устройства выходов 23i или 24i (d) блока 6.

Рабо.ту устройства в режиме Запись удобно рассмотреть для одного конкретного случая его применения, например, при реализации в нем (64, 32) модифицированного трехмерного кода (фиг. 3) с параметрами: n 4, m 4, N 16.

В данном случае на девятый (управляющий вход каждого блока 10i-104CO входа 20 5 устройства поступают логическая единица, настраивающая индикаторы неисправностей на работу в режиме Запись.

Одновременно на входы 14i-14ie устройства поступают для кодирования 16 че- 0 тырехразрядных сообщений, например: (1)011Q(2) 0110(3) QQQPJ4) (5) 0110Д6) 0110(7) 0000. (8) (9) 0110(10) 01 ТО (11) 0000(12) 1000(13) 0110(14) 0110(15)0000(16) 5 где в скобках указан номер (I) строки трехмерного кода (64,32), стрелками (-) указаны разряды подматрицы Hi двумерного кода, а нулевые значения контрольных разрядов (al и kbj), подлежащих кодированию - под- 0 черкнуты.

Таким образом на входы 14 устройства поступают 36 информационных и 28 контрольных (нулевых) разрядов, причем значения разрядов (iCj) входного Кода, 5 поступающих на входы 14(13) - 14(15) устройства, при отсутствии ошибок удовлетворяют соотношениям:

1С1 1СО + 2СО + ЗСО,

2С1 131 +2S1 +3S1, 0

3C3 1S8 + 2S8 + 3S8.

В блоках 2 и 5 первого 1 и второго 3 генераторов кода ошибок происходит формирование на выходах 21 и 22 контрольных 5 разрядов строк (ai) и столбцов (kbj) соответственно для четырех двумерных итеративных кодов, как описано в 2.

Например, контрольный разряда формируется на инверсном выходе 21 блока 27 0 по формуле:

2аЗ 2S6 + 2S7 + 2S8 + Г 0 + 1 + 1 +

+1 1,

а контрольный разряд 2Ы формируется на

инверсном выходе 11г блока 5i по формуле:

5 2Ы 2СО + 253 + 256 + Г 1 +0 + 0 + 1 0.

На входы а и /3 каждого блока 10-1-104 поступает комбинация (0111 0111), свидетельствуюа ая об отсутствии ошибок в

0 каждом девятиразрядном информационном сообщении: (100 011 011), поступившем на соответствующую подгруппу входов: 141-14з, 145-14. 14д-14ц и устройства, поэтому на выходах 16 и 17устрой5 ства формируется восемь логических нулей: HKOi, HK02, НКОз, НК04 и K0i, K02, КОз.

К04.

Одновременно 28 контрольных разрядов, сформированных на выходах 21 и 22

блоков 1 и 3, без изменения проходят (фиг. 2) на выходы 25 блоков , т.к. на входы соответствующих мажоритарных элементов 28 блоков 9, формирующих контрольные разряды а , или kbj , поступает или комбинация (0, ai. 1) или комбинация (0, 1, kbj), поэтому на адресные входы 16 и 25 соответствующих коммутаторов блоков 11, формирующих контрольные разряды а|(вых) и kbj(ebix) для записи в память (фиг. 4), поступает или комбинация (0, ai) или (0, kbj). a на выходах 234 третьего 6 генератора кода ошибок формируются четыре логических нуля по формулам:

4у1 1Ы+ 2Ы + ЗЬГ + Ч Ы 0 4 у 2 1Ь2 + 2Ь2 + ЗЬ2 + 4Ь2 О 4 у 3 1ЬЗ 4 2ЬЗ + ЗЬЗ + 4ЬЗ О 4 у 4 а4 +а8 + а12| + а16 0 На этом первый этап цикла Запись заканчивается.

На втором этапе работают блоки 111-1116, 124 и 13 (блоки 12i, 12г и 12з в режиме Запись не участвуют).

На выходе 18 блока 124 формируется логический нуль по формуле:

Нп4 4у 1 V4y 3 V4y 4 0, на выходе 19 устройства формируется код 0000 - признак отсутствия ошибок в режиме Запись, а на выходах 15 устройства, связанных с соответствующими входами 16 блоков памяти, формируются 28 контрольных разрядов трехмерного кода (64, 32), поступивших на первые (Do) и вторые (D1) информационные входы соответствующих коммутаторов блоков 11с -выходов 25 бло- ков 9.

Таким образом, четыре 16-разрядных кодовых слова подматриц Hi-H4 (фиг. 3), сформированные для записи в память на входах 14 устройства (информационные разряды) и выходах 15 устройства (контрольные разряды), содержат четное (правильное) количество единиц и будут иметь вид:

100 011 011

(Н1.Н2.НЗ.Н4)

011

1

5

0

5

0

5

0

комбинация (1000), а в остальные 12 блоков памяти - комбинация (0111).

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

В данном случае на входы 14 устройства поступают три девятиразрядные комбинз ции: 100 011 011, содержащие нечетное (правильное) количество единиц и одно четное девятиразрядное сообщение,, например, с искаженным (0 - 1) символом 2S6 (подчеркнут): 100 011 П1. Согласно подматрице Й2 (фиг. 3), на выходе 21 блока 2 и на выходе 222 блока 5i неправильно сформируются два контрольных разряда: а О (вместо 1)и 2Ы 1 (вместо О) по формуле:

+ 1 + 1 0

2Ы 1 +0+ И-Т-1

На входы блоков 10i, Юз и 104 поступает комбинация (0111 0111). свидетельствующая об отсутствии ошибок в первом, третьем девятиразрядном сообщении (100 011 011), а на входы блока 102 поступает комбинация (0101 1111), свидетельствующая об одиночной ошибке во второй подгруппе входов Ав устройства, в результате чего каждое 16-разрядное кодовое слово подматриц Hi, Нз и Н4, сформированное на первом этапе кодирования на соответствующих входах 14 устройства и выходах 25 блоков 9, будет иметь вид:

100 011

011

(Hi, Н3, Н4)

011

1

а 16-разрядное кодовое слово подматрицы Н2, сформированное нэ первом этапе кодирования на входах 14s-14e и выходах 25 блоков 9s-9a, содержит нечетное (неправильное) количество единиц и будет иметь вид (подчеркнуты три искаженных символа 2S6, ): 100 О

011 111

(Н2)

Изобретение относится к вычиелитель- ной технике и может быть использовано дли обнаружения и исправления двойных, fpynпрвых и пакетных ошибок в блоках памяти. Целью изобретения является расширение области примененияfустройства за счёт исправления трех пакетов и обнаружения N пакетов п-разрядных ошибок. Устройство для обнаружения и исправления ошибок содержит первый ген ёратбр кодов ошибок, со- стоШцйй из блоков свертки по модулю два, второй генератор кодЪв ошибок, состоящий из групп блоков свёртки по модулю два, и третий генератор кодов ошибок, состоящий из групп блоков свертки по модулю два. блоки коррекции, индикаторы неисправностей, блоки коммутаторов, элементы ИЛИ и блок обнаружения ошибок. 4 ил.

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

В конце цикла Запись в каждый из 16 блоков памяти записывается соответствующая строка сформированного трехмерного кода (64, 32), при этом в первый, пятый, девятый и 13-й блоки памяти записывается

ТТТ

1

На контрольных выходах 16i, 16з и 164 устройства формируются логические нули, поступающие на старший адресный вход коммутаторов блоков 11i-1l4, 119-1112, 1113-1116, пропуская на соответствующие выходы 15 устройства (по входам Do и D1) коммутаторов) значения контрольных разрядов подматриц Hi, Нзи Н4, сформированные на первом этапе кодирования (на выходах 25 блоков 9).

На контрольном выходе 162 устройства формируется логическая единица, поступающая на старший адресный вход сети соответствующих коммутаторов блоков 11s-11в. пропуская на выходы 15 (по входам D3 и D4 коммутаторов) исправленные (на втором этапе кодирования) значения контрольных разрядов подматрицы Н2. сформированные на выходах 23 и 24 блока б

Так как на четвертом выходе 25 блока 9у формируется искаженный (1 0) символ (а), а на первом выходе 25 блока 9з формируется искаженный (О - 1) символ (251), то на четвертом выходе 23з и первом выходе 23 блока 6 формируются две логические единицы по формулам: Зу4 аЗ + + +а11 + а151 1 +0+1 + 1 1; 4yV 15t + + 251 + 35Г + 4Ы 0 + 1 + 0 + 0 1, а на выходе 15 устройства формируются семь контрольных разрядов подматрицы Н2 с ис- правленным (0 1) символом а и исправленным (1 - 0) символом 2Ы по формулам: а5(вых) а 5 + 1 у А а5 t- 0 « а5 аб(вых) аб + 2 у 4 аб + 0 аб а7(вых) а7 + Зу 4 а + 1 -

2Ы(вых) 2Ы + 4у1 251 + 252(вых) 252 + 4у 2 2Ь2 + 0 - 2Ь2 253(вых) - 253 + 4у 3 2ЬЗ + 0 2ЬЗ а8(вых) а8 + 4у 4 а8 + 0 - а8 Исправление двух контрольных разрядов: а7 и 2Ы на втором этапе кодирования методом адаптации происходит следующим образом.

На адресные входы четвертого коммутатора блока 11 поступает комбинация два (10), поэтому на выход 15 устройства по информационному входу D2 коммутатора проходит значение: Зу , т.е. исправленное (0 - 1) значение символа ат а на адрес- н.ые входы первого коммутатора блока 11з поступает комбинация три (11), поэтому на выход f 5s устройства по информационному D3 входу коммутатора проходит значение: 4 у 1 0 с выхода 24/ блока б, т.е. исправленное (1 - 0) значение символа 25,1. в резуль- тате окончательно сформированное на входах 14s-14e и выходах 155-158 устройства 16-разрядное кодовое слово подматрицы Н2 содержит только один искаженный символ: 2S6 (на входе 14) и два исправленных методом адаптации символа: а и 2Ы (на выходах 15 и 15в). и имеет следующий вид (подчеркнут искаженный символ 2S6):

На выходе 18 блока 124 формируется логическая единица по формуле:

Нп4 4у U4y2v4 у 4 - 1, а на выходе 19 устройства формируется код 0101м - корректируемой ошибки Записи, разрещающий запись в память 64-разрядного кодового слова с одним ошибочным 2S6 и двумя исправленными а7 и 251 символами.

На этом цикл Запись заканчивается.

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

Необходимость исправления (методом адаптации) двух контрольных разрядов (ai) и (kbj) , неправильно сформированных на выходах 25 блоков 9 (на первом этапе цикла Запись), объясняется необходимостью Избавления от трехбитовой ошибки типа: 2S6, а7, 251 некорректируемой конфигурации (т е. некорректируемой в режиме Чтение). Ошибочный же информационный символ входного кода: например 2S6, методом адаптации в режиме Запись исправить нельзя (в отличие от режима Чтение).

И, наконец, рассмотрим случаи некорректируемой ошибки Записи, например, двухбитовой ошибки Записи, обнаруживаемой в режиме Запись или Чтение. При поступлении на входы 14 устройства двух ошибочных информационных символов, расположенных в разных подматрицах трехмерного кода, например символа 2S6 подматрицы На и символа 3S6 подматрицы Нз. на выходах 16 устройства сформируется две логические единицы: НК02 и НКОз. поэтому на выходе 19 устройства сформируется код 1001 - некорректируемой ошибки Записи, и работа устройства прерывается.

При поступлении на входы 14 устройства двух Ошибочных символов, расположенных в одной строке кодовой матрицы, например, символов 2S6 и 2S7 подматрицы Н2. на выходах 16 и 17 устройства сформируются логические нули, но на выходах 25 блока 9в неправильно сформируются два контрольных разряда: 251 и 252, поэтому на выходах 234 и следовательно на выходе 184 устройства сформируются логические единицы : 4у t, 4у 2 и Нгм, а на входы ЛБО 12 поступит запрещенная комбинация (несоответствующая отсутствию ошибок или корректируемой ошибке Записи):

00000000

где знак означает, что значение на выходах 18i, 182 и 18з устройства (т.е. кроме значения Нпт на выходе 184 устройства) для блока 13 в режиме Запись безразлично

Согласно логике работы блока 13, на выходе 19 устройства формируется запрещенная комбинация 1000, и работа устройства прерывается.

При поступлении на входы 14 устройства двух ошибочных символов, расположенных в разных строках одной подматрицы трехмерного кода, например, символов 2S3 и 2S6 подматрицы Н2. на выходах 16, 17 и 184 устройства сформируются логические нули, на выходах 25 блоков 9е и 9у неправильно сформируются два контрольных разряда, (аб) и (а7), которые без изменения поступят (на втором этапе кодирования) на выходы 15 устройства, а на выходе 19 устройства сформируется код 0000 - признак отсутствия ошибки, в результате чего 64- разрядное кодовое слово с четырехбитовой ошибкой в разрядах: 2S3, 2S6, аб и а7 будет записано по входам 14 и выходам 15 устройства в блоки памяти как безошибочное кодовое слово.

Такая двухбитовая ошибка Записи (типа 2S3 и 2S6) является необнаруживаемой ошибкой в режиме Запись, но при этом является обнаруживаемой ошибкой устройства, т.к. двухбитовая ошибка Записи данной конфигурации гарантированно обнаружится в режиме Чтение (см. случай четырехбитовой ошибки в описании работы Чтение).

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

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

Декодирование информации в режиме Чтение происходит в два этапа.

На первом этапе на управляющий вход 20 устройства поступает логический нуль,

.

перестраивающий индикаторы неисправно стей 10 на работу в режиме Чтение и разрешающий считывание (N- поразрядной информации из N блоков памяти на входы

.

5

10 15 20 2530

35 404550

55

14г Мы устройства. На первом этзпе декодирования трехмерного кода используются блоки 1, 3, 6, 9 и 10. В блоках свертки по модулю два 2 и 5 (соответственно первого 1 и второго 3 генераторов кода ошибок) - проверкой на нечетность каждой строки и каждого столбца кодовой матрицы (фиг. 3) - формируются (на выходах 21 и 22) первая и вторая группы разрядов синдрома: а и .

В блоках происходит исправле ние Одиночной пакетной ошибки каждого из N блоков памяти и формирование на выходах 2 первой группы скорректированных значений Д : о (i.l.K) - о (i,n,k) каждого блока памяти,

В индикаторах неисправностей 10i-10m (независимо друг от друга) происходит обнаружение некорректируемых (возникновение 2 - m пакетов п-разрядных ошибок) или корректируемых ошибок (возникновение только одного пакета ошибок) в каждой из m контролируемой группе блоков памяти, и формирование (на выходах 16 и 17) признаков некорректируемой и корректируемой K0i-K0m ошибки в соответствующей подгруппе блоков памяти

Одновременно в блоках свертки 8 по модулю два третьего 6 генератора кода ошибок - проверкой на четность и нечетность каждого ребра кодовой матрицы (фиг, 3) - формируется (на прямых 23 и инверсных 24 выходах блоков 8) третья группа разрядов синдрома: (iy j) и (i у j), которая одновременно является второй группой скорректированных значений Д : о (i,j,k) + i yj каждого блока памяти.

На этом первый этап декодирования заканчивается: в конце первого этапа цикла Чтение (фиг. 4) на первые адресные входы каждого коммутатора блока 111 поступает первая группа скорректированных значений: 1Д 1-го блока памяти (с выхода 25 блока 9i), на вторые адресные входы - признак НКОк (с выхода 16 блока 10k), а на третьи D2 и четвертые D3 информационные входы - поступает вторая группа скорректированных значений: Д 1-го блока памяти (с выходов 23i и 24| блока 6).

На втором этапе цикла Чтение используются блоки 11, 12 и 13.

В коммутаторах-корректорах блоков 111-11ы происходит исправление некорректируемой ошибки каждого из N блоков памяти (который при этом является i-м блоком памяти К-й контролируемой группы блоков памяти) и формирование (на выходах устройства)третьей группы окончательйо скорректированных значений 1Д(вых) - МД(вых) по формулам:

Щ(вых) (Н КО/ Д ) V(HКО Д), где 1Д : d1 (1,1,k)-d (l.n.k)- первая группа скорректированных значений 1-го блока па мяти, сформированная на выходах 25 блока 9i;

1Д : d1 (l,j,k) + ly j - вторая группа скорректированных значений 1-го блока памяти, сформированная на выходах 23i и 24j третьего б генератора кода ошибок:

- HKOk - признак некорректируемой ошибки К-ой контролируемой группы блоков памяти (логическая единица), сформированный на выходе 16 блока 10k.

Д(вых) : d1 (1,1,k) - (l,n,k) - третья группа скорректированных значений 1-го блока памяти, сформированная на выходах 15 блока 11i;

ОУ j) d(U,1) + ... + d (i-J.m).

В блоке 13 происходит анализ Зт - разрядного кода ошибки, сформированного на контрольных выходах 16,17 и 18 устройства, и формирование на выходах 19i-19 3 устройства четырехразрядного кода 0110 или 1010 - признаков корректируемой или некорректируемой ошибки устройства в режиме Чтение.

В конце цикла Чтение (после формирования на выходе 19 устройства признака отсутствия ошибок 0000 или 0110 - признака корректируемой ошибки устройства в режиме Чтение) скорректированная (N -поразрядная информация считывается с выходов 15 устройства на выходную магистраль данных.

На этом очередной цикл Чтение заканчивается .

На первом этапе декодирования в каждом блоке 9| реализуется синдромнб-мажо- ритарный алгоритм декодирования разрядов 1-го блока памяти. Данный алгоритм заключается в следующем: при отсутствии ошибок в n.m разрядах информации, считанной из т блоков памяти К-й контролируемой группы блоков памяти, информации проходит со входа 14 устройства: Д(вх) на выход 25 блока 9| : 1Д без изменения, так как на fn соответствующих выходах 21i первого генератора кода ошибок, где (К-1)гл km, и на п соответствующих выходах 22k второго генератора кода ошибок, формируется нулевой (т + п)- разрядный синдром, поступающий одновременно в блоки 9i и 10k, поэтому второе и третье значения: d(l,j,k) + он и d(l,j,k) + k /3jJ каждого сигнала входа 14 устройства, сформированные в блоках 26 и 27 блока 9i, совпадают на входе каждого мажоритарного элемента 28 с первыми, считанными из памяти значениями d(i,j,k) входа 14| устройства.

Таким образом, при отсутствии ошибок в К-й контролируемой группе блоков памяти на входы каждого мажоритарного элемента блока 9| поступают три одинаковых значения: 000 или 111, поэтому значения d (i,j,k) каждого разряда на выходе 25 блоки 9 совпадают со значениями d(i,j,k) разрядов входа 14 устройства:

Д Щ(вх) HKOk KOk

Одновременно на выходах 16 и 17 каждого блока формируется два логических нуля: HKOk и , т.е. формируется код 00 - признак отсутствия ошибок в К-й контролируемой группе блоков памяти, поэтому значения d (i,j,k) каждого разряда на выходе 15 блока 11| совпадают со значениями разрядов d (i,j,k) на выходе 25 блока 9|. т.е. со значениями разрядов d(i,j,k)Ha входе 141 устройства: 1Д(вых) 1Д(вх) HKOk КО.

Если в каждой из m контролируемой группе блоков памяти независимо возникают одиночные ошибки или одиночные пакеты Ошибок типа п нулей, или п единиц (возникновение 1-т пакетов ошибок одновременно в разных контролируемых группах блоков памяти является для устройства корректируемой ошибкой), то на m соответствующих выходах 21| первого генератора кода ошибок появляется унитарный код, содержащий одну единицу (а) и (т-1) нулей, а на п соответствующих выходах 22k второго 5 генератора кода ошибок появляется код, содержащий нечетное количество единиц (k/ j) и нечетное количество нулей. В результате на К-й группе выходов 21| и К-й группе выходов 22k первого и второго генераторов кода ошибок, где 1 - (k - 1)m + i, формируется (m + поразрядный синдром, содержащий четное количество единиц (а, k / j) и четное количество нулей, (расположенных на определенных позициях), посту- 5 пающий одновременно в блок 9i и 10k, поэтому второе и третье значения: {d)i,j,k) + + а и d(i,j,k) + k/ j каждого искаженного символа входа 14| устройства, сформированные в блоках 26 и 27 блока 9и будут 0 равны его инверсному значению: d(i,j,k).

Таким образом, при возникновении одиночной (корректируемой) пакетной ошибки в К-й контролируемой группе блоков памяти, на входы соответствующих ма- 5 жоритарных элементов 28i-28n блока 9i поступает комбинация 011 или 100, т.е. одно искаженное (0 или 1) и два исправленных (11 или 00) значения символа d(i,J,k) входа 14| устройства, формируя на соответствующих

0

5

0

5

0

0

выходах 25 блока 9i инверсные (т.е. исправленные) значения искаженных разрядов 1-го блока памяти.

Синдромно-мажоритарный алгоритм декодирования в каждой ЛБК 9i-9r i реализуется методом голосования в мажоритар- 5 ных элементах по формулам:

d1 (I.J,k) - d(i.j.k) d(i,J,k) + GJ K d(I.J.k)/l d(l.j,k) + Vft j v d(l,J,k) + (A Md(l.j.k) + k/Sj.

Например, при искажении первого разряда информация третьего блока памяти 10 второй контролируемой группы блоков памяти (т.е. символа 2S6 седьмого блока Памяти), мажоритарный элемент 28i блока 9 реализует функцию (фиг. 4):

(2S6) 2S6 Л (256+ О) s/ 2S6 А 15 A(2S6 + )v(2S6 + 07 W2S6+ ).

При возникновении одиночной (корректируемой) пакетной ошибки в l-м блоке памяти (т.е. в i-м блоке памяти К-й контролируемой группы блоков памяти), на 20 выходах 16 и 17 блока 101с появляется код 01 (признак корректируемой ошибки К-й контролируемой группы блоков памяти) по формулам:.-

KOk (Зп) -(Кар- Ка1 ... Ka(i-t) 25 v Ka(j-i-i)f ...vKam д A(K/81+K/ 2j:...);

HKOk (3n) f KOk) (Ka 1 . . v KamvK/ 1v/...),

Эта формула означает, что код 01 (корректируемой ошибки) формируется на выходах 16 и 17 блока 10k при поступлении на его первые m входов только одного единичного символла о и поступлении на его вторые п входов нечетного количества единичных симводов ф , а код 10 (признак некорректируемой ошибки К-й контролируемой группы блоков памяти) - формируется при появлении двух и более . единиц в разрядах синдрома (Ka1-Kam ), или четного количества единиц в разрядах синдрома ( -К/Зп ), или при появлении любой другой запрещенной комбинации на входах блока 10k.

В режиме Чтение код ошибки К-й контролируемой группы блоков памяти: 01 или 10 формируется в парафазном виде, а в режиме Запись код ошибки имеет вид 11, т.е. в режиме Запись .

Это различие учитывается блоком обнаружения ошибок 13, который, анализируя Зт - рэзрядный код ошибок на контрольных выходах 16, 17 и 18 устройства, формирует четырехразрядный код на выходе 19 (признаков ошибки устройства) в режиме Запись или Чтение по разным формулам.

30

35

45

50

55

0

5

0

5

0

5

5

0

5

В элементах ИЛИ 12i-12m происходит формирование (на контрольных выходах 18 устройства) признаков неисправностей Нщ для каждой 1-й группы выходов 25 блоков 9 - по формулам:

Нщ 1у 1 v |у 2v ... vl у п, где I у J - соответствующие значения разрядов синдрома, сформированные на выходах 23 блока 6).

Работа ЛБО 13 в режиме Чтение за- прогоаммиоована по Формулам:

Hn4m (НК01 + Ш)/у(НКОт - КОт):

KO (KOiV..,nJ (. -v/

НКОт vHniv./.THn m) V (HKOk K0k)x x HKOiv/ ... VHKO(k-i)V HKO(k+i) V... v HKOml;

HKO - ( Hni)

Из этих формул видно, что в режиме Чтение на выходах 19 устройства могут появиться только две разрешенные комбинации: 0110 (признак корректируемой ошибки устройства) или 1010 (некорректируемой ошибки устройства). Появление любой другой ненулевой комбинации расценивается как запрещенная, т.е. свидетельствует о неисправности в самой схеме контроля.

Таким образом, корректируемой ошибкой в устройстве в режиме Чтение является: возникновение одиночных пакетных ошибок (KOk) в каждой подгруппе из m блоков памяти, которые независимо исправляются в блоках . или возникновение некорректируемой ошибки (HKOk) в одной из m подгрупп блоков памяти (например, возникновение нескольких пакетных ошибок или групповых ошибок четного веса), которая исправляется в соответствующих блоках коммутаторов 1ti методом адаптации : отключением от выхода 15i устройства выходов 25 блока 9| и подключением к выходу 15i устройства выходов 23i и 24t блока 6.

В первом случае возникновения корректируемой ошибки КО на входах 14 устройства (возникновение одиночных пакетных ошибок КОк в разных подгруппах блоков памяти), на контрольных выходах 16 и 18 устройства сохраняются логические нули, а на контрольных выходах 17 - появляется 1,2m логических единиц.

Во втором случае (возникновение нескольких 1,2,..,,т пакетных ошибок, или гпупповых ошибок четного веса в одной подгруппе блоков памяти и возникновение только одиночных пакетных ошибок в других подгруппах блоков памяти), на контрольных выходах 16 устройства появляется унитарный m-разрядный код некорректируемой ошибки К-й подгруппы блоков памяти:

(k-i) V

v HKO(... VHKOm. на соответствующем (KOk) выходе 17 устройства появляется логический нуль, а состояние остальных контрольных выходов 17 и 18 - безразлично.

Если же на входах 14 устройство появляются некорректируемые ошибки в двух и более подгруппах блоках памяти(например, при возникновении четырех пакетных ошибок при отказах двух блоков памяти одной подгруппы блоков памяти и двух блоков памяти другой подгруппы блоков памяти и т.п.), на контрольных выходах 16 устройства появляются две и более логические единицы, а на выходах 19 устройства формируется код 1010 некорректируемой ошибки устройства, и работа устройства прерывается. Работа устройства также прерывается в случае возникновения неисправностей в самих блоках устройства. Например, при возникновении неисправностей в генераторе 6 кода ошибок или блоках 9 и отсутствии ошибок на входах 14 устройства (в блоках памяти) на контрольных выходах 16 и 17 устройства сохраняются логические нули, а на выходах 18 появляются логические единицы. В данном случае, согласно формулам работы блока 13, на выходах 19 устройства формируется запрещенный код 1000, и работа устройства также прерывается.

Рассмотрим работу устройства в режиме Ч геиие в случае полного отказа трех из N блоков памяти при реализации в устройстве трехмерного кода (64,32) с параметрами: n m 4, кодовая матрица которого „представлена на фиг. 3.

В работе устройства при отказах любых трех из 16 блоков памяти могут возникнуть пакетные ошибки различной конфигурации:

а) три пакетные ошибки возникли в разных подгруппах блоков памяти, например: в 3-м, 7-м и 11-м блоках памяти соответственно первой, второй и третьей подгруппы;

б)три пакетные ошибки возникли в двух подгруппах блока памяти, например: в 3-м, 6-м и 7-м блоках памяти соответственно первой и второй подгруппы;

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

При полном отказе любого 1-го блока памяти на соответствующем входе 14| устройства возникает пакет однонаправпен- ных ошибок типа 4 нуля или 4 единицы. (0000 или 1111)

:

Согласно модифицированной структуре примененных в устройстве двумерных кодов (16,8) с контролем по нечетности строк и с контрольным разрядом по нечетности Со, при появлении на входе 14| устройства пакета ошибок типа 4 нуля,или 4 единицы . соответствующая (1-я) строка кодовой матрицы (фиг, 3) будет -содержать четное (запрещенное) количество единиц, При этом на выходе 21| блока 1 формируется логическая единица, а на выходе 22k блока 3 - формируется нечетное количество единиц, на выходах 16, 17 блока 101с формируется код 01. Одиночная пакетная ошибка 1-го блока памяти исправляется в блоке 9|. и исправ- ленные разряды 1-го блока памяти поступают с выхода 25 блока 9i на выход 15| устройства. На выходе 19 блока 13 формируется код 0110 корректируемой ошибки устройства и исправленное 64-разрядное кодовое слово поступает с выходов 15 устройства на выходную магистраль данных.

Пусть в каждой из четырех подгрупп блоков памяти записаны одинаковые 16- разрядные кодовые слова подматриц Hi-H4:

О О О

J

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

При этом в информационные (1-3, 5-7, 9-11 и 13-15) блоки памяти записана комби- „с нация: 1110, а в контрольные (4,8,12 и 16) блоки памяти - соответственно комбинация: 0001.

При полном отказе типа 4 нуля в третьем, седьмом и одиннадцатом блоках ,„ памяти (примера), на входы 14(з), 14()и 14(ц) устройства и на первые входы блоков 9з, 9 и 9ц поступает комбинация 0000 вместо 1110, т.е. на входы 14 устройства поступает 64-разрядная комбинация с девятью искаженными (1- 0) символами: 1S6.1S7.1S8,

2S6, 257,258,,

356,357,358,

На входы блоков 10i, 10 и Юз поступает комбинация 0010 1110, а на входы блока 104 поступают логические нули, На выходах 16 и 18 устройства сохраняются логические нули, на выходах 17 устройства формируется код 1110, а на выходе 19 устройства формируется код корректируемой ошибки устройства: 0110.

Так как в данном примере (а) три пакетные ошибки возникли в разных (первой, втою

15

20

25

30

45

50

,

рой и третьей) подгруппах блоков памяти, то эти пакетные ошибки независимо исправляются в блоках 9:

разряды 1S6, 157 и 158 - исправляются в блоке 9з, разряды 2S6, 2S7, 258 - в блоке 9(7). а разряды 356, 3S7 и 3S8 - в блоке 9(ц). согласно синдромно-мажоритарному алгоритму декодирования, описанному в 2.

На выходах 25 блоков 9з. 9 и 9ц формируются исправленные значения разрядов соответственно 3-го, 7-го и 11-го блоков памяти: комбинация 1110, и на адресные входы четырех коммутаторов (фиг. 4) блоков 11(3). 11(7) и 11(ц) поступают соответственно комбинации: 01, 01, 01 и 00, поэтому на выходы 15(з). 15(7) и 15(11) устройства лропу- скаются комбинации 1110 с выходов 25 соответственно блоков 9з. 9 и 9ц. В конце цикла Чтение 64-разрядное кодовое слово с девятью исправленными (0 1) разрядами (т.е. с тремя исправленными пакетами ошибок) поступает с выходов 15 устройства на выходную магистраль данных.

При полном отказе типа 4 нуля в третьем, шестом и седьмом блоках памяти (пример б), на входы 14(з), 14(6) и 14(7) устрой- ства и на первые входы блоков 9з, 9е и 9 поступает комбинация 0000 вместо 1110.

На третью 14(д) - 14(12) и четвертую 14(13) - 14(16) подгруппы входов устройства поступают правильные 16-разрядные комбинации подматриц Нз и H-i двумерного кода (16,8):

111{0

1110

111 ,0

ооо ;i

На первую 14i-14 i подгруппу входов устройства поступает неправильная 16- разрядная комбинация с одной пакетной ошибкой типа 4 нуля в третьей строке подматрицы Н1 (искаженные символы 1S6, 157 и 158 - подчеркнуты, а искаженная строка «з отмечена стрелкой):

11110

111 О

000 0

А на вторую 14s-14s подгруппу входов поступает неправильная 16-разрядная комбинация с двумя пакетными ошибками во второй и третьей строке подматрицы Н2 (искаженные символы 2S3, 2S4, 2S5 и 2S6,

10

15

20

50

-

30

35

45

2S7,2S8 - подчеркнуты, а искаженные строки а& и ф - отмечены стрелкой):

111 О

000 0

000 0

000 1

Таким образом на входы 14 устройства (пример д) поступает 64-разрядная комбинация с девятью искаженными () символами: 156,1S7,158,253,254,255 и 2S6.2S7, 258.

На входы блоков Юз и 104 поступают логические нули, наъх оды блока 101 поступает комбинация 0010 1110, а на входы блока 102 - комбинация 0110 0000.

На выходах 16 устройства формируется код 01100 (НКОа), на выходах 17 устройства формируется код 1000 (KOi).

Пакетная ошибка третьего блока памяти (искаженные символы 256, 157 и 158) исправляются в блоке 9з согласно синдромно- мажоритарному алгоритму декодирования, описанному в 2. На выходах 25 блока 9з формируется правильная комбинация 1110 (с исправленными 0- 1 значениями 156, 157 и 158 третьего блока памяти), а на адресные входы четырех коммутаторов блока Из поступают соответственно комбинации: 01, 01, 01 и 00. Поэтому на выход 15з устройства пропускается правильная комбинация: 1110 с выхода 25 блока 9з (те. младшие разряды адреса четырех коммутаторов).

Пакетные же ошибки шестого и седьмого блоков памяти не могут быть исправлены в блоках 9е и 97, т.к. на информационные 14 и контрольные 22 входы (фиг. 2) блоков 9е и 97, а следовательно, на первый и третий вход каждого МЭ 28 в этих блоках, поступают логические нули. Поэтому на выходах блоков 9б и 9 формируются неправильные комбинации: 0000, а на выходах 232 и 23з блока 6 формируется комбинация: 1110 по формулам:

1+0+1 И 1.

На адресные входы четырех коммутаторов блока 11е и блока 11 поступает комбинация 10, поэтому на выходы 15е и 15 устройства пропускается правильная комбинация: 1110 соответственно с выходов 232 и 23з блока 6 (т.е. третьи D2 информационные входы коммутаторов блока 11е и блока 11). На выходах 18 устройства формируется код 0110 по формулам: Нп2 - Нпз 1 1 1 0 1, На входы блока 13 поступает 12-разрядная комбинация: 0100 1000 0110,

а на выходах 19 устройства формируется код 0110.

В конце цикла Чтение (пример 6) 64- разрядное кодовое слово с девятью исправленными (0- 1) разрядами:

1S6, 1S7, 1S8, 2S3, 2S4.2S5, 2S6, 2S7 и 2S8 трех блоков памяти (3-го, 6-го и 7-го) поступает с выхода 15 устройства на выходную магистраль данных.

При полном отказе трех блоков памяти в одной подгруппе (пример в):

типа 4 нуля - в шестом и седьмом блоках памяти и типа 4 единицы в восьмом блоке памяти на первую 14(1)- 14(4). третью 14{э) - 14(12) и четвертую 14(13) - 14(16) подгруппы входов устройства поступают правильные 16-разрядные комбинации подматриц Hi, Нз и Нз двумерного кода (16,8).

111 О

111 О

ILLS. ОООТГ

На вторую 14(5) - 14(8) подгруппу входов поступает неправильная 16-разрядная комбинация с тремя пакетными ошибками во второй, третьей и четвертой строке подматрицы Н2 (искаженные символы 2S3, 2S4, 2S5, 2S6, 2S7, 2S8, 2Ы, 2Ь2, 2ЬЗ - подчеркнуты, а искаженные строки «б , о Оз - отмечены стрелками):

111 9QO

йщ

11Г

Об

а f

Таким образом на входы 14 устройства (пример В) поступает 64-разрядная комбинация с шестью искаженными (I ) символами шестого и седьмого блоков памяти (2S3 - 2S8) и тремя искаженными (0 ) символами восьмого блока памяти(2Ь1,2Ь2 и 2b3), т.е. на входы 14 устройства поступает 9 искаженных символов.

На входы блоков 10i, Юз и 104 поступают логические нули, а на входы блока 102 поступает комбинация 0111 1110, соответствующая некорректируемой ошибке во второй подгруппе блоков памяти.

На выходах 16 устройства формируется код 0100 (НК02), а на выходах 17 - сохраняются логические нули.

Пакетные ошибки шестого, седьмого и восьмого блоков памяти исправляются в блоках 9б, 9 и 9в согласно примененному в них синдромно-мажоритарному алгоритму декодирования (хотя и we всегда три пакетные ошибки, возникшие в одной подгруппе блоков памяти, могут быть исправлены в блоках 9).

На информационные 14е. 14 и контрольные 21б, 21. 222 входы блоков 9е и 9 поступают комбинации: 0000, 1111, 1110, поэтому на входы каждого МЭ 281-28з этих блоков (фиг. 2, 4) поступает комбинация (011), а на входы блока 284 - комбинация (010).

Поэтому методом голосования на выходах 25 блоков 9е и 9 формируется правильная комбинация: 1110 (с исправленными 0 - 1 значениями 2S3, 2S4, 0 2S5 и 2S6, 2S7 и 2S8 шестого и седьмого блока памяти).

На информационные 14&и контрольные 218, 22г входы блока 9в поступают комбинации: 1111, 1111, 1110, поэтому на входы каждого МЭ блока 9з поступает комбинация (100), а на входы блока 284 - комбинация (101).

Поэтому на выходах 25 блока 9s формируется правильная комбинация 0001 (с ис- 0 правленными 1 значениями 2Ы,2Ь2 и 2ЬЗ восьмого блока памяти).

На выходах 23 (iyj) блока 6 сохраняются логические нули, а на выходах 24 (iyj) блока 6 - соответственно сохраняются логиче- 5 ские единицы т.к. в данном примере три пакетные ошибки (девять искаженных символов входа 14 устройства) исправляются на первом этапе декодирования в блоках 9б, 9j и 9е.

Поэтому на выходах 25 блоков 9i-9ie формируется правильное 64-разрядное кодовое слово: на выходах блоков 9-|-9з. 9s 9, 9g-9ii и 9i3-9is формируется комбинация 1110, а на выходах блоков 94, 9e, 9i2 и 9ie - формируется комбинация 0001.

На адресные входы четырех коммутатбров (фиг, 4) блока 11еи блока 11 поступают

соответственно комбинации: 11,11,11 и 10,

. а на адресные входы четырех коммутаторов

блока 11с- комбинации: 10,10, 10 и 11.

Поэтому на выходы 15е, 15з устройства пропускаются правильные комбинации: 1110, 1110 и 0001 соответственно с выходов 23 (ly j 0) блока 6 (т.е. третьи D2 ° информационные входы коммутаторов) или с выходов 24 (i у j 1) блока 6 (т.е. четвертые D3 информационные входы коммутаторов),

На выходах 18 устройства сохраняются логические нули, поэтому на входы блока 13 поступает 12-разрядная комбинация: 0100 0000 0000, а на выходах 19 устройства формируется код 0110.

В конце цикла Чтение (пример е) 64- разрядное кодовое слово с тремя исправленными пакетными ошибками, а именно с шестью исправленными (0 - 1) разрядами: 2S3, 2S4, 2S5 и 2S6, 2S7, 2S8 - шестого и

0

0

5

седьмого блоков памяти, и с тремя исправ- ненными (1- 0) разрядами: 2Ы, 2Ь2, 2ЬЗ - восьмого блока памяти, поступает с выхода 15 устройства на выходную магистраль данных

Аналогично в устройстве могут быть исправлены или обнаружены четыре пакетные ошибки определенной (корректируемой или некорректируемой) конфигурации.

Так, четыре пакетные ошибки в четырех разных подгруппах блоков памяти: в третьем, седьмом, 11-м и 15-м блоках памяти (пример а ) - могут быть исправлены в блоках 9з, 9, 9ц и 9i5.

Четыре пакетные ошибки в трех подгруппах блоков памяти1 в третьем, шестом, седьмом и 11-м блоках памяти (пример б ) - могут быть исправлены в блоках 9з. 9ц и 11е, 11

Четыре пакетные ошибки в одной под- группе блоков памяти1 в пятом, шестом, седьмом и восьмом (пример в) - могут быть исправлены в блоках 11s, 11е, 11т и 11з.

В данных примерах1 а , б ив , на контрольных выходах 16, 17 и 18 устройства формируется соответственно код ошибок:

0000 1111 0000 (а1),

или 0100 1010 0110 (б1),

или 0100 0000 1111 (в1), а на выходах 19 устройства формируется код корректируемой ошибки чтения 1 0110.

Четыре пакетные ошибки в двух под- группах блоков памяти (некорректируемой конфигурации): во втором, третьем и шестом, седьмом блоках памяти, могут быть обнаружены в блоках 10i, 102 и 13 устройства, При этом на контрольных выходах 16 и 17 устройства формируется запрещенная комбинация. 1100 0000, а на выходе 19 - код некорректируемой ошибки чтения : 1010. Аналогично в устройстве обнаруживаются и другие (4-N) пакетные ошибки некорректи- руемой конфигурации

Кроме того, устройством гарантированно обнаруживаются все трехбитовые и четырехбитовые (непакетные) ошибки.

Так, при возникновении некорректиру- емой трехбитовой ошибки на входах 14е и 14 устройства: в разрядах 2S3, 2S6 и 2S7 подматрицы Н2 (фиг. 3), и отсутствии ошибок на других входах 14 устройства, на входы а и / блока 102 поступит код: 0100 0100, который блок 102 воспримет за одиночную ошибку в разряде 2S4. а следовательно, сформирует на выходах 162 и 172 код корректируемой ошибки 01. Одновременно блок 92 неправильно исправит разряд 2S4, в результате чего на выходах 25 блоков 9е и 9у сформируется комбинация уже с четырьмя искаженными символами подматрицы Н2.1 2S3, 2S4, 2S6 и 2S7, а на выходах 232 и 23з блока 6 - соответственно сформируются четыре логические единицы : 2 у1, 2у2,3 у1 иЗу2.

В результате на контрольных выходах 16,17 и 18 устройства формируется запрещенная комбинация: 0000 0100 0110. а на выходе 19 - код некорректируемой ошибки чтения : 1010.

При возникновении некорректируемой четырехбитовой ошибки на входах 14е и 14 устройства1 в разрядах 2S3, 2S6, аб и а7 подматрицы Н2, внесенной, например, в кодовое слово при Записи (см. описание работы устройства в режиме Запись), т.е. при поступлении двух неправильных информационных разрядов: 2S3 и 2S6, формировании дополнительно двух неправильных контрольных разрядов: аб и а7 и записи в память кодового слова уже с четырехбитовой ошибкой (необнаруживаемой блоком 13 в режиме Запись) на контрольных выходах 16 и 17 устройства в режиме Чтение сохраняются логические нули, но на выходах 23а и 23з блока б сформируются четыре логические единицы : 2у 1, 2 уп , 3 у1 и 3 уп

В результате на входы блока 13 поступает запрещенная комбинация: 0000 0000 0110, а на выходе 19 устройства формируется код 1000, соответствующий в данном примере двухбитовой (некорректируемой) ошибке записи, обнаруживаемой в режиме Чтение, и работа устройства прерывается.

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

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

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

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

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

1)исправлять одиночные пакеты п-раз- рядных ошибок в N блоках памяти;

2)обнаруживать двухбитовые ошибки ё одном или разных блоках памяти;

3)обнаруживать одиночные ошибки, внесенные во входную информацию при записи в память.

Недостатками известного устройства является его низкая надежность и ограниченные функциональные возможности.

Зти недостатки связаны с тем, что из-за низкой корректирующей возможности примененного в устройстве кода, известное устройство не может скорректировать даже два пакета n-разрядных ошибок (или двухбитовую ошибку одного блока памяти), а также одиночную ошибку, внесённую во входную информацию При записи в память. В заявленном устройстве применен мо- йцифиррванный трехмерный код, состав- денный из : Vf Tмодифицированных двумерных кодов, с дополнительным контролем по четности для каждого (Vjsj) - разрядного ребра кодовой матрицы, и реализован синДроМно-мажорйтарный алгоритм кодирования и декодирования с адаптацией (в два шага), а также за счет значительного усложнения логики обнаружения ошибок, что позволяет устройству:

1)исправлять три пакета п-разряднь1х ошибок в N блоках памяти; : .- i

2)исправлять двухбитовые ошибки в од- : ном или разных блоках памяти (и обнаруживйть всё трех- И четырехбитовые ошибки); ; . 3) исправлять одиночные ошибки (и обнаруживать все двойные ошибки), Внёсё н- ные во входную информацию при записи 6 память. ; -;у- : :.

Ограниченные возможности известного устройства (второй его недостаток) объясняется тем, что данное устройство предназначено только для исправления ошибок жестко заданной конфигурации, а именно:

0

5

0

5

0

5

0

5

0

5

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

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

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

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

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

Заявленное устройство, реализующее модифицирова Нныйтрехмерный код, может быть дополнительно использовано:

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

-в системах хранения информации, вы- , полненных на магнитных носителях с N по- движными головками, в которых лакуны на

магнитной ленте могут привести к потере информации, считываемой несколькими (двумя, тремя) головками.

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

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

входов), блок обнаружения ошибок и N блоков коррекции, причем информационные входы группы каждого блока коррекции соединены с соответствующими входами группы первого генератора кодов ошибки и 5 являются информационными входами соответствующей группы устройства, первый контрольный вход каждого блока коррекции подключен к соответствующему выходу первого генератора кодов ошибок, вторые кон- 10 трольные входы с педвого по m-й блоков коррекции (где т ) объединены и подключены к выходам первой группы второго генератора кодов ошибок, первый, третий и четвертый выходы блока обнаружения 15 ошибок являются выходами некорректируемых ошибок устройства, выходом корректируемых ошибок которого является второй выход блока обнаружения ошибок, отличающееся тем, что, с целью 20 расширения области применения устройства за счет исправления трех пакетов и обнаружения N пакетов n-разрядных ошибок, в него введены третий генератор кодов ошигруппы подключены к входам третьей груп пы блока обнаружения ошибок и являютс контрольными выходами третьей группы ус тройства, информационными входами кото рого являются входы второго генератора кодов ошибок, каждый 1-й блок коррекции (где (k-1)m+i) является соответственно 1-м

(где i 1m блоком коррекции k-й группы

(где i - соответствующий номер 1-го инфор мационного входа устройства в информаци онных входах k-й группы устройства) выходы блоков коррекции подключены к соответствующим входам третьего генератора кодов ошибок и управляющим входам группы соответствующего блока коммутаторов выходы коГорого являются соответствующими информационными выходами устройства, прямые выходы i-й группы третьего генератора кодов ошибок подключены соот- ветствеьно к входам 1-го элемента ИЛИ, а также к информационным входам первой группы 1-го блока коммутаторов, инверсные выходы 1-й группы третьего генератора кодов ошибок подключены к соответствую-| - г- -- -г- -.. j v t j t i IW/J ГЧЛГХЛСП Ы ГЧ UU I DC 1 U I БУК}

бок, содержащий m групп блоков свертки по25 ЩИм информационным входам второй

модулю два, блок из m индикаторов исправ-группы 1-го блока коммутаторов, адресностей, N блоков коммутаторов и rpynhaиые входы группы которого подключены

элементов ИЛИ, второй генератор кодовк соответствующим выходам первой

ошибок содержит со второй по m-ю группыгруппы k-ro индикатора неисправностей

блоков свертки по модулю два, причем вы-30 входы первой и второй групп которого

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

;.

35

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

группы подключены к входам третьей группы блока обнаружения ошибок и являются контрольными выходами третьей группы устройства, информационными входами которого являются входы второго генератора кодов ошибок, каждый 1-й блок коррекции (где (k-1)m+i) является соответственно 1-м

(где i 1m блоком коррекции k-й группы

(где i - соответствующий номер 1-го информационного входа устройства в информаци- онных входах k-й группы устройства), выходы блоков коррекции подключены к соответствующим входам третьего генератора кодов ошибок и управляющим входам группы соответствующего блока коммутаторов, выходы коГорого являются соответствующими информационными выходами устройства, прямые выходы i-й группы третьего генератора кодов ошибок подключены соот- ветствеьно к входам 1-го элемента ИЛИ, а также к информационным входам первой группы 1-го блока коммутаторов, инверсные выходы 1-й группы третьего генератора кодов ошибок подключены к соответствую -t - j v t j t i IW/J ГЧЛГХЛСП Ы ГЧ UU I DC 1 U I БУК}

ЩИм информационным входам второй

входы первой и второй групп которого

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

Qaг 1

ш/ „

1С2 v/TJ

Фиг, 2

фиг J