ПМТ/К1 2021

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

Први колоквијум 2021. године одржан је 6. новембра и трајао је 2 сата.

Питање 1

1. (2п) Блок шема телекомуникационог система са становишта теорије информација. На шта се мисли када се каже да је циљ обезбедити ефикасан, безбедан и поуздан пренос података?
2. (3п) Објаснити шифру транспозиције, моноалфабетску и полиалфабетску шифру. Како се анализом криптограма може закључити која је шифра примењена? Како се може направити шифра код које се из криптограма никако не може добити порука без познавања кључа?

Питање 2

У циљу повећања поузданости преноса података примењује се код чија је генеришућа матрица:

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

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

Задатак 1

Посматра се извор без меморије који емитује два симбола са следећим вероватноћама:

$S_i$	$S_1$	$S_2$
$P(S_i)$	0.75	0.25

1. (2п) Одредити ентропију извора, ефикасност и степен компресије бинарног статистичког кода који одговара оригиналном извору.
2. (2п) Одредити ентропију извора, ефикасност и степен компресије бинарног статистичког кода који одговара другом проширењу оригиналног извора.
3. (2п) Нацртати кодно стабло које одговара коду из претходне тачке (који одговара другом проширењу) и означити хијерархијске нивое. Да ли је овај код тренутан?
4. (2п) Ако би био примењен оптимални статистички код, колики је минимални број бинарних симбола којим се може представити 1000 симбола које емитује овај извор?

Задатак 2

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