Предел Шеннона: как телекоммуникации "выбрались" из килобитной скорости

В начале 1980-х годов производители электронного оборудования столкнулись с препятствием. Только начавший набирать силу рынок персональной компьютерной техники нуждался в повышении скорости передачи информации по телефонным сетям, но на долгие годы модемы "застряли" на 9,6 Кбит/с: стоило попытаться пойти дальше – и возникало недопустимое количество ошибок. Позже группа инженеров продемонстрировала корректирующие коды, способные повысить скорость на 25%. Многих интересовали вопросы, насколько вообще можно увеличить критический параметр, и что это собственно за коды.

Ответу на первый вопрос к тому моменту исполнилось более 30 лет. Его дал в 1948 году Клод Шеннон (Claude Shannon) в статье, положившей начало дисциплине о теории информации. По словам профессора Лаборатории информации и систем принятия решений Массачусетского технологического института (MIT’s Laboratory for Information and Decision Systems) Дэвида Форни (David Forney), ознакомленные с работой Шеннона считали её самой выдающейся из того, что им приходилось видеть. Преподававший с 1956 по 1978 годы в MIT знаменитый учёный высказал идею, что любой телекоммуникационный канал – телефонная линия, радиодиапазон, оптоволоконный кабель – может быть описан двумя значениями: полосой пропускания и шумом. Первый параметр является диапазоном электрических, оптических или электромагнитных частот, которые могут быть использованы для передачи сигнала; второй – это факторы, препятствующие распространению сигнала. Взяв канал с определёнными характеристиками, Шеннон показал, как рассчитать максимальную скорость передачи с практически нулевым количеством ошибок. Он назвал её пропускной способностью (сегодня чаще применяется понятие предела Шеннона) и подтвердил, что вне зависимости от шума информацию можно передать.

В зашумленном канале единственный путь достигнуть безошибочности – это добавление некоторой избыточности. Например, если была попытка передать сообщение из трёх битов 001, можно послать его трижды: 001001001. В случае ошибки принимающая сторона получит 001011001, но восстановить изначальное 001 возможно. Любой такой метод добавления чрезмерной информации для исправления ошибок относится к корректирующим кодам. Чем более зашумлён канал, тем больше необходимо "лишних" данных. С увеличением кода скорость падает – то же изначальное сообщение становится больше, но без "полезной нагрузки". Поэтому идеальный код должен минимизировать количество служебных битов и максимизировать вероятность коррекции ошибок. Посылать одинаковую информацию трижды идеальным выходом определённо не является. Скорость падает на 2/3, а уязвимость остаётся: две ошибки в правильных точках сделают сообщение невосстановимым. Но Шеннон был уверен, что возможен иной подход. Он доказал существование для любого канала такого кода минимальной длины, который максимально близко позволяет подойти к названному его именем пределу и достичь максимально возможной скорости.

Однако доказательство не поясняло, как именно создать подобный код. Вместо этого за основу бралась вероятность. Пусть требуется передать сообщение их четырёх битов. Есть 16 возможных вариантов их комбинаций. Идея Шеннона состояла в назначении каждому случайного кода – своеобразного серийного номера. Если рассматривать достаточно шумный канал, четырём битам понадобится восьмибитный дополнительный код. Получатель, как и отравитель, должен иметь кодовую книгу соответствия 16 возможных сообщений 16 восьмибитным кодам. Поскольку есть 256 комбинаций 8 бит, остаётся 240, не включённых в книгу. Если на принимающей стороне появится один из этих 240 вариантов, значит в данные закралась явная ошибка. Но среди 16 разрешённых только один код может совпадать с полученным, который отличается, например, одной цифрой. Как продемонстрировал Шеннон, если назначить все возможные случайные коды сообщениям, среди них должен быть наиболее близко достигающий пропускной способности. Чем длиннее код, тем ближе: восьмибитные здесь не помогут, зато коды из двух тысяч бит для сообщений из тысячи – вполне. Конечно, подобная схема абсолютно непрактична. Кодовая книга со случайными значениями для всех вариантов сообщения длиной в тысячу бит не уместится на всех накопители всех компьютеров мира, однако была подтверждена принципиальная возможность поиска путей разработки эффективных кодов коррекции. Поиск продолжался до 1990-х годов, но только потому, что одно из лучших предложений, появившееся намного раньше, было проигнорировано.

В 1980-х годах были сделаны некоторые усовершенствования технологий, позволившие поднять скорость модемов до 14,4 Кбит/с. Все предлагавшиеся коды наталкивались на ограничение, называемое вычислительной скоростью отсечения (computational cutoff rate). Она варьировалось в зависимости от мощности передачи и шумовых характеристик канала, но на практике была вдвое меньше предела Шеннона. В 1993 году на конференции IEEE (Institute of Electrical and Electronics Engineers – Институт инженеров по электротехнике и радиоэлектронике) Алан Главиу (Alain Glavieux) и Клод Берро (Claude Berrou) представили новый набор кодов, согласно их оценке приближавшихся к заветному значению. Как рассказывает профессор компьютерных наук в MIT Мюриел Медар (Muriel Médard), их не воспринимали всерьёз, тем более что эти исследователи специализировались на электронике, а не кодах. Их "турбокоды" появились в результате проб и ошибок и не имели формального пояснения, но изучение быстро устранило скепсис. Это так называемые итеративные коды, когда декодер совершает серию предположений о том, каким должно быть закодированное сообщение. Каждое успешное "угадывание" повышает результаты декодера. Пытаясь объяснить превосходные показатели турбокодов, исследователи через несколько лет натолкнулись на работы Роберта Галлагера (Robert Gallager) 30-летней давности.

Преимущества кодов воспитанника MIT так долго недооценивались из-за сложности предложенного им алгоритма для существовавших тогда технологий, хотя Галлагер как раз руководствовался стремлением к простоте. Он использовал биты чётности – дополнительные биты, содержащие информацию о сообщении. Один из них может, например, говорить о чётности или нечётности суммы 1,2 и 4 битов передаваемых данных, а другой служить таким же "ключом" для 3,4 и 6, и так далее. Правильная информация о любых двух битах в трио передаёт достоверную о третьем. Итеративные техники придают "вес" некоторому полученному биту в соответствии с тем, насколько достоверно он был "угадан". Затем в процессе контроля чётности он вовлекается в проверку других битов, и его достоверность повышается. Но методика имеет недостаток с ложным положительным ростом достоверности, который по словам Форни можно описать как эффект слуха – когда он слышен отовсюду, начинает казаться правдой, хотя он лишь ходит по замкнутому кругу. Галлагер использовал схему с ограниченной проверкой на чётность – LDPC-код (Low-density parity-check code), значительно упростивший вычисления. Сегодня коды Галлагера наиболее близко подбираются к лимиту Шеннона для любого канала. Они интегрированы в стандарты беспроводной связи и цифрового ТВ, а относящиеся к декодированию чипы можно найти в мобильных телефонах.