Швидкі алгоритми дискретних косинус і синус-перетворень Фур’є

 

Дискретне косинус-перетворення Фур’є (ДКПФ) і дискретне синус-перетворення Фур’є (ДСПФ), а також відповідні швидкі алгоритми (ШКПФ і ШСПФ) забезпечують безнадлишкове виконання дискретного перетворення Фур’є (ДПФ) і Хартлі (ДПХ) комплексної, дійсної, комплексно-спряженої, парної або непарної послідовності [4]. При цьому розпаралелюється обробка дійсної, комплексно-спряженої і комплексної послідовностей.

Нехай x(n), n=0,1,…,N-1,N=2^m , m=1,2,3…- дійсна послідовність, x_c(n) і x_s(n) – відповідно її парна (4.19) і непарна (4.20) частини

 

x_c(n)=x_c(N-n)={x(n)+x(N-n)}/2, n=0,1,…,N/2; (4.19)

x_s(n)=-x_s(N-n)={x(n)-x(N-n)}/2, n=0,1,…,N/2; (4.20)

так, що x(n)=x_c(n)+x_s(n), n=0,1,…,N-1, і нехай H_C(k)=ДКПФ_N{x_c(n)}, H_S(k)=ДСПФ_N{xs(n)}, H_C(k)= x_c(n) C^kn_N, H_S(k)= x_s(n) S^kn_N,

де C^r_N=cos(2пr/N), S^'r_N= sin(2пr/N), xc(n)=ДКПФ^-1_N{H_C(k)} = N ДКПФ{H_C(k)},x_s(n) = ДСПФ^-1_N{H_S (k)} = ДСПФ{H_S(k)}.

 

Серед відомих [4] алгоритмів ШКПФ і ШСПФ простотою реалізації відрізняються алгоритми, побудовані за методом Рейдера-Бреннера (ШКПФРБ і ШСПФРБ). Їх графи загалом зберігають схему зв’язків алгоритмів за основою два, але за кількістю множень відповідають алгоритмам за розщепленою основою і мають дуже просту базову операцію “дійсний метелик”. Тому віддамо їм перевагу при реалізації ШКПФ і ШСПФ на потокових обчислювальних структурах.

Формули розкладу (ФР) алгоритмів ШКПФ і ШСПФ відповідно задаються виразами

 

H_C(2k) = ДКПФ_N/2 {x_c(n) + x_c(N/2+ n)};

H_C(I) = A(0), H_C(2k+1) = 2A(k) -H_C(2k-1), k=1,2,...N/2-2; (4.21)

H_S(2k) = ДСПФ_N/2{x_s(n)+x_s(N/2+n)};

H_S(I) = B(0), H_S(2k+1) = 2B(k) +H_S(2k-1), k=1,2,....N/2-2, (4.22)

де A(k)=ДКПФ_N/2{[x_c(n)-x_c(N/2+n)]Cⁿ_N}, B(k)=ДCПФ_N/2{[x_s(n)-x_s(N/2+n)]Sⁿ_N}.

 

На їх основі N-точкове ДКПФ розбивається на два N/2-точкові ДКПФ, а N-точкове ДСПФ - на ДСПФ_N/2 і ДКПФ_N/2. Рекурсивно застосовуючи ФР (4.21) і (4.22) до перетворень меншої розмірності, отримуємо алгоритми ШКПФРБ і ШСПФРБ [4]. Ці алгоритми мають близькі схеми реалізації обчислень, які достатньо просто реалізуються на одному і тому ж пристрої. Так, на рис. 4.9 наведений узагальнений граф алгоритмів ШКПФРБ і ШСПФРБ для N=16.

 

Рис 4.9. Узагальнений граф алгоритму ШКПФРБ і ШСПФРБ для N=16

Для першого з них використовуються множники r=s=1, R_n=C₁₆ ⁿ , на виході маємо P(k)=H_C(k), а для другого r=0, S=-1, R_n=S₁₆ⁿ, P(k)=H_S(k).

Порівняльний аналіз приведеного та відомого графа алгоритму комплексного ШПФ Кулі-Тьюкі за основою два (ШПФк2) з частотним прорідженням [4], показує співпадіння їх структури на m=log₂N основних етапах переходу до перетворень меншої розмірності. При цьому використовується суттєво спрощена базова операція, що виконується над дійсними даними при дійсних фазових множниках (рис.4.10).

 

Рис.4.10 Базові операції алгоритмів ШКПФ-ШСПФ

 

На двох останніх етапах фазові множники приймають тривіальне значення, і тому на графі не показані. Крім того, в алгоритмах ШКПФРБ-ШСПФРБ додатково введений етап виділення парної за (4.19) чи непарної за (4.20) складових вхідної послідовності, а також m=log₂N-1 етапів додавань, на яких здійснюється перехід від проміжних перетворень A(k) чи B(k) до необхідних H_C(k) і H_S(k).