Talk:Hadamard code

From Wikipedia, the free encyclopedia

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 , 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)