О некоторых свойствах линейных циклических кодов. 
Проблемы передачи информации

Министерство образования РФ Пермский Государственный Технический Университет Кафедра автоматизации и телемеханики

КОНТРОЛЬНАЯ РАБОТА ПО ПРЕДМЕТУ:

СЕТИ ЭВМ

Выполнила студентка Суханова С. А.

Гр. УК-04з, МТФ Проверил преподаватель Кузнецов И. И.

2007 г.

1. Циклические коды. Основные понятия и определения. Построить порождающую матрицу циклического кода с g (х) = 1+х+х*3

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

1.2 Основные параметры циклических кодов

1.3 Основные понятия и определения

1.4 Построить порождающую матрицу циклического кода с g (х) = 1+х+х*3

2. Понятие открытой системы

2.1 Модель OSI

2.2 Понятие «открытой системы»

1. Циклические коды. Основные понятия и определения. Построить порождающую матрицу циклического кода с g(х) = 1+х+х*3

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

Циклические коды — это целое семейство помехоустойчивых кодов, включающее в себя в качестве одной из разновидностей кодов Хэмминга, но в целом обеспечивающее большую гибкость с точки зрения возможности реализации кодов с необходимой способностью обнаружения и исправления ошибок, определяемой параметром d0, по сравнению с кодами Хэмминга (для которых d0=3 или d0=4). Одним из классов циклических кодов, способность исправлять многократные ошибки, являются коды БЧХ. Широкое использование циклических кодов на практике обусловлено также простотой реализации соответствующих кодеров и декодеров. Основные свойства и само название циклических кодов связаны с тем, что все разрешенные комбинации бит в передаваемом сообщении (кодовые слова) могут быть получены путем операции циклического сдвига некоторого исходного кодового слова:

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

Кодовые слова представляются в виде многочленов:

1.2 Основные параметры циклических кодов

Длина кода — n; Длина информационной последовательности — k; Длина проверочной последовательности — r=n-k; Кодовое расстояние кода — d₀; Скорость кода — R=k/n; Избыточность кода — R?; Вероятность обнаружения ошибки (искажения) — Р_ОО; Вероятность не обнаружения ошибки (искажения) — Р_НО.- коэффициенты из поля GF (q).

1.3 Основные понятия и определения

Кодовое расстояние между двумя кодовыми словами (расстояние Хэмминга) — это число позиций, в которых они отличаются друг от друга. Кодовое расстояние кода — это наименьшее расстояние Хэмминга между различными парами кодовых слов. Основные зависимости между кратностью обнаруживаемых ошибок t₀, исправляемых ошибок t_u, исправлением стираний t_c и кодовым расстоянием d₀кода:

Стиранием называется «потеря» значения передаваемого символа в некоторой позиции кодового слова, которая известна. Код, в котором каждое кодовое слово начинается с информационных символов и заканчивается проверочными символами, называется систематическим. Если код построен над полем GF (2), то коэффициенты принимают значения 0 или 1 и код называется двоичным. Длина циклического кода называется примитивной и сам код называется примитивным, если его длина n=q^m-1 над GF (q). Если длина кода меньше длины примитивного кода, то код называется укороченным или непримитивным. Общее свойство кодовых слов циклического кода — это их делимость без остатка на некоторый многочлен g (x), называемый порождающим. Результатом деления двучлена xⁿ+1 на многочлен g (x) является проверочный многочлен h (x). При декодировании циклических кодов используются многочлен ошибок e (x) и синдромный многочлен S (x). Многочлен ошибок степени не более (n-1) определяется из выражения

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

или

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

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

Перечисленные многочлены можно складывать, умножать и делить, используя известные правила алгебры, но с приведением результата по модулю 2, а затем по модулю xⁿ+1, если степень результата превышает степень (n-1). Примеры.

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

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

Пример.

1. 2.

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

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

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

1.4. Построить порождающую матрицу циклического кода с g(х) = 1+х+х*3

Для циклического (7,4)-кода с порождающим многочленом g (x)=1+х+х*3 матрицы G_{(n, k)} имеет вид:

1+х+х*3 1+х+х*3 1 1 0 1 0 0 0

(1+х+х*3)х х+х*2+х*4 0 1 1 0 1 0 0

G (7,4) = (1+х+х*3)х*2 = х*2+х*3+х*5 = 0 0 1 1 0 1 0

(1+х+х*3)х*3 х*3 +х*4+х*6 0 0 0 1 1 0 1

2. Понятие открытой системы

2.1 Модель OSI

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

В начале 80-х годов ряд международных организаций по стандартизации — ISO (международная организация по стандартизации (International Organization for Standardization, часто называемое также International Standards Organization) представляет собой ассоциацию ведущих национальных организаций по стандартизации разных стран; главным достижением ISO явилась модель взаимодействия открытых систем OSI, которая в настоящее время является концептуальной основой стандартизации в области вычислительных сетей; в соответствии с моделью OSI этой организацией был разработан стандартный стек коммуникационных протоколов OSI), ITU-T (Telecommunication Standardization Sector) — сектор телекоммуникационной стандартизации; основу деятельности ITU-T составляет разработка международных стандартов в области телефонии, телематических служб (электронной почты, факсимильной связи, телетекста, телекса и т. д.), передачи данных, аудио и видеосигналов.

За годы своей деятельности ITU-T выпустил огромное число рекомендаций-стандартов), и некоторые другие разработали модель OSI, которая сыграла значительную роль в развитии сетей. Модель OSI определяет различные уровни взаимодействия систем, дает им стандартные имена и указывает, какие функции должен выполнять каждый уровень. Модель OSI была разработана на основании большого опыта, полученного при создании компьютерных сетей, в основном глобальных, в 70-е годы. Полное описание этих моделей занимает более 1000 страниц текста.

В модели OSI (рис. 1) средства взаимодействия делятся на семь уровней: прикладной, представительный, сеансовый, транспортный, сетевой, канальный и физический. Каждый уровень имеет дело с одним определенным аспектом взаимодействия сетевых устройств.

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

2.2 Понятие «открытая система»

Модель OSI описывает взаимосвязи открытых систем. Что же такое открытая система?

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

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

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

Для реальных систем полная открытость является недостижимым идеалом. Как правило, даже в системах, называемых открытыми, этому определению соответствуют лишь некоторые части, поддерживающие внешние интерфейсы. Например, открытость семейства операционных систем Unix заключается, кроме всего прочего, в наличии стандартизованного программного интерфейса между ядром и приложениями, что позволяет легко переносить приложения из среды одной версии Unix в среду другой версии. Еще одним примером частичной открытости является применение в достаточно закрытой операционной системе Novell NetWare открытого интерфейса Open Driver Interface (ODI) для включения в систему драйверов сетевых адаптеров независимых производителей. Чем больше открытых спецификаций использовано при разработке системы, тем более открытой она является.

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

Если две сети построены с соблюдением принципов открытости, то это дает следующие преимущества:

· Возможность построения сети из аппаратных и программных средств различных производителей, придерживающихся одного и того же стандарта;

· Возможность безболезненной замены отдельных компонентов сети другими, более совершенными, что позволяет сети развиваться с минимальными затратами;

· Возможность легкого сопряжения одной сети с другой;

· Простота освоения и обслуживания сети;

Ярким примером открытой системы является международная сеть Internet. Эта сеть развивалась в полном соответствии с требованиями, предъявляемыми к открытым системам. В разработке ее стандартов принимали участие тысячи специалистов-пользователей этой сети из различных университетов, научных организаций и фирм-производителей вычислительной аппаратуры и программного обеспечения, работающих в разных странах. Само название стандартов, определяющих работу сети Internet-Request For Comments (RFS), что можно перевести как «запрос на комментарии», — показывает гласный и открытый характер принимаемых стандартов. В результате сеть Internet сумела объединить в себе разнообразное оборудование и программное обеспечение числа сетей, разбросанных по всему миру.

1. Олифер В. Г., Олифер Н. А. «Компьютерные сети» 2002 г.

2. Гоппа В. Я. «Рациональные представления кодов. Проблемы передачи информации» 1971 г.

3. Шпарлинский И. Е. «О некоторых свойствах линейных циклических кодов. Проблемы передачи информации» 1983 г.