Extended Hamming encode/decode



I needed to write some very simple c routines (tempted to use
assembly, but not for this application at this time) to
handle the following extended hamming code cases:

[ 8, 4, 4]
[16, 11, 4]
[32, 26, 4]

(These are the total number of bits, number of data bits, and
the guaranteed Hamming distance between valid symbols.)

As indicated by the last number (the hamming distance between
valid symbols) these routines are able to correct single bit
errors and detect double-bit errors (SECDED.)

There are many different ways to perform such Hamming codes
and I've chosen a particular one among many. There are
others that also work. Although I've chosen a fairly well
documented form, it's certainly not the only possible form
and so it is that comparisons of the encoded results with
other algorithms may, or may not, match up bit for bit. But
the function remains and it does conform to some I've seen.

The code I've written uses no tables at all and is very
short. As such, it may be appropriate for small micro
embedded use. For example, the 16-bit Hamming version, on
the MSP430 using IAR and the standard "release" code
generation, yields 144 words of code. With the "debug" code
generation, it's 175 words, instead. For 32-bit Hamming
codes, "release" again, that nearly doubles to 248 words. But
that gives an idea. Cycle counts vary on inputs.

I've isolated these into three short modules -- one for each
of the three data types required. There's an encode and
decode routine in each. If anyone is interested in the
results, here's a link to the code.

http://www.infinitefactors.org/misc/hamm.zip

A very short demo program that tests the routines and
illustrates their use is also included. There is a small
file included where the specific data sizes can be specified
for a particular compiler.

They've been tested using a couple of compilers, Microsoft's
VC++ 1.52C DOS compiler and IAR's MSP430 (Workbench 5.0)
compiler, but not so thoroughly tested that I'm confident
they will compile well with all of them. The design reuses
code, where it seemed possible, and does NOT require special
data typedefs.

Much better could be had with assembly, but these satisfied
the need for now and, of course, assembly would require many
different instances to be coded. These routines can act as a
template, though, for deductions to specific assembly coding.

I will gladly modify them based upon useful input, as well.

Jon
.


Quantcast