Wyner-Ahlswede-Körner Network Demo¶

Author: Cheuk Ting Li

In [1]:

from psitip import *
PsiOpts.setting(
    solver = "ortools.GLOP",    # Set linear programming solver
    repr_latex = True,          # Jupyter Notebook LaTeX display
    venn_latex = True,          # LaTeX in diagrams
    proof_note_color = "blue",  # Reasons in proofs are blue
    random_seed = 4321          # Random seed for example searching
)

In [2]:

X, Y, U = rv("X, Y, U")
M1, M2 = rv_array("M", 1, 3)
R1, R2 = real_array("R", 1, 3)

model = CodingModel()        # Define WAK network [Wyner 1975], [Ahlswede-Körner 1975]
model.set_rate(M1, R1)       # The rate of M1, M2 are R1, R2 resp.
model.set_rate(M2, R2)
model.add_edge(X, Y)         # X, Y are correlated source
model.add_node(X, M1,
            label = "Enc 1") # Encoder 1 maps X to M1
model.add_node(Y, M2,
            label = "Enc 2") # Encoder 2 maps Y to M2
model.add_node(M1+M2, Y,
            label = "Dec")   # Decoder maps M1,M2 to Y

model.graph()                # Draw diagram

Out[2]:

In [3]:

r = model.get_inner()  # Automatic inner bound
r

Out[3]:

$\exists A_{M_1}:\, \left\{\begin{array}{l} R_2 \ge H(Y|A_{M_1}),\\ R_1 \ge I(A_{M_1}; X|Y),\\ R_1+R_2 \ge H(Y)+I(A_{M_1}; X|Y),\\ A_{M_1} \leftrightarrow X \leftrightarrow Y\\ \end{array} \right\}$

In [4]:

# Although the above region does not look like the WAK region
# [Wyner 1975], [Ahlswede-Körner 1975], they are actually equivalent.

# Write the WAK region
r_wak = alland([
    R1 >= I(U & X),
    R2 >= H(Y | U),
    markov(U, X, Y)
]).exists(U)
r_wak

Out[4]:

$\exists U:\, \left\{\begin{array}{l} R_1 \ge I(U; X),\\ R_2 \ge H(Y|U),\\ U \leftrightarrow X \leftrightarrow Y\\ \end{array} \right\}$

In [5]:

# Prove r is the same region as r_wak
# Requires a higher level of searching to prove
with PsiOpts(auxsearch_level = 10):
    print(bool(r >> r_wak))
    print(bool(r_wak >> r))

True
True

In [6]:

# Automatic outer bound with 1 auxiliary, coincides with inner bound
model.get_outer(1)

Out[6]:

$\exists A:\, \left\{\begin{array}{l} R_1 \ge I(A; X),\\ R_2 \ge H(Y|A),\\ A \leftrightarrow X \leftrightarrow Y\\ \end{array} \right\}$

In [7]:

bool(model.get_outer() >> r_wak)  # Converse proof

Out[7]:

True

In [8]:

# Output converse proof (is_proof = True for shorter proof)
(model.get_outer(is_proof = True) >> r_wak).proof()

Out[8]:

$\begin{align*} &1.\;\text{Claim:}\\ &\exists U:\, \left\{\begin{array}{l} R_1 \ge I(U; X),\\ R_2 \ge H(Y|U),\\ U \leftrightarrow X \leftrightarrow Y\\ \end{array} \right\}\\ \\ &\;\;1.1.\;\text{Substitute }U := (X_P, M_1)\text{:}\\ \\ &\;\;1.2.\;\text{Steps: }\\ &\;\;R_1\\ &\;\;\ge I(M_1; X, Y|X_P, Y_P)\;\;\;{\color{blue}{\left(\because\,\text{rate of }M_1\text{:}\, R_1 \ge I(M_1; X, Y|X_P, Y_P)\right)}}\\ &\;\;= I(M_1, X_P; X)\;\;\;{\color{blue}{\left(\because\, I(M_1; Y, X|X_P, Y_P) = I(X_P, M_1; X)\right)}}\\ \\ &\;\;1.3.\;\text{Steps: }\\ &\;\;R_2\\ &\;\;\ge I(M_2; X, Y|M_1, X_P, Y_P)\;\;\;{\color{blue}{\left(\because\,\text{rate of }M_2\text{:}\, R_2 \ge I(M_2; Y, X|Y_P, X_P, M_1)\right)}}\\ &\;\;= I(M_2, Y_P; X, Y|M_1, X_P)\;\;\;{\color{blue}{\left(\because\, (X, Y) \leftrightarrow (X_P, M_1) \leftrightarrow Y_P\right)}}\\ &\;\;\ge I(M_2; X, Y|M_1, X_P)\\ &\;\;\ge I(M_2; Y|M_1, X_P)\\ &\;\;= H(Y|M_1, X_P)\;\;\;{\color{blue}{\left(\because\, H(Y|X_P, M_1, M_2) = 0\right)}}\\ \end{align*} $

References¶

A. El Gamal and Y.-H. Kim, Network Information Theory, Cambridge University Press, 2011, Ch. 10.
A. Wyner, "On source coding with side information at the decoder," IEEE Transactions on Information Theory, vol. 21, no. 3, pp. 294-300, 1975.
R. Ahlswede and J. Körner, "Source coding with side information and a converse for degraded broadcast channels," IEEE Transactions on Information Theory, vol. 21, no. 6, pp. 629-637, 1975.

In [ ]: