Unit 6 - Practice Quiz

ROM stands for Read-Only Memory. It is a type of non-volatile memory where data is permanently stored and cannot be easily altered or removed, primarily used for firmware.

RAM (Random-Access Memory), which includes both SRAM and DRAM, is volatile. It requires constant power to maintain the stored information.

DRAM stores each bit of data in a small capacitor, which leaks charge over time. Therefore, it must be periodically refreshed to retain its data.

PAL stands for Programmable Array Logic. It is a type of PLD with a programmable AND plane and a fixed OR plane.

A PLA is characterized by having both a programmable AND array and a programmable OR array, which makes it more flexible than a PAL.

FPGA stands for Field-Programmable Gate Array. It is an integrated circuit that can be configured by the user after manufacturing to implement custom digital logic.

Sequential PLDs incorporate memory elements, such as flip-flops or registers, along with combinational logic gates. This allows them to store state information and implement sequential circuits like counters and state machines.

EPROM stands for Erasable Programmable Read-Only Memory. It has a transparent quartz window on the package that allows UV light to pass through and erase the data, allowing it to be reprogrammed.

SRAM uses a bistable latching circuitry, typically a flip-flop, to store each bit. This is why it does not need refreshing but is larger and more expensive per bit than DRAM.

The defining characteristic of a PAL (Programmable Array Logic) is its structure, which features a programmable AND plane and a fixed OR plane.

SRAM (Static RAM) is much faster than DRAM because it doesn't have refresh cycles. Its high speed makes it ideal for use as cache memory to bridge the speed gap between the CPU and slower main memory (DRAM).

The BIOS must be retained when the computer is powered off, so it is stored in non-volatile memory. Modern systems use Flash memory (a type of EEPROM) for this purpose.

Because a PLA has both a programmable AND plane and a programmable OR plane, it offers greater flexibility in implementing logic functions compared to a PAL's fixed OR plane.

An FPGA consists of an array of Configurable Logic Blocks (CLBs) or Logic Elements (LEs). These blocks typically contain look-up tables (LUTs), flip-flops, and multiplexers, and can be programmed to perform a desired logic function.

The registers (usually D-type flip-flops) at the outputs of a sequential PLD are used to hold the current state of a sequential machine. The next state is determined by the inputs and the current state on each clock edge.

The two primary categories of semiconductor read/write memory are SRAM (Static RAM) and DRAM (Dynamic RAM). They are both volatile but differ in their underlying technology, speed, and cost.

Non-volatile memory is a type of computer memory that can retrieve stored information even after having been power cycled (turned off and back on). ROM is a primary example.

The structure of a PAL, with its AND gates feeding into OR gates, is perfectly suited for implementing logic functions directly in the Sum-of-Products (SOP) form.

CPLD stands for Complex Programmable Logic Device. It is an integrated circuit that is more complex than a PAL but less complex than an FPGA, often containing multiple macrocells with sequential logic capabilities.

Mask ROM is programmed with the desired data during the semiconductor fabrication process using a specific 'mask'. Once it is made, the data cannot be altered, making it suitable for high-volume, fixed-function products.

To get the required width of 16 bits from 8-bit chips, you need 16/8 = 2 chips in parallel for each bank. To get the required depth of 64K from 16K chips, you need 64K/16K = 4 banks. Total chips = 2 (for width) * 4 (for depth) = 8 chips. To select one of the 4 banks, you need a decoder that can select from 4 unique locations, which requires address lines.

The memory address 110 corresponds to the input combination A=1, B=1, C=0. This is the decimal value 6. Since the function is defined by the sum of minterms , the output for minterm 6 should be '1'. Therefore, the data bit stored at address 110 will be 1.

The PAL's OR gate for each output can sum up to 3 product terms (from the 3 AND gates). The function has exactly 3 product terms. The function has 2 product terms. Since both functions require 3 or fewer product terms, they can both be implemented on this PAL architecture.

In a PLA, product terms can be shared between different output functions. The required product terms are: (for both and ), (for ), and (for ). Since is shared, the total number of unique product terms needed is 3.

