有扰离散信道的编码定理

香农在他的经典著作中提出了著名的信息编码定理：

对于一个给定的有扰信道，若信道容量为C，只要发送端以低于C的速率R发送信息（R为编码器的输入二进制码元速率），则一定存在一种编码方法，使编码错误概率P随着码长的n的增加，按指数下降到任意小的值。表示为

这里，E(R)称为误差指数，它与R和C的关系如图1所示。

这条定理告诉我们两条理论：

（1）在码长及发送信息速率一定的情况下，为减小P，可以增大信道容量。

（2）在信道容量及发送信息速率一定的条件下，增加码长，可以使错误概率指数下降。

香农的信息编码定理为信道编码奠定了理论基础，虽然定理本身并没有给出具体的差错控制编码方法和纠错码的结构，但它从理论上为信道编码的发展提出了努力方向。

检错和纠错的基本原理

下面我们以三位二进制码组为例，说明检错纠错的基本原理。三位二进制码元共有8种可能的组合：000、001、010、011、100、101、110、111。如果这8种码组都可传递消息，若在传输过程中发送一个误码，则一种码组会错误地变成另一种码组。由于每一种码组都可能出现，没有多余的信息量，因此接收端可能发现错误，以为发送的就是另一种码组。但若我们只选用000、011、101、110这4种码组（这些码组称为许用码组）来传送消息，这相当于只传递00、01、10、11四种信息，而第3位是附加的。这位附加的监督码元与前面两位码元一起，保证码组中“1”码的个数为偶数。除上述4种许用码组以外的另外4种码组不满足这种校验关系，称为禁用码组，就表明传输过程中发生了错误。用这种简单的校验关系可以发现一个和三个错误，但不能纠正错误。

几种实用的简单检错码

奇偶监督码、水平奇偶监督码、水平垂直奇偶监督码、群计数码、恒比码ISBN国际统一图书编号。

差错控制系统中使用的信道编码可以有多种。

按照差错控制编码的不同功能，可以将其分为检错码、纠错码和纠删码。检错码仅能检测误码；纠错码仅可纠正误码；纠删码则兼有纠错和检错能力，当发现不可纠正的错误时可以发出错误只是或者简单地删除不可纠正错误的信息段落。

按照信息码元和附加的监督码元之间的检验关系可以分为线性码和非线性码。若信息码元与监督码元之间的关系为线性关系，即满足一组线性方程式，则称为线性码。反之，若两者不存在线性关系，则称为非线性码。

按照信息码元和监督码元之间的约束方式不同可以分为分组码和卷积码。在分组码中，编码后的码元序列每n位分为一组，其中k个是信息码元，r个是附加的监督码元，r=n-k。监督码元仅与本码组的信息码元有关，而与其它码组的信息码元无关。卷积码则不然，虽然编码后序列也划分为码组，但监督码元不但与本组信息码元有关，而且与前面码组的信息码元也有约束关系。

按照信息码元在编码后是否保持原来的形式不变，可划分为系统码和非系统码。在差错控制编码中，通常信息码元和监督码元在分组内有确定的位置，一般是信息码元集中在码组的前k位，而监督码元集中在后r=n-k位（有时两者倒过来放置）。在系统码中，编码后的信息码保持原样不变，而非系统码中信息码元则改变了原有的信号形式。系统码的性能大体上与非系统码相同，但是在某些卷积码中非系统码的系统优于系统码。优于非系统码中的信息位已“面目全非”，这对观察和译码都带来麻烦，因此很少应用。系统码的编码和译码相对比较简单些，因而得到广泛应用。

按照纠正错误的类型不同，可以分为纠正随机错误的码和纠正突发错误的码。前者主要用于发生零星独立错误的信道，而后者则用于对付以突发错误为主的信道。

按照构造差错控制编码的数学方法来分类，可以分为代数码、几何码和算术码。代数码建立在近世代数学基础上，是目前发展最为完善的编码。线性码是代数码的一个最重要的分支。

按照每个码元取值不同，可以分为二进制码和多进制码。

常用的差错控制方式主要有三种：检错重发（简称ARQ）、前向纠错（简称FEC）和混合纠错（简称HEC）。

检错重发方式中，发送端经编码后发出能够发现错误的码，接收端收到后经检验如果发现传输中有错误，则通过反向信道把这一判断结果反馈给发送端。然后，发送端把前面发出的信息重新传送一次，直到接收端认为已正确地收到信息为止。

常用的检错重发系统有三种，即停发等候重发、返回重发和选择重发。发送端在Tw时间内送出一个码组给接收端，接收端收到后经检测若未发现错误，则发回一个认可信号（ACK）给发送端，发送端收到ACK信号后再发出下一个码组。如果接收端检测出错误，则发回一个否认信号（NAK），发送端收到NAK信号后重发前一个码组，并再次等候ACK或NAK信号。这种工作方式在两个码组之间有停顿时间（Ti），使传输效率受到影响，但由于工作原理简单，在计算机数据通信中仍得到应用。

在这种系统中发送端无停顿地送出一个又一个码组，不再等候ACK信号，但一旦接收端发现错误并发回NAK信号，则发送端从下一个码组开始重发前一段N组信号，N的大小取决于信号传递及处理所带来的延时，这种返回重发系统比停发等候重发系统有很大改进，在很多数据传输系统中得到应用。

这种重发系统也是连续不断地发送信号，接收端检测到错误后发回NAK信号。与返回重发系统不同的是，发送端不是重发前面的所有码组，而是只重发有错误的那一组。显然，这种选择重发系统传输效率最高，但另一方面它的价格也最贵，因为它要求较为复杂得控制，在发送、接收端都要求有数据缓存器。此外，选择重发系统和返回重发系统都需要全双工的链路，而停发等候系统只要求半双工的链路。

前向纠错系统中，发送端经编码发出能够纠正错误的码，接收端收到这些码组后，通过译码能自动发现并纠正传输中的错误。前向纠错方式不需要反馈信道，特别适合于只能提供单向信道的场合。由于能自动纠错，不要去检错重发，因而延时小、实时性好。为了使纠错后获得低误比特率，纠错码应具有较强的纠错能力。但纠错能力愈强，则译码设备愈复杂。前向纠错系统的主要缺点就是设备较复杂。

混合纠错方式是前向纠错方式和检错重发方式的结合。在这种系统中发送端不但有纠正错误的能力，而且对超出纠错能力的错误有检测能力。遇到后一种情况时，通过反馈信道要求发送端重发一遍。混合纠错方式在实时性和译码复杂性方面是前向纠错和检错重发方式折中。

在实际信道上传输数字信号时，由于信道传输特性不理想及加性噪声的影响，所收到的数字信号不可避免地会发生错误。为了在已知信噪比的情况下达到一定的误比特率指标，首先应合理设计基带信号，选择调制、解调方式，采用频域均衡和时域均衡，使误比特率尽可能降低，但若误比特率仍不能满足要求，则必须采用信道编码，即差错控制编码，将误比特率进一步降低，以满足指标要求。

随着差错控制编码理论的完善和数字电路技术的发展，信道编码已成功地应用于各种通信系统中，而且在计算机、磁记录与存储中也得到日益广泛的应用。

差错控制编码的基本做法是：在发送端被传输的信息序列上附加一些监督码元，这些多余的码元与信息码元之间以某种确定的规则相互关联（约束）。接收端按照既定的规则检验信息码元与监督码元之间的关系，一旦传输过程中发生差错，则信息码元与监督码元之间的关系将受到破坏，从而可以发现错误，乃至纠正错误。研究各种编码和译码方法正式差错控制编码所要解决的问题。

在通信中，由于信息码元序列是一种随机序列，接收端无法预知码元的取值，也无法识别其中有无错码。所以在发送端需要在信息码元序列中增加一些差错控制码元，它们称为监督码元（校验元）。这些监督码元和信息码元之间有确定的关系。

在信息码元序列中加监督码元就称为差错控制编码，差错控制编码属于信道编码。

信息码元和监督码元之间有一种关系，关系不同，形成的码类型也不同。可分为两大类：分组码和卷积码。其中，分组码是把信息码元序列以每k个码元分组，编码器将每个信息组按照一定规律产生r个多余的码元（称为校验元），形成一个长为n=k r的码字。

这里主要介绍线性编码有关内容

线性编码

术语代数编码理论表示编码原理的子领域，其编码性质以代数术语表示，然后进一步研究 。

代数编码理论基本上分为两大类代码：

线性分组码

卷积码

它分析一个编码的以下三个特性-主要是：

码字长度

有效代码字总数

两个有效代码字之间的最小距离，主要使用汉明距离，有时也使用其他距离像Lee距离。

线性分组码

线性分组码具有的特性的线性度，即，任何两个码字的总和也是一个编码字，并且它们被应用到组的源比特中，因此称为线性分组码。有分组码不是线性的，但是很难证明编码是没有这个属性的编码。

线性分组码由其符号字母（例如，二进制或三元）和参数（n，m，

n是码字的长度，以符号表示，

m是将一次用于编码的源符号的数量，

有许多类型的线性分组码，如循环码（如汉明码）、重复代码、奇偶校验码、多项式编码（例如BCH码）、里德 - 所罗门编码、代数几何编码、里德 - 穆勒编码、完美编码。

编码原理使用N维球体模型。例如，可以在桌面上或三维中将多少便士包装成圆圈，可以将多少个弹珠包装在一个球面上。其他注意事项输入编码的选择。例如，六边形包装成矩形框的约束将在角落留下空的空间。随着尺寸越来越大，空白空间的百分比越来越小。但是在某些维度上，包装使用所有空间，这些代码是所谓的“完美”代码。唯一非常重要和有用的完美编码是距离为3汉明码，其参数满足（2 r - 1，2 r - 1 - r，3）和[23,12,7]二进制和[11,6,5 ]三重Golay码。

另一个编码属性是单个码字可能具有的邻居的数量。再次，以便士为例。首先我们把便士打包成矩形网格。每一分钱将有4个邻近的邻居（在距离更远的角落有4个）。在六边形，每一分钱将有6个近邻。当我们增加尺寸时，近邻的数量增加非常快。结果是使接收端选择邻居（因此错误）的噪声的方式也增加。这是分组码以及所有编码的基本限制。可能更难对单个邻居造成错误，但邻居数量可能足够大，因此总错误概率实际上会受到影响。

线性分组码的属性可以应用于很多应用。例如，线性分组码的校正子集合唯一性被用网格成形，是最有名的形状码之一。传感器网络中使用相同的属性进行分布式源代码编码。

卷积码

如果特定的一致监督关系不是在一个码字中实现，而是在个码字中实现，这种码称为卷积码。卷积码可用移位寄存器来实现，这种卷积编码器的输出可看作是输入信息码元序列与编码器响应函数的卷积。能纠正突发错误的哈格伯尔格码也是一种卷积码。在平稳高斯噪声干扰的信道上采用序贯译码方法的卷积码有很好的性能，能用于卫星通信和深空通信。

UTF-8 编码原理

为了统一全世界各国语言文字和专业领域符号（例如数学符号、乐谱符号）的编码，ISO制定了ISO 10646标准，也称为UCS（Universal Character Set）。UCS编码的长度是31位，可以表示231个字符。如果两个字符编码的高位相同，只有低16位不同，则它们属于一个平面（Plane），所以一个平面由216个字符组成。目前常用的大部分字符都位于第一个平面（编码范围是U-00000000~U-0000FFFD），称为BMP（Basic Multilingual Plane）或Plane 0，为了向后兼容，其中编号为0~256的字符和Latin-1相同。UCS编码通常用U-xxxxxxxx这种形式表示，而BMP的编码通常用 U xxxx这种形式表示，其中x是十六进制数字。在ISO制定UCS的同时，另一个由厂商联合组织也在着手制定这样的编码，称为Unicode，后来两家联手制定统一的编码，但各自发布各自的标准文档，所以UCS编码和Unicode码是相同的。

有了字符编码，另一个问题就是这样的编码在计算机中怎么表示。现在已经不可能用一个字节表示一个字符了，最直接的想法就是用四个字节表示一个字符，这种表示方法称为UCS-4或UTF- 32，UTF是Unicode Transformation Format的缩写。一方面这样比较浪费存储空间，由于常用字符都集中在BMP，高位的两个字节通常是0，如果只用ASCII码或Latin-1，高位的三个字节都是0。另一种比较节省存储空间的办法是用两个字节表示一个字符，称为UCS-2或UTF-16，这样只能表示BMP中的字符，但BMP中有一些扩展字符，可以用两个这样的扩展字符表示其它平面的字符，称为Surrogate Pair。无论是UTF-32还是UTF-16都有一个更严重的问题是和C语言不兼容，在C语言中0字节表示字符串结尾，库函数strlen、 strcpy等等都依赖于这一点，如果字符串用UTF-32存储，其中有很多0字节并不表示字符串结尾，这就乱套了。

UNIX之父Ken Thompson提出的UTF-8编码很好地解决了这些问题，现在得到广泛应用。UTF-8具有以下性质：

* 编码为U 0000~U 007F的字符只占一个字节，就是0x00~0x7F，和ASCII码兼容。

* 编码大于U 007F的字符用2~6个字节表示，每个字节的最高位都是1，而ASCII码的最高位都是0，因此非ASCII码字符的表示中不会出现ASCII码字节（也就不会出现0字节）。

* 用于表示非ASCII码字符的多字节序列中，第一个字节的取值范围是0xC0~0xFD，根据它可以判断后面有多少个字节也属于当前字符的编码。后面每个字节的取值范围都是0x80~0xBF，见下面的详细说明。

* UCS定义的所有231个字符都可以用UTF-8编码表示出来。

* UTF-8编码最长6个字节，BMP字符的UTF-8编码最长三个字节。

* 0xFE和0xFF这两个字节在UTF-8编码中不会出现。

具体来说，UTF-8编码有以下几种格式：

U-00000000 – U-0000007F: 0xxxxxxx

U-00000080 – U-000007FF: 110xxxxx 10xxxxxx

U-00000800 – U-0000FFFF: 1110xxxx 10xxxxxx10xxxxxx

U-00010000 – U-001FFFFF: 11110xxx 10xxxxxx10xxxxxx 10xxxxxx

U-00200000 – U-03FFFFFF: 111110xx 10xxxxxx10xxxxxx 10xxxxxx 10xxxxxx

U-04000000 – U-7FFFFFFF: 1111110x 10xxxxxx10xxxxxx 10xxxxxx 10xxxxxx 10xxxxxx

第一个字节要么最高位是0（ASCII字节），要么最高两位都是1，最高位之后1的个数决定后面有多少个字节也属于当前字符编码，例如111110xx，最高位之后还有四个1，表示后面有四个字节也属于当前字符的编码。后面每个字节的最高两位都是10，可以和第一个字节区分开。这样的设计有利于误码同步，例如在网络传输过程中丢失了几个字节，很容易判断当前字符是不完整的，也很容易找到下一个字符从哪里开始，结果顶多丢掉一两个字符，而不会导致后面的编码解释全部混乱了。上面的格式中标为x的位就是UCS编码，最后一种6字节的格式中x位有31个，可以表示31位的UCS编码，UTF-8就像一列火车，第一个字节是车头，后面每个字节是车厢，其中承载的货物是UCS编码。UTF-8规定承载的UCS编码以大端表示，也就是说第一个字节中的x是UCS编码的高位，后面字节中的x是UCS编码的低位。

例如U 00A9（©字符）的二进制是10101001，编码成UTF-8是11000010 10101001（0xC2 0xA9），但不能编码成11100000 10000010 10101001，UTF-8规定每个字符只能用尽可能少的字节来编码。

电子产品代码（EPC编码）是国际条码组织推出的新一代产品编码体系。原来的产品条码仅是对产品分类的编码，EPC码是对每个单品都赋予一个全球唯一编码，EPC编码96位（二进制）方式的编码体系。96位的EPC码，可以为2.68亿公司赋码，每个公司可以有1600万产品分类，每类产品有680亿的独立产品编码，形象的说可以为地球上的每一粒大米赋一个唯一的编码。

EPC编码的原则：

1、唯一性 2、简单性 3、可扩展性 4、保密性与安全性

EPC编码关注的问题：

1、生产厂商和产品 2、内嵌信息 3、分类 4、批量产品编码 5、载体

EPC编码结构：

EPC编码数据结构标准规定了EPC数据结构的特征、格式、现有EAN.UCC系统中的GTIN、SSCC、GLN、GRAI、GIAI、GSRN及NPC与EPC编码的转换方式。 EPC编码数据结构标准适用于全球和国内物流供应链各个环节的产品（物品、贸易项目、资产、位置等）与服务等的信息处理和信息交换。