Главная » Хабрахабр » [Перевод] Ричард Хэмминг: Глава 16. Цифровые фильтры — 3

[Перевод] Ричард Хэмминг: Глава 16. Цифровые фильтры — 3

«Цель этого курса — подготовить вас к вашему техническому будущему.»

imageПривет, Хабр. Помните офигенную статью «Вы и ваша работа» (+219, 2394 в закладки, 377k прочтений)?

Мы ее переводи, ведь мужик дело говорит. Так вот у Хэмминга (да, да, самоконтролирующиеся и самокорректирующиеся коды Хэмминга) есть целая книга, написанная по мотивам его лекций.

«Это не просто заряд положительного мышления; в ней описаны условия, которые увеличивают шансы сделать великую работу.» Это книга не просто про ИТ, это книга про стиль мышления невероятно крутых людей.

И ведем работу над изданием «в бумаге». Мы уже перевели 18 (из 30) глав.

Глава 16. Цифровые фильтры — 3

(За перевод спасибо Пахомову Андрею, который откликнулся на мой призыв в «предыдущей главе».) Кто хочет помочь с переводом, версткой и изданием книги — пишите в личку или на почту magisterludi2016@yandex.ru

Метод синтеза таких фильтров показан на рисунке 16. И вот теперь мы готовы рассмотреть систематический синтез нерекурсивных фильтров. Слева сверху эскиз фильтра, который вы хотели бы получить в идеальном случае. 1 и состоит из 6 частей. Для всех типов фильтров, кроме диференциатора, обычно стремятся получить передаточную характеристику равную 0 или 1 на различных интервалах частот, в то время как для диференциатора стремятся получить в качестве передаточной характеристики, потому что производная собственной функции фильтра равна Это может быть фильтр низких частот, фильтр верхних частот, полосно-заграждающий, полосно-пропускающий фильтр, фильтр-пробка или даже диференциатор.

следовательно желаемые коэффициенты равняются iω.

В области высоких частот, где обычно и располагаются помехи, передаточная функция имеет наивысшие значения (рисунок 16. Для диференциатора скорее всего будет задана некоторая частота среза, потому что, как вы могли заметить, дифференциирование увеличивает амплитуду сигнала, умножая ее на ω. Также обратите внимание на рисунок 15. II). II.

I Рисунок 16.

Предположим, мы представили разложение в ряд в виде комплексных экспонент. Коэффициенты соответствующих членов разложения в ряд Фурье легко рассчитываются, поскольку подынтегральные функции в выражении для их расчета являются простыми (когда существует производная, возможно использовать интегрирование по частям). В правом верхнем углу на рисунке 16. Тогда коэффициенты фильтра — это коэффициенты соответствующих членов ряда, представленные в экспоненциальной форме. I представлен символический график коэффициентов (конечно же, коэффициенты являются комплексными числами).

