Запоминающее устройство с коррекцией ошибок Советский патент 1984 года по МПК G11C29/00 

Изобретение относится к вьлчислительной технике, в частности к контролю работы запоминающих устройств и может быть использован в запоминающих устройствах ЭВМ. Известно запоминающее устройство с коррекцией ошибок, содержащее накопитель, схемы формирования проверочного слова, дешифраторы одноразрядной и двухразрядной ошибок постоянное запоминающее устройство, схему обнаружения ошибок и селектор С 3Однако многократное обращение к постоянному запоминающему устройств при возникновении ошибки в указанно устройстве значительно увеличивает время обращения к запоминающем устройству. Наиболее близким по технической сущности к изобретению является запоминающее устройство с коррекцией ошибок, содержащее накопитель информационный вход которого является информационным входом устройст ва, формирователь имцульсов контрольных разрядов, вход которого соединен с информационным входом устройстйа, а выход соединен с контрольным входом накопителя, блок поразрядного суммирования по модулю два, выход которого является информационным выходом устройства, а первый вход соединен с выходом накопителя, соединенные последовательно формирователь импульсов контрольного слова, вход которого соед нен с выходом накопителя, блок постоянной памяти и первый депшфратор, выход которого соединен с вторьм входом бл:)ка поразрядного суммирования по модулю два, первый элемент ИЛИ, входы которого соединены с выходами формирователя импульсов контрольного слова, между выходами разрядов блока постоянной памяти и третьим входом блока поразрядного суммирования по модулю два включен второй дешифратор 2 , Недостатак данного устройства обусловлен невозможностью обнаружен пакетных ошибок и сочетаний однот разрядных и пакетных ошибок, которы могут возникнуть при использовании многоразрядных блоков накопителя, что снижает достоверность храни мой информации. Цель изобретения - повышение надежности устройства. Поставленная цель достигается тем, что в запоминающее устройство с коррекцией ошибок, содержащее накопитель, первый элемент ИЛИ,формирователь импульсов контрольных разрядов, формирователь импульсов контрольного слова, блок постоянной памяти, первый и второй дешифраторы, сумматор по модулю два, причем йнформационньй вход накопителя соединен с входом формирователя импульсов контрольных разрядов и является входом устройства, выход формирователя импульсов контрольных разрядов соединен с контрольным входом накопителя, выход которого- подключен к входу формирователя импульсов контрольного слова и первому входу сумматора по модулю два, выход которого является информационным вькодом устройства, первьй выход формирователя импульсов контрольного слова соединен с входами первого элемента ИЛИ и блока постоянной памяти выход которого подключен к входам первого и второго дешифраторов, выходы которых соединены соответственно с BTopbiM и третьим входами сумматора по модулю два, введены элементы И, второй, третий и четвертый элементы ИЛИ, элемент ИЛИ-НЕ, причем второй выход формирователя импульсов контрольного слова соединен с первыми входами первого, второго и третьего элементов И, выход первого элемента ИЛИ подключен к вторым входам первого второго и третьего элементов И и к первому входу четвертого элемента И, выход блока постоянной памяти соединен с входами третьего и четвертого элементов ИЛИ и входом пятого элемента И, выход третьего элемента ИЛИ подключен к третьим входам первого и третьего элементов И и к второму входу четвертого элемента И, выход четвертого элемента ИЛИ соединен с четвертыми вхо-. дами первого и третьего элементов И и с третьим входом четвертого .элемента И, выходы первого и второго элементов И соединены с входами второго элемента ИЛИ, выход которого подключен к четвертому входу сумматора по модулю два,выходы третьего, четвертого и пятого , элементов И соединены с входами элемента ИЛИ-НЕ, выход которого под 3 ключей к пятому входу сумматора по модулю два и является контрольным выходом устройства. На фиг.1 представлена структурная схема предложенного устройства, на пример выполнения блока поразрядного суммирования по модулю два, на фиг.З и 4 - проверочная Н-матрица кода для разрядности запо минающего устройства равной 128 разрядам. Устройство, содержит накопитель 1 форми рователь 2 импульсов контрольных разрядов, сумматор 3 по модулю два, формирователь 4 импульсов контрольного слова, блок 5 постоянной памяти, первый дешифратор 6, первый элемент ИЛИ 7, второй дешифратор 8, первый элемент И 9, второй элемент И 10, третий элeмJeнт И 11, чет вертый элемент И 12, пятый элемент И 13, элемент ИЛЙ-НЕ 14, второй элемент ИЛИ 15, третий элементШШ 16, четвертый элемент ИЛИ 17, блок 18 элементов ИЛИ, блок 19 элементов И, блок 20 двухвходовых схем сложения по модулю два. ,0 ,1 /2 ,3 ,+ ,5 .4 ,7 oLd-cf-oicieitid Аеко .0 ,3 е э ,12 о 3 ,6 01 tJL etot оС сС еС d

