HP-16C programming challenge - Hamming distance



#11

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.


#12

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.


#13

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


#14

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.

#15

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


#16

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.


#17

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


#18

You're correct. I somehow missed that. The d < n/2 bound on my conjecture is wrong. Oh well.

#19

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


#20

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.


Possibly Related Threads...
Thread Author Replies Views Last Post
  Bought a 16C to compensate a little Eelco Rouw 23 1,745 12-07-2013, 01:26 PM
Last Post: Eelco Rouw
  Shiny new 16C! Keith Midson 7 628 10-27-2013, 02:22 AM
Last Post: Keith Midson
  HHC 2013 RPN Programming Challenge - Final Thought Jeff O. 7 640 10-17-2013, 11:02 AM
Last Post: Jeff O.
  Joys of eBay: HP-32S, HP-32SII, HP-42S, HP-16C, ... Sasu Mattila 7 620 09-23-2013, 04:39 PM
Last Post: Julián Miranda (Spain)
  HP-16C simulator fhub 12 902 06-30-2013, 10:14 PM
Last Post: Robert Prosperi
  Program for HP-16c... Leonid 9 748 06-07-2013, 08:51 PM
Last Post: David Hayden
  HP 11C/12C/15C/16C case Philippe Cairic 4 570 11-06-2012, 06:04 PM
Last Post: Matt Agajanian
  Understanding HP-16C integer division Jimi 18 1,237 10-16-2012, 09:13 PM
Last Post: Eddie W. Shore
  HHC 2012 RPN Programming Challenge Conundrum Jeff O. 15 958 10-08-2012, 03:34 PM
Last Post: Gerson W. Barbosa
  Mini-challenge: HHC2012 RPL programming contest with larger input David Hayden 14 1,039 10-05-2012, 10:36 PM
Last Post: David Hayden

Forum Jump: