lundi 25 février 2013

penser base 2

Dans la vie de tous les jours on utilise la base décimale et lorsqu'on fait de la programmation de haut niveau en général on continue à travailler avec la base décimale et parfois avec la base hexadécimale. Mais lorsqu'on travaille avec de petits micro-controlleurs il vaut mieux penser base 2. Dans cette chronique je vais expliquer le pourquoi et le comment de cette affirmation.

So tiny!

Les MCU atTiny ne s'appelle pas ainsi parce qu'ils sont physiquement petit, même s'ils peuvent l'être, mais parce que les ressources dont on dispose sur ces MCU sont vraiment limitées. l'atTiny13A par exemple avec son 1KB de mémoire flash ne permet vraiment pas d'utiliser les librairies 'C' complexes. Vous programmez en 'C' pour un atTiny13a et vous voulez faire une multiplication ou une division.

Faisons le test. Voici un petit programme qui fait des lectures analogiques et fait la moyenne de 20 échantillons pour éliminer les interférences, scénario classique.

On compile et ont constate que ça prend 224 octets de mémoire flash. Voici une autre version de ce même programme sauf qu'au lieu de faire la moyenne de 20 échantillons on va la faire sur 16 échantillons et on va remplacer la division par un opérateur >>.
Cette version prend 188 octets flash, un gain d'espace de 36 octets. En utilisant une puissance de 2 pour le nombre d'échantillons on peut remplacer la division par un décalage vers la droite de 4 positions ce qui équivaut à une division par 16. Toute multiplication par une puissance de 2 peut-être remplacée par un opérateur << avec le log2 du multiplicateur comme argument. Toute division par une puissance de 2 peut-être remplacée par un opérateur >> avec le log2 du diviseur. Non seulement le code prends moins d'espace mais l'exécution est plus rapide.

Il y a de nombreuses situations où il est judicieux de choisir des paramètres qui sont des puissances de 2 pour éviter une multiplication ou une division. C'est ce que j'appelle penser base 2. Un autre exemple est celui d'une interpolation linéaire entre 2 nombres. Au lieu de choisir un fraction décimale, on divise l'intervale en une puissance de 2. Par exemple supposons qu'on a calculer une table de sinus avec 90 valeurs stockées en mémoire flash. Soit une valeur à tous les 4 degrés. si on veut connaître la valeur au degré près on peut faire une interpolation linéaire entre les 2 valeurs.
Soit à connaître la valeur du sinus de 15 degrés:
Voilà, sans utiliser de multiplication ni de division ce code fait une interpolation linéaire pour trouver la valeur d'un sinus pour un angle qui tombe entre 2 valeurs de la table. Ça prends moins de code et c'est plus rapide. si on avait choisi de créer la table des sinus avec un interval de 3 ou 5 degrés il aurait fallu utiliser une multiplication et division.

Conclusion il faut penser en terme de base 2 lorsqu'on travaille avec de petits micro-processeurs.

dimanche 17 février 2013

Enfin une explication simple de la FFT

La FFT (transformée de Fourier rapide) est au coeur de l'analyse numérique des signaux. Depuis longtemps je cherche à comprendre son principe mais jusqu'ici je n'avais trouvé que des textes écris par des mathématiciens. Les mathématiciens adorent le langage abstrait et pour les comprendre il aurait fallu que je passes des heures à étudier ce langage. Mais moi les mathétiques ça m'intéresse pas tant que ça. Alors aujourd'hui je suis très content d'être tombé sur le blog EarLevel Engineering. J'y ai trouvé une explication simple, de la FFT. Sur cette page il y a un applet Java qui permet de contrôler la forme d'onde en ajustant les curseurs.

Quand je pense au temps que j'ai passé à essayer de décortiquer les équations des mathématiciens, j'en reviens pas que finalement c'est si simple que ça. Toute ma gratitude à Nigel Redmon, l'auteur de ce blog.

Pour une introduction à l'analyse spectrale j'ai trouvé ce vidéo en français sur youtube (durée 40 minutes).

Pour ceux qui lisent l'anglais voici un document pdf en lien avec ce sujet.

Résumé pour ceux qui ne comprennent pas l'anglais.

