Теория процессов
 Скачать 1.62 Mb.
|
|
(x ≥ mx) ? U 0 := S (x < mx) ? (8.2) Процесс Large имеет следующий вид: Init = (L = V ) a b c ? - 6 @ @ @ @ @ @ @ @ @ I α? y L := L ∪ {y} mn := min(L) β! mn L := L \ {mn} mn := min(L) (y ≤ mn) ? V 0 := L (y > mn) ? (8.3) 8.1.4 Анализ алгоритма разделения множеств Процесс, описываемый выражением (8.1), получается путём • выполнения над процессами (8.2) и (8.3) операций парал- лельной композиции и ограничения, в соответствии с опре- делением (8.1), и • выполнения редукции получившегося процесса. Редуцированный процесс выглядит следующим образом: 238 Aa Ca Bb Ac Cc - 6 ? - mx := max(S) y := mx S := S \ {mx} L := L ∪ {y} mn := min(L) L := L \ {mn} x := mn S := S ∪ {mn} mx := max(S) mn := min(L) ( x < mx y > mn ) ? ( x ≥ mx y ≤ mn ) ? U 0 := S V 0 := L ( x ≥ mx y > mn ) ? U 0 := S ( x < mx y ≤ mn ) ? V 0 := L (8.4) На данной диаграмме видно, что у процесса (8.4) имеются такие состояния (Ac и Ca), • из которых не выходит ни одного перехода (такие состоя- ния называются терминальными), т.е., попав в которые, процесс не может продолжать свою работу, • но попадание в эти состояния не является нормальным за- вершением работы процесса. Попадание процесса в такие состояния называется тупиком, или дедлоком. Процесс (8.1) действительно может попасть в одно из таких состояний, например, при U = {3} и V = {1, 2} 239 (где вес каждого числа совпадает с его значением). Тем не менее, процесс (8.1) обладает следующими свойства- ми: • данный процесс всегда завершает свою работу (т.е. попада- ет в одно из терминальных состояний - Ac, Cc или Ca) • после завершения работы процесса выполняются соотноше- ния S ∪ L = U ∪ V |S| = |U |, |L| = |V | S ≤ L (8.5) Для обоснования этих свойств мы будем использовать функ- цию f (S, L) def = | {(s, l) ∈ S × L | w(s) > w(l)} | Кроме того, при анализе последовательности операторов при- сваивания, выполняемых при переходе от состояния Aa к состо- янию Bb, удобно представлять эту последовательность схемати- чески как последовательность следующих действий: 1. S - y:=max(S) L (перенесение элемента y := max(S) из S в L) 2. L - x:=min(L) S 3. mx := max(S) 4. mn := min(L) Нетрудно установить, что имеют место следующие утвержде- ния. 1. Если в текущий момент времени i • процесс находится в состоянии Aa, и • значения S i , L i переменных S и L в этот момент удо- влетворяют равенству f (S i , L i ) = 0 т.е. имеет место соотношение S i ≤ L i 240 то S i+1 = S i и L i+1 = L i . Кроме того, после выполнения перехода от состояния Aa к состоянию Bb значения пере- менных x, y, mx и mn будут удовлетворять соотношениям y = x = mx ≤ mn и, таким образом, следующим переходом будет переход от состояния Bb к состоянию Cc, т.е. процесс нормально за- вершит свою работу. При этом • значения переменных U 0 и V 0 будут равны S i и L i со- ответственно, • и, следовательно, значения переменных U 0 и V 0 будут удовлетворять требуемым соотношениям. 2. Если в текущий момент времени i • процесс находится в состоянии Aa, и • значения S i , L i переменных S и L в этот момент удо- влетворяют неравенству f (S i , L i ) > 0 то после выполнения перехода от состояния Aa к состоянию Bb (т.е. в момент i + 1) новые значения S i+1 , L i+1 перемен- ных S и L будут удовлетворять неравенству f (S i+1 , L i+1 ) < f (S i , L i ) (8.6) Кроме того, значения переменных x, y, mx, mn в момент i + 1 будут удовлетворять соотношениям y = max(S i ), x = min(L i ) mx = max(S i+1 ), mn = min(L i+1 ) x < y, x ≤ mx, mn ≤ y Отсюда следует, что если в момент i + 1 процесс будет пере- ходить из состояния Bb в одно из терминальных состояний (Ac, Cc или Ca), то это возможно 241 (a) либо если x = mx (b) либо если y = mn В случае (a) имеют место соотношения S i+1 ≤ mx = x ≤ L i откуда, используя x < y и L i+1 ⊆ L i ∪ {y} получаем: S i+1 ≤ L i+1 (8.7) В случае (b) имеют место соотношения S i ≤ y = mn ≤ L i+1 откуда, используя x < y и S i+1 ⊆ S i ∪ {x} получаем соотношение (8.7). Таким образом, во всех возможных случаях попадания в какое-либо терминальное состояние имеет место соотноше- ние S ≤ L Истинность других соотношений, перечисленных в (8.5), усматривается непосредственно. Из первого и второго утверждения следует, что данный про- цесс не может зациклиться, так как зацикливание возможно толь- ко в том случае, когда • процесс бесконечно часто попадает в состояние Aa, и • при каждом попадании в состояние Aa значение функции f на текущих значениях переменных S, T положительно. Невозможность данной ситуации следует из 242 • неравенства (8.6), и • свойства фундированности множества натуральных чисел (т.е. из того, что в данном множестве нет бесконечных убы- вающих цепей). Читателю предлагается самостоятельно • найти необходимые и достаточные условия, которым долж- ны удовлетворять разделяемые множества U и V , чтобы приведённый выше алгоритм завершал свою работу с эти- ми U и V нормально, и • разработать такой алгоритм разделения множеств, кото- рый бы работал корректно на любых разделяемых множе- ствах U и V . 8.2 Вычисление квадрата Предположим, что мы имеем систему “умножитель”, у которой есть • два входных порта с именами In 1 и In 2 , и • один выходной порт с именем Out. Работа умножителя заключается в том, что он периодически • получает на свои входные порты два значения, и • выдаёт на выходном порте их произведение. Поведение умножителя описывается процессом M ul: A B C - - In 1 ? x In 2 ? y ? Out ! (x · y) 243 Используя этот умножитель, мы хотим построить систему “вычислитель квадрата”, поведение которой описывается процес- сом Square_Spec: - In ? z Out ! (z 2 ) Искомую систему мы построим как композицию • вспомогательной системы “дубликатор”, имеющей – входной порт In, и – выходные порты Out 1 и Out 2 поведение которой описывается процессом Dup: a b c - - In ? z Out 1 ! z ? Out 2 ! z т.е. дубликатор копирует свой вход на два выхода, и • умножителя, который будет получать на свои входные пор- ты те значения, которые будет выдавать дубликатор. Процесс Square, соответствующий такой композиции, опре- деляется следующим образом: Square def = def = Dup[pass 1 /Out 1 , pass 2 /Out 2 ] | | M ul[pass 1 /In 1 , pass 2 /In 2 ] ! \ {pass 1 , pass 2 } Потоковый граф процесса Square имеет вид ' & $ % ' & $ % e u u u e e - - Dup M ul In Out pass 1 pass 2 244 Однако процесс Square не соответствует своей специфика- ции Square_Spec. Данный факт нетрудно установить при помо- щи построения графового представления процесса Square, кото- рый, согласно определению операций параллельной композиции, ограничения и переименования, имеет следующий вид: aA bA cA aB bB cB aC bC cC 6 Out ! (x · y) 6 Out ! (x · y) ? Out ! (x · y) In ? z In ? z In ? z ? ? ? @ @ @ @ @ @ @ @ @ R x := z y := z После редукции данного процесса мы получим диаграмму A 1 A 2 A 3 - In ? z x := z y := z Out ! (x · y) - In ? z Out ! (x · y) x := z y := z (8.8) 245 из которой видно, что • процесс Square может последовательно совершить два дей- ствия ввода, не выполняя между ними действия вывода, • а процесс Square_Spec этого сделать не может. Процесс Square соответствует другой спецификации: Square_Spec 0 def = Buf [pass/Out] | | Square_Spec[pass/In] ! \ {pass} где Buf – буфер длины 1, поведение которого изображается диа- граммой - In ? x Out ! x Потоковый граф процесса Square_Spec 0 имеет вид ' & $ % ' & $ % e u u e - Buf Square_Spec In Out pass Графовое представление процесса Square_Spec 0 получается путём • применения операций параллельной композиции, ограни- чения и переименования к процессам Buf и Square_Spec, и • выполнения редукции получившегося процесса. Редуцированный процесс Square_Spec 0 имеет вид a 1 a 2 a 3 - In ? x z := x Out ! (z 2 ) - z := x In ? x Out ! (z 2 ) (8.9) 246 Соответствие процесса Square спецификации Square_Spec 0 можно понимать как истинность соотношения (8.8) ≈ (8.9) Доказать наблюдаемую эквивалентность процессов (8.8) и (8.9) можно, например, при помощи теоремы 34. Для того, чтобы её можно было применить, переименуем переменные в процес- се (8.9) (чтобы множества переменных анализируемых процессов не пересекались). Мы получим процесс, эквивалентный процессу (8.9): a 1 a 2 a 3 - In ? u v := u Out ! (v 2 ) - v := u In ? u Out ! (v 2 ) (8.10) Для доказательства соотношения (8.8) ≈ (8.10) при помощи теоремы 34 мы определим функцию µ : {A 1 , A 2 , A 3 } × {a 1 , a 2 , a 3 } → F m следующим образом: • µ(A i , a j ) def = ⊥, если i 6= j • µ(A 1 , a 1 ) def = > • µ(A 2 , a 2 ) def = (x = y = z = u) • µ(A 3 , a 3 ) def = ( x = y = v z = u ) Детальная проверка истинности соответствующих диаграмм оста- ётся читателю в качестве несложного упражнения. 247 8.3 Сети Петри Одной из математических моделей, предназначенных для описа- ния поведения распределённых систем, являются сети Петри. Сеть Петри – это граф, множество вершин которого делит- ся на два класса: позиции (V ) и переходы (T ). Каждое ребро соединяет позицию с переходом. Каждому переходу t ∈ T соот- ветствует два множества позиций: • in(t) def = {v ∈ V | существует ребро из v в t} • out(t) def = {v ∈ V | существует ребро из t в v} Разметка сети Петри представляет собой отображение ξ ви- да ξ : V → {0, 1, 2, . . .} Функционирование сети Петри заключается в преобразо- вании её разметки, которое происходит в результате срабатыва- ния переходов. Разметка ξ 0 в момент времени 0 предполагается заданной. Если в текущий момент времени i ≥ 0 сеть имела раз- метку ξ i , то сработать в этот момент может любой из переходов t ∈ T , который удовлетворяет условию ∀ v ∈ in(t) ξ i (v) > 0 Если в момент времени i сработал переход t, то разметка ξ i+1 в момент времени i + 1 определяется следующим образом: ∀ v ∈ in(t) ξ i+1 (v) := ξ(v) − 1 ∀ v ∈ out(t) ξ i+1 (v) := ξ(v) + 1 ∀ v ∈ V \ (in(t) ∪ out(t)) ξ i+1 (v) := ξ(v) Каждой сети Петри N можно сопоставить процесс P N , ко- торый моделирует работу этой сети. Компоненты процесса P N имеют следующий вид. • – X P N def = {x v | v ∈ V }, – I P N def = V v∈V (x v = ξ 0 (v)), 248 – S P N def = {s 0 } • Пусть t – произвольный переход сети N , и множества in(t) и out(t) имеют вид {u 1 , . . . , u n } и {v 1 , . . . , v m } соответствен- но. Тогда процесс P N содержит переход из s 0 в s 0 с меткой (x u 1 > 0) ∧ . . . ∧ (x u n > 0) ? x u 1 := x u 1 − 1, . . . , x u n := x u n − 1 x v 1 := x v 1 + 1, . . . , x v m := x v m + 1 8.4 Протоколы передачи данных в ком- пьютерных сетях 8.4.1 Понятие протокола Важным примером процессов с передачей сообщений являются протоколы передачи данных в компьютерных сетях (на- зываемые ниже просто протоколами). Каждый протокол можно рассматривать как совокупность нескольких взаимодействующих процессов, в которую входят • процессы, выполняющие формирование, отправление, при- ём и обработку сообщений (такие процессы называются агентами протокола, а сооб- щения, пересылаемые от одного агента другому, называют- ся кадрами (frame)) • и процесс, являющийся моделью поведения среды, через которую передаются кадры (такую среду обычно называют каналом связи). Проходя через среду, кадры могут искажаться или пропадать (например, в результате воздействия радиопомех). Поэтому каж- дый кадр должен содержать • не только ту информацию, которую один агент желает пе- редать другому, но и 249 • средства, позволяющие получателю этого кадра выяснить, был ли этот кадр искажён в процессе передачи. Ниже мы рассматриваем некоторые методы распознавания искажений в кадрах. Эти методы делятся на два класса: 1. методы, позволяющие • не только установить факт искажения , • но и определить искажённые биты кадра и исправить их (рассматриваются в параграфе 8.4.2), и 2. методы, позволяющие лишь установить факт искажения кадра (рассматриваются в параграфе 8.4.3). 8.4.2 Методы исправления искажений в кад- рах Методы распознавания искажений в кадрах, позволяющие • не только установить факт искажения, но и • определить номера искажённых битов и исправить их используются в таких ситуациях, когда вероятность того, что каждый передаваемый кадр будет искажён при передаче, явля- ется высокой. Например, такая ситуация имеет место в беспро- водной связи. Каждый кадр представляет собой битовую строку. Искаже- ние кадра заключается в инвертировании некоторых битов этого кадра. Если известно максимальное количество битов кадра, кото- рые могут быть инвертированы, то для распознавания инвер- тированных битов и их исправления могут быть использованы методы кодирования с исправлением ошибок, которые со- ставляют одно из направлений теории кодирования. В этом параграфе мы рассматриваем метод кодирования с исправлением ошибок в простейшем случае, когда в кадре мо- жет быть инвертировано не более одного бита. Данный метод 250 называется кодом Хэмминга для исправления одной ошибки (существуют коды Хэмминга для исправления произвольного ко- личества ошибок). Идея данного метода заключается в том, что биты кадра де- лятся на два класса: • информационные биты (содержащие ту информацию, ко- торую отправитель хочет передать получателю), и • контрольные биты (значения которых вычисляются по зна- чениям информационных битов). Пусть кадр f имеет вид (b 1 , . . . , b n ), и • количество информационных битов в нём равно k, • а количество контрольных битов – r, т.е. n = k + r. Поскольку отправитель может размещать свою информацию в k информационных битах, то мы можем считать, что информа- ция, которую отправитель передаёт получателю в кадре f , пред- ставляет собой битовую строку M размера k. Кадр, получаемый из строки M дополнением её контрольными битами, мы будем обозначать знакосочетанием ϕ(M ). Для каждого кадра f обозначим знакосочетанием hf i сово- купность всех кадров, получаемых из f инвертированием не бо- лее одного бита. Очевидно, что количество элементов в hf i равно n + 1. Предположение о том, что в кадре ϕ(M ) при передаче мо- жет произойти искажение не более чем в одном бите, можно пе- реформулировать следующим образом: получатель может полу- чить вместо ϕ(M ) любой кадр из множества hϕ(M )i. Нетрудно видеть, что для того, чтобы получатель для каж- дого M ∈ {0, 1} k мог по произвольному кадру из hϕ(M )i одно- значно восстановить M , необходимо и достаточно выполнение условия ∀ M 1 , M 2 ∈ {0, 1} k M 1 6= M 2 ⇒ hϕ(M 1 )i ∩ hϕ(M 2 )i = ∅ (8.11) 251 т.е. совокупность подмножеств множества {0, 1} n вида {hϕ(M )i | M ∈ {0, 1} k } состоит из непересекающихся подмножеств. Поскольку • количество таких подмножеств = 2 k , и • каждое из этих подмножеств состоит из n + 1 элемента то для выполнения условия (8.11) должно быть верно неравен- ство (n + 1) · 2 k ≤ 2 n которое можно переписать в виде (k + r + 1) ≤ 2 r (8.12) Нетрудно доказать, что при каждом фиксированном k > 0 нера- венство (8.12) (где r предполагается положительным) эквива- лентно неравенству r 0 ≤ r где r 0 зависит от k, и представляет собой нижнюю оценку коли- чества контрольных битов. Число r 0 нетрудно вычислить, когда k имеет вид k = 2 m − m − 1, где m ≥ 1 (8.13) в этом случае (8.12) можно переписать в виде 2 m − m ≤ 2 r − r (8.14) что эквивалентно m ≤ r (т.к. функция 2 x − x монотонна при x ≥ 1). Таким образом, в данном случае нижняя оценка количества контрольных битов r 0 равна m. Оказывается, что данная оценка достижима: существует ме- тод кодирования с исправлением одной ошибки, при котором ко- личество r контрольных битов совпадает с минимально возмож- ным значением r 0 . Ниже мы излагаем метод такого кодирования. 252 Если k имеет вид (8.13), и r = r 0 = m, то n = 2 m − 1, т.е. номера битов кадра (b 1 , . . . , b n ) можно представлять кортежами из {0, 1} m : каждый номер i ∈ {1, . . . , n} представляется двоичной записью числа i, дополненной слева нулями до кортежа длины m. Мы будем полагать, что номера контрольных битов имеют кортежную запись (0 . . . 1 . . . 0) (одна единица, и остальные нули). Значения контрольных битов мы будем вычислять следую- щим образом: для каждого j = 1, . . . , m значение контрольного бита с кортежным номером (0 . . . 1 . . . 0) (единица в j–й позиции) равно сумме по модулю 2 значений информационных битов, кор- тежная запись номеров которых содержит 1 в j–й позиции. При получении кадра (b 1 , . . . , b n ) мы проверяем m равенств X i j =1 b i 1 ...i m = 0 (j = 1, . . . , m) (8.15) (где сумма рассматривается по модулю 2). Возможны следующие случаи. • При передаче этого кадра не было искажений. В этом случае все равенства (8.15) будут верны. • При передаче этого кадра произошло инвертирование кон- трольного бита с кортежным номером (0 . . . 1 . . . 0) (единица в j–й позиции). Нетрудно видеть, что в этом случае среди равенств (8.15) будет неверно только равенство номер j. • При передаче этого кадра произошло инвертирование ин- формационного бита с кортежным номером, содержащим единицы в позициях j 1 , . . ., j l Нетрудно видеть, что в этом случае среди равенств (8.15) будут неверны только равенства с номерами j 1 , . . ., j l Таким образом, во всех случаях мы можем 253 • определить, было ли искажение кадра при передаче, и • если искажение было – то вычислить номер искажённого бита. 8.4.3 Методы обнаружения искажений в кад- рах Другой класс методов анализа искажений в кадрах связан с уста- новлением самого факта искажения. Задача определения номеров искажённых битов имеет высо- кую сложность, и поэтому, если вероятность искажения кадров при передаче невысока (что имеет место при использовании мед- ных или оптоволоконных каналов связи), то более эффективным с точки зрения сложности является повторная посылка искажён- ных кадров: если получатель кадра обнаруживает искажение в этом кадре, он просит отправителя послать этот кадр ещё раз. Для сравнения сложности задач исправления искажений и обнаружения искажений рассмотрим следующий пример. Пусть известно, что в кадре может быть искажено не более одного бита. Если размер кадра n = 1000, то • для исправления такого искажения нужно 10 контрольных битов, • а для обнаружения такого искажения нужен лишь 1 кон- трольный бит, значение которого полагается равным чёт- ности количества единиц в информационных битах. Один из методов кодирования с целью обнаружения искаже- ний заключается в следующем: • кадр делится на k частей, и • в каждой части назначается один контрольный бит, значе- ние которого полагается равным чётности количества еди- ниц в остальных битах этой части. Если при передаче этого кадра биты искажаются равновероят- но и независимо, то для каждой такой части кадра вероятность того, что 254 • эта часть кадра искажена, и • тем не менее, её чётность верна (т.е. мы считаем её неиска- жённой) меньше 1/2, поэтому вероятность необнаружения искажения мень- ше 2 −k Другим методом кодирования с целью обнаружения искаже- ний является полиномиальный код (Cyclic Redundancy Check, CRC). Данный метод основан на рассмотрении битовых строк как многочленов над полем Z 2 = {0, 1}: битовая строка вида (b k , b k−1 , . . . , b 1 , b 0 ) рассматривается как многочлен b k · x k + b k−1 · x k−1 + . . . + b 1 · x + b 0 Пусть необходимо передавать кадры размера m + 1. Каждый такой кадр рассматривается как многочлен M (x) степени ≤ m. Для кодирования этих кадров выбираются • число r < m, и • многочлен G степени r, имеющий вид x r + . . . + 1 Многочлен G называется образующим многочленом. Для каждого кадра M (x) его код T (x) вычисляется следую- щим образом. Многочлен x r · M (x) делится с остатком на G(x): x r · M (x) = G(x) · Q(x) + R(x) где R(x) – остаток, т.е. многочлен степени < r. Кодом кадра M (x) является многочлен T (x) def = G(x) · Q(x) Нетрудно видеть, что размер T (x) больше размера M (x) на r. 255 Обнаружение искажений при передаче кадра T (x) произво- дится путём деления полученного кадра T 0 (x) на G(x): считает- ся, что кадр T (x) был передан без искажений (т.е. полученный кадр T 0 (x) совпадает с T (x)), если T 0 (x) делится без остатка на G(x). Если кадр T (x) был передан без искажений, то исходный кадр M (x) можно восстановить путём представления T (x) в виде сум- мы T (x) = x r · M (x) + R(x) где R(x) состоит из всех мономов в T (x) степени < r. Если кадр T (x) был передан с искажениями, то связь между T (x) и T 0 (x) можно представить в виде соотношения T 0 (x) = T (x) + E(x) где многочлен E(x) называется многочленом искажений, и соответствует битовой строке, каждая компонента которой равна • 1, если соответствующий бит кадра T (x) был искажён, и • 0, иначе. Таким образом, • если T (x) был искажён в одном бите, то E(x) = x i • если T (x) был искажён в двух битах, то E(x) = x i + x j , • и т.д. Из определений T 0 (x) и E(x) следует, что T 0 (x) делится на G(x) без остатка тогда и только тогда, когда E(x) делится на G(x) без остатка. Поэтому искажение, соответствующее много- члену E(x), обнаруживается в том и только том случае, когда остаток от деления E(x) на G(x) не равен нулю. Рассмотрим подробнее вопрос о том, какие виды искажений могут быть обнаружены при помощи данного метода. 1. Однобитные искажения обнаруживаются всегда, т.к. мно- гочлен E(x) = x i не делится на G(x) без остатка. 256 2. Двухбитное искажение может не обнаруживаться в том слу- чае, когда соответствующий многочлен E(x) = x i + x j = x j · (x i−j + 1) делится на G без остатка (мы предполагаем, что i > j): x j · (x i−j + 1) = G(x) · Q(x) (8.16) Из теоремы о единственности разложения на множители многочленов над полем следует, что соотношение (8.16) вле- чёт соотношение x i−j + 1 = G(x) · Q 1 (x) (8.17) Имеет место следующий факт: если G(x) = x 15 + x 14 + 1 (8.18) то для каждого k = 1, . . . , 32768 многочлен x k + 1 не делит- ся на G(x) без остатка. Поэтому образующий многочлен (8.18) позволяет обнаружить двухбитные искажения в кад- рах длины ≤ 32768. 3. Представим многочлен искажений E(x) в виде E(x) = x j · (x k−1 + . . . + 1) (8.19) Число k в этой записи называют размером пакета оши- бок. Очевидно, что k равно размеру подстроки строки ис- кажений (т.е. той строки, которой соответствует многочлен E(x)), ограниченной левым и правым единичными битами. Обозначим знакосочетанием E 1 (x) второй множитель в (8.19). Из теоремы о единственности разложения на множители многочленов над полем следует, что искажение, соответ- ствующее многочлену (8.19), не обнаруживается в том и только том случае, когда E 1 (x) делится без остатка на G(x). Это невозможно, если степень E 1 (x) меньше степени G(x), т.е. если k − 1 < r (или k ≤ r). Таким образом, можно обнаружить такие искажения, раз- мер пакета ошибок в которых ≤ r. 257 4. Если размер пакета ошибок k = r + 1, то многочлен E 1 (x) (см. предыдущий пункт) делится без остатка на G(x) в том и только том случае, когда E 1 (x) = G(x). Вероятность такого совпадения равна 2 −(r−1) Таким образом, если размер пакета ошибок равен r + 1, то вероятность необнаружения такого искажения равна 2 −(r−1) 5. Можно доказать, что если размер пакета ошибок k > r + 1, то вероятность необнаружения такого искажения < 2 −r 6. Если • искажено нечётное количество битов, т.е. E(x) состоит из нечётного количества мономов, и • G = (x + 1) · G 1 то такое искажение обнаруживается, т.к. если бы было вер- но равенство E(x) = G(x) · Q(x) для некоторого многочлена Q(x), то, в частности было бы верно равенство E(1) = G(1) · Q(1) (8.20) чего не может быть, так как левая часть в (8.20) равна 1, а правая – 0. В заключение отметим, что в стандарте IEEE 802 использу- ется образующий многочлен G(x) вида G(x) = x 32 + x 26 + x 23 + x 22 + x 16 + x 12 + x 11 + +x 10 + x 8 + x 7 + x 5 + x 4 + x 2 + x + 1 он обнаруживает искажения, в которых размер пакета ошибок ≤ 32, или искажено нечётное количество битов. 258 8.4.4 Пример протокола Рассмотрим простой пример протокола, который состоит из двух агентов: отправителя и получателя. Задачей протокола явля- ется организация доставки кадров от отправителя получателю через ненадёжный канал связи (который может искажать и те- рять передаваемые кадры). Работа протокола происходит следующим образом. 1. Отправитель получает сообщения от процесса, не входя- щего в протокол, который называется сетевым уровнем (СУ) отправителя. Эти сообщения называются пакета- ми. Задача отправителя заключается в периодическом вы- полнении следующих действий: • получить очередной пакет от своего СУ • сформировать из этого пакета кадр • послать этот кадр в канал связи и включить таймер • если таймер пришлёт сигнал timeout (который озна- чает, что время ожидания подтверждения посланного кадра закончилось, и, видимо, этот кадр до получате- ля не дошёл), то послать этот кадр ещё раз • если придёт подтверждение от получателя, то это озна- чает, что текущий кадр дошёл до него успешно, и мож- но – получать следующий пакет от своего СУ, – формировать из него кадр, – и т.д. Блок-схема, представляющая описанное выше поведение, выглядит следующим образом: 259 |