Помехоустойчивое кодирование, распознавание символов
ГОСУДАРСТВЕННЫЙ КОМИТЕТ РОССИЙСКОЙ ФЕДЕРАЦИИ
ПО ВЫСШЕМУ ОБРАЗОВАНИЮ
Кубанский Государственный Технологический Университет
Кафедра автоматизации производственных процессов
ПОЯСНИТЕЛЬНАЯ ЗАПИСКА
к курсовой работе
Тема: «КОДИРОВАНИЕ И ПЕРЕДАЧА ИНФОРМАЦИИ.
РАСПОЗНАВАНИЕ ГРАФИЧЕСКИХ ОБЪЕКТОВ».
Выполнил: студент гр. 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