Описание программы

Реферат

Пояснительная записка курсовой работы – 19 стр.

Количество рисунков – 2

Количество таблиц – 1

Количество приложений – 1

Количество источников – 3

Ключевые слова: КОДИРОВАНИЕ, ЭФФЕКТИВНОЕ КОДИРОВАНИЕ, МЕТОД ШЕННОНА-ФАНО, СИМВОЛ, СООБЩЕНИЕ, ДВОИЧНЫЙ КОД, ОПТИМАЛЬНЫЙ КОД, РАВНОВЕРОЯТНЫЕ БУКВЫ.

Объектом исследования работы является изучение принципов эффективного кодирования методом Шеннона-Фано.

Цель работы состоит в создании программы эффективного кодирования методом Шеннона-Фано.

К полученным результатам относится приложение, демонстрирующее эффективное кодирование методом Шеннона-Фано.

Содержание

Введение………………………………………………………….………..5

1.Теоретические сведения.………………………………..………….....6

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

1.2.Основные сведения о методе кодирования Шеннона-Фано……...6

1.3.Алгоритм вычисления кодов Шеннона-Фано……………………...7

1.4.Общие сведения и пример решения задачи………………………..7

2.Требования к программному изделию……………………………….10

3.Описание программы……………………………………………….....11

4.Результаты и листинг программы……………………...…………….12

Заключение………………………………………………………………..18

Список использованной литературы…………..…….……..………….19

Введение

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

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

Одним из методов защиты является кодирование.

Кодирование – это отображение сообщений кодом по определенному правилу присвоения символов.

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

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

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

Таким образом, информатика занимается изучением обработки и передачи информации.

В работе отражается применение базовых понятий информатики.

1.Теоретические сведения

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

Этот вид кодирования используется для уменьшения объемов информации на носителе - сигнале.

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

где k – число символов исходного алфавита;

n_s – число двоичных разрядов для кодирования символа s;

f_s – частота символа s; причем

При эффективном кодировании существует предел сжатия, ниже которого не «спускается» ни один метод эффективного кодирования - иначе будет потеряна информация. Этот параметр определяетсяпредельным значением двоичных разрядов возможного эффективного кода – l_пр:

где n – мощность кодируемого алфавита,

f_i – частота i-го символа кодируемого алфавита.

Существуют два классических метода эффективного кодирования: метод Шеннона-Фано и метод Хаффмена. Входными данными для обоих методов является заданное множество исходных символов для кодирования с их частотами; результат - эффективные коды.

1.2 Основные сведения о методе кодирования Шеннона-Фано

Кодирование Шеннона — Фано (англ. Shannon-Fano coding) — алгоритм префиксного неоднородного кодирования. Относится квероятностным методам сжатия (точнее, методам контекстного моделирования нулевого порядка). Подобно алгоритму Хаффмана, алгоритм Шеннона — Фано использует избыточность сообщения, заключённую в неоднородном распределении частот символов его (первичного) алфавита, то есть заменяет коды более частых символов короткими двоичными последовательностями, а коды более редких символов — более длинными двоичными последовательностями.

Алгоритм был независимо друг от друга разработан Шенноном (публикация «Математическая теория связи», 1948 год) и, позже, Фано (опубликовано как технический отчёт).

1.3 Алгоритм вычисления кодов Шеннона-Фано

Код Шеннона — Фано строится с помощью дерева. Построение этого дерева начинается от корня. Всё множество кодируемых элементов соответствует корню дерева (вершине первого уровня). Оно разбивается на два подмножества с примерно одинаковыми суммарными вероятностями. Эти подмножества соответствуют двум вершинам второго уровня, которые соединяются с корнем. Далее каждое из этих подмножеств разбивается на два подмножества с примерно одинаковыми суммарными вероятностями. Им соответствуют вершины третьего уровня. Если подмножество содержит единственный элемент, то ему соответствует концевая вершина кодового дерева; такое подмножество разбиению не подлежит. Подобным образом поступаем до тех пор, пока не получим все концевые вершины. Ветви кодового дерева размечаем символами 1 и 0, как в случае кода Хаффмана.

