パリティチェックとハミング符号の基礎

データ通信や保存の際に、情報の正確性を確保するために用いられる技術に「パリティチェック」と「ハミング符号」があります。これらはエラー検出やエラー訂正に利用され、特に通信システムで重要な役割を果たします。この教材では、これらの基本概念とPythonによる実装を学びます。

パリティチェック

概要

パリティチェックは、データが正しく伝送されたかどうかを確認するための単純な方法です。データのビット列に対して、偶数パリティまたは奇数パリティを使用して、追加のビット（パリティビット）を付加します。

• 偶数パリティ: 1のビット数が偶数になるようにパリティビットを設定します。
• 奇数パリティ: 1のビット数が奇数になるようにパリティビットを設定します。

Pythonでの実装

以下は、偶数パリティを実装するPythonのサンプルコードです。

def calculate_parity_bit(data):
    """
    データの偶数パリティビットを計算する関数
    :param data: ビット列（文字列）
    :return: パリティビット（'0'または'1'）
    """
    ones_count = data.count('1')
    if ones_count % 2 == 0:
        return '0'  # 偶数なのでパリティビットは0
    else:
        return '1'  # 奇数なのでパリティビットは1

# 使用例
data = "1101001"
parity_bit = calculate_parity_bit(data)
print(f"データ: {data}, パリティビット: {parity_bit}")

コード解説

1. calculate_parity_bit関数は、ビット列を引数として受け取ります。
2. ones_countは、データ内の'1'の数をカウントします。
3. 1の数が偶数か奇数かによって、パリティビットを決定します。
4. 最後に、パリティビットを表示します。

ハミング符号

概要

ハミング符号は、特定のビットのエラーを検出し、訂正するための方法です。ハミング符号は、データビットに冗長ビットを追加して、エラーの位置を特定できるようにします。

ハミング符号の生成

ハミング符号を生成するための基本的な手順は次の通りです。

1. データビットを決定し、パリティビットの位置を計算します。
2. 各パリティビットの値を計算します。

以下は、(7, 4)ハミング符号を生成するPythonのサンプルコードです。

def hamming_encode(data):
    """
    ハミング符号を生成する関数 (7, 4)
    :param data: データビット（リスト）
    :return: ハミング符号（リスト）
    """
    # 位置 1, 2, 4 はパリティビットの位置
    p1 = data[0]  # d1
    p2 = data[1]  # d2
    p3 = data[2]  # d3
    d1 = data[3]  # d4
    d2 = data[4]  # d5
    d3 = data[5]  # d6
    d4 = data[6]  # d7

    # パリティビットの計算
    p1 = d1 ^ d2 ^ d4  # 1番目のパリティビット
    p2 = d1 ^ d3 ^ d4  # 2番目のパリティビット
    p3 = d2 ^ d3 ^ d4  # 3番目のパリティビット

    return [p1, p2, d1, p3, d2, d3, d4]

# 使用例
data_bits = [1, 0, 1, 1]  # d1, d2, d3, d4
hamming_code = hamming_encode(data_bits)
print(f"データビット: {data_bits}, ハミング符号: {hamming_code}")

コード解説

1. hamming_encode関数は、データビットをリストで受け取ります。
2. それぞれのデータビットを取得し、パリティビットを計算します。ここでは、XOR演算を使用してパリティビットを求めています。
3. 最後に、生成されたハミング符号を表示します。

ハミング符号のデコード

受信側でエラーを検出し、訂正するためにハミング符号をデコードする必要があります。以下は、ハミング符号のデコード処理を実装したサンプルコードです。

def hamming_decode(hamming_code):
    """
    ハミング符号をデコードし、エラーを検出・訂正する関数
    :param hamming_code: ハミング符号（リスト）
    :return: デコードされたデータビットとエラー位置
    """
    p1 = hamming_code[0]  # 1番目のパリティビット
    p2 = hamming_code[1]  # 2番目のパリティビット
    p3 = hamming_code[3]  # 3番目のパリティビット

    # パリティビットのチェック
    s1 = p1 ^ hamming_code[2] ^ hamming_code[4] ^ hamming_code[6]
    s2 = p2 ^ hamming_code[2] ^ hamming_code[5] ^ hamming_code[6]
    s3 = p3 ^ hamming_code[4] ^ hamming_code[5] ^ hamming_code[6]

    error_position = s1 * 1 + s2 * 2 + s3 * 4  # エラー位置の計算

    if error_position != 0:
        print(f"エラー位置: {error_position}")
        # エラー訂正
        hamming_code[error_position - 1] ^= 1

    return hamming_code[2:4] + hamming_code[4:6]  # データビットを返す

# 使用例
received_code = [1, 0, 1, 0, 0, 1, 1]  # 受信したハミング符号
decoded_data = hamming_decode(received_code)
print(f"デコードされたデータビット: {decoded_data}")

コード解説

1. hamming_decode関数は、ハミング符号を引数として受け取ります。
2. パリティビットを使用して、エラーの位置を特定します。
3. エラーが検出された場合、その位置のビットを訂正します。
4. 最後に、デコードされたデータビットを返します。

まとめ

この教材では、パリティチェックとハミング符号の基本概念を学び、Pythonを使用してそれを実装する方法を示しました。これらの技術は、データ通信や保存において非常に重要な役割を果たしており、エラーの検出と訂正の手段として広く利用されています。これを基に、さらなる学習を進めていきましょう。