Дискретное синусоидальное преобразование - Discrete sine transform

В математике , то дискретное синус - преобразование (DST) , является Фурье-преобразования , связанные аналогично дискретного преобразования Фурье (DFT), но с использованием чисто реальную матрицу . Это эквивалентно мнимым частям ДПФ примерно вдвое большей длины, работающим с реальными данными с нечетной симметрией (поскольку преобразование Фурье действительной и нечетной функции является мнимым и нечетным), где в некоторых вариантах вход и / или выход данные сдвинуты на половину отсчета.

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

DST связано с дискретным косинусным преобразованием (DCT), которое эквивалентно DFT вещественных и четных функций. См. Статью DCT для общего обсуждения того, как граничные условия связывают различные типы DCT и DST. Как правило, ДСТ является производным от DCT замены условию Неймана при х = 0 с условием Дирихля . И DCT, и DST были описаны Насиром Ахмедом Т. Натараджаном и KR Rao в 1974 году. DST-I типа (DST-I) был позже описан Anil K. Jain в 1976 г., а DST-II типа (DST- II) был описан Х. Б. Кекрой и Дж. К. Соланка в 1978 г.

Приложения

ТЛЧ широко используются при решении дифференциальных уравнений с помощью спектральных методов , где различные варианты DST соответствуют к слегка различным чет / нечет граничных условий на двух концах массива.

Неофициальный обзор

Иллюстрация неявных четных / нечетных расширений входных данных DST для N = 9 точек данных (красные точки) для четырех наиболее распространенных типов DST (типы I – IV).

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

Связанные с Фурье преобразования, которые работают с функцией в конечной области , такие как DFT, DST или ряд Фурье , можно рассматривать как неявно определяющие расширение этой функции за пределы области. То есть, как только вы напишете функцию как сумму синусоид, вы можете вычислить эту сумму в любом случае , даже если оригинал не был указан. ДПФ, как и ряд Фурье, подразумевает периодическое расширение исходной функции. DST, как и синусоидальное преобразование , подразумевает нечетное расширение исходной функции. ${\ displaystyle f (x)}$${\ displaystyle x}$${\ displaystyle x}$${\ displaystyle f (x)}$

Однако, поскольку ТЛЧ работают на конечных , дискретных последовательностей, две проблемы возникают , которые не применяются для непрерывного синус - преобразования. Во-первых, необходимо указать, является ли функция четной или нечетной как на левой, так и на правой границах области (т. Е. На границах min- n и max- n в определениях ниже, соответственно). Во-вторых, нужно указать, в какой точке функция четная или нечетная. В частности, рассмотрим последовательность ( a , b , c ) из трех равноотстоящих точек данных и скажем, что мы задаем нечетную левую границу. Есть два разумных возможностей: либо данные нечетен относительно точки до до , в этом случае нечетного расширения (- с , - Ь , - , 0, , Ь , с ), или данные нечетно о точка на полпути между a и предыдущей точкой, и в этом случае нечетное расширение будет (- c , - b , - a , a , b , c )

Этот выбор приводит ко всем стандартным вариациям DST, а также к дискретным косинусным преобразованиям (DCT). Каждая граница может быть как четной, так и нечетной (2 варианта на границу) и может быть симметричной относительно точки данных или точки на полпути между двумя точками данных (2 варианта на границу), всего возможностей. Половина этих возможностей, где левая граница нечетная, соответствует 8 типам DST; другая половина - это 8 типов DCT. ${\ Displaystyle 2 \ раз 2 \ раз 2 \ раз 2 = 16}$

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

Определение

Формально, дискретный синус преобразование является линейным , обратимо функция Р  : Р ^Н -> R ^N (где R обозначает множество действительных чисел ), или , что эквивалентно N × N квадратная матрица . Есть несколько вариантов DST с немного измененными определениями. В N действительных чисел х ₀ , х _{N - 1} преобразуются в N действительных чисел X ₀ , X _{N - 1} , согласно одной из формул:

DST-I

${\ displaystyle X_ {k} = \ sum _ {n = 0} ^ {N-1} x_ {n} \ sin \ left [{\ frac {\ pi} {N + 1}} (n + 1) ( k + 1) \ right] \ quad \ quad k = 0, \ dots, N-1}$

Матрица DST-I ортогональна (с точностью до масштабного коэффициента).

DST-I в точности эквивалентен DFT реальной последовательности, которая нечетна вокруг нулевой и средней точек, масштабированной на 1/2. Например, DST-I из N = 3 действительных чисел ( a , b , c ) в точности эквивалентен DFT из восьми действительных чисел (0, a , b , c , 0, - c , - b , - a ) (нечетная симметрия) в масштабе 1/2. (Напротив, типы DST II – IV включают сдвиг на половину выборки в эквивалентном ДПФ.) Это причина N  + 1 в знаменателе синусоидальной функции: эквивалентное ДПФ имеет 2 ( N +1) точки и имеет синусоидальную частоту 2π / 2 ( N +1), поэтому DST-I имеет частоту π / ( N +1).

Таким образом, DST-I соответствует граничным условиям: x _n является нечетным около n  = -1 и нечетным около n = N ; аналогично для X _k .

DST-II

