Boolean Algebra (Basic Laws, POS and SOP expressions)

What is Boolean Algebra?

}  Boolean Algebra is the mathematic representation of operation of logic gates (and digital circuits).

}  Boolean Algebra has variables (input and output) and operators (AND, OR Complement).

}  Operation of a logic gate (and digital circuit) can be represented using a Boolean function. Truth table is used to illustrate the results of a Boolean function.

SOP and POS expressions

}  There are two types of boolean expressions

◦     Sum of Products (SOP) expressions

◦     Product of Sums (POS) expressions

 

}  SOP expression

◦     A product term is produced when one or more boolean variables are logically multiplied. It is also called minterm. When two or more product terms are logically added a SOP expression is formed.

 

}  POS expression

◦     A sum term is produced when one or more boolean variables are logically added. This is also called maxtern. When two or more sum terms are logically multiplied a POS expression is formed.

You may read more on SOP and POS expressions here https://faculty.etsu.edu/tarnoff/ntes2150/Ch6_v02.pdf

Rules and Laws of Boolean Algebra

}  In Boolean algebra a variable can have only either 1 (TRUE) or 0 (FALSE) values. In Boolean algebra 1 is stands to represent the state of TRUE, not integer value 1. Also 0 stands to represent the state of FALSE, not the integer value 0. Therefore addition and multiplication works differently than we normally do in mathematics.

}  In Boolean algebra we do only addition and multiplication.

Basic Rules

Basic Laws

Basic Duality

}  According to basic laws of Boolean algebra there is an important feature called “Basic Duality”. It says that every boolean function has a dual function.

}  The duality principle ensures that "if we exchange every symbol by its dual in a formula, we get the dual result".

}  Everywhere we see 1, change to 0.

}  Everywhere we see 0, change to 1.

}  Similarly, + to ., and . to +.

More examples:

0 . 1 = 0: is a true statement "false and true evaluates to false“ it’s a basic law.

 Now lets replace all values and operations by its opposite value.

1 + 0 = 1: is the dual of (a): it is a true statement that "true or false evaluates true.“ it is also a basic law.

Like this, in every formula, if we replace every value and operation by its opposite, including the result, we get a valid formula.

De-Morgan’s Law

This is a very useful law in boolean algebra. This allows to get the complement of a boolean expression. This represent the basic duality of boolean algebra and mostly used when we design circuits using NAND and NOR gates.

 

(x + y)’ = x’.y’

(x.y)’ = x’ + y’

 

To get the complement of a boolean expression, do the following two steps;

 

•    Replace all values in the expression by its opposite.

•    Replace all “+” with “.” and vise versa.

Computer and Network Technology (CNT) - Lecture 04 from Susantha Herath

Logic Gates

Introduction

• Computer is a electronic device. It is a digital circuit built using many types of electronic components. The most important component in a computer is the processor. There are more than one processors in a modern computer dedicated for specific tasks.
• Processors are made of combination of millions of transistors. Transistor is the smallest single electronic component inside a processor. There are single transistors in a digital circuit for other operations, but we are talking about inside a computer processor.
• Using special combinations of different transistors (and other components such as diodes and resistors), small operational and individual circuit blocks are created. These blocks are called “Logic Gates”.
• We can say that a Logic Gate is the smallest single circuit unit in a processor.
• So, a processor is made of millions of logic gates.
• We now know that a computer is a digital circuit and it uses binary number system for data representation. We know that binary number system uses only 1 and 0. In a digital circuit, we can say that these are two states of current TRUE and FALSE.
• Logic gates are all about representing these two states of current with different inputs and output.
• It is important to understand how computer works in circuit level to learn other areas of computers such as programming and networking.

Logic Gates

• There are seven types of logic gates. Each logic gate represent with a unique symbol.
• A logic gate has one or more input and one output.
• Logic gates are the building blocks of a digital circuit (processor).
• Truth tables are used to show the operation of a gate (or gates). A truth table shows output for all possible combinations of inputs.

NOT gate (inverter)

• NOT gate has one input and one output
• NOT gate also called as the inverter gate because it convert the input state opposite.
• As shown in above truth table (A is input and X is output), NOT gate invert the input state.
• There are only two possible combination of inputs as shown in the above truth table.

AND gate

AND gate has two inputs and one output. When there are two inputs, there are only 4 possible combinations of outputs as shown in the following truth table. Output x TRUE only if both inputs (A and B) are TRUE.

OR gate

Output x TRUE if both or either one input (A or B, or both A and B) is TRUE. These output of gates are calculated according to BOOLEAN ALGEBRA which we will discuss in the next lesson.

XOR gate

Output x is TRUE if only one input is TRUE.

NAND gate

In NAND gate output x is FALSE only if both inputs (A and B) are TRUE.

NOR gate

In NOR gate output x is TRUE only if both inputs (A and B) are FALSE.

XNOR gate

In XNOR gate output x TRUE only if both inputs (A and B) are TRUE or both inputs are FALSE.

Summary

• Logic gates are the building blocks of a computer processor.
• There are seven logic gates.
• Boolean Algebra is the mathematics use to represent operations of logic gates (logic circuits).

Computer and network technology (CNT) lecture 03 from Susantha Herath

Representation of Integers

Few basic things to know

• Most Significant Bit (MSB) also called as Most Significant Digit (MSD). This is indeed the first digit (from left) in a binary number. More accurately the digit with the highest radix (base) value.
• Least Significant Bit (LSB) or Least Significant Digit (LSD). This is the digit of a binary number with the least radix value, probably the last digit.
• In binary number one digit is called as a bit.
• Computer memory is a place that store data and it has a fixed length of bits. Generally 8bit, 16bit, 32bit and 64bit in length.

Data Representation

• Computer uses a fixed number of bits to represent a single piece of data. Generally computers use 8bit, 16bit, 32bit and 64bit in size of binary numbers to represent different type and size of data.
• N-number of bit memory (location) can store 2n of different types of values.
• For an example 8bit memory can store 256 of different data values.
• 3bit memory can store 8 distinct values (patterns) 000, 001, 010, 011, 100, 101, 110, or 111
• 
  
• When we interpret these values, we need to know exactly what represent with these values.
• If we know that these represent decimal numbers, then we know it is from 0-7 then it is a different value.
• So this interpretation of a binary pattern called data representation or encoding.

Integer Representation

Integers are whole numbers or fixed point numbers. The radix point is fixed after the LSB.

Example: 3774 is a fixed point number (integer)

2949.94 is a floating point number (real number)

qIn a computer integers and floating point numbers are treated differently and processed separately. Floating point numbers are processed in a separate processor called floating point processor.

qComputers use fixed number of bits to represent integers. Commonly use bit lengths are 8bit, 16bit, 32bit and 64bit.

qThere are two types of integers

qUnsigned integers: can represent zero and positive numbers only

qSigned integers: can represent zero, positive and negative numbers.

q

qThere are three schemas (ways) to represent signed integers.

qSign Magnitude representation

q1’s complement representation

q2’s complement representation

qWe learned about two different types of Integers;

qUnsigned Integers – that can represent only zero and positive numbers. The value of an unsigned integer interpreted as the “magnitude of underlying binary pattern or the normal way we convert binary to decimal.

q

Example: 8bit binary number 0100 0010B (B = Binary)

0100 0010B = 2x21 + 2x26 = 4+64 = 68D (D = Decimal)

8bit   = 0000 0000

16bit = 0000 0000 0000 0000

32bit = 0000 0000 0000 0000 0000 0000 0000 0000

64bit = 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000

All above numbers represent zero in different bit systems. The bit length of each system is different.

n-bit Unsigned Integers

qAn n-bit pattern can represent 2n distinct integers. This range from 0 to (2n)-1

When you are programming you need to select the correct and appropriate bit size to store integers. If you want to store small numbers less than 255, you can select 8bit number, selecting 32bit length to store small numbers is a waste of resources.

Signed Integers

qSigned integers can represent zero, positive and negative numbers.

qThe MSB (Most Significant Bit) – Normally the first bit from left, represent the sign of the integer. Zero (0) to represent positive (+) sign and One (1) to represent negative (-) sign.

qThe magnitude of the integer represent differently in different schemas.

qThere are three schemas to represent signed integers.

1.Sign Magnitude Representation

2.1’s Complement Representation

3.2’s Complement Representation

Example of Signed Integers:

  +2344 is a positive integer  -23434 is a negative integer

n-bit Sign Magnitude Representation

qMost Significant Bit (MSB) is the sign bit. 0 representing positive and 1 representing negative signs.

qThe remaining (n-1) bits represent the magnitude / absolute value of the integer interpreted according to its binary pattern.

Examples:

n=8 (8bit number) and binary number is 01000001

Sign bit (MSB) is 0 à this is a positive number

Absolute value 1000001 à 65

01000001B = +65D

B = Binary, D = Decimal

Examples:

n=8 (8bit number) and binary number is 00000000

Sign bit (MSB) is 0 à this is a positive number

Absolute value 0000000 à 0

00000000B = +0D

n=8 (8bit number) and binary number is 10000000

Sign bit (MSB) is 1 à this is a negative number

Absolute value 0000000 à 0

10000000B = -0D

Problems (Drawbacks / Limitations) of Sign Magnitude Representation:

qThere are two representation for the number zero

qEven the number zero need to have a sign, since it is not necessary nor accurate and may leads to confusions.

qPositive and negative numbers need to process separately.

n-bit 1’s Complement Representation

In this representation, the MSB is the sign bit 0 represent positive and 1 represent negative numbers. The remaining n-1 bits represent the magnitude (value) of the integer.

qIn positive integers, the value of the integer is the binary pattern (value) of the n-1 bit magnitude. Same as Sign Magnitude Representation.

qFor negative integers, the absolute value is the n-1 binary pattern value of the inverse magnitude (complement).

Example: 1 000 0001B (sign bit = 1, negative integer)

Complement of 000 0001 is 111 1110 = 126D

1 000 0001B = -126D

In the 1’s Complement Representation, there are two different representation for zero;

0000 0000B and 1111 1111B hence +0 and -0

Since the processing method of positive and negative integers are different, computer need to process the positive and negative numbers separately.

n-bit 2’s Complement Representation

In 2’s Complement Representation also the MSB is the sign bit 0 represent positive and 1 represent negative integers.

For positive integers, the value of the integer equal to the magnitude of n-1 binary pattern

For negative integers, the absolute value of the integer equal to the magnitude of the complement of n-1 binary pattern plus one.

Example: 1 000 0001B (MSB = 1 is a negative number)

Complement of 000 0001 = 111 1110

Let’s add 1 to the complement = 111 1111 = 127

1 000 0001B = -127D

Advantages of 2’s Complement Representation

qThere is only one representation for the number 0

qIn binary addition and subtraction, both positive and negative numbers can treated together (process together)

qSubtraction can use the addition logic

qComputers use 2’s Complement Representation for processing integers.

Addition, Subtraction, Overflow and Underflow

Addition of positive integers

Example: n=8, 65D + 5D = 70D

65D   à   0100 0001B

5D   à   0000 0101B

65D + 5D   à  0100 0110B OK 70D within the range of -128 to +127

Subtraction is the addition of positive and negative integers

Example: n=8, 65D – 5D = 60D à 65D + (-5D)

65D   à   0100 0001B

-5D   à   1111 1011B

65D + (-5D)   à  0011 1100B à 60D OK within the range of -128 to +127

Overflow and underflow happens when the result is not within the acceptable range

Example of Overflow: n=8, 127D + D = 129D (not within -128 and +127, exceed maximum value)

127D   à   0111 1111B

2D   à   0000 0010B

127D + 2D   à  1000 0001B à -127D wrong answer

Example of underflow: n=8, -125D – 5D = -130D (not within -128 and +127, below the minimum value)

-125D   à   1000 0011B

-5D   à   1111 1011B

-125D + (-5D)   à  0111 1110B à +126D wrong answer

Range of n-bit 2’s complement signed integers

An n-bit 2’s complement integer can represent integers from -2(n-1) to +2(n-1)-1. This can represent all the integers within the range without missing any integers.

8bit from -128 to +127

16bit from -32,768 to +32,767

32bit from -2,147,483,648 to + 2,147,483,647

64bit from -9,223,372,036,854,775,888 to + 9,223,372,036,854,775,887

Decoding 2’s complement numbers

•Check the sign bit first. If sign bit = 0, the number is positive and the absolute value if the binary value of remaining n-1 integers.

•If the sign bit = 1, the integer is negative. To get the absolute value;

•Invert remaining n-1 bits and add 1 or

•Scan from left until the first occurrence of 1. Flip all values from that point to the left. Binary value of this pattern gives the absolute value of the negative integer.

