實(shí)現(xiàn)卷積交織的幾種實(shí)用方法

1、徐元欣王匡仇佩亮浙江大學(xué) 信息與通信工程研究所, 浙江 杭州 310027摘要 卷積交織在數(shù)字通信系統(tǒng)中得到了廣泛的應(yīng)用 本文將分析卷積交織原理 然后提出幾種實(shí)用的實(shí)現(xiàn)方法 并對(duì)其性能進(jìn)行了分析對(duì)比關(guān)鍵詞 卷積交織 atsc dvb rs 碼 hdtv中圖分類號(hào) tn911.22 文獻(xiàn)標(biāo)識(shí)碼 a引言1在數(shù)字通信中 信道中除了隨機(jī)干擾 常常由外來的脈沖干擾會(huì)引起突發(fā)錯(cuò)誤如電機(jī)的突發(fā)噪聲電火花等 同時(shí)同頻道干擾 相位噪聲 多徑和衰落信道等都會(huì)引起突發(fā)錯(cuò)誤 也就是說發(fā)生的錯(cuò)誤 有很強(qiáng)的相關(guān)性 當(dāng)發(fā)生一個(gè)錯(cuò)誤時(shí) 往往波及后面的很多數(shù)據(jù) 導(dǎo)致一片數(shù)據(jù)都發(fā)生錯(cuò)誤 使突發(fā) 錯(cuò)誤的數(shù)目超過了糾錯(cuò)碼的糾錯(cuò)能力

2、為了使糾錯(cuò)碼能抵抗這些突發(fā)錯(cuò)誤 在實(shí)際應(yīng)用中糾錯(cuò)編碼往 往要結(jié)合數(shù)據(jù)交織技術(shù) 在發(fā)送端加上數(shù)據(jù)交織器 在接收端加入去交織器 使得信道的突發(fā)錯(cuò)誤分 散開來 把突發(fā)差錯(cuò)信道改造成獨(dú)立的隨機(jī)差錯(cuò)信道 從而可以充分發(fā)揮糾錯(cuò)編碼的作用1 加上交 織后 系統(tǒng)的糾錯(cuò)性能可以提高好幾個(gè)數(shù)量級(jí) 美國 astc 和歐洲 dvb 的數(shù)字電視傳輸標(biāo)準(zhǔn)中都采 用了數(shù)據(jù)交織技術(shù)23下面以 atsc vsb 傳輸系統(tǒng)(如圖 1)為例加以說明 為了提高通信系統(tǒng)的可靠性 糾錯(cuò)編碼則可 采用級(jí)聯(lián)碼的方式來進(jìn)行誤碼控制 一般采用兩級(jí)串聯(lián) 第一級(jí)采用具有很強(qiáng)糾錯(cuò)能力的極大最小距 離可分碼(mds 碼)rs 碼 稱為外碼 第二級(jí)可采用

3、短的分組碼或卷積碼 稱為內(nèi)碼4 atsc vsb傳輸系統(tǒng)采用了這種形式rs(207,187)作為外碼了存在前面講述的突發(fā)錯(cuò)誤外接收8 電平 tcm 格狀編碼作為內(nèi)碼在數(shù)據(jù)傳輸中除端內(nèi)碼采用 viterbi 算法進(jìn)行格狀譯碼時(shí)當(dāng)接收信號(hào)的信噪比較低時(shí)會(huì)出 現(xiàn)差錯(cuò)擴(kuò)散也會(huì)引起突發(fā)錯(cuò)誤5這些突發(fā)錯(cuò)誤就可能超過 rs 碼的糾錯(cuò)能力因此為了充分發(fā)揮 rs 碼的 糾錯(cuò)能力在 rs 外碼和格狀編碼內(nèi)碼之間加入交織器dvb 的傳輸系統(tǒng)采用的是 rs(204,184)碼在 rs 碼后 也加入了交織器下面介紹卷積交織的原理然后提出實(shí)現(xiàn)卷積交織的實(shí)用優(yōu)化方法上頻(a)發(fā)射部分諧濾波器(b)接收部分圖 1 astc

4、vsb 傳輸系統(tǒng)卷積交織原理實(shí)際上交織過程也可以算是一個(gè)編碼過程2通過把經(jīng)過糾錯(cuò)編碼的數(shù)據(jù)進(jìn)行一定的排列組合提高原有糾錯(cuò)碼的糾突發(fā)錯(cuò)誤能力在數(shù)字通信中一般采用的同步交織有兩種同步與定時(shí)數(shù)據(jù) 去 擾rs 解 碼去 交 織tcm 解 碼相 位 跟 蹤均 衡ntsc 抑制if濾波 和解調(diào)調(diào)器數(shù) 據(jù) 擾 碼rs 編 碼交 織tcm 編 碼復(fù) 接導(dǎo) 頻 插 入vsb 調(diào) 制射 頻變段 同 步 場(chǎng) 同 步8電路與系統(tǒng)學(xué)報(bào)第 6 卷(1) 塊交織它是一個(gè)二維存儲(chǔ)器陣列 (n b)將數(shù)據(jù)先按行寫入然后按列讀出完成交織過程相應(yīng)地去交織過程是將數(shù)據(jù)按列寫入再按行讀出塊交織結(jié)構(gòu)簡單但數(shù)據(jù)延遲時(shí)間長而且所 需的存儲(chǔ)器

5、比較大7(2) 卷積交織( n2 , n1 ) 的卷積交織器滿足如下要求在該交織器輸出上的任何一個(gè)長度為 n2 的數(shù)據(jù)串中不包含交織前原來數(shù)據(jù)序列中相距小于 n1 的任何兩個(gè)數(shù)據(jù)顯然在發(fā)送端采用交織器在接收端就要用去交織器把數(shù)據(jù)恢復(fù)過來可以證明 (n2 , n1 ) 交織器相對(duì)應(yīng)的去交織器自身是一個(gè)7( n1 , n2 ) 交織器對(duì)于 ( n2 , n1 ) 的卷積交織器來說有兩個(gè)性能是設(shè)計(jì)者所關(guān)心的一個(gè)是編碼延遲 d它定義為從數(shù)據(jù)經(jīng)過交織和去交織后所引起的最大延遲號(hào)單元對(duì)于 ( n2 , n1 ) 交織器有如下關(guān)系 d n2 (n1 1)另一個(gè)是交織器和去交織器的存儲(chǔ)容量 s 和 su 個(gè)符

6、(1) s s u d設(shè)計(jì)交織器時(shí)希望其 d 和 ssu 盡量小卷積交織器最早由ramsey 7 和forney 6 提出下面要討論的這種結(jié)構(gòu)由forney給出ramsey的方案實(shí)質(zhì)上與之類似圖2表示了卷積交織器和去交織器的原理交織器的輸入端的輸入符號(hào)數(shù)據(jù)按順序分別進(jìn)入b 條支路延遲器每一路延遲不同的符號(hào)周期第一路無延遲第二路延遲m 個(gè)符號(hào)周 期第三路延遲2m 個(gè)符號(hào)周期.第b 路則延遲(b-1)m個(gè)符號(hào)周期交織器的輸出端按輸入端的工作節(jié)拍分別同步輸出對(duì)應(yīng)支路經(jīng)延遲的數(shù)據(jù)也就是卷積交織每條支路符號(hào)數(shù)據(jù)的延遲節(jié)拍為di=( i -1)mbi=1,2, b(2)去交織器的各個(gè)支路的延遲數(shù)與交織器相

7、反第一路延遲(b-1)m個(gè)符號(hào)周期第二路延遲(b-2)m個(gè)符號(hào)周期第三路延遲(b-3)m 個(gè)符號(hào)周期.第b 路則無延遲也就是卷積去交織每條支路延遲為dui=( b- i )mbi=1,2, b(3)由此可知該卷積(去)交織器有以下性質(zhì)6(1) 數(shù)據(jù)經(jīng)過交織器與去交織器所產(chǎn)生總延遲(即編碼延遲)d =b(b-1)m 個(gè)符號(hào)周期(2) 交織器或去交織器所需的存儲(chǔ)容量s = su = b(b-1)m/2 個(gè)符號(hào)單元(3) 交織器的兩個(gè)相鄰的輸入數(shù)據(jù)經(jīng)過交織器后出現(xiàn)在輸出端時(shí)其間隔增加為bm個(gè)符號(hào)周期交織器輸入端任何間隔低于bm個(gè)符號(hào)的兩個(gè)符號(hào)在交織器輸出端最小間隔為b個(gè)符號(hào) 該卷積交織器其實(shí)就是前面

8、提到的n2 =bm, n1 =b的卷積交織器8112i3去解碼來自b-2糾錯(cuò)編碼ib-1bbi=1,2, b圖 2 卷積交織器和去交織器在實(shí)際應(yīng)用中m值的選擇與交織器前面級(jí)連的糾錯(cuò)碼的碼字長有關(guān)若糾錯(cuò)碼采用(n, k)b碼為了實(shí)現(xiàn)方便一般取:n = bm(4)(b-1)mm(i-1)m2m信道2m(b- i)mm(b-1)m9第 1 期徐元欣等 實(shí)現(xiàn)卷積交織的幾種實(shí)用方法如atsc 采用rs(207,187)以及b=52, m=4的卷積交織器這里rs碼的碼字長為207但加上段同步頭每個(gè)傳輸包長為208dvb采用rs(204,188)卷積交織器的b=12,m=17稱該(去) 交織器為 (n b)

9、卷積(去)交織器糾錯(cuò)碼(n, k)級(jí)連上(n b)卷積(去)交織器可近似于一個(gè)糾錯(cuò)碼(bn, bk)1 這也可由圖3的示意圖得知它表示了編碼的符號(hào)數(shù)據(jù)經(jīng)交織后的順序被交織打亂的情況其中打斜線的每 個(gè)符號(hào)為編碼來的某個(gè)包的連續(xù)數(shù)據(jù)可看出經(jīng)過(n b)卷積交織器后由糾錯(cuò)碼rs(n,k)編碼來的n長的連續(xù)的包數(shù)據(jù)被分散到b個(gè)包中同時(shí)經(jīng)交織后的數(shù)據(jù)如果加入了長為 bt 的突發(fā)錯(cuò)誤經(jīng)過 去交織后這些長為bt個(gè)的突發(fā)錯(cuò)誤就被分散到相鄰的b個(gè)包中每個(gè)包t個(gè)錯(cuò)誤假設(shè)糾錯(cuò)碼(n, k)的 每個(gè)碼字包能糾t個(gè)錯(cuò)這樣加入了該卷積交織器后能糾長為 l=bt 的突發(fā)錯(cuò)誤在atsc 中 t=10能抵抗l=520 個(gè)符號(hào)周

10、期的突發(fā)錯(cuò)誤 dvb中個(gè)符號(hào)周期的突發(fā)錯(cuò)誤可以看出(n b) 卷積交織與(n突發(fā)錯(cuò)誤性能數(shù)據(jù)延遲上是相同的t=8 能抵抗 l=96b)塊交織在對(duì)付但前者所需的總存儲(chǔ)器容量比后者少一半故實(shí)際中常采用卷積交織3卷積交織的實(shí)現(xiàn)方法3.1 移位寄成器法圖 3 交織后數(shù)據(jù)分布示意圖由圖2 可知卷積交織實(shí)際就是將數(shù)據(jù)進(jìn)行不同的延遲以使連續(xù)的數(shù)據(jù)分散開來簡單的方法就是每條延遲支路可用fifo 移位寄成器來實(shí)現(xiàn)這里稱為移位寄成器法 去交織器都所需的寄成器數(shù)目s = s u = b(b-1)mk/2實(shí)現(xiàn)時(shí)最直觀對(duì)于交織器和(5)這里假定每個(gè)符號(hào)為 k比特當(dāng)b和m比較小時(shí)采用該方法簡單實(shí)用但b和m 都比較大時(shí)采用

