Polar码快速入门

2023-10-14 05:38
文章标签 入门 快速 polar

本文主要是介绍Polar码快速入门,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

Polar码快速入门

本科生在学习极化码时,并不是件简单的事情。网上极化码的资料很少,而且基本上都是较难的论文。这篇文章是用来帮你快速入门极化码。

Polar码背景

2015 年,国际电信联盟无线通信部(International Telecommunication Union-Radio Communications Sector,ITU-R)明确了未来 5G三大典型应用场景,分别为:

  1. 增强型移动宽带(enhanced mobile broadband,eMBB)场景。要求支持更高的传输速率(峰值速率:上行链路达到 10 Gbit/s,下行链路达到 20 Gbit/s)、更高的频谱效率(峰值频谱效率:上行链路达到12 bit/(s·Hz),下行链路达到 30 bit/(s·Hz))等。

  2. 大规模机器类通信(massive machine type communication,mMTC)。要求支持更大连接数密度(\(1×10^6\)个连接\(/km^2\))、更低能耗(终端电池使用寿命达到 15 年);

  3. 场景和超高可靠性低时延通信(ultra-reliable and low latency communication,uRLLC)场景。要求支持更低的时延(上下行链路时延 0.5 ms,即端到端时延低于 1 ms)、更高的可靠度(达到 99.9999%,即 1 ms 内的误帧率低于\(10^{-6}\))、更低的错误平层等。

而4G 中采用的信道编码方案 Turbo 码因在可靠性(Turbo 码存在译码错误平层)、编译码复杂度、译码吞吐量和编码效率等方面难以有效满足 5G 场景下的各种性能要求。亟需为 5G 新空口(new radio,NR)设计更加先进高效的信道编码方案,以尽可能小的业务开销实现信息快速可靠传输。

目前,国内外研究机构已针对 5G 信道编码技术开展了大量研究,并已达成部分共识。Polar 码因其理论证明可达到香农极限,且具有可实用的线性复杂度编译码能力而受到业界重视,成为5G NR信道编码方案的强有力候选者。在 2016 年 11 月召开的 3GPP RAN1#87 次会议上确定eMBB场景的 5G 短码块信道编码方案采用 Polar 码作为控制信道编码方案。

Polar码概述

2008 年,土耳其毕尔肯大学 Arikan 教授在国际信息论(International Symposium on Information Theory,ISIT)会议上首次提出信道极化(channel polarization)的概念。Polar码的核心思想是信道极化,不同的信道对于极化方法也有区别。

2009 年,Arikan教授在中对信道极化进行更为详细的阐述,并基于信道极化思想提出一种新型信道编码方法,即 Polar 码。 Arikan 分析了 Polar 码的极化现象,并给出 Polar 码在二元删除信道(binary erasure channel,BEC)中的具体构造方法以及编译码过程。

考虑到 Arikan E 给出的 Polar 码构造方法仅适用于 BEC 信道,具有较大的局限性,Mori 和 Tanaka 等人借鉴低密度奇偶校验(low-density parity-check,LDPC)码的构造方法,提出采用密度进化(density evolution,DE)方式构造 Polar 码,以适用于任意二进制离散无记忆信道(binary discrete memoryless channel,B-DMC)。我们这节课主要研究对象就是B-DMC

我们这节课主要讲述:

  1. 信道极化:信道合并和分解
  2. Polar码的编码方式
  3. Polar码的译码方式(简略)

信道极化

信道极化:包括信道合并和信道分解。

当合并信道的数目趋于无穷大时,一部分信道将趋于无噪信道,另外一部分则趋于全噪信道,这种现象就是信道极化。

无噪信道的传输速率会达到信道容量\(I(W)\),而全噪信道的传输速率趋于0。Polar码的编码策略正是应用了这种现象的特性,利用无噪信道传输用户的有用信息,全噪信道传输约定的信息或者不传信息。

规定:

对任意\(N=2^n(n \geqslant 0)\)个独立的B-DMC信道\(W\),使用递归的方式,合并成\(W_N\);然后再将\(W_N\)拆分为相关的信道\(\left \{ W_N^{(i)}: 1\leqslant i \leqslant N \right \}\),就是信道极化现象的具体实现过程。

信道极化过程

我们总结一下:
原先有N个性质相同的B-DMC信道,现在通过信道合并--信道分解的形式,得到了\(W_N^{(1)} \rightarrow W_N^{(N)}\)新的N个信道,这N个信道中,就有无噪和全噪信道,然后我们就能利用这N个不同性质的信道进行信息传输。

信道合并

B-DMC信道: \(W: X \rightarrow Y\),其中,\(x=(x_1, x_2 \cdots)\)表示输入向量集合,\(y=(y_1, y_2 \cdots)\)表示输出向量集合。转移概率记为:\(W (y|x),x \in X,y \in Y\)

信道合并:对N个互相独立的B-DMC信道\(W\)合并,生成信道\(W_N\),记作:\(W_N : X^N \rightarrow Y^N\)。其中,\(X^N=(x_1, x_2 \cdots x_N)\)表示输入序列,\(Y^N=(y_1, y_2 \cdots y_N)\)表示输出序列。信道的转移概率为\(W^N(y_1^N | x_1^N) = \prod_{i=1}^N W(y_i | x_i)\)

下面,我们研究N值不同时,信道合并的具体过程。

(1)N = 1 时,\(W_1 = W\),不用进行信道合并;

(2)N = 2时,\(W_2: X^2 \rightarrow Y^2\)。两个信道\(W\)组合成了\(W_2\),也就是红筐所示的部分。具体组合方式如下:

N=2示意图

这种由"\(\oplus\)"和走线构成的图成为长度为N的极化码的编码图,表示这张图的矩阵被称为生成矩阵\(G_N\),比如当N=2时,\(G_2=F=\begin{bmatrix} 1 & 0 \\ 1 & 1\end{bmatrix}\)\(F\)也被称为核心矩阵。

\((u_1, u_2)\)为信源序列,也成为信源比特;\((x_1, x_2)\)为输入的编码序列,即码字比特;\((y_1, y_2)\)为输出序列。

从上图中,我们可以写出输入序列的表达式:\(x_1=u_1\oplus u_2, x_2 = u_2\)

我们也能看出,这个是个积信道。转移概率为:\(W_2(y_1, y_2 | u_1, u_2) = W(y_1|u_1 \oplus u_2) W(y_2 | u_2)\)

(3)N=4时,具体组合方式如下

N=4示意图

N=4示意图

如上图所示,\((W_2^{(1)}, W_2^{(1)}) \rightarrow (W_4^{(1)}, W_4^{(2)}), (W_2^{(2)}, W_2^{(2)}) \rightarrow (W_4^{(3)}, W_4^{(4)})\)

转移概率为\(W_4(y_1^4 | x_1^4) = W_2(y_1, y_2| u_1 \oplus u_2, u_3 \oplus u_4)W_2(y_3, y_4|u_2, u_4)\)

信源比特和码字比特的关系:\(u_1^4 \rightarrow x_1^4\)的映射关系表达式为:\(x_1^4 = u_1^4G_4, G_4=\begin{bmatrix} 1 & 0 & 0 & 0 \\ 1 & 0 & 1 & 0 \\ 1 & 1 & 0 & 0 \\ 1 & 1 & 1 & 1 \end{bmatrix}\)

这个生成矩阵是怎么来的?直观上来说,可以把上面的式子进行矩阵运算(加法为模2加法),可得\((x_1, x_2, x_3, x_4)=(u_1 \oplus u_2\oplus u_3\oplus u_4, u_3 \oplus u_4, u_2 \oplus u_4, u_4)\)这个结果就是图表反应的结果。如果从数学上来说,见下面一般情况的N的分析。

所以,组合信道\(W_4\)和原始信道\(W^4\)之间的转移概率可表示为:\(W_4(y_1^4 | x_1^4) = W^4(y_1^4|u_1^4G_4)\)

(4)将上述结论类比到任意N,两个独立信道 \(W_{\frac {N}{2}}\) 可以通过信道组合转换成原道\(W_{N}\)

可以参考下图理解一下这个规律:长度为N的极化码编码图的最左列是竖着排列的\(N/2\)个长度为2的极化码的编码图,所以这\(N/2\)个长度为2的极化码的第一个码字比特\((u_1 \oplus u_2, u_3 \oplus u_4 \cdots u_{N-1} \oplus u_N)\)被置换到上一半(红框表示部分),而第二个码字比特被置换到下一半(绿框表示部分)。
N=8示意图

\(u_1^N \rightarrow x_1^N\)可表示为\(x_1^N=u_1^NG_N\)

\(G_N = B_NF^{\otimes n}\)为N阶生成矩阵。

其中,\(B_N\)为N阶比特反转矩阵,实现倒位功能。\(B_N=R_N(I_2 \otimes B_{N/2})\)\(I_2 = F^2\)\(R_N\)是个排列运算矩阵。

核心矩阵\(F=\begin{bmatrix} 1 & 0 \\ 1 & 1 \end{bmatrix}\)\(F^{\otimes n}\)为矩阵F的n阶克罗内克积。

  1. 排列运算矩阵\(R_N\)。举例来说:\((a_1, a_2, \cdots, a_N)R_N = (a_1, a_3,a_5,\cdots,a_{N-1},a_2,a_4,\cdots,a_N)\)
    比如N=4时,\(R_N=\begin{bmatrix} 1 & 0 &0&0 \\ 0&0&1&0 \\ 0&1&0&0 \\ 0&0&0&1\end{bmatrix}\)。也就是在每列的1,3,……,2,4……对应位置为1,其余为0
  1. 克罗内克积。比如\(A=\begin{bmatrix} 1 & 2 \\ 3&4 \end{bmatrix}, A \otimes F=\begin{bmatrix} 1F & 2F \\ 3F&4F\end{bmatrix}\),然后在对应位置展开即可。

如果感兴趣,用上面这些公式可以验证一下N=4时的生成矩阵。

组合信道和原始信道的转移概率为:\(W_N(y_1^N|u_1^N) = W^N(y_1^N | u_1^N G_N)\)

信道分解

信道分解过程是将组合信道\(W_N\)分裂成N个二进制输入比特信道\(W_N^{(i)}\)的过程。

我们先以N=2时为例。组合信道\(W_2\)分裂为\(W_2^{(1)}, W_2^{(2)}\),即极化过程:\((W,W) \rightarrow (W_2^{(1)}, W_2^{(2)})\)

(1)传输信源序列\(u_1\)的极化信道\(W_2^{(1)}(y_1, y_2 | u_1)\)的转移概率为:

\(W_2^{(1)}(y_1, y_2 | u_1) = P(y_1, y_2, u_1)/P(u_1)=\cdots = \frac {1} {2} \Sigma_{u_2}W(y_1|u_1 \oplus u_2)W(y_1 | u_2)\)

(2)传输信源序列\(u_2\)的极化信道\(W_2^{(2)}(y_1, y_2, u_1 | u_2)\)的转移概率为:

\(W_2^{(2)}(y_1, y_2, u_1 | u_2) = P(y_1, y_2, u_1, u_2)/P(u_2) = \cdots = \frac {1} {2} W(y_1|u_1 \oplus u_2)W(y_1 | u_2)\)

上面的推导中省略了很多步骤。我们只需要了解结论,有兴趣的同学课下可以来找我要具体的过程。

那么,我们分解出的两个信道能满足极化信道的要求吗?接下来我们可以验证一下极化信道的特性。

由转移概率,我们可得\(I(Y_1Y_2;U_1)+I(Y_1Y_2U_1;U_2)=2I(X_1;Y_1)=2I(W)\),其中\(I(W)\)表示信道\(W\)的互信息。这个式子表达的意思是:信道\(W\)的两次复用所能传递的信息等于极化信道\(W_2^{(1)}\)\(W_2^{(2)}\)所能传递的信息的和,极化信道不会损失信息传输的能力

\(I(Y_1Y_2;U_1) \leqslant I(Y_1Y_2U_1;U_2)\),即\(W_2^{(2)}\)\(W_2^{(1)}\)的传信能力大,也就是\(W_2^{(2)}\)\(W_2^{(1)}\)有更大的容量,当码长趋于无穷时,计划信道的容量非0即1。这里具体的证明我们不再展开,通过两者的大小比较有个直观的认识即可。

推广到N,我们定义极化信道表达式为\(W_N^{(i)}(\mathbf{y_1^N, u_1^{i-1}} | u_i)\),表示输入为\(u_i\),输出是\(\mathbf{y_1^N, u_1^{i-1}}\),也就是极化信道\(W_N^{(i)}\)能观察到W的输出\(\mathbf{y_1^N}\)和比特值\((u_1, u_2,\cdots,u_{i-1})\)。这是因为极化码使用串行抵消译码,从\(u_1\)开始逐一估计信源比特,直到\(u_N\),所以在译码\(u_i\)时,\((u_1, u_2,\cdots,u_{i-1})\)的值都已经获得,被当作译码\(u_i\)所需要的反馈

(二)Polar编码

根据信道极化现象,可将原本相互独立的N 个原始信道转化为 N 个信道容量不等的比特信
道。当 N 趋于无穷大时,一部分信道的容量趋于0,而另一部分信道的容量趋于 1。

假设 K 个信道的容量趋于 1,N-K 个信道的容量趋于 0,可选择 K 个容量趋近于 1 的信道传输信息比特,选择 N-K 个容量趋近于 0 的信道传输冻结比特,即固定比特,从而实现由 K 个信息比特到 N 个编码比特的一一对应关系,也即实现码率为 K/N 的Polar 码的编码过程。

具体编码方式可表示为\(x_1^N=u_1^NG_N\)。生成矩阵如何计算等问题在上面已经说过了。

Polar 码可由参数\((N,K A,u_{A^c})\)的陪集\(G_N\) 码定义。

\(N=2^n\)为码长;

K为信息比特个数,也就是无噪信道数;

A 为信息比特位置集合,A 中元素个数等于 K;

\(A^c\)为补集,也就是全噪信道的集合;

\(u_{A^c}\)为冻结比特所对应的序列,在\(A^c\)上传输的序列。由于冻结比特所在的信道特性极差,在信息传输过程中一般固定设为 0。

由于上述编码中的生成矩阵\(G_N\)中存在比特反转矩阵\(B_N\),故该编码方式也称为比特反转编码

在 3GPP 中已确定 Polar 码采用无比特反转编码,并把采用该编码方式得到的 Polar 码称为“基本Polar 码”,其生成矩阵为\(G_N = F^{\otimes n}\)

(三)Polar译码

极化码的译码基本方法主要有:连续消除(Successive Cancellation, SC) 译 码 、 置 信 传 播 (Belief Propagation, BP) 译 码 、 线 性 规 划 (Linear Programming, LP) 译 码 、 基 于 SC 列 表 (Successive Cancellation List, SCL)译码、最大似然(Maximum Likelihood, ML)译码等。

参考文献:《极化码讲义》-于永润编写。下载链接

ch9-极化码。http://staff.ustc.edu.cn/~wyzhou/chapter9.pdf

《面向 5G 新空口技术的 Polar 码标准化研究进展》:谢德胜、柴蓉等;重庆邮电大学移动通信重点实验室;2018−08−10

这篇关于Polar码快速入门的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/208516

相关文章

Spring Security 从入门到进阶系列教程

Spring Security 入门系列 《保护 Web 应用的安全》 《Spring-Security-入门(一):登录与退出》 《Spring-Security-入门(二):基于数据库验证》 《Spring-Security-入门(三):密码加密》 《Spring-Security-入门(四):自定义-Filter》 《Spring-Security-入门(五):在 Sprin

电脑桌面文件删除了怎么找回来?别急,快速恢复攻略在此

在日常使用电脑的过程中,我们经常会遇到这样的情况:一不小心,桌面上的某个重要文件被删除了。这时,大多数人可能会感到惊慌失措,不知所措。 其实,不必过于担心,因为有很多方法可以帮助我们找回被删除的桌面文件。下面,就让我们一起来了解一下这些恢复桌面文件的方法吧。 一、使用撤销操作 如果我们刚刚删除了桌面上的文件,并且还没有进行其他操作,那么可以尝试使用撤销操作来恢复文件。在键盘上同时按下“C

数论入门整理(updating)

一、gcd lcm 基础中的基础,一般用来处理计算第一步什么的,分数化简之类。 LL gcd(LL a, LL b) { return b ? gcd(b, a % b) : a; } <pre name="code" class="cpp">LL lcm(LL a, LL b){LL c = gcd(a, b);return a / c * b;} 例题:

Java 创建图形用户界面(GUI)入门指南(Swing库 JFrame 类)概述

概述 基本概念 Java Swing 的架构 Java Swing 是一个为 Java 设计的 GUI 工具包,是 JAVA 基础类的一部分,基于 Java AWT 构建,提供了一系列轻量级、可定制的图形用户界面(GUI)组件。 与 AWT 相比,Swing 提供了许多比 AWT 更好的屏幕显示元素,更加灵活和可定制,具有更好的跨平台性能。 组件和容器 Java Swing 提供了许多

【IPV6从入门到起飞】5-1 IPV6+Home Assistant(搭建基本环境)

【IPV6从入门到起飞】5-1 IPV6+Home Assistant #搭建基本环境 1 背景2 docker下载 hass3 创建容器4 浏览器访问 hass5 手机APP远程访问hass6 更多玩法 1 背景 既然电脑可以IPV6入站,手机流量可以访问IPV6网络的服务,为什么不在电脑搭建Home Assistant(hass),来控制你的设备呢?@智能家居 @万物互联

poj 2104 and hdu 2665 划分树模板入门题

题意: 给一个数组n(1e5)个数,给一个范围(fr, to, k),求这个范围中第k大的数。 解析: 划分树入门。 bing神的模板。 坑爹的地方是把-l 看成了-1........ 一直re。 代码: poj 2104: #include <iostream>#include <cstdio>#include <cstdlib>#include <al

hdu 4565 推倒公式+矩阵快速幂

题意 求下式的值: Sn=⌈ (a+b√)n⌉%m S_n = \lceil\ (a + \sqrt{b}) ^ n \rceil\% m 其中: 0<a,m<215 0< a, m < 2^{15} 0<b,n<231 0 < b, n < 2^{31} (a−1)2<b<a2 (a-1)^2< b < a^2 解析 令: An=(a+b√)n A_n = (a +

MySQL-CRUD入门1

文章目录 认识配置文件client节点mysql节点mysqld节点 数据的添加(Create)添加一行数据添加多行数据两种添加数据的效率对比 数据的查询(Retrieve)全列查询指定列查询查询中带有表达式关于字面量关于as重命名 临时表引入distinct去重order by 排序关于NULL 认识配置文件 在我们的MySQL服务安装好了之后, 会有一个配置文件, 也就

v0.dev快速开发

探索v0.dev:次世代开发者之利器 今之技艺日新月异,开发者之工具亦随之进步不辍。v0.dev者,新兴之开发者利器也,迅速引起众多开发者之瞩目。本文将引汝探究v0.dev之基本功能与优势,助汝速速上手,提升开发之效率。 何谓v0.dev? v0.dev者,现代化之开发者工具也,旨在简化并加速软件开发之过程。其集多种功能于一体,助开发者高效编写、测试及部署代码。无论汝为前端开发者、后端开发者

音视频入门基础:WAV专题(10)——FFmpeg源码中计算WAV音频文件每个packet的pts、dts的实现

一、引言 从文章《音视频入门基础:WAV专题(6)——通过FFprobe显示WAV音频文件每个数据包的信息》中我们可以知道,通过FFprobe命令可以打印WAV音频文件每个packet(也称为数据包或多媒体包)的信息,这些信息包含该packet的pts、dts: 打印出来的“pts”实际是AVPacket结构体中的成员变量pts,是以AVStream->time_base为单位的显