2
\$\begingroup\$

I want to design a 4x4 switch with 2x2 switches.

The 2x2 Switch

The 2x2 switches have a one-to-one relationship between inputs and outputs. As such, the select signal for the 2x2 switch is only a single bit because there are only two options: (1) The 2x2 switch is in "bar" broadcast. The inputs go horizontally to the outputs (In0 -> Out0 and In1-> Out1). (2) The 2x2 switch is in "cross" broadcast mode. The inputs cross each other as they go to the outputs (In0 -> Out1 and In1 -> Out0).

The switch is unicast. No input can drive more than one output. Also, no output can be driven by more than one input.

The 4x4 Switch

I hope my reasoning is right. I think the 4x4 switch would have 4!=24 combinations given the unicast limitations. That is, if In0 can go to any 4 outputs, then In1 has three choices left. In1 can go to any 3 leaving 2 choices for In2 and then leaving 1 choice for In3. So: 4*3*2*1 = 24 combinations.

Since my select signals are bits I would need 5 of them to cover all the combinations. 2^5 is 32 which is enough to cover 24 combinations.

This leads me to believe that there should be 5 2x2 switches inside the 4x4 switch, but I can't see a way to design it without running into a conflict between inputs going to outputs. Any help please?

Here is the VHDL for the 2x2 switch if it helps:

library IEEE;
use IEEE.STD_LOGIC_1164.ALL;

entity SW2x2 is
port (
    In0: in std_logic_vector(3 downto 0);
    In1: in std_logic_vector(3 downto 0);
    Out0: out std_logic_vector(3 downto 0);
    Out1: out std_logic_vector(3 downto 0);
    Sel: in std_logic);
end SW2x2;

architecture Behavioral of SW2x2 is

begin
    Out0 <= In0 when Sel='0' else
            In1 when Sel='1' else
            "0000";
    Out1 <= In1 when Sel='0' else
            In0 when Sel='1' else
            "0000";

end Behavioral;

FYI: The question is related to the design, not the VHDL code. VHDL is just given as reference.

\$\endgroup\$
4
  • \$\begingroup\$ A simple way is to only use 1 output of each of your 2x2 switches (so they are just a 2-to-1 mux). This would require 12 of the 2x2 switches, though. \$\endgroup\$
    – Justin
    Commented Feb 22, 2013 at 15:12
  • \$\begingroup\$ Here are some search terms that might help: "shuffle-exchange network", of which "Benes" and "Omega" are examples. Does your switch need to be self-routing, or can the settings be computed with global knowledge? How important is latency -- the number of switches in each input-to-output path? \$\endgroup\$
    – Dave Tweed
    Commented Feb 22, 2013 at 15:25
  • \$\begingroup\$ I'm not worried about latency at the moment, just functionality. What do you mean by "self-routing?" (Sorry for the stupid question) \$\endgroup\$
    – The Unknown Dev
    Commented Feb 22, 2013 at 15:33
  • \$\begingroup\$ In a self-routing network, the individual switches compute their own settings based only on the information available at their two inputs. Global routing uses knowledge of where every input needs to go in order to compute all of the switch settings in parallel. This is in the context of message-passing, in which each message carries destination address information. It's been a long time (30 years) since I last worked with this stuff, but IIRC, a 6-switch network (3 layers of two switches each) is non-blocking (but not self-routing). \$\endgroup\$
    – Dave Tweed
    Commented Feb 22, 2013 at 16:44

2 Answers 2

Reset to default
2
\$\begingroup\$

enter image description here

First we optionally swap adjacent pairs, then staggered pairs, then adjacent pairs again.

For example, the rotation ABCD -> DABC is achieved through the three stages like this:

  1. Swap both pairs: BADC
  2. Swap B and D: DABC
  3. No-op.

are switches, they let us swap the inner pair and outer pair.

\$\endgroup\$
5
  • 1
    \$\begingroup\$ Not only can the six-switch setup hit all permutations, but it would be able to do so even if one of the switches on the left or right were hard-wired to always pass straight through. \$\endgroup\$
    – supercat
    Commented Feb 23, 2013 at 0:18
  • \$\begingroup\$ That's what my intuition told me but I got stuck on that one case. It's suddenly obvious: ABCD -> BADC -> DABC. I will change the answer, thanks. \$\endgroup\$
    – Kaz
    Commented Feb 23, 2013 at 0:55
  • \$\begingroup\$ @supercat Are you sure bout the second claim: removing one of the switches? Suppose we remove one on the left, so that we cannot swap one of the two pairs. How can we achieve ABCD -> DABC? \$\endgroup\$
    – Kaz
    Commented Feb 23, 2013 at 1:09
  • \$\begingroup\$ I think this solution is correct. +1 We have got 6 switches, so there are 2^6=64 combinations. We expect to have only 24 combinations, so some combinations lead to the same output. But I can't see how this can be more optimized. (But you can prove me wrong. It's a nice mathematical problem. :-)) \$\endgroup\$
    – Al Kepp
    Commented Mar 25, 2013 at 2:27
  • \$\begingroup\$ @AlKepp Hmm. We know from sorting that a budget of \$n\log n\$ operations is enough to go to any permutation giving us a bound on how many exchange operations (thus switches) we need. But numerical experiments are indicating to me that \$2^{n\log n}\$ grows faster than \$n!\$. The ratio \$r(n)\$ between them seems to be exponential, judging from various \$r(2n)\$ values having about twice the number of decimal digits as \$r(n)\$. Permutations are formed by complete random access of choice w.r.t which element is appened to a sequence, but in-place exchanges must re-use positions. \$\endgroup\$
    – Kaz
    Commented Mar 25, 2013 at 3:48
0
\$\begingroup\$

One solution that cannot have collisions but can have broadcast (one input to many) and 8 control signals is: Showing only 2 of 4 blocks. enter image description here

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.