Квадратурная амплитудная модуляция

Оглавление

Описание алгоритма

Квадратурные модуляторы и демодуляторы.

Аналоговые квадратурные модулятор и демодулятор.

Цифровые модуляторы с интерполятором и ЦАП.

Цифровые демодуляторы с АЦП и дециматором.

Модемные протоколы, в которых используется КАМ.

Характеристики алгоритма.

Энергетический спектр сигнала.

Помехоустойчивость алгоритма КАМ.

Достоинства алгоритма.

Недостатки алгоритма.

Треллис-кодирование.

Треллис-кодирование.

Декодер Витерби

Список литературы.

Описание алгоритма [1]

При использовании данного алгоритма передаваемый сигнал кодируется одновременными изменениями амплитуды синфазной (I) и квадратурной (Q) компонент несущего гармонического колебания (f_c), которые сдвинуты по фазе друг относительно друга на π/2. Результирующий сигнал Z формируется в результате суммирования этих колебаний. Таким образом, QAM -модулированный дискретный сигнал может быть представлен соотношением:

, где

t - изменяется в диапазоне ;

m - порядковый номер дискрета времени;

 - шаг квантования входного сигнала по времени;

p - шаг квантования входного сигнала по амплитуде;

 и  ­– модуляционные коэфициенты ().

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

, или , где:

 – алгоритм изменения амплитуды модулированного сигнала;

 – алгоритм изменения фазы модулированного сигнала.

Таким образом, при использовании квадратурной амплитудной модуляции передаваемая информация кодируется одновременными изменениями амплитуды и фазы несущего колебания. На рисунке 1 представлен принцип формирования результирующего колебания Z путем суммирования вектора квадратурной составляющей Q с вектором синфазной составляющей I.

Рисунок 1

Амплитуда вектора Z определяется соотношением A_m, а угол, который этот вектор образует с осью абсцисс, определяется соотношением φ_m.

Для данного алгоритма существенно, что при модулировании синфазной и квадратурной составляющей несущего колебания используется одно и то же значение шага изменения амплитуды. Поэтому окончания векторов модулированного колебания образуют прямоугольную сетку на фазовой плоскости действительной - Re{Z} и мнимой - Im{Z} составляющих вектора модулированного сигнала. Число узлов этой сетки определяется типом используемого алгоритма QAM. Схему расположения узлов на фазовой плоскости модулированного QAM колебания принято называть созвездием (constellation).

Для указания типа алгоритма QAM принята следующая схема обозначения: QAM-<число >.

Используемое в обозначении алгоритма числовое значение обычно представляет собой число вида 2^N и соответствует количеству узлов на фазовой сетке, а также максимальному количеству различных значений вектора модулированного сигнала. Следует отметить, что в данном случае значение N соответствует показателю спектральной эффективности алгоритма.

На рисунке 2 приведена упрощенная структурная схема формирователя QAM-модулированного сигнала.

Рисунок 2

На первом этапе преобразования последовательность битов D {d₀, d₁,...,d_k} от источника сигнала преобразуется в последовательность двумерных модуляционных символов M {m₀ m₁, m_j}. Число битов в каждом определяется значением N (для алгоритма QAM-16 N=log₂16=4).

Формирователь кодовых символов преобразует двумерный кодовый символ m_j в пару кодовых символов α_j и β_j. Для алгоритма QAM-16 допустимые значения α_j и β_j принадлежат множеству {1,3,-1,-3} и определяют, соответственно, значения действительной и мнимой координаты вектора модулированного колебания. Сформированные значения А {α_j} и B {β_j} используются для амплитудной модуляции синфазной I и квадратурной Q составляющих несущего колебания. На последнем этапе преобразования выполняется суммирование этих колебаний и формирование результирующего сигнала Z.

На рисунке 3 представлено расположение векторов модулированного колебания - созвездие для алгоритма QAM-16.

Рисунок 3

Красным цветом отмечены значения модуляционных символов, которым соответствуют указанные точки фазовой плоскости модулированного колебания {m₃, m₂,m₁,m₀}. Для алгоритма QAM-16 пара {m₃,m₂} определяет номер квадранта фазовой плоскости или знаки действительной и мнимой координаты вектора модулированного колебания:

00 Sign(Re{Z})=1, Sign(Im{Z})=1

10 Sign(Re{Z})=1, Sign(Im{Z})=-1

01 Sign(Re{Z})=-1, Sign(Im{Z})=1

11 Sign(Re{Z})=-1, Sign(Im{Z})=-1

Для этого алгоритма пара {m₁,m₀} определяет значения амплитуды реальной и мнимой координаты вектора модулированного колебания соответственно. В таблице представлены значения кодовых символов α и β, которые соответствуют значениям младших разрядов модуляционного символа {m₁,m₀}.

m1	m0	αj	βj
0	0	1	1
0	1	1	3
1	0	3	1
1	1	3	3

Преобразование модуляционных символов в кодовые символы выполняется с применением алгоритмов Грея для помехоустойчивого кодирования данных. Так векторам модулированного колебания, которые находятся близко один от другого на фазовой плоскости, ставятся в соответствие значения кодовых символов, которые отличаются значениями только одного бита. В качестве примера могут быть рассмотрены два вектора Z=1+j и Z=1+3j, которым соответствуют кодовые символы {0,0} и {0,1}.

Квадратурные модуляторы и демодуляторы. [2] Аналоговые квадратурные модулятор и демодулятор.

Основной элемент модулятора и демодулятора – перемножитель (смеситель).

Рисунок 4

Рассматриваемый перемножитель (рис.4) представляет собой балансное устройство (double balanced Gilbert-cell mixer) на четырех транзисторах с дифференциальными входами (сигнальным и опорного колебания) и дифференциальным выходом. Для входного и выходного сигналов перемножитель представляет собой токовый элемент с низким входным (эмиттерным) и высоким выходным (коллекторным) сопротивлениями. Опорное колебание, с которым перемножается входной сигнал, подается в виде напряжения на базы транзисторов. Перемножитель используется вместе с преобразователем "напряжение–ток", включаемым на его эмиттерном входе.

Рисунок 5

В квадратурном модуляторе (рис.5) для суммирования выходных сигналов соответствующие коллекторные выводы двух перемножителей соединяются. При подаче на входы перемножителя сигнала, в общем случае выражаемого как , (1)

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

где  пропорционально . Нужное колебание выделяется путем фильтрации или без фильтрации – в квадратурных преобразователях. Первая составляющая, с суммарной частотой , выделяется в повышающих преобразователях частоты, а вторая, с разностной частотой , – в понижающих преобразователях (при ). При вторая составляющая в выражении (2) равна . В модуляторах реализуется режим с  (при ), а в демодуляторах используется составляющая разностной частоты, равной нулю (при ). Основные режимы квадратурных модулятора и демодулятора (см. рис.5) – модуляция/демодуляция сигнала с синфазной I(t_n) и квадратурной Q(t_n) модулирующими посылками и модуляция/демодуляция аналогового сигнала с одной боковой полосой (ОБП, SSB). В первом режиме модулирующие посылки – аналоговые, с постоянным уровнем в течение каждой посылки и дискретным изменением уровней от посылки к посылке. Уровни содержат информацию о цифровом коде модулирующего сигнала. На выходе модулятора

, (3)

где  и  – дискретно изменяемые амплитуда и фаза модулированного сигнала. Сигналы на выходе демодулятора

 (4)

(5)

пропорциональны входным сигналам модулятора I(t_n) и Q(t_n). Отметим, что НЧ-составляющие I(t_n), Q(t_n) на входе модулятора и I_дем(t_n), Q_дем(t_n) на выходе демодулятора представляют сигнал в прямоугольной системе, тогда как сигнал на выходе модулятора и входе демодулятора, согласно выражению (3), – в полярной системе координат. Во втором режиме на квадратурные входы модулятора подаются "комплексные" составляющие модулирующего НЧ-сигнала (со сдвигом 90°). С выхода модулятора, в зависимости от знака суммирования, снимается один из двух модулированных сигналов:

 (6)

или

, (7)

содержащих верхнюю или нижнюю боковые полосы (без инверсии и с инверсией спектра, соответственно). В выражениях (6) и (7)  и  – амплитуды и изменения фазы спектральных составляющих модулирующего сигнала. Пример аналоговых квадратурных модуляторов/демодуляторов – микросхемы серии AD834x фирмы Analog Devices (модуляторы AD8345/6/9 и демодуляторы AD8347/8). Модуляторы могут быть использованы также в качестве повышающих бесфильтровых преобразователей частоты. Другая серия аналоговых микросхем – AD607 и ее вариант AD61009. Это – микросхемы подсистем приемного тракта, содержащих понижающий преобразователь частоты и квадратурный демодулятор.

 
Цифровые модуляторы с интерполятором и ЦАП.

Рисунок 6

На рис.6 показана часть структурной схемы приемопередатчика с цифровыми модулятором и демодулятором. На входе канала модуляции используется цифровой двухканальный интерполирующий ФНЧ (интерполятор), повышающий частоту дискретизации в модуляторе, а на выходе канала, после цифрового квадратурного модулятора, - ЦАП. На вход канала поступают составляющие I(t_n) и Q(t_n) модулирующего цифрового сигнала в параллельном формате. На интерполятор от синтезатора частот поступают, как минимум, две последовательности тактовых импульсов, определяющих частоту отсчетов, - входных с частотой f_д1 и выходных с большей частотой f_д2 = f_д1K_инт, где K_инт - коэффициент интерполяции. Последовательность импульсов с частотой f_д2 подается также и на ЦАП. Цифровое опорное колебание, определяющее частоту несущей на выходе модулятора, может быть синусоидальным, формируемым, например, методом прямого цифрового синтеза (DDS), или прямоугольным, формируемым системой ФАПЧ. Отсчеты составляющих синусоидального опорного колебания ( и  на рис.6) характеризуются значениями описывающего их многоразрядного цифрового кода. Частота их следования равна f_д2 (на рис.6 не показана). В модуляторе цифровые коды входного сигнала и опорного колебания перемножаются, и, в зависимости от знака суммирования, выбирается сумма или разность их произведений. Прямоугольное опорное колебание (последовательность чередующихся "0" и "1"), которое можно рассматривать как одноразрядное, дополнительно содержит нечетные гармоники. В результате в выходном сигнале модулятора возникают дополнительные спектральные составляющие, которые могут либо фильтроваться на выходе ЦАП, либо одна из гармоник может быть использована для образования более высокочастотной несущей. Синусоидальное DDS-колебание применяется в микросхемах AD9853/6/7 и AD9873/7/9, а прямоугольное – в AD9773/5/7 и AD9782/4/6 (усовершенствованные варианты AD9773/5/7, содержащие цепи компенсации для уменьшения искажений преобразуемого сигнала). Следует отметить особенность микросхем AD9773/5/7 - наличие двух модуляторов и двух ЦАП. Это позволяет выполнять преобразование Гильберта (Hilbert transform), т.е. формировать "комплексный" модулированный сигнал, состоящий из двух составляющих с фазовым сдвигом 90. Комплексный сигнал (с выхода ЦАП) используется, например, при работе AD9773/5/7 или двух AD9782/4/6 с аналоговым модулятором AD8345 (или AD8346/9), выполняющим функцию квадратурного повышающего преобразователя частоты. Фирма Analog Devices выпускает также серию четырехканальных процессоров AD6622/3 (Transmit Signal Processor - TSP). Процессоры выполняют функции: преобразования и расщепления (на квадратурные составляющие) модулирующего цифрового сигнала - для получения различных видов модуляции (PSK, MSK, GMSK, QPSK и др.); интерполяции; квадратурной модуляции; суммирования четырех потоков информации в один широкополосный поток. Они не имеют своего ЦАП и могут входить в состав чипсета SoftCell вместе с ЦАП AD9754.

Цифровые демодуляторы с АЦП и дециматором.

