Брейсуэлл, Р. Преобразование Хартли. Теория и приложения ... Р. Брейсуэлл; Пер. А. И. Папков; Ред. И. С. Рыжак. - М. : Мир, 1990. - 175 с.

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

Для специалистов, занимающихся проблемами обработки сигналов и спектрального I также аспирантов и студентов старших курсов соответствующих специальностей.

ПРЕДИСЛОВИЕ РЕДАКТОРА ПЕРЕВОДА

Предлагаемая вниманию советского читателя книга профессора Станфордского университета принадлежит к оксфордской серии по техническим наукам и является нервой в мировой литературе монографией, посвященной преобразованию Хартли. Как и преобразование Фурье, оно может применяться для спектрального анализа и различных видов обработки сигналов. Данный вид преобразования назван в честь Р. Хартли, опубликовавшего в 1942 г. статью о паре интегральных преобразований-прямом и обратном,-использующих введенную им функцию cas 0 = sin 0 + cos 0. До начала 1980-х годов эти результаты оставались в забвении, пока к ним не привлек внимание исследователей Р. Брейсуэлл, разработавший основы теории как непрерывного, так и дискретного преобразования Хартли, а также один из вариантов его быстрого преобразования.

Непрерывный прогресс в области обработки информации связан с задачами всевозрастающей сложности. Такие задачи желательно решать в реальном или текущем времени (т. е. достаточно быстро) ц одновременным применением экономичных методов и средств реа-лйзЗЦИбГ Быстро действие и экономичность достигаются как развитием технологии и организацией средств обработки (СБИС, процессоры сложной архитектуры с высокой степенью распараллеливания и т. п.), так и совершенствованием алгоритмов обработки сигналов.

Обращение к преобразованию Хартли обусловлено ситуацией, сложившейся в ряде методов обработки информации, в частности использующих вещественные последовательности данных (одномерных и двумерных). Обработку таких данных желательно осуществлять в области вещественных чисел с помощью взаимно симметричных прямого и обратного преобразований. В отличие от преобразования Фурье, отображающего вещественные функции в комплексную область, и несимметричного по i (происходит изменение знака при переходе от прямого к обратному преобразованию) преобразование Хартли осуществляет прямое и обратное преобразования только в вещественной области и обладает указанной симметрией.

Книга написана в сжатой, компактной форме, но очень информативна, так как содержит изложение всех основных аспектов непрерывного и дискретного одномерного и двумерного преобразований Хартли. Такой стиль изложения требует от читателя особого внимания и усилий, однако он будет вознагражден, получив взамен богатство идей.

В настоящее время преобразование Хартли находит широкое применение при разработке двумерных и трехмерных быстрых преобразований, быстрых алгоритмов интерполяции и т.д.

ВВЕДЕНИЕ

- Вы, уж верно, знаете латынь?

- Да, но вы говорите так, как будто я ее не знаю.

Мольер. Мещанин во дворянстве

Гармонический анализ, в который вносит вклад данная книга, имеет удивительную историю, у истоков которой стоял, как часто считается, Жан Батист Жозеф Фурье (1768-1830), известный своим утверждением о том, что произвольная функция может быть представлена в виде тригонометрического ряда. Много работ как в математике, так и в физике было посвящено попыткам опровергнуть это утверждение. Часть достижений XIX в. в области математического анализа, который оперирует такими основополагающими понятиями, как непрерывность и предел, ставшими на сегодняшний день традиционными, возникли в связи с проблемами рядов Фурье. Что касается физики, то достаточно привести мнение лорда Кельвина: «Теорема Фурье-это не только один из наиболее блестящих результатов в современном математическом анализе, но и необходимый инструмент анализа почти всякого неясного вопроса в современной физике».

Достаточно рассмотреть формулу jt/2 = sin х — 7г sin 2х + 7з sin Зх + ...,

полученную Леонардом Эйлером (1707-1783), чтобы осознать тот факт, что в эволюционном процессе всегда есть предшественники. В подтверждение можно привести пример из II в. н. э., когда Клавдий Птолемей (грек из Александрии) использовал эту же основную идею. Тригонометрическая сумма вида z(0 = ах exp [itoj (г - гх)] + а2 ехр [гю2 (t - г2)] + + а3 ехр[гю3(г - г3)] + ...

является в конечном счете только комплексным представлением суммы вращающихся векторов, которая также может быть охарактеризована траекторией точки, движущейся по эпициклу, вращающемуся в свою очередь по деференту, центр которого перемещается по третьей окружности. Восходящая к древности идея включения дополнительного вращающегося вектора с его амплитудой, частотой и фазой необходима, чтобы лучше объяснить данные наблюдений, и лежит в основе метода расчета положений планет, который используется и поныне. Нововведением Фурье было утверждение об общем характере представления в виде суммы компонент с кратным соотношением угловых скоростей. Как известно, это утверждение встретило решительное сопротивление со стороны выдающихся французских математиков того времени, которые вполне справедливо требовали убедительных доказательств. В конце концов спор свелся к вопросу о необходимых и достаточных условиях существования интеграла Фурье, дискуссия вокруг которого длилась более столетия. Ее кульминацией явилась разработка методов анализа обобщенных функций, что все расставило по своим местам.

Теория функций комплексной переменной существенно облегчила трактовку колебательных процессов. (Анализ переменных токов сегодня немыслим без использования комплексной плоскости и множителя ехр [г'юг].) Следовательно, в теории рядов Фурье используется преимущество теории функций комплексной переменной и оказывается естественным анализ периодической функции р (е) с помощью комплексных компонент с„ ехр [йяя/], где коэффициент с„ является теперь комплексным. Таким образом, имеем

p(t) = £ ся ехр [йяи/] ,

и в пределе для функции f(t), не являющейся периодической, справедливо выражение

fit) = ] F(n) ехр ii2nnt]dn,

где и-вещественное число.

В то же время хорошо известно, что можно записать соответствующее выражение для ряда без использования мнимой единицы к

p(t) = а0 + £ («„ cos 2тint + b„ sin 2nnt),

Л=1

что и утверждал Фурье, таким образом, понятно, что использование комплексных экспонент является скорее удобной формой представления, нежели фундаментальным свойством.

Вещественное интегральное преобразование, сформулированное Хартли в 1942 г., позволяет обойтись без комплексного представления. Хотя его результат занял заметное место на страницах журнала Proceedings of the Institute of Radio Engineers (Труды Института радиоинженеров) и на него были ссылки в таких монографиях, как S. Goldman. Frequency Analysis, Modulation and Noise, McGraw-Hill, 1948 (имеется перевод: Гольдман С. Гармонический анализ, модуляция и шумы.-М.: ИЛ, 1951) и в моей книге R. N. Bracewell. The Fourier Transform and Its Applications, McGraw-Hill, 1965 (P. Брейсуэлл. Преобразование Фурье и его применения), возобладала традиционная инерция. Вероятно, можно было бы найти более ранние, но оставленные без внимания публикации.

В гл. 2 представлено преобразование Хартли с использованием функции cas и связь с преобразованием Фурье, по аналогии с которым соотношение

Н{я) = I /(Х)С<15 211зхс1Х

определяется как преобразование Хартли. В гл. 3 в сжатой форме без вывода приводятся теоремы для преобразования Хартли.

Дальнейшим расширением является определение дискретного преобразования Хартли:

N-1 ' .

Я(у) = N'1 £ Ш сая (2тт/Л0,

т = 0

свойства которого исследуются в гл. 4. Коэффициент ЛГ"1 обеспечивает равенство Н(0) среднему значению /(т); это свойство полностью соответствует исходной посылке о том, что коэффициент а0 равен постоянной составляющей периодического колебания.

Основной областью применения преобразования Хартли является цифровая фильтрация, или дискретная свертка,-тема гл. 5.

Наличие изображений, воспроизводимых или обрабатываемых на ЭВМ и отображаемых на экранах электронно-лучевых трубок, в значительной степени расширило область применения двумерного анализа, причем обнаружилось, что идея вещественного преобразования легко обобщается. Таким образом, можно получить преобразование плоскости, обеспечивающее взаимно однозначное соответствие (прямое и обратное) с другой плоскостью, на которой определен некоторый объект. Плоскость преобразования Хартли, если можно ее так назвать, помимо того, что значения, соответствующие каждой точке, вещественны, характеризуется отсутствием избыточности. В плоскости преобразования Фурье, напротив, эти величины комплексны, а значения в диаметрально противоположных точках образуют комплексно сопряженные пары. Двумерное преобразование Хартли вводится в гл. 6, где приводятся многие теоремы в обобщенной форме.

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

Гл. 8 посвящена быстрому алгоритму. Рассматриваются различные интересные аспекты быстрого спектрального анализа. Показано, каким образом практически реализуемые программы разбиваются на ряд отдельных частей, каждая из которых вносит вклад в общее время счета (машинное время) й характеризуется определенной зависимостью от анализируемой последовательности данных. Рассмотрение выходит за рамки традиционного анализа сложности и трудоемкости, выполняемого путем приближенного подсчета количества операций, и предполагает использование временной (или полосковой) диаграммы, характеризующей зависимость разбиений от объема последовательности данных. Затем специально внимание уделяется каждой полосе и делаются важные заключения относительно быстрых тригонометрических функций, быстрого вращения и быстрой перестановки. Основой нового алгоритма является вещественное преобразование, которое требует в 2 раза меньше машинного времени, чем комплексное преобразование Фурье.

Хорошо известно, что системы оптических линз могут формиро- " вать преобразование Фурье когерентного оптического излучения источника, и поэтому естествен вопрос о значении достижений последнего времени в этой области для оптики. Был предложен метод " формирования двумерного вещественного представления, который рассматривается в гл. 9. На плоскости вещественного преобразования компоненты электрического поля находятся в фазе; следовательно, распределение информации полностью характеризуется изменениями амплитуд. В полном объеме результаты и последствия подобной независимости от параметра фазы, к которому невосприимчивы детекторы электромагнитного излучения короче некоторой длины волны, еще ждут исследования.

Книга завершается набором программ для ЭВМ и атласом преобразований Хартли, которые призваны оказать помощь лицам, интересующимся приложениями или обобщениями различных аспектов вещественных преобразований. Для коммерческого использования некоторых из этих программ может потребоваться лицензия или заключение соглашения с Советом посредников Станфордского университета через Отдел лицензий в области технологии, Станфорд, Калифорния 94305.

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

Легко понять, почему математическая физика могла довольствоваться традиционным интегралом Фурье в течение времени, превышающего целое столетие. Даже введение радикально нового метода вычисления, а именно быстрого преобразования Фурье, поначалу слабо повлияло на практику вычислений, но когда пришло время компьютеров, этот метод осуществил подлинный переворот.

Когда в 1965 г. благодаря Кули и Тьюки быстрое преобразование Фурье стало доступно широкому кругу читателей, а соответствующие материалы были опубликованы в статьях методического характера и тематических выпусках журналов, эти методы получили высокую оценку специалистов в области анализа электрических сигналов. Это вызвало удивление в кругах специалистов по методам численного анализа, где подобные методы уже были известны. Превосходная ретроспектива дана в работе Эйдемана, Барраса и Джонсона, опубликованной в Archive for History of the Exact Sciences (Архив истории точных наук), в которой прослеживаются истоки метода, берущие начало от статьи Карла Фридриха Гаусса (1777-1855), написанной в 1805 г., в которой он утверждает: «Опыт убедит пользователя в том, что данный метод в значительной степени облегчит утомительный труд выполнения механических вычислений».

Интересным побочным эффектом этого исторического исследования является то, что, как оказалось, быстрый метод Гаусса для оценки суммы ряда Фурье предшествует статье, на которой базируется известность Фурье. Добавим, что статья Гаусса была опубликована много позже в собрании его сочинений C.F. Gams. Collected Works, Vol. 3, Göttingen, Royal Society of Sciences, 1876, и напомним, что когда Фурье выдвинул идею представления произвольных периодических функций посредством тригонометрических рядов, выдающиеся математики, такие, как Лагранж, были с ней несогласны.

Не было очевидным, что могут существовать более оптимальные алгоритмы, пока не оказалось, что новая процедура факторизации матриц, описывающих дискретное преобразование Фурье, оказывается более быстрой, нежели быстрое преобразование Фурье. Попытки извлечь пользу из того факта, что данные могут полагаться вещественными, оказались успешными лишь отчасти, потому что программа, оперирующая вещественными данными в преобразовании Фурье, не может быть использована для обращения (обязательно комплексного по своему характеру) из области преобразования в область исходных данных. Поэтому должна быть отобрана библиотека программ как для прямого, так и для обратного преобразований, принципиально отличающихся друг от друга. Ни один тип этих программ не обладает свойством взаимности для преобразований Фурье, но пары таких программ обеспечивают экономию машинного времени ценой увеличения требуемого объема памяти.

