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

（2，1，2）卷积码的译码设计1前言卷积码是由伊莱亚斯(Elias)于1954年首先提出来的。它充分利用了各组之间的相关性，本组的信息元不但决定本组的监督元，而且也参与决定以后若干组的监督元。同时在译码过程中，不但从该时刻所收到的码组中提取译码信息，而且还利用以后若干时刻内所收到的码组来提取有关信息。无论从理论上还是实际上均已证明其性能优于线性分组码。近年来众多有关卷积码研究结果表明，卷积码最有希望实现香农信道编码定理。但卷积码在译码理论及实际应用较为复杂，这些缺点限制了其进一步发展和应用。维特比译码算法由维特比（Viterbi）1964年提出，算法实质是最大似然译码，但它利用了编码网格图的特殊结构，在网格图中选择一条路径，使相应的译码序列与接收到的序列之间的汉明距(即量度)最小的一种最大似然译码方法，从而大大降低了计算的复杂性。目前，第三代移动通信系统(3G)在我国已经开始紧锣密鼓地实施，它带来的高速度、高品质的无线通信服务，将使我们领略到信息技术的无穷魅力。信道纠错编码技术作为保证信息可靠传输的技术，在3G各系统中广泛采用，并且我们现在所使用的第二代移动通信系统，如GSM、CDMA通信系统，还有卫星与空间通信系统广泛采用了卷积码信道编、译码技术。本次设计将以（2，1，2）卷积码为例，通过单片机，实现卷积码的译码，借助RS232完成单片机与单片机、单片机与计算机的串口通信，借助7279完成键盘扫描和数码管显示。（2，1，2）卷积码的译码设计2第一章系统组成及工作原理本次设计的（2，1，2）卷积码的译码由89C52单片机为工具，接收来自另一单片机或计算机的编码信息，通过7279的键盘扫描和数码管显示功能可以方便地观察到单片机接收的信息和译码结果。其系统框图如下图1－1所示。MAX232芯片能实现EIA-RS-232C的正负电压与TTL的高低电平之间的转换，通过它能够方便实现单片机与单片机、单片机与计算机间的串口通信。HD7279是一片具有串行接口的,可同时驱动8位共阴极数码管的智能显示驱动芯片,该芯片同时还可连接多达64键的键盘矩阵,单片即可独立完成显示、键盘接口的全部功能。采用7279芯片能够节省单片机资源，降低编程复杂度。1.1总体系统分析本系统的具体设计要求为：系统框图1.用汇编语音进行（2，1，2）卷积码的译码，并要求在数码管上显示输入的信息；2.用RS232串行芯片实现单片机与计算机的信息传输；3.用RS232串行芯片实现单片机与单片机的信息传输；4.在上位机上显示所传输的译码结果。1.2系统单元功能模块本系统具有以下单元功能模块：1.单片机译码部分；2.RS232串口通信部分；3.数据显示部分。89C52（编码）89C52MAX232RS2口89C52（译码）89C527279RS2口数码管、键盘RS2口MAX232RS2口图1－1系统框图（2，1，2）卷积码的译码设计3第二章软件设计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-2c2,i=bi+bi-2图2－1(2，1，2)卷积码编码器设寄存器m1、m2的起始状态为全零，则编码器的输入输出时序关系可用图2－2表示。（2，1，2）卷积码的译码设计4图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中编码器所对应的网格图，……（2，1，2）卷积码的译码设计5其中实线表示“0”，虚线表示“1”。图2－4网格图2.1.4卷积码的译码卷积码的译码方法可分为两大类。一类是代数译码，利用编码本身的代数结构进行译码，不考虑信道的统计特性；另一类是概率译码，这种译码建立在最大准则的基础上，由于计算时用到了信道的统计特性，因而提高了译码性能，但这是以增加硬件复杂度为代价的，常用的概率译码方法是维特比译码。维特比译码是基于最大似然准则的概率译码，它的基本思想是比较接收序列与所有可能的发送序列，从中选择与接收序列汉明距离最小的发送序列作为译码输出。可能的发送序列与接收序列的汉明距离称为量度。维特比译码使用网格图描述卷积码，每个可能的发送序列都与网格图中的一条路径相对应，如果在某个节点上发现某条路径已不可能与接收序列具有最小距离，那么就放弃这条路径，这样一直进行到倒数第二级。由于这种方法较早地丢弃了那些不可能的路径，因而减轻了译码的工作量。2.2系统总流程本系统的总流程图如图2－5所示。其主要功能模块有：系统初始化、数据接收、读数据、数据判断、显示、维特比译码。下面对各个部分进行说明。1.系统初始化堆栈指针SP设为67H，清10H－7FH内存单元，7279初始化，设置定时器1工作于方式2，波特率为1200，启动定时器，串行口工作于方式2并允许串口接收数据。2.数据接收当译码器接收到有效数据时，将接收到的12字节的数据存于存贮器16H－21H中，并将其转换为适合维特比译码的6字节数据，存于存贮器10H－15H单元中。1010111100000101011010010110111111110000000000011011（2，1，2）卷积码的译码设计6图2－5系统总流程图3.读数据当有键按下时，读取键值，并存于Acc寄存器中。4.数据判断判断按键号，并根据键号转向相应的处理程序。5.显示将接收到的数据或译码结果直观的在数码管上显示出来。（2，1，2）卷积码的译码设计76.维特比译码对接收到的数据进行维特比译码，并将译码结果存于存贮器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所示。（2，1，2）卷积码的译码设计8图2－7接收串口数据流程图2.5读数据部分主程序循环中每次都要判断是否有键按下，当有键按下时，调用读键值子程序，读出此按键的键号，并将键号存于Acc寄存器中，为后面的判断键号作准备。读键值流程图如图2－8所示。2.6数据判断部分当有键按下时，判断按键号，并根据键号转向相应的处理：如果键号为“1”，数码管显示接收数据的前8位；如果键号为“2”，数码管显示接收数据的后4位；如果键号为“3”，则对接收到的数据进行译码并显示译码结果；如果键号为“4”，对7279进行初始化；如果是其它键号，则不做任何处理。其程序流程在主程序流程图2－5中已经体现出来。图2－8读键值流程图7279的CS引角脚置低电平7279的CS引角恢复高电平（2，1，2）卷积码的译码设计92.7显示部分显示子程序能够将接收到的数据或译码结果直观的在数码管上显示出来。显示子程序有3个，分别为DISP1、DISP2、DISP3，它们分别用于显示接收数据的前8位、接收数据的后4位、维特比译码结果。现以DISP3为例说明显示部分，其流程图如图2－9所示。图2－9显示子程序流程图2.8维特比译码部分维特比译码又可分为维特比译码主程序、求状态历史记录和累计误差子程序、求状态顺序子程序、求译码结果子程序。7279的CS引角脚置低电平7279的CS引角恢复高电平（2，1，2）卷积码的译码设计101．维特比译码主程序当按键“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，其中带阴影的为幸存路径所经历的状态。（2，1，2）卷积码的译码设计11表2.1状态历史记录表12345600000000010001010002020302001000000001000011000202030000求状态历史记录和误差流程图如图2－11所示，其流程图又可以分为三个部分，分别如图2－12、2－13、2－14所示。图2－11求状态历史记录和误差流程图t状态图2－13求第2步译码状态历史记录和误差流程图图2－12求第1步译码状态历史记录和误差流程图（2，1，2）卷积码的译码设计12图2－14求第3，4，5，6步译码状态历史记录和误差流程图（2，1，2）卷积码的译码设计133.求状态顺序子程序根据上面求出的