Abstract. Non-Adjacent Form (NAF) is a canonical form of signed binary representation of integers. We present some explicit formulae of NAF and its left-to-right analogue (FAN) for randomly chosen n-bit integers. Interestingly, we prove that the zero-run l
–Booth(a),Naf(a),andFan(a)denotetheBoothencoding,NAF,andFANrepresentationofthearespectively. nintegeri Booth(a):=i2withβi∈{ 1,0,1}, ni=0βi Naf(a):= i=0νi2withνi∈{ 1,0,1},n Fan(a)=i=0φi2iwithφi∈{ 1,0,1}.–B(n):={Booth(a)|0≤a≤2n 1}. CaseB(n):={Booth(a)withβn=0|0≤a≤2n 1}.
1)|0≤a≤2n 1}. Case(n):={Booth(a)with(βn,βn 1)=(1,¯
Case(n):={Booth(a)with(βn,βn 1)=(1,0)|0≤a≤2n 1}.–N(n):={Naf(a)|0≤a≤2n 1}.
–F(n):={Fan(a)|0≤a≤2n 1}.
–κn=2ifnisoddandκn=1ifniseven.
–εnisthenegligiblefunctioninn,namelyforeveryconstantc≥0thereexistsanintegerncsuchthat|εn|≤1/ncforalln≥nc.
2.2BoothEncoding,NAFandFAN
TheBoothencoding[Boo51]ofanintegerisde nedasfollows:
De nition1(BoothEncoding[OSS+04]).Then-bitBoothencodingisann-bitsignedbinaryrepresentationthatsatis esthefollowingtwoconditions:
1.Signsofadjacentnonzerobits(withoutconsideringzerobits)areopposite.
2.Themostnonzerobitandtheleastnonzerobitare1and¯1,respectively,unlessallbitsarezero.
In[OSS+04],theyshowedasimpleconversionmethodfromann-bitbinarystringto(n+1)-bitBoothencoding.Givenanintegera,theBoothencodingofaisobtainedby
Booth(a)=2a a,
where standsforabitwisesubtraction.
Thenon-adjacentform(NAF)alsorepresentsanintegerinsignedform.Sincethereisnosuccessivenonzerobitsintherepresentation,NAFisastandardtech-niqueforcomputingexponentiations[IEEE].Accordingto[HKP+04,OSS+04],NAFcanbeinterpretedasacombinationoftheBoothencodingandaright-to-leftslidingwindowmethodwithwidth-2.Forexample,foraninteger13,wehaveBooth(13)=10¯11¯1.ThenwedivideBooth(13)(asastring)intowidth-2windowsfromrighttoleft:01,0¯1,1¯1(theleftmost0waspadded),andconvert¯¯¯101.11to01and11to01,ifexist.ThuswehaveNaf(13)=10¯
FANwasintroducedasaleft-to-rightanalogueofNAF[JY00].Infact,FANcanbealsointerpretedasacombinationoftheBoothencodingandaleft-to-rightslidingwindowmethodwithwidth-2.Forexample,again,wedividetheBoothencodingBooth(13)=10¯11¯1intowidth-2windowsfromlefttoright:10,¯11,¯10(therightmost0waspadded).Then,similarlytoNAF,convert1¯1to01and¯11to0¯1,ifexist.ThuswehaveFan(13)=100¯1¯1.NotethatFANcanhavesuccessivenonzerobitsunlikeNAF.
Table1showsNAF,FAN,Booth,andnon-signedbinaryrepresentationsofsomepositiveintegers.
3
Some Explicit Formulae o... 暂无评价 14页 免费 Evolution of Electronic ... 暂无评价 9页 免费 NAF算法的改进 暂无评价 4页 2.00元 NaF 暂无评价 2页...
Some Explicit Formulae o... 暂无评价 14页 免费 Evolution of Electronic ... 暂无评价 9页 免费 NAF算法的改进 暂无评价 4页 2.00元 NaF 暂无评价 2页...
热门文档