法律状态公告日
法律状态信息
法律状态
2016-02-03
未缴年费专利权终止 IPC(主分类):H04L1/00 授权公告日:20081008 终止日期:20141208 申请日:20051208
专利权的终止
2013-10-30
专利权的转移 IPC(主分类):H04L1/00 变更前: 变更后: 登记生效日:20130930 申请日:20051208
专利申请权、专利权的转移
2008-10-08
授权
授权
2006-07-19
实质审查的生效
实质审查的生效
2006-05-24
公开
公开
技术领域
本发明属于通信领域,涉及编码技术,具体地说是一种基于预编码的并行卷积低密度校验码LDPC的快速编码方法,适用于快速数据传输的有效编码。
背景技术
在现代数字通信系统中,为保证各种数据能够可靠、有效地传输,往往要利用纠错编码技术。近年来,随着无线数字通信的发展及各种高速率数据业务的出现,研究并利用纠错编码技术就显得越来越重要。
理论研究表明:低密度校验码LDPC长码的性能超过Turbo码,已接近香农限,同时具有线性译码复杂度,适用于高速数据传输。美国科学家Gallager在上世纪六十年代初发明了LDPC码,由于受到当时硬件水平的限制并没有得到应用。后来,随着大规模集成电路技术的发展,LDPC码从理论研究逐渐进入了实用发展的阶段。
LDPC码是一类线性分组码,由其校验矩阵H中只有极少数为非零元素的特点而命名。图1给出码长为8,行重为2,列重为4的(8,2,4)LDPC码的校验矩阵和因子图。图1.a为校验矩阵,图1.b为校验矩阵对应的因子图,校验矩阵中元素1的位置对应于因子图中变量节点和校验节点的连接关系。在因子图中连接变量节点和校验节点的闭合路径构成环,在一个环中,边的数目称为环长。图1中虚线部分表示的环长为4,也就是图1(8,2,4)LDPC码的最小环长。
目前,LDPC码的主要研究内容是如何设计随机性强、最小环长相对较大且易于实现编码的LDPC编码方法。
美国学者Shannon的信道编码定理说明:随机性在信道编码中有其重要的作用,而在和积译码算法的迭代过程中,由于环路造成的迭代信息的非独立性,使译码无法达到最优化,所以随机性和环长二者是影响中短码长LDPC码的主要因素。最近,瑞典学者HU Xiao-Yu等人提出了一种用PEG算法搜索出来的LDPC码,简称为PEG码。虽然中短码长的PEG码的性能优于随机构造的LDPC码,但PEG算法并没有考虑LDPC码的快速编码实现问题。
在现有LDPC码的编码过程中,如果直接采用信息比特与生成矩阵相乘的方法,则编码复杂度为o(n2),这种复杂度在中长码时,会造成编码的很大时延。目前常用的解决方法是采用具有下三角结构的稀疏校验矩阵直接编码,其复杂度为o(n)。为进一步避免校验矩阵结构的限制带来的性能损失,美国学者Richardson和Urbanke等人通过行列交换将校验矩阵转化为下三角结构进行编码,其复杂度仍为n+δo(n2),其中δ<<1。
可见,上述编码方法均存在复杂度高,编码时延大的问题。
发明的内容
本发明的技术方案是提供一种基于预编码的并行卷积LDPC码的编码器及其快速编码方法,以解决上述编码方法复杂度高,编码时延大的问题。
本发明的技术方案是这样实现的:
本发明的技术思路是设计并行卷积LDPC码编码器,由该编码器进行并行卷积LDPC码的编码,并获得所述LDPC码的校验矩阵H。
本发明的并行卷积LDPC码编码器包括:信息分组单元、信息预编码单元、卷积编码单元和信息重组单元,其中:
信息分组单元,用于实现信息流串并转换,即将一个信息流变换成M个并行子信息流,每个子信息流的长度为L,M>1,L>1;
信息预编码单元,用于实现并行卷积LDPC码的第一校验矩阵Hπ,即用于完成基于LDPC码第一校验矩阵Hπ的模2求和。该信息预编码单元包括存储器、交织器和模2加法器,其中存储器的个数等于并行子信息流的个数,即等于M,每个存储器对应个随机交织器,模2加法器的个数等于R是并行卷积LDPC码的码率;
卷积编码单元,用于实现并行卷积LDPC码的第二校验矩阵H′,即用于完成基于LDPC码第二校验矩阵H′的模2求和。该单元包括N个卷积编码器,
信息重组单元,用于完成信息流和编码器产生的校验比特流的并串转换。
利用上述编码器实现并行卷积LDPC码的编码方法,按如下过程进行:
首先,通过信息分组单元将信息比特进行分组,得到M个并行的子信息流,每个子信息流对应存入一个存储器中,且每个子信息流中包含L个比特,M>1,L>1;
然后,通过信息预编码单元将每组存储器中的信息流经过不同的随机交织器交织后,分别送入不同的模2加法器进行预编码,并由该信息预编码单元实现并行卷积LDPC码的第一校验矩阵Hπ;
其次,通过卷积编码单元将每个模2加法器的输出比特分别送入对应的卷积码编码器进行编码,并由该卷积编码单元实现并行卷积LDPC码的第二校验矩阵H′;
最后,通过信息重组单元将N个卷积码编码器输出的校验比特与存储器中的信息比特重组生成一个码率为R=M/(M+N)、码长为(M+N)L的并行卷积LDPC码字,即用[(M+N)L,M,M+N]表示。
上述编码方法,其中由信息预编码单元实现并行卷积LDPC码的第一校验矩阵Hπ,按如下过程进行:
首先,根据存储器的个数M和并行卷积LDPC码的码率R,确定每组存储器中采用的随机交织器的个数为:
然后,采用随机方式或伪随机序列生成交织器,并对第一校验矩阵Hπ进行优化;
最后,将每个存储器的第一个交织器的输出序列送入第一个模2加法器1,将每个存储器的第二个交织器的输出序列送入第二个模2加法器2,依次类推,直至将每个存储器的第N个交织器的输出序列送入第N个模2加法器N,最后得到第一校验矩阵Hπ为
式中,πi,j表示第i个存储器中的第j个交织器,Iπi,j表示由交织器πi,j确定的L×L维单位交织阵,i=1,2,…,M,j=1,2,…,N,
上述编码方法,其中由卷积编码单元实现并行卷积LDPC码的第二校验矩阵H′的过程如下:
首先,采用递归形式确定每个卷积码的编码形式,每个卷积码的码率为1;
然后,确定卷积编码器的递归多项式,即选用1/(1+D+D3)或1/(1+D+D4)作为递归多项式,D表示第一个移位寄存器的输出,D3表示第三个移位寄存器的输出,D4表示第四个移位寄存器的输出,最终得到第二校验矩阵H′为:
式中,HC由其中一个卷积编码器的递归多项式确定。
上述编码方法,其中由信息预编码单元实现并行卷积LDPC码第一校验矩阵Hπ的过程中,利用伪随机序列生成交织器对第一校验矩阵Hπ进行优化,按如下过程进行:
(1)根据存储器长度L取值确定迦罗华域GF(2)上的一个扩域GF(2n),满足L=2n-2:
(2)选择GF(2n)上的一个本原多项式p(x),构成除法电路,若选定一本原元α,给该电路设初值α0=(100,…,00),电路右移一位相当于序列乘一次α,依次向右移位可得到扩域GF(2n)上的所有元素α,α2,…,α2n-1,α0;
(3)选择扩域GF(2n)上的M×N个本原元
(4)构造2n-1阶单位交织阵I′πi,j,该矩阵每行和每列只有一个1,矩阵I′πi,j中的第t行第j列的元素用(t,s)表示,则(t,s)位置上元素取值方法为:选
(5)将上述I′πi,j中的第0行第0列删除得到Iπi,j,利用所有Iπi,j即可得到所有可供选择的第一校验矩阵;
(6)从满足条件的所有Hπ中再进行搜索,得到最小环长比较大的第一校验矩阵Hπ。
上述编码方法,其中由信息预编码单元决定并行卷积LDPC码的第一校验矩阵Hπ的过程中,利用随机方法生成交织器对第一校验矩阵Hπ进行优化的过程为:
(1)任意产生M+N-1个长为L的随机交织器,随机置入下式中的第一行和第一列中
其中,πi,j表示第i个存储器中的第j个交织器,i=1,2,…,M,j=1,2,…,N,
(2)搜索确定③式中的其余M×N-(M+N-1)个随机交织器,得到具有较大的最小环长的第一校验矩阵Hπ。
上述编码方法,将其第一校验矩阵Hπ和第二校验矩阵H′,通过级连则可形成并行卷积LDPC码的校验矩阵H,即
式中,Hc由其中一个卷积编码器的递归多项式确定,πi,j表示第i个存储器中的第j个交织器,Iπi,j表示由交织器πi,j确定的L×L维单位交织阵,0表示L×L维的全零矩阵,i=1,2,…,M,j=1,2,…,N,M是存储器的个数,
本发明由于采用卷积编码器实现并行卷积LDPC码的编码,因而减小了编码复杂度,可有效增加编码速度;同时由于本发明采用交织器对所述LDPC码校验矩阵进行优化,使码的随机性有了很大提高。
附图说明
图1是现有(8,2,4)LDPC码的校验矩阵及因子图
图2是本发明基于预编码的规则并行卷积LDPC码编码器图
图3是本发明基于预编码的(756,3,6)规则并行卷积LDPC码编码器图
图4是本发明7阶最大线性移存器电路图
图5是本发明基于预编码的(3060,3,6)规则并行卷积LDPC码编码器图
图6是本发明并行卷积LDPC码的性能曲线图
具体实施方式
以下参照附图对本发明作进一步详细描述。
参照图2,本发明的编码器包括信息分组、信息预编码、卷积编码和信息重组四个单元,其中:
信息分组单元,用于实现信息流串并转换,即将一个信息流变换成M个并行子信息流,每个子信息流的长度为L,得到的所有M个子信息流分别送入对应的存储器,以进行信息预编码单元的预编码运算;
信息预编码单元,用于实现第一校验矩阵Hπ,该信息预编码单元包括存储器、交织器和模2加法器,其中存储器的个数等于并行子信息流的个数M,每个存储器对应个随机交织器,模2加法器的个数等于R是并行卷积LDPC码的码率。存储器1中的第一个交织器用π1,1表示,存储器1中的第2个交织器用π1,2表示,依此类推,存储器1的第N个交织器用π1,N表示;存储器2中的第一个交织器用π2,1表示,存储器2中的第二个交织器用π2,2表示,依此类推,存储器2中的第N个交织器用π2,N表示,
卷积编码单元,包括N个卷积编码器,用于实现第二校验矩阵H′,即完成对LDPC码第二校验矩阵H′的模2求和。该单元根据收到的预编码单元输出比特进行卷积编码:卷积编码器1接收第一个模2加法器1的输出,并进行卷积编码,卷积编码器2接收第二个模2加法器2的输出,并进行卷积编码,依此类推,卷积编码器N接收第N个模2加法器N的输出,并进行卷积编码。
信息重组单元,用于完成信息流和卷积编码器产生的校验比特流的并串转换,从而生成并行卷积LDPC码的一个码字。
实施例一
参照图3,本实施例是(756,3,6)并行卷积LDPC码的编码器设计及编码过程,并通过伪随机方式设计交织器来优化第一校验矩阵Hπ。
1.编码器的结构与功能
该编码器包括信息分组单元、信息预编码单元、卷积编码单元和信息重组单元,各单元的构成与作用如下:
(1)信息分组单元,用于实现信息流串并转换,即将一个信息流变换成M=3个并行子信息流,每个子信息流长度L=126,得到的所有3个子信息流分别送入对应的存储器,以进行信息预编码单元的预编码运算。
(2)信息预编码单元,用于实现第一校验矩阵Hπ,该信息预编码单元包括存储器、交织器和模2加法器三种器件,其中存储器的个数等于并行子信息流的个数,即等于3,每个存储器对应3个随机交织器,模2加法器的个数等于3。存储器1中的第一个交织器用π1,1表示,存储器1中的第2个交织器用π1,2,存储器1的第3个交织器用π1,3表示,存储器2中的第一个交织器用π2,1表示,存储器2中的第二个交织器用π2,2表示,存储器2中的第3个交织器用π2,3表示,存储器3中的第一个交织器用π3,1表示,存储器2中的第二个交织器用π3,2表示,存储器3中的第3个交织器用π3,3表示。交织器的输出序列送入不同的模2加法器进行求和,即每个存储器中的第一个交织器的输出序列送入第一个模2加法器1进行求和,每个存储器中的第2个交织器的输出序列送入第二个模2加法器2进行求和,每个存储器中的第3个交织器的输出序列送入第3个模2加法器3进行求和,所有模2加法器的输出将送入卷积编码单元进行卷积编码。
(3)卷积编码单元,该单元包括三个卷积编码器,用于实现第二校验矩阵H′,即完成对LDPC码第二校验矩阵H′的模2求和。该单元根据收到的预编码单元输出比特进行卷积编码:卷积编码器1接收第一个模2加法器1的输出,并进行卷积编码,卷积编码器2接收第二个模2加法器2的输出,并进行卷积编码,卷积编码器3接收第3个模2加法器3的输出,并进行卷积编码。其中,每一个卷积编码器包括一个模2加法器和四个移位寄存器单元D1,D2,D3和D4,该四个移位寄存器单元的初始值均为零,利用每个卷积编码器进行编码过程是:该卷积编码器中的模2加法器对信息预编码单元中对应模2加法器的输出以及移位寄存器单元D1和D4的输出进行模2求和,并将移位寄存器D3的存储值送入移位寄存器D4,将移位寄存器D2的存储值送入移位寄存器D3,将移位寄存器D1的存储值送入移位寄存器D2,将上述模2求和得到的结果存入移位寄存器D1,最后将每个卷积编码器中的模2求和的结果送入信息重组单元。
(4)信息重组单元,将信息流和卷积编码器产生的校验比特流进行并串转换,从而生成(756,3,6)并行卷积LDPC码的一个码字。
2.利用编码器进行编码的过程
(1)通过信息分组单元将信息比特进行分组,得到3个并行的子信息流,每个子信息流对应存入一个存储器中,且每个子信息流中包含126个比特;
(2)通过信息预编码单元将每组存储器中的信息流经过3个不同的随机交织器交织,并将每个存储器的第一个交织器的输出序列送入第一个模2加法器1进行求和,将每个存储器的第二个交织器的输出序列送入第二个模2加法器2进行求和,将每个存储器的第三个交织器的输出序列送入第三个模2加法器3进行求和,并按如下过程实现LDPC码的第一校验矩阵Hπ:
1)根据存储器的个数M=3和并行卷积LDPC码的码率R=1/2,确定每组存储器中采用的随机交织器的个数为
2)采用伪随机序列生成交织器,对第一校验矩阵Hπ进一步进行优化;
3)交织器的输出序列送入不同的模2加法器进行求和,即将每个存储器的第一个交织器的输出序列送入第一个模2加法器1进行求和,将每个存储器的第二个交织器的输出序列送入第二个模2加法器2进行求和,将每个存储器的第三个交织器的输出序列送入第3个模2加法器3进行求和,最后得到第一校验矩阵Hπ为:
对上述产生的第一校验矩阵Hπ可通过伪随机方式进一步优化:
①根据存储器长度L=126确定迦罗华GF(2)上的一个扩域GF(27),满足L=27-2=126;
②选择扩域GF(27)上的一个本原多项式p(x)=x7+x3+1,构成除法电路,如图4所示。利用图4电路可产生GF(27)上所有元素,选定一本原元α,给电路设初值α0=(1000000),并将电路右移一位,即相当于序列乘一次α,依次向右移位可得到扩域GF(27)上的所有元素α,α2,…,α126,α0,类似地,选定另一个本原元β=α5,给电路设初值β0=(1000000),电路右移一位相当于序列乘一次β,依次向右移位可得到扩域GF(27)上的所有元素β,β2,β126,β0,表1给出了分别以α和β=α5为本原元产生的GF(27)上的所有元素;
③选择扩域GF(27)上的9个本原元
④造27-1阶单位交织阵I′πi,j,该矩阵每行和每列只有一个1,矩阵I′πi,j中的第t行第s列的元素用(t,s)表示,该(t,s)位置上元素取值为:选
⑤上述I′πi,j中的第0行第0列删除得到I′πi,j,利用所有9个I′πi,j即可得到实施例1中最小环长为12的第一校验矩阵Hπ。
表1 以p(x))=x7+x3+1为模的GF(27)的元素表
(3)通过卷积编码单元将每个模2加法器的输出比特分别送入对应的卷积码编码器进行编码,并按如下过程实现LDPC码的第二校验矩阵H′:
1)确定卷积编码单元中采用的卷积编码形式为递归卷积器;
2)采用递归多项式为1/(1+D+D4)的卷积编码器,该递归多项式表示卷积编码器中含有四个移位寄存器,D表示第一个移位寄存器的输出,D4表示第四个移位寄存器的输出,最后,得到第二校验矩阵H′为:
其中,Hc的表达式为
将上述第一校验矩阵Hπ与第二校验矩阵H′级连就可得到本发明并行卷积LDPC码的校验矩阵H。
(4)通过信息重组单元将3个卷积码编码器输出的校验比特与存储器中的信息比特重组生成一个码率为R=1/2、码长为756的LDPC码字。
实施例二
参照图5,本实施例是(3060,3,6)并行卷积LDPC码的编码器设计及编码过程,并通过随机方式设计交织器来优化第一校验矩阵Hπ。
1.编码器的结构与功能
该编码器包括信息分组单元、信息预编码单元、卷积编码单元和信息重组单元,各单元的构成与作用如下:
(1)信息分组单元,将一个信息流变换成M=3个并行子信息流,每个子信息流长度L=510。
(2)信息预编码单元,包括存储器、交织器和模2加法器,其中存储器的个数等于并行子信息流的个数,即等于3,每个存储器对应3个随机交织器,模2加法器的个数等于3。存储器1中的第一个交织器用π1,1表示,存储器1中的第2个交织器用π1,2,存储器1的第3个交织器用π1,3表示,存储器2中的第一个交织器用π2,1表示,存储器2中的第二个交织器用π2,2表示,存储器2中的第3个交织器用π2,3表示,存储器3中的第一个交织器用π3,1表示,存储器2中的第二个交织器用π3,2表示,存储器3中的第3个交织器用π3,3表示。交织器的输出序列送入不同的模2加法器进行求和,即每个存储器中的第一个交织器的输出序列送入第一个模2加法器1进行求和,每个存储器中的第2个交织器的输出序列送入第二个模2加法器2进行求和,每个存储器中的第3个交织器的输出序列送入第3个模2加法器3进行求和,每个模2加法器的输出将送入卷积编码单元进行卷积编码。
(3)卷积编码单元,该单元包括三个卷积编码器,用于实现第二校验矩阵H′,即完成对LDPC码第二校验矩阵H′的模2求和。该单元根据收到的预编码单元输出比特进行卷积编码:卷积编码器1接收第一个模2加法器1的输出,并进行卷积编码,卷积编码器2接收第二个模2加法器2的输出,并进行卷积编码,卷积编码器3接收第3个模2加法器3的输出,并进行卷积编码。其中,每一个卷积编码器包括一个模2加法器和三个移位寄存器单元D1,D2和D3,该三个移位寄存器单元的初始值均为零,利用每个卷积编码器进行编码过程是:该卷积编码器中的模2加法器对信息预编码单元中对应模2加法器的输出以及移位寄存器单元D1和D3的输出进行模2求和,并将移位寄存器D2的存储值送入移位寄存器D3,将移位寄存器D1的存储值送入移位寄存器D2,将上述模2求和得到的结果存入移位寄存器D1,最后将每个卷积编码器中的模2求和的结果送入信息重组单元。
(4)信息重组单元,用于完成信息流和卷积编码器产生的校验比特流的并串转换,从而生成(3060,3,6)并行卷积LDPC码的一个码字。
2.利用编码器进行编码的过程
(1)通过信息分组单元将信息比特进行分组,得到M=3个并行的子信息流,每个子信息流对应存入一个存储器中,且每个子信息流中包含L=510个比特。
(2)通过信息预编码单元将每组存储器中的信息流经过3个不同的随机交织器交织,并将每个存储器中的第一个交织器的输出序列送入第一个模2加法器1进行求和,将每个存储器中的第二个交织器的输出序列送入第二个模2加法器2进行求和,将每个存储器中的第三个交织器的输出序列送入第三个模2加法器2进行求和,并按如下过程实现并行卷积LDPC码的第一校验矩阵Hπ:
1)根据存储器的个数M=3和并行卷积LDPC码的码率R=1/2,确定每组存储器中采用的随机交织器的个数为
2)采用随机方式生成交织器,对第一校验矩阵Hπ进一步进行优化;
3)将每个存储器的第一个交织器的输出序列送入第一个模2加法器1,将每个存储器的第二个交织器的输出序列送入第二个模2加法器2,将每个存储器的第三个交织器的输出序列送入第3个模2加法器3,最后得到第一校验矩阵Hπ为:
对上述产生的第一校验矩阵Hπ可通过随机方式进一步优化:
①任意产生5个长为510的随机交织器,随机置入下式中的第一行和第一列,即π1,1、π1,2、π1,3、π2,1和π3,1;
②通过搜索方法确定⑥式中的其余4个随机交织器,即π2,2,π2,3π3,2和π3,3,得到具有较大最小环长的第一校验矩阵Hπ。
(3)通过卷积编码单元将每个模2加法器的输出比特分别送入对应的卷积码编码器进行编码,并按如下过程实现并行卷积LDPC码的第二校验矩阵H′:
1)确定卷积编码单元中采用的卷积编码形式为递归卷积器;
2)采用递归多项式为1/(1+D+D3)的卷积编码器,该递归多项式表示卷积编码器中含有三个移位寄存器,D表示第一个移位寄存器的输出,D3表示第四个移位寄存器的输出,最后,得到第二校验矩阵H′为:
其中,Hc的表达式为
将第一校验矩阵Hπ与第二校验矩阵H′级连就可得到本发明并行卷积LDPC码的校验矩阵H。
(4)通过信息重组单元将3个卷积码编码器输出的校验比特与存储器中的信息比特重组生成一个码率为R=1/2、码长为3060的并行卷积LDPC码字。
本发明设计的(756,3,6)和(3060,3,6)两个并行卷积LDPC码的性能曲线如图6所示,同时图6给出了利用PEG方法构造的LDPC码的性能曲线。图6中左边两条曲线对应的是码长为3060的LDPC码的性能曲线,右侧的两条曲线对应的是码长为756的LDPC码的性能曲线。由图6可得到以下结论:
(1)当码长较短且误码率为10-5时,本发明设计的并行卷积LDPC码的性能比采用PEG方法构造的LDPC码有约0.3dB的损失,这主要是由于PEG方法构造的LDPC码的突出特点消除了小环的影响;
(2)随着码长的增加,LDPC码受环的影响也逐渐降低,因而本发明所设计的码长为3060的并行卷积LDPC码的性能与采用PEG方法构造的LDPC码的性能几乎相当。
机译: 复合码并行并置位卷积码的编码方法,编码器和译码器,编码器和译码器系统
机译: 复合码并行并置位卷积码的编码方法,编码器和译码器,编码器和译码器系统
机译: 复合码并行并置位卷积码的编码方法,编码器和译码器,编码器和译码器系统