0 概述

文献[1]提出的极化码被证明在连续消去(Successive Cancellation, SC)译码算法下, 可以达到二进制输入对称离散无记忆信道(Binary Discrete Memoryless Channels, B-DMCs)的对称信道容量, 并且具有多项式级数的编译码复杂度。尽管极化码的构造方法明确, 但其仅能够在二进制删除信道(Binary Erasure Channel, BEC)下实现。文献[2-3]得出在一般信道下, 密度进化(Density Evolution, DE)方法是一种构造极化码的有效工具。基于DE方法, 文献[4-6]提出2种方法用于2×2维核矩阵极化码的构造:高斯近似DE(GA-DE)^[4-5]和Tal-Vardy^[6]。GA-DE方法具备线性的复杂度, 且其构造的极化码性能较好^[7]。Tal-Vardy能够提供信道升级和降级2种近似量化DE方法, 原位信道夹在由这2种方法构造的位信道之间。上述2种近似方法构造出的极化码非常接近^[6], 且Tal-Vardy被认为是较优的极化码构造方法。

文献[1]中的极化码是基于核矩阵${\mathit{\boldsymbol{G}}_2} = \left({\begin{array}{*{20}{c}} 1 & 0\\ 1 & 1 \end{array}} \right)$。文献[8]研究表明, 当m≥16时, 高维核矩阵G_m的极化速率高于原G₂核矩阵^[8]。在相同码长情况下, 较高的极化速率表明相应的极化码有较低的译码差错概率。在文献[8]的基础上, 许多研究者设计出具有较高极化速率的高维核矩阵^[8-10], 但是仍缺乏有效方法构造出相应的极化码。

构造高维核矩阵(维数大于等于3)极化码最直接的方式是将GA-DE方法和Tal-Vardy方法从G₂推广到高维核矩阵, 但该方式存在一定局限。GA-DE方法推广至高维核矩阵极化码时会引起一定的译码性能损失。Tal-Vardy方法直接推广至高维核矩阵极化码会导致其复杂度随核矩阵维数呈指数级增加。另一种方式是文献[1]提出的基于蒙特卡洛(Monte Carlo, MC)的极化码构造方法, 但其在后续研究中未得到广泛应用, 仅文献[11-12]利用该方法来构造G₂核矩阵极化码。

本文分析基于MC的极化码构造方法, 将其推广至高维核矩阵中, 提出一种两阶段蒙特卡洛方法(TPMC), 以实现高维核矩阵极化码的快速构造。

1 相关工作 1.1 符号说明

令W:X→Y为一个B-DMCs信道, 其输入字母集为X={0, 1}, 输出字母集为Y, 条件转移概率为W(y|x)。符号a_i^j表示一个行向量(a_i, a_i+1, …, a_j)。如果i>j, 则a_i^j=Ø。令W^N:X^N→Y^N表示由N个独立W组成的信道。因此, 对于每个x₀^N－1∈X₀^N－1和y₀^N－1∈Y₀^N－1, 转移概率为:

$ {W^N}\left( {y_0^{N - 1}\left| {x_0^{N - 1}} \right.} \right) = \prod\limits_{i = 0}^{N - 1} {W\left( {{y_i}\left| {{x_i}} \right.} \right)} $

令${\mathit{\boldsymbol{G}}_N} = {\mathit{\boldsymbol{B}}_N}\mathit{\boldsymbol{G}}_m^{ \otimes n}$是N×N维的生成矩阵, 其中, B_N是一个置换矩阵^[1], G_m是一个m×m维的核矩阵, ⊗n表示n倍的克罗内克积。本文使用的所有核矩阵均是线性最优核矩阵^[9]。向量信道W_N:X₀^N－1→Y₀^N－1定义为:

$ {W_N}\left( {y_0^{N - 1}\left| {x_0^{N - 1}} \right.} \right) = {W^N}\left( {y_0^{N - 1}\left| {u_0^{N - 1}{\mathit{\boldsymbol{G}}_N}} \right.} \right) $

其中, u表示消息序列。

位信道W_N⁽ⁱ⁾:X→Y^N×Xⁱ(0≤i≤N－1)定义为:

$ W_N^{\left( i \right)}\left( {y_0^{N - 1},u_0^{i - 1}\left| {{u_i}} \right.} \right) = \sum\limits_{u_{i + 1}^{N - 1}} {\frac{1}{{{m^{N - 1}}}}{W_N}\left( {y_0^{N - 1}\left| {u_0^{N - 1}} \right.} \right)} $

(1)

对于一个给定的核矩阵G_m, W_Gm:{0, 1}^m→Y^m定义为:

$ {W_{{\mathit{\boldsymbol{G}}_m}}}\left( {y_0^{m - 1}\left| {u_0^{m - 1}} \right.} \right) = \prod\limits_{i = 0}^{m - 1} {W\left( {{y_i}\left| {{{\left( {u_0^{m - 1}{\mathit{\boldsymbol{G}}_m}} \right)}_i}} \right.} \right)} $

(2)

其中, (u₀^m－1G_m)_i是向量u₀^m－1G_m的第i个元素。

对于SC译码, 基本的递归计算公式(单步位信道计算公式)为:

$ \begin{array}{l} W_{{\mathit{\boldsymbol{G}}_m}}^{\left( i \right)}\left( {y_0^{m - 1},u_0^{i - 1}\left| {{u_i}} \right.} \right) = \\ \;\;\;\;\;\;\frac{1}{{{2^{m - 1}}}}\sum\limits_{u_{i + 1}^{m - 1}} {W\left( {{y_0}\left| {{x_0}} \right.} \right)W\left( {{y_1}\left| {{x_1}} \right.} \right) \cdots W\left( {{y_{m - 1}}\left| {{x_{m - 1}}} \right.} \right)} \end{array} $

(3)

其中, ${u_i} \in \{ 0, 1\}, {x_i} = {\left({u_0^{m - 1}{\mathit{\boldsymbol{G}}_m}} \right)_i}, i = 0, 1, \cdots, m - 1$。

用[N]表示{0, 1, …, N－1}。对于2个实数x和y, 操作◇定义为:

$ x\diamondsuit y = 2{\rm{atanh}}\left( {\tanh \left( {x/2} \right)\tanh \left( {y/2} \right)} \right) $

1.2 极化码构造

构造一个k维的极化码即找到k个最可靠的位信道。文献[1]采用巴氏参数Z(W_N⁽ⁱ⁾)来评价位信道, 从所有N个位信道中挑选k个具备最小Z(W_N⁽ⁱ⁾)的位信道作为信息位集合。文献[6]使用更易操作的Pe(W_N⁽ⁱ⁾)对位信道进行排序, 其中, Pe(W_N⁽ⁱ⁾)表示在最大似然判决下第i个位信道的差错概率。本文同样采用Pe(W_N⁽ⁱ⁾)来评价位信道。

1.3 树结构SC译码

文献[13]将G₂核矩阵极化码的SC译码作为一个完全二进制树上的消息传递算法。本文将任意维的G_m核矩阵极化码的SC译码推广为一个完全m进制树上的消息传递算法。

令T_n(n>0)表示深度为n的完全m进制树, 则T_n有N=mⁿ个叶子节点。给定一个节点v, 分别用d_v、p_v和v₀, v₁, …, v_m－1表示节点v的深度、父节点和子节点, 如图 1(a)所示。在一般情况下, 树的叶子节点索引集为{0, 1, …, N-1}。在图 1(b)中, m=3, n=2, 信息节点集合A={4, 6, 7, 8}。叶子节点0、1、2、3、5称为冻结节点。令I_v为节点v的后代中叶子节点所构成的索引集合, 如果I_v中的节点都是冻结节点, 则T_n中的一个中间节点v也称为冻结节点。注意在SC译码过程中, 所有冻结节点的计算都可以忽略。

对于每个节点v, 存在一个转移概率二元组P_v(每个二元组包括一个概率对P_v[i], 索引为P_v[i][0]和P_v[i][1])和二进制值数组β_v, P_v和β_v的长度都是m^n－d_v。SC译码算法首先激活T_n的根节点, 根据接收到的信道输出计算每个节点的转移概率二元组值并赋给P_v。广度遍历下一层节点, 计算每个节点的P_v和β_v, 根据T_n叶子节点的P_v进行译码结果判决。

令v_i为v的第i个子节点。给定P_v和β_v0, β_v1, …, β_vk－1, 根据基本递归公式(3)可计算出P_vk。令*l表示(P_v[ml], P_v[ml+1], …, P_v[ml+m－1], (β_v0[l], β_v1[l], …, β_vi－1[l])), l∈0, 1, …, m^n－d_v－1－1。令f_i0(*l)和f_i1(*l)分别表示任意维极化码在v和v_i节点之间的基本递归公式。*l作为f_i0(*l)和f_i1(*l)的输入, 则f_i0(*l)和f_i1(*l)的计算步骤如下:

1) 执行以下替换:

$ {\mathit{\boldsymbol{P}}_{\rm{v}}}\left[ {ml + j} \right]\left[ 0 \right] \to W\left( {{y_j}\left| {{x_j} = 0} \right.} \right) $

$ {\mathit{\boldsymbol{P}}_{\rm{v}}}\left[ {ml + j} \right]\left[ 1 \right] \to W\left( {{y_j}\left| {{x_j} = 1} \right.} \right) $

$ \left( {{\mathit{\boldsymbol{\beta }}_{{v_0}}}\left[ l \right],{\mathit{\boldsymbol{\beta }}_{{v_1}}}\left[ l \right], \cdots ,{\mathit{\boldsymbol{\beta }}_{{v_{i - 1}}}}\left[ l \right]} \right) \to u_0^{i - 1} $

其中, l∈0, 1, …, m^n－d_v－1－1, j=0, 1, …, m－1。

2) 计算f_i0(*l):

$ {f_{i0}}\left( { * l} \right) = W_{{\mathit{\boldsymbol{G}}_m}}^{\left( i \right)}\left( {y_0^{m - 1},u_0^{i - 1}\left| {{u_i} = 0} \right.} \right) $

(4)

即:

$ {f_{i0}}\left( { * l} \right) = \frac{1}{{{2^{m - 1}}}}\sum\limits_{u_{i + 1}^{m - 1}} {W\left( {{y_0}\left| {{x_0}} \right.} \right)W\left( {{y_1}\left| {{x_1}} \right.} \right) \cdots W\left( {{y_{m - 1}}\left| {{x_{m - 1}}} \right.} \right)} $

(5)

其中, x_j=(u₀^m－1G_m)_j, j=0, 1, …, m－1。

对f_i0(*l)的计算作进一步解释, 由于(β_v0[l], β_v1[l], …, β_vi－1[l])→u₀^i－1和u_i=0, 则式(4)中u₀^i-1确定。给定一个u_i+1^m－1, 式(5)中的每个x_j=(u₀^m－1G_m)_j, j∈0, 1, …, m－1都可以确定。因此, 对于式(5)中的每个W(y_j|x_j), j∈0, 1, …, m－1可以通过P_v[ml+j][0]→W(y_j|x_j=0)和P_v[ml+j][1]→W(y_j|x_j=1)获得。因此, 可由式(5)计算出f_i0(*l)。利用同样的步骤可以计算出f_i1(*l)。求得f_i0(*l)和f_i1(*l)后, 可以得到:

$ {\mathit{\boldsymbol{P}}_{{v_i}}}\left[ l \right]\left[ 0 \right] = {f_{i0}}\left( { * l} \right),{\mathit{\boldsymbol{P}}_{{v_i}}}\left[ l \right]\left[ 1 \right] = {f_{i1}}\left( { * l} \right) $

其中, l∈0, …, m^n－d_v－1－1。

依据以上概念和定义, 算法1给出基于消息传递的高维核矩阵G_m极化码SC译码过程。

算法1     G_m极化码的树结构SC译码过程

输入     y₀^N－1

输出    译码码字$\hat c_0^{N - 1}$

初始化    激活根节点并将根节点v的P_v赋值为P_v=(P_v[0], P_v[1], …, P_v[N-1]), 其中, P_v[i][0]=W(y_i|x_i=0), P_v[i][1]=W(y_i|x_i=1), i=0, 1, …, N－1

1) 中间节点:

(1) 更新P_v

当一个中间节点v被激活时, 计算P_v0:

$ {{\rm{P}}_{{{\rm{v}}_{\rm{0}}}}}\left[ 1 \right]\left[ 0 \right] = {{\rm{f}}_{00}}\left( { * 1} \right) $

$ {{\rm{P}}_{{{\rm{v}}_{\rm{0}}}}}\left[ 1 \right]\left[ 1 \right] = {{\rm{f}}_{01}}\left( { * 1} \right) $

其中, l=0, 1, …, m^n－d_v－1－1。

传递P_v0给v₀, 然后局部译码节点v进入等待, 直到从v₀接收到β_v0。激活v₁并计算P_v1[0]:

$ {{\rm{P}}_{{{\rm{v}}_{\rm{1}}}}}\left[ 1 \right]\left[ 0 \right] = {{\rm{f}}_{{\rm{10}}}}\left( {{{\rm{P}}_{\rm{v}}}\left[ {{\rm{ml}}} \right],{{\rm{P}}_{\rm{v}}}\left[ {{\rm{ml + 1}}} \right], \cdots ,{{\rm{P}}_{\rm{v}}}\left[ {{\rm{ml}} + {\rm{m}} - 1} \right],{{\rm{ \mathit{ β} }}_{{{\rm{v}}_{\rm{0}}}}}\left[ 1 \right]} \right) $

$ {{\rm{P}}_{{{\rm{v}}_{\rm{1}}}}}\left[ 1 \right]\left[ 1 \right] = {{\rm{f}}_{{\rm{11}}}}\left( {{{\rm{P}}_{\rm{v}}}\left[ {{\rm{ml}}} \right],{{\rm{P}}_{\rm{v}}}\left[ {{\rm{ml + 1}}} \right], \cdots ,{{\rm{P}}_{\rm{v}}}\left[ {{\rm{ml}} + {\rm{m}} - 1} \right],{{\rm{ \mathit{ β} }}_{{{\rm{v}}_{\rm{0}}}}}\left[ 1 \right]} \right) $

其中, l=0, 1, …, m^n－d_v－1－1。

传递P_v1给v₁, 然后对v的子节点v₂, v₃, …, v_m－1应用上述同样的步骤。

(2) 更新β_v

局部译码节点v等待, 直到从v_m－1接收到β_vm－1, 然后根据下式计算β_v:

$ \begin{array}{l} \left( {{{\rm{ \mathit{ β} }}_{\rm{v}}}\left[ {{\rm{m1}}} \right],{{\rm{ \mathit{ β} }}_{\rm{v}}}\left[ {{\rm{m1}} + 1} \right], \cdots ,{{\rm{ \mathit{ β} }}_{\rm{v}}}\left[ {{\rm{m1}} + {\rm{m}} - 1} \right]} \right) = \\ \;\;\;\left( {{{\rm{ \mathit{ β} }}_{{{\rm{v}}_{\rm{0}}}}}\left[ 1 \right],{{\rm{ \mathit{ β} }}_{{{\rm{v}}_{\rm{1}}}}}\left[ 1 \right], \cdots ,{{\rm{ \mathit{ β} }}_{{{\rm{v}}_{{\rm{m}} - 1}}}}\left[ 1 \right]} \right){{\rm{G}}_{\rm{m}}} \end{array} $

其中, l=0, 1, …, m^n－d_v－1－1。

2) 叶子节点:

当一个叶子节点v被激活时, 如果P_v[0][0]≥P_v[0][1], 则${{{\rm{\hat u}}}_{\rm{i}}} = {{\rm{ \mathit{ β} }}_{\rm{v}}}\left[0 \right] = 0$, 如果P_v[0][0]＜P_v[0][1], 则${{{\rm{\hat u}}}_{\rm{i}}} = {{\rm{ \mathit{ β} }}_{\rm{v}}}\left[0 \right] = 1$, 其中, I_v⊂A。否则, β_v[0]=0(冻结位)。则${\rm{\hat c}}\left[{\rm{i}} \right] = {{\rm{ \mathit{ β} }}_{\rm{v}}}\left[0 \right]$, 其中, i是v的索引。

文献[8]指出, 一个高维核矩阵G_m极化码直接SC译码的复杂度为O(2^mNlog_mN)。文献[14]提出一种W-表达式方法来简化递归公式f_i0(*l)和f_i1(*l)。当m≤16时, 基于W-表达式方法, SC译码复杂度降低为O(mNlog_mN)。因此, 本文采用基于W-表达式方法的SC译码。

2 GA-DE方法与Tal-Vardy方法 2.1 GA-DE方法

本文通过一个简单的例子, 阐述GA-DE方法构造高维核矩阵极化码时存在一定程度的失真。

设一个G₆核矩阵的l-表达式为:^[15]

$ {\mathit{\boldsymbol{G}}_6} = \left( {\begin{array}{*{20}{c}} 1&0&0&0&0&0\\ 1&1&0&0&0&0\\ 1&0&1&0&0&0\\ 1&0&0&1&0&0\\ 1&1&1&0&1&0\\ 1&1&0&1&0&1 \end{array}} \right) $

基于该核矩阵, l₆⁽³⁾的l-表达式为:

$ \begin{array}{l} l_6^{\left( 3 \right)} = \underbrace {\left( {{l_0}\diamondsuit \left( {{l_1} + \left( {{l_2} + {l_4}} \right)\diamondsuit \left( {{l_3} + {l_5}} \right)} \right)} \right)}_{部分\;1} + \\ \;\;\;\;\;\;\;\underbrace {\left( {{l_3}\diamondsuit \left( {\left( { - {l_0} + {l_1}} \right)\diamondsuit \left( {{l_2} + {l_4}} \right) + {l_5}} \right)} \right)}_{部分\;2} \end{array} $

(6)

其中, $l_6^{\left(3 \right)} = {\log _a}\frac{{W_6^{(3)}\left({y_0^5, u_0^2|{u_3} = 0} \right)}}{{W_6^{(3)}\left({y_0^5, u_0^2|{u_3} = 1} \right)}}$是位信道对数似然比, ${l_i} = {\log _a}\frac{{W\left({{y_i}|{x_i} = 0} \right)}}{{W\left({{y_i}|{x_i} = 1} \right)}}, i = 0, 1, \cdots, 5$是信道输出对数似然比。文献[13]中给出了式(6)的似然比形式, 本文将其转化为对数似然比形式。

l₆⁽³⁾中引入了相同的随机变量, 例如部分1和部分2中2个相同的l_i(i=0, 1, …, 5)。部分1和部分2显然相关, 这违背了高斯假设(多个独立随机变量相加的结果为高斯分布)。因此, GA-DE方法构造出的高维核矩阵极化码会产生一定的失真, 这也在下文的实验中得到了验证。

2.2 Tal-Vardy方法

为不失一般性, 考虑G₂核矩阵的递归信道转化如下:

$ W_2^{\left( 0 \right)}\left( {y_0^1\left| {{u_0}} \right.} \right) = \frac{1}{2}\sum\limits_{{u_1}} {W\left( {{y_0}\left| {{u_0} \oplus {u_1}} \right.} \right)W\left( {{y_1}\left| {{u_1}} \right.} \right)} $

(7)

$W_N^{(0)}\left({y_0^{N - 1}|{u_0}} \right)$可以通过式(7)递归构造。原始信道W的输出字母集大小假定为μ, 即|y|=μ。执行式(7), 输出字母集大小增大到μ², 即|y₀¹|=μ²。因此, 信道$W_N^{(0)}\left({y_0^{N - 1}|{u_0}} \right)$输出字母集大小随码长N呈指数增长, 即|y₀^N－1|=μ^N。Tal-Vardy方法的基本思想是用一个降级或升级的信道近似W₂⁽⁰⁾(y₀¹|u₀), 使得最大输出字母集大小为μ。Tal-Vardy方法可以分解为2步:

1) 构造信道W₂⁽⁰⁾(y₀¹|u₀)。

2) 输出字母集大小从μ²减小至μ。

给定一个G_m核矩阵, 递归公式(7)转换为:

$ \begin{array}{*{20}{c}} {W_{{\mathit{\boldsymbol{G}}_m}}^{\left( 0 \right)}\left( {y_0^{m - 1}\left| {{u_0}} \right.} \right) = \frac{1}{{{2^{m - 1}}}}\sum\limits_{u_1^{m - 1}} {W\left( {{y_0}\left| {{x_0}} \right.} \right)W\left( {{y_1}\left| {{x_1}} \right.} \right) \cdots } }\\ {W\left( {{y_{m - 1}}\left| {{x_{m - 1}}} \right.} \right)} \end{array} $

(8)

式(8)表明W_Gm⁽⁰⁾(y₀^m－1|u₀)的输出字母集大小为μ^m, 其随着核矩阵大小m呈指数增长, 这对于一个较大维数的核矩阵将不切合实际。因此, Tal-Vardy方法不适用于大维数的核矩阵。

3 快速MC构造方法

由于GA-DE方法和Tal-Vardy方法推广至高维核矩阵时存在局限, 本文采用MC构造方法设计高维核矩阵极化码。传统SC译码具有较高延迟, 而在实际应用中, 利用MC构造方法无需对每一位进行连续译码。因为位信道具有对称性, 在用Pe(W_N⁽ⁱ⁾)评估位信道W_N⁽ⁱ⁾时, 假定SC译码过程中β为全0向量, 所以当一个节点v_i被激活时, P_vi无需等待β, 可以立刻进行计算, 且同一层所有节点的P_v能够并行计算。因此, 利用MC构造方法可以明显缩短SC译码的延迟。

MC构造方法模拟SC译码的过程如下:

1) 对每一位重复执行SC译码。

2) 通过大量的仿真并基于每一位的差错概率评估每个位信道。

3) 对所有位信道的差错概率排序, 选择具有最低差错概率的k个位信道作为信息位集合。

在MC构造方法的基础上, 本文提出一种TPMC方法, 以在不损失极化码译码性能的同时降低MC方法的复杂度。

3.1 TPMC方法

GA-DE方法所构造的最可靠和最不可靠的位可信。因此, 在本文TPMC方法的第1阶段, 利用GA-DE方法获得一些最可靠和最不可靠的位并将这些位固定为冻结位; 在第2阶段, 利用MC方法衡量剩余位的差错概率, 从剩余位中挑选差错概率较低的位, 与第1阶段中最可靠的位结合构成信息位集合。

令A_m和A_l分别表示由GA-DE方法产生的最可靠的位集合和最不可靠的位集合。算法2描述了TPMC方法的详细过程, 其中, A_r={r₁, r₂, …, r_p}为从[N]中移去最可靠的位和最不可靠的位而构成的剩余位集合, e(A_r)为向量e_r1, e_r2, …, e_rp。

算法2     TPMC方法

输入    差错向量e, 核矩阵G_m, 码长N, 码率R, 信息位u₀^N－1=0₀^N－1

输出    信息位集合A

1.获得A_m和A_l:利用GA-DE方法生成最可靠的位集合A_m和最不可靠的位集合A_l

2.令A_r=[N]－(A_m∪A_l), 且假定A_r={r₁, r₂, …, r_p}

3.for  i=0, 1, …, p  do

4.e[r_i]←0

5.end for

6.for  j=0, 1, …, M－1  do

7.x₀^N－1=0₀^N－1进入信道, 接收端的信道输出为y₀^N－1

8.将集合A_m和A_l中的位固定为冻结位并执行SC译码算法1

9.end for

10.选择e(A_r)中$\left\lceil {{\rm{NR}}} \right\rceil - \left| {{{\rm{A}}_{\rm{m}}}} \right|$个最小的差错概率对应的索引组成A_i

11.输出A=A_m∪A_l

在算法2的SC译码过程中, 所有冻结位的计算可以被忽略, 因此, 在激活节点v时, 如果v是一个冻结节点, 则可以跳过P_v的计算而直接译码下一个节点。

3.2 TPMC方法的复杂度分析

TPMC方法第2阶段确定的冻结位个数决定了方法的复杂度大小, 越多的位被固定为冻结位, 方法复杂度越低。仿真结果表明, 在不损失译码性能的情况下, TPMC方法能将多数位固定为冻结位。例如, 一个码长3 375、码率1/2的G₁₅^⊗3极化码在第2阶段可以固定3 200位为冻结位, 一个码长4 096、码率1/2的G₁₆^⊗3极化码在第2阶段可以固定3 750位为冻结位。

假定在SC译码下计算一个节点v的P_v需要一个时钟, 则TPMC方法所需的时钟数与SC译码树结构中的非冻结节点个数成正比。表 1所示为MC方法和TPMC方法的复杂度比较结果, 其中, Num-fro表示TPMC方法中第2阶段的冻结位个数, Num-MC表示在MC方法的SC译码过程中需要计算的节点个数, Num-TPMC表示在TPMC方法的SC译码过程中需要计算的节点个数, Rec-times表示TPMC方法相对于MC方法复杂度降低的倍数, 其计算公式为$\mathit{Rec}{\rm{ - }}\mathit{times}{\rm{ = }}\mathit{Num - MC}{\rm{/}}\mathit{Num - TPMC}$。

由表 1可以看出, 对于一个G₁₅^⊗3极化码, 码长为3 375, 利用MC方法构造时, SC译码过程中需要计算3 615个节点, 在利用TPMC方法时, 先固定3 000位冻结位, 仅需计算498个节点, 复杂度降低了86%。表 1的结果表明, 相比MC方法, TPMC方法能够大幅降低复杂度。

4 仿真结果与分析

本节通过仿真验证TPMC方法构造高维核矩阵极化码时的性能。考虑二进制相移键控(Binary Phase Shift Keying, BPSK)调制和一个加性高斯白噪声(Additive White Gaussian Noise, AWGN)信道, 二进制码字$\mathit{\boldsymbol{x}}\mathit{ = }\left({{\mathit{\boldsymbol{x}}_0}, {\mathit{\boldsymbol{x}}_1}, \cdots, {\mathit{\boldsymbol{x}}_{N - 1}}} \right)$基于${\mathit{\boldsymbol{s}}_n} = 1 - 2{\mathit{\boldsymbol{x}}_n}$映射到一个传输序列$\mathit{\boldsymbol{s}}\mathit{ = }\left({{\mathit{\boldsymbol{s}}_0}, {\mathit{\boldsymbol{s}}_1}, \cdots, {\mathit{\boldsymbol{s}}_{N - 1}}} \right)$上。在接收端, 获得接收向量$\mathit{\boldsymbol{y}}\mathit{ = }\left({{\mathit{\boldsymbol{y}}_0}, {\mathit{\boldsymbol{y}}_1}, \cdots, {\mathit{\boldsymbol{y}}_{N - 1}}} \right)$, 其中, ${\mathit{\boldsymbol{y}}_n} = {\mathit{\boldsymbol{s}}_n} + {\mathit{\boldsymbol{z}}_n}$、$\mathit{\boldsymbol{z}}\mathit{ = }\left({{\mathit{\boldsymbol{z}}_0}, {\mathit{\boldsymbol{z}}_1}, \cdots, {\mathit{\boldsymbol{z}}_{N - 1}}} \right)$是独立同分布随机变量, 都满足均值为0、方差为N₀/2的高斯分布。

4.1 最优M值

最优M值指在保证MC方法所设计极化码取得最佳译码性能的前提下, 可以允许的最小M值。最优M值通过以下过程获得:每次10倍地增加M值, 当发现增加M值并未提高译码纠错性能时, 则将前一个M值作为最优M值。例如, 仿真发现用MC方法构造G₁₅^⊗3极化码时, M=1e5和M=1e6有相同的误帧率(Frame Error Rate, FER), 则令M=1e5为该极化码的最优M值。

4.2 有效性分析

图 2所示为MC方法和TPMC方法构造的2个极化码(G₁₅^⊗3和G₁₆^⊗3)在SC下的FER结果。其中, 极化码码率为1/2, 所有码在信噪比SNR=2.0 dB下构造。在TPMC方法中, 对G₁₅^⊗3极化码固定N_f=3 200位, 对G₁₆^⊗3极化码固定N_f=3 750位。其中, N_f表示TPMC方法第2阶段中的全部冻结位个数(最可靠的位和最不可靠的位)。由表 1可知, 相比MC方法构造的G₁₅^⊗3极化码和G₁₆^⊗3极化码, TPMC方法复杂度分别降低了92.6%和89.1%。从图 2可以看出, TPMC方法和MC方法所构造极化码的FER几乎相同。

图 3所示为TPMC方法分别冻结N_f=3 200、3 250、3 300、3 350、3 375位后构造的5个极化码以及GA-DE方法构造的极化码在SC下的FER结果。其中, 码率为1/2, 所有码在SNR=2.0 dB下构造。从图 3可以看出, 冻结N_f=3 375位后构造的G₁₅^⊗3极化码与GA-DE方法构造的G₁₅^⊗3极化码等价。在TPMC方法中冻结N_f=3 350位, 即仅将剩余的25位作为非冻结位, 所构造的G₁₅^⊗3极化码明显优于GA-DE方法构造的G₁₅^⊗3极化码, 即在TPMC方法中将很少的位作为非冻结位, 能够提高译码纠错性能。

在不损失译码性能的情况下, N_f的值可以非常接近极化码的码长, 但目前还没有一个规则可以确定最优的N_f值, 本文通过仿真来选择较优的N_f值。

4.3 高维核矩阵极化码性能分析

图 4所示为TPMC方法和GA-DE方法构造的G₁₅^⊗3码在LSC下的FER结果。图 5所示为TPMC方法和GA-DE方法构造的G₁₆^⊗3码在LSC下的FER结果。其中, G₁₅^⊗3、G₁₆^⊗3的M值分别为1e5和1e6, 码长分别为3 375和4 096, 码率都为1/2。另外, Tal-Vardy方法构造的G₂^⊗12极化码也被引入进行比较。从图 4、图 5可以看出, 在LSC译码下, TPMC方法构造的极化码明显优于GA-DE方法构造的极化码, 在SC译码(L=1)下, 相比G₂^⊗12极化码, 用TPMC方法构造的G₁₅^⊗3和G₁₆^⊗3极化码的译码性能提升明显, 且G₁₅核和G₂核矩阵的极化速率几乎相同。

图 6所示为G₁₆^⊗3和G₂^⊗12极化码在LSC下的FER比较, G₁₆^⊗3和G₂^⊗12极化码分别通过TPMC方法和Tal-Vardy方法构造, M值为1e6, 码长为4 096, 码率为1/2。由图 6可以看出, 在LSC译码下, 相比Tal-Vardy方法构造的G₂^⊗12极化码, 同等码长的G₁₆^⊗3极化码性能提升明显。

5 结束语

本文提出一种基于MC的高维核矩阵极化码构造方法TPMC。利用GA-DE方法获得最可靠的位和最不可靠的位, 将这些位固定为冻结位并对剩余位执行MC方法, 以构造高维核矩阵极化码。仿真结果表明, 与MC方法相比, TPMC方法能够将多数位固定为冻结位而不损失极化码的译码性能, 并大幅降低计算复杂度。但TPMC方法主要降低SC译码中冻结位节点的计算复杂度, 下一步将研究能够降低其他节点计算复杂度的方法。