№1 лабораторлыќ жђмыс
жүктеу/скачать 34,5 Kb.
|
№1 жұмысОПТИМАЛЬДЫ ТАҢБАЛАУДЫҢ АЛГОРИТМI.ШЕННОН-ФАНО ӘДІСІЕгер алфавит әрiптерiнiң пайда болу ықтималдылығы әр-түрлi болса, онда бiркелкi таңбалау (бiр символ бiр әрiпке сәйкес келу) отимальды болмайды, үйткенi тепе-тең хаостық күйдiң (, ықтималдықтар бiрдей жағдай) энтропиясы тепе-теңсiз, реттелген күйдiң энтропиясынан ылғи да үлкен болады. Сондықтан бiркелкi емес таңбалау қолданылады. Байқалуының көбiрек ықтималдылығы бар әрiптер үшiн қысқа тiзбектi таңбалау қолданылады, ал ұзын комбинациялар сирек әрiптер үшiн қолданылады. Шеннон-Фано әдiсiн қолданамыз. Алфавит әрiптерi (таңбаланатын кезкелген хабар) ықтималдылығы азаю ретi бойынша жазылады. Әрiптер қосқанда ықтималдылығы шамамен тең болатын екi топқа бөлiнедi. Одан соң екi топтың әрқайсысы ықтималдылықтарының қосындысы бiрдей болатын, тағы да екi топқа бөлiнедi. Бөлу алфавитте таңбалайтын бiр әрiп қалғанша жалғаса бередi. Әрбiр бөлу операциясынан кейiн ықтималдылығы жоғарғы бөлiктегi әрiптерге 1 таңбалау элементi, ал төменгi бөлiктегi әрiптерге - 0 сәйкестендiрiледi. (1 мен 0-дi ауыстырғанда не болатынын ойластырыңыз). Осы әдiспен алынған бiртексiз таңбалау бiр мәндi шешiлетiн таңбалау болып есептелмейдi. Бұл проблеманы шешу үшiн алфавит әрiптерiнiң арасына бөлгiш символ қолдану керек, немесе бастапқы бөлiгi жеке комбинация ретiнде қолданылған таңбалауды алып тастау керек. Мысалы, 101 бiр әрiптiң таңбасын бiлдiредi, онда 1,10 немесе 10101 комбинациясын қолдануға болмайды.
1 – кесте
Тапсырма: 1. 9 мүшеден тұратын тізбек үшін оптимальды таңбалау құрастырыңыз (і = 1, …, 9, x9 = 0,03) 2. берілген алфавит әріптерінің таңбасын құрастырыңыз. жүктеу/скачать 34,5 Kb. Достарыңызбен бөлісу:
|