TWI665678B

TWI665678B - 編碼器及相關的編碼方法與快閃記憶體控制器

Info

Publication number: TWI665678B
Application number: TW107135826A
Authority: TW
Inventors: 郭軒豪
Original assignee: 慧榮科技股份有限公司
Priority date: 2017-11-27
Filing date: 2017-11-27
Publication date: 2019-07-11
Also published as: TW201926354A

Abstract

一種編碼方法包含有：將多個資料區塊進行處理以產生多個局部校驗碼區塊，其中該多個局部校驗碼區塊包含了一第一部分及一第二部分；使用一第一計算電路以根據該第二部分以產生一第一計算結果；根據該第一計算結果來調整該多個局部校驗碼區塊的該第一部分；對該調整後第一部分進行循環卷積操作，以產生一第一部分的校驗碼區塊；以及使用一第二計算電路以至少根據該第一部分的校驗碼區塊來產生一第二部分的校驗碼區塊；其中該第一部分的校驗碼區塊及該第二部分的校驗碼區塊係作為對該多個資料區塊進行編碼後所產生之多個校驗碼區塊。

Description

編碼器及相關的編碼方法與快閃記憶體控制器

本發明係有關於編碼器，尤指一種應用在快閃記憶體控制器中的編碼器。

在一般的編碼器中，會具有一個校驗碼檢查矩陣(parity-check matrix)，以供編碼器檢查所產生出來的校驗碼是否正確。舉例來說，編碼器在對資料進行編碼以產生校驗碼之後，會將資料與校驗碼和此校驗碼檢查矩陣進行相乘，而若是相乘結果等於“0”則判斷編碼正確；而若是相乘結果不等於“0”則判斷編碼錯誤。因應此校驗碼檢查矩陣，編碼器會具有一相對應的校驗碼產生矩陣以供產生適合的校驗碼，然而，在某些情況下，校驗碼產生矩陣可能無法被找到，因此編碼器會需要進行多個矩陣乘法操作及/或補償/調整操作，以產生類似使用校驗碼產生矩陣所產生的校驗碼，因此會增加編碼器的複雜度。特別地，上述多個矩陣乘法操作通常會包含循環卷積(circulant convolution)計算，因此更會大幅增加編碼器的硬體成本。

因此，本發明的目的之一在於提出一種編碼器，其可以降低編碼器中的循環卷積計算所需要的硬體，以避免先前技術中所述之硬體成本大幅增加的情形。

在本發明的一個實施例中，揭露了一種編碼器，其包含有一第一桶式移位器模組、一第一計算電路、一調整電路、一第一循環卷積計算電路以及一第二計算電路。該第一桶式移位器模組用以將多個資料區塊進行處理以產生多個局部校驗碼區塊，其中該多個局部校驗碼區塊包含了一第一部分及一第二部分；該第一計算電路耦接於該第一桶式移位器模組，且用以根據該第二部分以產生一第一計算結果；該調整電路用以根據該第一計算結果來調整該多個局部校驗碼區塊的該第一部分，以產生一調整後第一部分；該第一循環卷積計算電路耦接於該調整電路，且用以對該調整後第一部分進行循環卷積操作，以產生一第一部分的校驗碼區塊；以及該第二計算電路耦接於該第一循環卷積計算電路，且用以至少根據該第一部分的校驗碼區塊以產生一第二部分的校驗碼區塊；其中該第一部分的校驗碼區塊及該第二部分的校驗碼區塊係作為該編碼器針對該多個資料區塊所產生之多個校驗碼區塊。

