Инструменты пользователя

Инструменты сайта


examination:computer_science:question6

Вопрос №6 Кодирование информации. Основная теорема о кодировании при отсутствии помех

В компьютере информация представляется в двоичном виде, и, вообще говоря, кодирование информации в ЭВМ - одна из задач теории кодирования.

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

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

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

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

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

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

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

Пусть сообщение в первичном алфавите содержит n знаков, а закодированное – m знаков. Если исходное сообщение содержит IS(A) информации, а закодированное If(B), то условие обратимости кодирования (то есть неисчезновения информации при кодировании) очевидно может быть записано так: IS(A) ≤ If(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. Выбор такой формы определяется реализацией аппаратуры ЭВМ (электронными схемами), составляющими схематику компьютера, в основе которого лежит использование двоичного элемента хранения данных – триггера. Он имеет два устойчивых состояния (~ вкл., выкл.), условно обозначаемых как 0 и 1 и способен хранить минимальную порцию информации, называемую бит (binary digital).

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

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

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

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

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

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

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

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

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

examination/computer_science/question6.txt · Последние изменения: 2014/01/15 08:15 (внешнее изменение)