存储器阵列中故障地址的数据结构及故障地址的编码方法

摘要

一种存储器阵列中故障地址的数据结构及故障地址的编码方法。该存储器阵列中的故障地址的编码方法，该存储器阵列中一个页的容量以2m位为一个区段被区分为多个区段，该故障地址的编码方法包括：获得这些区段中的一第一区段内的N1个失效位的位置；产生(N1+1)位的一第一区段起始码；以及产生N1个m位的故障码接续于该第一区段起始码之后，用以指示该第一区段中N1个失效位的位置；其中，N1为大于或等于零的整数，且m为大于0的整数。

说明书

技术领域

本发明是有关于一种存储器阵列中地址数据的编码方法，且特别是有关于一种存储器阵列中故障地址的数据结构及故障地址的编码方法。

背景技术

众所周知，现今的固态储存装置(Solid State Drive，SSD)一般使用与非门闪存(NAND flash memory)为主要存储组件，而此类的闪存为一种非易失性(non-volatile)的存储器组件。也就是说，当数据写入闪存后，一旦系统电源关闭，数据仍保存在闪存中。在固态储存装置中，一般会将闪存的存储器阵列(memory array)区分为多个区块(block)作为擦除单元，而每个区块又被区分为多个页(page)作为读写单元。

一般来说，在闪存制作的过程，不可避免地会有一些故障存储单元(defective cell)而无法运行。于闪存制作完成后，需要先验证存储器阵列(memory array)中的所有存储单元，并确定所有无法运行的故障存储单元的地址(address)，并储存于损坏区地址表(address list of defective region)。当闪存运行时，损坏区地址表中所有地址所对应的故障存储单元即可被略过而不会被使用。再者，故障存储单元又可称为失效位(fail bit)。

在与非门闪存的存储器阵列(memory array)中，一个17,664字节(Byte)容量的页(page)，共计有141,312(17,664×8)个位(bit)，其中，141,312大于2¹⁷且小于2¹⁸。因此，利用18个位长度的地址即可寻址(address)至一个页里面的任一个位置。换句话说，需要利用18位长度的地址来记录一个失效位的位置。

一般来说，与非门闪存制造完成后会有约1％的损坏率。因此，在一个页的容量中约有1,414(14,132×1％)个失效位。为了表示出一个页中的所有失效位，因此损坏区地址表中至少需要25,452(1,414×18)位的容量来记录一个页里面的所有失效位的位置。

由于损坏区地址表会占去数据的储存空间，为维持使用者的数据储存空间，固态储存装置需额外增加闪存来储存损坏区地址表，如此将造成固态储存装置的成本提高。因此，如何减少损坏区地址表的大小是目前欲解决的问题。

发明内容

本发明的目的在于提出一种存储器阵列中的故障地址编码方法。利用霍夫曼码(Huffman code)来完成故障地址的编码，达成利用更少的数据量来记录相同数目的故障位。

本发明有关于一种存储器阵列中的故障地址的数据结构，该存储器阵列中一个页的容量以2^m位为一个区段被区分为多个区段，且该故障地址用以指出该页中的多个失效位的位置，该故障地址的数据结构包括：多个区段码对应至这些区段，其中，这些区段码中的一第一区段码对应至一第一区段，且该第一区段内具有N个失效位，该第一区段码包括：一第一区段起始码，具有(N+1)位；以及N个m位的故障码，接续于该第一区段起始码之后，用以指示该第一区段中N个失效位的位置；其中，N为大于或等于零的整数，且m为大于0的整数。

本发明有关于一种存储器阵列中的故障地址的编码方法，该存储器阵列中一个页的容量以2^m位为一个区段被区分为多个区段，该故障地址的编码方法包括：获得这些区段中的一第一区段内的N1个失效位的位置；产生(N1+1)位的一第一区段起始码；以及产生N1个m位的故障码接续于该第一区段起始码之后，用以指示该第一区段中N1个失效位的位置；其中，N1为大于或等于零的整数，且m为大于0的整数。

本发明有关于一种存储器阵列中的故障地址的数据结构，该存储器阵列中一个页的容量以2m位为一个区段被区分为多个区段，且每一该区段还被区分为二个子区段，且该故障地址用以指出该页中的多个失效位的位置，该故障地址的数据结构包括：多个区段码对应至这些区段，其中，这些区段码中的一第一区段码对应至一第一区段，且该第一区段内具有(Na+Nb)个失效位的位置，其中，Na个失效位位于对应的该第一区段内的一第一子区段，Nb个失效位位于该第一区段内的一第二子区段，该第一区段码包括：一第一区段起始码，具有(Na+Nb+1)位；一第一第一子区段失效位码，其为Na的二进制代码，接续于该第一区段起始码之后；以及Na个(m-1)位的故障码以及Nb个(m-1)位的故障码，接续于该第一第一子区段失效位码之后，用以指示该第一区段中该第一子区段内的Na个失效位的位置以及该第二子区段内的Nb个失效位的位置；其中，Na与Nb为大于或等于零的整数，且m为大于0的整数。

本发明有关于一种存储器阵列中的故障地址的编码方法，该存储器阵列中一个页的容量以2^m位为一个区段被区分为多个区段，且每一该区段还被区分为二个子区段，该故障地址的编码方法包括：获得这些区段中的一第一区段内的(Na1+Nb1)个失效位的位置，其中Na1个失效位位于该第一区段内的一第一子区段，Nb1个失效位位于该第一区段内的一第二子区段；产生(Na1+Nb1+1)位的一第一区段起始码；产生一第一第一子区段失效位码，其为Na1的二进制代码，接续于该第一区段起始码之后；以及产生Na1个(m-1)位的故障码以及Nb1个(m-1)位的故障码，接续于该第一第一子区段失效位码之后，用以指示该第一区段中该第一子区段内的Na1个失效位的位置以及该第二子区段内的Nb1个失效位的位置；其中，Na1与Nb1为大于或等于零的整数，且m为大于0的整数。

为了对本发明的上述及其它方面有更佳的了解，下文特举较佳实施例，并结合附图详细说明如下。

附图说明

图1A与图1B示出了区段中出现失效位数目与机率的关系图。

图2示出了为本发明中区段起始码的编码实施例示意图。

图3示出了本发明故障地址的编码方法第一实施例。

图4示出了利用本发明第一实施例所完成的故障地址示意图。

图5示出了本发明故障地址的编码方法第二实施例。

图6示出了利用本发明第二实施例所完成的故障地址示意图。

图7示出了第二实施例中区段内的失效位数目与子区段失效位码的位长度及区段码所节省的位数目的示意图。

具体实施方式

在本发明实施例提出的故障地址的数据结构中，存储器阵列中一个页的容量被区分为多个区段(segment)，并以区段为单位来记录各个区段中的失效位的地址。换句话说，每一个区段具有一个对应的区段码用以指示该区段中的失效位的地址。在本发明实施例中，每一个区段码包含区段起始码用以指示对应区段中的失效位数目。在本发明一实施例中，区段起始码可对应于失效位数目的发生机率。

请参照图1A与图1B，其示出了区段中出现失效位数目与机率的关系图。以下是以64位为一个区段，并将一个页区分为多个区段(segment)为例来进行说明。

如图1A与图1B所示，经由统计可知，在每个区段中随着失效位数目的增加而呈现机率下降的趋势。亦即，一个区段中出现零个失效位的机率最高(约为52.26％)、一个区段中出现一个失效位的机率次之(约为33.98％)、一个区段中出现二个失效位的机率再次之(约为10.81％)、一个区段中出现三个失效位的机率再次之(约为2.65％)。再者，一个区段中出现三十二个失效位的机率已经降低至10^-44。

以霍夫曼编码理论为例，霍夫曼编码理论是利用机率大小来作为编码的依据。机率越高的事件(event)，其编码的位长度越少；机率越低的事件，其编码的位长度越长。因此，如图3所示，其为本发明中区段起始码的编码实施例示意图。其中，区段起始码是根据失效位数目的发生机率所产生，并用以指示出该区段中的失效位数目。

当区段中出现零个失效位时，区段起始码设定为“0”；当区段中出现一个失效位时，区段起始码设定为“10”；当区段中出现二个失效位时，区段起始码设定为“110”；当区段中出现三个失效位时，区段起始码设定为“1110”；当区段中出现四个失效位时，区段起始码设定为“11110”；当区段中出现五个失效位时，区段起始码设定为“111110”；并且依此类推。换言之，区段起始码中“1”的数目总合即为该区段中的失效位数目。再者，区段起始码的位数目(bit number of segment start code)是由失效位的数目来决定。其中，区段起始码的位数目为失效位的数目加1。

当然，图2中的区段起始码中的数字(digit)也可以互相交换。举例来说，当区段中出现零个失效位时，区段起始码设定为“1”；当区段中出现一个失效位时，区段起始码设定为“01”；当区段中出现二个失效位时，区段起始码设定为“001”；当区段中出现三个失效位时，区段起始码设定为“0001”；当区段中出现四个失效位时，区段起始码设定为“00001”；当区段中出现五个失效位时，区段起始码设定为“000001”；并且依此类推。换言之，区段起始码中“0”的数目总合即为该区段中的失效位数目。

再者请参照图3，其示出了本发明故障地址的编码方法第一实施例。根据本发明的第一实施例，存储器阵列中一个页的容量以2^m位为一个区段区分为p个区段(segment)。因此，利用m个位长度的地址即可表示一个区段里面的任一个失效位的位置。再者，每一个区段码中包括区段起始码与故障码，其中，区段起始码用以指示对应区段中的失效位数目，而故障码用以指示对应区段中的失效位的位置。在本实施例中，故障码的数目可为零个。而故障地址的数据结构即包括所有区段码的组合。

首先设定x＝1(步骤S402)，接着获得第x个区段中的失效位数目Nx与位置(步骤S406)，其中失效位数目Nx可为零；再者，产生(Nx+1)位的区段起始码(步骤S408)以及产生Nx个m位的故障码(步骤S410)。接着，结合区段起始码以及Nx个故障码成为第x个区段码(步骤S412)。

当x＝p成立时(步骤S416)，代表所有p个区段码皆已完成，此时结合所有区段码而成为故障地址(步骤S420)；反之，当x＝p不成立时(步骤S416)，代表尚未完成p个区段码，因此设定x＝x+1(步骤S418)，并继续执行步骤S406。

再者请参照图4，其示出了利用本发明第一实施例所完成的故障地址示意图。其中，将一个页的容量区分为多个区段(segment)，例如，假设一个页的容量为141,311Bits，且设定每64(＝26)个位为一个区段。因此，一个页共可区分为2,208(141,312/64)个区段。而利用6个位长度的地址即可表示一个区段里面的任一个失效位的位置。

每个区段码(segment code)中，以失效位数目来决定区段起始码；接着，以六个位为一个故障码用以指示出该区段中故障位的位置。举例来说，假设一个区段的失效位数目为M，则会有M个故障码接续于区段起始码之后，其中M为大于或等于零的整数。

如图4所示，第一个区段Seg1中有三个失效位。因此，第一区段码为区段起始码“1110”合并三个故障码，亦即“1110[a5:a0][b5:b0][c5:c0]”。其中[a5:a0]指示出第一区段Seg1中第一个故障位的位置、[b5:b0]指示出第一区段Seg1中第二个故障位的位置、[c5:c0]指示出第一区段Seg1中第三个故障位的位置。

第二个区段Seg2中有一个失效位。因此，第二区段码为区段起始码“10”合并一个故障码，亦即“10[d5:d0]”。其中[d5:d0]指示出第二区段Seg2中第一个故障位的位置。

第三个区段Seg3中有零个失效位。因此，第三区段码为区段起始码“0”合并零个故障码，亦即“0”。

