Оптимальная коррекция ошибок для эры Интернета

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

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

На Симпозиуме IEEE по Основам компьютерной науки, в этом месяце, бывший и сегодняшний аспиранты MIT представят первую схему интерактивного кодирования, приближающуюся к оптимуму по всем трем указанным критериям.

«До этой работы было известно, как оптимизировать два из трех, — сообщил Мосен Гаффари (Mohsen Ghaffari), один из двух авторов доклада. — В данной статье это реализуется для них всех».

Более того, если в уже классическом анализе програм коррекции ошибок, проделанном в 1948 г. Клодом Шенноном, рассматривался случайный шум (все биты передаваемого кода имеют равную вероятность повреждения), Гаффари и его коллега Бернард Хоплер (Bernhard Haeupler) — выпускник MIT и доцент университета Карнеги-Мэллона, руководствовались моделью «атакующего шума» (adversarial noise), воздействующего на передачу наиболее разрушительным образом.

Алгоритм коррекции ошибок действует, добавляя к передаваемому сообщению дополнительную информацию. Это могут быть, например, биты, описывающие арифметические взаимосвязи между битами сообщения. В интерактивных коммуникациях максимальная допустимая частота ошибок — одна четвертая. Если повреждается больше четверти битов, надежные коммуникации становятся невозможны.

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