基于CRC的ASM信號維特比糾錯算法

張培欣, 王建新, *, 任 鵬, 楊樹樹, 宋海偉

(1. 南京理工大學(xué)電子工程與光電技術(shù)學(xué)院, 江蘇 南京 210094; 2. 南京電子設(shè)備研究所, 江蘇 南京 210007)

0 引 言

船舶自動識別系統(tǒng)(automatic identification system, AIS)是一種廣為人知且被廣泛使用的船舶自動追蹤系統(tǒng)[1-4],該系統(tǒng)由國際海事組織(international maritime organization, IMO)、國際航標協(xié)會(international association of marine aids to navigation and lighthouse authorities, IALA)等國際有關(guān)組織于20世紀90年代提出[5-7]。隨著國際海事貿(mào)易的日漸繁盛,海上航行安全、海事態(tài)勢感知、港口安全等需求也與日俱增,AIS早已不堪重負。因此,甚高頻數(shù)據(jù)交換系統(tǒng)(very high frequency data exchange system, VDES)應(yīng)運而生[8-12]。VDES整合了甚高頻數(shù)據(jù)交換(very high frequency data exchange, VDE)、應(yīng)用特定消息(application-specific messages, ASM)以及AIS,特有的功能及技術(shù)參數(shù),并且根據(jù)各種使用場景又細分為多種格式。

ASM主要被用于船與船、船與岸基站、船與衛(wèi)星之間傳遞特定的應(yīng)用消息[13]。根據(jù)ITU與IALA共同起草的建議書[14-15],ASM被劃分為10種格式,分別用鏈路配置編號1～10表示,其中4～10號采用了Turbo編碼,而1～3號沒有。眾所周知,Turbo編碼是一種能顯著提升信道容量的前向糾錯(forward error correction,FEC)編碼方式[16-20],這使得采用了Turbo編碼的4～10號ASM信號即使在較低信噪比(signal to noise ratio, SNR)下也有不錯的解碼性能,而沒有采用Turbo編碼的1～3號ASM信號的解碼性能則相對較差。本文利用ASM信號中同樣具有冗余信息的循環(huán)冗余校驗(cyclic redundancy check, CRC)字段糾錯,從而提高1～3號ASM信號的解碼性能。

傳統(tǒng)的基于CRC的糾錯算法主要有兩種:一種是查表式CRC糾錯算法[21],另一種是基于CRC的維特比糾錯算法[22-24]。顧名思義,查表式CRC糾錯方法首先需要一張表,這張表是根據(jù)參與CRC運算的信息比特長度以及CRC多項式生成的。當接收到的比特信息無法通過CRC時,就把接收到的信息比特按制表規(guī)則做相同運算,若在表中查到運算結(jié)果,則可根據(jù)查到的位置確定出錯比特位置。最簡單的查表式CRC糾錯算法僅能糾正1 bit錯誤,也有學(xué)者開發(fā)出了能糾正2 bits錯誤的查表式CRC糾錯算法[25],結(jié)合置信度判定,更是能實現(xiàn)多比特糾錯[26]。查表式CRC糾錯算法對解調(diào)性能確實有所提高,但提高幅度有限。相比于查表式CRC糾錯算法,基于CRC的維特比糾錯算法能糾正的錯誤比特數(shù)并不受限制,因此其糾錯性能要比查表式CRC糾錯算法優(yōu)異?；贑RC的維特比糾錯算法是在維特比解碼的過程中,讓CRC寄存器狀態(tài)也參與路徑轉(zhuǎn)移,最后在所有能通過CRC的路徑中,挑選與接收信號相關(guān)程度最大的路徑做后續(xù)解碼。基于CRC的維特比糾錯算法的缺點也很明顯,即計算量太大。其性能嚴重依賴于路徑的數(shù)目,因為路徑數(shù)目越多,嘗試的可能性越多,越有可能找到正確的結(jié)果。也有一些文章嘗試降低其計算量,例如符號狀態(tài)數(shù)減少的維特比算法[27-28],以及部分CRC輔助糾錯算法[29]。然而這些算法都需要在性能與計算量之間取舍。除了計算量太大這一問題以外,傳統(tǒng)維特比算法及其改進算法的分支度量設(shè)計過于理想化,其導(dǎo)致的性能損失也是不容忽視的一個問題。

