I'm using a butterfly network to generate a random combination of a bitstring of length [MATH]n[/MATH] and weight [MATH]w[/MATH]. 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 [MATH]x = \frac{n}{2}\log{n}[/MATH] distinct swaps (leaving away all the possible optimizations), corresponding to just as many coin tosses.
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 [MATH]2^x[/MATH]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 [MATH]\binom{n}{w}[/MATH] bitstring of length [MATH]n[/MATH] and weight [MATH]w[/MATH] 2. To generate the previous output, we use [MATH]2^x[/MATH] distinct configurations of swaps.
To rephrase the previous problems, we have [MATH]2^x[/MATH] possible configurations, but just [MATH]\binom{n}{w}[/MATH] 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.
But in general, how many configurations maps to the same bitstring? Worst case? Best case?
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 [MATH]x = \frac{n}{2}\log{n}[/MATH] distinct swaps (leaving away all the possible optimizations), corresponding to just as many coin tosses.
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 [MATH]2^x[/MATH]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 [MATH]\binom{n}{w}[/MATH] bitstring of length [MATH]n[/MATH] and weight [MATH]w[/MATH] 2. To generate the previous output, we use [MATH]2^x[/MATH] distinct configurations of swaps.
To rephrase the previous problems, we have [MATH]2^x[/MATH] possible configurations, but just [MATH]\binom{n}{w}[/MATH] 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.
But in general, how many configurations maps to the same bitstring? Worst case? Best case?