19545

Быстрые схемы дискретного преобразования Фурье

Лекция

Коммуникация, связь, радиоэлектроника и цифровые приборы

2 Лекция 14. Быстрые схемы дискретного преобразования Фурье. Обычные формулы для вычисления ДПФ требуют большого количества умножений: где число точек в ДПФ. Существуют приемы позволяющие уменьшить это количество. Они называются быстрыми схемами БПФ. Пр

Русский

2013-07-12

515.42 KB

4 чел.

2

Лекция 14. Быстрые схемы дискретного преобразования Фурье.

Обычные формулы для вычисления ДПФ требуют большого количества умножений: , где  - число точек в ДПФ. Существуют приемы, позволяющие уменьшить это количество. Они называются быстрыми схемами (БПФ). Простейшая относится к случаю .

Случай

 Любое число в интервале  однозначно представляется двоичным вектором длины . Если последовательность  задана, то положим

. В дальнейшем, что упростить изложение, введем обозначение , откуда . Имеем

. Основное замечание заключается в следующем: суммирование по индексу  равносильно суммированию по всем двоичным индексам .

, каждый из которых принимает два значения.

Для числа  существует аналогичное двоичное представление:. Рассмотрим самую внутреннюю сумму. . Нетрудно видеть, что это некоторая функция . Следующая сумма принимает вид . Этот процесс продолжается. Окончательно имеем . Количество сумм равняется , в каждой из которых лишь одно умножение. Для вычисления всех коэффициентов нужно  умножений. Другое преимущество этой схемы - экономный расход оперативной памяти.

Случай   с взаимно простыми сомножителями

Рассмотрим другой крайний случай, когда  и . В этом случае существуют целые , для которых . Отсюда следует, что

   (1)

При этом можно считать выполненными неравенства

.(2)

Если такое неравенство для , например, не имеет места, можно разделить на . Для

любого целого  из (1) вытекает

. При ограничениях типа (2)  находятся однозначно. Имеем

. Числа  - взаимно простые. Следовательно имеем для любого целого

. Теперь . Раскрывая скобки и отбрасывая члены кратные , получим показатель вида .

Из равенства  следует, что , поэтому весь показатель сравним с . Это означает, что . Вводя обозначения , окончательно получим  =

. Это означает, что преобразование Фурье для  точек свелось к последовательному выполнению преобразования Фурье по  точкам, а затем - по  точкам результатов предыдущего преобразования. При этом потребуется не более, чем  умножений. По сравнению с  выигрыш небольшой. Если же для какого-либо из промежуточных случаев есть своя быстрая схема, выигрыш может получиться значительным.


 

А также другие работы, которые могут Вас заинтересовать

33652. Режимы работы IPSec 30 KB
  Каждое из них определяет различные параметры IPSecсоединения такие как алгоритмы шифрования и аутентификации которые будут использованы при обмене информацией между системами сеансовые ключи шифрования и т. Алгоритмы шифрования IPSec это набор протоколов в которых используются алгоритмы аутентификации и шифрования. На сегодня определены два алгоритма аутентификации и семь алгоритмов шифрования. Алгоритм шифрования DES Dt Encryption Stndrd с явно заданным вектором инициализации Initiliztion Vector IV применяют в протоколе ESP по...
33653. Виртуальные частные сети 30.5 KB
  Виртуальные частные сети Виртуальная частная сеть VPN это технология обеспечивающая безопасную связь по открытой общей сети. Истинная частная сеть принадлежность оборудования сети предприятия и гарантия конфиденциальности информации передаваемой по этой сети. Такие сети не очень распространены. Корпоративные данные практически не доступны для абонентов не являющихся пользователями корпоративной сети или сотрудниками провайдера.
33654. Типы VPN-устройств 31 KB
  Типы VPNустройств Существует несколько основных типов VPNустройств: отдельное аппаратное устройство VPN на основе специализированной ОС реального времени имеющее 2 или более сетевых интерфейса и аппаратную криптографическую поддержку так называемый черный ящик; отдельное программное решение которое дополняет стандартную операционную систему функциями VPN; расширение межсетевого экрана за счет дополнительных функций защищенного канала; средства VPN встроенные в маршрутизатор. Устройства VPN могут играть роль шлюза или клиента...
33655. Атаки на протокол TCP и его защита 34 KB
  Если очередь входных соединений заполнена а система получает SYNпакет приглашающий к установке соединения он будет проигнорирован. ddress Spoofing Для формирования ложного TCPпакета и последующего перехвата установленного между доверенными узлами виртуального соединения атакующему необходимо знать текущие значения идентификаторов для данного соединения Seq и ck. В этом случае можно попытаться получить эти числа путём математического предсказания начального значения идентификатора TCPсоединения экстраполяцией его предыдущих значений...
33656. Метод Эль-Гамаля 103 KB
  1 WP1 = 1 mod P Затем генерируется секретный ключ Ха из диапазона 1 X P1. Затем вычисляется открытый ключ Y как степень: Y = WX mod P. Затем выбрав число K мы вычисляем число R по формуле : R = YK mod P. Для ее формирования используется операция побитового сложения по модулю 2: C1 = WK mod P 5.
33657. БЛОЧНОЕ КОДИРОВАНИЕ (АЛГОРИТМ ГОСТ) 252.5 KB
  БЛОЧНОЕ КОДИРОВАНИЕ АЛГОРИТМ ГОСТ В нашей стране установлен единый алгоритм криптографического представления данных для систем обработки информации в сетях ЭВМ отдельных вычислительных комплексов и ЭВМ который определяется ГОСТ 2814789. Этот алгоритм криптографического преобразования данных представляет собой 64битовый блочный алгоритм с 256битовым ключом предназначен для аппаратной и программной реализации удовлетворяет криптографическим требованиям и не накладывает ограничений на степень секретности защищаемой информации. В любом...
33658. БЛОЧНОЕ КОДИРОВАНИЕ (АЛГОРИТМ DES) 44 KB
  БЛОЧНОЕ КОДИРОВАНИЕ АЛГОРИТМ DES Алгоритм DES представляет собой блочный шифр предназначенный для шифрования данных 64битовыми блоками. DES относится к симметричным алгоритмам т. Фундаментальным строительным блоком Des является применение к тексту единичной комбинации этих методов подстановка а за ней перестановка зависящей от ключа. DES включает 16 раундов одна и та же комбинация методов применяется к открытому тексту 16 раз DES оперирует 64битными блоками открытого текста .
33659. Протокол SSL 46.5 KB
  Протокол SSL Протокол SSL Secure Socket Lyer предназначен для защиты данных передаваемых между приложениями клиентом и сервером. SSL работает поверх транспортного протокола предполагающего установление соединения TCP. SSL прозрачен для служб прикладного уровня таких как HTTP и FTP. Протокол SSL базируется на следующих принципах: Защищённый канал передачи данных.
33660. СМЕШАННЫЙ ШИФР (АЛГОРИТМ ГОСТ + ЭЛЬ ГАМАЛЯ) 32 KB
  К тому же ни одна из реализаций систем с открытым ключом предложенных до сих пор не может конкурировать в скорости с системами с секретным ключом такими например как DES или ГОСТ. Когда необходимо передать большое количество информации может оказаться что использование криптоалгоритмов с открытым ключом было бы слишком медленным тогда как использование симметричных алгоритмов было бы либо невозможным изза отсутствия разделенного секретного ключа либо не отвечающим требованиям секретности. Гибридная смешанная криптосистема...