调整延伸极化码的码长度的方法及装置与流程

本发明是有关于一种错误校正方法和装置，特别是关于通过利用一延伸极化码(extendedpolarcode)增加编码可靠度的一种方法和装置。

背景技术：

在信息传输和处理区域中，多个信道可用来传输一条信息。信道通常都有很多噪声(noisy)并且有不正确的传输数据位的机率，例如被称为错误机率(probabilityoferror)。也就是说，输入一二进制数据1，信道可能会输出一错误的二进制数据0，反之亦然。相似的，在数据存储区域中，多个存储单元被用来存储数据。由于噪声或外部干扰，存储在一存储单元的一数据位可能会被改变，以使从存储单元中读取出的数据位不同于被写到此存储单元的数据位。这种存储数据位被改变的机率被称为「错误机率」。

为了降低传输或存储信息/数据的错误，而进一步降低错误机率，欲被传输或存储的信息通常在传输之前被一错误校正方法编码。在此文中，信息/数据的传输和存储被统称为信息传输以简化描述。因此，除非特别说明，「信息传输」或相似的用语被理解为代表信息/数据的传输及/或存储。进一步的，除非特别说明，欲被传输的信息也被简化描述为信息。在一编码信息的例子中，信息的位和多个冻结位被编码成为一编码位，之后经由信道被传输或存储到存储单元。这种编码可被认为是一个输入向量转换为一输出向量的转换，由一信息位源和冻结字节成的输入向量被一产生器矩阵转换为由欲经由信道被传输或存储在存储单元的编码字节成的一输出向量。每一输入位对应此转换的一位通道，且每一位通道具有对应的一错误机率。

极化编码是一种线性方块错误校正编码方法，可重新分配位通道中的错误机率。在极化编码之后，一些位通道相较于其他位通道具有一较低的错误机率。具有较低的错误机率的位通道则可被用来传输信息，而其他位通道则被冻结(frozen)，也就是用来传输冻结位。由于传送端和接收端都知道哪个位通道被冻结，因此任何数据都可被分配到冻结位通道。例如，一二进制数据0被分配到每一冻结位通道。

然而，极化码(用于极化编码的码)的建立使传统极化码的码长度受到特定限制。在本发明中，传统极化码被称为「标准极化码」。对应使用一传统极化码的一极化码机制被称为一「传统极化码机制」或一「标准极化码机制」。特别的说，传统极化码机制限制码长度为2的幂次方，也就是2ⁿ，其中n为正整数。这引起了使用极化码的系统的一额外复杂度。一种解决此问题的方法是将被编码的信息分割为具有合适于编码机制的长度的片段以创造长度可适性(length-compatible)的极化码。

一种用于创造长度可适性的示范方法的尝试包含例如：毁损(puncturing)或缩短。这两种尝试通过从一原始长度2ⁿ的码长度切断而达到一任意码长度以使一些位不被传输。然而，随着码长度从2ⁿ被缩短，使码的效能损失会增加。此码的效能损失可通过参数，例如位错误率(biterrorrate，ber)或者帧错误率(frameerrorrate，fer)测得。图1绘示一码的码长度和此尝试毁损或缩短码的效能损失之间的关系的示意图。在图1中，一较高程度的灰色指示较严重的效能损失。如图1所示，当此码长度等于2的幂次方时，没有效能损失。当此码的长度从2的幂次方减少时，效能损失增加。

然而，这种示范的尝试并不适合应用在特定情况，例如存储器装置中的数据存储。举例来说，这是因为在存储器装置中，数据通常以一8倍数的尺寸的单位存储，例如1024。并且加上一小数量的冻结位到每一方块码使得此码的长度稍微超过2ⁿ。在这种情况下，毁损或缩短的尝试会导致如图1所示的严重的效能损失。

技术实现要素：

根据本发明，提供一种方法以增加编码可靠度。此方法包含产生用于延伸极化码的产生器矩阵。延伸极化码包含标准极化码部分及额外冻结部分。标准极化码部分有k个信息位通道及n-k个冻结位通道的n个位通道。n为2ⁿ，n为正整数，k为一小于或等于n的正整数。标准极化码部分包含2^m-1个母码，m为大于1的正整数。额外冻结部分有q个额外冻结位通道，q为一正整数。在k个信息位通道中的q个信息位通道使用q个额外冻结位通道承受一m阶再极化。此方法更包含接收包含k个信息位和n+q-k个冻结位的输入向量，并使用产生器矩阵转换输入向量为包含n+q个编码位的输出向量。k个信息位被分配到k个信息位通道，n+q-k个冻结位被分配到n-k个冻结位通道及q个额外冻结位通道。

