```
Subject:
```**Re: What's up with IEEE Scheme?**

From: rpw3@rigden.engr.sgi.com (Rob Warnock)

Date: 2000/10/15

Newsgroups: comp.lang.scheme

Message-ID: <8sb8f3$8vu19$1@fido.engr.sgi.com>

Anonymous <anonymous@anonymous.anonymous> wrote: +--------------- | Brian Campbell <lambda3@hotmail.com> writes: | > What does GF(blah) mean? | | Galois Field. +--------------- To go just a bit further... A Galois Field is simply a field with a finite number of elements. A field is (very crudely speaking) a set with an "addition" operator and a "multiplication" operator defined on it, with (most of) the usual rules of arithmetic -- identities for "addition" & "multiplication" (usually called "0" & "1"), additive and multiplicative inverses (except no multiplicative inverse for "0"), etc. You can prove that Galois Fields only come in certain sizes, namely a prime or a power of a prime, but not composite numbers (products of [powers of] different primes). So while there is a GF(27) and a GF(256), there is no GF(6). The most common/familiar representation of GF(p) [p a prime] is ordinary integer arithmetic with the results reduced modulo p, but that turns out not to work for GF(p^n) [n>1]. Galois Fields which are powers of 2 in size are very useful for checksums, error-correcting codes, cryptography, etc., and in this case the most common/familiar representation is polynomials with binary coefficients (which are neatly represented by ordinary binary integers), with addition of two polynomials being the XOR (addition mod 2) of the corresponding coefficients, and multiplication taken modulo a primitive "generator" polynomial of degree "n", where the field of is size 2^n. The basis of the argument thread about representations is that you can show that all possible representations for GF(n) (for some given "n") are isomorphic (that is, represent the "same" field), yet all representations are not equally useful or practical. In particular, I was arguing that the differences are strong enough to preclude defining a single "standard" representation for GF(n) (for each given "n"). +--------------- | > Could someone provide me with a reference? | You can find some on the web. +--------------- Indeed, lots. Here's a random sampling that might give you a flavor of the variety of representations/applications (and some tutorial stuff, too): <URL:http://grove.ufl.edu/~weijian/e6509_finalreport.htm> <URL:http://drake.ee.washington.edu/~adina/rsc/slide/slide.html> <URL:http://www.ddj.com/ftp/1994/1994.12/galois1.zip/BCKGRND.TXT> <URL:http://www.msdmag.com/98/9812/9812feat4.htm> <URL:http://www.4i2i.com/reed_solomon_codes.htm> <URL:http://lev.yudalevich.tripod.com/ECC/crc.html> <URL:http://www.cdg.org/tech/a_ross/LFSR.html> If you prefer books, my favorite general-purpose text is Lin & Costello's "Error Control Coding" <URL:http://shop.barnesandnoble.com/textbooks/ booksearch/isbninquiry.asp?isbn=013283796X>. -Rob ----- Rob Warnock, 31-2-510 rpw3@sgi.com Network Engineering http://reality.sgi.com/rpw3/ Silicon Graphics, Inc. Phone: 650-933-1673 1600 Amphitheatre Pkwy. PP-ASEL-IA Mountain View, CA 94043