Loading...
墨滴

寻找薛定谔的猫

2021/11/26  阅读:60  主题:默认主题

卷积编码及维特比译码

卷积编码概括及汉明距离

卷积码是一种有记忆的差错控制编码,最早是由 P.Elias 于 1955 年提出的。卷积编码被用于物理层,目的是减少因不完美信道造成的误码。卷积码的生成方式是将待传输的信息序列通过线性有限状态移位寄存器。卷积码在通信系统中得到广泛应用。

卷积码的参数表示为 ,其中:

  • N:约束长度,即移位寄存器的级数(每级包含 k 个参数);
  • k:信息码位的数目,是卷积编码器的每级输入的比特数目;
  • n:k 位信息码对应编码后的输出的比特数,它与 Nk 个输入比特相关;
  • 编码速率:

卷积码的纠错能力随着 N 的增加而增大,同时差错率随着 N 的增加而成指数下降。 卷积码是一种有记忆系统,先将信息序列分割成长度为 k 的一个个分组,并将 k 位信息编成 n 个比特,但此 n 个比特不但与当前的 k 个信息有关,而且与前面 组的信息有关。编码中,互相有关联的码元数量为 位。如下图所示,为 卷积编码器的一般结构图。 在卷积码中,汉明距离贯穿维特比解码的始终。所谓的汉明距离两个长度相同的码序列,它们之间不同的位(bit)的个数。 例如:码字 A 为 ,码字 B 为 ;则它们不同的 bit 数为 3,汉明距离为 3。

卷积编码器示例

本文给出两个卷积码编码器的示例,分别为 卷积码编码器和 IEEE 802.11 标准中的卷积编码器。 其中, 卷积码编码器是输出码长 ,约束长度(移位寄存器的级数) ,输入比特数为 卷积编码器。 卷积码编码器示例如下图所示。 卷积码编码生成多项式如下所示,其中 分别为两个输出。

当前笔者所做的项目中,信号传输的所采用的编码方式为IEEE 802.11标准中的卷积编码器,即用 的卷积码编码器,是输出码长 ,约束长度(移位寄存器的级数) ,输入比特数为 卷积编码器。 卷积码编码器示例如下图所示。 卷积码编码生成多项式如下所示,其中 分别为两个输出。

对于 卷积码编码器,每个输入到编码器的数据比特产生两个编码符号 ,然后依次输出。编码符号 ,由发生器函数编码 产生;编码符号 ,由发生器函数 编码产生。卷积码编码器初始状态为全 状态,第一个数据进入编码器后开始输出。最后编码器需要恢复全零状态,所以要在输入数据添加额外 的尾序列,这一过程称为 “点亮” 编码器,其作用将会在维特比译码中介绍。

卷积编码描述——树状图

卷积编码的描述方式有树状图、状态图和网格图等。以例子(2,1,3)卷积编码器入手,详细介绍卷积编码的描述方式。 如下图所示,(2,1,3)卷积编码器状态示意图,圈起来的 用来表示状态编码器的当前状态。为了便于描述,定义状态编码器的下一个状态为 。次状态由输入信号决定,则可以看做次状态为 。为了便于分析,通过树状图绘画分析步骤,引出另外两种描述方式。

第一步: 假设寄存器中初始状态全为0,则当前状态为 ,输出信号也是 ,为了与输出信号区分,我们定义当前状态为 状态,即 当前所在即为树状图的第一层,此处可以画出树状图初始层如下图所示。 第二步: 分析树状图第二层。在初始状态,即a状态下,对于 卷积编码器具有两种输入,即输入为0或输入为1。如下图所示。 如上图所示,当输入信号为0时,则编码器的下一状态为 ,输出信号也是 ;当输入信号为1时,编码器的下一状态为 ,输出信号也是 ,为了便于描述,定义此时的下一状态为b,则有 。可以画出如下图所示的树状图第一层示意图。 注意,对于参数为 的卷积码编码树状图,满足如下特性:

  • 输入的比特数为k,则共有 种变化;
  • 每一种变化对应树的一个分叉,共有 个分叉;
  • 每一分叉上应该标上输出的序列,分叉的端点为下一状态;
  • 分支的排列顺序相同,比如上分支为输入0,下分支为输入1。

第三步: 如下图所示,在第一层中具有状态分别为 的两个分支。 分支的状态转移方式已完成分析,在此处只需要分析b状态的分支。在b状态下,对于 卷积编码器具有两种输入,即输入为 或输入为 。如下图所示。 如上图所示,当输入信号为0时,则编码器的下一状态为 , 输出信号是 ;当输入信号为1时,编码器的下一状态为 ,输出信号是 。为了便于描述,分别定义此时的 。可以画出如下图所示的树状图第二层示意图。 第四步: 如上图所示,在第二层中具有状态分别为 的四个分支。 分支的状态转移方式已完成分析,在此处只需要分析c和d状态的分支。 在 状态下,对于 卷积编码器具有两种输入,即输入为0或输入为1。如下图所示。 在d状态下,对于 卷积编码器具有两种输入,即输入为 或输入为 。如下图所示。 如上述两个图所示,在 状态下,当输入信号为 时,则编码器的下一状态为 , 输出信号是 ;当输入信号为 时,编码器的下一状态为 ,输出信号是 。在 状态下,当输入信号为0时,则编码器的下一状态为 , 输出信号是 ;当输入信号为1时,编码器的下一状态为 ,输出信号是 。可以画出如下图所示的树状图第三层示意图。 对于 卷积编码器,第四步之后,树状图则无需再继续画下去。因为卷积码状态满足如下特点:

  • 卷积码编码的状态是有限的
  • 参数为(n,k,N)的卷积码编码的状态数为2^k(N-1) ;
  • 参数为(2,1,3)的卷积码编码的状态数为4。
  • 只要状态及分支都出现了,则后边的分支及状态都是重复,没必要再继续了;
  • 参数为(2,1,3)的卷积码编码共有4个状态,树状图第二层便出现了所有的状态,因此画到树状图的第三层就可以了,此后便是重复。

卷积编码描述——状态图

我们知道,参数为 的卷积码编码的状态数为 ,则参数为 的卷积码编码的状态数为 。根据前边的分析方式,可以做出如下表所示的状态转移表。 根据上述状态转移表,可以画出如下状态转移图。

卷积编码描述——网格图

卷积编码的网格图表示方式与树状图表示方式相同,即每一层树状图中相同状态的节点可以合并到网格图中的每列相同的点;同时网格图的每一级可以对应树状图的每一级。

参照树状图或状态转换图,可以画出如下图所示的卷积编码网格图。其中右侧虚线方框内的状态都是重复状态。

注意,网格图具备以下两个优点:

  • 网格图可以表征编码的过程

    在网格图中,可以根据依次输入的码序列确定一条路径,然后将这条路径上的所有输出连接起来就是输出的目的码序列。

    例如对于输入的待编码序列[1 1 0 0]。假设起始状态为a,输入1时,状态由a跳为b;而后再输入1后,状态则由b跳转为d;此后依次输入0和0,则状态依次跳转到c和d。如下图所示,网格图清晰地标出编码跳转路径。

    将下图所示路径上的所有输出依次连接起来,可以得到输出编码为11101000。

  • 网格图在卷积码的维特比译码中具有非常重要的作用。

卷积编码的最小距离

为了方便理解最小距离,先定义N维矢量空间 中的一点 为一个N重矢量。假设全体码字(发码序列)所对应的点构成矢量空间 里的一个子集空间 。发码序列一定在这个子集 中,传输正确时的收码序列也一定在这个子集 中。

如下图所示,为N维矢量空间 示意图,其中红色和灰色的圆圈表示一个个 重矢量 ,其中红色圆圈表示子集空间 ,所有的发码序列均在这个子集中。当收码出现错误时,接收的N重矢量有两种可能:

  • 一种情况,变得对应到子集空间 之外某一点,即下图所示的灰色圆圈。该种情况容易发现对应点不在子集上,从而判断出差错的存在。
  • 另一种情况,是仍然对应到子集空间 ,但是却对应到该子集的另一点上。例如,如下图所示,正确收码本应该是 ,而实际收码却为 。该种情况无法判断是传输发生错误,还是原本发送的就是另一个码字。

码集 各个码字间的距离是不一样的,如上图所示,码字 之间的码距分别为 。正确收码本应该是 。但是,如果实际接收的码的位置是由 点的位置向 点错1,此时收码点距离 点为1,距离 点为 ,因此按最大似然译码仍然可以译为 ,从而差错可以纠正。如果实际接收的码的位置是由 点的位置向 点错2,此时收码点距离 点为 ,距离 点为 ,此时若检错尚能有效发现错码,但若纠错就会译码输出 ,而产生一个错误输出。再进一步,如果实际接收的码的位置是由 点的位置向 点错 ,此时收码点就是 ,译码系统会认为接收端准确无误地接收到了 ,绝不会认为收到的 是发送 而错3位所导致的,这种情况根本检查不出任何差错。

以上讨论可知,当码距为3时,纠错能力为1,检错能力为2。可见,码距之间,距离越大,纠错和检错能力越强。但是在子集空间 中,往往含有多个码点,如上图红色圆圈所示。正如木桶的最短边所决定木桶的容量一样,子集空间 中码点之间最小距离决定卷积编码的特性,这个最短距离我们称为最小距离 注意,卷积码最小距的特点包含以下几个方面:

  • 卷积码的最小距为非零码字的最小码重;
  • 约束长度隐含某种独立性,即可以考虑分析 个信息比特编码后输出的码序列,即 个编码输出序列。
  • 最小距离分析的是非零码字,即为离开全零状态,经过约束长度个输入后的一串编码输出。

鉴于以上说明,采用树状图分析卷积码的最小码距最为方便。如下图所示,采用 卷积编码为例进行分析。该示例,因为要离开全零状态,所以树状图的上半部分不用考虑;同时约束长度只有 ,只需要考虑 级即可。 由上图所示,共有如下4种码距可能,可知最小码距为3。

卷积编码的自由距

注意,卷积码自由距的特点包含以下几个方面:

  • 卷积码不分组,自由距作为卷积码纠错性能的度量更合理;
  • 自由距的值不小于最小距,即
  • 编码后的非零序列应包含尽可能多的零,从而保证与全零序列之间具有最小的汉明距;
  • 自由距的求解:从全零出发,经历非零状态,又重新回到全零状态,这个过程中输出的1的最少个数即为自由距。

卷积码自由距离 的计算方式一般有三种方法:第一种是采用采用网格图进行推导,这种推到方式仅适用于简单的卷积编码;第二种是采用状态图法进行分析,这种可以分析较为复杂的卷积编码,也最具理论价值;第三种是最实用的一种方式,即采用计算机编程的方式进行搜索。 如上图所示,采用 卷积编码状态图为例进行分析。由图分析,单行程路径共有以下图所示两条,即得自由距

卷积码译码基础

如下图所示,为卷积编码/解码的信道模型,卷积译码器必须通过接收序列 来产生信息序列 的一个估计序列 。如果二者不同,则表明编码/传输/译码过程出现差错。

在关于卷积译码方面,常用的卷积译码算法是维特比译码算法。维特比算法实质上是卷积码的最大似然译码。 最大似然译码是通过求码字之间的相似度,然后选择路径量度最高的那个序列作为序列码的估计值序列。为了详细解释最大似然译码,先做以下定义: 定义卷积编码器输出序列 的长度为 ,经过无记忆信道传输后比特错误概率为 ,其中发生错误的比特数为 。可以得到似然度计算公式。 为了能直观分析,我们对上式进行简化运算,对两边求对数可以得到如下式子。 上式中, 均为正数,由编码长度及信道所决定。若要使上式最大化,则只需要 最小。 最小表示误码数量最低,即 的汉明距最小。所以,最大似然译码就是寻求和 序列之间具有最小汉明距离的X序列。

对于编码过程而言,我们可以根据输入的待编码的二进制序列来唯一的确定网格图上的一条路径;那么在译码的过程中,如果接收到接收码字之后,能在网格图上正确的得到路径编码时的路径,就能完成解码。鉴于此,我们还需引入两个问题:

如何在网格上得到译码路径;
如何解决信道引入的差错。

针对以上两个问题,我们先假设信号经过一个理想信道,在理想信道中,信号的传输过程不出现差错。另外假设数据接收端接收到的数据序列为 。可以有以下译码流程。

在信元时刻 ,从起始状态a开始有两种状态转移,各自对应的编码序列如下图所示。由于接收到的码元是11,因此可以判定下一状态为 ,该信元时刻对应的信息位为 在信元时刻 ,状态b有两种状态转移,各自对应的编码序列如下图所示。由于接收到的码元是 ,因此可以判定下一状态为 ,因此该信元时刻对应的信息位为 在信元时刻 ,状态 有两种状态转移,各自对应的编码序列如下图所示。由于接收到的码元是 ,因此可以判定下一状态为 ,因此该信元时刻对应的信息位为 在信元时刻 ,状态 有两种状态转移,各自对应的编码序列如下图所示。由于接收到的码元是 ,因此可以判定下一状态为 ,因此该信元时刻对应的信息位为 根据以上分析,接收端接收到的数据序列为 ,则译码路径为 ,输出的译码信号为 。 可见,整个译码的过程并不复杂,就是依次将每个接收码字在网格图中进行比较和选取。但是在实际的信道中,接收码字可能并不与当前状态的两条路径对应的编码码字相同。假设接收端接收到的数据序列为 ,则在信元时刻 无法选择正确的路径,如下图所示。 这时候,我们就需要引入对错误的度量,最终找到最小的错误的度量值所对应的路径,这条路径就是当前得出的最大似然路径。

