Устройство для кодирования двоичных циклических кодов

 

3356 9I

ОПИСАНИЕ

ИЗОБРЕТЕНИЯ

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

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

Республик

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ

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

Заявлено 24.VIII.1970 (№ 147407т/18-24) с присоединением заявки №

Приоритет

Опубликовано l 1.1V.1972. Бюллетень ¹ 13

Дата опубликования описания 18Х.1972

М. Кл. G 06f 11/12

Комитет по делам иаооретеиий и открытий при Сосете Министров

СССР

УДК 681.326.7(088.8) Автор изобретения

В. Н. Стародубцев

3 аявитель

УСТРОЙСТВО ДЛЯ КОДИРОВАНИЯ ДВОИЧНЫХ

ЦИКЛИЧЕСКИХ КОДОВ

Изобретение относится к устройству кодирования для двоичного циклического кода и может найти применение в тех областях вычислительной техники и техники передачи данных, где повышение помехоустойчивости информации производится с помощью циклических кодов, порождаемых различными полиномами, в частности в больших информационных и управляющих системах. Как известно кодовый полипом fp(x), принадлежащий циклическому коду, находится по информационному полиному f (x) как f p (x) = f (x) x +r (x), где r(x) — остаток от деления f(x)x" на порождающий полином g(x) степени r.

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

Деление осуществляется путем последовательного сложения по модулю два делителя вначале со старшими членами делимого, затем со старшими членами (начиная с первого значащего члена) получившегося остатка, и так до тех пор, пока, наконец, степень остатка не станет меньше степени делителя.

Реализация этих операций при делении любого полинома на определенный полином g(x) степени r производится сдвигающим регистром со встроенными сумматорами по модулю

2, охваченным обратными связями. Места включения сумматоров определяются коэффициентами полинома g(x).

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

Недостатком существующих кодирующих устройств является то, что они осуществляют

10 нахождение кода, порождаемого фиксированным полиномом g(x). При этом для кодирования информации при работе по Ж каналам требуется N различных устройств кодирования. При необходимости нахождения кодов, 15 порождаемых большим количеством различных полимов, более экономично производить кодирование в одном универсальном устройстве, позволяющем находить коды, порождаемые различными полиномами.

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

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

335691

65 полинома, на который необходимо производить деление, и управления схемами «И», Порождающий полином записывается в запоминающем регистре в нормализованной форме, т. е. вместо полинома степени j(r записывается полином g(x)x — >. При этом старший член полинома имеет степень r, а младшие члены r — / являются нулями. В итоге после /г сдвигов получаем остаток от деления f(x)x> на g(x)x — >, т. е. тот же самый результат, что и при делении f(х) х на a(x).

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

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

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

Запоминающий регистр 1 состоит из r запоминающих ячеек Π—:(r — 1), в которые из запоминающего устройства 2 поступают коэффициенты полинома д (х)х" — ), где j(I за исключением коэффициента при х . С тех запоминающих ячеек Π—: (r — 1), в которых записаны «1», подаются разрешающие сигналы на соответствующие схемы «И» 8 (Π— (г — 1)).

Это создает цепи обратной связи, соответствующие полиному, порождающему код.

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

На регистр 1 поступают коэффициенты полинома, порождающие необходимый код, начиная с коэффициента при степени r — 1, При этом полинам представляется в нормализованном виде, т. е. если степень полинома j (r, то он записывается умноженным на х" — 1 с тем, чтобы коэффициент при старшем члене находился на позиции r. При этом коэффициенты при младших r — j членах будут равны О.

Коэффициент при члене 0 степени нормализованного порождающего полинома записыва5

40 ется в ячейку 1О прн члене первой степени в ячейку 1 и т. д., при члене r — 1 степени— в ячейку 1 (r — I). С выходов ячеек запоминающего регистра, в которых записаны «1», подаются разрешающие сигналы на соответствующие схемы «И», и таким образом создаются необходимые цепи обратной связи для суммирования информационных символов с порождающим полиномом.

Процесс деления состоит из последовательных сдвигов и вычитания (суммирования) rro модулю 2 информационного полинома f(x) умноженного на х, и порождающего полинома g(x), умноженного на х — >. Это эквивалентно делению f(x)xr íà g(x), т, е. тому, что выполняет обычная схема кодирования для циклического кода, порождаемого фиксированным полиномом g(x) степени j.

Коэ ффициенты информационного полинома 7, начиная с коэффициентов при членах старших степеней, поступают на вход сумматора б. Тем самым они умножаются на х". На другой вход сумматора б поступают сигналы со старшего разряда сдвигающего регистра 4 (» — 1). Последовательность сигналов с выхода сумматора б, являющаяся частным от деления f(x)x> на порождающий полином g(x) степени j через схемы обратной связи «И», на которые подано разрешение с регистра порождающего полинома, поступает на соответствующие сумматоры 5. Таким образом производится суммирование содержимого сдвигающего регистра с порождающим полиномом.

Так как результат суммирования старших разрядов делимого и делителя всегда равен О, то сумматор для этой операции не предусмотрен.

После поступления К коэффициентов информационного полинома в ячейках сдвигающего регистра 4 (r — 1) —: (r — 1) остается остаток от деления, являющийся совокупностью проверочных символов кода.

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

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

«И» соединен со входом сдвигающего регистраа.

335691

Ф .5

Составитель В. Крылова

Техред Т. Курилко

Редактор Л. Утехина

Корректор О. Тюрина

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

Заказ 1295/10 Изд. № 4бб Тираж 448 Подписное

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

Москва, Я-35, Раушская наб., д. 4j5