Using a minimal number of muliplexers to create a 55:55 multiplexer from smaller multiplexers

Question

The Problem

I have an array of 110 digital pins and I need to route the pins with one-way channels through a series of multiplexers such that the following conditions will always be true:

• Each pin will have a channel/path to exactly one other pin
• Each pin may be either an input or output from one configuration to the next but will only be an input or output for any one configuration (a unidirectional channel/path).
• Due to the above two stipulations we can assume exactly half of the pins are input and half are output during any one configuration.
• All pins are digital.
• Either all pins are 3.3V logic or all pins are 5V logic, we dont know which it is ahead of time
• No pin will connect back on itself (this should be common sense but worth mentioning)
• The time it takes to reconfigure the network is not important, it can be slow.
• The configuration of the network should be controllable via an atmel, this atmel will not be the chip that connects to the 110 digital pins itself, only to control the multiplexer configuration. As such the number of pins needed to configure the network needs to be reasonable.
• Any solution should be able to fit on a 10cm x 10cm PCB, though it can have multiple layers.
• Propagation delay of a signal through the multiplexer, once the multiplexers have been configured, should be minimized. I do not have a specific minimum delay I can quote but getting this number as low as possible should be a priority.
• I list some parts below that I am currently using in my attempted solution, but there is no need that I need to use those specific parts. I can consider solutions using entirely different parts if they achieve the intended goal better. In fact if I cant get this approach to work I am even considering moving to an FPGA, however the main reason I am not is because they are all BGA packages and they would be a nightmare to work with in a prototype.

My Attempted solution

So I identified a few chips that I should be able to create a solution if I can find the right way to connect them all together. They are as follows.

Parts Being Considered

IDT72V70210

This is a chip with a single 32:32 digital (one way) multiplexer on it that is configurable through I2C. It has 1,024 channels so it is capable of routing any of its 32 inputs to any of the 32 outputs. It is expensive at about 25$ per chip so ideally I'd like to make it a priority to minimize the number of these chips I need in my solution.

APG792A

This is a chip with three 1:4 analog (two-way) multiplexers on it and is also configurable through I2C. These are relatively cheap at about a dollar or two so I dont mind having several on the board should they fit.

TCA9548A

This is a chip with one 1:8 I2C switch on it. It allows you to have 8 separate "sub-networks" of I2C devices so you can address the issue of I2C address conflicts by putting conflicting addresses in different I2C subnetworks. These are also relatively cheap so I dont mind if I need three or four of these.

Any Microcontroller

Finally any sort of microcontroller capable of controlling the multiplexers, this will not be connecting to the 110 digital pins only talking to the multiplexer array to configure it.

Current Approach

So my current way of tackling this, which keep in mind isnt really working out, is to have 2x32:32 digital multiplexer chip. It would have 32 inputs and 32 outputs on each chip. While by itself it would be capable of routing any pins in a group of 32 to any other pins in the same group that wont get me very close to handling 110 pins. My solution at first was to use the 1:4 analog multiplexers such that each multiplexer had its single side connected to one of the digital pins. The four output pins of the analog multiplexer would be connected to a pin as such, where A represents one of the 32:32 multiplexer and B represents the other one: an input on chip A, an input on chip B, an output on chip A, an output on chip B. My hope was if I selected the right pin arrangement between the analog and digital multiplexers I could achieve the result I wanted.

The problem is I cant find a configuration with this setup that actually can achieve my goal. The closes configuration I found would work to successfully route in any configuration 64 digital pins, but beyond that the topology has edge cases where it would fail. The problem with my solution that works for 64 pins is that more than half the pins on the 2x32:32 multiplexers would go completely unused for any configuration. So while I could scale this solution up to work by using 4x32:32 multiplexers this would significantly increase the cost to make this and would waste half the pins on the 32:32, so ideally I'd like to find a solution that is more affordable. I will need some sort of a new configuration but im struggling to figure out a way to do this well.

For reference here is the approach I would use that would work for up to 64 pins:

^{simulate this circuit – Schematic created using CircuitLab}

Answer 1

Good listing of options, I'll go with the one you ruled out early (sorry about that):

A CPLD or FPGA is the tool of choice here, for several reasons:

• It offers all the muxing capabilities you need
• One component does all will be a lot easier to assemble
• Typically, you can program IO levels. While 5V is a bit high typically, you could voltage-divide that (hint: resistor networks if you're assembling by hand or paying per pick) down to 3.3 V or 3 V; that would put actual 3 V at 1.8 V, and you might simply pick TTL or LVTTL as input levels for your FPGA

Your "can't solder BGA" does weigh heavily. However, there's a) breakout boards and b) you're aiming for 220 + 1 (for the control interface) IO ports. That will not make you happy with a QFP package...

Now, if you insist on both your sanity, and your non-BGA packages: You could use either the larges QFP FPGA you can find for cheap money that still has at least 111 I/Os, and use that to serialize your input, then send it to a second one, and deserialize there (underway, interleave as desired). Since that's clocked logic then, this might or might not fulfill your latency requirements. But honestly, assume clocking beyond 50 MHz, the latency of that might very well be OK for you, still. And the more parallel serial lines you have IO for, the lower you can make the duration of a "pin data packet", limiting the latency of that approach.

(I'll probably really just buy a Lattice ECP5 and design a board and learn to reflow solder BGA – I've never done that myself, and sounds like a fun challenge. At scale, assembly services shouldn't be very expensive. These aren't "high density" parts. I'm mentioning ECP5, because there's a free and open third-party toolchain for that, which you can use generate the bitstreams on the fly, e.g. on a raspberry Pi.)

Answer 2

As an addendum to @MarcusMüller answer:

Unfortunately it seems that you can't implement this in an FPGA that is available in QFN housing. If you could reduce the number of inputs to 108, then it would work out:

The device of (my) choice is a MachXO2-7000HC, which is the largest Lattice FPGA available in QFN. The good thing is this FPGA doesn't need external components - just one single voltage and some capacitors.

The FPGA design consists of two stages: First, there are 54 multiplexers with 110 inputs each - this selects the 54 pins used as inputs. Second, there are 110 multiplexers that use these 54 signals as inputs and select one of them for each of the (possible) outputs.

Unfortunately with 110 inputs this needs 2% more resources than are available in the FPGA. With 108 inputs only, it would fit. Although, reported resource usage is almost too much:

Number of LUT4s:        6696 out of  6864 (98%)

Input/Output direction can be selected with the internal tristate buffers on each pin. If you really need operation at 5V, then you have to add bidirectional level converters on each pin, e.g. TXB0108PWR - they have 8 channels and don't need any configuration.

The total design needs many configuration bits for the multiplexers (i.e. 54 * 7 + 108 * 6 = 1026) which can be organized as a shift register that can be filled from an external microcontroller.