• 検索結果がありません。

SD 数剰余加算を用いた剰余除算回路の構成

N/A
N/A
Info
ダウンロード
Protected

Academic year: 2021

シェア "SD 数剰余加算を用いた剰余除算回路の構成"

Copied!
6
0
0

読み込み中.... (全文を見る)

今ダウンロードする ( 6 ページ )

全文

(1)2007-SLDM-128 (4). IPSJ SIG Technical Reports. '. 2007/1/17. sd. 376-3515 S$Smffi|^*^#0T 1-5-1. E-mail: f{jia,wei}@ja4.cs.gunma-u.ac.jp. ,. sd. 2mKM&»&®&\zit'<ftm\zte «),. -9- K. Montgomery »JC. SD », fij^^^, %mm, m&&W, VHDL,Montgomery. Design of Residue Dividers Using Signed-Digit Number Residue Addition. Peng JIAf and Shugang WEIf. f Department of Computer Science Gunma Univ.. Tenjinl-5-1, Kiryu-shi,376-3515 Japan. E-mail: t{jia,wei}@ja4.cs.gunma-u.ac.jp. Abstract cussed.. In this paper, residue division algorithms using the binary adders and signed-digit (SD) adders are dis. We present first a simple redisue division algorithm using a residue addition and a addition.. When the. division algorithm is implemented by the binary number arithmetic, the carry propagation may limit the speed of the residue divider. We also implement the algorithm by using radix-two signed-digit number arithmetic, and the design. simulation results show that the speed of the residue division was improved. Moreover, in order to decrease the clock cycles of the operations, a residue division algorithm based on Montgomery method is also discussed.. Key words. signed-digit number, residue number system, modular addition, residue division, VHDL,Montgomery -19-.

(2) = A mod m. (2). (RNS). 0, L. J. \. f TTL. ■. | TTl. \. x = <A-)m = |X|ra - s^n(|^|ro) x m. /. (5). m) = /I. I t f VlJUb. w iv J. fv. |"*J. ^-^ N. « O/ 0. o. TO. =. flfljl: p = 5,TO = 17CD«h#,. f,. Ar 4- tos. =. l(mod. m)> T/^^b. ^, Ar = l(mod m) t^^L^O^VD [8]o r,5 (DfilH Euclidean7;i/rfU7TA^«i:oTAt<i6^>tl>. r\$A0M. i^nlf^h^ip. H^2n+5 [bjo. -^m = {~ 15, —14, • • • ,0, • • •, 14,15}. JKA-C. -6 -^ vj /7 fE tv_ cK V \. ^ (4) ^J;oT(29>17 = -5\ZtiK), it (5). ioT (29>17 =-5 - (-1)17 = 12 tC^So. >pj. 14K 1: a t b SrS^tTSo (a) abs((a)J ZV-1. (b)(a±b)m = ((a)m±{b)m) T,. «J*»DC|II»*ffl^T*ST*.. Signed^. (d) {_a)m s _ {a)m. Digit(SD) R«»1)^^R^[7| **. (e) (a)m ^ (6>m ^ (A;a)Tn ^ (*t)B. 3. fc».. Montgomery ffi{r*cJ<*J*BS3¥7;PJlJ. 3.1. 2. __. (1). I. x «flJ^I^#©iSt?*-&. I. -20-. /i. /g\. 0 ^ tt, v < m I. = 77. ^7").

(3) A = |A + v|m Sr a: E Xtiu.v &0 < u,v < m. U XAttBTF cfc 5 £. Input : u,v : 0 < u,v < m. Output : x = \u/v\m x:=0;. while A — u =|= 0 do a; :=x 4-1;. end do return. □. x. -x = -(xp_i. 0)2: u = ll,i; = 7,m = 15 i U. (9) p = 5 \Z. X,. i3*SD$kT:%Tt,. (1,-1,1,0,1)5^. (0,1,1,0,1)5^. (1,-1,1,1,-1)51? ,. 1 © £ 51,. SD. madd tmw. ^StefgINVERT. \t A - u = 0 tc (10 - a). 2x. (10 - b) 3.2. Z = Cp.tfP + zp-tf*-1 4- zp-22p~2 4- • • • 4- z0. = zp2p 4- Zo. (10-c) zp. ••• + 20 X. Xn—I. 4- xp_22p-2 H- ... 4- so. (8) -21-. =. cp_i. P-1 4-.

(4) (SDA). «j« SD &i&im (MSDD). SDA. /X G {-1,0,1}. HI 3. 3RI& SD ^CiJP^§§ (MSDA) 5.. (SDFA). (11). n feo. \Z\m =. lumC-. SD. C_i = \Cp-x2P\m = -Cp-i X. [I. (12). -^ m g {-1,0,1} ,. 2i. 30%. 4.. 3.3. Montgomery m @S§^\. -22-. n My h.

(5) , MM 2n .. ,. Montgomery. v CO Montgomery. Montgomery. 4.1. Montgomery SIS [9]. (13). X = \U*V. Input : v, m : 0 < v < m ,. Montgomery. Output : Z = Iv-^l™. :5fc)£l|3ns. £il2(Montgoinery $"]&*»):. 0. I/ = m,Vr = v,ii=0,5 = l;. < rc,y < m. for. 2 = 0 to n — 1. if. Montgomery. do. (U even) then U = 17/2; 5 = 25;. e/«et7 (V even) t/ien V = V/2; i2 = 2. (14). e/aet/ (f/ > F) t/ien U = (U - V)/2;. \Zfft)tlZo. Montgomery. else V = (V-U)/2; Input : x,2/,m : 0 < x,y < m,. Output : z = \xy2-n\m. Z= \m-R\m]. A = 0;. end. for i = 0 to (n — 1). do. do. Montgomery IS. A = A + x; x. 2/;. Montgomery. i/. t/ien A = A + m;. ^ 1. (|A|2=(=0). A = A/2;. — lr>ni u*\v-LZ. ^ = A;. end do. D h^ifOjRffttnUIffa.. y|TOfc*.. |2"n|m £ |2n|. 2. =. \x *. Montgomery flJ^^»*5* z t. o~. Xi * V. -1. «3: u = 11,v = 7,m = 24 - 1 t°T%£,. gomery M7 ;i/ 3* U XACJ: 0, 13 t#S,. (16). Mont. |7-124|24_1. =. Montgomery *. |11 x 13 x 2"4|24_1. =. 22n t <D Montgomery 4. 2. Montgomery i£8fc. 7;UrfL)XA3i4K:«fc?K. Montgomery ^StST. *.. Montgomery m$k<Dfem. tl,. Montgomery. gomery Multiplier TS^o. 3:8 3(Montgomery i85^):. «. tt. Montgomery Inverse <h Mont. Montgomery Inverse T. C^, V, 5, i?*fflViTt;O Montgomery 2S»C**«). Montgomery jMifc^^^ct "5 £ (15). .. /,. Montgomery. w £ (D Montgomery S S #* ff "5 0. Montgomery j^ic^^^^fcfi6> ^nTt^ [12]e. v im(D. kt),. £ 2n)HI. gcd{v,m). k{n. <. k. [7]o o. = -23-. Euclid's. Montgomery.

(6) Montgomery &&ffl UfctJ&R^gg. [6].to,. 5.. metic Hardware Algorithm Using a Signed-Digit Number Representation", IEICE Trans.INF. & SYST., Vol.E83-D, No.12, pp. 2056-2064, Dec.. tf. 2000.. t. [8]. [9]. D.E.Kunth,. "The Art of Computing Program. ming, Volume 2,Seminumerical Algorithm"s,third ed.Reading Mass.: AddisonWseley, 1998.. P.L. Montgomery, "Modular multiplication with. out trial division,"Mathematics of Computation, vol.44,no.l70,pp.519-521,1985.. .. [10]. 8. Applications,"IEEETrans.Comput,vol.44,no.8,pp.. SD. 1064-1065,1995.. [11]. [12]. Montgomery &(£. *.. [2]. [3]. [4]. N.S.Szabo and R.I.Tanaka , "Residue Arithmetic and Its Applications to Computer Technolorgy", New York: McGraw-Hill, 1967. M.A.Sonderstrand, W.K.Jendins,G.A.Junllien, and F.J.Taylor, "Residue Number System Arith metic: Modern Applications in Digital Signal Porcessing ," IEEE Press,New York,1986. D.Mandelbam : "Error correction in residue arith metic," IEEE Trans. Comput.,Vol.C-21,pp.538545,June 1972. F.Barsi and P.Maestrini : "Error correcting prop erties of redundant residue number systems," IEEE Trans. Comput.,Vol.C-22,pp.307-315,March 1973. [5]. D.P.Agrawal and T.R.N.Rao, "Modulo (2n -I- 1) arithmetic logic," IEEE J. Electronic Circuits and Systems,Vol.C-27,pp.l86-188,Nov. 1978.. [6]. Marcelo E.Kaihara ,Naofumi Takagi, "A Hardware Algorithm for Modular Multipli cation/Division" IEEE Trans. Comput., Vol54,NO.l,Jan 2005. [7]. E.Savas,C.K.Koc, "The Montgomery modular inverse-Revisited," IEEE Trans.Comput.49 (7) (2000)763-766. S.N. Parikh and D.W.Matula, "A redundant bi nary Euclidean GCD algorithm,"Proc. 10th IEEE Symp.Computer Arithmetic,pp.220-225.1991. Euclid's. [1]. B.S. Kaliski Jr, "The Montgomery Inverse and Its. S.Wei and K.Shimizu, "A Novel Residue Arith-. -24-.

(7)

参照

今ダウンロードする ( PDF - 6 ページ - 351.93 KB )

関連したドキュメント

New York Journal of Mathematics New York J. Math.

To complete the proof of the lemma we need to obtain a similar estimate for the second integral on the RHS of (2.33).. Hence we need to concern ourselves with the second integral on

New York Journal of Mathematics New York J. Math.

In view of the result by Amann and Kennard [AmK14, Theorem A] it suffices to show that the elliptic genus vanishes, when the torus fixed point set consists of two isolated fixed

New York Journal of Mathematics New York J. Math.

We develop three concepts as applications of Theorem 1.1, where the dual objects pre- sented here give respectively a notion of unoriented Kantorovich duality, a notion of

New York Journal of Mathematics New York J. Math.

The (strong) slope conjecture relates the degree of the col- ored Jones polynomial of a knot to certain essential surfaces in the knot complement.. We verify the slope conjecture

New York Journal of Mathematics New York J. Math.

We construct some examples of special Lagrangian subman- ifolds and Lagrangian self-similar solutions in almost Calabi–Yau cones over toric Sasaki manifolds.. Toric Sasaki

New York Journal of Mathematics New York J. Math.

In this section, we show that, if G is a shrinkable pasting scheme admissible in M (Definition 2.16) and M is nice enough (Definition 4.9), then the model category structure on Prop

#A1 INTEGERS 14 (2014) UPPER AND LOWER BOUNDS ON B

Erd˝ os, Some problems and results on combinatorial number theory, Graph theory and its applications, Ann.. New

J2 =−Id., g(J X, J Y) =−g(X, Y) (1.1) for any vector fieldsX, Y of the tangent vector spaceT(M).Then F(X, Y) =g(J X, Y) =g(X, J Y) =F(X, Y) and F(J X, J Y) =−F(X, Y)

Algebraic curvature tensor satisfying the condition of type (1.2) If ∇J ̸= 0, the anti-K¨ ahler condition (1.2) does not hold.. Yet, for any almost anti-Hermitian manifold there