Оптическая галография - Кольер Р.
Скачать (прямая ссылка):
§ 2. Дискретное фурье-преобразование и быстрое фурье-преобразование
Как отмечалось выше, машинные методы расчета фурье-голо-грамм сопряжены с вычислением очень большого количества отсчетов фурье-образа предметной функции. Поскольку вычислительная машина в состоянии запоминать координаты только ограниченного числа отсчетов предметной функции, представляет интерес рассмотреть форму, которую принимает их фурье-образ. Как и ранее, мы ограничимся анализом одномерного случая. Вспомним, что в соответствии с (4.9) фурье-образ функции а (х) определяется как
СО
A(E)= J а (х) ехр (2ni\x) dx. (19.13)
— со
Подставляя вместо а (х) выражение (19.12), получаем
OO OO
A (E) = ( 2 а (гН ""пі1 МЗК: Х~2т) ехР dx- (19J4>
J 1 N ьмакс / -^ьмакс ж—пт
— СО 771= — СО
Из соотношений (4.20) и (4.31) имеем
Г Sin (яЕмаке *-*>») ехр (2nilx) dx =
J ^ьмакс х — пт
— со
= ^i— rect ехР (2пі -г^-\ • (19Л5)
ьмакс V ьмакс / V ьмакс /
Подстановка (19.15) в (19.14) дает, что при лежащих в интервале (—?макс/2 ^ I ^ ?макс
ьмакс V ьмакс / \ ьмакс /
т—оо (19.16)
A (?) = О для всех остальных |.
ДИСКРЕТНОЕ ФУРЬЕ-ПРЕОБРАЗОВАНИЕ
621
При выводе (19.12) мы предполагали, что функция а (х) имеет ограниченную полосу частот. Теперь сделаем дополнительное предположение, а именно будем считать, что она ограничена в пространстве интервалом —xUSillc/2 ^ х ^ #Макс/2. (Строго говоря, это неверно, так как функция, ограниченная по полосе частот, не может одновременно быть ограниченной в пространстве; это допущение ведет к некоторой погрешности вычисления фурье-образа А (|). Однако, когда величина произведения #ма«с?макс намного больше единицы, что всегда соблюдается для голограмм, эта ошибка пренебрежимо мала [19.3].) Если функция а (х) ограничена в пространстве интервалом ±хмакс/2, то из теоремы отсчетов следует, что А (?) — фурье-образ функции а (х) — может быть восстановлен из отсчетов фурье-образа, взятых через интервалы А| = 1/ямако что аналогично соотношениям (19.8). При машинном расчете голограммы можно сократить машинное время путем вычисления А (?) только в точках отсчета | = п/хмапс, где п — целое число. Следовательно, для единичного отсчета функции А (I) в (19.16) можно написать
М/2
A Uu-)=* 2 а (") ехр І2Ш тпх ) , (19.17)
\ хмакс / ьмакс N ёмакс / N ьмакс жмакс /
т=-М/2
где M — общее число отсчетов ограниченной в пространстве функции а (х). Соотношение (19.17) называется дискретным фуръе-преобразованием.
Теперь оценим число ступеней вычисления, время и стоимость вычисления дискретного фурье-образа функций некоторых объектов. Для каждого отсчета A (n/xMSil{c) фурье-образа мы должны вычислить M произведений, соответствующих M отсчетам предметной пространственной функции, хранящимся в памяти вычислительной машины. Если в соответствии с теоремой отсчетов эти дискретные значения берутся с пространственным интервалом Ax = 1/^макс и если предметная пространственная функция характеризуется протяженностью хшакс, то общее количество вводимых в запоминающее устройство дискретных данных равно
М = ^? = ямакс?мако. (19-18)
Аналогично получаем общее число дискретных отсчетов фурье-образа
N — -—^р- 5макс #макс» (19.19)
Мы видим, что M = N, т. е. как исходная пространственная функция, так и фурье-образ требуют одинакового числа отсчетов. Для вычисления всех дискретных значений одномерного фурье-
622
ГОЛОГРАММЫ, СИНТЕЗИРОВАННЫЕ НА МАШИНЕ ГЛ. 19.
образа необходимо вычислить общее количество MN = N2 членов. Для двумерного фурье-образа, состоящего из матрицы NxN дискретных отсчетов, требуется iV4 членов.
Предположим, что мы ввели в запоминающее устройство вычислительной машины матрицу из 100 X 100 отсчетов предметной пространственной функции и что для вычисления одного члена суммы формулы (19.17) и прибавления его к остальным необходимо 30 мкс. (Последняя величина типична для современных больших вычислительных машин.) В этом случае матрица фурье-образа, состоящая из 100 X 100 отсчетов, может быть вычислена за 3000 с, т. е. менее чем за час. Такой матрице соответствует довольно примитивная картина. Поскольку стоимость часа машинного времени большой вычислительной машины может достигать нескольких сотен долларов, перспективы машинного синтеза фурье-голограмм кажутся довольно сомнительными. К счастью, в последнее время получил широкое распространение позволяющий сэкономить время метод вычисления, называемый быстрым фуръе-преобразованием; это существенно улучшает перспективы машинного синтеза.
Быстрым фурье-преобразованием назван алгоритм для вычисления фурье-образа. При больших значениях N этот алгоритм характеризуется существенно меньшим числом операций вычисления, чем следует из соотношения (19.17). (Поскольку объяснение этого алгоритма выходит за рамки настоящей книги, мы рекомендуем обратиться к работе [19.3].) Машинные программы быстрого фурье-преобразования широко доступны. Для успешного применения алгоритма предпочтительно, чтобы число iV представляло собой степень двух. В этом случае для вычисления фурье-образа матрицы из N X N отчетов требуется всего 4iV2 1оог2 N операций умножения и сложения [19.3]. В табл. 19.1 приведены некоторые оценки [19.4] машинного времени, необходимого для вычисления матриц из N X N отсчетов прямым методом (iV4 членов) и методом быстрого фурье-преобразования. Эти данные с очевидностью доказывают преимущества метода быстрого фурье-
