Algorithm::Hamming::Perl - Perl implementation of ECC Hamming encoding, for single bit auto error correction.

Location : Home > Languages > Perl > Package
Title : Algorithm::Hamming::Perl

　Algorithm::Hamming::Perl - ハミング符号の処理

use Algorithm::Hamming::Perl  qw(hamming unhamming);

$code = hamming($data);              # $data をエンコード

$data = unhamming($code);            # デコードしてエラーを除去
($data,$errors) = unhamming($code);  # エラーをカウントして返す。

説明

　これは誤り訂正符号（Error Correction Code）モジュールであり、ハミングエンコード（8 ビット・4 ビットのハミング符号 - つまりデータサイズが50％増加する）の実装である。１バイトに１ビットのエラーを訂正できる符号が付加されており、自動訂正が可能である。
　１ビット程度の誤りが含まれていると思われるデータの格納及び送信の前に利用すると有用である。
　ハミング符号化は1948年にベル研究所にいた Richard Hamming により提唱された。

エクスポートされるサブルーチン

hamming (SCALAR): 　提供された入力データからハミング符号を返す。
unhamming (SCALAR): 　提供されたハミング符号から元データを返す。シングルビット誤りを自動訂正する。
unhamming_err (SCALAR): 　提供されたハミング符号から元データを返し、修正した箇所をバイトで返す。シングルビット誤りを自動訂正する。

その他のサブルーチン

Algorithm::Hamming::Perl::hamming_faster (): 　プログラム開始時に１度実行されると、ハミング符号化を高速化するオプションのサブルーチンである。予備処理の結果の格納により大きな（ハッシュ）キャッシュを用いることで行う。欠点はメモリをたくさん使用することと初期化時に少々時間がかかることである。使うのであれば 1MB 以上のデータを処理しなければならないときである。

インストール

perl Makefile.PL
make
make test
make install

依存関係

　ExtUtils::MakeMaker

使用例

　本モジュールとともに提供されたプログラム例 "example*" を参照のこと。
　エンコードとデコードの例は以下の通り。

use Algorithm::Hamming::Perl  qw(hamming unhamming);

$data = "Hello";
$hamcode = hamming($data);

$original = unhamming($hamcode);

限界

　Perl だけでは遅いかも知れない。ハミング符号化は１バイト内に１ビットの誤りがあるときにのみ修復可能で、複数の誤りがある場合には自動訂正はうまく機能しない。

バグ

　ハミング符号化した文字列と一緒に使用してはいけない。これはバグに見える結果を返すであろう。もし奇数バイトの入力であれば、出力符号は半バイトとなる。残りは 0 で埋められる。これらと埋めたビット文字列の連結はデコード時の混乱の元である。
　上記の問題はある長さの入力及び出力をファイルハンドルに渡す際に発生する。安全のためにコードの例では 3072 バイトのバッファ－ファイルハンドルと一緒に使うには十分安全なサイズである－を用いている。

著作権

　本ライブラリはフリーソフトウェアであり、Perl 本体と同等の条件で修正／再配布してもよい。

著者

　Brendan Gregg, <brendan.gregg@tpg.com.au>
　[Sydney, Australia]

Updated : 2007/05/02