# Algorithme de Karplus-Strong

Le terme d'algorithme de Karplus-Strong, du nom des enseignants-chercheurs Kevin Karplus (en) et Alexander Strong qui l'ont respectivement analysé et inventé, désigne un ensemble de techniques simples permettant la synthèse d'aspect réaliste d'instruments à cordes pincées et de batterie. Il est classé dans les algorithmes de synthèse par modélisation physique.
Il est documenté par les chercheurs susnommés dans le Computer Music Journal du Massachusetts Institute of Technology en 1983, qui le développent entre 1978 et 1979.
Son principe repose sur l'emploi répété d'un filtre passe-bas, lequel agit plus fortement sur les plus hautes fréquences et plus faiblement sur les plus basses fréquences, appliqué cycliquement sur une même forme d'onde. Il effectue donc une interpolation entre une forme d'onde complète et du silence, mais avec une disparition plus rapide des hautes fréquences, la périodicité de la forme d'onde de base entraînant également une absence de fréquences inharmoniques à cette forme d'onde.

## Principe de fonctionnement

Algorithme du domaine temporel, il fonctionne, dans sa version la plus simple, par la répétition d'une forme d'onde (dans la publication originale, un extrait de bruit blanc), répétition qui peut être effectuée par la copie d'un buffer réinscriptible en informatique ou l'emploi d'une ligne de délai avec retour en électronique ; sur laquelle sera appliquée de manière répétée, au fil des itérations, un filtre dégradant progressivement les plus hautes harmoniques de la forme d'onde, de façon à modéliser la dégradation des vibrations telle qu'observable sur un vrai instrument.
Cette dégradation fonctionne, avec l'algorithme original, de manière très simple et naïve puisqu'elle se résume à effectuer des moyennes entre échantillons adjacents à chaque application successive. Néanmoins, n'importe quel filtre fréquentiel peut être utilisé pour obtenir un résultat semblable, du moment qu'il entraîne une dégradation plus rapide des harmoniques hautes et plus faible des harmoniques basses.

### Implémentation électronique

