Last active
March 19, 2021 13:04
-
-
Save glbter/258df7e0f7911fdb88c4974f9d3bb63d to your computer and use it in GitHub Desktop.
Hamming code - theory of information and encoding
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
{ | |
"cells": [ | |
{ | |
"cell_type": "code", | |
"execution_count": 1, | |
"id": "happy-cuisine", | |
"metadata": {}, | |
"outputs": [], | |
"source": [ | |
"from functools import reduce\n", | |
"import operator as op" | |
] | |
}, | |
{ | |
"cell_type": "markdown", | |
"id": "signed-bowling", | |
"metadata": {}, | |
"source": [ | |
"### Hamming code class" | |
] | |
}, | |
{ | |
"cell_type": "code", | |
"execution_count": 2, | |
"id": "variable-establishment", | |
"metadata": {}, | |
"outputs": [], | |
"source": [ | |
"class HammingCode:\n", | |
"\n", | |
" @staticmethod\n", | |
" def pow_two(max):\n", | |
" n = 0.5\n", | |
" while (n := n * 2) <= max:\n", | |
" yield int(n)\n", | |
"\n", | |
" @staticmethod\n", | |
" def dispatch(bits):\n", | |
" bits = bits.copy()\n", | |
" err = reduce(op.xor, (n for n, bit in enumerate(bits, 1) if bit))\n", | |
" bits[err - 1] = int(not bits[err - 1])\n", | |
" return bits\n", | |
"\n", | |
" @staticmethod\n", | |
" def encode(bits):\n", | |
" bits = bits.copy()\n", | |
" for n in HammingCode.pow_two(len(bits)):\n", | |
" bits.insert(n - 1, 0)\n", | |
"\n", | |
" for p in HammingCode.pow_two(len(bits)):\n", | |
" bits[p-1] = reduce(op.xor, (bit for n, bit in enumerate(bits, 1) if (n // p) % 2))\n", | |
" return bits\n", | |
"\n", | |
" @staticmethod\n", | |
" def decode(bits):\n", | |
" bits = HammingCode.dispatch(bits)\n", | |
" return [bit for n, bit in enumerate(bits, 1) if (n & (n - 1)) != 0]\n" | |
] | |
}, | |
{ | |
"cell_type": "markdown", | |
"id": "naked-identity", | |
"metadata": {}, | |
"source": [ | |
"`(n // p)` gives the number of block in line and `& 2` checks if it is a pair block \n", | |
"`num & (num - 1)` does a bitwise check, like 1000 & 0100 = 0000, and 1001 & 1000 = 1000\n", | |
"\n", | |
"$ \\begin{pmatrix}\n", | |
"0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1\\\\ \n", | |
"0 & 0 & 0 & 1 & 1 & 1 & 1 & 0 & 0 & 0 & 0 & 1 & 1 & 1 & 1\\\\ \n", | |
"0 & 1 & 1 & 0 & 0 & 1 & 1 & 0 & 0 & 1 & 1 & 0 & 0 & 1 & 1\\\\ \n", | |
"1 & 0 & 1 & 0 & 1 & 0 & 1 & 0 & 1 & 0 & 1 & 0 & 1 & 0 & 1\\\\\n", | |
"\\end{pmatrix} $" | |
] | |
}, | |
{ | |
"cell_type": "markdown", | |
"id": "mineral-petroleum", | |
"metadata": {}, | |
"source": [ | |
"### Tests" | |
] | |
}, | |
{ | |
"cell_type": "code", | |
"execution_count": 3, | |
"id": "recognized-satellite", | |
"metadata": {}, | |
"outputs": [], | |
"source": [ | |
"A_vector = [1, 0, 0, 1, 1, 0, 0, 0, 1, 0, 0]\n", | |
"X_vector = [0, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 0]\n", | |
"Y_vector = [0, 0, 1, 0, 1, 0, 1, 0, 1, 0, 0, 0, 1, 0, 0]\n", | |
"A = [1, 1, 0, 0]\n", | |
"X = [0, 1, 1, 1, 1, 0, 0]" | |
] | |
}, | |
{ | |
"cell_type": "code", | |
"execution_count": 4, | |
"id": "aggressive-samoa", | |
"metadata": { | |
"scrolled": true | |
}, | |
"outputs": [ | |
{ | |
"name": "stdout", | |
"output_type": "stream", | |
"text": [ | |
"decoded message with error: [1, 0, 0, 1, 1, 0, 0, 0, 1, 0, 0]\n", | |
"original message : [1, 0, 0, 1, 1, 0, 0, 0, 1, 0, 0]\n" | |
] | |
} | |
], | |
"source": [ | |
"print(f\"decoded message with error: {HammingCode.decode(Y_vector)}\")\n", | |
"print(f\"original message : {A_vector}\")" | |
] | |
}, | |
{ | |
"cell_type": "code", | |
"execution_count": 5, | |
"id": "middle-title", | |
"metadata": {}, | |
"outputs": [ | |
{ | |
"name": "stdout", | |
"output_type": "stream", | |
"text": [ | |
"encoded message by python: [0, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 0]\n", | |
"encoded message by matrix: [0, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 0]\n" | |
] | |
} | |
], | |
"source": [ | |
"print(f\"encoded message by python: {HammingCode.encode(A_vector)}\")\n", | |
"print(f\"encoded message by matrix: {X_vector}\")" | |
] | |
}, | |
{ | |
"cell_type": "code", | |
"execution_count": 6, | |
"id": "chronic-belize", | |
"metadata": {}, | |
"outputs": [ | |
{ | |
"name": "stdout", | |
"output_type": "stream", | |
"text": [ | |
"encoded message by python: [0, 1, 1, 1, 1, 0, 0]\n", | |
"encoded message by matrix: [0, 1, 1, 1, 1, 0, 0]\n" | |
] | |
} | |
], | |
"source": [ | |
"print(f\"encoded message by python: {HammingCode.encode(A)}\")\n", | |
"print(f\"encoded message by matrix: {X}\")" | |
] | |
} | |
], | |
"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.8.8" | |
} | |
}, | |
"nbformat": 4, | |
"nbformat_minor": 5 | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment