§ 10. Преобразования Хартли

Из того, что было сказано в § 9, следует, что при соответствующих условиях оказываются эффективными не только преобразования цифровых сигналов, выполняемые при применении тригонометрических функций в качестве базисных, но и иные. Это будет подтверждено и тем, чему посвящается следующая гл. IV. Если же иметь в виду использование в качестве базисных тригонометрических функций, то кроме преобразований Фурье находят применение и другие преобразования, например косинусное преобразование, описываемое в п. Ж. § 8 гл. V. Приводимые в этой книге сведения о преобразованиях Фурье и других преобразованиях цифровых сигналов должны приниматься во внимание и при рассмотрении преобразований сигналов, известных сейчас как преобразования Хартли, первые сообщения о которых лишь недавно появились в печати.

Тригонометрические функции являются тоже базисными для преобразований Хартли. Но образуются они иначе, чем функции, являющиеся базисными для преобразований Фурье, о которых было сказано в § 2 гл. III. Базисными для преобразований Хартли являются функции вида для которых принято обозначение Первая и последняя буквы в указывают на то, что берется сумма

Далее приведем описание преобразований Хартли и отметим условия, при которых дает преимущества их применение. Но сначала скажем несколько слов об истории создания преобразований этого вида. Еще в 1942 г. американским ученым P. B. Л. Хартли было указано на возможность использования строго взаимных интегральных преобразований, отличающихся от преобразований фурье тем, что все операции выполняются с вещественными числами без обращения к комплексным величинам. За последующие сорок с лишним лет этот вид преобразований не привлекал к себе внимания специалистов по цифровой обработке сигналов. Но в 1984 г. был опубликован предложенный Р.Н. Брейсуэллом алгоритм быстрого преобразования такого вида, с созданием которого оказалось возможным эффективное его использование. Брейсуэллом рассматриваемое преобразование было названо преобразованием Хартли в память о P. B. Л. Хартли. Алгоритм указанного выше быстрого преобразования был, однако, запатентован под названием алгоритма Брейсуэлла, и преобразование Хартли называют также преобразованием Хартли-Брейсуэлла. В появившихся публикациях для дискретного преобразования Хартли и для быстрого его варианта используются по аналогии с ДПФ и БПФ обозначения ДПХ и БПХ. Мы этими обозначениями пользоваться не будем, так как они приняты для рассматриваемых в гл. IV преобразований Хаара, не связанных с преобразованиями Хартли.

Ниже приводятся краткие сведения о дискретных преобразованиях Хартли и быстрое преобразование Хартли сравнивается с БПФ. Более подробно все это освещено в работе [17] и в работах, упоминаемых далее в гл. V и указанных в дополнительном списке работ, опубликованных в 1987-1988 гг. (попутно заметим, что первая публикация Брейсуэлла о Дискретных преобразованиях Хартли появилась в декабре 1983 г., но, как было указано, соответствующее быстрое преобразование подробно описано лишь в работе [17]).

Приводя формулы дискретных прямого и обратного преобразований Хартли, напомним, что для ДПФ и ОДПФ использовались аналогичные по своей структуре формулы (3.36) и (3.37).

Для последовательностей N вещественных чисел , каждое из которых соответственно принимает значения преобразование Хартли

а обратное преобразование Хартли

где по определению

Алгоритм быстрого преобразования Хартли аналогичен алгоритму БПФ, хотя в этом случае обработка данных производится в другом порядке. Схема выполнения быстрого преобразования Хартли для восьмиточечной последовательности приведена на рис. 3.17, для которого приняты следующие обозначения: 1 — операция, названная перестановкой; 2 — операция, названная объединением; 3 — линии передачи сигналов при линии перадачи сигналов при указанных выше значениях (обозначения приняты в общем соответственно для где номер шага преобразований). При описании рассматриваемой схемы выполнения быстрых преобразований в работе [17] отмечено, что, "как и в случае БПФ, цель перестановки элементов состоит в пошаговом делении пополам последовательности данных, что в результате дает совокупность пар чисел".

Рис. 3.17

В этом отношении процедура быстрого преобразования Хартли аналогична той, которая для БПФ иллюстрировалась у нас с помощью рис. 3.6. При показанном на рис. 3.17 быстром преобразовании, выполняя операцию объединения данных, имеют дело с тремя группами входных переменных и одной группой выходных переменных по восемь в каждой, причем первая выходная переменная получается как сумма первых элементов всех трех входных групп и аналогичным же образом формируются и другие выходные переменные. Возвращаясь к формулам (3.117) и (3.118), заметим, что мы ввели множитель вторую из них с тем, чтобы сохранилась аналогия с формулами (336) и (3.37) для ДПФ;

в работе [17], в которой приведен рассматриваемый сейчас нами рисунок, множитель имеется в первой формуле, однако это не имеет принципиального значения.

Для, -точечной последовательности примем следующие обозначения: -точечная -последовательность, имеющая дискретное преобразование Хартли -точечная -последовательность, имеющая дискретное преобразование Хартли Общая формула разложения Хартли имеет при этом следующий вид:

где соответственно равны (вывод этой формулы приведен в [17]).

Если не приходится иметь дело с комплексными числами, то преобразование Хартли оказывается более экономным по времени, так как все операции с вещественными числами как при прямом, так и при обратном преобразованиях, выполняемых к тому же единообразно, производятся несколько быстрее, чем при описанном в § 5 гл. III преобразовании Фурье. Экономия времени обработки информации получается и благодаря особому построению иллюстрируемого на рис. 3.17 алгоритма быстрого преобразования. При выполнении первых двух этапов, следующих за операцией перестановки, косинусные и синусные множители в формуле (3.119) принимают только значения или 1, или —1. Передача сигналов, показанная для этих этапов на рис. 3.17 сплошными линиями, производится без их изменения, а передача сигналов, показанная прерывистыми линиями, с их инвертированием. В этой части преобразование производится так же, как и преобразования, рассматриваемые нами в гл. IV, которые в ряде случаев оказываются более экономными, чем преобразования Фурье и Хартли. На следующем этапе иллюстрируемого рис. 3.17 преобразования двум третям ветвей отвечают косинусные и синусные множители, часть которых тоже равна 0 или 1, или — 1.

Преобразования Хартли тесно связаны с преобразованиями Фурье. По существу, описанный выше алгоримт быстрого вычисления преобразования Хартли основан на БПФ. Возможны переходы от одного из этих преобразований к другому. Вещественная и мнимая части преобразования Фурье равны соответственно четной и взятой со знаком минус нечетной частям преобразования Хартли. Появились и публикации, указывающие методы перехода от БПФ к быстрым преобразованиям Хартли (см., например, [150]). Преобразование Хартли связано и с другими рассматриваемыми в нашей книге преобразованиями сигналов. Так, для быстрого вычисления дискретного преобразования Хартли начинает использоваться описываемое нами в следующей главе преобразование Уолша-Адамара (см. источник [44] в дополнительном списке литературы).

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

т. е. дискретное преобразование Хартли от свертки функций указанного типа равно произведению дискретных преобразований Хартли от самих функций. Если функция несимметричная, то, как показано в работе [17], в выражении свертки появляется второе слагаемое, причем получаемое при этом выражение свертки "непосредственно выводится из теоремы свертки для ДПФ". И здесь проявляется тесная связь между дискретными преобразованиями Хартли и Фурье. Было бы разумным вообще рассматривать создание преобразований Хартли как один из этапов развития теории преобразований Фурье.

Заканчивая краткое изложение основных сведений о преобразованиях Хартли, отметим, что в касающихся их публикациях появились не обнаруживавшиеся ранее во всей рассматриваемой нами области науки и техники ноты рекламы и коммерции. В указывавшейся работе [17] правомерно говорится о том, что быстрое преобразование Хартли "можно выполнять за то же время, что и БПФ, а в ряде случаев и быстрее. Реальный выигрыш времени зависит от выполнения определенных условий ...", и в связи с этим Справедливо отмечается то, что "в ряде случаев дискретное преобразование Хартли представляет собой удобную замену дискретного преобразования Фурье (ДПФ) ". Однако опубликованное в 1987 г. в американском журнале "В мире науки" сообщение о преобразовании Хартли (см. источник [24] в дополнительном списке литературы) уже вышло под общим заголовком "На смену преобразованию Фурье", хотя и здесь оговорено, что возможно лишь то, что это будет так, как указано в заголовке. В конце статьи Брейсуэлла [17] приведено также непривычное для специалистов указание, касающееся представленной в статье программы выполнения быстрого преобразования Хартли. Написано, что "самостоятельное копирование, а также прямое или косвенное использование программы для расчетов на ЭВМ запрещено. За информацией о выдаче липензий следует обращаться в Отдел технических лицензий Сганфордского университета".