Сокращение вычислений для базовых дискретных преобразований Фурье и Хартли при разреженных массивах сигналов

Сокращение вычислений для базовых дискретных преобразований Фурье и Хартли при разреженных массивах сигналов

Приведены основанные на учете нулевых элементов в массивах входных и выходных сигналов алгоритмы, использование которых обеспечивает сокращение вычислений прямого и обратного базового дискретного преобразования Фурье и прямого базового преобразования Хартли. Наведено базовані на обліку нульових елем...

Ausführliche Beschreibung

Gespeichert in:
Bibliographische Detailangaben
Veröffentlicht in:Электронное моделирование
Datum:2013
Hauptverfasser: Годлевский, В.С., Денисенко, А.М.
Format: Artikel
Sprache:Russian
Veröffentlicht: Інститут проблем моделювання в енергетиці ім. Г.Є. Пухова НАН України 2013
Schlagworte:
Математические методы и модели
Online Zugang:https://nasplib.isofts.kiev.ua/handle/123456789/100845
Tags: Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
Назва журналу:Digital Library of Periodicals of National Academy of Sciences of Ukraine
Zitieren:Сокращение вычислений для базовых дискретных преобразований Фурье и Хартли при разреженных массивах сигналов / В.С. Годлевский, А.М. Денисенко // Электронное моделирование. — 2013. — Т. 35, № 3. — С. 35-48. — Бібліогр.: 12 назв. — рос.

Institution

Digital Library of Periodicals of National Academy of Sciences of Ukraine
id nasplib_isofts_kiev_ua-123456789-100845
record_format dspace
spelling Годлевский, В.С.
Денисенко, А.М.
2016-05-27T16:00:35Z
2016-05-27T16:00:35Z
2013
Сокращение вычислений для базовых дискретных преобразований Фурье и Хартли при разреженных массивах сигналов / В.С. Годлевский, А.М. Денисенко // Электронное моделирование. — 2013. — Т. 35, № 3. — С. 35-48. — Бібліогр.: 12 назв. — рос.
0204-3572
https://nasplib.isofts.kiev.ua/handle/123456789/100845
621.372
Приведены основанные на учете нулевых элементов в массивах входных и выходных сигналов алгоритмы, использование которых обеспечивает сокращение вычислений прямого и обратного базового дискретного преобразования Фурье и прямого базового преобразования Хартли.
Наведено базовані на обліку нульових елементів в масивах вхідних і вихідних сигналів алгоритми, що забезпечують скорочення обчислень прямого і зворотного базового дискретного перетворення Фурьє і прямого базового перетворення Хартлі.
The authors perform algorithms based on the account of zero elements in the arrays of input and output signals. The use of these signals ensures the reduction of calculations of the Fourier direct and inverse base discrete transformation and Hartley direct base transformation.
ru
Інститут проблем моделювання в енергетиці ім. Г.Є. Пухова НАН України
Электронное моделирование
Математические методы и модели
Сокращение вычислений для базовых дискретных преобразований Фурье и Хартли при разреженных массивах сигналов
Article
published earlier
institution Digital Library of Periodicals of National Academy of Sciences of Ukraine
collection DSpace DC
title Сокращение вычислений для базовых дискретных преобразований Фурье и Хартли при разреженных массивах сигналов
spellingShingle Сокращение вычислений для базовых дискретных преобразований Фурье и Хартли при разреженных массивах сигналов
Годлевский, В.С.
Денисенко, А.М.
Математические методы и модели
title_short Сокращение вычислений для базовых дискретных преобразований Фурье и Хартли при разреженных массивах сигналов
title_full Сокращение вычислений для базовых дискретных преобразований Фурье и Хартли при разреженных массивах сигналов
title_fullStr Сокращение вычислений для базовых дискретных преобразований Фурье и Хартли при разреженных массивах сигналов
title_full_unstemmed Сокращение вычислений для базовых дискретных преобразований Фурье и Хартли при разреженных массивах сигналов
title_sort сокращение вычислений для базовых дискретных преобразований фурье и хартли при разреженных массивах сигналов
author Годлевский, В.С.
Денисенко, А.М.
author_facet Годлевский, В.С.
Денисенко, А.М.
topic Математические методы и модели
topic_facet Математические методы и модели
publishDate 2013
language Russian
container_title Электронное моделирование
publisher Інститут проблем моделювання в енергетиці ім. Г.Є. Пухова НАН України
format Article
description Приведены основанные на учете нулевых элементов в массивах входных и выходных сигналов алгоритмы, использование которых обеспечивает сокращение вычислений прямого и обратного базового дискретного преобразования Фурье и прямого базового преобразования Хартли. Наведено базовані на обліку нульових елементів в масивах вхідних і вихідних сигналів алгоритми, що забезпечують скорочення обчислень прямого і зворотного базового дискретного перетворення Фурьє і прямого базового перетворення Хартлі. The authors perform algorithms based on the account of zero elements in the arrays of input and output signals. The use of these signals ensures the reduction of calculations of the Fourier direct and inverse base discrete transformation and Hartley direct base transformation.
issn 0204-3572
url https://nasplib.isofts.kiev.ua/handle/123456789/100845
citation_txt Сокращение вычислений для базовых дискретных преобразований Фурье и Хартли при разреженных массивах сигналов / В.С. Годлевский, А.М. Денисенко // Электронное моделирование. — 2013. — Т. 35, № 3. — С. 35-48. — Бібліогр.: 12 назв. — рос.
work_keys_str_mv AT godlevskiivs sokraŝenievyčisleniidlâbazovyhdiskretnyhpreobrazovaniifurʹeihartliprirazrežennyhmassivahsignalov
AT denisenkoam sokraŝenievyčisleniidlâbazovyhdiskretnyhpreobrazovaniifurʹeihartliprirazrežennyhmassivahsignalov
first_indexed 2025-11-26T02:05:49Z
last_indexed 2025-11-26T02:05:49Z
_version_ 1850607516211216384
fulltext ÓÄÊ 621.372 Â.Ñ. Ãîäëåâñêèé, ä-ð òåõí. íàóê, À.Ì. Äåíèñåíêî, êàíä. ôèç.-ìàò. íàóê Ãîñóäàðñòâåííîå ïðåäïðèÿòèå «ÄÈÑÈÒ» ÍÀÍ Óêðàèíû» (03164, Êèåâ, óë. Ãåí. Íàóìîâà, 17, òåë. (044)4229622, e-mail: disit2007@gmail.com) Ñîêðàùåíèå âû÷èñëåíèé äëÿ áàçîâûõ äèñêðåòíûõ ïðåîáðàçîâàíèé Ôóðüå è Õàðòëè ïðè ðàçðåæåííûõ ìàññèâàõ ñèãíàëîâ Ïðèâåäåíû îñíîâàííûå íà ó÷åòå íóëåâûõ ýëåìåíòîâ â ìàññèâàõ âõîäíûõ è âûõîäíûõ ñèãíàëîâ àëãîðèòìû, èñïîëüçîâàíèå êîòîðûõ îáåñïå÷èâàåò ñîêðàùåíèå âû÷èñëåíèé ïðÿ- ìîãî è îáðàòíîãî áàçîâîãî äèñêðåòíîãî ïðåîáðàçîâàíèÿ Ôóðüå è ïðÿìîãî áàçîâîãî ïðå- îáðàçîâàíèÿ Õàðòëè. Íàâåäåíî áàçîâàí³ íà îáë³êó íóëüîâèõ åëåìåíò³â â ìàñèâàõ âõ³äíèõ ³ âèõ³äíèõ ñèãíàë³â àëãîðèòìè, ùî çàáåçïå÷óþòü ñêîðî÷åííÿ îá÷èñëåíü ïðÿìîãî ³ çâîðîòíîãî áàçîâîãî äèñê- ðåòíîãî ïåðåòâîðåííÿ Ôóðüº ³ ïðÿìîãî áàçîâîãî ïåðåòâîðåííÿ Õàðòë³. Ê ë þ ÷ å â û å ñ ë î â à: óìåíüøåíèå âû÷èñëåíèé, äèñêðåòíîå ïðåîáðàçîâàíèå Ôóðüå, äèñêðåò- íîå ïðåîáðàçîâàíèå Õàðòëè, ó÷åò íóëåâûõ ýëåìåíòîâ â àëãîðèòìàõ. Ïîñòàíîâêà çàäà÷è. Ïðè ÷àñòîòíîé öèôðîâîé îáðàáîòêå ñèãíàëîâ (ñïåêò- ðàëüíîé è êîððåëÿöèîííîé, àäàïòèâíîé ôèëüòðàöèè) ïðèìåíÿþòñÿ áëèç- êèå ïî ñìûñëó è âèäó äèñêðåòíûå ïðåîáðàçîâàíèÿ Ôóðüå (ÄÏÔ) èëè Õàðòëè (ÄÏÕ) [1, 2]. Öåëåñîîáðàçíîñòü ïðèìåíåíèÿ êàæäîãî èç íèõ çàâè- ñèò îò îñîáåííîñòåé ðåøàåìûõ çàäà÷ è ñâîéñòâ èñïîëüçóåìûõ âû÷èñëè- òåëüíûõ ñðåäñòâ. Ðàññìîòðèì ïðèìåð öèôðîâîé îáðàáîòêè âåùåñòâåííûõ ñèãíàëîâ. Áàçîâîå ïðÿìîå äèñêðåòíîå ïðåîáðàçîâàíèå Ôóðüå (ÏÄÏÔ) N-òî÷å÷- íîé âåùåñòâåííîé ïîñëåäîâàòåëüíîñòè{ , ,..., }f k Nk � �0 1 (ãäå âñå ñîñòàâ- ëÿþùèå ïîñëåäîâàòåëüíîñòè ÿâëÿþòñÿ äåéñòâèòåëüíûìè ÷èñëàìè) ïðè N p�2 (ãäå ð — öåëîå ÷èñëî) èìååò âèä F N f i kn N n k N k� �� � � � � � � 1 2 0 1 exp � , n N� �0 1,..., . (1) ISSN 0204–3572. Ýëåêòðîí. ìîäåëèðîâàíèå. 2013. Ò. 35. ¹ 3 35 � Â.Ñ. Ãîäëåâñêèé, À.Ì. Äåíèñåíêî, 2013 Ïðè ñïåêòðàëüíîé îáðàáîòêå ñèãíàëîâ â ÷àñòîòíîé îáëàñòè äîñòàòî÷íî èç (1) âû÷èñëèòü òîëüêî ïåðâûå ãàðìîíèêè, îò íóëÿ äî N /2 1� , ïîñêîëüêó îñòàëüíûå ãàðìîíèêè Fn ïðè n N N� �/ , ... ,2 1 íèêàêîé äîïîëíèòåëüíîé èíôîðìàöèè î ÷àñòîòíûõ ñâîéñòâàõ ïîñëåäîâàòåëüíîñòè { }f k íå íåñóò. Ýòî ñëåäóåò èç ðàâåíñòâ F FN n n� � * , n N � �1 2 1,..., , (2) ãäå îïåðàöèÿ «*» îçíà÷àåò êîìïëåêñíîå ñîïðÿæåíèå. Îäíàêî ïðè îáðàòíîì äèñêðåòíîì ïðåîáðàçîâàíèÿ Ôóðüå (ÎÄÏÔ), � expf N F i kn N n k N k� � � � � � � � 1 2 0 1 � , n N� �0 1,..., , (3) èñïîëüçóþòñÿ âñå ñïåêòðàëüíûå ñîñòàâëÿþùèå (2). Áàçîâîå äèñêðåòíîå ïðÿìîå ïðåîáðàçîâàíèå Õàðòëè âåùåñòâåííîé ïî- ñëåäîâàòåëüíîñòè{ , , ..., }f k Nk � �0 1 èìååò âèä H N f kn N n k N k� � � � � � � � 1 2 0 1 cas � , n N� �0 1,..., , (4) ãäå cas cos sin 2 2 2� � �kn N kn N kn N � � � � � � � � � � � � � � � � . Ïðè ýòîì ÄÏÕ è ÄÏÔ ñâÿçàíû ñëåäóþùèìè ñîîòíîøåíèÿìè: Re ( )F H Hn n N n� � 1 2 , Im ( )F H Hn n N n� � � 1 2 , n N � �1 2 1,..., . (5) Áàçîâîå äèñêðåòíîå ïðåîáðàçîâàíèå Õàðòëè îáëàäàåò ñâîéñòâàìè, îòëè÷àþùèìè åãî îò ÄÏÔ. Âî-ïåðâûõ, îáðàòíîå ïðåîáðàçîâàíèå Õàðòëè (ÎÄÏÕ) ñîâïàäàåò ñ ÄÏÕ ñ òî÷íîñòüþ äî êîýôôèöèåíòà 1/ N: f H kn N n k N k� � � � � � � � 0 1 2 cas � , n N� �0 1,..., . (6) Âî-âòîðûõ, ïðè ðåàëèçàöèè ÄÏÕ âû÷èñëåíèÿ ïðîâîäÿòñÿ â ïîëå äåéñò- âèòåëüíûõ ÷èñåë. Ýòî â íåêîòîðûõ ñëó÷àÿõ äàåò âîçìîæíîñòü íåñêîëüêî óìåíüøèòü îáúåì êîäà ïðîãðàììû è ÷èñëî îïåðàöèé ïî ñðàâíåíèþ ñ ÄÏÔ. Íàëè÷èå áûñòðûõ ìåòîäîâ [1—5] âû÷èñëåíèé ïðåîáðàçîâàíèé Ôóðüå (ÁÏÔ) è Õàðòëè (ÁÏÕ) äåëàåò ïðèìåíåíèå äèñêðåòíûõ ïðåîáðàçîâàíèé (1) è (4) ýôôåêòèâíûì ñðåäñòâîì âû÷èñëåíèÿ ñïåêòðîâ, êîððåëÿöèîííûõ ôóíêöèé è ðåøåíèÿ äðóãèõ çàäà÷, ñâÿçàííûõ ñî ñïåêòðàëüíûì ðàçëîæå- íèåì è ôèëüòðàöèåé ñèãíàëîâ, â ñëó÷àå, êîãäà òðåáóåòñÿ íàéòè âñå ãàð- Â.Ñ. Ãîäëåâñêèé, À.Ì. Äåíèñåíêî 36 ISSN 0204–3572. Electronic Modeling. 2013. V. 35. ¹ 3 ìîíèêè îò íóëÿ äî N /2 1� , à ñ ïîìîùüþ îáðàòíûõ ïðåîáðàçîâàíèé (ÎÁÏÔ, ÎÁÏÕ) — âñå âðåìåííûå îòñ÷åòû ñèãíàëîâ. Ïðè ýòîì â ñëó÷àå ïðèìå- íåíèÿ êàê ïðÿìûõ, òàê è îáðàòíûõ ÁÏÔ è ÁÏÕ ÷èñëî îïåðàöèé (óìíî- æåíèÿ è ñëîæåíèÿ) íå ïðåâûøàåò C N Nlog , ÷òî ïðè áîëüøèõ çíà÷åíèÿõ N ñóùåñòâåííî ìåíüøå ÷èñëà N 2 îïåðàöèé ïðè íåïîñðåäñòâåííîì ïðèìå- íåíèè ïðåîáðàçîâàíèé (1), (3), (4), (6).  ýòîì ñëó÷àå êîíñòàíòà Ñ çàâèñèò òîëüêî îò âûáîðà àëãîðèòìà áûñòðîãî ïðåîáðàçîâàíèÿ è íå çàâèñèò îò çíà÷åíèÿ N.  ðàáîòå [2, c. 136] ïðèâåäåí ïðèìåð ðåàëèçàöèè àëãîðèòìà Êóëè—Òüþêè äëÿ êîìïëåêñíîãî âõîäÿùåãî ìàññèâà, ãäå óñòàíîâëåíî, ÷òî ÷èñëî îïåðàöèé äåéñòâèòåëüíîãî óìíîæåíèÿ M R è äåéñòâèòåëüíîãî ñëî- æåíèÿ AR , íåîáõîäèìûõ äëÿ ðàñ÷åòà ÁÏÔ, ñîñòàâëÿåò A N NR � � 1 2 10 7 82( log ) , M N NR � � 1 2 10 3 82( log ) , èëè A N NR � � 3 1 42( log ) , M N NR � � ( log )7 2 122 , â çàâèñèìîñòè îò ðåàëèçàöèè îïåðàöèè êîìïëåêñíîãî óìíîæåíèÿ (ïðè óñëîâèè, ÷òî ìàññèâû çíà÷åíèé ñèíóñîâ è êîñèíóñîâ ïðåäâàðèòåëüíî ïîäãîòîâëåíû è èñïîëüçóþòñÿ â ïðîãðàììå êàê ìàññèâû äåéñòâèòåëüíûõ ÷èñåë). Îäíàêî, ïðè ÷àñòîòíîé îáðàáîòêå ñèãíàëîâ íà ïðàêòèêå äîñòàòî÷íî ÷àñòî ñëó÷àåòñÿ, ÷òî òðåáóåìîå ÷èñëî êîìïîíåíò ïðåîáðàçîâàíèÿ â (1) èëè (3) ÿâëÿåòñÿ íåáîëüøèì. Ïðè ýòîì â (1), (2) ìíîæåñòâî èñêîìûõ ãàðìîíèê èìååò âèä ïîëîñû ÷àñòîò: S r r m� �{[ , ]1 , r N� �0 2 1, / , m N r� � / }2 1 . (7) Êðîìå òîãî, ÷àñòî èñõîäíàÿ ïîñëåäîâàòåëüíîñòü { }f k òàêæå ñîäåðæèò áîëüøîå ÷èñëî íóëåâûõ ýëåìåíòîâ. Ê òàêèì ñëó÷àÿì îòíîñÿòñÿ ñëåäóþ- ùèå òèïîâûå çàäà÷è: 1. Óçêîïîëîñíàÿ îáðàáîòêà ñèãíàëîâ, ïðè êîòîðîé äëÿ âûáîðêè { ,f k k N� �0 1, ..., } çíà÷åíèé ñèãíàëîâ âî âðåìåííîé îáëàñòè îïðåäåëÿþòñÿ çíà÷åíèÿ ñïåêòðàëüíûõ ñîñòàâëÿþùèõ ñèãíàëîâ â óçêîé ïîëîñå ÷àñòîò. Ñïåêòðàëüíûå ñîñòàâëÿþùèå ñèãíàëîâ ïîäâåðãàþòñÿ îáðàáîòêå â ÷àñ- òîòíîé îáëàñòè (íàïðèìåð, êîððåëÿöèîííîé îáðàáîòêå è (èëè) àäàïòèâíîé íåëèíåéíîé ôèëüòðàöèè [6]). Ïîñëå ôèëüòðàöèè îïðåäåëÿåòñÿ îáðàç âî âðåìåííîé îáëàñòè. Ïðè ýòîì îòíîøåíèå ÷èñëà îòñ÷åòîâ ñèãíàëà â èñõîä- íîé è ðåçóëüòèðóþùåé âðåìåííûõ ïîñëåäîâàòåëüíîñòÿõ ê ÷èñëó îòñ÷åòîâ ñïåêòðàëüíûõ ñîñòàâëÿþùèõ ñèãíàëîâ â ïðîìåæóòî÷íûõ ïîñëåäîâàòåëü- íîñòÿõ â óçêîïîëîñíîé ÷àñòîòíîé îáëàñòè ìîæåò äîñòèãàòü çíà÷åíèé ïî- ðÿäêà íåñêîëüêèõ ñîòåí èëè äàæå òûñÿ÷. Ñîêðàùåíèå âû÷èñëåíèé äëÿ áàçîâûõ äèñêðåòíûõ ïðåîáðàçîâàíèé Ôóðüå è Õàðòëè ISSN 0204–3572. Ýëåêòðîí. ìîäåëèðîâàíèå. 2013. Ò. 35. ¹ 3 37 2. Óâåëè÷åíèå òî÷íîñòè è èçáèðàòåëüíîñòè ñïåêòðàëüíîé è êîððåëÿ- öèîííîé îáðàáîòêè ñèãíàëîâ â ðåçóëüòàòå ñóùåñòâåííîãî óâåëè÷åíèÿ ðàç- ìåðíîñòè èñõîäíîé ïîñëåäîâàòåëüíîñòè çíà÷åíèé ñèãíàëà ïîñðåäñòâîì âêëþ÷åíèÿ â íåãî íóëåâûõ çíà÷åíèé. Äàííàÿ çàäà÷à íà ïðàêòèêå ìîæåò âñòðå÷àòüñÿ êàê â êà÷åñòâå ñîñòàâíîé ÷àñòè çàäà÷è 1, òàê è â êà÷åñòâå ñàìîñòîÿòåëüíîé çàäà÷è (íàïðèìåð, ïðè ðàñ÷åòå òîëüêî ñïåêòðàëüíûõ õà- ðàêòåðèñòèê â ÷àñòîòíîé îáëàñòè èñõîäíîãî ñèãíàëà, çàäàííîãî âî âðåìåí- íîé îáëàñòè). 3. Îïòèìèçàöèÿ âðåìåííûõ ôóíêöèé (îêîí) äëÿ ïðåîáðàçîâàíèÿ Ôóðüå, ïðè êîòîðîé èñêóññòâåííî äîáàâëÿåòñÿ áîëüøîå ÷èñëî íóëåâûõ (âñïîìî- ãàòåëüíûõ) ýëåìåíòîâ ê èñõîäíîìó ìàññèâó îòñ÷åòîâ ñèãíàëîâ äëÿ óâåëè- ÷åíèÿ òî÷íîñòè âû÷èñëåíèÿ ïàðàìåòðîâ îêîííûõ ôóíêöèé (ôóíêöèé öåëè è îãðàíè÷åíèé) [7, 8]. Ïðè ðåøåíèè ïåðå÷èñëåííûõ çàäà÷ ñ ïîìîùüþ ñòàíäàðòíûõ àëãîðèò- ìîâ, îñíîâàííûõ íà ìåòîäàõ ÁÏÔ èëè ÁÏÕ, çíà÷èòåëüíàÿ ÷àñòü îáùåé òðóäîåìêîñòè ïðèõîäèòñÿ ëèáî íà âû÷èñëåíèÿ ñ íóëåâûìè ýëåìåíòàìè, ëèáî íà âû÷èñëåíèÿ ÷àñòè ýëåìåíòîâ âûõîäíîãî ìàññèâà, êîòîðàÿ íå âîñòðåáîâàíà â ïîñòàíîâêå çàäà÷è îáðàáîòêè ñèãíàëîâ.  òàêèõ ñëó÷àÿõ íåïîñðåäñòâåííîå âû÷èñëåíèå ïî ôîðìóëàì (1), (2), (4) (ïðèìåíåíèå ñòàí- äàðòíîãî ÄÏÔ èëè ÄÏÕ) áîëåå ýôôåêòèâíî ïî ñðàâíåíèþ ñ àëãîðèòìàìè áûñòðîãî ïðåîáðàçîâàíèÿ. Äëÿ óìåíüøåíèÿ îáùåé òðóäîåìêîñòè âû÷èñëåíèé ïðåîáðàçîâàíèÿ Ôóðüå ïîñëåäîâàòåëüíîñòåé ñ áîëüøèì ñîäåðæàíèåì íóëåâûõ ýëåìåíòîâ öåëåñîîáðàçíî ïðèìåíÿòü ìîäèôèöèðîâàííûå àëãîðèòìû, íàïðàâëåííûå íà èñêëþ÷åíèå èç îáðàáîòêè íóëåâûõ è èçáûòî÷íûõ äàííûõ. Áóäåì ðàñ- ñìàòðèâàòü àëãîðèòìû, ïðåäñòàâëÿþùèå ñîáîé êîìáèíàöèè ñòàíäàðòíûõ ÄÏÔ èëè ÄÏÕ è ìîäèôèêàöèþ áûñòðûõ àëãîðèòìîâ èõ âû÷èñëåíèÿ, à òàêæå ïðîàíàëèçèðóåì îáëàñòè èõ öåëåñîîáðàçíîãî ïðèìåíåíèÿ. Ðàññìîòðèì ñëó÷àé, êîãäà òðåáóåòñÿ íàéòè ìàëîå ÷èñëî m ãàðìîíèê âõîäíîé ïîñëåäîâàòåëüíîñòè { , , ..., }f k Nk � �0 1 (âõîäíîãî ñèãíàëà). Êàê èçâåñòíî, åñëè ÷èñëî èñêîìûõ ãàðìîíèê m òàêîå, ÷òî 1� �m C Nlog , òî ðåêîìåíäóåòñÿ ïðèìåíÿòü ñòàíäàðòíûå ÏÄÏÔ èëè ÏÄÏÕ, ïîñêîëüêó, íà- ïðèìåð, â ñëó÷àå ïðèìåíåíèÿ ÏÄÏÔ äëÿ ïîëîñû S â (7) òðåáóþòñÿ òîëüêî 2m N îïåðàöèé âìåñòî CN Nlog â ñëó÷àå ÁÏÔ. Èçâåñòíû óñêîðåííûå ìå- òîäû ÏÄÏÔ, ïîçâîëÿþùèå óìåíüøèòü ÷èñëî îïåðàöèé ïðè âûïîëíåíèè ÏÄÏÔ, íàïðèìåð ìåòîä Ãåðöåëÿ, èñïîëüçîâàíèå êîòîðîãî ïîçâîëÿåò â äâà ðàçà óìåíüøèòü ÷èñëî îïåðàöèé ïî ñðàâíåíèþ ñ íåïîñðåäñòâåííûì ïðè- ìåíåíèåì ÏÄÏÔ. Èçâåñòíû òàêæå ìåòîäû, íàïðàâëåííûå íà àäàïòèâíîå èñêëþ÷åíèå èç âû÷èñëåíèé â àëãîðèòìàõ ÁÏÔ îïåðàöèé ñ íóëåâûìè ýëå- ìåíòàìè (íàïðèìåð, [9 —12]). Â.Ñ. Ãîäëåâñêèé, À.Ì. Äåíèñåíêî 38 ISSN 0204–3572. Electronic Modeling. 2013. V. 35. ¹ 3 Ðàññìîòðèì àëãîðèòìû, ïîçâîëÿþùèå óìåíüøàòü ÷èñëî îïåðàöèé ïî ñðàâíåíèþ ñ ìåòîäîì Ãåðöåëÿ ïðè âûïîëíåíèè ÏÄÏÔ, à òàêæå ÷èñëî îïåðàöèé ïðè âûïîëíåíèè ÏÄÏÕ. Ýòè àëãîðèòìû îñíîâàíû íà ðàçäåëü- íîì èñïîëüçîâàíèè ñâîéñòâ ñèììåòðèè ôóíêöèé cos x è sin x. Èñïîëüçîâàíèå ñâîéñòâ ñèììåòðèè ôóíêöèé ïðè âû÷èñëåíèè ÏÄÏÔ è ÎÄÏÔ. Ïðåäñòàâèì ÏÄÏÔ (1) ñ ó÷åòîì (7) â âèäå F Fn n� cos iFn sin , n S� , ãäå ìíîæåñòâî S çàäàíî (7); Fn cos è Fn sin — êîñèíóñíîå è ñè- íóñíîå ïðåîáðàçîâàíèÿ âõîäíîé ïîñëåäîâàòåëüíîñòè { , , ..., }f k Nk � �0 1 , F N f kn N n k N kcos cos� � � � � � � � 1 2 0 1 � , (8) F N f kn N n k N ksin sin� � � � � � � � � 1 2 0 1 � . (9) Äëÿ (8) è (9) ñïðàâåäëèâî ñëåäóþùåå óòâåðæäåíèå. Óòâåðæäåíèå 1. Åñëè â (1) N äåëèòñÿ áåç îñòàòêà íà ÷åòûðå, òî äëÿ ÷åò- íûõ ãàðìîíèê âõîäíîé ïîñëåäîâàòåëüíîñòè { , , ..., }f k Nk � �0 1 ÏÄÏÔ áóäåò èìåòü âèä F N f f f fl l N N N2 0 4 3 4 2 1 1cos ( )� � � � � � � � � � � � � � � � � � � � � � � � � � � k N k N k N k N kf f f f kl N1 4 1 2 2 4 cos � � � , (10) F N f f f fl l N N k N k N2 4 3 4 1 4 1 2 1 1sin ( )� � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � k N k N kf f kl N 2 4 sin � , (11) à äëÿ íå÷åòíûõ ãàðìîíèê âõîäíîé ïîñëåäîâàòåëüíîñòè — F N f f f f f fl N k N k N k N k N k2 1 0 2 1 4 1 2 2 1 � � � �� � � � � � � � � cos � � � � � � � � � � � � � cos ( )2 2 1�k l N , (12) F N f fl l N N2 1 4 3 4 1 1 � � � � � � � � � � � � �sin ( ) Ñîêðàùåíèå âû÷èñëåíèé äëÿ áàçîâûõ äèñêðåòíûõ ïðåîáðàçîâàíèé Ôóðüå è Õàðòëè ISSN 0204–3572. Ýëåêòðîí. ìîäåëèðîâàíèå. 2013. Ò. 35. ¹ 3 39 � � � � � � � � � � � � � k N k N k N k N kf f f f k l N1 4 1 2 2 2 2 1 sin ( )� � � � � � � , (13) ãäå l N� �0 2 1, ...,( / ) . Ä î ê à ç à ò å ë ü ñ ò â î óòâåðæäåíèÿ 1 ñëåäóåò èç ðàâåíñòâ cos 2 2� �kn N n N k N � � � � � � �� � � � � �cos ( ) � � �� � � � � � � � � � � � � � � ( ) cos ( ) cos1 2 2 1 2 2n n n N k N n N � � k N � � � � � � � � � � � � � , (14) sin 2 2� �kn N n N k N � � � � � � � �� � � � � �sin ( ) � � �� � � � � � � � � � � � � � � ( ) sin ( ) sin1 2 2 1 2 1n n n N k N n N � � 2 � � � � � � � � � � � � � k N . (15) Èç óòâåðæäåíèÿ 1 ñëåäóåò, ÷òî â ñëó÷àå, êîãäà èñõîäíàÿ ïîñëåäîâà- òåëüíîñòü { , , ... , }f k Nk � �0 1 âåùåñòâåííàÿ, äëÿ âû÷èñëåíèÿ ÏÄÏÔ (1) åäèíñòâåííîé ãàðìîíèêè (îäíîé ñïåêòðàëüíîé ñîñòàâëÿþùåé) ïðè ôèêñè- ðîâàííîì çíà÷åíèè n N� �0 1, ..., íåîáõîäèìî âûïîëíèòü N /2 îïåðàöèé óìíîæåíèÿ, à òàêæå 2 2N � îïåðàöèé ñëîæåíèÿ äëÿ ÷åòíûõ ãàðìîíèê è 2 4N � äëÿ íå÷åòíûõ. Ïðè âû÷èñëåíèè m ãàðìîíèê (äëÿ m�1) öåëåñîîáðàçíî ïðåäâàðèòåëü- íî âû÷èñëèòü ñóììû, ñîäåðæàùèåñÿ â (10) — (13) äëÿ k N� �1 4 1, ...,( ) : f f f f fk k N k N k N k1 2 2 � � � , (16) f f f f fk k N k N k N k2 2 2 � � � � � , (17) f f f f fk k N k N k N k3 2 2 � � � � � , (18) f f f f fk k N k N k N k4 2 2 � � � � � . (19) Òîãäà ïðè âû÷èñëåíèè m ãàðìîíèê, ïîäñòàâëÿÿ (16) â (10), (17) â (11) è (18) â (12), (19) â (13), äëÿ ïîñëåäîâàòåëüíîñòè { , , ..., }f k Nk � �0 1 íåîáõîäèìî Â.Ñ. Ãîäëåâñêèé, À.Ì. Äåíèñåíêî 40 ISSN 0204–3572. Electronic Modeling. 2013. V. 35. ¹ 3 âûïîëíèòü m N( / )2 óìíîæåíèé, à òàêæå 3 2 2 4 1 6( / ) (( / ) )N m N � îïå- ðàöèé ñëîæåíèÿ äëÿ ÷åòíûõ ãàðìîíèê è 3 2 2 4 1 4( / ) (( / ) )N m N � äëÿ íå÷åòíûõ. Òàêèì îáðàçîì, äëÿ ÏÄÏÔ ïðè èñïîëüçîâàíèè ôîðìóë (10)—(13) òðåáóåòñÿ ìåíüøåå ÷èñëî îïåðàöèé, ÷åì ïðè èñïîëüçîâàíèè ìåòîäà Ãåðöåëÿ. Ðàññìîòðèì ïðèìåíåíèå ÎÄÏÔ (3) äëÿ ðåøåíèÿ ðàñïðîñòðàíåííîé íà ïðàêòèêå çàäà÷è óçêîïîëîñíîé ÷àñòîòíîé ôèëüòðàöèè ñèãíàëîâ, êîãäà ïî ìàëîìó ÷èñëó m íåíóëåâûõ çíà÷åíèé ñïåêòðàëüíûõ ñîñòàâëÿþùèõ ñèãíàëà â ÷àñòîòíîé îáëàñòè îïðåäåëÿþòñÿ âñå N �1 çíà÷åíèÿ ñèãíàëà âî âðåìåííîé îáëàñòè.  ýòîì ñëó÷àå ôîðìóëà (3) äëÿ ïîëîñû S (7) ïðèìåò âèä � exp exf N F i kn N Fn k r r m k k N r m N r k� � � � � � � � � � � � 1 2 1 1 � p i kn N 2�� � � � � � � �� � � , n N� �0 1, ..., , (20) ãäå áåç îãðàíè÷åíèÿ îáùíîñòè ðàññóæäåíèé ïðåäïîëîæèì, ÷òî r �0. Ïî- ñêîëüêó èñõîäíàÿ ïîñëåäîâàòåëüíîñòü { , , ... , }f k Nk � �0 1 ÿâëÿåòñÿ äåéñò- âèòåëüíîé, ïðåîáðàçóåì (20) ê âèäó � Re cos Im sf N F kn N Fn k r r m k k r r m k� � � � � � � � � � � 1 2 2 2 1 1� in 2�kn N � � � � � � � �� � � , n N� �0 1, ..., . (21) Èçìåíèâ ïîðÿäîê ñóììèðîâàíèÿ âî âòîðîé ñóììå (20), � Re cos Im sf N F kn N Fn k r r m k k r r m k� � � � � � � � � � � 1 2 2 2 1 1� in ( )2� N k n N �� � � � � � � �� � � , n N� �0 1, ..., (22) è èñïîëüçîâàâ äëÿ (22) ñâîéñòâî (2), ïîëó÷èì � exp exp*f N F i kn N F i n k r r m k k r r m k� � � � � � � � � � � 1 2 1 1� 2�kn N � � � � � � � � � � � , n N� �0 1, ..., . (23) Çàïèøåì (23) â âèäå � exp expf N F i kn N F i n k r r m k k r r m k� � � � � � � � � � 1 2 2 1 1� �kn N � � � � � � � �� � � � � � � � � * , n N� �0 1, ..., . (24) Ñîêðàùåíèå âû÷èñëåíèé äëÿ áàçîâûõ äèñêðåòíûõ ïðåîáðàçîâàíèé Ôóðüå è Õàðòëè ISSN 0204–3572. Ýëåêòðîí. ìîäåëèðîâàíèå. 2013. Ò. 35. ¹ 3 41 Ïîñêîëüêó â (24) Im �f n �0, èç (24) íåïîñðåäñòâåííî ñëåäóåò ôîðìóëà (21) â âèäå � Re � Re cosf f N F kn N n n k r r m k k r r m � � � � � � � � � � � � 1 2 2 2 1 1� � � � � � � � �� � � Im sinF kn N k 2� , n N� �0 1, ..., . (25) Ñôîðìóëèðóåì óòâåðæäåíèå, àíàëîãè÷íîå óòâåðæäåíèþ 1, äëÿ îáùå- ãî ñëó÷àÿ ÎÄÏÔ (3). Ýòî óòâåðæäåíèå âûòåêàåò èç ôîðìóëû (25) ÎÄÏÔ äëÿ îáùåãî ñëó÷àÿ: � Re � ( ) Re cosf f N F F F kn N n n n N k N k� � � � � � � �� � 1 1 2 2 0 2 1 2 1 � � � � � � � � � � � � � � � � � 2 2 1 2 1 k N kF kn N Im sin � , n N� �0 1, ..., . Óòâåðæäåíèå 2. Åñëè â (3) N äåëèòñÿ áåç îñòàòêà íà ÷åòûðå, òî ÎÄÏÔ (3) äëÿ äåéñòâèòåëüíîé ïîñëåäîâàòåëüíîñòè { , ,..., }f k Nk � �0 1 ìîæíî ïðåäñòàâèòü â âèäå f N F F F F Fl N l N k N k N k 2 0 2 4 1 4 1 2 1 2 1 2� � � � � � ( ) Re Re Re ( / ) � � � � � � � � � � � � � � � cos 4�kl N � � � � � � � � � � � � � � � � � � 2 4 1 4 1 2k N k N k F F kl N ( / ) Im Im sin � , (26) f N F F F F Fl N l N k N k N2 1 0 2 4 1 4 1 2 1 2 1 2 � � � � � � � ( ) Im Re Re ( / ) k kl N � � � � � � � � � � � � � � � � cos 4� � � � � � � � � � � � � � � � � � 2 4 1 4 1 2k N k N k F F kl N ( / ) Im Im sin � , (27) ãäå l N� �0 2 1, ...,( / ) . Ä î ê à ç à ò å ë ü ñ ò â î óòâåðæäåíèÿ 2 âûïîëíÿåòñÿ ñ ïîìîùüþ òàêèõ æå ïðèåìîâ, êàê è äîêàçàòåëüñòâî óòâåðæäåíèÿ 1. Èç óòâåðæäåíèÿ 2 ñëåäóåò, ÷òî äëÿ âû÷èñëåíèÿ m0 âðåìåííûõ çíà- ÷åíèé ÎÄÏÔ (3) íåîáõîäèìî âûïîëíèòü m N0 ñëîæåíèé è m N 0 2 1 � � � � � óìíî- Â.Ñ. Ãîäëåâñêèé, À.Ì. Äåíèñåíêî 42 ISSN 0204–3572. Electronic Modeling. 2013. V. 35. ¹ 3 æåíèé. Ïðè âû÷èñëåíèè ÎÄÏÔ (20), â ñëó÷àå m íåíóëåâûõ çíà÷åíèé ñïåêòðàëüíûõ ñîñòàâëÿþùèõ ñèãíàëà â ÷àñòîòíîé îáëàñòè, äëÿ îäíîãî âðåìåííîãî îòñ÷åòà ÎÄÏÔ íåîáõîäèìî âûïîëíèòü N ñëîæåíèé è min ,2 3 2 1m N � � � � � óìíîæåíèé. Ïðè âû÷èñëåíèè m0 îòñ÷åòîâ (m0 1� ) ÎÄÏÔ öåëåñîîáðàçíî, êàê è â ñëó÷àå ÏÄÏÔ, ïðåäâàðèòåëüíî âû÷èñëèòü ñóììû, ñîäåðæàùèåñÿ â (26), (27) äëÿ k N� �1 4 1, ...,( ) . Òîãäà äëÿ âû÷èñëåíèÿ m0 îòñ÷åòîâ ÎÄÏÔ ïîòðåáóåòñÿ m m N 0 2 3 2 1min , � � � � � îïåðàöèé óìíîæåíèÿ è N N m � � � � � � 2 2 10( ) îïåðàöèé ñëîæåíèÿ. Èñïîëüçîâàíèå ñâîéñòâ ñèììåòðèè ôóíêöèé ïðè âû÷èñëåíèè ÄÏÕ. Ðàññìîòðèì ÄÏÕ (4), ïðåäñòàâèâ åãî â âèäå H H Hn n n� cos sin , n N� �0 1, ..., . (28) ãäå H N f kn N n k N kcos cos� � � � � � � � 1 2 0 1 � , H N f kn N n k N ksin sin� � � � � � � � 1 2 0 1 � . Äëÿ ïðåîáðàçîâàíèÿ (28) ñôîðìóëèðóåì óòâåðæäåíèå, àíàëîãè÷íîå óòâåðæäåíèþ 1. Óòâåðæäåíèå 3. Åñëè â (4) N äåëèòñÿ áåç îñòàòêà íà ÷åòûðå, òî äëÿ ÷åòíûõ ãàðìîíèê âõîäíîé äåéñòâèòåëüíîé ïîñëåäîâàòåëüíîñòè { ,f kk � � �0 1, ..., }N çàïèøåì H N f f f fl l N N N2 0 4 3 4 2 1 1cos ( )� � � � � � � � � � � � � � � � � � � � � � � � � � � k N k N k N k N kf f f f kl N1 4 1 2 2 4 cos � � � , H N f f f f fl l N N k N k N k N2 4 3 4 1 4 1 2 1 1sin ( )� � � � � � � � � � � � 2 4 �� � � � � � � � � � � � � � � � � � � k N kf kl N sin � , à äëÿ íå÷åòíûõ ãàðìîíèê âõîäíîé ïîñëåäîâàòåëüíîñòè — H N f f f f f fl N k N k N k N k N k2 1 0 2 1 4 1 2 2 1 � � � �� � � � � � � � � cos � � � � � � � � � � � � � cos ( )2 2 1�k l N , Ñîêðàùåíèå âû÷èñëåíèé äëÿ áàçîâûõ äèñêðåòíûõ ïðåîáðàçîâàíèé Ôóðüå è Õàðòëè ISSN 0204–3572. Ýëåêòðîí. ìîäåëèðîâàíèå. 2013. Ò. 35. ¹ 3 43 H N f fl l N N2 1 4 3 4 1 1 � � � � � � � � � � � �sin ( ) � � � � � � � � � � � � � k N k N k N k N kf f f f k l N1 4 1 2 2 2 2 1 sin ( )� � � � � � � , ãäå l N� �0 2 1, ...,( / ) . Ðàññìîòðèì äàëåå ÎÄÏÕ (6). Äëÿ çàäà÷è óçêîïîëîñíîé ÷àñòîòíîé ôèëüòðàöèè ñèãíàëîâ ñ ìàëûì ÷èñëîì m íåíóëåâûõ çíà÷åíèé ñïåêòðàëü- íûõ ñîñòàâëÿþùèõ ñèãíàëà â ÷àñòîòíîé îáëàñòè ôîðìóëà (6) äëÿ ïîëîñû S (7) ïðèìåò âèä f H kn N H k n k r r m k k N r m N r k� � � � � � � � � � � 1 1 2 2 cas cas � � n N � � � � � , n N� �0 1, ..., . (29) Äëÿ ÏÄÏÕ (4) â âèäå (28) ëåãêî óñòàíîâèòü ñëåäóþùåå ñâîéñòâî: H H HN n n n� � cos sin , n N � �0 2 1, ..., . (30) Ó÷èòûâàÿ (30), ìîæíî ïðåäñòàâèòü (29) â âèäå f H kn N Hn k r r m n k r r m n� � � � � � � � � � 2 2 2 1 1 cos sincos si � n 2�kn N � � � � � , n N� �0 1, ..., . Äëÿ îáùåãî ñëó÷àÿ ÎÄÏÕ (6) ïîëó÷èì f H H H kn N n n N k N n k N � � � � � � � � � � 0 2 1 2 1 1 2 1 2 2 2( ) coscos � � � � � � � 1 2 H kn N n sinsin � , n N� �0 1, ..., . Óòâåðæäåíèå 4. Åñëè N äåëèòñÿ áåç îñòàòêà íà ÷åòûðå, òî ÎÄÏÕ (6) ìîæíî ïðåäñòàâèòü â âèäå f H H H H Hl N l N k N k N k 2 0 2 4 1 4 1 2 2 1 2� � � � � ( ) cos ( / ) cos cos � � � � � � � � � � � cos 4�kl N � � � � � � � � � � � � � � � 2 4 1 4 1 2k N k N k H H kl N ( / ) sin sin sin � , Â.Ñ. Ãîäëåâñêèé, À.Ì. Äåíèñåíêî 44 ISSN 0204–3572. Electronic Modeling. 2013. V. 35. ¹ 3 f H H H H Hl N l N k N k N k 2 1 0 2 4 1 4 1 2 2 1 2 � � � � � � � ( ) sin ( / ) cos cos cos � � � � � � � � � � � 4�kl N � � � � � � � � � � � � � � 2 4 1 4 1 2k N k N k H H kl N ( / ) sin sin sin � , äëÿ l N� �0 2 1, ...,( / ) . Èç óòâåðæäåíèé 3 è 4 ñëåäóåò, ÷òî ÷èñëî îïåðàöèé ñëîæåíèÿ è óìíî- æåíèÿ ïðè ðàñ÷åòàõ äëÿ ÏÄÏÕ è ÎÄÏÕ ñîâïàäåò ñ ÷èñëîì îïåðàöèé ñëîæåíèÿ è óìíîæåíèÿ äëÿ ÏÄÏÔ è ÎÄÏÔ.  íåêîòîðûõ ñëó÷àÿõ, â ÷àñòíîñòè, êîãäà íåîáõîäèìî àíàëèçèðîâàòü äîñòàòî÷íî óçêóþ ïîëîñó ÷àñòîò (m N� / 4), äëÿ óìåíüøåíèÿ ÷èñëà îïåðà- öèé ñëîæåíèÿ ìîæíî èñïîëüçîâàòü ÄÏÕ (4), ïðèâåäåííîå ê âèäó H N f kn N n k N k� �� � � � � � � 1 2 40 1 cos � � , n N� �0 1, ..., . (31) Äëÿ (31) ñïðàâåäëèâî ñëåäóþùåå óòâåðæäåíèå. Óòâåðæäåíèå 5. Åñëè â (31) N äåëèòñÿ íà äâà, òî H N f f f fn n N k N k n N k � � � � � � � � � � �� � 1 2 2 1 10 2 1 2 1 2 ( ) ( )� � � � �� � � � � � � � � � � � cos 2 4 � �kn N (32) äëÿ n N� �0 1, ..., . Ä î ê à ç à ò å ë ü ñ ò â î óòâåðæäåíèÿ 5 ñâîäèòñÿ ê ïîèñêó òàêèõ òî÷åê p, äëÿ êîòîðûõ cos cos 2 4 2 4 � � � �kn N pn N �� � � � � � �� � � � � (33) èëè cos cos 2 4 2 4 � � � �kn N pn N �� � � � � � � �� � � � � . (34) Ïðè p N k� 2 ðàâåíñòâî (33) âûïîëíÿåòñÿ äëÿ ÷åòíûõ, à ðàâåíñòâî (34) — äëÿ íå÷åòíûõ çíà÷åíèé n, â ÷åì ìîæíî óáåäèòüñÿ, ïîäñòàâèâ p N k� 2 â (33) è (34). Ýòî è ÿâëÿåòñÿ äîêàçàòåëüñòâîì óòâåðæäåíèÿ 5. Ñîêðàùåíèå âû÷èñëåíèé äëÿ áàçîâûõ äèñêðåòíûõ ïðåîáðàçîâàíèé Ôóðüå è Õàðòëè ISSN 0204–3572. Ýëåêòðîí. ìîäåëèðîâàíèå. 2013. Ò. 35. ¹ 3 45 Èç óòâåðæäåíèÿ 5 ñëåäóåò, ÷òî åñëè êîñèíóñû â (32) âû÷èñëåíû çàðà- íåå, òî ïðè ôèêñèðîâàííîì çíà÷åíèè n äëÿ âû÷èñëåíèÿ ÄÏÕ íåîáõîäèìî âûïîëíèòü N ñëîæåíèé è ( )N 2 1 óìíîæåíèé. Àíàëîãè÷íûé ïîäõîä ìîæ- íî ïðèìåíèòü è äëÿ ÎÄÏÕ (6). Îòñå÷åíèå íóëåâûõ ýëåìåíòîâ â èçâåñòíûõ àëãîðèòìàõ ÁÏÔ. Èç- âåñòíû ìîäèôèêàöèè àëãîðèòìîâ ÁÏÔ, ïðåäíàçíà÷åííûå äëÿ ðåøåíèÿ ðàçëè÷íûõ ïðàêòè÷åñêèõ çàäà÷ öèôðîâîé îáðàáîòêè ñèãíàëîâ ïðè íàëè- ÷èè áîëüøîãî ÷èñëà íóëåâûõ ýëåìåíòîâ âî âõîäÿùèõ ïîñëåäîâàòåëüíîñòÿõ êàê ÏÄÏÔ, òàê è ÎÄÏÔ. Ìîäèôèêàöèþ áûñòðûõ àëãîðèòìîâ, íàïðàâëåííóþ íà èñêëþ÷åíèå èç âû÷èñëåíèé íóëåâûõ ýëåìåíòîâ ïðèíÿòî íàçûâàòü îòñå÷å- íèåì íóëåâûõ ýëåìåíòîâ (pruning) [9].  ðàáîòå [9] âíåñåíû èçìåíåíèÿ â ÁÏÔ-àëãîðèòì, ïðåäëîæåííûé â [10], ñîñòîÿùèå â èñêëþ÷åíèè èç âû÷èñ- ëåíèé íóëåâûõ áàáî÷åê íà êàæäîì óðîâíå âû÷èñëåíèÿ ÁÏÔ, ïðè ýòîì ÷èñëî óðîâíåé îñòàåòñÿ ïîñòîÿííûì.  ðàáîòå [11] ïîêàçàíî, ÷òî ïðè ïðîñòîì èçìåíåíèè ÁÏÔ-àëãîðèòìà ïî îñíîâàíèþ äâà ñ ïðîðåæèâàíèåì ïî âðåìåíè ïðèáëèçèòåëüíûé îòíîñè- òåëüíûé âûèãðûø ïî âðåìåíè ñîñòàâëÿåò t N m N s � �log log log 2 2 2 , ãäå N — îáùåå ÷èñëî òî÷åê ïðåîáðàçîâàíèÿ, ñðåäè êîòîðûõ òîëüêî m — íåíóëåâûå.  ðàáîòå [12] îáëàñòü îòñå÷åíèÿ íóëåâûõ ýëåìåíòîâ ÁÏÔ ðàñøèðåíà íà ñëó÷àé, êîãäà ÷èñëî òðåáóåìûõ îòñ÷åòîâ ðåçóëüòèðóþùåé ïîñëåäîâà- òåëüíîñòè m0 ìåíüøå ÷èñëà òî÷åê ïðåîáðàçîâàíèÿ N. Ïðè ýòîì óòâåðæ- äàåòñÿ, ÷òî äëÿ àëãîðèòìîâ, îïèñàííûõ â [9, 11], îáùèé îòíîñèòåëüíûé âûèãðûø ïî ÷èñëó îïåðàöèé ïðè íàëè÷èè íóëåé êàê â èñõîäíîé, òàê è â ðåçóëüòèðóþùåé ïîñëåäîâàòåëüíîñòè ñîñòàâëÿåò t N m m m N N mm N s � � � � �� � � � � � 2 2 12 2 2 0 0 2 0 log log log log ïðè , log log ( ) log . 2 2 0 2 0 2 1N m m N m N mm N � � � � � � � � � � � � � ïðè (35) Ðàññìîòðèì ïîäðîáíåå àëãîðèòì îòñå÷åíèÿ íóëåâûõ ýëåìåíòîâ â ÁÏÔ [12]. Îáîçíà÷èì ÷åðåç M R0 ÁÏÔ è AR0 ÁÏÔ ñîîòâåòñòâåííî ÷èñëî îïåðàöèé óìíîæåíèÿ è ñëîæåíèÿ ÁÏÔ äëÿ ýòîãî àëãîðèòìà. ×åðåç M R0 ÄÏÔ è AR0 ÄÏÔ Â.Ñ. Ãîäëåâñêèé, À.Ì. Äåíèñåíêî 46 ISSN 0204–3572. Electronic Modeling. 2013. V. 35. ¹ 3 îáîçíà÷èì ÷èñëî îïåðàöèé óìíîæåíèÿ è ñëîæåíèÿ â ÄÏÔ, îïòèìèçèðî- âàííîãî ñ ó÷åòîì èñêëþ÷åíèÿ íóëåâûõ ýëåìåíòîâ. Ñëåäóÿ [12], íàõîäèì A A N m m N m N m mR R0 0 0 27 1ÁÏÔ ÁÏÔ� � � ( , , ) (log ) �� �� � �� � � � � 7 2 5 2 2 0 1 2 01 1 2 1i N m m j i i m i N j log log log log , 2 0 1 2 N j N i N j � �� �� � �� (36) M M N m m N m mR R0 0 0 24 1ÁÏÔ ÁÏÔ� � � ( , , ) (log ) �� �� � �� � � � � 4 2 2 2 0 1 2 01 1 2 1i N m m j i i m i N j log log log log2 0 1 2 N j N i N j � �� �� � �� � � � � � � � , (37) ãäå[ ] — îïåðàöèÿ âçÿòèÿ öåëîãî ÷èñëà. Èç (36) è (37), à òàêæå óòâåðæäåíèé 1 è 2 ñëåäóåò, ÷òî ïðè îïðåäåëåííûõ çíà÷åíèÿõ m, m0 M MR R0 0 ÄÏÔ ÁÏÔ� , A AR R0 0 ÄÏÔ ÁÏÔ� . Ñðàâíèâàÿ ÷èñëî îïåðàöèé ñëîæåíèÿ è óìíîæåíèÿ äëÿ ÁÏÔ èç ðàáîòû [12] è ÄÏÔ ïðè m N� �1024 è ðàçëè÷íûõ çíà÷åíèÿõ m0, ïðèâåäåííîå â òàáëèöå, ìîæíî ñäåëàòü âûâîä î öåëåñîîáðàçíîñòè èñïîëüçîâàíèÿ îïèñàí- íûõ ìîäèôèêàöèé ÄÏÔ ïðè îòíîñèòåëüíî íåáîëüøèõ çíà÷åíèÿõ m0. Ñîêðàùåíèå âû÷èñëåíèé äëÿ áàçîâûõ äèñêðåòíûõ ïðåîáðàçîâàíèé Ôóðüå è Õàðòëè ISSN 0204–3572. Ýëåêòðîí. ìîäåëèðîâàíèå. 2013. Ò. 35. ¹ 3 47 m0 AR 0 ÁÏÔ, AR 0 OÁÏÔ MR 0 ÁÏÔ, MR 0 OÁÏÔ AR 0 OÄÏÔ MR 0 OÄÏÔ AR 0 ÄÏÔ ïðè çíà÷åíèÿõ ãàðìîíèêè MR 0 ÄÏÔ ÷åòíûõ íå÷åòíûõ 1 6 139 4 092 1 024 513 2 052 2 050 512 2 9 718 6 136 2 048 1 026 2 562 2 560 1 024 4 13 292 8 176 4 096 2 052 3 582 3 580 2 048 8 16 856 10 208 8 192 4 104 5 622 5 620 4 096 16 20 400 12 224 16 384 8 208 9 702 9 700 8 192 32 23 904 14 208 32 768 16 416 17 862 17 860 16 384 64 27 328 16 128 65 536 32 832 34 182 34 180 32 768 Âûâîäû Ïðåäñòàâëåííûå àëãîðèòìû ÄÏÔ è ÄÏÕ äàþò âîçìîæíîñòü óìåíüøèòü ÷èñëî òðåáóåìûõ îïåðàöèé ïî ñðàâíåíèþ ñ èçâåñòíûìè àëãîðèòìàìè ÁÏÔ è ÁÏÕ ïðè áîëüøèõ çíà÷åíèÿõ îòíîøåíèé ðàçìåðíîñòåé ìàññèâîâ âõîäíûõ èëè âûõîäíûõ ñèãíàëîâ ê ÷èñëó íåíóëåâûõ ýëåìåíòîâ â ýòèõ ìàññèâàõ. The authors perform algorithms based on the account of zero elements in the arrays of input and output signals. The use of these signals ensures the reduction of calculations of the Fourier direct and inverse base discrete transformation and Hartley direct base transformation. ÑÏÈÑÎÊ ËÈÒÅÐÀÒÓÐÛ 1. Ðàáèíåð Ë., Ãîóëä Á. Òåîðèÿ è ïðèìåíåíèå öèôðîâîé îáðàáîòêè ñèãíàëîâ. — Ì. : Ìèð, 1978. — 848 ñ. 2. Áëåéõóò Ð. Áûñòðûå àëãîðèòìû öèôðîâîé îáðàáîòêè ñèãíàëîâ. —Ì. : Ìèð, 1989. — 448 ñ. 3. Áðåéñóýëë Ð. Ïðåîáðàçîâàíèå Õàðòëè. — M. : Ìèð, 1990. — 175 ñ. 4. Ïðàäî Æ. Çàìå÷àíèå ê ñòàòüå «Áûñòðîå ïðåîáðàçîâàíèå Õàðòëè» // ÒÈÈÝÐ. — 1985. — 73, ¹ 12. — Ñ. 182—183. 5. Ñåðãååâ Â.Â, Óñà÷åâ À.Â. Íîâûé àëãîðèòì áûñòðîãî ïðåîáðàçîâàíèÿ Õàðòëè // Êîìïüþ- òåðíàÿ îïòèêà, 1990, Âûï.7. — Ñ. 66—67. 6. Àäàïòèâíûå ôèëüòðû. Ïîä ðåä. Êîóýíà Ê.Ô., Ãðàíòà Ï.Ì. — Ì. : Ìèð, 1988. — 388 ñ. 7. Ãîäëåâñêèé Â.Ñ., Äåíèñåíêî À.Ì. Ìåòîäè÷åñêèå ïîãðåøíîñòè äèñêðåòíîãî ïðåîáðà- çîâàíèÿ Ôóðüå è ñïîñîáû èõ êîìïåíñàöèè// Ýëåêòðîí. ìîäåëèðîâàíèå. — 2006. — 28, ¹ 3. — Ñ. 83 — 98. 8. Ãîäëåâñêèé Â.Ñ., Äåíèñåíêî À.Ì. ×èñëåííûé ñèíòåç îêîííûõ ôóíêöèé äëÿ äèñêðåòíî- ãî ïðåîáðàçîâàíèÿ Ôóðüå // Ýëåêòðîí. ìîäåëèðîâàíèå. — 2006. — 28, ¹ 4. — Ñ. 75 — 87. 9. Markel J.D. FFT pruning // IEEE Trans. Audio Electroacoust. — 1971. — Vol. AU-19. — P. 305—311. 10. Gentleman W.M., Sandle G. Fast Fourier transforms for fun and profit // AFIPS Conf. Proc. — Washington, D. C. : Spartan, 1966. — Vol. 29. — P. 563—578. 11. Skinner D.P. Prunning the decimation-in-time FFT algorithm // IEEE Trans. Acoust., Speech, Signal Processing. — 1976. — Vol. ASSP-24. — P. 193—194. 12. Sreenivas T.V., Rao P.V.S. FFT algorithm for both input and output pruning// Ibid. — 1979. Vol. ASSP-27. — P. 291—292. Ïîñòóïèëà 27.12.12 ÃÎÄËÅÂÑÊÈÉ Âèòàëèé Ñòàíèñëàâîâè÷, ä-ð òåõí. íàóê, äèðåêòîð ãîñóäàðñòâåííîãî ïðåä- ïðèÿòèÿ «ÄÈÑÈÒ» ÍÀÍ Óêðàèíû.  1986 ã. îêîí÷èë Õàðüêîâñêèé ïîëèòåõíè÷åñêèé èí-ò. Îáëàñòü íàó÷íûõ èññëåäîâàíèé — ìîäåëèðîâàíèå, îïòèìèçàöèÿ ðåæèìîâ è äèàãíîñòèêà òðó- áîïðîâîäíûõ ñèñòåì, àíàëîãîâàÿ è öèôðîâàÿ îáðàáîòêà ñèãíàëîâ. ÄÅÍÈÑÅÍÊÎ Àëåêñàíäð Ìèõàéëîâè÷, êàíä. ôèç.-ìàò. íàóê, íàó÷. ñîòð. ãîñóäàðñòâåííîãî ïðåäïðèÿòèÿ «ÄÈÑÈÒ» ÍÀÍ Óêðàèíû.  2000 ã. îêîí÷èë Êèåâñêèé íàöèîíàëüíûé óíèâåðñèòåò èì. Ò. Øåâ÷åíêî. Îáëàñòü íàó÷íûõ èññëåäîâàíèé — öèôðîâàÿ îáðàáîòêà ñèãíàëîâ. Â.Ñ. Ãîäëåâñêèé, À.Ì. Äåíèñåíêî 48 ISSN 0204–3572. Electronic Modeling. 2013. V. 35. ¹ 3

Ähnliche Einträge