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

Изобретение относится к вычислительной технике и может быть использовано в устройствах обработки и хранения информации (в частности, при хранении информации в ЭВС на магнитном диске) для кодирования данных, поступающих в виде последовательности байтов, избыточным помехоустойчивым кодом и для вычисления синдрома и определения типа ошибки в процессе декодирования этих данных/

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

На фиг.1 приведена блок-схема устройства для контроля последовательности байтов данныхi на фиг.2 -блок схема формирователя адреса и режима памяти проверочных символов; на фиг. 3 - блок-схема задатчика режима на фиг. 4 блок-схема блока определения четносл ти четверки байтов на фиг.5 -блок- схема блока определения типа ошибок

Устройство для контроля последовательности байтов данных содержит регистр 1 данных, буферную память 2 данных, счетчик 3 адреса, первый 4, второй 5, третий 6 и четвертый 7 мультиплексоры, выходной регистр 8, сумматор 9, первый 10 и второй 11 умножители, память 12 проверочных символов, регистр 13 проверочных символов, коммутатор 14, элемент ИЛИ 15, распределитель 16 тактов, формирователь 17 адреса и режима памяти проверочных символов, блок 18 определения типа ошибки, задатчик 19 режима, блок 20 определения четности Четверки байтов, регистр 21 типа ошибки, с первого по шестой входы 22-27, с первого по третий выходы 28-30.

Цифрами 31 - 57 на фиг.1 обозначены связи между блоками (шины). Каждая шина может содержать один или несколько проводов (электрических связей).

Формирователь 17 (фиг.2) содержит элементы ИЛИ 58 и 59, элементы И-ИЛИ 60 и 61, счетчик 62, мультиплексор 63, сумматор 64. Входы элементов ИЛИ 58 и 59 связаны с выходом блока 16.

Мультиплексор 63 имеет управляющий вход S,подключенный к шине 37, и четыре пары информационных входов. К первой паре подключены выходы один и три счетчика 62, к второй - выходы ноль и два счетчика 62, к третьей

ае

--.

25

159792

выходы сумматора 64 и один счетчика 62, к четвертой - выходы три jj ноль счетчика 62.

Задатчик 19 режима (фиг.З) содер5 жит триггеры 65 и 66, дешифратор 67, блок элементов И 68, состоящий из трех элементов И.

Блок 20 (фиг.4) содержит счетчик 69, регистр 70, элемент 2И-ИЛИ 71,

JO элемент ИЛИ 72.

Блок 18 (фиг.5) содержит двенадцатиразрядный сдвиговый регистра 73, мультиплексор 74, состоящий из двух мультиплексоров 74.1 и 74.2 (на 8

5 направлений каждый) с общим управлением, блок 75 элементов состояний из двух элементов И.

Информация в устройстве передается и обрабатывается 8-разрядными

20 байтами. Байты поступают в устройство и передаются между блоками устройства в параллельной форме.

При работе устройства каждый 8- разрядный байт является информационным или проверочным символом кода и рассматривается как элемент ко- нечного поля Галуа GF(2). Это поле содержит 256 элемента.

Работу устройства можно разделить

30 на четыре этапа. На первом этапе производится запись информационных символов на диск, и одновременно формируются проверочные символы. На втором этапе сформированные проверочные

35 символы переписываются на диск. На третьем этапе производится чтение с диска информационных символов, и одновременно формируются проверочные символы. На четвертом этапе считыва40 ются с диска проверочные символы и формируются синдромы.

На первом этапе 1024 информационных символов Ь(, ,Ь,. .. ,b,pj2 через мультиплексор 4 поступают из блока 2

45 на информационный вход регистра 8, и с выхода регистра 8 проходят на выход 29 устройства, откуда побайтно передаются для записи в диск. Однов-. ременно через мультиплексор 6 каждый

50 информационный символ (байт) передается в сумматор 9, который вместе с мультиплексором 7, умножителями 10 и 11, памятью 12, регистром 13 под управлением коммутатора 14, формиро55 вателя 17 и блока 20 выполняет процедуру вычисления проверочных символов. Всего вычисляется 16 проверочных символов, образующих четыре независимые группы.

31315979

Проверочные символы первой группы зависят только от информационных

Вычисление подсчитанных

символов Ь,

Ь D

проверочные символы второй группы зависят от информационных символов

.ч проверочные символы четвертой группы зависят только от информационных символов bj ,Ь,,.. . (Ь п+зЦо1 «b-foi3

В устройстве реализуется кодирование с перемежением, причем степень пере- межения равна четырем. При кодировании каждой группы информационных символов используется линейный (260,

проверочных символов выполняется точно ion,)ioto вычисление проверочных

символов при кодировании. Синдром вычисляется сумматором 9. Обнаружение ошибок заключается в сравнении синдрома с нулем (выполняется блоком 15). Если среди компонент синдрома есть хотя бы одна не- JQ нулевая, то имеет место искажение информации.

Если среди компонент синдрома имеется ровно одна .ненулевая, то считаем, что произошла однократная ошиб256, 4) код с минимальным расстояниемJ5 а в проверочных символах, а инфор-четыре.

Рассмотрим процессы кодирования и обнаружения ошибок для первой группы информационных символов. Для остальных трех групп информационньпс символов кодирование и обнаружение ошибок выполняются аналогично.

Кодирование (вычисление проверочных символов) выполняется путем умножения вектора, составленного из информационных символов (Ь(5 ,Ь,.. . ,Ц,,,

vc транспонированную усеченную проверочную матрицу. При кодировании и обнаружении ошибок все операции над символами кодо- вого слова выполняются в полеСГ(2®)4

Сложение двух элементов поля GF(2) сводится к подразрядному сложению по модулю два:

(А..,,.,.,. ,Ад} + (Ът,Е(,,.. Е

(B7+A7,Bj+AjВО+АО). (1)

Выражение (1) реализуется сумматором 9. Умножение на d реализуется с помощью сложений по модулю два:

Ад(А, ,А,... ,А(,)((А ,А,А ,АЗ+ +A,A2-t-A7,,,Ao,A,). (2)

Умножение на о также выполняется на сумматорах по модулю два:

A J (А,,)

А,А, А , ,АС , АР+АЛ fAg+A , Ар+А ,А ) .

(3)

Выражения (2) и (3) реализуются соответственно умножителями 10 и 11.

На третьем этапе вычисляются подсчитанные проверочные символы, а затем считанные с диска (четвертый этап) проверочные символы складываются с подсчитанными для получения синдрома.

Вычисление подсчитанных

ных символов выполняется вычисление про

мационные символы правильные.

В остальных случаях (при ненулевом . синдроме) считаем, что произошла неисправимая ошибка.

0 В каждой группе байтов, закодиро- ванной с помощью предложенного устройства, можно исправить однократную ошибку (ошибку в одном байте) и обнаружить все двукратные ошибки (ошиб5 ки в двух байтах) и пакет ошибок длины из 3 байтов.

За счет перемежения групп байтов можно исправить пакет из 4 байтов или обнаружить два пакета из 4 бай0 тов каждый или обнаружить пакет ошибок из 12 байтов.

Рассмотрим работу, устройства на первом этапе подробнее.

Сообщение длиной 1024 байтов находящееся в памяти 2, через вход ноль мультиплексора 4 побайтно передается для записи в диск с выхода 29 регистра 8. Одновременно через мульти- плексор 6 по шине 53 каждый байт сообщения (информационный символ кода) передается в сумматор 9, который совместно с мультиплексором 7, умножителями 10 и 11, памятью 12 и регистром 13 формирует проверочные символы.

5 Над каждым байтом производятся следующие действия: прием (выдача) байта в память 2 данных, вычисление вклада этого байта в образование проверочных символов (суммирование,

0 умножение на о , умножение на в), изменение на единицу адреса памяти 2.

Адрес памяти 2 формируется счетчиками 3 и 69 (фиг.1 и 4). Счетчик 69, на счетный вход которого посту5 пает импульс по шине 46, формирует младшие разряды адреса () , которые по шине 39 подаются в память 2. Выход три (выход старшего разряда) счетчика 69 подается на счет5

0

51

ный вход счетчика 3, формирующего старшие разряды ( четыре - девять) адреса памяти 2, которые поступают по .шине 32 в память 2.

Выход разряда два счетчика 69 (сигнал 48) (определяет четность четверки текущих байтов, при нуле этого разряда четверка четных байтов, при единице - четверка нечетных байтов.

Через элемент ИЛИ 58 и элемент Й- ИЛИ 60 на счетный вход счетчика 62, формирукщего адрес памяти 12, поступают импульсы в соответствии с фиг.2 (импульсы поступают из блока 16 в ; блок 17 по шине 52).

Через элемент ИЛИ 59 и элемент И-ИЛИ 61 поступают импульсы на вход разрешения записи памяти 12. При единице на этом входе запись в память 12 разрешена. Сигнал 50 разрешения приема информации из памяти 12 в регистр 13 формируется в блоке 20 элементом 2И-ИЛИ 71 (фиг.2).

В блоке 20 (фиг ..4) формируется сигнал 49, при нуле которого выход памяти 12 закрыт (равен нулю), при единице открыт.

Восемь выходов памяти 12 соединены с восьмью входами регистра 13, прием на который производится сигналом по шине 50. Начальная установка (сигнал 23) устанавливает в единицу оба триггера регистра 70. Первый триггер регистра 70 сбрасывается сигналом четности по шине 48, второй триггер сбрасывается выходом разряда три счетчика 69. В результате при обработке первой четной четверки байтов bg-bj все сложения выполняются с нулем, а при обработке первой нечетной четверки байтов bf сложения с нулем соответствуют

только проверочным символам (С,..,, 4л. 2

с1 ).

После записи последнего информационного байта b

югз

из памяти 2 на

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

Сигналом 34 мультиплексор 4 переключается на прием по другому входу. Сигналом 38 мультиплексор 5 также включается на прием по другому . входу. Проверочные символы из памяти 12 по шинам 42,40 и 57 через, мультиплексоры 5 и 4 поступают на выходной регистр 8 и далее через шину 29 записываются на диск.

96

Перед началом работы устройства в режиме чтения из диска информационных байтов (третий этап) внешним сигналом по шине 23 триггеры 65 и

66, задатчика 19 устанавливаются в состояние ноль. В режиме чтения из диска информационных байтов последние поступают по шине 26 в регистр 1 данных одновременно с сигналом 25

и далее по шине 56 в память 2, а также через мультиплексор 6 по шине 53 в сумматор 9. Каждый считанный информационный байт участвует в образовании проверочных символов в мультиплексоре 7, сумматоре 9, умножителях 10 и 11, памяти 12, регистре 13 аналогично указанному для первого этапа.

После считывания последнего информационного байта b из счетчика 3 поступает сигнал в задатчик 19 для установки в единицу триггера 65, в результате чего схема переводится

в режим работы четвертого этапа - чтение из диска проверочных символов, формирование синдрома в памяти 12, определение типа ошибки.

Очередной подсчитанный проверочный символ принимается на регистр 13 проверочных символов и по шине 54 поступает на сумматор 9, где складывается по модулю два со считанным из диска соответствующим проверочным символом. Полученный в результате сложения синдром записывается в па-, мять 12 через мультиплексор 7 и одновременно по шине 41 через мультиплексор 5 поступает в элемент ИЛИ 15. Если ошибок нет, синдромы должны быть равны нулю. Если есть ошибка, синдром будет ненулевьм и на выходе элемента ИЛИ 15 появится сигнал единица. Для каждой четверки синдромов.

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

Наличие в четверке синдромов одного ненулевого синдрома означает ошибку в проверочных символах. Соче- танин, кода и не равны нуf-fl - f i I

лю, a или S 0, свидетельствует об исправимой ошибке в информационном блоке. Остальные девять сочетаний нулевых и ненулевых синдроMOB свидетельствуют о неисправимых ошибках. Определение типа ошибки по

На четвертом этапе на вход 12-разрядного сдвигового регистра 73 (фиг.5) последовательно подаются сигналы с выхода элемента ИЛИ 15, т.е. единицы, если синдромы , , SY , ..., не равно нулю. С выходов три.

семь и одиннадцать

регистра 73 эти сигналы поступают на три управляющих входа Sp - Sj мультиплексора 74. На часть входов данных этого мультиплексора поданы сигналы с выхода элемента ИЛИ 15. Остальные вхйды данных подключены к сигналам единица или ноль. В результате- во время прохождения синдромов S у - проверяется выполнение условий, заданных таблицей 1.

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

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

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

регистра данных, первого и второго мультиплексоров и выходного регистра, информационный вход которого соединен с выходом первого мультиплексора, а выход - с выходом связи с

дисковой памятью устройства, второй выход распределителя тактов соединен с тактовым входом задатчика режима, а тактовый вход - с тактовым входом устройства, входы начальной установки, установки режима чтения-записи, строба данных, информации от ЭВМ устройства подключены соответственно к входам начальной установки режима чтения-записи задатчика режима,

к входу строба данных распределителя тактов и к входу информации от ЭВМ буферной памяти данных, выход которой соединен с выходом связи с ЭВМ устройства, выход старших разрядов счетчика, адреса соединен с первым, адресным входом буферной памяти данных, выход памяти проверочных символов подключен к первому информационному входу второго мультиплексора, отличающееся тем, что, с целью повышения достоверности эй счет увеличения контролируемого объема сообщения, в него введены третий и четвертый мультиплексоры, коммутатор, блок определения типа ошибки, регистр типа ошибки и блок определения четности четверки байтов, выходы признака формирования младших разрядов адреса, разрешения выдачи нулевого байта и строба регистра проверочных символов которого соединены соответственно с входом счетчика адреса, входом разрешения выдачи нулевого байта памяти проверочных символов и управляющим входом регистра проверочных символов, а тактовый и установочный входы соединены соответственно с начальньм входом установки устройства и с третьим выходом распределителя тактов, четвертый выход которого подключен к тактовому входу блока определения типа ошибки, выходы номера проверочного слова и номера комбинации формирователя адреса и режима памяти проверочных символов соединены соответственно с информационными входами коммутатора и блока определения типа ошибки, третий вход формирователя адре- Q

15

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

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

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

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

55 задатчика режима, информационный

вход второго триггера соединен с входом установки режима чтения-записи задатчика режима, выход первого триг-г гера связан с выходом разрешения pa-ii

11

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

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

597912

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

4, Устройство поп.1,отли- чающееся тем, что блок определения типа ошибки содержит регистр сдвига, мультиплексор, два элемента И, причем, тактовый вход блоtO ка соединен с первыми входами элементов И и с сдвигающим входом регистра сдвига, выходы которого соединены с управляющими входами мультиплексора, вход признака ошибки блока со)5 единен с установочным входом регистра сдвига и первым информационным входом мультиплексора, второй и тре- тки информационные входы которого соединены с щинами нулевого и единич20 ного сигнала, выходы мультиплесора ;оединены с вторыми входами первого д второго элементов И, третьи и чет- зертые входы которых соединены с ин- формационным входом и входом чтения

25 проверочного слова блока.

26

г

-

59

61

38

8

55

- ) 17

Фи.г.2

9иг.З

Редактор В.Данко заказ 236А/51

Составитель А.Давьщов Техред М.Ходанич

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

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

Корректор Г.Решетник Подписное

П ойз од тв нн -полй р йчГс о Г.УЖГОРОД. ул.Проектная,4

fuz.5

45

Корректор Г.Решетник Подписное

Изобретение относится к вычислительной технике и может быть использовано в устройствах обработки и хранения информации, в частности при хранении информации на магнитном диске. Целью изобретения является повышение достоверности информации за счет увеличения объема сообщения. Устройство содержит входной регистр данных, буфер данных, сумматор, первый и второй умножители, память проверочных символов, регистр проверочных символов, схему сравнения с нулем, блок тактирования, задатчик режима, формирователь адреса и режима памяти проверочных символов, мультиплексоры. Устройство позволяет кодировать блок данных объемом 1024 байта, в котором можно исправить любой пакет ошибок длиной до 25 бит, обнаружить при этом любой пакет ошибок длиной до 89 бит либо обнаружить любые два пакета ошибок до 25 бит каждый. Это йозво- ляет значительно увеличить .надежность дисковой запоминающей системы. 3 з.п. ф-лы, 5 ил. 1 табл. (О со СП ;0 ;0