ПРИМЕНЕНИЕ  ЦИКЛИЧЕСКИХ  КОДОВ

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

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

E-mail:  ad.khantova@yandex.ru

Кузнецов  Михаил  Владимирович

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

РФ,  г.  Самара

Циклические  коды  нашли  свое  применение  при  передаче  информации  по  каналам  связи.  Стандартами  международных  организаций  ITU-T  и  МОС  установлено,  что  вероятность  ошибки  при  телеграфной  связи  не  должна  превышать  3*10^-5  на  знак,  а  при  передаче  данных  –  10^-6  на  единичный  элемент,  бит.  На  практике  допустимая  вероятность  ошибки  при  передаче  данных  может  быть  еще  меньше  –  10^-9.  Однако  возможности  каналов  связи  часто  не  соответствуют  требованиям,  предъявляемым  к  верности  принимаемой  информации.  Каналы  связи,  особенно  проводные  каналы  большой  протяженности  и  радиоканалы,  обеспечивают  вероятность  ошибки  на  уровне  10^-3...10^-4  даже  при  использовании  устройств,  улучшающих  качество  каналов  связи.

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

Помехоустойчивый  код  характеризуется  тройкой  чисел  (  n,  k,  d₀  ),  где  n  –  общее  число  разрядов  в  передаваемом  сообщении,  включая  проверочные,  k  –  число  информационных  разрядов,  d₀  –  минимальное  кодовое  расстояние  между  разрешенными  кодовыми  комбинациями.  Число  обнаруживаемых  и/или  исправляемых  ошибок  связано  с  минимальным  кодовым  расстоянием  соотношениями:

(1)

(2)

(3)

где:  t_о  –  число  обнаруживаемых  ошибок, 

t_и  –  число  исправляемых  ошибок.

Циклические  коды  –  это  подкласс  линейных  кодов,  коды  которого  удовлетворяют  следующим  циклическим  свойствам:  если    -  кодовое  слово  кода,  тогда    полученное  циклическим  сдвигом  элементов  кода  C,  также  являются  кодовым  словом.  Все  циклические  сдвиги  слова  С  образуют  кодовые  слова.

Благодаря  циклическим  свойствам,  циклические  коды  являются  достаточно  легко  реализуемыми  технически.  И  потому  они  нашли  широкое  применение.

Алгоритм  контрольного  суммирования

Алгоритм  контрольного  суммирования  CRC  -Cyclic  redundancy  check-  предназначается  для  контроля  целостности  данных.  Он  широко  используется  в  проводных  и  беспроводных  сетях,  в  устройствах  хранения  данных,  для  проверки  информации  на  подлинность  и  защиты  от  несанкционированного  изменения.  В  универсальной  последовательной  шине  USB  каждый  пакет  имеет  поля  CRC,  позволяющие  обнаруживать  все  однократные  и  двукратные  битовые  ошибки.

CRC  предназначен  не  для  исправления  ошибок,  а  для  их  обнаружения.

Результатом  контрольного  суммирования  CRC  является  остаток  от  деления  многочлена,  соответствующего  исходным  данным,  на  порождающий  многочлен  фиксированной  длины.  Порождающий  многочлен  g(x)  задаёт  конкретный  код  CRC.

На  основе  теории  кодирования,  а  также  многочисленных  исследований  были  найдены  различные  порождающие  многочлены  для  CRC.  Причем  существуют  различные  полиномы  одной  разрядности.

Примеры  использования  наиболее  популярных  порождающих  многочленов  алгоритма  CRC:

CRC-8:  x⁸  +  x⁷  +  x⁶  +  x⁴  +  x²  +  1  –  используется  формой  Dallas  Semiconductor  в  устройствах  низкоскоростной  связи.

CRC-16-IBM  (CRC-16  или  CRC-16-ANSI):  x¹⁶  +  x¹⁵  +  x²  +  1  –  используется  в  ANSI  X3.28,  в  интерфейсах  USB,  ModBus  и  других  линиях  связи. 

CRC-32:  x³²  +  x²⁶  +  x²³  +  x²²  +  x¹⁶  +  x¹²  +  x¹¹  +  x¹⁰  +  x⁸  +  x⁷  +  x⁵  +  x⁴  +  x²  +  x  +  1  –  используется  при  кодировании  видео  и  аудио  сигналов  с  использованием  стандарта  MPEG-2,  при  кодировании  растровых  изображений  в  формате  PNG  и  во  многих  других  случаях.

Отметим,  что  приведенные  порождающие  многочлены  не  являются  единственными  для  CRC-8,  CRC-16,  CRC-32.  Разные  полиномы  для  одних  и  тех  же  CRC  используются  для  разных  технологий  и  в  разных  стандартах.

Коды  Боуза-Чоудхури-Хоквингема  (БЧХ).

Перспективными  с  точки  зрения  аппаратурной  реализации  представляются  коды  БЧХ.  Коды  БЧХ  длины  примерно  до  n=1023  оптимальны  или  близки  к  оптимальным  кодам.  БЧХ-коды  представляют  большой  класс  циклических  кодов  как  с  двоичным,  так  и  с  недвоичным  алфавитами.

Этот  класс  двоичных  кодов  позволяет  исправлять  ошибки.  Причем  метод  построения  этих  кодов  задан  явно.

Коды  БЧХ  отличается  возможностью  построения  кода  с  заранее  определёнными  корректирующими  свойствами,  а  также  предоставляет  разработчику  систем  связи  широкий  выбор  длин  блока  и  скоростей  кода.  БЧХ-коды  могут  исправлять  произвольное  количество  ошибок.  Однако  с  ростом  кратности  ошибки  значительно  возрастает  длина  кода,  что  ведет  к  уменьшению  скорости  передачи  и  усложнению  приемно-передающей  аппаратуры.

БЧХ-код  можно  задать  порождающим  полиномом.  Для  его  нахождения  в  необходимо  заранее  определить  длину  кода  n  и  требуемое  минимальное  расстояние  .

Порождающие  полиномы  для  БЧХ  кодов  можно  конструировать  из  множителей  полинома  .

Общий  список  порождающих  полиномов  для  БЧХ  кодов  дан  Питерсоном  и  Уэлдоном,  которые  дали  таблицы  множителей  полиномов    для  .

БЧХ-коды  уже  нашли  практическое  применение  в  цифровых  системах  записи  звука,  речи  и  музыки.  При  этом  предусматривается  исправление  обнаруженных  ошибок. 

Коды  Рида-Соломона

Частным  случаем  БЧХ-кода  являются  коды  Рида-Соломона.

Коды  Рида-Соломона  –  это  недвоичные  циклические  коды,  предназначенные  для  исправления  пачек  ошибок.

Коды  Рида-Соломона  применяются  в  сфере  цифровых  коммуникаций,  а  также  при  построении  запоминающих  устройств.  Например,  эти  коды  используются  в  помехоустойчивом  кодировании,  в  беспроводных  или  мобильных  коммуникациях,  спутниковых  коммуникациях,  в  цифровом  телевидении,  при  создании  архивов  с  информацией  для  восстановления  в  случае  повреждений.

Благодаря  кодам  Рида-Соломона  можно  прочитать  компакт-диск  с  множеством  царапин.  Для  компакт-диска  избыточность  кода  в  среднем  составляет  примерно  25  %.  Восстанавливаемое  количество  данных  равно  половине  избыточных.  Так,  если  емкость  диска  700  Мб,  то  количество  избыточных  данных  составит  175  Мб.  Таким  образом,  теоретически  можно  восстановить  до  87,5  Мб  из  700  Мб.  При  этом  нам  не  обязательно  знать,  какой  именно  символ  передан  с  ошибкой.

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

1. Алгоритм  контрольного  суммирования  CRC  [Электронный  ресурс]  –  Режим  доступа.  –  URL:  http://all-ht.ru/inf/systems/p_0_13.html 
2. Васильев  К.К.,  Глушков  В.А,  Дормидонтов  А.В.,  Нестеренко  А.Г.;  под  общей  редакцией  Васильева  К.К..  Теория  электрической  связи:  учебное  пособие  –  Ульяновск:  УлГТУ,  2008.  –  452  с.
3. Дмитриев  В.И.  Прикладная  теория  информации.  Учебник  для  студентов  ВУЗов  по  специальности  «Автоматизированные  системы  обработки  информации  и  управления».  –  М.:  Высшая  школа,  1989  –  320  с.
4. Евсеев  А.И  Передача  информации  [Электронный  ресурс]  –  Режим  доступа.  –  URL:  http://peredacha-informacii.ru/ 
5. Курс  «Теория  информации  и  кодирования»  [Электронный  ресурс]  –  Режим  доступа.  –  URL:  http://tik-diit.dp.ua/m256/
6. Никитин  Г.И.  Помехоустойчивые  циклические  коды:  Учебное  пособие  –  СПбГУАП,  2003  –  33  с  [Электронный  ресурс]  –  Режим  доступа.  –  URL:  http://window.edu.ru/catalog/pdf2txt/978/44978/21756?p_page=1 
7. Применение  циклических  кодов  в  каналах  с  независимыми  ошибками  [Электронный  ресурс]  –  Режим  доступа.  –  URL:  http://reftrend.ru/539992.html
8. Сергей  Кондратенко,  Юрий  Новиков  Основы  локальных  сетей  Лекция  10:  Алгоритмы  сети  Ethernet/Fast  Ethernet  [Электронный  ресурс]  –  Режим  доступа.  –  URL:  http://www.intuit.ru/studies/courses/57/57/lecture/1690? 
9. Циклические  коды  [Электронный  ресурс]  –  Режим  доступа.  –  URL:  http://life-prog.ru/1_56225_tsiklicheskie-kodi.html 
10. Циклические  коды  [Электронный  ресурс]  –  Режим  доступа.  –  URL:  http://pmpu.ru/vf4/codes/cyclic