艾睿电子方案平台-知识分享

物联网（Internet of Things）是连接各种物理节点的一种特殊网络，这些物理节点主要由各种各样的传感器组成，包括温度传感器、湿度传感器、压力传感器和图像传感器等等。随着传感技术和无线通信技术的大幅提升，物联网的各种应用也得到飞速发展，万物互联的时代越来越接近我们的生活。

在物联网蓬勃发展的同时，无线通信不可避免的会产生干扰的问题，这样会导致信号的误码率变高，严重影响系统的稳定性。如果采用CRC、累加和等方式验证数据的正确性，则不能解决数据错误后怎样恢复原始数据的问题。如果采用双向通信验证数据是否正确的方式，则会增加通信时间，导致系统延时加重，影响系统的实时性，而且有的单向通信的场合还不能使用这种方式。

本文专门针对这些问题，提出了一种物联网前向纠错的方案。该方案采用了卷积编码和维特比解码的方式，有效的解决了通信误码率的问题，提高了系统的稳定性和实时性。该方案适用于单向、双向通信模式，在发送端使用卷积编码发送，在接收端使用维特比解码，即使在通信过程中有一定的误码率，系统也能自动纠正错误数据，以达到正确通信的目的。

卷积编码

卷积编码（Convolutional Encoding）由Peter Elias在1955年第一次提出，目前已经广泛应用于信道编码领域。卷积编码可以处理一系列数据位，最大的特点就是输出的数据位不但与输入的数据位有关，而且与输入的数据位前面的数据位有关，即所谓的记忆深度，这样很好的提高了数据容错性能。其编码格式有很多种，本文讲解最基本的（2,1,2）格式，即2-bit输出、1-bit输入和2-bit记忆深度。

请参考图一的卷积编码示意图。图中I_n, I_n-1, …, I₁, I₀为输入数据位；C₁, C₀为清零位Clear，其初始值为00；F₁, F₀为补充位Flush，其初始值为00；O₁, O₀为输出数据位；X₁, X₂为异或计算器；S为选择开关。每输入一个数据位，便会输出对应的两个数据位。例如当输入I₀数据位时，I₀对应的输出低位数据位O₀的数值为I₀, C₁, C₀的异或值，而I₀对应的输出高位数据位O₁的数值为I₀, C₀的异或值。依次计算I₁, …, I_n-1, I_n对应的输出数据位。为了保证I_n和I_n-1这两个数据位的编码完整性，还需要计算F₁和F₀补充位对应的输出数据位。其中F₁对应的输出低位数据位的数值为F₁, F₀, I_n的异或值，而F₁对应的输出高位数据位的数值为F₁, I_n的异或值。

图一

请参考图二的卷积编码范例。范例中补充位和输入数据位为0010011，包含5位数据位；输出数据位为11011111101011，共14位输出数据位。依次根据编码规则计算输入数据位和补充位I₀, I₁, …, I₄, F₀, F₁，得到与之对应的各个输出数据位O_0,1, O_2,3, …, O_12,13。输入数据位I₀的输出低位数据位的数值为O₀=I₀^C₁^C₀=1^0^0=1,而输入数据位I₀的输出高位数据位的数值为O₁=I₀^C₀=1^0=1，由此得到O_1,0=11。以此类推，可以计算出所有剩余输出数据位的数值。

图二

当得到所有输出数据位以后，就可以将这些输出数据位无线发送出去，以便接收端进行前向纠错解码。

维特比解码

维特比解码（Viterbi Decoding）是由Andrew Viterbi在1967年发明的，并用他的名字命名。维特比解码具有一定的纠错能力，即使接收到的卷积编码数据有一定的误码存在，也可以使用维特比解码恢复出原始数据。

最常用的维特比解码方法是网格图（Trellis Diagram）分析法，如图三所示。由于（2,1,2）格式具有2-bit记忆深度，所以一共有4种状态，分别是State00, State01, State10和State11，初始状态为State00，此时对应t=0时刻。图中虚线表示输入数据位为0时状态转移的情况，而实线表示输入数据位为1时状态转移的情况。例如，在t=1时的状态为State10，当输入0时，状态转换为State01；当输入1时，状态转换为State11（去掉State10的最低位0，输入新的数据位0或1），分别对应图中的虚线箭头和实线箭头。在任意时刻t，计算并保存接收到的2-bit数据与所有可能的输出数据位之间最小分支汉明距离（Branch Metric），同时累加所有的最小分支汉明距离得到最小路径汉明距离（Path Metric），最后得到的这条最小路径汉明距离的数据就是解码出来的输出数据，进而得到最初的编码输入数据。汉明距离是计算两组数据之间各个对应数据位差异的总和，总和越小，汉明距离就越小，表明这两组数据越接近相同。

图三

网格图的状态、输入数据和输出数据的关系如图四所示。图中虚线箭头表示输入数据为0时从一个状态转移到另外一个状态，而实线箭头表示输入数据为1时从一个状态转移到另外一个状态。图中左边红色数据表示虚线对应的输出数据，而右边蓝色数据表示实线对应的输出数据。这样输出数据和输入数据就有了一一对应的关系，即得到了输出数据就会推导出对应的输入数据。

图四

利用网格分析法，可以找到前面范例输出数据11011111101011的一条汉明距离最小的路径，由于数据没有错误，所以该条路径的汉明距离为0，如图五所示。图中蓝色数据为接收端的卷积编码数据，红色数据为对应的解码数据，这样就完成了维特比解码过程，进而得到原始数据。

图五

假设O₄数据位由于干扰从0变为1，得到11011111111011，如图六所示。在t=3时刻，会存在两条最小汉明距离为1的分支路径，此时会保留这两条路径。在t=4时刻，会存在三条分支路径，汉明距离分别为0、1和1，这三条路径的累计汉明距离分别为1、2和2，此时只保留最小汉明距离路径，也就是去掉了图中红色路径，仍然保持最优路径，O₄数据位从1恢复到了0，这样就完成了前向自动纠错的功能。

图六

总结

实践证明，卷积编码和维特比解码具有很强的前向纠错能力，可以全部由软件编程实现，以便节约硬件成本，值得在物联网中推广应用。另外，卷积编码还有不同的编码方式，可以采用私有格式，用以实现通信数据密文发送，起到一定的加密作用，对系统的安全性也有很大的帮助。

AIOT