DOI : 10.17577/IJERTV2IS100253
- Open Access
- Total Downloads : 136
- Authors : Usman Ali, Tariq Jamil
- Paper ID : IJERTV2IS100253
- Volume & Issue : Volume 02, Issue 10 (October 2013)
- Published (First Online): 09-10-2013
- ISSN (Online) : 2278-0181
- Publisher Name : IJERT
- License:
This work is licensed under a Creative Commons Attribution 4.0 International License
Bit-wise Byte-wide Analysis of Shift-Right Operations on Binary Representation of Complex Numbers
AUTHORS AND AFFILIATIONS
1Laboratory of Signals and Systems L2S, CNRS-Supélec, University of Paris 11, Plateau de Moulon 91192, Gif-sur-Yvette, FRANCE
2Department of Electrical and Computer Engineering, Sultan Qaboos University, AlKhod 123, Muscat, SULTANATE OF OMAN
CORRESPONDING AUTHOR
Complex numbers play very important role in electrical and computer engineering. Arithmetic operations involving complex numbers represented in binary number system are handled in todays computers by the application of divide-and-conquer technique wherein complex numbers are partitioned into real parts and imaginary parts and then operations between each pair (real with real, imaginary with imaginary) are carried out independent of one another. This results in multiple sub-operations within an operation and delay in the production of the final result. Complex Binary Number System provides a one-unit binary representation of a complex number and allows for arithmetic operations on complex numbers to be carried out in exactly the same way as the real numbers. In this paper, we have investigated the effect of bit-wise byte-wide shift right operations on the complex binary representation of complex numbers and analyzed these results using mathematical equations.
Complex number, complex binary number, multiple-shift, shift-right
-
Introduction
Complex numbers play very important role in electrical and computer engineering. These days, arithmetic operations involving complex numbers represented in binary number system are handled by the application of divide-and-conquer technique wherein complex numbers are partitioned into real parts and imaginary parts and then operations between each pair (real with real, imaginary with imaginary) are carried out independent of one another. This results in multiple sub-operations within an operation and delay in the production of the final result. For example, lets consider arithmetic operations involving two complex numbers ( + ) and ( + ). Their addition involves two individual additions, one for the real parts( + )and one for the imaginary parts( + ). Their subtraction involves two individual subtractions, one for the real parts( )and one for the imaginary parts( ). Multiplication involves four individual multiplications
, , , , one subtraction 2 = , and one addition + . Finally, division
involves six individual multiplications , , , , 2, 2, two additions + and
2 +2
2 +2
2 + 2, one subtraction , and then two individual divisions +
and 2 +2 . If we
assume that each individual addition/subtraction, involving complex numbers, takes nsec to complete and each individual multiplication/division takes nsec to execute, such that
(multiplication can be assumed to be repeated-addition and division can be assumed to be repeated subtraction), then each complex addition/subtraction will take 2 nsec, each complex multiplication will take 4 + + = (2 + 4) nsec, and each complex division will take 6 + 2 + + 2 = (3 + 8) nsec. Now lets imagine a number system in which complex arithmetic does not involve any combination of individual arithmetic sub- operations as described previously. That is, addition, subtraction, multiplication, or division of complex numbers is just one pure addition, one puresubtraction, one puremultiplication, or one puredivision operation respectively and not a combination of various individual sub- operations within a given arithmetic operation. This will effectively reduce the complex addition/subtraction time to nsec and complex multiplication/division time to nsec. Mathematically, such a complex number system will yield reduction in execution time of addition/subtraction operation roughly by a factor of 2 × 100 = 50%, for multiplication
(2+4) × 100 = 4 × 100 = 400% (since is very small compared to ), and for division
(3+8) × 100 = 8 × 100 = 800%. With the reduction in execution times of complex
arithmetic operations roughly by factors of 50% to 800% in digital signal and image processing applications of engineering where complex numbers are most frequently utilized, it is possible to achieve tremendous improvement in the overall performance of systems, provided that 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
todays computers). Such a unique number system is referred to as Complex Binary Number System (CBNS) [1].
There have been several efforts in the past to define a binary number system (0 or 1) with bases other than 2 which would facilitate a one-unit representation of complex numbers. In 1960, Donald Knuth described a number system with base 2 and analyzed the arithmetic operations of numbers based on this imaginary base [2]. He was unsuccessful in providing a division algorithm for binary numbers based on this imaginary base and considered it as a main obstacle towards hardware implementation of this number system.Four years later, Walter Penney defined a binary number system, first by using a negative base of 4 [3], and then by using a complex number (1 + ) as the base [4]. Like Donald Knuth before him, Walter Penney was unable to formulate an efficient division process using these bases and, consequently, these number systems remained dormant for more than thirty years. V.
Stepanenko, in 1996, defined a number system with the base 2 and generated real and imaginary parts of complex numbers by taking even and odd powers of this base respectively [5]. He succeeded somewhat in resolving the division problem as an all-in-one operation but, in his algorithm, everythingreduces to good choice of an initial approximation in a Newton-Raphson iteration which may or may not converge.Jamil et al, in 2000 [6], revisited Penneys number system with base (1 + ) and presented a detailed analysis of this number system, now famously called Complex Binary Number System (CBNS) [7]. Extensive details of the algorithms to be followed in CBNS for binary representation of a complex number can be found in [1] and the implementation statistics of the arithmetic circuits designed based on this number system can be found in [8,9,10,11]. In this paper, we haverestricted ourselves to investigating the effects of multiple-bit (from 1 bit to 8 bits) shift-right operations only on a complex number represented in single-unit binary notation of complex binary number system.
This paper is organized as follows: In section 2, well present basic information about CBNS and how to represent an integer-only complex number into this new number system. Then well take the CBNS representation of complex numbers and, in section 3,give a comprehensive analysis of the effect of multiple-bit shift right operations on the complex numbers. Conclusions are presented in section 4, which are followed by acknowledgments and references.
-
( + )-base Complex Binary Number System
Mathematically, the value of any n-bit binary number (123 210)in base 2 can be represented in the form of a power series as 1(2)n1 + 2(2)n2 + 3(2)n3 +
+ 2(22 +1(2)1 +0(2)0. Following the same procedure, the value of an n-bit binary number with base (1 + )can be written in the form of a power series as 1(1 + )n1
+ 2(1 + )n2 + 3(1 + )n3 + + 2(1 + )2 +1(1 + )1 +0(1 + )0 where the co-effecients 1, 2, 3, , 2, 1, 0 are binary in nature (0 or 1) and belong to complex binary number system. Using the conversion algorithms given in [1], we are able to
obtain a one-unit binary representation of any given complex number, whether it is made from integers, fractions, or floating point numbers, in Complex Binary Number System (CBNS). In this paper only the conversion algorithm for integershas been excerpted from [1].
The reader is referred to [7] for a thorough coverage of the conversion algorithms for fractions and floating point numbers.
A positive integer N can be converted into CBNS representation by following these steps:
-
Express N in terms of powers of 4 by repeatedly dividing by 4 and keeping track of the remainders. This will result in a base 4 number ( 5,4,3,2,1,0,) where {0,1,2,3}
-
Convert Base 4 number ( 5,4,3,2,1,0,)to Base 4 by replacing each digit in the odd location (1,3,5 ,) with its negative to get ( 5,4,3,2,1,0,). Next, we normalize the new number, i.e., get each digit in the range 0 to 3, by repeatedly adding 4 to the negative digits and adding
a 1 to the digit on its left. This operation will get rid of negative numbers but may create some digits with a value of 4 after the addition of a 1. To normalizethis, we replace 4 by a 0 and subtract a 1 from the digit on its left. This subtraction might once again introduce negative digits which will be normalized using the previous method but this process will definitely terminate.
-
Lastly, we replace each digit in the normalized representation by its equivalent
binary representation in CBNS, i.e., 0 0000, 1 0001, 2 1100, and 3
1101.
For example,
201210 = 1,3,3,1,3,0 4 = 1,3, 3,1, 3,0 4
= 1,2,0,1,2,1,0 = 0001 1100 0000 0001 1100 0001 0000
= 1110000000001110000010000 (1+ )
To convert a negative integer into CBNS format, we simply multiply the representation of the corresponding positive integer with 11101 (equivalent to (1) (1+ )) according to the multiplication algorithm for CBNS[1].
For example,
201210 = 111000000000111000001 × 11101
= 110000000000110111010000 (1+)
To obtain binary representation of a positive or negative imaginary number in CBNS, we multiply the corresponding CBNS representation of positive or negative integer with 11 (equivalent to (+) (1+ )) or 111 (equivalent to () (1+)) according to the multiplication algorithm for CBNS [1]. Thus
+201210 = 111000000000111000001 × 11
= 10000000000010000110000 (1+ )
201210 = 111000000000111000001 × 111
= 111010000000111010001110000 (1+)
After obtaining CBNS representations for all types of integers (real and imaginary), it is now possible for us to represent an integer complex number (both real and imaginary parts of the complex number are integers) simply by adding the real and imaginary CBNS representations according to the addition algorithm for CBNS [1]. Thus
201210 +201210
= 1110000000001110000010000 1+ + 10000000000010000110000 1+
= 1110100000001110100011100000 1+
-
-
Multiple-Bit Shift Right Operations in CBNS
To analyze the effects of shift-right operations on a complex number represented in CBNS format, we wrote a computer program in C++ language which allowed for variations in magnitude and sign of both real and imaginary components of a complex number to be generated automatically in a linear fashion, and then decomposed the complex binary number after the shift-right operation into its real and imaginary components. We restricted the length of the original binary bit array to 800 bits and 0s were padded on the left-side of the binary data when the given complex number required less than maximum allowable bits for representation in CBNS format.
To illustrate these restrictions, lets consider the following complex number: Original complex number represented in CBNS before padding:
9010 +9010 = 110100010001000 1+
Padded complex binary array such that the total size of the array is 800 bits.
9010 +9010 = 0 0110100010001000 1+
Shifting this binary array by 1-bit to the right will yield 00 011010001000100 1+ ensuring that total array-size remains 800 bits. This is done by removing one 0 from the right-side and inserting one 0 on the left-side of the number. Similarly, shifting of the original binary array by 2,3,4,5,6,7,8-bits to the right will yield respectively:
000 01101000100010 1+
0000 0110100010001 1+
00000 011010001000 1+
000000 01101000100 1+
0000000 0110100010 1+
00000000 011010001 1+
000000000 01101000 1+
All the time we make sure that the total array-size remains 800 bits by removing 2,3,4,5,6,7,8 bits, respectively from the right-side of the original array.
Table 1 presents an overall summary of the effect on the signs of the complex numbers, represented in CBNS format, because of multiple-bit shift-right operations (1 to 8 bits).
Table 1. Effect on signs of complex numbers in CBNS format after shift-right operations
Before Shift-Right
After Shift-Right by 1-bit
After Shift-Right by 2-bits
Real
Imaginary
Real
Imaginary
Real
Imaginary
+
0
0
+
0
+
+
0
0
+
+
0
0
+
+
0
+
+
0
+
+
0
+
+
+
+
0
0
+
+
Before Shift-Right After Shift-Right After Shift-Right
by 3-bits by 4-bits
Real
Imaginary
Real
Imaginary
Real
Imaginary
+
0
+
0
0
+
+
0
0
+
+
+
0
0
0
+
+
+
+
0
+
0
+
+
0
+
+
0
+
+
+
Table 1 (continued). Effect on signs of complex numbers in CBNS format after shift-right operations
Before Shift-Right
After Shift-Right by 5-bits
After Shift-Right by 6-bits
Real
Imaginary
Real
Imaginary
Real
Imaginary
+
0
+
+
0
0
0
+
0
+
+
+
0
0
+
0
+
+
0
+
+
+
+
0
+
0
+
+
0
+
Before Shift-Right After Shift-Right After Shift-Right
by 7-bits by 8-bits
Real
Imaginary
Real
Imaginary
Real
Imaginary
+
0
+
+
0
0
+
0
0
+
0
+
0
+
+
0
+
+
0
+
+
+
0
+
+
+
0
+
+
0
Shift-right operations on complex binary numbers affect not only the signs of the given complex numbers (as shown in Table 1) but also have impact on the magnitudes of the complex numbers according to different mathematical relationships. To find out the effects of shift-right operations on the magnitudes of the complex numbers, we varied the magnitude of real and imaginary components of the original complex numbers in a linear fashion (Fig. 1). The complex numbers obtained after shift-right operations were analysed by obtaining mathematical equations describing their behavior, as given in Figs. 2-9.
Fig.1. Mathematical equations describing variations in magnitudes of complex numbers in the Cartesian plane (before shift-right)
Fig. 2. Mathematical equations describing variations in magnitudes of complex numbers in the Cartesian plane (after shift-right by 1-bit)
Fig.3. Mathematical equations describing variations in magnitudes of complex numbers in the Cartesian plane (after shift-right by 2-bits)
Fig. 4. Mathematical equations describing variations in magnitudes of complex numbers in the Cartesian plane (after shift-right by 3-bits)
Fig.5. Mathematical equations describing variations in magnitudes of complex numbers in the Cartesian plane (after shift-right by 4-bits)
Fig. 6. Mathematical equations describing variations in magnitudes of complex numbers in the Cartesian plane (after shift-right by 5-bits)
Fig.7. Mathematical equations describing variations in magnitudes of complex numbers in the Cartesian plane (after shift-right by 6-bits)
Fig. 8. Mathematical equations describing variations in magnitudes of complex numbers in the Cartesian plane (after shift-right by 7-bits)
Fig. 9. Mathematical equations describing variations in magnitudes of complex numbers in the Cartesian plane (after shift-right by 8-bits)
To fully understand the variations in the sign and magnitude of the complex numbers before and after the shift-right operation, we used Microsoft Excel to draw graphs as shown in the Figs.10-17.
Fig. 10 and Fig. 11 illustrate the effect on the real and imaginary parts of the complex numbers after 1-8-bits shift-right operations for positive and negative real only complex numbers (no imaginary part), respectively.
Fig. 12 and Fig. 13 present the effect on the real and imaginary parts of the complex numbers after 1-8-bits shift-right operations for positive and negative only imaginary complex numbers (no real part), respectively.
The four cases of ±Real±Imaginary complex numbers represented in CBNS format before the shift, and effects of 1-8 bits shift-right operations on the sign and magnitude of complex numbers are presented in Figs. 14,15,16, and 17 respectively.
25
20
15
10
5
0
20
Real Imag
Real shift 2-bit Imag shift 2-bit
Real Imag
Real shift 2-bit Imag shift 2-bit
15
10
5
-5
-10
-15
1 4 7 10 13 16 19
0
1 4 7 10 13 16 19
Real
Imag
Real shift 1-bit
Imag shift 1-bit
Real
Imag
Real shift 1-bit
Imag shift 1-bit
Real Imag
Real shift 3- bits
Imag shift 3- bits
Real Imag
Real shift 3- bits
Imag shift 3- bits
Real Imag
Real shift 4- bits
Imag shift 4- bits
Real Imag
Real shift 4- bits
Imag shift 4- bits
25 25
20 20
15 15
10 10
5 5
0 0
-5
-10
35
30
25
20
15
10
1 3 5 7 9 11 13 15 17 19
Real Imag
Real Shift Right 5-bit
-5
-10
35
30
25
20
15
10
5
1 3 5 7 9 11 13 15 17 19
Real Imag Real Shift
Right 6-bit
5 Imag Shift 0
Imag Shift
0
1 4 7 10 13 16 19 22 25 28
Right 5-bit
-5
-10
Right 6-bit
35 35
30 Real 30
25 25
20 Imag 20
Real Imag
15 Real Shift 15
Real Shift
10 Right 7-bit
10 Right 8-bit
5 Imag Shift 5
Imag Shift
Right 8-bit
0
-5 1 4 7 10 13 16 19 22 25 28
Right 7-bit 0
1 4 7 10 13 16 19 22 25 28
Fig. 10. Effects of shift-right operation on sign and magnitude of a positive real-only complex number (1-8 bits)
15
10 Real
5
0 Imag
-5 1 4 7 10 13 16 19
Real shift 1-
-10 bit
-15 Imag shift 1-
-20 bit
-25
0
1 4 7 10 13 16 19 Real
-5
Imag
-10
Real shift 2-
bits
-15 Imag shift 2-
bits
-20
10
5 Real 0
-5 1 4 7 10 13 16 19 Imag
-10 Real shift 3-
bits
-15 Imag shift 3-
-20 bits
-25
10
5 Real 0
-5 1 4 7 10 13 16 19 Imag
-10 Real shift 4-
bits
-15 Imag shift 4-
-20 bits
-25
0
10
-5 1 4 7 10 13 16 19 22 25 28
-10
-15
-20
-25
-30
Real Imag
Real Shift Right 5- bit
Imag Shift Right 5- bit
5
0
-5
-10
-15
-20
-25
-30
Real Imag
Real Shift Right 6-bit
Imag Shift Right 6-bit
-35
-35
0
5
0
-5 1 5 9 13 17 21 25 29
-10
-15
-20
-25
-30
-35
Real
Imag
Real Shift Right 7-bit
Imag Shift
Right 7-bit
-5 1 4 7 10 13 16 19 22 25
-10
-15
-20
-25
-30
Real Imag
Real Shift Right 8-bit
Imag Shift Right 8-bit
-35
Fig. 11. Effects of shift-right operation on sign and magnitude of a negative real-only complex number (1-8 bits)
25
20
15
10
5
0
25
1
4
7
10
13 16
1
1
4
7
10
13 16
1
Real Imag
Real shift 2- bits
Imag shift 2- bits
Real Imag
Real shift 2- bits
Imag shift 2- bits
20
15
10
5
0
-5
-10
Real Imag
Real shift 3- bits
Imag shift 3- bits
Real Imag
Real shift 3- bits
Imag shift 3- bits
-15
1 4 7 10 13 16 19
-5 9
-10
-15
Real Imag
Real shift 1- bit
Imag shift 1- bit
Real Imag
Real shift 1- bit
Imag shift 1- bit
20
15
10
5
25
Real Imag
Real shift 4-
bits
Imag shift 4- bits
Real Imag
Real shift 4-
bits
Imag shift 4- bits
20
15
10
5
0
0
1 4 7 10 13 16 19
40
30
20
10
Real Imag
Real Shift Right 5-bit
-5
-10
35
30
25
20
15
10
1 4 7 10 13 16 19
Real Imag
Real Shift Right 6-bit
0 Imag Shift Right
5 Imag Shift
-10
1 4 7 10 13 16 19 22 25 28
5-bit 0
1 4 7 10 13 16 19 22 25 28
Right 6-bit
35 35
30 Real 30
25 25
20 Imag 20
Real Imag
15 15
Real Shift
Real Shift
10 Right 6-bit
10 Right 8-bit
5 Imag Shift 5
Imag Shift
0
1 4 7 10 13 16 19 22 25 28
Right 6-bit 0
1 5 9 13 17 21 25 29
Right 8-bit
Fig. 12. Effects of shift-right operation on sign and magnitude of a positive imaginary-only complex number (1-8 bits)
15
10
5
0
15
Real
Imag
Real shift 2- bits
Imag shift 2- bits
Real
Imag
Real shift 2- bits
Imag shift 2- bits
10
5
0
-5
-10
-15
-20
-25
1 4 7 10 13 16 19
-5
-10
-15
-20
-25
1 4 7 10 13 16 19
Real
Imag
Real shift 1- bit
Imag shift 1- bit
Real
Imag
Real shift 1- bit
Imag shift 1- bit
Real
Imag
Real shift 3-
bits
Imag shift 3- bits
Real
Imag
Real shift 3-
bits
Imag shift 3- bits
Real
Imag
Real shift 4- bits
Imag shift 4- bits
Real
Imag
Real shift 4- bits
Imag shift 4- bits
0 10
-2 1 4 7 10 13 16 19
-4
-6
5
0
-8
-10
-12
-14
-16
-18
-20
-5
-10
-15
-20
-25
1 4 7 10 13 16 19
10 0
5
0
Real
-5
-10
1 4 7 10 13 16 19 22 25 28 Real
-5
-10
-15
-20
-25
-30
-35
1 4 7 10 13 16 19 22 25 28
Imag
Real Shift Right 5-bit
Imag Shift Right 5-bit
-15
-20
-25
-30
-35
Imag
Real Shift Right 6-bit
Imag Shift Right 6-bit
1 4 7 10 13 16 19 22 25 28
1 4 7 10 13 16 19 22 25 28
5
0 Real
0
-5
-10
Real
Imag
-5
-10
-15
1 4 7 10 13 16 19 22 25 28
Imag
-15 Real Shift
-20
Real Shift
-20
Right 7-bit
-25
Right 8-bit
-25 Imag Shift Imag Shift
-30
-35
Right 7-bit
-30
-35
Right 8-bit
Fig. 13. Effects of shift-right operation on sign and magnitude of a negativeimaginary-only complex number (1-8 bits)
25
20
15
10
5
0
-5 1 4 7 10 13 16 19
25
Real Imag
Real shift 2- bits
Imag shift 2- bits
Real Imag
Real shift 2- bits
Imag shift 2- bits
20
15
10
5
0
-10
-15
-20
-25
-5
-10
-15
1 4 7 10 13 16 19
Real Imag
Real shift 1- bit
Imag shift 1- bit
Real Imag
Real shift 1- bit
Imag shift 1- bit
20
18
16
14
12
10
8
6
4
25
Real
Imag
Real shift 4- bits
Imag shift 4- bits
Real
Imag
Real shift 4- bits
Imag shift 4- bits
20
15
10
5
0
Real
Imag
Real shift 3- bits
Imag shift 3- bits
Real
Imag
Real shift 3- bits
Imag shift 3- bits
2 -5
0
1 4 7 10 13 16 19
1 4 7 10 13 16 19 -10
35 35
30 Real 30
25 25
20 Imag 20
15 15
Real Shift Right
10 5-bit 10
Real Imag
Real Shift Right 6-bit
5 Imag Shift Right
5 Imag Shift
0
1 4 7 10 13 16 19 22 25 28
5-bit
0
-5 1 4 7 10 13 16 19 22 25 28
Right 6-bit
35 35
30 Real 30
25 25
20 Imag 20
15 15
10 10
10 10
Real Shift
Right 7-bit
5 Imag Shift 5
Real Imag
Real Shift Right 8-bit
Imag Shift Right 8-bit
0
-5 1 4 7 10 13 16 19 22 25 28
Right 7-bit 0
1 4 7 10 13 16 19 22 25 28
Fig. 14. Effects of shift-right operation on sign and magnitude of a +Real+Imaginary complex number (1-8 bits)
1 4 7 10 13 16 19
1 4 7 10 13 16 19
25
20
15
10
5
0
-5
-10
-15
-20
-25
25
1 4 7 10 13 16 19
1 4 7 10 13 16 19
Real Imag
Real shift 2- bits
Imag shift 2- bits
Real Imag
Real shift 2- bits
Imag shift 2- bits
20
15
10
5
0
-5
-10
-15
-20
-25
Real Imag
Real shift 1-bit Imag shift 1-bit
Real Imag
Real shift 1-bit Imag shift 1-bit
25
20
15
10
5
0
-5
-10
-15
-20
-25
1 4 7 10 13 16 19
25
1 4 7 10 13 16 19
1 4 7 10 13 16 19
Real
Imag
Real shift 4- bits
Imag shift 4- bits
Real
Imag
Real shift 4- bits
Imag shift 4- bits
20
15
10
5
0
-5
-10
-15
-20
-25
Real Imag
Real shift 3- bits
Imag shift 3- bits
Real Imag
Real shift 3- bits
Imag shift 3- bits
40 40
30 Real 30
20 20
10 Imag 10
Real Imag
0
Real Shift
0
Real Shift
-10
-20
-30
-40
1 4 7 10 13 16 19 22 25 28
Right 5-bit Imag Shift Right 5-bit
-10
-20
-30
-40
1 5 9 13 17 21 25 29
Right 6-bit Imag Shift Right 6-bit
40
30 Real
20
40
30 Real
20
10
0
-10
1 4 7 10 13 16 19 22 25 28
Imag
Real Shift Right 7-bit
10
0
-10
1 4 7 10 13 16 19 22 25 28
Imag
Real Shift Right 8-bit
-20 Imag Shift
-20 Imag Shift
-30
-40
Right 7-bit
-30
-40
Right 8-bit
Fig. 15. Effects of shift-right operation on sign and magnitude of a +RealImaginary complex number (1-8 bits)
1 3 5 7 9 11 13 15 17 19
1 3 5 7 9 11 13 15 17 19
25
20
15
10
5
0
-5
-10
-15
-20
-25
1 3 5 7 9 11 13 15 17 19
1 3 5 7 9 11 13 15 17 19
25
20
15
10
5
0
-5
-10
-15
-20
-25
25
1 3 5 7 9 11 13 15 17 19
1 3 5 7 9 11 13 15 17 19
Real Imag
Real shift 1- bit
Imag shift 1- bit
Real Imag
Real shift 1- bit
Imag shift 1- bit
Real Imag
Real shift 2- bits
Imag shift 2- bits
Real Imag
Real shift 2- bits
Imag shift 2- bits
20
15
10
5
0
-5
-10
-15
-20
-25
1 3 5 7 9 11 13 15 17 19
1 3 5 7 9 11 13 15 17 19
Real
Imag
Real shift 4- bits
Imag shift 4- bits
Real
Imag
Real shift 4- bits
Imag shift 4- bits
25
20
15
10
5
0
-5
-10
-15
-20
-25
Real
Imag
Real shift 3- bits
Imag shift 3- bits
Real
Imag
Real shift 3- bits
Imag shift 3- bits
40
30
20
10
0
-10
1 4 7 10 13 16 19 22 25 28
Real Imag
Real Shift Right 5-bit
40
30
20
10
0
-10
1 5 9 13 17 21 25 29
Real Imag Real Shift
Right 6-bit
-20 Imag Shift -20 Imag Shift
-30
-40
Right 5-bit
-30
-40
Right 6-bit
40 40
30 Real 30
20 20
10 Imag 10
Real Imag
0
Real Shift
0 Real Shift
-10
1 5 9 13 17 21 25 29
Right 7-bit
-10
1 4 7 10 13 16 19 22 25 28
Right 8-bit
-20 Imag Shift
-20
Imag Shift
-30
-40
Right 7-bit
-30
-40
Right 8-bit
Fig.16. Effects of shift-right operation on sign and magnitude of a Real+Imaginary complex number (1-8 bits)
25
20
15
10
5
0
-5
-10
-15
-20
-25
15
1 4 7 10 13 16 1
1 4 7 10 13 16 1
1
4
7
10
13 16
19
1
4
7
10
13 16
19
Real Imag
Real shift 1- bit
Imag shift 1- bit
Real Imag
Real shift 1- bit
Imag shift 1- bit
Real Imag
Real shift 2- bits
Imag shift 2- bits
Real Imag
Real shift 2- bits
Imag shift 2- bits
10
5
0
-5
9 -10
-15
-20
-25
1
4
7
10
13
16
19
1
4
7
10
13
16
19
Real
Imag
Real shift 3- bits
Imag shift 3- bits
Real
Imag
Real shift 3- bits
Imag shift 3- bits
Real Imag
Real shift 4- bits
Imag shift 4- bits
Real Imag
Real shift 4- bits
Imag shift 4- bits
0 10
1 4 7 10 13 16 19 5
-5 0
-5
-10
-15
-20
-10
-15
-20
-25
0
-5
-10
-15
-20
-25
-30
-35
1 4 7 10 13 16 19 22 25 28 Real
Imag
Real Shift Right 5-bit
Imag Shift Right 5-bit
10
5
0
-5
-10
-15
-20
-25
-30
-35
1 4 7 10 13 16 19 22 25 28
Real Imag
Real Shift Right 6-bit
Imag Shift Right 6-bit
10
5
0
-5
-10
-15
-20
-25
-30
-35
Real Imag
Real Shift Right 7-bit
Imag Shift Right 7-bit
0
-5
-10
-15
-20
-25
-30
-35
1 4 7 10 13 16 19 22 25 28 Real
Imag
Real Shift Right 8-bit
Imag Shift Right 8-bit
Fig. 17. Effects of shift-right operation on sign and magnitude of a RealImaginary complex number (1-8 bits)
After analyzing Figs. 1-17, we are able to obtain the characteristic equations describing complex numbers in CBNS format after shift-right operations. These equations are given in Table 2.
Table 2. Characteristic equations describing complex numbers in CBNS format after shift-right operations
Type Number
of
Complex
After Shift-Right by 1-bit
After Shift-Right by 2-bits
Realold
Imaginaryold
Realnew
Imaginarynew
Realnew
Imaginarynew
+
0
½Realold+ ¼
½Realold+ ¼
0
+½Realold ¼
0
½Realold+ ¼
½Realold+ ¼
0
+½Realold ¼
0
+
½Imagold+ ¼
½Imagold+ ¼
½Imagold + ¼
0
0
½Imagold+ ¼
½Imagold+ ¼
½Imagold + ¼
0
+
+
0
Imagold
½Realold + ¼
½Imagold + ¼
+
Realold
0
½Realold + ¼
½Imagold + ¼
+
Realold
0
½Realold + ¼
½Imagold + ¼
0
Imagold
½Realold + ¼
½Imagold + ¼
Type
of
Complex
After Shift-Right
After Shift-Right
Number
by 3-bits
by 4-bits
Realold
Imaginaryold
Realnew Imaginarynew
Realnew Imaginarynew
+
0
¼ Realold ¼ Realold
¼Realold 0
0
0
+
¼ Realold ¼ Realold
¼ Imagold ¼ Imagold
¼Realold 0
0 ¼Imagold
0
+
+
+
+
¼ Imagold ¼ Imagold
½Realold + ¼ 0
0 ½Imagold ¼
0 ½Imagold ¼
½Realold + ¼ 0
0 ¼Imagold
¼Realold ¼Imagold
¼Realold ¼Imagold
¼Realold ¼Imagold
¼Realold ¼Imagold
Table 2 (continued) Characteristic equations describing complex numbers in CBNS format after shift-right operations
Type Number
of
Complex
After Shift-Right by 5-bits
After Shift-Right by 6-bits
Realold
Imaginaryold
Realnew
Imaginarynew
Realnew
Imaginarynew
+
0
Realold
Realold
0
Realold
0
Realold
Realold
0
Realold
0
+
Imagold +
Imagold +
Imagold +
0
0
Imagold +
Imagold +
Imagold +
0
+
+
0
¼Imagold
Realold +
Realold +
+
¼ Realold +
0
Realold
Imagold
+
¼ Realold +
0
Realold
Imagold
0
¼ Imagold
Realold +
Imagold +
Type
of
Complex
After Shift-Right
After Shift-Right
Number
by 7-bits
by 8-bits
Realold
Imaginaryold
Realnew Imaginarynew
Realnew Imaginarynew
+
0
¼ ¼
¼ 0
0
¼ ¼
¼ 0
0
+
0 0
0 0
0
0 0
0 0
+
+
Realold + 0
0 0
+
0 Imagold
¼ ¼
+
0 Imagold
¼ ¼
Realold + 0
0 0
-
Conclusions
The role of complex numbers is vital in all types of engineering applications and the importance in these numbers in the professional realm of an engineer cannot be ignored. However, ever since the birth of computer, these numbers have been treated as distant relatives of the real world and nothing substantial has ever been done in the field of computer architecture and arithmetic to improve the performance of arithmetic operations involving these type of numbers. CBNS provides a viable alternative for a single-unit binary representation of complex numbers with the premise of substantial enhancement in the speed of arithmetic operations dealing with these types of numbers. In this paper, we have looked in detail on how shift-right operations of 1-8 bits on a complex number represented in CBNS affect the signs and magnitudes of these numbers. Continuing with this work, we intend to do similar analysis for shift-left operations on complex numbers represented in CBNS so that a wholesome picture about the true benefits of CBNS are established within the engineering community.
Acknowledgments
The work presented in this paper has been the result of a research grant: IG/ENG/ECED/06/02 provided by Sultan Qaboos University (Oman) and we gratefully acknowledge the encouragement rendered to us for this project. Preliminary versions of this paper, related to only nibble-size (up to 4-bits) shift-right operations have appeared previously in the Proceedings of the IEEE SoutheastCon 2007 and the Journal of Computers (Academy Publisher) in 2008. The positive feedback received from reviewers of these previous publications prompted us to engage in more thorough and extended analysis (up to 8-bits) of shift-right operationsinvolving complex binary numbers and we are thankful to these reviewers for their valuable input.
References
-
T. Jamil, Complex Binary Number System, Springer-Verlag, Germany, 2012.
-
D. Knuth, An imaginary number system, Communications of the ACM, 3, pp.345-347.
-
W. Penney, A numeral system with a negative base, Mathematics Student Journal, 11(4), 1964, pp. 1-2.
-
W. Penney, A binary system for complex numbers, Journal of the ACM, 12(2), 1964, pp. 247-248.
-
V. Stepanenko, Computer arithmetic of complex numbers, Cybernetics and System Analysis, 32(4), 1996, pp. 585-591.
-
T. Jamil, N. Holmes, D. Blest, Towards implementation of a binary number system for complex numbers, Proceedings of the IEEE Southeastcon, 2000, pp. 268-274.
-
T. Jamil, The complex binary number system: Basic arithmetic made simple, IEEE Potentials 20(5), 2002, pp. 39-41.
-
T. Jamil, B. Arafeh, A. AlHabsi, Hardware implementation and performance evaluation of complex binary adder designs, Proceedings of the 7th World Multiconference on Systemics, Cybernetics, and Informatics, 2, 2003, pp. 68-73.
-
T. Jamil, A. Abdulghani, A. AlMaashari, Design of a nibble-size subtractor for (1+j)-base complex binary numbers, WSEAS Transactions on Circuits and Systems 3(5), 2004, pp. 1067- 1072.
-
T. Jamil, A. Abdulghani, A. AlMaashari, Design and implementation of a nibble-size multiplier for (1+j)-base complex binary numbers, WSEAS Transactions on Circuits and Systems 4(11), 2005, pp. 1539-1544.
-
T. Jamil, S. AlAbri, Design of a divider circuit for complex binary numbers, Proceedings of the World Congress on Engineering and Computer Science, II. 2010, pp. 832-837.