TWI520501B - 記憶體控制器 - Google Patents

Description

記憶體控制器

本發明是有關於一種電子電路，且特別是有關於一種記憶體控制器。

隨著資料存取技術的發展，錯誤更正碼對於資料存取時的完整性與合法性具有極高的重要性。一般來說，使用低密度奇偶校驗碼(Low Density Parity Check Code,LDPC)技術來對欲傳輸的資料進行編/解碼並提供錯誤更正碼的方式已普遍應用於通訊領域。

然而，對於將LDPC的編/解碼技術應用於記憶體的資料存取方面，卻始終沒有可同時兼顧資料存取效率與節省硬體體積的技術方案。

有鑑於此，本發明提供一種記憶體控制器，可減少所需的記憶體的電路面積，並提升編碼與解碼效率。

本發明提出一種記憶體控制器，此記憶體控制器包括記憶體介面及編碼器模組。記憶體介面用以連接記憶體晶片。編碼器模組耦接至記憶體介面，此編碼器模組包括共享記憶體以及奇偶產生器模組。奇偶產生器模組耦接共享記憶體，用以自共享記憶體中讀取至少一基準向量，決定至少一基準向量的維度。該奇偶產生器模組根據決定維度後的基準向量產生生成矩陣(generation matrix)，並透過生成矩陣將原始資料轉換為碼字，並透過該記憶體介面儲存碼字至記憶體晶片。

本發明另提出一種記憶體控制器，此記憶體控制器包括記憶體介面及解碼器模組。記憶體介面用以連接記憶體晶片。解碼器模組耦接至記憶體介面，此解碼器模組包括內部記憶體、位元節點處理器以及校驗模組。內部記憶體用以儲存來自記憶體介面的碼字對應的一決策比矩陣。位元節點處理器耦接內部記憶體，用以自內部記憶體讀取決策比矩陣。校驗模組耦接內部記憶體與位元節點處理器，用以透過一校驗矩陣對來自位元節點處理器的決策比矩陣進行一疊代運算，以更新儲存於內部記憶體的決策比矩陣，並根據疊代運算的運算結果產生一修正矩陣，其中位元節點處理器更根據修正矩陣修正自內部記憶體讀取之更新後的決策比矩陣，且校驗模組根據修正後的決策比矩陣決定是否重複進行疊代運算，若校驗模組決定不重複進行疊代運算，則校驗模組根據修正後的決策比矩陣產生一已解碼資料。

基於上述，本發明實施例的記憶體控制器中的編碼器模 組可適應性地調整生成矩陣的維度，並且透過使用單一的記憶體來達到節省記憶體的功效。另外，本發明實施例的記憶體控制器中的解碼器模組則可在每一次的疊代運算之後判斷是否需要再次進行另一次的疊代運算，藉此，即使尚未達到預設的疊代次數，只要疊代運算的結果符合使用上的需求，即可終止疊代運算，從而提升解碼效率。

為讓本發明的上述特徵和優點能更明顯易懂，下文特舉實施例，並配合所附圖式作詳細說明如下。

10‧‧‧記憶體控制器

11‧‧‧記憶體晶片

12‧‧‧主機系統

102‧‧‧記憶體介面

104‧‧‧主機介面

106‧‧‧編碼器模組

108‧‧‧解碼器模組

22‧‧‧共享記憶體

24‧‧‧奇偶產生器模組

242_1-242-n‧‧‧奇偶產生器

244‧‧‧整合輸出電路

2442‧‧‧整合電路

2444‧‧‧多工器

32‧‧‧控制電路

322‧‧‧移位控制電路

3222‧‧‧基準向量暫存電路

3224‧‧‧移位多工器

324‧‧‧矩陣暫存電路

34‧‧‧運算電路

342_1-342_p‧‧‧子運算電路

36‧‧‧暫存電路

41‧‧‧多工器

42‧‧‧內部記憶體

44‧‧‧位元節點處理器

46‧‧‧校驗模組

462‧‧‧排列替換處理器

464‧‧‧校驗節點處理器

466‧‧‧決策電路

468‧‧‧早期終止電路

圖1為根據本發明一實施例所繪示的記憶體控制器的示意圖。

圖2為根據本發明一實施例所繪示的編碼器模組的示意圖。

圖3為根據本發明一實施例所繪示的奇偶產生器的示意圖。

圖4為根據本發明一實施例所繪示的解碼器模組的示意圖。

圖1為根據本發明一實施例所繪示的記憶體控制器的示意圖。請參照圖1，記憶體控制器10包括記憶體介面102、主機介面104、編碼器模組106以及解碼器模組108。記憶體介面102連接記憶體晶片11，主機介面104連接主機系統12。記憶體晶片 11可以是任何類型的非揮發性記憶體(non-volatile memory，NVM)，例如快閃記憶體或是其他記憶體或儲存媒體。在其他實施例中，記憶體晶片11可以是任何類型的揮發性記憶體。編碼器模組106的輸出端耦接至記憶體介面102，而編碼器模組106的輸入端耦接至主機介面104，用以執行編碼功能。解碼器模組108的輸入端耦接至記憶體介面102，而解碼器模組108的輸出端耦接至主機介面104，用以執行解碼功能。

舉例來說，當主機系統12欲將一原始資料(raw data)寫入至記憶體晶片11時，主機系統12會先將此原始資料傳送至主機介面104，以透過主機介面104將此原始資料傳送至編碼器模組106。然後，編碼器模組106可對來自主機介面104的原始資料進行編碼，並產生一碼字(codeword)。其中，此碼字包括此原始資料與相關糾錯資訊。接著，記憶體控制器10可透過記憶體介面102將此碼字寫入至記憶體晶片11。此外，當主機系統12欲自記憶體晶片11中讀取一指定資料時，主機系統12可透過主機介面104發送一讀取指令至記憶體控制器10。接著，記憶體控制器10可根據此讀取指令透過記憶體介面102自記憶體晶片11中取出相對應的碼字，並由解碼器模組108對所取出的碼字進行解碼，從而將解碼後的所述指定資料透過主機介面104傳送至主機系統12。

在本實施例中，編碼器模組106與解碼器模組108可同時或擇一設置於記憶體控制器10中。例如，當記憶體控制器10 只需要編碼功能時，記憶體控制器10可以配置編碼器模組106而移除解碼器模組108。在另一實施例中，當記憶體控制器10只需要解碼功能時，記憶體控制器10可以配置解碼器模組108而移除編碼器模組106。而當記憶體控制器10需要兼具編碼與解碼功能時，則記憶體控制器10可以同時包含編碼器模組106與解碼器模組108。

在本實施例中，編碼器模組106與解碼器模組108所提供的編/解碼功能可包括低密度奇偶校驗碼(Low Density Parity Check Code,LDPC)等各種編碼格式的編/解碼功能。舉例來說，編碼器模組106可對欲儲存的原始資料執行如下計算式(1)之運算來產生編碼後的碼字。

v=cG 計算式(1)

其中，c代表來自該主機介面的原始資料，G代表生成矩陣(generation matrix)，v代表編碼後的碼字。特別是，生成矩陣G的行(row)數會等於原始資料c的列(column)數(即，原始資料c的位元數)，以符合計算式(1)的運算規則。舉例來說，假設編碼器模組106一次可處理(即，編碼)的原始資料c之位元數為K位元，則原始資料c可以用1×K矩陣(matrix)表示。生成矩陣G可以用K×L矩陣表示，且K與L均為正整數。此外，由於生成矩陣G的列數為L，表示編碼器模組106產生的碼字v具有L個位元，因此輸出的碼字v可以用1×L矩陣表示。舉例來說，若原始資料c具有3個位元(即，1×3矩陣)，且生成矩陣G 為3×6矩陣，則編碼器模組106可以透過執行計算式(1)的運算來獲得6位元的碼字v(即，1×6矩陣)。也就是說，可由計算式(1)的生成矩陣G運算產生包括原始資料c與校驗碼(Error Correction Code,ECC)的碼字v。其中校驗碼可用於對原始資料c的合法性或完整性進行驗證。此外，原始資料c、生成矩陣G以及碼字v中的所有元素(element)或位元皆是以二進制(即，0或1)來表示。在一實施例中，上述計算式(1)中的元素相乘可利用及閘(AND gate)來實施，而元素相加則可利用互斥或閘(exclusive OR gete，或XOR gate)來實施。

在本實施例中，生成矩陣G為系統循環矩陣(Systematic-Circulant matrix)。亦即，生成矩陣G可以用如下計算式(2)之通用形式表示。

G=[I|P] 計算式(2)

其中，I為單位矩陣(Identity matrix)，且P為奇偶矩陣(parity matrix)。

舉例來說，假設原始資料c=[1 1 0]，生成矩陣G=，則編碼器模組106可產生碼字v=[1 1 0 1 0 1]，其中碼字v中前3個位元(即，[1 1 0])與原始資料c相同，碼字v中後3個位元(即，[1 0 1])為對應於原始資料c的校驗碼，而可作為對原始資料的驗證之用。此外，如計算式(2)所示，生成矩陣G由單位矩陣I以及奇偶矩陣P形成。本實施例中的單位矩陣 I為，奇偶矩陣P為。其中，奇偶矩陣P是由三個1×3的列矩陣形成，此三個1×3的列矩陣分別為[1 1 0]、[0 1 1]以及[1 0 1]。如前所述，生成矩陣G為系統循環矩陣，因此第一個1×3的列矩陣向右循環移位一個矩陣元素後，即為第二個1×3的列矩陣。類似的，第二個1×3的列矩陣向右右循環移位一個矩陣元素後，即為第三個1×3的列矩陣。第三個1×3的列矩陣向右循環移位一個矩陣元素後，即為第一個1×3的列矩陣。根據此特性，在儲存奇偶矩陣P時，僅需儲存其中一個列矩陣(此列矩陣稱之為基準向量)以節省存儲空間。若需要奇偶矩陣P其餘的列矩陣時，可將儲存的基準向量進行適當的向右循環移位一個矩陣元素後而可得之。

圖2為根據本發明一實施例說明圖1所繪示的編碼器模組106的示意圖。請參照圖2，編碼器模組106包括共享記憶體22以及奇偶產生器模組24。共享記憶體22例如是快閃記憶體、隨機存取記憶體等各種記憶體或儲存媒體。共享記憶體22可儲存有用以產生上述生成矩陣G(或奇偶矩陣P)的一個或多個基準向量。舉例來說，假設儲存於共享記憶體22中的多個基準向量的維度皆為1×3，表示這些基準向量分別由3個矩陣元素或位元(0或1)組成，並可以用1×3矩陣來表示。此外，當儲存於共享記憶體22中的基準向量的數量多於一個時，所有基準向量的維度可以相同也可以不相同，本發明不對其限制。

奇偶產生器模組24耦接共享記憶體22，並且用以自共享記憶體22中讀取出一個或多個基準向量。奇偶產生器模組24可先決定此一個或多個基準向量的維度，並根據決定維度後的基準向量產生一生成矩陣G。奇偶產生器模組24可包括n個奇偶產生器242_1-242_n與整合輸出電路244。奇偶產生器242_1-242_n分別耦接至共享記憶體22。在一實施例中，奇偶產生器模組24不調整基準向量的維度，而直接根據讀取自共享記憶體22中的基準向量產生生成矩陣G(或奇偶矩陣P)。在另一實施例中，奇偶產生器模組24可調整讀取自共享記憶體22中的基準向量的維度，並根據調整維度後的基準向量產生生成矩陣G(或奇偶矩陣P)。上述對基準向量的維度的調整較佳為降低基準向量的維度。整合輸出電路244可根據原始資料c與來自奇偶產生器242_1-242-n的一個或多個已編碼資料生成對應的碼字v。特別要說明的是，奇偶產生器242_1-242_n的數量可以視實際產品的設計需求/規格而定。對前述“已編碼資料”，圖3將會詳細闡述。此外，各奇偶產生器242_1-242_n需要的基準向量均儲存於共享記憶體22中，而非將上述的基準向量分別儲存在不同的記憶體中。當奇偶產生器242_1-242_n的數量多於一個(即，n>1，且n為正整數)時，奇偶產生器242_1-242_n會依序並輪流自共享記憶體22中讀取所需的基準向量，從而透過使用單一記憶體來節省記憶體在晶片中的電路面積。

一般而言，在編碼過程中，儲存於編碼裝置的維度(或， 位元數)皆是固定的，導致對應的生成矩陣G的維度也是固定的，在實務操作上缺乏彈性。然而，在本實施例中，在奇偶產生器模組24從共享記憶體22中讀取出所需的一個或多個基準向量之後，奇偶產生器模組24還可以適應性地調整此一個或多個基準向量的維度，從而產生符合不同需求的生成矩陣G。例如，假設儲存於共享記憶體22中的所有基準向量的維度是1×4，在奇偶產生器模組24取出所需的基準向量之後，奇偶產生器模組24可將此基準向量的維度進行調整，例如，降低為1×3，並根據降低後的基準向量產生對應的生成矩陣G。在一實施例中，當需要快速的儲存資料時，可使奇偶產生器模組24降低基準向量的維度。藉此以較低維度的生成矩陣G(相較於調整維度前的生成矩陣G)，而可加速資料編碼過程。在另一實施例中，當需要精確的儲存資料時，可使奇偶產生器模組24不調整基準向量的維度，以較高維度的生成矩陣G(相較於降低維度後的生成矩陣G)，而可提高儲存資料的精確度。

在奇偶產生器模組24產生生成矩陣G之後，奇偶產生器模組24可透過此生成矩陣G將來自主機介面104的原始資料c轉換為碼字v，並輸出碼字v至記憶體介面102，從而將碼字v寫入至記憶體晶片11。在一實施例中，生成矩陣G中的奇偶矩陣P可被劃分為一個或多個以矩陣形式呈現的列，且此一個或多個以矩陣形式呈現的列可分別包括一個或多個如前述的子矩陣。為 了說明方便，以下統一將每一個“以矩陣形式呈現的列”稱為子矩陣列(submatrix column)。例如，根據上述計算式(2)，生成矩陣G還可以用以下計算式(3)形式表示。

G=[I|第一子矩陣列 第二子矩陣列...第n子矩陣列] 計算式(3)

其中，每一個子矩陣列的行(row)數皆與奇偶矩陣P的行數相等，每一個子矩陣列的列(column)數皆與子矩陣(形如前述)的列數相等，第一子矩陣列至第n子矩陣列中所有的列之總和會與奇偶矩陣P的列數相等，並且n的數量可以視奇偶產生器242_1-242_n的數量而定。例如，n的數量與奇偶產生器242_1-242-n的數量相等。奇偶產生器242_1-242_n中的每一個根據所讀取和調整后的一個或多個基準向量產生對應奇偶矩陣P中的一個子矩陣列(submatrix column)，再根據原始資料c與該子矩陣列相乘，生成一個“已編碼資料”。藉此，奇偶產生器模組24中的每一個奇偶產生器可分別負責對於奇偶矩陣P中的一個子矩陣列的運算，從而達到分擔運算量與加快運算速度的功效。

以兩個奇偶產生器為例，假設奇偶產生器模組24包括奇偶產生器242_1與奇偶產生器242_2，原始資料c具有12個位元(即，原始資料c的維度為1×12)，且生成矩陣G的維度為12×18，其中，單位矩陣I的維度為12×12，而奇偶矩陣P的維度為12×6。此時，可將奇偶矩陣P劃分為兩個子矩陣列，例如，奇偶矩陣P=[第一子矩陣列 第二子矩陣列]，並將奇偶矩陣P中的第一子矩陣列 與第二子矩陣列分別劃分為4個維度為3×3的子矩陣，例如，奇偶矩陣。接著，在奇偶產生器模組22進行計算式(1)的運算時，奇偶產生器242_1可對原始資料c與奇偶矩陣P中的第一子矩陣列進行二進制的乘法與加法運算，以產生第一已編碼資料，並且奇偶產生器242_2可分別對原始資料c與奇偶矩陣P中的第二子矩陣列進行二進制的乘法與加法運算，以產生第二已編碼資料。

在本實施例中，由於奇偶產生器242_1-242_n的電路結構本質上是相同的，因此以下將以奇偶產生器242_1作為範例進行說明，而當奇偶產生器242_1-242_n的數量大於1時，其餘的奇偶產生器242_2-242_n可依此類推。舉例來說，圖3為根據本發明一實施例說明圖2所繪示的奇偶產生器242_1的示意圖。請參照圖3，奇偶產生器242_1包括控制電路32、運算電路34以及暫存電路36。控制電路32耦接共享記憶體22，用以自共享記憶體22讀取一個或多個基準向量(以下統一將奇偶產生器242_1讀取的基準向量稱為第一基準向量)，並決定此一個或多個第一基準向量的維度。接著，控制電路32可根據決定維度後的一個或多個第一基準向量而產生生成矩陣G中奇偶矩陣P的一個子矩陣列(例如，上述奇偶矩陣P中的第一子矩陣列)或子矩陣列中的一個子矩陣。特別是，在本實施例中，控制電路32產生的子矩陣列的行 數會與原始資料c中的位元c[1]、c[2]、…、c[k]的數量相等，而由控制電路32產生的子矩陣列亦具有k個行(row)。

圖3所示位元c[1]~c[k]表示原始資料c的部份或是全部位元。例如，若原始資料c具有k個位元，則位元c[1]~c[k]分別表示原始資料c的第一個位元至第k個位元。又例如，若原始資料c具有2k個位元，則位元c[1]~c[k]分別表示原始資料c的第一個位元至第k個位元(第一子資料)，或是分別表示原始資料c的第k+1個位元至第2k個位元(第二子資料)。也就是說，在原始資料c的位元數量大於k的情況下，原始資料c可以被分為多個子資料(每個子資料的位元數量均不大於k)。這些子資料依序輸入奇偶產生器242_1-242_n，以便原始資料c可以分批進行運算而完成計算式(1)。

在本實施例中，控制電路32可包括移位控制電路322以及矩陣暫存電路324。移位控制電路322耦接共享記憶體22，用以自共享記憶體22讀取上述一個或多個第一基準向量。特別是，移位控制電路322可根據一控制訊號CS決定此一個或多個第一基準向量的維度，並對決定維度後的此一個或多個第一基準向量進行至少一次的移位(shift)操作，以產生對應的子矩陣列。

