Fatihcan M Atay

Dina Irofti

A Delayed Consensus Algorithm in Networks of Anticipatory Agents

We introduce and analyze a delayed consensus algorithm as a model for interacting agents using anticipation of their neighbors' states to improve convergence to consensus. We derive a necessary and sufficient condition for the system to reach consensus. Furthermore, we explicitly calculate the dominant characteristic root of the consensus problem as a measure of the speed of convergence. The results show that the anticipatory algorithm can improve the speed of consensus, especially in networks with poor connectivity. Hence, anticipation can improve performance in networks if the delay parameter is chosen judiciously, otherwise the system might diverge as agents try to anticipate too aggressively into the future.

I. INTRODUCTION

Consensus problems arise in a wide range of applications in distributed computing [START_REF] Lynch | Distributed Algorithms[END_REF], management science [START_REF] Degroot | Reaching a consensus[END_REF], flocking and swarming theory [START_REF] Vicsek | Novel type of phase transition in a system of self-driven particles[END_REF], distributed control [START_REF] Fax | Information flow and cooperative control of vehicle formations[END_REF], and sensor networks [START_REF] Olfati-Saber | Consensus filters for sensor networks and distributed sensor fusion[END_REF], among others. In these applications, multi-agent systems interact to agree on a common value for a certain quantity of interest. The interaction rule that specifies the information exchange between the agents is called the consensus protocol or consensus algorithm. The consensus problem on networks in continuous time can be formulated as ẋi = u i (t), i = 1, . . . , n,

where n is the number of agents in the network, x i ∈ R is the state of the agent i at time t, which changes under the interaction with other agents as described by the consensus protocol u i (t). The system (1) is said to reach consensus if for any set of initial conditions {x i (0)} there exists c ∈ R such that lim t→∞ x i (t) = c for all i, in which case the number c is called the consensus value.

In the classical linear case, the consensus protocol typically has the form

u i (t) ∼ n j=1 a ij (x j (t) -x i (t)).
(

) 2
where a ij are nonnegative numbers describing the pairwise interaction strength between agents. Under mild conditions related to the connectivity of the network, it can be shown that the system (1) under (2) reaches consensus from arbitrary initial conditions. A more interesting case is when the consensus protocol involves a time delay, which can 1 Fatihcan M. Atay is with the Department of Mathematics, Bilkent University, 06800 Ankara, Turkey atay@member.ams.org 2 Dina Irofti is with the Laboratoire des Signaux et Systèmes (L2S, UMR CNRS 8506), CNRS-CentraleSupelec-University Paris-Sud, 3, rue Joliot Curie, 91190, Gif-sur-Yvette, France Dina.Irofti@l2s.centralesupelec.fr come in various forms. A well-known example is the delayed consensus protocol

u i (t) ∼ n j=1 a ij (x j (t -τ ) -x i (t -τ )) (3)
which has been studied in [START_REF] Olfati | Consensus problems in networks of agents with switching topology and time-delays[END_REF]. One can view (3) as modeling delayed information processing, since the protocol feeds back the same information (x j -x i ) to the system, as in ( 2), but only after a delay τ ≥ 0. In this case, it is known that there exists an upper limit τ max such that the system (1) under the protocol (3) reaches consensus from arbitrary initial conditions if and only if τ < τ max [START_REF] Olfati | Consensus problems in networks of agents with switching topology and time-delays[END_REF]. Another type of interaction, which models delayed information transmission, is given by the consensus protocol [START_REF] Atay | Consensus in networks under transmission delays and the normalized Laplacian[END_REF], [START_REF] Atay | The consensus problem in networks with transmission delays[END_REF], [START_REF] Moreau | Stability of continuous-time distributed consensus algorithms[END_REF], [START_REF] Seuret | Consensus under communication delays[END_REF]

u i (t) ∼ n j=1 a ij (x j (t -τ ) -x i (t)) , (4)
Here the interpretation is that the information coming from a neighbouring node j takes some time τ to reach site i.

It was shown that the system (1) under the protocol (4) reaches consensus from arbitrary initial conditions regardless of the value of the delay τ as long as the network contains a spanning tree [START_REF] Atay | Consensus in networks under transmission delays and the normalized Laplacian[END_REF], [START_REF] Atay | The consensus problem in networks with transmission delays[END_REF].

In this paper we study another delayed consensus protocol where the delay comes from a quite different source, namely from the anticipatory nature of the agents. More precisely, we consider a network of intelligent agents who try to anticipate the future states of their neighbors in their interaction, which is a common situation in, e.g., economic systems. We therefore consider an anticipatory algorithm of the form

u i (t) ∼ n j=1 a ij (x j (t + τ ) -x i (t)), (5)
where xj (t + τ ) is the anticipated state of the neighbor x j at some time (t+τ ) in the future. In order to estimate the future state, the agents use a first order estimation derived from past observations, namely they employ memory. It is reasonable to expect that the memory window is about the same order of magnitude as the view into future, which will be assumed in this paper. Therefore, agent i, knowing the current state of x j (t) of a generic neighbor j and remembering its past state x j (t -τ ) as well, uses a first-order estimation to get the future state xj (t + τ ) by linear extrapolation:

xj (t + τ ) = x j (t) + x j (t) -x j (t -τ ) τ τ, = 2x j (t) -x j (t -τ ). (6)
time

x j t -τ t t + τ
first-order estimation zero-order estimation Fig. 1. Estimating the future state x j (t + τ ) of an agent j from its present and past states.

The idea is graphically summarized in Figure 1. By comparison, the classical consensus algorithm (2) can be viewed as a zero-order estimation where an agent's expectation of the short-term future of its neighbors is represented simply by the present states, xj (t + τ ) = x j (t). Substituting ( 6) into (5), we thus obtain the consensus algorithm

u i (t) ∼ n j=1 a ij (2x j (t) -x j (t -τ ) -x i (t)), (7)
which will be the focus of our study in this paper. In precise terms, we will study the convergence of the following consensus problem

ẋi (t) = 1 d i n j=1 a ij (2x j (t) -x j (t -τ ) -x i (t)), (8)
where a ij = a ji ∀i, j and d i = n j=1 a ij is the (generalized) degree of node i. Dividing the summation by the degrees d i gives rise to a normalized Laplace operator, which is a natural choice in several applications and has some advantageous properties, as will be briefly reviewed in Section II. In particular, the normalization bounds the spectrum of Laplacian regardless of the network size, thus allowing comparison of networks of very different sizes.

We note that τ in ( 8) is to be seen as a design parameter, rather than a delay imposed by system constraints as in [START_REF] Fan | Spectral graph theory[END_REF] or (4). Nevertheless, ( 8) is still a delay-differential equation and its analysis is subject to the same difficulties one faces in studying infinite-dimensional systems on Banach spaces. The purpose of this paper is to investigate if and under what conditions the system (8) can reach consensus from arbitrary initial states, and furthermore, whether the introduction of a positive τ , namely anticipation, really brings any advantages into the consensus dynamics.

The paper is organized as follows. In Section II we introduce the basic notation and review relevant background information from graph theory. Section III presents the main results by giving necessary and sufficient conditions: we show that (8) reaches consensus from arbitrary initial states if and only if τ < 1. In Section IV we present a graphical depiction of the dominant roots for arbitrary eigenmodes of the system as a function of the delay value τ , thereby deriving a universal picture applicable for any undirected graph. In Section V we give simulation results from various networks and show that a positive τ can indeed improve speed of consensus, in some cases dramatically, especially in networks with poor connectivity. Hence, anticipation can improve performance in networks of interacting agents if the parameter τ is chosen judiciously, otherwise the system can diverge as agents try to anticipate too aggressively into the future.

II. PRELIMINARIES

We briefly review some relevant notions and notations from graph theory. For details, the reader is referred to standard texts such as [START_REF] Fan | Spectral graph theory[END_REF] or [START_REF] Godsil | Algebraic Graph Theory[END_REF].

A graph G = (V, E) consists of a finite set V of vertices and a set of edges E ⊂ V × V consisting of unordered pairs of vertices. Two vertices i and j are called neighbors if (i, j) ∈ E. We consider simple, non-trivial, and undirected graphs without self-loops or multiple edges. We denote by A = [a ij ] the (weighted) adjacency matrix of the graph, where a ij = a ji > 0 if i and j are neighbors, and a ij = 0 otherwise. The degree d i of node i is defined as d i = n j=1 a ij , i.e., the sum of the elements of the i th row of A, and D = diag(d 1 , . . . , d n ) denotes the diagonal degree matrix.

The normalized Laplacian matrix is defined as

L = I n -D -1 A, ( 9
)
where n is the number of nodes in the network, I n is the identity matrix of size n. The normalized Laplacian naturally arises in a class of important problems, in particular in random walks on networks, as D -1 A is the transition matrix for probability distributions arising from such walks [START_REF] Fan | Spectral graph theory[END_REF]. The eigenvectors of L form a complete set that span R n , and the eigenvalues λ i are real numbers and can be ordered as

0 = λ 1 ≤ λ 2 ≤ • • • ≤ λ n ≤ 2.
In particular, the upper and lower bounds imply that

|1 -λ k | ≤ 1, k = 1, 2, . . . , n. (10)
The first eigenvalue λ 1 is always zero and corresponds to the eigenvector (1, 1, . . . , 1) . The second eigenvalue λ 2 , which is also called the spectral gap, is positive if and only if the graph is connected. In fact, the multiplicity the zero eigenvalue equals the number of connected components of the graph. In a connected graph, λ 2 gives an indication of how difficult it is to disconnect the graph into two large pieces by removing a small number of edges, and is thus directly related to graph connectivity. In matrix form, (8) becomes

ẋ(t) = D -1 A(2x(t) -x(t -τ )) -x(t), (11)
with x = (x 1 , x 2 , . . . , x n ) . Since L has a complete set of eigenvectors {v k }, one can write x(t) = n k=1 u k (t)v k for some scalar coefficients u k , which transforms (11) into a system of n decoupled scalar equations

uk (t) = (1 -2λ k ) u k (t) -(1 -λ k )u k (t -τ ), k = 1, . . . , n. (12)
The characteristic equation corresponding to the eigenmode [START_REF] Olfati-Saber | Consensus filters for sensor networks and distributed sensor fusion[END_REF] is

ψ k (s) := s -2(1 -λ k ) + 1 + (1 -λ k )e -sτ = 0. (13)
Consequently, the characteristic equation for the whole system [START_REF] Olfati-Saber | Ultrafast consensus in small-world networks[END_REF] can be written as

Ψ(s) := n k=1 ψ k (s) = 0. ( 14
)
Note that s = 0 is always a characteristic root for the first factor ψ 1 (s) = s -1 + e -sτ corresponding to the first eigenmode, λ 1 = 0. Thus, points on the synchronization subspace spanned by v 1 = (1, 1, . . . , 1) can be at best neutrally stable. If that is the case, and in addition lim t→∞ u k (t) = 0 for all k ≥ 2, then the system converges to a point on v 1 , i.e. it reaches consensus, from arbitrary initial conditions. This clearly happens if and only if zero is a simple root of Ψ and all other roots of Ψ have negative real parts. Moreover, in this case the speed of convergence from general initial conditions depends on the slowest of these modes u k , k ≥ 2. Hence, we factor ( 14) into directions along and transverse to the synchronization subspace span(v 1 ) as Ψ(s) = ψ 1 (s) Ψ(s), where

Ψ(s) := n k=2 ψ k (s), (15)
and use the transverse part to quantify the speed of convergence, which motivates the following definition. Definition 1: The number s * ∈ C is called the dominant transverse root of the consensus algorithm (or dominant root, for short) if Ψ(s * ) = 0 and all roots s of Ψ satisfy Re(s) ≤ Re(s * ).

When τ = 0, system (8) reduces to the classical consensus problem (1)-( 2), and the characteristic equation ( 14) reduces to

Ψ(s) = n k=1 (s + λ k ); (16)
so, the dominant root is given by the second smallest eigenvalue λ 2 of the Laplacian. Therefore, λ 2 and the algebraic connectivity of the graph play an important role for convergence speed (how fast the network reaches consensus), small values of λ 2 implying a slow convergence. Note that λ 2 can be arbitrarily small in connected networks, depending on the connection structure.

III. CONVERGENCE OF THE CONSENSUS ALGORITHM

We begin by some observations on the roots of a certain complex function.

Lemma 2: The function

ψ(s) = s -β 1 -e -s , β ∈ R, (17)
has a simple root at zero and all its other roots have negative real parts if and only if β < 1.

(18) Proof: Clearly ψ(0) = 0; so zero is always a root of ψ. Moreover, ψ (0) = 1 -β is nonzero if and only if β = 1, in which case zero is a simple root. We note that ψ(s) is a special case of the function

ψ(s) := s -a 1 -a 2 e -s , a 1 , a 2 ∈ R. ( 19
)
which has been studied in the classical paper of Hayes [START_REF] Hayes | Roots of the transcendental equation associated with a certain difference-differential equation[END_REF].

The properties for ( 19) is therefore well-known; here we recall the stability region depicted in Figure 2. In particular, for the parameter values on the semi-infinite line L = {a 1 , a 2 : -a 2 = a 1 < 1} in the figure, ψ has a simple root at zero and all its remaining roots have negative real parts. Since ψ is a special case of (19) with a 1 = -a 2 = β, condition (18) follows from considering the line L in Figure 2.

We can now state the main convergence result for the consensus problem (8) of anticipating agents.

Theorem 3: The system (8) defined on a connected undirected graph reaches consensus from arbitrary initial conditions if and only if τ < 1.

(20) Proof: We will show that the characteristic equation ( 14) has a simple root at zero and all the remaining roots have negative real parts if and only if condition (20) holds. Consider first the roots of the first factor ψ 1 (s) = s-1+e -sτ in [START_REF] Seuret | Consensus under communication delays[END_REF]. By a change of variable s = sτ , we can equivalently consider the roots of

ψ 1 (s ) = s -τ + τ e -s .
Lemma 2 gives that ψ 1 , and therefore ψ 1 , has a simple root at zero and all the other roots have negative real parts if and only if (20) holds. It then suffices to show that all roots of the remaining factors ψ k , k = 2, . . . , n, in (14) have negative real parts under condition (20). Now, the roots s of ψ k satisfy

s = a k + b k e -sτ , (21)
with

a k = 2(1 -λ k ) -1 (22) b k = -(1 -λ k ). ( 23
)
For τ = 0, (21) reduces to

s = a k + b k = -λ k < 0 for k ≥ 2, ( 24
)
and the roots are on the open left complex plane. We next look for roots that may cross the imaginary axis as τ is increased from zero. Letting s = iω, ω ∈ R, the imaginary part of (21) gives Notice from ( 21) and ( 24) that ω = 0. Hence, dividing (25) by |ω|,

ω = -b k sin(ωτ ). Therefore, |ω| = |b k sin(ωτ )| ≤ |b k ωτ |. ( 25
)
1 ≤ |b k τ | = |τ (1 -λ k )| ≤ τ,
where we have substituted for b from (23) and used [START_REF] Moreau | Stability of continuous-time distributed consensus algorithms[END_REF]. This shows that, as long as condition (20) holds, no roots can cross the imaginary axis, and so all roots of ψ k for k = 2, . . . , n have negative real parts. This completes the proof of the theorem.

IV. COMPUTATION OF DOMINANT ROOTS

The performance of the consensus algorithm depends on the transverse dominant root of the problem, as defined in Definition 1. We use Lambert W function to solve for the characteristic roots.

Recall that the Lambert W function is defined as the inverse function of the mapping f (z) = ze z for z ∈ C [START_REF] Corless | On the Lambert W function[END_REF]; in other words, W (z) satisfies

W (z)e W (z) = z. ( 26
)
Since f is not one-to-one, W (z) is multi-valued. We let W 0 denote the principal branch of the Lambert function. Proposition 4: The root of the characteristic equation ( 13) having the largest real part is given by

s = 1 τ W 0 (τ b k e -a k τ ) + a k , ( 27
)
where W 0 is the principal branch of the Lambert W function and a k and b k are defined in ( 22)-( 23). Consequently, the dominant transverse root of the consensus problem equals

max 2≤k≤n 1 τ W 0 (τ b k e -a k τ ) + a k . (28)
Proof: As seen in the proof of Theorem 3, the roots of ψ k satisfy equation ( 21), which can be re-written as 13) of the characteristic equation. The region above the black line is when there is a root with positive real part. Note that, since zero is always an eigenvalue of the Laplacian in every network, the condition τ < 1 actually defines the region for reaching consensus, in accordance with Theorem 3. from which, by the definition (26) of Lambert function, one immediately has s = W (τ b k e -a k τ ). Going back to the original variable s shows that the roots of ψ k are given by

s -a k = b k e -(s-a k )τ e -a k τ . A change of variables s → (s -a k )τ gives s = τ b k e -a k τ e -s ,
s = 1 τ W (τ b k e -a k τ ) + a k ,
It follows by a recent result from [START_REF] Shinozaki | Robust stability analysis of linear timedelay systems by Lambert W function: Some extreme point results[END_REF] that the root with largest real part is given by the principal branch of the Lambert function, which establishes (27). Definition 1 then implies (28). Using Proposition 4 and equation ( 27), we calculate the dominant root for any eigenmode (12) of system (8) corresponding to a generic Laplacian eigenvalue λ. This gives a universal map of the dominant roots of the consensus problem [START_REF] Hayes | Roots of the transcendental equation associated with a certain difference-differential equation[END_REF] for any graph topology and delay value, which is depicted in Figure 3.

In the color map of Figure 3, lighter colors correspond to more negative real parts for the roots. Hence one notes, from the change in color as one moves vertically upwards from the horizontal axis, that a positive value of τ can indeed improve convergence speed for a given eigenmode. In the next section we will confirm this observation through actual simulation of several networks.

V. SIMULATION RESULTS

We illustrate and elaborate on the analytical results using numerical simulations in three example networks with various connection topologies. We compare the performance of the delayed anticipatory algorithm with the classical consensus algorithm. In all pairwise comparisons simulations are started from random initial conditions but identical ones for both algorithms. Network 1: Circular network made up of 20 vertices, where each vertex has two neighbours, one on each side (see Figure 4). We first check the converge condition (20) of Theorem 3. Figure 5 shows the comparison between results obtained with τ = 0.7 and τ = 2, respectively, for which the system converges or diverges, affirming condition (20). The convergence criterion depends only on τ and is independent of the network structure, as long as the latter is connected.

We next take τ = 0.7 for Network 1 and compare it with the classical undelayed algorithm τ = 0. Figure 6 shows that the speed of convergence to consensus is much faster under the anticipatory algorithm. This is confirmed from another point of view in Figure 7, which plots the standard deviation of the agents' states over time. The comparison makes it clear that the anticipatory algorithm performs much better. We note that the circular graph configuration has a small spectral gap λ 2 , and therefore converges poorly under the classical undelayed consensus protocol. However, the same network exhibits a dramatic improvement in convergence under the anticipatory protocol with τ = 0.7. Network 2: Circular network made up of 20 vertices, where each vertex has four neighbours, two on each side (see Figure 4). This network is similar to the initial setup of used in [START_REF] Olfati-Saber | Ultrafast consensus in small-world networks[END_REF], where the author demonstrated that convergence to consensus can be improved by random rewirings of the links en route to a small-world network configuration. Here, we will accomplish a similar improvement by using the anticipatory consensus algorithm instead of rewiring the network. Figure 8 shows the time evolution of the agents' states in Network 3 under the anticipatory algorithm with τ = 0.5, and compares it with the classical consensus algorithm with τ = 0. It is seen that the convergence speed is increased without the need to rewire the network. Network 3: An Erdős-Rényi random undirected graph with 20 nodes. If the edges of Network 2 are randomly rewired, the consensus performance increases monotonically at each step of rewiring, as shown in [START_REF] Olfati-Saber | Ultrafast consensus in small-world networks[END_REF]. After repeated random rewirings, the network approaches a random network, which should then have very good convergence properties. We therefore generate a random network with (approximately) the same number of edges as in Network 2, which is accomplished by taking p = 0.21 as the probability of having an edge between a pair of vertices. Figures 9 and 10 show, once again, that consensus is reached faster under the anticipatory algorithm. We conclude that using an anticipatory algorithm can lead to a better consensus performance than rewiring the network, which is useful because altering the network structure is not always possible in real networks. For reasons of clarity we have illustrated the results on networks with 20 agents, but the results are similar for larger networks.

Fig. 2 .

 2 Fig. 2. Stability region of equation (19) in a 1 -a 2 parameter space.

Fig. 3 .

 3 Fig. 3. Map of the dominant characteristic root of eigenmodes corresponding to a generic Laplacian eigenvalue λ and delay value τ . The colour represents the real part of the dominant root of a factor (13) of the characteristic equation. The region above the black line is when there is a root with positive real part. Note that, since zero is always an eigenvalue of the Laplacian in every network, the condition τ < 1 actually defines the region for reaching consensus, in accordance with Theorem 3.

Fig. 4 .

 4 Fig. 4. Network 1 (left) and Network 2 (right) used in the simulations. Each one is a regular network of 20 vertices arranged on a circle, where each vertex has 2 or 4 neighbors, respectively.

Fig. 5 .

 5 Fig.5. Time evolution of agents' states in[START_REF] Hayes | Roots of the transcendental equation associated with a certain difference-differential equation[END_REF] in the configuration of Network 1 starting from arbitrary initial conditions. In the top figure τ = 0.9 and the system converges towards consensus, whereas in the bottom figure τ = 1.1 and the system diverges.

Fig. 6 .

 6 Fig. 6. Time evolution of agents' states in Network 1 under the classical consensus protocol obtained with τ = 0 (top figure) and the anticipatory protocol obtained with τ = 0.7 (bottom figure), showing that the system reaches consensus much faster under the anticipatory algorithm.

Fig. 7 .

 7 Fig. 7.Time evolution of the standard deviation of agents' sates in Network 1, plotted for τ = 0 (dashed line) and τ = 0.7 (solid line), showing the superior performance of the anticipatory algorithm.

Fig. 8 .Fig. 9 .Fig. 10 .

 8910 Fig. 8. Time evolution of agents' states in Network 2 under the classical consensus protocol (top figure) and the anticipatory protocol with τ = 0.5 (bottom figure), demonstrating the superior performance of the latter algorithm.

ACKNOWLEDGMENT The authors thank the ZiF (Center for Interdisciplinary Research) of Bielefeld University for their support within the cooperation program Discrete and Continuous Models in the Theory of Networks, where this problem was initiated. Part of the research was carried out when DI visited the Max Planck Institute for Mathematics in the Sciences, Leipzig, Germany, in Summer 2015 under financial support from DAAD Short-Term Grants 2015 (57130097) and from L2S Laboratory, France. FMA acknowledges support from the European Union's Seventh Framework Programme (FP7/2007-2013) under grant agreement no. 318723 (MATHEMACS).


Sylvain Badey
email: sylvain.badey@inrap.fr

Xavier Rodier
email: xavier.rodier@univ-tours.fr

Spatial analysis for an efficient use of data from trial trenching

Number of archaeological features for each period

grid implantation on trial trenches >>

Differences

Trial trenching

The practice of preventive archaeology in France takes place in two steps: first, preliminary survey ("diagnostic" in french) and second, excavations. In rural areas this means an opening in the form of trial trenches. This continuous trenching pattern is performed using mechanical devices. Trenches (2.5m width) are evenly spaced (aprox. 18m) so as to cover around 10% of the surface. This first phase aims to provide sufficient information -on the nature, extent, chronology and degree of preservation of the sites in view to prescribe or not an excavation. The areas affected by these archaeological surveys are considerable, in some cases tens or hundreds of hectares.

On the 226 ha development project in Ozans (commune of Etrechet, Center of France), 412 trenches were opened for a cumulative total length of 124 km and a total area of 248,032 sqm. The overall open rate is 11%. Following these diagnostics, three excavations have been prescribed and performed in 2011.

Aims of the study

The study aims at testing and evaluating methods used in spatial analysis to propose archaeological hypothesis and compare them with those from the field. We focused on the geographic (location), geometric (dimensions) and chronological properties (dating) of archaeological remains. The aim is to estimate the contribution of spatial analysis, on the one hand to interpret the diagnostic's results, on the other hand to understand land use and settlements pattern in this area. Our methods are both cartographic with the grid analysis and statistic with data clustering.

Grid Analysis

The use of a grid analysis (or tessellation) overcomes the limitations of the the trial trenches implementation which creates a mask for the representation of archaeological remains.

The choice of the cell size defines the resolution of the study and of the representation of the research area. The area was divided into 1024 cells of 50 m square that intersect at least two trenches.

Several criteria are used for dating archaeological remains excavated during a diagnostic: the typo-chronological study of artefacts, stratigraphic or topological relations between the remains and ancient iconographic sources. In our project, datings were simplified and reclassified in a four classes called PERIODS: Protohistory, Antiquity, Middle Ages and Modern Era.

Modelisation and features indices

Summarize archaeological features in each cell ("addressed grid") is not relevant. Instead we used for each time class a "ventilated grid" with the "zonal clipping" algorithm. It follows a geometric principle: the intersection of the area calculation between the features area and the square.

In each cell the surface of archaeological features is weighted by the total number of remains of the period in order to obtain a more homogeneous class distribution between the different periods. The index obtained by cell was then classified with the Jenks algorithm. Six classes were defined from [0.1%-0.5%] (light gray) to [5%-35%] (black).

Finally, to represent distribution changes of the vestiges between two successive periods, the value of each cell for the earliest period was subtracted from the value of the corresponding cell for the other period. Here again six classes were defined. The lowest class [-30 to -3] in dark blue represents a depreciation of the index, meaning a decrease in the proportion of facts in the most recent period compared with the earliest period. The highest one in dark red shows conversely an increase in the index.

Data clustering

Data clustering aims at determining the geographic properties of archaeological feature distribution and organization for each period, then at defining and representing feature clusters. To obtain a point cloud, archaeological vestiges, initially represented by polygons, are reduced to their centroids.

Data clustering involves three steps:

1-Nearest Neighbour: characterize distribution

The method is based on a first-order property of the point cloud: the average distance from any point to its nearest neighbour. This distance is compared with the expected (theoretical) distance of a random distribution called null hypothesis. A K-Order is set to study the distance to the first nearest neighbour and then to the second, until the K-th one.

The functions for all periods point clouds are represented in a graph with K-Order in x-axis and the R statistic in y-axis. The Expected (random distribution) value is 1. For each period, the more R function tends to 0 the more distribution of the point cloud is concentrated.

Results: For all periods, scatter points have a relatively grouped distribution with R statistic approaching 0. Results: Unlike the first-order analysis, the point set of Protohistory emerges clearly from those of other periods with a tendency to lower aggregation. Point clouds of the three following periods are similar, with a strong trend of clustering.

2-Ripley

The curve reaches a maximum and then decreases gradually until the confidence interval (IC on the graph).

3-The «moving windows method»:

Represents aggregates with a spatial scan algorithm A spatial scan algorithm allows a local analysis of a set of points, ie to determine significant local aggregates. This spatial scan algorithm is called "moving windows method" because it identifies the aggregates within a circular window that scans the study area.

The algorithm points out concentration windows that are above what could be expected in the case of a null hypothesis.

The spatial scan was performed for each period. Identified aggregates are represented as deviational ellipses around the centroids of the identified clusters.

Results: Unlike the grid analysis which only allowed the comparison of the remain's concentrations for two periods, deviational ellipses -derived from the spatial scan-can all be represented together on the same map to overlay and compare aggregates for all periods.

Results

The result of this study is synthesized in the superposition of deviation ellipses and grid analysis maps. It allows a synthetic reading of the diagnostic data based on a robust and reproducible spatial analysis protocol.

Results show that it is possible to check interpretive hypothesis on the distribution of the remains. Indeed, spatial analysis reveals patterns by periods, that must be confronted to the essential archaeological interpretation.

Results meet the two objectives of an archaeological assessment. First, they are useful for the archaeologist to interpret the remains and to understand the dynamics of land-use and settlements pattern. Secondly, as decision-making tool, they provide elements for the authorities to deal with the archaeological sites (excavation or preservation).

  's K (Besag's L) function: characterizes distribution and determines scales of aggregates Ripley K function compares the density expected under the null hypothesis to the observed density by drawing search-circles of increasing radius. The various search radius produce a correlogram representing the spatial aggregation function (y-axis) and the search distance (x-axis). Scales of aggregates are identified by the inflection points of the function.


D Mazières

E Kohler

Calvin & Hobbes

Human basophil degranulation triggered by very dilute antiserum against IgE

Open education is a collective term to describe institutional practices and programmatic initiatives that broaden access to the learning and training traditionally offered through formal education systems.

OPEN DATA

Open data may include non-textual material such as maps, genomes, connectomes, chemical compounds, mathematical and scientific formulae, medical data and practice, bioscience and biodiversity (wikipedia)

"Datasets are available upon request by contacting the corresponding author" → How long will the email address last ? "Code can be found in the appendix" → Maybe, maybe not… OPEN DATA

OPEN DATA

A second concern held by some is that a new class of research person will emerge -people who had nothing to do with the design and execution of the study but use another group's data for their own ends, possibly stealing from the research productivity planned by the data gatherers, or even use the data to try to disprove what the original investigators had posited.There is concern among some front-line researchers that the system will be taken over by what some researchers have characterized as research parasites

The New England Journal of Medicine (2016) Open data is the idea that some data should be freely available to everyone to use and republish as they wish, without restrictions from copyright, patents or other mechanisms of control.

FAIR Data : Findable, Accessible, Interoperable, Re-Usable

OPEN METHODOLOGY OPEN METHODOLOGY

The (ugly) hacking way: Figshare is an online digital repository where researchers can preserve and share their research outputs, including figures, datasets, images, and videos.

Zenodo is a research data repository created by OpenAIRE and CERN to provide a place for researchers to deposit datasets.

ArXiv is a repository of electronic preprints of scientific papers in the fields of mathematics, physics, astronomy, computer science, quantitative biology, statistics, and quantitative finance, which can be accessed online.

GitHub is a web-based Git repository hosting service that offers all of the distributed version control and source code management functionality of git as well as adding its own features.

SOME VILlAIN

The publishers Springer and IEEE are removing more than 120 papers from their subscription services after a French researcher discovered that the works were computer-generated nonsense (2014)

SOME VILlAIN

Wiley is using fake DOIs to trap web crawlers and researchers. Wiley's fake DOIs are not stable, and create the potential for DOI collisions, which break the system (2016)

  Green access / Gold access / Hybrid access Nobody pays (sort of…) Author pays (a lot usually) Everybody pays (what the f…?)

  I consider that the Golden Rule requires that if I like a program I must share it with other people who like it. Software sellers want to divide the users and conquer them, making each user agree not to share with others. I refuse to break solidarity with other users in this way.

	NEWPLAYERS
	github : the open-source way to ORCID (Open Researcher and Contributor ID) is a nonproprietary alphanumeric code to
	host, create and curate knowledge uniquely identify scientific and other academic authors and contributors
	>>> data = load("data.txt")
	>>> mean, std = data.mean(), data.std()
	>>> file = file.open("analysis.txt")

p=0.052, click, click, click, p=0.049, save

The (bad) excel way:

click, click, select, click, click, move, del, click, reclick, save, unclick, ctrl-z, ctrl-z, click, enter, click, click, move, click, re-click, save

The (good) reproducible way: >>> write("mean: %f, std: %f" % (mean, std)) >>> exit() $ git commit -a -m "Computed results from 24/11/2016" I have heard from graduate students opting out of academia, assistant professors afraid to come up for tenure, mid-career people wondering how to protect their labs, and senior faculty retiring early, all because of methodological terrorism. APS Observer (2016) OPEN METHODOLOGY OPEN SOURCE W H A T E LS E ? GNU Manifesto, Richard M. Stallman, 1985 OPEN SOURCE W H A T E LS E ?

successstory

(S E LF -A D VE R TI S E M E N T)

NEW incentives

But mostly,


Hatam Abdoli
email: abdoli@eng.ui.ac.ir

Hooman Nikmehr
email: nikmehr@eng.ui.ac.ir

Naser Movahedinia
email: naserm@eng.ui.ac.ir

Florent De Dinechin
email: florent.de-dinechin@insa-lyon.fr

F Dinechin

Improving Energy Efficiency of OFDM Using Adaptive-Precision Reconfigurable FFT

Keywords: Quantization noise, Reconfigurable design, FFT, OFDM, BER, Energy efficiency

Being an essential issue in digital systems, especially battery-powered devices, energy efficiency has been the subject of intensive research. In this research, a multi-precision FFT module with dynamic runtime reconfigurability is proposed to trade off accuracy with the energy efficiency of OFDM in an SDR-based architecture. To support variable size FFT, a reconfigurable memory-based architecture is investigated. It is revealed that the radix-4 FFT has the minimum computational complexity in this architecture. Regarding implementation constraints such as fixed-width memory, a noise model is exploited to statistically analyze the proposed architecture. The required FFT word-lengths for different criteria -namely BER, modulation scheme, FFT size, and SNR -are computed analytically and confirmed by simulations in AWGN and Rayleigh fading channels. At run-time, the most energyefficient word-length is chosen and the FFT is reconfigured while the required application-specific BER is met. Evaluations show that the implementation area and the number of memory accesses are reduced. The results obtained

from synthesizing basic operators of the proposed design on an FPGA show energy consumption experienced a saving of over 80%.

Introduction

Over the past decades, wireless communication devices, such as mobile phones have rapidly developed from voice-only into smart-phones. Such an evolution is not possible unless requirements including higher computational performance, higher flexibility in programmability (to reduce production costs), greater efficiency in energy consumption and higher design reusability across some applications are appropriately met [START_REF] Woh | Mobile supercomputers for the next generation cell phone[END_REF].

To use the radio-frequency spectrum more efficiently, new communication techniques, such as orthogonal frequency division multiplexing (OFDM) have been proposed, each with its own rapidly increasing standards and modes [START_REF] Stotas | On the throughput and spectrum sensing enhancement of opportunistic spectrum access cognitive radio networks[END_REF]. To be supported by communication devices, cost-effective and practical approaches to reuse the same hardware resources for different standards/modes need to be developed. To realize this reusability, the system hardware should be partly/entirely flexible (reconfigurable) and/or reprogrammable. The required flexibility, which significantly contributes to cost reduction, introduces software defined radio (SDR) solutions in wireless technology.

The functionality of a portable radio device not only depends on its battery capacity but also on the device's energy consumption behavior. The gap between the battery capacity delivered to and the power demands from such devices is expected to widen since the former is estimated to improve by about 10% per year, while the computational performance needs to increase ten times every five years [START_REF] Van Berkel | Multi-core for mobile phones[END_REF].

Extensive use of energy-hungry applications such as video games, mobile P2P, video sharing, mobile TV, and 3D services signifies the energy consumption crisis. Therefore, research in this prominent issue [START_REF] Feng | A survey of energy-efficient wireless communications[END_REF][START_REF] Duan | Exploring memory energy optimizations in smartphones[END_REF] that considers the trade-off between design flexibility and energy efficiency is increasingly needed. Hence, to find the best scheme for the trade-off, different approaches such as designing architectures well-matched to algorithms and their run-time requirements may decrease the energy gap in SDR architectures.

OFDM has increasingly been adopted not only in the SDR architectures of wireless communications but also in wired and optical transmitters since it efficiently handles the frequency selective fading phenomenon, is robust against narrowband interference and impulse noise and provides an enhanced channel capacity. Nowadays, many digital communication standards and systems including UWB, WiMAX, WLAN, LTE, DVB-T, and ADSL have agreed to adopt OFDM standard [START_REF] Guan | Hierarchical design of an application-specific instruction set processor for high-throughput and scalable FFT processing[END_REF].

As shown in Table 1, in the heart of most OFDM-based systems, the ubiquitous fast Fourier transform (FFT), with various sizes (N) and throughputs, is required. Designing an energy-efficient reconfigurable FFT system suitable for different applications and standards has become an intriguing topic of study [START_REF] Gijung | Scalable FFT processor for MIMO-OFDM based SDR systems[END_REF][START_REF] Airoldi | Design and implementation of a power-aware FFT core for OFDM-based DSA-enabled cognitive radios[END_REF][START_REF] Patyk | Low-power application-specific FFT processor for LTE applications[END_REF]. Optimum implementation of the FFT block in DSP systems may seriously improve their essential design aspects, such as energy efficiency, speed, and accuracy. The next generation of wireless communication systems (5G) and cognitive radio (CR) devices [START_REF] Haykin | Cognitive radio: Brain-empowered wireless communications[END_REF] intend to significantly and dynamically improve spectrum usage, data rates, and energy efficiency. NC-OFDM (Non-Contiguous OFDM) [START_REF] Rajbanshi | An efficient implementation of NC-OFDM transceivers for cognitive radios[END_REF] is a promising spectral agile variant of OFDM for dynamic spectrum aggregation [START_REF] Bogucka | Dynamic spectrum aggregation for future 5G communications[END_REF]. According to the fast-changing wireless systems where various standards/modes should be supported, NC-OFDM CR systems need to change modulation schemes, the number of subcarriers, and FFT/IFFT size at run-time [START_REF] Ferreira | Reconfigurable NC-OFDM processor for 5G communications[END_REF].

Traditionally, wireless transceivers are designed to deal with the worst-case operating conditions. Particularly in baseband digital processing units, data and operator word-lengths are chosen to be large enough (oversized) to cope with the worst unfavorable system conditions, such as very low signal-to-noise ratio (SNR). However, by using adaptive word-length processing, the system word-length is changed dynamically at run-time in order to deal with system conditions and performance requirements [START_REF] Nguyen | Dynamic precision scaling for low power WCDMA receiver[END_REF]. The use of adaptive precision (word-length) compromises the system precision to improve energy efficiency when the error-tolerable system can work properly with less accuracy.

The objective of this study is to introduce a flexible design using a set of criteria, including FFT size (N), the required SNR, maximum tolerable bit error rate (BER), the proper modulation scheme, and energy considerations, in order to select a specific configuration from a set of pre-defined configurations for the system to operate accordingly. Optimized allocation of hardware resources to support different configurations and to select the best system parameters based on the selection criteria leads to significant reduction in the area and the energy consumption of the implemented design.

The flexibility can be achieved through resizing the word-length of the reconfigurable FFT operands. Reducing the word-length decreases the VLSI area, the energy consumption, and the FFT precision; however, the system needs to be able to tolerate some proportional errors [START_REF] Korkmaz | Energy , performance , and probability tradeoffs for energy-efficient probabilistic CMOS circuits[END_REF]. Further, it is clear that reducing the precision and VLSI area of FFT leads to increase the speed (throughput) of processing. Based on the required accuracy, this research calculates the tolerable error for different conditions and determines the corresponding acceptable FFT word-length. Accordingly, there is a tradeoff between accuracy (error probability) and energy efficiency. The system can be optimized by choosing appropriate parameters and configuration, based on the channel conditions and system properties.

The contributions of this article can be pointed out as

• Unlike the previous studies, our study takes into account the role of trivial multipliers in radix-8 and radix-16 when computing the FFT hardware complexity. Hence, the radix-4 representation with the lowest complexity is chosen. • A reconfigurable memory-based FFT is proposed to provide the required flexibility for SDR. • A noise analysis for the proposed architecture is presented, considering the implementation constraints. BER is expressed analytically based on SNR and signal to quantization noise ratio (SQNR), to find the minimum required FFT word-length in AWGN and Rayleigh fading channels. • An energy-efficient memory organization is proposed to dynamically provide the required word-length of FFT.

