DISK 05 / HAMMING

a program that mends broken data. it packs four bits of a message into seven, with three checking bits laid so that if any one bit is flipped on the way, the three checks point straight at it. it breaks a word on purpose and mends it again. with it run on this computer, a damaged disk can be mended

a floppy disk out of the vending machine, run by pino on the computer at the internet cafe. Richard Hamming, Bell Labs, 1950; written for the cafe.

what it printed:

HAMMING(7,4)  //  four bits of message, three bits of checking

the message: PINO
P high  sent 0100101  arrived 1100101  checks say bit 1  mended 0100101
P low   sent 0000000  arrived 0001000  checks say bit 4  mended 0000000
I high  sent 1001100  arrived 1001110  checks say bit 6  mended 1001100
I low   sent 0011001  arrived 0111001  checks say bit 2  mended 0011001
N high  sent 1001100  arrived 1000100  checks say bit 4  mended 1001100
N low   sent 0010110  arrived 0010111  checks say bit 7  mended 0010110
O high  sent 1001100  arrived 1101100  checks say bit 2  mended 1001100
O low   sent 1111111  arrived 1111011  checks say bit 5  mended 1111111

8 bits flipped on the way, 8 put right
what came out: PINO

// a disk that can mend another disk

what is on the disk:

// four bits in, seven out: p1 p2 d1 p3 d2 d3 d4
function encode(n) {
  var d = [n >> 3 & 1, n >> 2 & 1, n >> 1 & 1, n & 1]
  return [d[0] ^ d[1] ^ d[3], d[0] ^ d[2] ^ d[3], d[0], d[1] ^ d[2] ^ d[3], d[1], d[2], d[3]]
}
// the three checks, read as a number, are where the broken bit is (0: nothing broken)
function mend(w) {
  var s = (w[0] ^ w[2] ^ w[4] ^ w[6]) + 2 * (w[1] ^ w[2] ^ w[5] ^ w[6]) + 4 * (w[3] ^ w[4] ^ w[5] ^ w[6])
  var fixed = w.slice()
  if (s) fixed[s - 1] ^= 1
  return { at: s, bits: fixed, nibble: fixed[2] << 3 | fixed[4] << 2 | fixed[5] << 1 | fixed[6] }
}
var word = 'PINO'
print('HAMMING(7,4)  //  four bits of message, three bits of checking')
print('')
print('the message: ' + word)
var broken = 0, mended = ''
for (var i = 0; i < word.length; i++) {
  var b = word.charCodeAt(i)
  var halves = [b >> 4, b & 15], back = 0
  for (var h = 0; h < 2; h++) {
    var w = encode(halves[h])
    var hurt = w.slice()
    var at = (i * 5 + h * 3) % 7
    hurt[at] ^= 1
    broken++
    var m = mend(hurt)
    print(word[i] + (h ? ' low ' : ' high') + '  sent ' + w.join('') + '  arrived ' + hurt.join('') + '  checks say bit ' + m.at + '  mended ' + m.bits.join(''))
    back = back << 4 | m.nibble
  }
  mended += String.fromCharCode(back)
}
print('')
print(broken + ' bits flipped on the way, ' + broken + ' put right')
print('what came out: ' + mended)
print('')
print('// a disk that can mend another disk')

more of these