Устройство для умножения в конечных полях

 

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

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

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

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

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

Недостаток данного устройства состоит в том, что умножение в конечных полях производится с существенными затратами времени и при фиксированной размерности поля.

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

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

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

Для достижения технического результата, заключающегося в расширении функциональных возможностей устройства умножения в конечных полях за счет осуществления умножения полиномов в поле, размерность которого может быть изменена, и повышения быстродействия предлагается в устройство умножения в конечных полях, содержащее блок умножения на старший разряд и "а_е 1" блоков вычисления полиномов, причем группа выходов блока умножения на старший разряд соединена с группой вторых информационных входов первого блока вычисления полинома, а группы вторых информационных входов i x (i ) блоков вычисления полиномов соединены соответственно с группами информационных входов (i 1)-х блоков вычисления полиномов, дополнительно введены блок сдвига сомножителя, блок задания обратных связей, блок формирования величины сдвига и блок сдвига произведения, причем входы группы первых информационных входов устройства соединены соответственно с информационными входами блока сдвига сомножителя (a_e k)-e (k ) входы группы вторых информационных входов устройства соединены с информационными входами (k)-х блоков вычисления полиномов, а а_е-й вход группы вторых информационных входов устройства соединен с информационным входом блока сдвига сомножителя, группа управляющих входов устройства соединена с группами входов блока задания обратных связей и блока формирования величины сдвига, группы выходов блока формирования величины сдвига соединена с группами управляющих входов блока сдвига сомножителя и блока сдвига произведения, группа выходов блока задания обратных связей соединена с группами управляющих входов (а_е 1) блоков вычисления полиномов, у которых группы первых информационных входов соединены с группой выходов блока сдвига сомножителя и группой информационных входов блока умножения на старший разряд, группа выходов (а_е 1)-го блока вычисления полинома соединена с группой информационных входов блока сдвига произведения, группа выходов которого соединена с группой выходов устройства для умножения в конечных полях.

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

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

Наличие признаков, отличающих заявляемое техническое решение от прототипа, а именно: блок сдвига сомножителей, блок задания обратных связей, блок формирования величины сдвига и блок сдвига произведений, причем входы группы первых информационных входов устройства соединены соответственно с информационными входами блока сдвига сомножителя, (a_e k)-e (k ) входы группы вторых информационных входов устройства соединены с информационными входами (k)-х блоков вычисления полиномов, а а_е-й вход группы вторых информационных входов устройства соединен с информационным входом блока сдвига сомножителя, группа управляющих входов устройства соединена с группами входов блока задания обратных связей и блока формирования величины сдвига, группы выходов блока формирования величины сдвига соединена с группами управляющих входов блока сдвига сомножителя и блока сдвига произведения, группа выходов блока задания обратных связей соединена с группами управляющих входов (а_е 1) блоков вычисления полиномов, у которых группы первых информационных входов соединены с группой выходов блока сдвига сомножителя и с группой информационных входов блока умножения на старший разряд, группа входов (а_е 1)-го блока вычисления полинома соединена с группой информационных входов блока сдвига произведения, группа выходов которого соединена с группой выходов устройства для умножения в конечных полях, обуславливает соответствие заявляемого технического решения критерию "новизна".

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

В поле Галуа GF(2) умножение двух полиномов p(x) p_a-1x^a-1+p_a-2x^a-2+.+p₁x+p₀, и g(x) g_a-1x^a-1+g_a-2x^a-2+.+g₁x+g₀,p_ig_i(0,1),i,j= возможно осуществить за один такт времени, если реализовать устройство, содержащее а ступеней, срабатывающих одновременно, причем на первой ступени будет получен результат S⁽¹⁾ g_a-1p(x). На второй ступени будет получен результат S⁽²⁾(x) (g_a-1x + g_a-2)p(x) + b_a-2F(x), где b_a-2 первый коэффициент частного от деления g(x)p(x)/F(x). На i-й ступени будет получен результат S⁽ⁱ⁾(x) (g_a-1x^a-1 + g_a-2x^a-2 + + g_a-i)P(x) + + (b_a-2x^a-2 + b_a-3x^a-3 + + b_a-i)F(x), где b_a-i (i 1)-й коэффициент частного. На а-й ступени будет получен результат умножения r(x) S^(a)(x) (g_a-1x^a-1 + g_a-2x^a-2 + + + g_o)p(x) + (b_a-2x^a-2 + b_a-3x^a-3 + + + b_o)F(x) g(x)p(x) + b(x)F(x).

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

На фиг. 1 приведена функциональная схема предлагаемого устройства; на фиг. 2 функциональная схема для примера реализации блока сдвига сомножителя; на фиг. 3 и 4 функциональные схемы соответственно блока умножения на старший разряд и блока вычисления полинома; на фиг. 5 и 6 функциональные схемы для примера реализации соответственно блока задания обратных связей и блока формирования величины сдвига; на фиг. 7 функциональная схема для примера реализации блока сдвига произведения; на фиг. 8-10 функциональная схема устройства для примера реализации умножения с заданной разрядностью поля.

Функциональная схема заявляемого устройства (см. фиг. 1) содержит 1₁-1- группу первых информационных входов; 2 блок сдвига сомножителя; 3₁-3 группу вторых информационных входов; 4 блок умножения на старший разряд; 5₁-5 блоки вычисления полиномов; 6₁-6_е группу управляющих входов; 7 блок задания обратных связей; 8 блок формирования величины сдвига; 9 блок сдвига произведения; 10₁ⁱ-10 (i ) (a_e 1) групп информационных выходов блоков вычисления полиномов, 5₁-5; 11₁-11 группу выходов устройства для умножения в конечных полях.

Функциональная схема для примера реализации блока сдвига сомножителя 2 (см. фиг. 2) содержит: 1₁-1₅ группу информационных входов; 12₁-12₁₂ группу элементов И; 13₁-13₃ группу управляющих входов; 14₁-14₄ группу элементов ИЛИ; 15₁-15₅ группу выходов блока 2.

Функциональная схема блока умножения на старший разряд 4 (см. фиг. 3) содержит: 3 информационный вход; 15₁-15 группу информационных входов; 16₁-16 группу элементов И; 10₁⁰-10 группу выходов блока 4.

Функциональная схема блока вычисления полинома 5_i (i ) (см. фиг. 4) содержит: 3_i информационный вход; 10₁^i-1-10 группу вторых информационных входов; 15₁-15 группу первых информационных входов; 18₁ⁱ-18 первую группу элементов И; 19₁ⁱ-19 первую группу сумматоров по модулю два; 20₁ⁱ-20 вторую группу сумматоров по модулю два; 21₁ⁱ-21 вторую группу элементов И; 10₁ⁱ-10 группу выходов блока 5.

Функциональная схема для примера реализации блока задания обратных связей 7 (см. фиг. 5) содержит: 6₁-6₇ группу управляющих входов; 23₁-23₄ группу элементов ИЛИ; 24 элемент НЕ; 22₁-22₅ группу выходов блока 7.

Функциональная схема для примера реализации блока формирования величины сдвига 8 (см. фиг. 6) содержит: 6₁-6₇ группу управляющих входов; 25₁-25₃ группу элементов ИЛИ; 13₁-13₃ группу выходов блока 8.

Функциональная схема для примера реализации блока сдвига произведения 9 (см. фиг. 7) содержит:10₁-10₅ группу информационных входов; 13₁-13₃ группу управляющих входов; 26₁-26₁₂ группу элементов И; 27₁-27₄ группу элементов ИЛИ; 11₁-11₅ группу выходов.

