Polar Code（21）3GPP RAN1#90

发表于 2017-10-20 更新于 2018-10-21 分类于 3GPP_PolarCode 阅读次数：

前言

我一直有意将Polar Code系列和3GPP_PolarCode系列区分开，因此把它们放在不同的分类里，虽然它们都是关于polar code的文章，但前者关注极化码编译码算法本身，而后者关注极化码在5G标准化中的进展。前者更偏于理论研究，参考资料多是paper，后者更注重实际应用，参考资料多是3GPP proposal或Technical Specification（技术规范）。这可看作是polar code发展的两条线，有时这两条线又相交重叠，相互促进。如果你熟悉LTE system，那么3GPP_PolarCode系列则更容易理解。3GPP里的极化码是控制信道框架下的信道编码，它的上一步骤是CRC添加，它的下一步是速率匹配，这个过程在LTE system里也是如此。

3GPP RAN1#90会议于8月21~25日在布拉格召开。会议达成的结论已在3GPP Rel-15技术规范v1.0.0版本中体现，详见《5G物理层协议V100》。

截止到本次会议，polar coding一个比较完整的编码方案已经形成，从CRC计算到极化码编码，再到速率匹配方案都基本确定了，并已将本次会议达成的结论体现在v1.0.0版本协议的《5G-NR复用与信道编码》中。

本文结合本次会议达成的结论和v1.0.0版本协议的《5G-NR复用与信道编码》，对Polar coding过程进行比较全面的梳理。5G控制信道编码的基本流程：

CRC添加
信道编码
速率匹配

Code construction

这部分主要讨论了CRC和interleaver（交织器）的设计。一方面，基于CRC-Polar的编码方案无疑是3GPP确定采用的方案；另一方面，3GPP RAN1会议已同意支持提前终止（early termination，ET）的编译码策略。传统的做法是将CRC bits统一地放置在信息比特后面，译码端只有译出全部比特时才能对该码字进行校验，校验后才能知道该译码码字是否正确。新的方法是将CRC bits分散地插入到信息比特中间。这样做的好处是，只译出一部分bits即可进行一次CRC校验，一旦检测到误码立即终止译码，由于该码字已经出错，后面就没有必要再译了。Distributed-CRC（DCRC）可降低译码计算量，节省功率，带来提前终止增益。

例如，$K=4$位信息比特，CRC长度为${ {L}_{CRC}}=4$，CRC bits$\left( \begin{matrix} { {p}_{1}} & { {p}_{2}} & { {p}_{3}} & { {p}_{4}} \\ \end{matrix} \right)$已分散地插入到信息比特中：

\[\left( \begin{matrix} { {x}_{1}} & { {x}_{2}} & { {p}_{1}} & { {x}_{3}} & { {p}_{2}} & { {x}_{4}} & { {p}_{3}} & { {p}_{4}} \\ \end{matrix} \right)\] 译码时每译出一个CRC bit就进行一次校验。

如上所述，对于极化码编码，CRC计算和交织器往往是联系在一起的。这个过程分为两步：

第一步，进行正常的CRC添加。给定长度为${ {L}_{CRC}}$的CRC生成多项式，按照通行的做法去计算CRC。假设待编码比特序列长度为$K$，添加CRC后的序列长度为${ {K}^{'}}=K+{ {L}_{CRC}}$。3GPP已确定5G NR-PDCCH的CRC长度为24，即${ {L}_{CRC}}=24$，并采用如下生成多项式：

\[{ {g}_{\text{CRC24C}}}\left( D \right)=[{ {D}^{24}}+{ {D}^{23}}+{ {D}^{21}}+{ {D}^{20}}+{ {D}^{17}}+{ {D}^{15}}+{ {D}^{13}}+{ {D}^{12}}+{ {D}^{8}}+{ {D}^{4}}+{ {D}^{2}}+D+1]\]

第二步进行交织。交织器将${ {L}_{CRC}}$个CRC bits分散插入到$K$个信息比特中。交织器的输入、输出比特数相同，都是${ {K}^{'}}=K+{ {L}_{CRC}}$。

交织模式（interleaver pattern）按下列方法得到：

${ {K}_{\max }}$表示最大的信息比特数。5G NR控制信道所承载的内容不能太多，因为涉及信令开销的问题，大致在200 bits以内。${ {K}_{\max }}$限定了极化码待编码比特的数目。

3GPP采用统一的交织方法，即给定了一个统一交织模式$$，$$是按照最大比特数$( { {K}{}}+{ {L}{CRC}} )$得到的。交织器的输入比特数是$( K+{ {L}{CRC}} )$，对满足$( K+{ {L}{CRC}} )( { {K}{}}+{ {L}{CRC}} )$的任意比特数，其子交织模式$'$都来自于这个统一的交织模式$$。其中$( k )$的值见下表：

由于目前${ {K}_{\max }}$的值还未确定，$\pi \left( k \right)$是按照$\left( { {K}_{\max }}+{ {L}_{CRC}} \right)$的长度来计算的，在后面的协议版本中，这张表格将会得到进一步的修订。

子交织模式$\pi '$表示交织后的比特位置索引，当按照上述方法获得$\pi '$，根据这个比特索引重新给信息比特排序：

$c_{k}^{'}={ {c}_{\pi '\left( k \right)}}$，$k=0,1,...,{ {K}^{'}}-1$

至此，就得到了交织后的信息比特序列，其效果就是：

\[\begin{align} \nonumber & \left( \begin{matrix} { {x}_{1}} & { {x}_{2}} & { {x}_{3}} & { {x}_{4}} & { {p}_{1}} & { {p}_{2}} & { {p}_{3}} & { {p}_{4}} \\ \end{matrix} \right) \\ \nonumber & \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \downarrow \\ \nonumber & \left( \begin{matrix} { {x}_{1}} & { {x}_{2}} & { {p}_{1}} & { {x}_{3}} & { {p}_{2}} & { {x}_{4}} & { {p}_{3}} & { {p}_{4}} \\ \end{matrix} \right) \\ \end{align}\]

交织以后则进行极化码编码。不过在编码之前，还需要另一个独立的过程，那就是输入序列的设计。

Sequence design

极化码输入序列的设计，事关信息比特和冻结比特位置如何选取的问题。选取的规则是根据子信道可靠性程度，将信息比特放置在可靠性高的子信道上。关于如何评估子信道可靠性，本博客已花了大量篇幅介绍AWGN下的高斯近似法，之后又介绍了Beta-expansion算法。3GPP正是采用了华为提出的Beta-expansion算法，按照极化权重（PW）给子信道排序，用极化权重来度量子信道可靠性。这部分已经写入5G协议规范中，详见博文《5G-NR复用与信道编码》 polar coding一节。虽然5G协议并不会提到Beta-expansion算法，但协议所展示的Table 5.3.1-2 Polar sequence and its corresponding reliablity正是基于Beta-expansion算法得到的。

需要说明的是，Table 5.3.1-2所示的$W\left( Q_{i}^{ { {N}_{\max }}} \right)$，是在Beta-expansion算法基础上又做了进一步改进的结果。

按权重从小到大排序$W\left( Q_{0}^{ { {N}_{\max }}} \right)<W\left( Q_{1}^{ { {N}_{\max }}} \right)<...<W\left( Q_{ { {N}_{\max }}-1}^{ { {N}_{\max }}} \right)$，其中$Q_{i}^{ { {N}_{\max }}}$就是按可靠性程度排序之后的比特索引，最终得到极化码输入序列的比特位置索引$\mathbf{Q}_{0}^{ { {N}_{\max }}-1}=\left\{ Q_{0}^{ { {N}_{\max }}},Q_{1}^{ { {N}_{\max }}},...,Q_{ { {N}_{\max }}-1}^{ { {N}_{\max }}} \right\}$。

用$\bar{Q}_{I}^{N}$表示信息比特索引集合，用$\bar{Q}_{F}^{N}$表示冻结比特索引集合，$\left| \bar{Q}_{I}^{N} \right|={ {K}^{'}}+{ {n}_{PC}}$，$\left| \bar{Q}_{F}^{N} \right|=N-\left| \bar{Q}_{I}^{N} \right|$。

为了本文叙述的连贯性，本文涉及的${ {K}^{'}}$表示包含CRC比特的信息位数，即${ {K}^{'}}=K+{ {L}_{CRC}}$。因此本文中的${ {K}^{'}}$与5G协议《5G-NR复用与信道编码》 polar coding一节中的$K$等价。

若${ {n}_{PC}}=0$，则说明极化码编码采用CRC-Polar；若${ {n}_{PC}}>0$,则说明极化码采用CRC-PC-Polar，在这种情下，CRC、PC和待编码信息比特都作为极化码的信息比特位，即都在$\bar{Q}_{I}^{N}$中。对于PDCCH信道编码，${ {n}_{PC}}=0$。

用$Q_{PC}^{N}$表示PC比特索引集合，$\left| Q_{PC}^{N} \right|={ {n}_{PC}}$。极化码信息比特索引集合$\bar{Q}_{I}^{N}$还可进一步细分，用$\tilde{Q}_{I}^{N}$表示$\bar{Q}_{I}^{N}$中可靠性最高的$\left( \left| \mathbf{\bar{Q}}_{I}^{N} \right|-{ {n}_{PC}} \right)$个比特索引。PC比特又分为两个部分，其中有$n_{PC}^{wm}$个PC比特对应于$\tilde{Q}_{I}^{N}$的最小行重。用${ {G}_{N}}$表示极化码生成矩阵，${ {G}_{N}}={ {\left( { {G}_{2}} \right)}^{\otimes n}}$，$G2=\left[ \begin{matrix} 1 & 0 \\ 1 & 1 \\ \end{matrix} \right]$。用${ {\mathbf{g}}_{j}}$表示${ {G}_{N}}$的第$j$行，用$w\left( { {\mathbf{g}}_{j}} \right)$表示${ {\mathbf{g}}_{j}}$的行重，行重就是${ {\mathbf{g}}_{j}}$中“1”的个数。

因此1）把$n_{PC}^{wm}$个PC比特放置在具有$\tilde{Q}_{I}^{N}$最小行重的索引上；2）把$\left( { {n}_{PC}}-n_{PC}^{wm} \right)$个PC比特放置在$\bar{Q}_{I}^{N}$中可靠性最低的索引上；3）$\bar{Q}_{I}^{N}$中剩余的比特索引放置${ {K}^{'}}=K+{ {L}_{CRC}}$个信息比特。

这两部分的PC比特所在的位置是不会重合的。

如果$\tilde{Q}_{I}^{N}$中最小行重的比特索引数大于$n_{PC}^{wm}$，那么就将$n_{PC}^{wm}$个PC比特放置在行重最小且可靠性最高的比特索引上。

极化码输入序列索引示意如下图所示。

按照如上所述的方法，得到极化码输入序列$\mathbf{u}=\left[ { {u}_{0}}\text{ }{ {u}_{1}}\text{ }{ {u}_{2}}\text{ }...\text{ }{ {u}_{N-1}} \right]$。将序列$\mathbf{u}$和生成矩阵相乘

\[\mathbf{d}=\mathbf{u}{ {\mathbf{G}}_{n}}\]

得到编码器输出序列$\mathbf{d}=\left[ { {d}_{0}}\text{ }{ {d}_{1}}\text{ }{ {d}_{2}}\text{ }...\text{ }{ {d}_{N-1}} \right]$。

Rate matching

编码之后的速率匹配是非常重要的一环。速率匹配的输入序列即为编码输出序列$\mathbf{d}=\left[ { {d}_{0}}\text{ }{ {d}_{1}}\text{ }{ {d}_{2}}\text{ }...\text{ }{ {d}_{N-1}} \right]$，速率匹配的输出序列为${ {f}_{0}},{ {f}_{1}},{ {f}_{2}},...,{ {f}_{E-1}}$，速率匹配比特数为$E$。$E$才是实际要传输的编码比特数。

速率匹配分为三个过程，子块交织、比特收集、比特交织。

子块交织

子块交织就是上图所示的Rate-matching Interleaving，它将输入进来的N编码比特分为32个子块，然后将32个子块按照序列（0 1 2 3 4 5 6 7 8 9 10 11 12 16 13 17 14 18 15 19 20 24 21 22 25 26 28 23 27 29 30 31）重新排序。编码序列${ {d}_{0}},{ {d}_{1}},{ {d}_{2}},...,{ {d}_{N-1}}$，经过子块交织后表示为${ {y}_{0}},{ {y}_{1}},{ {y}_{2}},...,{ {y}_{N-1}}$。

上图是示意图，3GPP规范做了进一步修改：

子块交织过程为：

其中子块交织模式$P\left( i \right)$由下表得到：

比特收集

比特收集就是Circular Buffer，有三种速率匹配模式：repetition，puncturing，shortening。比特收集器的输入序列为子块交织器的输出${ {y}_{0}},{ {y}_{1}},{ {y}_{2}},...,{ {y}_{N-1}}$，比特收集器的输出序列为${ {e}_{0}},{ {e}_{1}},{ {e}_{2}},...,{ {e}_{E-1}}$。完成从极化码码长N到速率匹配比特数E的转换，E是实际传输的编码比特数。