Greetings, I'm looking for a quick way to computing complex phase rotation in fixed-point, basically for a given complex number X and phase theta, I'd like to compute: Y = X exp(j theta). I know that I can use CORDIC to first find Z = exp(j theta), and then do a complex multiply, but I'm hoping for a shortcut given that I am only rotating, and not scaling. If it makes a difference, this is for an FPGA implementation. Thanks in advance, Julius
Computing complex phase rotation in fixed-point
Started by ●June 2, 2009
Reply by ●June 2, 20092009-06-02
"julius" <juliusk@gmail.com> wrote in message news:a50d86f5-ee76-4123-b191-d8ab39be0582@j12g2000vbl.googlegroups.com...> Greetings, > > I'm looking for a quick way to computing complex phase rotation in > fixed-point, > basically for a given complex number X and phase theta, I'd like to > compute: > > Y = X exp(j theta). > > I know that I can use CORDIC to first find Z = exp(j theta), and then > do a complex > multiply, but I'm hoping for a shortcut given that I am only rotating, > and not scaling. > > If it makes a difference, this is for an FPGA implementation. > > Thanks in advance, > JuliusDepending on the precision needed, a LUT can do that quickly. Otherwise CORDIC or a LUT and a plain-vanilla complex multiplier works, too. The tradeoffs are complexity, latency, and resources. If you have multipliers and memory (like in a Xilinx), then LUTs or LUTs and multipliers works well, especially if you can't tolerate the latency of the CORDIC.
Reply by ●June 3, 20092009-06-03
On Jun 2, 6:57�pm, "Eric Jacobsen" <eric.jacob...@ieee.org> wrote:> "julius" <juli...@gmail.com> wrote in message > > news:a50d86f5-ee76-4123-b191-d8ab39be0582@j12g2000vbl.googlegroups.com... > > > > > Greetings, > > > I'm looking for a quick way to computing complex phase rotation in > > fixed-point, > > basically for a given complex number X and phase theta, I'd like to > > compute: > > > �Y = X exp(j theta). > > > I know that I can use CORDIC to first find Z = exp(j theta), and then > > do a complex > > multiply, but I'm hoping for a shortcut given that I am only rotating, > > and not scaling. > > > If it makes a difference, this is for an FPGA implementation. > > > Thanks in advance, > > Julius > > Depending on the precision needed, a LUT can do that quickly. � Otherwise > CORDIC or a LUT and a plain-vanilla complex multiplier works, too. > > The tradeoffs are complexity, latency, and resources. �If you have > multipliers and memory (like in a Xilinx), then LUTs or LUTs and multipliers > works well, especially if you can't tolerate the latency of the CORDIC.A variation of CORDIC will rotate an input IQ vector by an arbitrary phase without requiring use of a complex multiplier. As Eric notes though, sufficient stages of CORDIC to realize the required phase resolution will usually incur more pipeline latency than an equivalent Sin/Cos LUT and complex multiplier when implemented in modern FPGAs. Since CORDIC requires adders & registers in the FPGA fabric, it's often less efficient in resource usage as well. Eric
Reply by ●June 3, 20092009-06-03
On Jun 2, 9:57 pm, "Eric Jacobsen" <eric.jacob...@ieee.org>; wrote:> "julius" <juli...@gmail.com>; wrote in message > > news:a50d86f5-ee76-4123-b191-d8ab39be0582@j12g2000vbl.googlegroups.com... > > > I'm looking for a quick way to computing complex phase rotation in > > fixed-point, > > basically for a given complex number X and phase theta, I'd like to > > compute: > > > > Y = X exp(j theta). > > > > I know that I can use CORDIC to first find Z = exp(j theta), and then > > do a complex > > multiply, but I'm hoping for a shortcut given that I am only rotating, > > and not scaling....> > Depending on the precision needed, a LUT can do that quickly. Otherwise > CORDIC or a LUT and a plain-vanilla complex multiplier works, too. > > The tradeoffs are complexity, latency, and resources. If you have > multipliers and memory (like in a Xilinx), then LUTs or LUTs and multipliers > works well, especially if you can't tolerate the latency of the CORDIC.i think that you'll end up multiplying by exp(j theta) anyway. as an alternative to CORDIC or LUT, you use an optimized polynomical for sin (x) for -pi/2 < x < +pi/2. depending on how many terms in your polynomial approximation, you can get the error down to as small as you need it. for cos(x), maybe you can use cos(pi*x) = 1 - 2*(sin((pi/2)*x))^2 a pretty good approximation to sin((pi/2)*x) is sin((pi/2)*x) ~= 1.5707963268 * x + -0.6459640619 * x^3 + 0.0796915849 * x^5 + -0.0046768800 * x^7 + 0.0001530302 * x^9 for -1 <= x <= 1 r b-j
Reply by ●June 3, 20092009-06-03
On Jun 3, 2:33�pm, robert bristow-johnson <r...@audioimagination.com> wrote:> On Jun 2, 9:57 pm, "Eric Jacobsen" <eric.jacob...@ieee.org>; wrote: > > > > > "julius" <juli...@gmail.com>; wrote in message > > >news:a50d86f5-ee76-4123-b191-d8ab39be0582@j12g2000vbl.googlegroups.com... > > > > I'm looking for a quick way to computing complex phase rotation in > > > fixed-point, > > > basically for a given complex number X and phase theta, I'd like to > > > compute: > > > > � �Y = X exp(j theta). > > > > I know that I can use CORDIC to first find Z = exp(j theta), and then > > > do a complex > > > multiply, but I'm hoping for a shortcut given that I am only rotating, > > > and not scaling. > ... > > > Depending on the precision needed, a LUT can do that quickly. Otherwise > > CORDIC or a LUT and a plain-vanilla complex multiplier works, too. > > > The tradeoffs are complexity, latency, and resources. If you have > > multipliers and memory (like in a Xilinx), then LUTs or LUTs and multipliers > > works well, especially if you can't tolerate the latency of the CORDIC. > > i think that you'll end up multiplying by exp(j theta) anyway. as an > alternative to CORDIC or LUT, you use an optimized polynomical for sin > (x) for -pi/2 < x < +pi/2. depending on how many terms in your > polynomial approximation, you can get the error down to as small as > you need it. for cos(x), maybe you can use > > � � cos(pi*x) = 1 - 2*(sin((pi/2)*x))^2 > > a pretty good approximation to sin((pi/2)*x) is > > � � sin((pi/2)*x) ~= � � � � � � � 1.5707963268 * x > � � � � � � � � � � � � � � + � � � -0.6459640619 * x^3 > � � � � � � � � � � � � � � + � � � �0.0796915849 * x^5 > � � � � � � � � � � � � � � + � � � -0.0046768800 * x^7 > � � � � � � � � � � � � � � + � � � �0.0001530302 * x^9 > > � � for � � -1 �<= �x �<= �1 > > r b-jThat's a nice trick but unfortunately I am really trying to avoid multiplication for now. I guess I'll see the space vs. accuracy tradeoff for LUT and CORDIC. I did have a brain fart about CORDIC being initially invented exactly for coordinate rotation! Ha. Must be getting old .... Julius
Reply by ●June 3, 20092009-06-03
On Jun 3, 9:49�pm, julius <juli...@gmail.com> wrote:> > ... unfortunately I am really trying to avoid > multiplication for now. �I guess I'll see the space vs. accuracy > tradeoff for LUT and CORDIC. �I did have a brain fart about > CORDIC being initially invented exactly for coordinate > rotation!i thought it was precisely for rotation of a *unit* vector. and i don't see how multiplication (or something equivalent to it) is avoided with CORDIC. i dunno.> �Ha. �Must be getting old ....i thought it was you getting outa college a short decade ago. wasn't it? i even seem to remember a phone call from you (outa the blue) when i lived in New Jersey. maybe it was someone else. you dunno (yet) what getting old is. :-) i'm gaining a glimpse of it. s'pose Jerry sees it pretty well. r b-j
Reply by ●June 4, 20092009-06-04
On Jun 3, 7:06�pm, robert bristow-johnson <r...@audioimagination.com> wrote:> On Jun 3, 9:49�pm, julius <juli...@gmail.com> wrote: > > > ... unfortunately I am really trying to avoid > > multiplication for now. �I guess I'll see the space vs. accuracy > > tradeoff for LUT and CORDIC. �I did have a brain fart about > > CORDIC being initially invented exactly for coordinate > > rotation!In its simplest form, CORDIC takes the unit vector (1,0) and rotates it through an arbitrary angle in the range +/- 45deg. You then may get full 360deg range using x/y swapping and inversion to get the (cos,sin) of the rotation angle. However, nothing limits you from using any vector besides (1,0) for the starting point. This allows the rotation of arbitrary (x,y) vectors through an arbitrary angle. By connecting an ordinary accumulator-based NCO to the angle input of this CORDIC system it's possible to make a complex up/down conversion without any explicit multiplications or trig lookups. I've used this structure in the carrier tracking subsystem of several digital demods years ago. Eric
Reply by ●June 4, 20092009-06-04
On Jun 3, 10:06�pm, robert bristow-johnson <r...@audioimagination.com> wrote:> > i thought it was you getting outa college a short decade ago. �wasn't > it? �i even seem to remember a phone call from you (outa the blue) > when i lived in New Jersey. �maybe it was someone else. > > you dunno (yet) what getting old is. :-) �i'm gaining a glimpse of > it. �s'pose Jerry sees it pretty well. > > r b-jI moved from Berkeley to MIT in 2001, and I remembered that you lived in the northeast. So I thought I'd give you a call to try and meet up. Long story short, I got done with my PhD in 2006, then went to Houston for 2 years, and now I'm back in Boston. Weren't you saying in some other post that you go to Boston occasionally (from VT or NH where you live?), if you do please holla the next time you come down. My in-laws are in south NJ and I've been trying to meet with Jerry but it's been hard with all the family hijacking of your time when you visit them .... Sorry, Jerry! Julius
Reply by ●June 4, 20092009-06-04
On Jun 4, 9:54�am, emeb <ebromba...@gmail.com> wrote:> > In its simplest form, CORDIC takes the unit vector (1,0) and rotates > it through an arbitrary angle in the range +/- 45deg. You then may get > full 360deg range using x/y swapping and inversion to get the > (cos,sin) of the rotation angle. However, nothing limits you from > using any vector besides (1,0) for the starting point. This allows the > rotation of arbitrary (x,y) vectors through an arbitrary angle. By > connecting an ordinary accumulator-based NCO to the angle input of > this CORDIC system it's possible to make a complex up/down conversion > without any explicit multiplications or trig lookups. I've used this > structure in the carrier tracking subsystem of several digital demods > years ago. > > EricThanks for the review. My background is not in digital design, so I actually learned CORDIC not from its original conception, but in its application in computing trig functions. One of those moments when I completely miss what something was invented for in the first place! Julius
Reply by ●June 4, 20092009-06-04
On Jun 2, 6:01�pm, julius <juli...@gmail.com> wrote:> Greetings, > > I'm looking for a quick way to computing complex phase rotation in > fixed-point, > basically for a given complex number X and phase theta, I'd like to > compute: > > � Y = X exp(j theta). > > I know that I can use CORDIC to first find Z = exp(j theta), and then > do a complex > multiply, but I'm hoping for a shortcut given that I am only rotating, > and not scaling. > > If it makes a difference, this is for an FPGA implementation. > > Thanks in advance, > JuliusAre you going to repeatedly rotate this vector? If so, amplitude error may accumulate; I have seen the result go unstable in floating- point. It may not remain a unit vector. A phase accumulator with a lookup table can solve this, at the price of a few multiples. You can save memory on the LUT by having one LUT for 360 degrees, and one LUT for much smaller steps between the 0 and the next point in the first table. Use cos(sum of angles) and sin (sum of angles) to get the result. Again at a cost of a few multiplies. Dirk