L'implémentation électronique de Karplus-Strong, telle que décrite en figure 2, page 45 de la publication originale au sein du Computer Music Journal est illustrée par le schéma ci-dessus.
* Tout d'abord, un extrait sonore de taille fixée ($L$ échantillons discrets, correspondant à une seule forme d'onde dans le domaine temporel, et donc à une longueur d'onde à la fréquence fondamentale voulue) est envoyée dans le système. Dans l'implémentation initiale, il s'agit de bruit blanc, mais cela n'empêche pas l'emploi d'une autre forme d'onde comme un signal en dents de scie filtré ou non pour obtenir des résultats à la texture sensiblement différente.
* Cet extrait sonore, en plus d'être envoyé vers la sortie sonore principale, est simultanément envoyé vers une ligne de délai ayant un délai correspond à la taille de la forme d'onde ($L$ échantillons), et qui produira donc une sortie une fois que la première forme d'onde aura été jouée.
* Un filtre passe-bas très basique est appliqué sur la sortie cette première ligne de délai. Il est implémenté, dans la publication initiale, par l'application d'une moyenne entre chaque échantillon de la forme d'onde et la précédente (cette moyenne impliquant l'utilisation d'une seconde ligne de délai d'une longueur d'un échantillon).
* Une sortie audio provenant de l'extrait sonore initial, le temps de première forme d'onde (elle est alors constituée de forme d'onde originale, avec toutes ses harmoniques, jouée une seule fois), puis du filtre passe-bas vers lequel est réinjecté cycliquement le signal modifié est produite.
Pour comprendre comment fonctionne le filtre passe-bas simple suggéré par l'article de recherche, il faut comprendre les effets de l'opération de moyenne utilisée. Puisque cette perte de résolution est effectuée sur des échantillons adjacents, les plus hautes fréquences sont d'abord touchées et davantage que les basses, et puisque chaque valeur est transformée en une moyenne entre elle-même et la précédente, l'amplitude totale de la forme d'onde finit forcément par décroître. Cela reflète l'amortissement de la résonance.

#### Variante pour la production de sons de batteries

En plus de l'algorithme de génération de cordes pincées mentionné ci-dessus, l'article de recherche fait mention, en pages 46 à 47 du journal de publication, d'un algorithme de génération de sons de batteries.
De base, son principe consiste, pour une fraction répartie aléatoirement correspondant à 50 % des échantillons produits, à inverser le signe de l'échantillon après l'opération de moyenne.
De fait, l'effet de filtre fréquentiel est perdu et le son produit, apériodique, se rapproche d'un simple extrait de bruit irrégulier avec un fondu en fermeture.

### Implémentations informatiques

Le principe de l'algorithme de Karplus-Strong sert de base à de nombreux synthétiseurs, virtuels ou non. Le générateur « Pluck » (cordes pincées) du logiciel Audacity est basé sur son principe, d'après les déclarations des développeurs.
Ci-dessous se trouve un exemple d'implémentation basique de l'algorithme en langage Python.
Dans un langage de bas niveau, l'implémentation de l'algorithme est économe puisque l'opération de moyenne constituant le filtre passe-bas peut être implémentée avec une division et un décalage d'un bit vers la droite (équivalent d'une division par deux). À l'époque de la suggestion, en 1983, cela permet la synthèse en temps réel avec les processeurs de l'époque Intel 8080A, Texas Instruments TMS9900 (en) et SC/MP.
Plusieurs implémentations de référence en C++ de l'algorithme de synthèse de cordes pincées, ainsi que d'autres algorithmes dérivés de Karplus-Strong et notamment de type guide d'ondes numérique (en) sont présentes dans le STK (Sound Toolkit) édité par le CCRMA de l'université Stanford, publié sous licence libre.

### Détail de la production des harmoniques

Dans l'algorithme de synthèse de sons de cordes pincées (algorithme de Strong inventé en décembre 1978), illustré ci-dessus, il peut être observé que le déclin d'une harmonique s'étale sur une durée approximativement proportionnelle au nombre d'échantillons d'une seule forme d'onde au cube, divisé par le numéro de l'harmonique en question au carré. Une analyse mathématique plus détaillée est proposée par le papier de recherche, proposant notamment un calcul exact qui dépend de paramètres trigonométriques et est mis en relation avec le principe de transformée en Z, lui-même sous-jacent au plus classique filtre en peigne.
Plus prosaïquement, les corollaires de base qui permettent le fonctionnement de l'algorithme peuvent être expliquées expérimentalement comme il suit :
* Le fait de répéter cycliquement une forme d'onde aléatoire de taille courte suffit à créer un motif périodique, faisant apparaître à l'intervalle de la forme d'onde et à toutes ses harmoniques du contenu fréquentiel.
* Le fait que des harmoniques, de différentes intensités, soient présentes dans la forme d'onde initiale est dû au caractère apériodique de la forme d'onde choisie.
* Le lissage de la forme d'onde en remplaçant les valeurs discrètes par des moyennes contribue à la baisse progressive de la présence d'harmoniques au sein du signal, et donc de la présence de contenu fréquentiel audible (dans le domaine temporel, on tend vers un signal continu qui n'est pas audible ; l'amplitude moyenne décroît progressivement autour d'une intensité qui n'est pas 0).
* La première passe de l'algorithme ayant d'abord un effet sur les échantillons adjacents entre eux, et induira donc d'abord une perte de résolution au niveau des éventuelles harmoniques proches de la fréquence de Nyquist ; ce sera par effet boule de neige que, progressivement, le signal sera de plus en plus lisse puisque des intervalles de plus en plus grandes seront touchées par des moyennes entre échantillons éloignés.
La longueur du déclin, de même que la fréquence de base du son produit, peuvent être modulées par un rééchantillonnage ainsi que par un changement de la longueur d'onde correspondant à la fréquence de base. Le papier évoque également la possibilité de remplacer une partie des opérations de moyenne par des opérations de copie sans modification afin de l'« étendre », ce qui tend à modifier l'aspect du son.