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

(9) О 1 4011 С ИСАНИЕ ИЗОБРЦТЕ ЕЛЬСТВУ ОШИ ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССРПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТИЙ АВТОРСКОМУ СВИ(7) Московский ордена Ленина и ордена Октябрьской Революции энергети.ческий институт(56) Введение в запоминающие устройства прямого доступа и методы организации данных./Под ред. Г.К. Столярова. - М.: Статистика, 1974, с. 12.Хетагуров Я.А., Руднев Ю.П. Повышение надежности запоминающих устройств методами избыточного кодирования. - М Энергия, 1974, с. 71.Патент США У 4216541, кл. 365/15,опублик. 1980,(54) УСТРОЙСТВО ДЛЯ ОБНАРУЖЕНИЯБОК В БЛОКАХ ПАМЯТИ(57) Изобретение относится к областивычислительной техники и может бытьиспользовано для обнаружения ошибокв запоминающих устройствах с последовательным доступом. Устройство содержит преобразователь 1 кодов, блоки 2 и 3 обнаружения ацреса ошибки,коммутатор 4 и логические элементы.Изобретение позволяет повысить быстродействие устройства за счет сокращения времени на обнаружение адреса ошибки. 1 з.п. ф-лы, 3 ил.1 12Изобретение относится к вычислительной технике, а именно к устройствам для обнаружения ошибок в запо ,минающих устройствах и может быть использовано для обнаружения ошибок в запоминающих устройствах с после- . довательным доступом повышенного быстродействия.Цель изобретения - повышение быстродействия устройства.На фиг. представлена структурная схема устройства; на фиг. 2 функциональная схема преобразователя кодов; на фиг, 3 - функциональная схема блока обнаружения адреса ошибки.Устройство для обнаружения ошибки кодом, задаваемым полиномом Р(х) = =(х" +1) (х З + х+1) (х + х+1 ), содер. ,жит (фиг. 1 ) преобразователь 1 кодов, блоки 2 и 3 обнаружения адреса ошибки, коммутатор. 4. элементы И 5-7, счетчик 8, триггеры 9"11, входы 12-14 и выходы 15-1 устройства.Преобразователь 1 кодов (фиг, 2) содержит сдвиговый регистр 18 с обратной связью, элемент И 19, инвер тор 20, элементы И 21 и 22, ИЛИ-НЕ 23 и счетчик 24. Сдвиговый регистр 18 соответствует двучлену х+1. Он содержит триггеры 25-37 и сумматор 38 по модулю два.Блок 2 обнаружения адреса ошибки (фнг. 3) содержит сдвиговые регистры 39 и 40 с обратной связью, блок 41 сравнения, элемент И 42, инвертор 43, элементы И 44 и. 45 и счетчик 46. Сдвиговые регистры 39 и 40 соответствуют многочлену х ++1 и содержат триггеры 47 - 52 и сумматоры 53- 56 по модулю два.Блок 3 обнаружения адреса ошибки имеет точно такую же структуру, что и блок 2. Но, поскольку он соответствует многочлену М ++1, его сдви,говые регистры содержат по два триггера (что соответствует степени многочлена) и по два сумматора по модулю два, что соответствует количеству ненулевых членов хПри изменении количества сомножителей и порождающем полиноме Р(х) в устройстве увеличивается количество блоков обнаружения адреса ошибки, отличающихся друг от"друга количеством триггеров и сумматоров по модулю . два в сдвиговых регистрах.. Устройство обнаружения ошибки ра-ботает следующим образом. 49593 2 Пусть порождающий полинам кода задан следующим выражением:йР(х) = (х -1) р, Ь),1-.15где р,(х) - неприводимый многочленстепе)и 8 и порядка, равного е(е =2-1 ); С не делится на е; .Длина кода й равна наименьшемуобщему кратному (с, ее . Код,порожденный полиномом,Р(х) =(хфв- 1) П р (х), обнаруживает все пакеты4 ошибок О(х) длиной с Й и исправляетвсе пакеты ошибок В(х) длиной 6 Ь прифусловии, что с) Ь+йи Ь:СХНа фиг. приведен пример построения устройства для обнаружения ошибки кодом Р (х) = (х +1) х + х+1)(х + х+1), Длина кода о = 273. Выполнение процедуры декодирования начинается с обнуления по входу 13 д блоков 1-3 и 8-11, При приеме информации от накопителя все разряды, начиная с 256 информационных, по входуустройства 12 поступают на первыевходы преобразователя 1 кода и блоков 2 и 3 обнаружения адреса ошибки (на вторые регистры сдвига). Напервые регистры сдвига блоков 2 и 3информация поступает с пятого триггера регистра сдвига блока 1, Всерегистры сдвига работают синхронно,что обеспечивается подачей синхроимпульсов по входу 14 устройствачерез элементы И 21 и 44.На первом этапе работы устройства, т.е. на этапе деления информационного многочлена на соответствующие составляющие порождающего полинома, в сдвиговых регистрах блоков1-3 Формируются остатки от деления.Если ошибки не происходит, топосле прохождения и бит кодовогомногочлена (информационной последовательности ) через сдвиговые регистры блоков 1-3 содержимое триггеров 50регистров равно нулю. Это фиксируется элементом ИЛИ-НЕ 23 и блокамисравнения блоков 2 и 3, которыевырабатывают сигналы, поступающиена элемент И 6, формирующий сигналОшибки нет", запоминаемый в триггере 10. На этом работа устройствапрекращается.Если при передаче информации происходит ошибка, то после прохожде12495 ния И разрядов информационной последовательности через сдвиговые регистры блоков 1-3 содержимое триггероврегистров не равно нулю, причемошибка считается корректируемой только в том случае, если элемент ИЛИ-НЕвырабатывает сигнал несовпадения снулем восьми разрядов регистра сдвига преобразователя 1 кодов и всеблоки сравнения всех блоков обнаружения ошибки вырабатывают сигналынесовпадения содержимого первых ивторых регистров сдвига. Необходимоотметить, что сигналы от элементаИЛИ-НЕ и блоков сравнения анализируются только после приема информаци -онной последовательности, что обеспечивается сигналом переполнениясчетчика 8, запоминаемого в триггере 11,В случае возникновения корректируемой .ошибки информация в сдвиговыхрегистрах преобразователя 1 кодов иблоках 2 и 3 обнаружения адреса ошибки продолжает сдвигаться. Сдвиг информации в блоке 1 продолжается дотех пор, пока в триггерах 30-37 элементом ИЛИ-НЕ не зафиксированы нули,что в силу известных свойств двучлена х -1 определяет момент расположения Ь =5 младших разрядах сдвигового регистра 18 пакета ошибок. Сэтого момента сдвиг информации в регистре 18 и во всех первых регистрахсдвига блоков 2 и 3 прекращается,что обеспечивается передачей сигналаот блока 23 через элемент И 19 и инвертор 20 на элемент И 21.С момента обнаружения корректируе.мОй ошибки начинают поступать синхроимпульсы на счетчики 24 и 46Накопление синхроимпульсов в счетчике24 продолжается до момента выработкиэлементом ИЛИ-НЕ сигнала совпаденияс нулем, Этот сигнал через элементы 4519, 20 и 22 запрещает подачу синхроимпульсов на счетчик 24. В то жевремя сигнал с элемента 19 поступает на .коммутатор 4, разрешая тем самым передачу содержимого счетчика 5024 в канал ввода-вывода. Этот переданный код представляет собой остатокбт деления номера последнего безошибочного разряда в информационной последовательности на с, т.е, 3. г помодулю С = 13,С момента обнаружения корректируе(мой ошйбки сдвигается и содержимое 93 4вторых сдвиговых регистров в блоках 2 и 3. Сдвиг и накопление синхроимпульсов в счетчиках блоков 2 и 3 продолжается до тех пор, пока блоками сравнения не обнаружено совпадение ,содержимых первых и вторых триггеров в блоках, например, совпадения содер жимого триггеров 47 - 49 с 50 - 52 в блоке 2, имеющего место уже после. остановки сдвига в регистре 39. Сигнал совпадения от блока 41 через элементы 42-45 запрещает подачу синхроимпульсов на сдвиговый регистр 40 и на счетчик 46. Кроме того, сигнал с элемента И 42 является управ-, ляющим для коммутатора 4, поскольку он разрешает передачу содержимого счетчика 46 в канал. Этот переданный код также является остатком от деления номера последнего безошибочного разряда в информационной последовательности на е, =7, т,е. ы гпо модулю еАналогичное преобразование инфор- мации происходит и в блоке 3. При наличии сигнала совпадения от блока сравнения этого блока содержимое его счетчика передается на коммутатор 4, причем 1 г г по модулю е , т.е. равно 3.1Три переданных остатка однозначно определяют номер последнего безошибоч. ного разряда в информационной после",. довательности, что. и позволяет начать коррекцию. Формула изобретения 1, Устройство для обнаружения ошибок в блоках памяти, содержащее преобразователь кодов, первый, второй и третий входы которого являются первым, вторым и третьим входами устройства, а его выходы первой группы соединены с входами первой группы коммутатора, и первый элемент И, о т л и ч а ю щ е е с я тем, что, с целью повышения быстродействия устройства,оно содержит блоки обнаружения адреса ошибки, первый, второй и третий триггеры, счетчик, второй и третий элементы И, причем первый, второй и третий входы каждого блока обнаружения адреса ошибки соединены соответственно с первым, вторым и третьим входами устройства, а их четвертые входы соединены с первым выходом преобразователя ко 1249593дов, второй выход которого а такжепервые выходы блоков обнаруженияадреса ошибки соединены с входамипервого элемента И, выход которогосоединен с первым входом первоготриггера, выход которого являетсяпервым выходом устройства, третийвыход преобразователя кодов и второйвыход каждого блока обнаружения адреса ошибки соединены соответственнос управляющими входами коммутатораи входами второго элемента И, выходкоторого соединен с первым входомвторого триггера, выход которого является вторым выходом устройства,выходы второй группы преобразователя кодов и выходы группы блоков обнаружения адреса ошибки соединены ссоответствующими входами групп коммутатора, выходы которого являютсявыходами группы устройства, вторыевходы первого, второ о и третьеготриггеров, а также первый вход счетчика соединены с вторым входом устройства, первый вход третьего элемента И соединен с третьим входомустройства, второй вход третьегоэлемента И соединен с инверсным выходом третьего триггера, выход третьего элемента И соединен с вторымвходом счетчика, выход которого соединен с первым входом третьего тригрега, прямой выход которого соединенс пятым входом каждого блока обнаружения адреса ошибки и четвертымвходом преобразователя кодов, четвертый выход которого соединен сшестыми входами блоков обнаруженияадреса ошибки,2. Устройство по п, 1, о т л ич а ю щ е е с я тем, что блок обнаружения адреса ошибки содержит первый и второй сдвиговые регистры,блок сравнения, счетчик, элементы Ии инвертор, причем первый вход первого сдвигового регистра являетсяпервым вхбдом блока обнаружения адре.са ошибки, второй вход первого сдвигового регистра соединен с первымвходом второго сдвигового регистраи является вторым входом блока, первый вход первого элемента И соединенс первым входом второго элемента Ии является третьим входом блока, второй вход второго сдвигового регистраявляется четвертым входом блока,выходы первого,и второго сдвиговых о регистров соединены соответственнос первым и вторым входами блока срав.нения, выход которого соединен спервым входом третьего элемента И,второй вход которого является пятым д входом блока, выход третьего элемента И соединен с входом инвертора,установочный 1 вход счетчика соединенс первым входом второго сдвиговогорегистра, выход инвертора соединенс вторыми входами первого и второгоэлементов И, выход первого элементаИ соединен с третьим входом второгосдвигового регистра, а выход второгоэлемента И соединен с синхровходомсчетчика, третий вход первого сдвигового регистра является шестым входом блока обнаружения адреса ошибки,выходами которого являются выходысчетчика, третьего элемента И и инвертора.1249593 оставитель О. Кулакоехред О.Гортвай Корректор О. Лугов Редактор И, ДерЗаказ 4333/53 Тираж 543 ВНИИПИ Государственного комитета С по делам изобретений и открытий 113035, Москва, Ж-.35, Раушская наб