The rest of this article is organized as follows. A brief review of the existing literature is presented in Sect. 2. The FFT algorithm and the proposed reconfigurable architecture are discussed in Sect. 3. The noise model, the statistical analysis of the variable length FFT, and the analytical expression of BER are explained in Sect. 4. In Sect. 5, the proposed multi-precision FFT implanted inside an OFDM receiver is simulated and the results are compared with the analytical results. In addition, energy saving is estimated in this section for different configurations. Sect. 6 concludes the article.

Literature Review

In DSP processors, word-length optimization is to find the best format of data processing in order to decrease the area and energy consumption of the digital system. Traditionally, most previous works have focused on fixed (finite) word-length optimization where the data format and operator word-lengths are chosen to deal with the worst case conditions, like a low SNR in a noisy channel in wireless communication systems. Word-length optimization problem can be divided into two sub problems: range analysis and precision analysis [START_REF] Menard | DSP code generation with optimized data word-length selection[END_REF].

There are proposed three methods to compute the required range/precision of digital arithmetic circuits:

• Dynamic analysis, also known as simulation-based method, evaluates the data-flow graph (DFG) of the system; hence, it is not fast, scalable, and robust enough [START_REF] Nehmeh | Fast integer wordlength optimization for fixed-point systems[END_REF][START_REF] Kim | Dynamic wordlength calibration to reduce power dissipation in wireless OFDM systems[END_REF][START_REF] Cladera | Energy-aware computing via adaptive precision under performance constraints in OFDM wireless receivers[END_REF]. • Static analysis, also called analytical method, propagates inputs and errors through the DFG of the design and evaluates the outputs through statistical analysis [START_REF] Lee | Fine grain precision scaling for datapath approximations in digital signal processing systems[END_REF][START_REF] Chang | On the fixed-point accuracy analysis of FFT algorithms[END_REF][START_REF] Bhattacharyya | Optimization of number representation. Handbook of Signal Processing Systems[END_REF]]. • Hybrid schemes [START_REF] Rocher | Analytical approach for numerical accuracy estimation of fixed-point systems based on smooth operations[END_REF][START_REF] Caffarena | SQNR estimation of fixed-point DSP algorithms[END_REF], which take the advantages of both dynamic and static methods.

The authors in [START_REF] Yoshizawa | Use of a variable wordlength technique in an OFDM receiver to reduce energy dissipation[END_REF][START_REF] Kim | Dynamic wordlength calibration for energy reduction FFT processors in wireless LAN[END_REF] propose a dynamic word-length optimization technique to improve energy efficiency. In their approach, the higher the SNR, the more number of the lower significant bits of the data paths is set to zero. However, this method requires dedicated training symbols and a high number of iterative operations to find the correct word-length. This increases the processing overhead and the number of iterative operations that consequently decrease energy efficiency.

In [START_REF] Novo | Scenario-based fixed-point data format refinement to enable energy-scalable software defined radios[END_REF], the trade-off between energy and accuracy is investigated in an SDR platform and the FFT word-length is optimized in an OFDM system using intensive simulations. However, this scheme is limited to only 8-and 16-bit word-length processing and also it is not clear how the circuit switches between the two configurations at run-time. Furthermore, the adaptation procedure is applicable to only very few modulation schemes and coding rates. In this approach, the FFT hardware architecture is not explored and there is not enough detail on reconfiguration time overhead.

Recently, a dynamic word-length tunable FFT architecture for a wireless system is proposed where the word-length is scaled according to the run-time conditions such as SNR. In these scenario-oriented methodologies, data format refinement is satisfied based on the run-time conditions and the best working scenario for the current conditions is found, chosen and applied at run-time [START_REF] Lee | Fine grain precision scaling for datapath approximations in digital signal processing systems[END_REF][START_REF] Cladera | Energy-aware computing via adaptive precision under performance constraints in OFDM wireless receivers[END_REF].

An analytic dynamic precision scaling (DPS) method is adopted in [START_REF] Lee | Fine grain precision scaling for datapath approximations in digital signal processing systems[END_REF] in order to find the best word-length for each stage of the pipelined FFT, which seeks to reduce the time needed to find the optimum word-length and to decrease the power consumption. However, this approach only applies to fractional bits, (the integer bits are not considered) and the word-lengths of the twiddle factors and the inputs are assumed to be the same. In addition, this architecture only supports fixed size FFT architectures (only for a 256point FFT). Furthermore, the power consumed by SRAMs and the memory accesses are not considered in the analysis, either.

A simulation-based DPS OFDM receiver is proposed in [START_REF] Cladera | Energy-aware computing via adaptive precision under performance constraints in OFDM wireless receivers[END_REF]. This design improves energy efficiency by tuning the run-time processing word-length, based on periodic estimation of channel conditions while the required BER is satisfied. Nevertheless, to estimate the energy saving, only a cost function for the arithmetic operations is used and other important aspects of the design such as the memories and buses, the control unit and the reconfiguration overhead are not included in the evaluation.

In [START_REF] Chen | A low-memory-access length-adaptive architecture for 2 n -point FFT[END_REF], a reconfigurable pipelined architecture is proposed to compute variablesize FFT. Since the authors identify that the major energy dissipation is consumed by memory, they reduce memory accesses by decreasing the number of FFT stages. However the data-path width is not multi-precision and is only limited to 24 bits with FFT size restricted to powers of two.

Lee et al. [START_REF] Lee | A low-area dynamic reconfigurable MDC FFT processor design[END_REF] present a low-area dynamic reconfigurable pipelined FFT architecture for wireless networks. The method employs a four-path multipath delay commutator (MDC) in order to increase FFT processing throughput and power efficiency. The architecture only supports 64-, 128-and 256-point FFT while the reconfiguration time and circuit overhead are large.

A run-time reconfigurable FFT processor is presented in [START_REF] Ferreira | Reconfigurable FPGA-Based FFT processor for cognitive radio applications[END_REF] to support various FFT sizes and throughputs of 3G and 4G wireless standards using a mixed-radix pipelined architecture. The processor is suitable for cognitive radio applications and improves energy efficiency by enhancing resource usage efficiency and power saving. However, the reconfiguration time overhead is relatively high and the arithmetic operations and data-path width are limited to 16 bits.

Overall, to the best of our knowledge, the required word-length (precision) of reconfigurable FFT in different OFDM applications with various parameters (N, BER, SNR, modulation scheme, channel type) are not investigated analytically and are not specified precisely in the simulation-based methods. Hence, in this paper, these word-lengths are scrutinized analytically and verified by simulation. A feasible hardware architecture is also developed to implement the proposed multi-precision reconfigurable memory-based FFT with comparably low reconfiguration time overhead.

Proposed Memory-Based FFT Architecture

The pervasive FFT block is one of the main modules in DSP Processors, and more specifically in communication devices.The FFT is a fast implementation for discrete Fourier transform (DFT) expressed as [START_REF] Oppenheim | Discrete-Time Signal Processing[END_REF] x

k = N -1 n=0 d n exp - j2πnk N (k = 0, 1, 2, ..., N -1) (1)
where d n represents the input signal samples in the time domain, x k is their output in the frequency domain and N is the number of FFT points (FFT size).

Overall Structure

Although there are very few approaches focusing on the floating-point FFT [START_REF] Beulet Paul | Low power reconfigurable FP-FFT core with an array of folded DA butterflies[END_REF][START_REF] Pedram | A highly efficient multicore floating-point FFT architecture based on hybrid linear algebra/FFT cores[END_REF], most of the energy-efficient designs concentrate on the fixed-point FFT, mostly due to its less complexity and lower power dissipation. In the multimode systems, it seems to be more effective to have a reconfigurable FFT unit in order to achieve the required word-length, accuracy, speed and consequently, more efficient energy consumption.

Common major FFT architectures used in OFDM systems are compared in Table 2. The comparison includes reconfigurability (flexibility) and hardware complexity of the FFT since these parameters greatly affect energy efficiency of the SDR system. The table shows that among the three FFT design approaches, the memory-based architecture [START_REF] Chang | A novel memory-based FFT processor for DMT/OFDM applications[END_REF] can be the best choice for a reconfigurable word-length FFT. In the other two, the fully-parallel architecture does not provide any flexibility at all and the pipeline architecture supports only a low degree of reconfigurability on the FFT size.

Although some designs are developed for reconfigurable pipeline FFT processors [START_REF] Sarada | Reconfigurable FFT processor -A broader perspective survey[END_REF][START_REF] Xiao | Low-cost reconfigurable VLSI architecture for fast Fourier transform[END_REF][START_REF] Vennila | Dynamic partial reconfigurable FFT for OFDM based communication systems[END_REF][START_REF] Cho | Pipelined FFT for wireless communications supporting 128-2048 / 1536-point transforms[END_REF][START_REF] Janakiraman | Coarse grained ADRES based MIMO-OFDM transceiver with new radix-2 5 pipeline FFT/IFFT processor[END_REF], their flexibilities are limited only to very few FFT sizes and as a result, the hardware overhead incurred by the reconfigurability is not tolerable for low-power schemes.

As shown in Fig. 1, the main components constructing the proposed reconfigurable memory-based FFT (RMBFFT) are memory bank(s), a configuration mapping table (CMT), and a multi-precision reconfigurable processing unit (MPRP). In different situations, MPRP can be reconfigured for smaller area to consume less energy while providing the required precision. In high throughput systems, the proposed RMBFFT employs more MPRP instances to increase processing speed. In Fig. 1, the memory banks are used to store RMBFFT inputs and outputs in every processing stage, which will be explained in more details in Sect. 5. In the proposed scheme, the best energyefficient configuration (corresponding to the word-lengths) is obtained from CMT which stores the run-time specifications. These specifications such as the FFT size (N), the modulation scheme, sensed SNR, and required BER are applied while the system is working. The sensed SNR value is supposed to be measured using an SNR estimator block.

Using RMBFFT architecture makes the design of the FFT with any size of power of two (N = 2 n ) possible. In the proposed RMBFFT architecture, intrinsically the memory width (word-length) is fixed in all stages. Consequently, the number of output bits of the processing unit has to be the same as the number of input bits. This reduces the hardware cost as well as the energy consumed by the control unit.

