All-optical multistage interconnection networks are desirable for overcoming the limitations of optical signal regeneration in switching systems. We present a new implementation of the perfect-shuffle interconnection pattern that is coupled with an all-optical switching element, forming a complete stage of a multistage network. Switching is performed with birefringent calcite crystals and a ferroelectric liquid-crystal device, while interconnection is achieved with a space-semivariant imaging configuration. Cascading the layout allows this system to be used to construct an all-optical multistage interconnection network. An experimental demonstration of the stage is presented.