Крук Е.А. (ред.) Исследование LDPC кодов. Сборник статей. Часть 2

Подождите немного. Документ загружается.

А. В. Козлов,

аспирант

СанктПетербургский государственный университет

аэрокосмического приборостроения

ИССЛЕДОВАНИЕ ПРИМЕНЕНИЯ LDPCКОДОВ СОВМЕСТНО

C АЛГОРИТМАМИ БИТЛОАДИНГА В OFDMСИСТЕМАХ

Современные телекоммуникационные системы требуют приме&

нения эффективных методов передачи и помехоустойчивого коди&

рования для обеспечения высоких информационных скоростей. В

данной работе исследуются схемы передачи данных в беспровод&

ных системах связи, основанные на применении алгоритмов бит&

лоадинга и LDPC&кодов. В качестве примера рассматривается при&

менение этих методов в системах IEEE 802.11a.

Физический уровень систем передачи данных стандартов IEEE

802.11a основан на технологии OFDM. Идея данного метода со&

стоит в разбиении имеющейся полосы частот на поднесущие и про&

ведении эквализации независимо для каждой из них. В IEEE

802.11a в качестве модуляции в каждой поднесущей использует&

ся равномерная модуляция BPSK/QPSK/16QAM/64QAM. В стан&

дартных системах решение о смене вида модуляции принимает

MAC&уровень. Недостатками стандартного подхода является то,

что каждая поднесущая имеет свой коэффициент затухания сиг&

нала, отличающийся от коэффициентов затухания остальных, а

этот факт не учитывается, и используется одна и та же модуляция

в каждой частоте.

При использовании многочастотного метода передачи необхо&

димо учитывать тот факт, что в частотно&селективном канале раз&

личные частоты имеют различные коэффициенты передачи, т. е.

разумно использовать в различных подканалах сигнальные созвез&

дия разных размеров, а также распределять энергию между подка&

налами неравномерно (процедура битлоадинга).

Известно множество алгоритмов, использующих принцип бит&

ло&адинга, таких как алгоритмы Хугеса–Хартогса [1], Фишера–

Хубера [2], Кронгольда–Рамчандрана–Джонса (KRJ) [3] и т. д.

Алгоритмы битлоадинга можно разделить на две группы:

1) алгоритмы минимизации общей мощности передатчика при

фиксированной скорости передачи и вероятности ошибки;

2) алгоритмы максимизации скорости передачи при фиксиро&

ванной вероятности ошибки и общей мощности передатчика.

В данной работе рассмотрены алгоритмы из того и другого клас&

са в условиях совместного применения с LDPC [4] и сверточными

кодами (Convolutional Code, CC) в OFDM&системах, а также рас&

смотрено влияние скорости изменения и проблем оценивания ка&

нала на алгоритмы битлоадинга.

Применение LDPCкодов совместно c алгоритмом KRJ

Алгоритм KRJ является алгоритмом минимизации общей мощ&

ности передатчика при фиксированной скорости передачи и вероят&

ности ошибки. В системах IEEE 802.11a он позволяет добиться энер&

гетического выигрыша до 5 дБ при низких скоростях передачи, вы&

игрыш уменьшается до 1,5–2 дБ с ростом скорости передачи (рис. 1).

Сравнение производительности LDPC и сверточного кода при исполь&

зовании KRJ&алгоритма битлоадинга дано на рис. 2. Как видно из

результатов имитационного моделирования, LDPC&коды позволяют

добиваться дополнительного (2–2,5 дБ) энергетического выигрыша

в сравнении со сверточными кодами в системах IEEE 802.11a при

использовании KRJ&битлоадинга.

802.11, 20 MГц – ширина полосы, PEG(1728, 1296) – помехоустойчивый код,

10 итераций, многопороговый декодер

Рис. 1. KRJалгоритм совместно с LDPCкодом:

– KAM64 (54 Mбит/с); – KRJбитлоадинг (54 Mбит/с);

– KAM64 (36 Mбит/с); – KRJбитлоадинг (36 Mбит/с);

