Logic - 7

COMP109 Lectures 2020-12-09

Number Systems

To indicate that a number of from a particular base system then use a subscript to denote this:

• $4268_{10}$
• $1100\ 0111_2$

In a positional system you should multiply each digit by its place value:

• $4268_{10}=4\times 10^3+2\times 10^2+6\times 10^1 +$$\ 8\times 10^0$

Convert Decimal to Binary

The rule is to repeatedly divide by 2, writing down the remainder from each stage from right to left.

Example

• $\frac{533}{2}=266r1$
• $\frac{266}{2}=133r0$
• $\frac{133}{2}=66r1$
• $\frac{66}{2}=33r0$
• $\frac{33}{2}=16r1$
• $\frac{16}{2}=8r0$
• $\frac{8}{2}=4r0$
• $\frac{4}{2}=2r0$
• $\frac{2}{2}=1r0$
• $\frac{1}{2}=0r1$

You will read this from bottom to top.

Therefore:

\[533_{10}=1000010101_2\]

Alternative Method

If you know the powers of 2, continually subtract largest power value from the number.

This is the method that I usually use. The other method is best suited to a programmatic implementation.

Binary Addition

This topic was covered in this lecture. View the video for the full example.

Half Adder

This adder can add one bit only.

$P$	$Q$	Carry	Sum
1	1	1	0
1	0	0	1
0	1	0	1
0	0	0	0

Full Adder

This adder can be linked together to add any number of bits together.

$P$	$Q$	$C_{\text{in}}$	$C_{\text{out}}$	$S$
1	1	1	1	1
1	1	0	1	0
1	0	1	1	0
1	0	0	0	1
0	1	1	1	0
0	1	0	0	1
0	0	1	0	1
0	0	0	0	0

Black Box Notation

To save drawing out all of the gates every time you can draw the diagram as a package. There is also a symbol for an adder:

4-bit Adder

To complete the following calculation:

\[\begin{array}{ccccc} &a_3&a_2&a_1&a_0\\ +&b_3&b_2&b_1&b_0\\ \hline c&s_3&s_2&s_1&s_0 \end{array}\]

You would use the following circuit:

If the carry out from this is non-zero then there has been an overflow and the value is larger than you can provide space for.

This is an example of a combinatorial circuit.

Computer Representation of Negative Integers

Typically a fixed number of bits is used to represent integers:

• Unsigned integers can take up all space.
• Signed Integers
  • Leading Sign
    • Uses the first bit to denote being negative.
    • This can store negative zero which is not desired.
  • Two’s Complement

    • Given a positive integer $a$, the two’s complement of $a$, relative to a fixed bit length $n$, is the binary representation of:

      \[2^n-a\]

    • You can view this as flipping the bits.

Two’s Complement

The two’s complement of $a=3$ is:

\[2^4-3=13=1101_2=-3_{10}\]

The bonus of two’s complement is that $-1_{10}=1111_2$ will roll over to 0 when you add 1 to it. This also means that there is no two’s complement of zero as it is an overflow. This is good as we don’t want negative zero.

Properties

• Positive numbers start with 0, negative numbers start with 1.
• 0 is always represented as a string of zeros.
• -1 is always represented as a string of ones.
• The number range is split unevenly between $+ve$ and $-ve$ numbers (If 0 is positive then is is even).
• The range of numbers we can represent in $n$ bits is $-2^{n-1}$ to $2^{n-1}-1$.

Addition & Subtraction

You can add any negative number in order to take it. Generally any carry that goes off the end can be ignored.

Overflow

If Both inputs to an addition have the same sign, and the output sign is different, an overflow has occurred.

Overflow cannot occur if inputs have opposite sign.

Two’s Complement & Bit Negation

Take the example of $n=4$:

• $s^4-a=((2^4-1)-a)+1$
• The binary representation of $(2^4-1)$ is $1111_2$.
• Subtracting a 4-bit number $a$ from $1111_2$ just switches all the 0’s in $a$ to 1’s and all the 1’s to 0’s.
• So, to compute the two’s complement of $a$, flip the bits and add 1.

Converting to Decimal

To find the decimal representation of the integer with a given two’s complement:

• Fint the two’s complement of the given two’s complement.
• Write the decimal equivalent of the result.

4-bit Subtractor

The following diagram is an implementation of $a-b$ as the sum of $a$ and the two’s complement of $b$.

This flips the bits of $b$ and adds one via the carry in.

A more automated approach would be the following:

The XOR gates flip the bits when Subtract is high. Additionally, when Subtract is high 1 is added to the carry in.

Floating Point Numbers

It is not always possible to express numbers in integer form.

Real, or floating point numbers are used in the computer when:

• The number to be expressed is outside of the integer range of the computer like:

  \[3.6\times 10^{40} \text{ or } 1.6\times 10^{-19}\]

• The number contains a decimal fraction:

  \[123.456=1.23456\times 10^2\]

When using floating point numbers the number is writen like in scientific notation.

Binary Fractions

Fractions can be represented in base 2:

\[\begin{aligned} 10.01_2&=1\times 2^1+0\times2^0+0\times2^{-1}+1\times2^{-2}\\ &=1\times2+0+0+1\times0.25\\ &=2.25_{10} \end{aligned}\]

This gives a scientific representation of $10.10_2=1.001\times2^1$

In binary, for any non-zero number the leading digit is always 1.

To represent a number in scientific notation:

• The sign of the number.
• The magnitude of the number, known as the matissa or significand.
• The sign of the exponent
• the magnitude of the exponent.

Example - 1 Byte

\[S\ EE\ MMMMM\]

• $S$ is the sign of the number.
• $EE$ are the two characters encoding the exponent.

  • Both sign and magnitude.

    This is very low precision see the IEE 754 section for the list of precisions.

• $MMMMM$ are five characters for the mantissa.

IEEE 754

IEEE standard for floating point arithmetic. This is implemented in many hardware units and stipulates the computer representations of numbers:

• 16 bit half precision numbers.
  • 5 for exponent, 11 for mantissa.
• 32 bit single precision numbers.
  • 8 for exponent, 24 for mantissa.
• 64 bit double precision numbers.
  • 11 for exponent, 53 for mantissa.
• 128 bit quadrouple precision numbers.
  • 15 for exponent, 113 for mantissa.
• 16256bit octouple precision numbers.
  • 19 for exponent, 237 for mantissa.

As numbers are not stored as surds, small rounding error can accumulate if there isn’t enough precision.