содержание   ..  1  2  3  4  5  6  7   ..

17.  Методы цифрового кодирования

18.  Логическое кодирование.

Некоторые разновидности цифрового кодирования очень чувствительны к характеру передаваемых данных. Например, при передаче длинных последовательностей логических нулей посредством потенциального кода типа NRZ или AMI сигнал на линии долгое время не изменяется, и приемник может ошибиться с моментом считывания очередного бита. Для кода NRZ подобные проблемы возникают и при передаче длинных последовательностей логических единиц.  Логическое кодирование (которому может подвергаться исходная последовательность данных) должно внедрять в длинные последовательности бит, биты с противоположным значением, или вообще заменять их другими последовательностями. Кроме исключения “проблемных” битовых последовательностей, логическое кодирование позволяет также увеличить кодовое расстояние между символами (для упрощения декодирования), улучшить спектральные характеристики сигнала, а кроме того передавать в общем потоке служебные сигналы. В основном для логического кодирования применяются три группы методов: вставка бит, избыточное кодирование и скремблирование.

Вставка бит (bit stuffing) – наиболее прямолинейный способ исключения длинных последовательностей, например, логических единиц. Если в передаваемой последовательности встречается непрерывная цепочка “1”, то передатчик вставляет “0” после каждой, например, пятой “1”. Приемник отбрасывает все эти лишние “0”, которые встречаются после пяти “1”. Разумеется, можно проводить и обратную операцию – вставку “1” в длинные последовательности “0”. Схема вставки бит применяется, например, в протоколе HDLC.

Избыточные коды

Избыточные коды основаны на разбиении исходной последовательности бит на порции, которые часто называют символами. Затем каждый исходный символ заменяется на новый, который имеет большее количество бит, чем исходный. Например, логический код 4В/5В, используемый в технологиях FDDI и Fast Ethernet, заменяет исходные символы длиной в 4 бита на символы длиной в 5 бит. Так как результирующие символы содержат избыточные биты, то общее количество битовых комбинаций в них больше, чем в исходных. Так, в коде 4В/5В результирующие символы могут содержать 32 битовых комбинации, в то время как исходные символы - только 16. Поэтому в результирующем коде можно отобрать 16 таких комбинаций, которые не содержат большого количества нулей, а остальные считать запрещенными кодами (code violation). Кроме устранения постоянной составляющей и придания коду свойства самосинхронизации, избыточные коды позволяют приемнику распознавать искаженные биты. Если приемник принимает запрещенный код, значит, на линии произошло искажение сигнала. Ethernet Локальные сети Выделенный канал

Соответствие исходных и результирующих кодов 4В/5В представлено ниже.

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

Буква В в названии кода означает, что элементарный сигнал имеет 2 состояния - от английского binary - двоичный. Имеются также коды и с тремя состояниями сигнала, например, в коде 8В/6Т для кодирования 8 бит исходной информации используется код из 6 сигналов, каждый из которых имеет три состояния. Избыточность кода 8В/6Т выше, чем кода 4В/5В, так как на 256 исходных кодов приходится 3⁶=729 результирующих символов.

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

Для обеспечения заданной пропускной способности линии передатчик, использующий избыточный код, должен работать с повышенной тактовой частотой. Так, для передачи кодов 4В/5В со скоростью 100 Мб/с передатчик должен работать с тактовой частотой 125 МГц. При этом спектр сигнала на линии расширяется по сравнению со случаем, когда по линии передается чистый, не избыточный код. Тем не менее спектр избыточного потенциального кода оказывается уже спектра манчестерского кода, что оправдывает дополнительный этап логического кодирования, а также работу приемника и передатчика на повышенной тактовой частоте.

Скрэмблирование

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

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

где Bi - двоичная цифра результирующего кода, полученная на i-м такте работы скрэмблера, Ai - двоичная цифра исходного кода, поступающая на i-м такте на вход скрэмблера, Bi-з и Bi-5 - двоичные цифры результирующего кода, полученные на предыдущих тактах работы скрэмблера, соответственно на 3 и на 5 тактов ранее текущего такта,  - операция исключающего ИЛИ (сложение по модулю 2). Например, для исходной последовательности 110110000001 скрэмблер даст следующий результирующий код: B1 = А1 = 1 (первые три цифры результирующего кода будут совпадать с исходным, так как еще нет нужных предыдущих цифр)

Таким образом, на выходе скрэмблера появится последовательность 110001101111, в которой нет последовательности из шести нулей, присутствовавшей в исходном коде.

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

Различные алгоритмы скрэмблирования отличаются количеством слагаемых, дающих цифру результирующего кода, и сдвигом между слагаемыми. Так, в сетях ISDN при передаче данных от сети к абоненту используется преобразование со сдвигами в 5 и 23 позиции, а при передаче данных от абонента в сеть - со сдвигами 18 и 23 позиции.

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

Для улучшения кода Bipolar AMI используются два метода, основанные на искусственном искажении последовательности нулей запрещенными символами.

На рис. 2.17 показано использование метода B8ZS (Bipolar with 8-Zeros Substitution) и метода HDB3 (High-Density Bipolar 3-Zeros) для корректировки кода AMI. Исходный код состоит из двух длинных последовательностей нулей: в первом случае - из 8, а во втором - из 5.

Рис. 2.17. Коды B8ZS и HDB3. V - сигнал единицы запрещенной полярности; 1*-сигнал единицы корректной полярности, но заменившей 0 в исходном коде