11、該方法就需的大量的寄成器如實(shí)現(xiàn)dvb 的交織器和去交織器所需的寄成器數(shù)都是8976atsc 則需42432目前在fpga中實(shí)現(xiàn)或 asic 芯片設(shè)計(jì)中都很難承受這么多的寄成器采用該方法實(shí)現(xiàn)起來代 價(jià)非常大3.2 ram分區(qū)循環(huán)移位法 該方法就是將移位寄成器法中的(去)交織的各個(gè)支路的fifo延遲采用ram來實(shí)現(xiàn) 通過控制ram的讀寫就能實(shí)現(xiàn)卷積交織為了敘述方便下面以卷積交織為例講述這種方法如圖4所示除了第1條支路不需延遲外將ram分為b-1個(gè)區(qū)每區(qū)對(duì)應(yīng)于一條支路每區(qū)的大小si= ( i - 1)mi = 1,2, b(6)為了充分利用ram的空間 對(duì)于每區(qū)按 讀-修改- 寫 方式進(jìn)行循環(huán)操作

12、也就是在每個(gè)符號(hào)節(jié)拍當(dāng)前的讀寫地址相同 只是要先讀出該地址單元的原來的符號(hào)數(shù)據(jù)后 再寫入新的數(shù)據(jù) 每區(qū)自己的相 對(duì)地址ai 每更新一個(gè)單元按模 si 進(jìn)行循環(huán)加1 該區(qū)是每隔b個(gè)符號(hào)數(shù)據(jù)節(jié)拍才更新一個(gè)單元 也就 是ai 每b個(gè)數(shù)據(jù)才加1 由此可得出每路數(shù)據(jù)延遲di = s i b = ( i -1)mbi = 1,2, b上式(7)與 (2)式相同也就是每條支路達(dá)到了所需的延遲該方法能完成卷積交織 設(shè)第i區(qū)的首地址為hi 則(7)i 1i 1hi s j ( j 1)mi = 2, b(8)j 1 j 1所以對(duì)于整個(gè)ram的第n個(gè)節(jié)拍的讀寫地址指針應(yīng)為(n = 0,1,2, . )an= hi

13、+aiai = (ai +1) mod si i = n mod b +1(9)nbb b數(shù)據(jù)方 b10電路與系統(tǒng)學(xué)報(bào)第 6 卷該處的i表示第n個(gè)節(jié)拍的交織數(shù)據(jù)對(duì)應(yīng)的第i條延遲支路由式(6) (8)和(9)就產(chǎn)生ram的讀寫地址(見圖5)其中模b復(fù)位器按交織輸入的符號(hào)數(shù)據(jù)節(jié)拍在每包數(shù)據(jù)起始時(shí)從0開始進(jìn)行模b計(jì)數(shù)并在計(jì)數(shù) 值為0時(shí)停止讀寫ram和1時(shí)產(chǎn)生清0復(fù)位信號(hào)相類似地可采用ram分區(qū)循環(huán)移位法來實(shí)現(xiàn)卷積去交織這里不祥述可看出采用該方法實(shí) 現(xiàn)卷積交織所使用的存儲(chǔ)器為ram其容量(bit)為bs = s u = ) si = b(b-1)mk/2(10)i =2與移位寄成器法所需數(shù)目相同對(duì)于實(shí)

14、現(xiàn)dvb的交織器和去交織器都只需1122 8=8976比特的ram而atsc 都只需5304 8=42432比特的ram使所用存儲(chǔ)器的代價(jià)最小實(shí)現(xiàn)成為可能但這種方法還需用于存放每條支路的相對(duì)地址的fifo3.3ram整塊循環(huán)移位法 1 其容量為(b-1)個(gè)單元每個(gè)單元的大小為 log 2 max si j123in輸出輸入 i i ib圖 5 ram 分區(qū)循環(huán)移位法地址產(chǎn)生框圖圖 4 ram 分區(qū)循環(huán)移位法原理同樣為了敘述方便下面以卷積交織為例講述這種方法該方法是將分區(qū)循環(huán)讀寫改為整塊循環(huán)讀寫 要求每條支路的當(dāng)前輸入數(shù)據(jù)是靠相鄰的下一條支路的讀寫地址指針來輸出以達(dá)到延遲的目 的 其原理如圖6所

15、示 同樣為了充分利用ram的空間 對(duì)ram按 讀-修改-寫 方式進(jìn)行操作 假 設(shè)當(dāng)前交織的第n節(jié)拍的數(shù)據(jù)是參與第i條延遲支路 對(duì)應(yīng)的ram讀寫地址(絕對(duì))為an 支路地址為ai= an 那么第n+1 節(jié)拍的數(shù)據(jù)就對(duì)應(yīng)于第i +1 條延遲支路 相應(yīng)的讀寫地址為an+1 支路地址為ai+1 =an+1那么an+1 = an + ( i-1)mi = n mod b +1(11)經(jīng)過b個(gè)節(jié)拍也就是卷積交織一個(gè)b路循環(huán)后的第n+b節(jié)拍的數(shù)據(jù)應(yīng)連接第i條延遲支路第n+1+b節(jié)拍的數(shù)據(jù)就對(duì)應(yīng)于第i +1條延遲支路這時(shí)第i +1條的支路地址ai+1 應(yīng)朝第i條的支路地址ai 的方向前進(jìn)一拍以達(dá)到對(duì)第i條支路

16、的延遲作用比如圖6中畫出的虛線支路1假定ram容量為s個(gè)單元(12)2則an+b = an+b mod s = (an 1) mod s又由圖6可知如不限定ram容量則ban+b an= (i 1)m = b(b-1)m/2i 1結(jié)合式(12)(13)就可得該方法所需的ram的單元數(shù)目應(yīng)為s = b(b-1)m/2 +1(13)(14)這樣第i條延遲支路寫入的數(shù)據(jù)要經(jīng)過( i -1)m個(gè)b路循環(huán)后的第i +1條延遲支路時(shí)刻才讀出由此可得出每條支路數(shù)據(jù)的延遲為di = ( i -1)mb +1i = 1,2, b(15)寄成器寄成器ramaahs存放相對(duì)地址ms模 b 復(fù)位i = n mod b

17、 +1 復(fù)位m2m(i-1)mram(b-1)m取模 s iif si , 賦 011第 1 期徐元欣等 實(shí)現(xiàn)卷積交織的幾種實(shí)用方法將上式與(2)式相比較該方法的每條支路數(shù)據(jù)比 (2)多延遲一個(gè)節(jié)拍但輸出數(shù)據(jù)的相互順序分布滿足卷積交織的要求在ram容量為s單元時(shí)第n節(jié)拍的數(shù)據(jù)時(shí)刻的讀寫ram的地址an+1 = an + ( i-1)m mod si = n mod b +1(16)該處的i表示第n個(gè)節(jié)拍的交織數(shù)據(jù)對(duì)應(yīng)的第i條延遲支路由式(14)(16)可得到ram整塊循環(huán)移位法的地址產(chǎn)生框圖如圖7所示其中模b復(fù)位器按交織輸入的符號(hào)數(shù)據(jù)節(jié)拍在每包數(shù)據(jù)起始時(shí)從b-1開始 進(jìn)行模b計(jì)數(shù)并在計(jì)數(shù)值為0

18、和1時(shí)產(chǎn)生清0復(fù)位信號(hào)同樣可采用 ram整塊循環(huán)移位 法來實(shí)現(xiàn)卷積去交 織這里不祥述 該方法所需存儲(chǔ)器 ram的容量只比前 面ram分區(qū)循環(huán)移 位法多一個(gè)單元 對(duì)于實(shí)現(xiàn)dvb 的交 織器和去交織器都 只需 11238=8984輸出輸入比特的 ram而atsc 都只需53058=42440 比特的ram可看出該方法就省去了前面所需的fifo控制也簡單使實(shí)現(xiàn)的代價(jià)更小所以是用ram實(shí) 現(xiàn)卷積交織的最優(yōu)化方法但該方法對(duì)卷積交織的數(shù)據(jù)都要多延遲一個(gè)符號(hào)節(jié)拍圖8是仿真采用ram整塊循環(huán)移位法來實(shí)現(xiàn)atsc (b=52, m=4, s=5035)的卷積交織的ram地址的某幾段的結(jié)果假設(shè)an 初始值為510

19、1實(shí)際中可為任意初值圖 6ram 整塊循環(huán)移位法原理圖 7ram 整塊循環(huán)移位法地址產(chǎn)生框圖n=00, 0,4, 12, 24, 40, 60, 84, 112, 144, 180, 220, 264, 312, 364, 420, 480, 544, 612, 684,760, 840, 924,1012,1104,1200,1300,1404,1512,1624,1740,1860,1984,2112,2244,2380,2520,2664,2812,2964,3120,3280,3444,3612,3784,3960,4140, 432,4512,4704,4900,5100n=2085

20、301,5301, 0, 8, 20, 36, 56, 80, 108, 140, 176, 216, 260, 308, 360, 416, 476, 540, 608, 680,756, 836, 920,1008,1100,1196,1296,1400,1508,1620,1736,1856,1980,2108,2240,2376,2516,2660,2808,2960,3116,3276,3440,3608,3780,3956,4136,4320,4508,4700,4896,5096n=10660,5100,5104,5112,5124,5140,5160,5184,5212,524

21、4,5280, 15, 59, 107, 159, 215,275, 339, 407, 479,555, 635, 719, 807, 899, 995,1095,1199,1307,1419,1535,1655,1779,1907,2039,2175,2315,2459,2607,2759,2915,3075,3239,3407,3579,3755,3935,4119,4307,4499,4695,4895,圖 8采用 ram 整塊循環(huán)移位法實(shí)現(xiàn)卷積交織的仿真結(jié)果由圖8可看出經(jīng)過卷積交織第n=0節(jié)拍的數(shù)據(jù)延遲了1個(gè)節(jié)拍第n=1節(jié)拍的數(shù)據(jù)延遲了209個(gè)節(jié)拍 .第n=51節(jié)拍的數(shù)據(jù)延遲了106

22、09個(gè)節(jié)拍寄成器復(fù)位器5100模 b復(fù)位寄成器rams取模 sif s ,減去 sanm1,23 mi(i-1)mi+1ramb(b-1)m1,212電路與系統(tǒng)學(xué)報(bào)第 6 卷結(jié)束語本文在分析了卷積交織原理基礎(chǔ)上提出了三種實(shí)現(xiàn)方法 法和ram整塊循環(huán)移位法其性能對(duì)比見表1當(dāng)卷積交織的b4移位寄成器法ram分區(qū)循環(huán)移位m比較大時(shí)則所需的存儲(chǔ)量就大ram整塊循環(huán)移位法 尤其后者ram整塊循采用ram實(shí)現(xiàn)卷積交織的方法使實(shí)現(xiàn)成為可能其中的ram分區(qū)循環(huán)移位法分別在我國hdtv的第1代第2代樣機(jī)中得到了成功應(yīng)用從成本和規(guī)模上講 環(huán)移位法在hdtv的asic 芯片設(shè)計(jì)中具有重要的意義表1三種實(shí)現(xiàn)方法對(duì)比方

23、法所需總的存儲(chǔ)器控制數(shù)據(jù)總延遲(符號(hào))周期復(fù)位總的規(guī)模b(b-1)m b(b-1)m移位寄成器法ram 分區(qū)循環(huán)移位法 ram 整塊循環(huán)移位法b(b-1)m k 個(gè)寄成器b(b-1)m k 比特 ram簡單復(fù)雜,需 fifo可以可以很大較小 最小b(b-1)m +2 可以b(b-1)m+1k 比特 ram 較簡單參考文獻(xiàn)1 proakis, j. g. . digital communicationsm. 3rd edition. new york: mcgraw-hill, 1995. 468-470. 2 atsc. atsc digital television standards .

24、doc. a/53 , 1995-09.3 etsi. european standard (telecommunications series) dvbs. 1997.4 姚慶棟 梁慧君 戴文琪. 數(shù)字無線傳輸m. 杭州: 浙江大學(xué)出版社 1992. 247-248. 5 王新梅 肖國鎮(zhèn). 糾錯(cuò)碼原理與方法m. 西安: 西安電子科技大學(xué)出版社 1996.6 forney, g.d.burst-correcting codes for the classic bursty channelj. ieee trans. comm. tech., 1971, 19:772-781. 7 ramsey j l. realization of optimum interleavers j. ieee trans. inform. theor y, 1970, 16: