Исследование эффективного кодирования. Метод Шеннона-Фано

Размещено на http://www.allbest.ru/

Министерство образования Российской Федерации

КУБАНСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНОЛОГИЧЕСКИЙ УНИВЕРСИТЕТ

специальность 080801 Прикладная информатика в экономике

ЗАДАНИЕ

на курсовое проектирование

Тема проекта: Исследование эффективного кодирования. Метод Шеннона-Фано

Выполнила студентка

Пащенко А.В.

Группы 10-К-ПИ-1 3 курса

Краснодар

2012



Министерство образования Российской Федерации

КУБАНСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНОЛОГИЧЕСКИЙ УНИВЕРСИТЕТ

Кафедра ВТ и АСУ

ПОЯСНИТЕЛЬНАЯ ЗАПИСКА

к курсовому проекту (работе)

по дисциплине ``Теория информации и сигналов''

на тему ``Исследование квантования сигналов по уровню``

Выполнила студентка __Пащенко Андрей Васильевич_____

группы _10-К-ПИ-1______________________________________

Допущен к защите_______________________________________

Руководитель проекта д.тех.н.проф. Ключко В.И.__________

Нормоконтролер________________________________________

Защищен_____________ Оценка_______________

Члены комиссии________________________________________



Реферат

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

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

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

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

Ключевые слова: КОДИРОВАНИЕ, МЕТОД, КОД

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

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

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



Содержание

Введение

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

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

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

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

Заключение

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



Введение

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

В курсовой работе будет исследовано построение эффективного кода по методу Шеннона - Фано.



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

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

Понятие о кодировании.

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

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

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

Исторически первый код, предназначенный для передачи сообщений, связан с именем изобретателя телеграфного аппарата Сэмюэля Морзе и известен всем как азбука Морзе. Другим кодом, столь же широко распространенным в телеграфии, является код Бодо. Оба они используют два различных элементарных сигнала. Такие коды принято называть двоичными.

Коды, в которых сообщения представлены комбинациями с неравным количеством символов, называются неравномерными, или некомплектными. Коды, в которых сообщения представлены комбинациями с равным количеством символов, называется равномерными, или комплектными.

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

Коды могут быть представлены формулой, геометрической фигурой, таблицей, графом, многочленом, матрицей и.т.д.

Представление кода числа А в виде многочлена для любой позиционной системы счисления есть сумма произведений коэффициента а_i и веса x_i i-го разряда кода:

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

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

Принципы эффективного кодирования.

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

Различают избыточность естественную и искусственную. Естественная избыточность характерна для первичных алфавитов, а искусственная - для вторичных.

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

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

Статистическая избыточность обусловливается не равновероятностным распределением качественных признаков первичного алфавита и их взаимозависимостью. Например, для английского языка избыточность составляет 50 %.

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

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

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

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

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

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

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

Для двоичных кодов

и разность (L_cp - H) будет тем меньше, чем больше Н, а H достигает максимума при равновероятных и взаимно независимых символах. Отсюда вытекают основные свойства эффективных кодов:

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

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

Из свойств оптимальных кодов вытекают принципы их построения.

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

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

Построение эффективного кода по методу Шеннона-Фано.

Построение эффективного кода по методу Шеннона-Фано сводится к следующей процедуре:

множество сообщений располагают в порядке убывания вероятностей;

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

одной группе присваивается символ 0 , другой группе - символ 1;

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

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

В качестве примера построим код Шеннона - Фано, в котором вероятности появления букв подчиняются закону, представленному в таблице.

Выводы:

Число элементарных символов на букву сообщения с распределением вероятностей появления букв по закону Р=2^-i возрастает в порядке убывания вдроятност?й как натуральный ряд чисел.

Кодовые слова одинаковой вероятности появления имеют равную длину.

Для ансамблей равновероятных сообщений эффективным является равномерный код.

Коды, представляющие первичные алфавиты с неравномерным распределением символов, имеющие минимальную среднюю длину во вторичном алфавите, называется оптимальными неравномерными кодами (ОНК).

Эффективность ОНК оценивают с помощью коэффициента статистического сжатия



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

который показывает, насколько используется статистическая избыточность передаваемого сообщения. Для рассмотренного примера К_сс=1.1; К_оэ=1 .



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

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

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

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

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



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

3.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];

}

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 Результат



Заключение

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



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

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

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

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

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

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

Размещено на Allbest.ru