ПМТ/К1 2022
< ПМТ
Пређи на навигацију
Пређи на претрагу
- Овај рок није решен. Помозите SI Wiki тако што ћете га решити.
Питање 1
Један извор емитује 6 симбола, Si, i=1,2,...6 са вероватноћама P(Si) датим у следећој табели. Нека је примењен алгоритам за компресију који симболима придружује кодне речи дате у трећој врсти табеле:
Si | S₁ | S₂ | S₃ | S₄ | S₅ | S₆ |
---|---|---|---|---|---|---|
P(Si) | 0.65 | 0.15 | 0.08 | 0.05 | 0.04 | 0.04 |
kodne reči | 0 | 10 | 1100 | 1101 | 1110 | 1111 |
- (2п) Нацртати кодно стабло које одговара овом коду.
- (2п) Да ли је овај код тренутан? Да ли је овај код могао бити добијен Хафменовим поступком (објаснити зашто)?
- (2п) Предоложити поступак компресије којим се постиже мања средња дужина кодне речи у односу на решење приказано у табели. Ако је то могуће, израчунати постигнуту средњу дужину кодне речи.
Питање 2
- (3п) Објаснити шифру транспозиције и шифру моноалфабетске замене - како се конструишу и како се анализом криптограма може открити да ли је примењена нека од ових шифара.
- (3п) У чему се огледа сигурност RSA алгоритма. Под којим условима је из јавног кључа тешко одредити тајни кључ?
Задатак 1
Извор информација без меморије емитује три симбола са следећим вероватноћама:
Si | S₁ | S₂ | S₃ |
---|---|---|---|
P(Si) | 0.5 | 0.25 | 0.25 |
- (1п) Одредити ентропију извора.
- (2п) Одредити кодне речи добијене применог Хафменовог поступка, израчунати ефикасност тако добијеног кода и постигнут степен компресије.
- (2п) Ако извор емитује секвенцу S3, S1, S2, S1, S3, примењен је код одређен у претходном делу задатка и канал греши при преносу трећег бита, одредити декодовану секвенцу.
- (2п) Да ли се може постићи већи степен компресије уколико би се пре примене Хафменовог поступка обавило проширење овог извора? Ако је то могуће, колико он износи?
Задатак 2
- (2п) Низ информационих бита 10100001 треба заштитити кодом са понављањем три пута. Као последица шума који делује у каналу, 2. 4. и 12. бит у послатој секвенци су неисправно примљени. Какви закључци се могу донети након процеса већинског декодовања?
- (2п) Низ информационих бита 10100001 треба заштитити Хеминговим (7,4) кодом. Као последица шума који делује у каналу, 2. 4. и 12. бит у послатој секвенци су неисправно примљени. Какви закључци се могу донети након процеса декодовања?
- (2п) Уколико се грешке у каналу појављују са вероватноћом p=10⁻³, колика је вероватноћа да декодер не исправи грешку у кодној речи ако је примењен код из првог дела задатка, а колика ако је примењен код из другог дела задатка? Навести предности и мане ова два заштитна кода.