Accelerated near-field algorithm of sparse apertures by non-uniform fast Fourier transform

Siran Wang; Zhiping Li; Jianhua Wu; Zhengpeng Wang

doi:10.1364/OE.27.019102

1. Introduction

The near-field calculation of non-uniform sparse apertures is a general problem, whose scope of applications is wide. From aperture synthesis for plane-waves [1–3], directional modulation (DM) [4], focused sparse arrays to the CGH (computer-generated hologram) [5–7], and etc. When the unit number in non-uniform sparse apertures is large, such as the Square Kilometer Array (SKA), the accelerated calculation becomes essential. Different from the angular spectrum method with the NUFFT (AS-NUFFT) [8] and the convolution-based Fresnel-NUFFT(FR-NUFFT) [9], the method in this paper utilizing the Rayleigh-Sommerfeld convolution kernel, can be summarized as the RS-NUFFT.

Actually, the near-field calculation of apertures is the Rayleigh-Sommerfeld diffraction integral [10]. For uniform apertures, Rayleigh-Sommerfeld convolution method is exactly the same as the Rayleigh-Sommerfeld diffraction integral. Theoretically, the Fourier Transform of the Rayleigh-Sommerfeld convolution kernel is equivalent to the transfer function in angular spectrum method [11]. However, the strict condition cannot be ignored where the size of source aperture should be infinite (the sampling interval of the angular spectrum should be infinitely fine). In real applications, computational truncation is inevitable for the discreate and finite apertures, consequently, the two methods are different, and for large size apertures, the calculation result of the angular spectrum method is closed to that of the Rayleigh-Sommerfeld diffraction integral. As for Fresnel convolution method, the Fresnel kernel is the approximation of the Rayleigh-Sommerfeld kernel in the far regions of the near field zone, which means the calculation result of the Fresnel convolution method is closed to that of the Rayleigh-Sommerfeld diffraction integral when the near-field distances are relatively far.

The Rayleigh-Sommerfeld convolution method cannot be accelerated by FFT for non-uniform sparse apertures, which drives us to update the Rayleigh-Sommerfeld convolution method by the NUFFT. NUFFT is formally presented by Dutt and Rokhlin [12] in 1991, the most striking point is that the NUFFT greatly reduces the computation complexity for approximating the nonuniform discrete Fourier transform (NU-DFT), which is widely used in medical imaging, radio astronomy, etc. The speed and precision of the NUFFT relies on the selection of the kernel functions and the design parameters for the kernel function which contains the over-resampling ratio and the kernel width. In [13], June-Yub Lee selected the Gaussian function and gave out the concrete steps for calculation. Both [14] and [15] compared and reviewed the Kaiser-Bessel (KB) and the Gaussian function, which are widely accepted as the preferred kernel functions nowadays.

In non-uniform sparse aperture cases, taking the Rayleigh-Sommerfeld diffraction integral as the calculation standard, the RS-NUFFT has calculation errors. The errors are sourced from the absence of the detailed frequency components and high frequency components in the spatial angular spectrum domain of apertures. Consequently, we develop two techniques (padding zeros for apertures and increasing sampling rate for the convolution kernel) for increasing the calculation accuracy of the RS-NUFFT, which is the main academic contribution of this paper.

The organization of the rest of this paper is as follows. In Section 2, the near-field propagation methods are overviewed, and the RS-NUFFT is derived. In Section 3, the details of the RS-NUFFT are discussed, and the techniques reducing the calculation errors of the RS-NUFFT are given out. In Section 4, two examples are presented to demonstrate the effectiveness and generality of the algorithm. Conclusion follows in Section 5.

2. Theory

In this section, the basic theory of the RS-NUFFT is presented, which contains two parts. In the first part, the near-field calculation methods for apertures are overviewed. The second part derives the RS-NUFFT.

2.1. Basic theory on the near-field aperture calculation

Assume a rectangular coordinate system and take the aperture source plane z = 0 and the destination plane z = d, where d is the distance between the two planes (seen in Fig. 1.) The electric field on the destination plane can be expressed as

E (x, y) |_{z = d} = \int [r \times [\hat{z} \times E (x^{'}, y^{'}) |_{z = 0}] \frac{(1 + j k r) e^{- j k r}}{r^{3}}] d x^{'} d y^{'}

where E (x^’, y^’) |_{z = 0} and E (x, y) |_{z = d} represent the electric fields on the source plane and on the destination plane, r is vector from the aperture point to the destination point, r is the module of the r, and k is the wavenumber in the free space.

Fig. 1 The geometry of the calculation model with two parallel planes orthogonal to the z-axis. The plane with scattered points located at z = 0 presents the non-uniform sparse aperture plane. The plane with grids located at z = d is the near-field destination plane. The lines connecting the points on the two planes present the contribution of all the elements to a point on the near-field destination plane.

