Положительное выравнивание

Положительное выравнивание (битста́ффинг, англ. Bit stuffing) — вставка неинформационных битов в поток данных. Применяется при передаче данных и в телекоммуникации. Не следует путать с избыточными данными.

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

Другое использование положительного выравнивания предназначено для кодирования с ограниченной длиной серии (RLL): для ограничения количества последовательных битов одного и того же значения в передаваемых данных. Бит противоположного значения вставляется после максимально допустимого количества последовательных битов. Так как это общее правило, получателю не требуется дополнительная информация о расположении вставленных битов для того, чтобы выполнить их удаление.

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

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

Используется, в частности, в CAN (см. «bit stuffing» в шине CAN), HDLC, USB.

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

Вставка нулевого бита

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

Он был популяризирован SDLC IBM (позже переименованным в HDLC), а также используется в Low-Speed и Full-Speed USB.

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

В SDLC передаваемая битовая последовательность «01111110», содержащая шесть смежных единичных бит, является байтом флага. Вставка нулевого бита гарантирует, что этот шаблон никогда не появится в обычных данных, поэтому его можно использовать в качестве маркера для начала и конца кадра без какого-либо риска спутать его с обычными данными.^[1]

Основным недостатком положительного выравнивания является непредсказуемость скорости кодирования; это зависит от передаваемых данных.

Примечания

1. Kevin R. Fall and W. Richard Stevens, TCP/IP Illustrated Volume 1: The Protocols, Second Edition, Addison-Wesley, 2012, Kindle Edition loc 3505