Sonia Cafieri, Jon Lee, et al.
Journal of Global Optimization
The string replacement (SR) method was recently proposed as a method for exponentiation ae in a group G. The canonical k-SR method operates by replacing a run of i ones in a binary exponent, O < i ≤ k, with i - 1 zeroes followed by the single digit b = 2i - 1. After recoding, it was shown in [5] that the expected weight of e tends to n/4 for n-bit exponents. In this paper we show that the canonical k-SR recoding process can be described as a regular language and then use generating functions to derive the exact probability distribution of recoded exponent weights. We also show that the canonical 2-SR recoding produces weight distributions very similar to (optimal) signed-digit recodings, but no group inversions are required.
Sonia Cafieri, Jon Lee, et al.
Journal of Global Optimization
Mario Blaum, John L. Fan, et al.
IEEE International Symposium on Information Theory - Proceedings
B.S. Bollepalli, Scott D. Hector, et al.
Microlithography 1997
Jeong-Ik Lee, G. Klarner, et al.
Proceedings of SPIE - The International Society for Optical Engineering