Введение в локальные сети
Метод управления обменом CSMA/CD
В данной главе мы рассмотрим подробнее два основных алгоритма, применяемых в самой распространенной на сегодняшний день сети Ethernet/ Fast Ethernet. Речь идет о методе управления обменом (методе доступа) CSMA/CD и о методе вычисления циклической контрольной суммы пакета CRC.
Эти же самые алгоритмы используются во многих других локальных сетях. Например, метод доступа CSMA/CD применяется в сетях IBM PC Network, AT&T Starlan, Corvus Omninet, PC Net, G-Net и др. Что касается алгоритма вычисления циклической контрольной суммы CRC, то он стал фактическим стандартом для любых локальных сетей. Так что все, о чем говорится в данной главе, относится ко многим локальным сетям.
Как уже говорилось в главе 3, метод управления обменом CSMA/CD (Carrier-Sense
Multiple Access with Collision Detection - множественный доступ с контролем
несущей и обнаружением коллизий) относится к децентрализованным случайным
(точнее, квазислучайным) методам. Он используется как в обычных сетях
типа Ethernet, так и в высокоскоростных сетях типа Fast Ethernet. Поскольку
характеристики и области применения этих популярных на практике сетей
связаны именно с особенностями используемого метода доступа, его стоит
рассмотреть более подробно.
Сначала чуть подробнее о названии метода. В ранней сети типа Alohanet,
работавшей с 1970 г. на Гавайских островах, использовался радиоканал и
установленный на спутнике ретранслятор (отсюда слово «несущая» в названии
метода), а также сравнительно простой метод доступа CSMA (без обнаружения
коллизий). В сетях типа Ethernet и Fast Ethernet в качестве несущей выступает
синхросигнал, «подмешиваемый» к передаваемым данным таким образом, чтобы
обеспечить надежную синхронизацию на приемном конце за счет организации
(при необходимости) дополнительных принудительных переходов сигнала между
двумя (как в коде Ман-честер-П) или тремя электрическими уровнями (как
в коде типа 8В6Т, используемом в сегменте Fast Ethernet 100BaseT4 на основе
четырех неэкранированных витых пар). По сравнению с классическим методом
CSMA в методе CSMA/CD добавлено обнаружение конфликтов (коллизий) во время
передачи, что повышает надежность доставки информации.
При описании временных диаграмм сетей типа Ethernet и Fast Ethernet, а
также предельных размеров пакетов (кадров) широко используются следующие
термины.
RAND(0, 2min<N-IO>) • 512 • ВТ,
где N - значение счетчика попыток, RAND(a, b) — генератор случайных нормально распределенных целых чисел в диапазоне а...Ь, включая крайние значения. Дискрет изменения данного параметра равен минимальной длине пакета или максимально допустимой двойной задержке распространения сигнала в сети (PDV).
Глава 7.1.1. Алгоритм доступа к сети
На рис. 7.1 показана структурная схема алгоритма доступа к сети в соответствии
с методом CSMA/CD для одного из абонентов, имеющих данные (кадры) для
передачи.
В начале из кадра, предназначенного для передачи, абонент (узел) формирует
пакет. Далее при обозначении блоков информации, передаваемых по сети при
использовании алгоритма CSMA/CD, понятия «кадр» и «пакет» не различаются,
что не совсем правильно, но соответствует сложившейся практике.
Если после подготовки пакета сеть свободна, то абонент (узел) может начать
передачу. Но сначала он должен проверить, прошло ли минимально допустимое
время IPG после предыдущей передачи (блок 1 на рисунке). Только после
окончания времени IPG абонент может начать передачу битов своего пакета
(блок 2 на рисунке).
После передачи каждого бита абонент поверяет наличие конфликта (коллизии)
в сети. Если коллизий нет, передача битов продолжается до окончания пакета
(блок 4 на рисунке). В этом случае считается, что передача прошла успешно.
Рис. 7.1. Структурная схема алгоритма доступа к сети в соответствии с методом CSMA/CD
Если после передачи какого-то бита обнаружена коллизия, то передача пакета прекращается. Абонент (узел) усиливает коллизию, передавая 32-
битовый сигнал ПРОБКА и начинает готовиться к следующей попытке передачи (блок 3 на рисунке). Сигнал ПРОБКА гарантирует, что факт наличия коллизии обнаружат все абоненты, участвующие в конфликте.
После передачи сигнала ПРОБКА абонент, обнаруживший коллизию, увеличивает значение счетчика числа попыток (перед началом передачи счетчик был сброшен в нуль). Максимальное число попыток передачи должно быть не более 16, поэтому если счетчик попыток переполнился, то попытки передать пакет прекращаются. Считается, что в этом случае сеть сильно перегружена, в ней слишком много коллизий. Эта ситуация - аварийная, и обрабатывается она на более высоких уровнях протоколов обмена.
Если же количество попыток не превысило 16, то производится вычисление величины задержки по приведенной формуле, а затем и выдержка вычисленного временного интервала. Случайный характер величины задержки с высокой степенью вероятности гарантирует, что у всех абонентов, участвующих в конфликте, задержки будут различными. Затем попытка передать пакет повторяется с самого начала. Понятно, что тот абонент, у которого вычисленная задержка будет меньше, начнет следующую передачу первым и заблокирует все остальные передачи.
Если в момент возникновении заявки на передачу (после окончания подготовки пакета) сеть занята другим абонентом, ведущим передачу, то данный абонент ждет освобождения сети (блок 5 на рисунке). После освобождения сети он должен выждать после предыдущей передачи по сети время IPG до начала собственной передачи. Это связано с конечным быстродействием узлов, осуществляющих проверку наличия несущей (занятости среды каким-либо передающим абонентом).
Таким образом, получается, что метод CSMA/CD не только не предотвращает коллизии, наоборот, он их предполагает, он их даже провоцирует, а затем разрешает. Например, если заявки на передачу возникли у нескольких абонентов во время занятости сети, то после ее освобождения все эти абоненты одновременно начнут передачу и образуют коллизию. Коллизия возникает и в случае свободной сети, если заявки на передачу возникают у нескольких абонентов одновременно. В обоих этих случаях под словом «одновременно» понимается «в пределах интервала двойного прохождения сигнала по сети», то есть в пределах 512-битовых интервалов. Точно так же в пределах 512-битовых интервалов обнаруживаются все коллизии в сети.
Если коллизия обнаруживается раньше 480- битового интервала, то в результате в сети образуются пакеты, длина которых меньше нижнего установленного предела в 512-битовых интервалов (64 байта) даже с добавлением сигнала ПРОБКА. Такие, пакеты (кадры) называются карликовыми (runt frames). Если же коллизия обнаруживается в конце 512-битового интервала (после 480-битового интервала), то в результате может получиться пакет допустимой длины (вместе с сигналом ПРОБКА). Такие пакеты называть карликовыми не совсем правильно. Сигнал ПРОБКА, образующий 32 последних бита пакета, выступает в виде контрольной суммы пакета. Однако вероятность того, что ПРОБКА будет соответствовать правильной контрольной сумме пакета, крайне мала (примерно 1 случай на 4,2 миллиарда).
Коллизии (наложения пакетов в процессе передачи) могут и должны обнаруживаться до окончания передачи. Действительно, анализ принятого в конце каждого пакета поля FCS, фактически содержащего помехоустойчивый циклический код CRC (Cyclic Redundancy Check), привел бы к неоправданному снижению скорости передачи.
Практически коллизии обнаруживаются либо самим передающим абонентом, либо повторителями в сети, возможно, задолго до окончания передачи заведомо испорченного пакета. Если учесть, что длина пакетов в локальной сети типа Ethernet/Fast Ethernet может лежать в диапазоне от 64 до 1518 байт, то досрочное прекращение передачи и освобождение линии означает заметное повышение эффективности использования ее пропускной способности.
Первым признаком возникновения коллизии является факт получения сигнала ПРОБКА передающим абонентом во время передачи пакета. Другие признаки связаны с неверным форматом пакетов, передача которых была досрочно прекращена из-за возникновения коллизии:
длина пакета меньше 64 байт (512 бит); пакет имеет неверную контрольную сумму FCS (точнее, неверный циклический код); длина пакета не кратна восьми.Наконец, в сетях типа Ethernet используется код Манчестер-П и чисто аппаратный способ определения коллизии, основанный на анализе отклонения среднего значения сигнала от нуля.
Даже при загруженной сети для одного абонента число подряд следующих коллизий обычно не превышает 2—3. Этому способствует случайный характер возникновения запроса на передачу и случайная дискретная величина отсрочки следующей попытки передачи в случае возникновения коллизии. Всего же предусмотрено 16 попыток передачи, после чего
возникшая особая ситуация обрабатывается протоколом более высокого уровня. Число коллизий тем больше, чем больше диаметр (размер) сегмента и чем дальше расположены друг от друга абоненты с интенсивным трафиком.
7.1.2. Оценка производительности сети
Вопрос об оценке производительности сетей, использующих случайный метод доступа CSMA/CD, не очевиден из-за того, что существуют несколько различных показателей. Прежде всего, следует упомянуть три связанные между собой показателя, характеризующие производительность сети в идеальном случае - при отсутствии коллизий и при передаче непрерывного потока пакетов, разделенных только межпакетным интервалом IPG. Очевидно, такой режим реализуется, если один из абонентов активен и передает пакеты с максимально возможной скоростью. Неполное использование пропускной способности в этом случае связано, кроме существования интервала IPG, с наличием служебных полей в пакете Ethernet (см. рис. 7.2).
Пакет максимальной длины является наименее избыточным по относительной доле служебной информации. Он содержит 12304 бит (включая интервал IPG), из которых 12000 бит являются полезными данными.
Поэтому максимальное скорость передачи пакетов (или, иначе, скорость в кабеле - wire speed) составит в данном случае
108 бит/с / 12304 бит = 8127,44 пакет/с.
Пропускная способность представляет собой скорость передачи полезной информации и в данном случае составит
8127,44 пакет/с • 1500 байт = 12,2 Мбайт/с.
Наконец, эффективность использования физической скорости передачи сети, в случае Fast Ethernet равной 100 Мбит/с, по отношению только к полезным данным составит
8127,44 пакет/с • 12000 бит / 10е бит/с = 98 %.
При передаче пакетов минимальной длины (с учетом интервала IPG -84 • 8 = 672 бит, из которых только 46 • 8 = 368 бит несут полезную информацию) возрастает скорость в кабеле (148809,52 пакет/с вместо 8127,44 пакет/с), что означает всего лишь факт передачи большого числа коротких пакетов. В то же время пропускная способность (6,8 Мбайт/с вместо 12,2 Мбайт/с) и эффективность (55% вместо 98 %) заметно ухудшаются.
Для реальных сетей типа Fast Ethernet с большим числом активных абонентов N пропускная способность на уровне 12,2 Мбайт/с для какого-либо абонента является пиковым, редко реализуемым значением. При одинаковой активности всех абонентов средняя пропускная способность для каждого из них составит 12,2/N Мбайт/с, а на самом деле может оказаться еще меньше из-за возникновения коллизий, ошибок в работе сетевого оборудования и влияния помех (в случае работы локальной сети в условиях, когда кабельная система подвержена влиянию больших внешних электромагнитных наводок). Влияние помех, так же как и поздних конфликтов (late collision) в некорректных сетях, отслеживается с помощью анализа поля FCS пакета.
Для реальных сетей более информативен такой показатель производительности, как показатель использования сети (network utilization), который представляет собой долю в процентах от суммарной пропускной способности (не поделенной между отдельными абонентами). Он учитывает коллизии и другие факторы. Ни сервер, ни рабочие станции не содержат средств для определения показателя использования сети, для этого предназначены специальные, не всегда доступные, из-за высокой стоимости аппаратно-программные средства типа анализаторов протоколов.
Считается, что для загруженных систем Ethernet и Fast Ethernet хорошим значением показателя использования сети является 30%. Это значение соответствует отсутствию длительных простоев в работе сети и обеспечивает достаточный запас в случае пикового повышения нагрузки. Однако если показатель использования сети значительное время составляет 80...90% и более, то это свидетельствует о практически полностью используемых (в данное время) ресурсах, но не оставляет резерва на будущее. Впрочем, для реальных сетей типа Fast Ethernet это скорее гипотетическая ситуация.
На рис. 7.2 приведена зависимость показателя использования сети от времени при условии, что предложенная нагрузка (offered load), т.е. текущий запрос на пропускную способность, линейно возрастает. Сначала показатель использования сети также линейно возрастает, но затем конкуренция за владение средой передачи порождает коллизии и рассматриваемый показатель достигает максимума (точка полной нагрузки на графике). При дальнейшем увеличении предложенной нагрузки показатель использования сети начинает уменьшаться, особенно резко после точки насыщения. Это «плохая» область работы сети. Считается, что сеть работает хорошо, если и предложенная нагрузка, и показатель использования сети высоки.
Рис. 7.2. Зависимость показателя использования сети от времени при линейном увеличении предложенной нагрузки (1 - наилучшая область работы, 2 - приемлемая, 3 - плохая)
Некоторые авторы предлагают использовать для широко распространенного понятия «перегрузка» (overload) сетей на основе метода доступа CSMA/CD следующее определение: сеть перегружена, если она не может работать при полной нагрузке в течении не менее 80% своего времени (предполагается, что при этом в течении не менее 20% времени показатель использования сети недопустимо мал из-за коллизий). После точки насыщения наступает крах Ethernet (Ethernet collapse), когда возрастающая предложенная нагрузка заметно превышает возможности сети.
Стоит заметить, что реально маловероятно, чтобы предложенная нагрузка постоянно увеличивалась во времени и надолго превышала пропускную способность сети типа Fast Ethernet. Более того, любой детерминированный метод доступа не может обеспечить реализацию сколь угодно большой предложенной нагрузки, существующей продолжительное время. Если данный вариант детерминированного метода доступа не предусматривает, как и метод CSMA/CD, систему приоритетов, то никакой из абонентов не может захватить сеть более чем на время передачи одного пакета, однако передача данных отдельными пакетами с долгими паузами между ними ведет к снижению скорости передачи для каждого абонента. Однако преимущество детерминированных методов состоит в возможности простой организации системы приоритетов, что полезно из-за существования определенной иерархии в любом крупном коллективе.
Глава 7.2. Использование помехоустойчивых кодов для обнаружения ошибок в сети
Сигналы, непосредственно передаваемые по последовательным линиям (типа витой пары, коаксиального кабеля или телефонной линии), подвержены влиянию ряда факторов, воздействие которых может привести к возникновению ошибок в принятой информации. Ошибки могут возникать вследствие влияния на канал связи наводок и помех естественного или искусственного происхождения, а также вследствие изменения конфигурации системы передачи информации с временным нарушением или без нарушения целостности канала связи (например, в случае подключения новых абонентов к существующей локальной информационной сети).
Некоторые из ошибок могут быть обнаружены на основании анализа вида принятого сигнала, так как в нем появляются характерные искажения. Примером может служить код Манчестер-П, используемый в сетях Ethernet. На передающем конце линии этот код обязательно содержит переход с низкого электрического уровня на высокий или обратно в середине каждого тактового интервала, требуемого для передачи одного бита информации. Он также имеет среднюю составляющую, близкую к нулю. Эти свойства кода Манчестер-П могут использоваться для обнаружения разного рода ошибок. В частности, отличие средней составляющей сигнала от нуля является одним из признаков возникновения коллизий (наложений пакетов от разных абонентов), характерных для метода доступа CSMA/CD в сетях типа Ethernet. Однако сколько-нибудь серьезную систему обнаружения ошибок, вызванных воздействием помех с непредсказуемым поведением, на этой основе построить невозможно.
Стандартные протоколы обмена информации в сетях предусматривают введение обязательного поля для размещения помехоустойчивого (корректирующего) кода. Если в результате обработки принятого пакета обнаружится несоответствие принятого и вновь вычисленного помехоустойчивого кода, с большой долей вероятности можно утверждать, что среди принятых бит имеются ошибочные. Передачу такого пакета нужно будет повторить (в расчете на случайный характер помех).
Глава 7.2.1. Способы снижения числа ошибок в принятой информации
Имеется разрыв между требованиями к верности принимаемой информации и возможностями существующих каналов связи. В частности, стандартами международных организаций МККТТ и МОС установлено, что вероятность ошибки при телеграфной связи не должна превышать 3 • 10"5 (на знак), а при передаче данных - 10~6 (на единичный элемент, бит). На практике допустимая вероятность ошибки при передаче данных может быть еще меньше - 10~9. В то же время существующие каналы связи (особенно каналы большой протяженности и протяженные радиоканалы) обеспечивают вероятность ошибки на уровне 10~3...10"4 даже при использовании фазовых корректоров, регенеративных ретрансляторов и других устройств, улучшающих качество каналов связи.
Кардинальным способом снижения вероятности ошибок при приеме является введение избыточности в передаваемую информацию. В системах передачи информации без обратной связи данный способ реализуется в виде помехоустойчивого кодирования, многократной передачи информации или одновременной передачи информации по нескольким параллельно работающим каналам. Помехоустойчивое кодирование доступнее и при прочих равных условиях позволяет обойтись меньшей избыточностью и за счет этого повысить скорость передачи информации.
Глава 7.2.2. Характеристики и разновидности помехоустойчивых кодов
Помехоустойчивое кодирование предполагает введение в передаваемое сообщение, наряду с информационными, так называемых проверочных разрядов, формируемых в устройствах защиты от ошибок (кодерах-на передающем конце, декодерах — на приемном). Избыточность позволяет отличить разрешенную и запрещенную (искаженную за счет ошибок) комбинации при приеме, иначе одна разрешенная комбинация переходила бы в другую.
Помехоустойчивый код характеризуется тройкой чисел (n, k, d0), где n— общее число разрядов в передаваемом сообщении, включая проверочные (г), k=n-r - число информационных разрядов, d0— минимальное кодовое расстояние между разрешенными кодовыми комбинациями, определяемое как минимальное число различающихся бит в этих комбинациях. Число обнаруживаемых (tj и (или) исправляемых (t ) ошибок (разрядов) связано с параметром d0 соотношениями
Иногда используются дополнительные показатели избыточности, производные от приведенных выше характеристик n, k:R = r/n- относительная избыточность, v = k / n - относительная скорость передачи.
Существующие помехоустойчивые коды можно разделить на ряд групп, только часть из которых используется для обнаружения ошибок в передаваемых по сети пакетах (на рис. 7.3 используемые для этой цели группы выделены утолщенными стрелками). В группе систематических (линейных) кодов общим свойством является то, что любая разрешенная комбинация может быть получена в результате линейных операций над линейно-независимыми векторами. Это способствует упрощению аппаратной и программной реализации данных кодов, повышает скорость выполнения необходимых операций.
Рис. 7.3. Классификация помехоустойчивых кодов
Простейшими систематическими кодами являются биты четности/нечетности. Они не позволяют обнаружить ошибки четной кратности (т.е. ошибки одновременно в двух, четырех и т.д. битах) и поэтому используются при невысоких требованиях к верности принимаемых данных (или при малой вероятности ошибок в линии передачи). Примером может служить бит Parity (соответствие) в установках режимов работы последовательного порта с помощью команды MODE (MS DOS). Несмотря на ограниченные возможности обнаружения ошибок, биты четности/нечетности имеют большое значение в теории помехоустойчивого кодирования. Одни иг первых математически обоснованных и практически использовании? помехоустойчивых кодов - коды Хэмминга представляют собой простс совокупность перекрестных проверок на четность/нечетность. Циклические коды могут рассматриваться как обобщенные проверки на четность/ нечетность (см. далее).
Глава 7.2.3. Циклические коды (CRC)
Циклические коды - это целое семейство помехоустойчивых кодов, вклю чающее в себя в качестве одной из разновидностей коды Хэмминга, но : целом обеспечивающее большую гибкость с точки зрения возможност] реализации кодов с необходимой способностью обнаружения и исправ ления ошибок, определяемой параметром d0, по сравнению с кодами Хэм минга (для которых dQ=3 или d0=4). Широкое использование цикличес ких кодов на практике обусловлено также простотой реализаци соответствующих кодеров и декодеров.
Основные свойства и само название циклических кодов связаны с те!\ что все разрешенные комбинации бит в передаваемом сообщении (коде вые слова) могут быть получены путем операции циклического сдвиг некоторого исходного кодового слова:
Циклические коды задаются с помощью так называемых порождающр полиномов (многочленов) g(x) или их корней. Кроме того, вводятся понятия полинома исходного сообщения
Для этих полиномов, представляющих собой, по существу, альтерната ную запись чисел в двоичной системе счисления, определяются опер ции сложения, умножения и деления, необходимые для организации i
дирования н декодирования сообщения. Все эти операции выполняются по модулю 2.
Рассмотрим последовательность кодирования на примере циклического кода (7,4,3), имеющего g(x) = х3 + х + 1:
1) информационная часть сообщения записывается в виде полинома:
В рассматриваемом примере k = 4 и для сообщения 0111 получаем
2) и(х) умножается хг, что соответствует циклическому сдвигу исходного сообщения на г разрядов влево:
3) полученный многочлен делится на g(x):
где с(х)-полином - частное с максимальной степенью (k-1); R(x)-полином - остаток с максимальной степенью (г-1); © - обозначение поразрядной операции суммирования по модулю 2 (исключающее ИЛИ).
Кодированное сообщение представляется в виде
то есть на месте младших, освобожденных после домножения на хг, разрядов, записываются проверочные разряды.
Для рассматриваемого примера:
Таким образом, в данном случае А(х) = (х3 + х4 + х3) © х = х5 + х4 + х3 + х. Передаваемое кодированное сообщение в обычной двоичной форме имеет вид:
Один из возможных вариантов аппаратурной реализации кодера для рассматриваемого примера представлен на рис. 7.4 вместе с последовательностью сигналов, подтверждающей получение тех же самых проверочных разрядов (010) на восьмом такте (г + k + 1 = 8).
Кодер представляет собой сдвиговый регистр с обратными связями, организуемыми с помощью элементов М2 (исключающее ИЛИ, сумматор по модулю 2). Структура обратных связей полностью определяется ненулевыми коэффициентами порождающего полинома g(x).
Рис. 7.4. Пример формирования циклического кода (сигнал обратной связи отличен от нуля на 5-м и б-м тактах)
На первых восьми тактах ключ Кл. находится в верхнем положении и формируются проверочные разряды. Затем ключ Кл. устанавливается в
нижнее положение, что соответствует разрыву цепей обратных связей и передаче непосредственно в канал связи или на модулятор проверочных разрядов. Для временного хранения информационной части сообщения с целью последующей ее передачи вместе с проверочными разрядами кодер, очевидно, должен быть дополнен сдвиговым регистром длиной в k разрядов, ключами и соответствующими цепями управления. Однако, в целом, аппаратурные затраты при реализации кодеров в случае циклических кодов невелики - общее число триггеров и элементов М2 (исключая регистр временного хранения информационной части сообщения) не превышает 2 г и не зависит от длины информационной части сообщения.
Двухвходовый элемент М2, на один из входов которого подается в последовательной форме сообщение, на выходе формирует бит четности или нечетности (в зависимости от значения сигнала на втором входе элемента М2 - 0 или 1) для этого сообщения. В схеме кодера (рис. 7.4) элементы М2 включены между отдельными триггерами сдвигового регистра, причем сигналы обратной связи, поступающие на «свободные» входы элементов М2 (не связанные с передачей собственно сообщения через сдвиговый регистр), зависят как от предшествующих разрядов сообщения, так и от структуры обратных связей, принятой в кодере. В результате циклический код, формируемый таким кодером, можно считать совокупностью обобщенных бит четности и нечетности, тип которых (четность или нечетность) не определен заранее и может динамически меняться от такта к такту.
Порождающие полиномы, представляющие собой т. н. неприводимые многочлены (многочлены, которые делятся лишь на единицу и на самих себя), табулированы для разных значений n, k и dQ, например, п = 7...255, k = 3...247, d0= 3...127. Практически в компьютерных сетях используются циклические коды длиною в 2 или 4 байта (16 или 32 бита), а параметры п, k и d0 в явном виде не указываются. Это связано с возможностью выбора различной длины поля данных в пакете на этапе установления и выбора параметров соединения при неизменной длине поля циклического кода. Теоретическая вероятность ошибки при приеме в случае использования циклического кода не хуже рощ < 1/2г, так что для выполнения условия стандарта рош < 10"6 необходимое число проверочных разрядов г > Iog2106 = 20. Кроме случайно распределенных, циклический код позволяет обнаруживать подряд следующие ошибки (так называемые пакеты ошибок) длиною 1 = г или меньше. Это особенно важно в связи с возможностью возникновения продолжительных во времени помех, действующих на протяженные линии передачи в компьютерных сетях.
Хотя циклические коды обладают способностью исправления ошибок высокой кратности (при большом значении параметра d0) и известны технические решения декодеров с исправлением ошибок, однако практическая реализация таких декодеров на современном этапе представляется затруднительной, особенно в случае широкополосных (высокоскоростных) каналов связи. В настоящее время более распространены декодеры с обнаружением ошибок. При использовании обнаруживающего декодера в системе передачи информации неверно принятая информация может игнорироваться либо может быть запрошена повторная передача той же информации; в последнем случае предполагается наличие сигнала подтверждения правильности принятой информации, поступающего от приемника к передатчику информации. По мере развития элементной базы следует ожидать появления в интегральном исполнении декодеров циклических кодов, способных не только обнаруживать, но и исправлять ошибки.
Отметим также, что кроме систем передачи информации, циклические коды используется в запоминающих устройствах (ЗУ) для обнаружения возможных ошибок в считываемой информации. При записи файлов на диск (в том числе при их архивировании) вместе с файлами формируются и записываются соответствующие циклические коды. При чтении файлов (в том числе при извлечении файлов из архива) вычисленные циклические коды сравниваются с записанными и таким образом обнаруживаются возможные ошибки. Свойства циклического кода лежат в основе сигнатурного анализа (эффективного способа поиска аппаратных неисправностей в цифровых устройствах различной сложности). Варианты практической реализации соответствующих кодеров и сигнатурных анализаторов имеют между собой много общего.
Следует сделать два замечания относительно сложившейся терминологии. Хотя понятие «циклические коды» достаточно широкое, на практике его обычно используют для обозначения только одной разновидности, описанной выше и имеющей в англоязычной литературе название CRC (Cyclic Redundancy Check - циклическая избыточная проверка). Более того, иногда поле пакета, фактически содержащее код CRC, называется «контрольной суммой», что в принципе не совсем верно, но встречается повсеместно.
Перспективными с точки зрения аппаратурной реализации представляются коды БЧХ (коды Боуза-Чаудхури-Хоквингема), так же, как и коды Хэмминга, входящие в семейство циклических кодов. Коды БЧХ не слишком большой длины (примерно до п = 1023) оптимальны или близки к оптимальным кодам, т.е. обеспечивают максимальное значение d0 при минимальной избыточности. Эти коды уже нашли практическое применение в цифровых системах записи звука (речи, музыки), причем в варианте, предусматривающем исправление обнаруженных ошибок. Понятно, что относительно невысокие частоты дискретизации звуковых сигналов (48 или 96 кГц) не препятствуют так жестко, как в случае высокоскоростных сетей, проведению дополнительных вычислений.
