Суперканарейка в мире данных: Математики решили 30-летнюю загадку передачи информации

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

На протяжении следующих 30 лет были предприняты значительные попытки реализовать эту концепцию, однако разработка кода с такой особенностью, который был бы также практичным, оставалась недостижимой. Многие ученые считали, что идеальная форма локальной тестируемости никогда не будет достигнута. Однако в ноябре 2023 года группа исследователей во главе с Ирит Динур из Института Вейцмана в Израиле и математиков из Еврейского университета в Иерусалиме (Шаи Эвра, Рон Ливне, Алекс Любоцкий и Шахар Мозес) предложила решение , которое, по словам специалистов, является настоящим прорывом в этой области.

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

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

Основы кодирования и проблема шума

Шум — это неизбежная часть любой передачи данных. Информация в цифровом виде представляется как последовательность битов, состоящих из 0 и 1. Под воздействием шума некоторые из этих битов могут случайным образом изменяться. Примером может служить простой код 01, который при воздействии шума может стать 10. Чтобы справиться с этой проблемой, ученые разрабатывают так называемые коды для исправления ошибок. Один из простейших методов — это повторение каждого бита несколько раз. Например, если оригинальная информация состоит из 01, ее можно закодировать как 000111. Даже если несколько битов изменятся из-за шума (например, до 010110), получатель сможет восстановить оригинальное сообщение, используя простую проверку большинства (например, три нуля указывают на 0, три единицы — на 1).

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

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

Локальная тестируемость и графы

Идея локальной тестируемости появилась в 1990 году. Она заключалась в том, чтобы создать код, который можно было бы проверить на ошибки очень быстро, проверяя только небольшие фрагменты сообщения. Однако если код выбирался случайно, как рекомендовал Шеннон, он не мог быть локально тестируемым. Чтобы достичь локальной тестируемости, требовались более сложные математические структуры.

Здесь на помощь пришли графы. Сравнение кода с графом впервые предложил Ричард Хэмминг, который разработал известные коды для исправления ошибок в 1950-х годах. Он предложил проверять информацию с помощью дополнительных битов, называемых битами четности. Эти биты четности проверяют сумму определенных битов сообщения. Если сумма четная, бит четности становится 0, если нечетная — 1. Такие проверочные суммы и позволяют обнаруживать ошибки.

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

Прорыв с помощью многомерных графов

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

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

Результаты и значение открытия

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

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

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