Computer Science – Discrete Mathematics
Scientific paper
2008-03-19
Computer Science
Discrete Mathematics
Scientific paper
For applications to cryptography, it is important to represent numbers with a small number of non-zero digits (Hamming weight) or with small absolute sum of digits. The problem of finding representations with minimal weight has been solved for integer bases, e.g. by the non-adjacent form in base~2. In this paper, we consider numeration systems with respect to real bases $\beta$ which are Pisot numbers and prove that the expansions with minimal absolute sum of digits are recognizable by finite automata. When $\beta$ is the Golden Ratio, the Tribonacci number or the smallest Pisot number, we determine expansions with minimal number of digits $\pm1$ and give explicitely the finite automata recognizing all these expansions. The average weight is lower than for the non-adjacent form.
Frougny Christiane
Steiner Wolfgang
No associations
LandOfFree
Minimal weight expansions in Pisot bases does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Minimal weight expansions in Pisot bases, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Minimal weight expansions in Pisot bases will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-323598