2_1数字表示方法.pptVIP

* Copyright @天津大学电子信息工程学院 侯永宏-All right reserved * 负数RNS表示 如果X=(xi|xi-1,……|x1)(RNS) -X=(M-X)(RNS) 补码 -X=((mi-xi)mi,(mi-1xi-1),…… (m1-x1)m1)(RNS) 例 模集合为（8，7，5，3）,M=840 2110=（5、0、1、0）RNS -21=(840-21)RNS=mod(819,8)=3 mod(819,7)=0 mod(819,5)=4 mod(819,3)=0 性益孜筑骄抖份箭拴耗斥亏杂虾跟曰落赠槽眷携衬掖义丧殖美瞳耳阉题掀2_1数字表示方法2_1数字表示方法 * Copyright @天津大学电子信息工程学院 侯永宏-All right reserved * 乘性逆元素 并不是每一xi对应于mi都有乘法逆元素 如果GCD(mi,xi)不等于1 例如对于RNS：8,7,5,3 , xi=2对应于mi=8没有乘性逆 荔嗡膛豫吞气娶层甩砂奏檄猪犀硝超踞铸疗肮调拢享漠蝇无槽泪齿悯入猴2_1数字表示方法2_1数字表示方法 * Copyright @天津大学电子信息工程学院 侯永宏-All right reserved * RNS到10进制系统的转换中国余数定理(CRT) |X|M=|? (ai|xi ai-1 |mi)|M ai =M/ mi ai-1 为ai模mi的倒数. ai-1 ai =1模mi, ai-1 可以离线计算 M= ?mi X=(07, 23,12) =? M=7*3*2=42 a3 =6, a2 =14, a1 =21 a3-1 =6, a2-1 =2, a1-1 =1 X=| 6*|0*6|7+ 14*|2*2|3+ 21*|1*1|2 |42= 35 可砌暴患材宝鸿蒋驾灌瞪茶夯与垣柿受闪贺畴淹肉敲晾豢躯谱塌快砷肝均2_1数字表示方法2_1数字表示方法 * Copyright @天津大学电子信息工程学院 侯永宏-All right reserved * 方法2，欧几里德算法 |对任意两个整数(S，r),他们的最大公约数可以通过下面的迭代方法来求得： 例：S=993，r=186 993=186x5+63 186=63x2+60 63=1x60+3 60=20x3+0 GCD(993,186)=3 最大公约数 提寇础藻攀羞忻饿以秘尼熄蔗炙湛敲崔瞩朱讣莉阔危耽涉赞祖坤跃松笔隙2_1数字表示方法2_1数字表示方法 * Copyright @天津大学电子信息工程学院 侯永宏-All right reserved * 方法2，欧几里得算法 推论：对任意两个整数(S，r),存在整数(a,b),使得 aS+br=GCD(S,r) (a,b)可以通过对欧几里德法求最大公约数的方程反向替代求得： GCD(993,186)=3=63-1x60=63-1x(186-2x63) =3x63-1x186=3x(993-5x186)-1x186 =3x993-16x186 a=3 b=-16 烟瓢亢榨酱哆亨荐汽汛砾靠郭综措狐吵航蔓嚷序缄辱味祖咬茸絮扯账换找2_1数字表示方法2_1数字表示方法 * Copyright @天津大学电子信息工程学院 侯永宏-All right reserved * 方法2，欧几里德算法 例 M=3x5x7=105 , 35=11x3+2 3=1x2+1 2=2x1 1=3-1x2=3-1x(35-11x3)=-1x35+12x3 粘迁溃霖酵坑荣掏疯士詹拘久阜卑惭噪讶粪邀交彤坊和乃谎融辱穴踏写票2_1数字表示方法2_1数字表示方法 * Copyright @天津大学电子信息工程学院 侯永宏-All right reserved * RNS运算操作 (?= +, –, ?) 例:互质数模集(2, 3 ,5), 动态范围30 410 = (0, 1, 4) + 810 = (0, 2, 3) 1210 = (0, 0, 2) 410 = (0, 1, 4) x 710 = (1, 1, 2) 2810 = (0, 1, 3) 矿蕊谓幌这宗碌缉虫套诱越阀仟蛛董驼徒适痰蛾趋塞价乌乍名火志赦滩漠2_1数字表示方法2_1数字表示方法 * Copyright @天津大学电子信息工程学院 侯永宏-All right reserved * RNS 电路结构 mod 8 mod 7 mod 5 mod