【信道编码/Channel Coding】纠错编码与差错控制
简介:
这是本专栏信道编码/Channel Coding的第一站,想对信道编码有一个系统性的认识可以看本专栏的 信道编码的整体框架 一文。而在本篇文章中,将介绍如何看一族码字的检错能力以及纠错能力,以及整个传输系统中,我们有什么进行差错控制的方式,这是踏入信道编码的第一步。
目录
1.3 最小码距 (Minimum Code Distance)
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), 里面不同码字两两之间都有汉明距离对吧,那么那么多的汉明距离中,最小的那个就是最小码距,记为 , 这个参数非常重要。打个比方吧,下面是一个 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 检错能力
一族码字的检错能力由下面公式计算而得:
原理:
假设最小码距是3,我们是不是说过,最小码距是众多汉明距离中最小的那个。所以对于一族码字中的其中一段码字,它和其他码字之间不同的比特数最少是3,也就是说,这个码字要至少错3个比特才能变成另一段码字,而变成另一段码字之后,译码器当然就把它翻译成另一个码字去了,也即错三个比特就超出译码器检错范围了。但是假如只错了一个或者两个比特呢?它就会变成一个对于译码器而言非常陌生的一段码字,这时候译码器就知道错了。画成图就是这样:
这个红圈你就可以理解为汉明球。可以清晰看到检错能力就是:
2.2 纠错能力
一族码字的纠错能力由下面公式计算得到:(这不是方括号,是向下取整)
仍然取最小码距为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中,发送端对接收端反馈回传的数据进行比较,判断有无传输差错。通常这种只会在非常低出错率的信道中使用,现在可能也没啥地方会用这个了。