Sparse arrays can usually achieve larger array apertures than uniform linear arrays (ULA) with the same number of physical antennas. However, the conventional direction-of-arrival (DOA) estimation algorithms for sparse arrays usually require the spatial smoothing operation to recover the matrix rank which inevitably involves heavy computational complexity and leads to a reduction in the degrees-of-freedom (DOFs). In this paper, a low-complex DOA estimation algorithm by exploiting the discrete Fourier transform (DFT) is proposed. Firstly, the spatial spectrum of the virtual array constructed from the sparse array is established by exploiting the DFT operation. The initial DOA estimation can obtain directly by searching the peaks in the DFT spectrum. However, since the number of array antennas is finite, there exists spectrum power leakage which will cause the performance degradation. To further improve the angle resolution, an iterative process is developed to suppress the spectrum power leakage. Thus, the proposed algorithm does not require the spatial smoothing operation and the computational complexity is reduced effectively. In addition, due to the extention of DOF with the application of the sparse arrays, the proposed algorithm can resolve the underdetermined DOA estimation problems. The superiority of the proposed algorithm is demonstrated by simulation results.

We are developing an Ultra-Low Field (ULF) Magnetic Resonance Imaging (MRI) system with a tuned high-Tc (HTS)-rf-SQUID for food inspection. We previously reported that a small hole in a piece of cucumber can be detected. The acquired image was based on filtered back-projection reconstruction using a polarizing permanent magnet. However the resolution of the image was insufficient for food inspection and took a long time to process. The purpose of this study is to improve image quality and shorten processing time. We constructed a specially designed cryostat, which consists of a liquid nitrogen tank for cooling an electromagnetic polarizing coil (135mT) at 77K and a room temperature bore. A Cu pickup coil was installed at the room temperature bore and detected an NMR signal from a sample. The signal was then transferred to an HTS SQUID via an input coil. Following a proper MRI sequence, spatial frequency data at 64×32 points in k-space were obtained. Then, a 2D-FFT (Fast Fourier Transformation) method was applied to reconstruct the 2D-MR images. As a result, we successfully obtained a clear water image of the characters “TUT”, which contains a narrowest width of 0.5mm. The imaging time was also shortened by a factor of 10 when compared to the previous system.

We introduce a Welch FFT segment size selection method for FFT-based wide band spectrum measurement in the context of smart spectrum access (SSA), in which statistical spectrum usage information of primary users (PUs), such as duty cycle (DC), will be exploited by secondary users (SUs). Energy detectors (EDs) based on Welch FFT can detect the presence of PU signals in a broadband environment efficiently, and DC can be estimated properly if a Welch FFT segment size is set suitably. There is a trade-off between detection performance and frequency resolution in terms of the Welch FFT segment size. The optimum segment size depends on signal-to-noise ratio (SNR) which makes practical and optimum segment size setting difficult. For this issue, we previously proposed a segment size selection method employing a relationship between noise floor (NF) estimation output and the segment size without SNR information. It can achieve accurate spectrum awareness at the expense of relatively high computational complexity since it employs exhaustive search to select a proper segment size. In this paper, we propose a segment size selection method that offers reasonable spectrum awareness performance with low computational complexity since limited search is used. Numerical evaluations show that the proposed method can match the spectrum awareness performance of the conventional method with 70% lower complexity or less.

Multivariate Public Key Cryptosystems (MPKCs) are often touted as future-proofing against Quantum Computers. In 2009, it was shown that hardware advances do not favor just “traditional” alternatives such as ECC and RSA, but also makes MPKCs faster and keeps them competitive at 80-bit security when properly implemented. These techniques became outdated due to emergence of new instruction sets and higher requirements on security. In this paper, we review how MPKC signatures changes from 2009 including new parameters (from a newer security level at 128-bit), crypto-safe implementations, and the impact of new AVX2 and AESNI instructions. We also present new techniques on evaluating multivariate polynomials, multiplications of large finite fields by additive Fast Fourier Transforms, and constant time linear solvers.

In this letter, a new rapid and accurate synchronization scheme based on PMF-FFT for high dynamic GPS receiver is proposed, with a fine Doppler frequency estimation inserted between the acquisition and tracking modules. Fine Doppler estimation is firstly achieved through a simple interpolation of the PMF-FFT outputs in terms of LSE criterion. Then a high dynamic tracking loop based on UKF is designed to verify the synchronization speed and accuracy. Numerical results show that the fine frequency estimation can closely approach the CRB, and the high dynamic receiver can obtain fine synchronization rapidly just through a very narrow bandwidth. The simplicity and low complexity give the proposed scheme a strong and practical-oriented ability, even for weak GPS signals.

This letter presents a novel memory-based architecture for radix-2 fast Walsh-Hadamard-Fourier transform (FWFT) based on the constant geometry FWFT algorithm. It is composed of a multi-function Processing Engine, a conflict-free memory addressing scheme and an efficient twiddle factor generator. The address for memory access and the control signals for stride permutation are formulated in detail and the methods can be applied to other memory-based FFT-like architectures.

In this paper, a hardware efficient design methodology for a configurable-point multiple-stream pipeline FFT processor is presented. We first compared the memory and arithmetic components of different pipeline FFT architectures, and obtained the conclusion that MDF architecture is more hardware efficient than MDC for the overall processor. Then, in order to reduce the computational complexity, a binary-tree representation was adopted to analyze the decomposition algorithm. Consequently, the coefficient multiplications are minimized among all the decomposition probabilities. In addition, an efficient output reorder circuit was designed for the multiple-stream architecture. An 128∼2048 point 4-stream FFT processor in LTE system was designed in SMIC 55nm technology for evaluation. It owns 1.09mm2 core area with 82.6mW power consumption at 122.88MHz clock frequency.

We create a practical method to set the segment size of the Welch FFT for wideband and long-term spectrum usage measurements in the context of hierarchical dynamic spectrum access (DSA). An energy detector (ED) based on the Welch FFT can be used to detect the presence or absence of primary user (PU) signal and to estimate the duty cycle (DC). In signal detection with the Welch FFT, segment size is an important design parameter since it determines both the detection performance and the frequency resolution. Between these two metrics, there is a trade-off relationship which can be controlled by adjusting the segment size. To cope with this trade-off relationship, we define an optimum and, more easy to analyze sub-optimum segment size design criterion. An analysis of the sub-optimum segment size criterion reveals that the resulting segment size depends on the signal-to-noise ratio (SNR) and the DC. Since in practice both SNR and DC are unknown, proper segment setting is difficult. To overcome this problem, we propose an adaptive segment size selection (ASSS) method that uses noise floor estimation outputs. The proposed method does not require any prior knowledge on the SNR or the DC. Simulation results confirm that the proposed ASSS method matches the performance achieved with the optimum design criterion.

Many selected mapping (SLM) schemes have been proposed to reduce the peak-to-average power ratio (PAPR) of orthogonal frequency division multiplexing (OFDM) signal sequences. In this paper, an efficient selection (ES) method of the OFDM signal sequence with minimum PAPR among many alternative OFDM signal sequences is proposed; it supports various SLM schemes. Utilizing the fact that OFDM signal components can be sequentially generated in many SLM schemes, the generation and PAPR observation of the OFDM signal sequence are processed concurrently. While the u-th alternative OFDM signal components are being generated, by applying the proposed ES method, the generation of that alternative OFDM signal components can be interrupted (or stopped) according to the selection criteria of the best OFDM signal sequence in the considered SLM scheme. Such interruption substantially reduces the average computational complexity of SLM schemes without degradation of PAPR reduction performance, which is confirmed by analytical and numerical results. Note that the proposed method is not an isolated SLM scheme but a subsidiary method which can be easily adopted in many SLM schemes in order to further reduce the computational complexity of considered SLM schemes.

This paper proposes Fast Fourier Transform (FFT) based orthogonal beam selection method at the user terminals (UTs) to reduce the number of nulls for the other users except an intended user by the Block Diagonalization (BD) algorithm in multiuser MIMO (MU-MIMO) sytems. The BD algorithm has been proposed in order to realize MU-MIMO broadcast transmission with a realistic signal processing burden. The BD algorithm cancels inter-user interference by creating the weights so that the channel matrixes for the other users are set to be zero matrixes. However, when the number of transmit antennas is equals to the total number of received antennas, the transmission rate by the BD algorithm is decreased. The proposed method realizes the performance improvement compared to the conventional BD algorithm without the burden on the UTs. It is verified via bit error rate (BER) evaluation that the proposed method is effective compared to the conventional BD algorithm and antenna selection method. Moreover, the effectiveness of proposed method is verified by the performance evaluation considering medium access control (MAC) layer in a comparison with the conventional BD algorithm which needs the channel state information (CSI) feedback. Because the proposed method can be easily applied to beamforming without the CSI feedback (implicit beamforming), it is shown that the propose method is effective from a point of view on the transmission efficiency in MU-MIMO system.

