Computer Logic

Computer logic is an aspect of computer design concerning the fundamental operations and structures upon which all computer systems are built.

Number systems and codes

Number systems Theory

Numerical systems are based on counting using an alphabet and operations. The decimal number system uses the alphabet {0,1,2,3,4,5,6,7,8,9}, called digits, and the basic operations add, subtract, mulitply, and divide, symbolised as {+,-,*,/}.

The decimal number system has enough digits to count 9 items. To avoid creating as many digits as quantities we might encounter, the idea of relative or positional counting is used. The digit 5, for example can mean five, fifty, five-hundred, or five-millionth. Similarly for all the other digits - except zero (0). Zero is unique in that it serves as a place holder so that the other digits are correctly positioned. Thus the numbers 5, 50, 500, 0.000005 all contain the digit 5 to represent different quantities and the 0 digit merely allows us to correctly position the 5.

Digits are arbitrarily defined, so the digit 2 could mean forty-nine, 3 perhaps means seven (not the digit 7), and so on. While this may seem crazy, the fact is this flexibility is exactly what enables computer scientists to design language aware tools, like word-processors, spell checkers, and rudimentary language translators.

Since computer science is utterly based on Number System Theory, the meaning of digits must be expanded beyond mere counting, quantities, and values. However, passing digits between devices and humans cannot be done arbitrarily, otherwise we would not make sense of the results. For this reason there are basic conventional standards which define what digits will mean under specific situations. One such standard is the American Standard for Code International Interchange, or ASCII.

This Standard is a table which defines what the numbers zero (0) through one-hundred twenty-seven (127) represent. The English alphabet {a,b,c,...,x,y,z} is represented in both upper- and lower-case forms, as well as the digits themselves! Thus, the ASCII for the digit zero (0) is the number 48, one (1) is 49, and nine (9) is 57. Here, we have overloaded the digits to mean both a value (48) and a digit (0). This can lead to problems if we do something like: 48 = 40 + 8; is 48 an ASCII code or the number forty-eight? Unfortunately, the answer is: it depends on the context.

The key to understanding computers lies in unlearning that the digit 1 means one and only one, and learning that the digit 1 identifies something, which may not be a number at all. Similarly for all other digits. Indeed, we often borrow letters {a,b,c,...,x,y,z} to represent digits, too. The letter 'A', for example may represent the number ten, 'B' eleven, and 'F' fifteen. However, underneath all this meaning, the digits themselves have fixed and unique numerical values and obey Number Systems Theory.

Number Systems differ only in their total digits and all can represent the same quantity. So if we only had four digits, say {0,1,2,3}, we could still represent the number twenty as 110₄. We arrive at this surprising result by noting that the positional value has changed.

Here we can only count 3 values, so four must be written as 10₄. By moving 1 one position to the left we show it is four times its value - not ten times! We read it as, "One-zero, in the four Number system". So eight is 10₄(four) + 10₄(four), or 20₄. Twelve is three fours, or 30₄. Fifteen is twelve plus three or 33₄. Since sixteen is is four fours, we must again move 1 left another position, giving us 100₄ (or "One-zero-zero, in the four Number system"). Nineteen is sixteen plus three, or 103₄. Finally, twenty is four fours plus a four or 110₄.

Lets pick another number system, say one with twenty digits. The quantity twenty in this system is the number 10₂₀ (or "One, zero, in the twenty Number System"). We conclude that 110₄ = 10₂₀, or "One-One-zero in the four Number System equals one-zero, in the twenty Number System".

The astute reader (and you are, aren't you?) will have noticed that a ten-digit number system can represent nine values, four digits only three values, and twenty no more than nineteen. In each case the maximum value is one less than the number of digits. This is true for all number systems. Further, when repositioning digits left (or right), their value changes by a multiple of the number of digits. For a ten digit system the change is a multiple of ten, a four digit system changes by a multiple of four, and a twenty digit system changes each position by a multiple of twenty.

The Base and Power

A Number System is defined by how many digits it has, and this is called the base. We can therefore identify a Number System by its base. The number 110₄ can now be read as, "One-one-zero, base four" and know that "One-one-zero, base eight" (110₈) might look similar to 110₄, but is actually a different value in another Number System.

to be continued ....

Binary, Octal, Decimal and Hexadecimal Systems

Computer systems regularly use numeral systems of bases other than 10. Base 2 (binary), Base 8 (octal), and Base 16 (hexadecimal) numeral systems are used because designing a computer system is simpler in this manner than for other bases.

Binary numbers are the core of all computer operations. Unlike a decimal number, which has ten digits, a binary number is made up of only two digits, 1s and 0s. It is very easy to represent binary values in electrical circuits and computer systems. A high voltage can be used for 1, and a low voltage for 0. A single value, such as a 1 or a 0, is called a bit.

Hexadecimal is often used to represent binary data. The hexadecimal numeral system has the special property that every digit represents exactly four bits, so it can be used as a compact representation of large values. For example, the binary equivalent of the hexadecimal number A3 is 10100011, where A is 1010 (10 in decimal) and 3 is 0011 (3 in decimal).

Conversion

To convert from any base to another we use the 10th base as a portal base 0∙〖10〗^1+7∙〖10〗^0=07=7 then we divide the result by the other base (binary) and get the modular of it until the end 7mod2=1 3mod2=1 2mod1=1 since if the left number is less than the right number then we take down the number itself... after that we put the mod result beside each other from the last result to the first result 7(oct)=111(binary)

Arithmetics of non-decimal numbers

Just as rules exist for arithmetic operations on decimal numbers, there are a number of techniques for evaluating various operations in non-decimal bases.

Several systems have been designed to represent negative numbers in binary. The most commonly used is called two's complement. This system is popular because numbers using this representation are easy to negate, and arithmetic operations can be performed on both positive and negative numbers in the same manner.

In two's complement, binary values whose most significant bit (MSB) is 0 are positive, whereas those whose MSB is 1 are negative. To negate a two's complement binary number, invert all of the bits and add one. For example, 00010110 (22 in decimal) becomes 11101010 (-22 in decimal).

There are two common methods of calculating the two's complement of a binary number. The first is to first use one's complement, which is the simple inversion of each bit (1 becomes 0; 0 becomes 1). So the given binary representation of decimal 22, converted to one's complement is 11101001. To obtain the two's complement from the one's complement, just add 1. This yields 11101010 (-22 decimal). The mechanics of addition will become clearer as you progress. The other method is a shortcut to using one's complement and adding one; it takes advantage of the fact that adding 1 forces you to carry that bit during the addition, so we save ourselves some work ahead of time: beginning with the least significant bit (LSB), keep all of the 0-bits and the least significant 1-bit (10 in our example); then invert all of the bits more significant than that least significant 1-bit (111010); finally, the end result is 11101010 (-22 decimal).

Addition

To perform addition in any number system, begin with the LSB. Combine the two LSB's but if you exceed the base, you must carry a one to the next position. Any difference between the total combination computed and the base is to be left in that position. Here is an example in decimal: 456 + 789:

In the first place (places are numbered beginning with the least significant bit, a.k.a. right-most), we have 6 + 9, which yields 15. Because we are in decimal, we can only use {0-9}, so after 9, we need to carry one to the next place. 15 = 10 + 5, so 5 remains in the first place, and we carry the 10, but when we carry 10 to the next place, it is represented as 1.
In the second place, we have 3 terms to combine: 1 + 5 + 8, yielding 14. Again, 14 = 10 + 4, so we leave 4 as the result in the second place and carry the 10 as a 1 to the third place.
In the third place, we have 1 + 4 + 7 = 12. We see that 12 = 10 + 2, so we leave 2 as the result in the third place and carry the 10 as a 1 to the fourth place.
In the fourth place, which did not exist at the start of the problem, we have 1. This is the resultant value for the fourth place since there are no other terms with which to combine it.

And there you have it! In binary, it is slightly easier, because you will notice that after 1, we have already reached the base, so just zero the current position, and carry that 1 to the next position. It should feel like flipping bits, which it is!

In Binary Addition, We have to use following truth Table

A	B	A+B
0	0	00
0	1	01
1	0	01
1	1	10

The most significant bit in A+B is carry and is taken to next bit in addition.Here is an example: 1111 + 0101;

   1111          
    1111       15   
    0101        5    
   +-----        
   10100       20

Subtraction

Similar to Addition specified above we can perform binary Subtraction using truth table below

A	B	A-B
0	0	00
0	1	10(carry is -1 which is absurd in binary representation)
1	0	01
1	1	0

Multiplication

When doing multiplication with binary numbers the following truth table is used. The truth table for addition is also needed.

A	B	A*B
0	0	0
0	1	0
1	0	0
1	1	1

Example multiplication:

   1011         11
    101          5   
  *-----              
   1011           
  0000            
 1011             
+------           
 110111         55

Division

Binary Codes

The most common binary codes are BCD, Excess-3, and Gray Code. Each has its purpose. BCD stands for "Binary-coded decimal" and is just that. Using 4-bit binary strings, each decimal digit is encoded in binary: 486₁₀ = (0100 1000 0110)₂. The limit is of course 1001₂ because 9 is the largest decimal value and the 4-bit binary string has a capacity of 15₁₀.

Excess-3 code is the same as BCD, but adding 0011 (3₁₀). Gray Code has the core concept of reducing the number of bitwise changes to 1 for each increment in the counting order. This requires less power in a system, but will seem like an arbitrary sequence at first glance.

Please refer to Wikipedia article on Binary code

Logic gates and Digital Circuits

Any arithmetic operation in a computer system can be implemented using basic logical operations, such as AND and OR. In fact, it has been proven that an entire computer system can be designed and implemented using solely the NAND operation.

These logical operations have truth tables associated with them, which enumerate the output signals for particular combinations of inputs. Input signals are typically named A, B, and C, whereas outputs are typically represented as F, G, X, and Y.

The part of a digital logic circuit which performs one of these operations is called a gate. Signals enter these gates (inputs), and the gate generates new signals (outputs) depending on the signals it received.

The time it takes for a gate to generate an output when it receives new inputs signals is not instantaneous, but it is very fast, on the order of picoseconds. This switching time is dependant on the type of gate, and since gates cannot be perfectly manufactured, there is some uncertainty in the exact time.

NOT gate

The symbol for a NOT gate.

The NOT gate, more commonly called an inverter or inverting buffer, simply negates a signal. When it receives a low input, it outputs a high signal. When it receives a high input, it outputs a low signal.

A	F
0	1
1	0

AND gate

Please refer to Wikipedia article about the AND gate.

The symbol for a two-input AND gate.

An AND gate has two or more inputs, and one output.

A	B	F
0	0	0
0	1	0
1	0	0
1	1	1

OR gate

Please refer to Wikipedia article about the OR gate.

The symbol for a two-input OR gate.

An OR gate has two or more inputs, and one output.

A	B	F
0	0	0
0	1	1
1	0	1
1	1	1

NAND gate

Please refer to Wikipedia article on the NAND gate.

The symbol for a two-input NAND gate.

A NAND gate has two or more inputs, and one output. It is equivalent to the negation of the output from an AND gate with the same inputs.

A	B	F
0	0	1
0	1	1
1	0	1
1	1	0

XOR gate

Please refer to Wikipedia article on the XOR gate.

The symbol for a two-input XOR gate.

An XOR gate has two or more inputs, and one output.

A	B	F
0	0	0
0	1	1
1	0	1
1	1	0

Boolean Algebra

Please refer to Wikipedia article on Boolean algebra, or to the Wikiversity page on Boolean algebra.

Combinational Logic Design and principles

Switching Algebra

Combinational circuit analysis

Programmed minimization methods

Documentation standards

Block Diagrams

The "Block diagram" of a full one-bit adder

Block diagrams are used so that somebody looking at a circuit diagram does not have to see the details of every part, every time it appears in the diagram.

Circuit Timing

Decoders

A 2-to-4 decoder. Which line would be activated if the input was 10 (base-2)?

Decoding is performed by decoder,a combonational circuit with an n-bit binary code applied to its input and an m-bit binary code appears at the output.

Encoders

An encoder is a digital function that perform the inverse operation of a decoder.An encoder has 2'n input lines and n output lines.The output lines generate the binary code corresponding to the input value.

Multiplexers

A 4-to-1 multiplexer.

Multiplexers (sometimes called muxes, singular mux, for short) are used to route multiple signals over a single wire. Select signals are used to select the input signal to allow through to the output.

Demultiplexers (demuxes) perform the inverse operation. They accept a single input, and route it to a selected output.

Comparators

Adders, Subtractors

A full adder.

Sequential Logic

Latches and Flip-Flops

Latches and flip-flops can store one bit of data each.

S-R Latch

An asynchronous R/S Latch

SR latch operation
S	R	Action
0	0	Keep state
0	1	Q = 0
1	0	Q = 1
1	1	Restricted combination

The symbol for an SR latch.

D Flip-Flop

A D flip-flop is loaded with the signal present at D when the clock is high, low, rising, or falling (depending on the type used).

Master-Slave combinations

Clocked Synchronous State Machines

Feedback Sequential Circuits

Memory

All memory (RAM) is simply collections of flip flops, with a way of addressing a particular segment/word.

Bibliography

DIGITAL DESIGN practices and principles, second edition, by John. F. Wakerly