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?

Reply to
Dave
Loading thread data ...

For sure, but you did it well.

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.

Reply to
Symon

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

Reply to
John_H

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

Reply to
Jim Granville

Dave schrieb:

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

Reply to
backhus

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

Reply to
comp.arch.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

Reply to
glen herrmannsfeldt

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:

Reply to
backhus

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

formatting link

cheers,

Nir

Reply to
Nir Dahan

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

Reply to
John_H

John,

this is true that if you count 2:1 muxes the bitonic sort is (a bit) less expensive) but it's latency compared to the method I suggest is higher. Moreover, if you implement this in an FPGA the solution I proposed might even be cheaper since the FPGA LUTs will be used more efficiently. I will have to check this in more detail but I don't think there is a clear cut optimal solution here.

cheers,

Nir

formatting link

Reply to
Nir Dahan

ElectronDepot website is not affiliated with any of the manufacturers or service providers discussed here. All logos and trade names are the property of their respective owners.