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

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

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

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

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

Умножение некоторого произвольного многочлена f₁ (х) = = а₀ +a₁x+…+a_n-1x^n-1+a_nxⁿ на фиксированный много­член f₂ (х)=b₀+b₁x+…+b_k-1x^k-1+b_kx^k осуществляет­ся с помощью регистров сдвига, изображенных на рис. 1.2. Эти регистры строятся по виду многочлена f₂ (x) и отличаются лишь расположением сумматоров. Предполагается, что регистр пер­воначально находится в нулевом состоянии. На вход регистра поступают коэффициенты многочлена f₁ (x). начиная со стар­шей степени, а затем следуют k нулей.

Схема, изображенная на рис. 1.2, а и представляющая со­бой регистр с вынесенными сумматорами, работает следующим образом. Когда на входе имеет место первый коэффициент а_п, то на выходе появляется первый коэффициент произведения f₁ (x)f₂(x), равный a_nb_k. Кроме того, коэффициент а_n запоми­нается в первой ячейке памяти регистра. Со вторым тактом на входе появляется коэффициент a_n-1 и записывается в первую ячейку памяти, а коэффициент а_n этим же тактом переписыва­ется из первой во вторую ячейку регистра. При этом на выходе схемы появляется значение второго коэффициента произведения f₁ (x) f₂ (x), равное (а_п-1 b_k+ a_n b_к-1) и так далее.

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

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

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

выход

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

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

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

Для b_i= 0:a _jb_i=a_j0=0,

и для b _i =1 :a_jb_i=a_j*1=a_j,

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

Пусть, например, f₂ (X) = 1 + х+ х³ +x ⁵, т. е. b ₀ = 1, b₁= 1,

b₂=0,b₃=1,b₄=0,b₅=1.

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

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

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

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

Операция деления многочленов может быть реализована с помощью регистра сдвига с обратными связями. Схема деле­ния произвольного многочлена f₁ (х) = a₀+a₁x+…+a_n-1x^n-1+a_nxⁿ на постоянный многочлен f₂ (х)= b₀+b₁x+…+b_k-1x^k-1+b_kx^k представлена на рис. 1.4.

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

До поступления многочлена f₁ (x) на вход схемы, запоминаю­щие элементы должны находиться в нулевом состоянии. На выходе схемы будет 0 до тех пор, пока первый элемент а_n мно­гочлена f₁(x) не достигнет конца регистра, т. е. в течение пер­вых k сдвигов. После этого на выходе в соответствии с (1.3) по­явится первый элемент частного, а именно a_n/b _kили a_n*b_k^-1,по­лучаемый умножением элемента а_n, следующего из последней ячейки памяти, на величину b_k^-1. Как видно из (1.3), для каж­дого ненулевого коэффициента частного с, из делимого необхо­димо вычесть многочлен c_if₂(x). Вычитание осуществляется в сумматорах по модулю два после умножения коэффициента частного, например a_nb_k^-1, на множители — b_о, b₁,…,b_k-1.

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

Пример. Пусть f₂ (х) = 1 +x² + х⁴ + х⁵ т. е. b _о = 1, b₁=0,b₂=1,b₃=0,b₄=1,b₅=1.

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

Рис. 1.6. Схема, реализующая одновременное умножение на много член f₂(x)=b₀+b₁x+…+b_kx^k и деление на многочлен f₃(x)=c₀+c₁x+…+c_{k bв0} -I- п.х +... + e_kx^k и деление на многочлен /s(*) =

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

На основе регистра с встроенными сумматорами может быть построена схема (рис. 1.6), реализующая одновременное умно­жение на многочлен f₂(x) =b₀+b₁x+b₂x²+…+b_kx^k и деление на многочлен f₃(x) =c₀+c₁x+c₂x²+…+c_kx^k.

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

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

f(x)=c₀+c₁x+c₂x²+…+c_n-1x^n-1. (2.1)

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

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

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

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

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

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

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

Свойство 2.2. Если некоторая комбинация (c₀c₁c₂…c_n-1) принадлежит какому-либо циклическому коду, то и комбинация, полученная из предыдущей в результате циклического сдвига ее элементов, например (с_n-1 c₀c₁ … c_n-2), также принадлежит этому циклическому коду.

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

x^{2^m-1}-1≡0[modP(x)].(2.3)

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

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

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

x*f(x) ≡ с_п-1 + с_ох+с₁х² +... +с_n-2х^п-1 (2.5)

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

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

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

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

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

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

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

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

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

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

Для φ (х) — 111,

для x³φ (х) —000111.

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

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

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

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

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

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

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

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

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

1100 10100100001

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

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

Дата добавления: 2015-07-16