YaChudo

Полярні коди

Переглядів: 0. Оновлено 01.11.2026.

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

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

Особливості

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

F = [ 1 0 1 1 ] {\displaystyle F={\begin{bmatrix}1&0\\1&1\\\end{bmatrix}}} .

Наприклад,

[ 1 0 1 1 ] ⊗ [ 1 0 1 1 ] = [ 1 [ 1 0 1 1 ] 0 [ 1 0 1 1 ] 1 [ 1 0 1 1 ] 1 [ 1 0 1 1 ] ] = [ 1 × 1 1 × 0 0 × 1 0 × 0 1 × 1 1 × 1 0 × 1 0 × 1 1 × 1 1 × 0 1 × 1 1 × 0 1 × 1 1 × 1 1 × 1 1 × 1 ] = [ 1 0 0 0 1 1 0 0 1 0 1 0 1 1 1 1 ] . {\displaystyle {\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 ) {\displaystyle O(n\log n)} , що доказово досягають пропускної здатності дискретних бінарних симетричних каналів без пам'яті. Прикладом таких дискретних каналів є двійковий симетричний канал або двійковий канал зі стиранням.

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

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

Див. також

Примітки

  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.

Посилання

Джерело: стаття у Вікіпедії та історія редагувань (автори).