%3

{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "## Broadcast Channel 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", " solve_display_reg = True, # Display claims in solve commands\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, Z, U, V = rv(\"X, Y, Z, U, V\")\n", "M1, M2 = rv_array(\"M\", 1, 3)\n", "R1, R2 = real_array(\"R\", 1, 3)\n", "\n", "model = CodingModel() # Define broadcast channel\n", "model.set_rate(M1, R1) # Rate of M1 is R1\n", "model.set_rate(M2, R2) # Rate of M2 is R2\n", "model.add_node(M1+M2, X,\n", " label = \"Enc\") # Encoder maps M1,M2 to X\n", "model.add_edge(X, Y) # Channel X -> Y\n", "model.add_edge(X, Z) # Channel X -> Z\n", "model.add_node(Y, M1,\n", " label = \"Dec 1\") # Decoder 1 maps Y to M1\n", "model.add_node(Z, M2,\n", " label = \"Dec 2\") # Decoder 2 maps Z to M2\n", "\n", "model.graph() # Draw diagram" ] }, { "cell_type": "code", "execution_count": 3, "metadata": {}, "outputs": [ { "data": { "text/latex": [ "$\\displaystyle \\exists A_{M_1}, A_{M_2}, A_{M_1, M_2}:\\, \\left\\{\\begin{array}{l}\n", " R_1 \\ge 0,\\\\\n", " R_2 \\ge 0,\\\\\n", " \\begin{array}{l}\n", "R_1 \\le I(A_{M_1, M_2}, A_{M_1}; Y)\\\\\n", "{\\color{blue}{\\;\\;\\;\\;\\left(\\because\\,\\text{enc }M_1, M_2\\text{ to }A_{M_1}, A_{M_1, M_2}\\text{,}\\,\\text{dec }Y\\text{ to }A_{M_1}, M_1\\,\\text{nonuniq }A_{M_1, M_2}\\right)}}\n", "\\end{array},\\\\\n", " \\begin{array}{l}\n", "R_2 \\le I(A_{M_1, M_2}, A_{M_2}; Z)\\\\\n", "{\\color{blue}{\\;\\;\\;\\;\\left(\\because\\,\\text{enc }M_1, M_2\\text{ to }A_{M_2}, A_{M_1, M_2}\\text{,}\\,\\text{dec }Z\\text{ to }A_{M_2}, M_2\\,\\text{nonuniq }A_{M_1, M_2}\\right)}}\n", "\\end{array},\\\\\n", " \\begin{array}{l}\n", "R_1+R_2 \\le I(A_{M_1}; Y|A_{M_1, M_2})+I(A_{M_1, M_2}, A_{M_2}; Z)-I(A_{M_1}; A_{M_2}|A_{M_1, M_2})\\\\\n", "{\\color{blue}{\\;\\;\\;\\;\\left(\\because\\,\\text{enc }M_1, M_2\\text{ to }A_{M_1}, A_{M_2}, A_{M_1, M_2}\\text{,}\\,\\text{dec }Y\\text{ to }A_{M_1}, M_1\\text{,}\\,\\text{dec }Z\\text{ to }A_{M_2}, M_2\\,\\text{nonuniq }A_{M_1, M_2}\\right)}}\n", "\\end{array},\\\\\n", " \\begin{array}{l}\n", "R_1+R_2 \\le I(A_{M_2}; Z|A_{M_1, M_2})+I(A_{M_1, M_2}, A_{M_1}; Y)-I(A_{M_1}; A_{M_2}|A_{M_1, M_2})\\\\\n", "{\\color{blue}{\\;\\;\\;\\;\\left(\\because\\,\\text{enc }M_1, M_2\\text{ to }A_{M_1}, A_{M_2}, A_{M_1, M_2}\\text{,}\\,\\text{dec }Y\\text{ to }A_{M_1}, M_1\\,\\text{nonuniq }A_{M_1, M_2}\\text{,}\\,\\text{dec }Z\\text{ to }A_{M_2}, M_2\\right)}}\n", "\\end{array},\\\\\n", " (A_{M_1, M_2}, A_{M_1}, A_{M_2}) \\leftrightarrow X \\leftrightarrow Y,\\\\\n", " (A_{M_1, M_2}, A_{M_1}, A_{M_2}, Y) \\leftrightarrow X \\leftrightarrow Z\\\\\n", "\\end{array} \\right\\}$" ], "text/plain": [ "" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "# Automatic inner bound, gives 3-auxiliary Marton's inner bound \n", "# [Marton 1979], [Gel'fand-Pinsker 1980], [Liang-Kramer 2007]\n", "r = model.get_inner()\n", "r.display(str_proof_note = True) # Include reasons in blue" ] }, { "cell_type": "code", "execution_count": 4, "metadata": {}, "outputs": [ { "data": { "text/latex": [ "$\\exists U_1, U_2:\\, \\left\\{\\begin{array}{l}\n", " R_1 \\ge 0,\\\\\n", " R_2 \\ge 0,\\\\\n", " R_1 \\le I(U_1; Y),\\\\\n", " R_2 \\le I(U_2; Z),\\\\\n", " R_1+R_2 \\le I(U_1; Y)+I(X; Z|U_1),\\\\\n", " R_1+R_2 \\le I(U_2; Z)+I(X; Y|U_2),\\\\\n", " Y \\leftrightarrow X \\leftrightarrow Z,\\\\\n", " (Y, Z) \\leftrightarrow X \\leftrightarrow (U_1, U_2)\\\\\n", "\\end{array} \\right\\}$" ], "text/plain": [ "( ( R_1 >= 0 )\n", " &( R_2 >= 0 )\n", " &( R_1 <= I(U_1&Y) )\n", " &( R_2 <= I(U_2&Z) )\n", " &( R_1+R_2 <= I(U_1&Y)+I(X&Z|U_1) )\n", " &( R_1+R_2 <= I(U_2&Z)+I(X&Y|U_2) )\n", " &( markov(Y, X, Z) )\n", " &( markov(Y+Z, X, U_1+U_2) ) ).exists(U_1+U_2)" ] }, "execution_count": 4, "metadata": {}, "output_type": "execute_result" } ], "source": [ "# Define UV outer bound [El Gamal 1979], [Nair-El Gamal 2006]\n", "U1, U2 = rv_array(\"U\", 1, 3)\n", "r_uv = alland([\n", " R1 >= 0,\n", " R2 >= 0,\n", " R1 <= I(U1 & Y),\n", " R2 <= I(U2 & Z),\n", " R1+R2 <= I(U1 & Y) + I(X & Z | U1),\n", " R1+R2 <= I(U2 & Z) + I(X & Y | U2),\n", " markov(U1+U2, X, Y+Z),\n", " markov(Y, X, Z)\n", "]).exists(U1+U2)\n", "r_uv" ] }, { "cell_type": "code", "execution_count": 5, "metadata": {}, "outputs": [ { "data": { "text/latex": [ "$\\left\\{ \\begin{array}{ll}\n", "U_1 & := (Y_F, Z_P, M_1)\\\\\n", "U_2 & := (Y_F, Z_P, M_2)\\end{array}\\right.$" ], "text/plain": [ "CompArray(\n", "[[U_1, Y_F+Z_P+M_1],\n", " [U_2, Y_F+Z_P+M_2]])" ] }, "execution_count": 5, "metadata": {}, "output_type": "execute_result" } ], "source": [ "r_out = model.get_outer() # Get outer bound\n", "# Prove UV outer bound and output auxiliaries for proof\n", "(r_out >> r_uv).check_getaux_array()" ] }, { "cell_type": "code", "execution_count": 6, "metadata": {}, "outputs": [ { "data": { "text/latex": [ "$\\begin{align*}\n", "&1.\\;\\text{Claim:}\\\\\n", "&\\exists U_1, U_2:\\, \\left\\{\\begin{array}{l}\n", " R_1 \\ge 0,\\\\\n", " R_2 \\ge 0,\\\\\n", " R_1 \\le I(U_1; Y),\\\\\n", " R_2 \\le I(U_2; Z),\\\\\n", " R_1+R_2 \\le I(U_1; Y)+I(X; Z|U_1),\\\\\n", " R_1+R_2 \\le I(U_2; Z)+I(X; Y|U_2),\\\\\n", " Y \\leftrightarrow X \\leftrightarrow Z,\\\\\n", " (Y, Z) \\leftrightarrow X \\leftrightarrow (U_1, U_2)\\\\\n", "\\end{array} \\right\\}\\\\\n", "\\\\\n", "&\\;\\;1.1.\\;\\text{Substitute }\\left\\{ \\begin{array}{ll}\n", "U_1 & := (Y_F, Z_P, M_1)\\\\\n", "U_2 & := (Y_F, Z_P, M_2)\\end{array}\\right.\\text{:}\\\\\n", "\\\\\n", "&\\;\\;1.2.\\;\\text{Steps: }\\\\\n", "&\\;\\;R_1\\\\\n", "&\\;\\;\\le I(M_1; Y|Y_F)\\;\\;\\;{\\color{blue}{\\left(\\because\\,\\text{decode }M_1\\text{:}\\, R_1 \\le I(M_1; Y|Y_F)\\right)}}\\\\\n", "&\\;\\;\\le I(M_1, Y_F; Y)\\\\\n", "&\\;\\;\\le I(M_1, Y_F, Z_P; Y)\\\\\n", "\\\\\n", "&\\;\\;1.3.\\;\\text{Steps: }\\\\\n", "&\\;\\;R_2\\\\\n", "&\\;\\;\\le I(M_2; Z|Z_P)\\;\\;\\;{\\color{blue}{\\left(\\because\\,\\text{decode }M_2\\text{:}\\, R_2 \\le I(M_2; Z|Z_P)\\right)}}\\\\\n", "&\\;\\;\\le I(M_2, Z_P; Z)\\\\\n", "&\\;\\;\\le I(M_2, Y_F, Z_P; Z)\\\\\n", "\\\\\n", "&\\;\\;1.4.\\;\\text{Steps: }\\\\\n", "&\\;\\;R_1+R_2\\\\\n", "&\\;\\;\\le R_2+I(M_1; Y|Y_F)\\;\\;\\;{\\color{blue}{\\left(\\because\\,\\text{decode }M_1\\text{:}\\, R_1 \\le I(M_1; Y|Y_F)\\right)}}\\\\\n", "&\\;\\;\\le I(M_1; Y|Y_F)+I(M_2; Z|Z_P)\\;\\;\\;{\\color{blue}{\\left(\\because\\,\\text{decode }M_2\\text{:}\\, R_2 \\le I(M_2; Z|Z_P)\\right)}}\\\\\n", "&\\;\\;\\le I(M_1; Y|Y_F)+I(M_2; Z|M_1, Z_P)\\;\\;\\;{\\color{blue}{\\left(\\because\\,\\text{indep. of msgs }M_2\\text{, }M_1\\text{:}\\, I(M_2; Z; M_1|Z_P) \\le 0\\right)}}\\\\\n", "&\\;\\;\\le I(M_1, Y_F; Y)+I(M_2; Z|M_1, Z_P)\\\\\n", "&\\;\\;= I(M_1, M_2, Z_P; Z)+I(M_1, Y_F, Z_P; Y)-I(M_1, Y_F, Z_P; Z)\\\\\n", "&\\;\\;\\;\\;\\;\\;\\;\\;\\;\\;{\\color{blue}{\\left(\\because\\,\\text{Csiszar sum}\\text{:}\\, I(Z_P; Y|Y_F, M_1) = I(Y_F; Z|Z_P, M_1)\\right)}}\\\\\n", "&\\;\\;\\le I(M_1, Y_F, Z_P; Y)+I(M_1, M_2, Y_P, Z_P; Z)-I(M_1, Y_F, Z_P; Z)\\\\\n", "&\\;\\;= I(M_1, M_2, Y_P; Z)+I(M_1, Y_F, Z_P; Y)-I(M_1, Y_F, Z_P; Z)\\;\\;\\;{\\color{blue}{\\left(\\because\\, Z \\leftrightarrow (M_1, M_2, Y_P) \\leftrightarrow Z_P\\right)}}\\\\\n", "&\\;\\;\\le I(M_1, Y_F, Z_P; Y)+I(M_1, M_2, Y, Y_P; Z)-I(M_1, Y_F, Z_P; Z)\\\\\n", "&\\;\\;= I(M_1, Y_F, Z_P; Y)+I(M_2, X, Y, Y_P; Z|M_1, Y_F, Z_P)\\\\\n", "&\\;\\;\\;\\;\\;\\;\\;\\;\\;\\;{\\color{blue}{\\left(\\because\\, (Y_F, Z_P, X) \\leftrightarrow (M_1, M_2, Y_P, Y) \\leftrightarrow Z\\right)}}\\\\\n", "&\\;\\;= I(X; Z|M_1, Y_F, Z_P)+I(M_1, Y_F, Z_P; Y)-I(M_1, Y_F, Z_P; Z|X)\\\\\n", "&\\;\\;\\;\\;\\;\\;\\;\\;\\;\\;{\\color{blue}{\\left(\\because\\, (M_1, Y, Y_P, M_2, Y_F, Z_P) \\leftrightarrow X \\leftrightarrow Z\\right)}}\\\\\n", "&\\;\\;= I(X; Z|M_1, Y_F, Z_P)+I(M_1, Y_F, Z_P; Y)\\;\\;\\;{\\color{blue}{\\left(\\because\\, (M_1, Y_F, Z_P) \\leftrightarrow X \\leftrightarrow Z\\right)}}\\\\\n", "\\\\\n", "&\\;\\;1.5.\\;\\text{Steps: }\\\\\n", "&\\;\\;R_1+R_2\\\\\n", "&\\;\\;\\le R_2+I(M_1; Y|Y_F)\\;\\;\\;{\\color{blue}{\\left(\\because\\,\\text{decode }M_1\\text{:}\\, R_1 \\le I(M_1; Y|Y_F)\\right)}}\\\\\n", "&\\;\\;\\le I(M_1; Y|Y_F)+I(M_2; Z|Z_P)\\;\\;\\;{\\color{blue}{\\left(\\because\\,\\text{decode }M_2\\text{:}\\, R_2 \\le I(M_2; Z|Z_P)\\right)}}\\\\\n", "&\\;\\;\\le I(M_2; Z|Z_P)+I(M_1; Y|M_2, Y_F)\\;\\;\\;{\\color{blue}{\\left(\\because\\,\\text{indep. of msgs }M_1\\text{, }M_2\\text{:}\\, I(M_1; Y; M_2|Y_F) \\le 0\\right)}}\\\\\n", "&\\;\\;\\le I(M_1; Y|M_2, Y_F)+I(M_2, Z_P; Z)\\\\\n", "&\\;\\;= I(M_1, M_2, Y_F; Y)+I(M_2, Y_F, Z_P; Z)-I(M_2, Y_F, Z_P; Y)\\\\\n", "&\\;\\;\\;\\;\\;\\;\\;\\;\\;\\;{\\color{blue}{\\left(\\because\\,\\text{Csiszar sum}\\text{:}\\, I(Y_F; Z|Z_P, M_2) = I(Z_P; Y|Y_F, M_2)\\right)}}\\\\\n", "&\\;\\;= I(M_2, Y_F, Z_P; Z)+I(M_1, M_2, X, Y_F; Y)-I(M_2, Y_F, Z_P; Y)\\;\\;\\;{\\color{blue}{\\left(\\because\\, X \\leftrightarrow (M_1, M_2, Y_F) \\leftrightarrow Y\\right)}}\\\\\n", "&\\;\\;= I(X; Y|M_2, Y_F, Z_P)+I(M_2, Y_F, Z_P; Z)-I(M_2, Y_F, Z_P; Y|X)\\\\\n", "&\\;\\;\\;\\;\\;\\;\\;\\;\\;\\;{\\color{blue}{\\left(\\because\\, (M_1, M_2, Y_F) \\leftrightarrow X \\leftrightarrow Y\\right)}}\\\\\n", "&\\;\\;= I(X; Y|M_2, Y_F, Z_P)+I(M_2, Y_F, Z_P; Z)\\;\\;\\;{\\color{blue}{\\left(\\because\\, (M_2, Y_F, Z_P) \\leftrightarrow X \\leftrightarrow Y\\right)}}\\\\\n", "\\end{align*}\n", "$" ], "text/plain": [ "" ] }, "execution_count": 6, "metadata": {}, "output_type": "execute_result" } ], "source": [ "# Output proof of UV outer bound (is_proof = True for shorter proof)\n", "(model.get_outer(is_proof = True) >> r_uv).proof()" ] }, { "cell_type": "code", "execution_count": 7, "metadata": {}, "outputs": [], "source": [ "C = model.maximum(R1 + R2, [R1, R2], name = \"C\") # Get sum capacity" ] }, { "cell_type": "code", "execution_count": 8, "metadata": {}, "outputs": [ { "data": { "text/latex": [ "$\\displaystyle \\begin{array}{l}\n", "\\displaystyle Z \\leftrightarrow X \\leftrightarrow Y\\\\\n", "\\displaystyle \\Rightarrow \\; \\max\\left(I(X; Y),\\, I(X; Z)\\right) \\le C\\\\\n", "\\end{array} \\;\\mathrm{is}\\;\\mathrm{True}$" ], "text/plain": [ "" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "# Lower bound C >= max(I(X;Y), I(X;Z))\n", "# model.get_region() gives markov(Y,X,Z), needed since it is an assumption in C\n", "(model.get_region() >> (C >= emax(I(X & Y), I(X & Z)))).display_bool()" ] }, { "cell_type": "code", "execution_count": 9, "metadata": {}, "outputs": [ { "data": { "text/latex": [ "$\\displaystyle \\begin{array}{l}\n", "\\displaystyle Z \\leftrightarrow X \\leftrightarrow Y\\\\\n", "\\displaystyle \\Rightarrow \\; C \\le I(X; Y, Z)\\\\\n", "\\end{array} \\;\\mathrm{is}\\;\\mathrm{True}$" ], "text/plain": [ "" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "# Upper bound C <= I(X & Y+Z)\n", "(model.get_region() >> (C <= I(X & Y+Z))).display_bool()" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Less Noisy and More Capable" ] }, { "cell_type": "code", "execution_count": 10, "metadata": {}, "outputs": [ { "data": { "text/latex": [ "$\\displaystyle \\exists A_{M_1}, A_{M_2}, A_{M_1, M_2}:\\, \\left\\{\\begin{array}{l}\n", " R_1 \\ge 0,\\\\\n", " R_2 \\ge 0,\\\\\n", " \\begin{array}{l}\n", "R_1 \\le I(A_{M_1, M_2}, A_{M_1}; Y)\\\\\n", "{\\color{blue}{\\;\\;\\;\\;\\left(\\because\\,\\text{enc }M_1, M_2\\text{ to }A_{M_1}, A_{M_1, M_2}\\text{,}\\,\\text{dec }Y\\text{ to }A_{M_1}, M_1\\,\\text{nonuniq }A_{M_1, M_2}\\right)}}\n", "\\end{array},\\\\\n", " \\begin{array}{l}\n", "R_2 \\le I(A_{M_1, M_2}, A_{M_2}; Z)\\\\\n", "{\\color{blue}{\\;\\;\\;\\;\\left(\\because\\,\\text{enc }M_1, M_2\\text{ to }A_{M_2}, A_{M_1, M_2}\\text{,}\\,\\text{dec }Z\\text{ to }A_{M_2}, M_2\\,\\text{nonuniq }A_{M_1, M_2}\\right)}}\n", "\\end{array},\\\\\n", " \\begin{array}{l}\n", "R_1+R_2 \\le I(A_{M_1}; Y|A_{M_1, M_2})+I(A_{M_1, M_2}, A_{M_2}; Z)-I(A_{M_1}; A_{M_2}|A_{M_1, M_2})\\\\\n", "{\\color{blue}{\\;\\;\\;\\;\\left(\\because\\,\\text{enc }M_1, M_2\\text{ to }A_{M_1}, A_{M_2}, A_{M_1, M_2}\\text{,}\\,\\text{dec }Y\\text{ to }A_{M_1}, M_1\\text{,}\\,\\text{dec }Z\\text{ to }A_{M_2}, M_2\\,\\text{nonuniq }A_{M_1, M_2}\\right)}}\n", "\\end{array},\\\\\n", " \\begin{array}{l}\n", "R_1+R_2 \\le I(A_{M_2}; Z|A_{M_1, M_2})+I(A_{M_1, M_2}, A_{M_1}; Y)-I(A_{M_1}; A_{M_2}|A_{M_1, M_2})\\\\\n", "{\\color{blue}{\\;\\;\\;\\;\\left(\\because\\,\\text{enc }M_1, M_2\\text{ to }A_{M_1}, A_{M_2}, A_{M_1, M_2}\\text{,}\\,\\text{dec }Y\\text{ to }A_{M_1}, M_1\\,\\text{nonuniq }A_{M_1, M_2}\\text{,}\\,\\text{dec }Z\\text{ to }A_{M_2}, M_2\\right)}}\n", "\\end{array},\\\\\n", " \\begin{array}{l}\n", "I(X; Z) \\le I(X; Y)\\\\\n", "{\\color{blue}{\\;\\;\\;\\;\\left(\\because\\,\\text{more capable}\\right)}}\n", "\\end{array},\\\\\n", " \\begin{array}{l}\n", "I(X; Z|A_{M_1}) \\le I(X; Y|A_{M_1})\\\\\n", "{\\color{blue}{\\;\\;\\;\\;\\left(\\because\\,\\text{more capable}\\right)}}\n", "\\end{array},\\\\\n", " \\begin{array}{l}\n", "I(X; Z|A_{M_1, M_2}) \\le I(X; Y|A_{M_1, M_2})\\\\\n", "{\\color{blue}{\\;\\;\\;\\;\\left(\\because\\,\\text{more capable}\\right)}}\n", "\\end{array},\\\\\n", " \\begin{array}{l}\n", "I(X; Z|A_{M_2}) \\le I(X; Y|A_{M_2})\\\\\n", "{\\color{blue}{\\;\\;\\;\\;\\left(\\because\\,\\text{more capable}\\right)}}\n", "\\end{array},\\\\\n", " \\begin{array}{l}\n", "I(X; Z|A_{M_1, M_2}, A_{M_1}) \\le I(X; Y|A_{M_1, M_2}, A_{M_1})\\\\\n", "{\\color{blue}{\\;\\;\\;\\;\\left(\\because\\,\\text{more capable}\\right)}}\n", "\\end{array},\\\\\n", " \\begin{array}{l}\n", "I(X; Z|A_{M_1, M_2}, A_{M_2}) \\le I(X; Y|A_{M_1, M_2}, A_{M_2})\\\\\n", "{\\color{blue}{\\;\\;\\;\\;\\left(\\because\\,\\text{more capable}\\right)}}\n", "\\end{array},\\\\\n", " \\begin{array}{l}\n", "I(X; Z|A_{M_1}, A_{M_2}) \\le I(X; Y|A_{M_1}, A_{M_2})\\\\\n", "{\\color{blue}{\\;\\;\\;\\;\\left(\\because\\,\\text{more capable}\\right)}}\n", "\\end{array},\\\\\n", " \\begin{array}{l}\n", "I(X; Z|A_{M_1, M_2}, A_{M_1}, A_{M_2}) \\le I(X; Y|A_{M_1, M_2}, A_{M_1}, A_{M_2})\\\\\n", "{\\color{blue}{\\;\\;\\;\\;\\left(\\because\\,\\text{more capable}\\right)}}\n", "\\end{array},\\\\\n", " (A_{M_1, M_2}, A_{M_1}, A_{M_2}) \\leftrightarrow X \\leftrightarrow Y,\\\\\n", " (A_{M_1, M_2}, A_{M_1}, A_{M_2}, Y) \\leftrightarrow X \\leftrightarrow Z\\\\\n", "\\end{array} \\right\\}$" ], "text/plain": [ "" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "# More capable BC [Körner-Marton 1975], [El Gamal 1979]\n", "mc = (markov(V, X, Y+Z) >> (I(X & Y | V) >= I(X & Z | V))).forall(V)\n", "mc.add_meta(\"pf_note\", [\"more capable\"]) # Add a note to the proof\n", "model.reg = mc\n", "\n", "# For less noisy BC [Körner-Marton 1975], use:\n", "# model.reg = (markov(U+V, X, Y+Z) >> (I(U & Y | V) >= I(U & Z | V))).forall(U+V)\n", "\n", "r_mc = model.get_inner() # Give superposition region [Bergmans 1973], [Gallager 1974]\n", "r_mc.display(str_proof_note = True) # Include reasons in blue" ] }, { "cell_type": "code", "execution_count": 11, "metadata": {}, "outputs": [ { "data": { "text/latex": [ "$\\begin{align*}\n", "&1.\\;\\text{Claim:}\\\\\n", "&\\exists A_{M_1}, A_{M_2}, A_{M_1, M_2}:\\, \\left\\{\\begin{array}{l}\n", " R_1 \\ge 0,\\\\\n", " R_2 \\ge 0,\\\\\n", " R_1 \\le I(A_{M_1, M_2}, A_{M_1}; Y),\\\\\n", " R_2 \\le I(A_{M_1, M_2}, A_{M_2}; Z),\\\\\n", " R_1+R_2 \\le I(A_{M_1}; Y|A_{M_1, M_2})+I(A_{M_1, M_2}, A_{M_2}; Z)-I(A_{M_1}; A_{M_2}|A_{M_1, M_2}),\\\\\n", " R_1+R_2 \\le I(A_{M_2}; Z|A_{M_1, M_2})+I(A_{M_1, M_2}, A_{M_1}; Y)-I(A_{M_1}; A_{M_2}|A_{M_1, M_2}),\\\\\n", " I(X; Z) \\le I(X; Y),\\\\\n", " I(X; Z|A_{M_1}) \\le I(X; Y|A_{M_1}),\\\\\n", " I(X; Z|A_{M_1, M_2}) \\le I(X; Y|A_{M_1, M_2}),\\\\\n", " I(X; Z|A_{M_2}) \\le I(X; Y|A_{M_2}),\\\\\n", " I(X; Z|A_{M_1, M_2}, A_{M_1}) \\le I(X; Y|A_{M_1, M_2}, A_{M_1}),\\\\\n", " I(X; Z|A_{M_1, M_2}, A_{M_2}) \\le I(X; Y|A_{M_1, M_2}, A_{M_2}),\\\\\n", " I(X; Z|A_{M_1}, A_{M_2}) \\le I(X; Y|A_{M_1}, A_{M_2}),\\\\\n", " I(X; Z|A_{M_1, M_2}, A_{M_1}, A_{M_2}) \\le I(X; Y|A_{M_1, M_2}, A_{M_1}, A_{M_2}),\\\\\n", " (A_{M_1, M_2}, A_{M_1}, A_{M_2}) \\leftrightarrow X \\leftrightarrow Y,\\\\\n", " (A_{M_1, M_2}, A_{M_1}, A_{M_2}, Y) \\leftrightarrow X \\leftrightarrow Z\\\\\n", "\\end{array} \\right\\}\\\\\n", "\\\\\n", "&\\;\\;1.1.\\;\\text{Substitute }\\left\\{ \\begin{array}{ll}\n", "A_{M_1} & := X\\\\\n", "A_{M_2} & := M_2\\\\\n", "A_{M_1, M_2} & := (Y_F, Z_P, M_2)\\end{array}\\right.\\text{:}\\\\\n", "\\\\\n", "&\\;\\;1.2.\\;\\text{Steps: }\\\\\n", "&\\;\\;R_1\\\\\n", "&\\;\\;\\le I(M_1; Y|Y_P)\\;\\;\\;{\\color{blue}{\\left(\\because\\,\\text{decode }M_1\\text{:}\\, R_1 \\le I(M_1; Y|Y_P)\\right)}}\\\\\n", "&\\;\\;\\le I(M_1, Y_P; Y)\\\\\n", "&\\;\\;\\le I(M_1, X, Y_P; Y)\\\\\n", "&\\;\\;= I(X; Y)\\;\\;\\;{\\color{blue}{\\left(\\because\\, (M_1, Y_P) \\leftrightarrow X \\leftrightarrow Y\\right)}}\\\\\n", "&\\;\\;= I(M_2, X, Y_F, Z_P; Y)\\;\\;\\;{\\color{blue}{\\left(\\because\\, (M_2, Y_F, Z_P) \\leftrightarrow X \\leftrightarrow Y\\right)}}\\\\\n", "\\\\\n", "&\\;\\;1.3.\\;\\text{Steps: }\\\\\n", "&\\;\\;R_2\\\\\n", "&\\;\\;\\le I(M_2; Z|Z_P)\\;\\;\\;{\\color{blue}{\\left(\\because\\,\\text{decode }M_2\\text{:}\\, R_2 \\le I(M_2; Z|Z_P)\\right)}}\\\\\n", "&\\;\\;\\le I(M_2, Z_P; Z)\\\\\n", "&\\;\\;\\le I(M_2, Y_F, Z_P; Z)\\\\\n", "\\\\\n", "&\\;\\;1.4.\\;\\text{Steps: }\\\\\n", "&\\;\\;R_1+R_2\\\\\n", "&\\;\\;\\le R_2+I(M_1; Y|Y_F)\\;\\;\\;{\\color{blue}{\\left(\\because\\,\\text{decode }M_1\\text{:}\\, R_1 \\le I(M_1; Y|Y_F)\\right)}}\\\\\n", "&\\;\\;\\le I(M_1; Y|Y_F)+I(M_2; Z|Z_P)\\;\\;\\;{\\color{blue}{\\left(\\because\\,\\text{decode }M_2\\text{:}\\, R_2 \\le I(M_2; Z|Z_P)\\right)}}\\\\\n", "&\\;\\;\\le I(M_2; Z|Z_P)+I(M_1; Y|M_2, Y_F)\\;\\;\\;{\\color{blue}{\\left(\\because\\,\\text{indep. of msgs }M_1\\text{, }M_2\\text{:}\\, I(M_1; Y; M_2|Y_F) \\le 0\\right)}}\\\\\n", "&\\;\\;\\le I(M_1; Y|M_2, Y_F)+I(M_2, Z_P; Z)\\\\\n", "&\\;\\;= I(M_1, M_2, Y_F; Y)+I(M_2, Y_F, Z_P; Z)-I(M_2, Y_F, Z_P; Y)\\\\\n", "&\\;\\;\\;\\;\\;\\;\\;\\;\\;\\;{\\color{blue}{\\left(\\because\\,\\text{Csiszar sum}\\text{:}\\, I(Y_F; Z|Z_P, M_2) = I(Z_P; Y|Y_F, M_2)\\right)}}\\\\\n", "&\\;\\;= I(M_2, Y_F, Z_P; Z)+I(M_1, M_2, X, Y_F; Y)-I(M_2, Y_F, Z_P; Y)\\;\\;\\;{\\color{blue}{\\left(\\because\\, X \\leftrightarrow (M_2, M_1, Y_F) \\leftrightarrow Y\\right)}}\\\\\n", "&\\;\\;= I(X; Y|M_2, Y_F, Z_P)+I(M_2, Y_F, Z_P; Z)-I(M_2, Y_F, Z_P; Y|X)\\\\\n", "&\\;\\;\\;\\;\\;\\;\\;\\;\\;\\;{\\color{blue}{\\left(\\because\\, (M_1, M_2, Y_F) \\leftrightarrow X \\leftrightarrow Y\\right)}}\\\\\n", "&\\;\\;= I(X; Y|M_2, Y_F, Z_P)+I(M_2, Y_F, Z_P; Z)\\;\\;\\;{\\color{blue}{\\left(\\because\\, (M_2, Y_F, Z_P) \\leftrightarrow X \\leftrightarrow Y\\right)}}\\\\\n", "\\\\\n", "&\\;\\;1.5.\\;\\text{Steps: }\\\\\n", "&\\;\\;R_1+R_2\\\\\n", "&\\;\\;\\le R_2+I(M_1; Y|Y_F)\\;\\;\\;{\\color{blue}{\\left(\\because\\,\\text{decode }M_1\\text{:}\\, R_1 \\le I(M_1; Y|Y_F)\\right)}}\\\\\n", "&\\;\\;\\le I(M_1; Y|Y_F)+I(M_2; Z|Z_P)\\;\\;\\;{\\color{blue}{\\left(\\because\\,\\text{decode }M_2\\text{:}\\, R_2 \\le I(M_2; Z|Z_P)\\right)}}\\\\\n", "&\\;\\;\\le I(M_1; Y|Y_F)+I(M_2; Z|M_1, Z_P)\\;\\;\\;{\\color{blue}{\\left(\\because\\,\\text{indep. of msgs }M_2\\text{, }M_1\\text{:}\\, I(M_2; Z; M_1|Z_P) \\le 0\\right)}}\\\\\n", "&\\;\\;\\le I(M_1, Y_F; Y)+I(M_2; Z|M_1, Z_P)\\\\\n", "&\\;\\;= H(M_1, Y_F, Z, Z_P)-H(Z|M_1, M_2, Z_P)-H(M_1, Y_F, Z_P|Y)\\\\\n", "&\\;\\;\\;\\;\\;\\;\\;\\;\\;\\;{\\color{blue}{\\left(\\because\\,\\text{Csiszar sum}\\text{:}\\, I(Z_P; Y|Y_F, M_1) = I(Y_F; Z|Z_P, M_1)\\right)}}\\\\\n", "&\\;\\;\\le H(M_1, Y_F, Z, Z_P)-H(Z|M_1, M_2, Y_P, Z_P)-H(M_1, Y_F, Z_P|Y)\\\\\n", "&\\;\\;= H(M_1, Y_F, Z, Z_P)-H(Z|M_1, M_2, Y_P)-H(M_1, Y_F, Z_P|Y)\\;\\;\\;{\\color{blue}{\\left(\\because\\, Z \\leftrightarrow (M_2, M_1, Y_P) \\leftrightarrow Z_P\\right)}}\\\\\n", "&\\;\\;\\le H(M_1, Y_F, Z, Z_P)-H(Z|M_1, M_2, Y, Y_P)-H(M_1, Y_F, Z_P|Y)\\\\\n", "&\\;\\;= I(M_1, Y_F, Z, Z_P; M_2, X, Y, Y_P)-I(M_1, Y_F, Z_P; M_2, X, Y_P|Y)\\\\\n", "&\\;\\;\\;\\;\\;\\;\\;\\;\\;\\;{\\color{blue}{\\left(\\because\\, (Y_F, Z_P, X) \\leftrightarrow (M_2, M_1, Y_P, Y) \\leftrightarrow Z\\right)}}\\\\\n", "&\\;\\;= I(X; Z)+H(M_1, Y_F, Z_P|Z)-H(M_1, Y_F, Z_P|Y)\\;\\;\\;{\\color{blue}{\\left(\\because\\, (M_1, Y, Y_P, M_2, Y_F, Z_P) \\leftrightarrow X \\leftrightarrow Z\\right)}}\\\\\n", "&\\;\\;= I(X; Z)+I(M_1, Y_F, Z_P; X; Y)-I(M_1, Y_F, Z_P; Z)\\;\\;\\;{\\color{blue}{\\left(\\because\\, (M_1, Y_F, Z_P) \\leftrightarrow X \\leftrightarrow Y\\right)}}\\\\\n", "&\\;\\;= I(M_1, Y_F, Z, Z_P; X)-I(M_1, Y_F, Z_P; X|Y)\\;\\;\\;{\\color{blue}{\\left(\\because\\, (M_1, Y_F, Z_P) \\leftrightarrow X \\leftrightarrow Z\\right)}}\\\\\n", "&\\;\\;\\le I(X; Y)\\;\\;\\;{\\color{blue}{\\left(\\because\\,\\text{more capable}\\text{:}\\, I(X; Z|M_1, Y_F, Z_P) \\le I(X; Y|M_1, Y_F, Z_P)\\right)}}\\\\\n", "&\\;\\;= I(M_2, X, Y_F, Z_P; Y)\\;\\;\\;{\\color{blue}{\\left(\\because\\, (M_2, Y_F, Z_P) \\leftrightarrow X \\leftrightarrow Y\\right)}}\\\\\n", "\\end{align*}\n", "$" ], "text/plain": [ "" ] }, "execution_count": 11, "metadata": {}, "output_type": "execute_result" } ], "source": [ "# Output proof of tightness (is_proof = True for shorter proof)\n", "(model.get_outer(is_proof = True) >> r_mc).proof()" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Degraded Message Sets" ] }, { "cell_type": "code", "execution_count": 12, "metadata": {}, "outputs": [ { "data": { "image/svg+xml": [ "\r\n", "\r\n", "\r\n", "\r\n", "\r\n" ], "text/plain": [ "" ] }, "execution_count": 12, "metadata": {}, "output_type": "execute_result" } ], "source": [ "M0, M1 = rv_array(\"M\", 2)\n", "R0, R1 = real_array(\"R\", 2)\n", "\n", "model = CodingModel() # Degraded message set\n", "model.set_rate(M0, R0) # Rate of M0 is R0\n", "model.set_rate(M1, R1) # Rate of M1 is R1\n", "model.add_node(M0+M1, X,\n", " label = \"Enc\") # Encoder maps M1,M2 to X\n", "model.add_edge(X, Y) # Channel X -> Y\n", "model.add_edge(X, Z) # Channel X -> Z\n", "model.add_node(Y, M0+M1,\n", " label = \"Dec 1\") # Decoder 1 maps Y to M0,M1\n", "model.add_node(Z, M0,\n", " label = \"Dec 2\") # Decoder 2 maps Z to M0\n", "\n", "model.graph() # Draw diagram" ] }, { "cell_type": "code", "execution_count": 13, "metadata": {}, "outputs": [ { "data": { "text/latex": [ "$\\displaystyle \\exists A_{M_0}:\\, \\left\\{\\begin{array}{l}\n", " R_0 \\ge 0,\\\\\n", " R_1 \\ge 0,\\\\\n", " \\begin{array}{l}\n", "R_0 \\le I(A_{M_0}; Z)\\\\\n", "{\\color{blue}{\\;\\;\\;\\;\\left(\\because\\,\\text{enc }M_0, M_1\\text{ to }A_{M_0}\\text{,}\\,\\text{dec }Z\\text{ to }A_{M_0}, M_0\\right)}}\n", "\\end{array},\\\\\n", " \\begin{array}{l}\n", "R_0+R_1 \\le I(X; Y)\\\\\n", "{\\color{blue}{\\;\\;\\;\\;\\left(\\because\\,\\text{enc }M_0, M_1\\text{ to }A_{M_0}, X\\text{,}\\,\\text{dec }Y\\text{ to }A_{M_0}, M_0, X, M_1\\right)}}\n", "\\end{array},\\\\\n", " \\begin{array}{l}\n", "R_0+R_1 \\le I(A_{M_0}; Z)+I(X; Y|A_{M_0})\\\\\n", "{\\color{blue}{\\;\\;\\;\\;\\left(\\because\\,\\text{enc }M_0, M_1\\text{ to }A_{M_0}, X\\text{,}\\,\\text{dec }Z\\text{ to }A_{M_0}, M_0\\text{,}\\,\\text{dec }Y\\text{ to }X, M_1\\right)}}\n", "\\end{array},\\\\\n", " A_{M_0} \\leftrightarrow X \\leftrightarrow Y,\\\\\n", " (A_{M_0}, Y) \\leftrightarrow X \\leftrightarrow Z\\\\\n", "\\end{array} \\right\\}$" ], "text/plain": [ "" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "r = model.get_inner() # Give superposition region [Bergmans 1973], [Gallager 1974]\n", "r.display(str_proof_note = True) # Include reasons in blue" ] }, { "cell_type": "code", "execution_count": 14, "metadata": {}, "outputs": [ { "data": { "text/latex": [ "$A_{M_0} := (Y_F, Z_P, M_0)$" ], "text/plain": [ "CompArray(\n", "[[A_M_0, Y_F+Z_P+M_0]])" ] }, "execution_count": 14, "metadata": {}, "output_type": "execute_result" } ], "source": [ "r_out = model.get_outer() # Get outer bound\n", "(r_out >> r).check_getaux_array() # Check tightness" ] }, { "cell_type": "code", "execution_count": 15, "metadata": {}, "outputs": [ { "data": { "text/latex": [ "$\\begin{align*}\n", "&1.\\;\\text{Claim:}\\\\\n", "&\\exists A_{M_0}:\\, \\left\\{\\begin{array}{l}\n", " R_0 \\ge 0,\\\\\n", " R_1 \\ge 0,\\\\\n", " R_0 \\le I(A_{M_0}; Z),\\\\\n", " R_0+R_1 \\le I(X; Y),\\\\\n", " R_0+R_1 \\le I(A_{M_0}; Z)+I(X; Y|A_{M_0}),\\\\\n", " A_{M_0} \\leftrightarrow X \\leftrightarrow Y,\\\\\n", " (A_{M_0}, Y) \\leftrightarrow X \\leftrightarrow Z\\\\\n", "\\end{array} \\right\\}\\\\\n", "\\\\\n", "&\\;\\;1.1.\\;\\text{Substitute }A_{M_0} := (Y_F, Z_P, M_0)\\text{:}\\\\\n", "\\\\\n", "&\\;\\;1.2.\\;\\text{Steps: }\\\\\n", "&\\;\\;R_0\\\\\n", "&\\;\\;\\le I(M_0; Z|Z_P)\\;\\;\\;{\\color{blue}{\\left(\\because\\,\\text{decode }M_0\\text{:}\\, R_0 \\le I(M_0; Z|Z_P)\\right)}}\\\\\n", "&\\;\\;\\le I(M_0, Z_P; Z)\\\\\n", "&\\;\\;\\le I(M_0, Y_F, Z_P; Z)\\\\\n", "\\\\\n", "&\\;\\;1.3.\\;\\text{Steps: }\\\\\n", "&\\;\\;R_0+R_1\\\\\n", "&\\;\\;\\le R_1+I(M_0; Y|Y_F)\\;\\;\\;{\\color{blue}{\\left(\\because\\,\\text{decode }M_0\\text{:}\\, R_0 \\le I(M_0; Y|Y_F)\\right)}}\\\\\n", "&\\;\\;\\le I(M_0; Y|Y_F)+I(M_1; Y|Y_F)\\;\\;\\;{\\color{blue}{\\left(\\because\\,\\text{decode }M_1\\text{:}\\, R_1 \\le I(M_1; Y|Y_F)\\right)}}\\\\\n", "&\\;\\;\\le I(M_0, M_1; Y|Y_F)\\;\\;\\;{\\color{blue}{\\left(\\because\\,\\text{indep. of msgs }M_0\\text{, }M_1\\text{:}\\, I(M_0; Y; M_1|Y_F) \\le 0\\right)}}\\\\\n", "&\\;\\;\\le I(M_0, M_1, Y_F; Y)\\\\\n", "&\\;\\;= I(M_0, M_1, X, Y_F; Y)\\;\\;\\;{\\color{blue}{\\left(\\because\\, X \\leftrightarrow (M_0, M_1, Y_F) \\leftrightarrow Y\\right)}}\\\\\n", "&\\;\\;= I(X; Y)\\;\\;\\;{\\color{blue}{\\left(\\because\\, (M_0, M_1, Y_F) \\leftrightarrow X \\leftrightarrow Y\\right)}}\\\\\n", "\\\\\n", "&\\;\\;1.4.\\;\\text{Steps: }\\\\\n", "&\\;\\;R_0+R_1\\\\\n", "&\\;\\;\\le R_0+I(M_1; Y|Y_F)\\;\\;\\;{\\color{blue}{\\left(\\because\\,\\text{decode }M_1\\text{:}\\, R_1 \\le I(M_1; Y|Y_F)\\right)}}\\\\\n", "&\\;\\;\\le I(M_0; Z|Z_P)+I(M_1; Y|Y_F)\\;\\;\\;{\\color{blue}{\\left(\\because\\,\\text{decode }M_0\\text{:}\\, R_0 \\le I(M_0; Z|Z_P)\\right)}}\\\\\n", "&\\;\\;\\le I(M_0; Z|Z_P)+I(M_1; Y|M_0, Y_F)\\;\\;\\;{\\color{blue}{\\left(\\because\\,\\text{indep. of msgs }M_0\\text{, }M_1\\text{:}\\, I(M_0; Y; M_1|Y_F) \\le 0\\right)}}\\\\\n", "&\\;\\;\\le I(M_0, Z_P; Z)+I(M_1; Y|M_0, Y_F)\\\\\n", "&\\;\\;= I(M_0, M_1, Y_F; Y)+I(M_0, Y_F, Z_P; Z)-I(M_0, Y_F, Z_P; Y)\\\\\n", "&\\;\\;\\;\\;\\;\\;\\;\\;\\;\\;{\\color{blue}{\\left(\\because\\,\\text{Csiszar sum}\\text{:}\\, I(Y_F; Z|Z_P, M_0) = I(Z_P; Y|Y_F, M_0)\\right)}}\\\\\n", "&\\;\\;= I(M_0, Y_F, Z_P; Z)+I(M_0, M_1, X, Y_F; Y)-I(M_0, Y_F, Z_P; Y)\\;\\;\\;{\\color{blue}{\\left(\\because\\, X \\leftrightarrow (M_0, M_1, Y_F) \\leftrightarrow Y\\right)}}\\\\\n", "&\\;\\;= I(X; Y|M_0, Y_F, Z_P)+I(M_0, Y_F, Z_P; Z)-I(M_0, Y_F, Z_P; Y|X)\\\\\n", "&\\;\\;\\;\\;\\;\\;\\;\\;\\;\\;{\\color{blue}{\\left(\\because\\, (M_0, M_1, Y_F) \\leftrightarrow X \\leftrightarrow Y\\right)}}\\\\\n", "&\\;\\;= I(X; Y|M_0, Y_F, Z_P)+I(M_0, Y_F, Z_P; Z)\\;\\;\\;{\\color{blue}{\\left(\\because\\, (M_0, Y_F, Z_P) \\leftrightarrow X \\leftrightarrow Y\\right)}}\\\\\n", "\\end{align*}\n", "$" ], "text/plain": [ "" ] }, "execution_count": 15, "metadata": {}, "output_type": "execute_result" } ], "source": [ "# Output converse proof (is_proof = True for shorter proof)\n", "(model.get_outer(is_proof = True) >> r).proof()" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### References\n", "- A. El Gamal and Y.-H. Kim, _Network Information Theory_, Cambridge University Press, 2011, Ch. 5, 8.\n", "- K. Marton, \"A coding theorem for the discrete memoryless broadcast channel,\" IEEE Transactions on Information Theory, vol. 25, no. 3, pp. 306–311, May 1979.\n", "- S. I. Gel'fand and M. S. Pinsker, \"Capacity of a broadcast channel with one deterministic component,\" Problemy Peredachi Informatsii, vol. 16, no. 1, pp. 24–34, 1980.\n", "- Y. Liang and G. Kramer, \"Rate regions for relay broadcast channels,\" IEEE Transactions on Information Theory, vol. 53, no. 10, pp. 3517–3535, Oct 2007.\n", "- C. Nair and A. El Gamal, \"An outer bound to the capacity region of the broadcast channel,\" IEEE Transactions on Information Theory, vol. 53, no. 1, pp. 350–355, 2006.\n", "- J. Körner and K. Marton, \"Comparison of two noisy channels,\" Topics in information theory, pp. 411–423, 1977.\n", "- A. El Gamal, \"The capacity of a class of broadcast channels,\" IEEE Transactions on Information Theory, vol. 25, no. 2, pp. 166–169, 1979.\n", "- P. Bergmans, \"Random coding theorem for broadcast channels with degraded components,\" IEEE Transactions on Information Theory, vol. 19, no. 2, pp. 197–207, 1973.\n", "- R. G. Gallager, \"Capacity and coding for degraded broadcast channels,\" Problemy Peredachi Informatsii, vol. 10, no. 3, pp. 3–14, 1974." ] }, { "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 }