Error Correction, Part 2

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:

<span class="hljs-keyword">const</span> <span class="hljs-title function_">getParityBitPositions</span> = (<span class="hljs-params">message</span>) =&gt; {
  <span class="hljs-keyword">let</span> matrix={};
  <span class="hljs-keyword">for</span>(<span class="hljs-keyword">let</span> i=<span class="hljs-number">1</span>; i &lt;= message.<span class="hljs-property">length</span>; i = i * <span class="hljs-number">2</span>) {
    <span class="hljs-keyword">let</span> taken=<span class="hljs-number">0</span>; skipped=<span class="hljs-number">0</span>;
    matrix[i] = [];
    <span class="hljs-keyword">for</span>(<span class="hljs-keyword">let</span> x = i; x &lt;= message.<span class="hljs-property">length</span>; x++){
      <span class="hljs-keyword">if</span>(taken &lt; i) {
        matrix[i].<span class="hljs-title function_">push</span>(x)
        taken+=<span class="hljs-number">1</span>;
      }<span class="hljs-keyword">else</span>{
        skipped+=<span class="hljs-number">1</span>;
      }
      <span class="hljs-keyword">if</span>(skipped===taken) skipped = taken = <span class="hljs-number">0</span>;
    }
  }
  <span class="hljs-keyword">return</span> matrix;
}

<span class="hljs-keyword">const</span> addParityPlaceholder = <span class="hljs-keyword">function</span>(<span class="hljs-params">message</span>){
  <span class="hljs-keyword">const</span> digits= message.<span class="hljs-title function_">split</span>(<span class="hljs-string">&#x27;&#x27;</span>);
  <span class="hljs-keyword">const</span> matrix = <span class="hljs-title function_">getParityBitPositions</span>(message)
  <span class="hljs-comment">//add parity bits &quot;_&quot; to positions that are powers of two </span>
  <span class="hljs-comment">//as parity bits. (positions 1, 2, 4, 8, 16, 32, 64, etc.)</span>
  <span class="hljs-keyword">for</span>(<span class="hljs-keyword">let</span> b <span class="hljs-keyword">of</span> <span class="hljs-title class_">Object</span>.<span class="hljs-title function_">keys</span>(matrix)){
    <span class="hljs-comment">//...</span>
    digits.<span class="hljs-title function_">splice</span>(b-<span class="hljs-number">1</span>, <span class="hljs-number">0</span>, <span class="hljs-string">&quot;_&quot;</span>)
  }
  <span class="hljs-keyword">return</span> digits.<span class="hljs-title function_">join</span>(<span class="hljs-string">&quot;&quot;</span>);
}

<span class="hljs-keyword">const</span> flipABit = <span class="hljs-keyword">function</span>(<span class="hljs-params">message,n</span>){
  <span class="hljs-keyword">const</span> binaryMessage = message.<span class="hljs-title function_">split</span>(<span class="hljs-string">&quot;&quot;</span>);
  <span class="hljs-variable language_">console</span>.<span class="hljs-title function_">log</span>(<span class="hljs-string">&quot;Flipping at&quot;</span>,n);
  binaryMessage[n] = binaryMessage[n] === <span class="hljs-string">&quot;1&quot;</span> ? <span class="hljs-string">&quot;0&quot;</span> : <span class="hljs-string">&quot;1&quot;</span>;
  <span class="hljs-keyword">return</span> binaryMessage.<span class="hljs-title function_">join</span>(<span class="hljs-string">&quot;&quot;</span>)
}

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.

<span class="hljs-built_in">exports</span>.<span class="hljs-property">calcParity</span> = <span class="hljs-function">(<span class="hljs-params">message</span>) =&gt;</span> {
  <span class="hljs-keyword">const</span> withPlaceholders = <span class="hljs-title function_">addParityPlaceholder</span>(message);
  <span class="hljs-keyword">const</span> matrix = <span class="hljs-title function_">getParityBitPositions</span>(withPlaceholders);
  <span class="hljs-keyword">const</span> binaryMessage = withPlaceholders.<span class="hljs-title function_">split</span>(<span class="hljs-string">&#x27;&#x27;</span>);

  <span class="hljs-keyword">for</span>(<span class="hljs-keyword">let</span> bitIndex <span class="hljs-keyword">of</span> <span class="hljs-title class_">Object</span>.<span class="hljs-title function_">keys</span>(matrix)){
    <span class="hljs-keyword">let</span> thisCalc=<span class="hljs-number">0</span>;
    <span class="hljs-keyword">for</span>(<span class="hljs-keyword">let</span> idx <span class="hljs-keyword">of</span> matrix[bitIndex]){
      <span class="hljs-keyword">if</span>(binaryMessage[idx-<span class="hljs-number">1</span>] === <span class="hljs-string">&quot;1&quot;</span>) thisCalc+=<span class="hljs-number">1</span>;
    }
    <span class="hljs-comment">// if(thisCalc % 2 &gt; 0) console.log(`Setting B${bitIndex} to 1 because ${thisCalc}`)</span>
    <span class="hljs-comment">// else console.log(`Leaving B${bitIndex} as 0 because ${thisCalc}`);</span>
    binaryMessage[bitIndex - <span class="hljs-number">1</span>] = thisCalc % <span class="hljs-number">2</span> &gt; <span class="hljs-number">0</span> ?  <span class="hljs-string">&quot;1&quot;</span> : <span class="hljs-string">&quot;0&quot;</span>
  }
  <span class="hljs-keyword">return</span> binaryMessage.<span class="hljs-title function_">join</span>(<span class="hljs-string">&quot;&quot;</span>)
}

<span class="hljs-built_in">exports</span>.<span class="hljs-property">correctAnyErrors</span> = <span class="hljs-function">(<span class="hljs-params">received</span>) =&gt;</span> {
  <span class="hljs-keyword">let</span> errorPosition =<span class="hljs-number">0</span>, matrix = <span class="hljs-title function_">getParityBitPositions</span>(received), binaryMessage = received.<span class="hljs-title function_">split</span>(<span class="hljs-string">&#x27;&#x27;</span>);
  <span class="hljs-keyword">for</span>(<span class="hljs-keyword">let</span> idx <span class="hljs-keyword">of</span> <span class="hljs-title class_">Object</span>.<span class="hljs-title function_">keys</span>(matrix)){
    <span class="hljs-keyword">let</span> dataBits = matrix[idx], dataBitSum = <span class="hljs-number">0</span>;
    <span class="hljs-keyword">for</span>(<span class="hljs-keyword">let</span> bit <span class="hljs-keyword">of</span> dataBits){
      <span class="hljs-keyword">const</span> bitIdx = <span class="hljs-built_in">parseInt</span>(bit) - <span class="hljs-number">1</span>; <span class="hljs-comment">//no off by 1!</span>
      dataBitSum+= <span class="hljs-built_in">parseInt</span>(binaryMessage[bitIdx]);
    }
    <span class="hljs-keyword">if</span>(dataBitSum % <span class="hljs-number">2</span> !== <span class="hljs-number">0</span>) { <span class="hljs-comment">//the error check</span>
      errorPosition += <span class="hljs-built_in">parseInt</span>(idx); <span class="hljs-comment">//it&#x27;s additive</span>
      <span class="hljs-variable language_">console</span>.<span class="hljs-title function_">log</span>(<span class="hljs-string">&quot;Found error with Parity bit&quot;</span>,idx);
    }
  }
  <span class="hljs-keyword">if</span>(errorPosition &gt; <span class="hljs-number">0</span>){
    <span class="hljs-comment">//flip the error using the array of chars</span>
    <span class="hljs-variable language_">console</span>.<span class="hljs-title function_">log</span>(<span class="hljs-string">&quot;Correcting error at position&quot;</span>,errorPosition-<span class="hljs-number">1</span>);
    binaryMessage[errorPosition-<span class="hljs-number">1</span>] = binaryMessage[errorPosition-<span class="hljs-number">1</span>] === <span class="hljs-string">&quot;1&quot;</span> ? <span class="hljs-string">&quot;0&quot;</span> : <span class="hljs-string">&quot;1&quot;</span>;
  }
  <span class="hljs-keyword">return</span> binaryMessage.<span class="hljs-title function_">join</span>(<span class="hljs-string">&quot;&quot;</span>);
}

<span class="hljs-built_in">exports</span>.<span class="hljs-property">removeParityBits</span> = <span class="hljs-function">(<span class="hljs-params">message</span>) =&gt;</span> {
  <span class="hljs-keyword">const</span> digits= message.<span class="hljs-title function_">split</span>(<span class="hljs-string">&#x27;&#x27;</span>);
  <span class="hljs-keyword">const</span> matrix = <span class="hljs-title function_">getParityBitPositions</span>(message);
  <span class="hljs-keyword">const</span> bitPositions = <span class="hljs-title class_">Object</span>.<span class="hljs-title function_">keys</span>(matrix);
  <span class="hljs-comment">//gotta go in reverse here because the index positions will change as we mutate the array</span>
  <span class="hljs-keyword">for</span>(<span class="hljs-keyword">let</span> i = bitPositions.<span class="hljs-property">length</span>-<span class="hljs-number">1</span>; i &gt;=<span class="hljs-number">0</span>; i--){
    <span class="hljs-keyword">const</span> bitPosition = bitPositions[i];
    digits.<span class="hljs-title function_">splice</span>(bitPosition-<span class="hljs-number">1</span>, <span class="hljs-number">1</span>);
  }
  <span class="hljs-keyword">return</span> digits.<span class="hljs-title function_">join</span>(<span class="hljs-string">&quot;&quot;</span>);
}