ЦОРиИ

Контрольное задание №20

1 Изобразитьпроизвольную дискретную последовательность, записанную в виде суммы взвешенных и задержанных цифровых единичных отсчетов,

Решение:

Произвольный дискретный сигнал можно описать в виде суммы

2 Заданы входная последовательность и импульсная характеристика дискретной системы Вычислить дискретную свертку. Построить график свертки.

Решение:

Формула светки:

_{N=N1+N2-1=8+3-1=10}

3 Решить разностное уравнениеc начальным условием цифровой единичный импульс; отклик рекурсивной линейной дискретной системы.

Решение:

,

- цифровой единичный импульс

4 Вычислить комплексную частотную характеристику (КЧХ)(дискретизированное по времени преобразование Фурье) линейной дискретной системы с импульсной характеристикой,где

Построить графики модуля и фазы КЧХ как функции нормированной частотыв диапазоне где , – циклическая и линейная частоты, ‒ частота дискретизации.

Решение:

Исходная последовательность

График модуля

График фазы

5 Вычислить элементысистемы дискретных экспоненциальных функций (ДЭФ) и записать систему в виде матрицы размером Матрицу представить в алгебраической и экспоненциальной форме.

Решение:

В дискретном преобразовании Фурье используется система дискретных экспоненциальных функций (ДЭФ), определяемых следующим выражением

Обе переменные принимают дискретные значении

Обозначим

Тогда

Всю систему ДЭФ можно записать в виде матрицы V , строки которой нумеруются переменной k , столбцы переменной п, а в пересечении k-n строки и n-го столбца записана величина

Для N=4 матрица V имеет вид:

6 Выполнить прямое дискретное преобразование Фурье (ДПФ) последовательности Восстановить исходную последовательность через вычисление обратного ДПФпоследовательностикоэффициентовдискретного преобразования Фурье.

Решение:

, k=0,1,…,N-1;

, n=0,1,…,N-1.

Выражение для вычисления называется прямым преобразованием (ДПФ), а для вычисления - обратным (ОДПФ).

Коэффициент (постоянная составляющая) равен сумме всех отсчетных значений сигнала:

7 Дана последовательность Применить быстрое преобразование Фурье (БПФ) для вычисления коэффициентов ДПФ. Показать, что алгоритм БПФ можно применять для восстановления по коэффициентам ДПФ используемым в качестве исходного массива данных. Оценить вычислительную сложность алгоритма БПФ.

Решение:

Сигнал состоит из 8-х отсчетов во временной области. Применяя уравнение ДПФ, получаем:

Разобьем эту сумму на две при n = (0, 2, 4, 6) и (1, 3, 5, 7). Получим выражение:

Раскрывая суммы, запишем

Два различных поворачивающих множителя можно связать с помощью определения:

Тогда формула примет вид:

Полученное выражение для 8-точечного БПФ не слишком сложно, но по мере возрастания количества точек увеличивается его сложность. Чтобы упростить выражение, его обычно изображают в другом виде.

Представим в виде графа алгоритм БПФ с прореживанием по времени основанный на разбиении — объединении при 

Рисунок - Граф алгоритма БПФ с прореживанием по времени при N=8

На первом этапе отсчеты входного сигнала переставляются местами и исходная последовательность делится на «четную» и «нечетную последовательности» (обозначены красными и синими стрелками). Потом «четная» и «нечетная» последовательности в свою очередь делятся на «четную» и «нечетную» последовательности. При  такое деление можно делать раз. В нашем случае . Данная процедура называется двоично-инверсной перестановкой, так можно выполнить перенумерацию отсчетов переписав номер отсчета в двоичной системе в обратном направлении. Например  имеет индекс в десятичной системе счисления , если же  переписать справа налево то получим , то есть после разбиения на четные нечетные перед первой операцией «Бабочка» встанет на место , которая в свою очередь встанет на место . По аналогичному правилу поменяются местами все отсчеты, при этом некоторые останутся на месте, в частности, так как если  переписать справа налево то все равно останется , аналогично   и. Очень важно понять, что данный метод перенумерации должен применяться при записи числа в двоичной системе состоящей из  разрядов. В приведенном примере использовалось 3 разряда двоичного числа, но если же  (), то необходимо записать число при использовании 4 разрядов. В этом случае  и после переписывания получим , то есть при   не останется на месте, а поменяется местами с .

