{
"cells": [
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# Chapter 3: Defining computation\n",
"\n",
"Code related to [Chapter 3: Defining computation](https://introtcs.org/public/lec_03_computation.html) in __Introduction to Theoretical Computer Science__ by Boaz Barak. [](https://colab.research.google.com/github/boazbk/tcscode/blob/master/Chap_03_computation.ipynb)\n"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"!wget https://raw.githubusercontent.com/boazbk/tcscode/master/Utilities.ipynb\n",
"# get utility code from repository"
]
},
{
"cell_type": "code",
"execution_count": 3,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"Requirement already satisfied: schemdraw in /Users/boazbarak/opt/anaconda3/envs/tcs/lib/python3.9/site-packages (0.14)\n"
]
}
],
"source": [
"!pip install schemdraw"
]
},
{
"cell_type": "code",
"execution_count": 15,
"metadata": {},
"outputs": [],
"source": [
"import schemdraw as schem\n",
"import schemdraw.elements as elm\n",
"from schemdraw import logic\n",
"import schemdraw"
]
},
{
"cell_type": "code",
"execution_count": 16,
"metadata": {},
"outputs": [
{
"data": {
"image/png": "iVBORw0KGgoAAAANSUhEUgAAATwAAACfCAYAAABk+mXyAAAAOXRFWHRTb2Z0d2FyZQBNYXRwbG90bGliIHZlcnNpb24zLjUuMSwgaHR0cHM6Ly9tYXRwbG90bGliLm9yZy/YYfK9AAAACXBIWXMAAAsTAAALEwEAmpwYAAAYz0lEQVR4nO2dd7xcVbXHv79ggNCS0OsDqaFIURFDUR+9SfWFAIo0QfCBPOmWJyBIERQQUKmPjjQRCBBqpCORCCKEjtICCRAglNT1/lh7zHhJbps959yZs76fz/nse849Z681Z2bW7LP3KjIzgiAIqkC/shUIgiAoijB4QRBUhjB4QRBUhjB4QRBUhjB4QRBUhjB4QRBUhjB4QRBUhjB4QRBUhjB4QRBUhjB4QRBUhjB4QRBUhjB4QRBUhjB4QRBUhjB4QRBUhjB4QRBUhjB4QRBUhs+UrUCrI0nWIYuqJDXSZ8f+giDIQ4zwGkDSfMAzkq6QNGc6tivwCTCjt5ukKZL+KelPkk6RtFWt/yAIek8YvMYwYBCwK3CxpH7AnGlrhP7AMsBXgMOBW4Bxks6U9NkG+w6CyhIGrwHM7ENgK+ADYDjwc+AS4LfplInAGmam7m74ezIAWAHYBjgB+BswGDgIeF7S7yQtUuRrDYJ2QDFd1DiSNgNuBeYAdgGuA64BdgSeA75oZu83KGMt4AfAbvjc60TgCOD8mPMLgu5R6ghP0oWSTNKqZerRKGZ2B/A/afcCYDlgd+AJYCXg/AwLGY+b2beBNYHb8Ufpc4GrJQ1upO8gqAqlGbw04T8MeAfYpyw96pE0p6RTJb0i6U1JV0taqJuXn4WP6uYD/g+YDHwDf9z9L2DnHDqa2dPAlrhB/SDJGC1plRz9B0E7U+YIbzjwIXAksIek/iXqUuO3wKHA0sCiuKEaKWmuri5Mj5XfBd4ENgT2NLPn8NcHcJakgTmUNOcKYB3gMWB54CFJG+XoPwjaldLm8CQ9BDwE/C8wDtjDzK7vcM4IYOsS1MvBZGBB3EXlfmAocKyZHZNTiKR5gSuBryeZ25vZyJwymoGkLwBvmNnraX8AvgA0oIFupwBvAC8Dr8XcZvApzKzwDVgNd+lYK+1fCoyYxXkj0nmtuh2cXseGaf8DYHAT7ucc+OjUgI+BTct4X3ug7yBgOjABWD0dOzzzvX8NuBzYHpir7NccW9/YShnhSToN2MTM1k77mwK3Acua2WuFK8S/5hTfYtYjjC+b2SM96GtH4HrgBWBlM5sh6S5gY9wI/jqHzh1k9gPOAfZnptF7MLecHKQFnBuA7XDDNBQYiI/458N/GG7qabfAXMCSwCq4G0+NN4FfA2eZ2XuN6B60OEVbWNyp9i3gI/xRdhz+gTTgR2Vaf3whYDr/PlI4tRf9zAG8kq7fIB37Rtof00T9++GrxAaMB1Yo8352oesA4N7aPQHmBTbDH0sNOKjB+7Aq7rbzRN17+SawF9Cv7NcfWzlb8QJ9tfITYAiweN12HD4iUqk3BDaq+4IM760+wGmpj1PS/lzApHRsqSbq/xk8MsOAZ4CFyv6QdaLrgsCzSddL8VHabml/KjA0gwwBmwIP1L2v9wLLlP36Yyt+K16gfxkvmsXxhfFHsY1Lvynpi9FgH5unfh6uO3ZTOvatJus/P/DXJOu27o5o0g/PpsD6wICC7vXq+Gq9Ad9Mx2o/Fv8EFsgkR/gIflzq+x1gh7I/a7EVu5WuQF/cMhm8wamfj2oGB/hpOnZSAa9hGXxRwIAfd+P8neoMj6VHwf8o6H7vW2eEFsOnPf6cjp2dWdYi/Pti2OFlP1XEVtwWsbRNwszexb/AA/AvGfjjG3icbLPlv4KPaAw4VtLGsztX0hDgCmCeusOfA65tNEKkm1wAjMR/JH5uZlNxZ/RpwIHJhSULZjYe2BY4Kh06BfeRjO9CBYg3ubm8k9qBqa2tEM5XhHBzf7zj8ff5rhTG96kNeBqfY+zIuni6qllel2vD02JtkWTuLWlVM/sbcEY6dnzm+2JmdjIe9zwZOBA4N4xe+xNvcLFMT20kXu2cw1N7Eu6isqWkz+cWYmZX487OH+Mjyt+E0Wtv4s1tLgumdmJqF07t20UIT/6NP8Yfazex2aekWgX/0nfk4dld04wNWDHJ3VXSIDObAFyYju3fjHtkZvfgUSqfAPuReTQZ9C3C4DWJlMFkQdyQTEiHa1/oVwqQvwLwe3x18mdmdvfszjWzZ3EXnEl1h8fgscSFYWYvAHcDcwM7pMO/S+0ukpoyMjazu/BUXtOBoyXt2ww5QfmUYvAkjZI0WdIkSR9I+rukQr9cBfCl1D5uZjPS319M7WPNFCxpAeBG3OCOwH0cO8XMbsSTENQYamavNkfDTrkutVsBmGeHeQafB12vWULN7DbggLT72zQ6DjogaRVJN0maIOl9SWMlHdn1lX2DMkd4R5rZfMACuEf85ZKWbbRTSf0kHSDpIkm/lrRuw5r2jtok/L1JrwF4aBm4E2xTSFlnrsLjlZ8GdjOz6Z1f5aQVzNrfk5ujYZfck9r1647dldoNminYzM4DTsYjZa6UtFQz5bUoI4DHgf/AV9V3Bl4sVaOeUIYvDDAKOKTDsbeAzRvsV/iXvT40bAqwdQ/7acgPD1+UeC31MzQdq4WWPdrE+zoH7l5i+GP0ir3oo2EfxAyv4ZOkx3zp2AFp/6KC5N+e5N0P9C/rXvS1DZ+DNlo4SqX0Obw0Itsen7cZ02B3O+CuBvX0xwvsFOFPVmN7PIj9OeDhdOzg1F7WDIFpdfFsvKDQJGBLM3u+GbKaiflotJZAYsnUvtxhv9nyd086bIDXKQmct4GxwEWShuV4Iiuckn4pRuGT+RNTOx04YhbntXp6qO+l11GLz30PmL8J97M/Hotq+Ojoaw30VeoIL+nweNJj7bT/lbR/X4E6bNcHPj9lb7NK2bY4Hvr3d/x7+xSwWZmfl55sZY7wjjazQWY2AHeL2EtSU1wPSmIycGEaeZ2Wjp1uZh/kFJLSWl0HfBMPDdvWzEbllFECNSfoKamdu8N+U5E0B14hLuiAmY0zs0PNbHU8guhW4A+SFuzi0j5B6Y+0AOaPXiPwkJ/649tYz/y4BjIzfKue43rYT01+T/3IFsHTMgHsb2Yf4/NP6+KZeH+R876lOhaP4H5k7+K+dnfmlFE0aeph8bRbu5eLddhvNj/GkyiMxzPbFOaL2Me2bTq7SWb2DnAMntqrJeol9wmDl+YCtsbrr/Ya81KIX8NdMmocBRzbSL/dIX1Rz8WN3ijgUkkr4bGa4PndJs3m8h7LkrQ3HmBfW40daj1IUtqHWQL/4ZrITP/Fz6X2mWYLl7QT/iU2PKvN682W2SpIGizpeElDJM0haR68dOg7+Nxe36eR5+HebrhBmIxPrk8CXgXOBObOKKPXc1G9uRY4hJnzdMvh8bJPpmOXZ3xdq+NuGrV5lmvIOC/YyH3LJH9Y0uGOumP3pWPbNVn2WszMGHNYWfegr274SO4i3A1lEv6DdDuwbtm6dfs1lK1AE9+cwgweXjaxlil5Z9y14fq0/zQN5nTD3W2+jLuczEj9jseTZWZNbdQHDN5lSYcj0v6i6d5ObvQ+diF3ufTDa8Alue9rbH1jiyD2BpH0JeBafHrgBNzQnYuHKk3G3USmS5ofN1z9utnOg6cp3wCf2xySRE4FzgOOsTpH4XYglbHcMe3WIi52x+/JneZTFs2QuzhwJ7AU7ii+nyUrGLQXatf3NaUdwuoWIXJfm1ZIXwYWwkcm38YzDG/WU5ndYAL+OHG2mf2jCf0DDd+3t5iZ+68R7jazTVLs7HP46Gt78/C3rEhaAn8sWwP4C55xuymGNSifGOE1huGFYUYA+5pXJ3u37v9T8EfQ2mNoT9qp+IrzX/HkmA+YWSFuGQ2Qw9gBnJravXFjV1vFz4qk5YE78Bjip4Ctwti1NzHCy3xtq1PWfZN0KnAo8CBex3cgviq7KLCLee66bEhaH39sXhx4FA8/nND5VUGr0yfcUoJqk+ZBD8FHtt9P82dn4MbuQXwlOpcsSfoe7imwOJ6OapMwdtUgDF5QKimV1eX4yvavzGx0ShW2Bx52uHeuBYTk73kLcBYejvcrPOY4a/RL0HeJObygNFLY3SV4YtTHgR9LWgNfnAF3TWnY2TgZ1e8DR+K+ZO8CB5jZ7xvtO2gtwuAFZXIynlnmPTx91oJ47d558VHf2b3tOEW+rAHsCeyF524Dfzw+2MzG9VrroGUJgxeUgqTDgcPwUozfwOv3vlZ3yiPAvslwdeWz2NF/cQieQHSZuv7uB35irZ9YIWiAWKXNfG2rU5D/4iA8t1o/PF71MknjmVnkKBdvAn8EzjOz0Zn7DlqQGOEFZfAe8ENgrJn9MR3bDXcAvhMP8erKV7E7/ot/s5n1RIIgRni5r2114r4F7UxT3FIkbSjpVknvSpoo6XFJR0iasxnygiAIukN2gydpWzwL6khgJTMbhNeZWA3PdRYEQVAKWR9p04raC8CFZlZqBfd4NOsdvX3tkrbEf+jAfd7OivmzoK+Re4S3Ep7q+crM/QZ9mJR9+da6Q2cAlxRcKS4IuiS3watly3htdidI2kPSlzPLDUoiFRg/Zxb/2p2ZhceDoE+Q2y2lFoC9FP5o+ynM7JLudiZpBF7rotfUHtGKvrbVyfTaV8TT0QdBnyD3CO9ZPCHm8NmdIOmhur/HSDpB0oOSzsusS1A+Eb4V9CmyjvDMzCQdBFwp6X3gCjN7W9LKeOD2cXiRlFq24CWAM83sR5I+VbHMuigT1xmxaNE7evPaJZ2IV4er5yE8M0kQ9Bmyu6WY2c3AVsA2wAuSJuI1H8bi2Wtrhm1N4AYze1NSf7wsX9Ca/Ag4om7/Ajzt0tSS9AmCWVJopIWkA4CPzOzi9PcUM7tA0lrAgWa2f0ZZMcLrBXHfgnam6ASga+ExjrW/H0t/rwOMKViXIAgqRsTSZr621Yn7FrQzkS0lKJyU6fg3eLhhTqbgBcpfwAvzjDKziZllBC1MjPAyX9vqFJQPb2W8IlmzmYbXCT4bGBnFtYMweJmvbXUKMnhDgKeBV/CIjBwImAtYDFgVL/W4AV4cCDyD8kFm9mgmeUELEo+0QZl8ZGb3NatzSYvi9Sx+AKwHPCzpZ8BxkdigmkSZxqBtMbO3zOxkYAXgNHwU+FPgWklzl6pcUAph8IK2x8wmmdlhwBa4g/uOwDWS4gmnYoTBCyqDmd0BfBUvILQtcGq5GgVFEwYvqBRm9gSwHV7s5/uSGsrGE7QWsUqb+dpWJ8d96wEfmtl8PZWTg1QX9xTgH8AQM/ukDD2CYokRXpCT8WUr0AN+hSeyWBbYr2RdgoIIgxdkw8wWNTN1teF+cuD1Z8vSdRq+Ygv+aBvfhQoQb3JQZW7Eje7yQJQdqABh8ILKYmbTgevSbixeVIAweEHVuTu165eqRVAIYfCCqvNEaoeUqkVQCGHwgqpTWzhZLBYu2p8IrQkqjZlNS/6D/YDp3awdPt7MFm2uZkEziF+0oNJImgNPKtATFun6lKAvEiO8oOosmdo3zWzxrk6ucnH2diBGeEHVWSO1RWRgDkomDF5Qdf4ztY+UqkVQCGHwgsqSVmV3Tru3lqlLUAxh8IIqszkeVvYqcG/JugQFEIsWwSwpaHJ+6QJkzJI0ujs27Z6Vwsxy9r8wsA8wTwPdTAHeBF4CRpvZezl0qzJh8IKO3EI14kr3Bb4EjMPLOObm28BJGfszSWOAa4DLzeyVjH1XhkgAmvnaoGvqyjQ+Y2aFh3RJWhN4CB99DTez3/fg2u6WolwSeBhYBvgQz783rSdq4mUnlwBWAT4PzJn+Nx24CviZmcXqcg+IEV5QKSQtj49i5wEu7omx6wlm9rqkLYH7gcHAQDM7uLf9pSprmwPfBHbC6/kOk3Q6cLyZvd+41u1PLFoElUHSurgBWgq4D/huM+WZ2VPA1/G5uIMkDWugr0/M7EYzGwasCFyAD1gOB56QNDSHzu1OGLyg7ZHUX9JRuLFbAhgFbFtEHQszewAvBA5wvqRlMvT5spnV5iD/gqepv0/SUepmMHBVCYMXtC2S5pW0D/AUcCI+B3Y2sEXBj4DnADcA8wPn5DJKZjYaz+N3KjAH/hovlDRnpxdWmFi0yHxt0DV1ixYvk29FeDDwCbAosBqwIT7nNW/6/7PAwWY2shEhvf1spEWMp4CB+OhyRCN6zKL/7YAr8bnJO4EdzOzDnDLagTB4ma8NukbSKsDYgsQ9jI/qrkqFexoik3/i+8BgM5uRoa9/keYob8aN/ihgGzP7KKeMVicMXuZrg65JKZmuxkdiOZgfX4gAT9n+PPAocIeZ/SOTDAAkvUWe9FBbNjranBWSVsaN3RL4vdjWzD7OLadVCYOX+dog6AxJPwROAP5gZjs1ScYQ3OgthhcpGpZ7NNmqxKJFEBTLRYAB20iat6uTe4OZjQU2xR+ddyZvxAeSNpR0q6R3JU2U9LikI1phsSQMXhAUiJm9gT9uz8nM1FTNkPMkbuymAYen1eqGkbQtnllmJLCSmQ0CdsGnJ5bIIaOZhMELguK5J7XrNlOImd0J7J92z5a0TiP9JXeaM4GTzex0M5uQ5Iw1sz1zz5c2gzB4QVA8T6V21WYLMrMLgfPwuNxrJA1soLuVgM/i7i8tSRi8ICieWmnIoooBHQz8FVgBmCjJurl19BWs6ftaDqUkrSdpja7PzEcYvCAonpqbSCO58rpNCqE7IkNXE1K7VKdndZ/dKOge1AiDFwTFU/uSFxIJIWku4OS0ey3Qz8zUjW2bDl09i0fHDO9E1h6SHpH0qKRvpWOS9EjdObdJGg7sCZySXHUKIdJDBUHx1FYzJ3R6VgbqFhrWAV4E9rVeOt+amUk6CLhS0vvAFWb2dnJ2PhK4BDeGG+CDqdHApfij9It1XQ0ys6skHWxmX+vlS+sVMcILguJZO7VPdXZSJg4E9sPjjIc1mibezG4GtgK2AV6QNBEfNY4FtgDOSSF8U5NMgLXwOUQkLQW8IWlpoPCszTHCC4Li2Si1jzZTiKRNgDPS7j5m9pcc/ZrZ/cCWs5D3c2balL2AO9LfKzFzhLcrbvw+hyeQKJQILct8bRB0Rt3I5mNgkWZlNJH0Bdzfb37gJDM7uhlyOshcDrgMT0//PLC/mX0iqZbC6i7gC8DvgL/jKbOeNLPZzglm1zEMXt5rg6AzJP0EOA643sx27ur8XsoYgmd0XhhP0rBb7qpsrUo80gaFI+kzwPXky5ZSYyowHh9djMazpTyXU0DGbCnnZOjjU0haHbgdN3a3At8KYzeTGOFlvjbomroEoEXwGJ4P7zIzm9JoZxnz4Q3q7Wrp7JC0Hl6gaEHgT8DWkQ/v3wmDl/naoGvqDN5LeFbiLN3iAfmL4SFbG+ET67VQqhfxjMcNZRpuMOPx08ACeIr52xvRYxb97wJciPv43YyvyEYevA6Ewct8bdA1RdWlTaUNhwFHAzU55+GGr1cFfHrz2Ui+cDfj6exvNrOv90b2bPqeE69lUSsUdDHwHTObmktGOxF+eEHbkkobXoK7QBwKTAa+A9zRYBB9T/lv3Ni9y8zsJQ2TSjM+hhu7acBBwF5h7GZPGLyg7TGzaWb2S2AoHvi+IXCLpAHNli3pK8Av0+53zez1DH2uIOli4AFgdeA54KtmdlbuecF2IwxeUBnMbAxu7F7Byxue18w6rpJWBf6Ae0OcamZXN9DXApJ2knQTHtO6BzAdz2a8lpk9mEPndifcUoJKYWYvS9oKeATYHXfduDy3HElrA2PqDvWT9At8caVf2tSNdgA+/7gG0D/1NRWPWz3OzF7KrXs7E4sWnVwbNJ0PzWy+MgSnlOfnA2/hqcq7VZi7u58rSa+SL40SwAy85OQNwMVm9lbGvitDGLxZXzuCfAWig9lTpsETPgc2FPihmZ3Yzeu6a/BWxJ2rR+B+dzPw4j317ayOdWyn4XN0T3bXKAezJwxeUDhFuaV0Q4/N8WI0rwPLdqdQd3yuWptYtAiqzB14GNqSwFdL1iUogDB4QWVJLhzXpd1PpTsK2o8weEHVGZXa9cpUIiiGMHhB1XkytauUqkVQCOGHF1SdN1K7aLgjtT8xwgsqTcoV11NDN74ZugTNJ0Z4QaWR1B+PaJgB9DezGSWrFDSRGOEFVWfp1I4LY9f+hMELqs6aqR1bqhZBIYTBC6rOxqmNbCMVIAxeUFlSMaFa5bCGUr8HrUEYvKDK7IBnNHke+HO5qgRF0PartOFb1adZuutTmkMa3R2Tdk+PBYtq0M4jvFvKViDo0xyGp0d/Cc+LF1SAtk0PFfRdyk4PJWkj4G78CWdLMxtZtA5BObTzCC8IPoWkzwN/xI3daWHsqkUYvKAypFoW9wCD8VTpR5aqUFA4YfCCtidV/DoDn9ddALgaGJ7iaIMK0fartEF1kbQksDdwCLAQXtbwp8CJsSpbTcLgBWUyr6RNMvW1Ip7FZCCwGl5/dj08MQDA/cDBqTZtUFFilTYoHEkr4cWkm80UPILibOBuiw975QmDFxROKpF4Jj4Sy8HcwPp4XrvL8ciJ0cCfzGxSJhlBGxAGLwiCyhCrtEEQVIYweEEQVIYweEEQVIYweEEQVIYweEEQVIYweEEQVIYweEEQVIYweEEQVIb/B7ZHkL8AYzjTAAAAAElFTkSuQmCC\n",
"image/svg+xml": [
"\n",
"\n",
"\n"
],
"text/plain": [
""
]
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
"with schemdraw.Drawing() as d:\n",
" d.config(unit=0.5)\n",
" d += (X1 := logic.Xor())\n",
" d += (A := logic.Line().left(d.unit*2).at(X1.in1).idot().label('A', 'left'))\n",
" d += (B := logic.Line().left().at(X1.in2).dot())\n",
" d += logic.Line().left().label('B', 'left')\n",
"\n",
" d += logic.Line().right().at(X1.out).idot()\n",
" d += (X2 := logic.Xor().anchor('in1'))\n",
" d += (C := logic.Line().down(d.unit*2).at(X2.in2))\n",
" d.push()\n",
" d += logic.Dot().at(C.center)\n",
" d += logic.Line().tox(A.end).label('C$_{in}$', 'left')\n",
" d.pop()\n",
"\n",
" d += (A1 := logic.And().right().anchor('in1'))\n",
" d += logic.Wire('-|').at(A1.in2).to(X1.out)\n",
" d.move_from(A1.in2, dy=-d.unit*2)\n",
" d += (A2 := logic.And().right().anchor('in1'))\n",
" d += logic.Wire('-|').at(A2.in1).to(A.start)\n",
" d += logic.Wire('-|').at(A2.in2).to(B.end)\n",
" d.move_from(A1.out, dy=-(A1.out.y-A2.out.y)/2)\n",
" d += (O1 := logic.Or().right().label('C$_{out}$', 'right'))\n",
" d += logic.Line().at(A1.out).toy(O1.in1)\n",
" d += logic.Line().at(A2.out).toy(O1.in2)\n",
" d += logic.Line().at(X2.out).tox(O1.out).label('S', 'right')"
]
},
{
"cell_type": "code",
"execution_count": 10,
"metadata": {},
"outputs": [],
"source": [
"def f():\n",
" with schem.Drawing() as d:\n",
" d += elm.Resistor()\n",
" d += elm.Capacitor()\n",
" d += elm.Diode()"
]
},
{
"cell_type": "code",
"execution_count": 11,
"metadata": {},
"outputs": [
{
"data": {
"image/png": "iVBORw0KGgoAAAANSUhEUgAAAScAAAAjCAYAAADWvMzjAAAAOXRFWHRTb2Z0d2FyZQBNYXRwbG90bGliIHZlcnNpb24zLjUuMSwgaHR0cHM6Ly9tYXRwbG90bGliLm9yZy/YYfK9AAAACXBIWXMAAAsTAAALEwEAmpwYAAAEvklEQVR4nO3cX4hUZRjH8e+vNtsIoegvFUZ1IRht9IeC6EIRslW7MNoV6iJISMGLJFQSCiTS7EK2wIv+wHpV4Kq0be2CtF1ERYZCIF4UeCOSF5X0R4mwraeL8x7n7GFmzhmc8Zx3fD5wOJ4zj/jOceaZ83vf2ZWZ4ZxzdXNF1QNwzrlmvDk552rJm5Nzrpa8OTnnasmbk3Oulrw5OedqyZuTc66WomlOkm6TtEXSNQV1g5I2S7qjoE6S1kl6uLsjvbxImpY0Xfa865ykRZJekXRridq+ue6K5UuYkvYBo8CrZrajTd1W4C3gYzN7uk3dcmAWOAncZbFciJqRZABmpjLnXeckjQGbgF+AF8zssza1fXPdo7hzknQt8FQ4HC0oXxv2KyUtLFF3J/DIRQzPuV5L08JNwKeS9hQliH4QRXMCVtL4DxqStLhZkaR7gAfD4dU0Glq+bgDI3lUVNTzn6uBr4B9gI3BU0lDF4+mpWJpT2jzOhf1Ii7qRknXLgBsydc9Iiv422PW9D4FHgR+AJcARSZskxfI+7kjtn1SIdKvC4ZawL2pOWwEDhltEu7TuHeAnYBEe7VwEzOx74CHgPWABMAbMlJksj03tmxONSHcYGAf+oEm0y0S6s8Be4BuaRLtcpNsHHAh/9mjnomBmf5nZBmANcAZYARyTtLrakXVXDM0pbRr7zew8MBmO83dP6fGUmf0NTLSoSyPdj8DxTJ1HOxcVM5sEhoAvCJPllQ6oywbKFEl6EdgOXNnT0TR3Y9indzj7gedJms4bmbqRzOMAB0li27CkhWZ2Nlc3YWYm6TDzo913AJJWAO8Dg919OqVcR3LLHr10adv1hpmdlvQE8DKwE7gKorjuM2a2qm2FmRVuwJskczhVbVOZsSwAfg/nF4dzd4fjP4HBTO1X4fyz4XiA5LsiBtyXqXs7nNudOTdb8XOOamvymql8TH24bWjzHn2Sxms7hm26qO+UunMys22SdlPNnRPAz5mxnJc0yfy7p3ykS00Aj4fHPwKWktyJpZEuW/cSSbTbHGqWkSzbLiGZx7rUzpjZXAX/bkeKPqH74cuAVZP0LrC+xWODwC6S1+8F/XDdSzUnADP7tZcD6VA+2o1mzmfNi3bMn7/Kvqny0e5+kvm4Q2Z2oifPwLmLJOlekg/dIWAOeI0k5fSFGCbEm/mcxqrdMI1VukPZIjM7TWPVbk3YoDEJntb9x/xVu9Fmdc7VQfi50I3AUZLGdAJ4zMx2VTuy7oqyOeVW7T4I+3ykS6UNZifNI12+7jkake6TbozXuW6RdDMwBewhWawZBx4wsyOVDqwHomxOQRrhbs8d5x0kmYC7UNfih3zTaHcLyXWZNbPfujRW57phKXAMWE2yKDRiZuvM7Fy7vxSrmJtTGu2gSaRLZaJdqmlUy0W7lnXOVWgtyYfnl8CQmR0oqI9atM0pF+1aRbpU2mhaRbp8nUc6Vyf/hv0csA1YbmanKhzPJVF6ta6mXif53tP2grq9JBOHEwW/t+lbYAdwyiNdaTMdnnedGweuB8ZKzC31zXWP5pfNOecuL9HGOudcf/Pm5JyrJW9Ozrla8ubknKslb07OuVry5uScqyVvTs65WvLm5Jyrpf8BHsm0rdtSAqUAAAAASUVORK5CYII=\n",
"image/svg+xml": [
"\n",
"\n",
"\n"
],
"text/plain": [
""
]
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
"f()"
]
},
{
"cell_type": "code",
"execution_count": 6,
"metadata": {},
"outputs": [
{
"ename": "NameError",
"evalue": "name 'Circuit' is not defined",
"output_type": "error",
"traceback": [
"\u001b[0;31m---------------------------------------------------------------------------\u001b[0m",
"\u001b[0;31mNameError\u001b[0m Traceback (most recent call last)",
"File \u001b[0;32m/var/folders/tv/4pzd0j3x0y19_j8062mx8z9h0000gn/T/ipykernel_18991/3390395567.py:1\u001b[0m, in \u001b[0;36m\u001b[0;34m()\u001b[0m\n\u001b[0;32m----> 1\u001b[0m C \u001b[38;5;241m=\u001b[39m \u001b[43mCircuit\u001b[49m(\u001b[38;5;241m3\u001b[39m)\n\u001b[1;32m 2\u001b[0m g \u001b[38;5;241m=\u001b[39m C\u001b[38;5;241m.\u001b[39mgate(NAND,C\u001b[38;5;241m.\u001b[39mX[\u001b[38;5;241m0\u001b[39m],C\u001b[38;5;241m.\u001b[39mX[\u001b[38;5;241m1\u001b[39m])\n\u001b[1;32m 3\u001b[0m h \u001b[38;5;241m=\u001b[39m C\u001b[38;5;241m.\u001b[39mgate(NAND,C\u001b[38;5;241m.\u001b[39mX[\u001b[38;5;241m0\u001b[39m],C\u001b[38;5;241m.\u001b[39mX[\u001b[38;5;241m2\u001b[39m])\n",
"\u001b[0;31mNameError\u001b[0m: name 'Circuit' is not defined"
]
},
{
"ename": "NameError",
"evalue": "name 'Circuit' is not defined",
"output_type": "error",
"traceback": [
"\u001b[0;31m---------------------------------------------------------------------------\u001b[0m",
"\u001b[0;31mNameError\u001b[0m Traceback (most recent call last)",
"Input \u001b[0;32mIn [6]\u001b[0m, in \u001b[0;36m\u001b[0;34m()\u001b[0m\n\u001b[1;32m 1\u001b[0m \u001b[38;5;66;03m# utility code \u001b[39;00m\n\u001b[0;32m----> 2\u001b[0m \u001b[43mget_ipython\u001b[49m\u001b[43m(\u001b[49m\u001b[43m)\u001b[49m\u001b[38;5;241;43m.\u001b[39;49m\u001b[43mrun_line_magic\u001b[49m\u001b[43m(\u001b[49m\u001b[38;5;124;43m'\u001b[39;49m\u001b[38;5;124;43mrun\u001b[39;49m\u001b[38;5;124;43m'\u001b[39;49m\u001b[43m,\u001b[49m\u001b[43m \u001b[49m\u001b[38;5;124;43m'\u001b[39;49m\u001b[38;5;124;43m\"\u001b[39;49m\u001b[38;5;124;43mUtilities.ipynb\u001b[39;49m\u001b[38;5;124;43m\"\u001b[39;49m\u001b[38;5;124;43m'\u001b[39;49m\u001b[43m)\u001b[49m\n\u001b[1;32m 3\u001b[0m \u001b[38;5;28;01mfrom\u001b[39;00m \u001b[38;5;21;01mIPython\u001b[39;00m\u001b[38;5;21;01m.\u001b[39;00m\u001b[38;5;21;01mdisplay\u001b[39;00m \u001b[38;5;28;01mimport\u001b[39;00m clear_output\n\u001b[1;32m 4\u001b[0m clear_output()\n",
"File \u001b[0;32m~/opt/anaconda3/envs/tcs/lib/python3.9/site-packages/IPython/core/interactiveshell.py:2294\u001b[0m, in \u001b[0;36mInteractiveShell.run_line_magic\u001b[0;34m(self, magic_name, line, _stack_depth)\u001b[0m\n\u001b[1;32m 2292\u001b[0m kwargs[\u001b[38;5;124m'\u001b[39m\u001b[38;5;124mlocal_ns\u001b[39m\u001b[38;5;124m'\u001b[39m] \u001b[38;5;241m=\u001b[39m \u001b[38;5;28mself\u001b[39m\u001b[38;5;241m.\u001b[39mget_local_scope(stack_depth)\n\u001b[1;32m 2293\u001b[0m \u001b[38;5;28;01mwith\u001b[39;00m \u001b[38;5;28mself\u001b[39m\u001b[38;5;241m.\u001b[39mbuiltin_trap:\n\u001b[0;32m-> 2294\u001b[0m result \u001b[38;5;241m=\u001b[39m \u001b[43mfn\u001b[49m\u001b[43m(\u001b[49m\u001b[38;5;241;43m*\u001b[39;49m\u001b[43margs\u001b[49m\u001b[43m,\u001b[49m\u001b[43m \u001b[49m\u001b[38;5;241;43m*\u001b[39;49m\u001b[38;5;241;43m*\u001b[39;49m\u001b[43mkwargs\u001b[49m\u001b[43m)\u001b[49m\n\u001b[1;32m 2295\u001b[0m \u001b[38;5;28;01mreturn\u001b[39;00m result\n",
"File \u001b[0;32m~/opt/anaconda3/envs/tcs/lib/python3.9/site-packages/IPython/core/magics/execution.py:717\u001b[0m, in \u001b[0;36mExecutionMagics.run\u001b[0;34m(self, parameter_s, runner, file_finder)\u001b[0m\n\u001b[1;32m 715\u001b[0m \u001b[38;5;28;01mwith\u001b[39;00m preserve_keys(\u001b[38;5;28mself\u001b[39m\u001b[38;5;241m.\u001b[39mshell\u001b[38;5;241m.\u001b[39muser_ns, \u001b[38;5;124m'\u001b[39m\u001b[38;5;124m__file__\u001b[39m\u001b[38;5;124m'\u001b[39m):\n\u001b[1;32m 716\u001b[0m \u001b[38;5;28mself\u001b[39m\u001b[38;5;241m.\u001b[39mshell\u001b[38;5;241m.\u001b[39muser_ns[\u001b[38;5;124m'\u001b[39m\u001b[38;5;124m__file__\u001b[39m\u001b[38;5;124m'\u001b[39m] \u001b[38;5;241m=\u001b[39m filename\n\u001b[0;32m--> 717\u001b[0m \u001b[38;5;28;43mself\u001b[39;49m\u001b[38;5;241;43m.\u001b[39;49m\u001b[43mshell\u001b[49m\u001b[38;5;241;43m.\u001b[39;49m\u001b[43msafe_execfile_ipy\u001b[49m\u001b[43m(\u001b[49m\u001b[43mfilename\u001b[49m\u001b[43m,\u001b[49m\u001b[43m \u001b[49m\u001b[43mraise_exceptions\u001b[49m\u001b[38;5;241;43m=\u001b[39;49m\u001b[38;5;28;43;01mTrue\u001b[39;49;00m\u001b[43m)\u001b[49m\n\u001b[1;32m 718\u001b[0m \u001b[38;5;28;01mreturn\u001b[39;00m\n\u001b[1;32m 720\u001b[0m \u001b[38;5;66;03m# Control the response to exit() calls made by the script being run\u001b[39;00m\n",
"File \u001b[0;32m~/opt/anaconda3/envs/tcs/lib/python3.9/site-packages/IPython/core/interactiveshell.py:2800\u001b[0m, in \u001b[0;36mInteractiveShell.safe_execfile_ipy\u001b[0;34m(self, fname, shell_futures, raise_exceptions)\u001b[0m\n\u001b[1;32m 2798\u001b[0m result \u001b[38;5;241m=\u001b[39m \u001b[38;5;28mself\u001b[39m\u001b[38;5;241m.\u001b[39mrun_cell(cell, silent\u001b[38;5;241m=\u001b[39m\u001b[38;5;28;01mTrue\u001b[39;00m, shell_futures\u001b[38;5;241m=\u001b[39mshell_futures)\n\u001b[1;32m 2799\u001b[0m \u001b[38;5;28;01mif\u001b[39;00m raise_exceptions:\n\u001b[0;32m-> 2800\u001b[0m \u001b[43mresult\u001b[49m\u001b[38;5;241;43m.\u001b[39;49m\u001b[43mraise_error\u001b[49m\u001b[43m(\u001b[49m\u001b[43m)\u001b[49m\n\u001b[1;32m 2801\u001b[0m \u001b[38;5;28;01melif\u001b[39;00m \u001b[38;5;129;01mnot\u001b[39;00m result\u001b[38;5;241m.\u001b[39msuccess:\n\u001b[1;32m 2802\u001b[0m \u001b[38;5;28;01mbreak\u001b[39;00m\n",
"File \u001b[0;32m~/opt/anaconda3/envs/tcs/lib/python3.9/site-packages/IPython/core/interactiveshell.py:240\u001b[0m, in \u001b[0;36mExecutionResult.raise_error\u001b[0;34m(self)\u001b[0m\n\u001b[1;32m 238\u001b[0m \u001b[38;5;28;01mraise\u001b[39;00m \u001b[38;5;28mself\u001b[39m\u001b[38;5;241m.\u001b[39merror_before_exec\n\u001b[1;32m 239\u001b[0m \u001b[38;5;28;01mif\u001b[39;00m \u001b[38;5;28mself\u001b[39m\u001b[38;5;241m.\u001b[39merror_in_exec \u001b[38;5;129;01mis\u001b[39;00m \u001b[38;5;129;01mnot\u001b[39;00m \u001b[38;5;28;01mNone\u001b[39;00m:\n\u001b[0;32m--> 240\u001b[0m \u001b[38;5;28;01mraise\u001b[39;00m \u001b[38;5;28mself\u001b[39m\u001b[38;5;241m.\u001b[39merror_in_exec\n",
" \u001b[0;31m[... skipping hidden 1 frame]\u001b[0m\n",
"File \u001b[0;32m/var/folders/tv/4pzd0j3x0y19_j8062mx8z9h0000gn/T/ipykernel_18991/3390395567.py:1\u001b[0m, in \u001b[0;36m| \u001b[0;34m()\u001b[0m\n\u001b[0;32m----> 1\u001b[0m C \u001b[38;5;241m=\u001b[39m \u001b[43mCircuit\u001b[49m(\u001b[38;5;241m3\u001b[39m)\n\u001b[1;32m 2\u001b[0m g \u001b[38;5;241m=\u001b[39m C\u001b[38;5;241m.\u001b[39mgate(NAND,C\u001b[38;5;241m.\u001b[39mX[\u001b[38;5;241m0\u001b[39m],C\u001b[38;5;241m.\u001b[39mX[\u001b[38;5;241m1\u001b[39m])\n\u001b[1;32m 3\u001b[0m h \u001b[38;5;241m=\u001b[39m C\u001b[38;5;241m.\u001b[39mgate(NAND,C\u001b[38;5;241m.\u001b[39mX[\u001b[38;5;241m0\u001b[39m],C\u001b[38;5;241m.\u001b[39mX[\u001b[38;5;241m2\u001b[39m])\n",
"\u001b[0;31mNameError\u001b[0m: name 'Circuit' is not defined"
]
}
],
"source": [
"# utility code \n",
"%run \"Utilities.ipynb\"\n",
"from IPython.display import clear_output\n",
"clear_output()"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Circuits with AND, OR and NOT"
]
},
{
"cell_type": "code",
"execution_count": 5,
"metadata": {},
"outputs": [],
"source": [
"def AND(a,b): return a*b\n",
"\n",
"def OR(a,b): return 1 if a+b else 0\n",
"\n",
"def NOT(a): return 1-a"
]
},
{
"cell_type": "code",
"execution_count": 6,
"metadata": {},
"outputs": [],
"source": [
"def EVAL(code,X):\n",
" \"\"\"Evaluate code on input X.\"\"\"\n",
" n,m = numinout(code) # helper function - get number of inputs and outputs\n",
" \n",
" vtable = { f\"X[{i}]\":int(X[i]) for i in range(n)}\n",
" \n",
" for line in code.split(\"\\n\"):\n",
" if not line: continue\n",
" foo,op,bar,blah = parseline(line,2) \n",
" # helper function - split \"foo = OP(,blah)\" to list [\"foo\",\"OP\",\"bar\",\"blah\"]\n",
" # 2 is num of arguments to expect: blah is empty if it's missing\n",
" if op==\"NOT\": vtable[foo] = NOT(vtable[bar])\n",
" if op==\"AND\": vtable[foo] = AND(vtable[bar],vtable[blah])\n",
" if op==\"OR\": vtable[foo] = OR(vtable[bar],vtable[blah])\n",
" \n",
" return [vtable[f\"Y[{j}]\"] for j in range(m)] "
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Circuit for majority on 3 bits"
]
},
{
"cell_type": "code",
"execution_count": 7,
"metadata": {},
"outputs": [],
"source": [
"majcode = r\"\"\"firstpair = AND(X[0],X[1])\n",
"secondpair = AND(X[1],X[2])\n",
"thirdpair = AND(X[0],X[2])\n",
"temp = OR(secondpair,thirdpair)\n",
"Y[0] = OR(firstpair,temp)\n",
"\"\"\""
]
},
{
"cell_type": "code",
"execution_count": 8,
"metadata": {},
"outputs": [],
"source": [
"C = prog2circuit(majcode)\n",
"schemdraw(C,filename=\"majaoncircuit.png\")"
]
},
{
"cell_type": "code",
"execution_count": 9,
"metadata": {},
"outputs": [],
"source": [
"code = r\"\"\"\n",
"t1 = AND(X[0],X[1])\n",
"notx0 = NOT(X[0])\n",
"t2 = AND(notx0,X[2])\n",
"Y[0] = OR(t1,t2)\n",
"\"\"\"[1:]"
]
},
{
"cell_type": "code",
"execution_count": 10,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"[0]"
]
},
"execution_count": 10,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"EVAL(code,\"010\")"
]
},
{
"cell_type": "code",
"execution_count": 11,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": []
},
"execution_count": 11,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"prog2circuit(code)"
]
},
{
"cell_type": "code",
"execution_count": 13,
"metadata": {},
"outputs": [],
"source": [
"C = prog2circuit(code)\n",
"schemdraw(C)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Circuit for XOR for 3 bits"
]
},
{
"cell_type": "code",
"execution_count": 20,
"metadata": {},
"outputs": [
{
"data": {
"image/svg+xml": [
"\r\n",
"\r\n",
"\r\n",
"\r\n"
],
"text/plain": [
""
]
},
"metadata": {
"needs_background": "light"
},
"output_type": "display_data"
}
],
"source": [
"def XOR3(a,b,c):\n",
" w1 = AND(a,b)\n",
" w2 = NOT(w1)\n",
" w3 = OR(a,b)\n",
" w4 = AND(w2,w3)\n",
" w5 = AND(w4,c)\n",
" w6 = NOT(w5)\n",
" w7 = OR(w4,c)\n",
" return AND(w6,w7)\n",
"\n",
"drawcirc(XOR3)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Transform AND/OR/NOT circuits to NAND circuits"
]
},
{
"cell_type": "code",
"execution_count": 21,
"metadata": {},
"outputs": [],
"source": [
"def AON2NAND(code):\n",
" \"\"\"Translate an AON-CIRC program to an equivalent NAND-CIRC program\"\"\"\n",
" output = \"\"\n",
" counter = 0\n",
" for line in code.split(\"\\n\"):\n",
" if not line: continue\n",
" foo,op,bar,blah = parseline(line,2) \n",
" if op==\"NOT\":\n",
" output += f\"{foo} = NAND({bar},{bar})\\n\"\n",
" if op==\"AND\": \n",
" output += f\"temp_{counter} = NAND({bar},{blah})\\n\"\n",
" output += f\"{foo} = NAND(temp_{counter},temp_{counter})\\n\"\n",
" counter +=1\n",
" if op==\"OR\":\n",
" output += f\"temp_{counter} = NAND({bar},{bar})\\n\"\n",
" output += f\"temp_{counter+1} = NAND({blah},{blah})\\n\"\n",
" output += f\"{foo} = NAND(temp_{counter},temp_{counter+1})\\n\"\n",
" counter +=2\n",
" return output"
]
},
{
"cell_type": "code",
"execution_count": 22,
"metadata": {},
"outputs": [
{
"data": {
"image/svg+xml": [
"\r\n",
"\r\n",
"\r\n",
"\r\n"
],
"text/plain": [
""
]
},
"metadata": {
"needs_background": "light"
},
"output_type": "display_data"
}
],
"source": [
"C = prog2circuit(AON2NAND(code))\n",
"schemdraw(C)"
]
},
{
"cell_type": "code",
"execution_count": 23,
"metadata": {},
"outputs": [],
"source": [
"def BIG1(a,b):\n",
" t = NOT(b)\n",
" return OR(a,t)\n",
"\n",
"def BIG2(X):\n",
" \"\"\"Input is X[0]...X[3] which we consider as two three-bit numbers A and B. We return 1 iff A>B\"\"\"\n",
" y1 = BIG1(X[0],X[2])\n",
" n1 = BIG1(X[2],X[0])\n",
" y2 = BIG1(X[1],X[3])\n",
" t = AND(y2,n1)\n",
" return OR(y1,t)"
]
},
{
"cell_type": "code",
"execution_count": 24,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"gate_0 = NOT(X[2])\n",
"gate_1 = OR(X[0],gate_0)\n",
"gate_2 = NOT(X[0])\n",
"gate_3 = OR(X[2],gate_2)\n",
"gate_4 = NOT(X[3])\n",
"gate_5 = OR(X[1],gate_4)\n",
"gate_6 = AND(gate_5,gate_3)\n",
"Y[0] = OR(gate_1,gate_6)\n",
"\n"
]
}
],
"source": [
"code = circuit2prog(circuit(BIG2,4))\n",
"print(code)"
]
},
{
"cell_type": "code",
"execution_count": 25,
"metadata": {},
"outputs": [
{
"data": {
"image/svg+xml": [
"\r\n",
"\r\n",
"\r\n",
"\r\n"
],
"text/plain": [
""
]
},
"metadata": {
"needs_background": "light"
},
"output_type": "display_data"
}
],
"source": [
"C = prog2circuit(code)\n",
"schemdraw(C)"
]
},
{
"cell_type": "code",
"execution_count": 26,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"1"
]
},
"execution_count": 26,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"BIG2([1,0,0,1])"
]
},
{
"cell_type": "code",
"execution_count": 27,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"1"
]
},
"execution_count": 27,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"BIG1(1,0)"
]
},
{
"cell_type": "code",
"execution_count": 28,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": []
},
"execution_count": 28,
"metadata": {},
"output_type": "execute_result"
},
{
"data": {
"image/svg+xml": [
"\r\n",
"\r\n",
"\r\n",
"\r\n"
],
"text/plain": [
""
]
},
"metadata": {
"needs_background": "light"
},
"output_type": "display_data"
}
],
"source": [
"C = prog2circuit(code)\n",
"C"
]
},
{
"cell_type": "code",
"execution_count": 29,
"metadata": {},
"outputs": [
{
"data": {
"image/svg+xml": [
"\r\n",
"\r\n",
"\r\n",
"\r\n"
],
"text/plain": [
""
]
},
"metadata": {
"needs_background": "light"
},
"output_type": "display_data"
}
],
"source": [
"C.render_eval(1,1,1,0)"
]
},
{
"cell_type": "code",
"execution_count": 30,
"metadata": {},
"outputs": [
{
"data": {
"image/svg+xml": [
"\r\n",
"\r\n",
"\r\n",
"\r\n"
],
"text/plain": [
""
]
},
"metadata": {
"needs_background": "light"
},
"output_type": "display_data"
}
],
"source": [
"schemdraw(C)"
]
},
{
"cell_type": "code",
"execution_count": 31,
"metadata": {},
"outputs": [
{
"data": {
"image/svg+xml": [
"\r\n",
"\r\n",
"\r\n",
"\r\n"
],
"text/plain": [
""
]
},
"metadata": {
"needs_background": "light"
},
"output_type": "display_data"
}
],
"source": [
"schemdraw(C,[1,1,1,0])"
]
},
{
"cell_type": "code",
"execution_count": 32,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": []
},
"execution_count": 32,
"metadata": {},
"output_type": "execute_result"
},
{
"data": {
"image/svg+xml": [
"\r\n",
"\r\n",
"\r\n",
"\r\n"
],
"text/plain": [
""
]
},
"metadata": {
"needs_background": "light"
},
"output_type": "display_data"
}
],
"source": [
"xorcode = r'''notx0 = NOT(X[0])\n",
"notx1 = NOT(X[1])\n",
"a = AND(X[1],notx0)\n",
"b = AND(X[0],notx1)\n",
"Y[0] = OR(a,b)\n",
"'''\n",
"prog2circuit(xorcode)"
]
},
{
"cell_type": "code",
"execution_count": 35,
"metadata": {},
"outputs": [
{
"data": {
"image/svg+xml": [
"\r\n",
"\r\n",
"\r\n",
"\r\n"
],
"text/plain": [
""
]
},
"metadata": {
"needs_background": "light"
},
"output_type": "display_data"
}
],
"source": [
"schemdraw(_,[1,0])"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Circuit for ALLEQ function"
]
},
{
"cell_type": "code",
"execution_count": 38,
"metadata": {},
"outputs": [],
"source": [
"def ALLEQ(a,b,c,d):\n",
" t = AND(AND(AND(a,b),c),d)\n",
" u = AND(AND(AND(NOT(a),NOT(b)),NOT(c)),NOT(d))\n",
" return OR(t,u)"
]
},
{
"cell_type": "code",
"execution_count": 39,
"metadata": {},
"outputs": [
{
"data": {
"image/svg+xml": [
"\r\n",
"\r\n",
"\r\n",
"\r\n"
],
"text/plain": [
""
]
},
"metadata": {
"needs_background": "light"
},
"output_type": "display_data"
}
],
"source": [
"drawcirc(ALLEQ)"
]
},
{
"cell_type": "code",
"execution_count": 40,
"metadata": {},
"outputs": [
{
"data": {
"image/svg+xml": [
"\r\n",
"\r\n",
"\r\n",
"\r\n"
],
"text/plain": [
""
]
},
"metadata": {
"needs_background": "light"
},
"output_type": "display_data"
}
],
"source": [
"CMPcode = r'''temp_1 = NOT(X[2])\n",
"temp_2 = OR(X[0],temp_1)\n",
"temp_3 = NOT(X[0])\n",
"temp_4 = OR(X[2],temp_3)\n",
"temp_5 = NOT(X[3])\n",
"temp_6 = OR(X[1],temp_5)\n",
"temp_7 = AND(temp_6,temp_4)\n",
"Y[0] = OR(temp_2,temp_7)\n",
"'''\n",
"schemdraw(prog2circuit(CMPcode),[1,1,1,0])"
]
},
{
"cell_type": "code",
"execution_count": 41,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"\n",
"temp_1 = AND(X[0],X[1])\n",
"temp_2 = NOT(temp_1)\n",
"temp_3 = OR(X[0],X[1])\n",
"temp_4 = AND(temp_2,temp_3)\n",
"temp_5 = AND(temp_4,X[2])\n",
"temp_6 = NOT(temp_5)\n",
"temp_7 = OR(temp_4,X[2])\n",
"Y[0] = AND(temp_6,temp_7)\n"
]
}
],
"source": [
"print(function2code(XOR3))"
]
},
{
"cell_type": "code",
"execution_count": 42,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"True\n",
"True\n",
"True\n",
"True\n",
"True\n",
"True\n",
"True\n",
"True\n",
"True\n",
"True\n",
"True\n",
"True\n",
"True\n",
"True\n",
"True\n",
"True\n"
]
}
],
"source": [
"code = r'''\n",
"temp_1 = NOT(X[2])\n",
"temp_2 = AND(X[0],temp_1)\n",
"temp_3 = OR(X[0],temp_1)\n",
"temp_4 = NOT(X[3])\n",
"temp_5 = AND(X[1],temp_4)\n",
"temp_6 = AND(temp_5,temp_3)\n",
"Y[0] = OR(temp_2,temp_6)\n",
"'''\n",
"C = circuit(code)\n",
"for a in [0,1]:\n",
" for b in [0,1]:\n",
" for c in [0,1]:\n",
" for d in [0,1]:\n",
" print(((a>c) or ((a==c) and (b>d)))==C(a,b,c,d))"
]
},
{
"cell_type": "code",
"execution_count": 43,
"metadata": {},
"outputs": [
{
"data": {
"image/svg+xml": [
"\r\n",
"\r\n",
"\r\n",
"\r\n"
],
"text/plain": [
""
]
},
"metadata": {
"needs_background": "light"
},
"output_type": "display_data"
}
],
"source": [
"drawcirc(XOR3)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# NAND circuits"
]
},
{
"cell_type": "code",
"execution_count": 44,
"metadata": {},
"outputs": [],
"source": [
"code = r'''u = NAND(X[0],X[1])\n",
"v = NAND(X[0],u)\n",
"w = NAND(X[1],u) \n",
"Y[0] = NAND(v,w)\n",
"'''"
]
},
{
"cell_type": "code",
"execution_count": 45,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"\n",
"temp_1 = NAND(X[0],X[1])\n",
"temp_2 = NAND(X[0],temp_1)\n",
"temp_3 = NAND(X[1],temp_1)\n",
"temp_4 = NAND(temp_2,temp_3)\n",
"temp_5 = NAND(temp_4,X[2])\n",
"temp_6 = NAND(temp_4,temp_5)\n",
"temp_7 = NAND(X[2],temp_5)\n",
"Y[0] = NAND(temp_6,temp_7)\n"
]
},
{
"data": {
"image/svg+xml": [
"\r\n",
"\r\n",
"\r\n",
"\r\n"
],
"text/plain": [
""
]
},
"metadata": {
"needs_background": "light"
},
"output_type": "display_data"
}
],
"source": [
"def XORN(a,b):\n",
" u = NAND(a,b)\n",
" v = NAND(a,u)\n",
" w = NAND(b,u)\n",
" return NAND(v,w)\n",
"\n",
"def XOR3(a,b,c):\n",
" return XORN(XORN(a,b),c)\n",
"\n",
"print(function2code(XOR3))\n",
"drawcirc(XOR3)"
]
},
{
"cell_type": "code",
"execution_count": 46,
"metadata": {},
"outputs": [
{
"data": {
"image/svg+xml": [
"\r\n",
"\r\n",
"\r\n",
"\r\n"
],
"text/plain": [
""
]
},
"metadata": {
"needs_background": "light"
},
"output_type": "display_data"
}
],
"source": [
"drawcirc(XORN)"
]
},
{
"cell_type": "code",
"execution_count": 48,
"metadata": {},
"outputs": [
{
"data": {
"image/svg+xml": [
"\r\n",
"\r\n",
"\r\n",
"\r\n"
],
"text/plain": [
""
]
},
"metadata": {
"needs_background": "light"
},
"output_type": "display_data"
}
],
"source": [
"def MAJ3(a,b,c):\n",
" return OR(OR(AND(a,b),AND(b,c)),AND(a,c))\n",
"\n",
"drawcirc(MAJ3,NANDONLY=True)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# Increment"
]
},
{
"cell_type": "code",
"execution_count": 49,
"metadata": {},
"outputs": [],
"source": [
"def one(a):\n",
" return NAND(a,NAND(a,a))\n",
"\n",
"def INC(X):\n",
" n = len(X)\n",
" Y=[0]*(n+1)\n",
" c = one(X[0])\n",
" for i in range(n):\n",
" Y[i] = XORN(c,X[i])\n",
" c = AND(X[i],c)\n",
" Y[n] = c\n",
" return Y\n",
" "
]
},
{
"cell_type": "code",
"execution_count": 50,
"metadata": {},
"outputs": [
{
"data": {
"image/svg+xml": [
"\r\n",
"\r\n",
"\r\n",
"\r\n"
],
"text/plain": [
""
]
},
"metadata": {
"needs_background": "light"
},
"output_type": "display_data"
}
],
"source": [
"drawcirc(INC,4,NANDONLY=True)\n"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# Neural net activation functions"
]
},
{
"cell_type": "code",
"execution_count": 51,
"metadata": {
"scrolled": true
},
"outputs": [
{
"data": {
"image/svg+xml": [
"\r\n",
"\r\n",
"\r\n",
"\r\n"
],
"text/plain": [
""
]
},
"metadata": {
"needs_background": "light"
},
"output_type": "display_data"
}
],
"source": [
"import numpy as np\n",
"import matplotlib.pylab as plt\n",
"\n",
"\n",
"def step(x):\n",
" return np.array(x > 0, dtype=np.int)\n",
"\n",
"def sigmoid(x):\n",
" return 1 / (1 + np.exp(-x))\n",
"\n",
"def relu(x):\n",
" return np.maximum(0, 0.2*x)\n",
"\n",
"def mytanh(x):\n",
" return 0.5*np.tanh(x)+0.5\n",
"\n",
"x = np.arange(-5.0, 5.0, 0.1)\n",
"y_step = step(x)\n",
"y_sigmoid = sigmoid(x)\n",
"y_relu = relu(x)\n",
"y_tanh = mytanh(x)\n",
"\n",
"plt.plot(x, y_step, label='Step', color='r', lw=1, linestyle=None)\n",
"plt.plot(x, y_sigmoid, label='Sigmoid', color='g', lw=1, ls='--')\n",
"plt.plot(x, y_relu, label='ReLU(0.2x)', color='b', lw=1, linestyle='-.')\n",
"plt.plot(x, y_tanh, label='0.5tanh+0.5',color='y',lw=1,linestyle=':')\n",
"plt.ylim(-0.1, 1.1)\n",
"plt.legend()\n",
"plt.show()"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Misc code (can ignore for now)"
]
},
{
"cell_type": "code",
"execution_count": 52,
"metadata": {},
"outputs": [],
"source": [
"code = r'''temp_0 = NAND(X[0],X[0])\n",
"temp_2 = NAND(X[i],Y[0])\n",
"temp_3 = NAND(X[i],temp_2)\n",
"temp_4 = NAND(Y[0],temp_2)\n",
"Y[0] = NAND(temp_3,temp_4)\n",
"'''"
]
},
{
"cell_type": "code",
"execution_count": 53,
"metadata": {},
"outputs": [],
"source": [
"code = r'''temp_0 = NAND(X[0],X[0])\n",
"Y_nonblank[0] = NAND(X[0],temp_0)\n",
"Atstart[0] = NAND(X[0],temp_0) \n",
"Marker[i] = NAND(X_nonblank[i],X_noblank[i])\n",
"Atend[i] = NAND(X_nonblank[i],X_nonblank[i])\n",
"temp_2 = NAND(X[i],Y[0])\n",
"temp_3 = NAND(X[i],temp_2)\n",
"temp_4 = NAND(Y[0],temp_2)\n",
"Y[0] = NAND(temp_3,temp_4)\n",
"'''"
]
},
{
"cell_type": "code",
"execution_count": 55,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"temp_0 = NAND(X[0],X[0])\n",
"Y_nonblank[0] = NAND(X[0],temp_0)\n",
"Atstart[0] = NAND(X[0],temp_0) \n",
"Marker[0] = NAND(X_nonblank[0],X_noblank[0])\n",
"Atend[0] = NAND(X_nonblank[0],X_nonblank[0])\n",
"temp_2 = NAND(X[0],Y[0])\n",
"temp_3 = NAND(X[0],temp_2)\n",
"temp_4 = NAND(Y[0],temp_2)\n",
"Y[0] = NAND(temp_3,temp_4)\n",
"temp_0 = NAND(X[0],X[0])\n",
"Y_nonblank[0] = NAND(X[0],temp_0)\n",
"Atstart[0] = NAND(X[0],temp_0) \n",
"Marker[1] = NAND(X_nonblank[1],X_noblank[1])\n",
"Atend[1] = NAND(X_nonblank[1],X_nonblank[1])\n",
"temp_2 = NAND(X[1],Y[0])\n",
"temp_3 = NAND(X[1],temp_2)\n",
"temp_4 = NAND(Y[0],temp_2)\n",
"Y[0] = NAND(temp_3,temp_4)\n",
"temp_0 = NAND(X[0],X[0])\n",
"Y_nonblank[0] = NAND(X[0],temp_0)\n",
"Atstart[0] = NAND(X[0],temp_0) \n",
"Marker[2] = NAND(X_nonblank[2],X_noblank[2])\n",
"Atend[2] = NAND(X_nonblank[2],X_nonblank[2])\n",
"temp_2 = NAND(X[2],Y[0])\n",
"temp_3 = NAND(X[2],temp_2)\n",
"temp_4 = NAND(Y[0],temp_2)\n",
"Y[0] = NAND(temp_3,temp_4)\n",
"temp_0 = NAND(X[0],X[0])\n",
"Y_nonblank[0] = NAND(X[0],temp_0)\n",
"Atstart[0] = NAND(X[0],temp_0) \n",
"Marker[3] = NAND(X_nonblank[3],X_noblank[3])\n",
"Atend[3] = NAND(X_nonblank[3],X_nonblank[3])\n",
"temp_2 = NAND(X[3],Y[0])\n",
"temp_3 = NAND(X[3],temp_2)\n",
"temp_4 = NAND(Y[0],temp_2)\n",
"Y[0] = NAND(temp_3,temp_4)\n",
"\n"
]
}
],
"source": [
"res = \"\"\n",
"for i in [0,1,2,3]:\n",
" res += code.replace('[i]',f'[{i}]')\n",
"print(res)"
]
},
{
"cell_type": "code",
"execution_count": 56,
"metadata": {},
"outputs": [
{
"data": {
"image/svg+xml": [
"\r\n",
"\r\n",
"\r\n",
"\r\n"
],
"text/plain": [
""
]
},
"metadata": {
"needs_background": "light"
},
"output_type": "display_data"
}
],
"source": [
"res = r'''temp_0 = NAND(X[0],X[0])\n",
"temp_2 = NAND(X[0],temp_0)\n",
"temp_3 = NAND(X[0],temp_2)\n",
"temp_4 = NAND(temp_0,temp_2)\n",
"Y[0] = NAND(temp_3,temp_4)\n",
"temp_2 = NAND(X[1],Y[0])\n",
"temp_3 = NAND(X[1],temp_2)\n",
"temp_4 = NAND(Y[0],temp_2)\n",
"Y[0] = NAND(temp_3,temp_4)\n",
"temp_2 = NAND(X[2],Y[0])\n",
"temp_3 = NAND(X[2],temp_2)\n",
"temp_4 = NAND(Y[0],temp_2)\n",
"Y[0] = NAND(temp_3,temp_4)\n",
"temp_2 = NAND(X[3],Y[0])\n",
"temp_3 = NAND(X[3],temp_2)\n",
"temp_4 = NAND(Y[0],temp_2)\n",
"Y[0] = NAND(temp_3,temp_4)\n",
"'''\n",
"C = prog2circuit(res)\n",
"schemdraw(C)"
]
}
],
"metadata": {
"kernelspec": {
"display_name": "tcs",
"language": "python",
"name": "tcs"
},
"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.9.12"
}
},
"nbformat": 4,
"nbformat_minor": 4
}
| | |