Методы защиты информации от ошибок

Методы
защиты от ошибок при передаче информации
в ТКС.

Вопросы :

1. Методы защиты
   от ошибок при передаче и информации.

2. Помехоустойчивое
   (избыточное) кодирование

3. Системы передачи
   с обратной связью.

4. Групповые методы
   защиты от ошибок.

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

Изучив тему,
студент должен:

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

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

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

Тема №6. Методы
защиты от ошибок при передаче информации
в ТКС

1. Методы защиты от ошибок при передаче и информации

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

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

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

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

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

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

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

• помехоустойчивое
  кодирование;

• методы защиты
  от ошибок в системах передачи с обратной
  связью;

• групповые
  методы.

Соседние файлы в папке Лекции Вссит

• #
• #
• #
• #
• #
• #
• #
• #
• #

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

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

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

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

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

Помехи — это электрические возмущения, возникающие в самой аппаратуре или попадающие в нее извне.

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

Из групповых методов получили широкое применение мажоритар­ный метод.

Рекомендация для Вас — 13. Математическая модель изменения уровня жидкости.

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

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

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

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

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

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

6.2.1. Связность оконечных устройств

6.2.2. Автоматический запрос повторной передачи

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

6.2.1. Связность оконечных устройств

Оконечные устройства систем связи часто классифицируют согласно их связности с другими оконечными устройствами. Возможные типы соединения, показанные на рис. 6.6, называются симплексными (simplex) (не путайте с симплексными, или трансортогональными кодами), полудуплексными (half-duplex) и полнодуплексными (full-duplex). Симплексное соединение на рис. 6.6, а — это односторонняя линия связи.

Передача сигналов производится только от оконечного устройства А к оконечному устройству В. Полудуплексное соединение на рис. 6.6,б это линии связи, посредством которой можно осуществлять передачи сигналов в обоих направлениях, но не одновременно. И наконец, полнодуплексное соединение (рис. 6.6, в) — это двусторонняя связь, где передача сигналов происходит одновременно в обоих направлениях.

Передача только в одном направлении а)

а)

б)

в)

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

6.2.2. Автоматический запрос повторной передачи

Если зашита от ошибок заключается только в их обнаружении, система связи должна обеспечить средства предупреждения передатчика об опасности, сообщающие, что была обнаружена ошибка и требуется повторная передача. Подобные процедуры защиты от ошибок известны как методы автоматического запроса повторной передачи (Automatic Repeat Request — ARQ). На рис. 6.7 показаны три наиболее распространенные процедуры ARQ. На каждой схеме ось времени направлена слева направо. Первая процедура ARQ, запрос ARQ с остановками (stop-and-wait ARQ), показана на рис. 6.7, а. Ее реализация требует только полудуплексного соединения, поскольку передатчик перед началом очередной передачи ожидает подтверждения об успешном приеме (acknowledgement — АСК) предыдущей. В примере, приведенном на рисунке, третий блок передаваемых данных принят с ошибкой. Следовательно, приемник передает отрицательное подтверждение приема (negative acknowledgment — NAK); передатчик повторяет передачу третьего блока сообщения и только после этого передает следующий по очередности блок. Вторая процедура ARQ, непрерывный запрос ARQ с возвратом (continuous ARQ with pullback), показана на рис. 6.7,б. Здесь требуется полно-дуплексное соединение. Оба оконечных устройства начинают передачу одновременно: передатчик отправляет информацию, а приемник передает подтверждение о приеме данных. Следует .отметить,„что каждому блоку передаваемых данных присваивается порядковый номер. Кроме того, номера кадров АСК и NAK должны быть согласованы; иначе говоря, задержка распространения сигнала должна быть известна априори, чтобы передатчик знал, к какому блоку сообщения относится данный кадр подтверждения приема. В примере на рис. 6,7,б время подобрано так, что между отправленным блоком сообщений и полученным подтверждением о приеме существует постоянный интервал в четыре блока. Например, после отправки сообщения 8, приводит сигнал NAK, сообщающий об ошибке в блоке 4. При использовании процедуры ARQ передатчик «возвращается» к сообщению с ошибкой и снова передает всю информацию, начиная с поврежденного сообщения. И наконец, третья процедура, именуемая непрерывным запросом ARQ с выборочным повторением (continuous ARQ with selective repeat), показана на рис. 6.7, в. Здесь, как и во второй процедуре, требуется полнодуплексное соединение. Впрочем, в этой процедуре повторно передается только искаженное сообщение; затем передатчик продолжает передачу с того места, где она прервалась, не выполняя повторной передачи правильно принятых сообщений.

а)

б)

в)

Рис. 6.7. Автоматический запрос повторной передачи (ARQ): а) запрос

ARQ с остановками (полудуплексная связь); б) непрерывный запрос ARQ с возвратом (полнодуплексная связь); в) непрерывный запрос ARQ с выборочным повторением (полнодуплексная связь)

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

Главное преимущество схем ARQ перед схемами прямого исправления ошибок (forward error correction — FEC) заключается в том, что «обнаружение ошибок требует более простого декодирующего оборудования и меньшей избыточности, чем коррекция ошибок. Кроме того, она гибче; информация передается повторно только при обнаружении ошибки. С другой стороны, метод FEC может оказаться более приемлемым (или дополняющим) по какой-либо из следующих причин.

1. Обратный канал недоступен или задержка при использовании ARQ слишком велика.

2. Алгоритм повторной передачи нельзя реализовать удобным образом.

3. При ожидаемом количестве ошибок потребуется слишком много повторных передач.

Стратегии исправления ошибокПравить

Сетевое кодированиеПравить

Энергетический выигрышПравить

ПримечанияПравить

ЛитератураПравить

СсылкиПравить

Кодирование и защита от ошибок

Существует три наиболее распространенных орудия борьбы с ошибками в процессе передачи данных:

• коды обнаружения ошибок;
• коды с коррекцией ошибок, называемые также схемами прямой коррекции ошибок (Forward Error Correction — FEC);
• протоколы с автоматическим запросом повторной передачи (Automatic Repeat Request — ARQ).

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

1) Методы обнаружения ошибок

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

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

Контроль по паритету представляет собой наиболее простой метод контроля данных. В то же время это наименее мощный алгоритм контроля, так как с его помощью можно обнаружить только одиночные ошибки в проверяемых данных. Метод заключается в суммировании по модулю 2 всех битов контролируемой информации. Нетрудно заметить, что для информации, состоящей из нечетного числа единиц, контрольная сумма всегда равна 1, а при четном числе единиц — 0. Например, для данных 100101011 результатом контрольного суммирования будет значение 1. Результат суммирования также представляет собой один дополнительный бит данных, который пересылается вместе с контролируемой информацией. При искажении в процессе пересылки любого бита исходных данных (или контрольного разряда) результат суммирования будет отличаться от принятого контрольного разряда, что говорит об ошибке.
Однако двойная ошибка, например 110101010, будет неверно принята за корректные данные. Поэтому контроль по паритету применяется к небольшим порциям данных, как правило, к каждому байту, что дает коэффициент избыточности для этого метода 1/8. Метод редко применяется в компьютерных сетях из-за значительной избыточности и невысоких диагностических способностей.

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