– KAM64 (18 Mбит/с); – KRJбитлоадинг (18 Mбит/с);

15 25 30

0.1

0.01

0.001

0.0001

20 35

SNR, дБ на передатчике

PER

Применение LDPCкодов совместно c алгоритмом адаптации

по отношению сигнал/шум в поднесущей

Алгоритм адаптации по отношению сигнал/шум в поднесущей

(ABL) является алгоритмом максимизации скорости передачи при

фиксированной вероятности ошибки и общей мощности передатчи&

ка. Алгоритм состоит из:

1) оценки коэффициентов передачи поднесущих H

;

2) оценки дисперсии шума s

;

3) вычисления отношения сигнал/шум в поднесущей:

subc

SNR 1

10 log

;

4) выставления модуляционного созвездия в поднесущей по

SNR

subc

и порогу.

Данный алгоритм является очень привлекательным ввиду низ&

кой сложности аппаратной реализации и времени исполнения, кото&

рое особенно важно в условиях изменения канала. Производитель&

ность алгоритма битлоадинга сильно зависит от достоверности теку&

щей информации о канале, на основании которой работает алгоритм,

а следовательно, частоты обмена информацией о состоянии канала

между приемником и передатчиком (рис. 3). Как видно, при задерж&

0.1

0.01

0.001

10 14

PER

Рис. 2. Сравнение производительности LDPC и сверточного кода при

использовании KRJалгоритма битлоадинга:

– PEG (1728,1296) + KRJбитлоадинг; – сверточный код,

R = 0,75 + KRJбитлоадинг

802.11, 20 МГц – ширина полосы, сравнение LDPC со сверточным кодом,

КФМ, многопороговый декодер

SNR, дБ на передатчике

ке обмена более 5 мс и доплеровском рассеянии B

= 40 Гц (при ис&

пользовании сверточного кода) выигрыш от процедуры битлоадинга

практически нивелируется.

Другой проблемой использования алгоритмов битлоадинга явля&

ется их чувствительность к неточной оценке канала. При использо&

вании стандартного алгоритма оценки канала (рис. 4) ухудшение

составляет до 2–2,5 дБ по сравнению с идеальным оцениванием.

В данной работе была исследована возможность уменьшения этого

проигрыша за счет увеличения числа «длинных» тренировочных сим&

волов (LTS). Вставка двух дополнительных LTS&символов позволя&

ет добиться энергетического выигрыша в 1–1,5 дБ, что делает воз&

можным сократить потери до 1 дБ. Необходимо отметить, что при

имитационном моделировании учитывалось негативное влияние

вставки дополнительных тренировочных символов на информаци&

онную скорость передачи.

Как видно из результатов имитационного моделирования (рис. 5),

применение LDPC&кодов совместно с битлоадингом позволяет добить&

ся энергетического выигрыша до 2–2,5 дБ по сравнению со сверточ&

ными кодами.

Рис. 3. Производительность битлоадинга в зависимости от часто

ты обмена информацией о состоянии канала:

– статический 802.11a; – CC+ABL (идеальная, 320 мкс);

– CC + ABL (идеальная, 3 мс); – CC+ABL (идеальная, 5 мс)

SNR, дБ

Мбит/с

Пропускная способность, размер пакета = 1500

Рис. 4. Влияние оценки канала на производительность схемы

LDPC + ABL:

– статический 802.11a; – LDPC (2048, 1536)+ABL;

– LDPC (2048, 1536)+ABL+с дополнительной оценкой;

– LDPC+ABL (идеальная, с доплеровским смещением)

Мбит/с

Пропускная способность, размер пакета = 1500

Рис. 5. Сравнение схем передачи на базе LDPC + ABL и CC + ABL:

– LDPC (2048, 1536) + ABL; – CC (0.75) + ABL

Мбит/с

Пропускная способность, размер пакета = 1500

SNR, дБ

В целом применение LDPC&кодов совместно с битлоадингом по&

зволяет добиться энергетического выигрыша до 2,5–5,5 дБ по срав&

нению со стандартными методами кодирования и модуляции систем

IEEE 802.11a (рис. 6). С точки зрения информационной скорости

передачи, LDPC&коды сами по себе не дают столь большого выигры&

ша по сравнению со сверточными кодами, так как в отличии от LDPC

сверточные коды имеют эффективную схему управления скоростью

кода (выкалывание).

Литература

1. HughesHartogs D. Ensemble modem structure for imperfect

transmission media. US.Patents Nos. 4,679,227. July 1987.

2. Fischer R. H. J. A new loading algorithm for discrete multitone

transmission: Proceedings of GLOBECOM’96. Nov. 1996. P. 724–728.

3. Krongold B. J. D., Ramchandran K. Computationally efficient optimal

power allocation algorithms for multicarrier communication systems // IEEE

Transactions on Communications. 2000. Vol. 48(1). P. 23–27.

4. Gallager R. G. Low Density Parity Check Codes. Cambridge, MA: MIT

Press, 1963.

Рис. 6. Сравнение схем передачи на базе LDPC и стандартной IEEE

802.11a:

– статический 802,11a;

– статический 802.11a с LDPC(2048, 1536);

– LDPC(2048, 1536)+ABL+с дополнительной оценкой

10 15 25

Мбит/с

Пропускная способность, размер пакета = 1500

А. В. Белоголовый,

канд. техн. наук,

СанктПетербургский государственный университет

аэрокосмического приборостроения

CЖАТИЕ ИЗОБРАЖЕНИЙ

С ИСПОЛЬЗОВАНИЕМ LDPCКОДОВ

Введение

Многие схемы сжатия изображений используют разбиение целых

изображений на домены (некие области одинаковых размеров), а затем

каждый домен каким&то образом сжимается с потерями качества. Боль&

шинство методов далее используют какое&либо спектральное преобра&

зование, а затем – скалярное квантование полученных спектральных

коэффициентов. Термин «скалярное квантование» означает, что вход&

ными данными являются отдельные числа, и самым простым вариан&

том скалярного квантования является округление. Возможными вы&

ходными данными для процедуры скалярного квантования являются

так называемые «уровни квантования» или «уровни реконструкции».

Как правило, в алгоритмах сжатия изображений с потерями уровни

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

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

фактически обрабатывается независимо от остальных.

Однако обычные изображения содержат в себе большое количество

похожих областей, и, следовательно, после разбиения на домены обра&

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

очевидным, что использование этих свойств «похожести» доменов мо&

жет дать выигрыши, если при сжатии обрабатывать каждый домен как

единое целое, а не как множество независимых точек. Чтобы лучше

понять предпосылки возможных выигрышей, рассмотрим пример.

Возьмем стандартное тестовое изображение размером 512´512 то&

чек, каждая точка является одним из 256 оттенков серого. Разобьем

изображение на домены размером 8´8 точек. Домен при этом можно

представить вектором длины 64 или, что то же самое, точкой в 64&мер&

ном пространстве. Соответственно, всего в таком векторном простран&

стве будет 256^64 = 2^512 точек. Само же изображение будет разбито

всего на 4096 = 2^12 доменов, и, следовательно, далеко не все точки

пространства будут задействованы. Если бы набор доменов из 2^12 эле&

ментов для этого изображения был известен и кодеру, и декодеру, то

можно было бы передать каждый домен максимум 12 битами. Более

того, при сжатии с потерей качества все похожие домены внутри изоб&

ражения могут быть заменены на один, приближающий реальные до&

мены изображения с некоторой ошибкой, что позволит использовать

еще меньше бит. Например, если набор используемых образцов будет

содержать 256 доменов, то на передачу одного домена изображения по&

требуется максимум 1 байт, при этом сжатие составит минимум 16 раз.

Использование этих свойств похожести доменов при сжатии изоб&

ражений принципиально новым не является, а квантование, при

котором входными данными являются векторы, а не отдельные чис&

ла, принято называть векторным квантованием. Известен ряд ра&

бот, посвященных использованию векторного квантования при сжа&

тии изображений [1–10].

Векторное квантование при сжатии изображений

Общий метод состоит в том, что изображение разбивается на доме&

ны, а домены рассматриваются как векторы или некие точки в много&

мерном пространстве, затем при сжатии с потерей качества похожие

между собой домены заменяются на один образец. Все образцы помеща&

ются в кодовую книгу. Традиционно для этой цели используется обоб&

щенный алгоритм Ллойда [1, 9]. В результате для каждого вектора&

домена изображения находится кодовое слово, наилучшим образом при&

ближающее данный домен при накладываемых ограничениях, а также

для всего изображения получается кодовая книга, набор кодовых слов,

использующийся при квантовании данного изображения. Применитель&

но к сжатию изображений само по себе векторное квантование обеспе&

чивает сжатие в

log( )

раз, где N – длина вектора (число точек в доме&

не); L – число бит на символ одного элемента входного вектора; K –

число векторов в кодовой книге. Объем кодовой книги здесь не учиты&

вался.

После применения векторного квантования восстановленное изоб&

ражение будет отличаться от исходного. Причем уровень искажений

будет определяться не только степенью сжатия, но и самим набором

векторов в кодовой книге {W} = {w

, w

, ..., w

}. То есть, если для одного

изображения некая кодовая книга будет давать хорошие результаты по

качеству, для другого – та же самая кодовая книга будет вносить совсем

неприемлемые искажения. Именно поэтому в традиционных схемах

применения векторного квантования для сжатия изображений, чтобы

обеспечить приемлемое качество, кодовая книга каждый раз строится

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

книгу необходимо передавать для возможности восстановления изоб&

ражения. При этом кодовая книга сама по себе занимает много инфор&

мации и составляет существенную часть от общего количества байт,

которые необходимо хранить после сжатия. При использовании век&

торного квантования степень сжатия можно было бы повысить, если

отказаться от хранения кодовой книги, другим словами – использовать

одну и ту же книгу для всех изображений.

Кодовый подход к векторному квантованию

Будем говорить, что домен a размера nn1 покрывается в коде W с

радиусом R, если найдется w Î W, для которого сумма квадратов раз&

ностей элементов матрицы w – a не превышает R:

().

wa R12

Тог&

да любой код можно рассматривать как покрытие некоего множества

доменов радиусом R, а процесс векторного квантования можно рас&

сматривать как отображение множества доменов в кодовые слова

wÎW (рис. 1).

Для кодовой книги, построенной адаптивно при помощи обобщен&

ного алгоритма Ллойда, получается минимально возможный радиус

покрытия, так как код построен исключительно под домены изобра&

жения, а не является покрытием всего пространства. Но код при этом

не обладает никакими свойствами, следовательно, саму кодовую кни&

гу компактно не передать.

Рис. 1. Адаптивное покрытие выбранных точек пространства:

– кодовое слово; – домен; – все пространство

Если попытаться использовать для квантования специальный код,

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

но больше (рис. 2), но если при этом код будет являться какой&либо

структурой или будет обладать какими&либо свойствами, то сам код

можно будет компактно хранить, либо не хранить вообще, если он не

будет меняться для всех обрабатываемых изображений.

Пусть G – некоторый линейный (n, k)&код над полем GF(q), q = 256

для того же случая, когда каждая точка является одним из 256 от&

тенков серого GF(q). Пусть сторона домена изображения будет равна

, при этом n

= n.

Если точки покрываемого пространства являются доменами некоего

изображения, то сжатие будет состоять в том, что каждый домен из n

точек будет заменен на кодовое слово кода G, наиболее близкое к исход&

ному домену в евклидовой метрике. Так как кодовое слово однозначно

определяется своей информационной совокупностью (в нашем случае

информационная совокупность имеет длину k), то достаточно хранить

Рис. 2. Использование кода, покрывающего все пространство:

– кодовое слово; – домен изображения; – пространство