Канал демодуляции содержит АЦП, встроенный цифровой демодулятор и децимирующий фильтр (см.рис.6). Пример – микросхемы AD9870/4, представляющие собой субсистемы приемника и содержащие аналоговый преобразователь частоты и канал демодуляции. АЦП является узкополосным, так как его задача – произвести цифровое преобразование ПЧ-сигнала, поступающего с выхода преобразователя частоты. Узкополосность обеспечивается полосовой фильтрацией, ограничивающей спектр преобразуемого сигнала. При этом частота дискретизации может быть меньше верхней частоты спектра, но должна быть больше отфильтрованной полосы частот. Обычно используется сигма-дельта АЦП, содержащий, в общем случае, сигма-дельта модулятор и преобразующий децимирующий фильтр. В простейшем случае сигма-дельта модулятор формирует одноразрядную частотно-модулированную последовательность посылок "0" и "1", синхронизированную тактовыми импульсами с частотой f_т. Частота модулятора, пропорциональная модулирующему сигналу, равна f_мод = f_тn₁/(n₀ + n₁), где n₀ и n₁ - число посылок со значениями "0" и "1", соответственно, на интервале дискретизации. Интервал определяется частотой дискретизации f_д в преобразующем фильтре и равен 1/f_д. Частоту f_т, которая значительно выше частоты дискретизации f_д, называют также частотой передискретизации, а частоту f_д - частотой децимации. Обычно f_т = 2^Nf_д, где 2^N - коэффициент передискретизации (он же – коэффициент децимации), а N – разрядность получаемого на выходе АЦП цифрового сигнала. Частоты f_т и f_д соответствуют f_д2 и f_д1 на рис.6 (в канале демодуляции). Преобразующий фильтр, входящий в состав сигма-дельта АЦП и называемый также децимирующим, выполняет преобразование частотно-модулированного сигнала сигма-дельта модулятора в многоразрядный цифровой сигнал, сопровождаемое цифровой фильтрацией и децимацией. Используется цифровой фильтр (обычно трансверсальный или эквивалентный ему рекурсивный), суммирующий посылки "1", существующие на интервале дискретизации. Результаты суммирования выражаются цифровым кодом на многоразрядном выходе фильтра. Рассмотренный сигма-дельта модулятор – одноразрядный, однако в AD9870/4 используется многоразрядный, работающий аналогично, но формирующий на выходе многоразрядную последовательность посылок. Его можно рассматривать как АЦП с передискретизацией. Допускается и применение других типов АЦП. Важно, чтобы дискретизация была с повышенной частотой (с f_д2, см. рис.6), при которой в канале демодуляции уровень шумов, обусловленных цифровым преобразованием, снижается. К микросхемам с цифровыми демодуляторами, встраиваемыми в АЦП с дециматором, относятся также процессоры серии AD66xx - AD6620/24/24A/34/35/52 (Receive Signal Processor - RSP). В микросхемах этой серии демодуляторы именуются частотными трансляторами. Микросхемы AD66xx, кроме AD6652, требуют применения внешнего АЦП - AD6600/40/42 или AD9042, AD922x, AD923x, AD924x, AD943x. Микросхемы AD6600/40/42 (из той же серии AD66xx) - АЦП другого, конвейерного, типа.

Модемные протоколы, в которых используется КАМ. [3]

V.22bis

Это дуплексный протокол с частотным разделением каналов и модуляцией QAM. Несущая частота нижнего канала (передает вызывающий) - 1200 Гц, верхнего - 2400 Гц. Модуляционная скорость - 600 бод. Имеет режимы четырехпозиционной (кодируется дибит) и шестнадцатипозиционной (кодируется квадробит) квадратурной амплитудной модуляции. Соответственно, информационная скорость может быть 1200 или 2400 бит/с.Режим 1200 бит/с полностью совместим с V.22, несмотря на другой тип модуляции. Дело в том, что первые два бита в режиме 16-QAM (квадробит) определяют изменение фазового квадранта относительно предыдущего сигнального элемента и потому за амплитуду не отвечают, а последние два бита определяют положение сигнального элемента внутри квадранта с вариацией амплитуды. Таким образом, DPSK можно рассматривать как частный случай QAM, где два последних бита не меняют своих значений. В результате из шестнадцати позиций выбираются четыре в разных квадрантах, но с одинаковым положением внутри квадранта, в том числе и с одинаковой амплитудой.

V.32

Это дуплексный протокол с эхо-подавлением и квадратурной амплитудной модуляцией или модуляцией с решетчатым кодированием. Частота несущего сигнала - 1800 Гц, модуляционная скорость - 2400 бод. Таким образом, используется спектр шириной от 600 до 3000 Гц. Имеет режимы двухпозиционной (бит), четырехпозиционной (дибит) и шестнадцатипозиционной (квадробит) QAM. Соответственно, информационная скорость может быть 2400, 4800 и 9600 бит/с. Кроме того, для скорости 9600 бит/с имеет место альтернативная модуляция - 32-позиционная TCM.

V.32bis

