(4)bit shuffler/permuter

PHOBoS · Last edited by PHOBoS on Fri Mar 09, 2018 5:09 pm; edited 1 time in total

I already briefly mentioned this in the CMUSE thread, but what I would like is a circuit that has a
4 bit input and with some control signals can create permutations of these 4 bits (one at a time).
If you are unfamiliar with the term permutations it basically just means all the possible ways you
can rearrange the bits. I mainly want to test it with my chromatic melody generator but there are
other uses for it.

4bits has 4!=24 permutations. If the bits are labeled ABCD these are:
ABCD BACD CBAD DBCA
ABDC BADC CBDA DBAC
ACBD BCAD CABD DCBA
ACDB BCDA CADB DCAB
ADCB BDCA CDAB DACB
ADBC BDAC CDBA DABC

I have some ideas on how to achieve this but before I go into that I am curious if someone else can
come up with a nice solution. Using something like a PIC would be very easy btw but I'd like to do it
with logic chips. Although with something like a PIC it would be very simple to implement a CV input
and do all kinds of other things as well.

Instead of permutations it might also be useful to route an input to multiple outputs (like AABC or BDCD).
This would result in 4^4=256 different 'combinations'. A circuit for this would actually be very simple to
make. Just 4 muxes that route 1 of the inputs to 1 of the outputs controlled by 2 bits, so it would need 8
control bits in total.

Steveg · Joined: Apr 23, 2015 Posts: 184 Location: Perth, Australia

It is easier to do this with DPDT relays. You set up a bunch of crossovers to gain all the permutations. Each round swaps (or not) a pair of bits. Have a look at Knuth's work on minimal sorting networks and then imagine each sorting node is a crossover controlled by a signal line. You can make a crossover in CMOS using 4053 chips but two chips yields 3 crossovers so you will need a lot of them.
You can cut down on the number of permutations you need by following you permuter with a barrel shifter type arrangement to generate permutations that are just rotations of other permutations. DABC is ABCD rotated right one step. Two 4052s should create a barrel shifter for 4 bits with 2 control lines.
Actually I think I would use 4052s - each pair of chips gets you 2 permutations and their combinations ... You would probably need 4 pairs with 8 control lines.

Steveg · Joined: Apr 23, 2015 Posts: 184 Location: Perth, Australia

Okay I've done the permutations, you need 3 pairs of 4052s with 6 control lines.
One wired as a barrel shifter.
One that swaps A<->B and C<->D
One that swaps A<->D and B<->C

Instead of the barrel shifter you could use one that swaps A<->C and B<->D you just get a different set of duplicates.

PHOBoS · Posted: Wed Mar 07, 2018 8:00 pm Post subject:

PHOBoS · Posted: Wed Mar 07, 2018 8:13 pm Post subject:

hah, I am currently watching some lectures from Stanford University about C++ as one of them was about
permutations, which made me curious about the rest. In the current one about strings there is an example
code which uses the string "Donald Knuth". Laughing

PHOBoS · Posted: Wed Mar 07, 2018 8:20 pm Post subject:

oh something I forgot to mention. A permuter can of course be used as a barrel shifter. I want to look into it
if it is possible to rearrange it in such a way that it can rotate by connecting a counter to 2 of the control
lines. Maybe that is actually the case already.

PHOBoS · Posted: Thu Mar 08, 2018 1:24 pm Post subject:

PHOBoS · Posted: Fri Mar 09, 2018 10:44 am Post subject:

Here's the logic table for Rev1.2

~~note: I think there is an error in there which might also be in the schematics, will fix it when I found it.~~
found it and fixed it. (schematics are ok)

Steveg · Joined: Apr 23, 2015 Posts: 184 Location: Perth, Australia

Looks good. An impressive set of optimisations there.

PHOBoS · Last edited by PHOBoS on Thu Mar 15, 2018 7:36 pm; edited 1 time in total

PHOBoS · Posted: Thu Mar 15, 2018 1:17 pm Post subject:

I took me longer than I expected but I found a solution to add LEDs to the permuter. I don't know if this is the most efficient
way to do it (with logic chips) but I think it should work. Note that it can only be used with either Rev1.1 or Rev1.3 as it
doesn't have an X input for Rev1.2. (I am not sure yet how easy it is to add this)

The idea is to construct the LEDs in 4x4 grid where the rows are the inputs (X0..X3) and the columns are the outputs (Y0..Y3).
Note that the LEDs don't show the actual status of the outputs just how the in/outputs are routed. For the permuter each input
is routed to a different output so there can never be more than 1 LED on in a single row or column. Because of this you could
either use muxes to control rows or columns.

The permuter uses 1 control input (E) to mirror (reverse) the outputs, this can easily be done by using a 1<>8 mux (CD4051)
for each row of LEDs. The LEDs are connected in the order Y0..Y3 to 'outputs' 0..3 and in the reverse order Y3..Y0 to 'outputs'
4..7. This way the A&B inputs are used to turn on 1 of the LEDs in a row and the C input is used to reverse the whole row. So
the C input of all the 4 muxes will be connected to Control input E. This is the part of the schematic that I started with (U8..U11)
but then I got a bit stuck. So I had to shake it loose and it dropped on the floor and I couldn't find it at first and,..
ok enough sillyness.

Somehow I needed to turn the Control inputs A,B,C,D into 4 sets of 2 bits to control the muxes. I could use a 1<>16 mux for
each bit but that would require 8 of them which seemed a bit ridiculous. I typed out some logic tables to see if that woud give
me any ideas. It became a bit clearer after I typed one similar to the one posted above but with inputs and outputs swapped
as this made it easier to see how the ABCD inputs correlate with the Y0..Y3 outputs.

PHOBoS · Posted: Thu Mar 15, 2018 4:38 pm Post subject:

hmm, I think adding 4 muxes in parallel to route the actual signals would work. I wonder if I can also do
something similar for driving LEDs with the permuter Rev1.3 circuit. I have a gut feeling it can be simplified.

permuter LEDs 1_1.gif

Description:

Filesize:

130.8 KB

Viewed:

258 Time(s)

This image has been reduced to fit the page. Click on it to enlarge.

PHOBoS · Posted: Fri Mar 16, 2018 4:16 pm Post subject:

U1, U2, U3 of the Leds for permuter schematic can be replaced with just a single XOR chip. Cool

PHOBoS · Posted: Fri Mar 16, 2018 7:20 pm Post subject:

PHOBoS · Posted: Fri Mar 16, 2018 7:40 pm Post subject:

here's the version with reduced chip count.

4x4 bit matrix converter v1_1.gif

Description:

Filesize:

91.96 KB

Viewed:

282 Time(s)

This image has been reduced to fit the page. Click on it to enlarge.

PHOBoS · Posted: Sat Mar 17, 2018 6:05 pm Post subject:

And then there where 6 chips left.
I don't think I can reduce it any further.

Just to be clear, this is meant to be used in combination with the 4x4 bit matrix
to give it the same functionality as permuter V1.1 & V1.3 but with LEDs.

4x4 bit matrix converter v1_2.gif

Description:

Filesize:

70.62 KB

Viewed:

259 Time(s)

This image has been reduced to fit the page. Click on it to enlarge.