As shown in Fig. 1, CMT maps the run-time specifications of the FFT to a word-length for RMBFFT. The entries of CMT are computed based on the required SQNR in order to guarantee the demanded BER. This means that increasing SNR and decreasing the word-length may lead to a configuration that makes RMBFFT less accurate but more energy-efficient. The entries of CMT are calculated analytically and verified by simulation, as described in Sect. 4 and Sect. 5.

In the proposed RMBFFT architecture, MPRP consists of the butterfly unit and the corresponding twiddle factor multipliers. To make MPRP energy-efficient through reconfigurablity, modular multipliers and adders can be constructed using basic/small multipliers and adders. This provides the required flexibility to support all the operations on operands with different word-lengths. Like that in any arithmetic unit, in the butterfly unit the computation radix determines how many input bits are used to calculate the same number of output bits. Increasing the radix (usually a power of two) can potentially increase the processing speed and decrease the number of memory accesses in the expense of larger and more complex butterfly unit.

Radix-4 Butterfly

The common radices in the conventional FFT designs are 2, 4, and 8. When FFT size is not a power of 4 or 8, the mixed-radix-4/2 or 8/2 can be used to calculate all the required FFT size. For example with the FFT size of 32 in the mixed-radix-4/2, the FFT consists of two radix-4 stages followed by the last mixed-radix-4/2 reconfigures into radix-2 butterflies.

According to the previous research, to find the best computation radix that guarantees a low-power RMBFFT, the hardware complexities for different radices need to be examined using the entries of Table 3 where the numbers of non-trivial multiplications and additions are listed for different radices and various FFT sizes.

As indicated in the table, increasing the radix results in reduction of the overall number of multiplications and additions; hence the hardware complexity decreases that may increase energy efficiency. In previous studies, the trivial multiplications such as constant multiplications by √ 2 2 in the radix-8 butterfly are omitted when evaluating the hardware complexity. However, in reality, the complexity of such multipliers is about half the complexity of a non-trivial multiplier. This becomes even more important when N increases and the constant multipliers significantly affect the overall hardware complexity of the FFT architecture. Hence, the role of the trivial multiplications in the radices 8 and 16 is taken into account in the current research, unlike that in other studies. The comparison of the number of required multiplications for various radices of FFT, considering the trivial multiplications is illustrated in Fig. 2. As it is obvious in the figure, calculations in the radix-8 and above require more trivial multipliers to be used in the FFT design. Hence, using the radix-4 which results in the lowest hardware complexity for multiplication implementation can be the best choice for the proposed FFT architecture. Therefore, in Fig. 1, MPRP unit can be designed in the mixed-radix-4/2 that can be reconfigured into either the radix-4 or the radix-2 by the control unit based on N. In this section, SQNR of RMBFFT is formulated and then different values for BER are expressed analytically for different modulation schemes based on SNR and SQNR. Also, the tradeoff between SQNR and SNR is investigated. With dynamic adaptation of RMBFFT based on the sensed SNR, energy efficiency can be improved by reducing the word-length of RMBFFT, while the expected application-specific BER is guaranteed.

Quantization Loss and SQNR in RMBFFT

Based on the implementation constraints for the decimation in frequency (DIF) radix-4 RMBFFT introduced in Sect. 3, a noise model is developed for MPRP unit as shown in Fig. 3. In this figure, the word-lengths of both the memories and the arithmetic units are assumed to be the same. In the radix-4 butterfly unit, every real or imaginary output is calculated by summation of all four inputs. Hence, to prevent the possible overflow after this addition, the FFT inputs and the multiplication outputs in every stage are scaled down by shifting two bits to the right. This eliminates the noise caused by rounding in butterfly unit (rounding noise). Fig. 3 represents only the real part of the operations since the calculation for the imaginary part is the same.

In Fig. 3, x and y, respectively, represent the input and the output of one stage of the reconfigurable radix-4 FFT (MPRP), both with a-bit wordlengths. Also, e qi and e qt represent the additive quantization noise for the inputs of every stage and for the twiddle factors, respectively. In this scheme, the twiddle factors are stored in a ROM with b-bit word-length. For every output, the real phase of the complex multiplications consists of two real multiplications. Each of the real product terms is rounded to a bits and the additive rounding noise is represented by e m . All the additive noises are assumed to be the uniformly distributed random variables with zero mean (µ = 0) and non-correlated with one another; hence, their variances under round to nearest rounding scheme can be calculated as, σ 2 = q 2 12 = 2 -w 12 , where w is the word-length of the corresponding variable [START_REF] Proakis | Digital Signal Processing: Principles, Algorithms, and Applications[END_REF]. Every quantized input (x) with word-length a, can be represented as x = x + e qi , where x is any ideal (unquantized) input and e qi is the corresponding additive quantization noise [START_REF] Chang | On the fixed-point accuracy analysis of FFT algorithms[END_REF]. In Fig. 3, without any noise (ideal situation), the output (y) can be expressed as, y = 8x.t, where t is the twiddle factor. The rounded output (ŷ) can be expressed using the quantized inputs and the additive rounding noise after each multiplication as:

ŷ = Q[y] = 4x t + e m + 4x t + e m (2)
Consequently, the overall output quantization noise of one stage of the DIF FFT can be calculated as

n DIF = ŷ -y = 8(xe qt + te qi + e qi e qt ) + 2e m (3)
which leads to the quantization noise variance of

σ 2 nDIF = E |n DIF | 2 = 64 12 2 -2b x 2 + 2 -2a t 2 + 2 -2a-2b + 4 12 2 -2a (4)
From Eq. 4 and assuming x and t to be non-correlated variables normalized in the range [-1, 1) with uniform distribution, it can be concluded that σ 2 x = σ 2 t = 1 3 . Accordingly, Eq. 4 can be rewritten as

σ 2 nDIF = 64 12 1 3 2 -2b + 2 -2a + 2 -2a-2b + 1 3 2 -2a (5)
The scaling factor of 1/4, caused by the 2-bit scaling noted in Sect. 4.1, reduces the variance of the quantization error by a factor of ( 1 16 ) n-i in the i-th stage (i = 1, 2, ..., n) where n = log 4 N is the number of FFT stages [START_REF] Proakis | Digital Signal Processing: Principles, Algorithms, and Applications[END_REF]. Consequently, the total variance of the output quantization noise of RMBFFT is

σ 2 q = σ 2 nDIF ( N 4 )( 1 16
)

n-1 + ( N 4 2 )( 1 16
) n-2 + ...

+ N 4 n = σ 2 nDIF ( 1 4 ) n-1 + ( 1 4 ) n-2 + ... + 1 = 4 3 σ 2 nDIF 1 -( 1 4 ) n (6)
For sufficiently large N, Eq. 6 can be approximated as σ 2 q = 4 3 σ 2 n DIF . With regard to the variance of RMBFFT output signal as σ 2 y = 1 3N [START_REF] Proakis | Digital Signal Processing: Principles, Algorithms, and Applications[END_REF], due to the scaling in every stage, SQNR of RMBFFT can be expressed as

SQNR = σ 2 y σ 2 q = 3 12N σ 2 nDIF (7)
The above analysis is developed for the radix-4 DIF FFT. The quantization noise analysis for the decimation in time (DIT) FFT method is similar to what is given in Fig. 3, since DIT and DIF are similar except for the multipliers in DIT that are moved to the input of the butterfly unit. Hence, the overall noise for the radix-4 DIT FFT can be expressed as

σ 2 nDIT = 64 12 1 3 2 -2b + 2 -2a + 2 -2a-2b + 64 12 1 3 2 -2a (8)
Based on the implementation constraints of the radix-4 RMBFFT, comparing Eqs. 5 and 8 indicates that the quantization noise variance of the DIF scheme is smaller than that of the DIT design. Fig. 4 shows how choosing different values for N, a and b can affect SQNR. The figure reveals that increasing N and/or decreasing a can increase SQNR. As Fig. 4 indicates, situations in where inputs word-lengths (a), are larger than the twiddle factor word-length (b), do not considerably increase SQNR. The same results could be obtained once a and b are interchanged in the above analysis. This means that for twiddle factors word-length larger than inputs word-lengths, SQNR does not increase substantially.

BER Analysis in AWGN Channel

The aim of this section is to determine the minimum required accuracy (wordlength) of RMBFFT for different SNR values, modulation schemes, FFT size and application-specific BERs. The maximum reduction in SQNR to trade off accuracy for energy efficiency is calculated analytically, using the statistical analysis of RMBFFT. In this approach, at run-time, a special module is used to measure SNR and then to send this value to the FFT control unit. This unit then selects the word-lengths from CMT based on the SNR range that the sensed SNR falls into. In this section c(k) is the additive white Gaussian noise (AWGN) channel with the noise variance of σ 2 c = P signal SNR . Its probability density function (pdf), f c (x) can be expressed as

f c (x) = 1 σ c √ 2π exp -x 2 2σ 2 c . (9)
The overall quantization noise to signal ratio, σ 2 Q = 1 SQNR with SQNR calculated in Sect. 4.1, includes additive noises, e qi , e qt , and e m , which are assumed to be independent and identically distributed (iid). Hence, the overall sum can be considered as a Gaussian variable with the pdf function in the form of

f q (x) = 1 σ Q √ 2π exp -x 2 2σ 2 Q . ( 10
)
The pdf function can be represented as the convolution of the variables pdf functions. Hence, convolving Eqs. 9 and 10 results in

f N (x) = 1 σ 2 Q + σ 2 c √ 2π exp -x 2 2(σ 2 Q + σ 2 c ) . ( 11
)
The probability distribution F N (x) can be extracted from Eq. 11 as

F N (x) = 1 2     1 + erf     x 2 σ 2 Q + σ 2 c         (12)
where erf(x) = 2 √ π x 0 exp -t 2 dt. Each OFDM symbol contains overheads in both time domain (cyclic prefix) and frequency domain (guard bands) which take various values in different application layer standards. Although these overheads affect SQNR, they are ignored and only the effects of FFT module and modulation schemes are considered when calculating BER. In BPSK and QPSK modulations, BER can be calculated through

BER(σ Q , σ c ) = 1 -F N (1) = 1 2 erfc     1 2 σ 2 Q + σ 2 c     (13)
where

erfc(x) = 1 -erf(x) = 2 √ π ∞
x exp -t 2 dt. BER for 16-QAM modulation can be calculated using [START_REF] Fitz | On the bit error probability of QAM modulation[END_REF]:

BER(σ Q , σ c ) = 3 8 erfc     1 10 σ 2 Q + σ 2 c     + 1 4 erfc     3 10 σ 2 Q + σ 2 c     - 1 8 erfc     √ 5 2 σ 2 Q + σ 2 c     (14)
Based on BER obtained analytically through Eqs. 13 and 14, the required input word-lengths are calculated for different SNR to guarantee the applicationspecific BER constraint. The input word-lengths calculated for QPSK and 16-QAM modulations in AWGN channel are shown in Figs. 5 and6, respectively. For the sake of clarity, the word-lengths are shown for the proposed 64-, 256-, 1024-, and 4096-point RMBFFT. As expected, by increasing SNR and/or decreasing N, even smaller word-lengths can satisfy the required BER. Decreasing the word-length in RMBFFT leads to a smaller arithmetic circuit with less energy consumption and with the accuracy which still remains in the acceptable range.

BER Analysis in Rayleigh Fading Channel

This section presents BER expression to find the minimum required wordlength of RMBFFT in a Rayleigh fading channel. The OFDM technique can transform a frequency-selective wide-band channel into many non-selective (flat) narrowband subchannels. To compute BER, the method in chapter 13 of [START_REF] Proakis | Digital Communications[END_REF] is exploited in Eqs. 15 and 16 to average the non-fading AWGN BER expression with the chi-squared distribution obtained in the frequency nonselective Rayleigh fading channel:

P b = ∞ 0 P b,AWGN (γ)P df (γ)dγ ( 15
)
p df (γ) = 1 γ exp - γ γ γ ≥ 0 ( 16
)
where P b,AW GN (γ) represents the probability of error (BER) of a specific modulation scheme in an AWGN channel at a particular SNR;

γ = h 2 E b N0 . Here, E b
N0 is the ratio of bit energy to the noise power density in a non-fading AWGN channel, and the random variable h 2 is the instantaneous power of the fading channel. In Eq. 16, P df (γ) is the pdf function of γ caused by the Rayleigh fading channel, and γ =

E b N0 E[h 2 ] is the average SNR. If E[h 2 ] = 1, γ provides the average E b
N0 in the fading channel [START_REF] Simon | Digital Communication Over Fading Channels[END_REF]. Using Eqs. 15 and 16 and also Eq. 17 [START_REF] Fitz | On the bit error probability of QAM modulation[END_REF],

∞ 0 a.exp (-at) erfc √ bt dt = 1 - b a + b (17)
the average BER for M-QAM in a frequency non-selective Rayleigh fading channel can be expressed by [START_REF] Simon | Digital Communication Over Fading Channels[END_REF] BER

M-QAM,Ray ≈ 2 log 2 M 1-1 √ M √ M 2 i=1 1- 1.5(2i-1) 2 γ log 2 M M-1+1.5(2i-1) 2 γ log 2 M (18)
Using both Eq. 18 and the AWGN BER of our RMBFFT (Eq. 14), the BER of 16-QAM modulation in a Rayleigh fading channel can be expressed as:

BER 16-QAM,Ray ≈ 1 2 -3 8 1 √ 1+10(σ 2 Q +σ 2 c ) -1 4 3 √ 9+10(σ 2 Q +σ 2 c ) + 1 8 √ 10 √ 10+4(σ 2 Q +σ 2 c ) (19)
where σ 2 Q and σ 2 c are defined in Sect.4.2. Figs. 6(c) and 6(d) show the minimum required word-lengths calculated for 16-QAM modulation in the Rayleigh fading channel for BER=0.01 and BER=0.001, respectively. Similar to the AWGN, by increasing SNR and/or decreasing N , the minimum RMBFFT word-length can be reduced to satisfy the required BER in the Rayleigh model. Comparing Figs. 6(c) and 6(d) with Figs. 6(a) and 6(b) shows that the minimum FFT word-length requires more bits on the Rayleigh fading channel than on the AWGN channel when all the other parameters are the same.

Performance Evaluation

In this section, the analysis expressed in Sect. 4 is verified and compared with simulation results and the minimum required word-lengths are obtained for different specifications. Also, the reconfiguration overhead and the energy saving of RMBFFT are estimated. In accordance with RMBFFT, a memory organization is proposed to improve energy-efficiency.

Simulation Results

As shown in Fig. 7, the simplified OFDM transceiver is modeled in Simulink to validate the analysis performed in Sect. 4. In this figure, the generated random data are modulated in either QPSK or 16-QAM, the cyclic prefixes (CP), and subcarriers structure are based on LTE standard, and the channel model is AWGN or Rayleigh fading. At the receiver side, the proposed RMBFFT is implemented in MATLAB for 8-to 20-bit word-lengths. The channel is swept from 5 to 40 dB and BER of the corresponding system is measured using the Error Rate module. For different SNR and FFT sizes, based on the demanded application-specific BER, the required word-length of RMBFFT is obtained through simulation and compared with the analytical results.

For the sake of clarity, these comparisons are shown only for 256-and 1024-point RMBFFT in Fig. 8 for both AWGN and Rayleigh fading channels. Because of the assumptions used in Sect. 4 in order to simplify the analysis, the analytical and simulation results are not completely the same. Nevertheless, the difference is not significant and the simulation results follow the same general trend. As indicated in Fig. 8, the required word-length rises when N (FFT size) increases and SNR decreases in both schemes.

From the simulations and analytical results, it can be concluded that for LTE, the required word-length for different specifications (N, BER, modulation schemes and SNR) can vary from 8 up to 19 bits. However, implementing a practical reconfigurable RMBFFT hardware with one bit step is not efficient. Instead, optimized 4-bit addition and multiplication blocks can be used to efficiently construct 8-, 12-, 16-, 20-bit RMBFFT iteratively using modular (recursive) technique in digital arithmetic [START_REF] Parhami | Computer Arithmetic: Algorithms and Hardware Designs[END_REF].

At run-time, entries of CMT (shown in Fig. 1) that represent word-lengths of RMBFFT are selected by the system specifications which are SNR, BER, N, and modulation scheme. The entries labeled as "wl" (word-length) are listed in Table 4. The value of N in Table 4 is limited to 2048 points while in the other standards it may increase to 8192 or even more. For larger N and more complicated modulation schemes (like 64-QAM), larger RMBFFT word-lengths may be required.

Overhead Analysis

As mentioned in Sect. 4, at run-time a simple SNR estimator module that measures current SNR is required. Usually this module is already embedded and available in most wireless communication systems for different objectives such as: selecting modulation/coding parameters and channel state feedback [START_REF] Wilhelmsson | Analysis of a novel low complex SNR estimation technique for OFDM systems[END_REF]. Therefore, in the current analysis the overhead of SNR estimator block is not taken into account.

In the proposed reconfigurable design, CMT decision table provides the suggested word-length for MPRP unit of RMBFFT. To investigate the energy overhead of CMT in the proposed architecture, CMT and basic operators in MPRP are modeled in VHDL using FloPoCo [START_REF] De Dinechin | Designing custom arithmetic datapaths with FloPoCo[END_REF] and synthesized on a Virtex-6 xc6vcx75t Xilinx FPGA. The power dissipation of CMT circuit (P c ), 4-bit adder (P a ), and 4-bit multiplier (P m ) in the modular MPRP unit are estimated using Xilinx Xpower Analyzer (XPA) [52]. Taking the fact into consideration that transition rate of input data and data access rate of CMT are considerably less than that of MPRP, the results are P c =110 µW , P a =20 µW , and P m =90 µW . The energy saving of the proposed RMBFFT for different wordlengths are estimated in the next section, using the obtained power dissipation.

Energy Saving Estimation

In modular (divide and conquer) design, addition (multiplication) of 8-, 12-, 16-, and 20-bit operands can be constructed by using 2 (4), 3 (9), 4 [START_REF] Ferreira | Reconfigurable NC-OFDM processor for 5G communications[END_REF], and 5 (25) iterations of 4-bit adder (multiplier) block, respectively. Referring to Fig. 3, each output of MPRP combinational logic consists of three additions in butterfly, and two multiplications and one addition in multiplier unit. In modular multiplication, once the multiplier and multiplicand are sliced into x 4-bit blocks, x 2 4-bit multipliers followed by x 2 8-bit adders are required to sum up the partial products. Similarly, a 4x-bit addition can be implemented by x instances of 4-bit adders.

Since the word-lengths of additions and multiplications are the same (a), the estimated energy consumption of butterfly and multiplier unit are E b = 3 a 4 P a t a and E m = 2 a 4 2 P m t m + 2 a 4 2 + a 4 P a t a , respectively. The power dissipations P a and P m are explained in Sect. 5.2 and t m and t a are the critical path delays of 4-bit multiplier and 4-bit adder, respectively.

Since CMT is accessed once every execution of RMBFFT, energy consumption of CMT can be estimated as E c = P c t c , where t c is CMT critical path delay. So, based on the dynamic word-length extracted from CMT (a), the overall energy consumption of RMBFFT can be estimated as

