Реферат – Кодирование

20 Февраль 2014 →

Министерство образования и науки российской федерации

Обнинский институт атомной энергетики – филиал

федерального государственного автономного образовательного учреждения

высшего профессионального образования

«Национальный исследовательский ядерный университет «мифи»

(ИАТЭ НИЯУ МИФИ)

Реферат на тему

«Циклические коды»

Выполнил:

студент гр. ВТ2-С10

Карпенко С.В.

Проверил:

Мышев А.В.

Обнинск 2013

Оглавление

1. Циклические коды_____________________________________________ 32. Матричное задание кодов_______________________________________ 7

3. Литература___________________________________________________ 10

Введение

Кодирование информации в данный момент является важным аспектом в IT сфере деятельности. Данная проблема сопряжена как с необходимостью защиты информации, так и с проблемами роста потребления ресурсов, как известно, чем быстрее и лучше информация может быть зашифрована/расшифрована, тем больший интерес данная, условно говоря "кодировка" будет вызывать у конечного пользователя. Исходя из этого я выбрал наиболее интересную для себя систему кодировки, называемую, как циклическое кодирование.

Циклические коды

Циклическим кодом называется линейный блоковый (n,k)-код, который характеризуется свойством цикличности, т.е. сдвиг влево на один шаг любого разрешенного кодового слова дает также разрешенное кодовое слово, принадлежащее этому же коду и у которого, множество кодовых слов представляется совокупностью многочленов степени (n-1) и менее, делящихся на некоторый многочлен g(x) степени r = n-k, являющийся сомножителем двучлена xn+1.

Многочлен g(x) называется порождающим.

Как следует из определения, в циклическом коде кодовые слова представляются в виде многочленов где n - длина кода;

- коэффициенты из поля GF(q).

Если код построен над полем GF(2), то коэффициенты принимают значения 0 или 1 и код называется двоичным. Пример. Если кодовое слово циклического кода то соответствующий ему многочлен

Например, если код построен над полем GF(q)=GF(23), которое является расширением GF(2) по модулю неприводимого многочлена f(z)=z3+z+1, а элементы этого поля имеют вид, представленный в таблице 1,

Таблица 1

0

000

0

3

011

Z+1

0

001

1

4

110

Z2+Z

1

010

Z

5

111

Z2+Z+1

2

100

Z2

6

101

Z2+1

то коэффициенты принимают значения элементов этого поля и поэтому они сами отображаются в виде многочленов следующего вида где m - степень многочлена, по которому получено расширение поля GF(2); ai - коэффициенты, принимающие значение элементов GF(2), т.е. 0 и 1. Такой код называется q-ным.

Длина циклического кода называется примитивной и сам код называется примитивным, если его длина n=qm-1 на GF(q).

Если длина кода меньше длины примитивного кода, то код называется укороченным или не примитивным.

Как следует из определения общее свойство кодовых слов циклического кода - это их делимость без остатка на некоторый многочлен g(x), называемый порождающим.

Результатом деления двучлена xn+1 на многочлен g(x) является проверочный многочлен h(x).

При декодировании циклических кодов используются многочлен ошибок e(x) и синдромный многочлен S(x).

Многочлен ошибок степени не более (n-1) определяется из выражения где - многочлены, отображающие соответственно принятое (с ошибкой) и переданное кодовые слова.

Ненулевые коэффициенты в е(x) занимают позиции, которые соответствуют ошибкам.

Пример.

Синдромный многочлен, используемый при декодировании циклического кода, определяется как остаток от деления принятого кодового слова на порождающий многочлен, т.е.

или

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

Таблица 2

(x)

S(x)

1

Rg(x)[1]

X

Rg(x)[x]

X2

Rg(x)[x2]

X+1

Rg(x)[x+1]

X2+1

Rg(x)[x2+1]

В процессе декодирования по принятому кодовому слову вычисляется синдром, затем в таблице находится соответствующий многочлен е(х), суммирование которого с принятым кодовым словом дает исправленное кодовое слово, т.е. Перечисленные многочлены можно складывать, умножать и делить, используя известные правила алгебры, но с приведением результата по mod 2, а затем по mod xn+1, если степень результата превышает степень (n-1).

Примеры.

Допустим, что длина кода n=7, то результат приводим по mod x7+1.

При построении и декодировании циклических кодов в результате деления многочленов обычно необходимо иметь не частное, а остаток от деления. Поэтому рекомендуется более простой способ деления, используя не многочлены, а только его коэффициенты (вариант 2 в примере).

Пример. 1.2.

Матричное задание кодов

Циклический код может быть задан порождающей и проверочной матрицами. Для их построения достаточно знать порождающий g(x) и проверочный h(x) многочлены. Для несистематического циклического кода матрицы строятся циклическим сдвигом порождающего и проверочного многочленов, т.е. путем их умножения на x и

При построении матрицы H(n,k) старший коэффициент многочлена h(x) располагается справа.

Пример. Для циклического (7,4)-кода с порождающим многочленом g(x)=x3+x+1 матрицы G(n,k) и H(n,k) имеют вид: где

Для систематического циклического кода матрица G(n,k) определяется из выражения где Ik - единичная матрица; Rk,r - прямоугольная матрица. Строки матрицы Rk,r определяются из выражений или где ai(x) - значение i-той строки матрицы Ik; i - номер строки матрицы Rk,r.

Пример. Матрица G(n,k) для (7,4)-кода на основе порождающего многочлена g(x)=x3+x+1, строится в следующей последовательности или

Определяется R4,3, используя так как

Аналогичным способом определяется

В результате получаем или

Используя выражение получим тот же результат. Строки матрицы G(n,k) можно определить непосредственно из выражения где

Проверочная матрица в систематическом виде строится на основе матрицы G(n,k), а именно: где Ir - единичная матрица; - матрица из G(n,k) в транспонированном виде.

Пример. Для (7,4)-кода матрица H(n,k) будет иметь вид:

Одна из основных задач, стоящих перед разработчиками устройств защиты от ошибок при передаче дискретных сообщений по каналам связи является выбор порождающего многочлена g(x) для построения циклического кода, обеспечивающего требуемое минимальное кодовое расстояние для гарантийного обнаружения и исправления t-кратных ошибок.

Существуют специальные таблицы по выбору g(x) в зависимости от предъявляемых требований к корректирующим возможностям кода. Однако у каждого циклического кода имеются свои особенности формирования g(x). Поэтому при изучении конкретных циклических кодов будут рассматриваться соответствующие способы построения g(x).

Заключение

В заключении хочу сказать, что поиск оптимальных алгоритмов кодирования для определенной задачи, всегда будет актуальной задачей. Самым оптимальным алгоритмов можно считать тот, который сжимает исходный входной файл/поток максимально сильно и максимально быстро, так же не стоит забывать о ресурсах компьютера, которые при этом расходуются, выше описанный "оптимальный" код может расходовать недопустимо много ресурсов, поэтому необходимо помнить, что на ряду с проблемой кодирования стоит проблема оптимизации этих алгоритмов.

ЛИТЕРАТУРА

Лидовский В.И. Теория информации. - М., «Высшая школа», 2002г. – 120с.

Метрология и радиоизмерения в телекоммуникационных системах. Учебник для ВУЗов. / В.И.Нефедов, В.И.Халкин, Е.В.Федоров и др. – М.: Высшая школа, 2001 г. – 383с.

Цапенко М.П. Измерительные информационные системы. - . – М.: Энергоатом издат, 2005. - 440с.

Зюко А.Г. , Кловский Д.Д., Назаров М.В., Финк Л.М. Теория передачи сигналов. М: Радио и связь, 2001 г. –368 с.

Б. Скляр. Цифровая связь. Теоретические основы и практическое применение. Изд. 2-е, испр.: Пер. с англ. – М.: Издательский дом «Вильямс», 2003 г. – 1104 с.




See also:
Для студента
Похожие записи

Комментарии закрыты.