Шрифт:
4. Вы принимаете следующий фрагмент данных: 0110 0111 1100 1111 0111 1101. При этом известно, что протокол использует бит-стаффинг. Как будут выглядеть эти данные после удаления вставленных битов?
5. Может ли потеря, вставка или модификация одного бита при использовании бит-стаффинга вызвать ошибку, которую нельзя будет выявить с помощью контрольной суммы? Если нет, то почему? Если да, то каким образом? Играет ли при этом какую-либо роль длина контрольной суммы?
6. Сообщение верхнего уровня разбито на 10 фреймов, у каждого из которых шанс дойти до назначения без повреждений составляет 80 %. Если канальный уровень не обеспечивает контроль ошибок, сколько раз в среднем потребуется пересылать все сообщение?
7. При каких обстоятельствах протокол без обратной связи (например, с кодом Хэмминга) предпочтительнее протоколов с обратной связью, обсуждаемых в этой главе?
8. Для обеспечения большей надежности, чем та, которую предоставляет единственный бит четности, в некотором коде с обнаружением ошибок один бит четности суммирует все четные биты, а другой — все нечетные. Каким будет у этого кода расстояние Хэмминга?
9. Заметив, что используемая вами служба обмена мгновенными сообщениями не обеспечивает обнаружения ошибок, вы решили сами реализовать простейший механизм их выявления путем двукратной отправки каждого сообщения. Какими при этом будут расстояние Хэмминга и кодовая норма? Насколько эффективен этот способ в сравнении с использованием бита четности?
10. Допустим, вы обеспечиваете обнаружение ошибок путем двукратной отправки каждого сообщения. Если возникнут две однобитные ошибки, какова вероятность того, что они останутся незамеченными? Какой будет эта вероятность при использовании бита четности? Какой метод позволяет выявлять больше ошибок?
11. 8-битный байт с двоичным значением 10101111 необходимо закодировать, используя код Хэмминга с четным количеством единиц. Как будет выглядеть двоичное значение после кодирования?
12. 8-битный байт с двоичным значением 10011010 необходимо закодировать, используя код Хэмминга с нечетным количеством единиц. Как будет выглядеть двоичное значение после кодирования?
13. Приемник получает 12-битный код Хэмминга с контролем четности, шестнадцатеричное значение которого равно 0xB4D. Как (в шестнадцатеричном виде) выглядела исходная последовательность? Предполагается, что ошибочным может быть только 1 бит.
14. У кодов Хэмминга расстояние равно 3, что позволяет с их помощью исправлять одиночные ошибки или выявлять двойные. Можно ли применять их для одновременного выполнения обеих задач? Обоснуйте свою точку зрения. Сколько ошибок может быть исправлено, если расстояние Хэмминга равно n? А сколько обнаружено?
15. Имеется протокол, в котором на каждые 16 байт данных сообщения добавляется 1 байт избыточных данных. Может ли этот протокол использовать код Хэмминга для исправления одиночных ошибок?
16. Один из способов обнаружения ошибок заключается в передаче данных в виде блока из n рядов по k бит с добавлением битов четности к каждому ряду и каждой строке. Бит в нижнем правом углу — это бит четности, проверяющий свою строку и столбец. Будет ли такая схема выявлять все одиночные ошибки? Двойные? Тройные? Докажите на примере, что эта схема не в состоянии обнаруживать некоторые четырехбитные ошибки.
17. Сколько ошибок можно обнаружить и исправить в предыдущей задаче?
18. Составьте формулу для вычисления минимального количества избыточных битов r, добавляемых в сообщение m с целью исправления всех одиночных и двойных ошибок.
19. Принимая во внимание ответ на предыдущий вопрос, объясните популярность сложных вероятностных механизмов исправления ошибок, таких как рассмотренные в данной главе сверточные коды и коды LDPC.
20. Предположим, что данные передаются в блоках размером 1000 бит. Каков максимальный коэффициент ошибок, при котором механизм с обнаружением ошибок и повторной передачей (1 бит четности на блок) покажет себя лучше, чем код Хэмминга? Предполагается, что ошибки в битах не зависят друг от друга, а во время повторной передачи они не возникают.
21. В блоке битов из n строк и k столбцов используются горизонтальные и вертикальные биты четности для обнаружения ошибок. Какова вероятность того, что инверсия 4 бит не будет обнаружена?
22. Предположим, что сообщение 1001 1100 1010 0011 передается с использованием контрольной суммы для интернета (4-битное слово). Какова будет контрольная сумма?
23. Чему равен остаток от деления x7 + x5 + 1 на образующий многочлен x3 + 1?
24. Поток битов 10011101 передается с использованием стандартного метода циклического избыточного кода (CRC), описанного в данной главе. Образующий многочлен равен x3 + 1. Какая битовая последовательность будет реально передаваться? Предполагается, что третий бит слева при передаче инвертировался. Докажите, что эта ошибка будет обнаружена приемником. Приведите пример ошибок в битах передаваемой строки, которые приемник обнаружить не сможет.
25. Поток битов 11100110 передается с использованием стандартного метода циклического избыточного кода (CRC), описанного в этой главе. Образующий многочлен равен x4 + x3 + 1. Какая битовая последовательность будет реально передаваться? Предполагается, что третий бит слева при передаче инвертировался. Докажите, что эта ошибка будет обнаружена приемником. Приведите пример ошибок в битах передаваемой строки, которые приемник обнаружить не сможет.
26. Протоколы канального уровня всегда размещают код CRC в трейлере, а не в заголовке. Почему?