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

 

Изобретение относится к вычислительной технике и может быть использовано в качестве основного запоминакидего устройства в вычислительных системах. Целью изобретения является повышение надежности устройства. Устройство содержит блок 1 памяти, первый 3 и второй 23 коммутаторы, блок 3 кодирования, блок 7 элементов И-ШМ, первый 10 и второй 21 регистры , блок И декодирования, блок 12 коррекции, блок 15 обнаружения ошибок , элемент ИЛИ 16, первый 17 и второй 18 дешифраторы и блок 27 управления , В устройстве применяется сочетание кода БЧХ, исправляющего двухкратные и обнаруживающего трехкратные ошибки, и временной избыточности, а именно метода двойного инвертирования , сводящегося к поразрядному инвертированию слова, считанного из некоторой ячейки накопителя, записи его в ту же ячейку, считыванию и инвертированию . 2 ил., 2 табл. (Л

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

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

РЕСПУБЛИК (51)4 G 11 С 29/00

ОПИСАНИЕ ИЗОБРЕТЕНИЯ, К АВТОРСКОМ,Ф СОИДЕТЕЛЬСТВУ

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

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ

2!) 4103862/24-24

22) 04.08.86 (46) 15.02.88. Бюл. М 6 (72) И. А. Дичка, Е. Ф. Колесник, К. В. Коляда и В. И. Корнейчук (53) 681.327(088.8) (56) Авторское свидетельство СССР

)! 433542, кл. G i! С 29/00, 1972.

Авторское свидетельство СССР

У 855730, кл. G 11 С 29/00, 1979. (54) ЗАПОМИНА)ОЩЕЕ УСТРОЙСТВО С КОРРЕКЦИЕЙ ОШИБОК (57) Изобретение относится к вычислительной технике и может быть использовано в качестве основного запоминающего устройства в вычислительных системах. Целью изобретения является повышение надежности устройства.,80„„13? 4286 А 1

Устройство содержит блок 1 памяти, первый 3 и второй 23 коммутаторы, блок 3 кодирования, блок 7 элементов

И-ИЛИ, первый 10 и второй 21 регистры, блок 11 декодирования, блок 12 коррекции, блок 15 обнаружения ошибок, элемент ИЛИ 16, первый 17 и второй 18 дешифраторы и блок 27 управления. В устройстве применяется сочетание кода БЧХ, исправляющего двухкратные и обнаруживающего трехкратные ошибки, и временной избыточности, а именно метода двойного инвертирования, сводящегося к поразрядному инвертированию слова, считанного иэ некоторой ячейки накопителя, записи его в ту же ячейку, считыванию и инвертированию. 2 ил., 2 табл.

1374286

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

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

На фиг. 1 изображена структурная схема запоминающего устройства с кор- 10 рекцией ошибок; на фиг. 2 - граф-схема алгоритма работы блока управления.

Устройство содержит (фиг. 1) блок

1 памяти, первый коммутатор 2, блок

3 кодирования. Вход блока 3 является 15 информационным входом 4 устройства.

Первый информационный вход 5 коммутатора 2 соединен с выходом блока 3, а выход 6 - с информационным входом блока 1 памяти. Устройство также со- 20 держит блок 7 элементов И-ИЛИ, имеющий информационный вход 8 и выход 9, первый регистр 10, блок 11 декодиро» вания, блок 12 коррекции. Второй информационный вход 13 блока подключен 25 к первому регистру 10. Выход 14 блока

11 соединен с входами блока 15 обнаружения ошибок и с входами элемента

ИЛИ 16. Устройство также содержит первый 17 и второй 18 дешифраторы, 30 одни из выходов которых обозначены на фиг. ° 1 позициями 19 и 20, второй регистр 21, имеющий выход 22, второй коммутатор .23, имеющий вход 24 и вьгход 25, соединенный с третьим инфор мационным входом 26 коммутатора 2, и блок 27 управления. Блок 27 имеет входы 28 - 33 и выходы 34 — 43.

Блок 27 управления может быть реализован в виде автомата Мили, гРаф- 40 схема алгоритма работы которого приведена на фиг. 2. На ней приняты следующие обозначения; R, (= 0,7)-состояние автомата; R — начальное о состояние автомата; У, ((= 1,11) — 45 управляющие сигналы выдаваемые автоматом; X „ (k = 1;6) - логические: условия (входные сигналы автомата);

И (1 = 1,5) — логические условия, зависящие от кратности и характера ошибок и определяемые в соответствии с табл. 1:

Б„— Х Х Х Х (.ХPфх х, 112 xххх П3 xþхххю

U4 — Х х х Ч ХЗХ4Х5ХС 1 2 3 Ф где, Х - дизъюнкция разрядов 1 - 10 синдрома $, Х, = В, (В, ч ... чВ„, получаемая на выходе элемента ИЛИ 16;

Х„. — значение нулевого разряда В, синдрома; Х, — дизъюнкция пяти старших разрядов bl кода, считываемого

1 Ю из блока 15, Х = и b . — значение

5 ji сигнала на выходе дешифратора 17;

Х - дизъюнкция пяти младших разрядов В, кода, считываемого из блока 15, 5

- г д — значение сигнала вы 1=1

J хода дешифратора 18 (выходы дешифраторов инверсны; на возбужденном выходе дешифратора имеет место нулевой сигнал, на остальных — единичные сигналы).

На основании граф-схемы (см. фиг. 2) построена структурная таблица автомата (табл. 2), которая содержит двоичные коды состояний R,. автомата, логические условия Х„, U, выходные сигналы У.. При этом условие

Х„ соответствует оигналу "Запуск", поступающему на вход 28 блока 27 из центрального устройства управления, условие Х 2 - режиму работы (PP) запись (О) или чтение (1), поступающему на вход 29 блока 27 из центрального устройства управления (на фиг ° 1 не показано).

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

6 = fl EG k lf и имеет размерность k ч и, где k — количество информационных разрядов; и— длина кодового слова (k = n — 2 m);

m — целое положительное число, определяемое из соотношения 2 = и; Е— единичная матрица размерности k x k

G — подматрица размерности k х (n—

1), строки которой представляют собой остатки от деления единицы с (К вЂ” 1) нулями на порождающий полином кода; К вЂ” столбец, равный поэлементной сумме по модулю два столбцов !

- n-1 матрицы EG, обеспечивает контроль по четности всего слова. (Порождающую матрицу G неполного кода получают из соответствующей мат!

3742

4321 0

11010001001

26... ! 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

0110100010,1

l4

00110100011

1111011100013

0111101110012

0011110111011

0 01 10000101

1 4

10110111011003

000000000000001001101101102 с

1 1

0000O0000000000I 1101101001

g(x) =х +х +х +х +

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

16"..разрядные слова, необходимо в порождающей матрице полного (3), 21) кода БЧХ (n — 1 31, К = 21, m = 5) вычеркнуть 5 верхних строк и 5 левых столбцов, в результате чего получит- IO,)-я строка подматрицы G является

j-м остатком от деления единицы с нулями на полином который является порождающим для рассматриваемого кода.

В соответствии с порождающей матрицей строят блоки 3 и 11. Блок 15 . может быть выполнен в виде ПЗУ.

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

86 4 ся порождающая матрица (26, 16) кода

БЧХ, а затем к полученной матрице присоединить справа столбец, элемен-. ты которого равны сумме по модулю два элементов соответствующих строк матрицы (26, 16) — кода БЧХ.

Для (27, 16) — кода БЧХ порождающая матрица имеет следующий вид:

11110011111

10010! 001 1 0

I 010011 101 1

1011 I 1010 0

11000010101

Для инициализации устройства на вход,28 блока 27 подается сигнал "Запуск". устройство функционирует в одном из двух режимов "Запись" нли "Чтение".

Наличие сигнала "Запись" (Х О) на входе 29 блока 27 определяет режим записи. Подлежащее записи слово с входа 4 поступает в блок 3, где кодируется в соответствии с порождающей матрицей применяемого кода.

По сигналу Y = 1 (выход 34 блока 27 и по сигналам У1 (37) = I (" Выборка

74286 6 ние информации. Затем по сигналу Y

10

30 ся восстановление содержимого ячейки блока 1 памяти.

Если и в первом и во втором циклах чтения слово содержит ошибку кратности три и более (114 = 1), то блок 27 выдает на выход 44 сигнал

"Ошибка". Кроме того, если в процес4О се декодирования информации на входы

30-33 блока 27 поступает код Х Х,Х,Х отсутствующий в табл. 1 (при этом выполняется логическое условие Uz = l) то независимо от цикла чтения инфор4 мации (первой или второй) на выход 45 блока 27 выдается сигнал "Неисправность декодера".

5 l3 кристалла") и У .(38) = 9 (" Запись" ) слово записывается s блок 1 памяти.

Поступление на вход 29 блока 27 сигнала "Чтение" (Х, 1) определяет режим чтения. Блок 27 выдает с выходов 37 и 38 сигналы Х, = 1 и Х = 1, которые поступают на управляющие входы блока 1. При этом на выходе 39 блока 27 сигнал Y = 9. В соответствии с этими сигналами считываемое из блока 1 слово поступает в регистр

10 и блоки 11 и 12. Результатом работы блока 11 является значение $ синдрома и разряда S, = В,. Значение

В, поступает на вход 30 блока 27.

Значение $ поступает на вход блока

1S а также через элемент ИЛИ 16на вход 31 блока 27. Считанные по адресу S номера (их двоичные значения) искаженных разрядов из блока

15 поступают на дешифраторы 17 и 18.

При этом значения сигналов на нулевых выходах дешнфраторов 17 и 18 поступают на входы 33 и 32 блока 27 соответственно.

Если считанное слово не содержит ошибок, To HG сигналу Y = 1 с sbIKG да 41 блока 27, поступающему иа управляющий вход коммутатора 23, содержимое блока 12 поступает на выход

25 устройства.

Если считанное слово содержит однократную ошибку в разряде С,, то по сигналу Y = 1 с выхода 42 блока 27 в блоке 12 производится коррекция содержимого разряда С, и информация по сигналу Y = 1 (выход 41 блока 27 через коммутатор 23 поступает на выход 25. Если S ф О, то считанный

IIo адресу $ код (из блока 15), ле» вая Ь, -и нравая Ь половины которого представляют собой коды двух номеров искаженных разрядов, дешифрируется дешифраторами 17 и 18, вследствие чего в блоке 12 производится коррекция двух разрядов считанного слова (или одиого разряда), если один из номеров Ь; или Ъ равен нулю.

Если в считанном слове имеется двукратная ошибка или ошибка более высокой кратности, то по сигналу

У = l (выход 40 блока 27) содержимое блока 12 запоминается в регистре

21, а содержимое регистра 10, поступая в коммутатор 2, по сигналу Y = 1 5 (выход 36 блока 27) инвертируется и записывается в блок 1 по тому же адресу, по которому производилось чте1 (выход 38 блока 27) производится чтение содержимого той же ячейки накопителя, которое по сигналу Y = 1 (выход 39 блока 27) инвертируется и поступает в регистр 10 и блоки ll u

12. Вновь считанное слово корректируется по описанному выше алгоритму.

Если вновь считанное слово не со» держит ошибок или содержит однократную ошибку, то содержимое блока 12 выдается на выход 25, а также по сигналу Y = 1 (выход 35 блока 27), поступающему на соответствующий управляющий вход коммутатора 2, записывается в блок 1 памяти с целью восстановления информации в ячейке.

При наличии в слове двукратной ошибки на выход 25 выдается содержимое регистра 21, которое поступает через коммутатор 23 по сигналу У „

1 с выхода 43 блока 27. Если вновь считанное слово содержит ошибку кратности три и более (U< = 1) ° то в первом цикле чтения информации из накопителя оно содержало двукратную ошибку (11 = 1), то информация на вход

25 также выдается из регистра 21

Следует заметить, что во втором цикле чтения при выдаче информации из блока 12 или регистра 21 производит .

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

Запоминающее устройство с коррекцией ошибок, содержащее блок памяти, блок кодирования, блок декодирования, первый и второй регистры, блок обнаружения ошибок, блок коррекции, эле- . мент ИЛИ и блок управления, иричем вход блока кодирования является информационным входом устройства, адресным входом которого является ад1374286

Таблица 1

U„

0 Ошибок нет

1 Однократная ошибка

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

1 Двукратная ошибка

0 Трехкратная ошибка (или обнаруживаемая ошибка кратности 5,7,9,...)

0 Обнаруживаемая ошибка кратности

4,6,8,...

Неисправность дево е а

Остальные комбина и ресный вход блока памяти, выход блока коррекции подключен к информационному входу второго регистра, управляющий вход которого соединен с первым выходом блока управления, вход запуска блока управления является входом обращения устройства, вход управления режимом блока управления является входом чтения-записи устройства, вход анализа нулевого разряда синдрома блока управления подключен к выходу блока декодирования, вход анализа разрядов синдрома с.первого по десятый блока управле- 15 ния соединен, с выходом элемента ИЛИ, выходы элемента ИЛИ и входы блока обнаружения ошибок соединены поразряд но и подключены к группе выходов блока декодирования, второй и третий 20 выходы блока управления соединены соответственно с входом выборки и входом чтения-записи блока памяти, о т л и ч а ю щ е е с я тем, что, с целью повышения надежности устрой- 25 ства, в него введены первый и второй коммутаторы, блок элементов И-ИЛИ, первый и второй дешифраторы ошибок, причем первый, второй и третий информационные входы первого коммутато- З0 ра подключены соответственно к выходу-блока кодирования, выходу первого регистра и выходу второго коммутатора, выход первого коммутатора подклю чен к информационному входу блока па- З мяти, информационные входы второго коммутатора соединены соответственно . с выходом блока коррекции и выходом второго регистра, выход второго ком мутатора является информационным выходом устройства, информационные входы блока элементов И-ИЛИ подключены к выходам блока памяти, выходы блока элементов И-ИЛИ соединены с входами первого регистра н входами блока декодирования, выходы блока обнаружения ошибок подключены к входам соответствующих дешифраторов ошибок, первый вход признака ошибки блока управления подключен к первому выходу первого дешифратора,ошибок, второй вход признака ошибки блока управления соединен с первым выходом второго дешифратора ошибок, информационные входы блока коррекции подключены соответственно к вторым выходам дешифраторов ошибок и выходам блока элементов И-ИЛИ, четвертый, пятый и шестой выходы блока управления соединены соответственно с первым, вторым и третьим управляющими входами первого коммутатора, седьмой выход блока управления подключен к управляющему входу блока элементов И-ИЛИ, восьмой и девятый выходы блока управления соединены соответственно с первым управляющим входом второго коммутатора и управляющим входом бло ка коррекции, десятый выход блока управления подключен к второму управляющему входу второго коммутатора, одиннадцатый и двенадцатый выходы блока управления являются соответственно выходом Неисправимая ошибка" и выходом "Ошибка декодирования" устрой ства.

1 374286

Таблица 2

В 000 Х,Х, У е Уз

Y1 ° У, 0Ol

l0l

R% 101 01

Вз l l l 03

В, 100 Ui

R1 у

У1 Уь ° Ут

R . .000 И, а < 000

R 011

Re 1 l0 I

101

У» Y1ВУ1 у„у,„у, ъу»

"з

БЬ 000 U!

Y1»%9 YN

Нф 000 . U

0к

Rт О!О U, В, 010 U, з

1 10

Кр

000 0

Хл

Нф 000 ,010 U, R, 010 0

В 010

000 ь

Р Ф

Знамени« Y j(i 1 l l ) соответствует следующим сигналам . блока 27:

У (аыкод 37 блока 27) выборка кристалла; (38) - икание (Y 1) /запись (Y О) информация из блока 1 памяти!

Мз (34) нрокоцдение информации с блока 3!

Ъ (42) коррекции нулевого разркда считываемого слона! х, (41) - яро«окна«не информации иа ияну 25 данных с блока !2!

>с (36) - црокоищение информации с регистра 101

У (40) . «aga sa регистр 21;

Уа (Зр) инрертнроаание сеитыэаамой ияформацян нз блока 1 памяти!

Yq (35) нрокащеине информации с ныкода коммутатора 23; л0инбква

У> (43) арене@двине информация на инну 25 с даиаак регистра 211 (4й !ac!a%a cjasaaa лНеисараа) ость Фи«одера".

1 374286