Хабрахабр

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

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

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

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

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

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

Глава 17. Цифровые фильтры — IV

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

А сейчас мы обратимся к рекурсивным фильтрам, которые имеют следующий вид:

image

Мы используем предыдущие значения сигнала и его значение в текущий момент времени un а так же предыдущие значения полученные на выходе фильтра.
Этот классический подход является результатом того, что часто мы обрабатывает сигнал в режиме реального времени и у нас нет доступа к будущим значениям сигнала. Из этой формулы видно, что мы располагаем значениями только с одной стороны от текущего n-ого значения.

Тогда бы для вычисления yn мы столкнулись бы с системой, которая должна была бы моментально решать линейные уравнения — ничего страшного в век дешевых вычислений. Вспомнив основы, мы увидим, что если бы у нас были «будущие значения», вероятно, двухстороннее прогнозирование было бы намного более точное. Например использовать в обработке изображений рекурсивный цифровой фильтр было бы глупостью, потому что он не использует часть доступной, релевантной информации. Мы оставим в стороне это наблюдение, в наши дни мы часто записываем сигнал на ленту или другой носитель, и позже обрабатываем данные в лаборатории — и поэтому мы располагаем будущими значениями для какого-то момента времени.

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

Однако, в переходном состоянии, могут появляться и другие частоты, которые возникают из решения однородного дифференциального уравнения. Работая с линейной системой, мы видели, что какую бы частоту мы не подали на вход фильтра, когда он в стационарном состоянии, то только эта частота возникает на выходе фильтра, хотя фаза выходного сигнала может быть смещена относительно фазы исходного сигнала. Рекурсивный фильтр — это не что иное как решение дифференциального уравнения с постоянным коэффициентам при un членах, образующих функцию подкрепления (forcing function).

Следовательно, для стационарного состояния (игнорируя переходные процессы) мы принимаем, что

image

(где A могут быть комплексным числами, чтобы учесть смещение фазы), и это приводит к решению отношения A0/A1 для нахождения передаточной функции:

image

Разработана теоретическая часть представления функции в виде разложения в ряд Фурье; но пока что еще нет теории по представлению функции как отношения двух рядов Фурье (думаю что нет причин, по которым такой теории может не быть). Это выражение является рациональной функцией от комплексной переменной exp = z, в отличие от рассмотренного ранее не рекурсивного фильтра, где передаточная характеристика являлась полиномом от z. Поэтому в настоящий момент методы проектирования не являются систематическими (что Кайзер сделал для проектирования не рекурсивных фильтров), а скорее представляют из себя набор трюков.

Таким образом у нас есть фильтр Баттерворта, два типа фильтров Чебышёва (в зависимости от наличия одинаковых пульсаций в полосах пропускания и подавления) и эллиптический фильтр (который так назван из-за использования эллиптических функций), который имеет одинаковые пульсации в обоих полосах.

image

1 Рисунок 17.

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

I). Здорово, что водопроводчик подключил душ к трубам большого диаметра (Рисунок 17. Конечно, вода становилась все горячее и горячее по мере того, как ранее попавшая в трубы вода выходила наружу, и мне приходилось выпрыгивать из душа и пробовать снова найти подходящее положение ручки крана горячей воды. В результате, по утрам когда я начинал принимать душ вода была слишком холодной, я больше поворачивал ручку крана с теплой водой, все еще слишком холодно, и больше, по-прежнему слишком холодно, и еще больше, и наконец, когда вода становилась нужной температуры я останавливался. Я оказался, не смотря на богатый опыт, в классической ситуации неустойчивости. Задержка в подаче горячей воды причиняла мне неудобства. Тот же самый долгоиграющий эффект! Вы можете смотреть на эту ситуацию с одной из двух сторон: или мой отклик был слишком сильный (Я был очень груб в своих действиях) или обнаружение сигнала было слишком запаздывающим (Я был слишком торопливым в регулировке крана). В этом наглядном примере вы можете рассмотреть саму суть неустойчивости. Мне никогда раньше не приходилось сталкиваться с большими задержками, поэтому каждый день мое утро начиналось с неудобства!

Здесь я не буду углубляться в дизайн рекурсивных фильтров, только замечу, что во время борьбы с корректирующими формулами для численного решения обыкновенных дифференциальных уравнений я самостоятельно разработал одну теорию.

Корректор в методе предиктор-корректоров имеет форму

image

В обычных нерекурсивных фильтрах нет петли обратной связи — вычисленные значения yn не появляются позже в правой части выражения. Мы видим, что теперь коэффициенты uj рекурсивного фильтра — это производные yn' выхода фильтра, которые берутся из дифференциального уравнения. Следовательно, стабильность в области решения дифференциальных уравнений — это более сложная тема, чем в области рекурсивных фильтров. В дифференциальных уравнениях они появляются как и в петле обратной связи так и во входящих в него производных, формируя тем самым еще одну петлю обратной связи, обычно нелинейную.

Я не был бы самим собой, если бы я не задался вопросом, все ли рекурсивные фильтры должны обладать таким свойством. Такие рекурсивные фильтры часто называются «фильтры с бесконечной импульскной характеристикой» (БИХ — фильтры), потому что единичной возмущение будет отдаваться эхом по петле обратной связи, которое будет затухать в геометрической прогрессии, и то, только в том случае если фильтр стабилен. По правде говоря, это не тот вид фильтров, которые вы обычно будете проектировать, но этот пример показывает, что это утверждение является поверхностным. Вскоре я нашел противоположный пример. Если вы спросите себя, все ли, что вы говорите является истинным, то вы будете удивлены, сколько всего окажется ложным, даже в хорошо разработанных областях!

Сейчас вы увидите пример того, что случается слишком часто. В Главе 26 я затрону проблему работы с экспертами. И этот принятый факт они постоянно воспроизводят даже не пытаясь проверить, является ли он истинным или нет, особенно применительно к той проблеме, которую они пытаются решить в этот момент. Экспертам что-то рассказали в учебной аудитории, когда они были еще студентами, и они не задавались вопросами, они просто приняли это как факт.

Одна дама из математического департамента Лабораторий Белла танцевала сквэр-данс с одним из физиков на вечеринке в выходные, а в понедельник с утра, в коридоре она упомянула при мне о проблеме, с которой он столкнулся. Позвольте мне сейчас рассказать вам еще одну историю. Это называется «спектр процесса». Он измерял количество импульсов в радиоактивном эксперименте на каждом из, насколько я помню, 256 энергетических уровней. Его проблема заключалась в получении производной от полученных данных.

Чем больше я думал о её случайной заметке, тем больше я чувствовал, что ему нужен хороший помощник — то есть я! Итак, вы знаете, что (a) количество импульсов определенного уровня энергии будет образовывать кривую с разрывами и (b) ее дифференцирование для получения локального углового коэффициента само себе является не простой задачей. Он тут же захотел прийти ко мне в кабинет, но я был упрямым, и настаивал на встрече в его лаборатории. Я отыскал его в телефонном справочнике Лабораторий Белла и объяснил ему свой интерес и как я на него вышел. Зачем? Он пробовал предложить свой кабинет, но я все настаивал на его лаборатории. Он с блеском прошел тест лабораторией — стало ясно, что он был очень компетентным экспериментатором. Для того, чтобы оценить его способности и решить, стоит ли его проблема моего времени и усилий, так как она обещала быть крепким орешком.

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

Сразу же начались проблемы. Очевидно, что это была проблема сглаживания, а Кайзер, фактически, только что обучил меня самого, поэтому что могло быть лучше, чем привести экспериментатора к Кайзеру и попросить Кайзера спроектировать подходящий дифференцирующий фильтр? В этом месте проблема с Кайзером повторялась до тех пор, пока я прямо не сказал ему: «Хорошо, его энергия это время, а измерения, импульсы, это напряжение». Кайзер всегда думал о сигнале как о функции времени, а о площади под кривой как об энергии, а в этом случае энергия была независимой переменной! Только после этого Кайзер смог решить задачу.

Я упоминал вам что Кайзер очень способный человек, но его опыт, как это часто случается с экспертами, ограничил его виденье. Проклятье экспертов заключается их ограниченном понимании того, что они могут сделать. Я надеюсь подобные истории помогут вам избежать этой ловушки. Сможете ли вы в свою очередь сделать лучше?

Как же ее найти? Как я ранее замечал, обычно спектр полезного сигнала находится в нижней части полосы Найквиста, а спектр шума распределен по всей полосе Найквиста, таким образом нам нужно было отыскать частоту среза между полезным сигналом физика и плоским белым шумом. Итак, мы смоделировали это распределение, и он подготовил некоторое количество синтетических данных соответствующих этой модели. Сначала я выпытал у физика теоретическую модель эксперимента, которая была у него в голове — это было множество узких спектральных линий в форме гауссовых функций поверх широкой гауссовой функции (я сомневался в том, что это распределение Коши, но не спорил с ним, так как разница была бы очень маленькой, учитывая природу данных, которые у нас были). Далее, мы обработали таким же образом его экспериментальные данные и получили то же самое местоположение частоты среза! Быстрый спектральный анализ сигнала через быстрое преобразование Фурье, показал что сигнал заключен в нижней 1/20 части полосы Найквиста. (Возможно, удача должна быть приписана мастерству экспериментатора). Какая удача! Оказалось, что мы были способны отфильтровать 95% шума. Однажды, теория и практика сошлись! Наконец, Кайзер написал для него программа, которая синтезировала фильтр для заданой частоты среза, которую задавал экспериментатор.

Программа (1) рассчитала подходящий дифференцирующий фильтр, (2) написала программу для расчета сглаженного выхода и после этого (3) обработала данные этим фильтром без каких-либо вмешательств со стороны физика.

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

Главным образом, вначале определить проблему, потом свести правильных людей вместе, потом наблюдать за Кайзером чтобы поставить его перед фактом того, что фильтрация необходима не только для сигналов как функций времени, и наконец напомнить им то, что они знали из статистики (или должны были бы знать, но, возможно, и не знали). Мой вклад?

Кому-то нужно сохранять широкий кругозор и следить за тем, чтобы вещи делались честно. На основе моего, мне кажется, что необходимость такой роли возрастает по мере того, как люди становятся все более глубокими специалистами во все более узких областях знаний. Я буду говорить о природе Математике в Главе 23. Я думаю я пришел к этой роли после очень долго образования под началом Джона Тьюки в дополнение к хорошему фундаменту в форме универсального инструмента Науки, именуемого Математикой.

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

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

Анализ посредством разложения в ряд Фурье предполагает линейность лежащей в основе модели. Позвольте мне высказать некоторые опасения относительно некорректного применения интеллектуальных инструментов, более подробно я буду говорить о темах, близких к статистике, в Главе 27. Я видел как миллионы долларов были потрачены впустую, когда было довольно очевидно для аутсайдеров, что нелинейности исказят весь линейный анализ, сделанный приближением рядами Фурье. Вы можете использовать его для немного нелинейных случаев, но все же чаще искусно сделанный анализ разложением в ряды Фурье проваливает, так как исследуемое явление слишком нелинейно по своей природе. И я здесь не преувеличиваю. Когда им указали на это, их ответ был, что они не знали каким еще подходом можно было воспользоваться, поэтому они продолжали делать неправильные вещи!

image

2 Рисунок 17.

Возможности здесь безграничны и зависят, конечно же, от проблемы с которой вы имеет дело. Что насчёт нелинейных фильтров? Вы считаете выход медианного фильтра для определенного набора данных. Я займусь здесь только одним из них, медианным фильтром. Первым делом заметим, что он стремится сгладить любой локальный шум, но как поведет себя фильтр в точке разрыва (рис. Рассмотрим как он работает на практике. 2)? 17.

Он будет достаточно хорошо следовать за разрывами и не будет пробовать их полностью сгладить! С нечётным количеством членов в медианном фильтре, вы увидите, что выход фильтра остается на верхнем уровне до тех пор, пока больше чем половина точек на входе фильтра не окажется на нижнем уровне, после чего выход фильтра «прыгнет» вниз. В некоторых случаях это именно тот тип фильтр, который вам подойдёт — локальный шум сглаживается, при этом внезапные изменения в состоянии изучаемой системы не будут потеряны.

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

Однажды изучая книгу посвященную интегралам Фурье, я нашел теорему, которая утверждала что вариация функции умноженная на вариацию ее преобразования должна быть больше чем определенная константа. Напоследок, вот еще одно фундаментальное наблюдение, которое я сделал изучая цифровые фильтры. Да, каждая линейная теория должна иметь принцип неопределенности связывающий сопряженные переменные. Я спросил у себя: «Что это такое как не знаменитый принцип неопределенности Квантовой Механики»? Линейная инвариантность времени автоматически приводит к собственным функциям e^iω(t). Как только вы приминяете линейный подход, а КМ утверждает абсолютную аддитивность собственных состояний, то вы должны обнаружить принцип неопределенности. Это как если бы вы надели синие тонированные очки. Они немедленно приводят к рядам Фурье, а они в свою очередь имеют принцип неопределенности. На что бы вы не посмотрели, оно должно иметь синеватый оттенок!

Поэтому вы на самом деле не уверены, существует ли знаменитый принцип неопределенности КМ или нет; может быть это всего лишь эффект подразумеваемой линейности системы.

Очень часто мы видим то, что мы хотим увидеть, и именно поэтому вам следует повсеместно применять научных подход, сомневаясь в собственных убеждения.
Чтобы наглядно это продемонстрировать, я повторю историю Эддингтона о рыбаках. Немногие люди хотят верить в то, что то что мы видим зависит от того, с какой стороны мы подходим к проблеме! Они ловили рыбу сетью, и когда они исследовали размер пойманных сетью рыб, они решили что существует минимальный размер рыбы в море.

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

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

Кто хочет помочь с переводом, версткой и изданием книги — пишите в личку или на почту 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) Глава 6. Искусственный интеллект — 1
  7. «Artificial Intelligence — Part II» (April 11, 1995) Глава 7. Искусственный интеллект — II
  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) Глава 17. Цифровые фильтры — IV
  18. «Simulation, Part I» (May 5, 1995) (в работе)
  19. «Simulation, Part II» (May 9, 1995) Глава 19. Моделирование — II
  20. «Simulation, Part III» (May 11, 1995)
  21. «Fiber Optics» (May 12, 1995) Глава 21. Волоконная оптика
  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) Глава 27. Недостоверные данные
  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 не будет опубликован. Обязательные поля помечены *

Кнопка «Наверх»
Закрыть