通信工程 / 系统课时

处理尾比特与译码回溯边界

处理尾比特与译码回溯边界

同一段卷积码数据,如果把网格的终态条件设错,末尾几位就可能被误译。这里使用约束长度为 3 的卷积码,通过补零终止、直接截断和有限回溯实验,确认哪些比特应参与译码、哪些比特应被丢弃。

学习目标

  • 区分补零终止与截断网格的合法末态,计算尾比特带来的码率开销。
  • 说明回溯深度 DD 对判决时机和帧末冲刷的影响。
  • 运行硬判决 Viterbi 示例,复现短回溯和错误终态造成的输出差异。

用末态约束区分终止与截断

使用码率为 1/2、约束长度 K=3K=3 的卷积编码器,两个生成器抽头为二进制 111、101(八进制 7、5)。编码器保存前两位输入,所以状态只有 00、01、10、11 四种。以下独立帧均从 00 开始,原始信息为 101101001011,共 12 位。

方式 编码器输入 发射编码比特 译码终态 交付信息位
补零终止 10110100101100 28 位 固定为 00 前 12 位
截断网格 101101001011 24 位 四种状态中选路径度量最小者 全部 12 位

补零终止追加 K−1=2K-1=2 个 0,把编码器强制送回 00。这两个输入位也会产生四个编码比特,必须经过信道并参与 Viterbi 译码,只是恢复原始信息时不输出尾比特。有效信息码率为 12/28≈0.429,低于母码的 1/2。

截断网格不补尾比特,末态不能无依据地固定为 00。本例发送完 12 位后实际状态为 11,但译码器应依据接收数据选择最优末态。截断也不同于尾咬合码:尾咬合要求起始状态等于结束状态,而不是任意结束。

补零终止与截断网格的尾部状态对比

回溯深度怎样影响最后几位

Viterbi 在每一拍为四个状态保留最佳路径及其前驱。完整回溯在接收全帧后才确定路径;有限回溯深度 DD 则在收到第 tt 拍后,从当前最优状态沿幸存路径回退 DD 拍,立即固定最早的那个信息位。DD 是回溯拍数,不是要删除的尾比特数。

本例终止帧共 14 拍。如果取 D=8D=8,第 8 拍才能输出第 1 位;到第 14 拍只及时输出了 7 位,还剩 7 位必须在帧末从已知终态 00 完整回溯并冲刷出来,然后再删除最后 2 个尾输入位。截断帧则要从末拍路径度量最小的状态冲刷。

短回溯更早出结果,但不同路径可能尚未合并,早期判决无法被后续证据纠正。常用经验是让回溯深度取编码器记忆长度的约 5 倍;这里约为 10 拍,并非纠错保证。帧短于设定深度时,应直接对整帧回溯,不能等待不存在的后续符号。

运行硬判决 Viterbi 对比

使用 Python 3.10 或更新版本,下面的程序不需要第三方库。它使用汉明距离作分支度量:先把终止帧第一个双比特编码符号的两位都翻转,再比较完整回溯和 D=2D=2、D=8D=8 的有限回溯;最后使用无噪声截断帧验证错误固定终态的后果。为便于检验,示例保存全部幸存路径历史,实际流式译码可以改用按 DD 循环复用的决策缓存。

python
from math import inf

def encode(bit_string):
    state, coded = 0, []
    for char in bit_string:
        bit = int(char)
        a, b = state >> 1, state & 1
        coded.append((bit ^ a ^ b, bit ^ b))
        state = (bit << 1) | a
    return coded

def forward(received):
    metrics = [0, inf, inf, inf]  # 独立帧的初态为 00
    survivors, records = [], []
    for observed in received:
        next_metrics = [inf] * 4
        step = [None] * 4
        for state, score in enumerate(metrics):
            if score == inf:
                continue
            a, b = state >> 1, state & 1
            for bit in (0, 1):
                next_state = (bit << 1) | a
                expected = (bit ^ a ^ b, bit ^ b)
                distance = sum(x != y for x, y in zip(observed, expected))
                candidate = score + distance
                if candidate < next_metrics[next_state]:
                    next_metrics[next_state] = candidate
                    step[next_state] = (state, bit)
        survivors.append(step)  # 每一状态保存胜出前驱
        records.append(next_metrics)
        metrics = next_metrics
    return survivors, records

def traceback(survivors, records, final_state=None):
    state = (min(range(4), key=lambda s: records[-1][s])
             if final_state is None else final_state)
    cost = records[-1][state]
    bits = []
    for step in reversed(survivors):
        state, bit = step[state]
        bits.append(str(bit))
    return "".join(reversed(bits)), cost

def delayed(survivors, records, depth, final_state):
    emitted = []
    for t in range(depth - 1, len(survivors)):
        state = (final_state if t == len(survivors) - 1
                 else min(range(4), key=lambda s: records[t][s]))
        # 只回溯 depth 步,然后固定最早的一位
        for i in range(t, t - depth, -1):
            state, bit = survivors[i][state]
        emitted.append(str(bit))
    # 帧结束时从确定终态冲刷仍未输出的 depth-1 位
    full_bits, _ = traceback(survivors, records, final_state)
    return "".join(emitted) + (full_bits[-(depth - 1):] if depth > 1 else "")

payload = "101101001011"
terminated = encode(payload + "00")
corrupted = terminated.copy()
corrupted[0] = (terminated[0][0] ^ 1, terminated[0][1] ^ 1)
paths, records = forward(corrupted)
whole, metric = traceback(paths, records, 0)
print(f"终止全回溯:{whole[:-2]},路径距离={metric}")
print(f"终止 D=2:{delayed(paths, records, 2, 0)[:-2]}")
print(f"终止 D=8:{delayed(paths, records, 8, 0)[:-2]}")

paths, records = forward(encode(payload))
print(f"截断自由终态:{traceback(paths, records)[0]}")
print(f"截断误设终态00:{traceback(paths, records, 0)[0]}")

预期输出:

text
终止全回溯:101101001011,路径距离=2
终止 D=2:000101001011
终止 D=8:101101001011
截断自由终态:101101001011
截断误设终态00:101101001000

按帧边界检查译码结果

终止帧的最优路径距离为 2,与人为翻转的两个编码比特对应。D=2D=2 过早固定了前两位;在这组接收样本中 D=8D=8 与完整回溯一致,但不代表 8 拍对任何噪声都足够。无噪声截断帧若被错误要求回到 00,尾部 011 会误成 000,说明末态条件可以单独引入译码错误。

检查实现时按以下顺序定位边界:

  1. 核对译码拍数:终止帧应消耗 14 对编码比特,而不是只译码前 12 对;截断帧只消耗 12 对。
  2. 核对终态选择:补零终止从 00 回溯;截断取末拍度量最小的状态。如果帧起点也未复位,不能继续只把初态 00 设为可达。
  3. 核对冲刷与裁剪顺序:先补齐尚未输出的 D−1D-1 位,再对终止帧删掉最后 2 个尾输入位。先删接收符号或漏冲刷,都会造成长度或内容错误。

在这套配置下,最终两种方式都应向上层交付恰好 12 个信息比特。需要连续处理多帧时,还应明确编码器是否每帧复位;若状态跨帧延续,起始状态及回溯历史也必须随之传递。

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

目录与阅读设置

阅读设置

17

记录一个想法

处理尾比特与译码回溯边界

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

登录哪都通