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

 

Изобретение относится к вычислительной технике, а именно к устройствам обнаружения и коррекции ошибок в запоминагашзск устройствах, и может быть применено в запоминаюш ос устройствах с последовательным доступом и высоким быстродействием. Целью изобретения является повьш ение точности обнаружения и коррекции ошибок путем использования кода Файра. Устройство содержит блок 1 обнаружения ошибок, блок 2 памяти кода ошибки, блок 3 памяти адресов ошибок, буферный блок 4 памяти, блок 5 коррекции, коммутатор 6, преобразователь 7 последовательного кода в параллельный, блок 8 Ф

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

COUHAËÈCÒÈ×ÅCÍÈХ

РЕСПУБЛИК

ÄÄSUÄÄ1372366 А1 (51)46 11 С 29 00 1

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

К ABTOPGKOMY СВИДЕТЕЛЬСТВУ

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

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ (21) 4119574/24-24 (22) 30 ° 06.86 (46) 07.02.88. Бюл. М - 5 (71) Московский энергетический институт (72) И.Н.Андреева и Г.А.Бородин (53) 681.327 (088.8) (56) Хетагуров Я.A., Руднев IG.П. Повышение надежности запоминающих устройств методами избыточного кодирования. M.: Энергия, 1974, с.76.

Зарубежная радиоэлектроника, 1985, У 7, с.11, рис. 4. (54) УСТРОЙСТВО ДЛЯ ОБНАРУИ,НИЯ И

КОРРЕКЦИИ ОШИБОК (57) Изобретение относится к вычислительной технике, а именно к устройствам обнаружения и коррекции ошибок в запоминающих устройствах, и может быть применено в запоминающих устройствах с последовательным доступом и высоким быстродействием. Целью изобретения является повышение точности обнаружения и коррекции ошибок путем использования кода Файра. Устройство содержит блок 1 обнаружения ошибок, блок 2 памяти кода ошибки, блок 3 памяти адресов ошибок, буферный блок

4 памяти, блок 5 коррекции, коммутатор 6, преобразователь 7 последовательного кода в параллельный, блок 8

13 коммутации адресов, счетчик 9 синхроимпульсов, блок 10 коммутации сигналов обращения, элемент ИЛИ 11 и блок

12 сравнения. Цель достигается за счет того, что устройство обеспечивает обнаружение ошибок разрядностью до двенадцати бит и коррекцию ошибок разрядностью до шести бит в информации, считанной из внешнего накопителя и поступающей на вход 13 в последовательном коде. В блоке 4 информация записывается параллельным кодом.

Блок 1 реализует декодирование с применением кода Файра и формирует на

72366. своих выходах сигнал наличия или отсутствия ошибки, сигнал корректируемой или некорректируемой ошибки, передает в блок 2 код пакета ошибки и в блок 3 данные для определения номера первого ошибочного байта и первого ошибочного бита в этом байте.

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

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

Целью изобретения является повышение точности обнаружения и коррекции ошибок путем использования кода

Файра.

На фиг. 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 и второй

21 синхровходы, вход 22 начальной установки устройства. Устройство также содержит формирователь 23 синхросигналов, содержащий элемент НЕ 24, генератор 25 импульсов, триггер 26 и элемент И 27.

Блок 1 обнаружения ошибок содержит (фиг.2) регистры 28-32, выполненные каждый из D-триггеров 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), счетчика 3 и блока 1. Информация в устройство поступает от

1372366

10011

110

10010

Двочный код номеНомер первого ошибочного разряда н

18-м байте ра первого uf!»fбочного байта (например, 18-ro) 1, с лец ую171п о бпятый от блока разом.

1 2 3 4 5 6 7 8 9 10 12 13 14 15 16

0 0 0 0 0 + + + + + 0 0 . 0 0 0 внешнего накопителя по входу 13 в последовательном коде на преобразователь 7 и одновременно н блок 1.

Прием информации осуществляется по синхросерии СС1, поступающей по входу 20. Частота поступления СС1 определяется частотой работы внешнего накопителя.

Преобразователь 7 формирует парал-10 лельные слова (например, байты), информацИя о которых поступает на входы блока 4 ° При этом по входу 17 на блок 4 поступает сигнал лог."0" (запись), блок 10 формирует импугьс обращения для каждого байта информации. Блок 8 н соответствии с информацией, поступа1ощей от счетчиков 9, осуществляет последовательный перебор адресов блока 4. 20

