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

000

О

111

1

Изобретение относится к вычислительной технике и может быть использовано в качестве устройства для обнаружения и исправления двойных и пакетных ошибок в блоках памяти. Цель изобретения - повышение корректирующей способности устройства. Устройство содержит N блоков генераторов кода и исправления ошибок 1, группу блоков 2 свертки по модулю два по числу разрядов блоков памяти, группу 3 из N блоков коррекции 4, ,группу из N индикаторов неисправностей 5, группу из II блоков коммутаторов 6, блок обнаружения ошибок 7. Устройство реализует трехмерный итеративный код и позволяет исправлять двухбитовые и пакетные ошибки, а также одиночные ошибки, внесенные во входную информацию при записи. 5 ил.

Согласно модифицированной структуре примененных в устройстве двумерных кодов: с контролем по нечетности строк и столбцов и с контрольным разрядом по нечетности CQ, кодг- вая подматрица ЈН5 которого представлена на фиг. 3, при появлении на входе 8j устройства пакета ошибок типа 16 нулей или 16 единиц каждая строка и столбец кодовой МРТ5

с шестью иска- J0 a2, S6, Ъ13

при

16 единиц на входы -., g. поступит информация женными символами Сс Ъ2, ЬЗ ( в разрядах соответственно dl, d8, d9, d13, d14 и d15 пятого блока памяти, на выходах 17 блоков свертки по модулю два 2, 2g,

2, 2,%, 214 и 2,g сформируются шесть ва) : 1d1, 8d1, 9d1, 13d1, 14d1 и 15d1 единичных разрядов синдрома: 1, 8, а на остальных десяти выходах 18 бло У9 If13 If1 и У 15, а на выходах

десяти других блоков свертки 2 (из

I общего числа 16) сохранятся О.

iНа выходах шести сумматоров по модулю два блока сформируются , О (исправленные значения шести искаженных символов входа 8 устройст- i

ка ; сохраняются 1 (правильные значения десяти (из шестнадцати) символов входа 8g- устройства. Затем в коммутаторе 6у происходит исправление шести искаженных символов вхсда 8j устройства по формулам:

(вых) (HKOp).(1dO) V (НК05). 5Со (вх) + fj J (вых) (НК05). (8dO) V HKOS). (вх) + ув) (вых) (НКО). (9dO) V (НКО).58б(вх) + (вых) HKbs).(i3dC) У(НКоДзЬКвх) + у 13 J (вых) (НКОу). (14dO)V(HK05).5b2(Bx) + (вых) (НКО). (15dO)V(HKOy) 5ЪЗ(вх) + Ґ15,

На выходах 9 формируется 128-разрядное кодовое слово с шестью исправленными символами входа 8 устройства

Аналогично исправляются все девять информационных разрядов: Co,S1-S8 и контрольный разряд g пятого блока памяти.

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

В режиме записи в память на входы 85 устройства поступило четное девятиразрядное сообщение с одним искаженным символом 5S6 1 (подчеркнут): 100 011 111. На выходах 14

блока 1 г сформировались семь контрольных разрядов пятого блока памяти с двумя направильными символами аЗ О и Ы 1, т.е. для записи в память сформировалось 16-разрядное кодовое слово двумерного кода подматрицы Н , содержащее уже три искаженных символа 5S6, 5аЗ и 5Ы (подчеркнуты):

о

(Пример б)

ва) : 1d1, 8d1, 9d1, 13d1, 14d1 и 15d1 а на остальных десяти выходах 18 блока ; сохраняются 1 (правильные значения десяти (из шестнадцати) символов входа 8g- устройства. Затем в коммутаторе 6у происходит исправление шести искаженных символов вхсда 8j устройства по формулам:

При отсутствии ошибок (если бы символ S6, поступивший на вход 85-,был неискажен) правильно сформированное кодовое слово выглядело следующим образом:

30

(Пример а)

5

0

Hit)

п

Ы О

5

0

