Для рассматриваемого примера это уравнение будет иметь вид

ejl = bjl (1 + e5bjl 1 + e3bjl 2)[e] 1;

тогда

e2 = e2(1 + e5e 2 + e3e 4)e 1 = e; e4 = e4(1 + e5e 4 + e3e 8)e 1 = e5:

Таким образом, e(x) = ex2 + e5x4 и декодированное слово равно

vˆ(x) = r(x) + e(x) = 0:

Исправлены две ошибки. Была передана нулевая кодовая комбинация.

3.3. Порядок выполнения задания

Задание выполняется каждым учащимся индивидуально. Вариант задания выбирается согласно номеру студента в журнале группы.

Все расчеты должны быть расписаны максимально подробно.

1.Построить по заданным параметрам (n;k)-код РС. Код должен быть построен над полем GF(2m), где m = 4. Порождающий полином поля Галуа p(x) = x4 +x +1. Элементы поля представлены в табл. 2.1. Код должен гарантированно исправлять три ошибки (t = 3). Считать, что b = 1. Задание выполнять в следующем порядке:

а) определить n и k;

б) определить образующий полином кода РС; в) нарисовать схему систематического кодера РС.

2.Согласно номеру в журнале выбрать из табл. 3.1 информационный вектор u и полином ошибок e(x). Преобразовать вектор u в полином u(x). Считать, что вектор u записан, начиная с младшей степени.

3.Закодировать полученный в предыдущем пункте информационный полином u(x) систематическим кодом РС. Для кодирования использовать порождающий полином или схему кодера.

4.Наложить на полученный в предыдущем пункте кодовый полином v(x) кода РС двукратную ошибку e(x) и декодировать полученную комбинацию r(x) = v(x) + e(x) синдромным методом декодирования. Для решения ключевого уравнения использовать любой из трех алгоритмов (Берлекэмпа– Месси, Питерсона–Горенштейна–Цирлера, Евклида). Задание выполнять в следующем порядке:

а) определить синдромы; б) решить ключевое уравнение;

в) определить позиции ошибки по методу Ченя; г) определить значения ошибок по алгоритму Форни; д) исправить ошибки.

40

Таблица 3.1

Информационный вектор u и полином ошибок e(x) (выбираются согласно номеру студента в журнале)

№		Информационный вектор u	e(x)
1		e8 e5 e14 e10 e7 e7 e3 e0 e4	e5x3 + e14x13
2		e8 e3 e8 e13 e4 e3 e14 e14 e12	e11x2 + e12x6
3		e13 e2 e8 e1 e4 e5 e10 e10 e4	e4x9 + e8x10
4		e13 e9 e7 e14 e5 e3 e2 e8 e14	e13x2 + e0x8
5		e3 e13 e0 e13 e7 e4 e13 e5 e5	e11x11 + e4x14
6		e11 e11 e2 e3 e9 e0 e11 e14 e7	e2x9 + e6x14
7		e7 e5 e14 e4 e12 e12 e5 e5 e13	e11x2 + e10x9
8		e0 e13 e1 e7 e11 e14 e13 e4 e4	e0x5 + e13x6
9		e3 e1 e11 e5 e14 e10 e9 e14 e9	e11x2 + e0x5
10		e13 e13 e14 e9 e10 e3 e7 e11 e4	e7x2 + e10x6
11		e9 e4 e5 e0 e0 e0 e6 e3 e6	e5x4 + e4x7
12		e3 e8 e10 e0 e11 e1 e6 e1 e8	e6x2 + e14x4
13		e14 e2 e12 e10 e1 e2 e2 e4 e10	e2x2 + e2x12
14		e0 e0 e1 e0 e0 e14 e12 e11 e6	e2x5 + e1x9
15		e5 e4 e12 e6 e2 e8 e11 e3 e11	e13x9 + e10x13
16		e13 e11 e13 e4 e13 e10 e8 e3 e9	e5x5 + e4x10
17		e10 e3 e6 e8 e13 e0 e3 e5 e10	e13x6 + e0x13
18		e0 e5 e12 e14 e0 e9 e13 e5 e1	e10x6 + e13x14
19		e10 e13 e5 e8 e9 e2 e7 e7 e7	e14x3 + e0x14
20		e4 e2 e2 e10 e12 e14 e6 e1 e5	e13x4 + e7x5
21		e13 e6 e13 e12 e13 e2 e13 e13 e14	e12x4 + e2x10
22		e8 e5 e7 e6 e1 e1 e5 e3 e6	e2x10 + e14x12
23		e14 e13 e1 e2 e7 e12 e9 e11 e13	e0x3 + e9x14
24		e4 e0 e9 e14 e9 e12 e0 e9 e0	e4x4 + e13x10
25		e5 e1 e4 e2 e6 e4 e0 e8 e2	e0x5 + e14x7
26		e8 e1 e1 e6 e7 e14 e14 e2 e7	e1x3 + e4x6
27		e8 e3 e6 e4 e6 e13 e4 e12 e6	e9x6 + e3x7
28		e6 e7 e13 e10 e13 e1 e11 e1 e14	e1x5 + e9x12
29		e14 e8 e7 e2 e13 e12 e11 e10 e9	e5x6 + e1x11
30		e13 e7 e0 e3 e9 e9 e3 e12 e0	e9x7 + e4x11

41

3.4. Порядок защиты практической работы

Защита работы может осуществляться одним из нижеперечисленных способов или их сочетанием на усмотрение преподавателя.

1.Устный ответ по теме работы.

2.Тестирование по теме работы

3.Задача по теме работы.

4.Иные варианты на усмотрение преподавателя.

Контрольные вопросы

1.Что такое код Рида–Соломона?

2.Построение порождающего полинома кода РС.

3.Алгоритм Берлекэмпа–Месси.

4.Алгоритм Евклида.

5.Алгоритм Форни.

42

Список литературы

[1]Вернер, М. Основы кодирования : учебник для ВУЗов / М. Вернер. Мир программирования. — М. : Техносфера, 2004.

[2]Когновицкий, О. С. Основы циклических кодов : учебное пособие / О. С. Когновицкий. — Л. : ЛЭИС, 1990.

[3]Шварцман, В. О. Теория передачи дискретной информации : учебник для вузов связи / В. О. Шварцман, Г. А. Емельянов. — М. : Связь, 1979.

[4]Морелос-Сарагоса, Р. Искусство помехоустойчивого кодирования. Методы, алгоритмы, применение. / Р. Морелос-Сарагоса. Мир связи. — М. : Техносфера, 2005.

[5]Блейхут, Р. Теория и практика кодов, контролирующих ошибки / Р. Блейхут. — М. : Мир, 1986.

[6]Берлекэмп, Э. Алгебраическая теория кодирования. / Э. Берлекэмп. — М. : Мир, 1972.

[7]Massey, J. L. Shift-Register Synthesis and BCH Decoding / J. L. Massey // Information Theory, IEEE Transactions on. — 1969. — Jan. — Vol. 15. — P. 122–127.

[8]Габидуллин, Э. М. Кодирование в радиоэлектронике / Э. М. Габидуллин, В. Б. Афанасьев. — М. : Радио и связь, 1986.

[9]Скляр, Б. Цифровая связь. Теоретические основы и практическое применение / Б. Скляр ; под ред. А.В. Назаренко. — М. : Издательский дом «Вильямс», 2003.

[10]Золотарёв, В. В. Помехоустойчивое кодирование. Методы и алгоритмы : справочник / В. В. Золотарёв, Г. В. Овечкин ; под ред. чл.-корр. РАН Ю. Б. Зубарева. — М. : Горячая линия–Телеком, 2004.

[11]Варгаузин, В. А. Методы повышения энергетической и спектральной эффективности цифровой радиосвязи : учебное пособие / В. А. Варгаузин, И. А. Цикин. — СПб. : БХВ-Петербург, 2013.

[12]Галлагер, Р. Теория информации и надежная связь / Р. Галлагер ; под ред. М. С. Пинскера, Б. С. Цыбакова. — М. : «Сов. радио», 1974.

[13]Lin, S. Error Control Coding: Fundamentals and Applications / S. Lin, D. J. Costello. — New Jersey : Printice-Hall, 1983.

[14]Теория электрической связи : учебное пособие / К. К. Васильев, В. А. Глушков, А. В. Дормидонтов, А. Г. Нестеренко ; под ред. К. К. Васильева. — Ульяновск : УлГТУ, 2008.

43

Владимиров Сергей Сергеевич Когновицкий Олег Станиславович

ПРАКТИКА ПОМЕХОУСТОЙЧИВОГО КОДИРОВАНИЯ. ЦИКЛИЧЕСКИЕ КОДЫ

Практикум

Редактор Л. К. Паршина

План издания 2019, п. 50

Подписано к печати 27.12.2019 Объем 2,75 печ. л. Тираж 12 экз. Заказ 1016

Редакционно-издательский отдел СПбГУТ 193232 СПб., пр. Большевиков, 22 Отпечатано в СПбГУТ