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
First and second order reed muller code words
Started by ●September 27, 2005
Reply by ●September 27, 20052005-09-27
<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.
Reply by ●September 28, 20052005-09-28
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