Analysis and Construction of Galois Fields for Efficient Storage Reliability
In this paper, we first analyze existing table-based implementation and optimization techniques for GF(2^l) multiplication and division. Next, we propose the use of techniques that perform multiplication and division in an extension of GF(2^l), where the actual multiplications and divisions are performed in a smaller field and combined. This approach allows different applications to share Galois field multiplication tables, regardless of the field size, while drastically lowering memory consumption. We evaluated multiple such approaches in terms of basic operation performance and memory consumption. We then evaluated different approaches for their suitability in common Galois field applications. Our experiments showed that the relative performance of each approach varies with processor architecture, and that CPU, memory limitations and field size must be considered when selecting an appropriate Galois field implementation. In particular, the use of extension fields is often faster and less memory-intensive than comparable approaches using standard algorithms for GF(2^l).
When:
Monday, June 4, 2007 at 3:00 PM
Where:
E2-599
CRSS Contact:
Greenan, Kevin