close

Вход

Забыли?

вход по аккаунту

?

Markovskiy

код для вставкиСкачать
МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ
Федеральное государственное автономное
образовательное учреждение высшего образования
САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ
АЭРОКОСМИЧЕСКОГО ПРИБОРОСТРОЕНИЯ
ЦИКЛИЧЕСКИЕ КОДЫ
Методические указания
по выполнению курсовой работы
Санкт-Петербург
2016
Составители: С. Г. Марковский, Н. В. Марковская, А. М. Тюрликов
Рецензент – кандидат технических наук, доцент В. П. Попов
Представлены методические указания и рассмотрен подробный
пример выполнения курсовой работы по дисциплине «Теория информационных процессов и систем».
Предназначены для бакалавров заочной формы обучения, обучающихся по направлению 09.03.02.
Публикуется в авторской редакции.
Компьютерная верстка Н. Н. Караваевой
Сдано в набор 27.01.16. Подписано к печати 11.02.16. Формат 60×84 1/16.
Бумага офсетная. Усл. печ. л. 1,2. Тираж 50 экз. Заказ № 47.
Редакционно-издательский центр ГУАП
190000, Санкт-Петербург, Б. Морская ул., 67
© Санкт-Петербургский государственный
университет аэрокосмического
приборостроения, 2016
1. ОСНОВНЫЕ СВЕДЕНИЯ
ИЗ ТЕОРИИ ЦИКЛИЧЕСКИХ КОДОВ
1.1. Определение циклического кода
Определение. Циклическим кодом называется такой линейный
код [1], для которого циклический сдвиг любого кодового слова также является кодовым словом.
Рассмотрим следующие три кода и выясним, какие из этих кодов
являются циклическими:
a1 = (001), a2 = (010), a3 = (100), a4 = (111) – этот код не линейный,
следовательно, он не циклический;
a1 = (110), a2 = (101), a3 = (011), a4 = (000) – этот код линейный,
выполняется условие замкнутости для циклического кода, следовательно, код циклический;
a1 = (00000), a2 = (01011), a3 = (10101), a4 = (11110) – этот код линейный, но при циклическом сдвиге существуют слова, не принадлежащие этому коду, следовательно, код не циклический.
Замечание. Второй код – это линейный код с двумя информационными символами и одним проверочным (проверочный символ
формируется, как сумма по модулю 2 информационных символов).
Для математического описания циклических кодов используются многочлены с коэффициентами из конечного поля.
1.2. Многочлен с коэффициентами из конечного поля.
Операции над многочленами
Пусть имеется некоторое конечное поле GF(q) [1]. Многочленом
степени n называется следующее математическое выражение:
g(x=
) an xn + an −1xn −1 +  + a1x1 + a0 x0 , ai ∈ GF (q),
где q – число элементов в этом поле, x – формальная переменная.
3
Над многочленами определены следующие операции:
1) Сложение многочленов:
a(x=
) an xn +  + a1x1 + a0 x0 , b(x=
) bn xn +  + b1x1 + b0 x0 ,
тогда c(x) = a(x) + b(x) = (an + bn )xn +  + (a1 + b1 )x1 + (a0 + b0 )x0 .
Пример 1. Задано поле GF(2), a(x) = x3 + x2 + x, b(x) = x4 + x3 +
+ x2 + x2 + 1. Тогда, c(x) = x3 + x2 + x + x4 + x3 + x2 + x + 1 = x4 + 1.
Пусть степень многочлена deg(a(x)) = n1, deg(b(x)) = n2 , тогда из
операции сложения многочленов deg(a(x) + b(x)) ≤ max(n1,n2 ).
2) Умножение многочленов:
Пример 2. Задано поле GF(2), a(x) = x2 + x + 1, b(x)= x + 1. Тогда,
a(x)b(x) = (x2 + x + 1)(x + 1) = x3 + x2 + x2 + x + x + 1 = x3 + 1.
Если deg(a(x)) = n1, deg(b(x)) = n2 , то deg(a(x)b(x))
= n1 + n2 .
3) Деление многочленов с остатком.
Пример 3. Задано поле GF(2), b(x) = x3 + x + 1, g(x)= x + 1. Тогда,
b(x)mod g(x)= (x3 + x + 1)mod(x + 1)= 1 (рис. 1), где mod – операция
взятия остатка.
Запишем равенство, которое связывает 4 многочлена:
=
b(x) m(x) g(x) + c(x), deg(c(x)) < deg(g(x)).
Для двоичных многочленов (многочленов в поле GF(2)) используется сокращенная запись в виде списка степеней с ненулевыми коэффициентами.
Пример 4. Сокращенная запись для примера 2: a(x) = x2 + x + 1 ->
(210), b(x)= x + 1 -> (10). (210)(10) = (322110) = (30) -> x3 + 1 .
Многочлену
a(x=
) an xn + an −1xn −1 +  + a1x1 + a0 x0
степени
deg(a(x)) = n соответствует вектор a = (an an −1 a1a0 ) длины n + 1.
b(x)
q(x)
x +x+1
x+1
x3 + x2
x2 + x
3
–
m(x)
x2 + x + 1
– 2
x +x
1
c(x)
Рис. 1. Деление многочленов с остатком
4
Пример 5. Задан многочлен: a(x=
) x2 + 1. Какой вектор соответствует этому многочлену? a = (101), a(x) = 1 ⋅ x2 + 0 ⋅ x + 1 ⋅ 1.
Для сложения многочленов справедливо следующее утверждение.
Утверждение 1. Пусть имеется взаимно-однозначное соответствие между многочленами и векторами: a(x) ↔ a, b(x) ↔ b. Тогда,
a(x) + b(x) ↔ a + b.
Пример 6. Иллюстрация утверждения. Пусть заданы многочлены a(x) = x2 + x ↔ (110) и b(x) = x + 1 ↔ (011). Складываем многочлены: a(x) + b(x) = x2 + 1 ↔ (101).
Для того чтобы провести аналогию между операциями умножения многочленов и операциями над векторами рассмотрим следующий пример.
Пример 7. Задан многочлен: a(x) = x2 + 1 ↔ (101). Получим многочлен: a(x) ⋅ x = x3 + x ↔ (1010). Этот многочлен можно получить
путем сдвига вектора влево на 1 разряд.
Утверждение 2. Многочлену a(x), умноженному на xw, соответствует вектор a, сдвинутый на w позиций влево.
1.3. Порождающий многочлен циклического кода
Неформально, порождающий многочлен циклического кода
можно определить как некоторый многочлен, с помощью которого
можно получить весь список кодовых слов.
Пример 8. Пусть имеется следующий код:
a1 = (0000), a2 = (0101), a3 = (1010) – сдвиг a2 влево на 1 разряд,
a4 = (1111) – сложение a2 и a3. Поставим каждому кодовому слову в соответствие свой многочлен: a1 (x) = 0, a2 (x=
) x2 + 1, a3 (x=
) x3 + x,
3
2
a4 (x) = x + x + x + 1.
Далее при изложении материала, вместо использования утверждений типа: многочлен a(x), соответствующий кодовому слову a, будем кратко говорить: кодовое слово a(x).
Определение. Ненулевое кодовое слово наименьшей степени, называется порождающим многочленом циклического кода.
Пример 9. Укажем порождающий многочлен для кода из предыдущего примера. Код состоит из 4 кодовых слов (M = 4). Если исключить из рассмотрения слово a1 (x) = 0, состоящее из всех нулей,
то наименьшую степень имеет кодовое слово a2 (x=
) x2 + 1. Следовательно, оно и является порождающим многочленом, т. е. порождающий многочлен этого кода: g(x=
) x2 + 1.
Порождающий многочлен обладает следующими свойствами.
5
x3 + x
– 3
x +x
0
x2 + 1
x
–
2
x3 + x2 + x + 1 x + 1
x+ 1
x3 + x
– остаток ноль
–
x2 + 1
x2 + 1
0
– остаток ноль
Рис. 2. Деление кодовых слов на порождающий многочлен
Свойство 1. Степень порождающего многочлена равна r, т. е.
deg(g(x)) = r , где r – число проверочных символов в коде.
Свойство 2. Все кодовые слова делятся без остатка на порождающий многочлен:
∀a(x) : a(x)mod g(x) =
0.
Проиллюстрируем свойства порождающего многочлена на следующем примере.
Пример 10. Возьмем код из примера 8.
1) Длина кода n = 4, M = 4 = 2k, k = 2, r = n – k = 2, где k – число
информационных символов в коде. Следовательно, deg(g(x)) = 2.
2)  a3 (x)mod g(x) = 0, a4 (x)mod g(x) = 0 (рис. 2).
Непосредственно из свойства 2 следует алгоритм работы кодера/
декодера циклического кода для случая обнаружения ошибок.
Декодер хранит порождающий многочлен циклического кода и
для каждой, принятой из канала, последовательности y выполняет
следующие действия:
1. Представляет последовательность y в виде многочлена:
y <-> y(x);
2. Вычисляет многочлен: S(x) = y(x)mod g(x);
3. Если S(x) ≠ 0, то формируется сигнал обнаружения ошибки.
1.4. Определение параметров циклического кода
по порождающему многочлену
Справедливо следующее утверждение.
Утверждение 3. Длина циклического кода с порождающим многочленом g(x), это такое наименьшее значение n, для которого
xn mod g(x) = 1.
6
Воспользуемся этим утверждением и свойством 1 порождающего
многочлена для определения параметров циклического кода со следующим порождающим многочленом g(x) = x3 + x + 1.
В соответствии со свойством 1 определяем число проверочных
символов в коде r = deg(g(x)) = 3.
По утверждению 3 определяем длину кода. Для этого выполним
следующую итерационную процедуру:
x0 mod(x3 + x + 1) =
1;
x1 mod(x3 + x + 1) =
x;
x2 mod(x3 + x + 1) =
x2 ;
x3 mod(x3 + x + 1) = x + 1, n ≠ 3;
x4 mod(x3 + x + 1)= (x3 ⋅ x)mod(x3 + x + 1)=
3
= ((x3 mod(x3 + x + 1)) ⋅ x)mod(x=
+ x + 1)
= ((x + 1) ⋅ x)mod(x3 + x + 1) = x2 + x,
n ≠ 4;
x5 mod(x3 + x + 1) = (x3 + x2 )mod(x3 + x + 1) = x2 + x + 1, n ≠ 5;
x6 mod(x3 + x + 1) = (x3 + x2 + x)mod(x3 + x + 1) = x2 + 1, n ≠ 6;
x7 mod(x3 + x + 1)= (x3 + x)mod(x3 + x + 1)= 1.
Длина кода n = 7, число информационных символов кода
k = n – r = 4.
Таким образом, по порождающему многочлену можно определить все параметры циклического кода.
1.5. Кодирование циклических кодов
Кодер хранит порождающий многочлен g(x) и для каждой кодируемой последовательности m выполняет следующие действия:
1) Для вектора m формируем многочлен: m <-> m(x);
2) Вычисляем многочлен a=
(x) m(x) ⋅ g(x);
3) По многочлену a(x) формируем вектор a.
Пример 11. g(x) = x3 + x + 1, m = (1001). Выполнить кодирование.
1)  m(x=
) x3 + 1;
2)  a(x) = m(x) g(x) = (x3 + 1)(x3 + x + 1) = x6 + x4 + x3 + x3 + x + 1 =
= x6 + x4 + x + 1;
3) Получаем вектор длины 7: a = (1010011).
7
Замечание. Рассмотренный способ кодирования называется несистематическим кодированием. При этом способе информационные символы не располагаются в начале кодового слова, а как бы
“размазываются” по кодовым словам. Поэтому, на практике чаще
используется другой способ кодирования циклических кодов.
1.6. Систематическое кодирование циклических кодов
Кодер хранит порождающий многочлен циклического кода g(x)
и для каждой кодируемой последовательности m выполняет следующие действия:
1) вектору m ставится в соответствие многочлен: m <-> m(x);
2) вычисляется многочлен c(x) = m(x)xr mod(g(x));
3) многочлен a(x) формируется как:
=
a(x) m(x)xr + c(x);
4) многочлену a(x) ставится в соответствие вектор a.
Многочлен c(x) называется контрольной суммой. m(x)xr – сдвиг
вектора m влево на r позиций.
Алгоритм систематического кодирования представлен на рис.3.
Пример 12. g(x) = x3 + x + 1, m = (1001). Выполнить систематическое кодирование.
1)  m(x=
) x3 + 1;
2)  c(x) =
m(x)xr mod(g(x)) =
(x3 + 1)x3 mod(g(x)) =
(x6 + x3 )mod(g(x)) =
= x6 mod(g(x)) + x3 mod(g(x))= x2 + 1 + x + 1= x2 + x;
3)  a(x) = m(x)xr + c(x) = x6 + x3 + x2 + x;
4) a = (1001110). Старшие 4 символа вектора a – информационные
символы, 3 младших символа – проверочные символы.
Из приведенного выше алгоритма следуют следующие выводы:
1. В результате кодирования получаются слова линейного кода;
2. Данный линейный код – циклический код;
m(x)
m(x)
c(x)
k
r
Рис. 3. Алгоритм систематического кодирования
8
3. Все кодовые слова делятся без остатка на порождающий многочлен (a(x)mod g(x) = 0).
Проиллюстрируем эти выводы на конкретных примерах.
Пусть на вход кодера поступает последовательность m1, на выходе формируется кодовое слово a1. Также на вход кодера поступает последовательность m2, на выходе формируется кодовое слово a2
(рис. 4).
Пример 13. m1 = (1001), m2 = (1000).
Кодовое слово a1 = (1001110) (см. пример 12).
m2 (x) = x3 . c2 (x=
) x3 x3 mod(g(x=
)) x6 mod(g(x=
)) x2 + 1.
a2 (x) = x6 + x2 + 1. a2 = (1000101).
m3 = m1 + m2 = (1001) + (1000) = (0001).
m3 (x) = 1. c3 (x)= x3 mod(g(x))= x + 1. a3 = (0001011).
Для линейного кода: a3 = a1 + a2 = (1001110) + (1000101) =
= (0001011).
Пример 14. Проиллюстрируем вывод 3. Для этого проверим кодовое слово a1. a1 (x) = x6 + x3 + x2 + x -> (6321). Определяем остаток от
деления кодового слова на порождающий многочлен (рис. 5).
m1
Кодер
m2
Кодер
m3 + m1 + m2
Кодер
a1
a2
m3 + m1 + m2
Рис. 4. Пример систематического кодирования
–
(6321)
(643)
(310)
31
(421)
– (421)
0
– остаток ноль
Рис. 5. Проверка кодового слова
9
–
(4320)
(421)
–
(310)
(310)
0
(310)
10
– остаток ноль
Рис. 6. Проверка кодового слова
Пример 15. Для иллюстрации вывода 2 покажем, что циклический сдвиг кодового слова a1 также является кодовым словом.
a1 = (1001110). a* = (0011101) – циклический сдвиг влево первого
кодового слова.
Покажем, что вектор a* является кодовым словом, т. е. соответствующий ему многочлен делится на порождающий многочлен без
остатка (рис. 6).
a* (x) = x4 + x3 + x2 + 1 -> (4320).
1.7. Сравнение алгоритмов кодирования
и декодирования циклических кодов
Из рассмотренного выше алгоритма кодирования, следует, что
операция кодирования, фактически, сводится к вычислению многочлена c(x) = m(x)xr mod(g(x)). А операция декодирования, сводится к вычислению S(x) = y(x)mod(g(x)). Несложно показать, что
при декодировании, вместо многочлена S(x) = y(x)mod(g(x)) можно
использовать S(x) = y(x)xr mod(g(x)). Тогда, можно сделать вывод,
что кодирование и декодирование реализуются при помощи одной и
той же схемы, и, следовательно, при аппаратной реализации кодер
и декодер – идентичные устройства.
1.8. Синдромное декодирование циклических кодов
Так как циклические коды являются линейными, то все что мы
говорили о синдромном декодировании линейных кодов, может
быть перенесено на циклические коды. Однако в случае циклических кодов можно упростить вычисление синдрома.
Пусть g(x) – порождающий многочлен циклического (n,k) кода,
a(x) – переданное слово и=
y(x) yn −1xn −1 +  + y1x1 + y0 – многочлен,
10
соответствующий принятой из канала последовательности. В канале произошли ошибки, описанные вектором e, которому поставим в
соответствие полином ошибок=
e(x) en −1xn −1 +  + e1x1 + e0 . На вход
декодера канала поступает y(x) = a(x) + e(x).
Полином S(x), определяемый соотношением S(x) = y(x)mod(g(x))
называется синдромом принятой из канала последовательности
y(x). Синдром равен нулю только в том случае, если y(x) – кодовое
слово.
Теорема 1. Синдром S(x) не зависит от переданного слова, а определяется только полиномом ошибок.
Доказательство.
S(x) = y(x)mod(g(x)) = (a(x) + e(x)) mod(g(x)) =
= a(x)mod(g(x)) + e(x)mod(g(x)) = e(x)mod(g(x)).
Можно показать, что для циклических кодов (также как и для
линейных) синдромы различных ошибок, вес которых не превышает=
t (d − 1) / 2 различны, где d – минимальное расстояние кода.
Таким образом, алгоритм синдромного декодирования, за исключением правила вычисления синдрома, полностью совпадает
с алгоритмом синдромного декодирования линейных кодов.
Пример 16. Задан порождающий многочлен g(x) = x3 + x + 1. Построим таблицу соответствия синдромов и полиномов ошибок (табл.
1).
S(x) = 1 mod(x3 + x + 1) = 1.
S(x) = x mod(x3 + x + 1) = x.
S(x) = x2 mod(x3 + x + 1) = x2.
S(x) = x3 mod(x3 + x + 1) = x + 1.
= (x
(x3
S(x) = x4 mod(x3 + x + 1) = (x x3) mod(x3 + x + 1) =
mod(x3 + x + 1))) mod(x3 + x + 1) = (x (x + 1)) mod(x3 + x + 1) =
= (x2 + x) mod(x3 + x + 1) = x2 + x.
S(x) = x5 mod(x3 + x + 1) = (x x4) mod(x3 + x + 1) =
= (x (x4 mod(x3 + x + 1))) mod(x3 + x + 1) = (x (x2 + x)) mod(x3 + x + 1) =
=(x3 + x2) mod(x3 + x + 1) = x2 + x + 1
S(x) = x6 mod(x3 + x + 1) = (x x5) mod(x3 + x + 1) =
= (x (x5 mod(x3 + x + 1))) mod(x3 + x + 1) = (x (x2 + x + 1))mod(x3 + x + 1) =
= (x3 + x2 + x) mod(x3 + x + 1) = x2 + 1.
11
Таблица 1
Синдромное декодирование циклических кодов
e(x)
S(x)
e(x)
0
0
x3
S(x)
x+1
1
1
x4
x2+x
x
x
x5
x2+x+1
x2
x2
x6
x2+1
Пример 17. Задан порождающий многочлен g(x) = x3+x+1. На
вход кодера поступает сообщение m = (1001). На выходе кодера формируется кодовое слово:
a = (1001110). Пусть в процессе передачи возникла ошибка на четвертой позиции, т. е.: y = (1011110). Выполним алгоритм синдромного декодирования в режиме исправления ошибок.
1. Ставим в соответствие принятой из канала последовательности многочлен
y(x) = x6 + x4 + x3 + x2 + x.
2. Вычисляем синдром
=
x6
S(x) = (x6 + x4 + x3 + x2 + x) mod g(x) =
mod g(x) + x4 mod g(x) + x3 mod g(x) + x2 mod g(x) + x mod g(x) =
= x2 + 1 + x2 + x + x + 1 + x2 + x = x2 + x.
3. Выполняем поиск полученного синдрома в табл.1. Полученному синдрому соответствует многочлен ошибок e(x) = x4.
4. Декодер принимает решение в пользу кодового слова
a = (1001110).
Код с порождающим многочленом g(x) = x3 + x + 1 имеет минимальное расстояние d = 3. Поэтому в режиме исправления ошибок
он может исправить только одну ошибку.
Пример 18. Покажем работу декодера в режиме обнаружения
ошибок. В этом случае, декодер не исправляет ошибки, но может
обнаружить 1 или две ошибки.
Введем в вектор y еще одну ошибку на пятой позиции:
y = (1111110). Вычислим синдром:
+
x5
S(x) = (x6 + x5+ x4 + x3 + x2 + x) mod g(x) = x6 mod g(x) +
mod g(x) + x4 mod g(x) + x3 mod g(x) + x2 mod g(x) + x mod g(x) =
= x2 + 1 + x2 + x + 1 + x2 + x + x +1+ x2 + x = 1. S(x) ≠ 0.
Следовательно, декодер обнаружил две ошибки.
12
2. ПРИМЕР ВЫПОЛНЕНИЯ КУРСОВОЙ РАБОТЫ
2.1. Задание
Студент получает от преподавателя техническое задание. Различные варианты технического задания могут отличаться порождающим многочленом циклического кода, входным текстом для
кодирования, видом кодирования (систематическое, несистематическое) и распределением числа ошибок по группам текста для формирования последовательностей на входе декодера.
Пример технического задания к курсовой работе приведен в приложении.
Задан циклический код (7,4) с порождающим многочленом
x3 + x + 1. Т. е. код имеет следующие параметры: число проверочных символов r = deg(g(x)) = 3, число информационных символов
k = 4, длина кода n = 7, минимальное расстояние кода d = 3, количество исправляемых ошибок t = 1.
Входной текст: щур (3 символа, 24 бита). В табл. 2 приведены
русские строчные буквы кодировки ASCII Windows 1251.В кодировке ASCII Windows 1251 символы имеют следующие значения.
щ – 249(10) = F9(16) = 1111 1001 (2),
у – 243(10) = F3(16) = 1111 0011 (2),
р – 240(10) = F0(16) = 1111 0000 (2).
Разбиваем входной текст на группы по 4 разряда, так как согласно заданию, число информационных символов k = 4.
1111 1001 1111 0011 1111 0000.
Отметим, что в других вариантах задания, для циклического кода (7,3) входной текст разбивается на группы по 3 бита.
Формируем входные векторы для кодирования:
m1 = (1111), m2 = (1001), m3 = (1111), m4 = (0011),
m5 = (1111), m6 = (0000).
Поставим каждому вектору в соответствие многочлен:
m1 = (1111) => m1(x) = x3 + x2 + x + 1
m2 = (1001) => m2(x) = x3 + 1
m3 = (1111) => m3(x) = x3 + x2 + x + 1
m4 = (0011) => m4(x) = x + 1
m5 = (1111) => m5(x) = x3 + x2 + x + 1
m6 = (0000) => m6(x) = 0.
13
Таблица 2
Кодировка ASCII Windows для русских строчных символов
Символ
Код (10)
Код(16)
Символ
Код(10)
Код(16)
А
224
E0
Р
240
F0
Б
225
E1
С
241
F1
В
226
E2
Т
242
F2
Г
227
E3
У
243
F3
Д
228
E4
Ф
244
F4
Е
229
E5
Х
245
F5
Ж
230
E6
Ц
246
F6
З
231
E7
Ч
247
F7
И
232
E8
Ш
248
F8
Й
233
E9
Щ
249
F9
К
234
EA
Ъ
250
FA
Л
235
EB
Ы
251
FB
М
236
EC
Ь
252
FC
Н
237
ED
Э
253
FD
О
238
EE
Ю
254
FE
П
239
EF
Я
255
FF
Отметим, что каждая группа (каждый вектор) кодируется независимо от других групп (векторов).
2.2. Построение таблицы остатков от деления многочленов
на порождающий многочлен
В систематическом кодировании и синдромном декодировании
используется операция нахождения остатка от деления на порождающий многочлен. Поэтому, имеет смысл построить таблицу остатков от деления многочленов степени xr на порождающий многочлен
(табл. 3). Вычисление остатков от деления на порождающий многочлен x3 + x + 1 приведено в разделе 1.4 при вычислении длины кода.
Несмотря на то, что в задании указано систематическое кодирование, рассмотрим также несистематическое кодирование, которое
может присутствовать в других вариантах задания.
14
Таблица 3. Остатки от деления на порождающий многочлен
Остаток
Вектор
0 mod g(x)
0
(000)
1mod g(x)
1
(001)
x mod g(x)
x
(010)
x2
x2
(100)
x3 mod g(x)
x+1
(011)
x4
x2 +
(110)
mod g(x)
mod g(x)
x5 mod g(x)
x6
mod g(x)
x
x2 + x + 1
x2 +
1
(111)
(101)
2.3. Несистематическое кодирование
Выполним кодирование входных векторов. Заметим, что векторы m1, m3 и m5 одинаковые. Поэтому, из этих трех векторов, достаточно выполнить кодирование только вектора m1.
a1(x) = m1(x) g(x) = (x3 + x2 + x + 1) (x3 + x+1) =
= x6 + x4 + x3 + x5 + x3 + x2 + x4 + x2 + x + x3 + x+1 =
= x6 + x5 + x3 +1. a5(x) = a3(x) = a1(x).
a2(x) = m2(x) g(x) = (x3 + 1) (x3 + x+1) =
=x6 + x4 + x3 + x3 + x+1 = x6 + x4 + x +1.
a4(x) = m4(x) g(x) = (x + 1) (x3 + x+1) =
= x4 + x2 + x + x3 + x+1 = x4 + x3 + x2 +1.
a6(x) = m6(x) g(x) = 0 (x3 + x+1) = 0.
Проверим кодовые слова. Все кодовые слова должны без остатка
делиться на порождающий многочлен. При вычислении остатков
будем использовать правило: модуль суммы равен сумме модулей.
Остатки выбираем из табл. 3. Кодовое слово a6(x) не проверяется,
так как известно, что любой циклический код обязательно содержит вектор, состоящий из всех нулей.
=
a1(x)modg(x) = (x6 + x5 + x3 +1)mod(x3 + x + 1) =
6
x mod(x3 + x + 1) + x5mod(x3 + x + 1) + x3mod(x3 + x
=
a2(x)modg(x) = (x6 + x4 + x + 1)mod(x3 + x + 1) =
6
x mod(x3 + x + 1) + x4mod(x3 + x + 1) + xmod(x3 + x +
+ 1) +
+ 1mod (x3 + x + 1) = x2 + 1 + x2 + x + 1 + x + 1 + 1 = 0.
1) +
+ 1 mod (x3 + x + 1) = x2 + 1 + x2 + x + x + 1 = 0.
15
1111 1001 1111 0011 1111 0000
m
Кодер g(x) = x3 + x + 1
1101001 1010011 1101001 0011101 1101001 0000000
a
Рис.7. Результаты несистематического кодирования
=
a4(x)modg(x) = (x4 + x3 + x2 + 1)mod(x3 + x + 1) =
4
x mod(x3 + x + 1) + x3mod(x3 + x + 1) + x2mod(x3 + x +
1) +
+ 1 mod (x3 + x + 1) = x2 + x + x + 1 + x2 + 1 = 0.
Вывод: все кодовые слова определены правильно. Результаты кодирования представлены на рис. 7. На вход кодера поступает последовательность из 24 бит, на выходе последовательность
из 42 бит.
2.4. Систематическое кодирование
Выполним кодирование векторов, используя алгоритм систематического кодирования.
c1(x) = m1(x)xrmod g(x) = (x3 + x2 + x + 1)x3modg(x) =
= (x6 + x5 + x4 + x3)modg(x) = x6modg(x) + x5modg(x) + x4modg(x) +
+ x3modg(x) = x2 + 1 + x2 + x + 1+ x2 + x + x + 1 = x2 + x + 1.
a1(x) = m1(x) xr + c1(x)= (x3 + x2 + x + 1) x3 + x2 + x + 1=
= x6 + x5 + x4 + x 3+ x2 + x + 1.
a5(x) = a3(x) = a1(x)
c2(x) = m2(x)xrmodg(x) = (x3 + 1)x3modg(x) = (x6 + x3)modg(x) =
= x6modg(x) + x3modg(x) = x2 + 1 + x + 1 = x2 + x.
a2(x) = m2(x) xr + c2(x)= (x3 + 1) x3 + x2 + x = x6 + x3+ x2 + x.
c4(x) = m4(x)xrmodg(x) = (x + 1)x3modg(x) = (x4 + x3)modg(x) =
= x4modg(x) + x3modg(x) = x2 + x + x + 1 = x2 + 1.
a4(x) = m4(x) xr + c4(x)= (x + 1) x3 + x2 + 1 = x4 + x3+ x2 + 1.
16
1111 1001 1111 0011 1111 0000
m
Кодер g(x) = x3 + x + 1
1111111 1001110 1111111 0011101 1111111 0000000
a
Рис. 8. Результаты систематического кодирования
Проверим кодовые слова.
a1(x)modg(x) = (x6 + x5 + x4 + x3 +x2 + x + 1)modg(x) =
6
= x modg(x) + x5modg(x) + x4modg(x) + x3modg(x) + x2modg(x) +
+ xmodg(x) + 1modg(x) = x2 + 1 + x2 + x +
+ 1+ x2 + x + x + 1 + x2 + x + 1 = 0.
a2(x)modg(x) = (x6 + x3 +x2 + x)modg(x) =
= x6modg(x) + x3modg(x) + x2modg(x) + xmodg(x) =
= x2 + 1 + x +1+ x2 + x = 0.
a4(x) совпадает с соответствующим кодовым словом при несистематическом кодировании. Проверка его уже была выполнена ранее.
Вывод: кодовые слова определены правильно. Результаты кодирования приведены на рис. 8. Заметим, что в каждом кодовом слове,
первые 4 символа совпадают с входными векторами.
2.5. Построение таблицы соответствия синдромов
и векторов ошибок
При d = 3 циклический код может исправить только одну ошибку. Все варианты векторов одиночных ошибок представлены в левом столбце табл. 4. S(x) = e(x)modg(x). При заполнении таблицы использованы остатки от деления (см. табл.3).
2.6. Декодирование
Предположим, что ошибки присутствуют в кодовых словах a1(x)
и a2(x). На вход декодера поступают 7-битные последовательности
с выхода канала. Согласно заданию ошибки присутствуют в кодо17
вых словах a1(x) и a2(x).Внесем в каждое кодовое слово 1 ошибку,
т. е. сформируем последовательности y1(x) и y2(x).
y1(x) = x6 + x3 + 1, y2(x) = x6 + x + 1. Хотя в задании указано систематическое кодирование, выполним декодирование для случая,
когда в кодере использовался алгоритм несистематического кодирования. Далее, укажем отличие в процессе декодирования, если
в кодере применялся алгоритм систематического кодирования. Выполним алгоритм синдромного декодирования.
Для первой последовательности определяем синдром
S1(x) = y1(x)modg(x) = (x6 + x3 + 1)modg(x) =
= x6modg(x) + x3modg(x) + 1modg(x) =
= x2 + 1 + x + 1+ 1 = x2 + x +1.
По таблице соответствия синдромов и векторов ошибок выбираем вектор ошибки
e1(x) = x5.
Восстанавливаем кодовое слово
a1(x) = y1(x) + e1(x) = x6 + x5 + x3+ 1.
Так как выполнялось несистематическое кодирование, то теперь необходимо определить входной вектор m1(x) по формуле
m1(x) = a1(x)/g(x).
m1(x) = (x6 + x5 + x3+ 1)/( x3 + x + 1)= x3 + x2 + x + 1. Процесс деления представлен на рис. 9. Следовательно, m1 = (1111).
Таблица 4
Соответствие синдромов
и векторов ошибок
x6 + x5 + x3 + 1 x3 + x + 1
x6 + x4 + x3
x3 + x2 + x + 1
частное
Вектор ошибки e(x)
Синдром S(x)
x +x +1
0
0
x5 + x3 + x2
1
1
x
x
x2
x2
x3
x+1
x4
x2 + x
x5
x2 + x + 1
x6
x2 +
5
4
x4 + x3 + x2 + 1
x4 + x2 + x
1
x3 + x + 1
x3 + x + 1
0
остаток
Рис. 9. Вычисление входного вектора
18
Выполним алгоритм синдромного декодирования второй последовательности y2(x) = x6 + x + 1 .
Определяем синдром
S2(x) = y2(x)modg(x) = (x6 + x + 1)modg(x) =
6
= x modg(x) + xmodg(x) + 1modg(x) = x2 + 1 + x +1 = x2 + x.
По таблице соответствия синдромов и векторов ошибок выбираем вектор ошибки
e2(x) = x4.
Восстанавливаем кодовое слово
a1(x) = y1(x) + e2(x) = x6 + x4 + x+ 1.
Определяем выходной вектор m2(x). m2(x) = a2(x)/g(x) =
= (x6 + x4 + x +1)/(x3 + x + 1)= x3 + 1. Процесс деления представлен
на рис. 10. Следовательно, m2= (1001).
Так как в кодовых словах a3(x), a4(x), a5(x) и a6(x) при передаче по каналу не было ошибок, то это означает, что для них нет необходимости использовать алгоритм синдромного декодирования,
а можно сразу определять входные векторы (частные от деления кодовых слов на порождающий многочлен). Хотя на практике, алгоритм синдромного декодирования выполняется всегда, так как при
получении последовательности y(x) из канала неизвестно, есть ли
в ней ошибки или нет. Если, например, ошибок нет, то вычисленный синдром последовательности будет равен нулю. Из таблицы соответствия синдромов и векторов ошибок будет выбираться нулевой
вектор ошибки e(x). При сложении этого вектора с y(x) получим кодовое слово a(x) совпадающее с y(x).
Результаты декодирования представлены на рис. 11.
Если в кодере выполнялось систематическое кодирование, то
процесс декодирования такой же, как и при несистематическом коx6 + x4 + x + 1
x3 + x + 1
x6 + x4 + x3
x3 + 1
x3+ x + 1
частное
x3 + x + 1
0
остаток
Рис. 10. Вычисление входного вектора
19
1001001 1000011 1101001 0011101 1101001 0000000
m
Декодер g(x) = x3 + x + 1
1111 1001 1111 0011 1111 0000
a
Рис. 11. Результаты декодирования
дировании. Единственное отличие, что входной вектор можно восстановить непосредственно из кодового слова. Например, если декодер сформировал кодовое слово a1(x) = (x6 + x5 + x4 + x3 +x2 + x + 1),
которому соответствует вектор (1111 111), то при этом, так как k = 4,
то старшие 4 бита и составляют вектор m1= (1111).
3. СОДЕРЖАНИЕ ПОЯСНИТЕЛЬНОЙ ЗАПИСКИ
1. Титульный лист.
2.  Техническое задание к курсовой работе.
3.  Введение.
4.  Входные векторы для кодирования.
5.  Кодирование.
6. Внесение ошибок в выходную последовательность.
7. Таблица соответствия синдромов и векторов ошибок.
8. Декодирование.
9. Заключение.
10.  Список использованной литературы.
БИБЛИОГРАФИЧЕСКИЙ СПИСОК
1. Марковский С. Г., Тюрликов А. М. Элементы теории помехоустойчивого кодирования: учеб. пособие. СПБ.: ГУАП, 2014. 95 с.
20
ПРИЛОЖЕНИЕ
Техническое задание к курсовой работе по дисциплине “Теория
информационных процессов и систем”
Циклические коды
Вариант
 
1
Петров (гр.5131)
1. Задан циклический код с порождающим многочленом g(x) =
= x3 + x + 1. Входной текст символов для кодирования – “щур”.
2. Представить текст в двоичном коде, используя кодировку
ASCII Windows 1251.
3. Выполнить кодирование текста. Разделить входной текст
на 6 групп по 4 бита. Кодирование каждой группы выполнять раздельно. Использовать систематическое кодирование.
4. Внести в закодированный текст, случайным образом, ошибки
в соответствии с табл. П1. В группах, не указанных в таблице, ошибок не возникает.
Таблица П1
Распределение числа ошибок по группам текста
Первая группа
Вторая группа
1 ошибка
1 ошибка
5. Построить таблицу синдромов для векторов ошибок.
6. Выполнить декодирование в режиме исправления ошибок, используя алгоритм синдромного декодирования.
21
СОДЕРЖАНИЕ
1. Основные сведения из теории циклических кодов ......... 1.1 Определение циклического кода ........................... 1.2. Многочлен с коэффициентами из конечного поля.
Операции над многочленами .............................. 1.3. Порождающий многочлен циклического кода........ 1.4. Определение параметров циклического кода
по порождающему многочлену............................. 1.5. Кодирование циклических кодов. ........................ 1.6. Систематическое кодирование циклических кодов. 1.7. Сравнение алгоритмов кодирования
и декодирования циклических кодов.................... 1.8. Синдромное декодирование циклических кодов..... 2. Пример выполнения курсовой работы......................... 2.1. Задание............................................................ 2.2. Построение таблицы остатков от деления
многочленов на порождающий многочлен............. 2.3. Несистематическое кодирование.......................... 2.4. Систематическое кодирование............................. 2.5. Построение таблицы соответствия синдромов
и векторов ошибок............................................. 2.6. Декодирование.................................................. 3. Содержание пояснительной записки........................... Библиографический список........................................... Приложение................................................................ 22
3
3
3
5
6
7
8
10
10
13
13
14
15
16
17
17
20
20
21
Документ
Категория
Без категории
Просмотров
0
Размер файла
1 187 Кб
Теги
markovsky
1/--страниц
Пожаловаться на содержимое документа