数位电视传输技术.doc

數位電視傳輸技術期末報告針對DVB-T使用204/188 Reed-Solomon Encoder技術分析、討論及驗證（使用MATLAB軟體）碩研通訊一甲劉純佳M97S0101目錄圖目錄2表目錄2摘要31Finite Field31.1.Primitive Polynomial41.2.Finite Elements42RS Encoding82.1RS Encoder的編碼方式82.2Generator Polynomial92.3Generator Polynomial的電路表示法102.4RS Encoding運算103.使用Matlab驗證RS Encoder架構11結論15參考資料16圖目錄圖 1 RS encoder 流程圖8圖 2 RS Encoder的電路架構10表目錄表 1 Galois Field的四則運算功能3表 2 常用的本質多項式4表 3 的255筆元素資料6表 4 使用Matlab軟題執行上述RS編碼程式後的輸出結果14摘要 本報告係針對Reed-Solomon code(RS code)在DVB-T上所使用的204/188編碼方式作一個簡單的說明。首先將會從Finite Fields（有限體）的意義以及如何生成一個Galois Field（伽羅瓦體）做簡單的說明；其次將介紹Primitive Polynomial（本質多項式）與RS code的關連性；最後透過鈦思科技的數學運算軟體Matlab，經由撰寫程式的方式完成一RS Encoder，並與理論上的編碼技術相互整合，做一個簡單的說明、分析與驗證，並且將會輸入一筆訊息資料至撰寫好的RS Encoder程式內來進行編碼，以驗證其編碼結果。關鍵字： RS code、DVB-T、Finite Fields、Galois Field、Primitive Polynomial。1 Finite Field 在進行RS編碼之前，必須先了解整個Finite Field的架構，以及一些基本的運算特性，其中Galois Field為Finite Field的其中一種架構，也是進行整個RS編碼的主軸。在Galois Field當中，假設裡面有組數值，我們將各個數值以“Element（元素）”稱之，讓各個數值以一變數的次方來做Finite Field的表示，因此則可以表示成下列所示之Finite Field的狀態： 在上式中，其各個元素的數值大小並非是規律的變化（）而是利用位元以及運算的方式來表達，表達的方式與一組多項式有關，通常以Primitive Polynomial（本質多項式）稱之，其功能類似於一般數值運算中的“質數”的用途。 在Galois Field中，我們可以使用任意兩元素做四則運算，但是運算方式與一般數值的四則運算又有些許的不同，例如加法運算與減法運算相同，可視為位元作XOR運算功能；乘法運算與除法運算相同，可視為位元作AND運算功能，因此Galois Field又可稱作Binary Field。上述運算功能可彙整成如表 1所示之內容：表 1 Galois Field的四則運算功能加/減法乘/除法 接者本文將在以下章節提出一個例子，說明如何利用一組Primitive Polynomial建立Finite Field的Elements。1.1. Primitive Polynomial Primitive Polynomial（本質多項式）如同質數一般，其多項式不可被其他長度的多項式給整除，近年若需要使用本質多項式作相關運算，已不用費心去計算哪一組多項式才是本質多項式，已經有學者專家們特地將這些本質多項式給計算出來。常用的本質多項式如表 2所示：表 2 常用的本質多項式Primitive PolynomialmPolynomialmPolynomial3144155166177188199201021112212231324 上表為常見的本質多項式的內容，在本篇報告中所提到DVB-T的204/188編碼技術係使用表格中以黃色底顯示的本質多項式的內容來進行編碼，以下將說明如何將利用多項式產生一組伽羅瓦體的有限元素內容。1.2. Finite Elements 在進行運算之前，我們可以先想像上一章節中的本質多項式的內容，先將多項式的內容重新做排序的動作，然後將他想像成一組二進制的數值，如下列所示：如上列所示，最低位元為，最高位元為，每個的次方項係數可視為二進制的第幾個位元，因此我們可以將沒有列在多項式上的內容（）皆補上0，最後產生一組100011101的二進位數值。 在使用轉換之後所得到的二進制數值之前，我們可以先用變數來做接下來的運算，以免到最後因為一堆的0和1數字造成運算的混淆；以下將開始以本質多項式說明如何建立一組伽羅瓦體的有限元素內容：一開始我們可以根據本質多項式得到的元素，步驟如下：l 先令。l 將以外的內容移至等號右邊，如：由於在位元運算中，加法運算等同於減法運算，因此移項後正負號皆維持不變，因此可得到的伽羅瓦體的有限元素內容為：在之前的元素可以當作是一個位元從最低位元依序位移到最高位元的方式，因此可以得知的元素分別為：在之後的元素也是使用位元左移的概念作運算，如下列所示：Overflow!但到了要做的元素運算的時候，我們可以發現到經過一次位元左移後產生溢位（Overflow）的狀況，如下所示：此時就需要將與做運算，運算後得到一組新的元素值，運算方式如下：經過運算後所得到的數值即為的元素值。根據以上的作法可以得到255筆元素資料，我們將變數改寫成變數後彙整成表 3所示之清單：表 3 的255筆元素資料元素數值元素數值元素數值元素數值註：000101112 RS Encoding 在上一章節簡單介紹了Finite Field的特性以及如何利用Primitive Polynomial建構出Galois Field的元素內容後，接著我們將開始進行RS code的編碼說明。但在進行編碼之前，我們先來對DVB-T的204/188這組數字做一個解釋：我們令、，則：在上式中，為RS編碼後的symbol長度；為在RS code中所佔用的訊息長度；代表著RS Encode後所攜帶的parity symbols；則是在此編碼當中所能偵測並更正的最大錯誤symbols。以DVB-T為例，它的總長度為204個symbols，其中訊息量佔了188的symbols，其可以攜帶16個parity symbols，同時也具備了8個symbols的錯誤更正能力。了解這些意義之後，接著我們將開始依序說明如何做出RS編碼。2.1 RS Encoder的編碼方式 若想產生一組RS code的編碼，則編碼過程可以用圖 1的執行過程來進行運算，產生出一組經過RS 編碼後的結果如下圖所示：圖 1 RS encoder 流程圖 在第2章一開始我們有說明了變數、所代表的意義，也在第1.1節和第1.2節說明了Primitive Polynomial的選擇方法，並且建立了一組針對DVB-T規格的Finite Elements的Table，也就是完成了如圖 1所示的前三組區塊，接著我們將開始說明如何產生一組Generator Polynomial，以便讓我們進行RS編碼的動作。2.2 Generator Polynomial 要產生一組Generator Polynomial，其中變數以及Primitive Polynomial是這個部份的重心。透過產生的Finite Elements當作Generator Polynomial各項的係數；變數則掌握了Generator Polynomial的大小，以DVB-T為例，則Generator Polynomial最大可以表示到次方的範圍，其Generator Polynomial的表示式如同下列所示：當最高次方項係數為時，我們可以求得此多項式可以有個根（root），此時可以將上式改寫成以下敘述：之後將上式展開並做整理，由於此生成多項式的展開運算量龐大，因此本文將以此多項式的為一例子來做整理的說明：l 首先先將展開，展開後可得：l 接著根據表 3的內容，找出與所代表的數值分別是和，並做以及的運算：l 最後將整個多項式作整理，其中負號與正號代表的意義相同，即，因此整理後的多項式可修正為：以上就是生成多項式分解及整理的方式。由上述方式可整理出生成多項式的內容為：上式即為經展開及整理後的生成多項式的內容，其內容可以用電路形態表示之，詳細將會在下一節中做敘述。2.3 Generator Polynomial的電路表示法 在2.2節中我們得到了的內容，其內容可以使用一個簡單架構的電路表示之，其電路架構如下所示：圖 2 RS Encoder的電路架構 圖 2為一個基本的RS Encoder，稱作Linear Feedback Shift Register（LFSR）。灰色部分的區塊為一般的D型正反器，可視為記憶體的功能，會將運算結果暫存於記憶體中，當下一個clock接收到之後則會將先前的運算結果推至下一級作運算功能，我們可以將此電路功能視為先前有提及之Modulo 2運算功能，因為它只有對 0與1作運算，以及作XOR的功能運算；圖中的係數對應到生成多項式的各項係數，在此則是對位元作出AND運算功能。輸入訊息內容將會分解成位元型式，當輸入的訊息都送完之後即可得到一組經過編碼後的RS code輸出序列。2.4 RS Encoding運算 在2.3節中我們知道了RS Encoder的LFSR電路架構及其運算的方式，接著我們在回歸到理論去探討其運算式的表達方式。我們先將訊息向左移個位元，如下所示：接著我們可以將上式分解成商除數餘數的方式表示之：其中為商數多項式、為餘數多項式。 由上式可知，當我們把除以後，會留下一組餘數多項式，此餘數多項式實際上就是RS編碼當中所要額外加上去的編碼區塊部份。但一開始只知道訊息及生成多項式時，並沒辦法直接將餘數多項式給提取出來，也無法馬上知道商數多項式又是為何；因此，我們下一步就是要將上式作改寫的動作，如下式所示：上式可以想像成移位後的訊息多項式與生成多項式作除法運算功能來求得餘數多項式。在此功能當中，其除法功能相當於作位元XOR運算，因此可視為兩者做運算，最後求得所需的餘數多項式。 最後我們將經過上式運算求得的餘數多項式嵌入至移位後的訊息多項式，也就是在之前低位元的位置之後，即完成一組RS編碼的輸出結果。其運算式如下式所示：以上就是基本的RS Encoder的執行步驟及運算過程。3. 使用Matlab驗證RS Encoder架構 接著我們將利用鈦思科技的數學運算軟體Matlab來做RS Encoder的模擬及驗證。透過程式碼的撰寫來學習如何利用Primitive Polynomial來建立一組Finite Element Table；其次利用此功能來創建出一組生成多項式，最後利用檔案呼叫的方式將檔案“input.dat”裡的內容輸入至程式碼中，進行RS Encoding的動作；最後檢查輸出結果並存放至檔案“output.xls”內，並驗證其編碼輸出的正確性。其程式碼功能、註解及輸出結果部分如下所示：% Clear all of the Matlab environmentclear all;clc;%Setting Variablesn=255; %Finite Elements數量與相關參數最大值設定parity=16; %Parity Lengthmidv=128; %Finite Elements Lengthcodelength=204; %DVB-Ts RS Encoding Structureblock=188; %(n, k, t)=(204, 188, 8)shorten=(n-codelength);a_i(1)=1; %在MATLAB中由於矩陣起始為1開始，因此參數從1起跳i_a(2)=0;%Using Primitive Polynomial: X8+X4+X3+X2+1for i=1:n %Create Finite Elements if a_i(i) = midv %檢查是否矩陣內容超過128 rr=(a_i(i)-midv)*2; %意即當內容產生溢位時，執行Modulo 2運算得到正確的內容 a_i(i+1)=bitxor(rr,29); reg=a_i(i); i_a(reg)=i; else a_i(i+1)=a_i(i)*2;%否則直接作一次位元左移，得到新的數值存放至下一位址中 reg=a_i(i); i_a(reg)=i; endend%Create Generator Polynomial g(X)g(1)=a_i(121);%如同a_i矩陣，矩陣存放參數皆從1開始g(2)=a_i(226);%g(X)係數設定g(3)=a_i(195);g(4)=a_i(183);g(5)=a_i(170);g(6)=a_i(148);g(7)=a_i(192);g(8)=a_i(92);g(9)=a_i(4);g(10)=a_i(77);g(11)=a_i(162);g(12)=a_i(103);g(13)=a_i(110);g(14)=a_i(108);g(15)=a_i(105);g(16)=a_i(121);fid =fopen(output.xls,w);%建立一檔案，用於存放編碼後的資料load input.dat; %Read file “input.dat” to get message symbols%RS Encoders Main Structurefor k=(1:block) %在此編碼程式下將會建立188筆編碼資料，每一筆總共有204個symbols for i=1:(parity) %其中message symbols佔188筆，增加的編碼資料佔16筆 r(i)=0; %r(i)為放置16筆parity symbols 的暫存器矩陣，先將內容清除 end for j=1:188 c=input(j); %讀取輸入檔案的內容，開始進行編碼 reg=r(parity); add=bitxor(reg,c); fprintf(fid,%Xt,c);%將內容輸入至剛建立的檔案內，並以16進制表示 for i=(parity):-1:2 reg1=g(i); if g(i)=0 & add=0 reg2=i_a(reg1); reg3=i_a(add); out1=rem(reg2+reg3+255*2,n)+1;%有時會出現此處運算結果為0的情況 out=a_i(out1); %在原編碼中確實有矩陣位置0的存在 else %但Matlab必須設定指向矩陣位置1處 out=0; %否則會出現錯誤 end r(i)=bitxor(r(i-1),out);end if g(1)=0 & add=0 reg2=i_a(g(1); reg3=i_a(add); out1=rem(reg2+reg3+255*2,n)+1; out=a_i(out1); else out=0; end r(1)=out; end end for i=(parity):-1:1 fprintf(fid,%Xt,r(i);%將編碼後產生的parity symbol end%放至檔案內，完成編碼 fprintf(n);endfclose(fid);%完成編碼後，關閉程式檔案中止寫入功能 執行上述程式碼後，將會得到如下表所示之結果（左上角為第一筆symbol，往右依序為第二筆、第三筆.直至最後一筆）：表 4 使用Matlab軟題執行上述RS編碼程式後的輸出結果2923BE84E16CD6AE529049F1F1BBE9EBB3A6DB3C870C3E99245E0D1C06B747DEB3124DC843BB8BA61F035A7D0938251F5DD4CBFC96F5453B130D890A1CDBAE32209A50EE407836FD124932F69E7D49DCAD4F14F2444066D06BC430B7323BA122F622919DE18B1FDAB0CA9902B9729D492C807EC599D5E980B2EAC9CC53BF67D6BF14D67E2DDC8E6683EF574961FF698F61CDD11E9D9C167272E61DF0844F4A7702D7E8392C53CBC9121E33749E0CF4D5D49FD4A4597E35CF3222F4CC0D4B1ACFE8BA72EF3AAB3E76D0A07824表 4中白色格子部分為我們輸入的訊息內容，後面黃色格子部分則是我們經過編碼之後所嵌入的parity symbols，形成RS code的架構。上表中的編碼內容經轉換成十進制之後，確認與任課教授提供之輸出結果無誤，因此確認其程式碼具有RS Encoder正確編碼的功能。結論 本報告利用數學運算軟體Matlab，透過撰寫其程式碼完成RS Encod