{ "cells": [ { "cell_type": "markdown", "id": "d2494f5a", "metadata": {}, "source": [ "# Цифровая обработка сигналов - Лекция 16\n", "# Тема: Алгоритм Герцеля\n", "\n", "## Введение\n", "\n", "Перед вами обучающий материал по основам **цифровой обработки сигналов** с использованием средств языка программирования Python. Предполагается, что читатель имеет базовые знания из области высшей математики, а также владеет языком Python и хотя бы поверхностно знает различные python-библиотеки - numpy/scipy, matplotlib и другие. \n", "\n", "Для пользователей MATLAB / GNU Octave освоение материала с точки зрения программного кода не составит труда, поскольку основные функции и их атрибуты во многом идентичны и схожи с методами из python-библиотек.\n", "\n", "## Теоретический базис\n", "\n", "В предыдущих разделах нами были рассмотрены дискретное преобразование Фурье (ДПФ) и метод быстрого преобразования Фурье (БПФ). Была продемонстрирована возможность более эффективного расчета результата дискретного преобразования Фурье при использовании алгоритма БПФ. На практике же, например при декодировании сигналов Dual-Tone Multi-Frequency (DTMF), может потребоваться рассчитать ДПФ только для ограниченного количества отсчетов. В данном примере, чтобы получить значение одного спектрального отсчета, будет необходимо осуществить расчет полного дискретного преобразования Фурье. В этом случае использование алгоритма быстрого преобразования Фурье может потребовать большого количества вычислительных ресурсов.\n", "\n", "Ниже будет рассмотрен алгоритм Герцеля, позволяющий осуществить расчет для ограниченного количества отсчетов ДПФ.\n", "\n", "### Быстрое преобразование Фурье как БИХ фильтр\n", "Пусть имеется входной сигнал $s(n), n = 0, 1, ... N - 1$. Тогда набор из $N$ отсчетов данного сигнала можно записать в виде набора из $N$ частотных коэффициентов с использованием дискретного преобразования Фурье (ДПФ) в следующем виде:\n", "$$S(k) = \\sum_{n=0}^{N-1}s(n)W_{N}^{nk} \\tag{16.1}$$\n", "\n", "где $k = 0 ... N - 1$, $W_{N}^{nk} = exp(-j\\frac{2\\pi}{N}nk)$, $W_{N}^{nk}$ - поворотные коэффициенты. \n", "\n", "Так же заметим, что поворотные коэффициенты обладают следующим свойством:\n", "\n", "$$W_{N}^{-kN} = exp(-j\\frac{2\\pi}{N}Nn); k = 0 ... N - 1 \\tag{16.2}$$\n", "\n", "Это означает, что выражение (16.1) может быть записано в виде:\n", "\n", "$$S(k) = W_{N}^{-kN}\\sum_{n=0}^{N-1}s(n)W_{N}^{nk} = \\sum_{n=0}^{N-1}s(n)W_{N}^{k(n - N)} \\tag{16.3}$$\n", "\n", "Раскрывая сумму (16.3) получим следующее выражение:\n", "\n", "$$S(k)=s(0)W_{N}^{-kN}+s(1)W_{N}^{-k(N-1)}+s(2)W_{N}^{-k(N-2)}+...+s(1)W_{N}^{-k} \\tag{16.4}$$\n", "\n", "Обозначим $S(k)=y_{N-1}(k)$ и вынесем в $W_{N}^{-k}$ для фиксированного номера $k$ отсчета в ДПФ. Тогда перепишем выражение (16.4) следующим образом:\n", "\n", "$$y_{N-1}(k)=W_N^{-k}(s(N-1) + y_{N-2}(k)) \\tag{16.5}$$\n", "\n", "Таким образом получим рекуррентное соотношение для вычисления $y_{r}(k)$ для любого шага $r$ через $y_{r-1}(k)$\n", "\n", "$$y_{r}(k)=W_N^{-k}(s(r) + y_{r-1}(k)) \\tag{16.6}$$ где $s(r)$ - отсчет исходного сигнала с номером $r$\n", "\n", "Соотношение $(16.6)$ представляет собой выражение фильтра с бесконечной импульсной характеристикой (БИХ) первого порядка с коэффициентом $W_{N}^{-k}$. Структурная схема БИХ-фильтра представлена на рисунке:\n", "\n", "\n", "\n", "