Квантовые вычисления - Стин Э.
Скачать (прямая ссылка):
(т\(п - т)\)
Вышеупомянутые рассуждения приводят к практически важному результату,
связанному с уравнением (1): для передачи п значений величины X
необходимо переслать по каналу связи nS(X) ^ п битов. Такой метод
называется сжатием информации, а сама идея подобной связи называется
теоремой бесшумного кодирования Шэннона.
Идея типичных последовательностей привела к появлению способов изменения
объема информации, но сам метод сжатия информации не является лучшим,
поскольку Алисе необходимо накопить большое количество значений величины,
перед тем как передать Бобу какую-либо информацию. Более удачный способ
связи заключается в накоплении Алисой нескольких значений, например,
четырех, и передаче их как одного "сообщения" наиболее удобным методом.
Хаффман установил оптимальный метод, согласно которому Алиса использует
короткие наборы битов для передачи наиболее вероятных "сообщений" и более
2.2. Сжатие информации
29
Сообщение Хаффман Хамминг
0000 10 0000000
0001 000 1010101
0010 001 0110011
0011 11000 1100110
0100 010 0001111
0101 11001 1011010
0110 11010 0111100
0111 1111000 1101001
1000 011 1111111
1001 11011 0101010
1010 11100 1001100
1011 111111 0011001
1100 11101 1110000
1101 111110 0100101
1110 111101 1000011
1111 1111001 0010110
Таблица 1. Коды Хаффмана и Хамминга. В левом столбце представлены
шестнадцать возможных четырехбитовых сообщений, в двух оставшихся
столбцах показаны закодированные варианты сообщений. Код Хаффмана
соответствует сжатию информации: содержащие наименьшее количество битов
коды соответствуют наиболее вероятным сообщениям. Код соответствует
случаю, когда вероятность появления нуля в сообщении в три раза больше
вероятности появления единицы. Код Хаффмана является кодом, исправляющим
ошибки: каждое кодовое слово отличается от любого другого по крайней мере
в трех местах. Таким образом, возможно исправление одной ошибки. Кроме
того, код Хамминга является линейным: все слова являются линейными
комбинациями чисел 1010101, 0110011, 0001111, 1111111
длинные наборы для передачи менее вероятных сообщений (см. таблицу 1).
Процесс трансляции состоит из "кодирования" и "декодирования" (см. рис.
4). Такая терминология не вызывает никакого желания держать информацию в
тайне.
Согласно теореме бесшумного кодирования Шеннона, при вероятности р,
равной с использованием лучшей методики сжатия информации необходимо в
среднем 4~ 3,245 битов для передачи сообщения, состоящего из четырех
значений величины X. В коде Хаффмана, приведенном в таблице 1,
используется в среднем 3,273 бита. Это число,
30
Глава 2
Кодирование
Раскодирование
Рис. 4. Стандартный канал связи ("герб информационного террориста").
Источник (Алиса) формирует информацию, оперирует ею ("кодирует") и
пересылает по каналу. На приемнике (Боб) происходит "дешифрация"
полученных значений и извлечение информации
близкое к минимально возможному, указывает на большую эффективность
методов, подобных методу Хаффмана.
Сжатие информации - это понятие, имеющее огромное практическое значение.
Оно используется в телесвязи, например, при сжатии информации,
необходимой для передачи изображения в память компьютера. Сжатие
информации, с точки зрения проектирования каналов связи, является
уникальным инструментом. Предположим, что имеется телефонная линия в
гористой местности, однако ее пропускная способность недостаточна,
скажем, для передачи активного видео изображения. Типичное инженерное
решение заключается в замене линии другой, имеющей более высокую скорость
передачи. Однако вместо этого теория информации предлагает использовать
ту же линию, но для передачи обработанной информации (подвергнутой сжатию
и декомпрессии на разных концах линии). Довольно неожиданно то, что
пригодность кабеля зависит не только от него самого, но и от способа
обработки передаваемой информации.
2.3. Двоичный симметричный канал
До настоящего момента рассматривались лишь случаи связи по идеальному
каналу, т. е. по каналу без помех (noise-free channel). Также были
получены важные результаты, имеющие практическое значение: найдена мера
максимально возможного сжатия информации (теорема бесшумного кодирования
Шеннона) и практический метод сжатия информации (кодирование Хаффмана).
Теперь необходимо рассмотреть другой важный вопрос: связь с помехами. Как
и в предыдущем разделе, будет рассмотрен простейший пример с целью
проиллюстрировать общие принципы.
Предположим, что имеется двоичный канал, т. е. такой канал, по которому
Алиса может передавать Бобу нули и единицы. При исполь-
2.3. Двоичный симметричный канал
31
зовании канала без помех нулю или единице на выходе соответствуют ноль
или единица на входе (0 -? 0 и 1 -? 1). Однако, в случае канала с
помехами, единица может стать нулем, и наоборот. Существует множество
типов помех. Например, вероятность ошибочного "переброса бита" из
значения 0 в значение 1 (0 -> 1) должна совпадать с вероятностью