Быстрый алгоритм, базирующийся на новой процедуре факторизации, в достаточно изящной форме позволяет решить данную задачу и рекомендуется для численного анализа. Алгоритм оперирует только с вещественными числами-единственным видом данных, которыми мы располагаем в реальном эксперименте, и непосредственно дает ответы на интересующие нас вопросы, что также обычно представляется через вещественные данные и не требует перехода в область комплексного преобразования. С тех пор как в течение полутора столетия был хорошо известен комплексный характер коэффициентов Фурье, возможно, трудно принять, что комплексные числа-изобретение человеческого разума, а не создание самой природы. Естественно, мы все признаем, что энергетический спектр, например спектр оптического сигнала, описывается вещественной функцией переменной вещественной частоты /, но возникает вопрос: не следует ли интенсивность а} + bj этого спектра вычислять как квадрат модуля комплексного коэффициента а{ + 1Ър. Разумеется, это один из сно-собов. Другой способ, рассмотренный в данной книге, заключается в вычислении величины [#(/)]2 + [Я(-/)]2, где Н(Л-(вещественное) преобразование Хартли. Непосредственно может быть вычислена и фаза. Нет таких задач, для которых справедливо использование комплексного преобразования Фурье и одновременно не может быть применено вещественное преобразование Хартли.

ОГЛАВЛЕНИЕ

Предисловие редактора перевода ........................................5

Предисловие ..................................................................7

Глава 1. Введение ............................................................8

Глава 2. Преобразование Хартли ........................................14

Исходная формулировка ................................................14

Преобразование Хартли ................................................17

Четная и нечетная составляющие ......................................18

Формулы связи ............................................................18

Примеры ....................................................................19

Энергетический и фазовый спектры ....................................23

Задачи ......................................................................26

Глава 3. Теоремы ............................................................29

Соответствие операций ..................................................30

Свертка ....................................................................31

Соотношения между преобразованиями во временной и частотной областях ...........31

Задачи ......................................................................32

Глава 4. Дискретное преобразование Хартли ........................34

Дискретное преобразование Хартли ..................................34

Физический смысл величин I и V ......................................35

Четная и нечетная составляющие ......................................35

Примеры дискретных преобразований Хартли ......................36

Степени свободы ..........................................................39

Другие вещественные ядра ..............................................39

Теоремы ....................................................................40

Выводы ....................................................................43

Задачи ......................................................................43

Глава 5. Цифровая фильтрация посредством свертки ............46

Циклическая свертка ........................................................47

Дополнение нулями ......................................................49

Обращение свертки ................................50

Теорема о свертке ........................................................51

Теорема о свертке в частотной области (спектральное сглаживание) 53

Числовой пример свертки ..............................................53

Коэффициент ........................................................55

Числовой пример корреляционной функции ..........................56

Низкочастотная фильтрация ............................................57

Подчеркивание границ ..................................................59

Свертка с использованием быстрого преобразования Хартли 60

Способ без использования перестановок ..............................61

Свертка как умножение матриц ........................................62

Задачи .............................................63

Глава 6. Двумерные преобразования ..................................65

Двумерное преобразование Хартли ....................................65

Симметрия и антисимметрия ..........................................66

Примеры ....................................................................67

Теоремы для двумерных преобразований ............................67

Круговая симметрия ......................................................69

Двумерная фильтрация ..................................................69

Цикличность для двумерного случая ..................................71

Трехмерный случай ......................................................73

Задачи ......................................................................73

Глава 7. Факторизация матрицы преобразования ..................76

Матричное представление дискретного оператора ..................76

Перестановка ..............................................................78

Перестановочные диаграммы ..........................................79

Перестановочная матрица ..............................................82

Ячеистая структура перестановочной диаграммы ..................83

Каскадные матрицы ......................................................85

Переход к дискретному преобразованию Фурье ....................88

Задачи ......................................................................90

Глава 8. Алгоритм быстрого преобразования ........................91

Определяющие соотношения ............................................91

Свойства NlogN ..........................................................93

Повторное разбиение последовательностей ..........................95

Преобразование с использованием разложения на подпоследовательности .......96

Общая формула разложения ............................................97

Соотношения для случая N = 16 ......................................100

Направленный сигнальный граф ........................................101

Вычисление с замещением ..............................................103

Анализ временных затрат на вычисление с помощью полосковой диаграммы ............104

Степени числа 2 ..........................................................107

Тригонометрические функции ..........................................108

Быстрое вычисление синусов ............................................110

Операция быстрого поворота ..........................................112

Быстрая перестановка ....................................................114

Преобразование для последовательностей с основанием 4 и

другие модификации ......................................................115

Ранее применявшиеся подходы к преобразованию вещественных

данных ......................................................................117

Задачи :....................................................................120

Глава 9. Преобразование Хартли в оптике ..........................121

Целесообразность преобразования Хартли в оптике................121

Свойства симметрии ......................................................122

Осуществление преобразования Хартли, использующее поляризацию ...............................125

Практическое осуществление ............................................125

Источник некогерентного излучения ..................................126

Пример ....................................................................127

Голография в плоскости Хартли ......................................129

Приложение 1. Программы вычислений на ЭВМ ..................131

Приложение 2. Атлас преобразований Хартли ................163