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

Все эти коды добавляют к пересылаемой информации избыточные данные. Кадр состоит из m бит данных (то есть информационных бит) и r избыточных или контрольных бит. В блочном коде r контрольных бит вычисляются как простая функция связанных с ними m бит данных, как если бы для этих m бит данных r контрольных бит находились по огромной таблице соответствий. В систематическом коде m бит данных пересылаются напрямую вместе с контрольными битами и не кодируются перед отправкой. В линейном коде r контрольных бит вычисляются как линейная функция от m бит данных. Очень часто используется функция исключающего ИЛИ (XOR) или суммирование по модулю 2. Это означает, что для кодирования используются такие операции, как умножение матриц или простые логические схемы. Далее в этом разделе, если не указано иное, речь пойдет о линейных систематических блочных кодах.

Пусть полная длина кадра равна n (то есть n = m + r). Будем обозначать это как код (n,m). Набор из n бит, содержащий информационные и контрольные биты, часто называют n-битовым кодовым словом или кодовой комбинацией. Кодовая норма (code rate) или просто норма — это часть кодового слова, несущая неизбыточную информацию, или m/n. На практике значения нормы могут сильно отличаться. Например, для шумного канала обычной нормой считается 1/2, то есть половина полученной информации будет избыточной. В хороших каналах норма близка к единице, и к большим сообщениям добавляются лишь несколько контрольных бит.

Для того чтобы понять, как исправляются ошибки, сначала необходимо познакомиться с самим понятием ошибки. Если рассмотреть два кодовых слова, например 10001001 и 10110001, можно определить число отличающихся в них соответствующих разрядов. В данном примере отличаются 3 бита. Для нахождения этого числа нужно сложить два кодовых слова по модулю 2 (операция «исключающее или») и сосчитать количество единиц в результате, например:

10001001

+

10110001

00111000

Количество бит, которыми отличаются два кодовых слова, называется кодовым расстоянием или расстоянием между кодовыми комбинациями в смысле Хэмминга (Hamming, 1950). Смысл этого числа состоит в том, что если два кодовых слова находятся на кодовом расстоянии d, то для преобразования одного кодового слова в другое понадобится d ошибок в одиночных битах.

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

В большинстве приложений передачи данных все 2т возможных сообщений являются допустимыми, однако благодаря использованию контрольных бит не все 2й возможных кодовых слов используются. В действительности, если контрольных битов г, то допустимыми считаются лишь 2т/2и или 1/2r кодовых слов, а не все возможные 2т. Именно разреженность данных в пространстве кодовых слов позволяет получателю распознавать и исправлять ошибки.

Способности блочного кода по обнаружению и исправлению ошибок зависят от его минимального кодового расстояния. Для надежного обнаружения d ошибок необходим код с минимальным кодовым расстоянием, равным d + 1, поскольку d однобитовых ошибок не смогут изменить одну допустимую комбинацию так, чтобы получилась другая допустимая комбинация. Когда приемник встречает запрещенную кодовую комбинацию, он понимает, что при передаче произошла ошибка. Аналогично, для исправления d ошибок требуется код с минимальным кодовым расстоянием, равным 2d + 1, так как в данном случае даже при d однобитовых ошибках результат окажется ближе к исходному кодовому слову, чем к любому другому и, следовательно, его можно будет однозначно восстановить. Это означает, что исходное кодовое слово можно восстановить уникальным образом, основываясь на предположении, что возникновение большого числа ошибок менее вероятно.

В качестве простейшего примера корректирующего кода рассмотрим код, у которого есть всего четыре допустимые кодовые комбинации:

0000000000, 0000011111, 1111100000 и 1111111111

Этот код имеет расстояние, равное 5, это означает, что он может исправлять двойные ошибки и обнаруживать четверные ошибки. Если приемник получит кодовое слово 0000000111, ожидая только однобитные или двухбитные ошибки, он поймет, что оригинал должен быть равен 0000011111. Однако если тройная ошибка изменит 0000000000 на 0000000111, ошибка будет исправлена неверно. Если ожидать все перечисленные ошибки, то их можно распознавать. Ни одно из полученных кодовых слов не входит в список допустимых. Следовательно, произошла ошибка. Очевидно, что в данном примере невозможно одновременно исправлять двойные ошибки и распознавать четверные, потому что для этого полученное кодовое слово нужно будет интерпретировать двумя разными способами.

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

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

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

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

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

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

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

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

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

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

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

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

Чарльз Платт

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

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

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

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