Programmable Logic Device

A programmable logic device or PLD is an electronic component used to build reconfigurable digital circuits. Before the PLD can be used in a circuit it must be programmed.

PLD is a combination of a logic device and a memory device. The memory is used to store the pattern that was given to the chip during programming. Most of the methods for storing data in an integrated circuit have been adapted for use in PLDs.

It include:

§ Silicon antifuses

§ SRAM

§ EPROM or EEPROM cells

§ FLASH MEMORY

Types of PLD( Programmable Logic Device):

PROM - Programmable Read Only Memory

PROM is the first PLD and was introduced in 1970. PROM was used as computer memories to store program instructions and constant data values. PROM have fixed AND plane and programmable OR plane and it can be uses to program any combinational logics with limited numbers of inputs and outputs. 

PLA - Programmable logic arrays 

PLA was introduce in the 1975 due to limitations imposed by the PROM where both planes of AND and OR arrays are programmable. PLA allows implementing Boolean function in sum-of-product form. This layout allows for a large number of logic functions to be synthesized in the sum of products (and sometimes product of sums) canonical forms.

PAL -Programming Array Logic

PLA was introduced in the 1978 to address speed problem shown by PLA devices. A PAL is opposite to PROM, where AND array is programmable but the OR array is fixed. Due to this, PAL is faster than PLA devices. PAL contain flip-flops connected to the OR-gate outputs to implement sequential circuits. Registered or combinational output functions are model in a sum of product form. Each output is a sum of a fixed number of products of the input signals.

FPGA - Field Programmable Gate Array 

Field-programmable gate array (FPGA) is a semiconductor device that can be programmed after manufacturing. Instead of being restricted to the predetermined hardware function, an FPGA allows to program product features and functions, adapt to new standards, and reconfigure hardware for specific applications even after the product has been installed in the field—hence the name "field-programmable". An FPGA can be used to implement any logical function that an application-specific integrated circuit (ASIC) could perform, but the ability to update the functionality after shipping offers advantages for many applications. Each logic block can be programmed individually to perform simple logic functions and then, switches can be programmed to implement desire logic function. The key element in programmable logics are 3-input Look up Table (LUT), multiplexer and flip-flop. The 3-input LUT is similar to PAL, used to implement combinational or Boolean equations.

A simple FPGA contain on each Logic Block:

Floating Point Arithmetic

Floating Point arithmetic is an arithmetic operation on floating point numbers which include addition, subtraction, multiplication and division. The operations are done with algorithms similar to those used on sign magnitude integers.

Addition :

Using a 4 digit decimal example;

9.988 x10¹ + 2.332 x 10^-1

>9.988 x 10¹ + 0.023 x 10¹

>9.988 x10¹ + 0.023 x 10¹ = 10.011 x 10¹

>10.011 x 10¹  (overflow) = 1.0011 x 10²

Answer = 1.001 x 10²

Subtraction

Example 2: (subtraction)

Using 4 digit Binary example:

>1.000_­2­ x 2^-1  -1.00­0­₂­ x2^-2 ( 0.5 – 0.25)

>1.000­_2­ x2^-1  - 0.10­0₂ ­x 2_­­­^-1­­

>1.000­_2­ x2^-1  - 0.100­₂ ­x 2_­­­^-1­­ = 0.100­₂ x2^-1

>0.10­0₂ ­x 2_­­­^-1  ( under flow)

Answer = 1.000­_{2 ­}x 2

Multiplication

Using 4bit decimal example:

1.111 x 10¹⁰  X  9.500 x 10^-7

>New exponent = 10 -7 = 3

>1.111 x 9.500 = 10.5545 x 10³

>10.5545 x 10³ (overflow) = 1.056 x 10⁴

Example in binary:

1011.01 x 110.1

           1011.01

          X  110.1

            101101

                    0

       101101

     101101

-------------------
   1001001.001

 ­

Division

11111100 / 110=  101010

                     101010

                  --------------

          110) 11111100

                   110

                   ------------

                      111

                      110

                   -------------     

                          110

                          110

                   -------------

                                 0

                                 0   

                             ------

Rounding

Rounding Decimal:

Example 1:

0.8842       round to 3 decimal places = 0.884

                   round to 2 decimal places = 0.88

round toward + infinity

example 2:

1.23            round to 2 decimal places = 1.3

-2.86          round to 2 decimal places = -2.8

round toward – infinity

example 3

1.23            round to 2 decimal places = 1.2

-2.86          round to 2 decimal places = -2.9

DIGITAL LOGIC: BOOLEAN ALGEBRA

