Устройство для контроля последовательности байтов данных дисковой памяти

СОЮЗ СОВЕТСКИХСОЦИАЛИСТИЧЕСКИХРЕСПУБЛИК а) 4 С 06 Р 11/00 ц.ф,;ОПИСАНИЕ ИЗОБРЕТЕНИЯК АВТОРСКОМУ СВИДЕТЕЛЬСТВУ ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССРПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТИЙ(54) УСТРОЙСТВО ДЛЯ КОНТРОЛЯ ПОСЛЕДОВАТЕЛЬНОСТИ БАЙТОВ ДАННЫХ ДИСКОВОЙДАМЯТИ(57) Изобретение относится к вычислительной технике и может быть использовано в устройствах обработки ихранения информации, в частности прихранении информации на магнитном дис 801315979 А 1 ке. Целью изобретения является повы"шение достоверности информации засчет увеличения объема сообщения, Устройство содержит входной регистр данных, буфер данных, сумматор, первыйи второй умножители, память проверочных символов регистр проверочныхсимволов, схему сравнения с нулем,блок тактирования, задатчик режима,формирователь адреса и режима памятипроверочных символов, мультиплексоры.Устройство позволяет кодировать блокданных объемом 1024 байта, в которомможно исправить любой пакет ошибокдлиной до 25 бит, обнаружить при этомлюбой пакет ошибок длиной до 89 битлибо обнаружить любые два пакетаошибок до 25 бит каждый. Это позволяет значительно увеличить .надежностьдисковой запоминающей системы. 3 з.п.ф-лы, 5 ил. 1 табл,131 5979 1Изобретение относится к вычислительной технике и может быть использовано в устройствах обработки и хранения информации (в частности, при хранении информации в ЭВС на магнитном диске) для кодирования данных, поступающих в виде последовательности байтов, избыточным помехоустойчивым кодом и для вычисления синдрома и определения типа ошибки в процессе декодирования этих данных:Целью изобретения является повышение достоверности информации за счет увеличения объема сообщения.На Фиг.1 приведена блок-схема устройства для контроля последовательности байтов данных, на фиг.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 имеет управляющий вход Б,подключенный к шине 37, и четыре пары информационных входов. К первой паре подключены выходы "один" и "три" счетчика 62, к второй - выходы "ноль" и "два" счетчика 62, к третьей 10 15 20 25 35 40 45 50 55 2выходы сумматора 64 и "один" счетчика 62, к четвертой - выходы "три" и "ноль" счетчика 62. Задатчик 19 режима (фиг.3) содержит триггеры 65 и 66, дешифратор 67,блок элементов И 68, состоящий изтрех элементов И,Блок 20 (фиг.4) содержит счетчик69, регистр 70, элемент 2 И-ИЛИ 7 1,элемент ИЛИ 72,Блок 18 (фиг.5) содержит двенадцатиразрядный сдвиговый регистра 73,мультиплексор 74, состоящий из двухмультиплексоров 74.1 и 74.2 (на 8направлений каждый) с общим управлением, блок 75 элементов состоянийиз двух элементов И.Информация в устройстве передается и обрабатывается 8-разряднымибайтами. Байты поступают в устройство и передаются между блокамиустройства в параллельной форме.При работе устройства каждый 8 разрядный байт является информационным или проверочным символом кодаи рассматривается как элемент конечного поля Галуа СР(2 ф). Это полесодержит 256 элемента.Работу устройства можно разделитьна четыре этапа. На первом этапе производится запись информационных символов на диск, и одновременно формируются проверочные символы. На втором этапе сформированные проверочныесимволы переписываются на диск. Натретьем этапе .производится чтение сдиска информационных символов, и одновременно формируются проверочныесимволы. На четвертом этапе считываются с диска проверочные символы иФормируются синдромы.На первом этапе 1024 информационных символов ЬО,Ь 1Ь 2 черезмультиплексор 4 поступают из блока 2на информационный вход регистра 8,и с выхода регистра 8 проходят навыход 29 устройства, откуда побайтнопередаются для записи в диск. Одновременно через мультиплексор 6 каждыйинформационный символ (байт) передается в сумматор 9, который вместе смультиплексором 7, умножителями 10и 11, памятью 12, регистром 13 подуправлением коммутатора 14, формирователя 17 и блока 20 выполняет процедуру вычисления проверочных символов. Всего вычисляется 16 проверочных символов, образующих четыре независимые группы.794 35 3 .13159Проверочные символы первой группызависят только от информационныхсимВОлОВ Ь,Ь,Ь,Ь 10 ь отопроверочные сймволы второй группызависят от информационных символовЬ ЪЪ 4+1ЬотЬ(ор проверочные символы четвертой группызависят только от информационных символов ЬзЪ.Ь+зЬо 1 уЬ 1 ойзВ устройстве реализуется кодирование 10с перемежением, причем степень перемежения равна четырем. При кодировании каждой группы информационныхсимволов используется линейный (260,256, 4) код с минимальным расстоянием 15четыре.Рассмотрим процессы кодированияи обнаружения ошибок для первой группы информационных символов. Для остальных трех групп информационных 20символов кодирование и обнаружениеошибок выполняются аналогично,Кодирование (вычисление проверочных символов) выполняется путем умножения вектора, составленного из ин формационных символоВ (Ьо ЬЬ,;Ь ,Ь, ), на Н транспонированную усеченную проверочную матрицу,При кодировании и обнаружении ошибок все операции над символами кодового слова выполняются в поле СР(28)Сложение двух элементов поляСР(2 ) сводится к подразрядному сло 8жению по модулю два:=(В+А В 6+АйВо +Ао)(1) Выражение (1) реализуется сумматором 9. Умножение на о реализуется 40 с помощью сложений по модулю два: А =(А ААо)Ы=(А АА Аз++Ахфт 1+ о)Умножение на о также выполняет ся на сумматорах по модулю два: А=(АААо) оС =Вычисление "подсчитанных" проверочных символов выполняется точно так же, как и вычисление проверочных символов при кодировании.Синдром вычисляется сумматором 9. Обнаружение ошибок заключается в сравнении синдрома с нулем (выполняется блоком 15). Если среди компонент синдрома есть хотя бы одна ненулевая, то имеет место искажение информации.Если среди компонент синдрома имеется ровно одна, ненулевая, то считаем, что произошла однократная ошибка в проверочных символах, а информационные символы правильные.В остальных случаях (при ненулевом, синдроме) считаем, что произошла неисправимая ошибка.В каждой группе байтов, закодиро- ванной с помощью предложенного устройства, можно исправить однократную ошибку (ошибку в одном байте) и обнаружить все двукратные ошибки (ошибки в двух байтах) и пакет ошибок длины из 3 байтов.За счет перемежения групп байтов можно исправить пакет из 4 байтов или обнаружить два пакета из 4 байтов каждый или обнаружить пакет ошибок из 12 байтов,Рассмотрим работу, устройства напервом этапе подробнее.Сообщение длиной 1024 байтов находящееся в памяти 2, через входц нноль мультиплексора 4 побайтно передается для записи в диск с выхода 29регистра 8, Одновременно через мультиплексор 6 по шине 53 каждый байт сообщения (информационный символ кода)передается в сумматор 9, который совместно с мультиплексором 7, умножителями 10 и 11, памятью 12 и регистром 13 формирует проверочные символы.Над каждым байтом производятсяследующие действия: прием (выдача)байта в память 2 данных, вычисление"вклада" этого байта в образованиепроверочных символов (суммирование,умножение на Ыумножение на Ы ), Выражения (2) и (3) реализуются соответственно умножителями 10 и 11,На третьем этапе вычисляются "подсчитанные" проверочные символы, а затем считанные с диска (четвертый этап) проверочные символы складываются с "подсчитанными" для получения синдрома. изменение на единицу адреса памяти 2.Адрес памяти 2 формируется счетчиками 3 и 69 (фиг.1 и 4). Счетчик 69, на счетный вход которого поступает импульс по шине 46, формируетмладшие разряды адреса (" ноль"-"три"), которые по шине 39 подаются в память 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. В результатепри обработке первой четной четверки байтов Ь -Ъ все сложения выпол 0 3,няются с "нулем", а при обработкепервой нечетной четверки байтов ЬЬ сложения с "нулем" соответствуюттолько проверочным символам (СС 4 )После записи последнего информационного байта Ъ 1 из памяти 2 надиск с выхода счетчика 3 поступаетсигнал, устанавливающий вместо первого этапа второй.Сигналом 34 мультиплексор 4 переключается на прием по другому входу. Сигналом 38 мультиплексор 5 также включается на прием по другому .входу, Проверочные символы из памяти12 по шинам 42,40 и 57 через. мультиплексоры 5 и 4 поступают на выходнойрегистр 8 и далее через шину 29 записываются на диск. 6Перед началом работы устройства в режиме чтения из диска информационных байтов (третий этап) внешним сигналом по шине 23 триггеры 65 и бб, задатчика 19 устанавливаются в состояние "ноль", В режиме чтения из диска информационных байтов последние поступают по шине 26 в регистр 1 данных одновременно с сигналом 25 и далее по шине 56 в память 2, а также через мультиплексор б по шине 53 в сумматор 9, Каждый считанный информационный байт участвует в образовании проверочных символов в мультиплексоре 7, сумматоре 9, умножителях 10 и 11, памяти 12, регистре 13 аналогично указанному для первого этапа. После считывания последнего информационного байта Ь из счетчика 3 поступает сигнал в задатчик 19 для установки в "единицу" триггера 65, в результате чего схема переводится в режим работы четвертого этапа - чтение из диска проверочных символов, формирование синдрома в памяти 12, определение типа ошибки. Очередной "подсчитанный" проверочный символ принимается на регистр 13 проверочных символов и по шине 54 поступает на сумматор 9, где складывается по модулю два со считанным из диска соответствующим проверочным символом. Полученный в результате сложения синдром записывается в па-. мять 12 через мультиплексор 7 и.одновременно по шине 41 через мультиплексор 5 поступает в элемент ИЛИ 15, Если ошибок нет, синдромы должны быть равны нулю. Если есть ошибка, синдром будет ненулевым и на выходе элемента ИЛИ 15 появится сигнал "единица". Для каждой четверки синдромов, относящейся к одной группе байтов, возможны 16 комбинаций из ненулевых и нулевых синдромов, отраженных в таблице. Значение синдрома Б =1 ус-Ц)1 ловно означает неравенство его нулю. Наличие в четверке синдромов одного ненулевого синдрома означает ошибку в проверочных символах. Сочетания, кода Б 1 и Б не равны нуф д 1 Э 4лю, а Б 1:0 или Б :О, свидетельствует об исправимой ошибке в информационном блоке. Остальные девять сочетаний нулевых и ненулевых синдро(8 )4 О 1 О О О О 1 1 1 1 О О 1 1 О 1 О О 1 О О 1 О 1 1 1 1 1 О О О 1 О О О 1 О 1 1 О 1 О О 1 О 1 1 1 О О О, О 1 1 1 1 О О 1 О 1 О 1 1 Управляющийвход блока О 1 2 4 О 6 5 3 7 3 2 6 1 5 4 7 Характерошибки Под- Неисправимая ошибкалежит Нет Ошибка в прооши- верочных бок символах исправ- лению мов свидетельствуют о неисправимыхошибках. Определение типа ошибки по На четвертом этапе на вход 12-раз Орядного сдвигового регистра 73 (фиг,5) последовательно подаются сигналы с выхода элемента ИЛИ 15, т.е. "единицы", если синдромы Я, Я(з), (3)(ф)дов "три", "семь" и "одиннадцать" регистра 73 эти сигналы поступают на три управляющих входа Яо - Я мультиплексора 74На часть входов данных этого мультиплексора поданы 4 О сигналы с выхода элемента ИЛИ 15. Остальные вхбды данных подключены к сигналам "единица" или ".ноль". В результате во время прохождения синдромов 3- Б проверяется выполнеФиие условий, заданных таблицей 1. формула изобретения 1. Устройство для контроля после довательности байтов данных дисковой памяти, содержащее регистр данных, буферную память данных, счетчик адреса, первый и второй мультиплексоры, выходной регистр, сумматор, пеРвый 55 и второй умножители, память проверочных символов, регистр проверочных символов, элемент ИЛИ, распределитель тактов, задатчик режима и форкомбинациям нулевых и ненулевых синдромов представлено в таблице. мирователь адреса и режима памятипроверочных символов, адресный выходкоторого соединен с адресным входомпамяти проверочных символов, а тактовый и разрешающий входы соответственно соединены с первым выходомраспределителя тактов и выходом разрешения работы задатчика режима, выходы чтения с дисковой памяти, строба регистра данных записи проверочного слова, чтения проверочного слова, строба выходного регистра задатчика режима подключены соответственно к управляющему входу буферной памяти данных и к управляющим входамрегистра данных, первого и второгомультиплексоров и выходного регистра, информационный вход которого соединен с выходом первого мультиплексора, а выход - с выходом связи сдисковой памятью устройства, второйвыход распределителя тактов соединенс тактовым входом задатчика режима,а тактовый вход - с тактовым входомустройства, входы начальной установки, установки режима чтения-записи,строба данных, информации от ЭВМустройства подключены соответственно к входам начальной установки режима чтения-записи задатчика режима,131597910 510 25 30 ходу устройства. 40 45 50 55 к входу строба данных распределителя тактов и к входу информации отЭВМ буферной памяти данных, выходкоторой соединен с выходом связи сЭВМ устройства, выход старших разрядов счетчика. адреса соединен с первым. адресным входом буферной памятиданных, выход памяти проверочныхсимволов подключен к первому информационному входу второго мультиплексора, о. т л и ч а ю щ е е с я тем,что, с целью повышения достоверностиэй счет увеличения контролируемогообъема сообщения, в него введенытретий и четвертый мультиплексоры,коммутатор, блок определения типаошибки, регистр типа ошибки и блокопределения четности четверки байтов, выходы признака формированиямладших разрядов адреса, разрешениявыдачи нулевого байта и строба регистра проверочных символов которого соединены соответственно с входомсчетчика адреса, входом разрешениявыдачи нулевого байта памяти проверочных символов и управляющим входомрегистра проверочных символов, а тактовый и установочный входы соединены соответственно с начальным входомустановки устройства и с третьим выходом распределителя тактов, четвертый выход которого подключен к тактовому входу блока определения типаошибки, выходы номера проверочногослова и номера комбинации формирователя адреса и режима памяти проверочных символов соединены соответственно с информационными входами коммутатора и блока определения типаошибки, третий вход формирователя адреса и режима памяти проверочных символов связан с выходом четности четверки байтов данных блока определения четности четверки байтов, информационный вход устройства подключенк информационному входу регистра данных, выход которого соединен с входом данных буферной памяти данных ипервым информационным Входом третьего мультиплексора, второй адресныйвход буферной памяти данных связанс выходом признака формирования младших разрядов адреса блока определениячетности четверки байтов, а выход - спервым информационным входом первогомультиплексора, второй информационный вход которого подключен к выходу второго мультиплексора, а выход -к второму информационному входу третьего мультиплексора, выход записина дисковую память задатчика режимаподключен к управляющему входу третьего мультиплексора, выход которогосоединен с первым входом сумматора,выход младших разрядов счетчика адреса связан с входом установки работы с проверочным словом задатчикарежима, выход чтения проверочногослова которого подключен к входу чтения проверочного слова блока определения типа ошибки и входу чтения про" верочного слова формирователя адреса и режима памяти проверочных символов, управляющий вход коммутатора соединен с выходом разрешения работы задатчика режима, а выход - с управляющимвходом четвертого мультиплексора, первый, второй и третий информационные входы которого связаны с выходамисоответственно сумматора, первого ивторого умножителей, а выход - с информационным входом памяти проверочных символов, информационный вход регистра проверочных символов подключен к выходу памяти проверочных символов, а выход - к второму входусумматора, выход которого соединенс входами первого и второго умножителей и с вторым информационным входом второго мультиплексора, выходвторого мультиплексора через элемент ИЛИ соединен с входом признака ошибки блока определения типа ошибки, выхоц которого связан с информационнымвходом регистра типа ошибки, управляющий вход регистра типа ошибки подключен к входу начальной установкиустройства, а выход - к третьему вы 2Устройство по и. 1, о т л и ч аю щ е е с я тем, что эадатчик режима содержит первый и второй триггеры, дешифратор и три элемента И, выходы которых соединены с выходами строба регистра данных, строба выходного регистра и чтения с дисковой памяти, задатчика режима, а входы - с тактовым входом эадатчика режима, с выходами второго триггера и первым выходом дешифратора, установочные входы первого и второго триггеров связаны с входом начальной установки эадатчика режима, информационный вход второго триггера соединен свходом установки режима чтения-записи задатчика режима, выход первого триг-, гера связан с выходом разрешения ра1315979 12элемента 2 И-ИЛИ, выход которого свя.зан с выходом строба регистра проверочных символов блока. 11боты эадатчика режима и первым входом дешифратора, второй вход которо го подключен к выходу второго триггера, а выходы - к выходам записи проверочного слова чтения провероч ного слова, записи на дисковую память задатчика режима.3. Устройство по п.1, о т.л и - ч а ю щ е е с я тем, что блок определения четности четверки байтов со-. Ю держит счетчик, регистр, элемент 2 ИИЛИ, элемент ИЛИ, входы которого соединены с входом тактового блока, а выход связан с выходом строба регистра проверочного слова блока и вхо дом элемента 2 И-ИЛИ, установочный и счетный входы счетчика подключены соответственно к установочному и тактовому входам блока, а выходы - к выходам признака формирования млад ших разрядов адреса и разрешения выдачи нулевого байта блока и к первому входу регистра, второй вход которого соединен с установочным входом блока, а выходы - с входами 4, Устройство по п.1, о т л и - ч а ю щ е е с я тем, что блок определения типа ошибки содержит регистр сдвига, мультиплексор, два элемента И, причем, тактовый вход блока соединен с первыми входами элементов И и с сдвигающим входом регистра сдвига, выходы которого соединены с управляющими входами мультиплексора, вход признака ошибки блока соединен с установочным входом регистра сдвига и первым информационным входом мультиплексора, второй и третий информационные входы которого соединены с шинами нулевого и единичного сигнала, выходы мультиплесора .оединены с вторыми входами первого я второго элементов И, третьи и четвертые входы которых соединены с информационным входом и входом чтения проверочного слова блока.1315979И фиг, 5Составитель А.ДавТехред М. Хода нич Решетник рректо едактор В.Данко ПодписноеР Тираж 672 ВНИИПИ Государственног по Делам иэобретеннй 113035, Москва, Ж, Заказ 2364/ комитет и открытии аушская наб д л.Проектная,4 Пр водственно-полиграфическое предприятие, г.Ужго