7.3 卷积码在线视频

下面我们看一下

卷积码的一些基本定义

我们稍微回顾一下

刚才我们已经提到过

卷积码

可以用这三个参数来表示

有n k m

卷积码是一种有机的编码

它的编码器

我们可以

看作是一个有限状态机

这个K表示的是

单个时钟

节拍输入编码器的比特数目

n表示的是

单个时钟节拍编码器输出的

比特数目 M就表示

这个编码器所记忆的

阶时钟节拍的数目

我们以这样的一张图

来做个示例

给大家看一下卷积码

它的编码器整体结构

我们看卷积码的编码器的中心

部分其实就是一个有限状态

它也要记忆一些时钟节拍

其实主要记忆的是

历史的一些数 数据

那么输入左端

这实际上就

一般而言

就可以有K比特

同时并行的输入

那么同一个时钟节拍

会有N比特并行的输出

这就是个一般的

NKM卷积码编码器的结构

那么它的编码码率

当然也可以用N分之K当然也是

小于一来表示

我们如何来描述卷积码呢

因为卷积码也有编码

也有译码

所以我们把它划分为

描述的方法

划分为两大类

一类是解析法

主要用于描述卷积码的编码

另外一类是图形法

主要用于描述码的译码

那么编码方法当中

解析法方法里面

主要包含有三类方法

就是所谓的定义法

也就是离散卷积法

生成矩阵法

还有码多项式方法

用这三种方法

来描述卷积码的编码

对于图形法而言

也有三种工具

基本估计

我们用状态图来表示卷积码

那么进一步我们引入时序概念

就把状态图推广到树图

那么再进一步

我们把树图进行压缩

就变成了格图

我们用状态图

这个树图还有格图

描述卷积码的译码

下面我们通过事例

来给大家分析

我们先看编码

大家看胶片上给的事例

这就是一个212卷积码

我们观察这个例子中间

这两个方框

这就是两个寄存器

每个寄存器

一个是时钟节拍

可以记一个比特

我们看计算器结构的左端

就是一路输入

就一个时钟阶拍

只输入一比特

所以就指的是

212当中的1

就K=1

对吧

我们再看右侧

右侧它有两个输出

两路并行的输出

也就是 N=2

就212里面的2

那么

212里面

就第三个是M M=2

是什么意思

我们看有两个寄存器

每个寄存器可以记忆

一拍时钟两个寄存器

可以记忆两拍时钟

所以它记忆长度是二

那么它的这样的结构

我们可以看作是一个

离散

线性

时不变系统

线性时不变系统

我们缩写就LTI

这样的离散线性时不变系统

它不是一个是两个

大家注意

输入和上支路

这之间是一个

离散线性时不变系统

输入和下支路

也构成一个离散线性时不变系统

所以这实际上是两个系统

这两个系统它共享寄存器

所以叠加到一起去

这样构成了卷积码的编码器

对于离散线性实不变系统

我们知道

描述这个系统

可以用冲激响应

用冲激响应来描述

那么它的编码器的输出的编码

序列

就可以看作是输入的信息序列

与系统冲激相应的离散卷积

这也就是我们引出来的

卷积码的第一种描述方法

我们用它的定义来描述

因为卷积码的编码

就可以看作是一个离散卷积的

过程

那么下面我们举例来分析

假设说我输入的信息序列

是一个离散序列

就是有序列

那么编码之后的序列

就是输出响应序列

有两个子路

就第一只落是C1子序列

第二支路 C2子序列

我们把这两路编码序列做一个

二两路变一路的并串变换

那么交织到一起去

就变成了单路输出编码的序列

下面我们通过一个例子

来给大家说明

刚才我们举的

212卷积码的结构

这样的一个离散线性识别系统

上下两个之路的冲激效应

怎么求呢

非常简单的方法

应用

我们在信号系统学过的基本知识

假如我输入的是一个离散冲激

响应序列

那么输出的就应当是这个系统的

冲激响应了

我们离散冲激效应

序列δ

我们可以把它定义为就是1

后面全是0000

全是0

送到了上面的系统当中

大家看这个是一个摩尔加操作

对吧

一般而言

我们都假定

卷积码编码器的初始状态是全0

状态

也就是说

这两个寄存器里寄存的全是0

初始要做一下寄存器的清零

或者默认为是全零值

你输入1000000

这是一个冲激响应序列

我们可以算出来

上支路系统的冲激响应

其实应当是111

那么下支路的冲激响应

实际上应当是1

0 1

如果我们做熟了的话

其实不必要这样的逐个去算

直接从编码器的结构上

能看出来它的冲激效应

怎么看这样做

只要我有抽头输出

这两个寄存器

实际上有三个抽头对吧

最左面有个抽头

中间有个抽头

右面有个抽头

抽出头来

那么冲激响应当中

要如果没有抽出头了

冲激响应当中就是0

上支路这个系统

它抽了三个头

所以它的冲击响应

就是111

下支路

这个系统

它其实只抽两个头

就左边这个是1

中间这块没有抽

右面是1

所以它的冲击效应就是101

我们得到这两个冲激响应了

下面我们做卷积操作

假设说我们输入的是一个有序列

那么上支路的结果

就应当是把输入的

信息序列U序列

与冲激响应

g1做卷积

那么下支的编码子序列

就应当是输入的信息序列

以第二支路的冲激响应序列

g2做离散卷积

卷积之后

我们再做一个并串变换

就得到最终的编码序列了

大家在信号与系统当中

这门课里面

学习最痛苦的一件事情

就是手工做卷积

尤其离散卷积非常复杂

所以虽然我们

卷积码的得名

是来自于这种离散卷积的

但是我们描述编码器

一般都不采用这种

手工做离散

卷积的方法描述

这只是一个定义

我们可以引入一些

更简单的方法来表示

卷积码的编码

稍微简化一点

我们可以把这种卷积的操作

变成矩阵向量的乘法运算

矩阵重新运算

我们把这输入的信息序列

U0 U1

U2 U3

就我举个例子

就是5比特U0 U1 U2

U3 U4

5比特

那么我们可以把

刚才给的212卷积码的

两个冲激响应序列

把它组成一个

等效的生成矩阵

大家注意

我们这儿加一个定语

必须是等效的生成矩阵

具体怎么组织

很简单

把上支路的冲激响应g1

111

与下支路的冲激响应

g2是101

兼插就是上下两个支路

交错组合起来

比如说

这样组合11组合起来

10组合起来

11组合起来

大家看就变成了下面这种结果

111

1011

对吧

然后生成矩阵

它是一个移位带状矩阵

也就是说

第一行是111011

第二行也是

只不过相对于第一行要右移2

比特

以此类推

这构成的是一个带状矩阵

我们把输入的信息序列

与这样的一个带状矩阵相乘

就得到了编码输出了

所以矩阵向量相乘

比纯粹手工做离散卷积

要更简单一点

所以这就是所谓的用生成矩阵法

来描述卷积码的编码

我需要解释一下的是

卷积码本身是非分组码

严格意义上讲

是不能写出它的生成矩阵的

我们这只是一种等效的方法

那么原因在于

我输入的信息序列

长度是不确定的

它不像线性分组码

73收入必然是3比特

比如说15 11

收入必然是11比特

而对于卷积码而言

这输入的比特长度可长可短

短的话1比特2比特

长的话1000比特10000比特

因为它没有分组的概念

所以这个地方的生成矩阵

实际上是一种等效的结构

也就是说生成矩阵的维度啊

就带状矩阵的长度是可变化的

所以这只能是等效

不过用这种等效

已经极大的简化了

我们做离散卷积的过程

它的计算就比较方便一点

我们还可以进一步简化

所谓的采用码多项式的方法

来进行的卷积码的

这个编码描述

也就是说

我们把这个信息序列

还有生成卷积码的编码器的

两个支路的系统冲激响应

我们都可以把它映射为是多项式

那么信息序列

我们把他映射为是UX也变成了

信息

多项式

那么这两个冲激响应

我们把他映射为g1x g2x

变成两个是

生成多项式

有了信息多项式

和生成多项式

那么编码其实就是信息多项式

与生成多项式的相乘

就码多项式乘法运算

那么对于第一个支路的编码而言

它的码多项式C1x 其实就是信息

多项式Ux与生成多项式g1x

相乘

那么多样

相乘很容易做

大家可以自己做

公式见图

公式见图

公式见图

公式见图

请大家注意

码多项式乘法运算的时候

它是在 gf2域上

也就是在01集合

这样上面的一种线性运算

摩尔加摩尔乘的线性运算

换句话讲

如果某一个项

比如说

比如说我们这儿举了个例子

公式见图

公式见图

公式见图

等于是相互抵消0

有基数个项

那么就会存在

偶数各项就相互抵消了

它和摩尔加运算是类似的

所以经过整理

我们就能够得到第一个植入的

编码的码多项式

类似的也能得到

第二个植入的编码的码多项式

所以就能够得到最终

编码比特序列

所以卷积码

它最简单的编码描述

我们可以采用的码多项式的方法

来描述

好

我们再举一个例子

这个例子稍微复杂一些

这个例子是一个321

卷积码

大家观察

编码器的结构

它的输入

是由并行的两比特输入的

所以K就应当等于2

它的输出大家注意

实际上是有三个比特的

三个支路

所以N就应当等于个三

所以它的编码码率

实际上应当是2/3

那么它的记忆长度M 虽然大家

观察编码器是有两个寄存器

但是它的记忆长度并不是二

这不是322编码器

M实际上记忆长度是1

是321

为什么你仔细想一想就能明白

因为输入的这两个比特

是并行同时输入的

这两个寄存器

它其实记忆的是同一个时钟节拍

虽然它记忆了两个比特

但实际上是同一个时钟节拍

送进来的

所以它的记忆长度只能是一

它不是二

所以这就是一个

所以基本的321卷积码的

编码器的结构

好

那么它的码多项式

还有生成矩阵的方法

我们不再列举了

请大家自己仔细看一下书上的

介绍

下面我们重点来给大家讲

图形法的描述

我们还以刚才的

212卷积码的为例

212卷积码

我们刚才一开始就给大家讲过

卷积码

它还可以看做是有限状态机

因为像212卷积码

它有两个寄存器

记载了两拍时钟 确切的讲

对于特例而言

它记忆了两个比特

那么寄存了两个比特

你可以想一下

相当于这两个比特

比特

A B. 两比特

2比特一共有多少种组合呢

显然有00

01

10

11

有4种组合

对不对

因此我们可以用这两比特的

记忆的

两比特的组合

来得到卷积码的4种状态

叫212卷积码

实际上有4种状态

一般意义上

卷积码

有多少个状态呢

它应当有二的

KM次方个状态

而我们现在觉得特例

212卷积码

K=1

M=2

所以就是2的2次方

实际上有4种状态

我们可以根据212卷积码

它的输入比特输出比特之间的

映射关系

画出来状态

转移和输入输出比特之间的

一一对应的关系

那么这种关系对应关系图

就是所谓的状态图

我们可以给大家看一下

212卷机码的状态图的

实意ABCD4个状态

分别对应的是00

10

01

11 4个状态

那么这4个状态之间

是怎么对应的

大家注意这状态之间可以转移

它有箭头关系

就是状态转移的关系

或者状态转移分支

在这个状态转移分支上

有两种

比特组合

在括号里面的

实际上是输入的信息比特

因为我们是212卷积码

输入每拍时钟

输入1比特 一个比特

所以括号里面

比特的取值两种

0

1

我们再看转移分支的外面

括号外面也是两比特

这两个比特对应的是输出的编码

比特

那么212卷积码编码

比特变通一拍时钟

编出两比特

这两笔它一共有4种组合

00 01 10 11

一共4种组合

那么这种状态转移关系

它就表征了

当前时刻

卷积码的编码器是什么状态

下一个时刻

如果我输入信息为取值给定

我们就能够得到它的输出编码

比特的组合

同时我们也知道

卷积码编码器从当前的状态

转移到下一个时刻的另外的状态

比如我们这儿举个例子

我们把刚才212

卷积码的编码器画到这儿

我们从这个图上来分析一下

状态转移之间的关系

我们看这是212卷积码的

编码器的结构

假设说当前的时刻

这两个寄存器存的是

初始态是00

我们输入的信息比特是1

对吧

我们看一下上支路

这三因为是抽头抽出来

就是三个比特100摩尔加

那么上支路编出来是1

下支路的话就应该是1

但中间这个抽头没有抽出来

只是1和0摩尔加

那么输出的结果也是1

同时我们寄存器进行右移

对吧

把左面的寄存器的0

要移位到右面寄存器

右面0移出来

就移到了上下的支路上去了

那么左面寄存器里面

就把1移进来了

所以显然现在的这个状态

你就转移到了10状态

也就是我们看这个状态图上

就从00状态

转移到10状态

对不对

那么它输入的信息

比特括弧里面是1

那么编出来的编码

比特是11

这就是212卷积码的状态

图上的一个状态

转移的分支

就这么确定下来的

依次类推

所有的状态转移分

你都能确定

有两个特例

我们需要说明一下

大家观察全0状态

00状态

这00状态

这儿有一个自环

对吧

为什么

因为如果我输入信息

比特是0

初始状态是00

因为上下摩尔加所有的零摩尔加

还是零

所以编码编出来

还是00下一个状态还在00上

所以这个自环节表示这样的含义

就前一个状态是00

那么输入信息比特是00

那后一个状态还是00

类似的如果说

初始状态迁移状态是11

那么你输入一个1

它下一个状态还是1

所以11这儿也有个置换

那么这就构成了

整个212卷积码的

状态转移图了

一般来讲有线状态机

它的状态转移图

和我们卷积码的编码器

是一一对应的

这是另外一种描述工具

但是描述的是同一个对象

它是用不同的工具来描述的

在这个状态图上有三个关系

它们是一一对应的

第一个关系

就是状态

第二个

输入的比特

第三个关系

是输出的比特

请大家注意这三个关系

并不是相互独立的

因为他们有约束

有相互依赖

我只要确定

这三者当中的任意两者

那么就可以唯一决定的第三个量

举个例子讲

如果我们给定了状态和输入

我们就唯一的确定的输出

或者我们给定了状态和输出

就可以反推输入

或者我们给定了输入输出

那就能反推状态

因为它们三者之间

是有约束关系的

所有的卷积码的编码过程

都可以用状态图来一一对应

描述

这两者等价

你可以通过

编码器推导出来的状态图

反之我们通过状态图

也可以

反推出来编码器的结构

不过这个状态图

它还不能够完全反映

卷积码编码的全部信息

它的编码约束关系

都已经反映了

可是这个卷积码

它是个时序

结构

它有时间的概念

但是状态图

它们只有状态转移的关系

它没有这种时间的

关系在里面

所以我们可以考虑

把状态图

做一点扩展

把时序结构引进来

这就引出来了第二种图

也就是所谓的树图描述

我们以一个事例来给大家介绍

就212卷积码的事例

大家看这就是个树图

对于212卷积码而言

它是一个2察叉树

我们的初始状态

就是从全0状态开始

从这儿开始

这是树根根节点

然后我们有两个分叉

因为它有二叉是两个支路

上支路

我们对应的就是比特0

下支路就对应的比特1

二叉树是怎么来的呢

它是由信息比特来决定的

你输入信息

比特是0

我们就走上支路

输入信息

比特是1

我们就走下支路

就两个分支

那么根据状态图的约束

全零状态如果输入是0

它就转移到00

输入是1那就转移到

10

也就是转移到A状态

转移的A或者B 那么接着如果说

下一拍时钟

又输入的是0

那么全0还转移到全0

如果输入的是1

那么 A就转移到B

类似的B状态

如果输入的是0

那就转移到C 输入是1

就转移到D

大家看这就是分叉

随着横坐标时钟

随着时钟节拍的增长

每过一时钟节拍

那么这个数上的分差就多一倍

每过一个时钟节拍多一倍

这实际上是一个二叉的

满树

对吧

我们从树根开始

到某一个叶节点

这不会走过一个

由分支构成一条路径

路径上的编码

比特的组合

其实对应的就是某一个

卷积码编码的序列

比如刚才我们举的这个例子是

什么

1输入的信息

比特是10111

大家可以直接从树根

开始沿着树图

就能读出来它编码的序列

因为首比特是1

所以走下支路

第二比特都是0走的是上支路

第三比特是1 下支路

第四比特是1下支路

第五比特也是1下支路

后面有一些0的比特这也是

干什么

是结尾

比特通过0比特直接推

就能够把卷积码的

编码器又推

相当于是把它的结尾

就推回全0状态

这样的话

方便下一帧开始进行编码

所以这就是数图的结构

大家观察这个数字结构

它的横轴方向

就引入了时钟

或者时序概念

所以在树图上

从树根开始到叶节点

所有的路径就涵盖了

所有的卷积码编码

可以编码的合法序列了

原则上讲

我们在数图上

穷举所有的序列

就能够来进行译码了

不过人们发现说

树的话

只是一个形式化的工具

其实它的

应用上有限度的

或者说

是比较困难的

因为这是一个

二叉满树

你稍微数据真大一点

比如说

我们正常

等于100

那么按照212卷积码的结果来

看

它的数的总数有多少

就是路径或者序列总长有多少呢

就显然应当是2的100次方

这是天文数字

我们没有办法在工程上实现

所以

这个树图

它只是个理论分析的工具

那么为了工程上更方便的实现

那么有没有可能呢

把

树上面的这些分支

做一些压缩

我们仔细观察这个数的结构

看一看就能发现

这个树上面

其实是存在大量的冗余的

请大家看呢

我们以树根

为参考点

分解一下

把这个数分成上半子数

和下半子数观察

其实上半和下半下来

ABCD ABCD

一模一样

对吧

当然前面有一点差异性

ABCD

ABCD.是不一样的

但是从第三排始终开始

就是个重复了

所以按照这个结构

我们想办法

能不能把这个数上下对折

对折对折

把冗余的这些状态

能给

只有在每一个时钟节拍

把它只用一次

只表示一次

这样做

我们就得到了

在译码当中

最常用的一种工具

我们称它为是格图

英文我们叫做是

Trellis

Trellis的含义叫篱笆

因为格图结构就像

扎羊圈用的篱笆

所以我们就叫篱笆图

或者是格图

格图的结构

我们先给大家看个示意

它既包含了

树图的所有的

信息

有时序有状态

同时它又去掉了树图当中的冗余

胶片上给的示意

就是212卷积码的格图

大家观察横坐标

这是时序

对吧

时钟节拍

纵坐标是状态关系

我们212卷积码有4个状态

那么有4个状态

大家看就是

ABCD 每一拍

时钟大家观察

这不就是有4个状态

转移到下一拍

始终又有4个状态

对吧

这之间的转移关系

就是由状态图来约束的

仔细观察

我们这样来表示

虚线

就表示

信息位输入的信息位是比特1

实线

就表示输入的信息位是

0

那么在转移分支上的

这两个比特

编码比特

我们输出的编码比特

所以这个格图上

其实已经蕴含了

数图上的所有信息了

我们从全0状态出发

就从左侧全0状态出发

沿着格图上

任意走出来的一一个路径

就表示

卷积码的某一个编码序列

你把所有的路径都走一遍

就构成了卷积码

可以表示的所有核发码字

这就是格图的概念

我们有了这三个基本的图形工具

了

下面我们围绕格图

来给大家简单的解释一下

卷积码的译码

卷积码

现在最常用的译码准则

叫做是维特比算法

这个维度比算法

它是卷积码的一种最优译码算法

最优首先我们先解释一下

它的最优性

译码的过程

广义上来理解

也是一种估计

那么在信号检测与估计理论当中

译码的准则

我们一般来说

最佳的准则

或者说

是最优的判定原则

应当是用差错概率最小化

就平均误码率最小化政策

平均误码率最小

我们可以稍微利用概率论的知识

做一点推导

平均误码率最小

我们把这个平均差错做一个展开

什么叫平均差错呢

就是这样的一个概率

假设说我们接触到的码字是Y

如果我收到Y以后

产生了错误

这显然是一个条件差错

对吧

是一种条件差错

我们穷举了所有的接收信号序列

的组合

就PY就相当于是一种

信号序列的概率分布

那么对它进行平均

这不就是一个平均差错概率吗

所以让这个平均差错概率最小

其实我们展开平均差错概率定义

实际上就是条件差错概率的加权

平均

而这个条件差错概率

我们还可以

把它进一步展开来写

那么所谓的条件

差错概率就收到Y

产生了错误

其实等价的来看

不就应当是收到Y

我们译出来的结果

上面加个尖号

好

叫我们称为是冒号的 C冒

你估计出来

或者译马的序列

不等于发送的序列

这不就出现错误了吗

这就是条件差错概率

是吧

我们还可以把差错条件

差错概率再进一步展开

什么叫错误

错误不就是

1减掉

正确不就是错误

所以

这个条件差错概率

我们可以写成是一

减掉

正确

当然就是我估计的结果

等于争执估计的结果等于争执

我们看后面这一项

这一项

是收到信号以后

我们在译

并且译对

我们把前面估计就去掉了

写成这样的概念

叫收到y以后

我们译出来是C 这个概率

我们一般称为

后验概率

所谓后验大家看

这是一个条件概率

它是先收

收到Y以后

后进行判决或者估计

所以我们就称它为是后验概率

我们称它为是后验概率的

英文实际上应该是拉丁文

我们叫的是

如图

如图

与之相对应的还有一个概率

我们也经常用

这个概率也是个条件

概率

我们把它写为是

假定

发送的序列是C 然后给定发送

序列C的条件下

我们收到Y那么这个概率是

我先讲给了一个假设

看接收信号

在这种假设条件下的概率

这就是给定假设条件下的

概率

我们称这个概率叫做是

似然概率

似然概率

因为即一般我们叫做是

如图

需要考虑的问题

所以我们称它为叫似然概率

这两个概率的定义

请大家别搞混了

后验概率

条件上是

接收信号就先收

然后估计或者判断

那么似然概率是先给了一个

假设发送的是C然后结果收到

信号Y所以一个是先收后验

一个是先给定估计

然后看接收

所以这两个概率

一个叫后验概率

一个叫似然概率

我们给出来的后验概率

和似然概率的

定义了

前面按照前面的分析

我们知道平均差错概率最小

就应当等于

条件差错概率的加权平均最小

而条件差错概率

我们知道

其实应当是一

减掉的正确概率

你让条件差错概率最小

因为它是一减

那不就应当相当于是

让条件差错概率最小

就等价于让

条件正确

概率最大

对不对

条件正确概率就是后验概率

所以平均差错概率

最小

等价于后验概率最大

那么后验概率最大

我们一般成为是最大后验概率

准则

MAP M的意思

如图

如图

所以我们缩写叫MAP

叫MAP准则

所以这两者是

在所有的情况下

都是等价的

就平均差错概率最小

这样的最优准则

就等于最大后验概率准则

所以最大后验概率准则

是一般意义上的最佳译码准则

然后另外我们再看

后验概率实际上

似然概率之间是有关系的

我们刚才刚给了后验

概率是这个样子的

我们用BS公式

可以把它展开

分母上应该是PY分子上联合

概率

联合概率我们可以写成PC

乘上C条件项Y对吧

因为PY它是一个公共项

我们就不考虑了
因为PY它是一个公共项

我们就不考虑了

所以可以看到后验概率

其实应当正比于

PC

再乘以

似然概率就

C条件下Y对吧

你现在让后验概率最大

其实正比于似然概率与PC

PC是什么东西呢

我们因为PC是码字的概率

它与信源的统计分布有关

所以一般我们称

PC叫做先验概率

所以实际上后验概率最大

就等价于是先验概率

以似然概率的乘积最大

而一般情况下呢我们假设

我们不考虑信源统计的情况下

我们假设先验概率

码字都是等概出现的

在等概的条件下

那么也就是说是先验

等概的条件下

就最大后验概率准则

就应当等价于最大似然准则

最大似然准则

我们一般缩写为叫ML

如图

这个等价

请大家注意是有条件的

只有在先验等价的条件下

最大后验准则

就等价于最大似然译码准则

好

我们接着不加照明

接着直接给大家再来分析

最大似然准则

在先验等概的条件下

是最优准则了

那么我们针对实际的信道

最大似然准则怎么用呢

它有两种代表性的信道事例

如果说

我们前面研究的BSC信道二元

对称信道

在二元对称信道当中

你让似然概率最大化

其实就等价于让

汉明距离最小化

我们可以把它等价为是

最小

距离当然是汉明距离译码准则

如果说你要是在 AWGN信道

当中

白噪声信道当中

那么译码准则

最大的Sin码准则

等价于欧式距离

译码准则就是让欧式距离

最小化的译码准则

好

总而言之

我们看这个逻辑链条

相当于是推了有这么4步 最初始

的条件

就应当是让平均差错概率最小

那么平均差错概率最小

我们可以等价为是

后验概率最大

也就MAP最大后验概率准则

这是没有什么条件的

完全等价的

在先验等待的条件下

那么最大后验译码准则

就能够等价为最大似然译码准则

然后在 BSC信道条件当中

最大似然译码准则

就等价于最小汉明距离译码准则

如果是AWGN信道当中

那么最大似然准则

等价为是最小化

欧式距离译码准则

总而言之

不管是BAC信道

还是AWGN信道

其实译码就是要找距离

对吧

要不然是汉明距离

要不然是欧式距离

所以举个例子讲

比如说212卷积码

那么我们怎么做最大似然译码

其实就是把收到的序列

与格图上面的所有的序列

两两之间

分别去算他们的汉明距离

然后哪一个格图上

哪一个序列与接收到的

信号序列之间的汉明距离最小

序列

最大似然译码的结果

实际上就是两两比较

看

哪个距离近

我就以为谁

这就是最大似然译码的过程

前面我们已经有了一点准备了

下面我们在讲维特比算法之前

给大家做一点这种分析

最大似然译码

是不可能实现的

在中等码长

或者实用化的情况下

没有办法实现

为什么呢

因为最大似然译码

是一种指数复杂度的算法

它的搜索量是指数增长的

举个例子讲

刚才我们假设了

说这个数据帧的长度

这帧长是100比特

对吧

那么

格头上的卷积码编码序列有多少种呢

显然应当是二的100次方

中组合

格图上有2的100次方个序列

这个序列

比如说某一个学者是C如果我要

采用最大的似然译码

也就是说把收到的接收序列Y

与格上任何一个序列C之间要算

汉明距离 我们已经定一步

汉明距离了

算汉明距离

算多少个

一共要算二的100次方的距离

从这里面找一个最小的

最小值所对应的序列

就是它最大似然译码的结果

我只是说说大家看

它就是个理论工具

实用化没有办法做

因为存储量是天文数字

我们没有办法实现

并且搜索量比较量

都是指数爆炸的

那么维特比算法

理论上来讲

它的性能就等价于最大似然译码

但是它的计算量

要远远的小于最大的似然译码

它是一个非常巧妙的算法

下面我们先给大家讲一讲

维特比算法的基本设计思路

然后通过一个例子

来给大家介绍

维特比算法

到底具体是怎么算的

维特比算法的基本思路

实际上是一种

在格图上进行搜索的时候

提前就部分搜索和比较

提前删除一些

非法

或者竞争失败路径

最大限度的降低计算量的

这样的一种搜索过程

那么它的基本思路

我们通过一个身边就生活的例子

先给大家

举个生活例子说明一下

然后我们再来分析

它的迭代计算的过程

因为同学们每个人都有身份证

对吧

我们可以看把身份证的编码

因为身份证是18位编码

我们把身份证的编码

就可以看作

这也是一种编码序列

当然它是采用十进制编码

不是二进制

但是我们可以类比

你比如说我们身份证编码

比如说编出了这1101

08

然后叉叉叉叉

然后XX YY

ZZ.然后后面

还有

CD

E

F后4位

对吧

这就一共18位

假设说

现在公安部门要抓一个通缉犯

然后要在交通要道

比如说火车站

机场

要设卡去检查的身份证号码

那么也就是说

检查每个人的身份证的编码

看看是不是罪犯

也就是说把你的身份证号码

与罪犯的身份证号码

要做查找匹配

那么如果我们采用的

是

最似然译码的

这样的准则来进行

身份证的查找

这个罚度就极高

比如说我们举个例子

你拿到了一个身份证18位的

我就需要采用

最大似然译码的结果

是这么做的

就是我把这18位的身份证编码

与公安部所存储的大陆居民

数据库的14亿人

也接近14亿人的身份证序列的

一个一个比每一个身份证序列

要比14亿次

然后看

能不能找到一个最像的

最匹配的

就是我们的目标值

可是你想每一个序列都要穷举

14亿次

接近14亿次

所有的交通要道就全都被堵死了

对吧

光检查身份证

这个过程都要耗费很长时间

但是现实当中我刚才讲的

现实当中

我们经常会要抓一些

抓罪犯去

去核查身份证号码

从来没有出现过这种现象

就刚才讲的这种堵塞的现象

为什么

有人就有这种生活经验

它是很智能的

我们要去警务人员查询身份证

它根本不是说放到数据库里去穷

搜

看这两个序列之间

是不是像长的一样

其实我们是怎么做的

咱们是智能化的筛选

比如说

我要找的罪犯

他是北京市海淀区的

那么我知道这个信息就是

我这故意留下的

110108

这就是北京市海淀区

那11这是

北京市0108

这是海淀区

是这样的一个编码

你要找到罪犯

我就知道

前6个数字是110108

那么我要比对身份证的时候

就没有必要

18位全比

我只要比较前面这6位

甚至我先比较这两位

因为只要罪犯是北京市的

像山西的河北的

你像其他的14的

23的等等

就不用比了

就直接在前两个数字当中

我就表把其他的

30多个省市的

这个序列就全删除到

如果前两个一样

我才比第3位第4位

是不是01

是不是海淀区的

然后还一样

我们再看08

大家看

我们在人的根据人的生活经验

我们在进行这种比对的时候

是逐段比对的的每一段

如果吻合

我们再看下一段

如果不吻合

直接就删减了

所以我们是逐段比较吻合的

保留

就相当于

我们就把幸存结构保留

如果不吻合的就竞争失败了我们

直接删掉

没有必要全系列都穷举

那么在一边比一边

一边筛选

一边比一边筛选

所以很快就能够查找到目标

结果

这就是维特比算法的设计思想

那么维特比算法它的搜索

也是利用了这种分段比较的过程

它不像最大似然译码的

要进行穷举全序列

全序列上面去计算的接收信号

与发送序列

树图上的候选序列之间的

汉明距离

而是逐段每段一边比一边选

那么这种逐段

比较和选择的操作过程

我们就把它总结为

这样的三步过程

简称叫做是ACS运算

A我们称为是add

所谓是加运算

C Compare

也就是比较运算

S selection也就是所谓的

选择运算

就采用这样的三步操作

ACS就是所谓的加

比

选

我们就能够实现

低复杂度的

最大似然

译码的结果

怎么加怎么选

我们通过这是图上的结构

来给大家说明

我们从这处理图上抽取出来一个

片段

这个片段

比如说我们从这儿抽

看看这是抽到叫观察

这是树图的结果

我们可以看到

在每一拍时钟

实际上是

像212这个地方

是4状态转移到4状态

任意两个状态

都会转移到某一个状态

所以我们把它抽取出来

你看到这相当于是K时刻的两

个状态

Sk中加个0

这个是sk

加个1两个状态

那么在K+1时刻也有个状态

比如说

Sk加1

对吧

我们进行了转移

好

我们假设说上面分支它的编码

比特是

如图所示

下面这个编码比特

我们假设说

如图所示

如图所示

两个比特

好

那么我们假设说

初始状态是从全0开始

已经找出来一个部分路径到了

Sk0状态

以及另外一个部分路径

是到了sk1状态了

对不对

所以

维特比算法当中

sk0 sk1

这两每一个状态

它都有一个度量

这个度量我们就称为是

状态度量

这个状态度量反映的是什么呢

它反映的是

从初始的全0状态出发

到达第k时刻

Sk0状态

就某一个状态

这个部分路径

它与接收序列之间的

汉明距离是不请大家听清楚

是部分路径

对吧

从0时刻到K时刻

这个部分路径

我已经选出来的部分路径

与接收序列之间的汉明距离

汉明距离

我们把它存到

这个状态当中去

就变成状态度量

好

那么sk0它有个状态度量

其实也就是我们用

MSK0表示

Sk1

也有一个状态

度量

我们用MSK1来表示

那么现在我们维特比算法

我们要从这样的一个K时刻

我们要往前推一步

就变成了K+1时刻前进了一步

那么前进一步在树图上

我们就差出来一个蝶形

我们叫做

butterfly叫做蝶型单元

sk0 sk1

转移到sk+1

这是个

一片就是一个蝶形

那么从K时刻

要移到K+1

这个时候

Sk+1状态就有两条路径

对

有两条路径大家看

就是上支路

你看是

从全0状态到

Sk0状态

这个部分路径

然后再加上分支

这不就是一条路径

下面这个制度

就从全0状态出发

到sk1状态

再加上一个分支

这也是一个路径

这有两条路径

那么这两条路径的汉明距离

怎么算

很简单

不就是K时刻

Sk0的状态度量

我们刚才讲着

已经算出来的部分汉明距离了

然后要

这就是所谓的加法操作

加什么

加一个分支度量

分支度量 我们假设说

从在第k拍时钟

接收信号序列是YK比如说YK0

YK1对吧

它收到了两个比特 YK0YK1

那么上支路的路径上的分支

编码比特是CK0CK1

我就可以计算

YK0

YK2和上面植入上面

它的编码比特向量

是CK0

CK

这都是两比特

这两个比特之间

可以算汉明距离

汉明距离

其实就反映了支路上面

接收信号

编码比特之间的

这这个距离差

叫汉明距离

对吧

把分支的距离叠加到状态

度量上去

这不就相当于是

上面路径扩展一步以后的

汉明距离

就路径的汉明距离

对不对

以此类推下支路

把状态度量sk一再叠加上呢

YK0 YK1与

CK2

CK3 它们之间的汉明

距离

这两个分支的汉明距离

加大下面的状态度量上去

这就相当于两个状态

各加一个分支度量

这就完成了第一步操作

就是加比选当中的

第一步加法操作

相当于分支度量

要加到状态度量上

这样就能算出来

扩展一步的

路径的部分汉明距离了

第二步就是比较

你不是算出两个距离吗

我们现在用的最大

最大似然在BSC信道当中

等效准则就最小距离准则

显然我们算出两个路径来

的汉明距离了

我们就要比较是什么

看谁大谁小

对吧

比完了以后

我们不妨假设说上支路小

也就是说前面比后面的小

那么小的我们就优选

最后我们就优选出来说上支路

这个部分路径是幸存路径

也就是说把它保留

更新为选择出来

作为 sk+1状态

它的状态都凉了

下支路这个路径

它是竞争失败路径

就丢弃了

所以这就进行了比较和选择

也就算出来了

K+1时刻某一个状态的

现存路径所对应的状态

度量了

每一个状态都得这么做

这就是加比选

那么这是它的核心操作

我们稍微再补充它的初始化

那么初始的时候

维特比算法的状态度量

怎么设定

大家看举的例子

212卷积码里面

这有4个状态

对吧

ABCD初始的时候

因为我们知道

它是从全0状态出发的

所以我们初始化权利状态

状态度量是0

其他状态都是这样的

我们就给个大局

度量越小可能性越大

度量越大可能性越小

理论上我们给个无穷大

实际当中你比如说1000

10000都行

随便 我们编程的时候

就有一个大致

这样的话

给定初值了

然后我们用加比选操作

在格图上

每走一步

就加比选通过计算分支度量

和状态度量进行累加

然后比较选择度量

最小的

作为幸存入竞丢弃

竞争失败路径

从开始一拍一拍一拍一拍

在这个图上做

到最后做完了以后

怎么选择最终的结果呢

我们把它假设

已经回到了全0状态了

从全0状态回溯

找 找出来的

回溯译码的结果

找出来是哪一个

我们把译码路径的信息位

读出来

那就是译码的结果了

所以维特比算法的基本设计思路

就是采用的加比选操作

来实现整个的译码结果

那么我们刚才已经给大家讲过了

维特比算法的基本思路了

我们给大家做一点归纳和总结

维特比算法

它在性能上

是可以达到的

最大似然译码的性能的

那么维特比算法

它的复杂度

我们可以简单做个评估

最大的似然译码

算法

刚才我们提到过

假设说帧长是N

最大似然译码算法

它的复杂度

实际上我们是要进行穷举的

因此它的算法复杂度

应当是2的N次方

对于维德比算法来讲

它的算法复杂度

我们可以这样算

因为相当于trellis里面有N节

每一节

它其实有2的 km次方的状态

那么每一个状态

它要进行加比选操作

要有2的K次方的分支

因此要做2的K次方次

加法操作

然后进行比较和选择

因此它的计算复杂度

应当是2的K×M+1

的计算量

所以明显大家能够看到

维特比算法的计算量

要远小于最大似然

因为最大似然

它是一个指数复杂的算法

正常是在指数上

而对于维特比算法复杂度

是与帧长成线性比例关系

它的计算复杂度

主要是受约束长度的限制

M+1就约束长度

一般对于中等约束长度的卷积码

那么维特比算法法则并不太高

所以它是既具有理论上最优的

性能

又具有比较低的

复杂度的

一种非常好的译码方法

在实际的数字通信系统当中

只要用卷积码算法

现在最流行的一码方法

就用维特比算法

那么维特比算法

自从1967年

由安德鲁维特比发明以来

已经广泛的应用到了

各个通信领域当中

比如说像卫星通信

数字地面广播

还有移动通信系统当中

都普遍采用了

卷积码编码和维特比算法

前面两部分就是我们

给大家介绍的

线性分组码

和卷积码的基本知识