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

ОП ИСАН ИЕИЗОБРЕТЕНИЯК АВТОРСКОМУ СВИДЕТЕЛЬСТВУ Союз Советских Социалистических Республик( 1087284/26-24) Зависимо вт,л. 42 пт, 14 Заявлено 29.Ч 1.19 с присоединением заявкиПриоритетОпубликовано 29.Х 11.1967. Бюллетень3Дата опубликования описания 19.111.19 б 8 МП 1( б 061УДК 681.142.07(088,8 Комитет по делам изобретений и открыт при Совете Миниотро СССР. С. Лапин и В. И. Левенштейн Заявит РОЙСТВО ДЛЯ ИСПРАВЛЕНИЯ ОШИБОК В МНОГОРЯ ВОЙ СИСТЕМЕ ПЕРЕДАЧИ ДАННЫХИзвестны устройства для исправления ошибок в многорядовой системе передачи данных, содержащие буферный регистр, узел кодирования и декодирования информации, узел вычисления номеоа неправильно пере данного разряда, запоминающий блок и узел управления.Предлагаемое устройство отличается от известных тем, что оно содержит схему возведения остатка в заданную степень, подсое диненную к выходу узла кодирования и декодирования информации, а ее выход подключен ко входу узла вычисления кода и адреса пакета ошибок и исправления пакета ошибок, 15Это позволяет исправить пакет ошибок в одном из каналов передачи информации.На чертеже представлена блок-схема уст. ройства.Устройство содержит: буферный регистр 1; 2 узел 2 кодирования и декодирования; узел 3 возведения числа в степень 1.; узел 4 вычисления кода и адреса пакета ошибок и исправления пакета ошибок, узел 5 запоминающего устройства; узел 6 управления. 2При записи информации на магнитную ленту из узла 5 поступает по цепи 7 в регистр 1 информация очередной строки (строка - часть сообщения, записываемая по рабочим дорожкам магнитной ленты на одном 3 такте); из регистра 1 последовательно разряд за разрядом информация строки поступает в узел 2, где производится кодпровани информации корректирующим кодом. По окончании кодирования информации очереднойй строки эта информация, сохраняемая в регистре 1, передается (следует на передачу) по цепи Ь на запись за магнитную ленту, при этом в узле 2 результат кодирования сохраняется и используется при ксдировании информации следующей строки. Аналогичным образом производится кодирование и запись на ленту информации следующих строк. По окончании кодирования информации последней строки кодируемого сообщения в узле 2 будет сформирована контрольно- исправляющая сумма, которая по цепи 9 будет передана в регистр 1 и затем по цепи 8 будет передана на запись на магнитную ленту. На этом кодирование и запись блока информации на магнитную ленту заканчивается.При считывании информации с магнитной ленты информация очередной считываемой строки по цепи 10 поступает в регистр 1, после чего по цепи 11 следует на декодирование в узел 2; результат декодирования в узле 2 сохраняется и используется при декодировании информации следующей строки. По окончании декодирования инфоомацииИнформация сооб- щения 30 1100111 0101001 0110101 0001101 1111101 0011101 0111010 40 0010011 45 110000011011110 1 дорожка (ряд) 2 дорожка (ряд)3 дорожка (ряд) 4 дорожка (ряд) 50 55 1 дорожка 2 дорожка 3 дорожка 4 дорожка 1 1000001 60 65 редной считываемой строки информация данной строки по цепи 12 поступает в узел 5. Пое щцо как будет закончено декодированиеоследней строки закодированного сообщения, считываемого построчно с магнитной ленты, и последняя строка будет отослана в узел 5 из регистра 1, в узле 2 производится проверка на обнаружение ошибки в считанной с магнитной ленты информации.Если проверка показывает, что характеристика ошибки в результате декодирования равна нулю, то это свидетельствует о том, что информация блока считана с магнитной ленты без ошибок. Случай, когда характеристика ошибки отлична от нуля, свидетельствует об обнаружении ошибки; прп этом число-характеристика по цепи 13 отсылается в узел 3, где производится возведение этого числа в степень Е, где Е есть число, Е : 2 гпод и, где и - длина кода, г = 1, 2, 3, 4 Полученное в результате возведения в степень Е число передается в узел 4, где происходит вычисление поразрядной структуры и адреса исправимого пакета ошибок, который случился на одном из рядов (или дорожек магнитной ленты), По вычисленному адресу из узла б по цепи 14 поступает в узел 4 искаженная ошибкой информация. В узле 4 происходит исправление ошибки, и восстановленная информация по цепи 15 поступает в узел б, Случай, когда произошла нсправимая комбинация ошибок, фиксируется узлом 4 отдельно, Управление взаимодействием всех узлов устройства осуществляется узлом б узлом управления. Разрядность буферного регистра 1 равна разрядности строки, Узел 2 есть узел кодирования и декодирования информации; для циклического кода, порождающий многочлен которого д(х) имеет степень и - к, в основе узла 2 лежит обычно схема сдвигового регистра (п - к разрядов), осуществляющая деление многочлена, соответствующего коди руемой (или декодируемой) информации, на порождающий многочлен кода д(х). Схема сдвигового регистра известна и предметом изобретения не является, В случае, когда накопитель на магнитной ленте используется в вычислительной машине в качестве запоминающего устройства, общая блок-схема устройства сохраняет свою структуру, только функции узлов 3, 4 и 5 выполняет программное устройство вычислительной машины с оперативной памятью машины. Характеристика ошибки при декодировании в случае ее обнаружения узлом 2 отсылается в вычислительную машину, где уже находится только что считанный блок информации с ошибкой; при этом управленце передается программному устройству машины, которое производит возведение числа-характеристики в степень Е; где Е = - 2 допой и, где г = 1, 2, 3, и - длина кода, затем последующее вычисление кода и адреса пакета ошибок и исправление ошиб 5 10 15 20 25 ки в информации, хранящейся в оперативной памяти машины.Процесс исправления пакета ошибок на магнитной ленте, выполняемый устройством, проиллюстрируем конкретным примером.П р и м е р, Производится хранение информации на магнитной, ленте с 4 информационными дорожками (Т = 4). Требуется организовать исправление любого пакета ошибок длины до 2-х включительно, Ошибка может случиться на любой дорожке магнитной ленты, Процесс исправления пакета ошибок рассмотрим на примере использования специального корректирующего кода, исправляющего любой пакет ошибок длины два в данной многорядовой системе передачи и определяемого порождающим многочленом д(х) = (хв+1) х (хя+х+1). Длина кода 15 двоичных разрядов. Количество разрядов сообщения к=-8, Известно также, что в данном конкретном случае 2 = 4.Предположим, что на запись на магнитную ленту поступило сообщение10111001 В узле 2 производится кодирование информации сообщения. Посяедоввтельность кодирования схемой сдвигового регистраПо окончании кодирования контрольно-исправляющая сумма 0 0 1 0 0 1 1 отсылается через регистр 1 на запись на магнитную ленту. Предположим, что при считывании с магнитной ленты произошла ошибка, исказившая два разряда по 3 дорожке, при этом информация будет считана в виде Тогда в процессе считывания информация через регистр 1 проходит на декодирование в5 Информация сооб- щения следующей последовательности (начиная состарших разрядов)14 13 12 11 10 9 8 7 6 5 4 3 2 1 0разряда1 0 1 1 10)1)1 О 0,00 011 информацияВ узле 2 производится декодирование информации считанного сообщения Последовательность декодирования схемой сдвигового регистра1100111 0101001 0110101 0001101 1111101 0011101 1011101 0111010 1110100 0001111 0011110 0111100 1111000 1110000 число-характе 1100000ристика ошибки По окончании декодирования информации проверка на обнаружение ошибки показывает, что число-характеристика ошибки отлично от нуля; следовательно, ошибка обнарукена, Число-характеристика ошибки 1 1 0 0 0 0 0 отсылается в узел 3, где производится возведение его в степень 4.Возведение в степень 4 в данном случае сводится к преобразованию числа 1100000 квиду1000 1000 0000 0000 0000 0000 0Для циклического кода с порождающим многочленом, определяемым числом 1 1100111, получим, приведя преобразованное число по модулю 1 1 10 01 1 110001000000000000 ОООООООО111001111011110,100111001100111111101101110011100000011100111- 11011110111001111100 О Полученное число 1 1 1 0 0 1 0 соответствует для данного кода возведению в степень 4 числа 1 1 0 0 0 0 О. Число 1 1 1 0 0 1 0 отсылается в узел 4, где происходит поиск кода и адреса пакета ошибок и исправление ошибки. В результате на первом же такте (г=1) обнаружена исправим ая комбинация ошибок 10 0000011 В двух разрядах справа находится код пакета ошибок, который определяет, что произошло искажение двух разрядов по одной из дорожек. Определяется номер псрвого искаженного разряда.Так как- 1, то, поскольку 1: (п - )Т+к (п 1 ос а) и и = 15, к=8, Т = 4, получим, что 1=4. Следовательно, номер первого искаженного разряда в сообщении 1 = 4, а номер следующего искаженного разряда 1" = + Т=8. Производится исправление пакета ошибок длины два (по адресу =-4 и "=8). 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0разряда 25 1 0 1 1 10110000011 сообщенс ошибкойошибка нс 1 0 1 1 1 0 0 1 0 0 1 0 0 1 1 правлена Необходимо отметить, что факультативный ЗО случай, когда функции узлов 3, 4 и 5 выполняет вычислительная машина, является оптимальным, если при этом накопитель работаст совместно с вычислительной машиной. Время, затрачиваемое машиной на исправление 35 пакета ошиоок прп декодировании, незначительно, т. к. оно расходуется только прп обнаружении ошибки, а в подавляющем большинстве случаев ичформация считывается без ошибок.40 При использовании длинных циклическихкодов можно обеспечить величину избыточности информации порядка +2 г/ причем возможно организовать исправление пакетов 45 ОШРбОк разлРчной Длинь В многорядовой системе передачи. Предмет изобретения Устройство для исправления ошибок в многорядовой системе передачи данньх, содержащее буферный регистр, узел кодирования и декодирования информации, узел вычисле ния номера неправильно переданного разряда, запоминающий блок и узел управления, отличсиощееся тем, что, с целью исправления пакета ошибок в одном из каналов передачи информации, оно содержит схему возведе ния остатка в заданную степень, подсоединенную к выходу узла кодирования и декодирования информации, а се выход подключен ко входу узла вычисления кода и адреса пакета ошибок и исправления пакета оши бок,Заказ 1398/21 Тираж 530 Подписное ЦНИИПИ Комитета пс делам изобретений и открытий при Совете Министров СССР Москва, Центр, пр, Серова, д. 4 Типография, пр, Сапунова, 2