From: "bubba" Subject: Re: Maxidistant codes Date: Sat, 15 Jan 2000 19:47:11 -0600 Newsgroups: sci.math.num-analysis,sci.math Summary: [missing] Here are the 8-bit numbers arranged so that neighbors differ by exactly 3 bits (unless you count cycling 255 back to zero, where it fails): 0 00 1 07 2 09 3 02 4 05 5 08 6 03 7 04 8 0A 9 01 10 06 11 0B 12 0C 13 10 14 17 15 0D 16 11 17 16 18 0F 19 13 20 14 21 0E 22 12 23 15 24 18 25 1F 26 27 27 20 28 2B 29 19 30 1E 31 26 32 21 33 2A 34 1B 35 1C 36 24 37 23 38 28 39 1A 40 1D 41 25 42 22 43 29 44 2E 45 32 46 35 47 2C 48 30 49 37 50 2D 51 31 52 36 53 2F 54 33 55 34 56 39 57 3E 58 4E 59 40 60 47 61 49 62 42 63 45 64 48 65 38 66 3F 67 4F 68 41 69 46 70 4B 71 3B 72 3C 73 4C 74 50 75 43 76 44 77 4A 78 3A 79 3D 80 4D 81 51 82 56 83 58 84 53 85 54 86 59 87 52 88 55 89 5B 90 5C 91 57 92 5A 93 5D 94 65 95 62 96 69 97 64 98 63 99 68 100 66 101 5E 102 6A 103 61 104 6C 105 67 106 5F 107 6B 108 60 109 6D 110 71 111 76 112 6F 113 73 114 74 115 6E 116 72 117 75 118 78 119 7F 120 9F 121 83 122 84 123 89 124 82 125 85 126 88 127 86 128 81 129 8A 130 87 131 80 132 8B 133 8C 134 90 135 70 136 77 137 79 138 7E 139 9E 140 8D 141 91 142 96 143 8F 144 93 145 94 146 8E 147 92 148 95 149 98 150 A0 151 A7 152 A9 153 9B 154 7B 155 7C 156 9C 157 97 158 99 159 A1 160 A6 161 A8 162 9A 163 7A 164 7D 165 9D 166 A5 167 A2 168 AC 169 AB 170 B1 171 A4 172 A3 173 AD 174 AA 175 B0 176 B7 177 AE 178 B2 179 B5 180 AF 181 B3 182 B4 183 B9 184 BE 185 CE 186 C0 187 C7 188 C9 189 C2 190 C5 191 C8 192 B8 193 B6 194 BB 195 BC 196 CC 197 C1 198 C6 199 CB 200 D1 201 C4 202 C3 203 CD 204 BD 205 BA 206 CA 207 D0 208 D7 209 BF 210 CF 211 D3 212 D4 213 D9 214 D2 215 D5 216 D8 217 D6 218 DB 219 DC 220 E4 221 E3 222 E8 223 DA 224 DD 225 E5 226 E2 227 E9 228 E7 229 DF 230 EB 231 E0 232 ED 233 E6 234 DE 235 EA 236 E1 237 EC 238 F0 239 F7 240 EE 241 F2 242 F5 243 EF 244 F3 245 F8 246 FF 247 F1 248 FC 249 FB 250 F6 251 FD 252 FA 253 F4 254 F9 255 FE "Hendrik De Vloed" wrote in message news:8EBA70EDFhendriknospamdespamv@news.barco.com... > Hello everyone, > > For memory bit pattern tests I am looking into maxidistant codes, i.e. > two successive codewords have a maximal Hamming distance between them. > > So far I managed to come up with Walsh and Hadamard matrices, but don't > use all codewords. This is the algorithm (Perl) I came up with: > > @code=('0','1'); > > for $i (2..$length) { > @newcode0=map {"0".$_} @code; # prefix zero and one to the codes > @newcode1=map {"1".$_} @code; > @code=(); > for $j (0..($#newcode0)){ > # Swap every odd entry with the corresponding code but with > # the opposite prefix. > if(($j % 2)==1){ > my $tmp=$newcode0[$j]; > $newcode0[$j]=$newcode1[$j]; > $newcode1[$j]=$tmp; > } > } > push @code,@newcode0; # Concatenate the two half-codes. > push @code,@newcode1; > } > > This results in a code (e.g. length 4) of: > > --Maxidistant code of length 4 : > -- Format: ' codeword -- (distance_to_prev_code) ' > 0000 -- (1) > 1111 -- (4) > 0010 -- (3) > 1101 -- (4) > 0100 -- (2) > 1011 -- (4) > 0110 -- (3) > 1001 -- (4) > 1000 -- (1) > 0111 -- (4) > 1010 -- (3) > 0101 -- (4) > 1100 -- (2) > 0011 -- (4) > 1110 -- (3) > 0001 -- (4) > -- Minimal distance : 1 > -- Average distance : 3.125 > > The avg. distance seems to follow the formula ( (n*(2^n))+1) ) / (2^n), > with n=#bits-1. This is distinctly better than just linear counting, but I > was wondering if: > > * there are still better codes, with perhaps a larger minimal distance? > > * there is a specific math. field concerning this particular problem. > > * there is a name for "my" code. > > * there is an way to generate a "orthogonal" code where the bits that > didn't change between codes now change, and at the same time enforce the > same constraint horizontally. I.e. the two codes together test all bit- > toggles, both between codes and juxtaposed bits. > > I can imagine optimisation algorithms could sort the latter problem out, > but the code I need has 8 bits so 256! permutations are possible. And of > course it's a lot of work to write an optimisation algorithm just for this. > > Thanks in advance, > > Hendrik De Vloed >