Тема 11: Представление информации в компьютере. Двоичное
кодирование. Равномерные и неравномерные коды. Декодирование сообщений,
записанных с помощью неравномерных кодов
Уч. https://profspo.ru/reader/book/132235
блог https://www.blogger.com/blog/settings/5176340769831596958
Для хранения, передачи и обработки
информации нужно как-то зафиксировать её, записать с помощью некоторой системы
знаков (знаковой системы).
Знак — это заменитель
какого-то объекта, который вызывает в сознании человека образ этого объекта.
Например, знак напоминает горнолыжника, такой знак называется пиктограммой.
Символ — это знак, о
значении которого люди договорились, наприме𠫧» — это символ параграфа, а —
символ рубля. Если значение символов неизвестно, мы не сможем понять смысл
сообщения, записанного с их помощью. Поэтому многие древние тексты до сих пор
не расшифрованы.
Знаки бывают зрительные (буквы, цифры,
ноты, дорожные знаки), слуховые (звуки устной речи, звуковые сигналы),
осязательные (азбука Брайля для слепых людей), обонятельные (их используют
животные).
Знаковая
система определяется алфавитом (набором используемых знаков) и правилами
выполнения операций с этими знаками.
Знакомые всем знаковые системы — это естественные языки, с помощью
которых люди общаются в быту (русский, английский, китайский и др.). В
естественных языках кроме правил есть и исключения. Кроме того, одно и то же
слово может иметь различный смысл в зависимости от контекста, т. е. отрывка
текста, в котором оно употребляется.
В научных публикациях такая ситуация
недопустима, потому что смысл текста должен быть понят однозначно. В таких
случаях используют формальные языки,
в которых каждое слово и словосочетание имеют чётко определённое единственное
значение, и нет никаких исключений. Примеры формальных языков — математические
и химические формулы, нотная запись, языки программирования. Все формальные языки — искусственные, они
разработаны людьми для обмена информацией в специальных областях знаний
Компьютерах
для кодирования всех видов информации используется специальная знаковая система
— двоичный код.
Аналоговые
и дискретные сигналы
Информация передаётся в закодированном
виде с помощью сигналов. Согласно определению, сигнал — это изменение свойств
носителя, которое используется для передачи информации. Изменение выбранного
свойства (например, силы тока, напряжения, освещённости) во времени можно описать
в виде функции. Далее такую функцию тоже будем называть сигналом, как это
принято в электронике и вычислительной технике.
В устройствах как радиоприёмник и
микрофон, изменение электрического сигнала может произойти в любой момент и
быть любым (в пределах допустимого диапазона). Такие сигналы называют аналоговыми.
Органы чувств человека воспринимают
информацию в аналоговой форме: свет, звуковые волны, вкус, запах и т. п.
Поэтому раньше большинство технических устройств для работы с информацией
(телефоны, магнитофоны, фотоаппараты) тоже были аналоговыми.
Аналоговый
сигнал
— это сигнал, который в любой момент времени может принимать любые значения в
заданном диапазоне
Сигналы, с которыми работает компьютер,
называются дискретными или цифровыми. Они обладают двумя важными свойствами:
•
изменяются только в отдельные моменты времени
(дискретность по времени);
•
принимают только несколько возможных значений
(дискретность по уровню).
Дискретный
(цифровой) сигнал
— это последовательность значений, принадлежащих некоторому конечному
множеству.
Дискретизация — это
представление непрерывного объекта в виде множества отдельных элементов.
Дискретизация означает, что мы представляем целое (непрерывное) в виде набора
отдельных элементов.
Равномерное
и неравномерное кодирование
Алфавит
— это
набор знаков, который используется в языке.
Мощность
алфавита — это
количество знаков в алфавите.
Равномерный
код —
это код, в котором все кодовые слова имеют одинаковую длину.
Неравномерный
код — это
код, в котором кодовые слова имеют различную длину.
Двоичное
кодирование — это
кодирование с помощью двух знаков.
1
бит — это одна двоичная цифра (один знак сообщения, записанного в
двоичном коде).
Равномерное кодирование
Если алфавит языка состоит из M знаков
(имеет мощность M), то количество различных сообщений длиной L знаков
вычисляется как
N = ML.
Двоичный код — это сообщение, использующее
алфавит из двух знаков (0 и 1), поэтому для двоичного кода эта формула
запишется в виде
N = 2L.
Неравномерное кодирование
При неравномерном кодировании коды
различных знаков могут иметь разную длину. Это делается для того, чтобы
сократить длину сообщения, используя сведения о частотах встречаемости различных знаков. Знаки,
которые встречаются в сообщениях чаще других (например, для текстов на русском
языке — это пробел и буквы «О», «Е» и «А»), получают более короткие коды, а
редко встречающиеся знаки — более длинные.
Правило умножения: N = M1 · M2 · ... ·ML,
где Mk — это возможное количество вариантов выбора знака в позиции k сообщения.
Правило сложения: N = Nk + Nk+1 + ... +
Nm, где Nq ( q = k, …, m) — это количество различных сообщений длиной q.
Декодирование
Условие
Фано
В некоторых случаях даже при использовании
неравномерного кода не требуется вводить символ-разделитель. Для этого
достаточно выполнения условия Фано: ни одно кодовое слово не совпадает с
началом другого кодового слова. Такой код называют префиксным
Сообщения, записанные с помощью
равномерного кода, всегда
декодируются однозначно.
• Для того чтобы сообщение, закодированное
с помощью неравномерного кода, можно было однозначно декодировать, достаточно
выполнения условия Фано: ни одно кодовое слово не является началом другого
кодового слова. Такой код называют префиксным.
• Условие Фано выполняется тогда и только
тогда, когда в дереве, построенном по кодовой таблице, все вершины-знаки
являются листьям
Комментариев нет:
Отправить комментарий