АЛМАТИНСКИЙ ИНСТИТУТ ЭНЕРГЕТИКИ И СВЯЗИ

 

 

 

 

Кафедра автоматической электросвязи

 

 

 

 

 

 

 

 

 

СЕТИ СВЯЗИ и СИСТЕМЫ КОММУТАЦИИ

 

 

 

Программа, методические указания и контрольные задания

(для студентов специальности

380240-Многоканальные телекоммуникационные системы

заочной формы обучения).

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Алматы 2005

 

СОСТАВИТЕЛИ: Г. П. Данилина, Е. А. Шкрыгунова, Ш. А. Мирзакулова.  Сети связи и системы коммутации. Программа, методические указания и контрольные задания  для студентов специальности 380240-Многоканальные телекоммуникационные системы заочной формы обучения.- Алматы: АИЭС, 2005. -28 с.

 

 

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

 

Ил. 10  , табл. 8  , библиогр.-7

 

 

 

 

 

 

Рецензент: проф. кафедры автоматической электросвязи, канд. техн. наук Т. К. Бектыбаев

 

 

 

 

 

Печатается вне  плана издания Алматинского института энергетики и связи на 2005 г.

 

 

 

 

 

 

 

 

©   Алматинский институт энергетики и связи, 2005 г.

 

 

1 Программа курса

 

 

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

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

На практических занятиях студенты приобретают навыки формализации  задач анализа и синтеза сетей, рассчитывают потребное количество коммутаторов в заданных коммутационных блоках, отображают функциональные схемы АТС-ДШИ, АТСК-100/2000, АТСК, АТСКУ, АТСКЭ и цифровых АТС и их взаимодействие между собой.

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

        

Согласно программе, на изучение курса отведено 264 часов, в том числе:

- лекции – 26 часов;

- лабораторные занятия – 28 часов;

- практические занятия – 14 часов;

- самостоятельная работа – 222 час.

Распределение объёма часов работы студента - заочника при изучении курса приведено в таблице. Дисциплина «Сети связи и системы коммутации» изучается на четвертом  и пятом курсах. На четвертом курсе выполняются две контрольные работы. На пятом курсе выполняется контрольная и курсовая работа.

 

	Лекции	Практические	Лабораторные
4 курс	10	14	8
5 курс	16	14	6

 

 

1.1 Содержание учебного материала

 

1.1.1 История развития сетей связи и систем коммутации. Современное состояние сетей связи. Содержание и задачи дисциплины «Сети связи и системы коммутации». Перспективы  развития сетей связи и систем коммутации. Стандартизация на сетях связи. МСЭ-Т.

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

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

1.1.4 Сигнализация в телефонных сетях. Классификация видов сигнализации. Способы передачи межстанционной сигнальной информации. Абонентская сигнализация. Взаимодействие абонентского терминала со станцией. Передача номера абонента по абонентской линии. Линейная сигнализация. Регистровая сигнализация и методы передачи сигналов. Кодирование регистровых сигналов. Основы сигнализации ОКС№7. Сеть сигнализации.

1.1.5 Эталонная семиуровневая модель взаимодействия открытых систем (ВОС).

1.1.6 Основы построения интегральных сетей и сетей с интеграцией служб. Сети ISDN. Построение линейных интерфейсов: интерфейсы абонентских и соединительных линий, особенности организации интерфейсов ISDN. Дополнительные виды обслуживания.

1.1.7 Сети абонентского доступа. Способы аналогового абонентского доступа. Способы цифрового абонентского доступа. Построение абонентских сетей. Основы технологии хDSL.

1.1.8 Основы теории телетрафика. Предмет и задачи теории телетрафика. Моделирование телекоммуникационных систем. Потоки вызовов. Характеристики систем обслуживания вызовов. Системы обслуживания вызовов. Анализ. Синтез.

1.1.9 Современные технологии управления сетью связи и передачи данных. Интеллектуальные сети связи. Сеть управления электросвязью. Технологии передачи PDH и SDH.

1.1.10 Принципы построения систем коммутации. Виды коммутации: коммутация каналов, коммутация с запоминанием. Понятие об автоматической коммутации. Акустико-электрические и электро-акустические преобразователи. Принцип работы номеронабирателей. Схема телефонного аппарата. Сигнализация DTMF. Виды исканий. Ступени искания. Коммутационные приборы. Коммутационные блоки. Основные принципы автоматического установления соединения.

1.1.11 Принципы построения УУ. Индивидуальное, косвенное, общее управление, ПУУ, ЦУУ. Классификация УУ. Функции УУ.

1.1.12 Квазиэлектронные системы коммутации. Виды ступеней искания. БАЛ, БСЛ. АЦП, ЦАП.

1.1.13 Принципы цифровой синхронной коммутации. Ступень временной коммутации, его векторное представление. Реализация Т-ступени. Режимы: последовательная запись/произвольное считывание и произвольная запись/последовательное считывание. Методы расширения Т-ступени.

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

1.1.15 Принцип пространственно-временной коммутации. Координатный способ построения ST ступени. Классификация ЦКП.

1.1.16 Кольцевые цифровые коммутационные поля. ЦКП первого класса.

 

1.2 Перечень практических работ

 

1.2.1 Синтез централизованных сетей с применением методов: Ежи-Вильямса, Прима, Крускала.

1.2.2 Сравнительный расчет времени набора с использованием дискового и тастатурного номеронабирателей.

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

1.2.4. Построение коммутаторов звеньевых схем аналоговых и цифровых АТС.

 

1.3 Перечень лабораторных работ

 

1.3.1 Выбор оптимального местоположения объектов (АТС, распределительных шкафов).

1.3.2 Решение задач районирования.

1.3.3 Расчет каналов на обходных направлениях связи.

1.3.4 Целесообразность автоматического проектирования сетей связи.

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

1.3.6 Изучение регистра и тонального генератора.

1.3.7 Изучение установления соединения на АТС.

1.3.8 Ознакомление с обучающей программой ELS-1. Характеристики переключателя с пространственным разделением.

1.3.9 Исследование функциональных кнопок гибридного телефонного аппарата цифровой УПАТС IP PBX «Panasonic». Создание дополнительных услуг: «горячая линия», «перенаправление вызова», «конференц-связь».

1.3.10 Назначение (удаление, изменение номера) внутреннего номера абонента (имени абонента) на рабочем ПК с записью на ВЗУ. Перенос на главный ПК с инсталлированной программой IP PBX «Panasonic». Установление внутренней связи. Входящие вызовы, вызов с канала связи. Процедуры, когда все пути заняты. Блокирование номера.

1.3.11 Назначение (удаление) группы внутренних абонентов. Назначение (удаление, изменение номера) внутреннего номера абонента в группе (имени абонента в группе) на ПК с записью на ВЗУ. Перенос на главный ПК с инсталлированной программой IP PBX «Panasonic». Осуществление функции: «перехват вызова в группе»; «распределение вызова по очереди». Установление внутренней связи в группе. Внутренний вызов. Входящие вызовы, вызов с канала связи.

1.1.14 Назначение (удаление) дополнительных видов обслуживания абоненту УАТС. Назначение (удаление) ДВО абоненту в группе.

 

 

2 Методические указания по разделам  курса

 

2.1 Построение сетей. Синтез сетей

Изучение материала следует начинать с современного состояния и роли сетей связи в экономическом и социальном развитии общества. Необходимо изучить состав и структуру общегосударственной системы связи и её основных подсистем - общегосударственной системы телефонной связи, общегосударственных систем телеграфной связи, передачи данных, факсимильной связи и других. Нужно знать определения первичной и вторичных сетей связи. Ознакомиться с проблемой создания технической основы –  Единой автоматизированной сети связи. Изучить состав ЕАСС,  основные элементы, каналы и линии, средства управления сетью и их классификацию. Рассмотреть виды коммутации, применяемых в сетях, проблемы интеграции каналообразующей и коммутационной аппаратуры,  а также интеграции вторичных сетей связи. Необходимо усвоить предпосылки создания ЕАСС и её эффективность для народного хозяйства и отрасли связи.

Материал изложен в основной  литературе [1, стр. 7-25, стр. 3-25]

 

2.2 Телефонные сети

Материал данного раздела охватывает все виды сетей связи. Структура ЕАТСС описана в [5, стр. 323-394, 6, стр. 10-14]. Принципы построения телефонных сетей, вопросы распределения затухания по участкам разговорного тракта, системы нумерации в [1, стр. 227-247].

Изучив общую структуру ЕАСС, нужно рассмотреть способы построения различных сетей. Необходимо знать и уметь вычерчивать схему построения взаимосвязанной автоматически коммутируемой телефонной сети (АКТС).

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

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

Рассмотрение систем нумерации на различных телефонных сетях рекомендуется связать с ёмкостью и принципами их построения. Необходимо научиться рассчитать ёмкость различных систем нумерации. [1, стр. 26-70], [6, стр. 342-347, 359-373].

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

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

 

2.3 Коммутационные системы

В данном разделе рассматриваются принципы построения координатных, квазиэлектронных  и электронных АТС.

Материал данного раздела изложен в [1, стр. 148-226, 267-278, 2, стр. 398-403].

При рассмотрении принципов построения АТС и порядок установления соединения  на ступенях искания.

Рассмотрев преимущества и особенности координатных АТС, нужно внимательно разобрать построение их ступеней искания. Необходимо уметь изображать функциональные схемы АТСКУ. И, используя эти схемы, рассказывать порядок установления соединения.

Из схем типовых автоматических междугородных телефонных станций АМТС и АХЕ-10.

При изучении квазиэлектронных АТС следует уяснить, что в качестве коммутационного поля в этих станциях используются многозвенные коммутационные схемы. Изучите структурную схему АТС типа ЭАТС и МТ-20/25.

 

2.4 Построение коммутационных блоков, полей и их управляющих устройств

 

В этом разделе рассматриваются принципы телефонной коммутации, коммутационные блоки и управляющие устройства АТС. Для изучения  этого материала нужно прочитать [5, стр. 74-83, 8, стр. 6-26, 1, стр. 72-75].

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

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

 

2.5 Основы теории распределения информации

В этом разделе изучаются принципы расчета коммутационных систем, которые изложены в [стр. 61-71, 75-86, 109-112].

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

 

2.6 Состав оборудования  цифровой системы коммутации

Состав оборудования цифровой системы коммутации (ЦСК) Коммутационное поле, устройства сопряжения, управляющие устройства, устройства сигнализации и синхронизации. Виды цифровой коммутации: пространственная и временная. Включение абонентских линий в ЦСК, применение выносных устройств (концентраторов и мультиплексоров) Структуры системы подключения абонентов (звездообразная, лучевая, шлейфная, линейная). Функции BORSHT.

В состав оборудования ЦСК входит коммутационное поле (КП), управляющие устройства, устройства сопряжения, сигнализации и синхронизации.  Необходимый материал [5, стр. 109-117], [1, стр. 11-13, 16-18].

В процессе обслуживания вызова осуществляется обмен управляющими сигналами и  информацией между отдельными частями ЭУМ, управляющими устройствами ЭУС и периферийными устройствами  с помощью устройств сопряжения (соединения), вызываемых интерфейсами. Интерфейсы могут быть  системными [1, стр. 35,41] , ввода вывода [1, стр. 37-38, 82-85].

Устройства синхронизации координируют  работу УУ ЭУС [1, стр. 88,105-106].

 

2.7 Виды интеграции цифровых сетей

 

Развитие цифровых систем передачи (синхронные цифровые иерархии). Применение цифровых коммутационных узлов на первичной сети.

Первый и второй типы интеграции сетей. (IDN- Integrated Digital Network, ISDN Integrated Services Digital Network).  Виды сервиса, предоставляемые пользователями ЦСИС интерактивные и распределительные. Понятие об узкополосной и широкополосной ЦСИС. Модель ЦСИС: представлена в [2, стр. 395].

 

 

3 Контрольное задание

 

 

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

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

 

3.1Контрольная работа 1

 

Задание к контрольной работе

В приложении даны варианты заданий: выбор матрицы осуществляется  по последней цифре зачетной книжки и первой букве фамилии студента.  В зависимости от первой буквы фамилии стоимостные коэффициенты C_ij умножаются на следующие коэффициенты k:

А,Б,В,Г- k=1; Д,Ж,З,И- k=2; К,Л,М,Н- k=3; О,П,Р,С- k=4; Т...Я- k=5.

Необходимо:

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

- разработать блок- схему алгоритма одного из методов.

Для выполнения контрольной работы необходимо знать, что

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

- терминалы Т_i которые могут подключаться к концентратору или непосредственно к ЭВМ;

- концентраторы К_j могут  соединяться с центральной ЭВМ.

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

 Упрощенный вариант задачи синтеза

Упростим задачу, предположив возможность ее замены одноуровневой, т. е. сначала решается задача прикрепления терминалов к концентраторам, а затем – концентраторов к ЭВМ. Иными словами, решим задачу в следующей постановке: задано некоторое множество генераторов (источников) информации S_i , i=1,..n, которые должны быть соединены сетью минимальной стоимости с приемником информации S_o. Допускается соединение S_i между собой.

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

 

Заданными являются стоимости C_ij соединения S_i и S_j,пропускная способность r_ij, интенсивности источников а_i, интенсивность стока

а_о= -а_i .

Исходные данные задаются в виде таблиц. Вид таблиц приведен на примере таблицы 1 и таблицы 2.

Если пропускные способности одинаковы для всех линий (S_i , S_j) , то задается число r_ij =R.

 

Таблица 1                                                     Таблица 2

Сij	S0	S1	- -	Sn		rij	S0	S1	- -	Sn
S1	C10	-	- -	C1n		S1	r10	-	- -	r1n
S2	C20	C21	- -	C2n		S2	r20	r21	- -	r2n
- -	- -	- -	- -	- -		- -	- -	- -	- -	- -
Sn	Cn0	Cn1	- -	-		Sn	rn0	rn1	- -	-

 

Пример решения приведен в методических указаниях.

При решении, используя метод синтеза централизованной сети надо учитывать следующее:

Варианты задания даны в Приложении В (номер задания соответствует последней цифре зачетки). Кроме того, все стоимости C_ij и f_j следует умножать на последнюю цифру года (в 2001- на 1, в 2002- на 2 и т.д.). Задачу синтеза решить вручную. Результат представить в виде рисунка оптимальной схемы соединения терминалов с ЭВМ и соответствующей этой схеме стоимости. Разработать и описать блок- схему алгоритма.

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

 

3.2 Контрольная работа

 

Задача 1.

Записать сочетание элементарных сигналов полярно-числового и многочастотного кодов, принятых в отечественных системах координатных АТС, для кодовых комбинаций, соответствующих набранному номеру приведенному в таблице 3. При использовании многочастотного кода запись произвести для двух способов передачи: а) «импульсный челнок»; б) «безынтервальный пакет». Кратко сравнить указанные коды и способы передачи между собой.

Таблица 3 – Исходные данные

Номер варианта	0	1	2	3	4	5	6	7	8	9
Набранный номер	27777	33335	46666	88881	05555	11117	66667	22224	70000	54444
Продолжение таблицы 3
Номер варианта	10	11	12	13	14	15	16	17	18	19
Набранный номер	77777	28888	39999	63333	66668	55553	41111	99992	44447	39999

 

 

Задача 2.

Разработать и вычертить односвязную двухзвенную схему коммутации с применением МКС 10х10. Схему изобразить в координатном или в символическом обозначении. Определить число коммутаторов каждого звена, число входов и выходов из каждого коммутатора, коэффициенты расширения (сжатия) на звеньях и схемы в целом. Подсчитать число точек коммутации и количество МКС на каждом звене и для схемы в целом; проанализировать пригодность разработанной схемы для использования в режимах свободного, группового и индивидуального искания.

Число входов в схему N, выходов М промежуточных линий V, тип схемы выбрать из таблицы 2 в соответствии с вариантом.

 

Таблица 4 – Исходные данные

Номер варианта	0	1	2	3	4	5	6	7	8	9
N V M	20 50 100	200 60 30	50 100 200	40 80 100	20 40 100	60 100 200	30 60 200	20 40 100	40 50 100	200 100 50
Тип схемы	ВП ВП	ПВ ПВ	ВП ВП	ПВ ПВ	ВП ВП	ПВ ПВ	ВП ВП	ПВ ПВ	ВП ВП	ПВ ПВ

 