Блок 1 н да нно1! конкретно, с.fló÷àå реализует процедуру декод1»рон11 н»»я с применением кода файра с порожца1ощим полиномо."! 1 /Х/ = (Х " + 1)(Х 1+ Х + 1) (Х + ". + 1). Этот код по- 25 зноляет корректировать ош»»бк»» paзрядностью до шести бпт и об!!пру»1,!»вать ошибки разр»»дность1о до дне11лдцати бит. )1ли кода п = 1155 б1!1 при носемьнадцати пронеро»ных р;1зр»»дах. 30

Блок 1 осуществляет деки.1ирона1ние принятой l»11формации розу II>7 ëòo:1 чего явля»отся следую»1»е с»1гн1ъ;11.1: ла выходе 14 сигнаflff лог. "1" !»пи лог.

"0 соответствуют If!I 11 -I!f10 и 11 отсут35 стви1о ош1»бк11 н принятой 1»нформиции„ на выходе I 5 с!»1 наны лог. "1" If f1 1 лог. "0" соответствуют коррикт1»руемой или некорре1.тируемо11 оп!1161;е; на блок 2 поступает код пакета о:1п»бки, 40 представляю! »й собой чередование единиц и пулей н соответствии с тем, как искажена информация (разрядllocTb этого кода определяется порожда1ощим

На основе этой последовательности блок 2 размещает пакет опп»бок, приполиномом кода Файра и 1 данном примере равна шести; сигнал о том, что обнаруженная опп»бка локализована, поступающ»»й на блоки 3 и 6; данные необходимые для определения номеров ошибочных байтов, передаваемые на блок 3 ..

Таким образом, к моменту окончания приема информации, вся она размещена в блоке 4, а через определенное количество тактов (для данного порождающего полинома через 26 тактов) имеется необходимая информация для коррекции ошибки.

Передача информации на выходы 16 с одновременной коррекцией может в случае необходимости производиться с. большей частотой, поэтому в устройстве предусмотрена возможность подачи второй спнхросерии на вход 21 при

I!sf»If f1»II сигнала корректируемой ошибки, для чего испо.»ъзуется формирова1 течь 23.

На ocнове и!!формации о месте ошибки сформированный в блоке 1 блок 3 формирует: номер о1пибочного байта, номер первого ошибочного бита в байте !» номер следу»ощего байта, поскольку пакет ошибок может захватить два байта. Номер 11ерного опп»бочного бита и номер первого ошибочного байта от блока 3 вместе с пакетом оп»ибки от блока 1 поступает на блок 2. В соотнетстн1ьп с этой 1»1п11ормацией на выходы блока 2 выводятся дна байта, н

IfoTop»I:» пакет опьибок распределен необходим»ьп! образом. Например, если разрядность пакета опп»бок равна шести, а номер первого ошибочного бита н кодовой информационной последовательности ранен 142, то блок 3 вырабатывает следующую последонательI»OCTЬ

Двоичный код номера второго ошибочного байта (например, 19-го) 1372366 где + — разряд кода ошибки, соответствующий ошибочному биту в кодовой информационной последовательности.

7 8 9 10...1

1/1 78/1 10/6 87/6 19/3 97/3 29/8 106/8 39/5 116/5

27/3 104/3 36/8 113/8 46/5 123/5 56/2 133/4 65/7 142/7

53/5 130/5 63/2 140/2 73/7 5/4 82/4 15/1 92/1 24/6

79/7 12/4 89/4 22/1 99/1 31/6 108/6 41/3 118/3 50/8

5 106/1 38/6 115/6 48/3 125/3 57/8 134/8 67/5 114/5 77/2

6 132/3 64/8 141/8 74/5 7/2 84/2 16/7 93/7 26/4 103/4

7 14/2 91/2 23/7 100/7 33/4 110/4 43/1 120/1 52/6 129/6

8 40/4 117/4 50/1 126/1 59/6 136/6 69/3 69/3 1/8 78/8 11/5

9 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 35/2 112/2 44/7 121/7 54/4

1) 119/2 59/7 128/7 61/4 138/4 77/1

Кроме того, в каждом такте адрес очередного байта поступает на блок

12, на другие входы которого поступают адреса первого и второго ошибоч" ных байтов от блока 3.

До тех пор, пока адрес считываемого байта не совпадает с номерами ошибочных байтов, информация от блоПроцедура коррекции ошибок начинается подачей сигнала считывания (лог."1"), по входу 17. Наличие сигналов обращения на выходе блока 10 и адреса на выходе 19 через блок 8 обеспечивают выборку из блока 4 данных, поступающих на блок 5 для коррекции.

В блоке 3 содержится информация об адресах ошибок в соответствии с таблицей, в каждой ячейке которой указан номер ошибочного байта и соответствующий номер первого ошибочно-1О го бита (разряда) в этом байте в зависимости от содержимого К „ К и

K соответственно счетчиков 35-37

1 (фиг.2).

Заполнение памяти блока 3 в соответствии с таблицей происходит следующим образом.

Пример. Пусть содержимое К „, К, К счетчиков 35-37 равно соот- 20 ветственно 8,6,1. Для .получения номера ошибочного бита необходимо составить систему:

ix — 8 по модулю 11;

1х - 6 по модулю 15;

ix - 1 по модулю 7.

Используя исходные модули, получаем: 11х15х7 1155 = 107х11х15

165х7, причем

105х2хК, = 1 по модулю 11;

77х8хК 1 по модулю 15;

165x2xK = 1 по модулю 7

Тогда ix = 210хК < +616хК +330хК по

3 модулю 1155.

Подставляя К,К К, получаем:

ix = 210 8+616:6+330 1 1086 по модулю 1155.

По номеру первого ошибочного байта

1086:8=135,7 136 находим номер первого ошибочного разряда в байте:

8х0,76 = 6.

1372366 ка 4 без изменения передается «а выходы 16. При совпадении адреса очередного считанного байта с номером ошибочного байта, например, с восемнадцатым, блок 12 вырабатывает сигнал совпадения, и данные с выхода коммутатора 6 поступают на блок 5, в котором искаженный байт из блока 4 складывается по модулю два с посту- 1р пившим из коммутатора 6 байтом, в котором три последних разряда являются дополнением к искажениям. На выходе блока 5 получается скорректированная информация. При чтении из 15 блока 4 следующего байта срабатывает блок 12, и в блок 5 поступает через коммутатор 6 второй дополняющий байт.

Все последующие байты иэ блока 4 передаются на выходы 16 без изменения. 2р

Таким образом, обеспечивается коррекция информации при использовании кода Файра, что позволяет об«аруживать ошибки разрядностью до двенадцати бит и корректировать ошибки 25 до шести бит.

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

Устройство для обнаруже«ия и кор- Зр рекции ошибок, содержащее блок об«аружения ошибок, блок коррекции, блок памяти адресов ошибок, блок памяти кода ошибки, коммутатор и буферш»»» блок памяти, вход за »»»с»»/чте»п»я Ко торого является входом q,ïðàâëåíèÿ режимом работы устройства, »»»»формационными вь»ходам»» которого являются выходы блока коррекции, одни иэ и«формационных входов которого соединены 4р с выходами буферного блока памяти, а другие информационные входы блока коррекции подключены к выходам коммутатора, одни иэ информационных входов которого соединены с выхода- 45 ми блока памяти кода о»ш»бки, одни из адресных входов которого подключены к выходам первой группы блока обнаружения о»п»бок, выходы второй группы которого соединены с адресны- 5О ми входами блока памяти адресов oIIII»бок, о т л и ч а ю щ е е с я тем, что, с целью повьш»ения точности обнаружения и коррекции ошибок путем использования кода Файра, в него введены блок вь»бора адресов, формирователь сигналов обращен«», преобразователь последовательного кода в параллельньп», счетчик, элемент ИЛ1 и блок сравнения, одни из входов которого и одни из адресных входов блока выбора адресов являются адресными входами устройства, причем выходы счетчика соединены со счетньп»и входами блока выбора адреса и одними из тактовых входов формирователя сигналов обращения, выходы которых подключены соответственно к адресным входам и входу обращения буферного блока памяти, вход записи/чтения которого соединен с входом запуска блока выбора адреса и первым входом запуска формирователя сигналов обраще«ия, второй вход запуска которого является входом обраще«ия устройства, информационные входы буферного блока памяти подключе«ы к выходам преобразователя последователь«ого кода в пар ялл ел ь нь»й, и нфо рма ц»»о н»»ь»»» вход которого и информационный вход блока об«аружепия ошибок объединены и являются »информационным входом устройства, первый вход элеме«та 1ПИ и входы синхронизации счет шка, блока выбора адреса, формирователя сигналов обраще«ия и преобразователя последовательного кода в параллель«ый объединены и являются »»ервь»»» синхровходом устройства, вторым синхровходом которого является второй вход элемента ИЛИ, выход которого подключен к входу синхронизации блока обнаружения ошибок, первый вь»ход которого соединен с управляющим входом коммутатора и входом обращения блошка памяти адресов ошибок, вьжодь» которого подключены к другим адресньм входам блока памяти кода ошибки и другим входам блока сравнения, выходы которого соединены с другими информационными входами коммутатора, установочные входы счетчика, блока обнарукения ошибок и блока выбора адреса объединены и явля»отся входом начальной установки устройства, второй и третий выходы блока обнаружения ошибок являются соответственно вь»ходом признака наличия ош«бкп н»»ь»ходом признака некорректпруе»ой ошибки.

1372366

1372366

Составитель Б.Зайцева

Техред А.Кравчук Корректор В.Бутяга

Редактор А.Ворович

Заказ 487/43

Тираж 590 Подписное

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

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

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