Полярні коди

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

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

Особливості

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

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}}.

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

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

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

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

Див. також

Примітки

↑ ^а ^б ^в ^г E. Arikan, "Channel Polarization: A Method for Constructing Capacity-Achieving Codes for Symmetric Binary-Input Memoryless Channels, " IEEE Transactions on Information Theory, vol.55, no.7, pp.3051-3073, July 2009.
↑ Kalai, Gil (25 листопада 2010). Emmanuel Abbe: Erdal Arıkan’s Polar Codes. Combinatorics and more. Процитовано 26 січня 2017.(англ.)
↑ Слюсар В. И. Синтез LDPC и полярных кодов на основе торцевого произведения матриц.// Розвиток освіти, науки та бізнесу: результати 2020: тези доп. міжнародної науково-практичної інтернет-конференції, 3 — 4 грудня 2020 р. — Україна, Дніпро, 2020. — Т.2. — С. 393—396. [1].
↑ Polar Codes — A New Paradigm for Coding (PDF). Архів оригіналу (PDF) за 6 вересня 2015. Процитовано 30 січня 2021.

Посилання

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.(англ.)

[Arikan-1] а ^б ^в ^г E. Arikan, "Channel Polarization: A Method for Constructing Capacity-Achieving Codes for Symmetric Binary-Input Memoryless Channels, " IEEE Transactions on Information Theory, vol.55, no.7, pp.3051-3073, July 2009.

[2] Kalai, Gil (25 листопада 2010). Emmanuel Abbe: Erdal Arıkan’s Polar Codes. Combinatorics and more. Процитовано 26 січня 2017.(англ.)

[3] Слюсар В. И. Синтез LDPC и полярных кодов на основе торцевого произведения матриц.// Розвиток освіти, науки та бізнесу: результати 2020: тези доп. міжнародної науково-практичної інтернет-конференції, 3 — 4 грудня 2020 р. — Україна, Дніпро, 2020. — Т.2. — С. 393—396. [1].

[4] Polar Codes — A New Paradigm for Coding (PDF). Архів оригіналу (PDF) за 6 вересня 2015. Процитовано 30 січня 2021.

[1]

[2]

[3]

[4]