Моделирование систем обработки информации

Узел 1 состоит из двух элементов А и Б и выходит из строя при отказе одновременно обоих элементов А и Б, т. е. если только элемент А или только элемент Б неисправен, то узел исправен. Предположим, что вероятность безотказной работы этих элементов за определенный промежуток времени, составляет соответственно 0,8 и 0,9.

Узел 2 неисправен при отказе элемента В и вероятность безотказной работы за тот же промежуток его равна 0,8.

Узел 3 состоит из трех элементов Г, Д, Е, и выходит из строя, если неисправен любой из этих элементов. Вероятность их безотказной работы равна соответственно 0,7; 0,8; 0,9. Неисправность любого узла вызывает неисправность всей системы.

Для оценки работы каждого узла используется также таблица случайных величин.

Для запуска испытаний необходимо взять число из таблицы случайных чисел и сравнить его величину с пороговым значением, при котором происходит отказ элемента. Если выбранное значение превосходит пороговое, то отмечают отказ, в противном случае элемент исправен. После определения отказа, либо исправности элемента определяют состояние узла, а затем системы. Результат испытаний приведен в таблице 7.2.

Таблица 7.2

Номер реализации	Реализация	Результат для узла 1	Реали-зация	Результат для узла 2	Реализация	Результат для узла 3	Общий результат
	А	Б		В		Г	Д	Е
1	0,66	0,15	И	0,54	И	0,25	0,02	0,85	И	И
2	0,18	0,18	И	0,80	Н	0,59	0,89	0,68	Н	Н
3	0,83	0,33	И	0,46	И	0,27	0,25	0,68	И	И
4	0,03	0,17	И	0,45	И	0,86	0,33	0,81	Н	Н
5	0,32	0,66	И	0,43	И	0,49	0,92	0,92	Н	Н
6	0,38	0,96	И	0,78	И	0,93	0,42	0,42	Н	Н
7	0,41	0,68	И	0,39	И	0,35	0,66	0,66	И	И
8	0,75	0,12	И	0,02	И	0,45	0,20	0,20	И	И
9	0,29	0,45	И	0,65	И	0,58	0,88	0,88	Н	Н
10	0,53	0,31	И	0,81	Н	0,67	0,24	0,24	И	Н
11	0,75	0,89	И	0,79	И	0,13	0,02	0,57	И	Н

Разделив количество исправных состояний на общее количество реализации, получим, что вероятность такой системы быть в исправном состоянии составляет 4 / 11 = 0,36.

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

9.2 Схема использования метода Монте-Карло при исследовании систем со случайными параметрами

Построив модель системы массового обслуживания, на ее вход подают входные сигналы от генератора случайных чисел (ГСЧ). ГСЧ устроен так, что он выдает равномерно распределенные случайные числа из интервала от 0 до 1. Так как определенные события более вероятны, другие - менее, то равномерно случайные числа от генератора подают на датчик (ДСЧ), который преобразует их в заданный закон распределения вероятности. Далее модель отрабатывает входной сигнал и получает выходной, который является вероятностным событием. Если процедуру повторять многократно, то на выходе появится массив случайных чисел, который формируется в блоке накопления статистики (НС). Далее исследуют вероятностное распределение выходного сигнала в блоке расчета статистических показателей (РСП) и делают заключение о свойствах объекта, который моделируют. В блоке НС анализируют степень достоверности результата и определяют необходимое для этого количество статистических испытаний. При малом числе испытаний результат может оказаться недостоверным.

Например, событие А совершилось в результате проведенных двухсот экспериментов 50 раз. Это означает согласно методу Монте-Карло, что вероятность совершения события равна

Вероятность того, что событие не совершится, равна соответственно 1 - 0,25 = 0,75. Оценка вероятностей производиться по следующей формуле:

9.3 Генератор случайных чисел (ГСЧ)

Основа метода Монте-Карло - ГСЧ, равномерно распределенных в интервале (0, 1). Такая последовательность чисел должна обладать математическим ожиданием и дисперсией.

.

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

ГСЧ рр(а, b)

Пример:

Теперь x - случайное число, равномерно распределенное в диапазоне от a до b. ГСЧ порождает случайный поток событий с равномерным законом распределения. При одном обращении выпадает одно случайное число.

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

Следует запомнить, что генерация произвольного случайного числа состоит из двух этапов:

1. Генерация нормализованного случайного числа (равномерно распределенного от 0 до I);

2. Преобразование случайного числа в произвольный закон распределения.

ГСЧ делятся на:

- физические;

- табличные;

- алгоритмические.

Физические ГСЧ:

- монета («орел» - 1, «решка» - 0):

- игральные кости.

- разделенный на сектора вращающийся барабан со стрелкой.

- аппаратурный генератор шума (ГШ). В качестве ГШ используют шумящее тепловое устройство, например транзистор.

Табличные ГСЧ

	0 ? r ? 1
7	1	8	0	0,718
3	4	6	0	0,346
6	4	1	2	0,641
…	…
Случайные цифры	Случайные числа, равномерно распределенные от 0 до 1

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

Недостатки метода: для хранения большого количества цифр требуется много памяти.

Алгоритмические ГСЧ

Эти числа всегда квазислучайные (то есть следующее сгенерированное число зависит от предыдущего)

Достоинства данных ГСЧ: компактны, быстродействующие, не требуют ресурсов памяти. Имеется несколько алгоритмических методов получения ГСЧ.

9.4 Метод серединных квадратов

Имеется четырехзначное число. Возводим его в квадрат. Из а1 берется середина и записывается в а0, далее процедура повторяется.

Недостатки:

Если на очередной итерации получится ноль, то датчик вырождается.

Для качества генератора важно -- какое взято начальное значение.

Датчик будет повторять последовательность через 2n шагов (24 для нашего случая).

9.5 Метод серединных произведений

Умножая а0 на а1, из полученного результата берем середину, и умножаем ее на а1 и так далее.

9.6 Проверка качества работы датчика ГСЧ

От качества работы ГСЧ зависит качество работы всей системы и точность результатов. Поэтому случайную последовательность, порождаемую ГСЧ, требуется проверять целым рядом тестов.

1. Проверки на равномерность распределения

- ГСЧ должен выдавать значение статистических параметров близко к следующим:

(математическое ожидание)

(дисперсия)

(среднеквадратичное отклонение)

- частотный тест (выясняет, сколько чисел попало в интервал)

т. е. 58% должно попадать в интервал ,  - сколько чисел попало в интервал от 0 до 0,5, столько же и в интервал от 0,5 до 1.

- проверка по критерию ч2

Рис. 7.5

где f(r) - плотность вероятности; n1 - число точек, попавших в i-ый интервал; Pi - теоретическая вероятность попадания чисел в i-ый интервал.

,

,

,

Процедура проверки:

1. Запускают ГСЧ (N раз).

2. Разбивают диапазон от 0 до 1 на k интервалов.

3. Определяют количество случайных чисел, попавших в каждый интервал ni , i=(1чk).

Лекция № 10. РЕГРЕССИЯ И ОСОБЕННОСТИ ЕЕ ИСПОЛЬЗОВАНИЯ ПРИ МОДЕЛИРОВАНИИ

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

В этом разделе мы изучим некоторые особенности работы с уравнениями регрессии, на которые студенты меньше всего обращают внимание.

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

.

Широкому применению МНК способствует достаточно легкий (по сравнению с другими способами) аппарат расчета параметров регрессии. Наряду с МНК существуют и другие методы, позволяющие получить оценки параметров уравнений регрессии. Среди них наиболее известны метод наименьших модулей и метод минимакса (Чебышевское оценивание).

По первому методу необходимо чтобы параметры регрессионного уравнения были найдены из соотношения минимизации суммы абсолютных отклонений:

.

По второму - из требования минимизация максимального модуля отклонений между измеренными и вычисленными (теоретическими) значениями:

.

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

Например,

.

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

Пусть получено регрессионное уравнение следующего вида:

,

где - время, ч;

- температура, град. Сє.

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

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

Во-вторых, если измерение времени привести не в часах, а в минутах, то уравнение примет вид:

.

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

По степени информированности исследователя об объекте существует деление объектов на три типа «ящиков».

Однако вернемся к примерам построения регрессионной модели. Содержание ящика неизвестно. Задача - построить модель, зная вход и выход, то есть определить характер и взаимосвязь между входом и выходом.

1. Исследователь вносит гипотезу о структуре «ящика».

Рассматривая экспериментально полученные данные, предполагает, что они подчиняются линейной гипотезе, то есть выход (у) зависит от входа (х) линейно. Тогда:

2. Определим неизвестные коэффициенты модели А0 и A1.

a) Линейная одномерная модель:

Ошибка между теоретическим значением функции и экспериментальным значением yi-той точки:

Где i изменяется от 1 до n и соответствует экспериментально полученным точкам.

Исходя из МНК, ошибки всех точек следует сложить, и получим суммарную ошибку

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

Таким образом, F -- суммарная ошибка является функцией двух переменных А0 и A1. Очевидно, что ее можно минимизировать за счет подбора коэффициентов А0 и A1.

Для нахождения минимума функции F по ее переменным найдем производные по неизвестным А0 и A1 и приравняем их нулю.

Получим систему из двух уравнений с двумя неизвестным А0 и A1.

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

3. Следующий этап -- проверка.

Чтобы определить, принимается гипотеза или нет, нужно рассчитать ошибку между теоретической и экспериментальной зависимостями.

Как мы уже знаем исходя из нормального закона распределения случайных величин, найдем значение у по формуле:

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

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

б) Множественная линейная модель.

Предположим, что «ящик» линеен, но количество входных сигналов, действующих одновременно, равно n. Всего имеется информация по m измеренным точкам для каждого х и y.

Так как мы имеем экспериментальные данные обо всех входах и выходах черного «Ящика», то можно вычислить ошибку между теоретическим значением y и экспериментальным для i точки:

,

тогда суммарная ошибка будет

Ошибку минимизируем. Ошибка зависит от выбора параметров А0, А1, …Аn. Для нахождения экстремума приравняем все частные производные F по неизвестным А0, А1, …Аn к нулю:

Получим систему из (n +1) неизвестной, которую следует решить для определения А0, А1, …Аn.

Дальше вычисляется ошибка и находится «у» и определяются границы достоверных интервалов по аналогии с одномерной моделью.

К линейной множественной модели приводятся многие нелинейные модели подстановками и переобозначениями.

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

,

которое после логарифмирования можно записать так:

заменяя переменные, , где , .

Рассмотрим еще один пример.

Уравнение вида с помощью

; ;;

можно преобразовать в линейное уравнение:

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

В этом случае линеаризацию можно провести путем разложения данного уравнения в ряд Тейлора.

К требованиям, которые предъявляют к оценкам параметров регрессионного уравнения относятся требования, о получении несмешанных оценок, т.е. таких, при которых их выборочная (вычисленная) оценка будет максимально близкой к истинной. Однако, линеаризация не всегда позволяет получать такие оценки. Рассмотрим ранее линеаризованные уравнения:

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

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

10.1 Динамическая модель и ее характеристика

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

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

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

- определить число степеней свободы;

- отобразить инерционные свойства системы массами или моментами инерции, которые необходимо сосредоточить в определенных точках;

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

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

Одномассовая динамическая модель описываемая уравнением

,

где первое слагаемое - инерционные силы;

второе слагаемое - силы внутреннего сопротивления;

третье слагаемое - силы упругости;

Fj - внешние силы; n - число этих сил.

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

Для математического описания динамической модели необходимо:

- выбрать точки сосредоточения масс или моментов инерции;

- привести к этим точкам массы и силы инерции;

- привести упругодиссипативные связи в механизме к безинерционным связям между инерционными элементами системы;

- определить число и направление обобщенных координат;

- составить уравнения движения с учётом связей, ограничивающих функционирование механизма;

- представить уравнения Лагранжа в виде, возможном и удобном для математического разрешения.

С этой целью систему надо представить в виде либо голономной, либо неголономной и в зависимости от этого использовать тот или иной математический аппарат.

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

Лекция № 11. КОДИРОВАНИЕ ИЗОБРАЗИТЕЛЬНОЙ ИНФОРМАЦИИ

11.1 Дискретизация и квантование изображений

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

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

Этот сигнал восстанавливается с помощью следующего ряда:

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

- спектр оптических изображений должен быть ограничен частотами щвmax и щбmax

- шаг дискретизации должен приниматься не меньшим

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

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

(1)

Аналогичный вид имеет и матрица переходов от одного пикселя к другому по кадру:

(2)

Матрицы переходов от одного пикселя к другому характеризуют собой дискретный Марковский процесс перехода от оптической плотности одного пикселя к оптической плотности другого. Этот дискретный процесс является аналогом одномерной плотности распределения



Корреляционную матрицу изображения можно представить в виде произведения матриц переходов по строкам и по кадру.

Коэффициент корреляции между пикселями по диагонали в этом случае будет равен произведению . Непосредственные расчеты при обработке дискретной информации показывают, что представление матриц и в виде (1) и (2) является достаточно точным при расстоянии между элементами изображения до 5 пикселов.

11.2 Общие принципы кодирования изображений

При квантовании и дискретизации изображений в ЭВМ вводится первичное кодовое описание. Количество информации в этом описании определяется размерами изображения, линиатурой (размерами пикселов) и числом градаций оптической плотности. Первичное описание изображений связано с использованием растровых форматов изображения. Под форматом понимается размещение данных изображений на машинном носителе, в котором зафиксированы координаты каждого пиксела и его оптическая плотность. На размер файла в этом случае влияют число пикселов в изображении и число разрядов. При описании цветных изображений иногда используется до 24 и 32 разрядов на один пиксел. Это означает, что изображение размером 1024х768 пикселов требует размеров файлов до 3,0 Мбайт. Даже файлы черно-белых изображений при том же числе пикселов и числе градаций оптической плотности, равной 256 и требующей 8 разрядов для описания каждого пиксела, должны иметь объем 768 Кбайт.

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

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

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

Наиболее простым методом сжатия данных является учет неравновероятности градации оптической плотности в изображении, знакоизбыточность, вносимая при пренебрежении неравновероятности оптических плотностей пикселов, невелика и сократить объем памяти ЭВМ можно не более, чем в 1,5 раза.

Более существенного сокращения объема памяти ЭВМ можно достигнуть с учетом корреляции между значениями оптической плотности соседних пикселов. Если ввести в рассмотрение условную вероятность Р(i|j) того, что отсчет оптической плотности имеет значение i при условии наличия отсчета j в соседнем пикселе, то условная энтропия будет

,

где - вероятность того, что отсчеты оптической плотности в соседних пикселах равны i и j.

В соответствии с вышеприведенной формулой найдем энтропию двух событий i и j:

(1)

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

(2)

Исходя из свойств энтропии, взаимосвязанных событий, найденная по формуле (1) энтропия меньше энтропии, найденной по формуле (2). А это говорит об уменьшении количества информации в отсчетах с коррелированными значениями оптической плотности.

Важнейшей характеристикой метода сжатия визуальных данных является точность восстановления изображения. Если обозначить f(i,j) -- первичное кодовое описание изображения, a g(i,j) - вторичное описание после сжатия данных, то дисперсия отклонения функции g(i,j) от функции f(i,j) будет

(3)

Это отклонение является помехой, поэтому отношение сигнал/ шум выходного изображения определяется

(4)

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

11.3 Методы кодирования тоновых изображений

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

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

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

Методика построения тонового кода состоит в следующем. Определяются условные вероятности Р(i|j), где j - оптическая плотность предыдущего элемента. Затем для каждого значения j строится свой эффективный код для последующего элемента. Это означает, что при одной и той же оптической плотности последующего элемента его кодовая комбинация будет различной и зависимости от оптической плотности предыдущего элемента.

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

Лекция № 12. Кодирование с образованием блоков

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

Математическое ожидание и дисперсия определяются формулами

х - оптическая плотность.

Обычно блоки принимают размерами 4x4 пикселов. Для каждого пиксела информация в один бит обозначает, находится ли уровень оптической плотности пиксела выше или ниже среднего. Значения m и D вычисляются в отдельности для каждого блока.

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

,

где n1 и n2 - число пикселов в блоке, оптическая плотность которых выше или ниже значения mx. Пикселы, закодированные единицами, приравниваются к значению x1, а закодированные нулями -- к х0.

Достоинством этого метода кодирования является его простота, а также значительное сжатие данных в процессе кодирования изображений.

12.1 Кодирование с предсказанием отсчетов

Кодирование с предсказанием основано на том, что каждый отсчет оптической плотности xi можно предсказать на основе анализа нескольких предыдущих отсчетов, xi-1, xi-2, xi-3… Этот принцип базируется на проанализированной известной вам взаимозависимости корреляции между оптическими плотностями соседних пикселов.

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

Эта функция зависит не только от координат бi (номера пиксела), но и от некоторых параметров а. b. с,...:

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

Из этого условия можно найти или подобрать параметры a, b и с.

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

11.2 Кодирование штриховых изображений

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

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

Кодирование длинами серий.

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

Эффективное кодирование длинами серий возможно при знании плотности распределения этих длин. Если 10 - длины нулевых серий, a l1 - длины единичных серий, то энтропия их будет



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

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

Если кодовое слово содержит m разрядов, то с его помощью можно закодировать N отсчетов. При этом должно выполняться условие n ? 2m .

Для определения коэффициента сжатия информации представим, что появление нулей и единиц в строке представляет собой марковский процесс с переходными вероятностями взаимосвязи событий Р(i| j):

Средние длины серий будут равны

При длине кодового слова, равном m , коэффициент сжатия данных равен:

Расчеты показывают, что этот коэффициент обычно находится в пределах от 3 до 5.

Кодирование блоками

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

Анализ штриховых изображений показывает, что наиболее вероятными в них являются светлые пикселы. Для кодирования таких изображений целесообразно применять метод кодирования с пропуском белого. Если вероятность того, что блок размером lгхlb пикселов состоит только из нулевых элементов Р(0;lг,lb), то средняя длина кодового слова будет

Откуда

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



В этом случае, когда lb=1, блок принадлежит одной строке и код называется одномерным, в противном случае он называется двухмерным. Если ввести ранее принятые в матрице обозначения

, , то вероятность наличия нулей в строке будет

Коэффициент сжатия данных для одномерных кодов изменяется в пределах от 2 до 5 , а для двухмерных - от 4 до 8.

Векторное кодирование

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

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

Метод выделения векторов рассчитан на его применение в процессе сканирования изображения. При этом принадлежность серии пикселов от темных участков чертежа к одному отрезку прямой линии определяется сравнением соседних строк растра. Когда образуется вектор, координаты левой границы серии» на начальной линии сканирования принимаются за координаты начала вектора, а в качестве координат конца вектора принимаются координаты левой границы последней серии. Ширина отрезка прямой линии, представляемая в виде вектора, принимается равной длине серии пикселов.

Уравнение отрезка прямой линии представляется в обычной форме:

где б1, в1; б2, в2- координаты начала и конца отрезка прямой линии, или же в форме

,

где - угловой коэффициент прямой.

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

Кодирование методом аппроксимации

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

При выборе метода аппроксимации к аппроксимирующим функциям может

быть предъявлено одно из следующих требований:

- полное совпадение исходной и аппроксимирующей функций в узловых точках;

- минимальное значение суммы квадратов отклонений в узловых точках;

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

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

Лекция № 13. КОДИРОВАНИЕ ТЕКСТОВОЙ ИНФОРМАЦИИ

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

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

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

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

минимальное время передачи информации;

минимальный объем запоминающего устройства при хранении информации;

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

13.1 Оптимальные системы счисления

Найдем оптимальную систему счисления с использованием критерия минимума элементов, которые служат для определения максимального числа. Пусть k - основание системы счисления, тогда для изображения n-разрядного числа необходимо использовать v=kn элементов. Максимальное число, которое можно представить при системе счисления с основанием k и n разрядах равно:

(1)

Найдём n из выражения (1):

следовательно,

(2)

Определим, при каком значении k получается наименьшее значение v. Для этого продифференцируем выражение (2) получим:

(3)

Приравняем к нулю выражение (3) и найдем

,

где -- основание натурального логарифма.

Следовательно, оптимальной системой счисления будет с основанием .

Однако система счисления с дробным основанием с точки зрения технической реализации неприемлема. Поэтому выбирают основание достаточно близкое к основанию оптимальной системы счисления. При этом увеличение числа элементов для представлений максимального числа будет незначительным (6%).

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

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

Например, 714 запишем 111 001 100 (111=7, 001=1, 100=4).

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

Таблица1

Десятичный код	Двоично-десятичный код	Десятичный код	Двоично-десятичный код
0	0000 0000	6	0000 0110
1	0000 0001	7	0000 0111
2	0000 0010	8	0000 1000
3	0000 0011	9	0000 1001
4	0000 0100	10	0001 0000
5	0000 0101

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

13.2 Основные параметры кодов

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

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

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

Например, для передачи 128 сообщений нужен код длиной При кодировании используются равномерные и неравномерные коды. У равномерных кодов длина всех сообщений - одинакова, а у неравномерных, для разных сообщений -- разная. Примером равномерного кода, является код Бодо (пятиэлементный), а неравномерного -- код Морзе.

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

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

13.3 Способы представления кодов

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

,

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

В десятичной системе счисления , а цифры от 0 до 9. Поэтому, например, число 1245 запишется следующим образом:

.

В двоичной системе счисления , и, В и L Число 10111 в этой системе счисления может быть представлено так:

Одно и то же число может быть записано в различных системах счисления. Например, десятичное число 125 в двоичной системе счисления запишется следующим образом:

.

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

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

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

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

Теоретической базой эффективного кодирования является теорема, доказанная Кл. Шенноном для каналов передач в отсутствие помех (шумов).

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

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

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

Метод построения кода заключается в следующем-

- буквы алфавита выписываются в таблицу в порядке убывания вероятностей ;

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

- всем буквам первой группы в качестве первого символа присваивается 1, а всем буквам второй группы - 0;

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

- всем буквам первой группы присваивается 1, а второй - 0;

- процесс продолжается до тех пор, пока в каждой подгруппе не останется по одной букве.

При эффективном кодировании наибольший эффект получается в том случае, когда вероятности определяются формулой

,

где .

Среднее число символов на букву сообщения в этом случае точно равно энтропии.

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

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

Таблица 2

Буква	Р	Буква	Р	Буква	Р	Буква	Р
Z1	0.22	Z3	0.16	Z5	0.10	Z7	0.04
Z2	0.20	Z4	0.16	Z6	0.10	Z8	0.02

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

Таблица 3

Буква	Вероятность	Кодовые комбинации	Ступени разбиения
Z1	0.22	11____________________________	II
Z2	0.20	101___________________________	III
Z3	0.16	100___________________________	I
Z4	0.16	01____________________________	IV
Z5	0.10	001___________________________	V
Z6	0.10	0001__________________________	VI
Z7	0.04	00001_________________________	VII
Z8	0.02	00000_________________________	VIII

В данном примере первое разбиение делит все буквы на две группы: Z1-Z3, Z4 - Z8. Второе разбиение выполняется для первой группы. Им она делится на две подгруппы: Z1 и Z2 - Z3; третье разделение делит первую группу еще раз: Z2 и Z3 ; четвертое разбиение делит вторую группу на две подгруппы : Z4 и Z5 - Z8; пятое разбиение - на Z5 и Z6 - Z8; шестое -- на Z6 и Z7 - Z8; седьмое -- на Z7 и Z8.

Вычисления:

и среднее число символов:

,

где m - число букв, n - число двоичных символов в коде i-ой буквы дают следующие результаты:

,

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

Среднее число символов на буквучто близко к значению энтропии.

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

Лекция № 14. КОД ХАФФМЕНА

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

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

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

Пример. Задан алфавит из восьми букв: Z1,Z2,Z3,Z4,Z5,Z6,Z7,Z8 с

вероятностями:

соответственно.

Методика выполнения первого этапа иллюстрируется в таблице.

Таблица 4

Буква	Вероятность	Вспомогательные столбцы
		1	2	3	4	5	6	7
Z1	0.22	0.22	0.22	0,26	0,32	0,42	0,58	1
Z2	0.20	0.20	0.20	0,22	0,26	0,32	0,42
Z3	0.16	0.16	0.16	0,20	0,22	0,26
Z4	0.16	0.16	0.16	0,16	0,20
Z5	0.10	0.10	0.16	0,16
Z6	0.10	0.10	0,10
Z7	0.04	0,06
Z8	0.02

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

На третьем этапе по кодовому дереву составляется кодовая комбинация. Двигаясь по кодовому дереву от 1, можно записать для каждой буквы соответствующую ей кодовую комбинацию (смотри таблицу 5). Определяя , получим:

=2 0,22+0,20 2+0,16 3+0,10 3+0,10 4+ 0,04 5+0,04 5+0,02 5 = 0,44+0,4+0,48+0,48+0,03+0,4+0,2+0,1 = 2,8

Метод составления кодового дерева

Таблица 5

Буква	Код	Буква	Код	Буква	Код	Буква	Код
Z1	01	Z3	111	ZS	100	Z7	10101
Z2	00	Z4	110	Z6	1011	Z8	10100

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

Лекция № 15. ПОМЕХОУСТОЙЧИВОЕ КОДИРОВАНИЕ

15.1 Пути совершенствования эффективного кодирования

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

Более рациональным методом разделения знаков является такое построение кода, при котором ни одна комбинация кода не совпадает с началом более длинной комбинации. Такие коды называются префиксными.

Пусть задана последовательность кодов 1000001 101 10 10100, которые имеют вид: x1=00, x2=01, x3=101, x4=100. Эта последовательность декорируется однозначно: x4(100), x1(00), x2(01), x3(101), x3(101), x3(101), x1(00). Таким образом, эта последовательность префиксного кода.

Последовательность 000101010101 комбинаций непрефиксного кода x1=00, x2=01, x3=101, x4=010 может быть декорирована различным способом, так как комбинация 01 является началом комбинации 010.

Коды, полученные по методике Шеннона - Фэно и Хаффмена, удовлетворяют требованиям префиксных кодов.

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

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

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

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

- увеличение мощности передаваемого сигнала с тем, чтобы мощность полезного сигнала значительно превышала мощность помехи;

повторение кодовых комбинаций;

помехоустойчивое кодирование.

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