Кодирование информации

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

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

     Эти коды получили наибольшее применение в системах передачи дискретной информации.

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

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

     Проверочная группа из r символов формируется поэлементно по соответствующему алгоритму. Коды Хемминга, имеющие dmin = 3, позволяют исправить одну ошибку. [2; c. 230] 

2. ПРАКТИЧЕСКАЯ РЕАЛИЗАЦИЯ КОДИРОВАНИЯ

      2.1 Реализация программы кодирования по методу Хаффмана.

      Алгоритм Хаффмана ( англ. Huffman) — адаптивный жадный алгоритм оптимального префиксного кодирования алфавита с минимальной  избыточностью. Был разработан в 1952 году доктором Массачусетского технологического института Дэвидом Хаффманом. В настоящее время используется во многих программах сжатия данных.

      Код Хаффмана — статистический способ сжатия информации, который дает снижение средней длины кода, используемого для представления символов фиксированного алфавита. [7]

      Данная программа представляет собой реализацию кодирования по методу Хаффмана. Средой разработки данного приложения явилась среда программирования Borland Delphi 7. Ниже будут приведены описания основных процедур и функций данной программы с подробным описанием и комментариями. Полный исходный код будет представлен в приложениях.

      Работа данного приложения начинается с формирование таблицы частот символов на основе частотного анализа введённой пользователем строки. По умолчанию, строке присваивается значение «ИНФОРМАТИКА!». Заметим, что приложение чувствительно к регистру. Заполнение таблицы происходит по событию «TForm1.Button2Click»(кнопка «Заполнение вероятностной таблицы») и описано в соответствующей процедуре: 

      procedure TForm1.Button2Click(Sender: TObject);

      var i: integer;

          ch:char;

          schVh:integer;

      begin

        if edit8.Text = '' then edit8.Text:='ИНФОРМАТИКА!';

        form2.ListBox1.Clear;

        Form2.listbox1.Items.Add('Длина сообщения(символов): '+inttostr(length(edit8.Text)));

        str:=edit8.Text;

        kolCh:=0;

        While str<>'' do

          begin

            ch:=str[1];

            schVh:=0;

            kolCh:=kolCh+1;

            i:=1;

            while i<=length(str) do

              begin

                if str[i]=ch then

                               begin

                                 schVh:=schVh+1; //счётчик вхождений

                                 delete(str,i,1);

                                 i:=i-1;

                               end;

                i:=i+1;

              end;

            stringGrid1.RowCount:=kolCh+1;

            stringGrid1.Cells[0,kolCh]:=inttostr(kolCh);

            stringGrid1.Cells[1,kolCh]:='"'+ch+'"'; // добавляем в таблицу

            stringGrid1.Cells[2,kolCh]:=floattostr(schVh);

          end;

        //СТАТИСТИКА (общие расчёты, выводятся на Form2)

        Form2.listbox1.Items.Add('Количество символов алфавита: '+inttostr(kolCh));

        For i:=1 to kolCh do

            stringGrid1.Cells[3,i]:=floattostr(strtofloat(stringGrid1.Cells[2,i])/length(edit8.Text));

        For i:=1 to kolCh do

          begin

            StringGrid1.Cells[4,i]:=floattostr(-strtofloat(stringGrid1.Cells[3,i])*((ln(strtofloat(stringGrid1.Cells[3,i])/ln(2)))));

            ent:=ent-strtofloat(stringGrid1.Cells[3,i])*((ln(strtofloat(stringGrid1.Cells[3,i])/ln(2))));

          end;

        Form2.listbox1.Items.Add('Средняя энтропия сообщения: '+floattostr(ent/kolCh));

        //СТАТИСТИКА END

      end; 

Бинарное дерево, соответствующее коду Хаффмана, называют деревом Хаффмана.

Задача построения кода Хаффмана равносильна задаче построения соответствующего ему дерева.

Общая схема  построения дерева Хаффмана:

1. Составим список кодируемых символов (при этом будем рассматривать каждый символ как одноэлементное бинарное дерево, вес которого равен весу символа).
2. Из списка выберем 2 узла с наименьшим весом (под весом можно понимать частоту использования символа — чем чаще используется, тем больше весит).
3. Сформируем новый узел и присоединим к нему, в качестве дочерних, два узла выбранных из списка. При этом вес сформированного узла положим равным сумме весов дочерних узлов.
4. Добавим сформированный узел к списку.
5. Если в списке больше одного узла, то повторить 2-5.

      Таким образом, для формирования кодов нам достаточно построить взвешенное кодовое дерево. Это реализуется путём построения «вектора отцов» (arrOtec) - один из способов представления подвешенных деревьев, представляющего собой массив из n элементов (n – количество листьев дерева), в котором будут содержаться номера «отцов» каждого элемента, соответствующего индексу. Этот массив является динамическим, его размер определяется из количества символов в таблице (2*KolCh-1), поэтому целесообразным является обработка возможных исключительных ситуаций с помощью конструкции Try…Except…end. В случае ошибки (незаполненной вероятностной таблицы 2*KolCh-1=2*0-1=-1) всплывающие окно сообщает об ошибке и необходимости заполнения таблицы.

      Построение дерева с помощью вектора отцов происходит в несколько этапов:

1. находим 2 элемента с наименьшим весом(массив весов arrVes). Ставим им в соответствие «отца» новый элемент (значениям «вектора отцов» присваиваем индекс нового элемента). В массиве весов «отцу»данных элементов сумму их весов, а самим элементам значение 0, чтобы исключить их из дальнейшего рассмотрения.
2. в символьном массиве кодов ветвей (arrChKod) значению большего элемента ставим 0, меньшего 1.
3. повторяем данную процедуру, пока не будет заполнен весь «вектор отцов», за исключением последнего элемента – корня дерева, с весом равным 1.

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

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

       Построение кодов происходит по событию TForm1.Button1Click. 

       Try

         n:=kolCh*2-1;   //размерность дерева.

         //инициируем массивы: весов, "вектор отцов", кодовых символов (0,1), массив кода

         setlength (arrVes,n+1);

         setlength (arrOtec,n+1);

         setlength (arrChKod,n+1);

         setlength (arrKod,n+1);

         For i:=1 to n do arrVes[i]:=0;

         For i:=1 to n do arrOtec[i]:=0;

         For i:=1 to n do arrChKod[i]:='_';

         For i:=1 to kolCh do

           arrVes[i]:=strtofloat(stringGrid1.cells[2,i]);

         For j:=kolCh+1 to n do

         begin

           min:=100;   //минимальный

           newmin:=100; //самый минимальный  :)

           for i:=1 to n do

             begin

               if (newmin>=arrVes[i]) and(arrVes[i]<>0) then  //ищем 2 элемента с минимальным весом

                                     begin

                                       nmin:=nnewmin;

                                       min:=newmin;

                                       nnewmin:=i;

                                       newmin:=arrVes[i];

                                     end;

               if (min>=arrVes[i]) and(arrVes[i]<>0) and (arrVes[i]<>newmin) then //контрольный поиск 2 минимального :)

                                   begin

                                     nmin:=i;

                                     min:=arrVes[i];

                                   end;

             end; //end i

           //заполняем вектор отцов. на основе 2-х найденых элементов образуется новый

           //попутно формируется массив кодов. в процессе формирования изменяется и анализируется массив весов.

           arrOtec[nmin]:=j;

           arrOtec[nnewmin]:=j;

           arrVes[j]:=arrVes[nmin]+arrVes[nnewmin];

           arrVes[nmin]:=0;

           arrVes[nnewmin]:=0;

           arrChKod[nmin]:='0';

           arrChKod[nnewmin]:='1';

         end; //end j 

       Отчистка таблицы и кодовых полей происходит по изменению вводимой строки, а так же из основного меню: «Меню»-«Новый Код». Вызывается процедура обнуления всех глобальных параметров программы и объектов на формах Form1, Form2.

       Данная программа также рассчитывает основные информационные параметры данного кодирования.  Доступ к этой информации осуществляется через главное меню программы, вкладка «Статистика».  
 
 

       2.2. Реализация программы – эмулятора терминала азбуки Морзе.

       А́збука Мо́рзе— способ кодирования букв алфавита, цифр, знаков препинания и других символов при помощи длинных и коротких сигналов, так называемых «тире» и «точек» (а также пауз, разделяющих буквы). За единицу времени принимается длительность одной точки. Длительность тире равна трём точкам. Пауза между элементами одного знака — одна точка, между знаками в слове — 3 точки, между словами — 7 точек.

       Была  названа в честь американского  изобретателя Сэмюэля Морзе, который предложил её в 1838.

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

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