IEEE Rozita Teymourzadeh
email: rozita60@vlsi.eng.ukm.my

An Enhancement of Decimation Process using Fast Cascaded Integrator Comb (CIC) Filter

The over sampling technique has been shown to increase the SNR and is used in many high performance system such as in the ADC for audio and DAT systems. This paper presents the design of the decimation and its VLSI implementation which is the subcomponent in the over sampling technique. The design of three main units in the decimation stage that is the Cascaded Integrator Comb (CIC) filter, the associated half band filters and the droop correction are also described. The Verilog HDL code in Xilinx ISE environment has been derived to describe the CIC filter properties and downloaded in to Virtex II FPGA board. In the design of these units, we focus on the trade-off between the speed improvement and the power consumption as well as the silicon area for the chip implementation.

I. INTRODUCTION

The most popular A/D converters for audio applications 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 AD-Converter[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. In 1981, Eugene Hogenauer [START_REF] Hogenauer | An Economical Class of digital filters for Decimation and interpolation[END_REF] 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. Additionally the CIC filter does not require 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 onchip 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 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 enhanced high speed will be key issue in chip implementation of CIC decimators. In 1998, Garcia [START_REF] Garcia | Pipelined Hogenauer CIC Filters Using Field-Programmable Logic and Residue Number System[END_REF] 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 [START_REF] Meyer-Baese | Cost-effective Hogenauer Cascaded Integrator Comb Decimator Filter Design for custom ICs[END_REF] 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.

This paper shows the implementation of the high speed CIC filters which are consist of three parts, integrator, comb and down sampler. The CIC filter is considered as recursive filter because of the feedback loop in integrator circuit and it can work with maximum throughput of 190 MHz.

The next section describes the mathematical formulation and block diagram of CIC filters in detail. Enhanced high speed architecture is explained in section III. Section IV shows implementation and design result in brief. Finally conclusion is expressed in section V.

II. 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, Area-Efficient Digital Filter for Decimation and Interpolation[END_REF] are used to reduce remain sampling rate reduction to the Nyquist output rate. First half band filter and second half band filter make the frequency response more flat and sharp similar to ideal filter frequency response. Droop correction filter is allocated to compensate pass band attenuation which is created by the CIC filter. The frequency response of overall system will be shown in section V.

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

           1 0 ) ( ) 1 1 ( ) 1 ( ) ( ). ( ) ( RM k N k z N z N RM z z N C H z N I H z H (1)
where N is the number of stage, M is the differential delay and R is the decimation factor. In this paper, N, M and R have been chosen to be 5, 1 and 16 respectively to avoid overflow in each stages. From the equation, the maximum register growth/width, max G can be expressed as:

  N RM G  max (3)
In other word, max G 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 in B , most significant bit (MSB) at the filter output, max B is given by:

] 1 2 log [ max    in B R N B (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 result in more power consumption and speed limitation.

III. SPEED IMPROVEMENT A.Truncation for low power & 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

  N N RM k N RM k k N RM k k N RM k k N RM k k RM z z z z k h z H                                            1 0 1 0 1 0 1 0 ) 1 ( 0 1 ) ( ) ( (2)
ICSE2006 Proc. 2006, Kuala Lumpur, Malaysia this estimation and removing introduces additional error, the error can be made small enough to be acceptable for DSP applications. Figure 3 illustrates five stages of the CIC filter when max B is 25 bit so truncation is applied to reduce register width. Matlab software helps to find word length in integrator and comb section.

B. Pipeline structure

One way to have high speed CIC filter is by implementing the pipeline filter structure. Figure 4 shows pipeline CIC filter structure when truncation is also applied. In the pipelined structure, no additional pipeline registers are used in integrator part. So that hardware requirement is the same as in the non-pipeline [START_REF] Djadi | A high throughput Programmable Decimation and Interpolation Filter[END_REF]. The CIC decimation filter clock rate is determined by the first integrator stage that causes more propagation delay than any other stage due to maximum number of bit. So 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 nonpipelined 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 since the maximum clock rate is by the integrator. The above architecture showed that the maximum throughput was increased by 20 MHz when the pipeline structure is used for all the CIC parts consisting of integrator, comb and down sampler.

C. Modified Carry look-ahead Adder (MCLA)

The other technique to increase speed is using Modified Carry Look-ahead Adder. The Carry Look-ahead adder (CLA) is the fastest adder which can be used for speeding up purpose but the disadvantage of the CLA adder is that the carry logic is getting quite complicated for more than 4 bits so Modified Carry Look-ahead Adder (MCLA) is introduced to replace as adder. This improve in speed is due to the carry calculation in MCLA. In the ripple carry adder, most significant bit addition has to wait for the carry to ripple through from the least significant bit addition. Therefore the carry of MCLA adder has become a focus of study in speeding up the adder circuits [START_REF] Ciletti | Advanced Digital design with the Verilog HDL[END_REF]. The 8 bit MCLA structure is shown in Figure 5. Its block diagram consists of 2, 4-bit module which is connected and each previous 4 bit calculates carry out for the next carry. The CIC filter in this paper has five MCLA in integrator parts. The maximum number of bit is 25 and it is decreased in next stages. So 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 MCLA Logic block. The group Propagate P G and Generate G G of a 4bit adder will have the following expressions: The remaining 3 stages involve the reduction of the sampling frequency by the decimation factor of 2 only which are carried out by the first half band, droop correction and the second half band respectively. Figure 6 illustrate the frequency response of the overall decimation filter when the sampling frequency is 6.144 MHz. The CIC filter Verilog code was written and simulated by Matlab software. The signal to noise ratio is 141.56 dB in sigma delta modulator output and it is increased to 145.35 dB in the decimation stages. To improve the signal to noise ratio, word length of recursive CIC filter should be increased but the speed of filter calculation is also decreased.

The chip layout on Virtex II FPGA board has been shown in Figure 9.

Fig. 1

 1 Fig. 1 Digital Decimation Process

Fig. 2

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

Fig. 3

 3 Fig. 3 Five-stages of truncated CIC filter

Fig. 4

 4 Fig. 4 Five-stage of truncated pipeline CIC filter

  most important equations to obtain carry of each stage have been defined as below: Calculation of MCLA is based on above equations. 8-Bit MCLA Adder could be constructed continuing along in the same logic pattern, with the MSB carry-out resulting from OR & AND gates. The Verilog code has been written to implement addition. The MCLA Verilog code was downloaded to the Xilinx

  chip. From Xilinx ISE synthesize report, it was found minimum clock period is 3.701ns (Maximum Frequency is 270 MHz).

Fig. 5

 5 Fig. 5 The 8 bit MCLA structure

Fig. 6 Figure 7 Fig. 7 :

 677 Fig. 6 The frequency response of overall decimation filter

Fig. 8

 8 Fig. 8 Signal spectra (a) Output sigma delta modulator SNR (b) Output CIC filter SNR

Fig. 9

 9 Fig.9The core layout on FPGA board

REFERENCE


Daniel Benedikovic
email: daniel.benedikovic@u-psud.fr

Carlos Alonso-Ramos

Pavel Cheben

Jens H Schmid

Shurui Wang

Dan-Xia Xu

Boris Lamontagne

Jean Lapointe

Siegfried Janz

Robert Halir

Alejandro Ortega-Moñux

Juan-Gonzalo Wangüemert-Pérez

Inigo Molina-Fernández

Jean-Marc Fédéli

Milan Dado

Laurent Vivien

Fiber-chip surface grating couplers engineered by nanophotonic sub-wavelength grating metamaterials

teaching and research institutions in France or abroad, or from public or private research centers.

We have demonstrated by both designs and experiments a set of different fiber-chip surface grating couplers engineered by sub-wavelength grating metamaterials, requiring only a one step of lithography patterning and reactive ion etching, while providing the state-of-the-art fiber-chip coupling performance [START_REF] Halir | Waveguide sub-wavelength structures: a review of principles and applications[END_REF][START_REF] Halir | Continuously apodized fiber-to-chip surface grating coupler with refractive index engineered subwavelength structure[END_REF][START_REF] Benedikovic | High-efficiency single etch step apodized surface grating coupler using subwavelength structure[END_REF][START_REF] Benedikovic | Single-etch subwavelength engineered fiber-chip grating couplers for 1.3 µm datacom wavelength band[END_REF][START_REF] Benedikovic | Subwavelength index engineered surface grating coupler with sub-decibel efficiency for 220-nm silicon-on-insulator waveguides[END_REF][START_REF] Alonso-Ramos | Fiber-chip grating coupler based on interleaved trenches with directionality exceeding 95%[END_REF][START_REF] Benedikovic | High-directionality fiber-chip grating coupler with interleaved trenches and subwavelength index-matching structure[END_REF]. In particular, we have reported on apodized single-etch grating couplers with optimized thin film interference pattern. Those grating couplers are implemented in a conventional 220-nm-thick silicon photonics platform, with a coupling efficiency of up to -2.2 dB and -2.5 dB for wavelengths near 1.55 and 1.3 μm, respectively [START_REF] Benedikovic | High-efficiency single etch step apodized surface grating coupler using subwavelength structure[END_REF][START_REF] Benedikovic | Single-etch subwavelength engineered fiber-chip grating couplers for 1.3 µm datacom wavelength band[END_REF][START_REF] Benedikovic | Subwavelength index engineered surface grating coupler with sub-decibel efficiency for 220-nm silicon-on-insulator waveguides[END_REF]. In addition, a sub-decibel fiber-chip coupling efficiency of -0.70 dB has been experimentally realized by utilizing the CMOS-compatible manufacturing via backside metallization [START_REF] Benedikovic | Subwavelength index engineered surface grating coupler with sub-decibel efficiency for 220-nm silicon-on-insulator waveguides[END_REF].

We have also developed a flexible grating coupler concept with an ultra-high intrinsic directionality. The grating couplers can be fabricated by using only two, deep and shallow, etching levels, typically used in silicon photonic foundries [START_REF] Alonso-Ramos | Fiber-chip grating coupler based on interleaved trenches with directionality exceeding 95%[END_REF][START_REF] Benedikovic | High-directionality fiber-chip grating coupler with interleaved trenches and subwavelength index-matching structure[END_REF]. This coupling structure obviates the need of using typically complex fabrication processes such as high-index overlays, customized etch depths, and bottom mirrors. In particular, we have shown that the blazing effect can directly be implemented in any conventionally used silicon-on-insulator substrates, with a negligible dependence on the thickness of the BOX layer. We reported an experimental coupling efficiency of -1.3 dB near 1.55 μm in a standard 220-nm-thick silicon platform [START_REF] Benedikovic | High-directionality fiber-chip grating coupler with interleaved trenches and subwavelength index-matching structure[END_REF].

Figure :

 : Figure: Single-etch step apodized surface grating couplers in (a) linearly-tapered and (b) curved layout configurations, and subwavelength grating nanostructure inside the trenches. (c) Optical micrograph image of the surface grating couplers layout with metal reflector underneath. (d) Dual-etch surface grating coupler with interleaved deep and shallow etched trenches and subwavelength grating index-matching region.


Rim Kalaï
email: kalai@lamsade.dauphine.fr

Claude Lamboray
email: clambora@ulb.ac.be

L'α-robustesse lexicographique : une relaxation dela β -robustesse

Keywords: α-robustesse lexicographique, β-robustesse Lexicographic α-robustness, β-robustness

Dans ce papier, nous nous intéressons à deux approches de robustesse : d'un côté une approche fondée sur la quasi-optimalité que nous appellerons dans cet article la β-robustesse et d'un autre côté l'α-robustesse lexicographique. Nous mettons en évidence quelques propriétés communes aux deux approches. En outre, nous établissons un lien entre la β-robustesse et l'α-robustesse lexicographique qui montre que la seconde approche peut être considérée comme une relaxation de la première.

Introduction

Pour répondre à la préoccupation de robustesse, des approches extrêmement variées peuvent être envisagées. Nous nous intéressons ici à une forme de réponse particulièrement étudiée dans la littérature actuelle illustrée notamment dans [START_REF] Bertsimas | Robust discrete optimization and network flows[END_REF][START_REF] Gupta | Robustness in sequential investment decisions[END_REF][START_REF] Kalaï R | Robust 1-median location problem on a tree[END_REF][START_REF] Kouvelis | Robust Discrete Optimization and its Applications[END_REF][START_REF] Mulvey | Robust optimization of largescale systems[END_REF][START_REF] Perny | An axiomatic approach to robustness in search problems with multiple scenarios[END_REF][START_REF] Rosenblatt | A robustness approach to facilities design[END_REF]. Ces approches se divisent en deux grandes familles : celles qui se basent sur l'optimisation d'un critère de robustesse et celles qui imposent des conditions de robustesse qu'une solution doit vérifier pour être considérée comme robuste [START_REF] Aloulou | Une nouvelle approche de robustesse : α-robustesse lexicographique[END_REF]. Dans ce travail, nous nous intéressons à deux approches de robustesse appartenant à la seconde famille. Nous nous limitons au cas où l'incertitude est représentée par un ensemble discret et fini de scénarios.

Dans la première approche, une solution est dite robuste si elle n'est pas très loin de l'optimum quel que soit le scénario considéré. Cette mesure de robustesse a été initialement introduite par Kouvelis et al. dans le cadre du problème d'aménagement d'usine [START_REF] Kouvelis | Algorithms for robust single and multiple period layout planning for manufacturing systems[END_REF]. Les auteurs cherchent à déterminer les solutions dont le coût est à moins de (100 + p)% de celui de la solution optimale pour tous les scénarios, p étant un réel positif fixé. Les solutions robustes sont donc celles dont le regret relatif est inférieur à p%. Dans [START_REF] Snyder | Facility location under uncertainty : A review[END_REF], Snyder appelle cette mesure de robustesse la p-robustesse. Ce concept de robustesse basé sur la proximité de l'optimum a été également repris par Gutiérrez et al. dans le cas du problème de conception de réseaux (network design problem) [START_REF] Gutiérrez | A robustness approach to uncapacitated network design problem[END_REF] et du problème d'approvisionnement international (international sourcing) [START_REF] Gutiérrez | A robustness approach to international sourcing[END_REF], ainsi que par Mulvey et al. en programmation mathématique [START_REF] Mulvey | Robust optimization of largescale systems[END_REF].

La seconde approche se fonde sur le fait qu'en situation d'incertitude pure, aucun scénario ne peut être distingué et donc l'ordre des scénarios n'a pas d'importance. Remarquons que l'ordre des scénarios n'a pas d'importance non plus dans la première approche. Néanmoins, la seconde approche va davantage plus loin en supposant que le vecteur de performance d'une solution (représentant les valeurs possibles que prend la solution pour les différents scénarios) est équivalent à tout vecteur obtenu par permutation, notamment le vecteur obtenu en ordonnant les performances de la pire à la meilleure. Une solution est alors considérée comme robuste, selon cette seconde approche, si chacune de ses performances réordonnées est proche de l'optimum. Cette approche, appelée α-robustesse lexicographique, a été proposée par Kalaï dans [START_REF] Kalaï R | Une nouvelle approche de robustesse : application à quelques problèmes d'optimisation[END_REF] et a été appliquée au problème de localisation 1-médian [START_REF] Kalaï R | Robust 1-median location problem on a tree[END_REF] ainsi qu'aux problèmes de sac à dos [START_REF] Kalaï | Lexicographic α-robust knapsack problem : Complexity results[END_REF] et de plus court chemin [START_REF] Kalaï | Lexicographic α-robust shortest path problem[END_REF].

En plus du fait d'appartenir à la famille d'approches imposant des conditions de robustesse, plusieurs points communs existent entre ces deux approches :

• Elles cherchent un ensemble de solutions et non pas une seule solution robuste.

• Elles peuvent donner un ensemble vide de solutions robustes, à la différence des approches fondées sur l'optimisation d'un critère de robustesse, comme par exemple le critère du coût ou du regret maximal. • Elles tiennent compte de la dimension subjective de la robustesse [START_REF] Vincke | Newsletters of the European Working Group «Multicriteria Aid for Decisions[END_REF] par le biais d'un seuil d'indifférence à fixer par le décideur. En effet, ce paramètre traduit la perception du décideur d'être "proche de l'optimum".

• Elles considèrent tous les scénarios pour déterminer les solutions robustes, à la différence de l'approche minmax qui ne tient compte que du pire scénario.

Le but de ce travail est de mettre en relation ces deux approches ayant des philosophies similaires. Par souci d'homogénéité et vu que la p-robustesse fait appel à un seuil relatif alors que la α-robustesse lexicographique utilise un seuil absolu, nous proposons de comparer cette dernière avec l'approche qui considère qu'une solution est robuste si son regret absolu (non relatif) est inférieur à un seuil β pour tous les scénarios. Nous appelons cette dernière approche la β-robustesse. Soulignons que la β-robustesse et la p-robustesse reflètent le même concept de robustesse, la seule différence réside dans le choix de la nature du seuil (absolu ou relatif).

Le reste de l'article est organisé comme suit. Dans la section 2, nous introduisons les notations utilisées le long de cet article ainsi qu'un exemple illustratif. La section 3 est dédiée à certaines propriétés vérifiées par les deux approches. Un lien entre la βrobustesse et la α-robustesse lexicographique est établi dans la section 4. La section 5 est consacrée aux conclusions.

Notations et exemple 2.1 Notations

Nous considérons un ensemble fini de solutions ou d'alternatives, X = {x 1 , x 2 , . . . , x n } et un nombre fini de scénarios S, avec |X| = n et |S| = q. Chaque alternative x ∈ X est évaluée pour le scénario s par une fonction f s (x) (par exemple le coût). Sans perte de généralité, nous allons supposer que les fonctions f s (.) sont à minimiser.

Notons f (x) le vecteur d'évaluations (f s 1 (x), f s 2 (x), . . . , f s q (x)) de la solution x pour les différents scénarios. Le vecteur de désutilité de x, noté f (x), est obtenu en réordonnant f (x) de la pire (c'est-à-dire la plus grande) évaluation à la meilleure (c'est-à-dire la plus petite) évaluation. On a donc :

f1 (x) ≥ f2 (x) ≥ . . . ≥ fq (x)
Notons que le vecteur de désutilité d'une solution x introduit un préordre complet sur l'ensemble des scénarios qui dépend de la solution x considérée. Soit x * s une solution optimale pour le scénario s (elle peut ne pas être unique) :

x * s = arg min x∈X f s (x) (1)
De façon similaire, x * j est défini par rapport à la fonction fj (.) comme suit :

x * j = arg min x∈X fj (x) (2)
A partir de ces solutions, nous définissons deux nouvelles solutions notées x * et x * vérifiant :

f s (x * ) = f s (x * s ) ∀s ∈ S (3) fj (x * ) = fj (x * j ) ∀j ∈ {1, . . . , q} (4)
Si f est une fonction coût par exemple, la solution x * correspond à la solution dont le coût est minimum pour chacun des q scénarios, alors que la solution x * correspond à la solution dont le k ème plus grand coût est minimum pour tout k ∈ {1, . . . , q}. Signalons que, la plupart du temps, x * et x * ne sont pas des solutions réalisables mais correspondent à des solutions idéales. Elles jouent le rôle de points de référence auxquelles nous comparerons les solutions de X pour déterminer celles qui peuvent être considérées comme robustes.

Soient α et β deux réels positifs. Dans ce qui suit, nous allons noter :

• R β l'ensemble des solutions β-robustes défini comme suit :

R β (X) = {x ∈ X : ∀s ∈ S, f s (x) -f s (x * s ) ≤ β} (5)
• R α-lex l'ensemble des solutions α-robustes lexicographiques défini comme suit :

R α-lex (X) = {x ∈ X : ∀j ∈ {1, . . . , q}, fj (x) -fj (x * j ) ≤ α} (6)
Dans la sous-section qui suit, nous illustrons ces deux ensembles par un exemple pour que le lecteur puisse mieux se les représenter.

Exemple

Considérons l'exemple indiqué dans le tableau 1 avec

X = {a 1 , a 2 , a 3 , a 4 } et S = {s 1 , s 2 } :
Le point idéal x * de ce jeu de données correspond à la solution qui prend les valeurs 1 dans le premier scénario et 3 dans le deuxième scénario. Cette solution ainsi que celles de l'ensemble X sont représentées dans la Figure 1, où les axes correspondent aux deux scénarios. Pour une valeur de β = 4 par exemple, l'ensemble robuste R β (X) est constitué de l'unique solution a 2 . En effet, a 2 est à moins de 4 unités du point de référence à la fois pour le premier et le second scénario. Afin de calculer l'ensemble R α-lex (X), les vecteurs de performance des différentes solutions doivent être réordonnés comme le montre le Tableau 2.

s 1 s 2 f s (a 1 ) 6 3 f s (a 2 ) 4 7 f s (a 3 ) 3 10 f s (a 4 ) 1 11 f s (x * ) 1 3
TAB. 1 -Evaluations des quatre solutions pour les deux scénarios

t t t t t - 6 - 6 ? f (a 1 ) f (a 2 ) f (a 3 ) f (a 4 ) f (x * ) s 2 s 1 β = 4
FIG. 1 -Evaluation des solutions dans les deux scénarios.

j = 1 j = 2 fj (a 1 ) 6 3 fj (a 2 ) 7 4 fj (a 3 ) 10 3 fj (a 4 ) 11 1 fj (x * ) 6 1
TAB. 2 -Evaluations réordonnées des quatre solutions

- - 6 ? 6 f (a 2 ) f (a 3 ) f (x * ) f (a 4 ) j = 1 α = 2 f (a 1 ) j = 2 t t t t t

FIG. 2 -Evaluations réordonnées des solutions.

La solution x * correspond maintenant au point idéal du jeu de données réordonné. Remarquons que les nouvelles dimensions ne correspondent plus forcément à un scénario en particulier. Par exemple, f1 (a 1 ) = 6 = f 1 (a 1 ) provient du premier scénario et f1 (a 2 ) = 7 = f 2 (a 2 ) provient du deuxième scénario. Ces solutions sont représentées dans la Figure 2. Pour une valeur α = 2 par exemple, l'ensemble robuste R α-lex (X) est constitué de l'unique solution a 1 . En effet, a 1 est à moins de 2 unités du point idéal x * à la fois pour la première et la deuxième composantes.

Les Figures 1 et 2 montrent une propriété intéressante des deux approches étudiées dans cet article et évoquée dans l'introduction. Pour une valeur β < 4 (resp. α < 2), l'ensemble R β (X) (resp. R α-lex (X)) est vide. En effet, les seuils β et α expriment un niveau de tolérance fixé par le décideur pour exprimer son point de vue quant à la robustesse d'une solution par rapport au point idéal. S'il fixe un seuil trop faible et si le point de référence n'est pas une solution réalisable, il n'y aura pas de solutions robustes selon ses exigences. Nous expliciterons, dans la section 3 les seuils minimaux garantissant l'existence de solutions robustes pour les deux approches, ainsi que plusieurs autres propriétés.

Propriétés des ensembles

R β (X) et R α-lex (X)
Dans cette section, nous mettons en évidence certaines propriétés vérifiées par les deux ensembles de solutions robustes R α-lex (X) et R β (X). Pour se référer génériquement aux deux ensembles, nous les notons R ou encore R(Y ) pour spécifier qu'ils sont définis sur un sous-ensemble Y ⊆ X.

Propriété 1 Soit a ∈ X. Si f s (a) ≤ f s (x) pour tout x ∈ X et s ∈ S, alors a ∈ R(X).

Preuve:

Remarque préliminaire : Soient x et y deux solutions de X. Podinovskii démontre dans [START_REF] Podinovskii | Multi-criterion problems with uniform equivalent criteria[END_REF] que fj (x) ≤ fj (y) pour tout j si et seulement si il existe deux permutations σ et π telles que f σ(s) (x) ≤ f π(s) (y) pour tout s. En particulier, si f s (x) ≤ f s (y) pour tout s ∈ S alors ∀j ∈ {1, . . . , q}, fj (x) ≤ fj (y).

Par définition de a, f s (a) = f s (x * s ) pour tout s ∈ S. Donc a ∈ R β (X). Par ailleurs et d'après le résultat de Podinovskii, on a ∀k ≤ q, fk (a) ≤ fk (x) pour tout x ∈ X. Donc, ∀k, fk (a) = fk (x * k ) et a ∈ R α-lex (X).

On comprend bien que la propriété 1 est une propriété souhaitée dans tout ensemble de solutions robustes. En effet, s'il existe dans X une solution qui domine toutes les autres, c'est-à-dire une même solution qui est optimale dans tous les scénarios, il est évident que cette solution doit être considérée comme robuste. Dans ce cas particulier, les ensembles R β (X) et R α-lex (X) sont non vides quel que soit le seuil choisi.

Propriété 2 Les ensembles R β (X) et R α-lex (X) sont monotones respectivement par rapport à β et à α, i.e. : β ≤ β ′ ⇒ R β (X) ⊆ R β ′ (X) α ≤ α ′ ⇒ R α-lex (X) ⊆ R α ′ -lex (X) Preuve: x ∈ R β (X) ⇒ ∀s ∈ S, f s (x) -f s (x * s ) ≤ β ≤ β ′ ⇒ x ∈ R β ′ (X). x ∈ R α-lex (X) ⇒ ∀k ≤ q, fk (x) -fk (x * k ) ≤ α ≤ α ′ ⇒ x ∈ R α ′ -lex (X).
Les paramètres β et α caractérisent le degré d'exigence du décideur par rapport à une solution idéale. Il est clair que plus cette exigence est faible (et donc plus le paramètre est grand), plus il y a de solutions qui répondent aux préférences du décideur.

Il peut arriver que, pour des seuils β ou α trop petits, aucune solution dans X ne vérifie la condition de robustesse requise. Par conséquent, les ensembles R β (X) et R α-lex (X) peuvent être vides. Notons β min le seuil minimum pour lequel R β (X) est non vide et α min le seuil minimum pour lequel R α-lex (X) est non vide. Soulignons que ces seuils minimaux dépendent de l'ensemble X. En toute rigueur, ils doivent être notés β min (X) et α min (X). Néanmoins, par souci de simplicité, nous n'utiliserons ces dernières notations que s'il y a possibilité de confusion. Il est évident que, suite à la propriété de monotonie

(propriété 2), les ensembles R β (X) et R α-lex (X) restent non vides pour tout β ≥ β min et tout α ≥ α min . Proposition 1 β min = min x∈X max s∈S (f s (x) -f s (x * s )) α min = min x∈X max 1≤j≤q ( fj (x) -fj (x * j )) Preuve: x ∈ R β (X) ⇔ ∀s ∈ S, f s (x) -f s (x * s ) ≤ β ⇔ max s∈S (f s (x) -f s (x * s )) ≤ β Donc, β min = min x∈X max s∈S (f s (x) -f s (x * s )
). Pour α min , même preuve que précédemment en remplaçant f s (.) par fj (.), x * s par x * j et β par α.

De manière similaire, il existe un seuil à partir duquel chaque solution est robuste. Remarquons que, d'après la proposition 1, l'ensemble R β min (X) correspond exactement à l'ensemble des solutions optimales suivant le critère du regret maximal.

Propriété 3 Les ensembles R β (X) et R α-lex (X) vérifient la propriété suivante : Si Y ⊆ X alors R(X) ∩ Y ⊆ R(Y ) Preuve: Soient Y une partie de X et a une solution telle que a ∈ R β (X) ∩ Y . On a donc f s (a)-f s (x * s ) ≤ β, ∀s ∈ S. Posons x * s (Y ) = arg min x∈Y f s (x). Par définition de x * s , on a f s (x * s (Y )) ≥ f s (x * s ). Donc, pour tout s ∈ S, f s (a) -f s (x * s (Y )) ≤ β, ce qui signifie a ∈ R β (Y ). Idem pour R α-lex (X).
Cette propriété est appelée propriété de Chernoff [START_REF] Moulin | Choice functions over a finite set : a summary[END_REF] ou encore condition d'hérédité [START_REF] Aleskerov | Utility maximization, choice and preference[END_REF] en théorie de choix social. Elle signifie qu'une solution robuste sur un ensemble reste robuste sur une partie de cet ensemble. En d'autres termes, si une alternative n'est pas considérée comme robuste par rapport à une partie de X, elle ne peut être considérée robuste par rapport à l'ensemble X.

En particulier, si a ∈ R(X), on peut alors déduire de cette propriété que R(X) ⊆ R(X \{a}) (il suffit de considérer Y = X \{a} dans la propriété 3). Il est donc intéressant de remarquer que, lorsqu'une solution de X n'appartenant pas à l'ensemble robuste est enlevée, l'ensemble robuste risque de s'agrandir. Soulignons que cela ne se produit que si l'on enlève une solution x telle qu'il existe s pour lequel f s (x) = f s (x * s ), respectivement il existe j pour lequel fj (x) = fj (x * j ). agissant de la sorte, on modifie le point de référence. Comme les ensembles sont définis par rapport à ces points de référence, la modification de ces points influence l'ensemble des solutions robustes.

Pour résumer, si on réduit l'ensemble de solutions, une solution robuste reste robuste (si elle n'est pas enlevée) et une solution non robuste peut devenir robuste. Si, en revanche, on augmente l'ensemble de solutions, une solution initialement non robuste reste non robuste tandis qu'une solution robuste peut cesser de l'être. Cela peut même se produire lorsque l'ensemble des solutions est enrichi d'une seule solution qui ne sera pas considérée comme robuste. Imaginons que, dans l'exemple de la section 2, la solution f (a 5 ) = (8, 2) est ajoutée. Dès lors, l'ensemble des solutions β-robustes devient vide pour β = 4 alors qu'il contenait initialement la solution a 2 . D'autre part, si dans la propriété de Chernoff, on considère le cas particulier Y = R(X), il en découle le résultat suivant :

Propriété 4 R α-lex (X) et R β (X) sont idempotents, i.e. : R(R(X)) = R(X)
L'idempotence des ensembles R β (X) et R α-lex (X) implique qu'ils sont minimaux en un certain sens, puisqu'en ré-appliquant la démarche de recherche de solutions robustes à ces ensembles, on ne peut pas les réduire.

Les ensembles de solutions β-robustes et α-robustes lexicographiques vérifient une autre propriété faisant référence à deux sous-ensembles de X.

Propriété 5 Les ensembles R β (X) et R (X) vérifient la propriété suivante : ∀Y 1 , Y 2 ⊆ X, R(Y 1 ) ∩ R(Y 2 ) ⊆ R(Y 1 ∪ Y 2 ) Preuve: a ∈ R β (Y 1 ) ∩ R β (Y 2 ) ⇒ f s (a) -min y 1 ∈Y 1 f s (y 1 ) ≤ β ∀s ∈ S f s (a) -min y 2 ∈Y 2 f s (y 2 ) ≤ β ∀s ∈ S Comme min z∈Y 1 ∪Y 2 f s (z) = min{min y 1 ∈Y 1 f s (y 1 ), min y 2 ∈Y 2 f s (y 2 )}, on en déduit que f s (a) -min z∈Y 1 ∪Y 2 f s (z) ≤ β, ∀s ∈ S. Ce qui implique a ∈ R(Y 1 ∪ Y 2 ).
La preuve est similaire pour R α-lex (X). [START_REF] Moulin | Choice functions over a finite set : a summary[END_REF]. Elle signifie que si une solution est robuste sur deux sous-ensembles séparément, alors elle reste robuste sur l'union de ces deux sous-ensembles.

Cette propriété est appelée propriété d'expansion

En théorie du choix social, les propriétés de Chernoff et d'expansion sont importantes car elles caractérisent les fonctions de choix rationalisables par une relation ayant une partie asymétrique acyclique (voir théorème de Sen [START_REF] Moulin | Choice functions over a finite set : a summary[END_REF][START_REF] Sen | Choice functions and revealed preferences[END_REF]) 1 . Une fonction de choix est une fonction qui, à tout sous-ensemble non vide Y ⊆ X, associe un sous-ensemble non vide C(Y ) ⊆ Y . Une fonction de choix est dite rationalisable lorsqu'il existe une relation binaire S telle que l'ensemble des éléments maximaux de cette relation correspond à l'ensemble de choix. En fait, d'après Moulin [START_REF] Moulin | Choice functions over a finite set : a summary[END_REF], cette relation binaire correspond à la relation de base S associée à la fonction de choix et définie comme suit :

xSy ssi x ∈ C({x, y}) (7)
où C({x, y}) indique la fonction de choix appliquée au sous-ensemble {x, y}.

Notons que les ensembles R β (X) et R α-lex (X) ne correspondent pas toujours à des fonctions de choix, même s'ils ne sont pas vides sur X. En effet, considérons l'exemple de la section 2.2 pour

Y = {a 1 , a 4 } et β = β min (X) = 4. On a R β (Y ) = ∅ alors que R β (X) = {a 2 }. La même constatation peut être faite sur l'exemple pour l'ensemble R α-lex (X) en prenant Y = {a 2 , a 4 } et α = α min (X) = 2.
Néanmoins, il existe un seuil à partir duquel chacun de ces deux ensembles robustes correspond à une fonction de choix. Notons β c le seuil tel que :

∀Y ⊆ X, Y = ∅ ⇒ R β c (Y ) = ∅ (8)
De même, notons α c le seuil tel que :

∀Y ⊆ X, Y = ∅ ⇒ R α c -lex (Y ) = ∅ (9)
Il est clair que β c ≥ β min (X) et α c ≥ α min (X). Dans l'exemple de la section 2.2, on a β c = 5 > β min (X) et α c = 3 > α min (X). D'après la définition de β c et α c , nous avons :

Proposition 2 β c = max Y ⊆X,Y =∅ β min (Y ) α c = max Y ⊆X,Y =∅ α min (Y ) Preuve: On a ∀Y ⊆ X, Y = ∅, β ≥ β c ≥ β min (Y ) ⇒ R β (Y ) = ∅.
Ce qui démontre que ∀β ≥ β c , R β (X) est une fonction de choix. Il est clair que β c est le plus petit seuil vérifiant cette propriété. Idem pour α c . Si β ≥ β c et α ≥ α c , alors les ensembles R β (X) et R α-lex (X) sont des fonctions de choix rationalisables par les relations de base suivantes :

xS β y ⇔ x ∈ R β ({x, y}) (10) ⇔ f s (x) -min{f s (x), f s (y)} ≤ β, ∀s ∈ S (11) ⇔ f s (x) -f s (y) ≤ β, ∀s ∈ S ( 12
)
xS α y ⇔ x ∈ R α-lex ({x, y}) (13) ⇔ fj (x) -min{ fj (x), fj (y)} ≤ α, ∀j ∈ {1, . . . , q} (14)
⇔ fj (x) -fj (y) ≤ α, ∀j ∈ {1, . . . , q} (15)
Notons qu'en plus d'avoir une partie asymétrique acyclique, les relations S β et S α sont complètes [START_REF] Moulin | Choice functions over a finite set : a summary[END_REF]. Les ensembles R β (X) et R α-lex (X) correspondent respectivement aux éléments maximaux de S β et S α .

Proposition 3 ∀β ≥ β c , R β (X) = {x ∈ X : ∀y ∈ X xS β y} ∀α ≥ α c , R α-lex (X) = {x ∈ X : ∀y ∈ X xS α y}
Une interprétation de ce résultat est qu'au-delà d'un certain seuil, une solution robuste ne dépend plus du contexte (l'ensemble X entier) mais uniquement des évaluations par paire. En effet, une solution peut être éliminée dès lors qu'elle n'est pas robuste par rapport à une autre.

En plus des points communs énumérés dans l'introduction, nous venons de voir que les deux ensembles de solutions robustes se comportent de façon similaire par rapport à certaines propriétés. Cette ressemblance entre la β-robustesse et l'α-robustesse lexicographique suggère de chercher un lien entre ces deux approches, ce que nous nous proposons de faire dans la section qui suit.

4 Liens entre R β (X) et R α-lex (X)
Dans cette section, nous établissons une relation entre l'ensemble des solutions βrobustes R β (X) et l'ensemble des solutions α-robustes lexicographiques R α-lex (X).

Pour donner une idée intuitive du résultat, regardons l'évolution des ensembles R β (X) et R α-lex (X) en fonction des seuils β et α dans l'exemple de la section 2.2. Le Tableau 3 représente cette évolution pour des seuils variant de 1 à 8. Par exemple, pour β = α = 4, R β (X) = {a 2 } et R α-lex (X) = {a 1 , a 2 , a 3 }. Dans cet exemple, il apparaît que pour des seuils β et α égaux, l'ensemble R β (X) est inclus dans l'ensemble R α-lex (X) quelle que soit la valeur de ces paramètres. Par monotonie de l'ensemble des solutions β-robustes, cette constatation reste valable pour β ≤ α.

Valeur du seuil R β (X) R α-lex (X) 0 -1 ∅ ∅ 2 ∅ {a 1 } 3 ∅ {a 1 , a 2 } 4 {a 2 } {a 1 , a 2 , a 3 } 5 -6 {a 1 , a 2 } {a 1 , a 2 , a 3 , a 4 } = X 7 {a 1 , a 2 , a 3 } {a 1 , a 2 , a 3 , a 4 } = X 8 {a 1 , a 2 , a 3 , a 4 } = X {a 1 , a 2 , a 3 , a 4 } = X
TAB. 3 -Les ensembles R β (X) and R α-lex (X) en fonction du seuil Nous démontrons dans ce qui suit que cette relation est toujours vérifiée.

Théorème 1 Si β ≤ α alors R β (X) ⊆ R α-lex (X).
Preuve: Soit x ∈ R β (X). On a :

∀s ∈ S, f s (x) ≤ f s (x * ) + β (16)
La solution x * étant celle définie par l'équation [START_REF] Bertsimas | Robust discrete optimization and network flows[END_REF]. Grâce au résultat de Podinovskii énoncé dans la preuve de la propriété 1, nous pouvons déduire que :

∀j ≤ q, fj (x) ≤ fj (x * ) + β. (17)
Nous allons maintenant montrer que, pour tout k ≤ q :

fk (x * ) ≤ fk (x * k ). (18)
Par définition de x * , nous avons, pour tout x ∈ X :

∀s ∈ S : f s (x * ) ≤ f s (x). (19)
Cette inégalité est vraie en particulier pour

x = x * k = arg min x∈X fk (x), k étant fixé : ∀s ∈ S : f s (x * ) ≤ f s (x * k ). (20)
Nous pouvons déduire que :

∀j ≤ q : fj (x * ) ≤ fj (x * k ). (21)
Ceci étant vrai pour tout j, c'est vrai pour j = k, ce qui démontre l'inégalité [START_REF] Sen | Choice functions and revealed preferences[END_REF]. Etant données l'inégalité [START_REF] Rosenblatt | A robustness approach to facilities design[END_REF] et le fait que β ≤ α, il s'en suit que :

∀j ≤ q, fj (x) ≤ fj (x * j ) + α. (22)
Par conséquent, x ∈ R α-lex (X).

Remarquons que la démonstration reste vraie si on considère non pas l'ensemble X entier, mais seulement un sous-ensemble non vide

Y ⊆ X. Ainsi, si β ≤ α alors R β (Y ) ⊆ R α-lex (Y ).
Il découle du théorème 1 que les seuils α min et β min vérifient la relation suivante :

Corollaire 1 α min ≤ β min Preuve: Supposons que α min > β min et choisissons β = α = β min . On a donc R β (X) = ∅ et R α-lex (X) = ∅ ce qui contredit le théorème 1.
Les seuils β c et α c , définis respectivement par les équations (8) et [START_REF] Kalaï | Lexicographic α-robust knapsack problem : Complexity results[END_REF], vérifient ce qui suit :

Corollaire 2 α c ≤ β c Preuve: Supposons que β = α = β c . On a donc : ∀Y ⊆ X, Y = ∅ R β (X) = ∅ D'après le théorème 1, ceci implique que : ∀Y ⊆ X, Y = ∅ R α-lex (X) = ∅ Par conséquent, α c ≤ α = β c .
Le théorème 1 indique que l'α-robustesse lexicographique, tout en ayant beaucoup de propriétés communes avec la β-robustesse, est moins "sévère" que cette dernière puisqu'elle donne des solutions pour des seuils plus faibles que ceux exigés par la seconde approche. Cette caractéristique semble donner un argument en défaveur de l'α-robustesse lexicographique puisque, généralement, on cherche à réduire un ensemble de choix et non à l'augmenter. Néanmoins, rappelons que le seuil β min , donnant le plus petit ensemble de solutions β-robustes non vide, n'est autre que le regret maximal minimal. Cette valeur peut être importante dans certains cas ; dans l'exemple de la section 2.2, β min est deux fois plus grand que α min . Il n'est donc pas toujours possible de trouver des solutions βrobustes pour des seuils raisonnables, d'où l'intérêt d'avoir une approche similaire qui donne des solutions pour des seuils plus faibles.

Conclusion

Dans cet article, nous avons voulu mettre en évidence la similitude entre l'α-robustesse lexicographique et la β-robustesse sur la base d'un certain nombre de propriétés. De plus, nous avons pu établir un lien direct entre ces deux approches qui suggère que la première approche est en quelque sorte une relaxation de la seconde.

Ce travail de comparaison entre les deux approches ne constitue qu'un premier pas dans cette direction. Nous nous interrogeons, par exemple, sur les problèmes pour lesquels les deux seuils minimaux α min et β min sont différents. La réponse à cette question pourrait donner plus de crédibilité à l'α-robustesse lexicographique si de tels problèmes étaient nombreux. Il faudrait aussi étudier davantage la relation de base qui rationalise les deux ensembles, dans un but algorithmique par exemple. Finalement, une caractérisation axiomatique des deux ensembles de solutions robustes permettra de pouvoir clairement les distinguer.

De manière plus générale, nous pensons qu'il est utile d'élargir ce type de comparaison à d'autres approches de robustesse existantes. En effet, cela permettra de mieux guider un analyste ou un décideur dans le choix de l'approche robuste la plus appropriée dans une application concrète.

Pour que cette relation acyclique soit quasi-transitive, il faut qu'elle vérifie, en plus des propriétés de Chernoff et d'expansion, une troisième propriété appelée propriété d'Aizermann. Cette dernière stipule que si R(X) ⊆ Y ⊆ X alors R(Y ) ⊆ R(X). La propriété d'Aizermann n'est vérifiée ni pour R α-lex ni pour R β , comme le montre le contre-exemple suivant : f(x)=(6,3,3), f(y)=(4,4,4) et f(z)=(5,2,2).


Prof Rozita Teymourzadeh
email: rozita60@vlsi.eng.ukm.my

Dr Masuri Othman

On-Chip Implementation of Cascaded Integrated Comb filters (CIC) for DSP applications

Keywords: CIC, comb, Filters, Converters, Sigma Delta A/D conversion; comb filters, decimation filters

This paper presents the design of a CIC filters based on a low-pass filter for reducing the sampling rate, also known as decimation process. The targeted application for the filter is in the analog to digital conversion (ADC).The CIC is chosen because of its attractive property of both low power and complexity since it dose not required multipliers. Simulink toolbox available in Matlab software is used to design and simulate the functionality of the CIC filter. This paper also shows how sample frequency is decreased by CIC filter and it can be used to give enough stop-band attenuation to prevent aliasing after decimation.

I. INTRODUCTION

Sigma delta (∑Δ) modulator is an over sampled modulation technique which 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. The CIC filter is a preferred technique for this purpose. Additionally the CIC filter does not require storage for filter coefficients and multipliers as all coefficients are unity [START_REF] Hogenauer | An economical class of digital filters for decimation and interpolation[END_REF]. Furthermore its on-chip implementation is efficient because of its regular structure consisting of two 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 circuit and minimal changes to the filter timing. The CIC filter also removes quantization noise and prevents aliasing introduced during sampling rate decreasing. In this project, the design and implementation of CIC filters, its impulse responses are evaluated by using Matlab. Once the functionality of the filter is verified, the Verilog coding for the filter will be written, simulated and compared with the results from the MATLAB simulations. The chip implementation of the filter will follow. Section II presents overview of the CIC filter followed by section III which gives some results of the characteristics of the filters. Chip implementation of the filters is described in the last section.

II. An overview of CIC filters

A. CIC filters to perform the decimation process.

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 1-bit data stream at the output of the Sigma-delta modulator an n-bit data stream with lower sample rate (where n is determined by the specifications of the filters). 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 the CIC filter (Block in the middle).

B. CIC filters equation and block diagram

The building blocks of the CIC filter are the integrator (Fig. 2) and the comb filter (Fig. 3).

For the integrator, its equation in the discrete-time domain and z-domain are:

y[n] = y[n-1] + x[n] 1(a) H I (z) = 1 1 1   z 1(b)
Which is a simply single-pole IIR filter with a unity feedback coefficient and in other words a single integrator by itself is unstable.

The comb filters (another part of CIC filter) which does not require feedback for M (differential delay) = 1 is shown below:

Sampling rate reduction by the comb filter is given by fs/R where Fs is the high sampling rate and R is the decimation factor of the filter, the operation of the comb filter is:

y[n] = x[n] -x[n -RM] 2(a) Fig.3: Comb Cell Fig.2: Integrator Cell H C (z) = (1-z RM  ) 2(b)
The transfer function after adding Comb and Integrator block and in N stage is given as:

H (z) = H N I (z). H N C (z) =          1 0 1 ) ( ) 1 ( ) 1 ( RM k N k N N RM z z z (3)
The block diagram of one stage CIC filter is drawn as below:

A. Simulation

The structure of the CIC filter in figure 4 is inputted to Simulink toolbox as shown below:

B. Impulse and Frequency Response

Overall filter transfer function of N-order CIC with gain involving can be expressed as :

H(z) = N D K k N N D N z z z D                1 0 1 ) 1 ( ) 1 ( 1 (5)
Where the term 1/D N takes in to account the DC gain of the integrators and D = RM is desired decimation factor.

CIC filters have a linear-phase low-pass frequency response that can be obtained by

setting z = e  j
(by assuming a sampling interval T = 1/ f s , the digital frequency f d is related to ω through ω = 2πf T = 2πf d , where f is the analog frequency, obtaining

H(e d f j  2 ) = N D 1 2 1 2 ) ) ( ) ( (   D N d j N d d d e f Sin Df Sin    (6)
The transfer function of equation ( 6) is equal to zero at integer multiples of the frequency

f k = k.(1/D), with k = 1,…,[D/2] if D is even and k = 1,…,[D-1/2] for D odd.[2]

Fig. 1 :

 1 Fig.1: Digital Decimation Process This CIC filter chosen is a low pass filter with symmetric coefficient value and linearphase response. It provides 4:1 decimation (in above example) and magnitude compensation for the magnitude change (droop) from the CIC filter output. Detailed analysis will be presented in in section IV.

Fig. 4 :

 4 Fig.4: One-stage CIC filtering ProcessThe gain of the CIC filter can be expressed as:

Fig. 5 :

 5 Fig.5: CIC filter simulation Input and output of simulations (fig.6) make clearer the CIC filter tasks. Input frequency is 200 kHz and output frequency is 4 kHz which give decimation factor of 50. Because of the Integrator block in CIC filter DC gain also has increased and it evaluated by Gain equation: G = (50 × 1) 2 = 2500

Fig. 6 :

 6 Fig.6: Input and Output CIC filter

decimated sample rate. Using an appropriate FIR filter in series after the CIC decimation filter can compensate for the induced droop.

V. CIC FILTER CONSTRAINTS & CHIP DESIGN A. CIC filter constraints

CIC decimator filter have the following two constraints:

The word lengths of the filter stages must be no increasing. That is the word length of each filter stage. The number of bits of the first filter stage must be greater than or equal to the quantity Bmax. [START_REF]CIC decimation. Signal processing Blockset[END_REF]. Bmax is achieved by followed equation:

Where B is the number of bits of the input.

The number of output bit in last comb stage is achieved as below:

Bout bits are needed for each integrator and comb stage.

B. Chip design

VI. CONCLUSION

In this paper structure, block diagram and specification of CIC filter by using Matlab software has been proposed and also first step of chip implementation was described.

Although the objective of this paper has been written but further work about truncation or rounding which may be used for each stage still has not be done by this paper.

VII. ACKNOWLEDGEMENT

I wish to thank my supervisor, Prof. Dr. Masuri Othman who has assisted me for completion of this dissertation.


Rozita Teymourzadeh
email: rozita60@vlsi.eng.ukm.my

Masuri Othman

An Improved Recursive and Non-recursive Comb Filter for DSP Applications

The recursive and non-recursive comb filters are commonly used as decimators for the sigma delta modulators. This paper presents the analysis and design of low power and high speed comb filters. The comparison is made between the recursive and the non-recursive comb filters with the focus on high speed and saving power consumption. Design procedures and examples are given by using Matlab and Verilog HDL for both recursive and non-recursive comb filter with emphasis on frequency response, transfer function and register width. The implementation results show that non-recursive comb filter has capability of speeding up the circuit and reducing power compared to recursive one when the decimation ratio and filter order are high. Using Modified Carry Look-ahead Adder for summation and also apply pipelined filter structure makes it more compatible for DSP application.

1 Introduction lectronic and communication system for speech processing and radar make use of sigma delta modulator in their operation [START_REF] Crochiere | Multirate Digital Signal Processing[END_REF], [START_REF] Vaidyanathan | Multirate Systems and Filter Banks[END_REF]. Future system are required to operate with low power and high speed and therefore the sigma delta modulator must be designed accordingly.

The comb filter that will be designed in this paper is part of the sigma delta modulator which is required to be low power and high speed performance. Comb filter was applied to decimate the sampling frequency from high to low and obtain high resolution. It is also used to perform filtering of the out of band quantization noise and prevent excess aliasing introduced during sampling rate decreasing. Comb filter is popular because of no multipliers and coefficient storages are required due to all filter coefficients are unity [START_REF] Park | Principles of Sigma-delta Modulation for Analog-to-Digital Converters[END_REF].

Hence low power and high speed will be key issues in chip implementation of comb decimators.

There are two type of comb filter, first is recursive comb filter and second is non-recursive comb filter.

In 1981, Eugene Hogenauer [START_REF] Hogenauer | An Economical Class of digital filters for Decimation and interpolation[END_REF] invented a new class of economical digital filter for decimation called a Cascaded Integrator Comb filter (CIC) or recursive comb filter. This filter consists of three parts which are Integrator, comb and down sampler. CIC filter is considered as recursive filter because of the feedback loop in integrator circuit.

The second type called non-recursive comb filter which has regular structure and this property makes it suitable for VLSI implementation. In 1999, Yonghong Gao, Lihong Jia and Hannu Tenhunen [START_REF] Gao | A Partial-polyphase VLSI Architecture for very High speed CIC Decimation Filters[END_REF] introduced this filter because of its advantages such as no recursive loop and using low power consumption due to computations are performed at lower sampling rate.

The next section describes the mathematical formulation and block diagram of CIC filters in detail. Section 3 discusses non-recursive comb filter algorithms and its advantages compared to recursive filter. Enhanced high speed architecture is depicted in section 4. Section 5 shows implementation and design result in brief. Finally conclusion is expressed in section 6.

Recursive CIC filter design

Recursive comb filter or CIC filter consist of N stages of integrator and comb filter which are connected by a down sampler stage as shown in figure 1in z domain.

The CIC filter has the following transfer function: [START_REF] Crochiere | Multirate Digital Signal Processing[END_REF] where N is the number of stage, M is the differential delay and R is the decimation factor.

E            1 0 1 ) ( ) 1 ( ) 1 ( ) ( ). ( ) ( RM k N k N N RM N C N I z z z z H z H z H
In this paper, N, M and R have been chosen to be 5, 1 and 16 respectively to avoid overflow in each stages. From the equation, the maximum register growth/width, max G can be expressed as:

  N RM G  max (3)
In other word, max G 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 in B , most significant bit (MSB) at the filter output, max B is given by: ] 1 log [

2 max    in B R N B (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. The recursive part of the CIC filter has to operate with the high oversampling rate and has large width length which is the cause of high power consumption. Due to recursive loop in its structure, low power is limited by the high range of calculation in the integrator stage. Since the integrator stage works at the highest oversampling rate with a large internal word length, decimation ratio and filter order increase which result in more power consumption and speed limitation. In this case, a non-recursive filter is proposed to replace when the decimation ratio and filter order are high.

Truncation for speeding up purpose

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 DSP applications.

Figure 2 illustrates five stages of the CIC filter when max B is 25 bit so truncation is applied to reduce register width. Matlab software helps to find word length in integrator and comb section. The non-recursive comb filter [START_REF] Candy | Oversampling Delta-Sigma Data Converters: Theory, Design and simulation[END_REF], [START_REF] Farag | A programmable power-efficient decimation filter for software radios[END_REF] has ability of wide range of rate change. Its transfer function is shown as follow:

  N M i N i i N R i i i M z z z z H                               1 0 2 1 2 0 1 0 1 ) ( ( 5
)
where R is the decimation factor, N is the filter order and M is the number of stage. Note that R should be a power of 2.

Non-recursive comb filter structure is shown in Figure 3. Compared to the CIC filter structure, 1) it is clear that during decimation process and decreasing sampling frequency, the number of bit increases and it is the cause of the saving in power. 2) The comb decimator using the nonrecursive algorithm can achieve higher speed since the first stage always has small word length and also 3) when decimation ratio increases, the silicon size of the recursive design algorithm increases slowly compared to the nonrecursive design algorithm and it is next advantages of using non-recursive filter as decimator.

Non-recursive comb filter was implemented and R, M and N are selected respectively to be 8, 3 and 5 so if input word length is considered to be 5 output words length change to 20.

Every stage is included of N blocks non-recursive comb filter (See Figure 5). Figure 4 shows pipeline CIC filter structure when truncation is also applied. In the pipelined structure, no additional pipeline registers are used. So that hardware requirement is the same as in the non-pipeline [START_REF] Djadi | A high throughput Programmable Decimation and Interpolation Filter[END_REF].

 

N N RM k N RM k k N RM k k N RM k k N RM k k RM z z z z k h z H                                            1 0 1 0 1 0 1 0 ) 1 ( 0 1 ) ( ) ( Input Sample rate 1 1 1   z R RM z   1 Integrator Decimator Comb Output Sample rate R F s s F (2)
CIC decimation filter clock rate is determined by the first integrator stage that causes more propagation delay than any other stage due to maximum number of bit. So 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.

Clock rate in integrator section is R times higher than in the comb section, so pipeline structure can not applied for comb section.

Non-recursive comb filter has no integrator part; therefore pipeline structure is used for comb stages. Figure 5 shows Pipeline non-recursive comb filter. It is achieved by locating register after MCLA in stage M .

Modified Carry look-ahead Adder (MCLA)

The other technique to increase speed is using Modified Carry Look-ahead Adder. MCLA was selected to perform the summation in both recursive and non-recursive comb filters.

This improve in speed is due to the carry calculation in MCLA. In the ripple carry adder, most significant bit addition has to wait for the carry to ripple through from the least significant bit addition. Therefore the carry of MCLA adder has become a focus of study in speeding up the adder circuits [START_REF] Michael | Advanced Digital design with the Verilog HDL[END_REF].

The 8 bit MCLA structure is shown in Figure 6. Its block diagram consists of 2, 4-bit module which is connected and each previous 4 bit calculates carry out for the next carry.

The CIC filter in this paper has five MCLA in integrator parts. The maximum number of bit is 25 and it is decreased in next stages. So it truncated respectively to 25, 22, 20, 18 and 16 bit in each adder, left to right. Non-recursive comb filter has fifteen MCLA in nonrecursive part.

The Verilog code has been written to implement summation. The MCLA Verilog code was downloaded to the Xilinx FPGA chip. It was found minimum clock period on FPGA board is 4.389ns (Maximum Frequency is 220 MHz). Figure 7 shows the amplitude of the CIC filter output versus output samples number, before and after truncation is applied for the filter.

As seen in Figure 7, output amplitude curve of the filter is sharper when it is truncated and some LSB is discarded compared to filter response without truncation. It shows increasing the speed of filter calculation after truncation. To improve the signal to noise ratio, word length of recursive and non-recursive comb filter should be increased but the speed of filter calculation is also decreased. Recursive and non-recursive comb filters have been designed and investigated.

When N = 3 Block 1 Block 3 Block 2   N z 1 1    1 Z 1  Z  1 Z  1 Z  1 Z  1 Z + + +
) (n y   N z 1 1     N z 1 1     N z 1 1   ) (n x i s f 2 / 1 2 /  i s f 2 2 2 Stage 1 Stage M Stage 2 C+MN bit C bit C+2N bit C+N bit 1  Z R 1  Z 1  Z 1  Z 1  Z 1  Z 1  Z 1  Z 1 
Enhanced high Speed recursive and non-recursive comb filters was shown by using pipeline structure and replacing with the modified carry look-ahead adder (MCLA).

The evaluation indicates non-recursive comb filter is attractive compared to the recursive one due to lower power consumption and higher speed. First stage of recursive comb filter (CIC) word length always has maximum bit number and it is decreased by truncation function whereas first stage of non-recursive filter has minimum word length size compared to other stages, so it is the cause of achieving higher speed.

However Recursive comb filter (CIC) is attractive when the decimation ratio and filter order are not high.

Figure 1 :

 1 Figure 1: One-stage of CIC filter block diagram

Figure 2 :

 2 Figure 2: Five-stage of truncated CIC filter include integrator and comb cell

Figure 3

 3 Figure 3: Non-recursive Comb decimation filter

Figure 4 :Figure 5 :

 45 Figure 4: Five-stage of truncated pipeline CIC filter include integrator and comb cell

Figure 6 :

 6 Figure 6: The 8 bit MCLA structure

Figure 7 :

 7 Figure 7: Truncation effect on CIC filter amplitude vs. output sample number

Figure 8 :Figure 9

 89 Figure 8: Comb filter frequency response for R=16, M=1 and N=5

Figure 9 :

 9 Figure 9: Signal spectra (a) Output sigma delta modulator SNR (b) Output Comb filter SNR

Figure 10 :

 10 Figure 10: Working frequency comparisons of the (a) recursive and (b) non-recursive comb filter


Rozita Teymourzadeh
email: rozita60@vlsi.eng.ukm.my

Masuri Othman

An Overview of the Decimation process and its VLSI implementation

Keywords: Decimation, CIC, comb, Filters, Converters, Sigma Delta A/D conversion, comb filters, decimation filters

Digital Decimation process plays an important task in communication system. It mostly is applied in transceiver when the frequency reduction is required. However, the decimation process for sigma delta modulator is considered in this research work. The proposed design was simulated using MATLAB software and implemented by hardware description language in Xilinx environment. Furthermore, the proposed advance arithmetic unit is applied to improve the system efficiency.

INTRODUCTION

Although real world signals are analog, but digital to analog converter (ADC) helps lead signal to digital domain due to it is easier evaluate and process. Digital signal can be converted back to analog signal by digital to analog converter (DAC). Over sampling modulator is applied for audio application to convert it as digital signal by high sampling frequency. The audio signal is sampled within the modulator at a rate significantly higher than the Nyquist rate. After over sampling, decimation block is required to remove noise shaping and decimate the digital signal from high to low. For over sampling, Sigma delta modulator and for decimation Cascaded Integrator Comb filter (CIC), half band and Finite Impulse Response filter have been selected to carry out the task. This paper describes decimation process by the focus on high speed implementation of CIC filter [START_REF] Hogenauer | An economical class of digital filters for decimation and interpolation[END_REF]. The advantages of this paper are using three methods to speed up the CIC filter such as using Modified Carry Look-adder Adders and achieve the filter ripple less than 0.0002 db. Simulink toolbox available in Matlab software which is used to simulator and Verilog HDL coding by Xilinx software help to verify the functionality of the CIC filters and Implement it on VLSI as chip.

DESCRIPTION

Digital audio application such HiFi CD and DAT systems often use sigma delta A/D converters [START_REF] Pervez | An Overview of Sigma -Delta Converter[END_REF]. The quality of sigma delta modulator is recognized by the order and its resolution. In this project the sampling frequency represent as 6.144 MHz with the over sampling ration of 128. Nyquist frequency is selected to be 48 kHz to support B f equal to 24 kHz with the frequency response ripple less than 0.0002 db. Figure 1 shows 3rd order sigma delta modulator with multirate decimation filter. A multirate decimation filter system was chosen to realize the needed performance. The filter system was thus organized as an initial filter stage having a 16:1decimation ratio followed by a third stage having an 8:1decimation ratio.

2 1  R 16 0  R 2 2  R 2 3  R FIGURE 1: Digital Decimation Process
CIC filter is located after sigma delta modulator and decimate the frequency by the ratio of 16. The packing of modulator and CIC filter minimized the noise by decrease the number of parallel pad drivers. Then CIC filter increase the sigma delta resolution to improve Signal to Noise ratio.The two half band filters [START_REF] Brandt | A Low-Power, Area-Efficient Digital Filter for Decimation and Interpolation[END_REF] are used to reduce remain sampling rate reduction to the Nyquist output rate. First half band filter and second half band filter make the frequency response more flat and sharp similar to ideal filter specially second half band filter due to higher order of the filter (R=40), has most effect to make the frequency response sharp. All the even coefficients of half band filters are zero exception last one which is 0.5. This particular make them efficient for 2:1 decimation ratio and reduce the computational complexity by near 50% as compared to general direct form filter Architecture. Droop correction filter is allocated to compensate pass band attenuation which is created by CIC filter. The frequency response of overall system will be shown in Figure 2. FIGURE 2: Frequency response of decimation system Similar Decimation process has been done by Thompson [START_REF] Thompson | A VLSI Sigma Delta A/D Converter for Audio and Signal Processing Applications[END_REF] but in this paper high speed Cascaded Integrator Comb filter is designed and implemented to accomplish decimation task, remove quantization noise and avoid aliasing to the signal.

CASCADED INTEGRATOR COMB FILTER

Previously, Low pass decimation filter structure (FIGURE 3) widely used for decimation before appearance of the CIC decimation filter (Adams 1994). This structure has M Multipliers which make the large number of computation whereas new structure of decimation or CIC is multiplier less in terms of minimizing hardware and computational. Additionally the CIC filter does not require storage for filter coefficients and multipliers as all coefficients are unity (Sangil Park 1990). The VLSI implementation of CIC filter makes it able to be used as a SoC chip.

1  z D Y(m) D Fs / s F h(0) x(0) s F h(1) 1  z h(2) h(M-2) 1  z h(M-1)
           1 0 1 ) ( ) 1 ( ) 1 ( ) ( ). ( ) ( RM k N k N N RM N C N I z z z z H z H z H (1)
In this paper, N, M and R have been chosen to be 5, 1 and 16 respectively to avoid overflow in each stages. CIC filter has low and high pass component. Integrator part low pas transfer function structure amplify low frequency component so integrator it self is not stable due to the integrator output will cause over flow. In this case, the comb stage with high pass structure attenuates the low frequency component, making the whole system stable. N, M and R are parameters to determine the register length requirements necessary to assure no data loss. The maximum register growth/width, max G can be expressed as:

  N RM G  max (3)
In other word, max G 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 in B , most significant bit (MSB) at the filter output, max B is given by: ] 1 log [

2 max    in B R N B (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.

NOVEL SPECIFICATIONS

This paper describes how to enhance the decimation system. To achieve the aim, three methods are used as follow:

High speed CIC filter 1.1 Truncation

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 Audio applications. Figure 2 illustrates five stages of the CIC filter when max B is 25 bit so truncation is applied to reduce register width.

Matlab software helps to find word length in integrator and comb section.

Modified Carry look-ahead adder (MCLA)

The other technique to increase speed is using Modified Carry Look-ahead Adder [START_REF] Michael | Advanced Digital design with the Verilog HDL[END_REF]. The Carry Look-ahead adder (CLA) is the fastest adder which can be used for speeding up purpose but the disadvantage of the CLA adder is that the carry logic is getting quite complicated for more than 4 bits so Modified Carry Look-ahead Adder (MCLA) is introduced to replace as adder. This improve in speed is due to the carry calculation in MCLA. The 25bit MCLA structure is shown in Figure 4. Its block diagram consists of 2, 4-bit module which is connected and each previous 4 bit calculates carry out for the next carry. The Verilog code has been written to implement summation. The MCLA Verilog code was downloaded to the Xilinx FPGA chip. It was found minimum clock period on FPGA board is 4.389ns (Maximum Frequency is 220 MHz).

a[17] b[17] s[17] p[17] g[17] a[18] b[18] s[18] p[18] g[18] c[17] a[19] b[19] s[19] p[19] g[19] c[18] a[16] b[16] s[16] p[16] g[16] c[16] PFA PFA PFA PFA CLL-2 MCLA_16_1 a[15:0] b[15:0] s[15:0] Co4 Co4 a[21] b[21] s[21] p[21] g[21] a[22] b[22] s[22] p[22] g[22] c[20] a[23] b[23] s[23] p[23] g[23] c[21] a[20] b[20] s[20] p[20] g[20] c[19] PFA PFA PFA PFA CLL-2 Co5 Co5 a[24] b[24] s[24] SPFA Co6
Z + + 1  Z + + 1  Z + + 1  Z + + + - 1  Z Comb 1 25 bit + - 1  Z Comb 2 25 bit + - 1  Z Comb 3 25 bit + - 1  Z Comb 4 25 bit + - 1  Z Comb 5 25 bit CIC_out 1  Z 1  Z 1  Z 1  Z 1  Z FIGURE 6:
Five-stage of truncated pipeline CIC filter include integrator and comb cell

FILTER RIPPLE

Ripple is usually specified as a peak-to-peak level in decibels. It describes how little or how much the filter's amplitude varies within a band. Smaller amounts of ripple represent more consistent response and are generally preferable. There is, however, a tradeoff between ripple and transition bandwidth, so that decreasing either will only serves to increase the other. The way of ripple improvement is increasing the number of coefficients used by the filter. One disadvantage of using increasingly long filter lengths is the compute time required to perform the filtering. In this paper the order of first half band filter, droop correction and second half band filter has been design to be 4,8 and 40 respectively to provide ripple less than 0.0002 db.

DESIGN RESULTS

Figure 7 shows the Droop correction filter result. This filter design a low pass filter with pass band having the shape of inverse CIC filter frequency response. So it compensates amplitude droop cause of the CIC filter and makes whole system frequency response flat. To improve the signal to noise ratio, word length of recursive CIC filter should be increased but the speed of filter calculation is also decreased.

FIGURE 3 :

 3 FIGURE 3: Decimation filter (a) low pass decimation filter (b) CIC filter where N is the number of stage, M is the differential delay and R is the decimation factor The CIC filter consist of N stages of integrator and comb filter which are connected by a down sampler stage as shown in figure 1 in z domain. The CIC filter has the following

  FIGURE 4: Five-stages of truncated CIC filter include integrator and comb cell

FIGURE 5 :

 5 FIGURE 5: The 25 bit MCLA structure 1.3 Pipeline structureOne way to have high speed CIC filter is by implementing the pipeline filter structure. Figure6shows pipeline CIC filter structure. In the pipelined structure, no additional pipeline registers are used for integrator part.(Djadi et al 1994).

Figure 6

 6 shows pipeline CIC filter structure. In the pipelined structure, no additional pipeline registers are used for integrator part.(Djadi et al 1994).

FIGURE 7 :

 7 FIGURE 7: Droop Correction effect on frequency response Figure 8 shows the measured baseband output spectra before (Figure 8(a)) and after (Figure 8(b)) the decimation functions. The CIC filter Verilog code was wrote and simulated by Matlab software. It is found Signal to Noise ratio (SNR) is 141.56 dB in sigma delta modulator output and SNR is increased to 145.35 dB in the decimation stages.To improve the signal to noise ratio, word length of recursive CIC filter should be increased but the speed of filter calculation is also decreased.

FIGURE 8 :

 8 FIGURE 8: Signal spectra (a) Output ∑Δ modulator SNR (b) Output CIC filter SNR Figure9shows the pass band ripple for whole decimation system. It is clear that the pass band ripple is less than 0.0002 db.

FIGURE 9 :

 9 FIGURE 9: Pass band ripple in whole decimation frequency response

ACKNOWLEDGEMENT

I wish to thank my supervisor, Prof. Dr. Masuri Othman who has assisted me for completion of this dissertation.


Rozita Teymourzadeh
email: rozita60@vlsi.eng.ukm.my

Masuri Othman

VLSI Implementation of Cascaded Integrator Comb Filters for DSP Applications

Keywords: CIC, sigma delta, Decimation, Comb, recursive, truncation, MCLA

The recursive comb filters or Cascaded Integrator Comb filter (CIC) are commonly used as decimators for the sigma delta modulators. This paper presents the VLSI implementation, analysis and design of high speed CIC filters which are based on a low-pass filter. These filters are used in the signal decimation which has the effect on reducing the sampling rate. It is also chosen because its attractive property of both low power and low complexity since it dose not required a multiplier. Simulink toolbox available in Matlab software which is used to simulator and Verilog HDL coding help to verify the functionality of the CIC filters. Design procedures and examples are given for CIC filter with emphasis on frequency response, transfer function and register width. The implementation results show using Modified Carry Look-ahead Adder for summation and also apply pipelined filter structure enhanced high speed and make it more compatible for DSP applications.

Introduction

Electronic and communication system for speech processing and radar make use of sigma delta modulator in their operation [START_REF] Crochiere | Multirate Digital Signal Processing[END_REF], [START_REF] Vaidyanathan | Multirate Systems and Filter Banks[END_REF]. Future systems are required to operate with high speed and therefore the sigma delta modulator must be designed accordingly. Sigma delta (∑Δ) modulator is an over sampled modulation technique which 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. In 1981, Eugene Hogenauer [START_REF] Hogenauer | An Economical Class of digital filters for Decimation and interpolation[END_REF] invented a new class of economical digital filter for decimation called a Cascaded Integrator Comb filter (CIC) or recursive comb filter. Additionally the CIC filter does not require 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 two 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 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 enhanced high speed will be key issue in chip implementation of CIC decimators. This filter consists of three parts which are Integrator, comb and down sampler. CIC filter is considered as recursive filter because of the feedback loop in integrator circuit. The next section describes the mathematical formulation and block diagram of CIC filters in detail. Enhanced high speed architecture is explained in section 3. Section 4 shows implementation and design result in brief. Finally conclusion is expressed in section 5.

An overview of decimation system

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 Sigmadelta 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.

Fig. 1 Digital Decimation Process

The two half band filters [START_REF] Brandt | A Low-Power, Area-Efficient Digital Filter for Decimation and Interpolation[END_REF] are used to reduce remain sampling rate reduction to the Nyquist output rate. First half band filter and second half band filter make the frequency response more flat and sharp similar to ideal filter frequency response.

2 1  R 16 0  R 2 2  R 2 3  R
Droop correction filter is allocated to compensate pass band attenuation which is created by CIC filter. The frequency response of overall system will be shown in section 4.

CIC filters structure

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

           1 0 1 ) ( ) 1 ( ) 1 ( ) ( ). ( ) ( RM k N k N N RM N C N I z z z z H z H z H (1)
where N is the number of stage, M is the differential delay and R is the decimation factor. In this paper, N, M and R have been chosen to be 5, 1 and 16 respectively to avoid overflow in each stages. From the equation, the maximum register growth/width, max G can be expressed as:

  N RM G  max (3)
In other word, max G 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 in B , most significant bit (MSB) at the filter output, max B is given by: ] 1 log [

2 max    in B R N B (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 result in more power consumption and speed limitation.

Truncation for low power & high speed purpose

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 DSP applications. Figure 2 illustrates five stages of the CIC filter when max B is 25 bit so truncation is applied to reduce register width. Matlab software helps to find word length in integrator and comb section.

Fig. 3 Five-stages of truncated CIC filter include integrator and comb cell 3 Speed Improvement

There are two ways to speed up the CIC filter which describes as below.

Pipeline structure

One way to have high speed CIC filter is by implementing the pipeline filter structure. Figure 4 shows pipeline CIC filter structure when truncation is also applied. In the pipelined structure, no additional pipeline registers are used. So that hardware requirement is the same as in the non-pipeline [START_REF] Djadi | A high throughput Programmable Decimation and Interpolation Filter[END_REF]. CIC decimation filter clock rate is determined by the first integrator stage that causes more propagation delay than any other stage due to maximum number of bit. So 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. Clock rate in integrator

  N N RM k N RM k k N RM k k N RM k k N RM k k RM z z z z k h z H                                            1 0 1 0 1 0 1 0 ) 1 ( 0 1 ) ( ) ( (2)
section is R times higher than in the comb section, so pipeline structure can not applied for comb section.

1  Z R 1  Z 1  Z 1  Z 1  Z 1  Z 1  Z 1  Z 1 

Modified Carry look-ahead Adder (MCLA)

The other technique to increase speed is using Modified Carry Look-ahead Adder. The Carry Lookahead adder (CLA) is the fastest adder which can be used for speeding up purpose but the disadvantage of the CLA adder is that the carry logic is getting quite complicated for more than 4 bits so Modified Carry Look-ahead Adder (MCLA) is introduced to replace as adder. This improve in speed is due to the carry calculation in MCLA. In the ripple carry adder, most significant bit addition has to wait for the carry to ripple through from the least significant bit addition. Therefore the carry of MCLA adder has become a focus of study in speeding up the adder circuits [START_REF] Michael | Advanced Digital design with the Verilog HDL[END_REF]. The 8 bit MCLA structure is shown in Figure 6. Its block diagram consists of 2, 4-bit module which is connected and each previous 4 bit calculates carry out for the next carry. The CIC filter in this paper has five MCLA in integrator parts. The maximum number of bit is 25 and it is decreased in next stages. So 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 MCLA Logic block. The group Propagate P G and Generate G G of a 4bit adder will have the following expressions:

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

) . (

0 0 0 1 c p g c   (7) ) . . ( ) . ( 0 0 1 0 1 1 2 c p p g p g c    (8) ) . . ( ) . . ( ) . ( 0 . 0 1 2 0 1 2 1 2 2 3 c p p p g p p g p g c     (9) ) . . . ( ) . . ( ) . ( 0 1 2 3 1 2 3 2 3 3 4 g p p p g p p g p g c     ) . . . . ( 0 0 1 2 3 c p p p p 
Calculation of MCLA is based on above equations. 8-Bit MCLA Adder could be constructed continuing along in the same logic pattern, with the MSB carry-out resulting from OR & AND gates. The Verilog code has been written to implement summation. The MCLA Verilog code was downloaded to the Xilinx FPGA chip. It was found minimum clock period on FPGA board is 4.389ns (Maximum Frequency is 220 MHz). After the sigma delta modulator, the sampling rate must be reduced to 47 KHz which is 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 16. This is done by the CIC filter. The remaining 3 stages involve the reduction of the sampling frequency by the decimation factor of 2 only which are carried out by the first half band, droop correction and the second half band respectively. The Simulation results for all 4 stages are given in figure 7. Recursive CIC filters have been designed and investigated. Enhanced high Speed CIC filters was obtained by the pipeline structure and by using the modified carry look-ahead adder (MCLA). The evaluation indicates that the pipelined CIC filter with MCLA adder 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 CIC filter require maximum word length and also because of the recursive loop in its structure, thus power is limited by the calculation in integrator stage, so the truncation will reduced the power consumption to obtain high speed operation.

Fig. 2

 2 Fig. 2 One-stage of CIC filter block diagramN, M and R are parameters to determine the register length requirements necessary to assure no data loss. Equation (1) can be express as follow:

5 Fig. 4

 54 Fig. 4 Five-stage of truncated pipeline CIC filter include integrator and comb cell

Figure 6

 6 Fig. 5 The 8 bit MCLA structure 4 Design Results

Fig. 6

 6 Fig. 6 Comb filter frequency response for R=16, M=1 and N=5

Fig. 7

 7 Fig. 7 frequency response of (a) first half band filter (b) droop correction (c) second half band filter (d) overall decimation process , Over sampling ratio=128

Fig. 8

 8 Fig. 8 Signal spectra (a) Output sigma delta modulator SNR (b) Output CIC filter SNR 5 Conclusions


N Mahdavi
email: mahdavi_n2@yahoo.com

IEEE R Teymourzadeh

On-Chip Implementation of High Speed and High resolution Pipeline Radix 2 FFT Algorithm

A new on-chip implementation of Fast Fourier Transform (FFT) based on Radix 2 is presented. The pipeline and parallel approaches are combined to introduce a new high speed FFT algorithm which increases resolution by using floating point calculations in its structures. The design has the merits of low complexity and high speed performance. Furthermore, latency reduction is an important issue to implement the high speed FFT on FPGA. The proposed FFT algorithm shows the latency of   11 log 2 2  N N . Moreover, this algorithm has the advantage of low mean squared error (MSE) of 0.0001 which is preferable to Radix 2 FFT.

I. INTRODUCTION

Fast 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 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 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 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

Fig. 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 [8,[START_REF] Zheng | Design and implementation of a parallel real-time FFT processor[END_REF]. This block calculates the complex number in ( 1) and ( 2), as follow. Hence, one complex multiplication and two complex additions are required in this calculation. If

2 1 1 input W input output k    (1) 2 1 2 input W input output k    (2)
1 01 1 o iY X output   , 2 2 2 o o iY X output   and k k W w k iY 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]. Fig. 2, and Fig. 3, 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 k W 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) 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. Fig. 5, shows the internal structure of the RAM with the capability of reading and writing the two complex data simultaneously. The chip layout on Virtex 2 FPGA board is shown in Fig. 6.

Figure 1 .

 1 Figure 1. The FFT block diagram

Figure 2 .Figure 3 .Figure 4 .

 234 Figure 2. Pipeline floating point adder/ subtractor

  ROM. Thus, it avoids using a large number of gates in the FPGA board.

Figure 5 .

 5 Figure 5. Internal structure of the RAM

Fig. 7 ,

 7 shows the output digital signal of the new Radix-2 FFT algorithm which simulated by Modelsim software.Fig.8, shows the measured signal spectrum achieved by Radix-2 FFT algorithm for 1024 floating point complex data.

Figure 6 .Figure 7 .

 67 Figure 6. The core layout on FPGA board

ACKNOWLEDGMENT

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