Устройство для обнаружения ошибок в блоках памяти Советский патент 1990 года по МПК G11C29/00 

СО 4

05

иания и цекоднр)Ойаш1Я к расширение-- : иоласти npHNieneHji:4 уст1зойс.тва за с чат возмо лп-юсти деко,ч;дрова:-ия коцоя о,.Т ,n,;irtfU,, запав., :; з,пичными по-- линома и. Устройство содержит преоб-- pa3OBaTej b кода i , обнарухчекия адреса ошибки 2, 3, фор «1рователь угфавлягощнх сигналоз А , блоки таторов 5-7, эле1ме ты 8™ И , инве р- тор 12, элемент 13, первьв 14 и второй 15 триггеры, :четчнк 6 к

имеет информационный вход начальной установки IBj та 19, первый 20, второй 21,, управляю1Щ1с вькоды,, ,р.: выход 23, в ХОЛЬ выбора рея; гр:, ннформационны-х выхо контрольные выходы 26, Уст позволяет кодировать и ;1ек код(л Файра, исправляющяе п бсзк, задавг емме выражение ; -- (xf-1) П Р . (0 . f- ил„

Изобретение относится к вычислительной технике и может быть использовано для обнаружения ошибок в накопителях с последовательным доступом для повышения надежности. Целью изобретения является расширение функциональных возможностей устройства за счет совмещения функций кодирования и декодирования и расширение области применения устройства за счет возможности декодирования кодов одной длины, задаваемых различными полиномами. Устройство содержит преобразователь кода 1, блоки обнаружения адреса ошибки 2,3, формирователь управляющих сигналов 4, блоки коммутаторов 5-7, элементы И 8-11, инвертор 12, элемент ИЛИ 13, первый 14 и второй 15 триггеры, счетчик 16 имеет информационный вход 17, вход начальной установки 18, тактовый вход 19, первый 20, второй 21, третий 22 управляющие выходы, информационный выход 23, входы выбора режима 24, группу информационных выходов 25 и контрольные выходы 26. Устройство позволяет кодировать и декодировать коды Файра, исправляющие пакеты ошибок, задаваемые выражением Y(X) = (X E-1), П @ р J (х). 6 ил.

Изобретение относится к iiin-. nc. iH- телыюк тех нике м может быть исполь- эозаио для обдар У кения онптбок в на- копзгге.1ях с П1:)слало:затлдьиым для повышен-ня кадсж чос 1 и ,

Паль изобретемия - ;:г;сш1-;рение фу -гкцяональньк возможностей устройства за счет ссв1чещани: . функций кодирования и дакодироваПИЯ и расширение области гриь ененяя устройстн а за счет возможности дед одирования KojiQB одной ллии;1, зад;:заекь :-: раз; ичИЬЕ -Ш ПОЛИ нома Mi „

На фиг. 1 гградставлеиа структурная схема устройства:, на фяг. 2 - схема преобра яоватедя кода с леркьп- .г. таторов; на фяг, 3 - схгма блока обнгфужекия адреса ошнс КИ с вторым

же, с Т;;етьям коммутаторов;

на лиг, 5 - схема из коммутаторов первого ком;-утаторов; на фиг о 6 - то жй,, зт зрогс блока комуутаторюв.

Устройство ( . 1) содерлсит пре- образоватадь i ;;ода, Глоки 2 и 3 об-н:аружения адреса эш:;:бки. иовате ъ 4 у:-;;а ггтяташ;- ;;: сигналов, блоки 5-7 ко№-5утатэров. :1лементы И 8-11 ин11ер- ор 12., элемент 1Ш1 13. дервый 14 и второй 15 - pHrrersbis, сметчик 16, - нформац -юнны аход Г , вход 18 начальной устакоЕкн, та:;товьэд вход 19 neppiiSi 20 „ Еторсй 21 и третий 22 уп paBjifaoupie зыходь. инф;;рмэ11ионный вы-- ход 23, входы 2ч выбора режима, группу информаид-юнкьк вьс-;одов 25 и контрольные ВЫХОД 1 26 о

Преобразователь 1 кода содержат () триггеры 27-45, сумматоры по модулю два ii6-6 ,, элемент И-ИЛИ 62, элементы И 63-г65,, триггер 66 инвертор 67, элемея- - ЯПИ 68, элемент ИЛИ--НЕ 69 и c4i T4j K С„

IJJ OK 5 ;СОМ:ЧуТП ГПро л (ф:

держ1- Т коммуг/это). 71-7Д, Преобраз; : ател1, Knjia контро:1ьные пзряды копов. мьк М5 огоч;;е:-1ами oju-ion ci

оораловатсль Г:;ч ;ек ос ущестпля ет rie; f:;ni j

lia копит еЛЯ Икформа ОНМ:): ТГЛЬНОСТг -la ().

элемент И 99 -; la ;/..:/мт И 10, осуществляет прие:- и обра :;:; г ку маемой информадиониой п- с- т ао; ; ности до г-пюгочлепа:- Р (х)..

Блок 3 об ируже;;; ;; адр-;С;: о; (фиг,4) содержит I iJif; геры ;)- сумматоры по моду;п(; дна 1(9- i. му 113 срав}:аиия5 я пчертс ii мент И 115 а счс гччк 16, хюк мутаторов (фмг ,-.) ci.- epsi-rr И 1 1 7- 20 и комму- аторы .. Г

ДОМОЩЫО 6j:OKOB 3 м 7 ОС УСК-С т iSJI-: .-- СЯ

прием и обработка i;;;il}op a:;4oH i :ix IK

сиедовательнос е11 на oci- OPo iiiorc-4j::eHOB l (x) ,

Коммутатор 7t /Ьиг ,5; f .n:выполнен }ia ociiOBO деюнЬра:.-pa инБерторов 124-127 и эле снто; ИЛ

Коммутаторь 72 и 73 могут бь;т1. реализованы на №1кросхемах К155К 17, на управляющий вход которых -(адо подать нулевой потендиал,

Комкутатс р 74 может быть реализован на трех микросхемах типа К155К112,; строб-входы ко .горьс-; надо за ги еклять . на адресные вхо.ды псхдать .чвухразряд-ный код от блока 4, а на информаци- - онные входы соответственно с выбранными алгебраическими выражениями подать входы с соответствуи)пд1х выходов триггеров преобразователя 1j

кода.

Коммутатор 95 (фиг.6) может быть реализован на основе дешифратора и инвертор 134-136. Коммутатор 96 выполняется аналогично.

Коммутаторы 97, 98, 121 и 122 могут быть выполнены на микросхеме К155КП7, при этом управляющий вход заземляется.

Формирователь 7 управляющих сиг- калов может быть выполнен на микросхемах ПЗУ типа КР556РТ7.

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

образом.

