組合數(shù)學(xué)應(yīng)用之光盤的通道編碼

1、組合數(shù)學(xué)應(yīng)用組合數(shù)學(xué)應(yīng)用 之光盤的通道編碼之光盤的通道編碼 報(bào)告人：報(bào)告人： 學(xué)號(hào)：學(xué)號(hào)： 時(shí)間：時(shí)間：2016.12.15 1、應(yīng)用背景 2、通道編碼及其原因 3、具體應(yīng)用 應(yīng)用背景 隨著電子計(jì)算機(jī)的發(fā)展普及，組合數(shù)學(xué)這門古老的 學(xué)科逐漸煥發(fā)出了蓬勃的生機(jī)。它是一門研究?jī)?nèi)容豐富， 應(yīng)用廣泛的學(xué)科。同時(shí)它也是一門比較講究方法科技的 學(xué)科。它的魅力在于能夠找到巧妙的解法去完善并解決 一個(gè)組合數(shù)學(xué)的問題。計(jì)算機(jī)強(qiáng)大的計(jì)算能力也為尋求 組合數(shù)學(xué)問題的巧妙解法提出了無限的可能，同時(shí)也反 過來有效地推動(dòng)了計(jì)算科學(xué)的發(fā)展。現(xiàn)代數(shù)學(xué)可以分為 兩大類：一類是研究連續(xù)性對(duì)象，如分析、方程等。另 一類就是就是研究

2、離散對(duì)象的組合數(shù)學(xué)，計(jì)算機(jī)科學(xué)就 是算法的科學(xué)，而計(jì)算機(jī)所處理的對(duì)象是離散的數(shù)據(jù)， 研究離散兌現(xiàn)的科學(xué)恰恰就是組合數(shù)學(xué)，因此，在信息 時(shí)代的今天，組合數(shù)學(xué)就是信息時(shí)代的數(shù)學(xué)。 應(yīng)用背景 說到計(jì)算機(jī)，無疑會(huì)涉及到存儲(chǔ)的問 題。CD-ROM 一種能夠存儲(chǔ)大量數(shù)據(jù) 的外部存儲(chǔ)媒體。所用存儲(chǔ)標(biāo)準(zhǔn)為CD- DA音頻存儲(chǔ)標(biāo)準(zhǔn)。在CD-DA中將聲音轉(zhuǎn) 換成用“0”和“1”表示的數(shù)字信號(hào)之后，并 不是把他們直接記錄到盤上。而是需要做 變換處理，這種處理統(tǒng)稱為通道編碼。 為什么要做通道編碼 為什么要 把8位轉(zhuǎn)換成14位，而不是13，15 或16位 CD-ROM簡(jiǎn)介 CD-ROM，即光盤只讀存儲(chǔ)器，它是一種 能夠

3、存儲(chǔ)大量數(shù)據(jù)的外部存儲(chǔ)媒體，一張壓縮 光盤的直徑大約是4.5in，0.125in厚，能容納 約660M的數(shù)據(jù)。所有的CD-ROM盤都是用一 張母盤壓制而成，然后封裝到聚碳酸酯的保護(hù) 外殼里的。記錄在在母盤上的數(shù)據(jù)呈螺旋狀， 由中心向外散開，磁盤表面有許許多多微笑的 坑，那就是記錄的數(shù)字信息。讀CD-ROM上的 數(shù)據(jù)時(shí)，利用激光束掃描光盤，根據(jù)激光在小 坑上的反射變化得到數(shù)字信息。 通道編碼的原因 數(shù)字記錄中要做通道編碼的主要原因有兩個(gè)，一是 為了改善讀出信號(hào)的質(zhì)量，二是為了在記錄信號(hào)中提取 同步信號(hào)。例如，有連續(xù)多個(gè)字節(jié)的全“0”信號(hào)或者全 “1”信號(hào)要記錄到盤上，如果不做通道編碼就把他們記

4、錄到盤上，讀出時(shí)的信號(hào)就是一條直線，電子線路很難 區(qū)分有多少個(gè)“0”或者多少個(gè)“1”。通俗來說，通道編碼 實(shí)際上就是要在連續(xù)的“0”中插入若干個(gè)“1”，而在連續(xù) 的“1”中插入若干個(gè)“0”；并對(duì)“0”和“1”的連續(xù)長度數(shù)目即 “游程長度”加以限制。 通道編碼的原因 理論分析和實(shí)踐證明，根據(jù)20世紀(jì)70年代的 技術(shù)水平，把“0”的游程長度最短限制在兩個(gè)，最 長限制在10個(gè)，光盤上的信號(hào)就能可靠讀出。這 條規(guī)則的意思就是，兩個(gè)“1”之間最少要有兩個(gè)“0”； 且最多不超過10個(gè)“0”；那么一個(gè)字節(jié)的數(shù)據(jù)，在 光盤上需要多少位才能正確表示呢？接下來就要 用到我們的組合數(shù)學(xué)的知識(shí)了，我們來用組合數(shù) 學(xué)來

5、具體分析一下為何要把8位數(shù)據(jù)轉(zhuǎn)換成14位呢？ 具體應(yīng)用 假設(shè)我們要求的位數(shù)為n位，顯然n8,?，F(xiàn)在我們考慮求這樣 的n的最小值。 我們首先只考慮滿足任意兩個(gè)“1”之間至少要有兩個(gè)“0”的條件 下的數(shù)據(jù)位數(shù)n。 對(duì)于一個(gè)固定的k=2,我們現(xiàn)在求恰好包含k個(gè)“1”并滿足任意 兩個(gè)“1”之間至少要有兩個(gè)“0”這樣的n位數(shù)的個(gè)數(shù)。首先把k個(gè) “1”安排成一排，由于要求任意兩個(gè)“1”之間至少要有兩個(gè)“0”； 因此在這k個(gè)“1”之間的k-1歌空位上共放2（k-1）個(gè)“0”，每個(gè) 空位上正好放兩個(gè)“0”；然后把剩下的n-3k+2個(gè)“0”任意放到 k+1個(gè)位置上，每個(gè)位置放“0”的個(gè)數(shù)不限。可知該種安排的個(gè)

6、數(shù)為F（k+1，n-3k+2)= = 注：F(n,r)= 23 22 kn kn k kn22 r rn1 具體應(yīng)用 同時(shí)上述過程也表明n-3k+2=0;即1的個(gè)數(shù)k必須滿足k=（n+2)/3. 當(dāng)k=1時(shí)，容易知道，滿足任意兩個(gè)“1”之間至少要有兩個(gè)“0”這樣的n 位數(shù)共有n個(gè)（“1”在n個(gè)位置中隨便選一個(gè)）。 對(duì)于各位全是“0”的n位數(shù)顯然只有1個(gè)。 因此滿足任意兩個(gè)“1”之間至少要有兩個(gè)“0”這樣的n位數(shù) 的個(gè)數(shù)為 上式中每一項(xiàng)都應(yīng)該=256(8位二進(jìn)制數(shù)的個(gè)數(shù))。對(duì)于k=3時(shí)，由 上式得出n256，因此 n=15. 3/ )2( 0 22 n k k kn 3 23*2n 2 22*2

7、n 具體應(yīng)用 如果n=15，容易計(jì)算得到 =21+126+165+78+15+1=406； 406還是大于256. 如果n=14；容易得到 =6+70+120+66+14+1=277 277已經(jīng)和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 具體應(yīng)用 對(duì)于n=14，現(xiàn)在加上兩個(gè)“1”之間最多不超過10個(gè)“0”的條件。 （1）當(dāng)各位全是“0”時(shí)，不滿足要求。 （2）當(dāng)只有1位為“1”時(shí)，余下13位全為“0”時(shí)。13個(gè)“0”全在“1” 的左邊

8、或右邊，兩種情況都不滿足要求，“1”的左邊有一個(gè)“0” 且右邊有12個(gè)“0”或者“1”的右邊有一個(gè)“0”且左邊有12個(gè)“0”這 兩種情況也不滿足要求。類似地，“1”的左邊有兩個(gè)“0”且右邊 有11個(gè)“0”或者“1”的左邊有11個(gè)“0”且右邊有兩個(gè)“0”這兩種情況 也不滿足要求。于是有6種情況需要排除。 具體應(yīng)用 對(duì)于n=14，現(xiàn)在加上兩個(gè)“1”之間最多不超過 10個(gè)“0”的條件。 （3）當(dāng)只有兩位為“1”時(shí)，余下12位全是“0”時(shí)。 由于兩個(gè)“1”之間必須有兩個(gè)“0”，現(xiàn)在考慮剩 下的10個(gè)“0”的安排情況。 如果這10個(gè)“0”全放在兩個(gè)“1”之間，顯然不滿 足要求。如果這10個(gè)“0”中有9個(gè)放在兩個(gè)“1”之 間，剩下的1個(gè)“0”放在最左邊或最右邊，這兩 種情況也不滿足要去。于是又有三種情況需要 排除。 具體應(yīng)用 對(duì)于n=14，現(xiàn)在加上兩個(gè)“1”之間最多不超過 10個(gè)“0”的條件。 （4）當(dāng)“1”的位數(shù)大于等于3時(shí)，就不存在兩 個(gè)“1”之間存在超過10個(gè)“0”的可能了 綜上所述：滿足兩個(gè)“1”之間至少要有兩個(gè)“0” 且最多不超過10個(gè)“0”的14位數(shù)共有277-1-6- 3=267種，即8位的數(shù)據(jù)至少應(yīng)該用14位才能 有效表示。 具體應(yīng)用 我們知道，8位數(shù)據(jù)有256種代碼，1