在本發明的另一個實施例中，揭露了一種快閃記憶體控制器，其中該快閃記憶體控制器係用來存取一快閃記憶體模組，且該快閃記憶體控制器包含有一記憶體、一微處理器以及一編碼器，其中該記憶體用來儲存一程式碼；該微處理器用來執行該程式碼以控制對該快閃記憶體模組之存取；且該編碼器用以對該多個資料區塊進行編碼以得到多個校驗碼區塊。此外，該編碼器包含有一第一桶式移位器模組、一第一計算電路、一調整電路、一第一循環卷積計算電路以及一第二計算電路。該第一桶式移位器模組用以將多個資料區塊進行處理以產生多個局部校驗碼區塊，其中該多個局部校驗碼區塊包含了一第一部分及一第二部分；該第一計算電路耦接於該第一桶式移位器模組，且用以根據該第二部分以產生一第一計算結果；該調整電路用以根據該第一計算結果來調整該多個局部校驗碼區塊的該第一部分，以產生一調整後第一部分；該第一循環卷積計算電路耦接於該調整電路，且用以對該調整後第一部分進行循環卷積操作，以產生一第一部分的校驗碼區塊；以及該第二計算電路耦接於該第一循環卷積計算電路，且用以至少根據該第一部分的校驗碼區塊以產生一第二部分的校驗碼區塊；其中該第一部分的校驗碼區塊及該第二部分的校驗碼區塊係作為該編碼器針對該多個資料區塊所產生之多個校驗碼區塊。

在本發明的另一個實施例中，揭露了一種編碼方法，其包含有：將多個資料區塊進行處理以產生多個局部校驗碼區塊，其中該多個局部校驗碼區塊包含了一第一部分及一第二部分；使用一第一計算電路以根據該第二部分以產生一第一計算結果；根據該第一計算結果來調整該多個局部校驗碼區塊的該第一部分；對該調整後第一部分進行循環卷積操作，以產生一第一部分的校驗碼區塊；以及使用一第二計算電路以至少根據該第一部分的校驗碼區塊來產生一第二部分的校驗碼區塊；其中該第一部分的校驗碼區塊及該第二部分的校驗碼區塊係作為對該多個資料區塊進行編碼後所產生之多個校驗碼區塊。

在本發明的另一個實施例中，揭露了一種編碼器，其包含有一桶式移位器模組、一調整電路、一循環卷積計算電路以及一計算電路。該桶式移位器模組用以將多個資料區塊進行處理以產生多個局部校驗碼區塊，其中該多個局部校驗碼區塊包含了一第一部分及一第二部分；該調整電路用以根據該第二部分來調整該多個局部校驗碼區塊的該第一部分，以產生一調整後第一部分；該循環卷積計算電路耦接於該調整電路，且用以對該調整後第一部分進行循環卷積操作，以產生一第一部分的校驗碼區塊；以及該計算電路耦接於該循環卷積計算電路，且用以至少根據該第一部分的校驗碼區塊以產生一第二部分的校驗碼區塊；其中該第一部分的校驗碼區塊及該第二部分的校驗碼區塊係作為該編碼器針對該多個資料區塊所產生之多個校驗碼區塊。

請參考第1圖，第1圖為依據本發明一實施例之一種記憶裝置100的示意圖。記憶裝置100包含有一快閃記憶體（Flash Memory）模組120以及一快閃記憶體控制器110，且快閃記憶體控制器110用來存取快閃記憶體模組120。依據本實施例，快閃記憶體控制器110包含一微處理器112、一唯讀記憶體（Read Only Memory, ROM）112M、一控制邏輯114、一緩衝記憶體116、與一介面邏輯118。唯讀記憶體112M係用來儲存一程式碼112C，而微處理器112則用來執行程式碼112C以控制對快閃記憶體模組120之存取（Access）。控制邏輯114包含了一編碼器132以及一解碼器134，其中編碼器132用來對寫入到快閃記憶體模組120中的資料進行編碼以產生對應的校驗碼(或稱，錯誤更正碼(Error Correction Code)，ECC)，而解碼器134用來將從快閃記憶體模組120所讀出的資料進行解碼。

於典型狀況下，快閃記憶體模組120包含了多個快閃記憶體晶片，而每一個快閃記憶體晶片包含複數個區塊（Block），而該控制器（例如：透過微處理器112執行程式碼112C之快閃記憶體控制器110）對快閃記憶體模組120進行複製、抹除、合併資料等運作係以區塊為單位來進行複製、抹除、合併資料。另外，一區塊可記錄特定數量的資料頁（Page），其中該控制器（例如：透過微處理器112執行程式碼112C之記憶體控制器110）對快閃記憶體模組120進行寫入資料之運作係以資料頁為單位來進行寫入。

