Booth’s Algorithm और Floating Point

/ कंप्यूटर फंडामेंटल्स / 10 minutes of reading

Booth’s Algorithm (बूथ्स एल्गोरिदम)

Booth’s Algorithm एक binary multiplication technique है, जो signed numbers (positive और negative दोनों) को efficiently multiply करने के लिए use होती है। यह algorithm 2’s complement representation और arithmetic shift का उपयोग करके multiplication के steps को कम करता है और hardware-friendly बनाता है। Key Points
  • यह signed binary numbers के लिए design किया गया है।
  • Negative numbers को 2’s complement form में handle करता है।
  • Multiplier और Multiplicand को examine करके patterns (Q0 और Q−1) के अनुसार add, subtract या skip operations perform करता है।
  • हर step में arithmetic right shift करके result update करता है।
  • Hardware-friendly algorithm है, इसलिए CPUs और ALUs में आसानी से implement किया जा सकता है।
  • Efficiency बढ़ाता है क्योंकि repetitive 1s या 0s वाले sequences में unnecessary operations skip हो जाते हैं।

objective of Booth's Algorithm (उद्देश्य)

1. Signed Numbers के साथ Multiplication

  • Simple binary multiplication केवल positive numbers के लिए आसान होती है।
  • Negative numbers multiply करना मुश्किल होता है क्योंकि sign handling जरूरी होती है।
  • Booth’s Algorithm यह सुनिश्चित करता है, कि positive और negative दोनों numbers सही तरीके से multiply हों।
  • Example

Multiplier = −3
Multiplicand = 6
Result = −18

  • Normal binary multiplication में error हो सकता है।
  • Booth’s Algorithm 2’s complement और pattern recognition का उपयोग करके सही result देता है।

2. Computation Efficiency बढ़ाना (Reduce Operations)

  • Normal binary multiplication में हर bit के लिए add/subtract करना पड़ता है।
  • Booth’s Algorithm pattern analysis (Q0 और Q−1) के आधार पर केवल आवश्यक add/subtract करता है।
  • repeated 1s या 0s वाले sequences में unnecessary operations skip हो जाते हैं।
  • Example

Multiplier : 00001111 (decimal 15)
Normal multiplication → 4 adds
Booth’s Algorithm → only 1 add + shifts

3. Hardware-Friendly Implementation

  • Booth’s Algorithm को CPU और ALU में आसानी से implement किया जा सकता है।
  • यह arithmetic right shift और add/subtract operations का combination use करता है।
  • Hardware में multiplication fast और efficient हो जाता है।
  • Example : Booth’s Algorithm CPU level पर signed multiplication को optimize करता है।

4. 2’s Complement Representation का Support

  • Negative numbers को 2’s complement में represent करना जरूरी होता है।
  • Booth’s Algorithm automatically 2’s complement numbers handle करता है।
  • Sign bit और magnitude दोनों सुरक्षित रहते हैं।

5. Simplified Multiplication Process

  • Signed binary multiplication normal method से complex होती है।
  • Booth’s Algorithm इसे systematic और structured steps में divide करता है:
    • Initialize registers (A, Q, Q − 1)
    • Check pattern (Q0 Q − 1)
    • Add/Subtract if necessary
    • Arithmetic right shift
    • Repeat until count = 0

Booth’s Algorithm Steps (मुख्य चरण)

Step 1: Initialize Registers

  • A (Accumulator) = 0
  • Q = Multiplier (number to be multiplied)
  • M = Multiplicand (number जिससे multiply करना है)
  • Q − 1 = 0 (Extra bit to track previous LSB)
  • Count = Number of bits in Multiplier

Step 2: Examine Last Two Bits (Q0 और Q−1)

  • Q0 Q − 1 = 01 → A = A + M
  • Q0 Q − 1 = 10 → A = A − M
  • Q0 Q − 1 = 00 या 11 → No operation
  • यह step pattern recognition कहलाता है, और unnecessary operations को skip करता है।

Step 3: Arithmetic Right Shift (ARS)

  • Step 2 के बाद A, Q और Q − 1 को right shift करना होता है।
  • Arithmetic Right Shift में MSB (sign bit) preserve होता है।
  • Shift करने से result gradually update होता है।

Step 4: Decrement Count

  • Count = Count − 1
  • जब Count = 0 हो जाए, तो algorithm terminate कर देता है।

Step 5: Repeat Steps 2–4

  • Pattern check → Add/Subtract → Arithmetic Right Shift
  • यह loop तब तक चलता है जब तक Count = 0 न हो जाए।

Step 6: Final Product

  • Result = Concatenate (A और Q)
  • यह signed multiplication का final product होता है।

Example (उदाहरण)

Multiplier (Q) = 3, Multiplicand (M) = −6

  • Multiplier = 3 → 0011 (4-bit binary)
  • Multiplicand = −6 → 1010 (4-bit 2’s complement)

Step 1: Initialize Registers

RegisterValue
A0000
Q0011
M1010
Q−10
Count4

Step 2: Step‑by‑Step Table

StepQ0 Q−1OperationA (Before)A (After)Shift Right (A, Q, Q−1)Count
11 0A = A − M00000000 − 1010 = 0110ARS → A=0011, Q=0001, Q−1=14→3
21 1No Operation00110011ARS → A=0001, Q=1000, Q−1=13→2
30 1A = A + M00010001 + 1010 = 1011ARS → A=1101, Q=0100, Q−1=02→1
40 0No Operation11011101ARS → A=1110, Q=0010, Q−1=01→0

Step 3: Final Product

  • After Count = 0, concatenate A और Q
  • A = 1110, Q = 0010
  • Product = 11100010 (8-bit binary)
  • Decimal = −18
  • Answer : −18

Rules of Booth’s Algorithm (नियम)

Rule1: (Q0 Q − 1) = 01
  • A = A + M
  • फिर Arithmetic Right Shift करो
Rule2: (Q0 Q − 1) = 10
  • A = A − M
  • फिर Arithmetic Right Shift करो
Rule3: (Q0 Q − 1) = 00 या 11
  • कोई Add/Sub नहीं
  • बिना addition/subtraction के shift करो

Why Booth’s Algorithm? (क्यों आवश्यक है?)

1. Signed Numbers को Easily Multiply करने के लिए
  • Normal binary multiplication positive numbers के लिए simple होती है।
  • लेकिन real-world में हमें negative numbers (−5, −10, −20 etc.) भी multiply करने पड़ते हैं।
  • Booth’s Algorithm positive और negative दोनों numbers को बिना extra complexity के handle करता है।
2. 2’s Complement Representation को Support करता है
  • Computers negative numbers को 2’s complement में store करते हैं।
  • Booth’s Algorithm specially 2’s complement numbers के लिए design किया गया है।
  • इससे sign bit और magnitude दोनों safely preserved रहते हैं।
3. Unnecessary Add / Subtract Operations को Reduce करता है
  • Traditional multiplication में हर ‘1’ bit के लिए addition करना पड़ता है।
  • Booth’s Algorithm Q0 और Q − 1 pattern check करके:
    • केवल जरूरी time पर add या subtract करता है
    • repetitive bits वाले cases में operations skip कर देता है
4. Hardware Implementation को Efficient बनाता है
  • Booth’s Algorithm add, subtract और arithmetic right shift का combination use करता है।
  • ये operations ALU (Arithmetic Logic Unit) में easily available होते हैं।
  • इसलिए hardware design simple और cost-effective बनता है।
  • यही reason है कि modern CPUs में signed multiplication के लिए Booth-type logic use किया जाता है।
5. Speed और Performance Improve करता है
  • Multiplication computer का सबसे time-consuming arithmetic operation होता है।
  • Booth’s Algorithm:
    • कम clock cycles लेता है
    • fast execution देता है

Booth’s Algorithm -Advantages (लाभ)

  1. Supports Signed Binary Multiplication
    • Booth’s Algorithm positive और negative दोनों numbers के साथ multiplication कर सकता है।
    • Sign handling automatically होती है, जिससे error की संभावना कम हो जाती है।
  2. 2’s Complement Friendly Algorithm
    • Negative numbers को direct 2’s complement form में process करता है।
    • Separate sign handling की जरूरत नहीं होती।
  3. Reduces Unnecessary Operations
    • Repeated 1s या 0s वाले bit patterns में extra add/subtract steps skip कर देता है। इससे computation efficient बनती है।
  4. Fast Execution (High Speed)
    • कम clock cycles में result produce करता है।
    • Overall system performance improve होती है।
  5. Hardware-Friendly Design
    • ALU में आसानी से implement किया जा सकता है।
    • केवल Add, Subtract और Arithmetic Right Shift operations का use होता है।
  6. Efficient for long bit sequences
    • Multiplier में continuous 1s होने पर operations की संख्या काफी कम हो जाती है।
    • Large binary numbers के लिए यह method ज्यादा effective है।
  7. Widely Used in CPU Design
    • Modern processors में signed multiplication के लिए Booth’s logic का use किया जाता है।
    • यह hardware optimization में मदद करता है।

Booth’s Algorithm – Disadvantages (हानियाँ)

  1. The Algorithm is somewhat Complex
    • Normal binary multiplication की तुलना में समझना और implement करना कठिन होता है।
  2. An additional register/bit is required
    • Additional register/bit required होता है।
    • इससे hardware complexity बढ़ जाती है।
  3. Less Effective with Alternating Bit Patterns
    • जैसे: 101010… pattern वाले multipliers में advantage कम मिलता है।
    • Operations reduce नहीं हो पाते।
  4. Careful Implementation is Necessary
    • Arithmetic right shift और sign bit handling में छोटी सी गलती भी wrong result दे सकती है।
  5. Higher Overhead for Small Numbers
    • Very small multiplications के लिए Booth’s Algorithm unnecessary complex हो जाता है।
    • ऐसे cases में normal multiplication method ज्यादा simple होता है।

Floating Point Representation

Floating Point Representation एक technique है, जिसके द्वारा Computer real numbers (decimal numbers) जैसे 3.14, 0.005, -125.75 आदि को binary format में store और process करता है। इस method में number को scientific notation की तरह represent किया जाता है |

Number = Mantissa × Base^Exponent

  • यहाँ base हमेशा 2 (binary system) होती है।

Key Points

  • Decimal और fractional numbers को represent करने के लिए use होती है
  • Scientific notation (जैसे101 × 2³) पर based होती है
  • तीन main parts होते हैं: Sign bit, Exponent, Mantissa (Significand)
  • Very large और very small numbers दोनों को handle कर सकती है
  • Modern computers में IEEE 754 standard follow किया जाता है
  • Precision mantissa bits पर depend करती है

 Example

  • 5000000 = 5 × 10⁶
  • 00045 = 4.5 × 10⁻⁴

Why Floating Point Representation is Needed?
(आवश्यकता क्यों है?)

  1. Decimal Numbers को Represent करने के लिए
    1. Computer integer numbers आसानी से store कर सकता है, लेकिन 3.5, 0.25, 99.99 जैसे decimal numbers के लिए Floating Point जरूरी है।
  2. Very Large Numbers को Handle करने के लिए
    Scientific fields (जैसे ISRO, Astronomy) में बहुत बड़े numbers होते हैं, जिन्हें normal integer format handle नहीं कर सकता।
  3. Very Small Numbers के लिए
    Medical, physics और nano-technology में बहुत छोटी values (जैसे 0.000001) होती हैं, जिन्हें Floating Point आसानी से represent करता है।
  4.  Scientific और Engineering Calculations के लिए
    Distance, speed, temperature, pressure जैसी calculations Floating Point के बिना possible नहीं हैं।
  5. Wide Range of Values Provide करता है
    Floating Point Representation limited range की जगह very wide range के numbers को support करता है।

Basic Components of Floating Point Representation (मूल घटक)

Floating Point Representation में किसी भी real number को तीन मुख्य parts में divide करके store किया जाता है। ये components मिलकर decimal number को binary form में represent करते हैं।

  1. Sign Bit (S)
    • Sign Bit यह बताता है कि number positive है या negative।
    • Sign Bit = 0 → number positive
    • Sign Bit = 1 → number negative
    • Example
      • +12.5 → Sign Bit = 0
      • −12.5 → Sign Bit = 1
  2. Exponent (E)
    • Exponent यह बताता है कि binary point को कितनी positions shift करना है।
    • यह number के range (size) को represent करता है।
    • IEEE 754 standard में exponent को store करते समय bias add किया जाता है।
    • Example
      • 1.101 × 2³
      • यहाँ exponent = 3
  3. Mantissa / Significand (M)
    • Mantissa actual significant digits को store करता है।
    • Floating Point number की precision mantissa पर depend करती है।
    • Normalized form में mantissa हमेशा 1.xxxxx format में होता है।
    • Example
      • 1.101 × 2³
      • यहाँ mantissa = 1.101

Convert Decimal to Floating Point Representation

