【信道编码/Channel Coding】纠错编码与差错控制

简介:


这是本专栏信道编码/Channel Coding的第一站,想对信道编码有一个系统性的认识可以看本专栏的 信道编码的整体框架 一文。而在本篇文章中,将介绍如何看一族码字的检错能力以及纠错能力,以及整个传输系统中,我们有什么进行差错控制的方式,这是踏入信道编码的第一步。

目录

简介:

一、纠错码的主要结构特征

1.1 汉明重量 (Hamming weight)

1.2 汉明距离 (Hamming distance)

1.3 最小码距 (Minimum Code Distance)

1.4 汉明球 (Hamming Sphere)

二、纠错码的检错与纠错能力

2.1 检错能力

2.2 纠错能力

三、差错控制的方式

3.1 FEC(Forward Error Correction)前向纠错

3.2 ARQ (Automatic Repeat Request) 自动请求重传

3.3 IRQ(Information Repeat Request)信息重传


一、纠错码的主要结构特征


纠错码的纠错能力是由构造码字的数学结构决定的,其基本结构特征有:

1.1 汉明重量 (Hamming weight)

汉明重量就是一段码字里,非零码元的个数,对于二元的数字传输系统来讲,由于码元只有0或1的取值,所以码字里面1的个数就是汉明重量。比如10101011的汉明总量就是5。

1.2 汉明距离 (Hamming distance)

汉明距离就是两段码字之间不同的码元个数。比如101110和001100之间,可以清楚地看到两段码字的第1,5位是不同的,所以他们之间的汉明距离就是2。汉明距离还可以这么理解,就是两段码字进行异或之后得到的码字的汉明重量(有大用,读者体会一下)。

1.3 最小码距 (Minimum Code Distance)

最小码距是这么来的。对于一族码字 C(n,k), 里面不同码字两两之间都有汉明距离对吧,那么那么多的汉明距离中,最小的那个就是最小码距,记为 d_{min}, 这个参数非常重要。打个比方吧,下面是一个 C(6,3) 的线性分组码:

MESSAGE

CODE VECTOR

Weight

000

000000

0

001

110001

3

010

101010

3

011

011011

4

100

011100

3

101

101101

4

110

110110

4

111

000111

3

你可以进行多次计算两两之间的Hamming Distance,你会发现最小码距就是3,但是我们都知道,两两计算汉明距离也太慢了,有没有简单方法?

答案是有,就和 “汉明距离还可以这么理解,就是两段码字进行异或之后得到的码字的汉明重量。”这句话密不可分,由于线性分组码的性质,任意两段码字相异或在之后得到的码字任然在这一族码字中。所以看最小码距就简化到看汉明重量,所以一看就看到这一族码字中最小码距是3(非零)。

1.4 汉明球 (Hamming Sphere)

这是一个抽象概念,我们到下面会使用,到时候自然就明白了。

二、纠错码的检错与纠错能力


一族纠错码的检错与纠错能力都可从其 最小码距 中计算出来

2.1 检错能力

一族码字的检错能力由下面公式计算而得:

t_d=d_{min}-1

原理:

假设最小码距是3,我们是不是说过,最小码距是众多汉明距离中最小的那个。所以对于一族码字中的其中一段码字,它和其他码字之间不同的比特数最少是3,也就是说,这个码字要至少错3个比特才能变成另一段码字,而变成另一段码字之后,译码器当然就把它翻译成另一个码字去了,也即错三个比特就超出译码器检错范围了。但是假如只错了一个或者两个比特呢?它就会变成一个对于译码器而言非常陌生的一段码字,这时候译码器就知道错了。画成图就是这样:

 这个红圈你就可以理解为汉明球。可以清晰看到检错能力就是:t_d=d_{min}-1

2.2 纠错能力

一族码字的纠错能力由下面公式计算得到:(这不是方括号,是向下取整)

t_c=\left \lfloor \frac{d_{min}-1}{2} \right \rfloor

 仍然取最小码距为3,假如我们译码的时候按照最大似然译码准则(简单理解就是就近原则),比如一族中的一个码字错了一个比特,由于它距离变成另一个码字还有两个比特,所以我们会将其译为和它距离最近的那个码字(即能正确译码),但假如码字错了两个比特,它距离变成另一个码字只有一比特了,这时候出错的码字距离另一个码字更近,按就近原则就译为另一个码字了,这就出错了。可视化表示如下:

三、差错控制的方式


通信中的差错控制方式有三大类

3.1 FEC(Forward Error Correction)前向纠错

其系统图:

 正如系统图表示的一样,FEC的差错控制方式就是在接收端进行纠错,是单向的,不涉及重传。通常卷积码,RM码和Turbo码的系统会进行FEC的差错控制。在数字电视传播中LDPC码也成为了FEC的必备手段。

3.2 ARQ (Automatic Repeat Request) 自动请求重传

其系统图:

 

 可以看到,在ARQ中,有前向和后向的信道,也就是说,ARQ差错控制方式涉及重传的协议,比如接收端检查到错误,向发送端发信息说错了,然后发送端重传。而这诞生了三种协议:

3.2.1 Stop & Wait (SW,停等)

发送端每发送一帧之后停下等待接收方的确认返回。

3.2.2 Go Back N (GB-N,回退N步)

发送端不向SW协议一样等待确认信号,而是一直发,但是收到错误信息之后,从那个发生错误的帧开始及其之后的全部帧重传。

3.2.3 Selective Repeat (SR,选择重传)

发送端不等待确认信号,若收到错误信息,则只重传错误的帧

3.2.4 Hybrid ARQ(HARQ,混合ARQ)

混合ARQ是对传统ARQ的所做的重要改进。

通常CRC校验码检测会出现在ARQ系统中。

3.3 IRQ(Information Repeat Request)信息重传

IRQ是不用纠错码或检错码的差错控制方式,在IRQ中,发送端对接收端反馈回传的数据进行比较,判断有无传输差错。通常这种只会在非常低出错率的信道中使用,现在可能也没啥地方会用这个了。


版权声明:本文为Tomatomatodo原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
THE END
< <上一篇
下一篇>>