舉例來說，假設移位控制電路322從共享記憶體22取得一個第一基準向量，且圖3所示位元c[1]~c[k]為12個位元。在決定此第一基準向量的維度之後，移位控制電路322會根據此第一基準向量進行11次的移位操作，以產生具有12個行的子矩陣 列(或子矩陣)。以[a1 a2 a3]作為此第一基準向量的範例，控制電路32對[a1 a2 a3]進行11次的位移操作(例如向右位移)會依序產生[a3 a1 a2]、[a2 a3 a1]、[a1 a2 a3]、[a3 a1 a2]、[a2 a3 a1]、[a1 a2 a3]、[a3 a1 a2]、[a2 a3 a1]、[a1 a2 a3]、[a3 a1 a2]、[a2 a3 a1]，因而獲得相對應的子矩陣列(或子矩陣列中的子矩陣)為

然而，在另一實施例中，移位控制電路322也可以從共享記憶體22取得多個第一基準向量。以取得4個第一基準向量為例，在移位控制電路322決定所取得的4個第一基準向量的維度之後，假設此4個第一基準向量分別為[a1 a2 a3]、[b1 b2 b3]、[c1 c2 c3]、[d1 d2 d3]，此時移位控制電路322可對此4個第一基準向量分別進行2次的移位操作，以產生4個3×3子矩陣，進而獲得由此四個子矩陣組成的具有12個行(即，維度為12×3)的子矩陣 列，例如，。

詳細而言，移位控制電路322可包括基準向量暫存電路3222與移位多工器3224。基準向量暫存電路3222耦接共享記憶體22與矩陣暫存電路324，並且具有位元儲存區域bs_1、bs_2、…、bs_p，其中位元儲存區域bs_1-bs_p分別用以儲存來自共享記憶體22的第一基準向量的各個位元。例如，若所取得的第一基準向量具有4個位元，則此4個位元可依序儲存於移位控制電路322的位元儲存區域bs_1-bs_4。

移位多工器3224可接收控制訊號CS，並根據控制訊號CS從儲存於基準向量暫存電路3222中的第一基準向量中選擇性讀取一特定位元，以決定第一基準向量的維度，並執行對應的移位操作。舉例來說，如圖3所示，基準向量暫存電路3222具有一輸入端與多個輸出端，其中這些輸出端分別用以輸出位元儲存區域bs_1-bs_p中儲存的位元。基準向量暫存電路3222可以進行向右移位操作，例如將位元儲存區域bs_1的內容傳遞至位元儲存區域bs_2，其餘位元儲存區域bs_2~bs_p的向右移位操作依此類 推。移位多工器3224具有輸入端I1-Ip與輸出端O，輸入端I1-Ip分別耦接基準向量暫存電路3222的各輸出端，並且輸出端O耦接基準向量暫存電路3222的輸入端。在每一次的移位操作中，移位多工器3224可根據控制訊號CS而透過輸入端I1-Ip的其中之一從位元儲存區域bs_1-bs_p中選擇讀取一個特定位元，並透過輸出端O將取得的特定位元回饋(feedback)至基準向量暫存電路3222的位元儲存區域bs_1，以對此儲存於基準向量暫存電路3222的第一基準向量進行一次的移位操作，並將移位操作的結果作為所產生的子矩陣列的一個行。

例如，當移位多工器3224根據控制訊號CS將輸入端I2與輸出端O導通時，移位多工器3224可取得儲存於位元儲存區域bs_2中的特定位元(即，第一基準向量的第2個位元)，並透過輸出端O將取得的特定位元回饋至基準向量暫存電路3222的輸入端。而在基準向量暫存電路3222透過其輸入端接收到原先儲存於位元儲存區域bs_2中的特定位元之後，基準向量暫存電路3222會將原先儲存於位元儲存區域bs_1的位元寫入至位元儲存區域bs_2，並將接收到的特定位元寫入至位元儲存區域bs_1，從而完成一次的移位操作並輸出儲存於位元儲存區域bs_1-bs_2中的位元。

藉此，假設原本的第一基準向量的維度是1×4，但移位控制電路322欲產生具有3個列的子矩陣列，此時移位多工器3224可透過讀取第一基準向量的第3個位元，並將此第3個位元回饋 至基準向量暫存電路3222的輸入端。因此，移位控制電路322可以同時達到將第一基準向量的維度調整為1×3以及對儲存於基準向量暫存電路3222中的第一基準向量進行移位操作的功能。

矩陣暫存電路324耦接移位控制電路322與運算電路34，用以儲存控制電路322產生的子矩陣列。詳細而言，矩陣暫存電路324具有矩陣儲存區域ms_1-ms_p，其分別用以接收並儲存來自位元儲存區域bs_1-bs_p的位元。接續上述範例，在每完成一次移位操作後，矩陣儲存區域ms_1-ms_3可分別儲存來自位元儲存區域bs_1-bs_3的位元資料。在完成多次移位操作後，矩陣儲存區域ms_1-ms_3便分別記錄了欲進行運算的子矩陣列中的各個列。例如，矩陣儲存區域ms_1儲存了欲進行運算的子矩陣列 中的第一個列(即，)，矩陣儲存區域ms_2儲存了 第二個列(即，)，而矩陣儲存區域ms_3儲存了第三個列(即， )。又例如，矩陣儲存區域ms_1儲存了欲進行運算的子矩陣 列中的第一個列(即，)，矩陣儲存區域ms_2 儲存了第二個列(即，)，而矩陣儲存區域ms_3儲存了第三 個列(即，)。

運算電路34耦接控制電路32，用以透過控制電路32產生的各個列(例如，上述第一至第三個列)將位元c[1]~c[k]轉換為一已編碼資料(例如，上述第一已編碼資料)。舉例來說，運算電路34包括子運算電路342_1、342_2、…、342_p，其中子運算電路342_1-342_p分別包括多個及閘以及多個互斥或閘(其基本架構類似於圖3的子運算電路342_1)，以透過矩陣儲存區域ms_1-ms_p中儲存的各個列對位元c[1]~c[k]進行運算，以產生已編碼資料中的各個位元。

暫存電路36耦接運算電路34，用以儲存運算電路34產生的已編碼資料(即，第一已編碼資料)。例如，暫存電路36可包括暫存區rs_1、rs_2、…、rs_p，而可分別儲存子運算電路342_1-342_p輸出的第一已編碼資料的各個位元。在另一實施例中，如果原始資料為c[1]~c[2k]，運算電路34第一次運算處理c[1]~c[k]可得到一第一部分編碼資料，該第一部分編碼資料儲存在上述的暫存電路36中。此外，儲存在暫存電路36中的該第一部分編碼資料會被回授到運算電路34，與第二次運算處理c[k+1]~c[2k]得到第二部分編碼資料相加，而可得到完整的第一已編碼資料並儲存於暫存電路36中。根據圖3中的電路架構，假設原始資料c為c[1：k]，本實施例不需每產生子矩陣列中的一個行就對c[1：k]的任一單一位元執行一次二位元的乘法與加法運算，而是在控制電路32產生出完整的子矩陣列或子矩陣列的多個行之後，才透過此完整的子矩陣列或子矩陣列的多個行同時對c[1：k]的各個位元進行二位元的乘法與加法運算，從而大幅提升編碼效率。

請再次參照圖2，整合輸出電路244可根據原始資料c與來自奇偶產生器242_1-242-n的一個或多個已編碼資料產生對應的碼字v。舉例來說，整合輸出電路244可包括整合電路2442與多工器2444。接續上述奇偶矩陣之範例，整合電路2442可將來自奇偶產生器242_1與奇偶產生器242_2的第一 已編碼資料與第二已編碼資料進行整合，並將整合後的已編碼資料作為原始資料的校驗碼輸出至多工器2444。多工器2444可接收來自主機介面12的原始資料c以及排序後的第一與第二已編碼資料(即，原始資料的校驗碼)，並將其依序輸出以產生碼字v。當原始資料輸入至編碼器模組106進行編碼時，多工器2444可以選擇將來自主機介面12的原始資料c輸出作為碼字v中的前部。在奇偶產生器242_1-242-n完成編碼後，多工器2444可以選擇將整合電路2442所輸出的校驗碼作為碼字v中的後部。具體而言，結合如前的計算式(3)和計算式(1)，得到以下計算式(4)：v=cG=c[I|P]=c[I|第一子矩陣列 第二子矩陣列...第n子矩陣列]=c|[c×第一子矩陣列 c×第二子矩陣列...c×第n子矩陣列]計算式(4)

以兩個奇偶產生器(242_1與242_2)產生第一和第二已編碼資料為例，計算式(4)為v=c|[c×第一子矩陣列 c×第二子矩陣列]，即奇偶產生器242_1產生的第一已編碼資料為前述計算式(4)中之“c×第一子矩陣列”，奇偶產生器242_2產生的第二已編碼資料為前述計算式(4)中之“c×第二子矩陣列”。

請再次參照圖1，在解碼方面，解碼器模組108可透過校驗矩陣H來對來自記體體介面102的碼字進行解碼，其中校驗矩陣H符合HG=0(即零矩陣)的運算規則。特別是，由於在將碼字v 從記憶體晶片11中取出的過程中可能會有雜訊干擾，因此一般會利用碼字v對應的決策比矩陣來作為對碼字進行解碼的依據。換言之，碼字v對應的決策比矩陣可輔助判斷碼字v編碼前的原始資料c，並降低因讀取時產生的雜訊對於解碼造成的誤差。舉例來說，假設來自記憶體介面102的碼字具有9個位元，則其對應的決策比矩陣例如是以表示，其中γ ₁至γ ₉分別為此碼字v的第1個位元至第9個位元的決策比。所述決策比可以相關於位元為0的機率與位元為1的機率二者的比值。所述決策比可以依據設計需求而決定。例如，在本實施例中，假設透過記憶體介面102從記憶體晶片11讀取碼字v中第一個位元為0的機率為Pr(0)，而相同碼字v中相同第一個位元為1的機率為Pr(1)，則碼字v中所述第一個位元的決策比可以定義為Pr(0)除以Pr(1)再取log(即log[Pr(0)/Pr(1)]，亦稱為log-likelihood ratio)。例如，γ ₁=log(此碼字中的第1個位元為0的機率/此碼字中的第1個位元為1的機率)，其餘γ ₂至γ ₉以此類推。

圖4為根據本發明一實施例所繪示的解碼器模組的示意圖。請參照圖4，解碼器模組108可包括多工器41、內部記憶體42、位元節點(bit node)處理器44以及校驗模組46。內部記憶體42可以透過多工器41接收並儲存來自記憶體介面102的碼字v所對應的決策比矩陣。位元節點處理器44的輸入端耦接內部記憶體42的輸出端，以便自內部記憶體42讀取資料(例如決策比矩 陣)。換言之，在本實施例中，位元節點處理器44可以取出儲存於內部記憶體42的決策比矩陣，然後將此決策比矩陣傳輸至校驗模組46以進行後續運算。校驗模組46的第一輸出端通過多工器41耦接內部記憶體42的輸入端，而校驗模組46的輸入端耦接至位元節點處理器44的輸出端。校驗模組46可以透過校驗矩陣H對來自位元節點處理器44的決策比矩陣進行疊代(iterative)運算，以更新儲存於內部記憶體42的決策比矩陣，並根據疊代運算的運算結果產生一修正矩陣。

在本實施例中，每一次的疊代運算可包含對於決策比矩陣的排列替換與更新操作，並且每一次的疊代運算可包括同步執行的多個週期操作，其中每一個週期操作是針對決策比矩陣的一個行。舉例來說，校驗模組46可包括排列替換(permute)處理器462以及校驗節點(check node)處理器464。排列替換處理器462的輸入端耦接位元節點處理器44的輸出端，用以根據校驗矩陣H將來自位元節點處理器44的決策比矩陣進行一排列替換。舉例來說，排列替換處理器462可以行為單位對決策比矩陣γ的第一行至第三行中的元素進行排列替換。假設儲存在內部記憶體42中決策比矩陣γ的初始值為，校驗矩陣。 在讀取初始值的操作中，位元節點處理器44不處理從內部記憶體 42讀取的決策比矩陣γ的初始值，而將此初始值傳送給排列替換 處理器462。根據校驗矩陣H的第一子矩陣，排列替換處 理器462將決策比矩陣γ的初始值的第一行[γ ₁ γ ₂ γ ₃]調整為 [γ ₁ γ ₂ γ ₃]。根據校驗矩陣H的第二子矩陣，排列替換處理 器462將決策比矩陣γ的初始值的第二行[γ ₄ γ ₅ γ ₆]調整為 [γ ₅ γ ₆ γ ₄]。根據校驗矩陣H的第三子矩陣，排列替換處理 器462將決策比矩陣γ的初始值的第三行[γ ₇ γ ₈ γ ₉]調整為[γ ₉ γ ₇ γ ₈]。因此，經過排列替換處理器462以行為單位的排列替 換之後，決策比矩陣γ會被轉換為γ'，並且。

校驗節點處理器464的輸入端耦接排列替換處理器462的輸出端，校驗節點處理器464的第一輸出端通過多工器41耦接至內部記憶體42的輸入端，以及校驗節點處理器464的第二輸出端耦接至位元節點處理器44的第二輸入端。校驗節點處理器464可以根據經排列替換的決策比矩陣γ'更新儲存於內部記憶體42的決策比矩陣，並產生前述修正矩陣給位元節點處理器44。在本實施例中，校驗節點處理器464包括3個校驗節點處理模組。在排列替換處理器462產生經排列替換的決策比矩陣γ'之後，校驗節點處理器464的第一校驗節點處理模組負責對γ'的第一個列中的元 素(即，)進行更新操作，校驗節點處理器464的第二校驗節 點處理模組負責對γ'的第二個列中的元素(即，)進行更新操 作，並且校驗節點處理器464的第三校驗節點處理模組負責對γ' 的第三個列中的元素(即，)進行更新操作。

詳細來看，在疊代運算的第一週期操作中，第一校驗節點處理模組可將γ ₁減去一修正值λ ₀₀而產生ρ ₀₀，第二校驗節點處理模組可將γ ₂減去一修正值λ ₀₁而產生ρ ₀₁，而第三校驗節點處理模組可將γ ₃減去一修正值λ ₀₂而產生ρ ₀₂。特別是，在第一次的疊代運算中，由於修正值λ ₀₀、λ ₀₁與λ ₀₂皆是初始值(例如為零)，故ρ ₀₀=γ ₁-λ ₀₀=γ ₁，ρ ₀₁=γ ₂-λ ₀₁=γ ₂，且ρ ₀₂=γ ₃-λ ₀₂=γ ₃。在產生ρ ₀₀、ρ ₀₁與ρ ₀₂之後，校驗節點處理器464將儲存於內部記憶體42的決策比矩陣γ中的γ ₁、γ ₂與γ ₃分別更新為ρ ₀₀、ρ ₀₁與ρ ₀₂。

在疊代運算的第二週期操作中，第一校驗節點處理模組可將γ ₅減去修正值λ ₁₁而產生ρ ₁₁，第二校驗節點處理模組可將γ ₆減去修正值λ ₁₂而產生ρ ₁₂，而第三校驗節點處理模組可將γ ₄減去修正值λ ₁₀而產生ρ ₁₀。同樣地，由於此次為第一次的疊代運算，因此修正值λ ₁₁、λ ₁₂與λ ₁₀皆是初始值(例如為零)，並且ρ ₁₁=γ ₅-λ ₁₁=γ ₅，ρ ₁₂=γ ₆-λ ₁₂=γ ₆，且ρ ₁₀=γ ₄-λ ₁₀=γ ₄。在產生ρ ₁₁、ρ ₁₂與ρ ₁₀之後，校驗節點處理器464將儲存於內部記憶體42的決策比矩陣γ中的γ ₅、γ ₆與 γ ₄分別更新為ρ ₁₁、ρ ₁₂與ρ ₁₀。

在疊代運算的第三週期操作中，第一校驗節點處理模組可將γ ₉減去修正值λ ₂₂而產生ρ ₂₂，第二校驗節點處理模組可將γ ₇減去修正值λ ₂₀而產生ρ ₂₀，而第三校驗節點處理模組可將γ ₈減去修正值λ ₂₁而產生ρ ₂₁。同樣地，由於此次為第一次的疊代運算，因此修正值λ ₂₂、λ ₂₀與λ ₂₁皆是初始值(例如為零)，並且ρ ₂₂=γ ₉-λ ₂₂=γ ₉，ρ ₂₀=γ ₇-λ ₂₀=γ ₇，且ρ ₂₁=γ ₈-λ ₂₁=γ ₈。在產生ρ ₂₂、ρ ₂₀與ρ ₂₁之後，校驗節點處理器464將儲存於內部記憶體42的決策比矩陣γ中的γ ₉、γ ₇與γ ₈分別更新為ρ ₂₂、ρ ₂₀與ρ ₂₁。

值得一提的是，由於校驗節點處理器464可以不經過位元節點處理器44直接將其產生的決策比矩陣寫入內部記憶體42中，因此位元節點處理器44並不需要具有額外的儲存空間來儲存校驗節點處理器464產生的決策比矩陣，從而減少建構位元節點處理器44的設置成本。

在完成疊代操作中的三個週期操作之後，校驗節點處理器464可根據更新後的決策比矩陣ρ產生修正矩陣λ。在本實施例中，修正矩陣λ中某個元素，例如是根據在更新後的決策比矩陣中，同一列中除了自己本身位置之外的其他各個元素取絕對值後的最小的元素來決定。例如，假設更新後的決策比矩陣 ，則校驗節點處理器464產生的修正矩 陣λ例如是，其中λ ₀₀=min(| ρ ₁₀ |,| ρ ₂₀ |)， λ ₁₀=min(| ρ ₀₀ |,| ρ ₂₀ |)，λ ₂₀=min(| ρ ₀₀ |,| ρ ₁₀ |)，λ ₀₁=min(| ρ ₁₁ |,| ρ ₂₁ |)，λ ₁₁=min(| ρ ₀₁ |,| ρ ₂₁ |)，λ ₂₁=min(| ρ ₀₁ |,| ρ ₁₁ |)，λ ₀₂=min(| ρ ₁₂ |,| ρ ₂₂ |)，λ ₁₂=min(| ρ ₀₂ |,| ρ ₂₂ |)，並且λ ₂₂=min(| ρ ₀₂ |,| ρ ₁₂ |)。

