Apparatus and method for rectangular-to-polar conversion

• US 6,874,006 B1
• Filed: 10/30/2000
• Issued: 03/29/2005
• Est. Priority Date: 10/29/1999
• Status: Expired due to Term

• Current Assignee: Alan N. Willson, Jr.
• Original Assignee: Pentomics, Inc.
• Inventors: Fu, Dengwei, Willson, Alan N. Jr.
• Primary Examiner(s): Mai, Tan V
• Application Number:
  US09/698,249
• Time in Patent Office: 1,611 Days
• Field of Search: 708/442
• US Class Current: 708/442
• CPC Class Codes: H03H 17/0027 by means of a non-recursive filter
• CPC Class Codes: H03H 17/028 Polynomial filters
• CPC Class Codes: H04L 27/22 Demodulator circuits; Receiver circuits

Abstract

A rectangular-to-polar-converter receives a complex input signal (having X₀ and Y₀ components) and determines an angle φ that represents the position of the complex signal in the complex plane. The rectangular-to polar-converter determines a coarse angle φ₁ and a fine angle φ₂, where φ=φ₁+φ₂. The coarse angle φ₁ is obtained using a small arctangent table and a reciprocal table. These tables provide just enough precision such that the remaining fine angle φ₂ is small enough to approximately equal its tangent value. Therefore the fine angle φ₂ can be obtained without a look-up table, and the fine angle computations are consolidated into a few small multipliers, given a precision requirement. Applications of the rectangular-to-polar converter include symbol and carrier synchronization, including symbol synchronization for bursty transmissions of packet data systems. Other applications include any application requiring the rectangular-to-polar conversion of a complex input signal.

Claims

1. In a digital device, a method of generating an output signal that represents a polar angle φ

for a complex input signal, the method comprising the steps of;

(1) receiving the complex input signal having a real X₀ component and an imaginary Y₀ component;

(2) determining an angle φ

₁ that is a coarse approximation to the angle φ

, including the steps of

(2a) determining a Z₀ value that approximates a [1/X₀] value, wherein [X₀] is a truncated approximation of said X₀ component,

(2b) digitally multiplying said Z₀ value by Y₀, resulting in a [Y₀ Z₀] value, and

(2c) determining an arctan of said [Y₀Z₀] value, resulting in said angle φ

₁;

(3) determining a fine adjustment angle φ

₂, including the steps of

(3a) digitally computing an intermediate complex number, based on said [Y₀/X₀] value, said intermediate complex number having a real X₁ component and an imaginary Y₁ component,

(3b) determining a Z₁ that approximates a [1/X₁] value, wherein [X₁] is a truncated approximation of said X₁ component,

(3c) digitally multiplying said X₁ component by said [Z₁] value to produce a Z₁X₁ component, and digitally multiplying said Y₁ component by said [Z₁] component to produce a Z₁Y₁ component,

(3d) determining a one'"'"'s complement of said Z₁X₁ component, and

(3e) digitally multiplying said two'"'"'s complement of said Z₁X₁ component by said Z₁Y₁ component, resulting in said fine adjustment angle φ

₂; and

(4) adding said fine adjustment angle φ

₂ to said angle φ

₁ to form said output signal that is data used by said digital device.

2. The method of claim 1, wherein step (2a) comprises the step of retrieving said [Z₀] value from a memory device.

3. The method of claim 1, wherein step (2c) comprises the step of retrieving said angle φ

₁ value from a memory device.

4. The method of claim 1, wherein step (3b) comprises the step of retrieving said [Z₁] value from a memory device.

5. The method of claim 1, wherein step (2a) comprises the step of retrieving said [Z₀] value from a memory device, and wherein step (3b) comprises the step of retrieving said [Z₁] value from said memory device.

6. The method of claim 1, wherein said step (3a) comprises the step of multiplying said X₀ component and said Y₀ component by a tan φ

₁.

7. The method of claim 1, wherein said step (3a) comprises the step of multiplying said X₀ component and said Y₀ component by said [Z₀Y₀] value.

8. An apparatus that generates an output signal that represents a polar angle φ

for a complex input signal having a X₀ component and a Y₀ component, comprising;

a first memory that stores one or more Z₀ values indexed by [X₀], wherein [X₀] is a bit truncated version of said X₀ value, wherein said Z₀ value is approximately 1/[X₀];

a multiplier that multiplies said Z₀ value by the Y₀ component, resulting in a [Z₀Y₀] value;

a second memory that stores one or more φ

₁ angles, wherein said φ

₁ angle is approximately an arctan of [Z₀Y₀];

a digital circuit that multiples said X₀ component and said Y₀ component by said [Z₀Y₀] value, resulting in an intermediate complex number having an X₁ component and a Y₁ component;

