Решать задачи на скорость передачи данных (объём = скорость × время) и на равномерное/префиксное кодирование сообщений.
Скорость канала и префиксные коды
Скорость канала и префиксные коды
Скорость передачи данных (пропускная способность канала) измеряется в бит/с, Кбит/с, Мбит/с. Основная формула: V = Q / t, где Q — объём данных (бит), t — время (с). Отсюда: Q = V × t, t = Q / V. Важно согласовывать единицы: 1 Кбит/с = 1000 бит/с (в телекоммуникациях используется десятичный Кило), 1 Мбит/с = 10⁶ бит/с. При решении задач сначала переводите всё в единые единицы.
Кодирование сообщений: при равномерном коде все символы кодируются одинаковым числом бит. Если алфавит содержит N символов, минимальная длина кода: ⌈log₂N⌉ бит. При неравномерном коде разные символы имеют разную длину кодового слова — это позволяет сжимать часто встречающиеся символы.
Условие Фано (префиксное условие): код позволяет однозначно декодировать сообщение без разделителей тогда и только тогда, когда ни одно кодовое слово не является началом (префиксом) другого. Например, если «а» = 0, то ни одно другое слово не должно начинаться с 0. Проверка: строим дерево кодов — каждый символ должен быть листом. Минимальная суммарная длина кода для сообщения = сумма (длина кода символа × частота символа).
Lesson notes
Скорость канала и префиксные коды
Скорость передачи данных (пропускная способность канала) измеряется в бит/с, Кбит/с, Мбит/с. Основная формула: V = Q / t, где Q — объём данных (бит), t — время (с). Отсюда: Q = V × t, t = Q / V. Важно согласовывать единицы: 1 Кбит/с = 1000 бит/с (в телекоммуникациях используется десятичный Кило), 1 Мбит/с = 10⁶ бит/с. При решении задач сначала переводите всё в единые единицы.
Кодирование сообщений: при равномерном коде все символы кодируются одинаковым числом бит. Если алфавит содержит N символов, минимальная длина кода: ⌈log₂N⌉ бит. При неравномерном коде разные символы имеют разную длину кодового слова — это позволяет сжимать часто встречающиеся символы.
Условие Фано (префиксное условие): код позволяет однозначно декодировать сообщение без разделителей тогда и только тогда, когда ни одно кодовое слово не является началом (префиксом) другого. Например, если «а» = 0, то ни одно другое слово не должно начинаться с 0. Проверка: строим дерево кодов — каждый символ должен быть листом. Минимальная суммарная длина кода для сообщения = сумма (длина кода символа × частота символа).