Emmanuelle Anceaume
email: emmanuelle.anceaume@irisa.fr

Yann Busnel
email: yann.busnel@univ-nantes.fr

Sébastien Gambs
email: sebastien.gambs@irisa.fr

Characterizing the Adversarial Power in Uniform and Ergodic Node Sampling

Keywords: F, 2, 2 [Theory of Computation]: Analysis of Algorithms and Problem Complexity-Non-numerical Algorithms and Problems Theory, Algorithms

In this paper, we consider the problem of achieving uniform and ergodic peer sampling in large scale dynamic systems under adversarial behaviors. The main challenge is to guarantee that any honest node is able to construct a uniform and non-fixed (ergodic) sample of the node identifiers in the system, and this, despite the presence of malicious nodes controlled by an adversary. This sample is built out of a stream of events received at each node. We consider and study two types of adversary: an omniscient adversary that has the capacity to eavesdrop all the messages that are exchanged within the system, and a blind adversary that can only observe messages that have been sent or received by the manipulated nodes. The former model allows us to derive lower bounds on the impact that the adversary has on the sampling functionality while the latter one corresponds to a realistic model. Given any sampling strategy, we quantify the minimum effort exerted by both types of adversary on any input stream to prevent this strategy from outputting a uniform and ergodic sample.

INTRODUCTION

We investigate the problem of achieving uniform and ergodic peer sampling in large scale open systems in presence of adversarial nodes. Uniform sampling is a fundamental primitive ensuring that any individual in a population has the same probability to be selected as sample. Uniform sampling finds its root in many practical problems such as data collection, data dissemination, event driven communication, load balancing and data-caching [START_REF] Bertier | On Gossip and Populations[END_REF][START_REF] Jelasity | Gossip-based Peer Sampling[END_REF][START_REF] Karger | Simple Efficient Load Balancing Algorithms for Peer-to-Peer[END_REF][START_REF] Lv | Search and Replication in Unstructured Peer-to-Peer Networks[END_REF]. In particular, publish-subscribe systems require that each subscriber of any given topic has the same probability to be chosen as access point for that topic, even in case some topics are more popular than others [START_REF] Baldoni | TERA: Topic-based Event Routing for Peer-to-peer Architectures[END_REF]. Having access to a peer sampling service provides such systems with uniform samples of nodes. In the context of event-driven interaction systems, population protocols rely on uniform node sampling as a basis for the construction of fair schedulers [START_REF] Bertier | On Gossip and Populations[END_REF]. Achieving uniform sampling in large scale open and dynamic systems has been shown to be difficult. One of the reasons is that the population of these systems is very large (e.g., thousands or millions of nodes) and exhibits a very high churn (recent studies on the eDonkey file-sharing network have shown that in average 500, 000 peers connect and disconnect per day [START_REF] Blond | Finding Good Partners in Availability-Aware P2P Networks[END_REF]). Moreover, openness makes unavoidable the presence of malicious nodes that try to subvert the system functionalities. Most common attacks mainly consist in isolating targeted honest nodes from the remaining of the system so that sought resources and/or services become unreachable (denial of services attacks), and thus to the eventual partitioning of the system.

By relying on the topological properties of structured large scale dynamic systems, it has been shown that it is possible to guarantee that with high probability the identifier of any node is equally likely to appear in the local view of each other honest node in a number of communication rounds polynomial in the size of the system. One way to achieve this is by imposing nodes to frequently depart from their position and move to another random position in the system [START_REF] Anceaume | Dependability Evaluation of Cluster-based Distributed Systems[END_REF][START_REF] Awerbuch | Towards a Scalable and Robust Overlay Network[END_REF]. In unstructured large scale systems, nodes cannot rely on the topological nature of structured graphs to detect undesirable behaviors. To circumvent this issue, Bortnikov et al. [START_REF] Bortnikov | Brahms: Byzantine Resilient Random Membership Sampling[END_REF] rely on the properties of min-wise independent permutations. Such permutations are fed by the streams of gossiped nodes identifiers and eventually converge towards a uniform sampling on the node identifiers. However, this sample is definitive in the sense that no other node identifier received in the future in the input stream will ever have the chance to appear in the random sample. This makes this sampling strategy uniform but not ergodic, that is, it does not guarantee that the identifier of any node in the system has a non-zero probability to appear infinitely often in a sample. This clearly makes such an approach unfitted for dynamic systems.

A preliminary step in determining conditions under which uniform and ergodic sampling is achievable in unstructured peer-to-peer systems potentially populated with a large proportion of malicious nodes has been presented in a previous paper [START_REF] Anceaume | Uniform and Ergodic Sampling in Unstructured Peer-to-Peer Systems with Malicious Nodes[END_REF]. Briefly, we show in [START_REF] Anceaume | Uniform and Ergodic Sampling in Unstructured Peer-to-Peer Systems with Malicious Nodes[END_REF] that imposing strict restrictions on the number of messages sent by malicious nodes during a given period of time and providing each honest node with a very large memory (proportional to the size of the system) is a necessary and sufficient condition to obtain uniform and ergodic sampling.

In the present paper, we propose a characterization of the adversarial power towards biasing uniform and ergodic sampling. By adopting a statistical view of the input stream and by comparing distributions using metrics such as information divergence, we derive lower bounds on the work that the adversary has to exert to bias this input stream so that uniform and ergodic sampling does not hold. We consider and study two models of adversary: the omniscient adversary, which has the capacity to eavesdrop on all the messages that are exchanged within the system, and the blind adversary, which can only observe messages that have been sent or received by malicious nodes. To the best of our knowledge, we are not aware of any previous work that has characterized the minimum effort an adversary has to exert to prevent the uniform and ergodic sampling to be achievable.

The outline of this paper is as follows. In Section 2, we give an overview of the existing related work. Section 3 describes the model of the system and the assumptions that are made. In Section 4, we describe the functionalities of a sampling component and the properties that it should guarantee while in Section 5, we present some background on information divergence of data streams. The omniscient and blind adversary models, as well as the characterization of the minimum effort the adversary has to exert to bias the sampling properties, are respectively studied in Sections 6 and 7. Finally, Section 8 concludes with some open issues.

RELATED WORK

Different approaches have been proposed to deal with malicious behaviors in the peer sampling problem in unstructured large scale dynamic systems. Jesi et al. [START_REF] Jesi | Secure Peer Sampling[END_REF] propose a random sampling algorithm taking explicitly into account malicious nodes. Their solution assumes that the ultimate goal of the malicious nodes is to mutate the random graph into a hub-based graph, hub for which malicious nodes gain the lead. This approach, also adopted in several structured based systems [START_REF] Singh | Eclipse Attacks on Overlay Networks: Threats and Defenses[END_REF] through auditing mechanisms, or in sensor networks [START_REF] Liu | Detecting Malicious Beacon Nodes for Secure Location Discovery in Wireless Sensor Networks[END_REF], is effective only if the number of malicious nodes is very small with respect to the size of the system (i.e., typically of O(log n)). Bortnikov et al. [START_REF] Bortnikov | Brahms: Byzantine Resilient Random Membership Sampling[END_REF] have recently proposed a uniform but non-ergodic peer sampling algorithm that tolerates up to a linear number of malicious nodes. Their sampling mechanism exploits the properties offered by min-wise permutations. Specifically, the sampling component is fed with the stream of node identifiers periodically gossiped by nodes, and outputs the node identifier whose image value under the randomly chosen permutation is the smallest value ever encountered. Thus eventually, by the property of min-wise permutation, the sampler converges towards a random but permanent sample. In a previous work [START_REF] Anceaume | Uniform and Ergodic Sampling in Unstructured Peer-to-Peer Systems with Malicious Nodes[END_REF], the authors show that imposing strict restrictions on the number of messages sent by malicious nodes during a given period of time and providing each honest node with a very large memory (proportional to the size of the system) are necessary and sufficient conditions to obtain uniform and ergodic (non permanent) sampling. It is worth noting that our results complement two previous results [START_REF] Busnel | On the Uniformity of Peer Sampling based on View Shuffling[END_REF][START_REF] Gurevich | Correctness of Gossip-Based Membership under Message Loss[END_REF], in which an analysis of the class of uniform and ergodic sampling protocols is presented. Both previous work provide a complete analytical proof of a gossip-based protocol that reaches both uniformity and ergodicity, but in contrast to the present work, adversarial behaviors were not considered. Finally, taking a completely different approach from the previously mentioned papers, which are based on gossip algorithms or on distance function properties, the techniques presented in [START_REF] Yu | SybilLimit: A Near-Optimal Social Network Defense against Sybil Attacks[END_REF][START_REF] Yu | SybilGuard: Defending against Sybil Attacks via Social Networks[END_REF] rely on social network topologies to guard against Sybil attacks. Both protocols take advantage of the fact that Sybil attacks try to alter the fast mixing property of social networks to defend against these attacks.

SYSTEM MODEL

Model of the Network. We consider a dynamic system populated by a large collection of nodes in which each node is assigned a unique and permanent random identifier from an m-bit identifier space. Node identifiers (simply denoted ids in the following) are derived by applying some standard strong cryptographic hash function on nodes intrinsic characteristics. The value of m (160 for the standard SHA-1 hash function) is chosen to be large enough to make the probability of identifiers collision negligible. The system is subject to churn, which is classically defined as the rate of turnover of nodes in the system [START_REF] Godfrey | Minimizing churn in distributed systems[END_REF]. Each node knows only a small set of nodes existing within the system and this knowledge generally varies according to the activity of the system. The particular algorithm used by nodes to update this small set and to route messages induces the resulting overlay topology. In this work, we consider only unstructured overlays. Unstructured overlays are assumed to conform with random graphs, in the sense that relationships among nodes are mostly set according to a random process.

Adversary. We assume the presence of malicious nodes that try to manipulate the system by exhibiting undesirable behaviors (a node that is not malicious is called honest). In our context, this amounts to dropping messages that should normally be relayed by malicious nodes towards honest ones, and injecting new messages. Injecting new messages does not mean that malicious nodes have the ability to impersonate honest nodes. Rather, their goal is to judiciously increase the frequency of chosen ids to bias the sample list maintained by nodes. We model malicious behaviors through an adversary that fully controls these malicious nodes. The adversary model we considered follows the lines of [START_REF] Bortnikov | Brahms: Byzantine Resilient Random Membership Sampling[END_REF][START_REF] Jesi | Secure Peer Sampling[END_REF][START_REF] Malkhi | Probabilistic Byzantine Quorum Systems[END_REF], however we distinguish between two types of adversary: the omniscient adversary that is able to eavesdrop all messages exchanged within the system, and the blind adversary that can only observe messages sent or received by malicious nodes. In both models, we assume that the adversary can neither drop a message exchanged between two honest nodes nor tamper with its content without being detected. This is achieved by assuming the existence of a signature scheme (and the corresponding public-key infrastructure) ensuring the authenticity and integrity of messages. Sampling Assumptions. Similarly to Bortnikov et al. [START_REF] Bortnikov | Brahms: Byzantine Resilient Random Membership Sampling[END_REF], we assume that there exists a time T0 such that after that time, the churn of the system ceases. This assumption is necessary to make the notion of uniform sample meaningful. Thus from T0 onwards, the population of the system S is composed of n 2 m nodes, such that at least (1 -k)n of them are honest and no more than kn of them are malicious, and thus are controlled by the adversary. The subset of honest nodes in the overlay is denoted by N . Finally, we assume that all the nodes in S are weakly connected from time T0 onwards, which means that there exists a path between any pair of nodes in S in the underlying undirected graph whose vertices represent the nodes of S and edges are the communication links between these nodes.

SAMPLING COMPONENT

Following the approach taken in [START_REF] Anceaume | Uniform and Ergodic Sampling in Unstructured Peer-to-Peer Systems with Malicious Nodes[END_REF], each node u ∈ N has locally access to a sampling component1 as presented in Figure 1. The sampling component implements a strategy s and has uniquely access to a data structure Γu, referred to as the sampling memory. The size of the sampling memory Γu is bounded and is denoted by |Γu|. The sampling component S s u is fed with an infinite stream < vi, vj, . . . > of (possibly non unique) node ids that correspond to the node ids periodically received by node u ∈ N . This stream results either from the propagation of node ids through gossip-based algorithms (namely through push, or pull or push-pull mechanisms initiated by u and its neighbors), or from the node ids received during random walks initiated at u, or even from induced churn. The fingerprint of an input stream is a collection of weighted points in which each node id is weighted by the number of times this node id appears in the stream. Specifically, a stream of node ids can be summarized by < (v1, m1), . . . , (vn, mn) >, where vi denotes the identifier of a node in S and mi ∈ N represents the number of times vi appears in the stream. At each time t, the following three steps are atomically executed: the first element of the stream, say node id v, is given as input to the sampling component. The sampling component S s u reads v, and removes it from the stream. According to its strategy s, S s u may store or not v in Γu and outputs at most one node id.

For example, the strategy s may consist in storing v if Γu is not full, or in substituting v for a randomly chosen node id that belongs to Γu, or in simply dropping v. The output at time t, denoted S s u (t), is chosen among the node ids in Γu according to strategy s. For instance, strategy s may consist in choosing the smallest node id in Γu, or the smallest node id under a given min-wise permutation [START_REF] Bortnikov | Brahms: Byzantine Resilient Random Membership Sampling[END_REF]. The maximum finite hitting time needed for the sampling component S s u to reach a uniform sample is denoted by Ts. Clearly, Ts depends on the strategy s implemented by the sampling component and also on the stream of node ids the sampling component is fed with. We assume that the sampling strategy is known by the adversary in the sense that the algorithm used is public knowledge. However, if the algorithm is a randomized one, the adversary does not have access to the local random coins used by the honest nodes.

Finally, δ represents the number of node ids injected by the adversary in the input stream of node u during the time interval Ts. Note that it does not matter whether the injected node ids correspond to the node ids of malicious nodes or not as the unique goal of the adversary is to bias the input stream in such a way that whatever the strategy s of the sampler component, its output S s u (t) cannot guarantee both the uniform and ergodic properties [START_REF] Anceaume | Uniform and Ergodic Sampling in Unstructured Peer-to-Peer Systems with Malicious Nodes[END_REF]. More precisely, these properties are defined as follows Property 4.1 (Uniformity). Let N be a weakly connected graph from time T0 onwards, then for any time t ≥ Ts, for any node v ∈ S, and for any node u ∈ N ,

Pr[v ∈ S s u (t)] = 1 |S| .
Property 4.2 (Ergodicity). Let N be a weakly connected graph from time T0 onwards, then for any time t ≥ Ts, for any node v ∈ S, and for any node u ∈ N ,

Pr {t |t > t ∧ v ∈ S s u (t )} = ∅ = 0
, where ∅ represents the empty set.

Uniformity states that for any node in the system, its node id should have the same probability to appear in the sample of honest nodes in the system, while ergodicity says that any node id should have a non-zero probability to appear infinitely often in the sample of each honest node in the system. Note that uniformity by itself does not imply ergodicity, and vice versa. Indeed, the former does not impose any restriction on the freshness of output node ids, while the latter one does not provide any guarantee regarding the equiprobability of node ids to be chosen as samples. Moreover, as each node v in S has a non-zero probability to be returned by S s u (t) at time t, v must appear at least once in the input stream. Thus, ∀v ∈ S, starting from time Ts, mv > 0. Note that as previously said the model and analysis presented in this paper are independent from the way the stream of node ids at each node u is generated.

INFORMATION DIVERGENCE OF DATA STREAMS

A natural approach to detect changes on data streams is to model it as a distribution and to compute the distance between the observed stream and the ideal one. The metric we use in our context is the Kullback-Leibler (KL) divergence. It is sometimes called the relative entropy [START_REF] Cover | Elements of information theory[END_REF].

Definition 5.1 (Kullback-Leibler divergence).

Given two probability distributions on events p = {p1, . . . , pn} and q = {q1, . . . , qn}, the Kullback-Leibler divergence between pi relative to qi is defined as the expected value of the likelihood ratio with respect to qi. Specifically,

D(p||q) = n i=1 p i log 2 p i q i = H(p, q) -H(p), (1)
where H(p) = -pi log 2 pi is the (Shannon) entropy of p and H(p, q) = -pi log 2 qi is the cross entropy of p and q (by convention, 0 log 2 0 = 0).

The KL-divergence is a member of a larger class of distances known as the Ali-Silvey distances [START_REF] Ali | General Class of Coefficients of Divergence of One Distribution from Another[END_REF]. For the sake of clarity, we will use the notation log to denote the logarithm in base 2. Let p (U ) be the uniform distribution corresponding to a uniform stream, i.e., ∀i ∈ [1.

. n], p

(U ) i = 1
n , and q be the probability distribution corresponding to the input stream. In the rest of this paper and according to the classical use of the KL-divergence, we consider D(q||p (U ) ) as a measure of the divergence of the stream from the ideal one. Definition 5.2 (τ -closeness). A stream of node ids σ is τ -close if the KL-divergence between the probability distribution q corresponding to σ and the uniform probability distribution p (U ) is below or equal to a given value τ , where τ is a real. In the sequel, τ is called the robustness threshold.

Finally, given two distributions of probability, the Earth Mover's Distance (EMD) [START_REF] Monge | Mémoire sur la théorie des déblais et des remblais[END_REF] measures the minimal amount of work needed to transform one distribution to another by moving the probability mass between events. We rely on this metric to quantify the effort that an adversary exerts to bias the input stream. In our context, a unit of work corresponds to dropping one id and to pushing another id instead in the input stream.

OMNISCIENT ADVERSARY MODEL

In this section, we study the behavior of an omniscient adversary, which has the capacity to eavesdrop on all the messages sent and received by all the nodes in S. We demonstrate that the strategy that pushes all the probability mass over a single id is the one that maximizes the bias of the input stream so that it becomes far from the uniform distribution. We also describe an optimal strategy on how to achieve it.

In the following, the analysis of infinite input stream is restricted to any window of length Ts observed from time t ≥ T0. As previously said, Ts depends on the sampler strategy, and thus can be arbitrarily large. By abuse of language, the term "stream" will thus denote in the remaining of the paper the stream restricted to any such window of length Ts. The notation [1. . n] denotes the set {1, 2, . . . , n}.

Let σ be a stream such that the id of each node in S appears exactly once in the stream, except for a unique id that appears in all the remaining slots. Therefore, there exists a unique vi ∈ S such that mv i = Ts-(n-1) and ∀vj = vi ∈ S, mv j = 1. The following theorem states that the probability distribution associated to this particular stream is the one that has the maximal divergence from the uniform distribution. Theorem 6.1. (Maximal divergence from the uniform distribution) Let p (U ) be the uniform distribution corresponding to a uniform stream, that is, ∀i ∈ [1.

. n], p

(U ) i = 1
n , and q be the probability distribution corresponding to σ, i.e., it exists a unique vi ∈ S, q v i = Ts-(n-1) Ts and ∀vj ∈ S, vj = vi ⇒ q v j = 1

Ts . Then, for any possible probability distribution q, D(q||p (U ) ) ≤ D(q||p (U ) ).

Proof. Let q be the probability distribution representing any valid input stream on (T0, Ts]. We have ∀vi ∈ S, qv i = mv i Ts , where mv i is the number of times vi is present in the input stream. We have

D(q||p (U ) ) = H(q, p (U ) ) -H(q) = - n i=1 qi log p (U ) i -H(q) = log(n) -H(q).
Therefore, maximizing D(q||p (U ) ) amounts to minimizing H(q), which is equivalent to maximize n i=1 mv i log mv i Ts .

We characterize the stream that minimizes H(q) under the following constraints:

     1 ≤ mv i ≤ Ts with 1 ≤ i ≤ n, n i=1 mv i = Ts. (2)
From this set of constraints, we immediately have 1 ≤ mv i ≤ Ts -(n -1). To relax the second constraint, we consider

mv n = Ts - n-1 i=1 mv i . Let function f be such that f (mv 1 , . . . , mv n-1 ) = n-1 i=1 mv i log mv i Ts + Ts - n-1 i=1 mv i log 1 - n-1 i=1 mv i Ts .
Function f is differentiable on its domain Is = [1. . Ts -n + 1] n-1 , thus we get df dmv j (mv 1 , . . . , mv n-1 ) = log mv j Ts + mv j Ts mv j