Example : Convert 25.75 into Binary Floating Point

Step 1: Convert Integer Part to Binary

  • (25)₁₀ = (11001)₂

Step 2: Convert Fractional Part

  • 0.75 × 2 = 1.5 → 1
  • 0.5 × 2 = 1.0 → 1
  • (0.75)₁₀ = (.11)₂

Step 3: Combine

  • (25.75)10 = (11001.11)₂

Step 4: Normalize

  • 11001.11 = 1.100111 × 2⁴

Final Floating Point Form:

  • Mantissa = 1.100111
  • Exponent = 4

Advantages of Floating Point Representation (लाभ)

  1. Represents Decimal / Real Numbers
    • Floating Point Representation की help से fractional और real numbers (जैसे 3.14, 0.25, 99.99) को Computer में store किया जा सकता है।
  2. Handles Very Large Numbers
    • Scientific calculations (जैसे space distance, astronomy data) में आने वाले बहुत बड़े numbers को easily represent करता है।
  3. Useful for Very Small Numbers
    • Medical, physics और engineering fields में आने वाली बहुत छोटी values (जैसे 0.000001) को represent करने में helpful है।
  4. Provides Wide Range of Values
    • Integer representation की तुलना में Floating Point बहुत बड़ा range cover करता है।
  5. Essential for Scientific and Engineering Calculations
    • Temperature, speed, pressure, AI models, graphics processing जैसी calculations Floating Point के बिना possible नहीं हैं।

Disadvantages of Floating Point Representation (हानियाँ)

  1. Exact Precision Is Not Guaranteed
    • सभी decimal numbers binary में exactly represent नहीं हो पाते, जिससे rounding errors हो सकते हैं।
  2. Complex Hardware Required
    • Floating Point operations के लिए special hardware (FPU – Floating Point Unit) की आवश्यकता होती है।
  3. Slower Than Integer Operations
    • Floating Point calculations, integer calculations की तुलना में slow होती हैं।
  4. Care Required in Programming
    • Banking और financial applications में गलत rounding से errors आ सकते हैं।

Conclusion (निष्कर्ष)

Booth’s Algorithm एक efficient signed binary multiplication technique है, जो 2’s complement representation और arithmetic right shift का use करके unnecessary add/subtract operations को reduce करता है। यही वजह है कि CPU, ALU और modern processor design में widely used है।

Floating Point Representation computer को real numbers (decimal values) जैसे very large और very small numbers handle करने की power देता है। IEEE 754 standard floating point calculations को standardized और portable बनाता है, हालाँकि precision और rounding errors इसकी natural limitations हैं।

अक्सर पूछे जाने वाले प्रश्न (FAQ)

Q1. Booth’s Algorithm क्या है?

  • Booth’s Algorithm एक binary multiplication algorithm है, जो signed numbers (positive और negative) को efficiently multiply करने के लिए use होती है।

Q2. Booth’s Algorithm में Q0 और Q−1 का क्या role है?

  • Q0 और Q−1 bits का use bit pattern detect करने के लिए किया जाता है, जिससे decide होता है कि add, subtract या no operation perform करना है।

Q3. Booth’s Algorithm में Arithmetic Right Shift क्यों use किया जाता है?

  • Arithmetic Right Shift sign bit को preserve करता है, जिससे signed numbers का correct result मिलता है।

Q4. Floating Point Representation क्या है?

  • Floating Point Representation एक technique है, जिससे computer decimal / real numbers को binary scientific notation के form में store और process करता है।

Q5. IEEE 754 standard क्यों important है?

  • IEEE 754 floating point numbers के लिए एक international standard है, जो consistency, accuracy और compatibility ensure करता है।

Q6. Floating Point Representation में error क्यों आता है?

  • क्योंकि सभी decimal numbers binary में exactly represent नहीं हो पाते, इसलिए rounding errors possible होते हैं।

Q7. Booth’s Algorithm और Floating Point Arithmetic का practical use कहाँ है?

  • Booth’s Algorithm → CPU, ALU, processor design
  • Floating Point Arithmetic → scientific calculation, banking software, AI, graphics, ISRO missions

Related Posts

Start typing and press enter to search

error: Content is protected !!

DCA के सभी नोट्स,
पुराने पेपर और महत्वपूर्ण प्रश्न उत्तर

PGDCA के सभी नोट्स,
पुराने पेपर और महत्वपूर्ण प्रश्न उत्तर