改進的S模式糾錯算法?

梁豐??（中國西南電子技術(shù)研究所，成都610036）

改進的S模式糾錯算法?

梁豐??
（中國西南電子技術(shù)研究所，成都610036）

對檢測到錯誤的S模式應(yīng)答信號報文糾錯，傳統(tǒng)的方法是查表法，不僅效率很低，而且要求很大的存儲空間存放錯誤圖樣，不適合工程應(yīng)用。通過對S模式應(yīng)答信號的干擾情況、編譯碼方式及循環(huán)碼特性的深入研究，提出了余數(shù)計算的改進方法；再結(jié)合使用碼元置信度，實現(xiàn)了能快速、準(zhǔn)確定位誤碼并糾正它們的算法。改進的糾錯算法不僅效率高，而且占用系統(tǒng)資源少，易于硬件實現(xiàn)，其有效性已得到工程應(yīng)用的驗證。

S模式；應(yīng)答信號；突發(fā)脈沖干擾；循環(huán)冗余校驗；檢錯；糾錯

1 引言

循環(huán)冗余校驗（Cyclic Redundancy Check，CRC）是一種用于提高S模式通信質(zhì)量的差錯控制編碼技術(shù)，這種技術(shù)在信息碼元之外加入了多余的碼元，這些多余的碼元不載荷信息，只是用來校驗信息碼元在傳輸中是否出現(xiàn)差錯及為糾正錯誤信息碼元提供處理依據(jù)。根據(jù)S模式應(yīng)答信號處理流程，接收機不僅要對接收信號報文檢錯，還要求對檢測到錯誤的信號報文糾錯［1］。

CRC是在嚴(yán)密的數(shù)學(xué)理論基礎(chǔ)上建立起來的，其檢錯能力很強，實現(xiàn)方法也不難。為了能夠糾錯，要求每個可糾正的錯誤樣本必須與一個特定余數(shù)有一一對應(yīng)關(guān)系。對只有一位錯誤的信息，錯誤圖樣比較少，采用查表的方式糾錯還算簡單；但對于不止一位錯誤的信息，錯誤圖樣的數(shù)量急劇增加，不僅需要大量的存儲空間存放，查找也要花費大量時間。

突發(fā)脈沖對S模式應(yīng)答信號的干擾通常不止一位，使用查表法糾錯顯然不適合工程應(yīng)用。必須設(shè)計一種算法，通過建立余數(shù)與錯誤圖樣的某種對應(yīng)關(guān)系來找出誤碼的確切位置。本文首先對S模式應(yīng)答信號的主要干擾進行分析，然后對編譯碼及檢錯過程簡要說明，最后詳細(xì)敘述了改進的糾錯算法及其實現(xiàn)方法。糾錯的關(guān)鍵是對誤碼準(zhǔn)確定位，這正是算法改進的重點。糾錯過程中要使用碼元置信度，它攜帶了低置信度碼元的位置信息。改進后的糾錯算法已在硬件平臺實現(xiàn)，實際使用效果很理想。

2 S模式應(yīng)答信號的主要干擾

S模式應(yīng)答信號的中心頻率是1 090 MHz，單個脈沖寬度為0.5μs，碼速率為1 Mb／s。在同一空域中，存在多部應(yīng)答機同時工作的情況，應(yīng)答信號的頻率相同，工作方式為S模式和空中交通管制雷達信標(biāo)系統(tǒng)（Air Traffic Control Radar Beacon System，

ATCRBS）模式；還存在載波頻率在1 090 MHz附近的TACAN信號。此外，應(yīng)答信號的多徑效應(yīng)也是干擾的另一主要來源，這些信號相互疊加，形成脈沖串，屬于突發(fā)性干擾，當(dāng)空域中的飛機密度很小時，這些干擾不明顯；但當(dāng)空域中的飛機密度很大時，干擾會非常嚴(yán)重，尤其以ATCRBS模式應(yīng)答信號對S模式應(yīng)答信號的異步干擾最為嚴(yán)重，給接收機譯碼及報文使用帶來很大麻煩。

3 S模式應(yīng)答信號編譯碼過程

對S模式應(yīng)答信號糾錯，需要研究S模式應(yīng)答信號的編譯碼原理。S模式應(yīng)答信號由4個前導(dǎo)脈沖和56位（或112位）報文信息組成，報文信息的前32位（或88位）是數(shù)據(jù)塊（信息碼元），后24位是校驗塊（監(jiān)督碼元）［2］。報文信息編碼過程如圖1所示。

地面接收機對接收到的應(yīng)答信號先做濾波、變頻、放大等處理，然后根據(jù)脈沖幅度及位置關(guān)系進行譯碼。譯碼是編碼的逆過程，正確的譯碼直接關(guān)系到后面的糾錯能否成功，譯碼的同時還要對每一個碼元設(shè)置置信度以用于糾錯。譯碼后要對整個報文信息進行檢錯，檢錯計算的結(jié)果也用于糾錯處理。

4 碼元置信度判定

S模式應(yīng)答信號報文采用PPM方式，每1 b對應(yīng)1μs時間長度。如果前0.5μs或后0.5μs內(nèi)有脈沖幅度（主片），則該位碼元記為“1”或“0”；如果另0.5μs（從片）內(nèi)沒有脈沖幅度且主片的脈沖幅度來自天線的主波束而不是旁瓣，則這位的置信度記為高（通常以“0”表示），否則記為低（通常以“1”表示）。很多方法可實現(xiàn)S模式應(yīng)答信號報文譯碼及碼元置信度判定，文獻［3－4］描述了可行的算法。

5 糾錯前處理

S模式應(yīng)答信號報文是一種（56，32）循環(huán)碼（或（112，88）循環(huán)碼），生成多項式G（x）為24位。根據(jù)循環(huán)碼理論［5］，將報文信息中的數(shù)據(jù)塊M（x）向左移動24位得到的結(jié)果可表示為

那么，一個完整的報文信息為

式中，A（x）為特殊序列（比如詢問機代碼或飛機地址碼）。假設(shè)在傳輸過程中有最大長度為24位的脈沖干擾：

式中，j是距離數(shù)據(jù)塊末尾的位數(shù)，F(xiàn)（x）是最高指數(shù)不大于23次冪的多項式。E（x）是F（x）左移j位的結(jié)果，是最高指數(shù)不大于23＋j次冪的多項式，可得

在實際處理中，通常對除去（使用異或運算）特殊序列的報文計算余數(shù)S（x），則S（x）＝ε（x）。因此，如果報文信息在傳輸過程中沒有錯誤，使用CRC計算后可以得到預(yù)期余數(shù)“0”；相反，如果沒有得到預(yù)期的余數(shù)（比如還有未知余數(shù)ε（x）），則說明報文信息在傳輸過程中已被干擾或譯碼有錯（本文僅討論脈沖干擾造成的錯誤）。

有種特殊情況，如果j＝0，即干擾造成的錯誤只發(fā)生在報文信息的最低24位中。分析式（5）可知，等號左邊E（x）的最高次冪為23，而等號右邊G（x）的最高次冪為24，因此必須是e（x）＝0才能保證等式成立。由此可得ε（x）＝E（x），這說明計算的結(jié)果就是錯誤本身。

6 應(yīng)答信號報文糾錯

S模式應(yīng)答信號報文糾錯流程如下：

（1）判斷余數(shù)S（x）是否為零，不為零則需糾錯；

（2）找到誤碼的位置；

（3）糾正誤碼，即誤碼與“1”異或；

（4）再次進行檢錯計算，驗證糾錯是否成功，成功則輸出報文信息，否則申請重發(fā)或丟棄。

由前面敘述可知，突發(fā)脈沖對S模式應(yīng)答信號報文的干擾往往不止一位。根據(jù)循環(huán)碼原理，對于24位的干擾，可引起224－1種錯誤，每種錯誤對應(yīng)一個特定的余數(shù)，即存在224－1種錯誤樣本。如果將對應(yīng)每種錯誤的樣本事先計算出來并存儲，那么在糾錯過程中就可以通過查找對應(yīng)的錯誤樣本的方法找出誤碼的位置。但是，這種方法占用資源多，執(zhí)行效率很低，不合適用于實際工程中對S模式應(yīng)答信號報文進行糾錯。

6.1 改進的糾錯思路

如果對報文信息的干擾只出現(xiàn)在最低24位以內(nèi)，余數(shù)S（x）恰好與干擾E（x）相對應(yīng)，數(shù)據(jù)塊則不受影響。但實際的干擾可能對報文信息的任意一段造成影響，要準(zhǔn)確定位干擾出現(xiàn)的位置，除使用信息碼元和余數(shù)外，還需要碼元“置信度”的配合。

置信度的判定是隨著譯碼過程進行的，它為“高”時，說明該位碼元符合編碼規(guī)則，譯碼是準(zhǔn)確的；它為“低”時，說明該位碼元具有不確定性，而不能認(rèn)為該位一定有錯。因此，必須具備以下兩個條件的報文信息才能進行糾錯：一是余數(shù)S（x）不為零，如果余數(shù)為零，那就說明譯碼沒有錯誤，即報文信息沒有受到干擾，無需糾錯；二是置信度必須至少有一個為低，可以糾錯的碼元只針對置信度為低的。如果某碼元置信度為高，說明譯碼是準(zhǔn)確的，因此即使檢錯后發(fā)現(xiàn)報文信息有錯，也無法糾錯，只能丟棄報文信息。

糾錯的關(guān)鍵是準(zhǔn)確對誤碼定位，糾錯方法的改進本質(zhì)上是設(shè)計一種效率更高的定位誤碼的算法。前面提到如果干擾只出現(xiàn)在報文信息的最低24位中，計算得到的余數(shù)就是干擾本身。既然報文信息是一種循環(huán)碼，那么將它循環(huán)右移不會改變其特性，如果將誤碼移動到最低的24位中，就可以準(zhǔn)確對其定位，處理方法如下：

（1）將余數(shù)S（x）與置信度序列的最低24位比較；

（2）如果S（x）中所有出現(xiàn)“1”的位置與置信度序列最低24位中所有出現(xiàn)“1”（低置信度）的位置一一對應(yīng)，則誤碼即被定位，將報文中那些與S（x）中為“1”的位置相對應(yīng)的碼元糾正即可；

（3）如果不能一一對應(yīng)，將報文和置信度序列循環(huán)右移一位，并對移動后的報文計算新的余數(shù)S（x）；

（4）重復(fù)步驟1～3，直到這種一一對應(yīng)關(guān)系存在，否則錯誤就不能得到糾正。

從定位方法可以看出，每循環(huán)移動一位后都要重新計算一次余數(shù)S（x），而余數(shù)是通過對循環(huán)移動的整個報文計算得來，這樣的計算勢必花費較多時間。為提高定位誤碼的效率，需要優(yōu)化計算余數(shù)的算法。

6.2 高效的定位算法及實現(xiàn)

由于采用了循環(huán)碼，因此整個報文循環(huán)左移而產(chǎn)生的余數(shù)S1可由最初的余數(shù)S0產(chǎn)生，即

式中，S0和S1的最高次冪不大于23，Q0（x）和Q1（x）是商。式（8）中等號左邊多項式的最高次冪可能為24，而G（x）的最高次冪正是24，因此括號內(nèi)計算結(jié)果必為常數(shù)（0或1）才能保證等式右邊多項式的最高次冪不大于24。

分析式（8）可知，如果S0的最高次冪小于23（即系數(shù)s23＝0），那么這個常數(shù)必須為0；如果s23＝1，

xS0的最高次冪為24，而S1的最高次冪不大于23，等式左邊不為0，因此常數(shù)為1。

總結(jié)上述分析可得

式（9）即為余數(shù)S1的計算方法，它可直接由檢錯計算產(chǎn)生的結(jié)果S0和生成多項式G（x）使用移位及異或運算得出，不必對循環(huán)移動的報文重新計算，計算量自然少很多，效率必然很高。據(jù)此新算法設(shè)計的錯誤定位實現(xiàn)邏輯如圖2所示。如圖所示，用置信度最低24位初始化L寄存器，用原始余數(shù)初始化E寄存器。由于式（9）是循環(huán)左移得出的結(jié)論，所以必須將G（x）“高低位翻轉(zhuǎn)”得到G*（x），才能確保如圖右移計算的結(jié)果正確。

圖3所示為采用改進后的算法的S模式應(yīng)答信號報文糾錯流程，此圖也說明了糾錯的實現(xiàn)方法。

6.3 算法仿真

圖4所示為改進后的糾錯算法仿真計算數(shù)據(jù)。仿真使用Matlab按照圖3所示流程建立糾錯模型，將試驗中采集的一次全呼應(yīng)答報文作為輸入，該報文通過CRC檢錯發(fā)現(xiàn)了錯誤。檢錯后的報文經(jīng)過糾錯模型的處理，輸出的結(jié)果再經(jīng)過一次檢錯，最終證實糾錯是成功的。仿真結(jié)果驗證了算法的正確性。為便于分析，仿真過程中將每一步計算的數(shù)據(jù)輸出。

7 改進算法的試驗情況

從算法的推導(dǎo)過程可以看出，計算中使用了循環(huán)移位、異或及比較運算，這些運算非常適于硬件實現(xiàn)。S模式信號處理的實時性要求很高，在工程中使用FPGA實現(xiàn)該糾錯算法是很理想的選擇。糾錯的最大意義是當(dāng)空域中飛機密度很大時，它提高了信號的可用性，確保對飛機持續(xù)、穩(wěn)定地監(jiān)控；同時，減少了請求重發(fā)的概率、降低了系統(tǒng)的復(fù)雜性。

8 結(jié)束語

本文介紹的改進的S模式糾錯算法具有計算量小、效率高、正確率高、硬件實現(xiàn)容易等特點，該算法對由于突發(fā)脈沖干擾而造成錯誤的應(yīng)答信號進行糾錯，效果十分理想。對S模式應(yīng)答信號糾錯，除已介紹的算法外，以下兩點還需要深入研究。一是對接收信號正確譯碼并準(zhǔn)確判定置信度。報文信息及相應(yīng)的置信度是糾錯的前提，它們的正確性直接影響糾錯的結(jié)果，因此需要對譯碼及判定置信度的方法仔細(xì)研究。二是糾正隨機錯誤的算法。在S模式信號處理中使用了單脈沖、靈敏度時間控制（SensitivityTime Control，STC）等先進技術(shù)，這些技術(shù)可減少無線信道中隨機干擾引起的錯誤，但不可能完全消除；另外，譯碼過程也可能發(fā)生隨機錯誤。雖然這類錯誤所占比例很小，但也有必要對糾正它們進行研究。

［1］Doc9684 An／951，Manual on the Secondary Surveillance Radar（SSR）Systems［S］.

［2］ICAO，Annex 10 to the Convention on International Civil Aviation，Volume IV［S］.

［3］Galati G，Gasbarra M，Piracci E G.Decoding techniques for SSRMode Ssignal in high traffic environment［C］／／Proceedings of Radar Conference.［S.l.］：EURAD，2005：399－402.

［4］陳士毅.模式S應(yīng)答處理中的數(shù)據(jù)處理［D］.成都：電子科技大學(xué)，2006. CHEN Shi-yi.Data Processing of Mode SReply Processing［D］.Chengdu：University of Electronic Science and Technology of China，2006.（in Chinese）

［5］樊昌信，張甫翊，徐炳祥，等.通信原理［M］.5版.北京：國防工業(yè)出版社，2005. FAN Chang-xin，ZHANGFu-yi，XUBing-xiang，etal.Theory of Communication［M］.5th ed.Beijing：National Defense Industry Press，2005.（in Chinese）

LIANG Feng was born in Neijiang，Sichuan Province，in 1977.He received the M.S.degree froMUniversity of Electronic Science and Technology of China in 2006.He is now an engineer.His research concerns signal processing of the secondary radar.

Email：franvin－leung＠163.com

An IMproved AlgorithMfor Mode S Error Correction

LIANG Feng
（Southwest China Institute of Electronic Technology，Chengdu 610036，China）

To correct the Mode S reply message when the error is detected，the table lookup is a traditional method.But it has very low efficiency，and plenty of space is needed to store error patterns.Thismethod is not suitable for the engineering application.Through intensively studying the interference conditions，coding of Mode S reply and the characteristic of cyclic code，an improvedmethod of calculating remainder is presented.As a result，an algorithMis realized with which error codes can be located quickly and accurately by using the code confidence，and then be corrected.The improved algorithMnotonly has very high efficiency，but also takes up less systeMresources，and can be implemented easily in hardware.The effectiveness of improved algorithMhas been verified in the engineering application.

Mode S；replymessage；burst pulse interference；cyclic redundancy check；error detect；error correction

date：2012－10－26；Revised date：2013－03－18

??通訊作者：franvin－leung＠163.coMCorresponding author：franvin－leung＠163.com

TN911.72

A

1001－893X（2013）06－0755－04

梁豐（1977—），男，四川內(nèi)江人，2006年于電子科技大學(xué)獲碩士學(xué)位，現(xiàn)為工程師，主要研究方向為二次雷達信號處理。

10.3969／j.issn.1001－893x.2013.06.016

2012－10－26；

2013－03－18