{
"cells": [
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Wyner-Ahlswede-Körner Network Demo\n",
"\n",
"Author: Cheuk Ting Li "
]
},
{
"cell_type": "code",
"execution_count": 1,
"metadata": {},
"outputs": [],
"source": [
"from psitip import *\n",
"PsiOpts.setting(\n",
" solver = \"ortools.GLOP\", # Set linear programming solver\n",
" repr_latex = True, # Jupyter Notebook LaTeX display\n",
" venn_latex = True, # LaTeX in diagrams\n",
" proof_note_color = \"blue\", # Reasons in proofs are blue\n",
" random_seed = 4321 # Random seed for example searching\n",
")"
]
},
{
"cell_type": "code",
"execution_count": 2,
"metadata": {},
"outputs": [
{
"data": {
"image/svg+xml": [
"\r\n",
"\r\n",
"\r\n",
"\r\n",
"\r\n"
],
"text/plain": [
""
]
},
"execution_count": 2,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"X, Y, U = rv(\"X, Y, U\")\n",
"M1, M2 = rv_array(\"M\", 1, 3)\n",
"R1, R2 = real_array(\"R\", 1, 3)\n",
"\n",
"model = CodingModel() # Define WAK network [Wyner 1975], [Ahlswede-Körner 1975]\n",
"model.set_rate(M1, R1) # The rate of M1, M2 are R1, R2 resp.\n",
"model.set_rate(M2, R2)\n",
"model.add_edge(X, Y) # X, Y are correlated source\n",
"model.add_node(X, M1,\n",
" label = \"Enc 1\") # Encoder 1 maps X to M1\n",
"model.add_node(Y, M2,\n",
" label = \"Enc 2\") # Encoder 2 maps Y to M2\n",
"model.add_node(M1+M2, Y,\n",
" label = \"Dec\") # Decoder maps M1,M2 to Y\n",
"\n",
"model.graph() # Draw diagram"
]
},
{
"cell_type": "code",
"execution_count": 3,
"metadata": {},
"outputs": [
{
"data": {
"text/latex": [
"$\\exists A_{M_1}:\\, \\left\\{\\begin{array}{l}\n",
" R_2 \\ge H(Y|A_{M_1}),\\\\\n",
" R_1 \\ge I(A_{M_1}; X|Y),\\\\\n",
" R_1+R_2 \\ge H(Y)+I(A_{M_1}; X|Y),\\\\\n",
" A_{M_1} \\leftrightarrow X \\leftrightarrow Y\\\\\n",
"\\end{array} \\right\\}$"
],
"text/plain": [
"( ( R_2 >= H(Y|A_M_1) )\n",
" &( R_1 >= I(A_M_1&X|Y) )\n",
" &( R_1+R_2 >= H(Y)+I(A_M_1&X|Y) )\n",
" &( markov(A_M_1, X, Y) ) ).exists(A_M_1)"
]
},
"execution_count": 3,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"r = model.get_inner() # Automatic inner bound\n",
"r"
]
},
{
"cell_type": "code",
"execution_count": 4,
"metadata": {},
"outputs": [
{
"data": {
"text/latex": [
"$\\exists U:\\, \\left\\{\\begin{array}{l}\n",
" R_1 \\ge I(U; X),\\\\\n",
" R_2 \\ge H(Y|U),\\\\\n",
" U \\leftrightarrow X \\leftrightarrow Y\\\\\n",
"\\end{array} \\right\\}$"
],
"text/plain": [
"( ( R_1 >= I(U&X) )\n",
" &( R_2 >= H(Y|U) )\n",
" &( markov(U, X, Y) ) ).exists(U)"
]
},
"execution_count": 4,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"# Although the above region does not look like the WAK region\n",
"# [Wyner 1975], [Ahlswede-Körner 1975], they are actually equivalent.\n",
"\n",
"# Write the WAK region\n",
"r_wak = alland([\n",
" R1 >= I(U & X),\n",
" R2 >= H(Y | U),\n",
" markov(U, X, Y)\n",
"]).exists(U)\n",
"r_wak"
]
},
{
"cell_type": "code",
"execution_count": 5,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"True\n",
"True\n"
]
}
],
"source": [
"# Prove r is the same region as r_wak\n",
"# Requires a higher level of searching to prove\n",
"with PsiOpts(auxsearch_level = 10):\n",
" print(bool(r >> r_wak))\n",
" print(bool(r_wak >> r))"
]
},
{
"cell_type": "code",
"execution_count": 6,
"metadata": {},
"outputs": [
{
"data": {
"text/latex": [
"$\\exists A:\\, \\left\\{\\begin{array}{l}\n",
" R_1 \\ge I(A; X),\\\\\n",
" R_2 \\ge H(Y|A),\\\\\n",
" A \\leftrightarrow X \\leftrightarrow Y\\\\\n",
"\\end{array} \\right\\}$"
],
"text/plain": [
"( ( R_1 >= I(A&X) )\n",
" &( R_2 >= H(Y|A) )\n",
" &( markov(A, X, Y) ) ).exists(A)"
]
},
"execution_count": 6,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"# Automatic outer bound with 1 auxiliary, coincides with inner bound\n",
"model.get_outer(1)"
]
},
{
"cell_type": "code",
"execution_count": 7,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"True"
]
},
"execution_count": 7,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"bool(model.get_outer() >> r_wak) # Converse proof"
]
},
{
"cell_type": "code",
"execution_count": 8,
"metadata": {},
"outputs": [
{
"data": {
"text/latex": [
"$\\begin{align*}\n",
"&1.\\;\\text{Claim:}\\\\\n",
"&\\exists U:\\, \\left\\{\\begin{array}{l}\n",
" R_1 \\ge I(U; X),\\\\\n",
" R_2 \\ge H(Y|U),\\\\\n",
" U \\leftrightarrow X \\leftrightarrow Y\\\\\n",
"\\end{array} \\right\\}\\\\\n",
"\\\\\n",
"&\\;\\;1.1.\\;\\text{Substitute }U := (X_P, M_1)\\text{:}\\\\\n",
"\\\\\n",
"&\\;\\;1.2.\\;\\text{Steps: }\\\\\n",
"&\\;\\;R_1\\\\\n",
"&\\;\\;\\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)}}\\\\\n",
"&\\;\\;= 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)}}\\\\\n",
"\\\\\n",
"&\\;\\;1.3.\\;\\text{Steps: }\\\\\n",
"&\\;\\;R_2\\\\\n",
"&\\;\\;\\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)}}\\\\\n",
"&\\;\\;= 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)}}\\\\\n",
"&\\;\\;\\ge I(M_2; X, Y|M_1, X_P)\\\\\n",
"&\\;\\;\\ge I(M_2; Y|M_1, X_P)\\\\\n",
"&\\;\\;= H(Y|M_1, X_P)\\;\\;\\;{\\color{blue}{\\left(\\because\\, H(Y|X_P, M_1, M_2) = 0\\right)}}\\\\\n",
"\\end{align*}\n",
"$"
],
"text/plain": [
""
]
},
"execution_count": 8,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"# Output converse proof (is_proof = True for shorter proof)\n",
"(model.get_outer(is_proof = True) >> r_wak).proof()"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### References\n",
"- A. El Gamal and Y.-H. Kim, _Network Information Theory_, Cambridge University Press, 2011, Ch. 10.\n",
"- A. Wyner, \"On source coding with side information at the decoder,\" IEEE Transactions on Information Theory, vol. 21, no. 3, pp. 294-300, 1975.\n",
"- 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.\n"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": []
}
],
"metadata": {
"kernelspec": {
"display_name": "Python 3",
"language": "python",
"name": "python3"
},
"language_info": {
"codemirror_mode": {
"name": "ipython",
"version": 3
},
"file_extension": ".py",
"mimetype": "text/x-python",
"name": "python",
"nbconvert_exporter": "python",
"pygments_lexer": "ipython3",
"version": "3.8.3"
}
},
"nbformat": 4,
"nbformat_minor": 4
}