Многие слышали об оптоволокне и знают, что оно представляет собой магистральные каналы передачи данных (если хотите разобраться, как работает оптоволокно, вот отличный ликбез). По отповолокнам, проложенным по дну океанов, ежедневно прокачиваются Зетабайты гифок с котиками и AI слопа, а вероятность передать бит с ошибкой держиться на уровне 10^-10, т.е. один ошибочный бит (даже не байт) на 1 Гб данных. Естественно потребность в высокой скорости соединения неуклонно растёт и для оптоволокна повился свой аналог закона Мура, гласящий, что скорость передачи удесятеряется каждые 4 года. В этом цикле статей мы поговорим о том, есть ли предел скорости передачи данных для оптоволокна, попробуем его оценить и можно ли этот предел достигнуть на практике.

TL;DR

А нет его, я ещё не закончил писать весь цикл, так что он появится позже

Дисклеймер: я не претендую на математическую точность, а скорее на объяснение базовых идей на пальцах и базовых формулах, чтобы сформировать интуитивное понимание ограничений возникающих из теоретических и физических соображений.

Как я уже упомянул, скорость передачи удесеряется каждые 4 года. Это можно увидеть из графика внизу, которые показывает лабораторные рекорды. Разумеется, рекорд, установленный сегодня в лаборатории, не означает, что завтра можно прийти к себе домой и заказать тариф «10 петабит/с». Между лабораторным рекордом и конечным пользователем обычно проходит некоторое количество лет, протоколов, стандартизаций и других неприятных вещей.

Улучшение скорости передачи в оптоволокне со временем [1]. В качестве точек на графике используются рекордные скорости передачи данных представленных на OFC – ежегодной главной конференции людей, которые зачем-то решили всерьёз заниматься передачей информации по стеклу.
Улучшение скорости передачи в оптоволокне со временем [1]. В качестве точек на графике используются рекордные скорости передачи данных представленных на OFC – ежегодной главной конференции людей, которые зачем-то решили всерьёз заниматься передачей информации по стеклу.

Так как же можно достигнуть таких скоростей? Предстватьте, что вам нужно передать по оптоволокну какой-то файл как можно быстрее. Что можно улучшить в линии связи для этого? Оказывается вариантов всего три с половиной:

  1. Сжатие файла перед отправкой – очевидно, что отправка архива будет быстрее, так как нужно отправить меньше бит. Эта часть не касается передачи данных по оптоволокну и его ограничений, поэтому её в расчет скорости передачи не берем.

  2. Увеличить количество бит, передаваемых одним символом, N, далее мы обсудим что значит символ).

  3. Увеличить число символов, передаваемых в секунду, S.

  4. Использовать параллельно несколько независимых каналов в количестве K штук.

Итого, скорость передачи можно записать как:

R = N \times S \times K

Мы пройдем отдельно по каждому из компонентов, и в этой части мы поговорим о первых двух пунктах и о теоремах Шеннона для канала с шумом и без.

Как посчитать информацию?

В первую очередь нужно договориться о том, что такое информация в контексте линий связи и как её можно измерить. На этот вопрос смог ответить Клод Шеннон в своей знаменитой статье «A Mathematical Theory of Communication» (также сама диссертация очень приятна для чтения). Он рассмотрел следующую модель: пусть имеется источник случайности, полностью определённый набором исходов (который можно назвать алфавитом, а каждый отдельный исход символом) и вероятностями выбора каждого символа \{p_i\}. Это также означает, что выбор текущего символа не зависит от предыдущих или будущих выборов. Приёмник в свою очередь способен безошибочно различить все символы алфавита при измерении.

В такой модели Шеннон определил информацию как меру уменьшения незнания. Поскольку измерение однозначно определяет принятый символ, незнание снижается до нуля и, следовательно, полученная информация будет равна изначальному незнанию. Остаётся дело за малым: оценить меру незнания, известную также как информационная энтропия. Для этого постараемся ввести логичные требования на функцию H, приходящуюся в среднем на один символ:

  1. Она не должна зависеть от физической реализации алфавита. То есть H не зависит от того, передается ли информация как рукописный текст из трех символов или же как напряжения -5, 0 и 5 вольт в электрической цепи при однинаковом наборе вероятностей \{p_i\}.

  2. Эта функция должна быть непрерывной относительно \{p_i\}, т.е. малое изменение набора приведет к малому изменению незнания. На первый взгляд, это требование может показаться избыточным, поскольку при выводе формулы оно напрямую не используется, но оно необходимо для обобщения функции на случай иррациональных значений вероятностей.

  3. В случае, когда вероятности выбора символов равны между собой, увеличение количества символов в алфавите приведет к увеличению энтропии. Как частный пример этого правила рассмотрим алвафит с одним символом. Такой алфавит не несёт вообще никакой информации, так как получатель всегда будет знать какой символ ожидать; отправка символов получателю не добавит никакой информации. В случае с алфавитом размером 2 очевидно, что информация уже будет ненулевая, поскольку заранее не известно, что придет на приёмник, то есть незнание присутствует.

  4. Здесь я отойду от общепринятого изложения, так как в литературе обычно оно формулируется довольно сложно для понимания. В статье Шеннона дела обстоят лучше, но лично мне было не понятно из каких соображений он ввел своё требование. Поэтому я предлагаю такое условие (я проверял, и оно приводит к нужному результату; если я не прав, прошу в комментарии): энтропия принятого сообщения не должна поменяться, если из существующего алфавита создать другой, при сохранении взаимно-однозначного соответствия. Например, пусть имеется алфавит из 2 символов: «а» и «б». Из них можно создать новый алфавит: аа=А, аб=Б, ба=В, бб=Г. Если переписать текст написанный с помощью символов а и б, используя А, Б, В, Г, никакой новой информации не появится и никакая старая информациия не исчезнет.

И этот набор логичных требований очень удачный. Оказывается, что таким условиям удовлетворяет только одно семейство функций:

H(\{p_i\}) = -C\sum_{i=0}^N p_i \times \ln p_i

Константа перед суммой является произвольной и отражает свободу в выборе единиц измерения. По сути, с помощью этой константы можно менять основание логарифма, которое используется в формуле:

H' = \frac{1}{\ln C} H = -\sum_{i=0}^N p_i \times \frac{\ln p_i}{\ln C} = -\sum_{i=0}^N p_i \times \log_C p_i

Традиционно используется два основания:

  • число Эйлера, соответсвующая единица измерения наты

  • двойка, соответствующая единица измерения биты.

Более распространёной единицей является бит, поскольку он соответствует бинарному выбору, и его можно интерпретировать «физически»: энтропия задает нижнюю границу на среднее число да/нет-вопросов необходимых, чтобы узнать результат измерения.

Например, рассмотрим алфавит: {A: 0.1, B: 0.1, C: 0.4, D: 0.4}. Его энтропия составляет примерно 1.71 бита. Это значит, что при оптимальной стратегии в среднем нужно будет задать 1.71 вопроса, чтобы узнать принятый символ. В случае одного символа оптимальная стратегия будет следующей:

  • Это C? (Если да, то угадали за 1 вопрос, вероятность этого исхода 0.4, если нет идем к вопросу 2).

  • Это D? (Если да, то угадали за 2 вопроса (вероятность 0.4), если нет идем к вопросу 3).

  • Это A? (Это последний вопрос, независимо от ответа мы узнаем символ за 3 вопроса. Совокупная вероятность того, что мы дойдём до этого шага 0.2).

Итого, среднее число вопросов для такой стратегии составит: 1 * 0.4 + 2 * 0.4 + 3 * 0.2 = 1.8 вопроса, что больше энтропии этого источника, которая равна 1.71 бит. На первый взгляд кажется, что стратегия не оптимальна и должен быть подход получше. На самом деле, для одиночного символа лучшего результата достичь не удастся.

А, что если с помощью да/нет нужно узнать два символа? Можно спрашивать по отдельности про каждый символ и получить 3.6 вопросов при энтропии 3.42 Однако, если сменить стратегию, спрашивая сразу о комбинациях из двух символов, можно управиться в среднем, например, за 3.52 вопроса (или 1.76 вопроса на символ). По мере дальнейшего увеличения длины текста среднее число вопросов на символ будет стремиться к энтропии этого алфавита. Таким образом, значение энтропии достижимо, но только в пределе для очень длинных последовательностей.

Я думаю, что уже многие догадались, какое применение имеет эта часть теории непосредственно в информационных технологиях и передаче данных.

Во-первых, то, как хранится информация, идеально соответствует всему вышеописанному. Например, жесткий диск хранит целое число, состоящее из 8 символов принадлежащих алфавиту размером 2, в диапазоне от 0 до 255. Когда процессору нужно извлечь это число, он начинает играть в да/нет с жестким диском, который отвечает с помощью напряжения в цепи. Всего процессору понадобиться задать 8 вопросов, чтобы узнать, что это за число, а значит 8 бит информации. Поэтому такие числа и называют 8-битными.

