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

 

ОП ИСАН ИЕ

ИЗОБРЕТЕНИЯ

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ союз Советских

Социалистических

Республик

Зависимое от авт. свидетельства №

Заявлено 29.Ч1.1966 (№ 1087284/26-24) с присоединением заявки №

Приоритет

Опубликовано 29.XI I.1967. Бюллетень ¹ 3

Дата опубликования описания 19.111.19á8

Кл. 42пт, 14

МПК 6 06Е

УДК 681.142.07(088.8) Комитет по делам изобретений и открытий при Совете Миниотров

СССР

Авторы изобретения

В. С. Лапин и В. И. Левенштейн

Заявитель

УСТРОЙСТВО ДЛЯ ИСПРАВЛЕНИЯ ОШИБОК В МНОГОРЯДОВОЙ СИСТЕМЕ ПЕРЕДАЧИ ДАННЫХ

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

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

Это позволяет исправить пакет ошибок в одном из каналов передачи информации.

На чертеже представлена блок-схема устройства.

Устройство содержит: буферный регистр 1; узел 2 кодирования и декодирования; узел 8 возведения числа в степень L; узел 4 вычисления кода и адреса пакета ошибок и исправления пакета ошибок, узел 5 запоминающего устройства; узел 6 управления.

При записи информации на магнитную ленту из узла 5 поступает по цепи 7 в регистр 1 информация очередной строки (строка — часть сообщения, записываемая по раоочим дорожкам магнитной ленты на одном такте); из регистра 1 последовательно разряд за разрядом информация строки поступает в узел 2, где производится кодпровани информации корректирующим кодом. По окончании кодирования информации очередной строки эта информация, сохраняемая в регистре 1, передается (следует на переда»у) по цепи Ь на запись за магнитную ленту, при этом в уэлс 2 результат кодирования сохраняется и используется при кодиров lнии информации следующей строки. Аналогичным образом производится кодирован <е и запись на ленту информации следующих строк. По окончании кодирования информации последней строки кодпруемого сообщения в узле 2 будет сформирована контрольноисправляющая сумма, которая по цепи 9 будет передана в регистр 1 и затем по цепи 8 будет передана на запись на магнитную лен2о ту. На этом кодирование и запись блока информации на магнитную ленту заканчивается.

При считывании информации с магнитной ленты информация очередной считываемой

25 строки по цепи 10 пост пает в регистр 1, после чего по цепи 11 следует на декодирование в узел 2; результат декодирования в узле 2 сохраняется и используется при декодировании информации следующей строки. Пп

30 окончании декодирования информации оче208348

Информация сообщения

1100111

0101001

0110101

0001101

1111101

0011101

0111010

0010011

1 дорожка (ряд)

2 дорожка (ряд)

3 дорожка (ряд)

4 дорожка (ряд) 1100

0001

1011

110

55

1 100

0001

1 дорожка

2 дорожка

3 дорожка

4 дорожка

65 редной считываемой строки информация данной строки по цепи 12 поступает в узел 5. Пое щцо как. будет закончено декодирование оследней строки закодированного сообщения, считываемого построчно с магнитной ленты, и последняя строка будет отослана в узел

5 из регистра 1, в узле 2 производится проверка на обнаружение ошибки в считанной с магнитной ленты информации.

Если проверка показывает, что характеристика ошибки в результате декодирования равна нулю, то это свидетельствует о том, что информация блока считана с магнитной ленты без ошибок. Случай, когда характеристика ошибки отлична от нуля, свидетельствует об обнаружении ошибки; прп этом число-характеристика по цепи 18 отсылается в узел 8, где производится возведение этого числа в степень L, где L есть число, L: 2 mod п, где n — длина кода, r =1, 2, 3, 4... Полученное в результате возведения в степень L число передается в узел 4, где происходит вычисление поразрядной структуры и адреса исправимого пакета ошибок, который случился на одном из рядов (или дорожек магнитной ленты) . По вычисленному адресу из узла 5 по цепи 14 поступ",åò в узе,л 4 искаженная ошибкой информация. В узле 4 происходит исправление ошибки, и восстановленная информация по цепи 15 поступает в узел 5. Случай, когда произошла нсправимая комбинация ошибок, фиксируется узлом 4 отдельно. Управление взаимодействием всех узлов устройства осуществляется узлом 5— узлом управления.

Разрядность буферного регистра 1 равна разрядности строки. Узел 2 есть узел кодирования и декодирования информации; для циклического кода, порождающий многочлен которого d(x) имеет степень и — к, в основе узла 2 лежит обычно схема сдвигового регистра (n — к разрядов), осуществляющая деление многочлена, соответствующего кодируемой (или декодируемой) информации, на порождающий многочлен кода d(x). Схема сдвигового регистра известна и предметом изобретения не является. В случае, когда накопитель на магнитной ленте используется в вычислительной машине в качестве запоминающего устройства, общая блок-схема устройства сохраняет свою структуру, только функции узлов 8, 4 и 5 выполняет программное устройство вычислительной машины с оперативной памятью машины. Характеристика ошибки при декодировании в случае ее обнаружения узлом 2 отсылается в вычислительную машину, где уже находится только что считанный блок информации с ошибкой; при этом управление передается программному устройству машины, которое производит возведение числа-характеристики в степень