在校驗節點處理器464產生修正矩陣λ之後，校驗節點處理器464會將修正矩陣λ傳送給位元節點處理器44。然後，位元節點處理器44可根據此修正矩陣λ修正自內部記憶體42讀取之更新後的決策比矩陣ρ。舉例來說，位元節點處理器44可自內部記憶體42中讀取更新後的決策比矩陣ρ，並將更新後的決策比矩陣ρ加上修正矩陣λ，從而產生修正後的決策比矩陣γ，其中 。假設原始的決策比矩陣 ，更新後的決策比矩陣，並且修正矩陣 ，則經修正矩陣修正後的決策比矩陣。

此外，校驗模組46還可以根據經位元節點處理器44修正後的決策比矩陣γ決定是否重複進行另一次的疊代運算。若校驗模組46決定不重複進行另一次的疊代運算，則校驗模組46可根據修正後的決策比矩陣γ產生一已解碼資料，並將此已解碼資料傳送至主機介面104。舉例來說，校驗模組46還包括決策電路466 以及早期終止電路468。決策電路466耦接排列替換處理器462，用以對由位元節點處理器44修正後的決策比矩陣進行一硬決策(hard decision)，以取得一決策矩陣X。例如，將修正後的決策比矩陣γ中小於零的元素轉換為1，並將修正後的決策比矩陣γ中大於零的元素轉換為0，以獲得決策矩陣X。接續上述範例，假設 修正後的決策比矩陣，則經過決策電路466的硬決策 之後，決策電路466可產生維度為1×9的決策矩陣X=[1 0 0 0 0 0 0 0 0]。

早期終止電路468耦接決策電路466，用以運算並判斷決策矩陣X是否符合HX^T=0的運算規則。若決策矩陣X符合此運算規則，則早期終止電路468決定校驗模組46不重複進行另一次的疊代運算，並且校驗模組46以決策矩陣X作為已解碼資料而傳送至主機介面104。此外，若早期終止電路468判斷決策矩陣X不符合HX^T=0的運算規則，則校驗模組46根據經位元節點處理器44修正後的決策比矩陣γ重複進行另一次的疊代運算。特別是，在本實施例中，只有第一次進行疊代運算時，校驗節點處理器464是以零作為修正矩陣λ的初始值。在第二次之後的疊代運算中，校驗節點處理器464皆以前一次的疊代運算取得的修正矩陣λ去修正位元節點處理器44所提供的決策比矩陣γ而獲得決策比矩陣ρ(即ρ=γ-λ)，並且在完成另一次的疊代運算之後再次更新修正矩陣λ。

綜上所述，本發明實施例的記憶體控制器中的編碼器模組可適應性地調整生成矩陣的維度，並且透過使用單一的記憶體來達到節省記憶體的功效。另外，本發明實施例的記憶體控制器中的解碼器模組則可在每一次的疊代運算之後判斷是否需要再次進行另一次的疊代運算，藉此，即使尚未達到預設的疊代次數，只要疊代運算的結果符合使用上的需求，即可提前終止疊代運算，從而提升解碼效率。

雖然本發明已以實施例揭露如上，然其並非用以限定本發明，任何所屬技術領域中具有通常知識者，在不脫離本發明的精神和範圍內，當可作些許的更動與潤飾，故本發明的保護範圍當視後附的申請專利範圍所界定者為準。

106‧‧‧編碼器模組

22‧‧‧共享記憶體

24‧‧‧奇偶產生器模組

242_1-242_n‧‧‧奇偶產生器

244‧‧‧整合輸出電路

2442‧‧‧整合電路

2444‧‧‧多工器

Claims (16)

1. 一種記憶體控制器，包括：一記憶體介面，用以連接至少一記憶體晶片；以及一編碼器模組，耦接至該記憶體介面，該編碼器模組包括：一共享記憶體；以及一奇偶產生器模組，耦接該共享記憶體，用以自該共享記憶體中讀取至少一基準向量，決定該至少一基準向量的維度，該奇偶產生器模組根據決定維度後的該至少一基準向量產生一生成矩陣，並透過該生成矩陣將一原始資料轉換為一碼字，並透過該記憶體介面將該碼字儲存在該記憶體晶片。
2. 如申請專利範圍第1項所述的記憶體控制器，其中該奇偶產生器模組包括至少一奇偶產生器，並且該至少一奇偶產生器分別耦接該共享記憶體，其中當該奇偶產生器的數量大於一時，該些奇偶產生器依序輪流自該共享記憶體中讀取該至少一基準向量。
3. 如申請專利範圍第1項所述的記憶體控制器，其中該奇偶產生器模組包括至少一奇偶產生器與一整合輸出電路，其中每一所述奇偶產生器包括：一控制電路，耦接該共享記憶體，用以自該共享記憶體讀取該至少一基準向量中的至少一第一基準向量，決定該至少一第一基準向量的維度，並根據決定維度後的該至少一第一基準向量產生該生成矩陣中的一子矩陣列； 一運算電路，耦接該控制電路，用以透過該子矩陣列將該原始資料轉換為一已編碼資料；以及一暫存電路，耦接該運算電路，用以儲存該已編碼資料或該運算電路根據該原始資料產生的一部份編碼資料，其中該整合輸出電路用以根據該原始資料與來自該至少一奇偶產生器的至少一該已編碼資料輸出該碼字。
4. 如申請專利範圍第3項所述的記憶體控制器，其中該控制電路包括：一移位控制電路，耦接該共享記憶體，用以自該共享記憶體讀取該至少一第一基準向量，根據一控制訊號決定該至少一第一基準向量的維度，並對決定維度後的該至少一第一基準向量進行一移位操作，以產生該子矩陣列；以及一矩陣暫存電路，耦接該移位控制電路與該運算電路，用以儲存該子矩陣列。
5. 如申請專利範圍第4項所述的記憶體控制器，其中該移位控制電路包括：一基準向量暫存電路，耦接該共享記憶體與該矩陣暫存電路，用以儲存來自該共享記憶體的該至少一第一基準向量；以及一移位多工器，該移位多工器的多個輸入端耦接該基準向量暫存電路的多個輸出端，並且該移位多工器的一輸出端耦接該基準向量暫存電路的一輸入端，其中該移位多工器根據該控制訊號透過該移位多工器的該些 輸入端的其中之一從該至少一第一基準向量中選擇性讀取一特定位元，以決定該至少一第一基準向量的維度，並透過該移位多工器的該輸出端將該至少一特定位元回饋至該基準向量暫存電路，以對決定維度後的該至少一第一基準向量進行該移位操作。
6. 如申請專利範圍第1項所述的記憶體控制器，其中該奇偶產生器模組執行v=cG的運算，其中c代表該原始資料，G代表該生成矩陣，並且v代表該碼字。
7. 一種記憶體控制器，包括：一記憶體介面，用以連接一記憶體晶片；一解碼器模組，耦接至該記憶體介面，該解碼器模組包括：一內部記憶體，用以儲存來自該記憶體介面的一碼字所對應的一決策比矩陣；一位元節點處理器，耦接該內部記憶體，用以自該內部記憶體讀取該決策比矩陣；以及一校驗模組，耦接該內部記憶體與該位元節點處理器，用以透過一校驗矩陣對來自該位元節點處理器的該決策比矩陣進行一疊代運算，以更新儲存於該內部記憶體的該決策比矩陣，並根據該疊代運算的運算結果產生一修正矩陣，其中該位元節點處理器更根據該修正矩陣修正自該內部記憶體讀取之更新後的決策比矩陣，且該校驗模組根據修正後的決策比矩陣決定是否重複進行該疊代運算，若該校驗模組決定不重複進行該疊代運算，則該校驗模組根據修正後的決策比矩陣產生一 已解碼資料。
8. 如申請專利範圍第7項所述的記憶體控制器，其中該校驗模組包括：一排列替換處理器，耦接該位元節點處理器，用以根據該校驗矩陣將來自該位元節點處理器的該決策比矩陣進行一排列替換；一校驗節點處理器，耦接該排列替換處理器、該內部記憶體以及該位元節點處理器，用以根據經排列替換的決策比矩陣更新儲存於該內部記憶體的該決策比矩陣，並產生該修正矩陣。
9. 如申請專利範圍第7項所述的記憶體控制器，其中該校驗模組包括：一決策電路，耦接該位元節點處理器，用以對經該位元節點處理器修正後的決策比矩陣進行一硬決策，以取得一決策矩陣；以及一早期終止電路，耦接該決策電路，用以判斷該決策矩陣是否符合HX^T=0的運算規則，其中H代表該校驗矩陣，並且X代表該決策矩陣，其中當該決策矩陣符合該運算規則時，該早期終止電路決定該校驗模組不重複進行該疊代運算，並且該校驗模組以該決策矩陣作為該已解碼資料而傳送至該主機介面。
10. 如申請專利範圍第7項所述的記憶體控制器，其中該碼字符合v=cG的運算規則，並且該校驗矩陣符合HG=0的運算規 則，其中c代表一原始資料，G代表一生成矩陣，v代表該碼字，並且H代表該校驗矩陣。
11. 如申請專利範圍第7項所述的記憶體控制器，更包括：一編碼器模組，耦接至該記憶體介面，其中該編碼器模組包括：一共享記憶體；以及一奇偶產生器模組，耦接該共享記憶體，用以自該共享記憶體中讀取至少一基準向量，決定該至少一基準向量的維度，該奇偶產生器模組根據決定維度後的該至少一基準向量產生一生成矩陣，並透過該生成矩陣將一原始資料轉換為一碼字，並透過該記憶體介面將該碼字儲存在該記憶體晶片。
12. 如申請專利範圍第11項所述的記憶體控制器，其中該奇偶產生器模組包括至少一奇偶產生器，並且該至少一奇偶產生器分別耦接該共享記憶體，其中當該奇偶產生器的數量大於一時，該些奇偶產生器依序輪流自該共享記憶體中讀取該至少一基準向量。
13. 如申請專利範圍第11項所述的記憶體控制器，其中該奇偶產生器模組包括至少一奇偶產生器與一整合輸出電路，其中每一所述奇偶產生器包括：一控制電路，耦接該共享記憶體，用以自該共享記憶體讀取該至少一基準向量中的至少一第一基準向量，決定該至少一第一基準向量的維度，並根據決定維度後的該至少一第一基準向量產 生該生成矩陣中的一子矩陣列；一運算電路，耦接該控制電路，用以透過該子矩陣列將該原始資料轉換為一已編碼資料；以及一暫存電路，耦接該運算電路，用以儲存該已編碼資料或該運算電路根據該原始資料產生的一部份編碼資料，其中該整合輸出電路用以根據該原始資料與來自該至少一奇偶產生器的至少一該已編碼資料輸出該碼字。
14. 如申請專利範圍第13項所述的記憶體控制器，其中該控制電路包括：一移位控制電路，耦接該共享記憶體，用以自該共享記憶體讀取該至少一第一基準向量，根據一控制訊號決定該至少一第一基準向量的維度，並對決定維度後的該至少一第一基準向量進行一移位操作，以產生該子矩陣列；以及一矩陣暫存電路，耦接該移位控制電路與該運算電路，用以儲存該子矩陣列。
15. 如申請專利範圍第14項所述的記憶體控制器，其中該移位控制電路包括：一基準向量暫存電路，耦接該共享記憶體與該矩陣暫存電路，用以儲存來自該共享記憶體的該至少一第一基準向量；以及一移位多工器，該移位多工器的多個輸入端耦接該基準向量暫存電路的多個輸出端，並且該移位多工器的一輸出端耦接該基準向量暫存電路的一輸入端， 其中該移位多工器根據該控制訊號透過該移位多工器的該些輸入端的其中之一從該至少一第一基準向量中選擇性讀取一特定位元，以決定該至少一第一基準向量的維度，並透過該移位多工器的該輸出端將該至少一特定位元回饋至該基準向量暫存電路，以對決定維度後的該至少一第一基準向量進行該移位操作。
16. 如申請專利範圍第11項所述的記憶體控制器，其中該奇偶產生器模組執行v=cG的運算，其中c代表該原始資料，G代表該生成矩陣，並且v代表該碼字。