• KSII Transactions on Internet and Information Systems
    Monthly Online Journal (eISSN: 1976-7277)

w-Bit Shifting Non-Adjacent Form Conversion

Vol. 12, No. 7, July 30, 2018
10.3837/tiis.2018.07.025 , Download Paper (Free):


As a unique form of signed-digit representation, non-adjacent form (NAF) minimizes Hamming weight by removing a stream of non-zero bits from the binary representation of positive integer. Thanks to this strong point, NAF has been used in various applications such as cryptography, packet filtering and so on. In this paper, to improve the NAF conversion speed of the NAFw algorithm, we propose a new NAF conversion algorithm, called w-bit Shifting Non-Adjacent Form(SNAFw), where w is width of scanning window. By skipping some unnecessary bit comparisons, the proposed algorithm improves the NAF conversion speed of the NAFw algorithm. To verify the excellence of the SNAFw algorithm, the NAFw algorithm and the SNAFw algorithm are implemented in the 8-bit microprocessor ATmega128. By measuring CPU cycle counter for the NAF conversion under various input patterns, we show that the SNAF2 algorithm not only increases the NAF conversion speed by 24% on average but also reduces deviation in the NAF conversion time for each input pattern by 36%, compared to the NAF2 algorithm. In addition, we show that SNAFw algorithm is always faster than NAFw algorithm, regardless of the size of w.


Show / Hide Statistics

Statistics (Cumulative Counts from December 1st, 2015)
Multiple requests among the same browser session are counted as one view.
If you mouse over a chart, the values of data points will be shown.

Cite this article

[IEEE Style]
D. Hwang and Y. Choi, "w-Bit Shifting Non-Adjacent Form Conversion," KSII Transactions on Internet and Information Systems, vol. 12, no. 7, pp. 3455-3474, 2018. DOI: 10.3837/tiis.2018.07.025 .

[ACM Style]
Doo-Hee Hwang and Yoon-Ho Choi. 2018. w-Bit Shifting Non-Adjacent Form Conversion. KSII Transactions on Internet and Information Systems, 12, 7, (2018), 3455-3474. DOI: 10.3837/tiis.2018.07.025 .

[BibTeX Style]
@article{tiis:21826, title="w-Bit Shifting Non-Adjacent Form Conversion", author="Doo-Hee Hwang and Yoon-Ho Choi and ", journal="KSII Transactions on Internet and Information Systems", DOI={10.3837/tiis.2018.07.025 }, volume={12}, number={7}, year="2018", month={July}, pages={3455-3474}}