8.6. Модифицированный граф состояний

Модифицированный граф состояний на основе T(D) производящей функции кода может быть получен по следующей формуле:

T(D)= (3.1)

Где – независимые пути,

– контура,

}{ – означает, что пересекающиеся пути и контура следует обнулить.

Рис. 3.1. Диаграмма состояний с обозначенными расстояниями до нулевого пути

На рисунке 3.1 из состояния “a” в состояние “e” возможны следующие пути:

= a b c e =

= a b d c e =

= b c b =

= b d c b =

= d d =

Решение модернизированного графа состояний:

T(D)= = =

Пересекающиеся пути и контура равны 0, следовательно:

==

8.7. Решение задач

8.7.1. Задачи

1.Для передачи речи в сетях мобильной связи GSM используется оптимальный сверточный код с порождающими многочленами g₁(x) =1+х³+х⁴ и g₂(x) =1+х+х³+х⁴, имеющий свободное расстояние, равное d_free= 7 [2]. Построить схему кодера и определить число его состояний. Сколько метрик должен вычислять декодер на каждом шаге декодирования? Сколько выживших путей выбирается для продолжения декодирования?

2, Для передачи данных в сети GSM используется сверточный код с порождающими многочленами g₁(x) =1+х³+х⁴, g₂(x) =1+х+х³+х⁴, g₁(x) =1+х²+х⁴ и g₃(x) =1+ х+х²+х³+х⁴, имеющий свободное расстояние, равное d_free= 12 [7]. Построить схему кодера и определить число его состояний. Сколько метрик должен вычислять декодер на каждом шаге декодирования? Сколько выживших путей выбирается для продолжения декодирования?

8.7.2. Решение

Решение задачи 1. Сверточный: код, используемый для коди­рования речи в сетях мобильной связи GSM.

Схема кодера

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

3. Память кодера т = 4.

Кодовое ограничение п_с = 10.

Блоковая скорость 185/(2[185 + 4]) = 0,489 Относительная потеря скорости 4/(185 + 4) = 2,11 • 10^-2 Полная память кодера М = 4.

Существует 2^м = 16 состояний. На каждом шаге декодер вы­числяет 32 приращения метрик, исходя из которых вычисляют­ся тридцать две частичных метрики и сравниваются попарно; 16 выживших путей выбираются для продолжения и их частич­ные метрики запоминаются.

Решение задачи 2. Сверточный код для передачи данных в мобильных сетях связи GSM.

Схема кодера

2. Из равенства 3- (60+ж) = 228 следует, что х = 16, т.е. к инфор­мационной последовательности добавляются 16 нулей и коди­рование заканчивается нулевым состоянием.

3. Память кодера т = 4. Кодовое ограничение п_с = 3(4+1) = 15. Блоковая скорость 60/(3 • [60 + 4]) = 0,3125

учитывая 16 нулевых бит получаем 60/228 = 0,263 Относительная потеря скорости 4/64 = 6,25 • 10^-2

учитывая 16 нулевых бит получаем 16/76 = 0,211 Полная память кодера М = 4.

4. Существует I^м = 16 состояний. В каждом такте декодер вы- числяет 32 приращения метрик, исходя из которых вычисляются и попарно сравниваются 32 частичные метрики; 16 полученных путей выбираются для продолжения и их частичные метрики запоминаются.

8.3.2.1. Процедура сложения, сравнения и выбора

Вернемся к примеру двух ячеек с К = 3. На рис. 8.12 показан логический блок, со­ответствующий ячейке 1. Логическая схема осуществляет специальную операцию, ко­торая называется сложение, сравнение и выбор (add-compare-select — ACS). Метрика состояния Г_a’ вычисляется путем прибавления метрики предыдущего состояния а, Г_a, к метрике ветви δ_aa’ и метрики предыдущего состояния с, Г_с, к метрике ветви δ_ca’. Это даст в результате две метрики путей в качестве кандидатов для новой метрики состоя­ния Г_a’. Оба кандидата сравниваются в логическом блоке, показанном на рис. 8.12. Наиболее правдоподобная из двух метрик путей (с наименьшим расстоянием) запо­минается как новая метрика состояния Г_a’ для состояния а'. Также сохраняется новая история путей m_a’. для состояния а, где m_a’ — история пути информации для данного состояния, дополненная сведениями о выжившем пути.

На рис. 8.12 также показана логическая схема ACS для ячейки 1, которая дает но­вую метрику состояния Г_b’ и новую историю состояния m_b. Операция ACS аналогич­ным образом осуществляется и для путей в других ячейках. Выход декодера составля­ют последние биты на путях с наименьшими метриками состояний.