编码的基本方式
数据编码的常见编码？
数据编码的常见编码？
数据编码的目的是将数字数据转化成数字信号，以便在数字信道中传输。最常见的数据编码方式有三种：(1)非归零码：数字编码的一种方式，分别用正负2种不同的电平来分别表示0和1。要点：最简单，容易出错。(2)曼彻斯特编码：数字编码的一种方式，在非归零码码元的正中间时间出现了一次电平跳变，这样接收方可以将此作为同步信号。数字0对应信号从低电平到高电平，数字1对应信号从高电平到低电平。要点：中间跳变、同步信号，0低高、1高低(3)差分曼彻斯特编码：数字编码的一种方式，在非归零码码元的正中间时间出现了一次电平跳变，这样接收方可以将此作为同步信号。数字0的起始电平与前一数字的结尾电平相反，发生跳变，数字1的起始电平与前一数字的结尾电平一致。要点：曼彻斯特，0变1不变
信源编码种类及过程？
信源编码是指针对各种信息源及不同目的所进行的编码。
传统的信源编码主要考虑信息的表示，例如早期的莫尔斯电码、英文字符的ASCII编码等，主要完成英文信息的二进制表示。
现代数据通信系统中常见的信源编码大部分与数据 压缩有关，通过对原始数据的有损或无损压缩编码，可以极大地降低数据量，节省数据存储和传输的开销。
例如: 常用的无损压缩编码方式有Huffman的编码、算术编码、L-Z编码等；有损压缩编码方式有音乐的 MP3编码、视频流的H.264编码等。
此外，数据加密也可以是一类特殊的信源编码技术。
信源编码种类及过程？
三种编码方式：哈夫曼编码、LZ编码和算数编码。下面分析其各自基本原理。
1. 哈夫曼编码
哈夫曼编码是是一种可变长的分组编码，完全依据各字符出现的概率来构造码字。二进制的哈夫曼编码是基于二叉树的编码思想，所有可能的输入符号在哈夫曼树上对应为一个节点，结点的位置就是该符号的哈夫曼编码。为了构造出唯一可译码，这些节点都是哈夫曼树上的终极结点（即叶子结点），不再延伸，不会出现前缀码。具体编码方法如下：
将信源消息符号按其出现的概率大小依次排列为 p1≥p2≥…≥Pn；
取两个概率最小的字母分别配以 0 和 1 两个码元，并将这两个概率相加作为一个新字母的概率，与未分配二进制符号的字母一起重新排队；
对重排后的两个概率最小符号重复步骤2的过程；
不断继续上述过程，直到最后两个符号配以 0 和 1 为止；
从最后一级开始，向前返回得到各个信源符号所对应的码元序列，即为相应码字。
特别地，有时为了得到最短平均码长，尽量减少赋长码的信源符号，需要在编码前对信源符号作添加，使得信源的符号数量满足 M(N-1) 1，其中M为正整数，N为进制，这样在多次合并后就能充分利用短码，以便降低平均码长。
此外，哈夫曼编码方法所得到的码并非是唯一的，造成非唯一的原因如下：
每次对信源缩减时，赋予信源最后两个概率最小的符号，用0和1是可以任意的，所以可以得到不同的哈夫曼编码，但不会影响码字的长度。
对信源进行缩减时，两个概率最小的符号合并后的概率与其他信源符号的概率相同时，这两者在缩减信源中进行概率排序，其位置放置次序可以是任意的，故会得到不同的哈夫曼码。此时将影响码字的长度，一般将合并的概率放在上面，这样可以得到较小的码方差。
哈夫曼编码的特点：
哈夫曼码的编码方法保证了概率大的符号对应于短码，概率小的符号对应于长码，充分利用了短码；
而是缩减信源的最后二个码字总是最后一位不同，从而保证了哈夫曼码是即时码。
哈夫曼码的编码效率是非常高的，它可以单个信源符号编码或用L较小的信源序列编码，对编码器的设计来说也将简单得多。但是应当注意，要达到很高的效率仍然需要按长序列来计算，这样才能使平均码字长度降低。
哈夫曼编码的解码则在识别出一个个叶子结点后按照叶子结点对应的原信源符号译码。
哈夫曼编码虽然效率出众，但仍然存在一些分组码所具有但缺点。例如概率特性必须精确测定，以此来编织码表，若略有变化，还需要更换码表。故实际编码过程中需要对原始数据扫描两遍，第一遍用来统计原始数据中各字符出现的概率，创建码表存放起来，第二遍则依据码表在扫描的同时进行编码，才能传输信息。如果将这种编码放在网络通信中，两遍扫描会引起较大的时延；如果用于数据压缩，则会降低速度。因此，出现了自适应哈夫曼编码方法，其码表不是实现构造，而是随着编码的进行，不断动态构造、调整。
2. 算术编码
由于在使用分组码对信源单符号进行编码时，没有将符号间的相关性纳入考虑之中：若将m个符号合起来进行编码则会增加设备复杂度，且组间符号的相关性还是无法纳入考虑。这就使得信源编码的匹配原则不能充分满足，编码效率有所损失。
为了克服这种局限性，一种基于非分组码的编码方法——算数编码应运而生。编码的基本思路是：将需要编码的全部数据看成某一 L L L 长序列，所有可能出现的L长序列的概率映射到 [ 0 , 1 ] [0,1] [0,1] 的区间上，把 [ 0 , 1 ] [0,1] [0,1] 区间分成许多小段，每段长度等于某一序列的概率。再在段内取一个二进制小数用作码字，其长度可与该序列的概率匹配，达到高效率编码的目的。
算数编码实际的编译码过程比较复杂，但在性能上具有许多优点，特别是所需要的参数很少，不像哈夫曼编码那样需要一个很大的码表。从理论上说，只要已知信源符号集及其符号概率，算数编码的平均码长可以接近符号熵。
具体编码方法如下：
将文件以字节为单位读入，并将其分割成bit串形式
计算文件中bit0和bit1的总数量和各自的概率
对一定长度L的符号串进行编码，并将数据写入压缩后文件中
从压缩文件中读入数据，并还原成长度为L的符号串输入至解压文件中
3. LZ编码
LZ编码是由以色列研究者齐夫和伦佩尔完全脱离哈夫曼码和算术编码的设计思路，设计出的一系列比哈夫曼编码更有效、比算术编码更快捷的通用压缩算法。将这些算法统称为LZ系列算法。LZ系列算法利用一种巧妙的方式将字典技术应用于通用数据压缩领域，而且，可以从理论上证明LZ系列算法同样可以逼近信息熵的极限。
实验采用的 LZ-78编码 的编码过程如下：
设信源符号集 A = a 1 , a 2 , … , a K A={a1,a2,…,aK} A=a1,a2,…,aK 共K个符号，设输入信源符号序列为 U = ( u 1 , u 2 , … … , u L ) U=(u1,u2,……,uL) U=(u1,u2,……,uL)，编码是将此序列分成不同的段。
分解是迭代进行的，在第i步，编码器从 s i s_i s
i
\t
- 1 短语后的第一个符号开始向后搜索在此之前从未出现过的最短短语 s i s_i s
i
\t
，将短语 s i s_i s
i
\t
添入字典第i段。由于 s i s_i s
i
\t
是此时字典中最短的新短语，所以 s i s_i s
i
\t
在去掉最后一个符号 x x x 后所得的前缀必定是字典中之前已经出现过的。
若设此前缀是在第 j ( amplt i ) j(amplti) j(lti) 步时出现的，则对 s i s_i s
i
\t
的编码就可以利用 j j j 和 s i s_i s
i
\t
最后一位符号 x x x 来表示，即为码字 ( j , x ) (j,x) (j,x)。对于段号 j j j，最多需要 ⌈ l o g i ⌉ \\lceil logi \
ceil ⌈logi⌉ bit表示，而符号 x x x 只需 ⌈ l o g K ⌉ \\lceil logK \
ceil ⌈logK⌉ bit。若编码猴的字典中短语共有M(U)个，则U序列编码后输出的码流总长度为 ( ⌈ l o g i ⌉ ⌈ l o g K ⌉ ) (\\lceil logi \
ceil \\lceil logK \
ceil) (⌈logi⌉ ⌈logK⌉)。
LZ-78编码的核心实际上就是一个包含了短语、段号、码字、二进制码的字典，如下所示。
短语\t段号\t码字\t二进制码
a\t1\t(0,a)\t(0,0)
b\t2\t(0,b)\t(0,1)
ba\t3\t(2,a)\t(10,0)
baa\t4\t(3,a)\t(11,0)
…\t…\t…\t…
LZ编码的编码方法非常简捷，译码也很简单，可以一边译码一边建立字典。译码时若收到的码字为 ( j , x ) (j,x) (j,x)，则在字典中找到第 j j j 个短语，然后加上符号 x x x 即可译出对应的新短语，并添入字典。因此发送时无需传送字典本身。LZ算法的逻辑简单，硬件实现廉价，运算速度快，在很多计算机数据存储中得到应用。其优点在于能够有效利用信源输出序列的频率、重复性和高使用率的冗余度，是一种自适应算法，只需对信源序列进行一次扫描，无须知道信源的先验统计特性，运算时间正比于序列长度。但也有缺点，一是不能有效地利用位置的冗余度；二是该算法通常在序列起始段压缩效果差一些，随着长度增加效果变好。