// ************************************************************************** // // // // eses eses // // eses eses // // eses eseses esesese eses Embedded Systems Group // // ese ese ese ese ese // // ese eseseses eseseses ese Department of Computer Science // // eses eses ese eses // // eses eseses eseseses eses University of Kaiserslautern // // eses eses // // // // ************************************************************************** // // The module below decodes a given residue number x_enc[i] with respect to // // the moduli prime[i] that must be relatively prime numbers. The decoding // // is mainly based on the computation of multiplicative inverse elements for // // the prime[i] that are stored in the local array inverse[i]. As a result, // // the algorithm computes a number x_dec such that the following Chinese // // Remaindering puzzle is solved where N = numPrim: // // // // x_dec % prime[0] = x_enc[0] // // : : = : // // x_dec % prime[N] = x_enc[N] // // // // ************************************************************************** // macro numPrim = 4; macro Product(p,i) = (i==0 ? p[i] : p[i]*Product(p,i-1)); module DecodeRNS([4]nat ?prime,?x_enc,int x_dec,event rdy) { nat ProdPrimes; [4]int inverse; // compute the product of the given relatively prime numbers ProdPrimes = Product(prime,numPrim-1); // Compute multiplicative inverse elements inverse[i] for ProdPrimes/prime[i] // modulo prime[i], i.e. numbers inverse[i] such that the following holds: // (inverse[i] * (ProdPrimes/prime[i])) % prime[i] = 1 // The computation of the multiplicative inverse elements is done by the // extended Euclidean algorithm that makes use of Bézout's Lemma. for(i=0..numPrim-1) do || { int m,n,q,s,t,u,v; m = ProdPrimes/prime[i]; n = prime[i]; u = 1; v = 0; s = 0; t = 1; while(n!=0) { q = m / n; next(m) = n; next(n) = m - q * n; next(u) = s; next(v) = t; next(s) = u - q * s; next(t) = v - q * t; pause; } inverse[i] = u; } // now we can easily decode any given number x given in RNS representation x_dec = (sum(i=0..numPrim-1) (x_enc[i] * inverse[i] * ProdPrimes/prime[i])) % ProdPrimes; emit(rdy); } drivenby { prime[0] = 8; x_enc[0] = 5; prime[1] = 7; x_enc[1] = 3; prime[2] = 5; x_enc[2] = 4; prime[3] = 3; x_enc[3] = 2; await(rdy); } drivenby { prime[0] = 25; x_enc[0] = 20; prime[1] = 27; x_enc[1] = 15; prime[2] = 23; x_enc[2] = 16; prime[3] = 22; x_enc[3] = 21; await(rdy); }