Richard Hamming: Chapitre 17. Filtres numériques - IV

«Le but de ce cours est de vous préparer à votre avenir technique.»

Salut, Habr. Vous vous souvenez de l'article génial «Vous et votre travail» (+219, 2442 signets, 393k lectures)?

Hamming (oui, oui, les codes Hamming à vérification automatique et à correction automatique) a un livre entier écrit sur la base de ses conférences. Nous le traduisons, parce que l'homme parle d'affaires.

Ce livre n'est pas seulement sur l'informatique, c'est un livre sur le style de pensée des gens incroyablement cool. «Ce n'est pas seulement une charge de pensée positive; il décrit les conditions qui augmentent les chances de faire du bon travail. »

Nous avons déjà traduit 24 chapitres (sur 30). Et nous travaillons sur une édition papier.

Chapitre 17. Filtres numériques - IV

(Merci pour la traduction, Andrei Pakhomov, qui a répondu à mon appel dans le "chapitre précédent".) Qui veut aider à la traduction, la mise en page et la publication du livre - écrivez dans un e-mail personnel ou magisterludi2016@yandex.ru

Et maintenant, nous nous tournons vers les filtres récursifs, qui ont la forme suivante:



Cette formule montre que nous n'avons des valeurs que d'un côté de la nième valeur actuelle. On utilise les valeurs précédentes du signal et sa valeur à l'instant courant un, ainsi que les valeurs précédentes obtenues en sortie du filtre.
Cette approche classique est le résultat du fait que nous traitons souvent le signal en temps réel et que nous n'avons pas accès aux futures valeurs du signal.

En rappelant les bases, nous verrons que si nous avions des «valeurs futures», les prévisions bidirectionnelles seraient probablement beaucoup plus précises. Ensuite, pour calculer yn, nous trouverions un système qui résoudrait instantanément des équations linéaires - ce n'est pas grave à l'ère de l'informatique bon marché. Nous laisserons cette observation de côté, aujourd'hui nous enregistrons souvent le signal sur bande ou sur un autre support, et traitons plus tard les données en laboratoire - et donc nous avons des valeurs futures pour un certain moment. Par exemple, l'utilisation d'un filtre numérique récursif dans le traitement d'image serait stupide car il n'utilise pas certaines des informations pertinentes disponibles.

Le prochain aspect auquel vous devez faire attention lorsque vous utilisez la valeur de sortie précédente comme entrée suivante est la présence de rétroaction - et cela soulève automatiquement le problème de la stabilité. C'est une condition que nous devons constamment surveiller lors de la conception des filtres récursifs. Cela limite ce que nous pouvons faire. Dans ce cas, la stabilité signifie que l'effet des conditions initiales ne commencera pas à prévaloir dans le résultat final.

En travaillant avec un système linéaire, nous avons vu que peu importe la fréquence que nous appliquions à l'entrée du filtre lorsqu'il est stationnaire, seule cette fréquence apparaît à la sortie du filtre, bien que la phase du signal de sortie puisse être décalée par rapport à la phase du signal d'origine. Cependant, dans l'état de transition, d'autres fréquences peuvent apparaître qui résultent de la solution d'une équation différentielle homogène. Un filtre récursif n'est rien de plus qu'une solution d'une équation différentielle avec des coefficients constants pour des termes un qui forment une fonction de forçage.

Par conséquent, pour un état stationnaire (en ignorant les transitoires), nous supposons que



(où A peut être des nombres complexes pour prendre en compte le déphasage), et cela conduit à la solution du rapport A0 / A1 pour trouver la fonction de transfert:



Cette expression est une fonction rationnelle de la variable complexe exp {iωt} = z, contrairement au filtre non récursif précédemment considéré, où la caractéristique de transfert était un polynôme en z. La partie théorique de la représentation de la fonction sous forme d'expansion dans une série de Fourier est développée; mais jusqu'à présent il n'y a pas de théorie sur la représentation des fonctions comme relations de deux séries de Fourier (je pense qu'il n'y a pas de raison pour qu'une telle théorie n'existe pas). Par conséquent, pour le moment, les méthodes de conception ne sont pas systématiques (ce que Kaiser a fait pour la conception de filtres non récursifs), mais plutôt un ensemble d'astuces.

Ainsi, nous avons un filtre Butterworth, deux types de filtres Chebyshev (selon la présence de la même ondulation dans les bandes de passage et de suppression) et un filtre elliptique (qui est ainsi nommé en raison de l'utilisation de fonctions elliptiques), qui a la même ondulation dans les deux bandes.



Figure 17.1

Je ne parlerai que du sujet de la rétroaction. Pour clarifier le problème des commentaires, je vais vous raconter une histoire à mon sujet. Il était une fois, j'ai participé à une série de six émissions de télévision d'une demi-heure sur les ordinateurs et l'informatique. Le tournage a eu lieu principalement à San Francisco. J'y ai souvent séjourné et j'avais l'habitude de rester dans la même chambre dans le même hôtel - c'est super de connaître la chambre dans tous ses détails quand il est déjà tard dans la nuit et que vous êtes fatigué ou quand vous devez vous lever au milieu de la nuit - d'où le désir de rester dans la même la chambre.

C'est formidable que le plombier ait connecté la douche à de gros tuyaux (figure 17.I). En conséquence, le matin, quand j'ai commencé à prendre une douche, l'eau était trop froide, j'ai tourné la poignée du robinet avec de l'eau tiède plus, encore trop froide, et plus, encore trop froide, et encore plus, et enfin, quand l'eau a atteint la bonne température Je suis resté. Bien sûr, l'eau devenait de plus en plus chaude à mesure que l'eau qui s'était précédemment introduite dans les tuyaux sortait, et j'ai dû sauter de la douche et essayer à nouveau de trouver une position appropriée pour la poignée du robinet d'eau chaude. Le retard dans l'approvisionnement en eau chaude m'a causé des désagréments. Malgré la riche expérience, je me suis retrouvé dans une situation classique d'instabilité. Vous pouvez regarder cette situation d'un des deux côtés: soit ma réponse était trop forte (j'étais très grossière dans mes actions) ou la détection du signal était trop tard (j'étais trop hâtive pour régler le robinet). Le même effet longue durée! Je n'ai jamais eu à faire face à de longs retards auparavant, donc chaque jour ma matinée commençait avec des désagréments! Dans cet exemple illustratif, vous pouvez regarder l'essence même de l'instabilité.

Ici, je ne vais pas me plonger dans la conception de filtres récursifs, je note seulement que pendant la lutte avec les formules correctives pour la solution numérique des équations différentielles ordinaires, j'ai développé indépendamment une théorie.

Le correcteur dans la méthode prédicteur-correcteur a la forme



On voit que maintenant les coefficients uj du filtre récursif sont les dérivées yn 'de la sortie du filtre, qui sont tirées de l'équation différentielle. Les filtres classiques non récursifs n'ont pas de boucle de rétroaction - les valeurs yn calculées n'apparaissent pas plus tard sur le côté droit de l'expression. Dans les équations différentielles, elles apparaissent à la fois dans la boucle de rétroaction et dans ses dérivées, formant ainsi une autre boucle de rétroaction, généralement non linéaire. Par conséquent, la stabilité dans le domaine de la résolution d'équations différentielles est un sujet plus compliqué que dans le domaine des filtres récursifs.

De tels filtres récursifs sont souvent appelés «filtres à réponse impulsionnelle infinie» (filtres IIR), car une seule perturbation sera répercutée à travers la boucle de rétroaction, qui se décomposera de façon exponentielle, et uniquement si le filtre est stable. Je ne serais pas moi-même si je ne m'étais pas demandé si tous les filtres récursifs devaient avoir cette propriété. Bientôt, j'ai trouvé l'exemple opposé. En vérité, ce n'est pas le type de filtre que vous concevez habituellement, mais cet exemple montre que cette déclaration est superficielle. Si vous vous demandez si tout ce que vous dites est vrai, vous serez surpris de voir combien de choses s'avèrent fausses, même dans des domaines bien conçus!

Dans le chapitre 26, j'aborderai la question du travail avec des experts. Vous verrez maintenant un exemple de ce qui arrive trop souvent. Les experts ont appris quelque chose dans la classe quand ils étaient encore étudiants, et ils n'ont pas posé de questions, ils l'ont simplement pris comme un fait. Et ils reproduisent constamment ce fait accepté sans même chercher à vérifier s'il est vrai ou non, surtout par rapport au problème qu'ils tentent de résoudre en ce moment.

Permettez-moi de vous raconter une autre histoire maintenant. Une dame du département de mathématiques des Laboratoires Labs Bella dansait une danse carrée avec l'un des physiciens lors d'une fête le week-end, et lundi matin, dans le couloir, elle m'a mentionné un problème qu'il avait. Il a mesuré le nombre d'impulsions dans une expérience radioactive à chacun, si je me souviens bien, 256 niveaux d'énergie. C'est ce qu'on appelle le spectre du processus. Son problème était d'obtenir un dérivé des données.

Donc, vous savez que (a) le nombre d'impulsions d'un certain niveau d'énergie formera une courbe avec des discontinuités, et (b) la différencier pour obtenir un coefficient angulaire local n'est pas une tâche facile en soi. Plus je pensais à sa note aléatoire, plus je sentais qu'il avait besoin d'une bonne aide - c'est-à-dire moi! Je l'ai trouvé dans l'annuaire téléphonique des Laboratoires Bell et je lui ai expliqué mon intérêt et comment je l'ai rejoint. Il a immédiatement voulu venir dans mon bureau, mais j'étais têtu et j'ai insisté pour me rencontrer dans son laboratoire. Il a essayé d'offrir son bureau, mais j'ai quand même insisté sur son laboratoire. Pourquoi? Afin d'évaluer ses capacités et de décider si son problème vaut mon temps et mes efforts, car il promettait d'être un écrou difficile à casser. Il a passé le test avec brio par le laboratoire - il est devenu clair qu'il était un expérimentateur très compétent.

Il était presque à la limite de ce qu'il pouvait faire - les données ont été collectées pendant une semaine et la source de rayonnement était cachée par de nombreux écrans. Il ne semblait pas que vous puissiez faire autre chose pour collecter des données plus précises. De plus, je suis vite devenu convaincu, malgré le fait que je connaissais peu de détails, que son expérience était importante pour la physique ainsi que pour les laboratoires Bell. J'ai donc repris cette tâche. Moralité: dans une certaine mesure, vous pouvez choisir et travailler sur les tâches que vous jugez importantes.

Évidemment, c'était un problème de lissage, et Kaiser, en fait, m'a juste formé, alors quoi de mieux que d'amener l'expérimentateur à Kaiser et de lui demander de concevoir un filtre de différenciation approprié? Les problèmes ont commencé tout de suite. Kaiser a toujours pensé le signal comme une fonction du temps, et la zone sous la courbe comme de l'énergie, et dans ce cas, l'énergie était une variable indépendante! À ce stade, le problème avec Kaiser s'est répété jusqu'à ce que je lui dise directement: "Eh bien, son énergie est le temps, et ses mesures, ses impulsions, cette tension." Ce n'est qu'après cela que Kaiser a pu résoudre le problème.

La malédiction des experts réside dans leur compréhension limitée de ce qu'ils peuvent faire. Je vous ai mentionné que Kaiser est une personne très compétente, mais son expérience, comme cela arrive souvent avec des experts, a limité sa vision. Pouvez-vous, à son tour, faire mieux? J'espère que ces histoires vous aideront à éviter ce piège.

Comme je l'ai remarqué plus tôt, généralement le spectre du signal utile est au bas de la bande de Nyquist, et le spectre de bruit est distribué dans toute la bande de Nyquist, nous avons donc dû trouver la fréquence de coupure entre le signal utile du physicien et le bruit blanc plat. Comment la retrouver? Au début, j'ai essayé un modèle théorique de l'expérience à partir de la tête du physicien qui était dans sa tête - il y avait beaucoup de raies spectrales étroites sous forme de fonctions gaussiennes au-dessus d'une large fonction gaussienne (je doutais qu'il s'agissait d'une distribution de Cauchy, mais je ne m'y opposais pas, car la différence serait très faible, compte tenu de la nature des données dont nous disposions). Nous avons donc simulé cette distribution et il a préparé une certaine quantité de données synthétiques correspondant à ce modèle. Une analyse spectrale rapide du signal par transformée de Fourier rapide a montré que le signal est situé dans le 1/20 inférieur de la bande de Nyquist. De plus, nous avons traité ses données expérimentales de la même manière et avons obtenu le même emplacement de fréquence de coupure! Quelle chance! (Peut-être que la chance doit être attribuée à la compétence de l'expérimentateur). Il était une fois la théorie et la pratique réunies! Il s'est avéré que nous avons pu filtrer 95% du bruit. Enfin, Kaiser a écrit pour lui un programme qui a synthétisé un filtre pour une fréquence de coupure donnée, qui a été défini par l'expérimentateur.

Le programme (1) a calculé un filtre de différenciation approprié, (2) a écrit un programme pour calculer la sortie lissée, puis (3) a traité les données avec ce filtre sans aucune intervention du physicien.

Plus tard, j'ai attrapé un physicien en ajustant la fréquence de coupure pour différentes parties des données de niveau d'énergie obtenues dans une série de mesures et j'ai été forcé de lui rappeler qu'il y a certains «degrés de liberté» et ce qu'il fait n'est pas un traitement honnête des données. Cela devenait beaucoup plus problématique lorsque les choses allaient bien, pour le persuader de tirer le meilleur parti de ses données (ce qui était très coûteux à obtenir) - il devrait travailler avec les racines carrées de ses impulsions, car elles avaient la même variance. Enfin, il l'a compris et l'a fait. Lui et Kaiser ont écrit un ouvrage classique dans ce domaine qui a ouvert la porte à de nouvelles choses qui pourraient être faites.

Ma contribution Surtout, identifiez d'abord le problème, puis réunissez les bonnes personnes, puis regardez Kaiser pour le confronter au fait que le filtrage est nécessaire non seulement pour les signaux en fonction du temps, et enfin rappelez-leur ce qu'ils savaient des statistiques (ou auraient dû savoir, mais peut-être qu’ils ne le savaient pas).

Sur la base du mien, il me semble que la nécessité d'un tel rôle augmente à mesure que les gens deviennent des experts de plus en plus approfondis dans des domaines de connaissance de plus en plus étroits. Quelqu'un doit maintenir un large horizon et s'assurer que les choses sont faites honnêtement. Je pense que je suis arrivé à ce poste après une très longue formation sous la direction de John Tukey en plus d'une bonne base sous la forme d'un outil universel des sciences appelé Mathématiques. Je parlerai de la nature des mathématiques au chapitre 23 .

La plupart du traitement du signal provient des signaux au fil du temps. Dans le même temps, la plupart des filtres numériques sont conçus pour de petites études hautement spécialisées qui ne sont pas nécessairement associées aux signaux dans le temps. Ici, je vous demanderai d'être prudent à l'avenir. Supposons que vous dirigiez une entreprise au sommet et que vous soyez intéressé par des données qui montrent les coûts de main-d'œuvre antérieurs pour l'équipement. Ce seront des données bruyantes, mais vous voulez toujours comprendre, dans le sens habituel, ce qui se passe dans l'organisation - quels processus à long terme se déroulent - ceux qui sont si lents que les gens les comprendront lorsqu'ils se produisent déjà, mais comprennent néanmoins la capture qui est fondamentalement importante si vous voulez être un bon manager. Vous aurez besoin d'un filtre numérique pour lisser les données et voir les indices de la tendance, si elle existe. Vous ne voulez pas trouver une tendance qui n'existe pas, mais si elle existe, alors vous voulez vraiment savoir ce qu'elle était avant afin de prédire ce qu'elle est susceptible d'être dans un avenir proche. En fait, vous voudrez voir des changements dans la pente de la tendance, si les données vous permettent de la voir. Certains signaux, tels que la puissance de feu par rapport au déplacement du navire, ne sont pas liés au temps, mais ils peuvent vous en dire beaucoup sur l'état actuel de la flotte. Bien sûr, vous pouvez étudier cette relation en fonction du temps.

Au sommet de votre carrière, vous pourrez utiliser une variété de filtres numériques de bas niveau pour les signaux en fonction du temps, et pas seulement pour mieux gérer les choses. Par conséquent, je soutiens que vous synthétisez probablement beaucoup plus de filtres numériques pour de telles choses non standard que pour réduire les données radar et les applications classiques similaires. C'est généralement dans de nouvelles applications de connaissances que vous pouvez obtenir le plus de rendement.

Permettez-moi d'exprimer certaines préoccupations concernant l'utilisation incorrecte d'outils intelligents; plus en détail, je parlerai de sujets proches des statistiques dans le chapitre 27 . L'analyse d'expansion de Fourier suppose la linéarité du modèle sous-jacent. Vous pouvez l'utiliser pour des cas légèrement non linéaires, mais le plus souvent, une analyse habilement effectuée par expansion de Fourier échoue, car le phénomène étudié est de nature trop non linéaire. J'ai vu comment des millions de dollars ont été gaspillés quand il était assez évident pour les étrangers que les non-linéarités fausseraient toute l'analyse linéaire effectuée par approximation par la série de Fourier. Quand ils l'ont souligné, leur réponse a été qu'ils ne savaient pas quelle autre approche pouvait être adoptée, alors ils ont continué à faire la mauvaise chose! Et je n'exagère pas ici.



Figure 17.2

Et les filtres non linéaires? Les possibilités ici sont infinies et dépendent, bien sûr, du problème que vous traitez. Je ne traiterai que d'un seul d'entre eux, le filtre médian.Vous considérez la sortie du filtre médian pour un ensemble de données spécifique. Voyons comment cela fonctionne dans la pratique. Tout d'abord, nous notons qu'il cherche à atténuer tout bruit local, mais comment se comportera le filtre au point de rupture (Fig. 17.2)?

Avec un nombre impair de membres dans le filtre médian, vous verrez que la sortie du filtre reste au niveau supérieur jusqu'à ce que plus de la moitié des points à l'entrée du filtre soient au niveau inférieur, après quoi la sortie du filtre "saute" vers le bas. Il suivra assez bien les pauses et n'essaiera pas de les lisser complètement! Dans certains cas, c'est exactement le type de filtre qui vous convient - le bruit local est atténué, tandis que les changements brusques de l'état du système à l'étude ne seront pas perdus.

Je répète que l'analyse par série de Fourier est linéaire, alors qu'il existe un grand nombre de filtres non linéaires, mais la théorie n'est pas bien développée pour autre chose qu'un filtre médian. Le filtre de Kalman est un autre exemple de l'utilisation d'un filtre partiellement non linéaire, la partie non linéaire est l '«ajustement» indépendant du filtre au signal.

Enfin, voici une autre observation fondamentale que j'ai faite lors de l'étude des filtres numériques. Un jour, en étudiant un livre sur les intégrales de Fourier, j'ai trouvé un théorème qui prétendait que la variation d'une fonction multipliée par la variation de sa transformation devrait être supérieure à une certaine constante. Je me suis demandé: "Qu'est-ce que le fameux principe d'incertitude de la mécanique quantique"? Oui, chaque théorie linéaire devrait avoir un principe d'incertitude reliant les variables conjuguées. Dès que vous adoptez l'approche linéaire et que le CM affirme l'additivité absolue des états propres, vous devez découvrir le principe de l'incertitude. L'invariance linéaire du temps conduit automatiquement aux fonctions propres e ^ iω (t). Ils conduisent immédiatement à la série de Fourier, et ils ont à leur tour le principe de l'incertitude.C'est comme si vous portiez des lunettes teintées bleues. Quoi que vous regardiez, il devrait avoir une teinte bleutée!

Par conséquent, vous n'êtes pas vraiment sûr si le fameux principe de l'incertitude CM existe ou non; c'est peut-être juste l'effet de la linéarité implicite du système.

Peu de gens veulent croire que ce que nous voyons dépend de quel côté nous abordons le problème! Très souvent, nous voyons ce que nous voulons voir, et c'est pourquoi vous devez utiliser une approche scientifique partout, en doutant de vos propres croyances.
Pour le démontrer clairement, je vais répéter l'histoire d'Eddington sur les pêcheurs. Ils ont pêché dans le filet et, lorsqu'ils ont examiné la taille du poisson pris dans le filet, ils ont décidé qu'il y avait une taille minimale de poisson dans la mer.

En conclusion, si vous ne doutez pas des règles adoptées, de temps en temps, alors vous ne deviendrez probablement pas des leaders dans aucun domaine, par contre, si vous doutez de tout, vous serez paralysé et ne ferez rien . Quand douter, quand apprendre les bases, quand penser par vous-même et quand continuer et prendre les choses telles qu'elles sont, c'est une question de style de pensée, et je ne peux pas donner une formule simple pour résoudre ce problème. Vous devez apprendre de votre propre expérience. Les gains importants surviennent généralement après des changements importants dans les hypothèses sous-jacentes sur lesquelles la zone est basée. L'état de nos connaissances détermine l'équilibre entre les différents aspects de la recherche. Il semble que lorsque vous êtes jeune, l'intuition et la perspicacité ont plus de temps à payer, mais quand vous êtes vieux,moins de temps est laissé pour cela et devrait probablement se concentrer sur ce qui est déjà à portée de main.

À suivre ...

Qui veut aider à la traduction, la mise en page et la publication du livre - écrivez dans un e-mail personnel ou par courrier électronique magisterludi2016@yandex.ru

Soit dit en passant, nous avons également lancé la traduction d'un autre livre cool - "La machine à rêver: l'histoire de la révolution informatique" )