Location via proxy:   [ UP ]  
[Report a bug]   [Manage cookies]                
Everand Logo

Welcome to Everand!

  • Discover millions of ebooks, audiobooks, and so much more with a free trial

    From $11.99/month after trial. Cancel anytime.

    Complex Binary Number System: Algorithms and Circuits
    Complex Binary Number System: Algorithms and Circuits
    Complex Binary Number System: Algorithms and Circuits
    Ebook140 pages45 minutes

    Complex Binary Number System: Algorithms and Circuits

    By Tariq Jamil

    ()

    Read preview

    About this ebook

    This book is a compilation of the entire research work on the topic of Complex Binary Number System (CBNS) carried out by the author as the principal investigator and members of his research groups at various universities during the years 2000-2012. Pursuant to these efforts spanning several years, the realization of CBNS as a viable alternative to represent complex numbers in an “all-in-one” binary number format has become possible and efforts are underway to build computer hardware based on this unique number system.

    It is hoped that this work will be of interest to anyone involved in computer arithmetic and digital logic design and kindle renewed enthusiasm among the engineers working in the areas of digital signal and image processing for developing newer and efficient algorithms and techniques incorporating CBNS.
    LanguageEnglish
    PublisherSpringer
    Release dateOct 4, 2012
    ISBN9788132208549
    Complex Binary Number System: Algorithms and Circuits

    Related to Complex Binary Number System

    Related ebooks

    Electrical Engineering & Electronics For You

    View More
    View More

    Related podcast episodes

    Related articles

    • UNLIMITED

      What’s A Switch?

      Jan 11, 2021

      What’s A Switch?
      1 min read

    • UNLIMITED

      Use EBPF To Keep Tabs On Your CPU

      Oct 18, 2022

      Did you miss part one? Get hold of it on page 60 Mihalis Tsoukalos is a systems engineer and a technical writer. You can reach him at @mactsouk. We’re continuing our dive into the notoriously complex Extended Berkeley Packet Filter (eBPF) feature of

      9 min read

    • UNLIMITED

      Route Traffic Between Networks Using A Pi

      Jun 2, 2020

      A deep-dive into Pi networking solutions resulted in this tutorial. The goal was to uncover a Pi configuration that would enable the routing of network traffic from a wired network to a wireless network. The aim is to build a network router using a R

      10 min read

    • UNLIMITED

      STEM Online Learning Resources

      Sep 3, 2020

      STEM Online Learning Resources
      4 min read

    • UNLIMITED

      Math After COVID-19

      Apr 28, 2020

      Math After COVID-19
      4 min read

    • UNLIMITED

      Betting On A Drone Boom

      Jul 24, 2021

      Betting On A Drone Boom
      4 min read

    • UNLIMITED

      What Is The Future Of Game Streaming Now That Stadia Is Dead?

      Oct 31, 2022

      Once hyped as being ‘the future of gaming’, the Google Stadia game streaming service was officially, just three years after launch and before even making it to Australian shores. When game streaming first launched we did have some apprehension about

      2 min read

    • UNLIMITED

      Modular Arithmetic 101

      Dec 17, 2021

      Modular Arithmetic 101
      1 min read

    • UNLIMITED

      ALGOL: The Father Of Mainstream Languages

      May 2, 2023

      Mike Bedford hates to admit it, but he had his first experience with ALGOL before it fell out of favour, so getting to grips with it again was a trip down memory lane. I nthe latest instalment of our series on classic programming languages, we’re tur

      11 min read

    • UNLIMITED

      HotPicks

      Jul 27, 2021

      HotPicks
      12 min read

    • UNLIMITED

      Common Errors

      Aug 27, 2019

      If you receive a ‘Script not found’ error, this probably means that you don’t have the mod scripts installed in your Minecraft directory. Check that you’ve replaced .minecraft with the one from McPiFoMo; this should include mcpipy, which will be full

      1 min read

    • UNLIMITED

      The Cost of Cryptography: Computer security is trying to avoid wasting your time.

      Nov 14, 2013

      The VENONA project represents one of the most successful counter-intelligence attacks of the Cold War. It revolved around an encryption system, called the “one-time pad scheme,” that was completely unbreakable, but required generating a new, random e

      6 min read

    • UNLIMITED

      Interfacing To Single Board Computers

      Nov 16, 2021

      Mike Bedford With a degree in computer science, but a long standing interest in electronics, Mike likes to straddle the great divide with a foot in both camps - hardware and software. For many users, a major benefit of single board computers like the

      11 min read

    Related categories

    Reviews for Complex Binary Number System

    0 ratings

    0 ratings0 reviews

    What did you think?

    Tap to rate

    Review must be at least 10 words

      Book preview

      Complex Binary Number System - Tariq Jamil

      Tariq JamilSpringerBriefs in Electrical and Computer EngineeringComplex Binary Number System2013Algorithms and Circuits10.1007/978-81-322-0854-9_1© The Author(s) 2013

      1. Introduction

      Tariq Jamil¹  

      (1)

      Department of Electrical and Computer Engineering, Sultan Qaboos University, Muscat, 123, Oman

      Tariq Jamil

      Email: tjamil@squ.edu.om

      Abstract

      Complex numbers play a truly unique and important role in the realm of modern science and engineering. Using these numbers it is possible to locate a point within two dimensions of a Cartesian co-ordinate system. Therefore, these numbers are used extensively in digital signal processing algorithms and image processing applications. In this chapter we are going to review basic theory about complex numbers and arithmetic operations involving such type of numbers. This will enable us to justify the need for a more efficient representation of these numbers in computer architecture.

      1.1 What is a Complex Number?

      A complex number represents a point in a two-dimensional system and, in rectangular form, is written in the form $$ \left( {x + jy} \right) $$ where $$ x $$ , called the real part, denotes the position along the horizontal axis and y, called the imaginary part, denotes the position along the vertical axis. j is considered equivalent to $$ \sqrt { - 1} $$ and is used to represent the imaginary nature of the variable $$ y $$ . Another way of locating the point in a two-dimensional system is to use polar notation $$ r\angle \theta $$ where $$ r $$ represents the hypotenuse of length $$ \sqrt {x^{2} + y^{2} } $$ for a right-angled triangle having $$ x $$ as the base and $$ y $$ as the perpendicular, and $$ \theta $$ represents the angle made by the hypotenuse with the base of the triangle, given by $$ \tan^{ - 1} \frac{y}{x} $$ .

      1.2 Arithmetic Operations Involving Complex Numbers

      Arithmetic operations involving two complex numbers $$ (a + jb) $$ and $$ (c + jd) $$ are carried out as follows:

      Addition involves two individual additions, one for the real parts $$ (a + c) $$ and one for the imaginary parts $$ (b + d) $$ :

      $$ (a + jb) + (c + jd) = (a + c) + j(b + d) $$

      (1.1)

      Subtraction involves two individual subtractions, one for the real parts $$ (a - c) $$ and one for the imaginary parts $$ (b - d) $$ :

      $$ (a + jb) - (c + jd) = (a - c) + j(b - d) $$

      (1.2)

      Multiplication involves four individual multiplications $$ ac, ad, bc, bd $$ , one subtraction $$ac - bd$$ , and one addition $$ ad + bc $$ :

      $$ \left( {a + jb} \right) \times \left( {c + jd} \right) = ac + j\left( {ad + bc} \right) + j^{2} bd = \left( {ac - bd} \right) + j(ad + bc) $$

      (1.3)

      Division involves six individual multiplications $$ ac, ad, bc, bd, c^{2} , d^{2} $$ , two additions $$ac + bd$$ and $$ c^{2} + d^{2} $$ , one subtraction $$ bc - ad $$ , and then two individual divisions $$ \frac{ac + bd}{{c^{2} + d^{2} }} $$ and $$ \frac{bc - ad}{{c^{2} + d^{2} }} $$ :

      $$ \frac{{\left( {a + jb} \right)}}{{\left( {c + jd} \right)}} = \frac{{\left( {a + jb} \right)}}{{\left( {c + jd} \right)}} \times \frac{{\left( {c - jd} \right)}}{{\left( {c - jd} \right)}} = \frac{{ac + j\left( {bc - ad} \right) - j^{2} bd}}{{c^{2} - j^{2} d^{2} }} $$$$ = \frac{{\left( {ac + bd} \right) + j(bc - ad)}}{{c^{2} + d^{2} }} = \frac{ac + bd}{{c^{2} + d^{2} }} + j \frac{bc - ad}{{c^{2} + d^{2} }} $$

      (1.4)

      1.3 Justification for Complex Binary Number System

      Let’s assume that each individual addition/subtraction, involving complex numbers, takes $$ p $$ ns to complete and each individual multiplication/division takes $$ q $$ ns to execute, such that $$ p \ll q $$ (multiplication can be assumed to be repeated-addition and division can be assumed to be repeated subtraction), then each complex addition/subtraction will take $$ 2p $$ ns, each complex multiplication will take $$ 4q + p + p = (2p + 4q) $$ ns, and each complex division will take $$ 6q + 2p + p + 2q = (3p + 8q) $$ ns. Now imagine a number system in which complex arithmetic does not involve any combination of individual arithmetic operations as described in Sect. 1.2. That is, addition, subtraction, multiplication, or division of complex numbers is just one pure addition, one pure subtraction, one pure multiplication, or one pure division operation respectively and not a combination of various individual operations within a given arithmetic operation as mentioned previously. This will effectively reduce the complex addition/subtraction time to $$ p $$ ns and complex multiplication/division time to $$ q $$ ns. Mathematically, such a complex number system will yield reduction in execution time of addition/subtraction operation roughly by a factor of $$ \frac{p}{2p} \times 100 = 50\,\% $$ , for multiplication $$ \frac{(2p + 4q)}{q} \times 100 = \frac{4q}{q} \times 100 = 400\,\% $$ (since $$ p $$ is very small compared to $$ q) $$ , and for division $$ \frac{(3p + 8q)}{q} \times 100 = \frac{8q}{q} \times 100 = 800\,\% $$ . With the reduction in execution times of complex arithmetic operations roughly by factors of 50–800 % in digital signal and image processing applications, it is possible to achieve tremendous enhancement in the overall performance of systems based on these applications, provided a technique exists which treats a complex number as a single entity (rather than two entities comprising of real and imaginary parts) and facilitates a single-unit representation of complex numbers in binary format within a microprocessor environment (rather than two individual representations for real and imaginary parts respectively, as in today’s computers). Such a unique number system is referred to as Complex Binary Number System (CBNS).

      1.4 What is Complex Binary Number System?

      Efforts in defining a binary number system (0 or 1) with bases other than 2, which would facilitate a single-unit representation of complex numbers, date back to 1960 when Donald E. Knuth described a quater-imaginary number system with base $$ 2j $$ and analyzed the arithmetic operations of numbers based on this imaginary base [1]. However, he was unsuccessful in providing a division algorithm and considered it as a main obstacle towards hardware implementation of any imaginary-base number system.

      Walter Penney, in 1964, attempted to define a complex number system, first by using a negative base of $$ - 4 $$ [2], and then by using a complex number $$ ( - 1 + j) $$ as the base [3]. However, the main problem encountered with using these bases was again the inability to formulate an efficient division process. Stepanenko, in 1996, utilized the base $$ j\sqrt 2 $$ to generate real parts of complex numbers by taking even powers of the base and imaginary parts of complex numbers by taking odd powers of the base [4]. Although partly successful in resolving the division problem as an all-in-one operation, in his algorithm …everything…reduces to good choice of an initial approximation in a Newton–Raphson iteration which may or may not converge.

      Jamil et al., in 2000, revisited Penney’s number system with base $$ ( - 1 + j) $$ and presented a detailed analysis of this number system, now called Complex Binary Number System (CBNS) [5]. During the past several years, Jamil et al. have obtained research grants and published several articles in international conferences and journals describing conversion algorithms, arithmetic operations, and computer hardware circuits involving CBNS. This book is a compilation of the entire research work carried out on CBNS by the author and his various research teams, and is intended to assist new researcher in the fields of computer arithmetic and computer architecture as well as any student with interest in digital logic towards advancing modern day computing through incorporation of CBNS in both the software and hardware paradigms.

      In Chap. 2, algorithms to convert a given complex number into CBNS are presented. This is followed by presentation of techniques in Chap. 3 to carry out the arithmetic and shift operations in the new number system. Chapter 4 describes the hardware implementation, and performance statistics related to arithmetic circuits and, in Chap. 5, incorporation of these circuits within an associative dataflow environment to design a Complex Binary Associative Dataflow Processor (CBADP) has been explained. Conclusion and further research are outlined in Chap. 6.

      References

      1.

      D.E. Knuth, An imaginary number system. Commun. ACM 3, 345–347 (1960)MathSciNetCrossRef

      2.

      W. Penney, A numeral system with a negative base. Math. Student J. 11(4), 1–2 (1964)

      3.

      W. Penney, A binary system for complex numbers. J. ACM 12(2), 247–248

      Enjoying the preview?
      Page 1 of 1