Документ взят из кэша поисковой машины. Адрес оригинального документа : http://www.abitu.ru/en2002/closed/viewwork.html?thesises=116 Дата изменения: Fri May 5 15:24:34 2006 Дата индексирования: Tue Oct 2 03:18:01 2012 Кодировка: koi8-r Поисковые слова: equinox

Двойные каналы связи и числа Рамсея

Теория кодирования - одна из активно развивающихся областей
современной математики. К основным, традиционным задачам теории кодирования
относят две - в некотором смысле противоположные - задачи: 1) задачу
обработки информации с целью ее сокрытия и 2) задачу передачи информации
без ошибок по каналам связи. Анализируя способы решения задачи передачи
информации без ошибок, следует отметить два подхода: во-первых, подход,
основанный на разумной организации самой информации [3,4]; и, во-вторых, -
подход, основанный на исследовании возможностей канала связи [2]. Именно
исследованию каналов связи и посвящена настоящая работа.
Математическая формализация задачи [2] сводится к поиску независимого
множества [4,5,6] в характеристическом графе канала связи. Число
независимости как мощность наибольшего независимого множества определяет
количество информации, которое может быть передано без ошибок. Кроме
обычных каналов связи, интересным объектом исследования являются двойные
каналы связи, так как для случая пятиугольного канала связи [2]
использование двойного канала связи позволяет за один раз передать без
ошибок большее количество информации, чем при использовании обычного канала
дважды. Характеристический граф двойного канала в терминах
характеристического графа исходного канала определяется как нормальный
квадрат характеристического графа исходного канала. Тот факт, что для
пятиугольного канала связи имеет место неравенство
[pic],
где G - характеристический граф канала связи,
[pic] - нормальный квадрат характеристического графа (т.е.
характеристический граф
двойного канала),
[pic] - число независимости графа G,
означает существование таких каналов связи, для которых двойные каналы
позволяют передать без ошибок большее количество информации, чем при
использовании обычного канала дважды.
Характеристикой надёжности двойных каналов связи является число
[pic].
Число [pic] отражает наилучшую из возможных математических
характеристик двойных каналов связи. С использованием дизъюнктивного
объединения простых циклов [pic] в работе самостоятельно доказано
неравенство
[pic]
для четных l.
Мощным и современным средством оценки количества информации, которое
можно передать без ошибок по двойному каналу связи, является теорема о
равенстве числа Рамсея характеристике надёжности двойных каналов связи
[pic] [2].
В связи с этим в работе приведено определение чисел Рамсея и
самостоятельно вычислены некоторые из них, а именно [pic], [pic], [pic],.,
[pic]; [pic], [pic]. При этом задача вычисления [pic] представляет особый
интерес. Для доказательства равенства [pic] необходимо показать, что для
всех графов порядка меньше 6 существует хотя бы одна рёберная 2-раскраска
такая, что мощность каждого монохроматического множества не превосходит
двух, и что для графа порядка 6 не существует такой рёберной раскраски.
Использование чисел Рамсея позволяет получать значения [pic] при
оценке пропускной способности двойных каналов связи. В связи с этим
равенство [pic] даёт возможность воспользоваться полученными за долгие годы
оценками чисел Рамсея для характеристики надёжности двойных каналов связи.
Таким образом, в работе было самостоятельно проведено доказательство
неравенства [pic], изучены свойства чисел Рамсея, в частности,
самостоятельно получены некоторые из них, и проанализирована связь чисел
Рамсея с характеристикой надёжности двойного канала связи.

Литература

1. Лекции по теории графов / Емеличев В.А., Мельников О.И., Сарванов В.И.,
Тышкевич Р.И. - М.: Наука, 1990. - 384 с.
2. Noga Alon, Alon Orlitsky. Repeated Communication and Ramsey Graphs,
1995. http://www.math.tau.ac.il/~noga/ .
3. Леонтьев В.К. Теория кодирования - М.: Знание, 1977. - 64 с.
4. Яблонский С.В. Введение в дискретную математику: Учеб. пособие для
вузов. - 2-е изд., перераб. и доп. - М.: Наука. Гл. ред. физ.-мат. лит. -
384 с.
5. Прикладная математика для инженеров-системотехников. Дискретная
математика в задачах и примерах: Учеб. пособие / В.Г. Новоселов, О.В.
Скатков - К.: УМК ВО, 1992. - 200 с.
6. A. Pavlov, L. Pavlova. PDC-algorithms for Intractable Combinatorial
Problems. Theory And Methodology of Design. - Ужгород, 1998. - 326 с.
7. Теория Рамсея. В мире науки. 1990/?9.
http://rusnauka.narod.ru/lib/matem/ramsey/rams.htm .
8. J.J. O'Connor, E.F. Robertson. Frank Plumpton Ramsey.
http://www-history.mcs.st-andrews.ac.uk/history/Mathematicians/Ramsey.html
.
9. Гарднер М. От мозаик Пенроуза к надёжным шифрам - М.: Мир, 1993 - 416 с.