Voir la source de Algorithme de Karplus-Strong

[[File:Karplus-strong-A2.ogg|thumb|Exemples d'applications répétées de l'algorithme, pour produire un son d'[[instrument à cordes pincées]], en appliquant de manière répétée un [[filtre passe-bas]] sur une forme d'[[onde]], dont la [[fréquence fondamentale]] est de {{Unité|220|[[Hertz|Hz]]}}, jouée en boucle.]]

Le terme d''''algorithme de Karplus-Strong''', du nom des enseignants-chercheurs {{Lien|Kevin Karplus}} 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'[[Instrument à cordes pincées|instruments à cordes pincées]] et de [[Batterie (instrument)|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]]<ref name="mit">https://users.soe.ucsc.edu/~karplus/papers/digitar.pdf</ref>.

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 [[Mémoire tampon|buffer]] réinscriptible en informatique<ref name="python">{{lien web |langue=en |titre=Generating synthetic guitar sounds with the Karplus Strong algorithm |url=https://archive.wikiwix.com/cache/20211212154941/https://flothesof.github.io/Karplus-Strong-python.html |site=flothesof.github.io via [[Wikiwix]] |date=03-03-2014 |consulté le=21-11-2023}}.</ref> ou l'emploi d'une [[Ligne à retard (électronique)|ligne de délai]] avec retour en électronique<ref name="mit" /> ; 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 [[Harmonique (musique)|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 [[Échantillonnage (signal)|échantillons]] adjacents à chaque application successive. Néanmoins, n'importe quel [[Filtre (audio)|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 ===
<center>
[[Image:Karplus-strong-schematic.svg|440px]]
</center>

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]]<ref name="mit" /> est illustrée par le schéma ci-dessus.

# Tout d'abord, un extrait sonore de taille fixée (<math>L</math> é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 [[Timbre (musique)|texture]] sensiblement différente.
# Cet extrait sonore, en plus d'être envoyé vers la sortie sonore principale, est simultanément envoyé vers une [[Ligne à retard (électronique)|ligne de délai]] ayant un délai correspond à la taille de la forme d'onde (<math>L</math> é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'[[Résonance#Amortissement|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<ref name="mit" />.

De fait, l'effet de [[Filtre (audio)|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<ref name="python" />.

=== Implémentations informatiques ===
{{...}}
Le principe de l'algorithme de Karplus-Strong sert de base à de nombreux [[synthétiseur]]s, 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<ref>https://manual.audacityteam.org/man/pluck.html</ref>.

Ci-dessous se trouve un exemple d'implémentation basique de l'algorithme en [[Langage de programmation|langage]] [[Python (langage)|Python]].

