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

Лекция 2. Кодирование символьной информации

Кодирование информации в ЭВМ - одна из задач теории кодирования.

Теория кодирования - один из разделов теоретической информатики. Одна из задач - разработка принципов наиболее экономичного кодирования. Эта задача касается передачи, обработки, хранения информации. Частное ее решение – представление информации в компьютере.

Алфавит, в котором источник информации представляет сообщение, называется первичным.

Код – это соответствие знаков первичного алфавита знакам вторичного алфавита.

Кодирование – перевод сообщения из первичного алфавита во вторичный.

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

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

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

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

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

Пусть

первичный алфавит А сост. из 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)

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

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

Для двоичного кода М=2.

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