Э. Таненбаум - Компьютерные сети. (4-е издание) (DJVU) (1130092), страница 62
Текст из файла (страница 62)
Эти правила часто запрещают пересылку кадра до тех пор, пока получатель не даст разрешения, либо явно, либо неявно. Например, при уставовке соединения получатель может сказать; «Вы можете послать мне сейчас и кадров, но не посылайте следующие кадры, пока я не попрошу вас продолжать». Вданной главе мы рассмотрим различные механизмы, основанные на этом принципе. Обнаружение и исправление ошибок Как было показано в главе 2, телефонная система состоит из трех частей — коммутаторов, межкоммутаторных магистралей и местных телефонных линий. Первые две части являются сегодня почти полностью цифровыми.
Местные телефонные линни до сих пор представляют собой аналоговые медные витые пары и останутся такими еще в течение нескольких лет, поскольку их замена стоит очень дорого. И хотя в цифровой части телефонной системы ошибки случаются редко, в местных телефонных линиях вероятность ошибки очень велика. Кроме того, в последнее время все большее распространение получает беспроводная связь, в которой уровень ошибок на несколько порядков выше, чем в соединяюших телефонные станции магистралях.
Отсюда следует вывод: ошибки при передаче данных останутся важным фактором еше на долгие годы. Сейчас мы приступаем к изучению методов их обнаружения и устранения. Вследствие особенностей физических процессов, порождающих их, ошибки в некоторых типах носителей (например, радио) чаще была|от не единичными, а групповыми. В этом есть как положительные, так н отрицательные стороны. Положительные связаны с тем, что компьютеры всегда посылают данные битовыми блоками.
Представьте себе блок размером в 1000 бит при вероятности ошибки 0,001 на бит. Если бы ошибки были независимыми, то очень большой процент блоков содержал бы ошибки. Однако если ошибки приходят пакетами, искажая по 100 бит подряд, то из 100 блоков будут испорчены в среднем только один или два. Неудобством групп ошибок является то, что их значительно труднее исправить, чем изолированные ошибки. Обнаружение и исправление ошибок 23; Корректирующее кодирование разработчики сетей создали две основные стратегии для борьбы с ошибками.
Ка ждый метод основывается на добавлении к передаваемым данным некоторой из. быточной информации. В одном случае этой информации должно быть достаточно чтобы выявить, какие данные должны были прийти. В другом случае избыточцог информации должно быть достаточно только для того, чтобы получатель понял что произошла ошибка (без указания ее типа) и запросил повторную передачу Первая стратегия использует коды, называющиеся корректиру1ощими, или кода. ми с исправлением ошибок. Вторая — код с обнаружением ошибок. Использование кода с обнаружением ошибок часто называют прямым исправлением ошибок. Каждая стратегия занимает свою, так сказать, экологическую нишу. В высоконадежных каналах, таких как оптоволокно, дешевле использовать код с обнаружением ошибок и просто заново передавать случайные поврежденные блоки.
Однако, скажем, беспроводные соединения, в которых может возникать множество ошибок, чаше используют коды с избыточностью, достаточной для того, чтобы приемник мог определить, какие данные должны были прийти. Это надежнее, чем полагаться на повторную передачу, которая тоже, возможно, не сможет пройти без ошибок. Чтобы понять, как могут обнаруживаться и исправляться ошибки, необходимо рассмотреть подробнее, что же представляет собой ошибка. Обычно кадр состоит из гл битов данных (то есть информационных битов) н г избыточных или контрольных битов. Пусть полная длина кадра равна и (то есть п = т з- г). Набор из п бит, содержащий информационные и контрольные биты, часто называют и-битовым кодовым словом илн кодовой комбинацией. Если рассмотреть два кодовых слова, например 10001001 и 10110001, можно определить число различа|ощпхся в них соответствующих разрядов.
В данном примере различаются 3 бита. Для нахождения этого числа нужно сложить два кодовых слова по модулю 2 (операция «исключающее илиь) и сосчитать количество единиц в результате, например; 10001001 10110001 00111000 Количество битов, которыми различаются два кодовых слова, называется кодовыги расстоянием, или расстоянием между кодовыми комбинациями в смысле Хэмминга (Наппп1пя, 1950).
Смысл этого числа состоит в том, что если два кодовых слова находятся на кодовом расстоянии и', то для преобразования одного кодового слова в другое понадобится г( ошибок в одиночных битах. В большинстве приложений передачи данных все 2 возможных сообщений являются допустимыми, однако благодаря использованию контрольных битов не все 2" возможных кодовых слов используются. Зная алгоритм формирования контрольных разрядов, можно построить полный список всех допустимых кодовых слов и в этом списке найти такую пару кодовых слов, кодовое расстояние 234 Глава 3.
Уровень передачи данных между которыми будет минимальным. Это расстояние называется минимальным кодовым расстоянием кода, или расстоянием всего кода в смысле Хзмминга. Способности кода по обнаружению и исправлению ошибок зависят от его минимального кодового расстояния. Для обнаружения Ы ошибок в одном кодовом слове необходим код с минимальным кодовым расстоянием, равным Ы + 1, поскольку г( однобитовых ошибок не смогут изменить одну допустимую комбинацию так, чтобы получилась другая допустимая комбинация.
Когда прислужник встречает запрещенную кодовую комбинацию, он понимает, что при передаче произошла ошибка. Аналогично, для исправления И ошибок в одном кодовом слове требуется код с минимальным кодовым расстоянием, равным 2ь! + 1, так как в данном случае даже при Ы однобитовых ошибках результат окажется ближе к исходному кодовому слову, чем к любому другому, и, следовательно, его можно будет однозначно восстановить. В качестве простейшего примера кода с обнаружением ошибок рассмотрим код, в котором к данным добавляется один бит четности. Бит четности выбирается таким образом, чтобы количество единиц во всем кодовом слове было четным (или нечетным).
Например, при посылке числа 10110101 с добавлением бита четности в конце оно становится равным 101101011, тогда как 10110001 преобразуется в 101100010. Код с единственным битом четности имеет кодовое расстояние, равное 2, так как любая однократная ошибка в любом разряде образует кодовое слово с неверной четностью.
Такой код может использоваться для обнаружения однократных ошибок. В качестве простейшего примера корректирующего кода рассмотрим код, у которого есть всего четыре допустимые кодовые комбинации: 0000000000, 0000011111, 1111100000 и 1111111111 Этот код имеет расстояние, равное 5, что означает, что он может исправлять двойные ошибки. Если приемник получит кодовое слово 0000000111, он поймет, что оригинал должен быть равен 0000011111. Однако если тройная ошибка изменит 0000000000 на 0000000111, ошибка будет исправлена неверно. Попробуем создать код, состоящий из т информационных и г контрольных битов, способный исправлять одиночные ошибки. Каждому из 2 допустимых сообщений будет соответствовать и недопустимых кодовых слов, отстоящих от сообщения на расстояние 1. Их можно получить инвертированием каждого из и битов и-битового кодового слова. Таким образом, каждому из 2" допустимых сообщений должны соответствовать и + 1 кодовых комбинаций.
Поскольку общее количество возможных кодовых комбинаций равно 2", получается, что (и+ 1)2 < 2". Так как и = т+ г, это требование может быль преобразовано к виду (т+ г+ 1) < 2( При заданном т данная формула описывает нижний предел требуемого количества контрольных битов для возможности исправления одиночных ошибок. Этот теоретический нижний предел может быть достигнут на практике с помощью метода Хэмминга (1950).
Биты кодового слова нумеруются последовательно слева направо, начиная с 1. Биты с номерами, равными степеням 2 (1, 2, 4, 8, 16 и т, д.), являются контрольными. Остальные биты (3, 5, 6, 7, 9, 10 и т. д.) заполняются т битами данных. Каждый контрольный бит обеспечивает четность Обнаружение и исправление ошибок 236 (или нечетность) некоторой группы битов, включая себя самого. Один бит моясет входить в несколько различных групп битов, четность которых вычисляется Чтобы определить, в какие группы контрольных сумм будет входить бит данных в й-й позиции, следует разложить Ф по степеням числа 2.
Например, 11 = 8+ 2+ 1, а 29 = 16+ 8+ 4+ 1. Каждый бнт проверяется только темп контрольными битами, номера которых входят в этот ряд разложен1ия (например, 11-й бит проверяется битами 1, 2 и 8). Когда прибывает кодовое слово, приемник обнуляет счетчик. Затем он проверяет каждый контрольный бит Й ((т = 1, 2, 4, 8, ...) на четность.
Если сумма оказывается нечетной, он добавляет число )г к счетчику. Если после всех проверок счетчик равен нулю, значит, все проверки были пройдены успешно. В противном случае он содержит номер неверного бита, Например, если ошибку дают проверки битов 1, 2 и 8, это означает, что инвертирован бит 11, так как он является единственным битом, контролируемым битами 1„2 и 8. На рис. 3.7 изображены некоторые А8СП-символы, кодированные 11-битовым кодом Хэммннга. Напоминаем, что данные хранятся в битах 3, 5, 6, 7, 9, 10 и 11.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
