Помогите запрограммировать программу по псевдокоду

Открытый ответов : 0 32 Опубликовано в: IT технологии
0
Имеется псевдокод, необходимо составить программу, реализующую арифметическое кодирование информации
Арифметическое кодирование

Input: Объем алфавита M
вероятности букв pi, i = 1, ..., M
длина последовательности n
последовательность на выходе источника (x1, ..., xn),
Output : Кодовое слово арифметического кода
Кумулятивные вероятности :
q1 = 0;
for i = 2 to M do
qi = qi?1 + pi?1;
end
Кодирование :
for i = 1 to n do
F ? F + q(xi)G;
G ? p(xi)G; .
end
Формирование кодового слова :
c ? первые [? log G] + 1 разрядов после запятой в двоичной записи числа F + G/2.

Принцип кодирования:
Пусть даны числа 0, 1, 2 и распределение вероятности P(0)=2/3, P(1/6), P(2)=1/6
Берешь отрезок [0, 1]. Разбиваем на части в соответствии с распределением.
Теперь на вход подается последовательность: 0102
первая цифра 0 => выбираем отрезок первый [0, 2/3] и разбиваем его в соответствии с распределением
вторая цифра 1 => выбираем в новом отрезке второй отрезок [4/9, 5/9] и разбиваем его на части в соответствии с распределением
и так далее.

В итоге получим какой-то отрезок. [x, y]. Надо найти двоичную дробь, например 0.01101, которая имеет минимальное число цифр и принадлежит этому отрезку. Тогда ответ: 01101 (это закодированное сообщение)

Ваш ответ

Ваше имя:
Капча:

Поделиться с друзьями

97,958 вопросов

21,949 ответов

3,424 комментариев

8,547 пользователей

Яндекс.Метрика
...