+ log 1 - n-1 i=1 mv i Ts + Ts -n-1 i=1 mv i 1 -n-1 i=1 mv i Ts = log mv j + log Ts - n-1 i=1 mv j + 2(Ts -log(Ts)).
According to Equation 2, we have log mv j + log Ts -n-1 i=1 mv j ≥ 0 and, as Ts 1, this implies Ts -log(Ts) > 0. Then, we obtain that df dmv j > 0, leading to the fact that f is strictly increasing according to mv j . The maximum is then reach for mv j = Ts -n + 1 (f is a Schur-convex function).

From the set of constraints (cf. Equation 2), if the maximum of D(q||p (U ) ) is reached for mv j = Ts -n + 1 then

n i=1,i =j mv i = n-1 implies that ∀i ∈ [1.
.n], i = j, mv i = 1, which concludes the proof. This allows us to formulate an upper-bound D max on the KL-divergence between the uniform stream and any other stream:

D max = D(q||p (U ) ) = log(n) + log(Ts) -1 - n -1 Ts log (Ts -n + 1) . ( 3
)
Thus any input stream σ is D max -close (cf. Definition 5.2).

To determine the minimal effort that the adversary has to exert to bias the input stream so that both uniformity and ergodicity properties do not hold, we use the Earth Mover's Distance (EMD) between the uniform distribution and the target one. In the following, when we say that the adversary replaces node id vi by node id vj, we mean that he drops vi from the input stream and injects vj instead. Recall that the adversary is able to drop and inject node ids only from the nodes it controls. However, as motivated in the introduction, the adversary may succeed in surrounding a honest node with malicious nodes so that it may shape by itself the input stream of this honest node. Lemma 6.2. (Optimal strategy to maximize the divergence) Given an input stream σ, replacing the less frequent node id in σ with the most frequent one maximizes the gain in KL-divergence with respect to the uniform distribution for the same amount of work as measured by the EMD distance.

Proof. Given an input stream σ represented by the probability distribution q, we construct the input stream σ from σ by substituting one occurrence of node id vi with node id vj so that D(q ||p (U ) ) is maximized after this replacement (where q denote the probability distribution representing σ ). This amounts to maximizing D(q ||p (U ) ) -D(q||p (U ) ) .

Recall that all node ids in S must be present in σ . Therefore, we search for the node id pair (vi, vj) such that

         m v j = mv j + 1 m v i = mv i -1 vj = arg maxv j ∈S q v j log q v j -qv j log qv j vi = arg maxv i ∈S q v i log q v i -qv i log (qv i )
Consider the function f : x → x log(x), which is strictly increasing. As for any k ∈ S, qv k = mv k /Ts, we have:

   vj = arg maxv j ∈S f mv j +1 Ts -f mv j Ts vi = arg maxv i ∈S f mv i -1 Ts -f mv i Ts =⇒ vj = arg maxv j ∈S mv j vi = arg minv i ∈S mv i
This leads from the fact that the function g1 :

x → f ( x+1 Ts )- f ( x Ts ) (respectively g2 : x → f ( x-1 Ts ) -f ( x Ts )
) is strictly increasing (respectively strictly decreasing). Thus the optimal node id replacement that maximizes the KL-divergence gain is obtained by replacing the less frequent node id vi with the most frequent one vj.

Algorithm 1 shows an optimal implementation of Lemma 6.2 with respect to the number of performed replacements. This algorithm is run by the adversary. Specifically, the inputs of the algorithm are τs and an input stream σ that feeds the sampler component S s u of some honest node u. Recall that τs is the robustness threshold of the sampling strategy s implemented by S s u , i.e., for any τs-close input stream σ, the sampling strategy s is able to output a uniform and ergodic sample. The goal of the greedy Algorithm 1 is to tamper with the input stream σ in order to increase its KLdivergence above τs with a minimum effort.

return

By assumption, the adversary is omniscient and therefore has the capacity to observe the entire input stream σ. From Section 4, the adversary knows the strategy s of the sampler, and thus can compute the value of τs. The value of the maximum divergence D max is computed using Relation (3). If D max is larger than or equal to the robustness threshold, the algorithm returns "fail". Otherwise at each iteration, the adversary performs the optimal node id replacement until the KL-divergence exceeds the robustness threshold. Remember however, that the adversary cannot drop messages that have been sent or forwarded by nodes it does not control (i.e. the honest ones). Note that at lines ( 8) and ( 9) of Algorithm 1 both mv i and mv j are updated. Counter returned by Algorithm 1 represents the number of replacements done by the adversary.

Consider a sampling strategy s, its robustness threshold τs, and an input stream σ. Let be the number of replacements executed in Algorithm 1. If we denote by q σ( ) the probability distribution derived from σ after these optimal replacements, then we have Corollary 6.3. (Lower bound on the effort exerted by an omniscient adversary) The minimum number of replacements an omniscient adversary has to apply to exceed τs is

δ = inf ∈ N : D(q σ( ) ||p (U ) ) > τs . (4)

BLIND ADVERSARY MODEL

In this section, we study the behavior of a blind adversary, that is an adversary that only has the capacity to observe messages sent or received by the nodes he controls. A strategy that the adversary might apply to bias the input stream is to choose a node id (possibly one that belongs to a malicious node but not necessarily) and to push it in the input stream as much as possible. We show that this strategy is optimal with respect to the effort exerted by the adversary and we give the lower bound on the expected minimum amount of work a blind adversary has to exert to bias the input stream.

Theorem 7.1. (Lower bound on the expected effort exerted by a blind adversary) Let s be a sampling strategy, τs its robustness threshold and Ts the maximum convergence time of s. The minimum number of replacements a blind adversary has to apply in expectation to exceed τs is given when the input stream is the uniform one. We have δ = inf { ∈ Is : R > τs} [START_REF] Baldoni | TERA: Topic-based Event Routing for Peer-to-peer Architectures[END_REF] where Is = 0..Ts -n + 1 -Ts Proof. Let us consider the uniform node ids stream on a window of length Ts. For any vi ∈ S, vi is present in the stream Ts/n in average. Thus the probability distribution p (U ) is such that ∀vi ∈ S, p (U ) v i = 1/n. From Section 6, we have seen that the optimal strategy for the adversary to bias an input stream is to replace the less frequent node id in this stream with the most frequent one. By assumption, the adversary is blind and cannot observe all the node ids of the input stream. Thus the strategy the adversary applies consists in choosing a specific node id vj and repeatedly pushes vj in the input stream. Let σ be an input stream and σ be the stream obtained from σ after one step of this adversarial strategy (i.e., replacing vi by vj for some vi ∈ S). We have

D(q σ ||p (U ) ) -D(qσ||p (U ) ) = 1 n log mv j mv j + 1 + log mv i mv i -1 , (6)
where qσ and q σ represent respectively the probability distributions of σ and σ . In the following, q σ( ) denotes the probability distribution derived from σ after replacements. Given a sampling strategy s, we prove by induction on the number of optimal replacements that, starting from a uniform stream, the maximum KL-divergence after replacements is given by D(q σ( ) ||p (U ) ) = R where

R = 1 n -1 Ts n -1 log Ts n + log T 2 s Ts + n (7)
-log Ts -n 1 + ( -1) mod Ts n -1

Note that cannot be greater than Ts -n + 1 -Ts n . Indeed, all node ids in the initial uniform stream are present at least Ts n times and the maximum number of times a unique id can appear in the stream is (Ts -n + 1).

For = 1, the claim immediately holds from Equation 6. Now, assume that the claim also holds for all 1 ≤ k ≤ . We show that the claim holds for k = + 1. The KL-divergence with respect to the uniform stream after + 1 steps is

D(q σ( +1) ||p (U ) ) = D(q σ( ) ||p (U ) ) + D(q σ( +1) ||p (U ) ) -D(q σ( ) ||p (U ) ). (8)
The term D(q σ( +1) ||p (U ) ) -D(q σ( ) ||p (U ) ) represents the gain of step ( +1), and D(q σ( ) ||p (U ) ) is given by Equation 7. Two sub-cases need to be considered: (i) mod Ts n -1 = 0 and (ii) mod Ts n -1 = 0. Case (i): the less frequent node id vi in the stream at step + 1 is the same as the one removed at step . After steps, mv j = Ts n + and mv i = Ts n -1 + ( -1) mod Ts n -1 , thus the right part of Equation 6 is equal to By assumption (i), we have From Equation 8, we get

D(q σ( +1) ||p (U ) ) = = 1 n Ts n -1 log Ts n + log T 2 s Ts + n( + 1) -log Ts -n 1 + mod Ts n -1 ,
which ends Case (i).

Case (ii). The argumentation is the same as above. However, as mod Ts n -1 = 0, the node id that has been previously replaced is now present exactly once in the stream. Thus the adversary needs to randomly choose another node id in the stream before processing the next step of his strategy. Thus applying Equation 6 at step + 1 gives

D(q σ( +1) ||p (U ) ) -D(q σ( ) ||p (U ) ) = 1 n log Ts n + Ts n + + 1 + log Ts n Ts n -1 . (9)
By assumption ( -1) mod Ts n -1 = Ts n -1 -1 , and by combining the induction hypothesis 7 with the gain obtained at step + 1 (Equation 9), we get

D(q σ( +1) ||p (U ) ) = 1 n -1 Ts n -1 log Ts n + 3 log (Ts) -log (Ts + n( + 1)) -log (Ts -n) -log (n)) .
By assumption of the case : As a conclusion, any value of that allows the adversary to exceed the robustness threshold τs defeats the sampling strategy. Thus, the minimum number of replacement operations δ is the lower bound of this set of values.

We now evaluate the minimum amount of work a blind adversary has to exert, in the worst case, to bias the input stream. In the worst case, the node id vi the adversary has chosen to blindly flood might be initially present only once in the input stream. In order to bias the input stream, the adversary needs to push id vi sufficiently often so that the probability of appearance of id vi reaches the uniform value, with respect to all the other node ids, and then to continue to push this id δ times so that the divergence between the resulting stream and the uniform one is maximum.

Theorem 7.2. (Lower bound on the effort exerted by a blind adversary) Let s be a sampling strategy, τs its robustness threshold and Ts the maximum convergence time of s. The minimum number of replacements the adversary has to apply on a stream, in the worst case, to exceed τs is

δ + Ts n -1.
Proof. The proof is immediate. First, the adversary has to raise the chosen id at least up to the uniform value. As in the worst case, this id is present only once in the initial stream, this costs Ts n -1 replacements to reach a number of occurrences equals to Ts n . Moreover, once this id is present in the modified stream Ts n times, the adversary follows the same strategy as before, which requires δ more steps to guarantee that the robustness threshold τs is exceeded. Note that this value is a worst-case bound and not the exact minimum value with respect to τs because after the first ( Ts n -1) steps, the modified stream could be different from the uniform one. In this situation, the KL-divergence to the uniform stream is strictly greater than 0, reducing accordingly the amount of work of the adversary to exceed τs.

CONCLUSION AND OPEN ISSUES

In this paper, we have focused on the problem of achieving uniform and ergodic peer sampling in large scale open systems potentially populated with malicious peers. This problem consists in guaranteeing that the knowledge of the system maintained by each honest peer is a uniform and non permanent sample of the whole population of the system. By modeling input streams as probability distributions, we have characterized the minimum effort (measured in terms of node ids replacements) that an omniscient and a blind adversary have to exert on the input stream of node identifiers to exceed the robustness threshold that quantifies the power of a sampling strategy. Similarly to (pseudo)-random number generators that are considered as the basic mathematical tool to generate complex probability distributions, we believe that uniform peer sampling should be regarded as a necessary building block to derive larger classes of sampling schemes. This building block is of utmost importance in systems in which the population is continuously evolving and thus, where it is impossible to capture the full complexity of the network through global snapshots.

We conjecture that there exists a total order relationship on the power of (non-)ergodic uniform sampling strategies with respect to their robustness threshold τ . This can be depicted by using a planar representation as shown by Figure 2. Each τ -radius circle in this picture represents the class of τ -close uniform sampling strategies. For instance, in this representation the strategy proposed by Bortnikov et al. [START_REF] Bortnikov | Brahms: Byzantine Resilient Random Membership Sampling[END_REF] belongs to the largest circle corresponding to τ = ∞ on its non ergodic part (left side). As another illustrative example, the sampling strategy proposed in Busnel et al. [START_REF] Busnel | On the Uniformity of Peer Sampling based on View Shuffling[END_REF] should be ranked as less powerful than the one proposed by Gurevich et al. [START_REF] Gurevich | Correctness of Gossip-Based Membership under Message Loss[END_REF] since the latter one achieves uniform and ergodic sampling despite message loss contrary to the former one. Both strategies would appear in the ergodic part of the representation (right side). Finally, we think that this classification can be used as a tool to precisely compare any two sampling strategies as different as they are (e.g., [START_REF] Awerbuch | Towards a Scalable and Robust Overlay Network[END_REF] and [START_REF] Massoulié | Peer Counting and Sampling in Overlay Networks: Random Walk Methods[END_REF]). As future work, we intend to rank the state-theart sampling algorithms in the light of this new framework. Moreover, we plan to extend this work by integrating other dimensions, such as space and time resources, and deterministic versus probabilistic strategies.

Figure 1 :

 1 Figure 1: Sampling component of node u ∈ N .

Algorithm 1 :

 1 Adversary biasing strategy Data: an input stream σ, the robustness threshold τs Result: the number of replacements if it exists 1 if τs ≥ D max then 2 return "fail" maxv j ∈S mv j ; 6 while D(qσ||p (U ) ) ≤ τs do 7 vi ← arg min {v∈S:mv i =1} mv i ; 8 let k be the index of an item in the part of the stream controlled by an adversary such that σ[k] = vi ; 9 σ[k] ← vj //one occurrence of vi is dropped and vj is injected instead ; 10 ← + 1;

2 s

 2 Ts + n -log Ts -n 1 + ( -1) mod Ts n -1

1 +

 1 log (Ts + n ) -log (Ts + n( + 1)) -log Ts -n 2 + ( -1) mod Ts n -1.

