一种二进制域非相邻表示型的生成算法

A generating algorithm of non-adjacent form for binary domain

为了节约存储空间,通过分析非相邻表示型的定义与性质,提出一种二进制域基于字存储的非相邻表示型的多位生成算法。该算法将数字生成非相邻表示型的同时重点记录非零值及其在传统序列中所在位置,且将一个或多个非零值及其位置信息存储在一个存储字中,减少了存储字。结果表明,当窗口宽度为3,标量k的二进制长度为283时,存储k的非相邻表示型平均可节省75%左右的存储单元,访问内存71次。窗口宽度越大,需要的存储单元个数越少,访问内存的次数也越少。

This paper proposes a multi-bit generating algorithm of binary field non-adjacent form based on word storage to save storage space by analyzing the definition and properties of non-adjacent forms.This algorithm mainly records the non-zero values and their positions in traditional sequence along with the generating non-adjacent form of the numeral,and stores one or more non-zero values and their position information in a storage word to reduce the number of storage words required.The results show that with the window width by 3,the binary length of scalar k by 283,the storage unit of the non-adjacent form k can be saved about average 75%with accessing memory by 71 times.As the window width increases,the required number of storage units decreases,and the number of memory accesse decreases either.