Unit 4 - Practice Quiz

HDL stands for Hardware Description Language. It is a specialized computer language used to describe the structure, design, and behavior of electronic and digital logic circuits.

Synthesis is the process that translates the high-level hardware description (RTL code) into an optimized gate-level representation, which consists of logic gates and flip-flops.

Hardware by its nature is highly parallel. HDLs have constructs to describe concurrent operations that happen at the same time, unlike traditional software languages which are primarily sequential.

The module is the basic design unit in Verilog. It encapsulates the functionality and defines the input/output ports of a hardware component.

The left arrow ← symbol in RTL denotes a transfer operation. This statement means that the data currently in register R2 is copied into register R1.

A bus is a shared communication pathway that connects various components like the CPU, memory, and I/O devices, allowing data and control signals to be transferred between them.

Logic micro-operations perform bit-wise logical operations on data in registers. XOR (exclusive OR) is a logic operation, while ADD, INCREMENT, and SUBTRACT are arithmetic micro-operations.

A shift register is a cascade of flip-flops that share the same clock, used to store binary data. Its primary function is to shift the stored data one bit position at a time with each clock pulse.

A full adder is a combinational circuit that adds three bits: two operand bits (A and B) and a carry-in bit (Cin) from the previous stage, producing a sum and a carry-out.

Booth's multiplication algorithm is designed specifically to handle the multiplication of two signed binary numbers that are represented in the two's complement format.

Simulation involves running test cases (a testbench) on the HDL model to verify that it behaves as expected according to the design specifications. It is a crucial step to catch functional errors early.

A micro-operation is the most basic, atomic operation that can be performed on data stored within the CPU's registers during a single clock cycle.

This notation describes reading from memory. The contents of the memory location specified by the Address Register (AR) are transferred into register R1.

Digital systems simplify subtraction by converting it into an addition problem. The subtraction A - B is equivalent to adding A to the two's complement of B, allowing the same adder circuitry to be used for both operations.

As digital circuits grew in complexity, graphical schematic diagrams became extremely difficult to create, read, and maintain. HDLs provided a textual, scalable, and more manageable way to describe these large designs.

The wire data type is used to represent connections between hardware elements. It cannot store a value on its own and must be continuously driven by the output of a gate or another module.

The control function P: acts as a gate. The register transfer R2 ← R1 will only be executed during a clock cycle if the boolean control condition P is true (evaluates to 1).

A logical shift operation moves all bits in one direction and fills the empty spot created at the end with a 0. This is used for shifting unsigned numbers.

The fundamental algorithm for binary multiplication involves a loop. In each iteration, one bit of the multiplier is examined, a conditional addition is performed, and the partial product is shifted by one bit position to prepare for the next iteration.

Verification is a broader process than just initial simulation. It involves comprehensive checks, including post-synthesis simulation, static timing analysis, and formal verification, to confirm that the final hardware design is correct and meets all specified constraints.

Functional simulation verifies the logical correctness of the design but does not consider timing delays of gates and interconnects. Post-synthesis timing analysis is required to check if the design can meet the specified clock frequency. A common reason for failure on hardware after a successful functional simulation is a timing violation where signal propagation delays are too long.

We scan the multiplier 10110 with an appended LSB of 0, from right to left:

1. Pair 00: No operation.
2. Pair 10: Subtract multiplicand.
3. Pair 11: No operation.
4. Pair 01: Add multiplicand.
5. Pair 10: Subtract multiplicand.
   However, the standard algorithm only considers the last two bits at each step. Let's retrace: Y=10110, Y_-1=0.
   • Step 1: Bits are 00 -> Shift.
   • Step 2: Bits are 10 -> Subtract, Shift.
   • Step 3: Bits are 11 -> Shift.
   • Step 4: Bits are 01 -> Add, Shift.
   • Step 5: Bits are 10 -> Subtract, Shift.
6. Q₀Q_-1 = 00: Shift.
7. Q = x1011, Q₀Q_-1 = 10: Subtract, Shift.
8. Q = xx101, Q₀Q_-1 = 11: Shift.
9. Q = xxx10, Q₀Q_-1 = 01: Add, Shift.
10. Q = xxxx1, Q₀Q_-1 = 10: Subtract, Shift.
    • Step 1: 00: Shift.
    • Step 2: 10: Subtract, Shift.
    • Step 3: 01: Add, Shift.
    • Step 4: 10: Subtract, Shift.
    • Step 5: 01: Add, Shift.
      Sequence: Subtract, Add, Subtract, Add. Let's fix the original question with a new multiplier Y = 01101 (+13). Y_-1=0.
11. 10: Subtract.
12. 01: Add.
13. 10: Subtract.
14. 11: No-op.
15. 01: Add.

New Q: Using Booth's algorithm to multiply by 0110 (+6). Appended bit is 0. Pairs scanned from right: 00, 10, 11, 01. The sequence of arithmetic operations is: No-op, Subtract, No-op, Add. This is clear.
Options: A: No-op, Subtract, No-op, Add, B: Add, No-op, Subtract, No-op, C: Subtract, No-op, Add, No-op, D: No-op, Add, No-op, Subtract. Correct A. Let's replace the old Q2 with this one. I will do that in the final JSON.

This code uses blocking assignments (=). In a procedural block, blocking assignments execute sequentially. First, a = b is executed, so a becomes 0. Then, b = a is executed, using the new value of a. Since a is now 0, b also becomes 0. A correct swap would require non-blocking assignments (a <= b; b <= a;) or a temporary variable.

This is a sequential process. First, at time T1, the content of R1 is copied to R2. At this point, both R1 and R2 hold the original value of R1. Then, at time T2, the content of R2 (which is now the original value of R1) is copied back to R1. The net result is that the original value of R1 is in both registers, and the original value of R2 is lost.

Subtraction in 2's complement is performed by adding the 2's complement of the subtrahend. The 2's complement of a number (R2) is found by taking its 1's complement (not(R2)) and then adding 1. This result is then added to the minuend (R1).

For a memory write operation, the target memory address (X) must first be loaded into the Memory Address Register (MAR). Simultaneously or subsequently, the data to be written (R1) is loaded into the Memory Buffer Register (MBR). Finally, the Write control signal is asserted to transfer the data from the MBR to the memory location specified by the MAR.

The core paradigm of HDLs is to model hardware, which is naturally parallel. Multiple always blocks or continuous assignments in Verilog represent circuits that operate simultaneously. In contrast, C and other software languages follow a sequential, von Neumann model where instructions are executed in a defined order by a processor.

First, the data 1011 must be loaded into the register. This requires the parallel load operation, which is selected by setting the control inputs s1s0 to 11 for one clock cycle. After the data is loaded, it needs to be shifted right twice. The shift-right operation is selected by setting s1s0 to 01. This must be maintained for two consecutive clock cycles to perform two shifts.

The product of two n-bit numbers can be up to 2n bits long. In a shift-and-add multiplier, the accumulator must be large enough to hold the final product. For two 4-bit numbers, the product can be up to 8 bits (e.g., 1111 * 1111 = 11100001). Therefore, the accumulator and product register combination must accommodate 8 bits.

Logic synthesis is the process of converting a high-level, behavioral description of a circuit (written in an HDL) into an optimized gate-level representation, known as a netlist. This netlist consists of basic logic gates (AND, OR, NOT, etc.) and flip-flops from a specific technology library, and it describes the circuit's structure and connectivity.

When a combinational always block does not specify the value of a signal for all possible conditions, the synthesizer infers that the signal must hold its previous value. This behavior of 'remembering' a state implies memory, and the simplest form of memory element created for this situation is a latch. This is often an unintended result and can lead to timing issues.

The control function is (K'T + KT'). This is the Boolean expression for the XOR operation. Therefore, the register transfer R1 <- R1 ⊕ R2 is enabled and executed only when the condition K ⊕ T is true, which occurs when K and T have opposite logic levels.

To select one out of N sources, you need at least log₂(N) selection lines. In this case, there are 16 registers (N=16). Therefore, the number of selection lines required is log₂(16) = 4. These 4 lines can represent 2⁴ = 16 unique binary codes, each corresponding to one of the registers.

An arithmetic shift right shifts all bits one position to the right. The least significant bit is discarded. The most significant bit (MSB), which is the sign bit, is copied and preserved in the MSB position. Since the initial MSB is 1, the new MSB will also be 1. The remaining bits are shifted right, resulting in 11011010.

Let's trace the addition bit by bit, from right to left:

• Bit 0: 1 + 0 = 1. Sum=1, =0.
• Bit 1: 1 + 1 + 0 (carry-in) = 10. Sum=0, =1.
• Bit 2: 0 + 1 + 1 (carry-in) = 10. Sum=0, =1.
• Bit 3 (MSB): The inputs are A₃=1, B₃=0, and the carry-in from bit 2 is 1. So, . The sum is 1 + 0 + 1 = 10. The sum bit is 0, and the carry-out () is 1.

