编码器与快闪存储器控制器的制作方法

摘要: 本发明关于快闪存储器,尤其关于一种用于在快闪存储器储存设备中执行错误校正编码的编码器以及相关快闪存储器控制器。背景技术:1、典型的编码器通常依赖奇偶校验检查矩阵...
编码器与快闪存储器控制器的制作方法

本发明关于快闪存储器,尤其关于一种用于在快闪存储器储存设备中执行错误校正编码的编码器以及相关快闪存储器控制器。

背景技术:

1、典型的编码器通常依赖奇偶校验检查矩阵(parity-check matrix)来检查编码器产生的校验数据(parity)是否正确。例如,当编码器对数据进行编码产生校验数据后,将数据和校验数据与奇偶校验检查矩阵相乘,产生乘法结果。若乘法结果等于“0”,则判断编码正确;若乘法结果不等于“0”,则判断编码错误。相对于奇偶校验检查矩阵,编码器将依赖对应的奇偶校验生成矩阵来产生适当的校验数据。然而,在某些情况下,可能无法找到奇偶校验生成矩阵。在这种情形下,编码器需要执行大量的矩阵乘法运算、补偿运算和/或调整运算,才能获得相似的校验数据(相较于直接使用奇偶校验生成矩阵所产生的校验数据)。这种操作将增加编码器的复杂度,尤其是补偿运算通常是非因果式(non-causal)的,这将大大增加编码器的硬体成本和电路复杂度。

技术实现思路

1、本发明提供了一种低密度奇偶校验(low-density parity-check,ldpc)编码器架构,其利用具有两级循环结构的类四维超立方体式(tesseract-like)的奇偶校验检查矩阵,其中,类四维超立方体式的奇偶校验检查矩阵是透过对一般准循环(quasi-cyclic,qc)-ldpc奇偶校验检查矩阵进行同构变换(isomorphic transformation)所获得的。此外,类四维超立方体式的奇偶校验检查矩阵可以分解为第一级子矩阵和第二级子矩阵的层次结构。在一个实施例中,一个或多个非零第一级子矩阵是由第二级子矩阵组成的区块循环(block circulant)矩阵,而每个非零第二级子矩阵都是循环置换矩阵(circulantpermutation matrix)。本发明的ldpc编码器基于类四维超立方体式的奇偶校验检查矩阵,将输入数据分成多个数据区块,透过桶形移位器模块产生对应的局部校验数据区块,然后执行循环卷积运算得出中间结果。接着,进一步应用补偿电路来补偿中间结果,以产生最终的校验数据区块。

2、进一步来说,由于类四维超立方体式的奇偶校验检查矩阵的结构特性,补偿运算可以基于因果式(causal)的电路架构来实现。其中,针对每个中间结果的补偿运算仅需依赖一个或多个先前产生的中间结果。与需要在补偿运算进行之前,缓冲所有中间结果的习知非因果式的电路架构相比,这种因果关系允许编码器以更少的延迟、更低的存储器要求和更为精简的控制逻辑来执行编码。

3、本发明的实施例提供一种编码器,该编码器包含:一第一桶式移位器模块、一第一计算电路、一调整电路、一第一循环卷积计算电路、一补偿电路与一第二计算电路。该第一桶式移位器模块用以将多个数据区块进行处理以依序产生多个局部校验数据区块,其中,该多个局部校验数据区块包含了一第一部分及一第二部分,该第一部分的产生时间早于该第二部分,且该第一部分所包含之局部校验数据区块的数量少于该第二部分所包含之局部校验数据区块的数量。该第一计算电路耦接于该第一桶式移位器模块,用以依据该第一部分以产生一第一计算结果。该调整电路用以依据该第一计算结果来调整该多个局部校验数据区块的该第二部分,以产生一调整后第二部分。该第一循环卷积(circulantconvolution)计算电路耦接于该调整电路,用以对该调整后第一部分进行循环卷积操作,以产生一第二部分的校验数据区块。该补偿电路耦接于该第一循环卷积计算电路,用于对该第二部分的校验数据区块进行一补偿运算来产生补偿后的该第二部分的校验数据区块,其中该补偿运算是因果式(causal)的。该第二计算电路耦接于该第一循环卷积计算电路,用以至少依据补偿后的该第二部分的校验数据区块以产生一第一部分的校验数据区块。其中,该第一部分的校验数据区块及补偿后的该第二部分的校验数据区块系作为该编码器针对该多个数据区块所产生的多个校验数据区块,且该多个数据区块以及该多个校验数据区块系被写入至一快闪存储器中。