a fine angle computation stage that determines an angle φ

₂ based on Y₁/X₁; and

an adder that adds φ

₁+φ

₂ to produce said angle φ

to form the output signal that is data processed by said apparatus.

9. The apparatus of claim 8, wherein said fine angle computation stage includes:

a set of multipliers that multiply said X₁ component and said Y₁ component by a Z₁ value resulting in a X₁Z₁ component and a Y₁Z₁ component, wherein Z₁ is a bit truncated version of 1/[X₁], and wherein [X₁] is a bit truncated version of X₁.

10. The apparatus of claim 9, wherein said Z₁ value is retrieved from said first memory based on said [X₁] value.

11. The apparatus of claim 9, wherein said fine angle computation stage further includes:

a means for implementing a one'"'"'s complement of said X₁Z₁; and

a second multiplier for multiplying said one'"'"'s complement of X₁Z₁ by said Y₁Z₁ component.

12. The apparatus of claim 9, wherein said fine angle computation stage further includes:

a means for implementing a two'"'"'s complement of said X₁Z₁; and

a second multiplier for multiplying said two'"'"'s complement of X₁Z₁ by said Y₁Z₁ component.

13. The apparatus of claim 8, further comprising:

a scaling shifter, coupled to said digital circuit, wherein said scaling shifter scales said X₁ component in accordance with reciprocal values that are stored in said first memory.

14. The apparatus of claim 13, wherein said scaling shifter also scales said Y₁ component similar to said scaling of said X₁ component.

15. The apparatus of claim 8, wherein said digital circuit is a butterfly circuit that is coupled to an output of said multiplier.

16. In a digital device, a method of generating an output signal that represents a polar angle φ

for a complex input signal, the method comprising the steps of;

(1) receiving the complex input signal having a real X₀ component and an imaginary Y₀ component;

(2) retrieving a Z₀ value from a first memory, wherein Z₀ is a bit truncated approximation for 1/X₀;

(3) digitally multiplying said Z₀ value by said Y₀ component, resulting in a [Y₀Z₀] value;

(4) retrieving an angle φ

₁ from a second memory, wherein φ

₁ is based on an arctan of said [Y₀Z₀] value;

(5) digitally rotating said input complex signal in a complex plane by said angle φ

₁ to produce an intermediate complex signal having an X₁ component and a Y₁ component;

(6) digitally computing an angle φ

₂ that is an approximation to an arctan Y₁/X₁; and

(7) adding said angle φ

₂ to said angle φ

₁ to form the output signal that is data used by said digital device.

17. The method of claim 16, wherein said step (6) comprises step of:

(a) retrieving a Z₁ value from said first memory, wherein said Z₁ value is a bit truncated approximation of 1/X₁; and

(b) digitally multiplying said X₁ component by said Z₁ value to produce a Z₁X₁ component, and digitally multiplying said Y₁ component by said Z₁ value to produce a Z₁Y₁ component;

(c) determining a one'"'"'s complement of said Z₁X₁ component; and

(d) multiplying said one'"'"'s complement of said Z₁X₁ component by said Z₁Y₁ component.

18. The method of claim 16, wherein step (5) comprises the step of multiplying said input complex signal by a tan φ

₁.

19. The method of claim 16, wherein step (5) comprises the step of multiplying said input complex signal by said [Y₀Z₀] value.

20. In a digital device for generating an output signal that represents a polar angle φ

for a complex input digital signal, a method of converting Cartesian data of said input digital signal to polar angle data of said output signal, comprising the steps of;

(1) receiving the input digital signal; and

(2) determining at least two subangles, the combination of which subangles represents the polar angle φ

, wherein at least one subangle is determined by using a single trigonometric function of a subangle as an approximation for the subangle.

21. The method of claim 20, wherein step (2) comprises the step of:

(a) determining at least one subangle by using a memory device.

22. The method of claim 20, wherein said at least one subangle is determined by using a trigonometric function the tangent of said subangle as an approximation for said the subangle.

23. In a digital device for generating an output signal that represents a polar angle φ

for a complex input digital signal, a method of converting Cartesian data of said input digital signal to polar angle data of said output signal, comprising the steps of;

(1) receiving the input digital signal; and

(2) determining at least two subangles, the combination of which subangles represents the polar angle φ

, wherein at least one subangle is determined by using a trigonometric function of a subangle as an approximation for the subangle, and said trigonometric function is determined using a previously determined subangle and said Cartesian data of said input digital signal.

24. The method of claim 23, wherein said step of determining said trigonometric function using a previously determined subangle and said Cartesian data of said input digital signal comprises the step of determining said trigonometric function by rotating said Cartesian data of said input digital signal by said previously determined subangle.