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

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

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

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

Устройство для обнаружения ошиб-- ки кодом, задаваемым полиномом Р(х) ( х +1) (х + х+О (Xj + х+1 ), содер -жит (фиг. 1 ) преобразователь 1 кодов, блоки 2 и 3 обнаружения адреса оп-ибки, коммутатор 4. элементы И 5-7, счетчик 8, триггеры 9-11, вхо- ДЬ1 12-14 и выходы 15-17 устройства.

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

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

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

39и 40 с обратной связью, блок 41 сравнения, элемент И 42, инвертор 43, элементы И 44 и.45 и счетчик 46, Сдвиговые регистры 39 и 40 соответствуют многочлену х + х +1 и содер- жат триггеры 47 - 52 и сумматоры 53- 56 по модулю два,

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

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

V Устройство обнаружения ошибки работает следующим- образом.

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

РСХ) (х -1) Пр;(У) ,

JH

где pj(x) - неприводимый многочлен степени и порядка, равного ej {е.2 -I); С не делится на ej,

Длина кода и- равна наименьшему общему кратному (с, е, ,,,,е , Код, порожденный полиномом .Р(х) (х - и.- ).Ц pj{x, обнаруживает все пакеты

ошибок О(х) длиной d и исправляет все пакеты ошибок В(х) длиной 6Ъ при

и

условии, что c b+d-l и ,

J--1

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

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

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

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

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

: С момента обнаружения корректируемой ошибки начинают поступать синхроимпульсы на счетчики 24 и 46. Накопление синхроимпульсов в счетчике 24 продолжается до момента выработку, элементом ИЛИ-НЕ сигнала совпадения с нулем. Этот сигнал через элементы 19, 20 и 22 запрещает подачу синхроимпульсов на счетчик 24. В то же время сигнал с элемента 19 поступа- .ет на коммутатор 4, разрешая тем самым передачу содержимого счетчика 24 в канал ввода-вьшода. Этот пере- данньй код представляет собой остаток от деления номера последнего безошибочного разряда в информационной последовательности на с, т.е. is г по модулю С 13.

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

вторых сдвиговых регистров в блоках 2 и 3. Сдвиг и накопление синхроимпульсов в счетчиках блоков 2 и 3 продолжается до тех пор, пока блоками сравнения не обнаружено совпадение .содержимых первых и вторых триггеров в блоках, например, совпадения содержимого триггеров 47 - 49 с 50 - 52 в блоке 2, имеющего место уже после. остановки сдвига в регистре 39. Сигнал совпадения от блока 41 через элементы 42-45 запрещает подачу синхроимпульсов на сдвиговьй регистр 40 и на счетчик 46. Кроме того, сигнал с элемента И 42 является joipaB- ляющим для коммутатора 4, поскольку он разрешает передачу содержимого счетчика 46 в канал. Этот переданный код также является остатком от деления номера последнего безошибочного разряда в информационной последова5

0

5

0

5

0

5

на

ел

т.е. г.

Рч

по мотельностидулю е.

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

равно 3.

I ,

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

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

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

0

5

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

0 регистров соединены соответственно с первьм и вторым входами блока сравнения, выход которого соединен с первым входом третьего элемента И, второй вход которого является пятым

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

0

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