Курс лекций дисциплины вариативной части математического и естественнонаучного цикла (855805), страница 15

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 15)

относительная погрешность  = 2N −1 .122Это означает, что для решения данной задачи с точностью не хуже 5%(δ<0.05)необходимодискретизироватьсигналсчастотойнеменее50 ⋅ 126 = 6300 Гц (надо помнить о других составляющих погрешности –например: погрешность квантования АЦП, поэтому реальная частотадискретизации должна быть еще больше).Тогда алгоритм, выполняемый блоком обработки (БЦОС), состоит всуммировании квадратов 126 отсчетов (или более), поступающих от АЦП, ивычислении амплитуды как корня квадратного из деленного на 252 результатасуммирования: A =0.5 125[u д (n )]2 (с позиций эффективности вычислений∑126 n =0удобно выбрать N=128).В результате такой цифровой обработки определяется параметр сигнала– амплитуда, которая характеризует физический процесс– уровеньнапряжения в сети.При этом в виду независимости обрабатываемого сигнала от системыобработки необходимо учитывать следующие факторы:− начальная фаза сигнала неизвестна (относительно фронта тактирования)поэтому алгоритм обработки не должен зависеть от начальной фазысигнала, в т.ч.

от момента его поступления;− сигнал всегда содержит помехи и/или шумы, поэтому всегда надоучитывать возможность представления такого сигнала в разрядной сетке (втом числе при накопительном взвешивании и сложении отсчетов), а приналичии операций сравнения не использовать команд точного равенства(заменять командами попадания значения в интервал);− выбор частоты дискретизации сигнала должен быть основан не только наоснове теоремы отсчетов (т.е. полосе сигнала), но в соответствии стребованиями к результату обработки (т.е. с учетом параметров алгоритмаобработки).1234.1 Вычислительная сложность алгоритмаПреимущества ЦОС достигается не только за счет возможностиприменения развитого математического аппарата (в отличие от возможностейфизики при аналоговой обработке). Главным преимуществом являетсявозможность реализации алгоритмов ЦОС на электронно-вычислительныхустройствах (для простоты процессорах), которые в отличие от аналоговыхустройств не подвержены влиянию внешних факторов на работу алгоритма.ЭтомогутбытьобыкновенныеПЭВМ,серверыит.п.,атакжеспециализированные микросхемы, представляющие собой, как правило,«систему на кристалле» (микроконтроллеры, цифровые процессоры обработкисигналов и прочие).Поскольку каждый процессор, как цифровое устройство, функционируетна основе тактирующей системы, т.е.

каждая команда выполняется законечное число тактов (или циклов процессора) – за конечное время. Поэтомукоманды сложения, умножения выполняются также за конечное число тактов.С другой стороны разнообразие процессоров и их реализации делаетнеудобным использование числа тактов для сравнения производительности исложности алгоритмов. Поэтому сложность алгоритмов сравнивают по числуопераций сложения и умножения. Операции сложения, как правило,выполняются быстрее. Поэтому, исторически так сложилось, алгоритмы спреобладанием операций сложения считаются лучше, чем их же реализации наоснове операций умножения (при одинаковом числе всех операций).Пример 1.Рассмотрим реализацию КИХ фильтра с линейной фазой, содержащегоM коэффициентов (пусть M-четно):y (k ) =M −1∑ bm x(k − m )m =0Для вычисления одного выходного отсчета необходимо ровно M умножений иM-1 сложение на каждый отсчет выходного сигнала.

Это и определяетвычислительную сложность этого простейшего алгоритма.124Однако, учитывая симметричность коэффициентов фильтра, количествоумножений можно уменьшить в два раза, если сгруппировать слагаемые:y (k ) =0.5 M −1∑ bm [x(k − m ) + x(k − m + M − 1)], при таком же числе сложений.m =0Пример 2.Рассмотрим реализацию ДПФ (N точек):1X (n ) =NN −1∑ x(k ) ek =0−j2 nkN=1NN −1k =0 2n  2n k  + j sin k  N  N ∑ x(k )cosОчевидно, аргумент тригонометрических функций не зависит от отсчетовсигнала, как и результат вычисления функций cos и sin – поэтому их можновычислить заранее и хранить в виде таблицы коэффициентов, в эти жекоэффициенты можно включить деление на N (это возможно, если длина ДПФизвестна и фиксирована).

Тогда расчет действительной и мнимой частейспектра при действительном входном сигнале осуществляется по формулам:X re (n ) =1N 2n ∑ x(k )cos N k  ,k =0N −1X im (n ) =1NN −1 2n k N ∑ x(k )sink =0Это требует 2N умножений и 2N-2 сложений на каждый частотный отсчет(бин) ДПФ.

Всего отсчетов N, поэтому для полного вычисления N точечногоДПФ необходимо выполнить 2N2 умножений и 2N(N-1) сложений. Однако,учитываясимметриюспектрадействительногосигнала,напрактикевычисляют только 0.5N отсчетов. В результате вычислительная сложностьалгоритма расчета спектра сигнала из N отсчетов определяется как0.5 N ⋅ 2 N = N 2 умножений и 0.5 N ⋅ 2( N − 1) = N 2 − N сложений.Поэтому, например, в случаях, когда необходимо рассчитать не весьспектр сигнала, а только его малую часть, вместо реализации алгоритмарасчета ДПФ можно применить более простые в вычислительном контекстеалгоритмы.1254.1.1 Алгоритм ГерцеляРассмотрим импульсную характеристику отдельного канала ДПФhn (k ) = ej2 nkN, обозначим W = e−j2N. Тогда спектральную плотность сигналаможно представить в виде:N −1X (n ) = ∑ x(k ) ej2 n( N −k )Nk =0= x(0 )(W −n ) + x(1)(W −n )N −1N+ ... ++ x( N − 2 )(W −n ) + x( N − 1)(W −n )21Для фиксированного частотного отсчета n можно вынести множитель W − n :[]X (n ) = x(0 )(W −n ) + x(1)(W −n ) + ...

+ x( N − 2 )(W −n ) + x( N − 1) (W −n ) ,N −1N −21y N −1затем в выражении yN-1 повторить операцию и т.д.:  X (n ) =  ...(x(0)W −n + x(1))W −n + ... W −n + x( N − 2)W −n + x( N − 1)W −n  y1 yN −2y N −1Таким образом, процесс вычисления представим в виде рекуррентногосоотношения: yi = yi −1W − n + x(i ) , при y −1 = 0 .

После вычисления N-1 итерациизначениерекурсивнойфункциисовпадетсчастотнымотсчетом:X (n ) = y N −1W − n . Рекурсивное выражение можно интерпретировать как БИХфильтр первого порядка (но с комплексным коэффициентом) – рис. 4.6.Функция передачи этого фильтра имеет вид: Pn ( z ) =сравнитьеесфункциейпередачиканала1. Интересно1 − W −n z −1ДПФ:H n (z ) =1 − z−N1− ej2 nNz −1(отличаются числителем – при рассмотрении выборки N входных отсчетовзадержка на N тактов не влияет на результат и формулы совпадают).126x(i)y(i)()Y ( z ) 1 − W − n z −1 = X ( z )+z-1W-nРис. 4.6 – Реализация рекурсивной функции в виде БИХ фильтраЧтобы избежать комплексных операций на каждой итерации знаменательфункции передачи умножают на комплексно-сопряженное число, тогда можнополучить:−j2 nN1− ez −1Pn = 2n  −1−21 − 2 cosz + z N Этот фильтр представим каскадным соединением КИХ фильтра (рис.4.7)Pn′ = 1 − e−j2 nNz −1 и БИХ фильтра Pn′′ =x(i)1−11 − z + z−2 2n , где  = 2 cos. N vi+z-1+y(i)z-1-W-nαz-1-1БИХ частьКИХ частьРис.

4.7 – Реализация рекурсивной функции в виде БИХ фильтра 2-го порядкаСоответственно получается БИХ фильтр второго порядка, но уже сдействительными коэффициентами {α, -1}. Комплексное значение числителяW =en−j2 nN(реализация КИХ части) участвует в процессе вычислений одинраз – после последней итерации (при i=N-1), т.к. промежуточные значения yiинтереса не представляют. Описанный процесс фильтрации известен какалгоритм Герцеля (был предложен Джеральдом Гёрцелем (Goertzel) в 1958127году).

Вычислительная сложность алгоритма состоит в выполнении 2Nсложений (одно из них комплексное) и N умножений (одно из нихкомплексное). Несомненным достоинством алгоритма является минимальныетребования к памяти (для хранения промежуточных результатов) – для расчетатекущего значения vi одновременно надо «помнить» только два отсчета vi-1 иvi-2: vi = xi + vi −1 − vi −2 .Пример применения алгоритма Герцеля.Пустьнеобходимовдискретном сигнале произвольнойформыобнаружить тон (гармоническую составляющую) с известной частотойf0=1 кГц (подобная задача возникает при обнаружении сигнала в системахдекодирования, распознавания, управления, передачи данных и т.п.).Полагаем, что сигнал дискретизирован с частотой fs=10 кГц и имеетсяN=200 отсчетов сигнала (в памяти воображаемого устройства обработки).Тогда интересующий нас спектральный компонент имеет номер n =j 40 поэтому  = 2 cos ≈ 1.618034 , e 200 2 nNf0N = 20 ,fs= e j 36° .Тогда необходимо вычислить vi = xi + 1.618034vi −1 − vi −2 для каждогоi = 0,...,199 иX (20) = v199 − v198 e j 36° – значение спектральной плотности,амплитуда A20 =2X (20) .NВ качестве тестовых сигналов рассмотрим сигналы:x1 (n ) = sin (100nt s ) + 5 sin (2000nt s ) содержащий тон 1 кГц иx2 (n ) = sin (100nt s ) + 5 sin (1000nt s ) не содержащий такого тона.N=200;Fs=10000; %частота дискретизации%создаем сигналыt=2*3.1415/Fs*(0:N-1);x1=sin(50*t)+5*sin(1000*t);x2=sin(50*t)+5*sin(500*t);v(1)=0; %инициализация промежуточных переменныхv(2)=0;128for i=1:Nv(3)=x1(i)+1.618034*v(2)-v(1); %рекурсивная функцияfor j=1:2 %осуществление задержкиv(j)=v(j+1);end;end;y=v(2)-v(1)*(0.80902+0.58779i); %комплексное умножение на ej36ºA20=abs(y)/N*2; %вычисление амплитуды тонаТаблица 4.1x2Сигналx1X(20)=y-293.83 +404.55i0.0006 - 0.0015i5.01.6e-5Тон обнаруженТон отсутствуетA20ВыводыЭту же задачу можно было бы решить, применяя свойства корреляционнойфункции.

Однако в этом случае, число операций сложения и умножения былобы порядка 2N 2.N=200;Fs=10000;%создаем сигналыt=2*3.1415/Fs*(0:N-1);x1=sin(50*t)+5*sin(1000*t);x2=sin(50*t)+5*sin(500*t);x=sin(1000*t); %сигнал – эталон%расчет корреляционной функцииfor i=-N+1:N-1q1=0;q2=0;for j=-N+1:N-1m=i+j;if (m>=1)&&(m<=N)&&(j>=1)&&(j<=N)q1=q1+x(j)*x1(m);q2=q2+x(j)*x2(m);end;end;y1(i+N)=q1; %отсчеты корреляционной функции эталона и x1y2(i+N)=q2; %отсчеты корреляционной функции эталона и x2end;129y1(n)отсчеты nРис. 4.8 – Корреляционная функция эталонного сигнала с сигналом x1Анализируя отсчет y(0) по уровню и наблюдая симметричную функцию можнодостоверно сделать вывод о наличии тона с амплитудой2 y (0 )=5.Ny2(n)отсчеты nРис. 4.9 – Корреляционная функция эталонного сигнала с сигналом x2Анализируя отсчет y(0) по уровню и наблюдая несимметричную функциюможно достоверно сделать вывод об отсутствии тона.1304.2 Быстрое преобразование ФурьеМногообразие задач требующих вычисления ДПФ требуют эффективнойреализации алгоритма расчета спектральных коэффициентов, т.к.

Характеристики

Список файлов лекций