(по цифровому вещанию) Dvorkovich_V_Cifrovye_videoinformacionnye_sistemy

Глава 19. Помехоустойчивое кодирование в системах передачи

Используемые проверочные матрицы LDPC-кода, помимо того, что они описывают IRA-код, имеют некоторую периодичность в структуре, что позволяет существенно упросить их хранение, а также позволяет получить эффективную архитектуру декодеров таких кодов [7.31].

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

Обозначим как c1, c2, . . . , cwl индексы проверочных узлов, соединенных с первым информационным узлом в группе, тогда индексы проверочных узлов любого i-го информационного узла в группе можно получить, воспользовавшись формулами (19.58):

где q = (n − k)/Q.

Таким образом, для полного описания структуры матрицы используемого кода необходимо указать проверочные узлы, соединенные с первым информационным узлом в каждой из групп. Код стандарта DVB-T2 предусматривает использование фиксированного размера групп для всех скоростей и размеров блоков — это Q = 360 битовых узлов, при этом очевидно, что число групп в матрице будет отличаться для различных скоростей и размеров блоков. В стандарте приводятся таблицы, в которых перечисляются проверочные узлы для первого битового узла каждой из групп для всех скоростей кодирования и используемых блоков передачи данных.

Пример такой таблицы стандарта DVB-T2 для короткого блока (N = 16 200) со скоростью кодирования 2/3 представляет собой запись матрицы размерности 10 800 × 16 200 и имеет следующий вид:

19.6.4.Алгоритмы декодирования низкоплотностных кодов

Рассмотрим несколько алгоритмов декодирования LDPC-кодов — классические, предложенные еще Р. Галлагером, а также еще два более новых алгоритма.

Р. Галлагер в своей работе [7.25] предложил два итеративных алгоритма декодирования низкоплотностных кодов. Первый — алгоритм с распространением доверия (belief propagation, BP). Этот алгоритм обладает максимальной эффективностью среди всех известных алгоритмов декодирования. Доказано, что алгоритм BP достигает максимума правдоподобия, при условии, что проверочная матрица кода не содержит циклов [7.26]. Расплата за столь высокую эффективность — максимальная вычислительная сложность среди всех известных алгоритмов.

Второй алгоритм, предложенный Р. Галлагером, — алгоритм с инверсией бита (bit flip algorithm, BF). Он очень прост в реализации и использует жесткие решения модема относительно принятых битов. Расплата за простоту — низкая эффективность этого алгоритма. Оба алгоритма в настоящее время хорошо исследованы и для них разработано множество модификаций. Также существует и множество альтернативных оригинальных алгоритмов декодирования LDPC-кодов.

Начнем рассмотрение с алгоритма BF [7.32]. Его можно представить в виде основных шагов, выполняемых итеративно:

–инициализация,

–обновление проверочных узлов,

–обновление битовых узлов,

–инверсия битов.

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

где xni — входящие в проверочный узел m сообщения, σm — исходящее из этого проверочного узла сообщение, dr — количество смежных битовых узлов.

Глава 19. Помехоустойчивое кодирование в системах передачи

На рис. 19.37а изображено обновление проверочных битов с использованием графа Таннера. Здесь xn — по существу не что иное, как знак принятого из канала значения, полученный на этапе инициализации. В случае алгоритма с инверсией бита исходящее сообщение σm может принимать всего два значения — 0 или 1, что, в свою очередь, показывает, выполняется соответствующая проверка или нет.

Третий шаг алгоритма — обновление битовых узлов:

где Zn — исходящее из битового узла n сообщение, σmi — входящие в этот битовый узел сообщения, dc — количество смежных проверочных узлов.

Графическая интерпретация этого шага представлена на рис. 19.37б. В случае алгоритма с инверсией бита значение исходящего сообщения Zn равно числу невыполненных проверок для битового узла n. После того как найдены значения Zn для всех битовых узлов, находится и инвертируется бит, для которого Zn максимально.

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

Рис. 19.37. Алгоритм с инверсией бита: а — обновление проверочных узлов, б — обновление битовых узлов

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

Алгоритм BP в трактовке, предложенной в [7.31], можно представить в виде следующих шагов:

–инициализация,

–обновление проверочных узлов,

–обновление битовых узлов,

–вынесение жестких решений.

Последние три шага выполняются итеративно.

19.6. Низкоплотностные коды

Рис. 19.38. Алгоритм с распространением доверия: а) инициализация, б) обновление проверочных узлов, в) обновление битовых узлов

На рис. 19.38а изображена инициализация алгоритма. Znmi — сообщения от битового узла n к соответствующему проверочному узлу mi, rn — канальное логарифмическое отношение правдоподобия (log likelihood ratio, LLR) для битового узла n.

Второй шаг алгоритма — обновление проверочных узлов — изображен на рис. 19.38б. Znim — входящие сообщения для проверочного узла m от dr смежных битовых узлов, ynim — исходящие сообщения от узла m к битовым узлам ni. Исходящие сообщения рассчитываются по следующей формуле:

Выражение (19.64) — наиболее трудоемкая операция во всем алгоритме, поэтому обычно функцию log(1 + e−|x|) представляют таблицей для нескольких значений x, при этом вычисление (19.64) сводится к двум обращениям к таблице и нахождению разности полученных значений.

Третий шаг — обновление битовых узлов — изображен на рис. 19.38в. На рисунке ynmi — входящие сообщения для битового узла n от dc смежных проверочных узлов, Znmi — исходящие сообщения для каждого проверочного узла mi.

dc

После обновления всех битовых узлов находятся жесткие оценки принятых битов, которые представляют собой не что иное, как знак Zn:

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

Глава 19. Помехоустойчивое кодирование в системах передачи

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

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

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

Рассмотрим две распространенные модификации алгоритма BP — UMP-BP и UMP-APP [7.33]. Префикс UMP означает критерий оценки достоверности принятых битов — равномерно наиболее мощный (uniformly most powerful). Отличительной особенностью этих алгоритмов является отсутствие необходимости в вычислении отношения сигнал/шум на входе приемника, что позволяет существенно упростить декодирование.

Рассмотрим алгоритм UMP-BP. Как было сказано выше, этот алгоритм является модификацией алгоритма BP и отличается от него только шагом обновления проверочных узлов. Вычисление исходящих после проверки сообщений осуществляется по формуле (19.62), однако:

т. е. используется только первое слагаемое (19.63), что позволяет вычислять ynim как минимальный элемент проверки.

Алгоритм UMP-APP можно рассматривать как дальнейшее упрощение алгоритма UMPBP. Этот алгоритм отличается от алгоритма

UMP-BP шагом обновления битовых узлов. Здесь вычисляется только одно исходящее сообщение от битового узла n (рис. 19.39), вместо dc, как это было в BP и UMP-BP алгоритмах.

На рис. 19.40 изображены зависимости вероятности битовой ошибки от отношения сигнал/шум для рассмотренных алгоритмов декодирования. Результаты приведены

для кода скорости 3/4 и размерности 64 800 стандарта DVB-T2, число итераций декодирования для всех алгоритмов равно 20.

19.6.5.Оценка сложности алгоритмов декодирования

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

Начнем с алгоритма BF. Вычисление одной проверки требует сложить значения всех dc проверок для данного бита (выполнить dc − 1 операцию сложения), т. е. для N битов понадобится N · (dc − 1) сложений. Обновление проверочных узлов требует сложить все dr битов участвующих в проверке, что для M проверок потребует M · (dr − 1) операций сложения. Поиск максимального Zn требует сравнения всех N элементов, что требует (N − 1) операций.

Итого для выполнения алгоритма BF требуется M (dr −1) + N dc −1 операций для одной итерации обработки блока из N битов.

При анализе сложности алгоритма BP будем считать, что инициализация выполняется модемом, т. е. на вход декодера поступает последовательность мягких оценок. Тогда начнем со второго шага алгоритма. Вычисление yn,m для i-го бита представляет собой вычисление dr − 1 раз функции g(a, b), которая требует выполнения двух операций взятия знака, двух операций умножения, одну операцию сравнения и две операции обращения к памяти, всего 7 операций, итого 7M (dr − 1). При этом для каждой проверки находится dr значений yn,m, итого для M проверок имеем 7M dr (dr − 1) операций.

Обновление битов требует нахождения значения Znmi для каждой из dc проверок, входящих в битовый узел n. Вычисление Znmi требует выполнения dc − 1 вычислительных операций, итого для N битов N dc(dc − 1) операций.

Вычисление жесткого решения Zn потребует одной операции сложения и одной операции взятия знака для каждого бита кодового слова, т. е. 2N операций.

Вычисления можно несколько упростить, если объединить вычисления на шагах 3 и 4. И сначала вычислять сумму Zn, что потребует dc операций для

Глава 19. Помехоустойчивое кодирование в системах передачи

одного бита, т. е. N dc операций для всего кодового слова. А суммы Znmi можно находить вычитанием из Zn соответствующего значения ynmi , что потребует одной операции сложения для каждой проверки бита n, т. е. dc операций. Для всего кодового слова получим N dcопераций. То есть затраты на 3-й и 4-й шаг составят N dc + N dc + N = N (2dc + 1), где дополнительные N операций — взятие знака для получения жесткого решения.

На каждой итерации вычисляется синдром, что требует, как было показано выше, M (dr − 1) операций.

Всего для выполнения алгоритма BP требуется M (dr − 1) + 7M dr(dr − 1) + + N (2dc + 1) операций.

Рассмотрим теперь алгоритм UMP-BP. Ключевое отличие здесь — это второй шаг алгоритма, который позволяет существенно снизить вычислительные затраты на декодирование. Для нахождения ynim для i-го бита по прежнему требуется dr − 1 раз найти значения функции g(a, b). Однако за счет отказа от вычисления LUT g (a, b) нахождение модуля ynim сводится к поиску минимального значения среди входящих в поверку битов за исключением i-го. А знак находится как произведение всех знаков битов, входящих в проверку, за исключением i-го. Более того, как нетрудно показать, для расчета всех ynim достаточно найти два значения ynim — для бита, обладающего минимальным значением Znmi , модули всех остальных ynj m,j=i будут одинаковыми, различаться будут только их знаки [7.33]. Можно показать, что поиск двух минимальных элементов в массиве может быть выполнен за dr + log2 dr − 2 операций сложения [7.33]. Поиск знака может осуществляться следующим образом: находится произведение знаков всех битов, входящих в проверку, что требует dr − 1 операций, а затем для каждого ynim выполняется умножение на знак Znmi , т. е. dr операций для каждого бита, всего получаем N (dr + log2 dr − 2 + dr − 1 + dr ) = N (3dr + log2 dr − 3) операций.

Таким образом, для выполнения алгоритма UMP-BP требуется M (dr − 1) + + N (3dr + log2 dr − 3) + N (dc + 1) операций.

Алгоритм UMP-APP дополнительно упрощает и обновление битов, которое, по сути, аналогично нахождению жестких решений в алгоритме BP, что требует N dc операций, и еще N операций на взятие знака. То есть для выполнения алгоритма UMP-APP потребуется M (dr − 1) + N (3dr + log2 dr − 3) + N (dc + 1) операций. Вычислительная сложность всех рассмотренных алгоритмов сведена в табл. 19.9.

Таблица 19.9. Вычислительные затраты на выполнение одной итерации декодирования блока из N бит для различных алгоритмов

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

Основные методы полосовой модуляции можно разделить на следующие виды:

–амплитудная манипуляция (ASK — Amplitude Shift Keying);

–частотная манипуляция (FSK — Frequency Shift Keying);

–фазовая манипуляция (PSK — Phase-Shift Keying);

–квадратурная амплитудная модуляция (QAM — Quadrature Amplitude Modulation).

Способы приема информации разделяют на два вида:

–когерентный прием, при котором демодулятор использует информацию о фазе несущей;

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

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

В практике передачи цифровой информации чаще всего используется фазовая манипуляция и квадратурная амплитудная модуляция.

Глава 20. Системы модуляции и сигнального кодирования информации

Рис. 20.1. Сигнальные созвездия при амплитудной (а) и фазовой (б) манипуляции

Вобщем виде аналоговый сигнал, промодулированный дискретной цифровой информацией, можно представить следующей формулой:

В соответствующий момент времени он принимает одно из K = 2k дискретных значений, множество которых называется сигнальным алфавитом, а k — число битов, которыми может быть определен весь сигнальный алфавит [7.34–7.36].

20.1.1. Одномерные и двумерные созвездия

На рис. 20.1а приведены варианты одномерных созвездий при амплитудной манипуляции (ASK) для двух, четырех, восьми и шестнадцати значений амплитуды U (k) и неизменном значении частоты ω0 = 2πf0 и фазы φ(t) = φ0. Аналогичную структуру одномерных созвездий можно представить при частотной манипуляции (FSK) в радиосигнале.

Рис. 20.1б иллюстрирует варианты двумерных созвездий при фазовой манипуляции (PSK) для двух (BPSK — Binary Phase-Shift Keying), четырех, восьми и шестнадцати значений фазы φ(k) и неизменном значении амплитуды U (t) = U0.

При построении двумерных созвездий используются две составляющие (синфазная и квадратурная):

поскольку u(k) = U0 cos[ω0t + ϕ(k)] = I cos ω0t − Q sin ω0t.

Сигнальный алфавит характеризуется двумя основными параметрами — скоростью и помехоустойчивостью. Скорость сигнального алфавита определяется в битах и равна Rk/2.

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

d0 = 2 — нормированное расстояние между двумя точками созвездий при ASK-2 или PSK-2, а σ — среднеквадратический уровень созвездия, равный

Cn — длина вектора n-й точки созвездия.

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

20.1.2. Сигнальные созвездия квадратурно-амплитудной модуляции

Чаще всего используется одновременная передача двух отдельных k-битовых информационных блоков на двух несущих, находящихся в квадратуре (cos ω0t и sin ω0t), называемая квадратурно-амплитудной модуляцией (QAM):

u(k) = I(k) cos ω0t − Q(k) sin ω0t = Re {[I(k) + jQ(k)] exp(jω0t)} =

= U (k) cos[ω0t + ϕ(k)], (20.4)

где U (k) = I2(k) + Q2(k), ϕ(k) = arctg QI((kk)) .

На рис. 20.2 приведены сигнальные созвездия квадратурно-амплитудной модуляции — от QAM-4, обычно обозначаемой как QPSK (Quadrature Phase Shift Keying) или 4-PSK, до QAM-64. При QPSK используется два бита на отсчет, при QAM-8 — 3 бита (старшие два бита — в прямоугольниках, а младший бит — в кружках), при QAM-16 — 4 бита (старшие два бита — в прямоугольниках, а два младших — в кружках), при QAM-32 — 5 бит (старшие два бита — в больших прямоугольниках, следующий на ними бит — во вложенных меньших прямоугольниках, а два младших бита — в кружках) и при QAM-64 — 6 бит (старшие два бита — в серединах больших квадратов, следующие за ними два бита — в серединах меньших квадратов, а два младших бита — в кружках).

В табл. 20.1 приведены результаты расчетов минимального расстояния между точками созвездий, среднеквадратического уровня сигналов и межточечного расстояния, нормированного к этому уровню для различных созвездий ASK, PSK и QAM.

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

Радиосигнал с квадратурно-амплитудной модуляцией демодулируется путем умножения на два несущих колебания, сдвинутых по фазе относительно друг друга на 90◦, а результаты умножения фильтруются с использованием ФНЧ.