公开/公告号CN101571795A
专利类型发明专利
公开/公告日2009-11-04
原文格式PDF
申请/专利权人 深圳华为通信技术有限公司;
申请/专利号CN200910086802.8
发明设计人 张玉伦;
申请日2009-06-05
分类号G06F7/38(20060101);G06F7/544(20060101);G06F7/57(20060101);H03K19/00(20060101);
代理机构11205 北京同立钧成知识产权代理有限公司;
代理人刘芳
地址 518129 广东省深圳市龙岗区坂田华为基地B区2号楼
入库时间 2023-12-17 22:53:02
法律状态公告日
法律状态信息
法律状态
2020-05-22
未缴年费专利权终止 IPC(主分类):G06F7/38 授权公告日:20110209 终止日期:20190605 申请日:20090605
专利权的终止
2019-01-04
专利权的转移 IPC(主分类):G06F7/38 登记生效日:20181218 变更前: 变更后: 申请日:20090605
专利申请权、专利权的转移
2019-01-04
专利权人的姓名或者名称、地址的变更 IPC(主分类):G06F7/38 变更前: 变更后: 申请日:20090605
专利权人的姓名或者名称、地址的变更
2011-02-09
授权
授权
2009-12-30
实质审查的生效
实质审查的生效
2009-11-04
公开
公开
查看全部
技术领域
本发明实施例涉及信号处理技术领域,尤其涉及一种集成电路和集成电路解方程的方法。
背景技术
数字通信系统需要进行大量的数字信号处理,方程求解是数字通信系统中一种常见的信号处理任务。方程求解的信号处理方法有多种,例如乔里斯基(Cholesky)求解的方法:矩阵构造成正定对称矩阵,然后采用Cholesky分解法,将该正定对称矩阵分解为两个三角阵的乘积后,对构造的两个新方程进行求解。
现有技术中采用数字信号处理器(Digital Signal Processor;以下简称:DSP)处理求解方程的信号。DSP是一种通用的数字信号处理器,包括预读单元(Prefetch Uint;以下简称:PFU)、指令时序单元(InstructionSequencing Unit;以下简称:ISU)、地址寄存器文件(Address Register File;以下简称:ARF)、操作数寄存器文件(Operand Register File;以下简称:ORF)、控制寄存器文件(Control Register File;以下简称:CRF)、流水线控制单元(Pipeline Control Unit;以下简称:PIP)、存储电路子系统(Memory Subsystem;以下简称:MSS)和乘法累加单元(MultiplierAccumulator Unit;以下简称:MAU)等多个组成部分。采用DSP进行解方程运算时,需要运行编写的解方程的程序进行解方程,各个单元配合求解Cholesky等方程。
发明人在实现本发明的过程中发现现有技术中至少存在如下问题:
由于DSP一般需要授权费用,采用DSP求解方程的成本较高;由于DSP并非专用于解方程的处理器,相对于专用集成电路芯片,实现DSP的芯片面积较大;每一种DSP的运算能力都有上限,不能根据实际解方程的需求定义运算能力。
发明内容
本发明实施例提供一种集成电路和集成电路解方程的方法,用以解决现有技术中采用DSP解方程存在的芯片面积大、成本高和运算能力受限等缺陷,以减小求解方程所需的芯片的面积,降低解方程的成本,并可以根据解方程需求设计运算能力。
本发明实施例提供一种集成电路,用于求解线性方程G=RH,其中G为常数向量、R为系数矩阵、H为待求解向量,包括:乘法电路、加法电路、开方电路、除法电路、存储器和控制单元;
所述乘法电路、所述加法电路、所述开方电路和所述除法电路依次串联,所述加法电路与所述除法电路连接,所述除法电路与所述存储器连接,所述存储器与所述乘法电路连接;
所述控制单元用于当所述系数矩阵为正定对称的矩阵时,控制所述乘法电路、所述加法电路、所述开方电路、所述除法电路和所述存储器将正定对称的系数矩阵分解为三角矩阵与所述三角矩阵的转置矩阵的乘积;
所述控制单元还用于控制所述乘法电路、所述加法电路、所述除法电路和所述存储器,根据所述三角矩阵和所述常数向量计算出中间向量后、根据所述中间向量和所述三角矩阵的转置矩阵计算所述方程中的待求解向量。
本发明实施例还提供一种集成电路解方程的方法,应用于求解方程G=RH,其中G为常数向量、R为系数矩阵、H为待求解向量,包括:
如果所述系数矩阵为正定对称的矩阵,控制单元控制乘法电路、加法电路、开方电路、除法电路和存储器,将所述系数矩阵分解为三角矩阵与所述三角矩阵的转置矩阵的乘积;
所述控制单元控制所述乘法电路、所述加法电路、所述除法电路和所述存储器,根据所述三角矩阵和所述常数向量计算出中间向量后,根据所述中间向量和所述三角矩阵的转置矩阵计算出所述方程中的待求解向量。
本发明实施例提供了一种集成电路和集成电路解方程的方法,由乘法电路、加法电路、开方电路、除法电路和存储器组成的集成电路,在控制单元的控制下,将方程中正定对称的系数矩阵分解为三角矩阵与该三角矩阵的转置矩阵的乘积;然后根据三角矩阵和常数向量计算出中间向量后,根据中间向量和该三角矩阵的转置矩阵计算待求解向量;减小了求解方程所需的芯片的面积,降低了解方程的成本,并可以根据解方程的需求灵活设计集成电路的运算能力。
附图说明
图1为本发明集成电路第一实施例的示意图;
图2为采用cholesky分解进行解线性方程组的状态机的时序图;
图3为本发明集成电路第二实施例的示意图;
图4为本发明集成电路解方程的方法第一实施例的流程图;
图5为本发明集成电路解方程的方法第二实施例的流程图;
图6为本发明集成电路解方程的方法第三实施例的流程图。
具体实施方式
下面结合附图和具体实施例进一步说明本发明实施例的技术方案。
在信号处理时,很多情况下(例如:采用滤波器进行滤波)需要求解线性方程组。先介绍一种求解线性方程组的方法。求解线性方程组时,将该线性方程组构造成矩阵方程的形式,通过矩阵变换解方程。以方程(1)为例进行说明。
G=RH (1)
在方程(1)中,G为常数向量、R为系数矩阵、H为待求解向量。
假设系数矩阵R为正定对称矩阵,此时可以采用乔里斯基(Cholesky)分解的方法解方程。首先将R分解为两个三角矩阵的乘积,如公式(2):
R=LLT (2)
在方程(2)中,L为三角矩阵,LT为L的转置矩阵。将公式(2)代入方程(1)可以得到方程(3):
G=RH=LLTH=L(LTH)=LW (3)
在方程(3)中W为假设的中间向量,根据方程(3)可以求出中间向量W=L-1G的值,同时由方程(3)可知,W满足方程(4):
W=LTH (4)
W的值解出后,解方程(4)就可以得到待求解向量H的值。
由于不是所有的线性方程组构造成的矩阵方程的系数矩阵都是正定对称矩阵,当方程中待求解向量的系数矩阵为非正定对称矩阵时,采用Cholesky分解的方法求解该方程之前,需要对该方程进行正定变换,以方程(5)为例。
D=ZH (5)
在方程(5)中,D为常数向量,Z为系数矩阵,系数矩阵Z为非正定对称的矩阵、H为待求解向量。由于Z为非正定对称矩阵,不能直接对该矩阵进行Cholesky分解,将方程(5)转换成方程(6):
ZTD=ZTZH (6)
在方程(6)中ZT为Z的转置矩阵,根据正定矩阵的性质可知:ZTZ为正定对称矩阵,此时可以假设ZTZ为方程(1)中的正定对称矩阵R,ZTD为方程(1)中的常数向量G,根据公式(2)可以得到公式(7),根据公式(3)和方程(6)可以得到方程(8)。
ZTZ=R=LLT (7)
ZTD=ZTZH=RH=LLTH=L(LTH)=LW (8)
在方程(8)中,W也是中间向量,此时解方程(8)可以求出W的值,然后再解方程(4)就可以得到待求解向量H的值。
综上所述,采用Cholesky分解求解线性方程组的方法为:先将待解方程的系数矩阵构造为正定对称的矩阵;再将正定对称的系数矩阵分解为一个三角矩阵及其转置的乘积;然后解方程求出中间向量的值;最后解方程求出待求解向量的值。
在Cholesky分解过程中,将正定对称的系数矩阵R的分解为一个三角矩阵及其转置的乘积的方法具体如下:
假设三角矩阵L为下三角矩阵,将公式(2)展开,可以得到以下公式(21):
由公式(21)可知:正定对称的系数矩阵R第一行的对角线元素为三角矩阵L第一行与L的转置矩阵LT第一列的乘积,即R[0][0]=L[0][0]×L[0][0],其中n为正整数,表示矩阵R、L都是n×n阶的矩阵。同理矩阵R的第i行的对角线元素为L第i行与LT第i列的乘积,由于LT第i列与L第i行相同,所以矩阵R的第i行的对角线元素计算公式为满足公式(22):
>
公式(22)中的R[i][i]为系数矩阵R的第i行的对角线元素,L[i][i]为三角矩阵L第i行的对角线元素,L[i][k]为三角矩阵L第i行的非对角线元素,由公式(22)可以推导出L[i][i]的计算公式(23):
>
上述求解L第i行的对角线元素的过程可以叫做Cholesky分解一。
根据公式(21)还可以推导出R的第i行第j列的非对角线元素R[i][j]满足以下公式(24):
>
R[i][j]为系数矩阵R的第i行第j列的非对角线元素,L[i][i]为三角矩阵L第i行第i列的对角线元素,L[i][k]为三角矩阵L第i行第k列的非对角线元素,L[j][k]为三角矩阵L第j行第k列的非对角线元素,由公式(23)、(24)可以推导出三角矩阵L第i列的非对角线元素L[j][i]满足公式(25):
>
公式(25)中R[i][j]为所述系数矩阵的第i行第j列的非对角线元素,L[i][i]为所述三角矩阵第i行第i列的对角线元素,L[i][k]为所述三角矩阵第i行第k列的非对角线元素,L[j][k]为所述三角矩阵第j行第k列的非对角线元素。
上述求解L第i列的非对角线元素的过程可以叫做Cholesky分解二。
由于三角矩阵L第一行的非对角线元素全为“0”,因此利用公式(23)计算出L第一行的对角线元素后,可以通过公式(25)和公式(23)计算出三角矩阵L中所有元素的值。
进一步的,将正定对称的系数矩阵R的分解为一个三角矩阵及其转置的乘积之后,求解中间向量的方法具体如下:
将公式(3)展开可以得到公式(31):
根据公式(31)可以推导出常数向量G的第一个元素为三角矩阵L的第一行与中间向量W的乘积,即:G[0]=L[0][0]×W[0],同理可得到G的第i行元素与L和W的关系满足公式(32):
>
公式(32)中,G[i]为G的第i行元素,W[i]为W的第i行元素,L[i][i]为L第i行第i列的对角线元素,L[i][j]为L第i行第j列的非对角线元素,其中i为整数且i的取值范围为[0,n-1]。由公式(32)可以推导出W的第i行元素W[i]的计算公式(33):
>
公式(33)中,G[i]为G的第i行元素,W[i]为W的第i行元素,L[i][i]为L第i行第i列的对角线元素,L[i][j]为L第i行第j列的非对角线元素,其中i为整数且i的取值范围为[0,n-1],以下公式中i的取值范围相同。
再进一步地,求解出中间向量后,根据中间向量求解待求解向量的值的方法具体如下:
将公式(4)展开可以得到以下公式(41):
根据公式(41)可以推导出中间向量W的第i行元素满足公式(42):
>
公式(42)中,W[i]为中间向量W的第i行元素,H[i]为待求解向量H的第i行元素,L[i][i]为L第i行第i列的对角线元素,L[j][i]为L第j行第i列的非对角线元素(即三角矩阵L的转置矩阵LT第i行的非对角线元素)。由公式(42)可以推导出H的第i行元素H[i]的计算公式(43):
>
图1为本发明集成电路第一实施例的示意图,如图1所示,该集成电路用于求解线性方程G=RH,其中G为常数向量、R为系数矩阵、H为待求解向量。该集成电路包括:乘法电路1、加法电路2、开方电路3、除法电路4存储器5和控制单元6。乘法电路1、加法电路2、开方电路3和除法电路4依次串联,加法电路2还与除法电路4连接,除法电路4与存储器5连接,存储器5与乘法电路1连接。控制单元6用于当方程中的系数矩阵为正定对称的矩阵时,控制乘法电路1、加法电路2、开方电路3、除法电路4和存储器5将方程中正定对称的系数矩阵分解为三角矩阵与所述三角矩阵的转置矩阵的乘积;控制单元6还用于控制乘法电路1、加法电路2、除法电路4和存储器5根据所述三角矩阵和所述常数向量计算出中间向量后、根据所述中间向量和所述三角矩阵的转置矩阵计算所述待求解向量。
具体地,控制单元6控制乘法电路1、加法电路2、开方电路3、除法电路4和存储器5将待求解的方程G=RH中的正定对称的系数矩阵R,按照公式(2)的形式分解为一个三角矩阵L与该三角矩阵的转置矩阵LT的乘积。示例性的,以R为“10×10”的正定对称矩阵为例,分解之后的L和LT都是“10×10”的三角矩阵。分解之后的结果存在存储器5中。
表1为R和L的存储状态的一种示例表,计算开始之前,可以预先将R的下对角阵按照表1的方式存储在存储器5中,乘法电路和加法电路计算得到的L元素也按照表1的方式保存在存储器5中。表2为cholesky分解时求三角矩阵的对角线元素时存储器5的读写控制状态表。
表1
表2
在表2中,[00](L[0][0])表示三角矩阵的第一行的对角线元素L[0][0]在存储器中的写地址为00,[10](L[1][1])表示三角矩阵第二行的对角线元素L[1][1]在存储器中的写地址为10。
Cholesky分解一的过程:由公式(23)可知,集成电路中控制单元6的乔里斯基分解一模块控制乘法电路1、加法电路2、开方电路3和除法电路4按照表2对存储器5进行读写,可以根据正定对称的系数矩阵R的下对角阵求解出三角矩阵L的对角线元素,并将L的对角线元素保存到存储器5。示例性的,一种计算方法可以为:乔里斯基分解一模块控制乘法电路1对存储器5中存储的三角矩阵的第i行第k列非对角线元素进行平方运算,将得到的平方结果L[i][k]×L[i][k]发送至加法电路2,其中L为下三角矩阵从i=0时开始计算,第0行的所有非对角线元素为0;控制加法电路2的第一加法器对上述平方结果进行累加运算得到的平方累加结果,平方累加运算的公式为
Cholesky分解二的过程:由公式(25)可知,控制单元6的乔里斯基分解二模块控制乘法电路1、加法电路2、除法电路4计算出L与L[i][i]对应的第i列的非对角线元素L[j][i],保存到存储器5。示例性的,一种计算方法可以:乔里斯基分解二模块控制乘法电路1对三角矩阵L的一行或列的非对角线元素进行相乘运算,计算公式为L[i][k]×L[j][k],将得到的相乘结果发送至加法电路2;乔里斯基分解二模块控制加法电路2的第一加法器对上述相乘结果进行累加运算,计算出相乘累加结果,计算公式为
本实施例中,由R分解出L的过程可以为:先分解出第一列的对角线元素,然后分解出第一列的非对角线元素;根据分解出的结果迭代分解出下一列的对角线元素和非对角线元素,直至将R的下三角阵全部分解完毕。
由方程(33)可知,求解中间向量的过程可以为:控制单元6的中间向量求解模块控制乘法电路1、加法电路2、除法电路4可以根据三角矩阵L和方程(1)中常数向量G,计算出中间向量。示例性的,一种计算方法可以:中间向量求解模块控制乘法电路1对三角矩阵的第i行第j列非对角线元素与所述中间向量第j行元素进行相乘运算,计算公式为L[i][j]×W[j],其中j<i,将相乘运算得到的中间向量相乘结果发送至加法电路2;控制加法电路2的第一加法器对所述中间向量相乘结果进行累加计算出中间向量累加结果,计算公式为
由方程(43)可知,求解待求解向量的过程可以为:控制单元6的待求解向量求解模块控制乘法电路1、加法电路2、除法电路4根据中间向量W和三角矩阵的转置矩阵LT可以计算出方程(1)中的待求解向量H,其中G、R和H之间的关系满足方程(1),即:常数向量G为待求解向量H与正定对称的系数矩阵R的乘积。示例性的,一种计算方法可以:待求解向量求解模块控制乘法电路1对三角矩阵的转置矩阵的第i行第j列的非对角线元素与待求解向量进行相乘运算,将得到的待求解向量相乘结果L[i][j]×H[j]发送至加法电路2;控制加法电路2的第一加法器计算出待求解向量累加结果,计算公式为
进一步地,由于需要求解的线性方程的系数矩阵不一定是正定对称的矩阵,例如方程(5),D=ZH,其中D常数向量、Z为系数矩阵、系数矩阵Z为非正定对称的矩阵,H为待求解向量。需要根据方程(6)先将非正定对称的矩阵Z构造成正定对称的矩阵R=ZTZ。此时,控制单元6还用于当所述系数矩阵为非正定对称的矩阵时,控制乘法电路1、加法电路2和存储器5将系数矩阵Z转换为正定对称的矩阵、将常数向量D转化为所述正定对称的系数矩阵对应的常数向量G=ZTD。
此外,控制单元6可以为该集成电路上一个集成的单元,也可以为该集成电路上分散设置的多个单元。图2为采用cholesky分解进行解线性方程组的状态机的时序图,如图2所示,当待求解的方程的系数矩阵为非正定对称矩阵时,控制单元6处于构造正定对称矩阵的ZTZ210状态,此时控制单元6的正定对称模块指示乘法电路1和加法电路2执行ZTZ210的运算,以构造正定对称矩阵。构造正定对称矩阵状态结束后,控制单元6进入cholesky分解状态,乔里斯基分解一模块指示乘法电路1、加法电路2和开方电路3执行cholesky分解一211,乔里斯基分解二模块指示乘法电路1、加法电路2和除法电路4执行cholesky分解二212,其中cholesky分解一211和cholesky分解二212迭代进行。cholesky分解阶段结束后,控制单元6进入求解中间向量W的状态,中间向量求解模块指示乘法电路1、加法电路2和除法电路4执行中间向量W的计算。求解中间向量W213的阶段结束后,控制单元6进入求解待求解向量H214的状态,待求解向量求解模块指示乘法电路1、加法电路2和除法电路4执行待求解向量H214的计算。当方程的系数矩阵为非正定对称矩阵时,控制单元6进入求解待求解向量H214的状态时,同时进入将非正定对称的系数矩阵对应的常数向量转化的状态,求解G=ZTD,根据求出的正定对称的系数矩阵对应的常数向量的数值求解待求解向量H。
本实施例通过控制单元控制乘法电路、加法电路、开方电路、除法电路和存储器将线性方程中正定对称的系数矩阵分解为三角矩阵与该三角矩阵的转置矩阵的乘积;然后控制单元控制乘法电路、加法电路、除法电路和存储器,根据三角矩阵和常数向量计算出中间向量后、根据中间向量和该三角矩阵的转置矩阵计算待求解向量;实现了由乘法电路、加法电路、开方电路、除法电路和存储器组成的集成电路采用Cholesky分解的方法求解方程,减小了通过Cholesky分解的方法求解方程时所需的芯片的面积和成本,且根据解方程的需求可以灵活设计集成电路的运算能力。
图3本发明集成电路第二实施例的示意图,如图3所示,乘法电路1可以包括乘法器11,与乘法器11输入端分别连接的第一寄存器12和第二寄存器13,与第一寄存器12连接的第一选通器14,以及与第二寄存器13连接的第二选通器15,第一选通器14和第二选通器15分别与存储器5、加法电路2和控制单元(图3未示)连接。其中乘法器11用于对第一寄存器12和第二寄存器13中的数据进行相乘运算;第一选通器14用于根据控制单元发出的选通信号mux0_sel、第二选通器15用于根据控制单元发出的选通信号mux1_sel选择存储器5或加法电路2反馈的数据,分别输入第一寄存器12和第二寄存器13。
如图3所示,加法电路2可以包括:与乘法器11输出端连接的第三寄存器21,与第三寄存器21连接的第一加法器22,与第一加法器22依次闭环连接的第四寄存器23和第三选通器24,与第一加法器22依次串联的第四选通器26、第五寄存器25、第二加法器27、第六寄存器28;第四选通器26的输入端与第五寄存器25的输出端连接。其中,第一加法器22用于对第三寄存器21和第四寄存器23中的数据进行累加;第四选通器26用于根据所述控制单元发出的选通信号accu_end选择第一加法器22的累加结果、输入到第五寄存器25;第二加法器27用于对第五寄存器25中的累加结果与存储器5发送的数据进行加法运算。进一步地,第五寄存器25和第二加法器27可以通过位处理器29连接;位处理器29用于根据控制单元发出的移位信号round_sel或限幅信号clip_sel对第五寄存器25输出的数据进行移位或限幅处理。
可选地,开方电路3包括开方器31,开方器31的输入端与加法电路连接,具体可以与加法电路中第六寄存器28的输出端连接,用于对加法电路输出的数据进行开方运算。
可选地,除法电路4包括除法器41,与除法器41的输入端连接的第五选通器42;第五选通器42的输入端分别与开方器31、加法电路中的第六寄存器28和控制单元连接,除法器41还与控制单元连接。其中第五选通器42用于根据控制单元发出的选通信号图3中的X_sel选择开方器31或第六寄存器28的数据、输入除法器41;除法器41用于对接收的开方器31或第六寄存器28中的数据进行倒数运算后,将倒数运算的结果发送至存储器5。其中除法器41以接收到的控制单元发出的信号“1”为被除数,接收的开方器31或第六寄存器28中的数据为除数,进行除法运算,就可以求出开方器31或第六寄存器28中的数据的倒数。
可选地,存储器5包括:第六选通器51、第七选通器52、第一存储单元53、第二存储单元54、第三存储单元55。其中第六选通器51与除法器41、第六寄存器28和控制单元分别连接,第六选通器51用于选择除法电路中除法器41或加法电路中第六寄存器28的数据、输入第一存储单元53。第七选通器52与第一存储单元53、加法电路2中的第二加法器27和控制单元连接,用于选择第一存储单元53的数据、输入加法电路中的第二加法器27。第一存储单元53,分别与第六选通器51、第七选通器52、乘法电路1连接,用于存储第六选通器51发送的数据,将第六选通器51发送的数据发送至乘法电路1,具体为发送至乘法电路1中的第一选通器14、第二选通器15。第二存储单元54、第三存储单元55,各自与加法电路2中的第六寄存器28、乘法电路1第一选通器14和第二选通器15连接,用于存储第六寄存器28发送的数据,并将从第六寄存器28接收的数据发送至乘法电路1的第一选通器14和第二选通器15。
具体地,控制单元通过向各个运算电路即:乘法电路1、加法电路2、除法电路4、开方电路3发送控制信号,控制各个电路中元件进行解方程运算。例如控制单元分别向第一选通器14和第二选通器15发送选通控制信号mux0_sel和mux1_sel,控制第一选通器14、第二选通器15选择输出的数据,从而可以控制进入乘法器11的数据。优选的,图3中的第一、二、三、四、五、六寄存器为使用D触发器构造的寄存器。控制单元向第三选通器24发送清零信号sum_clr,用于在每次累加循环开始之前对加对加法电路清零。控制单元向第四选通器26发送累加结束信号accu_end,控制第一加法器的累加次数。控制单元向位处理器29发送四舍五入移位信号round_sel或限幅信号clip_sel等,用于针对不同的状态选择不同的移位限幅通路,例如:位处理器29之前的电路对信号进行过放大处理,经过位处理器29对放大的信号进行移位处理后就可以得到实际信号。当然控制单元也向第五、六、七选通器发送选通信号,控制第五、六、七选通器的输出。
此外,将存储器5分为三个存储单元,每个存储单元中存储不同的数据。控制单元通过控制第一选通器14、第二选通器15和第七选通器52,可以将不同状态下存储器5中的数据送入乘法器11或加法器28等。例如:在将待解方程的系数矩阵Z构造成正定对称矩阵R时,可以在第一存储单元53中预先按行存储ZT的元素,在第二存储单元54中预先按列存储Z的元素,计算R=ZTZ时,第一选通器14将第一存储单元53的数据输出到乘法器11、第二选通器15将第二存储单元54的数据输出到乘法器,然后乘法器对接收到的两路数据进行相乘运算。当存储单路中只存在一个RAM时,每一个存储单元可以为RAM中的一段存储空间,此时每进行一次运算都要读取该RAM,读取速度较慢。而在存储器分为多个RAM时,每一个存储单元可以为一个RAM,将需要计算的数据存储在不同的RAM中,进行运算时可以同时读取多个RAM中的数据,有利于提高读取存储器中数据的速度。
本实施例中的集成电路可以为专门用于解方程的专用集成电路(Application Specific Integrated Circuit;以下简称:ASIC),在控制单元的指示下,乘法电路完成所有的乘法运算、加法电路完成所有的加法运算、开方电路完成所有的开方运算、除法电路完成所有的倒数运算,由于采用第一选通器和第二选通器,可以控制进入乘法器的不同通路,同时采用四级流水线结构,即采用了四级寄存器,分别将多路选通器、乘法器、加法器和RAM分割开,可以同时执行多个操作。乘法电路、加法电路、开方电路、除法电路重复使用,可以减小芯片的面积,降低芯片成本。本实施例采用集成电路造出方程的正定对称的系数矩阵后,将该正定对称的系数矩阵分解为三角矩阵与该三角矩阵的转置矩阵的乘积;根据三角矩阵和常数向量计算出中间向量后,根据中间向量和该三角矩阵的转置矩阵计算待求解向量;从而实现由乘法电路、加法电路、开方电路、除法电路和存储器组成的ASIC通过Cholesky分解的方法求解方程的效果,减小了求解方程所需的芯片的面积,降低了解方程的成本,并可以根据解方程的运算需求设计集成电路的运算能力。
图4为本发明集成电路解方程的方法第一实施例的流程图,如图4所示,该集成电路解方程的方法可以采用上述的集成电路第一、第二实施例中的任意一种集成电路,求解方程G=RH,其中G为常数向量、R为系数矩阵、H为待求解向量,具体包括以下步骤:
步骤100、如果所述系数矩阵为正定对称的矩阵,控制单元控制乘法电路、加法电路、开方电路、除法电路和存储器,将所述系数矩阵分解为三角矩阵与所述三角矩阵的转置矩阵的乘积。
该实施例中的乘法电路、加法电路、开方电路和除法电路的结构可以采用本发明集成电路实施例中的任意结构。其中控制单元控制所述乘法电路、所述加法电路、所述开方电路、所述除法电路和所述存储器,根据公式(23)对待求解方程中正定对称的系数矩阵R进行Cholesky分解一,求解出三角矩阵L第一列的对角线元素;然后控制单元控制乘法电路、加法电路和除法电路根据公式(25)进行Cholesky分解二,求解出三角矩阵L第一列的非对角线元素。其中Cholesky分解一、Cholesky分解二的过程迭代进行,直至将R分解为完毕,其中R=LLT。Cholesky分解一、Cholesky分解二的具体方法可以参照本发明集成电路第一实施例中的相关描述。
步骤200、所述控制单元控制所述乘法电路、所述加法电路、所述除法电路和所述存储器,根据所述三角矩阵和所述常数向量计算出中间向量后,根据所述中间向量和所述三角矩阵的转置矩阵计算出方程中的待求解向量。
控制单元控制乘法电路、加法电路、除法电路和存储器,根据方程(33)求解中间向量;然后控制单元控制乘法电路、加法电路和除法电路,根据方程(43)求解待求解向量。求解中间向量、待求解向量的过程可以参照本发明集成电路第一实施例中的相关描述。
此外,若待解方程的系数矩阵为非正定对称矩阵,则在步骤100之前还可以执行以下步骤:所述控制单元控制所述乘法电路和加法电路,对所述系数矩阵进行转置、相乘、累加运算,将所述非正定对称的矩阵转换为正定对称的矩阵、并对常数向量进行相应的变换。例如将方程(5)非正定对称的矩阵Z构造成正定对称矩阵,具体为:正定对称单元的乘法电路和加法电路执行矩阵相乘、累加的过程得到ZTZ=R。
本实施例在控制单元的控制下,乘法电路和加法电路构造出方程的正定对称的系数矩阵后,乘法电路、加法电路、开方电路、除法电路和存储器将该正定对称的系数矩阵分解为三角矩阵与该三角矩阵的转置矩阵的乘积;然后乘法电路、加法电路、除法电路和存储器根据三角矩阵和常数向量计算出中间向量后,根据中间向量和该三角矩阵的转置矩阵计算待求解向量;从而实现了由乘法电路、加法电路、开方电路、除法电路和存储器组成的集成电路通过Cholesky分解的方法求解方程的效果,减小了求解方程所需的芯片的面积,降低了解方程的成本,且根据解方程的需求可以灵活设计集成电路的运算能力。
图5为本发明集成电路解方程的方法第二实施例的流程图,如图5所示,在本发明集成电路解方程的方法第一实施例的基础上,步骤100可以包括以下步骤:
步骤101、当所述系数矩阵为正定对称的矩阵时,所述控制单元的乔里斯基分解一模块控制所述乘法电路、所述加法电路和所述开方电路根据公式(23):>计算所述三角矩阵的对角线元素,其中R[i][i]为所述系数矩阵第i行的对角线元素,L[i][i]为所述三角矩阵第i行第i列的对角线元素,L[i][k]为所述三角矩阵第i行第k列的非对角线元素;
步骤102、控制单元的乔里斯基分解二模块控制所述乘法电路、所述加法电路和所述除法电路根据公式(25):>计算所述三角矩阵第i行的非对角线元素,其中R[i][j]为所述系数矩阵的第i行第j列的非对角线元素,L[j][k]为所述三角矩阵第j行第k列的非对角线元素。
上述的步骤101和步骤102迭代进行。
其中步骤101为Cholesky分解一的过程,具体可以参照本发明集成电路第一实施例中控制单元的乔里斯基分解一模块的相关描述。步骤102为Cholesky分解二的过程,参照本发明集成电路第一实施例中控制单元的乔里斯基分解二模块的相关描述。
本实施例在控制单元的控制下,乘法电路和加法电路构造出方程的正定对称的系数矩阵后,乘法电路、加法电路、开方电路、除法电路和存储器对正定对称的系数矩阵进行Cholesky分解一、Cholesky分解二后,将正定对称的系数矩阵分解为三角矩阵与该三角矩阵的转置矩阵的乘积;然后乘法电路、加法电路、除法电路和存储器计算出中间向量后,根据中间向量计算待求解向量;实现了由乘法电路、加法电路、开方电路、除法电路和存储器组成的集成电路通过Cholesky分解的方法求解方程的效果,减小了求解方程所需的芯片的面积,降低了解方程的成本,且根据解方程的需求可以灵活设计集成电路的运算能力。
图6为本发明集成电路解方程的方法第三实施例的流程图,如图6所示,在本发明集成电路解方程的方法第一、第二实施例的基础上,步骤200可以包括以下步骤:
首先求解中间向量,包括以下步骤:
步骤201、所述控制单元的中间向量求解模块控制所述乘法电路、所述加法电路和所述除法电路根据公式(33):>计算所述中间向量的i行的元素,其中G[i]为所述常数向量的第i行元素,W[i]为所述中间向量的第i行元素,L[i][i]为所述三角矩阵第i行第i列的对角线元素,L[i][j]为所述三角矩阵第i行第j列的非对角线元素。
其次,求解待求解向量,执行以下步骤:
步骤202、所述控制单元的待求解向量求解模块控制所述乘法电路、所述加法电路和所述除法电路根据公式(43):>计算所述待求解向量第i行的元素,其中W[i]为所述中间向量第i行元素,H[i]为所述待求解向量H的第i行元素,L[i][i]为所述三角矩阵第i行第i列的对角线元素,L[j][i]为所述三角矩阵第j行第i列的非对角线元素。
本实施例在控制单元的控制下,乘法电路和加法电路构造出方程的正定对称的系数矩阵后,乘法电路、加法电路、开方电路、除法电路和存储器对正定对称的系数矩阵进行Cholesky分解一、Cholesky分解二后,将正定对称的系数矩阵分解为三角矩阵与该三角矩阵的转置矩阵的乘积;然后乘法电路、加法电路、除法电路和存储器计算出中间向量后,根据中间向量计算待求解向量;实现了集成电路通过Cholesky分解的方法求解方程的效果,减小了求解方程所需的芯片的面积和成本,可以根据解方程的需求灵活设计集成电路的运算能力。
本领域普通技术人员可以理解:实现上述方法实施例的全部或部分步骤可以通过程序指令相关的硬件来完成,前述的程序可以存储于一计算机可读取存储介质中,该程序在执行时,执行包括上述方法实施例的步骤;而前述的存储介质包括:ROM、RAM、磁碟或光盘等各种可以存储程序代码的介质。
最后应说明的是:以上实施例仅用以说明本发明的技术方案,而非对其限制;尽管参照前述实施例对本发明进行了详细的说明,本领域的普通技术人员应当理解:其依然可以对前述各实施例所记载的技术方案进行修改,或者对其中部分技术特征进行等同替换;而这些修改或者替换,并不使相应技术方案的本质脱离本发明各实施例技术方案的精神和范围。
机译: 半导体集成电路系统的设计方法,导体集成电路基板的设计方法,封装体设计方法,导体集成电路的设计方法,导体集成电路系统的设计,导体集成电路系统的设计,导体集成电路系统的设计和半导体集成电路
机译: 一种用于访问集成电路中的存储单元的方法,一种用于确定一组字线电压-集成电路中的标识符的方法,一种用于对集成电路中的存储单元进行分类的方法,一种用于确定集成电路中的字线电压的方法访问集成电路中的存储单元和集成电路
机译: 用于访问集成电路中的存储单元的方法,确定集成电路中的一组字线电压标识符的方法,用于对集成电路中的存储单元进行分类的方法,用于确定用于访问存储器中的存储单元的字线电压的方法集成电路和集成电路