Расчёт вероятности ошибки линейных систем модуляции на основе диаграмм Вороного



Рис 2.8 Пример выходного файла



3. Реализация алгоритма Форчуна

3.1 Важные детали реализации

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

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

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

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

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

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

Четвёртая проблема связана с появлением «фантомных» рёбер при обработке событий удаления парабол из береговой линии. По сути, эти рёбра были совершенно не нужны в диаграмме - они либо дублировали другие рёбра, либо имели нулевую длину.

3.1.1 Первая версия. Проблема точек разбиения

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

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

Основная проблема появилась во время реализации метода добавления параболы в береговую линию. Добавление парабол осуществляется вызовом метода класса списка List<T>.BinarySearch(Titem, IComparer<T>comparer) [17]. Согласно документации, этот метод возвращает номер элемента, соответствующего переданному элементу в переменной item, с использованием метода IComparer<T>.Compate(Tone, Ttwo) [18], который сравнивает два элемента одно типа и возвращает значение int, описывающее отношение этих элементов. В метод сравнения Compare передаются два элемента: как one передаётся проверяемый элемент из береговой линии, как two - элемент, для которого мы ищем соответствие вызовом метода BinarySearch. Возвращаемая методом Compare переменная может иметь три значения:

1, если объект oneбольше объекта two;

0, если объект oneравен объекту two;

-1, если объект oneменьше объекта two.

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

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

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

3.1.2 Вторая версия. Проблема обработки рёбер

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

Рис. 3.1 Визуализация объекта ребра диаграммы Вороного до изменения. Фрагмент береговой линии и незавершённое ребро

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

Решение данной проблемы было найдено при детальном изучении программного кода реализации алгоритма Стивеном Форчуном. Он использовал для рёбер класс HalfEdge - половинное ребро, суть которого заключается в создании рёбер таким образом, чтобы:

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

Одна точка, задающая ребро, всегда фиксированная, вторая же может подвергаться изменению.

Рис. 3.2Визуализация объекта ребра после изменений. Фрагмент береговой линии и два незавершённых ребра

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

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

3.1.3 Третья версия. Проблема вырожденных парабол

Данная проблема была найдена в процессе модульного тестирования квадратных сеток сайтов. Она связана с обработкой функции получения координат параболы, когда её фокус совпадает с директрисой. В таком случае, парабола вырождается в прямую, перпендикулярную директрисе, и пересекающую её в точке фокуса, так как любые точки, не лежащие на перпендикуляре, будут дальше от фокуса, чем от директрисы. Функция Fx(double) будет не способна вернуть правильное значение и по оси Xфункция будет определена только в одной точке. Проблема заключается в методе поиска параболы под новой параболой в береговой линии - при обработке квадратной сетки, после добавления первой параболы, вставка следующей параболы затруднена. При написании метода поиска параболы предполагалось, что в любой итерации, кроме первой, береговая линия будет определена на всей протяжённости оси абсцисс. Но если в береговую линию была добавлена вторая парабола, фокус которой по координате Yсовпадает с фокусом первой параболы, метод вернёт отрицательное значение, «не найдя новой параболе места». Решением стало добавление механизма учёта вырожденности параболы. Механизм потребовал добавления отдельной переменной для обозначения вырожденности, и обработки этого случая в методе поиска параболы.



3.1.4 Четвёртая версия. Проблема фантомных рёбер

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

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

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

3.2 Интерфейс

Интерфейсная часть программы требует специального форматирования данных. Интерфейс состоит из двух частей: чтение входного файла и форматирование и запись выходного файла.

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

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



4. Тестирование программного обеспечения

4.1 Результаты модульного тестирования

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

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

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

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

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

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

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

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

4.2 Результаты интеграционного тестирования

4.2.1 Тестирование на правильность

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

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



4.2.2 Тестирование на время исполнения

При этом тестировании проверяются две гипотезы:

Время исполнения программы простого алгоритма построения будет больше времени исполнения программы алгоритма Форчуна.

Время исполнения программы простого алгоритма построения будет в раз больше времени исполнения программы алгоритма Форчуна.

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

Во-первых, реализация простого алгоритма написана на другом языке - С. Этот язык достаточно близок к языку C#, но значительно более старый. Следовательно, распространённые компиляторы С могут быть более оптимизированы, чем компиляторы C#, что может вылиться в более быструю работу программы на С, чем на C#, при выполнении одних и тех же действий.

Во-вторых, при реализации алгоритма Форчуна использовались сложные механизмы языка, например, вызовы LINQ-функций. Их реализация в языке C# может отличаться и быть медленнее реализации подобных функций в C, с учётом того, что на этом языке их нужно бы было реализовывать вручную.

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

В итоге проведения тестов, был выбран диапазон значений количества сайтов квадратной сетки от до . Шаг для замеров был выбран равным 10, причём он применялся не прямо к количеству сайтов, а к количеству сайтов в стороне подобной квадратной сетки, с шагом десять. То есть, получился следующий набор входных массивов сайтов:

сторона - , количество сайтов - ;

сторона - , количество сайтов - ;

сторона - , количество сайтов - ;

сторона - , количество сайтов - ;

сторона - , количество сайтов - ;

сторона - , количество сайтов - ;

сторона - , количество сайтов - ;

сторона - , количество сайтов - ;

сторона - , количество сайтов - ;

сторона - , количество сайтов - .

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

Спецификации ПК, на котором были проведены замеры:

ЦПУ: Intel Core i5 4460;

ОЗУ: 12 гигабайт;

Windows 10 Education Edition.

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

Время работы программ

	Простой алгоритм	Алгоритм Форчуна
100	127.00	12436.04
400	835.59	332477.08
900	1692.62	1537989.76
1600	4237.85	6913358.03
2500	9070.00	22350505.66
3600	11314.98	44034431.49
4900	14168.16	72549470.10
6400	17747.94	112480336.74
8100	26102.21	194038360.48
10000	27758.69	287276646.51



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

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

Отношения времени исполнения

100	97.92
400	394.15
900	873.53
1600	1570.66
2500	2467.40
3600	3441.33
4900	4429.27
6400	5884.31
8100	7433.79
10000	9729.67

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

Модуляцию ФМ-4 можно представить в виде дибитов (пара бит информации) двумя способами:

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

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

4.3 Контрольный расчёт вероятности ошибки линейных систем модуляции.

Как контрольный пример, был взят вариант модуляции ФМ-4.

Рис 4.1 Представление ФМ-4: передача символов от «0» до «3».

Рис 4.2 Представление ФМ-4: прямое расположение кодов (а), расположение кодов Грея (б)



Тогда вероятность ошибки на символ при равновероятной передачесимволов равна:

,

где - функция вероятности ошибки,

-квадратурная компонента.

Вероятность ошибки на бит согласно прямому способу представления дибитов:

,

Вероятность ошибки на бит при способе представления согласно коду Грея:

,

Расчётные значения вероятности ошибки равны:

Таблица расчётных значений вероятности ошибки

	0.5	1	2	3	4	5
	0.42202	0.292139	0.151113	0.0815311	0.449825	0.0251866
	0.302145	0.212811	0.111789	0.060715	0.0336075	0.0188498
	0.23975	0.158655	0.0786496	0.0416322	0.02275	0.0126736

При расчёте функции ошибок использована аппроксимация формулы [19 стр. 122 фор. 7.1.26]:



где ,

,

,

,

-0.284496736,

,

,

.

Для функции пересчитан коэффициент , так как в ней другая подынтегральная функция.

,

.

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

,

.

Далее представлен расчёт вероятности ошибки для ФМ-4 при равновероятной передаче символов для 4-х сигнальных позиций.



Рис. 4.1 Основания объёмных фигур для сигнальной позиции (1;0).

а) Относительно сигнальной позиции с координатами (0;1) для расчёта вероятности ошибки на бит;

б) относительно сигнальной позиции с координатами (?1;0) для расчёта вероятности ошибки на бит;

в) относительно сигнальной позиции с координатами (0;??1) для расчёта вероятности ошибки на бит;

г) для расчёта вероятности ошибки на символ.

Вероятность ошибки на бит для прямой последовательности:



Вероятности ошибки на бит для кода Грея:

Вероятность ошибки на символ:

Далее в таблице предоставлен результат численного интегрирования с точностью :

Результат расчёта вероятности ошибки с использованием диаграмм Вороного

	0,5	1	2	3	4	5
	0,028740	0,012586	0,003093	0,000867	0,000259	0,000081
	0,211100	0,146069	0,075557	0,040765	0,022491	0,012593
	0,182270	0,133484	0,072464	0,039899	0,022232	0,012513
	0,057480	0,025172	0,006186	0,001734	0,000518	0,000161
	0,422020	0,292139	0,151113	0,081531	0,044982	0,025186
	0,302145	0,212811	0,111788	0,060715	0,033607	0,018849
	0,239750	0,158655	0,078650	0,041632	0,022750	0,012674

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



Заключение

Цель данной бакалаврской работы была достигнута и преимущество во времени исполнения алгоритма Форчуна было доказано экспериментальным путём.

Задачи данной бакалаврской работы были достигнуты в полной мере: изучен и реализован алгоритм Форчуна, поставлен эксперимент для проверки двух выдвинутых гипотез.

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

Гипотеза о более быстрой работе алгоритма Форчуна в раз (равно количеству сайтов) по сравнению с простым алгоритмом была также подтверждена, несмотря на возможные предпосылки к обратному. Во взятом диапазоне количества сайтов алгоритм Форчуна работает быстрее чуть менее чем в раз.

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



Список использованных источников

1. Диаграмма Вороного [электронный ресурс] : портал Wikipedia. - Режим доступа: https://ru.wikipedia.org/wiki/%D0%94%D0%B8%D0%B0%D0%B3%D1%80%D0%B0%D0%BC%D0%BC%D0%B0_%D0%92%D0%BE%D1%80%D0%BE%D0%BD%D0%BE%D0%B3%D0%BE, свободный. - Статья.

2. Voronoi diagram [electronicresource] : Wikipedia portal. - Access mode: https://en.wikipedia.org/wiki/Voronoi_diagram, free. - Article.

3. Диаграмма Вороного [электронный ресурс] : портал Викиконспекты (университет ИТМО). - Режим доступа: https://neerc.ifmo.ru/wiki/index.php?title=%D0%94%D0%B8%D0%B0%D0%B3%D1%80%D0%B0%D0%BC%D0%BC%D0%B0_%D0%92%D0%BE%D1%80%D0%BE%D0%BD%D0%BE%D0%B3%D0%BE, свободный. - Статья.

4. Delaunay triangulation [electronic resource] : Wikipedia portal. - Access mode: https://en.wikipedia.org/wiki/Delaunay_triangulation, free. - Article.

5. S. Fortune. A sweepline algorithm for Voronoi diagrams. Proceedings of the second annual symposium on Computational geometry.[text] / S. Fortune // Algorithmica (1987) doi:10.1007/BF01840357. ISBN 0-89791-194-6.

6. Fortune's algorithm and implementation [electronic resource] : Algorithms and Stuff. - Access mode: http://blog.ivank.net/fortunes-algorithm-and-implementation.html, free. - Article.

7. Parabola [electronic resource] : Wikipedia portal. - Access mode: https://en.wikipedia.org/wiki/Parabola, free. -- Article.

8. Voronoi Diagram and a Day at the Beach [electronic source] : American Mathematical Society (AMS). - Access mode: http://www.ams.org/samplings/feature-column/fcarc-voronoi, free. - Article.

9. Ф. Препарата, М. Шеймос Вычислительная геометрия: Введение [электронный ресурс]. - М.: Мир, 1989. Стр. 295. - Режим доступа: http://algolist.manual.ru/maths/geom/prsh/, свободный. -- Сканированные изображения учебника.

10. D. Bell The Class Diagram [electronic resource] : IBM developerWorks, UML Basics. - Access mode: https://www.ibm.com/developerworks/rational/library/content/RationalEdge/sep04/bell/, free. - Article.

11. Диаграмма классов [электронный ресурс] : портал Wikipedia. - Режим доступа: https://ru.wikipedia.org/wiki/%D0%94%D0%B8%D0%B0%D0%B3%D1%80%D0%B0%D0%BC%D0%BC%D0%B0_%D0%BA%D0%BB%D0%B0%D1%81%D1%81%D0%BE%D0%B2, свободный. - Статья.

12. Блок-схема [электронный ресурс] : портал Wikipedia. - Режим доступа: https://ru.wikipedia.org/wiki/%D0%91%D0%BB%D0%BE%D0%BA-%D1%81%D1%85%D0%B5%D0%BC%D0%B0, свободный. - Статья.

13. Схемы алгоритмов, программ, данных и систем. Условные обозначения и правила выполнения[Текст] : ГОСТ 19.701-90 ЕСПД.

14. К. Канер , Д. Фолк, Нгуен Енг Кек Тестирование программного обеспечения. Фундаментальные концепции менеджмента бизнес-приложений [текст] -- Киев: ДиаСофт, 2001. -- 544 с. -- ISBN 9667393879.

15. Softwaretesting [electronic resource] : Wikipedia portal. - Access mode: https://en.wikipedia.org/wiki/Software_testing, free. - Article.

16. Square root of 3 [electronic resource] : Wikipedia portal. - Access mode: https://en.wikipedia.org/wiki/Square_root_of_3, free. - Article.

17. Метод List<T>.BinarySearch IComparer?(T,<T>) [элетронныйресурс] : Microsoft Developer Network (MSDN). - Режимдоступа: https://msdn.microsoft.com/ru-ru/library/ftfdbfx6(v=vs.110).aspx, свободный. - Статья.

18. Метод IComparer<T>.Compare T) [?(T,электронныйресурс] : Microsoft Developer Network (MSDN). - Режимдоступа: https://msdn.microsoft.com/ru-ru/library/xh5ks3b3(v=vs.110).aspx, свободный. - Статья.

19. Справочник по специальным функциям с формулами, графиками и математическими таблицами [текст]. - Под редакцией М. Абрамовица и И. Стиган, перевод с английского под редакцией В. А. Диткина и Л. Н. Карамзиной, Москва, «Наука» Главная редакция физико-математической литературы, 1979.



Приложение

Листинг программы алгоритма Форчуна

ЛистингFortune.cs

usingSystem;

usingSystem.Collections.Generic;

usingSystem.Linq;

usingyLibrary.Voronoi.Events;

namespaceyLibrary.Voronoi {

public sealed class Fortune{

private VoronoiDiagram diagram = new VoronoiDiagram();

public VoronoiDiagram Diagram {

get{

if (IsCalculated)

return diagram;

else

return null;

}

}

public bool IsCalculated { get; private set; }

private List<ParabolaArc> beachline = new List<ParabolaArc>();

private double sweepLine;

private int iteration = 0;

private List<HalfEdge> edges = new List<HalfEdge>();

private EventQueue eventQueue;

public Fortune(Point[] SitesAsPoints){

if (SitesAsPoints == null)

throw new ArgumentNullException(nameof(SitesAsPoints));

diagram.Sites = SitesAsPoints.Select((x) => new Site(x)).ToArray();

}

public Fortune(Site[] Sites) {

//There is some really strong need in validating of Site array.

if (Sites == null)

throw new ArgumentNullException(nameof(Sites));

if (Sites.Any(x => x == null))

throw new ArgumentNullException(nameof(Sites));

foreach (Site s in Sites)

if (Sites.Count(x => x.ID == s.ID) > 1)

throw new ArgumentException("There are multiple sites of the same ID.");

diagram.Sites = Sites;

}

public VoronoiDiagram Calculate() {

CalculateDiagram();

diagram.Edges = edges.ToArray();

diagram.IsOptimized = false;

edges = null;

IsCalculated = true;

return Diagram;

}

public VoronoiDiagram Calculate(FortuneOptions Options) {

CalculateDiagram();

diagram.Edges = edges.ToArray();

diagram.IsOptimized = false;

edges = null;

IsCalculated = true;

if (Options.HasFlag(FortuneOptions.Optimize))

VoronoiOptimizer.Optimize(ref diagram);

return Diagram;

}

void CalculateDiagram() {

eventQueue = new EventQueue(diagram.Sites);

while (!eventQueue.IsEmpty()) {

if (eventQueue.Peek() is ArcAppearEvent)

ProcessArcAppear(eventQueue.Dequeue() as ArcAppearEvent);

else if (eventQueue.Peek() is ArcRemoveEvent)

ProcessArcRemove(eventQueue.Dequeue() as ArcRemoveEvent);

iteration++;

}

}

void ProcessArcAppear(ArcAppearEvent arcAddEvent) {

sweepLine = arcAddEvent.Y;

ParabolaArc newArc = new ParabolaArc(arcAddEvent.SiteToAppear, GetIteration, GetSweepLine);

if (beachline.Count == 0) {

beachline.Add(newArc);

return;

}

int currentElementIndex = beachline.BinarySearch(newArc, new BeachlineInsertionComparer(GetLeftNeighbour, GetRightNeighbour));

ParabolaArc currentArc = beachline[currentElementIndex];

RemoveParabolaRemoveEvent(currentArc);

beachline.Insert(currentElementIndex + 1, newArc);

if (newArc.Y != currentArc.Y)

beachline.Insert(currentElementIndex + 2, new ParabolaArc(currentArc.Site, GetIteration, GetSweepLine));

Point[] newEdgesStartPoint = ParabolaArc.FindCrosspoints(newArc, currentArc);

edges.Add(new HalfEdge(newEdgesStartPoint[0], currentArc.Site, newArc.Site));

edges.Add(new HalfEdge(newEdgesStartPoint[0], newArc.Site, currentArc.Site));

CheckForRemoveEvent(GetLeftNeighbour(newArc));

CheckForRemoveEvent(GetRightNeighbour(newArc));

}

void ProcessArcRemove(ArcRemoveEvent arcRemoveEvent) {

sweepLine = arcRemoveEvent.Y;

ParabolaArc leftArc = GetLeftNeighbour(arcRemoveEvent.ArcToRemove),

rightArc = GetRightNeighbour(arcRemoveEvent.ArcToRemove);

RemoveParabolaRemoveEvent(leftArc);

RemoveParabolaRemoveEvent(rightArc);

HalfEdge leftEdge = edges.Find(x => x.LeftSite.Equals(leftArc.Site) && x.RightSite.Equals(arcRemoveEvent.ArcToRemove.Site)),

rightEdge = edges.Find(x => x.LeftSite.Equals(arcRemoveEvent.ArcToRemove.Site) && x.RightSite.Equals(rightArc.Site));

leftEdge.CloseEdge(arcRemoveEvent.VoronoiVertex);

rightEdge.CloseEdge(arcRemoveEvent.VoronoiVertex);

if (Point.Distance(leftEdge.A, leftEdge.B) == 0)

edges.Remove(leftEdge);

if (Point.Distance(rightEdge.A, rightEdge.B) == 0)

edges.Remove(rightEdge);

edges.Add(new HalfEdge(arcRemoveEvent.VoronoiVertex, leftArc.Site, rightArc.Site));

beachline.Remove(arcRemoveEvent.ArcToRemove);

CheckForRemoveEvent(leftArc);

CheckForRemoveEvent(rightArc);

}

void CheckForRemoveEvent(ParabolaArc arc) {

if (arc == null)

return;

ParabolaArc leftArc = GetLeftNeighbour(arc),

rightArc = GetRightNeighbour(arc);

if (leftArc == null || rightArc == null || leftArc.Site.Equals(rightArc.Site))

return;

HalfEdge leftEdge = edges.Find(x => x.LeftSite.Equals(leftArc.Site) && x.RightSite.Equals(arc.Site)),

rightEdge = edges.Find(x => x.LeftSite.Equals(arc.Site) && x.RightSite.Equals(rightArc.Site));

Point voronoiVertex = HalfEdge.Crosspoint(leftEdge, rightEdge);

if (voronoiVertex.IsNull) return;

double vertexCircleRadius = Point.Distance(voronoiVertex, arc);

if (voronoiVertex.Y + vertexCircleRadius < sweepLine) return;

voronoiVertex.Y += vertexCircleRadius;

ArcRemoveEvent removeEvent = new ArcRemoveEvent(arc, voronoiVertex, vertexCircleRadius);

eventQueue.Add(removeEvent);

}

public void Clear() {

iteration = 0;

sweepLine = 0;

IsCalculated = false;

diagram.Clear();

}

public double GetSweepLine() => sweepLine;

public int GetIteration() => iteration;

public ParabolaArc GetLeftNeighbour(ParabolaArc Element) {

int index = beachline.IndexOf(Element);

if (index == -1 || index == 0) return null;

else return beachline[index - 1];

}

public ParabolaArc GetRightNeighbour(ParabolaArc Element) {

int index = beachline.IndexOf(Element);

if (index == -1 || index == beachline.Count - 1) return null;

else return beachline[index + 1];

}

void RemoveParabolaRemoveEvent(ParabolaArc Arc) {

eventQueue.RemoveAll(x => {

if (x is ArcRemoveEvent)

{

ArcRemoveEvent e = x as ArcRemoveEvent;

return e.ArcToRemove.Equals(Arc);

}

else return false;});

}

}

}

ЛистингVoronoiDiagram.cs

using System;

namespace yLibrary.Voronoi{

public class VoronoiDiagram {

public Site[] Sites { get; internal set; }

public Edge[] Edges { get; internal set; }

public bool IsOptimized { get; internal set; }

public VoronoiDiagram(Site[] sites){ Sites = sites; }

internal void Clear() { Edges = null; }

[Serializable]

public class VDiagramStructureException : Exception {

public VDiagramStructureException(string message) : base(message)

{ }

}

}

}

ЛистингSite.cs

using System;

namespace yLibrary.Voronoi{

public class Site : IPoint, IEquatable<Site> {

private static int IDCounter = 0;

public int ID { get; } = IDCounter++;

public Point Position { get; }

public double X => Position.X;

public double Y => Position.Y;

public Site(double X, double Y) {

Position = new Point(X, Y);

}

public Site(Point Position) {

this.Position = Position;

}

public override bool Equals(object obj) {

if (obj is Site) return Equals(obj as Site);

else return false;

}

public bool Equals(Site other) => other.X == X && other.Y == Y;

public override int GetHashCode() => Position.GetHashCode() ^ ID.GetHashCode();

public override string ToString() => string.Format("ID:{0} ({1};{2})", ID, X, Y);

}

}

ЛистингEdge.cs

namespace yLibrary.Voronoi {

public abstract class Edge {

protected Point a, b;

public Point A => a;

public Point B => b;

public Site LeftSite { get; protected set; }

public Site RightSite { get; protected set; }

public override int GetHashCode() => LeftSite.GetHashCode() ^ RightSite.GetHashCode();

}

}

ЛистингHalfEdge.cs

using System;

namespace yLibrary.Voronoi {

public sealed class HalfEdge : Edge, IEquatable<HalfEdge> {

public Point DirectionPointA => new Point((LeftSite.X + RightSite.X) / 2d, (LeftSite.Y + RightSite.Y) / 2d);

public Point DirectionPointB => new Point(DirectionPointA.X + (LeftSite.Y - RightSite.Y) / 10d, DirectionPointA.Y - (LeftSite.X - RightSite.X) / 10d);

private bool infinite = true;

internal bool infiniteChange { get { return infinite; } set { infinite = value; } }

public bool IsInfinite => infinite;

public Point Vector => new Point((LeftSite.Y - RightSite.Y) / 10d, (LeftSite.X - RightSite.X) / -10d);

public HalfEdge(Point StartPoint, Site LeftSite, Site RightSite) {

this.LeftSite = LeftSite;

this.RightSite = RightSite;

a = StartPoint;

b = a + Vector;

}

public void CloseEdge(Point End) {

b = End;

infinite = false;

}

public bool HasPoint(Point Point) {

Point direction = new Point(Math.Sign(Vector.X), Math.Sign(Vector.Y));

if (infinite &&

((direction.X > 0 && a.X <= Point.X) ^

(direction.X < 0 && a.X >= Point.X) ^

(direction.X == 0 && a.X == Point.X)) &&

((direction.Y > 0 && a.Y <= Point.Y) ^

(direction.Y < 0 && a.Y >= Point.Y) ^

(direction.Y == 0 && a.Y == Point.Y)))

return true;

else return false;

}

public static Point Crosspoint(HalfEdge first, HalfEdge second) {

if (first == null || second == null || !first.infinite || !second.infinite)

return Point.NullPoint;

double[] x = { first.DirectionPointA.X, first.DirectionPointB.X, second.DirectionPointA.X, second.DirectionPointB.X },

y = { first.DirectionPointA.Y, first.DirectionPointB.Y, second.DirectionPointA.Y, second.DirectionPointB.Y };

double denominator = (x[0] - x[1]) * (y[2] - y[3]) - (y[0] - y[1]) * (x[2] - x[3]);

if (denominator == 0)

return new Point(double.NaN, double.NaN);

Point crosspoint = new Point(((x[0] * y[1] - y[0] * x[1]) * (x[2] - x[3]) - (x[0] - x[1]) * (x[2] * y[3] - y[2] * x[3])) / denominator,

((x[0] * y[1] - y[0] * x[1]) * (y[2] - y[3]) - (y[0] - y[1]) * (x[2] * y[3] - y[2] * x[3])) / denominator);

if (first.HasPoint(crosspoint) && second.HasPoint(crosspoint)) return crosspoint;

else return Point.NullPoint;

}

public override bool Equals(object obj) {

if (obj is HalfEdge) return Equals(obj as HalfEdge);

else return false;

}

public bool Equals(HalfEdge other) => other.LeftSite.ID == LeftSite.ID && other.RightSite.ID == RightSite.ID;

public override string ToString() => string.Format("ID {0}:{1} A({2};{3}) B({4};{5}) {6}", LeftSite?.ID, RightSite?.ID, a.X.ToString("G"), a.Y.ToString("G"), b.X.ToString("G"), b.Y.ToString("G"), infinite ? double.PositiveInfinity.ToString() : "");

public FullEdge ToFullEdge() => new FullEdge(a, b, LeftSite, RightSite, false, infinite);

}

}

ЛистингBeachlineElement.cs

using System;

namespace yLibrary.Voronoi {

public abstract class BeachlineElement {

private static int IDCount = 0;

private int IDnum;

public int ID => IDnum;

protected int lastCalcIteration = -1;

protected Func<int> GetCurrentIteration;

public BeachlineElement() {

IDnum = IDCount++;

}

public override string ToString() => "ID:" + ID;

}

}

ЛистингBeachlineInsertionComparer.cs

using System;

using System.Collections.Generic;

namespace yLibrary.Voronoi {

public class BeachlineInsertionComparer : IComparer<ParabolaArc> {

public const int TO_RIGHT = -1, TO_LEFT = 1, STOP = 0;

public Func<ParabolaArc, ParabolaArc> GetLeftNeighbour, GetRightNeighbour;

public BeachlineInsertionComparer(Func<ParabolaArc, ParabolaArc> GetLeftNeighbour, Func<ParabolaArc, ParabolaArc> GetRightNeighbour) {

this.GetLeftNeighbour = GetLeftNeighbour;

this.GetRightNeighbour = GetRightNeighbour;

}

public int Compare(ParabolaArc currentArc, ParabolaArc newArc) {

ParabolaArc left = GetLeftNeighbour(currentArc),

right = GetRightNeighbour(currentArc);

if (currentArc.Y == newArc.Y && right == null) return STOP;

if (left != null) {

Point[] leftBreakpoint = ParabolaArc.FindCrosspoints(left, currentArc);

if (leftBreakpoint.Length == 2)

if (leftBreakpoint[0].X > left.X && leftBreakpoint[0].X < currentArc.X)

leftBreakpoint = new Point[] { leftBreakpoint[0] };

else leftBreakpoint = new Point[] { leftBreakpoint[1] };

if (newArc.X < leftBreakpoint[0].X) return TO_LEFT;

}

if (right != null) {

Point[] rightBreakpoint = ParabolaArc.FindCrosspoints(currentArc, right);

if (rightBreakpoint.Length == 2)

if (rightBreakpoint[0].X < right.X && rightBreakpoint[0].X > currentArc.X)

rightBreakpoint = new Point[] { rightBreakpoint[0] };

else rightBreakpoint = new Point[] { rightBreakpoint[1] };

if (newArc.X > rightBreakpoint[0].X) return TO_RIGHT;

}

return STOP;

}

}

}

ЛистингParabolaArc.cs

using System;

namespace yLibrary.Voronoi {

public class ParabolaArc : BeachlineElement, IPoint, IEquatable<ParabolaArc> {

private bool IsDegenerated = true;

private double degenX;

public Site Site { get; }

public Point Focus => Site.Position;

public double X => Site.Position.X;

public double Y => Site.Position.Y;

protected Func<double> GetDirectrix;

private double a = 0d;

public double A {

get {

if (lastCalcIteration != GetCurrentIteration()) Recalculate();

return a;

}

}

private double b = 0d;

public double B {

get {

if (lastCalcIteration != GetCurrentIteration()) Recalculate();

return b;

}

}

private double c = 0d;

public double C {

get {

if (lastCalcIteration != GetCurrentIteration()) Recalculate();

return c;

}

}

public ParabolaArc(Site Site, Func<int> GetCurrentIteration, Func<double> GetDirectrix) : base() {

this.Site = Site;

this.GetCurrentIteration = GetCurrentIteration;

this.GetDirectrix = GetDirectrix;

Recalculate();

}

public double Fx(double X) => IsDegenerated ? (X == degenX ? double.PositiveInfinity : double.NaN) : A * Math.Pow(X, 2d) + B * X + C;

public static Point[] FindCrosspoints(ParabolaArc First, ParabolaArc Second) {

if (First == null || Second == null)

return new Point[0];

Point[] points;

double A = First.A - Second.A,

B = First.B - Second.B,

C = First.C - Second.C;

if(First.IsDegenerated || Second.IsDegenerated) {

if (First.IsDegenerated && Second.IsDegenerated)

return new Point[] { new Point((First.Focus.X + Second.Focus.X) / 2, First.Focus.Y) };

else {

points = new Point[1];

points[0] = First.IsDegenerated ? new Point(First.degenX, Second.Fx(First.degenX)) :

new Point(Second.degenX, First.Fx(Second.degenX));

return points;

}

}

if (A != 0) {

double discriminantRoot = Math.Sqrt(Math.Pow(B, 2d) - 4d * A * C);

if (discriminantRoot > 0d) {

points = new Point[2];

points[0].X = (-B + discriminantRoot) / 2d / A;

points[0].Y = First.Fx(points[0].X);

points[1].X = (-B - discriminantRoot) / 2d / A;

points[1].Y = First.Fx(points[1].X);

}

else if (discriminantRoot == 0d){

points = new Point[1];

points[0].X = -B / 2d / A;

points[0].Y = First.Fx(points[0].X);

}

else points = new Point[0];

}

else if (B != 0) points = new Point[] { new Point(-C / B, First.Fx(-C / B)) };

else throw new SameParabolaException(First, Second);

return points;

}

public void Recalculate(){

if (GetDirectrix == null)

throw new ArgumentException("GetDirectrix delegate is null, unable to calculate.");

double k = GetDirectrix(),

bMinusK = Site.Position.Y - k;

if (bMinusK == 0) degenX = Site.Position.X;

else {

IsDegenerated = false;

a = 0.5d / bMinusK;

b = -Site.Position.X / bMinusK;

c = 0.5d * (Math.Pow(Site.Position.X, 2d) / bMinusK + Site.Position.Y + k);

}

lastCalcIteration = GetCurrentIteration();

}

public override bool Equals(object obj) {

if (obj is ParabolaArc) return Equals(obj as ParabolaArc);

else return false;

}

public bool Equals(ParabolaArc other) => ID == other.ID;

public override int GetHashCode() => Site.GetHashCode() ^ 1176;

public override string ToString() => base.ToString() + string.Format(" SID {0} f(x) = {1} * x^2 + {2} * x + {3}", Site.ID, A, B, C);

[Serializable]

public class SameParabolaException : Exception{

private int ID1, ID2;

public new string Message { get; }

public SameParabolaException(ParabolaArc First, ParabolaArc Second) : base(){

ID1 = First.ID; ID2 = Second.ID;

Message = base.Message + string.Format("Impossible to find crosspoints of parabolas ID:{0} and ID:{1} as they are have the same graphics.", ID1, ID2);

}

}

}

}

ЛистингArcAppearEvent.cs

namespace yLibrary.Voronoi.Events {

public sealed class ArcAppearEvent : FortuneEvent {

public Site SiteToAppear { get; }

public ArcAppearEvent(Site Site) {

SiteToAppear = Site;

Position = SiteToAppear.Position;

}

public bool Equals(ArcAppearEvent other) => SiteToAppear.ID == other.SiteToAppear.ID;

}

}

ЛистингArcRemoveEvent.cs

namespace yLibrary.Voronoi.Eventsn {

public sealed class ArcRemoveEvent : FortuneEvent {

public double CircleRadius { get; }

public Point VoronoiVertex => new Point(X, Y - CircleRadius);

public ParabolaArc ArcToRemove { get; }

public ArcRemoveEvent(ParabolaArc ArcToRemove, Point Position, double CircleRadius) {

this.CircleRadius = CircleRadius;

this.ArcToRemove = ArcToRemove;

base.Position = Position;

}

public bool Equals(ArcRemoveEvent other) => ArcToRemove.ID == other.ArcToRemove.ID &&

VoronoiVertex.Equals(other.VoronoiVertex);

}

}

ЛистингEventQueue.cs

using System;

using System.Collections;

using System.Collections.Generic;

using System.Linq;

namespace yLibrary.Voronoi.Events {

public class EventQueue : IEnumerable {

private List<FortuneEvent> listOfEvents = new List<FortuneEvent>();

internal List<FortuneEvent> Events {

get { return listOfEvents; }

set { listOfEvents = value; }

}

public FortuneEvent this[int index] => listOfEvents[index];

public EventQueue() { }

public EventQueue(Site[] Sites) {

foreach (Site s in Sites) Add(new ArcAppearEvent(s));

}

public override bool Equals(object obj) {

if (obj.GetType() == typeof(EventQueue))

return listOfEvents.SequenceEqual(((EventQueue)obj).listOfEvents);

else return false;

}

public override int GetHashCode() => listOfEvents.GetHashCode() ^ 123464;

public void Add(FortuneEvent Item) {

if (listOfEvents.Count == 0) listOfEvents.Add(Item);

else if (listOfEvents[0].CompareTo(Item) == 1) listOfEvents.Insert(0, Item);

else if (listOfEvents.Last().CompareTo(Item) == -1) listOfEvents.Add(Item);

else {

for (int i = 0; i < Events.Count - 1; i++)

if (Events[i].CompareTo(Item) != Events[i + 1].CompareTo(Item)) {

Events.Insert(i + 1, Item);

return;

}

listOfEvents.Add(Item);

}

}

public void Enqueue(FortuneEvent Item) => Events.Add(Item);

public FortuneEvent Dequeue() {

FortuneEvent Item = Events.First();

Events.Remove(Item);

return Item;

}

public FortuneEvent Peek() => Events.First();

public int RemoveAll(Predicate<FortuneEvent> predicate) => listOfEvents.RemoveAll(predicate);

public bool IsEmpty() => listOfEvents.Count == 0;

public IEnumerator GetEnumerator() => listOfEvents.GetEnumerator();

}

}

ЛистингFortuneEvent.cs

using System;

namespace yLibrary.Voronoi.Events {

public abstract class FortuneEvent : IComparable, IPoint {

public Point Position { get; protected set; }

public double X => Position.X;

public double Y => Position.Y;

public int CompareTo(object obj) {

if (obj is FortuneEvent) {

FortuneEvent anotherEvent = (FortuneEvent)obj;

if (Position.Y > anotherEvent.Position.Y) return 1;

else if (Position.Y < anotherEvent.Position.Y) return -1;

else if (Position.X > anotherEvent.Position.X) return 1;

else if (Position.X < anotherEvent.Position.X) return -1;

else if (GetType() != anotherEvent.GetType()) {

if (anotherEvent is ArcAppearEvent) return 1;

else return -1;

}

else return 0;

}

else return -2;

}

public override bool Equals(object obj) {

if (obj is FortuneEvent && GetType() == obj.GetType()) {

if (this is ArcRemoveEvent)

return (this as ArcRemoveEvent).Equals(obj as ArcRemoveEvent);

else if (this is ArcAppearEvent)

return (this as ArcAppearEvent).Equals(obj as ArcAppearEvent);

return false;

}

else return false;

}

public override int GetHashCode() => Position.GetHashCode();

public override string ToString() => string.Format("{0} X:{1} Y:{2}", GetType().Name, X, Y);

}

}

ЛистингIPoint.cs

namespace yLibrary.Voronoi{

public interface IPoint {

double X { get; }

double Y { get; }

}

}

ЛистингPoint.cs

using System;

namespace yLibrary.Voronoi{

public struct Point : IPoint {

public Point(double X, double Y) {

this.X = X;

this.Y = Y;

}

public double X { get; set; }

public double Y { get; set; }

public bool IsNull => double.IsNaN(X) || double.IsNaN(Y);

public double Distance(IPoint other) => Distance(this, other);

public static double Distance(IPoint first, IPoint second) => Math.Sqrt(Math.Pow(first.X - second.X, 2d) + Math.Pow(first.Y - second.Y, 2d));

public static Point operator +(Point a, Point b) => new Point(a.X + b.X, a.Y + b.Y);

public static Point operator -(Point a, Point b) => new Point(a.X - b.X, a.Y - b.Y);

public static bool operator ==(Point a, Point b) => a.Equals(b);

public static bool operator !=(Point a, Point b) => !a.Equals(b);

public override bool Equals(object obj){

if (obj.GetType() == typeof(Point))

return ((Point)obj).X == X && ((Point)obj).Y == Y;

else return false;

}

public override int GetHashCode() => X.GetHashCode() ^ Y.GetHashCode();

public override string ToString() => string.Format("({0};{1})", X, Y);

public static readonly Point NullPoint = new Point(double.NaN, double.NaN);

}}



Реферат

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

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

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

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

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

Для построения диаграммы Вороного существует несколько алгоритмов. В данной работе были рассмотрены простой алгоритм и алгоритм Форчуна.

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

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

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

В отличие от простого алгоритма, алгоритм Форчуна имеет сложность в раз меньше (), и поэтому он имеет преимущество во времени исполнения.

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

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

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

Также, была проведена контрольная проверка - расчёт вероятности ошибки для модуляции ФМ-4. Эта модуляция имеет четыре сигнальные позиции. Были произведены два расчёта: теоретический, с использованием известной математической модели расчёта, и с использованием диаграмм Вороного. Были рассчитаны вероятности ошибки на символ, ошибки на бит прямого кода и ошибки на бит кода Грэя. С заданной точностью расхождение наблюдается только в нескольких случаях расчёта.



Презентация



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

...