Lucrarea de laborator nr. 2


Pentru problemele teoretice, se cere sa se rezolve pe hartie toate problemele.

Pentru problemele din al doilea set, se cere sa se scrie un program care sa rezolve problema data (se va rezolva una singura).

Probleme teoretice (toate sunt obligatorii):

  1. Fie codul:

    Mesaj Cuvant de cod
    a 0
    b 101
    c 11
    d 100

    Se cere sa se decodifice sirul 0101010111110101011

  2. Se considera multimea mesajelor $M=\{m_1, m_2,\dots,m_n\}$ si multimea simbolurilor de cod $S=\{0,1\}.$ Se cere sa se construiasca un cod cu proprietatea de prefix avand lungimile cuvintelor de cod date mai jos. Sa se argumenteze cazurile imposibile.
    1. $l_1=2,$ $l_2=1,$ $l_3=2,$ $l_4=2;$
    2. $l_1=2,$ $l_2=2,$ $l_3=3,$ $l_4=3,$ $l_5=2.$

  3. Aceeasi cerinta ca si la punctul precedent, dar cu multimea simbolurilor de cod $S=\{x, y, z\}$:
    1. $l_1=1,$ $l_2=2,$ $l_3=2,$ $l_4=2,$ $l_5=1;$
    2. $l_1=1,$ $l_2=2,$ $l_3=2,$ $l_4=2,$ $l_5=1,$ $l_6=3;$

  4. Sa se calculeze codul optimal pentru multimea simbolurilor de cod $S=\{0, 1\},$ pentru multimea de mesaje, cu frecventele de aparitie, date: $p_1=0.15,$ $p_2=0.55,$ $p_3=0.05,$ $p_4=0.01,$ $p_5=0.15,$ $p_6=0.09;$

    Apoi sa se calculeze lungimea medie a cuvantului de cod obtinut, si entropia sursei (H(M)).

  5. Acelasi enunt ca si la problema precedenta, dar pentru $S=\{x, y, z\}.$

  6. Presupunand probabilitatea ca un bit sa fie transmis eronat egala cu $10^{-4},$ calculati probabilitatea ca un sir de 1000 de biti sa contina 4 sau mai multe erori individuale.

  7. Consideram polinomul generator $g(X)=X^3+X^2+1.$ Luati ca informatie utila sirul 1001 (4 biti).
    1. Calculati bitii de control, si scrieti cuvantul de cod (complet)
    2. Modificati un bit oarecare, si verificati bitii de control

  8. Demonstrati ca daca polinomul generator este $g(X)=X+1,$ bitl de control este bit de paritate. Aratati ca CRC-ul astfel obtinut este capabil sa detecteze o eroare.

  9. Demonstrati ca daca polinomul generator divide polinomul $X^n+1,$ unde $n$ este numarul de biti ai cuvantului de cod, atunci orice permutare circulara a unui cuvant de cod este cuvant de cod.

  10. Demonstrati ca restul impartirii cuvantului receptionat la polinomul generator depinde numai de pozitiile erorilor, nu si de informatia transmisa.

Pentru urmatoarele probleme se cere un program (in orice limbaj instalat in laborator):

  1. Dandu-se un cod cu proprietatea de prefix si un sir de simboluri de cod, se cere sa se decodeze sirul. Se va construi si utiliza arborele asociat codului.

  2. Dandu-se frecventele de aparitie a unor mesaje, se cere sa se calculeze si sa se afiseze codificarea Huffman asociata. Se va calcula si afisa, in plus, lungimea medie a unui cuvant de cod (pentru codul generat), si entropia sursei.

  3. Dandu-se polinomul generator si lungimea cuvintelor de cod, se cere sa se determine prin incercari numarul de erori corectibile, precum si corespondenta intre resturile impartirii cuvantului receptionat la polinomul generator si pozitiile bitilor eronati. Apoi, dandu-se informatia utila sa se determine cuvantul de cod de transmis, si invers, danduse cuvantul receptionat sa se extraga informatia utila -- facand eventual corectia erorilor.

About this document ...

This document was generated using the LaTeX2HTML translator Version 2002-2-1 (1.70)

Copyright © 1993, 1994, 1995, 1996, Nikos Drakos, Computer Based Learning Unit, University of Leeds.
Copyright © 1997, 1998, 1999, Ross Moore, Mathematics Department, Macquarie University, Sydney.

The command line arguments were:
latex2html -split 0 -no_navigation lab-2.tex

The translation was initiated by Radu Lupsa on 2004-11-01

Radu Lupsa 2004-11-01