Talk:Hadamard code
Latest comment: 12 years ago by Ylloh in topic "Punctured" Hadamard code
Old discussion
I corrected one serious error on this page. Someone should carefully check this and fix the others. —Preceding unsigned comment added by 71.179.164.101 (talk • contribs) 15:08, 9 March 2008
- If there are 2n+1 codewords, then k = n+1. Therefore, it was correct as it was. Oli Filth(talk) 17:25, 9 March 2008 (UTC)
- I believe the anonymous user was pointing out that unless the Hadamard matrix of order 2n used to produce the codewords is equivalent to the matrix obtained from Sylvester's construction, the resulting code will not be linear. For example, there are millions of Hadamard matrices of order 32, any of which can be used to construct a (32,64,16) code, but only when Sylvester's matrix is used will it also be a [32,6,16] code.
- As far as I am aware, some authors use “Hadamard code” to refer to this more general construction, which doesn't even require that the Hadamard matrix have power-of-two order.Will Orrick (talk) 04:04, 15 March 2008 (UTC)
- If the code is constructed as the rows of , then there are 2N+1 codes. Therefore, they can be described by an (N+1)-bit index. Therefore the code will be (2N, N+1). How do you get (2N, 2N+1)? In fact, that doesn't even make sense; in an (n,k) code, n cannot be less than k, otherwise you would be achieving perfect compression!
- I'm no expert on Hadamard matrices; by "there are millions of Hadamard matrices of order 32", are you implying that there are order-32 Hadamard matrices that cannot be derived from Sylvester's construction by simple row/column permutation? If so, we do indeed need to clarify that the code is based on matrices from Sylvester's construction. Oli Filth(talk) 15:41, 15 March 2008 (UTC)
- We need to make sure we are using notation for codes in the same way. In the mathematics literature the usual convention is that if a code is not known to have linear structure, its parameters are enclosed in parentheses, (n,M,d), and the middle parameter, M, is the number of codewords. (M will, of course, usually be much larger than n.) When the code is linear, that is, when the set of codewords is a vector space over some finite field, the parameters are enclosed in square brackets, [n,k,d], and the middle parameter, k, is the dimension of the vector space (which must be no greater than n). In the case of binary codes, an [n,k,d] code is a special type of (n,2k,d) code. I do not know to what extent this convention is followed in the larger coding theory literature. I have, in fact, encountered articles online where the roles of parentheses and square brackets are reversed!
- One can form a (2n,2n+1,2n-1) code from from any Hadamard matrix H, taking as codewords the rows of H and –H, with –1 replaced by 0. A mathematician would only call this a [2n,n+1,2n-1] code if it were known that all 2n+1 codewords could be expressed as linear combinations (over the field with two elements) of some set of n+1 basis vectors chosen from among the codewords, and this will not usually be the case when H is an arbitrary Hadamard matrix.
- It is indeed the case that there are Hadamard matrices that cannot be obtained from Sylvester's construction by permutation and/or negation of rows and columns. It is known from work of Marshall Hall that, in addition to the class of 16×16 Hadamard matrices that can be derived from Sylvester's construction, there are four other classes that cannot be so derived. Lin, Wallis, and Zhu showed that there are tens of thousands of classes in order 32, and this has recently been extended into the millions.
- I would be wary of insisting that Hadamard codes are only those codes derived from Sylvester's construction since a more general usage of the term “Hadamard code” seems to be widespread. (See, for example, §4.1 of Introduction to Coding Theory by van Lint.) It is possible that in the signal processing community the term has a more specific meaning.Will Orrick (talk) 03:35, 16 March 2008 (UTC)
Merged Walsh–Hadamard code into Hadamard code
The two articles were nearly identical and have now been merged. For this, I streamlined the definitions and moved the local decodability section to Hadamard code. The merger has been previously discussed here. Note that the article Walsh–Hadamard code originated from the article Walsh code, which is the name that seems to be used for this code in telecommunications / engineering. It would be good if someone could expand the article from that perspective a bit. ylloh (talk) 19:12, 21 February 2013 (UTC)
- Is there a reliable source that discusses the relationship between these terms? Deltahedron (talk) 19:40, 21 February 2013 (UTC)
- The problem is that sources from different fields and even sources within the same field call this object differently, and I did not find a single source that points out that there are different names. For example,
- Arora, Sanjeev; Barak, Boaz (2009), Computational Complexity: A Modern Approach, Cambridge, ISBN 978-0-521-42426-4, Zbl 1193.68112
- call it the Walsh-Hadamard code.
- Guruswami, Venkatesan. "List decoding of binary codes." [[1]]
- calls it Hadamard code, and notes "The order 1 RM [ Reed–Muller ] code corresponds to evaluations of linear polynomials on and is often called the Hadamard code" (furthermore, he points out in a footnote: "To be accurate, the Hadamard code only encodes linear polynomials with no constant term but this is a minor difference.", which means he's referring to the Hadamard code and not the "punctured" Hadamard code).
- call it Walsh code or Walsh family. They note that the "Walsh family can be interpreted as a subcode of the first-order Reed-Muller code". If you study these references, you will see that the definitions match the "Hadamard code" or the "punctured Hadamard code". Sorry I don't have a better answer, but I do believe that there should only be a single article on this object. ylloh (talk) 20:20, 21 February 2013 (UTC)
- So the short answer to the question is No. In future please wait for a consensus of informed editors before following your own personal research. Deltahedron (talk) 22:40, 21 February 2013 (UTC)
- This is not original research. I posted informed and relevant sources above and added them to the article itself. The routine change-of-notation that I used falls under Wikipedia:Scientific citation guidelines#Examples, derivations and restatements and is necessary to bring the material from different fields and different authors together. ylloh (talk) 04:31, 22 February 2013 (UTC)
- The book
- Du, K-Lin; Swamy, M. N. S. (2010), Wireless Communication Systems: From RF Subsystems to 4G Enabling Technologies, Cambridge University Press,
- on page 253, contains the statement "The Walsh codes, also known as the Walsh–Hadamard codes, are generated by rearranging the Hadamard codes".
- So the short answer to the question is No. In future please wait for a consensus of informed editors before following your own personal research. Deltahedron (talk) 22:40, 21 February 2013 (UTC)
- The problem is that sources from different fields and even sources within the same field call this object differently, and I did not find a single source that points out that there are different names. For example,
- One thing one must be careful of is that the word "code" has a different meaning in the wireless communication literature than it does in the mathematics and computer science literature. Where the wireless communication literature says "code", the mathematics literature says "codeword"; in mathematics, a code is a set of codewords. By my reading, the quote above is saying that the Walsh and Hadamard codes (in the sense of mathematics) consist of the same codewords, but that the codewords are ordered differently. This bears further investigation: in particular, I have not found where "Hadamard code" is defined in the reference above Will Orrick (talk) 02:37, 22 February 2013 (UTC)
- Yes, some people call codewords "codes". Thanks for the reference to Du & Swamy! I agree that they probably mean to say that the codewords are the same, but that the encoding function is different. ylloh (talk) 04:31, 22 February 2013 (UTC)
"Punctured" Hadamard code
In the literature, when the punctured Hadamard code is used, it is just called Hadamard code (or Walsh code). For the purposes of this article, I chose to use the term punctured Hadamard code to distinguish between the two variants of the Hadamard code. Another name would be "restricted Hadamard code" or "affine Hadamard code". An entirely different possibility would be to use a descriptive name for the purposes of this article. The Hadamard code would be the "inner product code" (it corresponds to applying all linear functions in k variables to the message) and the punctured Hadamard code would be the "affine inner product code" (because it corresponds to applying an affine linear function in k variables to the message). ylloh (talk) 04:31, 22 February 2013 (UTC)