close

Вход

Забыли?

вход по аккаунту

?

17.Обработка информации в управляющих системах Часть I Методические указания к лабораторным работам

код для вставкиСкачать
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Министерство образования и науки Российской Федерации
Ярославский государственный университет им. П.Г. Демидова
Кафедра вычислительных и программных систем
Кафедра дифференциальных уравнений
Кафедра теории функций и функционального анализа
Обработка информации
в управляющих системах
Методические указания
к лабораторным работам
Часть I
Ярославль 2004
1
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
ББК В182я73
О 23
УДК 002:372.8
Составители А.К. Карлин, А.Д. Пендюр, Н.А. Стрелков
Обработка информации в управляющих системах. Часть I:
Метод. указания к лабораторным работам / Сост. А.К. Карлин,
А.Д. Пендюр, Н.А. Стрелков; Яросл. гос. ун-т. – Ярославль, 2004. –
19 с.
Содержатся основные теоретические положения и предлагаются
лабораторные работы для их усвоения и экспериментального подтверждения на программных моделях.
Указания предназначены для студентов, обучающихся по специальности 010200 Прикладная математика и информатика (дисциплина
“Обработка информации в управляющих системах”, блок ДС), очной
формы обучения. Могут быть использованы при выполнении расчетных, курсовых и дипломных работ.
Рецензент: кафедра теоретической информатики Ярославского
государственного университета им. П.Г. Демидова.
© Ярославский государственный университет, 2004
© А.К. Карлин, А.Д. Пендюр, Н.А. Стрелков, 2004
2
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Лабораторная работа № 1
Дискретизация аналогового сигнала.
Теорема Котельникова – Найквиста
В данной работе предлагается создать модель, иллюстрирующую
основные эффекты, возникающие при дискретизации аналоговых
сигналов.
При обработке аналогового сигнала на ЭВМ он предварительно
подвергается квантованию по времени и по уровню. Обычно квантование по уровню (обусловленное конечной разрядной сеткой ЭВМ)
оказывает незначительное влияние в силу того, что разрядные сетки
ЭВМ содержат достаточно большое число разрядов. Поэтому обычно
при анализе учитывается только квантование по времени.
В результате квантования по времени из непрерывной функции
x(t ) , где t – непрерывное время, получаем решетчатую функцию
x*[n] , где n = 0, 1, 2,… – безразмерное время. Соответственно, t = nT,
где T – период дискретизации (см. рис. 1.1).
Рис. 1.1. Дискретизация аналогового сигнала
(непрерывной функции)
Для теоретических приложений подразумевается идеальный дискретизатор, который можно представить как ключ, который замыкается с периодом T на очень короткое время. Этот процесс называют
импульсной дискретизацией. Аналитически процесс получения x*[n]
можно записать следующим образом:
3
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
x [ n] =
*
∞
∑ x(t ) ⋅ δ (t − nT ) ,
t = −∞
где δ (t ) − δ – функция.
При решении практических задач дискретизации возникают следующие вопросы:
- из каких соображений выбирать интервал дискретизации T;
- какова точность замены непрерывной функции дискретной;
- каков максимально допустимый интервал дискретизации;
- как восстановить непрерывный сигнал по известному дискретному.
Ответ на эти вопросы дает теорема Котельникова – Найквиста [1,
с. 32 – 36; 3, с. 108 – 111].
Согласно теореме Котельникова-Найквиста любую непрерывную
функцию x(t), спектр которой содержит частоты от 0 до Fc (т.е.
спектр ограничен частотой Fc и, соответственно, круговой частотой
ωc = 2πFc ), можно с любой степенью точности представить отсчета1
.
ми, следующими один за другим через интервалы времени T =
2 Fc
При таком выборе интервалов дискретизации функция x(t) однозначно представляется рядом особого вида, называемым рядом Котельникова – Найквиста:
∞
SIN (2πFc ⋅ (t − nT ))
.
(1.1)
x(t ) = ∑ x[nT ]
2πFc ⋅ (t − nT )
n = −∞
Разложение (1.1) определяет предельное (максимальное) значение интервала дискретизации T. Если для синусоиды с частотой Fc
1
, то происходит преобраинтервал дискретизации T больше, чем
2 Fc
зование частоты [5, с. 36-37]: амплитуда выходных импульсов будет
изменяться с разностной частотой ω p
ω p = ωc − r ⋅ ω0 ,
(1.2)
где ωc = 2πFc – круговая частота непрерывной функции,
ω0 = 2π / T0 – круговая частота квантователя ( T0 – интервал дискретизации);
r – ближайшее целое к ωc / ω0 .
4
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Случай ωc = rω0 (частота замыкания ключа (квантователя) совпадает или кратна частоте входной синусоиды) соответствует стробоскопическому эффекту, при котором объект, движущийся с частотой
ωc , кажется неподвижным.
Случай ωc ≠ rω0 соответствует стробоскопическому эффекту,
при котором объект, движущийся с частотой ωc , перемещается в ту
или иную сторону с разностной частотой ωc − r ⋅ ω0 . В этом случае
процесс импульсной дискретизации можно рассматривать как своеобразный преобразователь масштаба времени: периодические процессы высокой частоты преобразуются в периодические процессы
низкой частоты с сохранением их формы.
Содержание работы
Разработать программную модель, позволяющую проиллюстрировать следующую ситуацию, и дать ответы на вопросы.
Камера снимает движущуюся тележку с частотой 25 кадров в секунду. Диаметр переднего колеса тележки r1 , заднего – r2 . На колеса
нанесены различные рисунки (радиальная черта, диаметр и т.п. – в
зависимости от варианта задания).
При какой скорости движения тележки кажущееся вращение колес будет:
1) соответствовать реальности;
2) направлено в разные стороны;
3) оба будут направлены в обратную сторону.
Варианты заданий:
5
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
При необходимости увеличения числа вариантов можно предложить те же рисунки при одинаковом размере колес: r1 = r2 = 1.0 м
Лабораторная работа № 2
Фрактальное описание изображений
Целью данной лабораторной работы является ознакомление со
способом фрактального описания изображений, являющегося перспективным способом сжатия информации.
В 1988 году известные специалисты в теории динамических систем и эргодической теории Барнсли и Слоан предложили некоторые
идеи, основанные на положениях теории динамических систем для
сжатия и хранения графической информации. Они назвали свой метод методом фрактального сжатия информации.
Суть кодирования кадра (двумерное черно-белое изображение)
по Барнсли – Слоану сводится к следующему [4, с. 82 – 86]. Рассмотрим конечный набор сжимающих аффинных преобразований
S = { A1 , A2 ,..., Ak }. Такой набор называется аффинным коллажем.
Отображением данного коллажа замкнутого ограниченного множества точек (т. е. точек, составляющих изображение кадра) является изображение, полученное в результате применения преобразований коллажа к каждой точке исходного изображения. Основной теоретический результат, из которого следует принципиальная возможность
6
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
кодирования по Барнсли – Слоану, состоит в том, что отображение
фиксированного коллажа имеет, и притом единственную, неподвижную точку, т. е. такой набор точек кадра, который переводится этим
коллажем сам в себя. Неподвижная точка отображения коллажа называется аттрактором отображения. Таким образом аффинный коллаж S “кодирует” аттрактор.
Содержание работы
Построить изображение, заданное набором коэффициентов сжимающих аффинных преобразований A1 , A2 ,..., AN , где Ai (i=1,2,…,N) –
матрица коэффициентов, задающих преобразования перемещения,
поворота и изменения масштаба при переходе от системы координат
XOY к X ′O′Y ′ .
Процесс построения изображения описывается следующей последовательностью шагов:
Шаг 0. В качестве начального принимается произвольный набор
точек.
Примечание. Проделать для двух вариантов начальной картины:
1-й вариант. Начальное изображение – одна точка в начале координат.
2-й вариант. Случайное (квазипуассоновское) поле точек. Например, взять число точек T = 1000. Координаты точек получить, используя датчик Random.
Шаг 1. Для получения координат всех точек изображения последующего шага координаты точек изображения данного шага преобразуются согласно следующим выражениям:
x
( i )'
j
= ai x j + bi y j + ci ;
( i )'
= d i x j + ei y j + f i ;
yj
i = 1,2,..., N ; j = 1,2,..., M ;
N – число аффинных преобразований;
M – число точек (пиксель) на данном шаге;
ai , bi , ci , d i , ei , f i – коэффициенты аффинного преобразования Ai .
Шаг 2. Перейти к шагу 1. При получении аттрактора (неменяющейся картины) – останов.
Примечание. Для лабораторных работ число итераций 8 – 16.
Размеры изображений в лабораторных работах 2Lx2L, где L=60.
7
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Пример.
Число аффинных преобразований равно N = 4. Матрицы коэффициентов аффинных преобразований:
A1 :
0.14
0
0
0
0.9
5
A2 :
0.67
0
0
0.75
0
20
-0.3546
0.1231
-25
-45
A3 :
0.277
0.1576
A4 :
0.2893
0.3447
30
-0.1532
0.1286
-45
1-й вариант. Начальное изображение – одна точка в начале координат. Процесс построения изображения имеет следующий вид:
8
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
2-й вариант. Случайное (квазипуассоновское) поле точек. Число
точек T = 1000. Процесс построения изображения имеет следующий
вид:
Варианты заданий:
1. Коэффициенты преобразований A1 , A2 , A3 :
0.2774 0.0000 0.0000 A2 :
0.1995
A1 :
0.0000 0.9025 5.0000
0.1927
0.1995 0.6269 0.0000
A3 :
-0.1927 0.6492 -5.0000
9
-0.6269 0.0000
0.6492 -5.0000
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
2. Коэффициенты преобразований A1 , A2 , A3 , A4 :
0.2168
-29.0000 A2 : 0.2844
0.2168
A1 : 0.2844
-0.4926 0.1252
23.0000
-0.4926 0.1252
-0.2250 16.0000 A4 : 0.2493
-0.2250
A3 : 0.2493
0.5112
0.1097
-16.0000
0.5112
0.1097
-6.0000
-16.0000
34.0000
20.0000
3. Коэффициенты преобразований A1 , A2 , A3 , A4 :
0.0000
0.0000
0.0000
A1 : 0.3474
A2 : 0.3074
0.0000
0.6634
20.0000
0.0000
0.6634
0.0000
-20.0000 A4 : 0.6709
0.0000
A3 : 0.6709
0.0000
0.2920
0.0000
0.0000
0.2920
0.0000
-20.0000
19.00000
0.0000
4. Коэффициенты преобразований A1 , A2 , A3 , A4 :
-0.3815 -15.0000 A2 : -0.3887 0.3566
A1 : 0.3616
0.4016
0.3435
0.0000
-0.3754 -0.3693
0.3235
0.0000
0.3235
A3 : 0.0000
A4 : 0.0000
-0.5404 0.0000
28.0000
-0.5404 0.0000
16.0000
0.0000
0.0000
-27.0000
5. Коэффициенты преобразований A1 , A2 , A3 , A4 :
0.0000
-11.0000 A2 : 0.8125
0.0000
A1 : 0.8125
0.00000 0.2146
0.0000
0.0000
0.2146
-0.1544 0.0000
0.1544
A3 : 0.5644
A4 : 0.5644
0.5844
0.1491
0.0000
-0.5844 0.1491
12.0000
0.0000
0.0000
0.0000
6. Коэффициенты преобразований A1 , A2 , A3 , A4 :
0.0000
2.0000
0.0000
A1 : 0.7351
A2 : 0.7351
0.0000
0.2635
44.0000
0.0000
0.2635
-0.2635 -43.0000 A4 : 0.0000
0.2635
A3 : 0.0000
0.7351
0.0000
0.0000
-0.7351 0.0000
1.0000
-43.0000
44.0000
0.0000
7. Коэффициенты преобразований A1 , A2 , A3 , A4 :
-0.3815 -15.0000 A2 : -0.3566 0.3693
A1 : 0.3435
0.3815
0.3435
18.0000
-0.3693 -0.3566
17.0000 A4 : 0.3693
A3 : -0.3566 0.3693
10
17.0000
-14.0000
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
8. Коэффициенты преобразований A1 , A2 , A3 :
0.2531
-25.0000 A2 : 0.3435
-0.2531
A1 : 0.3435
-0.3815 0.2279
25.0000
0.3815
0.2279
0.000
1.0000
A3 : 0.5133
0.000
0.3406
-21.0000
24.0000
23.0000
9. Коэффициенты преобразований A1 , A2 , A3 :
0.3222
-20.0000 A2 : 0.3392
-0.3222
A1 : 0.3392
-0.6955 0.1571
16.0000
0.6955
0.1571
0.0000
0.0000
A3 : 0.2635
0.0
0.5257
-27.0000
20.0000
14.0000
10. Коэффициенты преобразований
0.0000
-36.0000 A2 :
A1 : 0.3923
0.0000
0.4325
34.0000
0.0000
37.0000 A4 :
A3 : 0.3923
0.0000
0.4325
-34.0000
0.0000
0.0000
A5 : 0.3923
0.0000
0.4325
0.0000
A1 , A2 , A3 , A4 , A5 :
0.3923
0.0000
0.0000
0.4325
0.3923
0.0000
0.0000
0.4325
-36.0000
-34.0000
37.0000
35.0000
11. Коэффициенты преобразований
-0.3508 -26.0000 A2 :
A1 : 0.3566
0.3693
0.3388
26.0000
-17.0000 A4 :
A3 : -0.3815 0.3263
-0.3435 -0.3624 14.0000
A1 , A2 , A3 , A4 :
0.3566
-0.3508
0.3693
0.3388
-0.3815 0.3263
-0.3435 -0.3624
26.0000
-25.0000
14.0000
-14.000
12. Коэффициенты преобразований
0.3271
-27.0000 A2 :
A1 : 0.2798
-0.3107 0.2945
24.0000
0.3271
23.0000 A4 :
A3 : 0.2798
-0.3107 0.2945
-22.0000
A1 , A2 , A3 , A4 :
0.2798
0.3271
-0.3107 0.2945
0.2798
0.3271
-0.3107 0.2945
23.0000
24.0000
-27.0000
-22.0000
11
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
13. Коэффициенты преобразований
0.0000
-32.0000 A2 :
A1 : 0.4633
0.0000
0.2378
45.0000
-0.2378 -1.0000 A4 :
A3 : 0.0000
0.4633
0.0000
0.0000
A1 , A2 , A3 , A4 :
0.0000
0.2378
-0.4633 0.0000
0.0000
0.2378
-0.4633 0.0000
-1.0000
32.0000
-1.0000
-32.0000
14. Коэффициенты преобразований
0.0000
0.0000
A1 : 0.8780
A2 :
0.6129
0.3074
0.0000
0.0000
0.0000
A3 : 0.1608
A4 :
0.0000
0.1661
40.0000
0.0000
-45.0000 A6 :
A5 : 0.1608
0.0000
0.1661
0.0000
A1 , A2 , A3 , A4 , A5 , A6 :
0.8780
0.0000
-0.7049 0.3074
0.1608
0.0000
0.0000
0.1661
0.1608
0.0000
0.0000
0.1661
0.0000
0.0000
0.0000
-45.0000
45.0000
0.0000
15. Коэффициенты преобразований
-0.4597 -17.0000 A2 :
A1 : 0.2579
0.2490
0.4760
16.0000
0.0000
0.0000
A3 : 0.6025
A4 :
0.0000
0.4804
-14.0000
A1 , A2 , A3 , A4 :
0.2207
0.5215
-0.2825 0.4074
0.2273
0.0000
0.0000
0.8969
17.0000
17.0000
0.0000
6.0000
16. Коэффициенты преобразований
-6.0000 A2 :
A1 : -0.6707 0.2525
-0.6039 -0.2804 -8.0000
0.0000
0.0000
A3 : 0.1937
A4 :
0.0000
0.8237
11.0000
A1 , A2 , A3 , A4 :
17. Коэффициенты преобразований
-38.0000 A2 :
A1 : -0.3585 0.0000
0.0000
-0.3074 -40.0000
38.0000 A4 :
A3 : -0.3585 0.0000
0.0000
-0.3074 -41.0000
0.0000
A5 : -0.6154 0.0000
-0.1705 43.0000
A1 , A2 , A3 , A4 , A5 :
12
-0.7654
0.4783
0.5610
0.0000
-0.3585
0.0000
-0.1937
0.0000
-0.2000
-0.3200
0.0000
0.3444
0.0000
-0.3074
0.0000
-0.5007
6.0000
-11.0000
0.0000
16.0000
0.0000
-12.0000
0.0000
13.0000
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Лабораторная работа № 3
Спектры Фурье при анализе сигналов
Целью данной лабораторной работы является ознакомление со
спектрами Фурье и их свойствами.
Преобразования Фурье являются стандартным инструментом обработки сигналов. Для решетчатой функции x[n], n=0,1,2… определены два Фурье-представления [1, с. 43 – 58; 3, с. 115 – 142]:
1) в виде дискретного ряда Фурье (ДРФ):
X (ω ) =
*
∞
∑ x[n] ⋅ exp(− jωn) ,
n = −∞
(1)
где j – мнимая единица,
ω – безразмерная частота,
n – безразмерное время,
для которого обратное преобразование от изображений к оригиналам
имеет вид:
1 π *
(2)
x[n] =
X (ω ) ⋅ exp( jωπ )dω ;
2π −∫π
2) в виде дискретного преобразования Фурье (ДПФ):
N −1
2π
1
(3)
nk ) , k = 0,1,2,..., ( N − 1) ,
X [k ] = N ∑ x[n] ⋅ exp(− j
N
n =0
где N – длина выборки для решетчатой функции x[n].
Обратное преобразование от изображений к оригиналам имеет
вид:
N −1
2π
(4)
nk ) , n = 0,1,2,..., ( N − 1) .
x[n] = ∑ X [k ] ⋅ exp( j
N
k =0
В качестве синонима понятия преобразования Фурье часто используют термин спектр, а какой именно спектр (ДРФ или ДПФ) или
дополнительно оговаривается, или это ясно из контекста.
Свойства ДРФ и ДПФ достаточно полно обсуждаются в [2]. В последние десятилетия более часто упоминается ДПФ в связи с тем, что
для него были найдены быстрые алгоритмы вычислений (БПФ). Наиболее часто отмечаемые свойства спектров: 1) частотная селективность (на графических изображениях спектров хорошо различимы
гармонические компоненты разных частот); 2) изображение свертки
13
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
сигналов (последнее является произведением изображений сворачиваемых сигналов – это свойство спектров используется для ускоренных вычислений свертки с использованием БПФ).
Для ДПФ спектр X[k] (сказанное ниже полностью переносится и
на случай спектра ДРФ X (ω ) ) является комплексным числом и в зависимости от способа записи комплексного числа:
X [k ] = Re{ X [k ]} + j ⋅ Im{X [k ]}
или X [k ] = A[k ] ⋅ exp{ j ⋅ ϕ[k ]}
компоненты спектра носят названия:
Re{X[k]} – вещественная часть спектра;
Im{X[k]} – мнимая часть спектра;
A[k] – амплитудный спектр;
ϕ[k ] – фазовый спектр.
Амплитудный спектр A[k ] = X [k ] , k = 0,1,2,..., ( N − 1) интересен
тем, что он инвариантен к сдвигам (т.е. не меняется при сдвигах) сигнала во времени.
N
Амплитудный спектр имеет ( + 1) независимых спектральных
2
точек ДПФ, когда x[n] является последовательностью действительных чисел. График амплитудного спектра имеет вид решетчатой
функции, точки которой зеркально симметричны относительно середины интервала наблюдения.
Содержание работы
1. Вычислить и построить графики ДПФ сигнала x[n],
n=0,1,2,…,(N-1) указанного в задании: вещественную часть спектра,
мнимую часть спектра, амплитудный спектр.
2. Построить те же графики для сигнала x[n ± T ] , T = const сдвинутого на T-тактов (кольцевой сдвиг – т. е. участки сигнала, выходящие за границы интервала наблюдения n=0,1,2,…, (N-1) с одной стороны, появляются с другой стороны этого интервала);
3. Построить те же графики для сигнала x[n], n=0,1,2,…, (N-1)
плюс белый шум с дисперсией D.
Рекомендуемые значения параметров: N=512; D=0.05,0.1,0.15;
T=50,100,150.
14
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Пример
Сигнал:
X[n]=(1[n]-1[n-256])(30+45SIN(0.3n) + 1[n-256](30+45SIN(0.1n) ,
n=0,1,…,512 ,
1, при n ≥ 0 ;
где 1[n] = 
0, при n < 0 .
Графики ДПФ имеют следующий вид:
Для сдвинутого сигнала x[n+100] графики принимают следующий вид:
Варианты заданий:
1) x[n]=(1[n]-1[n-N/2])SIN(0.2n)+(1[n-N/2]-1[n-N])SIN(0.05n);
2) x[n]=(1[n]-1[n-N])(SIN(0.2n)+SIN(0.05n));
15
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
3) x[n]=(1[n]-1[n-N/2])SIN(0.3n)+(1[n-N/2]-1[n-N])SIN(0.01n);
4) x[n]=(1[n]-1[n-N])(SIN(0.3n)+SIN(0.01n));
5) x[n]=(1[n-200]-1[n-300]);
6) x[n]=(1[n-100]-1[n-200]);
7) x[n]=(1[n-200]-1[n-300])SIN(0.2n);
8) x[n]=(1[n-100]-1[n-200])SIN(0.4n);
9) x[n]=(1[n]-1[n-N/2])COS(0.2n)+(1[n-N/2]-1[n-N])COS(0.05n);
10) x[n]=(1[n]-1[n-N])(COS(0.2n)+COS(0.05n));
11) x[n]=(1[n]-1[n-N/2])COS(0.3n)+(1[n-N/2]-1[n-N])COS(0.01n);
12) x[n]=(1[n]-1[n-N])(COS(0.3n)+cos(0.01n));
13) x[n]=(1[n-200]-1[n-300])COS(0.2n);
14) x[n]=(1[n-100]-1[n-200])COS(0.4n);
1, при n ≥ 0 ;
где 1[n] = 
0, при n < 0 .
Лабораторная работа № 4
Быстрое преобразование Фурье (БПФ)
Целью данной лабораторной работы является освоение алгоритма
БПФ и написание программы, реализующей этот алгоритм.
Фактически широкое применение дискретного преобразования
Фурье (ДПФ) (см. также лабораторную работу № 3) в науке и технике
началось с разработки методов вычисления ДПФ N-точечных последовательностей при больших N, предложенных Кули и Тьюки. Эти
методы назвали алгоритмами быстрого преобразования Фурье. Сейчас известен ряд методов выполнения БПФ.
Алгоритмы БПФ не применяются в тех случаях, когда число точек в последовательности является простым, но при N сложносоставном (т. е. имеющем много сомножителей) сокращение объема вычислений может быть значительным. Когда N является степенью двойки
(т. е. состоит из максимального числа сомножителей), алгоритмы
БПФ требуют проведения числа вычислений, пропорционального
N log 2 N (т. е. O( N log 2 N ) ), а не O( N 2 ) , требуемых при непосредственном просчете ДПФ по формуле
16
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
2π
(1)
nk ) , k = 0,1,2,..., ( N − 1) .
N
n =0
Существует два класса алгоритмов БПФ, и каждый класс имеет
множество модификаций [3, с. 123 – 142]. Рассматриваемый в данной
лабораторной работе алгоритм относится к классу алгоритмов БПФ с
прореживанием по времени и вычислением “на месте” (in place), т. е.
не требует дополнительных массивов памяти для хранения промежуточных результатов.
Детальный вывод алгоритма можно найти в [3, с. 128 – 131].
Приведем окончательный вариант алгоритма, оформленный в виде
рекурсивной процедуры [4, с. 45 – 50, 60 – 62]. Для двухточечной последовательности, т. е. N=2, ДПФ, выполняемое по формуле (1), совпадает с БПФ. Две компоненты спектра в этом случае вычисляются
следующим образом:
X [0] = x[0] + x[1];
(2)
X [1] = x[0] − x[1] .
Отсюда вариант процедуры, вычисляющей БПФ так, чтобы в
итоге на месте входной последовательности x[n], n=0,1,2…,N получился спектр X[k], k=0,1,2,…,N, следующий:
Процедура БПФ(N,x)
1. if N=2 then
BEGIN
2. Замена x[0] на X [0] = x[0] + x[1] и x[1] на X [1] = x[0] − x[1] ;
3. RETURN
END
ELSE
BEGIN
4. Определить функцию g[m] как состоящую из всех четных по n
значений x[n] и функцию h[m] из всех нечетных по n значений x[n],
т. е.
N
g[m] = x[2n], n = 0,1,2,..., − 1;
2
N
(3)
h[m] = x[2n + 1], n = 0,1,2,..., − 1;
2
5. CALL procedure БПФ(N/2, g);
6. CALL procedure БПФ(N/2, h);
7. Замена x[n] на X [k ] , где
X [k ] =
N −1
1
N
∑ x[n] ⋅ exp(− j
17
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
N
− 1;
2
N
N
(4)
X [k ] = G[k − N2 ] − WNk H [k − ], при k = ,..., N − 1;
2
2
2π
где WN = exp{− j }.
N
END.
Для того чтобы полученные значения спектра X [k ] были расположены в порядке возрастания, исходные данные x[n] должны быть
расположены в “двоично-реверсированном порядке”: новый порядковый номер получается чтением в обратном порядке двоичного номера
исходной последовательности.
Пример
Для восьмиточечной последовательности:
Исходная
последовательность: x[0] x[1] x[2] x[3] x[4] x[5] x[6] x[7]
Двоичная запись
номера:
000 001 010 011 100 101 110 111
Обратная двоичная
запись номера:
000 100 010 110 001 101 011 111
Новая
последовательность: x[0] x[4] x[2] x[6] x[1] x[5] x[3] x[7]
Содержание работы
Проделать пункт 1 лабораторной работы № 3 для N=512, 1024,
2048, используя алгоритм БПФ. Сравнить время счета при прямом
подсчете ДПФ и счете по алгоритму БПФ.
X [k ] = G[k ] + WNk H [k ], при k = 0,1,...,
ЛИТЕРАТУРА
1. Арутюнов П.А. Теория и применение алгоритмических измерений. М.: Энергоатомиздат, 1990.
2. Дьюдни Ф.К. Аффинные преобразования и фрактальные структуры // В мире науки. 1990. №7.
3. Залманзон Л.Н. Преобразования Фурье, Уолша, Хаара и их
применение в управлении,связи и других областях. М.: Наука, 1989.
4. Павлидис Т. Алгоритмы машинной графики и обработки изображений. М.: Радио и связь. 1986.
5. Цыпкин Я.З. Теория линейных импульсных систем. М.: Физматгиз, 1963.
18
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Учебное издание
Обработка информации
в управляющих системах
Часть I
Составители: Карлин Анатолий Кузьмич
Пендюр Анатолий Дементьевич
Стрелков Николай Александрович
Редактор, корректор В.Н. Чулкова
Компьютерная верстка И.Н. Ивановой
Подписано в печать 15.12.04. Формат 60х84/16. Бумага тип.
Усл. печ. л. 0,93. Уч.-изд.л. 0,8. Тираж 60 экз. Заказ
Оригинал-макет подготовлен
в редакционно-издательском отделе ЯрГУ
Отпечатано на ризографе
Ярославский государственный университет.
150000 Ярославль, ул.Советская, 14.
19
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
20
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Обработка информации
в управляющих системах
Часть I
21
Документ
Категория
Без категории
Просмотров
8
Размер файла
267 Кб
Теги
указания, методические, управляющем, система, часть, работа, информация, обработка, лабораторная
1/--страниц
Пожаловаться на содержимое документа