Аннотация научной статьи по математике, автор научной работы — Сергеев В. В., Усачев А. В.
Предложен новый алгоритм быстрого преобразования Хартли, при разработке которого использованы результаты, полученные Капориным для вычисления дискретного преобразования Фурье. Показано, что этот алгоритм требует наименьшего количества вещественных умножений и сложений по сравнению с известными алгоритмами.
Похожие темы научных работ по математике , автор научной работы — Сергеев В. В., Усачев А. В.
Текст научной работы на тему «Новый алгоритм быстрого преобразования Хартли»
В.В. Сергеев, А.В. Усачев
НОВЫЙ АЛГОРИТМ БЫСТРОГО ПРЕОБРАЗОВАНИЯ ХАРТЛИ
Удобным аппаратом цифровой обработки сигналов является дискретное преобразование Фурье (ДПФ). Широкое применение ДПФ объясняется наличием эффективных алгоритмов его вычисления.
Одним из наиболее быстрых алгоритмов вычисления ДПФ длиной 2^ (I i 2 ■ целое) был предложен И.Е. Капориным [1]. Этот алгоритм основывается на сведении преобразования Фурье L-точечной комплексной последовательности к вычислению четырех вещественных преобразований (двух косинусных и двух синусных) длиной порядка L/2. В обозначениях принятых в [1] преобразование по косинусам последовательности имеет вид: г
Ф.(Ю [а] = 2 а. eos , 0 i Не можете найти то, что вам нужно? Попробуйте сервис подбора литературы.
COS —jjj— + sin ¿all], о 2 — целое,
bj = aj + а 2 N — j ‘ Cj = aj — а 2 N — j ‘ 1 S j S N — 1; (4)
Разложив правую часть выражения (3) на две суммы по косинусам и синусам и учитывая, что
cos 2n(N-j)k = cos 2т^к . sin 2n [.] — Ф [a] — i Не можете найти то, что вам нужно? Попробуйте сервис подбора литературы.
Рубрика: 2. Электроника, радиотехника и связь
Дата публикации: 30.06.2014
Статья просмотрена: 1268 раз
Библиографическое описание:
Аверченко А. П., Воропаев В. К., Женатов Б. Д. Преобразование Фурье и преобразование Хартли [Текст] // Технические науки в России и за рубежом: материалы III Междунар. науч. конф. (г. Москва, июль 2014 г.). — М.: Буки-Веди, 2014. С. 22-24. URL https://moluch.ru/conf/tech/archive/90/5967/ (дата обращения: 18.11.2019).
В статье рассматриваются преобразования Хартли и Фурье, рассматриваются их зависимости. Рассмотрены сходства и отличия преобразования Хартли и Фурье.
Ключевые слова:преобразование Хартли, преобразование Фурье, cas функция, действительная и мнимая часть.
Ральф Винтон ЛайонХартли, раскрыл вещественные преобразования тесно связанные с преобразованием Фурье в 1942 году. Кроме того, используя собственные свойства, преобразование введенное Хартли позволяет произвести расчёты косвенных вычислений спектра мощности Фурье данной функции, пользуясь только арифметикой. В последние десятилетия были предложены некоторые новые дискретные вещественные ортогональные преобразования, которые Хартли, связал с другим известным комплексом.
В 1942 году было опубликована статья об интегральных преобразованиях — прямом и обратном, использующие введенную Хартли функцию 
. Преобразование Хартли позволяет разложить функцию на два синусоидальных компонента как набора представленных с точки зрения положительных и отрицательных составляющих отличающихся простотой от сложных геометрических прогрессий exp(jɷx), используемых в классическом анализе Фурье.
В отличие от преобразования Фурье, преобразование Хартли трансформирует одни вещественные функции в другие вещественные же функции не используя мнимую часть функции. Дискретная версия преобразования Хартли, была введена R. N.Bracewell в 1983 году [1, с.114].
Преобразование Хартли функции f(t) определяется:
Где ɷ может быть угловой частотой и 
это косинус и синус или ядро Хартли. С инженерной точки зрения, это преобразование принимает сигнал (функцию) из временной области в спектральной области Хартли.
Преобразование Хартли (как преобразование Фурье) имеют различные мелкие детали являющиеся предметом конвекции и могут быть изменены без изменения основных свойств.
— Прямое преобразование.
— Обратное преобразование.
1) Вместо того что бы использовать одно и тоже преобразование для прямого и обратного, можно удалить 
из прямого преобразования и использовать 
для обратного преобразования и вынести такой же коэффициент из прямого преобразования.
2) Можно также использовать 
вместо 
(т. е. частота вместо угловой частоты), в этом случае коэффициент полностью опустится.
3) Можно использовать разность cosɵ — sinɵ вместо cosɵ+ sinɵ [2, с.15]
Связь с преобразованием Фурье.
Преобразование Хартли отличается от классического преобразования Фурье F
выборе ядра. В преобразование Фурье, экспоненциальное ядро: 
где i — это мнимая единица.
Эти два преобразования тесно связаны между собой, однако преобразование Фурье (при условие, что преобразование использует коэффициент нормализации конвенции) может быть вычислено из преобразования Хартли:
То есть, действительная и мнимая часть преобразования Фурье задаётся чётными и нечётными частями преобразования Хартли. И наоборот, для вещественной функции F(T), преобразования Хартли задаётся от преобразования Фурье, действительной и мнимой частью.
Где 
и 
обозначают действительную и мнимую часть комплексного преобразования Фурье.
Пример преобразования Хартли и Фурье.
T=4,t=0.01..T, s(t)=exp [-5(
) 2 ],
cas(x)=cos(x)+sin(x) 
Функции Хартли.
Sh(f)=
F=1.5 f=-F,_f+0.02.. F
Сопоставление составляющих спектра Хартли с действительной и мнимой частью спектра Фурье [3].
Преобразование Хартли — это линейный оператор (преобразование Фурье также относится к линейным интегральным операциям) Из симметричности и обратных свойств, преобразование является унитарным оператором (в самом деле, ортогональном).
Существует также аналог теоремы свёртки для преобразования Хартли. Если две функции х(t) и y(t) имеют преобразование Хартли X(
) и 
то их свёртки 
есть преобразование Хартли:
По аналогии с преобразованием Фурье, преобразование Хартли чётной/нечётной функции чётные/нечётные.
Свойства cas функции вытекают непосредственно из тригонометрии, и его определение как фазовый сдвиг тригонометрических функции
то:
и её производная равна:
Преобразование Хартли может использоваться в качестве альтернативы преобразования Фурье при учете вышеописанных свойств.
1. Злобин С.Л, Стальной А. Я. «Двумерное быстрое преобразование Хартли в цифровой обработке изображений». Доклады 6–ой Международной конференции «Цифровая обработка сигналов и её применение». Том 2, стр. 114–116. Труды РНТОРЭС им. А. С. Попова. Москва, Россия, 2004 г.
2. Брейсуэлл Р. Преобразование Хартли. Теория и приложения. — М.: Мир, 1990
3. Bracewell, Ronald.N. (1986). The Hartley Transform. Oxford University Press. ISBN 9780195039696
4. Poularikas A. D. «The Hartley Transform» The Handbook of Formulas and Tables for Signal Processing. Ed. Alexander D. Poularikas Boca Raton: CRC Press LLC,1999
На симпозиуме по дискретным алгоритмам ACM на этой неделе группа исследователей из MIT представила новый алгоритм быстрого преобразования Фурье sFFT (Sparse Fast Fourier Transform), который на некоторых задачах может быть в десятки или сотни раз быстрее классического БПФ.
Преобразование Фурье предполагает получение коэффициентов («амплитуд») при разложении исходной функции на элементарные составляющие — гармонические колебания с разными частотами. Быстрое преобразование Фурье позволяет ускорить этот процесс за счёт разделения вектора коэффициентов на два вектора, рекурсивном вычислении ДПФ для них, и объединении результатов в одно БПФ. Считается, что метод БПФ предложен в 1805 году Гауссом и переоткрыт в 1965 году, после чего нашёл широкое применение с распространением современных компьютеров. В последние 50 лет предпринималось немало попыток повысить эффективность БПФ, например, FFTW.
Новый алгоритм MIT, как заявляется, работает быстрее FFTW. Сравнение приводится в научной работе, а также на странице проекта.
Алгоритм sFFT (Sparse Fast Fourier Transform) создан на основе двух существующих фильтров (фильтр Гаусса и фильтр Чебышева) и нацелен на то, чтобы быстро найти фрагменты с «разреженным» сигналом (sparse signal) и определить исходную амплитуду в каждом из них. Сигнал разбивается на фрагменты (rapid sampling) до тех пор, пока не останется разреженный сигнал с единственной амплитудой. А уже там новый алгоритм выявляет её в 10 тыс. раз быстрее классического БПФ.
Такой метод не является универсальным, и сейчас учёные пытаются определить, в каких конкретно приложениях он даст наибольшую прибавку в производительности.
Читают сейчас
Похожие публикации
- 28 декабря 2015 в 12:59
Ограниченность преобразования Фурье или почему стоит доверять своему слуху
Поиск периодических элементов защиты Паспорта РФ с помощью преобразования Фурье: часть вторая
Поиск периодических элементов защиты Паспорта РФ с помощью преобразования Фурье
AdBlock похитил этот баннер, но баннеры не зубы — отрастут
Комментарии 34
Курсовые работы, проекты, дипломы не являются научно исследовательскими работами. Даже у магистров, обучение которых обязательно имеет исследовательский уклон. По этому, если подходить к вопросу строго по ГОСТу, то государственных стандартов на оформление такого рода работ нет.
При этом вузовский стандарт для учебных работ может базироваться на ГОСТ 7.32-2001. Например, у нас на факультете требуют оформлять учебные работы в соответствии с вышеназванным ГОСТ. Возможно требование использовать стандарты ЕСКД или ЕСПД, но это опять же требования вузов, а не государства.
Если рассматривать структуру дипломных проектов, то она зависит от направления подготовки и присваиваемой квалификации (дипломные работы бакалавров, магистров и инженеров отличаются по своей структуре достаточно сильно). В дипломных работах инженеров разделы БЖ и экономическая часть, насколько мне известно, обязательны. У бакалавров и магистров этих разделов, насколько я знаю, нет. К сожалению, проконсультироваться на счет наличия требования к содержанию дипломов в ГОСах я сейчас не могу, поэтому приходится надеяться, что моя память меня не подводит.
Более того, я бы еще ужесточил требования к содержанию этих разделов, обязательно привязав их содержание к разрабатываемой в рамках диплома системе, а то когда видишь инженеров-пятикурсников, которые искренне не понимают зачем нужно учитывать стоимость сопровождения ПО при оценке разного рода затрат и которые пишут допустимый диапазон температур для офисного работника от +10 до +30 градусов при 8-и часовом рабочем дне, то волосы дыбом встают! Это я в декабре присутствовал на защитах курсовых проектов, которые у пятикурсников нашей кафедры должны перетекать в дипломные проекты.