Чередование (interleaving)

Большинство кодов коррекции ошибок создавались для каналов связи без памяти. Это значит, что данные коды противостоят случайным независимым ошибкам. Канал с памятью – это такой канал, в котором проявляется взаимная зависимость ухудшений передачи сигнала. Канал, в котором проявляется замирание вследствие многолучевого распространения, когда сигнал поступает на приемник по двум и более путям различной длины – есть пример канала с памятью. Следствием является различная фаза сигналов, и в итоге суммарный сигнал оказывается искаженным. Таким эффектом обладают каналы мобильной беспроводной связи, так же как ионосферные и тропосферные каналы. Ухудшения сигнала коррелируют во времени и в результате дают статистическую взаимную зависимость успешно переданных символов. Иными словами, искажения вызывают ошибки, имеющие вид пакетов, а не отдельных изолированных ошибок.

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

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

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

На рисунке 8.1 показан простой пример чередования. На рисунке 8.1, а показаны кодовые слова, еще не подвергнутые чередованию, от A до G. Каждое кодовое слово состоит из семи символов. Пусть наш код может исправлять однобитовые ошибки в любой 7-символьной последовательности. Если промежуток памяти канала равен длительности одного кодового слова, такой пакет, длительностью в 7 символов, может уничтожить информацию в одном или в двух кодовых словах. Допустим, что на передающей стороне кодовые символы перемешиваются, как показано на рисунке 8.1, б. Каждый кодовый символ каждого кодового слова отделяется от своего соседа на расстояние в семь символьных периодов. Как можно видеть на рисунке 8.1, б последовательные канальные пакеты шума попадают на семь символьных промежутков, влияя на один кодовых символ каждого из семи исходных кодовых слов. Во время приема в потоке восстанавливается вначале исходный поток битов, так что он становится похож на исходную кодовую последовательность, изображенную на рисунке 8.1, а. Затем поток декодируется. Поскольку в каждом кодовом слове возможно исправление одиночной ошибки, импульсная помеха не оказывает никакого влияния на конечную последовательность.

Рисунок 8.1. Пример процедуры чередования битов: а) исходные кодовые слова, содержащие семь кодовых символов; б) полученные кодовые символы

Обычно применяется два типа устройств чередования – блочные и сверточные.