Error Correction, Part 1

As you watch this video, note that it's not always smooth and seamless. Behind the scenes, Vimeo (my video provider) is adjusting for bandwith changes, alternating the sources based on throughput. The player is compensating for packet loss as well, correcting for errors in audio and video.

This stuff is complicated and you're about to see why.

This is part 1 of a 2-part series where we try to answer two simple questions:

• Was there an error in the transmission?
• Where is it?

This is tricky stuff! We'll tackle the theory in this video and in the next one, part 2, we'll spend the entire time writing the code necessary to fix my favorite Big Lebowski quote.

The Code

Here's the code used in the video. Note that the blurbs below are mostly for example. In the next video we'll write more useful stuff.

<span class="hljs-keyword">class</span> <span class="hljs-title class_">Encoder</span>{

  <span class="hljs-title function_">constructor</span>(<span class="hljs-params"></span>){

    <span class="hljs-variable language_">this</span>.<span class="hljs-property">encoding</span> = {
      <span class="hljs-string">&quot;A&quot;</span> : <span class="hljs-string">&quot;01000000000&quot;</span>,
      <span class="hljs-string">&quot;B&quot;</span> : <span class="hljs-string">&quot;10000000000&quot;</span>,
      <span class="hljs-string">&quot;C&quot;</span> : <span class="hljs-string">&quot;00100000000&quot;</span>,
      <span class="hljs-string">&quot;D&quot;</span> : <span class="hljs-string">&quot;00101000000&quot;</span>,
      <span class="hljs-string">&quot;E&quot;</span> : <span class="hljs-string">&quot;10100000000&quot;</span>,
      <span class="hljs-string">&quot;F&quot;</span> : <span class="hljs-string">&quot;10010000000&quot;</span>,
      <span class="hljs-string">&quot;G&quot;</span> : <span class="hljs-string">&quot;01010000000&quot;</span>,
      <span class="hljs-string">&quot;H&quot;</span> : <span class="hljs-string">&quot;11000000000&quot;</span>,
      <span class="hljs-string">&quot;I&quot;</span> : <span class="hljs-string">&quot;11010000000&quot;</span>,
      <span class="hljs-string">&quot;J&quot;</span> : <span class="hljs-string">&quot;01011000000&quot;</span>,
      <span class="hljs-string">&quot;K&quot;</span> : <span class="hljs-string">&quot;01011001000&quot;</span>,
      <span class="hljs-string">&quot;L&quot;</span> : <span class="hljs-string">&quot;10001000000&quot;</span>,
      <span class="hljs-string">&quot;M&quot;</span> : <span class="hljs-string">&quot;01010100000&quot;</span>,
      <span class="hljs-string">&quot;N&quot;</span> : <span class="hljs-string">&quot;01100000000&quot;</span>,
      <span class="hljs-string">&quot;O&quot;</span> : <span class="hljs-string">&quot;01110000000&quot;</span>,
      <span class="hljs-string">&quot;P&quot;</span> : <span class="hljs-string">&quot;10000100000&quot;</span>,
      <span class="hljs-string">&quot;Q&quot;</span> : <span class="hljs-string">&quot;01011000100&quot;</span>,
      <span class="hljs-string">&quot;R&quot;</span> : <span class="hljs-string">&quot;11100000000&quot;</span>,
      <span class="hljs-string">&quot;S&quot;</span> : <span class="hljs-string">&quot;11110000000&quot;</span>,
      <span class="hljs-string">&quot;T&quot;</span> : <span class="hljs-string">&quot;00110000000&quot;</span>,
      <span class="hljs-string">&quot;U&quot;</span> : <span class="hljs-string">&quot;10011000000&quot;</span>,
      <span class="hljs-string">&quot;V&quot;</span> : <span class="hljs-string">&quot;01011010000&quot;</span>,
      <span class="hljs-string">&quot;W&quot;</span> : <span class="hljs-string">&quot;00100100000&quot;</span>,
      <span class="hljs-string">&quot;X&quot;</span> : <span class="hljs-string">&quot;01011000110&quot;</span>,
      <span class="hljs-string">&quot;Y&quot;</span> : <span class="hljs-string">&quot;01011100000&quot;</span>,
      <span class="hljs-string">&quot;Z&quot;</span> : <span class="hljs-string">&quot;01011000111&quot;</span>,
      <span class="hljs-string">&quot; &quot;</span> : <span class="hljs-string">&quot;00000000000&quot;</span>
    }
  }
  <span class="hljs-title function_">encode</span>(<span class="hljs-params">message</span>){
    <span class="hljs-comment">//loop the characters in the message</span>
    <span class="hljs-comment">//we&#x27;ll assume for now that they won&#x27;t enter anything but alpha numeric with a space for separation</span>
    <span class="hljs-comment">//also ... uppercase to reduce pain</span>
    <span class="hljs-keyword">const</span> words = message.<span class="hljs-title function_">toUpperCase</span>(), out = [];

    <span class="hljs-keyword">for</span>(<span class="hljs-keyword">let</span> word <span class="hljs-keyword">of</span> words){
      <span class="hljs-keyword">for</span>(<span class="hljs-keyword">let</span> char <span class="hljs-keyword">of</span> word){
        <span class="hljs-keyword">const</span> encoding = <span class="hljs-variable language_">this</span>.<span class="hljs-property">encoding</span>[char];
        <span class="hljs-comment">//if the character can be encoded great. If not, ignore</span>
        <span class="hljs-keyword">if</span>(encoding) out.<span class="hljs-title function_">push</span>(encoding);
      }
    }
    <span class="hljs-keyword">return</span> out.<span class="hljs-title function_">join</span>(<span class="hljs-string">&quot;&quot;</span>);
  }   
  <span class="hljs-comment">//add the methods below</span>
}

  <span class="hljs-title function_">evenParity</span>(<span class="hljs-params"></span>){
    <span class="hljs-keyword">const</span> keys = <span class="hljs-title class_">Object</span>.<span class="hljs-title function_">keys</span>(<span class="hljs-variable language_">this</span>.<span class="hljs-property">encoding</span>);
    <span class="hljs-keyword">for</span>(<span class="hljs-keyword">let</span> key <span class="hljs-keyword">of</span> keys){
      <span class="hljs-comment">//default to even</span>
      <span class="hljs-keyword">let</span> pad = <span class="hljs-string">&quot;0&quot;</span>;
      <span class="hljs-comment">//split into a character array so we can filter</span>
      <span class="hljs-keyword">const</span> chars = <span class="hljs-variable language_">this</span>.<span class="hljs-property">encoding</span>[key].<span class="hljs-title function_">split</span>(<span class="hljs-string">&#x27;&#x27;</span>);
      <span class="hljs-keyword">const</span> ones = chars.<span class="hljs-title function_">filter</span>(<span class="hljs-function"><span class="hljs-params">v</span> =&gt;</span> v === <span class="hljs-string">&quot;1&quot;</span>);
      <span class="hljs-comment">//check mod 2 to see if we&#x27;re odd, if so, set the pad to 1</span>
      <span class="hljs-keyword">if</span>(ones.<span class="hljs-property">length</span> % <span class="hljs-number">2</span> !==<span class="hljs-number">0</span>) pad = <span class="hljs-string">&quot;1&quot;</span>
      <span class="hljs-comment">//update the encoding with a pad at the end</span>
      <span class="hljs-variable language_">this</span>.<span class="hljs-property">encoding</span>[key]+= pad;
    }
    <span class="hljs-variable language_">console</span>.<span class="hljs-title function_">log</span>(<span class="hljs-variable language_">this</span>.<span class="hljs-property">encoding</span>);
  }

  <span class="hljs-title function_">checkParity</span>(<span class="hljs-params">word</span>){
    <span class="hljs-comment">//make sure we have the right length</span>
    <span class="hljs-keyword">if</span>(word.<span class="hljs-property">length</span> !== <span class="hljs-number">12</span>) <span class="hljs-keyword">return</span> <span class="hljs-literal">false</span>;
    <span class="hljs-comment">//now make sure it&#x27;s even</span>
    <span class="hljs-keyword">return</span> word.<span class="hljs-title function_">split</span>(<span class="hljs-string">&quot;&quot;</span>).<span class="hljs-title function_">filter</span>(<span class="hljs-function"><span class="hljs-params">char</span> =&gt;</span> char === <span class="hljs-string">&quot;1&quot;</span>).<span class="hljs-property">length</span> %<span class="hljs-number">2</span> === <span class="hljs-number">0</span>;
  }

  <span class="hljs-title function_">decode</span>(<span class="hljs-params">binaryMessage</span>){
    <span class="hljs-keyword">let</span> out = [], codeWord = <span class="hljs-string">&quot;&quot;</span>;
    <span class="hljs-keyword">const</span> pad = <span class="hljs-variable language_">this</span>.<span class="hljs-property">encoding</span>.<span class="hljs-property">A</span>.<span class="hljs-property">length</span>;
    <span class="hljs-keyword">for</span>(<span class="hljs-keyword">let</span> i = <span class="hljs-number">0</span>; i &lt; binaryMessage.<span class="hljs-property">length</span>; i+=pad){
      codeWord = binaryMessage.<span class="hljs-title function_">substring</span>(i, i + pad);
      <span class="hljs-keyword">const</span> noError = <span class="hljs-variable language_">this</span>.<span class="hljs-title function_">checkParity</span>(codeWord);
    
      <span class="hljs-keyword">if</span>(noError){
        <span class="hljs-keyword">const</span> key = <span class="hljs-variable language_">this</span>.<span class="hljs-title function_">getAlpha</span>(codeWord);
        out.<span class="hljs-title function_">push</span>(key);
        codeWord = <span class="hljs-string">&quot;&quot;</span>;
      }<span class="hljs-keyword">else</span>{
        <span class="hljs-comment">//this is an error!</span>
        <span class="hljs-variable language_">console</span>.<span class="hljs-title function_">log</span>(<span class="hljs-string">&quot;Got an error with &quot;</span>, codeWord);
        <span class="hljs-keyword">const</span> fix = <span class="hljs-variable language_">this</span>.<span class="hljs-title function_">simpleHammingErrorCorrector</span>(codeWord);
        <span class="hljs-variable language_">console</span>.<span class="hljs-title function_">log</span>(<span class="hljs-string">&quot;Fixing with best guess:&quot;</span>, fix);
        out.<span class="hljs-title function_">push</span>(fix.<span class="hljs-property">word</span>);
      }
    }
    <span class="hljs-keyword">return</span> out.<span class="hljs-title function_">join</span>(<span class="hljs-string">&quot;&quot;</span>);
  }

<span class="hljs-title function_">simpleHammingErrorCorrector</span>(<span class="hljs-params">binaryMessage</span>){
  
  <span class="hljs-keyword">const</span> codeWords = <span class="hljs-title class_">Object</span>.<span class="hljs-title function_">values</span>(<span class="hljs-variable language_">this</span>.<span class="hljs-property">encoding</span>);
  <span class="hljs-keyword">let</span> bestCandidate = {}, bestDistance = <span class="hljs-title class_">Number</span>.<span class="hljs-property">POSITIVE_INFINITY</span>;

  <span class="hljs-keyword">for</span>(<span class="hljs-keyword">let</span> codeWord <span class="hljs-keyword">of</span> codeWords){
    <span class="hljs-keyword">let</span> thisDistance = <span class="hljs-number">0</span>;;
    
    <span class="hljs-comment">//we&#x27;re scanning each word for a match</span>
    <span class="hljs-keyword">for</span>(<span class="hljs-keyword">let</span> i = <span class="hljs-number">0</span>; i &lt; codeWord.<span class="hljs-property">length</span>; i++){
      <span class="hljs-keyword">if</span>(codeWord[i] !== binaryMessage[i]) {
        thisDistance+=<span class="hljs-number">1</span>;
      }
    }
    <span class="hljs-keyword">if</span>(thisDistance &lt; bestDistance){
      bestDistance = thisDistance;
      bestCandidate = {<span class="hljs-attr">word</span>: <span class="hljs-variable language_">this</span>.<span class="hljs-title function_">getAlpha</span>(codeWord), <span class="hljs-attr">binary</span>: codeWord, <span class="hljs-attr">distance</span>: bestDistance}
    }
  }
  <span class="hljs-keyword">return</span> bestCandidate;
}