Задачи

8.14. Может ли слово вида U = (0111100) принадлежать двоичному (7,3) циклическому коду? Каков будет ответ в случае кода (7,4)?

8.15. Может ли циклический (7,3) код содержать слова вида U1 = (0101110) и U2 = (1010110) ? Может ли содержать указанные слова циклический (7,4) код?

8.16. Для (7,3) двоичного циклического кода с порождающим многочленом вида

g(z) = (z +1)(z3 + z +1) построить систематическое кодовое слово, соответствующее информационному блоку (101) .

8.17. Для (7,4) двоичного циклического кода с порождающим многочленом вида g(z) = z3 + z2 +1 построить систематическое кодовое слово, соответствующее информационному блоку (1011) .

8.18. Для (7,4) двоичного циклического кода с проверочным многочленом вида

h(z) = (z +1)(z3 + z2 +1) построить систематическое кодовое слово, соответствующее информационному блоку (0110) .

8.19. Для (7,3) двоичного циклического кода с проверочным многочленом вида h(z) = z3 + z + 1 построить систематическое кодовое слово, соответствующее информационному блоку (111) .

8.20. Построить каноническую порождающую матрицу циклического (7,3) кода, задаваемого порождающим полиномом g(z) = (z +1)(z3 + z +1) .

8.21. Построить каноническую порождающую матрицу циклического (7,4) кода, задаваемого порождающим полиномом g(z) = z3 + z 2 + 1.

8.22. Построить каноническую порождающую матрицу циклического (7,3) кода, задаваемого проверочным полиномом h(z) = z3 + z2 + 1.

8.23. Построить каноническую порождающую матрицу циклического (7,4) кода, задаваемого проверочным полиномом h(z) = (z +1)(z3 + z +1) .

8.24. Изобразить кодер на основе сдвигающего регистра для (7,4) циклического ко-

да, порождаемого полиномом g(z) = z3 + z2 +1 и привести последовательность изменения состояния регистра и его выхода при подаче на вход информационного блока (1111) .

8.25. Изобразить кодер на основе сдвигающего регистра для (7,3) циклического кода, порождаемого полиномом g(z) = (z + 1)(z 3 + z 2 + 1) и привести последовательность изменения состояния регистра и его выхода при подаче на вход информационного блока

(111) .

8.26. Изобразить кодер на основе сдвигающего регистра для (7,3) циклического кода, задаваемого полиномом h(z) = z3 + z +1 и привести последовательность изменения со-

21

стояния регистра и его выхода при подаче на вход информационного блока (111) .

	8.27. Изобразить вычислитель синдрома на основе линейного регистра сдвига цик-
лического (7,4) кода с порождающим полиномом			g(z) = z3 + z2 +1. Привести состояния
регистра сдвига, найти значение синдрома и осуществить исправление ошибок для на-
блюдаемой комбинации Y = (1010101) .
	8.28. Изобразить вычислитель синдрома на основе линейного регистра сдвига цик-
лического (7,3) кода с порождающим полиномом			g(z) = (z +1) (z3 + z2 +1) . Привести со-
стояния регистра сдвига, найти значение синдрома и осуществить исправление ошибок
для наблюдаемой комбинации Y = (1010010) .
	8.29. Изобразить вычислитель синдрома на основе линейного регистра сдвига цик-
лического (7,4) кода с проверочным полиномом			h(z) = (z +1) (z3 + z +1) . Привести со-
стояния регистра сдвига, найти значение синдрома и осуществить исправление ошибок
для наблюдаемой комбинации Y = (1010101) .
	8.30. Для двоичного циклического кода может ли матрица размерности 2× 5 вы-
ступать в качестве порождающей или проверочной? Что можно сказать о матрице размер-
ности 3× 5 ?
	8.31. Найти все возможные значения числа информационных символов двоичного
циклического кода длины 6.
7.	8.32. Найти все возможные значения скорости двоичного циклического кода длины
8.	8.33. Найти все возможные значения скорости двоичного циклического кода длины
	8.34. Порождающая матрица (7,4) двоичного циклического кода имеет вид
		1 0 1 0 0 1 1
	G = 1 1 0 1 0 0 1 .
	1 1 1 1 1 1 1
	0 0 1 1 1 0 1
