Цифровая обработка ТВ сигналов. Часть 1. Бобрешов А.М - 23 стр.

UptoLike

ВУЗ: 

ВГУ | Воронеж

Составители: 

Рубрика: 

23
Следует иметь в виду , что в различных литературных источниках
запись соотношений для ДПФ и ДКП может быть различной . В соотношениях
(2.8)-(2.15) нормирующие показатели вида
N
1
или
MN
1
введены и в прямое
и в обратное преобразования. В то же время в (1.9)-(1.11) нормирующий
множитель имеется только в выражениях для прямого преобразования, как
обычно делается в справочниках по высшей математике. В технической
литературе встречаются оба варианта записи для ДПФ и ДКП.
Оценим количество операций , необходимых для вычисления ДПФ в
соответствии с (2.9). Для этого преобразуем (2.9), выделив в нем операции над
действительными частями чисел
,)]Im()()Re()([
1
)(
1
0
.
∑
−
=
+⋅=
N
n
kn
N
kn
N
WnjxWnx
N
kX
(2.16)
где k=0,1,… ,N-1; .
)
2
( nk
N
j
kn
N
eW
π
=
При этом учитывается, что значения сигнала x(n) являются
действительными числами.
Из (1.20) видно , что для вычисления одного значения X(k) необходимо
выполнить приблизительно 2N умножений и (2N-2) сложений действительных
чисел. Для вычисления всех N значений X(k) надо выполнить 2N
2
умножений и
N(2N-2) сложений действительных чисел. Кроме того, требуется ЗУ для
хранения значений x(n), X(k) и W
kn
N
.
Выполнение обратного ДПФ потребует в два раза больше операций , так
как значения X(k) являются комплексными числами и число слагаемых
увеличится вдвое.
В целом можно оценить затраты вычислительных ресурсов при
выполнении прямого и обратного ДПФ как пропорциональные N
2
. Аналогично
можно показать, что вычисление двумерных прямого и обратного ДПФ требует
выполнение количества операций , пропорционального N
2
M
2
.
Например, вычисление ДПФ для квадратного блока изображения,
содержащего 8х 8 элементов (пикселов), потребует выполнения примерно
16х 10
3
операций умножения и сложения. А вычисление ДПФ черно - белого
телевизионного кадра обычного стандарта разложения, содержащего 720х 576
пикселов, потребует выполнения около 8 х 10
11
операций . Если вычисления
производятся на компьютере, выполняющим 10
6
операций над
действительными числами в секунду , время вычисления ДПФ составит 8х 10
5
с
или более 200 ч. Очевидно , что для вычисления ДПФ телевизионных
изображений в реальном времени , т.е. за период кадровой развертки ,
необходимо искать пути сокращения количества требуемых операций .
Наиболее радикальный способ уменьшения объема вычислений
заключается в применении открытых в 60-е годы быстрых алгоритмов ДПФ,
называемых алгоритмами быстрого преобразования Фурье ( БПФ ). Подход
основан на использовании периодичности экспоненциальных функций типа
W
N
kn
= e
-j(2π /N)nk
и их симметрии относительно перестановки множителей n, k . В 
                                                  23
     Следует им еть в виду, что в различны х литературны х источниках
запись соотнош ений для Д ПФ и Д КП м ож ет бы ть различной . В соотнош ениях
                                                       1         1
(2.8)-(2.15) норм ирую щ иепоказатели вида                 или        введены и впрям ое
                                                       N         MN
и в обратное преобразования. В то ж е врем я в (1.9)-(1.11) норм ирую щ ий
м нож итель им еется только в вы раж ениях для прям ого преобразования, как
обы чно делается в справочниках по вы сш ей м атем атике. В технической
литературевстречаю тся оба варианта записи для Д ПФ и Д КП.
      О ценим количество операций , необходим ы х для вы числения Д П Ф в
соответствии с (2.9). Д ля этого преобразуем (2.9), вы делив в нем операции над
дей ствительны м и частям и чисел
                 1 N −1
      X (k ) =     ⋅ ∑ [ x (n ) Re(WNkn ) + jx (n ). Im(WNkn )],           (2.16)
                 N n =0
                     kn             2π
                               j(      ) nk
гдеk=0,1,… ,N-1; W   N    =e        N
                                              .

      П ри этом учиты вается, что значения сигнала x(n) являю тся
дей ствительны м и числам и.
      И з (1.20) видно, что для вы числения одного значения X(k) необходим о
вы полнить приблизительно 2N ум нож ений и (2N-2) слож ений дей ствительны х
чисел. Д ля вы числения всех N значений X(k) надо вы полнить2N2 ум нож ений и
N(2N-2) слож ений дей ствительны х чисел. К ром е того, требуется ЗУ для
хранения значений x(n), X(k) и WknN .
      В ы полнение обратного Д ПФ потребует в два раза больш е операций , так
как значения X(k) являю тся ком плексны м и числам и и число слагаем ы х
увеличится вдвое.
      В целом м ож но оценить затраты вы числительны х ресурсов при
вы полнении прям ого и обратного Д ПФ как пропорциональны е N2. А налогично
м ож но показать, что вы числениедвум ерны х прям ого и обратного Д ПФ требует
вы полнениеколичества операций , пропорционального N2M2.
      Н априм ер, вы числение Д ПФ для квадратного блока изображ ения,
содерж ащ его 8х 8 элем ентов (пикселов), потребует вы полнения прим ерно
16х 103 операций ум нож ения и слож ения. А вы числение Д ПФ черно-белого
телевизионного кадра обы чного стандарта разлож ения, содерж ащ его 720х 576
пикселов, потребует вы полнения около 8х 1011 операций . Е сли вы числения
производятся на            ком пью тере,   вы полняю щ им   106    операций     над
дей ствительны м и числам и в секунду, врем я вы числения Д ПФ составит 8х 105 с
или более 200 ч. О чевидно, что для вы числения Д ПФ телевизионны х
изображ ений в реальном врем ени, т.е. за период кадровой развертки,
необходим о искатьпути сокращ ения количества требуем ы х операций .
      Н аиболее радикальны й способ ум еньш ения объ ем а вы числений
заклю чается в прим енении откры ты х в 60-е годы бы стры х алгоритм ов Д П Ф ,
назы ваем ы х алгоритм ам и бы строго преобразования Ф урье (Б ПФ ). П одход
основан на использовании периодичности экспоненциальны х функций типа
WNkn = e-j(2π /N)nk и их сим м етрии относительно перестановки м нож ителей n, k . В

Страницы