Download Full Size | PDF

For relatively far regions of the near-field, the Eq. (1) can be approximated as the Fresnel diffraction

E (x, y) |_{z = d} = \int [r \times [\hat{z} \times E (x^{'}, y^{'}) |_{z = 0}] \frac{k}{d j} e^{- j k \frac{{(x - x^{'})}^{2} + {(y - y^{'})}^{2}}{2 d}}] d x^{'} d y^{'}

At the same time, according to the angular spectrum theory of plane waves [16–22], the electric field on an arbitrary plane can be represented by the integrals of the plane wave propagating in the whole directions. So, the electric field on the near-field destination surface can also be expressed by

E (x, y) |_{z = d} = \int [\int E (x^{'}, y^{'}) |_{z = 0} e^{j (k_{x} x^{'} + k_{y} y^{'})} d x^{'} d y^{'}] e^{- j k_{z} \cdot d} d k_{x} d k_{y}

where the part in square bracket is the angular spectrum of apertures, k_z is the down direction spectrum of the propagating plane wave.

2.2. The accelerated near-field algorithm for non-uniform sparse apertures

For uniform apertures, the Eqs. (1)–(3) can be accelerated by FFT. For non-uniform sparse apertures, the FFT needs to be replaced by the NUFFT. The flowchart of the algorithm is shown in Fig. 2.

Fig. 2 Schematic diagram of the accelerated near-field algorithm of non-uniform sparse apertures.

Download Full Size | PDF

From Fig. 2, the NUFFT is the key step to transform the unequal spatial fields of non-uniform sparse apertures into the equal angular spectrums accurately and efficiently. After getting the uniform angular spectrum of non-uniform sparse apertures, the next steps of the algorithm follow the classic propagation approaches.

As discussed above, for uniform apertures, the integral of Eq. (1) can be accelerated by FFT

E (x, y) |_{z = d} = IFFT 2 (FFT 2 (E_{e q u a l} (x^{'}, y^{'}) |_{z = 0}) \times FFT 2 (\frac{d (1 + j k r)}{r^{3}} e^{- j k r}))

where d(1 + jkr) exp(-jkr)/r³ is the system transfer function in the spatial domain, which can also be called Rayleigh-Sommerfeld convolution kernel. E_equal (x^’, y^’) |_{z =} ₀ is the electric field of uniform apertures. For non-uniform sparse apertures, the (4) can be modified as

E (x, y) |_{z = d} = IFFT 2 (NUFFT 2 (E_{s p a r s e} (x^{'}, y^{'}) |_{z = 0}) \times FFT 2 (\frac{d (1 + j k r)}{r^{3}} e^{- j k r}))

where E_sparse (x^’, y^’) |_{z = 0} distinguishing from E_equal (x^’, y^’) |_{z = 0} presents the electric field of non-uniform sparse apertures, and the Eq. (5) can be called RS-NUFFT.

Similar to the Eq. (1), the Eq. (2) can also be accelerated by FFT or NUFFT for uniform or non-uniform case

E (x, y) |_{z = d} = IFFT 2 (FFT 2 (E_{e q u a l} (x^{'}, y^{'}) |_{z = 0}) \times FFT 2 (\frac{k}{d j} e^{- j k (d + \frac{(x^{2} + y^{2})}{2 d})}))

E (x, y) |_{z = d} = IFFT 2 (NUFFT 2 (E_{e q u a l} (x^{'}, y^{'}) |_{z = 0}) \times FFT 2 (\frac{k}{d j} e^{- j k (d + \frac{(x^{2} + y^{2})}{2 d})}))

The k exp(-jk(d + (x² + y²)/2d)) /2πdj in the Eq. (6) and the Eq. (7) can be called Fresnel convolution kernel which is the approximate of the Rayleigh-Sommerfeld convolution kernel in the Eq. (4) and the Eq. (5) when the destination plane is relatively far from the aperture plane, and the Eq. (7) can be called as FR-NUFFT.

For uniform apertures, the Eq. (3) can be accelerated by

E (x, y) |_{z = d} = IFFT 2 (FFT 2 (E_{e q u a l} (x^{'}, y^{'}) |_{z = 0}) \cdot e^{- j k_{z} d})

In non-uniform sparse aperture case, the Eq. (8) can also be modified as

E (x, y) |_{z = d} = IFFT 2 (NUFFT 2 (E_{s p a r s e} (x^{'}, y^{'}) |_{z = 0}) \cdot e^{- j k_{z} d})

The Eq. (9) can be called AS-NUFFT. The exp (j k_z d) is the transfer function in the angular spectrum domain.