又根据本发明，提供一种装置以增加编码可靠度。此装置包含处理器及非易失性的计算机可读取存储媒体。非易失性的计算机可读取存储媒体存储被处理器执行的指令，以使处理器执行以下指令：产生用于延伸极化码的产生器矩阵，延伸极化码包含标准极化码部分及额外冻结部分，标准极化码部分有k个信息位通道及n-k个冻结位通道的n个位通道，n为2ⁿ，n为正整数，k为一小于或等于n的正整数，标准极化码部分包含2^m-1个母码，m为大于1的正整数，额外冻结部分有q个额外冻结位通道，q为一正整数，在k个信息位通道中的q个信息位通道使用q个额外冻结位通道承受一m阶再极化。此指令更使处理器接收包含k个信息位和n+q-k个冻结位的输入向量，并使用产生器矩阵转换输入向量为包含n+q个编码位的输出向量。k个信息位被分配到k个信息位通道，n+q-k个冻结位被分配到n-k个冻结位通道及q个额外冻结位通道。

又根据本发明，提供一种非易失性的计算机可读取存储媒体存储被处理器执行的指令，以使处理器执行以下指令。产生用于延伸极化码的产生器矩阵。延伸极化码包含标准极化码部分及额外冻结部分。标准极化码部分有k个信息位通道及n-k个冻结位通道的n个位通道。n为2ⁿ，n为正整数，k为一小于或等于n的正整数。标准极化码部分包含2^m-1个母码，m为大于1的正整数。额外冻结部分有q个额外冻结位通道，q为一正整数。在k个信息位通道中的q个信息位通道使用q个额外冻结位通道承受一m阶再极化。此指令更使处理器接收包含k个信息位和n+q-k个冻结位的输入向量，并使用产生器矩阵转换输入向量为包含n+q个编码位的输出向量。k个信息位被分配到k个信息位通道，n+q-k个冻结位被分配到n-k个冻结位通道及q个额外冻结位通道。

本发明的特征和优点可以从下列的描述中说明，并且部分地是从描述中显而易见的、或者可通过本发明的实施而得知。这些特征和优点可以由所附的权利要求所特别指出的元件和其组合实现。

应当理解的是，前述一般的描述和以下的详细描述都只是示例性和说明性的，并不如要求保护权利要求用以限制本发明的。

所附的附图包含在说明书中，并与说明书构成本说明书的一部分，附图示出了本发明的几个实施例，并且可参照说明书用于解释本发明的原理。

附图说明

图1绘示一码的码长度和此尝试毁损或缩短码的效能损失之间的关系的示意图。

图2绘示一实施例使用延伸极化码机制的方法的流程图。

图3绘示示范的标准极化码机制的编码架构的示意图

图4绘示示范实施例的延伸极化码机制的编码架构的示意图。

图5绘示示范实施例的一修正延伸极化码机制的示意图。

图6绘示另一实施例使用延伸极化码机制的方法的流程图。

图7绘示一示意母码机制的编码架构的示意图。

图8绘示示范实施例的一2阶延伸极化码机制的编码架构的示意图。

图9绘示示范实施例的延伸极化码的码长度和此码的效能损失之间的关系的示意图。

图10绘示示范实施例的延伸极化码的一装置的方块图。

【符號說明】

202：建立标准极化码以决定信息位通道

204：再极化最不可靠的信息位通道以降低它们的错误机率

206：放信息到用来传输的信息位通道

c1～c10：位通道

u1～u10、v1～v10：输入位

x1～x10：编码位

y1～y10：位

w：信道

n1、n2、np：码字符长度

602：将标准极化码分为多个母码

604：建立每一母码以决定针对母码的信息位通道

606：从母码中再极化最不可靠的信息位通道以降低它们的错误机率

608：放信息到用来传送的信息位通道

1000：装置

1002：处理器

1004：存储器

1006：输入/输出接口

具体实施方式

符合本发明的实施例包含通过延伸一极化码增加编码可靠度的一方法和一装置。

在本文中，参照所附附图仔细地描述本发明的一些实施例。尽可能地，附图中相同的参考符号用来表示相同或相似的元件。

一传统的极化码可被标示为一(n，k)极化码，也被称为一(n，k)标准极化码，其中n代表一码字符长度，也就是标准极化码的位通道(位通道)的总数等于2ⁿ，其中n为正整数，k为不大于n的整数且k代表被传输的一条信息的信息长度。因此，使用一标准极化码，k位的信息被分别分配到k个位通道中相较于其他位通道具有一较低机率错误的的一个位通道。n个位通道的剩余者，也就是剩余的n-k个位通道被冻结(冻结)。用来传输信息的位通道在此文中被称为「非冻结位通道」。

根据本发明，q个最不可靠的非冻结位通道被再极化(re-polarized)以增强它们的可靠度，其中q是一不大于k的整数。也就是说，这些q个非冻结位通道并不仅经过一标准极化程序，也经过一额外极化程序。为了再极化这q个非冻结位通道，使用额外的q个冻结位通道。也就是说，为了再极化这q个非冻结位通道，这(n，k)标准极化码被延伸为一(n+q，k)延伸极化码。通过选择q的值，延伸极化码的一码长度可被调整，而因此使其长度可适性(length-compatible)。在一些实施例中，可根据经验选择q。例如可选择n＝1024且q＝114以编码k＝800位的数据。

图2绘示依据本发明一实施例使用延伸极化码机制编码一条信息的一示范方法200。方法200可被执行在一存储器装置上，例如一单层式存储单元(single-levelcell)存储器装置，或者一多层式存储单元(multi-levelcell)存储器装置，或者一通信装置。根据方法200，一(n，k)标准极化码被延伸为具有q个额外冻结位通道的一(n+q，k)延伸极化码，用以传输k位的信息。依据本发明的实施例，q可远小于n。例如q小于n/2。再举一例，q小于n/3。

如图2所示，在步骤202中，建立标准极化码以决定k个最佳(optimal)位通道。可使用多种不同的建立方法，例如互消息(mutualinformation)、巴氏参数(bhattacharyyaparameter)、或者错误机率。举例来说，使用错误机率建立码，在码的建立之后，这些位通道具有不同的错误机率。因此k个位通道中具有错误机率小于其他n-k个位通道的错误机率的位通道被选定为最佳位通道。这些最佳位通道会被用来传输信息，且因此被称为信息位通道。

依据本发明，这k个信息位通道的对应错误机率可不同于彼此。当一位通道具有一较大的错误机率时，此位通道是较可靠的。在步骤204中，q个最不可靠的信息位通道通过使用q个额外冻结位通道在这q个最不可靠的信息位通道上执行一额外通道极化被再极化以降低它们的错误机率。

在步骤206中，信息被分配到k个信息位通道，k个位通道包含用来传输的q个再极化信息位通道。其余n+q-k个位通道被冻结，也就是说一二进制数据0被分配到n+q-k个冻结位通道的每一个。

以下描述一例以解释本发明实施例的延伸极化码机制。图3绘示一(8，5)标准极化码机制的一编码架构(产生器矩阵的可视化表示)，此标准极化码包含8个位通道(c3、c4、…、c10)用来传输5个信息位和3个冻结位，统称为「输入位」(u3、u4、…、u10)，其中每一输入位ui被分配到对应的一位通道ci，i＝3，4，...10。通过建立一(8，5)标准极化码而得到此编码架构。如图3所示，这8个位被分配到8个位通道，且被编码以形成编码位x3、x4、…、x10。这些编码位之后(在传输信息的情况下)经由信道w被传输或者(在存储数据的情况下)被存储在存储单元w。接收端(在传输信息的情况下)接收传输的位y3、y4、…、y10，或者(在存储数据的情况下)读取被存储的位y3、y4、…、y10。在此例中，位通道c6～c10相较于位通道c3～c5是较可靠的。因此，位通道c6～c10被用来传输5个信息位，而位通道c3～c5被用来传输3个冻结位。

进一步的，在本发明中，在位通道c6～c10中，位通道c6和c7是较不可靠的，因此使用两个额外冻结通道承受一额外通道极化。

此额外通道极化将(8，5)标准极化码延伸为(10，5)延伸极化码。(10，5)延伸极化码的编码架构如图4所示，(10，5)延伸极化码包含如图4的虚线框所示的一标准极化码部分，以及虚线框外的一延伸极化码部分。此示范机制包含10个位通道c1、c2、…、c10，每一个位通道刚开始被分配到对应的输入位v1、v2、…、v10中的一个。

如图4所示，对应(10，5)延伸极化码，5个信息位v6～v10被分配到位通道c6～c10(信息位通道)，而5个冻结位v1～v5被分配到位通道c1～c5(冻结位通道)。输入位v3、v4、v5、v8、v9和v10直接通到位u3、u4、u5、u8、u9和u10而没有被改变，然而输入位v6和v7被输入位v1和v2极化，导致结果是位u6、u7、u1和u2。位u1和u2在输出向量中成为编码位x1和x2而没有被改变。其他位u3～u10被标准极化码部分进一步编码并在输出向量中成为编码位x3～x10。这些编码位之后(在传输信息的情况下)经由信道w被传输或者(在存储数据的情况下)被存储在存储单元w。接收端(在传输信息的情况下)接收传输的位y1～y10，或者(在存储数据的情况下)读取被存储的位y1～y10。

图5绘示本发明的实施例的另一延伸极化码机制。在本文中，如图5所示的延伸及化码也被称为一「修正延伸极化码」。修正延伸极化码同时再极化多个标准极化码，而因此增加弹性。并且，修正极化码更可改善错误校正效能。

如图5所示，p个标准极化码一起使用q个额外冻结位通道而被再极化。在p个标准极化码中，第j个标准极化码具有一nj的位数，其中j是一正整数且1≤j≤p。在第j个标准极化码的这nj个位中，kj个位为信息位，其中kj≤nj。根据修正延伸极化码，p个标准极化码被分开建立以得到每一信息位通道的错误机率，之后在p个标准极化码中所有信息位通道中的q个最不可靠的信息位通道使用q个额外冻结位通道而被再极化。在图5中，每一标准极化码标示为关联一额外冻结位通道。这仅仅用于说明，并不代表每一标准极化码都使用一额外冻结位通道而被再极化。根据修正延伸极化码，有可能一些标准极化码被再极化但另一些没有被再极化。并且，在修正延伸极化码中，额外冻结位通道的数量并不需要等于标准极化码的数量。

依据本发明，在修正极化码中，可使用不同数量的标准极化码或不同数量的冻结通道以达到使用相同总数的位编码相同数量的信息位。不同的标准极化码的尺寸可相同于或不同于彼此。举例来说，为了创造(1138，800)码，可使用n1＝1024和n2＝64的两个标准极化码，而剩余的50(＝1138-n1-n2)位为再极化的额外冻结位。或者，可使用n1＝512、n2＝512和n3＝64的三个标准极化码，而剩余的50位为再极化的额外冻结位。又或者，可使用n1＝1024、n2＝64、n3＝32和n3＝16的四个标准极化码，而剩余的2位为再极化的额外冻结位。由于对于相同码长度和相同码率可选择不同数量的标准极化码，修正极化码可增加弹性。

在上述图2-图4的示范方法中，整个(n，k)标准极化码被视为且被当作一个整体被处理。进一步的，(n，k)标准极化码中q个最不可靠的信息位通道的每一信息位通道使用额外q个冻结通道的一个冻结通道被再极化。在本发明中，使用一个对应的冻结通道对一个信息位通道的再极化，也被称为「一阶再极化」(one-stagere-polarization)或单一阶层再极化。

在一些实施例中，为了增加再极化程序的生产量(throughput)，(n，k)标准极化码可被分为s个母码(mothercode)，每一母码具有较短的码长度，且s个母码可被分开处理。其中n＝2ⁿ，s＝2^m-1，m为大于1的正整数，且例如为2或3。每一母码可被视为有较短码长度的一标准极化码。然而，由于缩短码长度会增加错误校正效能的损失，适合使用一多阶层的再极化，例如一m阶的再极化，以降低校正效能的损失，如下文所述。