Example:

N=8 bit pattern = 1 100 0100 B

Negative number

Scan from right, until the first occurrence of 1, flip all values from that point to left

011 1100 B = 60 D

Represented negative value is -60 D

Big Endian vs. Little Endian

Modern computers store one byte of memory in single memory location / address. 1 byte = 8 bits. Therefore in 32bit integer stores in 4 memory locations.

Term “Endian” means the order of storing bytes in memory. In Big Endian standard – the most significant byte stores first in the lowest memory location. In Little Endian standard, the least significant byte (LSB) stores in the lowest memory location.

Floating Point Number Representation

A floating point number (also called as a real number) is a number with a decimal point. A floating point number can represent a very large positive or negative number as well as a very small negative or positive number. A real number has a range of -1.23x1088 to 1.25x1088 including zero.

Scientifically a floating point number represent as a number with a fraction and exponent of a certain radix.  F x rE

Same floating point number can represent in different ways. Consider 5.456D

We can represent this number in following ways:

54.532 x 100

5.4532 x 101

0.54532 x 102 and so on….

Since there are many ways to represent the same floating point number, we need to define a standard, so every floating point number should be in this standard. To make it standard, we can normalized the fraction part. In normalized form, there is only single none zero digit represent before the radix point. In above example 5.4532 x 101 is the normalized form of 54.532 number.

In computers, there is an issue of “Loss of Precision” in storing floating point numbers. An n-bit system can only stores 2n distinct finite numbers. Even within a small range 0.00 – 0.01, there are infinite number of decimal numbers. But the number of bits in a computer system is limited, only a the approximate number used, resulting in loss of accuracy.

Processing of a real number (floating number arithmetic) is very much less efficient and slower than processing of integers. In computers, real numbers uses fraction (F) and exponent (E) with radix (r) of 2. Both F and E can be negative or positive. In modern computing uses IEEE 754 standard to represent floating point numbers. There are two representation schemes

32 bit single precision and

64 bit double precision

IEEE-754 32-bit Single-Precision Floating-Point Numbers

In 32-bit single precision floating point number representation, decimal number represent in following structure:

•The most significant bit is the sign bit. Zero for positive numbers and One for negative numbers.

•Next following 8bit represent the exponent (E)

•Remaining 23bit represent the fraction (F)

You may wonder why radix (r) is not represent here. Because radix is always 2 for binary numbers (in computers).

IEEE-754 64-bit Double-Precision Floating-Point Numbers

64-bit double precision floating point number representation is similar to 32-bit single precision floating point number representation. Only difference is assignment of bit range for exponent and fraction.

•The most significant bit is the sign bit. Zero for positive numbers and One for negative numbers.

•Next following 11-bit represent the exponent (E)

•Remaining 52-bit represent the fraction (F)

Character Encoding

In computer memory, characters are represented (encode) using character schemes called as “character set”, “charset”, “character map” or “code page”. There are several standard schemes such as ASCII, EBCDIC, UTF, etc.

7-bit ASCII Code (aka US-ASCII, ISO/IEC 646, ITU-T T.50)

•ASCII (American Standard Code for Information Interchange) is one of the earlier character coding schemes.

•ASCII is originally a 7-bit code. It has been extended to 8-bit to better utilize the 8-bit computer memory organization. (The 8th-bit was originally used for parity check in the early computers). This is called ASCII-8 Code.

EBCDIC Code

This is stands for “Extended Binary Code Decimal Interchange Code”. This is a 8-bit code scheme without parity. With this up to 256 characters can be coded.

Unicode (aka ISO/IEC 10646 Universal Character Set)

•Before Unicode, no single character encoding scheme could represent characters in all languages.

•Unicode aims to provide a standard character encoding scheme, which is universal, efficient, uniform and unambiguous. Unicode standard is maintained by a non-profit organization called the Unicode Consortium (@ www.unicode.org). Unicode is an ISO/IEC standard 10646.

•Unicode is backward compatible with the 7-bit US-ASCII and 8-bit Latin-1 (ISO-8859-1). That is, the first 128 characters are the same as US-ASCII; and the first 256 characters are the same as Latin-1.

•Unicode originally uses 16 bits , which can represent up to 65,536 characters.

You can download this presentation on slideshare.

Representation of Integers from Susantha Herath