Теория информации и надежная связь - Галлагер Р.
Скачать (прямая ссылка):
Указание: рассмотрите поле элементов по модулю р и определите элемент поля а как Rp(a); исследуйте мультипликативный порядок а.
6.16. Пусть D4 + D2 + D + 1 — многочлен над GF(2). Выразить его как произведение двух неприводимых нормированных сомножителей. Какими соображениями вы руководствовались при решении этой задачи?
6.17. Рассмотрим поле, элементы которого являются многочленами степени 1 или меньше с коэффициентами, принадлежащими GF(3); умножение элементов поля определяется как умножение многочленов по модулю ?>2 + 1.
(а) Доказать, что D2 + 1 — неприводимый многочлен над GF(3).
(б) Написать таблицы сложения и умножения для этого поля.
6.18. Рассмотрим код с троичными символами, в котором каждое кодовое слово х = (хи х2, х3, х4) порождается троичной информационной последовательностью и = («!, и2) согласно правилам
Xi=Uiр X$ = Ui(j)U2,
Xz — Uz, ДГ4 = Ц1ф2ц2,
где ® означает сложение по модулю 3.
(а) Найти порождающую и проверочную матрицы для этого кода.
(б) Составить таблицу декодирования (т. е. таблицу соответствия синдромов шумовым последовательностям) таким образом, чтобы минимизировать вероятность неправильного декодирования. При этом предполагается, что передача производится в троичном симметричном канале с P(j\k) — е < г/3 при / ф k и P(j\k) = 1—28 при / = k.
(в) Показать, как для любого числа т > 2 проверочных символов построить проверочную матрицу линейного кода с троичными символами, чтобы таблица декодирования содержала нулевую последовательность, все шумовые последовательности с одной ошибкой и не содержала бы ни одной последовательности более чем с одной ошибкой. Выразить длину блока для этих кодов как функцию т.
(г) Повторить пункт (в) для линейных кодов с символами из произвольного поля GF(a).
6.19. Пусть приведенная ниже матрица 5X8 является порождающей матрицей для двоичного кода с проверкой на четность, у которого число информационных символов равно 5, а число проверочных символов равно 3,
556
“10 0 0 0 111
0 10 0 0 10 0
0 0 1 0 0 0 1 0 .
0 0 0 10 0 0 1
_0 0 0 0 1 1 1 1 _
Показать, что этот код циклический и найти порождающий и проверочный многочлены.
6.20. Рассмотреть циклический код длины 7 с порождающим многочленом D3 + D + 1. Представить схемы двух кодирующих устройств, одно из которых включает трехразрядный регистр сдвига, а другое—четырехзарядный регистр сдвига. Показать, что этот код способен исправлять все единичные ошибки и потому эквивалентен коду Хэмминга длины 7, исправляющему единичные ошибки.
6.21. Пусть g(D) = gmDm + ... + g0—порождающий многочлен циклического кода. Показать, что g0 =j= 0.
6.22. Показать, что представленное на рисунке устройство является циклическим (N, ?)-кодером с проверочным многочленом h(D).
Ключ замыкается вертикально для L
информационных СИМВОЛОВ Д?дг_1,...,
xN—L’ затем замыкается горизонтально. Регистр первоначально пуст.
Указание: найдите, что будет храниться в крайнем правом разряде регистра после того, как L информационных символов сойдут с регистра и поступят в ли* нию.
Замечание: это устройство имеет два практических преимущества перед устройством на рис. 6.5.4: во-первых, сложение по модулю 2 может производиться непосредственно в разрядах регистра и, во-вторых, отпадает необходимость в последовательном сложении по модулю 2, что важно при передаче с высокой скоростью.
6.23. Предположим, что двоичный циклический (N, L)-код используется в канале с пакетами стираний, т. е. при передаче кодового слова xN_lt ..., xlt х0 принимается последовательность вида у = xJV_1, ..., xi, е, е, ..., е, Xj, ..., хг, х0. Иными словами, правильно принимаются все символы, кроме серии, состоящей из нескольких стертых символов.
(а) Показать, что если число стертых символов не превышает N ¦— L, то всегда можно выполнить правильное декодирование.
(б) Показать, что если стерто более чем N — L символов, то декодер максимального правдоподобия всегда будет производить решение в условиях неопределенности.
(в) Начертить блок-схему простейшего декодера, который может исправлять все конфигурации N — L или меньшего числа последовательных стираний (предполагается, что L > N12).
6.24. Расстоянием (Хэмминга) между двумя последовательностями N символов, принадлежащих GF(q), называется число позиций, в которых эти последовательности отличаются, а весом последовательности называется число ненулевых символов последовательности. Наименьшим расстоянием dmin линейного кода с символами из GF{q) называется минимум расстояний между всеми парами кодовых слов.
557
(а) Показать, что dmin равно наименьшему весу ненулевых кодовых слов. Показать, что можно исправить все конфигурации менее чем dmin/2 ошибок (см. задачу 6.4).