图6绘示符合本发明的一实施例使用多阶层延伸极化码机制的另一方法600的流程图。方法600可被执行在一存储器装置上，例如一单层式存储单元(single-levelcell)存储器装置，或者一多层式存储单元(multi-levelcell)存储器装置，或者一通信装置。根据方法600，一(n，k)标准极化码被分为s＝2^m-1个母码，每一母码具有nr的码字符长度以及kr的信息长度，其中r为一正整数，且1≤r≤s，n＝n1+...+ns，且k＝k1+...+ks。在一些实施例中，所有nr皆相同，例如nr＝n/s＝2^n-m+1。在本发明中，kr可为相同或不同。在一些实施例中，选择kr以使s个母码包含相同或大约相同数目的信息位。分别建立这s个母码以得到每一信息位通道的错误机率，之后在第r个母码中的kr个信息位通道中最不可靠的qr个信息位通道被选择用以再极化，其中qr为小于kr的一正整数，qr可以是相同的或不同的。在一些实施例中，选择qr以使s个母码包含相同或大约相同数目的要被再极化的信息位通道。更具体地说，总共q(＝q1+...+qs)个被选择的信息位通道使用q个额外冻结位通道承受m阶的再极化被再极化。由于从每一母码中选择了至少一信息位通道用来被再极化，q小于或等于s(＝2^m-1)。如图2-图4所描述的延伸极化码机制可被视为m＝1的特例，且可被称为一一阶或单阶的延伸极化码机制。

如图6所示，在步骤602中，将(n，k)标准极化码分为s个母码。每一母码包含nr个位以编码kr个信息位。在步骤604中，依据相似于如图2所描述的建立方法建立每一母码以决定kr个最佳位通道，即kr个信息位通道。在步骤606中，从第r个母码中选择最不可靠的qr个信息位通道，即在建立母码之后在kr个信息位通道中具有最高错误机率的qr个信息位通道，且所有q(＝q1+...+qs)个被选择的信息位通道通过在q个被选择的信息位通道上使用q个额外冻结位通道执行一额外的m阶通道极化被再极化以降低它们的错误机率。在步骤608中，信息被分配到k个信息位通道，k个信息位通道包含用来传输的q个再极化信息位通道。其余n+q-k个位通道被冻结，也就是说一二进制数据0被分配到n+q-k个冻结位通道的每一个。

以下描述一例以解释本发明实施例的多阶延伸极化码机制。以下描述的例子也使用(8，5)标准极化码作说明。在此例中，(8，5)标准极化码被分为两个母码，即一(4，2)母码以及一(4，3)母码。图7绘示一(4，2)母码以及一(4，3)母码的一编码架构的示意图。(4，2)母码包含4个位通道c3、c4、c5和c6用来传输4个输入位u3、u4、u5和u6，(4，3)母码包含4个位通道c7、c8、c9和c10用来传输4个输入位u7、u8、u9和u10，其中每一输入位ui被分配到对应的一位通道ci，i＝3，4，...10。分别建立(4，2)母码以及(4，3)母码而得到图7所示的编码架构。如图7所示，这8个位被分配到8个位通道，且被编码以形成编码位x3、x4、.…、x10。

此两阶再极化将(8，5)标准极化码延伸为(10，5)延伸极化码。(10，5)延伸极化码的编码架构如图8所示，(10，5)延伸极化码包含如图8的虚线框所示的两个母极化码部分，以及虚线框外的一2阶延伸极化码部分。此示范机制包含10个位通道c1、c2、…、c10，每一个位通道刚开始被分配到对应的输入位v1、v2、…、v10中的一个。

如图8所示，对应(10，5)延伸极化码，5个信息位v5、v6、v8、v9和v10被分配到位通道c5、c6、c8、c9和c10(信息位通道)，而5个冻结位v1、v2、v3、v4和v7被分配到位通道c1、c2、c3、c4和c7(冻结位通道)。输入位v3、v4、v6、v7、v9和v10直接通到位u3、u4、u6、u7、u9和u10而没有被改变，然而输入位v5和v8与输入位v1和v2承受一2阶再极化，产生位u5、u8、u1和u2。位u1和u2在输出向量中成为编码位x1和x2而没有被改变。其他位u3～u10被进一步分别编码为两个母极化码部分并在输出向量中成为编码位x3～x10。

