Cryptography/AlgebraicCoding.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Algebraic Coding Theory"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "SageMath provides a great environment to play with the concepts of Algebraic Coding Theory.  If you have not already, I would highly recommend watching Dr. Andrew Misseldine's [Abstract Algebra](https://www.youtube.com/watch?v=Ox-_-D5bMyk&list=PLz7t89zv8Lp2D6xQOG7kUEbN1KP5u-mpH&index=80) videos on Coding Theory and Binary Symmetric Channels, note that the link leads to the first of several videos on this topic.  \n",
    "\n",
    "In SageMath, there are a few new topics we need to be introduced to before we can experiment with Group Codes and encoding messages and transmitting them over a binary symmetric channel.  The first is a new class object called a `MatrixSpace`.  Creating a MatrixSpace will allow us to create matrices and utilize them as our encoding and check matrices for our code.  The second is the command `GF(2)`, which specifies a Field of size 2.  We will use this field for our Matrix Space, since `GF(2)` is implemented as the set {0,1} in SageMath.  \n",
    "\n",
    "In the code below, we specify two Matrix Spaces, both over `GF(2)`, one of which consists of all 6x3 matrices and the other all 3x6 matrices.  This will give us the tools to define our canonical parity check matrices.  We also define G and H just as Dr. Misseldine defines them in the example he uses in his videos.  "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# define two matrix spaces, one of all 6x3 matrices, and one \n",
    "# of all 3x6 matrices.\n",
    "Z63 = MatrixSpace(GF(2),6,3)\n",
    "Z36 = MatrixSpace(GF(2),3,6)\n",
    "\n",
    "# create two matrices, one in each of our matrix spaces.  \n",
    "# Note that when defining a matrix over a MatrixSpace, \n",
    "# we don't need to separate the rows in any special \n",
    "# way, as Sage knows the size of the matrix.\n",
    "G = Z63([1,0,0, 0,1,0, 0,0,1, 0,1,1, 1,0,1, 1,1,0])\n",
    "H = Z36([0,1,1,1,0,0, 1,0,1,0,1,0, 1,1,0,0,0,1])\n",
    "\n",
    "print(G)\n",
    "\n",
    "print()\n",
    "\n",
    "print(H)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Here we define yet another Matrix Space, again over `GF(2)`, this time consisting of all 3x1 matrices, this will be the set of all messages we can encode.  we also define one specific message for us to use.  "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "message = MatrixSpace(GF(2),3,1)\n",
    "x = message([0,0,1])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Here we define some new classes for our use in this code.  We define the Bernoulli class, which acts as a Bernoulli distribution.  Note that objects of type Bernoulli require a parameter `p`, which will be the probability of success.  We also define the class SymmetricChannel.  This will act as a Binary Symmetric Channel for us to send messages over with some probability of errors.  Each object of type SymmetricChannel needs a Bernoulli distribution to accompany it.  To test whether or not the SymmetricChannel is set up correctly with a Bernoulli distribution, I have provided a function `test()`, which will tell us whether or not our SymmetricChannel is ready to go.  Do not change anything in this cell."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# import the random module to use in the Bernoulli class\n",
    "import random\n",
    "\n",
    "# define the Bernoulli class\n",
    "class Bernoulli:\n",
    "    # define the constructor, that requires a parameter p, which should\n",
    "    # be between zero and one.\n",
    "    def __init__(self, p):\n",
    "        self.p = p\n",
    "    \n",
    "    # define the method that will display information about the \n",
    "    # object when in a print statement\n",
    "    def __repr__(self):\n",
    "        return f\"Bernoulli distribution with parameter {self.p}\"\n",
    "    \n",
    "    # define the method that performs a random trial from the \n",
    "    # Bernoulli distribution based on the parameter p\n",
    "    def randomTrial(self):\n",
    "        value = random.random()\n",
    "        if value < self.p:\n",
    "            return 1\n",
    "        else:\n",
    "            return 0\n",
    "\n",
    "# define the SymmetricChannel class\n",
    "class SymmetricChannel:\n",
    "    \n",
    "    # define the constructor, which takes in a bernoulli object\n",
    "    def __init__(self, b):\n",
    "        # if b is a Bernoulli assign it to the bernoulli instance in the class,\n",
    "        # if not, set the bernoulli instance to None\n",
    "        if type(b) is Bernoulli:\n",
    "            self.bernoulli = b\n",
    "        else:\n",
    "            self.bernoulli = None\n",
    "            \n",
    "    # define the method that will provide information about the object when\n",
    "    # in a print statement\n",
    "    def __repr__(self):\n",
    "        return f\"A SymmetricChannel based on a Bernoulli distribution with parameter {self.bernoulli.p}\"\n",
    "    \n",
    "    # define a method to test whether or not the SymmetricChannel has been set up correctly.\n",
    "    # this just means whether or not the bernoulli object was accepted correctly.\n",
    "    def test(self):\n",
    "        if type(self.bernoulli) is None:\n",
    "            return \"Not set up correctly\"\n",
    "        if type(self.bernoulli) is Bernoulli:\n",
    "            return \"Set up correctly\"\n",
    "        \n",
    "    # this method takes in a matrix, which should be over GF(2), and uses the \n",
    "    # bernoulli object to randomly assign errors to the message, to simulate\n",
    "    # errors we would see over a real channel.\n",
    "    def transmit(self, message):\n",
    "        # is the matrix is of the right type, continue to use the Binary Symmetric Channel\n",
    "        if type(message) is sage.matrix.matrix_mod2_dense.Matrix_mod2_dense:\n",
    "            transmitted = []\n",
    "            # for each of the numbers in the message\n",
    "            for i in range(0,len(message.rows())):\n",
    "                # take a random trial from the bernoulli distribution.\n",
    "                value = self.bernoulli.randomTrial()\n",
    "                # then based on that random trial, either leave the message alone,\n",
    "                # or commit an error in that bit.\n",
    "                if value==0:\n",
    "                    if message[i] == 0:\n",
    "                        transmitted.append(0)\n",
    "                    else:\n",
    "                        transmitted.append(1)\n",
    "                else:\n",
    "                    if message[i] == 0:\n",
    "                        transmitted.append(1)\n",
    "                    else:\n",
    "                        transmitted.append(0)\n",
    "            # return the new message.\n",
    "            return matrix(transmitted).transpose()\n",
    "        # if the message was not of the right type, just return it.\n",
    "        else:\n",
    "            return matrix(message)\n",
    "        "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Here is our first example of sending a message over the channel, we define a Bernoulli distribution, a SymmetricChannel over that Bernoulli distribution, then we test the channel to ensure that it is set up correctly.  Then in the following cell, we define and encode the message, using our encoding message G, then transmit it over the symmetric channel, we can then perform the check with our matrix H, to see if any errors occured in transmitting."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# create a Bernoulli object\n",
    "B = Bernoulli(0.05)\n",
    "\n",
    "# create a SymmetricChannel based on that Bernoulli distribution\n",
    "T = SymmetricChannel(B)\n",
    "\n",
    "# test the SymmetricChannel to ensure that it is ready to receive messages.\n",
    "print(T.test())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# define our message\n",
    "x = message([0,1,0])\n",
    "\n",
    "# encode the message with the matrix G\n",
    "encoded = G*x\n",
    "\n",
    "# transmit the message over the Symmetric Channel\n",
    "transmitted = T.transmit(encoded)\n",
    "\n",
    "# print out the matrix H for reference.\n",
    "print(H,\"\\n\")\n",
    "\n",
    "# Use the matrix H to check for errors\n",
    "checked = H*transmitted\n",
    "print(\"Original Message: \",x.transpose())\n",
    "print(\"Encoded Message: \",encoded.transpose())\n",
    "\n",
    "# note that all these matrices are column vectors by default, thus it \n",
    "# is much easier to read if you print out the transpose\n",
    "\n",
    "# print both the message that was transmitted and the syndrome of that \n",
    "# message\n",
    "print(\"Recieved: \",transmitted.transpose())\n",
    "print(\"Syndrome: \",checked.transpose())"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "By running the above cell several times, occasionally we should see an error apear in the transmitted message, and the check will not come out to be zero.  Since this is a 1-error correcting code, if only one error occurs, we should see the corresponding column of H print out from the check.  If more errors occur, we must request another transmission."
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "SageMath 9.7",
   "language": "sage",
   "name": "sagemath"
  },
  "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.10.8"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}