I'm using a butterfly network to generate a random combination of a bitstring of length $n$ and weight $w$. Let me clarify it with an example. Suppose I want a random bitstring of length 8 and Hamming weight 2. The idea is:

  1. set the first 2 bits to 1, leaving all others to 0
  2. apply the butterfly network; each bit-swap has a 50/50 chance of being enabled

Basically for each swap we toss a fair coin to enable/disable the swap: if it is enabled, the involved bits are swapped, otherwise the bits are passed through. You can see that we have $x = \frac{n}{2}\log{n}$ distinct swaps (leaving away all the possible optimizations), corresponding to just as many coin tosses.

Butterfly network for n=8 and w=2

We can rephrase the previous problem saying that each swap is controlled by a control bit: if it is 1, the corresponding swap is enabled; otherwise, it is disabled. We have therefore $2^x$ distinct configurations of control bits.

Now my question is: how many times the same bitstring is generated in output? There are two main factors to be considered:

  1. The network is able to generate all the $\binom{n}{w}$ bitstring of length $n$ and weight $w$
  2. To generate the previous output, we use $2^x$ distinct configurations of swaps.

To rephrase the previous problems, we have $2^x$ possible configurations, but just $\binom{n}{w}$ distinct output: there must be some collision, i.e. two or more distinct swaps configurations (or equivalently control bits configurations) mapping to the same output bitstring. In the image below, for example, we can see that we are trying to generate all the words of length 4 and Hamming weight 2. We can also notice that there are two different ways to generate the string 1010: if only flip 0 and 2 produces 1 OR if only flip 1 and flip 3 produces 1.

enter image description here

But in general, how many configurations maps to the same bitstring? Worst case? Best case?


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.