Методы защиты от ошибок

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

При определении значения 1-го контрольного символа, размещаемого на 1-й позиции кодовой комбинации, проверяются на четность те информационные позиции;

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Рассчитаем показатели для первого варианта системы ARQ - с выборочным повторением.

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

T₁=N_ok*(L_k+N_ош)*R_k/V_k (12.1)

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

N_ok =E_инф/L_k*R_k;

N_ok =2000000/7*4096=70. (12.2)

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

Т₁ = 70*(7 +1)*4096 / 9600 = 238,9 с. (12.3)

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

E_зу=L_зу*R_К*M, (12.4)

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

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

Е_зу = 5*4096*1000 = 20 480 000 бит.

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

Т₂=N_ок(L_k+N_k)*R_к/V_K; (12.5)

T₂ = 70*(7 + 6)* 4096 / 9600 = 388,3 с.

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