Полярні коди

Полярні коди (англ. polar code) — коди, які призначені для передавання інформації каналом зв'язку, являють собою окремий випадок блокового лінійного коду, що спирається на ефект поляризації каналу.

Полярні коди були запропоновані у 2009 році Ердалом Аріканом як система кодування, що забезпечує математичну основу для вирішення проблеми пропускної здатності каналу Шеннона.

Особливості

Для формування поляризаційних кодів використовується кратний добуток Кронекера кількох поляризаційних матриць

$F={\begin{bmatrix}1&0\\1&1\\\end{bmatrix}}$.

Наприклад,

${\begin{bmatrix}1&0\\1&1\\\end{bmatrix}}\otimes {\begin{bmatrix}1&0\\1&1\\\end{bmatrix}}={\begin{bmatrix}1{\begin{bmatrix}1&0\\1&1\\\end{bmatrix}}&0{\begin{bmatrix}1&0\\1&1\\\end{bmatrix}}\\1{\begin{bmatrix}1&0\\1&1\\\end{bmatrix}}&1{\begin{bmatrix}1&0\\1&1\\\end{bmatrix}}\\\end{bmatrix}}={\begin{bmatrix}1\times 1&1\times 0&0\times 1&0\times 0\\1\times 1&1\times 1&0\times 1&0\times 1\\1\times 1&1\times 0&1\times 1&1\times 0\\1\times 1&1\times 1&1\times 1&1\times 1\\\end{bmatrix}}={\begin{bmatrix}1&0&0&0\\1&1&0&0\\1&0&1&0\\1&1&1&1\end{bmatrix}}.$

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

Особливістю кодів є відносно мала щільність значущих елементів матриці перевірки, за рахунок чого досягається відносна простота реалізації засобів кодування. Разом з тим, полярні коди вважаються першими відомими кодами з субквадратичною обчислювальною складністю кодування і декодування $O(n\log n)$, що доказово досягають пропускної здатності дискретних бінарних симетричних каналів без пам'яті. Прикладом таких дискретних каналів є двійковий симетричний канал або двійковий канал зі стиранням.

Застосування

Полярні коди розглядалися в якості претендентів на застосування у стандарті стільникового зв'язку 5G NR, однак поступилися при розробці відповідного стандарту кодам LDPC. Окремі фахівці вважають полярні коди оптимальними для стиснення даних з втратами.

Див. також

• LDPC
• Турбо-код

Посилання

• Simons Institute (20 січня 2015), Erdal Arikan. Polar Codes I, процитовано 26 січня 2017(англ.)
• Simons Institute (20 січня 2015), Erdal Arikan. Polar Codes II, процитовано 26 січня 2017(англ.)
• Simons Institute (20 січня 2015), Erdal Arikan. Polar Codes III, процитовано 26 січня 2017(англ.)
• Polar Codes I | Simons Institute for the Theory of Computing. simons.berkeley.edu (англ.). Процитовано 26 січня 2017.(англ.)