Tout commence avec le mathématicien Français Jean-Baptiste Fourier qui a démontré que toute fonction périodique est une somme de fonctions sinus et cosinus harmoniques de la fondamentale. Par harmonique on entend multiple entier de la fréquence fondamentale. Par exemple si on joue une note sur un instrument de musique, le son produit n'est pas pur. C'est à dire que ce n'est pas un sinusoïde mais qu'en plus de la note fondamentale, celle qu'on perçoit, il y a des harmoniques qui donnent le timbre particulier de l'instrument. Si on branche un micro sur l'entrée d'un oscilloscope et qu'on regarde la forme d'onde on vois bien que c'est périodique mais pas sinuoïdal. Pour connaître le contenu harmonique d'un signal on utilise l'analyse de Fourier. Sur les ordinateurs il existe un classe d'algorithmes appellés FFT pour Fast Fourier Transform qu'on pourrait traduire par Transformée de Fourier Rapide.

Si on considère un son quelconque par exemple le bruit d'un moteur de voiture on pourrait penser qu'il n'y a rien de périodique dans ce bruit. Mais en fait tout son est le résultat d'un vibration ou de la somme de plusieurs vibrations. On peut donc décomposer n'importe quel son en utilisant l'analyse de Fourier.

Si on multiplie 2 ondes sinusoïdales de même fréquence l'une par l'autre et qu'on calcule la valeur moyenne cette valeur sera proportielle à l'amplitude des 2 sinusoïdes. Par contre si les 2 sinusoïdes sont de fréquence différentes la moyenne sera nulle quel que soit les amplitudes de chacune d'elle.

Il faut d'abord échantillonner le signal. C'est à dire convertir le signal qui nous intéresse en une série de valeur numérique en utilisant un convertisseur analogue/numérique. Prenons l'exemple d'une carte son d'ordinateur. On branche un micro et on enregistre un son quelconque pendant une seconde à raison de 44000 échantillons par secondes. On a donc 44000 échantillons. On veut connaître le spectre de fréquences de cet enregistrement.

Donc si on veut savoir si une fréquence x est contenue dans ce signal complexe on multiple le signal par la fonction sinus(Fx). Si la fréquence x est contenue dans le signal la moyenne sera porportionnelle à l'amplitude de cette fréquence présente dans le signal. Sinon le résultat sera zéro.

Par multiplication en entends qu'on prend la valeur de la fonction sinus à chaque point et qu'on multiplie chaque échantillon par cette valeur et qu'ensuite on fait la moyenne de tous ces résultats. La fonction sinus() étant une fonction continue il y a un nombre infini de valeurs dans un cycle. Il faut donc choisir un interval régulier. Cet interval est en fait déterminer par la fréquence d'échantillonnage. Par exemple Si le signal a été échantillonné 44000/seconde pour une fréquence 100hz il y a 440 échantillons par cycles. Ici on utilise la sinus() et le cosinus() car la phase de notre sonde ne correspond pas nécessairement à la phase de cette fréquence dans le signal. En faisant le produit par le sinus et le cosinus et en calculant l'hypothénuse ça devrait nous donner la bonne amplitude de la composante signal.

C'est ce que j'ai compris mais je vous suggère de fouillez vous même l'internet afin de trouver des info supplémentaire. voici un autre lien en français, mais celui-là est plus mathématique (produit maticricel): http://perso.telecom-paristech.fr/~danger/amen_old/fft/

mise à jour 2015-09-17

Je viens de découvrir ce vidéo qui illustre bien la composition d'une onde carré à partir de l'addition d'harmoniques.


Quelques références

  • The Scientist and Engineer's Guide to Digital Signal Processing par Steven W. Smith. PDF. Le plus intéressant car pas trop mathématique.
  • Real-time digital signal processing, 2ed, Kuo,Lee,Tian. PDF
  • A technical tutorial on digital signal synthesis, Analog Device corp. PDF
  • Digital signal processing, Markus Kuhn. PDF
  • DSP and application with the C6713 and C6416 DSK. Rulph Chassaing. PDF
  • Voici un vidéo en anglais avec une explication simple de la FFT. https://youtu.be/spUNpyF58BY. Le canal 3Blue1Brown contient en fait plusieurs vidéos relié à ce sujet.

