文档下载 文档下载导航
设为首页 | 加入收藏
搜索 请输入内容:  
 导航当前位置: 文档下载 > 所有分类 > Some Explicit Formulae of NAF and its Left-to-Right Analogue
侵权投诉

Some Explicit Formulae of NAF and its Left-to-Right Analogue

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

n/2 n/2 +1 Thusk=0#[ 1¯1 k]=k=0n

2=2n.Thisimpliesthatthereare2nkdi erentrepresentationswith 1¯1 kpattern.Asthetotalnumberofintegerswith

n-bitis2nandProperty1,theassertionisproved. Lemma2(Classi cationLemma).B(n)canbedividedintothefollowingthreecases;

–Case(n)with#[CaseI(n)]=2n 1,

–Case(n)with#[CaseIIB(n)]=2n 2,

–CaseB(n)with#[Case(n)]=2n 2.

Proof.FromProperty1andLemma1,

#[CaseIB(n)]= n#[CaseB(n)]=

1 n 1 n ,=02k+1#[CaseB(n)]= kn 1 1n 1 k=02k+11 n k=0n2k =2n 1,k=0 n 1=2n 2,2k(ifniseven),(otherwise)=2n 2.

Lemma3(ExtensionLemma).B(n)canbeconstructedfromB(n 1)ac-cordingtothefollowingrules;

–Case(n)= {(βn=0) (βn 1,...,β0)|(βn 1,...,β0)∈B(n 1)},–Case(n)= (βn,βn 1)=(1,¯1) (βn 2,...,β0)|(βn 2,...,β0)∈B(n 2),–CaseB(n)=(βn ,βn 1)=(1,0) (βn 2,...,β0)|(1,βn 2,...,β0)∈{Case(n 1)∪CaseB(n 1)}.

Proof.FromProperty1andLemma1,2,wecanseethattheassertionistrue.Inthethirdcase,inordertoconstructCaseB(n)themostbit1ofthestringssampledfrom{CaseIIB(n 1)∪CaseIIIB(n 1)}ischangedtoβn 1=0andβn=1isconcatenated.RefertoFig.2.

Lemma4(CaseII-Classi cationLemma). n 1#Case(n)with#(themostconsecutivenonzerobits)=even=2+κn, n 2#Case(n)with#(themostconsecutivenonzerobits)=odd=2 κn,whereκn=2ifnisoddandκn=1ifniseven.Especially, #Case(n)with#(themostconsecutivenonzerobits)=2=2n 3.

5 Here,x ydenotesconcatenationbetweentwobitstringsxandy.Proof.StraightforwardbecauseofProperty1andLemma1.

上一页第5页

你可能喜欢

热门文档

相关文档

  • Amalgamating NAF and NAI

    Some Explicit Formulae o... 暂无评价 14页 免费 Evolution of Electronic ... 暂无评价 9页 免费 NAF算法的改进 暂无评价 4页 2.00元 NaF 暂无评价 2页...

  • Amalgamating NAF and NAI

    Some Explicit Formulae o... 暂无评价 14页 免费 Evolution of Electronic ... 暂无评价 9页 免费 NAF算法的改进 暂无评价 4页 2.00元 NaF 暂无评价 2页...

站点地图 | 文档上传 | 侵权投诉 | 手机版
本站所有资源均来自互联网,本站只负责收集和整理,均不承担任何法律责任,如有侵权等其它行为请联系我们.
文档下载 Copyright 2013 doc.guandang.net All Rights Reserved.  -  email