Материалы Международной научно- технической конференции «Вторые ержановские чтения». Актобе. 2007. С. 473-477
Вид материала | Документы |
СодержаниеРегистр сдвига Вектор сообщения Логическая схема для реализации деления многочленов |
- Итоги 34 Международной научно-технической конференции молодёжи ОАО «Запорожсталь» Вноябре, 258.19kb.
- Программа 4-й Международной студенческой научно-технической конференции Конференция, 803.12kb.
- Программа международной научно-технической конференции, посвященной 100-летию со дня, 190.07kb.
- Программа и пригласительный билет IX международной научно-технической конференции проблемы, 115.59kb.
- Доклад на Международной конференции "Роль международной научно-технической кооперации, 199.79kb.
- Уважаемые коллеги!, 64.69kb.
- Молодежная научно техническая конференция «Будущее технической науки» X international, 58.23kb.
- Рекомендации IV международной научно-технической конференции «промышленная безопасность, 113.46kb.
- Актуальные социально-экономические и правовые аспекты устойчивого развития региона., 2089.17kb.
- Iii чтения, посвященные памяти Р. Л. Яворского (1925 – 1995), 185.65kb.
// Материалы Международной научно- технической конференции «Вторые ержановские чтения». – Актобе. – 2007. – С.473-477
УДК 681.3.07
А.А. Садыков, Н.Н. Ташатов
кодирование в систематической форме линейных
циклических кодов
Евразийский национальный университет им. Л.Н. Гумилева, г. Астана
Кодирование в систематической форме.
Используем некоторые алгебраические свойства циклического кода для развития процедуры систематического кодирования, которая была рассмотрена в [4]. В этой статье было введено понятие систематическая форма и рассмотрено уменьшение сложности, которое делает эту форму кодирования более привлекательной.
Запишем вектор сообщения в форме многочлена степени k – 1 следующим образом:

Символы сообщения в систематической форме используются как часть кодового слова. Сдвинем символы сообщения в k крайних правых разряда кодового слова, а затем прибавим биты четности, разместив их в крайние левые п – k разряды. Такой сдвиг не вызывает переполнения п–разрядного регистра сдвига. Таким образом, осуществляем алгебраическую манипуляцию многочлена сообщения, и он оказывается сдвинутым вправо на п - k позиций. Умножив m(X) на


Регистр сдвига
0 n-1
0 | … | 0 | 0 | ![]() | ![]() | ![]() ![]() | … | ![]() ![]() |

Вектор сообщения
Рисунок 1 – Сдвиг многочлена в регистре сдвига с обратными
связями длины п на p = п – k позиций
Разделив уравнение (2) на g(X), получим:

Остаток р(Х) записывается следующим образом:

или


Прибавим р(Х) к обеим частям уравнения (3) и используя сложение по модулю 2, получим:

Из (6) вытекает алгоритм кодирования систематического циклического (n, k) – кода:
- Вектор сообщения в форме многочлена m(X), степени k – 1, умножается на
;
- Находится остаток р(Х) от деления
на g(X);
- Многочлен р(Х) заносится в п – k левых разрядов регистра сдвигов (см. рис. 1)
Левая часть уравнения (6) является действительным многочленом кодового слова, так как это многочлен степени не превышающая п - 1, который при делении на g(X) дает нулевой остаток. Это кодовое слово будет выглядеть следующим образом:


Многочлен кодового слова соответствует вектору кода

Циклический код в систематической форме.
Пусть дан вектор сообщения m = 1 0 0 1 1. Из набора кодовых слов (7, 4) с помощью порождающего многочлена g(X) = 1 + X + X3 надо получить систематическое кодовое слово.


Разделим


Используя уравнение (6), получаем следующее:


Логическая схема для реализации деления многочленов.
Важнейшее преимущество циклических кодов по сравнению с другими методами кодирования заключается в простоте их технической реализации. Использование в схемах кодеров и декодеров регистров сдвига с обратными связями, позволяет просто и достаточно эффективно защищать от ошибок информационные массивы большой длины. Процедура деления многочленов является основной в кодерах и декодерах циклических кодов. Пусть даны два многочлена V(X) и g(X), где


причем т > р. Схема деления, приведенная на рисунке 2, выполняет деление многочлена V(X) на g(X), определяя частное и остаток от деления


Рисунок 2 – Логическая схема для реализации деления многочленов
Разряды регистра в исходном состоянии содержат нули. Коэффициенты V(X) поступают и продвигаются по регистру сдвига по одному за такт, начиная с коэффициентов более высокого порядка. Частное после р-го сдвига на выходе равно



Рассмотрим схему деления многочленов, используя рисунок 2. Пусть



Необходимый регистр сдвига с обратной связью показан на рисунке 3.

Рисунок 3 – Схема деления для примера
Пусть первоначально регистр содержит нули. Схема выполнит следующие шаги.
-
Входная очередь
Номер сдвига
Содержимое регистра
Выход и обратная связь
0001011
0
000
-
000101
1
100
0
00010
2
110
0
0001
3
011
0
000
4
011
1
00
5
111
1
0
6
101
1
-
7
100
1
После четвертого сдвига коэффициенты частного




Прямое деление многочленов дает тот же результат.
СПИСОК ЛИТЕРАТУРЫ
- Скляр Б. Цифровая связь. Теоретические основы и практическое применение. Изд. 2-е, испр.: Пер. с англ. – Издательский дом «Вильямс», 2004. – 1104 с. ил.
- Вернер М. Основы кодирования. Москва: Техносфера, 2004. – 288 с.
- Березюк Н.Т., Андрущенко А.Г., Мощицкий С.С. Кодирование информации (двоичные коды). Харьков, издательское объединение «Вища школа», 1978, 252 с.
- Ташатов Н.Н. Систематические линейные блочные коды с контролем четности. // Вестник ПГУ им. С.М. Торайгырова. – 2007. – № (в печати).