arithmetic

1's Complement:

A method of representing signed binary numbers where positive numbers are represented as their true binary form, and negative numbers are formed by inverting all the bits of their positive counterpart.

To negate a binary number, "invert 0 to 1 and 1 to 0." For example,  "0010 -> 1101". 

∙ 2's Complement:

The standard method for representing signed binary numbers in computers. Positive numbers are their true binary form; negative numbers are formed by inverting all bits of the positive counterpart and then adding 1.

This is the standard for signed numbers in modern computers.  "Every computer today uses 2’s complement binary representations for signed  numbers." 

The universal method for representing signed numbers in modern  computers. 

∙ ALU (Arithmetic Logic Unit):

A digital circuit within the CPU that performs arithmetic (addition, subtraction, etc.) and logical (AND, OR, NOT, etc.) operations on binary numbers.

∙ AND Gate:

A basic digital logic gate whose output is 1 only if all its inputs are 1.

∙ Arithmetic Right Shift:

A bitwise operation that shifts the bits of a binary number to the right, filling the vacated leftmost bits with the original sign bit (0 for positive, 1 for negative) to preserve the number's sign.

∙ Binary:

A base-2 number system that uses only two symbols: 0 and 1. It is the fundamental language of computers.

∙ Booth's Algorithm:

An algorithm for multiplying signed binary numbers eiciently, especially those in 2's complement representation, by examining pairs of bits in the multiplier.

A specialized algorithm for signed multiplication. ∙ Examines two bits of the multiplier (current and previous).

∙ CarryIn:

An input to an adder circuit representing a carry from a less significant bit position.

∙ CarryOut:

An output from an adder circuit representing a carry generated to a more significant bit position.

∙ Decimal:

A base-10 number system that uses ten unique symbols (0-9).

∙ Full Adder:

A digital circuit that adds three binary inputs (two data bits and a carry in bit) and produces two outputs (sum and carry-out).

∙ Half Adder:

A digital circuit that adds two binary inputs (data bits) and produces two outputs (sum and carry-out), without a carry-in input.

A simpler adder with only a and b inputs, producing Sum and CarryOut  but no CarryIn. 

∙ Hexadecimal:

A base-16 number system that uses 16 unique symbols (0-9 and A F). Often used as a shorthand for binary.

∙ Inverter (NOT Gate):

A basic digital logic gate whose output is the logical opposite of its single input.

Output is the opposite of the input. 

∙ Logical Right Shift (srl):

A bitwise operation that shifts the bits of a binary number to the right, filling the vacated leftmost bits with zeros.

∙ Multiplicand:

The number that is being multiplied in a multiplication operation.

∙ Multiplier:

The number by which the multiplicand is multiplied in a multiplication operation.

∙ Multiplexor (MUX):

A combinational logic circuit that selects one of several input lines and directs it to a single output line based on a set of control inputs.

Selects one of several input signals and forwards the selected  input into a single output line based on a control signal.

∙ Negate:

In the context of 2's complement, to find the additive inverse of a number (i.e., its negative counterpart). Achieved by inverting all bits and adding 1.

∙ Number System:

A system for representing numbers using digits or other symbols in a consistent manner.

∙ Octal:

A base-8 number system that uses eight unique symbols (0-7). ∙ OR Gate: A basic digital logic gate whose output is 1 if at least one of its inputs is 1. ∙ Product: The result of a multiplication operation.

∙ Ripple Carry Adder:

A digital adder circuit composed of multiple full adders connected in series, where the carry-out of one stage feeds directly into the carry-in of the next stage.

 Created by connecting multiple 1-bit full adders in series,  where the CarryOut of one stage becomes the CarryIn of the next. 

∙ Signed Numbers:

Numbers that can represent both positive and negative values. In binary, often represented using 2's complement.

∙ Sign Extension:

The process of expanding a smaller number of bits to a larger number of bits while preserving the sign and value of the number, typically by replicating the sign bit into the new, more significant bit positions.

∙ Sign Bit:

The leftmost (most significant) bit in a signed binary number, indicating whether the number is positive (0) or negative (1).

∙ Sign Bit:

 "Leading 0s mean positive, and leading 1s mean negative." 

∙ Negation Shortcut:

To negate a 2's complement number: "Invert 0 to 1 and 1 to 0. – Then add 1." The document illustrates this with "0000 0000 0000 0111 = 7" and its  negation "1111 1111 1111 1001 = -7". 

∙ Relationship between negation and inversion

 The document highlights that "-a =  a + 1", where 'a' is the inverted form of 'a'. It explicitly states, "Note: negate and invert  are dierent!" 

Sign Extension:

When converting smaller bit values (e.g., 8-bit) to larger ones (e.g.,  32-bit), "copy the most significant bit (the sign bit) into the 'empty' bits." For  example, "1010 -> 1111 1010". 

∙ Addition and Subtraction: 

∙ "Subtraction uses addition." This is achieved by negating the subtrahend (second  operand) using 2's complement and then adding. For example, "7 – 6 = 7 + (-6) = 1".

∙ The process for a - b in 2's complement is a + (-b) = a + (b + 1). 

∙ sll

(shift left logical) / << (shift left)

∙ srl

(shift right logical) / >> (shift right)

∙ and, andi

&(bit-by-bit AND)

∙ or, ori

/ | (bit-by-bit OR)

∙ Terminology:

"First operand: Multiplicand," "Second operand: Multiplier," "Result:  Product."

∙ Binary Multiplication Process:

"Binary multiplication is just a bunch of right shifts  and adds." The process involves: 

1. Placing a copy of the multiplicand (shifted) if the multiplier digit is 1. 2. Placing 0 if the multiplier digit is 0. 

∙ First Version (Conceptual)

Uses a 64-bit ALU, 64-bit product register (initially 0),  and a 32-bit multiplier. Involves repeatedly testing the least significant bit of the  multiplier, adding the multiplicand to the product if it's 1, shifting the multiplicand  left, and shifting the multiplier right.

∙ Refined Version (Eicient):

Optimizes space by combining the right half of the  product with the multiplier. The "Product register has wasted space. => The  rightmost half of the product is combined with the multiplier." This version uses a  32-bit ALU and a 64-bit product register, where the left half receives the addition  result and the entire product register is shifted right.

∙ Signed Multiplication:

The "Easiest Way: Convert the multiplier and multiplicand to  positive numbers and then remember the original sign." The add-and-shift method  can work for signed numbers as well. 

∙ Signed Multiplication: ∙ Booth's Algorithm:

A specialized algorithm for signed multiplication that "looks at 2  bits of the multiplier." It performs operations based on the current and previous  multiplier bits

∙ Requires Arithmetic Right Shift to preserve the sign of the intermediate result when  shifting the product. arithmetic and logical operations.

 ∙ 00:

No arithmetic, middle of 0s.

∙ 01:

Add multiplicand, end of 1s string.

 10:

Subtract multiplicand, beginning of 1s string. 

∙ 11:

No arithmetic, middle of 1s. 

1. Explain the primary reason why 2's complement is the preferred method for  representing signed numbers in modern computers compared to 1's complement. 

1. 2's complement is preferred over 1's complement primarily because it has a unique  representation for zero (only one '0'). This avoids the ambiguity and complexity of  having both positive and negative zero found in 1's complement. Additionally, 2's  

complement simplifies arithmetic operations, especially subtraction, by allowing it  to be performed directly as addition.

2. Describe the process of converting a positive 4-bit binary number into its negative  2's complement representation. Use an example if it helps clarify.

2. To convert a positive 4-bit binary number to its negative 2's complement, you first  invert all its bits (0s become 1s, and 1s become 0s). Then, you add 1 to the result of  this inversion. For example, to negate 0010 (2), you invert to 1101, then add 1,  resulting in 1110 (-2).

3. What is the significance of the "leading 0s mean positive, and leading 1s mean  negative" rule in 2's complement representation? 

3. In 2's complement, the leftmost bit (Most Significant Bit or MSB) serves as the sign  bit. A leading 0 indicates a non-negative number, while a leading 1 indicates a  negative number. This convention is crucial for quickly determining the sign of a 2's  complement number and is fundamental to how computers interpret signed binary  values.

4. How does a computer perform subtraction using only addition operations? 

4. A computer performs subtraction by leveraging its addition capabilities and the 2's  complement system. To calculate a - b, the computer first finds the 2's complement  of b (which eectively negates b to -b). It then adds a to this 2's complement of b  (i.e., a + (-b)), thereby achieving subtraction through addition.

5. Dierentiate between a logical right shift (srl) and an arithmetic right shift,  particularly in the context of Booth's Algorithm. 