In Fig. 2, The NUFFT contains a convolution with the given kernel functions, an FFT operation on the over-resampled data, and a deconvolution. The selection of the kernel functions determines the accuracy and speed. Aside from the kernel functions, the over-resampling ratio and the kernel width influence not only the computation complexity, but also the accuracy of the reconstruction. Increasing the over-resampling ratio and kernel width will reduce the introduced truncation error by using a finite width window, and will meanwhile increase the computation complexity. Consequently, there should be a trade-off to select an appropriate over-resampling ratio and kernel width for specific applications.

The (9) can be called AS-NUFFT [8], and even can be extended for calculating the near fields on the tilted planes [25]. The exp(-jk_zd) is the transfer function in the angular spectrum domain. Theoretically, the Fourier Transform of RS convolution kernel is equivalent to the transfer function in the angular spectrum method. This equivalence can be traced back to 1967 [26], which was presented on the base of Weyl equation (the spherical wave is represented in the form of plane wave angular spectrum) [11]. However, the premise condition need to be payed enough attention to, where the size of source aperture should be infinite (the sampling interval of the angular spectrum should be infinitely fine). Consequently, if the aperture size is finite or even small, taking Eq. (1) as calculation standard, the calculation error of the Eq. (8) is much greater than that of Eq. (4). Apart from that, as the near-field distance increases, the aliasing error of the sampled transfer function in the Eq. (8) will become severe. To reduce the aliasing error, band-limited transfer function is developed [23]. However, the band-limited transfer function excludes some high frequency components, which reduces the calculation accuracy especially in the near regions of the aperture near-field. Through discussing the three methods calculating aperture near-field, we can clarify the applicable distance for the three methods in uniform aperture case. Predictably, the applicable distance of each method will be roughly the same in non-uniform case, seen in Fig. 3.

Fig. 3 The applicable distance of the three methods.

Download Full Size | PDF

3. Discussion

In this section, some issues related to the RS-NUFFT are discussed. For the sake of clarity, the overall discussion is divided into four subsections. In the first part, the computation complexity and the accuracy of the three propagation methods are compared with the Rayleigh-Sommerfeld diffraction integral in uniform aperture cases. In the second part, the kernel functions and the parameters in the NUFFT algorithms are reviewed. In the third part, the calculation accuracy of the RS-NUFFT for all the situations (aperture size, aperture sparsity and near-field distance) is analyzed, and the techniques (padding zeros for apertures, increasing sampling rate for the convolution kernel) are given out for improving the calculation accuracy of the RS-NUFFT. The computation complexity of the RS-NUFFT is listed in the final part. In order to simplify all the discussion, the simulated examples are all in one dimension.

3.1. The computation complexity and the accuracy of the convolution methods and the angular spectrum method

In uniform aperture cases, the computation complexity of the angular spectrum method is the lowest, according to the Eqs. (4), (6) and (8). Both the convolution methods need three FFT operations. Of course, the Eq. (6) can also be calculated as “Fourier form” [24], with the restriction where the intervals in apertures depend on the propagation distance and the wavelength. The “Fourier form” only needs one FFT operation.

For the uniform apertures, the computation complexity of the convolution methods is

O (3 N \log_{2} N)

The computation complexity of the angular spectrum method is

O (2 N \log_{2} N)

The computation complexity of the Eq. (6) in “Fourier form” is

O (N \log_{2} N)

where N is the unit number of the aperture plane and the destination plane (assuming the two planes are the same in size and sampling interval). If the calculation efficiency is the only motivator, the angular spectrum method is better than the convolution methods without any restriction.

The distribution and size of apertures can influence the calculation accuracy. In order to fully demonstrate the calculation accuracy of the three methods, we set two apertures in the size of 64λ and 2048λ, respectively, and both the apertures are set with uniform random amplitude and random phase in the range of (-π/2, π/2). The sampling interval of the apertures is 2λ, and the distances between the aperture plane and destination plane are set from 0.1S to 50S (S is the size of the aperture). The Errors of the Rayleigh-Sommerfeld convolution method, Fresnel convolution method and angular spectrum methods (with and without band-limited transfer function [24]) are listed in Fig. 4, where the Error is defined as:

E r r o r = \sqrt{\frac{\sum {(\tilde{E_{1}} - \tilde{E_{0}})}^{2}}{N \cdot {(\max (\tilde{E_{0}}))}^{2}}} \times 100

where

\tilde{E_{0}}

is the destination complex field calculated from the direct Rayleigh-Sommerfeld diffraction integral,

\tilde{E_{1}}

is the destination complex field calculated from other methods (i.e. the convolution-based Rayleigh-Sommerfeld method, the angular spectrum method), N is the sampling number in the destination field.

Fig. 4 The Errors of the three methods with different aperture sizes and near-field distance.

Download Full Size | PDF

