Profile - TW034

TW034

結合藍芽無線傳輸之RS Code FPGA晶片設計與實現

Project Paper - view as Preliminary(2010/07/21), Final(2010/11/01), Draft, Latest

1. 設計介紹 (Preliminary Paper)

 

 

設計目的：

        伴隨著科技產業的進步，通訊傳播媒介的與日俱增，現今多媒體訊息不僅是要傳達到接收端而已，而是需要具備正確性、高傳輸速率以及傳輸範圍的確保，這三個條件也成為訊息在傳輸過程中重要的一環，尤其個人資訊化的科技時代來臨後，資料傳輸的準確性更為重要，所以為了讓傳送的資料準確無誤，運用錯誤更正碼(Error Correction Code)技術來確保資料在傳送過程中，即使受到雜訊干擾也能檢錯及糾錯，完整無誤的呈現訊息內容。本作品將錯誤更正碼技術運用於無線傳輸系統中，以數位訊號當作訊息源，應用里得所羅門碼(Reed Solomon, RS碼)進行通道編碼，首先我們以Matlab軟體模擬分析系統性能，配合Quartus II開發軟體並以VHDL硬體描述語言撰寫硬體程式，並以FPGA晶片實現無線多媒體系統硬體電路，驗證里德所羅門碼在無線傳輸系統之糾錯能力，確保通訊品質。

本作品之設計目的是利用''里德所羅門碼(Reed Solomon碼，簡稱RS碼)''之錯誤更正技術，來確保、還原這些在傳輸過程中遭到破壞的資料，使之能正確的傳輸到接收端，提供更高品質及高效率的訊息傳輸，保證資料傳輸過程的正確性及可靠性。

本作品以友晶科技所研發的Altera DE2-70作為硬體開發平台，此平台有廣泛的多媒體資源，可以使本作品做到消除影像雜訊及雜音等目的，使本作品有更大的開發空間。

應用領域：

本作品可以應用在許多數位傳輸系統中，例如高畫質數位電視(HDTV)、數位通訊、影像電話、無線傳輸以及電腦儲存系統等資訊家電系統。

目標的使用者：

           數位通訊業者及一般消費者。

(Revision: 3 / 2010-06-30 12:25:59)

2. 功能描述 (Final Project Paper)

 

(1)   里德所羅門碼通道編碼

通道編碼在數位通訊系統設計中扮演著非常重要的角色，其原理是將要傳送的訊號位元或符號經過編碼演算法設計後，使其能夠對抗各種通道的雜訊干擾。近年來通道編碼越來越受到歡迎，已逐漸成為一種趨勢。而現今大部分的通訊系統都會加上錯誤更正技術，其原因是在通訊過程中會因雜訊干擾而造成訊息傳輸錯誤，為了能夠去除這些錯誤，就必須具備糾錯的能力，所以在通訊系統中，通道編碼已成為相當重要的一環。

設計說明：

發送端若傳送一個字元a (經ASCII碼轉換，配合( 7,3 )RS code編碼格式，字元a被轉換為2,0,3的三個十進位訊息，其有限場符號為: α¹,0, α³，亦可表示為多項式:( α¹+ α³x² )訊息，經過( 7,3 )RS code編碼運算後，算出四個核位元數值為:4,5,1,7，並與原本的訊息結合成為一組三個訊息元及四個核位元之完整( 7,3 )RS code碼字: 4517203。

其完整多項式訊息為:( α² +α⁶ x+α⁰ x²+α⁵ x³+α¹x⁴ +α³x⁶) →4517203

圖2-1顯示數值為a字元編碼後所要傳輸之碼字訊息：4517203

圖2-1：完整編碼後之訊息:4517203

(2)   里德所羅門碼通道干擾

我們使用人為的方式製造出通道雜訊，並與完整編碼後之碼字訊息作結合，模擬編碼訊息在通道傳輸中遭到干擾後的訊息。

通道干擾說明：

訊息在通道傳輸中若第2及第3位置被干擾，且雜訊大小分別為: 5 與 6，雜訊向量可表示為:(0000650)，其多項式為: α⁴x⁴+ α⁶x⁵。

圖2-2為設定雜訊攻擊之位置及數值：

 

圖2-2：設定雜訊攻擊之位置及數值

經過通道干擾後，訊息變為( α²+ α⁶x+ α⁰x²+ α⁵x³+ α²x⁴+ α⁶x⁵+ α³x6)→4517453

 

圖2-3為遭受雜訊干擾後之訊息：

圖2-3：遭受雜訊干擾後之訊息

(3)   里德所羅門碼通道解碼

在解碼端，經由藍芽接收機收到之受干擾訊息，我們利用解碼電路，首先計算出訊息錯誤徵狀值，接下來利用彼得森矩陣計算出錯誤位置多項式，再以秦式搜尋找出多項式之根，並依據其反元素找出錯誤位置，接著利用佛尼(Forney)計算出錯誤位置之錯誤值，最後將原本被雜訊干擾後之訊息改正回來。

圖2-4為計算徵狀值：( S₄= α¹,S₃= α⁶,S₂= α³, S₁= α²)

圖2-4：計算徵狀值

圖2-5為彼得森矩陣(計算錯誤位置多項式為: (α⁶x⁵+x⁶))：

圖2-5：彼得森矩陣之數值

圖2-6為秦式搜尋演算法(尋找多項式之根，並依據其反元素找出錯誤位置，數值為1者為其錯誤位置:即位置2及3)：

圖2-6：秦式搜尋演算法

圖2-7為佛尼(Forney)演算法(計算錯誤位置之錯誤值分別為6及5)：

圖2-7：佛尼(Forney)演算法

圖2-8為經過解碼後改正回來之正確訊息：

圖2-8：解碼後之正確訊息

 

 

 

 

 

(Draft / 2010-09-17 15:01:59)

3. 效能參數 (Final Project Paper)

 

             本作品主要特色為應用具有糾錯能力的( 7,3 )RS里德所羅門碼於藍芽無線傳輸系統，而RS( 7,3 )碼的糾錯能力為2個字符( 1個字符=3個位元 )，所以在本系統的無線傳輸過程中，每傳送一組碼字，若經通道干擾的訊息錯誤量在6( 2×3=6 )個位元以內，都能順利的更正回正確訊息。因此本無線傳輸系統可以應用在較複雜的干擾環境，提昇傳輸訊息的傳輸率及確保通訊品質。

(Draft / 2010-09-17 07:27:56)

4. 設計架構 (Preliminary Paper)

圖4-1為軟體設計流程圖：

圖4-1: 軟體設計流程圖

系統設計流程圖及電路圖：

 

    圖4-2及圖4-3分別為RS(7，3)編碼流程圖及電路圖：

           我們將鍵盤擷取的ASCII碼，當作編碼的訊息，加入雜訊干擾結合，把干擾的碼字傳送到解碼如圖4-2為訊息編碼流程：

圖4-2: RS編碼流程圖

圖4-3: RS編碼電路圖

 

    圖4-4為RS解碼流程圖，圖4-5至4-13為解碼電路圖：

 

將收到的多項式，進入RS（7,3）生成多項式得一餘數，將餘數代入電路中計算出徵狀值。

圖4-4: RS解碼流程圖

圖4-5: 徵狀值電路圖

    將徵狀值1~徵狀值4放置暫存器，使用彼德森矩陣計算錯誤位置多項式，此電路有一判斷電路，判斷兩個錯誤和一個錯誤時，應該由哪一個輸出。兩個錯誤和一個錯誤，運算式不相同所以需做判斷電路，電路下方有一判斷電路。

圖4-6:彼德森矩陣電路圖

    因運算方便，減少複雜度，所以推導反元素電路。

圖4-7:反元素電路 圖

   將場中之元素一一代入錯誤位置多項式尋找根，因此我們利用秦式搜尋法來完成。

圖4-8: 秦式搜尋電路圖

     經過秦式搜尋法找到根後，將根反元素得到錯誤位置。

圖4-9: 計算錯誤位置電路圖

    找到的錯誤位置分別在不同的暫存器上，經過由半加器所組成的判斷式各分別放入兩個暫存器上，準備計算錯誤值。

圖4-10: 錯誤位置判斷電路 圖

     將S1、S2 及錯誤位置代入錯誤值矩陣，計算錯誤值。

圖4-11: 計算錯誤值電路 圖

    將錯誤位置與錯誤值計算出來，但是需將錯誤值擺到正確的錯誤位置上，所以做一個比較電路。當收進來的錯誤位置與模組a0~a6(錯誤位置)其中一個相同，則比較電路會送出一個1，來開啟AND閘將錯誤值送出，因此錯誤值會在錯誤位置上。

圖4-12: 錯誤位置比較電路 圖

     將錯誤值與收到的訊息多項式相加，並改正回來。

 

圖4-13: 改正訊息電路 圖

 

 

(Revision: 2 / 2010-06-30 12:21:43)

5. 設計方法 (Final Project Paper)

 

本作品設計主要是針對訊號在無線傳輸過程中，遭受到雜訊干擾的情況，由目前使用最廣泛且最有效率的里德所羅門碼，來進行編碼及糾錯。

 

    本作品主要分為里德所羅門碼編解碼演算法以及週邊硬體電路等兩大部分，其使用 FPGA來實現里德所羅門碼編解碼演算法之設計如下：

1.      里德所羅門碼編碼單元：此編碼區塊為本作品重要的一環，透過里德所羅門碼編碼可以保護我們所要傳送之訊息，不易受到外來雜訊的干擾而產生錯誤之訊息。其編碼公式如下：

   設要編碼的k個位元訊息多項式為：

 

       

        其中k為訊息長度，訊息m=(m₀,m₁,…,m_k-1)。

        將訊息多項式乘x^2t，其中t為錯誤個數，再除以生成多項式 g(x)，

        即

        則 x^2tm(x)+b(x)為碼字多項式。其編碼電路架構圖如圖5-1所示。

圖5-1：里德所羅門碼編碼電路架構圖

2.      里德所羅門碼解碼單元：利用本單元內之解碼區塊，將經由雜訊干擾後之訊    

   息改正回來。解碼主要流程為圖5-2所示。其解碼部份區分為以下三個區塊：

 

圖5-2：里德所羅門碼解碼流程圖

(1)   徵狀值計算單元：

徵狀值計算為解碼過程的第一步，設α,α², α³,… , α^2t為生成多項式

                     g(x)的根，t代表錯誤更正的能力，碼字多項式及錯誤多項式分別為:

 

        及

        收到的信號可表示為:

       

        則徵狀值為:

       

(2)   彼得森矩陣單元：利用彼得森矩陣我們可以計算出錯誤位置多項式。

                   其公式及關係如下：

 

     利用上述矩陣可將σ (x)中係數{σi }解出來。倘若錯誤模式剛好有t個錯誤，

 那a之行列式值A ≠ 0；假如錯誤各數少於t個時，A = 0，若 A = 0，將A各刪除一

 行及一列成為A’，重新檢查A’ 之行列式是否為0，一直到剩餘的行列式不為0為

      止。

          若產生一個錯誤即得到1×1階彼德森矩陣：

            則[ S₁][ σ₁]=[S₂]

            計算σ₁：

            即得到錯誤位置多項式：

          若產生兩個錯誤即得到2×2階彼德森矩陣：

            

             計算σ₁σ₂：

            

            

             即得到錯誤位置多項式：

(1)   錯誤更正單元：此單元分為兩個部份，分別為Chien Search(秦式搜尋)演算法以及Forney(佛尼)演算法。其原理及公式如下：

 

Chien Search(秦式搜尋)演算法:

         Chien 尋根演算法就是將伽羅瓦場中所有的元素代入錯誤位置多項   

式測試，若為零表示此元素為此方程式的根，而根的倒數就是錯誤位置

，找到錯誤的位置再用佛尼（Forney）演算法去找出其相關位置之錯誤

大小。

 

Forney演算法:

                     經由關鍵方程式（Key Equation）及錯誤徵狀（Syndrome）推導得：

                    

        其中為錯誤位置為錯誤值。

 錯誤更正:

    求得錯誤位置跟錯誤值後，就有錯誤多項式 e(x)的各項係數，

再將接收的碼字多項式r(x)與e(x)做相加，即可得到由編碼器送出的

碼字多項式v(x)。

 

週邊硬體設計如下：

1.    七段顯示器：顯示傳輸訊號之訊息。

2.    鍵盤：將所要傳輸之訊息經由鍵盤輸入。

3.    RS232連接埠：利用電腦超級終端機傳送經由鍵盤鍵入之訊息，並以RS232連接埠連接DE2-70進行訊息之傳送。

4. 藍芽無線裝置：將所要傳輸之訊息利用藍芽無線裝置進行無線方式之傳輸。

 

 

 

 

 

 

 

(Revision: 5 / 2010-09-17 16:48:05)

6. 設計特點 (Preliminary Paper)

1.循環碼
　　　　錯誤更正碼主要是在編碼時，加入具有結構特性之糾錯資訊，即額外使用部分頻寬傳輸額外位元，再藉由調變傳輸；在接收端經解調後之接收訊號，使用相對應之錯誤更正解碼，利用糾錯資訊來達成錯誤偵測與更正，進而達到降低位元錯誤率或降低天線傳輸功率需求的目標。
　　循環碼解碼器的複雜性，主要取決於由徵候確定錯誤圖樣的組合電路的簡單與否。對某些碼來說，這種組合電路可以做得比較簡單，如循環漢明碼。除此以外，利用訊息集解碼中的捕錯解碼方法，也能夠用較簡單的組合邏輯電路實現解碼。它特別適用於更正突發錯誤碼、更正單個隨機錯誤碼，以及某些低碼率和碼長較短、更正錯誤能力較弱的碼。

 

 

2.Reed-Solomon(里德所羅門， 簡稱：RS)

         RS編解碼器即是以有限場為基本單位所建立，然而，這些基本運算單元的架構對於硬體而言是複雜且龐大的，且不容易被實現，因此選擇適當的運算單元架構，例如：加減法、乘法和除法或反元素等，可簡化整體電路的複雜度，有效降低晶片的大小加快資料處理的效率跟速度。

我們使用了DE2-70進行編碼，將錯誤訊息結合，再利用藍芽無線傳輸技術將訊息傳輸到另一台DE2-70進行解碼和錯誤改正，把我們的訊息正確的改正回來。

 

 

3.無線傳輸(藍芽)的特點

 藍芽現今可以讓不同產品(例如：印表機、PDA、PC、傳真機、鍵盤、Notebook)於短距離進行資料傳輸及溝通，因此藍芽不必使用任何有線的傳輸線路，就能連接各種數位設備。其特點如下：

 

 

 

操作頻段：2‧4GHz工業、科學、醫療頻段。連接執行於在全球範圍開放的2.4GHzISM波段上，可及範圍十公分到一百公尺。 

 

使用跳頻展頻(Frequency Hopping Spread Spectrum；FHSS)，最高可支援八個連結埠，毋需如紅外線傳輸埠做「視線(Line-of-sight)」的傳輸，支援同步和非同步傳輸模式，易與TCP/IP整合成網路。

 

 

4.UART(通用非同步收發器)之特點

          UART(Universal Asynchoronous Receiver Transmitter)通用非同步收發器是一種並列輸入/串列輸出與串列輸入/並列輸出方式的資料轉換。在UART協定中，傳送器及接收器不會共用同一個時脈訊號。也就是說，時脈訊號不會從UART傳送器發送至另一個UART接收器。所以，UART協定被稱之為非同步傳輸。

 

        在UART的傳輸結構中，起始位元固定為0，停止位元固定為1，所以接收端的動作是一直不斷的檢查傳輸線的狀態。當傳輸線上的信號一直為1就表示沒有資料傳送；當傳輸線上的信號由1變為0，即表示有資料將傳送，接收端就會開始準備接收8個位元資料，直到傳送完8個位元資料，傳送端最後會送出停止位元，並使傳輸線的信號保持為1，以等待下一次的資料傳輸。經由增加起始位元與停止位元方式，雖然會使串列傳輸效率更降低，但可解決位元資料傳輸的起始與停止之問題。另一串列傳輸協定為傳輸速度，通常以鮑率(Buat Rate)，即每秒傳輸的位元數來衡量，一般UART常使用的鮑率有1200、2400、4800、9600及19200等。兩種裝置在進行串列傳輸時，必須決定以何種鮑率來進行資料傳輸，當兩種裝置使用同一鮑率才能確保資料傳輸正確無誤。如下圖為基本的UART資料型態。

 

 

 

圖6-1: 基本的UART資料型態

 

(Revision: 2 / 2010-06-30 12:24:27)

7. 總結 (Final Project Paper)

 

 錯誤更正碼為目前學術界探討相當廣泛的一種提升通訊品質的技術，並受到各方學者的研究及重視，而後各種著名的編解碼理論及解碼電路也相繼的被提出以及研究，現今錯誤更正碼已普遍在通訊及電腦儲存系統等資訊家電系統上被廣泛的使用，並為各種通訊產品提供穩定品質的保證。但在糾錯編碼理論領域的研究，國內在硬體實現的部分普遍稍嫌不足，本作品以硬體電路實現出糾錯編碼技術，並結合藍芽無線通訊之技術，使本作品能夠擁有廣大的應用空間，以期望未來的糾錯編碼理論與技術能夠擁有更大的發展，並對國內學術及業界有所助益。

    感謝友晶科技舉辦這次的「2010 Altera亞洲創新設計大賽」，參加這次的Altera大賽讓我們學習到很多晶片及傳輸系統設計的技術，因為本作品的電路相當繁雜而且龐大，因此在這時候更可以體會到團隊合作的重要性。並且也讓我們學習到很多以前所沒有經歷過的，從一開始了解原理、架構系統設計電路圖、模擬訊息傳輸到最後的解決問題，都是我們這次參與「2010 Altera亞洲創新設計大賽」最寶貴的經驗以及收穫。而讓我感到收穫最大的部份就是了解如何從原理轉換為電路，這是我最大的突破。最後再次感謝友晶科技提供我們許多FPGA的平台以及相關的軟硬體資源，讓我們可以無後顧之憂的去發揮自己的想法以及創意，並從中提升自己對FPGA晶片的設計能力，也希望參加此次競賽可以與各大專院校共同學習以及成長，由此來增廣自己的視野以及提升各方領域之了解，因此能參與這次比賽我們都感到非常的榮幸。

(Revision: 3 / 2010-09-17 16:54:20)