Брейсуэлл Р. - Преобразование Хартли (теория и приложения), страница 10

Так как выходная последовательность состоит из 9 элементов, мы должны увеличить число элементов до )т'>8. В данном примере возьмем М = 1б на основании того, что программы, связанные с анализом данных, легче всего реализуются для степеней числа 2.

Тогда справедливо равенство (1 1 1 1 1 0 0 О) * (1 1 1 1 1 0 0 О) = =(1234 5432 1000 0000), однако мы можем также центрировать дополненные последовательности, помещая центральные элементы в точку т = О. Тогда (1110 00! Ц®(1110 001 Ц= = (5 4 3 2 1 О О О О О О О ! 2 3 4). Из выражения для центрированных последовательностей видим, что для получения желаемого результата дополнительные нули должны быть размещены в середине этих последовательностей, а не справа. Неумение дополнять последовательности данных до требуемых размеров и размещение дополнительных нулей в правой части последовательности ставят в тупик пользователей программ, разработанных друтпми агециалистами. Вышеприведенный пример может быть решен вручную; аналоговое вычислительное устройство, облегчающее выполнение свертки, имеет два концентрических наборных диска, каждый из которых состоит из М сегментов, в которые могут быть записаны две последовательности, вращающиеся относительно друг друга в противоположных направлениях, что обусловлено знаком «минус» в одном из сомножителей в сумме, определяющей процедуру свертки.

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

5.2. Аналоговое вычислительное устройство, установленное в положение для выполнения свертки последовательностей (1 2 3) и (! 3 5 7), результатом которой является последовательность (1 5 14 26 29 21). Ня роторе (вращающемся диске) в обратном порядке записана последовательность (71); на внутреннем кольце статора (неподвижного диска) записана последовательность (7" ), я на внешнем кольце посегментно регистрируется результат, т.е. последовательность (7з).

РотоР находитсЯ в положении, соответствУющем вычислению второго элемента (5) последовательности (7з). статор, на внутреннем кольце которого содержится информация о !' (г), имеет внешнее кольцо, на котором может быть записан результат свертки 7'(т). Если результат свертки известен, но последовательность 7; (т) на роторе отсутствует, то представляется возможность определить недостающие значения следующим образом. Устанавливая пустую ячейку (сегмент) для 1, (0) против 7 (0), можно констатировать следующее: «Первое значение, умноженное на 1, равно 1, поэтому в первую пустую ячейку записываем цифру 1.

Вращая диск, устанавливаем эту ячейку против )з (1). Тогда сумма, составленная из произведения второго значения на 1 и произведения 1 х 3, равна 5; поэтому записываем цифру 2 во вторую ячейку» и т.д. Циклическая свертка не является обращаемой, если только не будет присутствовать достаточное число нулей, чтобы предотвратить наложения. Иногда дополнение последовательностей нулями представляет собой приемлемый вариант, а в иных случаях †н. Простая программа реализации вращающегося вычислительного устройства, используемого для обращения свертки, приведена в приложении 1 под названием !СОХУ.

Обращенные последовательности могут быть также определены с помогцью этого метода, исходя из необходимости того, чтобы результирующая свертка представляла собой последовательность (Ц. Обращение свертки Очевидно, из анализа аналогового вычислительного устройства следует, что обычная свертка всегда может быть обращена. Пусть 50 Теорема о свертке Теорема о свертке, удовлетворяющая дискретному преобразованию Хартли (ДПХ), формулируется следующим образом. Еслибы(т) — цик- 5! лическая свертка последовательностей Л (т) и/з (т), т. е. П вЂ” 1 ./() = — Л( ЮЛ() = Е ЛЮ/з( — ') . =о то Н (ч) = '/з 1Н, (ч) Нз (ч) — Н,( — ч) Н, ( — ч) + Н, (ч) Н, ( — ч) + + Н, ( — ч) Н (ч)1, где Н (ч), Н, (ч) и Н (ч) — дПХ последовательностей / (т), /, (т) и /з (т) соответственно.

Этот результат может быть выражен другим способом в виде Н (ч) Н! (ч) Нзд (ч) + Н1 ( ч) Нзр (ч) где Н, (ч) = Н„(ч) + Н„(ч) — сумма четной и нечетной компонент. Обычный путь численного выполнения свертки заключается в дискретном преобразовании Фурье каждой из двух заданных последовательностей и в последующем умножении их комплексных элементов в области преобразования Фурье, что равнозначно умножению четырех соответствующих вещественных величин в элементе ДПФ свертки. Далее следует выполнить обратное преобразование Фурье, не забывая при этом о необходимости изменения знака перед мнимой единицей 6 Аналогичная процедура использования преобразования Хартли для выполнения свертки потребует только двух умножений вещественных величин в элементе ДПХ сверток, Однако очень часто возникают ситуации, особенно при обработке изображений, а также в общем случае при цифровой фильтрации, когда одна из свертываемых функций, например / (т), является четной.

Поэтому в данных ситуациях теорема о свертке упрощается и приводится к виду Н (ч) = Н, (ч) Н (ч). Благодаря этому упрощению необходимо только определить ДПХ обеих последовательностей данных, затем поэлементно перемножить получившиеся вещественные последовательности и к полученному результату применить операцию ДПХ. Таким образом, предлагаемая процедура имеет вид /; (т) ®/' (т) = ДПХ от 1(ДПХ от /;) х гДПХ от /' Н.

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

Вопрос выбора коэффициента Н ' будет рассмотрен ниже. Теорема о свертке в частотной области (спектральное сглаживание) Иногда операпия свертки должна выполняться в области преобразования, как, например, в случае необходимости сглаживания спектра Н, (ч) для выделения его наиболее интересных свойств и характеристик. С этой целью были предложены различные сглаживающие функции Н, (ч); так как эти сглаживающие функции всегда являются четными, процедура свертки в частотной области имеет вид Н, (ч) С«) Н (ч) = ДПХ от г(ДПХ от Н,) х (ДПХ от Нз)5, Вновь имеем простой и изящный результат, требующий выполнения только умножения вещественных величин. Выбор сглаживающей функции Н,(ч) субъективен по своему характеру, и может оказаться, что биномиальные коэффициенты (1/4) (2 1 ...

!), (1/16) (6 4 1 .. 1 4), (1/64)(20 15 6 1 ... 1 6 15) и т, д. лучше всего удовлетворяют требованиям, сводя этот выбор к реализации в чистом виде процедуры сглаживания. Тогда второй сомножитель-ДПХ от Н,(ч) — принимает вид простой суммы косинусов; например, ДПХ последовательности (1/4) (2 1 ... 1) пропорционально величине 1 + соз(2ят/А7).(Коэффициент пропордиональности зависит от Ж; однако на практике может оказаться целесообразным не оперировать в процессе вычислений ни этим коэффициентом, ни 1/4, оставив их в запасе вплоть до завершения процедуры.) Коэффициент 1 + соа (2ят/М), иногда называемый «окном типа косинус в квадрате», является изменяющимся в широком диапазоне изменения т весовым коэффициентом, максимальным при т = О и монотонно уменьшающимся до нуля при т = Н/2.

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

В следующих двух столбцах приводятся дискретные преобразования Хартли Н, и Н,. Пятый столбец содержит произведение Н, Н„а последний — последовательность/„ которая представляет собой свертку, равную дискретномупреобразованиюХартли столбца произведений Н,Н„ умноженному на Н. Появление коэффициента Н обусловлено тем, что в определении ДПХ фигурирует коэффициент Н ". Может оказаться более целесообразным умножение на Н на завершающем этапе вычислений в рамках нормировки, калибровки и других процедур. Примечательно, что значения/и приведенные в последнем столбце, отличаются от точных значений. Максимальное расхождение 52 53 Табаиоа 5.2 Таблиоа 5.

! Процедура свертка 2 1 0,5 г 1 4 О 427 1,457 О 6 0,25 -0,5 0 4 0,073 — 0,043 0 ! 0 0 0 0 0,073 0,043 0 0 025 -05 ! О О 427 — 1,457 6 15,008 20 15,008 6 0,992 0 0„992 1 0,622 -О,!25 -0,003 0 0,003 -О, 125 -0,622 ! -0,666 0 0 0 0,041 0 0 1 0 0 0,041 1 1 0,5 2 1 1 2 0,552 0 0 2 3 О 0 0 0 4 -0,125 0,207 -0,026 0 3 0,25 0 0 0 2 0,198 0 0 О 1 -О,гх О О 0 0 -0,125 — ! .207 0,151 -1 — 0,1Ы 0 0 0 0,026 0 О 1 2,992 -0,408 3,011 0 7,008 0,007 10,998 О 13,008 0,033 12,989 0 8Я92 -0,258 5,002 0 0 0 -0,666 Коэффициент )ч 55 Л Уг Н! Нг Н!Нг Уг достигает в данном примере 0,0004. Однако приближенный характер результата в принципе свойствен методу с использованием преобразования, вычисляемого с конечной точностью.

В табл. 5.2 представлен пример довольно общего характера. Все четыре произведения, фигурирующие в теореме о свертке, табулнрованы с использованием обозначения Йг = Н,( — ч). Предпоследний столбец содержит полусуммы элементов предыдуших четырех столбцов, а значения в последнем столбце представлягот собой ДПХ столбца для суммы, умноженное на 8.