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

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

Мы рассмотрели ряд протоколов, обеспечивающих надежную работу канального уровня за счет подтверждений и повторной передачи или, если взять более приближенный к жизни пример, за счет запросов ARQ (Automatic Repeat reQuest). Начиная с идеальной среды передачи, в которой отсутствуют ошибки, и идеального приемника, который может обработать входящий поток любого размера, мы познакомились с управлением потоком, затем с контролем ошибок при помощи порядковых номеров

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

В Интернете в качестве основного протокола линий «точка — точка» используется PPP. Он предоставляет сервис без установки соединения и без подтверждения. Для разделения кадров применяются флаговые байты, а для распознавания ошибок — коды CRC. С помощью этого протокола пакеты передаются по множеству типов соединений, включая каналы SONET в глобальных сетях и ADSL для домашних подключений.

Вопросы

1. Сообщение верхнего уровня разбито на 10 кадров, у каждого из которых шанс дойти до назначения без повреждений составляет 80 %. Если канальный уровень не обеспечивает проверки ошибок, сколько раз в среднем потребуется пересылать все сообщение?

2. В протоколе канального уровня используется следующее кодирование символов:

A: 01000111; B: 11100011; FLAG: 01111110; ESC: 11100000 Как в двоичных кодах будет выглядеть кадр, состоящий из четырех символов — A B ESC FLAG, при использовании каждого из следующих методов кадрирования:

1) подсчет байтов;

2) флаговые байты с символьным заполнением;

3) начальные и конечные флаговые байты с битовым заполнением.

3. В потоке данных, для которого применяется алгоритм символьного заполнения, встречается следующий фрагмент данных: A B ESC C ESC FLAG FLAG D. Каким будет выходной поток после заполнения символами?

4. Каковы максимальные накладные расходы для алгоритма символьного заполнения?

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

6. Каким будет на выходе следующий поток бит после применения битового заполнения на уровне передачи данных: 0111101111101111110?

7. При каких обстоятельствах протокол без обратной связи (например, с кодом Хэмминга) может быть предпочтительнее протоколов с обратной связью, обсуждаемых в данной главе?

8. Для обеспечения большей надежности, нежели та, которую предоставляет единственный бит четности, в некотором методе обнаружения ошибок один бит четности суммирует все четные биты, а другой — все нечетные. Каково будет в этом случае расстояние кода по Хэммингу?

9. При помощи кода Хэмминга передаются 16-битные сообщения. Сколько контрольных бит потребуется для того, чтобы приемник гарантированно мог обнаруживать и исправлять одиночные битовые ошибки? Как будет выглядеть код для передачи следующего сообщения: 1101001100110101? Предполагается, что код Хэмминга использует проверку четных бит.

10. Приемник получает 12-битную последовательность в коде Хэмминга, ее шестнадцатеричное значение равно 0xE4F. Как (в шестнадцатеричном виде) выглядела исходная последовательность? Предполагается, что ошибочным может быть только 1 бит.

11. Один из способов обнаружения ошибок заключается в передаче данных в виде блока из n рядов по к бит с добавлением битов четности к каждому ряду и каждой строке. Бит в нижнем правом углу — это бит четности, проверяющий свою строку и столбец. Будет ли такая схема обнаруживать все одиночные ошибки? Двойные ошибки? Тройные ошибки? Докажите на примере, что эта схема не в состоянии обнаруживать некоторые четырехбитные ошибки.

12. Предположим, что данные передаются в блоках размером 1000 бит. Каков максимальный коэффициент ошибок, при котором механизм с обнаружением ошибок и повторной передачей (1 бит четности на блок) покажет себя лучше, чем код Хэмминга? Предполагается, что ошибки в битах не зависят друг от друга, а во время повторной передачи ошибок в битах не бывает.

13. В блоке битов из n рядов и к строк используются горизонтальные и вертикальные биты четности для обнаружения ошибок. Какова вероятность того, что инверсия 4 бит не будет обнаружена?

14. Используя сверточный кодировщик, показанный на рис. 3.7, покажите выходную последовательность для входной последовательности 10101010 (слева направо) и нулевого внутреннего состояния.

15. Предположим, что сообщение 1001 1100 1010 0011 передается с использованием контрольной суммы для Интернета (4-битное слово). Какова будет контрольная сумма?

16. Чему равен остаток от деления

17. Поток бит 10011101 передается с использованием стандартного метода циклического избыточного кода (CRC), описанного в тексте. Образующий многочлен равен x 3+ 1. Какая битовая последовательность будет реально передаваться? Предполагается, что третий бит слева при передаче инвертировался. Докажите, что эта ошибка будет обнаружена приемником. Приведите пример ошибок в битах передаваемой строки, которые приемник обнаружить не сможет.

18. Отправляется 1024-битное сообщение, содержащее 992 бита данных и 32 бита CRC. Код CRC вычисляется с использованием стандартизированного в IEEE 802 многочлена 32 степени. Для каждого из следующих случаев объясните, распознает ли получатель ошибки передачи сообщения: