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

 

ОП ИСАНИЕ

ИЗЬ6РЕТЕН ИЯ

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ

Союз Советскик

Социалистическик

Республик

< 765886 (61) Дополнительное к авт. свид-ву— (22) Заявлено 31.10.78 (21) 2680934/18-24 с присоединением заявки №вЂ” (23) Приоритет— (51) М. Кл.а

G 11 С 29/00

Гооудерстееиимй комитет

Опубликовано 23.09.80. Бюллетень ¹ 35

Дата опубликования описания 28.09.80 (53) УДК 681..327 (088.8) до делам иэооретеиий и открытий

А. В. Городний, В. И. Корнейчук, 1О. Б. Рычагов, А. И. Слободянюк и В. В; Садовский (72) Авторы изобретения (71) Заявитель (54) УСТРОИСТВО ДЛЯ КОРРЕКЦИИ ОШИБОК

В БЛОКЕ ПАМЯТИ

Изобретение относится к запоминающим устройствам.

Известно устройство для коррекции ошибок в блоке памяти содержащее регистры, схему сравнения, логические элементы 11J

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

Из известных устройств наиболее близким техническим решением к предлагаемому изобретению является устройство для коррекции ошибок в блоке памяти, содержащее информационный регистр, регистр инверсного кода, элементы И, НЕ и ИЛИ, сумматор по модулю два, схему сравнения и блок управления, причем выходы информационного регистра подключены к первым входам одних из элементов И, входам элементов НЕ, сумматоров по модулю два и первому входу схемы сравнения, второй вход которой соединен с выходом регистра инверсного кода, выходы элементов НЕ подключены к первым входам других элементов И, вторые входы элементов И соединены с одними из выходов блока управления, а выходы — со входами элементов ИЛИ, выходы которых подключены к одним из выходов устройства, 2 выходы сумматоров по модулю два соединены с одними из входов информационного регистра, другие входы которого и входы регистра инверсного кода соединены со входами устройства 12).

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

Если ошибки преимущественно вызваны отказами типа генератор «О» и генератор «1>, то коррекция ошибок может быть осуществлена с меньшей временной избыточностью.

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

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

765886 отказов, схемы сравнения, сумматоров по модулю два, информационного регистра и элементов HE.

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

ИЛИ, выходы которых соединены с одними из входов элементов И второй группы, одни из входов блоков инверсии подключены к выходам элементов HE второй группы, а выходы — к выходам логического блока, входы которого соединены со входами элементов И первой группы и другими входами элементов И второй группы и блоков инверсии.

Целесообразным вариантом выполнения блока инверсии является блок, содержащий элементы НЕ, И и ИЛИ. причем первые входы первого и второго элементов И подключены соответственно ко входу и выходу элемента НЕ, а выходы — ко входам элемента

ИЛИ, выход которого подключен к выходу блока инверсии, вторые входы элементов И и вход элемента HE соединены соответственно со входами блока инверсии.

На фиг. l изображена структурная схема предлагаемого устройства; на фиг. 2— часть блока анализа отказов, называемая схемой анализа отказов и соответствующая одному контрольному разряду в информационном слове; на фиг. 3 — схема логического блока; на фиг. 4 — схема блока инверсии.

Устройство содержит (см. фиг. 1) информационный регистр 1, регистр 2 инверсного кода, элементы HE 3, элементы И 4 и 5, элементы ИЛИ 6, сумматоры 7 по модулю два, схему сравнения 8, блок 9 анализа отказов, логический блок 10. Элементы ИЛИ б и блок 10 имеют соответственно выходы

11 и 12, регистры 1 и 2 — соответственно входы 13 и 14.

В состав устройства также входит блок управления 15.

Вход блока 9 подключен к выходу схемы сравнения 8. Входы блока 10 соединены соответственно с выходами блока 9, схемы сравнения 8, сумматоров? по модулю два, регистра 1 и элементов НЕ 3.

Блок 9 анализа отказов (см. фиг. 2) состоит из К схем анализа отказов, где К вЂ” количество контрольных разрядов в информационном слове, записываемом в запоминающую ячейку. На фиг. 2 приводится пример выполнения i-ой (1 < i g k) схемы анализа отказов.

Схема анализа отказов состоит из j-входовых элементов И 16, входы которых связаны с соответствующими выходами схемы сравнения 8, а выходы соединены со входами элемента ИЛИ 17, своим выходом связанным с блоком 10 (j — количество разрядов в анализируемой группе разрядов информационного слова, считываемого яз запоминающей ячейки).