• Boolean algebra makes use of logical variables and operations.
• A variable may take 1 (TRUE) or 0 (FALSE).
• The basic logical operations are AND, OR, and NOT, which are symbolically represented by dot, plus sign, and overbar.

• 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.

Boolean Operators of 2 Input Variables

Boolean Operators Extended to More than 2 Inputs

Basic Identities of Boolean Algebra

COMPUTER ARITHMETIC: INTEGER ARITHMETIC

NEGATION

The negation of an integer can be formed with the following rules:

1. Set each 1 to 0 and each 0 to 1.
2. Add 1.

Special case:

1. Negation of 0 is 0.
2. Negation of an n-bit word of 2^n, will get back the same number.

ADDITION AND SUBTRACTION

To Subtract a number (subtrahend) from another (minuend), take the negation of the subtrahend and add it to the minuend.

Block Diagram of Hardware for Addition and Subtraction

MULTIPLICATION

UNSIGNED INTEGER

Multiplication of Unsigned Binary Integers

Hardware Implementation of Unsigned Binary Multiplication

1. Multiplier and multiplicand are loaded into tow registers (Q and M).
2. A third register, A register is initially set to 0.
3. A 1-bit C register is also initialized to 0.
4. Control logic reads the bits of the multiplier (Q) one at a time.
• If it is 1, M is added to the A register and the result is stored. Then all the bits of the C, A, Q registers are shifted to right one bit.
• If it is 0, no addition is performed, just the shift.
5. This process repeated for each bit of the original multiplier.
6. The product is contained in the A and Q registers.

Flowchart for Unsigned Binary Multiplication

TWO'S COMPLEMENT MULTIPLICATION

Booth's Algorithm for Two's Complement Multiplication

Booth's Algorithm (7 x 3)

1. The multiplier and multiplicand are placed in the Q and M registers respectively.
2. A 1-bit register is placed to the right of the LSB of the Q register.
3. A register is initialized to 0.
4. Control logic scans the bits of Q one at a time. The bit to its right is also examined.
• If the 2 bits are same (1-1 or 0-0), then shift all the registers (except M) to the right 1 bit.
• If the 2 bits differ, then M is added to (0-1) or subtracted from (1-0) the A register, follow by the right shift. 
• In either case, the right shift is such that the leftmost bit of A, not only is shifted, but also remains.
5. This process repeated for each bit of the original multiplier.

DIVISION

Flowchart for Unsigned Binary Division

Two's Complement Division (7/3)

1. Load the divisor into the M register. Load the dividend into the A, Q registers. (The dividend is expressed as a 2n-bit positive number.)
2. Shift A, Q left 1 bit position.
3. Subtract M from A.
• If the result is positive, then add 1 to Q.
• If the result is negative, restore the previous value of A.
4. This process repeated for each bit of the original dividend.
5. The remainder is in A and the quotient is in Q.

To do two's complement division, convert the operands into unsigned values and account for the signs by complementation where needed.

DIGITAL LOGIC : COMBINATIONAL CIRCUIT

A combinational circuit is a circuit  made up by combining logic gates such that the required logic at the output(s) depends only on the input logic present condition, both completely specified by either a truth table or by a Boolean expression.

Characteristics

(i) An output(s) remains constant, as long input conditions do not require change in output(s).

(ii) An output depends solely on the current input condition and not on any past input condition or past output condition.

(iii) A combinational circuit has no feedback of the output from a stage to the input of either that stage or any previous stage.

(iv) An output(s) at each stage appears after a delay in few tens or hundred ns depending upon the type or family of the gate used to implement the circuit.

Combinational circuit representation

1.  i). A block diagram for n inputs and m outputs.

    ii). A truth table of 2ⁿ rows

Example- Truth Table Four Rows for 2 inputs and 1 output

   Inputs                          Output

A1     A2                            F

 0        0                             1

 0        1                             0

 1        0                             0

 1        1                             0

2.  i). SOP terms (2ⁿ miniterms) for each output

    ii). POS terms (2ⁿ maxterms) for each output

   iii). Karnaugh map of n variables and 2ⁿ cells

FORMULATION OF A PROBLEM IN A COMBINATIONAL CIRCUIT

A). First step is to select the combinational circuit(s) in a logic network for which the problem of designing as per specifications is to be solved.

B). Criteria for whether a problem or its part is solvable by a combination circuit or not, is as follows:

     1). Criteria for whether a problem or its part is solvable.

        i). Check whether the required logic at the output(s) depends only on the input logic conditions, both completely specified by either a truth table or by a Boolean expression.

       ii). Check whether an output(s) remains same, as long present input condition does not require the change in the output(s).

      iii). Check whether an output depends solely on the current input condition and not on any past input condition or past output condition.

Specification of each output as a function of input conditions

1. Specify the number of inputs, n. The n is also the number of literals in a Boolean expression for an output.

2. Specify the number of outputs, m.

3. Specify the delays permitted at the outputs.

4. Specify the fan-ins permitted at the inputs.

5. Specify fan-outs permitted from the targets gates and building blocks.

6. Design a ‘truth table’ for n inputs and m outputs. Each output corresponds to each possible combination of input conditions.

7.Write a Boolean expression for the logic circuit for each output: The n is also the number of literals in a Boolean expression for output.

8. Specify as SOP or POS standard Format

Specification of gate characteristics

1. Propagation delays

2. Fan-ins permitted are specified in the problem

3. If a possible combination of the input condition is unspecified or is don’t care, specify it by ‘x’. [The Boolean expression for the output is an incomplete Boolean function.]

4. If a possible condition is high impedance output ‘tristate’, specify it by  ‘*’.

Summary

1. A combinational circuit — made up by combining logic gates such that:

i). Required logic at the output(s) depends only on the input logic present condition.

ii). Both (inputs and output) completely specified by a truth table or Boolean expression.

2. A combinational circuit — Problem Formulation means

i). Building block selection

ii). Defining Specifications

ARITHMETIC FOR COMPUTERS : ARITHMETIC LOGIC UNIT (ALU)

1. is one of the many components within a computer processor
2. is the final processing performed by the processor
3. after the information has been processed by the ALU, it is sent to the computer memory
4. a combinational circuits that performs arithmetic and logical operations
5. arithmetic operations include addition,subtraction,multiplication,division,ect
6. logical operations involve Boolean logic :AND,OR,NOT and XOR
6. a fundamental component of all processors
7. the design and function of an ALU may vary between different processor models
8. for example, some ALUs only perform integer calculations, while others are designed to handle floating point operations as well


ALU Input and Output

1. Data are presented to the ALU in registers, and the results of an operation are stored in registers.

2. These registers are temporary storage locations within the processor that are connected by signal paths to the ALU.

3. The ALU may also set flags as the result of an operation.

4. For example, an over­flow flag is set to 1 if the result of a computation exceeds the length of the register into which it is to be stored.

A typical diagram of an ALU

Arithmetic Logic Unit schematic symbol

- A and B are the data inputs

- F is the control input to choose the function

- R is the result of the function applied to A and B

- D is the status of the output

Example of arithmetic operation :

1. Two's Complement Addition : add the values and discard any carry-out bit.

      using 8-bit two’s complement numbers.

a). Add −8 to +3

     (+3)   0000 0011

   +(−8)   1111 1000

   ------------------------

     (−5)   1111 1011

b). Add −5 to −2

     (−2)   1111 1110

   +(−5)   1111 1011

   ------------------------

     (−7) 1 1111 1001 : discard carry-out

2. Overflow Rule for addition : 
- If 2 Two's Complement numbers are added, and they both have the same sign (both positive or both
negative), then overflow occurs if and only if the result has the opposite sign. Overflow never occurs when adding operands with different signs.

i.e.	Adding two positive numbers must give a positive result
	Adding two negative numbers must give a negative result

Overflow occurs if

• (+A) + (+B) = −C



• (−A) + (−B) = +C

Using 4-bit Two's Complement numbers (−8 ≤ x ≤ +7)

  (−7)   1001
+(−6)   1010
--------------
(−13) 1 0011 = 3 : Overflow (largest −ve number is −8)

3. Two's Complement Subtraction : Normally accomplished by negating the subtrahend and adding it to the minuhend. Any carry-out is discarded.

Using 8-bit Two's Complement Numbers (−128 ≤ x ≤ +127)

  (+8) 0000 1000                          0000 1000
−(+5) 0000 0101 -> Negate ->  +1111 1011
------                                          -------------
  (+3)                                         1 0000 0011 : discard carry-out

4. Overflow Rule for Subtraction :

- If 2 Two's Complement numbers are subtracted, and their signs are different, then overflow occurs if and only if the result has the same sign as the subtrahend.

Overflow occurs if

• (+A) − (−B) = −C



• (−A) − (+B) = +C

Using 4-bit Two's Complement numbers (−8 ≤ x ≤ +7)
Subtract −6 from +7

      (+7) 0111                          0111
    −(−6) 1010 -> Negate ->  +0110
   -------------                       -------
       13                                     1101 = −8 + 5 = −3 : Overflow 

5. Two's Complement Summary

i). Addition

• Add the values, discarding any carry-out bit

ii). Subtraction

• Negate the subtrahend and add, discarding any carry-out bit

iii). Overflow

• Occurs when adding two positive numbers produces a negative result, or when adding two negative numbers produces a positive result. Adding operands of unlike signs never produces an overflow



• Notice that discarding the carry out of the most significant bit during Two's Complement addition is a normal occurrence, and does not by itself indicate overflow



• As an example of overflow, consider adding (80 + 80 = 160)₁₀, which produces a result of −96₁₀ in 8-bit two's complement:
  

     01010000 =  80
  + 01010000 =  80
  -------------
     10100000 = −96 (not 160 because the sign bit is 1.)
    (largest +ve number in 8 bits is 127)

6. Multiplication and Division

- No problem with unsigned (always positive) numbers, just use the same standard techiques as in base 10 (remembering that x[n] × y[n] = z[2n])

• Multiplication Example : 1100101₂ × 111101₂ (101₁₀ × 61₁₀)
  

           1100101   10110
          × 111101  × 6110

   ---------------
            1100101
        +1100101

      +1100101
    +1100101
  +1100101
  ----------------
  ?????????????
  ----------------    
  

  Easier to use intermediary results:
  

         1100101   10110
        × 111101  × 6110
        -----------
          1100101
        +1100101
       ------------
       111111001
         +1100101
    ---------------
    10100100001
          +1100101
   ----------------
   101101110001
           +1100101
  -----------------
  1100000010001 = 409610 + 204810 + 1610 + 1 = 616110
  -----------------

• Division Example : 100101₂ ÷ 101₂ (37₁₀ ÷ 5₁₀)
  

                111 result = 710
         ---------

  101) 100101
          −101
          ---------
             1000
             −101
               ------
                  111
                −101
                ------
                    10 remainder = 210
                    ---

Example of logical operations :

1. AND

The logical AND operation compares 2 bits and if they are both "1", then the result is "1", otherwise, the result is "0".

2. OR

The logical OR operation compares 2 bits and if either or both bits are "1", then the result is "1", otherwise, the result is "0".

3. XOR

The logical XOR (Exclusive OR) operation compares 2 bits and if exactly one of them is "1" (i.e., if they are different values), then the result is "1"; otherwise (if the bits are the same), the result is "0".

4. NOT

The logical NOT operation simply changes the value of a single bit. If it is a "1", the result is "0"; if it is a "0", the result is "1". Note that this operation is different in that instead of comparing two bits, it is acting on a single bit.

ARITHMETICS FOR COMPUTER: INTEGER REPRESENTIVE

• In the binary number system, arbitrary numbers can be represented with just the digits zero and one, the minus sign, and the period, or radix point.

An 8-bit word can represent the numbers from 0 to 255, including

                                                                 00000000   =      0

                                                                 00000001   =      1

                                                                 00101001   =    41

                                                                10000000    =  128

                                                                11111111    =  255

Sign-Magnitude Representation

• treat the most significant (leftmost) bit in the word as a sign bit. If the sign bit is 0, the number is positive; if the sign bit is 1, the number is negative.
• The simplest form of representation that employs a sign bit is the sign-magnitude representation. In an n-bit word, the rightmost n - 1 bits hold the magnitude of the integer.

• The general case can be expressed as follows:

• there are two representations of 0:

Twos Complement Representation

• uses the most significant bit as a sign bit, making it easy to test whether an integer is positive or negative.

• It differs from the use of the sign-magnitude representation in the way that the other bits are interpreted.

Characteristics of Twos Complement Representation and Arithmetic

• The number zero is identified as positive and therefore has a 0 sign bit and a magnitude of all 0s.
• the range of positive integers that may be represented is from 0 (all of the magnitude bits are 0) through (all of the magnitude bits are 1). Any larger number would require more bits.

• Equation above defines the twos complement representation for both positive and negative numbers.

Converting between Different Bit Lengths

• It is sometimes desirable to take an n-bit integer and store it in m bits, where m > n .
• In sign-magnitude notation, this is easily accomplished: simply move the sign bit to the new leftmost position and fill in with zeros.

  This procedure will not work for twos complement negative integers. Using the

                   same example,

• Instead, the rule for twos complement integers is to move the sign bit to the new leftmost position and fill in with copies of the sign bit. 
• For positive numbers, fill in with zeros, and 
• for negative numbers, fill in with ones. 
• This is called sign extension.

Fixed-Point Representation

• we mention that the representations discussed in this section are sometimes referred to as fixed point.This is because the radix point (binary point) is fixed and assumed to be to the right of the rightmost digit.