義 守 大 學(xué) 資 訊 管 理 研 究 所 碩 士 論 文 應(yīng)用快速 之研究 A S 究 生：李俊明 指導(dǎo)教授：陳孟峰 博士 共同指導(dǎo)教授：王隆仁 博士 中華民國(guó) 九十二 年 六 月 - 1 - 應(yīng)用快速 研究生：李俊明 指導(dǎo)教授：王隆仁 義守大學(xué)資訊管理所 摘要 本論文 提出運(yùn)用 然 處理工具，例如：重新同步 (資料分割 (資料恢復(fù) (可逆式變長(zhǎng)度碼 (蓋錯(cuò) (及檔頭延伸碼 (技術(shù)，但是這些方法在檢測(cè)到錯(cuò)誤資料后，都只在處理如何減少錯(cuò)誤資料的移除量，避免將整個(gè)資料移除，但是對(duì)于錯(cuò)誤的資料并無法進(jìn)一步做資料更正。 而 對(duì)于多重的錯(cuò)誤具有相當(dāng)高的偵測(cè)及更正能力，目前已被應(yīng)用在許多的系統(tǒng)上，包括： (1)資料儲(chǔ)存設(shè)備 (例如：磁帶 ( 條碼 ( (2)無線或移動(dòng)通訊 (，例如：數(shù)位細(xì)胞式行動(dòng)電話 (微波通訊 (3)衛(wèi)星通訊 ( (4)數(shù)位電視 (以及 (5)高速數(shù)據(jù)機(jī) (例如：非對(duì)稱式數(shù)位回路系統(tǒng) (由此可見，如果能將 ，應(yīng)用到 低位元率影音編碼的資料傳輸上，勢(shì)必大幅提高 因此，本論文研究發(fā)現(xiàn)以質(zhì)因數(shù)計(jì)算的 算法可以用于 計(jì)算 )2( )12( m 點(diǎn)轉(zhuǎn)換 (其中 104 m )，而且這種 且，若將此快速 2 - 法，運(yùn)用在 容錯(cuò)技術(shù)上， 可以改善傳統(tǒng) 容錯(cuò)技術(shù)，且非常適用于 極低位元率影音編碼的資料傳輸。 關(guān)鍵詞： 容錯(cuò)度 ( 3 - A S i a to be as of of as in to in 1) as 2) or as 3) 4) ) as if be it a In it is be to 2( 04 m . is - 4 - It is by a - 5 - 目錄索引 中文摘要 1 英文摘要 3 目錄 5 第一章 緒言 6 1 7 1 9 1 10 第二章 10 2 10 2 12 2 12 第三章 14 3 14 3 16 3 18 第四章 算法 22 4散傅立葉轉(zhuǎn)換 22 - 6 - 4速傅立葉轉(zhuǎn)換 23 4 28 第五章 43 5 43 5 44 第六章 實(shí)驗(yàn)結(jié)果 46 第七章 結(jié)論與未來研究 59 參考文獻(xiàn) 60 - 7 - 第一章 緒言 1究背景 由于傳統(tǒng)的影音媒體被數(shù)位化成數(shù)位資料后，其資料量將極為龐大，相對(duì)地也需要相當(dāng)大容量的記憶體空間來儲(chǔ)存，然而目前一般電腦的儲(chǔ)存記憶體都不能滿足這種需求。而且在現(xiàn)有的通訊網(wǎng)路上傳遞這些影音數(shù)位資料，也會(huì)造成網(wǎng)路塞車、傳輸太慢等的問題。因此，如何在可接受的程度下，減少這些影音數(shù)位資料量，在現(xiàn)在及未來的影音媒體之播映、通訊及存錄上，其重要程度日益升高，于是數(shù)位影音壓縮技術(shù)便愈見其重要性 1。根據(jù)估算解析度為 1280 720 60的高畫質(zhì)電視 (2，若不經(jīng)數(shù)位影音壓縮編碼技術(shù)的 處理，所需的儲(chǔ)存容量將高達(dá) 9492鐘，但是在 200 倍壓縮率的數(shù)位影音壓縮編碼技術(shù)下，只需要 47鐘的儲(chǔ)存空間，所需的儲(chǔ)存空間只需原來的 200分之 1，由此可見數(shù)位影音壓縮編碼技術(shù)的重要性。 數(shù)位影音壓縮編碼技術(shù)，早在 1984年就開始討論，目前并以 準(zhǔn) 3-17最被廣泛采用。 下，所制定用來壓縮影音的編碼標(biāo)準(zhǔn)，由數(shù)位儲(chǔ)存媒體(18專用的 直發(fā)展到用于高畫質(zhì)電視系統(tǒng) (數(shù)位影音光碟 (19，與高品質(zhì)通訊網(wǎng)路影音服務(wù)專用的 轉(zhuǎn)往處理多媒體方面發(fā)展，并提出 剛開始進(jìn)行制定標(biāo)準(zhǔn)時(shí)，被命名為”極低位元率下的影音編碼”(后來才改名為”影音物件編碼” (成為多媒體物件的編碼標(biāo)準(zhǔn) 。也就是說，數(shù)位電視和電影的視訊與音訊資料、互動(dòng)式多媒體和無線通訊網(wǎng)路，都是 應(yīng)用極低位元率影音編碼的行動(dòng)多媒體，是 最初目的，此技術(shù)可以提供筆記型電腦、個(gè)人數(shù)位助理 (行動(dòng)電話，可以透過移動(dòng)體無線通訊網(wǎng)路技術(shù)，接收多媒體的影音數(shù)位資料。但是由于移動(dòng) - 8 - 體無線通訊網(wǎng)路技術(shù)，需要提高數(shù)位資料編碼效率，而很容易在數(shù)位資料傳送時(shí)發(fā)生錯(cuò)誤，所以對(duì)于傳送資料的容錯(cuò)度 (是一個(gè)必須慎重考慮的重要問題。 因此，如何解決數(shù)位資料在傳送及接收時(shí)，因雜訊所造成的錯(cuò)誤，將是一個(gè)極為重要的課題 17。 為了對(duì)付無線通訊網(wǎng)路中惡劣的傳輸環(huán)境以及移動(dòng)體可能的高速移動(dòng)，常常會(huì)使用上錯(cuò)誤更正碼 (技術(shù)，才不至于通訊品質(zhì)低落或是斷訊連連。換句話說，為了保證數(shù)位資料的正確性，通常數(shù)位化的資料還要再加入錯(cuò)誤更正碼，在原本的資料以外，再加入一些額外的資料以提高傳送的正確性。而為了提高通訊的正確性，最簡(jiǎn)單的方法，就是將每筆資料傳送兩次，或是在資料發(fā)生錯(cuò)誤時(shí)，將該筆資料一直重復(fù)傳送，直到接收 端接收正確為止。但是將資料重復(fù)傳送，不僅需要更多的傳送時(shí)間，亦浪費(fèi)了比較多的頻寬。為了更有效率的處理通訊所造成的錯(cuò)誤，就是利用錯(cuò)誤更正碼的技術(shù)，此技術(shù)是利用復(fù)雜的數(shù)學(xué)來產(chǎn)生一些額外的編碼資料，并置放在資料的適當(dāng)位置，當(dāng)資料發(fā)生錯(cuò)誤時(shí)，就可以利用此解碼技術(shù)，將錯(cuò)誤資料找出并予以更正。何況這種技術(shù)對(duì)于壓縮過的資料更是重要，因?yàn)閴嚎s后的資料若發(fā)生錯(cuò)誤，可能會(huì)造成整筆資料的不同。這就像有些衛(wèi)星電視臺(tái)，因?yàn)槔脭?shù)位資料傳送，在天候不佳時(shí)，時(shí)常會(huì)發(fā)現(xiàn)電視螢?zāi)簧系挠跋褡兂梢粋€(gè)個(gè)的方塊。 通常錯(cuò)誤更正碼大致可以分為兩類：一 類是區(qū)塊碼 (其使用的方法是一次編碼許多資料，但是編碼過程不影響以后的資料，也就是不具有時(shí)間相關(guān)性；另一類是回旋碼 (其編碼的過程是具有時(shí)間相關(guān)性的。這兩種編碼方式各有其長(zhǎng)處，區(qū)塊碼中最常用的循環(huán)碼 ( 及 而 (為一種回旋碼。這些錯(cuò)誤更正碼中，著名的S)碼已是數(shù)位通訊與資料儲(chǔ)存系統(tǒng)上廣泛被采用的一種錯(cuò)誤更正碼，它對(duì)于多重的錯(cuò)誤具有相當(dāng)高的偵測(cè)及更正能力 20。如再配合其他編碼技巧，例如串接或交錯(cuò)，其能力更可進(jìn)一步提升，以便應(yīng)用在 低位 - 9 - 元率影音編碼的資料傳輸上，提高數(shù)位資料通訊的容錯(cuò)度 ( 1究動(dòng)機(jī)與目的 筆記型電腦、個(gè)人數(shù)位助理和行動(dòng)電話等移動(dòng)體的無線通訊，在這個(gè)應(yīng)用領(lǐng)域，大量的影音數(shù)位資料利用 極低位元率編碼后，經(jīng)由無線通訊傳送給 接收端的移動(dòng)體，這個(gè)過程很容易發(fā)生資料傳送的錯(cuò)誤，所以對(duì)于數(shù)位資料的容錯(cuò)度 (要特別重視。雖然 提出了一些針對(duì)低位元率容錯(cuò)度的處理工具，例如：重新同步(資料分割 (資料恢復(fù) (可逆式變長(zhǎng)度碼 (蓋錯(cuò) (及檔頭延伸碼 (技術(shù) 17，但是這些方法技術(shù)在檢測(cè)到錯(cuò)誤資料后，都只是在如何減少錯(cuò)誤資料的移除量，對(duì)于錯(cuò)誤的資料并無法更正。 而 (被證實(shí)是一種功能強(qiáng)大的錯(cuò)誤更正碼，它對(duì)于多重的錯(cuò)誤具有相當(dāng)高的偵測(cè)及更正能力，目前已被應(yīng)用在許多的系統(tǒng)上，包括： (1)資料儲(chǔ)存設(shè)備 (例如：磁帶 ( 條碼 ( (2)無線或移動(dòng)通訊 (，例如：數(shù)位細(xì)胞式行動(dòng)電話 (微波通訊( (3)衛(wèi)星通訊 ( (4)數(shù)位電視 (以及 (5)高速數(shù)據(jù)機(jī) (例如：非對(duì)稱式數(shù)位回路系統(tǒng) (由此可見，如果能將 及更正能力，應(yīng)用到 低位元率影音編碼的資料傳輸上，勢(shì)必大幅提高 能。因此，為了滿足 應(yīng)用 功能，以適用于極低位元率影音編 - 10 - 碼的資料傳輸，并期望以加入少許冗余資料量而大幅提升 論文所采用的 55, 223)編碼式依據(jù)美國(guó)太空總署 (碼標(biāo)準(zhǔn)所修改而成，此標(biāo)準(zhǔn)為應(yīng)用于衛(wèi)星與太空通訊 33。 1文架構(gòu) 本論文架構(gòu)為第一章緒論說明研究的背景、動(dòng)機(jī)與目的；第二章探討目前用三小節(jié)描述 重新同步 (資料恢復(fù) (蓋錯(cuò) (三種方法； 第三章介紹 333四章介紹 五章說明本論文所使用的55六章利用電腦模擬觀察實(shí)驗(yàn)結(jié)果，第七章為結(jié)論及未來研究方向。 - 11 - 第二章 目前 面的處理，大致可以分成重新同步 (資料恢復(fù) (蓋錯(cuò) (三種方法 17,21-24，茲說明如下： 2新同步 (以壓縮的視訊為例，當(dāng)傳送壓縮視訊經(jīng)過有雜訊的通訊頻道時(shí)，錯(cuò)誤 (會(huì)被置入數(shù)位資料流 (。視訊解碼器 (對(duì)損壞的資料流進(jìn)行解碼，因?yàn)椴荒芫_定義出目前資料是屬于視訊的哪一部分，而與編碼器(去同步 (因此如果沒有使用矯正的方法，則經(jīng)解碼后的視訊品質(zhì)會(huì)迅速降低，而且很快地全部的視訊資料都不正確。有一個(gè)解決方法就是編碼器在資料流的幾個(gè)地方置入重新同步的記號(hào) (如圖 2示。當(dāng)解碼器在檢查出有錯(cuò)誤后，它可以隨后取得重新同步記號(hào)而恢復(fù)其同步。 圖 2碼器沒有限制重新同步記號(hào)只能置放在每一列巨集區(qū)塊(開端。編碼器可以有選擇的將影像分割到視訊封包內(nèi)。每一個(gè)視訊封包是由數(shù)個(gè)連續(xù)的巨集區(qū)塊所組成。這些巨集區(qū)塊可以在視訊中延展成多列的形式也可以只是部分被包含。一種 碼器的建議操作模式，就是每隔 k 位元 (期性地將重新同步 記號(hào)置入。當(dāng)視訊的一個(gè)部分包含了重要的資料，則巨集區(qū)塊相對(duì)應(yīng)于這個(gè)區(qū)域就會(huì)產(chǎn)生比視訊中的其他區(qū)域更多的位元?，F(xiàn)在，如果 碼器將重新同步記號(hào)以同樣的位元間隔置入 (可以為 512位元 )，則在重要區(qū)域的重新同步記號(hào)之間的巨集間隔會(huì)比較小，而在不重要區(qū) - 12 - 域的間隔則會(huì)比較大。因此，當(dāng)短暫的突現(xiàn)錯(cuò)誤產(chǎn)生，解碼器可以迅速地將視訊中重要的區(qū)域內(nèi)包含錯(cuò)誤的巨集區(qū)塊集中，并且維護(hù)重要區(qū)域的視訊品質(zhì)。 另外，資料分割 (于一種比較進(jìn)階的方法，在資料流中發(fā)現(xiàn)錯(cuò)誤并且以下一個(gè)重新同步記號(hào)再 同步之后，解碼器會(huì)將兩個(gè)重新同步記號(hào)之間含有錯(cuò)誤資料的巨集區(qū)塊隔離。如圖 2是一種資料分割的方法，其將移動(dòng)及巨集區(qū)塊標(biāo)頭 ( 資料與畫質(zhì)資料 (開，并且在其間插入一個(gè)第二同步記號(hào)，即移動(dòng)記號(hào) (如果畫質(zhì)資料遺失，則利用移動(dòng)資料來隱藏這些錯(cuò)誤。也就是說，由于錯(cuò)誤的畫質(zhì)資料被拋棄，就使用前一畫面作移動(dòng)補(bǔ)償 ( 圖 2料恢復(fù) (根據(jù)前述 ， 傳送壓縮影音經(jīng)過有錯(cuò)誤可能的頻道會(huì)有一個(gè)問題 ， 就是使用可逆式變長(zhǎng)度碼 (在解碼處理的過程中，如果當(dāng)解碼器在解讀變長(zhǎng)度碼 (據(jù)資料時(shí)發(fā)現(xiàn)錯(cuò)誤就會(huì)失去同步，并且依照慣例地將下一個(gè)重新同步點(diǎn)之前的資料移除。使用可逆式變長(zhǎng)度碼 (以緩和這個(gè)問題，并且使解碼器可以更有效率的隔離錯(cuò)誤區(qū)域。也就 是說，這種可逆式變長(zhǎng)度碼 (一種特殊的變長(zhǎng)度碼 (其字首代表可以正向與反向的意思，它可以從正、反兩個(gè)方向進(jìn)行解碼。其優(yōu)點(diǎn)是當(dāng)解碼器從正向進(jìn)行解碼而發(fā)現(xiàn)錯(cuò)誤時(shí)，它會(huì)跳到下一個(gè)重新同步記號(hào)并進(jìn)行反向解碼，直到又發(fā)現(xiàn)錯(cuò)誤為止，如圖 2時(shí)解碼器會(huì)嘗試將兩個(gè)錯(cuò)誤位置之間的資料進(jìn)行恢復(fù)，如果失敗就只要將兩個(gè)錯(cuò)誤之間的資料移除，而不是將兩個(gè)重新同步記號(hào)的資料移除。因此，善加利用可逆式變長(zhǎng)度碼 (術(shù)， - 13 - 可以提高資料復(fù)原的比例。 圖 2錯(cuò) (蓋錯(cuò)是極為重要的技術(shù)，在采取資料恢復(fù)方法之后，還需要對(duì)那些無法恢復(fù)的錯(cuò)誤資料做一些處理，也就是如何把錯(cuò)誤的資料隱藏起來，讓那些錯(cuò)誤不會(huì)太明顯。目前 低位元率下，對(duì)錯(cuò)誤資料的處理方式是使用蓋錯(cuò)的方法，此方法十分簡(jiǎn)單，就是直接復(fù)制前一個(gè)畫面來取代有錯(cuò)誤的畫面，亦如前面資料分割 (述，這樣因?yàn)榍昂髢蓚€(gè)畫面基本上的差距不會(huì)太大，所以方法雖簡(jiǎn)單但效果也不錯(cuò)。 另外，因?yàn)闄n頭資料所包含的資訊是有關(guān)于影音資料的規(guī)格大小，以及 解碼與影音有關(guān)的 有影音物件所使用的編碼方式。如果這些資訊因?yàn)轭l道的雜訊而受到干擾，解碼器將因?yàn)闆]有其他的參考依據(jù)，只好將屬于這些資訊的影音全部移除。為了減低這方面錯(cuò)誤所造成的損失， 構(gòu)引入，亦如圖 1所示。在每個(gè)影音封包中會(huì)使用一個(gè) 1位元的欄位來當(dāng)作 果這個(gè)位元被設(shè)定，則描述影音視訊的重要檔頭資訊會(huì)在影音封包中一直被重復(fù)。如果影音資料的檔頭受到干擾，解碼器仍然可以使用影音封包中的檔頭資 訊對(duì)影音資料的其余資料進(jìn)行解碼。在 可以發(fā)現(xiàn)，使用 且可以幫助獲得更高的整體影音解碼品質(zhì)。 - 14 - 第三章 是由 I. S. . 960年首先提出來的。它在計(jì)算機(jī)糾錯(cuò)系統(tǒng)，特別是儲(chǔ)存系統(tǒng)如：光碟 (磁碟、磁帶中用的很普遍，并 已廣泛使用在多媒體通訊上 33。RS 用不同的解碼演算法除錯(cuò)，例如 可除兩個(gè)未知錯(cuò)或四個(gè)已知錯(cuò)； 下為其應(yīng)用的范圍： 儲(chǔ)存裝置 ( 無線電、行動(dòng)電話及微波 (or 衛(wèi)星通訊 ( 數(shù) 位電視 ( 高速電話線傳輸 (RS 如 后將如同元件般直接叫入使用，這意味著解碼器 (編碼器復(fù)雜且慢，所以如何提升解碼器的速度，就變成非常重要的主題 25,34。 3S 學(xué)定義 在實(shí)現(xiàn) RS 35，須先決定 抗未知錯(cuò)數(shù) t (抗 t 個(gè) 因而需要 2此外，假設(shè)每筆資料 (位元數(shù)為 m，則構(gòu)成一個(gè)，因此一組 包括冗余資料 )最多為12 根據(jù)以上所述，一組 為 k=此可定義 n, k)， t，其代表 為了抗最多 附加 2共 此計(jì) - 15 - 算資料比率 (此可知， 為了具備較好的抗錯(cuò)能力而選擇較大的 而造成 一組 會(huì)降低傳輸率 (造成不良之影響。 然而在某些應(yīng)用情況下，位元數(shù)為 m，但 不如上述定義之 12 大。此時(shí)需以 較大的 用較短的 例說明：當(dāng)決定的抗錯(cuò)力是解兩個(gè) 知錯(cuò) )或是一個(gè) 此設(shè)計(jì)為運(yùn)用兩筆冗余資料的 RS 是為了配合電腦資料表示及傳遞規(guī)格，所采用的位元數(shù)為 m=8 (8 位元 )，故一組 個(gè) 時(shí)，如果 55的話，就必須利用 大小。 RS 要先了解其乘法 25及加法的意義及動(dòng)作原理，則可開始了解 RS 上述定義位元數(shù) 根據(jù) 便產(chǎn)生 的主要元素 (作為日后編碼或解碼用。關(guān)于 子 。因此令 m=8，使用的 1)( 2348 式中 ”+” 號(hào)為 代表 上式代入值使得 p( )=0，可找出所有 82 )的元素，并建立一個(gè)元素表，此表為以后編碼或解碼時(shí)所使用的元素值，如表 3 - 16 - 表 3初始元素表 3依據(jù)上一節(jié)的 RS F( 82 )之后，便可根據(jù)定義及所產(chǎn)生的元素表，進(jìn)行 加及乘的運(yùn)算，進(jìn)行資料編碼。 首先，計(jì)算 tj 1 )()( 其中 式最高項(xiàng)為 2t (g(x)=2t)。將原始資料以多項(xiàng)式系數(shù) (式表示，并標(biāo)示為I(x)=(1,I 編碼動(dòng)作可表示為求取余數(shù)： )()( g(x) 此式中由于 g(x)的最高項(xiàng)為 2t，故 d(x)的最高項(xiàng)必小于 2t。 上 式所得之結(jié)果 d(x)便是編碼所產(chǎn)生之冗余資料，將其與原始資料一同儲(chǔ)存，故編碼結(jié)果可表示為： )()()()()( 2 t - 17 - 由此式可知，編碼結(jié)果 C(x)必可被 g(x)整除，如此據(jù)以抗錯(cuò)及解錯(cuò)。編碼器示意圖如圖 3 圖 3圖中可看出 S (n, k)編碼器編碼后，輸出為 n=k+2t。若編碼后的資料在傳送過程中出錯(cuò)，其錯(cuò)誤模型可表示為 e(x)，則接收端所收到的資料 (表示為： r(x)=C(x)+e(x) m(x)g(x) 若錯(cuò)誤的數(shù)量在解錯(cuò)的范圍內(nèi)，仍可根據(jù) C(x)所含之資訊解錯(cuò)。 圖 3編碼器示意圖 圖 3為兩筆冗余資料的編碼器。右邊為原始資料輸 - 18 - 入，左邊為編碼后資料輸出。圖中 待 果存放于兩個(gè) 由控制器 (制，先將原始資料輸出，再將編碼所產(chǎn)生之冗余資料尾隨原始資料之后輸出，形成一組連續(xù)的資料序列。 3編碼器如上一節(jié)所述，理論的主要部分為取余數(shù)運(yùn)算，較簡(jiǎn)單且容易實(shí)現(xiàn) ，但解碼器與編碼器相反，其解碼步驟較多，硬體也復(fù)雜些。本節(jié)所述之解碼器的輸入資料必須為上一節(jié)編碼器編碼過的資料，若使用不同解碼器，則必須用不同的編碼器編碼。解碼示意圖如下圖 3 圖 3解碼示意圖 解碼器的輸入資料用 r(x)表示，其可能是已經(jīng)出錯(cuò)的資料。輸入為 過解碼器計(jì)算后，輸出亦為 出資料則用 C(x)表示，與編碼過的資料表示法相同。這代表原始資料經(jīng)編碼后儲(chǔ)存，爾后再讀出時(shí)卻可能已經(jīng)出錯(cuò)，但經(jīng)解碼器運(yùn)算后，錯(cuò)誤的部份將會(huì)被更正。只需將冗余資料去除掉，便為正確之原始資 料。 然而若要解已知錯(cuò) (則必須外界提供錯(cuò)誤位于何處之額外資訊。用 - 19 - j，則已知錯(cuò)誤位置的資訊可表示為： ti j 1 )1()( 此式為 表已知錯(cuò)位置， 0j碼器所接收到的資料是否出錯(cuò)，可經(jīng)由下式計(jì)算而判別出其癥狀 (這些癥狀值包含所有錯(cuò)誤大小及位置： )()()()( ， k=1, 2, , 2t 式中計(jì)算結(jié)果只剩下 e( k )，因?yàn)?k 為 3g(x)的根，而 g(x)可整除C(x)，故代入后 C( k )將被消掉。經(jīng)過 有 2, 全為 0則代表資料正確無誤；若不全為 0則表示有錯(cuò)誤存在，導(dǎo)致 e(x)殘留不為 0的值，必須進(jìn)行解錯(cuò)運(yùn)算。其中每個(gè) 位元寬度與 3若 3此時(shí) 。 癥狀值算完后便可得知資料是 否出錯(cuò)，若有錯(cuò)則必須繼續(xù)找出錯(cuò)誤位置及錯(cuò)誤大小之步驟，如下所述： 先以皮德森演算法 (將上述計(jì)算出之癥狀值解出錯(cuò)誤位置多項(xiàng)式 ( tt tt )( ，其中 10 ， 011 / 并將所有癥狀值以多項(xiàng)式形式表示 ( tk kk 1 1)( 此刻解碼器已解算出錯(cuò)誤 癥狀值、未知錯(cuò)誤位置多項(xiàng)式，并由外界提供而計(jì)算出已知錯(cuò)誤位置多項(xiàng)式，接下來必須計(jì)算錯(cuò)誤的大小。然而本例設(shè)計(jì)之 RS 解一個(gè)未知錯(cuò)或二個(gè)已知錯(cuò)，故在此造成一個(gè)分支，視不同狀況而以不同方式計(jì)算錯(cuò)誤的大小 ( )()()( ， er a s u r er r o ( )()( 若有已知錯(cuò)則以已知錯(cuò)誤多項(xiàng)式 (解錯(cuò)；若無已知錯(cuò)則使用上 - 20 - 述解算出之錯(cuò)誤位置多項(xiàng)式 (進(jìn)行解錯(cuò)運(yùn)算。 現(xiàn)已獲得錯(cuò)誤位置與錯(cuò)誤大小之個(gè)別多項(xiàng)式，只需將所有根代入并計(jì)算，便可得該錯(cuò)誤位置及錯(cuò)誤大?。?)( )()( 最后便是針對(duì)錯(cuò)誤位置，將解算出的錯(cuò)誤大小以 e(x)表示，并將 e(x)加回 r(x)，便可將錯(cuò)誤消掉而達(dá)到修正之結(jié)果， C(x)便為解碼后正確的資料： C(x) = r(x) + e(x) 綜合以上所述，總結(jié)解碼器之運(yùn)作流程如圖 3 圖 3解碼器之流程圖 - 21 - 依據(jù)上述之流程，其方塊圖如下圖 3 圖 3解碼器方塊圖 圖 3錯(cuò)誤解算出之后，將輸入資料修改。最下面的 后可見此方塊圖中的唯一分支點(diǎn)，判別是否有已知錯(cuò)，若有則后部將接收并處理 不再處理 后有二個(gè) 最主要作用在于個(gè)別將所有根依序代入錯(cuò)誤位置及錯(cuò)誤大 小二個(gè)多項(xiàng)式，其輸出結(jié)果供后部之 備 - 22 - 第四章 4散傅立葉轉(zhuǎn)換 (離散訊號(hào) )(一維離散傅立葉轉(zhuǎn)換 (下所示 36： 10 )/2()()( Nk , 1,.,1,0 (也可以寫成 10 )()( Nn (其中 2。 而 )( 反離散傅立葉轉(zhuǎn)換(如下所示： 10 )/2()(1)( Nk , 1,.,1,0 (因此，形成下面的轉(zhuǎn)換對(duì)： )()( (一維離散傅立葉轉(zhuǎn)換有下列特質(zhì)： 1. 線性 ()()()()()()( 213213 (其中 a和 2. 對(duì)稱性 (若 )(實(shí)數(shù)，則 )()( (3. 與回旋積的關(guān)系 對(duì)于兩個(gè)長(zhǎng)度分別為 1N 及 2N 的離散訊號(hào) )(1 )(2 執(zhí)行回旋積定義)()()( 213 后， )(3 長(zhǎng)度可達(dá) 121 現(xiàn)在將 )(1 )(2 別添補(bǔ) 12 N 及 11N 個(gè)零后，將其視為長(zhǎng)度為 (,1 與 )(,2 ， - 23 - 且其 (1 )(2 則 )()()( 213 (換言之，這是透過 合下一節(jié)所討論的快速傅立葉轉(zhuǎn)換，當(dāng)所考慮訊號(hào)的長(zhǎng)度大到一個(gè)程度以后，以上式執(zhí)行回旋積會(huì)比用定義直接計(jì)算快，而且訊號(hào)長(zhǎng)度越長(zhǎng)，所節(jié)省的時(shí)間越多。二維離散傅立葉轉(zhuǎn)換具備一維情況完全相同的性質(zhì)。 4速傅立葉轉(zhuǎn)換 (快速傅立葉轉(zhuǎn)換 (一種用來計(jì)算離散傅立葉轉(zhuǎn)換及反離散傅立葉轉(zhuǎn)換的高效率演算法?？焖俑道~轉(zhuǎn)換的價(jià)值在于它使用更快的計(jì)算方式來節(jié)省計(jì)算機(jī)的時(shí)間，降低了數(shù)位訊號(hào)處理中乘法的運(yùn)算量，使得更多更復(fù)雜的訊號(hào)得以快速的處理，改善了數(shù)位訊號(hào)不能即時(shí)處理的問題，為數(shù)位訊號(hào)的即時(shí)處理帶來了希望，因此，快速傅立葉轉(zhuǎn)換是數(shù)位訊號(hào)處理發(fā)展史上的一個(gè)重要里程碑。 快速傅立葉轉(zhuǎn)換的演算法，可分為時(shí)間端分組 (頻率端分組 (種 36。 茲以 N=16的離散函數(shù) )(例說明之。因?yàn)?N=16，所以 15 0 )()( n 15,.,1,0k (依照偶數(shù)位置和奇數(shù)位置，將序列 )(成兩個(gè)序列，可得 1501501616 )()()(e v e 因?yàn)?8/2)2(16/2)2(16 (所以 - 24 - 7 0 87 0 168 )12()2()( n (若令 )2()(10 ()12()(11 (則 7 0 8117 0 16810 )()()( n (令 7 0 81010 )()( n ( 7 0 81111 )()( n (7,.,1,0r ，即分別為 )(10 )(11 8點(diǎn) 寫 得 )()()( 111610 r (另外，由 (8 也可輕松證得 )()()8( 111610 r (7,.,1,0r ?？梢?所謂的蝶形 (算單元。在圖 4圖形來代表一個(gè)蝶形運(yùn)算單元，其中 變動(dòng)因子 ( 前三級(jí)可依此類推。亦即一個(gè) 16點(diǎn)的 個(gè) 8點(diǎn) 8點(diǎn)的 個(gè) 4點(diǎn) 4點(diǎn)的個(gè) 2點(diǎn) 個(gè) - 25 - 圖 4 運(yùn)算單元。 (a)蝶形運(yùn)算單元； (b)為 (a)之簡(jiǎn)圖。 圖 4整個(gè) 算法的流程圖 - 26 - 圖中輸出入序列的序號(hào)間恰有位元倒置的關(guān)系。所謂位元倒置就是將一序列之序號(hào)的二進(jìn)位碼反序后作為新的序號(hào)。 前面的 在 其他過程則相同。 我們?cè)俣纫?N=16的離散函數(shù) )(例說明之。因?yàn)?N=16，所以 15 0 )()( n 15,.,1,0k (將上式依 )(成兩部份，即 15 0 15 8 1616 )()()( n n (其中第二個(gè)和可寫成 15 8 7 0 7 0 16)8(1616 )8()1()8()(n n n (將此結(jié)果代回