Chapter 1
INTRODUCTION
It is well known that linear, time invariant electrical and acoustical systems can be defined by their measured impulse responses. The convolution of this impulse response with an arbitrary input signal produces the exact output of the system were the input signal actually applied to it. Disregarding measurement inaccuracies, a desired output can be achieved without ever introducing the input signal to the existent system. A signal processing platform with this capability would certainly be advantageous to users who would not otherwise have the opportunity to incorporate unique, expensive, or otherwise difficult to procure electrical or acoustical systems into their work.
The convolution operation is, at best, computationally demanding. In the time domain, the convolution of an Nx-point signal with an Nh-point impulse response requires Nx.Nh multiplications and Nx+Nh-1 additions. In the frequency domain, disregarding transform and inverse transform overhead, the same convolution still requires Nx+Nh-1 complex multiplications. To put this into perspective, consider two three-second audio signals, sampled at 44.1 kHz. The time domain convolution of these two signals would require approximately 17.5 billion multiplications and 265,000 additions. The frequency domain convolution would require approximately 265,000 complex multiplications plus the significant overhead incurred by the transform and inverse transform operations.
Existing systems (Farina & Righini, 1997) incorporate block convolution methods, which allow smaller, discrete blocks of the input to be convolved and sequentially concatenated. At least one system, implemented by Lake DSP, Inc. (McGrath, 1995), incorporates a hybrid time and frequency domain variation of block convolution summarized by Gardner (1995). Although theoretically sound, this solution introduces further complexity and overhead that requires dedicated signal processing hardware to achieve zero latency.
Current personal computing technology offers just enough speed and computational power to perform a dedicated convolution in near real time. Microsoft’s® DirectX® technology, for example, provides developers with the opportunity to operate on discrete, streaming buffers of existing audio or video data (deCarmo, 1998). Among others, Sonic Foundry’s® Acoustic Modeler® DirectX plug-in exploits this technology. The plug-in allows the user to preview a convolution result on streaming audio data (Sonic Foundry, 1997). Presumably, further improvements to existing technology and algorithms will reduce the computational load and resultant latency to the point where convolution with very low or zero latency on the personal computer becomes feasible. Besides reducing potential latency, a convolution algorithm with lower computational demands frees resources for concurrent processing.
The goal of this project is to attempt to reduce the computational complexity of convolution processes using multirate filter banks. Multirate filter banks split a wideband signal’s frequency content into multiple sub-bands (Vaidyanathan, 1993a). Such filter banks are deemed "multirate" because they effectively alter the sampling rate of the input signal while processing. Multirate filtering has been used extensively in audio compression algorithms like MPEG (Pohlmann, 1995). Data reduction, however, is not a primary objective in this research. Instead, it will be shown that a multirate filtering approach may reduce the overall number of calculations required in a given convolution scheme. A new variation on an existing algorithm specifically reduces the computation of a direct time-domain convolution by up to one half the number of operations.
The proposed variation is not ideal. Some distortion in the convolution result occurs due to the reduced computational load. Listening tests with typical musical input material and room impulse responses indicate that this distortion is often inaudible or difficult to detect in some musical material.
The paper is divided into two parts. The first part includes Chapters Two and Three. These chapters address relevant theoretical aspects of convolution and multirate processes. Chapter Four begins the second part, which combines the material from Chapters Two and Three. Chapter Five outlines the performance issues and listening test results associated with the algorithms from Chapter Four. Specifically, Chapter Two summarizes the mathematical process of discrete linear convolution and well known techniques used to reduce the number of calculations or significant input to output latency inherent to the process. Chapter Three discusses relevant multirate filtering fundamentals and summarizes the derivation of the filters used. Chapter Four summarizes previous research applying multirate filtering concepts to various convolution algorithms and discusses the proposed variation. Chapter Five addresses the computational performance of the methods from Chapter Four. Chapter Six outlines possible areas of future research. Chapter Seven concludes the paper.