第四个区段Seg4中有四个失效位。因此，第四区段码为区段起始码“11110”合并四个故障码，亦即“11110[e5:e0][f5:f0][g5:g0][h5:h0]”。其中[e5:e0]指示出第四区段Seg4中第一个故障位的位置、[f5:f0]指示出第四区段Seg4中第二个故障位的位置、[g5:g0]指示出第四区段Seg4中第三个故障位的位置、[h5:h0]指示出第四区段Seg4中第四个故障位的位置。

利用相同的方式来进行所有区段码的编码，因此第2,207个区段Seg2207中有零个失效位。所以第2,207区段码为区段起始码“0”合并零个故障码，亦即“0”。

第2,208个区段Seg2208中有二个失效位。因此，第2208区段码为区段起始码“110”合并二个故障码，亦即“110[i5:i0][j5:j0]”。其中[i5:i0]指示出第2,208区段Seg2208中第一个故障位的位置、[j5:j0]指示出第2,208区段Seg2208中第二个故障位的位置。

接着，将所有2,208个区段码结合之后即完成上述一个页的故障地址的编码。其编码完成后的故障地址为：“1110[a5:a0][b5:b0][c5:c0]10[d5:d0]011110[e5:e0][f5:f0][g5:g0][h5:h0]……0110[i5:i0][j5:j0]”。

举例来说，在与非门闪存具有约1％的损坏区时，一个页中约有1,414(14,132×1％)个故障位。因此，为了指示出一个页中所有故障位的位置，损坏区地址表中故障地址的长度为12,106(2,208+1,414+6×1,414)位，而故障地址可用来记录一个页里面的所有故障位的位置。

明显地，在相同的故障位数目下，本发明第一实施例的故障地址的编码方法可有效地减少纪录所有故障位的位置的数据量。

