For faster navigation, this Iframe is preloading the Wikiwand page for Lee-code.

Lee-code

Uit Wikipedia, de vrije encyclopedie

Een Lee-code is een foutcorrigerende lineaire code die men kan beschouwen als een uitbreiding van de Hamming-code naar niet-binaire woorden. Lee-codes kunnen gebruikt worden in die gevallen waarin niet-binaire signalen worden verzonden of opgeslagen.

Definities

Lee-afstand

Voor twee woorden van gelijke lengte met symbolen uit is de Lee-afstand gedefinieerd. Twee woorden en van symbolen hebben de Lee-afstand:

Deze metriek lijkt enigszins op de Manhattan-metriek.

Lee-sfeer

De verzameling bestaat uit alle woorden van de lengte met symbolen uit het alfabet .

De Lee-sfeer met straal rond een woord wordt gegeven door:

Dit is de verzameling van alle woorden met lengte waarvan de Lee-afstand tot niet meer bedraagt dan eenheden.

Lee-sferen hebben een meetkundige interpretatie. Voor bijvoorbeeld woorden met lengte 2 worden ze in het vlak voorgesteld door:

voor voor
Lee-sfeer voor 
Lee-sfeer 

enzovoort. Het woord bevindt zich in het midden van de figuur. De horizontale en verticale as komen overeen met de coördinaten en De woorden op een Lee-afstand ten hoogste bevinden zich in het centrum van de vierkantjes die binnen de figuur gelegen zijn. Dus 13 woorden liggen op afstand 2 of minder van

In drie dimensies () worden de vierkantjes kubussen die rondom een centraal punt gestapeld zijn.

Het volume (aantal woorden) van een Lee-sfeer is:

voor

Lee-code

Een deelverzameling is een e-foutencorrigerende Lee-code indien voor elk paar codewoorden geldt dat hun Lee-sferen met straal disjunct zijn:

De woorden die binnen de -sfeer van een codewoord uit liggen zijn "gedekt" door dat codewoord.

Perfecte Lee-code

Het aantal codewoorden, dus het aantal codeerbare boodschappen, van een e-foutencorrigerende Lee-code is zo groot mogelijk wanneer de Lee-sferen van de codewoorden een dichte pakking hebben. Een Lee-code is perfect wanneer:

wat betekent dat de Lee-sferen met straal van de codewoorden met lengte de vectorruimte volledig opvullen of betegelen; ze vormen een partitie van die ruimte. Met andere woorden elk woord van lengte wordt gedekt door een uniek codewoord uit

Alleen als een dergelijke betegeling van met Lee-sferen met straal mogelijk is, bestaat er een perfecte Lee-code, genoteerd als Er bestaan perfecte Lee-codes voor elke en voor elke Er bestaat geen [1]

Vermoeden van Golomb en Welch

Golomb en Welch[2] formuleerden het vermoeden dat er geen perfecte -foutencorrigerende Lee-codes bestaan voor en Het is nog niet in zijn algemeenheid bewezen, maar er zijn vele resultaten die het vermoeden bevestigen. Zo is onder meer bewezen dat er geen perfecte Lee-codes bestaan wanneer [3][4] Gravier et al. bewezen in 1998 dat er geen betegeling van de driedimensionele ruimte mogelijk is met Lee-sferen met een straal van 2 of meer. Dat bewijst het vermoeden van Golomb en Welch voor Het vermoeden is nadien ook bewezen voor en [1]

{{bottomLinkPreText}} {{bottomLinkText}}
Lee-code
Listen to this article

This browser is not supported by Wikiwand :(
Wikiwand requires a browser with modern capabilities in order to provide you with the best reading experience.
Please download and use one of the following browsers:

This article was just edited, click to reload
This article has been deleted on Wikipedia (Why?)

Back to homepage

Please click Add in the dialog above
Please click Allow in the top-left corner,
then click Install Now in the dialog
Please click Open in the download dialog,
then click Install
Please click the "Downloads" icon in the Safari toolbar, open the first download in the list,
then click Install
{{::$root.activation.text}}

Install Wikiwand

Install on Chrome Install on Firefox
Don't forget to rate us

Tell your friends about Wikiwand!

Gmail Facebook Twitter Link

Enjoying Wikiwand?

Tell your friends and spread the love:
Share on Gmail Share on Facebook Share on Twitter Share on Buffer

Our magic isn't perfect

You can help our automatic cover photo selection by reporting an unsuitable photo.

This photo is visually disturbing This photo is not a good choice

Thank you for helping!


Your input will affect cover photo selection, along with input from other users.

X

Wikiwand 2.0 is here πŸŽ‰! We've made some exciting updates - No worries, you can always revert later on