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.展开更多
When estimating the direction of arrival (DOA) of wideband signals from multiple sources, the performance of sparse Bayesian methods is influenced by the frequency bands occupied by signals in different directions. Th...When estimating the direction of arrival (DOA) of wideband signals from multiple sources, the performance of sparse Bayesian methods is influenced by the frequency bands occupied by signals in different directions. This is particularly true when multiple signal frequency bands overlap. Message passing algorithms (MPA) with Dirichlet process (DP) prior can be employed in a sparse Bayesian learning (SBL) framework with high precision. However, existing methods suffer from either high complexity or low precision. To address this, we propose a low-complexity DOA estimation algorithm based on a factor graph. This approach introduces two strong constraints via a stretching transformation of the factor graph. The first constraint separates the observation from the DP prior, enabling the application of the unitary approximate message passing (UAMP) algorithm for simplified inference and mitigation of divergence issues. The second constraint compensates for the deviation in estimation angle caused by the grid mismatch problem. Compared to state-of-the-art algorithms, our proposed method offers higher estimation accuracy and lower complexity.展开更多
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.展开更多
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.展开更多
The design of a high-speed decoder using traditional partly parallel architecture for Non-Quasi-Cyclic(NQC)Low-Density Parity-Check(LDPC)codes is a challenging problem due to its high memory-block cost and low hardwar...The design of a high-speed decoder using traditional partly parallel architecture for Non-Quasi-Cyclic(NQC)Low-Density Parity-Check(LDPC)codes is a challenging problem due to its high memory-block cost and low hardware utilization efficiency.In this paper,we present efficient hardware implementation schemes for NQCLDPC codes.First,we propose an implementation-oriented construction scheme for NQC-LDPC codes to avoid memory-access conflict in the partly parallel decoder.Then,we propose a Modified Overlapped Message-Passing(MOMP)algorithm for the hardware implementation of NQC-LDPC codes.This algorithm doubles the hardware utilization efficiency and supports a higher degree of parallelism than that used in the Overlapped Message Passing(OMP)technique proposed in previous works.We also present single-core and multi-core decoder architectures in the proposed MOMP algorithm to reduce memory cost and improve circuit efficiency.Moreover,we introduce a technique called the cycle bus to further reduce the number of block RAMs in multi-core decoders.Using numerical examples,we show that,for a rate-2/3,length-15360 NQC-LDPC code with 8.43-d B coding gain for Binary PhaseShift Keying(BPSK)in an Additive White Gaussian Noise(AWGN)channel,the decoder with the proposed scheme achieves a 23.8%–52.6%reduction in logic utilization per Mbps and a 29.0%–90.0%reduction in message-memory bits per Mbps.展开更多
基金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.
基金supported in part by the National Natural Science Foundation of China(Nos.6202780103 and 62033001)the Innovation Key Project of Guangxi Province(No.AA22068059)+2 种基金the Key Research and Development Program of Guilin(No.2020010332)the Natural Science Foundation of Henan Province(No.222300420504)Academic Degrees and Graduate Education Reform Project of Henan Province(No.2021SJGLX262Y).
文摘When estimating the direction of arrival (DOA) of wideband signals from multiple sources, the performance of sparse Bayesian methods is influenced by the frequency bands occupied by signals in different directions. This is particularly true when multiple signal frequency bands overlap. Message passing algorithms (MPA) with Dirichlet process (DP) prior can be employed in a sparse Bayesian learning (SBL) framework with high precision. However, existing methods suffer from either high complexity or low precision. To address this, we propose a low-complexity DOA estimation algorithm based on a factor graph. This approach introduces two strong constraints via a stretching transformation of the factor graph. The first constraint separates the observation from the DP prior, enabling the application of the unitary approximate message passing (UAMP) algorithm for simplified inference and mitigation of divergence issues. The second constraint compensates for the deviation in estimation angle caused by the grid mismatch problem. Compared to state-of-the-art algorithms, our proposed method offers higher estimation accuracy and lower complexity.
基金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 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.
基金supported in part by the National Natural Science Foundation of China(Nos.61101072 and 61132002)the new strategic industries development projects of Shenzhen city(No.ZDSY20120616141333842)Tsinghua University Initiative Scientific Research Program(No.2012Z10132)
文摘The design of a high-speed decoder using traditional partly parallel architecture for Non-Quasi-Cyclic(NQC)Low-Density Parity-Check(LDPC)codes is a challenging problem due to its high memory-block cost and low hardware utilization efficiency.In this paper,we present efficient hardware implementation schemes for NQCLDPC codes.First,we propose an implementation-oriented construction scheme for NQC-LDPC codes to avoid memory-access conflict in the partly parallel decoder.Then,we propose a Modified Overlapped Message-Passing(MOMP)algorithm for the hardware implementation of NQC-LDPC codes.This algorithm doubles the hardware utilization efficiency and supports a higher degree of parallelism than that used in the Overlapped Message Passing(OMP)technique proposed in previous works.We also present single-core and multi-core decoder architectures in the proposed MOMP algorithm to reduce memory cost and improve circuit efficiency.Moreover,we introduce a technique called the cycle bus to further reduce the number of block RAMs in multi-core decoders.Using numerical examples,we show that,for a rate-2/3,length-15360 NQC-LDPC code with 8.43-d B coding gain for Binary PhaseShift Keying(BPSK)in an Additive White Gaussian Noise(AWGN)channel,the decoder with the proposed scheme achieves a 23.8%–52.6%reduction in logic utilization per Mbps and a 29.0%–90.0%reduction in message-memory bits per Mbps.
