Zero, First, Second … nth-order Hold

The rectangular function is defined as: $$\mathrm{rect}(t) = \begin{cases} 0 & \mbox{if } |t| > \frac{1}{2} \\ \frac{1}{2} & \mbox{if } |t| = \frac{1}{2} \\ 1 & \mbox{if } |t| < \frac{1}{2}. \\ \end{cases}$$

The triangular function is defined as: $$\operatorname{tri}(t) = \begin{cases} 1 - |t|, & |t| < 1 \\ 0, & \mbox{otherwise} \end{cases}$$ It is the convolution of two identical unit rectangular functions: $$\operatorname{tri}(t) = \operatorname{rect}(t) * \operatorname{rect}(t) \quad = \int_{-\infty}^\infty \mathrm{rect}(\tau) \cdot \mathrm{rect}(t-\tau)\ d\tau$$ Zero-order hold and First-order hold use these functions. In fact, it has: $$x_{\mathrm{ZOH}}(t)\,= \sum_{n=-\infty}^{\infty} x(n)\, \mathrm{rect} \left(t-n\right) \$$ for Zero-order hold, and $$x_{\mathrm{FOH}}(t)\,= \sum_{n=-\infty}^{\infty} x(n)\, \mathrm{tri} \left(t-n\right) \$$ for First-order hold. Since $\operatorname{tri}(t) = \operatorname{rect}(t) * \operatorname{rect}(t)$, I would like to know if this is just a coincidence or if, for the Second-order hold the impulse response is $$\operatorname{tri}(t)*\operatorname{tri}(t)=\left(\operatorname{rect}(t) * \operatorname{rect}(t)\right)*\left(\operatorname{rect}(t) * \operatorname{rect}(t)\right).$$ Is it true also for a general $k$-th order hold? Namely, put $$x_{\mathrm{K-TH}}(t)\,= \sum_{n=-\infty}^{\infty} x(n)\, \mathrm{g}_k \left(t-n\right) \$$ where $\mathrm{g}_k \left(t-n\right)$ is the impulse response of the $k$-th order hold, I would like to know if its impulse response is $$\mathrm{g}_k \left(t-n\right)=\left(\operatorname{rect}(t) * \operatorname{rect}(t)\right)* \dots * \left(\operatorname{rect}(t) * \operatorname{rect}(t)\right),$$ k times.

• i haven't seen a reference for a $k$-th order hold for $k>1$. i would have expected it to be the $\operatorname{rect}(t)$ function convolved with itself $k-1$ times. but i don't know what the definition is. – robert bristow-johnson Mar 25 '16 at 3:14
• @robertbristow-johnson: In analogy with a zero-order-hold (zero order polynomial interpolation, i.e. piecewise constant), and a first-order-hold (first-order polynomial interpolation, i.e. piecewise linear), an n-th order hold is a piecewise interpolation by an n-th order polynomial. It is mentioned here (p. 6). – Matt L. Mar 25 '16 at 10:00
• These and what @robertbristow-johnson describes in his answer below are called B-splines. – Olli Niemitalo Apr 10 '17 at 15:32
• can anyone show with an image matrix with factor 2 , please ? And , I am quite unclear about factor here . – user30462 Aug 24 '17 at 18:01

This is not the case. First of all, a second-order hold would use three sample points to compute an interpolation polynomial, but your suggested impulse response $\text{tri}(t)\star\text{tri}(t)$ is non-zero in an interval of size $4$ (assuming a sample interval of $T=1$, as you do in your question). However, the impulse response corresponding to a second-order hold must have a support of length $3$.

Now you could suggest that an $n^{th}$-order hold could have an impulse response which is the convolution of $n$ rectangular functions. In this case you would get the correct support size, but of course that's not sufficient.

An $n^{th}$-order hold computes a piece-wise interpolation using $n+1$ consecutive data points. This is in analogy with a zero-order hold using a single data point, and a first-order hold, which uses two data points. This definition is commonly used in the literature (see e.g. here and here).

It's straightforward to show that the second-order polynomial that interpolates three data points $y[-1]$, $y[0]$, and $y[1]$ is given by

$$P(t)=y[-1]\frac{t(t-1)}{2}+y[0](1-t^2)+y[1]\frac{t(t+1)}{2}\tag{1}$$

In order to find the impulse response achieving the interpolation given by $(1)$, we have to equate $(1)$ with the expression

$$y[-1]h(t+1)+y[0]h(t)+y[1]h(t-1)\tag{2}$$

If we choose the support of the impulse response $h(t)$ as the interval $[-1,2]$, which is equivalent to choosing the interpolation interval $[0,1]$, equating $(1)$ and $(2)$ results in the following impulse response of a second-order hold:

$$h(t)=\begin{cases}\frac12(t+1)(t+2),&\quad -1<t<0\\ 1-t^2,&\quad0\le t \le 1\\ \frac12 (t-1)(t-2),&\quad 1<t<2\\ 0,&\quad\text{otherwise}\end{cases}\tag{3}$$

