zfecライブラリでデータ破損を復元する誤り訂正符号を生成

  • 3
    Like
  • 0
    Comment
More than 1 year has passed since last update.

zfecライブラリを利用して、データが一部破損していもて復元できる誤り訂正符号を生成してみました。

データ破損を復元するイメージ図

zfecライブラリはRAID-5アルゴリズムでデータ破損を復元します。Raid-5アルゴリズムに関してはこちらを読むと判りやすいです。XORを利用した単純な仕組みなのですぐ理解できると思います。

スクリーンショット 2016-02-25 16.33.13.png

スクリーンショット 2016-02-25 16.33.19.png

スクリーンショット 2016-02-25 16.33.36.png

zfecライブラリの特徴

・早い
・python, c, HaskelのAPIがある
・char配列を扱える

https://pypi.python.org/pypi/zfec

インストール

pip install zfec

2ブロックから誤り訂正符号を生成して検証

スクリーンショット 2016-02-25 16.33.13.png

2DataBlock
# -*- coding: utf-8 -*-
from __future__ import absolute_import, unicode_literals
import zfec

# エラー検出訂正
data_block1 = str('aiueo')
data_block2 = str('kakik')

# データブロック1と2からエラー検出符号:3を生成
_, _, data_block3 = zfec.Encoder(2, 3).encode([data_block1, data_block2])
print 'data block 3 is... {}'.format(data_block3)
# >>> data block 3 is... uyI}g

# データブロック1とエラー検出符号:3から2を復元
_, repaired_data_block2 = zfec.Decoder(2, 3).decode([data_block1, data_block3, ], [0, 2])
assert data_block2 == repaired_data_block2

# データブロック2とエラー検出符号:3から1を復元
repaired_data_block1, _ = zfec.Decoder(2, 3).decode([data_block2, data_block3, ], [1, 2])
assert data_block1 == repaired_data_block1


5ブロックから誤り訂正符号を生成して検証

5DataBlock
# -*- coding: utf-8 -*-
from __future__ import absolute_import, unicode_literals
import zfec

# エラー検出訂正
data_block1 = str('aiueo')
data_block2 = str('kakik')
data_block3 = str('ukeko')
data_block4 = str('sasis')
data_block5 = str('useso')

# データブロック1と2からエラー検出符号:3を生成
blocks = zfec.Encoder(5, 6).encode([data_block1,
                                    data_block2,
                                    data_block3,
                                    data_block4,
                                    data_block5])

ecc_block = blocks[-1]
print str('ecc block is... {}').format(ecc_block)
# >>> ecc block is... J?\j

# データブロック1-4とECCブロックから5を復元
repaired_blocks = zfec.Decoder(5, 6).decode([data_block1,
                                             data_block2,
                                             data_block3,
                                             data_block4,
                                             ecc_block], [0, 1, 2, 3, 5])
assert data_block5 == repaired_blocks[4]

# データブロック1,2,4,5とECCブロックから3を復元
repaired_blocks = zfec.Decoder(5, 6).decode([data_block1,
                                             data_block2,
                                             data_block4,
                                             data_block5,
                                             ecc_block], [0, 1, 3, 4, 5])
assert data_block3 == repaired_blocks[2]