I) мы должны ограничить разложение в ряд 2N+1 членами (это аналогично использованию прямоугольного окна). На следующем этапе (представлен ниже на рисунке 16. Коэффициенты с наложенной на них оконной функций представлены в нижней правой части иллюстрации, а итоговый фильтр в нижней левой. Такое ограничение количество членов (правая часть иллюстрации) приводит к эффекту Гиббса (левая часть иллюстрации).

Если первоначальный выбор этих параметров не подходит для вашей задачи, вы выбираете другие параметры и пробуете еще раз. Метод представленный выше требует выбора количества членов ряда Фурье (N) и формы оконной функции. Это метод проб и ошибок.

В этом случае необходимо задать два параметра: отклонение от идеального фильтра по вертикальной оси (δ) и ширину области перехода между полосой пропускания и полосой подавления (ΔF), пример показан на рисунке 16. Джеймс Фредерик Кайзер предложил метод синтеза, который позволяет одновременно как рассчитать количество коэффициентов ряда, так и получить конкретную оконную функцию из определенного семейства оконных функций. III.

III
Рисунок 16.

Для полосно-пропускающего фильтра, с заданными полосой пропускания fp и полосой подавления fp, применяется следующая последовательность расчетов:

Если полученное значение N слишком велико, то нужно остановиться и пересмотреть дизайн фильтра, иначе вы переходите к следующему шагу:

IV. Зависимость α(A) представлена на графике 16. Первоначальные коэффициенты разложения в ряд Фурье заданы как

Эти коэффициенты должны быть умножены на соответствующие весовые коэффициенты wk оконной функции

где

IV График 16.

Для вычисления ее значения вам потребуется сравнительного немного членов, потому ряд сходится быстро благодаря квадрату n! I0(x) является функцией Бесселя мнимого аргумента нулевого порядка. в знаменателе.

Лучше всего вычислять значение I0(x) рекурсивно; для заданного x следующий член ряда выражается через предыдущий как

Для частотно-заградительного фильтра формулы для расчета коэффициентов ck немного изменяются. Для фильтра низких или высоких частот одно из значений fp или fs has limnit possibel for it.

Давайте исследуем коэффициенты оконной функции Кайзера, wk:

Если мы исследуем эти числа, то увидим, что для α>0 они напоминают приподнятый косинус

Для A>21 присутствует «платформа». а соответствующая оконная функция похожа на окна Ханна и Хэмминга. С увеличением A постепенно возникает платформа. Для A<21, когда α=0, все весовые коэффициенты wk равны единицы и мы получим окно на подобие окна Ланцоша. Таким образом, окно Кайзера имеет те же свойства, что и многие популярные окна, но при этом конкретное окно, которое вы используете строится на основе заданных параметров, а не на основе предрассудка или догадки.

В некоторой степени методом проб и ошибок. Как Кайзер вывел эти формулы? В данном случае имеется в виду ширина переходной полосы между полосой пропускания и полосой затухания.) и величину звона δ. Вначале он предположил, что у него есть один разрыв и он смоделировал много вариантов на компьютере, чтобы видеть одновременно длительность фронта ΔF (Фронт сигнала — это переход сигнала из состояния 0 (нижний уровень) в 1 (верхний уровень). В идеальном случае он хотел получить вытянутую сфероидальную функцию, но он заметил, что полученные им значения точно аппроксимируются I0(x). После изрядного количества размышлений, прикосновения музы и не имея ничего определенного в качестве функции от A, мы заметим, что с увеличением A мы приходим от окна Ланцоша (A < 21) к платформе увеличивающейся высоты, 1/I0(α). Я спросил его, как он получил 0. Он построил графики и аппроксимировал функции. Он сказал, что он попробовал вначале 0. 4 для степени экспоненты. 4, которое к тому же отлично подошло, стало следующим логичным выбором. 5, но это оказалось слишком много, тогда значение 0. В такой ситуации, которая иногда все-таки случается, следует просто повторить синтез с менее строгими ограничениями. Это хороший пример того, что использование уже известных знания в комбинации с компьютером, в качестве инструмента для экспериментов, приводит к очень полезным результатам, даже в теоретических исследованиях.
Иногда метод Кайзера дает сбой, когда присутствует больше одного среза (на самом деле, срез отображается симметрично и на отрицательную область частот) и тогда звон, обусловленный разными срезами будет накладываться друг на друга и заложенное предельное значение звона будет превышено. Вся программа целиком может быть выполнена на небольшом, помещающемся в руку программируемом калькуляторе, например TI-59, не говоря уже о современном PC.

Функции Фурье замечательны тем, что они ортогональны не только на непрерывном интервале, но и на множестве отдельных точеке, равноотстоящих друг от друга. А теперь давайте вернемся к конечным рядам Фурье. Для 2N точек, в общем случае, в разложении в ряд присутствует только один член для наивысшей частоты — косинус (так как значение синуса будет равно нулю в точках дискретизации). Следовательно, вся теория остается той же самой, за исключением того, что в разложении в ряд может быть столько членов, сколько точек в исходном массиве. Полученное представление, с учётом округления, будет воспроизводить исходные данные. Коэффициенты определены как суммы значений данных умноженные на соответствующие функции Фурье.

Использование двух оптимизаций: (1) сложение и вычитание членов с одинаковым множителем перед выполнением операции умножения и (2) вычисление более высоких частот при помощи умножение более низких частот, привело к появлению быстрого преобразования Фурье (БПФ), которое требует N logN операций. Вычисление разложения будет выглядеть как 2N операций сложения и умножения для каждого из 2N значений исходных данных, то есть что-то около (2N)2 операций сложения и умножения. Такое уменьшение требуемой вычислительной мощности сильно изменило целые области науки и техники — то, что раньше было невозможно из-за высоких затрат и длительного времени вычисления, стало повсеместно распространено.

Все вы слышали про БПФ и публикацию Кули-Тьюки. А сейчас время еще одной истории из жизни. Тьюки подсказал мне, отчасти, базовые идеи БПФ. БПФ иногда называется преобразованием или алгоритмом Кули-Тьюки. Спустя несколько лет у меня появился программируемый внутри IBM-650, и он мне напомнил об этих оптимизациях еще раз. В то время у меня был программируемый внешними перфокартами калькулятор IBM (IBM Card Programmed Calculator), и операция «бабочка», которую он имел в виду, была абсолютно не практичной на оборудовании, которое у меня было. Таким образом я не реализовал БПФ, хотя книга, которую я уже опубликовал к тому моменту, показывает что все необходимое для этого я тогда уже знал, и мог реализовать БПФ очень просто! Все, что я тогда помнил, это то, что это была одна их немногих плохих идей Тьюки; Я абсолютно забыл почему она была плоха — только по из-за ограничений оборудования, которое у меня тогда было.

Подумайте о моей ошибке! Мораль: если вы запомнили, что что-то не может быть сделано, то также запомните основные причины почему это не может быть сделано, чтобы позже, когда обстоятельства изменятся, вы не сказали: «Это не может быть сделано». К счастью для моего эго, это распространенная ошибка ( и я ее совершил больше одного раза), но из-за того, что я попал впросак с БФТ, я теперь к очень чутко к ней отношусь. Разве может быть что-то глупее? Пожалуйста, запомните историю о том, каким глупцом я был и какую возможность я из-за этого упустил, и не совершайте такие ошибки сами. Я также заметил что другие тоже часто ошибаются таким же образом — слишком часто! Когда вы решаете, что что-то невозможно, не говорите в будущем снова, что это невозможно до того, как вы не изучите во всех деталях, почему вы изначально были правы, когда утверждали, что это невозможно.

Исследование этого вопроса убедит вас, что эта величина зависит только от самого сигнала и не зависит от расположения точки начала отсчета во времени, в противоположность значениям коэффициентов, которые зависят от расположения точки начала отсчёта. Сейчас я должен вернуться к деликатной теме спектра мощности, который равен сумме квадратов двух коэффициентов заданной частоты в области действительных чисел или квадрату модуля в комплексной области. Это именно спектральные линии открыли черный ящик строения атома и позволили Бору заглянуть вовнутрь. Спектр играет очень важную роль в науке и технике. Мы также регулярно исследуем черные ящики посредством изучения зависимостей между спектрами входных и выходных сигналов, чтобы получить понимание об их внутреннем устройстве — заметьте, что оно всегда уникально, но в общем мы получаем достаточно информации, чтобы формировать новые теории. Более новая квантовая механика, появившаяся в 1925 году, все изменила, чтобы бы хоть немного в чем-то уверенным, но спектр по-прежнему оставался ключом.

Обычно, по крайней мере в нашем воображении, мы имеем дело с аналоговым сигналом. Позвольте мне аккуратно проанализировать что мы делаем и что мы при этом подразумеваем, потому что это в значительной степени определяет что мы видим в итоге. Это то же самое, что и умножение сигнала на окно Ланцоша, или прямоугольное окно, если вам так больше нравится. Он обычно бесконечный и мы снимаем отсчёты на временном промежутке длиной 2L. V — чем длинее сигнал, тем уже петли (sinx)/x. Это означает, что происходит свёртка исходного сигнала с соответствующей функцией вида (sin x)/ x, рисунок 16. V
Затем мы производим дискретизацию через равные интервалы времени и высокие частоты накладываются на более низкие частоты. Каждая чистая спектральная линия растекается по соответствующей (sinx)/x кривой.
Рисунок 16. Как я уже упоминал, однажды, я аккуратно проработал соответствующие алгебраические преобразования, чтобы убедиться, что то, что должно быть истинно с точки зрении теории, на самом деле является истинным и на практике. Очевидно, что вне зависимости от порядка этих двух операций — дискретизации и ограничении сигнала по времени — мы получим одинаковый результат.

Дело в том, что когда мы допускаем представление сигнала в форме конечно ряда Фурье мы делаем предполагаем, что исходная функция является периодической с длиной периода равной в точности периоду дискретизации умноженному на количество снятых отсчётов. Затем мы используем ПБФ, которое является всего лишь хитроумным и точным методом получения коэффициентов конечного ряда Фурье. Такое отображение не является локальный эффектом, и как вы легко можете посчитать, что негармонические частоты накладываются на все гармонические частоты, конечно, наибольшим образом, на смежные частоты, но при этом, довольно не тривиальным образом, они влияют и на более отдаленные частоты. Мы насильно принимаем все негармонические частоты за гармонические — мы насильно превращаем сплошной спектр в линейчатый спектр.

Такой приём уменьшает амплитуду нулевой частоты в спектре до нуля и привносит серьезный разрыв в спектр. Я избегал вычитания среднего значения — стандартного приёма из области статистики, который используется для удобства или калибровки. Во время обработки данных для Тьюки, я часто использовал вычитание линейного или даже квадратичного тренда, из данных о полете самолета или ракеты. Если в последствии будет использоваться оконная функция, то она просто размажет этот разрыв по смежным частотам. При сложении двух функций отдельные частоты складываются алгебраически, и они могут как усилить друг друга так и полностью погасить, и это приведет к абсолютно ложному результату. Но спектр суммы двух сигналов отнюдь не является суммой спектров! Мы по-прежнему частично используем их, потому что мы не знаем чем их можно заменить — и никто из тех, кого я знаю, не имеет никаких разумных аргументов против моих замечаний. Линия тренда имеет большой разрыв на конце (помните, что мы предполагаем что функции являются периодическими), потому что ее коэффициенты уменьшаются как 1/k, что совсем не быстро.

Каждый спектр реального шума уменьшается довольно быстро по мере того, как мы стремимся к бесконечной частоте, иначе он имел бы бесконечную энергии. Но вернемся к теории. VI, имеет тенденцию приводить к плоскому спектру — помните, что частоты складываются алгебраически. Но процесс дискретизации сам по себе накладывает более высокие частоты на более низкие, и такое уменьшение полосы, как показано на графике 16. Сигнал преимущественно расположен в области низких частот. Таким образом существует тенденция наблюдать плоский спектр для шума, и если спектр плоский, то такую шум мы называем белым шумом. Таким образом, типичный спектр будет выглядеть как показано на графике 16. Это утверждение справедливо по нескольким причинам, включая использование оверсэмплинга (снятие отсчётов более часто, чем того требует теорема Найквиста), который дает нам возможность использовать усреднение для уменьшения погрешности измерения. Поэтому для удаления шума так распространен фильтр нижних частот. VI. Таким образом, когда мы используем оверсэмплинг, у нас есть шансы удалить большую часть шума при помощи фильтра нижних частот. Ни один линейный метод не может отделить сигнал от шума на одной и той же частоте, но шум за пределами частот сигнала может быть удален фильтром нижних частот.

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

Чего я тогда не знал — только потому, что я тогда ничего не знал о проектировании рекурсивных цифровых фильтрах- так это того, что я к тому моменту их уже создал, когда я подробно изучал теорию предиктор-корректоров применительно к численному решению обычных дифференциальных уравнений. Я аккуратно упомянул в предисловии к теме о цифровых фильтрах, что в то время, я думал, что я ничего о них не знаю. Корректор — это практически рекурсивный цифровой фильтр!

На самом деле, когда я позже столкнулся с задачей посадочной траектории на луну, где нет воздуха, и поэтому нет сопротивления, поэтому нет явной первой производной в уравнении, и я хотел воспользоваться таким решениям используя подходящую формулу для численного интегрирования, я обнаружил, что я у меня был квадратичный рост ошибки; небольшая ошибка округления в вычислении ускорения не будет исправлена и приведет к квадратичной ошибки в определении местоположения; ошибка в ускорении приводит к квадратичному росту ошибки в вычислении местоположения. Когда я изучал как численно проинтегрировать систему обычных дифференциальных уравнений, я был свободен от стереотипов из области цифровых фильтров, и вскоре я сообразил, что ограниченный входной сигнал, как говорят эксперты по цифровым фильтрам, если вы его интегрируете, может вызвать неограниченный сигнал на выходе — что они называли нестабильным, но абсолютно очевидно, что вы должны получить, если вы интегрируете — даже константное значение на входе приведет к линейному росту на выходе. Это и есть корень проблемы, в отличие от Земли, где сопротивление воздуха играет роль обратной связи и производит коррекцию неправильного ускорения, и как следствие коррекцию ошибки в местоположении.

При этом полиномиальный рост разрешен, а это уже не является стандартным критерием стабильности, унаследованным от классических аналоговых фильтров, где если он будет не ограничен, то у вас все расплавится — в любом случае, они никогда не рассматривались всерьез как инструмент интегрирования. Таким образом и по сей день я имею отношение к вопросу стабильности цифровых фильтров, под которой понимается не экспоненциальный рост выходного сигнала при ограниченном входном сигнале.

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

Продолжение следует...

Кто хочет помочь с переводом, версткой и изданием книги — пишите в личку или на почту magisterludi2016@yandex.ru

Кстати, мы еще запустили перевод еще одной крутейшей книги — «The Dream Machine: История компьютерной революции»)

