基于FPGA 的改进ADS-B纠错算法设计与实现

胡铁乔，刘丹阳，李阳波

（中国民航大学天津市智能信号与图像处理重点实验室，天津 300300）

基于FPGA 的改进ADS-B纠错算法设计与实现

胡铁乔，刘丹阳，李阳波

（中国民航大学天津市智能信号与图像处理重点实验室，天津 300300）

基于S模式数据链技术的广播式自动相关监视（ADS-B）系统，凭借其建设成本低及其精度高的优点而广泛用于空中交通管制等领域。然而，ADS-B系统的广播性和信号非加密特点，在高A/C应答异步干扰（FRUIT）交叠的情况下，使得信号在接收端被接收时极易产生误码。针对这一问题，结合FPGA的并行运算特性与资源配置情况，在循环冗余编码（CRC）校验和置信度判定的基础上，提出了一种基于FPGA的改进ADS-B纠错算法。给出了该改进算法的设计方案，并通过FPGA平台进行了大量实采信号的测试验证。经多次测试的结果表明：在不影响纠错性能的条件下，该改进算法可节省硬件开销，提升信号处理速度，保证了信号传输的可靠性。

ADS-B系统；CRC校验；比特置信度；纠错；FPGA

?

广播式自动相关监视（ADS-B）是一种基于卫星导航系统和空-空、地-空、地-地数据链通信的航空器运行监视技术，属于国际民用航空组织（ICAO，international civilaviation organization）定义的新航行系统（CNS/ATM，communications，navigation，surveillance/air traffic management）范畴。机载设备通过周期性广播ADS-B信号，实时地、自发地播报飞机的高度、经纬度、速度、呼号等精准信息。ADS-B是一种可弥补传统二次雷达所存在的监视盲区、价格相对低廉且监视能力较强的新技术。近年来，许多国家先后发布相关政策，大力推行ADS-B技术的相关应用。

基于S模式的ADS-B广播信号的发射频率为1 090MHz，与二次监视雷达下行信号的发射频率相同。因此，在高A/C广播异步干扰（FRUIT，false replies unsynchronized to interrogator transmission）交叠的情况下，信道占用率较高，极易导致ADS-B接收设备产生误码问题，从而有必要对ADS-B信号的误码进行检错纠错处理。常用的ADS-B广播信号纠错方法有以下3种：“Conservative”纠错技术[1]是一种基于滑窗技术的应用，但只可纠正在大小为24 bits窗内的错误位；“WholeMessage”技术[1]是将整个A/C广播FRUIT干扰对数据位及置信度的影响进行建模，可纠正多达5个不重叠FRUIT交叠环境下的错误，但处理方式较为复杂，且应用条件限制较多；“Brute Force”技术[1-3]是最为常用的ADS-B广播信号纠错技术，可纠正随机分布不超过d-1（d位CRC码的汉明距离）比特的错误图样，较之前两种方法操作性更强。

文献[2-4]均采用“Brute Force”纠错算法，算法灵活度较高，不足之处在于：①算法中的循环在FPGA中实现较为复杂；②该算法以串行数据处理的方式先进行CRC检错再进行纠错，纠错时涉及的对应取反操作将在FPGA实现过程中占用大量的查找表资源。文献[5]采用“Conservative”与“Brute Force”结合的纠错算法，可纠正大于5位比特的错误，提升了系统的纠错能力，但在FPGA中的实现复杂度也相应提升。本文提出的改进纠错方法省略了“Brute Force”纠错技术中的多个环节，优化了数据处理流程，硬件平台测试结果表明，在不影响纠错性能的条件下，本方法具有较强的可行性和准确性。

1 ADS-B信号处理流程

基于S模式的ADS-B广播信号采用脉冲位置调制（PPM,pulse position modulation），信号的总长为120 μs，其中包含8μs的报头及112μs的数据位，如图1所示。

图1 ADS-B广播信号波形图Fig.1 W aveform of ADS-B signal

ADS-B广播信号的处理主要针对两方面：报头检测、信号解调、纠错检错和报文消息解码。

如图2所示，信号经A/D模块转换为数字基带信号后，首先要进行的是信号的报头检测，以此来确定接收到正确的ADS-B信号。之后求取信号的参考功率，为后续报文解调及置信度的提取环节提供一个重要的数值参考依据。112位的数据位及相应的置信度计算提取完成后，将进行ADS-B信号的纠错及检错环节。消息域的88位数据完成纠错后，将进行报文的相关位置、速度等信息的解码。

图2 ADS-B广播信号处理流程图Fig.2 Flow chart of ADS-B signal processing

2 纠检错算法原理

2.1 置信度提取

纠错的关键是准确对误码定位。而实际的干扰可能对报文信息的任意一段造成影响，要准确定位干扰出现的位置，除使用信息码和校验码外，还需码元“置信度”的配合。根据DO-260B标准，可采用基线多采样点技术[1]来确定每一位高低置信度，该技术可以在最大程度上降低强干扰脉冲对ADS-B消息信号的影响[5]。其中，高置信度表明该位在发生错误时可能性较低，低置信度表明该位在发生错误时可能性较高。ADS-B广播信号采用的纠错算法是建立在置信度已知的基础上，即假若发生错误，默认错误只可能发生在低置信度位上而不考虑高置信度位。

对于ADS-B广播信号数据域中的任何一位，都以0.5μs的间隔分为前后两个码片，记为Chip_0、Chip_1。位判决及置信度提取过程[1]如下：

1）建立一个功率窗A及确定一条最低功率门限B，A窗的功率范围为报头参考功率的±3 dB，最低功率门限B为低于报头参考功率6 dB。当两个码片中的采样点分别落于A窗内时，认为其与报头相匹配，分别记为Chip_0_A、Chip_1_A，如图3中第1、3比特所示；当采样点功率低于门限B时，认为其缺少传输能量，分别记为Chip_0_B、Chip_1_B，如图3中第2、4比特所示。

2）计算每个码片中的采样点落在以上两类中的数目并根据采样点在码片中的相对位置给予不同的权重。居于码片中间位置的采样点给予较高的权重2，如图3中第1比特中的S1、S3区间所示，而居于码片边缘的采样点则给予较低的权重1，如图3中第1比特中的S0、S2、S4区间所示，这样就可以得到4个表征权重累加值的参数，假设图 3中的 S0、S1、S2、S3、S4中分别有 4、12、3、12、2 个采样点，则 4 个参数值分别为

3）使用两个等式来计算两个码片的分数Score1、Score0，以此来确定该位与0或1的匹配程度，即

根据式（5）和式（6），可知图 3的 Score1、Score0分别为

4）Score1＞Score0时判定该位为1，反之，该位为0。两个分数之间的差值若大于等于12（采样频率为40MHz），该位判定为高置信度；反之则为低置信度。如图3中第1比特所示，由于该位的Score1＞Score0，故该位为1；由于，故为低置信度。

图3 高低置信度在不同比特的表现形式Fig.3 Confidence manifestations in different bits

2.2 ADS-B广播信号的CRC校验

循环冗余校验（CRC）是一种较为常用的检错方法，其利用除法及余数的原理来进行错误侦测。

基于S模式的ADS-B广播信号采用CRC编码方式，信号由数据位（88位）和校验位（24位）组成。基于S模式的ADS-B广播信号采用改进的（112，88）CRC编码，其生成多项式G（X）如下

其硬件实现框图如图4所示。

图4 串行CRC24检验电路硬件实现图Fig.4 Hard ware of serial CRC24 testing circuit

图4中的D为寄存器，⊕为异或运算。接收系统在对信号进行位解码及置信度完成后，将通过上述CRC电路进行检错，若检错结果不为0，那么将用相应的纠错方法对错误比特位进行纠正。

3 信号纠检错算法的FPGA实现

3.1 改进的“Brute Force”纠错算法

ADS-B信号实际采用的CRC校验码，由于其汉明距离为6，也就是说最多只能纠正5位随机分布的低置信度比特的错误[6]。最多5位错误比特位的纠错组合只有32种，结合“Brute Force”纠错算法，考虑到FPGA的并行运算特性与资源配置情况，可在同时进行全部32种情况的纠错下而不占用过多的资源，因此提出了一种基于FPGA的改进“Brute Force”纠错方法。具体实现方法如下：

当依次进入CRC校验电路的112位数据位在低置信度位总数小于6的情况下，将这32种组合依次编号，每条路径都对应有规律的低置信度比特翻转及自身的CRC校验。32种组合的纠错路径树状图如图5所示，其中路径下方的“x”表示将当前进入的低置信度比特位取反后送入CRC校验，“～x”表示保持当前进入的低置信度比特位不变，未列出的路径状况默认为保持当前进入的比特位不变，纠错正确时，该条路径的CRC检错结果为0。图5虚线标记的路径表示当112位数据中含有5位低置信度且其中的第2、3、5位发生比特错误时的纠错过程。

图5 纠错路径树状图Fig.5 Tree diagram of correction paths

当112位全部进入CRC校验电路后，将得到32组不同的错误图样。在满足低置信度位总数小于6的情况下，32组通路中必定至少有一组结果为0，结果为0的这一组数据即为待解码的正确数据。

常用的“Brute Force”纠错算法只能在112位数据位解调完成，且已知112位单位矫正子及CRC检错结果的情况下才可对相应低置信度位进行纠错。与常用的“Brute Force”纠错算法相比，本方法可在接收数据的同时进行并行的CRC检错与纠错，省略了生成112位单位矫正子和求取错误图样后对低置信度矫正子进行异或匹配组合的步骤，节省了信号的处理时间。

3.2 两种实现方法及资源占用分析

使用“Brute Force”纠错方法在FPGA中的实现过程为：在解调完的88位数据（不含校验位）放入寄存器中后，将低置信度位的索引也记入对应存储器中。在低置信度位数小于6的情况下，完成32路并行CRC校验后（该算法在FPGA的实现过程中，对算法进行了部分调整，由于FPGA本身无法完成反馈环节，故将此环节变成了单向的信号流动），根据CRC结果为0的那一路结合低置信度索引存储器将对应位置的错误比特取反，最终输出正确结果。这种方法占用的寄存器较少，但由于使用大量的逻辑判断，占用的查找表资源比较多，且执行时间较长。

在现有的FPGA中，未改进前的方法中使用较多的查找表资源为通用资源，为更好地将FPGA中的资源利用起来，改进的方法在FPGA的实现过程中，将使用作为专用资源的块RAM来替代大量的查找表资源完成相应的功能。考虑到FPGA的并行数据处理特性及资源配置情况，本方法以Xilinx公司Virtex5-FPGA为实验平台，在FPGA的内部集成资源——简单双口存储器（Simple Dual Port RAM，dpram）中开辟出两组大小分别为88×32 bits及8×11 bits的空间来缓存数据，以此来省略大量的逻辑判断语句。

在完成 112位的 CRC校验后，88×32 bits的dpram（对应图6中的纠错码存储器）中存放了32组待选择输出的88位纠错码数据。将错误图样为0的一组数据选出，并从大小为8×11 bits的dpram（对应图6中的待发送存储器）中以字节的形式输出至串口，进而完成最终的报文解码环节。图6为改进的纠错算法在FPGA中的硬件实现框图。

两种方法在FPGA实现中的本质区别为：改进前的方法只记录一组88 bits的数据，最终在32组CRC校验结果中选出为0的一组，并跟据CRC结果进行对应低置信度索引位置的取反。而改进后的方法，将在块RAM中同时保存32组88 bits的数据并同时进行CRC校验，最终直接将CRC校验结果为0的一组数据输出。

图6 改进纠错算法的硬件实现框图Fig.6 Hardware design flow chart of imp roved algorithm

由表1可知，与使用常规的“Brute Force”纠错算法相比，由于未改进前的方法使用了大量的组合逻辑，所以导致占用了较多的查找表资源。改进后的方法由于降低了原有纠错算法中不必要的逻辑判断和运算，以增加2个RAM的代价，令查找表已使用数目大幅降低，减少了FPGA的硬件开销，逻辑资源占用情况得到了明显优化。

表1 改进前后硬件资源占用对比图Tab.1 Resource consumption contrast before and after improvement

3.3 FPGA实现及测试结果分析

在完成算法设计后，为验证此改进算法的合理性与可行性，本文首先使用Verilog HDL语言描述改进纠错算法，然后联合Xilinx的ISE软件将改进的“Brute Force”纠错算法在Xilinx的Virtex5-FPGA中实现，并在Chip Scope Pro Analyzer中分析实验结果。

经多次实验验证，选取其中一组测试信号进行详细说明。测试使用的原始数据为来自天津滨海国际机场附近的实采信号，接收频率为1 090MHz，采样频率为40MHz。选取其中的一条信号，在进行完帧头检测、信号解调等处理后，截取信号的局部进行显示。如图7所示，112位数据依次进入并行的32路纠错电路，第8路即crc_reg1_8的纠错位数为0，为常规检错电路，crc_reg1_8的结果（如图7中数字标记1处所示）为0表明该条消息为正确消息，无需进行纠错环节。

图7 原始信号功能测试验证图（无误码，无需纠错）Fig.7 Diagram of raw signal function validation test

由于实际接收到的ADS-B广播数据中，误码信号所占比例较小，所以，采用模拟产生误码的方式（即使用计数器人为的将某些码元的比特或位置信度改变）进行纠错验证。具体方法如下：原始信号中的前5位比特（如图8中数字标记2处所示）为10001（低…高），将图 8 中的第 2、3、5 位取反后变为11100，且令前5位都为低置信度位，在只展示信号关键部分的情况下从图9中可看到，纠错模块输入了有效的112位比特信号（DemodBit2，左侧为低位），且这112位信号中低置信度比特位个数crc_cnt值为5，为方便观察，位置信度的高低也在bit_confi中进行了相应的显示（如图9中数字标记3处所示）。

根据图5虚线标记的路径可知，当前错误比特位第2、3、5位假若得到正确纠错，crc_reg1_29在检错结果中应为0。如图10所示，有且只有crc_reg1_29的检错结果为0（如图10中数字标记4处所示）。经过纠错模块后，比特位第2、3、5位均得到了正确的纠错并在图中的mes_out变量中进行了显示（如图10中数字标记5处所示，左侧为低位），纠错完成后的结果与图8中完全相同，算法功能实现。

图8 原始信号功能测试验证局部图Fig.8 Partialdiagram of raw signal function validation test

图9 比特、置信度调整后时序图Fig.9 Sequencediagram of adjusted bits and confidences

图10 实现纠错功能的信号时序图Fig.10 Sequence diagram of signal correction

本接收机在2017年2月20日于一天中不同时刻分别采样，共采样581 976条ADS-B消息，其中各条所含低置信度位数统计情况如表2所示。

表2 实采信号含低置信度条数统计结果Tab.2 Statistics of low confidence for ADS-B signals

由表2可知，接收到的大量ADS-B消息中，92%为无需纠错信号。而在剩余的8%（含有低置信度位信号）中，其数量随所含低置信度位数值的增加呈逐级递减趋势，这也基本符合误码分布的特点。其中，在低置信度位小于6的情况下，所有ADS-B消息均可以CRC校验结果为0的形式输出。

4 结语

针对高A/C广播FRUIT交叠下ADS-B广播信号易产生误码的问题，提出了一种结合置信度的基于S模式的ADS-B广播信号的改进纠错方案，并在FPGA平台上实现了该方案，通过测试实验验证了该方案的可行性。FPGA系统的测试结果表明，由于改进的纠错算法降低了原有纠错算法中不必要的逻辑判断和运算，节省了硬件开销，因此响应速度得到极大提升。此算法能够正确地检测出ADS-B广播信号在传输过程中出错的比特位，并纠正其错误，有效保证了ADS-B广播信号传输的可靠性。另外，以上纠错方法也可适用于使用结合置信度的CRC检错，且以任意生成多项式、任意位数据输入的方式在FPGA中实现，灵活度较高。

[1]DO-260B.Minimum Operational Performance Standards for 1090MHz Extended Squitter Automatic Dependent Surveillance-Broadcast(ADSB)and Traffic Information Services-Broadcast(TIS-B)[S].Washington DC:RTCA,2009.

[2]周建红.ADS-B系统广播的一种纠错算法设计与实现[J].火控雷达技术,2011,40(3):92-95.

[3]张 辰.ADS-B信号解码板设计及报文处理[D].哈尔滨:哈尔滨工程大学,2013.

[4]郭 焘,田 忠,张 超.ADS-B系统接收处理的关键算法研究[J].火控雷达技术,2013,42(3):44-51.

[5]郭 焘.基于收发一体的S模式ADS-B系统的关键技术研究[D].西安:西安电子科技大学,2013.

[6]刘晓斌.基于模式S的ADS-B接收机系统算法研究[D].成都:成都电子科技大学,2011.

Design and implementation of improved correction algorithm for ADS-B based on FPGA

HU Tieqiao,LIU Danyang,LIYangbo
（Intelligent Signal and Image Processing Key Lab of Tianjin,CAUC,Tianjin 300300,China）

ADS-B（automatic dependent surveillance broadcast） system is based on Mode Sdata link,which is widely used in the field of air traffic management owing to its low cost and high precision.However,ADS-B is vulnerable to interference.The very severe overlapping Mode A/C False FRUIT （replies unsynchronized to interrogator transmission）environment leads to biterrors of ADS-B signal.In order to solve this problem,an improved signal correction method is presented combining with serial operation characteristics and resource allocation of FPGA,CRC （cyclic redundancy check）and bit confidence for ADS-B signal.This method is designed and tested by FPGA platform.ADS-B signal test results of FPGA platform show that this improved method needs less hard ware consumption and can improve signal processing speed without affecting the performance of error correction,ensuring the transmission reliability of ADS-B signal and making correction rate reaches100%.

ADS-B System;CRC checkout;bit confidence;correction;FPGA

胡铁乔（1970—），男，河南洛阳人，副教授，工学硕士，研究方向为基于FPGA、DSP高速处理平台的阵列信号处理系统.

V249

A

1674－5590（2017）05－0006－06

2016-12-22；

2017-03-09

国家重点研发计划（2016YFB0502402）

?

杨媛媛）