Веду на сто
Конспект

Кодирование и передача информации

Единицы информации, объем данных, системы счисления и условие Фано.

На экзамене

Задания 4, 7, 8, 11 и 14. Нужно считать объем и варианты, переводить числа между системами счисления и проверять код Фано.

Формулы и факты

Единицы и кодирование

  • 1 байт = 8 бит; 1 Кбайт = 1024 байта; 1 Мбайт = 1024 Кбайта.
  • Минимальная длина равномерного двоичного кода: i = \lceil \log_2 N \rceil, то есть 2^i \ge N.
  • Объем сообщения из K символов: I = K * i бит.
  • Число слов длины K из алфавита мощности N: N^K, если повторы разрешены.
ОбъектОбъем без сжатия
ТекстK * i бит
ИзображениеW * H * i бит
Звукf * t * i * c бит
ПередачаI = v * t; t = I / v

Для звука f: отсчетов в секунду, t: длительность, i: бит на отсчет канала, c: число каналов.

Системы счисления и Фано

(a_n a_{n-1}\ldots a_0)_q = \sum_{k=0}^{n} a_k q^k
  • В системе основания q допустимы цифры от 0 до q - 1.
  • Двоичные группы: по 3 бита для восьмеричной записи, по 4 бита для шестнадцатеричной.
  • Условие Фано: ни одно кодовое слово не является началом другого.

Алгоритм

Объем и передача

  1. Определи элементы: символы, пиксели, отсчеты или записи.
  2. Найди число элементов и бит на один элемент.
  3. Если дана мощность алфавита или палитры, округли \log_2 N вверх.
  4. Вычисли объем в битах, затем переведи единицы.
  5. Для передачи приведи объем и скорость к согласованным единицам.

Перевод и код Фано

  1. В десятичную: умножь цифры на степени основания справа налево, начиная с нулевой.
  2. Из десятичной: дели на новое основание, остатки читай снизу вверх.
  3. Для Фано сравни каждую пару слов: короткое не должно совпадать с началом длинного.
  4. При добавлении слова проверь его со всеми исходными словами в обе стороны.

Ловушки

  • Путают: биты и байты. Сверь: подпиши единицу каждого результата.
  • Путают: округление длины кода и общего объема. Сверь: сначала округли вверх биты одного символа.
  • Путают: моно и стерео. Сверь: для стерео множитель c = 2.
  • Путают: порядок остатков. Сверь: читай их от последнего к первому.
  • Путают: равные слова и префиксы. Сверь: ищи короткое слово в начале длинного.