day 42 - hamming codes.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "import numpy as np"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## algorithm"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def encode(parity_bits, data):\n",
    "    n = len(data) + parity_bits\n",
    "    assert 2 ** parity_bits == n + 1\n",
    "\n",
    "    # copy data to code\n",
    "    code = np.zeros(n, dtype=int)\n",
    "    code[np.arange(n) & np.arange(n) + 1 > 0] = data\n",
    "\n",
    "    # parity mask\n",
    "    mask = np.zeros(n, dtype=int)\n",
    "    mask[::2] = 1\n",
    "\n",
    "    # compute parity\n",
    "    i = 0\n",
    "    while i < n:\n",
    "        code[i] = code[i:][mask == 1].sum() & 1\n",
    "        i += i + 1\n",
    "        mask = np.repeat(mask, 2)[:n - i]\n",
    "\n",
    "    # result\n",
    "    return code"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def decode(code):\n",
    "    n = len(code)\n",
    "\n",
    "    # parity mask\n",
    "    mask = np.zeros(n, dtype=int)\n",
    "    mask[::2] = 1\n",
    "\n",
    "    # compute parity\n",
    "    error, i = -1, 0\n",
    "    while i < n:\n",
    "        error += (i + 1) * (code[i:][mask == 1].sum() & 1)\n",
    "        i += i + 1\n",
    "        mask = np.repeat(mask, 2)[:n - i]\n",
    "\n",
    "    # fix error\n",
    "    if error >= 0:\n",
    "        code[error] ^= 1\n",
    "\n",
    "    # get data from code\n",
    "    data = code[np.arange(n) & np.arange(n) + 1 > 0]\n",
    "\n",
    "    # result\n",
    "    return error, data"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## encoding"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "hamming code [1 0 0 1] -> [0 0 1 1 0 0 1]\n",
      "with error [0 0 1 0 0 0 1]\n",
      "error @ 3 -> [1 0 0 1]\n"
     ]
    }
   ],
   "source": [
    "parity_bits = 3\n",
    "data = np.random.randint(0, 2, 4)\n",
    "\n",
    "# generate code\n",
    "code = encode(parity_bits, data)\n",
    "print('hamming code', data, '->', code)\n",
    "\n",
    "# make error\n",
    "code[3] ^= 1\n",
    "print('with error', code)\n",
    "\n",
    "# reconstruct\n",
    "error, recon = decode(code)\n",
    "print('error @', error, '->', recon)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "hamming code [0 0 0 1 0 0 0 0 1 1 1] -> [1 1 0 0 0 0 1 1 0 0 0 0 1 1 1]\n",
      "with error [1 1 0 0 0 0 1 1 0 0 0 0 1 1 0]\n",
      "error @ 14 -> [0 0 0 1 0 0 0 0 1 1 1]\n"
     ]
    }
   ],
   "source": [
    "parity_bits = 4\n",
    "data = np.random.randint(0, 2, 11)\n",
    "\n",
    "# generate code\n",
    "code = encode(parity_bits, data)\n",
    "print('hamming code', data, '->', code)\n",
    "\n",
    "# make error\n",
    "code[14] ^= 1\n",
    "print('with error', code)\n",
    "\n",
    "# reconstruct\n",
    "error, recon = decode(code)\n",
    "print('error @', error, '->', recon)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  }
 ],
 "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.0"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}