Ћекции.ќрг


ѕоиск:




 атегории:

јстрономи€
Ѕиологи€
√еографи€
ƒругие €зыки
»нтернет
»нформатика
»стори€
 ультура
Ћитература
Ћогика
ћатематика
ћедицина
ћеханика
ќхрана труда
ѕедагогика
ѕолитика
ѕраво
ѕсихологи€
–елиги€
–иторика
—оциологи€
—порт
—троительство
“ехнологи€
“ранспорт
‘изика
‘илософи€
‘инансы
’ими€
Ёкологи€
Ёкономика
Ёлектроника

 

 

 

 


ѕр€мые ƒѕ‘ последовательностей x1m и x2m выражаютс€ следующими соотношени€ми

где

.

 

”чтем, что,

 

ѕоэтому

 

√рафическое представление вычислительных операций приведено на рисунке.

—трелочками представлены множители

.

ќтсчеты S0, S1, S2, S3 получаютс€ с использованием операции сложени€, поэтому около них стоит знак У + У, отсчеты S4, S5, S6, S7 наход€тс€ после выполнени€ операции вычитани€ и около них поставлен знак У - У.

 

 

ѕри N=2

 

ѕоследовательности на входах четырех двухточечных блоков »ндексы членов исходной послед. »ндексы членов послед. после перестановки разр€дов
ƒес€тична€ ——   ƒвоична€ —— ƒвоична€ ——   ƒес€тична€ ——
X110 = X10 = X0        
X111 = X12 = X4        
X120 = X11= X2        
X121 = X13 =X6        
X210 = X20 = X1        
X211 = X22 = X5        
X220 = X21 = X3        
X221 = X23 =X7        

 

ѕодсчитаем количество операций умножени€, которые нужно выполнить, использу€ алгоритм Ѕѕ‘.

 

Ќомер шага разбиени€  оличество умножений на посто€нный коэффициент  оличество блоков ƒѕ‘, подлежащих дальнейшему разбиению ¬ид последовательности на входах оставшихс€ блоков
  N / 2   N / 2
  2 (N / 4) = N / 2   N / 4
  4 (N / 8) = N / 2   N / 8
. . . . . .   . . . . . .  
M -1 N / 2 2 M -1 N / 2 M -1 = 2
M N / 2 - -

 

Ќа каждом шаге разбиени€ выполн€етс€ N / 2 умножений, количество шагов равно M = log 2 N.

—ледовательно, количество умножений равно (N / 2) log2 N вместо N2 при ƒѕ‘.

¬еличина выигрыша при переходе от ƒѕ‘ к Ѕѕ‘ увеличиваетс€ с увеличением количества отсчетов N.

 

2.4. јлгоритм Ѕѕ‘ с прореживанием по частоте

 

ѕусть имеетс€ исходна€ N - точечна€ последовательность xn, где N = 2M. –азобьем члены этой последовательности на две группы. ¬ первую включим первую половину членов исходной последовательности, а во вторую группу - вторую половину. »з первой группы образуем последовательность x1m, а из второй - последовательность x2m.

»ндексы последовательностей xn и x1m св€заны соотношением n = m, а индексы последовательностей xn и x2m - соотношением n = N/ 2 + m.

“огда



<== предыдуща€ лекци€ | следующа€ лекци€ ==>
–ассмотрим отдельно четные и нечетные отсчеты спектра (отсюда и название алгоритма: прореживание по частоте) | 
ѕоделитьс€ с друзь€ми:


ƒата добавлени€: 2015-05-07; ћы поможем в написании ваших работ!; просмотров: 429 | Ќарушение авторских прав


ѕоиск на сайте:

Ћучшие изречени€:

Ќе будет большим злом, если студент впадет в заблуждение; если же ошибаютс€ великие умы, мир дорого оплачивает их ошибки. © Ќикола “есла
==> читать все изречени€...

748 - | 582 -


© 2015-2023 lektsii.org -  онтакты - ѕоследнее добавление

√ен: 0.013 с.