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