Processing Galois Field arithmetic

US6766344B2 · kind B2 · utility

Assignee

• International Business Machines Corporation · US

Inventors

• Pradeep Kumar Dubey · New Delhi, IN
• Charanjit Singh Jutla · New York, US
• Josyula R. Rao · Briarcliff Manor, US
• Pankaj Rohatgi · Hartsdale, US
• Atri Rudra · New Delhi, IN
• Vijay Kumar · New Delhi, IN

Key dates

• Filing date: May 8, 2001
• Grant date: Jul 20, 2004
• Expiry date: Aug 21, 2022

Classification

• Technology area (CPC G): Physics
• CPC primary: G06F2207/7209
• WIPO field: Computer technology
• WIPO sector: Electrical engineering

Abstract

Efficient parallel processing of algorithms involving Galois Field arithmetic use data slicing techniques to execute arithmetic operations on a computing hardware having SIMD (single-instruction, multiple-data) architectures. A W-bit wide word computer capable of operating on one or more sets of k-bit operands executes Galois Field arithmetic by mapping arithmetic operations of Galois Field GF(2n) to corresponding operations in subfields lower order (m<n), which one selected on the basis of an appropriate cost function. These corresponding operations are able to be simultaneously executed on the W-bit wide computer such that the results of the arithmetic operations in Galois Field GF(2n) are obtained in k/W as many cycles of the W-bit computer compared with execution of the corresponding operations on a k-bit computer.