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

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

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

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

Устройство содержит (фиг.1) блок 1 местного управления, блок 2 кодирования , формирователь 3 сигналов записи, блок 4 памяти. Устройство содержит также усилитель 5 считыва- ния, блок 6 декодирования, блок 7 управления, первый 8 и второй 9 накопители, элемент ИЛИ 10, элементы И-ИЛИ 11, первый регистр 12, группу элементов И 13, второй регистр 14, первый счетчик 15, элемент НЕ 16, элемент И 17, второй счетчик 18 и коммутатор 19, входы 20 и 21, первый управляющий выход 22, выходы 23 и второй управляющий выход 24 блока 6 декодирования, выходы 25-29, третий 30 и четвертый 3I входы блока 7 управления и установочные входы 33 и 34 первого счетчика 15. Блок 6 декодирования содержит (фиг-2) блок 35 местного управления, первый 36 и второй 37 прео1.разователи кода, первый 38 и второй 39 блоки сравнения, первый 40 и второй 41 счетчики и элемент И 42, выходы 43-49 с первого по седьмой и выходы 50-54 с третьего по седьмой блока 3 местного управления блока декодирования.

Блок 7 (фиг.З) управления содержит первый 55 и второй 56 элементы задержки, генератор 57 синхроимпульсов, первый 58 и второй 59. элементы И, элемент НЕ 60, триггеры 61-63 с первого по третий, элемент И-ИЛИ 64 и элемент ИЛИ 65.

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

5

0

5

I

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

Проверяемь Й блок 4 памяти. (ЦМД- прибор) формирователь 3 сигналов записи и усилитель 5 считывания могут быть выполнены на микросхемах К1 602 РЦ2. Емкость накопителя 9 равна NxC бит (где N - предельно допустимое число ошибок в блоке 4 до перехода его на профилактический режим работы, а С - разрядность считываемого из него слова).

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

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

При записи информации в блок 4 данные от блока 1 (фиг.1) поступают в блок 2, а затем через формирователь 3 они поступают на выход устройства. При считывании информация из блока 4 через усилитель 5 поступает в блок 6. До начала работы происходит обнуление регистров 12 и 14 (сигнал на чертеже не показан). После того, как будет принят последний бит считанной информации, блок. 6 вьщает сигнал с выхода 24, по которому блок 7 вырабатывает сигнал обращения 26 к накопителю 8 и сигнал записи-чтения 25 к накопителям 8 и 9. В то же время адрес считываемой последовательности поступает с выходов блока на вход накопителя 8, а с его выхода считываемая информация передается на элемент ИЛИ 10. Запись информации в накопитель 8 организована так, что если в течение рабочего периода блок 4 (до профилактического цикла) в слове по лю- .бому из адресов обнаруживается ошибка, то по данному адресу в накопи- 5 тель 8 записывается двоичньй номер этой ошибки.

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

0

5

0

5

0

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

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

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

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

35

20

0 550 55

2577084

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

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

25

30

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

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

путем одновременного синхронного преобразования информации в преобразователях 36 и 37 (фиг.2), каждый из которых соответствует одной из составляющих порождающего полинома кода Файра, задаваемого формулой Р(х) (х -О Р, (х), где Р,(х) - неприводимый многочлен степени b и порядка е причем С не делится на е, максимальное значение которого е 2 -1, Дпина п кода - наименьшее общее кратное е и С. Количество контрольных разрядов равно (С+Ь).

1-ассмотрим, например, работу уст1

ройства для кода Файра, заданного по- 15 элементы 72 и 73 разрешают прохожде- рождающим полином (Р(х) (х +1) ( ние СИ от формирователя 66 по вы- +1) и имеющего максимальную длину ходам АЗ-46. Сигналы несовпадения от (2 -1)279. Этот код исправит блоков 38 и 39 изменят состояние триг- произвольный пакет ошибок длиной гера 85 и по выходу 22 уходит сигнал

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

пять бит или меньше.

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

полином. В рассматриваемом случае весь кодовый многочлен будет представлять собой последовательность их 270 нулей.

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

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

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

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

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

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

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

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

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

остаток от деления номера последнего безошибочного разряда информационной последовательности на (2 -1).

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

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

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

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

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

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

выход которого подключен ко второму входу элемента И, выход которого соединен со счетным входом первого счетчика, выходы второго счетчика подключены к адресным входам первой

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

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

2. Устройство по п.1, о т л и - чающее ся тем, что блок декодирования содержит преобразователи

кода, блоки сравнения, блок местного управления, счетчики и элемент И, причем входы преобразователей кодов и первый вход блока местного управления являются информационгеями входами блока, тактовым входом которого является второй вход блока местного управления, первый и второй РЫХОДЬ; оторого подключены к управляющим

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

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

5

0

5

второго и первого триггеров и элемента И-ИЛИ.

4. Устройство попп.1эи2, о т - ли чающе е ся тем, что блок местного управления блока декодирования содержит счетчик, триггер, регистры с первого по четвертый, элементы ИЛИ, элементы НЕ, элемент И, .элементы И-НЕ и формирователь синхро- импульсов, выход которого соединен со входом счетчика, первыми входами элемента И и элементов И-НЕ с первого по третий, второй вход элемента И подключен к выходу четвертого элемента И-НЕ, а третий вход - к.выходу триггера и вторьм входам второго и третьего элементов И-НЕ, второй вход первого элемента И-НЕ соединен с выходом счетчика и первым входом пятого элемента И-НЕ, выход которого подключен к первому входу триггера, выход первого элемента НЕ соединен с третьим входом второго и вторым входом пятого элементов И-НЕ, выход второго элемента НЕ подключен к третьим входам третьего и пятого элементов И-НЕ, выход первого элемента И-НЕ соединен с первыми входами первого и второго элементов ИЛИ, выходы которых подключёнь соответственно к выходу второго элемента И-НЕ и вхОду третьего элемента НЕ к выходу третьего элемента И-НЕ и входу четвертого элемента НЕ, вход первого регистра соединен с выходом третьего эле- 5 мента ИЛИ, входы с первого по третий которого подключены к,выходам регистров ср второго по четвертый соответственно, а четвертый вход третьего элемента ИЛИ является первым входом блока, вторым входом которого являются вход формирователя синхроимпульсов и второй вход триггера, третьим входом блока являются вход второго элемента НЕ и первый вход четвер- 5 того элемента И-НЕ, а четвертым входом - вход первого элемента НЕ и второй вход четвертого элемента И-НЕ, входами с пятого по седьмой блока яв- ляются входы регистров со второго по 0 четвертыйj выходами блока с первого по седьмой являются соответствено выходы первого и второго элементов ИЛИ, второго и третьего элементов И-НЕ, третьего и четвертого элёмен- 5 тов НЕ и четвертого элемента И-НЕ, выходами блока с восьмого по десятый являются выходы триггера, первого регистра и счетчика соответственно.

0

фиг

43

71 К 22 W

П

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

tpuf.

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

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

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

ВНИИПИ Государственного комитета СССР

по делам изобретений и открытий 113035, Москва, Ж-35, Раушская наб.., д. 4/5

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