HP Forum Archive 15

[ Return to Index | Top of Index ]

HP-16C programming challenge - Hamming distance Message #1 Posted by Eric Smith on 23 Jan 2006, 8:41 p.m. An n-bit binary word can represet 2^n possible values. For error detection (and/or correction), it is useful to add some redundancy to a data word, forming a code word. The code word will of necessity have more bits than the data word; the number of bits required depends on the amount of redundancy. The degree of redundancy, and thus the code's capacity for detecting or correcting errors, may be measured as Hamming distance. The Hamming distance between two binary code words is the number of bits that differ between the two words. For instance, 01101000 and 00101010 differ in two bit positions, so they have a Hamming distance of two. The mimimum distance of a code is the minimum Hamming distance between any two code words of that code. The challenge is to write an HP-16C program that determines the maximum possible number of code words in an 8-bit code with minimum distance 3. If the program is run with flag 0 clear, it should end with the count of valid code words in the X register. If flag 0 is set, it should pause displaying each code word, then end with the count in X (the same as if flag 0 is clear). I have written a C program that solves this class of problems, but I'll be working on the HP-16C program in parallel with anyone else that wants to try this challenge. The HP-16C should have enough memory to solve this problem, and possibly problems with 9-bit and 10-bit code words, but I'm pretty sure that it won't be able to handle 11-bit code words or larger.

Conjecture about binary codes with minimum Hamming distance constraint Message #2 Posted by Eric Smith on 24 Jan 2006, 5:55 p.m., in response to message #1 by Eric Smith This is a conjecture, and I haven't figured out a way to prove or disprove it: For an n-bit code (where n >= 4) with a Hamming distance of d (where 1 <= d < n/2), for odd valus of d there are 2^(n+2-2*d) code points, and for even values of d there are 2^(n+3-2*d) code points. Based on this conjecture, the count for the challenge problem (n=8, d=3) would be 16. I haven't yet figured out how to generalize the conjecture for n/2 <= d < n, though it is obvious that for the d = n case the count will always be 2. Edited: 24 Jan 2006, 5:55 p.m.

Re: Conjecture about binary codes with minimum Hamming distance constraint Message #3 Posted by Klaus on 25 Jan 2006, 4:57 a.m., in response to message #2 by Eric Smith Hi Eric, Aren't there multiple possibilities for a code with a distance d? If I recall right, you need a codeword to start with to define a unique code. I do not have the time to program your challange, but determining the distance between two words should be easy: XOR the two words and use the [number of bits set] function. (certainly, you already use this approach). (1)First, I would zero all regs. (2)I would then use 0 as the first codeword, and store it in REG 0. (3)Increment this number and calculate the distance with all stored codewords. (4)if the minimum distance >=3, then store this number. Repeat steps 3+4 until Overflow bit is set after incrementing the number to test. I hope this pseudocode isn't considered as an impolite posting, but as noone posted something, I decided to do so. Greetings! Klaus

Re: Conjecture about binary codes with minimum Hamming distance constraint Message #4 Posted by Eric Smith on 25 Jan 2006, 12:56 p.m., in response to message #3 by Klaus Quote: Aren't there multiple possibilities for a code with a distance d? If I recall right, you need a codeword to start with to define a unique code. Since XOR is a linear function, if you start with particular seed values A or B as the base for finding valid codewords, you end up with codeword sets Sa and Sb such that Sb = Sa XOR (A XOR B). If the value B is in Sa, the sets are identical. Your proposed agorithm is the simpler of the two I've come up with, and is the one I've coded on the 16C. My other algorithm is in C code, and I haven't yet coded it for the 16C to compare run times.

Re: Conjecture about binary codes with minimum Hamming distance constraint Message #5 Posted by Katie Wasserman on 25 Jan 2006, 10:44 a.m., in response to message #2 by Eric Smith Eric, Interesting problem. The 16C's #B (count the number of bits) function should make this a particularly small and easy to write program. I assume that you've done some testing with various values of n,d to come up with this conjecture. But if the graph here http://www.personal.uni-jena.de/~pfk/mpp/ecc.html is correct I don't think your conjecture holds for larger values of n and d. Wouldn't this graph be linear for all values of n,d? -Katie

Re: Conjecture about binary codes with minimum Hamming distance constraint Message #6 Posted by Eric Smith on 25 Jan 2006, 1:11 p.m., in response to message #5 by Katie Wasserman I'm not sure. Normally a Hamming code used for ECC imposes an additional requirement that may not be met by all codes of minimum distance. For instance, suppose you have n data bits and want a Hamming code with a minimum distance of Hmin. You need a codeword size of cn, where cn is obviously larger than n. For efficiency in encoding and decoding, the code is constrained such that n bits of the codeword are identical to the n data bits (i.e., for a subset of n bits of the cn bit codeword, those n bits have all 2^n unique values). I'm not certain whether there may exist a smaller value of cn such that there is a set of codewords of cn bits that meet the minimum distance Hmin but do not have the n bit subset.

