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

СОЮЗ СОВЕТСКИХСОЦИАЛ ИСТИЧЕСНРЕСПУБЛИК 137(19) 1 С 29 00 ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССРПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ ЕНИ АВТОРСКОМУ СВИДЕТЕЛЬСТВУ(57) Изобретение относится к вычислительной технике, а именно к устройствам обнаружения и коррекции ошибок в 119574/24-20.06.867.0288. Бюлосковский э У 5ергетический инст х, и можетнающих устрой строист в заломи(56) Хетагуров Я.А Руднев Ввышение надежности запоминаюройств методами избыточного кодирования. М,: Энергия, 1974, с.76.Зарубежная радиоэлектроника, 1985 У 7, с.11, рис. 4.,П. Пощих усти ошибок путем ра, Устройство ения ошибок,ода ошибкошибок, б5 коррекции(54) УСТРОЙСТВО КОРРЕКЦИИ ОШИБО ОБНАРУЖЕ ователь 7 параллель(22) (46) (71) тут (72 (53 САНИЕ ИЗО з апоминающих быть применен ствах с посл и высоким быс бретения явля обнаружения и едовательнь тродействи ется повыш коррекци кода Фай 1 обнаруж использования содержит блок блок 2 памяти памяти адресо 4 памяти, бло тор 6, преобр тельного кода блок 3 ерный блок коммутаоследоваый, блок 813 коммутации адресов, счетчик 9 синхроимпульсов, блок 10 коммутации сигналов обращения, элемент ИЛИ 11 и блок 12 сравнения. Цель достигается за счет того, что устройство обеспечивает обнаружение ошибок разрядностью до двенадцати бит и коррекцию ошибок разрядностью до шести бит в информации, считанной из внешнего накопителя и поступающей на вход 13 в последовательном коде, В блоке 4 информация записывается параллельным кодом. Блок 1 реализует декодирование с применением кода Файра и формирует на 72366,своих выходах сигнал наличия или отсутствия ошибки, сигнал корректируемой или некорректируемой ошибки, передает в блок 2 код пакета ошибки и в блок 3 данные для определения номера первого ошибочного байта и первого ошибочного бита в этом байте.Блок 12 осуществляет сравнение номеров ошибочных байтов с текущим адре" сом чтения нз блока 4 при их совпадении формирует сигнал, включающий коррекцию считанной информации в блоке 5. 1 табл.,6 ил.1Изобретение относится к вычислительной технике, а именно к устройствам обнаружения и коррекции ошибок в запоминающих устройствах, и может быть использовано в запоминаю щих устройствах с последовательным доступом повышенного быстродействия.Целью изобретения является повышение точности обнаружения и коррекции ошибок путем использования кода Файра.На фиг. 1 представлена структурная схема предлагаемого устройства; на фиг, 2 - 6 - функциональные схемы наиболее предпочтительных вариантов реализации соответственно блока обнаружения ошибок, блока выбора адреса, блока коммутации сигналов обращения, блока памяти адресов ошибок и коммутатора.Устройство содержит (фнг.1) блок 2 памяти кода ошибки,.блок 1 обнаружения ошибок, блок 3 памяти адресов ошибок, буферныйблок 4 памяти, блок 5 кор-. рекции, коммутатор 6, преобразователь 7 последовательного кода в параллельный блок 8 выбора адреса,счетчик 9, формирователь 10 сигналов обращения, элемент ИЛИ 11, блок 12 сравнения. На фиг. 1 обозначены информационный вход 13, выход 14 призна. ка наличия ошибки, выход 15 признака некорректнруемой ошибки, информационные выходы 16, вход 17 управления режимом работы, вход 18 обращения, 35 адресные входы 19, первый 20 и второй 221 синхровходы, вход 22 начальной установки устройства. Устройство также содержит формирователь 23 синхросигналов, содержащий элемент НЕ 24, генератор 25 импульсов, триггер 26 и элемент И 27.Блок 1 обнаружения ошибок содержит (фиг.2) регистры 28-32, выполненные каждый из Р-триггеров 33 и формирователя 34 четности, счетчики 35-38, блоки 39 и 40 сравнения, элементы И 41-47 и ИЛИ-НЕ 48-50, элементы 51 и 52, элемент ИЛИ 53 и триггеры 54 и 55.Блок 8 выбора адреса содержит (фиг,3) счетчик 56, коммутатор 57 и элемент И 58.Блок 10 коммутации сигналов обращения содержит (фиг.4) элемент И 59, коммутатор 60, элемент 61 задержки и формирователь 62 сигналов обращения. На фиг. 5 и 6 показаны элементы 63-67.В качестве блока 2 памяти кода ошибки и блока 3 памяти адресов оши. - бок могут быть применены, например, блоки постоянной памяти. В таблице представлен фрагмент таблицы истинности работы блока 3.Устройство работает следующим образом.Перед приемом информации от внешнего накопителя (не показан) по вхо-, ду 22 производится обнуление блока 8 (фиг.1), счетчикаи блока 1. Информация в устройство поступает от1372366 10011 110 10010 Двочцый код номе Номер первого ошибочного разряда в18-м байте ра первого о 11 п 1 бочного байта(например, 18-го) 1, следую 171 ь 1 обпятый от блокаразом: 1 2 3 4 5 6 7 8 9 10 12 13 14 15 160 0 0 0 О + + + + + 0 0,0 0 0 внешнего накопителя по входу 13 впоследовательном коде на преобразователь 7 и одновременно в блок 1.Прием информации осуществляется посинхросерии СС 1, поступающей по входу 20. Частота поступления СС 1 определяется частотой работы внешнего накопителя,Преобразователь 7 формирует парал лельные слова (например, байты),информацця о которых поступает навходы блока 4. При этом по входу 17на блок 4 поступает сигнал лог."0"(запись), блок 10 формирует импугьс 15обращения для каждого байта информации, Блок 8 в соответствии с информацией, поступа 1 ощей от счетчиков 9,осуществляет последовательный перебор адресов блока 4. 20Блок 1 в данном конкретном спучаереализует процедуру декодироваьп 1 яс применением кода Файра с порожда 1 ощим полиномо."1 /Х/ = (Х и + 1)(Х1.+ Х + 1) (Х 5 + Х + 1), Этот код позволяет корректировать о 1 п 51 бки разрядцостью до шести бцт и обциру 51 сцвать ошибки разр 51 дность 1 о до двенадцати бцт. Длц кода п = 1155 б 11 г привосемьнадцати проверочных р;1 зр 51 дах, 30Блок 1 осуществляет деко 11 ироганцеприц 51 той информациирозу 11)тлтй:1чего явля 1 отся следу 1 о 111 це сцгн;ь;нц: цавыходе 14 сигналы лог, "1" или лог."0" соответствуют нц цнццо цпц отсут 35стви 1 о ошибки в нрцнятоц 1151 форма 15 ицна выходе 15 сц," нилы лог. "1" цл 11лог. цО" соответствуют корр .ктируемой или некорре 1.тируемой ошибке; цаблок 2 поступает код пакета о;п 1 бки, 40представляю 1 п 1 й 1 собой чсредоваьп 1 еединиц и пулей в соответствии с тем,как искажена информация (разрядностьэтого кода определяется порожда 1 оп 1 ц 11 На основе этой последовательностиблок 2 размещает пакет опп 1 бок, приполицомом кода Файра и 1 данном примере равна 1 пестц; сигнал о том, что обнаруженная опп 1 бка локализована, поступающий ца блоки 3 и 6; данные необходимые для определения номеров ошибочных байтов, передаваемые на блок 3.Таким образом, к моменту окончания приема информации, вся она размещена в блоке 4, а через определенное количество тактов (для данного порождающего полинома через 26 тактов) имеется необходимая информация дчя коррекции ошибкиПередача информации на выходы 16 с одновремеш 1 ой коррекцией может в случае необходимости производиться с. большей частотой, поэтому в устройстве предусмотреца возможность подачи второй сццхросерии на вход 21 при цал 11 чци сигнала корректцруемой ошибки, для чего испо;1 ъзуется формирователь 23.На основе информации о месте ошибки сформ 11 ровацц 1 п 1 в блоке 1 блок 3 формирует: цомер о 1 пцбочцого байта, номер первого опибочцого бита в байте ц номер следу 1 ощего байта, поскольку пакет оп 1 цбок может захватить два байта. Номер первого опп 5 бочцого бита ц номер первого ошибочного байта от блока 3 вместе с пакетом ошибки от блока 1 поступает ца блок 2, В соот" ветств 1 ьц с этой иц 15 ормацией на выходы блока 2 выводятся два байта, в которьгс пакет опьцбок распределен необходимым образом, Например, если разрядность пакета оцп 1 бок равна шести, а номер первого ошибочного бита в кодовой информационной последовательности равен 142, то блок 3 вырабатывает следующую последовательноспьДвоичный код номера второгоошибочного байта (например,19-го)1372366 где + - разряд кода ошибки, соответствующий ошибочному биту в кодовойинформационной последовательности,В блоке 3 содержится информация об адресах ошибок в соответствии с таблицей, в каждой ячейке которой указан номер ошибочного байта и соответствующий номер первого ошибочноО го бита разряда) в этом байте в зависимости от содержимого К К . и К соответственно счетчиков 35-37 (фиг.2). 15Заполнение памяти блока 3 в соответствии с таблицей происходит сле" дующим образом.П р и м е р. Пусть содержимое К , К, К счетчиков 35-37 равно соот ветственно 8,6,1, Для получения но 7 8 9 10/1 78/1 10/6 87/ 9/8 106/8 39/5 116/5.6/2 133/4 65/7 142/7 93 97 27/3 104/3 36/8 113/8 46/5 123/ 3/2 140/2 73/7 5/4 82/4 15/1 92/1 24/6 53/5 130/ 79/7 12/ 9/1 31/6 108/6 41/3 118/3 50/ 89/4 22/ 15/6 48/3 125/3 57/8 134/8 6 14/5 77 5 106/1 38/б 6 132/3 64/8 7/2 84/2 16/7 93/7 26/4 103/4 41 8 7 100/7 33/4 110/4 43/1 120/1 52/6 129/6 4/2 91/2 9/6 136 69/3 69/3 1/8 78/8 11/5 40/4 117/4 5 12 66/6 147/6 76/3 64/8 85/8 18/5 95/5 28/2 105/2 37/7 10 92/8 25/5 102/5 3 112/2 44/7 121/7 54/4138/4 77/1 128/7 6 1 119/2 5 анПроцедура коррекции ошибок начинается подачей сигнала считывания (лог."1"), по входу 17. Наличие сиг налов обращения на выходе блока 10 и адреса на выходе 19 через блок 8 обеспечивают выборку из блока 4 д ных, поступающих на блок 5 для коррекции. мера ошибочного бита необходимо составить систему:1 х, - 8 по модулю 11;1 х- б по модулю 15;х по модулю 7.Используя исходные модули, получаем: 11 х 15 х 7 1155 = 107 х 11 х 15165 х 7, причем105 х 2 хК, = 1 по модулю 11;77 х 8 хК 1 по модулю 15;165 х 2 хК = 1 по модулю 7Тогда дх = 210 хК+616 хК+330 хК поЭ модулю 1155.Подставляя К,К К , получаем:1.х = 210 8+616:6+330 11086 по модулю 1155.По номеру первого ошибочного байта 1086:8=135,7,. 136 находим номер первого ошибочного разряда в байте: 8 х 0,76 = 6. Кроме того, в каждом такте адрес очередного байта поступает на блок 12, на другие входы которого поступают адреса первого и второго ошибоч ных байтов от блока 3,Ло тех пор, пока адрес считываемого байта не совпадает с номерами ошибочных байтов, информация от бло 1372366ка 4 без изменения передается ца выходы 16, При совпадении адреса очередного считанного байта с номером ошибочного байта, например, с восемнадцатым, блок 12 вырабатывает сигнал совпадения, и данные с выхода коммутатора 6 поступают на блок 5, в котором искаженный байт из блока 4 складывается по модулю два с посту пившим из коммутатора 6 байтом, в котором три последних разряда являются дополнением к искажениям. На выходе блока 5 получается скорректированная информация. При чтении из 15 блока 4 следующего байта срабатывает блок 12, и в блок 5 поступает через коммутатор 6 второй дополняющий байт. Все последующие байты из блока 4 передаются на выходы 16 без изменения. 20Таким образом, обеспечивается коррекция информации при использовании кода Файра, что позволяет обнаруживать ошибки разрядностью до двенадцати бит и корректировать ошибки 25 до шести бит.Формула изобретенияУстройство для обнаружения и кор рекции ошибок, содержащее блок обнаружения ошибок, блок коррекции, блок памяти адресов ошибок, блок памяти кода ошибки, коммутатор и буферц, блок памяти, вход эапс/чтец которого является входом управлеця режимом работы устройства, формационными вьходам которого являются выходы блока корре(ц, одни из ицформациоцньх входов котоРого соединены 40 с выходами буФерного блока памяти, а другие информационные входы блока коррекции подключены к выходам коммутатора, одни из информационных входов которого соединены с выхода ми блока памяти кода ошибки, одни из адресных входов которого подключены к выходам первой группы блока обнаружения опбок, выходы второй группы которого соединены с адресны ми входами блока памяти адресов ош- бок, о т л и ч а ю щ е е с я тем, что, с целью повышения точности обнаружения и коррекции ошибок путем использования кода Файра, в него введены блок выбора адресов, формрователь сигналов обращея, преобразователь последовательного кода впараллельньп, счетчик, элемецт ИБ 1и блок сравнения, одни из входов которого и одни из адресных входовблока выбора адресов являются адресными входами устройства, причем выходы счетчика соединены со счетцьпивходами блока выбора адреса и одними из тактовых входов формирователясигналов обращения, выходы которыхподключены соответственно к адреснымвходам и входу обращения буферногоблока памяти, вход записи/чтения которого соединен с входом запускаблока выбора адреса и первым входомзапуска формирователя сигналов обращения, второй вход запуска которогоявляется входом обращения устройства, информационные входы буФерногоблока памяти подключены к выходампреобразователя последовательногокода в паряллельцьй, информационныйвход которого и инФормационный входблока обнаружения ошибок объединеныи язляются пформационным входомустройства, первый вход элемента 1 ПИи входы синхронизации счетчка, блока выбора адреса, формирователя сигналов обращения и преобразователяпоследовательного кода в параллельный объединены и являются ервьсинхровходом устройства, вторым сцнхровходом которого является второйвход элемента ИЛИ, выход которогоподключен к входу синхронизации блока обнаруженя ошибок, первый вьходкоторого соединен с управляющим входом коммутатора и входом обращенияблока памяти адресов ошибок, вьжодькоторого подключены к другим адресньм входам блока памяти кода ошибкии другим входам блока сравнения, выходы которого соединены с другимиинФормационными входами коммутатора,установочные входы счетчика, блокаобнаружения ошибок и блока выбораадреса объединены и являотся входомначальной установки устройства, второй и третий выходы блока обнаружения ошибок являются соответственновьходом признака наличия ошибки цзьходом признака некорректцруеой ошибки.1372366 Составитель Б.ЗайцеваТехред А.Кравчук Коррект Бутяга Редакт орович аказ 487/43 Подпис го ком о ушска оизводственно-полиграфическое предприятие, г,ужгород, ул.Проектн Тираж 590ВНИИПИ Государстве по делам изобрет13035, Москва, Ж,еета СССРытийаб д. 4/5