[Править] *Коды Рида-Соломона

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

Коды Рида-Соломона являются циклическими кодами над числовым полем отличным от .

Напомним, что существует бесконечное количество конечных полей, и количество элементов в конечном поле всегда равно степени простого числа. Если мы зафиксируем число элементов n = q^k, то найдётся единственное с точностью до изоморфности конечное поле с таким числом элементов, которое обозначается как . Простейшая реализация этого поля — множество многочленов по модулю неприводимого^[3] многочлена p(x) степени k над полем вычетов по модулю q. В случае многочленов с действительными коэффициентами неприводимыми многочленами являются только квадратные многочлены с отрицательным дискриминантом. Поэтому существует только квадратичное расширение действительного поля — комплексные числа. А над конечным полем существуют неприводимые многочлены любой степени. В частности, над многочлен g(z) = z³ + z + 1 неприводим и множество многочленов по модулю g(z) образуют поле из 2³ = 8 элементов.

[Править] Примеры протоколов канала данных [править] hdlc протокол

Здесь мы познакомимся с группой протоколов давно известных, но по-прежнему широко используемых. Все они имеют одного предшественника — SDLC (Synchronous Data Link Control) - протокол управления синхронным каналом, предложенным фирмой IBM в рамках SNA. ISO модифицировала этот протокол и выпустила под названием HDLC — High level Data Link Control. MKTT модифицировала HDLC для X.25 и выпустила под именем LAP - Link Access Procedure. Позднее он был модифицирован в LAPB.

Все эти протоколы построены на одних и тех же принципах. Все используют технику вставки специальных последовательностей битов. Различия между ними незначительные.

\begin{figure}[h!] \centering\includegraphics[clip=true, width=0.88\textwidth]{pictures/frame.eps} \caption{Типовая структура кадра} (fig:frame) \end{figure}

На рис. (fig:frame) показана типовая структура кадра. Поле адреса используется для адресации терминала, если их несколько на линии. Для линий точка-точка это поле используется для различия команды от ответа.

• Поле Control используется для последовательных номеров кадров, подтверждений и других нужд.

• Поле Data может быть сколь угодно большим и используется для передачи данных. Надо только иметь ввиду, что чем оно длиннее тем, больше вероятность повреждения кадра на линии.

• Поле Checksum — это поле используется CRC кодом.

Флаговые последовательности 01111110 используются для разделения кадров и постоянно передаются по незанятой линии в ожидании кадра. Существуют три вида кадров: Information, Supervisory, Unnumbered.

Организация поля Control для этих трех видов кадров показана на рис. (fig:cfield). Как видно из размера поля Seq в окне отправителя может быть до 7 неподтверждённых кадров. Поле Next используется для посылки подтверждения вместе с передаваемым кадром. Подтверждение может быть в форме номера последнего правильно переданного кадра, а может быть в форме первого не переданного кадра. Какой вариант будет использован — это параметр.

\begin{figure}[h!] \centering\includegraphics[clip=true, width=0.88\textwidth]{pictures/cfield.eps} \caption{Cтруктура поля Control} \parbox{0.66\textwidth}{\small (а) Информационный кадр (Information)\\ (б) Управляющий кадр (Supervisory)\\(в) Ненумерованный кадр (Unnumbered) } (fig:cfield) \end{figure}

Разряд P / F использует при работе с группой терминалов. Когда компьютер приглашает терминал к передаче он устанавливает этот разряд в P. Все кадры, посылаемые терминалами имеют здесь P. Если это последний кадр, посылаемый терминалом, то здесь стоит F.

Supervisory кадры имеют четыре типа кадров.

• Тип 0 — уведомление в ожидании следующего кадра (RECEIVE READY). Используется когда нет встречного трафика, чтобы передать уведомление в кадре с данными.

• Тип 1 — негативное уведомление (REJECT) — указывает на ошибку при передаче. Поле Next указывает номер кадра, начиная с которого надо перепослать кадры.

• Тип 2 — RECEIVE NOT READY. Подтверждает все кадры, кроме указанного в Next. Используется, чтобы сообщить источнику кадров об необходимости приостановить передачу в силу каких-то проблем у получателя. После устранения этих проблем получатель шлет RECEIVE REDAY, REJECT или другой надлежащий управляющий кадр.

• Тип 3 — SELECTIVE REJECT — указывает на необходимость перепослать только кадр, указанный в Next. LAPB и SDLC не используют этого типа кадров.

Третий класс кадров — Unnubered. Кадры этого класса иногда используются для целей управления, но чаще для передачи данных при ненадёжной передаче без соединения.

Все протоколы имеют команду DISConnect для указания о разрыве соединения, SNRM и SABM — для установки счётчиков кадров в ноль, сброса соединения в начальное состояние, установки соподчинённости на линии. Команда FRMR — указывает на повреждение управляющего кадра.

1. ^  Идея рассмотрения информации как меры на множестве ещё не до конца исчерпала себя — такой меры ещё не построено. Однако доказано, что с помощью этой аналогии можно доказывать неравенства, например .

2. ^  Матрица называется стохастической, если все её элементы неотрицательны и сумма элементов в каждом столбце равна единице.

3. ^  Многочлен называется неприводимым, если он не разлагается в произведение многочленов меньшей степени.