how to implement this...

Hi

lets assume I have two signals, each carrying 8 bits of information.
One signal is a so called configuration signal and has exactly 4 bits
that are HIGH and 4 bits that are LOW. Now depending on on the values
of the configuration signal I wanna reorder the bits in the other signal
in the following way: If a bit is set in the configuration signal, then
the corresponding bit in the source register will be part of the most 
significant 4 bits of the result signal. If a bit in the configuration 
signal is not set then the corresponding bit in the source register will
be part of the least significant 4 bits. Difficult to describe, so here 
an example

Source: A B C D E F G H
Configuration: 1 0 1 0 1 0 1 0

Result = ACEG BDFH

So I could have two 8 to 4 - muxes that generate me the 4 MSB bits and 4 
LSB bits. Is there maybe a better approach to do implement this on an FPGA?

"Dave" <Dave@yahoo.com> wrote in message news:foqmok$c7t$1@aioe.org...
> Hi
>
> Difficult to describe,
>
For sure, but you did it well.
>
> So I could have two 8 to 4 - muxes that generate me the 4 MSB bits and 4 
> LSB bits. Is there maybe a better approach to do implement this on an 
> FPGA?

Dunno, but you're so good at describing, I'll guess you thought about this 
before posting. So, I'll bet on your solution. Is there a trick?

Cheers, Syms. 

Dave wrote:
> Hi
> 
> lets assume I have two signals, each carrying 8 bits of information.
> One signal is a so called configuration signal and has exactly 4 bits
> that are HIGH and 4 bits that are LOW. Now depending on on the values
> of the configuration signal I wanna reorder the bits in the other signal
> in the following way: If a bit is set in the configuration signal, then
> the corresponding bit in the source register will be part of the most 
> significant 4 bits of the result signal. If a bit in the configuration 
> signal is not set then the corresponding bit in the source register will
> be part of the least significant 4 bits. Difficult to describe, so here 
> an example
> 
> Source: A B C D E F G H
> Configuration: 1 0 1 0 1 0 1 0
> 
> Result = ACEG BDFH
> 
> So I could have two 8 to 4 - muxes that generate me the 4 MSB bits and 4 
> LSB bits. Is there maybe a better approach to do implement this on an FPGA?

I'm thinking this eloquent description is from a textbook problem.

Can you tell me if the order in the result has to be the same as the 
order in the source?

Can you describe the inputs and outputs to an 8-4 mux?  Chances are you 
haven't thought that through.  If you had 8 8-1 muxes instead, how would 
you determine the control for each one?  I'm guessing you can do this 
with a simple cascade of 2-1 muxes.  Think about how you might use a 
simple 2-1 mux and some slight additional control generation to produce 
several stages of intermediate results before settling on a final result.

The joy and the challenge of electronics includes wrapping your mind 
around the problem and figuring out how you can dice the problem up to 
get the desired result.  Different engineers will produce different 
"right" results.

Show me how you can use 2 8-4 muxes (specifically devices that can be 
found in Verilog or VHDL libraries) and I'll send you $20 toward next 
semester's books.

- John_H

Dave wrote:
> Hi
> 
> lets assume I have two signals, each carrying 8 bits of information.
> One signal is a so called configuration signal and has exactly 4 bits
> that are HIGH and 4 bits that are LOW. Now depending on on the values
> of the configuration signal I wanna reorder the bits in the other signal
> in the following way: If a bit is set in the configuration signal, then
> the corresponding bit in the source register will be part of the most 
> significant 4 bits of the result signal. If a bit in the configuration 
> signal is not set then the corresponding bit in the source register will
> be part of the least significant 4 bits. Difficult to describe, so here 
> an example
> 
> Source: A B C D E F G H
> Configuration: 1 0 1 0 1 0 1 0
> 
> Result = ACEG BDFH
> 
> So I could have two 8 to 4 - muxes that generate me the 4 MSB bits and 4 
> LSB bits. Is there maybe a better approach to do implement this on an FPGA?

The example does not really match the text...?
If each output can be one of two sources, selected by each config bit,
that is 8 x 2:1 MUX's, and you can have any mapping you like
(including the one in the example)

-jg

Dave schrieb:
> Hi
> 
> lets assume I have two signals, each carrying 8 bits of information.
> One signal is a so called configuration signal and has exactly 4 bits
> that are HIGH and 4 bits that are LOW. Now depending on on the values
> of the configuration signal I wanna reorder the bits in the other signal
> in the following way: If a bit is set in the configuration signal, then
> the corresponding bit in the source register will be part of the most 
> significant 4 bits of the result signal. If a bit in the configuration 
> signal is not set then the corresponding bit in the source register will
> be part of the least significant 4 bits. Difficult to describe, so here 
> an example
> 
> Source: A B C D E F G H
> Configuration: 1 0 1 0 1 0 1 0
> 
> Result = ACEG BDFH
> 
> So I could have two 8 to 4 - muxes that generate me the 4 MSB bits and 4 
> LSB bits. Is there maybe a better approach to do implement this on an FPGA?

Hi Dave,
what if the two signals are just two wires, and the 8 Bits of 
information come in serially? (Let's just assume it for the moment.)

Then you would just need two 4 bit shift regs with parallel outputs and 
an inverter on one of the shift regs Clock Enable.
Depending on the Configuration bit the Source data would eiter be 
shifted into the MSB-SR or the LSB-SR.

And if the signals actually do have 8 bits of parallel data, you can 
still use the above solution, if you can clock this circuit at 8 times 
the datarate (if possible). Of course you need another two 8 bit 
parallel to serial SRs.

Have a nice Synthesis
   Eilert

On 12 Feb., 07:56, backhus <n...@nirgends.xyz> wrote:

> And if the signals actually do have 8 bits of parallel data, you can
> still use the above solution, if you can clock this circuit at 8 times
> the datarate (if possible). Of course you need another two 8 bit
> parallel to serial SRs.

You can even use this thinking to model a parallel single clock
solution.
You write a for loop and just omit the registers.

Essentially what you create is a chain, where bit N is either taken
from the
right neighbour or from the input depending selctor bit at that
position.
(i.e. one output skips all 0s, the other all 1s)

Kolja Sulimma

Dave wrote:

> lets assume I have two signals, each carrying 8 bits of information.
> One signal is a so called configuration signal and has exactly 4 bits
> that are HIGH and 4 bits that are LOW. Now depending on on the values
> of the configuration signal I wanna reorder the bits in the other signal
> in the following way: If a bit is set in the configuration signal, then
> the corresponding bit in the source register will be part of the most 
> significant 4 bits of the result signal. If a bit in the configuration 
> signal is not set then the corresponding bit in the source register will
> be part of the least significant 4 bits. Difficult to describe, so here 
> an example

> Source: A B C D E F G H
> Configuration: 1 0 1 0 1 0 1 0

> Result = ACEG BDFH

> So I could have two 8 to 4 - muxes that generate me the 4 MSB bits and 4 
> LSB bits. Is there maybe a better approach to do implement this on an FPGA?

A 64K by 8 lookup table will do it.

You need more than a few muxes, especially if the result bits have to
come out in order.  Consider the positions that D could possibly come
out in, for example, and figure out how to get it to those positions.

It might be best to look at the problem backwards.  Consider each
output bit, which input bits could possibly be routed there, and
which configuration bits will indicate each of those.

You might also look at a priority encoder.

-- glen

Hi Kolja,
like John wrote earlyer in this thread:
The joy and the challenge of electronics includes wrapping your mind 
around the problem and figuring out how you can dice the problem up to 
get the desired result.  Different engineers will produce different 
"right" results.

Yours is a nice idea I would hardly think of, because I'm avoiding loops 
to create combinatorical logic. Mainly because I can not estimate what 
ammount of logic will be created.
But that's just some bad habit of me. :-)

Of course a test synthesis will show the results in an instant and the 
result can be accepted or dumped according to design requirements.

Well done.

Regards
   Eilert


comp.arch.fpga schrieb:
> On 12 Feb., 07:56, backhus <n...@nirgends.xyz> wrote:
> 
>> And if the signals actually do have 8 bits of parallel data, you can
>> still use the above solution, if you can clock this circuit at 8 times
>> the datarate (if possible). Of course you need another two 8 bit
>> parallel to serial SRs.
> 
> You can even use this thinking to model a parallel single clock
> solution.
> You write a for loop and just omit the registers.
> 
> Essentially what you create is a chain, where bit N is either taken
> from the
> right neighbour or from the input depending selctor bit at that
> position.
> (i.e. one output skips all 0s, the other all 1s)
> 
> Kolja Sulimma

Lets assume the configuration vector is 7:0.
The target vector will be also 7:0 (naturally)

The key to solving this is to observe for each configuration bit how
many "1"s are to its left and "0"s to its right.
For example:
 if we start from the left (bit 7) and move along to the right (bit 0)
on the configuration vector. we see that the first 1 we can encounter
can be only in places 7,6,5,4 ,3 - one of these should be muxed to
location 7 (MSB) of the target vector.
The second "1" we encounter can ONLY be in position 6,5,4,3,2 and one
of those should be muxed to target location 6.
continue like this and you will see that it is basically a set of 5:1
muxes (or 4:1 + a 2:1 mux) for each target location.
This is for the 4 high locations 7 to 4 in the target.
for locations 3 to 0 you have to look at the first "0" but approaching
from the RIGHT this time.
you will also get 4 5:1 muxes for the logic.

the control logic is easily generated by decoding the place of the
first "1", then the second "1" etc, etc. (and analogously for the "0"s
of course).

There are many optimizations that can be made along the way but this
approach is easiest to understand (for me) - it is also by far cheaper
than the huge LUT that was suggested before.

This is really a nice problem, I am actually considering posting about
it on my blog at http://asicdigitaldesign.wordpress.com

cheers,

Nir

On Feb 15, 8:40=A0am, Nir Dahan <write2...@googlemail.com> wrote:
> Lets assume the configuration vector is 7:0.
> The target vector will be also 7:0 (naturally)
>
> The key to solving this is to observe for each configuration bit how
> many "1"s are to its left and "0"s to its right.
> For example:
> =A0if we start from the left (bit 7) and move along to the right (bit 0)
> on the configuration vector. we see that the first 1 we can encounter
> can be only in places 7,6,5,4 ,3 - one of these should be muxed to
> location 7 (MSB) of the target vector.
> The second "1" we encounter can ONLY be in position 6,5,4,3,2 and one
> of those should be muxed to target location 6.
> continue like this and you will see that it is basically a set of 5:1
> muxes (or 4:1 + a 2:1 mux) for each target location.
> This is for the 4 high locations 7 to 4 in the target.
> for locations 3 to 0 you have to look at the first "0" but approaching
> from the RIGHT this time.
> you will also get 4 5:1 muxes for the logic.
>
> the control logic is easily generated by decoding the place of the
> first "1", then the second "1" etc, etc. (and analogously for the "0"s
> of course).
>
> There are many optimizations that can be made along the way but this
> approach is easiest to understand (for me) - it is also by far cheaper
> than the huge LUT that was suggested before.
>
> This is really a nice problem, I am actually considering posting about
> it on my blog athttp://asicdigitaldesign.wordpress.com
>
> cheers,
>
> Nir

Your solution is one of many.  While the "key" you mention was the key
to your understanding, the cheapest method to implement this may be
with 2:1 multiplexers.  Take a look at the bitonic sort (please search
google) and see how the method might be extended to a simple member
flag (1-left nibble, 0-right nibble) rather than full indexing.  A few
stages of 2:1 muxes (paired 2:1 muxes, actually, to swap two values or
pass them unswapped) and you have the result without having to figure
out where the middle 1s or 0s are in the 8-bit control vector.

- John_H