【信道编码】2 卷积码、状态转移图、状态转移表、网格表示和码字路径

写在最前面

肖丽霞老师的《信道编码》课程笔记。

经历了chatgpt的自信胡言乱语，输出y1和输出y2弄混，公式弄错

终于，理解并做对了orz

理解原理后，确实很简单

感谢书琪宝，yyds

【重点原理】对于（2,1,2）卷积编码器，连接逻辑如下：

（注意看图，三个指向的对应输出2）

• 输出1: 输入 ⊕ 寄存器2
• 输出2: 输入 ⊕ 寄存器1 ⊕ 寄存器2

参考：https://blog.csdn.net/tomatomatodo/article/details/121917054

例题先行，原理随后

示例：输入为01011100

状态转移表

状态转移图

卷积码的原理

请参考：https://blog.csdn.net/weixin_46258766/article/details/119060965

卷积码是一种错误纠正码，广泛用于通信系统中以增强数据传输的可靠性，尤其是在有噪声的信道中。卷积码通过在发送的数据中添加冗余信息来实现，这样即使在接收端接收到部分错误的数据，也能通过额外的冗余信息进行错误检测和纠正。

原理与结构

卷积码的核心原理是使用移位寄存器和若干逻辑门（通常是异或门）来处理输入的数据比特。下面是卷积码的一些基本组成部分和工作原理：

1. 移位寄存器：输入的数据比特序列被送入一系列的移位寄存器。这些寄存器按照时钟信号的节拍逐步移动数据，每个时钟周期将数据向前推进一位。
   
2. 逻辑门（通常是异或门）：移位寄存器的输出被送到一组逻辑门中，这些门根据预设的生成多项式进行操作。异或门是最常用的逻辑门，它根据特定的连接方式结合多个寄存器的输出。
   
3. 生成多项式：在卷积码中，生成多项式定义了每个输出位是如何从输入位及其历史（即寄存器中的位）中生成的。这些多项式决定了卷积编码器的连接方式和输出。
   
4. 码率：卷积码的码率定义为 ( \frac{k}{n} )，其中 ( k ) 是每次输入的比特数（通常为1），( n ) 是每次输出的比特数。码率较低意味着更高的冗余度，通常能提供更强的错误纠正能力。
   
5. 约束长度：约束长度是指计算每个输出比特所需要的输入比特的最大数量，它等于移位寄存器的大小加一。约束长度越大，编码器的记忆能力越强，纠错能力通常越好，但复杂性和延时也会增加。
   

工作流程

• 输入比特被序列地送入移位寄存器。
• 根据生成多项式，移位寄存器中的比特与逻辑门相连，生成输出比特。
• 输出比特包含了输入信息及其历史的信息，从而形成了冗余。

误差纠正

在接收端，卷积码通常使用维特比算法（一种最大似然译码算法）进行译码。这种算法可以高效地找到最可能产生观测到的接收序列的发送序列。维特比算法通过在可能的状态转移图中寻找一条最佳路

径（即最小错误路径）来工作。

总之，卷积码通过在发送端添加冗余信息，并在接收端使用复杂的译码技术，有效地提高了数据传输的可靠性，尤其是在信道条件恶劣的环境中。这使得卷积码在无线通信、卫星通信和数据存储等多种

应用中非常有价值。

（2,1,2）卷积编码器

（2,1,2）卷积编码器是一种典型的卷积编码器，常用于错误控制编码中。

这种编码器的参数（2,1,2）表示输出位数为2，输入位数为1，以及编码器内部的存储器单元数为2。

工作原理

1. 输入位数（1）：这意味着每个时钟周期编码器接收一个比特。
2. 输出位数（2）：每个输入比特会被编码成两个输出比特。这种从1比特到2比特的转换能够引入冗余，从而提高信号在噪声环境下的可靠性。
3. 存储器单元数（2）：卷积编码器有两个存储单元，这些单元存储过去接收的输入比特。这种记忆特性使得输出比特不仅依赖于当前输入比特，还依赖于之前的一或多个输入比特。

结构和示例

卷积编码器的典型结构包括几个移位寄存器和一些逻辑门，通常是异或门（XOR）。例如，一个（2,1,2）卷积编码器可能会有以下的连接方式：

• 第一个输出比特是输入比特与第一个寄存器内容的异或结果。
• 第二个输出比特可能是输入比特、第一个寄存器和第二个寄存器内容的异或结果。

状态转移和输出表格

一个（2,1,2）卷积编码器由于有两个寄存器，存在4个可能的状态，加上二进制输入，会产生8种可能的输入/状态组合。

对于（2,1,2）卷积编码器，连接逻辑如下：

• 输出1: 输入 ⊕ 寄存器2
• 输出2: 输入 ⊕ 寄存器1 ⊕ 寄存器2

这里的每一步，输出都是基于当前输入和之前状态的组合，通过逻辑门（如异或门）计算得到。

下面是如何标记这些转移：

• 状态00：

• 输入0：输出00，转移到状态00
• 输入1：输出11，转移到状态01

• 状态01：

• 输入0：输出11，转移到状态10
• 输入1：输出01，转移到状态11

• 状态10：

• 输入0：输出01，转移到状态00
• 输入1：输出10，转移到状态01

• 状态11：

• 输入0：输出10，转移到状态10
• 输入1：输出11，转移到状态11

基于前面的分析，我们可以为每个状态定义两个转移：

状态图的构建步骤

1. 定义节点：每个节点代表一个状态（例如，00, 01, 10, 11），状态代表寄存器的当前值。
2. 定义边：每个状态有两条边离开，一条对应输入0，另一条对应输入1。
3. 标记边：每条边根据其输入和生成的输出进行标记，格式通常为“输入/输出1输出2”，并指向新的状态。

1. 绘制方向：箭头表示状态的转移方向。

状态图的绘制

根据之前表格中的数据，可以确定每个状态对输入0和1的响应及输出。

每个状态有两个从该状态出发的箭头，分别对应输入0和输入1的响应。

基于我们已有的状态转移和输出表，我们可以构建卷积码的状态图，这是一种可视化表示，有助于理解状态之间的转移和由此产生的输出。状态图展示了卷积编码器在接收输入时如何从一个状态迁移到另一个状态，同时也展示了每种输入下的输出结果。

这样的状态图有助于直观理解卷积编码器在不同输入下如何改变状态，并且能够看到每种情况下的输出码元。这是通信系统设计和分析中的一个重要工具，特别是在设计和测试卷积编码方案时非常实用。

状态转移图

要画一个（2,1,2）卷积编码器的状态转移图，需要首先确定所有可能的状态和每个状态如何响应输入0或1。对于一个有两个寄存器的卷积编码器，状态可以是：00、01、10、11。每个状态对应于寄存器2和寄存器1的二进制内容。状态转移图将显示每个状态对于输入0或1的响应，以及相应的输出和下一状态。

法1步骤以绘制状态转移图

1. 画出所有可能的状态：以圆圈表示，并在圆圈内部标记状态名（例如，00、01、10、11）。
2. 为每个状态添加两个箭头：一个箭头对应输入0的响应，另一个箭头对应输入1的响应。
3. 标记每个箭头：标记应包括输入/输出。例如，从状态00接收输入0并输出01（如果输出1为0，输出2为1，则标记为0/01）。
4. 指明箭头的方向：箭头应指向基于当前状态和输入的下一状态。

箭头表示从某一状态到每一状态，0/10表示在这个状态下，输入0得到输出10。

以下是如何绘制状态图的描述：

• 状态00：

• 0/00 -> 状态00
• 1/11 -> 状态10

• 状态01：

• 0/10 -> 状态00
• 1/01 -> 状态10

• 状态10：

• 0/01 -> 状态01
• 1/10 -> 状态11

• 状态11：

• 0/11 -> 状态01
• 1/00 -> 状态11

每个箭头从当前状态指向下一状态，并在旁边标记输入和输出。例如，从状态00出发的两条边分别指向状态00和10，边上标记分别为"0/00"和"1/11"。

这样描述的状态转移图可以用笔和纸手动绘制，也可以使用各种软件工具如Graphviz、Lucidchart或Microsoft Visio等绘制。这种图形是通信系统设计和分析中常用的工具，有助于理解和验证编码器的行为。

法2卷积码状态转移

网格表示和码字路径（通过网格图寻找最匹配的路径）

在卷积码的分析和可视化中，网格表示和码字路径是两个常用的工具，它们帮助了解和说明卷积码的行为以及如何对编码的数据流进行解码。

网格表示（Trellis Diagram）

卷积码的网格表示，通常称为网格图或格子图（Trellis Diagram），是一种表示卷积码状态转移和路径选择的图形工具。它对于理解和实现维特比算法至关重要。

构建步骤

1. 节点：网格图的每个列代表一个时间步，每个列中的节点代表在该时间步可能的编码器状态。
2. 边：节点之间的边代表可能的状态转移。每个边上标有从一个状态转移到另一个状态时的输入/输出。

1. 时间步：每进一个时间步，输入一个新的数据比特，并产生一个或多个输出比特。编码器状态更新，移向新的状态。

功能

• 显示所有可能的状态和在每个时间步的转移。
• 识别并选择最佳路径（即最有可能产生观测到的接收数据序列的路径）。

码字路径

码字路径是网格图中从起始点到结束点的路径，表示了一个特定的输入序列如何被编码。每条路径都对应于特定的输入序列，并在网格图中由一系列边组成，这些边展示了序列经过编码器状态的变化。

解码过程

在接收端，维特比算法通过网格图搜索最佳路径（即最小汉明距离或最小错误概率路径）来译码。这条路径对应的就是最可能的输入序列。

• 观测到的序列：接收机接收到的序列，可能由于信道噪声含有错误。
• 搜索最佳路径：根据每条路径的可能性（通常是路径代价的累积），选择最佳路径。
• 汉明距离：每条路径产生的输出与实际接收到的序列之间的汉明距离用于评估路径。

例题

我们可以绘制一个网格图，每个时间步展示所有可能的状态转移。如果已知的接收序列是010111...，我们将通过网格图寻找最匹配的路径，这将是解码过程的一部分。

直接对照上图来连接点。

网格表示和码字路径提供了一种直观的方式来分析和理解卷积编码及其在信号传输中的作用，尤其是在实现和测试编码解码算法时非常有用。

应用

卷积编码器在无线通信系统中尤为重要，例如在卫星通信、深空通信以及移动通信中广泛使用，以提高数据传输的可靠性。通过引入错误纠正能力，卷积编码帮助通信系统在有错误的信道环境下恢复原始数据。