E R = E m + E b + E c = a 2 8 P m t m + a + a 2 8 P a t a + P c t c (20)
As shown in Fig. 9, to improve energy-efficiency of RMBFFT memory unit, the proposed interleaved memory is arranged as a 54 matrix of the memory banks. The memory organization consists of (N/4)4-bit modules to provide the ability to read/write nibbles of four inputs/outputs (A, B, C, and D in Since memory accesses are responsible for major part of energy consumed in FFT [START_REF] Sampson | En-erJ: approximate data types for safe and general low-power computation[END_REF], reducing the number of memory accesses can improve the overall energy-efficiency considerably. In addition, when the required dynamic wordlength decreases, energy efficiency of memory can be improved by forcing unused memory modules into idle state. For example, for 12-bit word-length, only the upper three rows of the banks are used and are accessed during three consecutive iterations. Hence, energy consumption can be reduced about 40%, comparing to 20-bit word-length case. Also, the banks in the two least significant rows can be powered down, which results in further 40% improvement in energy efficiency.

After being normalized to the conventional 20-bit FFT implementation, energy consumptions of different configurations of RMBFFT are compared and listed in Table 5. The maximum energy saving of MPRP is about 81% for the 8-bit word-length, while energy consumption rises to 103% for 20-bit due to the reconfiguration overhead penalty. The proposed memory organization having been used, up to 60% more energy efficiency is achievable due to reducing the number of memory accesses. Also, by disabling unused memory modules for smaller word-lengths, the energy consumption of modules can be reduced by 40% for the 8-bit RMBFFT.

Performance Comparison with Previous Works

Table 6, which displays the performance of both the RMBFFT architecture and previous efforts, reveals that the proposed scheme provides higher performance in terms of power dissipation, energy consumption, throughput, reconfiguration time, and number of FPGA slices. In the proposed method, wl and P represent word-length and the number of processing units (MPRP) of RMBFFT architecture; both can be chosen in accordance with the required throughput. For example, using four processing units (P=4), the achieved sampling rate is large enough to handle the maximum required throughput of LTE (30.72 MS/s) [START_REF] Sarada | Reconfigurable FFT processor -A broader perspective survey[END_REF] when the word-length equals 16 (wl=16). ASIC implementation of this architecture using CMOS technology can increase processing speed and consequently decrease the number of processing units (P) required. The energy consumption per symbol for the proposed RMBFFT with size 512 (N=512) is estimated to be 7, 15, 26, and 40 pJ when the word-length (wl) equals 8, 12, 16, and 20 bits respectively.

Reducing FFT word-length decreases energy consumption but causes a loss of accuracy or SQNR. Therefore, OFDM systems need FFT modules to be implemented with shorter word-lengths while meeting the required SQNR [START_REF] Chen | An indexed-scaling pipelined FFT processor for OFDM-Based WPAN applications[END_REF]. The SQNR performance of the proposed RMBFFT with N=512 is calculated and compared to those of the conventional FFT processors and shown in Table 7. The proposed scheme can be optimized based on the requirements at run-time, while the hardware can be reconfigured with a proper word-length and reasonable SQNR to guarantee the minimum required BER. For exam- ple, when the communication system works with a small FFT size (N=64) and BPSK modulation in a channel with high SNR, 8-bit word-length is quite enough to provide the required SQNR and BER. On the other hand, when higher SQNR is needed, longer word-lengths can be dynamically chosen in RMBFFT.

Conclusion

This paper proposes RMBFFT, a multi-precision reconfigurable FFT architecture, as a dynamic trade-off between accuracy and energy efficiency in OFDM systems. RMBFFT is a memory-based DIF radix-4 FFT that can be reconfigured according to the minimum required word-length based on the system specifications, including BER, SNR, the modulation scheme, and FFT size at run-time. Quantization noise analysis is exploited for RMBFFT and the required word-lengths are calculated statistically. To validate the analysis, the proposed RMBFFT was simulated and applied to an OFDM transceiver in AWGN and Rayleigh fading channels. The results of the simulation followed a similar trend as seen in the analytic calculations. Synthesizing the basic operators of RMBFFT on an FPGA showed more than an 80% energy saving with RMBFFT over the traditional implementation. In addition, introducing a reconfigurable memory organization, can reduce the energy consumption of RMBFFT memory by approximately 60%.

In the future, we plan to implement the proposed RMBFFT in an OFDM system and measure the energy savings precisely. RMBFFT can be applied in other applications such as image processing to increase processing speed and energy efficiency. This reconfigurable architecture can be used in other error-tolerable applications.

Fig. 3

 3 Fig. 3 Inserting quantization and rounding noise in DIF MPRP unit

Fig. 4

 4 Fig. 4 SQNR vs. the FFT size (N) and input word-length

Fig. 5

 5 Fig. 5 Required input word-length vs. SNR for different FFT sizes in QPSK (AWGN)

Fig. 6

 6 Fig. 6 Required input word-length vs. SNR for different FFT sizes in 16-QAM

Fig. 7

 7 Fig. 7 Simplified OFDM transceiver model in Simulink

Fig. 8

 8 Fig. 8 Analytical-based vs. simulation-based required word-length for 16-QAM

Fig. 9

 9 Fig. 9 Proposed energy-efficient memory organization of RMBFFT

Table 1

 1 System parameters for OFDM applications[START_REF] Sarada | Reconfigurable FFT processor -A broader perspective survey[END_REF]

	Standard	FFT size (N)	Sampling rate (MHz)	Bandwidth (MHz)
	WLAN (802.11 a, n)	64, 128	20	20
	WiMax (802.16e)	128,512,1024,2048	1.43, 5.72, 11.43, 22.86	1.25, 5, 10, 20
	3GPP-LTE	128, 256, 512, 1024, 1536, 2048 1.92, 3.86, 7.68, 15.36, 23.04, 30.72	1.25, 2.5, 5, 10, 15, 20
	DAB	256, 512, 1024, 2048	2	1.5
	DVB-T	2048, 8192	8	6, 7, 8

Table 2

 2 Comparison of well-known architectures in implementing the FFT

	Architecture	Area	Throughput Control complexity	Reconfigurability
	Memory-based	Very low	Moderate	High		High
	Fully-parallel	Very high	Very high	Low		NA (fixed)
	Pipeline	High	High	Moderate	Very low
	Data In			Data Out
		Memory Bank(s)	{Run-Time Specifications}
					Sensed SNR	Required BER	FFT size	Modulation scheme
		Multi-Precision
		Reconfigurable	word-lengths	Configuration Mapping
		Processing Unit(s)			Table (CMT)
		(MPRP)

Fig. 1 Proposed RMBFFT architecture

Table 3

 3 Number of non-trivial real multiplications and additions for N-point FFT[START_REF] Proakis | Digital Signal Processing: Principles, Algorithms, and Applications[END_REF] Total number of real multiplications (including trivial and non-trivial) vs. FFT size for different radices of FFT

		Number of real multiplications Number of real additions
	N	Radix-2 Radix-4	Radix-8	Radix-2 Radix-4 Radix-8
	16	24	20	NA	152	148	NA
	32	88	NA	NA	408	NA	NA
	64	264	208	204	1032	976	972
	128	712	NA	NA	2504	NA	NA
	256	1800	1392	NA	5896	5488	NA
	512	4360	NA	3204	13566	NA	12420
	1024 10248	7856	NA	30728	28336	NA
	2048 23560	NA	NA	68616	NA	NA

Table 4

 4 Content of CMT for LTE standard where "wl" represents word-length

						BER=0.01
				QPSK						16-QAM
	N	SNR	wl	SNR	wl	SNR	wl	SNR	wl	SNR	wl	SNR	wl
	64	<10	12	≥10	8			<8	16	≥8	12
	128	<8	16	≥ 8 <22	12	≥22	8	<17	16	≥17	12
	256	<8	16	≥8	12			≤10	20	>10 <18	16	≥18	12
	512	≤11	20	>11	16			≤12	20	>12	16
	1024	≤12	20	>12	16			≤15	20	>15	16
	1536	≤18	20	>18	16			≤19	20	>19	16
	2048	≤19	20	>19	16			≤20	20	>20	16
						BER=0.001
				QPSK						16-QAM
	N	SNR	wl	SNR	wl	SNR	wl	SNR	wl	SNR	wl	SNR	wl
	64	≤6	16	>6 <15	12	≥15	8	≤13	16	>13	12
	128	≤15	16	>15	12			>13 <20	16	≥20	12
	256	<17	16	≥17	12			≤14	20	>14 <20	16	≥20	12
	512	≤13	20	>13	16			≤18	20	>18	16
	1024	≤15	20	>15	16			≤20	20	>20	16
	1536	≤22	20	>22	16			≤23	20	>23	16
	2048	≤24	20	>24	16			≤25	20	>25	16

Table 5

 5 Normalized energy consumptions for different RMBFFT configurations

			(Worst Case)		RMBFFT
	Energy Consumption of [%]		Static 20-b	20-b	16-b 12-b	8-b
	MPRP			100%	103%	67%	39%	20%
	memory accesses			NA	100%	80%	60%	40%
	memory modules (by disabling modules)	NA	100%	80%	60%	40%
	Table 6 Performance comparison
	Design	[12]	[30]	[17]		[24]	Proposed
	FPGA device	Virtex-5	Virtex-5	Zynq-7000		Virtex-5	Virtex-6
	FFT size	512	64, 128, 256, 512	64-2048		512	(2 n )
	Architecture	NR	Pipeline MDC	Pipeline SDF		Pipeline	Memory-based
	Radix	NR	Mixed-radix 4/2	Mixed-radix 2 2 /2/3	Radix 2 5	Mixed-radix 4/2
	Word length	4-15	16	16		20	{8,12,16,20}
	Reconfigurability	No	Yes	Yes		Yes	Yes
	Reconfiguration time (µs)	NR	689	496		NR	0.01
	Multi-precision	Yes	No	No		No	Yes
	Core power (mW)	NR	NR	26-82		126	2P
	Energy consumption per symbol (pJ)	40-110	NR	NR		NR	{7,15,26,40}
	Maximum clock rate (MHz)	NR	111	NR		340	147
	Throughput (MSample/s)	NR	400	98		8R	P.R.( 4 wl ) 2
	Latency -critical path (ns)	NR	8.959	NR		2.941	6.8
	Number of slice registers	NR		6400	21427 (31%)	44P (1%)
	Number of slice LUTs	NR	20670 (Overall)	3200	16589 (24%)	46P (1%)
	Number of flip flops	NR		20 DSP core	26957 (39%)	46P (1%)
	NR: Not Reported
	R: clock rate
	P : Number of MPRP units

Table 7

 7 SQNR performance comparison with previous works

	FFT Design	[22]	[25]	[53]	[11]	[23]	Proposed RMBFFT
	Architecture	SDF	pipeline	SDF	MDF memory-based		memory-based
	FFT size	8192	8192	1024	512	512	512	512 512 512
	Word-length (bits)	16	16	16	14	12	8	12	16	20
	SQNR (dB)	34.9	53	51	41	57	16	41	61	69