Greetings:
(My apologies if this is not the correct forum. The people at
comp.compression were mute and had no opinion.)
I wish to create an Even-Parity Hamming code for an input file.
Part of the program is as follows:
(defun create-hamming (file)
(let (pattern byte i bitn hamming-bits)
(setq bitn 0 pattern 0 hamming-bits 0)
(setq byte (read-byte file nil))
(until (eql byte 'eof)
(dotimes (i 8)
(inc bitn)
(while (eq 1 (logcount bitn))
(inc hamming-bits)
(inc bitn))
(when (logbitp (- 8 i 1) byte)
(setq pattern (logxor pattern bitn))))
(setq byte (read-byte file nil)))
; return the pattern in hexadecimal
(format nil "~8,'0',X" pattern)))
Two questions:
1 - Does this program fragment truly create a bona fide Even-Parity
Hamming Code for the input file?
2 - Is there a more efficient way of producing the same Hamming Code?
Best regards,
Randyl Kent Plampin
Randyl wrote:
> (My apologies if this is not the correct forum. The people at
> comp.compression were mute and had no opinion.)
It is a reasonable forum for lisp questions, but possibly a
poor source of expertise about non-language subjects such as
Hamming codes.
> I wish to create an Even-Parity Hamming code for an input file.
> Part of the program is as follows:
>
> (defun create-hamming (file)
> (let (pattern byte i bitn hamming-bits)
> (setq bitn 0 pattern 0 hamming-bits 0)
> (setq byte (read-byte file nil))
> (until (eql byte 'eof)
> (dotimes (i 8)
> (inc bitn)
> (while (eq 1 (logcount bitn))
> (inc hamming-bits)
> (inc bitn))
> (when (logbitp (- 8 i 1) byte)
> (setq pattern (logxor pattern bitn))))
> (setq byte (read-byte file nil)))
> ; return the pattern in hexadecimal
> (format nil "~8,'0',X" pattern)))
>
> Two questions:
>
> 1 - Does this program fragment truly create a bona fide Even-Parity
> Hamming Code for the input file?
I'm pretty sure this program does not compute an Even-Parity
Hamming code, or anything else interesting. It looks like
something you typed in without running, and there are numerous
errors in the code. In fact, I can't even be sure which Lisp
dialect is intended. Perhaps you should get the algorithm
running before asking what it does.
> 2 - Is there a more efficient way of producing the same Hamming Code?
Almost certainly there is a more efficient way. If I understand
Hamming codes correctly, the code rewrites single bytes (of some
length) into bytes of some longer length, adding multiple
parity bits to the byte. Sometimes these parity bits are appended
directly to the source byte, sometimes they are transmitted
separately, but that is only an implementation detail.
If this is correct, then an obviously more-efficient algorithm
is simply to use table lookup. A Hamming code mapping 8-bit
bytes onto 12 bits requires only 512 bytes of table. A code
mapping 16-bit bytes onto 21 bits requires only 3#2^16 bytes.
For longer Hamming words where the memory footprint for the
translation table would be excessive, I suspect it would be
possible to decompose the Hamming matrix into tables for two
half-words, then and somehow combine the results of two half
words. However, I haven't thought through the details.