(2,1,2)卷积码的译码设计(0)

（2，1，2）卷积码的译码设计

前言

卷积码是由伊莱亚斯(Elias)于1954 年首先提出来的。它充分利用了各组之间的相关性，本组的信息元不但决定本组的监督元，而且也参与决定以后若干组的监督元。同时在译码过程中，不但从该时刻所收到的码组中提取译码信息，而且还利用以后若干时刻内所收到的码组来提取有关信息。无论从理论上还是实际上均已证明其性能优于线性分组码。近年来众多有关卷积码研究结果表明， 卷积码最有希望实现香农信道编码定理。但卷积码在译码理论及实际应用较为复杂， 这些缺点限制了其进一步发展和应用。

维特比译码算法由维特比（Viterbi）1964年提出，算法实质是最大似然译码， 但它利用了编码网格图的特殊结构， 在网格图中选择一条路径，使相应的译码序列与接收到的序列之间的汉明距(即量度)最小的一种最大似然译码方法，从而大大降低了计算的复杂性。

目前，第三代移动通信系统(3G) 在我国已经开始紧锣密鼓地实施，它带来的高速度、高品质的无线通信服务，将使我们领略到信息技术的无穷魅力。信道纠错编码技术作为保证信息可靠传输的技术，在3G各系统中广泛采用，并且我们现在所使用的第二代移动通信系统，如GSM、 CDMA 通信系统，还有卫星与空间通信系统广泛采用了卷积码信道编、译码技术。

本次设计将以（2，1，2）卷积码为例，通过单片机，实现卷积码的译码，借助RS232完成单片机与单片机、单片机与计算机的串口通信，借助7279完成键盘扫描和数码管显示。

1

（2，1，2）卷积码的译码设计

第一章 系统组成及工作原理

本次设计的（2，1，2）卷积码的译码由89C52单片机为工具，接收来自另一单片机或计算机的编码信息，通过7279的键盘扫描和数码管显示功能可以方便地观察到单片机接收的信息和译码结果。其系统框图如下图1－1所示。

89C5289C52 编码 ） （（译码）数码管、键盘MAX232 MAX232 7279

MAX232芯片能实现EIA-RS-232C的正负电压与TTL的高低电平之间的转换，通过它能够方便实现单片机与单片机、单片机与计算机间的串口通信。

HD7279是一片具有串行接口的, 可同时驱动8位共阴极数码管的智能显示驱动芯片, 该芯片同时还可连接多达64键的键盘矩阵, 单片即可独立完成显示、键盘接口的全部功能。采用7279芯片能够节省单片机资源，降低编程复杂度。

图 1－1 系统框图 1.1 总体系统分析

本系统的具体设计要求为：系统框图

1. 用汇编语音进行（2，1，2）卷积码的译码，并要求在数码管上显示输入的信

息；

2. 用RS232串行芯片实现单片机与计算机的信息传输； 3. 用RS232串行芯片实现单片机与单片机的信息传输； 4. 在上位机上显示所传输的译码结果。

1.2 系统单元功能模块

本系统具有以下单元功能模块：

1. 单片机译码部分； 2. RS232串口通信部分； 3. 数据显示部分。

2

（2，1，2）卷积码的译码设计

第二章 软件设计

2.1 相关理论说明

2.1.1 卷积码的描述

卷积码是把k个信息比特的序列编成n个比特的码组，每个码组的n-k个校验位与本码组的k个信息位有关，而与其他码组无关。为了达到一定的纠错能力和编码效率，分组码的长度一般都比较大。编译码时必须把整个信息码组存储起来，由此产生的译码延时随n的增加而增加。

卷积码是一个有限记忆系统，它也将信息序列分割成长度k的一个个分组，然后将k个信息比特编成n个比特，但k和n通常很小，特别适合以串行形式进行传输，时延小。与分组码不同的是在某一分组编码时，不仅参看本时刻的分组而且参看以前的N-1个分组，编码过程中互相关联的码元个数为nN。N称为约束长度。常把卷积码写成（n，k，N-1）卷积码。正因为卷积码在编码过程中，充分利用了各级之间的相关性，无论是从理论上还是实际上均已证明其性能要优于分组码。 2.1.2 卷积码的编码

本次设计以（2，1，2）卷积码为例。图2－1为这种卷积编码器的结构，它的编码方法是：序列依次移入一个两级移位寄存器，编码器每输入一位信息bi,输出端的开关就在c1和c2之间来回切换一次，输出为c1,i和c2,i ，其中

c1,i=bi+bi-1+bi-2 c2,i=bi+bi-2

图2－1 (2，1，2)卷积码编码器

设寄存器m1、m2的起始状态为全零，则编码器的输入输出时序关系可用图2－2表示。

3

（2，1，2）卷积码的译码设计

… … 图2－2 (2，1，2)卷积码编码器的输入输出时序

要使最后1 位输入同样影响3对输出，并且使编码器回到全零状态，还需使编

码器多输出2对信息，为了做到这一点，需要增加2个时钟循环，并且在此期间保持输入为0，这一过程叫做“点亮”编码器。如果不执行“点亮”操作，最后2位输入信息的纠错能力就会下降。 2.1.3 卷积码的图解表示

根据卷积码的特点，常采用图解表示法对其进行研究。主要的图解表示法有两种，即状态转移图、网格图。

因为卷积码的编码器的记忆性是有限的，所以可以使用状态转移图来表示其转移过程。在状态转移图中，卷积编码器的每一个状态对应于一个椭圆，状态的转移用两个椭圆间的有向线段表示，在线上标出状态转移的输入和对应的输出。图3－1中（2，1，2）卷积码的状态转移图如图2－3所示。

图2－3 状态转移图

另一种更为常用的描述卷积码的方法是网格图。该图根据时间的推进来反映状态的转移。网格图上纵坐标表示状态，横坐标表示时间，每一次状态转移利用连接相邻时间点上两个状态的有向线段来表示。图2－4是图2－3中编码器所对应的网格图，

4

（2，1，2）卷积码的译码设计

其中实线表示“0”，虚线表示“1”。

00 00 00

00 11 11 11 11 01 00

10 10

10 01 01 01 11 10

图2－4 网格图

2.1.4 卷积码的译码

00 11 11 00 10 01 01 10 卷积码的译码方法可分为两大类。一类是代数译码，利用编码本身的代数结构进行译码，不考虑信道的统计特性；另一类是概率译码，这种译码建立在最大准则的基础上，由于计算时用到了信道的统计特性，因而提高了译码性能，但这是以增加硬件复杂度为代价的，常用的概率译码方法是维特比译码。

维特比译码是基于最大似然准则的概率译码，它的基本思想是比较接收序列与所有可能的发送序列，从中选择与接收序列汉明距离最小的发送序列作为译码输出。可能的发送序列与接收序列的汉明距离称为量度。

维特比译码使用网格图描述卷积码，每个可能的发送序列都与网格图中的一条路径相对应，如果在某个节点上发现某条路径已不可能与接收序列具有最小距离，那么就放弃这条路径，这样一直进行到倒数第二级。由于这种方法较早地丢弃了那些不可能的路径，因而减轻了译码的工作量。

2.2 系统总流程

本系统的总流程图如图2－5所示。其主要功能模块有：系统初始化、数据接收、读数据、数据判断、显示、维特比译码。下面对各个部分进行说明。 1.系统初始化

堆栈指针SP设为67H，清10H－7FH内存单元，7279初始化，设置定时器1工作于方式2，波特率为1200，启动定时器，串行口工作于方式2并允许串口接收数据。 2. 数据接收

当译码器接收到有效数据时，将接收到的12字节的数据存于存贮器16H－21H中，并将其转换为适合维特比译码的6字节数据，存于存贮器10H－15H单元中。

5

（2，1，2）卷积码的译码设计

图2－5 系统总流程图

3.读数据

当有键按下时，读取键值，并存于Acc寄存器中。 4.数据判断

判断按键号，并根据键号转向相应的处理程序。 5.显示

将接收到的数据或译码结果直观的在数码管上显示出来。

6

（2，1，2）卷积码的译码设计

6.维特比译码

对接收到的数据进行维特比译码，并将译码结果存于存贮器58H－5DH单元中。

2.3 初始化部分

系统初始化是为以后串口接收数据，7279显示作好准备，其的主要工作是将堆栈指针SP设为67H，清10H－7FH内存单元，7279初始化，设置定时器1工作于方式2（自动恢复初始的8位计数器），波特率为1200 (不一定要1200，但波特率过高，数据传输过程中可能出错），启动定时器，串行口工作于方式2（9位异步串行通信，一帧信息为11位：1位起始位，8位数据位，1位附加数据位，1位停止位）并允许串口接收数据。

图2－6 系统初始化流程图

2.4数据接收部分

在主程序的循环中，每次都要判断是否从串中接收到有效数据（RI是否为1），当串中接收到有效数据时，将接收到的12字节的数据存于16H－21H中，并将其转换为适合维特比译码的6字节数据，存于10H－15H单元中。串口数据接收流程如下图2－7所示。

7

（2，1，2）卷积码的译码设计

7279的CS引角脚置低电平 7279的CS引角恢复高电平 图2－7 接收串口数据流程图

图2－8 读键值流程图 2.5 读数据部分

主程序循环中每次都要判断是否有键按下，当有键按下时，调用读键值子程序，读出此按键的键号，并将键号存于Acc寄存器中，为后面的判断键号作准备。读键值流程图如图2－8所示。

2.6 数据判断部分

当有键按下时，判断按键号，并根据键号转向相应的处理：如果键号为“1”，数码管显示接收数据的前8位；如果键号为“2”，数码管显示接收数据的后4位；如果键号为“3”，则对接收到的数据进行译码并显示译码结果；如果键号为“4”，对7279进行初始化；如果是其它键号，则不做任何处理。其程序流程在主程序流程图2－5中已经体现出来。

8

（2，1，2）卷积码的译码设计

2.7 显示部分

显示子程序能够将接收到的数据或译码结果直观的在数码管上显示出来。显示子程序有3个，分别为DISP1、DISP2、DISP3，它们分别用于显示接收数据的前8位、接收数据的后4位、维特比译码结果。现以DISP3为例说明显示部分，其流程图如图 2－9所示。

7279的CS引角脚置低电平 7279的CS引角恢复高电平 图2－9 显示子程序流程图

2.8 维特比译码部分

维特比译码又可分为维特比译码主程序、求状态历史记录和累计误差子程序、求状态顺序子程序、求译码结果子程序。

9

（2，1，2）卷积码的译码设计

1．维特比译码主程序

当按键“3”按下时，对接收到的数据进行维特比译码，并将译码结果存于58H－5DH单元中。维特比译码程序流程图如图2－10所示。

图2－10 维特比译码流程图 2. 求状态历史记录和累计误差子程序

状态历史记录表能够记录下维特比译码过程中每一步译码后，状态的变化过程，其所占内存空间为40H－57H。累计误差记录表能够记录上一次译码结束时的累计误差（可能的发送序列与接收序列的汉明距离）和本次译码结束后的累计误差，其中上一次的累计误差存于30H－33H单元中，本次结束后的累计误差存于34H－37H单元中。

本次设计所接收到的数据总共有6组，所以要将译码分为6步实现。已知起始状态为“0”（00），则下一个状态只可能是“0”（00）或“2”（10）（参考图2－4），所以第一步译码只需计算两个累计误差，并将其存于30H、32H单元中即可，第二步译码需根据第一次译码的累计误差求出本次译码完后的累计误差，存于34H－37H单元中，用34H－37H中的内容覆盖30H－33H中的内容，作为下一步的起始累计误差，并将各个状态的前导状态分别存于44H－47H单元中，第三步的译码过程较第二步只需加一个累计误差的比较，淘汰较大的累计误差，以后的译码都是第三步译码的重复，所以从第三步开始可以用循环完成。

假如输入的序列为010100，则接收到的序列（译码后的序列）为001110001011，根据上述过程，可以得到状态历史记录表2.1，其中带阴影的为幸存路径所经历的状态。

10

（2，1，2）卷积码的译码设计

表2.1 状态历史记录表 状 态 t 1 00 00 00 00 2 00 02 00 02 3 00 02 00 02 4 01 03 01 03 5 00 02 00 00 6 01 00 00 00 00 01 10 11

求状态历史记录和误差流程图如图2－11所示，其流程图又可以分为三个部分，分别如图2－12、2－13、2－14所示。

图2－11 求状态历史记录和误差流程图 图2－12 求第1步译码状态历

史记录和误差流程图 11

图2－13 求第2步译码状态历史记录和误差流程图

（2，1，2）卷积码的译码设计

图2－14 求第3，4，5，6步译码状态历史记录和误差流程图

12

（2，1，2）卷积码的译码设计

3. 求状态顺序子程序

根据上面求出的状态历史记录表，可以求出状态顺序表，将状态顺序存于60H

－66H单元中。求状态顺序流程图如图2－15所示。

图2－16 求译码结果流程图

图2－15 求状态顺序流程图

4. 求译码结果子程序

根据上一步的状态顺序表，可以查TRANS_TAB表得出维特比译码结果，将译码

结果保存在58H－5DH单元中。求译码结果流程图如图2－16所示。

13

（2，1，2）卷积码的译码设计

第三章 实验调试与分析

3.1 使用的主要仪器和工具

1. 带有串行接口的微机一台 2. 5V稳压电源一个 3. 单片机最小系统板两块 4. 串口线一根 5 Keil仿真软件 6. 串口调试助手

3.2 调试方法

在设计过程中，要先编写好软件，软件又可分为多个模块，需要对每个模块分别进行调试。

维特比译码是此次设计的核心部分。先编写好维特比译码程序，在Keil中对其进行编译，检查是否存在语法错误，如有语法错误，先要排除所有语法错误；为了进行仿真，需要在仿真前先假定已接收到编码数据001110001011，在维特比译码程序中已经预留了READ子程序，可用来在仿真前将以上6组数据分别写入10H－15H内存单元中；然后可以进行仿真，观察40H－57H单元中的状态历史记录表、60H－66H单元中的状态顺序记录表、58H－5DH中的译码结果是否与理论值一致，如不一致，察看问题出在哪里，对其进行修改，在此过程中可以使用Keil的断点执行、单步执行功能，并随时关注寄存器、关键内存单元中内容的变化，这样可以方便地逐步对维特比译码程序进行完善，最后能够实现正确译码功能。

其它如键盘扫描、数码管显示、数据接收等模块，其程序执行过程与外部输入有关，所以不能使用Keil进行仿真（但可使用Keil对语法错误进行检查），要把这些程序连同维特比译码程序一起烧入单片机中，使单片机与微机进行串口通信，观察实验现象，根据实验现象逐步定位并排除程序或硬件错误，最后要能实现所有功能。

在串口调试助手的发送框中输入001110001011，点击发送按钮（之前波特率要设为1200），查看单片机是不是接收到001110001011，是否译码结果为010100，如果是说明所有模块工作正常。再将发送框中的001110001011改为000110001011（只要改动不大，其它数据也可以），再次发送，看是否单片机还能够译码为010100，如果是说明所编写的维特比译码程序具有纠错能力。

把另一块编码单片机与此单片机通过MAX232进行连接，重复使用串口调试助手完成的功能，验证两块单片机之间是否能够正常通信。

14

（2，1，2）卷积码的译码设计

3.3 调试中出现的故障及解决方案

上述调试过程并不是一帆风顺的，调试过程中会遇到许多故障，有些故障很容易找到原因，但有一些故障，其原因难以发现。

例如程序中有一句“DJNZ R7,LW0”,由于LWO太远(离“DJNZ R7,LW0”超过128字节),所以程序找不到,需要将其拆分为“DJNZ R7,LP0”和“LP0: LJMP LW0”两句。

还有在用两块单片机进行通信时，只要编码单片机一发送数据，译码单片机就会死机，开始怎么也找不到错误，后面将编码单片机与微机（串口调试助手波特率设为1200）进行通信，发现单片机每发送12个数据，串口调试助手则接收到18个数据，所以怀疑是由波特率不一致导致的错误，后来检查发现编码单片机的晶振频率为6MHz，与译码单片机的11.0592MHz不同，所以两者波特率不同，导致接收单片机接收到18个数据，陷入死循环，改变编码单片机的TH1、TL1，使编码单片机与译码单片机的波特率都为1200，两块单片机能够正常通信。

15

（2，1，2）卷积码的译码设计

YM:

MOV @R1,A

INC R0 INC R1

DJNZ R7,C0 RET

LCALL READ

LCALL WTBYM ;维特比译码程序

LCALL ZTSX LCALL OUTPUT RET

READ: RET

WTBYM: MOV R0,#10H MOV R1,#44H MOV A,@R0 MOV R2,A MOV R3,#00H LCALL CMP MOV 30H,A MOV R3,#11H LCALL CMP MOV 32H,A

INC R0 MOV A,@R0 MOV R2,A MOV R3,#00H LCALL CMP ADD A,30H MOV 34H,A MOV @R1,#00H INC R1

MOV R3,#10H LCALL CMP ADD A,32H MOV 35H,A MOV @R1,#02H INC R1

MOV R3,#11H LCALL CMP ADD A,30H MOV 36H,A MOV @R1,#00H

;维特比译码主体程序(求状态历史记录和累计误差) 21

（2，1，2）卷积码的译码设计

INC R1

MOV R3,#01H LCALL CMP ADD A,32H MOV 37H,A MOV @R1,#02H INC R1

MOV 30H,34H MOV 31H,35H MOV 32H,36H MOV 33H,37H

MOV R7,#04H LW0: INC R0 MOV A,@R0 MOV R2,A MOV R3,#00H LCALL CMP ADD A,30H MOV 34H,A MOV R3,#11H LCALL CMP ADD A,31H

CJNE A,34H,LW1 LW1: JC LW2

MOV @R1,#00H AJMP LW3 LW2: MOV 34H,A MOV @R1,#01H LW3: INC R1

CJNE R7,#01H,LW00 LJMP LW01 LW00: MOV R3,#10H LCALL CMP ADD A,32H MOV 35H,A MOV R3,#01H LCALL CMP ADD A,33H

CJNE A,35H,LW4 LW4: JC LW5

MOV @R1,#02H AJMP LW6 LW5: MOV 35H,A

22

（2，1，2）卷积码的译码设计

MOV @R1,#03H LW6: INC R1

CJNE R7,#02H,LW02 INC R1 INC R1 LJMP LW01 LW02: MOV R3,#11H LCALL CMP ADD A,30H MOV 36H,A MOV R3,#00H LCALL CMP ADD A,31H

CJNE A,36H,LW7 LW7: JC LW8

MOV @R1,#00H AJMP LW9 LW8: MOV 36H,A MOV @R1,#01H LW9: INC R1

MOV R3,#01H LCALL CMP ADD A,32H MOV 37H,A MOV R3,#10H LCALL CMP ADD A,33H

CJNE A,37H,LW10 LW10: JC LW11

MOV @R1,#02H AJMP LW12 LW11: MOV 37H,A MOV @R1,#03H LW12: INC R1

LW01: MOV 30H,34H MOV 31H,35H MOV 32H,36H MOV 33H,37H LJMP LP1 LP0: LJMP LW0 LP1: DJNZ R7,LP0 RET

ZTSX: MOV R0,#65H MOV R1,#54H

将状态顺序存于60H－66H单元中23

; （2，1，2）卷积码的译码设计

MOV 66H,#00H MOV R7,#06H MOV A,@R1 LZ0: MOV @R0,A

CJNE R7,#01H,LZ1 RET

LZ1: MOV R2,A MOV A,R1 SUBB A,#04H ADD A,R2 MOV R1,A MOV 03H,@R1 MOV A,R2 XCH A,R1 SUBB A,R1 XCH A,R1 MOV A,03H DEC R0

DJNZ R7,LZ0 RET

OUTPUT: MOV R7,#06H ;将译码结果存于58H－5DH单元中 MOV R0,#60H MOV R1,#58H MOV R2,#00H CLR C

LOUT0: MOV A,@R0 RL A RL A INC R0 ADD A,@R0

MOV DPTR,#TRANS_TAB MOVC A,@A+DPTR MOV @R1,A INC R1 JZ LOUT1 SETB C LOUT1: MOV A,R2 RLC A MOV R2,A

DJNZ R7,LOUT0 RET

CMP: MOV A,R2 XRL A,R3 MOV R3,#00H

24

（2，1，2）卷积码的译码设计

JNB ACC.0,LC0 INC R3

LC0: JNB ACC.4,LC1 INC R3 LC1: MOV A,R3 RET

TRANS_TAB: DB 00H,0FFH,01H,0FFH,00H,0FFH,01H,0FFH DB 0FFH,00H,0FFH,01H,0FFH,00H,0FFH,01H END

25

本文来源：https://www.bwwdw.com/article/kc27.html