Задачи. 8. Канальное кодирование: часть 3

Лекции по Теоретическим основам цифровой связи   

8. Канальное кодирование: часть 3

Задачи

8.1.        Определите, какой из следующих полиномов будет примитивным. Подсказка: самый простой способ состоит в применении LFSR; аналогично способу, показанному на рис. 8.8.

а)

б)

в)

г)

д)

е)

ж)

з)

и)

8.2. а) Какова способность к коррекции ошибок у кода (7, 3)? Сколько

битов в символе?

б) Определите количество строк и столбцов нормальной матрицы (см. раздел 6.6), необходимой для представления кода (7, 3), описанного в п. а.

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

г) Является ли код (7; 3) совершенным? Если нет; то какую остаточную способность к коррекции ошибок он имеет?

8.3. а) Определите множество элементов через образующие

элементы конечного поля GF(), при .

б) Для конечного поля, определенного в п. а, составьте, таблицу сложения, аналогичную табл. 8.2.

в) Постройте таблицу умножения, подобную табл. 8.3.

г) Найдите полиномиальный генератор для кода (31, 27).

д) Кодируйте сообщение {96 нулей, затем 110010001111} (крайний правый бит является первым) систематическим кодом (7, 3). Почему, по вашему мнению, сообщение построено с таким большим количеством нулей в начале?

8.4. С помощью полиномиального генератора для кода (7, 3), кодируйте

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

8.5. а) Применяйте регистр LFSR для кодирования сообщения {6, 5, 1}

(крайний правый бит является первым) с помощью кода (7, 3) в систематической форме. Представьте итоговое кодовое слово в двоичной форме.

б) Проверьте результат кодирования в п. а путем вычисления полинома кодового слова со значениями корней полиномиального генератора кода (7, 3).

8.6. а) Пусть кодовое слово, найденное в задаче 8.5, искажается в ходе

передачи, в результате чего крайние правые 6 бит были инвертированы. Найдите значения всех синдромов путем вычисления полинома поврежденного кодового слова со значениями корней полиномиального генератора, g(X).

б) Проверьте, что значения синдромов, вычисленные в п. а, можно найти путем вычисления полинома ошибок, e(Х), со значениями корней генератора g(X).

8.7. а) Воспользуйтесь авторегрессионной моделью из уравнения (8.40)

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

б) Найдите значение каждой символьной ошибки.

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

8.8. Последовательность 1011011000101100 подается на вход блочного

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

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

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

а) Как правило, пакет шума длится 250 мс. Системным кодом является БЧХ (127, 36) при . Прямая задержка не превышает 5 с.

б) Как правило, пакет шума длится 20 мс. Системным кодом является сверточный код (127, 36) с обратной связью при степени Кодирования 1/2, способный корректировать в среднем 3 символа в последовательности из 21 символа. Прямая задержка не превышает 160 мс.

8.10 а) Рассчитайте вероятность появления байтовой (символьной) ошибки

после декодирования данных, находящихся на\ компакт-диске! как было описано в разделе 8.3. Считается, что вероятность передачи канального символа с ошибкой для компакт-диска составляет . Предполагается также, что внешний и внутренний декодеры сконфигурированы для коррекции всех 2-символьных ошибок и процесс чередования исключает корреляции ошибок между собой.

б) Повторите расчеты п. а для компакт-диска, для которого вероятность ошибочной передачи канального символа равна .

8.11. Система, в которой реализована модуляция BPSK, принимает

равновероятные биполярные символы (+1 или -1) с шумом AWGN. Дисперсия шума считается равной единице. В момент k значение принятого сигнала равняется 0,11.

а) Вычислите два значения правдоподобия для этого принятого сигнала.

б) Каким будет максимальное апостериорное решение, +1 или -1?

в) Априорная вероятность того, что переданный символ равен +1, равна 0,3. Каким будет максимальное апостериорное решение, +1 или -1?

г) Считая априорные вероятности равными полученным в п. в, рассчитайте логарифмическое отношение правдоподобий .

8.12. Рассмотрим пример двухмерного кода с контролем четности, описанного

в разделе 8.4.3. Как указано, переданные символы представляются в виде последовательности , которая определяет степень кодирования кода равной 1/2. Конкретная схема, требующая более высоких скоростей, выдает кодовую последовательность этого кода с исключениями через один бит, что дает в итоге степень кодирования, равную 2/3.
Переданный выход теперь определяется последовательностью , где i и j являются индексами месторасположения. Помехи преобразуют эту последовательность данных и контрольных разрядов в принятую последовательность 0,05, 0,10, 0,15 1,25, 3,0, где k —временной индекс. Вычислите значения мягкого выхода для битов данных после двух горизонтальных и двух вертикальных итераций декодирования. Дисперсия считается равной единице.

8.13. Рассмотрим параллельное соединение двух составных RSC-кодеров, как

показано на рис. 8.26. Устройство чередования блоков размером 10 отображает последовательность входных битов в последовательность , где влияние устройства чередования задается равным [6, 3, 8, 9, 5, 7, 1, 4, 10, 2], т.е. первый бит входного блока данных отображается на позицию 6, второй бит — на позицию 3 и т.д. Входная последовательность равна (0, 1, 1, 0, 0, 1, 0, 1, 1,0). Предполагается, что составной кодер начинает из нулевого состояния и к нему принудительно прибавляется бит погашения, необходимый для перевода кодера обратно в нулевое состояние.

а) Рассчитайте 10-битовую контрольную последовательность .

б) Рассчитайте 10-битовую контрольную последовательность .

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

г) Если декодирование осуществляется на основе алгоритма MAP, какие изменения, по-вашему, нужно внести в метрики состояний и метрики ветвей, если кодер не погашен?

8.14. а) Для нерекурсивного кодера, изображенного на рис. 38.1, вычислите

минимальное расстояние по всему коду.

б) Для рекурсивного кодера, изображенного на рис. 8.26, вычислите минимальное расстояние по всему коду. Считайте, что исключений битов нет, а значит, степень кодирования кода равна 1/3.

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

г) Повторите п. в для последовательности с весом 2 (00...0010100...00).

Рис. 38.1. Схема кодера с нерекурсивными составными кодами

8.15. Рассмотрим кодер, представленный на рис.8.25, а. Пусть он используется

в качестве составного кода в турбокоде. Его решетчатая структура из 4 состояний изображена на рис.8.25, б. Степень кодирования кода равна 1/2. Ветвь, помеченная как и, v, представляет выходное ответвляющееся слово (кодовые биты) для той ветви, где и является битами данных (систематический код), a v — контрольными битами. Биты данных и контроля четности передаются за каждый такт k. Сигналы, принятые из демодулятора, имеют искаженные помехами значения и,v: 1,9; 0,7 — в момент k = 1 и -0,4; 0,8 — в момент k = 2. Предполагается, что априорные вероятности битов 1 и 0 равновероятны и что кодер начинает из нулевого состояния в начальный момент k = 1. Также считается, что дисперсия помех равна 1,3. Напомним, что последовательность N бит характеризуется N интервалами переходов и N + 1 состояниями (от начального до конечного). Следовательно, в данном случае биты стартуют в моменты k = 1, 2, и интерес представляют метрики в моменты k = 1,2,3.

а) Рассчитайте метрики ветвей для моментов k = 1 и k = 2, которые нужны для применения алгоритма MAP.

б) Вычислите прямые метрики состояний для моментов k = 1, 2 и 3.

в) Ниже для каждого правильного состояния в табл. 38.1 даются значения обратных метрик в моменты k = 2и k = 3. Основываясь на данных таблицы и значениях, полученных в пп. а и б, вычислите значение логарифмического отношения правдоподобий, соответствующего битам данных в моменты k = 1 и k = 2.С помощью правила принятия решений MAP найдите наиболее вероятную последовательность информационных битов, которая могла быть передана.

Таблица 38.4

4,6

2,1

2,4

11,5

5,7

3,4

4,3

0,9

8.16. Пусть принятая последовательность, полученная в задаче 8.15 для кода со

