Binary symmetric sources and information theory

Question

How can we generate 3 or more binary Sources using BSC channel. As we know, BSC can be easily used to generate 2 binary sources with some cross-over-probability(say p). Eg, length of codeword(say n) n = 1000; p = 0.2, then input and output binary codeword will be having Hamming distance of approx 200. In this way we generate 2 Binary sources with 200 Hamming distance from each other.

My question is: How can we generate multiple Binary with same cross-over-probability or multiple binary sources with approx similar Hamming distance from each other. E.g: X, Y , Z, W. and they should have similar Hamming distance from each other(all combinations(X-Y)(X-Z) and so on).

And, there should be some way to calculate the joint entropy for them. I am trying to make some scheme to do that, if u have some ideas .. just discuss it. please let me know for any questions.. I will surely clear them

Thanks

Answer 1

You want to generate $n$-bit random variables $X_1,\dots,X_m$ such that the Hamming distance between $X_i,X_j$ is about $pn$. Let me start by showing you how to do this for the special case where $n=1$; then I'll generalize.

Set $q = (1 - \sqrt{1-2p})/2$. Pick a set $S \subseteq \{0,1\}^m$ of $m$-bit values, such that every element $s \in S$ has Hamming weight $qk$. Now pick a random $s$ from $S$, randomly permute the bit positions of $s$, and assign this to $X_1,\dots,X_m$ (i.e., $X_i$ is the $i$th bit of $s$). I claim this will have your desired property. Why? Well,

$$\Pr[X_i \ne X_j] = \Pr[X_i=0,X_j=1] + \Pr[X_i=1,X_j=0] = 2q(1-q) = p,$$

so the expected value of the Hamming distance between $X_i,X_j$ will be about $p$, as desired. The joint entropy is easy to calculate: it is simply $\log_2 |S|$.

What if we want $n>1$? Then we can just sample the first bit of $X_1,\dots,X_m$ as above; then sample the second bit of $X_1,\dots,X_m$ in the same way (iid; i.e., pick another $s$ from $S$, and randomly permute its bit-positions); and so on. This gives us a source where the expected value of the Hamming distance between any two $X_i,X_j$ is about $pn$, and where the joint entropy is $n \log_2 |S|$.