View source for Digital delay line

[[File:M-Sample Delay Line.png|thumb|320x320px|Standard block diagram representation of the integer M delay line.<ref>{{Cite web |title=The M-Sample Delay Line |url=https://ccrma.stanford.edu/realsimple/Delay/The_M_Sample_Delay_Line.html |access-date=2023-07-06 |website=ccrma.stanford.edu}}</ref>]]

A '''digital delay line''' (or simply '''delay line''', also called '''delay filter''') is a discrete element in a [[digital filter]], which allows a [[signal]] to be delayed by a number of [[Sample (signal)|samples]]. Delay lines are commonly used to delay [[audio signal]]s feeding [[loudspeaker]]s to compensate for the [[speed of sound]] in air, and to align [[video signal]]s with accompanying audio, called [[audio-to-video synchronization]]. Delay lines may compensate for [[Latency (audio)|electronic processing latency]] so that multiple signals leave a device simultaneously despite having different pathways. 

Digital delay lines are widely used building blocks in methods to simulate [[room acoustics]], [[musical instruments]] and [[Effects unit|effects units]]. [[Digital waveguide synthesis]] shows how digital delay lines can be used as [[sound synthesis]] methods for various musical instruments such as [[string instruments]] and [[wind instruments]]. 

If a delay line holds a non-integer value smaller than one, it results in a fractional delay line (also called interpolated delay line or fractional delay filter). A series of an integer delay line and a fractional delay filter is commonly used for modelling ''arbitrary delay'' filters in [[digital signal processing]].<ref name=":0">{{Citation |last1=Laakso |first1=Timo I. |title=Splitting the unit delay [FIR/all pass filters design] |date=January 1996 |magazine=IEEE Signal Processing Magazine |volume=13 |issue=1 |pages=30–60 |doi=10.1109/79.482137 |last2=Välimäki |first2=Vesa |last3=Karjalainen |first3=Matti A. |last4=Laine |first4=Unto K.|bibcode=1996ISPM...13...30L }}</ref> The [[Dattorro industry scheme|Dattorro scheme]] is an industry standard implementation of digital filters using fractional delay lines.<ref>{{Citation |last1=Smith |first1=Julius O. |title=Computational Acoustic Modeling with Digital Delay |date=June 5, 2008 |url=http://ccrma.stanford.edu/realsimple/Delay/Delay_lines.html |website=Center for Computer Research in Music and Acoustics |access-date=2007-08-21 |last2=Lee |first2=Nelson}}</ref>

== Theory ==

The standard delay line with integer delay is derived from the [[Z-transform]] of a [[Discrete time and continuous time|discrete-time signal]] <math>x</math> delayed by <math>M</math> samples<ref>{{Cite web |title=Delay Lines |url=https://ccrma.stanford.edu/~jos/pasp/Delay_Lines.html |access-date=2023-07-06 |website=ccrma.stanford.edu}}</ref>:<blockquote><math>y[n] = x[n-M]</math>    <math>\xrightarrow[]{\mathcal{Z} }</math>    <math>Y(z) = \overbrace{ z^{-M} }^{H_M(z)} X(z).  </math></blockquote>
In this case, <math>z^{-M} = H_M(z)</math> is the integer delay filter with:

<math>\begin{cases} |\centerdot| = 1 = 0dB, & \text{zero dB gain} \\ \measuredangle = -\omega M, & \text{linear phase with } \omega=2\pi fT_s \text{ where } T_s \text{ is the sampling period in seconds } [s]. \end{cases}</math>

The discrete-time domain filter for integer delay <math>M </math> as the inverse zeta transform of <math>H_{M}(z) </math> is trivial, since it is an [[Dirac delta function|impulse]] shifted by <math>M </math><ref>{{Cite web |title=INTRODUCTION TO DIGITAL FILTERS WITH AUDIO APPLICATIONS |url=https://ccrma.stanford.edu/~jos/filters/ |access-date=2023-07-06 |website=ccrma.stanford.edu}}</ref>:<blockquote>
<math>h_m[n] = \begin{cases} \text{1}, & \text{for } n = M \\ 0, & \text{for } n \neq M. \end{cases}</math></blockquote>
Working in the discrete-time domain with fractional delays is less trivial. In its most general theoretical form, a delay line with arbitrary fractional delay is defined as a standard delay line with delay '''<math>D \in \mathbb{R}</math>''', which can be modelled as the sum of an integer component <math>M \in \mathbb{Z}</math> and a fractional component <math>d \in \mathbb{R} </math> which is smaller than one sample:{{Equation box 1|border|indent=:|title=(Fractional) Delay Line - <math> \mathcal{Z} </math> Domain|equation={{NumBlk||<math>H_{D}(z) = z^{-D} \;\;\;\;\; \text{where} \;\;\;\;\; D = \overbrace{ \lfloor D\rfloor }^M + \overbrace{ ( D - \lfloor D \rfloor ) }^{d}
</math>|{{EquationRef|Def. 1}}}}|cellpadding=6|border colour=#0073CF|background colour=#F5FFFA}}This is the <math>\mathcal{Z}</math> domain representation of a non-trivial digital [[filter design]] problem: the solution is an any time-domain filter that represents or approximates the inverse Z-transform of <math>H_{D}(z) </math>.<ref name=":0" />

== Filter design solutions ==

=== Naive solution ===
The conceptually easiest solution is obtained by sampling the continuous-time domain solution, which is trivial for any delay value. Given a continuous-time signal <math>x</math> delayed by <math>D \in \mathbb{R}</math> samples, or  <math>\tau = DT_s </math> seconds<ref name=":2">{{Cite web |title=Ideal Bandlimited (Sinc) Interpolation |url=https://ccrma.stanford.edu/~jos/Interpolation/Ideal_Bandlimited_Sinc_Interpolation.html |access-date=2023-07-06 |website=ccrma.stanford.edu}}</ref>:<blockquote><math>y(t) = x(t-D)</math>     <math>\xrightarrow[]{\mathcal{F} }</math>     <math>Y(\omega) = \overbrace{ e^{-j\omega D} }^{H_{ideal}(\omega)} X(\omega). </math>       </blockquote>

In this case, <math>e^{-j\omega D} = H_{ideal}(\omega)  </math> is the continuous-time domain fractional delay filter with:

<math>\begin{cases} |\centerdot| = 1 = 0dB, & \text{zero dB gain} \\ \measuredangle = -\omega D, & \text{linear phase} \\ \tau_{gr} = -{d\measuredangle \over{d\omega}} = D, & \text{constant group delay} \\ \tau_{ph} = -{ \measuredangle \over{\omega}} = -D, & 
 \text{constant phase delay.} \end{cases}</math>

The naive solution for the sampled filter <math>h_{ideal}[n]  </math> is the sampled inverse Fourier transform of <math>H_{ideal}(\omega)  </math>, which produces a [[Causal filter|non-causal]] [[Infinite impulse response|IIR]] filter shaped as a [[Sinc function|Cardinal Sine]] <math>sinc()</math> shifted by <math>D</math><ref name=":2" />:<blockquote><math>h_{ideal}[n] = \mathcal{F}^{-1} [H_{ideal}(\omega)] =
{1\over{2\pi}} \int\limits_{-\pi}^{+\pi} e^{j\omega D} e^{j\omega n} d\omega = 
sinc(n- D) = 
{sin(\pi (n-D))\over{\pi (n-D)}} </math></blockquote>The continuous-time domain <math>sinc</math> is shifted by the fractional delay while the sampling is always aligned to the cartesian plane, therefore:
* when the delay is an integer number of samples <math>D \in \mathbb{N} </math>, the sampled shifted <math>sinc</math> degenerates to a shifted impulse just like in the theoretical solution.
* when the delay is a fractional number of samples <math>D \in \mathbb{R}  </math>, the sampled shifted <math>sinc</math> produces a non-causal IIR filter, which is not implementable in practice.
[[File:Sampling of continuous-time domain sinc function at various fractional delay values.gif|alt=Animation of shifting sinc|center|thumb|600x600px|The ideal fractional delay line is obtained by sampling the inverse Fourier transform of the continuous-time domain fractional delay filter. Note how for integer delay value this case degenerates to simple shifted impulses. Delaying a sampled signal with this filter conceptually coincides to resampling its analog source with equal sampling period but sample alignment shifted by '''<math>D \in \mathbb{R}  </math>.''' Also note that the image shows only the few samples around zero, but the non-causal IIR is defined for an infinite number of samples in both directions of the x-axis. ]]

=== Truncated causal FIR solution ===
The conceptually easiest implementable solution is the causal truncation of the naive solution above.<ref name=":1" /> <blockquote><math>h_{\tau}[n] = \begin{cases} sinc(n-D) & \text{for } 0\leq n\leq N\\ 0 & \text{otherwise} \end{cases} \;\;\;\;\; \text{where}\;\;\;\;\; {N-1\over{2}} < D < {N+1\over{2}}\;\;\;\;\;\text{and}\;\;\;\;\;N\;\text{is the order of the filter.}</math></blockquote>Truncating the impulse response might however cause instability, which can be mitigated in a few ways:

* Windowing the truncated impulse response, therefore smoothing it. Note that in this case we have to add a further shift <math>L </math> in order to align the window and the <math>sinc() </math> and provide symmetric filtering<ref name=":1" /><ref>{{Cite journal |last=Harris |first=F.J. |date=1978 |title=On the use of windows for harmonic analysis with the discrete Fourier transform |url=http://dx.doi.org/10.1109/proc.1978.10837 |journal=Proceedings of the IEEE |volume=66 |issue=1 |pages=51–83 |doi=10.1109/proc.1978.10837 |s2cid=426548 |issn=0018-9219}}</ref>.<blockquote><math>h_{\tau}[n] = \begin{cases} w(n-D)sinc(n-D) & \text{for } L\leq n\leq L + N\\ 0 & \text{otherwise} \end{cases}  \;\;\;\;\; \text{where}\;\;\;\;\; L = \begin{cases} round(D)- {N \over{2}} & \text{for even } N\\ \lfloor D \rfloor - {N-1 \over{2}} & \text{for odd } N \end{cases}</math></blockquote>
* General [[Least squares|Least Square]] (GLS) Method:<ref name=":0" /> iteratively adjusts the frequency response by windowing a Least Square Integral Error design, which minimises the square integral error between ideal and truncated frequency responses of the filter, defined as:
<blockquote><math>E_{LS} = {1\over{2\pi}} \int\limits_{-\alpha\pi}^{\alpha\pi} w(\omega) 
|H^{truncated}_D(e^{j\omega})- H^{id}_D(e^{j\omega})|^2 d\omega
\;\;\;\;\;\text{where } 0<\alpha \leq 1 \text{ is the passband width parameter}

 </math></blockquote>
* [[Lagrange polynomial|Lagrange Interpolator]] (Maximally Flat Fractional Delay Filter):<ref>{{Cite journal |last=Hermanowicz |first=E. |date=1992 |title={{as written|Expl|icity [sic]}} formulas for weighting coefficients of maximally flat tunable FIR delays |url=https://digital-library.theiet.org/content/journals/10.1049/el_19921239 |journal=Electronics Letters |language=en |volume=28 |issue=20 |pages=1936 |doi=10.1049/el:19921239}}</ref> adds "flatness" constraints to the first N derivatives of the Least Square Integral Error. This method is of particular interest because it has a closed form solution:
[[File:Block Diagram for the Explicit Formula for Lagrange Interpolation Coefficients.png|thumb|520x520px|A block diagram representation of the Lagrange Interpolator formula.<ref>{{Cite web |last=Smith |first=Julius |date=5 September 2022 |title=Explicit Formula for Lagrange Interpolation Coefficients |url=https://ccrma.stanford.edu/~jos/Interpolation/Explicit_Formula_Lagrange_Interpolation.html |website=[[ccrma]]}}</ref>]]
<blockquote><math>h_{D}[n] = \prod_{k=0 ,\; k\neq n}^N {D-k\over{n-k}} \;\;\;\;\;\text{where}\;\;\;\;\;0\leq n \leq N</math></blockquote>What follows is an expansion of the formula above displaying the resulting filters of order up to <math>N=3 </math>:
{| class="wikitable"
|+
! colspan="5" |Lagrange Interpolator Formula Expansion<ref name=":1" />
|-
|
|<math>h_{\tau}[0] </math>
|<math>h_{\tau}[1] </math>
|<math>h_{\tau}[2] </math>
|<math>h_{\tau}[3] </math>
|-
|N = 1
|<math>1-D </math>
|<math>D </math>
| -
| -
|-
|N = 2
|<math>{(D-1)(D-2) \over{2}} </math>
|<math>-D(D-2) </math>
|<math>{D(D-1) \over{2}} </math>
| -
|-
|N = 3
|<math>-{(D-1)(D-2)(D-3) \over{6}} </math>
|<math>{D(D-2)(D-3) \over{2}} </math>
|<math>-{D(D-1)(D-3) \over{2}} </math>
|<math>{D(D-1)(D-2) \over{6}} </math>
|}

=== All-pass IIR phase-approximated solution ===
Another approach is designing an [[Infinite impulse response|IIR]] filter of order <math>N</math> with a Z-transform structure that forces it to be an all-pass while still approximating a <math>D </math> delay<ref name=":1" />:<blockquote><math>H_D(z) = {z^{-N} A(z) \over{A(z^{-1})}} = 
{a_N+a_{N-1}z^{-1}+...+a_1z^{-(N-1)}+z^{-N}\over{1+a_1z^{-1}+...+a_{N-1}z^{-(N-1)}+a_Nz^{-N}}}
\;\;\;\;\; \text{which has} \;\;\;\;\; 
\begin{cases} |\centerdot| = 1 = 0dB & 0dB \text{ gain}  \\ \measuredangle_{H_D(z)} = -N\omega + 2\measuredangle_{A(z)} = -D\omega & \text{desired value for delay } D \end{cases} </math></blockquote>The reciprocally placed [[zeros and poles]] of <math>A(z) \text{ and } A(z^{-1}) </math> respectively flatten the [[Frequency response|frequency <math>|\centerdot| </math> response]], while the [[Phase response|phase]] is function of the phase of <math>A(z) </math>. Therefore, the problem becomes designing the [[FIR filter]] <math>A(z) </math>, that is finding its coefficients <math>a_k </math> as a function of D (note that <math>a_0=1 </math> always), so that the phase approximates best the desired value <math>\measuredangle_{H_D(z)} = -D\omega </math>.<ref name=":1" /> 

The main solutions are:

* Iterative minimization of Least Square Phase Error,<ref name=":0" /> which is defined as:
<blockquote><math>E_{LS} = {1\over{2\pi}} \int\limits_{-\pi}^{\pi} w(\omega) 

|\underbrace{ \underbrace{-D\omega}_{\measuredangle_{ID}} - \underbrace{(-N\omega+2\measuredangle_{A(z)})}_{\measuredangle_{H}} }_{\Delta\measuredangle_{ H_D }}|^2d\omega


 </math></blockquote>
* Iterative minimization of Least Square [[Group delay and phase delay|Phase Delay]] Error,<ref name=":0" /> which is defined as:
<blockquote><math>E_{LS} = {1\over{2\pi}} \int\limits_{-\pi}^{\pi} w(\omega) 
| {{ \Delta\measuredangle_{ H_D } }\over{\omega}} |^2


 </math></blockquote>
* Thiran All-Pole [[Low-pass filter|Low-Pass Filter]] with Maximally Flat [[Group delay and phase delay|Group Delay]].<ref>{{Cite journal |last=Thiran |first=J.-P. |date=1971 |title=Recursive digital filters with maximally flat group delay |url=https://ieeexplore.ieee.org/document/1083363 |journal=IEEE Transactions on Circuit Theory |volume=18 |issue=6 |pages=659–664 |doi=10.1109/TCT.1971.1083363 |issn=0018-9324}}</ref> This yields a closed solution for finding the coefficients <math>a_k </math> for positive delay <math>D>0 </math>:

<blockquote><math>a_k = (-1)^k\binom{N}{k}\prod_{l=0}^N {D+l \over{D+k+l}}
\;\;\;\;\; \text{where} \;\;\;\;\;
\binom{n}{k} = {N! \over{k! (N-k)! }}  </math></blockquote>
What follows is an expansion of the formula above displaying the resulting coefficients of order up to <math>N=3 </math>:
{| class="wikitable"
|+
! colspan="5" |Thiran All-Pole Low-Pass Filter Coefficients Formula Expansion<ref name=":1">{{Cite web |last=Välimäki |first=Vesa |date=1998 |title=Discrete Time Modeling of Acoustic Tubes Using Fractional Delay Filters |url=http://users.spa.aalto.fi/vpv/publications/vesan_vaitos/ |access-date= |website=}}</ref>
|-
|
|<math>a_0 </math>
|<math>a_1 </math>
|<math>a_2 </math>
|<math>a_3 </math>
|-
|N = 1
|1
|<math>-{D-1\over{D+1}} </math>
| -
| -
|-
|N = 2
|1
|<math>-2{D-2\over{D+1}} </math>
|<math>{(D-1)(D-2) \over{(D+1)(D+2)}} </math>
| -
|-
|N = 3
|1
|<math>-3{D-3\over{D+1}} </math>
|<math>3{(D-2)(D-3) \over{(D+1)(D+2)}} </math>
|<math>-{(D-1)(D-2)(D-3) \over{(D+1)(D+2)(D+3)}} </math>
|}

== Commercial history ==
[[File:DDL_1745-rack.jpg|thumb|Eventide DDL 1745 Digital Delay Line]]
Digital delay lines were first used to compensate for the [[speed of sound]] in air in 1973 to provide appropriate delay times for the distant speaker towers at the [[Summer Jam at Watkins Glen]] [[rock festival]] in New York, with 600,000 people in the audience. New York City–based company [[Eventide, Inc|Eventide Clock Works]] provided digital delay devices each capable of 200 milliseconds of delay. Four speaker towers were placed {{convert|200|ft|-1}} from the stage, their signal delayed 175 ms to compensate for the speed of sound between the main stage speakers and the delay towers. Six more speaker towers were placed 400 feet from the stage, requiring 350 ms of delay, and a further six towers were placed 600 feet away from the stage, fed with 525 ms of delay. Each Eventide DDL 1745 module contained one hundred 1000-bit [[shift register]] chips and a bespoke [[digital-to-analog converter]], and cost $3,800 ({{Inflation|index=US|value=3800|start_year=1972|fmt=eq|cursign=$}}).<ref>{{cite web |author=Nalia Sanchez |date=July 29, 2016 |title=Remembering the Watkins Glen Festival |url=https://www.eventideaudio.com/blog/jgoldbach/remembering-watkins-glenn-festival |access-date=February 20, 2020 |website=Eventide Audio |mode=cs2}}</ref><ref>{{Cite web |title=DDL 1745 Digital Delay |url=https://www.eventideaudio.com/rackmount/ddl-1745/ |access-date=2023-07-22 |website=Eventide Audio |language=en-US}}</ref>

== See also ==
* [[Analog delay line]]
* [[Delay-line memory]]
* [[Interpolation]]

== References ==
<references group="" responsive="1"></references>
== Further reading ==

* {{Cite journal |last1=Valimaki |first1=Vesa |last2=Laakso |first2=Timo |last3=Karjalainen |first3=Matti |last4=Laine |first4=Unto |date=1996 |title=Splitting the Unit Delay |url=https://www.academia.edu/97506981 |journal=IEEE Signal Processing Magazine |volume=13 |issue=1 |pages=30–60 |doi=10.1109/79.482137 |bibcode=1996ISPM...13...30L |via=IEEE Explore}}
* {{Cite journal |last=Harris |first=Frederic J. |date=January 1978 |title=On the use of windows for harmonic analysis with the discrete Fourier transform |url=https://ieeexplore.ieee.org/document/1455106 |journal=Proceedings of the IEEE |volume=66 |issue=1 |pages=51–83 |doi=10.1109/PROC.1978.10837 |s2cid=426548 |via=IEEE Explore}}

== External links ==
* ''[https://ccrma.stanford.edu/~jos/filters/ Introduction to Digital Filters]'' by Julius Smith
* ''[https://ccrma.stanford.edu/~jos/sasp/ Spectral Audio Signal Processing]'' by Julius Smith
* ''[https://ccrma.stanford.edu/~jos/pasp/ Physical Audio Signal Processing]'' by Julius Smith
* ''[http://users.spa.aalto.fi/vpv/publications/vesan_vaitos/ Discrete-Time Modeling of Acoustic Tubes Using Fractional Delay Filters]'' by Valimaki Vesa


[[Category:Digital signal processing]]
[[Category:Audio effects]]