Clemens Heuberger: Symmetric Signed Digit Expansions: Minimality, Algorithms, Quantitative Analysis, and Extensions

This is a joint work with Peter Grabner and Helmut Prodinger.

We study redundant $q$-ary digit expansions

\varepsilon_j q^j\end{displaymath}

with digits $-q/2\le \varepsilon_j \le q/2$ and a special rule to make representations of integers unique (for even $q$). It turns out that this expansion minimizes the costs $\sum_{j=0}^l \vert\eta_j\vert$ over all expansions $n=\sum_{j}\eta_j q^j$ with arbitrary integer digits $\eta_j$. The motivation to consider such minimal expansions comes from applications in cryptography and coding theory.

We give an algorithm to compute the $j$th digit of this ``symmetric signed digit expansion'' from the knowledge of the $j+1$ first digits of the ``standard'' $q$-ary expansion, i. e., the unique expansion with digits $0$, ..., $q-1$.

Additionally, we give an explicit formula for the $j$th digit of a minimal expansion without having to calculate the other digits. This enables us to calculate the number of occurrences of a given sub-block among the expansions of the integers up to some $N$ asymptotically.

We study the average number of carry propagations in von Neumann's addition method. Contrary to the standard case investigated by Knuth, there are positive and negative carries, which makes the situation more delicate.

Finally we deal with the question whether such results can be generalized to other number systems, for instance canonical number systems in an algebraic number field or number systems defined by recurring sequences.

Back to the Index

Please send comments and corrections to Thomas Klausner.