Файл: Методы кодирования данных.pdf

Особенности вторичного алфавита при кодировании.

1. Элементарные коды 0 и 1 могут иметь одинаковые длительности

(t0 = t1) или разные (≠);

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

3. Коды могут строиться для отдельного знака первичного алфавита (алфавитное кодирование).

Последующие (второе и далее) приближения при оценке значения информации, приходящейся на знак алфавита, строятся путем учета корреляций, т.е. связей между буквами в словах. Дело в том, что в словах буквы появляются не в любых сочетаниях; это снижает неопределенность определения следующей буквы после нескольких других, например, в русском языке нет слов, в которых встречается сочетание «щц» или «фъ». И напротив, после некоторых сочетаний можно с большей вероятностью предположить возможность появления следующей буквы, например, после распространенного сочетания «пр» непременно следует гласная буква, а их в русском языке всего 10 и, следовательно, вероятность определения следующей буквы 1/10, а не 1/33. В следствие этого примем следующее определение:

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

Учёт в английских словах двухбуквенных сочетаний понижает среднюю информацию на знак до значения I₂^(e) = 3,32 бит, учёт трехбуквенных до I₂^(e)=3,10 бит. Шеннон сумел приблизительно оценить пятибуквенные сообщения I₅^(e) ≈ 2,1 бит и восьмибуквенные I₈^(e) ≈ 1,9 бит. Аналогичные исследования для русского языка дают: I₂^(r) = 3,52 бит; I₃^(r) = 3,01 бит.

Последовательность I₀, I₁, I₂,... является убывающей в любом языке. Перекладывая её на учёт бесконечного числа корреляций, можно оценить предельную информацию на знак в данном языке I_∞, которая будет отражать минимальную неопределенность, связанную с выбором знака алфавита без учета семантических особенностей языка, в то время как I₀ является другим предельным случаем, поскольку характеризует наибольшую информацию, которая может содержаться в знаке данного алфавита. Шеннон ввел величину, которую обозначил относительной избыточностью языка:

(2.4)

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

Рассмотри проблему непосредственно передачи информации.

Для рассмотрения вопросов передачи информации удобно ппредположить, что получатель задает отправителю вопросы, допускающие только ответы «да» или «нет», так что отправителю остается только выбирать ответы в соответствии со смыслом передаваемого сообщения. ^[[15]]

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

Например, чтобы угадать задуманное число от 1 до 100 неразумно спрашивать про все числа по очереди: “Это не «0»?”. ‘А может «1»?". Гораздо разумнее разбить числа на группы и последовательно сужать поиск например - "Это число больше 50?” — “Нет”, “Оно больше 25?” и т.д. Важно, что последовательность вопросов (код) заготовлена и согласована с получателем.

Исследования Шеннона для английского языка дали значение I_∞ ≈ 1,4 ÷ 1,5 бит, что по отношению I₀ = 4,755 бит создает избыточность 0,68. Подобные оценки указывают, что и для других европейских языков, в том числе русского, избыточность составляет 60 — 70%. Это означает, что возможно почти трехкратное сокращение текстов при кодировании без значительного ущерба для их содержательной части и выразительности. Например, телеграфные тексты делаются меньше за счёт неиспользования союзов и предлогов без ущерба для смысла; в них же используются однозначно расшифровываемые сокращения «ЗПТ» и «ТЧК» вместо полных слов (эти сокращения приходится использовать, поскольку знаки «.» и «,» не входят в телеграфный алфавит). Однако такое «экономичное» представление слов понижает разборчивость языка, уменьшает возможность распознавания речи при наличии шума (а это одна из проблем передачи информации по реальным линиям связи), а также исключает возможность локализации и исправления ошибки (написания или передачи) при её возникновении. Именно избыточность языка позволяет легко восстановить текст, даже если он содержит большое число ошибок или неполон. В этом смысле избыточность есть определенная страховка и гарантия разборчивости.

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

2.3. Двоичная система счисления

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

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

Двоичная система счисления - это позиционная система счисления с основанием 2.

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

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

Двоичная система применяется в цифровых устройствах, так как является наиболее простой и соответствует требованиям следующим требованиям: 1) Чем меньше значений существует в системе, тем проще изготовить отдельные элементы, оперирующие этими значениями. Например, две цифры двоичной системы счисления могут быть легко представлены многими физическими явлениями: есть ток — нет тока, индукция магнитного поля больше пороговой величины или нет и т. д. 2) Чем меньше количество состояний у элемента, тем выше помехоустойчивость и тем быстрее быстродействие. Например, чтобы закодировать три состояния через величину индукции магнитного поля, потребуется ввести два пороговых значения, что не будет способствовать помехоустойчивости и надёжности хранения информации. 3) Двоичная арифметика является довольно простой. Простыми являются таблицы сложения и умножения - основных действий над числами. 4) Возможно использование аппарата алгебры логики для вычисления побитовых операций над числами.^[[16]]

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

1 + 0 = 0

1 + 1 = 10

10 + 10 = 100

Таблица умножения двоичных чисел .

0 * 0 = 0

0 * 1 = 0

1 * 0 = 0

1 * 1 = 1

К примеру, при использовании двоичной системы при измерении дюймами при указании линейных размеров в дюймах по традиции используют двоичные дроби, а не десятичные, например: 5¾̋ , 7 ̋ , 3 ̋ и т.д.

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

2.2. Таблица степеней основания «2»

Начиная с цифры 1 все цифры умножаются на два. Точка, которая стоит после «1» называется двоичной точкой.

Преобразование двоичных чисел в десятичные.

Допустим, нам дано двоичное число 110001. Для перевода его в десятичное число просто запишите его справа налево как сумму по разрядам следующим образом:

1 * 2⁰ + 0 * 2¹ + 0 * 2² + 0 * 2³ + 1 * 2⁴ + 1 * 2⁵ = 1 + 0 + 0 + 0 + 16 + 32 = 49.

Можно записать это в виде таблицы следующим образом:

Точно так же, начиная с двоичной точки, двигайтесь справа налево. Под каждой двоичной единицей напишите её эквивалент в строчке ниже. Сложите получившиеся десятичные числа. Таким образом, двоичное число 110001 равнозначно десятичному 49.

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

Например, двоичное число 1011011 переводится в десятичную систему так:

0*2+1=1>>1*2+0=2>>2*2+1=5>>5*2+1=11>>1l*2+0=22»22*2+l=45>> 45*2+1=91. В десятичной системе это число будет записано как 91. Или число 101111 переводится в десятичную систему так: 0*2+1=1>>1*2+0=2>>2*2+1 =5>>5*2+1=11>>11*2+1=23>>23*2+1=47 То есть в десятичной системе это число будет записано как 47. ^[17]

Предположим, нужно перевести число 19 в двоичное. Следует воспользоваться следующей процедурой:

19/2 = 9 с остатком 1

9 /2 = 4 с остатком: 1

4 /2-2 с остатком 0

2/2-1 с остатком 0

1 /2 - 0 с остатком: 1

Таким образом, мы делим каждое частное на 2 и записываем в остаток 1 или 0. Продолжать деление надо пока в делимом не будет 1. Ставим числа из остатка друг за другом, начиная с конца. В результате получаем число 19 в двоичной записи (начиная с конца): 10011.

2.4. Кодирование сигнала

Кодирование сигнала — есть его представление в некоторой форме, удобной для дальнейшего использования сигнала, т.е. это правило, описывающее представления одного набора знаков в другой набор знаков. Таким образом отображаемый набор знаков называется исходным алфавитом, а набор знаков используемый для отображения, - кодовым алфавитом, или алфавитом для кодирования. При этом кодированию подлежат как отдельные символы исходного алфавита, так и их различные комбинации. Соответственно для построения кода используются как отдельные символы кодового алфавита, так и их комбинации. К примеру, существует таблица соответствия между натуральными числами трёх систем счисления. Эту таблицу возможно рассматривать как определенное правило, описывающее отображение набора знаков десятичной системы счисления в двоичную и шестнадцатеричную. Тогда исходный алфавит - десятичные цифры от 0 до 9, а кодовые алфавиты - это 0 и 1 для двоичной системы; цифры от 0 до 9 и символы {А, В, С, D, Е, F} - для шестнадцатеричной. ^[[18]]

Кодовой комбинацией (кодом) называется совокупность символов кодового алфавита, используемы для кодирования одного символа (или одной комбинации символов) исходного алфавита. Вместе с этим кодовая комбинация может содержать один символ кодового алфавита. Исходным символом называется символ (или комбинация символов) исходного алфавита, которому соответствует кодовая комбинация. Например, поскольку 8 — 10002 и 8 является исходным символом, 10008 - это кодовая комбинация, или код, для числа 8. В это же время 8 - это исходный символ. Совокупность кодовых комбинаций называется кодом. Взаимосвязь символов (или комбинаций символов, если кодируются не отдельные символы) исходного алфавита с их кодовыми комбинациями составляет таблицу соответствия (таблицу кодов). Обратная процедура получения исходных знаков но кодам символов называется декодированием. Как видно, для выполнения правильного декодирования код должен быть однозначным, т.е. единственному исходному символу должен соответствовать единственный код и наоборот.