Это дуплексный протокол с эхо-подавлением и модуляцией TCM. Используются те же, что в V.32, частота несущего сигнала - 1800 Гц, и модуляционная скорость - 2400 бод. Имеет режимы 16-TCM, 32-TCM, 64-TCM и 128-TCM. Соответственно, информационная скорость может быть 7200, 9600, 12000 и 14400 бит/с. Режим 32-TCM полностью совместим с соответствующим режимом V.32.

V.34

Дуплексный протокол, максимальная скорость 28800 бит/с. Может также поддерживать 24000 и 19200 бит/с.

V.34bis

Другое название — V.34+. Максимальная скорость 33600 бит/с. Пониженные скорости: 31200, 24000 и 19200 бит/с.

В настоящее время КАМ наиболее широко используется в широкополосных модемах (ADSL, Ethernet). Используется непосредственно алгоритм КАМ (стандарт T1.413 ANSI), а также его разновидности: алгоритмы САР и G.dmt.

Рассмотрим характеристики алгоритма модуляции КАМ более подробно на примере стандарта T1.413 ANSI.

  Характеристики алгоритма. [1]

В настоящее время наибольшее распространение получили несколько вариантов QAM. Алгоритм модуляции QAM-4 кодирует сигнал изменением фазы несущего колебания с шагом π/2. Этот алгоритм модуляции имеет название QPSK (Quadrature Phase Shift Keying - квадратурная фазовая манипуляция). Широкое распространение получили также алгоритмы QAM-16, 32, 64, 128 и 256. Алгоритм квадратурной амплитудной модуляции, по сути, является разновидностью алгоритма гармонической амплитудной модуляции и поэтому обладает следующими важными свойствами:

·          ширина спектра QAM модулированного колебания не превышает ширину спектра модулирующего сигнала;

·          положение спектра QAM модулированного колебания в частотной области определяется номиналом частоты несущего колебания.

Эти полезные свойства алгоритма обеспечивают возможность построения на его основе высокоскоростных ADSL-систем передачи данных по двухпроводной линии с частотным разделением принимаемого (downstream) и передаваемого (upstream) информационных потоков.

Конкретная реализация алгоритма QAM определяет значения следующих параметров:

·          размерность модуляционного символа (log₂ количества точек созвездия) N [бит]

·          значение символьной скорости f_Symbol [кбод/сек]

·          центральная частота (central rate f_c)

Значение информационной скорости V (скорости передачи данных для алгоритма QAM) определяется следующим соотношением:

V = N * f_Symbol

Проект стандарта T1.413 ANSI предписывает использование следующих значений символьных скоростей в ADSL-системах передачи данных:

DOWNSTREAM fSymbol	UPSTREAM fSymbol
136 кбод 170 кбод 340 кбод 680 кбод 952 кбод 1088 кбод	85 кбод 136 кбод

Таким образом, при использовании символьной скорости 136 кбод, алгоритм QAM-256 позволяет обеспечить передачу данных со скоростью 1088 Кбит/сек.

Центральная частота f_c для конкретной реализации алгоритма модуляции определяется соотношением:

f_н + f _symbol /2 £ f_c £ f_в - f _symbol /2 ,где

f_н - нижняя граница спектра модулированного сигнала

f _symbol - значение символьной скорости

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

  Энергетический спектр сигнала.

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

На рисунке 7 представлено схематическое изображение маски для исходящего (UPSTREAM) потока ADSL.

Рисунок 7

Характерные для данной маски частотные диапазоны приведены в таблице:

№	fнач (KHz)	fкон (KHz)	PSD (dB/Hz)
1	0	4	-97.5
2	25.875	138	-34.5
3	3093	4545	-90

Диапазон 1 не используется для передачи данных в технологии ADSL. В диапазоне 2 должна быть размещена основная часть спектра полезного сигнала. Диапазон 3 не используется для передачи исходящего потока данных ADSL и предназначен для приема входящего потока.

Примерно такую же форму имеет маска для входящего (DOWNSTREAM) потока ADSL.

Рисунок 8

Характерные для маски входящего потока ADSL частотные диапазоны приведены в таблице:

	fнач (KHz)	fкон (KHz)	PSD (dB/Hz)
1	0	4	-97.5
2	4	138	-92.5-44.2
3	138	1104	-36.5

Диапазон 1 не используется для передачи данных в технологии ADSL. Диапазон 2 не используется для приема входящего потока данных ADSL и предназначен для передачи исходящего потока. В диапазоне 3 должна быть размещена основная часть спектра полезного сигнала.

Алгоритм модуляции QAM может быть использован для формирования линейного сигнала VDSL- устройств. На рисунке 9 представлено схематическое изображение спектра сигнала QAM-16, который обеспечивает передачу данных со скоростью 26 Мбит/сек - (6.5 Мбод).

Рисунок 9

Представленные на графике результаты были получены на двухпроводной линии длиной 1300 метров (4000 футов) при диметре провода 0.5 мм (26 AWG). На линии имелось одно пассив-ное ответвление (bridge-tap) длиной около 10 метров (30 футов). Наличие пассивных отводов на линии при использовании алгоритма модуляции QAM является одним из факторов, которые приводят к существенному уменьшению значения SNR для принимаемого сигнала. На приведенной выше диаграмме красным пунктиром отмечено искажение спектра модулированного колебания - провал на частоте f_с (5.4 МГц), которое вызвано именно наличием пассивного ответвления на линии.

Помехоустойчивость алгоритма КАМ.

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

 

Рисунок 10

 

Центр этого круга совпадает с узлом квадратурной сетки на фазовой плоскости. Заштрихованные области на рисунке соответствуют координатам искаженного вектора QAM-модулированного ко­лебания при воздействии на полезный сигнал помехи, относительный уровень которой опре­деляется соотношением 20dB £ SNR £30dB.

На диаграмме, которая приведена на рисунке 11, сплошными линиями представлены зависимости ожидаемого значения BER (Bit Error Rate - вероятность ошибок) от величины SNR для различных вариантов алгоритма QAM.

Использование дополнительного кодирования (пунктирные линии), например, по алгоритму Рида-Соломона (Reed-Solomon) позволяет повысить помехоустойчивость модулированного сигнала.

Достоинства алгоритма.

Алгоритм квадратурной амплитудной модуляции является относительно простым в реализации и в то же время достаточно эффективным алгоритмом линейного кодирования xDSL-сигналов. Современные реализации этого алгоритма обеспечивают достаточно высокие показатели спектральной эффективности. Как уже было отмечено выше, ограниченность спектра и относительно высокий уровень помехоустойчивости QAM-модулированного сигнала обеспечивают возможность построения на основе этой технологии высокоскоростных ADSL и VDSL-систем передачи данных по двухпроводной линии с частотным разделением принимаемого и передаваемого информационных потоков.

Недостатки алгоритма.

К недостаткам алгоритма можно отнести относительно невысокий уровень полезного сигнала в спектре модулированного колебания. Этот недостаток является общим для алгоритмов гармонической амплитудной модуляции и выражается в том, что максимальную амплитуду в спектре модулированного колебания имеет гармоника с частотой несущего колебания. Поэтому данный алгоритм в чистом виде достаточно редко используется на практике. Гораздо более широкое распространение получают алгоритмы, которые используют основные принципы QAM и в то же время свободны от его недостатков (например - алгоритм CAP).

Треллис-кодирование. [4] Треллис-кодирование.

Рассмотрим принципы треллис-кодирования на основе простейшего кодера, состоящего из двух запоминающих ячеек и элементов XOR (рис. 11).

Рисунок 11

Пусть на вход такого кодера поступает со скоростью k бит/с последовательность бит 0101110010. Если на выходе кодера установить считывающую ячейку, работающую с вдвое большей частотой, чем скорость поступления бит на вход кодера, то скорость выходного потока будет в два раза выше скорости входного потока. При этом считывающая ячейка за первую половину такта работы кодера считывает данные сначала с логического элемента XOR 2, а вторую половину такта — с логического элемента XOR 3. В результате каждому входному биту ставится в соответствие два выходных бита, то есть дибит, первый бит которого формируется элементом XOR 2, а второй — элементом XOR 3. По временной диаграмме состояния кодера нетрудно проследить, что при входной последовательности бит 0101110010 выходная последовательность будет 00 11 10 00 01 10 01 11 11 10.

