Guidon Yann

Le Jeu de la Vie de John H. Conway est encore loin d'avoir livré tous ses secrets ! Son créateur estime que les propriétés fondamentales de ce célèbre automate cellulaire sont maintenant déterminées [1], mais les réalisations informatiques continuent de progresser et deviennent de plus en plus audacieuses [2]. Nous décortiquerons une famille d’algorithmes « latéraux » efficaces en temps de calcul, économes en mémoire, pour débrider toute la puissance de votre PC dernier cri.

La compression est cet art fascinant de représenter les informations avec le moins de bits possible. Une des premières façons de compresser des données est d'éviter de gaspiller de la place à cause de représentations redondantes ou inutiles. Les codes binaires classiques sous-utilisent souvent l'espace de codage occupé, alors que les techniques de codage efficaces augmentent considérablement la complexité du code. Nous allons étudier un compromis, appelé Code Binaire Tronqué, et plus particulièrement une version peu connue : les codes phase-out.

Les algorithmes de compression de signaux (sons, images, mesures physiques...) utilisent des techniques de Traitement Numérique du Signal (TNS, ou DSP en anglais) pour modéliser et analyser les données. Ils font souvent appel à des filtres numériques, dont la plupart calculent simultanément la somme et la différence de deux échantillons. Chacun de ces calculs double la dynamique des signaux, donc augmente l'espace nécessaire pour représenter les résultats. Pourtant il suffit de 2N bits pour représenter deux nombres de N bits, et non 2N+2. Il est facile d'économiser un bit, mais se passer du deuxième est une autre aventure mathématique !

Lorsqu'on veut utiliser un composant, surtout inconnu, le premier réflexe est de se procurer sa documentation et la consulter. La datasheet (ou « fiche technique » en bon français) décrit les propriétés distinctives et essentielles du composant, mais d'une manière parfois tellement concentrée que l'avalanche de nombres et de termes peut décourager les débutants. Sans connaître le jargon ou les conventions, il est d'ailleurs facile de passer à côté de détails critiques ! Je vous propose de décortiquer la structure d'une datasheet pour mieux comprendre et trier les informations pertinentes.

Ne vous contentez plus des transistors bipolaires ! Les MOSFET sont une de ces merveilles modernes dont vous auriez tort de vous passer. Nous allons aborder les côtés pratiques de leur utilisation au quotidien car, si vous ne l'avez pas déjà fait, vous les adopterez après avoir lu cet article. Ils résoudront certains de vos problèmes et rendront vos montages plus efficaces, alors examinons leurs caractéristiques.

Après avoir linéarisé l'algorithme de décompression 3R (Recursive Range Reduction) [1] et expliqué les paradigmes de programmation et le style de codage [2], intéressons-nous à la réalisation matérielle. La traduction du JavaScript vers le VHDL étant prévue dès le début, le résultat est un circuit numérique très rapide (dès la première synthèse) occupant une place négligeable dans un FPGA.

L'algorithme de compression « 3R » (Recursive Range Reduction) est loin d'être le meilleur encodeur d'entropie, mais son principe rudimentaire a du bon. L'étape de décompression n'utilise qu'une quantité limitée d'opérateurs très simples, elle est très rapide et surtout elle peut fonctionner en flot quasi continu avec une très faible quantité de mémoire temporaire. Ces propriétés sont cruciales pour transmettre ou stocker des signaux avec des microcontrôleurs ou de la logique câblée. Nous allons examiner l'algorithme naïf de décompression puis linéariser sa structure récursive, dans l'optique de réaliser le décompresseur en matériel. Étonnamment cela améliore aussi la performance de la version logicielle !

Nous allons examiner le style très inhabituel du code JavaScript de l'article précédent [1], avec lequel le circuit de décodage pour l'algorithme 3R a été mis au point. Le style est inspiré de VHDL, un langage aux multiples facettes, permettant aussi bien de décrire le comportement d'un circuit et de le simuler (avec les contraintes de sémantique qui vont avec), que de générer un circuit réel (lors de ce qu'on appelle l'étape de la synthèse logique).

« 3R » signifie Recursive Range Reduction, ou Réduction Récursive des Bornes en français. Comme la plupart des algorithmes de compression, son fonctionnement n'est pas évident au premier abord, à cause des choix et subtilités un peu inhabituels. Mais une fois ceux-ci compris, 3R est assez élégant, c'est-à-dire que si on l'utilise bien, il remplit son rôle dans la plupart des cas avec un nombre minimal d'opérations très simples.