Перед началом работы устройства в любом из режимов производится обнуление триггеров преобразователя 1 кода блоков 2 и 3 обнаружения адреса ошибки, триггеров 14 и 15 и счетчика 16 по входу 18. Далее путем подачи управляюисих сигналов по входу 24 формирователь управляющих сигналов 4 осуществляет настройку уст- ройства на реализацию одного из кодов. Предположим, что необходимо реализовать устройство на основе кода, задаваемого многочленом й(х) (.i) (х 4-х+1) (х +х+О . Длина этого кода 1155 разрядов при 18 проверочных.

Кодирование информации.

Кодирование осуществляется преобразователем 1 кода. При этом из блока 4 считывается кодовая последовательность, которая определяет саму процедуру (кодирование-декодирование), выдает управляющие сигналы на коммутаторы 71-73 для реализадии кодирования на основе

g(x)x +х и х -«-х +х +х +хЗ+ + к + 1 .

Для этого необходимо, чтобы коммутатор 72 пропускал сигнал с 18-го разряда, т.е-, с триггера 44 преобразователя 1 кода, коммутатор 71 пропускал сигнал обратной связи с триггера 44 на сумматоры по модулю два соответственно 2, 3, 5, 7, 11, 13, 14, 16 разрядов или на сумматоры по модулю два 48, 49, 50, 52, 55,

57-59.

Информация, поступающая от памяти процессора и сопровождаемая синхро- ;

5

5

серией, сдвигается в замкнутом ре- гистре с обратными связями, образованном триггерами 27 - 44 и.сумматорами по модулю два. Причем сдвиг осуществляется до тех пор, пока не будут приняты все информационные разряды, при этом триггер 66 в нуле, а следовательно, информация из регистра на выход устройства через элемент И 63 не проходит. После того, как будут приняты все разряды, в.регистре остается остаток от дапения информационного многочлена (информационной последовательности) на порождающий полином g(x). В этот момент элемент И 63 открьшается, и содержимое регистра при разомкнутой обратной связи сдвигается на выход устройства. 0 Информация, выходящая из регистра, является проверочными разрядами кода для принятой информационной последовательности. На этом процесс кодирова-, ния принятой информационной последовательности заканчивается. Он может быть повторен аналогично столько раз, сколько информационных последовательностей передано через устройство для кодирования.

Декодирование инфopмalp и. Декодирование осуществляется преобразователем 1 кода совместно с блоками 2 и 3.обнаружения адреса ошибки. При этом преобразователь 1 кода осуществляет деление принимаемой инфор- мадаи на первую составляющую полинома g(x), т.е. на (). При этом путем подачи правляющцх сигналов от блока 4 на коммутаторы 71-74 осуществляется следующая коммутация сигналов: коммутатор 72 пропускает сигнал с выхода 11 триггера, в результате чего образуется замкнутый регистр с обратной связью, через элемент И-ИЛИ 62 и сумматор по модулю два 46, коммутатор 71 сигнал обратной связи не пропускает, поскатьку двучлен () промежуточных степеней х не содержит; коммутатор 73 пропускает сигнал обратной связи с вьгкодов 1-6 триггеров i через коммутатор 74, выходы 7-11 триггеров сигнал подастся на элемент

ИЛ11-НЕ 69.

Блок 2 обнаружения адреса ошибки одновременно преобразователем 1 кода преобразует информацию входную на основе многочлена . При этом коммутаторы 97 и 98 пропускают информа- 11ЯЮ с выхода четвертого триггера 78 (85), которая поступает на коммутато0

35

40

45

50

55

p:.i 95 и 96, Они, в свою очередь, эа- М1)кают обратн то связь верхнего и нижнего регистров на су1чматО рах по модулю два 86 и 89 соответственно, что позволяет получить первую степень х ,в многочлене х +хт1„ KoMwiiTaTopbi 99 и 100 не пропускают сигналов с выходов триггеров 79 и 84 на схему 91 сравнения.

Блок 3 обнару;кеник адреюа ошибки, преобразует информацию, поступающую на вход одновременно с пр :образова- телем 1 кода на основе мнс гочлена X -t-x- -1 . При этом через коммутаторы 121 и 122 выходы триггереF; ШЗ и 107 верхнего (по схеме) и нижнего регистров соединены с cyMMaTopa;viH по модулю два 109 и 111 соответстпенно, а также через коммутатооы П7 и 118 с сумматорами по модулю два 110 и 112 соответственно. На схему 113 сравнения поступают сигналы с выходов триггеров 101-103 и 105-107.

На этапе деления информационного многочлена, поступ:ающего на декодирующее устройство, на соста Е ляющие порождающего полинома g(x) F1 блоках 1.-3 формируются остчтки 61 деления. Если оимбки в инЛормаш-юином многочлене, поступившем на декг дирующее устройство, нет, то после приема всех 1155 его разрядов элемент 1 ШИ- Е 69 фиксирует нули, а скемь 91 и 113 сравнения фиксируют совпа,:,ение содержимых верхних (по схеме) ;л нижних ре- гистров в блоках 2 и 3. Ир версии этих сигналов поступают pis элемент И 8, который формирует сигнал Ошибки нет, который запоминается в триггере 14. На этом работа устройства по декодированию принятого исформацион- ного многочлена заканчивается. Если .принят информационный многочлен, содержащий ошибку, то после прохолсде

ния всех его 1155 разрядов через

блоки 1-3 содерж г1мое триггеров 33-37 блока 1 отлично от нуля и)чеет место несовпадение содержимого EiepXHHX (по схеме) и нижних регистро:Е1 в блоках 2 и 3. Сигналы от 69 и схем 91 и 113 сравнения аннулируются только после прохождения всех 1155 разрядов что обеспечивается счетчиком 16,

Если на декодирующее устройство для обработки поступает информацией- ный многочлен, содержащий некорректируемую ошибку (нет сравнения в одной из схем 91 или 113 сравнения или элемент ИЛИ-НЕ 69 не фиксирует нули,

или в двух из указанньк схем не т сравне шя), в триггер 15 поступает сигнал некорректируемой ошибки, и ;эа бота устройства заканчивается,

Если на декодирующее устройство для обработки поступает кгкЬорма цис ный многочлен, содержащий корректируемую ошибку (нет сравнекик Б схемах 91 и 113 и элемент ИЛИ-НЕ 6Э не фиксирует нули), то 1осле прохп.гг дения 1155 разрядов через блоки :-- - содержимое блоков продолжает сдвигаться. Сдвиг икформатши продолжаег- ся до тех nopj пока в пяти последних триггерах 33-37 1 1-тн разрядно/;: регистра схемой 1 ШИ-ИЕ 69 ке г-утут зафиксирова яы в силу изБес . ньк свойств двучлена (х +1) опрепг:-- ляет момент расположе п ня в шести п- ..вьгх триггерах 27-32 пакета ошибки. С этого момента сдвиг нформа1п-:и в блоке I прекращается через инвертор 6/ и элемент И 65, Одновое-чен о ется сдвиг информации г в вер Хп - х; (по схеме) регистрах блоков 2 и 3,

С момента обнаружения короектируг мой оимбки начинается полсчот ::v;i икт;-; имг ульсов в счетчике 70 н блок-г- -. счетчике 94 в блоке 2 и счетч-лкс : в блоке 3, Накопление синхроимпульсов Е счетчике 70 продолжается ;-о мента выработки элементе HJH-i-H; (-- сигнала сонпадегп-ш с нулем, Заф. рованный в счетчике 70 сод пс1цдс лг: .лист собой остаток от делечр;я нск осгк О иибочного разряда р ном многочлене на 11 ,

Сдвиг содержимого -мжшах (ло схеме) регистров блоков 2 и 3 и ягкоп- ление синхросигналов в с -:етчг-- к; ;:; , и 116 продолжаются до тех пор. ncjKa схемами 91 и ,113 сравнения сои- -ветст- венно не будут обча1;у7 сены соггпапекик содержимых верхних и нижних регистров. Сигнал совпадения от 9i -ьзрез элементы 92 и 93 запрещает прохс ;;де- ние синхросигналов ка нижний регистр блока 2 и па счетчик Э , Содержимое счетчика 9 связано с номером ошибочного разряда следуювг-:м соотношением: i Гр,по модулю е 2-1 15.

Ан.алогичное преобразование информации происходит в блоке 3. Содержимое счетчика 116 после его остановки опреде,пяет i г „ по модулю е , 7.

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

нформационном многочлене из 1155 разрядов, что позволяет начать кор- акцию. Предлагаемое устройство не осуществляет коррекции информации.г

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

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

35

40

45

5 О

5

0

5

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

JS

КЗ

сЙиЗ

к 47 45 etg 5Q 51 52 53 5 55 55 57

Фи9.5

58 596061

От If