Запоминающее устройство с коррекцией модульных ошибок

 

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

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

РЕСПУБЛИК

„„SU „„1633461 (51)5 G 11 С 29/00

А1

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

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

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

ПО ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМ

ПРИ ГКНТ СССР (21) 4664599/24 (22) 23.03.89 (46) 07.0З.9!. Б .. ¹ 9 (72) В. И. Николаев и С. A. Чучак (53) 681.327 6 (088.8) (56) Й а те нт С Ш Л ¹:3573728 кл. 340 — 146 1, 1971.

Авторское свидетельство С(CP № 1262576, кл. G !1 С 29/00, 1985. (54 ) В АИОМ И НЛЮ1ЦЕ Е УСТРОЙ СТВО С

КОРРЕКЦИЕЙ МОДУЛЬНЫХ ОШИБОК (57) Изобретение относится к вычислительной технике и может быть использовано для повышения надежности запоминающих устройств, выполненных на интегральных микросхемах Целью изобретения

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

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

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

Устройство содержит блоки 1 — I н> памяти, образующие накопитель с адресными входачи 2, входами 3 записи, входами 4 считывания, информационными входами 5 и информационнычи выходами 6, входами 7 и выявляется повышение надежности устройства

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

«все единицы». Дополнительно обнаруживаются ошибки любой кратности в пределах модуля. 4 табл., 6 ил. ходами 8 контрольных разрядов первой группы, входами 9 и выходами 10 контрольных разрядов второй группы, входами 11 и выходами 12 контрольных разрядов третьей группы, входной 13 и выходной 14 формирователи сумм номеров единичных байтов, входной 15 и выходной 16 формировател и сум м номеров нулевых байтов, формирователь 17 поразрядной суммы байгов, первый 18 и второй 19 блоки обнаружения ошибок, формирователь 20 номера искаженного байта, дешифратор 21, блок 22 коррекции ошибок, третий блок 23 обнаружения ошибок. информационные выходы 24 устройства, первый 25, второй 26 и третий 27 контрольные выходы устройства.

Входной 13 и выходной 14 формирователи сумм номеров единичных байтов (фиг. 2) содержат первую 28, вторую 29. третью 30 группы элементов И. группу элементов И вЂ” НЕ 31, первую 32 и вторую 33

163346

1 к к

Таблица

Д Е Ж 3 К в в г к к к о о о о о о о о о î о о о о o о ! о о о о о о ! о о о о о

O 1 O O O Î 1 O O о o o o

1 O QО О 0 1 о о э о о о о о ! о о о э

О О Î O ! 1 С О о о

1 О О О 1 о o о

O 1 О О O о ! о о о о о

1 1 О 1 1 1 0

1 1

o o о

1 1 О

Формирователь 20 номера искаженного байта (фиг. 4) содержит первую 51, вторую 52 группы элементов НЕ, первый 53 и второй 54 элементы И, группу элементов И 55, группу элементов ИЛИ 56, первый 57 и второй 58 элементы ИЛИ вЂ , первые 59, вторые 60, третьи 61 и четвертые 62 входы.

Выход А первой группы элементов И 28 используется для формирования семафорных разрядов.

Входной 15 и выходной 16 формирователи сумм номеров нулевых байтов аналогичны входному 13 и выходному 4 формирователям сумм номеров единичных байтов (фиг. 2) . Ha входы входного 15 и выходного 16 формирователей сумм номеров нулевых байтов подаются обратные коды информационных слов.

Первый 18 и второй 19 блоки обна ружения ошибок (фиг. 3) содержат сумматоры 39 — 42 по модулю два, первый 43, второй 44 и третий 45 элементы ИЛИ, первый 46, второй 47 элементы И, выходную группу элементов И 48, контрольные 45 выходы 49 и информационные выходы 50

Комбинационная схема, построенная на первом 43, втором 44, третьем 45 элементах

ИЛИ, первом 46 и втором 47 элементах И, формирует сигналы на контрольных выходах

49 в соответствии с табл. 2. 50

Т а б л и ц а

Ошибок нет 55

Неисправимая ошибка

Исправимая ошибка

3 группы элементов ИЛИ, первый 34 и второй 35 шифраторы, сумматор 36 по модулю два, семафорный выход 37, информационный выход 38. Порядок соединения выходов первой группы элементов И 28, группы элементов И вЂ” НЕ 31 с входами второй 29 и,Т

ИЛИ 45 И III ч4 Значение сигнала!

4 третьей 30 группами элементов И определяется табл. 1, где обозначены выходы

А, Б, В, Г, Д, Е, Ж, 3 первой 28 группы элементов И, выходы К! — Ка первого

34 шифратора и выходы К! — К6 второго 35 шифратора.

Бло к корре к ци и о ш и бок (фи г. 5) соде ржит первую 63, вторую 64, третью 65 группы элементов И, группу элементов ИЛИ 66, первую 67 и вторую 68 группы элементов

НЕ, выходной сумматор 69 для поразрядного сложения байтов, коммутирующие входы 70. Коммутирующие входы 70 на первую 67, вторую 68 группы элементов НЕ и третью 65 группу элементов И поступают от дешифратора 21.

Входной формирователь 17 и выходной сумматор 69 для поразрядного сложения байтов построены на сумматорах по модулю два.

Третий блок 23 обнаружения ошибок (фиг. 6) содержит группу сумматоров 71 по модулю два, элемент ИЛИ вЂ” НЕ 72, первый 73, второй 74 и третий 75 элементы И, элемент ИЛИ 76.

Значения входных шин третьего 23 блока обнаружения ошибок представлены в табл. 3.

1633461

Т а б л и ц а 3

49-19

49-18

6 (О) Вых.69

7О(0) Т а б л и ц а 4 г

Значение сигнала

Номер Сигнал выхода

Байтовая ошибка в первом контрольном байте.

1,2,3,4,5,6 или кратная ошибка

Обозначение Откуда считываются знавиода чения

С контрольных выходов

49 второго 19 блока обнаружения ошибок

С KQHTpoльных выходов

49 первого 18 блока обнаружения ошибок

С нулевого по номеру байта информационного выхода 6

С выхода сумматора 69

С нулевого по номеру из коммутирующих входов 70

Выходы 25 и 26 третьего блока 23 обнаружения ошибок являются первым 25 и вторым 26 контрольными выходами устройства.

Сигналы на выходах 25 и 26 формируются в соответствии с табл. 4.

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

111111! 1 содержится в байте с номером

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

Для хранения контрольных разрядов потребуется два байта: один байт контрольных разрядов используется для хранения поразрядной суммы байтов информационного слова; второй байт — для хранения суммы номеров байтов, код которых состоит из единиц (три разряда), суммы номеров байтов, код которых состоит из нулей (три разряда), а также для хра10

55 нения двух контрольных разрядов, указавших на наличие в байте с номером 000 кодов 00000000 или 11111111.

При записи информационного слова в блоки l i — 18 памяти формируются поразрядная сумма байтов информационного слова и суммы номеров единичных и нулевых байтов, которые записываются в блоки Iq ——

Iio памяти.

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

Если, например, в результате отказа из блоков I i — 1 вместо записанного байта информационного слова считывается константа

I I 1111!!, то на выходе первого 18 блока обнаружения ошибок формируется номер этого байта.

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

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

При записи коды чисел по входам 5 поступают на информационные входы блоков

l i — I> и на входы формирователей 13, 15 и 17, формирование контрольных разрядов Ki — К; в формирователях 13 и 15 происходит в соответствии с табл. 1, которая указывает последовательность получения контрольных разрядов Ki — К,- в режимах записи и считывания.

Например, если в единичном состоянии на ходится только нулевой, второй и пятый байты информационных разрядов, т. е. их состояние соответствует коду 11111111, то на выходе первой группы элементов И 28 формируется код 10010100, на выходе группы элементов И НЕ 31 формируется код

01101011 (фиг. 2). В результате этого на выходе первого шифратора 34 формируются сигналы Ki — Кз, код которых 011, и на выходе второго шифратора 35 формируются сигналы )х — К6, код которых 101. Эти контрольные разряды К вЂ” К и К вЂ” К6 складываются по модулю два в сумматоре 36, на информационном 38 выходе которого формируется сумма номеров единичных байтов 110. Единичное состояние семафорного выхода 37 сигнализирует об едичничном состоянии байта с номером 000.

Ааналогична работа формирователя 15 суммы номеров нулевых байтов, если один или несколько байтов информационных раз1633461

7 рядов находятся в состоянии 00000000.

Результат формирователя 17, который производит поразрядное суммирование байтов входных информационных разрядов, записывается в один из блоков 19 — 1)<) памяти для

5 хранения контрольных разрядов.

При считывании информационные разряды из блоков 1) 1н поступают íà входь( формирователей 14 и 16 и на вход блока 22 коррекции ошибок. Функционирование формирователей 14 и 16 аналогично работе формирователей 13 и 15 соответственно.

Сформированные при считывании в формирователях 14 и 16 суммы номеров единичных и нулевых байтов и суммы номеров единичных и нулевых байтов, сформированные при записи и хранящиеся в блоках

1<) 1)<) памяти, поступают Hd входы первого 18 и второго 19 блоков обнаружения ошибок. Вместе с суммами номеров и единичных байтов на входы первого 18 и второго 19 блоков обнаружения ошибок поступают семафорны<. разряды из формировате)ей 14 и 16 и из блоков 1<) — 1)<) памяти. В резульгате поразрядного сложения на сумматорах 40 — 42 по модулю два (фиг. 3) на информационных выходах 50 появляется чис I<)B<)H код номера )к исправного байта. Единичное значение сигнала на выходе суммагора 3!) по молулю лва сигнализирует о неисправности байта с нулевым номером.

