UNIT V

(SEQUENTIAL LOGIC DESIGN-1)

Basic Bistable Element

A combinational system is a system whose outputs depends only upon its current
inputs.
A sequential system is a system whose output depends on current input and past
history of inputs.
All systems we have looked at to date have been combinational systems.

Outputs depends on the current inputs and the system’s current state.

State” embodies all the information about the past needed to predict current output
based on current input.
State variables, one or more bits of information.
The state is a collection of state variables whose values at any one time contain all
the information about the past necessary to account for the circuit’s future behavior.
The simplest sequential circuit, no way to control its state.
Two states

One state variable, say, Q, two possible states

LOW HIGH
LOW
HIGH

LOW HIGH
 A bistable memory device is the generic term for the elements we are studying.

Latches and Flip flops

Latches and flip-flops (FFs) are the basic building blocks of sequential
circuits.

latch: bistable memory device with level sensitive triggering (no clock), watches all
of its inputs continuously and changes its outputs at any time, independent of a
clocking signal. 
flip-flop: bistable memory device with edge-triggering (with clock), samples its
inputs, and changes its output only at times determined by a clocking signal. 

• Here is an SR latch with a control input C.

• Notice the hierarchical design!

– The dotted blue box is the S’R’ latch.

– The additional NAND gates are simply used to generate the correct inputs
for the S’R’ latch.
• The control input acts just like an enable.

C S R S’ R’ Q
0 x x 1 1 No change
1 0 0 1 1 No change
1 0 1 1 0 0 (reset)
1 1 0 0 1 1 (set)
1 1 1 0 0 Avoid!

D latch

• Finally, a D latch is based on an S’R’ latch. The additional gates generate the S’
and R’ signals, based on inputs D (“data”) and C (“control”).
 – When C = 0, S’ and R’ are both 1, so the state Q does not change.

– When C = 1, the latch output Q will equal the input D.

• No more messing with one input for set and another input for reset!

C D Q
0 x No change
1 0 0
1 1 1

• Also, this latch has no “bad” input combinations to avoid. Any of the four
possible assignments to C and D are valid.
Flip-flops

• Here is the internal structure of a D flip-flop.

– The flip-flop inputs are C and D, and the outputs are Q and Q’.

– The D latch on the left is the master, while the SR latch on the right is
called the slave.
• Note the layout here.

– The flip-flop input D is connected directly to the master latch.

– The master latch output goes to the slave.

– The flip-flop outputs come directly from the slave latch.

MASTE
R SLAVE

D flip-flops when C=0

 • The D flip-flop’s control input C enables either the D latch or the SR latch, but
not both.
• When C = 0:

– The master latch is enabled, and it monitors the flip-flop input D.

Whenever D changes, the master’s output changes too.

– The slave is disabled, so the D latch output has no effect on it. Thus, the
slave just maintains the flip-flop’s current state.
D flip-flops when C=1

• As soon as C becomes 1,

– The master is disabled. Its output will be the last D input value seen just
before C became 1.

– Any subsequent changes to the D input while C = 1 have no effect on the

master latch, which is now disabled.

– The slave latch is enabled. Its state changes to reflect the master’s output,
which again is the D input value from right when C became 1.

Positive edge triggering

• This is called a positive edge-triggered flip-flop.

– The flip-flop output Q changes only after the positive edge of C.

– The change is based on the flip-flop input values that were present right at
the positive edge of the clock signal.
The D flip-flop’s behavior is similar to that of a D latch except for the positive edge-
triggered nature, which is not explicit in this table

C D Q
0 x No change
1 0 0 (reset)
1 1 1 (set)

Flip-flop variations

• We can make different versions of flip-flops based on the D flip-flop, just like
we made different latches based on the S’R’ latch.
 • A JK flip-flop has inputs that act like S and R, but the inputs JK=11 are used to
complement the flip-flop’s current state.

C J K Qnext
0 x x No change
1 0 0 No change
1 0 1 0 (reset)
1 1 0 1 (set)
1 1 1 Q’current

A T flip-flop can only maintain or complement its current state

C T Qnext
0 x No change
1 0 No change
1 1 Q’current

Characteristic equations

• We can also write characteristic equations, where the next state Q(t+1) is defined
in terms of the current state Q(t) and inputs.

D Q(t+1) Operation
0 0 Reset
Q(t+1) = D

1 1 Set

J K Q(t+1) Operation
0 0 Q(t) No change
0 1 0 Reset Q(t+1) = K’Q(t) + JQ’(t)

1 0 1 Set
1 1 Q’(t) Complement
 T Q(t+1) Operation
Q(t+1) = T’Q(t) +
0 Q(t) No change TQ’(t) = T Q(t)
1 Q’(t) Complement

Flip-Flop Vs. Latch

• The primary difference between a D flip-flop and D latch is the EN/CLOCK input.

• The flip-flop’s CLOCK input is edge sensitive, meaning the flip-flop’s output
changes on the edge (rising or falling) of the CLOCK input.

• The latch’s EN input is level sensitive, meaning the latch’s output changes on the
level (high or low) of the EN input.
Flip-Flops & Latches

74LS74

Dual Positive-Edge-Triggered D Flip-Flops with Preset, Clear, and Complementary

Outputs

74LS76

Dual Negative-Edge-Triggered J-K Flip-Flops with Preset, Clear, and Complementary

Outputs
74LS75 Quad Latch

74LS74: D Flip-Flop

74LS76: J/K Flip-Flop

74LS75: D Latch

Counters

• Counters are a specific type of sequential circuit.

• Like registers, the state, or the flip-flop values themselves, serves as the “output.”

• The output value increases by one on each clock cycle.

• After the largest value, the output “wraps around” back to 0.

• Using two bits, we’d get something like this:

Present State Next State

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

• Counters can act as simple clocks to keep track of “time.”

• You may need to record how many times something has happened.

– How many bits have been sent or received?

– How many steps have been performed in some computation?

• All processors contain a program counter, or PC.

– Programs consist of a list of instructions that are to be executed one after

another (for the most part).
– The PC keeps track of the instruction currently being executed.
 – The PC increments once on each clock cycle, and the next program
instruction is then executed.
Asynchronous Counters

• This counter is called asynchronous because not all flip flops are hooked to the
same clock.
• Look at the waveform of the output, Q, in the timing diagram. It resembles a
clock as well. If the period of the clock is T, then what is the period of Q, the
output of the flip flop? It's 2T!

• We have a way to create a clock that runs twice as slow. We feed the clock into a
T flip flop, where T is hardwired to 1. The output will be a clock who's period is
twice as long.
• If the clock has period T. Q0 has period 2T. Q1 period is 4T

• With n flip flops the period is 2n

3 bit asynchronous “ripple” counter using T flip flops

This is called as a ripple counter due to the way the FFs respond one after another in a
kind of rippling effect.

D Q0
Count enable EN
C

D Q1
C

D Q2
C

D Q3
C

Synchronous Counters

• To eliminate the "ripple" effects, use a common clock for each flip-flop and a
combinational circuit to generate the next state.
• For an up-counter, use an incrementer =>

• Internal details =>

.
• AND chain causes complement of a bit if all bits toward LSB from it equal 1
• Count Enable

• Forces all outputs of AND

chain to 0 to “hold” the state
• Carry Out

• Added as part of incrementer

• Connect to Count Enable of additional 4-bit counters to form larger counters

Design of Counters using digital ICs Asynchronous (Ripple) Counters

Clock is applied only to FF A. J and K are high in all FFs to toggle on every clock pulse.
Output of FF A is CLK of FF B and so forth.FF outputs D, C, B, and A are a 4 bit binary
number with D as the MSB.After the negative transistion of the 15th clock pulse the counter
recycles to 0000.This is an asynchronous counter because state is not changed in exact
synchronism with the clock.

Four-bit asynchronous (ripple) counter

Frequency division

The output frequency of each FF = the clock frequency of input / 2.

 The output frequency of the last FF = the clock frequency / MOD

Propagation Delay in Ripple Counters

Ripple counters are simple, but the cumulative propagation delay can cause

problems at high Frequencies. For proper operation the following apply:

Tclock ≥ N x tpd

Fmax= 1/(N x tpd)

Synchronous design methodology

Synchronous System Structure

Everything is clocked by the same, common clock

Typical synchronous-system timing

• Outputs have one complete clock period to propagate to

inputs.
• Must take into account flip-flop setup times at next clock
period.
Clock Skew

Clock signal may not reach all flip-flops simultaneously. Output changes of flip-flops
receiving “early” clock may reach D inputs of flip-flops with “late” clock too soon.

Reasons for slowness:

(a) wiring delays

(b) capacitance

(c) incorrect design

Clock-skew calculation

tffpd(min) + tcomb(min) - thold - tskew(max) > 0

First two terms are minimum time after clock edge that a D input changes

Hold time is earliest time that the input may change

Clock skew subtracts from the available hold-time margin

Compensating for clock skew:

– Longer flip-flop propagation delay

 – Explicit combinational delays
– Shorter (even negative) flip-flop hold times

Example of bad clock distribution

Gating the clock

Definitely a no-no

– Glitches possible if control signal (CLKEN) is generated by the same clock

– Excessive clock skew in any case.

Asynchronous inputs

Not all inputs are synchronized with the clock

Examples:

– Keystrokes

– Sensor inputs

– Data received from a network (transmitter has its own clock)

Inputs must be synchronized with the system clock before being

applied to a synchronous system.
 A simple synchronizer

Only one synchronizer per input

 Even worse

• Combinational delays to the two synchronizers are likely to be different.

way to do it

One synchronizer per input. Carefully locate the synchronization points in a sys
.But still a problem -- the synchronizer output may become metastable when setup and
hold time are not met.

Recommended synchronizer design

Hope that FF1 settles down before “META” is sampled.In this case, “SYNCIN” is valid
for almost a full clock period.Can calculate the probability of “synchronizer failure”
(FF1 still metastable when META sampled.
Impediments to synchronous design

• Clock skew

– Definition

The difference between arrival times of the clock at different memory devices

Example of clock skew

Influence of clock skew

Reduce the setup and hold time margins. For proper operation

tffpd(min) + tcomb(min) - thold - tskew(max) > 0

tsetup -tclk -tffpd(max) - tcomb(max) -

tskew(max) > 0

Reducing clock skew

proper buffering the clock

Better clock distribution .

Gating clock

Why not to gate the clock .

An acceptable way.
 (SEQUENTIAL LOGIC DESIGN-II)

MSI Registers

We will be discussing the 7400 register series which is a rather popular series of
registers.74ls373: This register is made up of 8 latches and to have a clock enable the
following structure is used:

When the enable signal is high although clocking is done, the values of the latches won’t
appear on the output lines. The following figure shows us how this enable line can be
used to select which one of the numerous registers’ value is to be set on the output bus:

Quote: Sometimes although a register may be able to store for instance 32 bits, only 16
communication lines are used that will load or send out data in two clock pulses.
74ls377: This register can be used where a bus is linked to the input of more than one
register and we want to be able to choose into which one, data will be loaded. Here we
have lost the ability to bus the outputs. In order to be able to bus the outputs we need to
use three state packages.

The reason we have either load control on a register package or three state control or not
both at the same time is that packages have a standard number of pins and thus both
can’t be on the package at the same time. Using outer three state packages or AND-OR
structures for bussing wastes a lot of space, thus using the components with three state
outputs are preferable, except when we want to use a component on two busses we will
have to use some form of extra hardware.

74ls374: This package is very similar to that of the 74ls373. The only particular
difference is that here we are allowed to feeding of outputs through combinational logic
back into the register and this is because we have flip flops instead of latches in the
74ls373:
Consider the following figure. We can add the contents of CReg and AReg, and put the
total in CReg using this circuit and activating the control signals selAReg, add and
selCReg. This will be done in two clock pulses and this is why the clock frequency must
be carefully decided (according to the longest path delay of the circuit).

The following structure shows how the clock enable of the registers actuall
As we mentioned before, gating must not be done on the clock, because it can
easily give this input hazards that we don’t want.

In system designs, such as the latter example, all control signals last from one rising edge
to the next one. Remember that the clock frequency is determined by the longest
common path.

Shift Register

Shift registers are a type of sequential logic circuit, mainly for storage of digital data.
They are a group of flip-flops connected in a chain so that the output from one flip-flop
becomes the input of the next flip-flop. Most of the registers possess no characteristic
internal sequence of states. All the flip-flops are driven by a common clock, and all are
set or reset simultaneously. In this chapter, the basic types of shift registers are studied,
such as Serial In - Serial Out, Serial In - Parallel Out, Parallel In - Serial Out, Parallel In
- Parallel Out, and bidirectional shift registers. A special form of counter - the shift
register counter, is also introduced.
Let’s observe the values of the flip flops in this shift register for the next couple of clock
pulse:

We are actually shifting our data to the right on every clock pulse.Shift registers are
widely used in parallel to serial converters which find applications in computer
communications.

74ls164: This package has two inputs and eight outputs. It can be useful in serial to
parallel conversion of data but not parallel to serial because there is no parallel loading.
We now want to see how universal shift registers are made. Consider the following
circuit:

In the last diagram, you can see that 4 modes of operation exist. When m1m0 is 00,
nothing
happens, that is the contents of the flip flops don’t change due to feed backing.
m1m0=01
puts us in right shift mode and 10 in left shift, whereas m1m0=11 gives us parallel load.
This structure can be used in a shift register to give us parallel to serial conversion
abilities.
74ls194: This package give us right and left shifting as well as parallel load in mode 11.
Serial In - Serial Out Shift Registers

A basic four-bit shift register can be constructed using four D flip-flops, as shown below.
The operation of the circuit is as follows. The register is first cleared, forcing all four
outputs to zero. The input data is then applied sequentially to the D input of the first flip-
flop on the left (FF0). During each clock pulse, one bit is transmitted from left to right.
Assume a data word to be 1001. The least significant bit of the data has to be shifted
through the register from FF0 to FF3.

In order to get the data out of the register, they must be shifted out serially. This can be
done destructively or non-destructively. For destructive readout, the original data is lost
and at the end of the read cycle, all flip-flops are reset to zero.
To avoid the loss of data, an arrangement for a non-destructive reading can be done by
adding two AND gates, an OR gate and an inverter to the system. The construction of
this circuit is shown below

The data is loaded to the register when the control line is HIGH (ie WRITE). The data
can be shifted out of the register when the control line is LOW (ie READ). This is shown
in the animation below

Serial In - Parallel Out Shift Registers

For this kind of register, data bits are entered serially in the same manner as discussed in
the last section. The difference is the way in which the data bits are taken out of the
register. Once the data are stored, each bit appears on its respective output line, and all
bits are available simultaneously. A construction of a four-bit serial in - parallel out
register is shown below.
 In the animation below, we can see how the four-bit binary number 1001 is
shifted to the Q outputs of the register.

Parallel In - Serial Out Shift Registers

A four-bit parallel in - serial out shift register is shown below. The circuit uses D flip-
flops and NAND gates for entering data (ie writing) to the register.

D0, D1, D2 and D3 are the parallel inputs, where D0 is the most significant bit and D3 is
the least significant bit. To write data in, the mode control line is taken to LOW and the
data is clocked in. The data can be shifted when the mode control line is HIGH as SHIFT
is active high. The register performs right shift operation on the application of a clock
pulse, as shown in the animation below.
Parallel In - Parallel Out Shift Register

For parallel in - parallel out shift registers, all data bits appear on the parallel outputs
immediately following the simultaneous entry of the data bits. The following circuit is a
four-bit parallel in - parallel out shift register constructed by D flip-flops.

The D's are the parallel inputs and the Q's are the parallel outputs. Once the register is
clocked, all the data at the D inputs appear at the corresponding Q outputs
simultaneously.

Bidirectional Shift Registers

The registers discussed so far involved only right shift operations. Each right shift
operation has the effect of successively dividing the binary number by two. If the
operation is reversed (left shift), this has the effect of multiplying the number by two.
With suitable gating arrangement a serial shift register can perform both operations. A
bidirectional, or reversible, shift register is one in which the data can be shift either left
or right. A four-bit bidirectional shift register using D flip-flops is shown below.
Here a set of NAND gates are configured as OR gates to select data inputs from the right
or left adjacent bistables, as selected by the LEFT/RIGHT control line. The animation
below performs right shift four times, then left shift four times. Notice the order of the
four output bits are not the same as the order of the original four input bits. They are
actually reversed!

Shift Register Counters

Two of the most common types of shift register counters are introduced here: the Ring
counter and the Johnson counter. They are basically shift registers with the serial outputs
connected back to the serial inputs in order to produce particular sequences. These
registers are classified as counters because they exhibit a specified sequence of states.

Ring Counters

A ring counter is basically a circulating shift register in which the output of the most
significant stage is fed back to the input of the least significant stage. The following is a
4-bit ring counter constructed from D flip-flops. The output of each stage is shifted into
the next stage on the positive edge of a clock pulse. If the CLEAR signal is high, all the
flip-flops except the first one FF0 are reset to 0. FF0 is preset to 1 instead
Since the count sequence has 4 distinct states, the counter can be considered as a mod-4
counter. Only 4 of the maximum 16 states are used, making ring counters very inefficient
in terms of state usage. But the major advantage of a ring counter over a binary counter
is that it
is self-decoding. No extra decoding circuit is needed to determine what state the counter
is in.

Johnson Counters

Johnson counters are a variation of standard ring counters, with the inverted output of the
last stage fed back to the input of the first stage. They are also known as twisted ring
counters. An n-stage Johnson counter yields a count sequence of length 2n, so it may be
considered to be a mod-2n counter. The circuit above shows a 4-bit Johnson counter. The
state sequence for the counter is given in the table as well as the animation on the left.
Again, the apparent disadvantage of this counter is that the maximum available states are
not fully utilized. Only eight of the sixteen states are being used. Beware that for both the
Ring and the Johnson counter must initially be forced into a valid state in the count
sequence because they operate on a subset of the available number of states. Otherwise,
the ideal sequence will not be followed.

Applications

Shift registers can be found in many applications. Here is a list of a few

To produce time delay

The serial in -serial out shift register can be used as a time delay device. The amount of
delay can be controlled by:
1. the number of stages in the register

2. the clock frequency

To simplify combinational logic

The ring counter technique can be effectively utilized to implement synchronous

sequential circuits. A major problem in the realization of sequential circuits is the
assignment of binary codes to the internal states of the circuit in order to reduce the
complexity of circuits required. By assigning one flip-flop to one internal state, it is
possible to simplify the combinational logic required to realize the complete sequential
circuit. When the circuit is in a particular state, the flip-flop corresponding to that state is
set to HIGH and all other flip-flops remain LOW.
To convert serial data to parallel data

A computer or microprocessor-based system commonly requires incoming data to be in

parallel format. But frequently, these systems must communicate with external devices
that send or receive serial data. So, serial-to-parallel conversion is required. As shown in
the previous sections, a serial in - parallel out register can achieve this.
Basic sequential Design steps

1. Step 1: From a word description, determine what needs to be stored in memory,

that is, what are the possible states.
2. Step 2: If necessary, code the inputs and outputs in binary.

3. Step 3: Derive a state table or state diagram to describe the behavior of the
system.
 4. Step 4: Use state reduction techniques to find a state table that produces the same
input/output behavior, but has fewer states.
5. Step 5: Choose a state assignment, that is, code the states in binary.
6. Step 6: Choose a flip flop type and derive the flip flop input maps or tables.

7. Step 7: Produce the logic equation and draw a block diagram (as in the case of
combinational systems).
Design of Modulus N Synchronous Counters

Asynchronous (Ripple) Counters

Asynchronous counters: the flip-flops do not change states at exactly the same time as
they do not have a common clock pulse.Also known as ripple counters, as the input
clock pulse “ripples” through the counter – cumulative delay is a drawback.n flip-flops a
MOD (modulus) 2n counter. (Note: A MOD-x counter cycles through x states.).Output of
the last flip-flop (MSB) divides the input clock frequency by the MOD number of the
counter, hence a counter is also a frequency divider.

Example:2-bit ripple binary counter.

Output of one flip-flop is connected to the clock input of the next more-significant flip-
flop.
 Example: 3-bit ripple binary counter

Propagation delays in an asynchronous (ripple-clocked) binary counter. If the

accumulated delay is greater than the clock pulse, some counter states may be
misrepresented

Example: 4-bit ripple binary counter (negative-edge triggered).

Asyn. Counters with MOD no. < 2n
States may be skipped resulting in a truncated sequence. Technique: force counter to
recycle before going through all of the states in the binary sequence.

Example: Given the following circuit, determine the counting sequence (and hence the
modulus no.)
MOD-6 counter produced by clearing (a MOD-8 binary counter) when count of six
(110) occurs.
Counting sequence of circuit (in CBA order).

Counter is a MOD-6 counter.

Exercise: How to construct an asynchronous MOD-5 counter? MOD-7
counter? MOD-12 counter?
The following is a MOD-? counter?

Decade counters (or BCD counters) are counters with 10 states (modulus-10) in
their sequence. They are commonly used in daily life (e.g.: utility meters,
odometers, etc.).

Design an asynchronous decade counter.

So far we are dealing with up counters. Down counters, on the other hand, count
downward from a maximum value to zero, and repeat.
Example: A 3-bit binary (MOD-23) down counter.

3-bit binary up counter

3-bit binary down

counter

Synchronous (Parallel) Counters

Synchronous (parallel) counters: the flip-flops are clocked at the same time by a
common clock
pulse. We can design these counters using the sequential logic design process.
Example: 2-bit synchronous binary counter (using T flip-flops, or JK flip-flops with
identical J,K inputs).

Example: 2-bit synchronous binary counter (using T flip-flops, or JK flip-flops with

identical J,K inputs).
Example: 3-bit synchronous binary counter (using T flip-flops, or JK flip-flops with
identical J, K inputs).

Note that in a binary counter, the nth bit (shown underlined) is always complemented
whenever

011…11 100…00 or
111…11 000…00

Hence, Xn is complemented whenever

Xn-1Xn-2 ... X1X0 = 11…11.

As a result, if T flip-flops are used,

then TXn = Xn-1 . Xn-2 . ... . X1 . X0 \

Counters with Parallel Load

Counters could be augmented with parallel load capability for the following
purposes:

To start at a different state 
 
To count a different sequence 


As more
sophisticated register with increment/decrement functionality. 

4-bit counter with parallel load.

Clear CP Load Count Function

0 X X X Clear to 0
1 X 0 0 No change
1 1 X Load inputs
1 0 1 Next state
(PROGRAMMABLE LOGIC DEVICES)

Introduction

There are two types of memories that are used in digital systems:

Random-access memory(RAM): perform both the write and read operations.

Read-only memory(ROM): perform only the read operation.

The read-only memory is a programmable logic device. Other such units are the
programmable logic array(PLA), the programmable array logic(PAL), and the field-
programmable gate array(FPGA).
Array logic

A typical programmable logic device may have hundreds to millions of gates

interconnected through hundreds to thousands of internal paths. In order to show the
internal logic diagram in a concise form, it is necessary to employ a special gate
symbology applicable to array logic.

Programmable Read Only Memory (PROM)

A block diagram of a ROM is shown below. It consists of k address inputs and n data
outputs. The number of words in a ROM is determined from the fact that k
address input lines are needed to specify 2k words.
Construction of ROM

Each output of the decoder represents a memory address. Each OR gate must be
considered as having 32 inputs. A 2k X n ROM will have an internal k X 2k decoder and
n OR gates.

Truth table of ROM

A programmable connection between to lines is logically equivalent to a switch that can

be altered to either be close or open .Intersection between two lines is sometimes called
a cross-point.

Programming the ROM

In Table 7-3, 0  no connection
1  connection
Address 3 = 10110010 is permanent storage using fuse link

Combinational circuit implementation

The internal operation of a ROM can be interpreted in two way: First, a memory unit
that contains a fixed pattern of stored words. Second, implements a combinational
circuit Fig. 7-11 may be considered as a combinational circuit with eight outputs, each
being a function of the five input variables.

Example

Design a combinational circuit using a ROM. The circuit accepts a 3-bit number
and generates an output binary number equal to the square of the input number.
Derive truth table first
Types of ROMs

The required paths in a ROM may be programmed in four different ways.

1. Mask programming: fabrication process

2. Read-only memory or PROM: blown fuse /fuse intact

3. Erasable PROM or EPROM: placed under a special ultraviolet light for a

given period of time will erase the pattern in ROM.

4. Electrically-erasable PROM(EEPROM): erased with an electrical signal

instead of ultraviolet light.
Combinational PLDs

A combinational PLD is an integrated circuit with programmable gates
divided into an AND array and an OR array to provide an AND-OR sum
of product implementation. 


PROM: fixed AND array constructed as a decoder and programmable
OR array. 

PAL: programmable AND array and fixed OR array. 

PLA: both the AND and OR arrays can be programmed.
Programmable Logic Array
Fig.7-14, the decoder in PROM is replaced by an array of AND gates that can be
programmed to generate any product term of the input variables. The product terms are
then connected to OR gates to provide the sum of products for the required Boolean
functions. The output is inverted when the XOR input is connected to 1 (since
x⊕1 = x’). The output doesn’t change and connect to 0 (since x⊕0 = x).
F1 = AB’+AC+A’BC’
F2 = (AC+BC)’
Programming Table

1. First: lists the product terms numerically

2. Second: specifies the required paths between inputs and AND gates

3. Third: specifies the paths between the AND and OR gates

4. For each output variable, we may have a T(ture) or C(complement) for

programming the XOR gate
Simplification of PLA
Careful investigation must be undertaken in order to reduce the number of distinct
product terms, PLA has a finite number of AND gates. Both the true and complement of
each function should be simplified to see which one can be expressed with fewer product
terms and which one provides product terms that are common to other functions.
Example

Implement the following two Boolean functions with a PLA: F1(A, B, C) = ∑(0, 1, 2,

4)

F2(A, B, C) = ∑(0, 5, 6, 7)
The two functions are simplified in the maps of Fig.7-15

PLA table by simplifying the function

Both the true and complement of the functions are simplified in sum of products. We can
find the same terms from the group terms of the functions of F1, F1’,F2 and F2’ which
will make the minimum terms.
F1 = (AB + AC + BC)’

F2 = AB + AC + A’B’C’
PLA
implementation
Programmable Array Logic

The PAL is a programmable logic device with a fixed OR array and a programmable
AND array.

When designing with a PAL, the Boolean functions must be simplified to fit into each
section. Unlike the PLA, a product term cannot be shared among two or more OR gates.
Therefore, each function can be simplified by itself without regard to common product
terms. The output terminals are sometimes driven by three-state buffers or inverters.
Example
PAL Table

z has four product terms, and we can replace by w with two product terms, this will
reduce the number of terms for z from four to three.

PAL implementation
Fuse map for example

Sequential Programmable Devices

Sequential programmable devices include both gates and flip-flops. There are several
types of sequential programmable devices, but the internal logic of these devices is too
complex to be shown here. We will describe three major types without going into their
detailed construction.
1. Sequential (or simple) Programmable Logic Device (SPLD)

2. Complex Programmable Logic Device (CPLD)

3. Field Programmable Gate Array (FPGA)

FPLS

The first programmable device developed to support sequential circuit implementation is

the field-programmable logic sequencer (FPLS).A typical FPLS is organized around a
PLA with several outputs driving flip-flops. The flip-flops are flexible in that they can be
programmed to operate as either JK or D type. The FPLS did not succeed commercially
because it has too many programmable connections.
SPLD

Each section of an SPLD is called a macrocell. A macrocell is a circuit that contains a

sum-of-products combinational logic function and an optional flip-flop. We will assume
an AND-OR sum of products but in practice, it can be any one of the two-level
implementation.

Macrocell

Fig.7-19 shows the logic of a basic macrocell. The AND-OR array is the same as in the
combinational PAL shown in Fig.7-16.

CPLD

A typical SPLD has from 8 to 10 macrocells within one IC package. All the flip-flops are
connected to the common CLK input and all three-state buffers are controlled by the EO
input. The design of a digital system using PLD often requires the connection of several
devices to produce the complete specification. For this type of application, it is more
economical to use a complex programmable logic device (CPLD). A CPLD is a
collection of individual PLDs on a single integrated circuit.
Fig.7-20 shows a general configuration of a CPLD. It consists of multiple PLDs
interconnected through a programmable switch matrix. 8 to 16 macrocell per PLD.

Gate Array

The basic component used in VLSI design is the gate array. A gate array consists of a
pattern of gates fabricated in an area of silicon that is repeated thousands of times until
the entire chip is covered with the gates. Arrays of one thousand to hundred thousand
gates are fabricated within a single IC chip depending on the technology used.
FPGA

FPGA is a VLSI circuit that can be programmed in the user’s location. A typical FPGA
logic block consists of look-up tables, multiplexers, gates, and flip-flops. Look-up table
is a truth table stored in a SRAM and provides the combinational circuit functions for the
logic block.

Differential of RAM and ROM in FPGA

The advantage of using RAM instead of ROM to store the truth table is that the table can
be programmed by writing into memory.

The disadvantage is that the memory is volatile and presents the need for the look-up
table content to be reloaded in the event that power is disrupted.
www.jntuworld.com || www.android.jntuworld.com || www.jwjobs.net || www.android.jwjobs.net

Comparison between PROM, PLA and

PAL
 (MEMORIES)

Introduction

There are two types of memories that are used in digital systems:

Random-access memory (RAM): perform both the write and read operations.

Read-only memory (ROM): perform only the read operation.

The read-only memory is a programmable logic device. Other such units are the
programmable logic array (PLA), the programmable array logic (PAL), and the field-
programmable gate array (FPGA).
Random-Access Memory

A memory unit stores binary information in groups of bits called words.

1 byte = 8 bits

1 word = 2 bytes

The communication between a memory and its environment is achieved through data
input and output lines, address selection lines, and control lines that specify the direction
of transfer.

Content of a memory

Each word in memory is assigned an identification number, called an address, starting

from 0 up to 2k-1, where k is the number of address lines. The number of words in a
memory with one of the letters K=210, M=220, or G=230.
64K = 216 2M = 221 4G = 232
Write and Read operations

Transferring a new word to be stored into memory:

1. Apply the binary address of the desired word to the address lines.

2. Apply the data bits that must be stored in memory to the data input
lines.

3. Activate the write input.

Transferring a stored word out of memory:

1. Apply the binary address of the desired word to the address lines.

2. Activate the read input.

Commercial memory sometimes provide the two control inputs for reading and writing
in a somewhat different configuration in table 7-1.

Timing Waveforms (write)

The access time and cycle time of the memory must be within a time equal to a fixed
number of CPU clock cycles. The memory enable and the read/write signals must be
activated after the signals in the address lines are stable to avoid destroying data in other
memory words. Enable and read/write signals must stay active for at least 50ns.
Timing Waveforms (read)

The CPU can transfer the data into one of its internal registers during the negative
transition of T3.

Types of memories

In random-access memory, the word locations may be thought of as being separated in

space, with each word occupying one particular location. In sequential-access memory,
the information stored in some medium is not immediately accessible, but is available
only certain intervals of time. A magnetic disk or tape unit is of this type. In a random-
access memory, the access time is always the same regardless of the particular location
of the word. In a sequential-access memory, the time it takes to access a word depends
on the position of the word with respect to the reading head position; therefore, the
access time is variable.

Static RAM

SRAM consists essentially of internal latches that store the binary information. The
stored information remains valid as long as power is applied to the unit. SRAM is easier
to use and has shorter read and write cycles. Low density, low capacity, high cost, high
speed, high power consumption.
Dynamic RAM

DRAM stores the binary information in the form of electric charges on capacitors. The
capacitors are provided inside the chip by MOS transistors. The capacitors tend to
discharge with time and must be periodically recharged by refreshing the dynamic
memory. DRAM offers reduced power consumption and larger storage capacity in a
single memory chip. High density, high capacity, low cost, low speed, low power
consumption.

Types of memories

Memory units that lose stored information when power is turned off are said to be
volatile. Both static and dynamic, are of this category since the binary cells need external
power to maintain the stored information. Nonvolatile memory, such as magnetic disk,
ROM, retains its stored information after removal of power.
Memory decoding

The equivalent logic of a binary cell that stores one bit of information is shown below.

Read/Write = 0, select = 1, input data to S-R latch

Read/Write = 1, select = 1, output data from S-R latch

*Refer SR latch with NOR gates

4X4 RAM

There is a need for decoding circuits to select the memory word specified by the input
address. During the read operation, the four bits of the selected word go through OR
gates to the output terminals. During the write operation, the data available in the input
lines are transferred into the four binary cells of the selected word. A memory with 2 k
words of n bits per word requires k address lines that go into kx2k decoder
Coincident decoding
A decoder with k inputs and 2k outputs requires 2k AND gates with k inputs per gate.
Two decoding in a two-dimensional selection scheme can reduce the number of inputs
per gate. 1K-word memory, instead of using a single 10X1024 decoder, we use two
5X32 decoders.
Address multiplexing

DRAMs typically have four times the density of SRAM. The cost per bit of DRAM
storage is three to four times less than SRAM. Another factor is lower power
requirement. Address multiplexing will reduce the number of pins in the IC package. In a
two-dimensional array, the address is applied in two parts at different times, with the row
address first and the column address second. Since the same set of pins is used for both
parts of the address, so can decrease the size of package significantly.

Address multiplexing for 64K DRAM

After a time equivalent to the settling time of the row selection, RAS goes back to the 1
level. Registers are used to store the addresses of the row and column. CAS must go
back to the 1 level before initialing another memory operation.

Internal Structure of ROM

An array of semiconductor devices

• diodes

• transistors

• fieldeffect
transistors 2N words by M bits
Data can be read but not changed

• (normal operating conditions)

• N input bits
• 2N words by M bits
• Implement M arbitrary functions of N
variables

Example 8 words by 5 bits:

ROM Memory Array

Alternate view

Each possible horizontal/vertical intersection indicates a possible connection. Or

gates at bottom output the word selected by the decoder (32 x 8)
Commercial ROM types

EPROM

Uses a floating gate for the FET at each bit location. User uses a programming voltage
that causes a temporary breakdown in the dielectric between the gate and the floating
gate to charge it. When programming voltage is removed the charge stays. How long?
EPROM manufacturers “guarantee” properly programmed bit has
70% of charge after 10 years. Use UV light to erase.
EEPROM

Electrically Erasable PROM. Like the EPROM only electrically erasable in circuit.
Many times referred to a “flash” programmable memory. Very slow on writes so not a
substitute for RAM.
General Block Diagram of ROM

Timing Diagram of ROM

• Access time from address – tAA

• Access time from chip select - tACS

 • Output-enable time - tOE

• Output-disable time - tOZ

• Output-hold time - tOH

R/W Memory

Memory to store and retrieve data when more than F/Fs. A

few types Static RAM – SRAM As long as power is

maintained data is held

SRAM

data storage
static RAM chip

Internal – an arrangement of storage structures

SRAM Timing

Timing for read

DRAM

Next step in memory is Synchronous SRAM which has a clocked interface for control,
address and data. Then comes DRAM – dynamic ram. In DRAM data is stored in a
semiconductor capicator.
DRAM Read

A read sees the bit line precharged to high. The word line is then activated. If cell stores
a 0 then there is a small drop on the voltage on the bit line. This is monitored by a sense
amp which provides the value stored. Value must be written back after the read.

DRAM Refresh

Charge stored leaks off over time. Must restore the values stored a 4096 row DRAM it
refresh every 64ms and thus each row every 15.6 usec. Larger DRAMs are banks of
smaller.

DDR SDRAM

Double data rate SDRAM. Double the data transfer rate of an SDRAM by transferring
on both edges of the clock. Access and setup times are the same as SRAM. Increased
data throughput as data is transferred in blocks.
DRAM structure and operation

Write operation

Setting the word line to 1.To store a 1, a HIGH voltage is placed on the bit line, which
charges the capacitor through the “on” transistor. To store a 0, a LOW voltage is placed
on the bit line, which discharges the capacitor through the “on” transistor
Read operation

The bit line is first precharged to a voltage halfway between HIGH and LOW. The word
line is set HIGH so that the precharged bit line is pulled slightly higher or slightly lower.
A sense amplifier detects this small change and recovers a 1 or 0 accordingly. Reading a
DRAM cell destroy the original voltage stored on the capacitor, the DRAM cell must be
written back the original data after reading.

Internal structure of a 64Kx1 DRAM

Multiplexed address inputs.

RAS_L: Row address strobe to store the higher order bits of the address into the row-
address register.
CAS_L: Column address strobe to store the lower order bits of the address into the
column-address register.
Row latches: the latches used to store data input/output from the memory array.

RAM Cells

Static RAM (SRAM):

• The basic element of a static RAM cell is the D-Latch.

• Data remains stored in the cell until it is intentionally modified.

• SRAM is fast (Access time: 1ns).

• SRAM needs more space on the semiconductor chip than DRAM.

– SRAM more expensive than DRAM

– SRAM needs more space than DRAM

• SRAM consumes power only when accessed.

• SRAM is used as a Cache

Dynamic RAM (DRAM):

• DRAM stores data in the form of electric charges in capacitors.

• Charges leak out, thus need to refresh data every few ms.

• DRAM is slow (Access time: 60ns).

• DRAM needs less space on the semiconductor chip than SRAM.

 – DRAM less expensive than SRAM

– DRAM needs less space than SRAM

• DRAM needs to be refreshed

• DRAM is used as the main memory

Types of semiconductor memory devices: Static RAM

Static RAM (also called SRAM)devices retain their data for as long as the DC power is
applied. The most common family of SRAM are the 61XXX, 62XXX or the CMOS
62CXXX series, where XXX indicates the memory capacity in Kbits. Some members of
this family are the following:

6116/6216 (2Kx8) 6164/6264 (8Kx8)

61256/62256 (32Kx8) 611024/621024 (128Kx8)

These series of SRAM devices are pin compatible with the 27XXX series of EPROMs,
with the difference that the WR signal is replaced by the programming voltage pin (Vpp)
on the EPROM. This allows a single socket on the PCB hold either a SRAM, during
system development, or an EPROM, after the operation of the program is verified to be
the expected one. Static RAM is fast with access times much less than 100ns. SRAM
chips with access times less than 10ns are often used as cache memory in computers.

DYNAMIC RAM CELL ARRAY

Asynchronous DRAM

This is the basic form, from which all others are derived. An asynchronous DRAM chip
has power connections, some number of address inputs (typically 12), and a few
(typically 1 or 4) bidirectional data lines. There are four active low control signals:
/RAS, the Row Address Strobe. The address inputs are captured on the falling edge of
/RAS, and select a row to open. The row is held open as long as /RAS is low. /CAS, the
Column Address Strobe. The address inputs are captured on the falling edge of /CAS,
and select a column from the currently open row to read or write. /WE, Write Enable.
This signal determines whether a given falling edge of /CAS is a read (if high) or write
(if low). If low, the data inputs are also captured on the falling edge of /CAS. /OE,
Output Enable. This is an additional signal that controls output to the data I/O pins. The
data pins are driven by the DRAM chip if /RAS and /CAS are low, and /WE is high, and
/OE is low. In many applications, /OE can be permanently connected low (output always
enabled), but it can be useful when connecting multiple memory chips in parallel.
DYNAMIC RAM

DRAM requires refreshing every 2 to 4 ms . Refreshing

occurs automatically during a read or write.

Internal circuitry takes care of refreshing cells that are not accessed over this interval.

– For a 256K X 1 DRAM with 256 rows, a refresh must occur every 15.6us
(4ms/256).
– For the 8086, a read or write occurs every 800ns .

– This allows 19 memory reads/writes per refresh or 5% of the time.

DRAM technologies

– EDO DRAM

– SDRAM

– DRDRAM

– DDR DRAM

Soft errors occur on DRAMs which often require ERROR DETECTION and/or
ERROR CORRECTION
A DRAM CONTROLLER is required for using DRAM

SYNCHRONOUS DYNAMIC RAM

In a synchronous DRAM, the control signals are synchronized with the system bus clock
and therefore with the microprocessor. It allows pipelined read/write operations
Double Data Rate (DDR) DRAM

An SDRAM type of memory where data are transferred on both the rising and the falling
clock edge, effectively doubling the transfer rate without increasing the clock
frequency.DDR-200 means a transfer rate of 200 million transfers per second, at a clock
rate of 100 MHz.DDR1 upto 400 MHz.DDR2 standard allows higher clock frequencies.

DRAM

Refresh circuit : storage decay in ms

DRAMs take up much less space, typically ¼ the silicon area of SRAMs or less (one
transistor and a capacitor)
DRAM Organization

Long rows to simplify refresh. Two new signals: RAS, CAS. Row Address Strobe,
Column Address Strobe replace Chip Select.

RAS, CAS Addressing

Even to read 1 bit, an entire 64-bit row is read! Separate addressing into two cycles:
Row Address, Column Address. Saves on package pins, speeds RAM access for
sequential bits!
Write cycle timing

RAM Refresh

Refresh Frequency :(4ms – 64ms)


4096 word RAM -- refresh each word once every 4 ms 
 
Assume 120ns memory access cycle 


This is one
refresh cycle every 976 ns (1 in 8 DRAM accesses)! 
 
But RAM is really organized into 64 rows 
 
This is one refresh cycle every 62.5 ms (1 in 500 DRAM
accesses) 


Large capacity DRAMs have 256 rows, refresh once every 16 ms
RAS-only Refresh (RAS cycling, no CAS cycling) 

External controller remembers last refreshed row  Some memory
chips maintain refresh row pointer

CAS before RAS refresh: if CAS goes low before RAS, then refresh

DRAM Technologies

Conventional DRAM 
 
Fast Page Mode (FPM) DRAM 
 
Extended Data Out (EDO) DRAM 


Synchronous DRAM (SDRAM)
 
Double Data Rate SDRAM (DDR SDRAM) 
 
Direct Rambus DRAM (DRDRAM) 


Synchronous-Link DRAM (SLDRAM) 
Fast Page Mode (FPM) DRAM

Sending the row address just once for many accesses to memory in locations near each
other, improving access time

Page mode
Burst modeaccess 
Memory is not read one byte at a time (32 or 64 bits at a time) 
 
Several consecutive chunks of memory 


“x-y-y-y” for four consecutive accesses 
Synchronous DRAM

Tied to the system clock

Burst mode

System timing : 5-1-1-1 


Internal interleaving New memory standard for modern
PCs Speed 
 
Access time: 10ns, 12ns,… 
 
MHz rating: 100 MHz, 133MHz 

Latency 
 
SDRAMs are still DRAMs 


5-1-1-1 (10ns means the second, third and fourth access
times) 2-clock and 4-clock Circuitry 

2-clock: 2 different DRAM chips on the module 
 
4-clock: 4 different DRAM chips
Packaging

Usually comes in DIMM packaging 


Buffered and unbuffered, 3.3 V and 5.0V 
Comparison of semiconductor memories