CSSE3010 - Hamming and Manchester Encoding

csse3010_hamming.js

/*
Hamming and Manchester Encoding example

Author: Joel Addison
Date: March 2013

Functions to do (7,4) hamming encoding and decoding, including error detection
and correction.
Manchester encoding and decoding is also included, and by default will use
least bit ordering for the byte that is to be included in the array.
*/

// List of syndrome positions. SYNDROME_CHECK[pos] will give the
// bit in the provided encoded byte that needs to be fixed
// Note: bit order used is 7 6 5 4 3 2 1 0
var SYNDROME_CHECK = [-1, 6, 5, 0, 4, 1, 2, 3];

/*
 * Extract a bit from a given byte using MS ordering.
 * ie. B7 B6 B5 B4 B3 B2 B1 B0
 */
var extract_bit = function(byte, pos) {
    return (byte >> pos) & 0x01;
};


/*
 * Encode a nibble using Hamming encoding.
 * Nibble is provided in form 0b0000DDDD == 0 0 0 0 D3 D2 D1 D0
 * Encoded byte is in form P H2 H1 H0 D3 D2 D1 D0
 */
var hamming_encode_nibble = function(data) {
    // Get data bits
    var d = [0, 0, 0, 0];
    d[0] = extract_bit(data, 0);
    d[1] = extract_bit(data, 1);
    d[2] = extract_bit(data, 2);
    d[3] = extract_bit(data, 3);

    // Calculate hamming bits
    var h = [0, 0, 0];
    h[0] = (d[1] + d[2] + d[3]) % 2;
    h[1] = (d[0] + d[2] + d[3]) % 2;
    h[2] = (d[0] + d[1] + d[3]) % 2;

    // Calculate parity bit, using even parity
    var p = 0 ^ d[0] ^ d[1] ^ d[2] ^ d[3] ^ h[0] ^ h[1] ^ h[2];

    // Encode byte
    var encoded = (data & 0x0f);
    encoded |= (p << 7) | (h[2] << 6) | (h[1] << 5) | (h[0] << 4);

    return encoded;
};

/*
 * Encodes the given byte using Hamming encoding.
 */
var hamming_encode_byte = function(byte) {
    var ls_nibble = byte & 0x0f;
    var ms_nibble = (byte & 0xf0) >> 4;

    var ls_hamming = hamming_encode_nibble(ls_nibble);
    var ms_hamming = hamming_encode_nibble(ms_nibble);

    return {'ls': ls_hamming, 'ms': ms_hamming};
};

/*
 * Decode a single hamming encoded byte, and return a decoded nibble.
 * Input is in form P H2 H1 H0 D3 D2 D1 D0
 * Decoded nibble is in form 0b0000DDDD == 0 0 0 0 D3 D2 D1 D0
 */
var hamming_decode_byte = function(byte) {
    var error = 0;
    var corrected = 0;

    // Calculate syndrome
    var s = [0, 0, 0];

    // D1 + D2 + D3 + H0
    s[0] = (extract_bit(byte, 1) + extract_bit(byte, 2) +
            extract_bit(byte, 3) + extract_bit(byte, 4)) % 2;

    // D0 + D2 + D3 + H1
    s[1] = (extract_bit(byte, 0) + extract_bit(byte, 2) +
            extract_bit(byte, 3) + extract_bit(byte, 5)) % 2;

    // D0 + D1 + D3 + H2
    s[2] = (extract_bit(byte, 0) + extract_bit(byte, 1) +
            extract_bit(byte, 3) + extract_bit(byte, 6)) % 2;

    var syndrome = (s[0] << 2) | (s[1] << 1) | s[2];

    if (syndrome) {
        // Syndrome is not 0, so correct and log the error
        error += 1;
        byte ^= (1 << SYNDROME_CHECK[syndrome]);
        corrected += 1;
    }

    // Check parity
    var p = 0;
    for (var i = 0; i < 8; ++i) {
        p ^= extract_bit(byte, i);
    }

    if (p != extract_bit(byte, 7)) {
        // Parity bit is wrong, so log error
        if (syndrome) {
            // Parity is wrong and syndrome was also bad, so error is not corrected
            corrected -= 1;
        } else {
            // Parity is wrong and syndrome is fine, so corrected parity bit
            error += 1;
            corrected += 1;
        }
    }

    return {'nibble': (byte & 0x0f), 'error': error, 'corrected': corrected};
};

/*
 * Encode a byte using Manchester encoding. Returns an array of bits.
 * Adds two start bits (1, 1) and one stop bit (0) to the array.
 */
var manchester_encode = function(byte) {
    // Add start bits (encoded 1, 1)
    var manchester_encoded = [0, 1, 0, 1];

    // Encode byte
    for (var i = 7; i >= 0; --i) {
        if (extract_bit(byte, i)) {
            manchester_encoded.push(0);
            manchester_encoded.push(1);
        } else {
            manchester_encoded.push(1);
            manchester_encoded.push(0);
        }
    }

    // Add stop bit (encoded 0)
    manchester_encoded.push(1);
    manchester_encoded.push(0);

    return manchester_encoded;
};

