Hi everyone. I need to pick a set of 65 points p(x,y,z) in a 3D space of 274625 points; as the set picked should provide the maximum possible minimum Hamming distance. (Consider the Hamming bound for sphere packing). Can anybody please help me with developing an algorithm for naming these 65 discrete points? Thanks, Tan
$\begingroup$
$\endgroup$
5
-
2$\begingroup$ Have you read the FAQ, by any chance? $\endgroup$– David Roberts ♦Aug 15, 2012 at 12:26
-
2$\begingroup$ $274625 = 65^3$. If it's just a $65 \times 65 \times 65$ cube then the optimal packing of $65$ points with respect to Hamming distance is clear (see also D.Roberts' comment). $\endgroup$– Noam D. ElkiesAug 15, 2012 at 12:30
-
1$\begingroup$ If the $x,y,z$ are selected from the same set of 65 alternatives, then it seems clear to me that you want to use the 65 points on the 3D-diagonal, i.e. select the points of the form $(x,x,x)$. There are 65 of them, and the minimum Hamming distance between two points within this set is three. As any pair of points has Hamming distance at most three, this cannot be beaten. Or did you want to ask something else? $\endgroup$– Jyrki LahtonenAug 15, 2012 at 13:50
-
$\begingroup$ Lahtonen Thanks for your response. I guess i couldn't express it clearly. There are 65^3 alternatives (not 65) to chose from, and I need to chose the best 65 which satisfy the max minimum Ham.Dist. x,y,z are the dimensions of each point (so 3D). $\endgroup$– TanAug 16, 2012 at 8:31
-
$\begingroup$ Elkies thanks for your response. I get your approach, but the space is not a cube, but a space of 65^3 points in their densest (assumingly a sphere) form. I need to find out the (or one of the) set of 65 points among all within this packing, satisfying the max.minimal ham.dist. So the members of the set should be 1)at a maximum distance from each other, and 2)reside in the packing. Hope this better explains my goal. I also checked the FAQ but couldn't really get D.Roberts' comment. $\endgroup$– TanAug 16, 2012 at 8:48
Add a comment
|