為提高1～3號ASM信號的解碼性能,本文綜合了符號狀態(tài)數(shù)減少的維特比算法和部分CRC輔助糾錯算法,在盡量減少犧牲性能的前提下降低了計算量。同時,為了解決傳統(tǒng)分支度量計算公式的設(shè)計缺陷導(dǎo)致的性能下降,重新設(shè)計了路徑度量,并基于此推導(dǎo)出了新的分支度量。仿真表明,新的分支度量解決了傳統(tǒng)分支度量設(shè)計過于理想化導(dǎo)致的性能損失;使用12個CRC移位寄存器參與糾錯能夠?qū)崿F(xiàn)1 dB的誤幀率(packet error rate,PER)性能提升;同時,采用合理的符號狀態(tài)數(shù)降低策略,能在幾乎不損失性能的前提下進一步將計算量降低3/4。

1 應(yīng)用特定消息

根據(jù)ITU與IALA共同起草的建議書[14-15],ASM根據(jù)應(yīng)用場景的不同又分為兩大類:岸基ASM(terrestrial component of ASM,ASM-TER)和星載ASM(satellite component of ASM,ASM-SAT)。本文研究的1～3號ASM屬于ASM-TER,因此,本文所有內(nèi)容也都基于ASM-TER。ASM-TER幀格式如圖1所示。

圖1 ASM-TER幀格式Fig.1 ASM-TER frame format

本文的重點是解碼,因此圖1中其他部分在此不多作介紹,只重點介紹信息序列。信息序列是整個數(shù)據(jù)幀中真正待傳輸?shù)臄?shù)據(jù),但它并非是由待傳輸?shù)脑级M制信息直接填充而來,而是要經(jīng)過補零、CRC、FEC、比特加擾等一系列操作后得到的。根據(jù)標準,CRC采用32 bit的ITU-T V.42 {RD-5}計算(生成多項式以16進制表示為0x04C11DB7,移位寄存器初始狀態(tài)為全1);1～3號ASM信號的FEC倍率為1,即不使用FEC,所以在此不多作介紹;比特加擾多項式表示為F(x)=1+x-14+x-15,初始狀態(tài)設(shè)定為100 101 010 000 000。

生成ASM-TER幀后,按照標準,還要將幀按照π/4四相相移鍵控(quadrature phase shift keying,QPSK)方式映射。實際中,接收端一般會將π/4 QPSK信號調(diào)整成QPSK信號以便于解調(diào),對于ASM-TER信號,只要將相角為π/2整數(shù)倍的符號逆時針旋轉(zhuǎn)π/4即可。

rn=sn(α)+wn

(1)

式中:wn是復(fù)高斯白噪聲,其分布服從N(0,γN)(γN表示噪聲功率)。

2 傳統(tǒng)基于CRC的維特比糾錯算法

本文提出的算法是在傳統(tǒng)基于CRC的維特比糾錯算法基礎(chǔ)上改進實現(xiàn)的。維特比算法是由Viterbi于1967年提出的一種可用于任何符號序列的最大似然判決器[30-31]。其基本思想是構(gòu)造馬爾可夫鏈,然后在所有的可能路徑中,找出可能性最大的路徑,其對應(yīng)的符號序列即最終的解碼結(jié)果。為直觀理解維特比算法的思路和過程,下面以QPSK信號為例介紹維特比算法。

2.1 維特比算法

根據(jù)文獻[16]所述,對α的最優(yōu)非相干估計可表示為

(2)

(3)

(4)

式(4)的每次計算都需要將n時刻之前的接收信號和假設(shè)信號進行相乘累加,浪費了巨大的計算量。同時可以觀察到,當前時刻的路徑度量與下一時刻的路徑度量存在簡單的數(shù)學(xué)關(guān)系:

(5)

因此,路徑度量可以迭代計算而不用每次重新計算。代表相鄰時刻路徑度量之間迭代關(guān)系的式被定義為分支度量。為了限制計算量,可以僅使用當前時刻附近NT個符號計算分支度量(NT被稱之為記憶長度):

(6)

同時可以用n時刻前NT-1個符號定義當前的符號狀態(tài):

(7)

基于式(7)對于符號狀態(tài)的定義,式(6)可改寫為

(8)

(9)

有了轉(zhuǎn)移路徑度量和分支度量的計算公式,只需要在每個時刻將所有的可能轉(zhuǎn)移情況代入公式,計算出對應(yīng)的分支度量和轉(zhuǎn)移路徑度量即可;對于下一時刻的每個狀態(tài),在所有轉(zhuǎn)移到當前符號狀態(tài)的分支中,挑選轉(zhuǎn)移路徑度量最大的作為幸存路徑,同時將其轉(zhuǎn)移路徑度量作為自己的路徑度量,并記錄下路徑信息;最后,挑選路徑度量最大的一支,根據(jù)記錄的路徑信息依次前推,根據(jù)符號狀態(tài)與碼元的對應(yīng)關(guān)系查找碼元即可實現(xiàn)回溯解調(diào)。為了方便查詢,將所有可能的符號狀態(tài)列出即可得到符號狀態(tài)表。同理,將所有可能的轉(zhuǎn)移情況列出可構(gòu)成符號狀態(tài)轉(zhuǎn)移表。符號狀態(tài)表用于最后根據(jù)符號狀態(tài)查詢對應(yīng)的碼元從而實現(xiàn)解調(diào),符號狀態(tài)轉(zhuǎn)移表用于轉(zhuǎn)移過程中查詢可能的轉(zhuǎn)移過程。

2.2 基于CRC的維特比糾錯算法

維特比算法的思路是嘗試多種可能的碼序列,從中找出可能性最大的作為解碼結(jié)果。嘗試的組合越多,可能得到正確的結(jié)果的可能性越大,這種思路適合用于糾錯。一種簡單的思想[22]就是,將CRC移位寄存器中的值也作為狀態(tài)的一部分,參與路徑的轉(zhuǎn)移。這種方法就要求在每個分支計算分支度量和路徑度量的同時,也計算該分支對應(yīng)的CRC校驗碼。直到最后,在所有能通過CRC的路徑中,挑選可能性最大的一支作為解碼結(jié)果。

需要注意的是,由于標準中規(guī)定經(jīng)過CRC后的序列還需經(jīng)過比特加擾,因此在對接收信號進行糾錯解碼之前,要先進行解擾。由于加擾操作實際上等同于將原序列與一特定偽隨機序列進行模二加,因此只要將接收信號與同一偽隨機序列進行一次模二加即可實現(xiàn)解擾。

當接收信號出現(xiàn)少量錯誤時,由于傳統(tǒng)維特比算法是尋找與接收信號相關(guān)性最大(傳統(tǒng)算法中體現(xiàn)為路徑度量最大)的路徑,所以也只能解出與接收信號匹配的錯誤序列(對應(yīng)路徑記為路徑1)。而在基于CRC的維特比糾錯算法中,雖然路徑1依然是路徑度量最大的,但它并不能通過CRC。而在路徑1附近的其他路徑,就有可能剛好嘗試了正確的符號組合(記為路徑2)。雖然路徑2的路徑度量不是最大的,但由于其與路徑1的差別很小,所以其路徑度量也只會比路徑1的略小。同時由于CRC的隨機性,其他能通過CRC的路徑與接收信號的相關(guān)性通常不會很大,對應(yīng)的路徑度量也不大。因此,只要在最后所有能通過CRC的路徑中,挑選相關(guān)性最大的一支解碼,即可實現(xiàn)糾錯。

在基于CRC的維特比糾錯算法中,由于CRC移位寄存器中的值也參與了路徑轉(zhuǎn)移,路徑的狀態(tài)也不僅僅由符號狀態(tài)決定,而是由符號狀態(tài)和CRC狀態(tài)共同決定,因此,定義擴展狀態(tài)

(10)

對于n+1時刻的每個擴展狀態(tài),都有可能由多條不同的路徑轉(zhuǎn)移而來。因此,對于n+1時刻的每個擴展狀態(tài),要從所有的可能轉(zhuǎn)移路徑中選取對應(yīng)轉(zhuǎn)移路徑度量最大的作為幸存路徑,同時將其轉(zhuǎn)移路徑度量作為自己的路徑度量,并記錄下路徑信息。以此類推,直到結(jié)束。最后,挑選能通過CRC的路徑中路徑度量最大的一支,根據(jù)記錄的路徑信息依次從后往前,根據(jù)符號狀態(tài)表查找碼元即可實現(xiàn)回溯解調(diào)。

3 改進的基于CRC的維特比糾錯算法

傳統(tǒng)的基于CRC的維特比糾錯算法雖然性能出色,但也有其弊端。以本文的應(yīng)用場景為例,假設(shè)NT=3,則符號狀態(tài)數(shù)NS=4NT-1=16,CRC狀態(tài)數(shù)NCRC=232≈4.295×109,總的擴展狀態(tài)數(shù)達到了驚人的6.872×1010,這顯然是不可接受的。為此,需要降低擴展狀態(tài)的數(shù)量。本文提出的算法通過兩個方面降低擴展狀態(tài)數(shù):降低符號狀態(tài)數(shù)和降低CRC狀態(tài)數(shù)。

除了計算量巨大這一問題之外,傳統(tǒng)基于CRC的維特比糾錯算法還有一個不容忽視的問題,即由分支度量計算公式的設(shè)計缺陷導(dǎo)致的性能損失。為解決這一問題,重新設(shè)計了新的路徑度量計算公式,并在此基礎(chǔ)上推導(dǎo)出了新的分支度量計算公式,彌補了傳統(tǒng)算法的性能損失。

3.1 符號狀態(tài)數(shù)降低

符號狀態(tài)數(shù)的大小由記憶長度NT和每個符號的可能狀態(tài)數(shù)M決定,NS=MNT-1。因此,要想降低符號狀態(tài)數(shù)NS,要么降低M,要么降低NT,或者兩者同時降低。

降低NT是直接以性能損失為代價的。這是因為維特比算法的一個特點就是嘗試的可能路徑越多,解碼正確的可能性越大,而NT直接決定了路徑數(shù)量。因此,降低NT的方法不做考慮。

(11)

為了保證狀態(tài)轉(zhuǎn)移的唯一性,分組方式需要滿足兩個要求:

(1) 集合的數(shù)量Jk應(yīng)當是非增長的(J1≥J2≥…≥JK);

(2) 前一時刻的任一集合應(yīng)當是下一時刻中某個集合的子集。

J=[J1,J2,…,JK]

(12)

經(jīng)過上述操作,每個符號的可能狀態(tài)數(shù)不再是M而是Jk,此時的符號狀態(tài)數(shù)應(yīng)當是Jk的乘積,即

(13)

只要不是所有的Jk都等于M,那么符號狀態(tài)數(shù)就得到了降低。具體使用的時候,符號狀態(tài)表和符號狀態(tài)轉(zhuǎn)移表也要根據(jù)分組方式構(gòu)建。

3.2 CRC狀態(tài)數(shù)降低

傳統(tǒng)的基于CRC的維特比糾錯算法需要將所有CRC移位寄存器狀態(tài)全部用于糾錯,這就導(dǎo)致了擴展狀態(tài)數(shù)急劇增大。以本文應(yīng)用場景為例,ASM-TER采用的是32位CRC,就算僅用兩個符號表示符號狀態(tài),擴展狀態(tài)數(shù)也達到了驚人的109量級,并且CRC在這之中做出了極大的貢獻。很自然的就能想到,削減CRC參與糾錯的長度就能有效地以指數(shù)次冪減少擴展狀態(tài)數(shù)。

CRC狀態(tài)的本質(zhì)就是CRC移位寄存器中的值,可以將其進行拆分[29]：

(14)