/*
 * Decode a Manchester array to a single data byte.
 */
var manchester_decode = function(manchester_array) {
    var decoded = 0;
    for (var i = 0; i < 8; ++i) {
        bit = 7 - i;
        // Use the second value of each encoded bit, as that is the bit value
        // eg. 1 is encoded to [0, 1], so retrieve the second bit (1)
        decoded |= manchester_array[4 + (i * 2) + 1] << (bit);
    }

    return decoded;
};

/*
 * Decodes two manchester arrays containing hamming encoded nibbles
 * of a single byte. The arrays are each decoded to a byte, most likely
 * hamming encoded.
 * By default, it is assumed the manchester array contains a byte using
 * least bit ordering.
 */
var manchester_decode_byte = function(ls_manchester, ms_manchester, ls_order) {
    if (typeof ls_order === 'undefined') {
        ls_order = true;
    }

    ls_hamming = manchester_decode(ls_manchester);
    ms_hamming = manchester_decode(ms_manchester);

    if (ls_order) {
        ls_hamming = reorder_byte(ls_hamming);
        ms_hamming = reorder_byte(ms_hamming);
    }

    return {'ls': ls_hamming, 'ms': ms_hamming};
};

/*
 * Changes a byte in most significant bit ordering into least significant
 * bit ordering, or vice versa.
 */
var reorder_byte = function(byte) {
    var new_byte = 0;

    for (var i = 0; i < 8; ++i) {
        new_byte |= extract_bit(byte, i) << (7 - i);
    }

    return new_byte;
};

/*
 * Encodes the given byte using Hamming encoding, followed by Manchester
 * encoding.
 * Uses least bit ordering for the Manchester encoding by default.
 */
var encode_byte = function(byte, ls_order) {
    if (typeof ls_order === 'undefined') {
        ls_order = true;
    }

    var hamming = hamming_encode_byte(byte, ls_order);
    var ls_hamming = hamming.ls;
    var ms_hamming = hamming.ms;

    if (ls_order) {
        ls_hamming = reorder_byte(ls_hamming);
        ms_hamming = reorder_byte(ms_hamming);
    }

    var ls_manchester = manchester_encode(ls_hamming);
    var ms_manchester = manchester_encode(ms_hamming);

    return {'ls': ls_manchester, 'ms': ms_manchester};
};

/*
 * Decodes two manchester arrays containing hamming encoded nibbles
 * of a single byte. The arrays are first decoded to a hamming byte, then
 * decoded from the hamming byte to a single nibble. The nibbles are joined
 * to get the final byte.
 * By default, it is assumed the manchester array contains a byte using
 * least bit ordering.
 */
var decode_byte = function(ls_manchester, ms_manchester, ls_order) {
    var decoded = manchester_decode_byte(ls_manchester, ms_manchester, ls_order);

    ls_decoded = hamming_decode_byte(decoded.ls);
    ms_decoded = hamming_decode_byte(decoded.ms);

    return ls_decoded.nibble | (ms_decoded.nibble << 4);
};

/*
 * Adapted from
 * https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/parseInt
 */
var filterInt = function (value) {
  if(/^(0[xX])?([0-9a-fA-F]+)$/.test(value))
    return Number(value);
  return NaN;
};

$(function() {
    $('#encode_results').hide();
    $('#encode_alert').hide();

    $('#encode').submit(function(event) {
        $('#encode_results').hide();
        var input = $('#encode_input').val().trim();
        var format = "binary"; // Default to binary

        if (input === "" || isNaN(filterInt(input))) {
            $('#encode_alert').show();
            return false;
        }

        if (input.lastIndexOf("0x", 0) === 0 || input.lastIndexOf("0X", 0) === 0) {
            // Hex input
            format = "hex";
        }

        if (format === "hex" && input.length !== 4 ||
                format === "binary" && input.length !== 8) {
            $('#encode_alert').show();
            return false;
        } else {
            $('#encode_alert').hide();
        }

        if (format == "binary") {
            input = parseInt(input, 2);
        } else if (format == "hex") {
            input = parseInt(input, 16);
        }

        $('#raw_input').text(input.toString(2) + ' (0x' + input.toString(16) + ')');

        var hamming = hamming_encode_byte(input);
        $('#ls_hamming').text(hamming.ls.toString(2) + ' (0x' + hamming.ls.toString(16) + ')');
        $('#ms_hamming').text(hamming.ms.toString(2) + ' (0x' + hamming.ms.toString(16) + ')');

        var manchester = encode_byte(input);
        $('#ls_manchester').text(manchester.ls.join(''));
        $('#ms_manchester').text(manchester.ms.join(''));

        $('#encode_results').show();

        return false;
    });


    $('#decode').submit(function(event) {
        $('#decode_results').hide();
        var decode_ms = $('#decode_ms').val().trim();
        var decode_ls = $('#decode_ls').val().trim();

        if (decode_ms === "" || decode_ms.length !== 22 || isNaN(filterInt(decode_ms)) ||
                decode_ls === "" || decode_ls.length !== 22 || isNaN(filterInt(decode_ls))) {
            $('#decode_alert').show();
            return false;
        } else {
            $('#decode_alert').hide();
        }

        var ms_array = decode_ms.split('');
        var ls_array = decode_ls.split('');

        var decoded = manchester_decode_byte(ls_array, ms_array);
        $('#decode_ls_manchester').text(decoded.ls.toString(2) + ' (0x' + decoded.ls.toString(16) + ')');
        $('#decode_ms_manchester').text(decoded.ms.toString(2) + ' (0x' + decoded.ms.toString(16) + ')');

        var hamming = decode_byte(ls_array, ms_array);
        $('#decode_hamming').text(hamming.toString(2) + ' (0x' + hamming.toString(16) + ')');

        $('#decode_results').show();

        return false;
    });

});

hamming.html

<!DOCTYPE html>
<html lang="en">
  <head>
    <meta charset="utf-8">
    <meta http-equiv="X-UA-Compatible" content="IE=edge">
    <meta name="viewport" content="width=device-width, initial-scale=1">
    <title>CSSE3010 Hamming Encoding</title>
    <link rel="stylesheet" href="http://netdna.bootstrapcdn.com/bootstrap/3.1.1/css/bootstrap.min.css">
  </head>

  <body>
    <div class="container">
      <div class="row">
        <div class="col-12-sm">
          <h1>CSSE3010 Hamming Encoding</h1>
          <p>Check your hamming and manchester encoding.</p>
        </div>
      </div>

      <div class="row">
        <div class="col-12-sm">
          <h2>Encode Data</h2>
          <div class="alert alert-warning alert-dismissable" id="encode_alert" style="display: none;">
            <button type="button" class="close" data-dismiss="alert" aria-hidden="true">&times;</button>
            <strong>Warning!</strong> Could not use given input as binary or hex.
            Please enter 8 bits for binary, or 2 chars for hex.
          </div>
          <p>
            Enter a single byte to be encoded, first through hamming and then
            through manchester encoding.
          </p>
          <form role="form" id="encode">
            <div class="form-group">
              <label for="encode_input">Input</label>
              <input type="text" class="form-control" name="encode_input" id="encode_input" placeholder="Enter data">
              <span class="help-block">Enter a binary number (8 chars) or hex number preceeded with '0x' (4 chars total).</span>
            </div>
            <button type="submit" class="btn btn-default">Submit</button>
          </form>

          <br>

          <div id="encode_results" class="well" style="display: none;">
            <h4>Input: <code id="raw_input"></code></h4>
            <h4>Hamming Encoded</h4>
            <ul>
              <li>Least significant nibble: <code id="ls_hamming"></code></li>
              <li>Most significant nibble: <code id="ms_hamming"></code></li>
            </ul>
            <h4>Manchester Encoded</h4>
            <p>
              The 22-bit sequence should include "0101" at the start and "10" at the
              end (encoded start [1, 1] and stop bits [0]).
            </p>
            <ul>
              <li>Least significant nibble: <code id="ls_manchester"></code></li>
              <li>Most significant nibble: <code id="ms_manchester"></code></li>
            </ul>
          </div>
        </div>
      </div>

      <div class="row">
        <div class="col-12-sm">
          <h2>Decode Data</h2>
          <div class="alert alert-warning alert-dismissable" id="decode_alert" style="display: none;">
            <button type="button" class="close" data-dismiss="alert" aria-hidden="true">&times;</button>
            <strong>Warning!</strong> Given input was not 22 bits long.
          </div>
          <p>
            Enter two 22-bit manchester encoded sequences, which will first be
            decoded from manchester to a single byte, then hamming decoded.
            The 22-bit sequence should include "0101" at the start and "10" at the
            end (encoded start and stop bits).
          </p>
          <form role="form" id="decode">
            <div class="form-group">
              <label for="decode_ls">Least Significant Nibble</label>
              <input type="text" class="form-control" name="decode_ls" id="decode_ls" placeholder="Enter data">
            </div>
            <div class="form-group">
              <label for="decode_ms">Most Significant Nibble</label>
              <input type="text" class="form-control" name="decode_ms" id="decode_ms" placeholder="Enter data">
            </div>
            <button type="submit" class="btn btn-default">Submit</button>
          </form>

          <br>

          <div id="decode_results" class="well" style="display: none;">
            <h4>Manchester Decoded</h4>
            <ul>
              <li>Least significant nibble: <code id="decode_ls_manchester"></code></li>
              <li>Most significant nibble: <code id="decode_ms_manchester"></code></li>
            </ul>
            <h4>Hamming Decoded</h4>
            <ul>
              <li>Byte: <code id="decode_hamming"></code></li>
            </ul>
          </div>
        </div>
      </div>
    </div>


    <script src="https://ajax.googleapis.com/ajax/libs/jquery/1.11.0/jquery.min.js"></script>
    <script src="http://netdna.bootstrapcdn.com/bootstrap/3.1.1/js/bootstrap.min.js"></script>
    <script src="csse3010_hamming.js"></script>
  </body>
</html>