При построении кода Шеннона — Фано разбиение множества элементов может быть произведено, вообще говоря, несколькими способами. Выбор разбиения на уровне n может ухудшить варианты разбиения на следующем уровне (n + 1) и привести к неоптимальности кода в целом. Другими словами, оптимальное поведение на каждом шаге пути ещё не гарантирует оптимальности всей совокупности действий. Поэтому код Шеннона — Фано не является оптимальным в общем смысле, хотя и дает оптимальные результаты при некоторых распределениях вероятностей. Для одного и того же распределения вероятностей можно построить, вообще говоря, несколько кодов Шеннона — Фано, и все они могут дать различные результаты. Если построить все возможные коды Шеннона — Фано для данного распределения вероятностей, то среди них будут находиться и все коды Хаффмана, то есть оптимальные коды.

1.4 Общие сведения и пример решения задачи

Задача

Построить эффективный код для сообщения, состоящего из 8 равновероятных букв.

Решение задачи

Построим код по методу Шеннона-Фано, если ве­роятности данного ансамбля сообщений равны

Р₁=Р₂=Р₃=…=Р₈=2^-3= ,

и порядок их размещения не играет роли.

1 шаг: располагаем сооб­щения в порядке возрастания порядковых номеров.

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

3 шаг: первой группе в качестве первого символа кодовых слов присваиваем 0, второй группе — 1.

4 шаг: разбиваем каждую из подгрупп еще на две равнове­роятные подгруппы, затем каждой первой подгруппе в качестве второго символа присваиваем 0, авторой - 1, и записываем их в колонку.

5 шаг: каждую из подгрупп разбиваем на две равновероят­ные части и первой из них присваиваем 0, а второй - 1 и, та­ким образом, в колонке появляется значение третьего символа.

Энтропия при N=8 передаваемых сообщениях

H=log₂N=log₂8=3 [бит/симв.]

Среднее число двоичных знаков на букву кода

Lcp=N, то есть код оптимальный.

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

Таблица 1

Сообщения	Порядок разбиения на группы	Кодограмма
1р.	2р.	3р.
А1
А2
А3
А4
А5
А6
А7
А8

2.Требования к программному изделию

2.1.Требования к функциональным характеристикам

Разработанная программа пригодна для эффективного кодирования методом Шеннона-Фано.

2.2. Контроль входной и выходной информации.

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

Описание программы

3.1. Интерфейс пользователя

На рисунке 1 показан внешний вид программы при запуске

Рис. 1

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

Также в программе находится поле ввода данных для кодирования и поле вывода закодированной информации.

4.Результаты и листинг программы

4.1. Листинг программы:

using System;

using System.Collections.Generic;

using System.ComponentModel;

using System.Data;

using System.Drawing;

using System.Linq;

using System.Text;

using System.Windows.Forms;

namespace WindowsFormsApplication13

