# Automata and Arithmetics in Canonical Number Systems
## 4 Estimation of the Number of States of an Addition Automaton
### Example of the Computation in the Number System \(\left(x^{2}+x+2,\{0,1\}\right)\)  
Let \(x^{2}+x+2\) be the base polynomial and \(\{0,1\}\) is the digit set. By Theorem 4.2, we know that this is a CNS. Let \(\gamma_{1}=110101\) and \(\gamma_{2}=101111\) be 6-bit long binary 'numbers' in the above CNS, and let \(\gamma=\gamma_{1}+\gamma_{2}\). The calculation of the digits of \(\gamma\) is similar to the usual binary arithmetic, but the carry propagation is a bit more advanced. In the classical binary system, we use the fact that \(1(-2)_{2}=1\cdot 2^{1}+(-2)\cdot 2^{0}=0\) (i.e., we use the \(x-2\) polynomial as the base). In the present system, according to this observation, \(1\,1\,2_{x^{2}+x+2}=0\). The addition process works as follows:1. Initialization The two numbers, \(\gamma_{1}\) and \(\gamma_{2}\), are digit-wise added without any further computations. The result is \(\gamma^{\prime}=211212\). 2. Reduction Starting from the least significant digit on the right, we reduce the augmented digits, which are not in the digit set \(\{0,1\}\). In this CNS, this is the only value 2. However, as in the classical binary systems, we have to take into account the possible carries, arriving from lower digits. How can we calculate this carry? In the case of the last digit, we assume that there is no carry; more precisely, the value of the carry is 0. To eliminate the last digit 2, we should subtract \(1\,1\,2\). The result is \((-1)(-1)\,0\), which is split into two parts: the calculated digit at the given position and the carry for the next position. In our case, the digit is 0, while the carry is \((-1)(-1)\). For the next digit, we add the carry arriving from the right to the value given at the position: \(1+(-1)(-1)=(-1)0\). Since 0 is a valid digit, we do not need any further operation at this position. The carry for the next position is \((-1)\). The next augmented digit is 2. Adding the carry, we obtain \(2+(-1)=1\), so the next calculated digit is 1, and the carry is 0. We continue the iteration until \(\gamma^{\prime}\) is completely processed and the carry becomes 0. The algorithm described above can be visualized by Table 2.  
Based on the algorithm for calculating the sum, we may construct the corresponding addition automaton. The states of the automaton are the possible carries during the computation. We start from the carry 0 and calculate the transition according to the possible inputs (augmented digit). The value of the transition is a pair \((\mathfrak{c},d)\), where \(\mathfrak{c}\) is the next carry and \(d\) is the output digit. The new carries are added to the automaton, and until we have unexplained transitions, we continue the construction of the automaton. The process generates the transition function of the automaton, as illustrated in Table 3.  
The values of the cells in the table contain pairs: the next state (carry) and the output (digit), according to the present state (carry) and the input (augmented digit). If a new unexplored carry appears in the transition value, then a new column is added to the table. We continue to fill out the table until no new carry appears. By Theorem 5, the algorithm will terminate \begin{table}
\begin{tabular}{c c c c c c c c c c c} \hline \hline \(\gamma^{\prime}\) & & & & & 2 & 1 & 1 & 2 & 1 & 2 \\ \hline \(\mathfrak{c}\) & 0 & 1 & 10 & \(-1{-}1\) & 0 & 0 & 0 & \(-1\) & \(-1{-}1\) & 0 \\ \hline \(\mathfrak{c}+\gamma^{\prime}\) & & 1 & 10 & \(-1{-}1\) & 2 & 1 & 1 & 1 & \(-10\) & 2 \\ \hline mod & & 0 & 0 & \(+(112)\) & \(-(112)\) & 0 & 0 & 0 & 0 & \(-(112)\) \\ \hline \(\gamma^{\prime\prime}\) & 0 & 1 & 10 & 101 & \(-1{-}10\) & 1 & 1 & 1 & \(-10\) & \(-1{-}10\) \\ \hline \(\gamma\) & & 1 & 0 & 1 & 0 & 1 & 1 & 1 & 0 & 0 \\ \hline \hline \end{tabular}
\end{table} 
Table 2: Computation in the binary number system.