5. Сжатие информации, избыточные коды, скрэмблирование

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

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

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

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

Исходный код	Результирующий код
0000	11110
0001	01001
0010	10100
0011	10101
0100	01010
0101	01011
0110	01110
0111	01111
1000	10010
1001	10011
1010	10110
1011	10111
1100	11010
1101	11011
1110	11100
1111	11101

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

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

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

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

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

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

Перемешивание данных скремблером перед передачей – это другой способ логического кодирования. Методы скремблирования заключается в побитном вычислении результирующего кода на основании бит исходного кода и полученных в предыдущих тактах бит результирующего кода. Например, скремблер может реализовать следующее выражение: B_i=A_i + B_i-3+B_i-5. B_i – результирующая кода, полученная на i-м такте работы кода. Двоичная цифра исходного кода, поступающая на i-м такте в код скремблера. Bi – цифра результирующего кода полученная на 3 или 5 тактов ранее текущего. + - исключающее или.

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

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

2&ZS – код исправляет только последовательности, состоящие из 8 нулей.

HDB3 – исправляет любые 4 подряд идущие нуля в исходной последовательности.

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