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

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 в трейлере, а не в заголовке. Почему?

27. При обсуждении протокола ARQ приводился пример сценария, в котором получатель принимает две копии одного и того же фрейма из-за потери подтверждения. Возможно ли, что получатель примет несколько копий одного фрейма, если ни один из фреймов (данных или подтверждения) утерян не будет?

28. Скорость передачи данных в канале составляет 4 Кбит/с, а время распространения сигнала — 20 мс. При каком размере фреймов эффективность протокола с остановкой и ожиданием составит по меньшей мере 50 %?

29. Протоколы A и B различаются только размером посылающего окна. Протокол A использует окно передачи размером 20 фреймов. B представляет собой протокол с остановкой и ожиданием. Эти протоколы используются в двух одинаковых каналах. Если A обеспечивает почти 100%-ю эффективность использования пропускной способности, то каков этот показатель у B?

30. Протокол с остановкой и ожиданием обеспечивает 25%-ю эффективность использования пропускной способности, передавая 900-битные фреймы по каналу с задержкой односторонней передачи 50 мс. Чему равна пропускная способность этого канала в битах в секунду?

31. Протокол с остановкой и ожиданием обеспечивает 60%-ю эффективность использования пропускной способности, передавая 300-битные фреймы по каналу, пропускная способность которого равна 50 Кбит/с. Чему равна задержка односторонней передачи у этого канала?

32. Протокол с остановкой и ожиданием передает 800-битные фреймы по каналу с задержкой односторонней передачи 8 мс и с пропускной способностью 1200 Кбит/с. Какова при этом эффективность использования пропускной способности?