Что такое посимвольное кодирование

2. Двоично-кодированные системы счисления. Посимвольное и групповое кодирование

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

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

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

При этом возможны два подхода к кодированию:

При посимвольном кодировании используются так называемые двоично-кодированные системы счисления. В таких системах каждому символу из алфавита сопоставляется оригинальная (неповторяющаяся) кодовая комбинация символов двоичного алфавита. Минимальная длина такой кодовой комбинации определяется соотношением. Для так называемого «естественного» посимвольного кодирования приот 3 до 15 можно использовать табл. П.1.1. Однако возможно и произвольное посимвольное кодирование, задаваемое табличным способом.

Пример 2.1 Рассмотрим двоично-кодированную троичную систему счисления (=3). В соответствии с формулой дляпри кодировании символов троичного алфавита достаточно двух двоичных разрядов. Соответствие символов троичного алфавита и двоичных кодовых комбинаций приведено в табл. П.2.1

Символы троичного алфавита

“Естественное” двоичное кодирование

Произвольное двоичное кодирование

Тогда троичное число 122,10012₃ в «естественном» двоично-кодированном представлении будет иметь вид 011010,0100000110, а при произвольном – 111010,1101011110. После отбрасывания незначащих нулей получим 11010,010000011 и 111010,110101111 соответственно.

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

Разбиение на k — разрядные группы выполняется влево и вправо от запятой. При необходимости исходное число можно дополнить незначащими нулями для получения полных k — разрядных групп.

Пример 2.2 Рассмотрим групповое кодирование для иk = 2. Максимальное целое десятичное число, которое можно представить двумя троичными разрядами, равно S k -1=3 2 -1=8. При этом для представления десятичных чисел от 0 до 8 используется 9 двухразрядных троичных чисел из множества <00,01,02,10,11,12,20,21,22>. Следовательно, укрупненное основание в этом случае равно S k =3 2 =9. В соответствии с формулой для минимальная длина двоичной комбинации, необходимой для укрупненного основания, равна 4. Соответствие двухразрядных троичных чисел и четырехразрядных двоичных кодовых комбинаций приведено в табл. П.2.2.

троичная группа ()

Теория кодирования. Кодирование источника. Посимвольное кодирование

Теория кодирования изучает свойства различных кодов и их применимость в конкретных задачах.

В рамках теории кодирования, кодом называется некое правило (алгоритм), которое однозначно ставит неким словам над исходным алфавитом некие новые кодовые слова, возможно над другим, целевым, алфавитом.

Код Пусть $S$ и $T$ – конечные множества, называемые соответственно исходным и целевым алфавитами. Код $C: S^* \to T^*$ есть всюду определённая функция, отображающая элементы $S^*$ – слова (последовательностей символов) над исходным алфавитом – на элементы множества $T^*$ – слова над целевым алфавитом.

В соответствии с исследуемыми задачами, выделяют четыре различных направления в теории кодирования:

Кодирование источника (сжатие данных)
Кодирование канала (обнаружение и исправление ошибок)
Криптографическое кодирование
Физическое кодирование (модуляция)

Сжатие данных

Сжатие данных в общем случае – это представление информации в меньшем информационном объёме, чем исходные данные. Выделяют сжатие данных без потерь (lossless) и сжатие данных с потерями (lossy).

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

Модель сжатия без потерь:

В качестве меры “успешности” сжатия без потерь вводится коэффициент сжатия: \[r = \frac,\] где $I_S$ – информационный объем данных источника, $I_C$ – информационный объём кодированных данных.

В случае посимвольного кодирования, для сообщения длиной $n$ , $I_S = n\log |A|,$ где $A$ – алфавит источника.

Модель сжатия с потерями:

В модели сжатия с потерями перед кодером добавляется квантователь, задачей которого является понижение размерности алфавита источника таким образом, чтобы в итоге $X^*$ являлся “достаточно близким” образом исходного сообщения $X$ . Например, в простейшем случае, квантователь может округлять значения. Среднеквадратичное отличие принятых сообщений $X^*$ и отправленных сообщений $X$ называется искажением: \[D = \frac<1> \sum_^ (x_i — x^*_i)^2.\]

Кроме требования однозначности, как правило, требуется так же обеспечить возможность каким-то образом разделять кодовые слова, соответствующие различным исходным сообщениям. Для достижения этого могут использоваться следующие подходы:

Использование разделительных кодовых слов – специальных кодовых слов, не соответствующих ни одному символу исходного алфавита
Использование кодов одинаковой длины (равномерное кодирование)
Использование префиксных кодов

Определение энтропии так же даёт нам некоторые указания касательно свойств оптимального кода, исходя из того, что энтропия кодированного сигнала должна быть максимальна (т.е. количество информации на символ кода – максимально):

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

Наиболее экономным для большинства применений оказывается использование префиксных кодов.

Предел оптимального кодирования без потерь нам даёт теорема Шеннона о кодировании источника: средняя (в смысле теории вероятностей) длина кодового слова не может быть меньше энтропии источника.

Основные методы посимвольного кодирования

Посимвольное кодирование, или кодирование без памяти, является простейшим методом кодирования.

Посимвольный код Пусть $S$ и $T$ – конечные множества, называемые соответственно исходным и целевым алфавитами. Код $C: S \to T^*$ есть всюду определённая функция, отображающая элементы $S$ – символы исходного алфавита – на элементы $T^*$ – слова над целевым алфавитом. Расширение посимвольного кода Обобщение посимвольного кода $C: S \to T^*$ на код $C^*: S^* \to T^*$ , совершаемое конкатенацией посимвольных кодов. Префиксный код Такой код, в котором ни одно кодовое слово меньшей длины не является префиксом никакого кодового слова большей длины.

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

Однозначно декодируемый посимвольный код Посимвольный код $C: S \to T^*$ является однозначно декодируемым, если в расширенном коде $C^*$ , любые две различных исходных строки $\mathbf, \mathbf \in S^*,$ $\mathbf\neq \mathbf$ , имеют различные коды: $C^*(\mathbf) \neq C^*(\mathbf)$

Мы так же хотим, чтобы средний (ожидаемый) информационный объем кода был минимальный.

Ожидаемая длина кодового слова (средняя длина кода) Математическое ожидание длины кодового слова из кода $C$ над источником $X$ обозначается $L(C, X)$ и называется ожидаемой (средней) длиной кодового слова: \[L(C,X) = \sum_ P(x) |C(x)|,\] где $|C(x)|$ – длина кодового слова $C(x).$

Необходимое и достаточное условие существования однозначно декодируемых префиксных кодов (и вообще однозначно декодируемых кодов переменной длины) устанавливается неравенством Крафта-МакМиллана:

Теорема (неравенство Крафта-МакМиллана) Пусть каждый символ исходного алфавита $S=\$ кодируется однозначно декодируемым кодом с кодовыми словами над алфавитом размерности $r,$ имеющими длины соответственно $\.$ Тогда: \[\sum_^ r^ <-l_i>\le 1.\] Обратно, для последовательности чисел $\,$ удовлетворяющей данному неравенству, существует однозначно декодируемый код. Доказательство (прямая теорема)

Пусть $S = \sum_i r^<-l_i>.$ Рассмотрим число \[S^N = \sum_\ldots\sum_ r^<-(l_+\ldots+l_)>,\] где $N\in\mathbb N.$

