КОЛИЧЕСТВО  ОБРАЗУЮЩИХ  МАТРИЦ  СИСТЕМАТИЧЕСКОГО  ЦИКЛИЧЕСКОГО  КОДА  (15,11)

Хантова  Анна  Дмитриевна

студент  3  курса,  факультет  информатики  СГАУ  им.  академика  С.П.  Королева,  РФ,  г.  Самара

E -mail:  ad.khantova@yandex.ru

Додонова  Наталья  Леонидовна

научный  руководитель,  доцент,  кафедра  прикладной  математики  СГАУ  им.  академика  С.П.  Королева,  РФ,  г.  Самара

Введение

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

Для  того  чтобы  перенести  информацию  в  пространстве  и  времени,  её  представляют  форме  сообщения.  Сообщение  же  всегда  представляется  в  виде  сигнала.  Построение  сигнала  по  определенным  правилам,  обеспечивающим  соответствие  между  сообщением  и  сигналом,  называют  кодированием.

Если  понимать  кодирование  в  широком  смысле,  то  это  преобразование  сообщения  в  сигнал.  Кодирование  в  узком  смысле  —  это  представление  дискретных  сообщений  определенными  сочетаниями  символов. 

Одним  из  наиболее  важных  кодов  является  циклический  код.  Циклические  коды  применяются  при  записи  на  CD  и  DVD,  при  передаче  аудио  и  видео  информации  ,при  использовании  USB-портов  для  обмена  информацией.

Циклический  код  —  это  линейный  код ,  обладающий  свойством  цикличности.  Иначе  говоря,  каждая  циклическая  перестановка  кодового  слова  также  является  кодовым  словом.  Циклические  коды  легко  реализуются  технически.  Благодаря  этому  они  нашли  широкое  применение.  Также  циклические  коды  незаменимы  при  необходимости  передачи  информации  по  каналам  связи,  в  которых  отсутствует  возможность  повторной  передачи.

Построение  циклического  кода.

В  процессе  кодирования  сообщений  длинная  последовательность  обычно  формируется  из  кодовых  комбинаций,  каждая  из  которых  соответствует  одному  знаку.  Число  символов,  из  которых  составлена  такая  кодовая  комбинация,  называется  длиной  кода. 

Пусть  сообщение  состоит  из  k  =  11  символов.  Построим  код,  обнаруживающий  и  исправляющий  одиночные  ошибки. 

Чтобы  исправить  одиночную  ошибку  в  принятой  комбинации  из  n  разрядов,  сначала  нужно  определить,  какой  именно  из  разрядов  был  искажен.  Чтобы  это  сделать,  каждой  одиночной  ошибке  в  определенном  разряде  должен  соответствовать  свой  опознаватель.  В  циклическом  коде  опознавателями  ошибок  служат  остатки  от  деления  многочленов  ошибок  на  образующий  многочлен  кода.  Поэтому  образующий  многочлен  должен  обеспечить  требуемое  число  различных  остатков  при  делении  векторов  ошибок  с  единицей  в  искаженном  разряде.  Наибольшее  число  остатков  дает  неприводимый  многочлен.  При  степени  многочлена  m=n  -k  он  может  дать  2n-k-1  ненулевых  остатков.  Таким  образом,  выполнение  неравенства  (1)  является  необходимым  условием  исправления  любой  одиночной  ошибки. 

  (1)

Сn  —  это  общее  число  разновидностей  одиночных  ошибок  в  кодовой  комбинации  из  n  символов.  Тогда  степень  образующего  многочлена  кода.

  (2)

Посчитаем  длину  кода  при  k=11  согласно  формуле  (1).

Возьмем  n=14

2^14-11>=15

8>=15 

Это  выражение  не  верно.

Возьмем  n=15

2^15-11>=16

16>=16

Выражение  верно,  значит  n=15,m=15-11=4.

Таким  образом,  мы  получили  код  (15,11).Выберем  образующий  многочлен.  Образующий  многочлен  должен  быть  делителем  многочлена  х  ⁿ+1,  то  есть  в  нашем  случае  х¹⁵+1. 

