Robust remaindering and signal processing
Date
2017
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
University of Delaware
Abstract
The Chinese remainder theorem (CRT) also known as Sunzi Theorem provides a reconstruction
of an integer from its remainders modulo several smaller integers called moduli,
if the integer is smaller than the least common multiple (lcm) of all the moduli. In this dissertation,
we mainly consider a problem of robust remaindering with erroneous remainders.
The robust remaindering problem is to robustly reconstruct an integer from its erroneous
remainders such that the reconstruction error is upper bounded by the remainder error level
τ whenever the remainder errors are upper bounded by τ. Its applications can be found in
many areas, such as phase unwrapping in radar signal processing, frequency determination
from several undersampled waveforms, and computational neuroscience. ☐ A robust CRT has recently been proposed for a special case when the remaining
integers of the moduli factorized by their greatest common divisor (gcd) are pairwise coprime.
It basically says that the reconstruction error is upper bounded by the remainder
error level τ if τ is less than a quarter of the gcd of all the moduli. One can see that the
constraint on the moduli limits the applications in practice. In this dissertation, therefore,
we first propose a robust CRT with a general set of moduli on which the constraint used in
previous works is no longer required. A corresponding robust reconstruction algorithm is
also proposed. We call it a single stage robust CRT. Afterwards, we propose a two-stage
robust CRT by grouping the set of moduli into several smaller group and applying the single
stage robust CRT across these groups. This is then easily generalized to a multi-stage robust
CRT. With the procedure, an improvement in the robustness is obtained. ☐ In the previous robust CRT’s, the dynamic range of the large number is assumed to
be the maximal possible one, i.e., the lcm of all the moduli. By relaxing this assumption,
we further study a trade-off between the dynamic range and the robustness bound for twomodular
systems. It basically says that a decrease in the dynamic range may lead to an
increase of the robustness bound. We first obtain a general condition on the remainder errors
and derive the exact dynamic range with a closed-form formula for the robustness to hold.
We then propose simple closed-form reconstruction algorithms. Furthermore, the newly
obtained two-modular results are applied to robust reconstruction for multi-modular systems
and generalized to real numbers. Finally, some simulations are carried out to verify our
proposed theoretical results. ☐ We propose a new robust CRT, which relaxes the constraint that all the remainder
errors have to be small but sacrifices the dynamic range of the large integer. It basically says
that an integer can be robustly reconstructed from its erroneous remainders when a combined
occurrence of multiple unrestricted errors and an arbitrary number of small errors is in the
remainders, where the determinable integer is required to be less than the lcm of a subset
of the moduli. A reconstruction algorithm is also proposed. With the new result, a better
performance on frequency estimation from undersampled waveforms is obtained. ☐ Moreover, we study robust reconstruction and error correction for polynomials when
a few residues have unrestricted errors and some (or all) of the remaining residues have
small errors. We first generalize all the results of robust integer reconstruction to polynomials.
Next, we obtain a stronger residue error correction capability for polynomial remainder
codes with non-pairwise co-prime moduli, i.e., apart from the number of errors that can be
corrected in the previous existing result, some small residue errors can be also corrected in
the residues. On the other hand, different from the Hamming distance, another type of distance
called degree-weighted distance for polynomial residue codes is defined. With respect
to the degree-weighted distance, we derive the error correction capability of these codes and
also propose the minimum degree-weighted distance decoding algorithm. Neither of the
minimum Hamming distance decoding and the minimum degree-weighted distance decoding
is absolutely stronger than the other, but they can complement each other from different
points of view. ☐ Finally, we conduct further research on the generalized CRT for multiple integers.
We first obtain a better dynamic range than that in the prior works for the case of two integer
determination. A simple closed-form determination algorithm for two integers is proposed. When the number of erroneous residue sets is given, we obtain a better sufficient condition on
the range of the determinable two integers than that in the previous work. Moreover, similar
to the CRT for a single integer, the maximal possible dynamic range for the generalized CRT
for multiple integers is the lcm of all the moduli, but some conditions on the multiple integers
and/or moduli need to be imposed. So, compared with the previous results, we propose two
new conditions on the multiple integers and moduli so that the dynamic range can reach
the maximal possible one, i.e., the lcm of all the moduli. Two corresponding determination
algorithms are also proposed.
Description
Keywords
Applied sciences, Robust remaindering, Signal processing