US3927312A

US3927312A - Vector rotator

Info

Publication number: US3927312A
Application number: US519735A
Authority: US
Inventors: Warren D Dickinson
Original assignee: United States Department of the Army
Current assignee: United States Department of the Army
Priority date: 1974-10-31
Filing date: 1974-10-31
Publication date: 1975-12-16
Anticipated expiration: 1992-12-16

Abstract

A two stage approach is used in which rotation angles are specifically selected for easy mechanization. First stage provides rotations in even 30* increments so that multiplications are replaced by simple shift or shift/add operations. Rotation angles available in the second stage each have sines with at most two nonzero bits in their binary representations.

Description

United States Patent l 1 1 [111 Di kinson 1 Dec. 16, 1975 [5 VECTOR ROTATOR 3.725.686 4/1973 umch 235/156 2 1 Q Inventor: Warren D. Dickinson Huntsville, 3.767.905 /1973 (Jardt. -/1. 6

Ala. Primary Examiner-loseph F. Ruggiero [73] Assignee' The Unlted States of America as Attorney, Agent, or Firm-Lawrence A. Neureither;

represented by the Secretary of the Jose h H Beumer Robert C Sims Army, Washington, DC. p

[22] Filed: Oct. 31, 1974 21 Appl. No.: 519,735 [571 ABSTRACT A two stage approach is used in which rotation angles [52] US. Cl. 235/189; 235/156; 235/186 are specifically selected for easy mechanization. First [51] Int. Cl. G06F 7/38 stage p s at s in even 0 r nts s at [58] Field of Search 235/152, 156, 186, 189, multiplications are replaced by simple shift or shift- 235/l64, 197 /add operations. Rotation angles available in the second stage each have sines with at most two nonzero [56] References Cit d bits in their binary representations.

UNITED STATES PATENTS 7 Claims, 6 Drawing Figures 3,684,876 8/1972 Sutherland 235/156 X G REG ISTER n to.

b REGISTER 8 l l ISSHIFT ISHIFT LasmFT] [SHIFT] I 23 n v m r- I- S '2 BITZ 5 a m i ADDER BIT! CONTROL GENERATOR E 5 72 FADDER SHIFT 70/ 9b REGISTER U.S. Patent Dec. 16, 1975 Sheet 3 of 5 IST. STAGE ROTATION REQUIREMENTS US. Patent Dec. 16, 1975 Sheet4of5 3,927,312

U.S. Patent Dec.16,1975 SheetS f5 QIREGISTER b REGISTER SHIFT SHIFT SHIFT SHIFT 1y I SHIFT h V r ADDER ADDER ADDER ADDER 3 35 36 a? CONTROL com: 38 GENERATOR ADDER m BIT4 g, 39) ,Q 5 ADDER ADDER J72 SHIFT /7l 0 REGISTER b REGISTER b 9 REGISTER V FIG. 6

VECTOR ROTATOR SUMMARY OF THE INVENTION The invention performs vector rotation in a binary machine (computer). Inputs are the rotation angle and the real and imaginary components of the vector to be rotated. Outputs are the real and imaginary components of the vector after rotation. Vector rotation occurs in 26 sequential stages depending upon accuracy requirements. Rotation angles at each stage are selected for easy mechanization on a binary computer.

Rotation angles available in the first stage are in even 30 increments so that rotations can generally be accomplished by shift/add operations, sign changes and reversals of real and imaginary components. Rotation angles available in second and succeeding stages are selected such that the binary representations of their sines have at most 2 nonzero bits. This characteristic assures that multiplications can be replaced by shift- /add operations.

This vector rotator scheme has been configured for use in taking fast fourier transforms. Special cases of vector rotation include conversion from polar to rectangular coordinates and computations of sines and cosines.

BRIEF DESCRIPTION OF THE DRAWINGS FIG. 1 is a graphic illustration of the vector rotation proper;

FIG. 2 is a graphic representation of the rotation of the vector in the first stage;

DESCRIPTION OF THE PREFERRED EMBODIMENT The function of this method is to perform vector rotation in a binary machine (computer). The method performs this rotation in a sequence of rotations which have unique properties allowing the rotations to be performed either faster or with less hardware than conventional techniques.

FIG. 1 illustrates the problem being solved by this invention. Vector V specified by its real and imaginary components a and b is to be rotated by an angle 6. It is desired to determine the real and imaginary components a and b of the vector V following rotation.

Maghematically,

where i= VTI. By a familiar identity,

and thus,

V =(a+ ib) (cos 6+isin 6) =acos6+iasin6+ibcos6bsin6 =(a cos 6bsin 6)+i(u sin 6+bcos6) a 1' [1 Thus 11 cos 6'bsin 6 and b =usin 6+bcos6 To define the function of this method more clearly,

its inputs and outputs are as follows:

2 Inputs: (1, b, 6 Outputs: :1 b

The solution in common practice proceeds in three parts as follows:

1. Determine sin 6 and cos 6;

2. Perform four multiplications, a X cos 6 a X sin 6, b

X cos 6, b X sin 6; and 3. Perform two additions [a cos 6] [-b sin 6] and [a sin 6] [b cos 6}.

This conventional approach can be expensive due to the need for calculating sin 6 and cos 6 as well as be cause of the difficulty of performing four multiplications.

Two primary differences exist when compared to conventional methods as follows:

I. This invention does not require explicit calculation of sin 6 and cos 6; and

2. This invention replaces the referenced four multiplications by shift/add operations which are, in general, much simpler.

The invention being claimed is more general than the specific embodiment described. This embodiment was developed for one particular application known to the inventor. The invention is applicable, with minor de-- sign modification, to a wide variety of requirements.

The example embodiment selected is for a special purpose data processor to perform Fast Fourier Trans forms (FFT). This data processor takes as an input a large number of complex time samples of an electrical signal and calculates the Digital Fourier Transform thus producing the frequency spectrum of the signal. Calculation of the FFT requires an enormous number of vector rotations, and indeed, the greatest portion of PET cost is related to these vector rotations.

The example embodiment is for 4,000 point trans form being computed by 12 sequential stages arranged in a pipeline fashion. The data processor uses the Sande-Tukey algorithm in a radix 2 design (two points transformed at a time).

Random cancellations and enhancements produced by combining a large number of samples makes it possible to achieve adequately precise overall performance with an accuracy of roughly 1% at each rotation stage. Thus, sin 6 and cos 6 need only be determined to the 7th binary bit. Actually, performance is adequate even if the 5th and 6th bits are occasionally in error.

Vector rotation for this embodiment is performed in two stages. The first stage performs a rotation 6 of n.3()

where "=0, 1.2. 3,. 12. The vector being transformed is within 15 of the desired fianl position after completion of this first rotation.

The second stage performs rotation by an angle 6 whose sine possesses at most two nonzero binary bits. Since only two nonzero bits exist, multiplication of a number by these sines can be implemented as a simple shift/add operation.

The cosines of angles less than 15 are very close to unity and for the 6 angles have the property that the term (I cos 6 has only one nonzero bit out to the 7th binary place. Hence, multiplications by cos 6 can also be implemented as a shift/add operation.

FIG. 2 shows as dark lines the 12 rotation angles possible in the 1st stage. Rotations by the 4 angles given by .n do not require multiplications at all, but can be accomplished with sign changes and by reversals of real and imaginary components. The remainilYg' 8 vectof each have a sine or a cosine equal to 2:2 Multiplica tion by this angle can be accomplished by a siiiiple 05E bit shift. Assume for the moment that it is the sine which is 2, and let us find the cosine.

cos 6 lwin 9 (l sin 6)" by the binomial expansion,

cos l-?. sin 0 2"I sin 6 2 sin 6 2 sin"67 2 "sin'0. for sin 0 2 CO5 30 l 2'11 2? 2lll 2I3 2-l-l For this application it is permissible to ignore the 2 term and succeeding terms. Thus,

cos 30 5 l 2 The cos 30 multiplication can be accomplished by shifting three bits to the right and subtracting from the unshifted number. FIG. 4 shows a table of the mathematical results required for each of the 12 rotation possibilities. Note that V is the vector which emerges from the first rotation and that VI a i b,

Note also that when cos 6 2*, then sin 0 l2 FIG. 3 shows the functional circuit diagram for implementing this technique. Major components are shifters 5-8, input registers 9 and 10, adders 11-14, and

output registers

16 and 17. The control signals necessary to set switches 20-24 and change signs of sign generators 28-31 are generated by a separate subsystem known as the control code generator 33.

The V vector which emerges from the 1st Rotator state will be within of the desired final angle. The angular rotation accomplished by the second stage 0 is restricted to 12 possible values each of which has the property that sin 6 has at most 2 nonzero bits in its binary representation. Thus, multiplication by sin 0 requires only two shifts and one add.

Since 6 is small, cos 6 is very close to unity. It happens that for each of the 12 6 angles (1 cos 0 has only one nonzero binary bit out to the 7th binary place. Thus multiplication by cos 6 can be accomplished by shifts and adds.

FIG. 5 shows a table of the 12 6 angles; the respective values of sin 0 and cos 0 and reveals the maximum errors A cos 0 introduced by using the cos 6 values shown. The greatest error introduced is 2 and this is negligible for this application. Required outputs in mathematical form are also given in the table of FIG. 5.

Note in FIG. 5 that 6 angles generally increase in 09 steps thus introducing i0.45 errors. Between the last two 0 values, however, a gap of 3.7 exists. Thus, errors as large as il.8 can exist after second stage rotation. This error is judged to be acceptable for this application since errors are within 109 for 90 of the required rotation angles.

If an application requires greater accuracy, however, then a third rotation stage can be used without greatly expanded hardware. The third stage would require at most two shift registers and four adders. It would have a set of shift angles 0 having sin (i -values identical to the sin 0 values of FIG. 5, except that all nonzero bits would be shifted 3 bits to the right. Thus, the greatest angular error emerging from the third stage would be fl).23 which corresponds to errors in sin 6 beyond the 7 bit accuracy generally used in this application. Note that for the third stage cos would be assumed equal to unity, since differences would be less than 2-1 1.

FIG. 6 shows the functional circuits needed to perform second stage rotation. Major components are 6 adders 34-39, 6 variable shift registers 41-46, four sign generators 47-50, and 2 output registers 53 and 54. Necessary control signals are provided by control code generator 55 to variable shift registers 41-46.

4 The particular Fast Fourier Transform application being described uses the Sande-Tukey algorithm where points are transformed in order using radix 2 pipeline stages.

The angular rotations required for each pair of points vary in a regular progression according to the formula,

where 6 is given in degrees M the number of stages in the pipeline m the stage of the pipeline being addressed, m=1,2,3,...,M

And k is an index variable which follows a counting Thus the required angular rotations start at zero and progress in even increments through negative angles up to -1 80.

Define a term (or register in FIGS. 3 and 6) 6,, 0. The 0,, register has the bit values shown below.

Note that the first bit of 0,, reveals the quadrant location of the desired rotation angle without reference to any other bit value. This being true because the rotations only goes up to -l. If the contents of the 0,, register are multiplied by the fraction then a new term (or register) is formed whose bit values are favorable for determining rotator. control bits. The denominator 4 can be dropped as this only shifts the result two places to the left. This is taken care of by the interpretation of the value of the bit positions by

generators

33 and 55. Since the binary representation of 3 is l 1, this multiplication is accomplished by one shift by shifter 71 and one add by adder 72. This new term 6 has the bit positions (with interpretation) shown below:

required for the second stage. It can be used directly as 7 one of the control bits for that stage to control the

sign generators

49 and 50.

The first 3 bits of 6 can be ignored completely in determining second stage control bits since the 1st stage rotation exactly eliminates these bits.

The control code generator 33 uses the 5th and smaller valued bits of 6 to produce control bits for the second rotator stage. The first requirement for generating these control bits is to determine the 0 angle which is closest to the desired rotation. The table of FIG. 5 showsthe programming for the angles. The mean 6 50. Bits -9 of 6 are used to address the control code generator 55 so as to produce proper word output. The word output from control generator will contain a plurality of bits which are individually connected to shift registers 41-46 (shown in cable form in FIG. 6). Shift registers 41-46 may take the form of the well known sin 0 30 14.5 7.2" 3.6

Least sig nificant sin 0 bit Note that the 30 values correspond exactly and that other bits differ at most by 0.5. Differences for smaller angles are within 0.1". This correspondence is not surprising in view of the fact that sin 6 is a nearly linear function for small angles.

The bit value correspondence, between registers 0 and sin 0 makes it possible to use only bits 5-9 of 19 to determine the proper 0 rotation. These five bits can reference a 12 word decode memory also contained in generator 55 which outputs a plurality of easily mechanizable control bits. These bits control the amount of shift of each variable shifter 41-46. If an open circuit is desired at a shifter, then that shifter shifts its input to the right a number of places more than the total places in its input. In this way its output is zero and a open circuit.

For small angles, the ratio of bit values between 6 and sin 6 approaches 1r/3. For applications requiring greater accuracy than the example, closer correspondence between the 6 and sin 0 registers can be obtained by multiplying 6 by 1r/3. This multiplication requires only two shifts and two adds to yield 11 bit accuracy due to the sparcity of 1s in this particular number.

In operation the first stage of rotation FIG. 3 has fed into it the coordinates of the vector to be rotated: a, b, and 0. The value of the 6 is recorded in the register 70 as 0 0,, is changed to 6 by shifters 71 and adder 72. The output of adder will have its l-9 bits representing 6 however, only bits l-4 are used in the first stage rotation to select the control words from control generator 33.

The output of control generator 33 is shown to have 5 bit outputs. Bit 1 controls the position of switch 24, bit 3 controls the positions of switches 20-23, bit 4 controls the sign of sign generator 30, and bit 5 controls the sign of sign generator 31. Bit 2 controls the signs of

sign generators

28 and 29; however, since these sign generators should be opposite from each other, an inverter 69 is inserted in series between' bit 2 and sign generator 28. As can be seen from reference to FIG. 4 all the required outputs of a and [2 are obtained by this first stage rotational circuit. Control generator 33 can be any of the well known programmable read only devices such as the 74186 PROM (see TTL Data Book for Design Engineers copyright 1973 by Texas Instruments).

The output of the a register 16 and the b register 17 is also fed to the inputs of the second stage rotational circuit FIG. 6. Again adder 72 produces all the bits l-9; however, bits l3 are not needed for second stage rotation. Bit 4 is used directly to control the sign of the rotation by direct connection to sign generators 49 and shift registers which have their amount of shift controlled by a clock which in turn is controlled by the bits from control generator 55. In this way the required outputs for 0 can be derived by programming the word outputs of control generator 55 in accordance with the table shown in FIG. 5. The outputs of the a register 53 and b register 54 represent the desired coordinates of the vector after rotation. Control generator 55 can be any of the well known programmable read only" devices such as the 74186 PROM (see TTL Data Book for Design Engineers copyright 1973 by Texas Instruments).

The shift registers 41-46 could also be each a plurality of shift registers and a switch each in parallel with the others. The switches could then be controlled by the outputs from control generator 55. For example shift register 41 could take the shape of three shift registers in series with three switches each shift register and switch being in parallel with each other. One shift register being a shift 7 places shift register, the second shift register being a shift 6 places shift register, and the third shift register being a shift 5 places register. The control generator having bits connected to each of the switches to control their operation. Looking at FIG. 6 one can see that adder 34 produces an output corresponding to the first half of the a register as depicted in FIG. 5. Adder 37 corresponds to the second half of the a register, likewise the b register has its first and second parts corresponding to the outputs of

adders

36 and 35.

OTHER EMBODIMENTS If vgctor V is specified in polar coordinates as,

V=Re =Rcos6+jRsin0 and it is desired to find the real and imaginary components, then a simplified vector rotation technique can be employed. Note that this problem is a special case of vector rotation in which a R and b 0. The first stage of the rotator requires only 2 rather than 4 adders.

If @ctor V is specified as,

then sin 6 and cos 0 are directly computed by the rotator device. The 1st rotation stage requires no adders and the second stage is reduced by almost half if only the sine or the cosine need be computed.

Innumerable variations of the rotator device are possible depending upon specific applications and upon specific hardware capabilities. Applications requiring high degrees of accuracy will need as many as four or five stages and will need to perform some actual multiplications due to the significant numbers of nonzero bits which exist in the cosine functions in bit positions beyond 10.

7 Applications which are not keyed to a rigid time schedule can take advantage of cases in which convergence is quicker than worst case predictions. For these applications it may be worthwhile to include more possible rotation angles in each stage. For example, one could add 6 angles having nonzero bits in the following bit positions, (6 and 7), and 7), (4 and 7) and (3 and 7).

I claim: 1. A method for determining the vector components of a vector to be rotated 6 comprising the steps of:

determining the components of the vector rotated 6 in even 30 increments such that 6 equal 0 within a 1 error; selecting rotation angles from 0 to 15 in steps to represent 6 such that 6 i 6 can be selected such that any error between the algebraic sum of them and 6 is within one half of one of said steps; rotating 0 the vector components of the vector already rotated 6 and selecting 0 such that the combination of 6 and i 6-;

is most nearly equal to 0. 2. A method as set forth in claim 1 further comprising the step of:

selecting the stepped values of 6-, such that the sign of each 6 has at most two nonzero bits in its binary representation. 3. A method as set forth in claim 2 further comprising the steps of:

representing 0 as a binary number; multiplying this number by 3 so as to obtain a second binary member having a plurality of output bits; determining 6 by the progression of the first four highest bits. 4. A method as set forth in claim 3 further comprising the step of:

utilizing fifth highest bit and lesser bits for representing in steps 6 5. A method as set forth in claim 4 further comprising the step of:

performing said 6 rotation of the components by shift/ add operations, sign changes and reversals of real and imaginary components. 6. A method as set forth in claim 5 further comprising the step of:

performing the required multiplications in the 9 rotation by shift/add operations. 7. A method as set forth in claim 4 further comprising the step of:

utilizing the fourth highest bit to determine the sign of 6 e

Claims

1. A method for determining the vector components of a vector to be rotated theta * comprising the steps of: determining the components of the vector rotated theta 1* in even 30* increments such that theta 1 equal theta within a + OR - 15* error; selecting rotation angles from 0 to 15* in steps to represent theta 2* such that theta 1 + OR - theta 2 can be selected such that any error between the algebraic sum of them and theta is within + OR - one half of one of said steps; rotating theta 2* the vector components of the vector already rotated theta 1*; and selecting theta 2 such that the combination of theta 1 and + OR - theta 2 is most nearly equal to theta .

2. A method as set forth in claim 1 further comprising the step of: selecting the stepped values of theta 2 such that the sign of each theta 2 has at most two nonzero bits in its binary representation.

3. A method as set forth in claim 2 further comprising the steps of: representing theta as a binary number; multiplying this number by 3 so as to obtain a second binary member having a plurality of output bits; determining theta 1 by the progression of the first four highest bits.

4. A method as set forth in claim 3 further comprising the step of: utilizing fifth highest bit and lesser bits for representing in steps theta 2.

5. A method as set forth in claim 4 further comprising the step of: performing said theta 1 rotation of the components by shift/add operations, sign changes and reversals of real and imaginary components.

6. A method as set forth in claim 5 further comprising the step of: performing the required multiplications in the theta 2 rotation by shift/add operations.

7. A method as set forth in claim 4 further comprising the step of: utilizing the fourth highest bit to determine the sign of theta 2.