Можно сказать что напрямую двоично-инверсная перестановка удобна когда заранее количество отсчетов входного сигнала фиксировано, однако в универсальных алгоритмах БПФ на различные размеры , двоично-инверсная перестановка не эффективна, проще и быстрее поменять отсчеты местами.

После двоично-инверсной перестановки получаем четыре 2-точечных ДПФ:

На основе четырех 2-точечных ДПФ формируются два 4-точечных ДПФ:

И на последнем уровне формируется полный спектр входного сигнала.

Алгоритм с прореживанием по времени на каждом уровне требует  комплексных умножений и сложений. При количество уровней разложения — объединения равно , таким образом общее количество операций умножения и сложения равно .

8 Заданы последовательности иВычислить циклическую дискретную сверткупоследовательностей с помощью ДПФ. Построить график свертки.

Решение:

Использование БПФ для вычисления свертки основано на том, что ДПФ свертки последовательностей есть покомпонентное произведение ДПФ соответствующих последовательностей.

Вычислим ДПФ последовательностей:

, k=0,1,…,7;

Далее производится поочередное умножение элементов первой последовательности с элементами второй последовательности и просуммировать полученные значения. После производится обратное преобразование по формуле обратного преобразования, в результате которого получаем свертку, рассчитанную с помощью ДПФ.

, n=0,1,…,7.

9 Вычислитьядро (матрицу)дискретного косинусного преобразования (ДКП) размером Матрицу представить в тригонометрической и числовойформе.

Решение:

Матрица С для вычисления дискретно-косинусного преобразования выглядит следующим образом

10 Выполнить прямое ДКП последовательности Изобразить график функции. Восстановить исходную последовательность через вычисление обратного ДКП последовательностикоэффициентов дискретного косинусного преобразования.

Решение:

11Вычислить двумерное ДКП массива данных размером Восстановить исходный массив, выполнив двумерноеобратное дискретное косинусное преобразование (ОДКП), если

Решение:

Матрица ДКП 8×8:

Двумерное ДКП массива данных

Обратное ДКП:

12 Вычислить среднеквадратичную ошибку восстановления исходных данных (задача 11) при обнулении 75% наименьших по значениям коэффициентов преобразования ДКП и последующем выполнении ОДКП над полученным массивом.

Решение:

Обнулим 48 наименьших значений матрицы С:

Обратное ДКП:

Среднеквадратичная ошибка восстановления исходных данных:

Список литературы

1 Оппенгейм А., Шафер Р. Цифровая обработка сигналов.‒ М.: Техносфера, 2006.

2 Теория прикладного кодирования: Учеб. пособие. В 2 т. В.К. Конопелько, А.И. Митюхин и др.; Под ред. проф. В.К. Конопелько. – Мн.: БГУИР, 2004.

3 Овсянников В.А. Методы формирования и цифровой обработки сигналов. Учебное пособие для студентов специальности «Радиосвязь, радиовещание и телевидение» в 2-ух частях. ‒Мн.: БГУИР 2010.

4 Лосев В.В. Микропроцессорные устройства обработки информации. Алгоритмы цифровой обработки: Учебное пособие для вузов. – Мн: Вышэйшая школа, 1990.

5 Смит С. Цифровая обработка сигналов. Практическое руководство для инженеров и научных работников: Пер. с англ. ‒ М.: Додека-XXI, 2008.

6 Айфичер Э.С., Джервис Б.У. Цифровая обработка сигналов: практический подход: Пер. с англ. ‒ М.: Издательский дом «Вильямс», 2008.

7 Гонсалес Р., Вудс Р. Цифровая обработка изображений. ‒ М.: Техносфера, 2005.

8 Андерсон Д.А. Дискретная математика и комбинаторика.: Пер. с англ. ‒ М.: Издательский дом «Вильямс», 2004.