Method and apparatus for storing complex numbers to allow for efficient complex multiplication operations and performing such complex multiplication operations

• US 5,936,872 A
• Filed: 12/20/1995
• Issued: 08/10/1999
• Est. Priority Date: 09/05/1995
• Status: Expired due to Term

• Current Assignee: Intel Corporation
• Original Assignee: Intel Corporation
• Inventors: Fischer, Stephen A., Mennemeier, Larry M., Kowashi, Eiichi, Peleg, Alexander D., Dulong, Carole
• Primary Examiner(s): Malzahn, David H.
• Application Number:
  US08/575,966
• Time in Patent Office: 1,329 Days
• Field of Search: 364/754.03, 364/724.16, 364/736.02, 364/748.07, 395/562
• US Class Current: 708/622
• CPC Class Codes: G06F 7/4812 Complex multiplication

Abstract

The invention provides a method and apparatus for storing complex data in formats which allow efficient complex multiplication operations to be performed and for performing such complex multiplication operations. According to one aspect of the invention, a method for multiplying complex numbers is provided for use in a data processing system. In response to receiving an instruction, eight data elements are read and used to generate a resulting complex number. These eight data elements were previously stored as packed data and include two representations of each of the components of a first and second complex number. Each of these representations is signed such that it represents either the positive or negative of said component. As a result of the manner in which these eight data elements are stored, the resulting complex number represents the product of the first and second complex numbers. According to another aspect of the invention, a machine-readable medium is described. This machine-readable medium has stored thereon data representing sequences of instructions which, when executed by a processor, cause that processor to perform the above described method.

Claims

1. In a data processing system that executes a program of instructions, a method for multiplying complex numbers comprising the steps of:

A) receiving a first instruction;

B) in response to said first instruction;

B1) reading eight data elements stored as packed data, a first subset of said eight data elements including two representations of each of the components of a first complex number, a second subset of said eight data elements including two representations of each of the components of a second complex number, wherein each representation of said components either represents the positive or negative of said component; and

B2) generating a resulting complex number representing the product of said first and second complex numbers using said first and second subsets.

2. The method of claim 1, wherein a first and a third data element of said first subset each represents the positive of the real component of said first complex number, and a second and a fourth data element of said first subset each represents the positive of the imaginary component of said first complex number.

3. The method of claim 2, wherein a first and a fourth data element of said second subset each represents the positive of the real component of said second complex number, a second data element of said second subset represents the negative of the imaginary component of said second complex number, and a third data element of said second subset represents the positive of the imaginary component of said second complex number.

4. The method of claim 3, said step of generating comprising the steps of:

a) multiplying said first data element of said first subset by said first data element of said second subset to generate a first intermediate result;

b) multiplying said second data element of said first subset by said second data element of said second subset to generate a second intermediate result;

c) adding said first intermediate result to said second intermediate result to generate the real component of said resulting complex number;

d) multiplying said third data element of said first subset by said third data element of said second subset to generate a third intermediate result;

e) multiplying said fourth data element of said first subset by said fourth data element of said second subset to generate a fourth intermediate result; and

f) adding said third intermediate result to said fourth intermediate result to generate the imaginary component of said resulting complex number.

5. The method of claim 2, wherein a first data element of said second subset represents the positive of the real component of said second complex number, a second and a third data element of said second subset each represents the positive of the imaginary component of said second complex number, and a fourth of said second subset represents the negative of the real component of said second complex number.

6. The method of claim 2, wherein a first and a third data element of said second subset each represents the positive of the real component of said second complex number, and a second and a fourth data element of said second subset each represents the positive of the imaginary component of said second complex number.

7. The method of claim 6, said step of generating comprising the steps of:

a) multiplying said first data element of said first subset by said first data element of said second subset to generate a first intermediate result;

b) multiplying said second data element of said first subset by said second data element of said second subset to generate a second intermediate result;

c) subtracting said second intermediate result from said first intermediate result to generate the real component of said resulting complex number;

d) multiplying said third data element of said first subset by said third data element of said second subset to generate a third intermediate result;

e) multiplying said fourth data element of said first subset by said fourth data element of said second subset to generate a fourth intermediate result; and

f) subtracting said fourth intermediate result to said third intermediate result to generate the imaginary component of said resulting complex number.

8. The method of claim 1, wherein those of said eight data elements representing said first complex number are stored in a first packed data item, while those of said eight data elements representing said second complex number are stored in a second packed data item.

9. The method of claim 8 further comprising the initial step of:

storing said eight data elements.

10. The method of claim 9, said step of storing said eight data elements further comprising the steps of:

storing two representations of each of the components of said first complex number at a set of adjacent locations in a memory to generate said first packed data item; and

copying said first packed data item from said memory into a register in a processor.

11. The method of claim 9, said step of storing said eight data elements further comprising the steps of:

receiving a second instruction; and

in response to said second instruction;

reading a third packed data item having at least a first data element and a second data element, said first and second data elements of said third packed data item respectively representing the real component and the imaginary component of said first complex number; and

generating said first packed data item based on said third packed data item.

12. The method of claim 11, wherein said second instruction is one of a pack instruction and an unpack instruction.

13. The method of claim 9, said step of storing said eight data elements further comprising the steps of:

receiving a second instruction; and

in response to said second instruction;

reading a third packed data item having at least a first data element and a second data element, said first and second data elements of said third packed data item respectively representing the real component and the imaginary component of said first complex number;

reading a fourth packed data item having at least a first data element and a second data element, said first and second data elements of said fourth packed data item respectively representing the real component and the imaginary component of said first complex number; and

generating said first packed data item based on said third packed data item and said fourth packed data item.

14. The method of claim 13, wherein said second instruction is a pack instruction.

15. The method of claim 13, wherein one of said first and second data elements of said fourth packed data item is negative.

16. The method of claim 9, wherein said step storing said eight data elements further comprises the steps of:

reading a third packed data item, said third packed data item including a first and a second data element respectively representing the positive of the real and imaginary components of said second complex number;

performing an exclusion OR operation on said third packed data item and a mask to generate a fourth packed data item, said fourth packed data item including a first and a second data element respectively representing the positive of real component and the inverse of the imaginary component of said second complex number;

adding one to said second data element of said fourth packed data item to generate a fifth packed data item, said fifth packed data item including a first and a second data element respectively storing the positive of the real component and the negative of the imaginary component of said second complex number;

generating a sixth packed data item having a first and second data element being respectively representing the positive of the real and imaginary components of said second complex number; and

generating said second packed data item using the data elements in said fifth packed data item and said sixth packed data item.

17. The method of claim 16, wherein said step of generating said second packed data item is performed in response to a second instruction.

18. The method of claim 1, said step of generating further comprising the step of:

writing said resulting complex number as a third packed data item, said third packed data item having a first and second data elements respectively representing the real and imaginary components of said resulting complex number.

19. The method of claim 18, wherein said data elements in said first and second packed data items each contain N bits, and wherein said data elements in said third packed data item each contain 2N bits.

20. The method of claim 18, further comprising the steps of:

C) generating a fourth packed data item based on said third packed data item, said fourth packed data item having a first and second pair of data elements, each of said first pair of data elements representing the real component of said resulting complex number, and each of said second pair of data elements representing the imaginary component of said resulting complex number.

21. In a data processing system that executes a program of instructions, a method comprising the steps of:

A) receiving a first instruction;

B) in response to said first instruction;

B1) reading a first set of eight data elements, said first set of eight data elements including one representation of each of the components of a first, second, third and fourth complex number; and

B2) generating the real component of both a first and second resulting complex number using said first set of eight data elements, said first resulting complex number representing the product of said first and second complex numbers, said second resulting complex number representing the product of said third and fourth complex numbers;

C) receiving a second instruction; and

D) in response to said second instruction;

D1) reading a second set of eight data elements, said second set of eight data elements including one representation of each of the components of said first, second, third, and fourth complex number; and

D2) generating the imaginary component of both said first and second resulting complex number using said second set of eight data elements.

22. The method of claim 21, wherein those data elements in said first set of eight data elements representing the components of said first and third complex numbers are stored in a first packed data item, those data elements in said second set of eight data elements representing the components of said first and third complex numbers are stored in a third packed data item, those data elements in said second set of eight data elements representing the components of said second and fourth complex numbers are stored in a second packed data item, and those data elements in said second set of eight data elements representing the components of said second and fourth complex numbers are stored in a fourth packed data item.

23. A machine-readable medium having stored thereon data representing sequences of instructions, said sequences of instructions which, when executed by a processor, cause said processor to perform steps of:

A) reading a first instruction;

B) in response to said first instruction;

B1) reading eight data elements stored as packed data, a first subset of said eight data elements including two representations of each of the components of a first complex number, a second subset of said eight data elements including two representations of each of the components of a second complex number, wherein each representation of said components either represents the positive or negative of said component; and

B2) generating a resulting complex number representing the product of said first and second complex numbers using said first and second subsets.

24. The machine-readable medium of claim 23, wherein a first and a third data element of said first subset each represents the positive of the real component of said first complex number, and a second and a fourth data element of said first subset each represents the positive of the imaginary component of said first complex number.

25. The machine-readable medium of claim 24, wherein a first and a fourth data element of said second subset each represents the positive of the real component of said second complex number, a second data element of said second subset represents the negative of the imaginary component of said second complex number, and a third data element of said second subset represents the positive of the imaginary component of said second complex number.

26. The machine-readable medium of claim 24, wherein a first data element of said second subset represents the positive of the real component of said second complex number, a second and a third data element of said second subset each represents the positive of the imaginary component of said second complex number, and a fourth of said second subset represents the negative of the real component of said second complex number.

27. The machine-readable medium of claim 24, wherein a first and a third data element of said second subset each represents the positive of the real component of said second complex number, a second and a fourth data element of said second subset each represents the positive of the imaginary component of said second complex number.

28. The machine-readable medium of claim 23, wherein those of said eight data elements representing said first complex number are stored in a first packed data item, while those of said eight data elements representing said second complex number are stored in a second packed data item.

29. The machine-readable medium of claim 28, said sequences of instructions, when executed by said processor, cause said processor to perform the additional step of:

storing said eight data elements.

30. The machine-readable medium of claim 29, said step of storing said eight data elements further comprising the steps of:

storing two representations of each of the components of said first complex number at a set of adjacent locations in a memory to generate said first packed data item; and

copying said first packed data item from said memory into a register in a processor.

31. The machine-readable medium of claim 29, said step of storing said eight data elements further comprising the steps of:

reading a second instruction; and

in response to said second instruction, performing the steps of;

reading a third packed data item having at least a first data element and a second data element, said first and second data elements of said third packed data item respectively representing the real component and the imaginary component of said first complex number; and

generating said first packed data item based on said third packed data item.

32. The machine-readable medium of claim 31, wherein said second instruction is one of a pack instruction and an unpack instruction.

33. The machine-readable medium of claim 29, said step of storing said eight data elements further comprising the steps of:

reading a second instruction; and

in response to said second instruction, performing the steps of;

reading a third packed data item having at least a first data element and a second data element, said first and second data elements of said third packed data item respectively representing the real component and the imaginary component of said first complex number;

reading a fourth packed data item having at least a first data element and a second data element, said first and second data elements of said fourth packed data item respectively representing the real component and the imaginary component of said first complex number; and

generating said first packed data item based on said third packed data item and said fourth packed data item.

34. The machine-readable medium of claim 33, wherein said second instruction is a pack instruction.

35. The machine-readable medium of claim 33, wherein one of said first and second data elements of said fourth packed data item is negative.

36. The machine-readable medium of claim 29, wherein said step storing said eight data elements further comprises the steps of:

reading a third packed data item, said third packed data item including a first and a second data element respectively representing the positive of the real and imaginary components of said second complex number;

performing an exclusion OR operation on said third packed data item and a mask to generate a fourth packed data item, said fourth packed data item including a first and a second data element respectively representing the positive of real component and the inverse of the imaginary component of said second complex number;

adding one to said second data element of said fourth packed data item to generate a fifth packed data item, said fifth packed data item including a first and a second data element respectively storing the positive of the real component and the negative of the imaginary component of said second complex number;

generating a sixth packed data item having a first and second data element being respectively representing the positive of the real and imaginary components of said second complex number; and

generating said second packed data item using the data elements in said fifth packed data item and said sixth packed data item.

37. The machine-readable medium of claim 29, wherein said step of generating said second packed data item is performed in response to a second instruction.

38. The machine-readable medium of claim 23, said step of generating said resulting complex number further comprising the step of:

writing said resulting complex number as a third packed data item, said third packed data item having a first and second data elements respectively representing the real and imaginary components of said resulting complex number.

39. The machine-readable medium of claim 38, wherein said data elements in said first and second packed data items each contain N bits, and wherein said data elements in said third packed data item each contain 2N bits.

40. The machine-readable medium of claim 38, said sequences of instructions, when executed by said processor, cause said processor to perform the additional step of:

C) generating a fourth packed data item based on said third packed data item, said fourth packed data item having a first and second pair of data elements, each of said first pair of data elements representing the real component of said resulting complex number, and each of said second pair of data elements representing the imaginary component of said resulting complex number.