Научная литература
booksshare.net -> Добавить материал -> Физика -> Гольденберг Л.М. -> "Цифровая обработка сигналов: Справочник" -> 14

Цифровая обработка сигналов: Справочник - Гольденберг Л.М.

Гольденберг Л.М. Цифровая обработка сигналов: Справочник — М.: Радио и связь, 1985. — 312 c.
Скачать (прямая ссылка): cifrovayaobrabotkasignalov1985.djvu
Предыдущая << 1 .. 8 9 10 11 12 13 < 14 > 15 16 17 18 19 20 .. 97 >> Следующая

арифметических операций для N=q'= \+а-2пр, где q' - простое; р=31,61;
а=3,5; п= 1,2,3. В этом случае ДПФ сводится к вычислению (q'-1)-точечной
круговой свертки, которую, в свою очередь, можно представить в виде
прямого произведения а-2" и p-точечных сверток (см. 1.4.7). Для
вычисления p-точечной свертки используется ТЧП Мерсенна, требующее р
операций умножения и 2р(р-1) сложения.
Таблица 1.7
<Z' 1 Число операций для действительной входной последовательности
я' в'-1 Число операций для действительной входной
последовательности
умноже- ния сложения умноже- ния | сложения
367 2*3-61 488 61 976 1831 2-3-5-61 4880 607 560
373. 22.3.3I 620 41044 1861 22-3-5-31 6200 412 920
733 22-3-61 1220 153 964 2441 2(r) 5-61 8540 1 073 600
(1.78)
1.5.3. Использование эффективных методов поворота вектора (КОРДИК)
КОР ДИК*-это совокупность эффективных методов поворота вектора (х" y)-
x+iy на угол 6 с помощью только операций сложения и сдвига [1.16]. КОРДИК
может служить эффективным средством реализации поворачивающих множителей
в алгоритмах БПФ. Общее выражение, описывающее КОРДИК, имеет вид:
х1 = ах±Ру;)
Ух = ау ±&х,}
где Xi, у\ - координаты вектора, повернутого на угол 0=±arctg[P/a].
Модуль вектора (х\, ух) равен модулю вектора (х, у), умноженному на
коэффициент
С = "|/a2 -J- Р2.
Различают две основные разновидности КОРДИКа: полный и оптимальный.
Полный КОРДИК представляет собой итерационный процесс. В этом случае а=1;
Р=2_(, где I - номер итерации. Процесс поворота вектора (х, у) на угол 0
с точностью до п-го разряда требует п итераций и происходит следующим
образом: вначале осуществляется присвоение начальных значений 1=0; 0(=-0;
G(=l, а затем я раз выполняется последовательность операций:
.сц - sign (0г); xi+i - xi + сц yi2~l;
У1+1-У1 сц xi 2 г; (1.79)
0l+i = 6/-o,i ai -f- ctg (2-l) \
Gi+1 = Gi (1 + 2-(r)г) i /2,
I = I -[- 1 •
* CORDIC - Coordinate Rotation Digital Computer.
38
п-1
В конце п-й итерации коэффициент G= П -(1Ч-2-**)1/2" 1,6.
г=о
Из (1.79) следует, что полный КОРДИК требует 2п операции сложения с
одновременным сдвигом.
Идея оптимального КОРДИКа заключается в том, чтобы выбрать такие целые
числа а и Р, удовлетворяющие равенству 0=arctg(P/a) или P/a=tg0 с
заданной степенью точности, чтобы минимизировать число операций сложения
при вычислениях по формулам (1.79). Другими словами, двоичное
представление таких аир должно содержать минимальное число единиц.
Использование оптимального КОРДИКа для вычисления ДПФ становится ясным из
примера 1.25.
Пример 1.25. Вычислим 8-точечное ДПФ:
7
Х{к) = У х (п Т) wf,
п=0
k=0,
, 7.
(1.80)
Преобразуем выражение (1.80) согласно алгоритму с множителями поворота
(см. 1.3.5), для чего сделаем подстановку:
k = k1-\-k2-2; п = ^-(-"2-4 ; к%3= 0, ... ,3; к±, п% = 0, 1.
(1.81)
Тогда
3 Г Г1 1
х{кг+кг-2)^ ^ ( S *:""!+"*•¦*)T)w*>n*
пг=о L Vn2=0 J
Таким образом, вычисление свелось к 2- и 4-точечным ДПФ, не требующим
операций умножения, и умножению на множители поворота WshinK Для
реализации множителей поворота используем оптимальный КОРДИК- Пояснения
приведены в табл. 1.8 для поворота на 0= (2я/8)/-Ья/8.
Таблица 1.8
ч 2Я G-61+62+63+64
8 1 6j е2 6з 04
0 0 0 0 я/4 -л/8
1 я/4 0 0 -я/4 я/8
2 я/2 0 я/2 я/4 -я/8
3 Зя/4 0 я/2 -я/4 я/8
4 я я 0 я/4 -я/8
5 5я/4 я 0 -я/4 я/8
6 Зя/2 я я/2 я/4 -я/8
7 7я/4 я я/2 -я/4 я/8
39
Как видно из табл. 1.8, повороты осуществляются в четыре ступени. На
первых двух ступенях повороты являются тривиальными и не изменяют модуля
векторов. На третьей и четвертой ступенях все векторы поворачиваются на
один и тот же угол с точностью до знака с тем, чтобы модуль всех векторов
умножался на один и тот же коэффициент G. В конце последней ступени все
векторы оказались повернутыми относительно искомого положения на один и
тот же дополнительный угол, равный п/8. Так как дополнительный фазовый
сдвиг не изменяет формы ДПФ, то его можно не устранять.
Повороты на я, я/2 и я/4 осуществляются следующим образом:
¦Г1=
I У1 =
*1=- у>
я/2-* {
-у,
Х1 = Х - у,
я/4 -"• {
Ui=#+*-
Поворот на я/8 с точностью до 16-го разряда обеспечивается оптимальным
отношением а/Р= 128/309, которому соответствует
2
( tx = x + x-2~2; tv - t/ + y-2-'
Y* 1 (**-<*• 2-5-*.2-s) 2-i ± у.2-2 ;
* y1=(ty-ty2-s - y2-s) 2-i ± x-2-2.
В результате для вычисления 8-точечного ДПФ потребовалось 128 операций
сложения и ни одной операции умножения.
1.5.4. Специальные виды ДПФ
В таких важных приложениях цифровой обработки сигналов, как реализация
трансмультиплексоров (см. разд. 9), нашли применение нечетно-временное
нечетно-частотное ДПФ (Н2ДПФ) [1.20] и косинусное преобразования [1.21],
позволяющие существенно сократить число требуемых арифметических операций
по сравнению со случаем использования обычного ДПФ.
Нечетно-временное нечетно-частотное ДПФ. Этот вид преобразования
используется для эффективного вычисления ДПФ Аг-точечных (N кратно 4)
симметричных действительных последовательностей в случае, когда во
Предыдущая << 1 .. 8 9 10 11 12 13 < 14 > 15 16 17 18 19 20 .. 97 >> Следующая

Реклама

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed

Есть, чем поделиться? Отправьте
материал
нам
Авторские права © 2009 BooksShare.
Все права защищены.
Rambler's Top100

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed