Порядок выполнения практического занятия

Выполнение практического занятия состоит в решении студентами задач в режиме интерактивного взаимодействия с преподавателем и с коллегами по группе, с анализом полученных результатов.

Задачи для решения

5.1. Алфавит некоторого сообщения включает в себя 4 символа, которые обозначим s₁,s₂,s₃ иs₄соответственно. При этом:

p(s₁) = 0.75;

p(s₂) =p(s₃) = 0.1;

p(s₄) = 0.05.

Источник сообщения памятью не обладает. Выполните кодирование символов s₁-s₄методом Хаффмана. Вычислите среднюю разрядность кода символа и эффективность сжатия.

5.2. Реализуйте кодирование по Хаффману символов сообщений, алфавит источника которых включает в себя 4 символа, причем вероятность появления одного из них в 3 раза выше, чем каждого из остальных (обозначив при этом символ с более высокой вероятностью появления как s₁, а остальные – какs₂,s₃иs₄). Рассчитайте среднюю разрядность кода символа и эффективность сжатия.

5.3. Выполните кодирование по Хаффману символов сообщений, алфавит источника которых состоит из 7-ми символов, один из которых встречается в 10 раз чаще, чем каждый из остальных (обозначив символ с большей вероятностью появления как s₁, а остальные – какs₂-s₇). Рассчитайте среднюю разрядность кода символа и эффективность сжатия.

5.4. Методом Хаффмана без Марковского прогнозирования осуществите кодирование символов сообщения:

419560, 419550, 419803, 419871, 419876, 419848, 419844, 419889.

Вычислите среднюю разрядность кода символа, а также эффективность сжатия относительно априорной энтропии, рассчитанной на базе предположения:

1) об отсутствии памяти у источника сообщения;

2) о наличии у источника сообщения памяти 1-го порядка.

5.5. Выполните кодирование символов сообщения, приведенного в условиях предыдущей задачи, методом Хаффмана с Марковским прогнозированием 1-го порядка. Рассчитайте среднюю разрядность кода символа, а также эффективность сжатия относительно априорной энтропии сообщения, вычисленной на основе предположения о наличии у его источника памяти 1-го порядка.

5.6. Методом Хаффмана без Марковского прогнозирования осуществите кодирование символов сообщения:

1.0000 V

1.0000 V

0.9999 V

1.0000 V

1.0001 V

1.0002 V

1.0001 V

1.0000 V

1.0000 V

0.9999 V

Вычислите среднюю разрядность кода символа, а также эффективность сжатия по отношению к априорной ИЭ данного сообщения, рассчитанной в предположении:

1. об отсутствии памяти у его источника;

2. о наличии у него памяти 1-го порядка.

5.7. Реализуйте кодирование символов сообщения, приведенного в условиях предыдущей задачи, методом Хаффмана с Марковским прогнозированием 1-го порядка. Рассчитайте среднюю разрядность кода символа и эффективность сжатия относительно априорной энтропии сообщения, вычисленной в предположении о наличии у его источника памяти 1-го порядка.

5.8. Определите длину (в битах) текста телеграммы “meet me tomorrow”после его сжатия методом Хаффмана без Марковского прогнозирования.

5.9. Реализуйте кодирование методом Хаффмана без Марковского прогнозирования следующей английской пословицы:

A FRIEND IN NEED IS A FRIEND INDEED.

5.10. Реализуйте кодирование символов сообщения, приведенного в условиях предыдущей задачи, методом Хаффмана с Марковским прогнозированием 1-го порядка.