N Mahdavi
email: mahdavi_n2@yahoo.com

Masuri Bin
email: masuri@vlsi.eng.ukm.my

Keywords: Radix, FFT, Butterfly, VLSI, Floating point

Using Fast Fourier Transform (FFT) is indispensable in most signal processing applications. Designing an appropriate algorithm for the implementation of FFT can be efficacious in digital signal processing. Sophisticated techniques such as pipelining and parallel calculations have potential impacts on VLSI implementation of FFT algorithm. Furthermore, a mathematic approach such as floating point calculation achieves higher precision. In this paper, an efficient algorithm with using parallel and pipelining methods is proposed to implement high speed and high resolution FFT algorithm. Latency reduction is an important issue to implement the high speed FFT on FPGA. The Proposed FFT algorithm shows the latency of 5131 clock pulse when N refers to 1024 points. The design has the mean squared error (MSE) of 0.0001 which is preferable to Radix 2 FFT.

I. INTRODUCTION

ast Fourier transform is a faster version of DFT which was invented by Cooley & Tuky in 1965 [START_REF] Cooley | An Algorithm for the Machine Calculation of Complex Fourier series[END_REF]. There are several types of FFT algorithms. Radix-2 is a practical algorithm to calculate FFT by using decimation in time (DIT) method.

The main idea of decimation in time is to sunder the input string of n h with length of DFTs. This procedure will continue till only 2-point DFTs remains [START_REF] Saidi | Decimation-in-time frequency FFT algorithm[END_REF]. The final result is the formation of FFT algorithm. In 2006 petrovsky [START_REF] Petrovsky | Automatic Generation of Split-Radix 2-4 Parallel-Pipeline FFT Processors: Hardware Reconfiguration and Core Optimization[END_REF] implemented Radix 2-4 based on parallel-pipeline FFT-processors at structural level. He achieved 0.00201 MSE on his FFT algorithm. This paper shows the implementation of high speed and high resolution FFT based on parallel pipeline and floating point Radix-2 with the minimum MSE of 0.0001.

The next section describes the principle of the FFT structure. The mathematical formulation and block diagram of pipeline FFT algorithm is described in section III. Section IV shows implementation and design result in brief. Finally, conclusion is expressed in section V.

II. PRINCIPLE OF THE FFT STRUCTURE

The computation of N-point FFT via decimation-in-time

algorithm requires   N N O 2 log complex multiplication
time [START_REF] Lo Sing Cheng | Efficient FPGA Implementation of FFT based Multipliers[END_REF] and it will be increased if basic butterfly computation is used for adder and multiplication in decimation-in-time FFT algorithm. Additionally a complicated controller is also required. Furthermore, implementing fixed point FFT algorithm, results the output differs significantly in comparison to the expected output.

To obtain the high speed and high resolution FFT algorithm, implementation of the floating point pipeline FFT is applied.

The proposed method shows high performance of the FFT algorithm. The principle architecture is based on using a memory to keep input and output data. Thus, it reduces hard ware complexity. All the blocks are designed to operate with the same clock frequency. These stages implement as pipeline and parallel to reduce FFT calculations time.

III. FFT BLOCK DIAGRAM DESCRIPTION

Figure 1 shows the main block diagram of the FFT algorithm. Each block will be investigated separately.

A. Radix-2 Butterfly Algorithm

First, the RAM is initialized by external microprocessor and the data are loaded to the RAM by bit reserve address pin. The Radix 2 Butterfly block is the primary prefatory step taken in DIT FFT [START_REF] Hemmert | An Analysis of The Double-Precision Floating-point FFT on FPGAs[END_REF][START_REF] Zheng | Design and implementation of a parallel real-time FFT processor[END_REF]. This block calculates the complex number in equation 1 and 2 as follow.

2 1 1 input W input output k    (1) 2 1 2 input W input output k    (2)
1 o iY X output   , 2 2 2 o o iY X output   and k k W w k iY X W   we have:     2 2 1 1 1 i W i W i o o Y Y X X X iY X k k       (3)     2 2 1 i W i W i X Y Y X Y i k k          2 2 1 2 2 i W i W i o o Y Y X X X iY X k k       (4)     2 2 1 i W i W i X Y Y X Y i k k     
Thus, each butterfly requires four real multiplications and six real additions. If the above equations are implemented using fixed point calculations, the error possibility of the result will increase. These errors [START_REF] Ifeachor | Digital Signal Processing: A Practical Approch[END_REF] consist of round-off, overflow and coefficient quantization errors. To reduce the errors and provide high resolution, floating point adder/subtractor is replaced. This adder/subtractor operates in 3 stages including mantis alignment, mantis addition/ subtraction and normalization. Thus, each of the above phases can be used as stages for pipeline implementation. We convert the first phase into two stages in order to achieve higher clock frequency [START_REF] Mano | Computer System Architectur. Third Edition[END_REF], [START_REF] Patterson | Computer Organization & Design: the Hardware/ Software Interface[END_REF]. Figures 2 and3 show the block diagram of the pipeline adder/subtractor and multiplier. It is not necessary to adjust the exponents in multiplier. Since the normalized inputs are loaded to the multiplier, the mantises are multiplied and the exponents are added and amended. The result may be shifted one bit leftward. Thus the exponent will be decremented one unit.

B. ROM and RAM Blocks

The ROM in Radix-2 FFT algorithm has two look-up tables to save There is a RAM in the FFT block diagram. According to the system workflow, two complex data must be read from the RAM simultaneously and loaded to the butterfly block. Meanwhile, the two outputs of the butterfly block have to be written in the RAM at the same time. Figure 5 shows the internal structure of the RAM with the capability of reading and writing the two complex data simultaneously.

IV. IMPLEMENTATION RESULT

The new architecture of the Radix-2 FFT algorithm Verilog code was written and simulated by Matlab software. The design code is downloaded to the Virtax-2 FPGA board. From Xilinx ISE synthesize report, it was shown minimum clock period is 9.94 ns (Maximum Frequency is 100.6 MHz). The chip layout on Virtex 2 FPGA board is shown in Figure 6.

Figure 7 shows the output digital signal of the new Radix-2 FFT algorithm which simulated by Modelsim software.

Figure 8 shows the measured signal spectrum achieved by Radix-2 FFT algorithm for 1024 floating point complex data.

VI. ACKNOWLEDGMENT

We wish to thank our friend, Dr. Mohamad Amir Amini who has assisted us for completion of this dissertation.

v N 2 

 2 into two substrings with odd and even indexes. The N-point DFT of n h can be achieved by suitable combining to 2 N -point DFT of each substring. Each one of them can be reduced to 4 N -point

Fig. 2 .Fig. 3 .Fig. 4 .

 234 Fig. 2. Pipeline floating point adder/ subtractor

kW

  coefficients. These coefficients are inherently complex numbers so the real & imaginary parts are separately kept on that. Since the amplitude of the sine and cosine are the same in the four quarters, (they only differ in the signs)

Fig. 5 .

 5 Fig. 5. Internal structure of the RAM

Fig. 6 .

 6 Fig. 6. The core layout on FPGA board

Fig. 7 .Fig. 8 .

 78 Fig. 7. The output digital signal of the system


Rozita Teymourzadeh
email: rozita60@eng.ukm.my

Burhanuddin Yeop Majlis

V H Mok

Masuri Bin Othman

VLSI Implementation of High Resolution High Speed Low Latency Pipeline Floating point Adder/Subtractor for FFT Applications

This paper presents on-chip implementation of high speed low latency floating point adder /subtractor with high accuracy performance for FFT in OFDM transceiver. However due to high performance and high resolution, the floating point adder is matched with power network applications as well. The design was implemented for 32-bit pipelined adder/subtractor which satisfied IEEE-754 Standard for floating -point Arithmetic. The design is focused on the trade-off between the latency and speed improvement as well as resolution and silicon area for the chip implementation. In order to reduce the critical path and decrease the latency, the novel structure was designed and investigated. Consequently, synthesis report indicating the latency of 4 clock cycles due to each stage operate within just one clock cycle. The unique structure of designed adder well thought out. The synthesis software provides results representing the estimated area and delay for design when it is pipelined to various depths. I.

INTRODUCTION

Recently Orthogonal frequency division multiplexing [START_REF] Bingham | Multicarrier Modulation for Data Transmission: An Idea Whose Time has Come[END_REF] (OFDM) techniques have received immense attention in high-speed data communication systems such as wireless local area network (WAN), digital audio/video broadcasting and beyond 3G research [START_REF] Tian | Efficient Algorithms of FFT Butterfly For OFDM Systems[END_REF]. OFDM is a multi-carrier transmission technique, which divides the available spectrum into many carriers, each one being modulated by a low rate data stream. Then Inverse Fast Fourier Transform (IFFT) or Fast Fourier Transform (FFT) transforms are used to get the signal in time domain or spectrum frequency. FFT reduces the complexity of the OFDM. Hence the performance of the FFT has highly effect on the OFDM system result. High resolution, high speed and low latency, FFT would not be achieved unless with efficient elements in particular such the butterfly component. The performance of butterfly is greatly depending on its adders and subtractors. Hence, this paper with emphasis of the simple structures, focused on design and implementation of efficient high performance floating point adder/subtractor for FFT algorithm. Narasimhan [START_REF] Narasimhan | A 100 MHz FPGA Based Floating point Adder[END_REF] in 1993 proposed 8 stage floating point adder for FPGA. The specifications for the adder stated that it should work at 62.5 MHz. In 2004, John Thompson [START_REF] Thompson | A 64-bit Decimal Floating-point Adder[END_REF] presented a decimal floating-point adder with 5 stages that compiled with the current draft revision of IEEE-754 Standard. The adder supported operations on 64-bit (16-digit) decimal floating-point operands. Initial synthesis testing and evaluation was done and performed using Synopsys Design Compiler and LSI Logic's Gflxp 0.11 micron CMOS standard cell library. In 2005, Chi Huang presented [START_REF] Huang | A Design of High Speed Double Precision Floating Point Adder Using Macro Modules[END_REF] high speed double precision floating point adder using custom-designed macro modules and other advanced optimization technology. Based on SMIC six-layer-metal CMOS process, he achieved a 4-stage pipelined double precision floating point adder which could complete a floating point addition in 7.72ns. The total gate count in this system is 37977 gates. All the results show that the effort is taken to achieve low latency & area, high resolution and speed by introducing the new algorithms. In this paper the advanced floating point adder with pipelined structure is presented. The similar work also represented within year 2005 to 2009 [START_REF] Shi Chen | Implementation of Vector Floating-Point Processing Unit on FPGAs For High Performance Computing[END_REF][START_REF] Xenoulis | Test Generation Methodology For High-Speed Floating Point Adders[END_REF][START_REF] Wai Yu | Optimizing Coarse-Grained Units in Floating Point Hybrid FPGA[END_REF], to show engineers effort for increasing the capability of floating point calculation. However still there are not enough available resources regarding floating point arithmetic.

