Сверточные коды. 4 Дисер с 15 СК и Мягкое дек с 55. Программноаппаратная реализация оптимального алгоритма декодирования каскадных кодов на базе кодов рида соломона в адаптивных системах обмена данными
 Скачать 5.5 Mb.
|
Коды РС в стирающем канале связиВсе перечисленные выше подходы к упразднению процедуры поиска локаторов ошибок сводятся к необходимости знать позиции ошибочных символов, что аналогично работе декодера в стирающем канале связи. Наличие стираний для кода, определенного над полем GF(q), означает, что демодулятор имеет q обычных выходных символов и (q + 1)-й символ, соответствующий стиранию. Предполагается, что при появлении стирания нет абсолютно никакой информации о том, какой символ был фактически передан [107]. Для исправления стираний в кодах РС необходимо ввести многочлен локаторов стираний, аналогичный многочлену локаторов ошибок:
где e – максимальное количество стираний, которое способен исправить код. Зная позиции стираний, можно вычислить Г(x) и подставить на эти места произвольные принятые символы, вычислив после этого S(x). Ключевое уравнение для исправления стираний примет вид:
Дальнейшее исправление стираний полностью соответствует классическому алгоритму нахождения значений ошибок по алгоритму Форни. Двукратная выдача кодового блокаИз предложенных методов этот наиболее прост в реализации. Суть его заключается в повторной выдаче каждого кодового блока РС. Для минимизации действия импульсной помехи все символы, поступающие в канал связи, перемежаются. На приемной стороне после деперемежителя кодовая последовательность восстанавливается, при этом символы, значения которых не совпадают с повторно принятыми, считаются ошибочными. Номера позиций этих символов поступают в декодер, где рассчитываются значения этих символов согласно алгоритму Форни. Таким образом, благодаря использованию двукратной выдачи кодового блока, удастся избежать процедуры вычисления позиций искаженных символов. Такие символы можно считать стертыми, а декодер, как известно, восстанавливает в два раза больше стираний, чем ошибок по классическому алгоритму [110]. Для определения эффективности данного подхода к декодированию кодов РС необходимо построить график BER предложенного кодека и сравнить кривые с классическим методом декодирования. Графики будут строиться нормированными относительно энергии, приходящейся на каждый бит принятого символа. Делается это для объективности оценки эффективности того или иного метода помехоустойчивого кодирования. Рассматриваться графики будут на примере СПД с QAM-16 модуляцией. Полученные графики представлены на рисунке 2.1. Рисунок 2.1 – Значения BER для кодов РС(15, 9) с двукратной выдачей кодового блока и с классическим способом декодирования Из рисунка 2.1 видно, что предложенный подход существенно уступает в помехоустойчивости классическому методу декодирования кодов РС и в дальнейшем он рассматриваться не будет. Произведение кодов РС и БЧХВ качестве другого способа замещения процедуры расчета локаторов ошибок рассмотрим произведение блоковых кодов, то есть систему кодирования, при которой для каждого символа внешнего кода рассчитываются проверочные символы внутренним кодом. При этом символы, для которых проверка четности внутреннего кода не выполняется, будут стираться. Таким образом, для внешнего кода будут известны ошибочные позиции, и необходимость использования БМА отпадает. В качестве внутреннего кода был выбран укороченный на семь символов код БЧХ (15, 11, 3). Укороченный код имеет такое же кодовое расстояние и записывается в виде БЧХ (8, 4, 3). Он способен исправить одну ошибку в каждом принятом символе внешнего кода и детектировать две ошибки [10]. Рисунок 2.2 – Значения BER для произведения кода РС(15, 9) и кода БЧХ(8, 4) в сравнении с классическим способом декодирования Для оценки эффективности этого подхода построим график BER и сравним его с классическим методом декодирования. Графики представлены на рисунке 2.2. Как видно из рисунка 2.2, данный подход существенно уступает классическому алгоритму декодирования и в дальнейшем рассматриваться также не будет. Мягкие подходы к декодированию кодов РСАлгоритм декодирования кодов РС нельзя непосредственно обобщить таким образом, чтобы использовать мягкие решения демодулятора. Существуют лишь подходы, при которых нужно несколько раз производить декодирование с жестким решением [107]. Однако в частном случае, соответствующем стираниям в демодуляторе, можно применить алгебраическое декодирование [33]. В работе предлагаются два способа квантования принятого сигнала для двух типов сигналов: для PSK-модуляции и для QAM-модуляции. Для примера, квантование сигнала будет осуществляться на восемь уровней. При этом более высокое значение МРС будет соответствовать более надежно принятым символам [100, 127]. Формирование мягких решений символов при фазовоймодуляции При фазовой модуляции значение символа зависит только фазы принятого сигнала. В этом случае квантование целесообразно осуществлять только по углу отклонения принятого сигнала от номинальной точки сигнального созвездия. Такое созвездие представлено на рисунке 2.3 [90]. В качестве примера приведена СПД с QPSK-модуляцией при соотношении сигнал-шум 10 дБ. Более светлые области на сигнальном созвездии соответствуют наиболее надежным символам. Рисунок 2.3 – Созвездие принимаемого сигнала при QPSK модуляции и SNR=10 дБ с квантованием на 8 уровней Гистограмма распределения индексов достоверности символов (МРС) представлена на рисунке 2.4. На ней темным цветом показано распределение МРС, которые были определенны неверно. Рисунок 2.4 – Гистограмма распределения МРС принятого сигнала при QPSK и SNR=10 дБ с квантованием на 8 уровней Графики BER для оценки эффективности работы декодера Витерби с мягкими решениями по сравнению с жесткими решениями представлены на рисунке 2.5. Рисунок 2.5 – Значения BER для сверточного кода (171,133), работающего с жесткими и мягкими решениями при QPSK-модуляции Из рисунка 2.5 видно, что использование мягких методов при декодировании сверточного кода по алгоритму Витерби повышает ЭВК системы в среднем на 1.5 - 2 дБ при фазовой модуляции. Формирование мягких решений символов при квадратурной амплитудной модуляции При QAM-модуляции значение символа зависит не только от фазы, но и от амплитуды принимаемого сигнала, поэтому квантование сигнала осуществляется по прямоугольным зонам, площади всех зон при этом строятся равными [90, 114]. В работе также предложено оставлять открытыми границы зон, в которых с увеличением амплитуды сигнала, конкурирующие точки будут отсутствовать. Вид сигнального созвездия, иллюстрирующего данный подход, представлен на рисунке 2.6. Рисунок 2.6 – Созвездие принимаемого сигнала при QAM-16 модуляции и SNR=10 дБ с квантованием на 8 уровней В качестве примера рассматривается СПД с QAM-16 модуляцией и квантованием каждого принимаемого символа на восемь уровней при соотношении сигнал-шум в канале связи 10 дБ. Гистограмма распределения МРС принятого сигнала представлена на рисунке 2.7. Рисунок 2.7 – Гистограмма распределения МРС принятого сигнала при QAM-16 и SNR=10 дБ с квантованием на 8 уровней Для определения надежности оценок полученных описанным выше путем, Н вводится логарифмический коэффициент правдоподобия оценки L МРС :
где пр МРС вероятность правильной оценки символа, ош МРС вероятность ошибочной оценки. Графики зависимости коэффициента надежности оценки принятого символа от соотношения сигнал-шум в канале представлены на рисунке 2.8. P P Графики BER для оценки эффективности работы декодера Витерби с мягкими решениями по сравнению с жесткими решениями при QAM-16 модуляции представлены на рисунке 2.9. Из рисунка 2.9 видно, что при мягком декодировании сверточного кода по алгоритму Витерби, ЭВК системы в среднем повышается на 1 – 1.5 дБ при квадратурной амплитудной модуляции.
Использование мягких оценок для определениястираний Суть предлагаемого подхода заключается в том, чтобы для каждого принятого из канала связи символа получать мягкие решения от детектора. Сочетание описанного выше метода определения МРС с кодами РС позволяет избежать выполнения процедуры БМА. Для этого стираются наименее надежные символы, а дальнейшее декодирование сводится к поиску значений стертых позиций. Для оценки эффективности данного подхода при QPSK-модуляции в сочетании с кодом РС (15, 9) сравним его график BER с графиком при классическом способе декодирования. Графики представлены на рисунке 2.10. Рисунок 2.10 – Значения BER для СПД с QPSK-модуляцией и кодом РС(15, 9) при мягком и классическом декодировании Графики BER для СПД с QAM-16 модуляцией и кодом РС (15, 9) представлены на рисунке 2.11. Как видно из рисунков 2.10 и 2.11, использование мягких подходов в определении стертых символов уступает в помехоустойчивости классическому алгоритму поиска локаторов ошибок. Проигрыш составляет порядка 2 - 3 дБ, что существенно для работы СПД по радиоканалу, поэтому использование такого подхода в разрабатываемой системе нецелесообразно. Однако для проводных каналов связи, в которых соотношение сигнал-шум много выше, данный подход может быть применен как альтернатива ресурсоемкой процедуре БМА с целью экономии вычислительных мощностей. Рисунок 2.11 – Значения BER для СПД с QAM-16 модуляцией и кодом РС(15, 9) при мягком и классическом декодировании Исходя из анализа всех рассмотренных методов замещения процедуры БМА на получение стираний, можно прийти к выводу, что ни один из этих подходов не обеспечивает в должной степени помехоустойчивость СПК и уступает классическому методу декодирования РС. Поэтому в дальнейшем проектирование каскадного кодека будет строиться с использованием БМА. Обобщенный каскадный код на базе кодов РС и сверточных кодовДля повышения помехозащищенности СПК эффективна система каскадного кодирования с использованием кода РС на внешней ступени кодирования и сверточного кода – на внутренней. В качестве внутреннего кода выбран сверточный код памяти шесть с порождающими полиномами x6 x3 x2 x1 1 и x6 x5 x3 x2 1, что соответствует записи в восьмеричной системе (171, 133). Этот код наиболее эффективен в борьбе с одиночными ошибками и распространен во многих существующих стандартах цифровой связи [110]. При использовании сверточного декодера, работающего по алгоритму Витерби, важно получать из канала символы с мягким решением. Это позволяет повысить энергетический выигрыш от кодирования (ЭВК) на 2 - 3 дБ [98], поэтому предложенная система формирования МРС остается актуальной. На рисунке 2.12 представлены графики BER для описанного каскадного кода в сравнении с другими рассмотренными способами кодирования на примере СПД с BPSK-модуляцией. Рисунок 2.12 – Значения BER для всех рассмотренных СПД на примере BPSK-модуляции Как видно из рисунка 2.12, СПД с каскадным кодом является наиболее эффективной в плане помехоустойчивости среди всех рассмотренных, поэтому дальнейшая реализация кодека будет строиться по этому принципу. Описание всех представленных в этой главе моделей, разработанных в системах MATLAB, Simulink [92], можно найти, обратившись к Приложению А. Выводы по главеВ ходе выполнения работы были рассмотрены различные методы упразднения процедуры поиска локаторов ошибок по алгоритму Берлекэмпа - Месси. Все предложенные подходы сводятся к получению стираний из канала связи и дальнейшему поиску их значений. Однако эти алгоритмы оказались менее эффективными в помехоустойчивости по сравнению с классическим алгоритмом декодирования кодов РС. Из этого следует, что отказываться от процедуры БМА и полностью положиться на стирания, не целесообразно. Необходимо искать пути оптимизации этой процедуры. Также в работе предложены методы мягкого квантования принимаемого сигнала для фазовой и квадратурной амплитудной видов модуляции. Эти подходы доказали свою эффективность на примере декодирования сверточного кода по алгоритму Витерби. При этом средний ЭВК составил 1.5 - 2 дБ при фазовой модуляции и 1 - 1.5 дБ при квадратурной амплитудной модуляции. В ходе математического моделирования различных СПК было доказано, что наиболее эффективной из них является каскадная схема на основе кодов Рида - Соломона в качестве внешней ступени кодирования и сверточного кода – на внутренней ступени. При этом целесообразно использовать алгоритм Витерби с мягким входом при декодировании сверточного кода для достижения лучшей помехозащищенности системы. ГЛАВА 3.ПРОГРАММНО – АППАРАТНАЯ РЕАЛИЗАЦИЯ АДАПТИВНОГО КАСКАДНОГО КОДЕКА, ОПТИМИЗИРОВАННОГО ПОД АРХИТЕКТУРУ ПЛИС Реализация СПК будет осуществляться на базе ПЛИС фирмы ALTERA, что накладывает ряд ограничений, которые необходимо учесть при разработке. Устройство должно быть оптимальным с точки зрения затрачиваемых на его реализацию аппаратных ресурсов, энергопотребления и скорости его работы [57, 58, 59]. Кроме того, СПК должна иметь способность адаптироваться к изменяющимся характеристикам канала связи. Таким образом, разработка оптимального декодера каскадного кода требует решения трех основных задач: аппаратной реализации алгоритма Витерби для декодирования внутреннего сверточного кода; аппаратной реализации оптимального алгоритма декодирования внутреннего кода РС; разработки процедуры адаптивной подстройки кодека под изменяющиеся условия в канале связи. Аппаратная реализация алгоритма ВитербиСуществует несколько различных способов декодирования сверточных кодов. Наиболее эффективным из них является алгоритм Витерби, так как он является алгоритмом декодирования по максимуму правдоподобия. Однако он также является относительно ресурсоемким алгоритмом, поэтому аппаратная реализация оптимальной структуры декодера Витерби является актуальной задачей. Все дальнейшие операции декодера и его устройство будут рассматриваться на примере сверточного кода (171, 133). Структурная схема такого кодера представлена на рисунке 3.1. Рисунок 3.1 – Структурная схема сверточного кодера (171, 133) Декодер, работающий согласно алгоритму Витерби, можно условно разделить на пять основных устройств: BMU (Branch Metrics Unit), модуль расчета метрик ребер решетки; ACS (Add-Compare-Select), модуль сложения, сравнения и выбора метрик путей; SMS (State Metric Storage), регистр хранения метрик узлов; SPM (Survivor Path Memory), регистр хранения траектории, выживший путей; TBU (Traceback Unit), модуль обратного прохода. Схема включения этих устройств представлена на рисунке 3.2. Подробное описание работы каждого устройства приведено ниже [29].
Структура работы аппаратного декодера Витерби приведена на блок-схеме (рисунок 3.3).
Аппаратное описание структурытреллис-диаграммы Для работы декодера сверточных кодов ему необходимо хранить в своей памяти решетку, описывающую разрешенные переходы из одного состояния в другое. Так как эта решетка статична, то ее можно хранить в ROM (Read Only Memory). В аппаратном исполнении треллис-диаграмма будет представлена в виде двух таблиц. В обеих таблицах в качестве адреса выступает узел решетки на текущем этапе декодирования [62]. Каждому адресу ячейки (текущему узлу) первой таблицы соответствует следующий узел решетки при условии, что по каналу был передан ноль. Вторая таблица содержит состояния решетки при условии, что передана была единица. В таблице 3.1 приведено состояние ROM для сверточного кода (171, 133). Здесь каждому следующему состоянию (младшие шесть бит ячейки) добавляются два бита с выхода кодера (старшие два бита). Таким образом, для перехода в следующее состояние решетки необходимо обратиться в ROM по адресу, равному текущему состоянию, при этом память возвращает следующее состояние решетки, а также состояние кодера, что удобно при расчете метрики ветви. Таблица 3.1. Таблица переходов по состояниям решетки
Для динамически перестраиваемых решеток (при разработке адаптивных сверточных кодеков) инициализация памяти переходов состояний должна осуществляться в начале каждого сеанса связи. Тогда схема работы такого блока памяти примет следующий вид (рисунок 3.4) [43]:
Аппаратная реализация блокаBMU Блок BMU рассчитывает метрику предполагаемой кодовой комбинации. Для этого он генерирует все возможные ветви решетки для текущих узлов решетки и сравнивает их с принятой из канала связи кодовой комбинацией. В качестве метрики в данном случае выступает хэмминговое расстояние между предполагаемой кодовой последовательностью и принятой, что в свою очередь представляет собой количество отличающихся друг от друга разрядов в этих комбинациях. Для выбранного кода из каждого текущего состояния могут выходить две ветви. Одна формируется из предположения декодера о том, что принятый символ был нулем, и вторая – из предположения о том, что передавалась единица [77]. Схема BMU-блока представлена на рисунке 3.5. На схеме сравнение производится с помощью поразрядной операции XOR, а расчет метрики осуществляется подсчетом единиц в полученном векторе.
Аппаратная реализация блокаACS Как и следует из названия, блок ACS выполняет три основные функции: прибавляет, сравнивает, выбирает. На вход ACS подаются все возможные метрики ветвей решетки, сгенерированные блоком BMU. Два сумматора складывают на каждом узле решетки полученную метрику ветви с метрикой пути, накопленной в данном состоянии [80]. После обработки всех состояний на текущем шаге решетки в каждое следующее состояние приходит по два конкурирующих пути. Метрики этих путей сравниваются, и сохраняется только путь с наилучшей метрикой [70]. Полученные метрики состояний записываются в блок SMS, а траектория выживших путей – в блок SPM. Схема блока ACS представлена на рисунке 3.6
Блоки SMS иSPM Блок SMS представляет собой набор регистров, хранящих информацию о метриках путей, выживших на текущем этапе декодирования. Эта информация необходима блоку ACS для определения веса пути на следующем этапе и выбора из двух конкурирующих путей того, чей вес меньше. Регистры SMS-блока обновляются каждый такт с поступлением новых данных на декодер [81]. Блок SPM реализуется в виде набора сдвиговых регистров, хранящих в памяти информацию о траектории выживших путей. На каждом такте декодирования, после выбора выжившего пути, в память SPM-блока записывается текущее состояние решетки, из которой этот (выживший) путь исходит. Так как в каждое последующее состояние приходит по два конкурирующих пути из разных узлов, отличающихся друг от друга только младшим разрядом, то в SPM-блок за один такт декодирования записывается только один бит информации. Зная структуру решетки, по этим данным можно восстановить траекторию всего пути от начала до конца, тем самым декодировав принятую информацию [64]. Обратный проход решетки. МодульTBU После того как треллис-диаграмма заполнена, то есть число тактов декодирования достигло глубины декодирования, из всех выживших путей выбирается единственный путь по правилу максимального правдоподобия, то есть минимального веса. Из блока SPM извлекается траектория этого пути. Далее необходимо совершить обратный проход решетки по выбранной траектории с целью восстановления принятых данных. На рисунке 3.7 приведен алгоритм обратного прохода решетки и выдачи декодированных данных. При завершении прямого прохода решетки в регистр блока TBU записывается выбранная траектория выжившего пути. На каждом такте обратного прохода этот регистр сдвигается на один бит вправо. Младший бит регистра участвует в восстановлении предыдущего состояния решетки. Процедура повторяется вплоть до достижения начального состояния решетки.
Для формирования предыдущего состояния решетки необходимо текущее состояние сдвинуть на один такт влево, а на место младшего разряда записать младший бит регистра траектории пути. При этом старший бит регистра текущего состояния решетки – есть декодированный бит принятой последовательности (рисунок 3.8) [65].
Аппаратная реализация оптимального алгоритма декодирования кода Рида – СоломонаНа заре создания первых декодеров кодов РС они строились на многоразрядных сдвиговых регистрах, умножителях, сумматорах и большом количестве других АЛУ. Развитие современной микроэлектроники позволяет реализовать эти АЛУ на одном кристалле в корпусе микросхемы – ПЛИС. Описание алгоритмов для ПЛИС требует соблюдения определенных правил, а также накладывает некоторые ограничения по скорости работы устройства, занимаемой им площади на кристалле ПЛИС и по энергопотреблению системы. Под оптимизацией алгоритма для ПЛИС будет пониматься некоторое приемлемое соотношение между этими тремя параметрами [3, 44]. В этом параграфе будут описаны существующие высокоскоростные алгоритмы реализации кодеков РС, рассмотрены способы оптимизации этих алгоритмов, а также будут предложены различные подходы к их аппаратной реализации. Реализация алгоритма быстрого декодирования кодов РС, описанного в первой главе, на ПЛИС сводится, как правило, к разработке трех основных АЛУ: SC-block (Syndrome Computation block). Блок расчета синдромного многочлена. Выполняет вычисления согласно формуле (3.1):
где R(z) – полином принятых кодовых слов, α – примитивный элемент поля Галуа. KES-block (Key-Equation block). Блок, решающий ключевое уравнение:
где Λ(z) – полином локаторов ошибки, t – корректирующая способность кода. CSEE-block (Chien Search and Error Evaluator block). Блок, выполняющий процедуру Ченя по поиску корней полинома локаторов ошибок путем последовательного перебора всех возможных значений и рассчитывающий значение ошибки согласно алгоритму Форни:
где Y – значение ошибки, z производная от полинома локаторов ошибки, j – номер позиции в принятом векторе R, на которой произошла ошибка [15, 18, 39]. Все три блока работают в конвейерном режиме, обрабатывая поступающую информацию последовательно друг за другом [66, 69]. Оптимальная реализация каждого из этих блоков будет подробно описана в этом параграфе. Также будет рассмотрен алгоритм адаптивной подстройки декодера РС для динамически изменяемых параметров канала связи [116, 117]. Оптимальная реализацияSC-блока Блок SC рассчитывает синдромный многочлен на основе поступающих в декодер данных из канала связи. Этот многочлен имеет степень c = n – k, равную количеству проверочных символов в блоке кода РС, следовательно, синдром должен храниться в регистре памяти размером c ячеек [53]. Каждая i-я ячейка вычисляется согласно (3.1). В аппаратном виде схема вычисления синдрома примет вид:
Блок SC состоит из набора таких элементов, их количество зависит от вносимой кодом избыточности. Эти соединяются между собой по принципу сдвигового регистра, благодаря чему через n тактов, когда декодер примет полный кодовый блок, на выходе SC-блока будет сформирован синдромный многочлен (рисунок 3.10) [76].
Оптимальная реализацияKES-блока После того как расчет синдромного многочлена завершен, эти данные поступают в KES-блок, задача которого определить два полинома: полином локаторов ошибок и полином значений ошибок. Наиболее проблемным местом в алгоритме декодирования кодов РС является реализация KES-блока. Скорость работы этого блока непосредственно влияет на пропускную способность всего декодера, в отличие от относительно простых SC- и CSEE-блоков [40, 52], поэтому особое внимание будет уделено именно оптимизации KES-блока. Как было оговорено выше, существуют различные алгоритмы поиска полинома локаторов ошибок, такие как алгоритм Евклида и алгоритм Гурусвами - Судана. Однако они не подходят для аппаратной реализации высокоэффективного декодера кодов РС. Поэтому для разрабатываемой СПК был выбран алгоритм Берлекэмпа – Месси [34, 35]. БМА – сложный алгоритм с множеством вложенных путей и условных переходов. В явном виде он неприспособлен к архитектуре ПЛИС и требует оптимизации и доработки [106]. Его удобнее всего рассматривать как итеративный процесс построения линейного сдвигового регистра с обратной связью [115]. Позднее этот алгоритм был доработан, что позволило сократить длину сдвигового регистра до минимальной с сохранением требуемых свойств. Реализация обновленного алгоритма была описана Р. Блейхутом в работе [87] и получила название безынверсионного БМА (iBM) [11]. Данный алгоритм находит скалярные произведения z и z вместо z и z, что требует ключевое уравнение (3.2). Однако при дальнейшем прохождении процедуры Ченя, эти выражения дадут одинаковые результаты, поэтому в дальнейшем описании алгоритма множитель β будет опускаться в обозначениях. Описать работу алгоритма iBM можно с помощью следующего псевдокода [2]: Инициализа ция: 0 b0 1, 0 b0 0 для i 1,2,..., t. k0 0. 0 1. 0 0 i i Вход:si, i 0, 1, ..., 2t1. for r 0 step 1 until 2t-1 do begin Шаг 1: δr sr λ0 r sr 1 λ1 r ... sr t λt r Шаг 2: r1 r λir r λi1 r , i 0, 1, ... , t Шаг then 3: if δr 0 and kr 0 begin bir1 ir, r1 r i 0, 1, ... , t end kr 1 kr 1 else begin bir1 bi1 r, r 1 r kr1 kr1 i 0, 1, ... , t end end end for i 0 step 1 until t-1 do |