Министерствообразования РФ
ПермскийГосударственный Технический Университет
Кафедра автоматизациии телемеханики
КОНТРОЛЬНАЯРАБОТА ПО ПРЕДМЕТУ:
СЕТИ ЭВМ
Выполнила студентка
Суханова С. А.
Гр. УК-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, являющийся сомножителем двучлена xn+1, и их корней.Кроме того, вводятся понятия полинома исходного сообщения. Для этих полиномов,представляющих собой, по существу, альтернативную запись чисел в двоичнойсистеме счисления, определяются операции сложения, умножения и деления,необходимые для организации кодирования и декодирования сообщения. Все этиоперации выполняются по модулю 2.
Кодовые словапредставляются в виде многочленов:
/>
/>
1.2 Основныепараметры циклических кодов
Длина кода — n; Длина информационной последовательности — k; Длина проверочнойпоследовательности — r=n-k; Кодовое расстояние кода — d0; Скоростькода — R=k/n; Избыточность кода — R; Вероятность обнаружения ошибки(искажения) — РОО; Вероятность не обнаружения ошибки (искажения) — РНО./> — коэффициентыиз поля GF(q).
1.3Основные понятия и определения
Кодовоерасстояние между двумя кодовыми словами (расстояние Хэмминга) — это числопозиций, в которых они отличаются друг от друга. />Кодовоерасстояние кода — это наименьшее расстояние Хэмминга между различными парамикодовых слов. />Основные зависимости между кратностьюобнаруживаемых ошибок t0, исправляемых ошибок tu,исправлением стираний tc и кодовым расстоянием d0кода:
/>/>
Стираниемназывается «потеря» значения передаваемого символа в некоторойпозиции кодового слова, которая известна. />Код, в котором каждоекодовое слово начинается с информационных символов и заканчивается проверочнымисимволами, называется систематическим. Если код построен над полем GF(2), токоэффициенты принимают значения 0 или 1 и код называется двоичным. Длинациклического кода называется примитивной и сам код называется примитивным, еслиего длина n=qm-1 над GF(q). Если длина кода меньше длиныпримитивного кода, то код называется укороченным или непримитивным. />Общее свойство кодовых слов циклического кода — это их делимостьбез остатка на некоторый многочлен g(x), называемый порождающим. />Результатомделения двучлена xn+1 на многочлен g(x) является проверочныймногочлен h(x). />При декодировании циклических кодовиспользуются многочлен ошибок e(x) и синдромный многочлен S(x). Многочленошибок степени не более (n-1) определяется из выражения
/>
где /> — многочлены,отображающие соответственно принятое (с ошибкой) и переданное кодовые слова. Ненулевыекоэффициенты в е(x) занимают позиции, которые соответствуют ошибкам. />Синдромный многочлен, используемый при декодировании циклическогокода, определяется как остаток от деления принятого кодового слова напорождающий многочлен, т.е.
/>
или
/>
Следовательно,синдромный многочлен зависит непосредственно от многочлена ошибок е(х)./> Это положение используется при построении таблицы синдромов,применяемой в процессе декодирования. Эта таблица содержит список многочленовошибок и список соответствующих синдромов, определяемых из выражения />(см. таблицу4).
Таблица 4 (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]
/>
В процесседекодирования по принятому кодовому слову вычисляется синдром, затем в таблиценаходится соответствующий многочлен е(х), суммирование которого с принятымкодовым словом дает исправленное кодовое слово, т.е.
/>
Перечисленныемногочлены />можноскладывать, умножать и делить, используя известные правила алгебры, но сприведением результата по модулю 2, а затем по модулю xn+1, еслистепень результата превышает степень (n-1). Примеры.
/> />
Допустим, что длина кодаn=7, то результат приводим по модулю x7+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 00 0
(1+х+х*3)х х+х*2+х*4 0 11 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+х*60 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г.