DDCArv_Ch5.pdf

# Arithmetic circuits and adders This section explores the fundamental arithmetic circuits that form the basis of digital computation, with a primary focus on adders and their various implementations. ## 1. Arithmetic circuits and adders ### 1.1 Introduction to adders Adders are essential combinational logic circuits that perform the arithmetic addition of binary numbers. They are a cornerstone of digital design, enabling operations like counting, arithmetic logic unit (ALU) functionality, and data processing within computer architectures [5](#page=5). ### 1.2 Basic adder building blocks #### 1.2.1 Half adder A half adder is the simplest adder circuit that adds two single binary bits, A and B, producing a Sum (S) and a Carry Out (Cout) [5](#page=5). * **Logic:** * Sum: $S = A \oplus B$ [5](#page=5). * Carry Out: $C_{out} = A \cdot B$ [5](#page=5). #### 1.2.2 Full adder A full adder is a circuit that adds three single binary bits: two input bits, A and B, and a Carry In ($C_{in}$) from a previous, less significant bit position. It outputs a Sum (S) and a Carry Out ($C_{out}$) [5](#page=5). * **Logic:** * Sum: $S = A \oplus B \oplus C_{in}$ [5](#page=5). * Carry Out: $C_{out} = AB + AC_{in} + BC_{in}$ [5](#page=5). ### 1.3 Multibit Adders To add numbers larger than a single bit, multiple full adders are chained together. These are categorized as Carry Propagate Adders (CPAs). The efficiency of CPAs is largely determined by how the carry signal propagates through the stages [6](#page=6). #### 1.3.1 Ripple-carry adder A ripple-carry adder is constructed by connecting multiple 1-bit full adders in series. The carry-out of one stage becomes the carry-in of the next, rippling through the entire chain [8](#page=8). * **Disadvantage:** This ripple effect makes ripple-carry adders inherently slow, especially for a large number of bits, as the carry must propagate through every stage before the final sum is determined [8](#page=8). * **Delay:** The total delay of an N-bit ripple-carry adder is approximately $N$ times the delay of a single full adder ($t_{FA}$), i.e., $t_{ripple} = N \cdot t_{FA}$ [9](#page=9). #### 1.3.2 Carry-lookahead adder (CLA) Carry-lookahead adders aim to overcome the speed limitations of ripple-carry adders by calculating carry signals in parallel, rather than waiting for them to propagate. This is achieved by using "generate" and "propagate" signals [10](#page=10) [11](#page=11). * **Generate ($G_i$) and Propagate ($P_i$) signals for a column *i*:** * **Generate ($G_i$):** A carry is generated at column *i* if both input bits $A_i$ and $B_i$ are 1. $G_i = A_i \cdot B_i$ [11](#page=11). * **Propagate ($P_i$):** A carry-in to column *i* will propagate to the carry-out if either $A_i$ or $B_i$ (or both) is 1. $P_i = A_i + B_i$ [11](#page=11). * **Carry Out ($C_i$) of a column:** This can be expressed as: $C_i = G_i + P_i \cdot C_{i-1}$ [11](#page=11). * **Block Propagate and Generate signals:** To speed up carry propagation across multiple bits, these column-level signals are used to compute block-level propagate and generate signals for groups of bits (e.g., k-bit blocks) [13](#page=13). * **Block Propagate ($P_{k:0}$):** A carry-in to a k-bit block will propagate through all *k* bits to become the block's carry-out if each individual bit within the block propagates. For a 4-bit block (bits 3:0): $P_{3:0} = P_3 \cdot P_2 \cdot P_1 \cdot P_0$ [14](#page=14) [15](#page=15). * **Block Generate ($G_{k:0}$):** A carry is generated by a k-bit block if it's generated in any bit position within the block, or if it's generated in a lower position and propagated through all higher positions up to the block's carry-out. For a 4-bit block (bits 3:0): $G_{3:0} = G_3 + G_2P_3 + G_1P_2P_3 + G_0P_1P_2P_3$ [15](#page=15). This can be factored as: $G_{3:0} = G_3 + P_3(G_2 + P_2(G_1 + P_1G_0))$ [15](#page=15) [17](#page=17) [18](#page=18). * **Block Carry Out ($C_{k}$):** The carry-out of a k-bit block is determined by the block's generate and propagate signals: $C_k = G_{k:0} + P_{k:0} \cdot C_{-1}$ (where $C_{-1}$ is the carry-in to the block) [17](#page=17). * **Structure:** A 32-bit CLA can be implemented using 4-bit blocks, where each block has its own carry-lookahead logic, and a higher-level carry-lookahead logic handles carries between these blocks [19](#page=19) [25](#page=25). * **Steps in CLA addition:** 1. Compute $G_i$ and $P_i$ for all columns [11](#page=11) [21](#page=21). 2. Compute $G$ and $P$ for k-bit blocks [22](#page=22). 3. The carry-in propagates through each k-bit block's generate/propagate logic, while sums are computed concurrently [23](#page=23). 4. Compute the sum for the most significant k-bit block [24](#page=24). * **Delay:** The delay of an N-bit CLA with k-bit blocks is given by $t_{CLA} = t_{pg} + t_{pg\_block} + (N/k – 1)t_{AND\_OR} + k \cdot t_{FA}$. For large N (e.g., $N > 16$), CLAs are significantly faster than ripple-carry adders [26](#page=26). #### 1.3.3 Prefix adders Prefix adders, also known as carry-prefix adders, offer further speed improvements by computing all carry-prefix signals in parallel. They achieve this by pre-calculating carry-in signals for each column without waiting for a sequential ripple [27](#page=27) [28](#page=28). * **Carry Calculation:** The core idea is to compute carry-in ($C_{i-1}$) for each column *i* efficiently. The sum $S_i$ is then computed as $S_i = (A_i \oplus B_i) \oplus C_{i-1}$ [28](#page=28). * **Prefixes:** The circuit aims to quickly compute "prefixes" of the form $G_{k-1:-1}$ for various block sizes (1, 2, 4, 8 bits, etc.) until all carry-ins are known. These prefixes are essentially the carry-outs of the blocks [29](#page=29). * **Generate ($G_{i:j}$) and Propagate ($P_{i:j}$) for a block spanning bits *i* to *j*:** These are defined recursively [30](#page=30). * **Generate ($G_{i:j}$):** A carry is generated for the block $i:j$ if the upper part ($i:k$) generates a carry, or if the upper part propagates a carry generated by the lower part ($k-1:j$). $G_{i:j} = G_{i:k} + P_{i:k} \cdot G_{k-1:j}$ [30](#page=30). * **Propagate ($P_{i:j}$):** A carry propagates through the block $i:j$ if both the upper part ($i:k$) and the lower part ($k-1:j$) propagate the carry. $P_{i:j} = P_{i:k} \cdot P_{k-1:j}$ [30](#page=30). * **Carry-in to column *i* ($C_{i-1}$):** This is equivalent to the carry generated for the prefix spanning up to column $i-1$. $C_{i-1} = G_{i-1:-1}$ [29](#page=29). * **Delay:** The delay of a prefix adder for N bits is $t_{PA} = t_{pg} + \log_2 N (t_{pg\_prefix}) + t_{XOR}$ where $t_{pg}$ is the delay to produce initial $P_i, G_i$ and $t_{pg\_prefix}$ is the delay of a prefix cell. Prefix adders are generally the fastest among the discussed CPA types for large N [33](#page=33) [34](#page=34). ### 1.4 Adder Delay Comparisons Comparing the delays of different 32-bit adder implementations using a 2-input gate delay of 100 ps and a full adder delay of 300 ps: * **Ripple-carry adder:** $t_{ripple} = 32 \times 300 \text{ ps} = 9.6 \text{ ns}$ [34](#page=34). * **Carry-lookahead adder (32-bit with 4-bit blocks):** $t_{CLA} = [100 + 600 + (32/4 – 1)200 + 4 \text{ ps} = [100 + 600 + 7 \times 200 + 1200 \text{ ps} = 3.3 \text{ ns}$ [34](#page=34). * **Prefix adder:** $t_{PA} = [100 + \log_2 32 + 100 \text{ ps} = [100 + 5 \times 200 + 100 \text{ ps} = 1.2 \text{ ns}$ [34](#page=34). This comparison highlights that prefix adders offer the lowest delay, followed by carry-lookahead adders, with ripple-carry adders being the slowest due to the sequential carry propagation. The trade-off for increased speed in CLAs and prefix adders is typically higher hardware complexity [34](#page=34) [6](#page=6). > **Tip:** When analyzing adder delays, remember that the complexity of the gates used for generate, propagate, and prefix computations directly impacts the overall circuit speed. > > **Example:** Consider a 32-bit addition. A ripple-carry adder would require 32 full adder delays sequentially. A carry-lookahead adder with 4-bit blocks would have a carry-lookahead logic for the blocks (which depends on the number of blocks), plus the delay within each block. A prefix adder would have a delay logarithmic to the number of bits, making it asymptotically faster. --- # Subtractors, comparators, and the ALU This section explores fundamental digital logic components: subtractors, comparators, and the Arithmetic Logic Unit (ALU), detailing their operations, control mechanisms, and status flag generation. ### 2.1 Subtractors A subtractor performs the arithmetic operation of subtraction. It can be implemented using an adder by converting the subtraction of B into the addition of its two's complement, along with a carry-in of 1. This relationship is expressed as [36](#page=36): $A - B = A + \overline{B} + 1$ [36](#page=36). ### 2.2 Comparators Comparators are digital circuits that determine the relationship between two binary numbers. #### 2.2.1 Equality comparator An equality comparator checks if two numbers, A and B, are identical. It outputs a signal that is HIGH if A is equal to B, and LOW otherwise [1](#page=1) [37](#page=37). #### 2.2.2 Signed less than comparator A comparator can also determine if one signed number is less than another. A number A is considered less than B ($A < B$) if the result of subtracting B from A ($A - B$) is negative. However, care must be taken to account for potential overflow conditions when performing this subtraction, as overflow can lead to incorrect sign interpretation [38](#page=38). ### 2.3 The Arithmetic Logic Unit (ALU) The ALU is a crucial combinational logic circuit within a processor that performs arithmetic and logic operations on binary operands [39](#page=39) [40](#page=40). #### 2.3.1 Basic operations A typical ALU is designed to perform fundamental operations such as: * Addition [40](#page=40). * Subtraction [40](#page=40). * Logical AND [40](#page=40). * Logical OR [40](#page=40). #### 2.3.2 Control signals and operation selection The specific operation performed by the ALU is determined by a set of control signals. For a 2-bit control signal (`ALUControl1:0`), different combinations dictate the operation: * `00`: Add [41](#page=41) [42](#page=42) [43](#page=43). * `01`: Subtract [41](#page=41) [42](#page=42) [43](#page=43). * `10`: AND [41](#page=41) [42](#page=42). * `11`: OR [41](#page=41) [42](#page=42). The control signals manage multiplexers within the ALU to select the appropriate functional unit (e.g., adder, OR gate) and route its output to the ALU's result bus. For addition and subtraction, the `ALUControl0` signal often controls the carry-in to the adder [41](#page=41) [42](#page=42) [43](#page=43). > **Tip:** Understanding how control signals direct data flow through functional units is key to comprehending ALU operation. #### 2.3.3 Status flags ALUs also generate status flags, which are single-bit outputs that provide information about the result of the most recent operation. These flags are essential for conditional branching and error detection [44](#page=44) [45](#page=45). * **N (Negative flag):** Set to 1 if the most significant bit (MSB) of the result is 1, indicating a negative result in signed number representations [46](#page=46). * **Z (Zero flag):** Set to 1 if all bits of the result are 0, indicating that the result of the operation is zero [47](#page=47). * **C (Carry flag):** Set to 1 if the adder produces a carry-out. This flag is relevant for addition and subtraction operations (when `ALUControl` is `00` or `01`) [48](#page=48). * **V (Overflow flag):** Set to 1 if an arithmetic operation results in an overflow. Overflow occurs when the addition of two numbers with the same sign produces a result with the opposite sign. The condition for overflow can be complex, involving the signs of the operands and the result, and is dependent on whether the ALU is performing addition or subtraction [49](#page=49) [50](#page=50). #### 2.3.4 Comparisons based on flags The status flags can be combined logically to perform comparisons between operands, distinguishing between signed and unsigned interpretations: | Comparison | Signed | Unsigned | | :---------- | :----------------------------------- | :------- | | `==` | $Z$ | $Z$ | | `!=` | $\sim Z$ | $\sim Z$ | | `<` | $N \oplus V$ | $\sim C$ | | `<=` | $Z \lor (N \oplus V)$ | $Z \lor \sim C$ | | `>` | $\sim Z \land \sim(N \oplus V)$ | $\sim Z \land C$ | | `>=` | $\sim(N \oplus V)$ | $C$ | The general principle is to perform a subtraction ($A - B$) and then interpret the resulting flags to determine the comparison outcome [52](#page=52). #### 2.3.5 Other ALU operations Beyond basic arithmetic and logic, ALUs can support other operations: * **Set Less Than (SLT):** This operation sets the least significant bit (LSB) of the result to 1 if $A < B$, and to 0 otherwise. It comes in both signed and unsigned versions. The implementation often involves an adder and logic to derive the SLT condition from the ALU's control signals and flags [53](#page=53) [54](#page=54) [55](#page=55). * **XOR:** Performs the bitwise exclusive OR operation between operands A and B [53](#page=53). --- # Shifters, multipliers, dividers, and number representations This section explores fundamental digital operations, including bit shifting for multiplication and division, various multiplication and division algorithms, and different methods for representing numbers in binary, ranging from fixed-point to floating-point formats. ### 3.1 Shifters Shifters are digital circuits that move the bits of a binary number. Different types of shifters exist, each with specific behaviors for filling vacated bit positions [57](#page=57). #### 3.1.1 Logical Shifter A logical shifter shifts bits to the left or right and fills any empty positions with zeros [57](#page=57). * **Left Shift (<<):** Bits are moved to the left. The least significant bits (LSBs) are filled with zeros. For example, `11001 << 2` results in `00100` [57](#page=57). * **Right Shift (>>):** Bits are moved to the right. The most significant bits (MSBs) are filled with zeros. For example, `11001 >> 2` results in `00110` [57](#page=57). #### 3.1.2 Arithmetic Shifter An arithmetic shifter behaves similarly to a logical shifter, but for right shifts, it fills the vacated MSB positions with the value of the original most significant bit (sign bit). This preserves the sign of a signed number [57](#page=57). * **Arithmetic Right Shift (>>>):** For a number like `11001`, an arithmetic right shift by 2 (`11001 >>> 2`) results in `11110` [57](#page=57). #### 3.1.3 Rotator A rotator shifts bits in a circular manner. Bits shifted off one end of the number are reintroduced at the other end [57](#page=57). * **Rotate Right (ROR):** Bits shifted off the right end reappear on the left. For example, `11001 ROR 2` results in `01110` [57](#page=57). * **Rotate Left (ROL):** Bits shifted off the left end reappear on the right. For example, `11001 ROL 2` results in `00111` [57](#page=57). #### 3.1.4 Shifters as Multipliers and Dividers Shifters can efficiently perform multiplication and division by powers of two. * **Multiplication by 2^N:** A left shift by `N` positions is equivalent to multiplying the number by $2^N$ [59](#page=59). * Example: `00001 << 3` is equivalent to $1 \times 2^3 = 8$, resulting in `01000` [59](#page=59). * Example with signed numbers: `11101 << 2` (representing -3 in two's complement) is equivalent to $-3 \times 2^2 = -12$, resulting in `10100` [59](#page=59). * **Division by 2^N:** An arithmetic right shift by `N` positions is equivalent to dividing the number by $2^N$ [59](#page=59). * Example: `01000 >>> 1` is equivalent to $8 \div 2^1 = 4$, resulting in `00100` [59](#page=59). * Example with signed numbers: `10000 >>> 2` (representing -16) is equivalent to $-16 \div 2^2 = -4$, resulting in `11100` [59](#page=59). > **Tip:** Using shifters for multiplication and division by powers of two is significantly faster than using general multiplication and division hardware. ### 3.2 Multipliers Multiplication in binary involves forming partial products by multiplying each bit of the multiplier with the multiplicand, and then summing these shifted partial products [60](#page=60). #### 3.2.1 Multiplication Process The process can be visualized with a decimal example: $230 \times 42$. This breaks down into $(230 \times 2)$ and $(230 \times 40)$, which are then added. In binary, for a 4x4 multiplication: * Each bit of the multiplier ($B_i$) is ANDed with each bit of the multiplicand ($A_j$) to form partial products $A_j B_i$ [61](#page=61). * These partial products are then shifted appropriately and summed to produce the final product [61](#page=61). ### 3.3 Dividers Division in binary, similar to decimal long division, aims to find a quotient (Q) and a remainder (R) such that the dividend (A) can be expressed as $A = B \times Q + R$, where $0 \le R < B$. The general form is $A/B = Q + R/B$ [62](#page=62) [63](#page=63). #### 3.3.1 Binary Long Division The binary division process involves repeatedly subtracting the divisor (B) from a portion of the dividend. * An iterative algorithm can be described as follows [64](#page=64): * Initialize a remainder register $R'$ to 0. * For each bit $A_i$ from the most significant to the least significant: * Shift $R'$ left by one bit and append the current bit $A_i$ to form a new $R$: $R = \{R' \ll 1, A_i\}$ [64](#page=64). * Subtract the divisor $B$ from $R$: $D = R - B$ [64](#page=64). * If $D < 0$, the quotient bit $Q_i$ is 0, and $R'$ is set to $R$ (no subtraction occurred) [64](#page=64). * If $D \ge 0$, the quotient bit $Q_i$ is 1, and $R'$ is set to $D$ (subtraction occurred) [64](#page=64). * After iterating through all bits, the final $R'$ holds the remainder [64](#page=64). > **Example:** Binary division of $1101$ by $10$ ($13 \div 2$). > * $R' = 0$. > * $i=3$ ($A_3=1$): $R = \{0 \ll 1, 1\} = 1$. $D = 1 - 10 = -1$. $Q_3=0$, $R'=1$. > * $i=2$ ($A_2=1$): $R = \{1 \ll 1, 1\} = 11_2 = 3$. $D = 11_2 - 10_2 = 01_2 = 1$. $Q_2=1$, $R'=1$. > * $i=1$ ($A_1=0$): $R = \{1 \ll 1, 0\} = 10_2 = 2$. $D = 10_2 - 10_2 = 0$. $Q_1=1$, $R'=0$. > * $i=0$ ($A_0=1$): $R = \{0 \ll 1, 1\} = 1$. $D = 1 - 10_2 = -1$. $Q_0=0$, $R'=1$. > * Final quotient is $0110$ and remainder is $1$ [64](#page=64) [6](#page=6). ### 3.4 Fixed-Point Numbers Fixed-point representation defines a specific number of bits for the integer part and a specific number of bits for the fractional part of a number, with the binary point's position fixed [69](#page=69) [70](#page=70). #### 3.4.1 Number Systems Binary representations can denote positive numbers (unsigned binary) or negative numbers, typically using two's complement or sign/magnitude formats [68](#page=68). #### 3.4.2 Representation * **Unsigned Fixed-Point Format (Ua.b):** Represents an unsigned number with `a` integer bits and `b` fractional bits. For example, U4.4 means 4 bits for the integer part and 4 bits for the fractional part [71](#page=71). * Example: $6.75$ in U4.4 is `01101100` [70](#page=70) [71](#page=71). * Common formats include 8-bit, 16-bit, and 32-bit fixed-point numbers, such as U8.8 for sensor data and U16.16 for higher precision signal processing [71](#page=71). * **Signed Fixed-Point Format (Qa.b):** Represents a signed number (typically in two's complement) with `a` integer bits (including the sign bit) and `b` fractional bits [72](#page=72). * To negate a Q fixed-point number, invert all bits and add one to the LSB [72](#page=72). * Example: To write $-6.75$ in Q4.4: * $6.75$ is `01101100`. * Inverting bits: `10010011`. * Adding 1 to LSB: `10010100` [72](#page=72). * Q1.15 (also known as Q15) is a common format for signal processing, representing values in the range $[1, -1)$ [72](#page=72). #### 3.4.3 Saturating Arithmetic Saturating arithmetic is an overflow handling technique where, instead of wrapping around, the result is clamped to the maximum or minimum representable value if an overflow occurs [73](#page=73). * **Example:** In U4.4, adding $12$ (`11000000`) and $7.5$ (`01111000`) would normally overflow. With saturating arithmetic, the result is the maximum representable value, $15.9375$ (`11111111`) [73](#page=73). > **Tip:** Saturating arithmetic is crucial in applications like signal processing and graphics to prevent artifacts caused by overflow, such as clicking sounds in audio or dark pixels in video [73](#page=73). ### 3.5 Floating-Point Numbers Floating-point numbers represent a wide range of values by using a variable position for the binary point, similar to scientific notation in decimal [69](#page=69) [75](#page=75). #### 3.5.1 Representation A floating-point number is generally expressed as $\pm M \times B^E$, where $M$ is the mantissa, $B$ is the base, and $E$ is the exponent [75](#page=75). * In binary, the base $B$ is typically 2. * The binary point floats to the right of the most significant '1' bit in the mantissa [69](#page=69). #### 3.5.2 Floating vs. Fixed Point * **Floating-point:** Offers a greater dynamic range (smallest to largest values) and is preferred for general-purpose computing where ease of programming is paramount. However, floating-point arithmetic is more complex and can be slower and more power-intensive [76](#page=76). * **Fixed-point:** Has a smaller dynamic range but is simpler and more efficient for hardware implementations, making it ideal for performance-critical applications like signal processing, machine learning, and video processing [76](#page=76). #### 3.5.3 IEEE 754 Standard The IEEE 754 standard defines the representation for floating-point numbers, commonly in 32-bit (single-precision) and 64-bit (double-precision) formats. A 32-bit floating-point number is divided into three fields [77](#page=77) [83](#page=83): * **Sign (1 bit):** 0 for positive, 1 for negative [77](#page=77). * **Exponent (8 bits):** Represents the power of 2. It is stored in a "biased" form to allow for both positive and negative exponents and to simplify comparisons. The bias for single-precision is 127. The stored exponent is `bias + actual exponent` [77](#page=77) [80](#page=80) [83](#page=83). * **Mantissa/Fraction (23 bits):** Represents the significant digits of the number. The leading '1' before the binary point is implicit and not stored, saving a bit and increasing precision [79](#page=79). ##### 3.5.3.1 Converting to IEEE 754 To represent a decimal number in IEEE 754 32-bit format: 1. Convert the magnitude of the decimal number to its binary equivalent [78](#page=78). 2. Express the binary number in scientific notation: $1.xxxxx \times 2^{\text{exponent}}$ [78](#page=78). 3. Fill the fields: * **Sign bit:** Determined by the original number's sign [78](#page=78). * **Exponent bits:** Calculate the biased exponent: `bias + actual exponent` [80](#page=80). * **Fraction bits:** Store the bits of the mantissa that appear after the binary point [79](#page=79). > **Example:** Representing $228_{10}$ in IEEE 754. > 1. $228_{10} = 11100100_2$ [78](#page=78). > 2. Binary scientific notation: $1.11001_2 \times 2^7$ [78](#page=78). > 3. Fields: > * Sign: 0 (positive) [78](#page=78). > * Exponent: $127 (\text{bias}) + 7 = 134 = 10000110_2$ [80](#page=80). > * Fraction: $11001000000000000000000$ (padded to 23 bits) [79](#page=79). > The resulting representation is `0 10000110 11001000000000000000000` [80](#page=80). ##### 3.5.3.2 Special Cases The IEEE 754 standard also defines special values: * **Zero:** Sign exponent fraction $\pm 0$ `X 00000000 00000000000000000000000` [82](#page=82). * **Infinity ($\infty$):** Sign exponent fraction `0 11111111 00000000000000000000000` (positive infinity) or `1 1111111 00000000000000000000000` (negative infinity) [82](#page=82). * **Not a Number (NaN):** Sign exponent fraction `X 11111111 non-zero` [82](#page=82). ##### 3.5.3.3 Precision and Rounding * **Single-Precision:** 32 bits (1 sign, 8 exponent, 23 fraction), bias = 127 [83](#page=83). * **Double-Precision:** 64 bits (1 sign, 11 exponent, 52 fraction), bias = 1023 [83](#page=83). * **Overflow:** Occurs when a number is too large to be represented [84](#page=84). * **Underflow:** Occurs when a number is too small (close to zero) to be represented [84](#page=84). * **Rounding Modes:** Used to adjust a number when it cannot be precisely represented after an operation. Common modes include rounding down, up, toward zero, and to the nearest value [84](#page=84). > **Example of Rounding:** Rounding $1.100101_2$ (which is $1.578125_{10}$) to 3 fraction bits. > * Down: $1.100_2 = 1.5_{10}$ > * Up: $1.101_2 = 1.625_{10}$ > * Toward zero: $1.100_2 = 1.5_{10}$ > * To nearest: $1.101_2 = 1.625_{10}$ (since $1.625$ is closer to $1.578125$ than $1.5$) [84](#page=84). ### 3.6 Floating-Point Addition Adding floating-point numbers is a multi-step process that requires aligning the numbers before performing the addition [86](#page=86). #### 3.6.1 Addition Algorithm The general steps for floating-point addition are: 1. **Extract components:** Separate the sign, exponent, and fraction bits from both numbers [86](#page=86) [88](#page=88). 2. **Form mantissas:** Prepend the implicit leading '1' to the fraction bits to reconstruct the full mantissa [86](#page=86) [88](#page=88). 3. **Compare exponents:** Determine the difference between the exponents of the two numbers [86](#page=86) [89](#page=89). 4. **Align mantissas:** Shift the mantissa of the number with the smaller exponent to the right by the difference in exponents. This ensures both numbers have the same exponent before addition [86](#page=86) [89](#page=89). 5. **Add mantissas:** Perform binary addition on the aligned mantissas. The exponent remains the same as the larger of the two original exponents [86](#page=86) [89](#page=89). 6. **Normalize mantissa:** If the result of the addition has a mantissa that is not in the form $1.xxxxx$ (e.g., $10.xxxxx$ or $0.1xxxxx$), adjust it by shifting the binary point and updating the exponent accordingly [86](#page=86) [90](#page=90). 7. **Round result:** Apply a rounding mode if the normalized mantissa exceeds the available fraction bits [86](#page=86). 8. **Assemble:** Combine the sign, the adjusted exponent (biased), and the fraction bits back into the floating-point format [86](#page=86) [90](#page=90). > **Example:** Adding $0\text{x}3\text{FC}00000$ and $0\text{x}40500000$. > * N1: $0\ 01111111\ 10000000000000000000000$ (S=0, E=127, F=.1) $\implies$ Mantissa = $1.1_2$, Exponent = 0 [88](#page=88). > * N2: $0\ 10000000\ 10100000000000000000000$ (S=0, E=128, F=.101) $\implies$ Mantissa = $1.101_2$, Exponent = 1 [88](#page=88). > * Compare exponents: $127 < 128$. Exponent difference is 1. > * Align N1: Shift $1.1_2$ right by 1 $\implies 0.11_2$ (now with exponent 1) [89](#page=89). > * Add mantissas: $0.11_2 + 1.101_2 = 10.011_2$ [89](#page=89). > * Normalize: $10.011_2 \times 2^1 = 1.0011_2 \times 2^2$ [90](#page=90). > * Assemble: S=0, Exponent = $2 + 127 = 129 = 10000001_2$, Fraction = $001100...$. Result is $0\ 10000001\ 00110000000000000000000$, which is $0\text{x}40980000$ [90](#page=90). --- # Counters, shift registers, and memory arrays This section delves into essential sequential digital building blocks, covering the functionality, implementation, and applications of counters, shift registers, and various types of memory arrays [91](#page=91). ### 4.1 Counters Counters are digital circuits that increment or decrement a binary number on each clock edge. They are fundamentally used to cycle through a sequence of numbers [92](#page=92). #### 4.1.1 Counter implementation and applications A basic counter increments its value on each active clock edge. If a reset signal is asserted, the counter typically returns to a predefined initial state, often zero [92](#page=92) [93](#page=93). **Applications include:** * Digital clock displays [92](#page=92). * Program counters, which track the address of the next instruction to be executed in a processor [92](#page=92). A SystemVerilog implementation of a counter with a synchronous reset demonstrates this behavior. The `always_ff` block describes a flip-flop that triggers on the positive edge of the clock. If the `reset` signal is high, the counter `q` is reset to 0; otherwise, it is incremented by 1 (`q <= q + 1;`). An alternative, more verbose implementation explicitly uses an adder to compute the next state before assigning it to the flip-flops [93](#page=93). > **Tip:** Synchronous resets are generally preferred in digital design as they ensure that the reset signal is synchronized with the clock, preventing timing issues. #### 4.1.2 Divide-by-2N counter A divide-by-2N counter is a specific type of counter where the most significant bit (MSB) toggles its state every $2^N$ clock cycles. This property makes them useful for functions like slowing down a clock signal or creating periodic events, such as blinking an LED. For example, a 50 MHz clock divided by a 24-bit counter can produce a signal with a frequency of approximately 2.98 Hz [94](#page=94). > **Example:** To blink an LED with a 50 MHz clock, one could use a 24-bit counter. The MSB of this counter would flip every $2^{24}$ clock cycles, effectively creating a blinking signal. #### 4.1.3 Digitally Controlled Oscillator (DCO) A digitally controlled oscillator (DCO) is an extension of a counter that can generate an output frequency proportional to a digital input value. Instead of simply incrementing by 1 on each clock cycle, the counter increments by a value 'p'. The output frequency ($f_{out}$) is then given by the formula [95](#page=95): $$f_{out} = f_{clk} \times \frac{p}{2^N}$$ where $f_{clk}$ is the input clock frequency, $p$ is the increment value, and $N$ is the number of bits in the counter [95](#page=95). > **Example:** To generate a 200 Hz signal from a 50 MHz clock ($f_{clk}$), using a 24-bit counter ($N=24$): > We need $\frac{p}{2^{24}} = \frac{200}{50 \text{ MHz}}$. > If we choose $p = 67$, then $f_{out} = 50 \text{ MHz} \times \frac{67}{2^{24}} \approx 199.676 \text{ Hz}$. > For a more precise frequency, a 32-bit counter ($N=32$) with $p = 17179$ can yield $f_{out} \approx 199.990 \text{ Hz}$. ### 4.2 Shift Registers Shift registers are sequential circuits that store and shift binary data serially. They consist of a chain of flip-flops, where the output of one flip-flop is connected to the input of the next [96](#page=96). #### 4.2.1 Serial-to-parallel conversion On each clock edge, a new bit is shifted into the first flip-flop, and the data in all subsequent flip-flops is shifted one position down the chain. This process effectively converts a serial input data stream (`Sin`) into a parallel output word (`Q0` to `QN-1`) [96](#page=96). #### 4.2.2 Shift register with parallel load Shift registers can be augmented with a 'load' control signal [97](#page=97). * When the `Load` signal is high (e.g., `Load = 1`), the register behaves like a standard parallel-load register, accepting data from parallel inputs (`D0` to `DN-1`) [97](#page=97). * When `Load` is low (`Load = 0`), the register functions as a traditional shift register, shifting data from `Sin` to the output `Sout` [97](#page=97). This dual functionality allows shift registers with parallel load to act as both serial-to-parallel converters (shifting `Sin` into `Q0:N-1`) and parallel-to-serial converters (shifting `D0:N-1` out through `Sout`) [97](#page=97). The SystemVerilog implementation for a configurable shift register with parallel load and synchronous reset is provided. The `always_ff` block handles the logic, prioritizing reset, then load, and finally the serial shift operation. The serial output `sout` is assigned to the most significant bit of the register `q[N-1]` [98](#page=98). ### 4.3 Memory arrays Memory arrays are fundamental structures designed for efficient storage of large amounts of digital data. They consist of a two-dimensional arrangement of bit cells, where each cell stores a single bit [100](#page=100) . #### 4.3.1 Structure and addressing A memory array is characterized by its depth (number of rows or words) and width (number of columns or bits per word). For an N-bit address and M-bit data, there are $2^N$ unique addresses, defining $2^N$ rows (depth), and each row can store an M-bit data value (width). (#page=100, 101) The total array size is depth $\times$ width, which equals $2^N \times M$ [100](#page=100) . > **Example:** A 22 × 3-bit array signifies a memory with 4 words (since $2^2 = 4$) and each word is 3 bits wide. The word stored at address `10` (binary for 2) would be `100`. A 1024-word by 32-bit array requires 10 address bits ($2^{10} = 1024$) and outputs 32 data bits . #### 4.3.2 Wordlines and Bitlines Access to individual memory cells is managed through wordlines and bitlines . * **Wordline:** Similar to an enable signal, a wordline selects a specific row in the memory array. Only one wordline is active (high) at any given time, corresponding to the unique address being accessed. Reading or writing occurs on the row enabled by the wordline . * **Bitline:** These lines carry the data to and from the memory cells. When a wordline is activated, the bitlines are used to either read the stored bit's value or to write a new value into the cell . #### 4.3.3 Types of memory Memory arrays are broadly categorized into two main types: Random Access Memory (RAM) and Read-Only Memory (ROM) . ##### 4.3.3.1 Random Access Memory (RAM) RAM is volatile memory, meaning it loses its stored data when power is removed. (#page=106, 107) It offers fast read and write operations. The term "random access" signifies that any data word can be accessed with equal ease and speed, unlike sequential access memories . There are two primary types of RAM: * **Dynamic Random Access Memory (DRAM):** Invented by Robert Dennard, DRAM stores each bit of data on a capacitor. (#page=110, 111, 112) The term "dynamic" arises because the charge on the capacitor leaks over time, necessitating periodic refreshing (rewriting) to maintain the data. Reading a bit from DRAM also destroys its stored value, requiring a read-and-refresh cycle. A DRAM bit cell typically consists of a transistor and a capacitor . * **Static Random Access Memory (SRAM):** SRAM stores data using cross-coupled inverters, which do not require refreshing as long as power is supplied. (#page=110, 114, 115) This makes SRAM faster and simpler to access than DRAM, but it typically requires more transistors per bit, making it less dense and more expensive . ##### 4.3.3.2 Read-Only Memory (ROM) ROM is nonvolatile memory, retaining its data even when power is switched off. (#page=106, 108) It is designed for quick reading, but writing data is either impossible or a slow process. Historically, ROMs were programmed at the time of fabrication, but modern ROMs like Flash memory allow for reprogramming. Flash memory, invented by Fujio Masuoka, is widely used in storage devices like thumb drives and solid-state drives . **ROMs can be represented using dot notation:** * A dot in a bit cell indicates that a '1' is stored . * The absence of a dot can indicate a '0', or a specific configuration might be implied for '0' . > **Example:** A 22 × 3-bit ROM can be used to implement logic functions. (#page=118, 121) If the address lines are A1 and A0, and the outputs are Data2, Data1, and Data0, the functions can be mapped as follows : > * Data2 = A1 $\oplus$ A0 (#page=120, 122) . > * Data1 = A1 + A0 (#page=120, 122) . > * Data0 = A1 $\cdot$ A0 (#page=120, 122) . > The memory array effectively acts as a lookup table (LUT), where each input combination (address) maps to a pre-programmed output . #### 4.3.4 Logic with memory arrays Memory arrays, particularly ROMs, can be utilized to implement arbitrary logic functions. (#page=121, 122, 123) By programming the bit cells, the memory array can store the truth table of a desired logic function. The address lines correspond to the logic function's inputs, and the data lines correspond to its outputs . #### 4.3.5 SystemVerilog Memory Implementation SystemVerilog provides constructs for modeling RAM and ROM: * **RAM:** A RAM can be declared as an array of logic vectors, with read and write operations controlled by clock and write enable signals . * **ROM:** A ROM is also declared as an array, but its contents are typically initialized from a file (`USDreadmemh` in SystemVerilog) at simulation startup, and it only supports read operations. (#page=127, 128) . #### 4.3.6 Multi-ported memories Multi-ported memories are memory structures that allow multiple read and/or write operations to occur concurrently. Each "port" provides an independent address/data interface. A common example is a register file, which often has multiple read ports and one or more write ports to support simultaneous access by different functional units within a processor. (#page=129, 130) A 32x32 register file with two read ports and one write port is illustrated in SystemVerilog . --- # Logic arrays and FPGAs This topic explores programmable logic devices, specifically Programmable Logic Arrays (PLAs) and Field-Programmable Gate Arrays (FPGAs), detailing their structures and functionalities for implementing digital circuits . ### 5.1 Programmable Logic Arrays (PLAs) PLAs are a type of programmable logic device that implement combinational logic functions. Their internal structure consists of two programmable arrays: an AND array followed by an OR array . #### 5.1.1 Structure of a PLA A PLA takes inputs and generates implicants using an AND array, which are then combined in an OR array to produce the final outputs. The connections within these arrays are fixed, but the programming allows for the selection of which input lines are connected to which AND gates and which AND gate outputs are connected to which OR gates . > **Tip:** The structure of a PLA is fundamentally a sum-of-products implementation where both the product terms (AND array) and the sum terms (OR array) are programmable . **Example:** Consider the functions: * $X = ABC + ABC$ * $Y = AB$ These can be implemented in a PLA where the AND array generates the product terms $ABC$, $ABC$, and $AB$, and the OR array combines $ABC$ and $ABC$ to form $X$, and $AB$ to form $Y$. The dot notation in diagrams represents a programmable connection . ### 5.2 Field-Programmable Gate Arrays (FPGAs) FPGAs are another type of programmable logic device that offer more flexibility than PLAs. They are characterized by an array of configurable Logic Elements (LEs) and programmable interconnections. FPGAs can implement both combinational and sequential logic . #### 5.2.1 Components of an FPGA A typical FPGA is composed of several key elements : * **Logic Elements (LEs):** These are the fundamental units that perform logic operations . * **Input/Output Elements (IOEs):** These interface the internal logic of the FPGA with the external world . * **Programmable Interconnection:** This network of wires and switches allows LEs and IOEs to be connected flexibly . * **Other Building Blocks:** Some FPGAs may also include specialized blocks like multipliers and RAMs . #### 5.2.2 Logic Elements (LEs) Each LE is designed to implement logic functions. A standard LE is composed of : * **Lookup Tables (LUTs):** These are memory elements that can implement any combinational logic function of their inputs . * **Flip-flops:** These provide sequential logic capabilities, allowing the LE to store state . * **Multiplexers:** These are used to route signals and select between combinational and registered outputs, connecting LUTs and flip-flops . **Example: Altera Cyclone IV LE** An Altera Cyclone IV LE, for instance, contains one four-input LUT, one registered output, and one combinational output. This structure allows it to implement functions of up to four variables using the LUT and provides both a combinational and a sequential output . #### 5.2.3 LE Configuration Examples The configuration of LEs and the calculation of required LEs for specific functions are crucial for FPGA design. **Example 1: XOR Chain** To implement the function $Y = A_1 \oplus A_2 \oplus A_3 \oplus A_4 \oplus A_5 \oplus A_6$ using Altera Cyclone IV LEs: * **Required LEs:** 2 . * **Explanation:** The first LE can compute $Y_1 = A_1 \oplus A_2 \oplus A_3 \oplus A_4$, which is a function of 4 variables and fits within a single LE's LUT. The second LE can then compute $Y = Y_1 \oplus A_5 \oplus A_6$, a function of 3 variables, utilizing the registered output of the first LE and two additional inputs . **Example 2: 32-bit 2:1 Multiplexer** To implement a 32-bit 2:1 multiplexer using Altera Cyclone IV LEs: * **Required LEs:** 32 . * **Explanation:** A 1-bit multiplexer is a function of 3 variables (data input 1, data input 2, and select line), which can be implemented within a single LE. Therefore, a 32-bit multiplexer requires 32 such 1-bit multiplexer implementations, each requiring one LE . **Example 3: Arbitrary Finite State Machine (FSM)** To implement an arbitrary FSM with 2 bits of state, 2 inputs, and 3 outputs using Altera Cyclone IV LEs: * **Required LEs:** 5 . * **Explanation:** * Each bit of state requires an LE to hold the current state bit and implement the next state logic. The next state logic is a function of the current state (2 bits) and the inputs (2 bits), totaling 4 variables, which fits in one LE. Thus, 2 LEs are needed for the two state bits . * Each output bit requires an LE to compute its value. The output logic is typically a function of the current state (2 bits). Thus, 3 LEs are needed for the three output bits . * Total LEs = 2 (for state) + 3 (for outputs) = 5 LEs . ### 5.3 FPGA Design Flow The process of designing for an FPGA typically involves using specialized Computer-Aided Design (CAD) tools, such as Altera's Quartus II. The general flow includes : 1. **Design Entry:** Creating the circuit design using schematic entry or a Hardware Description Language (HDL) . 2. **Simulation:** Verifying the design's functionality through simulation . 3. **Synthesis and Mapping:** The CAD tool translates the design into a netlist and maps it onto the available LEs and interconnections of the target FPGA . 4. **Configuration Download:** The synthesized design is compiled into a configuration file, which is then downloaded onto the FPGA to program its logic and routing . 5. **Testing:** The implemented design on the FPGA is tested to ensure it functions correctly . --- ## Common mistakes to avoid - Review all topics thoroughly before exams - Pay attention to formulas and key definitions - Practice with examples provided in each section - Don't memorize without understanding the underlying concepts

