ПМТ/К1 Јануар 2023

Овај рок није решен. Помозите SI Wiki тако што ћете га решити.

Поправни први колоквијум 2023. године одржан је 18. јануара 2023. и трајао је 2 сата.

Питање 1

Нека се при преносу података примењује заштитни блок код чија је генеришућа матрица:

$G=\begin{bmatrix} 1 & 1 & 0 & 1 & 0 & 1\\ 1& 0 & 1 & 0 & 1 & 0\\ 1& 1& 1 & 0 &0 & 0 \end{bmatrix}$

1. (3п) Одредити кодни количник овог кода и написати све кодне речи овог кода.
2. (1п) Колико је минимално Хемингово растојање у коду?
3. (1п) Колико највише грешака овај код може исправити, а колико детектовати?

Питање 2

1. (1п) Објаснити моноалфабетску шифру. Како се она може разбити?
2. (2п) Објаснити полиалфабетску шифру. Шта је то Вернамова шифра и зашто је она битна?
3. (2п) Описати укратко RSA алгоритам. У чему се огледа његова сигурност? Како се могу комбиновати симетрични и асиметрични криптосистем?

Задатак 1

Извршити Хафменово кодовање извора информација без меморије који емитује седам симбола са следећим вероватноћама:

Si	S₁	S₂	S₃	S₄	S₅	S₆	S₇
P(Si)	0.2	0.3	0.2	0.05	0.1	0.1	0.05

1. (3п) Одредити ентропију извора а затим и ефикасност и степен компресије добијеног кода.
2. (2п) Нацртати одговарајуће кодно стабло и означити хијерархијске нивое. Да ли је добијени код тренутан? Да ли је добијени код компактан?
3. (1п) Ако извор емитује секвенцу симбола S₂, S₆, S₄, S₁, S₅ и канал греши при преносу првог бита, одредити декодовану секвенцу.
4. (2п) Ако се на излаз Хафменовог кодера прикључи заштитни кодер са понављањем три пута а затим канал у коме је вероватноћа грешке p=10⁻¹, одредити укупан број бита који се шаље кроз канал за пример из претходне тачке. Колику вероватноћу грешке тада региструје корисник (декодер ради по принципу већинског одлучивања)? Како се мења број бинарних симбола пренетих кроз канал а како вероватноћа грешке коју региструје корисник ако се уместо понављања три пута примени код са понављањем три пута?

Задатак 2

1. (4п) Низ информационих бита 00100100 кодовати Хеминговим (8,4) кодом. Као последица шума који делује у каналу, 2, 7. и 10. бит у секвенци која се појављује на излазу кодера нису исправно примљени. Какви закључци се могу донети након процеса декодовања?
2. (2п) Ако се грешке у каналу појављују са вероватноћом p=10⁻³, израчунати вероватноћу да се појави грешка коју није могуће ни кориговати ни детектовати.