Кодирующее устройство корректирующего кода

 

йосесе4е 3 и э 5 ве1ентмс

СПИ

ИЗОБРЕТЕНИЯ

Союз Советских

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

Республик (») 542354

К АВТОРСКОМУ СВНДЕТЕЛЬСТВУ (61) Дополнительное к авт. свид-ву— (22) Заявлено 04.03.75 (21) 2112512/09 с присоединением заявки № (23) Приоритет (43) Опубликовано05.01.77.Бюллетень ¹ 1 (45) Дата опубликования описания 31.03.77 (51) M. Кл.

Н 04 Ь 3/02

С- 06 F 11/10

Государственный комитет

Совата Министров СССР оа делам изобретений и открытий (53) УДК 621.394..14 (088.8) (72) Авторы изобретения

А.А. Давыдов, Г.М. Тененгольц, З.И. Мунджишвили и Д.В. цискаридзе (71) Заявитель

Ордена Ленина институт проблем управления (54) КОДИРУЮЩЕЕ УСТРОЙСТВО КОРРЕКТИРУЮЩЕГО КОДА

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

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

Основание кода равно двум. Код является циклическим (11.

Однако такое устройство имеет сравнительно низкое быстродействие,, связанное с тем, что двоичная информация обрабатыва- 20 ется поразрядно.

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

Однако это устройство действует медленно, так как после подачи в него всех информационных символов необходимо еще 2 5 тактов сдвига (второй и третий этапы), прежде чем начнут выдаваться ко:.трольные символы. (Здесь 5 — количество контрольных символов) Цель изобретения — повы шение бы с тро†действия устройства.

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

542354 выходом соответствующего разряда блока вычисления контрольных чисел.

На чертеже приведена структурная электрическая схема кодирующего устройства корректирующего кода. 5

Устройство содержит блок вычисления контрольных чисел 1, блок управления 2 и преобразователь "число-код" 3. К управляющему входу преобразователя "число-код" подключен выход блока управления 2, а к )p информационным входам подсоединены соответствующие выходы разрядов блока вычисления контрольных чисел 1, выполненного в виде последовательно соединенных ячеек, каждая из которых состоит из последова- )5 тельно соединенных комбинационного сумматора 4 по модулю числа, равного степени два, и регистра хранения контрольного числа 5, выход которого является выходом соответствующего разряда блока 1. 20

Кодирование происходит в два этапа. В течение первого этапа в блоке 1 вычисляются по информационным символам контрольные числа. На втором этапе преобразователь "число-код" 3 преобразует эти чис- 25 ла в контрольные символы. которые передаются на выход устройства.

Перед началом работы устройства регистры 5 всех разрядов блока 1 обнуляются.

Затем на вход устройства последовательно (начиная с символа с(к ) пэступают ичные инфэрмациэнные символы +g,((„g",ag

Каждый информационный символ может принимать одно из значений 0,1,..., $ — 1.

При выполнении устройства на двоичных элементах каждый информационный символ представляет собой 9/ -разрядное число, записанное в двэичной системе счисления.

Блок 1 вычисляет контрольные числа за

"к" шагов. На каждом шаге обрабатывается один информационный символ (на первом— символ (К, на втором С „и т.д.). РезулЬтаты обработки записываются в регистры (5 хранения контролируемых чисел 5. Обозначим через 15 1. число, записанное в i --тый регистр 5 после u -того шага. Тогда рабэту блока 1 на (V + 1)-вэм шаге можно описать следующим образом. Информационный символ CL „о поступает в первый сумматор 4, где складывается с содержимым (е) первого регистра 5 (т.е. с числом В ()), Полученная сумма с(„ +В представляет ((У) (Г+ ) собой число В4 и записывается в первый регистр 5 как результат нэвэго шага. (u) (v+ 1)

Одновременно сумма ((,„ +В = Ь 4 поступает вэ второй сумматор 4, где складывается с содержимым второго резистра 5 (т.е. с числом В ). Полученная сумма gp (u ) (vms) (т)

В, В2 представляет собой число (и+1)

Â2 и записывается во второй регистр 5 как результат нэвэгэ шага. Одновременно сумма В (В2 = В 2 поступает в тре(v+ s)+ (e) (о т ц тий сумматор 4, где складывается с сэдержимым третьего регистра 5 (т.е. с числом

5 (o-)

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

1 в регистры 5 записаны соответственно (К) B (к) B (к)

S и являются искомыми контрольными числами.

Вычислением контрольных чисел заканчивается работа блока 1 на первом этапе.

Преобразователь "число-код" 3 на этом этапе не включается.

На втором этапе контрольные числа в соответствии с управляющими сигналами, поступающими на управляющий вход преобразователя 3, проходят из регистров 5 блока 1 на соответствующие информационные входы преобразовareas "число-код" 3, где каждое контрольное число В . преобразуетК

1 ся в соответствующую ему 1 -тую группу контрольных символов, В преобразователе

3 образуется наименьший неотрицательный вычет 1) ° числа 5„- по модулю ;, пред(К) ставляющему собой степень двойки, причем образование вычета 5 сводится к отбрасы1 ванию старших разрядов соответствующего (К) контрольного числа В . . При этом отбра1 сывается тп. - n . .старших разрядов и об1 разуется п -разрядное двоичное число . Разделяя это число на подблоки по ь ф двоичных разрядов в каждом, преобразоЪ ватель 3 формирует 1 -тую группу контрольных символов, так как такое разделение есть не что иное, как формирование — ичной записи числа ()

В преобразователе "число-код 3 формируются S групп контрольных символов (из каждого контрольного числа формируется группа контрольных символов). Эти группы проходят на выход устройства. На вход устройства на втором этапе работы информационные символы не подаются. Роль блока

1 на втором этапе заключается в хранении в регистрах 5 вычисленных на первом этапе контрольных чисел.

Формированием групп контрольных симвб542354 лов и выдачей их на выход устройства про цесс кодирования завершается, Контрольные символы вычисляются в устройстве таким образом, что любые две кодовые последовательности отличаются друг от друга по крайней мере в 6+1 позициях, Это значит, что минимальное кодовое пас стояние равно 5+1, и в информации, закодированной с помощью предлагаемого ус ройства, можно исправить 5(2 ошибок. 10

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

Ф -разрядное двоичное число, а каждое !5 (К1 контрольное число В; является rA„-разрядным двоичным числом.

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

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

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

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

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

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

Источники информации, принятые во вни-. мание при экспертизе:

1. Берлекзмп Э. Алгебраическая теория кодирования, "Мир", М., 1971, стр. 134, 1 38-142.

2. Авторское свидетельство СССР

М 443389, G 06 F 11/10, 14.11 72.у f

: м

542354

Составитель И. Черняк

Редактор Б. Федотов Техред А. демьянова Корректор Б. К)гас

Заказ 6002/37 Тираж 864 Подписное

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

1 1 3035, Москва, Ж вЂ” 35, Раушская наб., д. 4/5

Филиал ППП "Патент", г. Ужгород, ул. Проектная, 4