Защита от ошибок в сетях

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

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

Выделяют две основные причины возникновения ошибок при пере­даче информации в сетях:

• сбои в какой-то части оборудования сети или возникновение не­благоприятных объективных событий в сети (например, коллизий при использовании метода случайного доступа в сеть). Как пра­вило, система передачи данных готова к такого рода проявлениям и устраняет их с помощью предусмотренных планом средств;

• помехи, вызванные внешними источниками и атмосферными явле­ниями.

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

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

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

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

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

Другой групповой метод, также не требующий перекодирования информации, предполагает передачу данных блоками с количествен­ной характеристикой блока. Такими характеристиками могут быть: число единиц или нулей в блоке, контрольная сумма передаваемых символов в блоке, остаток от деления контрольной суммы на посто­янную величину и др. На приемном пункте эта характеристика вновь подсчитывается и сравнивается с переданной по каналу связи. Если характеристики совпадают, считается, что блок не содержит ошибок. В противном случае на передающую сторону поступает сигнал с тре­бованием повторной передачи блока. В современных ТВС такой ме­тод получил самое широкое распространение.

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

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

К числу наиболее важных показателей корректирующих кодов относятся:

• значность кода, или длина кодовой комбинации, включающей ин­формационные символы (т) и проверочные, или контрольные, сим­волы (К). Обычно значность кода п есть сумма т+К;

• избыточность кода K_изб, выражаемая отношением числа конт­рольных символов в кодовой комбинации к значности кода;

• корректирующая способность кода К_кс, представляющая собой отношение числа кодовых комбинаций L, в которых ошибки были обнаружены и исправлены, к общему числу переданных кодовых комбинаций М в фиксированном объеме информации.

Выбор корректирующего кода для его использования в данной ТКС зависит от требований по достоверности передачи информации. Для правильного выбора кода необходимы статистические данные о за­кономерностях появления ошибок, их характере, численности и рас­пределении во времени. Например, корректирующий код, обнаружи­вающий и исправляющий одиночные ошибки, эффективен лишь при условии, что ошибки статистически независимы, а вероятность их появления не превышает некоторой величины. Он оказывается непри­годным, если ошибки появляются группами. При выборе кода надо стремиться, чтобы он имел меньшую избыточность. Чем больше коэффициент К_из6, тем менее эффективно используется пропускная способ­ность канала связи и больше затрачивается времени на передачу ин­формации, но зато выше помехоустойчивость системы.

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

В этом коде контрольные символы занимают позиции, соответ­ствующие значениям 2°, 2¹, 2², 2³ и т.д., т.е. позиции с номерами 1, 2, 4, 8 и т.д. (нумерация позиций кодовой комбинации — слева направо). Количество контрольных символов в кодовой комбинации должно быть таким, чтобы в процессе декодирования сформированное кор­ректирующее число (в двоичной системе счисления) могло указать позицию кодовой комбинации с максимальным номером. Например, для пяти информационных разрядов потребуется четыре контрольных. В полученной кодовой комбинации позиция с наибольшим номером будет 9-й, что записывается как 1001, т.е. требует четырех разрядов.

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

При определении значения 1-го контрольного символа, размещае­мого на 1-й позиции кодовой комбинации, проверяются на четность те информационные позиции, двоичные изображения номеров кото­рых содержат единицу в младшем разряде, т.е. проверяются позиции с нечетными номерами. При определении значения 2-го контрольного символа, размещаемого на 2-й позиции кодовой комбинации, прове­ряются на четность те информационные позиции, двоичные изобра­жения номеров которых содержат единицу во 2-м разряде, т.е. пози­ции с номерами 3, 6, 7, 10, 11 и т.д. Значение 3-го контрольного симво­ла, размещаемого на 4-й позиции кодовой комбинации, определяется путем контроля на четность тех информационных позиций, двоичные изображения номеров которых содержат единицу в 3-м разряде, т.е. позиции с номерами 5, 6, 7, 12 и т.д. Аналогично устанавливаются значения и других контрольных символов.

В процессе декодирования формируется корректирующее число (КЧ), разрядность двоичного изображения которого устанавливается по указанному выше правилу. Значения разрядов этого числа опреде­ляются по правилам, аналогичным тем, которые использовались для определения значений контрольных символов в процессе кодирова­ния. Разница лишь в том, что при определении значений разрядов КЧ проверяются на четность не только информационные позиции, но и контрольные. Например, для определения значения младшего разряда КЧ проверяются на четность те позиции кодовой комбинации, двоич­ные изображения номеров которых содержат единицу в младшем раз­ряде, т.е. позиции с нечетными номерами 1, 3, 5, 7 и т.д.

Значение корректирующего числа определяет номер позиции ко­довой комбинации, в которой произошла ошибка. Для ее исправления необходимо значение кода в этой позиции изменить на противополож­ное (0 на 1 или 1 на 0). Если КЧ равно нулю, то это указывает на отсутствие ошибок в принятой кодовой комбинации. Процесс деко­дирования завершается выделением из кодовой комбинации инфор­мационных символов.

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

Системы передачи с обратной связью делятся на системы с ре­шающей обратной связью и системы с информационной обратной связью.

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

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

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

Пример 13.3. В системах с решающей обратной связью ARQ, где реали­зуется непрерывный автоматический запрос на повторение и концепция скользящих окон, для двух возможных вариантов защиты от ошибок (си­стемы с выборочным повторением и системы с возвращением на N_K кад­ров) и заданных характеристиках линий связи и объеме передаваемой ин­формации найти время на передачу этой информации и необходимый объем буферного ЗУ на приемном пункте.

Исходные данные:

Е_инф = 2 Мбит — объем передаваемой информации;

L_k = 7 — длина окна (количество кадров в окне);

R_k = 4096 бит — длина одного кадра;

V _k = 9600 бит/с — пропускная способность канала связи;

М_к = 1000 — количество каналов в многоканальной линии связи;

N_ош = 1 — число кадров в окне, принятых с ошибками. Ошибочные кадры передаются повторно. Для упрощения условия примера и опреде­ленности будем считать, что в каждом окне ошибочный кадр имеет второй номер (это важно для оценки систем с возвращением на N_k кадров).

Постановка задачи иллюстрируется на рис. 13.2. Данные передаются от узла А к узлу В по прямому каналу. В семикадровом окне на приемном пункте (в узле В) во втором кадре обнаружены ошибки, и сигнал об этом (NAK 2) по обратному каналу передается в узел А (рис. 13.2, а). В протоко­ле ARQ реализуется один из двух методов обнаружения и повторной пере­дачи искаженных данных:

• выборочное повторение (рис. 13.2, б), когда повторно передается только искаженный кадр данного окна. Все другие кадры этого окна, поступившие в узел В после искаженного кадра (в нашем примере это кадры с номерами от 3 до 7), временно хранятся на приемном пункте в буферном ЗУ;

• возвращение на n_k кадров (рис. 13.2, в), когда повторно передается не только искаженный кадр, но и все кадры данного окна, посту­пившие вслед за искаженным (предполагается, что источник, по­служивший причиной искажения второго кадра, продолжает дей­ствовать). Здесь надобность в буферном ЗУ пропадает. Рассчитаем показатели для первого варианта системы ARQ — с выбо­рочным повторением.

Время на передачу заданного объема информации определяется по формуле

где n_ok — количество окон в передаваемом объёме информации, причем

в

Рис. 13.2. Система с решающей обратной связью ARQ:

а — передача данных по прямому каналу; б — выборочное повторение;

в — возвращение на n_k кадров

Следовательно,

T₁ = 70 • (7+1) • 4096 / 9600 = 238,9 с.

Необходимый объем буферного ЗУ:

(13.3)

где L_3у — количество кадров данного окна, временно сохраняемых в буферном ЗУ (в нашем примере L_3y = 5).

Следовательно, Е_зу = 5 • 4096 • 1000 = 20 480 000 бит.

Для второго варианта системы ARQ — с возвращением на n_k кадров (в нашем примере N_K = 6) — определяется только время на передачу ин­формации:

(13.4)

Как видно, первый вариант предпочтительнее по времени на передачу заданного объема информации, зато требует на приемном пункте буфер­ной памяти. Разница в значениях показателей Т1, и Т₂ будет тем больше, чем выше интенсивность ошибок в линиях связи.