Главная > Помехоустойчивое кодирование > Кодирование с исправлением ошибок в системах цифровой связи
<< Предыдущий параграф
Следующий параграф >>
<< Предыдущий параграф Следующий параграф >>
Макеты страниц

8.6. Кодирование для каналов с ограниченной полосой

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

число исследователей; они получили ряд интересных результатов [109—111].

В задачах такого типа предъявляемые к системе требования (скорость информации, ширина полосы и т. д.) определяют предпочтительное множество сигналов (или ряд множеств, таких как ФМ, АИМ и др.), а также скорость передачи символов и число информационных битов на символ. Таким образом, в системе без кодирования требуется использование -ичной модуляции. Наилучшим подходом при кодировании в случае алфавитов большого объема является использование кодов с большими скоростями. Обычный метод состоит в расширении множества сигналов до и использовании кода с Поскольку скорость передачи символов не меняется, система с кодированием будет занимать такую же полосу частот, что и система без кодирования, и каждому символу будет соответствовать то же число информационных бит, а именно Однако если код выбран достаточно хорошим, то система с кодированием позволит уменьшить требуемое значение на величину, равную выигрышу от кодирования. Далее, не обсуждая фактической ширины полосы или влияния фильтрации, сосредоточиваем внимание на задаче построения эффективных кодов для некоторых хорошо известных схем -ичной модуляции. Будут рассматриваться сверточные коды и алгоритм декодирования Витерби, однако .к аналогичным результатам могут привести и другие методы.

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

и кодового слова в противном случае. В предположении, что шум является гауссовским, а компоненты шума независимы и имеют дисперсию формулу (8.15) можно записать в виде

Это оптимальное решающее правило эквивалентно выбору если

Таким образом, метрика, которая требуется декодеру на ортогональной составляющей есть Заметим, что эта метрика отличается от использованной ранее для двоичной ФМ,

поскольку в этом случае и (8.16) можно привести к виду

В декодерах Витерби обычно реализуется метрика, определяемая согласно (8.17) для двоичной ФМ, однако реализация метрики, определяемой согласно (8.16) для алфавитов большого объема, не приводит к существенным трудностям. Она приводит лишь к сравнительно небольшим изменениям начальной части декодера. Заметим, что (8.16) можно также переписать в виде

Таким образом, вероятность ошибки при различении определяется евклидовым расстоянием между этими двумя векторами. Квадрат расстояния

и вероятность ошибки при различении

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

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

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

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

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

Тогда нижняя граница для вероятности ошибки задается неравенством

и сама вероятность ошибки приближается к этой границе при больших отношениях сигнал-шум. Асимптотический выигрыш от кодирования определяется формулой

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

В качестве примера рассмотрим кодирование для -ичной ФМ с использованием сверточных кодов и декодирования Витерби при двух информационных битах на передаваемый символ. Для этого выбираем сверточный код с -ичную (рис. 8.27), предполагая при этом, что на передачу каждого символа затрачивается единичная энергия. Рассмотрим код с структура которого приведена на рис. 6.7. Этот код выбран только потому, что он уже рассматривался ранее. (В данной задаче выколотые коды не обладают специальными преимуществами.) Важным моментом при построении кода является согласование ребер

Рис. 8.27. Отображение кодовых ребер в сигнальные точки для кода Грея в случае

кода с сигнальными точками. Использование кода Грея для отображения кодовых ребер в сигнальные точки показано на рис. 8.27. Интуиция говорит, что такое отображение является удовлетворительным, поскольку все ребра, расстояния Хемминга между которыми равно 1, 2 и 3, переходят в сигнальные точки, евклидово расстояние между которыми не меньше соответственно. Читатель может убедиться, что свободное евклидово расстояние определяется как

т. е. обусловлено расстоянием между нулевым путем и путем Однако основная система без кодирования, имеющая два бита на символ (т. е. система, с которой нужно проводить сравнение) — это система с (или КФМ). Этой системе соответствуют четыре точки, расположенные на координатных осях. Если средняя (или пиковая) мощность в основной системе без кодирования такая же, как в системе с кодированием, то получаем, что евклидово расстояние равно и асимптотический выигрыш от кодирования составляет

Этот сравнительно небольшой выигрыш можно увеличить, если осуществить кодирование более разумно. Для этого нужно использовать преимущества значительного различия расстояний между точками множества сигналов (заметим, что Рассмотрим отображение, показанное на рис. 8.28. Первые два символа, соответствующие каждой точке (они подчеркнуты), задаются уже знакомым кодом с структура которого показана на рис. 6.3. Третий символ является незакодированным символом данных. Таким образом, при использовании этой схемы каждому ребру по-прежнему соответствуют два информационных бита, достоинством является чрезвычайная простота реализации декодера для кода с Заметим, что максимально разделенными при указанном отображении являются пары сигнальных точек, в которых закодированные ребра совпадают, а незакодированные информационные биты различны (так, расстояние между и 001 равно Диаграмма, задающая это отображение, показана на рис. 8.29. Она совпадает со стандартной диаграммой для кода с однако имеет параллельные переходы между состояниями. Эти параллельные переходы соответствуют совпадающим ребрам кода с с различными незакодированными информационными битами. Отображение на рис. 8.28 убеждает, что расстояние между параллельными переходами всегда равно

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

Рис. 8.28. Отображение (подчеркнутых) кодовых ребер с в множество сигналов

Рис. 8.29. Решетчатая структура кода, используемого для (при отображении, показанном на рис. 8.28)

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

а соответствующий выигрыш от кодирования составляет

Такой подход приводит к существенно большему выигрышу от кодирования, чем в случае, проиллюстрированном на рис. 8.27, а сложность соответствующего декодера примерно такая же. Хотя логически этот метод представляется не очень целесообразным при ряде схем выбора сигналов, он приводит к существенному выигрышу. Причина состоит в том, что во многих случаях наиболее эффективно применять кодирование лишь к некоторым информационным битам каждого символа. При значительном различии расстояний между сигналами некоторую информацию можно передавать без всякого кодирования. Однако применение этого метода имеет свои пределы. Заметим, что для так что параллельные переходы ограничивают сверху свободное евклидово расстояние значением 2. Поэтому выигрыш от кодирования не может превышать Для получения большего выигрыша при следует устранить параллельные переходы и использовать код с

Рис. 8.30. Отображение (подчеркнутых) ребер кода с в множество сигналов -АИМ

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

Другой пример использования кода с при том же методе отображения, что и ранее, но с -ичной амплитудно-импульсной модуляцией -АИМ) показан на рис. 8.30. Это отображение использует два информационных бита на символ, так что основная система, имеющая ту же пиковую мощность (с ней нужно проводить сравнение), — это -АИМ, имеющая Диаграмму для этого кода можно построить аналогично диаграмме рис. 8.29. Она будет отражать параллельные переходы и, квадрат расстояния между параллельными переходами Заметим, что при этом максимальный асимптотический выигрыш от кодирования ограничен величиной

Эта величина больше соответствующего значения для однако расстояние, накапливаемое при непараллельных кодовых переходах, оказывается меньшим. Из рис. 8.30 видно, что все противоположные сравнения (например, сравнение 11 с 00) приводят к квадрату расстояния а все ортогональные сравнения — к квадрату расстояния

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

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

вклад в свободное евклидово расстояние, и наименьшее евклидово расстояние соответствует случаю, когда все остальные сравнения, соответствующие свободному расстоянию кода Хемминга являются ортогональными. Таким образом, общее евклидово свободное расстояние кода ограничено снизу следующим образом:

С помощью этого соотношения были вычислены минимальные асимптотические выигрыши от кодирования для кодов с из табл. соответствующие значения приведены в табл. 8.4. Столбец и первый столбец значений выигрыша относятся к сравнению -АИМ с кодированием и -АИМ без кодирования с той же пиковой мощностью.

Таблица 8.4. (см. скан) Асимптотический выигрыш от кодирования для кодов с из табл. Б.2 при -АИМ, показанной на рис. 8.30

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

Заметим, что при одинаковой пиковой мощности система -АИМ имеет на большую среднюю мощность, чем -АИМ. Именно эта величина обусловливает дополнительный выигрыш при сравнении на основе средних мощностей.

Несмотря на то что предложенные схемы кодирования во многих случаях приводит к превосходным характеристикам, правомерен вопрос о том, как следует строить коды для улучшения характеристик. Точнее, хотелось бы иметь эффективный алгоритм для построения кодов, близких к оптимальным. Такой подход был описан Унгербоеком [109, 110]. Он включает разбиение множества сигналов на подмножества, причем расстояния между элементами

Рис. 8.31. Разбиение множества сигналов -АИМ на подмножества с возрастающими свободными расстояниями внутри подмножества

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

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

С учетом этих ограничений сигнальные точки нужно ставить в соответствие переходам по решетке таким образом, чтобы максимизировалось свободное евклидово расстояние кода. В работах [109, 110] это сделано для некоторых способов выбора сигналов и в каждом случае для каждого найден код, минимизирующий свободное евклидово расстояние. Один такой решетчатый код показан на рис. Заметим, что в этом коде не используются параллельные переходы. (Ранее отмечалось, что параллельные переходы ограничивают получаемый выигрыш значением а такой выигрыш можно получить уже при Поэтому путям, которые выходят из одного состояния или входят в одно состояние, ставятся в соответствие сигналы из множеств или (Числа,

Рис. 8.32. Решетчатый код с для с двумя информационными битами на символ

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

В результате по сравнению с системой без кодирования выигрыш составляет При таком же подходе в случае больших длин кодового ограничения Унгербоек получил значения выигрыша, сравнимые с приведенными в табл. 8.4. Аналогичные методы были также использованы для поиска хороших кодов для различных схем -ичной -ичной квадратурной амплитудной модуляции и одновременной -ичной амплитудной и фазовой модуляции. Унгербоек показал, что как для получения требуемых характеристик, так и для упрощения реализации в случае сигналов высокого порядка весьма желательно широкое применение параллельных переходов [109. 110]. Согласно результатам этих работ при значениях можно добиться выигрыша от кодирования в Приведены результаты ряда экспериментов, показывающих, что при интересных для практики значениях вероятности ошибки бита получающийся выигрыш от кодирования примерно на меньше предсказываемого.

Андерсон и Тейлор [111] рассмотрели аналогичную задачу для частотной модуляции с непрерывной фазой Они построили специальные решетчатые коды, которые максимизируют свободное евклидово расстояние для такого выбора сигналов. Их результаты показывают возможность построения кодов, характеристики которых на лучше характеристик двоичной ФМ без кодирования и которые имеют при этом более узкий спектр (ширина полосы между первыми нулями составляет 3/4 ширины полосы для двоичной Предложенные ими коды очень интересны, однако их рассмотрение выходит за рамки этой книги.

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

Один из них состоит в квадратурной ФМ со скоростью следования символов, составляющей 3/4 от скорости следования символов двоичной ФМ без кодирования, и последующем кодировании с Как следует из рис. 6.14, при значении длины кодового ограничения можно получить выигрыш от кодирования в Однако результаты сравнения такого метода с ЧМНФ могут измениться, если ввести значительную фильтрацию.

Задачи

(см. скан)

(см. скан)

<< Предыдущий параграф Следующий параграф >>
Оглавление