T 2 s

 2 induction: D(q σ( +1) ||p (U ) Ts + n( + 1)-log Ts -

Figure 2 :

 2 Figure 2: Characterization of Sampling Strategies

Although malicious nodes have also access to a sampling component, we cannot impose any assumptions on how they feed it or use it as their behavior can be totally arbitrary.


Patrick Adde

Christophe Jego

Raphaël Le Bidan

Ernesto Perez

Chamorro Jorge
email: jorge.perezchamorro@ieee.org

Raphael Le Bidan

Jorge Ernesto

Perez Chamorro

Design and implementation of a soft-decision decoder for Cortex codes

INTRODUCTION

Forward Error Correction (FEC) is a powerful technique to improve performance of digital communication systems. Nowadays, modern FEC techniques such as turbo codes or Low-Density Parity-Check (LDPC) codes allow to closely approach the ultimate limit of channel capacity on a variety of channel models, for sufficiently long code length. On the other hand, a long FEC code introduces latency which may not be tolerable for certain applications such as sensor networks. In the short block length regime (a hundred code bits or less), block codes with soft-decision decoding at the receiver side may offer a practical and efficient alternative to modern FEC schemes and traditional convolutional codes also. This requires in turn block codes with good minimum distance properties (to guarantee good error-rate performance), and, more importantly, enough structure to facilitate the design of a low-complexity soft-decision decoder. We recall here that, in contrast to classical hard-decision decoders which operate on binary values, a soft-decision decoder directly process the unquantized (or quantized in more than two levels in practice) samples at the output of the matched filter, thereby avoiding the loss of information. Soft-decision decoding may offer up to 3 dB coding gain over hard-decision decoding, but with more computational complexity.

Cortex codes are a family of rate-1/2 self-dual linear block codes first introduced in [START_REF] Carlach | A new family of block turbocodes[END_REF]. The construction of Cortex codes combines a very short mother code with a sequence of permutations to produce the parity bits. If the mother code is self-dual, the resulting Cortex code inherits from the self-dual property [START_REF] Carlach | A systematic construction of selfdual codes[END_REF]. This implies in particular that the (n-k)×n paritycheck matrix (in systematic form) of an (n, k) Cortex code can be written as H=[P, I n-k ], with I n-k the (n-k)×(n-k) identity matrix and where the (n-k)×k sub-matrix P satisfies: P×P t =I n-k . The Cortex construction opens a broad spectrum of possibilities for the construction of either short or long structured rate-1/2 systematic linear block codes with good minimum distance properties [START_REF] Olocco | A family of self-dual codes which behave in many respects like random linear codes of rate 1/2[END_REF].

Maximum-likelihood (ML) soft-decision decoding is known to offer the best decoding performance, but it is usually computationally intractable for most codes of practical interest. Hence sub-optimal decoding algorithms have to be considered. Belief Propagation (BP) is a soft-input soft-output decoding algorithm relying on the exchange of soft information along the edges of a graph defined by the paritycheck matrix H of the code [START_REF] Kschischang | Factor Graphs and the Sum-Product Algorithm[END_REF]. BP is known to closely approximate the performance of optimal Maximum A Posteriori (MAP) decoding at reduced complexity for codes with sparse parity-check matrices. On the other hand, BP performs poorly with codes like Cortex codes having highdensity parity-check matrices, due to the presence of many short cycles in the graph. Another approach to soft-decision decoding, called reliability-based decoding, exploits the reliability of the received symbols to search for the most likely codeword in a reduced list of candidates. A first category of algorithms in this family applies a series of candidate error patterns in the least reliable positions in the received word followed by a hard-decision decoding step in order to correct the remaining errors (if any). This category includes the softdecision decoding algorithms devised by Chase [START_REF] Chase | A class of algorithms for decoding block codes with channel measurement information[END_REF]. Another category performs successive re-encoding of a set of candidate information sequence to produce to generate the list of candidate codewords. The Ordered Statistics Decoding (OSD) approach falls into this category [START_REF] Fossorier | Soft-decision decoding of linear block codes based on ordered statistics[END_REF].

Recently, a simple and efficient algorithm was introduced in [START_REF] Adde | Maximum likelihood soft decoding of systematic block codes: from algorithm to architecture[END_REF] for soft-decision decoding of rate-1/2 systematic linear block codes with a parity-check matrix H composed of an invertible sub-matrix P. This algorithm can be applied to any self-dual codes. It is particularly attractive for short Cortex codes since it offers near-ML performance at low decoding complexity in this case. To our knowledge, no digital implementation of soft-decision Cortex decoders with acceptable performance has been reported up to now. In contrast, analogue decoding was successfully applied to Cortex codes by taking advantage of a particular bipartite graph representation (Cortex graph) which can be mapped onto a network of analogue operators [START_REF] Perez Chamorro | A subthreshold PMOS analog cortex decoder for the (8,4,4) Hamming code[END_REF].

The remainder of the paper is organized as follows. Section II describes the construction of Cortex codes. Section III introduces the proposed decoding algorithm and its performance. The challenging issue of designing a decoder for (32, 16, 8) Cortex codes is discussed in Section IV. Finally, a FPGA prototype of the decoder is described in Section V.

II. CORTEX CODES CONSTRUCTION

The general encoding structure for Cortex codes is shown in Fig. 1 [START_REF] Carlach | A new family of block turbocodes[END_REF][START_REF] Carlach | A systematic construction of selfdual codes[END_REF]. The k information bits are first split into m subsequences of length-b bits each. Each sub-sequence is encoded by a rate-1/2 systematic base mother code such as the [START_REF] Perez Chamorro | A subthreshold PMOS analog cortex decoder for the (8,4,4) Hamming code[END_REF][START_REF] Kschischang | Factor Graphs and the Sum-Product Algorithm[END_REF][START_REF] Kschischang | Factor Graphs and the Sum-Product Algorithm[END_REF] extended Hamming code [START_REF] Carlach | A systematic construction of selfdual codes[END_REF] or the (4,2,2) Hadamard code [START_REF] Perez Chamorro | Decoding a family of dense codes using the sumproduct algorithm and subthreshold PMOS[END_REF], to produce a sub-sequence of m intermediate parity bits. Then, a permutation is applied to the whole sequence of k parity bits and the encoding process is iterated several times. The final codeword is obtained by concatenating the k message bits with the k final parity bits.

C C C C C C C C C I N T E R L E A V E R

Fig.1: General Cortex encoding scheme

The minimum distance (and thus the decoding performance) of the Cortex code is influenced by the choice of the mother code, the number of encoding stages, as well as by the choice of the permutation functions. To our knowledge, no systematic design procedure has been yet proposed for the specification of the number of encoding stages and their structure. On the other hand, a method for the generation of the interleavers is described in [START_REF] Perez Chamorro | Decoding a family of dense codes using the sumproduct algorithm and subthreshold PMOS[END_REF]. This technique guarantees the construction of Cortex codes with the highest minimum distance for a given block length. A simple construction results by using the same mother code and interleaver at all encoder stages. The (4,2,2) Hadamard code has been chosen as the mother code in our study since it was shown in [START_REF] Perez Chamorro | Decoding a family of dense codes using the sumproduct algorithm and subthreshold PMOS[END_REF] to yield codes with high minimum distance. Further, the inverse of this code is easily obtained as shown in Fig. 2. Encoding equations and their Fig. 3 shows how to construct a (16,8,5) Cortex code from the (4,2,2) Hadamard code, using 4 encoding stages separated by 3 identical interleavers. The minimum distance d min =5 is known to be the highest possible minimum distance that can be achieved with a (16,8) binary linear block code. The soft-decision decoding algorithm introduced in [START_REF] Adde | Maximum likelihood soft decoding of systematic block codes: from algorithm to architecture[END_REF] first applies a series of Neps error patterns in order to try to eliminate the errors located in the least reliable positions inside the k information bits (first k bits in the received word). Each candidate information sequence is re-encoded to produce a candidate codeword. The same procedure is applied in parallel to the k parity bits, by inverting the encoding equations in order to re-compute the k message bits from the k parity bits. This produces a second list of Nepr candidate codewords. The decoder finally selects the candidate codeword at minimum Euclidean distance from the received word. Compared to the algorithms in [START_REF] Chase | A class of algorithms for decoding block codes with channel measurement information[END_REF] and [START_REF] Fossorier | Soft-decision decoding of linear block codes based on ordered statistics[END_REF], the proposed algorithm is computationally much simpler since it does not require a Gaussian elimination nor a hard-decision decoder. The error pattern generation strategy is similar to the one in [START_REF] Fossorier | Soft-decision decoding of linear block codes based on ordered statistics[END_REF]. channel. Soft-decision decoding was performed on 8-bit fixedpoint received samples, using Neps+Nepr=64 error patterns for both the systematic and the parity part. Although not shown explicitly in Fig. 4, simulation results show that short Cortex codes (n≤48) essentially achieve ML decoding performance at low complexity. On the other hand, a higher number of error patterns is required to maintain performance close to ML softdecision decoding with longer Cortex codes (n>48).

reciprocals read: O 1 =I 2 , O 2 =I 1 ⊕ I 2 and O 1 = I 1 ⊕ I 2 , O 2 =I 1 , respectively.

IV. SOFT DECODER ARCHITECTURE FOR CORTEX CODES

Designing soft decoding architectures for Cortex codes is a challenging issue. In this section, a digital implementation of a decoder based on the proposed soft decoding algorithm for (32,16,8) Cortex code is detailed. The decoder uses information quantized on 8 bits with L rs = L rp = 6 least reliable symbols and Nep = Neps+Nepr = 32+32 error patterns. The decoder architecture consists of four blocks: reception, processing, transmission and control as shown in Fig. 5. In the reception part, the n=32 binary symbols of the received word are processed sequentially. So, this block computes successively positions of the L rs and L rp least reliable symbols for the systematic and parity parts of the received word. In parallel, serial-in parallel-out shift register memorizes sequentially the 32 symbols of the received word. The processing part is composed of three main tasks. First, error patterns are generated from the sign bits of the received word by testing different combinations of 0 and 1 in the least reliable bit positions. Then, these error patterns are encoded. Finally, a selection function allows the maximum likelihood code word to be found. This selection is done from metric values computed for each error pattern. Note that a parallel processing is done for Neps and Nepr error patterns. Moreover, as the 32 binary symbols are available thanks to the serial-in parallel-out shift register, the metric of each encoded error pattern can be directly computed. The transmission unit is only composed of a parallel-in serial-out shift register. This operator enables to sequentially transmit the systematic part of the binary decoded word. The three previous blocks are supervised by a control block. In our design, this task is achieved by a 5-bit counter that generates some control signals. The soft decoder architecture is structured in two pipelined stages: reception and processing-transmission as shown in Fig. 5. The first stage sequentially processes n=32 binary symbols in 32 clock periods. The second stage is composed of two main blocks. Neps and Nepr error patterns are generated, encoded and compared in 32 clock periods thanks to a parallel processing. Finally, the 16 decoded bits are sequentially transmitted in 16 clock periods. The decoder latency, L, can be defined as the symbol number processed by the decoder during the decoding of one symbol. It depends on the number of pipeline stages and the codeword length n. According to this definition, the resulting latency of the decoder architecture is L=2n=64 clock symbols.

Logic syntheses for the hardware complexity estimations were performed using the Synopsys tool with a STMicrolectronics 0.09 μm CMOS process ASIC target. Soft decoder is clocked at f=200MHz. As shown, the more complex function is the metric computation and selection. Its complexity is almost the half of the total soft decoder complexity. By analyzing the architecture of this critical part, two parameters appear to directly affect its complexity: Nep (error patterns) and L r (least reliable binary symbols). The number of quantization bits q has also a direct impact on the decoder complexity and, in particular, on the shift register sizes. Decreasing these parameter values improves area-efficiency while the performance could decrease. A complexity analysis of the soft decoder has to be done to lead to low a complexity architecture with negligible performance degradation.

V. FPGA PROTOTYPE OF DESIGNED SOFT DECODER

In order to validate the designed soft decoder, BER performance measures have to be carried out. For this reason, we have integrated the proposed decoder into an experimental setup. The experimental setup is a development board from Dinigroup that contains 6 Xilinx Virtex5 LX330 devices. All the components of the experimental setup were implemented onto only one of the FPGAs. A Pseudo Random Generator (PRG) sends out pseudo random data streams at each clock period f 0 . This module is composed of flip-flops and XOR gates. An (32,16,8) Cortex code encoder processes the data streams. The last task of the transmitter is a BPSK mapping. We have chosen to integrate an AWGN channel from a white Gaussian noise generator adapted to hardware implementation. The Wallace method generates a variable that is normally distributed from a pool of variables that follows a normal distribution as well. High accuracy, speed and low-cost hardware are reached using this method as explained in [START_REF] Gonzalez | Design and implementation of a MIMO channel emulator onto FPGA device[END_REF]. Each output sample is a 5 bit vector to be sent in one clock period (f 0 ). The Signal to Noise Ratio (SNR) is controllable via a computer that calculates the equivalent variance square root σ and sends it to the experimental setup thanks to a PCI bus. Computation resources of the complete system take up 2,116 slice Flip-Flops and 3,974 slice LUTs. Moreover, 7 DSP resources and 1 BlockRAM of 18kbits are also necessary. The soft decoder occupies 1,114 slice LUTs, 2,905 slice Flip-Flops and 0 BlockRAM of 18Kbs. The maximum frequency estimated after place and route is 72 MHz for the soft decoder, resulting in an input data rate of T in =72 Mb/s. However, taking into account the code rate R=0.5, the output data rate becomes T out =36 Mb/s. Simulated performance of ML soft decoding algorithm and measured performance of designed soft decoder for the (32,16,8) Cortex code are plotted in Fig. 6. Performance is evaluated by Monte-Carlo simulation and hardware emulation using our experimental setup, respectively. Monte-Carlo simulations are done using a random variable and Wallace method for the AWGN channel. The prototype shows identical performance when compared to fixed-point simulation based on Wallace method, for Nep = 32+32 error patterns.

VI. CONCLUSION

Soft-decision decoding of short Cortex codes has been investigated. A soft-decision decoding algorithm has been introduced which exploits the code structure to achieve ML performance using a small number of error patterns. The digital implementation of this algorithm has been described for a specific Cortex code. The simulation results and the hardware complexity of the prototype demonstrate the practicality and the benefits of the proposed decoding algorithm in this context.

Fig. 2 :

 2 Fig.2: Encoding relations for the (4,2,2) Hadamard code

Fig. 3 :

 3 Fig. 3: (16,8,5) Cortex code built from (4,2,2) Hadamard code III. SOFT-DECISION DECODING OF CORTEX CODES

Fig. 4 :Fig. 5 :

 45 Fig.4: Soft decoding performance of different Cortex codes with Nep =32+32 and n=[4;512].The Bit-Error Rate (BER) performance of several Cortex codes with increasing length constructed from the (4,2,2) Hadamard codes is shown in Fig.4, assuming QPSK transmission over an additive white Gaussian noise (AWGN)

Fig. 6 :

 6 Fig.6: BER performance of soft decoding of a (32,16,8) Cortex code with Nep =32+32

Table 1 :

 1 Table 1 gives the complexity in terms of equivalent 2-input (NAND) gate count for each function of the soft decoder. hardware complexity of the soft decoder

	STMicrolectronics 90 nm CMOS	soft decoder functions	equivalent gate count
		least reliable bits	1 644
	reception block	serial-in, parallel-out shift register 32x8	2 679
		error pattern construction
			2184
	processing block	error pattern encoding
		metric computation and selection	4 043
	transmission block	parallel-in, serial-out shift register 16x1	194
	control block	5-bit counter	47
	soft decoder complexity	10 791

ACKNOWLEDGMENT

The authors wish to thank Pierre-Louis Bullot, Romain Ducaffy, Rémy Lopez, Angela Navarro and Wiklund Xavier (Telecom Bretagne students) for their significant help during the architecture design of the soft decoder.

code (4,2,2) Hadamard code (4,2,2) Hadamard code (4,2,2) Hadamard code (4,2,2) Hadamard code (4,2,2) Hadamard code (4,2,2) Hadamard code (4,2,2) Hadamard code (4,2,2) Hadamard code (4,2,2) Hadamard code (4,2,2) Hadamard code (4,2,2) Hadamard code (4,2,2) Hadamard code (4,2,2) Hadamard code (4,2,2) Hadamard code (4,2,2) Hadamard code


Meng Li

, Charbel

Abdel Nour

Christophe Jego
email: christophe.jego@ims-bordeaux.fr

Jianxiao Yang

Catherine Douillard

Charbel Abdel Nour

Christophe Jégo

Efficient iterative receiver for Bit-Interleaved Coded Modulation according to the DVB-T2 standard

Keywords: BICM, shuffled iterative receiver, LDPC code, rotated constellation, DVB-T2 standard

INTRODUCTION

Signal Space Diversity (SSD) [START_REF] Giraud | Algebraic tools to build modulation schemes for fading channels[END_REF][START_REF] Boutros | Signal space diversity: A powerand bandwidth-efficient diversity technique for the Rayleigh fading channel[END_REF] doubles the diversity order of the conventional BICM schemes and largely improves the fading performance especially for high coding rate systems [START_REF] Nour | Improving BICM performance of QAM constellations for broadcasting applications[END_REF]. When a severe fading occurs, BICM with SSD [START_REF] Nour | Improving BICM performance of QAM constellations for broadcasting applications[END_REF] avoids the simultaneous fading in both the I and Q components leading to important gains. This scheme has been adopted by the second generation of the terrestrial digital video broadcasting standard (DVB-T2). In order to achieve additional improvement in performance, iterations between the decoder output and the demapper (BICM-ID) can be introduced. BICM-ID with an outer LDPC code was investigated for different DVB-T2 transmission scenarios [START_REF] Nour | Improving BICM performance of QAM constellations for broadcasting applications[END_REF]. It is shown that an iterative processing associated with SSD can provide additional error correction capability reaching more than 1.0 dB over some types of channels. Thanks to these advantages, BICM-ID has been recommended in the DVB-T2 implementation guidelines [START_REF] Dvb-T2 | Implementation guidelines for a second generation digital terrestrial television broadcasting system (DVB-T2)[END_REF] as a candidate solution to improve the performance at the receiver. However, designing a low complexity high throughput iterative receiver remains a challenging task. One critical problem is the additional latency introduced by this additional iterative loop. Therefore, a more efficient information exchange method between the demapper and the decoder has to be applied. Another critical problem is the computation complexities of both the rotated QAM demapper and the LDPC decoder. In [START_REF] Li | Design of Rotated QAM Mapper/Demapper for the DVB-T2 Standard[END_REF], a flexible demapper architecture for DVB-T2 is presented. Lowering complexity is achieved by decomposing the rotated constellation into two-dimensional sub-regions in signal space. In [START_REF] Li | Design and FPFA prototyping of a bit-iterleaved coded modulation receiver for the DVB-T2 standard[END_REF], a novel complexity-reduced LDPC decoder architecture based on the vertical layered schedule [START_REF] Hocevar | A reduced complexity decoder architecture via layered decoding of LDPC codes[END_REF] and the normalized Min-Sum (MS) algorithm is detailed. It closely approaches the full-complexity BP performance provided in the implementation guidelines of the DVB-T2 standard. An additional critical problem is dealing with memory conflicts in the presence of double-diagonal, triplediagonal or multiple-diagonal sub-matrices within the parallel decoding units. They could introduce performance loss when the conflicts are not properly solved [START_REF] Marchand | Conflict Resolution by Matrix Reordering for DVB-T2 LDPC Decoders[END_REF]. Since the vertical layered schedule enables parallel LDPC decoding, this schedule can be extended to the demapping process. Circuits continuously exchanging information between the Soft-Input Soft-Output (SISO) decoder on one hand and the demapper on the other hand are appealing to the implementation. In this context, processing one frame can be decomposed into multiple parallel smaller sub-frame processing having each a length equal to the parallelism level. While having a comparable computational complexity as the standard iterative schedule, the receiver with a shuffled iterative schedule enjoys a lower latency. However, such a parallel processing requires good matching between the demapping and the decoding processors in order to guarantee a high throughout pipeline architecture. This calls for an efficient message passing between both sides. In this paper, different schedule solutions are investigated for the DVB-T2 standard. The remainder of the paper is organized as follows. In Section 2, the basic principles of the BICM-ID and SSD are briefly recalled. The detection principle for rotated constellation and a vertical layered decoding using a normalized MS algorithm are also introduced. In Section 3, hardware oriented iterative processing for the BICM receiver is detailed. Finally, simulation results validate the potential of the proposed iterative receiver for the DVB-T2 standard. The SSD introduces two modifications to the classical BICM system, which are shown in Fig. 1. The classical QAM constellation is rotated by a fixed angle α and becomes a rotated constellation whose Q component is delayed for d symbol periods, the delayed Q component and the current I component consist of a new complex symbol [START_REF] Nour | Improving BICM performance of QAM constellations for broadcasting applications[END_REF]. The in-phase and quadrature components of the classical QAM constellation are sent into two different rotated QAM symbols therefore doubling the constellation diversity of the BICM scheme. When a severe fading occurs, one of the components is erased and the according LLRs could be rescued from the remaining component. At the transmitter side, the messages u are encoded as the codeword c . Afterwards, this codeword c is interleaved by  and becomes the input sequence v of the mapper. At each symbol time t, m consecutive bits of the interleaved sequence v are mapped into complex symbol t x . At the receiver side, the demapper calculates a two-dimensional squared Euclidean distance to obtain the bit LLR ˆi t v of the i th bit of symbol v t . These demapped LLRs are then deinterleaved and used as inputs of the decoder. The extrinsic information is finally generated by the decoder and fed back to the demapper for additional iterations.

BICM-ID STRUCTURE

BICM-ID with SSD

Demapping algorithm for iterative receiver

For Gray-mapped QAM constellations, the demapper calculates two-dimensional Euclidean distance for the computation of the LLR ˆi t v related to the i th bit of v t . The

resulting ˆi t v becomes:     0 1 1 1 ( ) ( ) 2 2 0, , 0 0, , 0 ˆi i j j t t m m euc t euc t i t t t j j j j ib j j ib x x w w D x D x v ext ext                                               (1) where
I I Q Q euc t t d eq t d t d t eq t t D x y x y x                  2 , , ( ) ( ) ( )
the operator  means the Jacobian logarithm, i.e.,

            max , log 1 exp , if 5 max , log 1 exp 5 , else x y x y x y x y x y                 (3) ( ) t j
ext is the a priori information of the i th mapping bit i b of the symbol t x and is also the decoded extrinsic information from (9). . 2  is the AWGN variance.

LDPC decoding algorithm for iterative receiver

A vertical layered schedule (VSS) with the BP algorithm updates the messages between check and bit nodes in a column by column way as explained in [START_REF] Li | Design and FPFA prototyping of a bit-iterleaved coded modulation receiver for the DVB-T2 standard[END_REF].

Vertical layered BP algorithm 0. Initialization:

1. (0) mn n T llr    m M n  2.     (0) sgn m n m M n llr     ,     (0) m n m M n llr     
      ( ) ( 1) ( 1

   

( 1) ( ) sgn sgn

t t m m mn mn T T         m M n  9.     ( 1) ( ) t t m m mn mn T T           m M n  10. Hard decision according to   ( ) sgn t n T
where n llr denotes the intrinsic channel reliability value of the bit node n , mn E denotes the message sent from check node m to bit node n , mn T denotes the message sent from bit node n to check node m and n T denotes a posteriori information of bit node n .

ITERATIVE RECEIVER FOR DVB-T2

Hardware oriented iterative algorithm

To reduce the computation complexity of (1), a sub-region selection algorithm [START_REF] Li | Design of Rotated QAM Mapper/Demapper for the DVB-T2 Standard[END_REF] is proposed to avoid a complete search of signals in the constellation plane. However, when iterative processing is considered, the sub-region selection algorithm becomes sub-optimal. In fact, the selected region by the algorithm may not contain the minimum Euclidean distance due to the extrinsic information. Therefore, the Maxlog approximation is the only complexity-reduced demapping approach applied in this case.

On the LDPC side, a VSS Min-Sum (VSSMS) was proposed in [START_REF] Li | Design and FPFA prototyping of a bit-iterleaved coded modulation receiver for the DVB-T2 standard[END_REF]. It introduces only a 0.1~0.2 dBs penalty with respect to VSS BP while greatly reducing complexity. However, in the context of BICM-ID, the VSSMS introduces an additional penalty and reduces the expected performance gain. In fact, a decoding algorithm with a higher accuracy is a must in this case. The Min-Sum-3 or VSSMS3 seems to provide the required precision at the lowest impact on complexity. The difference between the VSSMS and VSSMS3 is that the 3 rd minimum values are updated and saved leading to more accuracy of the check node process 1 m M .

The crucial problem in the implementation of a frame-byframe schedule in the iterative receiver is the latency introduced by the block interleaver and block de-interleaver.

To overcome this problem, two new solutions are proposed.

The first consists of replacing the classical RAM based block interleaver and de-interleaver memorizing the connections between the demapper output and the decoder input by a Look-Up-Table (LUT). The other is the application of VSS decoding to replace of the classical layered HSS LDPC decoding. In this way, both the decoded and demapped extrinsic information could be exchanged without waiting for the complete frame processing.

Shuffled demapping and decoding algorithm

The shuffled demapping and decoding algorithm is detailed as follows. Fig. 2 also gives a graphical illustration.

Shuffled Parallel Demapping and Decoding Algorithm

      1 , 2 ,..., i Q      (observation node processing)     0 1 1 ( ) 2 0, , 0 1 ( ) 2 0, , 0 1 ˆmax 1 max i t j i t j m i t t e u ct j x j j ib w m t euc t j x j j ib w v D x ext D x ext                                           (4)
Decoder processing for

1,2,..., n Q   (check node processing)       ( 1) 1 0 1 ( 1) 0 ( ) 1 sgn , if sgn , else 0 t t m m n m m t t m m n m mn t T M n P T M E                              (5) (bit node processing) ˆ, i n t LLR v  where   1 n i    (6) ( ) ( ) ( ) , 1
, else

n t t n n m n m M n LLR t T LLR E           (7) ( ) ( ) ( ) t t t mn n mn T T E   (8)
(bit node updating for next demapping)

( ) ( ) t t n n n ext T LLR   (9)
(check node updating)    

,

t t m m mn mn T T         m M n  (10)                         ' ' ' 1 0 0 0 1st 1 1 1 1 2nd 1 2 2 2 3rd min , , index min , , index min , , index t
t m m n m m mk t t m m n m m mk t t m m n m m mk M T T P M M T T P M M T T P M                 (11) ' where ( ) \ k N m n  .
The demappers perform (4) for the corresponding bits. Still for these updated bits, the decoding processors perform equation ( 5)-( 11). Then another group of Q bits are considered. The advantage of such a scheduling is a lower decoding latency leads to a decrease in the number of required iterations and/or better BER performance.

EXPERIMENTAL RESULTS

The simulation is carried out for all the schedules. Two comparisons of simulated performance of BER for different decoding schemes (QPSK and 16QAM, a code rate R=4/5 and 16,200 bit frames), are presented in Fig. 3 and Fig. 4, with a maximum of 50 iterations. The channel model used to simulate and emulate the effect of erasure events is a modified version of the classical Rayleigh fading channel. More information about this model is given in [START_REF] Li | Design of Rotated QAM Mapper/Demapper for the DVB-T2 Standard[END_REF]. Eb/N0(dB) There is around 1.0 dB performance improvement @ 10e-6 of BER for the iterative floating point VSSBP receiver when compared to the non-iterative receiver. The gain increases to 2.0 dB when a 16QAM constellation is used. In a BICM-ID context, VSSMS3 enjoys a reduced penalty with respect to VSSBP. In other words, iterative processing between the decoder and the demapper seems to reduce the penalty of suboptimal LDPC decoding. In both cases, fixed point algorithms suffer from a small performance loss compared with floating point algorithms. However, this penalty is once again smaller for the iterative receiver.

1 0 -3 1 0 -2 1 0 -1 1 0 -4 1 0 -5 1 0 -6 1 0 -7 1

CONCLUSION

In this paper, we have investigated possible scheduling of the BICM iterative receiver. It defines the order of passing messages between the demapper and the decoder. Our objective is to ensure a good matching between reception algorithms on one hand and the iterative receiver architecture on the other hand. Hardware-oriented simulated BER performance was given for two reception schemes over a fading channel with erasure. These results validate the potential of an iterative receiver as a practical and a competitive solution for the DVB-T2 standard.

Currently, an FPGA prototyping to measure the performance of the proposed iterative receiver is under integration.

Fig. 1 :

 1 Fig. 1: (a) The BICM with SSD transmitter; (b) Conventional BICM-ID receiver.

  the square of the Euclidean distance between the constellation point and the equalized observation, i.e, 2

  inphase and quadrature components of the equalized complex symbol , eq t y . t  is a scalar representing the channel attenuation at time t. i b  represents the subset of constellation symbols with i th bit i

  parallel processing unit with Q bits ( Q can be 1, 45, 90, 120, 180 or 360), performing the following algorithm for the current code bit index 1,2,...,

Fig. 2 .

 2 Fig.2. The basic idea of the parallelized iterative receiverThere are several possible message passing schedules. They correspond to the possible combinations of the parallelism of LDPC decoder and the message passing ways between the LDPC decoder and the demapper.

Fig. 3 :

 3 Fig. 3: Performance comparison for QPSK over a fading channel with 15 % of erasures. 16K frames, DVB-T2 LDPC, rate R=4/5

Fig. 4 :

 4 Fig. 4: Performance comparison for 16QAM over a fading channel with 15 % of erasures. 16K frames, DVB-T2 LDPC, rate R=4/5

Table . 1

 . different message passing schedules for the iterative receiver Schedule B and Schedule C is the number of the LLRs that are updated during the iterative processing at the demapper. Schedule C is the desired schedule for HW implementation.

	Schedule	A		B	C
	Receiver based on	Demapper	LDPC	LDPC
	Demapper symbols	1		90		90
	Updated LLR	2 log ( ) M	2 90 log ( ) M  	90
	LDPC Parallelism	1	90	90
	LDPC bits processed	2 log ( ) M	90	90
	Feedback Extrinsic	2 log ( ) M	90	90
	There interesting cases are listed in Table.1 under
	consideration of implementation. Schedule A is based on
	the demapper, LDPC works in the VSS schedule serially.
	Each symbol leads to	2 log ( ) M variable bits updating, then
	all the extrinsic information is fed back to the original
	symbol. Schedules B and C are based on VSS LDPC
	decoder, with parallelism of 90. So 90 variable bits get
	updated and generate 90 extrinsic informations that are fed
	back to a maximum of 90 demapper symbols. If all bits
	originate from different symbols, then there are 90
	demappers working in parallel benefiting from the extrinsic
	information to update LLRs. The difference between

ACKNOWLEDGMENT

This work has been carried out in the framework of the SME42 project of the EUREKA's Eurostars programme.


Quang Trung Dong

Matthieu Arzel

Christophe Jégo
email: christophe.jego@ims-bordeaux.fr

Design and FPGA Implementation of Stochastic Turbo Decoder

Stochastic decoding that is inspired by stochastic computation is an alternative technique for decoding of error-correcting codes.

The extension of this approach to decode convolutional codes and turbo codes is discussed in this article. The switching activity sensitivity is circumvented and the latching problem is reduced by transforming the stochastic additions into stochastic multiplications in the exponential domain and using multiple streams with deterministic shufflers. The number of decoding cycles is thus considerably reduced with no performance degradation. Stochastic decoding, previously applied to the decoding of LDPC codes, can now be applied to decoding of turbo codes. In addition, the first hardware architecture for stochastic decoding of turbo codes is presented. The proposed architecture makes fully-parallel turbo decoding viable on FPGA devices. Results demonstrate the potential of stochastic decoding to implement fully-parallel turbo decoders.

INTRODUCTION

Principles of stochastic computation were elaborated in the 1960's by Gaines [START_REF] Gaines | Stochastic computing[END_REF] and Poppelbaum et al. [START_REF] Poppelbaum | Stochastic computing elements and systems[END_REF] as a method to carry out complex operations with a low hardware complexity. The main feature of this method is that the probabilities are converted into streams of stochastic bits using Bernoulli sequences in which the information is given by the statistics of the bit streams. Complex arithmetic operations on probabilities such as multiplication and division are transformed into operations on bits using elementary logic gates. Stochastic decoding of Forward Error Correction (FEC) is inspired by these principles. The two main appealing features of this approach for iterative decoding are very simple hardware structures of computing nodes and high-throughput decoding. Early stochastic methods were only successful for decoding special short/acyclic Hamming [START_REF] Gaudet | Iterative decoding using stochastic computation[END_REF] or LDPC codes [START_REF] Gross | Stochastic implementation of LDPC decoders[END_REF]. These methods result in poor decoding performance when used to decode practical codes on factor graphs (with cycles). An improved stochastic decoding approach was then proposed to decode practical LDPC codes [START_REF] Sharifi Tehrani | Stochastic decoding of LDPC codes[END_REF]. When compared with conventional Sum-Product implementations, stochastic decoding could provide near-optimal performance for practical LDPC codes. The potential of this method for lowcomplexity decoding was validated by an FPGA implementation of a (1024, 512) LDPC decoder. This first implementation provides a throughput of 706 Mbps at a Bit Error Rate (BER) of 10 -6 with performance loss of about 0.1 dB, compared to the floating-point BP, while occupying only 36% of a Virtex-4 LX200 FPGA device [START_REF] Sharifi Tehrani | An areaefficient FPGA-based architecture for fully-parallel stochastic LDPC decoding[END_REF]. High data rates and architecture efficiencies were achieved thanks to many recent improvements [7] [8]. In addition, this approach was extended to well-known linear block codes with high-density parity-check matrices, namely BCH codes, Reed Solomon codes and product codes [START_REF] Sharifi Tehrani | Stochastic decoding of linear block codes with high-density parity-check matrices[END_REF]. Moreover, stochastic decoding is also of high interest for low power decoders [START_REF] Gaudet | Switching activity in stochastic decoders[END_REF] and fault-tolerant nanoscale circuits [START_REF] Winstead | A probabilistic LDPC-coded fault compensation technique for reliable nanoscale computing[END_REF].

Turbo codes [START_REF] Berrou | Near shannon limit error correcting coding and decoding: Turbo-codes[END_REF] are a family of FECs that are especially attractive for mobile communication systems and have been adopted as part of several channel coding standards for high data rates such as UMTS and CDMA2000 (third-generation) or 3GPP-LTE (the last step toward the fourth generation). A major challenge in the implementation of turbo decoders is high-throughput decoding. Indeed, the next generations of mobile communication systems will require data rates of 1 Gb/s and beyond. Designers try to exploit the maximum feasible amount of parallelism in turbo decoders for the sake of higher throughput. However, due to the lack of parallelism in the MAP-based decoding algorithm, the implementation of fully-parallel turbo decoders is still challenging for practical turbo codes.

Another form of stochastic algorithm was proposed in [START_REF] Winstead | Stochastic iterative decoders[END_REF] and used for trellis decoding algorithm of an acyclic [START_REF] Bahl | Optimal decoding of linear codes for minimizing symbol error rate[END_REF][START_REF] Winstead | A probabilistic LDPC-coded fault compensation technique for reliable nanoscale computing[END_REF] Hamming code and a (256,121) product Turbo code based on 32 component decoders of this Hamming code. An improved stochastic decoding approach was recently introduced to decode convolutional codes and turbo codes [START_REF] Dong | Stochastic Decoding of Turbo Codes[END_REF]. The results provided in this paper validate the potential of stochastic decoding as a practical approach for highthroughput turbo decoders and encourage to keep on investigating in this way. One major problem in stochastic decoding which deeply degrades the performance is related to the sensitivity to the level of random switching activity. Different solutions such as Edge Memories (EMs) [START_REF] Sharifi Tehrani | Fully parallel stochastic LDPC decoders[END_REF] have been suggested to solve this latching problem. In [START_REF] Arzel | Stochastic multiple-stream decoding of Cortex codes, submitted at Signal Processing[END_REF], authors introduced an original idea to reduce the number of clock cycles required to decode one codeword and to replace the EMs by simple deterministic shufflers. The proposed architecture, that uses multiple streams in parallel to represent the same probability, presents the best architecture efficiency defined as the ratio between data throughput and hardware complexity.

Thanks to these previous studies, this paper discusses the implementation issues of stochastic turbo decoders. The first FPGA-based implementation of a stochastic turbo decoder is presented. The remainder of the paper is organized as follows. Section 2 recalls the basic principles of turbo decoding and stochastic computation. Details of multiple stream decoding of turbo codes are given in Section 3. Synthesis and turbo decoding performance results for a turbo decoder are finally presented.

STOCHASTIC IMPLEMENTATION OF THE APP ALGORITHM

For convolutional turbo codes, the decoding is performed using the BCJR algorithm, also known as the MAP algorithm [START_REF] Bahl | Optimal decoding of linear codes for minimizing symbol error rate[END_REF]. It was adapted by Anderson and Hladik to deal with tail-biting codes. A sub-optimal version of the MAP algorithm in the logarithmic domain with an acceptable loss of performance referred to as Sub-MAP algorithm was then introduced. The stochastic decoding of turbo codes requires the stochastic computation to be applied to a tail-biting A Posteriori Probability (APP) algorithm, which relies on the trellis representation. Fig. 1 details the exchange of information between the various sections of a tail-biting APP decoder.

. Stochastic tail-biting APP decoder

There are as many sections as symbols to decode and each section is made up of five modules. A  module is fed by the channel outputs u i and v i , which are associated with the i th transmitted symbol d i and its parity bit y i . This module converts u i and v i into a priori probabilities, represented by two stochastic streams to compute the branch metrics and then the forward metrics in an A module and the backward metrics in a B module. These modules are involved in a recursive process since they use the forward and backward metrics α i and β i+1 from their neighbors and provide them α i+1 and β i . A Dec module decides the final value of each binary symbol, d i for the transmitted symbol d i . A last module is also required if the APP decoder is part of a turbo decoder: the Extr module. This module computes the output extrinsic probability Pr ex out which is then used by a module  of the second APP decoder as the input Pr ex in . In stochastic decoding, probabilities received from the channel are transformed to streams of stochastic bits using Bernoulli sequences. Each bit in the stream is likely to be '1' with the probability to be transformed. All the modules exchange stochastic streams over a logic gate network based on the code trellis representation. Each stochastic decoding step is referred to as a decoding cycle (DC) and corresponds to the output of one new bit for each stochastic unit. The decoding process terminates when a maximum number of DCs is reached.

Using stochastic representation, operations on probabilities are transformed into bit-serial operations on stochastic streams using simple processing elements. Multiplication and division are thus processed by simple logic gates. From the equations of the APP algorithm, it can be noted that besides the multiplication and division operations, a huge number of additions is necessary. Since the addition of values in the interval [0, 1] may take values bigger than 1, this operation cannot be done directly with stochastic streams. In practice, a multiplexer can produce an output stream that is the scaled sum of the input probabilities by randomly selecting one of the inputs. But, as the output sequence length has to be larger than the input sequence lengths to achieve the same precision, it severely slows down the decoding convergence speed. For this reason, a novel technique for implementing the stochastic addition operation has been proposed in [START_REF] Dong | Stochastic Decoding of Turbo Codes[END_REF]. It consists in transforming the stochastic additions into stochastic multiplications in the exponential domain. The number of DCs is thus considerably reduced with no performance degradation.

MULTIPLE STREAM DECODING OF TURBO CODES

Different solutions have been suggested to solve the latching problem, and thus, to improve the BER performance of stochastic decoding, such as: using supernodes, scaling the received Log-Likelihood Ratios (LLRs) up to a maximum value, Edge Memories (EMs) insertion and Noise-Dependent Scaling (NDS). Basically, these solutions aim at re-randomizing and decorrelating stochastic streams. An EM is a complex unit based on a register in which only valuable bits referred to as regenerative bits, i.e. avoiding signals stuck at '0' or '1', are written and randomly read. Such a unit is efficient to solve the latching problem when the register depth is sufficient (typically between 32 and 64) and when it is duplicated for any vertex of the decoding graph, as detailed in [START_REF] Tehrani | Tracking forecast memories in stochastic decoders[END_REF]. It means that EMs insertion is costly in terms of hardware resources. To improve that, some alternatives have been proposed such as the Tracking Forecast Memory (TFM) [START_REF] Tehrani | Tracking forecast memories in stochastic decoders[END_REF] and the Majority-based TFM (MTFM) [START_REF] Tehrani | Majority-based tracking forecast memories for stochastic LDPC decoding[END_REF]. Nevertheless, these solutions still require some hardware resources such as 8-bit registers, random address generators, adders and comparators. Re-randomizing and decorrelating stochastic streams can be done without these complex units if all the probabilities are represented by multiple stochastic streams.

An EM picks up a regenerative bit from a pool when correlation occurs. It is also possible to pick up a regenerative bit from another independent stochastic stream representing the same probability. To reduce the correlation between the concurrent streams, more than two are required. Moreover, the regenerative bit has to be randomly selected among them. In a multiple stream architecture, all the streams and the logic gates are duplicated p times (p>2) and the random bit selection is done by a simple shuffler. The shuffler is made of a register of p JK flip-flops -providing the stochastic normalization -, a p-bit barrel-shifter and p multiplexers. Note that the barrel-shifter is purely combinatorial with a circular shuffling rule to avoid additional random generators. The major interest of multiple stream decoding is that representing a probability by p stochastic streams instead of one divides the number of DCs by p to insure the same precision. It means that a stochastic architecture based on multiple streams has a throughput similar to any other stochastic architecture parallelized at degree p as suggested in [START_REF] Gaudet | Iterative decoding using stochastic computation[END_REF]. Four digital decoder behavioral models were written in C language to assess the decoding performance of the four decoding methods, namely the proposed multiple stream exponentional stochastic decoder, an exponentional stochastic decoder, a conventional stochastic decoder and a floating-point Sub-MAP decoder for both convolutional and turbo codes. Fig. 2 shows the BER performance of the stochastic decoding of a tail-biting RSC code (n = 400 bits, code rate R = 1/2). A decoder combining NDS and EMs provides a BER performance similar to the one of a conventional APP floating-point algorithm. Processing additions in the exponential domain enables a decrease of the number of DCs from 30K to 4K. Moreover, a 32-stream

FPGA IMPLEMENTATION AND PERFORMANCE RESULTS

Designing stochastic decoding architectures for turbo codes is a challenging issue. In this section, an implementation of a turbo decoder based on the proposed multiple stream exponentional stochastic decoding algorithm is detailed. The additional cost of addition operations in the exponential domain in terms of hardware resources is reasonable as explained in [START_REF] Dong | Stochastic Decoding of Turbo Codes[END_REF]. Indeed, expanding the Taylor series to the second order is sufficient for both exponential and logarithmic modules. Note that a stochastic architecture where all the probabilities are represented by eight independent streams has been designed. It offers a compromise between data throughput and hardware complexity for this first FPGA-based integration. Implementation results of the turbo decoder for a (n=40 bits, R=1/3) turbo code is given in Table I. First, the complexities of one section of the stochastic APP decoder in terms of resources for stochastic computation and for random bit generation are summarized. Remember that a randomization engine is necessary for providing random bits. These random bits are used in 2-to-1 multiplexers and as the addresses of stochastic stream generators. Fortunately, the complexity impact of the random bit generation can be greatly reduced by reusing them in different modules of the APP decoder and in the two decoders. In our design, 112 slice LUTs and 1,344 slice Flip-Flops are necessary for one section of APP decoder. Then, the hardware complexity of an APP decoder that contains 40 sections is given. Indeed, there are as many sections as symbols to process in the proposed fully-parallel architecture. Finally, the stochastic turbo decoder occupies 149,020 slice LUTs and 90,760 slice Flip-Flops. In order to validate the designed stochastic turbo decoder, BER performance measures have to be carried out. For this reason, we have integrated the designed turbo decoder into an experimental setup. All the components of the experimental setup were implemented onto one Xilinx Virtex5 LX330 FPGA device. A Pseudo Random Generator (PRG) sends out pseudo random data streams at each clock period f 0 . This module is composed of flip-flops and XOR gates. A (n=40, R=1/3) turbo code encoder processes the data streams. The last task of the transmitter is a BPSK mapping. We have chosen to integrate an AWGN channel from a white Gaussian noise generator adapted to hardware implementation. The Wallace method generates a variable that is normally distributed from a pool of variables that follows a normal distribution as well [START_REF] Gonzalez | Design and implementation of a MIMO channel emulator onto FPGA device[END_REF]. The Signal to Noise Ratio (SNR) is controllable via a computer that sends it to the experimental setup thanks to a PCI bus. Simulated performance of stochastic decoding algorithm and measured performance of designed 8-streams stochastic decoder for the (n=40 bits, R=1/3) turbo code are considered. The prototype shows identical performance when compared to simulation.

CONCLUSION

The paper discussed the architecture of a stochastic turbo decoder. The number of decoding cycles is considerably reduced with no performance degradation by transforming the stochastic additions into stochastic multiplications in the exponential domain and using multiple streams with deterministic shufflers. An FPGA-based architecture for a fully-parallel 8-streams stochastic decoder of a (n = 40, R = 1/3) turbo code is then presented. To the best of our knowledge, this is the first hardware implementation of a stochastic turbo decoder.

Fig. 1

 1 Fig.1. Stochastic tail-biting APP decoder

Fig. 2 .

 2 Fig.2. Stochastic decoding performance of convolutional code

Fig. 3 .

 3 Fig.3. Stochastic decoding performance of turbo code decoder with shufflers achieves similar BER performance and necessitates only 150 DCs. The stochastic decoding performance of a (n = 600 bits, R = 1/3) turbo code are given in Fig. 3. Conventional stochastic decoder based on EMs and NDS techniques achieves similar BER performance of a floating-point Sub-MAP turbo decoder with 6 iterations. The exponential stochastic approach enables the number of DCs to be reduced from 250K to 32K. The 32-streams stochastic decoder with shufflers requires only 1K DCs. It means that multiple stream architectures for stochastic turbo decoding are competitive in terms of BER performance but also in terms of DCs with state-of-the-art high-speed turbo decoders.