1. Сравните равномерные и неравномерные коды: какие достоинства и недостатки имеет каждый тип?
Равномерные и неравномерные коды отличаются длиной кодовых слов. В равномерных кодах все слова имеют одинаковую длину, что упрощает обработку и делает их удобными для хранения и передачи данных, но увеличивает избыточность. Неравномерные коды позволяют сократить среднюю длину сообщения, используя короткие кодовые слова для частых символов, но требуют дополнительных методов разделения символов (например, условия Фано или префиксного кода).
2. Сколько можно построить различных двоичных кодов длиной 5 бит? 7 бит? 10 бит?
5 бит → 2⁵ = 32 7 бит → 2⁷ = 128 10 бит → 2¹⁰ = 1024
3. Какую длину кодового слова нужно выбрать для двоичного кодирования, если алфавит исходного сообщения включает: а) 16 символов; в) 56 символов; б) 25 символов; г) 256 символов?
16 символов → log₂16 = 4 → 4 бита 25 символов → log₂25 ≈ 4,64 → округляем до 5 бит 56 символов → log₂56 ≈ 5,8 → округляем до 6 бит 256 символов → log₂256 = 8 → 8 бит
4. Попробуйте придумать для кодирования слова ГАГАРА другой (не такой, как на рис. 2.11) неравномерный код, для которого выполняется условие Фано.
Неравномерный код для слова "ГАГАРА" с условием Фано должен быть префиксным (ни одно кодовое слово не является началом другого). Возможный вариант:
Г = 0 А = 10 Р = 11 Тогда слово "ГАГАРА" кодируется как 0 10 0 10 11 10. Этот код удовлетворяет условию Фано, так как никакое кодовое слово не является префиксом другого.
5. В середине XX века в СССР был выпущен троичный компьютер, в котором все данные хранились в троичном коде (использовались три символа: 0, 1 и –1). а) Определите, сколько различных кодовых слов можно записать в троичном коде длиной L. б) Какую длину равномерного троичного кода нужно выбрать, чтобы перекодировать сообщение на русском языке? в) Запишите условие выбора длины L равномерного троичного кода для предыдущей задачи в виде неравенства.
а) Для троичного кода, где используются три символа (0, 1 и -1), количество различных кодовых слов длиной L будет равно:
3^L
где L — длина кодового слова.
б) Для перекодирования сообщения на русском языке, необходимо выбрать длину троичного кода, которая сможет закодировать все символы алфавита. В русском языке 33 буквы, а также возможны пробелы и знаки препинания. Для простоты, допустим, что нужно закодировать 33 символа.
Для троичного кода длина кодового слова должна быть такой, чтобы 3^L было больше или равно 33. То есть:
3^L ≥ 33
Посмотрим, для какого L это выполняется:
3^3 = 27 (меньше 33) 3^4 = 81 (больше 33) Таким образом, для кодирования русского алфавита и дополнительных символов нужно выбрать длину 4.
в) Условие выбора длины L для перекодирования сообщения будет:
3^L ≥ N, где N — количество символов, которые нужно закодировать (в данном случае N ≥ 33).