Преобразование информации из непрерывной в дискретную. Двоичное кодирование.

На прошлых уроках мы узнали:

·      Информация для человека – это система посланий или сигналов, которые человек получает из различных источников.

·      Сигналы представляют собой некоторые изменения физических величин. Получая информационные сигналы человек их каким-то образом связывает и интерпретирует.

·      Сигналы бывают двух видов, непрерывные и дискретные.

·      Непрерывные сигналы могут принимать бесконечное множество значений на некотором непрерывном промежутке.

·      Дискретные сигналы могут принимать конечное число значений.

·      Есть две формы представления информации: знаковая и образная.

·      В знаковой форме информация записывается на естественном или формальном языке и состоит из дискретных сигналов, представленных знаками.

·      В образной форме информация представляет собой изображение или звук и состоит из непрерывных сигналов.

Вопросы:

·      Дискретизация и её назначение.

·      Двоичное кодирование информации и его принципы.

В повседневной жизни мы часто сталкиваемся с ситуациями, когда необходимо изменить форму представления информации. Перевести информацию из знаковой формы представления в образную и наоборот. Например, когда мы читаем текст вслух или когда музыкант играет музыку по нотам – это перевод информации из знаковой формы в образную, то есть представление её в виде непрерывных звуковых сигналов. Когда мы записываем под диктовку текст или когда при помощи слов или условных обозначений мы описываем предмет на листе бумаги, мы переводим информацию из образной формы в знаковую. То есть мы выражаем её с помощью дискретных сигналов.

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

Рассмотрим одно из многих практических применений дискретизации информации. Допустим у нас есть график изменения температуры на улице одного из городов в течение месяца. Мы можем преобразовать данные, которые представлены в графике, в таблицу. Для этого в таблицу будем вносить данные об измерении температуры на каждый 5 день. Как видим, полученная таблица не даёт нам полного представления об изменении температуры в течение месяца. Так, например, в таблице не указана минимальная температура, которая была зафиксирована на 27 день измерений, а также максимальная температура, которая была зафиксирована на 18 день. Однако мы можем уточнить данные, которые содержатся в таблице, если мы будем записывать в неё результаты измерений каждого дня или каждого часа. Таким образом мы преобразовали непрерывную информацию, представленную в виде кривой изменения температуры в дискретную форму, то есть содержимое таблицы измерений, хоть и с потерей точности.

Непрерывная информация

Дискретная информация

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

У каждого языка есть свой алфавит. Так называется конечный набор символов, которые отличаются друг от друга и используются для представления информации на этом языке. Алфавит любого языка характеризуется своей мощностью, или количеством символов, которые в него входят. Так мощность алфавита русских букв – 33 символа, мощность алфавита английских букв – 28 символов. Согласно книге рекордов Гиннеса, алфавит с самой высокой мощностью среди естественных языков – это алфавит кхмерских букв, он содержит 72 символа, а алфавит с самой малой мощностью – у языка Ротокас, которым пользуются жители острова Бугенвиль. Алфавит букв этого языка содержит всего 11 символов.

Алфавит, мощность которого составляет два символа, называется двоичным алфавитом. Давайте подумаем, какие символы может содержать такой алфавит. Это могут быть символы «А» и «Б», единица и ноль, истина и ложь, плюс и минус, да и нет. Такой алфавит легко реализовать технически. В качестве одного символа можно представить наличие какого-нибудь сигнала. Это может быть электрический сигнал, световой или любой другой. В качестве второго символа такого алфавита можно представить отсутствие этого сигнала.

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

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

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

Схема двоичного кодирования

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

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

Для того, чтобы найти вторую цепочку на первом узле выберем левую ветвь схемы, то есть первым символом цепочки будет ноль. А на втором узле выберем правую ветвь, то есть вторым символом цепочки будет единица.

Таким же образом найдём третью цепочку. Она будет состоять из символов один и ноль. А последняя оставшаяся цепочка будет состоять из двух единиц.

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

Таким же образом найдём все возможные цепочки, состоящие из 3 символов двоичного алфавита. Для этого нам нужна 3-уровневая схема.

Это будут цепочки: 000, 001, 010, 011, 100, 101, 110, 111.

У нас получилось 8 цепочек. То есть при помощи двоичного кода длиной 3 символа мы можем закодировать алфавит из 8 символов. Это в 2 раза больше, чем для двоичного кода длиной 2 символа. 

Так же мы можем найти что с помощью 4-значного двоичного кода можно закодировать 16 символов, при помощи 5-значного – 32, при помощи 6-значного – 64 и т. д… То есть при увеличении длины двоичного кода на единицу, становится возможным кодирование в 2 раза большего числа символов. Обратим внимание что с помощью 1-значного двоичного кода можно закодировать 2 символа. При помощи 2-значного – 2 умножить на 2 символа, записывается два во второй степени 2². При помощи 3-значного – 2 × 2 × 2, то есть 2³ степени символов. При помощи 4-значного – 2⁴ символов и так далее… И для того, чтобы найти, сколько символов можно закодировать с помощью N-разрядного двоичного кода, достаточно перемножить цепочку из N двоек или 2^N.

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

Условие этой задачи можно выразить с помощью уравнения: M = 64 = 2^X. X равно разрядности двоичного кода, который потребуется для кодирования алфавита. Мы можем рассчитать, что для того, чтобы получить 64, нужно перемножить последовательность из 6 двоек, то 2⁶. X = 6. Мы можем дать ответ: для кодирования алфавита государства потребуется шестиразрядный двоичный код.

Важно запомнить:

·      Дискретизацией называется процесс преобразования информации из непрерывной формы в дискретную.

·      Для дискретизации информации нужно представить её в виде символов какого-нибудь языка.

·      Алфавит языка – это набор всех различных символов, которые используются для представления информации на этом языке.

·      Мощность алфавита – это число символов, которые в него входят.

·      Двоичным называется алфавит, который состоит из двух символов.

·      Двоичное кодирование – это представление информации с помощью двоичного алфавита.