235_qrcode.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## QR-Code\n",
    "\n",
    "QR-Codes wurden 1994 von der japanischen Firma *Denso Wave* zur Markierung von Komponenten für die   Automobilproduktion entwickelt. QR steht für *quick response*.\n",
    "\n",
    "QR-Codes sind quadratische Raster. Sie bestehen aus Funktionsmustern und dem Encodierungsbereich. Die kleinste Einheit ist das Modul, dass hell (0) oder dunkel (1) sein kann.\n",
    "\n",
    "#### Versionen\n",
    "Je nach QR-Code Version besteht der QR-Code aus unterschiedlich vielen Modulen.\n",
    "<img src=\"./img/qrcode2.png\" width=\"601\">"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Patterns und Formatinformation\n",
    "\n",
    "- Finder-Pattern: 3 Stück, 7 Module lang von hellen Modulen umgeben, korrigiert Verdrehungen \n",
    "- Alignment-Pattern: QR-Version 1,2,...,40 enhält 0,1,...,46 Stück. Korrigiert\n",
    "Verzerrungen (unebene Flächen, Aufnahme von der Seite etc.) \n",
    "- Timing-Pattern: 2 Stück von Spalte 6, Zeile 6 horizontal und vertikal, abwechselnd helle und dunkle Module, zur Bestimmung der Koordinaten der einzelnen Module (oben links: (0/0).  \n",
    "- Formatinformation: 31 Module\n",
    "\n",
    "\n",
    "<img src=\"./img/qrcode1.png\" width=\"701\">\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Die Formatinformationen umfassen 15 Bit und enthalten Informationen zum Fehlerkorrekturniveau und zur verwendeten Maske. Da ohne Formatinformationen der QR-Code nicht decodiert werden kann, werden diese Informationen immer doppelt dargestellt. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Codewörter\n",
    "\n",
    "Der Encodierungsbereich enthält 8-Bit Codewörter (CW) für Daten und Fehlerkorrektur. \n",
    "\n",
    "Stößt ein CW an eine Grenze, wird die Richtung umgekehrt und das CW in die benachbarten Spalten eingetragen. \n",
    "Kommt es zu einer Behinderung durch ein Funktionsmuster, umfließt das CW das Muster. Innerhalb eines CW werden die Bits immer von rechts nach links gelesen.\n",
    "\n",
    "Das Beispiel zeigt Anordnung und Ausrichtung der CW bei QR-Code V2, Fehlerkorrekturniveau M. \n",
    "\n",
    "<img src=\"./img/qrcode10.png\" width=\"701\">\n",
    "\n",
    "Die Berechnung der Fehlerkorrektur CW verlangt eine aufwendige Polynomdivision."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Modus und CCI\n",
    "\n",
    "Die Datenkapazität (d.h. die Anzahl der darstellbaren Zeichen) ist vom verwendeten *Modus* abhängig. Er wird durch eine 4 Bit lange Sequenz (Mode-Indikator) innerhalb des ersten Daten-CW festgelegt (rechts unten).\n",
    "\n",
    "Danach folgt die *CCI*-Sequenz, die angibt. wieviele Zeichen kodiert sind.\n",
    "\n",
    "<img src=\"./img/qrcode12.png\" width=\"601\">\n",
    "\n",
    "#### Masken\n",
    "\n",
    "Beim Erzeugen des QR-Codes können im Encodierungs-Bereich Modul-Sequenzen entstehen, die den Funktionsmustern ähneln. Um dies zu korrigieren und um eine gleichmäßige Verteilung von hellen und dunklen Modulen zu erhalten, werden die Module maskiert:  Die CW werden mit den koordinatengleichen Modulen der Maske XOR-verknüpft. \n",
    "\n",
    "Von den verfügbaren Masken wird diejenige gewählt, die die angegebenen Kriterien am besten erfüllt.  \n",
    "\n",
    "In der Maske wird das Modul in Spalte i, Zeile j dunkel gefärbt (=1), wenn der folgenden Ausdruck wahr ist:\n",
    "\n",
    "```\n",
    "Maske 0: (i+j) % 2 == 0\n",
    "Maske 1: j % 2 == 0\n",
    "Maske 2: i % 3 == 0\n",
    "Maske 3: (i+j) % 3 == 0\n",
    "Maske 4: (j//2 +  i//3) % 2 == 0\n",
    "Maske 5: (i*j) % 2 + (i*j) % 3 == 0\n",
    "Maske 6: ((i*j) % 2 + (i*j) % 3) % 2 == 0\n",
    "Maske 7: ((i*j) % 3 + (i+j) % 2) % 2 == 0\n",
    "```\n",
    "\n",
    " __[Maske 0](img/maske21_0.png)__ -\n",
    " __[Maske 1](img/maske21_1.png)__ -\n",
    " __[Maske 2](img/maske21_2.png)__ -\n",
    " __[Maske 5](img/maske21_5.png)__ -\n",
    " __[Maske 6](img/maske21_6.png)__ "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Hilfen zur Decodierung"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Formatinformation\n",
    "\n",
    "<img src=\"./img/qrcode_hilf_04.png\" width=\"501\">"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Modi\n",
    "\n",
    "<img src=\"./img/qrcode_hilf_06.png\" width=\"500\">"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "  <p>Mode-Indikator und CCI\n",
    "    <ul>\n",
    "    <li>Mode-Indikator immer 4 Bit</li>\n",
    "    <li>Modus Byte: CCI 8 Bit lang, dann pro Zeichen 8 Bit</li>\n",
    "    <li>Modus Alphanumeric: CCI 9 Bit lang, dann pro zwei Zeichen 11 Bit.\n",
    "    1. Zeichen: x//45, 2. Zeichen: x%45. Für 1 Zeichen am Ende 6 Bit.</li>\n",
    "    <li>Modus Numeric: CCI 10 Bit lang, dann 10 Bit für je drei Ziffern.\n",
    "    Für 2 bzw 1 Ziffer am Ende: 7 bzw. 4 Bit.</li>\n",
    "\n",
    "  </ul>\n",
    "</p>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Die Masken für die ersten 6 CW:\n",
    "```\n",
    "1001 1001 1001 1001 1001 1001 0110 0110 0110 0110 0110 0110  # Maske  0\n",
    "1100 1100 1100 1100 1100 1100 0011 0011 0011 0011 0011 0011  # Maske  1\n",
    "0000 0000 0000 0000 0000 0000 1010 1010 1010 1010 1010 1010  # Maske  2\n",
    "0110 0001 1000 0110 0001 1000 1001 0010 0100 1001 0010 0100  # Maske  3\n",
    "1100 0011 1100 0011 1100 0011 1001 0110 1001 0110 1001 0110  # Maske  4\n",
    "0000 1100 0010 0000 1100 0010 1010 1011 1010 1010 1011 1010  # Maske  5\n",
    "0111 1100 1010 0111 1100 1010 1011 1111 1010 1011 1111 1010  # Maske  6\n",
    "0000 1011 1101 0000 1011 1101 0110 0010 0111 0110 0010 0111  # Maske  7\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Encodierungs-/Decodierungstabelle für den Modus Alphanumeric \n",
    "\n",
    "<img src=\"./img/qrcode_hilf_12.png\" width=\"600\">\n",
    "\n",
    "Encodierungs-/Decodierungstabelle für den Modus Byte\n",
    "\n",
    "<img src=\"./img/qrcode_hilf_13.png\" width=\"600\">"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Decodierung\n",
    "\n",
    "Zur Decodierung gehen wir wie folgt vor:\n",
    "- Bestimmung der Formatinformation. Damit erhalten wir die Nummer der Maske.\n",
    "- Notation der CW aus dem zu dekodierenen QRCode und der Maske. In den Beispielen reichen die ersten 6 CW.\n",
    "- Ermitteln der demaskierten CW durch Xor-Verknüpfung.\n",
    "- Modus bestimmen, daraus ergibt sich die Länge des CCI.\n",
    "- CCI bestimmen, daraus ermittelt sich die Anzahl der codierten Zeichen.\n",
    "- Dekodieren der Daten mit der zum Modus gehörenden Tabelle."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Beispiel 1:\n",
    "\n",
    "<img src=\"./img/qrcode_07.png\" width=\"500\">"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```\n",
    "Format-Information: 000110100001100  => Fehlerkorrekturniveau H, Maske 6\n",
    "\n",
    "0011 1100 1011 0000 1101 1010 0101 1100 0100 0101 0001 0101  # maskiert\n",
    "0111 1100 1010 0111 1100 1010 1011 1111 1010 1011 1111 1010  # Maske  6\n",
    "0100 0000 0001 0111 0001 0000 1110 0011 1110 1110 1110 1111  # demaskiert\n",
    "\n",
    "Modus: Byte, CCI-Länge: 8 Bit\n",
    "CCI: 0000 0001 = 1 => ein Zeichen wird dargestellt, pro Zeichen 8 Bit\n",
    "1. Zeichen: 0111 0001 = 113 => Es ist das Zeichen q codiert.\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Beispiel 2:\n",
    "\n",
    "<img src=\"./img/qrcode_08.png\" width=\"500\">"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```\n",
    "Format-Information: 001001110111110  => Fehlerkorrekturniveau H, Maske 1\n",
    "\n",
    "1101 1100 1101 1000 1011 0101 0110 0111 0011 0011 1101 1111  # maskiert\n",
    "1100 1100 1100 1100 1100 1100 0011 0011 0011 0011 0011 0011  # Maske  1\n",
    "0001 0000 0001 0100 0111 1001 0101 0100 0000 0000 1110 1100  # demaskiert\n",
    "\n",
    "Modus: numeric, CCI-Länge: 10 Bit\n",
    "CCI: 0000 0001 10 = 5 => 5 Zeichen werden dargestellt, 10 Bit für 3 Zeichen, 7 Bit für 2 Zeichen\n",
    "1. Einheit (10 Bit): 00 0111 1001  => 121\n",
    "2. Einheit (7 Bit): 0101 010 => 42\n",
    "Es ist die Zahl 12142 codiert.\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Beispiel 3:\n",
    "\n",
    "<img src=\"./img/qrcode_09.png\" width=\"500\">"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```\n",
    "Format-Information: 001011010001001  => Fehlerkorrekturniveau H, Maske 0\n",
    "\n",
    "1011 1001 1000 0000 0101 0011 0110 0010 0110 0110 1000 1010  # maskiert\n",
    "1001 1001 1001 1001 1001 1001 0110 0110 0110 0110 0110 0110  # Maske  0\n",
    "0010 0000 0001 1001 1100 1010 0000 0100 0000 0000 1110 1100  # demaskiert\n",
    "\n",
    "Modus: alphanumeric, CCI-Länge: 9 Bit\n",
    "CCI: 0000 0001 1 = 3 Zeichen werden dargestellt, 11 Bit für 2 Zeichen, 6 Bit für 1 Zeichen\n",
    "1. Einheit (11 Bit): 001 1100 1010  => 458\n",
    "458 // 45 = 10, 458 % 45 = 8 \n",
    "2. Einheit (6 Bit): 0000 01 => 1\n",
    "Es ist die Zeichenfolge A81 kodiert. \n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "[Beispiele zum Ausdrucken](img/qrcodes.pdf)"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.5"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}