计网复习——海明码的原理和代码实现

日常复习408的一天，把孩子闲的。花了一上午复习了python语法。

以数据1010为例讲述海明码的编码原理和过程：

1. 确定海明码的位数

海明码分为两部分：有效信息（n位）+校验位（k位），满足条件

现在1010对应n=4，则复合要求的k至少为3

则完整的海明码我们可以用4+3=7位来表示

2.确定校验位的分布

意思是在7个海明码位中选定3个位置作为校验位。第i个校验位放在第个海明码位上

3. 分组以形成校验关系

每个数据位用多个校验位进行校验，但要满足条件：被校验数据位的海明位号等于校验该数据位的各校验位海明位号之和。其实就是把D_i的二进制表示中的1的下标提取出来，作为相应位置的校验位，然后求这些校验位的异或。

4.校验位取值

校验位P_i的值为第i组（由该校验位校验的数据位）所有位求异或

5. 海明码的校验原理

每个校验组分别利用校验位和参与形成该校验位的信息位进行奇偶校验检查，，构成k个校验方程组，若“S1 S2 S3” 的值为 “000”，则说明无措，否则说明出错，且这个数就是错误位的位号。

5. 代码实现

import numpy as np
# 辅助函数：用来获取一个正整数的二进制位为1的所有下标
def get_ones_positions(num):
    positions = []
    binary = bin(num)[2:]  # 将整数转换为二进制字符串，并去掉开头的"0b"
    for i, digit in enumerate(binary[::-1]):  # 反向遍历二进制字符串的每一位
        if digit == '1':
            positions.append(i + 1)  # 如果当前位是1，则将索引添加到结果列表中
    return positions


def HaiMingCode(passage):
    # 0. 将二进制倒转过来，方便处理
    passage = passage[::-1]

    # 1. 获取海明码校验位数
    n = len(passage) # 信息位数
    k = 1 # 校验位数
    while n + k > pow(2, k) - 1:
        k += 1

    # 2. 确定校验位的分布
    P_index_array = [pow(2, i) for i in range(k)] # 校验位下标
    D_index_array = list(np.arange(1, n + k + 1)) # 数据位下标
    D_index_array = [x for x in D_index_array if x not in P_index_array]
    H_array = np.zeros(n + k, dtype = int)
    print("P_index_array:", P_index_array)
    print("D_index_array:", D_index_array)
    PD = {i + 1 : [] for i in range(k)}

    # 3. 分组形成校验关系
    for idx, D_index in enumerate(D_index_array):
        P_index_list = get_ones_positions(D_index)
        for P_index in P_index_list:
            PD[P_index].append(idx + 1)
    print("PD:", PD)        

    # 4. 逐一异或，求校验位取值
    for P_key, P_value in PD.items():
        num = int(passage[P_value[0] - 1])
        for D_index in range(1, len(P_value)):
            num ^= int(passage[P_value[D_index] - 1])
        H_array[P_index_array[P_key - 1] - 1] = num
        
    # 5. 获得海明码
    for j, i in enumerate(D_index_array):
        H_array[i - 1] = int(passage[j])
    print("H_array:", H_array)