Число $(l_+\ldots+l_)$ соответствует длине кода для строки длины $N$ $\mathbf = a_\ldots a_.$ В сумме выше, для каждой возможной строки длины $N$ имеется ровно один такой член. Введём дискретную функцию $g_N(l),$ значением которой является количество строк $\mathbf$ длины $N$ , коды которых имеют длину $l$ . Тогда, определяя \(l_ = \underset i \min

l_i,\) \(l_ = \underset i \max

l_i,\) получаем: \[S^N = \sum_>^>r^ <-l>g_N(l).\] Теперь положим, что код $C$ является однозначно декодируемым, т.е. $\forall \mathbf \neq \mathbf: C^*(\mathbf) \neq C^*(\mathbf).$ Рассмотрим $\mathbf$ , имеющий длину кода $l$ . Всего существует $r^l$ различных потенциально возможных кодов длины $l$ , следовательно, с необходимостью следует, что $g_N(l) \leq r^l$ . Тогда, \[S^N = \sum_>^>r^ <-l>g_N(l) \leq \sum_>^> 1 = N(l_-l_).\] Отметим, что мы не накладывали ограничений на $N$ , т.е. \[\forall N\in \mathbb N: S^N \leq N(l_-l_).\] Это возможно только, когда $S\le 1$ . Действительно, если $S>1$ , то $S^N$ является экспоненциальной функцией $N$ , в то время как правая часть $N(l_-l_)$ является линейной функцией $N$ . При $S>1$ , неизбежно $\exists N_0 \in \mathbb N : \forall N > N_0, S^N > N(l_-l_).$ $\not \Delta$

Доказательство (обратная теорема) Пусть $l_1 \le \ldots \le l_n$ удовлетворяют неравенству Крафта. Тогда, можно составить однозначный префиксный код, выбирая на каждом шаге $i=\<1,\ldots, n\>$ код длины $l_i$ и исключая все коды длин $l \ge l_i$ с префиксами, совпадающими с этим кодом. На каждом шаге таким образом исключается $r^$ из всех возможных кодовых слов. Тогда всего при построении кода исключается $\sum_^n r^$ кодовых слов. Ясно, что такой код можно построить, если число исключённых кодовых слов не превышает число всех возможных кодовых слов $r^$ . Из неравенства Крафта, \[\sum_^ r^ <-l_i>\le 1,\] \[\sum_^ r^ \le r^,\] то есть это условие выполняется и код можно построить. Полный префиксный код Если префиксный код удовлетворяет неравенству Крафта равенством, т.е. \[\sum_^ r^ <-l_i>= 1,\] такой код называется полным.

Теорема Шеннона о кодировании источника ограничивает снизу максимально достижимое сжатие энтропией источника. Сохраняется ли это ограничение при посимвольном кодировании? Вообще говоря, ответ может быть неочевиден. Поэтому, найдём нижнюю границу ожидаемой длины кода $L(C, X).$ Сперва докажем неравенство Гиббса.

Расстояние Кульбака-Лейблера неотрицательно: \[D_(P||Q) = \sum_ P(x) \log\left(\frac\right) \ge 0,\] где $P,Q$ – распределения вероятностей случайной дискретной величины $X$ .

Рассмотрим $f(u) = -\log u$ и $u(x) = \frac$ . $f(u)$ – выпуклая вниз функция, т.к. $f»(u) = u^ <-2>> 0$ . Тогда из нер-ства Йенсена, \[\begin \sum_ P(x) f(u(x)) & \ge f(\sum_ P(x) u(x)) \\& = -\log <\sum_Q(x)> \\& = 0. \end\] $\not \Delta$

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

Пусть $X=\$ , $P(x_i) = p_i$ , $|C(x_i)| = l_i$ , $i=1, \ldots, n$ . Тогда, \[L(C,X) = \sum_ p_i l_i.\]

Пусть $q_i = \frac<2^<-l_i>>$ , где $z = \sum_i 2^<-l_i>$ . Тогда $l_i = — \log_2 q_i — \log_2 z$ , тогда \[\begin L(C,X) & = -\sum_ p_i \log_2 q_i — \log_2 z & (\sum_i p_i = 1) \\& \ge -\sum_ p_i \log_2 p_i — \log_2 z & \text <(из н-ва Гиббса)>\\& \ge -\sum_ p_i \log_2 p_i — \log_2 1 & \text <(из н-ва Крафта)>\\& = H(X). \end\]

Равенство соответственно достигается в случае $p_i=q_i$ и $z=1$ , то есть, если $l_i = — \log_2 p_i,$ т.е. длина двоичного кодового слова $i$ -го символа равна количеству собственной информации этого символа, и код является полным.

Это важный результат, поэтому повторимся.

Оптимальные длины кодовых слов посимвольного префиксного кода Ожидаемая длина посимвольного префиксного кода достигает минимума и равняется энтропии источника $H(X)$ тогда и только тогда, когда длины кодовых слов соответствующих символов равны количеству собственной информации соответствующих символов \[|C(x)| = -\log_2 P(x)\]

Верно так же и обратное: любой выбор длин кодовых слов неявно определяет оптимальный источник.

Оптимальный источник для посимвольного кодера $C$

Определяется распределением вероятностей \[P(x) = \frac<2^<-|C(x)|>> <\sum_2^<-|C(x')|>>.\]

Мы установили нижнюю границу. Но насколько близко к ней можно подойти? Оказывается, в пределах одного бита.

Для источника случайной переменной $x$ из ансамбля $X$ существует префиксный код $C$ , удовлетворяющий неравенствам \[H(X) \le L(C,X) < H(X)+1\]

$\Delta$ : Первое неравенство $L(C,X) \ge H(X)$ уже доказано выше.

Выберем длины кодовых слов, округлив теоретически оптимальные длины до ближайшего целого вверх: \[l(x) = \left\lceil -log_2 P(x) \right\rceil.\]

Покажем, что префиксный код с такими длинами кодовых слов существует (удовлетворяет нер-ству Крафта): \[\sum_ 2^<-l(x)>=\sum_ 2^<-\left\lceil -log_2 P(x) \right\rceil>\le \sum_ 2^ = 1.\]

Тогда, \[\begin L(C,X) & = \sum_ P(x) \left\lceil -log_2 P(x) \right\rceil \\& < \sum_ P(x) \left( -log_2 P(x) + 1 \right) \\& = H(x)+1 \end\]

Отметим, что если для кодирования источника с вероятностями $p_i$ используется полный префиксный код с длинами кодов $l_i$ , то ожидаемая длина кода будет отличаться от энтропии на расстояние Кульбака-Лейблера от оптимального источника данного кода с вероятностями $q_i = 2^<-l_i>$ : \[\begin L(C,X) — H(X) & = \sum_i p_i l_i + \sum_i p_i \log_2 p_i \\ & = -\sum_i p_i \log_2 q_i + \sum_i p_i \log_2 p_i \\ & = \sum_i p_i \log_2 \frac \\ & = D_(p||q) \end\]

Алгоритм Хаффмана

Один из способов построить оптимальный посимвольный код – алгоритм Хаффмана.

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

Отождествим эти символы.

Если в рассмотрении более 1 символа, перейдём к шагу 1.

Более подробное описание доступно здесь

Поскольку каждая итерация уменьшает число рассматриваемых символов на 1, алгоритм завершится за $|X|-1$ итераций, где $|X|$ – размер алфавита источника $X$ .

Код, составленный по алгоритму Хаффмана, оптимален.

Доказательство индукцией по размеру алфавита $|X|$ .

База. $|X| = 2$ , ожидаемая длина кода Хаффмана $L=1$ . Код очевидно оптимален.

Пусть алгоритм Хаффмана даёт оптимальный код для алфавита размера $|X|=n-1$ .

Тогда для алфавита $A_X=\$ , без ограничения общности, положим, что $P(x_i) \ge P(x_) \ge P(x_n),$ $i\in \<1,\ldots, n-2\>$ .

В процессе работы алгоритма, будет так же построен код для источника $X’$ с алфавитом $A_=\, x’\>,$ причём $P(x’) = P(x_)+P(x_n)$ . Пусть средняя длина кодового слова для источника $X’$ по алгоритму Хаффмана $L’$ . По предположению индукции, этот код оптимален.

Пусть средняя длина кодового слова для источника $X$ по алгоритму Хаффмана $L$ . Допустим, такой код не оптимален. Тогда существует другой код со средней длиной кодового слова $\widetilde L < L$ . Мы можем построить полный префиксный код, такой, что коды для $x_$ и $x_n$ отличаются только последним битом, а его средняя длина $\hat L \le \widetilde L$ .

Из нового префиксного кода с длиной $\hat L$ мы можем построить код для $X’$ , сохранив коды для $x_1,\ldots,x_$ и назначив общий префикс кодов $x_$ и $x_n$ в качестве кода $x’$ . Пусть его средняя длина $\hat L’$

Тогда, поскольку $X’$ отличается от $X$ тем, что два символа из $X$ в нём отождествляются, а отождествлённый символ в наших кодах имеет кодовое слово на 1 бит короче, имеем \[L = L’ + P(x’),\] \[\hat L = \hat L’ + P(x’).\]

Поскольку по предположению индукции $L’$ является длиной оптимального кода, $\hat L’ \ge L’$ , но тогда $\hat L \ge L$ , что противоречит $\hat L \le \widetilde L < L$ . Следовательно, код Хаффмана для алфавита размера $|X|=n$ оптимален.

По индукции, код Хаффмана для любого алфавита размерности $|X|\ge 2$ оптимален.

Другие алгоритмы посимвольного кодирования

Код Шеннона

Все символы алфавита источника упорядочиваются по убыванию вероятности. Каждому символу ставится в соответствие “кумулятивная вероятность” $q_i = \sum_^ p_j$ . Кодовым словом для $i$ -го символа являются $l_i = \left\lceil -log_2 p_i \right\rceil$ разрядов дробной части из двоичного представления $q_i$ .

Код Шеннона использовался Шенноном при доказательстве теоремы о кодировании источника, однако он не является оптимальным, и никогда не лучше (но иногда эквивалентен) коду Шеннона-Фано.

Код Шеннона-Фано

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

Код Шеннона-Фано даёт оценку средней длины $L(C,X) \le H(X)+2$ . Понятно, что он не является оптимальным.

Следует отметить, что подход похож на подход Хаффмана, однако алгоритм Хаффмана строит дерево “снизу вверх”, от листьев, в то время как алгоритм Шеннона-Фано строит дерево “сверху вниз”, от корня.

Код Элиаса (Шеннона-Фано-Элиаса)

Так же известен как код Гильберта-Мура 1

Каждому символу ставится в соответствие число \[F_i = \frac <2>+ \sum_^ p_j.\]

Кодовым словом $i$ -го символа выбираются первые $l_i = \left\lceil -\log_2 p_i \right\rceil + 1$ дробных разрядов двоичного представления числа $F_i$ .

Код Элиаса даёт оценку средней длины $L(C,X) \le H(X)+2$ .

Gilbert E. N., Moore E. F. Variable‐Length Binary Encodings //Bell System Technical Journal. – 1959. – Т. 38. – №. 4. – С. 933-967.↩︎

лекции по ОТИ. Введение. Понятие информации. Информация и данные

Единственный в мире Музей Смайликов

Самая яркая достопримечательность Крыма
Скачать 376.35 Kb.

2. Эффективное посимвольное кодирование для сжатия данных.

идея такого кодирования базируется на том, чтобы использовать для часто встречающихся символов более короткие кодовые цепочки, а для редких — более длинные. В результате средняя длина кода будет меньше, чем при равномерном кодировании;

согласно теореме Шеннона, наилучшее кодирование позволяет сократить l_ср. до величены энтропии Н, подсчитанной для данного набора символов;

неравномерное кодирование позволяет автоматически устранить избыточность, связанную с тем, что количество символов в алфавите может быть не кратно степени двойки (так, например, чтобы закодировать одинаковым числом разрядов 5 разновидностей символов потребуется 3 бита, так же как и для 8 символов).

Наибольшее распространение получил способ построения эффективного кода предположенный Хаффменом. Рассмотрим его на примере. Пусть задан алфавит из 5 разновидностей символов Z₁ – Z_{5, и} их вероятности. В таблице 5.1 наряду с этими исходными данными приведены так же результаты кодирования по Хаффмену: кодовые цепочки K_i их длинны l_i. Процедуру построения кода иллюстрирует таблица и рисунок 1

На первом этапе символы упорядочивают по убыванию вероятностей, а затем выполняют несколько шагов «объединения», на каждом из которых суммируются вероятности наиболее редко встречающихся символов и столбец вероятностей пересортировывается .

Пример кода Хаффмена

На втором этапе строится «дерево кода», ветви которого отображают в обратном порядке процесс «объединения вероятностей». При построении дерева принимается правило соответствия большей вероятности одному из направлений ветви (например «левому») и определенному значению бита кода (например, «1») . Цепочки битов от «корня» до конца каждой ветви соответствуют кодам исходных символов (табл.5.1 – 5.2).
Таблица 2 Объединение вероятностей символов

Z_i P_i Шаги объединения K_i

1 2 3 4

Z₁
Z₂
Z₃
Z₄
Z₅ 0,35
0,25
0,17
0,15
0,08 0,35
0,25
0,23
0,17 0,40
0,35
0,25 0,60
0,40 1,00 11
10
00
011
010

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

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

В целом код Хаффмена проигрывает по сравнению с «цепочечными» кодами и его редко используют самостоятельно, однако он часто фигурирует как элемент более сложных алгоритмов сжатия.

3 Сжатие информации с учетом цепочек символов по Лемпелю-Зиву.

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

Наиболее удачным алгоритмом сжатия, основанным на таком подходе является алгоритм Лемпеля-Зива, который в разных модификациях используется, в частности, в большинстве программ-архиваторов. Основная идея алгоритма состоит в том, что цепочки символов, уже встреченные ранее кодируются ссылкой на их «координаты» (номер первого символа и длину) в «словаре», где находится уже обработанная часть сообщения.

Сжимаемое сообщение постепенно «вдвигается» в буфер источника. Программа- кодер выделяет в буфере блок (цепочку) символов первоначально максимальной длины (обычно порядка 16 символов) и пытается найти совпадающую цепочку в словаре источника. Если это не удается, кодер повторяет поиск для более короткого «урезанного» варианта цепочки. Когда эта цепочка обнаруживается в словаре, в канал передаются ее координаты. Если же поиск не дал результата даже для самого короткого варианта цепочки из двух символов, каждый из них передается по каналу самостоятельно.

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

Уточним дополнительно некоторые моменты:

коды координат цепочки и коды отдельных символов различаются битовыми признаками (например, в первом случае – 1, во втором –0) ;

поскольку цепочки находятся чаще в начале словаря, и чаще бывают короткими, дополнительный выигрыш получают за счет статистического кодирования (по Хаффмену) их «адресов» и «длин»;

«канал» — понятие применимое и к реальному каналу передачи данных, и к файлу, куда данные записываются для хранения. В последнем случае декодер «отрабатывает» при разворачивании сжатого файла;

при ограниченной длине словаря (обычно от 4 до 16 кбайт) новые поступающие символы и цепочки «вытесняют» прежние (текст как бы «вдвигается» в словарь). Разумеется, вначале, когда словарь не заполнен, эффективность сжатия невысока. Рост объема словаря позволяет повысить степень сжатия, но значительно увеличивается трудоемкость поиска цепочек.

Добавим, что алгоритм Лемпеля-Зива используется в большинстве популярных программ-архиваторов (в том числе, например, в zip, rar, arj и их windows – версиях).

Различие скорости и эффективности кодирование-декодирование определяются в основном особенностями программной реализации.

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

4 Сжатие изображений по блочному алгоритму JPEG.

Как известно, все множество цветовых оттенков может быть задано различными пропорциями яркости трех цветовых составляющих, — в частности, красного (Red – R), зеленого (Green – G) и голубого (Blue – B). В памяти компьютера изображение чаще всего представляется как матрица (растр) точек — пикселей.

(Наряду с таким «растровым» представлением существует и так называемое «векторное», когда элементы изображения — кривые – описываются математическими уравнениями. К «векторному» описанию изображения применимы способы сжатия данных без потерь. Здесь мы будем говорить о методах, применяемых по отношению к растровым изображениям).

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

Особенности человеческого зрения заключаются, в частности, в том, что глаз слабо различает мелкие детали изображения и более чувствителен к изменениям яркости, чем к цветовым переходам. Эти особенности использует популярный алгоритм сжатия с потерями информации JPEG. В настоящее время широко используется «блочная» версия алгоритма, в которой все изображение разбивается на блоки 8х8 и в дальнейшем эти блоки «огрубляются» таким образом, чтобы код, который их описывает, стал как можно короче (исходное описание каждого такого блока требует 8х8х3=192 байта).

Анализ методов кодирования данных (Алфавит кодирования)

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

Автоматизированная система обработки информации (АСОИ) представляет собой совокупность информации, экономико-математических методов и моделей, технических, программных, технологических средств и штата специалистов, предназначенную для обработки информации и принятия управленческих решений

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

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

Целью исследования курсовой работы является изучение методов кодирования данных.

В связи с поставленной целью курсовой работы, были определенный следующие задачи:

Рассмотреть основные определения кодирования. Алфавит кодирования;

Изучить способ кодирование информации с помощью систем счисления;

Охарактеризовать способы кодирования текстовой информации;

Выявить способы кодирования целых и действительных чисел;

Рассмотреть кодирование графических данных;

Проследить особенности кодирования звуковой информации.

Объектом исследования курсовой работы является система кодирования данных.

Предметом исследования курсовой работы являются методы и приемы кодирования данных.

Структура курсовой работы. Курсовая работа состоит из введения, двух глав, разделенных на параграфы, заключения и списка литературы.

ГЛАВА 1. СУЩНОСТЬ КОДИРОВАНИЯ ИНФОРМАЦИИ

1.1. Основные определения кодирования. Алфавит кодирования

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

Существует множество понятий и определений «кода». Но мы в своей работе будем опираться на следующее: «Код (code) – это совокупность знаков, символов и правил представления информации».[10, с.40]

В частности можно различать двоичный и троичный код. Алфавит первого ограничен двумя символами (0, 1), а второго – тремя символами (-1, 0, +1). Сигналы, реализующие коды, обладают одной из следующих характеристик:

униполярный код (значения сигнала равны 0, +1, либо 0, -1 );

полярный код (значения сигнала равны +1, -1);

биполярный код (значения сигнала равны 0, +1, -1).

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

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

Последовательным является такой код, в котором знаки следуют один за другим во времени. Параллельным – тот, в котором знаки передаются одновременно, образуя символ. [10, с.41]

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

Естественные языки обладают большой избыточностью для экономии памяти, объем которой ограничен, имеет смысл ликвидировать избыточность текста или уплотнить текст.

Существуют несколько способов уплотнения текста.

1. Переход от естественных обозначений к более компактным. Этот способ применяется для сжатия записи дат, номеров изделий, уличных адресов и т.д. Идея способа показана на примере сжатия записи даты. Обычно мы записываем дату в виде 10. 05. 01. , что требует 6 байтов памяти ЭВМ. Однако ясно, что для представления дня достаточно 5 битов, месяца — 4, года — не более 7, т.е. вся дата может быть записана в 16 битах или в 2-х байтах.

2. Подавление повторяющихся символов. В различных информационных текстах часто встречаются цепочки повторяющихся символов, например пробелы или нули в числовых полях. Если имеется группа повторяющихся символов длиной более 3, то ее длину можно сократить до трех символов. Сжатая таким образом группа повторяющихся символов представляет собой триграф S P N , в котором S – символ повторения; P – признак повторения; N- количество символов повторения, закодированных в триграфе. В других схемах подавления повторяющихся символов используют особенность кодов ДКОИ, КОИ- 7, КОИ-8 , заключающуюся в том, что большинство допустимых в них битовых комбинаций не используется для представления символьных данных.

3. Кодирование часто используемых элементов данных. Этот способ уплотнения данных также основан на употреблении неиспользуемых комбинаций кода ДКОИ. Для кодирования, например, имен людей можно использовать комбинации из двух байтов диграф PN, где P – признак кодирования имени, N – номер имени. Таким образом может быть закодировано 256 имен людей, чего обычно бывает достаточно в информационных системах. Другой способ основан на отыскании в текстах наиболее часто встречающихся сочетании букв и даже слов и замене их на неиспользуемые байты кода ДКОИ.

4. Посимвольное кодирование. Семибитовые и восьмибитовые коды не обеспечивают достаточно компактного кодирования символьной информации. Более пригодными для этой цели являются 5 — битовые коды, например международный телеграфный код МГК-2. Перевод информации в код МГК-2 возможен с помощью программного перекодирования или с использованием специальных элементов на основе больших интегральных схем (БИС). Пропускная способность каналов связи при передаче алфавитно-цифровой информации в коде МГК-2 повышается по сравнению с использованием восьмибитовых кодов почти на 40%.

5. Коды переменной длины. Коды с переменным числом битов на символ позволяют добиться еще более плотной упаковки данных. Метод заключается в том, что часто используемые символы кодируются короткими кодами, а символы с низкой частотой использования — длинными кодами. Идея такого кодирования была впервые высказана Хаффманом, и соответствующий код называется кодом Хаффмана. Использование кодов Хаффмана позволяет достичь сокращения исходного текста почти на 80%.

Использование различных методов уплотнения текстов кроме своего основного назначения – уменьшения информационной избыточности – обеспечивает определенную криптографическую обработку информации. Однако наибольшего эффекта можно достичь при совместном использовании как методов шифрования, так и методов кодирования информации [6, с.95].

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

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

Информация передается в виде сообщений. Дискретная информация записывается с помощью некоторого конечного набора знаков, которые будем называть буквами, не вкладывая в это слово привычного ограниченного значения (типа «русские буквы» или «латинские буквы»). Буква в данном расширенном понимании — любой из знаков, которые некоторым соглашением установлены для общения. Например, при передаче сообщений на русском языке такими знаками будут русские буквы. Вообще, буквой будем называть элемент некоторого конечного множества (набора) отличных друг от друга знаков. Множество знаков, в котором определен их порядок, назовем алфавитом.[18, с.86]

Рассмотрим некоторые примеры алфавитов.

1. Алфавит прописных русских букв:

А Б В Г Д Е Ё Ж З И Й К Л М Н О П Р С Т У Ф Х Ц Ч Ш Щ Ъ Ы Ь Э Ю Я

2. Алфавит Морзе:

3. Алфавит клавиатурных символов ПЭВМ IBM (русифицированная клавиатура):

4. Алфавит знаков правильной шестигранной игральной кости:

5. Алфавит арабских цифр:

6. Алфавит шестнадцатеричных цифр:

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

7. Алфавит двоичных цифр:

Алфавит 7 является одним из примеров, так называемых, «двоичных» алфавитов, т.е. алфавитов, состоящих из двух знаков. Другими примерами являются двоичные алфавиты 8 и 9:

8. Двоичный алфавит «точка», «тире»: . _

9. Двоичный алфавит «плюс», «минус»: + —

10. Алфавит прописных латинских букв:

11. Алфавит римской системы счисления:

12. Алфавит языка блок-схем изображения алгоритмов:

.

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

На рисунке приведена схема, иллюстрирующая процесс передачи сообщения в случае перекодировки, а также воздействия помех[3, с.11].

1.2 Кодирование информации с помощью систем счисления

Для записи информации о количестве объектов используются числа. Числа записываются с использованием особых знаковых систем, которые называются системами счисления. Алфавит систем счисления состоит из символов, которые называются цифрами. Например, в десятичной системе счисления числа записываются с помощью десяти всем хорошо известных цифр: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9.

Система счисления — это знаковая система, в которой числа записываются по определенным правилам с помощью символов некоторого алфавита, называемых цифрами. [7, с.6]

Все системы счисления делятся на две большие группы: позиционные и непозиционные системы счисления.

Римская непозиционная система счисления. Самой распространенной из непозиционных систем счисления является римская. В качестве цифр в ней используются: I (1), V (5), X (10), L (50), С (100), D (500), М (1000).

Значение цифры не зависит от ее положения в числе. Например, в числе XXX (30) цифра X встречается трижды и в каждом случае обозначает одну и ту же величину — число 10, три числа по 10 в сумме дают 30.

Величина числа в римской системе счисления определяется как сумма или разность цифр в числе. Если меньшая цифра стоит слева от большей, то она вычитается, если справа — прибавляется. Например, запись десятичного числа 1998 в римской системе счисления будет выглядеть следующим образом:

MCMXCVIII = 1000 + (1000 — 100) + (100 -10)+5 + 1 + 1 + 1.

Позиционные системы счисления. Первая позиционная система счисления была придумана еще в Древнем Вавилоне, причем вавилонская нумерация была шестидесятеричной, то есть в ней использовалось шестьдесят цифр! Интересно, что до сих пор при измерении времени мы используем основание, равное 60 (в 1 минуте содержится 60 секунд, а в 1 часе — 60 минут).

В XIX веке довольно широкое распространение получила двенадцатеричная система счисления. До сих пор мы часто употребляем дюжину (число 12): в сутках две дюжины часов, круг содержит тридцать дюжин градусов и так далее.

В позиционных системах счисления количественное значение цифры зависит от ее позиции в числе.

Наиболее распространенными в настоящее время позиционными системами счисления являются десятичная, двоичная, восьмеричная и шестнадцатеричная. Каждая позиционная система имеет определенный алфавит цифр и основание.

В позиционных системах счисления основание системы равно количеству цифр (знаков в ее алфавите) и определяет, во сколько раз различаются значения одинаковых цифр, стоящих в соседних позициях числа.

Десятичная система счисления имеет алфавит цифр, который состоит из десяти всем известных, так называемых арабских, цифр, и основание, равное 10, двоичная — две цифры и основание 2, восьмеричная — восемь цифр и основание 8, шестнадцатеричная — шестнадцать цифр (в качестве цифр используются и буквы латинского алфавита) и основание 16.

Таблица 1.1

Позиционные системы счисления

Двоичная система счисления. В двоичной системе счисления основание равно 2, а алфавит состоит из двух цифр (0 и 1). Следовательно, числа в двоичной системе в развернутой форме записываются в виде суммы степеней основания 2 с коэффициентами, в качестве которых выступают цифры 0 или 1. [10, с.47]

Любое неотрицательное число в позиционной системе счисления может быть представлено в виде:

,

где а — основание системы счисления,

хi — разряды (числа от 0 до а-1), их обозначения образуют алфавит системы счисления,

аi — весовые коэффициенты (веса) разрядов,

n — число разрядов целой части числа,

р — число разрядов дробной части числа.

Например, число в десятичной системе счисления 57310=5*102+7*101+3*100

Число в двоичной системе счисления:

Позиционная система счисления — такая, в которой весовые коэффициенты определяются позицией разряда.

В вычислительной технике наиболее распространены: двоичная (binary, BIN), десятичная (decimal, DEC), шестнадцатеричная (hexadecimal, HEX) и непозиционная двоично-десятичная (binary coded decimal, BCD) системы исчисления. В BCD системе вес каждого разряда равен степени 10, как в десятичной системе, а каждая цифра i-го разряда кодируется 4-мя двоичными цифрами. Восьмеричная система счисления (octal, OCT) применяется реже. Следует отметить, что в цифровые устройства используют только двоичную систему счисления, так как построены на основе устройств с двумя состояниями. Другие системы счисления используются человеком только для удобства записи, т.е. для сокращенного (и часто более удобного) представления двоичных чисел.

Формат двоичного числа

Микропроцессоры обрабатывают упорядоченные двоичные наборы. Минимальной единицей информации является один бит (BInary digiT).

Далее следуют – тетрада, или ниббл (4 бита), байт ( byte, 8 бит), двойное слово (DoubleWord 16 бит) или длинное (LongWord 16 бит) и учетверенное (32 бита) слова. Младший бит обычно занимает крайнюю правую позицию, старший — соответственно крайнюю левую, т.е. “старшинство” разрядов убывает слева направо.

Шестнадцатеричное представление двоичных чисел. Для перевода числа из двоичной системы в шестнадцатеричную, его необходимо разбить, начиная справа на тетрады — группы по 4 двоичных цифры — и каждую группу представить шестнадцатеричной цифрой из таблицы. Для обратного перевода каждая HEX цифра заменяется четверкой двоичных, незначащие нули слева иногда (но не всегда) отбрасываются. Нуль обычно не отбрасывается, если старший значащий знак обозначен буквой (см. таблицу).

Двоичные и шестнадцатиричные (HEX) коды целых чисел от 0 до 15

Пример: число 57310 = 10001111012 = 023D16 = 023Dh

Вывод по 1 главе

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

Мы в своей работе будем опираться на следующее определение: «Код (code) – это совокупность знаков, символов и правил представления информации».

Сигналы, реализующие коды, обладают одной из следующих характеристик:

униполярный код (значения сигнала равны 0, +1, либо 0, -1 );

полярный код (значения сигнала равны +1, -1);

биполярный код (значения сигнала равны 0, +1, -1).

Последовательным является такой код, в котором знаки следуют один за другим во времени. Параллельным – тот, в котором знаки передаются одновременно, образуя символ.

Естественные языки обладают большой избыточностью, поэтому для экономии памяти, объем которой ограничен, имеет смысл ликвидировать избыточность текста или уплотнить текст.

Существуют несколько способов уплотнения текста.

Переход от естественных обозначений к более компактным.

Подавление повторяющихся символов.

Кодирование часто используемых элементов данных.

Посимвольное кодирование.

Коды переменной длины.

Информация передается в виде сообщений. Дискретная информация записывается с помощью некоторого конечного набора знаков, которые называются буквами. Буква в данном расширенном понимании — любой из знаков, которые некоторым соглашением установлены для общения.

В канале связи сообщение, составленное из символов (букв) одного алфавита, может преобразовываться в сообщение из символов (букв) другого алфавита. Саму процедуру преобразования сообщения называют перекодировкой.

Для записи информации о количестве объектов используются числа. Числа записываются с использованием особых знаковых систем, которые называются системами счисления.

Все системы счисления делятся на две большие группы: позиционные и непозиционные системы счисления. Самой распространенной из непозиционных систем счисления является римская. Наиболее распространенными в настоящее время позиционными системами счисления являются десятичная, двоичная, восьмеричная и шестнадцатеричная.

Первая позиционная система счисления была придумана еще в Древнем Вавилоне, в XIX веке довольно широкое распространение получила двенадцатеричная система счисления. В настоящее время человечество приняло в использование десятеричную систему счисления.

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

ГЛАВА 2.КОДИРОВАНИЕ ИНФОРМАЦИИ В СИСИТЕМЕ ОБРАБОТКИ ИНФОРМАЦИИ

2.1. Кодирование текстовой информации

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

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

Для хранения кода одного символа может быть выделен один байт. С помощью одного байта можно закодировать 256 различных символов, учитывая, что каждый бит принимает значение 0 или 1, и количество их возможных сочетаний в байте равно 2 8 =256. Этого вполне достаточно для представления текстовой информации, включая прописные и строчные буквы русского и латинского алфавитов, цифры, знаки, псевдографические символы и т. д [19, с.24].

Кодирование заключается в том, что каждому символу ставится в соответствие уникальный десятичный код от 0 до 255 или соответствующий ему двоичный код от 00000000 до 11111111. Таким образом, человек различает символы по их начертанию, а компьютер — по их коду. Важно, что присвоение символу конкретного кода — это вопрос соглашения, которое фиксируется в кодовой таблице.

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

Существует несколько различных стандартов кодирования символов, но первоосновой для всех стал стандарт ASCII (American Standard Code for Information Interchange — американский стандартный код для информационного обмена).

В ASCII закреплены две таблицы кодирования: базовая и расширенная. В базовой таблице определены значения кодов с 0 по 127, а в расширенной — с 128 по 255. В базовой таблице находятся символы латинского алфавита, цифры, знаки арифметических операций и знаки препинания (табл. 1.1). Кроме того, за кодами с 0 по 32 закреплены специальные функции: перевод строки, ввод пробела и т. д. Расширенная таблица содержит символы национальных алфавитов различных стран мира и так называемые символы псевдографики, с помощью которых можно, например, рисовать таблицы [19, с.25].

Рис.2.1 Таблица кодов ASCII (расширенная)

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

Альтернативная кодировка не подошла для ОС Windows. Пришлось передвинуть русские буквы в таблице на место псевдографики, и получили кодировку Windows 1251 (Win-1251). Кодировка символов русского языка, известная как кодировка Windows-1251, была введена «извне» — компанией Microsoft, но, учитывая широкое распространение операционных систем и других продуктов этой компании в России, она глубоко закрепилась и нашла широкое распространение.

Сейчас существует несколько различных кодовых таблиц для русских букв (КОИ-8, СР-1251, СР-866, Мае, ISO), причём тексты, созданные в одной кодировке, могут совершенно неправильно отображаться в другой. Решается такая проблема с помощью специальных программ перевода текста из одной кодировки в другую [4. c.67].

Другая распространённая кодировка носит название КОИ-8 (код обмена информацией, восьмизначный) – её происхождение относится к временам действия Совета Экономической Взаимопомощи государств Восточной Европы. Сегодня кодировка КОИ – 8 имеет широкое распространение в компьютерных сетях на территории России и в российском секторе Интернета.

Международный стандарт, в котором предусмотрена кодировка символов русского языка, носит названия ISO (International Standard Organization – Международный институт стандартизации). На практике данная кодировка используется редко.

Если проанализировать организационные трудности, связанные с созданием единой системы кодирования текстовых данных, то можно прийти к выводу, что они вызваны ограниченным набором кодов (256). Математикам требуется использовать в формулах специальные математические знаки, переводчикам необходимо создавать тексты, где могут встретиться символы из различных алфавитов, экономистам необходимы символы валют ($, F, А). Для решения этой проблемы была разработана универсальная система кодирования текстовой информации — UNICODE. В этой кодировке для каждого символа отводится не один, а два байта, то есть шестнадцать битов. Очевидно, что если, кодировать символы не восьмиразрядными двоичными числами, а числами с большим разрядом то и диапазон возможных значений кодов станет на много больше. Шестнадцать разрядов позволяют обеспечить уникальные коды для 65536 различных символов – этого поля вполне достаточно для размещения в одной таблице символов большинства языков планеты. Этого хватает на латинский алфавит, кириллицу, иврит, африканские и азиатские языки, различные специализированные символы: математические, экономические, технические и многое другое.

Несмотря на тривиальную очевидность такого подхода, простой механический переход на данную систему долгое время сдерживался из-за недостатков ресурсов средств вычислительной техники (в системе кодирования UNICODE все текстовые документы становятся автоматически вдвое длиннее). Но во второй половине 90-х годов технические средства достигли необходимого уровня обеспечения ресурсами, и сегодня мы наблюдаем постепенный перевод документов и программных средств на универсальную систему кодирования UNICODE.

2.2. Кодирование целых и действительных чисел

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

1. Прямой код. Изменение знака производится просто, путем инверсии бита знака. Пусть 00001001 = 9, тогда 10001001 = -9. Если при сложении двух чисел в этом коде знаки совпадают, то трудностей нет. Если знаки различаются необходимо найти наибольшее число, вычесть из него меньшее, а результату присвоить знак наибольшего слагаемого.

2. Обратный код, инверсный или дополнительный «до 1». Изменение знака производится просто — инверсией всех бит: 00001001 = 9, а 11110110 = — 9. Сложение также выполняется просто, т.к. знаковые биты можно складывать. При переносе единицы из левого (старшего) бита, она должна складываться с правым (младшим). Например: 7 + (-5) = 2.

11111010 =-5 (инверсия 00000101 = 5)

Сложение в обратном коде происходит быстрее, т.к. не требуется принятие решения, как в предыдущем случае. Однако суммирование бита переноса требует дополнительных действий. Другим недостатком этого кода является представление нуля двумя способами, т.к. инверсия 0. 00 равна 1. 11 и сумма двух разных по знаку, но равных по значению чисел дает 1. 11. Например: (00001001 = 9) + (11110110 = -9) = 11111111. Кстати, из этого примера понятно, почему код называется дополнительным «до 1». Этих недостатков лишен код, дополнительный до 2.

3. Дополнительный или дополнительный «до 2» код. Число с противоположным знаком находится инверсией исходного и добавлением к результату единицы. Например, найти код числа -9.

00001001 = 9 11110111 =-9

11110110 — инверсия 00001000 — инверсия

11110111 =-9 00001001 = 9

Проблемы двух нулей нет. +0 = 00000000, -0 = 11111111 + 1 = 00000000 (перенос из старшего бита не учитывается).Сложение производится по обычным для неотрицательных чисел правилам.

Из этого примера видно, что в каждом разряде двух равных по модулю чисел складываются две единицы, что и определило название способа. Этот метод применяется наиболее часто, и когда говорят о дополнительном коде, то имеется в виду дополнительный «до 2-х» код.

Примеры однобайтных целых чисел:

Целое двоичное без знака (256 чисел)

Целое двоичное co знаком (от ‑27 до

Числа с плавающей точкой. Вещественные числа хранятся в показательной форме, т.е. в виде двух составляющих: мантиссы и порядка. Различия в способах такого представления чисел заключаются в количестве байтов, отводимых под порядок и мантиссу и небольших отличиях в форме их хранения. Например в четырехбайтовом формате под мантиссу отводится 3 байта и один байт для хранения порядка (КВ — короткий вещественный формат):

Пример одного из вариантов формата:

мантисса (от 2-1 до 1)

Старший разряд старшего байта хранит знак мантиссы, следующий за ним — знак порядка.

В другом варианте знак мантиссы может храниться в старшем разряде байта 2, а сам порядок храниться в «смещенной» форме, в виде числа Е‑127.

Тогда представление числа D: D = ±M * 2^(E-127), где мантисса, Е – смещенный порядок, хранящийся в старшем байте. При этом может быть принято соглашение о неявном присутствии единицы слева от десятичной точки, так что мантисса будет принимать значения от 1 до 2. Соответственно в зависимости от вариаций формата будут слегка отличаться и диапазоны представления чисел. Так, в последнем варианте, где у нормализованной мантиссы первая значащая цифра (единица) мысленно находится слева от запятой, а справа располагаются 23 разряда — 1,xx..xx, Mmax = 1,111..11 = 1 +1/2 +1/4+ 1/8 +. = 2, а Mmin= 1,000..00 = 1 для положительных чисел (SM=0) и -1 и -2 для отрицательных, (SM=1). Порядок числа Emax = 11111110 = 254, а Emin = 00000001 = 1. Теперь можно определить диапазон представления положительных чисел от +Dmax = Mmax * 2(254-127) = 3,4 * 1038 до +Dmin = Mmin * 2(1-127) = 1,17 * 10-38. Точность определяется числом достоверных десятичных цифр. При 23 двоичных разрядах мантиссы 223 примерно равно 107, т.е. достоверными являются только 6-7 значащих десятичных знаков, а не 38. Необходимо отметить, что значения порядка 11111111 и 00000000 по международным стандартам IEEE 754 и IEEE 854 предназначены для кодирования денормализованных чисел, отрицательной и положительной бесконечностей, неопределенности и так называемых «Не-чисел» [7, c.89].

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

Для кодирования целых чисел от 0 до 255 достаточно иметь 8 разрядов двоичного кода (8 бит). 16 бит позволяют закодировать целые числа от 0 до 65535, а 24 – уже более 16,5 миллионов различных значений.

Для кодирования действительных чисел используют 80-разрядное кодирование. При этом число предварительно преобразовывают в нормализованную форму:

3,1414926 = 0,31415926  101

300 000 = 0,3  106

Первая часть числа называется мантиссой, а вторая – характеристикой. Большую часть из 80 бит отводят для хранения мантиссы (вместе со знаком) и некоторое фиксированное количество разрядов отводят для хранения характеристики.

2.3. Кодирование графических данных

Телевизионный способ представления видеоинформации во многом повлиял на формирование принципов представления графической информации в компьютере. Одной из основополагающих идей телевидения является создание изображения на базе системы точек, «обегаемых» по очереди, например, электронным лучом. Подобную систему точек принято называть растром. Посмотрев через лупу на экран телевизора или на фотографию, вы увидите множество точек различных цветов, составляющих растр (см. рис. 1.1).

Рис. 2.2. Растровое изображение под увеличением

Поскольку линейные координаты и индивидуальные свойства каждой точки (яркость) можно выразить с помощью целых чисел, то можно сказать, что растровое кодирование позволяет использовать двоичный код для представления графических данных. Закодировав каждый цвет каким-нибудь числом, можно представить изображение в виде последовательности чисел. Для чёрно-белого изображения на каждую точку будет достаточно одного бита: белый цвет будет обозначаться единицей, а чёрный — нулём, как показано на рисунке 1.2.

Рис. 2.3. Цифровое представление чёрно-белого изображения

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

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

где N есть число цветов, а i — необходимое количество битов информации [19, c. 27].

Например, для кодирования 256 градаций серого потребуется 8 битов, то есть 1 байт. В этом случае 0 будет означать чёрный цвет, 255 — белый, а числа от 1 до 254 — серые цвета различной яркости.

Цветные изображения кодируются сложнее. Часто при кодировании цвета используют трёхбайтовое кодирование, когда каждый байт представляет собой интенсивность одного из трёх базовых цветов — красного, зелёного и синего. Это связано с природной цветовой чувствительностью глаза человека. Практически любой цвет, воспринимаемый глазом, можно получить, смешивая три этих базовых цвета. Например, пурпурный цвет получается от смешения красного и синего, а жёлтый — от смешения красного и зелёного. Меняя пропорции, можно получить различные оттенки. Если смешать все три базовых цвета в одинаковой пропорции, то получится серый цвет. Такой способ кодирования цвета называется RGB (Red, Green, Blue).

Если яркость каждого из базовых цветов кодировать числом от 0 до 255, то потребуется 3 байта (то есть 24 бита) на каждую точку. В этом случае белый цвет будет кодироваться тремя числами (255,255, 255), чёрный — (0, 0, 0). Коды (255, 255, 200) будут обозначать блёкло-жёлтый цвет, а (100, 0, 100) — тёмно-фиолетовый.

Режим представления цветной графики с использованием 24 двоичных разрядов называется полноцветным (True Color).

Каждому из основных цветов можно поставить в соответствие дополнительный цвет, т.е. цвет, дополняющий основной цвет до белого. Нетрудно заметить, что для любого из основных цветов дополнительным будет цвет, образованный суммой пары остальных основных цветов. Соответственно дополнительными цветами являются: голубой (Cyan), пурпурный (Magenta) и жёлтый (Yellow). Принцип декомпозиции произвольного цвета на составляющие компоненты можно применять не только для основных цветов, но и для дополнительных, т.е. любой цвет можно представить в виде суммы голубой, пурпурной и жёлтой составляющей. Такой метод кодирования цвета принят в полиграфии, но в полиграфии используется ещё и четвёртая краска – чёрная (Black). Поэтому данная система кодирования обозначается четырьмя буквами CMYK (чёрный цвет обозначается буквой К, потому, что буква В уже занята синим цветом), и для представления цветной графики в этой системе надо иметь 32 двоичных разряда. Такой режим также называется полноцветным.

Если уменьшить количество двоичных разрядов, используемых для кодирования цвета каждой точки, то можно сократить объём данных, но при этом диапазон кодируемых цветов заметно сокращается. Кодирование цветной графики 16-разрядными двоичными числами называется режимом High Color.

Отдельный элемент графического изображения имеет широко распространённое название — пиксель (от англ. picture element — элемент изображения). Чем гуще сетка пикселей на мониторе, тем лучше качество изображения. Размер графической сетки обычно представляется в форме произведения числа точек в горизонтальной строке на число строк: MxN. Мы можем настраивать режим работы монитора, например: 800×600 или 1024×768 пикселей.

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

С практической точки зрения очень важно понимать, что количество используемых на рисунке цветов существенным образом сказывается на размере графического файла. Для записи чёрно-белого изображения, имеющего 100 точек по вертикали и 100 точек по горизонтали, потребуется 100×100 = 10000 битов (1250 байтов). Изображение такого же размера, но использующее 256 градаций серого цвета, потребует 100 х 100 х 8 = 80 000 битов (10000 байтов). Изображение, использующее 24-битный код, потребует:

100x100x24 = 240 000 битов (30 000 байтов).

2.4. Кодирование звуковой информации

Информация, в том числе графическая и звуковая, может быть представлена в аналоговой или дискретной форме. При аналоговом представлении физическая величина принимает бесконечное множество значений, причем ее значения изменяются непрерывно. При дискретном представлении физическая величина принимает конечное множество значений, причем ее величина изменяется скачкообразно. Примером аналогового представления графической информации может служить, скажем, живописное полотно, цвет которого изменяется непрерывно, а дискретного — изображение, напечатанное с помощью струйного принтера и состоящее из отдельных точек разного цвета. Примером аналогового хранения звуковой информации является виниловая пластинка (звуковая дорожка изменяет свою форму непрерывно), а дискретного — аудиокомпакт-диск (звуковая дорожка которого содержит участки с различной отражающей способностью). Звуковая информация из аналоговой формы в дискретную преобразуется путем дискретизации, т.е. разбиения непрерывного (аналогового) звукового сигнала на отдельные элементы. В процессе дискретизации производится кодирование, т. е. присвоение каждому элементу конкретного значения в форме кода.

Дискретизация — это преобразование непрерывных изображений и звука в набор дискретных значений, каждому из которых присваивается значение его кода.

Как известно из курса физики, звук — это колебания среды, непрерывный сигнал с меняющейся амплитудой (рис. 1.3).

Рис.2.4. Звуковая волна

При кодировании звука этот сигнал надо представить в виде последовательности нулей и единиц. Как, например, это происходит в микрофоне? Через равные промежутки времени, очень часто (десятки тысяч раз в секунду) измеряется амплитуда колебаний. Каждое измерение производится с ограниченной точностью и записывается в двоичном виде. Частота, с которой записывается амплитуда, называется частотой дискретизации [19. c. 29].

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

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

Например, при записи на компакт-диски (CD) используются 16-разрядные значения, а частота дискретизации равна 44 032 Гц. Эти параметры обеспечивают превосходное качество звучания речи и музыки. Для стереозвука отдельно записывают данные для левого и для правого канала.

Приёмы и методы работы со звуковой информацией пришли в вычислительную технику наиболее поздно. К тому же, в отличие от числовых, текстовых и графических данных, у звукозаписей не было столь же длительной и проверенной истории кодирования. В итоге методы кодирования звуковой информации двоичным кодом далеки от стандартизации. Множество отдельных компаний разработали свои корпоративные стандарты, но среди них можно выделить два основных направления [6. c. 115].

1. Метод FM (Frequency Modulation) основан та том, что теоретически любой сложный звук можно разложить на последовательность простейших гармонических сигналов разных частот, каждый из которых представляет собой правильную синусоиду, а, следовательно, может быть описан числовыми параметрами, т.е. кодом. В природе звуковые сигналы имеют непрерывный спектр, т.е. являются аналоговыми. Их разложение в гармонические ряды и представление в виде дискретных цифровых сигналов выполняют специальный устройства – аналогово-цифровые преобразователи (АЦП). Обратное преобразование для воспроизведения звука, закодированного числовым кодом, выполняют цифро-аналоговые преобразователи (ЦАП). При таких преобразованиях неизбежны потери информации, связанные с методом кодирования, поэтому качество звукозаписи обычно получается не вполне удовлетворительным и соответствует качеству звучания простейших электромузыкальных инструментов с окрасом характерным для электронной музыки. В то же время данный метод копирования обеспечивает весьма компактный код, поэтому он нашёл применение ещё в те годы, когда ресурсы средств вычислительной техники были явно недостаточны.

2. Метод таблично волнового (Wave-Table) синтеза лучше соответствует современному уровню развития техники. В заранее подготовленных таблицах хранятся образцы звуков для множества различных музыкальных инструментах. В технике такие образцы называют сэмплами. Числовые коды выражают тип инструмента, номер его модели, высоту тона, продолжительность и интенсивность звука, динамику его изменения, некоторые параметры среды, в которой происходит звучание, а также прочие параметры, характеризующие особенности звучания. Поскольку в качестве образцов исполняются реальные звуки, то его качество получается очень высоким и приближается к качеству звучания реальных музыкальных инструментов.

Вывод по 2 главе

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

Кодирование текстовой информации заключается в том, что каждому символу ставится в соответствие уникальный десятичный код от 0 до 255 или соответствующий ему двоичный код от 00000000 до 11111111. Сейчас существует несколько различных кодовых таблиц для символов (КОИ-8, СР-1251, СР-866, Мае, ISO, Win-1251, СР866 (DOS)), причём тексты, созданные в одной кодировке, могут совершенно неправильно отображаться в другой. Решается такая проблема с помощью специальных программ перевода текста из одной кодировки в другую. Но сегодня мы наблюдаем постепенный перевод документов и программных средств на универсальную систему кодирования UNICODE.

Основой графического изображения является системы точек, которую принято называть растром. Отдельный элемент графического изображения имеет широко распространённое название — пиксель (от англ. picture element — элемент изображения). Чем гуще сетка пикселей на мониторе, тем лучше качество изображения. Поскольку линейные координаты и индивидуальные свойства каждой точки (яркость) можно выразить с помощью целых чисел, то можно сказать, что растровое кодирование позволяет использовать двоичный код для представления графических данных. Закодировав каждый цвет каким-нибудь числом, можно представить изображение в виде последовательности чисел. Кодирование цветов отдельных пикселей аналогично кодированию символов текста. Таблица нумерации цветов есть своеобразный алфавит, пользуясь которым, компьютер записывает графическую информацию. В итоге, как и в случае с текстом, получается последовательность целых чисел, которая стандартным образом сохраняется в памяти.

Звуковая информация для представления в двоичном виде из аналоговой формы в дискретную преобразуется путем дискретизации, т.е. разбиения непрерывного (аналогового) звукового сигнала на отдельные элементы. В процессе дискретизации производится кодирование, т. е. присвоение каждому элементу конкретного значения в форме кода. При кодировании звука этот сигнал представляется в виде последовательности нулей и единиц. Приёмы и методы работы со звуковой информацией пришли в вычислительную технику наиболее поздно. В итоге методы кодирования звуковой информации двоичным кодом далеки от стандартизации. Множество отдельных компаний разработали свои корпоративные стандарты, но среди них можно выделить два основных направления.

ЗАКЛЮЧЕНИЕ

В ходе выполнения курсовой работы нами были решены следующие задачи:

Рассмотрены основные определения кодирования. Алфавит кодирования;

Изучены способ кодирование информации с помощью систем счисления;

Охарактеризованы способы кодирования текстовой информации;

Выявлены способы кодирования целых и действительных чисел;

Рассмотрены методы кодирование графических данных;

Прослежены особенности кодирования звуковой информации.

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

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

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

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

СПИСОК ИСПОЬЗУЕМОЙ ЛИТЕРАТУРЫ

Баричев С. В. Введение в криптографию. Электронный сборник.- М.: Вече1998. -244c

Ведеев Д. А. Защита данных в компьютерных сетях. Открытые системы.- М.: Дрофа 1995, №3.-180с

Горбоконенко В.Д., Шикина В.Е. Кодирование информации: Методические указания / сост. Ульяновск: УлГТУ, 2006. – 56 с.

Ефремова О., Морозов В., Угринович Н. Курс компьютерной технологии с основами информатики. Учебное пособие для старших классов. – М.: АСТ; ABF, 2000

Зегжда П. Теория и практика. Обеспечение информационной безопасности. – М: Альфа 1996.-173с

Келим Ю.М. Вычислительная техника: Учеб. пособие для студ. сред. проф. образования / Юрий Михайлович Келим. – М.: Издательский центр «Академия», 2005. – 384 с.

Кутугина Е.С. Арифметические и логические основы построения компьютера: Учеб. Пособие. – Изд. 3-е, перераб. и доп. – Томск, 2007. – 104 с.

Левин В.К. Защита информации в информационно-вычислительных системах и сетях // Программирование.- СПБ.: Питер 1994. — N5.-160с

Леонтьев В.П. ПК: универсальный справочник пользователя.- М: Айрис 2000. -165с

Максимов Н.В., Партыка Т.Л., Попов И.И. Архитектура ЭВМ и вычислительных систем: Учебник. – М.:ФОРУМ: ИНФРА-М, 2006. – 512 с. ил. (Профессиональное образование).

Правовая информатика и управление в сфере предпринимательства. Учебное пособие. – М.: Юристъ 1998. – 432с

Рожнова В.С.. Автоматизированные системы обработки учетно-аналитической информации [Текст] / под ред.– М.: Финансы и статистика, 2002. – 418с.

Романец Ю. В., Тимофеев П.А., Шаньгин В.Ф. Защита информации в компьютерных системах и сетях / Под ред.В.Ф. Шаньгина.-2-е изд., перераб. и доп.-М.: Радио и связь. 2001-376 с: ил.

Савельев А. Я. Основы информатики: Учебник для вузов. – М.: Оникс 2001.-370с

Семакин И.Г., Хеннер Е.К. Информатика. 10-й класс. – М.: Лаборатория Базовых Знаний, 2001

Симонович С.В. Информатика. Базовый курс. – СПБ: Питер 2000. -137с

Сяо Д., Керр Д., Мэдник С. Защита ЭВМ.- М.: Айрис 1982.- 226с

Угринович Н.Д. Информатика и информационные технологии. Учебник для 10-11 классов / Н.Д. Угринович. –М.:БИНОМ. Лаборатория знаний, 2003. -512 с.: ил.

Яновский А.В., Воронкова И.А. Информационные технологии: Учеб. Пособие. – Томск, 2007. – 148 с.

При копировании любых материалов с сайта evkova.org обязательна активная ссылка на сайт www.evkova.org

Сайт создан коллективом преподавателей на некоммерческой основе для дополнительного образования молодежи

Сайт пишется, поддерживается и управляется коллективом преподавателей

Telegram и логотип telegram являются товарными знаками корпорации Telegram FZ-LLC.

Cайт носит информационный характер и ни при каких условиях не является публичной офертой, которая определяется положениями статьи 437 Гражданского кодекса РФ. Анна Евкова не оказывает никаких услуг.

Читать:
Как добавить альфа канал в png