Функциональная схема (пример реализации) устройства для умножения в конечных полях (см. фиг. 8-10) содержит: 1₁-1₅ группу первых информационных входов; 2 блок сдвига сомножителя; 3₁-3₅ группу вторых информационных входов; 6₁-6₇ группу управляющих входов устройства; 7 блок задания размерности поля; 8 блок формирования величины сдвига; 9 блок сдвига произведения; 10₁ⁱ-10₅ⁱ -i-ю (i ) группу выходов блока вычисления полинома 5_i; 13₁-13₃ группу выходов блока формирования величины сдвига 8; 15₁-15₁₅ группу выходов блока сдвига сомножителя; 16₁-16₅ группу элементов И блока умножения на старший разряд; 18₁^j-18₅^j j-ю (j ) группу первых элементов И; 19₁ⁱ-19₅ⁱ i-ю (i ) группу первых сумматоров по модулю два; 20₁ⁱ-20₄ⁱ i-ю (i ) группу вторых сумматоров по модулю два; 21₁ⁱ-21₅ⁱ i-ю (i ) группу вторых элементов И; 11₁-11₅ группу информационных выходов устройства.

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

Входы 1₁-1 группы первых информационных входов соединены с соответствующими входами группы информационных входов блока сдвига сомножителя 2, а i-й вход группы вторых информационных входов 3₁-3соединен с информационным входом блока умножения на старший разряд 4, (а_е j)-й вход группы вторых информационных входов 3₁-3 соединен с информационным входом блока вычисления полинома 5_j, входы 6₁-6_е группы управляющих входов соединены соответственно с группой входов блока задания обратных связей 7 и блока формирования величины сдвига 8, группа выходов блока формирования величины сдвига 8 соединена соответственно с группами информационных входов блока сдвига сомножителя 2 и блока сдвига произведения 9, группа выходов блока сдвига сомножителя 2 соединена с группой информационных входов блока умножения на старший разряд 4 и с группами первых информационных входов блоков вычисления полиномов 5₁-5, входы группы вторых информационных входов блока вычисления полинома 5₁ соединены соответственно с выходами блока умножения на старший разряд 4, группа выходов блока задания обратных связей 7 соединена с группами управляющих входов блоков вычисления полиномов 5₁-5, группы информационных выходов 10₁ⁱ-10 i-х блоков вычисления полиномов 5_i (i ) соединены соответственно с группами вторых информационных входов (i + 1)-х блоков вычисления полиномов 5_i, а группа информационных выходов блока вычисления полинома 5 соединена с группой информационных входов блока сдвига произведения 9, выходы которого соединены соответственно с выходами 11₁-11 группы выходов устройства.

В блоке сдвига сомножителя 2 (пример реализации) вход 1₁ соединен с первыми входами элементов И 12₁, 12₆, 12₁₀ группы, вход 1₂ соединен с первыми входами элементов И 12₂, 12₇, 12₁₁ группы, вход 1₃ соединен с первыми входами элементов 12₃, 12₈, 12₁₂ группы, вход 1₄ соединен с первыми входами элементов И 12₄, 12₉ группы, вход 1₅ соединен с первым входом элемента И 12₅, вход 13₁ группы управляющих входов блока соединен с вторыми входами элементов И 12₁₀-12₁₂ группы, вход 13₂ группы управляющих входов блока соединен с вторыми входами элементов И 12₆-12₉группы, вход 13₃ группы управляющих входов блока соединен со вторыми входами элементов И 12₁-12₅ группы, выходы элементов И 12₂-12₅ соединены соответственно с первыми входами группы элементов ИЛИ 14₁-14₄, выходы элементов И 12₆-12₉ соединены соответственно с вторыми входами группы элементов ИЛИ 14₁-14₄, выходы элементов И 12₁₀-12₁₂ соединены соответственно с третьими входами элементов ИЛИ 14₂-14₄ группы, выход элемента И 12₁ и выходы группы элементов ИЛИ 14₁-14₄ соединены соответственно с выходами 15₁-15₅ группы выходов блока 2.

