parity符号とhumming符号をemulationした

Rubyで。当然手元にvim-quickrun。
[情報理論やりなおし勉強会（４）]( http://atnd.org/events/40292 )の復習。にはならない。情報理論の基礎―情報と学習の直観的理解のために (SGC Books)の第四章第二部を倒した積りに成ってゐる。
parity検査符号とhumming検査・訂正符号をemulationした。時々妙なerrorが出るので、確実に間違いが有る。洞所だ。

# encoding=utf-8
require 'matrix'

class Binary
  include Enumerable
  attr_accessor :binary, :chunk_size
  @@default_chunk_size = 4;

  # return [number]
  def self.default_chunk_size; @@default_chunk_size; end

  # param [Array] binary
  def self.parity binary
    binary.reduce(0){|sum, bit| sum + bit } % 2
  end

  # param [number] n
  # param [number] size
  # return [Array]
  def self.chunk_from_int n, size=@@default_chunk_size
    ("%0.#{size}b" % n.abs.floor).split('').map &:to_i
  end

  # param [Array] binary
  # param [number] chunk_size
  def initialize binary, chunk_size=@@default_chunk_size
    @binary = binary
    @chunk_size = chunk_size
  end

  # param [number] frequency
  # return [Binary]
  def crush frequency=8
    @binary = @binary.map{|bit| rand(frequency) == 0 ? (bit + 1) % 2 : bit }
    self
  end

  # return [Enumerator]
  def each &proc
    @binary.each_slice @chunk_size, &proc
  end

  # return [string]
  def to_s
    @binary.each_slice(@chunk_size).map{|chunk| "[#{chunk.join ', '}]" }.join "\n"
  end
end

class Coder
  # param [Binary] binary
  # return [Binary]
  def encode binary
    binary.binary = binary.map{|chunk| encode_chunk chunk }.flatten
    binary.chunk_size = @chunk_size
    binary
  end

  # param [Binary] binary
  # return [Binary]
  def decode binary
    binary.binary = binary.map{|chunk| repaire chunk }.flatten
    binary.chunk_size = Binary.default_chunk_size
    binary
  end
end

class Parity < Coder
  def initialize
    @chunk_size = 5
  end

private
  def encode_chunk chunk
    chunk << Binary.parity(chunk)
  end

  def repaire chunk
    if Binary.parity(chunk[0..3]) == chunk[4]
      chunk[0..3]
    else
      [nil] * 4
    end
  end
end

class Humming < Coder
  @@matrix = Matrix[* (1..7).map{|n| Binary.chunk_from_int n, 3 }].transpose

  def initialize
    @chunk_size = 7
  end

private
  def encode_chunk chunk
    [
      chunk[0],
      chunk[1],
      chunk[2],
      chunk[3],
      Binary.parity([chunk[1], chunk[2], chunk[3]]),
      Binary.parity([chunk[0], chunk[2], chunk[3]]),
      Binary.parity([chunk[0], chunk[1], chunk[3]])
    ]
  end

  def repaire chunk
    sum = calc_sum(chunk)
    return chunk[0..3] if sum == 0
    chunk[sum - 1] = (chunk[sum - 1] + 1) % 2
    if calc_sum(chunk) == 0
      chunk[0..3]
    else
      [nil] * 4
    end
  end

  def calc_sum chunk
    (@@matrix * Matrix.column_vector(chunk)).column(0).to_a.
      reverse.
      each_with_index.
      reduce(0){|sum, elm| sum + (elm[0] % 2) * 2 ** elm[1] }
  end
end

def print_result encoder
  binary = Binary.new (1..15).map{|n| Binary.chunk_from_int n }.flatten
  # binary = Binary.new [
  #   0, 0, 0, 1,
  #   0, 0, 1, 0,
  #   0, 0, 1, 1,
  #   0, 1, 0, 0,
  #   0, 1, 0, 1,
  #   0, 1, 1, 0,
  #   0, 1, 1, 1,
  #   1, 0, 0, 0,
  #   1, 0, 0, 1,
  #   1, 0, 1, 0,
  #   1, 0, 1, 1,
  #   1, 1, 0, 0,
  #   1, 1, 0, 1,
  #   1, 1, 1, 0,
  #   1, 1, 1, 1
  # ]
  binary = encoder.encode(binary).crush 32
  puts encoder.decode binary
  puts
end

print_result Parity.new
print_result Humming.new

# vim:set ft=ruby et sw=2 sts=2 ff=unix:

出力例

[0, 0, 0, 1]
[0, 0, 1, 0]
[0, 0, 1, 1]
[0, 1, 0, 0]
[0, 1, 0, 1]
[0, 1, 1, 0]
[0, 1, 1, 1]
[1, 0, 0, 0]
[, , , ]
[1, 0, 1, 0]
[0, 0, 1, 0]
[1, 1, 0, 0]
[1, 1, 0, 1]
[1, 1, 1, 0]
[1, 1, 1, 1]

[0, 0, 0, 1]
[0, 0, 1, 0]
[0, 0, 1, 1]
[0, 1, 0, 0]
[0, 1, 0, 1]
[0, 1, 1, 0]
[0, 1, 1, 1]
[1, 0, 0, 0]
[1, 0, 0, 1]
[0, 0, 1, 0]
[1, 0, 1, 1]
[1, 1, 0, 0]
[1, 1, 0, 1]
[1, 1, 1, 0]
[1, 1, 1, 1]

cf. 前回 → 符号化algorithmを実験してみた (fano符号、shannon符号、huffman符号)