Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Is there such a thing as a nonlinear Hamming code?

Please give me a formal definition of Hamming code. Many that I've seen say that a Hamming code is binary, yet I've been given examples of non-binary Hamming codes.

share|improve this question
    
According to Wikipedia, Hamming codes are binary and linear –  Hagen von Eitzen May 2 '13 at 21:58
2  
This document contains some information on non-binary Hamming codes. The formal definition is on page 51. I'm not sure about nonlinear Hamming codes. If your (linear) Hamming code is $C$, you could form a nonlinear code $C'$ by taking some $x \not\in C$ and definining $C' = x + C$. However, I would hesitate to call that resulting code $C'$ a Hamming code, since the usual decoding method would no longer work. –  Snowball May 2 '13 at 22:29
    
@Snowball,hagen Thanks for the reference. I wonder why so many places define Hamming codes to be binary. –  Ryan May 2 '13 at 22:36
2  
Hamming codes in the usual sense are linear (check matrix given by listing the points of a projective space, see azimut's +1 answer). If we extend the notion to include all perfect single-error-correcting code (I don't think any author worth mentioning does this), then there are non-linear ones, too. The combinatorial mess of those is daunting, but I know one Bulgarian researcher who is/was serious about classifying them (and made significant progress). I'm sad to say there is a lot of variation in the quality of coding theoretical Wikipedia pages. –  Jyrki Lahtonen May 12 '13 at 7:07

1 Answer 1

up vote 5 down vote accepted

Hamming codes exist over any finite base field $\mathbb F_q$, and they are always linear.

Usually they are defined in the following way: A parity check matrix of the Hamming code of codimension $k$ is constructed by writing projective (= up to scalar multiples) representatives of the non-zero vectors in $\mathbb F_q^k$ into the columns of a matrix. If you take this matrix as a generator matrix, the dual of the Hamming code is generated, which is called Simplex code.

For example, for $q = 3$ and $k = 3$, there are $3^3 - 1 = 26$ non-zero vectors in $\mathbb F_3^3$, and a set of projective representatives consists of $26 / 2 = 13$ vectors. A parity check matrix of the Hamming code (and thus, a generator matrix of the Simplex code) is given by $$ \begin{pmatrix} 0 & 0 & 0 & 0 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\ 0 & 1 & 1 & 1 & 0 & 0 & 0 & 1 & 1 & 1 & 2 & 2 & 2 \\ 1 & 0 & 1 & 2 & 0 & 1 & 2 & 0 & 1 & 2 & 0 & 1 & 2 \end{pmatrix}. $$

By the way, this question is somewhat related.

share|improve this answer
    
Any idea how to determine the error correcting capabilities of a non-binary hamming code? –  sh1ftst0rm Jul 30 '13 at 18:59
    
EDIT: I guess more to the point, do you know how to determine the minimum codeword length required to get a functioning SECSED non-binary Hamming code? –  sh1ftst0rm Jul 30 '13 at 19:14
    
@sh1ftst0rm: The minimum distance of any Hamming code (binary or not, and independent of the dimension) is $3$. this mens that you can correct a single error, but not more. –  azimut Jul 30 '13 at 21:01
    
It appears that any Hamming code parity check matrix is universal, in that it will work for regardless of whether the data is in binary or some other base. And as azimut said, all Hamming codes have distance 3. The important point for non-binary codes is that when you create the Generator matrix from the parity matrix, the negation that happens has to be in the proper base. –  sh1ftst0rm Jul 31 '13 at 12:05
    
@sh1ftst0rm: The parity check matrix is not universal. Note the symbols $2$ in the above ternary example. –  azimut Jul 31 '13 at 12:29

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.