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

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

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

сомножителей М; а - число такое, что N является наименьшим положительным
целым числом, для которого справедливо aw= 1 (mod М).
Преобразование (1.53) называется прямым, а (1.54)-обратным ТЧП (ОТЧП).
При вычислении ОТЧП встречаются операции сравнения, выполняемые над
отрицательными степенями целого числа. По определению [1.12]
rfs == г2 (mod М),
где г и гг, s - целые числа; s>0 в том и только в том случае, если Is
sr2ris(modM).
Использование ТЧП для вычисления круговой свертки двух
последовательностей целых чисел х(пТ) н h(nT)= 0 N-1 аналогично ДПФ (см.
1.4.2) и
заключается в выполнении следующих действий:
1) вычислении ТЧП последовательности х{пТ):
, N-1 '
X (к) = ( 2 х (п Т) апк\ (mod M),k= 0, ... , N- 1; (1.55}
2) вычислении ТЧП последовательности h(nT):
H(k) = (% h(nT) апк\ (mod М), к=0, ... , N-1; (1.56)
\п=0
3) перемножении полученных ТЧП:
У (k) = (X (к) Н (к)) (mod М), к = 0 N- 1; (1.57)
4) вычислении ОТЧП последовательности У (к):
у (пТ)= (n~1 J У (к) а~пк ^ (mod М), п = 0S ... , N- 1. (1.58)
Последовательность у(пТ) является искомой сверткой. Так как в кольце
целых чисел по mod М числа могут быть представлены однозначно, если их
абсолютное значение не превосходит М/2, то х(пТ) и h(nT) должны быть
промасштабиро-ваны таким образом, чтобы \y(tiT) |
С точки зрения эффективности вычислений к ТЧП предъявляются следующие
требования:
число N должно быть представимо в виде произведения большого числа
сомножителей, чтобы существовал эффективный алгоритм типа БПФ;
умножение на степени а должно быть простей операцией; так, если а равно
некоторой степени числа 2, то умножение сводится к сдвигам;
число М должно иметь двоичное представление с малым количеством разрядов
для облегчения операции по modM и быть достаточно большим, чтобы
исключить переполнение.
Наибольшее распространение на практике получили теоретико-числовые
преобразования с числами Ферма (ТЧПФ) и Мерсенна (ТЧПМ).
Теоретико-числовое преобразование Ферма [1.6, 1.12] является наиболее
перспективным, так как позволяет использовать эффективные алгоритмы типа
?ПФ. В качестве модуля М выбирается одно из чисел Ферма:
М = ^ = 22<+1=2ь + 1,Ь = 2'.
.¦Здесь Ft называется t-м числом Ферма. Первые семь чисел равны:
F0 = 3 F1== 5 F2 - 17 F" - 257 F4 = 65 537 Fs = 641X6 700 417 Ft = 274
177X67 280 421 310 721.
В табл. 1.4 приведены параметры нескольких возможных реализаций ТЧПФ.
простые числа.
Таблица 1.4
Г t ь Ft N для a=2 N для a= V~2 JV max a для Nmo3c
2 4 2*+l 8 16 16 1/2"
3 8 2*+ 1 16 32 , 256 3
4 16 216+ 1 32 64 65536 / 3
5 32 2*2-f 1 64 128 128 1/2
Пример 1.14. С помощью ТЧПФ вычислить свертку последовательностей: л=[2,
-2, 1, 0]~т; h=[l, 2, 0, 0]т [1.12]. В качестве модуля выберем число
М=/7г=17. При 1V=4 а=4. Матрица ТЧПФ (1.53) принимает вид
-т* =
[
1 1 1
41 42 43
42 44 4б
43 46 49
1 '1 1 4
1 -1 1 -4
1 1 1 П 1 1 1 ]
-1 -4 I 1 4 16 13
1 -1 Н 1 16 1 16
-1 4 J L1 13 16 4 J
-Так как 4-1=-4(mod 17), то матрица ОТЧПФ
•^,ф=4-1
1 1 1
4-1 4-2 4-3 4-2 4-4 4-6 4-з 4-в 4-9
Согласно (1.55)-(1.58) вычисляем:
1) ТЧПФ последовательности х:
^СэзТфх(то(1 17)
1111
1 4 16 13 v
1 16 1 16 ¦
1 13 16 4
21 [ ,81 I п
•5 |_ 78 I 10
1 Н 243 Н 5 0J [ 213 J ] 9J
(mod 17).
1111
1 13 16 4
1 16 1 16
4 16 13
(mod 17).
(mod 17)
28
2) ТЧПФ последовательности h:
Н = ТфЬ(тос117);
1 1 1 1 1 Г 1 ]
1 4 16 13 Ы 2
1 16 1 16 х О г
1 13 16 4 J L 0 J
(mod 17),
3) ?=Х-НТ=з[3, 90, 80, 90]т=[3, 5, 12, 5]T(modl7).
4) ОТЧПФ от Y дает искомую свертку: у=Т-'ф\з[2, 2, 14, 2]т (mod 17). Так
как результаты должны лежать в диапазоне [-8, 8], то окончательно у= =
[2, 2, -3, 2]т. (Сравните с примером 1.13).
Гебретико-числовым преобразованием Мерсенна [1.12] называется пара
следующих преобразований:
/р-1
"(2 \п=1
( р-1
* к12
\ *=с
X(k)
х (п Т)
x{nT)-2nk\ (modq),k = 0.......-I;
(1.59)
р-1
X (ft) 2'
-nk
(mod q), " = 0, ... , p-1, (1-60)
тде p- простое положительное число; q=2?-1-простое число (число
Мерсенна).
В качестве р могут быть выбраны числа 2, 3, 5, 7, 13, 17, 19, 31, 61. С
точки зрения обеспечиваемого динамического диапазона наиболее широко
используются числа 31 и 61. Преобразование Мерсенна не обладает
структурой БПФ и для своей реализации требует (р-I)2 операций сдвига н
р(р-1)-сложения.
Пример 1.15. С помощью ТЧПМ найдем свертку последовательностей: х= = [2,
-2, 1, 0, 0]т; h=[l, 2, О, О, 0]т. Выберем р=5, тогда д=25-1=31. Матрица
ТЧПМ имеет вид
1 1 1 1 1 " "1 1 1 1 1"
1 2 22 23 24 1 2 4 8 16
1 22 2* 2* 2" = 1 4 16 2 8
1 23 2е 2" 212 1 8 2 16 4
1 2* 28 212 21* 1 16 8 4 2_
(mod 31)-
Так как S_, = 25(mod31), то матрица ОТЧПМ
Т-! =5-2
"I 1 1 1 1 " "I 1 1 1 Г
1 2 1 2-2 2-* 2-4 I 16 8 4 2
1 2-2 2-4 2-8 2-8 = 25 1 8 2 16 4
1 2-3 2-8 2-" 2-12 1 4 16 2 8
1 2-4 2-8 2-12 2-18 _ 1 2 4 8 16
(mod 31)-
Теперь вычисляем: _
1) ТЧПМ последовательности х: Х=Тмх= [1, 2, 10, 19, 9]т (mod 31); ч.
2) ТЧПМ последовательности h: H=T"h=[3, 5, 9, 17, 2]т (mod 31);
Предыдущая << 1 .. 4 5 6 7 8 9 < 10 > 11 12 13 14 15 16 .. 97 >> Следующая

Реклама

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed

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

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed