奇偶、CRC 与海明码

本课目标

能把比特流组织为帧，逐步维护序号、窗口、确认、定时器、介质状态或MAC表；能从报文/时序状态计算检错码、利用率、最小帧和转发结果。

核心机制

奇偶校验能发现奇数个比特错误；CRC把数据后补r个0，用生成多项式做模2除法，余数作为FCS，接收余数0仅表示通过该检错规则；海明码用多个校验位定位单比特错误，满足2^r≥m+r+1。

帧、时序与状态推演

数据1101、生成多项式1011时r=3，模2除法余数001，发送1101001。

统一表格记录“时刻、发送方窗口、接收方期望、帧/ACK、定时器、介质或转发表状态”。每次事件只更新受影响对象；帧丢失、ACK丢失、超时和重复帧必须分别处理。计算前先明确序号位数、窗口边界、传播方向和单位。

可运行模型

def crc(data,g):
 a=list(map(int,data+'0'*(len(g)-1)));p=list(map(int,g))
 for i in range(len(data)):
  if a[i]:
   for j,x in enumerate(p):a[i+j]^=x
 return ''.join(map(str,a[-(len(g)-1):]))
print(crc('1101','1011'))

先手算再运行。修改比特串、生成多项式、窗口、传播时延、码片或MAC帧顺序，说明状态和结果怎样变化。

边界与错因

检错通过不保证绝对无错；确认号语义必须按协议定义；GBN和SR的接收窗、重传范围不同。CSMA监听不能消除传播期碰撞；交换机学习源地址而非目的地址；VLAN分广播域，普通交换端口分冲突域。PPP点到点链路不需要介质竞争。

状态复核时还要检查帧序号是否落在窗口、同一帧是否重复交付、令牌是否唯一、交换表端口是否由最近源帧学习，以及帧长度能否覆盖最坏碰撞往返时间。

迁移练习

为同一场景加入数据帧丢失、ACK丢失或序号回绕，重新画时间线；将集线器换交换机、将端口划入不同VLAN，重画冲突域和广播域；改变帧长与传播时延，重新判断利用率和碰撞检测。

课内验收

完成下方两道在线题，并提交完整比特运算、窗口表或MAC学习表。只写最终答案而没有状态迁移视为未完成。