Как было описано выше, данная трехбитовая ошибка двумерного кода является некорректируемой ошибкой устройства (в режиме чтения), так как при считывании кодового слова (пример б) из 5-го блока памяти на выходах 15 и 16 генератора 19,- кода ошибок был бы сформирован синдром: 0001 0001, которьй индикатор неисправности 5g воспримет за корректируемую одиночную ошибку в разряде g, в результате чего вместо некорректируемой трехбитовой ошибки в разрядах 5S6, 5аЗ и 5Ы будет ложно исправлена ошибка в разряде ggr, и на выходы 9f устройства поступит кодовое слово уже с четырьмя ошибочными символами (подчеркнуты):

55

(Пример в)

2516

Поэтому в предлагаемом устройстве реализуется мажоритарно-синдром- ный алгоритм кодирования с адаптацией (обнулением контрольных разрядов двумерного кода). Как было описано выше, при поступлении на вход 8 устройства информации с одним искаженным символом контрольные разряды 1-го блока памяти, сформирован- 14 блока 1 обнуляа, на управляющий вход которого поступает 1. Поэтому, если, например, на входы &5 устройства поступит информационное Сообщение 100 011 111, в режиме Запись в пятый блок памяти будет записано не кодовое слово (пример б),

ные на выходе

ются в коммутаторе 6

а кодовое слово с нулевыми|Г контрольными разрядами, содержащее шесть ошибочных символов: S6, а2, аЗ, Ъ2, ЬЗ, g (подчеркнуты):

100 011 111

(Пример г)

000

О

При декодировании данного кодового слова на выходах Ю5 и 11 устрой-3 ства появится код 10 некорректируемой ошибки 5-го блока памяти, которая является корректируемой ошибкой устройства, так как на входы индикатора неисправностей 5 посту

пит синдром 0101 1111, на входы блока 7 - код ошибки 00001000 0000000 соответствующий некорректируемой ошибке пятого блока памяти и на выходах 12 сформируется код 0110 - при- знак корректируемой ошибки устройства. Кодовое слово (пример г) исправится методом адаптации в коммутаторе 6, и на выходе устройства появится кодовое слово (пример а) с .шестью исправленными символами: 5S6 (вых), 5а2 (вых), 5аЗ (вых), 5Ь2 (вы 5ЪЗ (вых), g5 входа 8 устройства (подчеркнуты):

100 О 011 1 011 1

011 155

Реализация в устройстве синдромно- мажоритарного алгоритма кодирования ч декодирования с адаптацией поз26

0

воляет исправлять ошибки, в кодовое слово

внесенные | при записи в память.

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

Работу блока 7,рассмотренную отдельно для режиме Запись и Чтение можно выразить более простыми формулами, общими для режима кодирования и декорирования информации.

Работа блока 7 - формирование сигналов на выходах 12 (НпЗп), 123 (Нп4го), 122(КО) и 12, (НКО)--; в общем виде запрограммирована по формулам:

НпЗп

...УСнксу

Hn4m

(НКО,

ко,);

ко) v

KO()VC

(НКО, + ,..V(HKON + КО $}; КО (КО, V ... VKON) х X ( ... V (ККОе)х

х ()А А (нком V кое )А

A(HKO VKOgt7) Л ... Л (HKONV KCJ ;

НКО (КО)- (НпЗп V Hn4m).

Последняя формула означает, что сигнал НКО формируется как в режиме Запись, так и в режиме Чтение на выходе 12j устройства при поступлении на входы блока 7 ненулевого кода синдрома, который при

этом не совпадает

Л

ни

с одной из разрешающих омбинаций , соответствующих корректируемой ошибке КО устройства. Из формул видно, что сама информация об ошибке - сигналы на выходах 12, (НКО) и 122 (КО) и сигналы на выходах 12 ъ (Hn4m) и 12 j. (НпЗп) - формируются в парафазном коде (01) или (10).

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

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

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

5l

9иг. 2

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

24

ДО

А

1Л 1

о ст.

-зчО

7

фиг. 5