степенью кодирования 2/3, создается путем исключений из кода со степенью кодирования 1/2 (задаваемого решеткой на рис. 8.25, б). Исключение происходит таким образом, что передается только каждый второй контрольный бит. Таким образом, принятая последовательность из четырех сигналов представляет собой информационный бит, контрольный бит, информационный бит, информационный бит. Вычислите метрики ветвей и прямые метрики состояний для моментов времени k = 1 и k = 2, которые необходимы для алгоритма MAP.

8.17. Решетка для кода из четырех состояний используется как составной код в

турбокоде, как показано на рис. 8.25, б. Степень кодирования равна 1/2, а ветвь, обозначенная как и, v, представляет собой выход, ответвляющееся слово (кодированные биты) для этой ветви, где и — это информационные биты, a v — биты четности. Из демодулятора принимается блок из N = 1024 фрагментов. Пусть первый сигнал из демодулятора поступает в момент k = 1 и в каждый последующий момент k поступают зашумленные биты данных и контроля четности. В момент времени = 1023 принятые сигналы имеют зашумленные значения и, v, равные 1,3; -0,8, а в момент k = 1024 значения равны -1,4; -0,9. Предполагается, что априорные вероятности того, что биты данных равны 1 или 0, равны и что конечное состояние кодера будет а = 00 в завершающий момент k = 1025. Также считается, что дисперсия помех равна 2,5.

а) Рассчитайте метрики ветвей для моментов k = 1023 и k = 1024.

б) Рассчитайте обратные метрики состояний для моментов k = 1023, 1024 и 1025.

в) Ниже в табл. 38.2 даются значения прямых метрик состояний в моменты k = 1023 и k 1024 для каждого правильного состояния. Основываясь на таблице и информации из пп. а и б, вычислите значения отношений правдоподобий, связанных с информационными битами в моменты времени k = 1023 и k = 1024. Используя правило принятия решений алгоритма MAP, найдите наиболее вероятную последовательность битов данных, которая могла быть передана.

Таблица 38.2

6,6

12,1

7,0

1,5

4,2

13,4

4,0

5,9

8.18.      Имеется два статистически независимых наблюдения зашумленного

сигнала, и . Проверьте, что логарифмическое отношение правдоподобий (log-likelihood ratio — LLR) можно выразить через индивидуальные LLR как

,

где L(d) является априорным LLR основного бита данных d.

8.19. а) Используя теорему Байеса, подробно распишите этапы

преобразования , приведенной в уравнениях (8.129) и (8.130,6). Подсказка: воспользуйтесь упрощенной системой обозначений, применяемой в уравнениях (8.121) и (8.122).

б) Объясните, каким образом суммирование по состояниям в уравнении (8.130,а) дает в итоге уравнение (8.130,б).

в) Повторите п. а и покажите, как уравнение (8.133) переходит в уравнение (8.135).Также объясните, как суммирование по состояниям в будущий момент дает уравнение (8.135).

8.20.Исходя из уравнения (8.139) для метрики ветви , покажите, каким образом получается уравнение (8.140), и укажите, какие члены следует считать постоянными в уравнении (8.140). Почему члены не появляются в уравнении (8.140,а)?

8.21. Устройство чередования на рис. 8.27 (аналогичное устройству в

соответствующем кодере) гарантирует, что выходная последовательность декодера DEC1 упорядочена во времени так же, как и последовательность . Можно ли реализовать это более простым способом? Что можно сказать о применении устройства восстановления в нижнем ряду? Не будет ли это более простым способом? Если это осуществить, тогда можно будет убрать два прежних устройства восстановлений. Объясните, почему это не сработает.

8.22. При декодировании согласно алгоритму Витерби, используется

устройство сложения, сравнения и выбора (add-compare-select — ACS). А при реализации алгоритма максимума апостериорной (maximum a posteriori — MAP) вероятности в турбодекодировании не применяется идея сравнения и выбора переходов. Вместо этого в алгоритме MAP рассматриваются все метрики ветвей и состояний для данного интервала времени. Объясните это принципиальное различие между двумя алгоритмами.

8.23.      На рис. 38.2 показан рекурсивный систематический сверточный (recursive

systematic convolutional — RSC) кодер со степенью кодирования 1/2, К = 4. Заметьте, что на рисункеиспользуется формат памяти в виде 1-битовых блоков задержек (см. раздел 8.4.7.4). Следовательно, текущее состояние цепи можно описать с помощью уровней сигналов в точках , ,, аналогично способу описания состояния в формате разрядов памяти. Составьте таблицу, аналогичную табл. 8.5, которая будет определять все возможные переходы в цепи, и с ее помощью изобразите участок решетки.

Рис. 38.2. Рекурсивный систематический сверточный (RSC) кодер со степенью кодирования 1/2, К = 4

8.24.      На рис. 38.3 показан рекурсивный систематический сверточный (recursive

systematic convolutional — RSC) кодер со степенью кодирования 2/3, К=3. Заметьте, что на рисунке используется формат памяти в виде 1-битовых блоков задержек (см. раздел 8.4.7.4). Составьте таблицу, аналогичную табл. 8.5, которая будет определять все возможные переходы в цепи, и с ее помощью изобразите участок решетки. С помощью таблицы, подобной табл. 8.6, найдите выходное кодовое слово для информационной последовательности 1 1 0 0 1 1 0 0 1 1.В течение каждого такта данные поступают в цепь в виде пары , а каждое выходное ответвляющееся слово образуется из пары битов данных и одного контрольного бита, .

Рис. 38.3, Рекурсивный систематический сверточный (RSC) кодер со степенью кодирования 2/3, К = 3

8.25. Рассмотрим турбокод, состоящий из двух сверточных кодов, которые, в

свою очередь, состоят из четырех состояний. Оба составных кода описываются решеткой, которая изображена на рис. 8.25, б. Степень кодирования кода равна 1/2, а длина блока — 12. Второй кодер оставлен не погашенным. Метрики ветвей, прямые метрики состояний и обратные метрики состояний для информационных битов, связанных с кодером в конечном состоянии, описываются матрицей, изображенной ниже. Принятый 12-сигнальный вектор образован из сигнала данных, сигнала контроля четности, сигнала данных, сигнала контроля четности и т.д. и имеет следующие значения.

1,2 1,3 -1,2 0,6 -0,4 1,9-0,7 -1,9 -2,2 0,2 -0,1 0,6 Матрица ветвей

Альфа-матрица

Бета-матрица

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

Вопросы для самопроверки

8.1.          Объясните высокую эффективность кодов Рида-Соломона при наличии импульсных помех (см. раздел 8.1.2.).

8.2.          Объясните, почему кривые на рис. 8.6 показывают снижение достоверности передачи при низких значениях степеней кодирования (см раздел 8.1.З.).

8.3.          Среди всех способов определения примитивности полинома наиболее простой — использование линейного регистра сдвига с обратной связью (linear feedback shift register —LFSR). Объясните эту процедуру (см. пример 8.2.).

8.4.          Объясните, каким образом можно получить синдром, вычисляя принятый полином со всеми значениями корней полиномиального генератора кода (см. раздел 8.1.6.1).

8.5.          Какое ключевое преобразование осуществляет система чередования/восстановления над мпульсными помехами (см. раздел 8.2.1.)?

8.6.          Почему предел Шеннона, равный -1,6 дБ, не представляет интереса при разработке реальных систем (см. раздел 8.4.5.2.)?

8.7.          Почему алгоритм декодирования Витерби не дает апостериорных вероятностей (см. раздел 8.4.6.)?

8.8.          Каково более описательное название алгоритма Витерби (см. раздел 8.4.6.)?

8.9.          Опишите сходство и отличие в реализации декодирования на основе алгоритмов Витерби и максимума апостериорной вероятности (MAP) (см. раздел 8.4.6.).









© Банк лекций Siblec.ru
Формальные, технические, естественные, общественные, гуманитарные, и другие науки.
E-mail: formyneeds@yandex.ru