From Fig. 4, in uniform aperture cases, the calculation accuracy of the Rayleigh-Sommerfeld convolution method is much better than that of the other two methods. For the Fresnel convolution method, the calculation accuracy increases greatly as the distance increases. Because the Fresnel kernel is the approximate of the Rayleigh-Sommerfeld kernel in the far region of the near-field zone. For angular spectrum method (without band-limited transfer function), the Error curves have a similar trend with that of the Fresnel convolution method in the first half, because high frequency components cannot not propagate too long distance, the absence of high frequency components due to under-sampling do not affect the characterization of the destination fields. In the second half, the Error curves go up, because the aliasing error of the sampled transfer function becomes severe. The angular spectrum method with band-limited transfer function can greatly diminish the aliasing error [23]. Comparing the Error curves between the top and the bottom in Fig. 3, the large aperture can reduce the Error for angular spectrum method, because the spatial angular spectrum of the large aperture contains more detailed frequency components, which can better characterize the destination fields.

3.2. Comparison of two kind kernel functions in NUFFT

In Fig. 2, the non-uniform sparse aperture field is transformed to the uniform angular spectrum by the NUFFT. The calculation accuracy and time of the NUFFT can further influence the performance of the presented accelerated algorithm in this paper. As mentioned above, the efficiency and accuracy of the NUFFT mainly depend on kernel functions.

Generally speaking, the Gaussian kernel function and Kaiser-Bessel kernel function are common choices. From the point of view of accuracy, Kaiser-Bessel has a better performance in similar situations, according to [14] and [15]. To ensure the logical integrity of this paper, in the following, we testify the correctness of the above conclusion.

We set a hundred numbers, randomly generated within the region of 0 to 2π, as the positions of non-uniform units and a hundred complex numbers as the corresponding excitations. The calculation results of the NUFFTs are compared with the direct integral method to show the accuracy. MES_dB (the logarithm of Mean Error Square) is defined as

M E S = 100 \sqrt{\frac{{| x_{r e f} - x_{N U F F T} |}^{2}}{x_{r e f}^{2}}}

M E S_{d B} = 20 \times \lg (M E S)

where x_ref is the referenced value calculated by direct integral method, x_NUFFT is calculated by NUFFT. In Fig. 5, compared with the Gaussian kernel, the K-B kernel has better accuracy in the settings where the parameters (the over-resampling ratio is 2, the kernel width is 24) are the same. The design parameters of the kernel functions are fully discussed in [14], the simple conclusion is that the accuracy of NUFFT will be higher when the kernel width and over-resample ratio increase. To get a better trade-off between the accuracy and the calculation efficiency, the over-resampling ratio is set to 2 and the kernel width is set to 24, which is recommended in [13].

Fig. 5 The accuracy of the NUFFTs with different kernel functions. The x-axis is the linear wavenumber.

Download Full Size | PDF

We set different numbers of the non-uniform units to compare the calculation speed of the two kernel functions. The computation time is listed in Table 1. In this paper, all calculations are performed in MATLAB on a personal computer with an Intel i7-7700HQ CPU, 8-GB RAM, and windows operation system. The calculation speed of the K-B kernel is slower than that of the Gaussian kernel. The difference of the two kernels in calculation accuracy and speed is sourced from the special functions contained in the kernels, the details can be found in [15].

Table 1. Computation time of the two kernel functions.

View Table

From Fig. 5 and Fig. 6, the accuracy of the K-B kernel is about ten times higher than that of the Gaussian kernel, and the K-B kernel takes nearly sixty times longer than the Gaussian kernel in the same situation. Moreover, the accuracy of the two kernels is very high, so it is not necessary to teeter between the two kernels from the perspective of accuracy. According to the discussion, the Gaussian kernel offers a better accuracy-speed tradeoff. Consequently, the Gaussian kernel is selected for the presented accelerated algorithm.

Fig. 6 The Errors of the RS-NUFFT with different aperture distributions. (a) uniform aperture. (b) Gaussian aperture. (c) random aperture.

Download Full Size | PDF

3.3. Error source analysis and reduction for the RS-NUFFT

Based on the discussion above, we can conclude that the Rayleigh-Sommerfeld convolution method and the NUFFT with the Gaussian kernel function are a great combination for non-uniform sparse aperture near-field calculation.

In the following, take the Rayleigh-Sommerfeld diffraction integral (the Direct Calculation) as standard, the calculation accuracy of the RS-NUFFT is discussed. Similar to the discussion about uniform case above, the aperture sizes, the aperture distributions, the aperture sparsity and the near-field distances all influence the calculation accuracy of the RS-NUFFT.

