概要
- 学習中のコンピュータの構成と設計 MIPS Edition 第6版(下)(以降パタへネ本)の5.5章に、誤り検出・訂正の例題があります。手を動かして理解しようと思い、1bit ECCの機能をpythonで実装してみました。
- ちなみに、誤り検出・訂正の機能自体はbchlibというモジュールを使うことで、pythonでも実現できるようです。
- 誤り検出・訂正の仕組みについては、ここでは割愛します。
実装
1bit_ecc.py
# 引数のビットパターンにパリティビットを挿入し、挿入後のビットパターンとパリティビット数を返す
def insert_parity_bit(input):
num = input.replace('_', '')
cnt = 1
ref = 0
bit_pattern = list(num)
is_complete = False
while True:
# パリティビットの挿入
position = 2**(cnt - 1) - 1
bit_pattern.insert(position, '0')
# パリティビット数確認
ref += 2**cnt - 1
if (len(num) <= ref):
if is_complete: break
else: is_complete = True
cnt += 1
# bit_pattern をlistで扱う
bit_pattern = [int(i) for i in bit_pattern]
return bit_pattern, cnt
# パリティ・ビットのチェック対象ビットをもとに、パリティ・ビットを更新する関数
def get_hamming_ecc_code(bit_pattern, n):
for n in range(cnt):
sum = 0
mask = 0b1 << n
# チェック対象ビットを加算
for i in range(1, len(bit_pattern) + 1):
if i & mask != 0:
sum += bit_pattern[i - 1]
# 奇数ならパリティビットを1にする
if sum % 2 == 1:
bit_pattern[2**n - 1] = 1
return bit_pattern
# 引数のビットパターンに誤りがあるか判定する関数
def check_ecc_code(bit_pattern):
# パリティ・ビット数を計算
cnt = 0
while True:
if len(bit_pattern) < 2**cnt:
break
cnt += 1
loss_bit = 0
for n in range(cnt):
sum = 0
mask = 0b1 << n
# チェック対象ビットを加算
for i in range(1, len(bit_pattern) + 1):
if i & mask != 0:
sum += bit_pattern[i - 1]
# 奇数となるnを加算する
if sum % 2 == 1:
loss_bit += (2**n)
if loss_bit > 0:
print(f'{loss_bit} bit can be errored.')
else:
print('No error bit.')
上記では3つの関数を定義しています。
-
insert_parity_bit
引数のビットパターンにパリティ・ビットを挿入し、挿入後のビット・パターンとパリティ・ビット数を返す関数です。while文の中では、ビット・パターン(num)の長さと挿入されるパリティ・ビットの位置を比較することで必要なパリティ・ビットの数を取得し、初期値として0を挿入しています。 -
get_hamming_ecc_code
パリティ・ビットのチェック対象ビットをもとに、パリティ・ビットを更新して Hamming ECC Codeを取得する関数です。for ループの中では、パリティ・ビットのチェック対象ビットをマスク処理と論理和によって取得してそれらを加算していき、合計値(sum)が奇数であればパリティ・ビットに1を代入しています。 -
insert_parity_bit
引数のビットパターンに誤りがあるか判定する関数です。get_hamming_ecc_code関数と似たようなことをやっており、合計値(sum)が奇数となるパリティ・ビットを合計することで、誤りのあるビット位置を取得しています。これで誤りを検出できるのがすごいですよね。
テスト
簡単なテストをしてみました。
test.py
print('[Get Hamming ECC]')
input = '1001_1010'
bit_pattern, cnt = insert_parity_bit(input)
ecc_code = get_hamming_ecc_code(bit_pattern, cnt)
# そのままだとリストなので、strにキャスト
hamming_ecc_code = ''.join([str(i) for i in ecc_code])
print(f'Hamming ECC Code: {hamming_ecc_code}\n')
print('[Judge Hamming ECC]')
expected = [0, 1, 1, 1, 0, 0, 1, 0, 1, 0, 1, 0]
test_bit_1 = [1, 1, 1, 1, 0, 0, 1, 0, 1, 0, 1, 0]
test_bit_2 = [0, 0, 1, 1, 0, 0, 1, 0, 1, 0, 1, 0]
test_bit_3 = [0, 1, 0, 1, 0, 0, 1, 0, 1, 0, 1, 0]
test_bit_4 = [0, 1, 1, 0, 0, 0, 1, 0, 1, 0, 1, 0]
test_bit_5 = [0, 1, 1, 1, 1, 0, 1, 0, 1, 0, 1, 0]
test_bit_6 = [0, 1, 1, 1, 0, 1, 1, 0, 1, 0, 1, 0]
test_bit_7 = [0, 1, 1, 1, 0, 0, 0, 0, 1, 0, 1, 0]
test_bit_8 = [0, 1, 1, 1, 0, 0, 1, 1, 1, 0, 1, 0]
test_bit_9 = [0, 1, 1, 1, 0, 0, 1, 0, 0, 0, 1, 0]
test_bit_10 = [0, 1, 1, 1, 0, 0, 1, 0, 1, 1, 1, 0]
test_bit_11 = [0, 1, 1, 1, 0, 0, 1, 0, 1, 0, 0, 0]
test_bit_12 = [0, 1, 1, 1, 0, 0, 1, 0, 1, 0, 1, 1]
check_ecc_code(expected)
check_ecc_code(test_bit_1)
check_ecc_code(test_bit_2)
check_ecc_code(test_bit_3)
check_ecc_code(test_bit_4)
check_ecc_code(test_bit_5)
check_ecc_code(test_bit_6)
check_ecc_code(test_bit_7)
check_ecc_code(test_bit_8)
check_ecc_code(test_bit_9)
check_ecc_code(test_bit_10)
check_ecc_code(test_bit_11)
check_ecc_code(test_bit_12)
実行すると以下のようになります。
inputの値は、パタへネ本の例題で使用していた値を借りています。
Hamming ECC Codeは解答と一致していることがわかります。
[Get Hamming ECC]
Hamming ECC Code: 011100101010
[Judge Hamming ECC]
No error bit.
1 bit can be errored.
2 bit can be errored.
3 bit can be errored.
4 bit can be errored.
5 bit can be errored.
6 bit can be errored.
7 bit can be errored.
8 bit can be errored.
9 bit can be errored.
10 bit can be errored.
11 bit can be errored.
12 bit can be errored.
感想
- 難しかったです。まず、パリティ・ビットをどうやって挿入するかでつまずきました。最初から2進数で処理する方法があまり浮かびませんでした。また、パリティ・ビットのチェック対象となるビットを取得する方法も悩みました。
- 上記以外にも実装については様々なやり方があると思います。CPUアーキテクチャだけでなくpythonも勉強中ですので、ベターな記述方法があれば教えていただきたいです。