Multiuser Channel Networks — Examples

Substituting $P_1=P_2=N=1$ and $\rho =1\mathrm{/}2$ into [F1] gives the individual bound $\frac{1}{2}\ln (1+3\mathrm{/}4)=\frac{1}{2}\ln (7\mathrm{/}4)$ and sum bound $\frac{1}{2}\ln (1+1+1+1)=\ln 2$.

For the selected point, the individual constraints hold with equality and the sum constraint is $\ln (7\mathrm{/}4)\le \ln 2$, true because $7\mathrm{/}4\le 2$. By [F3], the no-feedback Gaussian sum bound from the same powers is $\frac{1}{2}\ln (1+2)=\frac{1}{2}\ln 3$. The feedback point has larger sum because $\ln (7\mathrm{/}4)>\frac{1}{2}\ln 3$ is equivalent to $(7\mathrm{/}4{)}^2>3$, i.e. $49>48$.

For independent Bernoulli inputs with parameters $p,q$, given $X_2$ the XOR is a bijective relabeling of $X_1$, and given $(X_1,X_2)$ the output is fixed. Thus [F4]–[F5] give $I(X_1;Y\mid X_2)=H(X_1\mid X_2)=h_b(p)$; interchanging users gives $h_b(q)$. The deterministic output and [F3], [F6] give $I(X_1,X_2;Y)=H(Y)=h_b(p+q-2pq)$.

For any finite time-sharing variable, the sum bound is $I(X_1,X_2;Y\mid Q)=H(Y\mid Q)\le \ln 2$, because each conditional output is binary. With $Q$ constant and $p=q=1\mathrm{/}2$, both individual informations and the sum information equal $\ln 2$. Hence every nonnegative pair with sum at most $\ln 2$ is in the closed region, and no pair with larger sum is.

The diagonal joint law has probability $1\mathrm{/}2$ on $(0,0)$ and $(1,1)$, so it is not a product law: its marginals are uniform but their product puts positive mass on $(0,1)$ and $(1,0)$. More generally, suppose a finite mixture $P_Q{P}_{X_1\mathrm{\mid }Q}{P}_{X_2\mathrm{\mid }Q}$ equals this diagonal law. For every positive-mass $q$, nonnegativity and zero total off-diagonal mass force $P(X_1=0\mathrm{\mid }q)P(X_2=1\mathrm{\mid }q)=P(X_1=1\mathrm{\mid }q)P(X_2=0\mathrm{\mid }q)=0$. If $X_1$ had positive conditional mass on both bits, these equalities would force $P(X_2=0\mathrm{\mid }q)=P(X_2=1\mathrm{\mid }q)=0$, impossible; hence $X_1$ is deterministic given $q$, and the two equalities then force $X_2$ to be the same deterministic bit. Thus any such public time-sharing representation uses deterministic diagonal product components. With $Q$ selecting $(0,0)$ or $(1,1)$, [F5] gives $I(X_1;Y\mid X_2,Q)=I(X_2;Y\mid X_1,Q)=0$; the mixture adds no private-message rate.

The only positive-probability source pairs are $(0,0),(0,1),(1,1)$. Under $X_j=S_j$ their outputs are $0,1,2$, which are distinct; applying the inverse table at every coordinate reconstructs both source blocks with error exactly zero under [F1]–[F2].

The three equiprobable source atoms give $H(S_1,S_2)=-(3)(1\mathrm{/}3)\ln (1\mathrm{/}3)=\ln 3$. Since $3^2=9>8=2^3$ and $\ln$ is increasing, $\ln 3>\frac{3}{2}\ln 2$.

Let independent product inputs have $X_1\sim \mathrm{Bern}(p)$ and $X_2\sim \mathrm{Bern}(q)$. Since $Y=X_1+X_2$ is deterministic, expansion of [F3] gives $I(X_1,X_2;Y)=H(Y)$. Put $A=2p-1$, $B=2q-1$, and $T=AB$. Then $P_Y(0)=\frac{(1-A)(1-B)}{4},P_Y(1)=\frac{1-T}{2},P_Y(2)=\frac{(1+A)(1+B)}{4}\mathrm{.}$ The two endpoint masses sum to $(1+T)\mathrm{/}2$, and their difference has absolute value $\mathrm{\mid }A+B\mathrm{\mid }\mathrm{/}2$.

If $T\le 0$, equal endpoint masses are feasible by taking $B=-A$ and $A^2=-T$. At fixed middle mass $b=P_Y(1)$, write the endpoint masses as $(1-b)t$ and $(1-b)(1-t)$. Their entropy contribution is $(1-b)h_b(t)\le (1-b)\ln 2$, because $h_b^{\mathrm{\prime }}(t)=\ln ((1-t)\mathrm{/}t)$ is positive for $t<1\mathrm{/}2$ and negative for $t>1\mathrm{/}2$, with continuity at the endpoints. Since $b=(1-T)\mathrm{/}2\ge 1\mathrm{/}2$, $H(Y)\le h_b(b)+(1-b)\ln 2.$ This function has derivative $\ln ((1-b)\mathrm{/}b)-\ln 2<0$ for $b\ge 1\mathrm{/}2$, so it is at most its value $\frac{3}{2}\ln 2$ at $b=1\mathrm{/}2$.

If $T\ge 0$, $A$ and $B$ have the same sign and $\mathrm{\mid }A+B\mathrm{\mid }\ge 2\sqrt{T}$. For fixed endpoint total, entropy is maximized when the endpoint imbalance is smallest, attained at $\mathrm{\mid }A\mathrm{\mid }=\mathrm{\mid }B\mathrm{\mid }=\sqrt{T}$; hence it is enough to consider $p=q=r$ or their simultaneous complements. By symmetry take $0\le r\le 1\mathrm{/}2$, where the output law is $((1-r{)}^2,2r(1-r),r^2)$. Its entropy derivative is $2[\ln \frac{1-r}{r}-(1-2r)\ln 2]\ge 0.$ Indeed, with $x=1-2r\in [0,1)$, $g(x)=\ln ((1+x)\mathrm{/}(1-x))-2x$ satisfies $g(0)=0$ and $g^{\mathrm{\prime }}(x)=2x^2\mathrm{/}(1-x^2)\ge 0$, while $2x\ge x\ln 2$. Therefore the entropy is at most its value $\frac{3}{2}\ln 2$ at $r=1\mathrm{/}2$. Continuity covers the endpoints.

Uniform product inputs $p=q=1\mathrm{/}2$ give output probabilities $(1\mathrm{/}4,1\mathrm{/}2,1\mathrm{/}4)$ and entropy $\frac{3}{2}\ln 2$. Steps 1.4 and 1.5 show no independent product input gives greater output entropy; by determinism and step 1.3 this is the maximum product-input sum mutual information. For any finite time-sharing variable, [F4] makes $I(X_1,X_2;Y\mid Q)$ an average of these product-input informations, so the same $\frac{3}{2}\ln 2$ upper bound holds.

Consider separate fixed-length source encoders with message indices $J=(J_1,J_2)$ of sizes $M_1,M_2$, channel output $Y^n$, and reconstruction ${\widehat{S}}^n=g(Y^n)$ with error ${ϵ}_n$. Since the source-block alphabet has size $4^n$, Fano's inequality [F5] gives $H(S_1^n,S_2^n\mid Y^n)\le \ln 2+2n{ϵ}_n\ln 2$. The encoders make $J$ a deterministic function of $(S_1^n,S_2^n)$, and the channel output depends on the source blocks only through $J$, so the finite chain rules [F6] give $I(S_1^n,S_2^n;Y^n)=I(J;Y^n)$. Therefore $n\ln 3=H(S_1^n,S_2^n)\le I(J;Y^n)+H(S_1^n,S_2^n\mid Y^n)\le H(J)+\ln 2+2n{ϵ}_n\ln 2.$ If $\pi$ is the law of $J$, concavity of $\ln$ gives $H(J)={\sum }_{j:{\pi }_j>0}{\pi }_j\ln (1\mathrm{/}{\pi }_j)\le \ln {\sum }_{j:{\pi }_j>0}1\le \ln (M_1{M}_2)$. Thus $n\ln 3\le \ln M_1+\ln M_2+\ln 2+2n{ϵ}_n\ln 2$, so reliable separate descriptions require asymptotic sum rate at least $\ln 3$.

By step 2.1, the independent-private-message product-input MAC region has sum rate at most $\frac{3}{2}\ln 2$, strictly below $\ln 3$ by step 1.2. Therefore that separated rate region cannot carry this source pair at its entropy rate, while step 1.1 gives the uncoded zero-error correlated source-channel code.