Abstract
The linear canonical transform (LCT) describes the effect of quadratic phase systems on a wavefield and generalizes many optical transforms. In this paper, the computation method for the discrete LCT using the adaptive least-mean-square (LMS) algorithm is presented. The computation approaches of the block-based discrete LCT and the stream-based discrete LCT using the LMS algorithm are derived, and the implementation structures of these approaches by the adaptive filter system are considered. The proposed computation approaches have the inherent parallel structures which make them suitable for efficient VLSI implementations, and are robust to the propagation of possible errors in the computation process.
©2013 Optical Society of America
1. Introduction
The linear canonical transform (LCT) is a three-parameter linear integral transform that describes the effect of quadratic phase systems on a wavefield [1,2]. The LCT generalizes many optical transforms, such as the Fourier transform (FT), the fractional Fourier transform (FRFT) [1], the Fresnel transform [3,4], the scaling operation. These integral transforms are of great importance in electromagnetic, acoustic, and other wave propagation problems where they represent the solution of the wave equation under a variety of circumstances [5]. In optics, the LCT can describe a broad class of optical systems including thin lenses, sections of free space in the Fresnel approximation, section of quadratic graded-index media, and linear quadratic phase systems [1]. The LCT itself has found many applications in phase reconstruction, filter design, graded-index media analysis, signal synthesis, pattern recognition, time-frequency analysis, optimal filtering, holographic three-dimensional television and many others [5–8]. Understanding the LCT can help to gain more insight into its special cases and to carry the knowledge gained from one subject to others [3].
Discrete counterpart of a continuous transform is very important for computing the samples of the continuous transform. The well-known discrete Fourier transform (DFT) is commonly used to obtain the samples of the FT, and is thus widely applied in signal and image processing [9,10]. Therefore, after the continuous LCT has been introduced, the definition and the implementation of the discrete LCT have been derived [5,11,12]. These methods are used to approximate the continuous LCT in the same sense that the DFT approximates the continuous FT.
However, the above works to compute the discrete LCT are generally limited to implementing it on a data block and thus not to compute the discrete LCT of the stream data which updates with every new sample. Besides, due to the floating point arithmetic in software and hardware realizations, noise, for example come from roundoff errors, can propagate and accumulate over time.
In this paper, we present the discrete LCT computation by the adaptive method. The approaches for computing the block discrete LCT and the sliding discrete LCT via the LMS algorithm are derived, and the implementation structures of these approaches by the adaptive filter system are considered. Since the adaptive algorithm can automatically adjust for possible errors, the appearing error in the computation process of the discrete LCT is attenuated when it propagates over time. Furthermore, the proposed computation approaches for the block discrete LCT and the sliding discrete LCT have the inherent parallel structures and is suitable for efficient very large scale integration (VLSI) implementations, which implies that the processing speed is essentially independent of the size of the data block .
2. Linear canonical transform and LMS adaptive filter
2.1 Linear canonical transform
The LCT of a signal with parameters is defined as [4]
where is the parameter matrix and . Two successive LCTs with matrices and is another LCT with the matrix , and consequently the inverse LCT is given by the LCT with parameters . Note that when the LCT becomes a chirp multiplication. Therefore, we only consider the case of , and without loss of generality we assume in this paper. When , the LCT reduces to the FRFT. For further details about properties of the LCT, readers can refer to [1–7,11–14].The LCT of the ideal uniform sampled signal with sampling interval is [13]
Equation (2) shows that the LCT of the uniform sampled signal replicates with a period of .By sampling uniformly points in the replicated period in the LCT domain, the sampling interval in the LCT domain is . Then the discrete LCT of can been defined as [11,12]
where denotes the interval without generality. The conventional time-bandwidth product is the minimum number of samples to identify a signal whose energy are confined to and in the time domain and the frequency domain respectively. Likewise, the product is the minimum number of samples to identify a signal whose energy are confined to and in the time domain and the LCT domain respectively [5,12]. This minimum sample number is also referred as the number of freedom degrees.2.2 LMS adaptive filter
Adaptive filters are widely used in a variety of applications, including noise cancellation, system modeling, linear prediction filtering, and spectral estimation [15]. An adaptive filter has an adaptation process that automatically seeks an optimal impulse response by adjustable weights [16]. The model of the adaptive filter is shown in Fig. 1, where is the input signal vector, is the weight vector on the iteration of the algorithm, is the desired response which is also named reference signal, is the estimate output, and is the error signal.
The objective of the adaptation process is to minimize the average total error power [15,16]
where denotes statistical expectation. It is shown that the performance function (also called the cost function) is a convex quadratic function of weights.The steepest descent method uses gradients of the performance surface for seeking its minimum, where each change in the weight vector proportional to the negative of the gradient vector
where is a step parameter.The most popular algorithm in adaptive signal processing is the least-mean-square (LMS) algorithm [16]. This algorithm is an implementation of steepest descent using the estimated gradients , which takes the instantaneous gradients of . The algorithm is given by
The LMS adaptive algorithm has been applied to adaptive process modeling, adaptive noise canceling, adaptive line enhancer, etc [15–18].3. Block discrete LCT computation by adaptive filter
In [19], the relationship between the DFT and the least-mean-square (LMS) algorithm has been established, which is used to compute the DFT via the adaptive LMS algorithm. Due to the adaptive algorithm adjustment, this computation method for the DFT has a built-in error cancellation mechanism. Moreover, this technique has the inherent parallel structure and is very suitable for efficient VLSI implementation, which implies that the processing speed is independent of the size of the data block .
Discrete LCT computation is the basis for applications of the continuous LCT, and we propose the discrete LCT computation using the adaptive LMS algorithm. In this section, we present the block-based discrete LCT computation by an adaptive filter, which has the parallel structure that is suitable for efficient VLSI implementation.
In order to implement the computation of the discrete LCT by the adaptive LMS algorithm, the discrete signal to be transformed is served as the desired response of the adaptive filter system, and the input signal vector to the system at time index is constructed as
The choice of can be motivated as follows. The result of the continuous adaptive process is the weight vector , which is expected to be associated with the discrete LCT of . Note that the discrete LCT can be regarded as the expansion coefficient of transformed signal in term of the harmonic series with quadratic phase terms, which can be seen from the discrete transform kernel. This is the generalized results of the FT case that the DFT of a discrete signal is the expansion coefficient in terms of the discrete harmonic series to the discrete signal. Therefore, by choosing the vector in (7), the weighted sum of harmonic series with quadratic phase terms can well match the desired signal , which can transform into its discrete LCT by means of the adaptive LMS algorithm.For an adaptive filter, an adaptation process can automatically seek an optimal impulse response by adjusting the weight vector . In addition to the input signal vector , the desired response is supplied to the adaptive filter during the adaptation process. In many applications, considerable ingenuity on is required to obtain a better performance for an adaptive process. For example in the application of system modeling, the desired response is the output of the unknown system to be modeled; in the application of interference canceling, the desired response is the delayed version of the input signal; in the application of channel equalization, the desired response is the output of the decision device. Compared to these applications, the adaptive filter used here looks somewhat special that rather than the output the weight vector is the cared result that gives the “expected” discrete LCT transform with certain parameters by means of the LMS algorithm. It should be pointed that the proposed method is used to compute the discrete LCT with certain known parameters which gives the certain input vector to the adaptive filter.
The filter weight vector is adjusted with the LMS algorithm which is given in (6). Let the initial weight vector be set to zero. We obtain
andUsing the relationwe haveFollowing the same procedure, we can obtain the weight vectorFor the case that , it givesWe can clearly see that the element of comprise the values of the discrete LCT of the signal block , except for a scale factor of .Equation (12) is only applicable for with . Thus, we need to compute again
Note that for the input signal vector . However, the products for areSubstituting (15) into (14), we can obtainCombining the relationship between and that , we can obtainSimilarly, using the relationship and the product , we can obtain the weight vector at the time Along this line, we can obtainMoreover, we can obtain a completely general formula for with the initial condition . That isNote that the objective using the LMS adaptive algorithm here is to compute the discrete LCT. Except the first term, every term of the series (20) has a multiplicative factor of before the summation. Therefore, if the step size is chosen as then the series reduces to its first term only, regardless of the time index . In fact, with this particular choice of the step size that , the discrete LCT can be computed by means of the adaptive LMS algorithm which is shown as follows. At the time where is an integer the weight vector becomes
Although Eq. (21) is very similar to the discrete LCT of the input signal block at the first look, they are different indeed. That is to say we can’t use (21) to compute the block discrete LCT directly. From (21) the weights areTherefore, if we want to compute the block discrete LCT of the input signal block , we need to multiply a phase factor with from the time to . Thus, the computation of the block discrete LCT by using the LMS adaptive filtering system is shown in Fig. 2. From Fig. 2 we can see that compared to directly compute the discrete LCT, the discrete LCT computation by the adaptive filtering technique has the inherent parallel structure that makes it suitable for efficient VLSI implementation. Moreover, this method can automatically adjust for possible errors as it propagates over time, which is not shared by other method for the computation of the discrete LCT.4. Sliding discrete LCT computation by adaptive filter
We have shown the block discrete LCT computation by adaptive filter system. This method is suitable for implementing discrete LCT on a block by block basis. In some application scenarios, discrete time signals need to be transformed continuously in the LCT domain. At each instant, the most recent samples of the input signal are transformed in the LCT domain, which is referred as the sliding discrete LCT.
For the case when the signal is a stream of samples, the sliding discrete LCT vector is
When , from (20) we haveThe weights can be rewritten asFrom (23) we haveComparing (25) and (26) we can see that in order to complete the sliding discrete LCT computation of by weights , the weights at time index need to multiply the corresponding phase factor and the input samples need to multiply a time-variant phase factor , , which can be complemented by a time-variant phase network.Figure 3(a) shows the configuration of the computation of sliding discrete LCT by the adaptive method. Figure 3(b) shows the details of the time-variant phase network, where denotes times delay, .
5. Simulation results
In this Section, numerical examples of discrete LCT computation by the proposed adaptive LMS algorithm are demonstrated. The original continuous signal is a Gaussian function where . The discrete signal is sampled from the continuous signal with sampling interval , that is . The continuous signal and the discrete signal are shown in Fig. 4. Since , signals and are approximated as finite signals in the interval , and thus can be numerically simulated in a computer.
First, we consider the discrete LCT of with parameters . The discrete LCTs of computed by the definition (3) directly and by the proposed adaptive method are shown in Fig. 5. The amplitude and real part results of the discrete LCT are plotted in Fig. 5(a) and Fig. 5(b), respectively. Also, the continuous LCT of original continuous signal is plotted in Fig. 5. From Fig. 5, we can see that the discrete LCT of computed by the proposed adaptive method is exactly equal to the discrete LCT computed by the definition (3), which are well approximated as the continuous LCT of .
Then, we consider the discrete LCT of with parameters by , which is essentially the discrete FRFT of . The discrete LCTs of computed by the definition (3) directly and by the proposed adaptive method are shown in Fig. 6, where the amplitude and real part of the discrete LCT are plotted in Fig. 6(a) and Fig. 6(b), respectively. Also, the continuous LCT of original continuous signal is plotted in Fig. 6. For a Gaussian function , its FRFT has the analytic closed-form . Then according to the shift property of the FRFT, the FRFT of signal is . The position of the maximum amplitude value of continuous FRFT is theoretically. From Fig. 6 it is shown that the discrete LCT of computed by the proposed adaptive method is exactly equal to the discrete LCT computed by the definition (3). Besides, from Fig. 6(a), the position of the maximum amplitude value of the discrete LCT is 3.566, which implies the well approximation to the continuous LCT.
6. Conclusion
In this paper, the computation of the block discrete LCT and the sliding discrete LCT by LMS adaptive filter system has been proposed. We have shown that with a particular choice of the step to be , the discrete LCT of a signal block with length can be computed by means of the adaptive LMS algorithm. Besides, the sliding discrete LCT computation by the adaptive system has been shown. The proposed computation methods are robust to the errors, and the inherent parallel structure makes the proposed computation techniques very suitable for efficient VLSI implementation.
Acknowledgments
This work was supported in part by the National Science Foundation of China for Distinguished Young Scholars under Grant No. 60625104 and by the National Natural Science Foundation of China under Grant No. 61201354, and by the Basic Science Foundation of Beijing Institute of Technology under Grant 20120542005.
References and links
1. H. M. Ozaktas, Z. Zalevsky, and M. A. Kutay, The Fractional Fourier Transform with Applications in Optics and Signal Processing (Wiley, 2001).
2. J. J. Healy and J. T. Sheridan, “Cases where the linear canonical transform of a signal has compact support or is band-limited,” Opt. Lett. 33(3), 228–230 (2008). [CrossRef] [PubMed]
3. A. Stern, “Why is the linear canonical transform so little known?” Proc. AIP860,225–234 (2006). [CrossRef]
4. D. F. V. James and G. S. Agarwal, “The generalized Fresnel transform and its applications to optics,” Opt. Commun. 126(4-6), 207–212 (1996). [CrossRef]
5. A. Koc, H. M. Ozaktas, C. Candan, and M. A. Kutay, “Digital computation of linear canonical transforms,” IEEE Trans. Signal Process. 56(6), 2383–2394 (2008). [CrossRef]
6. S. C. Pei and J. J. Ding, “Eigenfunctions of linear canonical transform,” IEEE Trans. Signal Process. 50(1), 11–26 (2002). [CrossRef]
7. B. Deng, R. Tao, and Y. Wang, “Convolution theorems for the linear canonical transform and their applications,” Science in China Ser. F 49(5), 592–603 (2006). [CrossRef]
8. L. Onural, A. Gotchev, H. M. Ozaktas, and E. Stoykova, “A survey of signal processing problems and tools in holographic three-dimensional television,” IEEE Trans. Circ. Syst. Video Tech. 17(11), 1631–1646 (2007). [CrossRef]
9. A. V. Oppenheim and R. W. Schafer, Digital Signal Processing (Prentice-Hall, 1975)
10. L. R. Rabiner and B. Gold, Theory and Application of Digital Signal Processing (Prentice-Hall, 1975).
11. S. C. Pei and J. J. Ding, “Closed-form discrete fractional and affine Fourier transforms,” IEEE Trans. Signal Process. 48(5), 1338–1353 (2000). [CrossRef]
12. F. S. Oktem and H. M. Ozaktas, “Exact relation between continuous and discrete linear canonical transforms,” IEEE Signal Process. Lett. 16(8), 727–730 (2009). [CrossRef]
13. J. Zhao, R. Tao, and Y. Wang, “Sampling rate conversion for linear canonical transform,” Signal Process. 88(11), 2825–2832 (2008). [CrossRef]
14. J. Zhao, R. Tao, Y. L. Li, and Y. Wang, “Uncertainty principles for linear canonical transform,” IEEE Trans. Signal Process. 57(7), 2856–2858 (2009). [CrossRef]
15. B. Widrow, J. R. Glover Jr, J. M. McCool, J. Kaunitz, C. S. Williams, R. H. Hearn, J. R. Zeidler, E. Dong Jr, and R. C. Goodlin, “Adaptive noise canceling: Principles and applications,” Proc. IEEE 63(12), 1692–1716 (1975). [CrossRef]
16. B. Widrow, J. M. McCool, M. G. Larimore, and C. R. Johnson Jr., “Stationary and nonstationary learning characteristics of the LMS adaptive filter,” Proc. IEEE 64(8), 1151–1162 (1976). [CrossRef]
17. B. Widrow and S. D. Stearns, Adaptive Signal Processing (Prentice-Hall, 1985).
18. B. Widrow, J. M. McCool, and M. Ball, “The complex LMS algorithm,” Proc. IEEE 63(4), 719–720 (1975). [CrossRef]
19. B. Widrow, P. Baudrenghien, M. Vetterli, and P. F. Titchener, “Fundamental relations between the LMS algorithm and the DFT,” IEEE Trans. Circ. Syst. 34(7), 814–820 (1987). [CrossRef]