通信工程 / 系统课时

按汉明度量执行 Viterbi 硬判决

按汉明度量执行 Viterbi 硬判决

收到卷积码比特后,仅凭每一组码对分别判定,容易把局部噪声当成信息位。这里用约束长度为 3 的卷积码,逐拍计算汉明距离、保留每个状态的最优幸存路径,再从终态回溯,恢复带有单比特错误的发送序列。

学习目标

  • 根据卷积编码器的状态和输入,列出网格图中的分支及输出码对。
  • 用汉明距离更新路径度量,并为每个状态保留一条幸存路径。
  • 编写并运行 Viterbi 硬判决译码器,核对路径度量与恢复结果。

建立四状态网格

采用码率 R=1/2R=1/2、约束长度 K=3K=3 的卷积码,生成多项式为八进制 (7,5)(7,5),即二进制抽头 111111 与 101101。每输入 1 位就输出 2 位,编码器记住最近的 2 个历史输入。

设当前输入为 uu,状态为 (a,b)(a,b),其中 aa 是上一拍输入、bb 是上上拍输入。输出码对和下一状态分别为:

  • 第一输出位:v1=u⊕a⊕bv_1=u\oplus a\oplus b。
  • 第二输出位:v2=u⊕bv_2=u\oplus b。
  • 下一状态:(u,a)(u,a);因此状态只有 00、01、10、11 四种。

例如从状态 00 出发,输入 0 产生 00,仍停在 00;输入 1 产生 11,转到 10。接收机不知道输入是哪一支,必须把两条候选分支都计入搜索。

四状态卷积码的网格分支与最优回溯路径

累计汉明距离并选择幸存路径

硬判决只接收已经量化为 0 或 1 的比特。对每个接收码对 rr,分别计算它与候选输出 vv 不同的位数,称为汉明距离 dH(r,v)d_H(r,v)。例如 dH(01,00)=1d_H(01,00)=1,dH(01,10)=2d_H(01,10)=2。

从初始状态 00 开始,令其路径度量为 0,其他状态不可达。每一拍执行:

  1. 从所有可达旧状态分别尝试输入 0 和 1,计算输出码对及下一状态。
  2. 将该分支的汉明距离加到旧路径度量上。
  3. 如果多条路径汇入同一下一状态,只保留累计距离最小的路径,并记录它的前驱状态和输入位;距离相等时使用固定规则打破平局。

设发送信息位为 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 程序保留每拍各状态的最优前驱,而不是枚举所有完整输入序列。译码结束后从已知终态反向读取记录。这里按状态排序后遍历、对同分候选保留先到的路径,保证结果可复现。

python
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)

预期输出:

text
发送码对: 11 10 00 01 01 11
接收码对: 11 10 01 01 01 11
恢复信息: 1011
终止尾位: 00
路径度量: 1

判断译码是否可靠

本例回溯得到输入 101100,去掉末尾用于清空寄存器的两位 00,恢复原信息 1011。最优度量 1 表示选中的编码路径与接收比特总共相差 1 位,不代表已证明只有这一位发生错误,也不等于任意误码分布都能纠正。

  • 已知零尾终止:按本例固定从终态 00 回溯;若发送端没有添加零尾,不能强行选 00,通常应从末拍最小度量状态回溯。
  • 长序列实现:保存每拍每个状态的前驱;对于固定约束长度 KK,译码运算量随接收拍数 TT 线性增长,约为 O(T2K)O(T2^K)。
  • 硬判决的局限:输入只有比特值,丢失了接收信号的可靠度。若接收机还保留幅度或对数似然信息,应改用对应的软判决分支度量,而不是直接套用汉明距离。

可以把程序中的 received[2] = "01" 改为 received[2] = "00" 验证无误码情况:恢复信息仍为 1011,路径度量变为 0。

按自己的节奏,确认真正理解。

目录与阅读设置

阅读设置

17

记录一个想法

按汉明度量执行 Viterbi 硬判决

0 / 10000 · 笔记保存到账号。未提交的修改会在关闭、离开或刷新后丢失。

登录哪都通