Раздел A • Категория A9 (демонстрационный вариант-2012)
Условие задачи
Дано:
для кодирования некоторой последовательности, состоящей из букв А, Б, В , Г и Д, решили использовать неравномерный двоичный код, позволяющий однозначно декодировать двоичную последовательность, появляющуюся на приёмной стороне канала связи.
Использовали код:
А–1;
Б–000;
В–001;
Г–011.
Вопрос:
укажите, каким кодовым словом должна быть закодирована буква Д. Длина этого кодового слова должна быть наименьшей из всех возможных. Код должен удовлетворять свойству однозначного декодирования.
Варианты ответа:
00
01
11
010
Теоретические сведения
Кодирование информации – преобразование передаваемых данных на специализированные кодовые слова.
Кодовое слово – сепаратная комбинация допустимых алфавитом символов.
Существует равномерное и неравномерное кодирование. При использовании равномерного кодирования все символы кодируются кодами одинаковой длины, а при неравномерном кодировании символы могут кодироваться кодами различной длины.
Решение
А | Б | В | Г | Д |
1 | 000 | 001 | 011 | ? |
Последовательно переберем все предложенные кодовые слова.
Предположим, что Д = 00 (первый вариант ответа).
В данном случае фрагмент В = 001 можно представить как сумму двух составляющих 00 и 1, которые в свою очередь являются значениями фрагментов Д и А, что приводит к неоднозначности кодирования. То есть, если будет дана последовательность 001, то мы не сможем однозначно сказать, из каких фрагментов она строится. Следовательно, фрагмент Д не может принимать значение равное 00.
Предположим, что Д = 01 (второй вариант ответа).
В данном случае фрагмент Г = 011 можно представить как сумму двух составляющих 01 и 1, которые в свою очередь являются значениями фрагментов Д и А, что приводит к неоднозначности кодирования. То есть, если будет дана последовательность 011, то мы не сможем однозначно сказать, из каких фрагментов она строится. Следовательно, фрагмент Д не может принимать значение равное 01.
Предположим, что Д = 11 (третий вариант ответа).
В данном случае фрагмент Д = 11 можно представить как сумму двух составляющих 1 и 1, которые в свою очередь являются значениями одного и того же фрагмента А, что приводит к неоднозначности кодирования. То есть, если будет дана последовательность 11, то мы не сможем однозначно сказать, из каких фрагментов она строится. Следовательно, фрагмент Д не может принимать значение равное 11.
В итоге, методом исключения неподходящих вариантов, мы вышли на правильный ответ, это ответ под номером четыре. Но давайте, для пущей уверенности верифицируем и данный вариант.
Пусть Д = 010. Очевидно, что последовательность 010 никак нельзя заменить другой комбинацией значений, используя фрагменты А, Б, В или Г. Следовательно, Д = 010, то кодовое слово, являющееся ответом к поставленной задаче.
Вывод: |
кодовым словом 010 должна быть закодирована буква Д, чтобы удовлетворять свойству однозначного кодирования. |
Ответ: |
4 |
Комментарии