极化码编码器的硬件实现

舒长青，沙 金

(南京大学微电子所，江苏南京 210046)

最近，由 Arikan提出的极化码［1－2］是编码理论的一个重大突破。极化码是目前唯一的一种有确定构造方式的能在二进制离散无记忆信道下达到香农容量的信道编码方式，同时，它具有较低的编解码复杂度O(NlogN)，N是码长。然而，在实际应用中，为了达到理想的纠错性能，极化码的码长一般需要大于210，故编码器难以对所有信息比特同时编码，否则硬件实现比较困难，本文提出了一种基于部分并行输入编码器的结构设计。

1 极化码基础

对于二元离散无记忆信道W(B－DMC W)，将N个独立的信道W按照一定的方式进行合并，可以获得长度为N的矢量信道，即有对于B－DMC W，WN:xN→yN，其中满足N=2n，n≥0。当n=0时，W1=W，n=1时的信道合成如图1所示。

图1 两个W信道的合并示意图

对于更一般的情况，由N个信道W合成的信道为WN。WN可以递归地由两个WN/2信道构成，其中WN/2是由N/2个W信道合并而成［3］。如图2所示，其中RN是个排列运算，将奇数比特按顺序置于偶数比特前，即(1，2，3，…，N)→ (1，3，…，N－1，2，4，…，N)。

图2 基于信道WN/2的信道WN

2 极化码编码

2.1 生成矩阵

如图2所示，从信息比特u1N通过线性变化得到中间参量，再经过RN变换，即奇数比特与偶数比特分离，然后进入两个分离信道WN/2，也即转变为两个N/2码长的极化码，经过lbN次迭代之后，可将信息比特编码为，即可等效地记一个N阶矩阵GN［4］，使得

这里称GN为生成矩阵。可以得到

式中:BN是比特反转矩阵，⊗是两个矩阵的Kronecker积。

式中:GN(Λ)表示GN中与Λ中元素对应的那些行所组成的子矩阵，GN(ΛC)为GN(Λ)的陪集。

2.2 信息位的选取

信息位的选取对编码有着重要的影响，是极化码编码的重要内容。如果选择完全好的信道进行信息比特传输，当编码块长度达到一定范围时，就能实现真正的无失真可靠通信。E.Arikan提出一种信息位选取的方法［5］，针对BEC信道具有较低复杂度和实用性，但对于其他信道未能找到一个有效的方法去实现这个编码构造。自极化码被提出以来，很多学者对其信息位选取方法展开了研究。目前主要有3种选取方法，Monte－Carlo方法、BEC方法及Density evolution方法。

3 编码器设计

3.1 基本模块

极化码在理论上可以在B－DMC上通信达到香农极限，但是需要比较长的码字，通常N≥210，上文描述了极化码的生成矩阵和信息位的选取，但由于码长过大，极化码的编码器设计比较复杂，本实验提出了一种基于部分并行输入的编码器硬件结构，可以化简至比较简单的W4信道的编码模块。

编码器的实现主要是两个模块，一个是RN变换，采取一种特定的读取和存储机制实现，另一个模块实现相邻比特的异或，每次处理32 bit，即16个二进制异或门即可实现。

如图3所示，1 024 bit每次输入32位，将奇数位与相邻的偶数位比特异或，将异或后的16位奇数位和未变的16位偶数位分别存入两个RAM中，其中偶数位用16位寄存器寄存一个周期，实现两个RAM的“乒乓”存储。Memory swich为地址选择器，按特定顺序读取和存储RAM中各地址的比特实现RN变换。4个RAM皆为单端口RAM，深度为32，每个地址存储16 bit。用RAM 1和RAM 2分别存储第一次处理后的奇偶位比特，然后将两个RAM中的比特分别读出再通过该模块，只要在每次迭代的过程中适当地改变地址选择器，将特定地址的比特按顺序读出，经过处理更新完毕后再存入另两个RAM中，进行迭代操作。

图3 基本处理模块

3.2 读取和存储机制

在信息比特的处理中，采用一种特定的读取和存储机制，利用“乒乓存储”，在读取数据的同时向其他RAM写入数据，可以提高系统的吞吐率和性能，实现数据的无缝连接和处理，具体步骤如下:

1)在每个时钟周期内，按顺序读入32位信息比特。假设原始1 024 bit按顺序编号为1，2，3，…，1 024。在第1周期，将处理后的1，3，…，31存入RAM 1的地址1;第2周期，将33，35，…，63存入 RAM 2的地址1，将上次处理后寄存了1个周期的2，4，…，32存入RAM 1的地址2;第3 周期，将65，67，…，95 存入 RAM 1 的地址3，寄存了1 个周期的34，36，…，64存入RAM 2的地址2;依此类推，33个周期后可将信息比特全部存入RAM 1和RAM 2中，此时存储的比特顺序如图4所示。

图4 第1次处理后比特顺序

2)将RAM 1和RAM 2中的比特读出，再输入图3的计算单元，将处理后的比特存入RAM 3和RAM 4中。具体操作为:在第34周期，读出RAM 1和RAM 2地址1的数据输入图3模块，同时将处理后的1，5，…，61存入RAM 3的地址1;第35周期，读出RAM 1和RAM 2地址3的数据，将65，69，…，125存入RAM 4的地址1，寄存了1个周期的3，7，…，63存入RAM 3的地址2;依此类推，操作方式如步骤1)，此时读取RAM 1和RAM 2中的地址顺序为1，3，5，7，9，11，13，15，17，19，21，23，25，27，29，31，2，4，6，8，10，12，14，16，18，20，22，24，26，28，30，32。需要注意的是，每次应该同时读取2个RAM相同地址的信息比特，33个周期后可将信息比特全部存入RAM 3和RAM 4中，此时RAM 3和RAM 4中存储的比特顺序如图5所示(依旧为原始编号)。

图5 第2次迭代后比特顺序

3)如步骤2)，将RAM3和RAM4中的比特读出，再输入图3的计算单元，将处理后的比特存入RAM1和RAM2中，操作方式如上，此时读取RAM3和RAM4的地址顺序为1，3，5，7，9，11，13，15，2，4，6，8，10，12，14，16，17，19，21，23，25，27，29，31，18，20，22，24，26，28，30，32。

4)重复步骤2)和步骤3)进行迭代处理，以下要设置读存储器的地址顺序依次为:第4次迭代顺序为1，3，5，7，2，4，6，8，9，11，13，15，10，12，14，16，17，19，21，23，18，20，22，24，25，27，29，31，26，28，30，32;第 5 次迭代顺序为 1，3，2，4，5，7，6，8，9，11，10，12，13，15，14，16，17，19，18，20，21，23，22，24，25，27，26，28，29，31，30，32;第 6 次迭代顺序为1，2，3，4，5，6，7，8，9，10，11，12，13，14，15，16，17，18，19，20，21，22，23，24，25，26，27，28，29，30，31，32。

5)每次迭代过程需要33个周期，故经过6次迭代共198个周期后，此时信息比特已经完成R5的变换，可化简为64个W4信道的编码，而基于W4信道的编码模块比较简单，用简单的异或门即可实现，可以对存储器中各地址的信息比特进行并行操作，此处不作赘述。至此，编码完成。

4 结语

极化码的出现引起了巨大的影响，很多研究者都进行了相关的研究，本文提出了一种基于部分并行输入的编码器硬件结构。类似于LDPC等信道编码器可用DSP［6］或FPGA实现，本文提出的编码器也可在硬件平台上实现。作为一个新出现的技术，极化码还有很多的研究需要进行，特别是在译码上，找到一个合适可行并且易于硬件实现的译码算法十分必要。

:

［1］ARIKAN E.Channel polarization:a method for constru－cting capacityachieving codes for symmetric binary－input me－moryless channels［J］.IEEE Trans.Inform.Theory，2009，55(7):3051－3073.

［2］李斌，王学东.极化码原理及应用［J］.通信技术，2012，45(10):21－23.

［3］MARI R，TANAKA T.Performance and construction of polar codes on symmetric binary－input memoryless channels［C］//Proc.ISIT 2009.Seoul，Korea:IEEE Press，2009:1496－1500.

［4］ARIKAN E.Channel combining and splitting for cutoff rate improvement［J］.IEEE Trans.Inform.Theory，2006，52(2):628－639.

［5］ARIKAN E.Source polarization［C］//Proc.2010 IEEE International Symposium on Informantion Theory Proceedings(ISIT).Pasadena，CA，USA:IEEE Press，2010:899－903.

［6］于佳，董淑福，张健.LDPC码快速编码器的DSP设计与实现［J］.电视技术，2011，35(7):49－51.