Phase 6 serial key or number

Promira Platform System User Manual v

Changes in version

Added auto start feature.

Updated text for upgrades()

Changes in version

Improved the connection to Windows.

Changes in version

Added features for Promira platform with eSPI Analysis Application.

Updated Applications section.

Changes in version

Fixed the connectivity issue of the first attempt to connect the Promira platform to the Promira API pm_load function after the device reset.

Changes in version

Added features for Promira platform I²C Active Level 2 Application and SPI Active Level 3 Application.

Changes in version

Added features for Promira platform SPI Active Level 2 Application.

The Promira Serial Platform with the I²C/SPI Active applications and eSPI Analysis application supports I²C master/slave active modes; Single, Dual, and Quad SPI master/slave active modes; and Single, Dual and Quad eSPI analysis modes. The Promira platform supports up to 8 SPI SS/CS signals, up to 16 GPIO signals, and up to 11 eSPI Digital IO signals depending on purchased application. The Promira platform connects to an analysis computer via Ethernet or Ethernet over USB. The applications installed on the Promira Serial Platform are field-upgradeable and future-proof.

Notes:

(1) Ultra Slave will be released at a future date.

Pinouts

Pin Description

Note:

(1) The pin description in this table is for Promira FW v/v and above.

USB Compliance

The Promira Serial Platform is USB compliant and will operate as a high speed ( Mbps) device on a USB  hub or host controller. For additional information see table

Physical Specifications

• Dimensions: W x D x L: mm x mm x mm (" x " x ")
• Weight: g ( lbs)

Promira Boot Process

Promira General Boot Process

1. Promira platform is off, and 3 leds are off
2. Power on Promira platform by connecting it to computer USB connector.
3. In about 1 s right led turns red.
4. In about 5 s right led turns blue.
5. Issue Promira API function pm_load, or connect Promira platform to Control Center Serial or Flash Center.
6. In about 1 us right led turns green, and Promira platform is ready to transfer data.

Promira FW Update Boot Process

1. Right led is green, and Promira platform is ready to transfer data.
2. Issue FW update in Control Center Serial or Promira Update Utility.
3. 3 leds turn off.
4. In about 1 s right led turns red.
5. In about 5 s all 3 leds turn blue.
6. Promira platforms appears as a hard drive on the computer.
7. Copy pmu file to Promira hard drive on the computer
8. Eject safely the Promira hard drive from the computer.
9. Reboot Promira platform by disconnecting and connecting the USB cable.
10. In about 1 s right led turns red.
11. In about 5 s all 3 leds turn blue.
12. In about 5 s all 3 leds flash blue (one at a time).
13. Promira platform automatically reboots: Bullets in General Boot Process section are occurred.

Promira License Update Boot Process

The steps are similar to the Promira FW Update Boot Process steps. However, it is faster, and without step

Compatibility

Overview

The Promira Serial Platform software is offered as a bit or bit Dynamic Linked Library (or shared object). The specific compatibility for each operating system is discussed below.

Windows Compatibility

The Promira Serial Platform software is compatible with bit and bit versions of Windows 7, and Windows 8/ The software is provided as a bit or bit application.

Linux Compatibility

The Promira Serial Platform software is compatible with bit and bit standard distributions of Linux with kernel and integrated USB support including: Red Hat, Ubuntu, Fedora, and SuSE. The software is provided as a bit or bit application. When using the bit library on a bit distribution, the appropriate bit system libraries are also required. When using either the bit library or 32 bit library, the appropriate system libraries are also required.

Mac OS X Compatibility

The Promira Serial Platform software is compatible bit and bit Intel versions of Mac OS X Lion, Mountain Lion, Mavericks, Yosemite, and El Capitan. The software is provided as a bit or bit application. Installation of the latest available update is recommended.

Connectivity

There are two ways to connect to the Promira Serial Platform: via USB or via Ethernet. No additional device drivers are required for using either method.

USB

The Promira Serial Platform uses Ethernet over USB, which allows the host software to connect to the adapter via an IP address. To use this interface, connect the device to your PC with a USB cable and follow the instructions below to set up the connection on the PC.

For Ethernet over USB, the Promira Serial Platform is a DHCP server that dynamically distributes network configuration parameters, such as IP addresses for interfaces and services.

Windows

1. Connect Promira to PC with USB cable.
2. After the device is connected to the development PC, Windows will automatically search for the appropriate RNDIS driver. To verify the drive is installed correctly, right-click on Computer and select Manage. From System Tools, select Device Manager. If the Total Phase Promira platform shows up with an exclamation mark, continue to the next step and install the driver. Otherwise, close this window, skip RNDIS driver installation in the next step and continue to the following step.
3. Install RNDIS driver:
   1. Right-click on Total Phase Promira platform device and select Update Driver Software When prompted to choose how to search for device driver software, choose Browse my computer for driver software.
   2. Browse for driver software on your computer will come up. Select Let me pick from a list of device drivers on my computer.
   3. A window will come up asking to select the device type. Select Network adapters, as RNDIS emulates a network connection.
   4. In the Select Network Adapter window, select Microsoft Corporation from the Manufacturer list. Under the list of Network Adapter:, select Remote NDIS compatible device.
   5. The Total Phase Promira platform device is now installed and ready for use.
4. From the Start menu, select Control Panel | Network and Internet | Network and Sharing Center.
5. Select Change adapter settings on the left panel.
6. Right-click on the USB Ethernet/RNDIS Gadget adapter, select Properties.
   

   Figure 1 : Windows Change adapter settings window.
7. Double click on Internet Protocol Version 4 (IPv4).
   

   Figure 2 : Windows Network Interface Properties dialog.
8. Select Obtain IP address automatically and also select Obtain DNS server address automatically.
   

   Figure 3 : Windows IPv4 Properties dialog.
9. Select OK and Close to dismiss the dialogs.
10. In order to make sure it is ready or to know the IP address of the Promira Serial Platform, right-click on the USB Ethernet/RNDIS Gadget adapter, select Status and then select Details. The IP address assigned to the network interface on the host PC is will be in the format of x.x.x and is listed as the IPv4 Address. The IP address of the device will be at the preceding address. For example, the image below shows for the host IP address. The device address will then be This device address will also be displayed in the Control Center software and will be needed when connecting to the device using the API.
    

    Figure 4 : Windows Connection Details.
11. Select OK and Close to dismiss the dialogs.

Linux

1. Download the Promira Serial Platform Linux support files from the website and follow the instructions in the manicapital.com file.
2. Connect Promira to PC with USB cable.
3. Use to determine the network interface of Promira. If you do not recognize which one is the new interface, compare the lists from before and after plugging in the device.
4. The Promira Serial Platform will be shown as tppx.

Mac OS X

1. Connect Promira to PC with USB cable.
2. Select Network under System Preferences.
3. Select Total Phase Promira Platform.

Figure 5 : Mac OS X Network Preferences window.

1. Select Using DHCP from the Configure IPv4: dropdown list box.
2. Select Apply to apply the changes.

Ethernet

The Promira platform can be connected to the computer through the Ethernet port. The Promira network preference for Ethernet is configurable by the Control Center Serial. The Promira platform can be configured to static IP addressing or dynamic IP addressing (DHCP). The default network preferences of the Promira platform for Ethernet is a static and its IP address is This IP address can be changed using the promira command-line application provided in the util folder in the Promira API package. For more details see the Control Center Serial manual section Configuring Network Preference and the manicapital.com file in the API package.

Detecting IP addresses

To detect the IP addresses to which the Promira Serial Platforms are attached, use the routine as described in following API documentation. Alternatively, the Control Center software can be used to list the available devices.

Dynamically Linked Library

The Promira requires the Promira DLL to operate and is only compatible with the Promira Serial Platform.

In addition to the Promira DLL, the Aardvark Compatibility DLL is provided to make the Aardvark API available for legacy and compatibility purposes.

DLL Location

Total Phase provides language bindings that can be integrated into any custom application. The default behavior of locating the Promira DLL and the Aardvark Compatibility DLL is dependent on the operating system platform and specific programming language environment. For example, for a C or C++ application, the following rules apply:

On a Windows system, this is as follows:

1. The directory from which the application binary was loaded.
2. The applications current directory.
3. bit system directory (for a bit application). Examples:
   • [Windows 7/8 bit]
   • [Windows 7/8 bit]
4. bit system directory (for a bit application). Examples:
   • [Windows 7/8 bit]
5. The Windows directory. (Ex: )
6. The directories listed in the PATH environment variable.

On a Linux system, this is as follows:

1. First, search for the shared object in the application binary path. If the filesystem is not present, this step is skipped.
2. Next, search in the applications current working directory.
3. Search the paths explicitly specified in .
4. Finally, check any system library paths as specified in and cached in .

On a Mac OS X system, this is as follows:

1. First, search for the shared object in the application binary path.
2. Next, search in the applications current working directory.
3. Search the paths explicitly specified in .
4. Finally, check the /usr/lib and /usr/local/lib system library paths.

If the DLL is still not found, an error will be returned by the binding function. The error code is for the management API and for the application API.

DLL Versioning

The Promira Compatibility DLL checks to ensure that the firmware of a given device is compatible. Each DLL revision is tagged as being compatible with firmware revisions greater than or equal to a certain version number. Likewise, each firmware version is tagged as being compatible with DLL revisions greater than or equal to a specific version number.

Here is an example.

Hence, the DLL is not compatible with any firmware less than version  and the firmware is not compatible with any DLL less than version  In this example, the version number constraints are satisfied and the DLL can safely connect to the target firmware without error. If there is a version mismatch, the API calls to open the device will fail. See the API documentation for further details.

Field Upgrades

Upgrade Philosophy

The Promira Serial Platform is designed so that its internal firmware (FW) and License can be upgraded by the user, thereby allowing the inclusion of any additional applications purchased, software support renewals, performance enhancements, or critical fixes available after the receipt of the device.

The Promira Serial Platform shows multiple FW version numbers in the Control Center Serial GUI Configure Adapter window, Flash Center GUI - Add Adapters window, Data Center GUI connect window, and the Promira Utility window. The first one is the version number of the system FW and the others are the version numbers of the various Promira applications. For example, the FW numbers //manicapital.com represent FW system v and FW application v and so on.

Promira API has four main FW functions: pm_version, pm_app_version, ps_app_version, and pa_app_version. Promira API function pm_version returns FW system version and Promira API functions pm_app_version, ps_app_version, and pa_app_version return FW application versions.

Upgrade Procedure

Basic steps for License or Firmware Update with Promira Utility

• Step 1 - Connect the USB port of the Promira platform to the PC.
• Step 2 - Run the Promira Update Utility.
• Step 3 - Select the desired Promira Serial Platform by clicking on Promira button.
• Step 4 - Click the Update License/Firmware button to put the device into update mode and have it show up as a storage device on the PC.
• Step 5 - Copy the downloaded <name>.pmu file to the storage device.
• Step 6 - Power cycle the Promira platform.

Please refer to the Promira Utility product for more information on how to upgrade the firmware and license on the Promira Serial Platform.

Introduction

The Promira API documentation that follows is oriented toward the Promira Rosetta C bindings. The set of Promira API functions and their functionality is identical regardless of which Rosetta language binding is utilized. The only differences will be found in the calling convention of the functions. For further information on such differences please refer to the documentation that accompanies each language bindings in the Promira API Software distribution.

General Data Types

The following definitions are provided for convenience. All Promira data types are unsigned.

Notes on Status Codes

Most of the Promira API functions can return a status or error code back to the caller. The complete list of status codes is provided at the end of this chapter and in the Promira applications' user manuals. All of the error codes are assigned values less than 0, separating these responses from any numerical values returned by certain API functions.

Application Management Interface

Application Management

Find Devices (pm_find_devices)

Get a list of IP addresses to which Promira adapters are attached.

Find Devices (pm_find_devices_ext)

Get a list of IP addresses and unique IDs to which Promira Serial Platforms are attached.

Open a Promira Serial Platform (pm_open)

Open a connection to a Promira Serial Platform.

Close the Promira Device (pm_close)

Close the connection to the Promira adapter.

Version (pm_version)

Return the version matrix for the system connected to the given handle.

Sleep (pm_sleep_ms)

Sleep for given amount of time.

Status String (pm_status_string)

Return the status string for the given status code.

Applications (pm_apps)

Return the installed applications.

Licensed Applications (pm_licensed_apps)

Return the licensed applications.

Application Version (pm_app_version)

Return the version matrix for the given application in the system connected to the given handle.

Launch an Application (pm_load)

Launch an application.

Launch an Application (pm_load_ext)

Launch an application.

Query Network Configurations (pm_query_net)

Get the Ethernet network interface properties for this Promira handle.

Configure Network Configuration (pm_config_net)

Configure the Ethernet network interface.

Query Preferences (pm_query_pref)

Get preferences.

Configure Preferences (pm_config_pref)

Configure the preferences.

Read License (pm_read_license)

Read the entire license.

Features (pm_features)

Return the features licensed for the application.

Feature Value (pm_feature_value)

Return the value of a feature for the application.

Feature Description (pm_feature_description)

Return the description of a feature for the application.

Error Codes

Disclaimer

All of the software and documentation provided in this manual, is copyright Total Phase, Inc. ("Total Phase"). License is granted to the user to freely use and distribute the software and documentation in complete and unaltered form, provided that the purpose is to use or evaluate Total Phase products. Distribution rights do not include public posting or mirroring on Internet websites. Only a link to the Total Phase download area can be provided on such public websites.

Total Phase shall in no event be liable to any party for direct, indirect, special, general, incidental, or consequential damages arising from the use of its site, the software or documentation downloaded from its site, or any derivative works thereof, even if Total Phase or distributors have been advised of the possibility of such damage. The software, its documentation, and any derivative works is provided on an "as-is" basis, and thus comes with absolutely no warranty, either express or implied. This disclaimer includes, but is not limited to, implied warranties of merchantability, fitness for any particular purpose, and non-infringement. Total Phase and distributors have no obligation to provide maintenance, support, or updates.

Information in this document is subject to change without notice and should not be construed as a commitment by Total Phase. While the information contained herein is believed to be accurate, Total Phase assumes no responsibility for any errors and/or omissions that may appear in this document.

Life Support Equipment Policy

Total Phase products are not authorized for use in life support devices or systems. Life support devices or systems include, but are not limited to, surgical implants, medical systems, and other safety-critical systems in which failure of a Total Phase product could cause personal injury or loss of life. Should a Total Phase product be used in such an unauthorized manner, Buyer agrees to indemnify and hold harmless Total Phase, its officers, employees, affiliates, and distributors from any and all claims arising from such use, even if such claim alleges that Total Phase was negligent in the design or manufacture of its product.

Contact Information

Total Phase can be found on the Internet at manicapital.com If you have support-related questions, please go to the Total Phase support page at manicapital.com For sales inquiries, please contact sales@manicapital.com

[ Dec. 4, HIGH BASE MULTIPLE RAIL FOURIER TRANSFORM SERIAL STAGE [75] Inventor: Richard E. Llewellyn, Greenbelt,

[73] Assignee: Westinghouse Electric Corporation,

Pittsburgh, Pa.

[ Filed: Feb. 8, 21 App]. No.: ,

' OTHER PUBLICATIONS G. D; Bergland, Fast Fourier Transform Hardware Implementations An Overview, IEEE Trans. Vol. AU No. 2 June , pp.

Primary ExaminerFelix D. Gruber Assistant Examiner-David l-l. Malzahn Att0rney--F. H. Henson et al.

[57] ABSTRACT A serial processor section for use in a parallel-serial processor of a multiple-input Fast Fourier Transform (FFT) machine wherein a base higher than 2 is used for the expansion of the cooley-Tukey'algorithm. The" serial processor section utilizes a plurality of serial processor stages, each having a number of rails equal to the number of the base used to expand the Fourier series equations, with each rail being an input and an output line to and from the stage. The multiple rails originate at the output of the parallel processor section and pass from serial stage to serial stage in the parallel-serial processor to derive the desired outputs therefrom. Appropriate delay means, multiplier means and summing circuits are utilized in the serial processor section in order to generate outputs therefrom in accordance with the Cooley-Tukey algorithm.

19 Claims, 13 Drawing Figures PATENTED 4W5 3.

SHEET 1 OF 3 4 RAlL 4 RAlL BASE4 BASE4 SERIAL SERIAL 5 STAGE STAGE --p PARALLEL-SERIAL4-RAIL PROCESSOR //0 2 4RA|L 4RA|L SEER. @? 1 STAGE STAGE 4 RAIL 4RAIL BASE4 BASE4 SERIAL SERIAL STAGE STAGE PARALLEL-SERIAL 8- RAIL PROCESSOR USING DUAL 4-RA\L SERIAL STAGES FIG. 3

PATENTED l A (5) A1 (9) A; (13) MIZ) (2) 1M6) l A (i4) A ll3) SHEET 2 UF 3 MN) A (l5) FIG. 7

