01.1 Number systems

fds

Representation

• A bit is the most basic unit of information
• It can have two possible states: on (1) or off (0)
• Usually grouped into bigger data structures (bytes)

In mathematics we call a bigger data structures as a tuple

• ordered structure of $n$ elements, each element being a digit

In digital systems, we have ordered tuples to represent numbers

Non-negative integers

• Digit-vector (or string) representing the integer $x$ is denoted by $x=(X_{n-1},X_{n-2},\dots ,X_1,X_0)$
• The least significant digit (or low-order digit): $X_0$
• The most significant digit (or high-order digit): $X_{n-1}$

(Non) Redundant Number Systems

A number system is nonredundant if

• each digit-vector represents a different integer A number system is redundant if
• The are numbers represented in multiple ways

Weighted Number Systems

We have the digits associated to a weight corresponding to its position in the number: $x={\sum }_{i=0}^{n-1}{X}_i\cdot W_i$

When those weights $W_i$ are of the form $\{\begin{array}{l}{W}_0=1\\ W_i=W_{i-1}\cdot R_{i-1},1\le i\le n-1\end{array}$ Which is a radix number system

Fixed and Mixed Radix Number Systems

All the elements of the radix vectors have the same value $r$ (the radix) → a fixed-radix number

Fixed Radix	Mixed Radix
Decimal	Time ($HH:MM:SS$)
Binary	Imperial units
Octal	Bits → Bytes → kb
Hex

Conventional Number Systems

A system with

• a fixed positive radix $r$
• a canonical set of digit values
  • A radix-$r$ conventional number system

Binary/Octal/Hex to/from Decimal

We can convert binary to decimal $10011_2=1\cdot 2^4+0\cdot 2^3+0\cdot 2^2+1\cdot 2^1+1\cdot 2^0=19$

For decimal to binary, you divide by the base, the remainder is the bit value

$5/2=2\text{ rem }1⟹2/2=1\text{ rem }0⟹1/2=0\text{ rem }1⟹5_{10}=101_2$

Signed Integers

The most significant bit defines whether the number is postive or negative

Postive	Negative
0	1

We can have symmetrical number system, where the positive and negative are only differentiated by the sign

Left Arithmetic Shift

We discard the second most significant bit (to keep the sign), and shift the rest

Right Arithmetic Shift

We shift to the right (keeping the sign in the same spot), padding with 0s

True and Complement (TC)

A signed integer is represented by a positive integer $x_R$ $x_R=x\mathrm{mod}C$

For $|x|<C$, we have $x_R=\{\begin{array}{ll}x& \text{if }x\ge 0\\ C-|x|=C+x& \text{if }x<0\end{array}$

Range Extension

If we want to represent a signed number on more bits than it currently has, we move the sign to the first and pad the rest with zeros/ones (if negative)

Example

$1001$ ($-7$) → to 8 bits We move the sign, and pad with ones (negative) → $11111001$

Left Arithmetic Shift

We discard the second most significant bit and shift the rest to the left (pad the end with zeros)

Right Arithmetic Shift

We shift to the right, copying the sign to the new most significant bit, we lost the least significant bit

Different Codes

Hamming weight and distance

Distance: How much the numbers differ from each other, bitwise (so the number of different bits)

Weight: The amount of ones ($1$) in a number

Gray’s code

When you increment the number, the hamming distance is 1