Теория информации и надежная связь - Галлагер Р.
Скачать (прямая ссылка):
(г) Для кода Рида-Соломона с длиной блока N и объемом входного алфавита q найти общее число кодовых слов, у которых число ненулевых элементов точно равно dmin.
6.32. Рассмотрим двоичный БЧХ-код с произвольным т, примитивным элементом a, г = 1 и d = 3. Показать, что он совпадает с кодом Хэмминга в циклическом виде, длина блока которого равна 2т — 1. Решить (6. 7. 27) для этого случая и показать, что решение эквивалентно методу декодирования при помощи таблицы декодирования, которая ранее была получена для кодов Хэмминга.
6.33. Воспользоваться итеративным алгоритмом и найти двоичный регистр сдвига минимальной длины, который генерирует многочлен [над GF(2)] 1 + + D3 + Di + D7-; найти двоичный регистр сдвига минимальной длины, генерирующий D2 + Di + De [над GF(2)].
6.34. Многочлен f(D) = D4 + D + 1 является примитивным над GF(2). Пусть а является многочленом t в поле многочленов по модулю/(D) (см. рис. 6.6.3). Рассмотреть БЧХ-код с q — 2, т = 4, с а, определенным выше, г = 1 и d = 5. Нарисовать блок-схему устройства для вычисления синдромного многочлена S(D), представляя все Si как элементы поля многочленов по модулю ((D).
6.35. Показать, что An(D) = [C„(D) S(D)]q—1 при всех п > 0 [см. (6.7.69)].
Указание: просмотрите доказательство утверждений (в) и (г) теоремы 6.7.3.
6.36. Показать, что из (6.7.21) следует (6.7.22). Заметим, что для этого достаточно доказать, что если производная многочлена над конечным полем определяется (6.7.21) и если f(D) = g(D)h(D), то f(D) = g'(D)h(D) + g(D)h'(D).
6.37. Начертить блок-схему исправляющего две ошибки порогового декодера для сверточного кодера, представленного ниже.
6.38. Начертить блок-схему порогового декодера, исправляющего две ошибки и обнаруживающего три ошибки, для систематического сверточного кодера со скоростью (в битах), равной У2, и с проверочными символами, порождаемыми по следующему правилу:
(2) Хп ¦
-ип +«n-e + un-!+«n-e + un-10-Указание: постройте множество из пяти линейных комбинаций шумовых
символов, ортогональных к г
(1)
1
и использовать значения этих линейных комби-
нации в качестве входных символов в пороговом устройстве.
6.39, Метод порогового декодирования можно использовать для блоковых кодов, так же как и для сверточных кодов. Рассмотреть код максимальной длины с L информационными символами и длиной блока N = 2L — 1.
(а) Показать, что декодер может вычислять (N — 1)/2 линейных комбинаций шумовых символов z0, ,
Указание: вспомните, кодом Хэмминга и что каждое кодовое слово в дуальном коде соответствует проверочному соотношению кода макси-
» 1 „ лою
Л Av. 0
zN—\’ ортогональных к zN_\-что, как показано в § 6.6., дуальный код является
L =
мальной длины. Вспомните также, что в коде Хэмминга каждая последовательность (в частности, имеющая вес 2) находится на расстоянии не больше 1 от некоторого кодового слова.
(б) Показать, что если пороговый декодер рассчитан на исправление тот же пороговый декодер может использоваться для исправления всех шумовых символов. Показать, что таким образом можно исправлять комбинации (N—3)/4 или менее ошибок,
(в) Нарисовать подробную детальную блок-схему такого декодера при
4.
6.40. Последовательный декодер выходит из узла а с нулевым порогом и движется к узлу 0, лежащему в дереве принятых цен ниже. Записать последовательность проверяемых узлов, просмотренных декодером до первой проверки узла дерева на глубине I = 3. Предполагается, что при движении вперед декодер всегда выбирает ребро, отмеченное символом 0.
6.41. (а) Пусть Г;—цена l-ro узла вдоль правильного пути в дереве принятых цен для последовательного декодера. Найти среднее значение по ансамблю кодов и шумов в канале цены Г;. Воспользоваться границей Чернова для оценки сверху Рг[Г;!< [Д] и показать, что Рг[Г; ^ iА] стремится к 0 экспоненциально с ростом I при любом смещении В < С.
(б) Пусть Гг цена l-то узла в дереве принятых цен, которая соответствует некоторой информационной последовательности, отличающейся от переданной в первом символе. Применить к Рг[Г( ^ iА] границу Чернова. Показать, что полученная граница отличается от границы для Рг[Г; < iА] множителем ехр [— vLB — iА]. Показать, что если R < В < С, то вероятность того, что какая-либо из цен Гi превысит М, убывает с ростом г'Д экспоненциально.
6.42. Границы вероятности ошибки и среднего числа вычислений в § 6.9 производят впечатление несколько искусственных, поскольку их вывод основы-
560
вался на использовании либо меняющегося во времени кода, либо кода с бесконечным кодовым ограничением. В этой задаче изменим эти нереальные предположения на новые. Точнее, будет использоваться ансамбль кодов, введенный перед леммой 6.9.1, с конечной длиной кодового ограничения, равной L подблокам. Изменим также алгоритм декодирования следующим образом. При любом 1(1 > L), как только декодер произведет первую F-проверку узла на глубине I в дереве принятых цен, он окончательно принимает гипотезу о символах источника в (I — L + 1)-м подблоке и полагает Tt_L = — оо. Другими словами, декодер не может менять гипотезы о символах, от которых узел максимального проникновения декодера в дерево удален более, чем на длину кодового ограничения. Будем говорить, что в п-м узле произошла ошибка, если декодер когда-либо совершит F-проверку на глубине п + L в узле какого-либо неправильного пути, впервые ответвляющегося от правильного в п-м узле.