{

public partial class Form1: Form

{

public Form1()

{

InitializeComponent();

}

private void button1_Click(object sender, EventArgs e)

{

label6.Text = "";

label8.Text = "";

dataGridView2.Rows.Clear();

dataGridView1.Rows.Clear();

int n = int.Parse(textBox1.Text);

string[] mass1 = new string[n];

for (int i = 0; i < n; i++)

{

mass1[i] = dataGridView3.Rows[i].Cells[0].Value.ToString();

label6.Text += mass1[i];

}

string[] mass2 = new string[9] { "А", "Б", "В", "Г", "Д", "Е", "Ё", "Ж", "З" };

int count1 = 0;

int count2 = 0;

int count3 = 0;

int count4 = 0;

int count5 = 0;

int count6 = 0;

int count7 = 0;

int count8 = 0;

int count9 = 0;

dataGridView1.Rows.Clear();

for (int i = 0; i < n; i++)

{

if (mass1[i] == mass2[0]) count1++;

else if (mass1[i] == mass2[1]) count2++;

else if (mass1[i] == mass2[2]) count3++;

else if (mass1[i] == mass2[3]) count4++;

else if (mass1[i] == mass2[4]) count5++;

else if (mass1[i] == mass2[5]) count6++;

else if (mass1[i] == mass2[6]) count7++;

else if (mass1[i] == mass2[7]) count8++;

else if (mass1[i] == mass2[8]) count9++;

}

double[] fn = new double[9];

double[] mass3 = new double[9] { count1, count2, count3, count4, count5, count6, count7, count8, count9 };

Array.Sort(mass3,mass2);

for (int i = 0; i < 9; i++)

{

dataGridView1.Rows.Add(mass2[i], mass3[i]);

}

for (int i = 0; i < 9; i++)

{

fn[i] = Math.Round(mass3[i]/20,2);

dataGridView1.Rows[i].Cells[2].Value = fn[i];

}

////

int m = 3;

for (int i = 0; i < 9; i++)

{

if ((mass3[8]!=0)&(m<4)&(mass3[8]!=mass3[i]))

dataGridView1.Rows[8].Cells[m].Value = 1;

dataGridView1.Rows[8].Cells[11].Value = dataGridView1.Rows[8].Cells[3].Value.ToString();

}

m = 4;

for (int i = 0; i < 9; i++)

{

for (int k = 3; k <= m; k++)

{

if (mass3[7]!= 0)

dataGridView1.Rows[7].Cells[k].Value = 0;

}

if ((mass3[7]!= 0) & (m < 5) & (mass3[7]!= mass3[i]))

dataGridView1.Rows[7].Cells[m].Value = 1;

dataGridView1.Rows[7].Cells[11].Value = dataGridView1.Rows[7].Cells[3].Value.ToString() + dataGridView1.Rows[7].Cells[4].Value.ToString();

}

m = 5;

for (int i = 0; i < 9; i++)

{

for (int k = 3; k <= m; k++)

{

if (mass3[6]!= 0)

dataGridView1.Rows[6].Cells[k].Value = 0;

}

if ((mass3[6]!= 0) & (m < 6) & (mass3[6]!= mass3[i]))

dataGridView1.Rows[6].Cells[m].Value = 1;

dataGridView1.Rows[6].Cells[11].Value = dataGridView1.Rows[6].Cells[3].Value.ToString() + dataGridView1.Rows[6].Cells[4].Value.ToString()

+ dataGridView1.Rows[6].Cells[5].Value.ToString();

}

m = 6;

for (int i = 0; i < 9; i++)

{

for (int k = 3; k <= m; k++)

{

if (mass3[5]!= 0)

dataGridView1.Rows[5].Cells[k].Value = 0;

}

if ((mass3[5]!= 0) & (m < 7) & (mass3[5]!= mass3[i]))

dataGridView1.Rows[5].Cells[m].Value = 1;

dataGridView1.Rows[5].Cells[11].Value = dataGridView1.Rows[5].Cells[3].Value.ToString() + dataGridView1.Rows[5].Cells[4].Value.ToString()

+ dataGridView1.Rows[5].Cells[5].Value.ToString() + dataGridView1.Rows[5].Cells[6].Value.ToString();

}

m = 7;

for (int i = 0; i < 9; i++)

{

for (int k = 3; k <= m; k++)

{

if (mass3[4]!= 0)

dataGridView1.Rows[4].Cells[k].Value = 0;

}

if ((mass3[4]!= 0) & (m < 8) & (mass3[4]!= mass3[i]))

dataGridView1.Rows[4].Cells[m].Value = 1;

dataGridView1.Rows[4].Cells[11].Value = dataGridView1.Rows[4].Cells[3].Value.ToString() + dataGridView1.Rows[4].Cells[4].Value.ToString()

+ dataGridView1.Rows[4].Cells[5].Value.ToString() + dataGridView1.Rows[4].Cells[6].Value.ToString()

+ dataGridView1.Rows[4].Cells[7].Value.ToString();

}

m = 8;

for (int i = 0; i < 9; i++)

{

for (int k = 3; k <= m; k++)

{

if (mass3[3]!= 0)

dataGridView1.Rows[3].Cells[k].Value = 0;

}

if ((mass3[3]!= 0) & (m < 9) & (mass3[3]!= mass3[i]))

dataGridView1.Rows[3].Cells[m].Value = 1;

dataGridView1.Rows[3].Cells[11].Value = dataGridView1.Rows[3].Cells[3].Value.ToString() + dataGridView1.Rows[3].Cells[4].Value.ToString()

+ dataGridView1.Rows[3].Cells[5].Value.ToString() + dataGridView1.Rows[3].Cells[6].Value.ToString()

+ dataGridView1.Rows[3].Cells[7].Value.ToString() + dataGridView1.Rows[3].Cells[8].Value.ToString();

}

m = 9;

for (int i = 0; i < 9; i++)

{

for (int k = 3; k <= m; k++)

{

if (mass3[2]!= 0)

dataGridView1.Rows[2].Cells[k].Value = 0;

}

if ((mass3[2]!= 0) & (m < 10) & (mass3[2]!= mass3[i]))

dataGridView1.Rows[2].Cells[m].Value = 1;

dataGridView1.Rows[2].Cells[11].Value = dataGridView1.Rows[2].Cells[3].Value.ToString() + dataGridView1.Rows[2].Cells[4].Value.ToString()

+ dataGridView1.Rows[2].Cells[5].Value.ToString() + dataGridView1.Rows[2].Cells[6].Value.ToString()

+ dataGridView1.Rows[2].Cells[7].Value.ToString() + dataGridView1.Rows[2].Cells[8].Value.ToString()

+ dataGridView1.Rows[2].Cells[9].Value.ToString();

}

m = 10;

for (int i = 0; i < 9; i++)

{

for (int k = 3; k <= m; k++)

{

if (mass3[1]!= 0)

dataGridView1.Rows[1].Cells[k].Value = 0;

}

if ((mass3[1]!= 0) & (m < 11) & (mass3[1]!= mass3[i]))

dataGridView1.Rows[1].Cells[m].Value = 1;

dataGridView1.Rows[1].Cells[11].Value = dataGridView1.Rows[1].Cells[3].Value.ToString() + dataGridView1.Rows[1].Cells[4].Value.ToString()

+ dataGridView1.Rows[1].Cells[5].Value.ToString() + dataGridView1.Rows[1].Cells[6].Value.ToString()

+ dataGridView1.Rows[1].Cells[7].Value.ToString() + dataGridView1.Rows[1].Cells[8].Value.ToString()

+ dataGridView1.Rows[1].Cells[9].Value.ToString() + dataGridView1.Rows[1].Cells[10].Value.ToString();

}

m = 11;

for (int i = 0; i < 9; i++)

{

for (int k = 3; k <= m; k++)

{

if (mass3[0]!=0)

dataGridView1.Rows[0].Cells[k].Value = 0;

}

dataGridView1.Rows[0].Cells[11].Value = dataGridView1.Rows[0].Cells[3].Value.ToString() + dataGridView1.Rows[0].Cells[4].Value.ToString()

+ dataGridView1.Rows[0].Cells[5].Value.ToString() + dataGridView1.Rows[0].Cells[6].Value.ToString()

+ dataGridView1.Rows[0].Cells[7].Value.ToString() + dataGridView1.Rows[0].Cells[8].Value.ToString()

+ dataGridView1.Rows[0].Cells[9].Value.ToString() + dataGridView1.Rows[0].Cells[10].Value.ToString();

}

//////////////

for (int i = 0; i < 9; i++)

{

dataGridView2.Rows.Add(mass1[i]);

for (int j = 0; j < 9; j++)

{

if (dataGridView2.Rows[i].Cells[0].Value.ToString() == dataGridView1.Rows[j].Cells[0].Value.ToString())

dataGridView2.Rows[i].Cells[1].Value = dataGridView1.Rows[j].Cells[11].Value;

}

label8.Text += dataGridView2.Rows[i].Cells[1].Value.ToString();

}

//////////////

}

}

}

4.2. Результат:

Рис. 2

Заключение

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

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

Кодирование Шеннона — Фано является достаточно старым методом сжатия, и на сегодняшний день оно не представляет особого практического интереса. В большинстве случаев, длина последовательности, сжатой по данному методу, равна длине сжатой последовательности с использованием кодирования Хаффмана. Но на некоторых последовательностях могут сформироваться неоптимальные коды Шеннона — Фано, поэтому более эффективным считается сжатие методом Хаффмана.

Список используемой литературы

1. А.В.Власенко, В.И.Ключко Теория информации и сигналов. Учебное

пособие / Краснодар: Изд-во КубГТУ, 2003.- 97 с.

2. Теория передачи сигналов: Учебник для вузов / А.Г.Зюко, Д.Д.Кловский,

М.В.Назаров, Л.М.Финк. - 2-е изд., перераб. и доп. - М.: Радио и связь, 1986. - 304 с.: ил.

3. Т. А. Павловская. C#. Программирование на языке высокого уровня.Учебник для вузов.ISBN: 978-5-91180-174-8.2009г.