While schematics represent a fixed structure, HDLs describe behavior. A synthesis tool can interpret this behavior and explore many different gate-level implementations to find one that is optimized for specific constraints (e.g., run at a high speed, use minimal chip area). This automated optimization is a core advantage of the HDL synthesis flow over manual schematic design.

Booth's algorithm recodes the multiplier. The multiplier 0110 has a string of ones from bit 1 to bit 2. The algorithm interprets this as (+M) at the position to the right of the LSB of the string (position 1) and (-M) at the position to the left of the MSB of the string (position 3). This corresponds to the operation (2^3 - 2^1) * M = (8 - 2) * M, which equals 6M. The algorithm effectively replaces a series of additions with one addition and one subtraction.

The expression R2' + 1 is the definition of the 2's complement of R2 (where R2' is the 1's complement). The overall operation is R1 + (2's complement of R2), which is the standard method for performing the subtraction R1 - R2 using binary addition hardware.

The logical OR operation has the property that X OR 1 = 1 and X OR 0 = X. Therefore, to set specific bits to 1, you can perform an OR operation between the register and a mask word. The mask should have 1s in the positions you want to set and 0s in the positions you want to leave unchanged. This is often called 'selective-set'.

In a standard shift-and-add multiplier, each cycle examines the LSB of the multiplier register (Q). If the LSB is 1, it signifies that the multiplicand (A) should be added to the partial product stored in the accumulator. If the LSB is 0, no addition is performed. Regardless of the addition, the cycle concludes with a right shift of the combined accumulator and Q registers to prepare for the next bit.

Let M = -8 and Q = -3. We use 8-bit registers for an 8-bit result. M = 11111000 (-8). -M = 00001000 (+8). The accumulator A is initialized to 00000000 and the multiplier register Q holds 1101 (we only care about its 4 bits). The implicit bit Q(-1) is 0.

1. Cycle 1 (Q0=1, Q-1=0 -> '10'): A <- A - M. A = 00000000 - 11111000 = 00001000. Right shift [A,Q]: A=00000100, Q=x110.
2. Cycle 2 (Q0=0, Q-1=1 -> '01'): A <- A + M. A = 00000100 + 11111000 = 11111100. Right shift [A,Q]: A=11111110, Q=xx11.
3. Cycle 3 (Q0=1, Q-1=0 -> '10'): A <- A - M. A = 11111110 - 11111000 = 00000110. Right shift [A,Q]: A=00000011, Q=xxx1.
4. Cycle 4 (Q0=1, Q-1=1 -> '11'): No-op. Right shift [A,Q]: A=00000001, Q=xxxx.
   The final concatenated result in [A,Q] is 000000011000 (the lower 8 bits), which is 00011000 in binary, or +24 in decimal, the correct answer for (-8) * (-3).

Modern synthesis tools are capable of interpreting certain 'non-synthesizable' constructs for practical purposes. An initial block for register initialization is commonly synthesized into a power-on-reset value, often loaded into block RAM or flip-flop initialization bits in an FPGA. Crucially, the timing constraint file (e.g., SDC) is a primary input to the synthesis process. The tool actively uses these constraints to make decisions about gate selection, placement, and routing to meet performance targets, not just to check them afterward.

This question addresses the core HDL vs. SPL paradigm. The Verilog code does not describe a sequence of operations. It describes a static hardware circuit: a 2-to-1 multiplexer with inputs a and b and selector sel. The output of this multiplexer is continuously available to the D-input of a flip-flop (q). The @(posedge clk) specifies the event (a clock edge) at which the flip-flop captures this value. This is a description of parallel hardware and timed events. A C if-else block, conversely, is compiled into a sequence of CPU instructions: test a condition, then branch to one set of instructions or another for sequential execution.

This code uses blocking assignments (=). Within a procedural block, blocking assignments execute sequentially in a zero-time simulation model. When the always block triggers on a clock edge:

1. The statement q1 = din; executes and completes immediately. The Verilog scheduler updates q1 with the current value of din.
2. The statement q2 = q1; executes next. It reads the value of q1, which has already been updated in the same simulation time step. Therefore, q2 is assigned the new value of q1, which is the current value of din. Both q1 and q2 get the value of din on the same clock edge, defeating the purpose of a multi-stage pipeline. To create a proper pipeline, non-blocking assignments (<=) must be used.

In Register Transfer Language, all micro-operations to the right of a control signal (like K:) that are separated by commas are assumed to occur simultaneously within the same clock cycle. This implies that the hardware must have parallel resources to execute these operations. In this case, it requires a data path with an adder to compute R1 + R2 and a separate incrementer (or another adder) to compute AR + 1. Both results must be available to be loaded into their respective destination registers on the same clock edge when the control signal K is active.

In a realistic single-bus architecture, data from memory and data for the ALU cannot typically be accessed in a single cycle. The process must be broken down:

1. Memory Fetch: First, the content of the memory location pointed to by AR must be retrieved. This involves a memory read operation, and the data from memory is placed into the Data Register (DR). This constitutes the first micro-operation: DR ← M[AR].
2. Arithmetic Operation: Once the operand from memory is stable in DR, the ALU can perform the addition. The ALU takes its inputs from R1 and DR, performs the addition, and the result is written back to R1. This is the second micro-operation: R1 ← R1 + DR.
   Option A is less efficient as it uses the bus more than necessary. Option C is not possible in a single cycle in such an architecture. Option D has redundant/incorrect steps.

Let's trace the multiplication of M=0110 and Q=0101. A is initialized to 0000.

• Initial State: A = 0000, Q = 0101.
• Cycle 1: Q0 is 1. Add M to A: A = 0000 + 0110 = 0110. Shift right [A,Q]: A = 0011, Q = 0010.
• Cycle 2: Q0 is 0. No add. Shift right [A,Q]: A = 0001, Q = 1001.
• Cycle 3: Q0 is 1. Add M to A: A = 0001 + 0110 = 0111. Shift right [A,Q]: A = 0011, Q = 1100.
  After the third cycle completes with its shift, the state is A = 0011 and Q = 1100.

The most efficient way to compute a multiplication by a constant is to use shifts and adds/subtracts. The constant is 7. We can represent 7 as .

• Multiplying A by 8 is a single arithmetic shift left by 3 positions (shl(A, 3)).
• Then, we subtract A to get 8A - A = 7A.
• Finally, we subtract B.
  This translates to a sequence of three micro-operations:
  1. T ← shl(A, 3) (Computes 8A)
  2. T ← T - A (Computes 7A)
  3. Y ← T - B (Computes 7A - B)
     This is more efficient than adding A seven times or other more complex decompositions.

Booth's algorithm performs an addition for a 01 pair and a subtraction for a 10 pair when scanning the multiplier bits from right to left (with an implicit 0 appended). An operation occurs at every transition between 0 and 1. To maximize operations, we need to maximize transitions.
Let's analyze the bit patterns (appending ):

• 11111111 -> 111111110: Only one transition (10) at the start. 1 operation.
• 10000000 -> 100000000: Two transitions (00...01 at the end). 2 operations.
• 01010101 -> 010101010: A transition at every single bit (10, 01, 10, etc.). This results in 8 operations, one for each bit of the multiplier. This is the worst-case scenario.
• 00110011 -> 001100110: Transitions at bit 0 (10), bit 2 (01), and bit 4 (10). 3 operations.

Deep, subtle corner-case bugs in control-heavy logic like coherency protocols are a classic weakness of simulation-based verification. Simulation, even with high coverage, only explores a tiny fraction of the possible state space. Formal verification, in contrast, uses mathematical techniques to exhaustively prove that a design adheres to specified properties under all possible conditions and input sequences. It doesn't run 'test cases' but rather analyzes the entire state space. This makes it exceptionally powerful at finding complex corner cases that are nearly impossible to trigger with directed or random testing. Gate-level simulation is for timing verification, and emulation/more seeds just scales up the same simulation methodology that already failed.

This code demonstrates a classic Verilog race condition. The fork...join block spawns two parallel threads. Both threads schedule an event to occur at time #1. Because they are scheduled for the exact same simulation time, the Verilog LRM does not guarantee their order of execution.

• Scenario 1: The a = 1; statement executes first. Then, b = a; executes, reading the new value of a. b becomes 1, and therefore c becomes 1.
• Scenario 2: The b = a; statement executes first. It reads the current value of a, which is still 0. b becomes 0. Then, a = 1; executes. The final value of c is 0.
  Since either order is valid, the result is non-deterministic and depends on the specific simulator's scheduling algorithm.

The key advantage of a carry-lookahead adder (CLA) is speed, which comes from eliminating the ripple effect. In a ripple-carry adder, the calculation of the sum bit and carry must wait for the carry from the previous stage. The worst-case delay is proportional to the number of bits, . The CLA logic, as shown in the equation, calculates any carry bit as a two-level logic function of the P (propagate) and G (generate) signals. Since all P and G signals are themselves generated in parallel from the main inputs A and B, all carry bits can be computed in a constant, small number of gate delays, independent of the bit position. This parallel computation breaks the serial dependency and results in a worst-case delay of for hierarchical CLAs.

A common bus is a shared electrical resource. At any time, only one device is allowed to be a 'driver' (outputting a signal). If two standard logic gates were to drive the bus simultaneously, with one outputting a high voltage ('1') and the other a low voltage ('0'), it would create a direct, low-resistance path between the power supply and ground. This is a short circuit known as bus contention, which leads to excessive current, potential hardware damage, and an invalid, indeterminate logic level on the bus. Tri-state buffers solve this by adding a high-impedance ('Z') state. When a register is not selected to drive the bus, its buffer is put in this 'Z' state, effectively disconnecting it electrically and allowing another buffer to safely control the bus voltage.

The Load_R1 signal must be asserted whenever any micro-operation that writes to R1 is active. We need to find the condition for each operation and combine them with a logical OR.

• The first operation R1 ← R2 happens when condition x is true AND the time step is T1. The Boolean term is x \cdot T1 (or x AND T1).
• The second operation R1 ← R1 + R2 happens when condition y is false (y') AND the time step is T2. The Boolean term is y' \cdot T2 (or NOT y AND T2).
• The third operation R1 ← 0 happens during time step T3. The Boolean term is simply T3.
  Since R1 should be loaded if any of these conditions are met, the final control signal is the logical OR of these terms: Load_R1 = (x \cdot T1) + (y' \cdot T2) + T3.

Let R = 11001011.

• Arithmetic Shift Right (ashr): Shifts bits right and replicates the Most Significant Bit (MSB) to preserve the number's sign. The MSB is 1, so a 1 is shifted in. Result: 11100101 (-27).
• Logical Shift Right (lshr): Shifts bits right and always shifts a 0 into the MSB position. Result: 01100101 (101).
• Rotate Right (ror): Shifts bits right and moves the original Least Significant Bit (LSB) into the MSB position. The LSB of R is 1, so a 1 is moved to the MSB. Result: 11100101 (-27).
  This example shows a case where ashr and ror produce the identical result because the LSB matches the sign bit.

For a procedural block to be synthesized into purely combinational logic, every output must be assigned a deterministic value for every possible combination of inputs. If a condition exists where an output is not explicitly assigned (e.g., an if (condition) statement without a corresponding else), the synthesis tool must infer logic that holds the output's previous value. The hardware element that implements this 'memory' behavior is a latch. This is known as an inferred latch and is often an unintentional design error that can complicate timing analysis. A default clause in a case statement is a way to prevent inferred latches by ensuring all conditions are covered.

A generate for loop is not a runtime construct; it is a synthesis-time (or elaboration-time) construct. Its purpose is to create multiple, static instances of hardware. For the synthesis tool to know how many physical copies of a module or logic block to create, the bounds of the loop must be constant values that can be determined during the compilation/synthesis process. The tool effectively 'unrolls' the loop, creating distinct hardware for each iteration. In stark contrast, a for loop in C is a runtime construct compiled into machine code with branches and jumps, allowing its iteration count to be a variable determined during program execution.

This question tests the analysis of micro-operations. The operation R / 4 can be implemented with two consecutive shift-right operations (for an unsigned integer). However, the + 8 part is an arithmetic addition. The universal shift register's functions are Hold, Shift, and Parallel Load. It does not have an internal adder. While we could parallel-load the value 8, there is no mechanism provided to add it to the existing (or shifted) value of R. The operations are mutually exclusive in any given cycle. Therefore, to perform (R / 4) + 8, the value of R would need to be sent to an external ALU, operated upon, and the result would then be loaded back into R using the Parallel-Load function. The register itself cannot complete the entire sequence.

The most significant paradigm shift brought by VHDL and Verilog was their synergy with logic synthesis tools. Before this, designers primarily used schematic capture to specify the exact gate-level structure of a circuit, a tedious and error-prone process for large designs. HDLs allowed designers to describe the behavior of a circuit at the Register Transfer Level (RTL)—describing how data moves between registers and the logical operations performed on it. A synthesis tool could then automatically translate this higher-level description into an optimized gate-level netlist. This abstraction from structure to behavior was the key to managing the complexity of modern digital systems and dramatically boosted productivity.

Radix-4 Booth's algorithm recodes the multiplier bits to perform multiplication more quickly by handling two bits at a time. It examines overlapping groups of three bits to decide which multiple of the multiplicand M () to add/subtract. The recoding table is as follows:

• 000 or 111 -> 0 * M
• 001 or 010 -> +1 * M
• 101 or 110 -> -1 * M
• 011 -> +2 * M
• 100 -> -2 * M
  Therefore, the bit group 011 is the unique pattern that codes for the +2M operation. The 2M value is typically pre-calculated with a single left shift of M.