说明书WPAN中全并行输入的循环左移准循环矩阵乘法器
技术领域
本发明涉及信道编码领域,特别涉及一种WPAN标准QC-LDPC近似下三角编码中全并行输入的循环左移准循环矩阵乘法器。
背景技术
低密度奇偶校验(Low-Density Parity-Check,LDPC)码是高效的信道编码技术之一,而准循环LDPC(Quasi-Cyclic LDPC,QC-LDPC)码是一种特殊的LDPC码。QC-LDPC码的生成矩阵G和校验矩阵H都是由循环矩阵构成的阵列,具有分段循环的特点,故被称为QC-LDPC码。循环矩阵的首行是末行循环右移1位的结果,其余各行都是其上一行循环右移1位的结果;循环矩阵的首列是末列循环下移1位的结果,其余各列都是其前一列循环下移1位的结果。因此,循环矩阵完全由其首行或首列来表征。通常,循环矩阵的首行或首列被称为它的生成多项式。
当采用近似下三角编码方法对QC-LDPC码进行编码时,通过行列交换,校验矩阵H变换成近似下三角形状HALT,它由6个子矩阵组成如下:
HALT=ABLCDE---(1)]]>
其中,L是下三角矩阵。HALT对应码字vALT=(s,p,q),矩阵A和C对应向量s,矩阵B和D对应一部分校验向量p,矩阵L和E则对应余下的校验向量q。计算部分校验向量p的方法如下:
p=s(C+EL-1A)Τ((D+EL-1B)-1)Τ (2)其中,上标-1和Τ分别表示对矩阵求逆和转置。令
m=s(C+EL-1A)Τ (3)
F=((D+EL-1B)-1)Τ (4)则向量m和矩阵F满足如下关系:
p=mF (5)
矩阵F是由如下u×u个b×b阶循环矩阵Fi,j(0≤i<u,0≤j<u)构成的准循环矩阵:
F的连续b行和b列分别被称为块行和块列。由式(6)可知,F有u块行和u块列。令循环矩阵Fi,j的首行fi,j或首列hi,j是其生成多项式。
令向量m=(e0,e1,…,eu×b-1),部分校验向量p=(d0,d1,…,du×b-1)。以b比特为一段,向量m和部分校验向量p均被等分为u段,即m=(m0,m1,…,mu-1)和p=(p0,p1,…,pu-1)。由式(5)可知,部分校验向量的第j段pj满足
pj=m0F0,j+m1F1,j+…+miFi,j+…+mu-1Fu-1,j (7)
其中,0≤i<u,0≤j<u。令是生成多项式hi,j循环下移n位的结果,其中,0≤n≤b。那么,式(7)中Pj的第k比特校验位dj×b+k可表示为
dj×b+k=m0h0,j↓(k)+m1h1,j↓(k)+...+mihi,j↓(k)+...+mu-1hu-1,j↓(k)---(8)]]>
其中,0≤k<b。
目前,全并行输入的准循环矩阵乘法器是基于u个移位寄存器加法器(Shift-Register-Adder,SRA)电路,如图1所示。生成多项式查找表L0~Lu-1分别预先存储准循环矩阵F的第0~u-1块行中的所有生成多项式,向量m=(e0,e1,…,eu×b-1)全并行送入该电路。以计算校验段pj(0≤j<u)为例。当第0个时钟周期到来时,移位寄存器R0~Ru-1分别从生成多项式查找表L0~Lu-1加载生成多项式h0,j~hu-1,j,并分别与向量段m0~mu-1进行向量乘,乘积的模2和是Pj的第0比特校验位dj×b。当第1个时钟周期到来时,移位寄存器R0~Ru-1分别循环右移1位,内容分别变为并分别与向量段m0~mu-1进行向量乘,乘积的模2和是Pj的第1比特校验位dj×b+1。上述右移-乘-加过程继续进行下去。当第b-1个时钟周期到来时,移位寄存器R0~Ru-1分别循环右移1位,内容分别变为并分别与向量段m0~mu-1进行向量乘,乘积的模2和是Pj的最后1比特校验位dj×b+b-1。使用图1所示的全并行输入乘法器,能在u×b个时钟周期内逐位输出部分校验向量p。该方案需要u×b个寄存器、u×b个二输入与门和u×b个二输入异或门,还需要u个u×b比特ROM存储循环矩阵的生成多项式。
WPAN标准采用了一种码率η=0.5的QC-LDPC码,b=21,u=2。
WPAN标准QC-LDPC近似下三角编码中全并行输入的准循环矩阵乘法器的现有解决方 案有两个缺点:一是需要42个寄存器,导致电路的功耗大、成本高;二是模2加法器有42个输入端,加法运算的延时长,会造成乘法器的工作频率低、吞吐量小。
发明内容
WPAN标准QC-LDPC近似下三角编码中准循环矩阵乘法器的现有实现方案存在功耗大、成本高、工作频率低、吞吐量小的缺点,针对这些技术问题,本发明提供了一种基于循环左移的全并行输入乘法器。
如图2所示,WPAN标准QC-LDPC近似下三角编码中全并行输入的循环左移准循环矩阵乘法器主要由4部分组成:生成多项式查找表、b位二进制乘法器、3位二进制加法器和移位寄存器。乘法过程分5步完成:第1步,全并行输入向量m;第2步,清零移位寄存器R;第3步,生成多项式查找表L0、L1分别输出准循环矩阵F第j(0≤j<2)块列中第0、1块行的生成多项式比特,这些生成多项式比特分别通过b位二进制乘法器M0、M1与向量段m0、m1进行标量乘,b位二进制乘法器M0、M1的乘积通过b个3位二进制加法器A0,A1,…,Ab-1与移位寄存器R的内容相加,3位二进制加法器A0,A1,…,Ab-1的和被循环左移1位后的结果存入移位寄存器R;第4步,重复第3步b次,此时,移位寄存器R存储的是校验段pj;第5步,以1为步长递增改变j的取值,重复第2~4步2次,移位寄存器R依次得到的是校验段p0、p1,它们构成了校验向量p=(p0,p1)。
本发明提供的全并行输入准循环矩阵乘法器结构简单,适用于WPAN标准中的QC-LDPC码,能在保持速度的条件下,减少寄存器和延时,降低功耗和成本,提高工作频率和吞吐量。
关于本发明的优势与方法可通过下面的发明详述及附图得到进一步的了解。
附图说明
图1是由u个移位寄存器加法器SRA电路构成的全并行输入准循环矩阵乘法器;
图2是一种基于循环左移的全并行输入准循环矩阵乘法器。
具体实施方式
下面结合附图对本发明的较佳实施例作详细阐述,以使本发明的优点和特征能更易于被本领域技术人员理解,从而对本发明的?;し段ё鞒龈宄魅返慕缍?。
令和分别是生成多项式fi,j循环右移n位和循环左移n位的结果,其中,0≤n≤b。那么,式(7)等号右边的第i项可展开为
miFi,j=ei×bfi,jr(0)+ei×b+1fi,jr(1)+...+ei×b+b-1fi,jr(b-1)---(9)]]>
令生成多项式fi,j=(fi,j,0,fi,j,1,…,fi,j,b-1),则Fi,j可视为单位矩阵循环右移版本的加权和,即
Fi,j=fi,j,0Ir(0)+fi,j,1Ir(1)+…+fi,j,b-1Ir(b-1) (10)
那么,式(7)等号右边的第i项可展开为
miFi,j=mi(fi,j,0Ir(0)+fi,j,1Ir(1)+...+fi,j,b-1Ir(b-1))=fi,j,0miIr(0)+fi,j,1miIr(1)+...+fi,j,b-1miIr(b-1)=fi,j,0mir(0)+fi,j,1mir(1)+...+fi,j,b-1mir(b-1)---(11)]]>
既然将mi循环右移n位等价于将它循环左移b-n位,即那么式(11)可改写为
miFi,j=fi,j,0mi1(b)+fi,j,1mi1(b-1)+...+fi,j,b-1mi,j1(1)=(fi,j,0mi)1(b)+(fi,j,1mi)1(b-1)+...+(fi,j,b-1mi)1(1)=(0+fi,j,0mi)1(b)+(fi,j,1mi)1(b-1)+...+(fi,j,b-1mi)1(1)=((0+fi,j,0mi)1(1)+fi,j,1mi)1(b-1)+...+(fi,j,b-1mi)1(1)=(...((0+fi,j,0mi)1(1)+fi,j,1mi)1(1)+...+fi,j,b-1mi)1(1)---(12)]]>
将式(7)代入式(2),整理可得
pi=(...((0+Σi=0u-1fi,j,0mi)1(1)+Σi=0u-1fi,j,1mi)1(1)+...+Σi=0u-1fi,j,b-1mi)1(1)---(13)]]>
式(13)是一个乘-加-左移-存储的过程,可推导出一种基于循环左移的全并行输入准循环矩阵乘法器。图2是其功能框图,由生成多项式查找表、b位二进制乘法器、3位二进制加法器和移位寄存器四种功能??樽槌?。生成多项式查找表L0、L1分别预存准循环矩阵F第0、1块行中的所有循环矩阵生成多项式。生成多项式查找表L0、L1输出的生成多项式比特分别与向量段m0、m1进行标量乘,这2个标量乘法分别通过b位二进制乘法器M0、M1完成。b位二进制乘法器M0、M1的乘积与移位寄存器R的内容相加,该加法通过b个3位二进制加法器A0,A1,…,Ab-1完成。3位二进制加法器A0,A1,…,Ab-1的和被循环左移1位后的结果存入移位寄存器R。
生成多项式查找表L0、L1存储准循环矩阵F中的循环矩阵生成多项式。L0、L1分别存储F的第0、1块行中的所有生成多项式,对于任一块行,依次存储第0、1块列对应的生成多项式。
本发明提供了一种基于循环左移的全并行输入准循环矩阵乘法,适用于WPAN标准中的QC-LDPC码,其乘法步骤描述如下:
第1步,全并行输入向量m;
第2步,清零移位寄存器R;
第3步,生成多项式查找表L0、L1分别输出准循环矩阵F第j(0≤j<2)块列中第0、1块行的生成多项式比特,这些生成多项式比特分别通过b位二进制乘法器M0、M1与向量段m0、m1进行标量乘,b位二进制乘法器M0、M1的乘积通过b个3位二进制加法器A0,A1,…,Ab-1与移位寄存器R的内容相加,3位二进制加法器A0,A1,…,Ab-1的和被循环左移1位后的结果存入移位寄存器R;
第4步,重复第3步b次,此时,移位寄存器R存储的是校验段pj;
第5步,以1为步长递增改变j的取值,重复第2~4步2次,移位寄存器R依次得到的是校验段p0、p1,它们构成了校验向量p=(p0,p1)。
从以上步骤不难看出,整个计算过程共需u×b个时钟周期,与现有的基于2个SRA电路的全并行输入乘法方案完全相同。
WPAN标准中准循环矩阵乘法器的现有解决方案需要42个寄存器、42个二输入与门和41个二输入异或门,而本发明需要21个寄存器、42个二输入与门和42个二输入异或门。两种乘法方案耗费相同数量的与门,虽然本发明比现有解决方案多用了1个二输入异或门,但本发明节约了大量的寄存器,仅为现有解决方案的1/2。
现有解决方案需要1个42位模2加法器,而本发明将模2加法平均分配给了b个3位模2加法器??杉?,本发明的加法器延时远小于现有解决方案。
综上可见,对于WPAN标准QC-LDPC近似下三角编码中的全并行输入准循环矩阵乘法器,与现有解决方案相比,本发明保持了相同的速度,节约了大量的寄存器,极大地缩短了逻辑电路的延时,具有功耗小、成本低、工作频率高、吞吐量大等优点。
以上所述,仅为本发明的具体实施方式之一,但本发明的?;し段Р⒉痪窒抻诖?,任何熟悉本领域的技术人员在本发明所揭露的技术范围内,可不经过创造性劳动想到的变化或替换,都应涵盖在本发明的?;し段е?。因此,本发明的?;し段вΩ靡匀ɡ笫樗薅ǖ谋;し段??! ∧谌堇醋宰ɡ鴚ww.www.4mum.com.cn转载请标明出处