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

1

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

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

13742862

где.Х - дизъюнкция разрядов 1-10 синдрома S, Xj В , vB V . . . v В-.р , псшучаемая на выходе элемента ИЛИ 16; Х. - значение нулевого разряда В, синдрома; Xj - дизъюнкция пяти стар- ншх разрядов bj кода, считываемого

из блока 15, X, V Ъ . - значение

из блока 15, X, V Ъ . - значение

:1

На фиг. 1 изображена структурная

схема запоминающего устройства с кор- игнала на выходе дешифратора 17; оекпиеи mrmfimct ня Лиг. V - rnaih-fxf- ,.

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

X,

V Ъ . - значение сигнала выi.-i i . .

хода дешифратора 18 (выходы дешифраторов инверсны; на возбужденном выходе дешифратора имеет место нулевой сигнал, на остальных - единичные сигрекцией ошибок; на фиг. 2 - граф-схема алгоритма работы блока управления. Устройство содержит (фиг. 1) блок

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

3 кодирования. Вход блока 3 является t5 информационным входом 4 устройства. Первьш информационный вход 5 коммутатора 2 соединен с выходом блока 3, а выход 6 - с информационным входом блока 1 памяти. Устройство также со- 20 налы), держит блок 7 элементов И-ИЛИ, имеющий информационный вход 8 и выход 9, На основании граф-схемы (см. первый регистр 10, блок 11 декодиро- Фиг. 2) построена структурная табли- вания, блок 12 коррекции. Второй ин- Ца автомата (табл. 2), которая содер- формационный вход 13 блока подключен 25 -жит двоичные коды состояний R авто- к первому регистру 10. Выход 14 блока мата, логические условия Х, U, выIIсоединен с входами блока 15 обна- ходные сигналы YJ. При этом условие

Х соответствует сигналу Запуск, поступающему на вход 28 блока 27 из 30 центрального устройства управления, условие Х - режиму работы-(РР) - запись (0) ИЛИ чтение (1), поступающему на вход 29 блока 27 из центрального у стройства управления (на фиг. 1

ход 25, соединенный с третьим инфор- js показано), мационным входом 26 коммутатора 2, и В устройстве используется мод ифи- блок 27 управления. Блок 27 имеет цированный код БЧХ (с дополнительной входы 28 - 33 и выходы 34-43. проверкой на четность всего слова).

Блок 27 управления цожет быть рва- исправляющий двукратные ошибки. Поро- лизован в виде автомата Мили, граф- 40 матрица такого кода представляется в виде

G II EG k 11

ружения ошибок и с входами элемента ИЛИ 16. Устройство также содержит первый 17 и второй 18 дешифраторы, одни из выходов которых обозначены на фиг. 1 позициями 19 и 20, вторрй регистр 21, имеющий выход 22, второй коммутатор .23, имеющий вход 24 и высхема алгоритма работы которого приведена на фиг. 2. На ней приняты

следующие обозначения: R, (i 0,7)- состояние автомата; R - начальное

и имеет размерность k i: п, где k - косостояние автомата; У, (j 1,11) - 45 ичество информационных разрядов; п- управляющие сигналы, вьщаваемые ав- длина кодового слова (k п - 2 т);

m - целое положительное число, определяемое из соотношения 2 п; Е - единичная матрица размерности k х k; G - подматрица размерности k х (п - k - 1), строки которой представляют собой остатки от деления единицы с (к - 1) нулями на порождающий полином кода; К - столбец, равный поэле- с, ментной сумме по модулю два столбцов 1 - п-1 матрицы EG , обеспечивает

томатом; X , (k Ii6) - логические условия (входные сигналы автомата); Uj (l 1,5) - логические условия, зависящие от кратности и характера ошибок и определяемые в соответствии с табл. 1:

и, .XyXt,

U4 Х,Х, УЗ Х,Х,,,

и, XjXjX V X,X,XjX,

Us и. ,

50

контроль по четности всего слова.

Порождающую матрицу G неполного кода получают из соответствующей матиз блока 15, X, V Ъ . - значение

:1

дов В кода, считываемого из блока 15,

X,

V Ъ . - значение сигнала выi.-i i . .

