Реализация операций умножения и деления многочленов в поле двоичных чисел

Операции умножения и деления многочленов реализуются с помощью регистров сдвига, состоящих из сумматоров, запоми­нающих устройств и устройств умножения. Сумматор (рис. 1.1, а) представляет собой устройство, осуществляющее сложение по модулю 2 величин на входах 1 и 2. Запоминающее устройство (рис. 1.1,6) служит для хранения в течение определенного вре­мени постоянной величины а.

Рис. 1.1. Функциональное обозначение сумма­торапо модулю два (а), запоминающего уст­ройства (б) и устройства умножения (в)

Устройство умножения (рис. 1.1, в) осуществляет умноже­ние некоторой входной величины с на постоянный множитель а.

Умножение многочленов

Умножение некоторого произвольного многочлена f1 (х) = = а0 +a1x+…+an-1xn-1+anxn на фиксированный много­член f2(х)=b0+b1x+…+bk-1xk-1+bkxk осуществляет­ся спомощью регистров сдвига, изображенных на рис. 1.2. Эти регистры строятся по виду многочлена f2 (x) и отличаются лишь расположением сумматоров. Предполагается, что регистр пер­воначально находится в нулевом состоянии. На вход регистра поступают коэффициенты многочлена f1 (x). начиная со стар­шей степени, а затем следуют k нулей.

Схема, изображенная на рис. 1.2, а и представляющая со­бой регистр с вынесенными сумматорами, работает следующим образом. Когда на входе имеет место первый коэффициент ап, то на выходе появляется первый коэффициент произведения f1(x)f2(x), равный anbk. Кроме того, коэффициент аn запоми­нается в первой ячейке памяти регистра. Со вторым тактом на входе появляется коэффициент an-1 и записывается в первую ячейку памяти, а коэффициент аn этим же тактом переписыва­ется из первой во вторую ячейку регистра. При этом на выходе схемы появляется значение второго коэффициента произведения f1(x) f2 (x), равное (ап-1 bk+ an bк-1 ) и так далее.

Таким образом, схема работает в соответствии с таблицей.



Следовательно, произведение будет равно:




Схема, изображенная на рис. 1.2,6 и представляющая со­бой регистр с встроенными сумматорами, работает аналогично предыдущей. Очевидно, что обе схемы равноценны.

выход

Рис. 1.2. Реализация умножения многочленов с помощью регистров сдвига с вынесенными (а) и встроенными (б) сумматорами

Рассмотрим некоторые характерные особенности построения этих схем для многочленов с двоичными коэффициентами, а именно с коэффициентами 0 и 1.

Умножение на величину bi производим по правилу:

Для bi= 0 :ajbi=aj0=0,

и для bi=1:ajbi=aj*1=aj,

Таким образом, умножение на 0 соответствует разорванной цепи, а умножение на 1 — короткому замыканию.

Пусть, например, f2 (X) = 1 + х+ х3 +x5, т. е. b0= 1, b1= 1,

b2=0,b3=1,b4=0,b5=1.


Рис.1.3. Устройство умноженияна многочлен f (x) = 1 + х + x3 + х5

Схема умножения на многочлен реализуется с помощью ре­гистра с встроенными сумматорами, имеющего вид, представ­ленный на рис. 1.3. Как видно из рис. 1.3, сумматор, на который подан только один вход, может быть устранен.

Аналогично строится регистр с вынесенными сумматорами.

Деление многочленов

Операция деления многочленов может быть реализована с помощью регистра сдвига с обратными связями. Схема деле­ния произвольного многочлена f1(х) = a0+a1x+…+an-1xn-1+anxn на постоянный многочлен f2 (х)= b0+b1x+…+bk-1xk-1+bkxk представлена на рис. 1.4.



Рис. 1.4. Реализация деления на многочлен с помощью регистра сдвига c обратными связями

До поступления многочлена f1 (x) на вход схемы, запоминаю­щие элементы должны находиться в нулевом состоянии. На выходе схемы будет 0 до тех пор, пока первый элемент аn мно­гочлена f1(x) не достигнет конца регистра, т. е. в течение пер­вых k сдвигов. После этого на выходе в соответствии с (1.3) по­явится первый элемент частного, а именно an/bkили an*bk-1,по­лучаемый умножением элемента аn, следующего из последней ячейки памяти, на величину bk-1. Как видно из (1.3), для каж­дого ненулевого коэффициента частного с, из делимого необхо­димо вычесть многочлен cif2(x). Вычитание осуществляется в сумматорах по модулю два после умножения коэффициента частного, например anbk-1 , на множители —bо, b1,…,bk-1.

