Kraft ongelijkheid

Mei 16, 2016 Ester Gernaey K 0 10
FONT SIZE:
fontsize_dec
fontsize_inc

In coderingstheorie, '' 'ongelijkheid Kraft' '', zo genoemd omdat Leon Kraft, uiten voldoende voorwaarden voor het bestaan ​​van een prefix code, de noodzakelijke voorwaarden voor het bestaan ​​van een uniek decodeerbare code voor een bepaalde groep woord lengtes. Hun aanvragen om codes en voorvoegsels bomen worden meestal gebruikt in de informatica en informatie-theorie.

Meer specifiek Kraft ongelijkheid, beperkt de lengte van woorden in een prefixcode: indien de exponentiële van de lengte van elk goed woord genomen, moeten de resulterende verzameling waarden een waarschijnlijkheidsfunctie volgen, dat wil zeggen, de totale omvang Het moet kleiner zijn dan of gelijk aan één zijn. Kraft ongelijkheid kan worden begrepen in termen van een budget woorden te gebruiken, met de kortere woorden, de duurste.

  • Als Kraft ongelijkheid geldt strikt ongelijk, de code heeft een aantal redundantie.
  • Als Kraft ongelijkheid wordt voldaan, zodat het resultaat is precies gelijk aan 1, de code in kwestie is een complete code.
  • Als Kraft ongelijkheid niet in het bezit, de code is niet uniek decodeerbaar.

Definitie

Gegeven een bron van symbolen te worden gecodeerd met een alfabet van symbolen met behulp van een set woord lengtes, Kraft ongelijkheid komt overeen met:

Houd in gedachten dat:

  • Er moet een code naar een van de prefix conditiecodes zijn.
  • Het is voldoende om een ​​code met de code volgorde vast lengtes toestand: ....
  • Gegeven een bekende code, met een lengte die aan Kraft ongelijkheid, kunnen we niet beweren onmiddellijk te zijn. Echter, we weten dat er een onmiddellijke code lengtes ... sinds Kraft ongelijkheid wordt geverifieerd met een dergelijke reeks lengtes.
  • Merk op dat alle unieke decodeerbaar code voldoet Kraft ongelijkheid.
(0)
(0)
Vorige artikel PixInsight
Volgende artikel Embalse El Tunal

Commentaren - 0

Geen reacties

Voeg een Commentaar

smile smile smile smile smile smile smile smile
smile smile smile smile smile smile smile smile
smile smile smile smile smile smile smile smile
smile smile smile smile
Tekens over: 3000
captcha