Алфавитное кодирование, порядок его применения.
ПустьА={a1,a2,a3,…,an} – алфавит.
a1, a2, a3, …,an – элементыалфавита, т.е. буквы.
Тогда последовательность букв – слово. Множество слов – выражение.
Еслиα = a1, a2, … ak – то к – длина слова.
Если α =a1, a2, то a1 называется префиксом (или началом) слова, аa2 – постфиксом (концом) слова.
Алфавитное кодирование задается схемой (или таблицей кодов) σ:
Пример:
А = {0,1,2,3,4,5,6,7,8,9}
B = {0,1}
Эта схема однозначна, но кодирование не является взаимно однозначным: 
, а значит невозможно декодирование.
Однако если добавить по одному символу, то каждый символ будет кодироваться тетрадами. Такая схема позволяет однозначное кодирование.
Схема алфавитного кодирования называется разделимой, если любое слово, составленное из элементарных кодов, единственным образом разлагается на элементарные коды. Алфавитное кодирование с разделимой схемой допускает декодирование.
Схема называется префиксной, если элементарный код одной буквы не являетсяпрефиксом элементарного кода другой буквы.
Например.
А = {a,b}
B = {0,1}
σ = {a -> 0; b -> 01} данная схема разделима. Но не префиксна. Следовательно, свойство быть префиксной буквой достаточное, но не необходимое для разделимости кода. Хотя префиксная схема всегда является разделимой.
Для получения разделимой схемы алфавитного кодирования необходимо чтобы длины элементарных кодов удовлетворяли соотношению, известному как неравенство Макмиллана.
Если числа длиной L1, L2, …, Lnсоответствуют длинам элементарных кодов β1, β2, …, βn и удовлетворяют: ∑ (iот 1 до n) (2в степени –Li) меньше либо равно 1, то существует схема σ<α1 ->β1; α2 ->β2; …αn ->βn>
|
|
Пример.
Схему кодирования, лежащую в основе азбуки Морзе, можно записать
по историческим и техническим причинам 0 называется точкой, а 1 – тире. Проведя проверку на разделимость получим
Таким образом, схема азбуки Морзе не является разделимой. На самом деле, в азбуке Морзе используются дополнительные элементы – паузы между буквами и словами, что позволяет декодировать сообщение.
Асинхронное и синхронное кодирование как основа для манчестерского кода.
Для правильного распознавания позиций символов в передаваемом сообщении получатель должен знать границы передаваемых элементов сообщения. Для этого необходима синхронизация передатчика и приемника. Использование специального дополнительного провода для сигналов синхронизации (в этом случае имеем битовую синхронизацию) слишком дорого, поэтому используют другие способы синхронизации.
В асинхронном режиме применяют коды, в которых явно выделены границы каждого символа (байта) специальными стартовым и стоповым символами. Подобные побайтно выделенные коды называют байт-ориентированными, а способ передачи - байтовой синхронизацией. Однако это увеличивает число битов, не относящихся собственно к сообщению.
В синхронном режиме синхронизм поддерживается во время передачи всего информационного блока без обрамления каждого байта. Такие коды называют бит-ориентированными. Для входа в синхронизм нужно обозначать границы лишь всего передаваемого блока информации с помощью специальных начальной и конечной комбинаций байтов (обычно это двухбайтовые комбинации). В этом случае синхронизация называется блочной (фреймовой).
|
|
Единицей передаваемых данных в асинхронных протоколах обычно занимает 1 байт. Некоторые символы имеют управляющий характер. В этих протоколах существуют управляющие последовательности, обычно начинающиеся с какого-то специального символа. Эти последовательности вызывают на управляемом устройстве достаточно сложные действия — например, загрузку нового шрифта на принтер.
В асинхронных протоколах применяются стандартные наборы символов, чаще всего ASCII или EBCDIC. Так как первые 32 или 27 кодов в этих наборах являются специальными кодами, которые не отображаются на дисплее или принтере, то они использовались асинхронными протоколами для управления режимом обмена данными. В самих пользовательских данных специальные символы никогда не встречались, так что проблемы их отделения от пользовательских данных не существовало.
В синхронных протоколах между пересылаемыми символами нет стартовых и стоповых сигналов, поэтому отдельные символы в этих протоколах пересылать нельзя. Все обмены данными осуществляются кадрами, которые имеют в общем случае заголовок, поле данных и концевик. Все биты кадра передаются непрерывным синхронным потоком, что значительно ускоряет передачу данных.
В этих протоколах основной задачей приемника является распознавание границы байтов. Затем приемник должен найти начало и конец кадра, а также определить границы каждого поля кадра — адреса назначения, адреса источника, других служебных полей заголовка, поля данных и контрольной суммы, если она имеется.
|
|
Символьно-ориентированные протоколы используются в основном для передачи блоков отображаемых символов, например текстовых файлов. Так как при синхронной передаче нет стоповых и стартовых битов, для синхронизации символов необходим другой метод. Синхронизация достигается за счет того, что передатчик добавляет два или более управляющих символа, называемых символами SYN, перед каждым блоком символов. Символы SYN выполняют две функции: во-первых, они обеспечивают приемнику битовую синхронизацию, во-вторых, как только битовая синхронизация достигается, они позволяют приемнику начать распознавание границ символов SYN. После того как приемник начал отделять один символ от другого, можно задавать границы начала кадра с помощью другого специального символа. Обычно в символьных протоколах для этих целей используются символы STX (StartofTeXt, ASCII 0000010) и ЕТХ (EndofTeXt, ASCII 0000011).
Такой способ выделения начала и конца кадра работает только в том случае, если внутри кадра не было символов STX и ЕТХ.Когда протоколы начали использоваться для связи нескольких компьютеров, то эта проблема возникла.
Для решения вновь появившейся проблемы стали разрабатываться специальные протоколы. Наиболее популярным был BSC компании IBM. Он работал в двух режимах — непрозрачном, в котором некоторые специальные символы внутри кадра запрещались, и прозрачном, в котором разрешалась передачи внутри кадра любых символов. Прозрачность достигалась за счет того, что перед управляющими символами STX и ЕТХ всегда вставлялся символ DLE (DataLinkEscape). Такая процедура называется стаффитом символов. А если в поле данных кадра встречалась последовательность DLE ЕТХ, то передатчик удваивал символ DLE, то есть порождал последовательность DLE DLE ЕТХ. Приемник, встретив подряд два символа DLE, всегда удалял первый, а оставшиеся символы DLE ЕТХ считал просто пользовательскими данными.
Бит-ориентированные протоколы. Потребность в паре символов в начале и конце каждого кадра означает, что символьно-ориентированная передача не эффективна для передачи двоичных данных, так как приходится в поле данных кадра добавлять достаточно много избыточных данных. Кроме того, формат управляющих символов для разных кодировок различен. Так что этот метод допустим только с определенным типом кодировки. Чтобы преодолеть эти проблемы, был разработан универсальный метод, называемый бит-ориентированной передачей. Этот метод сейчас применяется при передаче как двоичных, так и символьных данных. Широко используются 3 схемы бит-ориентированной передачи:
1) Похожа на схему с символами STX и ЕТХ. Начало и конец каждого кадра отмечается одной и той же 8-битовой последовательностью, называемой флагом. Термин «бит-ориентированный» используется потому, что принимаемый поток битов сканируется приемником на побитовой основе для обнаружения стартового флага, а затем во время приема — для обнаружения стопового флага. Поэтому длина кадра в этом случае не обязательно должна быть кратна 8 бит. Чтобы обеспечить синхронизацию приемника, передатчик посылает последовательность байтов простоя, предшествующую стартовому флагу. Для достижения прозрачности данных в этой схеме необходимо, чтобы флаг не присутствовал в поле данных кадра. Это достигается с помощью приема, известного как вставка 0 бита, — бит-стаффинга. Схема вставки бита работает только во время передачи поля данных кадра. Если эта схема обнаруживает, что подряд передано пять единиц, то она автоматически вставляет дополнительный ноль. Бит-стаффинг гораздо более экономичен, чем байт-стаффинг.
2) Во второй схеме для обозначения начала кадра имеется только стартовый флаг, а для определения конца кадра используется поле длины кадра, которое при фиксированных размерах заголовка и концевика чаще всего имеет смысл длины поля данных кадра. Эта схема наиболее применима в локальных сетях.
3) Третья схема использует для обозначения начала и конца кадра флаги, которые включают запрещенные для данного кода сигналы. Этот способ очень экономичен, так как не требует ни бит-стаффинга, ни поля длины, но его недостаток заключается в зависимости от принятого метода физического кодирования.