卷积码编译码规则
⑴ 卷积码的过程
下面就让我们来看看网格图是如何描述卷积编码过程的：仍以（2,1,2）为例，假定输入序列为1011010100，起始状态（零时刻）为状态a（零状态）。第一个有效时钟沿来临后，编码器接收到输入信息“1”，根据图所示网格图知该时刻（即时刻1）状态为b，并输出其对应的编码结果“11”，同样在下一个时刻（时刻2）接收到输入信息“0”，状态变为c并输出“10”，接下来的输入数据依次类推……，由此我们可以用网格图作出该例子的卷积编码过程，如图5所示，其中两个状态连线之间的信息为输出结果。
⑵ 卷积码的表示方法
描述卷积码编码器过程的方法有很多，如矩阵法、多项式、码树和网格图等，这里我们主要介绍和卷积码编码器结构密切相关的多项式法，以及与卷积码译码密切相关的网格图法。
结构图多项式法就是由卷积码的生成多项式直接得出其编码器的结构图。如前面例子中的（2，1，2）卷积码的生成多项式矩阵为：G(D)=[1 ,1 ]
其中，D是延迟算子，生成多项式的第一项为1 D ，表示输出编码的第一个码元等于输入码元x（n）与前两个时刻输入的码元x（n-1）、x（n-2）的模2和，同理第二项类似。 将编码器寄存器中的内容组合（x（n-1）、x（n-2））定义为编码器状态。如仍以前面所举的例子（2，1，2）为例，则该编码器的状态有四种：00，10，01和11，下面分别用a，b，c，d来代替。编码器在每一个时钟沿打入一个输入信息x（n），因此图示寄存器组合内容就变为（x（n），x（n-1））即状态发生了转移，并同时输出G0（n）、G1（n）。由此我们可以将图所示编码过程用右图所示的状态图表示。
编码器
由图所示，随着信息序列不断输入，编码器就不断从一个状态转移到另一个状态并同时输出相应的码序列，所以图3所示状态图可以简单直观的描述编码器的编码过程。因此通过状态图 很容易给出输入信息序列的编码结果，假定输入序列为110100，首先从零状态开始即图示a状态，由于输入信息为“1”，所以下一状态为b并输出“11”，继续输入信息“1”，由图知下一状态为d、输出“01”……其它输入信息依次类推，按照状态转移路径a->b->d->c->b->c->a输出其对应的编码结果“110101001011”。
网格图
状态图可以完整的描述编码器的工作过程，但是其只能显示状态转移的过程而不能显示状态转移发生的时刻，由此引出用来表示卷积码的另一种常用方法——网格图。网格图就是时 间与对应状态的转移图（如图），在网格图中每一个点表示该时刻的状态，状态之间的连线表示状态转移。通过观察网格图可以发现在网格图中输入信息x（n）并没有标出，但如观察到转移后的状态表示（x（n），x（n-1））就可以发现输入信息已经隐含在转移后的状态中。在图中还可以发现两个网格图不同主要集中在转移后状态位置不同。重新排序结构（即所谓蝶型结构）是为了优化运算而设计的，因为其中蝶型与蝶型之间是相互独立的。
⑶ 卷积码的原理
DMT和卷积编码调制在DSL中的应用
钟晓建 潘贵敦 马亲民 梁小宇
�
(华中师范大学物理系武汉430079)
【摘要】讨论了离散多音频调制和网格编码相结合的调制方式在DSL中的应用,离散多音频调制DMT〔1〕是一种多载波调制技术，将传输数据根据各子带信噪比按位分配到子带上，使每个子带码元宽度大于多径延迟。如果把调制和纠错编码结合起来，则可使误码率大大降低，是一种带宽利用率较高的调制方式。
�关键词：ADSL离散多音频网格编码〔2〕欧氏距离〔3〕离散傅立叶变换／逆变换
1引 言
� 随着Internet技术的不断发展,人们对传输数据的速度、质量要求越来越高,在当前为了有效地利用现有的资源——电话线，提出了DSL〔1〕(数字用户线)的概念，使用话音频率以上的频带(4 k~1.1 MHz)来调制高速数字信号,按照Δf=4.3125 kHz分割成一个个的子带,由于Δf刚好是音频的宽度，故命名为离散多音频,DMT调制是基于离散傅立叶变换对并行数据进行调制解调的。随着超大规模集成电路(VL SI)和数字信号处理(DSP)技术的不断进步，用FFT实现实时DMT调制已付诸使用。但以往的调制解调系统，纠错编码与调制是各自独立设计并实现的，译码和解调也是如此，这样解调器在接收信号是对信号作独立硬判决，硬判决结果再送给译码器译码，这种硬判决会导致接收端信息的不可恢复的丢失，解决这个问题的方法是在接收端采用软判决译码。DSL技术中就是将DMT和网格编码综合设计，在白噪声环境下比传统技术的误码性能有了很大的提高。这种最佳的编码调制系统是按照编码序列的欧氏距离为设计的量度，这就要求将编码器和调制器当作一个统一的整体进行综合设计，使得编码器和调制器级联后产生的编码信号序列具有最大的欧氏自由距离。从信号空间的角度看，这种最佳编码调制的设计实际上是一种对信号空间的最佳分割。经过实验分析，DMT和卷积编码结合后的编码增益比传统编码的编码增益增加了8 dB。�
2xDSL接入设备体系结构
� 在ADSL的应用当中,其硬件体系结构大致是由线路接口、接收滤波、线路驱动、模拟前端以及DMT收发器这几个模块组成。其中DMT收发器在发端对数据进行复用、循环冗余校验、前向纠错、子带排序、卷积编码、星座映射以及IFFT变换，送到模拟前端变换成模拟信号发送出去，而在收端是将模拟信号经过FFT变换、解映射、维特比译码等一系列反变换，提交给上层。根据T1.413〔4〕标准，采用韦氏16状态4维网格码作为内码，采用Reed�Solomon编码作为前向纠错码，另外由于网格编码对成块的噪声抵抗能力较差，因此在进行网格编码之前将数据进行交织使噪声分散。ADSL的DMT收发器框图大致如图1所示。
3DMT与卷积编码调制原理
� 在ADSL的发送端,将数据分配到不同的子带上,这种分配可以根据各个子带的信噪比来确定分配的bit数。而ADSL系统为各个子带建立并维持了一个比特数和增益大小的表，是在ATU-R一端计算出来并返回给局端。为保证后一子带所带的位数不小于前一子带的位数，先对子带进行排序，即子带按信噪比大小从小到大进行排序。为了使编码获得的码字有较大的欧氏自由距离，采用了四维TCM网格编码，这样位抽取是基于一对子带的,因为一个子带在空间上是二维的,一对相互正交的子带在空间上则是四维的 ，相应的在解码的时候也是一对一对的作维特比译码。欧氏自由距离是在四维空间上计算出来的，这样四维的陪集可以由两个二维的陪集的联合构成，即这样四维TCM网格码的欧氏自由距离可以由两个二维星座图的距离的平方和算出， 在译码系统中，最可能发生错误的情况是在具有最小的平方欧氏距离的两个序列�{an}和{bn}�之间，(前者是发送序列，后者是译码序列)，这一最小平方欧氏距离常又称为平方自由距离，记做：
��编码的目的是为了使这个平方自由距离最大。
�网格编码调制的通过一种特殊的信号映射可变成卷积码的形式。这种映射的原理是将调制信号集分
割成子集，是的子集内的信号间具有更大的空间距离，用编码效率为k/(k 1)的卷积码选择子集，用其余位选择子集中的点。在DSL数字用户环路中用16状态的4维网格编码的编码器结构如图2所示。
其中的卷积编码部分如图3所示。
图2中每两个子带抽取的位数z′=x y-1(x为第一个子带所带的位数，y为第二个子带所带的位数)。{uz′-1,uz′-2，…u1}为原码，输出的是经过卷积以及异或以后的编码，为两个二进制码字，即{vz-y�,vz′-y-1，…v1,v0}和{wy-1,wy-2,…w1,w0}，这两个二进制码字将映射成两个星座点。编码算法使星座点的两个最低位决定星座点的二维陪集{v1,v0}和{w1,w0}实际上是这个上标的二进制表示。对于一帧中最后两个码字，为了使卷积编码状态{s3,s2,s1,s0}回到零状态。让编码前的码字的{u1,u2}={0,0}，则最后两对子带抽取的位数z′＝x y-3。
�
这样编码得出的信号有两个基本特征：
� (1)星座图中所用的信号点数大于未编码同种调制所需的点数(扩大了一倍)，这些附加的信号点为纠错编码提供冗余度。
�(2)采用卷积码在相继的信号点之间引入某种依赖性，因而只有某些信号点序列才是允许出现的，这些允许的信号序列可以模型化为网络结构。可用网格图来表述。
� 在接收端对接收序列进行维特比译码〔4〕，即最大似然译码，可以用网格图求最相似的路径来描述这种算法，它依赖于有限状态的马尔可夫系统的描述，包括状态变迁以及状态变迁的输出码字。在四维TCM�编码的基础上，解码时要对一对一对的数据进行解码，计算码距时也是以四维空间的欧氏距离为标准，取最相似的一条路径。对于长度为L m的网格路径(L为信息序列的长度，m表示后缀为m个0向量)接收序列为所有的网格路径在零时刻发散于同一个初始状态、收敛于第j时刻(j＝L m)的同一个最后一状态。在理想状况下，对于一个存储量无限度的通道，可以将所有可能的路径都记录下来，然后选择其中对数似然函数值最大的作为译码结果。
对数似然函数是将接收序列判定为某条路径的序列的条件概率的对数
��这里的对数似然函数取最大值，实际上是接收的码序列与估计路径的码之间的距离取最小值，是基于欧氏空间距离来计算的。在这里维特比译码算法的核心是回退的观点，采用动态规划法存储数据，如果对每条可能的路径进行存储的话，随着译码深度的增加，存储量将成4的指数增长，这在现实条件下是不可能的。因为每个节点都有四个分支(二输入十六状态的网格图)，因此我们对于j时刻到达的某一状态
δi(i=1,2…，S-1)，进行加—比—选操作，即将所有可能前一时刻的状态的最大似然函数∧j-1(δp)与当前接收的序列和前一状态到当前状态的估计码的似然度相加，选择其中最大的作为j时刻i状
态的最大似然函数值，并在幸存序列j(δi)在原来的基础上加上这条最优的路径u〔δp→δi〕。这样给出的算法可以表述为：
� 变量／存储：
� S—状态数(DSL为16)；
� T—每一状态的分支数(4)；
� j—时刻编号，即第j时刻
�对于用卷积编码完毕的序列可以直接送到数字信号处理器中作IDFT〔5〕变换成串行数据了。每个子带i的二进制码字可以映射成星座图上的复数点(Zi=ai jbi)，为了使输出信号为实信号，频域上的子带i的复数值(i≥N′,N′=N/2)为
��Zi=conj�(ZN-i),(i≥N′，N′=N/2)
即取共轭复数，这样经过离散傅立叶逆变换，得到时域信号：
��此信号经过并／串变换，再通过A／D变换，变成模拟信号送到线路上进行传输。
4仿真结果
� 我们在应用Itex公司的ADSL解决方案中，用该公司提供的局端仿真工具IADT对ADSL链路性能进
行仿真，得到ADSL每个子带(从0~255)的信噪比，再根据这个预测值来确定每个子带的位数和增益值。
从而建立一个与子带一一对应的表，其线路预测的信噪比曲线如图4所示。
我们可以看到，测得的线路上行速率为544
kbps，网络速率(去掉ADSL链路开销)为448 kbps，下行链路速率为8 160 kbps，网络速率为7 616 kbps。
5总 结
� 本文描述了在带宽受限的信道采用DMT和卷积编码相结合的技术，将调制与纠错编码结为一体，高效利用了现有的带宽。随着ADSL技术的逐渐成熟，该编码技术也正在应用于其它领域，如无线通信，针对其信道的衰减特性可以获得较高的带宽利用率。在具体硬件实现上,由于超大规模集成电路的发展，硬件已不再是信号处理的瓶颈了,如以上分析的维特比译码,其对硬件的需求是随着N的增大而迅速增加,需要上十万的门电路实现，现已有单片的维特比译码器，或是在特殊的应用中集成在一块数字芯片中，同时完成RS编码、交织、FFT变换等等。
�参考文献
�
1Asymmetrical Digital Subscriber Lines(ADSL)�ITU-T�Recommendation G.992,Geneva,June,1999
2曹志刚，钱亚生.现代通信原理.北京：清华大学出版社
3Stephen G Wilson.digital Molation and Coding,○C1996 byPrentice�Hall,Inc
4ANSI T1.413�1998,COMMITTEE T1—Telecommunications Working Group T1E1.4 T1E1.4/98�007R5，1998
5John G Proakis.Digital Communications,Third edition,McGraw�Hill 1998
charinput[10]={0,0,1,1,1,0,1,1,1,1};
charoutput[5]={0};
intr1=0,r2=0;
inti;
for(i=0;i<5;i++)
{
output[i]=(input[2*i]+r1+r2)&1;
r2=r1;
r1=output[i];
}
for(i=0;i<5;i++)
printf("%d",output[i]);
printf("
");
⑸ 卷积码的编码原理
卷积码编码器
以二元码为例，编码器如图。输入信息序列为u=(u0，u1，…），其多项式表示为u(x)=u0+u1x+…+ulxl+…。编码器的连接可用多项式表示为g(1,1)(x)=1+x+x2和g(1,2)(x)=1+x2，称为码 的子生成多项式。它们的系数矢量g(1,1)=(111）和g(1,2)=(101）称作码的子生成元。以子生成多项式为阵元构成的多项式矩阵G(x)=[g(1,1)(x),g(1,2)(x)]，称为码的生成多项式矩阵。
⑹ 信息经卷积编码器之后的信息速率如何求
卷积码
卷积码是一种差错控制编码，由P.Elias于1955年发明。因为数据与二进制多项式滑动相关故称卷积码。卷积码在通信系统中应用广泛，如IS-95，TD-SCDMA，WCDMA，IEEE 802.11及卫星等系统中均使用了卷积码。
卷积码使用（n，k，L）表示，码率为R。
n为输出码字；
k为输入的比特信息；
L为约束长度，也称为记忆深度。
R表示为R = k/n。
卷积码是一种有记忆的纠错码，编码规则是将k个信息比特编码形成n个比特，编码后的n个码元不但与当前输入的k个信息有关，仍与之前的L-1组的信息有关，其结构如下图1所示，图1来自Goldsmith的着作。
图中表示有L级信息比特，每次输入k比特信息，共有k*L个比特，每次输出n个比特信息，可以明显地看出该n个比特信息不仅与当前输入的k个比特信息有关，与之前L-1组信息比特也有关，所以卷积码是有记忆的编码，记忆深度为L。
注：此处与其他常见表示方法不同，此处将输入的比特做了缓存，所以记忆深度不一样，L看寄存器的个数确定。
2、卷积码表示方法
图2是输出码长n=2，记忆深度L为2，输入比特k=1的，（2,1,2）卷积码编码器。用该例说明卷积码的以下几种表示方法。
2.1 生成多项式
生成多项式使用K-1阶的多项式描述编码器的移位寄存器和模二加法器的连接状态。每个模二加法器的连接可表示成一个多项式。多项式的次数输入的阶次为0，其余按寄存器数的移位次数依次递增。如上图
输出1： g1(x) = 1 + x + x^2
输出2： g2(x) = 1 + x^2
以下是IEEE 802.11标准中的卷积码编码器，生成多项式分别为：
输出1： g1(x) = 1 + x^2 + x^3+ x^5 + x^6
输出2： g2(x) = 1 + x + x^2 +x^3 + x^6
2.2 状态图
状态图是关于系统状态变化的描述，它将由系统的输入，根据当前的系统状态，影响系统的输出。卷积码编码器存储的L-1段消息，既要因新的消息输入而改变，又要影响当前的编码输出，把卷积码编码器的移位寄存器中任一时刻所存储的信息称为卷积码编码器的一个状态。
（n,k,L）卷积码共有2^(k*(L-1))个状态，每次输入k比特只有2^k种状态变化，所以，每个状态只能转移到全部状态的某个子集(2^k个状态)中去，每个状态也只能由全部状态的某个子集（2^k个状态）转移而来。
（2,1,2）卷积码编码器包含2级移位寄存器和2个模2加法器。2级移位寄存器共有2^2=4种不同状态，定义为S0(00)、S1(01)、S2(10)和S3(11)四种状态。在每个时刻，输入的1个比特信息，当前状态将转为4种状态中的任何一种。
状态表类似查找表，原理即根据当前的输入和当前的状态，可以从表中查得输出信息。图4为卷积码的状态转移图，图中的状态转移表示“输入/输出1输出2”。
卷积编码码率是什么
为了支持高效、灵活的传输方式，信道编码技术需要考虑到各种不同的传输码率和调制方式，兼顾HARQ重传技术以及链路自适应技术。为此，信道编码技术常常使用打孔或者重复的方法，从编码比特流中提取预定长度比特序列，这个过程称为速率匹配。研究表明，均匀并且对称的打孔或者重复模式能够获得最优的速率匹配性能。均匀的打孔或者重复模式是指打孔或者重复的比特位置的分布是均匀的，以避免连续的比特位置上的比特被打孔或者重复。
TD-LTE中卷积码速率匹配的原理如图3-31所示。卷积编码器输出的第一、二和三校验比特流分别独立地交织后，被比特收集单元依次收集，也就是交织后的第一、二和三校验比特流依次输入到缓冲器中。每次传输时，比特选择单元从缓冲器头部的比特开始逐位读取，直至达到预定的比特数。当读取到缓冲器的尾部，仍然没有达到预定的比特数时，比特选择单元自动跳至缓冲器的头部继续读取。卷积码的这种基于缓冲器的速率匹配的过程，被称为循环缓冲器速率匹配（CBRM）。
TD-LTE采用的卷积编码器是码率为1/3的最优距离谱编码器，内嵌码率为1/2的最优距离谱编码器，这种编码编码方法能够保证获得优异的纠错性能。如图3-31所示，卷积码速率匹配时，比特收集单元在收集3个比特流时，3个比特流是依次被收集，这样能够保证卷积码通过速率匹配得到码率为1/2码字时，其距离谱仍然是最优的。
TD-LTE卷积码速率匹配采用的交织器是一个简单的行列交织器，如图3-32所示，交织器执行按行写入、内部列交织、按列读出的简单操作。行列交织器的列数固定为32，交织前，需要根据每个比特流的长度，计算得到行列交织器的行数，并根据需要在行列交织器的第一行的头部进行补零操作。在基于循环缓冲器进行速率匹配时，交织器的使用能够保证卷积码的打孔或者重复模式是均匀的，从而获得优异的卷积码速率匹配性能。另外，由于卷积码和Turbo码采用了一致的速率匹配方法，因此基站和终端能够采用一致的算法实现卷积码和Turbo码的速率匹配。
卷积编码1/2码率是什么
（1）对输入的数据进行卷积编码，编码速率为1/2，即每输入1个比特编码输出2个比特。
（2）将每次编码输出的2个比特量化为相应的数值，通过每一组数值计算出该组4个状态（s0，s1，s2，s3）的分支度量值，即BM值。
（3）进行加比选（ACS）运算，同时保存路径信息。首先在0时刻给4个状态（s0，s1，s2，s3）赋初始路径向量值（PM）：假如起始点为状态s0，则状态s0的初始路径向量值为PM0=100（该数值根据实际的情况来定，如回溯深度和分支度量值等，以便计算），状态s1、状态s2、状态s3的初始路径向量赋值为PM1=PM2=PM3=0。
（4）ACS过程。因为到达每一个状态有两条路径（如图3），例如到达状态s0（00）的两条路径分别是s0（00）和s1（01），从中选出到达s0路径度量值最大的一条路径作为幸存路径。如图2，若从0时刻到1时刻：BM0=-8，BM1=0，max{PM0+BM0，PM1+BM1}=PM0+BM0=92，所以1时刻到达状态s0的保留路径为0时刻从状态s0来的路径，从而更新1时刻s0的PM0=92；同时由于1时刻到达s0的是“0”路径，所以保存的该时刻s0的路径信息是0（若是“1”路径，则保存的该时刻s0的路径信息为1）。以此类推，可求出该时刻到达状态s1、s2、s3的幸存路径，存储该路径信息，更新其路径度量值PM。
（5）输出判决（OD），即回溯过程，就是根据回溯深度以及ACS过程中所保存的PM值和幸存路径信息进行相应的算法回溯出译码结果。