{
"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",
"