${\ displaystyle X_ {k} = \ sum _ {n = 0} ^ {N-1} x_ {n} \ sin \ left [{\ frac {\ pi} {N}} \ left (n + {\ frac { 1} {2}} \ right) (k + 1) \ right] \ quad \ quad k = 0, \ точки, N-1}$

Некоторые авторы дополнительно умножают член X _{N - 1} на 1 / √ 2 (см. Ниже соответствующие изменения в DST-III). Это делает матрицу DST-II ортогональной (с точностью до масштабного коэффициента), но нарушает прямое соответствие с вещественно-нечетным ДПФ полусмещенного ввода.

DST-II подразумевает граничные условия: x _n нечетно около n  = −1/2 и нечетно около n  =  N  - 1/2; X _k нечетно около k  = −1 и четно около k  =  N  - 1.

DST-III

${\ displaystyle X_ {k} = {\ frac {(-1) ^ {k}} {2}} x_ {N-1} + \ sum _ {n = 0} ^ {N-2} x_ {n} \ sin \ left [{\ frac {\ pi} {N}} (n + 1) \ left (k + {\ frac {1} {2}} \ right) \ right] \ quad \ quad k = 0, \ точки, N-1}$

Некоторые авторы дополнительно умножают член x _{N - 1} на √ 2 (см. Выше соответствующее изменение в DST-II). Это делает матрицу DST-III ортогональной (с точностью до масштабного коэффициента), но нарушает прямое соответствие с вещественно-нечетным ДПФ с полусмещенным выходом.

DST-III подразумевает граничные условия: x _n нечетное около n  = −1 и четное около n  =  N  - 1; X _k нечетно около k  = −1/2 и нечетно около k  =  N  - 1/2.

DST-IV

${\ displaystyle X_ {k} = \ sum _ {n = 0} ^ {N-1} x_ {n} \ sin \ left [{\ frac {\ pi} {N}} \ left (n + {\ frac { 1} {2}} \ right) \ left (k + {\ frac {1} {2}} \ right) \ right] \ quad \ quad k = 0, \ dots, N-1}$

Матрица DST-IV ортогональна (с точностью до масштабного коэффициента).

DST-IV подразумевает граничные условия: x _n нечетно около n  = −1/2 и четно около n  =  N  - 1/2; аналогично для X _k .

Летнее время V – VIII

Типы DST I – IV эквивалентны вещественно-нечетным ДПФ четного порядка. В принципе, на самом деле существует четыре дополнительных типа дискретного синусоидального преобразования (Martucci, 1994), соответствующих вещественно-нечетным ДПФ логически нечетного порядка, которые имеют множители N +1/2 в знаменателях синусоидальных аргументов. Однако на практике эти варианты используются редко.

Обратные преобразования

Обратное к DST-I - это DST-I, умноженное на 2 / ( N  + 1). Инверсией DST-IV является DST-IV , умноженное на 2 / N . Обратное к DST-II - это DST-III, умноженное на 2 / N (и наоборот).

Что касается DFT , коэффициент нормализации перед этими определениями преобразования является просто условием и различается в зависимости от обработки. Например, некоторые авторы умножают преобразования на, чтобы обратное преобразование не требовало дополнительного мультипликативного множителя. ${\ displaystyle {\ sqrt {2 / N}}}$

Вычисление

Хотя прямое применение этих формул потребует O ( N ² ) операций, можно вычислить то же самое со сложностью только O ( N log N ) путем факторизации вычислений, аналогичных быстрому преобразованию Фурье (БПФ). (Можно также вычислить DST с помощью БПФ в сочетании с O ( N ) этапами предварительной и постобработки.)

DST-III или DST-IV можно вычислить из DCT-III или DCT-IV (см. Дискретное косинусное преобразование ) соответственно, изменив порядок входов и изменив знак каждого другого выхода, и наоборот для DST. -II из DCT-II. Таким образом, следует, что типы II – IV DST требуют точно такого же количества арифметических операций (сложения и умножения), что и соответствующие типы DCT.

Рекомендации

Библиография

• SA Martucci, "Симметричная свертка и дискретные синусоидальные и косинусные преобразования", IEEE Trans. Сигнальный процесс. СП-42 , 1038–1051 (1994).
• Маттео Фриго и Стивен Джонсон : FFTW , http://www.fftw.org/ . Бесплатная ( GPL ) библиотека C, которая может вычислять быстрые DST (типы I – IV) в одном или нескольких измерениях произвольного размера. Также М. Фриго и С. Г. Джонсон, « Дизайн и реализация FFTW3 », Протоколы IEEE 93 (2), 216–231 (2005).
• Такуя Оура: Универсальный пакет БПФ, http://www.kurims.kyoto-u.ac.jp/~ooura/fft.html . Бесплатные библиотеки C и FORTRAN для вычисления быстрых DST в одном, двух или трех измерениях, мощность двух размеров.
• Нажмите, WH; Теукольский, С.А. Феттерлинг, штат Вашингтон; Фланнери, Б.П. (2007), «Раздел 12.4.1. Синусоидальное преобразование» , Численные рецепты: Искусство научных вычислений (3-е изд.), Нью-Йорк: Cambridge University Press, ISBN   978-0-521-88068-8 .
• Р. Чивукула и Ю. Резник, " Быстрое вычисление дискретных косинусных и синусоидальных преобразований типов VI и VII ", Proc. SPIE Vol. 8135, 2011.