| 摘要 |
1,218,967. Digital Fourier analyser; addressing data stores. INTERNATIONAL BUSINESS MACHINES CORP. 26 Sept., 1968 [9 Oct., 1967], No. 45666/68. Headings G4A and G4C. A digital Fourier analyser evaluates the following functions of binary input coefficients C, D, W where subscripts R, I indicate real and imaginary parts:- the analyser comprising means for multiplying each of D R and D, by both W R and W 1 , means for determining the signs of the "DW" products formed, complementing means responsive to the sign determining means for complementing to one those 'DW" products which are negative, modifier means for modifying C 1 and C R to provide two outputs for each of these inputs in accordance with the following rules:- (a) if the corresponding input is negative, it is complemented to one, and (b) either the input, or its complement (as the case may be) has 1 added for each complemented product in the corresponding formula, 1 added if the corresponding part of the C input is negative, and 1 added for each negative term in the corresponding formula, and adding means for adding together the modified C terms and the "DW" products in accordance with the above formulµ. General.-Digital Fourier analysis is done in real-time according to the Cooley-Tukey or Danielson-Lanczos algorithm involving a series of calculations each of which obtains results A, B from quantities C, D and a weight W, where C, D are original inputs or results obtained in previous calculations in the series. The real and imaginary parts (indicated by subscripts R, I) of A, B, C, D, W in a given calculation are related by:- since A, B, C, D, W are complex numbers. The weights W are in general different for different calculations in the series. The factors for a given calculation are obtained from memory and supplied to an arithmetic unit, the results from which are stored in the memory in preparation for subsequent calculations in the series. Arithmetic unit (Figs. 3a, 3b).-The factors W R , W I , D R , D I , C R , C I , which are signed binary numbers, are placed in registers 311, 309, 307, 305, 303, 301, respectively. Pre-multipliers 321, 323 obtain the multiples 1 to 7 of W R and W 1 respectively (ignoring sign), the multiples being supplied to selection logic units 325, 327, 329, 331. These and post-multipliers 333, 335, 337, 339, form D R W R , D 1 W R , D I W 1 , D R W I respectively (excluding signs) by using each triple of bits of D R , D I to select an appropriate multiple from the respective pre-multiplier 321, 323 and forming the products by adding the selected multiples suitably displaced. The signs of the products are evaluated by sign logic 312, and the products ones-complemented (if negative) or not (if positive) at 313, 315, 317, 319. The sign logic 312 also controls modified twos-complementors (see "rules (a) and (b)" above for details) 341, 343 (involving adders) fed with C R , C I , respectively, so that adders 345, 347, 349, 351 and following twos-complementors 353, 355, 357, 359 (which involve adders and can perform round-off) provide the quantities 2A R , 2A I , 2B R , 2B I , respectively, these quantities being stored in shift registers 361, 363, 365, 367 with a one-bit displacement to remove the factors 2. If the two highest order bits (excluding the sign bits) in all these shift registers are zero, scaling logic 375 causes the outputs of the shift registers to be shifted one bit position to high order by NAND gates at 369, 371, 373, 374. The total number of shifts which occur in this way (throughout the series of calculations) is counted. Addressing the memory.-Fig. 4 shows the circuitry for the Danielson-Lanczos case. A timing pulse generator 407 counts up binary counters 401, 409, 403. Each overflow of counter 401 shifts a shift register 413 and bit box 421 (connected in a loop) and clears counter 403 and a register 405. Adder 417 adds the contents of shift register 413 and bit box 421 to the contents of counter 403. Adder 419 adds the contents of shift register 413 to the contents of register 405. On equality between shift register 413 and counter 409, comparator 415 clears counter 409 and gates the adders 417, 419 to counter 403 and register 405, respectively. Counter 401 provides the address of A, and with a high order 1 appended the address of B. The addresss of D, C, W are provided by adder 417, counter 403 and register 405, respectively. The circuitry for the Cooley-Tukey case differs in that the upper input to adder 419 is simply 1, the A and B addresses come from counter 403 and adder 417, respectively, the W address is re-, versed end-for-end before use, and the FF411 shown in Fig. 4 for memory selection is omitted. |
