A modified Euclidean algorithm and the VLSI implementation

Author

Xu, Youshi

Author_Institution

Dept. of Telecommun., Mid-Sweden Univ., Sundsvall, Sweden

Volume

3

fYear

1996

fDate

13-16 May 1996

Firstpage

1324

Abstract

The extended Euclidean algorithm is important in algebraic and symbolic computations, in error correcting codes, in code division multiple access and, in cryptology. We propose a modified algorithm and a recursive implementation. Both the time and space complexity of the implementation is better than conventional ones. The regular and modular construction implies that it can be implemented on VLSI chips. The implementation can be used in decoding BCH codes, RS codes and Goppa codes. A throughput of hundreds of megabits per second is achievable

Keywords

BCH codes; Goppa codes; Reed-Solomon codes; VLSI; code division multiple access; computational complexity; cryptography; decoding; digital signal processing chips; error correction codes; integrated logic circuits; polynomials; BCH codes; CDMA; ECC; Goppa codes; RS codes; VLSI implementation; algebraic computations; code division multiple access; cryptology; error correcting codes; modified Euclidean algorithm; modular construction; recursive implementation; shift-register implementation; space complexity; symbolic computations; time complexity; Decoding; Equations; Error correction codes; Galois fields; Modular construction; Polynomials; Registers; Systolic arrays; Telecommunication computing; Very large scale integration;

fLanguage

English

Publisher

ieee

Conference_Titel

Electrotechnical Conference, 1996. MELECON '96., 8th Mediterranean

Conference_Location

Bari

Print_ISBN

0-7803-3109-5

Type

conf

DOI

10.1109/MELCON.1996.551191

Filename

551191