Hamming code

[guysbarash@gmail.com]

Given a binary string of length n of valid data. what is the minimal number of parity bits i have to add in order to create hamming distace of D between each valid word?

 

thx in advance

[fiveworlds]

0 binary strings are electrical how that binary string is interpreted is arbitary. Say for instance I have 3 leds and 3 switches and the octal 010 meaning the middle switch is on. Given no circuitry in between you have no idea if I have lit any or all of the leds. If I change the circuit I can change which led I light while leaving the middle switch on. Perhaps I should expand this the hamming distance between "toned" and "roses" is three. However as binary they could be both "000,001,010,011,100" being read by two different machines. So one machine outputs "toned" the other "roses" but between "000,001,010,011,100" and "000,001,010,011,100" there is a hamming distance of zero because it's always the same

Edited June 15, 2014 by fiveworlds

[Enthalpy]

Hi Guysbarash, welcome here!

 

This query is difficult. It is equivalent to predicting the length of an error-correcting code given the number of data bits and the number of positions to correct (=half the distance).

 

No general response exists, but heuristic bounds are known which are not bad.

 

A naive strict minimum is rather simple, but rarely attained (by Hamming codes, the Golay code, and I know no other so-called "perfect" code).

http://en.wikipedia.org/wiki/Binary_Golay_code

Take the length of the code which includes the redundancy, compute all combinations of 0 to D modified positions in this code: their binary log must be smaller than the length of the redundancy - just to contain enough information.

 

Most codes do not attain the minimum length, and even less so if one wishes a method to decode them, which is generally the case. The Bch codes are general, can be long, and are not bad. They add Log₂(length including redundancy +1) redundancy bits for every distance bit.

http://en.wikipedia.org/wiki/BCH_code

Hamming codes are less general than your query, as they guarantee only one corrected bit.

http://en.wikipedia.org/wiki/Hamming_code

 

In error-correcting codes, we say "redundancy" rather than "parity", among others because some codes are not binary, for instance the Reed-Solomon ones

http://en.wikipedia.org/wiki/Reed-Solomon

http://en.wikipedia.org/wiki/Reed-Solomonhttp://en.wikipedia.org/wiki/Reed-Solomonhttp://en.wikipedia.org/wiki/Reed-Solomon

Edited July 21, 2014 by Enthalpy