4、本发明的实施例提供一种编码器,该编码器包含:一桶式移位器模块、一调整电路、一循环卷积(circulant convolution)计算电路、一补偿电路与一计算电路。该桶式移位器模块用以将多个数据区块进行处理以产生多个局部校验数据区块,其中,该多个局部校验数据区块包含了一第一部分及一第二部分,该第一部分的产生时间早于该第二部分,且该第一部分所包含之局部校验数据区块的数量少于该第二部分所包含之局部校验数据区块的数量。该调整电路用以依据该多个局部校验数据区块的该第一部分来调整该多个局部校验数据区块的该第二部分,以产生一调整后的第二部分。该循环卷积计算电路耦接于该调整电路,用以对该调整后的第二部分进行循环卷积操作,以产生一第二部分的校验数据区块。该补偿电路耦接于该循环卷积计算电路,用以对该第二部分的校验数据区块进行一补偿运算,以产生补偿后的该第二部分的校验数据区块,其中该补偿运算是因果式(causal)的。计算电路耦接于该循环卷积计算电路,用以至少依据补偿后的该第二部分的校验数据区块,以产生一第二部分的校验数据区块。其中,该第一部分的校验数据区块及补偿后的该第二部分的校验数据区块系作为该编码器针对该多个数据区块所产生的多个校验数据区块,且该多个数据区块以及该多个校验数据区块系被写入至一快闪存储器中。

5、本发明的实施例提供一种编码器,该编码器包含:一桶式移位模块、一循环卷积计算电路与一补偿电路。该桶式移位模块用于处理多个数据区块,以依序产生多个局部校验(partial parity)数据区块。该循环卷积计算电路耦接于该桶式移位器模块,用以对多个局部校验数据区块进行循环卷积操作,以产生多个卷积结果。该补偿电路耦接于该循环卷积计算电路,用以对该多个卷积结果进行一补偿运算,以产生多个校验数据区块,其中该补偿运算是因果式(causal)的。其中,该多个数据区块与该多个校验数据区块被写入一快闪存储器中。

1.一种编码器,包含:

2.如权利要求1所述的编码器,其特征在于,该补偿电路用于分别对该多个局部校验数据区块的该第二部分中的每一者所对应的一卷积结果进行该补偿运算;该补偿电路依据一个或多个在产生时间上早于一目标局部校验数据区块的其他局部校验数据区块所对应的卷积结果,补偿该目标局部校验数据区块所对应的卷积结果。

3.如权利要求1所述的编码器,其特征在于,该多个局部校验数据区块的该第一部分包含了c1个局部校验数据区块,该多个局部校验数据区块的该第二部分包含了c2个局部校验数据区块,并且c1小于c2;该第一计算电路包含:

4.如权利要求3所述的编码器,其特征在于,补偿后的该第二部分的校验数据区块包含了c2个补偿后校验数据区块,且该第二计算电路包含有:

5.如权利要求3所述的编码器,其特征在于,c1等于2,c2等于3。

6.如权利要求5所述的编码器,其特征在于,该第一计算电路以及该第二计算电路中的每一者包含一补偿电路,该补偿电路以因果式操作来执行一补偿运算。

7.如权利要求1所述的编码器,其特征在于,一快闪存储器控制器中的一低密度奇偶检查码(low-density parity check code,ldpc code)编码电路。

8.如权利要求1所述的编码器,其特征在于,该编码器用于基于与一准循环(quasi-cyclic,qc)-ldpc奇偶校验检查矩阵同构(isomorphic)的类四维超立方体式(tesseract-like)的奇偶校验检查矩阵,对该多个数据区块执行ldpc编码。

9.一种包含如权利要求1所述的编码器的快闪存储器控制器。

10.一种编码器,包含:

11.如权利要求10所述的编码器,其特征在于,该补偿电路用于分别对该多个局部校验数据区块的该第二部分中的每一者所对应的一卷积结果进行该补偿运算;该补偿电路依据一个或多个在产生时间上早于一目标局部校验数据区块的其他局部校验数据区块所对应的卷积结果,补偿该目标局部校验数据区块所对应的卷积结果。

12.如权利要求9所述的编码器,其特征在于,该多个局部校验数据区块的该第一部分仅包含一个局部校验数据区块。

13.如权利要求10所述的编码器,其特征在于,其为一快闪存储器控制器中的一低密度奇偶检查码(low-density parity check code,ldpc code)编码电路。

14.如权利要求10所述的编码器,其特征在于,该编码器用于基于与一准循环(quasi-cyclic,qc)-ldpc奇偶校验检查矩阵同构(isomorphic)的类四维超立方体式(tesseract-like)的奇偶校验检查矩阵,对该多个数据区块执行ldpc编码。

15.如权利要求10所述的编码器,其特征在于,该编码器用于基于一奇偶校验检查矩阵,对该多个数据区块进行ldpc编码,且该奇偶校验检查矩阵的第一列与第一行上的每个子矩阵皆为一单位矩阵。

16.一种包含如权利要求10所述的编码器的快闪存储器控制器。

17.一种编码器,包含:

18.如权利要求17所述的编码器,其特征在于,该补偿电路用于分别对该多个局部校验中的每一者所对应的一卷积结果进行该补偿运算;该补偿电路依据于一个或多个在产生时间上早于一目标局部校验数据区块的其他局部校验数据区块所对应的卷积结果,补偿该目标局部校验数据区块所对应的卷积结果。

19.如权利要求17所述的编码器,其特征在于,该编码器用于基于与一准循环(quasi-cyclic,qc)-ldpc奇偶校验检查矩阵同构(isomorphic)的类四维超立方体式(tesseract-like)的奇偶校验检查矩阵,对该多个数据区块执行ldpc编码。

20.一种包含如权利要求17所述的编码器的快闪存储器控制器。