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

Коды Рида—Соломона широко применяются на практике благодаря хорошим возможностям по исправлению ошибок, особенно последовательных. Они используются в сетях DSL, в кабельных и спутниковых сетях, а также для исправления ошибок на компакт-дисках, дисках DVD и Blu-ray. Поскольку работа идет на базе m-битных символов, однобитные ошибки и m-битные последовательные ошибки обрабатываются одинаково — как одна символьная ошибка. При добавлении 2t избыточных символов код Рида—Соломона способен исправить до t ошибок в любом из переданных символов. Это означает, например, что код (255,233) с 32 избыточными символами исправляет до 16 символьных ошибок. Так как символы могут быть последовательными, а размер их обычно составляет 8 бит, то возможно исправление последовательных ошибок в 128 битах. Ситуация выглядит еще лучше, если модель ошибок связана с удалением данных (например, царапина на компакт-диске, уничтожившая несколько символов). В таком случае возможно исправление до 2t ошибок.

Коды Рида—Соломона часто используют в сочетании с другими кодами, например сверточными. И вот почему. Сверточные коды эффективно обрабатывают изолированные однобитные ошибки, но с последовательностью ошибок они, скорее всего, не справятся, особенно если ошибок в полученном потоке бит слишком много. Добавив внутрь сверточного кода код Рида—Соломона, вы сможете очистить поток бит от последовательностей ошибок. Таким образом, получившийся составной код обеспечит надежную защиту как от одиночных, так и от массовых ошибок.

Наконец, взглянем на код LDPC (Low-Density Parity Check, код с малой плотностью проверок на четность). Коды LDPC — это линейные блочные коды, изобретенные Робертом Галлагером и описанные в его докторской диссертации (Gallagher, 1962). Как и о большинстве других диссертаций, об этой вскоре позабыли. Однако в 1995 году, когда вычислительные мощности сделали огромный скачок вперед, представленный в ней код изобрели заново.

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

Коды LDPC удобно применять для блоков большого размера. Они превосходно справляются с ошибками — лучше, чем на практике удается многим другим кодам (включая те, с которыми мы уже познакомились). По этой причине коды LDPC быстро добавляются в новые протоколы. Они являются частью стандарта цифрового телевидения, сетей Ethernet 10 Гбит/с, сетей, работающих по линиям электропитания, а также последней версии 802.11. Очевидно, что эти коды обязательно будут использоваться и в новых сетях, пока что находящихся на стадии разработки.

3.2.2. Коды с обнаружением ошибок

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

Мы рассмотрим три кода с обнаружением ошибок. Все они относятся к линейным систематическим блочным кодам:

1.    Код с проверкой на четность.

2.    Код с контрольными суммами.

3.    Циклический избыточный код.

Для того чтобы понять, в каких ситуациях обнаружение ошибок может быть эффективнее исправления, возьмем первый из перечисленных кодов. К отправляемым данным присоединяется единственный бит четности (parity bit), который выбирается так, чтобы число единичных битов в кодовом слове было четным (или нечетным). Это эквивалентно вычислению бита четности в виде суммы по модулю 2 для битов данных (или применению операции исключающего ИЛИ). Например, если отправляется кодовое слово 1011010 и число единиц должно быть четным, то в конце добавляется ноль, и последовательность превращается в 10110100. Если же число единиц должно быть нечетным, то последовательность устанавливается такая: 10110101. Кодовое расстояние кода с единственным битом четности равно двум, так как любая однобитная ошибка меняет четность кодового слова на неправильную. Это означает, что данный код позволяет распознавать однобитные ошибки.

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

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

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

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

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

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

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

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

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

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

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

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

Чарльз Платт

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

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

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

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