實作上，透過微處理器112執行程式碼112C之快閃記憶體控制器110可利用其本身內部之元件來進行諸多控制運作，例如：利用控制邏輯114來控制快閃記憶體模組120之存取運作（尤其是對至少一區塊或至少一資料頁之存取運作）、利用緩衝記憶體116進行所需之緩衝處理、以及利用介面邏輯118來與一主裝置（Host Device）130溝通。

在一實施例中，記憶裝置100可以是可攜式記憶裝置（例如：符合SD/MMC、CF、MS、XD標準之記憶卡），且主裝置130為一可與記憶裝置連接的電子裝置，例如手機、筆記型電腦、桌上型電腦…等等。而在另一實施例中，記憶裝置100可以設置在一電子裝置中，例如設置在手機、筆記型電腦、桌上型電腦之中，而此時主裝置130可以是該電子裝置的一處理器。

在本實施例中，編碼器132為一低密度奇偶檢查碼（Low-Density Parity Check code，LDPC code）編碼器，且可以根據來自主裝置130的資料來產生對應的校驗碼，且所產生的校驗碼符合一校驗碼檢查矩陣。具體來說，參考第2圖，假設該校驗碼檢查矩陣為一大小為c*t的矩陣(例如，c=5，t=48)，而該校驗碼檢查矩陣可以分為左側的矩陣M(大小為c*(t-c))以及右側的矩陣K(大小為c*c)，為了找出與該校驗碼檢查矩陣所對應的校驗碼產生矩陣，可以先找出矩陣K的反矩陣K ^-1(inverse matrix)，之後再將反矩陣(K ^-1)與矩陣M相乘以得到矩陣P，而矩陣P的轉置矩陣(transpose matrix)便可以作為校驗碼產生矩陣。換句話說，在找到矩陣P的轉置矩陣之後，編碼器132可以將來自主裝置130的資料乘以矩陣P的轉置矩陣來得到對應於該些資料的校驗碼，而編碼器之後再將資料與校驗碼一起乘上該校驗碼檢查矩陣以判斷校驗碼是否正確。舉例來說，若是相乘結果等於“0”則判斷編碼正確；而若是相乘結果不等於“0”則判斷編碼錯誤。在判斷編碼正確之後，資料與對應的校驗碼便會被寫入至快閃記憶體模組120中的一個資料頁中。

然而，在某些情況下，反矩陣K ^-1可能無法被輕易找到，因此編碼器132會需要進行多個矩陣乘法操作及/或補償/調整操作來得到一個類似反矩陣K ^-1的內容，以供找出校驗碼產生矩陣來產生校驗碼。本發明因此提出了一種電路架構，以使得編碼器132可以在盡可能節省硬體成本的情形下完成編碼器132的操作。需注意的是，編碼器132中有關於編碼的過程涉及許多複雜的數學運算，但由於本發明的重點是在於電路架構的設計，故相關的矩陣內容及推導過程的細節在此不予贅述。

參考第3圖，其為根據本發明一實施例之編碼器300的示意圖，其中編碼器300可以作為第1圖所示之編碼器132。如第3圖所示，編碼器300包含了一桶式移位器模組310、一第一計算電路320、一調整電路330、一循環卷積(circulant convolution)計算電路340、一補償電路342以及一第二計算電路350。在本實施例中，桶式移位器模組310包含了多個桶式移位器311、312、313、314、315以及多個累加電路317_1~317_5；第一計算電路320包含了一循環卷積計算電路322、一補償電路324以及一桶式移位器模組326；調整電路330包含了多個累加電路332、334、336；以及第二計算電路350包含了一桶式移位器模組352、一循環卷積計算電路354、一補償電路356、一包含兩個累加電路357、358的輸出電路。在本實施例中，編碼器300係將來自主裝置130的一筆資料分為多個資料區塊(在本實施例中該多個資料區塊為43個資料區塊DB_1~DB_43)，並將該多個資料區塊DB_1~DB_43進行編碼後產生多個校驗碼區塊(在本實施例中該多個校驗碼區塊為5個校驗碼區塊PB_1~PB_5)。需注意的是，上述之一個資料區塊與一個校驗碼區塊的大小是相同的，且資料區塊的大小可以由設計者所自行決定，例如192*192個位元。

在編碼器300的操作中，首先，桶式移位器模組310將資料區塊DB_1~DB_43進行處理以產生多個局部校驗碼(partial parity)區塊PPB_1~PPB_5。具體來說，桶式移位器311可以分別對資料區塊DB_1~DB_43進行移位操作，並透過累加電路317_1來將43個移位後資料區塊進行相加來得到局部校驗碼區塊PPB_1；桶式移位器312可以分別對資料區塊DB_1~DB_43進行移位操作，並透過累加電路317_2來將43個移位後資料區塊進行相加來得到局部校驗碼區塊PPB_2；類似地，桶式移位器313、314、315可以分別對資料區塊DB_1~DB_43進行移位操作，並透過累加電路317_3、317_4、317_5來將43個移位後資料區塊進行相加來分別得到局部校驗碼區塊PPB_3、PPB_4、PPB_5。

局部校驗碼區塊PPB_1~PPB_5會被分兩個部分以進行不同的處理，其中第一部分包含了三個局部校驗碼區塊PPB_1~PPB_3，而第二部分包含了兩個局部校驗碼區塊PPB_4~PPB_5。在第一計算電路320的操作中，循環卷積計算電路322將局部校驗碼區塊PPB_4~PPB_5進行循環卷積操作以產生兩個中間區塊；補償電路324係為一可移除(optional)的元件，且用來補償循環卷積計算電路322所輸出的兩個中間區塊；桶式移位器模組326用以對該兩個中間區塊進行處理以產生三個計算結果區塊。在本實施例中，由於桶式移位器模組326係根據兩個中間區塊來產生三個計算結果區塊，故桶式移位器模組326可以包含6個桶式移位器(2*3=6)。

調整電路330中的累加電路332、334、336將桶式移位器模組326所產生的三個計算結果區塊分別與局部校驗碼區塊PPB_1~PPB_3進行相加，以產生調整後的局部校驗碼區塊。

接著，循環卷積計算電路340對調整後之第一部分的局部校驗碼區塊(即PPB_1~PPB_3)進行循環卷積操作，並透過補償電路342以產生校驗碼區塊PB_1~PB_3。需注意的是，補償電路342為一可移除的元件，亦即在不需要補償的情形下可以自編碼器300中移除而不會影響到其操作。

接著，在第二計算電路350的操作中，桶式移位器模組352對校驗碼區塊PB_1~PB_3進行處理以產生兩個處理後區塊；循環卷積計算電路354將兩個處理後區塊進行循環卷積操作以產生兩個輸出區塊；補償電路356係為一可移除的元件，且用來補償循環卷積計算電路354所輸出的兩個輸出區塊；累加電路357、357分別將循環卷積計算電路322或是補償電路324所產生的中間區塊與循環卷積計算電路354或是補償電路356所產生的兩個輸出區塊進行相加，以產生校驗碼區塊PB_4~PB_5。在本實施例中，由於桶式移位器模組352係根據三個校驗碼區塊PB_1~PB_3來產生兩個處理後區塊，故桶式移位器模組352可以包含6個桶式移位器(3*2=6)

在產生校驗碼區塊PB_1~PB_5之後，編碼器會將資料區塊DB_1~DB_43連同校驗碼區塊PB_1~PB_5一起與校驗碼檢查矩陣相乘以判斷校驗碼區塊PB_1~PB_5是否正確。若是正確，快閃記憶體控制器110便會將資料區塊DB_1~DB_43連同校驗碼區塊PB_1~PB_5一起寫入到快閃記憶體模組120的一區塊的一資料頁中。

在第3圖所示的電路架構中，桶式移位器模組310可以被比對為第2圖所示之矩陣M，而第一計算電路320、調整電路330、循環卷積計算電路340、補償電路342以及第二計算電路350則是用來產生一個類似於第2圖所示之反矩陣K ^-1的內容，以在無法確實找到反矩陣K ^-1的情形下可以產生校驗碼區塊PB_1~PB_5。此外，編碼器300具有三個循環卷積計算電路322、340、354，其中循環卷積計算電路322為2*2個循環矩陣/區塊相乘，循環卷積計算電路340為3*3個循環矩陣/區塊相乘，以及循環卷積計算電路354為2*2個循環矩陣/區塊相乘，因此總和來說編碼器300的循環矩陣/區塊相乘的次數為17次(4+9+4=17)。因此，由於編碼器300只需進行17次循環矩陣/區塊相乘操作便可以產生五個校驗碼區塊，故可以確實降低編碼器300的硬體成本。

參考第4圖，其為根據本發明另一實施例之編碼器400的示意圖，其中編碼器400可以作為第1圖所示之編碼器132。如第4圖所示，編碼器400包含了一桶式移位器模組410、一第一計算電路420、一調整電路430、一循環卷積計算電路440、一補償電路442以及一第二計算電路450。在本實施例中，桶式移位器模組410包含了多個桶式移位器411、412、413、414、415以及多個累加電路417_1~417_5；第一計算電路420兩個桶式移位器模組422、424；調整電路430包含了多個累加電路432、434、436、438；以及第二計算電路350包含了一桶式移位器模組452以及一輸出電路424。在本實施例中，編碼器400係將來自主裝置130的一筆資料分為多個資料區塊(在本實施例中該多個資料區塊為43個資料區塊DB_1~DB_43)，並將該多個資料區塊DB_1~DB_43進行編碼後產生多個校驗碼區塊(在本實施例中該多個校驗碼區塊為5個校驗碼區塊PB_1~PB_5)。需注意的是，上述之一個資料區塊與一個校驗碼區塊的大小是相同的，且資料區塊的大小可以由設計者所自行決定，例如192*192個位元。

在編碼器400的操作中，首先，桶式移位器模組410將資料區塊DB_1~DB_43進行處理以產生多個局部校驗碼(partial parity)區塊PPB_1~PPB_5。具體來說，桶式移位器411可以分別對資料區塊DB_1~DB_43進行移位操作，並透過累加電路417_1來將43個移位後資料區塊進行相加來得到局部校驗碼區塊PPB_1；桶式移位器412可以分別對資料區塊DB_1~DB_43進行移位操作，並透過累加電路417_2來將43個移位後資料區塊進行相加來得到局部校驗碼區塊PPB_2；類似地，桶式移位器413、414、415可以分別對資料區塊DB_1~DB_43進行移位操作，並透過累加電路417_3、417_4、417_5來將43個移位後資料區塊進行相加來分別得到局部校驗碼區塊PPB_3、PPB_4、PPB_5。

局部校驗碼區塊PPB_1~PPB_5會被分兩個部分以進行不同的處理，其中第一部分包含了四個局部校驗碼區塊PPB_1~PPB_4，而第二部分包含了一個局部校驗碼區塊PPB_5。在第一計算電路420的操作中，桶式移位器模組422對局部校驗碼區塊PPB_5進行移位操作以產生一中間區塊，且桶式移位器模組424對該中間區塊進行處理以產生四個計算結果區塊。

調整電路430中的累加電路432、434、436、438將桶式移位器模組424所產生的四個計算結果區塊分別與局部校驗碼區塊PPB_1~PPB_4進行相加，以產生調整後的局部校驗碼區塊。

接著，循環卷積計算電路440對調整後之第一部分的局部校驗碼區塊(即PPB_1~PPB_4)進行循環卷積操作，並透過補償電路442以產生校驗碼區塊PB_1~PB_4。需注意的是，補償電路442為一可移除的元件，亦即在不需要補償的情形下可以自編碼器400中移除而不會影響到其操作。

接著，在第二計算電路450的操作中，桶式移位器模組452對校驗碼區塊PB_1~PB_4進行處理以產生一個處理後區塊；輸出電路454將桶式移位器模組422所產生的中間區塊與桶式移位器模組452所產生的輸出區塊進行相加，以產生校驗碼區塊PB_5。

在第4圖所示的電路架構中，桶式移位器模組410可以被比對為第2圖所示之矩陣M，而第一計算電路420、調整電路430、循環卷積計算電路440、補償電路442以及第二計算電路450則是用來產生一個類似於第2圖所示之反矩陣K ^-1的內容，以在無法確實找到反矩陣K ^-1的情形下可以產生校驗碼區塊PB_1~PB_5。此外，編碼器400僅具有一個循環卷積計算電路440，其中循環卷積計算電路440為4*4個循環矩陣/區塊相乘。因此，由於編碼器400只需進行16次循環矩陣/區塊相乘操作便可以產生五個校驗碼區塊，故可以確實降低編碼器400的硬體成本。

另一方面，若是校驗碼檢查矩陣中的矩陣K具有某一種特定的型式，例如矩陣K的最後一行與最後一列的數值均為“0”時，第4圖所示的編碼器400中的元件可以進一步地減少，例如以下所述之第5圖所示的實施例。

參考第5圖，其為根據本發明另一實施例之編碼器500的示意圖，其中編碼器500可以作為第1圖所示之編碼器132。如第5圖所示，編碼器500包含了一桶式移位器模組510、一調整電路530、一循環卷積計算電路540、一補償電路542以及一計算電路550。在本實施例中，桶式移位器模組510包含了多個桶式移位器511、512、513、514、515以及多個累加電路517_1~517_5。在本實施例中，編碼器500係將來自主裝置130的一筆資料分為多個資料區塊(在本實施例中該多個資料區塊為43個資料區塊DB_1~DB_43)，並將該多個資料區塊DB_1~DB_43進行編碼後產生多個校驗碼區塊(在本實施例中該多個校驗碼區塊為5個校驗碼區塊PB_1~PB_5)。需注意的是，上述之一個資料區塊與一個校驗碼區塊的大小是相同的，且資料區塊的大小可以由設計者所自行決定，例如192*192個位元。

在編碼器500的操作中，首先，桶式移位器模組510將資料區塊DB_1~DB_43進行處理以產生多個局部校驗碼(partial parity)區塊PPB_1~PPB_5。具體來說，桶式移位器511可以分別對資料區塊DB_1~DB_43進行移位操作，並透過累加電路517_1來將43個移位後資料區塊進行相加來得到局部校驗碼區塊PPB_1；桶式移位器512可以分別對資料區塊DB_1~DB_43進行移位操作，並透過累加電路517_2來將43個移位後資料區塊進行相加來得到局部校驗碼區塊PPB_2；類似地，桶式移位器513、514、515可以分別對資料區塊DB_1~DB_43進行移位操作，並透過累加電路517_3、517_4、517_5來將43個移位後資料區塊進行相加來分別得到局部校驗碼區塊PPB_3、PPB_4、PPB_5。

局部校驗碼區塊PPB_1~PPB_5會被分兩個部分以進行不同的處理，其中第一部分包含了四個局部校驗碼區塊PPB_1~PPB_4，而第二部分包含了一個局部校驗碼區塊PPB_5。調整電路530中的累加電路532、534、536、538分別將局部校驗碼區塊PPB_5的內容加入到局部校驗碼區塊PPB_1~PPB_4中，以產生調整後的局部校驗碼區塊。

接著，循環卷積計算電路540對調整後之第一部分的局部校驗碼區塊(即PPB_1~PPB_4)進行循環卷積操作，並透過補償電路542以產生校驗碼區塊PB_1~PB_4。需注意的是，補償電路542為一可移除的元件，亦即在不需要補償的情形下可以自編碼器500中移除而不會影響到其操作。

接著，計算電路550將局部校驗碼區塊PPB_5與校驗碼區塊PB_1~PB_4進行相加，以產生校驗碼區塊PB_5。

在第5圖所示的電路架構中，桶式移位器模組510可以被比對為第2圖所示之矩陣M，而調整電路530、循環卷積計算電路540、補償電路542以及計算電路550則是用來產生一個類似於第2圖所示之反矩陣K ^-1的內容，以在無法確實找到反矩陣K ^-1的情形下可以產生校驗碼區塊PB_1~PB_5。此外，編碼器500僅具有一個循環卷積計算電路540，其中循環卷積計算電路540為4*4個循環矩陣/區塊相乘。因此，由於編碼器500只需進行16次循環矩陣/區塊相乘操作便可以產生五個校驗碼區塊，故可以確實降低編碼器500的硬體成本。另一方面，相較於第4圖的實施例，由於少了第一計算電路420以及第二計算電路450中的部分元件，故可以進一步地降低成本。

