W06_kody_liniowe_wstęp.ipynb

{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "provenance": [],
      "toc_visible": true,
      "include_colab_link": true
    },
    "kernelspec": {
      "name": "python3",
      "display_name": "Python 3"
    },
    "language_info": {
      "name": "python"
    }
  },
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "view-in-github",
        "colab_type": "text"
      },
      "source": [
        "<a href=\"https://colab.research.google.com/github/mrospond/kik/blob/main/W06_kody_liniowe_wst%C4%99p.ipynb\" target=\"_parent\"><img src=\"https://colab.research.google.com/assets/colab-badge.svg\" alt=\"Open In Colab\"/></a>"
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "#@title Potrzebne biblioteki...\n",
        "\n",
        "# Praca z wektorami i macierzami\n",
        "import numpy as np"
      ],
      "metadata": {
        "id": "e9_HTJHJfmD2"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "source": [
        "# Kodowanie kanałowe: kody liniowe\n",
        "\n",
        "Interesują nas tylko tzw. **blokowe** kody **liniowe** (czyli opisywane macierzami). Kodowanie od strony algebraicznej dla kodu o parametrach:\n",
        "$$ (n,k) $$\n",
        "polega na utworzeniu słowa kodowego o długości\n",
        "$$ n \\text{ symboli} $$\n",
        "na podstawie ciągu informacyjnego liczącego\n",
        "$$ k \\text{ symboli} $$\n",
        "Kodowany ciąg symboli jest dzielony na bloki $k$ symboli i każdy jest niezależnie zastępowany odpowiednim blokiem $n$ symboli.\n",
        "\n",
        "W związku z tym, że słowa kodowe mogą reprezentować wszystkie możliwe kombinacje symboli w ciągu informacyjnym, to różnych słów w kodzie jest $2^k$. Ale wszystkich ciągów o długości $n$ jest $2^n$, zatem przeważająca część ciągów o długości $n$ reprezentuje sytuację, w której nastąpiło przekłamanie (są to tzw. sekwencje zabronione)."
      ],
      "metadata": {
        "id": "UAip-YkhEeLk"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "## Macierze opisujące systematyczny kod liniowy"
      ],
      "metadata": {
        "id": "Arcj7TkgI64f"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "### Macierz generująca\n",
        "\n",
        "Macierz generująca zawiera bazę podprzestrzeni liniowej (tj. naszego kodu). Można jej używać do tworzenia słów kodowych $\\mathbf{x} $ z ciągów informacyjnych $\\mathbf{u}$:\n",
        "\n",
        "$$\n",
        "  \\mathbf{x} = \\mathbf{u}\\mathbf{G}\n",
        "$$\n",
        "\n",
        "Ciąg informacyjny liczy $k$ symboli, słowo kodowe $n$ symboli, zatem macierz generująca ma wymiary $k \\times n$.\n",
        "\n",
        "Na przykład dla kodu $(5,3)$ możemy mieć następującą macierz generującą:\n",
        "\n",
        "$$\n",
        "  \\mathbf{G} = \\begin{bmatrix} \n",
        "    1 & 0 & 0 & 1 & 0 \\\\\n",
        "    0 & 1 & 0 & 1 & 1 \\\\\n",
        "    0 & 0 & 1 & 0 & 1\n",
        "  \\end{bmatrix}\n",
        "$$\n",
        "\n",
        "W tym przypadku możemy zobaczyć, w jaki sposób symbole ciągu informacyjnego odwzorowują się na symbole słowa kodowego:\n",
        "\n",
        "$$\n",
        "  \\begin{bmatrix} x_1 & x_2 & x_3 & x_4 & x_5 \\end{bmatrix} = \\begin{bmatrix} u_1 & u_2 & u_3 \\end{bmatrix}\\begin{bmatrix} \n",
        "    1 & 0 & 0 & 1 & 0 \\\\\n",
        "    0 & 1 & 0 & 1 & 1 \\\\\n",
        "    0 & 0 & 1 & 0 & 1\n",
        "  \\end{bmatrix}\n",
        "$$\n",
        "\n",
        "Zatem (musimy pamiętać, że wykonujemy operacje w $\\mathit{GF}(2)$):\n",
        "$$\n",
        "  x_1 = u_1\n",
        "$$\n",
        "\n",
        "$$\n",
        "  x_2 = u_2\n",
        "$$\n",
        "\n",
        "$$\n",
        "  x_3 = u_3\n",
        "$$\n",
        "\n",
        "$$\n",
        "  x_4 = u_1 \\oplus u_2 = x_1 \\oplus x_2\n",
        "$$\n",
        "\n",
        "$$\n",
        "  x_5 = u_2 \\oplus u_3 = x_2 \\oplus x_3\n",
        "$$\n",
        "\n",
        "Dla kodu systematycznego $(n,k)$ macierz generująca może być podana w postaci kanonicznej i występuje w niej na początku podmacierz jednostkowa $\\mathbf{I}_k$."
      ],
      "metadata": {
        "id": "yAjdCDDbKFh1"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "#@markdown Prosty kod liniowy: macierz generująca\n",
        "\n",
        "G = np.array([\n",
        "    [1, 0, 0, 1, 0],\n",
        "    [0, 1, 0, 1, 1],\n",
        "    [0, 0, 1, 0, 1]\n",
        "])\n",
        "\n",
        "n = G.shape[1]\n",
        "k = G.shape[0]\n",
        "\n",
        "print(f\"Macierz generująca dla naszego kodu ({n},{k}):\\n{G}\")\n",
        "\n",
        "kod = np.zeros((2**k, n), dtype=int)\n",
        "d_min = n\n",
        "print(f\"\\nWszystkie słowa kodowe: \")\n",
        "for i in range(2**k):\n",
        "  u = np.array([int(x) for x in np.binary_repr(i, width=k)])\n",
        "  x = np.matmul(u,G) % 2\n",
        "  waga_x = np.sum(x)\n",
        "  print(f\"-> dla ciągu {u}: słowo kodowe {x} o wadze {waga_x}.\")\n",
        "  if waga_x > 0 and waga_x < d_min:\n",
        "    d_min = waga_x\n",
        "  kod[i] = x\n",
        "\n",
        "print(\"\\nCały kod w jednej macierzy:\\n\", kod)"
      ],
      "metadata": {
        "id": "_OIy0qjCL3eu",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "e0398dbd-5a06-4db0-bc7f-56944cc50398"
      },
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "Macierz generująca dla naszego kodu (5,3):\n",
            "[[1 0 0 1 0]\n",
            " [0 1 0 1 1]\n",
            " [0 0 1 0 1]]\n",
            "\n",
            "Wszystkie słowa kodowe: \n",
            "-> dla ciągu [0 0 0]: słowo kodowe [0 0 0 0 0] o wadze 0.\n",
            "-> dla ciągu [0 0 1]: słowo kodowe [0 0 1 0 1] o wadze 2.\n",
            "-> dla ciągu [0 1 0]: słowo kodowe [0 1 0 1 1] o wadze 3.\n",
            "-> dla ciągu [0 1 1]: słowo kodowe [0 1 1 1 0] o wadze 3.\n",
            "-> dla ciągu [1 0 0]: słowo kodowe [1 0 0 1 0] o wadze 2.\n",
            "-> dla ciągu [1 0 1]: słowo kodowe [1 0 1 1 1] o wadze 4.\n",
            "-> dla ciągu [1 1 0]: słowo kodowe [1 1 0 0 1] o wadze 3.\n",
            "-> dla ciągu [1 1 1]: słowo kodowe [1 1 1 0 0] o wadze 3.\n",
            "\n",
            "Cały kod w jednej macierzy:\n",
            " [[0 0 0 0 0]\n",
            " [0 0 1 0 1]\n",
            " [0 1 0 1 1]\n",
            " [0 1 1 1 0]\n",
            " [1 0 0 1 0]\n",
            " [1 0 1 1 1]\n",
            " [1 1 0 0 1]\n",
            " [1 1 1 0 0]]\n"
          ]
        }
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "#@markdown Minimalna odległość Hamminga $d_{\\min}$ dla kodu liniowego\n",
        "\n",
        "def hamming_distance(x: np.ndarray, y: np.ndarray) -> int:\n",
        "  roznice = np.array(x != y)\n",
        "  return np.count_nonzero(roznice)\n",
        "\n",
        "print(\"Porównanie odległości Hamminga między wszystkimi parami różnych słów kodowych: \")\n",
        "\n",
        "for i in range(kod.shape[0]):\n",
        "  for j in range(i+1,kod.shape[0]):\n",
        "    print(f\"-> odległość między {kod[i]} i {kod[j]} wynosi {hamming_distance(kod[i], kod[j])}.\")\n",
        "\n",
        "print(f\"\\nMinimalna odległość Hamminga dla tego kodu (wyliczona z niezerowych wag słów kodowych): {d_min}.\")"
      ],
      "metadata": {
        "id": "83ycDBtaQtKJ",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "a5082ccc-f1cb-4618-9cae-01261afdf0d8"
      },
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "Porównanie odległości Hamminga między wszystkimi parami różnych słów kodowych: \n",
            "-> odległość między [0 0 0 0 0] i [0 0 1 0 1] wynosi 2.\n",
            "-> odległość między [0 0 0 0 0] i [0 1 0 1 1] wynosi 3.\n",
            "-> odległość między [0 0 0 0 0] i [0 1 1 1 0] wynosi 3.\n",
            "-> odległość między [0 0 0 0 0] i [1 0 0 1 0] wynosi 2.\n",
            "-> odległość między [0 0 0 0 0] i [1 0 1 1 1] wynosi 4.\n",
            "-> odległość między [0 0 0 0 0] i [1 1 0 0 1] wynosi 3.\n",
            "-> odległość między [0 0 0 0 0] i [1 1 1 0 0] wynosi 3.\n",
            "-> odległość między [0 0 1 0 1] i [0 1 0 1 1] wynosi 3.\n",
            "-> odległość między [0 0 1 0 1] i [0 1 1 1 0] wynosi 3.\n",
            "-> odległość między [0 0 1 0 1] i [1 0 0 1 0] wynosi 4.\n",
            "-> odległość między [0 0 1 0 1] i [1 0 1 1 1] wynosi 2.\n",
            "-> odległość między [0 0 1 0 1] i [1 1 0 0 1] wynosi 3.\n",
            "-> odległość między [0 0 1 0 1] i [1 1 1 0 0] wynosi 3.\n",
            "-> odległość między [0 1 0 1 1] i [0 1 1 1 0] wynosi 2.\n",
            "-> odległość między [0 1 0 1 1] i [1 0 0 1 0] wynosi 3.\n",
            "-> odległość między [0 1 0 1 1] i [1 0 1 1 1] wynosi 3.\n",
            "-> odległość między [0 1 0 1 1] i [1 1 0 0 1] wynosi 2.\n",
            "-> odległość między [0 1 0 1 1] i [1 1 1 0 0] wynosi 4.\n",
            "-> odległość między [0 1 1 1 0] i [1 0 0 1 0] wynosi 3.\n",
            "-> odległość między [0 1 1 1 0] i [1 0 1 1 1] wynosi 3.\n",
            "-> odległość między [0 1 1 1 0] i [1 1 0 0 1] wynosi 4.\n",
            "-> odległość między [0 1 1 1 0] i [1 1 1 0 0] wynosi 2.\n",
            "-> odległość między [1 0 0 1 0] i [1 0 1 1 1] wynosi 2.\n",
            "-> odległość między [1 0 0 1 0] i [1 1 0 0 1] wynosi 3.\n",
            "-> odległość między [1 0 0 1 0] i [1 1 1 0 0] wynosi 3.\n",
            "-> odległość między [1 0 1 1 1] i [1 1 0 0 1] wynosi 3.\n",
            "-> odległość między [1 0 1 1 1] i [1 1 1 0 0] wynosi 3.\n",
            "-> odległość między [1 1 0 0 1] i [1 1 1 0 0] wynosi 2.\n",
            "\n",
            "Minimalna odległość Hamminga dla tego kodu (wyliczona z niezerowych wag słów kodowych): 2.\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "### Macierz kontrolna (macierz kontroli parzystości)\n",
        "\n",
        "Słowa kodowe tworzymy w taki sposób, że możemy opisać pojedyncze słowo, w którym da się wyróżnić symbole / pozycje informacyjne i kontrolne (tzn. na pewno da się to zrobić dla kodu systematycznego, dla kodu niesystematycznego może nie dać się w taki sposób wyróżnić pozycji).\n",
        "\n",
        "Na przykład jeśli mamy słowo (trzymamy się tylko symboli binarnych):\n",
        "$$ x_1 x_2 x_3 x_4 x_5 $$\n",
        "to możemy mieć kod, w przypadku którego pierwsze trzy symbole są informacyne, a dwa pozostałe tworzone jako kontrolne z tych trzech pierwszych, np.:\n",
        "$$ x_4 = x_1 \\oplus x_2 \\Longrightarrow x_1 \\oplus x_2 \\oplus x_4 = 0 $$\n",
        "$$ x_5 = x_2 \\oplus x_3 \\Longrightarrow x_2 \\oplus x_3 \\oplus x_5 = 0 $$\n",
        "\n",
        "W każdym takim przypadku równania kontrolne są opisane tzw. macierzą kontrolną (ona nazywana jest też macierzą kontroli parzystości, ale to nie musi być najprostsza kontrola parzysości, którą znamy z lat wcześniejszych), która w tym przypadku wygląda następująco:\n",
        "\n",
        "$$  \n",
        "  \\mathbf{H} = \\begin{bmatrix} \n",
        "    1 & 1 & 0 & 1 & 0 \\\\\n",
        "    0 & 1 & 1 & 0 & 1 \\\\\n",
        "  \\end{bmatrix}\n",
        "$$\n",
        "\n",
        "Wymiary też macierzy to $(n-k) \\times n$, czyli wierszy jest tyle, ile symboli kontrolnych, a kolumn tyle ile symboli w pojedynczym słowie.\n",
        "\n",
        "Skoro macierz kontrolna zawiera równania kontrolne, które są spełnione dla słowa kodowego, to musi zachodzić:\n",
        "$$\n",
        "  \\mathbf{x}\\mathbf{H}^T = \\mathbf{0}_{n-k}\n",
        "$$\n",
        "w przeciwnym przypadku zachodzi przekłamanie.\n",
        "\n",
        "Wynik mnożenia $\\mathbf{s} = \\mathbf{x}\\mathbf{H}^T$ nazywa się syndromem.\n",
        "\n",
        "Każde słowo w kodzie liniowym jest kombinacją wektorów bazy zawartych w macierzy generującej, musi zatem zachodzić:\n",
        "$$\n",
        "  \\mathbf{G}\\mathbf{H}^T = \\mathbf{0}_{k\\times(n-k)}\n",
        "$$\n",
        "\n",
        "Dla kodu systematycznego $(n,k)$ macierz kontrolna może być podana w postaci kanonicznej i występuje w niej na końcu podmacierz jednostkowa $\\mathbf{I}_{n-k}$. W takim przypadku macierz kontrolna może być bardzo prosto uzyskana z generującej (i na odwrót)."
      ],
      "metadata": {
        "id": "hYoIwFR0J8di"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "#@markdown Prosty kod liniowy: macierz kontrolna\n",
        "\n",
        "def H_z_G(Gen: np.ndarray) -> np.ndarray:\n",
        "  k = Gen.shape[0]\n",
        "  if not np.allclose(np.eye(k), Gen[:k,:k]):\n",
        "    print(\"G nie jest w postaci kanonicznej!\")\n",
        "    return\n",
        "  PT = Gen[:,k:]\n",
        "  H = np.concatenate((PT.T,np.eye(n-k)), axis=1).astype(int)\n",
        "  print(f\"Dla macierzy generującej G = \\n{Gen}\\npodmacierz P^T = \\n{PT}\\nzatem macierz kontrolna H = \\n{H}\")\n",
        "  return H\n",
        "\n",
        "H = H_z_G(G)\n",
        "\n",
        "print(\"*\"*100)\n",
        "print(f\"GH^T = \\n{np.matmul(G,H.T) % 2}\")\n",
        "print(\"*\"*100)\n",
        "print(\"Cały kod w jednej macierzy:\\n\", kod)\n",
        "print(\"*\"*100)\n",
        "print(f\"Wyniki mnożenia yH^T dla wszystkich y z V_n:\")\n",
        "for i in range(2**H.shape[1]):\n",
        "  y = np.array([int(x) for x in np.binary_repr(i, width=H.shape[1])])\n",
        "  s = np.matmul(y,H.T) % 2\n",
        "  print(f\"-> dla ciągu {y} syndrom s = {s}, zatem\", end=\" \")\n",
        "  if np.sum(s) == 0:\n",
        "    print(\"jest to poprawne słowo kodowe\")\n",
        "  else:\n",
        "    print(\"jest to sekwencja zabroniona\")"
      ],
      "metadata": {
        "id": "NZtw-nwvJeoD",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "d73b9f20-7a5c-41ba-d200-c10042bded94"
      },
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "Dla macierzy generującej G = \n",
            "[[1 0 0 1 0]\n",
            " [0 1 0 1 1]\n",
            " [0 0 1 0 1]]\n",
            "podmacierz P^T = \n",
            "[[1 0]\n",
            " [1 1]\n",
            " [0 1]]\n",
            "zatem macierz kontrolna H = \n",
            "[[1 1 0 1 0]\n",
            " [0 1 1 0 1]]\n",
            "****************************************************************************************************\n",
            "GH^T = \n",
            "[[0 0]\n",
            " [0 0]\n",
            " [0 0]]\n",
            "****************************************************************************************************\n",
            "Cały kod w jednej macierzy:\n",
            " [[0 0 0 0 0]\n",
            " [0 0 1 0 1]\n",
            " [0 1 0 1 1]\n",
            " [0 1 1 1 0]\n",
            " [1 0 0 1 0]\n",
            " [1 0 1 1 1]\n",
            " [1 1 0 0 1]\n",
            " [1 1 1 0 0]]\n",
            "****************************************************************************************************\n",
            "Wyniki mnożenia yH^T dla wszystkich y z V_n:\n",
            "-> dla ciągu [0 0 0 0 0] syndrom s = [0 0], zatem jest to poprawne słowo kodowe\n",
            "-> dla ciągu [0 0 0 0 1] syndrom s = [0 1], zatem jest to sekwencja zabroniona\n",
            "-> dla ciągu [0 0 0 1 0] syndrom s = [1 0], zatem jest to sekwencja zabroniona\n",
            "-> dla ciągu [0 0 0 1 1] syndrom s = [1 1], zatem jest to sekwencja zabroniona\n",
            "-> dla ciągu [0 0 1 0 0] syndrom s = [0 1], zatem jest to sekwencja zabroniona\n",
            "-> dla ciągu [0 0 1 0 1] syndrom s = [0 0], zatem jest to poprawne słowo kodowe\n",
            "-> dla ciągu [0 0 1 1 0] syndrom s = [1 1], zatem jest to sekwencja zabroniona\n",
            "-> dla ciągu [0 0 1 1 1] syndrom s = [1 0], zatem jest to sekwencja zabroniona\n",
            "-> dla ciągu [0 1 0 0 0] syndrom s = [1 1], zatem jest to sekwencja zabroniona\n",
            "-> dla ciągu [0 1 0 0 1] syndrom s = [1 0], zatem jest to sekwencja zabroniona\n",
            "-> dla ciągu [0 1 0 1 0] syndrom s = [0 1], zatem jest to sekwencja zabroniona\n",
            "-> dla ciągu [0 1 0 1 1] syndrom s = [0 0], zatem jest to poprawne słowo kodowe\n",
            "-> dla ciągu [0 1 1 0 0] syndrom s = [1 0], zatem jest to sekwencja zabroniona\n",
            "-> dla ciągu [0 1 1 0 1] syndrom s = [1 1], zatem jest to sekwencja zabroniona\n",
            "-> dla ciągu [0 1 1 1 0] syndrom s = [0 0], zatem jest to poprawne słowo kodowe\n",
            "-> dla ciągu [0 1 1 1 1] syndrom s = [0 1], zatem jest to sekwencja zabroniona\n",
            "-> dla ciągu [1 0 0 0 0] syndrom s = [1 0], zatem jest to sekwencja zabroniona\n",
            "-> dla ciągu [1 0 0 0 1] syndrom s = [1 1], zatem jest to sekwencja zabroniona\n",
            "-> dla ciągu [1 0 0 1 0] syndrom s = [0 0], zatem jest to poprawne słowo kodowe\n",
            "-> dla ciągu [1 0 0 1 1] syndrom s = [0 1], zatem jest to sekwencja zabroniona\n",
            "-> dla ciągu [1 0 1 0 0] syndrom s = [1 1], zatem jest to sekwencja zabroniona\n",
            "-> dla ciągu [1 0 1 0 1] syndrom s = [1 0], zatem jest to sekwencja zabroniona\n",
            "-> dla ciągu [1 0 1 1 0] syndrom s = [0 1], zatem jest to sekwencja zabroniona\n",
            "-> dla ciągu [1 0 1 1 1] syndrom s = [0 0], zatem jest to poprawne słowo kodowe\n",
            "-> dla ciągu [1 1 0 0 0] syndrom s = [0 1], zatem jest to sekwencja zabroniona\n",
            "-> dla ciągu [1 1 0 0 1] syndrom s = [0 0], zatem jest to poprawne słowo kodowe\n",
            "-> dla ciągu [1 1 0 1 0] syndrom s = [1 1], zatem jest to sekwencja zabroniona\n",
            "-> dla ciągu [1 1 0 1 1] syndrom s = [1 0], zatem jest to sekwencja zabroniona\n",
            "-> dla ciągu [1 1 1 0 0] syndrom s = [0 0], zatem jest to poprawne słowo kodowe\n",
            "-> dla ciągu [1 1 1 0 1] syndrom s = [0 1], zatem jest to sekwencja zabroniona\n",
            "-> dla ciągu [1 1 1 1 0] syndrom s = [1 0], zatem jest to sekwencja zabroniona\n",
            "-> dla ciągu [1 1 1 1 1] syndrom s = [1 1], zatem jest to sekwencja zabroniona\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "# Kod z kontrolą parzystości jako kod liniowy\n",
        "\n",
        "Zapewne najbardziej popularnym dydaktycznie :) kodem detekcyjnym jest kod z kontrolą parzystości. Ma parametry:\n",
        "\n",
        "$$ (n, n-1) \\quad \\text{tj.} \\quad n = k+1$$\n",
        "\n",
        "Kodowanie jest bardzo proste: do $n-1 = k$ symboli tworzących ciąg informacyjny dodaje się jeden symbol kontrolny w taki sposób, żeby w całym ciągu $n$ symboli była parzysta liczba jedynek.\n",
        "\n",
        "W ten sposób: jeśli wystąpi jedno przekłamanie na dowolnym z $n$ symboli w bloku, będzie wiadomo, że nastąpiło przekłamanie, bo liczba jedynek będzie nieparzysta.\n",
        "\n",
        "Jak automatycznie wyliczać bit kontrolny? Zobaczmy, że bit kontrolny ma być 0, jeśli tylko symbole informacyjne zawierają parzystą liczbę 1, a takie coś \"wykrywa\" dodawanie XOR:\n",
        "\n",
        "$$x_1 \\oplus x_2 \\oplus x_3 \\oplus \\dots \\oplus x_{n-1} = x_n$$\n",
        "\n",
        "a więc:\n",
        "\n",
        "$$x_1 \\oplus x_2 \\oplus x_3 \\oplus \\dots \\oplus x_{n-1} \\oplus x_n = 0$$\n",
        "\n",
        "czyli:\n",
        "\n",
        "$$\\mathbf{H} = \\begin{bmatrix} 1 & 1 & 1 & \\cdots & 1 & | 1 \\end{bmatrix}$$"
      ],
      "metadata": {
        "id": "1u9Pl92hEmhT"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "#@title Syndrom dla kodu z kontrolą parzystości { run: \"auto\" }\n",
        "\n",
        "#@markdown Wprowadź ciąg binarny:\n",
        "slowo = '00111100' #@param {type:\"string\"}\n",
        "\n",
        "y = np.array([int(c) for c in slowo])\n",
        "H = np.ones(len(y), dtype=int)\n",
        "\n",
        "print(f\"Macierz kontrolna: {H}\")\n",
        "\n",
        "# syndrom = int(H @ y % 2)\n",
        "syndrom = int(np.dot(H,y)%2)\n",
        "\n",
        "print(f\"Syndrom to {syndrom}, zatem: \", end=\"\")\n",
        "if syndrom:\n",
        "  print(\"na pewno nastąpiły przekłamania.\")\n",
        "else:\n",
        "  print(\"możemy wnioskować, że nie ma przekłamań (chociaż możemy się mylić).\")"
      ],
      "metadata": {
        "id": "v54eK2I4PjjI",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "ecf2a5d8-32af-4bb5-ef50-7db9c43e7b94"
      },
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "Macierz kontrolna: [1 1 1 1 1 1 1 1]\n",
            "Syndrom to 0, zatem: możemy wnioskować, że nie ma przekłamań (chociaż możemy się mylić).\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "## Macierz generująca dla kodu z kontrolą parzystości\n",
        "\n",
        "Skoro:\n",
        "$$\n",
        "  \\mathbf{H} = \\begin{bmatrix} 1 & 1 & 1 & \\cdots & 1 & | 1 \\end{bmatrix} = \\mathbf{H} = \\begin{bmatrix} \\mathbf{P} | 1 \\end{bmatrix}\n",
        "$$\n",
        "\n",
        "to macierz generująca:\n",
        "$$\n",
        "  \\mathbf{G} = \\begin{bmatrix} \\mathbf{I}_{n-1} | \\mathbf{P}^T \\end{bmatrix} = \\begin{bmatrix} 1 & 0 & 0 & \\cdots & 0 & 0 & 1 \\\\ 0 & 1 & 0 & \\cdots & 0 & 0 & 1 \\\\ 0 & 0 & 1 & \\cdots & 0 & 0 & 1 \\\\  &  &  &  & \\ddots & & \\\\ 0 & 0 & 0 & \\cdots & 1 & 0 & 1 \\\\ 0 & 0 & 0 & \\cdots & 0 & 1 & 1 \\end{bmatrix}\n",
        "$$\n",
        "\n",
        "Jest tak dlatego, że dla ciągu informacyjnego $\\mathbf{u}$ tworzymy słowo kodowe:\n",
        "$$\n",
        "  \\mathbf{x} = \\mathbf{u}\\mathbf{G}\n",
        "$$\n",
        "według reguły:\n",
        "$$\n",
        "  \\forall_{i=1,\\dots,n-1} \\quad x_i = u_i \\\\\n",
        "  x_n = \\sum_{i=1}^{n-1} u_i = \\sum_{i=1}^{n-1} x_i\n",
        "$$\n"
      ],
      "metadata": {
        "id": "N2Z-wlxRETUA"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "#@markdown Macierz generująca kodu z kontrolą parzystości\n",
        "\n",
        "def G_z_H(Kon: np.ndarray) -> np.ndarray:\n",
        "  n = Kon.shape[1]\n",
        "  k = n - Kon.shape[0]\n",
        "  print(f\"Kod ({n},{k})\")\n",
        "\n",
        "  if not np.allclose(np.eye(n-k), Kon[:,k:]):\n",
        "    print(\"H nie jest w postaci kanonicznej!\")\n",
        "    return\n",
        "  P = Kon[:,:k]\n",
        "  G = np.concatenate((np.eye(k),P.T), axis=1).astype(int)\n",
        "  print(f\"Dla macierzy kontrolnej H = \\n{Kon}\\npodmacierz P = \\n{P}\\nzatem macierz generująca G = \\n{G}\")\n",
        "  return G, k\n",
        "\n",
        "K = np.array([H])\n",
        "G, k = G_z_H(K)\n",
        "\n",
        "print(\"*\"*100)\n",
        "print(\"Sprawdźmy, czy poprawnie koduje: \")\n",
        "for i in range(2**k):\n",
        "  u = np.array([int(x) for x in np.binary_repr(i, width=k)])\n",
        "  x = np.matmul(u,G) % 2\n",
        "  s = np.matmul(x,K.T) % 2\n",
        "  print(f\"-> ciąg informacyjny {u} słowo kodowe x = {x}; wynik mnożenia xH^T = {s}.\")"
      ],
      "metadata": {
        "id": "ZpQ8TIGQPVSd",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "9d113def-f372-433e-eb5a-7c914ec8e4c8"
      },
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "Kod (8,7)\n",
            "Dla macierzy kontrolnej H = \n",
            "[[1 1 1 1 1 1 1 1]]\n",
            "podmacierz P = \n",
            "[[1 1 1 1 1 1 1]]\n",
            "zatem macierz generująca G = \n",
            "[[1 0 0 0 0 0 0 1]\n",
            " [0 1 0 0 0 0 0 1]\n",
            " [0 0 1 0 0 0 0 1]\n",
            " [0 0 0 1 0 0 0 1]\n",
            " [0 0 0 0 1 0 0 1]\n",
            " [0 0 0 0 0 1 0 1]\n",
            " [0 0 0 0 0 0 1 1]]\n",
            "****************************************************************************************************\n",
            "Sprawdźmy, czy poprawnie koduje: \n",
            "-> ciąg informacyjny [0 0 0 0 0 0 0] słowo kodowe x = [0 0 0 0 0 0 0 0]; wynik mnożenia xH^T = [0].\n",
            "-> ciąg informacyjny [0 0 0 0 0 0 1] słowo kodowe x = [0 0 0 0 0 0 1 1]; wynik mnożenia xH^T = [0].\n",
            "-> ciąg informacyjny [0 0 0 0 0 1 0] słowo kodowe x = [0 0 0 0 0 1 0 1]; wynik mnożenia xH^T = [0].\n",
            "-> ciąg informacyjny [0 0 0 0 0 1 1] słowo kodowe x = [0 0 0 0 0 1 1 0]; wynik mnożenia xH^T = [0].\n",
            "-> ciąg informacyjny [0 0 0 0 1 0 0] słowo kodowe x = [0 0 0 0 1 0 0 1]; wynik mnożenia xH^T = [0].\n",
            "-> ciąg informacyjny [0 0 0 0 1 0 1] słowo kodowe x = [0 0 0 0 1 0 1 0]; wynik mnożenia xH^T = [0].\n",
            "-> ciąg informacyjny [0 0 0 0 1 1 0] słowo kodowe x = [0 0 0 0 1 1 0 0]; wynik mnożenia xH^T = [0].\n",
            "-> ciąg informacyjny [0 0 0 0 1 1 1] słowo kodowe x = [0 0 0 0 1 1 1 1]; wynik mnożenia xH^T = [0].\n",
            "-> ciąg informacyjny [0 0 0 1 0 0 0] słowo kodowe x = [0 0 0 1 0 0 0 1]; wynik mnożenia xH^T = [0].\n",
            "-> ciąg informacyjny [0 0 0 1 0 0 1] słowo kodowe x = [0 0 0 1 0 0 1 0]; wynik mnożenia xH^T = [0].\n",
            "-> ciąg informacyjny [0 0 0 1 0 1 0] słowo kodowe x = [0 0 0 1 0 1 0 0]; wynik mnożenia xH^T = [0].\n",
            "-> ciąg informacyjny [0 0 0 1 0 1 1] słowo kodowe x = [0 0 0 1 0 1 1 1]; wynik mnożenia xH^T = [0].\n",
            "-> ciąg informacyjny [0 0 0 1 1 0 0] słowo kodowe x = [0 0 0 1 1 0 0 0]; wynik mnożenia xH^T = [0].\n",
            "-> ciąg informacyjny [0 0 0 1 1 0 1] słowo kodowe x = [0 0 0 1 1 0 1 1]; wynik mnożenia xH^T = [0].\n",
            "-> ciąg informacyjny [0 0 0 1 1 1 0] słowo kodowe x = [0 0 0 1 1 1 0 1]; wynik mnożenia xH^T = [0].\n",
            "-> ciąg informacyjny [0 0 0 1 1 1 1] słowo kodowe x = [0 0 0 1 1 1 1 0]; wynik mnożenia xH^T = [0].\n",
            "-> ciąg informacyjny [0 0 1 0 0 0 0] słowo kodowe x = [0 0 1 0 0 0 0 1]; wynik mnożenia xH^T = [0].\n",
            "-> ciąg informacyjny [0 0 1 0 0 0 1] słowo kodowe x = [0 0 1 0 0 0 1 0]; wynik mnożenia xH^T = [0].\n",
            "-> ciąg informacyjny [0 0 1 0 0 1 0] słowo kodowe x = [0 0 1 0 0 1 0 0]; wynik mnożenia xH^T = [0].\n",
            "-> ciąg informacyjny [0 0 1 0 0 1 1] słowo kodowe x = [0 0 1 0 0 1 1 1]; wynik mnożenia xH^T = [0].\n",
            "-> ciąg informacyjny [0 0 1 0 1 0 0] słowo kodowe x = [0 0 1 0 1 0 0 0]; wynik mnożenia xH^T = [0].\n",
            "-> ciąg informacyjny [0 0 1 0 1 0 1] słowo kodowe x = [0 0 1 0 1 0 1 1]; wynik mnożenia xH^T = [0].\n",
            "-> ciąg informacyjny [0 0 1 0 1 1 0] słowo kodowe x = [0 0 1 0 1 1 0 1]; wynik mnożenia xH^T = [0].\n",
            "-> ciąg informacyjny [0 0 1 0 1 1 1] słowo kodowe x = [0 0 1 0 1 1 1 0]; wynik mnożenia xH^T = [0].\n",
            "-> ciąg informacyjny [0 0 1 1 0 0 0] słowo kodowe x = [0 0 1 1 0 0 0 0]; wynik mnożenia xH^T = [0].\n",
            "-> ciąg informacyjny [0 0 1 1 0 0 1] słowo kodowe x = [0 0 1 1 0 0 1 1]; wynik mnożenia xH^T = [0].\n",
            "-> ciąg informacyjny [0 0 1 1 0 1 0] słowo kodowe x = [0 0 1 1 0 1 0 1]; wynik mnożenia xH^T = [0].\n",
            "-> ciąg informacyjny [0 0 1 1 0 1 1] słowo kodowe x = [0 0 1 1 0 1 1 0]; wynik mnożenia xH^T = [0].\n",
            "-> ciąg informacyjny [0 0 1 1 1 0 0] słowo kodowe x = [0 0 1 1 1 0 0 1]; wynik mnożenia xH^T = [0].\n",
            "-> ciąg informacyjny [0 0 1 1 1 0 1] słowo kodowe x = [0 0 1 1 1 0 1 0]; wynik mnożenia xH^T = [0].\n",
            "-> ciąg informacyjny [0 0 1 1 1 1 0] słowo kodowe x = [0 0 1 1 1 1 0 0]; wynik mnożenia xH^T = [0].\n",
            "-> ciąg informacyjny [0 0 1 1 1 1 1] słowo kodowe x = [0 0 1 1 1 1 1 1]; wynik mnożenia xH^T = [0].\n",
            "-> ciąg informacyjny [0 1 0 0 0 0 0] słowo kodowe x = [0 1 0 0 0 0 0 1]; wynik mnożenia xH^T = [0].\n",
            "-> ciąg informacyjny [0 1 0 0 0 0 1] słowo kodowe x = [0 1 0 0 0 0 1 0]; wynik mnożenia xH^T = [0].\n",
            "-> ciąg informacyjny [0 1 0 0 0 1 0] słowo kodowe x = [0 1 0 0 0 1 0 0]; wynik mnożenia xH^T = [0].\n",
            "-> ciąg informacyjny [0 1 0 0 0 1 1] słowo kodowe x = [0 1 0 0 0 1 1 1]; wynik mnożenia xH^T = [0].\n",
            "-> ciąg informacyjny [0 1 0 0 1 0 0] słowo kodowe x = [0 1 0 0 1 0 0 0]; wynik mnożenia xH^T = [0].\n",
            "-> ciąg informacyjny [0 1 0 0 1 0 1] słowo kodowe x = [0 1 0 0 1 0 1 1]; wynik mnożenia xH^T = [0].\n",
            "-> ciąg informacyjny [0 1 0 0 1 1 0] słowo kodowe x = [0 1 0 0 1 1 0 1]; wynik mnożenia xH^T = [0].\n",
            "-> ciąg informacyjny [0 1 0 0 1 1 1] słowo kodowe x = [0 1 0 0 1 1 1 0]; wynik mnożenia xH^T = [0].\n",
            "-> ciąg informacyjny [0 1 0 1 0 0 0] słowo kodowe x = [0 1 0 1 0 0 0 0]; wynik mnożenia xH^T = [0].\n",
            "-> ciąg informacyjny [0 1 0 1 0 0 1] słowo kodowe x = [0 1 0 1 0 0 1 1]; wynik mnożenia xH^T = [0].\n",
            "-> ciąg informacyjny [0 1 0 1 0 1 0] słowo kodowe x = [0 1 0 1 0 1 0 1]; wynik mnożenia xH^T = [0].\n",
            "-> ciąg informacyjny [0 1 0 1 0 1 1] słowo kodowe x = [0 1 0 1 0 1 1 0]; wynik mnożenia xH^T = [0].\n",
            "-> ciąg informacyjny [0 1 0 1 1 0 0] słowo kodowe x = [0 1 0 1 1 0 0 1]; wynik mnożenia xH^T = [0].\n",
            "-> ciąg informacyjny [0 1 0 1 1 0 1] słowo kodowe x = [0 1 0 1 1 0 1 0]; wynik mnożenia xH^T = [0].\n",
            "-> ciąg informacyjny [0 1 0 1 1 1 0] słowo kodowe x = [0 1 0 1 1 1 0 0]; wynik mnożenia xH^T = [0].\n",
            "-> ciąg informacyjny [0 1 0 1 1 1 1] słowo kodowe x = [0 1 0 1 1 1 1 1]; wynik mnożenia xH^T = [0].\n",
            "-> ciąg informacyjny [0 1 1 0 0 0 0] słowo kodowe x = [0 1 1 0 0 0 0 0]; wynik mnożenia xH^T = [0].\n",
            "-> ciąg informacyjny [0 1 1 0 0 0 1] słowo kodowe x = [0 1 1 0 0 0 1 1]; wynik mnożenia xH^T = [0].\n",
            "-> ciąg informacyjny [0 1 1 0 0 1 0] słowo kodowe x = [0 1 1 0 0 1 0 1]; wynik mnożenia xH^T = [0].\n",
            "-> ciąg informacyjny [0 1 1 0 0 1 1] słowo kodowe x = [0 1 1 0 0 1 1 0]; wynik mnożenia xH^T = [0].\n",
            "-> ciąg informacyjny [0 1 1 0 1 0 0] słowo kodowe x = [0 1 1 0 1 0 0 1]; wynik mnożenia xH^T = [0].\n",
            "-> ciąg informacyjny [0 1 1 0 1 0 1] słowo kodowe x = [0 1 1 0 1 0 1 0]; wynik mnożenia xH^T = [0].\n",
            "-> ciąg informacyjny [0 1 1 0 1 1 0] słowo kodowe x = [0 1 1 0 1 1 0 0]; wynik mnożenia xH^T = [0].\n",
            "-> ciąg informacyjny [0 1 1 0 1 1 1] słowo kodowe x = [0 1 1 0 1 1 1 1]; wynik mnożenia xH^T = [0].\n",
            "-> ciąg informacyjny [0 1 1 1 0 0 0] słowo kodowe x = [0 1 1 1 0 0 0 1]; wynik mnożenia xH^T = [0].\n",
            "-> ciąg informacyjny [0 1 1 1 0 0 1] słowo kodowe x = [0 1 1 1 0 0 1 0]; wynik mnożenia xH^T = [0].\n",
            "-> ciąg informacyjny [0 1 1 1 0 1 0] słowo kodowe x = [0 1 1 1 0 1 0 0]; wynik mnożenia xH^T = [0].\n",
            "-> ciąg informacyjny [0 1 1 1 0 1 1] słowo kodowe x = [0 1 1 1 0 1 1 1]; wynik mnożenia xH^T = [0].\n",
            "-> ciąg informacyjny [0 1 1 1 1 0 0] słowo kodowe x = [0 1 1 1 1 0 0 0]; wynik mnożenia xH^T = [0].\n",
            "-> ciąg informacyjny [0 1 1 1 1 0 1] słowo kodowe x = [0 1 1 1 1 0 1 1]; wynik mnożenia xH^T = [0].\n",
            "-> ciąg informacyjny [0 1 1 1 1 1 0] słowo kodowe x = [0 1 1 1 1 1 0 1]; wynik mnożenia xH^T = [0].\n",
            "-> ciąg informacyjny [0 1 1 1 1 1 1] słowo kodowe x = [0 1 1 1 1 1 1 0]; wynik mnożenia xH^T = [0].\n",
            "-> ciąg informacyjny [1 0 0 0 0 0 0] słowo kodowe x = [1 0 0 0 0 0 0 1]; wynik mnożenia xH^T = [0].\n",
            "-> ciąg informacyjny [1 0 0 0 0 0 1] słowo kodowe x = [1 0 0 0 0 0 1 0]; wynik mnożenia xH^T = [0].\n",
            "-> ciąg informacyjny [1 0 0 0 0 1 0] słowo kodowe x = [1 0 0 0 0 1 0 0]; wynik mnożenia xH^T = [0].\n",
            "-> ciąg informacyjny [1 0 0 0 0 1 1] słowo kodowe x = [1 0 0 0 0 1 1 1]; wynik mnożenia xH^T = [0].\n",
            "-> ciąg informacyjny [1 0 0 0 1 0 0] słowo kodowe x = [1 0 0 0 1 0 0 0]; wynik mnożenia xH^T = [0].\n",
            "-> ciąg informacyjny [1 0 0 0 1 0 1] słowo kodowe x = [1 0 0 0 1 0 1 1]; wynik mnożenia xH^T = [0].\n",
            "-> ciąg informacyjny [1 0 0 0 1 1 0] słowo kodowe x = [1 0 0 0 1 1 0 1]; wynik mnożenia xH^T = [0].\n",
            "-> ciąg informacyjny [1 0 0 0 1 1 1] słowo kodowe x = [1 0 0 0 1 1 1 0]; wynik mnożenia xH^T = [0].\n",
            "-> ciąg informacyjny [1 0 0 1 0 0 0] słowo kodowe x = [1 0 0 1 0 0 0 0]; wynik mnożenia xH^T = [0].\n",
            "-> ciąg informacyjny [1 0 0 1 0 0 1] słowo kodowe x = [1 0 0 1 0 0 1 1]; wynik mnożenia xH^T = [0].\n",
            "-> ciąg informacyjny [1 0 0 1 0 1 0] słowo kodowe x = [1 0 0 1 0 1 0 1]; wynik mnożenia xH^T = [0].\n",
            "-> ciąg informacyjny [1 0 0 1 0 1 1] słowo kodowe x = [1 0 0 1 0 1 1 0]; wynik mnożenia xH^T = [0].\n",
            "-> ciąg informacyjny [1 0 0 1 1 0 0] słowo kodowe x = [1 0 0 1 1 0 0 1]; wynik mnożenia xH^T = [0].\n",
            "-> ciąg informacyjny [1 0 0 1 1 0 1] słowo kodowe x = [1 0 0 1 1 0 1 0]; wynik mnożenia xH^T = [0].\n",
            "-> ciąg informacyjny [1 0 0 1 1 1 0] słowo kodowe x = [1 0 0 1 1 1 0 0]; wynik mnożenia xH^T = [0].\n",
            "-> ciąg informacyjny [1 0 0 1 1 1 1] słowo kodowe x = [1 0 0 1 1 1 1 1]; wynik mnożenia xH^T = [0].\n",
            "-> ciąg informacyjny [1 0 1 0 0 0 0] słowo kodowe x = [1 0 1 0 0 0 0 0]; wynik mnożenia xH^T = [0].\n",
            "-> ciąg informacyjny [1 0 1 0 0 0 1] słowo kodowe x = [1 0 1 0 0 0 1 1]; wynik mnożenia xH^T = [0].\n",
            "-> ciąg informacyjny [1 0 1 0 0 1 0] słowo kodowe x = [1 0 1 0 0 1 0 1]; wynik mnożenia xH^T = [0].\n",
            "-> ciąg informacyjny [1 0 1 0 0 1 1] słowo kodowe x = [1 0 1 0 0 1 1 0]; wynik mnożenia xH^T = [0].\n",
            "-> ciąg informacyjny [1 0 1 0 1 0 0] słowo kodowe x = [1 0 1 0 1 0 0 1]; wynik mnożenia xH^T = [0].\n",
            "-> ciąg informacyjny [1 0 1 0 1 0 1] słowo kodowe x = [1 0 1 0 1 0 1 0]; wynik mnożenia xH^T = [0].\n",
            "-> ciąg informacyjny [1 0 1 0 1 1 0] słowo kodowe x = [1 0 1 0 1 1 0 0]; wynik mnożenia xH^T = [0].\n",
            "-> ciąg informacyjny [1 0 1 0 1 1 1] słowo kodowe x = [1 0 1 0 1 1 1 1]; wynik mnożenia xH^T = [0].\n",
            "-> ciąg informacyjny [1 0 1 1 0 0 0] słowo kodowe x = [1 0 1 1 0 0 0 1]; wynik mnożenia xH^T = [0].\n",
            "-> ciąg informacyjny [1 0 1 1 0 0 1] słowo kodowe x = [1 0 1 1 0 0 1 0]; wynik mnożenia xH^T = [0].\n",
            "-> ciąg informacyjny [1 0 1 1 0 1 0] słowo kodowe x = [1 0 1 1 0 1 0 0]; wynik mnożenia xH^T = [0].\n",
            "-> ciąg informacyjny [1 0 1 1 0 1 1] słowo kodowe x = [1 0 1 1 0 1 1 1]; wynik mnożenia xH^T = [0].\n",
            "-> ciąg informacyjny [1 0 1 1 1 0 0] słowo kodowe x = [1 0 1 1 1 0 0 0]; wynik mnożenia xH^T = [0].\n",
            "-> ciąg informacyjny [1 0 1 1 1 0 1] słowo kodowe x = [1 0 1 1 1 0 1 1]; wynik mnożenia xH^T = [0].\n",
            "-> ciąg informacyjny [1 0 1 1 1 1 0] słowo kodowe x = [1 0 1 1 1 1 0 1]; wynik mnożenia xH^T = [0].\n",
            "-> ciąg informacyjny [1 0 1 1 1 1 1] słowo kodowe x = [1 0 1 1 1 1 1 0]; wynik mnożenia xH^T = [0].\n",
            "-> ciąg informacyjny [1 1 0 0 0 0 0] słowo kodowe x = [1 1 0 0 0 0 0 0]; wynik mnożenia xH^T = [0].\n",
            "-> ciąg informacyjny [1 1 0 0 0 0 1] słowo kodowe x = [1 1 0 0 0 0 1 1]; wynik mnożenia xH^T = [0].\n",
            "-> ciąg informacyjny [1 1 0 0 0 1 0] słowo kodowe x = [1 1 0 0 0 1 0 1]; wynik mnożenia xH^T = [0].\n",
            "-> ciąg informacyjny [1 1 0 0 0 1 1] słowo kodowe x = [1 1 0 0 0 1 1 0]; wynik mnożenia xH^T = [0].\n",
            "-> ciąg informacyjny [1 1 0 0 1 0 0] słowo kodowe x = [1 1 0 0 1 0 0 1]; wynik mnożenia xH^T = [0].\n",
            "-> ciąg informacyjny [1 1 0 0 1 0 1] słowo kodowe x = [1 1 0 0 1 0 1 0]; wynik mnożenia xH^T = [0].\n",
            "-> ciąg informacyjny [1 1 0 0 1 1 0] słowo kodowe x = [1 1 0 0 1 1 0 0]; wynik mnożenia xH^T = [0].\n",
            "-> ciąg informacyjny [1 1 0 0 1 1 1] słowo kodowe x = [1 1 0 0 1 1 1 1]; wynik mnożenia xH^T = [0].\n",
            "-> ciąg informacyjny [1 1 0 1 0 0 0] słowo kodowe x = [1 1 0 1 0 0 0 1]; wynik mnożenia xH^T = [0].\n",
            "-> ciąg informacyjny [1 1 0 1 0 0 1] słowo kodowe x = [1 1 0 1 0 0 1 0]; wynik mnożenia xH^T = [0].\n",
            "-> ciąg informacyjny [1 1 0 1 0 1 0] słowo kodowe x = [1 1 0 1 0 1 0 0]; wynik mnożenia xH^T = [0].\n",
            "-> ciąg informacyjny [1 1 0 1 0 1 1] słowo kodowe x = [1 1 0 1 0 1 1 1]; wynik mnożenia xH^T = [0].\n",
            "-> ciąg informacyjny [1 1 0 1 1 0 0] słowo kodowe x = [1 1 0 1 1 0 0 0]; wynik mnożenia xH^T = [0].\n",
            "-> ciąg informacyjny [1 1 0 1 1 0 1] słowo kodowe x = [1 1 0 1 1 0 1 1]; wynik mnożenia xH^T = [0].\n",
            "-> ciąg informacyjny [1 1 0 1 1 1 0] słowo kodowe x = [1 1 0 1 1 1 0 1]; wynik mnożenia xH^T = [0].\n",
            "-> ciąg informacyjny [1 1 0 1 1 1 1] słowo kodowe x = [1 1 0 1 1 1 1 0]; wynik mnożenia xH^T = [0].\n",
            "-> ciąg informacyjny [1 1 1 0 0 0 0] słowo kodowe x = [1 1 1 0 0 0 0 1]; wynik mnożenia xH^T = [0].\n",
            "-> ciąg informacyjny [1 1 1 0 0 0 1] słowo kodowe x = [1 1 1 0 0 0 1 0]; wynik mnożenia xH^T = [0].\n",
            "-> ciąg informacyjny [1 1 1 0 0 1 0] słowo kodowe x = [1 1 1 0 0 1 0 0]; wynik mnożenia xH^T = [0].\n",
            "-> ciąg informacyjny [1 1 1 0 0 1 1] słowo kodowe x = [1 1 1 0 0 1 1 1]; wynik mnożenia xH^T = [0].\n",
            "-> ciąg informacyjny [1 1 1 0 1 0 0] słowo kodowe x = [1 1 1 0 1 0 0 0]; wynik mnożenia xH^T = [0].\n",
            "-> ciąg informacyjny [1 1 1 0 1 0 1] słowo kodowe x = [1 1 1 0 1 0 1 1]; wynik mnożenia xH^T = [0].\n",
            "-> ciąg informacyjny [1 1 1 0 1 1 0] słowo kodowe x = [1 1 1 0 1 1 0 1]; wynik mnożenia xH^T = [0].\n",
            "-> ciąg informacyjny [1 1 1 0 1 1 1] słowo kodowe x = [1 1 1 0 1 1 1 0]; wynik mnożenia xH^T = [0].\n",
            "-> ciąg informacyjny [1 1 1 1 0 0 0] słowo kodowe x = [1 1 1 1 0 0 0 0]; wynik mnożenia xH^T = [0].\n",
            "-> ciąg informacyjny [1 1 1 1 0 0 1] słowo kodowe x = [1 1 1 1 0 0 1 1]; wynik mnożenia xH^T = [0].\n",
            "-> ciąg informacyjny [1 1 1 1 0 1 0] słowo kodowe x = [1 1 1 1 0 1 0 1]; wynik mnożenia xH^T = [0].\n",
            "-> ciąg informacyjny [1 1 1 1 0 1 1] słowo kodowe x = [1 1 1 1 0 1 1 0]; wynik mnożenia xH^T = [0].\n",
            "-> ciąg informacyjny [1 1 1 1 1 0 0] słowo kodowe x = [1 1 1 1 1 0 0 1]; wynik mnożenia xH^T = [0].\n",
            "-> ciąg informacyjny [1 1 1 1 1 0 1] słowo kodowe x = [1 1 1 1 1 0 1 0]; wynik mnożenia xH^T = [0].\n",
            "-> ciąg informacyjny [1 1 1 1 1 1 0] słowo kodowe x = [1 1 1 1 1 1 0 0]; wynik mnożenia xH^T = [0].\n",
            "-> ciąg informacyjny [1 1 1 1 1 1 1] słowo kodowe x = [1 1 1 1 1 1 1 1]; wynik mnożenia xH^T = [0].\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "# Kod z powtarzaniem jako kod liniowy\n",
        "\n",
        "Najbardziej prymitywny kod korekcyjny to kod z powtarzaniem. Polega na $(n-1)$-krotnym powtórzeniu symbolu, tzn. na jeden bit informacyjny przypada $n-1$ identycznych z nim bitów kontrolnych (innymi słowy: na jedną pozycję informacyjną / jeden symbol informacyjny przypada $n-1$ pozycji / symboli kontrolnych):\n",
        "\n",
        "$$ x_1 = x_2 $$\n",
        "$$ x_1 = x_3 $$\n",
        "$$ x_1 = x_4 $$\n",
        "$$ \\vdots $$\n",
        "$$ x_1 = x_n $$\n",
        "\n",
        "czyli:\n",
        "\n",
        "$$ x_1 \\oplus x_2 = 0 $$\n",
        "$$ x_1 \\oplus x_3 = 0 $$\n",
        "$$ x_1 \\oplus x_4 = 0 $$\n",
        "$$ \\vdots $$\n",
        "$$ x_1 \\oplus x_n = 0 $$\n",
        "\n",
        "a więc macierz kontrolna dla takiego kodu o parametrach $(n,1)$ przyjmuje formę:\n",
        "\n",
        "$$\\mathbf{H} = \\begin{bmatrix} 1 & 1 & 0 & 0 & \\cdots & 0 & 0 \\\\ 1 & 0 & 1 & 0 & \\cdots & 0 & 0 \\\\ 1 & 0 & 0 & 1 & \\cdots & 0 & 0 \\\\  &  &  &  & \\ddots & & \\\\ 1 & 0 & 0 & 0 & \\cdots & 1 & 0 \\\\ 1 & 0 & 0 & 0 & \\cdots & 0 & 1 \\end{bmatrix}$$\n",
        "\n",
        "Kod z powtarzaniem może oczywiście polegać na wielokrotnym powtarzaniu całego bloku bitów, np. dla trzech powtórzeń:\n",
        "\n",
        "$$111 \\rightarrow 111\\,111\\,111\\,111$$\n",
        "$$0101 \\rightarrow 0101\\,0101\\,0101\\,0101$$\n",
        "\n",
        "jednakże w takim przypadku nie da się go w jednolity sposób przedstawić jako kodu $(n,k)$.\n",
        "\n",
        "Kod z powtarzaniem o parametrach $(n,1)$ pozwala nam bezbłędnie korygować wszystkie przekłamania aż do $\\lfloor \\frac{n}{2} \\rfloor$-krotnych."
      ],
      "metadata": {
        "id": "AljbKljWEt1P"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "#@title  { run: \"auto\" }\n",
        "#@markdown Macierz generująca kodu z powtarzaniem\n",
        "\n",
        "#@markdown Wprowadź $n$:\n",
        "n = 5 #@param {type:\"integer\"}\n",
        "\n",
        "assert n>1, \"to ma być kod z powtarzaniem\"\n",
        "\n",
        "H = np.concatenate((np.ones((n-1,1)),np.eye(n-1)), axis=1).astype(int)\n",
        "\n",
        "G, k = G_z_H(H)\n",
        "\n",
        "print(\"*\"*100)\n",
        "print(\"Sprawdźmy, czy poprawnie koduje: \")\n",
        "for i in range(2**k):\n",
        "  u = np.array([int(x) for x in np.binary_repr(i, width=k)])\n",
        "  x = np.matmul(u,G) % 2\n",
        "  s = np.matmul(x,H.T) % 2\n",
        "  print(f\"-> ciąg informacyjny {u} słowo kodowe x = {x}; wynik mnożenia xH^T = {s}.\")"
      ],
      "metadata": {
        "id": "CzJ83wdBVQS3",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "f00a2a90-d122-4c7a-a036-b17da0c860a0"
      },
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "Kod (5,1)\n",
            "Dla macierzy kontrolnej H = \n",
            "[[1 1 0 0 0]\n",
            " [1 0 1 0 0]\n",
            " [1 0 0 1 0]\n",
            " [1 0 0 0 1]]\n",
            "podmacierz P = \n",
            "[[1]\n",
            " [1]\n",
            " [1]\n",
            " [1]]\n",
            "zatem macierz generująca G = \n",
            "[[1 1 1 1 1]]\n",
            "****************************************************************************************************\n",
            "Sprawdźmy, czy poprawnie koduje: \n",
            "-> ciąg informacyjny [0] słowo kodowe x = [0 0 0 0 0]; wynik mnożenia xH^T = [0 0 0 0].\n",
            "-> ciąg informacyjny [1] słowo kodowe x = [1 1 1 1 1]; wynik mnożenia xH^T = [0 0 0 0].\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "# Kod Hamminga: kod liniowy szczelnie upakowany\n",
        "\n",
        "Kod Hamminga charakteryzuje się macierzą kontrolną, którą tworzą reprezentacje binarne kolejnych liczb. Parametry kodu to dla dowolnego $m \\geq 3$: $(2^m-1,2^m-1-m)$. Zatem długość słowa kodowego $n= 2^m-1$, liczba symboli informacyjnych to $k = 2^m-1-m$, zaś symboli kontrolnych jest w tym przypadku $n-k = m$. Najprostszy taki kod ma parametry $(7,4)$ i macierz kontrolną:\n",
        "\n",
        "$$  \n",
        "  \\mathbf{H} = \\begin{bmatrix} \n",
        "    0 & 0 & 0 & 1 & 1 & 1 & 1 \\\\                              \n",
        "    0 & 1 & 1 & 0 & 0 & 1 & 1 \\\\\n",
        "    1 & 0 & 1 & 0 & 1 & 0 & 1\n",
        "  \\end{bmatrix} \n",
        "  \\Longrightarrow\n",
        "  \\begin{cases}\n",
        "    x_4 \\oplus x_5 \\oplus x_6 \\oplus x_7 = 0 \\\\\n",
        "    x_2 \\oplus x_3 \\oplus x_6 \\oplus x_7 = 0 \\\\\n",
        "    x_1 \\oplus x_3 \\oplus x_5 \\oplus x_7 = 0\n",
        "  \\end{cases}\n",
        "  \\Longrightarrow\n",
        "  \\begin{cases}\n",
        "    x_4 = x_5 \\oplus x_6 \\oplus x_7 \\\\\n",
        "    x_2 = x_3 \\oplus x_6 \\oplus x_7 \\\\\n",
        "    x_1 = x_3 \\oplus x_5 \\oplus x_7\n",
        "  \\end{cases}\n",
        "$$\n",
        "\n",
        "Mnemotechnicznie - patrząc od prawej strony od dołu:\n",
        "*   w ostatnim rzędzie mamy naprzemiennie jedynkę z zerem,\n",
        "*   w następnym rzędzie mamy naprzemiennie dwie jedynki z dwoma zerami,\n",
        "*   w następnym rzędzie mamy naprzemiennie cztery jedynki...\n",
        "W ogólności w rzędzie nr $i$ mamy naprzemiennie $2^{i-1}$ jedynek z $2^{i-1}$ zerami (na końcu zer jest o jedno mniej).\n",
        "\n",
        "Proszę zauważyć, że kolejne kolumny macierzy Hamminga tworzą binarne reprezentacje liczb: $1, 2, 3, \\dots, 2^n-1$. Ze względu na powyższą właściwość korekta jest prosta: wartość syndromu (w postaci liczby binarnej) mówi, którą pozycję skorygować.\n",
        "\n",
        "Korygować można tylko jedną pozycję ($t=1$), ponieważ minimalna odległość Hamminga dla kodu Hamminga wynosi $d_{\\min} = 1$ (można to sprawdzić na macierzy kontrolnej: wszystkie kolumny są różne, a da się dobrać trzy różne kolumny sumujące się do $\\begin{bmatrix} 0 \\\\ 0 \\\\ 0 \\end{bmatrix}$).\n",
        "\n",
        "W przypadku kodu Hamminga pozycje informacyjne oraz kontrolne są wymieszane (jest to tzw. kod niesystematyczny), ale i tak można poznać, które pozycje są kontrolne: to pozycji związane z kolumnami, które zawierają tylko jedną jedynkę (czyli pozycje, które występują w jednym równaniu kontrolnym, które je wyznacza)."
      ],
      "metadata": {
        "id": "zm4x4FoqEwWb"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "Najpierw znajdźmy wszystkie słowa kodowe kodu Hamminga:"
      ],
      "metadata": {
        "id": "rEXaAK_S2hJO"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "#@title Sprawdźmy, czy konkretne słowo należy do kodu Hamminga $(7,4)$ { run: \"auto\" }\n",
        "#@markdown * Przy okazji od razu zobaczymy, jak działa dekodowanie z syndromem\n",
        "#@markdown * Polecam sprawdzić słowo 1010101 i jego małe modyfikacje\n",
        "\n",
        "def dekodowanie_syndrom(H, y):\n",
        "  syndrom = np.matmul(y,H.T) % 2\n",
        "  print(f\"Podano słowo {y}, syndrom dla tego słowa to {syndrom}, zatem:\")\n",
        "  if sum(syndrom) == 0:\n",
        "    print(\"uznajemy, że nie nastąpiło przekłamanie\")\n",
        "  else:\n",
        "    brak = 8 - len(syndrom)\n",
        "    if brak > 0:\n",
        "      padd = np.zeros(brak, int)\n",
        "      syndrom = np.hstack((padd,syndrom))\n",
        "    pozycja = int(np.packbits(syndrom))\n",
        "    y[pozycja-1] += 1\n",
        "    poprawione = y%2\n",
        "    print(f\"uznajemy, że nastąpiło przekłamanie na pozycji {pozycja} i poprawne słowo kodowe to {poprawione}\")\n",
        "\n",
        "#@markdown Wprowadź ciąg binarny:\n",
        "slowo = '1010101' #@param {type:\"string\"}\n",
        "\n",
        "assert len(slowo) == 7, \"Oczekiwane słowo o długości 7\"\n",
        "\n",
        "H = np.array(\n",
        "    [\n",
        "        [0, 0, 0, 1, 1, 1, 1],\n",
        "        [0, 1, 1, 0, 0, 1, 1],\n",
        "        [1, 0, 1, 0, 1, 0, 1]\n",
        "    ]\n",
        ")\n",
        "\n",
        "print(f\"Macierz kontrolna kodu Hamminga (7,4):\\n{H}\")\n",
        "\n",
        "y = np.array([int(x) for x in slowo])\n",
        "dekodowanie_syndrom(H, y) "
      ],
      "metadata": {
        "id": "G64GQPDbBfNH",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "16d539b1-5031-4038-da61-9d4d8fa11c05"
      },
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "Macierz kontrolna kodu Hamminga (7,4):\n",
            "[[0 0 0 1 1 1 1]\n",
            " [0 1 1 0 0 1 1]\n",
            " [1 0 1 0 1 0 1]]\n",
            "Podano słowo [1 0 1 0 1 0 1], syndrom dla tego słowa to [0 0 0], zatem:\n",
            "uznajemy, że nie nastąpiło przekłamanie\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "Warto się pobawić z kodami Hamminga wyższych rzędów..."
      ],
      "metadata": {
        "id": "pWufNUP4VkGL"
      }
    }
  ]
}