通信工程 / 系统课时

从网格图读取编码状态转移

从网格图读取编码状态转移

给定卷积码的输入比特,怎样从网格图读出每拍的状态、分支输出和后续路径?这里采用码率为 1/2、约束长度为 3 的 (7,5) 卷积码,先列出四状态的全部转移,再展开四拍时间网格,最后手算并验证两条候选路径的输出。

学习目标

  • 根据移位寄存器抽头列出四个状态的八条分支。
  • 区分状态图与按时间展开的网格图,正确读取 输入/输出。
  • 追踪两条候选路径,核对各拍输出及完整码字。

从抽头推导状态转移

约定生成多项式为八进制 (7,5)8(7,5)_8,对应两个输出抽头 111 和 101。当前输入为 utu_t,前两拍输入为 a=ut−1a=u_{t-1}、b=ut−2b=u_{t-2},状态记为 st=(a,b)s_t=(a,b)。初始寄存器清零时,起始状态是 00。

两位输出依次为 v0,t=ut⊕a⊕bv_{0,t}=u_t\oplus a\oplus b、v1,t=ut⊕bv_{1,t}=u_t\oplus b,下一状态是 st+1=(ut,a)s_{t+1}=(u_t,a)。每个状态只可能选择输入 0 或 1,因此四个状态共有八条分支。

当前状态 输入 0:输出 / 下一状态 输入 1:输出 / 下一状态
00 00 / 00 11 / 10
01 11 / 00 00 / 10
10 10 / 01 01 / 11
11 01 / 01 10 / 11

例如,状态 10 意味着 a=1,b=0a=1,b=0;若本拍输入 0,两路输出为 10,寄存器更新为 01。状态图的边标注采用 输入/两位输出,因此该分支写作 0/10。

卷积码(7,5)的四状态图与八条输入输出分支

把状态图展开成时间网格

状态图表示所有允许的转移,但不区分这些转移发生在哪一拍。时间网格将同样的四个状态复制到 t=0 至 t=4 的五列中;每条边只从第 tt 列连接到第 t+1t+1 列,因此四拍输入对应四段边、五个状态节点。

读图时遵守固定次序:先在当前列找到状态,再选标有本拍输入的边,读取该边的两位输出,最后落到下一列的状态。例如,从 t=0 的 00 输入 1,必须沿 1/11 到达 t=1 的 10,不能直接跳到 11。

四拍卷积码网格图中的两条候选路径及逐拍输出

列出候选路径的输出

设两条候选输入分别为 1011 与 1101,并且都从 00 开始。沿网格每走一段,就记录一对输出;将四对按时间顺序拼接,得到各自的八位编码结果。

候选路径 输入序列 状态序列(含初态) 每拍输出 八位码字
A 1011 00→10→01→10→11 11 10 00 01 11100001
B 1101 00→10→11→01→10 11 01 01 00 11010100

路径 A 的第二拍从状态 10 输入 0,得到 10 并进入 01;第三拍再输入 1 时,输出却是 00。这说明分支输出由当前输入与历史状态共同决定,不能把输入 1 固定对应某一输出对。

两条路径的末状态分别为 11 和 10,这里没有追加归零尾比特。未给定接收序列或分支距离时,它们都只是合法候选路径,不能判断哪条更接近实际发送路径。

用 Python 验证逐拍分支

下面的 Python 3 示例只依赖标准库:先打印八条状态转移,再逐拍运行两条候选输入,输出状态路径与完整码字。运行后可逐行与上表核对。

python
def step(state, bit):
    a, b = map(int, state)
    # 八进制(7,5)对应两路抽头111与101
    pair = f"{bit ^ a ^ b}{bit ^ b}"
    return f"{bit}{a}", pair

def trace(bits):
    state = "00"  # 初始记忆寄存器清零
    states = [state]
    outputs = []
    for char in bits:
        state, pair = step(state, int(char))
        states.append(state)
        outputs.append(pair)
    return "→".join(states), " ".join(outputs), "".join(outputs)

for state in ("00", "01", "10", "11"):
    branches = []
    for bit in (0, 1):
        nxt, pair = step(state, bit)
        branches.append(f"{bit}/{pair}→{nxt}")
    print(f"{state}: {'  '.join(branches)}")

for name, bits in (("A", "1011"), ("B", "1101")):
    nodes, pairs, codeword = trace(bits)
    print(f"{name} {bits}: {nodes}; {pairs}; {codeword}")

预期输出:

text
00: 0/00→00  1/11→10
01: 0/11→00  1/00→10
10: 0/10→01  1/01→11
11: 0/01→01  1/10→11
A 1011: 00→10→01→10→11; 11 10 00 01; 11100001
B 1101: 00→10→11→01→10; 11 01 01 00; 11010100

若核对结果不同,优先检查三处:状态两位是否按“前一拍、前两拍”排列,下一状态是否为 (当前输入, 原状态第一位),输出顺序是否始终是 7 抽头在前、5 抽头在后。只有这些约定一致,状态图、时间网格与编码结果才能逐条对应。

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

目录与阅读设置

阅读设置

17

记录一个想法

从网格图读取编码状态转移

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

登录哪都通