參考第6圖，其為根據本發明一實施例之一種編碼方法的流程圖，同時參考第1~6圖及以上實施例所揭露的內容，編碼方法的流程如下所述。

步驟600：流程開始。

步驟602：將多個資料區塊進行處理以產生多個局部校驗碼區塊，其中該多個局部校驗碼區塊包含了一第一部分及一第二部分。

步驟604：使用一第一計算電路以根據該第二部分以產生一第一計算結果。

步驟606：根據該第一計算結果來調整該多個局部校驗碼區塊的該第一部分，以產生一調整後第一部分。

步驟608：對該調整後第一部分進行循環卷積操作，以產生一第一部分的校驗碼區塊。

步驟610：使用一第二計算電路以至少根據該第一部分的校驗碼區塊來產生一第二部分的校驗碼區塊，其中該第一部分的校驗碼區塊及該第二部分的校驗碼區塊係作為對該多個資料區塊進行編碼後所產生之多個校驗碼區塊。

簡要歸納本發明，在本發明之編碼器中，其透過將局部校驗碼區塊分為兩個部分來進行操作，以在可以確實產生校驗碼區塊的情形下降低編碼器中的循環卷積計算所需要的硬體。因此，本發明之編碼器可以避免先前技術中所述之硬體成本大幅增加的情形。以上所述僅為本發明之較佳實施例，凡依本發明申請專利範圍所做之均等變化與修飾，皆應屬本發明之涵蓋範圍。

100	記憶裝置
110	快閃記憶體控制器
112	微處理器
112C	程式碼
112M	唯讀記憶體
114	控制邏輯
116	緩衝記憶體
118	介面邏輯
120	快閃記憶體模組
130	主裝置
132、300、400、500	編碼器
134	解碼器
310、326、352、410、422、424、452、510	桶式移位器模組
311、312、313、314、315、411、412、413、414、415、511、512、513、514、515	桶式移位器
317_1~317_5、332、334、336、357、358、417_1~417_5、432、434、436、438、517_1~517_5、532、534、536、538	累加電路
320、420	第一計算電路
322、340、354、440、540	循環卷積計算電路
324、342、356、442、542	補償電路
330、430、530	調整電路
350、450	第二計算電路
454	輸出電路
550	計算電路
600~610	步驟
DB_1~DB_43	資料區塊
PPB_1~PPB_5	局部校驗碼區塊
PB_1~PB_5	校驗碼區塊

第1圖為依據本發明一實施例之一種記憶裝置的示意圖。第2圖為校驗碼檢查矩陣及校驗碼產生矩陣的示意圖。第3圖為根據本發明一實施例之編碼器的示意圖。第4圖為根據本發明另一實施例之編碼器的示意圖。第5圖為根據本發明另一實施例之編碼器的示意圖。第6圖為根據本發明一實施例之一種編碼方法的流程圖。

Claims

一種設置在一快閃記憶體控制器中的編碼器，包含有：一第一桶式移位器模組，用以將多個資料區塊進行處理以產生多個局部校驗碼(partial parity)區塊，其中該多個局部校驗碼區塊包含了一第一部分及一第二部分；一第一計算電路，耦接於該第一桶式移位器模組，用以根據該第二部分以產生一第一計算結果；一第一輸出電路，用以根據該第一部分以及該第一計算結果以產生一第一部分的校驗碼區塊；以及一第二計算電路，耦接於該第一循環卷積計算電路，用以至少根據該第一部分的校驗碼區塊以產生一第二部分的校驗碼區塊；其中該第一部分的校驗碼區塊及該第二部分的校驗碼區塊係作為該編碼器針對該多個資料區塊所產生之多個校驗碼區塊，且該多個資料區塊以及該多個校驗碼區塊係被寫入至一快閃記憶體中。
如申請專利範圍第1項所述之編碼器，其中該第二部分包含了至少兩個局部校驗碼區塊，且該第一計算電路與該第二計算電路均包含了循環卷積操作。
如申請專利範圍第2項所述之編碼器，其中該第一部分包含了C1個局部校驗碼區塊，該第二部分包含了C2個局部校驗碼區塊，且該第一計算電路包含有：一第二循環卷積計算電路，用以將C2個局部校驗碼區塊進行循環卷積操作以產生C2個中間區塊；以及一第二桶式移位器模組，耦接於該第二循環卷積計算電路，用以對該C2個中間區塊進行處理以產生C1個計算結果區塊以作為該第一計算結果；其中該第一輸出電路根據該C1個計算結果區塊與該C1個局部校驗碼區塊以產生該第一部分的校驗碼區塊。
如申請專利範圍第3項所述之編碼器，其中該第一部分的校驗碼區塊包含了C1個校驗碼區塊，且該第二計算電路包含有：一第三桶式移位器模組，用以對該C1個校驗碼區塊進行處理以產生C2個處理後區塊；一第三循環卷積計算電路，耦接於該第三桶式移位器模組，用以將C2個處理後區塊進行循環卷積操作以產生C2個輸出區塊；一第二輸出電路，耦接於該第三循環卷積計算電路，用以根據該C2個中間區塊來調整該C2個輸出區塊，以產生C2個校驗碼區塊來作為該第二部分的校驗碼區塊。
如申請專利範圍第1項所述之編碼器，其中該第一計算電路以及該第二計算電路均不包含任何的循環卷積操作。
如申請專利範圍第5項所述之編碼器，其中該第一部分包含了C1個局部校驗碼區塊，該第二部分包含了C2個局部校驗碼區塊，C2等於1，且該第一計算電路包含有：一第二桶式移位器模組，用以對該C2個局部校驗碼區塊進行處理以產生C1個計算結果區塊以作為該第一計算結果；其中該第一輸出電路根據該C1個計算結果區塊以及該C1個局部校驗碼區塊以產生該第一部分的校驗碼區塊。
如申請專利範圍第6項所述之編碼器，其中該第一部分的校驗碼區塊包含了C1個校驗碼區塊，且該第二計算電路包含有：一第三桶式移位器模組，用以對該C1個校驗碼區塊進行處理以產生C2個處理後區塊；一第二輸出電路，耦接於該第三桶式移位器模組，用以根據該C2個中間區塊來調整該C2個輸出區塊，以產生C2個校驗碼區塊來作為該第二部分的校驗碼區塊。
如申請專利範圍第1項所述之編碼器，其為在該快閃記憶體控制器中的一低密度奇偶檢查碼（Low-Density Parity Check code，LDPC code）編碼電路。
一種快閃記憶體控制器，該快閃記憶體控制器係用來存取一快閃記憶體模組，且該快閃記憶體控制器包含有：一記憶體，用來儲存一程式碼；一微處理器，用來執行該程式碼以控制對該快閃記憶體模組之存取；以及一編碼器，用以對多個資料區塊進行編碼以得到多個校驗碼區塊，其中該編碼器包含有：一第一桶式移位器模組，用以將該多個資料區塊進行處理以產生多個局部校驗碼(partial parity)區塊，其中該多個局部校驗碼區塊包含了一第一部分及一第二部分；一第一計算電路，耦接於該第一桶式移位器模組，用以根據該第二部分以產生一第一計算結果；一輸出電路，用以根據該第一部分以及該第一計算結果以產生一第一部分的校驗碼區塊；以及一第二計算電路，耦接於該第一循環卷積計算電路，用以至少根據該第一部分的校驗碼區塊以產生一第二部分的校驗碼區塊；其中該第一部分的校驗碼區塊及該第二部分的校驗碼區塊係作為該編碼器針對該多個資料區塊所產生之多個校驗碼區塊。
如申請專利範圍第9項所述之快閃記憶體控制器，其中該第二部分包含了至少兩個局部校驗碼區塊，且該第一計算電路與該第二計算電路均包含了循環卷積操作。