Код B8ZS исправляет только последовательности, состоящие из 8 нулей. Для этого он после первых трех нулей вместо оставшихся пяти нулей вставляет пять цифр: V-1*-0-V-1*. V здесь обозначает сигнал единицы, запрещенной для данного такта полярности, то есть сигнал, не изменяющий полярность предыдущей единицы, 1* - сигнал единицы корректной полярности, а знак звездочки отмечает тот факт, что в исходном коде в этом такте была не единица, а ноль. В результате на 8 тактах приемник наблюдает 2 искажения - очень маловероятно, что это случилось из-за шума на линии или других сбоев передачи. Поэтому приемник считает такие нарушения кодировкой 8 последовательных нулей и после приема заменяет их на исходные 8 нулей. Код B8ZS построен так, что его постоянная составляющая равна нулю при любых последовательностях двоичных цифр.

Код HDB3 исправляет любые четыре подряд идущих нуля в исходной последовательности. Правила формирования кода HDB3 более сложные, чем кода B8ZS. Каждые четыре нуля заменяются четырьмя сигналами, в которых имеется один сигнал V. Для подавления постоянной составляющей полярность сигнала V чередуется при последовательных заменах. Кроме того, для замены используются два образца четырехтактовых кодов. Если перед заменой исходный код содержал нечетное число единиц, то используется последовательность 000V, а если число единиц было четным - последовательность 1*00V.

Улучшенные потенциальные коды обладают достаточно узкой полосой пропускания для любых последовательностей единиц и нулей, которые встречаются в передаваемых данных. На рис. 2.18 приведены спектры сигналов разных кодов, полученные при передаче произвольных данных, в которых различные сочетания нулей и единиц в исходном коде равновероятны. При построении графиков спектр усреднялся по всем возможным наборам исходных последовательностей. Естественно, что результирующие коды могут иметь и другое распределение нулей и единиц. Из рис. 2.18 видно, что потенциальный код NRZ обладает хорошим спектром с одним недостатком - у него имеется постоянная составляющая. Коды, полученные из потенциального путем логического кодирования, обладают более узким спектром, чем манчестерский, даже при повышенной тактовой частоте (на рисунке спектр кода 4В/5В должен был бы примерно совпадать с кодом B8ZS, но он сдвинут в область более высоких частот, так как его тактовая частота повышена на 1/4 по сравнению с другими кодами). Этим объясняется применение потенциальных избыточных и скрэмблированных кодов в современных технологиях, подобных FDDI, Fast Ethernet, Gigabit Ethernet, ISDN и т. п. вместо манчестерского и биполярного импульсного кодирования.

Рис. 2.18. Спектры потенциальных и импульсных кодов

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

19.  Методы обнаружения и коррекции ошибок.

Обнаружение и коррекция ошибок

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

Большая часть протоколов канального уровня выполняет только первую задачу — обнаружение ошибок, считая, что корректировать ошибки, то есть повторно передавать данные, содержавшие искаженную информацию, должны протоколы верхних уровней. Так работают такие популярные протоколы локальных сетей, как Ethernet, Token Ring, FDDI, а также протоколы глобальных сетей frame relay и АТМ. Однако существуют протоколы канального уровня, например LLC2 для локальных сетей или HDLC для глобальных, которые самостоятельно решают задачу восстановления искаженных или потерянных кадров.

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

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

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

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

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

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

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

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

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

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

Порождающий полином x¹⁶ + x¹² + x⁵ + 1 рекомендован ITU. Он обнаруживает ошибки кратности 1 и 2, ошибки нечетной кратности; все пачки ошибок с длиной не более 16; 99,997% пачек длины 17; 99.998% пачек с длиной 18 и больше.

20.  Методы восстановления искаженных и потерянных кадров.

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

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

Существует два подхода к организации процесса обмена квитанциями: с просто­ями и с организацией «окна».

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

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

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

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

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

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

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

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

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

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

Перемещение окна вдоль последовательности номеров кадров иллюстрирует рис. 5.13, в. Здесь t₀ — исходный момент, t₁ и t_n — моменты прихода квитанций на первый и п-й кадр соответственно. Каждый раз, когда приходит квитанция, окно сдвигается влево, но его размер при этом не меняется и остается равным w. Заметим, что хотя в данном примере размер окна в процессе передачи остается постоянным, в реальных протоколах (например, TCP) можно встретить вариан­ты данного алгоритма с изменяющимся размером окна.

Итак, при отправке кадра с номером n источнику разрешается передать еще w - 1 кадров до получения квитанции на кадр n, так что в сеть последним уйдет кадр с номером (w + n - 1). Если же за это время квитанция на кадр n так и не пришла, то процесс передачи приостанавливается, и по истечении некоторого тайм-аута кадр n (или квитанция на него) считается утерянным, и он передается снова.

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

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

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

Другие методы используют отрицательные квитанции. Отрицательные квитан­ции бывают двух типов — групповые и избирательные. Групповая квитанция со­держит номер кадра, начиная с которого нужно повторить передачу всех кадров, отправленных передатчиком в сеть (метод Go Back N). Избирательная отрицательная квитанция требует повторной передачи только одного или нескольких кадров (метод Selective Repeat).

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

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

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

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

При использовании метода Sliding Window для нумерации кадров обычно используются 3 бита. В случае использования спутникового канала может использоваться 7 бит.

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

Метод скользящего окна реализован во многих протоколах: LLC2, LAP-B, Х.25, TCP, Novell NCP Burst Mode.

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

содержание   ..  1  2  3  4  5  6  7   ..