30 Years of Generalized and Robust Chinese Remainder Theorems

Xiang-Gen Xia

University of Delaware

In this short article, I would like to briefly summarize the works on generalized and robust Chinese remainder theorems my collaborators and I have carried out  over the past 30 years. It is also dedicated to the 30th anniversary of my career at the University of Delaware.

After I joined the University of Delaware in the Fall of 1996, exactly 30 years ago, I started to involve with Chinese remainder theorem (CRT) that is the most world -wise well-known mathematics result from ancient China. It is to uniquely determine a large unknown non-negative integer from its remainders modulo several smaller moduli. In the first 10 years, I was interested in its generalized version where there are multiple unknown integers to determine from their sets of remainders modulo several moduli. The first paper on this topic is [1] that, although, appeared two years later than [2], while [2] is based on [1]. The reason is that the processing of IEEE Transactions on Signal Processing at that time was slow and 3 years from submitting to publishing was not uncommon. Our results on generalized CRT appeared in [1]-[10].

Since 2006, I started to work on robust Chinese remainder theorem (RCRT) that was motivated from the phase unwrapping in radar signal processing. The name RCRT appeared at the first time in 2007 in [11] in the literature. In many applications including phase unwrapping, only remainders of an unknown value can be detected and the detected remainders are usually erroneous. It is known that the conventional CRT is not robust in the sense that a small error in a remainder may cause a large error in the reconstruction. The question is how to robustly recover the unknown value from the erroneous remainders with small errors. The above mentioned RCRT is to answer this question. Our results on one dimensional RCRT appeared in [11]-[32] with applications in moving target imaging in radar signal processing using linear antenna arrays and etc., and also in digital communications as error correction coding.

We then started to work on multidimensional CRT (MD-CRT) and its robust versions, i.e., robust MD-CRT. The first paper on this topic is [33]. For MD-CRT, a critical question is whether it can perform better than several independent one dimensional/conventional CRT, i.e., whether non-separable MD-CRT performs better than separable MD-CRT. [40] has positively answered this question. In [41]-[42], we have further shown that for 3D moving target SAR imaging, using robust MD-CRT, non-separable planar antenna arrays can truly perform better than separable planar antenna arrays. Hopefully, this is just the beginning of the investigations of multidimensional array designs in various applications by using MD-CRT and its robust versions.

The summary above covers only research to which I contributed. This article is not intended to review other researchers’ work on these topics. My major collaborators on these topics are, alphabetically, Guangpu Guo (G. Guo), Gang Li (G. Li), Xiaoping Li (X.-P. Li), Xiaowei Li (X. Li), Hong Liang (H. Liang), Huiyong Liao (H. Liao), Genyuan Wang (G. Wang), Wei Wang (W. Wang), Wenjie Wang (W.-J. Wang),  Li Xiao (L. Xiao), and Guangcai Zhou (G. Zhou). With this opportunity, I would like to thank all of them.

List of Publications

Generalized Chinese Remainder Theorem

[1] X.-G. Xia, On estimation of multiple frequencies in undersampled complex valued waveforms, IEEE Trans. on Signal Processing, vol. 47, pp. 3417-3419, Dec. 1999.

[2] G. Zhou and X.-G. Xia, Multiple frequency detection in undersampled complex-valued waveforms with close multiple frequencies, IEE Electronics Letters, vol.33, no.15, pp.1294-1295, Jul. 1997.

[3] X.-G. Xia, An efficient frequency estimation algorithm from multiple undersampled waveforms, IEEE Signal Processing Letters, vol. 7, pp. 34-37, Feb. 2000.

[4] X.-G. Xia and K. Liu, A Generalized Chinese Remainder Theorem for Residue Sets with Errors and Its Application in Frequency Determination from Multiple Sensors with Low Sampling Rates, IEEE Signal Processing Letters, vol. 12, pp. 768-771, Nov. 2005.

[5] H. Liao and X.-G. Xia, A sharpened dynamic range of a generalized Chinese remainder theorem for multiple integers, IEEE Trans. on Information Theory, vol. 53, pp. 428-433, Jan. 2007.

[6] L. Xiao and X.-G. Xia, A Generalized Chinese Remainder Theorem for Two Integers, IEEE Signal Processing Letters, vol. 21,  pp. 55-59, Jan. 2014.

[7] W. Wang, X.-P. Li, X.-G. Xia, and W.-J. Wang, The largest dynamic range of a generalized Chinese remainder theorem for two integers, IEEE Signal Processing Letters, vol. 22, pp. 254-258, Feb. 2015.

[8] L. Xiao, X.-G. Xia, and H. Y. Huo, New Conditions on Achieving the Maximal Possible Dynamic Range for a Generalized Chinese Remainder Theorem of Multiple Integers, IEEE Signal Processing Letters, vol. 22, pp. 2199-2203, Dec. 2015.

[9] W. Wang, X.-P. Li, X.-G. Xia, W.-J. Wang, and J. Qian, "Simplification on dynamic range of a generalized Chinese remainder theorem for multiple integers, Integers, vol. 17, #A28, July 17, 2017.

[10] J. Xu, Z.-Z. Huang, Z.-R. Wang, L. Xiao, X.-G. Xia, and T. Long, Radial velocity retrieval for multichannel SAR moving targets with time-space Doppler de-ambiguity, IEEE Trans. on Geoscience and Remote Sensing, vol. 56, pp. 35-48, Jan. 2018.

Robust Chinese Remainder Theorem

[11] X.-G. Xia and G. Wang, Phase Unwrapping and A Robust Chinese Remainder Theorem, IEEE Signal Processing Letters, vol. 14, pp. 247-250, April 2007.

[12] G. Li, J. Xu, Y. Peng, and X.-G. Xia, An efficient implementation of a phase unwrapping algorithm, vol. 14, pp. 393-396, IEEE Signal Processing Letters, June 2007.

[13] G. Li, J. Xu, Y. Peng, and X.-G. Xia, Location and imaging of moving targets using non-uniform linear antenna array, IEEE Trans. on Aerospace and Electronic Systems, vol. 43, pp. 1214-1220, July 2007.

[14] X. Li and X.-G. Xia, A Fast Robust Chinese Remainder Theorem Based Phase Unwrapping Algorithm, IEEE Signal Processing Letters, vol.15, pp.665-668, Oct. 2008.

[15] H. Liang, X. Li, and X.-G. Xia, Adaptive Frequency Estimation with Low Sampling Rates Based on Robust Chinese Remainder Theorem and IIR Notch Filter, Advances in Adaptive Data Analysis, vol. 1, pp. 587-600, Oct. 2009.

[16] X. Li, H. Liang, and X.-G. Xia, A Robust Chinese Remainder Theorem with its Applications in Frequency Estimation from Undersampled Waveforms, IEEE Trans. on Signal Processing, vol. 57, pp. 4314-4322, Nov. 2009.

[17] X. Li and X.-G. Xia, A Robust Doppler Ambiguity Resolution Using Multiple Paired Pulse Repetition Frequencies, IET Radar, Sonar & Navigation, vol. 4, pp. 375-383, June 2010.

[18] W.-J. Wang and X.-G. Xia, A Closed-Form Robust Chinese Remainder Theorem and Its Performance Analysis, IEEE Trans. on Signal Processing, vol. 58, pp. 5655-5666, Nov. 2010.

[19] X. Li and X.-G. Xia, Location and Imaging of Elevated Moving Target Using Multi-Frequency Velocity SAR with Cross-Track Interferometry, IEEE Trans. on Aerospace and Electronic Systems, vol. 47, pp. 1203-1212, April 2011.

[20] W.-J. Wang, H. Y. Jiang, X.-G. Xia, P. C. Mu, and Q. Y. Yin, A Wireless Secret Key Generation Method Based on Chinese Remainder Theorem in FDD Systems, Science China -- Information Sciences, vol.55, pp.1605-1616, July 2012.

[21] B. Yang, W.-J. Wang, X.-G. Xia, and Q. Yin, Phase detection based range estimation with a dual-band robust Chinese remainder theorem, Science China -- Information Sciences, vol. 57,  022302:1-022302:9, Feb. 2014.

[22] L. Xiao, X.-G. Xia, and W.-J. Wang, Multi-Stage Robust Chinese Remainder Theorem, IEEE Trans. on Signal Processing, vol. 62, pp. 4772-4785, Sept. 2014.

[23] L. Xiao and X.-G. Xia, Error Correction in Polynomial Remainder Codes with Non-Pairwise Coprime Moduli and Robust Chinese Remainder Theorem for Polynomials, IEEE Trans. on Communications, vol. 63, pp.605-616, March 2015.

[24] W.-J. Wang, X.-P. Li, W. Wang, and X.-G. Xia, Maximum Likelihood Estimation Based Robust Chinese Remainder Theorem for Real Numbers and Its Fast Algorithm, IEEE Trans. on Signal Processing, vol. 63, pp.3317-3330, July 2015.

[25] L. Xiao and X.-G. Xia, A New Robust Chinese Remainder Theorem with Improved Performance in Frequency Estimation from Undersampled Waveforms, Signal Processing, vol. 117, pp. 242-246, Dec. 2015.

[26] X.-P. Li, X.-G. Xia, W.-J. Wang, and W. Wang, A robust generalized Chinese remainder theorem for two Integers, IEEE Trans. on Information Theory, vol. 62, pp. 7491-7504, Dec. 2016.

[27] L. Xiao, X.-G. Xia, and H. Y. Huo, Towards Robustness in Residue Number Systems, IEEE Trans. on Signal Processing, vol. 65, pp. 1497-1510, Mar. 2017.

[28] L. Xiao and X.-G. Xia, Minimum degree-weighted distance decoding for polynomial residue codes with non-pairwise coprime moduli, IEEE Wireless Communications Letters, vol. 6,  pp. 558-561, Aug. 2017.

[29] L. Xiao and X.-G. Xia, Frequency determination from truly sub-Nyquist samplers based on robust Chinese remainder theorem, Signal Processing, vol. 150, pp. 248-258. Sept. 2018. https://doi.org/10.1016/j.sigpro.2018.04.022

[30] L. Xiao and X.-G. Xia, Robust Polynomial Reconstruction via Chinese Remainder Theorem in the Presence of Small Degree Residue Errors, IEEE Trans. on Circuits and Systems II: Express Briefs, vol. 65, pp. 1778-1782, Nov. 2018.

[31] X.-P. Li, T.-Z. Huang, Q. Liao, and X.-G. Xia, Optimal Estimates of Two Common Remainders for A Robust Generalized Chinese Remainder Theorem, IEEE Trans. on Signal Processing, vol. 67, pp. 1824-1837, Apr. 1, 2019.

[32] G. Guo and X.-G. Xia, Exact Dynamic Range--Robustness Tradeoff for Chinese Remainder Theorem under Non-Uniformly Bounded Remainder Errors, preprint, arXiv:2609.22615, 2026.

Robust Multidimensional Chinese Remainder Theorem

[33] L. Xiao, X.-G. Xia, and Y.-P. Wang, Exact and robust reconstructions of integer vectors based on multidimensional Chinese remainder theorem (MD-CRT), IEEE Trans. on Signal Processing, vol. 68, pp. 5349–5362, 2020.

[34] L. Xiao, H. Huo, and X.-G. Xia, Robust multidimensional Chinese remainder theorem for integer vector reconstruction, IEEE Trans. on Signal Processing, vol. 72, pp. 2364–2380, 2024.

[35] G. Guo and X.-G. Xia, A generalized multidimensional Chinese remainder theorem (MD-CRT) for multiple integer vectors,  IEEE Trans. on Signal Processing, vol. 73, pp. 5136–5151, 2025.

[36] G. Guo and X.-G. Xia, A construction of pairwise co-prime integer matrices of any dimension and their least common right multiple,  IEEE Trans. on Signal Processing, vol. 73, pp. 2187–2199, 2025.

[37] X.-G. Xia and G. Guo, Prime and co-prime integer matrices, IEEE Signal Processing Letters, vol. 32, pp. 3037–3041, 2025.

[38] X.-P. Li, S. y. Sun, Q. y. Liao, and X.-G. Xia, Maximum likelihood estimation based complex-valued robust Chinese remainder theorem and its fast algorithm,  IEEE J. Miniaturization Air Space Syst., vol. 7, no. 1, pp. 64–79, Mar. 2026.

[39] X.-P. Li, S. y. Sun, Q. y. Liao, and X.-G. Xia, Maximum likelihood estimation based robust multidimensional Chinese remainder theorem and its fast algorithm, IEEE Trans. on Signal Processing, vol. 74, pp. 3283-3298, July 2026, doi: 10.1109/TSP.2026.3718323.

[40] G. Guo and X. -G. Xia, Robust multidimensional Chinese remainder theorem (MD-CRT) with non-diagonal moduli and multi-stage framework, IEEE Trans. on Signal Processing, vol. 74,   doi: 10.1109/TSP.2026.3738672, Sept. 2026.

[41] G. Guo and X.-G. Xia, Moving target SAR imaging using planar arrays and multidimensional Chinese remainder theorem (MD-CRT), Part I: A general framework, preprint, arXiv:2606.14910, 2026.

[42] G. Guo and X.-G. Xia, Moving target SAR imaging using planar arrays and multidimensional Chinese remainder theorem (MD-CRT), Part II: Two subarray designs, preprint, arXiv:2606.14911, 2026.

支持单位：