Re: Orientation of rotationally invariant bit vectors
- From: acd <acd4usenet@xxxxxxxx>
- Date: Tue, 16 Oct 2007 06:18:06 -0700
On 16 Okt., 04:49, Gene <gene.ress...@xxxxxxxxx> wrote:
However, this is quite expensive as a cicuit and I am wondering,You said "circuit," so you are designing hardware? I guess this is
whether there are
cheaper ways to implement a function which gives the "orientation".
obvious: For n=20, both functions fit in a 256KB ROM.
Yes I did.
The circuit for the proposed method (minimum of all rotated copies for
both classes)
grows quadradically with the number of inputs, because I need a linear
number of 2-input minimum circuits
of input size n.
Your proposal to use a lookup table will grow exponentially in size.
Besides, the first function, whether an input is invariant under
reflection turns out to be quite cheap.
Synthesis to Altera Cyclone II devices required 19 logic cells for
input size 22.
It is not clear whether there exists a circuit class which grows with
O(n log^k n) but it could very well be.
When I wrote "circuit of low cost" I meant it in a complexity-related
way, in number of 2-input gates not
in Dollars.
If the function is used in a chip, this will be more or less
equivalent. An onchip memory of 256K requires a decent amount of chip
area and is not cheap.
Andreas
.
- Follow-Ups:
- References:
- Prev by Date: Re: Orientation of rotationally invariant bit vectors
- Next by Date: Re: Orientation of rotationally invariant bit vectors
- Previous by thread: Re: Orientation of rotationally invariant bit vectors
- Next by thread: Re: Orientation of rotationally invariant bit vectors
- Index(es):
Relevant Pages
|
