Портал аспирантов
 

Вернуться   Портал аспирантов > Общие > Дискуссионный зал > Физико-математические науки

Ответ
 
Опции темы
Старый 14.06.2011, 14:24   #1
Paul Kellerman
Gold Member
 
Регистрация: 25.06.2005
Адрес: F000:FFF0
Сообщений: 1,804
По умолчанию Вопрос по разновидностям сверток многочленов

Пусть над простым полем Галуа GF(p) заданы два многочлена a(x) и b(x),
и определены операции сложения многолченов, умножения многочленов,
и вычисления остатка одного многочлена по модулю другого многочлена.

Тогда, насколько я помню в общем виде свертка многочленов выглядит:

c(x) = (a(x)*b(x)) mod g(x)

Если deg(g(x)) > deg(a(x)) + deg(b(x)), то имеем линейную свертку, кото-
рая по сути совпадает с произведением многочленов a(x) и b(x), если же
deg(g(x)) <= deg(a(x)) + deg(b(x)), то в случае если g(x) неприводим над
полем GF(p) то имеем полевую свертку, а если g(x) = x^r - 1, то свертка
называется циклической. Однако я нигде не нашел комментариев по по-
воду остальных случаев, когда g(x) не является неприводимым, но в то
же время он не выглядит как x^r - 1. Например, как называется свертка
вида (a(x)*b(x)) mod (x^r), которая легко получается путем вычисления
произведения многочленов a(x) и b(x) с последующим "отбрасыванием"
слагаемых со степенями выше r ? Усеченной сверткой или как-то еще?
Paul Kellerman вне форума   Ответить с цитированием
Реклама
Старый 01.07.2011, 09:38   #2
Paul Kellerman
Gold Member
 
Регистрация: 25.06.2005
Адрес: F000:FFF0
Сообщений: 1,804
По умолчанию

Итерационно-сдвиговая схема вычисления общего случая свертки многочленов
a(x) и b(x) степени <= m - 1 по модулю нормированного многочлена степени m:
g(x) = x^m + g[m-1]*x^(m - 1) + ... + g[0], заданных над простым полем GF(p).

При g(x) = x^m - 1, имеем циклическую свертку.
При g(x) = x^m, имеем усеченную линейную свертку.
При g(x) неприводимом над GF(p), имеем полевую свертку.

Буду рад комментариям, дополнениям, замечаниям.
Вложения
Тип файла: pdf 4bit-Convolution-LFSR-math.pdf (190.6 Кб, 3 просмотров)

Последний раз редактировалось Paul Kellerman; 01.07.2011 в 10:19.
Paul Kellerman вне форума   Ответить с цитированием
Старый 01.07.2011, 09:43   #3
Paul Kellerman
Gold Member
 
Регистрация: 25.06.2005
Адрес: F000:FFF0
Сообщений: 1,804
По умолчанию

Аппаратная реализация (электрическая модель в Multisim 10) итерационно-сдвиговой
схемы вычисления свертки для четырехразрядного (m = 4) двоичного случая (p = 2).
Сдвиговый регистр на базе D-триггеров расположен в верхней части схемы. В нижней
части расположены индикаторы (UL1, UL2, UL3) для отображения a(x), b(x) и свертки
c(x)=a(x)*b(x) mod g(x) в эквиваленте четырехразрядного шестнадцатеричного числа,
DIP-переключатели J2, J3, J4 для задания коэффициентов многочленов a(x), b(x), g(x),
а также схема для формирования 4-х тактовых импульсов по линии CLK и последовате-
льной подачи коэффициентов b[4 - s] многочлена b[x] по линии BMS, s - номер такта.

При g = (0001), g(x) = x^4 + 1, имеем циклическую свертку.
При g = (0000), g(x) = x^4, имеем усеченную линейную свертку.
При g = (0011), g(x) = x^4 + x + 1 неприводим над GF(2), имеем полевую свертку.

Буду рад комментариям, дополнениям, замечаниям.
Вложения
Тип файла: pdf 4bit-Convolution-LFSR-circuit.pdf (235.0 Кб, 3 просмотров)

Последний раз редактировалось Paul Kellerman; 01.07.2011 в 10:15.
Paul Kellerman вне форума   Ответить с цитированием
Ответ

Опции темы

Ваши права в разделе
Вы не можете создавать новые темы
Вы не можете отвечать в темах
Вы не можете прикреплять вложения
Вы не можете редактировать свои сообщения

BB коды Вкл.
Смайлы Вкл.
[IMG] код Вкл.
HTML код Выкл.



Текущее время: 23:32. Часовой пояс GMT +3.


Powered by vBulletin® Version 3.8.8
Copyright ©2000 - 2024, vBulletin Solutions, Inc. Перевод: zCarot
© 2001—2024, «Аспирантура. Портал аспирантов»
Рейтинг@Mail.ru