読者です 読者をやめる 読者になる 読者になる

へっぽこびんぼう野郎のnewbie日記

けろけーろ(´・ω・`)!

ハミングコードについて。応用情報過去問のやつ。

数学 コンピュータサイエンス

はじめに

応用情報の過去問問いてたら、ハミングコードなるものが出てきた。
問題は解けたけど、パリティチェックと何が違うんと思って調べた。

ハミングコードの簡単な歴史

ハミングさんという偉い人が発見した。
【その経緯】
→普通のパリティチェックだと、エラーは発見できるけど、勝手に直してはくれないしめんどくさくね?
→勝手に直せるのつくろう
→シングルエラーなら勝手に直してくれて、ダブルエラーは検出できるようになった
→現在では主にエラーが出にくいPCのメモリ内で使われるらしい(これはwikipediaソース)
ソース(PDF注意):http://www.mth.msu.edu/~jhall/classes/codenotes/Hamming.pdf


言い換えると、シングルエラーじゃないと勝手に直してくれない。

ハミングコード

応用情報の過去問に出てくるやつは、ハミングコードの亜種である。よってひとまずおいておく。

通常ハミングコードは次のようにする。
出典:Hamming code - Wikipedia, the free encyclopedia
f:id:haruharu1:20150325013806p:plain
1 2 4 8と、dataに対して2の乗数のとこに挟んでいく。

これは何をしているかというと、この「pほげ」というのがパリティチェック部で、
DataをそれぞれXOR演算でチェックしているのだ。

(ORとかANDじゃないのは、ORだとひとつでも1があれば1になるし、ANDはひとつでも0があれば0になっちゃうからだと思う。)

チェックの仕方に特徴があって、
p1は1個おき、p2は2個おき、p4は4個おきとチェックしている。

なんでこんなやり方すんのというのは、d1(Data1)は3番目、d2は5番目にあるというのを見るとわかる。
たとえばd1の位置はp1とp2の位置で表現できる。
そして、p1とp2の位置だけで表現できるのはd1の位置のみである。
2進数表現ばんじゃーいヽ(´ー`)ノ

ゆえに、p1とp2がおかしくて(XOR演算結果=1)、他のp4等が正しければ(XOR演算結果=0)
あ、じゃあp1とp2がおかしいっていうことは、d1がおかしいからおかしくなったんだなと決まる。
d2のときはp1とp4で決まる。


そんなノリでした。

応用情報の問題、ハミングコード亜種

問4 ハミング符号 平成25年春期|応用情報技術者試験.com
これは、ハミングコードを後ろから挿入しているだけ。

「別に前からしかやっちゃダメとかは言われてねぇ!!」

で、パリティチェックを含めた場所を特定する。
p1チェック→XOR演算→1→おかしい
p2チェック→XOR演算→1→おかしい
p3(p4だけど名前変えてみたかったんだろう)チェック→XOR演算→1→おかしい
よって、1 + 2 + 4で右から7番目がおかしいので1から0にするよ
みたいな

ハミングコードはすごいということがわかった

でもまだよくわかってないのでふ〜ん程度に流しておいて、あんまり信用しないでください

  • Generator matrix(いみふ)
  • Parity-check matrix(やはりいみふ)
  • Block Code
  • Linear Codes
  • Hamming distanceの最小値がなんで3になるのか

しらん。