linAlg_Codierungstheorie_Patrick_Mischler.ipynb

{
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {
        "colab_type": "text",
        "id": "view-in-github"
      },
      "source": [
        "<a href=\"https://colab.research.google.com/github/PatMis16/linAlgGoogleColab/blob/main/linAlg_Codierungstheorie_Patrick_Mischler.ipynb\" target=\"_parent\"><img src=\"https://colab.research.google.com/assets/colab-badge.svg\" alt=\"Open In Colab\"/></a>"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "4n5SRRnHp4TD"
      },
      "source": [
        "# Codierungstheorie\n",
        "\n",
        "\n",
        "\n"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "IZf5CtQBqxy7"
      },
      "source": [
        "## Einleitung in die Codierungstheorie\n",
        "\n",
        "In einem alten Kinderspiel startet ein Kind damit, dass es einem anderen Kind eine Nachricht (ein Wort oder ein kurzer Satz) zuflüstert. Diese Nachricht wird dann von Kind zu Kind weitergegeben. Das letzte Kind in der Reihe gibt die zugeflüsterte Nachricht laut wieder. Oft mit dem Ergebnis das nicht genau das wiedergegeben wird, was das erste Kind weitergegeben hat. Es finden also bei der Übertragung Fehler statt. Übertragungsfehler können sich durch verschiedene Arten von Störungen auch beim elektronischen übertragen von Daten ergeben. So können beispielsweise elektromagnetische Störungen dazu führen das bei der Übertragung ein Bit-Fehler auftritt. Dabei wird eine 1 zu einer 0 oder Umgekehrt. \n",
        "Hinter der Codierungstheorie steht die Idee, dass Fehler bei der Übermittlung von Daten erkannt und sogar korrigiert werden können. Eine einfache jedoch nicht gerade effiziente Methode wäre es, eine Nachricht mehrmals zu übertragen und dann jeweils gegeneinander zu prüfen. Somit wäre sichergestellt, dass Fehler zumindest erkannt werden könnten. Allerdings ist die Fehlererkennung eingeschränkt. Betrachten wir ein Beispiel, bei dem die Nachricht 3-mal übertragen wird.\n",
        "\n",
        "1. > Lorem ipsum dolor\n",
        "2. > Lorem *a*psum dolor\n",
        "3. > Lorem ipsum dolor\n",
        "\n",
        "Wir sehen das bei der 2. Übertragung ein Fehler beim zweiten Wort aufgetreten ist. Dies lässt sich daran erkennen, dass sie Nachricht bei der 1. und 3. Übertragung korrekt ist. Würde aber folgendes Übertragen:\n",
        "\n",
        "1. > Lorem *a*psum dolor\n",
        "2. > Lorem *a*psum dolor\n",
        "3. > Lorem ipsum dolor\n",
        "\n",
        "Würde *ipsum* fälschlicherwe als Fehler identifiziert, da die beiden *apsum* in der Überzahl sind. \n",
        "Zudem wird hier die 3-fache Datenmenge übertragen, was dieses Verfahren nicht sehr effizient macht. \n",
        "\n",
        "Der amerikanische Mathematiker *Richard W. Hamming* hat für diesen Zweck eine einfache und doch effiziente Methode entwickelt welche *Hamming-Code* genannt wird. Der Einsatz reicht von der Fehlerprüfung bei der Datenübertragung im Netzwerk bis zu der Fehlererkennung in ECC-Speicherchips."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "BMehIYJDq6Ur"
      },
      "source": [
        "## Theorieteil\n",
        "Der *Hamming-Code* gehört zu den linearen Codes und bezieht sich auf Binärziffern. Das bedeutet, wir bewegen uns um Körper $\\mathbb{Z}_2$ [[Weitz. 2018.]](zotero://select/items/_C9DWSI2S) . Dabei bezieht sich der Begriff *Hamming-Code* auf einen Code mit einer Prüfmatrix $(E|B)$ mit der Form $(m \\times (2^m -1))$ [[Socher. 2022.]](zotero://select/items/_QGF4J2P6). \n",
        "Der *Hamming-Code* kann in verschiedenen Längen implementiert werden. *Hamming-Codes* weisen einen *Hamming-Abstand* von 3 auf. Dies bedeutet, dass sich die Codewörter um mindestens 3 Bit unterschieden müssen. Damit lassen sich bis zu zwei Bitfehler in einem Code erkennen, aber nur ein Bitfehler kann korrigiert werden. Beim erweiterten *Hamming-Code* mit einem *Hamming-Abstand* von 4, können mit hilfe eines zusätzlichen Paritätsbit bis zu drei Bitfehler erkennen, jedoch kann auch nur ein Fehler korrigiert werden [Hamming Code 2020.](zotero://select/items/_8C9CJA2Z). Ein *Hamming-Code* ist somit durch seine Länge $N$, die Anzahl Paritätsbits $k$, den *Hamming-Abstand* $d$ und die Anzahl Datenbits $n$ bestimmt. Dies ergiebt einen sogenannten $N$-$k$-$d$-Code, wobei man bei der Bezeichnung eines *Hamming-Codes* meistens nur die Gesamtlänge $N$ und die Anzahl Datenbits $n$, Gesamtlänge abzüglich der Prüfbits, als Bezeichnung verwendet werden.\n",
        "\n",
        "$$\n",
        "\\begin{aligned}\n",
        "N &= 2^k - 1 = \\text{Gesamtlänge} \\\\\n",
        "k &= ~ \\text{Paritätsbits} \\\\\n",
        "d &= ~\\text{Hamming-Abstand} \\\\\n",
        "n &= 2^k-k-1 = \\text{Datenbits} \\\\\n",
        "\\end{aligned}\n",
        "$$\n",
        "\n",
        "Besteht ein Datenpaket nun aus 7 Zeichen, müssen 3 davon für das Prüfen und korrigieren verwendet werden, damit der Code funktioniert. Als $N$-$k$-$d$-Code wird dies als $[7,4,3]$-Code bezeichnet. Für den *Hamming-Code* schreibt man $(7,4)$-*Hamming-Code*. Das Verhältnis von Nutzlast zu der Menge der übertragenen Daten ist bei diesem Beispiel eher schlecht. Allerdings verbessert sich das Verhältnis mit zunehmender Anzahl Zeichen (Bits), welche in einem Paket übermittelt werden.\n",
        "\n",
        "Prinzip: Wird ein Vektor bestehend aus 0 und 1 mit einem Vektor bestehend aus \"nur\" 1 multipliziert, erhält man Anzahl 1 in v.\n",
        "\n",
        "$$\n",
        "\\vec{v_1} = \\begin{pmatrix} 0 \\\\ 1 \\\\ 1 \\\\ 1 \\end{pmatrix},\n",
        "\\vec{v_2} = \\begin{pmatrix} 1 \\\\ 0 \\\\ 0 \\\\ 1 \\end{pmatrix},\n",
        "\\vec{v_3} = \\begin{pmatrix} 0 \\\\ 0 \\\\ 0 \\\\ 0 \\end{pmatrix}, \n",
        "\\vec{a} = \\begin{pmatrix} 1 \\\\ 1 \\\\ 1 \\\\ 1 \\end{pmatrix} \\\\\n",
        "~\\\\\n",
        "\\begin{aligned}\n",
        "\\vec{v_1}\\vec{a}&=3 \\\\\n",
        "\\vec{v_2}\\vec{a}&=2 \\\\\n",
        "\\vec{v_3}\\vec{a}&=0\n",
        "\\end{aligned}\n",
        "$$\n",
        "\n",
        "In Python kann diese Berechnung ebenfalls durchgeführt werden. Dazu wird die Bibliothek `numpy` mit den entsprechenden Funktionen für die Matrixmultiplikation verwendet. "
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 43,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "8jwEORuIpjma",
        "outputId": "860844a1-6350-4c1c-8e62-c2f37ebc6f10"
      },
      "outputs": [
        {
          "name": "stdout",
          "output_type": "stream",
          "text": [
            "[0 1 1 1]\n",
            "3\n",
            "2\n",
            "0\n"
          ]
        }
      ],
      "source": [
        "import numpy as np\n",
        "\n",
        "v1 = np.array([0,1,1,1])\n",
        "v2 = np.array([1,0,0,1])\n",
        "v3 = np.array([0,0,0,0])\n",
        "\n",
        "a = np.array([1,1,1,1])\n",
        "print(v1)\n",
        "print(np.matmul(v1, a))\n",
        "print(np.matmul(v2, a))\n",
        "print(np.matmul(v3, a))"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "EE93P81JxhJB"
      },
      "source": [
        "Die Vektoren können nun als **Codewort** bezeichtnet werden. Werden die Codewörter nun um ein Kontrollbit ergänzt [[Teschl. 2013]](zotero://select/items/_85KJXNKN), kann eine **Generatormatrix** erstellt werden. Die Generatormatrix besteht aus einer Einheitsmatrix. Die Einheitsmatix wird für die zu übertragende Nutzlast gebildet. Beispielsweise für 4 Bit:\n",
        "\n",
        "$$\n",
        "I_4 = \n",
        "\\begin{pmatrix}\n",
        "1 & 0 & 0 & 0 \\\\\n",
        "0 & 1 & 0 & 0 \\\\\n",
        "0 & 0 & 1 & 0 \\\\\n",
        "0 & 0 & 0 & 1\n",
        "\\end{pmatrix}\n",
        "$$\n",
        "\n",
        "Die Einheitsmatrix $I$ wird nun mit den Vektoren ergänzt, die bei der Multiplikation mit dem zu codierenden Wort bei einer geraden Anzahl Einsen eine $0$ und bei ungerader Anzahl Einsen eine $0$ ergiebt. Das Egebnis ist eine Generatormatrix $G_4$:\n",
        "\n",
        "$$\n",
        "G_4 = \n",
        "\\begin{pmatrix}\n",
        "1 & 0 & 0 & 0 \\\\\n",
        "0 & 1 & 0 & 0 \\\\\n",
        "0 & 0 & 1 & 0 \\\\\n",
        "0 & 0 & 0 & 1 \\\\\n",
        "\\color{green}1 & \\color{green}0 & \\color{green}1 & \\color{green}1 \\\\\n",
        "\\color{red}1 & \\color{red}1 & \\color{red}0 & \\color{red}1 \\\\\n",
        "\\color{pink}0 & \\color{pink}1 & \\color{pink}1 & \\color{pink}1\n",
        "\\end{pmatrix}\n",
        "$$\n",
        "\n",
        "Wid nun die Generatormatrix beispielsweise mit dem *Null-Wort* $a = (0, 0, 0, 0)^T$ multipliziert, ist die Anzahl Einsen ungerade und somit die sogenannten **Paritätsbits** gleich $0$.\n",
        "\n",
        "$$\n",
        "C = G \\cdot a = \n",
        "\\begin{pmatrix}\n",
        "1 & 0 & 0 & 0 \\\\\n",
        "0 & 1 & 0 & 0 \\\\\n",
        "0 & 0 & 1 & 0 \\\\\n",
        "0 & 0 & 0 & 1 \\\\\n",
        "\\color{green}1 & \\color{green}0 & \\color{green}1 & \\color{green}1 \\\\\n",
        "\\color{red}1 & \\color{red}1 & \\color{red}0 & \\color{red}1 \\\\\n",
        "\\color{pink}0 & \\color{pink}1 & \\color{pink}1 & \\color{pink}1\n",
        "\\end{pmatrix} \n",
        "\\cdot\n",
        "\\begin{bmatrix}\n",
        "0 \\\\\n",
        "0 \\\\\n",
        "0 \\\\\n",
        "0\n",
        "\\end{bmatrix}\n",
        "= (0,0,0,0,0,0,0)^T\n",
        "$$\n",
        "\n",
        "Dies lässt sich auch mit Python einfach nachvollziehen:"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 44,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "v4g7T_oA442N",
        "outputId": "bff5bfc7-1a1a-4de0-a8b1-eb5466f18e6c"
      },
      "outputs": [
        {
          "name": "stdout",
          "output_type": "stream",
          "text": [
            "[0 0 0 0 0 0 0]\n"
          ]
        }
      ],
      "source": [
        "import numpy as np\n",
        "\n",
        "G = np.array([[1, 0, 0, 0], [0, 1, 0, 0], [0, 0, 1, 0], [0, 0, 0, 1], [1, 0, 1, 1], [1, 1, 0, 1], [0, 1, 1, 1]])\n",
        "a = np.array([0, 0, 0, 0])\n",
        "result = np.matmul(G, a)\n",
        "result[result % 2 == 0] = 0\n",
        "print(result)"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "Für ein gültiges Codewort beispielsweis $b=(0,0,0,1)^T$  ergibt sich eine gerade Anzahl von Einsen. \n",
        "\n",
        "$$\n",
        "C = G \\cdot b = \n",
        "\\begin{pmatrix}\n",
        "1 & 0 & 0 & 0 \\\\\n",
        "0 & 1 & 0 & 0 \\\\\n",
        "0 & 0 & 1 & 0 \\\\\n",
        "0 & 0 & 0 & 1 \\\\\n",
        "\\color{green}1 & \\color{green}0 & \\color{green}1 & \\color{green}1 \\\\\n",
        "\\color{red}1 & \\color{red}1 & \\color{red}0 & \\color{red}1 \\\\\n",
        "\\color{pink}0 & \\color{pink}1 & \\color{pink}1 & \\color{pink}1\n",
        "\\end{pmatrix} \n",
        "\\cdot\n",
        "\\begin{bmatrix}\n",
        "0 \\\\\n",
        "0 \\\\\n",
        "0 \\\\\n",
        "1\n",
        "\\end{bmatrix}\n",
        "= (0,0,0,1,1,1,1)^T\n",
        "$$\n",
        "\n",
        "Auch dies lässt sich mit Hilfe von Python einfach berechnen:"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 45,
      "metadata": {},
      "outputs": [
        {
          "name": "stdout",
          "output_type": "stream",
          "text": [
            "[0 0 0 1 1 1 1]\n"
          ]
        }
      ],
      "source": [
        "import numpy as np\n",
        "\n",
        "G = np.array([[1, 0, 0, 0], [0, 1, 0, 0], [0, 0, 1, 0], [0, 0, 0, 1], [1, 0, 1, 1], [1, 1, 0, 1], [0, 1, 1, 1]])\n",
        "b = np.array([0, 0, 0, 1])\n",
        "result = np.where(np.matmul(G, b) % 2 == 0, 0, 1)\n",
        "print(result)"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "Wird die Generatormatrix $G$ mit einem ungültigen Codewort $c = (0,0,1,1)$ multipliziert, ergeben sich eine ungerade Anzahl von Einsen:\n",
        "\n",
        "$$\n",
        "C = G \\cdot c = \n",
        "\\begin{pmatrix}\n",
        "1 & 0 & 0 & 0 \\\\\n",
        "0 & 1 & 0 & 0 \\\\\n",
        "0 & 0 & 1 & 0 \\\\\n",
        "0 & 0 & 0 & 1 \\\\\n",
        "\\color{green}1 & \\color{green}0 & \\color{green}1 & \\color{green}1 \\\\\n",
        "\\color{red}1 & \\color{red}1 & \\color{red}0 & \\color{red}1 \\\\\n",
        "\\color{pink}0 & \\color{pink}1 & \\color{pink}1 & \\color{pink}1\n",
        "\\end{pmatrix} \n",
        "\\cdot\n",
        "\\begin{bmatrix}\n",
        "0 \\\\\n",
        "0 \\\\\n",
        "1 \\\\\n",
        "1\n",
        "\\end{bmatrix}\n",
        "= (0,0,1,1,0,1,0)^T\n",
        "$$\n",
        "\n",
        "Auch dieses Beispiel lässt sich mit Python nachvollziehen:"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 46,
      "metadata": {},
      "outputs": [
        {
          "name": "stdout",
          "output_type": "stream",
          "text": [
            "[0 0 1 1 0 1 0]\n",
            "[1 0 1 1 1 0 0]\n"
          ]
        }
      ],
      "source": [
        "import numpy as np\n",
        "\n",
        "G = np.array([[1, 0, 0, 0], [0, 1, 0, 0], [0, 0, 1, 0], [0, 0, 0, 1], [1, 0, 1, 1], [1, 1, 0, 1], [0, 1, 1, 1]])\n",
        "c = np.array([0, 0, 1, 1])\n",
        "result = np.matmul(G, c)\n",
        "result[result % 2 == 0] = 0\n",
        "print(result)\n",
        "\n",
        "c2 = np.array([1, 0, 1, 1])\n",
        "result = np.where(np.matmul(G, c2) % 2 == 0, 0, 1)\n",
        "print(result)"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "_i3MJjzQ59co"
      },
      "source": [
        "Tritt nun bei der Übertragung eines Codewortes ein Fehler auf, kann dies mithilfe einer Prüfmatrix $H$ (Check-Matrix) erkannt und korrigiert werden. Dazu wird eine Einheitsmatrix $I_k$ mit den Paritätsbits ergänzt. $k$ bezieht sich auf die Anzahl der Paritätsbits. Bei einer Nutzlast von 4 Bit ergeben sich 3 Paritätsbits, daher $I_3$. \n",
        "\n",
        "$$\n",
        "I_3=\n",
        "\\begin{pmatrix}\n",
        "1 & 0 & 0 \\\\\n",
        "0 & 1 & 0 \\\\\n",
        "0 & 0 & 1\n",
        "\\end{pmatrix}\n",
        "$$\n",
        "\n",
        "Die Paritätsbits können aus der Generatormatrix übernommen werden. Die Prüfmatrix $H_4$ hat dementsprechend folgende Form:\n",
        "\n",
        "$$\n",
        "H_4=\n",
        "\\begin{pmatrix}\n",
        "1 & 0 & 1 & 1 & 1 & 0 & 0 \\\\\n",
        "1 & 1 & 0 & 1 & 0 & 1 & 0 \\\\\n",
        "0 & 1 & 1 & 1 & 0 & 0 & 1\n",
        "\\end{pmatrix}\n",
        "$$\n",
        "\n",
        "Die Prüfmatrix $H_4$ kann nun zur Überprüfung von übertragenen Codewörtern verwendet werden. Damit lässt sich nun feststellen, ob bei der Übertragung Fehler aufgetreten sind. Dazu wird die Prüfmatrix $H_4$ mit dem Codewort $C$ multipliziert, was zum Ergebnis Vektor $\\overrightarrow{z}$ führt.\n",
        "\n",
        "Beispiel ohne Bit-Fehler:\n",
        "\n",
        "$$\n",
        "\\overrightarrow{z} = H_4 \\cdot C = \n",
        "\\begin{pmatrix}\n",
        "1 & 0 & 1 & 1 & 1 & 0 & 0 \\\\\n",
        "1 & 1 & 0 & 1 & 0 & 1 & 0 \\\\\n",
        "0 & 1 & 1 & 1 & 0 & 0 & 1\n",
        "\\end{pmatrix}\n",
        "\\cdot\n",
        "\\begin{pmatrix}\n",
        "0 \\\\\n",
        "1 \\\\\n",
        "0 \\\\\n",
        "1 \\\\\n",
        "0 \\\\\n",
        "1 \\\\\n",
        "1 \\\\\n",
        "\\end{pmatrix}\n",
        "=\n",
        "\\begin{bmatrix}\n",
        "0 \\\\\n",
        "0 \\\\\n",
        "0\n",
        "\\end{bmatrix}\n",
        "$$\n",
        "\n",
        "Auch das lässt sich wieder mit Python nacvollziehen."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": []
    },
    {
      "cell_type": "code",
      "execution_count": 47,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "Ojv8e87B993X",
        "outputId": "55a4e395-c068-4ed3-d8e9-7dc819de81a5"
      },
      "outputs": [
        {
          "name": "stdout",
          "output_type": "stream",
          "text": [
            "[0 0 0]\n"
          ]
        }
      ],
      "source": [
        "import numpy as np\n",
        "\n",
        "H4 = np.array([[1, 0, 1, 1, 1, 0, 0], [1, 1, 0, 1, 0, 1, 0], [0, 1, 1, 1, 0, 0, 1]])\n",
        "C = np.array([0, 1, 0, 1, 0, 1, 1])\n",
        "result = np.where(np.matmul(H4, C) % 2 == 0, 1, 0)\n",
        "print(result)"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "aSgBYthYBiF_"
      },
      "source": [
        "Beispiel mit Bit-Fehler im Codewort $C_f$\n",
        "\n",
        "$$\n",
        "\\overrightarrow{z} = H_4 \\cdot C_f = \n",
        "\\begin{pmatrix}\n",
        "1 & 0 & 1 & 1 & 1 & 0 & 0 \\\\\n",
        "1 & 1 & 0 & 1 & 0 & 1 & 0 \\\\\n",
        "0 & 1 & 1 & 1 & 0 & 0 & 1\n",
        "\\end{pmatrix}\n",
        "\\cdot\n",
        "\\begin{pmatrix}\n",
        "0 \\\\\n",
        "\\color{red}1 \\\\\n",
        "1 \\\\\n",
        "0 \\\\\n",
        "0 \\\\\n",
        "1 \\\\\n",
        "1 \\\\\n",
        "\\end{pmatrix}\n",
        "=\n",
        "\\begin{bmatrix}\n",
        "1 \\\\\n",
        "1 \\\\\n",
        "0\n",
        "\\end{bmatrix}\n",
        "$$\n",
        "\n",
        "Und wieder die entsprechende Berechnung in Python."
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 48,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "kSVlaF0ICH5Z",
        "outputId": "f95fd584-533c-40c1-a9d3-7cbe3131386f"
      },
      "outputs": [
        {
          "name": "stdout",
          "output_type": "stream",
          "text": [
            "[0 0 1]\n",
            "[0 0 0]\n"
          ]
        }
      ],
      "source": [
        "import numpy as np\n",
        "\n",
        "H4 = np.array([[1, 0, 1, 1, 1, 0, 0], [1, 1, 0, 1, 0, 1, 0], [0, 1, 1, 1, 0, 0, 1]])\n",
        "Cf = np.array([0, 0, 1, 1, 0, 1, 1])\n",
        "result = np.where(np.matmul(H4, Cf) % 2 == 0, 0, 1)\n",
        "print(result)\n",
        "\n",
        "Cf2 = np.array([1, 0, 1, 1, 1, 0, 0])\n",
        "result = np.where(np.matmul(H4, Cf2) % 2 == 0, 0, 1)\n",
        "print(result)"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "-C4loMNTN0Uo"
      },
      "source": [
        "Aus dem resultierenden Vektor $\\overrightarrow{z}$ ist nun nicht nur ersichtlich das ein Fehler aufgetreten ist, sondern auch an welcher Stelle dieser sich befindet. Der Binäre Wert des Vektors $overrightarrow{z}$ kann ausgewiertet werden: $0\\cdot 2^0 + 1\\cdot 2^1 + 1 \\cdot 2^2$ "
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "UJrXgSuLTwHZ"
      },
      "source": [
        "## Praktischer Teil\n",
        "\n",
        "Im ersten Teil wird eine Klass erstellt, mit dem sich für einen Hammincode, alle Notwendigen funktionen wie das Generieren einer Generator-Matrix und einer Prüfmatrix erstellen lässt.\n",
        "\n",
        "Der zweite Teil stellt das Hauptprogramm dar, in dem die Berechnungen durchgeführt werden.\n"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "WTYsmZmhUW5K"
      },
      "source": [
        "### Klasse HammingCode\n",
        "\n",
        "Die Klasse `HammingCode` besteht zum einen aus einem Konstruktor `__init__` in dem eine Instanz der Klasse (Objekt) mit den gegeben Angaben erzeugt wird. Der Konstruktor akzeptiert einen Parameter `k` mit dem die Anzahl Paritätsbits für das instanzierte `HemmingCode`-Objekt initialisiert wird. Bei der Initialisierung werden automatisch die Generatormatrix mit der Funktion `__construct_gen_matrix`, die Prüfmatrix mit der Funktion `__construct_chk_matrix` und die Decodierungs-Matrix mit der Funktion `__construct_encode_matrix()` erzeugt."
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 49,
      "metadata": {
        "id": "RVG4sS68T-af"
      },
      "outputs": [],
      "source": [
        "class HammingCode:\n",
        "    \"\"\"\n",
        "    Klasse zur verarbeitung von Hamming-Codes\n",
        "    \"\"\"\n",
        "    def __init__(self, k):\n",
        "        \"\"\"\n",
        "        Initialisierung einer HammingCode-Instanz\n",
        "        :param k: Anzahl der Paritätsbits im HammingCode\n",
        "        \"\"\"\n",
        "        self.k = k  # number of parity bits\n",
        "        self.N = 2**k - 1  # code length\n",
        "        self.p = 2 ** k - k - 1  # payload bits\n",
        "        self.__construct_chk_matrix()  # construct the check matrix\n",
        "        self.__construct_gen_matrix()  # construct the generator matrix\n",
        "        self.__construct_encode_matrix()  # construct the encode matrix\n",
        "\n",
        "    def __construct_gen_matrix(self):\n",
        "        \"\"\"\n",
        "        Konstruktion der Generator-Matrix für die HammingCode-Instanz\n",
        "        :return: none\n",
        "        \"\"\"\n",
        "        id_matrix = np.identity(self.p)\n",
        "        self.gen_matrix = np.append(id_matrix, self.parity_matrix, axis=0)\n",
        "\n",
        "    def __construct_chk_matrix(self):\n",
        "        \"\"\"\n",
        "        Konstruktion der Prüfmatrix für die HammingCode-Instanz\n",
        "        :return: none\n",
        "        \"\"\"\n",
        "        id_matrix = np.identity(self.k)\n",
        "        self.chk_matrix = \"\"\n",
        "        tmp_check_matrix = \"\"\n",
        "        for i in range(1, self.N+1):\n",
        "            bin_num_rep = bin(i)[2:]\n",
        "            bin_num_arr = self.__to_array(bin_num_rep)\n",
        "            while len(bin_num_arr) < self.k:\n",
        "                bin_num_arr.insert(0, 0)\n",
        "            if i == 1:\n",
        "                tmp_check_matrix = np.array([bin_num_arr[::-1]])\n",
        "            else:\n",
        "                tmp_check_matrix = np.vstack((tmp_check_matrix, bin_num_arr[::-1]))\n",
        "        nonsy_chk_matrix = tmp_check_matrix.T\n",
        "        one_pos = []\n",
        "        for i in range(self.N):\n",
        "            if np.sum(nonsy_chk_matrix[:, i]) == 1:\n",
        "                one_pos.append(i)\n",
        "        self.parity_matrix = np.delete(nonsy_chk_matrix, one_pos, 1)\n",
        "        self.chk_matrix = np.hstack((self.parity_matrix, id_matrix))\n",
        "\n",
        "    def __construct_encode_matrix(self):\n",
        "        \"\"\"\n",
        "        Konstruktion der Decodierungs-Matrix fir die HammingCode-Instanz\n",
        "        :return: none\n",
        "        \"\"\"\n",
        "        id_matrix = np.identity(self.p)\n",
        "        null_matrix = np.zeros((self.p, self.k))\n",
        "        self.encode_matrix = np.hstack((null_matrix, id_matrix))\n",
        "\n",
        "    @staticmethod\n",
        "    def __to_array(input_string):\n",
        "        \"\"\"\n",
        "        Methode zur Rückgabe eines Integers aus für jedes Zeichen eines Strings\n",
        "        :param input_string: Eingabe-String\n",
        "        :return: Integer\n",
        "        \"\"\"\n",
        "        return [int(x) for x in str(input_string)]\n",
        "\n",
        "    def get_length(self):\n",
        "        \"\"\"\n",
        "        Methode zur Rückgabe der Code-Länge\n",
        "        :return: Code-Länge als Integer\n",
        "        \"\"\"\n",
        "        return self.N\n",
        "\n",
        "    def get_payload(self):\n",
        "        return self.p\n",
        "\n",
        "    def get_generator_matrix(self):\n",
        "        \"\"\"\n",
        "        Methode um die Generator-Matrix auszugeben.\n",
        "        :return: generator matrix\n",
        "        \"\"\"\n",
        "        return self.gen_matrix\n",
        "\n",
        "    def get_check_matrix(self):\n",
        "        \"\"\"\n",
        "        Methode um die Prüfmatrix auszugeben.\n",
        "        :return: check matrix\n",
        "        \"\"\"\n",
        "        return self.chk_matrix\n",
        "    \n",
        "    def get_encoding_matrix(self):\n",
        "        \"\"\"\n",
        "        Metode zur rückgabe der Entcodierungs-Matrix\n",
        "        :return: encoding matrix\n",
        "        \"\"\"\n",
        "        return self.encode_matrix\n",
        "\n",
        "    def encode(self, word):\n",
        "        \"\"\"\n",
        "        Methode zum \"encoden\" eines Wortes\"\n",
        "        :param word: Wort zum \"encoden\"\n",
        "        :return: \"encoded\" Wort\n",
        "        \"\"\"\n",
        "        word_array = [int(x) for x in str(bin(word)[2:])]\n",
        "        word_array_len = len(word_array)\n",
        "        if word_array_len < self.p:\n",
        "            for i in range(self.p - word_array_len):\n",
        "                word_array.insert(0, 0)\n",
        "        tmp_encode = np.where(np.matmul(self.gen_matrix, word_array) % 2 == 0, 0, 1)\n",
        "        return ''.join(map(str, [int(x) for x in tmp_encode]))\n",
        "        \n",
        "        \n",
        "\n",
        "    def decode(self, codeword):\n",
        "        \"\"\"\n",
        "        Methode zum \"decoden\" eines Wortes\n",
        "        :param codeword: Wort zum \"decoden\"\n",
        "        :return: \"decoded\" Wort\n",
        "        \"\"\"\n",
        "        codeword_array = self.__to_array(codeword)\n",
        "        decoded_word = np.where(np.matmul(self.encode_matrix, codeword_array) % 2 == 0, 0, 1)\n",
        "        return decoded_word\n",
        "\n",
        "    def check(self, codeword):\n",
        "        \"\"\"\n",
        "        Methode zum prüfen der Gültigkeit eines Codewortes.\n",
        "        :param codeword: Codewort zum prüfen\n",
        "        :return: \"True\" wenn das wort korrekt ist, \"False\" wen das codewort fehler hat.\n",
        "        \"\"\"\n",
        "        codeword_array = self.__to_array(codeword)\n",
        "        check = np.where(np.matmul(self.chk_matrix, codeword_array) % 2 == 0, 0, 1)\n",
        "        error = sum(int(check) * (2 ** i) for i, check in enumerate(check[::-1]))\n",
        "        print(\"Error in bit: \", error)\n",
        "        return ''.join(map(str, [int(x) for x in check]))"
      ]
    },
    {
      "attachments": {},
      "cell_type": "markdown",
      "metadata": {
        "id": "kEtFFEcSUN_g"
      },
      "source": [
        "### Ausführung\n",
        "Die Klasse kann nun im Python Code verwendet werden. Mit dem Aufruf `HamingCode(k)` wird eine Instanz der Klasse erzeugt mit $k$ Paritätsbits. Mir den verwschiedenen Methoden der Klasse können nun ausgaben generiert werden. So ist \n"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 51,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "XEzSX5C3UhcM",
        "outputId": "39045117-27ef-48c9-d183-2913d1f3274c"
      },
      "outputs": [
        {
          "name": "stdout",
          "output_type": "stream",
          "text": [
            "Length:  7\n",
            "Payload:  4\n",
            "Generator Matrix:  [[1. 0. 0. 0.]\n",
            " [0. 1. 0. 0.]\n",
            " [0. 0. 1. 0.]\n",
            " [0. 0. 0. 1.]\n",
            " [1. 1. 0. 1.]\n",
            " [1. 0. 1. 1.]\n",
            " [0. 1. 1. 1.]]\n",
            "Check Matrix:  [[1. 1. 0. 1. 1. 0. 0.]\n",
            " [1. 0. 1. 1. 0. 1. 0.]\n",
            " [0. 1. 1. 1. 0. 0. 1.]]\n",
            "Encoding Matrix:  [[0. 0. 0. 1. 0. 0. 0.]\n",
            " [0. 0. 0. 0. 1. 0. 0.]\n",
            " [0. 0. 0. 0. 0. 1. 0.]\n",
            " [0. 0. 0. 0. 0. 0. 1.]]\n",
            "Word:  0\n",
            "Encoded Word:  0000000\n",
            "Error in bit:  0\n",
            "Check Result:  000\n",
            "Decoded Word:  [0 0 0 0]\n",
            "Word:  1\n",
            "Encoded Word:  0001111\n",
            "Error in bit:  0\n",
            "Check Result:  000\n",
            "Decoded Word:  [1 1 1 1]\n",
            "Word:  2\n",
            "Encoded Word:  0010011\n",
            "Error in bit:  0\n",
            "Check Result:  000\n",
            "Decoded Word:  [0 0 1 1]\n",
            "Word:  3\n",
            "Encoded Word:  0011100\n",
            "Error in bit:  0\n",
            "Check Result:  000\n",
            "Decoded Word:  [1 1 0 0]\n",
            "Word:  4\n",
            "Encoded Word:  0100101\n",
            "Error in bit:  0\n",
            "Check Result:  000\n",
            "Decoded Word:  [0 1 0 1]\n",
            "Word:  5\n",
            "Encoded Word:  0101010\n",
            "Error in bit:  0\n",
            "Check Result:  000\n",
            "Decoded Word:  [1 0 1 0]\n",
            "Word:  6\n",
            "Encoded Word:  0110110\n",
            "Error in bit:  0\n",
            "Check Result:  000\n",
            "Decoded Word:  [0 1 1 0]\n",
            "Word:  7\n",
            "Encoded Word:  0111001\n",
            "Error in bit:  0\n",
            "Check Result:  000\n",
            "Decoded Word:  [1 0 0 1]\n",
            "Word:  8\n",
            "Encoded Word:  1000110\n",
            "Error in bit:  0\n",
            "Check Result:  000\n",
            "Decoded Word:  [0 1 1 0]\n",
            "Word:  9\n",
            "Encoded Word:  1001001\n",
            "Error in bit:  0\n",
            "Check Result:  000\n",
            "Decoded Word:  [1 0 0 1]\n",
            "Word:  10\n",
            "Encoded Word:  1010101\n",
            "Error in bit:  0\n",
            "Check Result:  000\n",
            "Decoded Word:  [0 1 0 1]\n",
            "Word:  11\n",
            "Encoded Word:  1011010\n",
            "Error in bit:  0\n",
            "Check Result:  000\n",
            "Decoded Word:  [1 0 1 0]\n",
            "Word:  12\n",
            "Encoded Word:  1100011\n",
            "Error in bit:  0\n",
            "Check Result:  000\n",
            "Decoded Word:  [0 0 1 1]\n",
            "Word:  13\n",
            "Encoded Word:  1101100\n",
            "Error in bit:  0\n",
            "Check Result:  000\n",
            "Decoded Word:  [1 1 0 0]\n",
            "Word:  14\n",
            "Encoded Word:  1110000\n",
            "Error in bit:  0\n",
            "Check Result:  000\n",
            "Decoded Word:  [0 0 0 0]\n",
            "Word:  15\n",
            "Encoded Word:  1111111\n",
            "Error in bit:  0\n",
            "Check Result:  000\n",
            "Decoded Word:  [1 1 1 1]\n",
            "Hamming-Code with error\n",
            "Codeword with error:  0111011\n",
            "Error in bit:  2\n",
            "Check Result:  010\n",
            "Hamming-Code with error\n",
            "Codeword with error:  1110011\n",
            "Check Matrix:\n",
            "  [[1. 1. 0. 1. 1. 0. 0.]\n",
            " [1. 0. 1. 1. 0. 1. 0.]\n",
            " [0. 1. 1. 1. 0. 0. 1.]]\n",
            "Error in bit:  3\n",
            "Check Result:  011\n"
          ]
        }
      ],
      "source": [
        "import numpy as np\n",
        "\n",
        "def main():\n",
        "    k = 3\n",
        "    hamming = HammingCode(k)\n",
        "    print(\"Length: \", hamming.get_length())\n",
        "    print(\"Payload: \", hamming.get_payload())\n",
        "    print(\"Generator Matrix: \", hamming.get_generator_matrix())\n",
        "    print(\"Check Matrix: \", hamming.get_check_matrix())\n",
        "    print(\"Encoding Matrix: \", hamming.get_encoding_matrix())\n",
        "\n",
        "    for w in range(hamming.get_payload()**2):\n",
        "        encode_decode(hamming, w)\n",
        "\n",
        "    # Hamminc Code with error:\n",
        "    print(\"Hamming-Code with error\")\n",
        "    codeword_with_error = \"0111011\"\n",
        "    print(\"Codeword with error: \", codeword_with_error)\n",
        "    check = hamming.check(codeword_with_error)\n",
        "    print(\"Check Result: \", check)\n",
        "\n",
        "     # Hamminc Code with error:\n",
        "    print(\"Hamming-Code with error\")\n",
        "    codeword_with_error_2 = \"1110011\"\n",
        "    print(\"Codeword with error: \", codeword_with_error_2)\n",
        "    print(\"Check Matrix:\\n \", hamming.get_check_matrix())\n",
        "    check = hamming.check(codeword_with_error_2)\n",
        "    print(\"Check Result: \", check)\n",
        "    \n",
        "\n",
        "\n",
        "def encode_decode(hamming, word):\n",
        "    print(\"Word: \", word)\n",
        "    encoded_word = hamming.encode(word)\n",
        "    print(\"Encoded Word: \", encoded_word)\n",
        "    check = hamming.check(encoded_word)\n",
        "    print(\"Check Result: \", check)\n",
        "    decoded_word = hamming.decode(encoded_word)\n",
        "    print(\"Decoded Word: \", decoded_word)\n",
        "\n",
        "\n",
        "if __name__ == '__main__':\n",
        "    main()\n"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "UqaLTlyasKAj"
      },
      "source": [
        "## Literatur\n",
        "[Weitz. 2018. *Konkrete Mathematik (nicht nur) für Informatiker: mit vielen Grafiken und Algorithmen in Python*](zotero://select/items/_C9DWSI2S)\n",
        "\n",
        "[Teschl. 2013. *Mathematik für Informatiker: Band 1: Diskrete Mathematik und Lineare Algebra*](zotero://select/items/_85KJXNKN)\n",
        "\n",
        "[Socher. 2022. *Mathematik für Informatiker: diskrete Mathematik, lineare Algebra und Wahrscheinlichkeitsrechnung*](zotero://select/items/_QGF4J2P6)\n",
        "\n",
        "[2020. * Wikipedia: Hamming-Code*](zotero://select/items/_8C9CJA2Z)"
      ]
    }
  ],
  "metadata": {
    "colab": {
      "authorship_tag": "ABX9TyN5KSCOgMhkhCSAZDxMIbKh",
      "collapsed_sections": [],
      "include_colab_link": true,
      "provenance": [],
      "toc_visible": true
    },
    "kernelspec": {
      "display_name": "Python 3.10.6 ('.venv': venv)",
      "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.10.6"
    },
    "vscode": {
      "interpreter": {
        "hash": "4df1b6a76f181d946d9f21b9bc17916943543fd2ea538bba1b60436507cc8f97"
      }
    }
  },
  "nbformat": 4,
  "nbformat_minor": 0
}