Extended Hamming encode/decode
in [Embedded]
|
Prev: Announcement: New version of UML state machine code generator available
Next: CFP with Extended Deadline of Mar. 21, 2010: The 2010 International Conference on Computer Design (CDES'10), USA, July 2010
From: Jon Kirwan on 6 Mar 2010 19:56 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
From: Vladimir Vassilevsky on 6 Mar 2010 23:27 Jon Kirwan wrote: > 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.) If your goal is the absolutely the smallest code, Meggit decoder is a way to go. It is going to be rather slow though. It only takes ~10 lines of code to decode either of the codes; the decoder is going to be identical except for a couple of constants. Vladimir Vassilevsky DSP and Mixed Signal Design Consultant http://www.abvolt.com
From: Jon Kirwan on 7 Mar 2010 01:18 On Sat, 06 Mar 2010 22:27:56 -0600, Vladimir Vassilevsky <nospam(a)nowhere.com> wrote: >Jon Kirwan wrote: >> 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.) > >If your goal is the absolutely the smallest code, Meggit decoder is a >way to go. It is going to be rather slow though. It only takes ~10 lines >of code to decode either of the codes; the decoder is going to be >identical except for a couple of constants. I'll look at it. I'd looked on the web for a short bit and found abstract and overly large examples. But I don't recall checking that one out yet and it should be worth a moment to look, I suspect. The code I wrote is already done and if it suits anyone, it's there. After looking over a few on the web, I gave up hoping to find something that fit the need for decent speed _and_ size at one time and just decided to "do it" and move on. But thanks for the pointer. I'll look it over, tomorrow. In the meantime, I found a way to slightly shorten and speed things up in my case and have moved that version into the old slot on that link I gave. Jon
From: whygee on 7 Mar 2010 02:58 Jon Kirwan wrote: > Vladimir Vassilevsky wrote: >> If your goal is the absolutely the smallest code, Meggit decoder is a >> way to go. It is going to be rather slow though. It only takes ~10 lines >> of code to decode either of the codes; the decoder is going to be >> identical except for a couple of constants. I've never heard of Meggit, however SECDED is often good enough when speed is needed, for example in real-time communications (radio or long wires anyone ?) > I'll look at it. I'd looked on the web for a short bit and > found abstract and overly large examples. But I don't recall > checking that one out yet and it should be worth a moment to > look, I suspect. tell us what you end up with :-) > The code I wrote is already done and if it suits anyone, it's > there. After looking over a few on the web, I gave up hoping > to find something that fit the need for decent speed _and_ > size at one time and just decided to "do it" and move on. But > thanks for the pointer. I'll look it over, tomorrow. I've just downloaded it and had a very short look, and even tried to run the test : $ gcc hamm_08.h hamm_08.c hamm.c -o hamm $ ./hamm 1 2 3 (stuffs are displayed) so it seems to work and to be good enough for me :-) > In the meantime, I found a way to slightly shorten and speed > things up in my case and have moved that version into the old > slot on that link I gave. great ! thanks for the .zip, > Jon yg -- http://ygdes.com / http://yasep.org
From: Jon Kirwan on 7 Mar 2010 03:54
On Sun, 07 Mar 2010 08:58:17 +0100, whygee <yg(a)yg.yg> wrote: >Jon Kirwan wrote: >> Vladimir Vassilevsky wrote: >>> If your goal is the absolutely the smallest code, Meggit decoder is a >>> way to go. It is going to be rather slow though. It only takes ~10 lines >>> of code to decode either of the codes; the decoder is going to be >>> identical except for a couple of constants. >I've never heard of Meggit, however SECDED is often good enough >when speed is needed, for example in real-time communications >(radio or long wires anyone ?) I've not heard of Meggit, either. Perhaps Vladimir can discuss it, since he has put it on the table for us. >> I'll look at it. I'd looked on the web for a short bit and >> found abstract and overly large examples. But I don't recall >> checking that one out yet and it should be worth a moment to >> look, I suspect. >tell us what you end up with :-) I think I'll spare myself some time and wait for a short note from Vladimir about it. It seems something he knows about. >> The code I wrote is already done and if it suits anyone, it's >> there. After looking over a few on the web, I gave up hoping >> to find something that fit the need for decent speed _and_ >> size at one time and just decided to "do it" and move on. But >> thanks for the pointer. I'll look it over, tomorrow. >I've just downloaded it and had a very short look, and even >tried to run the test : >$ gcc hamm_08.h hamm_08.c hamm.c -o hamm >$ ./hamm 1 2 3 >(stuffs are displayed) > >so it seems to work and to be good enough for me :-) Hehe. Hopefully. If you define E32 or E16 in the command line and specify the other libraries (it's okay to specify them all, I suppose), then you can test the wider word sizes. You _do_ need to look at hamm_def.h to make sure it specs the right c lingo for the word sizes, though. >> In the meantime, I found a way to slightly shorten and speed >> things up in my case and have moved that version into the old >> slot on that link I gave. >great ! > >thanks for the .zip, No problem. If it helps in some way, I'm happy already. Jon > >> Jon >yg |