The impulse response $(3)$ of a second-order hold looks like this:

I leave it up to you to show that this impulse response cannot be generated by convolving three rectangular functions with each other.

• Matt, can you provide a reference for your representation of what a 2nd-order hold is. i am 100% convinced that the plot is wrong. – robert bristow-johnson Mar 25 '16 at 2:57
• i corrected Eq. (1) (assuming the premise is correct). i'll leave it to you to reflect that into $h(t)$. – robert bristow-johnson Mar 25 '16 at 3:04
• @robertbristow-johnson: I undid your edit, because your "correction" was wrong. My equation gives $P(-1)=y[-1]$, as it should be the case; yours gives $P(-1)=-y[-1]$. I'll leave it to you to reflect why this is wrong. – Matt L. Mar 25 '16 at 6:38
• i stand corrected about the "correction". i lost count of the number of minus signs. (actually i was thinking that $(t-1)=2$ which is off by a minus sign. i did a little more looking around. no one seems to be particularly explicit. – robert bristow-johnson Mar 26 '16 at 7:24

so this is why i think an $n$-th order hold is a $\operatorname{rect}\left( \frac{t - T/2}{T} \right)$ convolved against itself $n$ times.

Wikipedia isn't the final reference of all things, but there is something that i sniffed from there. consider sampling and reconstruction (the Shannon Whittaker whatever formula). if the original bandlimited input is $x(t)$ and the samples are $x[n]\triangleq x(nT)$ that bandlimited input can be reconstructed from the samples with

$$x(t) = \sum\limits_{n=-\infty}^{\infty} x[n] \ \operatorname{sinc}\left( \frac{t - nT}{T} \right)$$

which is the output of an ideal brickwall filter with frequency response:

\begin{align} H(f) &= \operatorname{rect}(fT) \\ &= \begin{cases} 1 \quad |f| < \frac{1}{2T} \\ 0 \quad |f| > \frac{1}{2T} \\ \end{cases} \end{align}

when driven by the ideally sampled function

\begin{align} x_\text{s}(t) & = x(t) \cdot \sum\limits_{n=-\infty}^{\infty} \delta\left( \frac{t - nT}{T} \right) \\ & = x(t) \cdot T \sum\limits_{n=-\infty}^{\infty} \delta(t - nT) \\ & = T \sum\limits_{n=-\infty}^{\infty} x(t) \delta(t - nT) \\ & = T \sum\limits_{n=-\infty}^{\infty} x(nT) \delta(t - nT) \\ & = T \sum\limits_{n=-\infty}^{\infty} x[n] \delta(t - nT) \\ \end{align}

so when $x_\text{s}(t)$ goes into $H(f)$, what comes out is $x(t)$. the $T$ factor is needed so that the passband gain of the reconstruction filter, $H(f)$ is the dimensionless $1$ or 0 dB.

that means that the impulse response of this ideal brickwall filter is

\begin{align} h(t) & = \mathcal{F}^{-1} \left\{ H(f) \right\} \\ & = \frac1T \operatorname{sinc}\left( \frac{t}{T} \right) \\ \end{align}

the reconstructed $x(t)$ is

$$x(t) = h(t) \circledast x_\text{s}(t)$$

we clearly cannot realize that reconstruction filter because it is not causal. but with enough delay, we might be able to get closer and closer with a delayed causal $h(t)$.

now a practical DAC does not get particularly close, but because it simply outputs the sample value $x[n]$ for the sample period immediately after the sample, the output of the DAC looks like this

$$x_\text{DAC}(t) = \sum\limits_{n=-\infty}^{\infty} x[n] \ \operatorname{rect}\left( \frac{t - nT - \tfrac{T}2}{T} \right)$$

and it can be modeled as a filter with impulse response

$$h_\text{ZOH}(t) = \frac1T \operatorname{rect}\left( \frac{t-\tfrac{T}2}{T} \right)$$

driven by the same $x_\text{s}(t)$. so

$$x_\text{DAC}(t) = h_\text{ZOH}(t) \circledast x_\text{s}(t)$$

and the frequency response of the implied reconstruction filter is

\begin{align} H_\text{ZOH}(f) &= \mathcal{F}^{-1}\{ h_\text{ZOH}(t) \} \\ &= \frac{1 - e^{j 2 \pi f T}}{j 2 \pi f T} \\ &= e^{j \pi f T} \operatorname{sinc}(fT) \\ \end{align}

note the constant half-sample delay in this frequency response. that's where the Zero-order hold comes from.

so, while the ZOH has the same DC gain as the ideal brickwall reconstruction but not the same gain at other frequencies. in addition, the images in $x_\text{s}(t)$ aren't fully beaten down as would be with the brickwall, but they're beaten down a bit.

so why, in the POV of the time domain, is this? i think it's because of the discontinuities in $x_\text{DAC}(t)$. it's not as bad as the sum of dirac impulses in $x_\text{s}(t)$, but $x_\text{DAC}(t)$ has jump discontinuities.

how do you get rid of jump discontinuities? maybe turn them into discontinuities of the first derivative. and you do that by used if integration in the continuous time domain. so a first-order hold is one where the output of the DAC is run through an integrator with transfer function $\frac{1}{j 2 \pi f T}$ but we try to undo the effects of integrator with a differentiator done in the discrete-time domain. the output of that discrete-time differentiator is $x[n] - x[n-1]$ or Z-transform $X(z) - z^{-1}X(z) = X(z)(1 - z^{-1})$

the transfer function of that differentiator is $(1 - z^{-1})$ or, in the continuous Fourier domain, $(1 - (e^{j 2 \pi f T})^{-1}) = 1 - (e^{-j 2 \pi f T})$. this makes the transfer function of the first-order hold that of the continuous-time integrator, the discrete-time differentiator, and the ZOH of the DAC all multiplied together.

\begin{align} H_\text{FOH}(f) &= \mathcal{F}^{-1}\{ h_\text{FOH}(t) \} \\ &= \left( \frac{1 - e^{j 2 \pi f T}}{j 2 \pi f T} \right)^2 \\ &= e^{j 2 \pi f T} \operatorname{sinc}^2(fT) \\ \end{align}

the impulse response of this is

\begin{align} h_\text{FOH}(t) &= \mathcal{F}\{ H_\text{FOH}(f) \} \\ &= \left( \operatorname{rect}\left( \frac{t-\tfrac{T}{2}}{T}\right) \right) \circledast \left( \operatorname{rect}\left( \frac{t-\tfrac{T}{2}}{T}\right) \right) \\ &= \frac{1}{T} \operatorname{tri}\left( \frac{t-T}{T} \right) \\ \end{align}

now, continuing with this further, the second-order hold would have both continuous zeroth and first derivatives. it does this by integrating again in the continuous-time domain and trying to make up for it in the discrete-time domain with another differentiator. that tosses in another $e^{j \pi f T} \operatorname{sinc}(fT)$ factor which means convolving with another $\operatorname{rect}\left( \frac{t-\tfrac{T}{2}}{T}\right)$.

• This will finally converge to a Gaussian impulse response, and I can't make much intuitive sense of this. I strongly believe that an n-th order hold is - in complete analogy with ZOH and FOH - an n-th order polynomial interpolator. I share this view with several other authors: e.g., these ones and this one. I haven't seen your interpretation of an n-th order hold anywhere else. – Matt L. Mar 27 '16 at 18:39
• a very long Gaussian. the impulse response of an $n$-th order hold will be $n+1$ adjacent sections of piecewise $n$-th order polynomials concatenated in such a way that all of the derivatives, up to the $(n-1)$-th derivative will be continuous. and i think it's causal. BTW, i haven't finished the answer yet. sorta crapped out on it, but i plan to tie it all together eventually. and i'll fix a whole lotta grammar – robert bristow-johnson Mar 27 '16 at 19:11

Another question was marked as a duplicate of this. There it was asked also what polygonal hold is. It and polygon hold seem to be synonyms for linear interpolation, where "dots are connected" rather than the output looking like a saw as in predictive first-order hold. Connecting the samples with lines requires knowing the next sample in advance so that the line may be aimed at the correct direction. In the context of real-time control systems where the samples are not known in advance, it means that the output must be delayed by one sampling period for the lines to connect at the samples.

Polynomial hold (not polygonal hold) includes both zero-order hold and first-order hold.

As was noted in the comments the convolution of $$n$$ rectangular functions will converge to the Gaussian impulse response.

A cardinal B-spline can be defined as follows:

\begin{align*} B_0(t) &= \begin{cases} 1 &\text{if } t \in [0, 1) \\0 & \text{otherwise}\end{cases}\\ B_p(t) &= (B_{p-1} * B_{0})(t) \end{align*}

for $$p > 1$$. $$B_0(t)$$ is a polynomial of degree 0 (nearest neighbor interpolation, rectangular function). Note this rectangular function is a scaled variation of the one defined by the original poster. The triangular function $$B_1(t)$$ is a linear interpolation.

Then according to On the Asymptotic Convergence of B-Spline Wavelets to Gabor Functions, this results in

$$\lim_{m\to\infty} \sqrt{\frac{m+1}{12}}B_m\sqrt{\frac{m+1}{12}}x = \frac{1}{\sqrt{2\pi}}\exp\left(-\frac{x^2}{2}\right)$$

(which is the Gaussian function). The $$p$$-order B-spline has an explicit representation in the form

$$B_p(x) = \frac{1}{\Gamma(p)}\sum_{k=0}^\infty (-1)^k \binom{p}{k}(x - k)_+^{p-1}$$

where $$x_+ := \text{max}(0, x)$$ (cf. On some generalizations of B-splines). Both the support and the smoothness are tied to the integral order $$p$$. Some explicit computations can be found here: wikipedia.