ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 07.04.2021
Просмотров: 404
Скачиваний: 1
13 Обработка ошибок. Результаты теории кодирования.
infonets_04.pdf– из лекций Коваля.
Теория кодирования Хемминга. Простые коды характеризуются тем, что для передачи
информациииспользуются все кодовые слова(комбинации), количество которыхравно N=q
n
(q -
основание кода, а n -длина кода. Тогда задача кодирования заключаетсявполучении при передаче
для каждой k -элементной комбинации из множества q
k
соответствующего ей кодового
словадлиною n из множества q
n
.Задача декодированиясостоитв полученииk - элементной
комбинации из принятого n -разрядного кодового слова приодновременном обнаружении
илиисправлении ошибок
Параметры помехоустойчивыхкодов:
1.
Длина кода –n
2.
Длина информационной последовательности –k
3.
Длина проверочной последовательности – r = n –k
4.
Скорость кода – R = k/n
5.
Избыточность кода – 1/R
6.
Кодовое расстояние между двумя кодовымисловами (расстояние Хэмминга) - это
числопозиций, в которых они отличаются друг от друга.
7.
Кодовое расстояние кода d
0
- это наименьшеерасстояние Хэмминга между различными
парами кодовых слов
Основные результаты. Основные зависимости между кратностьюобнаруживаемых ошибок t
о
,
исправляемыхошибок t
u
, исправлением стираний t
c
и кодовымрасстоянием d
0
кода:
d
0
≥ t
0
+ 1; d
0
≥ t
0
+ t
u
+ 1 (при t
0
>t
u
);
d
0
≥ 2 t
u
+ 1; d
0
≥ 2 t
u
+ t
c
+ 1
d
0
≥ t
c
+ 1;
Стиранием называется потеря значенияпередаваемого символов некоторой позициикодового
слова, которая известна.Т.о. расстояние Хэмминга между верными кодовымисловами должно
быть больше, чем оно может получиться в результате ошибок.
Граница Хэмминга близкак оптимальной длявысокоскоростных q-ичного и двоичного кодов
n – k ≥ log
q
∑
i = 0…tu
( C
n
i
* ( q - 1)
i
);
Обработка ошибок может быть осуществлена с помощью контрольных сумм. Контрольные суммы
– значение, полученное путем сложения битовинформационной последовательности:
Позволяет обнаруживать однократные ошибки (в случае нескольких – нечетное количество).
Ещё количество ошибок можно уменьшить введением бита паритета.
14 Полиномиальное кодирование (CRC).
На практике активно применяются полиномиальные коды или циклические избыточные коды
(CyclicRedundancyCode — CRC).
CRC коды построены на рассмотрении битовой строки как строки коэффициентов полинома. k-
битовая строка соответствует полиному степени k − 1. Самый левый бит строки — коэффициент
при старшей степени. Например, строка 110001 представляет полином x5 + x4 + x0. Коэффициенты
полинома принадлежат полю
вычетов по модулю 2.
Основная идея заключена в том, чтобы пересылать только такие сообщения, полиномы которых
делятся на некоторый фиксированный полином G(x). Если мы получаем сообщение, что чей –то
полином не делится на G(x), значит при передаче сигнал был искажен. Мы не заметим ошибок,
если они один допустимый полином (то есть полином делящийся на G(x)) преобразовали в другой
допустимый полином. Полином G(x) тем лучше, чем больше среднее расстояние Хемминга на
парах допустимых полиномов.
В CRC используется добавление к нашему сообщению некоторого количества бит так, чтобы
результирующий полином делился на G(x).
15 Различные подходы к управлению ресурсами канала (статические, динамические).
16 Протоколы локальных сетей института IEEE (802). Ethernet-сети. CSMA/CD.
http://www.citforum.ru/nets/protocols2/2_02_00.shtml
http://ru.wikipedia.org/wiki/Ethernet
В 1980 году в институте IEEE был организован "Комитет 802 по стандартизации локальных сетей", в
результате работы которого было принято семейство стандартов IEEE 802.х, которые содержат
рекомендации для проектирования нижних уровней локальных сетей - физического и канального.
Позже результаты его работы легли в основу комплекса международных стандартов ISO 8802-
1...5. Эти стандарты были созданы на основе очень распространенных фирменных стандартов
сетей Ethernet, ArcNet и TokenRing.
Стандарт IEEE 802 содержит несколько разделов:
В разделе 802.1 приводятся основные понятия и определения, общие характеристики и
требования к локальным сетям.
Раздел 802.2 определяет подуровень управления логическим каналом LLC.
Разделы 802.3 - 802.5 регламентируют спецификации различных протоколов подуровня
доступа к среде MAC и их связь с уровнем LLC:
o
стандарт 802.3 описывает коллективный доступ с опознаванием несущей и
обнаружением
конфликтов
(Carriersensemultipleaccesswithcollisiondetection
-
CSMA/CD), прототипом которого является метод доступа стандарта Ethernet;
o
стандарт 802.4 определяет метод доступа к шине с передачей маркера
(Tokenbusnetwork), прототип - ArcNet;
o
стандарт 802.5 описывает метод доступа к кольцу с передачей маркера
(Tokenringnetwork), прототип - TokenRing.
Ethernet —
, преимущественно локальных.
Стандарты Ethernet определяют проводные соединения и электрические сигналы на физическом
уровне, формат кадров и протоколы управления доступом к среде — на
OSI
. Ethernet в основном описывается стандартами
CSMA/CD (CarrierSenseMultipleAccesswithCollisionDetection — множественный доступ с контролем
несущей и обнаружением коллизий) — технология(802.3) множественного доступа к общей
передающей среде в
. CSMA/CD
используется как в обычных сетях типа
, так и в высокоскоростных сетях (
17 Оборудование Ethernet сетей. Сегментация. Коммутаторы в сетях Ethernet.
http://maxlevel.by.ru/txt/seti_7.htm
http://www.bestreferat.ru/referat-25669.html
http://webdev.dlink.ru/technology/switche1.php
При оборудовании сетей Ethernet в качестве передающей среды используется
. Метод управления доступом (для сети на коаксиальном
множественный доступ с контролем несущей и обнаружением коллизий
CarrierSenseMultipleAccesswithCollisionDetection), скорость передачи данных 10 Мбит/с, размер
пакета от 72 до 1526
. Режим работы – полудуплексный. Количество узлов в одном
разделяемом сегменте сети ограничено предельным значением в 1024 рабочих станции
Сегментация. Производительность Ethernet можно повысить: разделите перегруженный сегмент
на два сегмента, соединенные мостом или маршрутизатором. Трафик в каждом сегменте при
этом уменьшается, так как меньшее число компьютеров пытается осуществить передачу, и время
доступа к кабелю сокращается. Разделение сегмента — удачный ход при подсоединении к сети
новых пользователей или установке новых приложений, интенсивно работающих с сетью
(например, баз данных и видеоприложений).
Коммутатор Ethernet представляет собой устройство для организации сетей большого размера.
Предназначен для соединения нескольких
Коммутатор Ethernet поддерживает внутреннюю таблицу, связывающую порты с адресами
подключенных к ним устройств. Используя таблицу адресов и содержащийся в пакете адрес
получателя, коммутатор организует виртуальное соединение порта отправителя с портом
получателя и передает пакет через это соединение.
18 Понятие маршрутизации пакетов данных. Алгоритмы маршрутизации,
классификация.
http://ru.wikipedia.org/wiki/
. служат для соединения нескольких сетей на основе
. Обычно
маршрутизатор использует адрес получателя, указанный в пакетах данных, и определяет по
таблице маршрутизации путь, по которому следует передать данные. Если в таблице
маршрутизации для адреса нет описанного маршрута, пакет отбрасывается.
содержит информацию, на основе которой маршрутизатор принимает
решение о дальнейшей пересылке пакетов. Таблица маршрутизации может составляться двумя
способами: 1 статическая маршрутизация — когда записи в таблице вводятся и изменяются
вручную, 2 динамическая маршрутизация — когда записи в таблице обновляются автоматически
при помощи одного или нескольких
Маршрутизаторы помогают уменьшить загрузку сети, благодаря её разделению на
или
, а также благодаря фильтрации пакетов.
19.Коммутация каналов, пакетов, сообщений. STM.
http://www.raisecom.ru/articles/3283/
http://lanhelper.ru/seti/2/22
Задача коммутации — определение потоков и соответствующих маршрутов, и их фиксация в
таблицах сетевых устройств. Есть два подхода к решению задач коммутации: 1 коммутация
каналов (circuitswitching), 2 - коммутация пакетов.
Коммутация каналов.При коммутации каналов коммутационная сеть образует между конечными
узлами непрерывный составной физический канал из последовательно соединенных
коммутаторами промежуточных канальных участков. В сети с коммутацией каналов перед
передачей данных всегда необходимо выполнить процедуру установления соединения, в
процессе которой и создается составной канал. И только после этого можно начинать передавать
данные.
Коммутация пакетов.Эта техника коммутации была специально разработана для эффективной
передачи компьютерного трафика. При коммутации пакетов все передаваемые пользователем
сообщения разбиваются в исходном узле на сравнительно небольшие части, называемые
пакетами. Каждый пакет снабжается заголовком, в котором указывается адресная информация,
необходимая для доставки пакета на узел назначения, а также номер пакета, который будет
использоваться узлом назначения для сборки сообщения.
Техника синхронного режима передачи (SynchronousTransferMode, STM, TimeDivisionMultiplexing,
TDM) – это коммутация каналов на основе техники разделения частот ( или разделения времени ).
20 IP-адресация. IP-маршрутизация. Маршрутизация в глобальной сети Internet. Протоколы
маршрутизации в Интернет.
http://net.e-publish.ru/p234aa1.html
http://net.e-publish.ru/p235aa1.html
http://opds.sut.ru/electronic_manuals/it_emd/it5.htm
IP-адрес – это уникальный числовой адрес, однозначно идентифицирующий узел, группу узлов
или сеть. IP-адрес имеет длину 4 байта и обычно записывается в виде четырех чисел (так