II. DESIGN AND IMPLEMENTATION

Based on IEEE-754 standard for floating point [START_REF]Draft IEEE Standard for Floating-Point Arithmetic[END_REF] arithmetic 32-bit data register is considered to allocate mantissa, exponent and sign bit in a portion of 23, 8 and 1 bit respectively. The advantage of this adder is that it can be easily switched to 12-bit mantissa 8-bit power and 1-bit sign bit arithmetic calculations. Additionally the floating-point adder unit performs the addition and subtraction using substantially the same hardware as used for floating-point operations. This advantage causes saving the core area by minimizing the number of elements. Figure 1 shows the new structure of the floating point adder when it is divided to the four separate blocks. The purpose is that to share total critical path delay into three equal blocks. These blocks calculate the arithmetic function within 1 clock cycle. However the propagation delay can be associated with continues assignment [START_REF] Ciletti | Advanced Digital design with the Verilog HDL[END_REF] so that to increase the overall critical path delay and the reason of slowing down the throughput. Hence in this paper, the effort is taken to reduce the worst effect of delay for arithmetic calculations. Based on combinational circuit design, the output of each stage is only depending on its input value at the time. As shown in the Fig. 1, each block creates the output within 1 clock cycles at the time. The unique structure of this adder enables us to feed the output result in pipeline registers after every clock cycles. Hence, the sequential structure is applied for overall pipelined add/subtractor algorithm to combine the stages. The pipeline floating point adder structure consists of compare stage, aligned mantissa, add/subtractor stage and finally normalized stage. While the effective operation is determined the blocks, compare stage and aligned mantissa lead us to align the mantissa and exponent accordingly to make sure having the same exponent in two operands. The significant point is to design the function so that all calculation performs within one clock cycle. The basic operation of the aligned mantissa and normalized block is shifting. Every shifting need one clock cycle and it causes huge delay to align 32-bit operand. Hence, the advanced algorithm is applied to avoid having many delays on aligning stage. This is the third advantage of the mentioned adder. Fig. 2345show the internal structure of proposed pipelined adder/subtractor algorithm whereas Fig. 1 and Fig. 6 present the overall structure of pipelined adder. As shown in the figures, the smart algorithm is designed for add/sub stage to apply two's complement for the operand if it is required and combine addition and subtraction in the same hardware block diagram. In addition to save power consumption, the proposed architecture also offers power savings due to the simplification of data paths. Ignoring the shifting blocks and combine the adder and subtractor has the significant role to reduce power-effective in the overall system. The total number of gate count in the system is 6691 which is given by synthesis report of Xilinx ISE synthesis software. This total gate count proves the low area and low power consumption for proposed floating point adder/subtractor, whereas the almost similar project implements the adder with the equivalent gate count of 37977 [START_REF] Huang | A Design of High Speed Double Precision Floating Point Adder Using Macro Modules[END_REF].

III. IMPLEMENTATION RESULT

The implementation was modeled in Verilog HDL code and simulated by Modelsim software. The design was synthesized by Xilinx-ISE software and downloaded to FPGA Virtex II.

The synthesis result shows the system specification of every stage of the pipelined floating point adder/subtractor separately. These stages are introduced as Compare, Align, Add/Sub and Normalized stages (Tables I-IV). Finally the synthesis result of overall system by combining of the mentioned stages is given (Table V). From Xilinx ISE synthesize report; it was found minimum clock period is 3.592 ns (Maximum Frequency is 278.428 MHz) for floating point adder/subtractor. As shown in the result, total slice number in overall pipeline floating point adder is less than the sum of the each cell blocks. It is due to advance configurations which avoid repeating the similar slice and try to reuse the similar slice again. Furthermore, the minimum clock periods increased sharply after add/sub stage was applied. This issue can be explained by utilizing FPGA adder to calculate fixed point arithmetic. However the speed result is high enough to cover the subject and for future work, enhancing the maximum frequency will be obtained by applying high speed prefix adder [START_REF] Burgess | Prenormalization rounding in IEEE floating-point operations using a flagged prefix adder[END_REF] to calculate fix point arithmetic. The chip layout on Virtex II FPGA board has been shown in Fig. 7. The estimated latency of the design for 32 bit resolution is 4 clock cycle due to its pipeline structures.

IV. CONCLUSION

Efficient algorithm of high resolution high speed low area floating point adder/subtractor with reducing mean latency for FFT in OFDM applications was designed and investigated. The structure of the adder is consisting of 4 parts called compare stage, aligned stage, add/sub stage and finally normalized stage. Each block calculates the arithmetic operation within 1 clock cycle. The result will be inputted to the pipeline register and it is the reason to reduce the latency. The unique structure of this adder ignores all the shifter cells and replace it with multiplexer to reduce delay propagation through each cells. The evaluation indicates that the proposed pipelined adder is attractive due to high resolution (32-bit floating point), low area (6691 gate count) and low latency of 4 clock cycle. The maximum frequency for this adder is 278.428 MHz. To increase the speed, prefix adder can be replaced with FPGA structural adder to calculate.

Figure 1 .Figure 6 .Figure 7 .

 167 Figure 1. Block diagram of the proposed Adder/Subtractor Figure 2. Compare stage structure

TABLE I

 I

	TABLE III.	NORMALIZED STAGE SPECIFICATION	TABLE IV.
	.	COMPARE STAGE SPECIFICATION	TABLE II.	ALIGN STAGE SPECIFICATION

ADD/SUB STAGE SPECIFICATION TABLE V. FLOATING POINT ADDER /SUBTRACTOR SPECIFICATION


Choo Kian Hoe

Aravind Chokalingam Vaithlingam
email: aravind_147@yahoo.com

Rozita Teymourzadeh

Rajparthiban Rajkumar

Design of Automatic Soil Humidity Control using Maximum Power Point Tracking Controller

Keywords:

The photovoltaic system uses the photovoltaic array as a source of electrical power for the direct conversion of the sun's radiation to direct current without any environmental hazards. The main purpose of this research is to design of a converter with Maximum Power Point Tracker (MPPT) algorithm for any typical application of soil humidity control. Using this setup the major energy from the solar panel is used for the control of soil humidity. The design of the converter with MPPT together with the soil humidity control logic is presented in this paper. Experimental testing of the design controller is implemented and evaluated for performance under laboratory environment.

INTRODUCTION

Water and energy resources are the most essential elements for sustaining human needs, maintaining health and food production, as well as for social and economic development. Based on previous research work, the capital city in the text is endeavouring hard to ascertain ways and means to keep the water level at the optimum level by finding an alternative water supply to maintain the high rising demand for water [1]. The actual cause of this high demand for water is due to the improper usage and handling of the clean water. In order to sustain the rising demand of energy, some alternative energy resources have been proposed in recent years such as solar energy, wind and tidal resources. Solar energy is prevalent popular choice of clean, recyclable renewable energy as they are more environmental friendly. Unfortunately, the optimal utilisation of the photovoltaic [START_REF] Lin | A battery charger with maximum power point tracking function for low-power photovoltaic system applications[END_REF][START_REF] Gamboa | A unity power factor, maximum power point tracking battery charger for low power wind turbines[END_REF][START_REF] Giustiniani | Low-Frequency Current Oscillations and Maximum Power Point Tracking in Grid-Connected Fuel-Cell-Based Systems[END_REF] energy is a major drawback with the conversion efficiency being in the range of 8 to 16 percent. This percentage is even lower with lesser radiation from the sun due to the improper weather conditions. In order to overcome these problems, the converter is designed with Maximum Power Point Tracking (MPPT) system. This paper presents a simple photovoltaic rainwater pumping system which is taken as an application to demonstrate the soil humidity control with the MPPT-based converter. The soil humidity controller acts automatically when the humidity of the system drops thereby pumping the rainwater that is collected underneath in the reservoir. The humidity level can be adjusted by the users using a set point value.

II. SYSTEM OVERVIEW

The system configuration is divided into two parts, buck converter with MPPT algorithm and soil humidity controller. Figure 1 The buck converter is designed based on explications given in ref [START_REF] Muhammad | Power Electronics, Circuits, Devices & Applications[END_REF]. The MPPT algorithm is generated using the PWM where the MOSFET driver activates the corresponding switch operations. The soil humidity controller uses a microcontroller to control the soil humidity. Using a humidity sensor such as capacitive sensor, the status of the humidity level is measured and displayed on the LCD screen.

The controller activates the external water pump once the humidity level drops to the pre-set value.

Figure 4 shows the block diagram for the soil humidity controller. Figure 5 shows the complete schematic for the designed system.

Soil Humidity

Capacitive Sensor

Microcontroller

External Pump

Soil humidity below the set value Display

(b) MPPT Controller

The energy harvested through the photovoltaic array has an optimum point, which is called the Maximum Power Point Tracking (MPPT). This maximum power point cannot be achieved when the voltage or the current of the operating system is incompatible with the solar array [START_REF] Liu | Design and Implementation of a Maximum Power Point Tracking Battery Charging System for Photovoltaic Applications[END_REF]. Meanwhile, the maximum power point is also dependent on the temperature and the degree of the solar radiation striking by the panel. Therefore, the Maximum Power Point Tracker method is used to ensure that the solar module to extract the maximum power from the solar panel for rapidly changing conditions to charge the battery. For generating the pulse width, the TL494CN is used instead of PIC or microcontroller since all the functions needed to construct a pulse width modulation is incorporated in this chip. The more flexible TL494 is specially designed for power supply control.. The MPPT algorithm can be achieved by using the internal function of the chip.

Internally, it has two error amplifiers, an on-chip adjustable oscillator, a Dead Time Control (DTC) comparator, a pulse-steering control flip-flop, a 5V precision regulator and output control circuits. The TL494 achieved the MPPT by using the error amplifiers that measures the output signal and the sets the value to automatically change the PWM of the converter to achieve the maximum point of the power supplied to the converter [START_REF]Designing Switching Voltage Regulators with the TL494[END_REF].

(c) Soil Humidity Controller

A microcontroller PIC16F887 is used for the soil humidity sensing and controller application. It has the feature of sensing by means of the soil humidity sensor and displays the humidity level on the LCD screen. The controller activates the external water pump once the humidity level drops to the set value. The built-in ADC is suitable to read the soil humidity since the output signal from the humidity sensor is in analog. The humidity sensor is supplied with 5V DC voltage and the output signal is based on the capacitance value of the sensor. Figure 6 shows the ADC value programmed into the controller. IV. HARDWARE OVERVIEW Figure 7 shows the prototype for the experimental setup operating by extracting the maximised energy from the solar panel. The solar panel can be adjusted based on the geographic coordinate of the place, since different place has different coordinate of sun radiation that strikes it at a different angle on the plane of the solar panel. Once the energy is generated, the buck converter with Maximum Power Point Tracker (MPPT) extracts the most energy from the solar panel to use in the soil humidity controller and store some of the energy in the battery for back-up operation. From this, the system performs autonomously with sufficient/adequate sun radiation and rainwater. V. RESULTS AND DISCUSSION Figure 8 shows the three different radiation levels on the solar panel at various times of the day to derive the solar characteristics. Figure 9 shows the three different solar radiations on the solar panel based on the power and voltage curves of the solar panel. The PV graph is plotted to show the maximum power point of the solar panel for optimal control. Figure 10 shows the time and voltage characteristics of the converter. The charging point of the converter based on the time of day indicated can be determined from this plot. The converter with MPPT algorithm is designed constructed, built and validated for performance. This power output is able to be used in soil humidity controller with battery backup. The external source is able to supply water to the soil when the humidity level is dropped to the desired humidity level. This research has a contributory significance to the current endeavours for safe, renewable and environmental friendly alternative source of energy in the face of countering the adverse human intervention effects on the global climatic change environment.

Figure 1 :

 1 Figure 1: Overview of the Complete System

Figure 2 Figure 2 :

 22 Figure2shows the block diagram for the buck converter with MPPT algorithm.

Figure 4 :Figure 5 :Figure 5 :

 455 Figure 4: Soil humidity control

Figure 6 :

 6 Figure 6: ADC measurements versus Humidity

Figure 7 :

 7 Figure 7: Prototype experimental setup

Figure 8 :

 8 Figure 8: Solar panel radiation characteristics

  indicates the overall block diagram representation of the system.

	Solar Panel	Converter with MPPT	Soil Humidity Controller
		Battery
		Backup


Rozita Teymourzadeh

Yazan Samir Algnabi

Nooshin Mahdavi

Masuri Bin Othman

On-chip Implementation of High Resolution High Speed Floating Point Adder/Subtractor with Reducing Mean Latency for OFDM

Keywords: OFDM, FFT, FPGA, Synopsys design compiler, CMOS layout

Fast Fourier transform (FFT) is widely applied in OFDM trance-receiver communications system. Hence Efficient FFT algorithm is always considered. This paper proposed FPGA realization of high resolution high speed low latency floating point adder/subtractor for FFT in OFDM trancereceiver. The design was implemented for 32 bit pipelined adder/subtractor which satisfied IEEE-754 Standard for floating-point Arithmetic. The design was focused on the trade-off between the latency and speed improvement as well as resolution and silicon area for the chip implementation. In order to reduce the critical path and decrease the latency, the novel structure was designed and investigated. Consequently, synthesis report indicated the latency of 4 clock cycles due to each stage operated within just one clock cycle. The unique structure of designed adder well thought out resulted 6691 equivalent gate count and lead us to obtain low area on chip. The synthesis Xilinx ISE software provided results representing the estimated area and delay for design when it is pipelined to various depths. The report shows the minimum delay of 3.592 ns or maximum frequency of 278.42 MHz.

INTRODUCTION

Recently

Orthogonal Frequency Division Multiplexing [START_REF] Bingham | Multicarrier modulation for data transmission: An idea whose time has come[END_REF] (OFDM) techniques have received immense attention in high-speed data communication systems such as Wireless local Area Network (WAN), digital audio/video broadcasting and beyond 3G research [START_REF] Tian | Efficient algorithms of FFT butterfly for OFDM systems[END_REF] .

OFDM is a multi-carrier transmission technique, which divides the available spectrum into many carriers, each one being modulated by a low rate data stream. Then Inverse Fast Fourier Transform (IFFT) or Fast Fourier Transform (FFT) transforms are used to get the signal in time domain or spectrum frequency. FFT reduces the complexity of the OFDM. Hence the performance of the FFT has highly effect on the OFDM system result.

High resolution, high speed and low latency, FFT would not be achieved unless with efficient elements in particular such the butterfly component. The performance of butterfly is greatly depending on its adders and subtractors. Hence, this research with emphasis of the simple structures, focused on design and implementation of efficient high performance floating point adder/subtractor for FFT algorithm.

Narasimhan [START_REF] Narasimhan | A 100 MHz FPGA based floating point Adder[END_REF] in 1993 proposed 8 stage floating point adder for FPGA. The specifications for the adder stated that it should work at 62.5 MHz.

In 2004, Thompson [START_REF] Thompson | A 64-bit decimal floating-point adder[END_REF] presented a decimal floatingpoint adder with 5 stages that compiled with the current draft revision of IEEE-754 Standard. The adder supported operations on 64 bit (16 digit) decimal floating-point operands. Initial synthesis testing and evaluation was done and performed using Synopsys Design Compiler and LSI Logic's Gflxp 0.11 micron CMOS standard cell library.

In 2005, Huang et al. [START_REF] Huang | A design of high speed double precision floating point adder using macro modules[END_REF] presented high speed double precision floating point adder using customdesigned macro modules and other advanced optimization technology. Based on SMIC six-layermetal CMOS process, he achieved a 4 stage pipelined double precision floating point adder which could complete a floating point addition in 7.72 ns. The total gate count in this system is 37977 gates.

All the results show that the effort is taken to achieve low latency and area, high resolution and speed by introducing the new algorithms. In this study the advanced floating point adder with pipelined structure is presented.

The similar work also represented within year 2005 to 2009 [START_REF] Shi Chen | Implementation of vector floating-point processing unit on FPGAs for high performance computing[END_REF][START_REF] Xenoulis | Test generation methodology for high-speed floating point adders[END_REF][START_REF] Yu | Optimizing coarse-grained units in floating point hybrid FPGA[END_REF] , to show engineers effort for increasing the capability of floating point calculation. However still there are not enough available resources regarding floating point arithmetic.

Design and implementation: Based on IEEE-754 standard for floating point [START_REF] Hollasch | IEEE Standard 754 Floating Point Numbers[END_REF] arithmetic 32 bit data register is considered to allocate mantissa, exponent and sign bit in a portion of 23, 8 and 1 bit respectively. The advantage of this adder is that it can be easily switched to 12 bit mantissa 8 bit power and 1 bit sign bit arithmetic calculations. Additionally the floating-point adder unit performs the addition and subtraction using substantially the same hardware as used for floating-point operations. This advantage causes saving the core area by minimizing the number of elements. Fig. 1 shows the new structure of the floating point adder when it is divided to the four separate blocks. The purpose is that to share total critical path delay into three equal blocks. These blocks calculate the arithmetic function within 1 clock cycle. However the propagation delay can be associated with continues assignment [START_REF] Ciletti | Advanced Digital design with the Verilog HDL[END_REF] so that to increase the overall critical path delay and the reason of slowing down the throughput. Hence in this study, the effort is taken to reduce the worst effect of delay for arithmetic calculations.

Based on combinational circuit design, the output of each stage is only depending on its input value at the time. As shown in the Fig. 1, each block creates the output within 1 clock cycles at the time. The unique structure of this adder enables us to feed the output result in pipeline registers after every clock cycles. Hence, the sequential structure is applied for overall pipelined add/subtractor algorithm to combine the stages.

The pipeline floating point adder structure consists of compare stage, aligned mantissa, add/subtractor stage and finally normalized stage.

While the effective operation is determined the blocks, compare stage and aligned mantissa lead us to align the mantissa and exponent accordingly to make sure having the same exponent in two operands.

Fig. 1: Block diagram of the proposed adder

The significant point is to design the function so that all calculation performs within one clock cycle. The basic operation of the aligned mantissa and normalized block is shifting. Every shifting need one clock cycle and it causes huge delay to align 32 bit operand. Hence, the advanced algorithm is applied to avoid having many delays on aligning stage. This is the third advantage of the mentioned adder. In addition to save power consumption, the proposed architecture also offers power savings due to the simplification of data paths. Ignoring the shifting blocks and combine the adder and subtractor has the significant role to reduce power-effective in the overall system.

The total number of gate count in the system is 6691 which is given by synthesis report of Xilinx ISE synthesis software. This total gate count proves the low area and low power consumption for proposed floating point adder/subtractor, whereas the almost similar project implements the adder with the equivalent gate count of 37977 [START_REF] Huang | A design of high speed double precision floating point adder using macro modules[END_REF] .

MATERIALS AND METHODS

The Floating point adder designed according to the IEEE 754 standard. The design process was to create software model of efficient pipeline floating point adder algorithm using Verilog HDL programming language. The system was simulated by Modelsim and its function was fully covered accordingly.

The design was emulated the following characteristics; Floating point arithmetic computation, Pipelined addition and subtractions and finally data and factor precision. The proposed adder was fabricated on FPGA Virtex-II chip and the layout core was submitted respectively.

RESULTS AND DISCUSSION

Implementation result: The implementation was modeled in Verilog HDL code and simulated by Modelsim software. The design was synthesized by Xilinx-ISE software and downloaded to FPGA Virtex II.

The synthesis result shows the system specification of every stage of the pipelined floating point adder/subtractor separately. These stages are introduced as Compare, Align, Add/Sub and Normalized stages (Table 1234). Finally the synthesis result of overall system by combining of the mentioned stages is given (Table 5). ---------------------------------------------------------------------------------- ---------------------------------------------------------------------------------- ---------------------------------------------------------------------------------- From Xilinx ISE synthesize report; it was found minimum clock period is 3.592 ns (Maximum Frequency is 278.428 MHz) for floating point adder/subtractor. As shown in the result, total slice number in overall pipeline floating point adder is less than the sum of the each cell blocks. It is due to advance configurations which avoid repeating the similar slice and try to reuse the similar slice again.

Furthermore, the minimum clock periods increased sharply after add/sub stage was applied. This issue can be explained by utilizing FPGA adder to calculate fixed point arithmetic. However the speed result is high enough to cover the subject and for future study, enhancing the maximum frequency will be obtained by applying high speed prefix adder [START_REF] Burgess | Prenormalization rounding in IEEE floating-point operations using a flagged prefix adder[END_REF] to calculate fix point arithmetic. The chip layout on Virtex II FPGA board has been shown in Fig. 7.

The estimated latency of the design for 32 bit resolution is 4 clock cycle due to its pipeline structures. ---------------------------------------------------------------------------------- The advance design algorithm leaded us to have minimum equivalent of gate count (6691 gate) resulted saving area and power consumption satisfied low area low power on chip core. This value is 37977 gates in previous research work [START_REF] Huang | A design of high speed double precision floating point adder using macro modules[END_REF] .

----------------------------------------------------------------------------------- QTY

CONCLUSION

Efficient algorithm of high resolution high speed low area floating point adder/subtractor with reducing mean latency for OFDM applications was designed and investigated. The structure of the adder is consisting of 4 parts called compare stage, aligned stage, add/sub stage and finally normalized stage. Each block calculates the arithmetic operation within 1 clock cycle. The result will be inputted to the pipeline register and it is the reason to reduce the latency. The unique structure of this adder ignores all the shifter cells and replace it with multiplexer to reduce delay propagation through each cells. The evaluation indicates that the proposed pipelined adder is attractive due to high resolution (32 bit floating point), low area (6691 gate count) and low latency of 4 clock cycle. The maximum frequency for this adder is 278.428 MHz. To increase the speed, prefix adder can be replaced with FPGA structural adder to calculate.

Fig. 2 -Fig. 3 :Fig. 6 :

 236 Fig. 2: Compare stage structure

Fig. 7 :

 7 Fig. 7: The core layout on FPGA board

Table 1 :

 1 Compare stage specification HDL synthesis report -

Table 2 :

 2 Align stage specification HDL synthesis report -

	-
	QTY

Table 3 :

 3 Add/sub stage specification HDL synthesis report -

	-
	QTY

Table 4 :

 4 Normalized stage specification HDL synthesis report -

Table 5 :

 5 Floating point adder/subtractor specification HDL synthesis report -


Rozita Teymourzadeh

Yazan Samir Algnabi

Masuri Othman

Shabiul Islam

Mok Vee Hong

On-Chip Implementation of Pipeline Digit-Slicing Multiplier-Less Butterfly for Fast Fourier Transform Architecture

Keywords: Pipelined digit-slicing multiplier-less, Fast Fourier Transform (FFT), Verilog HDL, Xilinx

The need for wireless communication has driven the communication systems to high performance. However, the main bottleneck that affects the communication capability is the Fast Fourier Transform (FFT), which is the core of most modulators. This study presents on-chip implementation of pipeline digit-slicing multiplier-less butterfly for FFT structure. The approach taken; in order to reduce computation complexity in butterfly, digit-slicing multiplier-less single constant technique was utilized in the critical path of Radix-2 Decimation In Time (DIT) FFT structure. The proposed design focused on the trade-off between the speed and active silicon area for the chip implementation. The new architecture was investigated and simulated with MATLAB software. The Verilog HDL code in Xilinx ISE environment was derived to describe the FFT Butterfly functionality and was downloaded to Virtex II FPGA board. Consequently, the Virtex-II FG456 Proto board was used to implement and test the design on the real hardware. As a result, from the findings, the synthesis report indicates the maximum clock frequency of 549.75 MHz with the total equivalent gate count of 31,159 is a marked and significant improvement over Radix 2 FFT butterfly. In comparison with the conventional butterfly architecture, design that can only run at a maximum clock frequency of 198.987 MHz and the conventional multiplier can only run at a maximum clock frequency of 220.160 MHz, the proposed system exhibits better results. The resulting maximum clock frequency increases by about 276.28% for the FFT butterfly and about 277.06% for the multiplier. It can be concluded that on-chip implementation of pipeline digit-slicing multiplier-less butterfly for FFT structure is an enabler in solving problems that affect communications capability in FFT and possesses huge potentials for future related works and research areas.

INTRODUCTION

FFT plays an important role in many Digital Signals Processing (DSP) applications such as in communication systems and image processing. It is an efficient algorithm to compute the Discrete Fourier Transform (DFT). DFT is the main and important procedure in data analysis, system design, and implementation [START_REF] Oppenheim | Discrete-Time Signal Processing[END_REF]. In order to reduce the complexity computation of the FFT algorithm many modules have been designed and implemented in different platforms. These modules focus on the radix order or twiddle factors to perform a simple and efficient algorithm which includes the higher radix FFT [START_REF] Bergland | A radix-eight fast-Fourier transform subroutine for real-valued series[END_REF], the mixed-radix FFT [START_REF] Singleton | An algorithm for computing the mixed radix fast Fourier transform[END_REF], the prime-factor FFT [START_REF] Kolba | A prime factor FFT algorithm using high-speed convolution[END_REF], the recursive FFT [START_REF] Varkonyi-Koczy | A recursive Fast Fourier Transform algorithm[END_REF], low-memory reference FFT [START_REF] Wang | Novel memory reference reduction methods for FFT implementation on DSP processors[END_REF], Multiplier-less based FFT [START_REF] Zhou | Novel design of multiplier-less FFT processors[END_REF][START_REF] Prasanthi | Multiplier less FFT Processor Architecture for Signal and Image Processing[END_REF][START_REF] Mahmud | FPGA implementation of a canonical signed digit multiplier-less based FFT Processor for wireless communication applications[END_REF] and Application-Specific Integrated Circuits (ASIC) system such as stated by [START_REF] Baas | A low-power, high-performance, 1024-point FFT processor[END_REF]. ASIC-based systems are able to fit real low-power or high performance applications; however the function is very solid to be modified [START_REF] Hsu | Parallel-computing approach for FFT implementation on Digital Signal Processor (DSP)[END_REF]. The study of the digitslicing technique has been dealt by Bin [START_REF] Bin Nun | A modular approach to the hardware implementation of digital filters[END_REF]; [START_REF] Peled | Digital Signal Processing Theory, Design and Implementation[END_REF]; [START_REF] Sharrif | Digit slicing architecture for real time digital filters[END_REF] for the digital filters.

The design and implementation of Digit-slicing FFT has been discussed by [START_REF] Samad | Implementation of a high speed fast Fourier transform VLSI chip[END_REF]. This study proposed a similar idea with the ones put forth by [START_REF] Samad | Implementation of a high speed fast Fourier transform VLSI chip[END_REF]; but having a difference by the use of a different algorithm and different platform, which helps to improve the performance and achieve higher speed. Recently, FPGAs Field Programmable Gate Array have become an applicable option to direct hardware solution performance in the real time application. In this study, digit-slicing architecture was proposed in designing the pipeline digit-slicing multiplier-less butterfly.

The FFT butterfly multiplication is the most crucial part in causing the delay in the computation of the FFT. In view of the fact, the twiddle factors in the FFT processor were known in advance hence we proposed to use the pipeline digit slicing multiplier-less butterfly to replace the traditional butterfly in FFT.

The study structure is organized as follows; describes the FFT architecture in brief, explains the butterfly conventional architecture, discuses the digit slicing architecture, explicates the design of the pipeline digit-slicing multiplier-less butterfly architecture in detail and finally the implementation result and conclusion respectively.

Fast Fourier Transform (FFT):

A useful method to transform domains from the time domain to the frequency domain and the reverse for the implementation on digital hardware is the DFT. For Npoint DFT of a complex data sequence x (n) is defined in Eq. 1:

N1 kn N n0 X(k) x(n) W ,k 0,1,......., N 1       (1)
Where:

x(n) and X(k) = Complex numbers kn j2 / N N

We  

= The twiddle factor

The DFT of N-point finite sequence represents harmonically related frequency components of x(n). The direct computation of Eq. 1 requires the order of N 2 operations where N is the transform size. [START_REF] Cooley | An algorithm for the machine calculation of complex Fourier series[END_REF] found this new technique to reduce the order of complexity operations of DFT from N 2 to (Nlog 2 N). Consequently, a huge number of FFT algorithms have been developed such as Radix-2, radix-4 and split radix algorithms. These algorithms are mostly used for practical applications due to their simple structure and constant butterfly geometry.

In general, higher-radix FFT algorithm has fewer numbers of complex multiplications, whereas radix-2 FFT algorithm is the simplest form in all FFT algorithms. Furthermore, it has a regularity mode that makes it suitable for VLSI implementation as shown in the fallowing Eq. 2:

NN 11 22 nm m nm N N N n 0 n 0 22 X[m] x[2n]W W x[2n 1]W       (2)
FFT algorithm relies on a 'divide-and-conquer' methodology, which divides the N coefficient points into smaller blocks in different stages. The first stage computes with groups of two coefficients, yielding N/2 blocks, each computing the addition and subtraction of the coefficients scaled by the corresponding twiddle factors, called a butterfly for its cross-over appearance as shown in Fig. 1.

These results are used to compute the next state of N/4 blocks, which will then combine the results of two previous blocks, combining four coefficients at this point. This process is repeated until one main block is formed, with a final computation of all N coefficients. Fig. 2 shows the 8-point radix-2 DIT FFT.

Conventional

Butterfly architecture The conventional radix-2 DIT butterfly architecture consists of complex data I/O, complex multiplier and complex adder and subtraction as shown in Fig. 3.

Consider A and B as the complex input data, and the complex twiddle factor is considered as W = Wr-jWi, hence finally the complex output are X and Y. The index r and i represent the real and imaginary parts respectively:

X A WB  (3) Y A WB  (4) (Xr jXi) (Ar jAi) (Wr jWi) (Br jBi)          (5) (Yr jYi) (Ar jAi) (Wr jWi) (Br jBi)          (6)
The implementation of the complex multiplier is required for four real multipliers and two real adders as shown in Fig. 4. The complex multiplier is determined in Eq.7:

(Br jBi) (Wr jWi) (Br Wr) (Br jWi) ( jBi Wr) ( jBi jWi) [(Br Wr) ( jBi jWi)] [(Br jWi) ( jBi Wr)] [(Br Wr) (Bi Wi)] [(Br jWi) ( jBi Wr)]                            (7)
The real and imaginary parts of the multiplication result is

)] ( ) [( Wi Bi Wr Br    and )] ( ) [( Wr jBi jWi Br    respectively.
The complex adder is required for two real adders to perform addition functionality as shown in Fig. 5.

(Ar jAi) (Br jBi) (Ar Br) j(Ai Bi)        (8)
Digit-slicing architecture: The concept behind the digit-slicing architecture is any binary number that can be sliced into a few blocks of shorter binary numbers, with each block carrying a different weight. In this study, the fixed-point 2's complements arithmetic has been chosen to represent the input data, which are singed numbers with absolute value less than one. The absolute value of the input data x with length of B bits (x 0 ,x 1 ,x 2 ,….,x B-1 ) has been represented in 2's complement as:

B1 jj k0 x 2 x      (9)
To represent the sliced data, there are many different algorithms. Depending on the data type and word length, different structures can be introduced. In this study, where the fundamental sliced algorithm will be presented as following:

b1 pk (pb 1) k k0 x 2 X 2         (10)
Where:

x = Sliced into b blocks p = Bit widths per block

p1 j k k, j j0 X 2 X     (11)
Where: X k,j =All either ones or zeros except X k=b-1, j= p-1 = which is zero or minus one The algorithm in Eq. ( 10) applies when the sliced data word length is 2 x such as 2 2 =4, 2 3 = 8, 16… bits. Thus, let us consider the decimal number -0.65625 of which we would like to demonstrate how digit slicing operates accordingly:

x = 1.010 1100 2 = -0.65625 10 where, the suffix 2 refers to a binary fixed point two's complement number 8 bits and the suffix 10 refers to a decimal number, if x is sliced into two blocks, of each four bits wide, that is b = 2 and p = 4:

3 j 3 2 0 0, j j0 3 j 3 1 1 1, j j0 X 2 X 2 2 12 X 2 X 2 2 6               1 4k (8 1) k k0 x 2 X 2        4 0 4 1 7 7 10
x 2 12 2 ( 6) 2 84 x (12 96) 2 0.65625 128

                 
Another algorithm that represents the sliced data with a word length 2 x +1 such as 2 2 +1=5, 9, 17…bits can be dealt as the following:

p1 k p k k0 x 2 X        (12)
Where, x is a decimal number whose absolute value is less than one and is sliced into b blocks each of p bits wide.

The most significant block is k = 0 where this contains the only sign bit of x plus leading dummy zeros to make up a block of length p bits [START_REF] Samad | Implementation of a high speed fast Fourier transform VLSI chip[END_REF]:

k0 p1 j k k, j k, j j0 X 0 or 1 only X 2 X ; X 0 or 1 only for k 0         ( 13
)
Let us assume that the decimal number -0.328125 is represented as nine bits two's complement number:

k 2 4 k k0 4 0 4 1 3 1 4 2 3 2 1 3 5 6 10 x 2 X x [2 ] [ 1] [2 ] [2 2 ] [2 ] [2 2 ] 1 2 2 2 2 -0.328125                          
As a comparison between the first and the second algorithms, the second algorithm requires one extra block to deal with the sign bit which makes the design more complicated and requires more hardware for the implementation. In this study, the first digit-slicing algorithm has been chosen to build the digit-slicing FFT butterfly structure. Therefore, any complex numbers, F, can be sliced into smaller blocks b, each having a shorter word length, p, as illustrated in following equations:

RI F F jF  (13) b 1 b 1 pk (pb 1) pk (pb 1) R k Ik k 0 k 0 F 2 F 2 j 2 F 2                     (
j R k R k, j j0 F 2 F     (15) p1 j Ik Ik, j j0 F 2 F     (16)
Where, the values of F Ik,i and F Rk,I are either zero or one.

Pipeline digit-slicing multiplier-less butterfly architecture:

The butterfly is the smallest component to build the FFT. As mentioned in the explanations prior to this, the butterfly structure contains one complex multiplier, one complex adder, and one complex subtractor. The digit-slicing architecture has been applied for the butterfly input to slice the data into four groups each carrying four bits as shown in Fig. 8. where, A k,j are all either ones or zeros except for A k=b-1,j=p-1 which is zero or minus one.

The same applies for the input B:

b1 pk (pb 1) k k0 B 2 B 2         (19) p1 j k k, j j0 B 2 B     (20)
where, B k,j are all either ones or zeros except for the value B k=b-1,j=p-1 which is zero or minus one. The multiplication functionality is regarded as the most important operation for most signal processing systems, but it is a complex and expensive operation. Many techniques have been introduced for reducing the size and improving the speed of multipliers. Some applications require Constant Coefficient Multipliers such as digital signal processing, image processing, and multiple precision arithmetic in the design of compilers. Constant Coefficient Multipliers is one of the most common solutions to speed up the multiplication process. The multiplier can be designed for one constant which is termed as Single Constant Multiplier (SCM) or for many constant and is termed as Multiple Constant Multiplier (MCM). Since the twiddle factor in FFT processor are known in advance, a special design of SCM has been proposed to perform the multiplication function with the twiddle factor without using the traditional multiplier, which is termed as Single Constant Multiplier Less (SCML). The design of the SCML consists of four lookup tables (ROMs) and adder to perform the output as shown in Fig 9 . To generate the lookup tables data (the multiplication result possibilities), which are 16 different results for each ROM, a special MATLAB program has been written by applying the digit-slicing algorithm for all the possible numbers for the input data (4 bits) from "0000" to "1111" to perform all the possibilities for the multiplication result. The result for the SCML has been optioned by simple addition for all the lookup tables' results. In the hardware implementation, the addition logic has been reduced. During the addition of the four products obtained from the look-up tables, the least significant digit (4 bits) for each level is always added to zero. These bits will not be affected, or changed and will be carried into the next column. The storage of all these possibilities in four different ROMs allows the design to perform the multiplication process without any real multiplier.

From Eq. 10 and 11, the digit-slicing multiplier is represented as the following:

3 4k (7) k k0 BW 2 WB 2        (21) 3 j k k, j j0 WB 2 WB    (22)
where, WB k,j are all either ones or zeros except for WB k=b-1,j=p-1 which is zero or minus one and where W is the constant.

The result of the multiplication will be added and subtracted with the complex inputs A r +jA i for the butterfly to perform the butterfly outputs. The butterfly output X has been defined as:

b1 pk (pb 1) k k0 X 2 X 2         (23) p1 j k k, j j0 X 2 X     (24)
where, X k,j are all either ones or zeros except for X k=b-1,j=p-1 which is zero or minus one. By applying Eq. 17, 19 and 21 into Eq. 3: For the addition and subtraction, the parallel-prefix Koggie and Stone Ling adder were used for high speed and better performance. The pipeline technique was applied for the full design for better performance.

33 4k (pb 1) 4k (pb 1) kk k 0 k 0 3 4k (pb 1) k k0 k k k X A WB 2 X 2 2 A 2 2 WB 2 X A WB                            k k rk ik rk k r k ik k i k X is complex number X X jX

RESULT

Two different modules were implemented for radix-2 DIT butterfly. The first module uses the conventional architecture for the butterfly where the twiddle factors are stored in ROM and called by the butterfly to be multiplied with the inputs by utilising the dedicated high speed multiplier equipped with the Virtex-II FPGA. The other module uses the pipelined digit-slicing single constant multiplier-less architecture to perform the multiplication with the twiddle factor. Both modules were built and tested in MATLAB as indicated in Fig. 9 and 10, and is then coded in Verilog and synthesized by using the XST-Xilinx Synthesis Technology tool. The target FPGA was Xilinx Virtex-II XC2V500-6-FG456 FPGA. The ModelSim simulation result of pipelined digit-slicing multiplier-less radix-2 DIT butterfly is shown in Fig. 12 and 13, while the synthesis results for the two models are presented in Table 1, which demonstrates the hardware specifications for the design.

CONCLUSION

This study presented an on-chip implementation of pipeline digit-slicing multiplier-less butterfly for FFT structure. The implementation has been coded in Verilog hardware descriptive language and was tested on Xilinx Virtex-I1 XC2V500-6-FG456 prototyping FPGA board. A maximum clock frequency of 549.75 MHz has been obtained from the synthesis report for the pipeline digit-slicing multiplier-less butterfly that is 2.77 time faster than the conventional butterfly. It can be concluded that on-chip implementation of pipeline digit-slicing multiplier-less butterfly for FFT structure is an enabler in solving problems that affect communications capability in FFT and possesses huge potentials for future related works and research areas.

Fig. 1 :

 1 Fig. 1: Butterfly structure.

Fig. 3 :

 3 Fig. 3: Radix-2 DIT FFT Butterfly Architecture.

Fig. 4 :

 4 Fig. 4: Complex multiplier structure

14 )Fig. 6 :

 146 Fig. 6: The digit-slicing first algorithm for -0.65625

  p1

Fig

  Fig. 9: Digit-Slicing Single Constant Multiplier (DSSCM) Structure. b1 pk (pb 1) k k0 A 2 A 2        

  -slicing single constant multiplier-less has been designed and tested in MATLAB as shown in Fig 10 and 11, of which the result is then compared with the normal multiplier.

Fig. 10 :

 10 Fig. 10: MATLAB design of Digit-Slicing Single Constant Multiplier-Less for the Butterfly.

Fig. 11 :

 11 Fig. 11: MATLAB design of Digit-slicing Butterfly.

  It indicates the maximum clock frequency of 549.75 MHz for Pipelined digit-slicing Multiplier-less Butterfly as well as the Pipelined Digit-slicing Single Constant Multiplier-less for the butterfly with a performance of the maximum clock frequency of 609.980 MHz. Meanwhile, Fig. 14 and 15 shows the RTL schematic for the Pipeline Digit-Slicing Single Constant Multiplier-less for the Butterfly.

Fig. 14 :

 14 Fig. 14: RTL schematic for the Pipeline Digit-slicing Single Constant Multiplier-Less for the Butterfly.

Fig. 15 :

 15 Fig. 15: RTL schematic for the Pipeline Digit-slicing Single Constant Multiplier-Less Lookup table (ROM) for the Butterfly.

Table 1 :

 1 Hardware specifications of the digit-slicing butterfly

	Xilinx Virtax-II	Total equivalent gate Maximum
	FPGA XC2v250-6FG456	count for design	Frequency MHz
	Conventional butterfly	18.408	198.987
	Pipeline Digit-Slicing	31.159	549.750
	Multiplier-less Butterfly
	Conventional 16 bits	4.131	220.160
	Multiplier
	Pipeline Digit-Slicing Single	6.483	609.980
	Constant Multiplier-Less
	16 bits for the butterfly


Yazan Samir
email: yazansamir@yahoo.com

Rozita Teymourzadeh
email: rozita_teymourzadeh@yahoo.com

Ieee Member

THE EFFECT OF THE DIGIT SLICING ARCHITECTURE ON THE FFT BUTTERFLY

Keywords: -Digit-Slicing technique, Fast Fourier Transform (FFT), Verilog HDL, Xilinx

Most communications systems tend to achieve bandwidth, power and cost efficiencies to capable to describe modulation scheme. Hence for signal modulation orthogonal frequency division multiplexing (OFDM) transceiver is introduced to cover communications demand in four generation. However high performance Fast Fourier Transforms (FFT) as a main heart of OFDM acts beyond the view. In order to achieve capable FFT, design and realization of its efficient internal structure is key issues of this research work. In this paper implementation of high performance butterfly for FFT by applying digit slicing technique is presented. The proposed design focused on the trade-off between the speed and active silicon area for the chip implementation. The new architecture was investigated and simulated with the MATLAB software. The Verilog HDL code in Xilinx ISE environment was derived to describe the FFT Butterfly functionality and was downloaded to Virtex II FPGA board.

INTRODUCTION

With the increasing use of transceiver in communication system the usage of and requirement for signal processing has increased. Among the digital signal processing block FFT is the most critical processor to transfer one function into another, which is called the frequency domain representation, or simply the Discrete Fourier Transform (DFT) of the original time domain. DFT is the main and important procedure in the data analysis, system design and implementation [START_REF] Oppenheim | Discrete-Time Signal Processing[END_REF]. In order to reduce the complexity computation of the FFT algorithm many modules have been designed and implemented in different platforms. These modules focus on radix order or twiddle factor to perform a simply and efficient algorithm which includes the higher radix FFT [START_REF] Bergland | A radix-eight fast-Fourier transform subroutine for real-valued series[END_REF], the mixed-radix FFT [START_REF] Singleton | An algorithm for computing the mixed radix fast Fourier transform[END_REF], the prime-factor FFT [START_REF] Kolba | A prime factor FFT algorithm using high-speed convolution[END_REF], the recursive FFT [START_REF] Varkonyi-Koczy | A recursive fast Fourier transform algorithm[END_REF], low-memory reference FFT [START_REF] Wang | Novel memory reference reduction methods for FFT implementation on DSP processors[END_REF], Multiplier-less based FFT [7, 8, and 9] and application-specific integrated circuits (ASIC) system such as [START_REF] Baas | A low-power, high-performance, 1024-point FFT processor[END_REF]. ASIC-based system can fit real application for low-power or high performance; however, it is very solid to modify the function [START_REF] Hsu | Parallel-computing approach for FFT implementation on digital signal processor (DSP)[END_REF]. The study of the digit slicing technique has been dealt by [12, 13, and 14] for the digital filters. The design and implementation of Digit slicing FFT has been discussed one time before in [START_REF] Samad | Implementation of a High Speed Fast Fourier Transform VLSI Chip[END_REF]. This paper proposed the similar idea with [START_REF] Samad | Implementation of a High Speed Fast Fourier Transform VLSI Chip[END_REF] by using a different algorithm and different platform which help to improve the performance and get higher speed. Recently, FPGAs has become an applicable option to direct hardware solution performance in the real time application. In this paper, digit slicing architecture was proposed to design the digit-slicing butterfly. Which is a portion of the computation that combines the results of smaller discrete Fourier transforms into a larger DFT. The FFT butterfly multiplication is the most crucial part in causing the delay in the computation of the FFT. In view of the fact, the twiddle factors in the FFT processor was known in advance hence we proposed to use the digit slicing multiplier to replace with conventional multiplier in FFT butterfly. The paper structure was organized as follow; section 2 describes the FFT architecture in brief, whilst section 3 explains the butterfly conventional architecture. The digit slicing architecture will be discussed in section 4 followed by section 5 that proposes the design of digit slicing butterfly architecture in detail. Finally section 6 and 7 shows implementation result and conclusion respectively.

FAST FOURIER TRANSFORM (FFT)

A useful method to transform domain from the time domain to the frequency domain and the reverse for the implementation on digital hardware is the discrete Fourier transform (DFT). For N-point DFT of a complex data sequence x (n) is defined in equation (1).

) 1 ( 1 ,......., 1 , 0 , ) ( ) ( 1 0       N k W n x k X N n kn N
Where x(n) and X(k) are complex numbers, and

N j kn N e W / 2  
is the twiddle factor. The DFT of N-point finite sequence represents harmonically related frequency components of x(n). The direct computation of equation (1) requires the order of N 2 operations where N is the transform size. In 1965, Cooley and Tukey have found the new technique to reduce the order of complexity operations of DFT from N 2 to (Nlog 2 N). Consequently, a huge number of FFT algorithms have been developed such as Radix-2, radix-4 and split radix algorithms. These algorithms mostly used for practical applications due to their simple structure and constant butterfly geometry. In general, higher-radix FFT algorithm has fewer numbers of complex multiplications whereas radix-2 FFT algorithm is the simplest form in all FFT algorithms. Furthermore, it has a regularity that makes it suitable for VLSI implementation as shown in the fallowing equation (2).

) 2 ( ] 1 2 [ ] 2 [ ] [ 1 2 0 2 1 2 0 2          N n nm N m N N n nm N W n x W W n x m X
FFT algorithm relies on a divide and conquers methodology, which divides the N coefficient points into smaller blocks in different stages. The first stage computes with groups of two coefficients, yielding N/2 blocks, each computing the addition and subtraction of the coefficients scaled by the corresponding twiddle factors, called a butterfly for its cross-over appearance. These results are used to compute the next state of N/4 blocks, which will then combine the results of two previous blocks, combining 4 coefficients at this point. This process is repeated until we have one main block, with a final computation of all N coefficients [START_REF] Benhamid | FPGA Implementation of a Canonical Signed Digit Multiplier-less based FFT Processor for Wireless Communication Applications[END_REF].

CONVENTIONAL BUTTERFLY ARCHITECTURE

The conventional radix-2 DIT butterfly architecture is consisting of complex data I/O, complex multiplier and finally complex adder and subtractor Fig. 1.

Consider A and B are the complex input data, the complex twiddle factor considered as W = Wr -jWi.

Finally the complex output are X and Y. The index r and i represent the real and imaginary parts respectively.

) 4 ( ) 3 ( r N r N W B A Y W B A X         ) 6 ( ) ( ) ( ) ( ) ( ) 5 ( ) ( ) ( ) ( ) ( jBi Br jWi Wr jAi Ar jYi Yr jBi Br jWi Wr jAi Ar jXi Xr               Figure 1. Radix-2 DIT FFT Butterfly Architecture
The implementation of the complex multiplier required four real multipliers and two real adders Fig. 2. The complex multiplier was determined equation [START_REF] Hsu | Parallel-computing approach for FFT implementation on digital signal processor (DSP)[END_REF].

) 7 ( )] ( ) [( )] ( ) ( ) ( ) ( Wr jBi jWi Br Wi Bi Wr Br jWi Wr jBi Br           
The real and imaginary parts of the multiplication result is

)] ( ) [( Wi Bi Wr Br    and )] ( ) [( Wr jBi jWi Br   
respectively.

Figure 2.

The Complex Multiplier Structure.

The complex adder is required two real adders to perform addition functionality.

) 8 ( ) ( ) ( ) ( ) ( Bi Ai j Br Ar jBi Br jAi Ar       

DIGIT SLICING ARCHITECTURE

The concept behind the digit slicing architecture is any binary number can be sliced into a few blocks of shorter binary numbers, with each block carrying a different weight. In this paper, the fixed-point 2's complements arithmetic has been chosen to represent the input data, which are singed numbers with absolute value less than one. The absolute value of the input data x with length of B bits (x 0 ,x 1 ,x 2 ,….,x B-1 ) has been represented in 2's complement as:

) 9 ( 2 1 0      B k j j x x
To represent the sliced data, there are many different algorithms. Depend on the data type and word length, different structures can be introduced. In this paper, the fundamental sliced algorithm will be presented as following:

) 10 ( 2 2 ) 1 ( 1 0             pb b k k pk X x
Where x is sliced into b blocks and p is bit widths per block.

) 11 ( 2 1 0 ,     p j j k j k X X
Where X k,j are all either ones or zeros except for X k=b-1,j=p-1 which is zero or minus one. This algorithm (6 and 7) applies when the sliced data word length is 2 2 such as 4, 8, 16, ect. bits. Another algorithm to represent the sliced data with word length 2 2 +1 such as 5, 9, 17, ect. bits can be dealt as following: Where x is a decimal number whose absolute value is less than one, and is sliced into b blocks each of p bits wide. The most significant block is k = 0 and this contains only the sign bit of x plus leading dummy zeros to make up a block of length p bits [START_REF] Samad | Implementation of a High Speed Fast Fourier Transform VLSI Chip[END_REF].

only or X k 1 0 0    ) 13 ( . 0 1 0 ; 2 1 0 , ,       k for only or X X X p j j k j k j k
As a comparison between the first and the second example, the second algorithm required one extra block to deal with the sign bit only this makes the design more complicated and requires more hardware for the implementation. In this paper, the first digit-slicing algorithm has been chosen to build the digit-slicing FFT butterfly structure. Therefore, any complex numbers, F, can be sliced into smaller blocks b, each having a shorter word length, p, as illustrated in following equations:

) 15 ( 2 2 2 2 ) 14 ( ) 1 ( 1 0 ) 1 ( 1 0                           pb b k k I pk pb b k k R pk I R F j F F F j F F ) 16 ( 2 2 1 0 , 1 0 ,         p j j k I j k I p j j k R j k R F F and F F
Where F Ik,i and F Rk,I have values which are either zero or one.

DIGIT SLICING BUTTERFLY ARCHITECTURE

The novel butterfly architecture was designed and investigating accordingly. In order to reduce the complexity computation and enhanced the throughput, digit slicing butterfly obtained by applying the digit slicing technique. As mentioned in section 3 the butterfly structure contains of one complex multiplier, one complex adder and one complex subtractor. The digit slicing architecture has been applied for the butterfly input to slice the data to four groups each carrying four bits as shown in Fig. 3.

Figure 3. Digit Slicing Structure

The multiplication regarded as the most important operations for most signal processing systems, but it complex and expensive operation. Many techniques have been introduced for reducing the size and improving the speed of multipliers. Since the twiddle factor in FFT processor are known in advanced a special design of digit slicing multiplier has been proposed to perform the multiplication with the twiddle factor. The digit slicing architecture has been applied for the input data and sliced to four groups each has four bits to be multiplied by the constant W = Wr -jWi 16 bits 2's complement fixed point, which has absolute value less than one to represent the FFT twiddle factor. By applying equation (10 and 11) to equation (5 and 6) the digit slicing butterfly output will be:

) ( ) ( ) ( ) ( jBi Br B and jAi Ar A jYi Yr Y and jXi Xr X        
By slicing the input data A and B into b blocks each carrying p bits wide.

                1 0 , ) 1 ( 1 0 2 2 2 p j j k j k pb b k k pk A A where A A
Where A k,j are all either ones or zeros except for A k=b-1,j=p-1 which is zero or minus one. The same for the input B

                1 0 , ) 1 ( 1 0 2 2 2 p j j k j k pb b k k pk B B where B B
Where B k,j are all either ones or zeros except for B k=b-1,j=p-1 which is zero or minus one. The output X has been defined as:

                1 0 , ) 1 ( 1 0 2 2 2 p j j k j k pb b k k pk X X where X X
Where X k,j are all either ones or zeros except for X k=b-1,j=p-1 which is zero or minus one. Putting all the slicing equations above into equation ( 3)

) 17 ( 2 2 2 2 2 2 ) 1 ( 1 0 ) 1 ( 1 0 ) 1 ( 1 0 r N k k k r N pb b k k pk pb b k k pk pb b k k pk r N W B A X W B A X W B A X                                          r N k ik r N k k rk ik rk k k W B X of part ag and W B A X of part al jX X X number complex is X        

Im Re

Same step for output X has been applied to get output Y

W B A Y                                     ) 1 ( 1 0 ) 1 ( 1 0 ) 1 ( 1 0 2 2 2 2 2 2 ) 18 ( r N k k k W B A Y    r N k ik r N k k rk ik rk k k W B Y of part ag and W B A Y of part al jY Y Y number complex is Y        Im Re
Finally, the complex output has been represented as following:

) 20 ( ) 19 ( Wi B Wr B A X Wi B Wr B A X rk ik ik ik ik rk rk rk           ) 22 ( ) 21 ( Wi B Wr B A Y Wi B Wr B A Y rk ik ik ik ik rk rk rk          
The constant twiddle factor was stored in look-up table ROM.

IMPLEMENTATION RESULT

Two different modules have been implemented for radix-2 DIT butterfly. The first module uses the conventional architecture for the butterfly where the twiddle factors are stored in ROM and called by the butterfly to be multiplied with the inputs using the dedicated high speed multiplier equipped with the Virtex-II FPGA and the other module uses the digit slicing multiplier-less architecture to ModelSim simulation result of digit slicing radix-2 DIT butterfly is shown in Fig. 5, while the synthesis results for the two models are presented in Table 1, which demonstrates the hardware specifications for the design. It shows the maximum throughput of 535.90 MHz for the mentioned system. As well as the digit slicing multiplier has performed the maximum throughput of 609 MHz.

CONCLUSION

paper presented design and implementation of digit slicing butterfly for FFT structure. The implementation has been coded in Verilog hardware descriptive language and was tested on Xilinx Virtex-I1 XC2V500-6-FG456 prototyping FPGA board. A maximum clock frequency of 535.90 MHz has been obtained from the synthesis report for the digit slicing butterfly.

  with the twiddle factor. Both modules has been built and tested in MATLAB Fig.4, then coded in Verilog and synthesized using the XST -Xilinx Synthesis Technology tool. The target FPGA was Xilinx Virtex-II XC2V500-6-FG456 FPGA[17].

Figure 4 .Figure 5 .

 45 Figure 4. MATLAB design of Digit Slicing Butterfly

TABLE 1 .

 1 HARDWARE SPECIFICATIONS OF THE DIGIT-SLICING BUTTERFLY Xilinx Virtax-II

		Total equivalent	Maximum
	FPGA XC2v250-6FG456	gate	Frequency MHz
	Conventional butterfly	18,408	198.987
	Digit-Slicing Butterfly	31,159	535.90
	Conventional 16 bits Multiplier	4,131	220.16
	Digit-Slicing 16 bits Multiplier	6,483	609.60


Rozita Teymourzadeh

Yazan Samir Algnabi

Md Masuri Othman

Mok Shabiul Islam

Mok Vee Hong

VLSI Implementation of Novel Class of High Speed Pipelined Digital Signal Processing Filter for Wireless Receivers

Keywords: ASIC, CIC, CMOS, FPGA, sigma delta modulator, silterra, virtex, Xilinx

come

L'archive ouverte

INTRODUCTION

The most popular ADC converters are realized based on the use of over sampling and sigma-delta (∑Δ) modulation techniques followed by decimation process [START_REF] Ritoniemi | A Stereo audio sigma-delta ADconverter[END_REF]. Oversampled Sigma delta (∑Δ) modulator provides high resolution sample output in contrast to the standard Nyquist sampling technique. However at the output, the sampling process is needed in order to bring down the high sampling frequency and obtain high resolution. The CIC filter is a preferred technique for this purpose. A 3rd order sigma-delta ADC with a five bit data stream output is considered. The dynamic range required is 98 dB which can be achieved by efficient decimation system after applying oversampling technique.

The objective of this study is the on-chip implementation of novel class of high speed CIC filter designed for 5 bits data stream input, from 3rd order sigma delta modulator adapted for multi-standard wireless receiver. This filter performs both filtering of the out of band quantization noise and prevents excess aliasing introduced during sampling rate decreasing. Furthermore, in order to save power consumption and high speed implementation, computation complexity should be relaxed based on filter order and number of output bit.

For the first time in 1981, Hogenauer (1998) invented a new class of economical digital filter for decimation called a Cascaded Integrator Comb filter (CIC) or recursive comb filter. This filter worked with sampling frequency of 5 MHz. The introduced CIC filter did not required storage for filter coefficients and multipliers as all coefficients are unity [START_REF] Park | Principles of sigma-delta modulation for analog-to-digital converters[END_REF]. Furthermore its on-chip implementation is efficient because of its regular structure consisting of three basic building blocks, minimum external control and less complicated local timing is required and its change factors is reconfigurable with the addition of a scaling Abu-Al-Saud and Stuber ( 2003), CIC filter structure was slightly modified to enhance its sample rate conversion performance at the expense of requiring a few extra computations. However, it is still necessary to design new algorithm in terms of high performance requirement. Later, [START_REF] Mortazavi | A comparative study and design of decimation filter for high-precision audio data converters[END_REF] proposed recursive CIC filter with 120 dB stop-band attenuation and less than 0.0003 pass-band ripples. The CIC filter functionality was well described in bit-serial and bitparallel arithmetic in this research work. [START_REF] Wang | Design of CIC filter and DFC used in energy metering IC[END_REF], in 2009 presented principles of CIC filter which was used in energy calculations. They proposed a new structure of third order CIC decimation filter for electric power metering chip application. In the mentioned design, saving hardware resources and cost reduction was the main concern.

Similar work through the years 2005-2010 also presented [START_REF] Shahana | Polyphase implementation of non-recursive comb decimators for sigma-delta A/D converters[END_REF][START_REF] Dolecek | On Design of CIC decimation filter with improved response[END_REF][START_REF] Sun | A down-sample design under special condition in high-speed all-digital system[END_REF][START_REF] Mortazavi | Experimental evaluation of different realizations of recursive CIC filters[END_REF], to show the efforts that engineers put to increase the CIC filter efficiency for four Generation (4G) filter applications. However, there are inadequate resources regarding high performance decimation filters and enhancement of CIC filter performance is still a challenging task.

Consequently, this study focused on the chip implementation of novel algorithm of five order high speed CIC filters with finite-precision effect and adaptive filter time varying systems. In order to reduce filter calculations and decrease active core area for 4G wireless communication applications, high speed adder was designed and implemented based on carry lookahead adder (CLA) equations. ASIC realization of proposed CIC filter leads us to optimize filter functionality such as power consumption and active core area.

Development of a decimation filter:

The purpose of the CIC filter is twofold; firstly to remove filtering noise which could be aliased back to the base band signals and secondly to convert high sample rate m bit data stream at the output of the Sigma-delta modulator to n bit data stream with lower sample rate. This process is also known as decimation which is essentially performing the averaging and a rate reduction functions simultaneously. Figure 1 shows the decimation process using CIC filter.

The two half band filters [START_REF] Brandt | A low-power, areaefficient digital filter for decimation and interpolation[END_REF] are used to reduce the remain sampling rate reduction to the Nyquist output rate. First half band filter and second half band filter make the frequency response flatter and sharper similar to the ideal filter frequency response. Droop correction filter is allocated to compensate pass band attenuation which is created by the CIC filter. A sample of the frequency response of overall decimation process is given as Table 1.

As shown in Table 1, the final frequency bandwidth of overall decimation system can satisfy audio application whereas 4G wireless communication requires wider band width and lower oversampling ratio with dynamic range of 98 dB. Hence it is the motivation to design novel class of high speed CIC filter to be applied in DSP block of transceiver.

Principle of CIC filter structure:

The CIC filter consist of N stages of integrator and comb filter which are connected by a down sampler stage as shown in Fig. 1 in z domain. The CIC filter has the following transfer function:

RM N RM 1 N N k N IC 1N k0 (1 z ) H(z) H (z).H (z) ( z ) (1 z )            (1)
Where: N = The number of stage M = The differential delay R = The decimation factor In this project, N, M and R have been chosen to be 5, 1 and 16 respectively to avoid overflow in each stage.

N, M and R are parameters to determine the register length requirements necessary to assure no data loss. Equation 1 can be expressed as follows:

  NN (RM 1) N RM 1 RM 1 k k k k 0 k 0 k 0 NN RM 1 RM 1 k N k 0 k 0 H(z) h(k)z z z z 1 RM                                     (2)
From the Eq. 2, the maximum register growth/width, G max can be expressed as:

  N max G RM  (3)
In other words, G max is the maximum register growth and a function of the maximum output magnitude due to the worst possible input conditions [START_REF] Hogenauer | An economical class of digital filters for decimation and interpolation[END_REF]. If the input data word length is B in , the Most Significant Bit (MSB) at the filter output, B max is given when M is equal to1:

max 2 in B [Nlog R B 1]    (4)
In order to reduce the data loss, normally the first stage of the CIC filter has maximum number of bit compared to the other stages. Since the integrator stage works at the highest oversampling rate with a large internal word length, decimation ratio and filter order increase which resulted in more power consumption and speed limitation.

Proposed filter architecture:

The new algorithm of proposed CIC filter with dynamic range of 98 dB is investigated. The new algorithm was applied as linear adaptive filter. The filter is capable to involve both order-update and time-update recursions. The new adaptive filter distinguishes itself by virtue of order updates which are made possible by exploiting the time-shifting property of uniformly sampled temporal data. The designed filter is known collectively as fast algorithm because its computational complexity increases linearly with the number of adjustable parameter and more demanding in code terms.

Truncation for low power and high speed:

Truncation means estimating and removing Least Significant Bit (LSB) to reduce the area requirements on chip and power consumption and also increase speed of calculation. Although this estimation and removing introduces additional error, the error can be made small enough to be acceptable for wireless communication systems. Figure 3 illustrates five stages of the CIC filter when is 25 bit B max so truncation is applied to reduce register width. Calculations and MATLB software helps to find word length in integrator and comb section respectively.

New pipelining architecture: The way to have high speed CIC filter is by implementing the pipeline filter architecture. Figure 4 shows pipeline CIC filter structure when truncation is also applied. This pipelining is different compared with normal pipeline structures. In the proposed CIC adaptive filter, no additional pipeline registers are used in integrator part. This is an important advantage of projected CIC filter because not only the system satisfies pipeline structure but also saves power consumption and reduces area on chip implementation. However, the hardware requirement is more relaxed compared with similar pipeline structures. The CIC decimation filter clock rate is determined by the first integrator stage that causes more propagation delay [START_REF] Djadi | A high throughput programmable decimation and interpolation filter[END_REF] than any other stage due to maximum number of bit. Hence it is possible to use a higher clock rate for a CIC decimation filter if a pipeline structure is used in the integrator stages, as compared to non-pipelined integrator stages. The clock rate in integrator section is R times higher than in the comb section.

Previously, the pipeline structure for CIC filter was applied just for integrator part since the maximum clock rate is determined by the integrator. The above architecture showed that the maximum throughput was increased by 60 MHz when the pipeline structure is used for all the CIC parts consisting of integrator, comb and down sampler.

Proposed high speed adder: The major technique to increase speed is by using proposed fast adder. This adder designed and implemented based on Carry Lookahead Adder (CLA). The CLA is the fast adder which can be used for speeding up purpose but the disadvantage of the CLA adder is that the carry logic is gets quite complicated for more than 4 bits hence the proposed adder is introduced to replace as adder. This high speed is due to the carry calculation in CLA. In the ripple carry adder, the most significant bit addition has to wait for the carry to ripple through from the least significant bit addition. Therefore the carry of fast adder has become the focus of research [START_REF] Ciletti | Advanced digital design with the verilog HDL[END_REF].

The 8 bit designed adder architecture is shown in Fig. 5. Its block diagram consists of 2, 4 bit module which is connected. Each previous 4 bit calculates carry out for the next carry.

The new CIC filter in this study utilizes five fast adders in integrator parts. The maximum number of bit is 25 and it is decreased in the next stages. Hence it truncated respectively to 25, 22, 20, 18 and 16 bit in each adder, left to right. Notice that each 4 bit adder provides a group propagate and generate signal, which is used by the adder Logic block.

The group Propagate P G and Generate G G of a 4 bit adder will have the following expressions: (5

) G 3 3 2 3 2 1 3 2 1 0 G g p .g p .p .g p .p .p .g     (6)
The most important equations to obtain carry of each stage have been defined as below:

1 0 0 0 c g (p .c )  (7) 2 1 1 0 1 0 0 c g (p .g ) (p .p .c )    (8) 3 2 2 1 2 1 0 2 1 0. 0 c g (p .g ) (p .p .g ) (p .p .p c )     (9) 4 3 3 2 3 2 1 3 2 1 0 3 2 1 0 0 c g (p .g ) (p .p .g ) (p .p .p .g ) (p .p .p .p .c )      (10)
Calculation of proposed adder is based on above equations. 8 bit high speed adder could be constructed continuing along in the same logic pattern, with the MSB carry-out resulting from OR and AND gates. The Verilog code has been written to implement addition. The projected adder Verilog code was downloaded to the Xilinx FPGA chip. From Xilinx ISE Virtex-5 synthesize report; it was found that the minimum clock period is 1.986 ns (Maximum Frequency is 503.449 MHz).

RESULTS

After the sigma delta modulator, the sampling rate must be reduced to the Nyquist sampling rate. This is carried out in 4-stages. The first stage involves the reduction of the sampling frequency by the decimation factor of R 0 . This is done by the proposed CIC filter. The remaining 3 stages involve the reduction of the sampling frequency by the decimation factor of R n which are carried out by the first half band, droop correction and the second half band respectively. Figure 6 illustrates the frequency response of the overall decimation filter when the decimation factor is 128.

Figure 7 creates the droop correction filter result. This filter designs a low-pass filter with pass-band having the shape of inverse of the CIC filter frequency response. Consequently it compensates the amplitude droop cause of the CIC filter. Table 2 shows the specification of proposed CIC filter and Fig. 8 creates the core layout of CIC filter on FPGA board.

As shown in Table 2, the synthesis report of Xilinx ISE environment indicates the maximum throughput of 330 MHz in filter specification. The dynamic range of proposed CIC filter is 98 dB which satisfies wireless communication transceiver systems [START_REF] Grati | Relaxed decimtion filter specifications for wireless transceivers[END_REF]. To optimize the projected CIC filter in terms of power consumption and active core area measurement ASIC implementation was performed successfully. Fig. 9 illustrates the active core layout of proposed CIC filter followed by Table 3 related to the filter specification in terms of power consumption and area measurment. It was implemented on ASIC under the Silterra and Mimos technology library which compiled the proposed design core to perform gate-level synthesis and optimization. After compiling, the netlist is created. The estimated area and power consumption result of the high speed filter in Silterra 0.18 µm and Mimos 0.35 µm technology in maximum clock frequency is shown in Table 3. The implementation of new CIC filter was done successfully and the actual data was tested by design analyzer system on FPGA board in real time.

DISCUSSION

The FPGA implementation of novel class of high speed low power Recursive CIC filters have been designed and investigated to fulfill the requirement of wireless transceiver applications. The novel CIC filter was obtained by its designed efficient architecture. To achieve high speed filter new technique was applied consequently. The special pipeline architecture, designing proposed fast arithmetic calculation unit and truncation lead us to have high speed novel CIC filter and upgrade the filter structure to achieve the maximum throughput of 332.93 MHz. The evaluation indicates that the pipelined proposed CIC filter is attractive due to high speed when both the decimation ratio and filter order are not high as stated in the Hogenauer Comb filter. Since the first stage of the CIC filter require maximum word length and also because of the recursive loop in its structure, the reduction in power consumption is limited by the throughput. Thus the truncation will reduce the power consumption and the number of calculation. The power consumption computed using CAD tools (Cadence and Synopsys) and 0.18 μm Silterra technology library. It was reported 3.14 mW power at maximum clock frequency. The ASIC core measurement calculated as 0.308×0.308 mm2 on 0.18 µm Silterra and 1.148×1.148 mm2 on 0.35 µm MIMOS technology library. The results prove high enlargement of CIC filter performance in trade-off between power and speed compare to the previous similar research work [START_REF] Shahana | Polyphase implementation of non-recursive comb decimators for sigma-delta A/D converters[END_REF][START_REF] Sun | A down-sample design under special condition in high-speed all-digital system[END_REF][START_REF] Mortazavi | Experimental evaluation of different realizations of recursive CIC filters[END_REF][START_REF] Brandt | A low-power, areaefficient digital filter for decimation and interpolation[END_REF][START_REF] Djadi | A high throughput programmable decimation and interpolation filter[END_REF]Ciletti, 2003;[START_REF] Grati | Relaxed decimtion filter specifications for wireless transceivers[END_REF].

  circuit and minimal changes to the filter timing. It is also used to perform filtering of the out of band quantization noise and prevent excess aliasing introduced during sampling rate decreasing. Hence implementing high performance CIC filter will be issue of this research work. Garcia et al. (1998) designed Residue Number System (RNS) for pipelined Hogenauer CIC. Compared to the two's complement design, the RNS based Hogenaur filter enjoys an improved speed advantage by approximately 54%. Similar structure by Meyer-Baese et al. (2005) has been implemented to reduce the cost in the Hogenauer CIC filter which shows that the filter can operate up to maximum clock frequency of 164.1 MHz on Altera FPLD and 82.64 MHz on Synopsys cell-based IC design.

Fig. 1 :

 1 Fig. 1: Digital decimation process

Fig. 2 :

 2 Fig. 2: One-stage of CIC filter block diagram

Fig. 5 :

 5 Fig. 5: The 8 bit proposed adder architecture

Fig. 6 :

 6 Fig. 6: Frequency response of overall decimation filter

Fig. 8 :

 8 Fig. 8: Core layout on FPGA board

Fig. 9 :

 9 Fig. 9: ASIC active core layout of CIC filter

Table 1 :

 1 Decimation filters specifications

		Pass band	Stop band Transition
		(kHz)	(kHz)	band (kHz)
	CIC filter	7.00	384.00	377.00
	First half band filter	32.00	170.00	138.00
	Droop correction	32.00	70.00	38.00
	Second half band filter	21.77	26.53	4.76

Table 2 :

 2 High speed pipelined CIC filter characteristic HDL synthesis report

	Design statistics
	No. of IOs		33.000
	No. of multiplexer		2.000
	No. of Xor		240.000
	No. of slices		774.000
	Timing report
	Minimum period (ns)		3.004
	Maximum frequency (MHz)		332.930
	Minimum input arrival time before clock (ns)	2.997
	Maximum output required time after clock (ns)	2.775
	Total equivalent gate count for design	5216.000
	Total memory usage (MB)		66.000
	Table 3: ASIC implementation result of CIC filter
	CIC filter specification	Silterra 0.18 µm	Mimos 0.35 µm
	Active core area (mm 2 )	0.3080.308	1.1481.148
	Power consumption (mW)	3.14	6.03