Устройство для обнаружения ошибок в блоках памяти

 

Изобретение относится к вычислительной технике и может быть использовано для обнаружения ошибок в накопителях с последовательным доступом для повышения надежности. Целью изобретения является расширение функциональных возможностей устройства за счет совмещения функций кодирования и декодирования и расширение области применения устройства за счет возможности декодирования кодов одной длины, задаваемых различными полиномами. Устройство содержит преобразователь кода 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 ил.

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

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

РЕСПУБЛИН

С 11 С 29/00

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

И А BTOPCHOMV СВИДЕТЕЛЬСТВУ г(!

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

flO ИЗОбРЕТЕНИЯМ И ОТКРЫТИЯМ

ПРИ ПСНТ СССР (21) 4336930/24-24 (22) 30,11.87 (46) 23.09.90. Бюл. 11 35 (71) Московский энергетический институт (72) И,Н.Андреева и Г.A.Бородин (53) 68 1 ° 327 (088.8) (56) Авторское свидетельство СССР

1"- 1372386, кл. G 11 С 29/00, 1986.

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

Р 1249523, кл. С 11 С 29/00, 1985.

„„SU„„1594611 А 1

2 (54) УСТРОЙСТВО ДЛЯ ОБНАРУЖЕНИЯ ОШИБОК В КЛОКАХ ПАМЯТИ (57) Изобретение относится к вычисли-.. тельной технике и может бьггь использовано для обнаружения ошибок в накопителях с последовательным досту— пом для повышения надежнссги. Целью изобретения является распгирение функциональных возможностей устройства за счет совмещения функций кодироВВ НИя и дЕКОдира -ЛЧИя,:- 13ЛСИП(рЕНИЕ-области пр)(менен.«я устройства зя =чет

1)(1Я;<ос<)1(3С;).Ц Д<.1(0 t 11)ОВЛ ЦС! КОДОВ ОЗ-.

С! H,.t ) l q НЬ(МИ Л О !! ер)кит пр е с бц обнаружения

1 0 .. .:I:t -! . зe(111 В,, е; !ых

r!! t rlO}rc3МИ,"Стй;) и. 1-ВО СС разовател< кода:: } бло) а.дреса Окибки 2, 3, фо(. уг(рлвяяю(((}(х сигналoз 71 1 таторон 5-7, злементы тор 1 2, зл еме:-!т и.!!Я 3, и второй 15 т13иг г еры, 1 мцр она тел ь блски комму8- 11 ИНВЕР-! (! и eр B1! :(й 1 {( (етчцк 16 и имеет информаьион" .{}t Вход,, В - ....

НаЧаЛЬНОй уСТЛНОВКИ 18., т-.: t t. ttc.é Е :

I 9, первь(й 2С, нторсй 21,,:, е-, ии управляю!цие .=..bD(îäû, kf}tc} ....... :. 0})1, - .

Выход 23, Вхсг:ь! выб cpa . .с s группу цнформя!}ионньх Вых-.::,с}

КО}(трОЛЬНЫЕ ВЫХОДЫ 26. УС.1,, Сс!3«. В;

11r) ЗВОЛЯЕт КОДИР ОВатв И -l;, .. С

КОДЬ! ФяйР",,, HС(!РЛВЛЯЮПЯ = Ис С-:

6 Ок за, гrc Вc) с .".t} )с В}1!р лже(В1. с!. . (х — 1 1-) р . (И) . 6 и.), 1 <

Изобретение от);осlt f(я к;;.: r()c 14—

" ель(!01-: т ех}(ц)се !f;))I! eт:3ыт ь исп «131 ь=

3 Овл c! G lfля 0(3)lс}p,"t(е (ия О(п(бо к в нл (СОП;1 (Е {Et). C it(. (. I 3" .ЗЛ!::гЬНЬ!М ДС)С ГУПО)". (1;1! ЦО Н,!!)!OH< °,-1 1)а г ж HO 0 Ц

Ие;<г, и )обретения — — .c}я(рениe ф- .-<КЦИО:tc<31.; l!HEX ВЗЗМзж}{ССтЕй УСтРОйс т в а за с ч ет с с H } t e)lt e }f -:.. функций к о-1 И})0 1=(ftk .Я И («I(01<И3 В 1 "IЯ И Гс! 1(И рение Области I ри}!е}!ения устройства

С с(т E)<)ЗМг,,;;-,,О -", И Дг (ОДЦГ С.. ()ЛНИЯ .(01< ОВ 011!!OЙ л <(ИI !, Зс!г - Зяег Ьс ра rb!1<ч }-(Ь(}а: ИОПИ ." ОМсl ":с! .

Нл ц)."!1, 1 (1 j) -ег(. .. тя Вл с! )!cl с те кт ур Hi(ÿ схe}è ycòãойствл Не фit-. 2 — .".Хемс; пj) 000рл з ОБл т е(1}! "Ода с I ерв ь}м блО I(c l

1 r

КQ)1,!Ьг« Л r Ос) ОВ, }!c{ „" (Г с 1 -* СХ ЕМЛ 10}c об:иг р-,.-.;Ля.(я а (г):.:Сл 0 rttt ки с Бторьlу)

l, 0!iOК0 Ко 1"rУТ=. " i) )11 !)Л <<)И.г, с(ТО же, с: тр ет:- -(и = . ((3}(коммутаторов; 3

Ня 1!В(т . 5 С)((Еr l,) ОДНОГО ИЗ КОМ}ггта ГС-РОВ Г< . .)В ОГО 5)EC) ..=. IrOt! . TB ТОР OB . ;)Я фИГ . О Т 0 Ж(,, -1Ò О,) ОГ С OJIOKC. К ОМ . УТЛ

Г р гр

Е<1 1

Усгройс-.во (<ьселг „1) содер;кит псе- 4Обря!ЗОВЛТ ЕЛЬ j (01Л,:сПОКИ 2 и 3

<3<) !сс) Рсг" at!})c. л Р: "s "!1! бки. фон}(и-!си )-- 7 tcoi„-В:;,) E= -,, pOH, -)(еме н--ь) И 8-1 1

-3

-ИНВЕ-,, гоо "? -,г С МЕН- (" Д(1„ПЕВ1)Ы," ( с

)Ь. и;=, rr рой ", -) г-)г<г.(" гг(г; счегг<и}с 0

П! Ер В},-.-1, ) НТ Ор:.-: ? 1r тг, Е; Ий 22 уП;.) ЛБЕ(К.СЕ<(ИВ eb)). "()c3 с!, И Нф.; (3МЛ ))ИС) }iHb ВЫход 23, входы 2-. Вь}бс ) a режима, руп— пУ инфоРыа}в<он} ьсх вь0«3Дов 23 и конт26.

Преобря зоват ель 1 кода содеряят (фиг 2) триг! еры 27-ч 5. сумматс)р и ио модулю ",вя с)6-с „зле (ент И-ИЛИ 62, э}<ементы И 63-.,(5,, триггер 66., rHfl})ep"0p 67, .-.немев 1iIjH 68 зл 1(eH}

}Я tir, --1(1) 6 9 И С сг Е Гг(}! 1С

t1.1 Ок 3 (с)}) tутг). (1 )ОВ (11 ) !

r жс Т Косг"!у c!3 ci)}, 71- 1.

Пр е О б <3 с3 1 (). 1 Т,) }, к 11 "> c) к с }11 1) с)-1 b н Ь) <с р Л - ")я Еl f 1

Мг Х Мггог011 Е !Лм < Р t!,11, 1 о

},х — 1):, Р; (х) с

Обрct »(:Бсг. с Ilь сс

О() jll(» E» IЯ (-,1, c ;1<:

НЛ (1 ОП - )т Е:(Я tt .ф . t . -! }1, ); .! 1): р (, 1 1

<аiopы по 1)р;)у(1ю .(в:) 8-> 9", Cг)яВ IеflHя,, И".Вс -!)Топ ",2, -.:1

И СЧЕТГ(ИК ) - .:.::ОК ". КС ) lс . ".(1! :

ЭЛЕМЕ(ГГ )i 99 -:::..::; П

0С "ЩЕСТВЛ}г Е " . (1((Г

МЛЕМО » ИНфОР! 1:::(О ..:.:. .. -С.»: —.:. !.:: Г

Н(CÒÈ Т!0 }t)!0 "0(. (Р! С))! 11 СХ ;

1 е)лОК 3 Об (лружс :: );.:. с);(.г. (фиг, ) co, le 3жи г т())1 : е! ы, 1 - .л с 1p c} op b1 t! o . ) o-);, !): л !)(1 1 1 7 - j му 1 ", 3 срл)=,1! !л- я 1 Hер-,„-). мент .1 )15; с-((3 (:к 16 гl ТЛТО} Ов {ф. -11, -, С< <)Ожс! rC; r

И 117-12(: . ко муr ) Ор ; пр.(с);!(Ью б<(р};.)в 3 1; 7 -;.с .-;; 1 „..г{рием и Обрл:»3-: к 1::Фор).:;." =.!!r!rC;(ЕДОВЯТЕЧ<,Н -1(- (й;г.l 1!)cc ....:;-,à —— чл e H o E) },, (х )КоммуTHTop г, {",!и, . j

Выло:t}te}! на .с!:Онс, !с)к <1)():) . -.л

I1epyop0I1 1 2<1--1 27 . -с е){(: ):..-О

128-132.

Коммутаторы 72 H 73 -fn-"у. -г бь;т), ялизованы нл микрс)схемах К155КП71 на упрлвляюплй вход которых:(яд о по;Еа-.ь нулевой потенциал, Коммутатор 74 может бьгг}. р ел.".};==сван на трех микросхемах ти.-.л К15511П21 строб-входы котсрьгх }(ало )с ., — лять,.

На адресные вхочы ((и (лть;:.— ухр(t" pяд-10

50

5 1 5946 ный код от блока 4, а на информационные входы соответственно с выбранными алгебраическими выражениями подать входы с соответствующих выходов триггеров преобразователя 1 I кода.

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

Коммутаторы 97, 98, 121 и 122 могут быть выполнены на микросхеме

К155КП7, при этом управляющий вход эазеипяется.

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

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

Перед началом работы устройства в любом из режимов производится обнуление триггеров преобразователя

1 кода блоков 2 и 3 обнаружения адреса ошибки, триггеров 14 и 15 и

25 счетчика 16 по входу 18. Далее путем подачи управляюших сигналов по входу 24 формирователь управляющих сигналов 4 осуществляет настройку устройства на реализацию одного из ко30 дов. Предположим, что необходимо реализовать устройство на основе кода, задаваемого многочленои g(x)

=(x"+1) (х +х+ ) (x +x+ ) . Длина этого кода 1155 разрядов при 18 проверочных. 35

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

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

g (х) =х 1 +х +х и+х +к "+х +х +х Э+

+ х + 1.

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

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

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

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

При этом преобразователь 1 кода осу ществляет деление принимаемой информации на первую составляющую полинома

g(x), т.е. на (х"+1). При этом путем подачи управляющих сигналов от блока

4 на коммутаторы 71 †?4 осуществляется следующая коммутация сигналов: коимутатор 72 пропускает сигнал с выхода

11 триггера, в результате чего образуется замкнутый регистр с обратной связью, через элемент И-HJIV» 62 и сумматор по модулю два 46, коммутатор

71 сигнал обратной связи не пропускает, поскольку двучлен (x " +1) промежуточных степеней К не содержит; коммутатор 73 пропускает сигнал обратной связи с выходов 1-6 триггеров, через коммутатор 74, выходы 7-11 триггеров сигнал подастся на элемент

ИЛИ-HF. 69.

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

159+61 i р 1 95 и 96. Они, в свою очередь, замыкают обратную связь верхнего н нижнего регистров на сумматорах по модул:о два 86 и 89 соответственно, что позволяет получить первую степень в многочлене х "+х+1. Комму3 аторы 99 и 100 не пропускают сигна.- ов с выходов триггеров 79 и 81 на схему 91 сравнения.

Блок 3 обнаружения адр вг а ошибки, преобразует информа цию, пс ступающую на вход одновременно с пр. образователем 1 кода на основе мнсгочлена х +х+1. При этом через коммутаторы з

121 и 122 выходы триггерсв 103 и 107 верхнего (по схеме) и нижнего осгистров соединены с сумматора:1и по модулю два 109 и 111 соответственно, а также череa коммутаторы 1 7 и 118 с сумматорами по модулю два 110 и 112

20 соответственно. Ча схему 113 сравнения поступают сигналы с выходов триггеров 101 †1 и 105-107.

На этапе деления инфор 1ационного

l многочлена, поступающего на декодирующее устройство, 1! coc Ta Elëÿþùèå гторождающего полинома g (x) г, блс3ках

1-3 формируются остатки с1 пеле13ия.

Если ошибки в ин133ормацио1<111ом много30 члене, поступившем на,.гек -. пирующее устройство, нет, то после приема всех 1155 его разрядов эл:-мент ИЛИ-HE.

69 фиксирует нули,:. с хем;1 91 и 113 сравнения фиксир уют со впа, ение с;одержимых верхних (по схеме) . нижних ре- 35 гистров в блоках 2 и 3. Иг:версии этих сигналов поступают на элемент

И 8, который формирует си.r нал п0шибки нет ", который запомина:-Tñÿ в триггере 14. На этом работа устройства пс 0 декодированию принятoro и1формационного многочлеча заканчивается. Если .принят информационный мнс г очлен, содержащий ошибку, то после прохождения всех его 1155 разрядов через блом 1-3 содержимое т,ригг еров 33-37 блока 1 отлично от нуля имеет место несовпадение содержимого верхних (по схеме) и нижних регистро в блоках

2 и 3, Сигналы от ИЛИ-НЕ l9 и схем 50

91 и 113 сравнения аннулируются только после прохождения всех 1155 разрядов, что обеспечивается счетчиком 16.

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

Если на декодирующее > стройc Tво для обработки псстуггает Hrr!Üop"..;" ци" l ный многочлен, содержащий коррсктируемую ошибку (нет сравнен:-.я в схемах 91 и 113 и элемент ИЛИ-HЕ 69

НЕ фИКСИруЕт Нупн), То ПОС.:1 Е дения 1155 разрядов через блоки содержимое блоксв продолжает с.;1вигаться. Сдвиг информации продолжа е-ся до тех пор, пока в пяти пос.- едних ", риггерах 33-37 11-;и:азрядно : реги(Тра схе1<го 11 1 Л1<,-<1Е 6<9;.:е-,= ., —, <,:-с зафиксирава ны нули, что в сил»у - —,B х спо йств дю."-iлена (х 1 +",, рпр ляет момент pacriàrloæåaira в шее ги п < вых триггерах 27-32 пак::та ошибки <

С этого момента сдвиг 11:1фс3рмац:.:!< в блоке 1 прс кращаег ся;врез и".в.--.: ор б: эл с мент И 6 ., Пд 3о Jo cJ ° 11< 13 г1О ется сдвиг информации 1, вер

С момента обнаружен: я корр - "-Jpi:c— мой с3133ибки Начинается li:J.-,с-. CT ., я ;.::..— импуJTE>coB в сч. г l lt;;- 7i, rг б

СЧЕТЧИКЕ 9 3 3В !JтаКЕ 2 И С-3Ет«;1к3" в блгке 3, Накопление с3-: нхрои<-.: .-:-:=сов в счет<1ике. 73 ".ponoлжаe. ся мента вьгработки .3лементом 1ГИ-Н

c H I н а л а с о <3 и

- Io . -

2" — 1

Аналогичное преобразование информации происходит в блоке З„Содертмое счет:ика 116 после сго остановки определяет = г по модулю е =

Р 1

2-1=7.

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

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

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

Устройство для обнаружения ошибок в блоках памяти, содержащее преобразователь кода, группу блоков обнаружения адреса ошибки, первый, второй и третий элементы И, первый и второй триггеры, счетчик, информационный вход, вход начальной установки и так- 15 товый вход преобразователя кода и блоков обнаружения адреса ошибки группы соединены и являются соответствующими входами устройства, первый выход преобразователя кода соединен с четвертым входом каждого блока обнаружения адреса ошибки группы, первый и второй выходы которых соединены с соответствующими входами первого и второго элементов И соответст- 25 венно, второй и третий выходы преоб разователя кода соединены с соответствующими входами первого и второго элементов И соответственно, выход первого элемента И соединен с входом первого триггера, выход которого является первым управляющим выходом устройства, вход начальной установки устройства соединен с соответствующими входами счетчика и первого и второго триггеров, первый вход третьего элемента И соединен с тактовым входом устройства, о т л и ч а ю щ ее с я тем, что, с целью расширения функциональных возможностей устрой40 ства за счет совмещения функций кодирования и декодирования и расширения области применения устройства за счет возможности декодирования кодов одной длины, задаваемых различными полиномами, в него введены блоки ком45 мутаторов,— формирователь управляющих сигналов, четвертый элемент И, эле= мент KIN и инвертор, выход которого соединен с шестым входом каждого блока обнаружения адреса ошибки группы и с четвертым входом преобразователя кода, пятый вход которого соединен с вторым выходом счетчика, первый выход которого соединен с входом инвертора, с седьмым входом каждого блока обнаружения адреса ошибки группы, с первым входом четвертого элемента И и с соответствующим входом первого элемента И, выход третьего элемента И соединен с входом счетчика, входы элемента ИЛИ соединены с соответствующими входами первого элемента И, выход элемента ИЛИ.соединен с вторым входом четвертого элемента

И, выход которого является вторым управляющим выходом устройства, выход первого триггера соединен с соответствующим входом второго элемента

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

1594611

Я ФУ 48 ФУ 50 Я 5253 5О 5 5 И 57 58 Ю9б062

Фиг.б

Составитель И.Лапушкин

Редактор О.Поповен Техред 11. goдaни Корректор Т.i1a-ie«

Закаэ 2834 Тираж 485 Подписное

В1%ИПИ Государственного комитета по,иэобретенилм и открь тинм r;nè Г-,НТ .СС,:- 13035,„ Москва, Ж-35,. Раушская наб., д. 4/5

Проиэводственно- иэдательский комбинат "Патент",, г. Ужгopop,, gл Гаг=-:;::;.