Продолжение таблицы 4

Номер варианта	10	11	12	13	14	15	16	17	18
N V M	100 80 40	30 60 100	40 50 100	60 100 200	200 80 40	20 40 200	40 80 200	100 50 20	100 60 20
Тип схемы	ПВ ПВ	ВП ВП	ПВ ПВ	ВП ВП	ПВ ПВ	ВП ВП	ПВ ПВ	ВП ВП	ПВ ПВ

 

Задача 3.

Вычертить функциональную схему и схему группообразования заданного блока ступени группового искания координатной АТС; указать тип и число многократных координатных соединителей (МКС) на каждом звене блока, максимальное число направлений, на которые можно разделить выходы блока, максимально допустимое число линий (максимальная доступность), отводимых в одном направлении, рассчитать коэффициент расширения σА и связность fАВ; определить номера МКС и номера переключающего, выбирающего и удерживающего электромагнитов в этих МКС, с помощью которых устанавливается соединение от заданного входа к заданному выходу требуемого направления. Считать, что все направления образованы при q = 1. Кратко описать понятия "внутренние блокировки". Исходные данные взять в таблице 3.

 

Таблица 5 – Исходные данные

Параметр	Предпоследняя цифра номера зачетной книжки
	1	2	3	4	5	6	7	8	9	0
Тип блока	60х 80х 400	80х 120х 400	30х 40х 200	30х 40х 200	60х 80х 400	40х 40х 200	30х 40х 200	80х 120х 400	60х 80х 400	40х 40х 200
Продолжение таблицы 5
Номер направления	20	7	15	4	18	6	10	12	9	8
Номер выхода в направлении	17	20	13	9	16	5	8	19	14	3
Номер входа	22	13	26	15	6	18	9	17	1	7

 

Задача 4

Изобразить функциональную схему координатной АТС (АТСК) с одной ступенью искания ГИ (группового искания), предназначенную для работы на районированной сети без узлов при пятизначной нумерации. На схеме показать включение входящих и исходящих соединительных линий к декадно-шаговым и координатным АТС. Кратко описать работу регистров и маркеров по установлению соединения, указанного в таблице 4.

 

Таблица 6 – Исходные данные

Параметр	Предпоследняя цифра номера зачетной книжки
	1	2	3	4	5	6	7	8	9	0
Система АТС	АТС К	АТС КУ	АТС КУ	АТС К	АТС КУ	АТС КУ	АТС К	АТС КУ	АТС КУ	АТС К
Тип абонентского регистра	АРБ	АРБ	АР	АР	АРБ	АРБ	АР	АР	АРБ	АРБ
Вид связи	к АТС ДШ	внут рист	от АТС ДШ	к АТС КУ	от АТС КУ	от АТС ДШ	внут рист	к АТС ДШ	от АТС КУ	к АТС КУ

4  Методические указания к выполнению контрольной работы 1

 

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

Алгоритм Ежи – Вильямса

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

Алгоритм представляет собой итерационный процесс построения  соединений сети, пропускающей заданный поток информации.

 

Шаг 0. Вычисляется система пометок

t_ij= C_ij- C_io  для всех i, jN, ij                                                                  (1)

Параметр t_ij представляет собой разницу стоимости соединения узла i c узлом j или непосредственно с центром- узлом S_o.

 

Шаг 1. Выбрать наименьшее t_ij

         {t_ij}= t_kl .

Если t_kl <0, то перейти к шагу 2, при t_kl0- Шаг 4.

 

Шаг 2. Проверить а_k>0 (нужно ли передавать информацию?) и а_k r_kl; (а_k+ а_l)  r_lo (есть ли свободная пропускная способность).

При выполнении этих условий переходим к шагу 3, в противном случае t_kl полагаем равным  и возвращаемся к шагу 1.

 

Шаг 3. Если t_kl <0, то производится соединение S_k и S_l и пересчет показателей:    а_k¹=0 а_l¹= a_l+a_k

r_kl=r- а_k

F¹  =F+ С_kl.

Полагаем t_kl= и переходим к шагу 1.

 

Шаг 4. Если наименьшее t_{kl 0, это значит, что затраты на соединение} S_k-го узла с S_l-м больше, чем на соединение с S₀. В этом случае, S_k соединяется с S₀.

Полагаем: а_k^н=0

a₀^н=а_о+ а_k

F^н=F¹+С_ko

Процесс продолжается до тех пор, пока все а_i не станут равны 0.

Проиллюстрируем алгоритм небольшим примером.

Пример - Определить сеть минимальной стоимости, соединяющую терминал S_1,S₂, S₃ с ЭВМ S₀.

Стоимости линий C_ij приведены в таблице 7, пропускные способности всех линий приняты одинаковыми, r_ij=5.

Все полученные результаты вносим в таблицу.

Используя данные из приложения заполняем таблицу.

 

Таблица 7 – Стоимости линий C_ij

	S0	S1	S2	S3
S1	1	-	2	4
S2	4	3	-	1
S3	3	1	5	-

 

Расчет приведем на примере , при условии что

а₀=-8; а₁=2; а₂=3; а₃=3.

        

Шаг 0. Подсчитаем множество пометок по формуле (1)

t_ij= C_ij- C_io

t₁₂= C₁₂- C₁₀=2-1=1

t₁₃= C₁₃- C₁₀=4-1=3

t₂₁= C₂₁- C₂₀=3-4=-1;

t₂₃= C₂₃- C₂₀=1-4=-3;

t₃₁= C₃₁- C₃₀=1-3=-2;

t₃₂= C₃₂- C₃₀=5-3=2

 

Итерация 1.

Шаг 1. Определяем наименьшую пометку в множестве

Это означает, что нужно проверить возможность соединения вершин S₂ и S₃ (S₂=>S₃).

Шаг 2. Проверяем величину интенсивности в вершине S₂

а₂=3>0; а₂=3<r=5.

         А₂+ а₃=3+3>r- следовательно соединение S₂ => S₃ невозможно, полагаем t₂₃= и переходим к выполнению итерации 2.

Итерация 2.

Шаг 1. Определяем

 { t_ij}= t₃₁=-2, что соответствует соединению S₃ и S_1.

Шаг 2. а₃=3>0   а₃+ а₁=3+2=5=r, следовательно, это соединение возможно.

Шаг 3. Подсчитаем:

- затраты  F=C₃₁=1;

- новые интенсивности терминалов S₃ и S₁;

- a₃¹=0     а₁¹=2+3=5;

- пропускную способность

r¹₃₁=5-3=2.

 

Положим t₃₁=.          

 

Переходим к шагу 1 итерации 3.

Итерация 3.

Шаг 1. Определим { t_ij} = t₂₁.

Шаг 2. Проверим:

         a₂=3>0;  а₂<r=5;  а₂+а₁^’= 3+5>r=5, следовательно, это соединение невозможно, положим t₂₁= и переходим к  итерации 4.

Итерация 4.

Шаг 1.    {t_ij}= t₁₂>0, значит все  t_ij – положительны, переходим к шагу 4 .

          Шаг 4. Определим вершины с положительной интенсивностью и соединим их с S_0.

A₁=5<r₁₀    a¹¹₁=0   а¹₀=-8+5=-3    F¹¹=F+C₁₀=1+1=2. 

А₂=3<r₂₀    a¹₂=0   а¹¹₀=-3+3=0    F¹¹¹=F¹¹+C₂₀=2+4=6. 

A¹₃=0

 

Следовательно, расчет окончен, оптимальная схема приведена на рисунке 2. Затраты равны 6 ед.

 

 

 

 

 

 

 

 

        

               

  

 

Метод Прима

Алгоритм этого метода отличается от вышеописанного только способом выбора вершины- претендента, т. е. построением множества пометок t_ij(Шаг 0). Описываемый подход основан на идее выбора вершины, ближайшей к S₀ (центральному обрабатывающему устройству), или к вершине S_j, уже соединенной сетью с S₀.

Каждой вершине S_j приписывается пометка w_j, причем в начале расчетов w₀=0, w_j=-, т.е. в сеть входит только вершина S₀.

 

Шаг 0. Подсчитывается множество Т= { t_ij}

t_ij= C_ij- w_j  для тех вершин, где w_j=0.

Конечные значения имеют только t_i0, равные стоимости C_i0(т. к. w₀=0), а все остальные равны . Дальше выполняются те же шаги, что и в методе Ежи- Вильямса.

Шаг 1. Определяется наименьшее значение t_ij, т. е. вершина S_i, ближайшая к S₀(на 1 итерации).

                               { t_ij}= t_kj

Шаг 2. Осуществляются проверки:                                            

                            a_k>0            a_k<r_kj 

                                                       a_k+a_j<r_j0

Шаг 3. Вычисляются значения:                                                                

                            a_k^н=0           a_j^н=a_j+a_k                                                                                                

                            r_kj^н=r_ij-a_k          F^’=F⁰+C_kj     

Полагается w_k=0                                                                   3       

Переход к шагу 0 следующей итерации.

 

Пример расчета приводится ниже

 

Проиллюстрируем алгоритм, описанный выше, примером. Пусть w₀=0, w_j=-. С учетом данных таблицы 3 подсчитаем значения t_ij.

Шаг 0.

Т:  t₁₀= C₁₀- w₀=1-0=1;

t₂₀= C₂₀- w₀=4-0=4;

t₃₀= C₃₀- w₀=3-0=3;

         t₁₂= C₁₂- w₂=2+ w₂=, t₁₃=;

t₂₁= C₂₁-  w₁=3+ w₁=, t₂₃=_;

t₃₁= C₃₁-  w₁=1+ w₁=_; t₃₂=_.

 

_{Шаг 1. Определим}  { tij}

{ t_ij}= t₁₀=1

Шаг 2.        а₁=2>0; r₁₀=5; a₁<r₁₀.

Выполнение условий позволяет перейти к шагу 3.

 

Шаг 3. Вычислим новые значения:

а¹₁=0; a¹₀=-8+2=-6; r¹₁₀=5-2=3; F=C₁₀=1.

Положим w₁=0; t₁₀=  и перейдем к шагу 0.

 

Шаг 0. Подсчитаем:

Т¹:      t₂₁= C₂₁-  w₁=3- 0=3_;

t₃₁= C₃₁-  w₁=1- 0=1.

Шаг 1.        {TUT¹}= t₃₁, т. е. S₃=>S₁.

Шаг 2.        а₃=3>0; r₃₁=5>a₃; a₁¹+a₃=0+3 r₁₀=3.

Шаг 3.

                                                         a₃¹=0; a₀¹¹=-6+3=-3.

                                                        r₁₀¹¹=3-3=0.

                                                         r₃₁¹=5-3=2.

                                                        F¹=F=C₃₁=1+1=2

 

 

 

Положим  w₃=0; t₃₁= _{и перейдем к шагу 0.}

Шаг 0.

Т²: t₂₃=С₂₃- w₃=1.

Шаг 1. Определим {TUT¹ UT²}= {t_ij}=t₂₃.

Шаг 2. а₂=3>0; r₂₃=5>a₂; r₃₁¹=2<a₂, следовательно, соединение S₂=>S₃ невозможно, положим t₂₃= и перейдем к шагу 1.

Шаг 1. {TUT¹ UT²}= t₂₀=2.

Шаг 2. а₂=3>0; r₂₀=5>а₂,

Шаг 3. а₂¹=0; r₂₀¹=5-3=2; а₀¹¹¹=-3+3=0

         F=2+4=6

Поскольку все а_i¹=0, задача решена.

 

 

 

 

 

 

        

 

 

 

                                   

	Рисунок 6

 

 

 

Синтез двухуровневой централизованной сети

Рассмотрим алгоритм синтеза двухуровневой сети, включающей заданное число терминалов T_i, i=1,..n, некоторое допустимое множество концентраторов K_j (j=1,..m), места, расположения которых известны, а количество должно быть выбрано в результате решения задачи. Центральное обрабатывающее устройство (ЭВМ) обозначим К₀. Заданы стоимости создания концентраторов f_j и количество терминалов, которые можно подключить к каждому концентратору, r_j.Если к концентратору подключен хотя бы один терминал, то он называется открытым, в противном случае – закрытым.

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

Итак, заданными являются:

- множества терминалов Т_i и концентраторов K_j (i=1,..n; j=1,2,…m),

ЭВМ – К₀;

- стоимости линий связи, заданные матрицей стоимости С=ççС_ijçç,

i=1,..n; j=0,1,…m;

- стоимости создания концентраторов f₁,f₂,…f_m;

- количество возможного подключения терминалов r_j.

Определить:

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

- схему подключения к ним терминалов;

- стоимость сети.

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

 

Алгоритм метода добавления

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

Шаг 0. Первоначально считаем, что все концентраторы закрыты, а терминалы присоединены к ЭВМ - к К₀. Затраты на создание такой сети равны сумме соединения терминалов с ЭВМ, т. е. сумме элементов столбца, соответствующего К₀, т. е.

F⁰=С_i0.

Очевидно, что это самое дорогое решение.

Итерация 1.

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

Шаг 1. Откроем К₁. Эффект от изменения присоединения S_i к К₁ вместо К₀ определим по формуле

                                               С_i0- C_i1.                                                      (*)

Очевидно, что присоединить к К₁ целесообразно только те S_i, для которых подсчитанные разности (*) будут положительными. Однако число таких присоединяемых S_i ограничено r₁. Подсчитаем эффект, учитывая затраты f₁ на создание концентратора К₁.

F₁¹=F⁰- (C_i0-C_i1)- … (C_j0-C_j1) +f₁.

(включены только (C_i0-C_i1)>0, число их меньше r₁).

Аналогичных шагов будет m (по числу концентраторов).

Шаг (m+1). Определяются наименьшие затраты:

{F₁¹, F₂¹, … F_m¹}= F_j¹

Следовательно, откроем концентратор К_j, присоединив к нему {S_g, S_l, S_к}.

Итерация 2.

Считая открытым концентратор K_j, будем открывать по очереди еще по одному концентратору.

Шаг 1. Откроем К₁при открытом K_j,оценим:

(C_i0-C_i1) для i, не присоединенных к K_j;                                             (**)

(C_gj-C_g1) для g, l, … k, т. е. для тех S₁, которые присоединены к K_j.

Выбираются r₁ наибольших разностей (**) и подсчитываются затраты:

F_1,j²=F_j^’- (C_gx-C_g1)+f₁.

Шагов будет m-1 (по числу закрытых еще концентраторов).

Шаг m. Определяется наименьшее значение функции:

min {F_j1², F_j2², … F_jm²}, jm.

Итерация 3.

Анализируется возможность открытия третьего концентратора при уже открытых двух.

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

Пример

Пусть задано 5 терминалов и 3 концентратора, к каждому из которых можно присоединить по 2 терминала. В таблице 8 приведена матрица затрат.

 

            Таблица 8                                     

	K0	K1	K2	K3
T1	8	4	6	6
T2	10	5	3	8
T3	3	4	0	7
T4	4	12	6	1
T5	12	10	8	0

 

 

 

f₁=4; f₂=3; f₃=2; r=2

 

Шаг 0. Присоединим все терминалы к ЭВМ (рисунок 7) и подсчитаем затраты:

 

F₀=С_i0=8+10+3+4+12=37.

 

 

 

 

 

 

 

 

 

                           

 

                                 Рисунок 7

 

 

Итерация 1.

Шаг 1. Откроем К₁.

C₁₀- C₁₁=8-4=4

C₂₀- C₂₁=10-5=5

C₃₀- C₃₁=3-4=-1

C₄₀- C₄₁=4-12=-8

C₅₀- C₅₁=12-10=2

_{Выберем две наибольшие разности и подсчитаем новое значение функции стоимости:}

_{F11=37-(C10-C11)-(C20-C21)+f1=37-4-5+4=32.}

T₁, T₂=>K₁

Шаг 2. Откроем К₂:

C₁₀- C₁₂=8-6=2

C₂₀- C₂₂=10-3=7

C₃₀- C₃₂=3-0=3

C₄₀- C₄₂=4-6=-2

C₅₀- C₅₂=12-8=4

Выберем две наибольшие разности, соответствующие варианту прикрепления Т₂ и Т₅ к К₂.

_{F21=37-(C20-C22)-(C50-C52)+f2=37-7-4+3=29.}

T₂, T₅=>K₂.

Шаг 3. Откроем концентратор К₃

C₁₀- C₁₃=8-6=2

C₂₀- C₂₃=10-8=2

C₃₀- C₃₃=3-7=-4

C₄₀- C₄₃=4-1=3

C₅₀- C₅₃=12-0=12

                                               _{F31=37-(C40-C43)-(C50-C53)+f3=37-3-12+2=24.}

T₄, T₅=>K₃.

Шаг 4. Выберем наилучший вариант прикрепления:

{F₁^’, F₂^’, F₃^’}= {32,29,24}=24,

что соответствует T₄, T₅=>K₃.

 

 

 

 

 

 

 

 

 

 

 

                                            Рисунок 8

 

Итерация 2.

Шаг 1. При открытом К₃ откроем К₁: подсчитаем C_i0-C_i1 для i=1,2,3;  C_i3-C_i1 для i=4,5.

C₁₀- C_i1=8-4=4

C₄₃- C₄₁=1-12=-11

C₂₀- C₂₁=10-5=5

C₅₃- C₅₁=0-10=-10

C₃₀- C₃₁=3-4=-1

_{F3,12=24-(C10-C11)-(C20-C21)+f1=24-4-5+4=19.}

T₁, T₂=>K₁.

Шаг 2. При открытом К₃ откроем К₂: подсчитаем C_i0-C_i2 для i=1,2,3;  C_i3-C_i2 для i=4,5.

C₁₀- C_i2=8-6=2                                  C₄₃- C₄₂=1-6=-5

C₂₀- C₂₂=10-3=7                               C₅₃- C₅₂=0-8=-8

C₃₀- C₃₂=3-0=3

_{F3,22=F31-(C20-C22)-(C30-C32)+f2=24-7-3+3=17.}

T₂, T₃=>K₂.

Шаг 4.

{F₃₁², F₃₂²}= {19,17}=17, T₂, T₃=>K₂.

 

 

 

 

 

 

 

 

 

 

 

 

Итерация 3.

Откроем концентратор К₁ при открытых К₂ и К₃. Подсчитаем целесообразность подсоединения к нему всех терминалов:

C₁₀- C₁₁=8-4=4

C₂₂- C₂₁=3-5=-2

C₃₂- C₃₁=0-4=-4

C₄₃- C₄₁=1-12=-11

C₅₃- C₅₁=0-10=-10

Положительная разность только одна:

_{F33,2,1=F23,2=(C10-C11)+f1=17-4+4=17.}

_{Поскольку открытие К1 не уменьшит целевую функцию, в качестве оптимального можно принять любой вариант сети- при открытых концентраторах К2 и  К3 (рисунок 9) или открытых всех трех концентраторах (рисунок 10), F3,2,13=17.}

 

 

 

 

 

 

 

 

 

 

 

 

5 Методические указания к контрольной работе 2

 

Задача 1 выполняется  после изучения раздела «Телефонные сети программы». Перед решением задачи рекомендуется внимательно прочитать подраздел 4.7 литературы 1, и рассмотреть полярно-числовой код [7] и многочастотный код таблица 4.2 из [7]. Кроме того, нужно внимательно изучить способы передачи сигналов, обратив особое внимание на способы импульсного челнока и безынтервального пакета. При передаче информации безынтервальным пакетом затруднено распознавание одинаковых сигналов, следующих друг за другом. Поэтому при передаче информации о повторяющихся цифрах каждая четная повторяющаяся цифра передается в многочастотном коде комбинацией подмены, представляющей собой сочетание частот f1, f11, где f1=900 Гц,  f11=1700 Гц.

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

Перед решением задачи 2 рекомендуется внимательно прочитать материал, изложенный на с. 125-128 [7]. Схемы нужно разработать, используя минимальное количество МКС. Поэтому все выходы каждой вертикали каждого МКС должны быть использованы полностью. В схеме ВПВП расчет рекомендуется начинать с выбора числа выходов из одного коммутатора звена А –m a, в схеме ПВПВ этот расчет нужно начинать с выбора числа входов в один коммутатор звена А –na. В том  и другом случае нужно помнить, что ёмкость вертикали заданного МКС равна 10 (m=10). В ряде вариантов оптимальное построение схемы имеет место при запараллеливании вертикалей или на звене А, или на звене В.

Изобразить схему можно или в координатном виде или в символическом по образцу  рисунка 3.9 a  или рисунка 3.21b [1].

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

Задача 3 выполняется после усвоения принципов построения ступеней группового искания координатных АТС.

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

Напомним, что для построения блоков ГИ преимущественно применяются трехзвенные МКС. Схема контактного поля трехпозиционного МКС приведена на рисунке 2.10 [7, стр. 67]. На схеме видно, что для выбора выхода первого десятка должны сработать первый переключающий электромагнит, а при выборе выхода второго десятка должен сработать второй переключающий электромагнит и выбирающий электромагнит, номер которого определяется цифрой единиц заданного выхода.

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

Приложение А

№ 0.

	S0	S1	S2	S3	S4	S5	a0=-15
S1	5	-	3	8	7	2	a1=3
S2	7	4	-	5	4	3	a2=4
S3	2	3	1	-	4	1	a3=3
S4	1	7	4	6	-	5	a4=2
S5	4	8	3	4	5	-	a5=3

r=6

№ 2.

	S0	S1	S2	S3	S4	S5	a0=-18
S1	2	-	7	9	6	3	a1=3
S2	5	7	-	11	10	4	a2=5
S3	6	9	11	-	7	3	a3=4
S4	1	6	10	7	-	7	a4=2
S5	10	3	4	3	7	-	a5=4

r=7

№ 4.

	S0	S1	S2	S3	S4	S5	S6	a0 = -22
S1	10	-	6	4	5	7	3	a1=2
S2	3	6	-	2	4	8	6	a2=4
S3	4	4	2	-	7	9	3	a3=2
S4	5	5	4	7	-	4	6	a4=3
S5	2	7	8	9	4	-	5	a5=5
S6	4	3	6	3	6	5	-	a6=5

r=8

№ 6.

	S0	S1	S2	S3	S4	S5	a0=-22
S1	10	-	8	13	15	11	a1=5
S2	14	8	-	7	4	15	a2=4
S3	17	13	7	-	11	9	a3=5
S4	21	15	4	11	-	7	a4=2
S5	12	11	15	9	7	-	a5=6

r=10

№ 8.

	S0	S1	S2	S3	S4	S5	a0=-15
S1	5	-	3	8	7	2	a1=3
S2	7	4	-	5	4	3	a2=4
S3	2	3	1	-	4	1	a3=3
S4	1	7	4	6	-	5	a4=2
S5	4	8	3	4	5	-	a5=3

r=6

 

№ 1.

	S0	S1	S2	S3	S4	S5	а0=-15
S1	2	-	7	9	6	4	a1=3
S2	5	7	-	11	10	8	a2=5
S3	1	9	11	-	10	8	a3=2
S4	6	4	10	8	-	11	a4=2
S5	10	11	8	4	7	-	a5=3

r=5

№ 3.

	S0	S1	S2	S3	S4	S5	a0=-12
S1	3	-	5	4	7	10	a1=2
S2	5	5	-	2	1	10	a2=1
S3	7	4	2	-	4	2	a3=3
S4	6	7	1	4	-	8	a4=4
S5	1	10	6	1	8	-	a5=2

                   r=5

№ 5.

	S0	S1	S2	S3	S4	S5	S6	a0= -23
S1	5	-	4	3	7	5	2	a1=4
S2	7	4	-	8	3	1	4	a2=4
S3	8	3	8	-	11	17	9	a3=6
S4	2	7	3	11	-	6	5	a4=2
S5	4	5	1	17	6	-	7	a5=3
S6	11	2	4	9	5	7	-	a6=4

                   r=6

№ 7.

	S0	S1	S2	S3	S4	S5	a0=-25
S1	6	-	8	12	4	10	a1=7
S2	12	8	-	11	6	9	a2=4
S3	15	12	11	-	7	13	a3=5
S4	9	4	6	7	-	5	a4=3
S5	7	10	9	13	5	-	a5=6

                   r=7

№ 9.

	S0	S1	S2	S3	S4	S5	a0=-27
S1	11	-	9	7	11	4	a1=7
S2	13	9	-	6	10	12	a2=3
S3	17	7	6	-	4	8	a3=9
S4	10	11	10	4	-	5	a4=2
S5	14	4	12	8	5	-	a5=6

                   r=9

Приложение В

№ 1.

	K0	K1	K2	K3
T1	7	4	6	9
T2	5	2	0	8
T3	2	4	6	5
T4	1	4	2	10
T5	8	7	4	12
T6	7	5	9	0
T7	10	6	11	4

r=3; f₁=4; f₂=2; f₃=5.

 

№ 2.

	K0	K1	K2	K3	K4
T1	7	8	0	6	4
T2	4	5	2	5	3
T3	9	7	12	3	6
T4	12	7	9	0	10
T5	4	5	7	3	2
T6	7	0	5	4	13
T7	10	5	10	11	15

r=2; f₁=1; f₂=5; f₃=4; f₄=2.

 

 

№ 3.

	K0	K1	K2	K3
T1	7	4	5	3
T2	5	4	7	9
T3	12	8	11	0
T4	10	4	5	7
T5	14	8	6	9
T6	8	3	2	4

r=3; f₁=5; f₂=6; f₃=4.

 

№ 4.

	K0	K1	K2	K3	K4
T1	5	7	3	0	4
T2	6	7	4	2	8
T3	8	5	0	10	11
T4	10	8	9	13	15
T5	15	11	8	12	0
T6	8	3	4	5	6

r=3; f₁=4; f₂=5; f₃=6; f₄=2.

 

 

№ 5.

	K0	K1	K2	K3
T1	4	0	3	5
T2	3	4	2	1
T3	2	4	0	6
T4	3	2	4	5
T5	5	6	3	2

r=2; f₁=2; f₂=3; f₃=2.

 

 

№ 6.

	K0	K1	K2	K3
T1	4	2	5	3
T2	2	5	3	6
T3	5	8	0	7
T4	7	4	4	2
T5	3	4	5	1

r=2; f₁=6; f₂=2; f₃=3.

 

 

№ 7.

	K0	K1	K2	K3
T1	4	0	2	3
T2	8	5	4	10
T3	7	4	1	2
T4	4	5	2	0
T5	3	4	2	5
T6	9	7	4	3

r=3; f₁=f₂=4; f₃=2.

 

 

№ 8.

	K0	K1	K2	K3	K4
T1	4	0	2	2	3
T2	8	5	6	4	10
T3	7	4	3	1	2
T4	4	5	11	2	0
T5	3	4	9	2	5
T6	9	7	10	4	3

r=2; f₁=3; f₂=2; f₃=3.