维特比译码

维特比译码是将接收到的序列和所有可能的发送序列作比较,选择其中汉明距离最小的序列当作是现在的发送序列的一种算法。

译码器从某个状态出发,每次向右延伸一个分支,并与接收数字相应分支进行比较,计算他们之间的距离,然后将计算所得距离加到延伸路径的积累距离值中。对每个状态的各条路径的累积值进行比较,保留距离值最小的一条路径。当有两条以上最小路径时,可任取其中一条。

在译码的过程中,每个信元时间内,每个状态需要完成以下操作:

  • 译码状态从全零开始;
  • 将分支度量与上一时刻状态的路径度量相加,保留幸存路径,淘汰其他路径;
  • 所有路径合并的部分即可输出译码结果,其他部分继续译码。 接下来以 卷积码为例子说明。示例的信息序列 、发送序列 和接收序列 分别如下所示。 卷积码采用维特比译码算法的译码过程。此处所说的汉明距均为各个分支路径与输入序列的汉明距离。
  • 在初始时刻 ,状态从 开始,延伸出两条路径,此时输入的序列为 。如下图所示。路径 的汉明距为 ;路径 的汉明距为
  • 在初始时刻 ,分别从状态 和状态 延伸出两条路径,此时输入的序列为 。如下图所示。此时,路径 的汉明距为 ;路径 的汉明距为 ;路径 的汉明距为 ;路径 的汉明距为
  • 在初始时刻 ,分别从状态 、状态 、状态 和状态 延伸出两条路径,此时输入的序列为 。如下图所示。此时,路径 的汉明距为 ;路径 的汉明距为 ;路径 的汉明距为 ;路径 的汉明距为 ;路径 的汉明距为 ;路径 的汉明距为 ;路径 的汉明距为 ;路径 的汉明距为
  • 此时已经遍历了所有状态,我们在此处开始向前回溯。此处共有 个路径,比较有路径 与输入的接收序列的汉明距离最小。此时我们可以确定第1个码元的值,且该值为 。下图所示。
  • 在时刻 ,分别从状态 、状态 、状态 和状态 延伸出两条路径,此时输入的序列为 。如下图所示。此时,路径 的汉明距为 ;路径 的汉明距为 ;路径 的汉明距为 ;路径 的汉明距为 ;路径 的汉明距为 ;路径 的汉明距为 ;路径 的汉明距为 ;路径 的汉明距为 比较有路径 和路径 与输入的接收序列的汉明距离最小,此处可以随机选择一个路径,假设选择的路径为 。此时我们可以确定第 个码元的值,且该值为 。下图所示。
  • 在初始时刻S_4,分别从状态 、状态 、状态 和状态 延伸出两条路径,此时输入的序列为 。此时,路径 的汉明距为 ;路径 的汉明距为 ;路径 的汉明距为 ;路径 的汉明距为 ;路径 的汉明距为 ;路径 的汉明距为 ;路径 的汉明距为 ;路径abcbdd的汉明距为

比较可以得出:路径 与输入的接收序列的汉明距离最小。此时我们可以确定第3个码元的值,且该值为0。下图所示。

  • 重复以上步骤,可以分别求出第 、第 和第 个码元,如下图所示。分别译得第 、第 和第 个码元分别为 对于第7和第8个码字,可以通过直接比较各个路径的汉明距离确定路径,最终确定对应的码字。此处剩下四条路径,从上到下分别是黑色路径、黄色路径、绿色路径和红色路径,他们的汉明距离分别为4、4、2和1。可以确定红色路径的汉明距离最小。则第7和第8两个码字分别为1和1。

值得注意的是,上述判定方式所采用的回溯时延都小于前六个码的回溯时延,这导致译码的准确度不高。为了克服这个现象,在发送完待发送数据后,需要持续发送一定的0码字。这便合理解释了在工程中需要对编辑器进行 “点亮”操作(详见“卷积编码器示例”一节)。

在进行译码时,回溯时延越长,对译码的准确性越有利,但是却对通信的事实性不利。一般设定回溯延时D是卷积码限制长度N的5~10倍,满足表达式

同时在进行译码时,可以根据汉明距离的大小,减少某些路径,以减少计算量。例如下图,指向时刻 四个状态路径,分别去掉汉明距较大的那一条。即去掉路径 、路径 、路径 和路径 ,可以得到如下图所示的路径分支。

若喜欢DSP的matlab实现相关话题,还请关注本人公众号

寻找薛定谔的猫

2021/11/26  阅读:60  主题:默认主题

作者介绍

寻找薛定谔的猫