Теория кодирования

Альтернативным вариантом  является представление чисел со знаком в дополнительном коде. Идея построения дополнительного кода достаточно проста: на оси целых положительных  чисел, помещающихся в машинное слово  на промежутке (0;65535), сместим положение  нуля на середину интервала.

Числа, попадающие в первую половину (0; 32767) считываются положительными, а числа из второй половины (32768; 65535) – отрицательными.

В этом случае судить о знаке  числа можно будет по его величине и в явном виде выделение знака  не потребуется.

Например, число 1000000000000012 = 3276910 – отрицательное числа, число 0000000000000012 = 110 положительное число.

Принадлежность к интервалу  кодов положительных или отрицательных  чисел видна по состоянию старшего бита – у кодов положительных  чисел его значение «0» отрицательных  – «1».Это напоминает представление  со знаком, но не является таковым, поскольку  используется другой принцип кодирования. Его применение позволяет заменить вычитание чисел их суммированием  в дополнительном коде.

 

6. Эффективное кодирование

6.1 Основная теорема Шеннона о кодировании для канала без помех. Эту теорему можно сформулировать так:

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

пропускной способности канала, т.е при условии

Ī (Z) = ,

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

2. Не существует способа кодирования, обеспечивающего передачу сообщений без их неограниченного накопления, если  Ī (Z) >

Убедимся в справедливости теоремы на основе некоторых логических рассуждений.

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

Если количество знаков в  кодируемой последовательности равно  N, то  = - число типичных последовательностей.

          Так как N = T/τ , где Т – длительность кодируемой последовательности, τ – длительность одного знака то .                       (1)

Каждой типичной последовательности нужно поставить в соответствие кодовую комбинацию той же продолжительности  Т из символов с объемом алфавита m. При скорости манипуляции число символов в кодовой комбинации составит T, что позволяет образовать различных кодовых комбинаций, причем =    (2)

Из сравнения (1) и (2) видно, что . Следовательно, если , то кодовых комбинаций, пропускаемых каналом, достаточно для того, чтобы закодировать все типичные последовательности знаков, причем останется еще некоторый излишек.

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

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

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

Можно дать другую формулировку этой теоремы:

Сообщения источника с  энтропией H(Z) всегда можно закодировать последовательностями символов с объемом алфавита m так, что среднее число символов    на знак сообщения будет сколь угодно близко к велbчине H(Z)/log m, но не менее её.

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

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

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

Метод  Шеннона  – Фано. Код строиться так. Знаки алфавита сообщения выписывают в таблицу в порядке убывания вероятностей. Затем их разделяют на две группы так, чтобы суммы вероятностей в каждой группе были по возможности одинаковыми. Всем знакам верхней половины в качестве первого символа приписывают 0, а всем нижним – 1. Каждую  из полученных групп в свою очередь разбивают на две подгруппы с одинаковыми суммарными вероятностями и т.д. Процесс повторяется до тех пор, пока в каждой подгруппе останется по одному знаку.

Методика Шеннона –  Фано не всегда приводит к однозначному построению кода.

 Метод Хаффмена. Метод Хаффмена гарантирует однозначное построение кода с наименьшим для данного распределения вероятностей средним числом символов на букву.

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

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

Каждому сочетанию ставится в соответствие кодовая комбинация по методике Шеннона – Фано или  Хаффмена.

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

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

Кодовое обозначение каждого  очередного знака зависит от 1-1 предшествовавших ей знаков и определяется по вероятностям различных 1 – грамм на основании  методики Шеннона – Фано или Хаффмена. Конкретное значение 1выбирают в зависимости  от степени корреляционной связи  между знаками или сложности  технической реализации кодирующих и декодирующих устройств. 

 

 

 

 

 

 

 

 

 

 

 

 

Практическая  часть

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

Одним из способов кодирования  является двоичное кодирование и  системы счисления. Примеры работы с системами счисления приведены в приложении 1. Алгоритм перевода числа из одной системы счисления в другую описан в приложении 2.

В практической части рассмотрены  варианты решения задач по теории кодирования различными программными средствами. В частности реализация средствами языка программирования PASCAL.

Лабораторные задания  для решения задач кодирования  на языке программирования PASCAL.

Задача 1. Написать программу, которая реализует перевод из одной системы счисления в другую (из 10 в 2)

Решение:

Program perevod;                                                             

uses crt;                                                                    

var a,i,s,x:integer;                                                         

begin clrscr;                                                                

        writeln('perevod iz 10-oi v 2-yu');                                    

        writeln('vvedite chislo');                                             

begin readln;                                                                

i:=1;                                                                        

s:=0;                                                                        

repeat                                                                       

x:=a mod 2;                                                                  

s:=x*i+s;                                                                    

a:=a div 2;                                                                  

i:=i*10;                                                                     

until (a div 2<1);                                                           

s:=1*i+s;                                                                    

write(s);                                                                    

end;                                                                        

readkey;                                                                 

end.  

 

Ответ:                                                                     

perevod iz 10-oi v 2-yu

vvedite chislo 12

1100

Задачи для самостоятельного решения .

Написать программу, которая  реализует перевод из одной системы  счисления в другую: из 10 в 8;

из 10 в 16;

из 2 в 16;

из 2 в 10;

из 8 в 2;

 

Задача 2. Азбука Морзе, код «Морзянка».

Решение:

Program morze;

uses crt;

var s,t:string;

i:integer;

begin clrscr;

writeln(‘введите текст’);

read(s);

for i:=1 to length(s) do

begin

t:=copy(s,i,l);

if  t=’а’ then write(‘.- ‘)

else if t =’б’ then write(‘-…‘)

else if t =’в’ then write(‘.--‘)

else if t =’г’ then write(‘--. ‘)

else if t =’д’ then write(‘-..‘)

else if t =’е’ then write(‘.   )

else if t =’ж’ then write(‘…-‘)

else if t =’з’ then write(‘--..‘)

else if t =’и’ then write(‘..  ‘)

else if t =’й’ then write(‘.---‘)

else if t =’к’ then write(‘-.-‘)

else if t =’л’ then write(‘.-..‘)

else if t =’м’ then write(‘-- ‘)

else if t =’н’ then write(‘-. ‘)

else if t =’о’ then write(‘--- ‘)

else if t =’п’ then write(‘.--. ‘)

else if t =’р’ then write(‘.-‘)

else if t =’с’ then write(‘… ‘)

else if t =’т’ then write(‘-  ‘)

else if t =’у’ then write(‘..-‘)

else if t =’ф’ then write(‘..-.‘)

else if t =’х’ then write(‘….‘)

else if t =’ц’ then write(‘.-.-‘)

else if t =’ч’ then write(‘-.--‘)

else if t =’ш’ then write(‘----‘)

else if t =’щ’ then write(‘--.-‘)

else if t =’ъ’ then write(‘-..-‘)

else if t =’ы’ then write(‘---.‘)

else if t =’ь’ then write(‘-..-‘)

else if t =’э’ then write(‘..-.‘)

else if t =’ю’ then write(‘..--‘)

else if t =’я’ then write(‘.-.-‘)

else if t =’’ then write(‘//‘)

end;

readkey;

end.

 

Ответ:

vvedite tekst

хорошая погода

….---.-.--- ----.-  .-.-//.--.--- --. --- -.. .-

Задачи для самостоятельного решения.

Написать программу, которая  заменит предложения в знаки (тире, запятая, точки и т.д).

- ясный день;

- солнечная погода;

- алая роза.

 

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

Решение: