Поляризовані коди: досягнення ємності Шеннона

Проблема, яку Шеннон не вирішив

Теорія Шеннона про шумні канали 1948 року доводить, що будь-який канал зв’язку має максимальну надійну швидкість – його ємність, і існують коди, які наближаються до неї з випадною ймовірністю помилок. Однак цей доказ не надавав практичного способу побудови таких кодів — це був доказ існування через випадкове кодування, а не конструкція. Понад шістдесят років інженери використовували коди (згорткові, турбо, LDPC), які дуже добре наближалися до ємності в практиці, але без доказу їх досягнення та без простої виразної конструкції.

Arikan's ядро and channel polarization

Erdal Arikan's 2009 paper changed that with a deceptively simple idea: combine two independent copies of the same channel using a small 2x2 transform, then recursively combine 2 into 4, 4 into 8, and so on. The building block is:

F = [ 1 0 ] G_N = F^(kron n), N = 2^n [ 1 1 ] n=1: combine 2 uses of the channel -> 2 synthetic channels n=2: combine 4 uses of the channel -> 4 synthetic channels ... As N grows, the synthetic channel capacities spread apart: a fraction ~C of them approach capacity 1 (perfectly reliable) the rest approach capacity 0 (useless) — very few stay in between This spreading-apart is channel polarization, and it is the whole trick: as N grows large, the fraction of synthetic channels that become almost noise-free approaches exactly the original channel's Shannon capacity C. Nothing about the underlying physical channel changed — the polarization is purely a property of how the recursive combining interacts with the channel's statistics.

F = [ 1  0 ]        G_N = F^(kron n),   N = 2^n
    [ 1  1 ]

n=1: combine 2 uses of the channel  -> 2 synthetic channels
n=2: combine 4 uses of the channel  -> 4 synthetic channels
...
As N grows, the synthetic channel capacities spread apart:
a fraction ~C of them approach capacity 1 (perfectly reliable)
the rest approach capacity 0 (useless) — very few stay in between

Заморожування слабких каналів

Будівельний етап коду Поля полягає в наступному: ранжуйте N синтетичних каналів за надійністю, розмістіть фактичні біти інформації на приблизно N·C найнадійніших, та заморозьте решту – встановивши їх на відоме значення, зазвичай нуль, узгоджене заздалегідь між передавачем і приймачем. Оскільки заморожені позиції не несуть інформації, але все ще відомі декодеру, вони діють як вбудована резервна копія саме там, де канал найслабший, та інформація передається лише тоді, коли вона може вижити. Обчислення того, які канали є надійними (щільність еволюції, або простіша оцінка за допомогою гаусового розподілу та параметрів Біттахарі), також є добре вивченим та ефективним попереднім обчисленням.

Послідовне скасування декодування

Збірковий декодер, послідовне скасування (SC), використовує ту саму рекурсивну структуру: він декодує біти по одному в фіксованому порядку, і кожен прийняття залежить від усіх попередньо декодованих бітів, точно так само, як і збудовуючий канал. Декодування SC має складність O(N log N), яка відповідає вартості кодування O(N log N) рекурсивного ядра — але само по собі декодування SC сходиться до ємності лише тоді, коли N стає дуже великим, і на практичних довжинах блоків його несвідома помилка відстає від усталених кодів. Виправлення, яке широко використовується в розгортанні, це декодування SC-List: відстежуйте кілька кандидатів для декодування паралельно замість одного та використовуйте доданий CRC для вибору життєвого шляху, який проходить перевірку. Ця комбінація зробила коди полярності конкурентоспроможними на практиці, а не лише в асимптотичному доведенні.

Від теореми до стандарту

У 2016 році 3GPP обрало коди Поля для контрольних каналів 5G New Radio, зробивши їх першим кодом, що досягає ємності, з чіткою конструкцією та формальним доказом, який було розгорнуто в глобальному комунікаційному стандарті — надзвичайно швидкий перехід від теоретичного паперу до мільярдів телефонів, і прямий результат конструктивного, рекурсивного дизайну, який зробив як кодер, так і декодер SC-List достатньо ефективними для реалізації в кремнії.

Frequently asked questions

Спробуйте наживо

Усе, що вище, працює прямо у вашому браузері — відкрийте Polar Codes і змінюйте параметри під час роботи. Нічого не встановлюється, нічого не завантажується на сервер, уся модель живе в одній вкладці.