FPGAs use a 'sea-of-gates' (or more accurately, sea-of-LUTs) architecture. Each Configurable Logic Block (CLB) contains one or more Look-Up Tables (LUTs) and flip-flops. This distributed, fine-grained structure provides a very high ratio of registers to logic, making them ideal for pipelined and other register-heavy designs. CPLDs, in contrast, have registers only in the macrocells at the edge of their logic blocks, a much coarser-grained architecture.

The entire memory must be refreshed within the 64 ms period. Since there are 8192 rows, the refresh controller must initiate a refresh operation for each row within this time. The average time between these operations is the total period divided by the number of rows: Time = 64 ms / 8192 = seconds, or 7.81 µs.

The OLMC is a key feature of sequential and complex PLDs. It sits between the OR-plane and the output pin. Its main purpose is to provide flexibility by allowing the user to select whether the output should be the direct combinational result of the sum-of-products logic or if it should be passed through a flip-flop to create a registered, synchronous output. It often also allows for output polarity control and feedback to the AND-array.

For prototyping, an electrically erasable and programmable memory like EEPROM or Flash is ideal because it allows the firmware to be changed easily without special equipment. For high-volume mass production, a Mask ROM (MROM) is the most cost-effective solution because the data is permanently patterned into the silicon during manufacturing, resulting in a very low per-unit cost once the initial setup (mask) cost is paid.

This is the fundamental distinction. In a PAL, the user can define the product terms (AND logic), but the way these product terms are summed for each output (OR logic) is fixed. In a PLA, the user can define not only the product terms but also which product terms are summed for each individual output, offering greater flexibility at the cost of more complexity and potentially slower speed.

The structural simplicity of the DRAM cell is the key to its high density. The 1-transistor, 1-capacitor (1T1C) design takes up significantly less silicon area than the 6-transistor (6T) flip-flop latch used in a standard SRAM cell. This allows many more DRAM cells to be packed into the same amount of space.

A function with more inputs than a single LUT can handle is implemented by breaking it down. For a 6-input function, a common method is to use four 4-input LUTs to compute parts of the function and then two 2-input LUTs (or MUXes) to combine those results, and one final MUX to get the final result. More efficiently, a 6-input function can be implemented with two 4-input LUTs feeding into a 2:1 MUX (if one of the inputs is used as the MUX select line).

A BCD (Binary Coded Decimal) input consists of 4 bits to represent decimal digits 0 through 9. A standard 7-segment display has 7 segments (a, b, c, d, e, f, g) that need to be controlled. Therefore, the decoder circuit must have 4 inputs and 7 outputs. The number of product terms (P) would depend on the logic simplification of the 7 output functions.

A synchronous counter is a state machine, which requires memory elements (flip-flops) to store its current state. Sequential PLDs are specifically designed for this purpose, as they integrate programmable logic (AND-OR arrays) with registers (flip-flops) in their macrocells. A simple PAL, PLA, or ROM lacks these integrated registers and cannot directly implement a state machine.

SRAM-based FPGAs store their configuration in SRAM (Static RAM) cells. SRAM is volatile memory, meaning its contents are lost when power is removed. Therefore, every time an SRAM-based FPGA is powered on, its configuration bitstream must be reloaded from a non-volatile source, such as an external SPI flash memory chip or a host processor.

The Chip Enable (CE) signal is used to select the entire chip. If CE is inactive, the chip is typically in a low-power standby mode and will not respond. The Output Enable (OE) signal controls the output buffers. When OE is active (and CE is also active), the data from the selected memory location is driven onto the data bus. Deactivating OE puts the data bus pins in a high-impedance state, allowing multiple devices to share the bus.

First, the function must be minimized using Boolean algebra or a K-map. The function is . The terms and can be combined: . So, the minimized function is . This minimized form has two product terms. Therefore, it would require 2 AND gates in the PAL's AND-plane connected to one OR gate.

The key advantage of a PLA's architecture is its flexibility. Because both the AND and OR arrays are programmable, a product term generated in the AND array can be routed to any of the OR gates. This allows for efficient sharing and distribution of logic resources, which can be beneficial when some output functions are very complex (requiring many product terms) while others are simple. In a PAL, each output's OR gate is fed by a fixed, dedicated set of AND gates.

CPU cache needs to operate at speeds comparable to the CPU itself to be effective. SRAM offers very low latency (fast access times) because of its transistor-latch design, making it ideal for cache. However, this design makes it expensive and less dense. Main memory needs large capacity at a reasonable cost, which is where DRAM excels due to its simple, dense cell structure, even though it is slower and requires refreshing.

An FPGA's functionality comes from two key components: the logic elements (CLBs/LUTs) that implement logic functions, and the routing resources that connect them. The programmable interconnect matrix consists of wires and programmable switches that allow the synthesis tool to create custom paths between any two points on the chip, effectively wiring the logic blocks together to build the user's desired circuit.

The number of states that can be represented by 'n' flip-flops is . To implement a state machine with 'N' states, we need to find the smallest integer 'n' such that . In this case, N=5. For n=2, , which is not enough. For n=3, , which is sufficient to represent 5 states (with 3 states being unused). Therefore, a minimum of 3 flip-flops are required.

1. Total number of rows to refresh: The DRAM has 16K rows, which is rows.
2. Total time for one full refresh: This is the number of rows multiplied by the time for one row refresh: .
3. Refresh period: The entire refresh must be completed within 64 ms.
4. Percentage of time spent on refresh (overhead): This is the ratio of the total time taken for refreshing to the total refresh period.
   
   

We minimize each function and count the total unique product terms.

: Group {0,1,4,5} gives and group {10,11,14,15} gives . So (2 product terms: ).

: All minterms have . So (1 product term: ).

: Group {0,1,2,3} gives . Group {10,11} gives . Group {12,13} gives . So (3 product terms: ).

None of the product terms are shared between functions. The 6 unique terms are: , , , , , . The PLA's programmable OR array routes the appropriate terms to each output: , , .

The maximum clock frequency is limited by the longest delay path between any two flip-flops in the system.

Path 1 — Internal state register feedback: The signal travels from the flip-flop output, through the combinational logic (AND-OR array), and back to the flip-flop input.

Path 2 — PLD registered output to external circuit: Since the output is registered (directly from the flip-flop), it becomes valid after . The external circuit must capture it before the next clock edge, requiring its setup time to be met.

The system clock must satisfy all constraints simultaneously. The bottleneck is the slower path:

A single 4-input LUT can implement any Boolean function of up to 4 variables. The 6-input XOR must be decomposed.

Balanced tree decomposition (2 levels, 3 LUTs):

1. LUT-1: Computes (3-input function, fits one 4-input LUT).
2. LUT-2: Computes (3-input function, fits one 4-input LUT).
3. LUT-3: Computes (2-input function, fits one 4-input LUT).

LUT-1 and LUT-2 operate in parallel (level 1), and LUT-3 combines their results (level 2). This balanced tree has only 2 levels of logic delay, providing predictable and symmetric timing.

Note: A cascade approach (LUT-1 computes , LUT-2 computes ) uses only 2 LUTs but creates an asymmetric path. Synthesis tools typically prefer the balanced 3-LUT tree for better timing predictability across the FPGA fabric.

The PAL16L8 allows each output OR gate to accept up to 7 product terms. We must check whether the given function fits.

The function has 7 terms: , , , , , , .

We check for redundancies by absorption: term is a subset of (whenever , we also have ). So is redundant and the function actually requires only 6 product terms.

Since both the original 7-term expression and the simplified 6-term expression fit within the PAL16L8's limit of 7 product terms per OR gate, the function can be implemented directly on a single output without any factoring or cascading. The device's 10+ input pins also accommodate the 6 input variables.

1. Understand the Target: The decoder is for a common anode display. This means a logic '0' turns a segment ON, and a logic '1' turns a segment OFF. The segments are typically labeled a, b, c, d, e, f, g. Let's map the ROM data bits to segments: D7, D6, D5, D4, D3, D2, D1, D0 -> (unused), g, f, e, d, c, b, a.
2. Analyze the Requirement: For the input address (binary 1011), the BCD code is invalid. The requirement is to make the display blank.
3. Determine the Output for 'Blank': To make a common anode display blank, all segments must be turned OFF. This requires applying a logic '1' to all segment lines (a through g).
4. Construct the Data Word: The data word to be stored is gfedcba. Since all segments must be OFF (logic 1), the required pattern is 1111111. If we assume the 8th bit (D7) is unused and pulled high or is a don't care set to 1, the 8-bit word is 11111111 in binary.
5. Convert to Hexadecimal: The binary value 11111111 is equal to in hexadecimal. Therefore, the value stored at address must be .

