Title :
Variation on variation on Euclid´s algorithm
Author :
Goupil, Alban ; Palicot, Jacques
Author_Institution :
France Telecom Res. & Dev., Cesson-Sevigne, France
fDate :
5/1/2004 12:00:00 AM
Abstract :
In a paper entitled "Variation on Euclid\´s Algorithm for Plynomials", Calvez et al. has shown that the extended Euclid\´s algorithm can be partially obtained by the nonextended one; in fact, it can obtain only two of the three unknowns of the Bezout\´s theorem. This letter goes further and shows that all polynomials given by the extended Euclid\´s algorithm and all the intermediate values can be obtained directly by the nonextended Euclid\´s algorithm. Consequently, only remainder computations are used. Avoiding multiplications and divisions of polynomials decreases the computational complexity. This variation of Calvez et al. justifies the title of the present letter.
Keywords :
computational complexity; polynomials; Bezout´s theorem; Euclid´s algorithm; computational complexity; polynomials; Blind equalizers; Computational complexity; Digital communication; Digital signal processing; Polynomials; Research and development; Signal processing algorithms;
Journal_Title :
Signal Processing Letters, IEEE
DOI :
10.1109/LSP.2004.824053