| Term | Definition | |------|------------| | Half Adder | A combinational logic circuit that performs the addition of two single binary digits, producing a sum bit and a carry-out bit. The sum bit is the XOR of the two inputs, and the carry-out is the AND of the two inputs. | | Full Adder | A combinational logic circuit that adds three single binary digits: two input bits and a carry-in bit from a previous stage. It produces a sum bit and a carry-out bit. Its logic is typically defined as $S = A \oplus B \oplus C_{in}$ and $C_{out} = AB + AC_{in} + BC_{in}$. | | Ripple-Carry Adder | A multibit adder where the carry-out of each stage is fed as the carry-in to the next stage. This creates a chain reaction, or ripple, of carry propagation from the least significant bit to the most significant bit, leading to a slow execution time that depends on the number of bits. | | Carry-Lookahead Adder (CLA) | A type of multibit adder that significantly speeds up carry propagation. It achieves this by pre-calculating the carry-in for larger blocks of bits using generate ($G_i$) and propagate ($P_i$) signals, thereby reducing the delay associated with a ripple-carry adder. | | Generate Signal ($G_i$) | In carry-lookahead addition, the generate signal for column $i$, defined as $G_i = A_i B_i$. If this signal is 1, a carry is generated in that column regardless of the carry-in. | | Propagate Signal ($P_i$) | In carry-lookahead addition, the propagate signal for column $i$, defined as $P_i = A_i + B_i$. If this signal is 1, a carry-in to that column will propagate through to the carry-out. | | Block Propagate Signal | In carry-lookahead adders using blocks of bits, this signal indicates whether a carry-in to the block will propagate through all bits of that block to become the block's carry-out. For a 4-bit block, it is calculated as $P_{3:0} = P_3P_2P_1P_0$. | | Block Generate Signal | In carry-lookahead adders using blocks of bits, this signal indicates whether a carry will be generated within the block. For a 4-bit block, it is calculated as $G_{3:0} = G_3 + G_2P_3 + G_1P_2P_3 + G_0P_1P_2P_3$. | | Prefix Adder | A highly parallel adder architecture that computes carry prefixes, which are signals indicating whether a carry will be generated or propagated through a range of bits. This architecture allows for very fast carry computation, with a delay proportional to the logarithm of the number of bits. | | Subtracter | A digital circuit that performs subtraction. It can be implemented using an adder by taking the two's complement of the subtrahend and adding it to the minuend, i.e., $A - B = A + (\text{NOT } B) + 1$. | | Comparator | A digital circuit that compares two binary numbers to determine their relationship (e.g., equal, less than, greater than). Equality comparators check if all corresponding bits are the same, while signed comparators often use subtraction and check the status flags of the ALU. | | Arithmetic Logic Unit (ALU) | A fundamental digital circuit that performs arithmetic and logic operations on operands. It typically includes an adder, subtracter, logic gates (AND, OR, XOR), and multiplexers controlled by an operation code to select the desired function. | | Status Flags | Bits that indicate the outcome of an ALU operation. Common flags include Negative (N, most significant bit of the result), Zero (Z, set if the result is all zeros), Carry (C, generated by the adder's carry-out), and Overflow (V, indicating an invalid result for signed arithmetic). | | Shifter | A digital circuit that shifts the bits of a binary word to the left or right. Logical shifters fill empty positions with zeros, while arithmetic shifters fill empty positions with the sign bit during right shifts to preserve the number's sign. Rotators shift bits circularly. | | Multiplier | A digital circuit that performs multiplication of two binary numbers. It typically involves generating partial products by multiplying the multiplicand with each bit of the multiplier and then summing these partial products. | | Divider | A digital circuit that performs division of two binary numbers, producing a quotient and a remainder. The process often involves repeated subtraction and shifting operations, similar to long division. | | Fixed-Point Number | A number representation where the binary point (radix point) has a fixed position. The number of bits allocated for the integer part and the fractional part is predefined, allowing for a specific range and precision. | | Floating-Point Number | A number representation that allows for a wider dynamic range than fixed-point numbers. It consists of a sign bit, an exponent, and a mantissa (fraction), similar to scientific notation. The IEEE 754 standard is commonly used for its representation. | | Mantissa | The fractional part of a floating-point number, typically normalized such that the most significant bit is always 1 (implicit leading 1). It determines the precision of the number. | | Exponent | The part of a floating-point number that determines the magnitude or scale of the number. It is often stored in a biased form to represent both positive and negative exponents. | | IEEE 754 Standard | A technical standard for floating-point arithmetic that defines formats for representing numbers (single-precision 32-bit, double-precision 64-bit) and specifying the behavior of arithmetic operations, including special values like infinity and NaN (Not a Number). | | Saturating Arithmetic | A type of arithmetic that prevents overflow by clamping the result to the maximum or minimum representable value when an overflow occurs, rather than wrapping around. This is useful in applications like signal processing to avoid audible or visible artifacts. | | Counter | A sequential logic circuit that generates a sequence of distinct values in response to clock pulses. Counters are used for timing, sequencing operations, and in applications like digital clocks and program counters. | | Shift Register | A sequential logic circuit that shifts its stored bits one position to the left or right on each clock pulse. They are used for serial-to-parallel conversion, parallel-to-serial conversion, and creating time delays. | | Memory Array | A two-dimensional arrangement of bit cells used to store digital data. It consists of rows (wordlines) and columns (bitlines), addressed by an address decoder to select specific memory words for reading or writing. | | DRAM (Dynamic Random Access Memory) | A type of RAM that stores each bit of data in a separate capacitor within an integrated circuit. It requires periodic refreshing to maintain data due to charge leakage from the capacitors. | | SRAM (Static Random Access Memory) | A type of RAM that uses flip-flops (typically cross-coupled inverters) to store each bit. It does not require refreshing as long as power is supplied and is generally faster but more expensive and less dense than DRAM. | | ROM (Read-Only Memory) | A type of non-volatile memory that stores data permanently or semi-permanently. Data is read quickly, but writing is typically impossible or very slow. Flash memory is a modern type of ROM. | | PLA (Programmable Logic Array) | A type of programmable logic device that consists of a programmable AND array followed by a programmable OR array. It is used to implement combinational logic functions. | | FPGA (Field-Programmable Gate Array) | A type of programmable logic device that consists of an array of configurable logic elements (LEs), programmable interconnections, and input/output blocks. FPGAs can implement both combinational and sequential logic and are widely used for prototyping and custom hardware development. | | Logic Element (LE) | The basic building block within an FPGA. An LE typically contains lookup tables (LUTs) for combinational logic and flip-flops for sequential logic, along with multiplexers for configuration. | | LUT (Lookup Table) | A combinational logic circuit implemented as a small memory. A $k$-input LUT can implement any boolean function of $k$ variables by storing the function's truth table in its memory locations. |