文档下载 文档下载导航
设为首页 | 加入收藏
搜索 请输入内容:  
 导航当前位置: 文档下载 > 所有分类 > 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

aBinary

¯10000100001000110001¯20001000010001100010¯¯¯30010100101001010011¯40010000100011000100¯¯50010100101011110101

6010¯10010¯10010¯100110

70100¯10100¯10100¯10111

801000010001¯10001000

901001010011¯101¯11001¯¯100101001010111101010¯¯¯¯¯111010101101111011011¯¯¯121010010100101001100¯¯¯¯¯131010110011101111101¯¯¯141001010010100101110

151000¯11000¯11000¯11111

3Lemmas

Inthissection,wepreparesomelemmasrequiredtoproveourtheorems.

3.1SomePropertiesofBoothEncoding

Property1.Duetothede nitionofBoothencoding,thenumberofHammingweightofBooth(a)isalwayseven,iftheoriginalintegeraispositive.

Let 1¯1 kbeapatternofnonzerobitsinBoothencodingsuchthat

¯1(k-times)withoutconsideringzerobitsbetween1and¯1.1,1,¯1,1,...,1,¯

kk¯¯Let#[ 11 ]bethetotalnumberofstringswith 11 pattern.Forexam-

ple,inB(3)\{0},allelementsexcept1¯11¯1havethesamepattern 1¯1 2.Thus#[ 1¯1 2]=6and#[ 1¯1 4]=1.

Lemma1(PatternLemma).B(n)containsallpossiblerepresentationswith1 kpatternfor0≤k≤ n/2 . 1¯

Proof.For1≤k≤ n/2 ,

n+1,#[ 1¯1 0]=0 n+1,#[ 1¯1 k]=2k n+1,...#[ 1¯1 1]=2 n+1....#[ 1¯1 n/2 ]=2 n/2 k21

4

上一页第4页

你可能喜欢

热门文档

相关文档

  • 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