Patent ID: 7065074

Claim:
A 2 n ×2 n generalized divide-and-conquer network, n>3, comprising 2 └n/2┘ 2 ┌n/2┐ ×2 ┌n/2┐ input nodes, each of the 2 └n/2┘ input nodes being a 2 ┌n/2┐ ×2 ┌n/2┐ generalized divide-and-conquer network, 2 ┌n/2┐ 2 └n/2┘ ×2 └n/2┘ output nodes, each of the 2 ┌n/2┐ output nodes being a 2 └n/2┘ ×2 └n/2┘ generalized divide-and-conquer network, and an interstage exchange connecting the input nodes to the output nodes, wherein the interstage exchange is a bit-permuting exchange induced by a permutation σ on integers from 1 to n such that σ maps the numbers └n/2┘+1, └n/2┘+2, . . . , n, into the set {1, 2, . . , ┌n/2} excluding the bit-permuting exchange equal to the └n/2┘ th power of SHUF (n) , and wherein each 2 k ×2 k generalized divide-and-conquer network (k<n), being representative of each of the input nodes and each of the output nodes, is implemented by forming the bit-permuting 2-stage tensor product, excluding the plain 2-stage tensor product, between a 2 ┌k/2┐ ×2 ┌k/2┐ generalized divide-and-conquer network and a 2 └k/2┘ ×2 └k/2┘ generalized divide-and-conquer network, recursively until k=1, such that a 2×2 generalized divide-and-conquer network is a single cell.