Отметим одну важную особенность принципа формирования дибитов. Значение каждого формируемого дибита зависит не только от входящего информационного бита, но и от двух предыдущих бит, значения которых хранятся в двух запоминающих ячейках. Действительно, если принято, что A_i — входящий бит, то значение элемента XOR 2 определится выражением , а значение элемента XOR 3 — выражением . Таким образом, дибит формируется из пары битов, значение первого из которых равно , а второго – . Следовательно, значение дибита зависит от трех состояний: значения входного бита, значения первой запоминающей ячейки и значения второй запоминающей ячейки. Такие кодеры получили название сверточных кодеров на три состояния (K = 3) с выходной скоростью ½.

Работу кодера удобно рассматривать на основе не временных диаграмм, а так называемой диаграммы состояния. Состояние кодера будем указывать с помощью двух значений — значения первой и второй запоминающих ячеек. К примеру, если первая ячейка хранит значение 1 (Q1=1), а вторая — 0 (Q2=0), то состояние кодера описывается значением 10. Всего возможно четыре различных состояния кодера: 00, 01, 10 и 11.

Пусть в некоторый момент времени состояние кодера равно 00. Нас интересует, каким станет состояние кодера в следующий момент времени и какой дибит будет при этом сформирован. Возможны два исхода в зависимости от того, какой бит поступит на вход кодера. Если на вход кодера поступит 0, то следующее состояние кодера также будет 00, если же поступит 1, то следующее состояние (то есть после сдвига) будет 10. Значение формируемых при этом дибитов рассчитывается по формулам  и . Если на вход кодера поступает 0, то будет сформирован дибит 00 (), если же на вход поступает 1, то формируется дибит 11 (). Приведенные рассуждения удобно представить наглядно с помощью диаграммы состояний (рис. 12), где в кружках обозначаются состояния кодера, а входящий бит и формируемый дибит пишутся через косую черту. Например, если входящий бит 1, а формируемый дибит 11, то записываем: 1/11.

Рисунок 12

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

Используя диаграмму состояний кодера, несложно построить временную диаграмму переходов для уже рассмотренной нами входной последовательности бит 0101110010. Для этого строится таблица, в столбцах которой отмечаются возможные состояния кодера, а в строках — моменты времени. Возможные переходы между различными состояниями кодера отображаются стрелками (на основе полной диаграммы состояний кодера — рис. 13), над которыми обозначаются входной бит, соответствующий данному переходу, и соответствующий дибит. Например, для двух первых моментов времени диаграмма состояния кодера выглядит так, как показано на рис. 14. Красной стрелкой отображен переход, соответствующий рассматриваемой последовательности бит.

Рисунок 13 Рисунок 14

Продолжая отображать возможные и реальные переходы между различными состояниями кодера, соответствующие различным моментам времени (рис. 14, 15, 16), получим полную временную диаграмму состояний кодера (рис. 17).

Рисунок 15

Рисунок 16

Рисунок 17

Основным достоинством изложенного выше метода треллис-кодирования является его помехоустойчивость. Как будет показано в дальнейшем, благодаря избыточности кодирования (вспомним, что каждому информационному биту ставится в соответствие дибит, то есть избыточность кода равна 2) даже в случае возникновения ошибок приема (к примеру, вместо дибита 11 ошибочно принят дибит 10) исходная последовательность бит может быть безошибочно восстановлена.

Для восстановления исходной последовательности бит на стороне приемника используется декодер Витерби.

Декодер Витерби

Декодер Витерби в случае безошибочного приема всей последовательности дибитов 00 11 10 00 01 10 01 11 11 10 будет обладать информацией об этой последовательности, а также о строении кодера (то есть о его диаграмме состояний) и о его начальном состоянии (00). Исходя из этой информации он должен восстановить исходную последовательность бит. Рассмотрим, каким образом происходит восстановление исходной информации.

Зная начальное состояние кодера (00), а также возможные изменения этого состояния (00 и 10), построим временную диаграмму для первых двух моментов времени (рис. 17). На этой диаграмме из состояния 00 существует только два возможных пути, соответствующих различным входным дибитам. Поскольку входным дибитом декодера является 00, то, пользуясь диаграммой состояний кодера Треллиса, устанавливаем, что следующим состоянием кодера будет 00, что соответствует исходному биту 0.

Однако у нас нет 100% гарантии того, что принятый дибит 00 является правильным, поэтому не стоит пока отметать и второй возможный путь из состояния 00 в состояние 10, соответствующий дибиту 11 и исходному биту 1. Два пути, показанные на диаграмме, отличаются друг от друга так называемой метрикой ошибок, которая для каждого пути рассчитывается следующим образом. Для перехода, соответствующего принятому дибиту (то есть для перехода, который считается верным), метрика ошибок принимается равной нулю, а для остальных переходов она рассчитывается по количеству отличающихся битов в принятом дибите и дибите, отвечающем рассматриваемому переходу. Например, если принятый дибит 00, а дибит, отвечающий рассматриваемому переходу, равен 11, то метрика ошибок для этого перехода равна 2.

Для следующего момента времени, соответствующего принятому дибиту 11, возможными будут два начальных состояния кодера: 00 и 10, а конечных состояния будет четыре: 00, 01, 10 и 11 (рис. 18).

Рисунок 18

Соответственно для этих конечных состояний существует несколько возможных путей, отличающихся друг от друга метрикой ошибок. При расчете метрики ошибок необходимо учитывать метрику предыдущего состояния, то есть если для предыдущего момента времени метрика для состояния 10 была равной 2, то при переходе из этого состояния в состояние 01 метрика ошибок нового состояния (метрика всего пути) станет равной 2 + 1 = 3.

Для следующего момента времени, соответствующего принятому дибиту 10, отметим, что в состояния 00, 01 и 11 ведут по два пути (рис. 19).

Рисунок 19

В этом случае необходимо оставить только те переходы, которым отвечает меньшая метрика ошибок. Кроме того, поскольку переходы из состояния 11 в состояние 11 и в состояние 01 отбрасываются, переход из состояния 10 в состояние 11, отвечающий предыдущему моменту времени, не имеет продолжения, поэтому тоже может быть отброшен. Аналогично отбрасывается переход, отвечающий предыдущему моменту времени из состояния 00 в 00.

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

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

Аналогично и на последнем такте работы декодера имеется всего четыре возможных пути (рис. 20), причем истинный путь, однозначно восстанавливающий исходную последовательность битов 0101110010, соответствует метрике ошибок, равной 0.

Рисунок 20

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

Состояния кодера	T=0	t=1	t=2	t=3	t=4	t=5	t=6	t=7	t=8	t=9	t=10
00	-	0	2	3	2	3	3	3	0	2	3
01	-	-	3	0	3	2	2	0	3	3	0
10	-	2	0	3	0	3	3	3	2	0	3
11	-	-	3	2	3	0	0	2	3	3	2

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

В описанном выше случае мы предполагали, что все принятые декодером дибиты не содержат ошибок. Рассмотрим далее ситуацию, когда в принятой последовательности дибитов содержатся две ошибки. Пусть вместо правильной последовательности 00 11 10 00 01 10 01 11 11 10 декодер принимает последовательность 00 11 11 00 11 10 01 11 11 10, в которой третий и пятый дебит являются сбойными. Попробуем применить рассмотренный выше алгоритм Витерби, основанный на выборе пути с наименьшей метрикой ошибок, к данной последовательности и выясним, сможем ли мы восстановить в правильном виде исходную последовательность битов, то есть исправить сбойные ошибки.

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

Рисунок 21

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

Аналогичная ситуация возникнет и при получении пятого (также сбойного) дибита (рис. 22).

Рисунок 22

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

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

Состояния кодера	t=0	t=1	t=2	t=3	t=4	t=5	t=6	t=7	t=8	t=9	t=10
00	-	0	2	3	3	2	3	4	2	4	5
01	-	-	3	1	2	2	3	2	4	5	2
10	-	2	0	2	1	3	3	4	4	2	5
11	-	-	3	1	2	2	2	3	4	5	4

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

Список литературы.

1. Филимонов А.. Алгоритмы модуляции протоколов XDSL. http://www.protocols.ru/files/Technologies/xDSL.pdf

2. Голуб В. Квадратурные модуляторы и демодуляторы в системах радиосвязи. http://www.electronics.ru/pdf/3_2003/06.pdf

3. Пасковатый А. Модемные протоколы физического уровня. http://www.analytic.ru/ftproot/pub/byb_art/physics.zip

4. Пахомов С. Технология 1000Base-T на физическом уровне. http://www.compress.ru/article.aspx?id=9774&iid=412