Re: how presentation-dependent are BCH-codes?

koslowj wrote:
BCH-codes of length n arise as intersections of (conventional) Reed-
Solomon codes in some algebraic field extension of F=GF(q) with F^n.
For simplicity, let's assume gcd(n,q)=1 and work in the splitting
field G=GF(q^m) of x^n-1. Consider alpha in G of order n, and select
D-1 consecutive (modulo n) powers of a, e.g., alpha^{b+l}, l<D-1, for
some b<n; these are the roots of the induced Reed-Solomon code C'.

The generator polynomial g(x) of the resulting BCH code C is obtained
by closing up the set of roots above under conjugation and multiplying
all factors of the form (x-t), t in this extended set.

Now consider an element beta of G of order n, and find the longest
sequence of consecutive (modulo n) powers of beta among the roots of g
(x). (Note that this sequence need not have lengths D-1, as for
beta=alpha conjugation can already produce a longer sequence of
consecutive powers of alpha than the one we started with; I have an
example of this). Let C'' be the Reed-Solomon code with this new set
of roots.

Question: does C'' always yield the same BCH code over F as C'?

While alpha and beta produce the same _sets_ of powers, the
_ordered_sequences_ of powers differ by some permutation, which in
general fails to preserve consecutiveness.

Pointers to the literature are welcome, thanks!

-- Jürgen

Hi Jürgen!

If I understood your question correctly, then the answer seems to be negative. Let q=2, m=5 and n=31, so we work inside GF(32). For the sake of being definite we may take alpha to be a root of x^5+x^2+1. Consider the BCH (or RS) code with designed distance 5, so as roots of the generator polynomial we include the powers alpha^j, with j=1,2,3,4.
Out of these all but beta:=alpha^3 are conjugate, so the roots of the resulting generator polynomial of the BCH-code have zeros at the following powers of alpha:
1, 2, 4, 8, 16 <- these 5 are conjugates of alpha
3, 6, 12, 24, 17 <- these 5 are conjugates of beta

If I understood your intention correctly, then we basically want to find the longest run of the base-beta discrete logarithms of these guys. To do that observe that alpha=alpha^32=alpha^63=beta^21. Therefore the above (base-alpha) discrete logarithms become base-beta logarithms, if we multiply them by 21 modulo 31. So they are:
21, 11, 22, 13, 26 <- for conjugates of alpha
1, 2, 4, 8, 16 <- for conjugates of beta

As we see there are two longest runs among these logarithms. Both of them have length 2, (1,2) and (21,22). Unfortunately both of these pairs correspond to conjugate elements, so selecting either one as a generating set will yield a generator polynomial of degree 5 only (as opposed to the degree 10 generator polynomial we started with).

I may, of course, have misunderstoos your question. In order to avoid ambiguities like this the family of BCH codes is very often defined, not using consecutive powers of a fixed element of order n but any element of order n. Alternatively a set of exponents in an arithmetic progression (with difference coprime to n) is allowed. IIRC this is the full generality adopted in e.g. MacWilliams&Sloane or van Lint (GTM series). The reason is, of course that the standard proof for the BCH-bound for minimum distance goes through verbatim. The class of BCH-codes is then subdivided to primitive ones (where alpha is a primitive element of the field, i.e. a generator of the multiplicative group) and narrow sense BCH-codes (the run of exponents begins at zero or one, don't remember which :-).

To learn more about this you may also search for Hartmann-Tzeng bound. It is a slight generalization, and involves the union of translates of a given arithmetic progression. As an example of H-T bound I give (the only one I remember right now) the case where n=2^k+1, so alpha is in
the field of GF(2^(2k)). Here alpha^{-1} is a conjugate of alpha,
so the conjugates of alpha have discrete logarithms
....,-4,-2,-1,1,2,4,....
Here we have the arithmetic progressions (-4,-1,2) as well as its translate (-2,1,4). If k is even, then (3,n)=1, and we are in business.
The BCH-bound would only promise that the minimum distance of the code generated by the minimum polynomial of alpha would be at least 4=3+1, because we have an arithmetic progression of length 3 among the exponents. Because there are two such progressions, the H-T argument shows that the minimum distance must be at least 5. I don't remember exactly what is required about the set of translates, if there are more than two of them (may be the shift amounts also needed to form an arithmetic progression - I am not sure and can't be bothered to look it up now).

Have fun working with these!

Jyrki


.

Relevant Pages

  • Re: Lets discuss big bang theory some more.
    ... alpha e^2/hbar c ... The trouble starts here in using the emasculated cgs units to evaluate ... appropriate multiplier to the initial results. ... powers of alpha, and therefore different powers of c. ...
    (sci.physics)
  • Re: combinatorics question, should be easy
    ... Let alpha be a root of f. ... Powers of a root alpha of f can be seen as a basis (alpha^2, alpha, ... if you have some difference set S it is conjectured that all other ...
    (sci.math)
  • Re: Monte Cook joins Paizo for Pathfinder RPG
    ... level, Bards dramatically better in Alpha 3, the class pet replacement ... I haven't looked at Alpha 3, ... these rage-point powers are *more complicated* than the fighter ... the barbarian has never been so complex to play - can ...
    (rec.games.frp.dnd)
  • Re: quadratics with related roots
    ... > are alpha and beta, write down a quadratic whose roots are (two ... denoted by say C_1 and C_0 resp, which are symmetric polynomials ...
    (sci.math)
  • Re: quadratics with related roots
    ... > If the roots of the quadratic equation are ... > formulas involving alpha and beta), ... > I did maths at university and don't recall ever having do to anything ...
    (sci.math)