Frequency-Domain Characterization of Finite Sample Linear Systems with Uniform Window Inputs

A continuous linear time-invariant (LTI) system can be characterized by its frequency transfer function (FTF) or impulse response function (IRF) (e.g., ref. [1,2]). In the time domain, an LTI system’s output is the convolution of the input and the IRF. In the frequency domain, the output is the product of the input and the FTF. The corresponding expressions in the time domain and frequency domain are Fourier transform pairs. For theoretical convenience, one can determine a continuous system’s characteristics using the Dirac delta function with an infinitely narrow and infinitely high-power pulse. In practice, the test pulse must have a finite width and amplitude. The input and output of continuous time-invariant systems are sampled to produce the sequences of the input, $x\left[n\right]$, and the output, $y\left[n\right]$, of discrete-time LTI systems. The foundational theory of discrete-time LTI systems is based on an infinite number of samples (e.g., [2]). However, realistic systems allow only for a finite number of samples. The finite-sample LTI (FS-LTI) system complicates the applications of LTI theories, especially in the frequency domain.

The purpose of this study is to bridge the gap between time-domain and frequency-domain operations for FS-LTI systems. A system with finite samples cannot be a time-invariant system. To preserve the characteristics of an LTI system, explicit or implicit assumptions about the remaining data samples need to be made. Typical assumptions are that the unavailable samples have zero values or are periodic repetitions of the available samples. For an FS-LTI system, one can use a unit sample function, $\delta \left[n\right],$ to determine the finite sample IRF, $h\left[n\right]$, up to the length of the number of available samples, M. The IRF of an FS-LTI system can only match the IRF of the corresponding infinite-sample LTI (IS-LTI) system for M samples.

For a continuous LTI system, we can obtain the FTF via the ratio of the Fourier transform of the output and input functions. For an FS-LTI discrete system with M samples, we can also obtain $H_r\left[k\right]=Y\left[k\right]/X\left[k\right]$, where $X\left[k\right]$ and $Y\left[k\right]$, with a length of $N\ge M$, are the discrete Fourier transforms (DFTs) of $x\left[n\right]$ and $y\left[n\right]$, respectively. In this study, n and k are used for time and frequency domain indices, respectively. When data samples are unavailable, zero values will be assumed to ensure proper operations or theoretical completeness. $H_r\left[k\right]$ and $h\left[n\right]$ are interchangeable in describing the FS-LTI system for finite impulse response (FIR) systems if M is sufficiently long. In general, however, the inverse DFT (IDFT) of $H_r\left[k\right]$ does not directly recover any sample of $h\left[n\right]$ for infinite impulse response (IIR) systems because the output is the sum of circular convolution in frequency-domain and time-domain exchanges. When $x\left[n\right]$ is a finite uniform window sequence, we use $H_0\left[k\right]$ to denote $Y\left[k\right]/X\left[k\right]$. In such a case, $H_0\left[k\right]$ may contain singularities. A fundamental question is whether $H_0\left[k\right]$ or $H_r\left[k\right]$ contains sufficient information to derive $h\left[n\right]$ for an FS-LTI system.

In this study, we are primarily concerned with deriving $h\left[n\right]$ from $H_0\left[k\right]$ for FS-LTI systems. When the input testing function is a uniform window function having a width of L and the output is or is assumed to be zeros after M points, the LTI system is marginally stable since the zeros of the z-domain transfer function are all on the unit circle. The IRF of such marginally stable systems is a periodic function after $M-L+1$ points [3]. For a marginally stable system, as shown in [3], the non-redundant or effective part of $h\left[n\right]$ can indeed be obtained from $H_0\left[k\right]$ if the zero-padded length, N, of $x\left[n\right]$ and $y\left[n\right]$ is chosen to be a sufficiently large multiple of L. The current work extends that of [3]. We show here that N does not need to be a multiple of L in order to use $H_0\left[k\right]$ to describe the FS-LTI system. As the marginally stable system is an artifact due to the zero-value assumption for unavailable samples, the methods discussed here apply to all FS-LTI systems, whether the corresponding IS-LTI systems are FIR or IIR, stable or unstable. Although our focus is on the theoretical equivalence of $H_0\left[k\right]$ and $h\left[n\right]$ for FS-LTI systems, our approach to finding the IRF offers the advantages of frequency domain filtering in practical signal processing.

The literature on FS-LTI systems is largely concerned with error estimations in system identifications. The textbook [4] lays the background for system identifications and reviews the theories and techniques up to the publication time. Reference [5] discusses the quality of system identification for general linear models using the standard quadratic prediction error criterion and bounds the difference between the expected value of the identification criterion evaluated at the estimated and optimal parameters. An extension to Shannon’s sampling theorem for the finite-time case is found in [6], which demonstrates that a higher sample rate is necessary to recover finite-duration signals. When an observed signal is modeled as the output over a finite interval of an LTI operator having a short-duration impulse response, ref. [7] shows that complex exponentials over the observation interval are pseudomodes of LTI operators, corresponding to pseudo-eigenvalues that are samples from the operator’s frequency response. Finite-time bounds on the identification error of least-squares estimates for a broad range of heavy-tailed noise distributions and transition matrices are provided in [8]. A data-driven method for order selection and the achievement of the precise estimation of system parameters using an approach closely related to the Ho–Kalman subspace algorithm is presented in [9]. Assuming mild marginal mean square stability, ref. [10] identifies how much data are needed to estimate an unknown bilinear system up to a desired accuracy with high probability. The limits and optimization algorithms in finite-time linear system identifications for the so-called fixed budget and fixed confidence settings are discussed in [11]. The end-to-end sample complexity for evaluating the robust linear observer’s performance under coprime factor uncertainty is examined by [12]. A review of the non-asymptotic theory on system identification can be found in the tutorial [13]. Most recently, a distribution-free, finite-sample data perturbation method for finite-sample identification of linear regression models with residual-permuted sums was discussed in [14].

In the following, we outline the background and introduce additional notations in Section 2. We show how to find $h\left[n\right]$ from $H_0\left[k\right]$ for the cases of L and N being coprime in Section 3 and for general cases in Section 4. In demonstrating the equivalence of $h\left[n\right]$ and $H_0\left[k\right]$, we introduce two DFT pairs. Applications are discussed in Section 5. The main points are summarized in Section 6.

The input to the causal LTI system of interest is a uniform window function, $x_L\left[n\right]=\left\{\begin{array}{c}1,0\le n\le L-1\\ 0,otherwise\end{array}\right.$, and the output $y\left[n\right]\left\{\begin{array}{c}\ne 0,n=M-1\\ =0,n\ge M\end{array}\right.$ has a finite non-zero length of M. N is the length of zero-padded samples of the input and output. M can be regarded as the total number of samples of an FS-LTI system. For brevity, we use FS-LTI($L,M,N$) to denote an FS-LTI system with parameters $L,M,N$ so defined. For such a system, the impulse response function (IRF), $h\left[n\right]$, can be expressed as [3] where $u\left[n\right]$ is the unit step function. Let $\mathbb{I}$ be the set for all the integers, $\delta [n,L]\equiv \left\{\begin{array}{c}1,iff{\displaystyle \frac{n}{L}}\in \mathbb{I}\hfill \\ 0,otherwise\hfill \end{array}\right.$ be the comb function, and ${\delta }_{0+}[n,L]\equiv \delta [n,L]u\left[n\right]$ be the comb function for non-negative integers. The above expression can be alternatively written as where $n_m=n-m$. After $\max (M-L+1,0)$ points, the IRF of this simple marginally stable system is periodic with a period of L. The total independent number of points to completely describe $h\left[n\right]$ is $M_{ind}=\max (M+1,L).$

Let ${\pi }_N\equiv {\displaystyle \frac{\pi }{N}}$, ${W\equiv e}^{-j2{\pi }_N}$, $\mathbb{N}=\left\{0:N-1\right\}$, with $0:N-1$ denoting consecutive integers from 0 to $N-1$, inclusive. The discrete Fourier transform (DFT) of any $x\left[n\right]$ is Corresponding to the uniform window input function $x_L\left[n\right]$, $X_L\left[k\right]={\displaystyle \frac{1-W^{Lk}}{1-W^k}}$, $k\in \mathbb{N}$. The DFT of $y\left[n\right]$ is $Y\left[k\right]={\sum }_{n=0}^{M-1}y\left[n\right]W^{nk}$, $k\in \mathbb{N}$. The ratio of $Y\left[k\right]$ to $X_L\left[k\right]$ is Let $G_{LN}$ be the greatest common factor of L and N, and ${\mathbf{k}}_{\mathbf{0}}\equiv \{k_1,\dots (G_{LN}-1)k_1\}$ with $k_1\equiv {\displaystyle \frac{N}{G_{LN}}}$. We define which is the inverse of $X_L\left[k\right]$ with all its zeros set to zero. Further, we define$H_1\left[k\right]$ sets the poles of $H_0\left[k\right]$ to zeros but otherwise is the same as $H_0\left[k\right]$. The N-point inverse DFT (IDFT) of $H_1\left[k\right]$ is

All the parameters and variables $i,k,l,m,n$ for both lower and upper cases, with or without subscripts, are integers. We use k and n for frequency- and time-domain indexing, respectively. The % symbol in the subscript indicates a modulo operation, e.g., $N_{\%L}=mod(N,L)$. Similarly, $N_{\#L}=floor\left({\displaystyle \frac{N}{L}}\right)$ is used for lower integer operations. With these notations, we can write $N=N_{\#L}L+N_{\%L}$. Note that the floor operator rounds down for negative numbers, e.g., $floor(-0.5)=-1$.

We seek the IRF, $h\left[n\right]$, from $H_0\left[k\right]$ for FS-LTI($L,M,N$) systems.

Note that $L_i=(N_{\#L}-i_L)L$ is a multiple of L. The number of +1 and −1 pairs in $p_1\left[n\right]$ is $N_{\#L}-i_L$. As L and N are coprime, $Z\left[k\right]$ does not have a singularity. Figure 1 is an example for $L=4$, $N=21$, and $i_L=1$ showing the agreement between the direct IDFT of $P_1\left[k\right]$ and $p_1\left[n\right]$. The number of positive (or negative) ones is $N_{\#L}-i_L=4$.

When $L=1$ and ${1\le i}_L\le N-1$, we have When $N=L+1$ and $i_L=0$, we have $p_1\left[n\right]=\delta \left[n\right]-\delta [n-1]$. The lemma also holds if $N=L\ne 1$ and $i_L>0$. In this case, $p_1\left[n\right]=0$.

In Figure 2, we show $h_1\left[n\right],h_2\left[n\right],h_3\left[n\right]$, and $h\left[n\right]$ for $L=3$, $M=15$, $N=20$, $y\left[n\right]=h\left[n\right]\ast x_L\left[n\right]={\sum }_{i=0}^{n}h[n-i]x_L\left[i\right]$ for $n=0:14$, where $h\left[n\right]=$${1.1}^n$ for $n\ge 0$, and * is the convolution operator. In this example, $y\left[n\right]$ is truncated after 15 samples for an IS-LTI system with $h\left[n\right]=$${1.1}^n,n\ge 0$ and $L_{\alpha }=6$. In Figure 2, $h\left[n\right]$ is obtained from the time-domain method described in Section 2 and is seen to be the same as $h_3\left[n\right]$ for all $n=0:N-1$. $h_3\left[n\right]$ is the same as the IRF of the IS-LTI system for the first M points. Although the IRF of the IS-LTI may diverge as n tends to infinity, the IRF of the FS-LTI is always bounded for all n as long as $y\left[n\right]$ is bounded. Theorem 1 applies to complex input and output as well. Figure 3 shows an example of complex output with $L>M$. In this example, $L=10$, $M=4$, $y\left[n\right]=[1+j,1-j,j,1]$, $N=21,L_{\alpha }=20$. $h\left[n\right]$ is a periodic function with a period of 10. In both examples, $h_2\left[n\right]$ agrees with $h\left[n\right]$ in the first $L_{\alpha }$ points and $h_3\left[n\right]$ agrees with $h\left[n\right]$ for all the N points.

For Lemma 3 and Theorems 2 and 3, we define $\beta =floor\left({\displaystyle \frac{M-N_{\%L}}{L}}\right)+1$, ${\mathsf{\Delta }}_{\beta }=N_{\%L}+\beta L$, and $L_{\beta }=N-{\mathsf{\Delta }}_{\beta }$.

Theorem 1 states that the minimum N, $N_{min}$, required to produce $M_{ind}=\max (M+1,L)$ using $h_3[n$] is either $L+1$ for $L>M$ or the coprime of L that is larger than $M+1$. Theorem 2 shows that, for any $N\ge L+M+1$, we can determine the effective part of $h\left[n\right]$ completely. For any integer L, we can always find in $[M+1,M+L]$ an integer, $iL+1$, that is a coprime of L. Thus, $N_{min}$ lies in $[M+1,M+L]$ to recover all the $M_{ind}$ points in $h\left[n\right]$. Further, per the Bertrand–Chebyshev theorem [15], there is always a prime number between $n/2$ and $n-2$ for $n>6$. For M larger than 5, we can always find a prime number in $\left[\right(M+1)/2,M-1]$. Thus, if we can choose L freely, we only need to pad one zero to the M samples in the output and apply Theorem 1 to determine the independent part of $h\left[n\right]$.