Firstly, we discuss the influence of the aperture size, the aperture distribution and the near-field distance. The aperture sizes are set from 2³ λ to 2¹³ λ, and near-field distances are set from 0λ to 5 × 2¹³ λ. The aperture distributions are set to uniform distribution, Gaussian distribution (the amplitude on the edge of apertures is 0.183 with the uniform phase), and random distribution, respectively. The sampling intervals are non-uniform, and the average interval is λ. The Errors are listed in Fig. 6.

From Fig. 6, the calculation accuracy of the RS-NUFFT increases as the near-field distance increases, because high frequency components cannot not propagate too long distance, so the absence of high frequency components due to under-sampling do not affect the characterization of the destination field in long distance. The calculation accuracy of the RS-NUFFT increases as the aperture size increases, because the angular spectrums of large apertures contain more detailed frequency components, which can better characterize the destination fields. Actually, these two trends are similar to those in uniform case, however, in some regions, the Error increases as the aperture size increases, because when the size increases, the non-uniform positions increase. In Fig. 6, we can also see that different aperture distributions can influence the calculation accuracy of the RS-NUFFT, however, in real applications, we cannot choose the aperture distribution, and in most cases the near-field distances are fixed.

Secondly, the influence of the aperture sparsity on calculation accuracy of the RS-NUFFT is discussed. Without loss of generality, the aperture is set to random distribution, and the aperture sizes are set from 2³ λ to 2¹³ λ, and near-field distances are set from 0λ to 5 × 2¹³ λ. The average non-uniform sampling interval is set to λ, 2λ and 4λ. The Errors are listed in Fig. 7.

Fig. 7 The Errors of the RS-NUFFT with different average sampling rates in non-uniform sparse apertures. (a) The average sampling rate is λ. (b) The average sampling rate is 2λ.(c) The average sampling rate is 4λ.

Download Full Size | PDF

From Fig. 7, the calculation accuracy of the RS-NUFFT reduces as the average sampling interval increases, because increasing the average sampling interval will lose some high frequency components which still play an essential role for characterizing the destination fields in the relative near region of the aperture near-field.

From the discussion above, we can conclude that the aperture size, the aperture distribution, the near-field distance and the aperture sparsity all influence the calculation accuracy of the RS-NUFFT, however, in most case, the aperture distribution, the sampling rate and the near-field are fixed. Consequently, if we want to increase the calculation accuracy of the RS-NUFFT, we should consider more about increasing the aperture size by padding zeros or the sampling rate of the convolution kernel to acquire more detailed or high frequency components.

Firstly, we discuss about increasing the aperture size through padding zeros. For the spatial angular spectrum of the aperture, increasing the aperture size means increasing the sampling rate in angular domain, which will acquire more detailed spatial frequency components, and can better characterize the destination near-field planes. However, padding zeros is not suitable for large apertures. On the one hand, large apertures have already acquired more detailed spatial frequency components compared with the small ones, on the other hand, padding zeros for large apertures will waste too much computation source. Consequently, padding zeros benefits more to the small apertures, in the following, we discuss the effectiveness of padding zeros for small apertures. The non-uniform sparse aperture is set to random distribution, the size is set to 30λ, the average sampling interval is λ, and the near-field distance is set to five times of the original aperture size. The distance is set for showing the effectiveness of padding zeros, because when the distance is short, the main cause of the calculation error is the absence of the high frequency components rather than that of detailed frequency components. In Fig. 8, the Error tendency with padding zeros is listed.

Fig. 8 The Errors of the RS-NUFFT with different zero-padding ratio.

Download Full Size | PDF

From Fig. 8, padding zeros can reduce the calculation error of the RS-NUFFT in relatively far distance in the near-field of apertures, because increasing the detailed frequency components of apertures can better characterize the destination field. However, padding too many zeros without considering the computation time is not a wise move, so we should keep a balance between calculation accuracy and time in real applications.

Secondly, we discuss about increasing the sampling rate of the convolution kernel for improving the calculation accuracy of the RS-NUFFT. In Fig. 9, the conditions are set the same as those in Fig. 7, except for increasing all the sampling rate of the convolution kernel to λ/2, and the Error are listed.

Fig. 9 The Error of the RS-NUFFT with the sampling rate λ/2 of the convolution kernel. (a) The average sampling rate is λ (maximum value 2.2091). (b) The average sampling rate is 2λ (maximum value 1.7204). (c) The average sampling rate is 4λ (maximum value 2.2937).

Download Full Size | PDF

Compared the Errors in Fig. 7, the Errors in Fig. 9 reduce greatly, which means high frequency components (less than k) still play an essential role in characterizing the aperture field, especially in relatively near regions of the aperture near-field. Furthermore, we increase the sampling rate of the convolution kernel to λ/4, the Errors are listed in Fig. 10.

Fig. 10 The Error of the RS-NUFFT with the sampling rate λ/4 of the convolution kernel. (a) The average sampling rate is λ (maximum value 0.5849). (b) The average sampling rate is 2λ (maximum value 0.74). (c) The average sampling rate is 4λ (maximum value 0.8569).

Download Full Size | PDF

From Fig. 10, increasing the sampling rate to λ/4 can further reduce the Error, however, high frequency components (more than k) cannot propagate too long distance, consequently, in most case, taking account for the computation time, we just need to increase the sampling rate of the convolution kernel to λ/2 for improving the calculation accuracy of the RS-NUFFT in relatively near regions of the aperture near-field.

Above all, we can conclude that the RS-NUFFT with the techniques (padding zeros for apertures, increasing sampling rate for the convolution kernel) can generally accelerate the near-field calculation of non-uniform sparse apertures in all situations. For far regions of the aperture near-field, if the aperture is small, we can increase the calculation accuracy through padding zeros. For near regions of the aperture near-field, if the aperture is sparse, we can reduce the calculation error through increasing the sampling rate of the convolution kernel. For other cases, the RS-NUFFT itself is accurate, and of course, if we still want to increase the calculation accuracy, padding zeros and increasing sampling rate of the convolution kernel still work, however, they may also waste too much computation source. Consequently, we should keep a balance between the calculation accuracy and time in real applications.

3.4. The computation complexity of the RS-NUFFT

The unit number of non-uniform aperture plane is N, the sampling number of uniform destination plane is M. The aperture sparsity ratio is defined as the ratio of mean distance between the adjacent units to the half of wavelength. The computation complexity of the RS-NUFFT can be expressed as:

O = O_{1} {\begin{cases} p W M + R (2 N - 1) \log_{2} [R (2 N - 1)] \\ + (2 N - 1) \end{cases}} + O_{2} [2 (2 N - 1) \log_{2} (2 N - 1)] + O_{3} (2 N - 1)

where R and W are the over-resampling ratio and the kernel width in the NUFFT, and p is the kernel calculation constant which is dependent on the kernel function [14]. The first part of Eq. (16) is the computation complexity of the NUFFT. (2N-1) satisfies the minimum requirement for the essence of the convolution of Eq. (3) and Eq. (4), the second part of Eq. (16) is the computation complexity of the two FFT operations. The last part presents the computation complexity of the product of the angular spectrum of the aperture and the Rayleigh-Sommerfeld convolution kernel.

The M is set from 100 to 10000, and the sparsity ratio is set as 2 and 64. Considering the reduction of the calculation error by the double zero padding, and the over resampling interpolation, the computation complexities are compared in Fig. 11.

Fig. 11 The computation complexity of the Direct Calculation, the RS-NUFFT, the RS-NUFFT with the double zero padding and the over resampling interval of 1/4 wavelengths when the sparsity ratio is set as 2 and 64, respectively.

Download Full Size | PDF

In Fig. 11, the Direct Calculation is more time-saving for small apertures compared with the RS-NUFFT due to its simple operations. However, as the size increases, the speed advantage of the RS-NUFFT is manifested, and the speed up ratio (the computation time ratio of the Direct Calculation to the RS-NUFFT) can reach up to two orders of magnitude. As the sparsity ratio increases, the speed up ratio is partly reduced, which indicates that the RS-NUFFT is more suitable for situations where the sparsity ratio is relatively small. Considering the two techniques to reduce the calculation error of the RS-NUFFT, the speed up ratio reduces slightly. Compared with increasing the sampling rate to λ/4, the computation complexity of double padding zeros is smaller.

4. Example

To demonstrate the effectiveness of the RS-NUFFT, two application examples, the focused near-field and plane wave near-field synthesis, are presented in the following.

4.1. The computation of the focused sparse apertures

Non-uniform sparse aperture technique has been utilized to depress the side lobe levels (SLL) in the focal plane when the average distance between the adjacent units is beyond half a wavelength [5]. The direct integral is time-consuming, especially for large apertures.

Two-dimensional squared sparse apertures with different sizes are simulated and compared in this paper. The units of the apertures are located at λ/2 on the uniform grid, but the number is only one-eighth of the full apertures. The distances between the aperture planes and the destination planes are 1.5 times aperture sizes. The excitation phase is set to conjugate, matching onto the focused point. The computation time of the sparse apertures is reduced drastically by the RS-NUFFT compared with the direct integral method, as shown in Fig. 12. The x-axis presents the size of the apertures, and some focused results are shown as the contour in the figures. The larger apertures achieve better speed up ratios.

Fig. 12 The computation time of the RS-NUFFT and the Direct Calculation, as aperture size increases. The focused near-field results are listed on the right. The first row, from the top to the bottom is in sizes of 20λ,40λ,60λ. The second row, from the top to the bottom is in sizes of 80λ, 100λ, 120λ. The third row, the top is in the size of 140λ.

Download Full Size | PDF

4.2. The calculation of the plane wave synthesis

In the introductory section of this paper, many non-uniform cases are listed in order to show potential application scenarios. As an example of the plane wave synthesis, we just follow the design guidelines in [3] and utilize the genetic algorithm (GA) to find the relatively good results. The GA requires calling the fitness functions containing the calculation of the radiation near field multiple times. The procedure applying the RS-NUFFT reduces a lot of time compared with the direct integral. The optimized units of the aperture are shown in Fig. 13, in which the size and color order of the marker denotes the amplitude and phase of the non-uniform units, respectively. The number of units is 400. The distance between the aperture plane and the destination plane is 1.5 times the length of a 30λ × 30λ aperture.

Fig. 13 The positions of aperture units. The amplitude of the units is related to the size of the square and the color is related to the phase (unit in degree).

Download Full Size | PDF

Figures 14(a) and 14(b) show the calculated complex field of plane wave synthesis. The calculation results on the diagonal line by the RS-NUFFT and the direct integral are compared in Fig. 14(c), whose time-consumptions are 0.30 s and 1.11s, respectively. The Error defined in Eq. (10), is reduced from 2.84% to 0.01% just with one zero padding on the four sides and the time cost is 0.51s. These results demonstrate the efficiency of the RS-NUFFT.

Fig. 14 (a) and (b) are the amplitude and phase of the destination near-field. The curves in (c) are the amplitude (up subplot) and phase (down subplot) calculated by the RS-NUFFT and the Direct Calculation along the diagonal.

Download Full Size | PDF

5. Conclusion

This paper presents an accelerated algorithm (RS-NUFFT) for calculating the near-field of non-uniform sparse apertures. The presented method using the Rayleigh-Sommerfeld kernel is different from the methods in [8] [9], which are angular spectrum (AS-NUFFT) and Fresnel convolution (FR-NUFFT). In order to increase the calculation accuracy of the RS-NUFFT, we develop two techniques (padding zeros for apertures and increasing sampling rate for the convolution kernel) for different situations. As mentioned in previous sections, the AS-NUFFT (band-limited transfer function) is accurate for large apertures and relatively far regions of the aperture near-field. FR-NUFFT is suitable for relatively far regions of the aperture near-field. The RS-NUFFT with the techniques is suitable for all the situations including small and large apertures, sparse and dense apertures, near and far regions of the aperture near-field. Compared with the direct Rayleigh-Sommerfeld diffraction integral, the RS-NUFFT reduces the computation time greatly, especially for large apertures.

Finally, the simulated examples containing the focused field, and the plane wave synthesis by non-uniform sparse apertures are presented to demonstrate the generality of the RS-NUFFT.

Funding

National Natural Science Foundation of China (NSFC) (61671033).

References

1. M. D’Urso, G. Prisco, and M. Cicolani, “Synthesis of plane wave generators via non-redundant sparse arrays,” IEEE Antennas Wirel. Propag. Lett. 8, 449–452 (2009). [CrossRef]

2. A. Buonanno, M. D’Urso, and G. Prisco, “Reducing complexity in indoor array testing,” IEEE Trans. Antenn. Propag. 58(8), 2781–2784 (2010). [CrossRef]

3. O. Bucci, M. Migliore, G. Panariello, and D. Pinchera, “Plane-wave generators: Design guidelines, achievable performances and effective synthesis,” IEEE Trans. Antenn. Propag. 61(4), 2005–2018 (2013). [CrossRef]

4. B. Zhang, W. Liu, and X. Gou, “Compressive sensing based sparse antenna array design for directional modulation,” IET Microw. Antennas Propag. 11(5), 634–641 (2017). [CrossRef]

5. G. Sun and Q. Zhu, “The Design of A Focused Sparse Microstrip Antenna Array,” in IEEE International Symposium on Antennas and Propagation (APSURSI) (IEEE, 2016), p. 515.

6. M. Hawes and W. Liu, “Compressive sensing-based approach to the design of linear robust sparse antenna arrays with physical size constraint,” IET Microw. Antennas Propag. 8(10), 736–746 (2014). [CrossRef]

7. N. Ullah, H. Zhao, T. Rahim, S. Rahman, and M. MuhammadKamal, “Reduced side lobe level of sparse linear antenna array by optimized spacing and excitation amplitude using particle swarm optimization,” in 7th IEEE International Symposium on Microwave, Antenna, Propagation, and EMC Technologies (MAPE) (IEEE, 2018), p. 96.

8. T. Shimobaba, T. Kakue, M. Oikawa, N. Okada, Y. Endo, R. Hirayama, and T. Ito, “Nonuniform sampled scalar diffraction calculation using nonuniform fast Fourier transform,” Opt. Lett. 38(23), 5130–5133 (2013). [CrossRef] [PubMed]

9. C. Chang, J. Wu, Y. Qi, C. Yuan, S. Nie, and J. Xia, “Simple calculation of a computer-generated hologram for lensless holographic 3D projection using a nonuniform sampled wavefront recording plane,” Appl. Opt. 55(28), 7988–7996 (2016). [CrossRef] [PubMed]

10. F. Shen and A. Wang, “Fast-Fourier-transform based numerical integration method for the Rayleigh-Sommerfeld diffraction formula,” Appl. Opt. 45(6), 1102–1110 (2006). [CrossRef] [PubMed]

11. M. Born and E. Wolf, Principles of Optics, 7th ed. (Cambridge University, 1996), p. 711.

12. A. Dutt and V. Rokhlin, “Fast fourier transforms for nonequispaced data,” Appl. Comput. Harmon. Anal. 2(1), 85–100 (1995). [CrossRef]

13. L. Greengard and J.-Y. Lee, “Accelerating the Nonuniform Fast Fourier Transform,” SIAM Rev. 46(3), 443–454 (2004). [CrossRef]

14. K. K. Chan and S. Tang, “Selection of convolution kernel in non-uniform fast Fourier transform for Fourier domain optical coherence tomography,” Opt. Express 19(27), 26891–26904 (2011). [CrossRef] [PubMed]

15. D. Xu, Y. Huang, and J. U. Kang, “GPU-accelerated non-uniform fast Fourier transform-based compressive sensing spectral domain optical coherence tomography,” Opt. Express 22(12), 14871–14884 (2014). [CrossRef] [PubMed]

16. H. G. Booker and P. C. Clemmow, “The Concept of an Angular Spectrum of Plane Waves and its Relation to that of Polar Diagram and Aperture Distribution,” J. Inst. Electr. Eng. 97(3), 11–17 (1950).

17. G. Borgiotti, “Fourier Transforms Method of Aperture Antennas,” Alta Freq. 32, 196–204 (1963).

18. C. A. Balanis, Antenna Theory: Analysis and Design, 2nd ed. (Wiley, 1997).

19. P. C. Clemmow, The Plane Wave Spectrum Representation of Electromagnetic Field (Pergamon, 1966).

20. E.V. Jull, Aperture Antenna and Diffraction Theory(Institution of Engineering and Technology, 1981).

21. T.B. Hansen and A.D. Yaghjian, Plane-Wave Theory of Time-Domain Fields: Near-Field Scanning Applications (Wiley-IEEE Press, 1999).

22. M. Ettorre, M. Casaletti, G. Valerio, R. Sauleau, L. Le Coq, S. Pavone, and M. Albani, “On the near-field shaping and focusing capability of a radial line slot array,” IEEE Trans. Antenn. Propag. 62(4), 1991–1999 (2014). [CrossRef]

23. K. Matsushima and T. Shimobaba, “Band-Limited Angular Spectrum Method for Numerical Simulation of Free-Space Propagation in Far and Near Fields,” Opt. Express 17(22), 19662–19673 (2009). [CrossRef] [PubMed]

24. T. Shimobaba, N. Masuda, and T. Ito, “Simple and fast calculation algorithm for computer-generated hologram with wavefront recording plane,” Opt. Lett. 34(20), 3133–3135 (2009). [CrossRef] [PubMed]

25. Y. Xiao, X. Tang, Y. Qin, H. Peng, W. Wang, and L. Zhong, “Nonuniform fast Fourier transform method for numerical diffraction simulation on tilted planes,” J. Opt. Soc. Am. A 33(10), 2027–2033 (2016). [CrossRef] [PubMed]

26. G. C. Sherman, “Application of the convolution theorem to Rayleigh’s integral formulas,” J. Opt. Soc. Am. 57(4), 546–547 (1967). [CrossRef] [PubMed]

NUFFT points	Gaussian kernel(s)	Kaiser-Bessel kernel(s)
100	0.0003	0.0181
200	0.0005	0.0295
500	0.0015	0.0702
1000	0.0026	0.1561

Accelerated near-field algorithm of sparse apertures by non-uniform fast Fourier transform

Abstract

1. Introduction

2. Theory

2.1. Basic theory on the near-field aperture calculation

2.2. The accelerated near-field algorithm for non-uniform sparse apertures

3. Discussion

3.1. The computation complexity and the accuracy of the convolution methods and the angular spectrum method

3.2. Comparison of two kind kernel functions in NUFFT

3.3. Error source analysis and reduction for the RS-NUFFT

3.4. The computation complexity of the RS-NUFFT

4. Example

4.1. The computation of the focused sparse apertures

4.2. The calculation of the plane wave synthesis

5. Conclusion

Funding

References

Cited By

Figures (14)

Tables (1)

Equations (16)

Optics Express