Re: Conjecture about binary codes with minimum Hamming distance constraint Message #7 Posted by Katie Wasserman on 26 Jan 2006, 11:46 p.m., in response to message #6 by Eric Smith Eric, I'm not sure about this -- there could be a bug in my program -- but I think that I found counterexamples to your conjecture. n=15, d=7 gives 32 codewords n=16, d=7 also gives 32 codewords Am I wrong? -Katie

Re: Conjecture about binary codes with minimum Hamming distance constraint Message #8 Posted by Eric Smith on 27 Jan 2006, 3:02 a.m., in response to message #7 by Katie Wasserman You're correct. I somehow missed that. The d < n/2 bound on my conjecture is wrong. Oh well.

Re: HP-16C programming challenge - Hamming distance Message #9 Posted by PeterP on 26 Jan 2006, 6:04 p.m., in response to message #1 by Eric Smith Eric, please accept my appologies upfront for probably completely misunderstanding the problem - I have never dealt with codes, error correction, hammond, etc. yet due to the light responses as well as the opportunity to learn something, please find below some thoughts of mine. It will be great when you point out the flaws to me: Asumption: For an 8-bit code with a minimum hamming distance of 3 I understood this to mean that all code words need to be different from all other code words by at least 3 bits. Starting Case: Lets assume those three digits are in the first three places. xxx00000. ignoring whatever we have in the last 5 digits, there are 2*2*2 such words, that are different in at least the first 8 digits. I shall call those first three digits “significant digits” or SD vs the other 5 digits NSD (non-significant digits) Extensions of starting case: Place 1 SD anywhere in the remaining 5 places to create another unique word, that is different in at least the three SD. There are 3*5 combinations of this rule However, halve the words created in such a way will be identical to all possible words that are created by having 3 SD and all combinations in the remaining 5 SD. Example: Starting Case: 101 xxxxx. This creates all words which have 101 in the first three digits and anything in the remaining 5 digits. The total of such IDENTICAL words is 2^5. One such words will be 101 xx1xx. If we now start switiching the first SD to another place, say the 6ht, we create words of the structure x01 xx1xx. This creates words of the structure 001 xx1xx and 101 xx1xx. As one can see, the second word is a combination we have seen already. In a similar vein, one can place 2 SD in the remaining 5 places, for 3*5*4 ways (3 ways to pick a pair from the 3 SD, 5*4 ways to place the pair in the remaining spots). However one out of ever 4 words created that way will be pre-created. And, last but not least, one can place all 3 SD in the remaining 5 places, 1*5*4*3 (1 way to pick 3 SD, 5*4*3 ways to place 3SD in 5 spots). However one out of ever 8 combinations we will have seen already. In summary we should have the following number of words: 2^3 * (1 + 3*5 -3*5/2 + 3*5*4 – 3*5*4/4 + 1*5*4*3 – 1*5*4*3/8) = 968 In general terms, for m digits and n distance: 2^n*(1 + Sum[x = 1 to min(n,m-n)] { (n!/(n-x)! * (m-n)!/(m-n-x)! * (1- 1/(2^x)) } Cheers Peter

Re: HP-16C programming challenge - Hamming distance Message #10 Posted by Eric Smith on 27 Jan 2006, 12:53 a.m., in response to message #9 by PeterP Now you've got me confused. With an eight bit code, there can't possibly be more than 256 codewords (minimum distance 1), and for larger minimum distances there have to be fewer valid codewords. For instance, for an 8 bit codeword with minimum distance 3, there are 16 valid codes. One set (in hexadecimal) is { 00, 07, 19, 1e, 2a, 2d, 33, 34, 4b, 4c, 52, 55, 61, 66, 78, 7f }. You can derive different sets, but they all are equivalent to that set with bit permutations and/or XOR by a constant. Note also that only 7 bits of the 8 are actually needed. Typically the eight bit would be used for word parity, which actually increases it to minimum distance 4. (Confirmed by doing a search for 8 bit codewords with minimum distance 4, which also results in 16 valid codewords.) I'm not distinguishing "data bits" from "ECC bits". I'm just considering the total number of bits in a codeword. Because an 8 bit codeword of minimum distance 3 (or 4) can have exactly 16 unique values, it can be used to encode 4 bits of data. I still have not come up with an analytical way to determine the number of codewords for a given bit count and minimum distance. My conjecture was based on output of the brute-force search program, and the patterns for d_min >= bits/2 are not readily apparent, which I think corresponds to the fluctuations in the curves on the ECC page Katie referenced earlier. Eric Edited: 27 Jan 2006, 2:59 a.m.

[ Return to Index | Top of Index ]

Go back to the main exhibit hall