1.11. Варианты модификации параметров кодов

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

В подобных условиях при наличии достаточно совершенных процессоров передатчика и приемника выбор параметров кода на основе некоторого множества средних показателей канала связи зачастую оказывается непродуктивным. Одним из путей выхода из подобной ситуации является использование систем адаптивного кодирования – автоматической и целенаправленной коррекции параметров кода по мере изменения качества канала. К параметрам кода, которые могут быть использованы в качестве параметрической адаптации, следует отнести количество информационных и избыточных разрядов, приходящихся на кодовую комбинацию или список слов, подлежащих передаче. Этот список в зависимости от условий передачи данных в канале связи может увеличиваться или уменьшаться. Адаптивное кодирование повышает помехоустойчивость или скорость передачи за счет перераспределения избыточности кода между состояниями канала связи. Отличное решение этой задачи возможно при наличии канала обратной связи. В такой системе избыточные символы могут добавляться передатчиком по запросу приемника. Запрос формируется при условии, что декодер не в состоянии обработать принятую последовательность. Целенаправленное изменение параметров кода получило название модификации кодов. Различные варианты модификации кодов представлены на рис. 1.16.

Рис. 1.16.  Варианты модификации параметров избыточных кодов

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

.

 

Если в матрице  вычеркиваются первые  столбцов, то в матрице  верхние строк становятся бесполезными, и они удаляются автоматически. Возникает вопрос о значении параметра . Рассмотрим блоковый код (15,7,5) с порождающим полиномом g(x)=7218 и матрицей  в систематической форме

.

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

           при         и      ,

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

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

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

По сути, обратными операциями рассмотренным выше являются операции расширения, удлинения и пополнения.

Любой двоичный  код можно расширить до  кода со значением  путем добавления к каждой кодовой комбинации результата суммирования по  всех ее символов, т.н. проверка на четность. Безызбыточный код имеет минимальное расстояние , следовательно, любое искажение хотя бы одного символа в таком коде обязательно приводит к искажению кодового слова. Простейший систематический код  строится путем добавления к комбинации из  информационных символов одного проверочного разряда. Легко видеть, что эта сумма равна нулю, если среди информационных символов имеется четное число единиц, и равно единице, если – нечетное. После добавления проверочного символа образуются кодовые комбинации, содержащие только четное число единиц, что сокращает весовой спектр кода до  комбинаций с четным весом. Из-за простоты кодирования (и декодирования) контроль по четности часто проводится в кодере источника или в иных вспомогательных целях. Следует заметить, что двукратное повторение безызбыточных кодовых комбинаций обеспечивает повышение минимального расстояния до двух, но в этом случает скорость кода снижается вдвое, так как . В процедуре проверки на четность этот параметр кратен величине .

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

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

Особое место в ряду модификаций параметров кода занимает процедура замещения проверочных символов (на рис. 1.16 показана стрелкой). При передаче данных в пакетных режимах такие коды используются для определения целостности блока данных. Например, в кодах Абрамсона [19] кроме проверок, которые определяются по схеме кода (7,4,3) выполняется проверка на четность по всем символам.

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

Во-первых, по пути поиска наиболее вероятных слов среди всего разрешенного множества кодовых комбинаций или, во-вторых, с использованием лексикографического метода. Во втором случае в каждом кодовом векторе необходимо выделить разряды, которые будут отвечать за организацию списка. Если такое выделение произведено, и приемник «знает», какие символы отвечают за составление списка. Ошибочная фиксация таких символов приведет к тому, что номер списка будет идентифицирован неверно. Для защиты номера списка от искажений целесообразно использовать один (или несколько)  проверочных разрядов по следующей схеме. На передаче в сформированной -разрядной комбинации выкалывается проверочный разряд, позиция которого известна передатчику и приемнику. На  место этого разряда записывается  бит проверки четности исключительно тех разрядов, которые указывают на номер списка. Поскольку принудительная трансформация символа происходит всегда на одной и той же позиции разрешенной кодовой комбинации, то приемник воспринимает эту позицию как стирание, восстановление которого  не  влияет на сложность реализации декодера.

Пусть дана комбинация кода  вида =111000010100110 и пусть первые три разряда определяют номер списка. Получив такой вектор, декодер обращается к списку с номером   1112=710 и осуществляет поиск вектора не среди всего разрешенного множества кодовых комбинаций, а в значительно меньшем подмножестве векторов, которое отвечает указанному номеру списка. Для защиты этого номера передатчик выкалывает последний (правый) бит вектора , показанный жирным курсивом, и устанавливает на его место бит четности. В этом случае в канал связи будет отправлен вектор 1.

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