Читаем Компьютерные сети. 5-е издание полностью

Рассмотрим канал с изолированными ошибками, возникающими с вероятностью 10-6 на бит. Такое значение может показаться очень небольшим, но для длинного кабельного канала, в котором распознавать ошибки довольно сложно, оно в лучшем случае считается допустимым. Типичные локальные сети характеризуются вероятностью ошибки 10-10. Пусть блок данных состоит из 1000 бит. Для создания кода, исправляющего однократные ошибки в 1000-битном блоке, как видно из представленного выше уравнения (3.1), потребуется 10 контрольных бит. Для 1 Мбит данных это составит 10 000 проверочных бит. Чтобы просто обнаруживать одиночную 1-битовую ошибку, достаточно одного бита четности на блок. На каждые 1000 блоков будет выявляться одна ошибка, и придется переслать повторно еще один блок (1001 бит), чтобы исправить ее. Таким образом, суммарные накладные расходы на обнаружение ошибки и повторную передачу составят всего 2001 бит на 1 Мбит данных против 10 000 бит, необходимых для кода Хэмминга.

Проблема данной схемы заключается в том, что если к блоку добавлять всего один бит четности, то гарантированно распознаваться будет только одна однобитная ошибка в блоке. В случае возникновения последовательности ошибок вероятность обнаружения ошибки будет всего лишь 0,5, что абсолютно неприемлемо. Этот недостаток может быть исправлен, если рассматривать каждый посылаемый блок как прямоугольную матрицу n бит шириной и k бит высотой (принцип ее построения был описан выше). Если вычислить и отправить один бит четности для каждой строки, то гарантированно обнаружить можно будет до k однобитных ошибок, при условии, что в каждой строке будет не большое одной ошибки.

Однако можно сделать кое-что еще, чтобы повысить уровень защиты от последовательностей ошибок — биты четности можно вычислять в порядке, отличном от того, в котором данные отправляются. Этот способ называется чередованием (interleaving). В нашем примере мы будет вычислять бит четности для каждого из n столбцов, но биты данных отправляться будут в виде k строк, в обычном порядке: сверху вниз и слева направо. В последней строке отправим n бит четности. На рис. 3.8 порядок пересылки показан для n = 7 и k = 7.

Рис. 3.8. Чередование битов четности для обнаружения последовательностей ошибок

Чередование представляет собой общую технику преобразования кода, способного обнаруживать (или исправлять) изолированные ошибки, в код, обнаруживающий (или исправляющий) последовательности ошибок. На рис. 3.8, там, где присутствует последовательность ошибок длиной n = 7, мы видим, что ошибочные биты находятся в разных столбцах (последовательность ошибок не означает, что все биты в ней неправильные; это всего лишь подразумевает, что, по меньшей мере, первый и последний биты сбойные. На рис. 3.8 из семи сбойных бит на самом деле изменено значение только четырех). В каждом из n столбцов повреждено будет не больше одного бита, поэтому биты четности этих столбцов помогут выявить ошибку. В данном методе n бит четности в блоках из kn битов данных применяются для обнаружения одной последовательности ошибок длиной n бит или меньше.

Последовательность ошибок длиной n + 1 не будет обнаружена, если будут инвертированы первый и последний биты, а все остальные биты останутся неизменными. Если в блоке при передаче возникнет длинная последовательность ошибок или несколько коротких, вероятность того, что четность любого из n столбцов будет верной (или неверной), равна 0,5, поэтому вероятность необнаружения ошибки будет равна 2-n.

Второй тип кода с обнаружением ошибок, код с использованием контрольной суммы, весьма напоминает группу кодов, применяющих биты четности. Под «контрольной суммой» часто подразумевают любую группу контрольных бит, связанных с сообщением, независимо от способа их вычисления. Группа бит четности — также один из примеров контрольной суммы. Однако существуют и другие, более надежные контрольные суммы, основанные на текущей сумме бит данных в сообщении. Контрольная сумма обычно помещается в конец сообщения, в качестве дополнения функции суммирования. Таким образом, ошибки можно обнаружить путем суммирования всего полученного кодового слова: бит данных и контрольной суммы. Если результат равен нулю, значит, ошибок нет.

Один из примеров контрольной суммы — это 16-битная контрольная сумма, которая используется во всех пакетах протокола IP при пересылке данных в Интернете (Braden и др., 1988). Она представляет собой сумму бит сообщения, поделенного на 16-битные слова. Так как данный метод работает со словами, а не с битами (как при использовании битов четности), то ошибки, при которых четность не меняется, все же изменяют значение суммы, а значит, могут быть обнаружены. Например, если бит младшего разряда в двух разных словах меняется с 0 на 1, то проверка четности этих битов не выявит ошибку. Однако при добавлении к 16-битной контрольной сумме две единицы дадут другой результат, и ошибка станет очевидной.

Перейти на страницу:

Все книги серии Классика computer science

Компьютерные сети. 5-е издание
Компьютерные сети. 5-е издание

Перед вами — очередное, пятое издание самой авторитетной книги по современным сетевым технологиям, написанной признанным экспертом в этой области Эндрю Таненбаумом в соавторстве с профессором Вашингтонского университета Дэвидом Уэзероллом. Первая версия этого классического труда появилась на свет в далеком 1980 году, и с тех пор каждое издание книги неизменно становилось бестселлером и использовалось в качестве базового учебника в ведущих технических вузах. В книге последовательно изложены основные концепции, определяющие современное состояние и тенденции развития компьютерных сетей. Авторы подробнейшим образом объясняют устройство и принципы работы аппаратного и программного обеспечения, рассматривают все аспекты и уровни организации сетей — от физического до уровня прикладных программ. Изложение теоретических принципов дополняется яркими, показательными примерами функционирования Интернета и компьютерных сетей различного типа. Пятое издание полностью переработано с учетом изменений, происшедших в сфере сетевых технологий за последние годы и, в частности, освещает такие аспекты, как беспроводные сети стандарта 802.12 и 802.16, сети 3G, технология RFID, инфраструктура доставки контента CDN, пиринговые сети, потоковое вещание, интернет-телефония и многое другое.

А. Гребенькова , Джеймс Уэзеролл

Технические науки

Похожие книги

102 способа хищения электроэнергии
102 способа хищения электроэнергии

Рассмотрена проблема хищений электроэнергии и снижения коммерческих потерь в электрических сетях потребителей. Приведены законодательно–правовые основы для привлечения к ответственности виновных в хищении электроэнергии. Изложены вопросы определения расчетных параметров средств учета электроэнергии, показаны схемы подключения счетчиков электрической энергии. Описаны расчетные и технологические способы хищения электроэнергии. Обсуждаются организационные и технические мероприятия по обнаружению, предотвращению и устранению хищений.Для работников энергоснабжающих организаций и инспекторского состава органов Ростехнадзора. Материалы книги могут быть использованы руководителями и специалистами энергослужб предприятий (организаций) для правильного определения расчетных параметров средств учета и потерь электроэнергии в электрических сетях.Если потенциальные расхитители электроэнергии надеются найти в книге «полезные советы», они должны отдавать себе отчет, что контролирующие структуры информированы в не меньшей степени и, следовательно, вооружены для эффективной борьбы с противоправной деятельностью.Настоящая книга является переработанным и дополненным изданием выпущенной в 2005 г. книги «101 способ хищения электроэнергии».

Валентин Викторович Красник

Технические науки / Образование и наука
Электроника для начинающих (2-е издание)
Электроника для начинающих (2-е издание)

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

Чарльз Платт

Радиоэлектроника / Технические науки
100 великих чудес инженерной мысли
100 великих чудес инженерной мысли

За два последних столетия научно-технический прогресс совершил ошеломляющий рывок. На что ранее человечество затрачивало века, теперь уходят десятилетия или всего лишь годы. При таких темпах развития науки и техники сегодня удивить мир чем-то особенным очень трудно. Но в прежние времена появление нового творения инженерной мысли зачастую означало преодоление очередного рубежа, решение той или иной крайне актуальной задачи. Человечество «брало очередную высоту», и эта «высота» служила отправной точкой для новых свершений. Довольно много сооружений и изделий, даже утративших утилитарное значение, тем не менее остались в памяти людей как чудеса науки и техники. Новая книга серии «Популярная коллекция «100 великих» рассказывает о чудесах инженерной мысли разных стран и эпох: от изобретений и построек Древнего Востока и Античности до небоскребов в сегодняшних странах Юго-Восточной и Восточной Азии.

Андрей Юрьевич Низовский

История / Технические науки / Образование и наука