专栏首页小锋学长生活大爆炸基于信息论的编码技术

基于信息论的编码技术

摘 要

信息论是通过应用密码学、概率论、信息熵、通信系统、随机过程等方法,来研究信息的传输、提取和处理系统的一门学科。而编码技术研究的主要内容是如何既可靠又有效地传输信息。1948年香农在《贝尔系统技术杂志》上发表了《通信的数学理论》。次年,他又发表了另一篇著作《噪声下的通信》。人们认为这两篇文章成了现在信息论的奠基著作。1959年香农发表了“保真度准则下的离散信源编码定理”,首先提出了率失真函数及率失真信源编码定理,此后发展成为信息率失真编码理论。现在,信息理论广泛应用在通信、计算机等领域,随着通信安全与质量的高要求化,编码技术也在不断地突飞猛进。

关键词

信息论 编码 综述

正 文

信息论是通过应用密码学、概率论、信息熵、通信系统、随机过程等方法,来研究信息的传输、提取和处理系统的一门学科(如图1[[1]]所示)。信息论在统计物理(热力学)计算机科学(科尔莫戈罗夫复杂度)、推断统计(奥卡姆剃刀)等学科方向中都有奠基性的贡献。信息论将信息的传递作为一种统计现象来考虑,给出了估算通信信道容量的方法。信息传输和信息压缩是信息论研究中的两大领域。这两个方面又由信息传输定理、信源-信道隔离定理相互联系。

图 1 信息论研究领域

1948年香农在《贝尔系统技术杂志》上发表了《通信的数学理论》。次年,他又发表了另一篇著作《噪声下的通信》。人们认为这两篇文章成了现在信息论的奠基著作。1959年香农发表了“保真度准则下的离散信源编码定理”,首先提出了率失真函数及率失真信源编码定理,此后发展成为信息率失真编码理论。

香农第一定理是可变长无失真信源编码定理、香农第二定理是有噪信道编码定理、香农第三定理是保失真度准则下的有失真信源编码定理。香农的这三大定理是信息论的基础理论。这三大定理都是存在性定理,虽然并没有提供具体的编码实现方法,但为通信信息的研究指明了方向。

从图2可知,当信源、信道、信宿确定后,编码与译码部分对信号的传输将起至关作用。因此,自信息论发展以来,许多科学家对编码的研究也是从未止步。

图 2 信息传输模型

由于香农虽然指出了可以通过差错控制码在信息传输速率不大于信道容量的前提下实现可靠通信,但却没有给出具体实现差错控制编码的方法,对于编码的实现一直止步不前。终于,在1949年,R.Hamming和M.Golay提出了第一个实用的差错控制编码方案,人类在信道编码上实现了第一次的突破。

数学家R.Hamming将每4个比特的输入数据设置成一组,并通过计算这些信息的线性组合来得到3个校验比特,然后将得到的7个比特输入计算机。通过按照设定的算法和原则, 计算机能读取这些字码并够检测到是否有错误,同时还可定位到发生错误的具体位置。该码还可以纠正比特串中发生的单个比特错误。这个编码方法就是分组码的基本思路,这个编码方案后来被命名为汉明码。由于每4个比特编码就需要3个比特的冗余校验比特,而且在一个码组中只能纠正单个比特错误,这使得汉明码的编码效率较低。

M.Golay先生研究了汉明码的缺点,提出了Golay码。通过将不同个数的信息比特分为一组,Golay码可以分为二元Golay码和三元Golay码。前者将信息比特每12个分为一组,编码生成11个冗余校验比特,相应的译码算法可以纠正3个错误;后者的操作对象是三元而非二元数字,三元Golay码将每6个三元符号分为一组,编码生成5个冗余校验三元符号,这样由11个三元符号组成的三元Golay码码字可以纠正2个错误。

Elias在1955年提出卷积码编码方式。卷积码与分组码的不同在于:它充分利用了各个信息块之间的相关性。通常卷积码记为(n,k,N)码。卷积码的编码过程是连续进行的,依次连续将每k个信息元输入编码器,得到n个码元,得到的码元中的检验元不仅与本码的信息元有关,还与以前时刻输入到编码器的信息元(反映在编码寄存器的内容上)有关。同样,在卷积码的译码过程中,不仅要从本码中提取译码信息,还要充分利用前后时刻收到的码组。从中提取相关信息,而且译码也是可连续进行的,这样可以保证卷积码的译码延时相对比较小。

图 3 卷积码编码器一般原理

1967年,Viterbi提出了Viterbi译码算法。在Viterbi译码算法提出之后,卷积码在通信系统中得到了极为广泛的应用,如GSM、 IS-95 CDMA、3G、商业卫星通信系统等。

1993年,在日内瓦召开的 IEEE通信国际会议上,两位当时普通的法国电机工程师C.Berrou和A.Glavieux称他们发明了一种编码方法,可使信道编码效率接近香农极限[[2]]。

在Turbo码解码过程中,某一特定比特的电平被量化为整数。其数值就作为判决该比特为“1”或“0”的可置信度的度量。Turbo码系统在发射端和接收端分别设置两个编[[3]]码器和解码器。其中一对编解码器对特定的一段比特流进行奇偶校验码的加入和校验计算,另一对编解码器则在同一段码流经过交织扰动后对其进行上述同样操作。

图 4 Turbo码原理图

一开始,Turbo码只是应用于一些特殊场合,比如卫星链路。后来,研究人员将它扩展到数字音频和视频广播领域。紧接着,Turbo码成为通信研究的前沿,Turbo码成为了始于本世纪初的3G/4G移动通信技术的核心,直到今天4.5G依然在采用。

1999年,LDPC低密度奇偶校验码于1962年由Gallager提出,然后,被人们遗忘了。直到Turbo码被提出以后,人们才发现Turbo码从某种角度上说也是一种LDPC码[[4]]。

图 5 LDPC码系统框图

2007年,土耳其比尔肯大学教授E.Arikan基于信道极化理论提出的一种线性信道编码方法,即Polar码。该码字是迄今发现的唯一一类能够达到香农限的编码方法,并且具有较低的编译码复杂度,当编码长度为N时,复杂度大小为 O ( NlogN) [[5]]。Polar码的编码策略正是应用了这种现象的特性,利用无噪信道传输用户有用的信息,全噪信道传输约定的信息或者不传信息。Polar码比Turbo码和LDPC码更接近信道容量,Polar码可以保证5G任何场景的高性能通信。

结 论

信道编码技术广泛应用于数字通信系统中,有的已经被应用于某些无线通信标准中。相信随着信道编码技术会随着 信道编码理论的发展在通信领域得到更深入的应用。


[[1]] Cover T M, Thomas J A. Elements of information theory[M]. John Wiley & Sons, 2012.

[[2]] 刘东华.Turbo码原理与应用技术[M].北京:电子工业出版社,2004.

[[3]] 卢彦民.纠错码ASIC设计及低功耗设计研究[M],2007

[[4]] 白宝明,孙成,陈佩瑶,等.信道编码技术新进展[J].无线电通信技术,2016,42(6):1-8.

[[5]] ARIKAN E.Channel Polarization:a method for construction capacity-achieving codes for symmetric binary-input memoryless channels[J].IEEE Transactions on Information Theory,2009,55(7):3051-3073.

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • Maven工程java -jar时提示xxx-SNAPSHOT.jar中没有主清单属性

    小锋学长
  • 紧急避坑!stm32cube+freertos+fatfs挂载正常, read等其他操作都返回错误3 not ready

    紧急避坑!!!如果没有用freertos,那中断优先级设置没啥关系。但如果用了freertos,那SDIO的优先级必须要注意跟freertos区分开来,不能高过...

    小锋学长
  • 深度学习基础知识题库大全

    解析:正确答案A,更多层意味着网络更深。没有严格的定义多少层的模型才叫深度模型,目前如果有超过2层的隐层,那么也可以及叫做深度模型。

    小锋学长
  • python笔记39-unittest框架如何将上个接口的返回结果给下个接口适用(面试必问)

    面试必问:如何将上个接口的返回结果,作为下个接口的请求入参?使用unittest框架写用例时,如何将用例a的结果,给用例b使用。 unittest框架的每个用例...

    上海-悠悠
  • UML之用例图

    UML-Unified Model Language 统一建模语言,又称标准建模语言。是用来对软件密集系统进行可视化建模的一种语言。 在UML系统开发中...

    chain
  • THINKPHP5.1 Config的配置与获取详解

    首先需要在控制器内引入Config类,这里使用5.1新增的facade,通过facade可以静态的调用原本需要被继承才能使用的方法。

    砸漏
  • windows系统中eclipse C开发环境的架设

    虽然c有很多经典的开发环境,但是大多数是linux或unix下的,对于windows的忠实用户来讲,可能并不习惯。 windows环境中,有一个dev-c++可...

    菩提树下的杨过
  • npm 切换源

    咻一咻
  • centos7文件共享服务器nfs搭建

    相对于samba来说,如果仅仅只是希望搭建一个linux之间进行文件共享的服务器,而不是所有异构的系统之间共享的话,nfs是一个不错的选择。但是客户端如果想要共...

    十里桃花舞丶
  • JavaScript 数组去重的多种方法原理详解

    数组去重,这是一个面试经常会遇见的问题,网上讲数组去重的文章也是特别的多,但是我们依旧来讲讲数组去重,这篇文章比较适合于接触过一段时间的JavaScript的初...

    FEWY

扫码关注云+社区

领取腾讯云代金券