Схема анализа отказов реализует логи- ческую функцию у! — — х V x х х з... ...x>Vx хахз...х Чх хгхз..х>, где х ь..х — сигнаЛы на выходах соответствую1 щих разрядов схемы сравнения 8, у„ = 1, если количество отказавших разрядов в анализируемой группе разрядов равно единице.

В противном случае у; = О.

Таким образом, на выходах блока 9 анализа отказов формируется код y y уз...y

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

Блок 10 (см. фиг. 3) состоит из первой группы элементов И 18, входы которых.связаны с соответствующими выходами сумматоров 7 по модулю два и блока 9 анализа отказов, а выходы подключень! через элементы ИЛИ 19 к первым входам элементов

И 20 второй группы. Ко вторым входам элементов И 20 подключены выходы схемы срав. нения 8. Выходы элементов И 20 соединены с первыми входами блоков инверсии 21, втоЗО рые и третьи входы которых связаны соответственно с прямыми и инверсными выходами информационного регистра 1.

На фиг. 3 принятые следующие обозначения для сигналов и А А ...А — на выходах блока ? по модулю два; у ну ...у„— на выходах блока 9 анализа отказов; х ьх q...x„— на выходах схемы сравнения 8;

Q ьg ...Я,„— на прямых выходах информационного регистра 1;

Q i,Qa...Q< — на инверсных выходах информационного регистра 1; где n — количество разрядов дополненного информационного слова.

4$

Блок инверсии 21 содержит элементы

НЕ 22, первый 23 и второй 24 элементы И и элемент ИЛИ 25, причем первые входы эле ментов И 23 и 24 подключены соответственно ко входу и выходу элемента НЕ 22, а

$o выходы — ко входу элемента ИЛИ 25, выход которого подключен к выходу блока 21.

Вторые входы элементов И 23 и 24 и вход элемента НЕ 22 соединены соответственно со входами блока 21, Ц

Работа устройства происходит следующим образом.

В цикле записи информационное слово по входу 13 поступает в информационный регистр 1, кодируется в соответствии с алго6

Пусть ячейка имеет четыре дефектных разряда, например, 1-й является генератором «1», 2-й — генератором «О», 4-й — генератором «!», 8-ой генератором «0».

10!010001110

А

А

Аз

А

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

= 0111100111!0.

В результате декодирования этого кода сумматорами 7 получим:

Группа, контролируемая А и 0 1 0 1 ошибка А — — 1

Группа, контролируемая А 1 0 0 1 ошибка А г= 1

Группа, контролируемая А з, 1 1 0 0 0 ошибка А з=

Группа, контролируемая А 1 1 1 0 ошибка А <=

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

После циклов повторной записи и чтения в регистр 2 поступает код х з = 010101110001

На выходе схемы сравнения 8 в результате сравнения кодов ха = 110100010000. Разряды этого кода, имеющие значение 1, соответствуют позициям отказавших разрядов.

С выхода схемы сравнения 8 код ха поступает на блок 9 анализа отказов, на выходе которого формируется 4-разрядный код у уаузу4..

= 1111, так как в каждой иэ контрольных групп находится только один дефектный разряд. Так, в группе, контролируемой А, дефектным является 1 -й разряд, в группе контролируемой Аг — 2-й разряд, в группе, контролируемой Аз — 4-й разряд, а в группе, контролируемой А« — 8-й разряд. В то же время каждый контролируемый разряд дает ошибку. Поэтому коррекция считанной информации осуществляется блоком 10 путем инверсии отказавших разрядов. Скорректированное информационное слово поступает на выход 12.

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

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

1. Устройство для коррекции ошибок в блоке памяти, содержащее информационный

765886 ритмом образования кода Хэмминга, через элементы И 4 и ИЛИ 6 в прямом коде поступает на выход 11 и заносится в выбранную ячейку запоминающей системы (на фиг. 1 не показана). В цикле чтения считанное информационное слово поступает в информационный регистр 1, а с его выхода— на сумматоры 7. В случае отсутствия ошибок по всем контрольным разрядам информационное слово с выхода информационного регистра 1 через блок 10 поступает на выход 12. Если искажающие информацию от- 1п казы имеют место, то по сигналам блока управления 15 осуществляется коррекция считанной информации. Для этого содержимое информационного регистра 1 через элементы НЕ 3, И 5 и ИЛИ 6 в инверсном коде поступает на выход 11 и заносится в соответствующую ячейку запоминающей системы. Затем выполняется цикл чтения с занесением считанной информации по входу

: 14 в регистр 2.

Содержимое регистров 1 и 2 сравнивается между собой на схеме сравнения 8. На выходах схемы сравнения 8 сигнал «1» появляется в тех разрядах, в которых совпадают коды регистров 1 и 2. Эти разряды запоминающей ячейки являются отказавшими и представляют собой генераторы конс- п таит (генератор «О» или генератор «1»). С выхода схемы сравнения 8 результат сравнения поступает на блок 9 анализа отказов, на выходах которого, формируются сигналы анализа отказов, на выходах которого формируются сигналы у ну а,у„. Коррекция счи3О таиной информации осуществляется в блоке 10 путем инверсии тех разрядов считанного информационного слова, в которых имеют место отказы {т. е. логические уровни сигналов на выходах схемы сравнения 8 по этим разрядам равны 1) и для которых выполняются следующие условия: отказавший разряд принадлежит i-й (1<

Работа устройства иллюстрируется следующим примером.

Допустим, необходимо записать в ячейку восьмиразрядное информационное слово х — — 11001110. В соответствии с принципом $в построения кодов Хэмминга информационное слово х дополняется четырьмя контрольными разрядами А и А2, Аз, А и на вход

11 для записи в выбранную ячейку поступает код: к а = А А l А зl ООА 41 110. Контрол ь$$ ные разряды А и.. А 4 формируются сумматорами 7 по модулю два. В рассматриваемом примере А — — 1, А а = О, Аз = О, А 4 — — О.

Следовательно, х а = 011010011110. (.1

Х регистр, регистр инверсного кода, элементы

И, HE и ИЛИ, сумматор по модулю два, схему сравнения и блок управления, причем выходы информационного регистра подключены к первым входам одних из элементов И, входам элементов НЕ, сумматоров по модулю два и первому входу схемы сравнения, второй вход которой соединен.с выходом регистра инверсного кода, выходы элементов

HE подключены к первым входам других элементов И, вторые входы элементов И соединены с одними из выходов блока управления, а выходы — со входами элементов ИЛИ, выходы которых подключены к одним из выходов устройства, выходы сумматоров по модулю два соединены с одними-из входов информационного регистра, другие входы кото-. рого и, .входы регистра инверсного кода сое- 1 диненц со входами устройства, отличающе-. еся тем, что, с целью повышения быстродействия устройства, оно содержит блок анализа отказов, вход которого подключен к выходу схемы сравнения, и логический блок; входы которого соединены соответственно с вы20 ходами блока анализа отказов, схемы сравнения, сумматоров по модулю два, информационного регистра и элементов HE.

2. Устройство по и. 1, отличающееся тем, что блок анализа отказов содержит груп- 25 пу элементов И и элементы ИЛИ, входы которых подключены к выходам элементов И соответствующих групп, входы элементов И и выходы элементов ИЛИ соединены соот6

8 ветственно со входамн и выходами блока анализа отказов, 3. Устройство по пп. 1 и 2, отличающееся тем, что логический блок содержит группы элементов И, элементы ИЛИ и блоки инверсии, прмчем выходы элементов И первой группы йодключены ко входам элементов

ИЛИ, выходы которых соединены с одними нз входов элементов И второй группы, одни из входов блоков инверсии подключены к выходам элементов HE второй группы, а выходы — к выходам логического блока, входы которого соединены со входами элементов И первой группы и другими входами элементов И второй группы и блоков инверсии.

4. Устройство по п. 3, отличающееся тем, что каждый блок инверсии содержит элементы НЕ, И и ИЛИ, причем первые входы первого и второго элементов И подключены соответственно ко входу и выходу элемента НЕ, а выходы — ко входам элемента ИЛИ, выход которого подключен к выходу блока инверсии, вторые входы элементов

И и вход элемента HE соединены соответственно со входами блока инверсии.

Источники информации, принятые во внимание при экспертизе

1. Авторское свидетельство СССР № 402870, кл. G 06 F 1!/00, 1972.

2. Авторское свидетельство СССР № 622086, кл. G !1 С 29/00, 1976 (прототип) .

7б5886 х, Xg

МЗ х

Х, xz х> ху

X)

ХЗ

М

/(Xg

АЗ

ЯЗ УЗ гт) !

Фиг. 3

Фиг. 4

Составитель В. Рудаков

Редактон О. Стенина Техред К. Шуфрич Корректор Ю. Макаренко

Заказ 648/48

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

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

I l 3035, Москва, Ж вЂ” 35, Раушскаи наб., д. 4/5

Филиал ППП <Патента, т. Ужгород, ул. Проектная, 4