Synthesis of Arithmetic Circuits: FPGA, ASIC and Embedded Systems

3.1 NATURAL NUMBERS

3.1.1 Weighted Systems

Any natural number (nonnegative integer) can be represented, in a unique way, in the form of a sum of powers Bⁱ of some natural number B greater than 1, each of them multiplied by a natural number smaller than B. The following theorem defines the base-B numeration system.

Theorem 3.1 Given a natural number B greater than 1, any natural number x smaller than Bⁿ can be expressed in the form

where every coefficient x_i is a natural number smaller than B. Furthermore, there is only one possible vector (x_n−1 x_n−2 … x₀) representing x.

The following algorithm computes the coefficients x_i:

Algorithm 3.1

for i in 0..n − 1 loop x(i):=x mod B; x:=x/B; end loop;

Definitions 3.1

1. The most commonly used values of B are 10 (decimal system), 2 (binary system), 16 (hexadecimal system), and 8 (octal system). The coefficients x_i of the base-B representation of x are called the base-B digits of x. The binary digits are called bits. The hexadecimal digits 10, 11, 12, 13, 14, and 15 are usually replaced by letters: A, B, C, D, E, and F.
2. This type of representation is called positional as the weight Bⁱ associated with the digit x_i depends on i, that is, on the position of the digit within the vector (x_n−1 x_n−2 … x₀).
3. The base-B digits could in turn be encoded in another base. As an example, if B = 10 and the decimal digits are represented in the form of 4-bit ...