Многочлен  х  ⁿ+1  можно  представить  в  виде  произведения  всех  неприводимых  многочленов,  степени  которых  являются  делителями  числа  m.

Делители  m=4:  4,2,1.

Для  нахождения  неприводимых  многочленов  нужных  степеней  можно  воспользоваться  таблицей  неприводимых  многочленов:

неприводимые  многочлены  первой  степени:  х+1

неприводимые  многочлены  второй  степени:  х²+х+1

неприводимые  многочлены  четвертой  степени:  х⁴+х+1;  х⁴+х³+1;  х⁴+х³+х²+х+1

х¹⁵+1=(  х+1)(  х²+х+1)(  х⁴+х+1)(  х⁴+х³+1)(  х⁴+х³+х²+х+1)

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

Один  из  сомножителей  степени  m=4  может  быть  принят  за  образующий  многочлен  код. 

Составим  таблицу  остатков  для  трех  неприводимых  многочленов  четвертой  степени

Таблица  1. 

Таблица  остатков  от  деления  на  многочлен

Остатки  получим,  деля  на  g(x)  комбинацию  в  виде  единицы  с  рядом  нулей  и  выписывая  все  промежуточные  остатки.

1)  g₁=  х⁴+х+1

Этому  многочлену  соответствует  кодовая  комбинация  10011

Таким  образом,  многочлен  g₁=  х⁴+х+1образует  15  остатков,  а  значит  может  быть  выбран  в  качестве  образующего.

2)  g₂=  х⁴+х³+1

Таким  образом,  многочлен  g₂=  х⁴+х³+1  образует  15  остатков,  а  значит  может  быть  выбран  в  качестве  образующего.

3)  g₃=  х⁴+х³+х²+х+1

Таким  образом,  многочлен  g₃=  х⁴+х³+х²+х+1

образует  всего  5  остатков,  а  значит  не  может  быть  выбран  в  качестве  образующего.

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

Образующей  называется  матрица,  которая  состоит  k  линейно  независимых  строк.  Каждая  из  этих  строк  является  разрешенной  кодовой  комбинацией.  Все  остальные  разрешенные  комбинации  могут  быть  представлены  в  виде  линейной  комбинации  строк  образующей  матрицы.

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

(3)

Для  составления  образующих  матриц  воспользуемся  результатами  таблицы  1.

Таблица  2.

Образующая  матрица  для  многочлена  g ₁=  х⁴+х+1

Таблица  3.

Образующая  матрица  для  многочлена  g ₂=  х⁴+х³+1

Подсчет  количества  матриц.

Перестановка  строк  (столбцов)  образующей  матрицы  приводит  к  эквивалентному  коду  с  той  же  корректирующей  способностью.

Однако,  поскольку  код  должен  оставаться  систематическим,  мы  можем  переставлять  только  последние  m  столбцов.

То  есть,  надо  посчитать,  сколько  всего  существует  перестановок  из  m  элементов.  Это  можно  сделать  по  формуле

P_n   =m·(m−1)·(m−2)...3·2·1  =  m!  (4)

4!=4*3*2*1=24

Значит,  для  каждого  образующего  многочлена  мы  можем  получить  24  образующих  матриц  систематического  кода.

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

1.Дмитриев  В.И.  Прикладная  теория  информации.  Учебник  для  студентов  ВУЗов  по  специальности  «Автоматизированные  системы  обработки  информации  и  управления».  М.:  Высшая  школа,  1989  —  320  с.

2.Евсеев  А.И  Передача  информации  [Электронный  ресурс]  —  Режим  доступа.  —  URL:  http://peredacha-informacii.ru/   (дата  обращения  30.04.2015).
3.Прохоров  В.С.  ТЕОРИЯ  ИНФОРМАЦИИ  Лекции  [Электронный  ресурс]  —  Режим  доступа.  —  URL:  http://profbeckman.narod.ru/Informat.files/Teorinf.pdf   (дата  обращения  28.04.2015).
4.Фурсов  В.А.  Лекции  по  теории  информации:  Учеб.  пособие  под  редакцией  Н.А.  Кузнецова  Самара:  Изд-во  СГАУ,2006.  —  148  с.