1
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ Why don't you start by starting with a simpler special case? What about the case $n=1$, and three sources? Can you find one-bit random variables $X,Y,Z$ such that $\Pr[X \ne Y]$, $\Pr[Y \ne Z]$, and $\Pr[X \ne Z]$ are all about 0.2? $\endgroup$
    – D.W.
    Dec 6, 2017 at 16:05

1 Answer 1

1
$\begingroup$

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|$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.