Overleg:Lee-code

Volume van een Lee-sfeer

Is er een bron of bewijs voor de in het artikel gegeven formule voor het volume van een Lee-sfeer?

Voorbeeld: q=9 en n=7. Als ik het volume bereken van de schil op afstand 4 dan kom ik uit op 1582. Voor de bol met e=4 kom ik op 2073. De op dit moment aanwezige formule geeft echter 2241 als resultaat. Bob.v.R (overleg) 26 mrt 2014 14:16 (CET)

Er zaten een paar onnauwkeurigheden in mijn handmatige berekening, er komt in dit voorbeeld toch 2241 uit voor het volume van de totale bol (en 1666 voor de schil op afstand 4). Nu eens kijken wat het algemene bewijs voor de formule kan zijn. Bob.v.R (overleg) 26 mrt 2014 22:51 (CET)

mooi dat je de moeite neemt om die berekeningen uit te voeren ;) De formule vond ik in het artikel "Coding for the Lee and Manhattan Metrics with Weighing Matrices" op arXiv.org, maar de oorspronkelijke bron is een artikel van S. W. Golomb en L. R. Welch, “Perfect codes in the Lee metric and the packing of polyominos”, SIAM Journal Applied Math., vol. 18, pp. 302–317, 1970. (niet vrij te raadplegen) En ja, ik kom ook 2241 uit. Je kan de grootte van die "sferen", S(n,e), overigens met een recursieve formule berekenen, die je kan afleiden uit de geometrische voorstellingen: een sfeer voor zekere "e" bestaat uit (2e+1) "laagjes" van vakjes, kubussen, n-dimensionale kubusachtige dingetjes... In twee dimensies /// 1 dimensie /// bevat de bovenste laag 1 vakje, de volgende 3, de volgende 5, enz. tot een maximum van 2e+1, daarna verminderen ze weer tot er 1 overblijft. In drie dimensies (n=3) /// twee dimensies (n=2) /// heeft de bovenste laag 1 kubusje, de volgende 5 (dit is S(2,1)), de volgende 13 (=S(2,2)), enz. Dat geeft de algemene formule:

S(n,e) = S(n-1,e) + 2 * som {S(n-1,i), i =0...e-1}

waarbij S(1,e)=2e + 1. Door die uit te rekenen voor S(7,4) kom ik ook uit op 2241. Klever (overleg) 27 mrt 2014 10:24 (CET)

Dank je voor je reactie! In je tekst hierboven heb ik (volgens mij) twee correcties toegevoegd. Misschien wil je even kijken of je die overneemt, dan wel deze weer verwijdert. De recursieve formule die je geeft is slim bedacht. Zelf had ik S(7,4) berekend zonder de n te variëren, maar door echt te tellen hoeveel woorden R(7,g) er in iedere 'schil' zitten, waarbij een schil bestaat uit alle woorden met 1 bepaald gewicht g. Bijvoorbeeld R(7,0)=1, R(7,1)=14, ...., R(7,4) = 1666. En daarna is S(7,4) = som{R(7,g), g = 0 ... 4}. Bob.v.R (overleg) 27 mrt 2014 12:05 (CET)

En algemeen: S(n,e) = som{R(n,g), g = 0 ... e}. Bob.v.R (overleg) 27 mrt 2014 18:42 (CET)