избыточное кодирование и скремблирование
Логическое кодирование: избыточные коды и скремблирование.
Виды логического кодирования:
Скремблирование. Заключается в побитовом вычислении результирующего кода на основании исходного. Например, Bi = Ai XOR Bi-3 XOR Bi-5. Bi – двоичная цифра результирующего кода, полученная на i-ом такте работы скремблера (устройство, выполняющее данное логическое преобразование). Ai – двоичная цифра исходного кода, поступающая на скремблер на i-ом такте. XOR – операция исключающего ИЛИ (сложение по модулю 2)
Коммутация: понятие, схема коммутации, декомпозиция задачи коммутации.
Коммутация- соединение конечных узлов через сеть транзитных
Используя принцип декомпозиции (разбиение на подзадачи), её решение можно представить в виде решения нескольких частных задач:
Технологии коммутации: коммутация каналов, коммутация пакетов.
Технологии коммутации
Коммутационная сеть образует между конечными узлами непрерывный составной физический канал из последовательно соединённых коммутаторами промежуточных канальных участков. При этом скорость передачи на всех участках должна быть одинаковой, а перед началом передачи данных необходимо выполнять процедуру установления соединения.
Данная технология была специально разработана для эффективной передачи компьютерного трафика. Согласно исследованиям, коэффициент пульсации трафика отдельного пользователя (отношение средней интенсивности обмена данными к максимальной) составляет от 1:50 до 1:100. При коммутации пакетов все передаваемые данные разбиваются в исходном узле на сравнительно небольшие части (пакеты). Каждый пакет снабжается заголовком, где указывается адресная информация, необходимая для доставки пакета узлу назначения, а также номер пакета, который будет использоваться узлом назначения при сборке данных. Пакеты передаются по сети как независимые блоки. Коммутаторы пакетной сети имеют внутренние буферы для временного хранения пакетов на случай, когда выходной интерфейс коммутатора в момент принятия пакета занят передачей другого пакета. Аналогия с многозадачными ОС.
21. Разделяемая среда передачи данных. Режимы передачи данных. Сетевая топология:
Общие условия выбора системы дренажа: Система дренажа выбирается в зависимости от характера защищаемого.
Механическое удерживание земляных масс: Механическое удерживание земляных масс на склоне обеспечивают контрфорсными сооружениями различных конструкций.
Организация стока поверхностных вод: Наибольшее количество влаги на земном шаре испаряется с поверхности морей и океанов (88‰).
Логический код. Избыточное кодирование и крэмблирование
Логическое кодирование используется для улучшения потенциальных кодов типа AMI, NRZI или 2Q1B. Логическое кодирование должно заменять длинные последовательности битов, приводящие к постоянному потенциалу, вкраплениями единиц. Как уже отмечалось, для логического кодирования характерны два метода — избыточные коды и скрэмблирование.
Избыточные кодыоснованы на разбиении исходной последовательности битов на порции, которые часто называют символами. Затем каждый исходный символ заменяется новым, который имеет большее количество битов, чем исходный. Например, логический код 4В/5Б, используемый в технологиях FDDI и Fast Ethernet, заменяет исходные символы длиной в 4 бит символами длиной в 5 бит. Так как результирующие символы содержат избыточные биты, то общее количество битовых комбинаций в них больше, чем в исходных. Поэтому в результирующем коде можно отобрать 16 таких комбинаций, которые не содержат большого количества нулей, а остальные считать запрещенными кодами (code violation). Кроме устранения постоянной составляющей и придания коду свойства самосинхронизации, избыточные коды позволяют приемнику распознавать искаженные биты. Если приемник принимает запрещенный код, значит, на линии произошло искажение сигнала.
После разбиения получившийся код 4В/5В передается по линии путем физического кодирования по одному из методов потенциального кодирования, чувствительному только к длинным последовательностям пулей. Символы кода 4В/5В длиной 5 бит гарантируют, что при любом их сочетании на линии не может встретиться более трех нулей подряд.
Буква Б в названии кода означает, что элементарный сигнал имеет два состояния (от английского binary — двоичный). Имеются также коды и с тремя состояниями сигнала, например, в коде 8Б/6Т для кодирования 8 бит исходной информации используется код из 6 сигналов, каждый из которых имеет три состояния.
Использование таблицы перекодировки является очень простой операцией, поэтому этот подход не усложняет сетевые адаптеры и интерфейсные блоки коммутаторов и маршрутизаторов.
Метод скрэмбирования основан на предварительном «перемешивании» исходной информации таким образом, чтобы вероятность появления единиц и нулей на линии становилась близкой. Устройства, или блоки, выполняющие такую операцию, называются скрэмблерами. При скремблировании используется известный алгоритм, поэтому приемник, получив двоичные данные, передает их па дескрэмблер, который восстанавливает исходную последовательность битов. Избыточные биты при этом по линии не передаются.
Логическое кодирование, избыточные коды, скремблирование.
Логическое кодирование.
Избыточные коды.
Избыточные коды основаны на разбиении исходной последовательности бит на порции, которые называют символами. Каждый исходный символ заменяется на новый, который имеет большее количество бит, чем исходный. Например, логический код 4В/5В заменяет исходные символы длиной в 4 бита на символы в 5 бит. Так как результирующие символы содержат избыточные биты, то общее количество битовых комбинаций в них больше, чем в исходных.
Избыточные коды также позволяют приемнику распознавать искаженные биты. Если приемник принимает запрещенный код, значит, на линии произошло искажение сигнала.
Имеются также коды и с тремя состояниями сигнала, например, в коде 8В/6Т для кодирования 8 бит исходной информации используется код из 6 сигналов, каждый из которых имеет три состояния.
Для обеспечения заданной пропускной способности линии передатчик, использующий избыточный код, должен работать с повышенной тактовой частотой.
Скремблирование.
Скремблирование не изменяет длину исходного кода, но изменяет последовательность следования 1 и 0. Методы скремблирования заключаются в побитном вычислении результирующего кода на основании бит исходного кода и полученных в предыдущих тактах бит результирующего кода. Наиболее часто используется операция «исключающее ИЛИ».
После получения результирующей последовательности приемник передает ее дескрэмблеру, который восстанавливает исходную последовательность на основании обратного соотношения.
Различные алгоритмы скремблирования отличаются количеством слагаемых и сдвигом между слагаемыми.
Различают две основных схемы скремблеров: самосинхронизирующиеся и аддитивные скремблеры.
Особенностью самосинхронизирующего скремблера является то, что он управляется самой скремблированной последовательностью, т.е. той, которая поступает в канал. Поэтому не требуется специальной установки состояний скремблера и дескремблера, т.к. они оказываются идентичными в результате записи в их регистры сдвига скремблированной последовательности. На приемной стороне выделение информационной последовательности происходит сложением по модулю два принятой скремблированной последовательности с псевдослучайной последовательностью (ПСП) регистра. Одним из недостатков самосинхронизирующихся скремблеров-дескремблеров является свойство размножения ошибок.Данный недостаток ограничивает число обратных связей в регистре сдвига. Второй недостаток самосинхронизирующихся скремблеров связан с возможностью появления на его входе так называемых «критических ситуаций», когда выходная последовательность приобретает периодический характер с периодом, меньшим длины ПСП. Для предотвращения таких ситуаций в скремблере и дескремблере предусматриваются специальные дополнительные схемы контроля, которые выявляют периодичность элементов на входе и нарушают ее.
Аддитивные скремблеры (с начальной установкой) позволяют производить установку начальных состояний регистров. Результирующий сигнал не поступает на вход регистра, и размножения ошибок не происходит. Недостатки самосинхронизирующихся скремблеров отсутствуют при аддитивном скремблировании. Однако в этом случае требуется предварительная идентичная установка состояний регистров скремблера и дескремблера.
Суммируемые в скремблере последовательности независимы, поэтому критических ситуаций не наступает. Отсутствие эффекта размножения ошибок и необходимость специальной защиты от нежелательных ситуаций делают способ аддитивного скремблирования предпочтительнее и экономически эффективнее, если не учитывать затрат на решение задачи взаимной синхронизации пары скремблер – дескремблер.
Исправление ошибок, код Хемминга.
Исправление ошибок.
Обработка и передача больших массивов информации, особенно в условиях помех, сопровождается появлением ошибок. Для большинства видов информации появление ошибок недопустимо (системы управления, математические расчеты и т.д.). Во многих случаях лучше исправлять уже возникшие ошибки, чем пытаться их предотвратить.
Код Хемминга.
Одна из простейших, но эффективных процедур исправления ошибок разработана Р. Хеммингом в 1948 г. и широко используется для защиты данных. Суть метода наглядно иллюстрируется диаграммами Венна. Пусть необходимо защитить слово длиной 4 бита, например 1110. Четыре бита информации хранятся в четырех областях, образованных пересечением трех окружностей (Рис.а). Затем записываются три бита четности (Рис. б) по правилу: полное число единиц в каждой окружности должно быть четным. Ошибка устранимого типа (только в одном бите из четырех) обнаруживается при проверке битов четности (Рис. в). Видно, что нарушение произошло в области пересечения окружностей А и С, но за пределами окружности В (Рис. г). Т.е. применение кода Хемминга позволяет локализовать сбойный бит, следовательно, исправить его.
В коде Хемминга для защиты четырехразрядного слова от одиночных ошибок требуется применение семиразрядного кодового слова. Поэтому этот код называют (7,4). Таким же двухпозиционным цифровым обозначением, состоящим из длины кодового и защищаемого слова, называют другие типы кодов защиты от ошибок.
Если в защищаемом слове возникают две и более ошибок, то код Хемминга не позволяет их исправить. Действительно, при возникновении двух ошибок код Хемминга определит эту ситуацию как появление одной ошибки, и попытка исправить ее приведет к появлению новых. Этот эффект может быть устранен введением дополнительного бита четности, расположенного за пределами пересекающихся окружностей (код Хемминга 8,4). Он не позволяет исправить двойные ошибки, но дает возможность блокировать введение новых ошибок. Используются другие разновидности кодов защиты: (16,11), (32,26), (64, 57). Их трудно представить в виде диаграмм Венна, но они просто реализуются аппаратным методом. Защита информации кодом Хемминга отличается высоким быстродействием.
Логическое кодирование
Некоторые разновидности цифрового кодирования очень чувствительны к характеру передаваемых данных. Например, при передаче длинных последовательностей логических нулей посредством потенциального кода типа NRZ или AMI сигнал на линии долгое время не изменяется, и приемник может ошибиться с моментом считывания очередного бита. Для кода NRZ подобные проблемы возникают и при передаче длинных последовательностей логических единиц. Логическое кодирование (которому может подвергаться исходная последовательность данных) должно внедрять в длинные последовательности бит, биты с противоположным значением, или вообще заменять их другими последовательностями. Кроме исключения “проблемных” битовых последовательностей, логическое кодирование позволяет также увеличить кодовое расстояние между символами (для упрощения декодирования), улучшить спектральные характеристики сигнала, а кроме того передавать в общем потоке служебные сигналы.
В основном для логического кодирования применяются три группы методов:
2. избыточное кодирование;
Вставка бит(bit stuffing) – наиболее прямолинейный способ исключения длинных последовательностей, например, логических единиц. Если в передаваемой последовательности встречается непрерывная цепочка “1”, то передатчик вставляет “0” после каждой, например, пятой “1”. Приемник отбрасывает все эти лишние “0”, которые встречаются после пяти “1”. Разумеется, можно проводить и обратную операцию – вставку “1” в длинные последовательности “0”. Схема вставки бит применяется, например, в протоколе HDLC.
Избыточное кодирование основано на разбиении исходной последовательности бит на участки одинаковой длины – символы. Затем каждый символ заменяется (как правило, табличным способом) на новый, имеющий либо большее количество бит, либо другое основание системы счисления (например, на символ, состоящий из троичных разрядов).
Среди логических кодов можно выделить:
1. Код 4B/5B заменяет каждые 4 бита входного потока (исходный символ) на 5-битный выходной символ. Так как количество различных 5-битных символов равно 32, а исходные символы могут содержать лишь одну из 16 битовых комбинаций (т.е. избыточность равна 32/16 = 2), среди возможных выходных кодов можно отобрать 16 “удобных” комбинаций – не содержащих большого количества нулей (больше трех подряд), среди оставшихся кодов выделить служебные символы (для поддержания синхронизации, выделения границ кадров и их полей и т.д.), а оставшиеся коды считать запрещенными.
| Входной символ | Выходной символ | Входной символ | Выходной символ |
Накладные расходы при кодировании 4B/5B составляют 25% (один лишний бит на четыре бита данных), соответственно для достижения той же пропускной способности, что и без логического кодирования, передатчик должен работать на повышенной на 25% частоте. Код 4B/5B используется в FDDI и Fast Ethernet (100BaseFX и 100BaseTX).
2. Код 8B/10B заменяет каждый 8-битный исходный символ 10-битным выходным символом. При том же уровне накладных расходов (25%), что в случае кода 4B/5B, обладает 4-кратной избыточностью (1024 выходных символов и 256 исходных символов). При кодировании 8B/10B каждому исходному символу сопоставлено два выходных символа, выбор из которых осуществляется в зависимости от последнего бита предыдущего переданного символа. В результате код обеспечивает стабильное соотношение “0” и “1” в выходном потоке, независимо от исходных данных. Это свойство важно для лазерных передатчиков, поскольку от данного соотношения зависит их нагрев и количество ошибок приема. Код 8B/10B используется в Gigabit Ethernet (1000BaseSX, 1000BaseLX, 1000BaseCX).
3. Код 8B/6T кодирует каждые 8 бит исходной информации шестью троичными
(T – ternary, троичный) разрядами, принимающими значения <+, 0, –>. Например, “00000000” = “+–00+–“, “11111110” = “–+0+00”. Избыточность кода 8B/6T выше, чем у кода 4B/5B и составляет 3 6 /2 8 = 729/256 = 2,85. Применяется в Fast Ethernet (100BaseT4).
Скремблированиезаключается в побитном вычислении выходной последовательности на основании значений бит исходной последовательности и уже вычисленных бит результата.
Например, скремблер может вычислять для каждого бита следующее выражение: Bi=AiÅBi-3ÅBi-5, где Ai – i-й бит исходной последовательности, Bi – i-й бит результата скремблирования, Å – операция сложения по модулю два.
Так для исходной последовательности 110110000001 скрэмблер даст следующий результирующий код: B1 = А1 = 1 (первые три цифры результирующего кода будут совпадать с исходным, так как еще нет нужных предыдущих цифр).
Таким образом, на выходе скрэмблера появится последовательность 110001101111, в которой нет последовательности из шести нулей, присутствовавшей в исходном коде.
После получения результирующей последовательности приемник передает ее дескрэмблеру, который восстанавливает исходную последовательность на основании обратного соотношения: Сi=ВiÅBi-3ÅBi-5 = (АiÅBi-3ÅBi-5)ÅBi-3ÅBi-5 = Аi.
Различные алгоритмы скремблирования отличаются разным количеством слагаемых и разным сдвигом между слагаемыми (в приведенном выше примере используется два слагаемых со сдвигами 5 и 7). Например, в ISDN используется два варианта скремблирования: со сдвигами 5 и 23, и со сдвигами 18 и 23.
Существуют специальные методы скремблирования, применяемые совместно определенными методами физического кодирования. Например, для улучшения кода AMI применяются методы B8ZS и HDB3.
Метод B8ZS (Bipolar with 8-Zeros Substitution, биполярный с заменой 8 нулей) заменяет последовательности, состоящие из 8 нулей на “000V10V1”, где V – сигнал единицы запрещенной в данном такте полярности, а 1 – сигнал единицы корректной полярности. Если на 8 тактах приемник наблюдает три начальных нуля и два искажения полярности, то он заменяет эти 8 бит на 8 логических нулей.
Метод HDB3 (High-Density Bipolar 3-Zeros, биполярный трех-нулевой высокой плотности) заменяет последовательности из четырех идущих подряд нулей на один из четырех четырехразрядных биполярных кодов в зависимости от предыстории – полярности предыдущего импульса и предыдущей замены.
Логическое кодирование
Логическое кодирование употребляется для совершенствования потенциальных кодов на подобии:
Логическое кодирование используется для уменьшения длинных последовательностей одинаковых бит, приводящие к неизменному потенциалу, вставками бинарных единиц.
Для логического кодирования разработаны два основных способа уменьшения длинных последовательностей одинаковых бит:
Избыточные коды
Избыточные коды базируются на разделение начальной последовательности бит на порции, которые нередко именуют символами. После чего, исходный символ подменяют на новый, содержащий наибольшее количество бит нежели исходный.
Код 4В/5В затем передается по линии с помощью физического кодирования по одному из методов потенциального кодирования, чувствительному только к длинным последовательностям нулей. Символы кода 4В/5В длиной 5 бит гарантируют, что при любом их сочетании на линии не могут встретиться более трех нулей подряд.
Использование таблицы перекодировки является очень простой операцией, поэтому этот подход не усложняет сетевые адаптеры и интерфейсные блоки коммутаторов и маршрутизаторов.
Скремблирование
Скремблирование (англ. scramble — перемешивать) — разновидность кодирования информации, для передачи по каналам связи и хранения, улучшаюшая спектральные и статиcтические характеристики.
Скремблирование есть приведение информации к виду, по различным характеристикам похожему на случайные данные.
Перемешивание данных скремблером перед передачей их в линию с помощью потенциального кода является другим способом логического кодирования.
Методы скремблирования заключаются в побитном вычислении результирующего кода на основании бит исходного кода и полученных в предыдущих тактах бит результирующего кода. Например, скремблер может реализовывать следующее соотношение:
где Вi, — двоичная цифра результирующего кода, полученная на i-м такте работы скремблера, Ai — двоичная цифра исходного кода, поступающая на вход скремблера, Вi-3 и Bi-5 — двоичные цифры результирующего кода, полученные на предыдущих тактах работы скремблера, соответственно на 3 и на 5 тактов ранее текущего такта, операция исключающего ИЛИ (сложение по модулю 2).
Например, для исходной последовательности 111000000001 скрэмблер даст следующий результирующий код:
Таким образом, на выходе скремблера появится последовательность 111110001100, в которой нет последовательности из восьми нулей, присутствовавшей в исходном коде.
После получения результирующей последовательности приемник передает ее дескремблеру, который восстанавливает исходную последовательность на основа¬нии обратного соотношения:
Произведем обратную операцию с последовательностью 111110001100, для получения исходной последовательности:
Получаем исходную последовательность: 111000000001.
Различные алгоритмы скремблирования отличаются количеством слагаемых, дающих цифру результирующего кода, и сдвигом между слагаемыми. Так, в сетях ISDN при передаче данных от сети к абоненту используется преобразование со сдвигами в 5 и 23 позиции, а при передаче данных от абонента в сеть — со сдвигами 18 и 23 позиции.
Для улучшения кода AMI используются два метода, основанные на искусственном искажении последовательности нулей запрещенными символами:
