Научная литература
booksshare.net -> Добавить материал -> Физика -> Галлагер Р. -> "Теория информации и надежная связь" -> 266

Теория информации и надежная связь - Галлагер Р.

Галлагер Р. Теория информации и надежная связь — М.: Советское радио, 1974. — 738 c.
Скачать (прямая ссылка): teoriyainformacii1974.pdf
Предыдущая << 1 .. 260 261 262 263 264 265 < 266 > 267 268 269 270 271 272 .. 355 >> Следующая


(а) Показать, что наименьшее расстояние построенного таким образом кода не меньше 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.
Предыдущая << 1 .. 260 261 262 263 264 265 < 266 > 267 268 269 270 271 272 .. 355 >> Следующая

Реклама

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed

Есть, чем поделиться? Отправьте
материал
нам
Авторские права © 2009 BooksShare.
Все права защищены.
Rambler's Top100

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed