2. Таймерные сигнальные конструкции, как инструмент
увеличения скорости передачи информации в каналах модели Гильберта.
Таймерным сигнальным конструкциям (ТСК) посвящено много работ в связи с
возможностью получения пропускной способности канала большей, чем при
позиционном кодировании [4].
Передаваемые по каналу сигнальные конструкции имеют интервалы между
смежными моментами модуляции не кратными элементу « найквиста», но и не
меньше его:
=
+ ∆ ( ∈ 1 … ) ∈
целые числа
∆=
( ∈ 1 … ) ∈ 1; 2; − целые числа
(6)
Выбор сигнала
с
не меньше t
0
устраняет межсимвольные искажения, а отсутствие
кратности
величине t
0
позволяет уменьшить минимальное расстояние между
сигнальными конструкциями, что в свою очередь увеличивает мощность разрешенного к
передаче множества [4] :
= ∑
(
)
=
!
! (
)!
(7)
Для случая
=
=
=
(
)
110
где i – число информационных отрезков
в сигнальной конструкции,что
соответствует числу моментов модуляции . Среди разрешенных сигналов могут быть
реализации с одним ЗММ, двумя, тремя и т.д. С максимальным числом моментов
модуляции mвозможна только одна реализация(точки).
Для примера в табл. 2 приведено количество реализаций ТСК для
некоторых величин T
c
= mt
0
и S
∈ 2 ; 3 ; 4 при = 3 [ ].
Таблица 2 – Количество реализаций ТСК и среднее значение ЗММ
для некоторых величин; = mt
0
;N = 2
m
T
c
S
T
c
= 4t
0,
N
пк
= 16
T
c
= 5t
0
,
N
пк
= 32
T
c
=6t
0
,
N
пк
= 64
T
c
= 7t
0
,
N
пк
= 128
T
c
= 8t
0
,
N
пк
= 256
2
10
35
84
165
286
3
20
84
220
455
816
7
120
680
2024
4495
8436
Примечание. Символом
пк
обозначено число реализаций при позиционном
кодировании для =2.
Как видно из табл. 2, на одном и том же интервале можно образовать большее
количество ТСК , чем сигналов простого двоичного кода (N = 2
m
). Следовательно ,
эффективная скорость передачи, т.е. количество передаваемой информация на
интервале увеличивается.
При работе по каналам модели Гильберта на интервалах хорошего
состояния вероятность
ош
определяется величиной зоны,,
∆” ,
среднеквадратичным отклонением ЗМВ,,, ” что в свою очередь зависит от
соотношения сигнал/помеха, а также числом переходов в кодовом слове ,,i “
Остановимся на проблеме обнаружения ошибок и исправления смещенной ЗМВ
в избыточных кодовых конструкциях ТСК.
Обнаружение ошибок на приеме в сигнальных конструкциях производится
проверкой условия качества [2], которое устанавливает связь между длительностью
расстояний смежных ЗММ (
)и системой некоторых коэффициентов А ,которые
определяют минимальные расстояния между реализациями ТСК[4].
∑
A
τ = 0 mod (A
0
) (8)
Коэффициенты уравнения должны обеспечивать наличие остатков
(синдромов) обеспечивающих исправление более вероятныхсмещенийЗМВ [4].
Так как модуль сравнения А определяет число возможных синдромов с одной
стороны, а также мощность множества ТСК удовлетворяющих условию (8),то для
уменьшения его значения необходимо исправлять более вероятные смещенияЗМВ , а
остальные достаточно обнаруживать с целью исправления за счет повторения. Сравним
вероятность появления на интервале
смещений одного ЗМВ из трех в кодовых
словах при S=7 , i=3 для значения
с
= 0,02t
0
.
Определим вероятности смещений одного ЗМВ на величину 1,5
∆ > >
0,5
∆. Вероятность такого события будет определяться [8]
(1
∆) = ф
, ∆
ф
, ∆
(9)
а вероятность смещения двух ЗМВ
111
(1
∆) = 3[
( 1
∆) ]
2
* p(0) (10)
где p(0) – вероятностьверного приема ЗМВ в зоне 0,5
∆≥
≥ 1,5∆ (в пределах ,,
своей’’ зоны).
Аналогично для вероятности смещения трёх ЗМВ на величину
0,5
∆≤
≤ 1,5∆ определяется
(1
∆) = [ (1∆) ]
3
(11)
Подставив соответствующие значения
∆ и
в выражения [(8);(11)] получим
численные значения смещений одного ( = 1
∆) , двух и трёх ЗМВ.
(
= 1∆) = 1,7 ∙ 10
4
[ ( = 1∆)]
2
= 2,89 ∙ 10
8
(3
3
)=
(
=1∆) = 4,9 ∙ 10
12
Таким образом, так как вероятность двукратных смещений на = 1
∆ почти на 4
порядка меньше смещения
(1
∆ ), а трёх ЗМВ более чем на 7 порядков меньше
значение смещения одного перехода, то с целью уменьшения модуля А ( увеличение
мощности множества) целесообразно предусмотреть смещение только одного перехода.
(1
∆) = 1,7 ∙ 10
4
. Рассмотрим результаты измерений качества передачи избыточных
ТСК по каналу ГТС с ЧМ, в которых параметры уравнения качества передачи
удовлетворяли условию[4]:
2∙
с
+ 3∙
с
+ 5 ∙
с
= 0 (mod
) (12)
В таблице 3 приведены номера кодовых слов принятых ошибочно при передаче
7500 кодовых слов с тремя ЗММ при S =7 на интервале
= 8
по каналу ГТС г.
Одессы :
Таблица 3
Номера кодовых
слов с
дроблением
Номер Искаженные КС (
= 1∆)
Первый ЗММ Второй ЗММ Третий ЗММ
756; 1549; 2383;
3131; 3643; 4444;
5052; 5881; 6677;
7453;
1067;2030; 2305;
2543; 2717; 2936;
3339; 3408; 3486;
3530; 3723; 3838;
4040; 4972;
5508;6089; 6101;
6215;6453
3768;7437
825; 1649; 1695;
2017; 2461; 2576;
3042; 3991 ;
4916;
5138; 5847
Из таблицы следует, что при большом значении помехи
>
могут появиться
дробления (обычно увеличивается число ММ на два), а в“ хорошем” состоянии
канала)смещения ЗММ. Обычно смещается один ЗММ (вероятность смещения двух
ММ на(
= 1∆) в тысяча раз меньше вероятности смещения одного ЗМВ.
Изменения числа моментов модуляции легко проверяется на приеме появлением
более трех ЗМВ, а наличие смещений проверяется выполнением уравнения качества
приема (уравнения 12).
Уравнение качества приема обеспечивает проверку условия отбора для передачи
из общего множества кодовых слов [2].
M =
(
)
=
[
(
)]!
[
(
)]!
(13)
112
Наличие длительностей отдельных отрезков ,, x
1
” , ,,x
2
” и ,,х
3
” удовлетворяющих
условию отбора кодовых слов
2
+ 3
+ 5
= 0 (mod11)
говорит о правильной передаче координат кодового слова.
При искажении одного из переходов на величину Ѳ= 1
∆ уравнение(11) не будет
выполняться и в зависимости от номера смещенного ММ в остатке будут числа
представлены в табл.4
Таблица 4
Номера ЗММ
Знак искаж
I
II
III
+
2
3
5
−
9
8
6
Наличие одного из указанных в таблице 4 остатков позволяет однозначно
исправлять появляющиеся одиночные смещения ЗММ.
Список литературы:
1 Мир программирования М.Вернер. Основы кодирования. Учебник для вузов,
ТехносфераМосква 2004.
2 Шеннон К Математическая теория связи М.НЛ. 1963
3 Васильев В.И и др. Системы связи. Учебное пособие для Вузов – М; Высшая
школа 1987.280с
4 Захарченко М.В и др.Системипередаванняданих Том 1. Ефективнiсть
блокового кодування. Одеса 2014.486с.
113
СЕКЦИЯ 2
SESSION 2
Қосымшалармен бірге есептеу және математикалық модельдеу
Computational and mathematical modeling with applications
Hesaplamalı ve matematikse lmodelleme ve uygul amaları
Вычислительное и математическое моделирование с приложениями
УДК 519.7
1
Амиргалиев Е.Н.,
2
Калыбек уулу Б.
1
Д.т.н., профессор, Университет имени Сулеймана Демиреля,
Каскелен, Казахстан, e-mail: amir_ed@mail.ru
О РЕЗУЛЬТАТАХ РЕШЕНИЯ ЗАДАЧИ ГРУППОВОГО СИНТЕЗА
АЛГОРИТМОВ КЛАССИФИКАЦИИ
Abstract. In this work some numerical results of the decision of a task of group
synthesis on an example of two algorithms are considered. Is applied the metrics of affinity of
classification in space of classification.
В работе рассматривается возможность решения задачи группового синтеза
классификаций для исходных алгоритмов. В качестве алгоритма A
1
принять алгоритм
максиминного расстояния, а в качестве A
2
–алгоритм К внутригрупповых средних.
Пусть
A
A
A
m
,...,
1
исходный заданный набор алгоритмов и
n
S
S
M
,...,
1
конечное множество объектов,
.
D
M
Результатом применения
i
A
к
M
является
классификация
)
(
)
(
M
M
K
i
, где
)
(M
пространство классификации, элементами
которого являются конкретные классификации. Основная задача группового синтеза
состоит в следующем.
Пусть определена метрика
)
,
(
"
'
K
K
d
в
(
M
) и
F
(K)=
m
i
i
K
K
d
1
)
,
(
,
)
(M
K
.
Найти
)
(
)
(
M
M
K
такое, что
)
(
min
)
(
)
(
K
F
M
K
K
F
.
Пространство
классификаций
)
(M
конечно
множества
объектов
n
S
S
M
,...,
1
помимо рассмотренных метрических свойств, обладает некоторыми
"структурными" свойствами, которые также можно использовать для решения задач
синтеза групповых классификаций [1].
Очевидно, что структура
)
(M
не является булевой алгеброй, так как в ней,
нетрудно проверить, не выполнены дистрибутивные законы, однако по аналогии с
дискретной булевой алгеброй можно показать, что
)
(
1
M
n
базис в
)
(M
.
Действительно,
)
(
1
M
n
является единственным из множеств
),
(M
l
,
1
,...,
2
n
l
которое является дизъюнктным множеством. Также, очевидно, что ни для
одного элемента
)
(
1
M
K
n
не может существовать элемента
'
K , удовлетворяющего
неравенству
K
K
O
'
, т.е. элементы
)
(
1
M
n
неделимы и являются атомами
)
(M
.
Таким образом, пространство классификаций
)
(M
характеризуется наличием
минорантного дизъюнктного множества атомов
)
(
1
M
n
.
Таким образом, в качестве метрики близости в пространстве классификации
использована метрика, введенная в работе [2 ]. В качестве базовых алгоритмов
использованы алгоритмы максиминного расстояния и К внутригрупповых средних,
рассмотренных в подробно в работе [3]. В качестве исходных объектов использованы
114
данные размером 61х14 (реальные гидрогеологические данные). С помощью
реализованной программы, исходные допустимые объекты классифицировались, при
различных параметрах алгоритмов, сначала максиминным методом, а затем
корректировались методом Квнутригрупповых средних и получены следующие
результаты:
Классификация 1
Алгоритм: максиминный метод + метод Квнутригрупповых средних
Входные параметры максиминного алгоритма: первый объект: S1, параметр: 0,4
Количество кластеров 12
Кластер 1 (7): S0, S1, S2, S3, S4, S7, S8; Кластер 2 (2): S11, S21;
Кластер 3 (8): S26, S34, S35, S36, S37, S39, S40, S41; Кластер 4 (1): S51;
Кластер 5 (6): S24, S27, S29, S30, S49, S50; Кластер 6 (2): S10, S15;
Кластер 7 (7): S9, S12, S17, S18, S19, S23, S31
Кластер 8 (9): S52, S53, S54, S55, S56, S57, S58, S59, S60
Кластер 9 (2): S16, S20
Кластер 10 (13): S22, S25, S28, S32, S33, S38, S42, S43, S44, S45, S46, S47, S48; Кластер
11 (3): S5, S6, S14; Кластер 12 (1): S13.
Классификация 2
Алгоритм: максиминный метод + метод Квнутригрупповых средних
Входные параметры максиминного алгоритма: первый объект: S1, параметр: 0,5
Количество кластеров 8
Кластер 1 (9): S0, S1, S2, S3, S4, S5, S7, S8, S13; Кластер 2 (2): S11, S21;
Кластер 3 (11): S26, S33, S34, S35, S36, S37, S38, S39, S40, S41, S42
Кластер 4 (1): S51; Кластер 5 (16): S16, S20, S24, S25, S27, S28, S29, S30, S43, S44, S45,
S46, S47, S48, S49, S50; Кластер 6 (4): S6, S10, S14, S15;
Кластер 7 (9): S9, S12, S17, S18, S19, S22, S23, S31, S32;
Кластер 8 (9): S52, S53, S54, S55, S56, S57, S58, S59, S60.
Классификация 3
Алгоритм: максиминный метод + метод Квнутригрупповых средних
Входные параметры максиминного алгоритма: первый объект: S1, параметр: 0,6
Количество кластеров 6
Кластер 1 (13): S0, S1, S2, S3, S4, S5, S7, S8, S12, S13, S17, S18, S19
Кластер 2 (2): S11, S21; Кластер 3 (17): S22, S23, S26, S31, S33, S34, S35, S36, S37, S38,
S39, S40, S41, S42, S53, S56, S60; Кластер 4 (7): S51, S52, S54, S55, S57, S58, S59;
Кластер 5 (17): S16, S20, S24, S25, S27, S28, S29, S30, S32, S43, S44, S45, S46, S47,
S48, S49, S50; Кластер 6 (5): S6, S9, S10, S14, S15
Классификация 4
Алгоритм: максиминный метод + метод Квнутригрупповых средних
Входные параметры максиминного алгоритма: первый объект: S52, параметр: 0,4
Количество кластеров 11
Кластер 1 (1): S51; Кластер 2 (2): S11, S21; Кластер 3 (2): S6, S14; Кластер 4 (8): S24,
S27, S28, S29, S30, S32, S49, S50; Кластер 5 (3): S23, S26, S35; Кластер 6 (5): S12,
S13, S17, S18, S19; Кластер 7 (2): S16, S20
Кластер 8 (3): S9, S10, S15; Кластер 9 (18): S22, S25, S31, S33, S34, S36, S37, S38, S39,
S40, S41, S42, S43, S44, S45, S46, S47, S48;
Кластер 10 (9): S52, S53, S54, S55, S56, S57, S58, S59, S60
Кластер 11 (8): S0, S1, S2, S3, S4, S5, S7, S8
Классификация 5
115
Алгоритм: максиминный метод + метод квнутригрупповыхсредних
Входные параметры максиминного алгоритма: первый объект: S52, параметр: 0,5
Количество кластеров 9
Кластер 1 (3): S51, S52, S59; Кластер 2 (2): S11, S21; Кластер 3 (4): S3, S5, S6, S14;
Кластер 4 (8): S24, S27, S28, S29, S30, S32, S49, S50; Кластер 5 (10): S23, S26, S35,
S53, S54, S55, S56, S57, S58, S60; Кластер 6 (11): S0, S1, S2, S4, S7, S8, S12, S13, S17,
S18, S19; Кластер 7 (2): S16, S20
Кластер 8 (3): S9, S10, S15; Кластер 9 (18): S22, S25, S31, S33, S34, S36, S37, S38, S39,
S40, S41, S42, S43, S44, S45, S46, S47, S48.
Классификация 6
Алгоритм: максиминный метод + метод квнутригрупповыхсредних
Входные параметры максиминного алгоритма: первый объект: S52, параметр: 0,6.
Получены кластера, с центрами соответственно S55 и S6.
Определяя расстояний между классификациями, получаем следующую таблицу
расстояний:
A
1
A
2
A
3
A
4
A
5
A
6
Сумма
A
1
0
23
38
21
30
48
160
A
2
23
0
21
32
43
49
168
A
3
38
21
0
33
35
44
171
A
4
21
32
33
0
15
43
144
A
5
30
43
35
15
0
43
166
A
6
48
49
44
43
43
0
227
Из таблицы видно, что наиболее приближенной ко всем классификациям является
классификация, полученная в результате выполнения алгоритма А
4
(максиминный
метод + метод К внутригрупповых средних с входными параметрами:
первый объект: S52, параметр: 0,4).
Таким образом, групповой синтез на базе двух алгоритмов при различных
параметрах дает классификацию на базе алгоритма А
4
, что и является искомым
решением.
Список литературы:
1 M.B. Aidarkhanov. Metric and Structural Approaches to the
Construction of Group Classifications // Pattern Recognition and
Image Analysis. USA 1994. Vol.4, №4, P. 372389
2 Айдарханов М.Б. Методы синтеза классификации для конечных и континуальных
множеств объектов. Алматы, Галым, 1994, 200с.
3 Амиргалиев Е.Н. Теория распознавания образов и кластерного анализа. Алматы,
Издательский Центр КазНТУ, 2003, 340с.
УДК518.9
Достарыңызбен бөлісу: |