17. Алфавитное кодирование с неравной длительностью элементарных сигналов.

В качестве примера использования данного варианта кодирования рассмотрим телеграфный код Морзе («азбука Морзе»). В нем каждой букве или цифре сопоставляется некоторая последовательность кратковременных импульсов - точек и тире, разделяемых паузами. Длительности импульсов и пауз различны: если продолжительность импульса, соответствующего точке, обозначить τ, то длительность импульса тире составляет 3τ, длительность паузы между точкой и тире τ, пауза между буквами слова 3τ (длинная пауза), пауза между словами (пробел) – 6τ. Таким образом, под знаками кода Морзе следует понимать: «•» - «короткий импульс + короткая пауза», «- » - «длинный импульс + короткая пауза», «0» - «длинная пауза», т.е. код оказывается троичным.

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

Таблица 3.3

Среднее значение длины кода К(r,3) = 3,361. Полагая появление знаков вторичного алфавита равновероятным, получаем среднюю информацию на знак равной I(2) = log23 = 1,585 бит. Подставляя эти данные, а также для русского алфавита I1(r) = ,356 бит в (3.4), получаем:

т.е. избыточность составляет около 22% (для английского языка ≈ 19%). Тем не менее, код Морзе имел в недалеком прошлом весьма широкое распространение в ситуациях, когда источником и приемником сигналов являлся человек (не техническое устройство) и на первый план выдвигалась не экономичность кода, а удобство его восприятия человеком.

18. Блочное двоичное кодирование

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

Пусть имеется словарь некоторого языка, содержащий п = 16000 слов (это, безусловно, более чем солидный словарный запас!). Поставим в соответствие каждому слову равномерный двоичный код. Очевидно, длина кода может быть найдена из соотношения К(А,2) ≥ log2n ≥ 13,97 = 14. Следовательно, каждое слово кодируется комбинацией из 14 нулей и единиц - получатся своего рода двоичные иероглифы. Например, пусть слову «ИНФОРМАТИКА» соответствует код 10101011100110, слову «НАУКА» - 00000000000001, а слову «ИНТЕРЕСНАЯ» -00100000000010; тогда последовательность:

очевидно, будет означать «ИНФОРМАТИКА ИНТЕРЕСНАЯ НАУКА».

Легко оценить, что при средней длине русского слова K(r) = 6,3 буквы (5,3 буквы + пробел между словами) средняя информация на знак первичного алфавита оказывается равной I(A) = К(А,2)/ K(r) =14/6,3 = 2,222 бит, что более чем в 2 раза меньше, чем 5 бит при равномерном алфавитном кодировании. Для английского языка такой метод кодирования дает 2,545 бит на знак. Таким образом, кодирование слов оказывается более выгодным, чем алфавитное.

Еще более эффективным окажется кодирование в том случае, если сначала установить относительную частоту появления различных слов в текстах и затем использовать код Хаффмана. Подобные исследования провел в свое время Шеннон: по относительным частотам 8727 наиболее употребительных в английском языке слов он установил, что средняя информация на знак первичного алфавита оказывается равной 2,15 бит.

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

19. Системы счисления

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

0, 1, 2, 3, 4, 5, 6, 7, 8, 9.

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

Рассмотрим число, записанное в десятичной системе:  343,32. В его записи   цифра 3 повторена три раза, при этом:

- левая цифра 3 означает количество сотен (ее вес равен 102);

- цифра 3, стоящая перед точкой, означает количество единиц (ее вес 10°),

- самая правая цифра 3 означает  количество десятых долей единицы (ее вес равен 10-1).

Последовательность цифр 343.32 представляет собой сокращенную запись выражения:

3·102 + 4·l01 + 3·100 + 3·10-1 + 2·10-2

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

A=anqn + anqn-1 + an-2qn-2 + …+ a1q1 + anq0

или другая форма:

A=anqn-1 + an-1qn-2 + an-2qn-3 + …+ a2q1 + a1q0,

где: a0, a1, a2,…, an – цифры, q –основание системы счисления.

Запись числа в таком виде представляет собой полином, где каждый коэффициент ai,- цифра и i=0,1,2,…n.

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

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

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

Число единиц какого-либо разряда, объединяемых в единицу очередного старшего разряда, называют основанием позиционной системы счисления, а сама система счисления называется  q — ричной.

Например, основанием десятичной системы счисления является число 10; двоичной — число 2; троичной — число 3 и т.д.

Для записи произвольного числа в q-ричной системе счисления достаточно иметь qразных цифр at, i=1,2,…,q. Так, в троичной системе счисления любое число, может быть выражено посредством цифр 0, 1, 2. Эти цифры служат для обозначения некоторых различных целых чисел, называемых базисными.

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

Для установления факта, что число записано не в десятичной системе, около этого числа пишется нижний индекс, указывающий основание системы счисления:  35.548или 101(2).