Содержание книги и переведенные главы

Предисловие

  1. Intro to The Art of Doing Science and Engineering: Learning to Learn (March 28, 1995) Перевод: Глава 1
  2. «Foundations of the Digital (Discrete) Revolution» (March 30, 1995) Глава 2. Основы цифровой (дискретной) революции
  3. «History of Computers — Hardware» (March 31, 1995) Глава 3. История компьютеров — железо
  4. «History of Computers — Software» (April 4, 1995) Глава 4. История компьютеров — Софт
  5. «History of Computers — Applications» (April 6, 1995) Глава 5. История компьютеров — практическое применение
  6. «Artificial Intelligence — Part I» (April 7, 1995) (в работе)
  7. «Artificial Intelligence — Part II» (April 11, 1995) (в работе)
  8. «Artificial Intelligence III» (April 13, 1995) Глава 8. Искуственный интеллект-III
  9. «n-Dimensional Space» (April 14, 1995) Глава 9. N-мерное пространство
  10. «Coding Theory — The Representation of Information, Part I» (April 18, 1995) (в работе)
  11. «Coding Theory — The Representation of Information, Part II» (April 20, 1995)
  12. «Error-Correcting Codes» (April 21, 1995) (в работе)
  13. «Information Theory» (April 25, 1995) (в работе, Горгуров Алексей)
  14. «Digital Filters, Part I» (April 27, 1995) Глава 14. Цифровые фильтры — 1
  15. «Digital Filters, Part II» (April 28, 1995) Глава 15. Цифровые фильтры — 2
  16. «Digital Filters, Part III» (May 2, 1995) Глава 16. Цифровые фильтры — 3
  17. «Digital Filters, Part IV» (May 4, 1995)
  18. «Simulation, Part I» (May 5, 1995) (в работе)
  19. «Simulation, Part II» (May 9, 1995) готово
  20. «Simulation, Part III» (May 11, 1995)
  21. «Fiber Optics» (May 12, 1995) в работе
  22. «Computer Aided Instruction» (May 16, 1995) (в работе)
  23. «Mathematics» (May 18, 1995) Глава 23. Математика
  24. «Quantum Mechanics» (May 19, 1995) Глава 24. Квантовая механика
  25. «Creativity» (May 23, 1995). Перевод: Глава 25. Креативность
  26. «Experts» (May 25, 1995) Глава 26. Эксперты
  27. «Unreliable Data» (May 26, 1995) (в работе)
  28. «Systems Engineering» (May 30, 1995) Глава 28. Системная Инженерия
  29. «You Get What You Measure» (June 1, 1995) Глава 29. Вы получаете то, что вы измеряете
  30. «How Do We Know What We Know» (June 2, 1995) в работе
  31. Hamming, «You and Your Research» (June 6, 1995). Перевод: Вы и ваша работа

Кто хочет помочь с переводом, версткой и изданием книги — пишите в личку или на почту magisterludi2016@yandex.ru


Оставить комментарий

Ваш email нигде не будет показан
Обязательные для заполнения поля помечены *

*

x

Ещё Hi-Tech Интересное!

Как Яндекс применил компьютерное зрение для повышения качества видеотрансляций. Технология DeepHD

Когда люди ищут в интернете картинку или видео, они часто прибавляют к запросу фразу «в хорошем качестве». Под качеством обычно имеется в виду разрешение — пользователи хотят, чтобы изображение было большим и при этом хорошо выглядело на экране современного компьютера, ...

Security Week 36: Telnet должен быть закрыт

Telnet — это очень старый протокол. Википедия сообщает, что он был разработан в 1969 году, много лет активно использовался для удаленного доступа к компьютерам и серверам, причем как под управлением Unix/Linux, так и для систем под Windows (telnet можно было ...