▼
Posts: 2,309
Threads: 116
Joined: Jun 2005
An nbit 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 HP16C program that determines the maximum possible number of code words in an 8bit 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 HP16C program in parallel with anyone else that wants to try this challenge.
The HP16C should have enough memory to solve this problem, and possibly problems with 9bit and 10bit code words, but I'm pretty sure that it won't be able to handle 11bit code words or larger.
▼
Posts: 2,309
Threads: 116
Joined: Jun 2005
This is a conjecture, and I haven't figured out a way to prove or disprove it:
For an nbit code (where n >= 4) with a Hamming distance of d (where 1 <= d < n/2), for odd valus of d there are 2^(n+22*d) code points, and for even values of d there are 2^(n+32*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.
▼
Posts: 260
Threads: 32
Joined: Jul 2005
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
▼
Posts: 2,309
Threads: 116
Joined: Jun 2005
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.
Posts: 1,477
Threads: 71
Joined: Jan 2005
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.unijena.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
▼
Posts: 2,309
Threads: 116
Joined: Jun 2005
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.
▼
Posts: 1,477
Threads: 71
Joined: Jan 2005
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
▼
Posts: 2,309
Threads: 116
Joined: Jun 2005
You're correct. I somehow missed that. The d < n/2 bound on my conjecture is wrong. Oh well.
Posts: 564
Threads: 72
Joined: Sep 2005
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 8bit 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 (nonsignificant 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 precreated.
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,mn)] { (n!/(nx)! * (mn)!/(mnx)! * (1 1/(2^x)) }
Cheers
Peter
▼
Posts: 2,309
Threads: 116
Joined: Jun 2005
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 bruteforce 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.