EXPANSION BASE TOTAL BASE 2 EQUIVALENT MMBER OF"RA|LS" ADDERS MULTIPLIERS ADDERS ADDERS MUL'HPUERS 'IDTAL AIDERS SAVING 4 I6 I2 I00 [6 I6 I28 22% HIGH BASE MULTIPLE RAIL FOURIER TRANSFORM SERIAL STAGE BACKGROUND OF THE INVENTION The invention relates to a parallel-serial processor or stage for a multiple-input Fast Fourier Transform (FFT) machine which can be used to perform functions such as spectral analysis. The invention particularly concerns a processor stage using a base higher than 2 for the expansion of the algorithm and results in a considerable savings in hardware requirements.

2. Description of the Prior Art It, is known that time and frequency domain analyses are related through Fourier series and transforms, and that given a variable expressed as a function of time, Fourier analysis will break down the variable into a sum of oscillatory functions, each having a specific frequency. This technique has many useful applications as,'for example, in spectral analysis. These frequencies, with their corresponding amplitudes and phase angles, will comprise the frequency contents of the original variable. The technique of Fourier transform analysis for digital computers called the Fast Fourier Transform method (FFT) utilizes computers in frequency domain analyses. This method, known as the Cooley-Tukey method (see An Algorithm For the Machine Calculation of Complex Fourier Series," Math. Computation, Volume 19, pages l, Apr. ) reduces the number of multiplications and the resulting hardware required in calculating the frequency contents of a time function by a significant factor compared to the direct method of computation.

The use of parallel-serial stages to expand the Fourier series equations is known in the art. However, known serial stages of a parallel-serial transform machine utilize expansion bases of 2 in order to generate the Cooley-Tukey algorithm. However, a base 2 expansion stage is not efficient compared to higher base expansion stages because of the greater number of arithmetic computations required by a base 2 stage, which correspondingly requires additional hardware.

SUMMARY OF THE DISCLOSURE This and other disadvantages of the prior 'art are solved by the instant invention which relates to a processor stage for a multiple-input Fast Fourier Transform (FFT) machine utilizing expansion bases higher than 2 for the Cooley-Tukey algorithm which it implements. The attendant advantage of using higher base recursive equations considerably reduces the hardware required to perform the arithmetic computations.

More specifically, the invention concerns a multirail serial processor stage for a parallel-serial Fast Fourier Transform (F FT) machine for such exemplary uses as a spectral analyzer or a digital filter-bank. The serial stage according to the invention utilizes a number of rails equal to the number of the base used to expand the Fourier series equations, wherein each rail is an input and output line to and from the stage. The multiple rails originate at the output of the parallel stageand pass to successive serial stages in the parallelserial processor in order to derive the desired output therefrom. The processor stage includes appropriate delay means and register sections, and multiplying sections to generate the desired sequences in order to provide the desired expansion of the input to the summing section. The processor stage according to the invention provides a significant decrease in the number of multipliers required compared to the prior art, thereby significantly reducing the complexity, size, and cost of the hardware required.

BRIEF DESCRIPTION OF THE DRAWINGS FIG. 1 is a block diagram of a parallel-serial base 4 4 rail processor according to the invention;

FIG. 2 is a block diagram of a parallel-serial base rail processor using dual base rail serial processor stages according to the invention;

FIG. 3 is an expanded block diagram of a base rail serial processor stage, similar to the type that may be used in the processors of FIGS. 1 and 2;

FIGS. 4A through 4G are a series of diagrams illustrating register loading procedures;

F IG. 5 is a diagram of a base rail serial processor stage;

FIG. 6 explains the symbols of the summing circuit section of FIG. 5; and

FIG. 7 is a table showing the relative hardware savings achieved by the invention.

DETAILED DESCRIPTION OF THE INVENTION FIG. 1 illustrates a serial stage processor according to the invention connected to the output of parallel processor stage 1. If a base 4 expansion is desired, the output of base 4 parallel processor stage 1, having four rails 2, 3, 4 and 5, is applied to the input of the 4 rail base 4 serial stage 6. The mechanization of a system according to the invention depends upon the number of rails being equal in number to the base of the Cooley- Tukey expansion that is used. Each serial stage has as outputs the same number of rails as are fed into it. Thus, with respect to FIG. 1, the four rail outputs of serial stage 6 are fed to the input of 4 rail base 4 serial stage 7. Two serial stages connected as shown are required in order to provide the desired expansion as explained hereafter. If it is desired to use base 4 serial stages in an 8 rail parallel-serial machine, two base 4 serial stages can be paralleled as shown in FIG. 2. Thus, FIG. 2 shows base 8 parallel stage 9 having an 8 rail output, four rails of which are applied to the input of 4 rail base 4 serial stage 10, and the other four rails of which are applied to the input of 4 rail base 4 serial stage The four rail outputsof stages 10 and 11 are in turn connected to the four rail inputs of 4 rail base 4 serial stages 12 and 13, the additional serial stages being required in order to provide the desired expansion.

FIG. 3 illustrates in further detail a base 4 serial stage of the type comprising serial stages 6 and 7 of FIG. 1, and 10 through 13 of FIG. 2. Each serial stage may be broken down into five general sections. The first section (I) is a set of delay lines 14, 15 and 16 which align the incoming data in the proper position. The delay lines are selected to enable such alignment and their time delays are related to the number of rails. Thus, with respect to FIG. 3, the top rail has no delay line, and the next rail has a delay line 14 with a delay line equal to %N, wherein N is a constant selected to set the delay line to enable the desired alignment of incoming data A( 0) through A( 15). The remaining two rails have delay lines of 2/4N and %N. The second section (II) comprises cyclical switch means (not shown) which are conventional in the art, which switch the outputs from the top rail and the delay lines 14, 15 and 16 of the secnd, third, and fourth rails, respectively into the top rail and the delay lines 17, 18 and 19, respectively of the second, third, and fourth rails. In the base rail serial stage of FIG. 3, the cyclical switch has four operating positions wherein during each position setting, the third section (III) comprising delay lines 17, 18 and 19, is connected to receive a fourth of the data to be handled in the integration period. The delay lines 17, 18 and 19 store the applied data long enough to enable an entire integration period to appear in parallel at the output of the third section. Consider the example of N 16 samples or digital words, i.e., A(0) to A( of a given integration period, such as appear serially on input J=0 in FIG. 3. The first four samples A(0) to A(3), corresponding to AN are supplied to delay 19 in the first switch position, the next four samples A(4) to A(7) to delay 18 in the second switch position, A(8) to A(ll) to delay 17 in the third, and A(l2) to A(15) (without any delay in the line, and hence directly to multiplier section(lll)in the fourth. As shown in detail hereafter, selection of the delays of MN, lN, and %N results in the samples of the entire integration period (i.e., A(0) to A( 15)), appearing in parallel in successive groups of I four at the output of section III. (For example, when A(l2) appears on the top line from J=0, A(8), A(4) and A(0) simultaneously are presented in parallel at the outputs of delays 17, 18 and 19, respectively. 7

Input samples on each of lines J=l J=2, and J=3 will be loaded in a similar fashion as the above example. Delays 14, 15 and 16 thus are employed to maintain alignment of the data samples of corresponding integration periods on all four lines J=0 to J=3, when desired, although those delays of course are optional where alignment is not required.

The fourth section (IV) comprises multipliers 20, 21 and 22, respectively connected to the outputs of delay lines 17, 18 and 19, with the multiplying angles W W and W being selected to provide the proper phase shift for the Cooley-Tukey algorithm.

In general, the angles for the multipliers are:

m multiplier number p stage number n number of stages r expansion base of stage The fifth section (V) comprises the summing circuit connected to receive the outputs of the fourth section. In FIG. 3, the summing circuit comprises adder means 24 through 31, and multiplier 32 with a multiplying angle 90; the summing circuit is arrahgeaia sim'rfi' incoming terms with the necessary internal phase shifts in order to generate the outputs required by the Cooley-Tukey algorithm.

The serial stage illustrated and explained with respect to FIG. 3, may be used in a parallel-serial 4 rail processor as shown in the block diagram of FIG. 1. In order to illustrate the generation of the required outputs according to the invention, the system of FIG. 1 will be explained in detail. Serial stage 6 of FIG. 2 comprises a base rail serial processor stage as shown in FIG. 3. The operation of the four rails of the input to the cir- Cult of FIG. 3 are independent, and therefore the operation of only one rail will be described herein in order to illustrate the operation of the serial processor stage. Thus it is assumed that the inputs to the top line of FIG. 3 are A(0), A(l) A(15). The delay means 14 through 19 may comprise registers as shown in FIG. 4, having the number of storage positions needed to provide the required delays to effect data alignment. The registers are loaded with data A(0) through A(lS) in the following manner in order to effect the desired alignment and outputs therefrom: A(k k A(0) A(3) load into bottom register A(4) A(7) load into middle register A(8) A(ll) load into top register A(l2) A(15) go directly into summing section The multiplier section operates according to the angle equation:

From the foregoing multiplier angle equation, since a zero degree (0) phase angle results, the multiplier section IV for the first stage does not require any multipliers. Solution of the first recursive equation of the Cooley-Tukey algorithm for a base 4 expansion requires the following results from the summing circuit of the first serial processor stage 6 of FIG. 1 is:

The base 4 expansion of the 4 rail system in accordance with the foregoing requires phase angle shifts in increments of $41 of , or The superscripts 0, 4, 8, and 12 of the W terms correspondingly represent 0, 90, and phase angle shifts.'Moreover, W, or 0, and W or , correspond to addition or subtraction, whereas W", or 90, and W", or , phase angle shifts are readily implemented in hardware. By recognizing redundancies in the foregoing equations, the 4 rail base 4 serial stage of FIG. 3 is thus accomplished through the use of only three multipliers 20, 21 and 22 and eight adders in the summing section V, the latter includingthe single, constant phase shift multiplier From the foregoing equations, it is clear from FIG. 3 that the multiplier 32 is positioned to afford the necessary internal phase shifts to the samples processed in the summer section V.

The output from serial stage 6 is applied to the input of serial stage 7 of FIG. l. The register loading proceeds according to samplings as indicated in FIGS. 4A to 4G.

The angles of the multipliers of the second serial processor stage are chosen according to the following equation:

W WU m, therefore:

W =W W2: W0, W3: W

The multiplier section thus generates the following sequences in order to provide the desired outputs from the I summing section of the second serial processor stage. The results from the summing section are as follows:

An analysis of the foregoing outputs from the summing section of thesecond stage reflect that in addition to the 90 increments of phase shift, W, W, W and W", (and which are provided by the constant phase shift multiplier of the summing section V), certain variable phase shifts'(i.e., which changeas a function of the input samples) are required. These phase shifts are achieved by the variable phase shift multipliers 20, 21 and 22 of section IV in FIG. 3.

An analysis of FIG. 3 in light of the foregoing equations demonstrates that the variable phase shift multipliers are so positioned as to produce the requisite total phase shifts through the stage.

By writing the equations for the output of the summing section in terms of the input to the first stage, A the output equations become:

* fixed and variablehave been delineated from the The described combination of the first and second serial stages taken in conjunction with the procedure for register loading, multiplier angles, and summing circuit thus functions to generate the desired sequences in order to provide the expansion according to the C ley-Tukey algorithm. It particularly will be appreciated from the foregoing that the present invention is a further extension of the symmetry recognized in the C ley-Tukey algorithm, in that two types of phase shifts expansions (at a base greater than 2) and that the fixed phase shifts have been introduced in summing section V. The symmetry of the summing section V thereby resulting enables use of a common summing section for all four rails. Moreover, by performing the fixed phase shift in the summing section, the burden on the requisite function of the variable phase shift multipliers of section IV is reduced, permitting an overall simplification of the serial stage and particularly permitting reducing the number of multipliers.

FIG. 5 is a diagram showing a base rail serial processor stage according to the invention showing the configuration of the five general sections discussed with respect to FIG. 3. FIG. 6 explains the symbols of FIG. 5 relating to the summing section, which is believed to be self-explanatory.

The complex diagram for a base 8, 8 rail stage is shown in FIG. 5. If the base of Cooley-Tukey expansion is chosen to be a power of 2, the summing section can be greatly reduced by taking advantage of the multiplier of 2. If an expansion base that is not a power of 2 is used, then hard-wired multipliers will have to be used in the summing section. The use of base 8, of course, defines the smallest incremental phase shift to be one-eighth of , or As in the case of the base 4 expansion, the constant angle phase shifts again are performed in the summing section.

The extension to higher bases than 8 is fairly simple. For bases higher than 4, multipliers must be added to the summing circuitry. The phase shift elements, as noted, need not be multipliers, since this function is readily performed. The additional multipliers required for the base 8 stage (FIG. 5) are not overly complicated (i.e., 45 and in addition to 90, as to which comment is made above), but base 16 and higher bases require a much larger number of multipliers, minimizing the advantage of going to a stage with a base higher than 8. The invention contemplates the use of one or more serial processor stages and the use of any base number greater than 2, and the specific examples disclosed herein are exemplary systems of the invention.

The advantage of this invention is that it will significantly reduce the hardware required to perform the arithmetic in a serial stage of a parallel-serial processor. The table of FIG. 7 gives a comparison of the hardware required for three different base serial stages. Since a stage with a base higher than two is the equivalent of several base two stages, the equivalent base 2 hardware is tabulated for comparison. If it is assumed that there are seven adders per multiplier, it is seen that a considerable savings is effected.

It appears from the table that the savings achieved from a higher base serial stage is only from a reduction of the multipliers. A further, more subtle hardware savings can be found, however, by using a higher base stage. Since a higher base stage replaces several base 2 stages, many items that are one of a kind in each type stage, such as switches, registers, etc., can be saved by using one higher base stage. For example, in the design of a processor according to the invention, a percent total reduction in nonmemory hardware was achieved by replacing the base 2 stages by base 4 stages. Thus the percentage savings is larger than indicated in the table because of the other component savings.

What is claimed is:

l. A processor having parallel and serial processor sections for a Fast Fourier Transform (FFT) machine using expansion bases higher than 2 for the implementation of the Cooley-Tukey algorithm comprising:

first and second sequentially connected serial processor stages for input data, each of the first and second serial processor stages having:

a plurality of input and output means equal in number to the expansion base thereof,

alignment means connected to the plurality of input means to align the input data in a predetermined position,

means connected to the output of the alignment means to arrange an entire integration period of the data in parallel,

multiplier means connected to the last recited means and receiving variable phase shift multiplying angle inputs to provide the proper phase shift for the parallel data in accordance with the algorithm, and I a summing circuit connected to receive the output of the multiplier means and including constant phase shift means to generate outputs at the output means in accordance with the algorithm;

the parallel processor section having a number of output means equal to its base expansion number, and wherein the input means of the first serial processor stage is connected to the output means of the parallel processor section, and the input means of the second serial processor stage is connected to the output means of the first serial processor stage to receive as input data the generated outputs therefrom.

2. A processor as recited in claim 1 wherein the alignment means comprise first delay means.

3. A processor as recited in claim 2 wherein the means to arrange the data in parallel comprise second delay means.

4. A processor as recited in claim 3 wherein the first and second delay means comprise interacting register means.

5. A processor as recited in claim 1 wherein the parallel processor section has a base expansion number and number of output means twice that of the base expansion number and number of input means of the sequentially connected first and second serial processor stages, and further comprising:

additional sequentially connected first and second serial processor stages, the input means of the first additional serial processor stage being connected to the remaining output means of the parallel processor stage.

6. A processor as recited in claim 1 wherein the base expansion number and number of output means of the parallel processor section is equal to the base expansion number and number of input and output means of the first and second serial processor stages.

7. A serial processor for a Fast Fourier Transform (FFT) machine using expansion bases higher than 2 for the implementation of the Cooley-Tukey algorithm comprising:

at least one serial processor stage for input data having a plurality of input and output means equal in number to the expansion base of the serial processor, alignment means connected to the plurality of input means to align the input data in a predetermined position, means connected to the output of the alignment means to arrange an entire integration period of the data in parallel, multiplier means connected to the last recited means having variable shift multiplying angles associated therewith to provide the proper phase shift for the parallel data in accordance with the algorithm, a summing circuit connected to receive the output of the multiplier means and including constant phase shift means to generate outputs at the output means in accordance with the algorithm.

8. A serial processor as recited in claim 7 wherein the alignment means comprise first delay means.

9. A serial processor as recited in claim 8 wherein the means to arrange the data in parallel comprise second delay means.

A serial processor as recited in claim 9 wherein the first and second delaymeans comprise interacting register means.

A serial processor as recited in claim 7 connected to receive the output of a parallel processor section, the parallel processor section having a number of output means equal to the base expansion number.

A serial processor stage for a Fast Fourier Transform machine using an expansion base higher than 2 for the implementation of the Cooley-Tukey algorithm comprising:

input means for converting a succession of input samples of a desired integration period including a predetermined number of samples into a plurality of successive groups of equal numbers of samples, and presenting the corresponding samples of said groups in parallel,

a multiplier section for receiving the plural groups of samples from said input means and producing a corresponding number of plural parallel outputs,

a summing section receiving the parallel outputs of said multiplier section and producing a corresponding number of plural parallel outputs,

said summing section including a plurality of summers and means for multiplying selected ones of said samples by constant phase shifts in accordance with the algorithm, and

said multiplier section including multipliers for multiplying selected ones of the samples by variable phase shifts whereby the phase shifts of samples produced through said multiplier and summing sections, and the summing of samples by said summing means, are in accordance with the algorithm.

A serial processor stage as recited in claim 12 wherein said input means includes switching means, and

storing means having a number of inputs corresponding to the number of groups,

said switching means supplies said groups of samples to said inputs of said storing means, in succession,

and

said storing means includes individual storing means of selected, different storage time periods connected to said inputs for receiving and storing respectively associated ones of said groups of samples for different time periods so as to present the corresponding samples of said groups in parallel to said multiplier section.

A serial processor stage as recited in claim 12 wherein:

said multipliers of said multiplier section receive corresponding ones of said groups of samples and variable phase shift inputs W, in accordance with wherein m the number of the multiplier stage number of the serial stage in a cascaded arrangement of plural serial stages n the number of cascaded serial stages r expansion base of stage W= exp (21ri/N)] where N number of samples in the integration period.

A serial processor stage as recited in claim 12 wherein said constant phase shift multiplier of said summing section performs phase shifting in accordance with phase shift angles having a smallest increment of divided by the base of the stage.

A serial processor stage as recited in claim 15 and implemented for a base 4 expansion, wherein the constant phase shift multiplier of said summing section performs phase shifting in accordance with phase shift angles having a smallest increment of A serial processor stage as recited in claim 16 wherein said summing section includes a single 90 phase shifter as the constant phase angle multiplier.

A serial processor stage as recited in claim 15 and implemented for a base 8 expansion, wherein the constant phase shift multiplier of said summing section performs phase shifting in accordance with phase shift angles having a smallest increment of

A serial processor stage as recited in claim 18 wherein said summing section includes 45, 90 and l35 phase shifters as the constant phase angle multipli-