Message passing algorithms,whose iterative nature captures complicated interactions among interconnected variables in complex systems and extracts information from the fixed point of iterated messages,provide a powerf...Message passing algorithms,whose iterative nature captures complicated interactions among interconnected variables in complex systems and extracts information from the fixed point of iterated messages,provide a powerful toolkit in tackling hard computational tasks in optimization,inference,and learning problems.In the context of constraint satisfaction problems(CSPs),when a control parameter(such as constraint density)is tuned,multiple threshold phenomena emerge,signaling fundamental structural transitions in their solution space.Finding solutions around these transition points is exceedingly challenging for algorithm design,where message passing algorithms suffer from a large message fiuctuation far from convergence.Here we introduce a residual-based updating step into message passing algorithms,in which messages with large variation between consecutive steps are given high priority in the updating process.For the specific example of model RB(revised B),a typical prototype of random CSPs with growing domains,we show that our algorithm improves the convergence of message updating and increases the success probability in finding solutions around the satisfiability threshold with a low computational cost.Our approach to message passing algorithms should be of value for exploring their power in developing algorithms to find ground-state solutions and understand the detailed structure of solution space of hard optimization problems.展开更多
Watermarking system based on quantization index modulation （QIM） is increasingly popular in high payload applications,but it is inherently fragile against amplitude scaling attacks.In order to resist desynchronizati...Watermarking system based on quantization index modulation （QIM） is increasingly popular in high payload applications,but it is inherently fragile against amplitude scaling attacks.In order to resist desynchronization attacks of QIM digital watermarking,a low density parity check （LDPC） code-aided QIM watermarking algorithm is proposed,and the performance of QIM watermarking system can be improved by incorporating LDPC code with message passing estimation/detection framework.Using the theory of iterative estimation and decoding,the watermark signal is decoded by the proposed algorithm through iterative estimation of amplitude scaling parameters and decoding of watermark.The performance of the proposed algorithm is closer to the dirty paper Shannon limit than that of repetition code aided algorithm when the algorithm is attacked by the additive white Gaussian noise.For constant amplitude scaling attacks,the proposed algorithm can obtain the accurate estimation of amplitude scaling parameters.The simulation result shows that the algorithm can obtain similar performance compared to the algorithm without desynchronization.展开更多
To overcome the limitations of conventional speech enhancement methods, such as inaccurate voice activity detector(VAD) and noise estimation, a novel speech enhancement algorithm based on the approximate message passi...To overcome the limitations of conventional speech enhancement methods, such as inaccurate voice activity detector(VAD) and noise estimation, a novel speech enhancement algorithm based on the approximate message passing(AMP) is adopted. AMP exploits the difference between speech and noise sparsity to remove or mute the noise from the corrupted speech. The AMP algorithm is adopted to reconstruct the clean speech efficiently for speech enhancement. More specifically, the prior probability distribution of speech sparsity coefficient is characterized by Gaussian-model, and the hyper-parameters of the prior model are excellently learned by expectation maximization(EM) algorithm. We utilize the k-nearest neighbor(k-NN) algorithm to learn the sparsity with the fact that the speech coefficients between adjacent frames are correlated. In addition, computational simulations are used to validate the proposed algorithm, which achieves better speech enhancement performance than other four baseline methods-Wiener filtering, subspace pursuit(SP), distributed sparsity adaptive matching pursuit(DSAMP), and expectation-maximization Gaussian-model approximate message passing(EM-GAMP) under different compression ratios and a wide range of signal to noise ratios(SNRs).展开更多
For data association in multisensor and multitarget tracking, a novel parallel algorithm is developed to improve the efficiency and real-time performance of FGAs-based algorithm. One Cluster of Workstation （COW） wit...For data association in multisensor and multitarget tracking, a novel parallel algorithm is developed to improve the efficiency and real-time performance of FGAs-based algorithm. One Cluster of Workstation （COW） with Message Passing Interface （MPI） is built. The proposed Multi-Deme Parallel FGA （MDPFGA） is run on the platform. A serial of special MDPFGAs are used to determine the static and the dynamic solutions of generalized m-best S-D assignment problem respectively, as well as target states estimation in track management. Such an assignment-based parallel algorithm is demonstrated on simulated passive sensor track formation and maintenance problem. While illustrating the feasibility of the proposed algorithm in multisensor multitarget tracking, simulation results indicate that the MDPFGAs-based algorithm has greater efficiency and speed than the FGAs-based algorithm.展开更多
Signal detection plays an essential role in massive Multiple-Input Multiple-Output(MIMO)systems.However,existing detection methods have not yet made a good tradeoff between Bit Error Rate(BER)and computational complex...Signal detection plays an essential role in massive Multiple-Input Multiple-Output(MIMO)systems.However,existing detection methods have not yet made a good tradeoff between Bit Error Rate(BER)and computational complexity,resulting in slow convergence or high complexity.To address this issue,a low-complexity Approximate Message Passing(AMP)detection algorithm with Deep Neural Network(DNN)(denoted as AMP-DNN)is investigated in this paper.Firstly,an efficient AMP detection algorithm is derived by scalarizing the simplification of Belief Propagation(BP)algorithm.Secondly,by unfolding the obtained AMP detection algorithm,a DNN is specifically designed for the optimal performance gain.For the proposed AMP-DNN,the number of trainable parameters is only related to that of layers,regardless of modulation scheme,antenna number and matrix calculation,thus facilitating fast and stable training of the network.In addition,the AMP-DNN can detect different channels under the same distribution with only one training.The superior performance of the AMP-DNN is also verified by theoretical analysis and experiments.It is found that the proposed algorithm enables the reduction of BER without signal prior information,especially in the spatially correlated channel,and has a lower computational complexity compared with existing state-of-the-art methods.展开更多
正交时频空(Orthogonal Time Frequency Space, OTFS)调制作为极具潜力的调制方案能够显著提升高移动场景下通信系统的鲁棒性。传统的OTFS同步消息传递(Message Passing, MP)检测算法及其变体每次迭代都需要更新并传递所有的信息,从而...正交时频空(Orthogonal Time Frequency Space, OTFS)调制作为极具潜力的调制方案能够显著提升高移动场景下通信系统的鲁棒性。传统的OTFS同步消息传递(Message Passing, MP)检测算法及其变体每次迭代都需要更新并传递所有的信息,从而导致收敛速度过慢。针对上述问题,提出基于残差的OTFS异步消息传递算法。该算法利用消息更新前后的差值作为知情调度信息来控制消息传递的顺序,从而实现迭代资源的非均匀分配。仿真结果表明,基于残差的OTFS异步消息传递算法相较于传统的同步消息传递算法,在信噪比为20 dB时,迭代次数减少了45%,误比特性能提高了7 dB。展开更多
In this paper,an index modulation(IM)aided uplink orthogonal time frequency space modulation(OTFS)structure for sparse code multiple access(SCMA)is proposed.To be more specific,the information bits are firstly partiti...In this paper,an index modulation(IM)aided uplink orthogonal time frequency space modulation(OTFS)structure for sparse code multiple access(SCMA)is proposed.To be more specific,the information bits are firstly partitioned for transmit antenna(TA)selection and sparse codeword mapping,respectively.Subsequently,the codewords deployed on the 2-dimensional(2D)delay-Doppler(DD)plane are transmitted by the selected TA,and the superimposed signals are jointly detected at the receiver.Furthermore,a low-complexity zero-embedded expectation propagation(ZE-EP)detector is conceived,where the codebooks are extended with zero vectors to reflect the silent indices.The simulation results demonstrate that the proposed IM-OTFS-SCMA system is capable of providing significant performance gain over the OTFS-SCMA counterpart.展开更多
卫星物联网是6G实现万物智联的关键所在,而其频谱资源和星上载荷的双重受限性,给海量用户的接入效能提升带来严峻挑战。针对稀疏码多址接入(SCMA,sparse code multiple access)星载接收机多用户检测效率低下问题,考虑迭代过程中码字发...卫星物联网是6G实现万物智联的关键所在,而其频谱资源和星上载荷的双重受限性,给海量用户的接入效能提升带来严峻挑战。针对稀疏码多址接入(SCMA,sparse code multiple access)星载接收机多用户检测效率低下问题,考虑迭代过程中码字发送概率的差异性,提出一种基于状态位置信息的对数域消息传递算法(SPI-Log-MPA,state position information based log message passing algorithm)。该算法根据用户码字状态位置的变化情况,在迭代检测过程中通过减少不可靠码字、提前对稳定用户进行解码、设立奖惩机制对非稳定用户进行解码等措施,显著提升了检测效率。在此基础上,对阶段设置与状态位置信息矩阵两方面进行优化,提出两阶段的改进算法,进一步加快了收敛速度。复杂度分析与仿真结果表明,所提算法在保证误码率性能的前提下具有更低的计算复杂度。展开更多
基金supported by Guangdong Major Project of Basic and Applied Basic Research No.2020B0301030008Science and Technology Program of Guangzhou No.2019050001+2 种基金the Chinese Academy of Sciences Grant QYZDJ-SSWSYS018the National Natural Science Foundation of China(Grant No.12171479)supported by the National Natural Science Foundation of China(Grant Nos.11301339 and 11491240108)。
文摘Message passing algorithms,whose iterative nature captures complicated interactions among interconnected variables in complex systems and extracts information from the fixed point of iterated messages,provide a powerful toolkit in tackling hard computational tasks in optimization,inference,and learning problems.In the context of constraint satisfaction problems(CSPs),when a control parameter(such as constraint density)is tuned,multiple threshold phenomena emerge,signaling fundamental structural transitions in their solution space.Finding solutions around these transition points is exceedingly challenging for algorithm design,where message passing algorithms suffer from a large message fiuctuation far from convergence.Here we introduce a residual-based updating step into message passing algorithms,in which messages with large variation between consecutive steps are given high priority in the updating process.For the specific example of model RB(revised B),a typical prototype of random CSPs with growing domains,we show that our algorithm improves the convergence of message updating and increases the success probability in finding solutions around the satisfiability threshold with a low computational cost.Our approach to message passing algorithms should be of value for exploring their power in developing algorithms to find ground-state solutions and understand the detailed structure of solution space of hard optimization problems.
基金National Natural Science Foundation of China(No.61272432)Qingdao Science and Technology Development Plan(No.12-1-4-6-(10)-jch)
文摘Watermarking system based on quantization index modulation （QIM） is increasingly popular in high payload applications,but it is inherently fragile against amplitude scaling attacks.In order to resist desynchronization attacks of QIM digital watermarking,a low density parity check （LDPC） code-aided QIM watermarking algorithm is proposed,and the performance of QIM watermarking system can be improved by incorporating LDPC code with message passing estimation/detection framework.Using the theory of iterative estimation and decoding,the watermark signal is decoded by the proposed algorithm through iterative estimation of amplitude scaling parameters and decoding of watermark.The performance of the proposed algorithm is closer to the dirty paper Shannon limit than that of repetition code aided algorithm when the algorithm is attacked by the additive white Gaussian noise.For constant amplitude scaling attacks,the proposed algorithm can obtain the accurate estimation of amplitude scaling parameters.The simulation result shows that the algorithm can obtain similar performance compared to the algorithm without desynchronization.
基金supported by National Natural Science Foundation of China(NSFC)(No.61671075)Major Program of National Natural Science Foundation of China(No.61631003)。
文摘To overcome the limitations of conventional speech enhancement methods, such as inaccurate voice activity detector(VAD) and noise estimation, a novel speech enhancement algorithm based on the approximate message passing(AMP) is adopted. AMP exploits the difference between speech and noise sparsity to remove or mute the noise from the corrupted speech. The AMP algorithm is adopted to reconstruct the clean speech efficiently for speech enhancement. More specifically, the prior probability distribution of speech sparsity coefficient is characterized by Gaussian-model, and the hyper-parameters of the prior model are excellently learned by expectation maximization(EM) algorithm. We utilize the k-nearest neighbor(k-NN) algorithm to learn the sparsity with the fact that the speech coefficients between adjacent frames are correlated. In addition, computational simulations are used to validate the proposed algorithm, which achieves better speech enhancement performance than other four baseline methods-Wiener filtering, subspace pursuit(SP), distributed sparsity adaptive matching pursuit(DSAMP), and expectation-maximization Gaussian-model approximate message passing(EM-GAMP) under different compression ratios and a wide range of signal to noise ratios(SNRs).
基金Supported by National Defence Scientific Research Foundation
文摘For data association in multisensor and multitarget tracking, a novel parallel algorithm is developed to improve the efficiency and real-time performance of FGAs-based algorithm. One Cluster of Workstation （COW） with Message Passing Interface （MPI） is built. The proposed Multi-Deme Parallel FGA （MDPFGA） is run on the platform. A serial of special MDPFGAs are used to determine the static and the dynamic solutions of generalized m-best S-D assignment problem respectively, as well as target states estimation in track management. Such an assignment-based parallel algorithm is demonstrated on simulated passive sensor track formation and maintenance problem. While illustrating the feasibility of the proposed algorithm in multisensor multitarget tracking, simulation results indicate that the MDPFGAs-based algorithm has greater efficiency and speed than the FGAs-based algorithm.
基金supported by Major Project of Science and Technology Research Program of Chongqing Education Commission of China(Grant No.KJZD-M201900601)China Postdoctoral Science Foundation(Grant No.2021MD703932)Project Supported by Engineering Research Center of Mobile Communications,Ministry of Education,China(Grant No.cqupt-mct-202006)。
文摘Signal detection plays an essential role in massive Multiple-Input Multiple-Output(MIMO)systems.However,existing detection methods have not yet made a good tradeoff between Bit Error Rate(BER)and computational complexity,resulting in slow convergence or high complexity.To address this issue,a low-complexity Approximate Message Passing(AMP)detection algorithm with Deep Neural Network(DNN)(denoted as AMP-DNN)is investigated in this paper.Firstly,an efficient AMP detection algorithm is derived by scalarizing the simplification of Belief Propagation(BP)algorithm.Secondly,by unfolding the obtained AMP detection algorithm,a DNN is specifically designed for the optimal performance gain.For the proposed AMP-DNN,the number of trainable parameters is only related to that of layers,regardless of modulation scheme,antenna number and matrix calculation,thus facilitating fast and stable training of the network.In addition,the AMP-DNN can detect different channels under the same distribution with only one training.The superior performance of the AMP-DNN is also verified by theoretical analysis and experiments.It is found that the proposed algorithm enables the reduction of BER without signal prior information,especially in the spatially correlated channel,and has a lower computational complexity compared with existing state-of-the-art methods.
文摘正交时频空(Orthogonal Time Frequency Space, OTFS)调制作为极具潜力的调制方案能够显著提升高移动场景下通信系统的鲁棒性。传统的OTFS同步消息传递(Message Passing, MP)检测算法及其变体每次迭代都需要更新并传递所有的信息,从而导致收敛速度过慢。针对上述问题,提出基于残差的OTFS异步消息传递算法。该算法利用消息更新前后的差值作为知情调度信息来控制消息传递的顺序,从而实现迭代资源的非均匀分配。仿真结果表明,基于残差的OTFS异步消息传递算法相较于传统的同步消息传递算法,在信噪比为20 dB时,迭代次数减少了45%,误比特性能提高了7 dB。
基金supported in part by the National Key Research and Development Program of China with Grant number 2021YFB2900502。
文摘In this paper,an index modulation(IM)aided uplink orthogonal time frequency space modulation(OTFS)structure for sparse code multiple access(SCMA)is proposed.To be more specific,the information bits are firstly partitioned for transmit antenna(TA)selection and sparse codeword mapping,respectively.Subsequently,the codewords deployed on the 2-dimensional(2D)delay-Doppler(DD)plane are transmitted by the selected TA,and the superimposed signals are jointly detected at the receiver.Furthermore,a low-complexity zero-embedded expectation propagation(ZE-EP)detector is conceived,where the codebooks are extended with zero vectors to reflect the silent indices.The simulation results demonstrate that the proposed IM-OTFS-SCMA system is capable of providing significant performance gain over the OTFS-SCMA counterpart.
文摘卫星物联网是6G实现万物智联的关键所在,而其频谱资源和星上载荷的双重受限性,给海量用户的接入效能提升带来严峻挑战。针对稀疏码多址接入(SCMA,sparse code multiple access)星载接收机多用户检测效率低下问题,考虑迭代过程中码字发送概率的差异性,提出一种基于状态位置信息的对数域消息传递算法(SPI-Log-MPA,state position information based log message passing algorithm)。该算法根据用户码字状态位置的变化情况,在迭代检测过程中通过减少不可靠码字、提前对稳定用户进行解码、设立奖惩机制对非稳定用户进行解码等措施,显著提升了检测效率。在此基础上,对阶段设置与状态位置信息矩阵两方面进行优化,提出两阶段的改进算法,进一步加快了收敛速度。复杂度分析与仿真结果表明,所提算法在保证误码率性能的前提下具有更低的计算复杂度。