Циклический избыточный контроль (Cyclic Redundancy Check — CRC) является в настоящее время наиболее популярным методом контроля в вычислительных сетях (и не только в сетях; в частности, этот метод широко применяется при записи данных на гибкие и жесткие диски). Метод основан на рассмотрении исходных данных в виде одного многоразрядного двоичного числа. Например, кадр стандарта Ethernet, состоящий из 1024 байт, будет рассматриваться как одно число, состоящее из 8192 бит. Контрольной информацией считается остаток от деления этого числа на известный делитель R. Обычно в качестве делителя выбирается семнадцати- или тридцатитрехразрядное число, чтобы остаток от деления имел длину 16 разрядов (2 байт) или 32 разряда (4 байт). При получении кадра данных снова вычисляется остаток от деления на тот же делитель R, но при этом к данным кадра добавляется и содержащаяся в нем контрольная сумма.
Если остаток от деления на R равен нулю, то делается вывод об отсутствии ошибок в полученном кадре, в противном случае кадр считается искаженным.

Этот метод обладает более высокой вычислительной сложностью, но его диагностические возможности гораздо шире, чем у методов контроля по паритету. Метод CRC обнаруживает все одиночные ошибки, двойные ошибки и ошибки в нечетном числе битов. Метод также обладает невысокой степенью избыточности. Например, для кадра Ethernet размером 1024 байта контрольная информация длиной 4 байта составляет только 0,4 %.

2) Методы коррекции ошибок

Техника кодирования, которая позволяет приемнику не только понять, что присланные данные содержат ошибки, но и исправить их, называется прямой коррекцией ошибок (Forward Error Correction — FEC). Коды, обеспечивающие прямую коррекцию ошибок, требуют введения большей избыточности в передаваемые данные, чем коды, которые только обнаруживают ошибки.

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

000 1, 001 0, 010 0, 011 1, 100 0, 101 1, 110 1, 111 0, то есть всего 8 кодов из 16 возможных.

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

Можно доказать, что если мы сконструировали избыточный код с расстоянием Хемминга, равным n, такой код будет в состоянии распознавать (n-1) -кратные ошибки и исправлять (n-1)/2 -кратные ошибки. Так как коды с контролем по паритету имеют расстояние Хемминга, равное 2, они могут только обнаруживать однократные ошибки и не могут исправлять ошибки.

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

Наиболее часто в современных системах связи применяется тип кодирования, реализуемый сверхточным кодирующим устройством (Сonvolutional coder), потому что такое кодирование несложно реализовать аппаратно с использованием линий задержки (delay) и сумматоров. В отличие от рассмотренного выше кода, который относится к блочным кодам без памяти, сверточный код относится к кодам с конечной памятью (Finite memory code); это означает, что выходная последовательность кодера является функцией не только текущего входного сигнала, но также нескольких из числа последних предшествующих битов. Длина кодового ограничения (Constraint length of a code) показывает, как много выходных элементов выходит из системы в пересчете на один входной. Коды часто характеризуются их эффективной степенью (или коэффициентом) кодирования (Code rate). Вам может встретиться сверточный код с коэффициентом кодирования 1/2.
Этот коэффициент указывает, что на каждый входной бит приходится два выходных. При сравнении кодов обращайте внимание на то, что, хотя коды с более высокой эффективной степенью кодирования позволяют передавать данные с более высокой скоростью, они, соответственно, более чувствительны к шуму.

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

3) Методы автоматического запроса повторной передачи

В простейшем случае защита от ошибок заключается только в их обнаружении. Система должна предупредить передатчик об обнаружении ошибки и необходимости повторной передачи. Такие процедуры защиты от ошибок известны как методы автоматического запроса повторной передачи (Automatic Repeat Request — ARQ). В беспроводных локальных сетях применяется процедура «запрос ARQ с остановками» (stop-and-wait ARQ).

В этом случае источник, пославший кадр, ожидает получения подтверждения (Acknowledgement — ACK), или, как еще его называют, квитанции, от приемника и только после этого посылает следующий кадр. Если же подтверждение не приходит в течение тайм-аута, то кадр (или подтверждение) считается утерянным и его передача повторяется. На
рис.
1.13 видно, что в этом случае производительность обмена данными ниже потенциально возможной; хотя передатчик и мог бы послать следующий кадр сразу же после отправки предыдущего, он обязан ждать прихода подтверждения.