Поскольку мы рассматриваем двоичное поле, то коэффици­енты b0,b1,…,bk-1 могут принимать значения 0 или 1, а зна­чение bк —только 1. Учитывая также, что при сложении по модулю 2 знак минус может быть заменен плюсом, схема на рис. 1.4 значительно упростится, если устройства умножения заменить, как и в регистрах умножения, короткими замыкания­ми для bi = 1 и обрывом цепи для bi = 0. При этом число встроенных в регистр сумматоров уменьшится и будет равно числу единичных коэффициентов bi= 1 (i =0, 1, .,., k—1).

Пример. Пусть f2 (х) = 1 +x2 + х4 + х5 т. е. bо =1, b1=0,b2=1,b3=0,b4=1,b5=1.


Рис. 1.5. Схема деления на многочлен f(x)= 1 +x2+ х4+x5


Рис. 1.6. Схема, реализующая одновременное умножение на много член f2(x)=b0+b1x+…+bkxk и деление на многочлен f3(x)=c0+c1x+…+ck bв0 -I- п.х + ... + ekxk и деление на многочлен /s(*) =

На рис. 1.5 представлена схема деления на заданный мно­гочлен.


На основе регистра с встроенными сумматорами может быть построена схема (рис. 1.6), реализующая одновременное умно­жение на многочлен f2(x)=b0+b1x+b2x2+…+bkxk и деление на многочлен f3(x)=c0+c1x+c2x2+…+ckxk.

2. ОБЩИЕ ПРИНЦИПЫ ПОСТРОЕНИЯ ЦИКЛИЧЕСКИХ КОДОВ

Характерной особенностью циклических кодов является представление кодовых комбинаций длины п многочленами сте­пени п— 1 вида

f(x)=c0+c1x+c2x2+…+cn-1xn-1. (2.1)

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

Другой распространенной формой представления комбина­ций циклического кода является векторная форма (coc1c2 ... сn-1), где элементы кода с1- являются коэффициентами много­члена f(x), принадлежащими простому полю GF (р). Для дво­ичных циклических кодов коэффициенты сi принадлежат полю GF (2), т. е. принимают значения 0 и 1.

Таким образом, обе формы представления комбинаций свя­заны между собой тем, что одна вытекает из другой. Например, комбинации (1010001) соответствует многочлен f (x)= 1+x2+ х6.

Приведем основные свойства циклических кодов, которые определяют их построение.

Свойство 2.1. Циклический код в полиномиальном его пред­ставлении можно определить как множество многочленов степени п—1 и меньше, каждый из которых делится без остатка на некоторый многочлен Р (х), называемый образующим или порождающим многочленом кода.

Из этого свойства вытекает, что для каждой комбинации циклического кода, представленной многочленом f(x), справед­ливо сравнение

f(x)=[mod Р(х)]. (2.2)

Свойство 2.2. Если некоторая комбинация (c0c1c2…cn-1) принадлежит какому-либо циклическому коду, то и комбинация, полученная из предыдущей в результате циклического сдвига ее элементов, например (сn-1 c0c1 … cn-2), также принадлежит этому циклическому коду.

Это свойство основывается на свойстве 1.3 полей Галуа, со­гласно которому любой неприводимый в поле двоичных чисел многочлен Р (х) степени т является делителем двулена (x2^m-1-1), т. е.

x2^m-1-1≡0[modP(x)].(2.3)

Таким образом, выбрав длину комбинации п, удовлетворяю­щую равенству п = 2т — 1, получим

xn-1≡0[modP(x)].(2.4)

При таком значении п, умножив на х многочлен комбинации циклического кода f(х), представленного в виде (2.1), получим: x*f(x) =сох + с]х2+ ... + сn-2хn-1 + сn-1хn. В силу (2.4) можно записать: сn-1xn≡сn-1[mod Р (х)].Тогда

x*f(x)≡сп-1 + сох+с1х2 + ... +сn-2хп-1 (2.5)

Но так как согласно свойству 2.1 многочлен f(x) делится на Р (х) без остатка, то и многочлен xf (x), представленный много­членом (2.5), также делится на Р(х). Отсюда вектор (сn-1сос1 ... сn-2 ), полученный из исходной комбинации цикли­ческого кода (c0c1c2…сn-1) путем циклического сдвига, будет принадлежать также циклическому коду. Из доказательства свойства 2.2 вытекает следствие, которое заключается в том. что для большинства циклических кодов п = 2т—1, где т — степень образующего неприводимого многочлена Р (х). Но на практике иногда выбирают длину комбинации n1меньше 2m-1. Такой циклический код называют укороченным.

Рассмотрим теперь общие принципы построения цикличе­ского кода. Задачей кодирующего устройства является преоб­разование k-элементной комбинации (aoa1 ... аk-1 ) исходного безызбыточного кода в n-элементную комбинацию (c0c1c2 ... cn-1) избыточного циклического (п,k)-кода. Таким образом, каждая комбинация циклического кода содержит п—k избы­точных элементов.

Задачей декодера является обратное преобразование при­нятой n-элементной комбинации циклического кода в исходную k-элементную комбинацию. При этом эффективность цикличе­ского кода оценивается его способностью корректировать воз­никающие при передаче по каналу ошибки.

Существует несколько способов кодирования. Наиболее про­стой из них заключается в том, что многочлен (2.1), соответст­вующий комбинации циклического кода, получают путем умно­жения многочлена φ(х) = aо + а1x+ ... ak-1 xk-1, соответ­ствующего исходной комбинации, на образующий многочлен Р(х) степени т, т. е.

f(x) = φ(x)P(x). (2.6)

Отсюда видно, что для циклического (п, k)-кода степень образующего многочлена m = п— k, т. е. равна числу избыточных элементов комбинации.

Циклический код, построенный в соответствии с (2.6), на­зывают несистематическим, так как среди элементов комбина­ции (c0c1c2 ... cn-1) нельзя выделить информационные и избы­точные или проверочные.

Другой способ кодирования соответствует систематическому циклическому (п, k)-коду.Построение систематического цикли­ческого кода сводится к тому, чтобы к информационным эле­ментам a0, a1, … ak-1 исходного k-элементного кода добавить (п—k) полученных определенным образом избыточных элемен­тов. Причем в каждой комбинации n-элементного циклического кода информационные и избыточные элементы будут занимать определенные позиции. Значения добавленных избыточных эле­ментов должны определяться таким образом, чтобы выполня­лось свойство 2.1 циклических кодов, т. е. деление без остатка на образующий многочлен Р (х).

Чтобы построить систематический циклический код, комби­нацию исходного k-элементного кода, принадлежащую группе порядка 2к, записывают в виде многочлена φ(х)степени к—1. Затем многочлен φ(х) умножается на хn-k, что равносильно приписыванию к исходной k-элементной комбинации n — k ну­лей со стороны младшего разряда.

Например, необходимо умножить многочлен φ(х) = 1 +x+x2 на хn-k = х3. Тогда имеем хn-kφ(х) = х3 + х4 + х5. Если записать многочлен φ(х) и результат умножения в виде двоичныхкомбинаций, то получим

Для φ(х) — 111,

для x3φ(х)—000111.

Полученное таким образом произведение хn-kφ(х) делим на производящий многочлен Р (х) степени n — k. При делении на производящий многочлен Р (х) образуется частное Q(х) той же степени, что и φ(х) и, кроме того, возможно появление ос­татка R (х), т.е.

Видоизменяя уравнение, получим

Очевидно, что многочлен (2.8) соответствует комбинации ци­клического кода, так как он удовлетворяет основному требова­нию циклических кодов, а именно, делится без остатка на про­изводящий многочлен Р(х).

В дальнейшем будем рассматривать только двоичные коды, поэтому знаки «+» и«—» равноценны.

Если многочлен хn-kφ(х)+R(х) записать в виде комбина­ции, то легко заметить, что систематический циклический (n1k)- код можно построить, приписав к каждой кодовой комбинации исходного k-элементного кода остаток от деления многочлена хn-kφ(х) на производящий многочлен Р(х).

Рассмотрим пример построения систематического циклического (n, k)-кода, для которого n=15, k=11 и n-k=4.

В качестве производящего выбран многочлен P(x)=1+x+x4.

Для кодирования комбинации 10100100001, которой соответствует многочлен φ(х)=1+x2+x5+x10, разделим x4φ(х) на производящий многочлен Р(х) и найдем остаток R(х). В результате находим, что R(х)=1+x. Кодовый многочлен образуется путем сложения x4φ(х) и R(х) согласно (2.8):


Этому многочлену соответствует комбинация циклического кода

1100 10100100001

проверочные информационные

элементы элементы


6897641489984670.html
6897740768941850.html
    PR.RU™