ROM and Programmable Logic Devices

ROM

• ROM stands for Read Only Memory.
• It has a fixed set of data that can be only read, but not written to.
• ROMs are suitable for implementing truth tables.
• In a ROM, you can embed multiple functionalities within a single ROM.
• ROMs are used in computer systems for initialization, because they retain data even when power is removed.
• A typical ROM can have 2^11 addresses (2048 addresses) with 8 outputs, totaling 2 KByte or 16 Kbits.

Programmable Logic Devices (PLD)

• PAL stands for Programmable Array Logic.
• PALs are smaller logic devices with a fixed OR array and a programmable AND array.
• PALs are easier to program because only the AND gates are programmable.
• PALs are less flexible than PLAs because they only have a programmable AND array.
• PLA stands for Programmable Logic Array.
• PLAs are more complex logic devices that have a programmable AND array and a programmable OR array.
• PLAs have a set of AND gates on each input and a set of OR gates on each output.
• PLAs are more flexible than PALs because they have programmable AND and OR arrays.
• Both PLAs and PALs implement combinational logic circuits.

Multiplexer (MUX)

• A MUX is a combinational logic circuit with multiple data inputs and a single output.
• It selects a specific input line based on the value of the select signal.
• A two-channel MUX has two data inputs and one output.
• An n-channel MUX has n data inputs and m select lines, where m is determined by the number of inputs (2^m = n).
• A 16-input MUX can be used to implement a 4-bit majority function.

De-multiplexer (DeMUX)

• A DeMUX is a combinational logic circuit that has a single data input and multiple output lines.
• It directs the data input to a specific output line based on the destination address.
• An n-output DeMUX with an m-bit destination address can select one of n output lines.
• It is the opposite of a MUX.

Encoder

• An encoder is a combinational logic circuit that has a set of input lines and a smaller set of output lines.
• It produces a unique binary output for each combination of inputs.
• Encoders can be implemented with individual input lines or an n-bit input bus.
• These can be used to convert a higher number of input bits to an encoded output with a smaller number of bits.

Decoder

• A decoder is a combinational logic circuit that transforms a binary input word into a unique output.
• Decoders have a set of input lines and a larger set of output lines.
• Each output is activated for a specific combination of inputs.
• They can be implemented with an input/output bus or with an expanded output bus.

Logic Minimization

• Logic minimization is a process of finding the simplest expression of a logic function.
• It can be done using Boolean algebra and K-maps, or using design tools like Verilog.
• The goal is to reduce the number of logic gates needed to implement the function.

Sum-of-Products (SOP)

• SOP is a way to represent logic functions as a sum of product terms.
• Each product term is a product of literals, where a literal is a variable or its complement.
• Minterms are a special type of product term where each variable appears exactly once in true or complemented form.
• The sum of minterms can be used to determine the SOP form of the logic function.
• The Σ symbol denotes the logical sum of minterms.

Product-of-Sums (POS)

• POS is a way to represent logic functions as a product of sum terms, where each sum term is the sum of literals.
• Maxterms are the complement of minterms, and can be used to express a logic function in POS form.
• The Π symbol denotes the logical product of maxterms.

K-Maps

• K-maps are a graphical method for simplifying logic functions.
• They are a visual representation of the truth table, where adjacent squares represent combinations that differ in a single variable.
• Combining adjacent squares containing 1's can simplify the function.

Don't Care & Can't Happen

• Don't care terms are input combinations where the corresponding output does not matter.
• They are denoted by X and can be treated as 1's or 0's to simplify the function.
• Can't happen terms are input combinations that are not possible in a given application.
• These are usually denoted by X and are not used in the simplification process.

Full Adder

• A full adder is a combinational logic circuit that adds three bits, including a carry-in bit.
• It produces a sum bit and a carry-out bit.
• It can be implemented using three half adders or other combinations of logic gates, including AND, OR, and XOR gates.

Half Adder

• A half adder is a combinational logic circuit that adds two bits.
• It produces a sum bit and a carry bit.
• It is a simpler version of the full adder, but it's not able to handle a carry-in bit.

ROM Example

• A ROM can be defined as a memory circuit that can only be read.
• ROMs are well-suited for implementing truth tables and multiple single-bit functions.
• ROMs are commonly used for system initialization and are non-volatile, meaning they retain data even when power is removed.
• A specific ROM structure would be 2^11 x 8 (2KByte or 16Kbits) when referring to a ROM with 11 address lines and 8 outputs.
• Implementing combinational logic using ROMs is possible, with a ROM of 2^K words by M bits able to implement M arbitrary functions of K variables (e.g., an 8-word by 5-bit ROM).

Muxes, De-muxes, Decoders & Encoders

• These are key combinational circuits used in digital design.
• A multiplexer (MUX) selects one of multiple input signals based on a selection address.
• A demultiplexer (DEMUX) routes a single input signal to one of multiple output lines based on a destination address.
• An encoder converts a set of inputs into a code (usually binary).
• A decoder converts a code into a set of outputs.

Combinational Circuits

• Combinational circuits, in contrast to sequential circuits, yield outputs dependent only on current inputs.
• Synthesis of a combinational circuit may comprise these steps:
  • Logic minimization: simplifying output functions using techniques like K-maps or Boolean algebra
  • Design tools: leveraging tools like Verilog for hardware description and design
  • Verification: ensuring design correctness through manual review or simulation

SOP & POS

• SOP (Sum-of-Products) form: a logic expression represented as the ORing of ANDed literals, simplifying to a sum of minterms where each minterm corresponds to a row with F=1 in a truth table.
• POS (Product-of-Sums) form: the ANDing of ORed literals, representing a function as the product of maxterms where each maxterm corresponds to a row with F=0 in a truth table.
• The duality principle allows for the alternative approach of considering all rows where f=0 and using maxterms instead of minterms (thus, POS over SOP form).
• The principle suggests both SOP and POS forms are equivalent in representing a logic function.

K-Maps

• K-Maps (Karnaugh Maps) represent a Boolean function visually, simplifying its representation in terms of SOP or POS.
• Each cell in a K-Map corresponds to a minterm.
• K-Maps can be implemented for two-variable, three-variable, four-variable, five-variable, and six-variable functions.
• K-Maps leverage the principle of logical adjacency, where cells adjacent to each other differ in only one variable.
• Circles are used to group adjacent 1s, representing product terms and their corresponding variables.
• Larger circles (powers of 2) indicate more variables can be eliminated for simplification.

Full Adder Implementation Using PLA

• A PLA (Programmable Logic Array) can implement a full adder (an arithmetic circuit that adds three bits).
• The full adder has three inputs: x, y, and carry-in (cin), and two outputs: sum (s) and carry-out (cout).
• The PLA would have product terms for each combination of inputs, and output terms based on specific Boolean expressions.
• Using a PLA leads to efficient implementation compared to using individual gates.

Read Only Memory (ROM)

• ROMs are capable of implementing a range of logic functions, including truth tables and multiple single-bit functions.
• ROMs are non-volatile memories that retain data even when power is removed.
• ROM size is defined by the number of address lines (inputs) and the number of output lines (outputs). For example, a ROM with 11 address lines and 8 outputs would have 2^11 x 8 = 2KByte (16Kb).

This quiz covers the fundamentals of ROM and Programmable Logic Devices. It includes details on their structures, functions, and differences, specifically focusing on Read Only Memory, Programmable Array Logic (PAL), and Programmable Logic Array (PLA). Test your knowledge and understanding of these essential computer components.