Состояние контр<) II IIblx выходов 49 сигна.(изирует о наличии (отсутствии) исправимых (неисправимых) ошибок в считаннь(х из блоков l l 1н информационных разрядах.

8

Если это условие не выполняется, то на выходе элемента ИЛИ вЂ” НЕ 58 появляется единичный сигнал на контрольном выходе 25, который сигнализирует о неисправимой ошибке.

С выходов формирователя 20 код искаженного байта поступает на входы дешифратора 21, который преобразует его в унитарный.

Единичный сигнал, поступивший с выхода дешифратора 21 на один из входов 70 (фиг. 5), запрещает выдачу искаженного байта информационных разрядов через первую 63 группу элементов И в выходной суммгтор 69 и через вторую 64 группу элементов И на вход группы элементов

ИЛИ 66, выходы которой являются информационными выходами 24 устройства. Этот же единичный сигнал разрешает выдачу исправленного байта информационных разрядов на вход группы элементов ИЛИ 66 и далее на информационные вь(холы 24 устройства. Исправление байта осх (цествляется в выходном сумматоре 69 путем поразрядного сложения байтов информационных разрядов, поступивших с выходов первой 63 группы элементов И, и поразрядной суммы байтов, полученной в формирователе 17 и поступающей из блоког

1<)- l l)) памяти по первым 8 контрольных выходам. На выходе сумматора 69 сфор мируется скорректированный байт информационного слова. Таким образом происходит коррекция пакетных ошибок.

Пусть, например, на информ; ) цнонные входы 5 блоков 1)- !q памяги посту((а<т ) <)il числа.

С выхолов блоков 18 и 19 коды номеров искаженных байтов на выходах 50 и информационных выходах контрольных curIIà 1<)B 49 поступают Н3 входы формирователя 20 номера искаженного байта (фиг. 4)

Контрольные разряды с выхода блока 19 обнаружения ошибок поступают на первые 40 вхолы 59, контрольные разряды с выхода блока 18 обнаружения ошибок поступают на вторые входы 60. Коды номеров неисправных байтов с выхода блока 19 обнаружения ошибок поступают на третьи входы 61 45 а коды номеров неисправных байтов с выхода блока 18 обнаружения ошибок на четвертые входы 62. На выходе формирователя 20 номера искаженного байта появляется код номера искаженного байта в том случае, если выполняется условие: 50

/00),, Р, 1!) /\// 11)н ЛОО)н/, 00) н гле числовой кол контрольного выхода

11))) блока 18 обнаружения ошибок;

00I> j числовой код контрольного выхода

11)>3 блока 19 обнаружения ошибок.

11111111 0010;101 О((ОООООО 11110! гО

010000)0. 111111!1. 10101100. !1001011

Тогда во входном формирователе !3 сумм номеров единичных байтов (фиг 2) на выходах первой группы элементов И 28 и на выходах группы элементов И HE 3! формируются восьмиразрялные коды

10000100 и 01111011 соответственно На аналогичных выходах групп элементов во входном формирователе 15 сумм номеров нулевых байтов формируются коды 00100000 и 110111111. Поэтому в формирователе 13 на выходе первого шифратора 34 формируется код 000, на выходе второго шифратора 35 формируется код 101 (табл. 1). Следовательно, на информационном выходе 38 формируется кол 101, который представляет собой сумму номеров единичных байтов записываемого шестидесятичетырех разрядного информационного слова, а семафорный выход 37 находится в единичном состоянии, что сигнализирует о наличии в байте с номером 000 кода 11111111.

В формирователе 15 на выходе первого шифратора 34 формируется код 010, на выходе второго 35 шифратора формирует1633461

11111111

00101101

010000!0

1 1 1 1 1 1 1 1

11001011

О-й байт (ООО)

2-й байт (010)

3-й байт (011)

4-й байт (IОО)

5-й байт (101)

6-й байт (110)

7-й байт (111)

Поразрядная сумма байтов

Исправленный байт с номером 001.

11111111

11111111

11001011

llllll0O

55

O0101OOI

9 ся код 000, следовательно, на информационном выходе 38 формируется код 010. а семафорный 37 выход находится в нулевом состоянии.

В формирователе 17 производится поразрядное сложение байтов информационного слова

0-й байт (000)

1-й байт (001)

2-й байт (010)

3-й байт (011)

4-й байт (100)

5-й байт (101)

6-й байт (110)

7-й байт (111)

lllll100 Поразрядная сумма байтов

Таким образом, в контрольные блоки 19

Iip памяти будут записаны: код 11111100 поразрядной суммы байтов; код 1101, где первый разряд синнализирует о наличии в байте с номером 000 кода 11111111, а следующие три разряда — сумма номеров единичных байтов; код 0010, где первый разряд сигнализирует об отсутствии в байте с номером 000 кода 00000000, а следующие три разряда представляют сумму номеров нулевых байтов.

Пусть, например, в результате отказа второго блока памяти из блоков в 1 считывается следующее информационное слово:

llllllll. llllllll. 00000000. 11110100.

01000010. 1lllllll. 10101100. 110OlOll.

Это информационное слово поступает на выходные блоки формирователя 4 суммы номеров единичных байтов и формирователя

l6 сумм номеров нулевых байтов. С выхода формирователя 14 на один из входов первого блока 18 обнаружения ошибок поступит код 1100, где 2, 3, 4 разряды — поразрядная сумма номеров единичных байтов. С выхода формирователя 16 на один из входов второго блока 19 обнаружения ошибок поступит вновь сформированный код 0010.

На вторые входы блоков 18 и 19 по шинам 12 и 10, соответственно, поступят сформированные при записи информационного слова контрольные коды: на блок 18— код 1101, на блок 19 — код 0010 (фиг. 1).

В результате слажения по модулю два в блоке 18 сформируется номер искаженного байта 001:! 101

[phone], который поступит на информационные выходы 50 блока 18 и контрольные разряды с кодом 11. Эти контрольные разряды разрешат выдачу номера искаженного байта на информационные выходы

50 (фиг. 3). В результате функционирования второго блока 19 обнаружения ошибок

10 вырабатываются коды: на выходе 50 — 000, на выходе 49 — 00,0010

+00!0

00()().

Коды с выходов первого 18 и второго 19 блоков обнаружения ошибок поступают на входы формирователя 20 номера искаженного байта. Код 00 с контрольного в хода

49 блока 19 поступает на первые 59 входы формирователя 20 номера искаь нного байта, код I с контрольного выхода 49 блока 18 поступает на вторые 60 входы формирователя 20, код 000 с информационного 50 выхода блока 19 на третьи входы 61 формирователя 20 и код 001 с выхода 50 блока 18 на четвертые 62 входы формирователя 20. В результате этого на выходе первого 53 элемента И формируется сигнал единицы, который разрешает выдачу через группу элементов И 55 и далее через группу элементов ИЛИ 56 на дешифратор 21 кода OOI искаженного байта. Одновременно на контрольном выходе 27 устройства формируется нулевой бит, сигнализирующий об отсутствии неисправной ошибки в считанном слове.

Код 001 после дешифрации преобразуется в унитарный код 01000000, который поступает на коммутирующие входы 70 блока

22 коррекции (фиг. 5). Единичный разряд унитарного кода запрещает выдачу через первую группу элементов И 63 на выходной сумматор 69 и через вторую группу элементов И 64, группу элементов ИЛИ 66 на выход 24 устройства искаженного байта с номером OOI. В выходном 69 сумматоре формируется искаженный байт информационного слова, который по разрешающему единичному сигналу унитарного кода через третью группу элементов И 65. через группу элементов ИЛИ 66 поступит на выход 24 устройства на место заблокированного байта с номером 001.

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

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

1ч 1п памяти на выход 8:

1633461

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

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

)8 и 19 обнаружения выдают сигнал 00, в третьем блоке 23 обнаружения ошибок (фиг. 6), в группе 71 сумматоров по модулю два производится поразрядное сравнение нулевых по номеру байтов; считанного из блока 1 памяти и сформированного на выходе сумматора 69 (фиг. 5) .

По результатам этого сравнения формируются контрольные разряды 25 и 26 (фиг. 6) .

Если не совпали все 8 разрядов, значит байтовая ошибка в контрольных разряда х (в поразрядной сумме байтов) или информационном слове. 1 — 7 несовпадений на выходе группы сумматоров 71 по модулю два указывает на наличие 1 7 кратных ошибок.

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

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

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

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

Фиг. Г

1633461

61

1633461

Составитель Ю. Сычев

Редактор С. Патрушева Техред А. Кравчук Корректор О. Кравцова

Заказ 620 Тираж 347 Подписное

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

113035, Москва, Ж вЂ” 35, Рау шская наб., a 4/5

Производственно-издательский комбинат <Патент», г. Ужгород, ул. Гагарина, 101