Во-вторых, информационная энтропия задаёт теоретический предел для сжатия данных без потерь. В случае случайной равновероятной последовательности бит, сжать не получиться вообще ничего так как один «бит-символ» несет ровно один бит информации. В дальнейшем мы будем считать, что по оптоволокну передается именно такая информация.

А теперь пошумим

На практике в любом канале связи присутствуют помехи и шумы, которые искажают переданные символы. Поэтому начнём с такой модели: передатчик отправляет набор символов \{x_i\}, а на приёмнике мы получаем набор \{y_j\}. При этом мы вольны выбирать как выбирать символы из алфавита, т.е. \{p(x_i)\} можно менять, а также свойства канала полностью известны, то есть мы знаем распределение вероятностей {p(y_j|x_i)}, где p(y_j|x_i) - это вероятность, что на приёмнике мы получим y_j при условии, что был отправлен символ x_i.

Сколько информации сможет передать такой канал?

Для этого сначала оценим, сколько незнания об отправленном символе остаётся у приемника после того, как он получил y_j. Зная набор \{p(x_i)\} и \{p(y_j|x_i)\}, по теореме Байеса можно посчитать набор вероятностей \{p(x_i|y_j)\}, то есть вероятности того, что был отправлен символ x_i при условии, что был принят символ y_j. Таким образом, для каждого y_j мы опять имеем набор вероятностей на множестве символов \{x_i\}. А значит можем посчитать количество незнания об отправленном символе, при условии, что на приёмнике был получен y_j:

H(\{x_i\}|y_j) = \sum_i p(x_i|y_j) \ln p(x_i|y_j)

Но на приёмнике мы получаем разные символы y_j с вероятностями p(y_j) (которые тоже можно посчитать). Поэтому нам нужно величину выше усреднить по различным принимаемым символам y_j, чтобы оценить сколько у приёмника остаётся незнания в среднем (эта величина также называется условной энтропией):

H(\{x_i\}|\{y_j\}) = \sum_j p(y_j) H(\{x_i\}|y_j)

Вспомнив, что информация - это мера уменьшения незнания, можно вычислить, какое количество информации в среднем получает приёмник, как разность между изначальным незнанием (до приёма символов), которое равно энтропии источника, и оставшимся незнанием после приёма символов:

I(\{x_i\}|\{y_j\}) = H(\{x_i\}) - H(\{x_i\}|\{y_j\})

Эта величина известна как взаимная информация, и она показывает, сколько информации о величине y имеет приёмник при доступе к величине x (и наоборот, так как она симметрична). Как правило, из такого канала необходимо выжать максимум. Поскольку у нас есть свобода в выборе \{p(x_i)\}, пропускная способность канала вычисляется как максимум взаимной информации по всем возможным распределениям входных символов (по сути, эта максимизация — это своего рода перекодировка данных, которые нужно отправить, учитывающая свойства канала):

C = \max_{\{p(x_i)\}} I(\{x_i\}|\{y_j\})

Самым простым примером, для того чтобы проиллюстрировать, как все работает, является бинарный симметричный канал, где передатчик отправляет 0 или 1, а канал с вероятностью e изменяет значение бита, а получатель измеряет пришедшее значение бита. В этом случае максимум взаимной информации достигается, если 0 и 1 отправляются с вероятностью 0.5, и равен:

I_{BSC} = -e\log e - (1-e) \log (1-e)

Рассмотрим частные случаи. Если e = 0, то взаимная информация равна 1. По сути канал передает сообщение без искажений, и один символ-бит успешно передает 1 бит информации. Занимательно, что если канал будет инвертировать каждый входящий бит, то взаимная информация останется равна 1, так как в этом случае, чтобы восстановить всю информацию, достаточно инвертировать пришедший сигнал.

То есть канал, который всегда ошибается, может передавать столько же информации, сколько идеальный канал. Потому что проблема не в самом факте ошибки. Проблема в непредсказуемости ошибки.

Гораздо интереснее, когда вероятность ошибки отлична от 0 или 1. Например для вероятности в 11% взаимная информация будет равна 0.5. То есть на один переданный символ-бит придётся в среднем полбита информации.

Ситуация странная: с одной стороны нам отправляют по каналу 1000 бит, мы получаем в среднем 110 битов с ошибками и 890 битов без ошибок. А с другой стороны теория информации нам говорит, что у нас в распоряжении на самом деле только 500 бит информации. Кажется, что теория информации украла у нас целых 890-500=390 бит. Выглядит как заговор телеком-операторов, чтобы брать с нас лишние деньги за Интернет.

Однако появление ещё одной конспирологической теории придётся отложить. Проблема в том, что приёмник должен восстановить исходное сообщение. Если передатчик отправил 01001101, а приёмник получил 01011101, то сам по себе приёмник не знает, какой из битов неправильный.

Можно, конечно, сделать самый тупой и надёжный алгоритм:

  1. Передатчик отправляет сообщение.

  2. Приёмник получает его.

  3. Они созваниваются.

  4. Сравнивают каждый бит.

  5. Приёмник исправляет ошибки.

Работает!

Но есть маленькая проблема.

Для передачи данных через канал мы почему-то хотели избежать необходимости сначала передавать те же самые данные ещё раз.

Поэтому нужен другой способ.

Коррекция ошибок

Самый простой способ заключается в дублировании символов, то есть вместо отправки единичного символа мы отправляем три его копии. Таком образом, если мы хотим отправить сообщение 010, то по каналу нужно отправлять 000 111 000. Приёмник решает какой бит был отправлен смотря на то, каких битов в тройке оказалось больше. В этом случае, если изначальная вероятность ошибки равна e, то вероятность ошибиться на приёмнике будет e^3 [все биты перевернулись] + 3 e^2 [два из трех перевенулись]. Для 11% процентов ошибок в канале такая кодировка даст 3% ошибок на выходе. Все ещё не 0%, но лучше чем было.

Что при таком подходе происходит с точки зрения теории информации? А точнее какова будет энтропия переданного сообщения 000 111 000? Она будут равна энтропии изначального сообщения, по свойству 3. А вот, что изменится так это количество информационных бит на переданный символ с 1 до 1/3, поскольку теперь 3 символа несут 1 бит информации. То есть, пожертвовав количеством бит на символ или скоростью передачи информации, мы снизили количество ошибок. Возникает вопрос: можно ли, понижая количество битов на символ, добиться передачи без ошибок? И если да, то как сильно нужно понизить скорость передачи для этого?

На этот вопрос отвечает теорема Шеннона о канале с шумом, из которой следует, что количество информации на один символ N не должно превышать пропускную способность канала:

N \leq C

Это теорема, опять же, выполняется в пределе большого количества бит. Так, например, в нашем примере с e=0.11 (C \approx 0.5), чтобы передать 1000 изначальных бит, нам понадобится передать в общей сложности около 2000 бит (включая избыточные), чтобы можно было скорректировать ошибки.

Ещё один интересный частный случай находится в точке e=0.5. В этом случае взаимная информация равна нулю. Это значит, что такой канал вообще не передает никакой информации и не существует кода коррекции ошибок, который мог бы это исправить. На этом занимательном факте базируется криптографическая стойкость шифра Вернама (побитовый XOR со случайной битовой строкой, также известного как «одноразовый блокнот»).

К сожалению, теорема Шеннона о канале с шумом не конструктивна, т.е. она говорит «Хорошие коды существуют», а не «Вот вам файл shannon_code.fec, скачайте и пользуйтесь». К счастью, хорошие коды были найдены: например, коды Хэмминга (относительно короткие по длине и поэтому далеки от теоретического предела), БЧХ-коды и стандарт в телеком индустрии сейчас, LDPC коды (довольно длинные используются блоки длинной в 16 и 64 тысяч символов), которые заслуживают отдельной статьи. Как правило сообщение состоит из оригинальных битов и дополнительных бит, которые являются различными суммами по модулю два оригинальных бит.

В этом кратком математическом вступлении мы формализовали понятия незнания и информации и как их можно измерить с помощью игры в «угадайку»: сколько в среднем вопросов «да/нет» нужно задать, чтобы узнать сообщение, а также как передавать сообщения через каналы с помехами. В следующей части мы уже добавим щепотку физики и поговорим о передаче символов по оптоволокну и какие шумы ограничивают количество информационных бит на символ.

Stay tuned!

  1. Richardson, D., Fini, J. & Nelson, L. Space-division multiplexing in optical fibres. Nature Photon 7, 354–362 (2013). https://doi.org/10.1038/nphoton.2013.94