{
"cells": [
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Ch 14 - Joint Source-Channel Coding\n",
"\n",
"Reference: Ch 14 of A. El Gamal and Y.-H. Kim, _Network Information Theory_, Cambridge University Press, 2011.\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",
")"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Thm 14.1 (2-DMS over DM-MAC)\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": [
"X1, X2 = rv_array(\"X\", 1, 3)\n",
"Y = rv(\"Y\")\n",
"U1, U2 = rv_array(\"U\", 1, 3)\n",
"M1, M2 = rv_array(\"M\", 1, 3)\n",
"R1, R2 = real_array(\"R\", 1, 3)\n",
"\n",
"model = CodingModel() # Define multiple access channel\n",
"model.add_edge(U1, U2) # Correlated sources U1, U2\n",
"model.add_node(U1, X1, label = \"Enc 1\") # Encoder 1 maps U1 to X1\n",
"model.add_node(U2, X2, label = \"Enc 2\") # Encoder 2 maps U2 to X2\n",
"model.add_edge(X1+X2, Y) # Channel X1,X2 -> Y\n",
"model.add_node(Y, U1+U2, label = \"Dec\") # Decoder maps Y to U1,U2\n",
"\n",
"# model.partition = [U1+U2, X1+X2+Y]\n",
"\n",
"model.graph() # Draw diagram"
]
},
{
"cell_type": "code",
"execution_count": 3,
"metadata": {},
"outputs": [
{
"data": {
"text/latex": [
"$\\displaystyle \\begin{array}{l}\n",
"{\\color{blue}{\\text{Codebook:}}}\\\\\n",
"{\\color{blue}{\\;\\;U_1[i_1], X_1[i_1]\\text{,}\\,\\text{rate = }H(U_1)}}\\\\\n",
"{\\color{blue}{\\;\\;U_2[i_2], X_2[i_2]\\text{,}\\,\\text{rate = }H(U_2)}}\\\\\n",
"{\\color{blue}{\\text{Enc 1}\\,\\text{finds}\\,i_1\\text{:}\\,\\left(U_1\\text{,}U_1[i_1], X_1[i_1]\\right)\\in\\mathcal{T}}}\\\\\n",
"{\\color{blue}{\\text{Enc 2}\\,\\text{finds}\\,i_2\\text{:}\\,\\left(U_2\\text{,}U_2[i_2], X_2[i_2]\\right)\\in\\mathcal{T}}}\\\\\n",
"{\\color{blue}{\\text{Dec}\\,\\text{finds}\\,i_2, i_1\\text{:}\\,\\left(Y\\text{,}U_2[i_2], X_2[i_2], U_1[i_1], X_1[i_1]\\right)\\in\\mathcal{T}}}\\\\\n",
"\\exists Q_i:\\, \\left\\{\\begin{array}{l}\n",
" \\begin{array}{l}\n",
"H(U_1) \\le I(U_1, X_1; U_2, X_2, Y|Q_i)\\\\\n",
"{\\color{blue}{\\;\\;\\;\\;\\left(\\because\\,\\text{enc }U_1\\text{ to }X_1\\text{,}\\,\\text{dec }Y\\text{ to }U_1, X_1\\right)}}\n",
"\\end{array},\\\\\n",
" \\begin{array}{l}\n",
"H(U_2) \\le I(U_2, X_2; U_1, X_1, Y|Q_i)\\\\\n",
"{\\color{blue}{\\;\\;\\;\\;\\left(\\because\\,\\text{enc }U_2\\text{ to }X_2\\text{,}\\,\\text{dec }Y\\text{ to }U_2, X_2\\right)}}\n",
"\\end{array},\\\\\n",
" \\begin{array}{l}\n",
"H(U_1)+H(U_2) \\le I(U_2, X_2; Y|Q_i)+I(U_1, X_1; U_2, X_2, Y|Q_i)\\\\\n",
"{\\color{blue}{\\;\\;\\;\\;\\left(\\because\\,\\text{enc }U_2\\text{ to }X_2\\text{,}\\,\\text{enc }U_1\\text{ to }X_1\\text{,}\\,\\text{dec }Y\\text{ to }U_2, X_2, U_1, X_1\\right)}}\n",
"\\end{array},\\\\\n",
" Q_i {\\perp\\!\\!\\perp} (U_1, U_2),\\\\\n",
" U_1 \\leftrightarrow (Q_i, U_2) \\leftrightarrow X_2,\\\\\n",
" (U_2, X_2) \\leftrightarrow (Q_i, U_1) \\leftrightarrow X_1,\\\\\n",
" (Q_i, U_1, U_2) \\leftrightarrow (X_1, X_2) \\leftrightarrow Y\\\\\n",
"\\end{array} \\right\\}\n",
"\\end{array}$"
],
"text/plain": [
""
]
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
"r = model.get_inner(is_proof=True) # Automatic inner bound\n",
"r.display(note=True) # Include reasons in blue"
]
},
{
"cell_type": "code",
"execution_count": 4,
"metadata": {},
"outputs": [
{
"data": {
"text/latex": [
"$\\exists Q:\\, \\left\\{\\begin{array}{l}\n",
" H(U_1|U_2) \\le I(X_1; Y|U_2, X_2, Q),\\\\\n",
" H(U_2|U_1) \\le I(X_2; Y|U_1, X_1, Q),\\\\\n",
" H(U_1, U_2) \\le I(X_1, X_2; Y|Q),\\\\\n",
" Q {\\perp\\!\\!\\perp} (U_1, U_2),\\\\\n",
" U_1 \\leftrightarrow (Q, U_2) \\leftrightarrow X_2,\\\\\n",
" (U_2, X_2) \\leftrightarrow (Q, U_1) \\leftrightarrow X_1,\\\\\n",
" (Q, U_1, U_2) \\leftrightarrow (X_1, X_2) \\leftrightarrow Y\\\\\n",
"\\end{array} \\right\\}$"
],
"text/plain": [
"( ( H(U_1|U_2) <= I(X_1&Y|U_2+X_2+Q) )\n",
" &( H(U_2|U_1) <= I(X_2&Y|U_1+X_1+Q) )\n",
" &( H(U_1+U_2) <= I(X_1+X_2&Y|Q) )\n",
" &( indep(Q, U_1+U_2) )\n",
" &( markov(U_1, Q+U_2, X_2) )\n",
" &( markov(U_2+X_2, Q+U_1, X_1) )\n",
" &( markov(Q+U_1+U_2, X_1+X_2, Y) ) ).exists(Q)"
]
},
"execution_count": 4,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"# The inner bound in [Cover-El Gamal-Salehi 1980], \n",
"# which is equivalent to the above\n",
"Q = rv(\"Q\")\n",
"r_in = region(\n",
" H(U1 | U2) <= I(X1 & Y | U2+X2+Q),\n",
" H(U2 | U1) <= I(X2 & Y | U1+X1+Q),\n",
" H(U1+U2) <= I(X1+X2 & Y | Q),\n",
" bnet((U1, U2), (U1+Q, X1), (U2+Q, X2), (X1+X2, Y))\n",
").exists(Q)\n",
"r_in"
]
},
{
"cell_type": "code",
"execution_count": 5,
"metadata": {},
"outputs": [
{
"data": {
"text/latex": [
"$\\begin{align*}\n",
"&1.\\;\\text{Claim:}\\\\\n",
"&\\exists Q_i:\\, \\left\\{\\begin{array}{l}\n",
" H(U_1) \\le I(U_1, X_1; U_2, X_2, Y|Q_i),\\\\\n",
" H(U_2) \\le I(U_2, X_2; U_1, X_1, Y|Q_i),\\\\\n",
" H(U_1)+H(U_2) \\le I(U_2, X_2; Y|Q_i)+I(U_1, X_1; U_2, X_2, Y|Q_i),\\\\\n",
" Q_i {\\perp\\!\\!\\perp} (U_1, U_2),\\\\\n",
" U_1 \\leftrightarrow (Q_i, U_2) \\leftrightarrow X_2,\\\\\n",
" (U_2, X_2) \\leftrightarrow (Q_i, U_1) \\leftrightarrow X_1,\\\\\n",
" (Q_i, U_1, U_2) \\leftrightarrow (X_1, X_2) \\leftrightarrow Y\\\\\n",
"\\end{array} \\right\\}\\\\\n",
"\\\\\n",
"&\\;\\;1.1.\\;\\text{Substitute }Q_i := Q\\text{:}\\\\\n",
"\\\\\n",
"&\\;\\;1.2.\\;\\text{Steps: }\\\\\n",
"&\\;\\;H(U_1)\\\\\n",
"&\\;\\;= H(U_1)+H(Q, X_1|U_2)+H(U_2, X_2|Q)-H(Q, U_2, X_1, X_2)\\;\\;\\;{\\color{blue}{\\left(\\because\\, H(Q, X_2|U_2) = H(X_2|U_2, Q, X_1)+H(Q)\\right)}}\\\\\n",
"&\\;\\;\\le I(U_1; U_2)+I(Q, X_2, Y; X_1|U_2)-I(Q; U_2, X_1)\\;\\;\\;{\\color{blue}{\\left(\\because\\, H(U_1|U_2) \\le I(X_1; Y|U_2, X_2, Q)\\right)}}\\\\\n",
"&\\;\\;= I(U_1, X_1; U_2, X_2, Y|Q)\\;\\;\\;{\\color{blue}{\\left(\\because\\, I(X_2, Y; U_1|Q, X_1)+I(Q, X_1, X_2, Y; U_2|U_1) = I(X_2, Y; U_2|Q, X_1)\\right)}}\\\\\n",
"\\\\\n",
"&\\;\\;1.3.\\;\\text{Steps: }\\\\\n",
"&\\;\\;H(U_2)\\\\\n",
"&\\;\\;= H(U_2|U_1)+I(U_2, X_2; U_1, X_1, Y|Q)-I(X_2; Y|Q, U_1, X_1)\\\\\n",
"&\\;\\;\\;\\;\\;\\;\\;\\;\\;\\;{\\color{blue}{\\left(\\because\\, I(X_2; U_1, X_1|Q)+I(Q, X_1, X_2, Y; U_2|U_1) = I(Q, X_2; U_2)\\right)}}\\\\\n",
"&\\;\\;\\le I(U_2, X_2; U_1, X_1, Y|Q)\\;\\;\\;{\\color{blue}{\\left(\\because\\, H(U_2|U_1) \\le I(X_2; Y|U_1, X_1, Q)\\right)}}\\\\\n",
"\\\\\n",
"&\\;\\;1.4.\\;\\text{Steps: }\\\\\n",
"&\\;\\;H(U_1)+H(U_2)\\\\\n",
"&\\;\\;\\le I(U_1; U_2)+I(X_1, X_2; Y|Q)\\;\\;\\;{\\color{blue}{\\left(\\because\\, H(U_1, U_2) \\le I(X_1, X_2; Y|Q)\\right)}}\\\\\n",
"&\\;\\;= I(U_2, X_2; Y|Q)+I(U_1, X_1; U_2, X_2, Y|Q)\\\\\n",
"&\\;\\;\\;\\;\\;\\;\\;\\;\\;\\;{\\color{blue}{\\left(\\because\\, I(X_2; X_1|Q)+I(X_2, Y; U_1|Q, X_1)+I(Q, X_1, X_2, Y; U_2|U_1) = I(Q, X_2; U_2)\\right)}}\\\\\n",
"\\end{align*}\n",
"$"
],
"text/plain": [
""
]
},
"execution_count": 5,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"(r_in >> r).proof() # Prove one direction of equivalence"
]
},
{
"cell_type": "code",
"execution_count": 6,
"metadata": {},
"outputs": [
{
"data": {
"text/latex": [
"$\\begin{align*}\n",
"&1.\\;\\text{Claim:}\\\\\n",
"&\\exists Q:\\, \\left\\{\\begin{array}{l}\n",
" H(U_1|U_2) \\le I(X_1; Y|U_2, X_2, Q),\\\\\n",
" H(U_2|U_1) \\le I(X_2; Y|U_1, X_1, Q),\\\\\n",
" H(U_1, U_2) \\le I(X_1, X_2; Y|Q),\\\\\n",
" Q {\\perp\\!\\!\\perp} (U_1, U_2),\\\\\n",
" U_1 \\leftrightarrow (Q, U_2) \\leftrightarrow X_2,\\\\\n",
" (U_2, X_2) \\leftrightarrow (Q, U_1) \\leftrightarrow X_1,\\\\\n",
" (Q, U_1, U_2) \\leftrightarrow (X_1, X_2) \\leftrightarrow Y\\\\\n",
"\\end{array} \\right\\}\\\\\n",
"\\\\\n",
"&\\;\\;1.1.\\;\\text{Substitute }Q := Q_i\\text{:}\\\\\n",
"\\\\\n",
"&\\;\\;1.2.\\;\\text{Steps: }\\\\\n",
"&\\;\\;H(U_1|U_2)\\\\\n",
"&\\;\\;= H(U_1, U_2)+H(X_1|Q_i, U_2, X_2)-H(U_2, X_1|Q_i)\\;\\;\\;{\\color{blue}{\\left(\\because\\, H(X_2|U_2, Q_i, X_1)+H(Q_i) = H(Q_i, X_2|U_2)\\right)}}\\\\\n",
"&\\;\\;\\le H(U_2|U_1)+H(X_2|Q_i, U_2, X_1)+H(Y|Q_i, U_2, X_2)-H(U_2, X_2, Y|Q_i, U_1, X_1)\\\\\n",
"&\\;\\;\\;\\;\\;\\;\\;\\;\\;\\;{\\color{blue}{\\left(\\because\\,\\text{enc }U_1\\text{ to }X_1\\text{,}\\,\\text{dec }Y\\text{ to }U_1, X_1\\text{:}\\, H(U_1) \\le I(U_1, X_1; U_2, X_2, Y|Q_i)\\right)}}\\\\\n",
"&\\;\\;= I(X_1; Y|Q_i, U_2, X_2)\\;\\;\\;{\\color{blue}{\\left(\\because\\, I(X_2, Y; U_2|Q_i, X_1) = I(X_2, Y; U_1|Q_i, X_1)+I(Q_i, X_1, X_2, Y; U_2|U_1)\\right)}}\\\\\n",
"\\\\\n",
"&\\;\\;1.3.\\;\\text{Steps: }\\\\\n",
"&\\;\\;H(U_2|U_1)\\\\\n",
"&\\;\\;\\le I(U_2, X_2; U_1, X_1, Y|Q_i)-I(U_1; U_2)\\\\\n",
"&\\;\\;\\;\\;\\;\\;\\;\\;\\;\\;{\\color{blue}{\\left(\\because\\,\\text{enc }U_2\\text{ to }X_2\\text{,}\\,\\text{dec }Y\\text{ to }U_2, X_2\\text{:}\\, H(U_2) \\le I(U_2, X_2; U_1, X_1, Y|Q_i)\\right)}}\\\\\n",
"&\\;\\;= I(X_2; Y|Q_i, U_1, X_1)\\;\\;\\;{\\color{blue}{\\left(\\because\\, I(Q_i, X_2; U_2) = I(X_2; U_1, X_1|Q_i)+I(Q_i, X_1, X_2, Y; U_2|U_1)\\right)}}\\\\\n",
"\\\\\n",
"&\\;\\;1.4.\\;\\text{Steps: }\\\\\n",
"&\\;\\;H(U_1, U_2)\\\\\n",
"&\\;\\;\\le H(U_1, X_1|Q_i)+H(U_2, X_2|Q_i)-I(U_1; U_2)-H(U_1, U_2, X_1, X_2|Q_i, Y)\\\\\n",
"&\\;\\;\\;\\;\\;\\;\\;\\;\\;\\;{\\color{blue}{\\left(\\because\\,\\text{enc }U_2\\text{ to }X_2\\text{,}\\,\\text{enc }U_1\\text{ to }X_1\\text{,}\\,\\text{dec }Y\\text{ to }U_2, X_2, U_1, X_1\\text{:}\\, H(U_1)+H(U_2) \\le I(U_2, X_2; Y|Q_i)+I(U_1, X_1; U_2, X_2, Y|Q_i)\\right)}}\\\\\n",
"&\\;\\;= I(X_1, X_2; Y|Q_i)\\;\\;\\;{\\color{blue}{\\left(\\because\\, I(Q_i, X_2; U_2) = I(X_2; X_1|Q_i)+I(X_2, Y; U_1|Q_i, X_1)+I(Q_i, X_1, X_2, Y; U_2|U_1)\\right)}}\\\\\n",
"\\end{align*}\n",
"$"
],
"text/plain": [
""
]
},
"execution_count": 6,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"(r >> r_in).proof() # Prove another direction of equivalence"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Thm 14.2 (2-DMS with Common Part over DM-MAC) (Not proved)\n"
]
},
{
"cell_type": "code",
"execution_count": 7,
"metadata": {},
"outputs": [
{
"data": {
"image/svg+xml": [
"\r\n",
"\r\n",
"\r\n",
"\r\n",
"\r\n"
],
"text/plain": [
""
]
},
"execution_count": 7,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"X1, X2 = rv_array(\"X\", 1, 3)\n",
"Y = rv(\"Y\")\n",
"U0, U1, U2 = rv_array(\"U\", 0, 3)\n",
"M1, M2 = rv_array(\"M\", 1, 3)\n",
"R1, R2 = real_array(\"R\", 1, 3)\n",
"\n",
"model = CodingModel() # Define multiple access channel\n",
"model.add_edge(U0, U1) # Correlated sources U0, U1, U2\n",
"model.add_edge(U0+U1, U2) # Correlated sources U0, U1, U2\n",
"model.add_node(U0+U1, X1, label = \"Enc 1\") # Encoder 1 maps U0,U1 to X1\n",
"model.add_node(U0+U2, X2, label = \"Enc 2\") # Encoder 2 maps U0,U2 to X2\n",
"model.add_edge(X1+X2, Y) # Channel X1,X2 -> Y\n",
"model.add_node(Y, U0+U1+U2, label = \"Dec\") # Decoder maps Y to U0,U1,U2\n",
"\n",
"# model.partition = [U0+U1+U2, X1+X2+Y]\n",
"\n",
"model.graph() # Draw diagram"
]
},
{
"cell_type": "code",
"execution_count": 8,
"metadata": {},
"outputs": [
{
"data": {
"text/latex": [
"$\\displaystyle \\begin{array}{l}\n",
"{\\color{blue}{\\text{Codebook:}}}\\\\\n",
"{\\color{blue}{\\;\\;A_{X_1, X_2}[i_1]\\text{,}\\,\\text{rate = }I(A_{X_1, X_2}; U_0)}}\\\\\n",
"{\\color{blue}{\\;\\;U_0[i_2], U_1[i_2], X_1[i_2]\\text{,}\\,\\text{rate = }H(U_0, U_1)+I(A_{X_1, X_2}; X_1|U_0, U_1)}}\\\\\n",
"{\\color{blue}{\\;\\;U_0[i_3], U_2[i_3], X_2[i_3]\\text{,}\\,\\text{rate = }H(U_0, U_2)+I(A_{X_1, X_2}; X_2|U_0, U_2)}}\\\\\n",
"{\\color{blue}{\\text{Enc 1}\\,\\text{finds}\\,i_1\\text{:}\\,\\left(U_0\\text{,}A_{X_1, X_2}[i_1]\\right)\\in\\mathcal{T}}}\\\\\n",
"{\\color{blue}{\\;\\;\\;\\;\\text{finds}\\,i_2\\text{:}\\,\\left(U_0, U_1, A_{X_1, X_2}\\text{,}U_0[i_2], U_1[i_2], X_1[i_2]\\right)\\in\\mathcal{T}}}\\\\\n",
"{\\color{blue}{\\text{Enc 2}\\,\\text{finds}\\,i_3\\text{:}\\,\\left(U_0, U_2, A_{X_1, X_2}\\text{,}U_0[i_3], U_2[i_3], X_2[i_3]\\right)\\in\\mathcal{T}}}\\\\\n",
"{\\color{blue}{\\text{Dec}\\,\\text{finds}\\,i_1, i_3, i_2\\text{:}\\,\\left(Y\\text{,}A_{X_1, X_2}[i_1], U_0[i_3], U_2[i_3], X_2[i_3], U_0[i_2], U_1[i_2], X_1[i_2]\\right)\\in\\mathcal{T}}}\\\\\n",
"\\exists A_{X_1, X_2}:\\, \\left\\{\\begin{array}{l}\n",
" \\begin{array}{l}\n",
"H(U_1|A_{X_1, X_2}, U_0, U_2, X_2, Y) \\le I(X_1; Y|A_{X_1, X_2}, U_0, U_1, X_2)\\\\\n",
"{\\color{blue}{\\;\\;\\;\\;\\left(\\because\\,\\text{enc }U_0, U_1, A_{X_1, X_2}\\text{ to }X_1\\text{,}\\,\\text{dec }Y\\text{ to }U_0, U_1, X_1\\right)}}\n",
"\\end{array},\\\\\n",
" \\begin{array}{l}\n",
"H(U_2|A_{X_1, X_2}, U_0, U_1, X_1, Y) \\le I(X_2; Y|A_{X_1, X_2}, U_0, U_2, X_1)\\\\\n",
"{\\color{blue}{\\;\\;\\;\\;\\left(\\because\\,\\text{enc }U_0, U_2, A_{X_1, X_2}\\text{ to }X_2\\text{,}\\,\\text{dec }Y\\text{ to }U_0, U_2, X_2\\right)}}\n",
"\\end{array},\\\\\n",
" \\begin{array}{l}\n",
"H(U_2|U_0)+H(U_1|A_{X_1, X_2}, U_0, U_2, X_2, Y) \\le I(U_2, X_2; Y|A_{X_1, X_2}, U_0)+I(X_1; Y|A_{X_1, X_2}, U_0, U_1, X_2)\\\\\n",
"{\\color{blue}{\\;\\;\\;\\;\\left(\\because\\,\\text{enc }U_0, U_2, A_{X_1, X_2}\\text{ to }X_2\\text{,}\\,\\text{enc }U_0, U_1, A_{X_1, X_2}\\text{ to }X_1\\text{,}\\,\\text{dec }Y\\text{ to }U_2, X_2, U_0, U_1, X_1\\text{,}\\,\\text{enc }U_0, U_2, A_{X_1, X_2}\\text{ to }X_2\\text{,}\\,\\text{enc }U_0, U_1, A_{X_1, X_2}\\text{ to }X_1\\text{,}\\,\\text{dec }Y\\text{ to }U_2, X_2, U_0, U_1, X_1\\text{,}\\,\\text{enc }U_0, U_2, A_{X_1, X_2}\\text{ to }X_2\\text{,}\\,\\text{enc }U_0, U_1, A_{X_1, X_2}\\text{ to }X_1\\text{,}\\,\\text{dec }Y\\text{ to }U_2, X_2, U_0, U_1, X_1\\right)}}\n",
"\\end{array},\\\\\n",
" \\begin{array}{l}\n",
"H(U_2|U_0)+H(U_0, U_1)+I(A_{X_1, X_2}; X_1|U_0, U_1) \\le I(A_{X_1, X_2}, U_0, U_2, X_2; Y)+I(A_{X_1, X_2}, U_2, X_2, Y; U_1, X_1|U_0)\\\\\n",
"{\\color{blue}{\\;\\;\\;\\;\\left(\\because\\,\\text{enc }U_0, U_2, A_{X_1, X_2}\\text{ to }X_2\\text{,}\\,\\text{enc }U_0, U_1, A_{X_1, X_2}\\text{ to }X_1\\text{,}\\,\\text{enc }U_0\\text{ to }A_{X_1, X_2}\\text{,}\\,\\text{dec }Y\\text{ to }A_{X_1, X_2}, U_2, X_2, U_0, U_1, X_1\\right)}}\n",
"\\end{array},\\\\\n",
" (U_1, U_2) \\leftrightarrow U_0 \\leftrightarrow A_{X_1, X_2},\\\\\n",
" U_2 \\leftrightarrow (A_{X_1, X_2}, U_1, U_0) \\leftrightarrow X_1,\\\\\n",
" (U_1, X_1) \\leftrightarrow (A_{X_1, X_2}, U_2, U_0) \\leftrightarrow X_2,\\\\\n",
" (U_1, U_2, U_0, A_{X_1, X_2}) \\leftrightarrow (X_1, X_2) \\leftrightarrow Y\\\\\n",
"\\end{array} \\right\\}\n",
"\\end{array}$"
],
"text/plain": [
""
]
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
"r = model.get_inner(is_proof=True) # Automatic inner bound\n",
"r.display(note=True) # Include reasons in blue"
]
},
{
"cell_type": "code",
"execution_count": 9,
"metadata": {},
"outputs": [
{
"data": {
"text/latex": [
"$\\exists W:\\, \\left\\{\\begin{array}{l}\n",
" H(U_1|U_0, U_2) \\le I(X_1; Y|U_0, U_2, X_2, W),\\\\\n",
" H(U_2|U_0, U_1) \\le I(X_2; Y|U_0, U_1, X_1, W),\\\\\n",
" H(U_1, U_2|U_0) \\le I(X_1, X_2; Y|U_0, W),\\\\\n",
" H(U_0, U_1, U_2) \\le I(X_1, X_2; Y),\\\\\n",
" W {\\perp\\!\\!\\perp} (U_1, U_2, U_0),\\\\\n",
" U_2 \\leftrightarrow (W, U_0, U_1) \\leftrightarrow X_1,\\\\\n",
" (U_1, X_1) \\leftrightarrow (W, U_0, U_2) \\leftrightarrow X_2,\\\\\n",
" (W, U_1, U_2, U_0) \\leftrightarrow (X_1, X_2) \\leftrightarrow Y\\\\\n",
"\\end{array} \\right\\}$"
],
"text/plain": [
"( ( H(U_1|U_0+U_2) <= I(X_1&Y|U_0+U_2+X_2+W) )\n",
" &( H(U_2|U_0+U_1) <= I(X_2&Y|U_0+U_1+X_1+W) )\n",
" &( H(U_1+U_2|U_0) <= I(X_1+X_2&Y|U_0+W) )\n",
" &( H(U_0+U_1+U_2) <= I(X_1+X_2&Y) )\n",
" &( indep(W, U_1+U_2+U_0) )\n",
" &( markov(U_2, W+U_0+U_1, X_1) )\n",
" &( markov(U_1+X_1, W+U_0+U_2, X_2) )\n",
" &( markov(W+U_1+U_2+U_0, X_1+X_2, Y) ) ).exists(W)"
]
},
"execution_count": 9,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"# The inner bound in [Cover-El Gamal-Salehi 1980]\n",
"W = rv(\"W\")\n",
"r_in = region(\n",
" H(U1 | U0+U2) <= I(X1 & Y | U0+U2+X2+W),\n",
" H(U2 | U0+U1) <= I(X2 & Y | U0+U1+X1+W),\n",
" H(U1+U2 | U0) <= I(X1+X2 & Y | U0+W),\n",
" H(U0+U1+U2) <= I(X1+X2 & Y),\n",
" bnet((U0, U1), (U0+U1, U2), (U0+U1+W, X1), (U0+U2+W, X2), (X1+X2, Y))\n",
").exists(W)\n",
"r_in"
]
},
{
"cell_type": "code",
"execution_count": 10,
"metadata": {},
"outputs": [
{
"data": {
"text/latex": [
"$\\begin{align*}\n",
"&1.\\;\\text{Claim:}\\\\\n",
"&\\exists A_{X_1, X_2}:\\, \\left\\{\\begin{array}{l}\n",
" H(U_1|A_{X_1, X_2}, U_0, U_2, X_2, Y) \\le I(X_1; Y|A_{X_1, X_2}, U_0, U_1, X_2),\\\\\n",
" H(U_2|A_{X_1, X_2}, U_0, U_1, X_1, Y) \\le I(X_2; Y|A_{X_1, X_2}, U_0, U_2, X_1),\\\\\n",
" H(U_2|U_0)+H(U_1|A_{X_1, X_2}, U_0, U_2, X_2, Y) \\le I(U_2, X_2; Y|A_{X_1, X_2}, U_0)+I(X_1; Y|A_{X_1, X_2}, U_0, U_1, X_2),\\\\\n",
" H(U_2|U_0)+H(U_0, U_1)+I(A_{X_1, X_2}; X_1|U_0, U_1) \\le I(A_{X_1, X_2}, U_0, U_2, X_2; Y)+I(A_{X_1, X_2}, U_2, X_2, Y; U_1, X_1|U_0),\\\\\n",
" (U_1, U_2) \\leftrightarrow U_0 \\leftrightarrow A_{X_1, X_2},\\\\\n",
" U_2 \\leftrightarrow (A_{X_1, X_2}, U_1, U_0) \\leftrightarrow X_1,\\\\\n",
" (U_1, X_1) \\leftrightarrow (A_{X_1, X_2}, U_2, U_0) \\leftrightarrow X_2,\\\\\n",
" (U_1, U_2, U_0, A_{X_1, X_2}) \\leftrightarrow (X_1, X_2) \\leftrightarrow Y\\\\\n",
"\\end{array} \\right\\}\\\\\n",
"\\\\\n",
"&\\;\\;1.1.\\;\\text{Substitute }A_{X_1, X_2} := W\\text{:}\\\\\n",
"\\\\\n",
"&\\;\\;1.2.\\;\\text{Steps: }\\\\\n",
"&\\;\\;H(U_1|W, U_0, U_2, X_2, Y)\\\\\n",
"&\\;\\;= H(U_1|U_0, U_2)+H(Y|U_0, U_1, W, X_2)-H(Y|U_0, U_2, W, X_2)\\\\\n",
"&\\;\\;\\;\\;\\;\\;\\;\\;\\;\\;{\\color{blue}{\\left(\\because\\, H(W, X_2|U_2, U_0)+H(Y|W, U_1, U_0, X_2) = H(W, X_2, Y|U_1, U_2, U_0)\\right)}}\\\\\n",
"&\\;\\;\\le I(U_0, U_2, W, X_1, X_2; Y)-I(U_0, U_1, W, X_2; Y)\\;\\;\\;{\\color{blue}{\\left(\\because\\, H(U_1|U_0, U_2) \\le I(X_1; Y|U_0, U_2, X_2, W)\\right)}}\\\\\n",
"&\\;\\;= I(X_1; Y|U_0, U_1, W, X_2)-I(U_0, U_1, W; Y|X_1, X_2)\\;\\;\\;{\\color{blue}{\\left(\\because\\, (W, U_2, U_0) \\leftrightarrow (X_1, X_2) \\leftrightarrow Y\\right)}}\\\\\n",
"&\\;\\;= I(X_1; Y|U_0, U_1, W, X_2)\\;\\;\\;{\\color{blue}{\\left(\\because\\, (W, U_1, U_0) \\leftrightarrow (X_1, X_2) \\leftrightarrow Y\\right)}}\\\\\n",
"\\\\\n",
"&\\;\\;1.3.\\;\\text{Steps: }\\\\\n",
"&\\;\\;H(U_2|W, U_0, U_1, X_1, Y)\\\\\n",
"&\\;\\;= H(U_2|U_0, U_1)+H(Y|U_0, U_2, W, X_1)-H(Y|U_0, U_1, W, X_1)\\\\\n",
"&\\;\\;\\;\\;\\;\\;\\;\\;\\;\\;{\\color{blue}{\\left(\\because\\, H(W, X_1|U_1, U_0)+H(Y|W, U_2, U_0, X_1) = H(W, X_1, Y|U_1, U_2, U_0)\\right)}}\\\\\n",
"&\\;\\;\\le I(U_0, U_1, W, X_1, X_2; Y)-I(U_0, U_2, W, X_1; Y)\\;\\;\\;{\\color{blue}{\\left(\\because\\, H(U_2|U_0, U_1) \\le I(X_2; Y|U_0, U_1, X_1, W)\\right)}}\\\\\n",
"&\\;\\;= I(X_2; Y|U_0, U_2, W, X_1)-I(U_0, U_2, W; Y|X_1, X_2)\\;\\;\\;{\\color{blue}{\\left(\\because\\, (W, U_1, U_0) \\leftrightarrow (X_1, X_2) \\leftrightarrow Y\\right)}}\\\\\n",
"&\\;\\;= I(X_2; Y|U_0, U_2, W, X_1)\\;\\;\\;{\\color{blue}{\\left(\\because\\, (W, U_2, U_0) \\leftrightarrow (X_1, X_2) \\leftrightarrow Y\\right)}}\\\\\n",
"\\\\\n",
"&\\;\\;1.4.\\;\\text{Steps: }\\\\\n",
"&\\;\\;H(U_2|U_0)+H(U_1|W, U_0, U_2, X_2, Y)\\\\\n",
"&\\;\\;= H(U_1, U_2|U_0)+H(Y|U_0, U_1, W, X_2)-H(Y|U_0, U_2, W, X_2)\\\\\n",
"&\\;\\;\\;\\;\\;\\;\\;\\;\\;\\;{\\color{blue}{\\left(\\because\\, H(W, X_2|U_2, U_0)+H(Y|W, U_1, U_0, X_2) = H(W, X_2, Y|U_1, U_2, U_0)\\right)}}\\\\\n",
"&\\;\\;\\le I(U_2, X_2; Y|U_0, W)+I(X_1; Y|U_0, U_1, W, X_2)-I(U_1; Y|U_0, W, X_1, X_2)\\\\\n",
"&\\;\\;\\;\\;\\;\\;\\;\\;\\;\\;{\\color{blue}{\\left(\\because\\, H(U_1, U_2|U_0) \\le I(X_1, X_2; Y|U_0, W)\\right)}}\\\\\n",
"&\\;\\;= I(U_2, X_2; Y|U_0, W)+I(X_1; Y|U_0, U_1, W, X_2)\\;\\;\\;{\\color{blue}{\\left(\\because\\, U_1 \\leftrightarrow (X_1, X_2, W, U_0) \\leftrightarrow Y\\right)}}\\\\\n",
"\\\\\n",
"&\\;\\;1.5.\\;\\text{Steps: }\\\\\n",
"&\\;\\;H(U_2|U_0)+H(U_0, U_1)+I(W; X_1|U_0, U_1)\\\\\n",
"&\\;\\;\\le I(U_1; U_0, U_2)+I(X_1, X_2; Y)+I(U_0, X_1; W|U_1)-I(U_0; U_1, W)\\;\\;\\;{\\color{blue}{\\left(\\because\\, H(U_0, U_1, U_2) \\le I(X_1, X_2; Y)\\right)}}\\\\\n",
"&\\;\\;= I(U_0, U_2, W, X_2; Y)+I(U_1, X_1; U_2, W, X_2, Y|U_0)\\\\\n",
"&\\;\\;\\;\\;\\;\\;\\;\\;\\;\\;{\\color{blue}{\\left(\\because\\, H(U_1|U_2, U_0)+H(X_1|W, U_1, U_0)+H(Y|X_1, X_2) = H(U_1, X_1, Y|W, U_2, U_0, X_2)\\right)}}\\\\\n",
"\\end{align*}\n",
"$"
],
"text/plain": [
""
]
},
"execution_count": 10,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"(r_in >> r).proof() # Our bound is at least as large as Cover-El Gamal-Salehi"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Thm 14.3 (Gray-Wyner System)\n"
]
},
{
"cell_type": "code",
"execution_count": 11,
"metadata": {},
"outputs": [
{
"data": {
"image/svg+xml": [
"\r\n",
"\r\n",
"\r\n",
"\r\n",
"\r\n"
],
"text/plain": [
""
]
},
"execution_count": 11,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"X, Y, U = rv(\"X, Y, U\")\n",
"M0, M1, M2 = rv_array(\"M\", 3)\n",
"R0, R1, R2 = real_array(\"R\", 3)\n",
"\n",
"model = CodingModel() # Define Gray-Wyner system\n",
"model.set_rate(M0, R0) # The rate of M0, M1, M2 are R0, R1, R2 resp.\n",
"model.set_rate(M1, R1)\n",
"model.set_rate(M2, R2)\n",
"model.add_edge(X, Y) # X, Y are correlated source\n",
"model.add_node(X+Y, M0+M1+M2,\n",
" label = \"Enc\") # Encoder maps X,Y to M0,M1,M2\n",
"model.add_node(M0+M1, X,\n",
" label = \"Dec 1\") # Decoder 1 maps M0,M1 to X\n",
"model.add_node(M0+M2, Y,\n",
" label = \"Dec 2\") # Decoder 2 maps M0,M2 to Y\n",
"\n",
"model.graph() # Draw diagram"
]
},
{
"cell_type": "code",
"execution_count": 12,
"metadata": {},
"outputs": [
{
"data": {
"text/latex": [
"$\\exists A:\\, \\left\\{\\begin{array}{l}\n",
" R_1 \\ge H(X|A),\\\\\n",
" R_2 \\ge H(Y|A),\\\\\n",
" R_0 \\ge I(A; X, Y)\\\\\n",
"\\end{array} \\right\\}$"
],
"text/plain": [
"( ( R_1 >= H(X|A) )\n",
" &( R_2 >= H(Y|A) )\n",
" &( R_0 >= I(A&X+Y) ) ).exists(A)"
]
},
"execution_count": 12,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"# Automatic outer bound with 1 auxiliary, gets Gray-Wyner region [Gray-Wyner 1974]\n",
"r_gw = model.get_outer(1)\n",
"r_gw"
]
},
{
"cell_type": "code",
"execution_count": 13,
"metadata": {},
"outputs": [
{
"data": {
"text/latex": [
"$\\displaystyle \\begin{array}{l}\n",
"{\\color{blue}{\\text{Codebook:}}}\\\\\n",
"{\\color{blue}{\\;\\;A_{M_0}[i_1], M_0[i_1]\\text{,}\\,\\text{rate = }\\max\\left(I(A_{M_0}; X, Y),\\, -R_1+H(X)+I(A_{M_0}; Y|X)\\right)}}\\\\\n",
"{\\color{blue}{\\;\\;A_{M_0}[i_2], X[i_2], M_1[i_2]\\text{,}\\,\\text{rate = }\\max\\left(I(A_{M_0}; X|Y)+H(A_{M_0}, X),\\, -R_2+H(X)+I(A_{M_0}; Y|X)+H(A_{M_0}, Y)\\right)}}\\\\\n",
"{\\color{blue}{\\;\\;Y[i_3], M_2[i_3]\\text{,}\\,\\text{rate = }\\max\\left(H(Y),\\, -R_0+H(Y)+I(A_{M_0}; X|Y)\\right)}}\\\\\n",
"{\\color{blue}{\\text{Enc}\\,\\text{finds}\\,i_1, i_2, i_3\\text{:}\\,\\left(X, Y\\text{,}A_{M_0}[i_1], M_0[i_1], A_{M_0}[i_2], X[i_2], M_1[i_2], Y[i_3], M_2[i_3]\\right)\\in\\mathcal{T}}}\\\\\n",
"{\\color{blue}{\\text{Dec 1}\\,\\text{finds}\\,i_1, i_2\\text{:}\\,\\left(M_0, M_1\\text{,}A_{M_0}[i_1], M_0[i_1], A_{M_0}[i_2], X[i_2], M_1[i_2]\\right)\\in\\mathcal{T}}}\\\\\n",
"{\\color{blue}{\\text{Dec 2}\\,\\text{finds}\\,i_1, i_3\\text{:}\\,\\left(M_0, M_2\\text{,}A_{M_0}[i_1], M_0[i_1], Y[i_3], M_2[i_3]\\right)\\in\\mathcal{T}}}\\\\\n",
"\\exists A_{M_0}:\\, \\left\\{\\begin{array}{l}\n",
" R_0 \\ge 0,\\\\\n",
" R_1 \\ge 0,\\\\\n",
" R_2 \\ge 0,\\\\\n",
" \\begin{array}{l}\n",
"R_0+R_1 \\ge H(X)+I(A_{M_0}; Y|X)\\\\\n",
"{\\color{blue}{\\;\\;\\;\\;\\left(\\because\\,\\text{enc }X, Y\\text{ to }A_{M_0}, M_0, M_1\\text{,}\\,\\text{dec }M_0, M_1\\text{ to }A_{M_0}, X\\right)}}\n",
"\\end{array},\\\\\n",
" \\begin{array}{l}\n",
"R_0+R_2 \\ge H(Y)+I(A_{M_0}; X|Y)\\\\\n",
"{\\color{blue}{\\;\\;\\;\\;\\left(\\because\\,\\text{enc }X, Y\\text{ to }A_{M_0}, M_0, M_2\\text{,}\\,\\text{dec }M_0, M_2\\text{ to }A_{M_0}, Y\\right)}}\n",
"\\end{array},\\\\\n",
" \\begin{array}{l}\n",
"R_0+R_1+R_2 \\ge H(X)+H(Y|A_{M_0})+I(A_{M_0}; Y|X)\\\\\n",
"{\\color{blue}{\\;\\;\\;\\;\\left(\\because\\,\\text{enc }X, Y\\text{ to }A_{M_0}, M_0, M_1, M_2\\text{,}\\,\\text{dec }M_0, M_1\\text{ to }A_{M_0}, X\\text{,}\\,\\text{dec }M_0, M_2\\text{ to }Y\\right)}}\n",
"\\end{array}\\\\\n",
"\\end{array} \\right\\}\n",
"\\end{array}$"
],
"text/plain": [
""
]
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
"r = model.get_inner(is_proof=True) # Automatic inner bound\n",
"r.display(note=True) # Include reasons in blue"
]
},
{
"cell_type": "code",
"execution_count": 14,
"metadata": {},
"outputs": [
{
"data": {
"text/latex": [
"$\\displaystyle \\begin{array}{l}\n",
"\\mathrm{True}\\\\\n",
"A := A_{M_0}\\\\\n",
"\\end{array}$"
],
"text/plain": [
""
]
},
"metadata": {},
"output_type": "display_data"
},
{
"data": {
"text/latex": [
"$\\displaystyle \\begin{array}{l}\n",
"\\mathrm{True}\\\\\n",
"A_{M_0} := A\\\\\n",
"\\end{array}$"
],
"text/plain": [
""
]
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
"# Although the above region does not look like the Gray-Wyner region,\n",
"# they are actually equivalent.\n",
"\n",
"(r >> r_gw).solve().display() # r implies r_gw\n",
"(r_gw >> r).solve().display() # r_gw implies r"
]
},
{
"cell_type": "code",
"execution_count": 15,
"metadata": {},
"outputs": [
{
"data": {
"text/latex": [
"$\\displaystyle \\begin{align*}\n",
"&1.\\;\\text{Claim:}\\\\\n",
"&\\exists A:\\, \\left\\{\\begin{array}{l}\n",
" R_1 \\ge H(X|A),\\\\\n",
" R_2 \\ge H(Y|A),\\\\\n",
" R_0 \\ge I(A; X, Y)\\\\\n",
"\\end{array} \\right\\}\\\\\n",
"\\\\\n",
"&\\;\\;1.1.\\;\\text{Substitute }A := (X_P, Y_P, M_0)\\text{:}\\\\\n",
"\\\\\n",
"&\\;\\;1.2.\\;\\text{Steps: }\\\\\n",
"&\\;\\;R_1\\\\\n",
"&\\;\\;\\ge I(M_1; X, Y|M_0, 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, M_0)\\right)}}\\\\\n",
"&\\;\\;\\ge I(M_1; X|M_0, X_P, Y_P)\\\\\n",
"&\\;\\;= H(X|M_0, X_P, Y_P)\\;\\;\\;{\\color{blue}{\\left(\\because\\, H(X|Y_P, M_1, M_0, X_P) = 0\\right)}}\\\\\n",
"\\\\\n",
"&\\;\\;1.3.\\;\\text{Steps: }\\\\\n",
"&\\;\\;R_2\\\\\n",
"&\\;\\;\\ge I(M_2; X, Y|M_0, X_P, Y_P)\\;\\;\\;{\\color{blue}{\\left(\\because\\,\\text{rate of }M_2\\text{:}\\, R_2 \\ge I(M_2; X, Y|X_P, Y_P, M_0)\\right)}}\\\\\n",
"&\\;\\;\\ge I(M_2; Y|M_0, X_P, Y_P)\\\\\n",
"&\\;\\;= H(Y|M_0, X_P, Y_P)\\;\\;\\;{\\color{blue}{\\left(\\because\\, H(Y|X_P, M_2, M_0, Y_P) = 0\\right)}}\\\\\n",
"\\\\\n",
"&\\;\\;1.4.\\;\\text{Steps: }\\\\\n",
"&\\;\\;R_0\\\\\n",
"&\\;\\;\\ge I(M_0; X, Y|X_P, Y_P)\\;\\;\\;{\\color{blue}{\\left(\\because\\,\\text{rate of }M_0\\text{:}\\, R_0 \\ge I(M_0; X, Y|X_P, Y_P)\\right)}}\\\\\n",
"&\\;\\;= I(M_0, X_P, Y_P; X, Y)\\;\\;\\;{\\color{blue}{\\left(\\because\\, (X_P, Y_P) {\\perp\\!\\!\\perp} (X, Y)\\right)}}\\\\\n",
"\\end{align*}\n",
"$"
],
"text/plain": [
""
]
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
"# Output converse proof (is_proof = True for shorter proof)\n",
"# Lower search level to avoid modification to regions\n",
"with PsiOpts(auxsearch_level = 1):\n",
" model.proof_outer(r_gw).display()"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Extremal Points and Corner Points"
]
},
{
"cell_type": "code",
"execution_count": 16,
"metadata": {},
"outputs": [
{
"data": {
"text/latex": [
"$H(X, Y)$"
],
"text/plain": [
"H(X+Y)"
]
},
"execution_count": 16,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"# Minimum sum rate is H(X, Y)\n",
"sumrate = r.minimum(R0 + R1 + R2, [R0, R1, R2])\n",
"sumrate"
]
},
{
"cell_type": "code",
"execution_count": 17,
"metadata": {},
"outputs": [
{
"data": {
"text/latex": [
"$H(X)+H(Y)$"
],
"text/plain": [
"H(X)+H(Y)"
]
},
"execution_count": 17,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"# Minimum weighted sum rate when R0 is counted twice is H(X)+H(Y)\n",
"wsumrate = r.minimum(R0 * 2 + R1 + R2, [R0, R1, R2])\n",
"wsumrate"
]
},
{
"cell_type": "code",
"execution_count": 18,
"metadata": {},
"outputs": [
{
"data": {
"text/latex": [
"$\\inf_{A_{M_0}}\\max\\left(\\frac{1}{2}H(X)+\\frac{1}{2}I(A_{M_0}; Y|X),\\, \\frac{1}{2}H(Y)+\\frac{1}{2}I(A_{M_0}; X|Y),\\, \\frac{1}{3}H(X)+\\frac{1}{3}H(Y|A_{M_0})+\\frac{1}{3}I(A_{M_0}; Y|X)\\right)$"
],
"text/plain": [
"(( universe() ).exists(A_M_0)).minimum(emax((1/2)*H(X)+(1/2)*I(A_M_0&Y|X), (1/2)*H(Y)+(1/2)*I(A_M_0&X|Y), (1/3)*H(X)+(1/3)*H(Y|A_M_0)+(1/3)*I(A_M_0&Y|X)))"
]
},
"execution_count": 18,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"# Minimum symmetric rate\n",
"symrate = r.minimum(emax(R0, R1, R2), [R0, R1, R2])\n",
"symrate"
]
},
{
"cell_type": "code",
"execution_count": 19,
"metadata": {},
"outputs": [
{
"data": {
"text/latex": [
"$\\sup_{A_{M_0}:\\, A_{M_0} \\leftrightarrow X \\leftrightarrow Y,\\; A_{M_0} \\leftrightarrow Y \\leftrightarrow X}I(A_{M_0}; Y)$"
],
"text/plain": [
"(( ( markov(A_M_0, X, Y) )\n",
" &( markov(A_M_0, Y, X) ) ).exists(A_M_0)).maximum(I(A_M_0&Y))"
]
},
"execution_count": 19,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"# The corner point max R0 s.t. R0 + R1 = H(X), R0 + R2 = H(Y)\n",
"corner1 = (r & (R0 + R1 == H(X)) & (R0 + R2 == H(Y))).maximum(R0, [R0, R1, R2])\n",
"corner1"
]
},
{
"cell_type": "code",
"execution_count": 20,
"metadata": {},
"outputs": [
{
"data": {
"text/latex": [
"$\\begin{array}{l}\n",
"\\mathrm{True}\\\\\n",
"\\left\\{ \\begin{array}{ll}\n",
"U & := A_1\\\\\n",
"A_{M_0} & := (A_1, U_1)\\end{array}\\right.\\\\\n",
"\\end{array}$"
],
"text/plain": [
"True\n",
"CompArray(\n",
"[[U, A_1],\n",
" [A_M_0, A_1+U_1]])"
]
},
"execution_count": 20,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"# This is the Gacs-Korner common information [Gacs-Korner 1973]\n",
"(corner1 == gacs_korner(X & Y)).solve()"
]
},
{
"cell_type": "code",
"execution_count": 21,
"metadata": {},
"outputs": [
{
"data": {
"text/latex": [
"$\\inf_{A_{M_0}:\\, X \\leftrightarrow A_{M_0} \\leftrightarrow Y}I(A_{M_0}; X, Y)$"
],
"text/plain": [
"(( ( markov(X, A_M_0, Y) ) ).exists(A_M_0)).minimum(I(A_M_0&X+Y))"
]
},
"execution_count": 21,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"# The corner point min R0 s.t. R0 + R1 + R2 = H(X,Y)\n",
"corner2 = (r & (R0 + R1 + R2 == H(X+Y))).minimum(R0, [R0, R1, R2])\n",
"corner2"
]
},
{
"cell_type": "code",
"execution_count": 22,
"metadata": {},
"outputs": [
{
"data": {
"text/latex": [
"$\\begin{array}{l}\n",
"\\mathrm{True}\\\\\n",
"\\left\\{ \\begin{array}{ll}\n",
"A_{M_0} & := U_1\\\\\n",
"U & := A_1\\end{array}\\right.\\\\\n",
"\\end{array}$"
],
"text/plain": [
"True\n",
"CompArray(\n",
"[[A_M_0, U_1],\n",
" [U, A_1]])"
]
},
"execution_count": 22,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"# This is Wyner's common information [Wyner 1975]\n",
"(corner2 == wyner_ci(X & Y)).solve()"
]
},
{
"cell_type": "code",
"execution_count": 23,
"metadata": {},
"outputs": [
{
"data": {
"text/latex": [
"$\\inf_{A_{M_0}:\\, X \\leftrightarrow A_{M_0} \\leftrightarrow Y,\\; A_{M_0} \\leftrightarrow Y \\leftrightarrow X}I(A_{M_0}; Y)$"
],
"text/plain": [
"(( ( markov(X, A_M_0, Y) )\n",
" &( markov(A_M_0, Y, X) ) ).exists(A_M_0)).minimum(I(A_M_0&Y))"
]
},
"execution_count": 23,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"# The corner point min R0 s.t. R0 + R2 = H(Y), R1 = H(X|Y)\n",
"corner3 = (r & (R0 + R2 == H(Y)) & (R1 == H(X|Y))).minimum(R0, [R0, R1, R2])\n",
"corner3"
]
},
{
"cell_type": "code",
"execution_count": 24,
"metadata": {},
"outputs": [
{
"data": {
"text/latex": [
"$\\displaystyle \\begin{array}{l}\n",
"\\mathrm{True}\\\\\n",
"\\left\\{ \\begin{array}{ll}\n",
"A_{M_0} & := U\\\\\n",
"D_X & := U\\\\\n",
"D_Y & := (X, Y)\\\\\n",
"D_Z & := U\\end{array}\\right.\\\\\n",
"\\end{array}$"
],
"text/plain": [
""
]
},
"metadata": {},
"output_type": "display_data"
},
{
"data": {
"text/latex": [
"$\\displaystyle \\begin{array}{l}\n",
"\\mathrm{True}\\\\\n",
"\\left\\{ \\begin{array}{ll}\n",
"U & := D_W\\\\\n",
"D_X & := A_{M_0}\\\\\n",
"D_Y & := Y\\\\\n",
"D_Z & := X\\end{array}\\right.\\\\\n",
"\\end{array}$"
],
"text/plain": [
""
]
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
"# This is the necessary conditional entropy [Cuff-Permuter-Cover 2010] plus I(X;Y)\n",
"# We need the double Markov property [Csiszar-Korner 2011] to prove this\n",
"with dblmarkov().assumed():\n",
" (corner3 <= H_nec(Y | X) + I(X & Y)).solve().display()\n",
" (corner3 >= H_nec(Y | X) + I(X & Y)).solve().display()"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Thm 14.4 (Broadcast Channel)\n",
"\n",
"Skipped"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### References\n",
"- A. El Gamal and Y.-H. Kim, _Network Information Theory_, Cambridge University Press, 2011, Ch. 14.\n",
"- T. Cover, A. El Gamal and M. Salehi, \"Multiple access channels with arbitrarily correlated sources,\" IEEE Transactions on Information theory 26.6, pp. 648-657, 1980.\n",
"- R. M. Gray and A. D. Wyner, \"Source coding for a simple network,\" Bell Syst. Tech. J., vol. 53, no. 9, pp. 1681–1721, 1974.\n",
"- P. Gács and J. Körner, \"Common information is far less than mutual information,\" Problems Control Inf. Theory, vol. 2, no. 2, pp. 149–162, 1973.\n",
"- A. D. Wyner, \"The common information of two dependent random variables,\" IEEE Trans. Inf. Theory, vol. IT-21, no. 2, pp. 163–179, Mar. 1975.\n",
"- P. W. Cuff, H. H. Permuter, and T. M. Cover, \"Coordination capacity,\" IEEE Trans. Inf. Theory, vol. 56, no. 9, pp. 4181–4206, Sep. 2010.\n",
"- C. T. Li and A. El Gamal, \"Extended Gray–Wyner system with complementary causal side information,\" IEEE Trans. Inf. Theory, vol. 64, no. 8, pp. 5862–5878, 2017\n",
"- I. Csiszár and J. Körner, \"Information theory: coding theorems for discrete memoryless systems,\" Cambridge University Press, 2011.\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
}