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

 

Изобретение относится к области вычислительной техники и может быть использовано для обнаружения ошибок в запоминающих устройствах с последовательным доступом. Устройство СО держит преобразователь 1 кодов, бло ки 2 и 3 обнаружения а:дреса ошибки, коммутатор 4 и логические элемеиты. Изобретение позволяет повысить быстродействие устройства за счет сокращения времени на обнаружение адреса ошибки. 1 з.п. ф-лы, 3 ил. (Л С СД :о

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

COLlHAЛИСТИЧЕСНИХ

РЕСПУБЛИН (19) (11) E (511 4 G ll С 29 00

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

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

/Р

1У

/ф

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

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И.ОТНРЫТИЙ (2l) 3861624/24-24 (22) 28. 02. 85 (46) 07.08. 86. Бюл. В 29 (71) Московский ордена Ленина и ордена Октябрьской Революции энергетический институт (72) И.Н. Андреева и Г.А. Бородин (53) 681.327 (088.8 ) (56) Введение в запоминающие устройства прямого доступа и методы организации данных./Под ред. Г.К. Столярова. — М.: Статистика, 1974, с. 12.

Хетагуров Я.А., Руднев Ю.П. Повышение надежности запоминающих устройств методами избыточного кодирования. — М. . Энергия, 1974, с. 71.

Патент США У 4216541, кл. 365/15, опубликi. 1980. (54) УСТРОЙСТВО ДЛЯ ОБНАРУЖЕНИЯ OIHБОК В БЛОКАХ ПАМЯТИ (з7) Изобретение относится к области вычислительной техники и может быть использовано для обнаружения ошибок в запоминающих устройствах с последовательным доступом. Устройство содержит преобразователь 1 кодов, блоки 2 и 3 обнаружения ацреса ошибки, коммутатор 4 и логические элементы.

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

1 l2

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

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

На фиг.! представлена структурная схема устройства; на фиг. 2 функциональная схема преобразователя кодов; на фиг, 3 — функциональная схема блока обнаружения адреса ошибки.

Устройство для обнаружения оп|ибки кодом, задаваемым полиномом P(x) =

=(х" +1) (х З + х+1) (х + х+1 ), содер.жит (фиг. 1 ) преобразователь 1 кодов, блоки 2 и 3 обнаружения адреса опибки, коммутатор. 4. элементы И

5-7, счетчик 8, триггеры 9"11, входы 12-14 и выходы 15-17 устройства.

Преобразователь 1 кодов (фиг. 2) содержит сдвиговый регистр 18 с обратной связью, элемент И 19, инвер тор 20, элементы И 21 и 22, ИЛИ-НЕ

23 и счетчик 24. Сдвиговый регистр

18 соответствует двучлену х +I Он

13 содержит триггеры 25-37 и сумматор

38 по модулю два.

Блок 2 обнаружения адреса ошибки (фнг. 3) содержит сдвиговые регистры

39 и 40 с обратной связью, блок 41 сравнения, элемент И 42, инвертор

43, элементы И 44 и. 45 и счетчик 46.

Сдвиговые регистры 39 и 40 соответствуют многочлену х + x +1 и содержат триггеры 47 — 52 и сумматоры 5356 по модулю два.

Блок 3 обнаружения адреса ошибки имеет точно такую же структуру, что и блок 2. Но, поскольку он соответствует многочлену М + х +1, его сдвиг ,говые регистры содержат по два триггера (что соответствует степени многочлена) и по два сумматора по модулю два, что соответствует количеству ненулевых членов х

При изменении количества сомножителей и порождающем полиноме P(x) в устройстве увеличивается количество блоков обнаружения адреса ошибки, отличающихся друг от друга количеством триггеров и сумматоров по модулю . два в сдвиговых регистрах. . Устройство обнаружения ошибки ра- ботает следующим. образом.

49593 2

Пусть порождающий полинам кода задан следующим выражением: м

P (x) = (х -1) ()р, (х), f-1

5 где р;(х) — неприводимый многочлен степеуи и порядка, равного е °

J (е =2 -1); С не делится на е; .

Длина кода и равна наименьшему общему кратному (с, е,,...е,„ . Код, порожденный полиномом .P(х) =(х н — 1) П р. (х1, обнаруживает все пакеты

J ошибок О(х) длиной Й и исправляет все пакеты ошибок В{х) длиной а р при

H условии, что с) b+d-1 и b» ÅÕ..

1=1

На фиг.! приведен пример построения устройства для обнаружения ошибки кодом P (х) = (х +1) (х + х+1) (х + х+1) . Длина кода n = 273. Выполнение процедуры декодирования начинается с обнуления по входу 13 блоков 1-3 и 8-11. При приеме информации от накопителя все разряды, начиная с 256 информационных, по входу устройства 12 поступают на первые входы преобразователя 1 кода и блоков 2 и 3 обнаружения адреса ошибки (на вторые регистры сдвига). На первые регистры сдвига блоков 2 и 3 информация поступает с пятого триггера регистра сдвига блока 1. Все регистры сдвига работают синхронно,. что обеспечивается подачей синхроимпульсов по входу 14 устройства через элементы И 21 и 44.

На первом этапе работы устройст4О ва, т.е. на этапе деления информа— ционного многочлена на соответствующие составляющие порождающего полинома, в сдвиговых регистрах блоков

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

Если ошибки не происходит, то после прохождения и бит кодового многочлена (информационной последовательности ) через сдвиговые регистры блоков I 3 содержимое триггеров

50 регистров равно нулю. Это фиксируется элементом ИЛИ-НЕ 23 и блоками сравнения блоков 2 и 3, которые вырабатывают сигналы, поступающие на элемент И 6, формирующий сигнал

"Ошибки нет", запоминаемый в триггере IO. На этом работа устройства прекращается.

Если при передаче информации происходит ошибка, то после прохожде) 2495 ния И разрядов информационной после довательности через сдвиговые регист ры блоков 1-3 содержимое триггеров регистров не равно нулю, причем ошибка считается корректируемой толь- S ко в том случае, если элемент ИЛИ-НЕ вырабатывает сигнал несовпадения с нулем восьми разрядов регистра сдвига преобразователя 1 кодов и все блоки сравнения всех блоков обнаружения ошибки вырабатывают сигналы несовпадения содержимого первых и вторых регистров сдвига. Необходимо отметить, что сигналы от элемента

ИЛИ-НЕ и блоков сравнения анализируются только после приема информационной последовательности, что обеспечивается сигналом переполнения счетчика 8, запоминаемого в триггере 11.

В случае возникновения корректируемой .ошибки информация в сдвиговых регистрах преобразователя 1 кодов и блоках 2 и 3 обнаружения адреса ошибки продолжает сдвигаться. Сдвиг информации в блоке 1 продолжается до тех пор, пока в триггерах 30-37 элементом ИЛИ-НЕ не зафиксированы нули, что в силу известных свойств двучлена х -1 определяет момент располо- 30

С жения Ь =5 младших разрядах сдвигового регистра 18 пакета ошибок. С этого момента сдвиг информации в регистре 18 и во всех первых регистрах сдвига блоков 2 и 3 прекращается, что обеспечивается передачей сигнала от блока 23 через элемент И 19 и инвертор 20 на элемент И 21.

С момента обнаружения корректируемОй ошибки начинают поступать синх- 40 роимпульсы на счетчики 24 и 46 ° Накопление синхроимпульсов в счетчике

24 продолжается до момента выработки элементом ИЛИ-НЕ сигнала совпадения с нулем. Этот сигнал через элементы

19, 20 и 22 запрещает подачу синхроимпульсов на счетчик 24. В то же время сигнал с элемента 19 поступает на .коммутатор 4, разрешая тем саMblM передачу содержимого счетчика 50

24 в канал ввода-вывода. Этот переданный код представляет собой остаток бт деления номера последнего безошибочного разряда в информационной последовательности на с, т.е. i r no модулю С = 13.

С момента обнаружения корректируе( мой ошйбки сдвигается и содержимое

93 4 вторых сдвиговых регистров в блоках

2 и 3. Сдвиг и накопление синхроимпульсов в счетчиках блоков 2 и 3 продолжается до тех пор, пока блоками сравнения не обнаружено совпадение .содержимых первых и вторых триггеров в блоках, например, совпадения содер жимого триггеров 47 — 49 с 50 — 52 в блоке 2, имеющего место уже после. остановки сдвига в регистре 39. Сигнал совпадения от блока 41 через элементы 42-45 запрещает подачу синхроимпульсов на сдвиговый регистр

40 и на счетчик 46. Кроме того, сигнал с элемента И 42 является управ-, ляющим для коммутатора 4, поскольку он разрешает передачу содержимого счетчика 46 в канал. Этот переданный код также является остатком от деления номера последнего безошибочного разряда в информационной последовательности на е, =7, т.е. =- г „ по модулю е

Аналогичное преобразование инфор- мации происходит и в блоке 3. При наличии сигнала совпадения от блока сравнения этого блока содержимое его счетчика передается на коммутатор 4, причем i г по модулю е, т.е. равно 3.

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

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

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

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

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

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

1249593

Составитель О. Кулаков

Техред О.Гортвай

Корректор О. Луговая

Редактор И. Дербак

Заказ 4333/53

Тираж 543

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

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

Подписное

Производственно-полиграфическое предприятие, г. Ужгород, ул. Проектная, 4