Content deleted Content added
→Merged Walsh–Hadamard code into Hadamard code: new section |
m Maintain {{WPBS}}: 2 WikiProject templates. Remove 1 deprecated parameter: field. Tag: |
||
| (23 intermediate revisions by 9 users not shown) | |||
Line 1:
{{WikiProject banner shell|class=C|
{{WikiProject Mathematics|priority=Low }}
{{WikiProject Computer science |importance=Low}}
}}
== Old discussion ==
I corrected one serious error on this page. Someone should carefully check this and fix the others. <small>—Preceding [[Wikipedia:Signatures|unsigned]] comment added by [[User:71.179.164.101|71.179.164.101]] ([[User talk:71.179.164.101|talk]] • [[Special:Contributions/71.179.164.101|contribs]]) 15:08, 9 March 2008</small><!-- Template:Unsigned -->
Line 23 ⟶ 29:
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 [[User_talk:Will_Orrick#Hadamard_code|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. [[User:Ylloh|ylloh]] ([[User talk:Ylloh|talk]]) 19:12, 21 February 2013 (UTC)
:Is there a [[WP:RS|reliable source]] that discusses the relationship between these terms? [[User:Deltahedron|Deltahedron]] ([[User talk: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,
::* {{Citation
| last1=Arora | first1=Sanjeev | authorlink1=Sanjeev Arora
| last2=Barak | first2=Boaz
| title=Computational Complexity: A Modern Approach
| url = http://www.cs.princeton.edu/theory/complexity/
| publisher=[[Cambridge University Press|Cambridge]]
| year=2009
| isbn=978-0-521-42426-4
| zbl=1193.68112
}}
::call it the Walsh-Hadamard code.
::* Guruswami, Venkatesan. "List decoding of binary codes." [[http://www.cs.cmu.edu/~venkatg/pubs/papers/ld-binary-ms.pdf]]
::calls it Hadamard code, and notes "The order 1 RM [ [[Reed–Muller code|Reed–Muller]] ] code corresponds to evaluations of linear polynomials on <math>\mathbb F_2^m</math> 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).
::* {{Citation
| last1=Amadei | first1=M.
| last2=Manzoli | first2=U.
| last3=Merani | first3=M.L.
| title=On the assignment of Walsh and quasi-orthogonal codes in a multicarrier DS-CDMA system with multiple classes of users
| publisher=[[Cambridge University Press|Cambridge]]
| year=2002
| pages=841–845
| booktitle=Global Telecommunications Conference, 2002. GLOBECOM'02. IEEE
| volume=1
}}
::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. [[User:Ylloh|ylloh]] ([[User talk: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 [[WP:OR|personal research]]. [[User:Deltahedron|Deltahedron]] ([[User talk: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. [[User:Ylloh|ylloh]] ([[User talk:Ylloh|talk]]) 04:31, 22 February 2013 (UTC)
:::The book
:::* {{Citation
| last1=Du | first1=K-Lin
| last2=Swamy | first2=M. N. S.
| title=Wireless Communication Systems: From RF Subsystems to 4G Enabling Technologies
| publisher=Cambridge University Press
| year=2010
}},
:::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 [[User:Will Orrick|Will Orrick]] ([[User talk: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. [[User:Ylloh|ylloh]] ([[User talk: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. [[User:Deltahedron|Deltahedron]] ([[User talk:Deltahedron|talk]]) 07:38, 22 February 2013 (UTC)
::::::The reliable literature is inconsistent. On page 393, the book
::::::* {{citation
| title=Signaling in Telecommunication Networks
| volume=87
| series=Wiley Series in Telecommunications and Signal Processing
| first1=John G.
| last1=van Bosse
| first2=Fabrizio U.
| last2=Devetak
| edition=2
| publisher=John Wiley & Sons
| year=2006
| 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.[[User:Will Orrick|Will Orrick]] ([[User talk: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]]). [[User:Ylloh|ylloh]] ([[User talk: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). [[User:Ylloh|ylloh]] ([[User talk:Ylloh|talk]]) 04:31, 22 February 2013 (UTC)
:On Wikipedia we go by what [[WP:RS|reliable sources]] say. We don't invent our own terminology. [[User:Deltahedron|Deltahedron]] ([[User talk: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. [[User:Ylloh|ylloh]] ([[User talk: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 [http://pages.cs.wisc.edu/~dieter/Courses/2013s-CS880/Scribes/PDF/lecture03.pdf] 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. <!-- Template:Unsigned --><small class="autosigned">— Preceding [[Wikipedia:Signatures|unsigned]] comment added by [[User:Hpfister|Hpfister]] ([[User talk:Hpfister#top|talk]] • [[Special:Contributions/Hpfister|contribs]]) 15:48, 15 September 2019 (UTC)</small> <!--Autosigned by SineBot-->
== External links modified ==
Hello fellow Wikipedians,
I have just modified one external link on [[Hadamard code]]. Please take a moment to review [https://en.wikipedia.org/w/index.php?diff=prev&oldid=807408345 my edit]. If you have any questions, or need the bot to ignore the links, or the page altogether, please visit [[User:Cyberpower678/FaQs#InternetArchiveBot|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.
{{sourcecheck|checked=false|needhelp=}}
Cheers.—[[User:InternetArchiveBot|'''<span style="color:darkgrey;font-family:monospace">InternetArchiveBot</span>''']] <span style="color:green;font-family:Rockwell">([[User talk:InternetArchiveBot|Report bug]])</span> 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. <!-- Template:Unsigned --><small class="autosigned">— Preceding [[Wikipedia:Signatures|unsigned]] comment added by [[User:Ntheazk|Ntheazk]] ([[User talk:Ntheazk#top|talk]] • [[Special:Contributions/Ntheazk|contribs]]) 16:37, 20 March 2020 (UTC)</small> <!--Autosigned by SineBot-->
| |||