Виды помех в каналах связи. Основные виды помех и искажений в системах связи. Методы борьбы с помехами

Данный алгоритм (алгоритм LZ77 4Назван по именам авторов Абрахама Лемпеля (Abraham Lempel) и Якоба Зива (Jacob Ziv). Опубликован в 1977 году. ) был одним из первых, использующих словарь . В качестве словаря используются N последних уже закодированных элементов последовательности. В процессе сжатия словарь-подпоследовательность перемещается ("скользит") по входящей последовательности. Цепочка элементов на выходе кодируется следующим образом: положение совпадающей части обрабатываемой цепочки элементов в словаре - смещение (относительно текущей позиции), длина, первый элемент, следующий за совпавшей частью цепочки. Длина цепочки совпадения ограничивается сверху числом n . Соответственно, задача состоит в нахождении наибольшей цепочки из словаря, совпадающей с обрабатываемой последовательностью. Если же совпадений нет, то записывается нулевое смещение, единичная длина и только первый элемент незакодированной последовательности - {0, 1, e} .

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

1. подпоследовательность уже закодированных элементов длины N - словарь - буфер поиска (англ. search buffer);
2. подпоследовательность длины n из цепочки элементов, для которой будет произведена попытка поиска совпадения - буфер предварительного просмотра (англ. look-ahead buffer).

В терминах скользящего окна алгоритм сжатия описывается так: если e 1 , . . . , e i - уже закодированная подпоследовательность, то e i-N+1 , . . . , e i - суть словарь или буфер поиска, а e i+1 , . . . , e i+n - буфер предварительного просмотра. Аналогично, задача состоит в поиске наибольшей цепочки элементов из буфера предварительного просмотра, начиная с элемента e i+1 , совпадающей с цепочкой из буфера поиска - эта цепочка может начинаться с любого элемента и заканчиваться любым элементом , т.е. выходить за пределы буфера поиска, вторгаясь в буфер предварительного просмотра. Естественно, что выходить за пределы скользящего окна нельзя. Пусть в скользящем окне найдена максимальная по длине совпавшая цепочка элементов e i-p , . . . , e i+q , тогда она будет закодирована следующим образом: {p+1, q+p+1, e i+p+q+2 } - смещение относительно начала буфера предварительного просмотра (e i+1) , длина совпавшей цепочки, элемент, следующий за совпавшей цепочкой из буфера предварительного просмотра. Если в результате поиска найдено два совпадения с одинаковой длиной, то выбирается ближайшее к началу буфера предварительного просмотра. После этого скользящее окно смещается на p + q + 2 элементов вперед, и процедура поиска повторяется.

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

Приведем пример сжатия данным алгоритмом. Сожмем строку "TOBEORNOTTOBE" с параметрами N = 10 и n = 3 :

Если выделить для хранения смещения 4 бита, длины - 2 бита, а элементов - 8 бит, то длина закодированной последовательности (без учета обозначения конца последовательности) составит 4 x 8 + 2 x 8 + 8 x 8 = 112 бит, а исходной - 102 бита. В данном случае мы не сжали последовательность, а, наоборот, увеличили избыточность представления. Это связано с тем, что длина последовательности слишком мала для такого алгоритма. Но, например, рисунок кодового дерева Хаффмена на рис. 13.1 , занимающий 420 килобайт дискового пространства, после сжатия имеет размер около 310 килобайт.

Ниже приведен псевдокод алгоритма сжатия.

// M - фиксированная граница // считываем символы последовательно из входного потока // in - вход - сжатая последовательность // n - максимальная длина цепочки // pos - положение в словаре, len - длина цепочки // nelem - элемент за цепочкой, str - найденная цепочка // in - вход, out - выход // SlideWindow - буфер поиска while(!in.EOF()) //пока есть данные { // ищем максимальное совпадение и его параметры SlideWindow.FindBestMatch(in, n, pos, len, nelem); // пишем выход: смещение, длина, элемент out.Write(pos); out.Write(len); out.Write(nelem); // сдвинем скользящее окно на len + 1 элементов SlideWindow.Move(in, len + 1); } Листинг 13.2. Алгоритм сжатия методом LZ77

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

Видно, что процесс декодирования значительно проще с вычислительной точки зрения.

// n - максимальная длина цепочки // pos - положение в словаре, len - длина цепочки // nelem - элемент за цепочкой, str - найденная цепочка // in - вход, out - выход // Dict - словарь while(!in.EOF()) //пока есть данные { in.Read(pos); in.Read(len); in.Read(nelem); if(pos == 0) { //новый отдельный символ //удаляем из словаря первый (дальний) один элемент Dict.Remove(1); //добавляем в словарь элемент Dict.Add(nelem); out.Write(nelem); } else { //скопируем соответствующую строку из словаря str = Dict.Get(pos, len); //удалим из словаря len + 1 элементов Dict.Remove(len + 1); //Добавляем в словарь цепочку Dict.Add(str + nelem); out.Write(str + nelem); } } Листинг 13.3. Алгоритм

Данный алгоритм является родоначальником целого семейства алгоритмов, и сам по себе в изначальном виде практически не используется. К его достоинствам можно отнести приличную степень сжатия на достаточно больших последовательностях, быструю распаковку, а также отсутствие патента 5документ, обеспечивающий исключительное право эксплуатировать изобретение в течение известного времени (обычно 15-20 лет) на алгоритм. К недостаткам относят медленную скорость сжатия, а также меньшую, чем у альтернативных алгоритмов, степень сжатия (модификации алгоритма борются с этим недостатком). Сочетание алгоритмов Хаффмена (Huffman) ( "Алгоритмы сжатия изображений без потерь") и LZ77 называют методом DEFLATE 6Так называется сжатие, а разжатие называется INFLATE (англ. DEFLATE - сдувать, INFLATE - надувать). . Метод DEFLATE используется в графическом формате PNG, а также в универсальном формате сжатия данных ZIP.

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

Чтобы убедиться в необходимости повторной передачи данных, отправитель нумерует отправляемые кадры и для каждого кадра ожидает от приемника так называемой положительной квитанции (Positive Acknowledgment, АСК) - служебного кадра, извещающего о том, что исходный кадр получен и данные в нем корректны. Для того чтобы организовать такую нумерацию, и нужна процедура логического соединения - она дает точку отсчета, с которой начинается нумерация. Время ожидания квитанции ограничено - при отправке каждого кадра передатчик запускает таймер, и, если по истечении заданного времени положительная квитанция на получена, кадр считается утерянным. Приемник в случае получения кадра с искаженными данными может отправить отрицательную квитанцию (Negative Acknowledgment, NACK) - явное указание на то, что данный кадр нужно передать повторно.

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

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

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

Недостатки этого метода коррекции особенно заметны на низкоскоростных каналах связи, то есть в территориальных сетях.

Второй метод называется методом скользящего окна (sliding window). В этом методе для повышения скорости передачи данных источнику разрешается передать некоторое количество кадров в непрерывном режиме, то есть в максимально возможном для источника темпе без получения на эти пакеты квитанций. Количество пакетов, которые разрешается передавать таким образом, называется размером окна. Рисунок 6.6, б иллюстрирует применение данного метода для окна размером W пакетов.

В начальный момент, когда еще не послано ни одного пакета, окно определяет диапазон пакетов с номерами от 1 до W включительно. Источник начинает передавать пакеты и получать в ответ квитанции. Для простоты предположим, что квитанции поступают в той же последовательности, что и пакеты, которым они

соответствуют. В момент t t при получении первой квитанции Kj окно сдвигается на одну позицию, определяя новый диапазон от 2 до (W + 1).

Процессы отправки пакетов и получения квитанций идут достаточно независимо друг от друга. Рассмотрим произвольный момент времени t n , когда источник получает квитанцию на пакет с номером п. Окно сдвигается вправо и определяет диапазон разрешенных к передаче пакетов от (n + 1) до (W + п). Все множество пакетов, выходящих из источника, можно разделить на перечисленные ниже группы (см. рис. 6.6, б).

Пакеты с номерами от 1 до η уже были отправлены и квитанции на них получены, то есть они находятся за пределами окна слева.

Пакеты, начиная с номера (η + 1) и заканчивая номером (W + п), находятся в пределах окна и потому могут быть отправлены, не дожидаясь прихода какой-либо квитанции. Этот диапазон может быть разделен еще на два поддиапазона:

О пакеты с номерами от (η + 1) до m уже отправлены, но квитанции на них еще не получены;

О пакеты с номерами от m до (W + п) пока не отправлены, хотя запрета на это нет.

Все пакеты с номерами, большими или равными (W + η + 1), находятся за пределами окна справа и поэтому пока не могут быть отправлены.

Перемещение окна вдоль последовательности номеров пакетов иллюстрирует рис. 6.6, в. Здесь t〇 - исходный момент, tļ и t n - моменты прихода квитанций на первый и η-й пакет соответственно. Каждый раз, когда приходит квитанция, окно сдвигается влево, но его размер при этом не меняется и остается равным W.

При отправке пакета в источнике устанавливается тайм-аут. Если за это время квитанция на отправленный пакет не придет, пакет (или квитанция на него) считается утерянным, и пакет передается снова.

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

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

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

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

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

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

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

Размер окна может быть также изменен узлом назначения. Причиной уменьшения размера окна является перегрузка узла назначения, который не успевает обработать поступающие пакеты. Мы вернемся к этой проблеме позже, в разделе «Обратная связь» главы 7, когда будем изучать методы борьбы с перегрузками.

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

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

Еще по теме Повторная передача и скользящее окно:

1. § 29 Передача и переход прав по обязательствам. – Римская конструкция права передачи. – Облегчение передачи новейшим законодательством. – Передаточная надпись. – Ограничения передачи. – Действие передачи. – Ответственность передатчика и права приобретателя. – Вступление в право кредитора или суброгация. – Русский закон передачи. – Передача заемных писем. – Переход требований к кредиторам.

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

Итак, существует два метода организации процесса обмена квитанциями: метод простоя источника и метод скользящего окна.

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

Рис. 17.10. Метод простоя источника

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

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

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

Рисунок 17.11 иллюстрирует применение данного метода для окна размером 5 кадров.

Рис. 17.11. Метод скользящего окна

В начальный момент, когда еще не послано ни одного кадра, окно определяет диапазон номеров кадров от 1 до 5 включительно. Источник начинает передавать кадры и через какое-то время получать в ответ квитанции. Для простоты предположим, что квитанции поступают в той же последовательности (но не обязательно в том же темпе), что и кадры, которым они соответствуют. В момент получения отправителем квитанции 1 окно сдвигается на одну позицию вверх, определяя новый диапазон разрешенных к отправке кадров (от 2 до 6).

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

После получения квитанции 2 (на кадр 2) окно сдвигается вверх на единицу, определяя диапазон разрешенных к передаче кадров от 3 до 7. Аналогичное «скольжение» окна вверх происходит после получения каждой квитанции : окно сдвигается вверх на 1, но его размер при этом не меняется и остается равным 5. После прихода квитанции 8 окно оказывается в диапазоне от 9 до 13 и остается таковым достаточно долго, так как по каким-то причинам источник перестает получать подтверждения о доставке кадров. Отправив последний разрешенный кадр 13, передатчик снова прекращает передачу с тем, чтобы возобновить ее после прихода квитанции 9.

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

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