w-Bit Shifting Non-Adjacent Form Conversion = w-Bit Shifting Non-Adjacent Form Conversion

다국어 초록 (Multilingual Abstract)

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 NAF_W algorithm, we propose a new NAF conversion algorithm, called W-bit Shifting Non-Adjacent Form(SNAF_W), where W is width of scanning window. By skipping some unnecessary bit comparisons, the proposed algorithm improves the NAF conversion speed of the NAF_W algorithm. To verify the excellence of the SNAF_W algorithm, the NAF_W algorithm and the SNAF_W 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 SNAF₂ 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 NAF₂ algorithm. In addition, we show that SNAF_W algorithm is always faster than NAF_W algorithm, regardless of the size of W.