通信工程 / 系统课时
按汉明度量执行 Viterbi 硬判决
按汉明度量执行 Viterbi 硬判决
收到卷积码比特后,仅凭每一组码对分别判定,容易把局部噪声当成信息位。这里用约束长度为 3 的卷积码,逐拍计算汉明距离、保留每个状态的最优幸存路径,再从终态回溯,恢复带有单比特错误的发送序列。
学习目标
- 根据卷积编码器的状态和输入,列出网格图中的分支及输出码对。
- 用汉明距离更新路径度量,并为每个状态保留一条幸存路径。
- 编写并运行 Viterbi 硬判决译码器,核对路径度量与恢复结果。
建立四状态网格
采用码率 、约束长度 的卷积码,生成多项式为八进制 ,即二进制抽头 与 。每输入 1 位就输出 2 位,编码器记住最近的 2 个历史输入。
设当前输入为 ,状态为 ,其中 是上一拍输入、 是上上拍输入。输出码对和下一状态分别为:
- 第一输出位:。
- 第二输出位:。
- 下一状态:;因此状态只有
00、01、10、11四种。
例如从状态 00 出发,输入 0 产生 00,仍停在 00;输入 1 产生 11,转到 10。接收机不知道输入是哪一支,必须把两条候选分支都计入搜索。

累计汉明距离并选择幸存路径
硬判决只接收已经量化为 0 或 1 的比特。对每个接收码对 ,分别计算它与候选输出 不同的位数,称为汉明距离 。例如 ,。
从初始状态 00 开始,令其路径度量为 0,其他状态不可达。每一拍执行:
- 从所有可达旧状态分别尝试输入
0和1,计算输出码对及下一状态。 - 将该分支的汉明距离加到旧路径度量上。
- 如果多条路径汇入同一下一状态,只保留累计距离最小的路径,并记录它的前驱状态和输入位;距离相等时使用固定规则打破平局。
设发送信息位为 1011,添加两位 00 使编码器回到终态 00。发送码对为 11 10 00 01 01 11;第三组的第二位翻转后,收到 11 10 01 01 01 11。各拍最小累计度量如下,— 表示不可达:
| 已处理码对 | 状态 00 | 状态 01 | 状态 10 | 状态 11 |
|---|---|---|---|---|
11 |
2 | — | 0 | — |
11 10 |
3 | 0 | 3 | 2 |
… 01(第3拍) |
1 | 2 | 1 | 3 |
| 第4拍 | 2 | 3 | 2 | 1 |
| 第5拍 | 3 | 1 | 3 | 2 |
| 第6拍 | 1 | 3 | 3 | 3 |
第一拍从 00 输入 1 得到输出 11,分支距离为 0,故状态 10 的度量为 0。第三拍虽然收到错误的 01,正确路径仍可凭后续码对保持优势;最终已知终态 00 的累计度量为 1。
编写 Viterbi 译码器
下面的 Python 3 程序保留每拍各状态的最优前驱,而不是枚举所有完整输入序列。译码结束后从已知终态反向读取记录。这里按状态排序后遍历、对同分候选保留先到的路径,保证结果可复现。
def transition(state, bit):
a, b = state
output = (bit ^ a ^ b, bit ^ b) # (7,5) 八进制抽头
return output, (bit, a)
def encode(bits):
state, pairs = (0, 0), []
for bit in bits:
out, state = transition(state, bit)
pairs.append("".join(map(str, out)))
return pairs
def viterbi_hard(received):
metrics = {(0, 0): 0} # 起始状态已知
history = []
for pair in received:
next_metrics, back = {}, {}
for state in sorted(metrics):
for bit in (0, 1):
out, next_state = transition(state, bit)
distance = sum(int(x) != y for x, y in zip(pair, out))
cost = metrics[state] + distance
# 每个下一状态只保留最小度量的前驱
if next_state not in next_metrics or cost < next_metrics[next_state]:
next_metrics[next_state] = cost
back[next_state] = (state, bit)
metrics = next_metrics
history.append(back)
state, decoded = (0, 0), [] # 两位零尾保证终态为 00
for back in reversed(history):
state, bit = back[state]
decoded.append(bit)
decoded.reverse()
return decoded, metrics[(0, 0)]
message = [1, 0, 1, 1]
sent = encode(message + [0, 0])
received = sent.copy()
received[2] = "01" # 模拟第三个码对出现一位翻转
decoded, metric = viterbi_hard(received)
print("发送码对:", " ".join(sent))
print("接收码对:", " ".join(received))
print("恢复信息:", "".join(map(str, decoded[:-2])))
print("终止尾位:", "".join(map(str, decoded[-2:])))
print("路径度量:", metric)预期输出:
发送码对: 11 10 00 01 01 11
接收码对: 11 10 01 01 01 11
恢复信息: 1011
终止尾位: 00
路径度量: 1判断译码是否可靠
本例回溯得到输入 101100,去掉末尾用于清空寄存器的两位 00,恢复原信息 1011。最优度量 1 表示选中的编码路径与接收比特总共相差 1 位,不代表已证明只有这一位发生错误,也不等于任意误码分布都能纠正。
- 已知零尾终止:按本例固定从终态
00回溯;若发送端没有添加零尾,不能强行选00,通常应从末拍最小度量状态回溯。 - 长序列实现:保存每拍每个状态的前驱;对于固定约束长度 ,译码运算量随接收拍数 线性增长,约为 。
- 硬判决的局限:输入只有比特值,丢失了接收信号的可靠度。若接收机还保留幅度或对数似然信息,应改用对应的软判决分支度量,而不是直接套用汉明距离。
可以把程序中的 received[2] = "01" 改为 received[2] = "00" 验证无误码情况:恢复信息仍为 1011,路径度量变为 0。