L; где Е: — 2 mod и, где r = 1, 2, 3..., и — длина кода, затем последующее вычисление кода и адреса пакета ошибок и исправление ошиб5

25 ки в информации, хранящейся в оперативной памяти машины.

Процесс исправления пакета ошибок на магнитной ленте, выполняемый устройством, проиллюстрируем конкретным примером.

Пример. Производится хранение информации на магнитной ленте с 4 информационными дорожками (Т = 4) . Требуется организовать исправление любого пакета ошибок длины до 2-х включительно. Ошибка может случиться на любой дорожке магнитной ленты.

Процесс исправления пакета ошибок рассмотрим на примере использования специального корректирующего кода, исправляющего любой пакет ошибок длины два в данной многорядовой системе передачи и определяемого порождающим многочленом d(x) = (х +1) х (хя+х+1). Длина кода 15 двоичных разрядов. Количество разрядов сообщения к=-8. Известно также, что в данном конкретном случае 2 = 4.

Предположим, что на запись на магнитную ленту поступило сообщение

10111001

B узле 2 производится кодирование информации сообщения.

Последовательность кодирования схемой сдвигового регистра

По окончании кодирования контрольно-исправляющая сумма 0 0 1 0 0 1 1 отсылается через регистр 1 на запись на магнитную ленту.

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

Тогда в процессе считывания информация через регистр 1 проходит на декодирование в

208348

111ОО1О

+11100111

ООООО11

Информация ñîî6щения

О

1

О

1 о о о о о

5 следующей последовательности (начиная со старших ра".ðÿäîâ)

14 13 12 11 10 9 8 7 6 5 4 3 2 1 О М разряда

1 О 1 1 1 Ю Ц 1 Ю 0,0!Ю Ю 1 1 инфоРмации

В узле 2 производится декодирование информации считанного сообщения

Последовательность декодирования схемой сдвигового регистра

11ОО111

О1О1ОО1

О1101О1

ООО11О1

1111101

О0111O1

1О111О1

О111О1О

111О1О0

ООО1111

ОО1111О

О1111ОО

1111ООО

111ОООО

1 число-xBpBKTGристика ошибки

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

1 1 0 0 0 0 0 отсылается в узел 3, где производится возведение его в степень 4.

Возведение в степень 4 в данном случае сводится к преобразованию числа

1 1 0 0 0 0 0 к виду

1ООО 1ООО

Для циклического кода с порождающим многочленом, определяемым числом 1 1 1 Ю 0 1 1 1, получим, приведя преобразованное число по модулю 1 1 1 0 0 1 1 1

+10О0 000000000000 0000000О

11100111

+1! 100111

+11100100

1!!00111

11100111

10011100 !

1100111

11100111 !!0001000

11100111 — 11011110

1110011!

11100! 0

Полученное число 1 1 1 0 0 1 0 соответствует для данного кода возведению в степень 4 числа 1 1 00000. Число 1 1 1 00 1 0 отсылается в узел 4, где происходит поиск кода и адреса пакета ошибок и исправление ошибки.

В результате на первом же такте (i =1) обнаружена исправимая комбинация ошибок

10 0000011

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

Так как i — 1, то, поскольку (n — 1) Т+к (mod n) и и = 15, к=8, 7 = 4, получим, что

j=4. Следовательно, номер первого искаженного разряда в сообщении = 4, а номер следующего искаженного разряда j" = + T=8.

Производится исправление пакета ошибок длины два (по адресу j =-4 и !" =8) .

14 13 12 11 10 9 8 7 6 5 4 3 2 1 0 М разряда

0 1 Ю 1 Ю 0 Ю 0 Ю 1 "" "" . с ошибкой ошибка ис1 Ю 1 1 1 0 0 1 0 0 1 0 0 1 1 правлена

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

При использовании длинных циклических кодов можно обеспечить величину избыточности информации порядка 1+2а/р, причем возможно организовать исправление пакетов

45 Ошибок различной Длинь! В многорядовой системе передачи.

Предмет изобретения

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

208348

Составитель В. А. Субботин

Редактор В. В. Сорокина Текред А. А. Камышникова Корректор М. П. Ромашова

Заказ 1398/21 Тираж 530 Подписное

ЦНИИПИ Комитета пс делам изобретений и открытий при Совете Министров СССР

Москва, Центр, пр. Серова, д. 4

Типография, пр. Сапунова, 2