vendredi 15 février 2013

Le jacasseux

Il s'agit d'une découverte accidentelle. Je dirais que le son produit doit ressemblé à celui d'une poule verbo-moteur qui caquette après avoir respiré de l'hélium. Je ne vous explique pas comment ça fonctionne. Si ça vous intéresse vous étudier le code et essayez de comprendre par vous même. Avec un petit haut-parleur de 130 ohm le son s'entend bien mais si vous avez un petit ampli ce sera mieux. Si vous éliminez le filtre passe-bas et branchez le haut-parleur directement sur RA1 le son sera plus fort.
Indice les 2 oscillateurs le PWM1 et le NCO fonctionnent tous les deux à la fréquence de 125Khz. Utilisez un fil de plusieurs centimètres pour relier C1 à RA2, question de bien capter les interférences électromagnétiques.

jacasseux.asm

pic12f322_m.inc

mercredi 6 février 2013

forth n'est pas mort

Cette chronique est en réaction à un commentaire d'un internaute sur un forum qui s'étonnait qu'un programmeur utilise le langage forth. N'en déplaise à certains ce language de programmation inventé dans les années 60 par Charles H. Moore est encore utilisé de nos jours. Si on consulte l'index Tiobe sur l'utilisation des différents langages de programmations forth se retrouve en 38ième position. Considérant qu'il existe des centaines de langages ce n'est pas si mal.

Même si je n'ai personnellement pas utilisé beaucoup le forth, j'en apprécie néanmoins la grande simplicité de la syntaxe. Cette syntaxe est déroutante au début car les langages les plus utilisés de nos jours ont tous une syntaxe qui ressemble à celle du C/C++. Le forth c'est totalement différent. En forth tout est affaire de vocabulaire. Une programme est un mot qui est défini à partir des mots de bases. Donc au départ il y a un dictionnaire qui contient un certains nombres de mots et à partir de ceux-ci on défini de nouveaux mots en utilisant les mots primitifs.

En forth il n'y a pas de mots réservés, on peut même donner une novuelle définitions aux mots primitifs.

En forth la pile est la structure de donnée de base. Toutes les opérations sont effectuées sur les objets qui sont préalablement empilés par exemple pour additionner 2 nombres la sequénce est la suivante:
23 24 +

le nombre 23 est envoyé sur la pile ensuite le nombre 24 puis le mot primitif + effectue l'addition. Les arguments précèdent tourjours l'action. Si je veux définir le mot carre
: carre dup * ;
le mot : appelle le compilateur, il est suivit du nom du mot à définir ensuite de sa définition. Le mot ; termine la définition. Le seul séparateur est l'espace et un mot peut contenir n'importe quel caractère sauf l'espace, par exemple:
: 2 2 * ;
je viens de définir un nouveau mot qui s'appelle 2 et c'est tout à fait valide. Ce mot multiplie par 2 le nombre qui est au sommet de la pile. Pour ce faire il commence par empiler le nombre 2 et ensuite il appelle le mot * qui effectue la multiplication. Le résultat remplace les arguments au sommet de la pile. Bien sur il n'est pas conseiller de définir un nombre comme mot car on ne pourra plus l'utiliser jusqu'à ce qu'on est supprimer du dictionnaire le mot 2.

Le forth n'a pas simplement une syntaxe très simple il est aussi très simple de créer un compilateur pour ce langage et aussi simple de créer une machine virtuelle pour interpréter du bytecode forth. Si je devais créer une machine virtuelle pour un MCU j'utiliserais sans doute une machine à piles forth, pour sa simplicité et son économie d'espace.

Même si forth n'est pas main stream les machines virtuelles qui utilise le modèle à pile sont nombreuses, Java vm, javascript vm, .net vm, postscript vm, le firmware des imprimantes HP (HPGL), etc.

Voici quelques liens concernant forth
Introduction à forth (dernière mise à jour 2009).
rforth1 sur PIC18
groupe d'intérêt du forth (anglais)
GA-144, un chip qui contient 144 ordinateurs forth en réseau (anglais). La compagnie GreenArray a été fondée par Charles H. Moore lui-même. A 75 ans il est toujours actif.
swift forth, un produit commercial (anglais).
Le logiciel libre gforth (anglais)