2.Макмиллан теңсіздігі
Алфавиттік кодтау схемасы бөлінгішті деп аталады, егер кез-келген элементар кодтардан құралған сөз элементар кодтарға жалғыз әдіспен жіктелетін болса.
Бөлінгішті схемалы алфавиттік кодтау декодтауға рұқсат етеді. Префиксті схема бөлінгішті болатынын дәлелдеуге болады.
Алфавиттік кодтау схемасы бөлінгішті болуы үшін элементар кодтардың ұзындығы Макмиллан теңсіздігі деп аталатын қатынасты қанағаттандыруы керек.
Макмиллан теңсіздігі
Егер алфавиттік кодтау схемасы
бөлінгішті болса, онда
теңсіздігі орындалады.
Мысал
Алфавиттік кодтау схемасы
А={ а, b} и В={0, 1},
бөлінгішті болып табылады, себебі
демек, Макмиллан теңсіздігі орындалады:
Берілген схема префиксті болып табылмайды, себебі а әрпінің элементар коды b әрпінің элементар кодының префиксі болып табылады.
Достарыңызбен бөлісу: |
