一种基于MDL原理的信号分选新算法＊

黄桂根 孟 兵 李 品

（南京电子技术研究所，南京，210039）

引 言

信号分选是雷达侦察信号处理的核心环节［1］，也是雷达信号侦察与对抗领域的研究热点问题之一［2-3］。传统上，雷达信号分选技术大多基于由5大特征参数构成的脉冲描述字（Pulse description word，PDW）实现［4-8］，包括：脉冲宽度、脉冲频率、脉冲幅度、脉冲到达时间［9-12］和脉冲到达角。此类信号分选算法的性能受限制于截获系统的信号检测能力和参数测量精度。

近年来，基于脉内调制特征的信号分选研究越来越受到科研人员的重视［13］。通过对信号脉内调制方式分类和调制参数估计，形成包含脉内调制方式等特征参数的精细脉冲描述字，依据该脉冲描述字可以获得更为可靠的信号分选性能。针对带有复杂有意调制方式的雷达脉冲信号，此类算法具有明显的性能优势。但是，其缺陷在于不能提取无意调制特征；同时，为了保证脉内调制方式分类识别准确率和参数估计精度，对输入SNR、系统采样率有较苛刻的要求。

最小描述长度准则是一种信息压缩准则，属于归纳推理工具［14］，能够通用地解决模型选择问题，普遍被应用到选择最优分类模型问题上，被广泛应用于多个领域，包括降噪［15］、压缩感知［16］、医学图像处理［17］、语音识别［18］等。本文将最小描述长度准则用于脉冲数据聚类处理，不同的雷达辐射源信号由于存在有意或无意调制，将形成不同的向量类，从而实现雷达信号分选。

1 MDL原理

最小描述长度（Minimum description，MDL）准则源于最优编码。将数据z视为信息，对其进行编码并发送给接收者。将模型视为对数据编码的方法，并且选择最节俭的模型，即对于传输，它是最短编码。

首先，假设要传输的信息是z1，z2，…，zm，使用长度为A的有限字母表。例如，可以使用长度A＝2的二进制编码｛0，1｝。这是一个有4种可能信息的例子，其二进制编码见表1。

表1 瞬间前缀码编码规则Table 1 Coding rule of instant prefix code

这是一种所谓的瞬间前缀码，即任何一个码都不是另一个码的前缀，且接收者确切知道何时信息被全部发送。本文的研究就针对这样的瞬间前缀码。

可以使用表1中的编码，或者可以排列这些码，例如对于z1，z2，z3，z4使用码110，10，111，0。决定使用哪一种编码取决于发送信息的频率。例如，如果发送z1最频繁，则对z1使用最短的码0。使用这种策略平均信息长度将比较短。

假设信息发送的概率为Pr（zi）（i＝1，2，3，4），则由香农定理可知，应当使用长度为Li＝-log2（Pr（zi））的码，且平均信息长度满足

由上面的结果可见：为了传递具有概率密度函数Pr（z）的随机变量z需要大约-log2Pr（z）位信息。为了方便，通常将-log2Pr（z）记为logPr（z）＝logePr（z）。

假设有一个以θ为参数的模型M和包括输入、输出的数据Z＝（X，Y）。令该模型下输出的（条件）概率是Pr（y｜θ，M，X），假设接收者知道全部输入，并且希望传送输出。那么传送输出所需要的信息长度是

它是给定输入目标值的对数概率。第二项是传送模型参数θ的平均码长，而第一项是传送模型和实际目标值之间的偏差的平均码长。例如，假设有单一目标y～N（θ，σ2），参数θ～N（0，1），并且无输入（为了简化），则信息长度是

式中：由于y比较集中于θ附近，所以较小的σ就是较短的信息长度。

MDL原理表明，应当选择能够使式（2）极小化的模型。将式（2）视为（负的）对数后验分布，因而极小化描述长度等价于极大化后验概率。

2 截获系统接收脉冲信号模型及其预处理

假设环境中，存在K个独立的雷达辐射源，接收机一共接收到N个来自这些辐射源的脉冲信号。用xn（t；αn）（n＝1，…，N）表示第n个接收到的脉冲，其中“αn＝k”表示第n个脉冲来自第k个雷达辐射源。那么，第n个脉冲可表示为

脉冲信号xn（t；αn）进入截获接收机后，通过对信号的幅度进行门限检测后，可消除时间延迟τn，那么，式（4）可重写为

2.1 幅度归一化处理

事实上，由于

2.2 基于多项式拟合的相位调整

事实上，上面的预处理过程都附带着噪声干扰。通过“幅度归一化处理”和“基于多项式拟合的相位调整”两个预处理步骤，可以得到消除冗余参数ηn，ψn和ωn后的带高斯噪声的脉冲信号

由于前面的预处理都在离散时间上完成，上式又可以表示为

式中：T为采样间隔，M′表示单个脉冲的采样点数。式（13）可用矢量表示为

3 MDL雷达脉冲聚类算法

MDL准则表明，给定一个数据集合和一组竞争统计模型，最佳的统计模型将为数据集合产生最小的描述长度。根据MDL原理可以将其应用于雷达脉冲信号聚类分选处理。

用Y＝｛y1，…，yN｝表示一个包含多个类的数据集合，集合＝｛α1，α2，…，αN｝为Y的关联数据集合，且有

即关联集合将数集Y划分为个数据类。将属于同一个类的数据元素放置在一起，那么，划分后的数据集Y可重新表示为

用θ表示个类的模型参数集合，且为θ的最大似然估计。那么可以用一个条件密度函数）对数据集合Y进行建模，并定义Y在该模型下描述长度为

MDL准则通过下面的公式确定Y中类的数量

在给定数据集合Y时，MDL准则的目的是通过使用关联向量找到Y中数据类的数量，根据关联向量可以计算最小描述长度该准则可以被视为在数学模型的复杂度和数学模型对数据集合的适合度之间求取平衡。

对于雷达脉冲数据而言，数据集合Y＝｛y1，…，yN｝中的每个元素yi（i＝1，…，N）均为数据采集后的雷达脉冲数据向量。因为数据采集时，每个雷达脉冲对应的数据向量可能包含几十、几百甚至上千个采样数据，考虑到正交相检，每个采样数据可以为复数，即Y＝｛y1，…，yN｝可为多维复向量集合。

假设雷达脉冲向量中附加的噪声为高斯分布。那么，来自第k个雷达辐射源的脉冲向量y1（k），…，（k）是服从均值为μk，协方差矩阵为Σk的多参数正态分布样本。那么，样本均值的估计量和协方差矩阵的估计量可以通过下面的公式计算。

数据集合Y的条件密度函数为维正态分布的联合分布，其参数集为θ＝｛μ1，μK，1，…，｝。假设噪声样本之间相互独立，该假设对于雷达辐射源分类处理通常是合理的，则协方差矩阵Σk为

式中M表示单个脉冲向量的维数。可以定义样本标准偏差为

分别用μkm和σkm表示第m个元素的均值μk和标准偏差σk。由于来自同一雷达辐射源的每个脉冲都会出现由电子电路产生的随机噪声，所以，如果采样来自同一雷达辐射源脉冲，则可以假设所有的μkm和σkm独立同分布。

根据假设，式（17）中右边两项可通过下面的公式计算

式中：Nk为归属于第k个类中的脉冲数据向量的数量（即有k＝1，…，，N1＋N2＋…＋＝N），mn表示包含有n个脉冲数据向量的类的数量。

4 MDL雷达脉冲聚类处理流程

为了能够将MDL准则合理应用于雷达脉冲信号分选处理，首先需要为每个假定的类数量，找到一个适合的划分，通过该划分可以计算出其对应的最小描述长度L（Y，）。值不同，则对应的最小描述长度L（Y，）也不相等，在的可选范围内计算的所有L（Y，）值中，最小的L（Y，）值对应的分类数量值即是最佳分类时数据类（雷达辐射源）的数量K＊。

为了直观和工程实现的需要，将上面所述聚类过程用迭代过程描述如下：

首先，令＝1，即将整个数据集合Y视为同一个类。分别计算出这个类的样本均值和标准偏差，并根据式（17，23，24）计算此时的描述长度

第2次迭代（＝2）时，数据集合Y被划分为两个类，这两个类的中心根据式（26）进行初始化。标准偏差向量给出了数据的散布大小，因此根据它进行数据类的分裂。然后根据新形成的类中心，对Y中的每个数据向量重新进行分类处理，分类的依据是数据向量与类中心的距离。对Y多次聚类处理，直到两个类的中心都收敛，然后对Y做聚类处理，类的中心不会发生改变。最后，计算出对应的值。

通常，在将Y划分为个类之后，要完成下一次迭代处理，即需要将Y划分为＋1个类。通过初始化＋1个类的中心值，并对Y进行重新聚类处理，便可以实现。对于初始化＋1个类的中心值，这里采用的方法是将个已有的类中心值中的其中一个分裂为两个类中心，同时保持其他-1个类中心值不变。例如，如果选择第k个类进行分裂处理，那么两个新类的中心由式（27）计算。最优的划分将产生最小描述长度

整个聚类处理过程的流程图如图1所示，整个聚类过程由3级循环构成。

图1 基于MDL原理的雷达脉冲聚类处理流程Fig.1 Processing flow of radar pulse clustering based on MDL criterion

5 算法运算量分析

根据图1所示处理流程，分析算法的运算量，将整个聚类分选流程分别根据三级循环进行运算量分析。在第1级循环中，选择出-1个最小描述长度中的最小值，作为当前的最小描述长度与第3级循环中的运算量相比，第1级循环内的运算量可以忽略不计。在第2级循环中，首先根据式（19）和（22）计算出第k个类的均值和标准偏差，并根据式（27）将第k个类的中心分裂为两个类；此外，在新的数据类中心收敛后，计算聚类收敛后的最小描述长度与第3级循环中的运算量相比，第2级循环内的运算量也可以忽略不计。在第3级循环中，主要运算可分为两部分。首先，根据欧氏距离，将Y中的所有N个雷达脉冲数据向量归类至距离最近的数据类中。每计算一个M维的雷达脉冲数据向量与一个类中心的欧氏距离包括：M个浮点数据减法运算、M个浮点数据乘法运算和（M-1）个浮点数加法运算。Y中总共有N个雷达脉冲数据向量，且当前有个数据类，总共需要的运算量有

式中Sub，Mul和Add分别表示单次浮点减法、乘法和加法运算。

其次，在对Y内的所有雷达脉冲数据一次聚类后，需要更新所有个类的中心

式中：Div表示单次浮点除法运算。

如果要确保现有的个类中心收敛，第3级循环需要执行NItr次迭代聚类处理，完成第3级循环需要的所有运算量为

通常，可以假设M≥1且N≥，对上式简化后可重新记为

因为第2级循环需要执行-1次，所以，第2，3级循环的运算量为

根据上式，在数据集合Y中元素数量N确定的情况下，最终运算量与成正比关系；如果给定了数据集合Y中类的最大数量，那么运算量与数据量N成正比关系。

6 计算机仿真及分析

为了验证基于MDL准则聚类分选算法的有效性，应用MATLAB软件，对两类数据进行了蒙特卡罗仿真，这两类数据分别为二维高斯数据和多维雷达脉冲向量数据。

对于高斯数据的仿真，目的在于验证基于MDL准则聚类处理算法的有效性；对于雷达脉冲信号数据的仿真，目的在于考察针对雷达脉冲信号的预处理算法的有效性，同时考察基于MDL准则聚类处理算法应用于雷达脉冲信号分选课题的有效性及其分选性能。

6.1 基于二维高斯数据的仿真

对5个二维高斯数据类［X，Y］进行聚类处理，其中X和Y为相互独立的一维高斯向量。各个类的均值与方差的设置情况如表2所示，每个类的元素数量为500，生成的5个二维高斯数据类的元素分布情况如图2所示。

表2 二维高斯数据类的参数列表Table 2 Parameters of 2-D Gauss data clusters

表3为应用MDL聚类处理算法对上述5个高斯数据类的分类处理性能，分类结果如图3所示。图4所示为基于最小描述字长度的聚类检测仿真结果，当将原始数据划分为5个数据类时，计算得到的最小描述长度值达到最小。

表3 基于MDL准则的高斯数据聚类处理性能Table 3 Clustering processing performance for Gauss data based on MDL criterion

图3 离线MDL聚类处理的分类结果Fig.3 Clustering result of offline MDL processing algorithm

图4 基于MDL聚类处理的检测结果Fig.4 Detection result of clustering process based on MDL criterion

6.2 基于雷达脉冲数据的仿真

在仿真过程中，为了尽可能反映外场信号环境的真实情况，根据表4的参数设置生成雷达脉冲信号数据。其中每个雷达辐射源产生20个脉冲信号，截获采样时间为0.1μs，采样率1GHz，SNR为20dB。图5～9给出了6部雷达的幅度和相位特征。

表4 待分选雷达辐射源的参数Table 4 Parameters of radar emitters for deinterleaving

图5 雷达1和2脉冲信号特征Fig.5 Pulse signal character of Radar 1and Radar 2

表5为针对上述6部雷达的脉冲信号分选性能，雷达脉冲信号得到了很好的分选，全部脉冲信号都被正确地分选出来，分选的正确率达100%。

表5 基于MDL准则聚类算法的雷达脉冲信号分选性能Table 5 Deinterleaving performance for radar pulse signal based on MDL criterion

图6 雷达3的信号特征Fig.6 Pulse signal character of Radar 3

图7 雷达4的信号特征Fig.7 Pulse signal character of Radar 4

图8 雷达5的信号特征Fig.8 Pulse signal character of Radar 5

图9 雷达6的信号特征Fig.9 Pulse signal character of Radar 6

7 结束语

针对基于MDL准则的雷达脉冲信号分选算法，本文开展了原理性研究：与传统的基于脉冲描述字的信号分选算法不同，该算法利用雷达脉冲信号的脉内调制特征差异，实现雷达信号分选；详细论述了算法原理、设计了处理流程、并分析了算法运算量。后续将就以下方面开展深入研究：（1）研究不同SNR情况下的算法性能；（2）本算法运算量与3max成正比关系，与一般算法比较，运算量较大，需要根据工程实现，研究并开发实时在线算法；（3）综合本算法与传统算法的优势，研究基于PDW、脉间信息和脉内信息的全息信号分选算法。

［1］ 赵国庆.雷达对抗原理［M］.西安：西安电子科技大学出版社，1999.

Zhao Guoqing.Radar electronic principle［M］.Xi′an：Xidian University Press，1999.

［2］ 李合生，韩宇，蔡英武.雷达信号分选关键技术研究综述［J］.系统工程与电子技术，2005，27（12）：2035-2040.

Li Hesheng，Han Yu，Cai Yingwu.Overview of the crucial technology research for radar signal sorting［J］.Systems Engineering and Electronics，2005，27（12）：2035-2040.

［3］ 杨学永，宋国栋，钱轶，等.现代雷达信号分选跟踪的几种方法［J］.现代雷达，2014，36（3）：43-48.

Yang Xueyong，Song Guodong，Qian Yi，et al.Several methods of radar signal sorting and tracking［J］.Modern Radar，2014，36（3）：43-48.

［4］ 韩俊，何明浩，朱元清.基于多参数的雷达辐射源分选新方法［J］.数据采集与处理，2009，24（l）：91-94.

Han Jun，He Minghao，Zhu Yuanqing.Sorting of radar emitter based on multi-parameters［J］.Journal of Data Acquisition and Processing，2009，24（l）：91-94.

［5］ 张西托，饶伟，杨泽刚.平面变换技术脉冲分选自动实现方法［J］.数据采集与处理，2012，27（4）：495-500.

Zhang Xituo，Rao Wei，Yang Zegang.Automatic fulfillment of deinterleaving pulses based on plane transformation［J］.Journal of Data Acquisition and Processing，2012，27（4）：495-500.

［6］ 杨文华，高梅国.基于平面变换技术的脉冲信号分选［J］.北京理工大学学报，2005，25（2）：151-154.

Yang Wenhua，Gao Meiguo.The deinterleaving of pulse signal based on plane transformation［J］.Journal of Beijing Institute of Technology，2005，25（2）：151-154.

［7］ Douglas N.Special purpose correlation functions for improved signal detection and parameter estimation［C］∥Proceedings of International Conference on Acoustics，Speech，and Signal Processing（ICASSP′93）.［S.l.］：IEEE，1993：73-76.

［8］ Mardia H K.New techniques for the deinterleaving of repetitive sequences［C］∥IEE Proceedings of Radar and Signal Processing.［S.l.］：IEEE，1989：149-154.

［9］ Milojevic D J，Popovic B M.Improved algorithm for the deinterleaving of radar pulse［J］.IEE Proceedings of Radar and Signal Processing，1992，139（1）：98-104.

［10］黄桂根，傅有光，武月婷.一种改进的基于DTOA统计的信号分选算法［J］.数据采集与处理，2011，26（4）：430-435.

Huang Guigen，Fu Youguang，Wu Yueting.Improved radar signal deinterleaving algorithm based on DTOA Histogram［J］.Journal of Data Acquisition and Processing，2011，26（4）：430-435.

［11］柴娟芳，司锡才，马晓东.基于PRI谱的双门限雷达信号分选算法及其硬件平台设计［J］.数据采集与处理，2009，24（l）：38-43.

Chai Juanfang，Si Xicai，Ma Xiaodong.Double-threshold PRI sorting algorithm based on PRI spectrum and its sorting platform design［J］.Journal of Data Acquisition and Processing，2009，24（l）：38-43.

［12］李英达，肖立志.一种脉冲重复间隔复杂调制雷达信号分选方法［J］.电子与信息学报，2013，35（10）：2493-2497.

Li Yingda，Xiao Lizhi.A method of signal sorting for radar signal of pulse repetition interval complex modulated［J］.Journal of Electronics＆Information Technology，2013，35（10）：2493-2497.

［13］张治海，秦开兵，张元发.基于脉内特征的雷达信号分选新方法［J］.现代防御技术，2009，37（2）：104-107.

Zhang Zhihai，Qin Kaibing，Zhang Yuanfa.New method for sorting radar signal based on in-pulse characteristics［J］.Modern Defence Technology，2009，37（2）：104-107.

［14］陈爱萍，范媛媛.MDL理论的多属性值域划分方法［J］.计算机工程与应用，2013，49（1）：167-171.

Chen Aiping，Fan Yuanyuan.Value domain partition method of multiple attributes based on MDL principle［J］.Computer Engineering and Application，2013，49（1）：167-171.

［15］王衍学，向家伟，蒋占四，等.基于改进标准化最大似然估计的最小描述长度降噪方法［J］.振动与冲击，2014，33（1）：137-140.

Wang Yanxue，Xiang Jiawei，Jiang Zhansi，et al.M inimum description length denoising based on improved normalized maximum likelihood［J］.Journal of Vibration and Shock，2014，33（1）：137-140.

［16］麦超云，孙进平，崔如心，等.压缩感知合成孔径雷达射频干扰抑制处理［J］.北京航空航天大学学报，2014，40（1）：59-62.

Mai Chaoyun，Sun Jinping，Cui Ruxin，et al.RFI suppression processing for compressive sensing based SAR imaging［J］.Journal of Beijing University of Aeronautics and Astronautics，2014，40（1）：59-62.

［17］蒋建国，宣浩，郝世杰，等.最小描述长度优化下的医学图像统计形状建模［J］.中国图象图形学报，2011，16（5）：879-885.

Jiang Jianguo，Xuan Hao，Hao Shijie，et al.Statistical shape modeling based on minimum description length optimization in medical images［J］.Journal of Image and Graphics，2011，16（5）：879-885.

［18］徐向华，朱杰，郭强.语音识别中基于最小描述长度准则的决策树动态剪枝算法［J］.声学学报，2006，31（4）：370-376.

Xu Xianghua，Zhu Jie，Guo Qiang.Decision tree dynamic pruning method based on minimum description length in speech recognition［J］.Acta Acustica，2006，31（4）：370-376.