组合数学应用之光盘的通道编码

1、组合数学应用组合数学应用 之光盘的通道编码之光盘的通道编码 报告人：报告人： 学号：学号： 时间：时间：2016.12.15 1、应用背景 2、通道编码及其原因 3、具体应用 应用背景 随着电子计算机的发展普及，组合数学这门古老的 学科逐渐焕发出了蓬勃的生机。它是一门研究内容丰富， 应用广泛的学科。同时它也是一门比较讲究方法科技的 学科。它的魅力在于能够找到巧妙的解法去完善并解决 一个组合数学的问题。计算机强大的计算能力也为寻求 组合数学问题的巧妙解法提出了无限的可能，同时也反 过来有效地推动了计算科学的发展。现代数学可以分为 两大类：一类是研究连续性对象，如分析、方程等。另 一类就是就是研究

2、离散对象的组合数学，计算机科学就 是算法的科学，而计算机所处理的对象是离散的数据， 研究离散兑现的科学恰恰就是组合数学，因此，在信息 时代的今天，组合数学就是信息时代的数学。 应用背景 说到计算机，无疑会涉及到存储的问 题。CD-ROM 一种能够存储大量数据 的外部存储媒体。所用存储标准为CD- DA音频存储标准。在CD-DA中将声音转 换成用“0”和“1”表示的数字信号之后，并 不是把他们直接记录到盘上。而是需要做 变换处理，这种处理统称为通道编码。 为什么要做通道编码 为什么要 把8位转换成14位，而不是13，15 或16位 CD-ROM简介 CD-ROM，即光盘只读存储器，它是一种 能够

3、存储大量数据的外部存储媒体，一张压缩 光盘的直径大约是4.5in，0.125in厚，能容纳 约660M的数据。所有的CD-ROM盘都是用一 张母盘压制而成，然后封装到聚碳酸酯的保护 外壳里的。记录在在母盘上的数据呈螺旋状， 由中心向外散开，磁盘表面有许许多多微笑的 坑，那就是记录的数字信息。读CD-ROM上的 数据时，利用激光束扫描光盘，根据激光在小 坑上的反射变化得到数字信息。 通道编码的原因 数字记录中要做通道编码的主要原因有两个，一是 为了改善读出信号的质量，二是为了在记录信号中提取 同步信号。例如，有连续多个字节的全“0”信号或者全 “1”信号要记录到盘上，如果不做通道编码就把他们记

4、录到盘上，读出时的信号就是一条直线，电子线路很难 区分有多少个“0”或者多少个“1”。通俗来说，通道编码 实际上就是要在连续的“0”中插入若干个“1”，而在连续 的“1”中插入若干个“0”；并对“0”和“1”的连续长度数目即 “游程长度”加以限制。 通道编码的原因 理论分析和实践证明，根据20世纪70年代的 技术水平，把“0”的游程长度最短限制在两个，最 长限制在10个，光盘上的信号就能可靠读出。这 条规则的意思就是，两个“1”之间最少要有两个“0”； 且最多不超过10个“0”；那么一个字节的数据，在 光盘上需要多少位才能正确表示呢？接下来就要 用到我们的组合数学的知识了，我们来用组合数 学来

5、具体分析一下为何要把8位数据转换成14位呢？ 具体应用 假设我们要求的位数为n位，显然n8,。现在我们考虑求这样 的n的最小值。 我们首先只考虑满足任意两个“1”之间至少要有两个“0”的条件 下的数据位数n。 对于一个固定的k=2,我们现在求恰好包含k个“1”并满足任意 两个“1”之间至少要有两个“0”这样的n位数的个数。首先把k个 “1”安排成一排，由于要求任意两个“1”之间至少要有两个“0”； 因此在这k个“1”之间的k-1歌空位上共放2（k-1）个“0”，每个 空位上正好放两个“0”；然后把剩下的n-3k+2个“0”任意放到 k+1个位置上，每个位置放“0”的个数不限。可知该种安排的个

6、数为F（k+1，n-3k+2)= = 注：F(n,r)= 23 22 kn kn k kn22 r rn1 具体应用 同时上述过程也表明n-3k+2=0;即1的个数k必须满足k=（n+2)/3. 当k=1时，容易知道，满足任意两个“1”之间至少要有两个“0”这样的n 位数共有n个（“1”在n个位置中随便选一个）。 对于各位全是“0”的n位数显然只有1个。 因此满足任意两个“1”之间至少要有两个“0”这样的n位数 的个数为 上式中每一项都应该=256(8位二进制数的个数)。对于k=3时，由 上式得出n256，因此 n=15. 3/ )2( 0 22 n k k kn 3 23*2n 2 22*2

7、n 具体应用 如果n=15，容易计算得到 =21+126+165+78+15+1=406； 406还是大于256. 如果n=14；容易得到 =6+70+120+66+14+1=277 277已经和256非常接近了。 如果n=13，容易求得 =189，显然不满足要求。 3/ )215( 0 2215 k k k 3/ )214( 0 2214 k k k 3/ )213( 0 2213 k k k 具体应用 对于n=14，现在加上两个“1”之间最多不超过10个“0”的条件。 （1）当各位全是“0”时，不满足要求。 （2）当只有1位为“1”时，余下13位全为“0”时。13个“0”全在“1” 的左边

8、或右边，两种情况都不满足要求，“1”的左边有一个“0” 且右边有12个“0”或者“1”的右边有一个“0”且左边有12个“0”这 两种情况也不满足要求。类似地，“1”的左边有两个“0”且右边 有11个“0”或者“1”的左边有11个“0”且右边有两个“0”这两种情况 也不满足要求。于是有6种情况需要排除。 具体应用 对于n=14，现在加上两个“1”之间最多不超过 10个“0”的条件。 （3）当只有两位为“1”时，余下12位全是“0”时。 由于两个“1”之间必须有两个“0”，现在考虑剩 下的10个“0”的安排情况。 如果这10个“0”全放在两个“1”之间，显然不满 足要求。如果这10个“0”中有9个放在两个“1”之 间，剩下的1个“0”放在最左边或最右边，这两 种情况也不满足要去。于是又有三种情况需要 排除。 具体应用 对于n=14，现在加上两个“1”之间最多不超过 10个“0”的条件。 （4）当“1”的位数大于等于3时，就不存在两 个“1”之间存在超过10个“0”的可能了 综上所述：满足两个“1”之间至少要有两个“0” 且最多不超过10个“0”的14位数共有277-1-6- 3=267种，即8位的数据至少应该用14位才能 有效表示。 具体应用 我们知道，8位数据有256种代码，1