ZeePedia

LAST IN-FIRST OUT (LIFO) MEMORY

<< First In-First Out (FIFO) Memory
THE LOGIC BLOCK: Analogue to Digital Conversion, Logic Element, Look-Up Table >>
img
CS302 - Digital Logic & Design
Lesson No. 43
LAST IN-FIRST OUT (LIFO) MEMORY
Last In-First Out Memory finds applications in computer systems where it is used to
implement a stack. The operation of a stack can be understood by viewing a stack of plates. In
a stack of plates the first plate is placed at the bottom the next plate placed is placed on the
top, the third plate is placed on the top of the second plate and so on. Plates are removed one
at a time from the top of the stack, thus the last plate placed on the stack top is the first to be
removed followed by the second plate and then the plate at the bottom which was placed first.
In a register based LIFO memory implementation a set of Parallel In/Parallel Out registers are
connected together such that data is pushed down or pulled up when data is stored or
removed from the memory respectively. Figure 43.1.
Stack Top
Register 1
Register 2
Stack
Register 3
Control
Register 4
Register 5
Figure 43.1
A five byte LIFO Memory
In the LIFO memory shown, the first 8-bit data value is stored in the first register Reg.
1. To store the next value, the first value stored in Reg. 1 is pushed down (shifted) to the
second register Reg. 2. The second 8-bit data value is written into the first register Reg. 1. The
third data value can only be stored when both the previous values are pushed (shifted) down
to the Registers 2 and 3. A maximum of five, 8-bit data values can be stored in the LIFO
register. The fifth and the last value stored in the first register Reg. 1 is the first value to be
read out. The remaining four values in the memory are pulled (shifted) up. At any time new
data can be added to the LIFO memory or the stored data can be read out.
Shift Register based Stack implementation finds use in specialized digital systems. A
practical way to implement the program stack which a program under execution uses to
access variables is by means of the RAM memory. The stack is known as a RAM Stack. A
special purpose register known as the `Stack Pointer Register' stores the address of the top of
the stack, a reserved area in the RAM memory. As data values are written or read from the
RAM stack, the Stack Pointer Register increments or decrements its contents always pointing
to the stack top. Figure 43.2.
429
img
CS302 - Digital Logic & Design
Initially, the Stack Pointer Register has the contents 0, which is address of memory
location of the stack. A value `7' is stored in the Stack by writing it to memory location 0
pointed to by the Stack Pointer Register. To store the next value 4 in the stack the contents of
the Stack Register are incremented so that the next vacant location in the Stack is accessed.
The new data value 4 is written at the new location. Similarly, data values 9 and 8 are stored in
the next two consecutive locations in the Stack. The Stack Pointer Register points to the Stack
Top (location 3) which has the data value 8 stored. A data value can be read from the Stack
Top by reading the data value from the address pointed to by the Stack Pointer Register. After
reading the data value the contents of the Stack Pointer Register are decremented to point to
the new Stack Top.
Locations
3
4
Stack
8
3
Pointer
Register
2
9
1
4
7
0
Figure 43.2
Memory Based Stack
Memory Expansion
Digital systems require different amounts of memory in the form of RAM and ROM
Memory depending upon specific applications. A computer requires large amounts of RAM
memory to store multiple application programs, data and the operating system. In a computer,
part of the RAM is reserved to support the Video Memory, Stack and I/O buffers. The ROM
used by a computer is relatively very small as it stores few bytes of code used to Boot the
Computer system on power up. Micro-controller based digital system designed for specific
applications do not have large memory requirement, in fact the total memory requirement of
such micro-controller systems is met by on-board RAM and ROM having a total storage
capacity of few hundred of kilobytes. Computer and Digital systems have the capability to
allow RAM memory to be expanded as the needed arises by inserting extra memory in
dedicated memory sockets on the computer motherboard.
The total amount of memory that is supported by any digital system depends upon the
size of the address bus of the microprocessor or a micro-controller. A microprocessor having
an address bus of 16 bits can generate 216 or 65536 unique addresses to access 65536
locations which allows either a single 65536 location RAM or a combination of RAM and ROM
totalling 65536 memory locations to be connected to the microprocessor. It is also possible to
initially have a 32768 location RAM connected to the microprocessor with the remaining 32768
address locations unoccupied allowing the microprocessor to execute a program that can be
stored in 32768 locations. The remaining memory space can be utilized latter by connecting
430
img
CS302 - Digital Logic & Design
another 32768 location RAM. Microprocessors used in computer systems have memory
spaces of the order of 232 and larger.
The data unit size accessed by a microprocessor when it issues an address to either
read or write from or to a memory also depends upon the microprocessor architecture more
specifically the number of the data lines. A microprocessor having an 8-bit data bus can
access a byte of information from any unique memory location. A microprocessor having a 16-
bit data bus allows two bytes to be accessed from a memory location. Practically,
microprocessors used in computer systems have up to 64 bit wide data buses allowing up to 8
bytes of data to be accessed simultaneously. A microprocessor that accesses 64-bits of data
simultaneously requires RAM to be organized in such a way that allows 8 bytes of data to be
accessed when ever any unique address is selected. On the other hand a microprocessor
having a data bus of only 8-bits requires RAM that allows only a single byte of data to be
accessed when ever any single address location is selected.
The total memory requirement of a computer or digital system is determined by the
size of the address and data bus of a microprocessor. Microprocessors which have small
address bus and a data bus have a small memory space. Microprocessors which have wide
address and data buses have very large memory spaces which are rarely fully occupied by
RAM and ROM devices.
Memory, both RAM and ROM are implemented in fixed data unit sizes of 1, 4 or 8 bits.
Similarly, these memory devices are implemented having sizes in terms of total addressable
locations which are restricted to address ranges between few hundred kilobytes to megabytes.
The memories that are available in fixed sizes have to be connected together to form larger
memories having appropriate data unit sizes and total number of addressable locations to fulfil
the memory space requirements of a digital or computer system. Another important aspect of
the RAM and ROM memories that are manufactured are the addresses of each memory
location. For example, two 32Kbyte RAM chips have 215 locations each. The first addressable
locations in both the RAM chips have an address 0. Similarly, the second and third locations in
both the memory chips have addresses 1 and 2 respectively. If the two RAM chips are
connected together to form a 64 Kbyte RAM then one of 32Kbyte memory chips should
respond to the address between 0 and 32767 and the other 32Kbyte memory chip should
respond to the address 32768 and 65535. The two memory chips have bases address 0 and
32768 respectively.
Memory Map
The Memory Map of any digital system specifies the total memory space that can be
accessed by the microprocessor and the distribution of the total addressable space amongst
RAM, ROM, stack and buffers. The memory map shown in the figure shows the division of 1
MByte of addressable space into ROM, RAM for storage of data, RAM for storage of program
code, vacant space which can be used in the future and a stack. Figure 43.3. The 1 MByte
address space is divided into 16 equal blocks of 64 Kbytes each. The first 64Kbyte block
having a base address 00000H is reserved for ROM memory. A maximum 64Kbyte sized
ROM chip can be connected in the memory space. If a smaller ROM chip is connected in the
memory space, the remaining unoccupied addresses can be utilized in future to expand the
ROM memory by connecting extra ROM chips. The next block of 64KByte is reserved for
storage of data by connecting a 64KByte RAM chip. The base address of the block is 10000H.
The third block of 64KByte is used to store program code by connecting a 64KByte RAM chip.
The base address of the third block is 20000H. The last 64KByte block having a base address
of F0000H is reserved for implementing the stack. A 64Kbyte RAM chip is connected at the
431
img
CS302 - Digital Logic & Design
base address F0000H to support the Stack. Twelve blocks starting from base address 30000H
are left unoccupied. These blocks can be used to connect additional RAM to increase the total
amount of Memory RAM.
Figure 43.3
1 MByte Memory Map
Expanding Data Unit Size
Memories are implemented in 1, 4 and 8 bit data unit sizes. A processor that accesses
16-bit of data at each address location requires memory to be connected such that each
address location allows access to 16-bits of data. In the example shown, two 4 K byte RAM
chips are connected together to form a 4K Word (16-bit) memory or 8K Byte memory. Figure
43.4. A 4KByte RAM memory chip has A0 ­ A11 address lines to address 4K locations. The
address lines of both the 4KByte RAM chips are connected together so that the same address
is used to select identical memory locations in both the memory chips. Each 4KByte RAM chip
has 8 data lines to allow access to 8-bits of data at each memory location. The address lines
of both the memory chips are kept separate. The memory chip shown on the right stores the
least significant byte of the 16-bit data and the chip on the left stores the most significant byte
of the 16-bit data value. The least significant byte is accessed through data lines D0 ­ D7 and
the most significant byte is accessed through data lines D8 ­ D15. The R / W control line of
both the memory chips are also connected together so that a word (16-bit) value is read or
written to the selected location. The CS pins of both the chips are also connected together so
that both the memory chips are selected simultaneously when ever a read or write memory
operation is carried out.
432
img
CS302 - Digital Logic & Design
Figure 43.4
Implementing 4K Word RAM using two 4K Byte RAM chips
Expanding Memory Locations
The two 4KByte memory chips can be connected together to form an 8 KByte memory
thereby doubling the total number of memory locations. Addressing 8KByte of memory
requires 13 address lines. The first 12 address lines A0 ­ A11 of the two memory chips are
connected together, the data lines of both the chips are also connected together. Since the
data lines are shared, therefore at any given instant data can be read or written to one of the
two chips. Selection of either of the two memory chips is done through the CS signal. The first
memory chip which maps the address range from 0 to 4K is selected when the CS signal is
set to logic 0. The second memory chip which maps the memory range 4K to 8K is connected
to the CS through a NOT gate therefore it is selected when the signal is set to logic high. The
CS line is connected to the A12 address line which selects the first memory chip when it is
logic 0, the second memory chip is selected when the A12 signal is set to logic 1. Figure 43.5.
433
img
CS302 - Digital Logic & Design
Figure 43.5
Implementing 8K Byte RAM using two 4K Byte RAM chips
Expanding Data Unit Size and Memory Locations
Memory chips can be connected together in different manners to increase the total size
(locations) or the size of the data unit stored. Four 4K Byte chips can be connected together to
implement an 8K x Word memory. Figure 43.6. Chips A and B are connected to provide 4K x
16 bit of memory space and the chips C and D are connected to provide another 4K x 16 bit of
memory space. The RAM chips A and B are selected simultaneously when A12 address line is
set to logic 0. The RAM chips C and D are selected simultaneously when A12 address line is
set to logic 1. The R / W control line is connected to all the four RAM chips. RAM chips A and
C provide access to upper byte of the 16-bit data and RAM chips B and D provide access to
the lower byte of the 16-bit data.
434
img
CS302 - Digital Logic & Design
4K x 8
4K x 8
RAM
RAM
A0 - A11
A
B
A12
4K x 8
4K x 8
RAM
RAM
C
D
D8 - D15
D0 - D7
Figure 43.6
An 8K x 16 RAM implemented using four 4K x 8 memory chips
Address Decoders
All memory chips have the first location identified by address zero. The next location
has the address one and successive memory locations have addresses assigned in an
ascending order. When these memory chips are connected to a microprocessor at the
specified location represented in the memory map the memory chips are connected such that
the memory chip has the start address specified by a Base Address and the successive
memory locations are selected by ascending addresses with respect to the Base address.
Thus the first memory location is accessed by the Base Address and the next successive
location is accessed by Base Address +1 and so on. In the 8KByte memory implemented in
figure 43.5 the first 4KByte memory has the base address 0000H and the second 4KByte
memory chip has a base address 1000H. A memory chip is connected at the Base Address by
selecting it when the specified Base Address is generated by the microprocessor. An Address
Decoder detects the generated Base Address and selects the desired memory chip.
Three 4KByte memory chips are shown to be connected at Base Addresses 0000H,
1000H and 2000H respectively. Figure 43.7. A 2 x 4 decoder is used for address decoding.
The most significant address lines A12 and A13 are connected to the two input lines of the 2 x 4
decoder. When both the address lines are logic 0, the base address is
0000 and the first 4K memory chip RAM1 is selected. When A12 address line is logic 1 it
indicates the Base Address 4K which selects the second 4K memory chip RAM2. When
address line A13 is set to logic 1 it indicates a Base Address 8K selecting the third 4K memory
chip RAM3.
435
img
CS302 - Digital Logic & Design
Figure 43.7a Address Decoding of three 4KByte memory chips
The memory map of the memory configuration shown in figure 43.7a is shown in figure
43.7b.
A13
A12
Output
0
0
CS0
4K RAM0
0
1
CS1
1
0
CS2
4K RAM1
1
1
CS3
4K RAM2
Vacant
Figure 43.7b Memory Map for the three 4K RAM chips
Memory Decoders can be implemented in different ways. The simplest method to
implement is by using logic gates. The other method is to use m x n decoders. Both decoders
are shown. Figure 43.8 and 43.9. In the logic based address decoder a combination of OR,
436
img
CS302 - Digital Logic & Design
NAND and NOT gates are used to select four memory devices at Base Addresses 000H,
200H, 400H, 600H respectively. A 2 x 4 Decoder is used to decode the same memory space.
A 3 x 8 Decoder divides the 64K memory space into eight equal blocks of 8K.
Figure 43.8
Logic Gate based Address Decoder
Figure 43.9
2 x 4 and 3 x 8 Decoder based Address Decoders
Introduction to FPGAs
Programmable Logic Devices are based on a programmable AND-OR gate array which
are programmed to implement any function in the SOP form. The output of the AND-OR gate
array can be directly used as a combinational circuit output. Provision is there to connect the
output of the AND-OR gate array to a D-flip-flop for Sequential circuit operation. An FPGA is a
more flexible device than PLDs as instead of a single AND-OR gate array, an FPGA device
contains multiple logic blocks that can be individually programmed to perform different
functions. Each Logic Block is connected to other blocks through row and column
interconnects that can be programmed to connect any Logic block to another. The Logic
blocks are connected to the outside world through programmable I/O blocks. The block
diagram of a Field Programmable Gate Array FPGA is shown. Figure 43.10.
437
img
CS302 - Digital Logic & Design
Input/Output
Block
I/O
I/O
I/O
I/O
Logic
Logic
Logic
Logic
Block
Block
Block
Block
I/O
I/O
Logic
Logic
Logic
Logic
Block
Block
Block
Block
I/O
I/O
Row
Interconnect
Column
Interconnect
I/O
I/O
Logic
Logic
Logic
Logic
Block
Block
Block
Block
I/O
I/O
I/O
I/O
Figure 43.10 Block diagram of a FPA
438
Table of Contents:
  1. AN OVERVIEW & NUMBER SYSTEMS
  2. Binary to Decimal to Binary conversion, Binary Arithmetic, 1’s & 2’s complement
  3. Range of Numbers and Overflow, Floating-Point, Hexadecimal Numbers
  4. Octal Numbers, Octal to Binary Decimal to Octal Conversion
  5. LOGIC GATES: AND Gate, OR Gate, NOT Gate, NAND Gate
  6. AND OR NAND XOR XNOR Gate Implementation and Applications
  7. DC Supply Voltage, TTL Logic Levels, Noise Margin, Power Dissipation
  8. Boolean Addition, Multiplication, Commutative Law, Associative Law, Distributive Law, Demorgan’s Theorems
  9. Simplification of Boolean Expression, Standard POS form, Minterms and Maxterms
  10. KARNAUGH MAP, Mapping a non-standard SOP Expression
  11. Converting between POS and SOP using the K-map
  12. COMPARATOR: Quine-McCluskey Simplification Method
  13. ODD-PRIME NUMBER DETECTOR, Combinational Circuit Implementation
  14. IMPLEMENTATION OF AN ODD-PARITY GENERATOR CIRCUIT
  15. BCD ADDER: 2-digit BCD Adder, A 4-bit Adder Subtracter Unit
  16. 16-BIT ALU, MSI 4-bit Comparator, Decoders
  17. BCD to 7-Segment Decoder, Decimal-to-BCD Encoder
  18. 2-INPUT 4-BIT MULTIPLEXER, 8, 16-Input Multiplexer, Logic Function Generator
  19. Applications of Demultiplexer, PROM, PLA, PAL, GAL
  20. OLMC Combinational Mode, Tri-State Buffers, The GAL16V8, Introduction to ABEL
  21. OLMC for GAL16V8, Tri-state Buffer and OLMC output pin
  22. Implementation of Quad MUX, Latches and Flip-Flops
  23. APPLICATION OF S-R LATCH, Edge-Triggered D Flip-Flop, J-K Flip-flop
  24. Data Storage using D-flip-flop, Synchronizing Asynchronous inputs using D flip-flop
  25. Dual Positive-Edge triggered D flip-flop, J-K flip-flop, Master-Slave Flip-Flops
  26. THE 555 TIMER: Race Conditions, Asynchronous, Ripple Counters
  27. Down Counter with truncated sequence, 4-bit Synchronous Decade Counter
  28. Mod-n Synchronous Counter, Cascading Counters, Up-Down Counter
  29. Integrated Circuit Up Down Decade Counter Design and Applications
  30. DIGITAL CLOCK: Clocked Synchronous State Machines
  31. NEXT-STATE TABLE: Flip-flop Transition Table, Karnaugh Maps
  32. D FLIP-FLOP BASED IMPLEMENTATION
  33. Moore Machine State Diagram, Mealy Machine State Diagram, Karnaugh Maps
  34. SHIFT REGISTERS: Serial In/Shift Left,Right/Serial Out Operation
  35. APPLICATIONS OF SHIFT REGISTERS: Serial-to-Parallel Converter
  36. Elevator Control System: Elevator State Diagram, State Table, Input and Output Signals, Input Latches
  37. Traffic Signal Control System: Switching of Traffic Lights, Inputs and Outputs, State Machine
  38. Traffic Signal Control System: EQUATION DEFINITION
  39. Memory Organization, Capacity, Density, Signals and Basic Operations, Read, Write, Address, data Signals
  40. Memory Read, Write Cycle, Synchronous Burst SRAM, Dynamic RAM
  41. Burst, Distributed Refresh, Types of DRAMs, ROM Read-Only Memory, Mask ROM
  42. First In-First Out (FIFO) Memory
  43. LAST IN-FIRST OUT (LIFO) MEMORY
  44. THE LOGIC BLOCK: Analogue to Digital Conversion, Logic Element, Look-Up Table
  45. SUCCESSIVE –APPROXIMATION ANALOGUE TO DIGITAL CONVERTER