Untitled

BOOLEAN ALGEBRA

The digital circuitry in digital computers and other digital systems is designed, and its behavior is analyzed, with the use of a mathematical discipline known as Boolean algebra.

could be used to solve problems in relay-switching circuit design

Boolean algebra turns out to be a convenient tool in two areas:

Analysis: It is an economical way of describing the function of digital circuitry.

Design: Given a desired function, Boolean algebra can be applied to develop a simplified implementation of that function.

makes use of variables and operations.

variable may take on the value 1 (TRUE) or 0 (FALSE).

The basic logical operations are:

AND, OR, and NOT

symbolically representation:

A AND B = A*B

A OR B = A + B

NOT A = A

The operation AND yields true (binary value 1) if and only if both of its operands are true. The operation OR yields true if either or both of its operands are true. The unary operation NOT inverts the value of its operand.

DIGITAL LOGIC

Gates

The fundamental building block of all digital logic circuits is the gate. Logical functions are implemented by the interconnection of gates.

A gate is an electronic circuit that produces an output signal that is a simple Boolean operation on its input signals. The basic gates used in digital logic are AND, OR, NOT, NAND, NOR, and XOR.

Each gate is defined in three ways: graphic symbol, algebraic notation, and truth table.

assert a signal is to cause a signal line to make a transition from its logically false (0) state to its logically true (1) state. The true (1) state is either a high or low voltage state, depending on the type of electronic circuitry

It should be clear that AND, OR, and NOT gates constitute a functionally complete set, because they represent the three operations of Boolean algebra. For the AND and NOT gates to form a functionally complete set, there must be a way to synthesize the OR operation from the AND and NOT operations. This can be done by applying DeMorgan’s theorem:

A + B = A*B

A OR B = NOT ((NOT A) AND (NOT B))

With gates, we have reached the most primitive circuit level of computer hardware.

combinational circuits

A combinational circuit is an interconnected set of gates whose output at any time is a function only of the input at that time. As with a gate, a combinational circuit can be defined in three ways:

Truth table: For each of the 2n possible combinations of input signals, the binary value of each of the m output signals is listed.

Graphical symbols: The interconnected layout of gates is depicted

Boolean equations: Each output signal is expressed as a Boolean function of its input signals.

Implementation of Boolean Functions.

Any Boolean function can be implemented in electronic form as a network of gates. For any given function, there are a number of alternative realizations.

We can express this function by simply itemizing the combinations of values of A, B, and C that cause F to be 1:

F + ABC + ABC + ABC

The SOP form expresses that the output is 1 if any of the input combinations that produce 1 is true. We can also say that the output is 1 if none of the input combinations that produce 0 is true.

The SOP has one term for each 1, and the POS has one term for each 0. However, there are other considerations:

It is often possible to derive a simpler Boolean expression from the truth table than either SOP or POS.

It may be preferable to implement the function with a single gate type (NAND or NOR).

Three methods that can be used to achieve simplification are:

1) Algebraic simplification

2) Karnaugh maps

3) Quine–McCluskey tables

KARNAUGH MAPS For purposes of simplification, the Karnaugh map is a convenient way of representing a Boolean function of a small number (up to four) of variables. The map is an array of 2n squares, representing all possible combinations of values of n binary variables.

In the case of three variables, the representation is an arrangement of eight squares , with the values for one of the variables to the left and for the other two variables above the squares. For four variables, 16 squares are needed.

The map can be used to represent any Boolean function in the following way. Each square corresponds to a unique product in the sum-of-products form

The principle is as follows. Any two squares that are adjacent differ in only one of the variables. If two adjacent squares both have an entry of one, then the corresponding product terms differ in only one variable. In such a case, the two terms can be merged by eliminating that variable

This process can be extended in several ways. First, the concept of adjacency can be extended to include wrapping around the edge of the map. Thus, the top square of a column is adjacent to the bottom square, and the leftmost square of a row is adjacent to the rightmost square

Second, we can group not just 2 squares but 2n adjacent squares

We can summarize the rules for simplification as follows:

1.Among the marked squares (squares with a 1), find those that belong to a unique largest block of 1, 2, 4, or 8 and circle those blocks.

2. Select additional blocks of marked squares that are as large as possible and as few in number as possible, but include every marked square at least once. The results may not be unique in some cases.

3. Continue to draw loops around single marked squares, or pairs of adjacent marked squares, or groups of four, eight, and so on in such a way that every marked square belongs to at least one loop; then use as few of these blocks as possible to include all marked squares.

THE QUINE–MCCLUSKEY METHOD

The method is suitable for programming on a computer to give an automatic tool for producing minimized Boolean expressions

We would like to produce a minimal expression suitable for implementation with gates. The first step is to construct a table in which each row corresponds to one of the product terms of the expression.

The terms are grouped according to the number of complemented variables. That is, we start with the term with no complements, if it exists, then all terms with one complement, and so on.

The next step is to find all pairs of terms that differ in only one variable, that is, all pairs of terms that are the same except that one variable is 0 in one of the terms and 1 in the other.

Because of the way in which we have grouped the terms, we can do this by starting with the first group and comparing each term of the first group with every term of the second group.

The new table is organized into groups, as indicated, in the same fashion as the first table. The second table is then processed in the same manner as the first.

the third table that is produced contains only one term: BD. In general, the process would proceed through successive tables until a table with no matches was produced. In this case, this has involved three tables.

After the elimination of variables, we are left with an expression that is clearly equivalent to the original expression. However, there may be redundant terms in this expression, just as we found redundant groupings in Karnaugh maps. The matrix layout assures that each term in the original expression is covered and does so in a way that minimizes the number of terms in the final expression.

NAND AND NOR IMPLEMENTATIONS

It is sometimes desirable to implement a Boolean function solely with NAND gates or solely with NOR gates. Although this may not be the minimum-gate implementation, it has the advantage of regularity, which can simplify the manufacturing process.

Multiplexers

The multiplexer connects multiple inputs to a single output. At any time, one of the inputs is selected to be passed to the output.

Multiplexers are used in digital circuits to control signal and data routing. An example is the loading of the program counter (PC). The value to be loaded into the program counter may come from one of several different sources:

1) A binary counter, if the PC is to be incremented for the next instruction

2) The instruction register, if a branch instruction using a direct address has just been executed

3) The output of the ALU, if the branch instruction specifies the address using a displacement mode

Decoders

A decoder is a combinational circuit with a number of output lines, only one of which is asserted at any time. Which output line is asserted depends on the pattern of input lines. In general, a decoder has n inputs and 2n outputs.

Decoders find many uses in digital computers. One example is address decoding. Suppose we wish to construct a 1K-byte memory using four 256 * 8-bit RAM chips.

decoder can be used as a demultiplexer. The demultiplexer performs the inverse function of a multiplexer.

Read-Only Memory

Combinational circuits are often referred to as “memoryless” circuits, because their output depends only on their current input and no history of prior inputs is retained. However, there is one sort of memory that is implemented with combinational circuits, namely read-only memory (ROM).

ROM is a unit that performs only the read operation. This implies that the binary information stored in a ROM is permanent and was created during the fabrication process.

A ROM can be implemented with a decoder and a set of OR gates.

This can be viewed as a truth table with four inputs and four outputs. For each of the 16 possible input values, the corresponding set of values of the outputs is shown.

It can also be viewed as defining the contents of a 64-bit ROM consisting of 16 words of 4 bits each.

Adderrs

Binary addition differs from Boolean algebra in that the result includes a carry term.

we wish to add two n-bit numbers. This can be done by putting together a set of adders so that the carry from one adder is provided as input to the next.

For a multiple-bit adder to work, each of the single-bit adders must have three inputs, including the carry from the next-lower-order adder.

If the carry values could be determined without having to ripple through all the previous stages, then each single-bit adder could function independently, and delay would not accumulate. This can be achieved with an approach known as carry lookahead.

TEC,sede central,Fundamentos de organizacion de computadoras

Escuela de ingenieria en computacion

Resumen #4 (W.Stallings, cap. 11 - Lógica Digital) PARTE 1

Jossy Mejia Vargas 2017109693

Lunes 4 de septiembre del 2017, 2 semestre, Esteban Arias Mendez