Теория информации и надежная связь - Галлагер Р.
Скачать (прямая ссылка):
(а) Показать, что наименьшее расстояние построенного таким образом кода не меньше d.
554
(б) Показать, что общее число линейных комбинаций из d — 2 строк равно
d-2
i = О
используя это, показать, что N должно удовлетворять соотношению
d-2
!(“)> 2'=2'v-l'
i= о
где L — число информационных символов в коде.
Замечание. Из этого неравенства следует нижняя граница для наименьшего расстояния, которого можно достичь в кодах с проверкой на четность (и, следовательно, в произвольном двоичном коде). Заметим, что эта граница несколько сильнее, чем граница Гилберта в задаче 5.19, поскольку она увеличивает достижимое значение dmin на 1.
6.9. Рассмотрим два кода с проверкой на четность. Код 1 строится следующим образом:
Xl — Ul, *4=ul©u2>
*2= «2. *5 = «1®«3.
*3 = “3. *в = «2®«3.
= «1 ф И2 © и3 •
Код II строится совершенно аналогично, за исключением того, что хв = и2.
(а) Найти порождающую и проверочную матрицы для кода I.
(б) Найти таблицу декодирования для кода I для ДСК с переходной вероятностью е < V2.
(в) Найти точное выражение вероятности ошибочного декодирования для кодов I и II. Какая из этих вероятностей больше?
(г) Найти dmin для кодов I и II.
(д) Построить опровергающий пример для утверждения, что если наименьшее расстояние одного (N, ?)-кода с проверкой на четность больше, чем наименьшее расстояние другого (N, А)-кода с проверкой на четность, то первый код имеет в ДСК меньшую вероятность ошибки.
6.10. Рассмотрим код с проверкой на четность, у которого строки порождающей матрицы не являются линейно независимыми. Показать, что некоторая ненулевая информационная последовательность отображается в нулевое кодовое слово. Используя это, показать, что для каждой информационной последовательности существует по крайней мере одна другая информационная1 последовательность, которая отображается в то же самое кодовое слово. Ясно, что такие коды не интересны для практики.
6.11. Рассмотрим две проверочные матрицы Нх и #2, столбцы которых образуют одно и то же пространство (т. е. у которых одно и то же множество линейных комбинаций столбцов).
(а) Показать, что последовательность х удовлетворяет соотношению \Н2 = = 0 тогда и только тогда, когда хЯ2 =0 и, следовательно, и Н2 соответствуют одному и тому же множеству кодовых слов.
(б) Показать, что синдромы двух шумовых последовательностей, вычисленные по Н2, не совпадают (т. е. егН2 ф е2Н2) тогда и только тогда, когда не совпадают синдромы, вычисленные по Нг. Используя это, показать, что таблицы декодирования, построенные по Н2 и по Hlf исправляют одно и то же множество шумовых последовательностейJ
(в) Допустим, что число столбцов равно г и мощность наибольшего множества линейно независимых столбцов, равна г' < г. Показать, что число кодовых слов в коде равно 2N~r и что число строк в таблице' декодирования равно 2Г' •
555
6.12. Рассмотрим два кода с проверкой на четность с одной и той же длиной блока. Будем интерпретировать множество кодовых слов в каждом коде как группу сложения по модулю 2. Показать, что множество последовательностей, являющихся кодовыми словами в обоих кодах, образует подгруппу в каждой из рассмотренных выше групп. Интерпретируя последовательности в этой подгруппе как код с проверкой на четность, опишите процедуру нахождения проверочной матрицы нового кода через проверочные матрицы первоначальных кодов.
6.13. Показать, что число элементов любой конечной группы, в которой каждый элемент является обратным для самого себя, равно 2", где п — некоторое целое число, и что эта группа изоморфна группе, образуемой последовательностями из п двоичных символов с операцией сложения по модулю 2. (Две группы называются изоморфными, если существует взаимнооднозначное соответствие между их элементами, которое сохраняет групповую операцию.)
Указание: сначала покажите методом доказательства от противного, что эта группа абелева. Затем рассмотрите подгруппу из двух элементов. Далее покажите, что элементы любой подгруппы и единственный смежный класс этой подгруппы образуют новую подгруппу с удвоенным числом элементов.
6.14. Пусть 1, а, д2, ..., обозначают элементы циклической группы порядка 6. Найти порядок каждого элемента группы и выписать все подгруппы этой группы.
6.15. (а) Написать таблицы сложения и умножения для поля целых чисел
О, 1, 2, 3, 4, в котором сложение и умножение производится по модулю 5.
(б) Доказать теорему Ферма: для любого простого числа р и любого целого числа а, не делящегося на р, остаток от деления op—I на р по модулю р равен единице, т. е. Рр(ор_1) = 1.