Location : Home > Languages > Perl > Package
Title : Algorithm::FEC
 		Toolbox Logo

名称

　Algorithm::FEC - ヴァンデルモンド行列を用いた前方誤り訂正

概要

use Algorithm::FEC;

説明

　本モジュールは Luigi Rizzo らによる FEC ライブラリへのインタフェースである。詳しくは本ディストリビューションに含まれているファイル README.fec を見よ。
　このライブラリはヴァンデルモンド行列に基づく簡単な（encoded_blocks, data_blocks）抹消符号を実装している。エンコーダは data_blocks と block_size を引数にとり、元データを再構成することで data_blocks の要素の部分集合として 0 から encoded_blocks - 1 の間の数の異なる符号化されたブロックを生成することができる。
　data_blocks 及び encoded_blocks として許される値が以下の式に従う。

data_blocks <= encoded_blocks <= MAXBLOCKS

ただし最速の実装に対しては MAXBLOCKS = 256 であり、最遅に対しては MAXBLOCKS = 65536 である。（実装は自動的に選択される）

　もしデータが要求されているサイズでなければ（つまり blocksize の倍数でなければ）符号化の際にパッドし（０で埋めるなど）、復号化の後に元に戻さなければならない。さもなければ本ライブラリは文句を言う。
　将来のバージョンではメモリに短い切片をロードする代わりにスカラを拡張するかも知れない（$fec->copy (..., my $x) などをトリッキーなことで可能かも）。要望があればメールを。
　引数なしで呼び出されればブロックと関連付けられた内部記憶を解放する。

$block = $fec->encode (block_index)

　0 から encoded_blocks - 1（この値を含む）までの値のインデクス block_index の単一の符号化されたブロックを生成する。0 から data_blocks - 1 までのブロクは元データブロックのコピーである。
　符号化されたブロックは Perl のスカラとして返される。そのためブロックはメモリに適合されるべきだ。これが問題であればメールを欲しい。それをファイルしよう。

$fec->set_decode_blocks ([array_of_blocks], [array_of_indices])

　ブロックの data_blocks を復号化する準備を行う（array_of_blocks パラメータ用の set_encode_blocks を見よ。）。
　データブロック本体を必要としないのでインデクスの配列（0 から encoded_blocks - 1 まで）が２つめの参照配列として必要である。
　双方の配列は正確に data_blocks エントリを持つ必要がある。
　本メソッドはブロックとインデクス配列を再並び替えするので、（必要であれば）復号化された結果をブロックの反映することができる。
　双方の配列は正確に data_blocks エントリを持つ必要がある。
　インデクス配列は復号化の順を示しており、インデクス配列の n-番目のエントリは復号化結果の n-番目のデータの対応している。配列の n-番目に格納されている値は符号化されたデータブロックのインデクスを含んでいる。
　data_blocks より小さいインデクスの入力ブロックは最後の位置に移動させられ（ブロック k を位置 k に）、その間はチェックブロックで埋められる。復号化プロセスは既に復号化されたデータブロックを変更しないが、チェックブロックは変更する。
　すなわち、この関数を indices = [4,3,1], data_blocks = 3 とともに呼び出した場合、配列 [0,2,1] を返す。これは入力ブロック 0 がファイルブロック 0 に、入力ブロック 1 はファイルブロック 2 に、入六ブロック 2 はデータブロック 1 に対応していることを意味する。
　この配列全体に対して繰り返し処理し、対応するデータブロックを全て書き出すこともできる。（これでは不十分だけれども）

for my $i (0 .. $#idx)
   if ($idx[$i] != $i) # need we move this block?
      copy encoded block $idx[$i] to position $i
   }
}

　copy メソッドはここでは有用である。
　本メソッドは set_encode_blocks により設定されたブロック配列を破壊する。

$fec->shuffle ([array_of_blocks], [array_of_indices])

　set_decode_blocks と同じであるが、ブロックは復号化のためには設定されない点が異なる。
　本メソッドは通常は用いられないが、復号化の前、再順序化のあとにブロックを移動したい場合には set_decode_blocks の前に shuffle を呼び出せばよい。ファイルはマッピングされないので、set_decode_blocks を２度呼び出すよりは時間がかかる。

$fec->decode

　set_decode_blocks に先立ち呼び出されることでブロックを復号化する。
　本メソッドは set_decode_blocks により設定されるブロック配列を上書きする。

$fec->copy ($srcblock, $dstblock)

　（set_encode_blocks などで特定された）１つのブロックを他のブロックにコピーするユーティリティ関数。これは set_*_blocks によって設定されたブロックを破壊する。

互換性

　freenet（http://freenet.sf.net）でファイルをコード化する方法とは互換性がある。他のファイルフォーマットとの互換性については分からない。他に例があれば教えて欲しい。

参考資料

　Net::FCP. こんなにめったに使われないモジュールを実際に使ってくれたユーザから受け取った著者。

バグ

著者

　Marc Lehmann <pcg@goof.com>
　http://home.schmorp.de

Toolbox Logo
 Updated : 2008/08/11