7.2.6. Вопросы реализации

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

7.2.6.1. Декодеры с жестким решением. В последнее время было построено несколько декодеров с жестким решением, работающих при высоких скоростях поступления данных (около нескольких мегабит в секунду и выше). Первый из этих декодеров подробно описан в работе Форни и Боуэра [86]. Структура всех этих декодеров одинакова (рис. 7.20), хотя детали реализации могут быть различными.

Предположим, что используется систематический код с Данные обрабатываются в декодере следующим образом. После получения информационной последовательности и проверочной последовательности копия кодирующего устройства вычисляет синдромную последовательность После этого принятая информационная последовательность задерживается на период времени, равный задержке в буфере декодера и задержке, происходящей в центральном процессоре декодера. Для восстановления последовательности ошибок нужна лишь синдромная последовательность так что в дальнейшем в декодере обрабатывается лишь эта последовательность. Последовательность записывается в буфер декодера, представляющий собой запоминающее устройство с произвольной выборкой (ЗУПВ). По мере необходимости символы синдрома извлекаются из буфера центральным процессором декодера и поступают в блок, изображенный в нижней части рис. 7.20. Центральным процессором в буфер возвращаются корректирующие символы Извлечение символов синдрома из буфера и возвращение в буфер корректирующих символов происходят в соответствии с алгоритмом декодирования Фано. Скорость, с которой происходят эти извлечения и возвращения, сильно меняется со временем, поскольку меняется число операций, необходимых для декодирования одного символа. Исправляющие символы извлекаются, конечно, из буфера с

Рис. 7.20. Типичная структура высокоскоростного декодера с жестким решением

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

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

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

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

При осуществлении декодирования вперед по кодовому дереву регистр сдвигается вправо. Оценки символов последовательности ошибок помещаются в устройства для хранения и Используя содержимое регистра алгоритм Фано выдает новые оценки для ошибок. Если делается предположение об ошибке в последовательности то порождающий многочлен кода складывается с содержимым регистра по модулю 2 для устранения влияния этой ошибки. При движении назад последние символы последовательностей используются для того, чтобы восстановить содержимое регистра таким, каким оно было до принятия пробного решения. При движениях назад [регистр сдвигается влево] символы синдрома удаляются из левого конца регистра и помещаются в ЗУПВ для хранения Если согласно алгоритму требуется поиск до глубины, равной глубине обратного поиска, то это запоминающее устройство будет целиком заполнено символами синдрома. Затем после того, как декодер снова начинает двигаться вперед, эти символы синдрома возвращаются в регистр и ЗУПВ для снова начинает заполняться символами последовательности

Устройство управления алгоритмом Фано реализует множество правил при декодировании (см. табл. 7.1), определяет соотношение между значениями метрики и текущим порогом. Аппаратура для вычисления метрики пути при использовании кодов с и с жестким решением весьма проста. Пусть приращения метрики на ребра равны при наличии на ребре нуля, одной и двух ошибок соответственно. Предположим, что приращение порога А является целым числом. Этот выбор соответствует отношению метрик, равному Метрика может накапливаться в двух счетчиках. Первый из них является циклическим счетчиком с А разрядами, вычисляющим величины по модулю А и сдвигающимся вправо или влево в зависимости от того, движется ли декодер вперед или назад (заметим, что приращение ребра равно 1 по модулю А независимо от того, меняется порог или нет). Когда содержимое первого разряда циклического счетчика равно 1, значение метрики равно а когда содержимое последнего разряда равно 1, значение метрики равно Другой счетчик служит для накапливания величин, кратных А (А-счетчику). Тогда фактическое значение метрики будет равно сумме показаний счетчика по модулю А и увеличенного в А раз показания А-счетчика.

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

Как следует из (7.55), оценка переданной информационной последовательности легко получается в виде и необходимым корректирующим символом является

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

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

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

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

исследовано несколько новых методов. Один из них — метод быстрого уменьшения порога. Этот метод был применен в высокоскоростных декодерах для уменьшения среднего числа операций С [86]. В основе метода лежит следующее. Декодер, работающий при скорости, меньшей большую часть времени двигается вперед по правильному пути или ненамного возвращается назад для исправления одной или двух ошибок. Метод быстрого уменьшения порога уменьшает долю времени, которая тратится на эти кратковременные поиски, снижая таким образом С для декодеров с и с жестким решением. Значения метрики в случае нуля, одной или двух ошибок выбираются равными соответственно или 6). Кроме того, предполагается, что два ребра, выходящие из одной вершины, являются дополнительными. В этом случае имеется ряд условий, при которых уменьшение порога не вызывает обратного поиска. Последнее выполняется, если, во-первых, предыдущее изменение порога состояло в его увеличении и, во-вторых, с момента предыдущего изменения порога на данном ребре не возникало ошибок. В этом случае все другие пути должны лежать ниже текущего порога (из-за выбора метрики). Если текущее ребро содержит ошибку, вызывающую нарушение порога, то порог можно немедленно понизить на поскольку ни один из других путей не лежит выше порога. После этого декодер может продолжать движение вперед. Однако вновь быстро уменьшать порог нельзя до тех пор, пока он не будет повышен.

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

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

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

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

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

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

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

Зависимость произведения необходимого для достижения значений от показателя Парето показана на рис. 7.21. Требуемое значение сильно зависит от При увеличении от 1,0 до 1,5 значение можно уменьшить на два порядка. Как показано на рис. 7.14, в случае когерентной системы с фазовой модуляцией этого можно достичь увеличением

Рис. 7.21. Зависимость значения необходимого для достижения от показателя Парето

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

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

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

Рассмотрим, например, реализацию декодера с -уровневым мягким решением, структура которого аналогична структуре, изображенной на рис. 7.20. Вместо того чтобы вводить в буфер один символ синдрома на каждое ребро, приходится запоминать дополнительных символов на ребро, соответствующих числу символов в канале. Таким образом, для достижения того же значения емкость ЗУПВ буфера должна быть в раз большей, чем в случае жесткого решения [если устройство задержки, в котором хранится последовательность также является частью ЗУПВ, то емкость последнего всего в раз больше]. Кроме того, вычисление метрики существенно усложняется при увеличении интервала значений метрики. Это приводит к замедлению вычислений, что снижает скорость вычислений при фиксированной скорости поступления данных. Таким образом, значение

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

Пример. Возникающие сложности можно оценить с помощью рис. 7.14 и 7.21. Предположим, что декодер с жестким решением достигает значения Такое значение позволяет получить при (в соот ветствии с рис. 7.21). Для кода с значение требуемое для достижения составляет (из рис. 7 14). При стремлении сохранить прежнюю емкость ЗУПВ произведение при квантовании на восемь уровней следует уменьшить в 10 раз, так что для достижения нужно иметь Из рис. 7.14 следует, что для достижения того же значения нужно взять Таким образом, сравнивая декодеры примерно одинаковой сложности, получаем, что фактический дополнительный выигрыш от кодирования при переходе к квантованию на восемь уровней составляет всего

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

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