The data from the SRAM will be valid only after all three timing constraints are met. Let's define T=0 as the moment the address and Chip Select (CS) are asserted.

1. Address Access Time (): Data is not valid until 20 ns after the address is stable. So, data is valid at .
2. Chip Select Access Time (): CS is asserted at T=0. Data is not valid until 15 ns after CS is asserted. So, data is valid at .
3. Output Enable Access Time (): OE is asserted at T=5 ns (5 ns after address/CS). Data is not valid until 10 ns after OE is asserted. So, data is valid at .

For the data to be guaranteed valid, we must wait for the latest of these events. The three events complete at 20 ns, 15 ns, and 15 ns respectively.
The latest time is 20 ns. Therefore, the data is guaranteed to be valid 20 ns after the address is first applied.

The general-purpose interconnect matrix in an FPGA is designed for flexibility, allowing connections between any logic elements. This flexibility comes at the cost of speed, as signals must pass through multiple programmable switches (pass transistors, multiplexers), which adds significant RC delay. A 32-bit adder requires a carry signal to ripple from the least significant bit to the most significant bit. If this carry signal were routed through the general interconnect, the delay would accumulate at each of the 32 stages, making the adder very slow.

Dedicated carry chains solve this by providing a direct, optimized, high-speed connection for the carry signal between vertically or horizontally adjacent Logic Elements (LEs) or Configurable Logic Blocks (CLBs). This specialized path has very low delay compared to the general-purpose routing, allowing the carry to propagate very quickly. This is the main reason for the significant performance improvement.

1. ROM Size Calculation: A ROM that implements a function of N inputs and M outputs requires words of M bits each. For 8 inputs and 6 outputs, the ROM size is bits. The ROM's decoder will have 8 inputs and outputs (word lines).

2. PLA AND-Plane Crosspoints: A PLA AND-plane has crosspoints, where N is the number of inputs and P is the number of product terms. The '2' accounts for both the true and complemented form of each input. Utilized crosspoints are the ones actually used to form the product terms. The question asks for the number of crosspoints in the plane, which is the total size. Number of crosspoints = .

3. ROM Decoder Crosspoints: The ROM's address decoder is a fixed AND-plane that generates all possible minterms. The number of crosspoints in this decoder is . However, a more standard view of a decoder's complexity is its number of outputs, which is . Let's consider the comparison to be against the number of bits in the decoder input stage, which is often represented as . A more direct comparison is the number of programmable elements. In the PLA, it's the number of fuses/switches. In the ROM, the connections are fixed. Let's interpret 'crosspoints in the ROM's decoder' as the number of transistors in the NOR/NAND decoder array, which is approximately . Size = .

4. Calculate the Ratio: The question asks for the ratio of PLA AND-plane crosspoints to ROM decoder crosspoints.
   PLA AND-plane size = .
   Ratio = .

This calculation matches option D exactly. The key is understanding the internal structure of both devices to make a valid comparison.

1. State Encoding: To represent 5 states, we need a minimum of bits. These 3 bits will be the outputs of 3 D-flip-flops, representing the current state ().

2. Inputs to Combinational Logic: The combinational logic block must calculate two things: the next state and the outputs. For a Mealy machine, both are a function of the current state and the primary inputs.

   • Current State bits: 3 (from the flip-flop outputs, fed back)
   • Primary Input bits: 3
   • Total inputs to the logic block = .

3. Outputs from Combinational Logic: The logic block must generate the signals that will be the inputs to the flip-flops (next state) and the primary outputs.

   • Next State bits (): 3 (these will be connected to the D-inputs of the flip-flops).
   • Primary Output bits: 4
   • Total outputs from the logic block = .

Therefore, the combinational logic requires 6 inputs (3 state bits + 3 primary inputs) and produces 7 outputs (3 next-state bits + 4 primary outputs).

First, identify the minterms: . On a 4-variable K-map, these four cells form a checkerboard pattern — no two minterms are adjacent, so no pair can be combined into a larger implicant. The minimum SOP therefore requires all 4 product terms, one per minterm.

Since the PAL's OR gate accepts at most 3 product terms, the function cannot fit on a single output. The standard solution is output cascading:

1. First output: Implement (3 terms — fits the OR gate).
2. Feedback: Route back into the AND array as a new input variable.
3. Second output: Implement (2 terms — fits the OR gate).

This uses two PAL macrocells to realize a 4-term function that exceeds the capacity of a single OR gate. The tradeoff is one additional level of propagation delay due to the feedback path.

The leakage current must be low enough that the capacitor voltage stays above 1.92 V for the entire 64 ms refresh period.

1. Maximum allowable voltage drop:
   

2. Maximum charge that can be lost:
   

3. Maximum leakage current: Since :
   

This extremely small current (~31 fA) illustrates why DRAM cell transistors must have exceptionally low off-state leakage. In practice, this is achieved through high-threshold-voltage access transistors and careful process engineering.

Let T=0 be the start of the bus cycle when the address becomes stable.

1. ROM Data Availability: We need to find when the ROM data is guaranteed to be valid. This is the later of two events:

   • From Address: Data is valid at ns.
   • From Output Enable: The OE signal is asserted at ns. Data is valid after that. So, data is valid at ns.
     The data is guaranteed to be valid at the latest of these two times, which is 150 ns.

2. System Timing Requirement: The microprocessor latches the data at ns. This means the data must be valid before this time. The minimum bus cycle time given this latch point is 200 ns.

3. Timing Margin: The ROM provides stable data at 150 ns. The processor needs it at 200 ns. The margin is the difference between when the data is needed and when it becomes available.

   • Margin = (Time data is latched) - (Time data is valid)
   • Margin = .

The minimum bus cycle time is determined by the processor's requirement (200 ns), and the ROM meets this requirement with a 50 ns margin.

Let the 4 bits of the counter be . The next state () for each bit is a function of the current state. The synchronous reset (RST) also affects the next state.

• . This is a 2-input function (RST, ).
• . This is a 3-input function (RST, ).
• . This is a 4-input function (RST, ).
• . This is a 5-input function (RST, ).

At first glance, the logic for is a 5-input function, which cannot fit into a single 4-input LUT. This would suggest that the logic for the MSB needs to be decomposed, requiring an extra LUT and therefore more than 4 LEs.

However, modern FPGAs are highly optimized for counters. The LUT can be configured to include the flip-flop's current state () as an implicit input. More importantly, most FPGA flip-flops have dedicated synchronous clear/preset inputs that are handled by dedicated signals, not by general LUT logic. When the synthesis tool sees if (RST) Q <= 0;, it will map the RST signal to the flip-flop's synchronous clear port, not consume a LUT input.

Therefore, the next-state logic becomes:

• . (1 input, )
• . (2 inputs, )
• . (3 inputs, )
• . (4 inputs, )

Each of these logic functions has 4 or fewer inputs and can be implemented in a single 4-input LUT. Since each bit also requires one flip-flop, each bit of the counter maps perfectly to one Logic Element (1 LUT + 1 FF). Therefore, a total of 4 LEs are required.

1. Word count and address width: The DRAM stores 64M = words of 16 bits each. Total capacity = bytes = bytes = 128 MB.

2. Byte addressing: The system uses a byte address bus. With 128 MB, byte addresses range over 27 bits: A26 down to A0. Since the DRAM is 16-bit (2-byte) wide, the least significant address bit A0 selects the byte within the 16-bit word and is not sent to the DRAM chip. The DRAM sees word address bits A26 down to A1 — a total of 26 bits.

3. Square array: The word locations are organized as a square: Rows = Columns = . This requires 13 bits for the row address and 13 bits for the column address.

4. RAS/CAS mapping: Using the standard convention where higher-order bits select the row and lower-order bits select the column:

   • Row Address (13 bits): A26 ... A14
   • Column Address (13 bits): A13 ... A1

   Total: 13 + 13 = 26 bits (A26 to A1).

The byte address 0x01A34B68 is provided for context but its specific value is not needed — the question is about the address bit mapping.

We minimize each output function and count the total unique product terms across both circuits. Since the circuits have disjoint inputs, no product terms can be shared between them.

Full Adder (inputs: A, B, ):

• — 4 product terms
• — 3 product terms
• No terms are shared between S and . Total: 7 unique terms.

4-to-2 Priority Encoder (inputs: highest priority, outputs: ):

• — uses terms and
• — uses terms and
• The term is shared between both outputs. Unique terms: , , . Total: 3 unique terms.

Combined total: unique product terms. The PLA's programmable OR array can route the appropriate product terms to each of the 4 outputs ().

CPLD architecture is designed to handle logic functions that are wider (require more product terms) than a single macrocell or LAB can provide. This is accomplished through 'product term expansion' or 'logic sharing'.
When a function, like the one requiring 25 product terms, exceeds the capacity of a single macrocell (16 terms), the CPLD's fitter/compiler will split the logic. It will implement the first 16 product terms in one macrocell/LAB. The remaining 9 product terms are implemented in other nearby macrocells. The outputs of these product terms are not used to drive a pin but are routed via the Programmable Interconnect Array (PIA) to the first macrocell. These are called 'expander' product terms. The first macrocell's OR gate is expanded to include these additional terms from its neighbors, allowing it to synthesize the complete 25-term function. This is a key architectural feature of CPLDs that allows them to efficiently implement wide SOP expressions.

A ROM can be used as a lookup table to implement any combinational logic function.

1. Determine the number of inputs: A 4x4 multiplier takes two 4-bit numbers as input. Let the inputs be A (4 bits) and B (4 bits). The total number of input lines to the ROM is inputs.

2. Determine the number of address lines: The number of address lines for the ROM is equal to the total number of inputs. So, there are 8 address lines.

3. Determine the number of memory locations (words): The number of locations in the ROM is locations. Each location will store the pre-calculated result of a multiplication.

4. Determine the number of outputs (word size): The result of multiplying two 4-bit numbers can be up to 8 bits long. For example, the maximum multiplication is (binary 1111 x 1111), which equals 225 (binary 11100001), requiring 8 bits for the output.

5. Calculate the total size: The total size of the ROM is (number of locations) x (word size) = bits = 2048 bits.

The PAL's OR gate supports at most 4 product terms. We must find a form (true or complement) of each function that fits.

For F1: requires 6 terms (exceeds limit). requires 3 terms (fits). Strategy: implement and use the programmable output polarity to invert it, yielding .

For F2: requires 4 terms (fits exactly). requires 5 terms (exceeds limit). Strategy: implement directly without inversion.

Analysis of each option:

• Option A: needs 6 terms — exceeds limit. Invalid.
• Option B: (3 terms, fits) + (4 terms, fits). Both fit. Valid.
• Option C: (6 terms, exceeds) — Invalid.
• Option D: (5 terms, exceeds) — Invalid.

This demonstrates programmable output polarity's value: by implementing a function's complement when it has fewer terms, a PAL can handle functions that would otherwise exceed its capacity.

1. Memory Organization:

   • The processor has a 32-bit data bus (implied, as it's a 32-bit address bus system, a standard assumption). We need to build a memory that is 32 bits (4 bytes) wide.
   • The DRAM chips are 8 bits (1 byte) wide.
   • To create a 32-bit wide memory bank, we need chips placed in parallel. All 4 chips will be active at the same time to provide the full 32-bit word.

2. Memory Capacity and Number of Banks:

   • Total required memory: 1 GB = bytes.
   • Capacity of one chip: 256M x 8-bit = 256 MB = bytes.
   • The bank of 4 chips created in step 1 has a total capacity of locations x 32 bits/location = x 4 bytes = bytes = 1 GB.
   • Since one bank of 4 chips provides the full 1 GB required, only these 4 chips are needed in total. No additional banks are necessary.

3. Address Decoding:

   • Each DRAM chip has 256M () locations. To address these locations, it needs 28 address lines ( to ). These lines are handled internally by the DRAM's RAS/CAS logic.
   • The processor has a 32-bit address bus. For a byte-addressable memory of 1GB ( bytes), the processor will use address lines down to .
   • The lowest two address bits () are typically used for byte selection within the 32-bit word and are not sent to the DRAMs.
   • Since we only have one bank of chips, we need a way to enable this bank. The external address decoder's job is to select which bank of chips to enable using the high-order address bits that are not used by the chips themselves. The processor address bus goes up to . The memory space is 1GB = bytes. So processor addresses are used for this memory space. The higher bits are used to select the 1GB memory block itself. So the external decoder will decode and to generate the master chip select signal for this entire memory module. Therefore, 2 address lines are used by the external decoder to map the 1GB block into the processor's 4GB address space.