I'd like to have a comparison of the compelxity needed to evaluating the
following two expressions:
E1 = sum_(i=0)^(N-1) x_iy_i
E2 = sum_(i=0)^(N-1) sign(x_i)sign(y_i)
where
sign(x) = 1 for x>0
0 for x=0
-1 for x<0.
Any one has ideas of how much saving I can get by replacing E1 with E2 on
a fixed point DSP? And what I should expect to pay for the saving?
many thanks
Jiaquan
This message was sent using the Comp.DSP web interface on
www.DSPRelated.com
is sign correlation faster than normal correlation on DSPs?
Started by ●October 11, 2005
Reply by ●October 11, 20052005-10-11
Huo Jiaquan wrote:> I'd like to have a comparison of the compelxity needed to evaluating the > following two expressions: > E1 = sum_(i=0)^(N-1) x_iy_i > E2 = sum_(i=0)^(N-1) sign(x_i)sign(y_i) > where > sign(x) = 1 for x>0 > 0 for x=0 > -1 for x<0. > > Any one has ideas of how much saving I can get by replacing E1 with E2 on > a fixed point DSP? And what I should expect to pay for the saving? > > many thanks > Jiaquan > > This message was sent using the Comp.DSP web interface on > www.DSPRelated.comI don't think you will save anything on a fixed-point DSP, but you would save something on an FPGA. John
Reply by ●October 11, 20052005-10-11
john wrote:> Huo Jiaquan wrote: > >>I'd like to have a comparison of the compelxity needed to evaluating the >>following two expressions: >>E1 = sum_(i=0)^(N-1) x_iy_i >>E2 = sum_(i=0)^(N-1) sign(x_i)sign(y_i) >>where >>sign(x) = 1 for x>0 >> 0 for x=0 >> -1 for x<0. >> >>Any one has ideas of how much saving I can get by replacing E1 with E2 on >>a fixed point DSP? And what I should expect to pay for the saving? >> >>many thanks >>Jiaquan >> >>This message was sent using the Comp.DSP web interface on >>www.DSPRelated.com > > > I don't think you will save anything on a fixed-point DSP, but you > would save something on an FPGA. > > John >I think the savings would be negative on a fixed-point DSP. But I agree on the FPGA. -- Jim Thomas Principal Applications Engineer Bittware, Inc jthomas@bittware.com http://www.bittware.com (603) 226-0404 x536 I thought I was wrong once, but I was mistaken.
Reply by ●October 13, 20052005-10-13
"Jim Thomas" <jthomas@bittware.com> wrote in message news:11kn8q09g0ifff6@corp.supernews.com...> john wrote: >> Huo Jiaquan wrote: >> >>>I'd like to have a comparison of the compelxity needed to evaluating the >>>following two expressions: >>>E1 = sum_(i=0)^(N-1) x_iy_i >>>E2 = sum_(i=0)^(N-1) sign(x_i)sign(y_i) >>>where >>>sign(x) = 1 for x>0 >>> 0 for x=0 >>> -1 for x<0. >>> >>>Any one has ideas of how much saving I can get by replacing E1 with E2 on >>>a fixed point DSP? And what I should expect to pay for the saving? >>> >>>many thanks >>>Jiaquan >>> >>>This message was sent using the Comp.DSP web interface on >>>www.DSPRelated.com >> >> >> I don't think you will save anything on a fixed-point DSP, but you >> would save something on an FPGA. >> >> John >> > > I think the savings would be negative on a fixed-point DSP. But I agree > on the FPGA. > > -- > Jim Thomas Principal Applications Engineer Bittware, Inc > jthomas@bittware.com http://www.bittware.com (603) 226-0404 x536 > I thought I was wrong once, but I was mistaken.Hmmm... I think the answer is more like: "it depends". - it depends on how you get sgn(.) a 1-bit ADC would do that. - it depends on how you compute sgn(x)*sgn(y) because, since sgn(x) and sgn(y) are 1-bit numbers that can be packed into a word, sgn(x)*sgn(y) is XOR[sgn(x), sgn(y)]. So, if XOR on a word is easier to compute than sgn(x)*sgn(y) that might help. Then, the sum of bits in the word might be done in a shift/1-bit add process??? Does this make any sense? Fred
Reply by ●October 13, 20052005-10-13
Fred Marshall wrote: ...> Then, the sum of bits in the word might be done in a shift/1-bit add > process??? > > Does this make any sense?Can you read Forth? \ COUNTING BITS, faster than with the carry flag. \ We can interpret a number as 32 1-bit cells, each containing \ the count of bits in that cell. : count-bits ( n -- bitcount ) \ or DUP U2/ 55555555 AND - \ At this point there are 16 2-bit cells, each containing \ the count of bits originally in those cells. 33333333 2DUP AND >R SWAP 2 RSHIFT AND R> + \ Now there are 8 4-bit cells, each containing the count of bits \ originally in those cells. Each cell's high bit is always zero. 0F0F0F0F 2DUP AND >R SWAP 4 RSHIFT AND R> + ; \ Each byte now contains the count of bits originally in that byte. \ This is all that is needed for working with 8-bit ports. When the \ high byte is zero, 2/ can replace U2/ throughout. But U2/ allows 00FF00FF 2DUP AND >R SWAP 8 RSHIFT AND R> + ; \ Each word now contains the count of bits originally in that word. 0000FFFF 2DUP AND >R SWAP 8 RSHIFT AND R> + ; \ A few cycles can be saved here if needed. The result is the count of \ bits. Jerry -- Engineering is the art of making what you want from things you can get. �����������������������������������������������������������������������
Reply by ●October 13, 20052005-10-13
"Jerry Avins" <jya@ieee.org> wrote in message news:nYOdnQRtgu9odtDenZ2dnUVZ_smdnZ2d@rcn.net...> Fred Marshall wrote: > > ... > >> Then, the sum of bits in the word might be done in a shift/1-bit add >> process??? >> >> Does this make any sense? > > Can you read Forth?Not in the least... but thanks for adding to the idea. I still don't know if they make sense in the real application. Fred
Reply by ●October 13, 20052005-10-13
Fred Marshall wrote:> since sgn(x) and sgn(y) are 1-bit numbers ...Sorry for clipping out so much context, but according to the OP:>>>>sign(x) = 1 for x>0 >>>> 0 for x=0 >>>> -1 for x<0.By that definition, sign(x) cannot be a one-bit number. -- Jim Thomas Principal Applications Engineer Bittware, Inc jthomas@bittware.com http://www.bittware.com (603) 226-0404 x536 I'm a man. But I can change. If I have to. I guess. - Red Green
Reply by ●October 13, 20052005-10-13
Fred Marshall wrote:> "Jerry Avins" <jya@ieee.org> wrote in message > news:nYOdnQRtgu9odtDenZ2dnUVZ_smdnZ2d@rcn.net... > >>Fred Marshall wrote: >> >> ... >> >> >>>Then, the sum of bits in the word might be done in a shift/1-bit add >>>process??? >>> >>>Does this make any sense? >> >>Can you read Forth? > > > Not in the least... but thanks for adding to the idea. I still don't know > if they make sense in the real application.If it should come to matter, I can write it out in C. One iteration is copying, masking, and adding. It takes log_2(n) iteration for n bits. The first and last iteration can be done a bit more simply. Jerry -- Engineering is the art of making what you want from things you can get. �����������������������������������������������������������������������
Reply by ●October 13, 20052005-10-13
Jim Thomas wrote:> Fred Marshall wrote: > >> since sgn(x) and sgn(y) are 1-bit numbers ... > > > Sorry for clipping out so much context, but according to the OP: > > >>>>> sign(x) = 1 for x>0 >>>>> 0 for x=0 >>>>> -1 for x<0. > > > By that definition, sign(x) cannot be a one-bit number.That function is usually called "signum" and used in equations as sgn(). Jerry -- Engineering is the art of making what you want from things you can get. �����������������������������������������������������������������������
Reply by ●October 13, 20052005-10-13
Jim Thomas wrote:> Fred Marshall wrote: > >> since sgn(x) and sgn(y) are 1-bit numbers ... > > > Sorry for clipping out so much context, but according to the OP: > > >>>>> sign(x) = 1 for x>0 >>>>> 0 for x=0 >>>>> -1 for x<0. > > > By that definition, sign(x) cannot be a one-bit number. >A little hysteresis in the clipper solves that problem.