3.3 新分支度量設(shè)計

除了巨大的計算量,傳統(tǒng)的基于CRC的維特比糾錯算法還有另外一個問題,即由于其分支度量計算公式的設(shè)計過于理想化導(dǎo)致的性能損失。下面將結(jié)合實例闡述這一問題。

為便于闡述,首先對式定義的分支度量進行改寫

(15)

要解決這一問題,只能重新設(shè)計路徑度量,并基于此推導(dǎo)新的分支度量?，F(xiàn)在讓我們重新回顧維特比算法的基本思想:尋找可能性最大的路徑。式及其后續(xù)的簡化變形都是用接收信號與假設(shè)信號之間的相關(guān)性衡量可能性,相關(guān)性越大則可能性越大。但是衡量可能性的方式不只相關(guān)性這一種,接收信號與假設(shè)信號之間的誤差也能用于衡量可能性,誤差越小可能性越大。因此,本文重新定義的路徑度量表示為

(16)

基于式(16)的分支度量可表示為

(17)

同樣為了限制存儲空間和計算量,僅使用當前時刻附近NT個符號計算分支度量:

(18)

此時,對α的估計為

(19)

至此,我們完成了新路徑度量的設(shè)計和新分支度量的推導(dǎo)。本文提出的算法步驟總結(jié)如下。

步驟 1狀態(tài)表構(gòu)建:根據(jù)需求選取合適的分組方式和參與糾錯的CRC寄存器位數(shù),并據(jù)此構(gòu)建符號狀態(tài)表、符號狀態(tài)轉(zhuǎn)移表。

步驟 2初始化:構(gòu)建路徑信息表與路徑度量表。路徑信息表用于記錄轉(zhuǎn)移到當前符號狀態(tài)之前的有用信息,路徑度量表用于記錄當前狀態(tài)的路徑度量。路徑度量表中,對應(yīng)CRC移位寄存器數(shù)值為全1的應(yīng)初始化為0,其他全部初始化為正無窮。

步驟 4狀態(tài)轉(zhuǎn)移:根據(jù)上步幸存的分支度量計算轉(zhuǎn)移路徑度量,同時計算CRC移位寄存器在轉(zhuǎn)移后的狀態(tài)。

步驟 5路徑幸存:在n+1時刻,每個擴展狀態(tài)都有多種可能的轉(zhuǎn)入路徑,選取其中轉(zhuǎn)移路徑度量最小的一條作為幸存路徑,并把其轉(zhuǎn)移路徑度量作為當前擴展狀態(tài)的路徑度量,同時記錄下路徑信息。

步驟 6回溯解調(diào):當算法運行至最后一個時刻,只保留對應(yīng)CRC狀態(tài)為全0的路徑,選取其中路徑度量最小的一個,并根據(jù)記錄的路徑信息逐步回溯解調(diào)。

4 性能仿真

采用1號ASM-TER信號進行仿真,符號速率Rs=9 600 ksps,假設(shè)接收信號中無頻偏、相偏,蒙特卡羅仿真1 000次,使用PER衡量各算法的性能。

4.1 基于新分支度量的維特比算法性能

為考察新分支度量對性能的影響,本仿真中所有算法均不包含糾錯功能且不降低符號狀態(tài)數(shù)?；谛路种Ф攘康木S特比算法性能如圖2所示。

圖2 基于新分支度量的維特比算法性能Fig.2 Performance of the new branch metric based Viterbi algorithm

圖2中SNR表示每比特能量比上噪聲功率譜密度(Eb/N0)。從圖2中可以看出,以PER=0.8為基準,記憶長度NT=3時的傳統(tǒng)維特比算法與相干解調(diào)有著約1 dB不到的性能差距,隨著NT的增加,性能差距逐漸縮小,但直到NT=5時依然有約0.3 dB的性能損失。同時從圖2中也可以看到,基于本文提出的新分支度量的維特比算法在NT=3時的性能就幾乎與相干解調(diào)算法重合。這充分說明了本文提出的新分支度量的有效性。

4.2 改進的基于CRC的維特比糾錯算法在不同CRC狀態(tài)數(shù)降低策略下的性能

本小節(jié)仿真了改進的基于CRC的維特比糾錯算法在不同CRC狀態(tài)數(shù)降低策略下的性能,本節(jié)中統(tǒng)一NT=3且不降低符號狀態(tài)數(shù),具體性能如圖3所示。從圖3中可以看到,以PER=0.8為基準,對于改進的基于CRC的維特比糾錯算法,只用4個CRC寄存器參與糾錯相比于相干解調(diào)算法幾乎沒有性能提升;當參與糾錯的CRC寄存器個數(shù)提高到8時,性能有了約0.3 dB的提升;而當使用12個CRC寄存器參與糾錯時,性能提升了約1 dB。圖3說明,使用部分CRC參與糾錯能獲得一定的性能提升。

圖3 本文提出算法在不同CRC寄存器個數(shù)下的性能Fig.3 Performance of the proposed algorithm with different number of CRC registers

4.3 改進的基于CRC的維特比糾錯算法在不同符號狀態(tài)數(shù)降低策略下的性能

本節(jié)仿真了改進的基于CRC的維特比糾錯算法在不同符號狀態(tài)數(shù)降低策略下的性能,本節(jié)中統(tǒng)一設(shè)定NT=3,參與糾錯的CRC寄存器位數(shù)NCr=12。具體性能如圖4所示。

圖4 本文提出算法在不同符號狀態(tài)數(shù)降低策略下的性能Fig.4 Performance of the proposed algorithm with different strategy of reducing the number of symbol statuses

從圖4中可以看到,在使用12位CRC寄存器參與糾錯的情況下,J=(4,4)、J=(4,2)以及J=(2,2)時PER性能幾乎相同,相較其他情況性能最好。同時,J=(4,1)、J=(2,1)、J=(1,1)時PER性能有較大損失,其性能與相干解調(diào)算法幾乎相同。同時從圖4中也可以看到,雖然J=(4,1)、J=(2,2)兩種策略下分支數(shù)量相同,但J=(4,1)時的PER性能卻更差,很顯然這是由于符號分組策略跳躍過大造成的。圖4說明,降低符號狀態(tài)數(shù)能在有效降低計算量的同時做到幾乎不損失性能。但符號狀態(tài)數(shù)也不能無限制降低,以本文應(yīng)用場景來說,綜合權(quán)衡性能與計算量,最合適的符號狀態(tài)數(shù)降低策略為J=(2,2)。

5 結(jié) 論

為提高1～3號ASM信號的解碼性能,本文提出了一種基于CRC的改進維特比糾錯算法。為解決基于CRC的維特比糾錯算法計算量太大的問題,本文從兩個方面減少了算法的路徑數(shù)從而減小計算量:一方面是通過將符號的可能狀態(tài)分組以降低符號狀態(tài)數(shù),同時詳細闡述了分組的基本要求和最佳分組方式;另一方面是通過削減CRC參與糾錯的長度減少CRC狀態(tài)數(shù),從而減少擴展狀態(tài)數(shù)。除了減少計算量,本文還詳細分析了傳統(tǒng)維特比算法分支度量的設(shè)計缺陷導(dǎo)致的性能損失。為解決這一問題,基于維特比算法尋找可能性最大的路徑的思想,本文重新推導(dǎo)了一個新的分支度量。仿真表明,在其他條件相同的情況下,新分支度量解決了傳統(tǒng)分支度量導(dǎo)致的性能損失問題,在僅用兩個符號定義符號狀態(tài)的情況下就幾乎與相干解調(diào)算法的性能一致。仿真還表明,對于ASM-TER信號,用8個CRC寄存器參與糾錯,就能將誤幀率性能相對于相干解調(diào)提升0.3 dB,用12個能提升1 dB。通過仿真發(fā)現(xiàn),對于ASM-TER信號來說,最佳的符號狀態(tài)數(shù)降低策略為J=(2,2),該策略在幾乎不降低解碼性能的同時,計算量僅為J=(4,4)完全不分組策略計算量的1/4。