Subject: Re: What's up with IEEE Scheme?
From: rpw3@rigden.engr.sgi.com (Rob Warnock)
Date: 14 Oct 2000 01:40:09 GMT
Newsgroups: comp.lang.scheme
Message-ID: <8s8dhp$8js5p$1@fido.engr.sgi.com>
Dima Pasechnik  <d.pasechnik@quicknet.nl> wrote:
+---------------
| bjl@cs.purdue.edu (Bradley J Lucier) writes:
| > So I think there are too many (i.e., >1) incompatible ways to 
| > implement GF(2^k) that are useful for different algorithms
| > to have a useful standard implementation.
| 
| What does prevent you from providing conversions from one 
| representation to another?
+---------------

Because in some (but not other!) representations, there's a direct
correspondence with *external* data, such that a change of GF
representation destroys the correspondence. For example, in the
GF polynomials used for error-correcting codes, there is a big
distinction between "systematic" codes (those for which a subset
of the encoded bits *are* the unencoded "user" information bits)
and "non-systematic" codes.

In almost all cases, a conversion of a systematic code from one
GF representation to another will destroy the systematic property,
rendering the code useless for its originally-intended purpose.

(Of course, there are *other* purposes -- e.g., crypto -- for
which non-systematic codes are in fact preferable. But that's
another story...)

In short, while in theory all GF(x)s [for some "x"] are "the same",
in practice they really aren't.


-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