5. A logical right shift (srl) moves all bits to the right and fills the vacated leftmost bits  with zeros. An arithmetic right shift, crucial for Booth's Algorithm, also shifts bits  right but fills the vacated leftmost bits with the original sign bit. This preserves the  sign of the number during the shift operation, which is essential for correct signed  multiplication.

6. List the four basic hardware building blocks mentioned in the context of ALU design  and briefly state the function of each

6. The four basic hardware building blocks are: AND gate (output is 1 only if all inputs  are 1), OR gate (output is 1 if at least one input is 1), Inverter (output is the opposite  of the input), and Multiplexor (selects one of multiple inputs to pass to its single  output based on a control signal).

7. What is the role of a multiplexor in the design of a 1-bit ALU that performs both AND  and OR operations?

7. In a 1-bit ALU designed to perform both AND and OR operations, a multiplexor acts  as a selector. Based on an "Operation" control signal, the multiplexor chooses  either the output of the AND gate or the output of the OR gate to be the final result of  the 1-bit logical unit. This allows the ALU to perform dierent logical functions  based on the instruction.

. Explain the relationship between an n-bit multiplicand and an m-bit multiplier  regarding the length of their product. Provide an example.

8. When an n-bit multiplicand is multiplied by an m-bit multiplier, the resulting product  will be (n+m) bits long. This is because multiplication can potentially double the  number of bits required to represent the maximum possible value. For example,  

multiplying a 4-bit number (like 1111) by another 4-bit number (1111) can result in  an 8-bit product.

9. Describe the core principle behind the "refined version" of the multiplication  algorithm in terms of how it optimizes space.

9. The "refined version" of the multiplication algorithm optimizes space by combining  the multiplier register with the rightmost half of the product register. Instead of  having separate registers for the multiplier and the entire product, the partial  product is shifted right, eectively moving bits from the product's left half into the  space previously occupied by the multiplier bits. This reduces the total register  space needed.

 In Booth's Algorithm, what actions are taken when the multiplier bits (current and  previous) are "01" and "10" respectively? 

10. In Booth's Algorithm, if the current and previous multiplier bits are "01", it indicates  the end of a string of 1s, and the multiplicand is added to the left half of the product.  If the bits are "10", it signifies the beginning of a string of 1s, and the multiplicand is  subtracted from the left half of the product.

 CarryOut Logic:

 CarryOut = (a AND b) OR (CarryIn AND (a XOR b)) (or derived from  its truth table).

∙ Sum Logic:

Sum = (a XOR b) XOR CarryIn (or derived from its truth table).

∙ Outputs:

Sum, CarryOut. 

1. Compare and contrast the concepts of 1's complement and 2's complement  representations for signed binary numbers. Discuss their respective advantages and  disadvantages, explaining why 2's complement has become the standard in modern  computing architectures.

2. Detail the step-by-step process of binary multiplication as performed by a computer  using the "refined version" of the algorithm. Illustrate with a small example (e.g., 4- bit numbers) and explain how the algorithm optimizes the use of registers.

3. Explain the fundamental components and logic behind a 1-bit full adder. Derive or  explain the logical expressions for both the Sum and CarryOut outputs based on the  inputs a, b, and CarryIn. How are multiple 1-bit full adders combined to form a 32- bit Ripple Carry Adder?

. Describe Booth's Algorithm for signed binary multiplication. Explain its core  principle of looking at two bits of the multiplier and how dierent bit patterns (00, 

01, 10, 11) lead to specific arithmetic or no-operations. Discuss the importance of  the arithmetic right shift in this algorithm.

5. Discuss the role of the Arithmetic Logic Unit (ALU) within a computer system.  Explain how the basic hardware building blocks (AND, OR, Inverter, Multiplexor) are  combined to create a functional 1-bit ALU capable of performing both logical and  arithmetic operations, including subtraction.

Product:

The result of a multiplication operation. 

∙ Structure:

 Each bit position has its own 1-bit ALU, with carries propagated from the  least significant bit (LSB) to the most significant bit (MSB). 

∙ 1-Bit Full Adder:Inputs:

a, b, CarryIn.

1-Bit Logical Unit:

Combines AND and OR gates with a multiplexor to select the  operation. 

OR Gate:

 Output is 1 if at least one input is 1. 

AND Gate:

Output is 1 only if all inputs are 1. 

∙ ALU:

The digital circuit that performs arithmetic (addition, subtraction) and logical  (AND, OR) operations. 

∙ Arithmetic Right Shift

Preserves the sign bit when shifting the product. III. Arithmetic Logic Unit (ALU) Design 

Signed Multiplication:Easiest Way:

Convert to positive, multiply, then determine  the final sign. 

Refined Multiplication Algorithm:

Optimizes the process by combining the  multiplier and the product's right half to save space and reduce the number of  registers. 

∙ Binary Multiplication Process:

Essentially a series of shifts and additions.

∙ If the multiplier digit is 1, add a shifted copy of the multiplicand. 

∙ If the multiplier digit is 0, add 0 (or just shift). 

∙ Product Length:

An n-bit multiplicand and m-bit multiplier yield an (n+m)-bit  product. 

Product

The result of multiplication. 

 Multiplier:

The second operand. 

∙ Multiplicand:

The first operand. 

Purpose:

 Bit-by-bit manipulation of binary numbers. 

∙ MIPS Instructions / C Operators:

sll / << (shift left logical): Shifts bits to the left,  filling with zeros. 

∙ srl / >> (shift right logical):

Shifts bits to the right, filling with zeros. ∙ and, andi / &

(bit-by-bit AND):

 Produces 1 if both corresponding bits are 1, else 0. ∙ or, ori / |

(bit-by-bit OR):

Produces 1 if at least one corresponding bit is 1, else 0. C. Multiplication 

∙ Subtraction using Addition:

Subtraction is performed by adding the negated (2's  complement) value of the subtrahend. 

∙ a - b = a + (-b) 

∙ This is equivalent to a + (b_inverted + 1).

∙ ALU Design for Subtraction:

 Involves inverting the 'b' input and setting the least  significant CarryIn bit to 1 for addition. 

∙ Limitations:

Less commonly used than 2's complement due to issues like having  two representations for zero (+0 and -0).

∙ Negation:

: Invert all bits (0 to 1, 1 to 0).

∙ Relationship between 'a' and '-a':

 a + a_inverted = -1. Therefore, -a = a_inverted + 1. C. 1's Complement 

∙ Sign Extension:

Converting a smaller bit-value (e.g., 8-bit) to a larger one (e.g., 32- bit) involves copying the most significant bit (sign bit) into the "empty" leading bits.

∙ Negation (Inversion then Add 1):

 To negate a 2's complement number, invert all  bits (0 to 1, 1 to 0) and then add 1 to the result.

∙ Leading Bits:

 A leading 0 indicates a positive number; a leading 1 indicates a  negative number.

 Conversion:

Understand the methods for converting numbers between these  systems.

∙ Hexadecimal (Base-16):

 Uses digits 0-9 and A-F. Often used as a shorthand for  binary.

∙ Decimal (Base-10):

Uses digits 0-9. The common human number system. 

Octal (Base-8):

Uses digits 0-7

Binary (Base-2):

Uses 0 and 1. The fundamental system for computers.

∙ 32-Bit ALU (Ripple Carry Adder):

A 32-bit ALU is constructed "By connecting  adjacent 'black boxes'" (1-bit ALUs). The CarryOut of one 1-bit ALU becomes the  CarryIn of the next, forming a "Ripple Carry Adder." 

∙ Implementing Subtraction in ALU:

Achieved by converting a - b to a + (-b) = a + (b +  1). This is done by inverting the 'b' input (using Binvert) and setting the least  significant CarryIn to 1. 

∙ 1-Bit ALU:

Combines the 1-bit logical unit and the 1-bit full adder, using a  multiplexor controlled by an 'Operation' input to select between arithmetic  (addition) and logical operations. 

∙ Implementing Subtraction in ALU: Achieved by

 Half Adder:

A simpler adder with only two inputs (a, b) and outputs Sum and  CarryOut. 

∙ The document provides a truth table for the 1-bit full adder and expressions for  CarryOut = (b · CarryIn) + (a · CarryIn) + (a · b) and Sum = (a · b · CarryIn) + (a · b ·  CarryIn) + (a · b · CarryIn) + (a · b · CarryIn).

∙ 1-Bit Full Adder:

A circuit that adds three 1-bit inputs (a, b, CarryIn) and produces a  Sum and a CarryOut.