عنوان

Parametric Linear System Solving with Error Correction

شماره

TLpq2390187711

زبان متن نوشتاري يا گفتاري و مانند آن

انگلیسی

عنوان اصلي

Parametric Linear System Solving with Error Correction

نام عام مواد

[Thesis]

نام نخستين پديدآور

Waddell, Cleveland Alexander

نام ساير پديدآوران

Blackman, Terrance

نام ناشر، پخش کننده و غيره

North Carolina State University

تاریخ نشرو بخش و غیره

2019

نام خاص و کميت اثر

162

جزئيات پايان نامه و نوع درجه آن

Ph.D.

کسي که مدرک را اعطا کرده

North Carolina State University

امتياز متن

2019

متن يادداشت

Consider solving a black box linear system, A(u)x = b(u), where the entries are polynomials in u over a field K, and A(u) is full rank. The solution, x = (1/g(u))ƒ(u), where g is always the least common monic denominator, can be recovered even if some evaluations are erroneous. In [Boyer and Kaltofen, Proc. SNC 2014] the problem is solved with an algorithm that generalizes Welch/Berlekamp decoding of an algebraic Reed-Solomon code. Their algorithm requires the sum of a degree bound for the numerators plus a degree bound for the denominator of the solution. We describe an algorithm that given the same inputs uses possibly fewer evaluations to compute the solution. We introduce a second count for the number of evaluations required to recover the solution based on work by Stanley Cabay. The Cabay count includes bounds for the highest degree polynomial in the coefficient matrix and right side vector, but does not require solution degree bounds. Instead our algorithm iterates until the Cabay termination criterion is reached. At this point our algorithm returns the solution. Assuming we have the actual degrees for all necessary input parameters, we give the criterion that determines when the Cabay count is fewer than the generalized Welch/Berlekamp count. We then specialize the algorithm for parametric linear system solving to the recovery of a vector of rational functions, (1/g(u))ƒ(u). If the rational function vector is the solution to a full rank linear system our early termination strategy applies and we may recover it from fewer evaluations than generalized Welch/Berlekamp decoding. We then show that if entries in our rational function vector are polynomials, then the vector can be viewed as an interleaved Reed-Solomon code. Thus if the errors occur in bursts we can again do better than generalized Welch/Berlekamp decoding. The aforementioned algorithms do not work when the matrix of the system, A(u)x = b(u), is rank deficient and some evaluations cause errors. We next present an algorithm for solving black box linear systems where the entries are polynomials over a field and the matrix of the system is rank deficient. The algorithm first locates and removes all errors, after which it computes a solution that satisfies the input degree bounds. Finally we view the recovery of a vector of polynomials as the decoding of interleaved Reed-Solomon codes. It is known that interleaved schemes improve the error correction capabilities of codes when errors occur in bursts. If we consider that the evaluations of the polynomials in the vector are done one at a time and that the errors are dependent then it is likely that errors occur in consecutive evaluations (bursts). An error model that considers consecutive entries in the vector to be wrong is a burst error model. We show how to encode and transmit data (polynomials) so that the data (polynomials) transmitted can be recovered with fewer evaluations than is required by Generalized Welch/Berlekamp decoding.

موضوع مستند نشده

Applied mathematics

مستند نام اشخاص تاييد نشده

Blackman, Terrance

مستند نام اشخاص تاييد نشده

Waddell, Cleveland Alexander

نام الکترونيکي

فرمت انتشار

p

نوع ماده

[Thesis]

کد کاربرگه

276903

سطح دسترسي

a

تكميل شده

Y