This paper describes a fast and effective algorithm for refining the parameter estimates of multicomponent third-order polynomial phase signals (PPSs). The efficiency of the proposed algorithm is accompanied by lower signal-to-noise ratio (SNR) threshold, and computational complexity. A two-step procedure is used to estimate the parameters of multicomponent third-order PPSs. In the first step, an initial estimate for the phase parameters can be obtained by using fast Fourier transformation (FFT), k-means algorithm and three time positions. In the second step, these initial estimates are refined by a simple moving average filter and singular value decomposition (SVD). The SNR threshold of the proposed algorithm is lower than those of the non-linear least square (NLS) method and the estimation refinement method even though it uses a simple moving average filter. In addition, the proposed method is characterized by significantly lower complexity than computationally intensive NLS methods. Simulations confirm the effectiveness of the proposed method.

Linear cryptanalysis proposed by Matsui is one of the most effective attacks on block ciphers. Some attempts to improve linear cryptanalysis have been made since Matsui introduced. We focus on how to optimize linear cryptanalysis with such techniques, and we apply the optimized linear cryptanalysis on FEAL-8X. First, we evaluate two existing implementation methods so as to optimize the computation time of linear cryptanalysis. Method 1 removes redundant round function computations and optimizes the other computation of linear cryptanalysis by transforming it into bitwise operations. Method 2 transforms the computation of linear cryptanalysis into a matrix multiplication and reduces the time complexity of the multiplication using the fast Fourier transform (FFT). We implement both methods optimized for modern microprocessors and compare their computation time to clarify the appropriate method for practical cryptanalysis. From the result, we show that the superior implementation depends on the number of given known plaintexts (KPs) and that of guessed key bits. Furthermore, we show that these results enable us to select the superior method to implement linear cryptanalysis without another comparative experiment. By using the superior method, we implement the multiple linear cryptanalysis (MLC) on FEAL-8X. Our implementation can recover the secret key of FEAL-8X with 210KPs in practical computation time with non-negligible probability, and it is the best attack on FEAL-8X in data complexity.

An integral attack is one of the most powerful attacks against block ciphers. We propose a new technique for the integral attack called the Fast Fourier Transform (FFT) key recovery. When N chosen plaintexts are required for the integral characteristic and the guessed key is k bits, a straightforward key recovery requires the time complexity of O(N2k). However, the FFT key recovery only requires the time complexity of O(N+k2k). As a previous result using FFT, at ICISC 2007, Collard etal proposed that FFT can reduce the time complexity of a linear attack. We show that FFT can also reduce the complexity of the integral attack. Moreover, the estimation of the complexity is very simple. We first show the complexity of the FFT key recovery against three structures, the Even-Mansour scheme, a key-alternating cipher, and the Feistel structure. As examples of these structures, we show integral attacks against Prøst, AES, PRESENT, and CLEFIA. As a result, an 8-round Prøst P128,K can be attacked with about an approximate time complexity of 279.6. For the key-alternating cipher, a 6-round AES and a 10-round PRESENT can be attacked with approximate time complexities of 251.7 and 297.4, respectively. For the Feistel structure, a 12-round CLEFIA can be attacked with approximate time complexities of 287.5.

Overlapped FFT based energy detection has been proposed as a signal detection scheme in dynamic spectrum access. The overlapped FFT scheme increases the number of FFT frames to reduce the variance of squared noise and improves the detection performance. As the FFT frames are overlapped, correlation values between the frames affect to the detection performance. This paper proposes the window functions which decrease the correlation values between adjacent FFT bins. Numerical results obtained through computer simulation show that novel window functions generated by upsampling a Hamming window improves the detection performance by 0.09. However, this window function suffers more from adjacent channel interference than a conventional window. Therefore, this paper also proposes a two step detection scheme to achieve higher detection performance and to avoid the influence of the adjacent channel signal. Numerical results also indicate that the proposed scheme improves the detection performance and reduces the effect from the adjacent channel signal.

We are developing a fast Fourier transform (FFT) processor using high-speed and low-power single-flux-quantum (SFQ) circuits. Our main concern is the development of an SFQ butterfly processing circuit, which is the core processing circuit in the FFT processor. In our previous study, we have confirmed the complete operation of an integer-type butterfly processing circuit using the AIST 2.5 kA/cm$^{2}$ Nb standard process at the frequency of 25 GHz. In this study, we have designed an integer-type butterfly processing circuit using the AIST 10,kA/cm$^{2}$,Nb advanced process and confirmed its high-speed operation at the maximum frequency of 50,GHz.

In this paper, we propose a time and memory efficient Ultra Wide Band Short Range Radar (UWB SRR) system for measuring relative target velocities of up to 150km/hr. First, for the proposed detector, we select the required design parameters for good performance. The parameters are the number of coherent integrations, non-coherent integrations, and FFT points. The conventional detector uses a Fast Fourier Transform (FFT) to extract the range and velocity of the target simultaneously. Therefore, it requires high computation effort, high FFT processing time, and a huge amount of memory. However, the proposed pulse radar detector first decides the target range and then computes the target velocity using FFT sequentially for the decided range index. According to our theoretical and simulation analyses, the FFT processing time and the memory requirement are reduced compared to those of the conventional method. Finally, we show that the detection performance of the proposed detector is superior to that of the conventional detector in a background of Additive White Gaussian Noise (AWGN).

We investigate the utilization of vector registers (VRs) on reducing memory references for single instruction multiple data fast Fourier transform calculation. We propose to group the butterfly computations in several consecutive stages to maximize utilization of the available VRs and take the advantage of the symmetries in twiddle factors. All the butterflies sharing identical twiddle factors are clustered and computed together to further improve performance. The relationship between the number of fused stages and the number of available VRs is then examined. Experimental results on different platforms show that the proposed method is effective.

We propose a new fine Doppler frequency estimator using two fast Fourier transform (FFT) samples for pulse Doppler radar that offers highly sensitive detection and a high resolution of velocity. The procedure of fine Doppler frequency estimation is completed through coarse frequency estimation (CFE) and fine frequency estimation (FFE) steps. During the CFE step, the integer part of the Doppler frequency is obtained by processing the FFT, after which, during the FFE step, the fractional part is estimated using the relationship between the FFT peak and its nearest resultant value. Our simulation results show that the proposed estimator has better accuracy than Candan's estimator in terms of bias. The root mean square error (RMSE) of the proposed estimator has more than 1.4 time better accuracy than Candan's estimator under a 1,024-point FFT and a signal-to-noise ratio (SNR) of 10 dB. In addition, when the FFT size is increased from 512 to 2,048, the RMSE characteristics of the proposed estimator improve by more than two-fold.

High-performance FFT processor is indispensable for real-time OFDM communication systems. This paper presents a CORDIC based design of variable-length FFT processor which can perform various FFT lengths of 64/128/256/512/1024/2048/4096/8192-point. The proposed FFT processor employs memory based architecture in which mixed radix 4/2 algorithm, pipelined CORDIC, and conflict-free parallel memory access scheme are exploited. Besides, the CORDIC rotation angles are generated internally based on the transform of butterfly counter, which eliminates the need of ROM making it memory-efficient. The proposed architecture has a lower hardware complexity because it is ROM-free and with no dedicated complex multiplier. We implemented the proposed FFT processor and verified it on FPGA development platform. Additionally, the processor is also synthesized in 0.18 µm technology, the core area of the processor is 3.47 mm2 and the maximum operating frequency can be up to 500 MHz. The proposed FFT processor is better trade off performance and hardware overhead, and it can meet the speed requirement of most modern OFDM system, such as IEEE 802.11n, WiMax, 3GPP-LTE and DVB-T/H.

In this paper, to reduce the memory size requirements of IFFT for OFDM-based applications, we propose a new IFFT design technique based on a combined integer mapping of three IFFT input signals: modulated data, pilot and null signals. The proposed method focuses on reducing the size of memory cells in the first two stages of the single-path delay feedback (SDF) IFFT architectures since the first two stages require 75% of the total memory cells. By simulations of 2048-point IFFT design for cognitive radio systems, it is shown that the proposed IFFT design method achieves more than 13% reduction in gate count and 11% reduction in power consumption compared with conventional IFFT design.