Talk: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 2ⁿ⁺¹ 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 2ⁿ 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 ${\begin{bmatrix}H&-H\end{bmatrix}}^{T}$, then there are 2^N+1 codes. Therefore, they can be described by an (N+1)-bit index. Therefore the code will be (2^N, N+1). How do you get (2^N, 2^N+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,2^k,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 (2ⁿ,2ⁿ⁺¹,2^n-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 [2ⁿ,n+1,2^n-1] code if it were known that all 2ⁿ⁺¹ 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 $\mathbb {F} _{2}^{m}$ 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).

• Amadei, M.; Manzoli, U.; Merani, M.L. (2002), On the assignment of Walsh and quasi-orthogonal codes in a multicarrier DS-CDMA system with multiple classes of users, vol. 1, Cambridge, pp. 841–845 {{citation}}: Unknown parameter |booktitle= ignored (help)

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".

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)

If a reliable source says that WH codes are obtained by rearranging H codes, then they are not obviously the same. We don't try to decide what reliable sources might have meant to say, we use what they do say. Deltahedron (talk) 07:38, 22 February 2013 (UTC)

The reliable literature is inconsistent. On page 393, the book

• van Bosse, John G.; Devetak, Fabrizio U. (2006), Signaling in Telecommunication Networks, Wiley Series in Telecommunications and Signal Processing, vol. 87 (2 ed.), John Wiley & Sons, ISBN 9780470048139

says "CDMA systems use two types of codes: Walsh codes (also called Hadamard codes) and pseudorandom noise (PN) codes." The subsequent discussion states that the number of "codes" (that is, codewords) equals the length of the "codes". This differs from the definition of Hadamard code in the mathematics literature, where the number of codewords is twice the length (since complements of codewords are also codewords). This tells me two things: (1) there are differences of opinion about whether "Walsh code" and "Hadamard code" mean the same thing or something slightly different; (2) the term "Hadamard code" has multiple, closely related, usages. One cannot write a decent Wikipedia article on this subject unless one is aware of the differences in how terminology is used by different authors and different disciplines.

I've been watching this page for a long time, and I just don't see that there is a large body of "informed editors" prepared to weigh in and resolve the discrepancies between different sources. I'm grateful that Ylloh has taken on the onerous task of describing the competing conventions and definitions that appear in the literature. I see no problem with the edits that have been made so far.Will Orrick (talk) 12:07, 22 February 2013 (UTC)

• I added a merger template to Walsh–Hadamard code. If there's no substantial opposition in the next few weeks, I suggest that the merger is completed (by replacing Walsh–Hadamard code with a redirect; the content has already been merged into Hadamard code). ylloh (talk) 18:04, 25 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)

On Wikipedia we go by what reliable sources say. We don't invent our own terminology. Deltahedron (talk) 07:33, 22 February 2013 (UTC)

That's exactly why I'm trying to ask for a discussion here. I handled the situation the way I did, and I'm interested in whether other editors have better ideas. ylloh (talk) 15:29, 22 February 2013 (UTC)

First, I want to acknowledge Ylloh for significantly improving this page. Second, I want to note that I am professor in ECE and teach graduate classes on this subject. I was drawn to this page because a student in my class was incorrectly using the term "punctured Hadamard code" based on this Wikipedia page. The "punctured Hadamard code" is a [2^k - 1, k,2^{k-1} - 1] code formed by puncturing any single bit of the Hadamard code (all are equivalent). This family is dual to the family of [2^k - 1,2^k - k - 1,3] Hamming codes, up to equivalence. For example, this reference [2] makes this point without discussing equivalence). I don't know if there is a standard term (other than 1st-order Reed-Muller) for the code this page calls the "punctured Hadamard code". Using standard terminology, however, it should be called the "augmented Hadamard code" because augmenting refers to increasing the dimension by one whereas puncturing refers to reducing the length by 1. Thus, I am going fix this on the main page. — Preceding unsigned comment added by Hpfister (talk • contribs) 15:48, 15 September 2019 (UTC)

External links modified

Hello fellow Wikipedians,

I have just modified one external link on Hadamard code. Please take a moment to review my edit. If you have any questions, or need the bot to ignore the links, or the page altogether, please visit this simple FaQ for additional information. I made the following changes:

• Added archive https://web.archive.org/web/20110720084646/http://www.complextoreal.com/CDMA.pdf to http://www.complextoreal.com/CDMA.pdf

When you have finished reviewing my changes, you may follow the instructions on the template below to fix any issues with the URLs.

This message was posted before February 2018. After February 2018, "External links modified" talk page sections are no longer generated or monitored by InternetArchiveBot. No special action is required regarding these talk page notices, other than regular verification using the archive tool instructions below. Editors have permission to delete these "External links modified" talk page sections if they want to de-clutter talk pages, but see the RfC before doing mass systematic removals. This message is updated dynamically through the template {{source check}} (last update: 18 January 2022).

• If you have discovered URLs which were erroneously considered dead by the bot, you can report them with this tool.
• If you found an error with any archives or the URLs themselves, you can fix them with this tool.

Cheers.—InternetArchiveBot (Report bug) 19:21, 27 October 2017 (UTC)

Not an inner product

The nondegenerate bilinear form defined in the article is not an inner product. Taking x = 1 yields a counterexample to the positive definiteness. — Preceding unsigned comment added by Ntheazk (talk • contribs) 16:37, 20 March 2020 (UTC)