FPGA Central

I'd like to have a comparison of the compelxity needed to evaluating th
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 o
a fixed point DSP? And what I should expect to pay for the saving?

many thanks
Jiaqua

This message was sent using the Comp.DSP web interface o
www.DSPRelated.com

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

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
[email protected] http://www.bittware.com (603) 226-0404 x536
I thought I was wrong once, but I was mistaken.

"Jim Thomas" <[email protected]> wrote in message
news:[email protected]..
> 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
> [email protected] 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

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.
¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯ ¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯

"Jerry Avins" <[email protected]> wrote in message
news:[email protected]..
> 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

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
[email protected] http://www.bittware.com (603) 226-0404 x536
I'm a man. But I can change. If I have to. I guess. - Red Green

Fred Marshall wrote:
> "Jerry Avins" <[email protected]> wrote in message
> news:[email protected]..
>
>>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.
¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯ ¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯

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.
¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯ ¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯

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.

Stan Pawlukiewicz wrote:
> 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.

How? there are three states to represent. As Jim Thomas pointed out
(most of us were nodding our heads instead of thinking) sgn(x) and
sgn(y) are 2-bit numbers (with room to spare).

Are you suggesting that the OP should change his procedure? I can't
guess if that would be good or not.

Jerry
--
Engineering is the art of making what you want from things you can get.
¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯ ¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯

Jerry Avins wrote:
> Stan Pawlukiewicz wrote:
>
>> 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.
>
>
> How? there are three states to represent. As Jim Thomas pointed out
> (most of us were nodding our heads instead of thinking) sgn(x) and
> sgn(y) are 2-bit numbers (with room to spare).

In a real clipper, there is always a little noise, even with a dead
short across the input. Hysteresis calms the clipper down some. The
zero state is something one sees in Matlab, not in the real world.

If you want to be mathematically anal about it, the probability that a
signal value x=x0, is zero for a Gaussian distribution.
>
> Are you suggesting that the OP should change his procedure? I can't
> guess if that would be good or not.

Don't need to guess when you have some actual experince with
clipper/correlators.
>
> Jerry

Stan Pawlukiewicz wrote:
> Jerry Avins wrote:

...

>>> A little hysteresis in the clipper solves that problem.
>>
>> How? there are three states to represent. As Jim Thomas pointed out
>> (most of us were nodding our heads instead of thinking) sgn(x) and
>> sgn(y) are 2-bit numbers (with room to spare).
>
>
> In a real clipper, there is always a little noise, even with a dead
> short across the input. Hysteresis calms the clipper down some. The
> zero state is something one sees in Matlab, not in the real world.
>
> If you want to be mathematically anal about it, the probability that a
> signal value x=x0, is zero for a Gaussian distribution.

Well, the same basic technique that provides hysteresis can provide a
dead band between +/- delta. (Like a test for zero in floating point.)

>> Are you suggesting that the OP should change his procedure? I can't
>> guess if that would be good or not.
>
>
> Don't need to guess when you have some actual experince with
> clipper/correlators.

I don't, much. Thanks for the education.

Jerry
--
Engineering is the art of making what you want from things you can get.
¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯ ¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯

Jerry Avins wrote:
> Stan Pawlukiewicz wrote:
>
(snip)
>
> I don't, much. Thanks for the education.

This stuff is olde, you can find some of it in the MIT Radiation Lab series.


>
> Jerry

Stan Pawlukiewicz wrote:
> Jerry Avins wrote:
>
>> Stan Pawlukiewicz wrote:
>>
> (snip)
>
>>
>> I don't, much. Thanks for the education.
>
>
> This stuff is olde, you can find some of it in the MIT Radiation Lab
> series.

I lent my "Principles of Radar" to my son when he was in college, and I
haven't seen it since. I thought choke joints and T-R tubes were very
clever when I first read about them.

Jerry
--
Engineering is the art of making what you want from things you can get.
¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯ ¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯

Jerry Avins wrote:
> Stan Pawlukiewicz wrote:
>
>> Jerry Avins wrote:
>>
>>> Stan Pawlukiewicz wrote:
>>>
>> (snip)
>>
>>>
>>> I don't, much. Thanks for the education.
>>
>>
>>
>> This stuff is olde, you can find some of it in the MIT Radiation Lab
>> series.
>
>
> I lent my "Principles of Radar" to my son when he was in college, and I
> haven't seen it since. I thought choke joints and T-R tubes were very
> clever when I first read about them.

Tell him to give it back. A Father's job, to teach a son character,
never ends.

>
> Jerry

"Jim Thomas" <[email protected]> wrote in message
news:[email protected]..
> 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,

You're correct. I automatically overlooked the zero part because of
practical experience. Others have addressed it in terms of hysteresis and
noise. So, I stand corrected re: the definition of sgn() and stand on the
answer as a good one.

So, if sgn() isn't what we want (even though the OP did), then what how, in
math, do we *represent* the output of a clipper (suitably scaled and biased
or coded to be a single bit 1,0?) sbit()? clip()? I probably should know
but don't seem to have an answer on the tip of my tongue.

Fred