Skip to content

The New Turing Omnibus Chapter 12 Error Correcting Codes

Jump to bottom Edit New page
Paul Mucur edited this page May 18, 2016 · 13 revisions

The Chapter

Leo volunteered to shepherd this meeting and we began by discussing the applications of error-correcting codes using the example from the book of communications with spacecraft.

We discussed the constraints of the problem and how that might affect any potential solutions:

  • We only want to send a message once as re-sending can take a huge amount of time;
  • With that in mind, we need to not only be able to detect errors but correct them;
  • We want to tolerate interference anywhere in the message (e.g. cosmic radiation flipping random bits)

Leo then began by explaining the Hadamard matrix and how to build successive matrices from previous ones using the Cartesian product:

Leo then related the Hadamard matrix to our problem as it is particularly well-suited for generating a language of code words for use in error correction.

Intuitively, we want each word in our language to be as distinct as possible so that we can easily identify them even if they are corrupted.

e.g. If our code words were like so:

000001 = 0
000010 = 1

Then if we receive the message 100000 then we can't easily identify the original word.

However, if our code words were like so:

000000 = 0
111111 = 1

Then our message 100000 is much more likely to be 0 than it is 1 due to the number of errors in the message.

Designing such a language is actually quite difficult but the Hadamard matrix is ideal for such a task as each of its rows differ from one another as much as possible.

To better explore how successive Hadamard matrices change (and see the differences between rows), Leo demonstrated his browser-based visualisation:

We then used the H3 Hadamard matrix to pick a message (the number 5) and flip one bit and attempt to recover it.

Using the Hamming distance, we counted the number of errors between our corrupted message and each row to determine the correct code:

We discussed the relationship between the size of the matrix and how many errors various Hadamard matrices can tolerate (as beyond a certain point there will be multiple possible words with the same likelihood):

With this understood, we attempted the first problem given in the chapter which was to generate a matrix for 6-bit words. We couldn't use the Hadamard matrix to do this as they generate words that are powers of 2 so we took to the whiteboard instead:

Joel's proposed a solution and wagered that there were no further words:

In order to test this, we decided to write a program in Ruby to solve the problem for us. James proposed a way for us to do this:

An early version of our Ruby program to generate solutions for the 6-bit problem:

Show & Tell

>> matrix = hadamard_one = [[1, 1], [1, -1]]
=> [
     [1,  1],
     [1, -1]
   ]

>> matrix = matrix.map { |row| row.map { |cell| hadamard_one.map { |one_row| one_row.map { |one_cell| one_cell * cell } } } }.flat_map { |row| row.transpose.map(&:flatten) }
=> [
     [1,  1,  1,  1],
     [1, -1,  1, -1],
     [1,  1, -1, -1],
     [1, -1, -1,  1]
   ]

>> matrix = matrix.map { |row| row.map { |cell| hadamard_one.map { |one_row| one_row.map { |one_cell| one_cell * cell } } } }.flat_map { |row| row.transpose.map(&:flatten) }
=> [
     [1,  1,  1,  1,  1,  1,  1,  1],
     [1, -1,  1, -1,  1, -1,  1, -1],
     [1,  1, -1, -1,  1,  1, -1, -1],
     [1, -1, -1,  1,  1, -1, -1,  1],
     [1,  1,  1,  1, -1, -1, -1, -1],
     [1, -1,  1, -1, -1,  1, -1,  1],
     [1,  1, -1, -1, -1, -1,  1,  1],
     [1, -1, -1,  1, -1,  1,  1, -1]
   ]

>> matrix = matrix.map { |row| row.map { |cell| hadamard_one.map { |one_row| one_row.map { |one_cell| one_cell * cell } } } }.flat_map { |row| row.transpose.map(&:flatten) }
=> [
     [1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1],
     [1, -1,  1, -1,  1, -1,  1, -1,  1, -1,  1, -1,  1, -1,  1, -1],
     [1,  1, -1, -1,  1,  1, -1, -1,  1,  1, -1, -1,  1,  1, -1, -1],
     [1, -1, -1,  1,  1, -1, -1,  1,  1, -1, -1,  1,  1, -1, -1,  1],
     [1,  1,  1,  1, -1, -1, -1, -1,  1,  1,  1,  1, -1, -1, -1, -1],
     [1, -1,  1, -1, -1,  1, -1,  1,  1, -1,  1, -1, -1,  1, -1,  1],
     [1,  1, -1, -1, -1, -1,  1,  1,  1,  1, -1, -1, -1, -1,  1,  1],
     [1, -1, -1,  1, -1,  1,  1, -1,  1, -1, -1,  1, -1,  1,  1, -1],
     [1,  1,  1,  1,  1,  1,  1,  1, -1, -1, -1, -1, -1, -1, -1, -1],
     [1, -1,  1, -1,  1, -1,  1, -1, -1,  1, -1,  1, -1,  1, -1,  1],
     [1,  1, -1, -1,  1,  1, -1, -1, -1, -1,  1,  1, -1, -1,  1,  1],
     [1, -1, -1,  1,  1, -1, -1,  1, -1,  1,  1, -1, -1,  1,  1, -1],
     [1,  1,  1,  1, -1, -1, -1, -1, -1, -1, -1, -1,  1,  1,  1,  1],
     [1, -1,  1, -1, -1,  1, -1,  1, -1,  1, -1,  1,  1, -1,  1, -1],
     [1,  1, -1, -1, -1, -1,  1,  1, -1, -1,  1,  1,  1,  1, -1, -1],
     [1, -1, -1,  1, -1,  1,  1, -1, -1,  1,  1, -1,  1, -1, -1,  1]
   ]

Thanks

Thanks to Leo and Geckoboard for both hosting and shepherding the meeting, to everyone who brought snacks and to James C, Tom and Kevin for the software they wrote before the meeting.

Add a custom footer
Clone this wiki locally