В блоке умножения на старший разряд 4 входы 15₁-15 группы информационных входов блока соединены соответственно с первыми входами группы элементов И 16₁-16, вторые входы которых объединены и соединены с информационным входом 3 блока, выходы группы элементов И 16₁-16 соединены соответственно с выходами 10₁⁰-10 группы выходов блока 4.

В каждом блоке вычисления полинома 5_i (i ) вход 15_j (j ) группы первых информационных входов соединен с первым входом элемента И 18ⁱ_j первой группы, вторые входы которых объединены и соединены с информационным входом 3_i блока, а выход элемента И 18_jⁱсоединен с первым входом соответствующего сумматора по модулю два 19_jⁱпервой группы, входы 10₁^i-1-10 группы вторых информационных входов соединены с вторыми входами соответствующих сумматоров по модулю два 20₁ⁱ-20 второй группы, первые входы элементов И 21₁ⁱ-21 второй группы объединены и соединены с входом 10 группы вторых информационных входов, входы 21₁-22 группы управляющих входов соединены соответственно с вторыми входами элементов И 21₁ⁱ-21 второй группы, выходы которых соединены соответственно со вторыми входами сумматоров по модулю два 19₁ⁱ-19 первой группы, а выходы сумматоров по модулю два 19₂ⁱ-19 первой группы соответственно соединены с первыми входами сумматоров по модулю два 20₁ⁱ-20 второй группы, выход сумматора по модулю два 19₁ⁱ первой группы и выходы сумматоров по модулю два 20₁ⁱ-20 второй группы соединены соответственно с выходами 10₁ⁱ-10 блока вычисления полинома 5_i.

В блоке задания обратных связей 7 (пример реализации) вход 6₁соединен с первым входом третьего элемента ИЛИ 23₃, вход 6₂ соединен с первым входом четвертого элемента ИЛИ 23₄, вход 6₃ соединен с первым входом второго элемента ИЛИ 23₂, вход 6₄ соединен с вторым входом второго элемента ИЛИ 23₂, с входом элемента НЕ 24 и с вторым входом четвертого элемента ИЛИ 23₄, вход 6₅ соединен с первым входом первого элемента ИЛИ 23₁, вход 6₆ соединен с вторым входом первого элемента ИЛИ 23₁, с вторым входом третьего элемента ИЛИ 23₃ и с третьим входом четвертого элемента ИЛИ 23₄, вход 6₇ соединен с третьим входом первого элемента ИЛИ 23₁, с третьим входом второго элемента ИЛИ 23₂ и с четвертым входом четвертого элемента ИЛИ 23₄, выходы элементов ИЛИ 23₁-23₄ и выход элемента НЕ 24 соответственно соединены с выходами 22₁-22₅ блока 7.

В блоке формирования величины сдвига 8 (пример реализации) входы 6₁и 6₂ соединены соответственно с первым и вторым входами первого элемента ИЛИ 25₁, входы 6₃ и 6₄ соответственно соединены с первым и вторым входами второго элемента ИЛИ 25₂, входы 6₅-6₇ соответственно соединены с первым, вторым и третьим входами третьего элемента ИЛИ 25₃, выход элемента ИЛИ 25_i (i ) соединен с выходом 13_i блока 8.

В блоке сдвига произведения 9 (пример реализации) вход 10₁ соединен с первым входом элемента И 26₁ группы, вход 10₂ соединен с первыми входами элементов И 26₂ и 26₆ группы, вход 10₃ соединен с первыми входами элементов И 26₃, 26₇ и 26₁₀ группы, вход 10₄ соединен с первыми входами элементов И 26₄, 26₈ и 26₁₁ группы, вход 10₅ соединен с первыми входами элементов И 26₅, 26₉ и 26₁₂ группы, вход 13₁ группы управляющих входов блока соединен с вторыми входами элементов И 26₁₀-26₁₂ группы, а 13₂ группы управляющих входов блока соединен с вторыми входами элементов И 26₆-26₉ группы, вход 13₃ группы управляющих входов блока соединен с вторыми входами элементов И 26₁-26₅ группы, выходы элементов И 26₁-26₄соединены соответственно с первыми входами группы элементов ИЛИ 27₁-27₄, выходы элементов И 26₆-26₉ соединены соответственно с вторыми входами группы элементов ИЛИ 27₁-27₄, выходы элементов И 26₁₀-26₁₂соединены соответственно с третьими входами элементов ИЛИ 27₁-27₃группы, выходы группы элементов ИЛИ 27₁-27₄ и выход элемента И 26 соединены соответственно с выходами 11₁-11₅ группы выходов устройства для умножения в конечных полях.

Работает устройство для умножения в конечных полях следующим образом.

При описании работы устройства в поле GF(2) (i ), определенном полиномом F_i(x) (i ) степени a_i с коэффициентом из поля GF(2)- т.е.

F_i(x) F_io+F_i1x+.+Fx, F_ijGF(2), i=,j=,F_io=1, каждый элемент поля представляют в виде полинома над GF(2), степень которого меньше а_i, т.е. вместо элементов p,q,rGF(2) рассматривают полиномы
p_i(x) p_ijx^j, p_ij GF(2), i=, j=,
q_i(x) q_ijx^j, q_ij GF(2), i=, j=,
r_i(x) r_ijx^j, r_ij GF(2), i=, j=.

Тогда умножение элементов GF(2^ai), т.е. p_iq_i r_i, выполняется по правилам умножения представляющих эти элементы полиномов по модулю F_i(x), т.е.

r_i(x) p_i(x)q_i(x) + b_i(x)F_i(x), (1) где b_i(x) полином степени меньшей, чем a_i 1.

В дальнейшем, для определенности, будем считать, что величины a_i, i упорядочены в порядке неубывания индексов, т.е.

a₁ a₂ a_e.

Для вычисления полинома r_e(x) можно использовать рекуррентное уравнение S_e^(k)(x) q_l1ae-k-1p_e(x) + S_e^(k-1)(x)x + b_l1aek-1F(x), k 1, 2, (2) где b_l1aek-1 q_l1ae-kp_l1ae-1 S_l1ae-1^(k-1),
S_e^(o)(x) q_lae-k^p_e(x)
Тогда
r_e(x) S_e^(ae-1)(x).

Полином r_i(x) в случае a_i < a_e можно вычислить, преобразовав соотношение (1) следующим образом
(x) q_i(x)(x)+b_i(x)(x),
где (x) r_i(x)x,(x) p_i(x)x,(x) F_i(x)x
Поскольку степень полинома (x) равна ае, то для вычисления (x) можно использовать рекурентное уравнение, аналогичное уравнению (2), т.е.

(x) q(x)+(x)x+b(x), k=1,2, (3)
где (x) q(x).

Тогда
(x) (x).

Для получения r_i(x) достаточно разделить (x) на х ^ае^-ai
На a_i, i входов группы первых информационных входов 1₁-1устройства в параллельном коде подаются коэффициенты полинома p_i(x). Аналогичным образом на a_i, i входов группы вторых информационных входов 3₁-3 устройства подаются коэффициенты полинома q_i(x).

С помощью информации, подаваемой с выходов блока формирования величины сдвига 8 на управляющие входы блока сдвига сомножителя 2, вектор коэффициентов полинома p_i(x) сдвигается на (a_e a_i) разрядов в сторону старших разрядов.

На входы блока умножения на старший разряд 4 подается с выходов блока сдвига сомножителя 2 вектор коэффициентов поли-нома (x) p_i(x)х ^ае^-ai и с а_е-го входа группы вторых информационных входов устройства коэффициент a_i,ae-1. На выходах блока умножения на старший разряд 4 будет сформирован результат вектор коэффициентов полинома
S_i^(o)(x) q(x).

На первые информационные входы блока вычисления полинома 5_k (k ) подается вектор коэффициентов полинома (x), на вторые информационные входы подается вектор коэффициентов полинома S_i^(k-1)(x), на информационный вход подается с (a_e k)-го входа группы вторых информационных входов 3₁-3 устройства коэффициент q_i, на управляющие входы подается код с выходов блока задания обратных связей 7. На выходах 10₁^k-10 блока вычисления полинома 5_k будет сформирован результат вектор коэффициентов полинома
(x) q(x)+(x)x+b(x).

Коэффициенты полинома q(x) (первого слагаемого) формируются с помощью первой группы элементов И 18₁^k-18 блока 5_k. Формирование коэффициентов полинома (x) обеспечивает блок задания обратных связей 7. Коэффициенты полинома b(x) (третьего слагаемого) формируются с помощью второй группы элементов И 21₁^k-21_ae^kблока 5_k. Суммирование всех трех слагаемых осуществляется с помощью первой группы 19₁^k-19_ae^k и второй группы 20₁^k-20 сумматоров по модулю два.

Коэффициенты полинома (x) S_i(^ae-1)(х) с выходов блока вычисления полинома 5 будут подаваться на информационные входы блока сдвига произведения 9. С помощью кода, подаваемого на управляющие входы блока сдвига произведения с выходов блока формирования величины сдвига 8, в блоке сдвига произведения 9 будет осуществлен сдвиг вектора коэффициентов полинома (x) на (a_e-a_i) разрядов в сторону младших разрядов. На выходах 11_e-11 блока сдвига произведения 9 будут получены коэффициенты искомого полинома r_i(x).

Рассмотрим работу устройства для случая, когда l 7,
F₁ (x) x³ + x + 1, F₂ (x) x³ + x² + 1,
F₃ (x)' x⁴ + x + 1,
F₄ (x) x⁴ + x³ + 1, F₅ (x) x⁵ + x² + 1,
F₆ (x) x⁵ + x⁴ + x³ + x² + 1,
F₇ (x) x⁵ + x⁴ + x² + x + 1.

При этом а₁ а₂ 3, а₃ а₄ 4, а₅ а₆ а₇ 5.

На основании значений коэффициентов полиномов (x) F_i(x)х ^ае^-ai (x) F₁(x)x² x⁵ + x³ + x², (x) F₂(x)x² x⁵+ x⁴ + x², (x) F₃(x)x x⁵ + x² + x, (x) F₄(x)x x⁵ + x⁴ + x, (x) F₅(x), (x) F₆(x), (x) F₇(x) составим матрицу синтеза блока задания обратных связей 7, в которой столбцы соответствуют входам, а строки выходам блока задания обратных связей 7.

Y₁ Y₂ Y₃ Y₄ Y₅ Y₆ Y₇
0 0 0 0 1 1 1 b₁
0 0 1 1 0 0 1 b₂
1 1 1 0 1 1 1 b₃
1 0 0 0 0 1 0 b₄
0 1 0 1 0 1 1 b₅
Тогда
b₁= Y₅Y₆Y₇, b₁= Y₃Y₄Y₇, b₃= b₄= Y₁Y₆, b₅= Y₂Y₄Y₆Y₇
Построенный в соответствии с полученными выражениями блока задания обратных связей 7 приведен на фиг. 5.

На основании значений a_i, i составим матрицу синтеза блока формирования величины сдвига 8, в которой столбцы соответствуют входам, а строки выходам блока формирования величины сдвига 8.

Y₁ Y₂ Y₃ Y₄ Y₅ Y₆ Y₇
1 1 0 0 0 0 0 C₁
0 0 1 1 0 0 0 C₂
0 0 0 0 1 1 1 C₃
Тогда
C₁ Y₁ V Y₂, C₂ Y₃ V Y₄, C₃ Y₅ V Y₆ V Y₇.

Построенный в соответствии с полученными выражениями блок формирования величины сдвига 8 приведен на фиг. 6.

Рассмотрим работу устройства при умножении элементов поля GF(2³), определяемого полиномом F₁(x) x³ + x + 1. В этом случае сигнал "1" поступает на управляющий вход устройства. Сигнал "1" появляется на выходах 22₃ и 22₄ блока задания обратных связей 7 (на остальных выходах блока задания обратных связей сигнал "0"), а также на выходе 13₁ блока формирования величины сдвига 8 (на остальных выходах блока формирования величины сдвига 8 сигнал "0").

Пусть p_i(x) x² + 1, q_i(x) x² + x. При этом на информационные входы 1₁-1₅ блока сдвига сомножителя 2 поступает двоичный код 00101, соответствующий коэффициентом полинома p_i(x). В результате на выходах 15₁-15₅ блока сдвига сомножителя 2 появляется код 10100, соответствующий коэффициентам полинома p_i(x). На входы 3₁-3₅ поступает двоичный код 00110, соответствующий коэффициентам полинома q_i(x).

На выходах 10₁⁰-10₅⁰ группы элементов И 16₁-16₅ блока умножения на старший разряд 4 появляются коэффициенты полинома (x) q(x)=0(x⁴+x²)=0, т.е. двоичный код 00000.

На выходах группы элементов И 18₁¹-18₅¹ (первых входах сумматоров по модулю два 19₁¹-19₅¹) блока вычисления полинома 5 появляются коэффициенты полинома q(x) 0 (x³ + x²) 0, т.е. двоичный код 00000. На выходах группы элементов И 21₁¹-21₅¹ (вторых входах сумматоров по модулю два 19₁¹-19₅¹) появляются коэффициенты полинома b(x) 0(x³ + x²) 0, т.е. двоичный код 00000. На выходах сумматоров по модулю два 19₁¹-19₅¹ появляется двоичный код 00000, который поступает (кроме младшего разряда коэффициента при х^о 0) на первые входы сумматоров по модулю два 20₁¹-20₄¹. На вторые входы сумматоров по модулю два 20₁¹-20₄¹ поступают коэффициенты полинома (x)x 0 * x 0, т. е. двоичный код 0000. В результате на выходах 10₁¹-10₅¹ блока вычисления полинома 5₁ появляются коэффициенты полинома (x) 0 + 0 0, т.е. двоичный код 00000.

На выходах группы элементов И 18₁²-18₅² (первых входах сумматоров по модулю два 19₁²-19₅²) блока вычисления полинома 5₂ появляются коэффициенты полинома q(x) 1(x⁴ + x²) x⁴ + x², т.е. двоичный код 10100. На выходах группы элементов И 21₁²-21₅² (вторых входах сумматоров по модулю два 19₁²-19₅²) появляются коэффициенты полинома b(x) 0(x³ + x²) 0, т.е. двоичный код 00000. На выходах сумматоров по модулю два 19₁²-19₅² появляется двоичный код 10100, который поступает (кроме младшего разряда) на первые входы сумматоров по модулю два 20₁²-20₄². На вторые входы сумматоров по модулю два 20₁²-20₄²поступают коэффициенты полинома (x)x 0 * x 0, т.е. двоичный код 0000. В результате на выходах 10₁²-10₅² блока вычисления полинома 5₂появляется вектор коэффициентов полинома S_i⁽²⁾(x) x⁴ + x² + 0 x⁴ + x², т.е. двоичный код 10100.

На выходах группы элементов И 18₁³-18₅³ (первых входах сумматоров по модулю два 19₁³-19₅³) блока вычисления полинома 5₃ появляются коэффициенты полинома q(x) 1(x⁴ + x²) x⁴ + x², т.е. двоичный код 10100. На выходах группы элементов И 21₁³-21₅³ (вторых входах сумматоров по модулю два 19₁³-19₅³) появляются коэффициенты полинома b(x) 1(x³ + x²) x³ + x², т. е. двоичный код 01100. На выходах сумматоров по модулю два 19₁³-19₅³ появляется двоичный код 11000, который поступает (кроме младшего разряда) на первые входы сумматоров по модулю два 20₁³-20₄³. На вторые входы сумматоров по модулю два 20₁³-20₄³поступают коэффициенты полинома (x)x (x⁴ + x²)x x⁵ + x³, т. е. двоичный код 0100. В результате на выходах 10₁³-10₅³ блока вычисления полинома 5 появляются коэффициенты полинома (x) (x⁴ + x³) + +x³= x⁴, т.е. двоичный код 10000.

На выходах группы элементов И 18₁⁴-18₅⁴ (первых входах сумматоров по модулю два 19₁⁴-19₅⁴) блока вычисления полинома 5₄ появляются коэффициенты полинома q(x) 0(x⁴ + x²) 0, т.е. двоичный код 00000. На выходах группы элементов И 21₁⁴-21₅⁴ (вторых входах сумматоров по модулю два 19₁⁴-19₅⁴) появляются коэффициенты полинома b(x) 1(x³ + x²) x³ + x², т.е. двоичный код 01100. На выходах сумматоров по модулю два 19₁⁴-19₅⁴ появляется двоичный код 01100, который поступает (кроме младшего разряда) на первые входы сумматоров по модулю два 20₁⁴-20₄⁴. На вторые входы сумматоров по модулю два 20₁⁴-20₄⁴ поступают коэффициенты полинома (x) x⁴ * x x⁵, т.е. двоичный код 0000. В результате на выходах 10₁⁴-10₅⁴ блока вычисления полинома 5₄появляются коэффициенты полинома (x) (x) x³+x²+0 x³+x², т.е. двоичный код 01100.

На выходах 11₁-11₅ блока сдвига произведения 9 появляются коэффициенты полинома r_i(x) (x)/х ^ае^-ai (x³ + x²)/x² x + 1, т.е. двоичный код 00011.

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

Если в известном устройстве на умножение тратится время
T₁ t_n at, где t_o тактовая частота, t_n время подготовки к процедуре умножения то в предлагаемом устройстве на умножение будет затрачено время
T₂ t_n + t_o.

Эффективность устройства определится формулой
Э Т₁/Т₂.

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

УСТРОЙСТВО ДЛЯ УМНОЖЕНИЯ В КОНЕЧНЫХ ПОЛЯХ, содержащее блок умножения на старший разряд и a_l 1 блоков вычисления полиномов (где a_l - максимальная разрядность сомножителей, l число различных полиномов, определяющих конечное поле), причем выходы блока умножения на старший разряд соединены с информационными входами первой группы первого блока вычисления полиномов, информационные входы первой группы блока вычисления полиномов соединены с информационными выходами (i 1)-го блока вычисления полиномов, отличающееся тем, что в него введены блок сдвига сомножителя, блок задания обратных связей, блок формирования величины сдвига и блок сдвига произведения, причем информационные входы первой группы устройства соединены с соответствующими информационными входами блока сдвига сомножителя, информационный вход второй группы устройства соединен с информационным входом (a_l i)-го блока вычисления полиномов, а a_l-й информационный вход второй группы устройства соединен с информационным входом блока умножения на старший разряд, управляющие входы устройства соединены с соответствующими входами блока задания обратных связей и блока формирования величины сдвига, выходы которого соединены с управляющими входами блока сдвига сомножителя и блока сдвига произведения, выходы блока задания обратных связей соединены с управляющими входами a_l 1 блоков вычисления полиномов, информационные входы второй группы которых соединены с выходами блока сдвига сомножителя и группой информационных входов блока умножения на старший разряд, выходы (a_l 1)-го блока вычисления полиномов соединены с информационными входами блока сдвига произведения, выходы которого соединены с выходами устройства.

РИСУНКИ

Рисунок 1, Рисунок 2, Рисунок 3, Рисунок 4, Рисунок 5, Рисунок 6, Рисунок 7, Рисунок 8, Рисунок 9, Рисунок 10