Article View: comp.theory
Article #1938Hamming codes algorithm needed
From: chchmeds
Date: Tue, 12 Jan 1993 03:00
Date: Tue, 12 Jan 1993 03:00
25 lines
1330 bytes
1330 bytes
I need an algorithm to solve the following problem:
Find a set of 32-bit binary numbers such that the Hamming distance
between every pair of them is (at least) a given constant (say 16).
We can stop finding numbers after we have 256 of them, but not before.
The Hamming distance between two numbers is the number of bits in which they
differ.
It is easy enough to get two numbers which differ in 16 positions. Getting
a third which differs from *both* the previous two is a little more
time-consuming, but not much. But after 20 of them, it gets very sluggish
indeed using a brute-force ("pick a random nunmber and try it") technique.
You may recognize such a set of numbers as a Hamming code. There are
well-known methods for generating Hamming codes of distance 3 to 6;
unfortunately they don't generalise to other distances.
TIA for any pointers.
Gordon
---
Gordon Findlay
Christchurch School of Medicine
Gordon@chmeds.ac.nz
chchemds@otago.ac.nz
Technical Details
Message-ID:
<1993Jan12.160004.505@otago.ac.nz>Path:
arc1-ca.pugleaf.net!sparky!uunet!munnari.oz.au!comp.vuw.ac.nz!canterbury.ac.nz!otago.ac.nz!chchmedsShow Full Headers
Complete Article Headers
Path: arc1-ca.pugleaf.net!sparky!uunet!munnari.oz.au!comp.vuw.ac.nz!canterbury.ac.nz!otago.ac.nz!chchmeds From: chchmeds@otago.ac.nz Newsgroups: comp.theory,comp.programming Subject: Hamming codes algorithm needed Message-ID: <1993Jan12.160004.505@otago.ac.nz> Date: 12 Jan 93 16:00:04 +1300 Organization: University of Otago, Dunedin, New Zealand Lines: 25