再者，请参照图5，其示出了本发明故障地址的编码方法第二实施例。根据本发明的第二实施例，存储器阵列中一个页的容量以2^m位为一个区段区分为p个区段(segment)，而每个区段再区分为二个子区段。因此，利用(m-1)个位长度的地址即可表示一个子区段里面的任一个失效位的位置。再者，每一个区段码中包括区段起始码、子区段失效位码(sub-segment>

首先设定x＝1(步骤S602)，接着获得第x个区段中的失效位数目(Nax+Nbx)及位置(步骤S604)，其中Nax及Nbx分别为第x个区段的各子区段中的失效位数目，且Nax及Nbx可为零；再者，产生(Nax+Nbx+1)位的区段起始码(步骤S606)，将Nax的二进制代码(binary code)作为子区段失效位码(步骤S608)，以及产生Nax个(m-1)位的故障码与Nbx个(m-1)位的故障码(步骤S610)。接着，结合区段起始码，子区段失效位码以及(Nax+Nbx)个故障码成为第x个区段码(步骤S612)。

当x＝p成立时(步骤S614)，代表所有p个区段码皆已完成，此时结合所有区段码而成为故障地址(步骤S616)；反之，当x＝p不成立时(步骤S614)，代表尚未完成p个区段码，因此设定x＝x+1(步骤S618)，并继续执行步骤S604。

请参照图7，其绘示第二实施例中区段内的失效位数目与子区段失效位码的位长度的示意图。在本实施例中，子区段失效位码可用以指示前半区段中的失效位数目Nax或者后半区段中的失效位数目Nbx，其中，子区段失效位码的位长度是根据区段中的失效位数目(Nax+Nbx)而决定，并以二进制代码(binary code)来表示。举例来说，假设第x个区段中有1个失效位(即Nax+Nbx＝1)，则其前半区段或后半区段中的失效位数目具有二种可能性，即0个失效位及1个失效位。因此，子区段失效位码的位长度设定为1，并用1个位长度的二进制法来表示前半区段或后半区段中的失效位数目。例如，子区段失效位码“0”表示具有0个失效位，“1”表示具有1个失效位。

再者，假设第x个区段中有2个失效位(即Nax+Nbx＝2)，则其前半区段或后半区段中的失效位数目具有三种可能性，即0个失效位、1个失效位及2个失效位。因此，其子区段失效位码的位长度设定为2，并用2个位长度的二进制法来表示前半区段或后半区段中的失效位数目。例如，子区段失效位码“00”表示具有0个失效位，“01”表示具有1个失效位及“10”表示具有2个失效位。同理，假设第x个区段中有3个失效位(即Nax+Nbx＝3)，则其前半区段或后半区段中的失效位数目具有四种可能性，即0个失效位、1个失效位、2个失效位及3个失效位。因此，其子区段失效位码的位长度亦设定为2，并用2个位长度的二进制法来表示前半区段或后半区段中的失效位数目。例如，子区段失效位码“00”表示具有0个失效位，“01”表示具有1个失效位，“10”表示具有2个失效位及“11”表示具有3个失效位。以此类推。

再者，请参照图6，其示出了利用本发明第二实施例所完成的故障地址示意图。其中，将一个页的容量区分为多个区段(segment)，例如，假设一个页的容量为141,311Bits，且设定每64(＝26)个位为一个区段。因此，一个页共可区分为2,208(141,312/64)个区段。再者，每一个区段再区分为二个子区段，亦即，前32位的前半区段与后32位的后半区段。而利用5个位长度的地址即可表示二个子区段中的任一个失效位的位置。

根据本发明的第二实施例，每个区段码(segment code)中，是以失效位数目来决定区段起始码，以及子区段失效位码。接着，以五个位为一个故障码(defective code)指示出二个子区段中故障位的位置。举例来说，假设一个区段的失效位数目为M，则该区段码中会有M个故障码。其中，子区段失效位码可为前半区段中的失效位数目或者后半区段中的失效位数目，并以二进制代码(binary code)来表示。以下是以前半区段中的失效位数目来进行说明。

如图6所示，第一个区段Seg1中有三个失效位，其中二个失效位位于前半区段，一个失效位位于后半区段。再者，由于第一个区段Seg1中有三个失效位，子区段失效位码的位长度设定为2，并以2个位长度的二进制法来表示前半区段中的失效位数目。因此，第一区段码即为区段起始码“1110”合并子区段失效位码“10”与三个故障码。亦即“111010[a4:a0][b4:b0][c4:c0]”。其中，区段起始码为“1110”代表第一区段Seg1中有三个失效位；再者，子区段失效位码为二进制代码“10”，亦即2，代表前半区段中有二个失效位，并通过推算可得知，后半区段中有一个失效位。因此，在接续的故障码中，[a4:a0]指示出第一区段Seg1的前半区段中第一个故障位的位置、[b4:b0]指示出第一区段Seg1的前半区段中第二个故障位的位置、[c4:c0]指示出第一区段Seg1的后半区段中第一个故障位的位置。

第二个区段Seg2中有一个失效位，位于后半区段。再者，由于第二个区段Seg2中有一个失效位，子区段失效位码的位长度设定为1，并以1个位长度的二进制法来表示前半区段中的失效位数目。因此，第二区段码即为区段起始码“10”合并子区段失效位码“0”与一个故障码。亦即“100[d4:d0]”。其中，区段起始码为“10”代表第二区段Seg2中有一个失效位；再者，子区段失效位码为二进制代码“0”，亦即0，代表前半区段中有零个失效位，并通过推算可得知，后半区段中有一个失效位。因此，[d4:d0]指示出第二区段Seg1的后半区段中第一个故障位的位置。

第三个区段Seg3中有零个失效位。因此，第三区段码仅有区段起始码，亦即“0”，代表第三个区段Seg3中没有任何失效位。

第四个区段Seg4中有四个失效位，其中二个失效位位于前半区段，二个失效位位于后半区段。再者，由于第四个区段Seg4中有四个失效位，子区段失效位码的位长度设定为3，并以3个位长度的二进制法来表示前半区段中的失效位数目。因此，第四区段码即为区段起始码“11110”合并子区段失效位码“010”与三个故障码。亦即“11110010[e4:e0][f4:f0][g4:g0][h4:h0]”。其中，区段起始码为“11110”代表第四区段Seg4中有四个失效位；再者，子区段失效位码为二进制代码“010”，亦即2，代表前半区段中有二个失效位，并通过推算可得知，后半区段中有二个失效位。因此，在接续的故障码中，[e4:e0]指示出第四区段Seg4的前半区段中第一个故障位的位置、[f4:f0]指示出第四区段Seg4的前半区段中第二个故障位的位置、[g4:g0]指示出第四区段Seg4的后半区段中第一个故障位的位置、[h4:h0]指示出第四区段Seg4的后半区段中第二个故障位的位置。

利用相同的方式来进行所有区段码的编码。因此第2,207个区段Seg2207中有零个失效位。所以第2,207区段码仅有区段起始码，亦即“0”，代表第2,207个区段Seg2207中没有任何失效位。

第2,208个区段Seg2208中有二个失效位，其中一个失效位位于前半区段，一个失效位位于后半区段。因此，第2,208区段码即为区段起始码“110”合并子区段失效位码“01”与二个故障码。亦即“11001[i4:i0][j4:j0]”。其中，区段起始码为“110”代表第2,208区段Seg2208中有二个失效位；再者，子区段失效位码为二进制代码“01”，亦即1，代表前半区段中有一个失效位，并通过推算可得知，后半区段中有一个失效位。因此，在接续的故障码中，[i4:i0]指示出第2,208区段Seg2208的前半区段中第一个故障位的位置、[j4:j0]指示出第2,208区段Seg2208的后半区段中第一个故障位的位置。

接着，将所有2,208个区段码结合之后即完成上述一个页的故障地址的编码。其编码完成后的故障地址为：“111010[a4:a0][b4:b0][c4:c0]100[d4:d0]011110010[e4:e0][f4:f0][g4:g0][h4:h0]……011001[i4:i0][j4:j0]”。

第二实施例通过将每一个区段再区分为二个子区段以减少纪录失效位的位置所需的位长度，亦即减少故障码的位数，进而缩短整体故障地址的编码长度。比较图4与图6的二实施例后可知，第二实施例故障地址的编码方法可用更少的数据量来记录相同的故障位。举例来说，第二实施例中的第一区段码共计21位，而第一实施例中的第一区段码共计22位，亦即第二实施例节省了1个位。其差异在于，第二实施例中，第一区段码中的故障码少了三个位，而子区段失效位码多了二个位，因此可节省一个位。同理，第二实施例中的第四区段码共计28位，而第一实施例中的第一区段码共计29位，亦即第二实施例节省了1个位。其差异在于，第二实施例中，第四区段码中的故障码少了四个位，而子区段失效位码多了三个位，因此可节省一个位。

请参照图7，其示出了第二实施例中区段内的失效位数目与子区段失效位码的位长度及区段码所节省的位数目的示意图。如图所示，当区段中失效位数目为1时，子区段失效位码的位长度为1，因此区段码中节省的位数目为零。当区段中失效位数目为2时，子区段失效位码的位长度为2，因此区段码中节省的位数目为零。再者，当区段中失效位数目为3时，子区段失效位码的位长度为2，因此区段码中节省的位数目为1。换言之，当区段中失效位数目大于3时，都可以产生的位数较少的区段码。经由统计，利用第二实施例所公开的故障地址编码方法，每一页的故障地址相较于第一实施例，大约可以减少180位，即大约减少1.5％。换言之，在具有约1％的损坏率的状况下，根据第二实施例的公开的故障地址编码方法，每一页的故障地址大约为11,926位。

换言之，在相同的情况下，利用本发明第二实施例所公开的故障地址的编码方法可以利用更少的数据量来记录相同数目的故障位。

综上所述，虽然本发明已以较佳实施例公开如上，然其并非用以限定本发明。本领域技术人员，在不脱离本发明的精神和范围内，可作各种更改与修饰。因此，本发明的保护范围是以本发明的权利要求为准。