|
|
 | |  |
|
Билет 15
В компьютере информация представляется в двоичном виде, и, вообще говоря, кодирование информации в ЭВМ - одна из задач теории кодирования.
Теория кодирования - один из разделов теоретической информатики. Одна из задач - разработка принципов наиболее экономичного кодирования. Эта задача касается передачи, обработки, хранения информации. Частное ее решение – представление информации в компьютере.
Опред: источник представляет сообщение в алфавите, который называется первичным, далее это сообщение попадает в устройство, преобразующее и представляющее его во вторичном алфавите.
Код – правило, описывающее соответствие знаков (или их сочетаний) первичного алфавита знаком (их сочетаниями) вторичного алфавита.
Кодирование – перевод информации, представленной сообщением в первичном алфавите, в последовательность кодов.
Декодирование – операция обратная кодированию.
Кодер – устройство, обеспечивающее выполнение операции кодирования.
Декодер – устройство, производящее декодирование.
Операции кодирования и декодирования называются обратимыми, если их последовательное применение обеспечит возврат к исходной информации без каких-либо ее потерь.
Пример обратимого: слова - телеграфный код.
необратимого: английский - русский – здесь неоднозначно.
Далее будем иметь ввиду только обратимое кодирование.
Математическая постановка условия обратимого кодирования.
Пусть первичный алфавит А состоит из 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) / log2 M= I (A) , здесь I (A) - средняя информация на знак первичного алфавита.
Первая теорема Шеннона (переформулировка).
При отсутствии помех средняя длина двоичного кода может быть сколь угодно близкой к средней информации, приходящейся на знак первичного алфавита.
Какие же могут быть особенности вторичного алфавита при кодировании:
· Элементарные коды 0 и 1 могут иметь одинаковые длительности (t0=t1) или разные (?).
· Длина кода может быть одинаковой для всех знаков первичного алфавита (код равномерный) или различной (неравномерный код)
· Коды могут строиться для отдельного знака первичного алфавита (алфавитное кодирование) или для их комбинаций (кодирование блоков, слов).
Комбинации этих особенностей – основа конкретного способа кодирования. Их много.
Равномерное алфавитное кодирование.
Пример его использования – представление символьной информации в компьютере.
Определим, какой должна быть длинна кода:
· Компьютерный алфавит С включает 52 буквы латинского алфавита
· 66 букв русского (прописные и строчные)
· Цифры 0…9 – 10 штук
· Знаки математических операций, препинания, спецсимволы – 20 штук
Итого-148 символов.
К (С, 2) ? log2 148 ? 7,21, но длина кода – целое число, следовательно, К (С,2) =8. Именно такой способ кодирования принят в компьютерных системах. Называют 8 бит=1 байт, а кодирование байтовым
Один байт соответствует количеству информации в одном знаке алфавита при их равновероятном распределении. Это объемный (знакомый уже) способ измерения информации.
Итак. Символы (characters) в компьютере хранятся в виде числового кода, причем каждому символу ставиться в соответствии своя уникальная комбинация двоичных разрядов. В этом случае текст будет представлен как длинный ряд битов, в котором следующее друг за другом комбинации битов отражают последовательность символов в исходном тексте. Присвоение символу конкретного двоичного кода _ это вопрос соглашения, которое фиксируется в кодовой таблице – их существует несколько.
Таблица, в которой устанавливается однозначное соответствие между символами и их порядковыми номерами, называется таблицей кодировки.
Для разных типов ЭВМ используют различные таблицы кодировки. С распространением ПК типа IBM PC международным стандартом стала таблица кодировки под названием ASC II.
Американский национальный институт стандартов (American National Standards Institute, ANSI) принял американский стандартный код для обмена информации (American Standard Cod for Information Interchange – ASCII), который приобрел очень большую популярность. В этом коде комбинации двоичных разрядов длинной 7 бит используют для преставления строчных и прописных букв английского алфавита, цифр от 0 до 9, а также кодов управления передачей информации (перевод строки, возврат каретки, табуляция и т.д.). Определим мощность алфавита, зная, что каждый символ несет 7 бит информации: N=27=128, т.е. 7-ю битами можно закодировать 128 различных символов. Управляющие символы получили коды 0..31, 127. Символы, видимые на экране дисплея или на бумаге при печати, получили коды 32..126.
В наше время код ASCII часто употребляется в расширенном восьмиразрядном формате, который получается добавлением нуля в старший (7-ой) разряд байта. Но байт дает нам возможность закодировать 256 различных символов (N=28=256)! Следовательно, при использовании 7-битовой кодировки остается незадействованной половина кодовой таблицы. Поэтому коды 128..255, получаемые добавлением 1 в старший разряд, были выделены для представления символов, неподдерживаемых исходной версией кода ASCII – так называемых национальных символов и алфавитов, а также для символов псевдографики.
Но 01000001 представляет также букву А. Таким образом одна и та же комбинация из восьми битов может представлять как число, так и букву, а данном случае комбинаций 01000001 это 65, а с другой стороны – буква А. Все зависит от интерпретации битового содержания.
Если программа определяет элемент данных для арифметических целей, то 01000001 представляет двоичное число, эквивалентное десятичному числу 65.
Если программа определяет элемент данных (один смежный байт или более), имея в виду его описание, как, например, заголовок, тогда 01000001 представляет собой букву или "строку".
При программировании это различие становится понятным, так как назначение каждого элемента данных определено.
|
| Категория: Мои статьи | Добавил: aDr3naL1n (02.02.2011)
|
| Просмотров: 790
| Рейтинг: 0.0/0 |
| |
 | |  |
|
|
