TY - JOUR

T1 - Robust Polynomial Reconstruction via Chinese Remainder Theorem in the Presence of Small Degree Residue Errors

AU - Xiao, Li

AU - Xia, Xiang Gen

N1 - Publisher Copyright:
© 2004-2012 IEEE.

PY - 2018/11

Y1 - 2018/11

N2 - Based on unique decoding of the polynomial residue code with non-pairwise coprime moduli, a polynomial with degree less than that of the least common multiple of all the moduli can be accurately reconstructed when the number of residue errors is less than half the minimum distance of the code. However, once the number of residue errors is beyond half the minimum distance of the code, the unique decoding may fail and lead to a large reconstruction error. In this brief, assuming that all the residues are allowed to have errors with small degrees, we consider how to reconstruct the polynomial as accurately as possible in the sense that a reconstructed polynomial is obtained with only the last τ number of coefficients being possibly erroneous, when the residues are affected by errors with degrees upper bounded by τ. In this regard, we first propose a multi-level robust Chinese remainder theorem for polynomials, namely, a tradeoff between the dynamic range of the degree of the polynomial to be reconstructed and the residue error bound τ is formulated. Furthermore, a simple closed-form reconstruction algorithm is also proposed.

AB - Based on unique decoding of the polynomial residue code with non-pairwise coprime moduli, a polynomial with degree less than that of the least common multiple of all the moduli can be accurately reconstructed when the number of residue errors is less than half the minimum distance of the code. However, once the number of residue errors is beyond half the minimum distance of the code, the unique decoding may fail and lead to a large reconstruction error. In this brief, assuming that all the residues are allowed to have errors with small degrees, we consider how to reconstruct the polynomial as accurately as possible in the sense that a reconstructed polynomial is obtained with only the last τ number of coefficients being possibly erroneous, when the residues are affected by errors with degrees upper bounded by τ. In this regard, we first propose a multi-level robust Chinese remainder theorem for polynomials, namely, a tradeoff between the dynamic range of the degree of the polynomial to be reconstructed and the residue error bound τ is formulated. Furthermore, a simple closed-form reconstruction algorithm is also proposed.

KW - Chinese remainder theorem

KW - polynomial reconstruction

KW - residue codes

KW - residue errors

KW - residue number systems

UR - http://www.scopus.com/inward/record.url?scp=85030792077&partnerID=8YFLogxK

U2 - 10.1109/TCSII.2017.2756343

DO - 10.1109/TCSII.2017.2756343

M3 - Article

AN - SCOPUS:85030792077

SN - 1549-7747

VL - 65

SP - 1778

EP - 1782

JO - IEEE Transactions on Circuits and Systems II: Express Briefs

JF - IEEE Transactions on Circuits and Systems II: Express Briefs

IS - 11

M1 - 8049289

ER -