Построить порождающий и проверочный полиномы кода.
	8.35. Проверочная матрица (7,3) двоичного циклического кода имеет вид
		1 0 1 1 0 0 0
	H = 0 1 0 1 1 0 0
	0 0 1 0 1 1 0
	0 0 0 1 0 1 1
Построить порождающий и проверочный полиномы кода.
	8.36. Двоичный (7,4) циклический код описывается порождающим полиномом
g(z) = z3 + z +1. Наблюдается вектор Y = (0010010) . Вычислить полином синдрома и де-

кодировать наблюдаемый вектор.

8.37. Двоичный (7,4) циклический код описывается проверочным полиномом

22

h(z) = z4 + z2 + z +1. Наблюдается вектор Y = (0010010) . Вычислить полином синдрома и декодировать наблюдаемый вектор.

9. БЧХ–коды и коды Рида–Соломона.

9.1. Какие из полиномов f (x) = x3 + x2 + x +1, f (x) = x2 + x +1, f (x) = x3 + x2 + x,

f (x) = x3 + x2 +1, f (x) = x3 + x +1 могут быть использованы для построения расширенного поля GF(8) как множества полиномов с операциями по модулю f (x) ?

9.2.На примере поля GF(4) показать, что приводимые полиномы не пригодны для построения расширенного поля.

9.3.Найти подходящий полином f (x) и построить расширенное поле GF(9) со сложением и умножением по модулю f (x) .

9.4. Полином f (x) = x4	+ x3 + x2	+ x + 1 неприводим над полем GF(2) . Вычислить
произведения полиномов вида	x(x3 + x2	+ x + 1) , x2 (x2 + x + 1) и (x2 + 1)(x2 + x + 1) в по-
ле GF(16) по модулю полинома f (x) .

9.5. Перечислить все возможные значения мультипликативного порядка элементов поля GF(11) и привести примеры элементов, обладающих указанными порядками. Указать несколько вариантов примитивного элемента поля GF(11) .

9.6. Перечислить все возможные значения мультипликативного порядка элементов поля GF(13) и привести примеры элементов, обладающих указанными порядками. Указать несколько вариантов примитивного элемента поля GF(13) .

9.7. Пусть порядок поля GF(q) нечетен, а ς – примитивный элемент поля GF(q) .

Является ли элемент ς 2 примитивным? Если нет, каков его мультипликативный порядок? Какой должна быть степень примитивного элемента, чтобы вновь полученный элемент был бы примитивным?

9.8. Существуют ли конечные поля, в которых все ненулевые элементы (кроме единицы) являются примитивными? Если существует, привести несколько примеров подобных полей. Возможно ли построение подобного поля с характеристикой большей, чем 2?

9.9. Является ли полином f (x) = x3 + x2 +1 над полем GF(2) примитивным? Если да, то построить соответствующее расширенное поле в виде последовательных степеней примитивного элемента.

9.10.Рассмотреть все неприводимые над полем GF(2) полиномы 5–й степени. Сколько из них являются не примитивными?

9.11.Раскрыть скобки в соотношении (α + β )2l +1 , α , β GF(2m )

23

9.12. Раскрыть скобки в соотношении (α + β )16 , α , β GF(64) , если мультиплика-
тивный порядок элементов α иβ составляет 3 и 7 соответственно.
9.13. Найти все 2-сопряженные с элементами α , β , и γ поля GF(16) ,		если их
мультипликативный порядок равен 15, 5 и 3 соответственно. Указать длины циклов всех
2-сопряженных элементов.
9.14. Найти все 2-сопряженные с элементами α , β , и γ поля GF(64) ,		если их
мультипликативный порядок равен 9, 7 и 3 соответственно. Указать длины циклов всех 2-
сопряженных элементов.
9.15. Вычислить степень минимальных полиномов элементов α , β , и		γ	поля
GF(16) , если их мультипликативный порядок равен 15, 5 и 3 соответственно.
9.16. Вычислить степень минимальных полиномов элементов α ,	β , и	γ	поля
GF(64) , если их мультипликативный порядок равен 9, 7 и 3 соответственно.

9.17. Определить исправляющую способность и число информационных символов двоичного циклического кода длины 15, если среди корней его порождающего полинома

имеются ς и ς 9 , где ς – примитивный элемент поля GF(16) .

9.18. Определить исправляющую способность и число информационных символов двоичного циклического кода длины 15, если среди корней его порождающего полинома

имеются ς , ς 9 и ς 10 , где ς – примитивный элемент поля GF(16) .

9.19. Сколько информационных символов содержит слово двоичного БЧХ–кода длины 63, исправляющего все 5-ти кратные ошибки?

9.20. Может ли существовать (15,9) БЧХ–код?

9.21. Какие из пар чисел (n, k) отвечают стандартному коду Рида–Соломона: (31,15), (31,21), (63,13), (127,57) и (255,179). Какова исправляющая способность кода для разрешенных пар?

9.22. Существует ли стандартный код Рида–Соломона, исправляющий ошибки кратности 7 и содержащий k =17 информационных символов? Каков будет ответ при k =16 ?

9.23. На основании примитивного полинома		f (x) = x3 + x +1 определить мини-
мальный многочлен элемента	ς 3 в поле GF(8) , где	ς	– примитивный элемент поля
GF(8) .
9.24. На основании примитивного полинома		f (x) = x4 + x +1 определить мини-
мальный многочлен элемента	ς 5 в поле GF(16) , где ς		– примитивный элемент поля
GF(16) .

9.25. Доказать, любой минимальный полином всегда неприводим. 24

9.26. Порождающий полином двоичного БЧХ–кода представляет собой произведение двух минимальных многочленов: g1(z) = z5 + z2 +1 (минимальный многочлен

примитивного элемента ς ) и g3 (z) = z5 + z4 + z3 + z2 +1 (минимальный многочлен

элемента ς 3 ). Определить длину, число информационных символов и конструктивное расстояние кода.

9.27. Перечислить возможные значения скорости и конструктивного расстояния всех примитивных двоичных БЧХ–кодов длины 31.

9.28. Может ли примитивный двоичный БЧХ–код длины 15 или более иметь конструктивное расстояние s +1 = 6 ?

9.29. Каждый символ (7,3) кода Рида–Соломона представляет собой слово двоичного симплексного (7,3) кода. Определить число двоичных информационных бит и исправляющую способность результирующего каскадного двоичного кода.

9.30. Разработчику телекоммуникационной системы необходим двоичный линейный блоковый код длины 20 со скоростью 1/2, исправляющий двукратные ошибки. Возможно ли его получение путем укорочения БЧХ–кода?

9.31. Одним из кодов, используемых в звуковом CD стандарте, является укороченный (32,28) код Рида–Соломона. Алфавит кода содержит 256 символов. Какова длина, число информационных символов и кодовое расстояние исходного (не укороченного) кода Рида–Соломона?

9.32. Одним из кодов, используемых в звуковом CD стандарте, является укорочен-

ный (28,24) код Рида–Соломона в поле GF(2m ) . Его символы представляют собой все возможные m –разрядные двоичные числа. В получаемом таким образом двоичном коде

число информационных бит составляет 192. Какова длина, число 2m –ичных информационных символов и кодовое расстояние исходного (не укороченного) кода Рида–Соломона?

10. Сверточные коды.

10.1. Порождающие полиномы двоичного сверточного кода в восьмеричной системе счисления заданы в виде (g1, g2 ) = (23, 35) .

а). Какова длина кодового ограничения и скорость формируемого кода? б). Изобразить кодер на основе регистра сдвига.

в). Закодировать поток входных данных 1000000000… и 1100000000, определить вес полученных кодовых слов и расстояние между ними.

10.2. Порождающие полиномы двоичного сверточного кода в восьмеричной системе счисления заданы в виде (g1, g2 , g3 ) = (13,15,17) .

а). Какова длина кодового ограничения и скорость формируемого кода? б). Изобразить кодер на основе регистра сдвига.

в). Закодировать поток входных данных 1000000000… и 1100000000…, определить вес полученных кодовых слов и расстояние между ними.

25

10.3. Порождающие полиномы двоичного сверточного кода в восьмеричной систе-
ме счисления заданы в виде (g1, g2 ,			g3, g4 ) = (5, 7, 7, 7) .
а). Какова длина кодового ограничения и скорость формируемого кода?
б). Изобразить кодер на основе регистра сдвига.
в). Закодировать поток входных данных 1000000000… и 1100000000…, определить
вес полученных кодовых слов и расстояние между ними.
10.4.	Порождающие	полиномы				двоичного сверточного кода			заданы в	виде
g1(z) =1, g2	(z) =1+ z . Требуется:
а). изобразить диаграмму состояний данного кода;
б). найти передаточную функцию T (D) ;
в). определить свободное расстояние и асимптотический выигрыш от кодирования
при использовании мягких решений;
г). найти полную передаточную функцию T (D, N, L) ;
д). нарисовать решетчатую диаграмму кода;
е). найти на решетчатой диаграмме три пути с наименьшим весом.
10.5.	Порождающие	полиномы				двоичного сверточного кода			заданы в	виде
g1(z) =1, g2	(z) =1+ z и g3 (z) =1+ z . Требуется:
а). изобразить диаграмму состояний данного кода;
б). найти передаточную функцию T (D) ;
в). определить свободное расстояние и асимптотический выигрыш от кодирования
при использовании мягких решений;
г). найти полную передаточную функцию T (D, N, L) ;
д). нарисовать решетчатую диаграмму кода;
е). найти на решетчатой диаграмме три пути с наименьшим весом.
10.6. Порождающие полиномы двоичного сверточного кода заданы в виде:
	g (z) =1+ z2 , g		2	(z) =1+ z + z2 и g			3	(z) =1+ z + z2 .
Требуется:	1
а). нарисовать диаграмму состояний данного кода;
б). найти передаточную функцию T (D) ;
в). определить величину свободного расстояния и асимптотический выигрыш от
кодирования;
г). нарисовать решетчатую диаграмму;
д). определить по решетчатой диаграмме пути с наименьшим весом и их число.
10.7.	Один из двух	порождающих полиномов сверточного							кода имеет	вид
g (z) =1+ z + z2 . Какой из полиномов g					2	(z) =1 или g	2	(z) =1+ z2 обеспечит лучшее зна-
1
чение выигрыша от кодирования, каково его максимальное значение?

10.8. Имеются два альтернативных варианта кодирования потока информационных данных:

– на основании блокового кода Рида–Маллера с k = 4 ;

R =1/ 2–. с помощью сверточного кода с длиной кодового ограничения m = 4 и скоростью

При почти одинаковых затратах на реализацию какой из вариантов является предпочтительным?

26

10.9. Предположим, что имеются два альтернативных варианта кодирования потока данных. Первый состоит в использовании кода Рида–Маллера с k = 5 , а второй – в применении сверточного кода с длиной кодового ограничения m = 5 , скоростью R =1/ 3 и свободным расстоянием d =12 . При почти одинаковых затратах на реализацию какой из вариантов является предпочтительным?

10.10. Сверточный код, порождаемый полиномами g1(z) =1+ z и g2 (z) =1+ z2 , используется для кодирования потока данных вида 111111... .Объяснить, почему подобный код называется катастрофическим и не рекомендуется для практического использования?

10.11. Сверточный код, порождаемый полиномами	g (z) =1+ z3	и
	1

g2 (z) =1+ z + z2 , используется для кодирования потока данных вида 110110110110110...

.Объяснить, почему подобный код называется катастрофическим и не рекомендуется для практического использования?

10.12. Неподходящий выбор порождающих полиномов может привести к построению катастрофического сверточного кода, т.е. к кодированию бесконечного потока данных бесконечного веса в бесконечное кодовое слово с конечным числом единиц. Показать, что

а). код с порождающими полиномами, имеющими общий делитель вида g(z) =1+ z всегда будет катастрофическим;

б). систематический сверточный код никогда не будет катастрофическим.

10.13. Обобщить решение задачи 10.12а на случай представления общего делителя в виде g(z) =1+ zu(z) , где u(z) – произвольный ненулевой полином конечной степени. (Подсказка: первоначально необходимо доказать, что последовательность 1/(1+ u(z)) не может иметь конечного веса).

10.14. Имеется сверточный код, порождаемый полиномами g1(z) =1 и g2 =1+ z . Переданное кодовое слово имеет вид 110100111001, причем последние два символа отвечают нулевым информационным битам, устанавливающим кодер в нулевое состояние. Ошибки происходят на позициях второго и пятого кодовых символов. Сколько и какие передаваемые биты сообщения окажутся неправильно декодированными?

10.15. Рассматривается сверточный код с порождающими полиномами g1(z) =1, g2 (z) =1+ z и g3 (z) =1+ z . Передается кодовое слово 111100100011 (последние три символа отвечают нулевым битам потока данных, необходимых для обнуления кодера). При передаче исказились второй, третий и пятый кодовые символы. Сколько и какие передаваемые биты сообщения будут неправильно декодированы?

10.16. Декодировать максимально возможное число информационных бит при условии, что наблюдается слово 10010001111010, а порождающими полиномами служат g1(z) =1, g2 (z) =1+ z .

10.17. Декодировать максимально возможное число информационных бит при условии, что наблюдается слово 100101100011000, а порождающими полиномами служат g1(z) =1, g2 (z) =1+ z и g3 (z) =1+ z .

27

10.18. Декодировать принятую последовательность 10010100011100 при условии,

что порождающими сверточный код полиномами являются g1 =1+ z2 , g2 =1+ z + z2 , а после кодирования пяти бит кодер обнуляется путем подачи на вход двух нулевых бит.

10.19. Декодировать принятую последовательность 111111100000100111 при усло-
вии, что порождающими сверточный код полиномами являются g								=1+ z2	, g	2	=1+ z + z2
							1
и g3 =1+ z + z2 , а после кодирования четырех бит кодер обнуляется путем подачи на вход
двух нулевых бит.
10.20. Поток данных кодируется двоичным сверточным кодом с порождающими
полиномами g1(z) =1 и g2	(z)	=1+ z			. Двоичные кодовые символы передаются с помощью
бинарных ФМ сигналов, так что 0				→	+1, а	1 →	−1. На выходе гауссовского канала наблю-
дается последовательность	Y = (−0.5, − 0.5,					−	3, − 4, − 6, 2, − 4, 5, 3, −	2) . Декодировать по-
следнюю с использованием процедур жестких и мягких (основанную на вычислении кор-
реляции между наблюдением и путями по решетке) решений при условии, что два по-
следних символа отвечают нулевому входному биту, устанавливающему кодер в нулевое
состояние. Объяснить различия (если они есть) в результатах декодирования при исполь-
зовании этих двух процедур. Какой из двух результатов достовернее?
10.21. Поток данных кодируется двоичным сверточным кодом с порождающими
полиномами g (z) =1+ z2 и g		2	(z) =1+ z + z2				. На выходе гауссовского канала наблюдает-
1
ся последовательность Y = (5, 6, 0.5, 0.5, 0.5, 5, − 4, 5, − 3, − 2) . Декодировать последнюю с
использованием процедур жестких и мягких (основанную на вычислении корреляции ме-
жду наблюдением и путями по решетке) решений при условии, что четыре последних
символа отвечают двум входным нулевым битам, устанавливающим кодер в нулевое со-
стояние. Объяснить различия (если они есть) в результатах декодирования при использо-
вании этих двух процедур. Какой из двух результатов достовернее?
10.22. Сверточный	код		с	выкалыванием, полученный из				кода	со		скоростью
R0 =1/ 2 , имеет скорость R = 7 /10				. Определить параметры исходного кода.

10.23. Какова максимально возможная скорость сверточного 1/ n –скоростного кода, позволяющего построить код с выкалыванием со скоростью R = 3/10 ? Определить параметры исходного кода.

28