налы), На основании граф-схемы (см. Фиг. 2) построена структурная табли- Ца автомата (табл. 2), которая содер- -жит двоичные коды состояний R авто- мата, логические условия Х, U, выхода дешифратора 18 (выходы дешифраторов инверсны; на возбужденном выходе дешифратора имеет место нулевой сигнал, на остальных - единичные сигналы), На основании граф-схемы (см. Фиг. 2) построена структурная табли- Ца автомата (табл. 2), которая содер- -жит двоичные коды состояний R авто- мата, логические условия Х, U, выконтроль по четности всего слова.

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

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

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

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

16-разрядные слоёа, необходимо в по-два элементов соответствующих строк

рождающей матрице полного (31, 21) -матрицы (26, 16) - кода БЧХ.

кода БЧХ (п - 1 31, К 21, m 5)

вычеркнуть 5 верхних строк и 5 левых Дпя (27, 16) - кода БЧХ порождаюстолбцов, в результате чего получит- матрица имеет следующий ввд

1 000000000000000

G

1

1 о 1 о

00000000010 0000000000 i

j-я строка подматрицы G является J-M остатком от деления единицы с нулями на полином

g(x) х + х + х« + х + + х + х + 1,

который является порождакицим для рассматриваемого кода.

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

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

... 4 3 2 1 1101000100

0Г 1 О 1 О О О 1 О 0011010001 1111011100

01 1 1 1 о 1 i I о

0011110111 1111001111

1о о I о I о о 1 1

1010011 101

1о 1 I 1 I I о 1 о

о 1 о 1 1 I I 1 о I

1 100001010 01 10000101 1101110110

о 1 I о 1 1 I о I 1

I о 1 1 о 1 о о 1

0

5

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

Устройство функционирует в одном из двух режимов: Запись или Чтение.

Наличие сигнала Запись (Х - 0) на входе 29 блока 27 определяет режим записи. Подлежащее записи слово с входа 4 поступает в блок 3, где кодируется в соответствии с порождающей матрицей применяемого кода. По сигналу Y, I (выход 34 блока 27 и по сигналам YT (37) I (Выборка

кристалла) и Y. -(38) 0 (Запись) слово записывается в блок 1 памяти. Поступление на вход 29 блока 27 сигнала Чтение (Х. 1) определяет режим чтения. Блок 27 выдает с выходов 37 и 38 сигналы Y 1 и Y 1,

которые поступают на управляющие входы блока 1. При этом на выходе 39 блока 27 сигнал Yj 0. В соответствии с этими сигналами считываемое из блока 1 слово поступает в регистр 10 и блоки 11 и 12. Результатом работы блока 11 является значение Б синдрома и разряда S В. Значение Вр поступает на вход 30 блока 27. Значение S поступает на вход блока 15, а также через элемент ШМ 16 - на вход 31 блока 27. Считанные по адресу S номера (их двоичш 1е значения) искаженных разрядов.из блока 15 поступают на дешифраторы 17 и 18. При этом значения сигналов на нулевых выходах дешифраторов 17 и 18 поступают на входы 33 и 32 блока 27 соответственно.

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

Если считанное слово содержит однократную ошибку в разряде Со, то по сигналу Yф 1 с выхода 42 блока 27 в блоке 12 производится коррекция содержимого разряда С и информация по сигналу YS 1 (выход 41 блока 27 через коммутатор 23 поступает на выход 25. Если S 7 О, то считанный по адресу Б код (из блока 15), левая Ъ и правая Ъ половины которого представляют собой коды двух номеров искаженных разрядов, дешифрируется дешифраторами 17 и 18, вследствие чего в блоке 12 производится коррекция двух разрядов считанного слова (или одного разряда), если одни из номеров Ь| или Ъ равен нулю.

Если в считанном слове имеется двукратная ошибка или ошибка более высокой кратности, то по сигналу Y-, 1 (выход 40 блока 27) содержимое блока 12 запоминается в регистре 21, а содержимое регистра 10, поступая в коммутатор 2, по сигналу Yg 1 (выход 36 блока 27) инвертируется и записывается в блок 1 по тому же адресу, по которому производилось чте15

20

25

13742866

ние информации. Затем по сигналу Y 1 (выход 38 блока 27) производится чтение содержимого той же ячейки накопителя, которое по сигналу Y 1 (выход 39 блока 27) инвертируется и поступает в регистр 10 и блоки 11 и 12. Вновь считанное слово корректируется по описанному выше алгоритму. (О Если вновь считанное слово не содержит ошибок или содержит однократную ошибку, то содержимое блока 12 видается на выход 25, а также по сигналу YJ I (выход 35 блока 27), поступающему на соответствующий управляющий вход коммутатора 2, записывается в блок памяти с целыо восстановления информации в ячейке.

При наличии в слове двукратной ошибки на выход 25 вьщается содержимое регистра 21, которое поступает через коммутатор 23 по сигналу Y:,, 1 с выхода 43 блока 27. Если вновь считанное слово содержит ошибку кратности три и более (И О то в первом цикле чтения информации из накопителя оно содержало двукратную ошибку (Uj 1), то информация на вход 25 также выдается из регистра 21. Следует заметить, что во втором цикле чтения при выдаче информации из блока 12 шш регистра 21 производйт-г ся восстановление содержимого ячейки блока I памяти.

Если ив первом и во втором циклах чтения слово содержит ошибку кратности три и более (U4 О то блок 27 выдает на выход 44 сигнал Ошибка. Кроме того, если в процессе декодирования информации на входы 30-33 блока 27 поступает код отсутствующий в табл. 1 (при этом выполняется логическое условие Uy 1), то независимо от цикла чтения информации (первой или второй) на выход 45 блока 27 выдается сигнал Неисправность декодера.

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

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

30

35

40

45

50

55

ресный вход блока памяти, выход блока коррекции подключен к информационному входу второго регистра, управляющий вход которого соединен с первым выходом блока управления, вход запуска блока управления является входом обращения устройства, вход управления режимом блока управления является входом чтения-записи устройства вход анализа нулевого разряда синдрома блока управления подключен к выходу блока декодирова- :ния, вход анализа разрядов синдрома с.первого по десятый блока управле- кия соединен.с выходом элемента ИЛИ, выходы элемента ИЛИ и входы блока обнаружения ошибок соединены поразрядно и подключены к группе выходов блока декодирования, второй и третий выходы блока управления соединены соответственно с входом выборки и входом чтения-записи блока памяти, отличающееся тем, что, с цепью повышения надежности устрой- ства, в него введены и второй коммутаторы, блок элементов И-ИШ, первый и второй дешифрато ш ошибок, причем первый, второй и третий информационные входы первого коммутато- ра подключены соответственно к выходу блока кодирования, выходу первого регистра и выходу второго кс«ммутато- ра, выход первого коммутатора подклнг чен к информационному входу блока па- мяти, информационные входы второго коммутатора соединены соответственно с выходом блока коррекции и выходом второго регистра, выход второго комI О

1 1

О

1

1 о

о о

1 о

1 о

1 о

1

Ошибок нет

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

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

Остальные комбинации

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

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

1

О Обнаруживаемая ошибка кратности 4,6,8,...

jIeHcnpaBHOCTb декодера

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

Таблица I

. Ш,

и. и.

4

LlL

000

001

R,

Rf R, R

R

101

III

too on

R«.

«0

R, .Ri

R. R«

R#

R.

RI R

Эяачвпн Yj(i 1 « П) соответствует следующим сигналам блока 27s

Y(выход 37 влока 27) - выборка кристалла;

1(38) - чтеияв (Y, « 1) /запись {Y, « о) ииформации нз блока I

7i(34) офохощяение иаформации с блока 3;

74(2) г ксррвхтя нулевого разряда считываемого слова

Y,(41) прохоовдвкяв ивфсфмащш яа шину 25 дашшх с блока 12 {

X,(36) - проюятюям вяф011мац8и с регкстра 10;

(40) о atHbM мпа яа регистр 21;

V,(39) - т едт11р9йАия« вчипшв0(Ы1 иифоршции из блока 1 гамятк;

I,(35) « п шсакдешм ак юрмашп с выхода коммггатора 23;

YK(44) шпат еягаала ОавЮкя ;

информации иа «вшу 25 с даииых регистра 211

Yitv4Sf - B«new ешчпмв Нвйсврммость дажодвра.

Таблица 2

X,

x,x, x,x, u,

j

uV y

I I

I

u.

u,

Ul

I

Y,. Yj

Y,. Y

« 4

y,. Y(. Y, Y,,. n

n

t. Y,. Y,

5f,.VY« YH

Y,.Y,,Y

V,

,.5,

«

С Конец )

I KlW I

Уп (ff I

yiimffsi Ую1ЧЗ)

Фиг, 2