Xreferat.com » Остальные рефераты » Помехоустойчивое кодирование, распознавание символов

Помехоустойчивое кодирование, распознавание символов

ГОСУДАРСТВЕННЫЙ КОМИТЕТ РОССИЙСКОЙ ФЕДЕРАЦИИ

ПО ВЫСШЕМУ ОБРАЗОВАНИЮ



Кубанский Государственный Технологический Университет


Кафедра автоматизации производственных процессов


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


к курсовой работе


Тема: «КОДИРОВАНИЕ И ПЕРЕДАЧА ИНФОРМАЦИИ.

РАСПОЗНАВАНИЕ ГРАФИЧЕСКИХ ОБЪЕКТОВ».


Выполнил: студент гр. 97-ОА-62

Яворский Д.Н.

Номер зачётной

книжки: 97-ОА-650

Проверил: доцент каф. АПП

Шахворостов Н.Н.


Краснодар

1999


ГОСУДАРСТВЕННЫЙ КОМИТЕТ РОССИЙСКОЙ ФЕДЕРАЦИИ

ПО ВЫСШЕМУ ОБРАЗОВАНИЮ



Кубанский Государственный Технологический Университет


ЗАДАНИЕ


На курсовую работу


Студенту гр.


По дисциплине




Тема курсовой работы




Исходные данные










1. Выполнить расчёты:


1.1


1.2


1.3


1.4


2. Выполнить графические работы:


2.1


2.2


3. Выполнить научные и учебно-исследовательские работы:


3.1


3.2


3.3


3.4


4. Оформить расчётно-пояснительную записку


5. Основная литература








Задание выдано


Срок сдачи работы


Задание принял


Руководитель проекта


Работа защищена


С оценкой


ЧЛЕНЫ КОМИССИИ:

РЕФЕРАТ


ПЕРЕДАЧА ИНФОРМАЦИИ, КОДИРОВАНИЕ, КОД ШЕННОНА-ФЭНО,

ЭФФЕКТИВНОСТЬ КОДА, РАСПОЗНАВАНИЕ СИМВОЛОВ.


Темой курсового проекта является моделирование передачи эффективно закодированной информации по каналу связи с помехами, а также распознавание пяти букв латинского алфaвита.

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

Во второй части сделана попытка распознавания строки в графическом формате, составленной из пяти строчных и пяти прописных букв латинского алфавита,

и cодержащей помехи. В программе была смоделирована система распознавания, основанная на шаблонной классификации.


Курсовой проект содержит страниц, 3 рисунка,

13 таблиц, 4 источника, 2 приложения.

СОДЕРЖАНИЕ


ВВЕДЕНИЕ.......................................


1 КОДИРОВАНИЕ И ПЕРЕДАЧА ИНФОРМАЦИИ

1.1 ТЕОРЕТИЧЕСКИЕ СВЕДЕНИЯ.....................

1.2 ПОЛУЧЕННЫЕ РЕЗУЛЬТАТЫ......................

1.3 ОПИСАНИЕ ПРОГРАММЫ.........................

1.4 ВЫВОД......................................


2 РАСПОЗНАВАНИЕ ГРАФИЧЕСКИХ ОБЪЕКТОВ

1.1 ТЕОРЕТИЧЕСКИЕ СВЕДЕНИЯ ....................

1.2 ОПИСАНИЕ ПРОГРАММЫ.........................

1.3 ВЫВОД......................................


ЗАКЛЮЧЕНИЕ.....................................


ЛИТЕРАТУРА.....................................


ПРИЛОЖЕНИЕ А...................................


ПРИЛОЖЕНИЕ Б...................................

ВВЕДЕНИЕ


Данная работа демонстрирует моделирование процессов передачи и распознавания информации. Она состоит из двух частей.

Первая часть посвящена моделированию канала передачи информации. Для передачи сообщения через такой канал с помехами используется алгоритм кодирования по методу Шеннона-Фэно с последующим кодированием (n,1) кодом.

Вторая часть посвящена моделированию простой системы распознавания. В качестве объектов выступают пять прописных и пять строчных букв латинского алфавита в BMP-формате. Строка символов содержит помехи в виде одиночных и объединившихся в группы пикселей. Использован шаблонный подход к распознаванию.

1 КОДИРОВАНИЕ И ПЕРЕДАЧА ИНФОРМАЦИИ


1.1 ТЕОРЕТИЧЕСКИЕ СВЕДЕНИЯ


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


Источник


Приемник




Vi Vj

Кодер источника

Декодер

источника


Помехи


Zi Zj

Декодер

канала

Кодер

канала

Канал

Xi Yj



Рисунок 1.1.1 - Структура передачи информации


Источник генерирует последовательность сообщений из ансамбля {V, P(V)},

где V – символ сообщения;

P(V) – вероятность символа сообщения, рассчитываемая по формуле:


(1.1.1)


где i=1…m;

m, r – заданные величины.

Кодер источника кодирует сообщение Vi в Zi по алгоритму Шеннона-Фэно.

Энтропия сообщения H(Z), бит/символ вычисляется по следующей формуле:


(1.1.2)


Формула для расчета средней длины кода Lср, бит имеет вид:

(1.1.3)


где L(Zi) – длина кода, бит;

P(Zi) – вероятность кода.


Максимальная энтропия H(Z)max, бит/символ неравномерного двоичного кода Zi определяется по формуле:


(1.1.4)


Зная среднюю длину кода, можно определить коэффициент эффективности Кэф кода Zi по формуле:


(1.1.5)


Для расчета коэффициента избыточности Кизб используется формула:


(1.1.6)


Кодер канала осуществляет простое кодирование повторением n = 3 раз каждого двоичного сигнала сообщения Zi. Таким образом, имеется всего два кода:


Х1=(0 0 0) Х2=(1 1 1)


Вероятность каждого из них определяется по формуле:


(1.1.7)


где к=0,1;

- количество элементов «к» в коде Zi.

При передаче Xк по каналу связи возможны ошибки с вероятностями, определяемыми следующим образом:


P10=0.2 + 0.02A (1.1.8)


P01=0.2 + 0.02B (1.1.9)


где р10 – вероятность принятия нуля при передаче единицы;

р01 – вероятность принятия единицы при передаче нуля;

А, В – заданные величины.


В дальнейшем, для удобства будут использоваться следующие принятые обозначения:


Х - передаваемый код;

Y - принимаемый код.


При построении канальной матрицы P(Y/X) воспользуемся тем, что при передаче может произойти ошибка лишь в одном разряде X1 или X2.

Тогда в 1 строке матрицы элементы определятся следующим образом:

1 – p01 , i = 1

P(xi,yj) = P01/3 , i = 2,3,4. (1.1.10)


0 , i = 5,6,7,8.

Элементы канальной матрицы совместной вероятности P(X,Y) определяются по формуле:


P(xi,yj)=P(xi)P(yj/xi) (1.1.11)


Зная матрицу совместной вероятности P(X,Y), можно вычислить элементы матрицы вероятностей P(Y). Они находятся по формуле:


P(yi)=P(x1,yi)+ P(x2,yi) (1.1.12)


В свою очередь, формула для расчета элементов матрицы условной вероятности P(X/Y) имеет вид:


P(xi/yj)=P(xi,yj)/P(yj) (1.1.13)


Энтропия передаваемого сигнала H(X), бит/символ и принимаемого сигнала H(Y), бит/символ определяется соответственно по формуле:


(1.1.14)


(1.1.15)


Условные энтропии H(X/Y), бит/символ и H(Y/X), бит/символ рассчитываются соответственно по формулам:


(1.1.16)


(1.1.17)


Совместная энтропия H(X,Y), бит/символ находится по формуле:


(1.1.18)


Взаимная энтропия I(X,Y), бит/символ определяется по формуле:


(1.1.19)


Передача информации по каналу связи осуществляется со скоростью V, рассчитываемой по формуле:


V = 1000(A+1) (1.1.20)


Постоянную скорость передачи двоичных символов по каналу связи R, бит/с можно рассчитать по формуле:


R = V I(X,Y) / 3; (1.1.21)


Производительность источника , бит/с определяется по следующей формуле:


= (H(X) V ) (1.1.22)

1.2 ПОЛУЧЕННЫЕ РЕЗУЛЬТАТЫ


По условию варианта определены следующие постоянные:


m = 15;

r = 10;


Определим характеристики посылаемых символов.


Вероятности символов Vi(они же - вероятности кода Zi), генерируемых источником рассчитываем по формуле 1.1.1. Полученные значения вероятностей приведены в таблице 1.2.2.

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

Результаты разработки кодов показаны в таблице 1.2.1.

Таблица 1.2.1 - Вероятности и коды символов


Vi P(Vi) Zi L(Zi)
1 0.231 11 2
2 0.183 10 2
3 0.1408 011 3
4 0.1042 0101 4
5 0.0732 01001 5
6 0.0732 01000 5
7 0.0479 00111 5
8 0.0479 00110 5
9 0.0282 00101 5
10 0.0282 00100 5
11 0.0141 00011 5
12 0.0141 00010 5
13 0.0056 000011 6
14 0.0056 000010 6
15 0.0028 000000 6

Вычислим энтропию сообщения H(Z),бит/символ по формуле

1.1.2 :


H(Z) = 3.218 бит/символ


Среднюю длину неравномерного кода определим по формуле

1.1.3 :


Lср = 3.5652 бит


Максимальную энтропию неравномерного двоичного кода Zi определяем по формуле 1.1.4:


H(Z)max = 3.218 бит


По формуле 1.1.5 вычислим коэффициент эффективности Кэф неравномерного двоичного кода Zi:


Кэф = 0.903


Для расчета коэффициента избыточности Кизб воспользуемся формулой 1.1.6:


Кизб = 0.176


При простом кодировании повторением n=3 раз каждого двоичного сигнала сообщения Zi имеется два кода: Х1 и Х2, вероятности которых Р(Х1) и Р(Х2) находятся по формуле 1.1.7:


Р(Х1) = 0.4113 Р(Х2) = 0.5885


Вероятности возможных ошибок, при прохождении кода по каналу определяются по формулам 1.1.8 и 1.1.9 соответственно:


P10 = 0.3 P01 = 0.2

Канальная матрица P(Y/X) со стороны приемника для кода Х0 и Х1, рассчитанная по формуле 1.1.10, приведена в таблице 1.2.3. Для проверки расчета в последнем столбце таблицы 1.2.3 приведена сумма по текущей строке. Значения вероятностей в таблице 1.2.3 приводятся в десятитысячных долях единицы.


Таблица 1.2.2 - Канальная матрица P(Y/X)


X

Y

сумма


000 001 010 100 011 101 110 111
000 8000 0667 0667 0667 0000 0000 0000 0000 10000
111 0000 0000 0000 0000 1000 1000 1000 1000 10000

В таблице 1.2.3 приведены значения элементов канальной матрицы совместной вероятности P(X,Y), определенные по формуле 1.1.11. Значения вероятностей в таблице 1.2.3 приводятся в десятитысячных долях единицы.


Таблица 1.2.3 - Матрица совместных вероятностей P(X,Y)


Х

Y

000 001 010 100 011 101 110 111
000 3292 0274 0274 0274 0000 0000 0000 0000
111 0000 0000 0000 0000 0588 0588 0588 4119

Элементы матрицы вероятностей P(Y) находятся по формуле 1.1.12. Полученные данные приведены в таблице 1.2.4 в десятитысячных долях единицы. В последнем столбце для проверки приведена сумма по строке.


Таблица 1.2.4 - Матрица P(Y)

Y

Сумма

000 001 010 100 011 101 110 111
3292 0274 0274 0274 0588 0588 0588 4119 10000

Рассчитав матрицы P(X,Y) и P(Y), можно вычислить элементы матрицы условной вероятности P(X/Y) по формуле 1.1.13. Матрица P(X/Y) приведена в таблице 1.2.6.


Рассчитываем энтропию передаваемого сигнала H(X) и энтропию принимаемого сигнала H(Y) по формулам 1.1.14 и 1.1.15 соответственно:


H(X) = 0.9777 бит/символ


H(Y) = 2.2025 бит/символ


Условные энтропии H(X/Y) и H(Y/X) рассчитаем, воспользовавшись формулами 1.1.16 и 1.1.17 соответственно:


H(X/Y) = 0.0000 бит/символ


H(Y/X) = 1.2244 бит/символ


Таблица 1.2.5 - Матрица P(X/Y)


X

Y

Сумма


000 111
000 1 0 1.0000
001 1 0 1.0000
010 1 0 1.0000
100 1 0 1.0000
011 0 1 1.0000
101 0 1 1.0000
110 0 1 1.0000
111 0 1 1.0000

По формуле 1.1.18 находим совместную энтропию H(X,Y):


H(X,Y) = 2.2014 бит/символ


Сделаем проверку полученных значений энтропий:


H(Y/X) + H(X) = 2.2025 бит/символ


H(X/Y) + H(Y) = 2.2025 бит/символ


Совпадение полученных значений свидетельствует о правильности найденных значений энтропий.


Определим значение взаимной энтропии I(X,Y), используя формулу 1.1.19:


I(X,Y) = 0.9777 бит/символ


Для отыскания следующих характеристик канала вычислим скорость передачи двоичных символов по каналу связи с помощью формулы 1.1.20:


V = 6000 символов/c


Информация передается по каналу связи с постоянной скоростью R, вычисляемой с помощью формулы 1.1.21:


R = 1956.1 бит/с


Производительность источника по формуле 1.1.22 равна:


= 5868.3 бит/с


Результатом работы программы являются графики числа ошибок восстановления информации от параметра n (n,1) – кода и от p01 и p10. При теоретическом расчёте мы предположили, что в канале нет ошибок. Действительно, полученное нулевое значение энтропии H(X/Y) также об этом свидетельствует.

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

Примерный вид полученных графиков приведен на рисунках 1.2.1 и 1.2.2.




45


Количество

ошибок,%


15


20 40 60 100

Количество повторений, n


Рисунок 1.2.1 – Число ошибок восстановления




100


Количество

ошибок,%






15




20 40 60 100

p01,p10, %


Рисунок 1.2.1 – Число ошибок восстановления


1.3 ОПИСАНИЕ ПРОГРАММЫ


В соответствии с заданием мною была разработана программная модель канала с выводом графика зависимости числа ошибок от числа n. Программа написана на языке Borland Pascal 7.0.

Для программной реализации канала программа запрашивает длину передаваемого массива сообщений, число n и выполняет подсчет числа ошибок при его передаче. Затем идет расчет массива данных для построения графика зависимости числа ошибок от n для n, изменяющегося в интервале 1..100 с шагом 3. После этого происходит вывод на экран искомого графика.

В программе используются следующие процедуры и функции:

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

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

Процедура set_codes заполняет массив кодов по алгоритму Шеннона-Фэно и инициализирует маски для декодирования неравномерного кода.

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

Процедура deranges вносит в код, соответствующий сообщению sourse, помехи в соответствии с моделью (n,1)-кода. В ней используются функции побитного сдвига shr и shl, а также функция flag.

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

в старших битах.

Процедура graphik служит для отображения на экране графика зависимости числа ошибок восстановления информации от значений параметра n (n,1) – кода. Всё изображение привязано к началу координат (x0,y0). Для удобства по

оси y откладываются значения в %. График отображается отрезками прямых для сглаживания резких скачков

значений.


1.4 ВЫВОД


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


Кодирование информации по Шеннону-Фэно в сочетании с кодированием (n,1) кодом показало неплохие результаты при программном моделировании канала. Так, при передаче порядка 1000 символов при n = 20..25

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

Поможем написать работу на аналогичную тему

Получить выполненную работу или консультацию специалиста по вашему учебному проекту

Похожие рефераты: