Forums

First and second order reed muller code words

Started by Unknown September 27, 2005
Hi,

I am looking for first and second order reed muller code words of
length 31 (do they exist?). I have had a quick look on Google, but most
of the articles are on decoding strategies without actually listing the
code words. Would any of you know where these codes are tabulated? I
couldnt find them in Proakis or other Comms texts, either.

(In case you are wondering, I am working through the paper "Ternary
sequences with perfect periodic autocorrelation", Hoholdt and
Justensen, IEEE Trans. Info Theory, July 1983, p. 597. In this it
claims that in one particular subset of these sequences, the two Singer
difference sets used to generate the code, coincide with words of the
first and second order reed muller codes.)

Slainte
Porterboy

<porterboy76@yahoo.com> asked in message 
news:1127833486.656126.311650@z14g2000cwz.googlegroups.com...
> > I am looking for first and second order reed muller code words of > length 31 (do they exist?).
Reed-Muller codes are extended codes of length 2^m, so the codewords you seek are likely to belong to a punctured Reed-Muller code in which the overall parity bit has been deleted.
> without actually listing the > code words. Would any of you know where these codes are tabulated?
It is not clear why you want a list of codewords. The second-order Reed-Muller code of length 32 has 2^16 codewords, and so it is unlikely that someone has published a list of all the codewords. Of course, you can construct a codeword for yourself as follows. Choose a degree-2 Boolean polynomial in 5 variables: a(1,2)x_1x_2 + a(1,3)x_1x_3 + ... + a(4,5)x_4x_5 + a(1)x_1 + a(2)x_2 + ... + a(5)x_5 + a(0) where the a's are 0 or 1, the first row has 5-choose-2 = 10 terms, and the second row has 5 terms. Note that + means XOR in this context. Now, construct the truth table of this polynomial by evaluating it at (x_1, x_2, ... , x_5) = (0, 0, ... , 0) and then at (0, 0, ... ,0, 1) and then at (0, 0, ... , 1, 0) , .... (1,1,...,1). The truth table is your codeword.
> > (In case you are wondering, I am working through the paper "Ternary > sequences with perfect periodic autocorrelation", Hoholdt and > Justensen, IEEE Trans. Info Theory, July 1983, p. 597. In this it > claims that in one particular subset of these sequences, the two Singer > difference sets used to generate the code, coincide with words of the > first and second order reed muller codes.)
Unless you use the same order of evaluation as they did, it is unlikely that your codeword will match their sequence exactly.
Hello Dilip,

I guess you are the same D.V. Sarwate who is referenced twice in the
above paper ("cross correlation properties of pseudo-random and related
sequences", IEEE Proc, May 1980 & "construction of sequences with good
correlation properties", IEEE Trans Info Theory 1979) Thanks for your
reply.

My question may have sounded a little uneducated, but that's because it
is! My strengths are (linear) signal-processing and multirate theory, I
am really not so well versed in information theory and coding. So when
I read about Singer difference sets, quadrics, Abelian groups, modulo
arithmetic, Galois fields etc.,  I get a little out of my depth.

The reason I was going for Hoholdt's ternary codes based on the Reed
Muller codes is because so far I cannot follow the other method he uses
for code generation. He talks about cyclotomic classes and
nonmultipliers, which is so far Greek to me, and his notation is quite
gnomic (I am doing my homework, but it's slow!). In fact Hoholdt claims
(p. 599) that your sequences are a specific case of his general Ternary
sequences, so maybe it is your paper I should be reading. Sorry to say
I dont have access to it just yet.

Well, in the mean time, I will use your suggestion for generation of
the Reed Muller codes, although I guess if what you say is true, I am
unlikely to hit upon the correct codes. 

Slainte 
Porterboy