This video is free to watch - hope you enjoy it! If you like what you see, there's a ton more where that came from...

Sign Up

Correcting Errors in a Digital Transmission, Part 2

In the previous video we saw how we could correct errors using parity bits. In this video we'll orchestrate those bits using some math along with a divide and conquer algorithm to correct single-bit errors in transmissions of any size.

This content is for subscribers only - which you can become in just 30 seconds!

Sign Up

This video contains and algorithm that you could very well be asked about in an interview: The Hamming Code. It’s a deceptively simple algorithm to understand, very difficult to implement (at least for me).

We can use this algorithm to detect whether an error occurred in a digital transmission of any size - knowing precisely where it is and how to correct it.

It’s a fun puzzler and I’ll show you my solution in this video.

The Code

Here’s the code used in the video. There’s always room for improvement - feel free to suggest! Your comments, as always, are welcome and you can drop me an email or, when the code is published, feel free to leave an issue on GitHub.

Here are our utility functions:

const getParityBitPositions = (message) => {
  let matrix={};
  for(let i=1; i <= message.length; i = i * 2) {
    let taken=0; skipped=0;
    matrix[i] = [];
    for(let x = i; x <= message.length; x++){
      if(taken < i) {
        matrix[i].push(x)
        taken+=1;
      }else{
        skipped+=1;
      }
      if(skipped===taken) skipped = taken = 0;
    }
  }
  return matrix;
}

const addParityPlaceholder = function(message){
  const digits= message.split('');
  const matrix = getParityBitPositions(message)
  //add parity bits "_" to positions that are powers of two 
  //as parity bits. (positions 1, 2, 4, 8, 16, 32, 64, etc.)
  for(let b of Object.keys(matrix)){
    //...
    digits.splice(b-1, 0, "_")
  }
  return digits.join("");
}

const flipABit = function(message,n){
  const binaryMessage = message.split("");
  console.log("Flipping at",n);
  binaryMessage[n] = binaryMessage[n] === "1" ? "0" : "1";
  return binaryMessage.join("")
}

Next up, our parity calculators/correctors. Note that you’ll need to export both of these if you want to plug them into your encoder.

exports.calcParity = (message) => {
  const withPlaceholders = addParityPlaceholder(message);
  const matrix = getParityBitPositions(withPlaceholders);
  const binaryMessage = withPlaceholders.split('');

  for(let bitIndex of Object.keys(matrix)){
    let thisCalc=0;
    for(let idx of matrix[bitIndex]){
      if(binaryMessage[idx-1] === "1") thisCalc+=1;
    }
    // if(thisCalc % 2 > 0) console.log(`Setting B${bitIndex} to 1 because ${thisCalc}`)
    // else console.log(`Leaving B${bitIndex} as 0 because ${thisCalc}`);
    binaryMessage[bitIndex - 1] = thisCalc % 2 > 0 ?  "1" : "0"
  }
  return binaryMessage.join("")
}

exports.correctAnyErrors = (received) => {
  let errorPosition =0, matrix = getParityBitPositions(received), binaryMessage = received.split('');
  for(let idx of Object.keys(matrix)){
    let dataBits = matrix[idx], dataBitSum = 0;
    for(let bit of dataBits){
      const bitIdx = parseInt(bit) - 1; //no off by 1!
      dataBitSum+= parseInt(binaryMessage[bitIdx]);
    }
    if(dataBitSum % 2 !== 0) { //the error check
      errorPosition += parseInt(idx); //it's additive
      console.log("Found error with Parity bit",idx);
    }
  }
  if(errorPosition > 0){
    //flip the error using the array of chars
    console.log("Correcting error at position",errorPosition-1);
    binaryMessage[errorPosition-1] = binaryMessage[errorPosition-1] === "1" ? "0" : "1";
  }
  return binaryMessage.join("");
}

exports.removeParityBits = (message) => {
  const digits= message.split('');
  const matrix = getParityBitPositions(message);
  const bitPositions = Object.keys(matrix);
  //gotta go in reverse here because the index positions will change as we mutate the array
  for(let i = bitPositions.length-1; i >=0; i--){
    const bitPosition = bitPositions[i];
    digits.splice(bitPosition-1, 1);
  }
  return digits.join("");
}
  • The Basics of Logic

    Let’s jump right in at the only place we can: the very begining, diving into the perfectly obvious and terribly argumentative 'rules of logic'.

  • Boolean Algebra

    You're George Boole, a self-taught mathematician and somewhat of a genius. You want to know what God's thinking so you decide to take Aristotle's ideas of logic and go 'above and beyond' to include mathematical proofs.

  • Binary Mathematics

    This is a famous interview question: 'write a routine that adds two positive integers and do it without using mathematic operators'. Turns out you can do this using binary!

  • Bitwise Operators

    This is a famous interview question: 'write a routine that adds two positive integers and do it without using mathematic operators'. Turns out you can do this using binary!

  • Logical Negation

    We've covered how to add binary numbers together, but how do you subtract them? For that, you need a system for recognizing a number as negative and a few extra rules. Those rules are one's and two's complement.

  • Entropy and Quantifying Information

    Now that we know how to use binary to create switches and digitally represent information we need to ask the obvious question: 'is this worthwhile'? Are we improving things and if so, how much?

  • Encoding and Lossless Compression

    Claude Shannon showed us how to change the way we encode things in order to increase efficiency and speed up information trasmission. We see how in this video.

  • Correcting Errors in a Digital Transmission, Part 1

    There are *always* errors during the transmission of information, digital or otherwise. Whether it's written (typos, illegible writing), spoken (mumbling, environment noise) or digital (flipped bits), we have to account for and fix these problems.

  • Correcting Errors in a Digital Transmission, Part 2

    In the previous video we saw how we could correct errors using parity bits. In this video we'll orchestrate those bits using some math along with a divide and conquer algorithm to correct single-bit errors in transmissions of any size.

  • Encryption Basics

    In this video we play around with cryptography and learn how to encrypt things in a very simple, basic way. We then ramp up our efforts quickliy, creating our own one-time pad and Diffie-Hellman secure key transmitter.

  • Functional Programming

    Functional programming builds on the concepts developed by Church when he created Lambda Calculus. We'll be using Elixir for this one, which is a wonderful language to use when discovering functional programming for the first time

  • Lambda Calculus

    Before their were computers or programming languages, Alonzo Church came up with a set of rules for working with functions, what he termed lambdas. These rules allow you to compute anything that can be computed.

  • Database Normalization

    How does a spreadsheet become a highly-tuned set of tables in a relational system? There are rules for this - the rules of normalization - which is an essential skill for any developer working with data

  • Big O Notation

    Understanding Big O has many real world benefits, aside from passing a technical interview. In this post I'll provide a cheat sheet and some real world examples.

  • Arrays and Linked Lists

    The building block data structures from which so many others are built. Arrays are incredibly simple - but how much do you know about them? Can you build a linked list from scratch?

  • Stacks, Queues and Hash Tables

    You can build all kinds of things using the flexibility of a linked list. In this video we'll get to know a few of the more common data structures that you use every day.

  • Trees, Binary Trees and Graphs

    The bread and butter of technical interview questions. If you're going for a job at Google, Microsoft, Amazon or Facebook - you can be almost guaranteed to be asked a question that used a binary tree of some kind.

  • Basic Sorting Algorithms

    You will likely *never* need to implement a sorting algorithm - but understanding how they work could come in handy at some point. Interviews and workarounds for framework problems come to mind.

  • DFS, BFS and Binary Tree Search

    You now know all about trees and graphs - but how do you use them? With search and traversal algorithms of course! This is the next part you'll need to know when you're asked a traversal question in an interview. And you will be.

  • Dynamic Programming and Fibonnaci

    Dynamic programming gives us a way to elegantly create algorithms for various problems and can greatly improve the way you solve problems in your daily work. It can also help you ace an interview.

  • Calculating Prime Numbers

    The use of prime numbers is everywhere in computer science... in fact you're using them right now to connect to this website, read your email and send text messages.

  • Graph Traversal: Bellman Ford

    How can you traverse a graph ensuring you take the route with the lowest cost? The Bellman-Ford algorithm will answer this question.

  • Graph Traversal: Djikstra

    Bellman-Ford works well but it takes too long and your graph can't have cycles. Djikstra solved this problem with an elegant solution.

Watch Again

[[prev.title]]

[[prev.summary]]

Next Up

[[next.title]]

[[next.summary]]