1.5.3. Использование эффективных методов поворота вектора (КОРДИК)

КОРДИК — это совокупность эффективных методов поворота вектора на угол с помощью только операций сложения и сдвига [1.16]. КОРДИК может служить эффективным средством реализации поворачивающих множителей в алгоритмах БПФ. Общее выражение, описывающее КОРДИК, имеет вид:

где — координаты вектора, повернутого на угол Модуль вектора равен модулю вектора умноженному на коэффициент

Различают две основные разновидности КОРДИКа: полный и оптимальный. Полный КОРДИК представляет собой итерационный процесс. В этом случае где I — номер итерации. Процесс поворота вектора на угол

0 с точностью до разряда требует итераций и происходит следующим образом: вначале осуществляется присвоение начальных значений а затем раз выполняется последовательность операций:

В конце итерации коэффициент

Из (1.79) следует, что полный КОРДИК требует операции сложения с одновременным сдвигом.

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

Использование оптимального КОРДИКа для вычисления ДПФ становится ясным из примера 1.25.

Пример 1.25. Вычислим -точечное ДПФ:

Преобразуем выражение (1.80) согласно алгоритму с множителями поворота (см. 1.3.5), для чего сделаем подстановку:

Тогда

Таким образом, вычисление свелось к 2- и 4-точечным ДПФ, не требующим операций умножения, и умножению на множители поворота Для реализации множителей поворота используем оптимальный КОРДИК. Пояснения приведены в табл. 1.8 для поворота на

Таблица 1.8 (см. скан)

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

Повороты на осуществляются следующим образом:

Поворот на с точностью до разряда обеспечивается оптимальным отношением которому соответствует

В результате для вычисления -точечного ДПФ потребовалось 128 операций сложения и ни одной операции умножения.