🚀 go-pugleaf

RetroBBS NetNews Server

Inspired by RockSolid Light RIP Retro Guy

Article View: comp.theory
Article #1938

Hamming codes algorithm needed

#1938
From: chchmeds
Date: Tue, 12 Jan 1993 03:00
25 lines
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!chchmeds

Show 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