Первая теорема Шеннона

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

Представление информации в ЭВМ

Источник представляет сообщение в алфавите, который называется первичным, далее это сообщение попадает в устройство, преобразующее и представляющее его во вторичном алфавите.

• Код – правило, описывающее соответствие знаков (или их сочетаний) первичного алфавита знаком (их сочетаниями) вторичного алфавита.

• Кодирование – перевод информации, представленной сообщением в первичном алфавите, в последовательность кодов.

• Декодирование – операция обратная кодированию.

• Кодер – устройство, обеспечивающее выполнение операции кодирования.

• Декодер – устройство, производящее декодирование.

Операции кодирования и декодирования называются обратимыми, если их последовательное применение обеспечит возврат к исходной информации без каких-либо ее потерь.

Пример обратимого: слова ↔ телеграфный код.

необратимого: английский ↔ русский – здесь неоднозначно.

Далее будем иметь ввиду только обратимое кодирование.

Математическая постановка условия обратимого кодирования.

Пусть первичный алфавит А состоит из N знаков со средней информацией на знак I^А, вторичный В – из М знаков со средней информацией на знак I ^В .

Пусть сообщение в первичном алфавите содержит n знаков, а закодированное – m знаков. Если исходное сообщение содержит I_S (A) информации, а закодированное I_f (B), то условие обратимости кодирования (то есть неисчезновения информации при кодировании), очевидно, может быть записано так:

I_S (A) ≤ I_f (B) - то есть операция обратимого кодирования может увеличить количество информации в сообщении, но не может уменьшить ее.

n* I ^(A) ≤ m* I ^(B) (заменили произведением числа знаков на среднее информационное содержание знака).

Отношение m/n –характеризует среднее число знаков вторичного алфавита, который используется для кодирования одного знака первичного. Обозначим его К (А, В)

К (А, В)≥ I ^(A) / I ^(B) Обычно К (А, В) >1 => знак первичного алфавита кодируется несколькими вторичными =>? – проблема выбора наилучшего варианта – оптимального кода.

Оптимальность - это экономический фактор (меньше энергии, времени, объема носителя - уже в зависимости от задачи и поставленных ограничений).

Минимально возможная длина кода: К^min (А, В)= I ^(A) / I ^(B) –это нижний предел длины кода. Но реально в схемах кодирования как близко возможное приближение К (А, В) к К^min (А, В).

При отсутствии помех всегда возможен такой вариант кодирования сообщения, при котором среднее число знаков кода, приходящихся на один знак первичного алфавита, будет сколь угодно близко к отношению средних информаций на знак первичного и вторичного алфавитов.

Таким образом, оптимальное кодирование принципиально возможно.

Наиболее важна для практики ситуация, когда М=2, то есть информацию кодируют лишь двумя сигналами 0 и 1.

Компьютер - универсальное устройство, всю информацию в нем представляют в виде двоичного набора изображающих знаков 0 и 1. Выбор такой формы определяется реализацией аппаратуры ЭВМ (электронными схемами), составляющими схематику компьютера, в основе которого лежит использование двоичного элемента хранения данных – триггера. Он имеет два устойчивых состояния (~ вкл., выкл.), условно обозначаемых как 0 и 1 и способен хранить минимальную порцию информации, называемую бит (bi nary digi t al).

Шенноном была рассмотрена ситуация, когда при кодировании сообщения в первичном алфавите учитывается различная вероятность появления знаков, а также равная вероятность появления знаков вторичного алфавита. Тогда:

К^min (А, В)= I ^(A) / log₂ M= I ^(A) , здесь I ^(A) - средняя информация на знак первичного алфавита.

Первая теорема Шеннона (переформулировка).

При отсутствии помех средняя длина двоичного кода может быть сколь угодно близкой к средней информации, приходящейся на знак первичного алфавита.

Какие же могут быть особенности вторичного алфавита при кодировании:

Элементарные коды 0 и 1 могут иметь одинаковые длительности (t0=t1) или разные (≠).

Длина кода может быть одинаковой для всех знаков первичного алфавита (код равномерный) или различной (неравномерный код)

Коды могут строиться для отдельного знака первичного алфавита (алфавитное кодирование) или для их комбинаций (кодирование блоков, слов).

Комбинации этих особенностей – основа конкретного способа кодирования. Их много. Мы рассмотрим

Равномерное алфавитное кодирование.

Пример его использования – представление символьной информации в компьютере.

Определим, какой должна быть длинна кода:

· Компьютерный алфавит С включает 52 буквы латинского алфавита

· 66 букв русского (прописные и строчные)

· Цифры 0…9 – 10 штук

· Знаки математических операций, препинания, спецсимволы – 20 штук

Итого-148 символов.

К (С, 2) ≥ log₂ 148 ≥ 7,21, но длина кода – целое число, следовательно, К (С,2) =8. Именно такой способ кодирования принят в компьютерных системах. Называют 8 бит=1 байт, а кодирование байтовым

Один байт соответствует количеству информации в одном знаке алфавита при их равновероятном распределении. Это объемный (знакомый уже) способ измерения информации.

Дата добавления: 2014-10-17