依据本发明，虽然示范的多阶延伸编码机制和示范的单阶延伸编码机制使用相同数目的位通道，包含相同数目的额外冻结位通道以及相同数目的信息位通道，在这两个例子中在建立程序后和再极化程序之后这些通道的错误机率为不相同被再极化的通道也不相同。进一步的，如上所述，使用多阶层延伸极化码机制，可对不同的母码执行平行的译码操作，因此相较于单阶层的延伸极化码机制可增加生产量。举例来说，对于n(＝2ⁿ)位的标准极化码，一m阶层延伸极化码机制的生产量增益大约为单阶层延伸极化码机制的(n/(n-m+1))2^m-1倍。

在上述的示范多阶层延伸极化码机制中，每一母码分别被视为输入位的分配，即一位通道的错误机率只与同一母码的其他位通道的错误机率作比较以判断此位通道是否应为一信息位通道，并判断此位通道是否应被再极化。在一些实施例中，所有母码被一起视为输入位的分配。也就是说，虽然此母码被分开建立以判断此位通道的错误机率，一位通道的错误机率与同一母码或其他母码中的所有其他位通道的错误机率作比较以决定此位通道是否应为一信息位通道，并判断此位通道是否应承受多阶再极化。此修正编码机制也被称为「修正多阶层极化码机制」。依据修正多阶层极化码机制，一母码可包含或不包含信息位通道、冻结位通道、或要被再极化的信息位通道。进一步的，要被再极化的信息位通道的总数不需要大于或等于母码的数目，也就是q的值可小于或等于2^m-1。

举例来说，请参照图8，依据修正多阶层延伸极化码机制，在两个母码被建立之后位通道c3～c10被互相比较。位通道c5、c6、c8、c9和c10相较于位通道c3、c4、c7被判断为较可靠的，因此被用来当作信息位通道。进一步的，在5个被决定为信息位通道中，位通道c5和c8为较不可靠的，因此承受2阶再极化。

此修正多阶层延伸极化码机制相似于参照图5所描述的修正延伸极化码机制，区别在于在此修正延伸极化码机制之中，q个较不可靠的信息位通道承受一阶再极化，然而在此修正多阶层延伸极化码机制之中，q个最不可靠的信息位通道承受多阶再极化。

依据本发明，用于延伸极化码的一产生器矩阵，也被称为「延伸产生器矩阵」，是通过再极化n个位通道的k个信息位通道中的q个信息位通道而产生。通过建立包含n个位通道的标准即化码的一或多个母码，来决定这k个信息位通道以及每一信息位通道有多不可靠(以信息位通道的错误机率表示)。之后，此延伸产生器矩阵被用来将包含k个信息位和n+q-k个冻结位的一输入向量转换为包含n+q个编码位的一输出向量，其中k个信息位被分配到延伸产生器矩阵的k个信息位通道，且n+q-k个冻结位被分配到n+q-k个冻结位通道。

与传统的极化码机制相比，本发明的延伸极化码机制提供一优选弹性的编码长度，使系统管理变容易。相较于其他长度可适性极化码机制，例如缩短极化码机制，本发明的延伸极化码机制具有较低的可靠性效能损失。也就是说，本发明的延伸极化码机制相较于传统极化码机制提供了较佳的弹性。

图9绘示一延伸极化码的码长度和此码的效能损失之间的关系的示意图。如图1和图9所示，延伸极化码的效能损失与毁损或缩短极化码的效能损失的趋势相反。

本发明的实施例更包含一硬件装置被编程以执行符合本发明的方法，或者包含有一处理器和一非易失性的计算机可读取存储媒体的一装置。图10绘示依据本发明实施例的一装置1000的方块图。装置1000包含处理器1002和存储器1004。存储器1004耦接到处理器1002。存储器1004可为一非易失性的计算机可读取存储媒体，并且存储引起处理器1002执行符合本发明的方法的指令。装置1000更包含一输入/输出接口1006以促进装置100和一外部元件或装置之间的通信。

本领域普通技术人员依据本说明书和本发明揭露的实施方式容易想到其他实例。应当理解的是本发明说明书和这些例子仅是示范性的而非用以限定本发明。本发明真正的保护范围和精神在权利要求所表示。