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

 

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

СОЦИАЛИСТИЧЕСКИХ

РЕСПУБЛИН

А1

0% (И): (504 G 11 29 00 «Щ Р

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

fi A8TOPOMOMV СВИДЕТТЛУСТВУ.

$P

«М .: М, ""..ТУ

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

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ (21) 3861634/24-24 (22) 28. 02. 85 (46) 15.09.86.Бюл. В 34 (71) Московский ордена Ленина и ордена Октябрьской Революции энергетический институт (72) И.Н.Андреева и Г.А.Бородин (53) 681.327(088.8) (56) Питерсон, Уэлдон. Коды, исправляющие ошибки. М.:Мир, 1976, с.401.

Патент США В 4216541, кл.365/15, 1980. (54) УСТРОЙСТВО ДЛЯ КОРРЕКЦИИ ОШИБОК

В.БЛОКАХ ПАМЯТИ (57) Устройство относится к вычислительной технике и предназначено для обнаружения и коррекции ошибок в блоках памяти, выполненных на сдвиговых регистрах, таких как 3У на цилиндрических магнитных доменах (ЦМД). и приборах с зарядовой связью (ПЗС).

Целью изобретения является повышение быстродействия устройства. Устройство содержит блок кодирования, формирователь сигналов записи, блок декодирования, счетчик, усилитель считывания, блок местного управления. Повышение быстродействия достигается введением двух накопителей, блока управления, элементов И-ИЛИ, И, НЕ, регистров, счетчика и группы элементов И, что позволяет исключить повторное обращение к слову, в котором повторно обнаружена ошибка, а также за счет одновременного синхронного преобразования информации при декодировании. 3 з.п.ф-лы, 4 ил °

1257708

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

° (ЗУ) йа цилиндрических магнитных доменах (ЦМД) и приборах с зарядовой связью (ПЗС) .

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

На фиг.1 представлена функциональная схема предлагаемого устройства; на фиг.2 — функциональные схемы наиболее предпочтительных вариантов выполнения. блока декодирования, блока управления и блока местного управления блока декодирования соответственно.

Устройство содержит (фиг.l) блок

1 местного управления, блок 2 кодирования, формирователь 3 сигналов записи, блок 4 памяти. Устройство содержит также усилитель 5 считыва ния, блок 6 декодирования, блок 7 управления, первый 8 и второй 9 накопители, элемент ИЛИ 10 элементы

И-ИЛИ 11, первый регистр 12, группу элементов И 13, второй регистр 14, первый счетчик 15, элемент НЕ l6, элемент И 17, второй счетчик 18 и коммутатор 19, входы 20 и 21, первый управляющий выход 22, выходы 23 и второй управляющий выход 24 блока

6 декодирования, выходы 25-29, третий 30 и четвертый 31 входы блока 7 управления и установочные входы 33 и 34 первого счетчика 15. Блок 6 декодирования содержит (фиг.2) блок 35 местного управления, первый 36 и вто4О рой 37 преобразователи кода, первый

38 и второй 39 блоки сравнения, первый 40 и второй 41 счетчики и элемент И 42, выходы 43-49 с первого по седьмой и выходы 50-54 с третьеII"o по седьмой блока 3 местного управ45 ления блока декодирования.

Блок 7 (фиг.3) управления содержит первый 55 и второй 56 элементы задержки, генератор 57 синхроимпульсов, первый 58 и второй 59. элементы

И, элемент НЕ 60, триггеры .61-63 с первого по третий, элемент И-ИЛИ 64 и элемент ИЛИ 65.

Блок 35 местного управления блока декодирования содержит (фиг.4)формирователь 66 синхроимпульсов, счетчик 67, первый 68 и второй 69 элементы ИЛИ, элемент И 70, элементы

И-HF 71-75 с первого по пятый, элементы HE 76-79 с первого по четвертый, регистры 80-83 с первого по четвертый, третий элемент ИЛИ 84 и триггер 85.

Проверяемый блок 4 памяти.(ЦИДприбор) формирователь 3 сигналов записи и усилитель 5 считывания могут быть выполнены на микросхемах К1

602 РЦ2. Емкость накопителя 9 равна

NxC бит (где N — предельно допустимое число ошибок в блоке 4 до перехода его на профилактический режим работы, а С вЂ” разрядность считываемого из него слова).

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

Предлагаемое устройство работает следующим образом.

При записи информации в блок 4 данные от блока (фиг.l) поступают в блок 2, а затем через формирователь 3 они поступают на выход устройства. При считывании информация из блока 4 через усилитель 5 поступает в блок 6 ° До начала работы происходит обнуление регистров 12 и

14 (сигнал на чертеже не показан).

После того, как будет принят последний бит считанной информации, блок.

6 выдает сигнал с выхода 24, по которому блок 7 вырабатывает сигнал обращения 26 к накопителю 8 и сигнал записи-чтения 25 к накопителям 8 и

9. В то же время адрес считываемой последовательности поступает с выхо.— дов блока 1 на вход накопителя 8, а с его выхода считываемая информация передается на элемент ИЛИ 10. Запись информации в накопитель 8 организована так, что если в течение рабочего периода блок 4 (до профилактического цикла) в слове по лю.бому из адресов обнаруживается ошибка, то по данному адресу в накопитель 8 записывается двоичный номер этой ошибки.

Подсчет числа ошибок за рабочий период происходит в счетчике 18.

1257

Время рабочего периода устанавливается по входу 33. Если за время рабочего периода не набрано установленное количество ошибок, то обнуление счетчика 15 происходит по входу 33 ("время"). Если в какой-то момент времени содержимое счетчика 15 становится равным некоторому предельно допустимому, то блок 4 переводит-. ся на профилактический режим работы по сигналу переполнения счетчика 15 на выходе 32; а счетчик 15 устанавливается в ноль по входу 34.

Предположим, что с начала рабочего периода еще не было обнаружено 15 ни одной ошибки. Считанная из накопителя 8 нулевая информация поступает по входу 31 на блок 7, в то же время считанная из блока 4 информация декодируется в блоке 6. Сигнал 20 о наличии или отсутствии ошибки поступает от блока 6 по выходу 22 в блок 7. Если в декодированной информации обнаружена ошибка, то блок 7 вырабатывает сигнал по выходу 27 (ошибки по данному адресу с начала рабочего периода не было). В этом случае необходимо запомнить факт обнаружения первой ошибки по данному адресу, записать в накопитель 8 по 30 данному адресу код ошибки и запомнить в накопителе 9 скорректированное слово.

Факт обнаружения ошибки запоминается путем изменения содержимого 35 счетчика 15 на единицу. При этом сигнал ошибки поступает-на элемент И 17

У а сигнал отсутствия ошибки по данному адресу до последнего обращения к блоку 4 через элемент НЕ 16 поступа- 40 ет с выхода элемента ИЛИ 10 иа вход элемента И 17, разрешая .изменение со. держимого счетчика 15.. Запись кода ошибки по данному адресу в накопи-. тель 8 происходил при наличии второ- 45 го сигнала обращения к нему, который через элементы 55 и 56 задержки (фиг.3) и элемент ИЛИ 65 поступает на выход 26. Содержимое счетчика 15 поступает на информационный вход íà" SO копителя 8 и по соответствующему адресу осуществляется запись кода ошибки. Декодированное в блоке 6 слово передается в блок i при наличии управляющего сигнала 27 и одновременно 55 поступает на запись в накопитель 9 через элементы И 13, управляемые сигналом 27 и в регистр 14. Сигнал

708 4 обращения к накопителю 9 вырабатывается на выходе 29 генератором 57.

Эти же сигналы изменяют содержимое счетчика 18. Адрес каждого слоя задается содержимым счетчика 15 (если ошибка по данному адресу произошла впервые) или содержимым, считанным из накопителя 8, (еспи ошибка по данному адресу уже была). Эта информация через элементы И-ИЛИ 11 поступает на регистр 12. Счетчик 18 задает адреса, по которым размещаются отдельные группы слова. Сигнал переполнения счетчика 18 постугает по входу 30 и снимает сигналы 25, 26, 27 и 29.

Если к блоку 4 производится обращение по адресу, по которому записано слово, в котором уже была обнаружена ошибка, и блок 6 снова фиксирует ошибку в этом слове, тогда из накопителя 8 считывается код ошибки по данному адресу. Эта информация определяет.следующие этапы работы системы: ненулевой сигнал 31 с элемента ИЛИ 10 запрещает прохождение сигнала ошибки из блока б на счетчик 15, т.е. эта обнаруженная ошибка не фиксируется как новая; ненулевой, сигнал с элемента ИЛИ !О вместе с сигналом ошибки 22 от блока 6 преобразуются в блоке 7 в сигнал 28 (ошибка по данному адресу за время рабочего периода была); сигнал 28 разрешает прохождение информации из накопителя 8 через элементы И-ИЛИ 11 на регистр

12, в результате (при наличии сигналов "Обращение (29) и "Зп/Чт" (25) уже скорректированное ранее слово считывается из накопителя 9 на коммутатор 19, сигнал 28 разрешает прохождение через коммутатор 19 информации из накопителя 9, а не из блока 6.

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

Временные затраты, связанные с исправлением ошибок при первом обращении к некоторой информации по адресу Е (обычно от 1 до 1024), сокращаются путем изменения алгоритма декодирования, реализуемого блоком б, причем увеличение скорости декодирования основано на сокращении количества сдвигов принятой информации

1257708 Ф жим„ например, что ошибка имеет место в 146-150 разрядах информационной последовательности, тогда в результате деления получатся остатки

000111110 и 10011 соответственно, Блок 38 фиксирует несовпадение содержимого пяти последних триггеров преобразователя 37 с содержимым триггеров преобразователя 36. Блок 39

10 фиксирует ненулевое содержимое первых четырех триггеров преобразователя 37. Сигналы несовпадения поступают по входам 50 и 51 в блок 35, и пройдя через элементы НЕ 76 и 77 и

- 15 элементы 72 и 73 разрешают прохожде+ ние СИ от формирователя 66 по выходам 43-46. Сигналы несовпадения от блоков 38 и 39 изменят состояние триг. гера 85 и по выходу 22 уходит сигнал

20 "Обнаружена ошибка". Поступление СИ по выходам 43 и 44 обеспечивает сдвиг информации в преобразователях 36 и з" 37 в процессе поиска местоположения р- ошибки. Сдвиг инфо, мации в блоке 37

15 продолжается до тех пор, пока в его (С-Ь) старших разрядах не будут зафиксированы нули, что в силу известных свойств двучлена х -l определяс ет момент расположения в его Ь млад30 ших разрядах пакета ошибок.

% путем одновременного синхронного преобразования инфо мацки в преобразователях 36 и 37 (фиг.2), каждый из которых соответствует одной из со ставляющих порождающего полинома кода .Файра, задаваемого формулой

Р(х) (х -1) Р, (х), где Р,(х) — неприводимый многочлен степени Ь и порядка е, причем С не делится на е, максимальное значение которого е 2 -1. Длина и кода — наименьшее общее кратное е и С. Количество контрольных разрядов равно (С+Ь).

Рассмотрим, например, работу уст" ройства для кода Файра, заданного по рождающим полином (Р(х) (х +1) (х +х

+1) и имеющего максимальную длину и 9 (2 -1)=279. Этот код исправит

5 произвольный пакет ошибок длиной пять бит или меньше.

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

2?О нулей.

Преобразователи 36 и 37 осуществляют деление кодового многочлена на многочлены х + х +1 и х +1 соот9 ветственно. Оба преобразователя работают синхронно, что обеспечивается подачей на их входы синхроимпульсов (СИ) по выходам 43 и 44 соответственно от формирователя 66, который запускается по входу 21 сигналом от блока 1.

Если ошибки не произошло, то пос ле прохождения и бит через преобразователи 36 и 37, содержимое их равно нулю. Это фиксируется блоками 38 и

39, которые вырабатывают сигналй, поступающие по входам 50 и 51 блока 45

35 на элементы НЕ 75 и 76, запрещающие подачу синхроимпульсов на преобразователи 36 и 37, и тем самым прекращая работу блока 6. Кроме того, сигналы сравнения 50 и 51 не изме- 50 няют состояния триггера 85, и по выходу 22 от блока 6 уходит сигнал

"Ошибки нет".

Если при передаче информации произошла ошибка, то после прохождения и бит кодового многочлена через преобразователи 36 и 37, полученные в них остатки не равны нулю. ПредполоС момента обнаружения ошибки по выходам 45 и 46 начинают поступать

СИ на счетчики 40 и 41. Накопление

СИ в счетчике 40 продолжается до момента выработки блоком 39 сигнала совпадения. Этот сигнал по входу 51 в блоке 35, запрещает подачу СИ на вход счетчика 40. В то же время содержимое счетчика 40 передается через регистр 81 и выходы 23 (фиг.4) в блок 1. Это переданное число представляет собой остаток от деления номера последнего безошибочного разряда информационной последовательности на С.

С начала процесса поиска местоположения ошибки сдвигается и содержимое в преобразователе 36 до тех пар пока не совпадает с содержимым пяти младших разрядов нреобразователя 37, В результате блок 38 выработает сигнал совпадения, который запретит подачу СИ на преобразователь

36 и тем самым остановит его и счетчик 41, содержимое которого поступитв блок. 35 на регистр 80, откуда будет передано в блок l. Переданное из счетчика 41 число представляет собой

1257708

10

25

55 остаток от деления номера последнегь безошибочного разряда информационной последовательности на (2 -1), Таким образом, может быть вычислен номер последнего безошибочного разряда в информационной последовательности. В то же время пакет ошибки находится в младших разрядах преобразователя 37, и при наличии двух сигналов совпадения 50 и 51 блок 35 выдает разрешающий сигнал 49 на элемент И 42. Этот сигнал обеспечивает подачу СИ через элемент И 70 и элемент ИЛИ б8 на преобразователь 37, сдвигая его содержимое, в результате чего пакет ошибок будет передан в блок 35, а оттуда в блок 1. Зная номера ошибочных разрядов и имея картину ошибок, можно скорректировать информацию путем сложения по модулю два ошибочных разрядов с разрядами пакета ошибок.

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

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

НЕ и группа элементов И, причем один из входов первого накопителя соединены с выходами первого счетчика и первыми входами элементов И-ИЛИ, вторые входы которых и входы элемента ИЛИ подключены к выходам первого накопителя, другие входы которого соединены с выходами блока. местного управления, другие входы которого подключены к выходам коммутатора, одни из входов которого соединены с выходами второго накопителя, а другие входы и первые входы элементов И группы — с выходами блока декодирования, первый и второй управляющие выходы которого подключены соответственно к первым входам блока управления и элемента

И и ко второму входу блока управления, третий вход которого соединен с выходом переполнения второго счетчика, а четвертый вход — с выходом элемента ИЛИ и входом элемента НЕ, выход котОрого подключен ко второму входу элемента И, выход.которого соединен со счетным входом первого счетчика, выходы второго счетчика подключены К, адресным входам первой группы второго накопителя, информационные входы и адресные входы второй группы которого соединены соответственно с выходами первого и второго регистров, входы которых подключены соответственно к выходам элементов И-HJIH и к выходам элементов И группы, первый выход блока управления соединен с первыми управляющими входами накопителей, второй выход — со вторым управляющим входом первого накопителя, а третий выход— со вторыми входами элементов И группы, третьими входами элементов И-ИЛИ и первым управляющим входом коммутатора, второй управляющий вход которого и четвертые входы элементов И-ИЛИ подключены к четвертому выходу блока управления, пятый выход которого соединен со входом второго счетчика и вторым управляющим входом второго накопителя.

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

9 1257708

30 элемента задержки, вторые входы триг- 50

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

3. Устройство по п.1, Q T JI H ч а ю щ е е с я тем, что блок управления содержит триггеры, генератор синхроимпульсов,элементы задержки, элементы И, элемент НЕ, элемент И-ИЛИ и элемент ИЛИ, причем выход первого элемента задержки соединен со входом второго элемента задержки и первыми входами первого и второго элементов

И, выходы которых подключены соответстненно к первым входам первого и второго триггеров, выходы которых соединены с первым и вторым входами элемента И-ИЛИ, третий и четвертый входы которого подключены к выходу генератора синхроимпульсон, вторые входы элементов И являются первым входом блока, вторым входом которого являются вход первого элемента задержки и первые входы третьего триггера и элемента ИЛИ, второй вход которого подключен к выходу второго герон являются третьим входом блока, четвертым входом которого являются третий вход первого элемента Р и вход элемента НЕ, выход которого соедипен с третьим входом второго элемента И, выходами блока с первого псг пятый являются соответственно выходы третьего триггера, элемента ИЛИ, 10

25 второго и первого триггеров и элемен— та И вЂ” ИЛИ.

4. Устройство по пп.!, „и 2, о т— л и ч а ю щ е е с я тем, что блок местного управления блока декодиронания содержит счетчик, триггер, регистры с первого по четвертый, элементы ИЛИ, элементы НЕ, элемент И, .элементы И вЂ” НЕ и формирователь синхроимпульсов, выход которого соединен со входом счетчика, первыми входами элемента И и элементов И-НЕ с первого по третий, второй вход элемента

И подключен к выходу четвертого элемента И-НЕ, а третий вход — к, выходу триггера и вторым входам второго и третьего элементов И-НЕ, второй вход первого элемента И-НЕ соединен с выходом счетчика и первым входом пятого элемента И-НЕ, выход которого подключен к первому входу триггера, выход первого элемента НЕ соединен с третьим входом второго и вторым входом пятого элементов И-HE выход второго элемента НЕ подключен к третьим входам третьего и пятого элементов

И-НЕ, выход первого элемента И-НЕ соединен с первыми входами первого и второго элементов ИЛИ, выходы которых подключены соответственно к выходу второго элемента -HE и входу третьего элемента HE к выходу третьего элемента И-HK и входу четнертого элемента НЕ, вход первого регистра соединен с выходом третьего элемента ИЛИ, входы с первого по третий которого подключены к,выходам ре= гистров со второго по четвертый соответственно, а четвертый вход третьего элемента ИЛИ является первым входом блока, вторым входом которого являются вход формирователя синхроимпульсов и второй вход триггера, треть. им входом блока являются вход второго элемента HE и первый вход четвертого элемента И-НЕ, а четвертым входом — вход первого элемента НЕ и второй вход четвертого элемента И-НЕ, входами с пятого по седьмой блока яв- ляются входы регистров со второго по четвертый, выходами блока с первого по седьмой являются соотнетствено ныходы первого и второго элементов

ИЛИ, второго и третьего элементов

И-НЕ, третьего и четвертого элементов НЕ и четвертого элемента И-HE выходами блока с восьмого по десятый являются выходы триггера, первого регистра и счетчика соответственно.

1257708 фиг. / фиг 2

1257708 ОЙ @Составитель Т.Зайцева

Техред И.Попович Корректор C.черни

Редактор Ю,Середа

Заказ 503I/51 Тираж 543 Подписное

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

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

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