توصيفگر ها :
تبديل فوريه سريع تنك , تبديل فوريه سريع , آرايه برنامه پذير اثر ميداني , پياده سازي سخت افزاري , ابر داده , SFFT , FFT , FPGA , Hardware Implementation , Big Data
چكيده فارسي :
يكي از مسائل مهم در زمينه پردازش داده‌هاي ديجيتال، محاسبه تبديل فوريه داده‌هاي با ابعاد بزرگ است. پياده سازي سخت افزاري تبديل فوريه سريع براي كاربردهاي گوناگون به ازاي مقادير N كوچكتر از 217 رايج است تا از مصرف بالاي منابع تراشه جلوگيري گردد. در برخي از كاربردها همچون بعضي از انواع سنجش طيف فركانسي، در حوزه مقصد تبديل، اكثر نقاط داده برابر يا نزديك صفر است (تنك است). در ساليان اخير روشي جديد به نام تبديل فوريه سريع تنك جهت تبديل فوريه يا معكوس تبديل فوريه چنين داده هايي ابداع و بر روي بسترهاي سخت‌افزاري گوناگون پياده سازي شده است. تبديل فوريه سريع تنك در مقايسه با تبديل فوريه سريع معمولي به كل نقاط داده در حوزه مبدأ تبديل نياز ندارد كه به معني به كارگيري مبدل هاي آنالوگ به ديجيتال ارزان در ورودي مدار محاسبه تبديل است. هدف اين پژوهش پياده سازي سخت افزاري اين واحد پردازشي با بهبود عملكرد آن نسبت به كارهاي قبلي است. از تكنيك هاي اشتراك گذاري و استفاده مجدد از واحدهاي محاسباتي، براي بهينه سازي طرح به لحاظ سرعت محاسبات و حجم سخت افزار استفاده شده است. خروجي نهائي سخت‌افزار، مكان و مقدار فركانس‌هاي قابل ملاحظه در داده است. پياده سازي سخت افزاري اين واحد مبتني بر الگوريتم كدگشايي سندرم مي‌باشدكه بخش هاي اصلي محاسباتي آن واحد حل معادلات درجه مختلط 2 و 3 و واحد دستگاه معادلات مختلط خطي است. طراحي، پياده سازي و شبيه سازي سخت‌افزار از طريق نرم‌افزارهاي Simulink، Simulink HDL coder، Modelsim، ISE Xilinx، Active HDL به انجام رسيده است. صحت سنجي نهايي سخت افزار با استفاده از مدل سطح پايين آن و چند تابع سنجش صورت گرفته است. توابع سنجش شامل داده‌هاي مختلف با طيف‌هاي فوريه متفاوت از نظر مكان فركانس‌هاي قابل ملاحظه و مقدار ضريب فوريه آنها هستند. سخت‌افزار ارائه شده قادر به محاسبه با دقت بالاي طيف فوريه داده يك ميليون نقطه‌اي حاوي حدود 720 فركانس قابل ملاحظه در زمان حدود يك ميلي ثانيه مي باشد. در شرايط برابر كار حاضر با چند پژوهش مشابه مقايسه شده است كه نسبت به سريع ترين آنها، 50 درصد افزايش سرعت به آمده است. ميزان خطاي به دست آمده كمتر از 0.01 درصد مي باشد. اين تبديل با استفاده از تنها 5.6 درصد از كل نقاط حوزه زمان انجام مي گردد كه معادل با نمونه برداري در حوزه زمان با نرخي بسيار كمتر از نرخ نايكوئيست مي باشد. در صورتي كه تعداد فركانس قابل ملاحظه بيشتر باشد، زمان محاسبات طولاني تر و براي تعداد فركانس كمتر، زمان محاسبه سريع تر مي گردد. در مقايسه با پژوهش‌هاي مشابه قبلي سخت‌افزار حاصل از نظر وفق پذيري نيز عملكرد بهتري دارد و ميزان منابع مصرفي برابر با 20 درصد از Regs، 27 درصد از LUTs، 29 درصد از BRAMs و 31 درصد از DSP48s در تراشه XC6VLX240t مي باشد. اكثر منابع مصرفي سخت‌افزار مربوط به 7 مبدل فوريه سريع 8192 نقطه اي درون طرح است كه با جايگزيني آنها با ساختارهاي ديگر مبدل فوريه سريع مي توان منابع مصرفي را كاهش داد. به علاوه با توجه به تحليل هاي به دست آمده، قابليت افزايش سرعت كل سخت افزار كماكان وجود دارد.
چكيده انگليسي :
One of the problems in the field of digital data processing is computing the Fourier transform of big data. Hardware implementation of fast Fourier transform (FFT) for various applications is common for N below 217 in order to prevent high resource consumption. In some applications such as some types of spectrum sensing, in the destination domain, most data points are equal to or near zero (sparse). In recent years, a new method called Sparse Fast Fourier transform has been developed for computing the Fourier transform or the inverse of the Fourier transform of such data. Compared with FFT, Sparse Fast Fourier Transform (SFFT) does not require the entire data points in the source domain, which results in the use of some cheaper analog-to-digital converters at the input section of the calculation circuit. The purpose of this research is hardware implementation of this processing unit to improve its performance compared to previous works. The resource sharing and reuse techniques were used to optimize the design in terms of computing speed and hardware resource utilization. The outputs of the hardware are the locations and amplitudes of valuable components in frequency domain. The design is based on the syndrome decoding algorithm in which the main computational units are the unit of solving complex equations of order 2 and 3, and the unit of complex linear equations system. The design, implementation, and simulation of the hardware are done by Simulink, Simulink-HDL -coder, Modelsim, ISE Xilinx, and Active HDL softwares. The final verification of the hardware is done by using the low-level model of the design and several test bench functions. The test bench functions include different data with different Fourier spectra in terms of the location of the valuable frequencies and the Fourier coefficient values. The proposed hardware is able to calculate the Fourier spectrum of a million-point data containing about 720 valuable frequencies in about 1 ms with high accuracy. In equal conditions, compared with other works the proposed design shows 50 percent increase in speed. The error rate is below 0.01 %, and the conversion is done by using only 5.6 percent of total time-domain data points, which is equivalent to a much lower sampling rate than the Nyquist rate. If the number of valuable frequencies is higher, a longer computation time occurs and for a smaller number of them, the time is lower. Also compared to previous works, the resulting hardware performs better in terms of resource consumption. It consumes 20% of Regs, 27% of LUTs, 29% of BRAMs, and 31% of DSP48s of the XC6VLX240t chip. Most of the hardware consumption is related to the seven 8192-point FFT units in the design, which can be reduced by replacing them with other FFT unit structures. In addition, according to the obtained analysis results, there is still possibility to increase the speed of the hardware.
