Ein anderes Beispiel - Interview zum Logidy EPSi, Frage und Antwort 3:
Original:
Can you comment on the convolution algorithms used in EPSi? From what I understand, convolution is around since long, code for it is published in Numerical Recipes, which is available since 1985/86. How much of research was needed to get from such sources, which include the explanation of the math behind to the final code, which is now run in EPSi?
Discrete causal convolution is: y(n) = sum(i = 0: inf) of x(n-i)*s(i), where s(n) is an infinite discreet impulse response. For a finite impulse response the sum is finite and the process is then called Finite Impulse Response (FIR) filtering. For an impulse response of length N, every output sample requires N multiply-accumulates.
In the frequency domain, convolution becomes a multiplication which only costs a few cycles per output sample. Therefore fast convolution can be done in the frequency domain using a Fast Fourier Transform (FFT) algorithm and its inverse to convert audio from and back to the time domain. A complication arises when low throughput latency is required. Efficiency per sample increases with the size of the data segments used in the FFT. The biggest segment processed in the EPSI is 8192 sample wide, which incurs a latency of 16384 samples on the outputs, an unacceptable 370 ms of delay. All the trickery then resides in the use of data segments of multiple sizes in order to fill that gap.
The EPSi is capable of running impulse responses up to 262 144 samples long. The direct convolution for such files at 44.1KHz requires about 11.5 billion multiply-accumulate cycles per second. But the DSP I am using is only capable of about 0.6 billion multiply-accumulate cycles per second. The FFT approach then affords a factor 20 in window length.
Although I built this algorithm entirely on my own, I since learned of other commercial efforts having followed the same path, most of them put to work on computer native products.
DeepL:
Können Sie sich zu den in EPSi verwendeten Faltungsalgorithmen äußern? Soweit ich weiß, gibt es die Faltung schon seit langem, Code dafür ist in Numerical Recipes veröffentlicht, die seit 1985/86 verfügbar ist. Wie viel Forschung war nötig, um von solchen Quellen zu erhalten, die die Erklärung der Mathematik hinter dem endgültigen Code beinhalten, der jetzt in EPSi ausgeführt wird?
Diskrete kausale Faltung ist: y(n) = Summe(i = 0: inf) von x(n-i)*s(i), wobei s(n) eine unendliche diskrete Impulsantwort ist. Für eine endliche Impulsantwort ist die Summe endlich und der Prozess wird dann als Finite Impulse Response (FIR) Filterung bezeichnet. Für eine Impulsantwort der Länge N benötigt jedes Ausgangs-Sample N Multiplikationsakkumulationen.
Im Frequenzbereich wird die Faltung zu einer Multiplikation, die nur wenige Zyklen pro Ausgangsstichprobe kostet. Daher kann eine schnelle Faltung im Frequenzbereich mit Hilfe eines Fast Fourier Transform (FFT)-Algorithmus und seiner Inverse durchgeführt werden, um Audio von und zurück in den Zeitbereich zu konvertieren. Eine Komplikation entsteht, wenn eine geringe Durchsatz-Latenzzeit erforderlich ist. Die Effizienz pro Stichprobe steigt mit der Größe der in der FFT verwendeten Datensegmente. Das größte Segment, das in der EPSI verarbeitet wird, ist 8192 Sample Wide, was eine Latenz von 16384 Samples auf den Ausgängen bedeutet, eine unannehmbare Verzögerung von 370 ms. Alle Tricks liegen dann in der Verwendung von Datensegmenten unterschiedlicher Größe, um diese Lücke zu schließen.
Die EPSi ist in der Lage, Impulsantworten mit einer Länge von bis zu 262 144 Samples auszuführen. Die direkte Faltung für solche Dateien bei 44,1 kHz erfordert etwa 11,5 Milliarden Multiplikations-Akkumulationszyklen pro Sekunde. Aber der DSP, den ich benutze, ist nur in der Lage, etwa 0,6 Milliarden Multiplikator-Zyklen pro Sekunde zu erzeugen. Der FFT-Ansatz bietet dann einen Faktor 20 in der Fensterlänge.
Obwohl ich diesen Algorithmus vollständig selbst entwickelt habe, habe ich seitdem von anderen kommerziellen Bemühungen erfahren, die denselben Weg eingeschlagen haben, die meisten von ihnen haben sich an nativen Computerprodukten orientiert.
Mensch (ich selber):
Kannst du uns etwas zu den Faltungsalgorithmen sagen, die in EPSi verwendet werden? Sowie ich es verstehe, gibt es Faltung seit langem, entsprechende Algorithmen sind beispielsweise in den Numerical Recipes veröffentlicht, diese gibt es seit 1985/86. Wie viel eigene Forschung war nötig, um von diesen Quellen, die auch die ganze Mathematik dahinter erklären, zum schlussendlichen Code zu kommen, der nun im EPSi läuft?
Zeitdiskrete Faltung wird geschrieben als: y(n) = sum(i = 0: inf) von x(n-i)*s(i), wobei s(n) eine unendliche diskrete Impulsantwort ist. Für eine endliche Impulsantwort ist die Summe ebenfalls endlich. Man nennt den Vorgang dann Filterung mit endlicher Impulsantwort (Finite Impulse Response (FIR) filtering). Bei einer Impulsantwort der Länge N benötigt jedes Ausgangs-Sample N Multiply-Accumulates.
Im Frequenzbereich wird aus der Faltung eine einfache Multiplikation, die nur einige Taktzyklen pro Ausgangs-Sample benötigt. Daher kann man schnelle Faltung im Frequenzbereich mithilfe der Schnellen Fourier Transformation (FFT) und ihrer Umkehrung durchführen. Man transformiert das Signal einfach vom Zeit- in den Frequenzbereich, faltet durch Multiplikation und transformiert zurück. Wenn man niedrige Latenzen erreichen möchte, wird es etwas komplizierter. Die Effizienz pro Sample wächst mit steigender Größe der verwendeten Datensegmente bei der FFT. Im EPSi ist das größte verwendete Segment 8192 Samples groß, daraus folgt eine Latenz von 16384 Samples am Ausgang. Dies wäre ein inakzeptables Delay von 370 ms. Die ganze Kunst besteht nun darin, Datensegmente verschiedener Größen zu nutzen, um diese Lücke aufzufüllen.
EPSi kann mit Impulsantworten bis zur Länge von 262144 Samples umgehen. Eine direkte Faltung solcher Dateien bei 44,1 kHz benötigt ca. 11,5 Milliarden Multiply-Accumulate-Zyklen pro Sekunde. Der verwendete DSP kann aber nur ca. 0,6 Milliarden Multiply-Accumulate-Zyklen pro Sekunde ausführen. Der FFT Ansatz führt hier zu einem Faktor 20 in der Länge der Impulsantwort.
Obwohl ich diesen Algorithmus komplett alleine entwickelt habe, habe ich später von anderen Produktentwicklungen erfahren, die denselben Ansatz verfolgen, die meisten davon für die Verwendung auf gewöhnlichen Computern.
Es ist erstaunlich gut, aber der Vibe geht leicht verloren und etwas komplexere Formulierungen gehen knapp am Ziel vorbei. Schade, dass Roland soetwas in den 80ern nicht hatte. Was wäre uns erspart geblieben...