{{Boîte déroulante|titre=Exemple d'implémentation basique de l'algorithme de Karplus-Strong en [[Python (langage)|Python]]|contenu=
<syntaxhighlight lang="python">
#!/usr/bin/python3
#-*- encoding: Utf-8 -*-
from numpy import array as np_array
from scipy.io.wavfile import write
from sounddevice import play
from random import random
from typing import List

# Install dependencies:
# sudo pip3 install --upgrade scipy sounddevice numpy

# All frequencies used below are expressed in Hertz

def karplus_strong(
    noise_samples : List[int],
    number_output_samples : int
):
    
    output_samples : List[int] = []
    
    for wavetable_iteration in range(number_output_samples // len(noise_samples)):
        for output_position in range(len(noise_samples)):
            
            wavetable_position = output_position % len(noise_samples)
            
            # Apply the (very simple) low-pass filter = mean over adjacent PCM
            # samples values over each sample
            
            noise_samples[wavetable_position] = (
                noise_samples[wavetable_position] +
                noise_samples[(wavetable_position - 1) % len(noise_samples)]
            ) / 2
        
        # Copy the next iteration of filtered waveform into the output
        
        output_samples += noise_samples
    
    return np_array(output_samples)

def do_karplus_strong_with_noise(
    output_length_seconds : float,
    fundamental_frequency : int
) -> None:
    
    work_sampling_frequency = 8000
    
    resampled_sampling_frequency = int(8000 * (2.0 / output_length_seconds))
    
    # Calculate the length in samples of a single wavelength
    
    wavelength_in_samples = int(round(
        (work_sampling_frequency / fundamental_frequency) *
        (resampled_sampling_frequency / work_sampling_frequency)
    ))
    
    # Generated random samples in the range [-1.0;1.0]; as expected by Numpy
    
    noise_samples : List[float] = [random() * 2 - 1 for i in range(wavelength_in_samples)]
    
    # Apply the Karplus-Strong plucked string algorithm over the noisey waveform
    
    pluck_samples : List[float] = karplus_strong(
        list(noise_samples),
        work_sampling_frequency * 2 # Apply the algorithm to 2 seconds of sample at 8000 Hz
    )
    
    # Play the output sound
    
    play(pluck_samples, blocking = True, samplerate = resampled_sampling_frequency)
    
    # In addition, save the produced sound to a file in order to enable
    # further analysis with software such as Audacity
    
    write('output_file.wav', resampled_sampling_frequency, pluck_samples)

do_karplus_strong_with_noise(
    output_length_seconds = 0.363,
    fundamental_frequency = 303
)

</syntaxhighlight>
}}

Dans un [[Langage de programmation de bas niveau|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 [[Opération bit à bit|décalage]] d'un bit vers la droite (équivalent d'une division par deux)<ref>Pages 44 et 45 de la publication au sein du journal de recherche original</ref>. À l'époque de la suggestion, en [[1983]], cela permet la synthèse en temps réel avec les processeurs de l'époque [[Intel 8080|Intel 8080A]], {{Lien|Texas Instruments TMS9900}} et [[National Semiconductor SC/MP|SC/MP]]<ref>Page 43 de la publication au sein du journal de recherche original</ref>.

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 {{Lien|trad=Digital waveguide synthesis|guide d'ondes numérique}} sont présentes dans le ''STK'' (''Sound Toolkit'') édité par le [[CCRMA]] de l'[[université Stanford]], publié sous licence libre<ref>{{Lien web |langue=en |titre=The Synthesis ToolKit in C++ (STK) |url=https://ccrma.stanford.edu/software/stk/ |date= |site=[[CCRMA]], [[Université Stanford]] |consulté le=9 mars 2021}} </ref>.

=== Détail de la production des harmoniques ===
[[Fichier:Sample Karplus-Strong output spectrogram, obtained with Audacity.png|thumb|Illustration d'un [[spectrogramme]] (ou [[sonogramme]]) d'une vibration produite avec l'algorithme de Karplus-Strong, généré avec [[Audacity]] par une [[Transformée de Fourier à court terme|transformation de Fourier glissante]] : on observe globalement l'absence de représentation des fréquences inharmoniques (leur présence vers le début est due à un détail de fonctionnement de la transformation utilisée) et le déclin progressif des différentes harmoniques, les plus hautes en premier.]]

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é<ref>Page 47 de la publication au sein du journal de recherche original</ref>. 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]]<ref>Pages 50 à 52 de la publication au sein du journal de recherche original</ref>.

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 [[moyenne]]s 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|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<ref>Pages 47 à 48 de la publication au sein du journal de recherche original</ref>.

=== Détail de la manifestation physique ===
{{...}}

== Historique des brevets ==
{{...}}

== Algorithmes similaires ==
{{...}}

== Bibliographie ==
{{Légende plume}}
* {{Plume}} {{Article |langue=en |auteur1={{Lien|Kevin Karplus}} |auteur2=Alex Strong |périodique=[[Computer Music Journal]] |titre=Digital Synthesis of Plucked-String and Drum Timbres |sous-titre= |lieu= |éditeur=[[MIT Press]] |date=été [[1983]] |volume=7 |numéro=2 |pages totales=13 |passage=43-55 |issn=0148-9267 |e-issn=1531-5169 |lire en ligne=https://users.soe.ucsc.edu/~karplus/papers/digitar.pdf }}
* {{Article |langue=en |auteur1={{Lien|David A. Jaffe}} |auteur2=Julius O. Smith |périodique=[[Computer Music Journal]] |titre=Extensions of the Karplus-Strong Plucked String Algorithm |sous-titre= |lieu= |éditeur=[[MIT Press]] |date=été [[1983]] |volume=7 |numéro=2 |pages totales=14 |passage=56-69 |issn=0148-9267 |e-issn=1531-5169 |lire en ligne=http://musicweb.ucsd.edu/~trsmyth/papers/KSExtensions.pdf }}

== Notes et références ==
{{References}}

== Voir aussi ==
=== Articles connexes ===
* [[Synthèse par modélisation physique]]
* [[Instrument à cordes pincées]]
* [[Résonance acoustique]]

=== Liens externes ===
{{...}}

{{Portail|Musique|informatique|musique électronique}}

[[Catégorie:Acoustique]]
[[Catégorie:Traitement du son]]
[[Catégorie:Son]]
[[Catégorie:Traitement numérique du signal]]
[[Catégorie:Algorithme numérique]]