Наброски и зарисовки растений, плодов, цветов: Освоить конструктивное построение структуры дерева через зарисовки отдельных деревьев, группы деревьев...
Поперечные профили набережных и береговой полосы: На городских территориях берегоукрепление проектируют с учетом технических и экономических требований, но особое значение придают эстетическим...
Топ:
Когда производится ограждение поезда, остановившегося на перегоне: Во всех случаях немедленно должно быть ограждено место препятствия для движения поездов на смежном пути двухпутного...
Характеристика АТП и сварочно-жестяницкого участка: Транспорт в настоящее время является одной из важнейших отраслей народного...
Эволюция кровеносной системы позвоночных животных: Биологическая эволюция – необратимый процесс исторического развития живой природы...
Интересное:
Распространение рака на другие отдаленные от желудка органы: Характерных симптомов рака желудка не существует. Выраженные симптомы появляются, когда опухоль...
Мероприятия для защиты от морозного пучения грунтов: Инженерная защита от морозного (криогенного) пучения грунтов необходима для легких малоэтажных зданий и других сооружений...
Лечение прогрессирующих форм рака: Одним из наиболее важных достижений экспериментальной химиотерапии опухолей, начатой в 60-х и реализованной в 70-х годах, является...
Дисциплины:
2017-11-17 | 352 |
5.00
из
|
Заказать работу |
|
|
Пусть –произведение целых положительных попарно взаимно-простых положительных чисел, пусть и пусть удовлетворяют равенству , тогда единственным решением системы сравнений
будет
Эта теорема позволяет каждое число n,0≤n<Mоднозначно задать системой остатков по модулям , i=1,k.
4.3. Трехмерное преобразование Фурье в поле
Рассмотрим ДПФ длины N=255, ядром которого является примитивный элемент поля .
(1) |
, ,
(2) |
Произвольный ненулевой элемент поля ) задается как степень примитивного элемента поля: = ,
Согласно (2)
(3) |
, = , = = ,
Где приняты обозначения: = , = , =
Более того, в силу попарной взаимной простоты модулей , если i (, , ) и j (, , ), то ij (, , ). Таким образом, формулу (4.1) определяющую ДПФ, можно переписать в виде:
(4) |
, = , =
Это сразу подсказывает следующий алгоритм вычисления вектора по вектору . Сначала разбиваем координаты вектора на тройки чисел (прификсированных и ) и к каждой из них применяем 3-точечное преобразование с ядром = ; это дает набор из 255 величин
(5) |
, = , = .
Затем к этому вектору длины 255 применяется 5-точечное ДПФ с ядром = по правилу: координаты вектора группируются по 5 чисел (по фиксированным и ) и для каждой такой совокупности вычисляется 5-мерный вектор ,
(6) |
, = , = .
Наконец, к вектору длины 255 применяется 17-точечное ДПФ с ядром = , приводящее к искомому 255-мерному вектору :
(7) |
, = , = .
(8) |
(9) |
|
Экспериментально установлено, что переход от одномерной структуры к трехмерной, уменьшает время, требуемое на вычисление ДПФ примерно в 10 раз.
Таким образом, переход от ДПФ длины 255 к ДПФ длин 3, 5 и 17, каждое из которых вычисляется 255 раз в цикле, очень существенно понижает вычислительную сложность алгоритма.
Следующий наш шаг – полностью избавиться от ДПФ внутри циклов, заменив их на БПФ (быстрое преобразование Фурье) длин 3, 5 и 17, которые основаны как на свойствах поля , так и на свойствах алгоритмов быстрого умножения многочленов, заданных над конечным полем.
4.4 Быстрое преобразование Фурье БПФ длины 3
3-точечное ДПФ с ядромβдля вектора задается формулой
)=
Так как ядро β удовлетворяет тождеству 1+ , то легко проверить непосредственно, что числа могут быть вычислены по правилу:
, которое содержит только одно умножение и 5 сложений (вместо 4 умножений и 6 сложений). Если , .
4.5. Быстрое преобразование Фурье длины 5
5-точечное ДПФ с ядром задается равенством
,
непосредственное вычисление по которому требует 16 умножений и 20 сложений. Использование только тождества на ядре (которое в данном случае имеет вид 1+ + + ) дает 9 умножений и 21 сложение. Это достигается, например, следующим образом:
,
Аналогично,
,
,
и, наконец,
Дальнейшего уменьшения числа умножений можно добиться за счет перехода к циркулянту и использования полиномиальной свертки (ПС). Приведем необходимые сведения:
Утверждение 4.5.1. Два двучлена и , , , , , можно перемножить, выполняя не более трех умножений чисел в поле F.
Действительно, ()()≜ , где , и
Если умножение происходит вполе F , то , где ,
Следствие 4.5.1. Два многочлена степени m над полем F можно перемножить, выполняя не более умножений чисел в поле F.
Например, для m=3 (с учетом, что charGF()=2) имеем:
|
(10) |
≜
где t≜ (так что при вычислении по модулю многочлена надо делать редукцию по модулю ); согласно утверждению 4.5.1:
≜
≜
≜
Для вычисления , , опять воспользуемся утверждением 4.5.1. Имеем
(11) |
Таким образом, для вычисления коэффициентов многочлена необходимо только 9 (вместо 16) умножений. Точные формулы для коэффициентов многочлена (при ) имеют вид:
(12) |
Для коэффициентов при , согласно (10)-(12)
,
,
,
,
(13) |
,
,
Если произведение вычисляется в кольце F (так что ), то формулы (10)-(12) принимают вид:
≜ , (10а)
(11a) |
, ≜
,
.
Вычисление вектора где а – циркулянт, первая строка которого задается вектором , равносильно вычислению в F произведения , где и .
Подчеркнем, что преобразуемая последовательность , за исключением первого элемента, дает реверсивный порядок коэффициентов многочлена при координате стоит коэффициент .
Утверждение 4.5.2. Для ДПФ простой длины n всегда существует такая перестановка строк и столбцов матрицы Фурье, что она может быть превращена в окаймленный циркулянт.
Этот результат принадлежит Рейдеру. Мы подробно проиллюстрируем соответствующий алгоритм в следующем пункте, посвященному БПФ длины 17, а сейчас вернемся к БПФ длины 5.
Прежде всегоизбавимся от единичного окаймления матрицы Фурье:
= )
В столбцах и строках матрицы, стоящей в правой части равенства выполним перестановку .Если выполним такую же перестановку координат у векторов d и его спектра А, получаем
) (14)
Циркулярная матрица для БПФ длины 5 получается, если задать нумерацию ненулевого элемента поля GF (5) с образующей 3: 1 (mod5), 3 3 (mod5), 4 (mod5), 2 (mod5): .
Этим задача свелась, согласно утверждения 4.5.2, к вычислению многочлена c (x)=d(x)w(x)mod(x -1), где d(x)= или, иначе, циклической свертки с=с
Для вычисления этой циклической свертки длины 4, перепишем формулы (13) в более удобном для организации экономного вычисления виде:
, ;
(15)
Этот алгоритм содержит 9 умножений и 17 сложений. Но если появляются какие-то условия на коэффициенты или ,то число вычислений уменьшается. Например, если =0 или 1, то число умножений равно только 5. В нашем случае и так как - ядро БПФ длины 5, то =1. Учитывая это, из формул (13) – (14) окончательно приходим к следующему алгоритму:
|
, , , , , , , , , , , . (16)
Так что алгоритм БПФ длины 5 в поле в нашем случае содержит 5 умножений и 11сложений.
4.6 Быстрое преобразование Фурье длины 17
17-точечное ДПФ с ядром задается равенством
(17)
В = .
Для уменьшения числа умножений, как и для 5-точечного ДПФ, воспользуемся переходом к циклической свертке с последующей редукцией по следствию из утверждения 4.5.1. Сначала воспользуемся алгоритмом Рейдерадля перехода к циркулянту. Так как 5 является примитивным элементом поля GF(17), то имеем:
i | 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
N=5 | 5 8 6 13 14 2 10 16 12 9 11 4 3 15 7 1 |
Таким образом, без учета в нумерации одиночного окаймления, к циклической свертке приводит, например, такая перестановка строки столбцов матрицы Фурье в (17) (соответствующих координат преобразуемого вектора а и спектра А), которая дается второй строкой этой таблицы: единичное окаймление остается на месте, а первая строка циркулянта соответственно имеет вид:
получаем,
где , – вектор, полученный из спектра А указанной перестановкой координат, а - вектор столбец, определяемый вторым равенством в (18).
Согласно утверждению 4.5.2, задача вычисления (18) эквивалентна задаче вычисления циклической свертки
(19)
Вычислять свертку (19) будем следующим образом. Пусть (так что ) и пусть
Так что
,
,
Сначала будем полагать переменную х параметром и найдем циклическую свертку по модулю . Обозначая , согласно равенствам (15) имеем:
(20)
В поле для элемента выполняется тождества:
; ;
(21)
Эти тождества позволяют упростить вычисления величин, входящих в (20). Например,
Aлгоритм вычисления R(x)=r(x) для произвольного многочлена содержит 4 умножения и 12 сложений. А именно, воспользуемся равенством (12) и учтем, что в поле согласно второму из тождеств в (20) выполняется равенство ,char =2. Имеем:
При табличной реализации умножения необходимо иметь только один массив длины 256 произведений всех элементов поля на элемент . Алгоритм:
(22)
Для остальных 5 умножений вида R(x)=r(x)b(x) число умножений не уменьшается, равно 9, и алгоритм, согласно (12), можно записать в виде:
|
Алгоритм: , , , , , ,
, , , , , , (23) , , , , , , , , .
Так как суммы коэффициентов , естественно, вычисляются заранее и вводятся в алгоритм фиксированными константами, то всего имеем 9 умножений и 17 сложений. Для входящих в (20) коэффициентов, величины
соответственно равны:
Полное число сложений и умножений для этой реализации равно соответственно 129 и 61. Для полного БПФ по длине 255 имеем 1935 сложений и 1255 умножений.
|
|
Индивидуальные и групповые автопоилки: для животных. Схемы и конструкции...
Особенности сооружения опор в сложных условиях: Сооружение ВЛ в районах с суровыми климатическими и тяжелыми геологическими условиями...
Своеобразие русской архитектуры: Основной материал – дерево – быстрота постройки, но недолговечность и необходимость деления...
Состав сооружений: решетки и песколовки: Решетки – это первое устройство в схеме очистных сооружений. Они представляют...
© cyberpedia.su 2017-2024 - Не является автором материалов. Исключительное право сохранено за автором текста.
Если вы не хотите, чтобы данный материал был у нас на сайте, перейдите по ссылке: Нарушение авторских прав. Мы поможем в написании вашей работы!