在提供數位化資訊與通訊的技術中,錯誤更正碼扮演著核心之的角色。不論是已普及的數位式音響如CDDVD,未來的數位式廣播、數位電視,現在的數位式衛星直播,電腦各式記 憶體及儲存裝置如RAMROM、硬碟機、光碟機、甚至運算處理單元,網際網路資料編碼格式等皆使用錯誤更正碼來大大提升訊息的可靠性與整體性。主要研究範圍可區分為下列課題:

 

 

B3G系統中的時空碼 (space-time code)設計

 

高效能編解碼技術一直是無線接取系統設計的關鍵議題。這是因為它們能夠增加系統容量、擴大涵蓋範圍以及提高傳輸品質。我們相信在未來的B3G系統中,前瞻性編解碼技術將持續扮演重要角色。我們計畫分別對渦輪碼、低密度對偶檢查碼、時空碼以及中國餘數定理碼等前瞻性編碼方式,針對在不同的調變方法、符元大小、編碼率及無線通道特性等條件下:1.探討這些編碼技術於正交分頻多工/分碼多重接取系統中的編碼設計準則;2.找出實際設計範例;3.評估錯誤表現性能;4.提出可實行的解碼方法。另一方面,為了因應B3G系統為提供全面性的服務所要求的多樣傳輸品質,我們也將提出具體的適應性編解碼架構。

 

代數幾何碼 (Algebraic-Geometric Codes

 

里德所羅門碼 (Reed-Solomon Codes),簡稱RS碼,為相當普及應用於現今工業界的錯誤更正碼。RS碼的效能非常好。但其缺點為需要用大的符號域(Symbol Field) GF(q) 來建立長的RS碼。 而算術複雜度隨符號域大小成指數成長,因此RS碼的編解碼複雜度將隨其長度增加而變得非常高。 代數幾何碼可視為RS碼的推廣,可建立具有不亞於或甚至超越RS碼效能的長碼而不需 要用大的符號域。 代數幾何碼從一九八0年代開始建立編碼的數學理論基礎,並在一九九年代發展解碼的方法。但長久以來即有一個代數幾何碼可否在實際應用上與RS碼匹敵的問題 。原因是RS碼有可運用於工業界的實用編解碼演算法及VLSI架構。 而代數幾何碼則有待開發。 代數幾何碼的解碼如同RS碼一般分為四個步驟:計算病徵 (Syndromes),找出錯誤位置多項 (Error Locator Polynomials),解出錯誤位置與計算錯誤值。 我們在這方面的研究成果有論文 論文在文獻上首次將一個富盛名的找出錯誤位置多項式的方法, Feng-Rao 演算法,運用非均勻一維心臟壓縮式陣列(Systolic Array) 很有效率的以平行處理的方式實現出來。針對一類重要的代數幾何碼,Hermitian碼,發明出一種 類似用於RS碼計算病徵以及解出錯誤位置的演算法及其VLSI機構。我們相信這些發明有助於早日將代數幾何碼應用於工業界。此外,我們以高斯消去法重新闡釋廣泛用於RS碼解碼找出錯 誤位置多項式的Berlekamp-Massey 演算法,並把這個闡釋推廣於代數幾何碼的解碼上,發展出一種新的快速找出錯誤位置多項式的方法。近來我們利用Hermitian碼的代數結構與Grobner Basis的關連,發明出一種類似用於RS碼的編碼器硬體機構。

 

 線性區塊碼的籬笆結構 Trellis Structure of Linear Block Codes

 

線性區塊碼的軟性解碼比硬性解碼有更佳的性能。而從事軟性解碼的一個前提通常是需要 建立一個線性區塊碼的籬笆圖 (Trellis Diagram) 在這樣一個籬笆圖上,我們更可以做每一個訊息位元的最佳軟性解碼。因軟性解碼的複雜度取決於籬笆圖的複雜度,我們必須去尋找具 小複雜度的籬笆圖。 我們在這方面的研究成果有論文 在論文中,我們對Reed-Muller 碼最小籬笆圖中各位元位置的複雜度問題作了最後的解決。 並提供一個很簡單的遞迴公式來計算此最小複雜度。一般知道將線性區塊碼的字元位置重新排列,其最小籬笆圖的複雜度可能變小。 但如何有效率的找出一個最佳的排列使得最小籬笆 圖的複雜度最小,一直是一個未能解決的問題。 在論文中,我們提出一個可行的演算法,只要線性區塊碼的長度中等以下,都可以快速決定一個最佳的排列出來。雖然這個 演算法對較長的碼來說,其複雜度仍無法忍受,但已是當今最好的演算法。 在論文中,我們開始嘗試探討非線性區塊碼的籬笆結構。

 

 其他的錯誤更正碼

 

除了上述錯誤更正碼外,近年來我們研究的課題亦包括渦輪碼(turbo code)低密度同位元檢查碼(Low Density Parity Check code)等。

 

 

數位通訊

 

數位通訊技術的核心包括調變解調變技術、編解碼技術、同步技術及接收器結構技術等。除編解碼技術如 (I) 所述外,我們其他主要研究範圍可區分為下列課題:

 

 無線通訊技術

 

無線通訊技術是近一、二十年來數位通訊研究的重要課題之 我們的研究重點是放在適用於無線通訊的調變技術暨接收器結構技術上。 編碼調變技術可在不增加頻寬、不增加傳輸功率的條件下,大大降低數位傳輸的位元錯誤率。此技術已很成功的運用在有線高速數據機的製作上。 對無線通道而言,設計最佳編碼調 變的標準不同於有線通道。 我們針對CPFSK 這種調變方式提出一個演算法來決定最佳的二元迴旋碼(Binary Convolutional Codes) 來形成用於無線通道的最佳編碼調變。 在無線通訊技術中,常用分集法(Diversity) 來大大的降低傳輸的位元錯誤率。 當然使用分集法需要額外的資源,例如頻寬、效率、硬體設備等。我們利用理論證明超取樣 (Oversampling) 的方法其作用相當於分集法的效果。 因此,我們可以用運算複雜度來交換利用分集法所需要的資源。

 

 同步技術

 

同步技術是數位通訊的古典課題。 同步器的設計,一般而言是一種工藝。其確切的性能分析一般是非常困難的,因此大都以概略性分析及模擬為主。在論文中,我們運用隨機逼近法 則,提出一種遞迴式最大可能估測法來做為聯合式載波相位及符元時序回復的同步演算法,並以模擬驗證其具有非常好的性能。這包括其準確的收斂性及快速的收斂性,並適用於即時 (Real Time) 的應用上。在論文中,我們更進一步運用系統理論中的 Lyapunov 穩定性理論及隨機程序中的 Martingale 理論來證明這個同步演算法以機率為1 的方式到正確值並且其收 速率漸進於 Cramer-Rao 下限,也就是漸進於最佳收斂速率。