где ci - вектор-столбцы степени 1 Н-матрицы для поля Галуа GF(2).

Разряд SO проверочного слова получается сложением по модулю два тех разрядов, у которых имеется 1 в верхней строке матрицы. Разряды 81 проверочного слова получшотся сложением, по модулю два разрядов второй строки, а разряды S2 - третьей строки Н-матрицы. Разряд общей четности определяется как 80 SO + 81 s- 82.

При возникновении ошибок в i и j разрядах хранимого в накопителе слова значения разрядов 81 и 32 проверочного слова,определяются

. 5i i ©dLJ:S2 c ©ct H.

Разряд общей четности 80 0.

При возникновении ошибки в одном разряде хранимого слова выполняются условия 0

(81), . При возникновентш трех ошибок разряд общей четности SC равен единице, а условие 82(81) не выполняется.

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

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

Этому требованию удовлетворяет распред ение вектор-столбцов

Н-матрицы декодирования по пакетам которое при разрядности пакета, равной 4, имеет вид 24 В основу работы предложенного устройства положены следую цие теоретические предпосьшки. Повышение требований к надежности. запоминающих устройств (ЗУ) на полупроводниковых эапоминающих микросхемах привело к необходимости применения корректирующих кодов Боуза-Чоудхури-Хоквингема (БЧХ),исправляющих одну или две одноразрядные ошибки, и обнаруживающих три одноразрядные ошибки, возникающие в результате сбоев или отказов в полупроводниковом ЗУ. Однако эти коды не обнаруживают ошибки, при отказах строки запоминающих микросхем модуля памяти, всего модуля памяти, схем кодирования и декодирования и др., т.е. при отказах и сбоях, приводящих к пакетным ошибкам, а также к сочетаниям пакетных и одноразрядных ошибок. Для кода БЧХ с параметрами: п - кодовое слово, равное 16 и - . информационное слово, равное 7, порощдаю1ций полином имеет вид Т(Х) (XV X +1). Щ оверочная Н-матрица декодирования следующая о / 1 о 1 111 в 9 10 11 15 ,13 Л4 eicioLdL cL е(- cL О э ,12 ,0 ,3 .6 /Э , оС d d с1 d об об

Пакет 2

Пакет 1

О

1 1

К

,12

d° d

oi ot

СЗ С8

СО 5 С1 А Проверочная Н- матрица кодирования строится аналогично проверочной Н-матрице декодирования только порождающий цолиноиР(Х) (.Х+1) (X +x+X +X+l) выбирается по известным таблицам построения кода БЧХ. Устройство работает следующим образом. При записи информационное слово поступает с информационного входа устройства в накопитель 1 и формирователь 2 импульсов контрольных разрядов, где в соответствии, с Н-матрицей кодирования формируют1 ся Значенияконтрольньпс разрядов, которые также поступают в накопител Т через его контрольный вход. Щ)и считьгаании значения информационных и контрольных разрядов поступают на формирователь 4 импул сов контрольного слова, где опреде ляются значения разрядов SO, SI и контрольного слова в соответствии с Н-матрицей декодирования (фиг.З и 4). В формирователе 4 импульсов контрольного слова определяется также значение разряда общей четности, как сумма по модулю два значений разрядов SO, SI и S2 контрольного слова,т.е. SO ф S1 (Ф S Значение разряда общей четности контрольного слова поступает с дополнительного выхода формирователя 4 импульсов контрольного слова на первьй инверсный вход первого элемента И9, первый вход второго эле мента И 10 и первьй вход третьего элемента И 11. Значения разрядов S1 и S2 проверочного слова являютс адресными разрядами блока 5 постоя ной памяти. По адресу S t S2 из блока 5 постоянной памяти считыва ется два слова А... .А В.. .Bipja J, J в которых содержатс «т - - - - у л - ----- - -.-. - --т тт- -- - -- В двоичной форма значения местопол жения либо одной одноразрядной опш ки (слово А...А , двух одноразрядных ошибок (слово

Пакет 4

1 О

13

,14

ot о(

.12

,12

L С2

«1 С4

7

1 А,,...А ДЛЯ первой ошибки, а слово В.. .ВГ{о J, для второй ошибки. Здесь .h означает ближайшее большее целое число, п кодовое слово, определяемое как сумма информационных и контрольных разрядов. При возникновении одной или двух одноразрядных ошибок считанные из блока 5 постоянной памяти кодовые слова дешифруются в первом дешифраторе 6 (слово А(.. .Argoij-jn J и втором дешифраторе 8 (слово B.,.Brg -i а затем в сумматоре 3 по модулю два происходит непосредственное исправление отказавших разрядов. В первом элементе ИЛИ 7 происходит определение неравенства нулю разрядов S1 и S2 -проверочного слова. В третьем 16 и четвертом 17 элементах ИШ происходит определение неравенства нулю считанных из блока постоянной памяти 5 кодовых слов А .. и Б...Бг(-, соответственно.2 J В первом 9 и втором 1П элементах И и во втором элементе ШЖ 15 происходит определение значения вектора, ошибки контрольного разряда СО, т.е. в случае ошибки в этом разряде на выходе второго элемента ИЛИ 1,5 вырабатывается сигнал логической 1. Первьй элемент И 9 вырабатывает сигнал вектора ошибки контрольного разряда СО только в том случае, когда имеется вторая, ошибка в любом другом разряде хранимого в накопителе 1 слова. Второй элемент И 10 вьфабатывает сигнал вектора-ошибки контрольного разряда СО, когда имеется только одна ошибка в считанном из накопителя t слове и она находится в контрольном разряде СО. В третьем,элементе И 11 вьфабатывается сигнал о наличии трех одноразрщных ошибок в слове, считанном из накопителя 1, причем среди них нет ошибки контрольного разряда СО. В пятом элементе И 13 вырабатывается сигнал о наличии пакетной ошибки.При этом из блока 5 постоямной памяти, считьшаются кодовые слова все разряды которых равны логической 1. В элементе ИЩ-НЕ 14 вырабатывается управлякмцийл сигнал для сумматора 3 по модулю- два. При наличии одной или двух-одноразрядных ошибок ВЕфабатывается сигнал логической .1 который.разрешает, коррекцию отказав- ших разрядов с помощью блока 19 элементов И и блока. 20 двухвходовьпс схе сложения по модулю два (фиг.2). В блоке схем ИЛИ 18 происходит поразр;яи ное объединение соответствунмцих выходов первого депгафратора 6 и второго дешифратора 8. При наличии трех одноразр1щных ошибок или пакетных ошибок, или сочетания пакетных ошибок с одноразрядшлш вырабатывает ся сигнал логического , запрещаюпщй коррекцию в сумматоре 3. по/модул два. . В зависимости от значений разрядов SO...S2 контрольного слова и значени разрядов кодовых слов А.. .Аг|в „i и Б.. .B jo%-nJ возможны случаи, при веденные в таблице. , Дпя обнаружения сочетаний пакетных ошибок с одноразрядН1Л4И необходимо, чтобы по модулю два любого пакета раз рядов с любым вектор-столбцом .одиночного-разряда Н-матрицы не равнялась никакому из используемых вектор-столбцов Н-матрицы или никакой сумме двух любых вектор-столбцов Н-матрищ 1. Различие сочетания 4-разрядной пакетной ошибки и одноразрядной ошибки от двух одноразрядных ошибок /осуществляется-за счет различия разряда общей четности. Различие сочетания i-й 4-разрядной пакетной ошибки и j-й одноразрядной ошибки от любой одноразрядной осуществляется за счет значения разрядов Si контрольного слова для сочетания ошибок могут совпадать со значениями разрядов S1 контрольного слова только j-й одноразрядной ошибки, так как разряды 81 пакетной ошибки всегда равны нулю (Н-матрица на фиг.З и 4), значения разрядов S2 контрольного слова для сочетания ошибок всегда неравны значениям разрядов S2 контрольного слова J-й одноразрядной ошибки, так как значения разрядов S2 контрольного слова i-й 4-разрядной пакетной ошибки всегда неравны нулю (Н-матрица на фиг.З и А). При разрядности пакетных ошибок, равной восьми, необходимо объединить два пакета по четыре разряда проверочной Н-матрицы. Все комби- нации пяти, шести и семиразрядных ошибок среди восьмиразрядного пакета ошибок определяются с помощью ЭВМ. Процент обнаружения этих комбинаций ошибок равен 97-99, а для восьмиразрядного пакета - 100. Устройство позволяет повысить достоверность хранимой в ЗУ и вьдаваемой из него на обработку в другие устройства информации за счет того, что в нем по сравнению с прототипом щ)оисходит обнаружение пакетных ошибок и сочетания пакетных ошибок с одноразрядными. ГЦзизнак наличия обнаруживаемой, но некорректируемой-ошибки поступает на выход.данного устройства ив приемном устройстве может использоваться для блокировки приема и обработки ошибочной информации.

О

О

Любое значе- Любое значение, неравное ние,неравнулю.ное нулю

Условие (31) вьшол няется

О

О

Любое эначе- Любое значение, неравное ние нулю

Условие (S1) не выполняется

Любое значе- Любое значение ние

Условие (S1) не вьшолняется

Любое значе- Любое значение, неравное ние нулю

Условие (81) не выполняется

О Любое значение, неравное нулю

Ошибок нет

Одноразрядная ошибка в разрядах кроме разряда СО

Одноразрядная ошибка в контрольном разряде СО

Двоичный

Две одноразномер мес- номер мес- рядные ошибки

тоположения в разрядах, второй ошиб- кроме конки . трольного разряда СО

О

Три одноразрядный ошибки в разрядах, кроме разряда СО.

Одноразрядная ошибка и пакетная ошибка разрядности 4

Три одноразДвоичный

й рядные ошибки, номер месестоположенияпричем третья ения второй ошибка в разряде СО ошибки

Пакетная .ошибВсе разряряка разрядносыды равны ти 4 или две единице пакетные ошибки по 4 разряда каждая

(put, Т

С дыхода элемента ИЛИ- М17 C I J ./J It J 0 n 0 0 0 f f r 1 0 0 0 0 r f и O.ipfOiOioio ТШ ГоТТГо U ToJ 01010101 010101010101010101010101 0101 01 01 0 1 01 01.01 01 0101 0101010101 010101 0101010 10110 10 101010 1 0 t 0 10 0101 0101 10 1010 to 01010101 10101010 01 01 1010010110100101101001 011010 ai 10011 00110011G01100110 01100110 о ) и тг1 7тггг 7 т т 010000 01 00011011 1110qtqo / 111 ц 00010001011110001011101100101101 0100 to ft 0100101 1 1000100010001000 00 0101 11 00100100101 1 00 f о 10 00 000/ 01010011 0000 0110000010010101 110 о QO10001 0011 1 O.t 1 1 о 1 1 1 10 001 1 010о 1 i OCIC2C5&C CffCmCS(CnmCffmi 2 S 4 S6 7 S9Wff 12/5 /5/6/7 f Hi fwf Hi fШ 010 101 Of 0 1 0 1 0 1 0 10 1 0 1 01 0 10 To 1 01 01 1010 101010 1011 1010 10 f 01 010101010 01010 г 0101010 001 1010 101010 10 10/& 01 010101 1010101001010101 10101010 0101101001011 OfO01011010010110 J 0 1 iri1iTJ( 10 OUOO 1 ООГОО 1 1 1 001 1011 11100100010000010100000111100100 TO 110100f 101 n010001 111 0/0000000 oil 1 Of 11011101 1110 11 01 0 0 1 0 11 110 0 01 10 11101 о 11 о 010 о 01 00100111 о aooo 011 о о о 001 10010 10 1 f о 00/ 01 01 1 iJf tOI 11 on о 001 о о 00 1 1 1 1000 1101 lO/O, 1819 202122252 25262728 295051 52Х 5 5556575В59А0 1 2(5Ш7Ы со... С1 контрольн 1е 1... - utftpop tffuuo/ /fbie разряды fpuzJ

Tl О О О О 1 1 О 1 6 О О 01 t fj 01 010100010001

Р т ГПП-гт ж г ГгГ/ТТ 7 10 1 о 1 О 10 I 01 о f О 1 о 1 о 1 о о о 1 о 1 о 1 О г о 0

01010 1010 tOIOfOlOIOffJOIOJOtOlOf Ol010(OlOf010t01lO}OOOIOf010IOIO .01 01 о 1 о I I о 1 о 1 о 1 00 1 о 1 П f)1 1 о i о 1 010

01 011 о 1 о о 1 о 11 о 1 00 1 о 100 J 00 i on 01 о

k-nHi Wi Hii- rrri n i. f о 1100о 11 j lot 01 1000101000100111 о о n j 1 о ouG о о i о 00 1 о о 1 о 11 о 11 о f 1 f 01 1

00101101110 f 001 011-10111 0000 I OOOf

и f и I,

Ш,

f on n 0 101 f 1 eaoiooo 11000110 10100

- 1010 01 n01UOni//--IUVVVVIIUUIUJUU111 01 0 0 0 1 1 1 f у 1 0 1 10

{j 101110 10111 0It 1 f 00001111 ioiooi(A

3051 ЛЯЯ55ЛетЯ398в61626Ш65в6616В63Я7П2757 75ГК7778798вК

г ш ттч-ш г

1010101010101010101 0101010101010

101 010 1 0 г 0 1 010 to 10 10 10 to t о 1010 re

0101010101010 tot 1 01 0 to 16 to 101 в t 0

0181010110101010010 101 a 110 1 01 01B

0 t 0 1 to t 0 0 t в 11 0 t 0 0 t 0 t r 0 10 0 10 11 010

nmi-m Him fw ff/-fw wn

111Q ion 0 10 01 11 в tie 011 1 6 111 0 101 i 901000100106t et to/t tot ft f t fffffOet

5 ИД1 | И { Л1/ г |

|||/И1 г;и// ли,П;|||Ш

ти«яяаямаяяхяят1

50... 11 J - uMfofmntaofante SOfSlfSf feifodH lyo&epovHiKO fjuth

Ui.4.

n

л

ЗАПОМИНАЩЕЕ УСТРОЙСТВО С КОРРЕКЦИЕЙ ОШИБОК, содержащее накопитель, первый элемент ИЛИ, формирователь импульсов контрольных разрядов, формирователь импульсов контрольного слова, блок постоянной памяти, первьй и второй дешифраторы,- сумматор по модулю два,причем информационный вход накопителя соединен с входом формирователя импульсов контрольньпс разрядов и является входом устройства, вькод формирователя импульсов контрольных разрядов соединен с крн- рольньм входом накопителя,выход которого подключен к входу формирователя импульсов контрольного слова и первому входу сумматора по модулю два, выход которого является информационным выходом устройства, первый выход формирователя .импульсов контрольного слова соединен с входами первого элемента ИЛИ и блока постоянной памяти, выход которого подключен к входам первого и второго дешифраторов, вьЬсоды которых соединены соответственно с вторым и- третьим входами сумматора по модулю два, отличающееся тем, что, с целью повышения надеж- ности устройства, оно содержит элементы И, второй, третий и четвертый элементы ИЛИ, элемент ШШ-НЕ,причем второй вьБсод формирователя импульсов контрольного слова соединен с первьми входами первого, второго и -третьего элементов И, выход первого элемента ИЛИ подключен к вторым входам первого, второго и третьего элементов И и к первому входу четвертого элемента И, выход блока достоянной памяти соединен с входа(Л ми третьего и четвертого элементов ИЛИ и входом пятого элемента И, выход третьего элемента ИЛИ подключен к третьим входам первого и треть-g его элементов И и к второму входу четвертого элемента И, выход четвертого элемента ИЛИ соединен с чет-f вертыми входами первого и третьего элементов И и с третьим входом четвертого элемента И, выходы первого и второго элементов И соединены с входами второго элемента ИЛИ, выход| которого подключен к четвертому входу сумматора по модулю два, выходы третьего, четвертого л пятого элементов И соединены с входами элемента ШШ-НЕ выход которого подключен к пятому входу сумматора по моду тю два и является контрольным выходом устройства.