[go: up one dir, main page]

TW201546815A - 解碼方法、記憶體儲存裝置及記憶體控制電路單元 - Google Patents

解碼方法、記憶體儲存裝置及記憶體控制電路單元 Download PDF

Info

Publication number
TW201546815A
TW201546815A TW103120045A TW103120045A TW201546815A TW 201546815 A TW201546815 A TW 201546815A TW 103120045 A TW103120045 A TW 103120045A TW 103120045 A TW103120045 A TW 103120045A TW 201546815 A TW201546815 A TW 201546815A
Authority
TW
Taiwan
Prior art keywords
bits
bit
error
information
memory
Prior art date
Application number
TW103120045A
Other languages
English (en)
Other versions
TWI543178B (zh
Inventor
Chien-Fu Tseng
Original Assignee
Phison Electronics Corp
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Application filed by Phison Electronics Corp filed Critical Phison Electronics Corp
Priority to TW103120045A priority Critical patent/TWI543178B/zh
Priority to US14/475,585 priority patent/US9543983B2/en
Publication of TW201546815A publication Critical patent/TW201546815A/zh
Application granted granted Critical
Publication of TWI543178B publication Critical patent/TWI543178B/zh

Links

Classifications

    • H—ELECTRICITY
    • H03—ELECTRONIC CIRCUITRY
    • H03M—CODING; DECODING; CODE CONVERSION IN GENERAL
    • H03M13/00—Coding, decoding or code conversion, for error detection or error correction; Coding theory basic assumptions; Coding bounds; Error probability evaluation methods; Channel models; Simulation or testing of codes
    • H03M13/03—Error detection or forward error correction by redundancy in data representation, i.e. code words containing more digits than the source words
    • H03M13/05—Error detection or forward error correction by redundancy in data representation, i.e. code words containing more digits than the source words using block codes, i.e. a predetermined number of check bits joined to a predetermined number of information bits
    • H03M13/11—Error detection or forward error correction by redundancy in data representation, i.e. code words containing more digits than the source words using block codes, i.e. a predetermined number of check bits joined to a predetermined number of information bits using multiple parity bits
    • H03M13/1102—Codes on graphs and decoding on graphs, e.g. low-density parity check [LDPC] codes
    • H03M13/1105—Decoding
    • H03M13/1108—Hard decision decoding, e.g. bit flipping, modified or weighted bit flipping
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F11/00—Error detection; Error correction; Monitoring
    • G06F11/07—Responding to the occurrence of a fault, e.g. fault tolerance
    • G06F11/08—Error detection or correction by redundancy in data representation, e.g. by using checking codes
    • G06F11/10—Adding special bits or symbols to the coded information, e.g. parity check, casting out 9's or 11's
    • G06F11/1008—Adding special bits or symbols to the coded information, e.g. parity check, casting out 9's or 11's in individual solid state devices
    • G06F11/1012—Adding special bits or symbols to the coded information, e.g. parity check, casting out 9's or 11's in individual solid state devices using codes or arrangements adapted for a specific type of error
    • H—ELECTRICITY
    • H03—ELECTRONIC CIRCUITRY
    • H03M—CODING; DECODING; CODE CONVERSION IN GENERAL
    • H03M13/00—Coding, decoding or code conversion, for error detection or error correction; Coding theory basic assumptions; Coding bounds; Error probability evaluation methods; Channel models; Simulation or testing of codes
    • H03M13/03—Error detection or forward error correction by redundancy in data representation, i.e. code words containing more digits than the source words
    • H03M13/05—Error detection or forward error correction by redundancy in data representation, i.e. code words containing more digits than the source words using block codes, i.e. a predetermined number of check bits joined to a predetermined number of information bits
    • H03M13/11—Error detection or forward error correction by redundancy in data representation, i.e. code words containing more digits than the source words using block codes, i.e. a predetermined number of check bits joined to a predetermined number of information bits using multiple parity bits
    • H03M13/1102—Codes on graphs and decoding on graphs, e.g. low-density parity check [LDPC] codes
    • H03M13/1105—Decoding
    • H03M13/1128—Judging correct decoding and iterative stopping criteria other than syndrome check and upper limit for decoding iterations
    • H—ELECTRICITY
    • H03—ELECTRONIC CIRCUITRY
    • H03M—CODING; DECODING; CODE CONVERSION IN GENERAL
    • H03M13/00—Coding, decoding or code conversion, for error detection or error correction; Coding theory basic assumptions; Coding bounds; Error probability evaluation methods; Channel models; Simulation or testing of codes
    • H03M13/37—Decoding methods or techniques, not specific to the particular type of coding provided for in groups H03M13/03 - H03M13/35
    • H03M13/3746—Decoding methods or techniques, not specific to the particular type of coding provided for in groups H03M13/03 - H03M13/35 with iterative decoding
    • H—ELECTRICITY
    • H03—ELECTRONIC CIRCUITRY
    • H03M—CODING; DECODING; CODE CONVERSION IN GENERAL
    • H03M13/00—Coding, decoding or code conversion, for error detection or error correction; Coding theory basic assumptions; Coding bounds; Error probability evaluation methods; Channel models; Simulation or testing of codes
    • H03M13/03—Error detection or forward error correction by redundancy in data representation, i.e. code words containing more digits than the source words
    • H03M13/05—Error detection or forward error correction by redundancy in data representation, i.e. code words containing more digits than the source words using block codes, i.e. a predetermined number of check bits joined to a predetermined number of information bits
    • H03M13/11—Error detection or forward error correction by redundancy in data representation, i.e. code words containing more digits than the source words using block codes, i.e. a predetermined number of check bits joined to a predetermined number of information bits using multiple parity bits
    • H03M13/1102—Codes on graphs and decoding on graphs, e.g. low-density parity check [LDPC] codes
    • H—ELECTRICITY
    • H03—ELECTRONIC CIRCUITRY
    • H03M—CODING; DECODING; CODE CONVERSION IN GENERAL
    • H03M13/00—Coding, decoding or code conversion, for error detection or error correction; Coding theory basic assumptions; Coding bounds; Error probability evaluation methods; Channel models; Simulation or testing of codes
    • H03M13/03—Error detection or forward error correction by redundancy in data representation, i.e. code words containing more digits than the source words
    • H03M13/05—Error detection or forward error correction by redundancy in data representation, i.e. code words containing more digits than the source words using block codes, i.e. a predetermined number of check bits joined to a predetermined number of information bits
    • H03M13/11—Error detection or forward error correction by redundancy in data representation, i.e. code words containing more digits than the source words using block codes, i.e. a predetermined number of check bits joined to a predetermined number of information bits using multiple parity bits
    • H03M13/1102—Codes on graphs and decoding on graphs, e.g. low-density parity check [LDPC] codes
    • H03M13/1148—Structural properties of the code parity-check or generator matrix
    • H03M13/1171—Parity-check or generator matrices with non-binary elements, e.g. for non-binary LDPC codes
    • H—ELECTRICITY
    • H03—ELECTRONIC CIRCUITRY
    • H03M—CODING; DECODING; CODE CONVERSION IN GENERAL
    • H03M13/00—Coding, decoding or code conversion, for error detection or error correction; Coding theory basic assumptions; Coding bounds; Error probability evaluation methods; Channel models; Simulation or testing of codes
    • H03M13/29—Coding, decoding or code conversion, for error detection or error correction; Coding theory basic assumptions; Coding bounds; Error probability evaluation methods; Channel models; Simulation or testing of codes combining two or more codes or code structures, e.g. product codes, generalised product codes, concatenated codes, inner and outer codes
    • H03M13/2957—Turbo codes and decoding

Landscapes

  • Engineering & Computer Science (AREA)
  • Theoretical Computer Science (AREA)
  • Physics & Mathematics (AREA)
  • Probability & Statistics with Applications (AREA)
  • Quality & Reliability (AREA)
  • General Engineering & Computer Science (AREA)
  • General Physics & Mathematics (AREA)
  • Techniques For Improving Reliability Of Storages (AREA)

Abstract

一種解碼方法、記憶體儲存裝置及記憶體控制電路單元。所述解碼方法包括：發送讀取指令序列，其用以讀取多個記憶胞以取得多個第一位元；判斷所述第一位元是否具有第一錯誤；若所述第一位元具有所述第一錯誤，對所述第一位元執行第一迭代解碼程序以取得多個第二位元，並且記錄所述第一迭代解碼程序的第一位元翻轉資訊；判斷所述第二位元是否具有第二錯誤；若所述第二位元具有所述第二錯誤，根據所述第一位元翻轉資訊對所述第二位元執行第二迭代解碼程序以取得多個第三位元。

Description

解碼方法、記憶體儲存裝置及記憶體控制電路單元
本發明是有關於一種解碼方法，且特別是有關於一種用於可複寫式非揮發性記憶體模組的解碼方法、記憶體儲存裝置及記憶體控制電路單元。
數位相機、行動電話與MP3播放器在這幾年來的成長十分迅速，使得消費者對儲存媒體的需求也急速增加。由於可複寫式非揮發性記憶體模組(例如，快閃記憶體)具有資料非揮發性、省電、體積小，以及無機械結構等特性，所以非常適合內建於上述所舉例的各種可攜式多媒體裝置中。
一般來說，為了確保資料的完整性，欲寫入至可複寫式非揮發性記憶體模組的資料會被編碼。編碼過的資料才會被寫入至可複寫式非揮發性記憶體模組。從可複寫式非揮發性記憶體模組中讀取出的資料則會經過對應的解碼程序。在眾多的解碼演算法中，位元翻轉(bit flipping)解碼演算法是運算複雜度較低的。但 是，位元翻轉解碼演算法的解碼成功率也相對較低。
本發明提供一種解碼方法、記憶體儲存裝置及記憶體控制電路單元，可使用運算複雜度較低的解碼演算法，並且可提升解碼成功率。
本發明的一範例實施例提供一種解碼方法，其用於可複寫式非揮發性記憶體模組，所述可複寫式非揮發性記憶體模組包括多個記憶胞，所述解碼方法包括：發送讀取指令序列，其中所述讀取指令序列用以讀取所述記憶胞以取得多個第一位元；判斷所述第一位元是否具有至少一第一錯誤；若所述第一位元具有所述第一錯誤，對所述第一位元執行第一迭代解碼程序以取得多個第二位元，並且記錄所述第一迭代解碼程序的第一位元翻轉資訊；判斷所述第二位元是否具有至少一第二錯誤；若所述第二位元具有所述第二錯誤，根據所述第一位元翻轉資訊對所述第二位元執行第二迭代解碼程序以取得多個第三位元；以及若所述第二位元不具有所述第二錯誤，輸出所述第二位元。
在本發明的一範例實施例中，所述的第一位元翻轉資訊包括一錯誤索引資訊，並且錯誤索引資訊用以指示所述第一位元中被翻轉或未被翻轉的至少一第一位元。
在本發明的一範例實施例中，所述的判斷所述第二位元是否具有所述第二錯誤的步驟包括：對所述第二位元執行一奇偶 檢查(parity check)程序以取得多個校驗子(syndrome)，其中每一所述第二位元是對應至所述校驗子的至少其中之一；以及根據所述校驗子判斷所述第二位元是否具有所述第二錯誤。
在本發明的一範例實施例中，所述的根據第一位元翻轉資訊對所述第二位元執行第二迭代解碼程序以取得所述第三位元的步驟包括：根據第一位元翻轉資訊取得所述第二位元的一校驗權重資訊；以及根據校驗權重資訊來翻轉所述第二位元的至少其中之一。
在本發明的一範例實施例中，所述的根據第一位元翻轉資訊取得所述第二位元的校驗權重資訊的步驟包括：對第一位元翻轉資訊執行一縮放(scaling)操作以產生一參考資訊；以及將參考資訊與所述第二位元的一預設校驗權重資訊相加以取得所述第二位元的校驗權重資訊。
在本發明的一範例實施例中，所述的對第一位元翻轉資訊執行縮放操作以產生參考資訊的步驟包括：將第一位元翻轉資訊與一縮放參數相乘，其中縮放參數的值與一總迭代次數為負相關(negative correlation)。
在本發明的一範例實施例中，所述的縮放參數的值更與一奇偶檢查矩陣的一行權重(column weight)為負相關。
在本發明的一範例實施例中，所述的解碼方法更包括：記錄第二迭代解碼程序的一第二位元翻轉資訊；判斷所述第三位元是否具有至少一第三錯誤；若所述第三位元具有所述第三錯 誤，根據第二位元翻轉資訊對所述第三位元執行一第三迭代解碼程序以取得多個第四位元，其中第二位元翻轉資訊與第一位元翻轉資訊不同；以及若所述第三位元不具有所述第三錯誤，輸出所述第三位元。
在本發明的一範例實施例中，所述的解碼方法是使用一低密度奇偶檢查演算法來編碼與解碼。
本發明的一範例實施例提供一種記憶體儲存裝置，其包括連接介面單元、可複寫式非揮發性記憶體模組及記憶體控制電路單元。連接介面單元用以耦接至一主機系統。可複寫式非揮發性記憶體模組包括多個記憶胞。記憶體控制電路單元耦接至連接介面單元與可複寫式非揮發性記憶體模組，並且用以發送一讀取指令序列，其中讀取指令序列用以讀取所述記憶胞以取得多個第一位元。記憶體控制電路單元更用以判斷所述第一位元是否具有至少一第一錯誤。若所述第一位元具有所述第一錯誤，記憶體控制電路單元更用以對所述第一位元執行一第一迭代解碼程序以取得多個第二位元，並且記錄第一迭代解碼程序的一第一位元翻轉資訊。記憶體控制電路單元更用以判斷所述第二位元是否具有至少一第二錯誤。若所述第二位元具有所述第二錯誤，記憶體控制電路單元更用以根據第一位元翻轉資訊對所述第二位元執行一第二迭代解碼程序以取得多個第三位元。若所述第二位元不具有所述第二錯誤，記憶體控制電路單元更用以輸出所述第二位元。
在本發明的一範例實施例中，所述的第一位元翻轉資訊 包括一錯誤索引資訊，並且錯誤索引資訊用以指示所述第一位元中被翻轉或未被翻轉的至少一第一位元。
在本發明的一範例實施例中，所述的記憶體控制電路單元判斷所述第二位元是否具有所述第二錯誤的操作包括：記憶體控制電路單元對所述第二位元執行一奇偶檢查程序以取得多個校驗子，其中每一所述第二位元是對應至所述校驗子的至少其中之一，記憶體控制電路單元根據所述校驗子判斷所述第二位元是否具有所述第二錯誤。
在本發明的一範例實施例中，所述的記憶體控制電路單元根據第一位元翻轉資訊對所述第二位元執行第二迭代解碼程序以取得所述第三位元的操作包括：記憶體控制電路單元根據第一位元翻轉資訊取得所述第二位元的一校驗權重資訊；以及記憶體控制電路單元根據校驗權重資訊來翻轉所述第二位元的至少其中之一。
在本發明的一範例實施例中，所述的記憶體控制電路單元根據第一位元翻轉資訊取得所述第二位元的校驗權重資訊的操作包括：記憶體控制電路單元對第一位元翻轉資訊執行一縮放操作以產生一參考資訊；以及記憶體控制電路單元將參考資訊與所述第二位元的一預設校驗權重資訊相加以取得所述第二位元的校驗權重資訊。
在本發明的一範例實施例中，所述的記憶體控制電路單元對第一位元翻轉資訊執行縮放操作以產生參考資訊的操作包 括：記憶體控制電路單元將第一位元翻轉資訊與一縮放參數相乘，其中縮放參數的值與一總迭代次數為負相關。
在本發明的一範例實施例中，所述的縮放參數的值更與一奇偶檢查矩陣的一行權重為負相關。
在本發明的一範例實施例中，所述的記憶體控制電路單元更用以記錄第二迭代解碼程序的一第二位元翻轉資訊。記憶體控制電路單元更用以判斷所述第三位元是否具有至少一第三錯誤。若所述第三位元具有所述第三錯誤，記憶體控制電路單元更用以根據第二位元翻轉資訊對所述第三位元執行一第三迭代解碼程序以取得多個第四位元，其中第二位元翻轉資訊與第一位元翻轉資訊不同。若所述第三位元不具有所述第三錯誤，記憶體控制電路單元更用以輸出所述第三位元。
在本發明的一範例實施例中，所述的記憶體控制電路單元是使用一低密度奇偶檢查演算法來編碼與解碼。
本發明的一範例實施例提供一種記憶體控制電路單元，其用於控制一可複寫式非揮發性記憶體模組，其中可複寫式非揮發性記憶體模組包括多個記憶胞，記憶體控制電路單元包括主機介面、記憶體介面、記憶體管理電路及錯誤檢查與校正電路。主機介面用以耦接至一主機系統。記憶體介面用以耦接至可複寫式非揮發性記憶體模組。記憶體管理電路耦接至主機介面與記憶體介面，並且用以發送一讀取指令序列，其中讀取指令序列用以讀取所述記憶胞以取得多個第一位元。錯誤檢查與校正電路耦接至 記憶體管理電路，並且用以判斷所述第一位元是否具有至少一第一錯誤。若所述第一位元具有所述第一錯誤，錯誤檢查與校正電路更用以對所述第一位元執行一第一迭代解碼程序以取得多個第二位元，並且記錄第一迭代解碼程序的一第一位元翻轉資訊。錯誤檢查與校正電路更用以判斷所述第二位元是否具有至少一第二錯誤。若所述第二位元具有所述第二錯誤，錯誤檢查與校正電路更用以根據第一位元翻轉資訊對所述第二位元執行一第二迭代解碼程序以取得多個第三位元。若所述第二位元不具有所述第二錯誤，錯誤檢查與校正電路更用以輸出所述第二位元。
在本發明的一範例實施例中，所述的第一位元翻轉資訊包括一錯誤索引資訊，並且錯誤索引資訊用以指示所述第一位元中被翻轉或未被翻轉的至少一第一位元。
在本發明的一範例實施例中，所述的錯誤檢查與校正電路判斷所述第二位元是否具有所述第二錯誤的操作包括：錯誤檢查與校正電路對所述第二位元執行一奇偶檢查程序以取得多個校驗子，其中每一所述第二位元是對應至所述校驗子的至少其中之一；以及錯誤檢查與校正電路根據所述校驗子判斷所述第二位元是否具有所述第二錯誤。
在本發明的一範例實施例中，所述的錯誤檢查與校正電路根據第一位元翻轉資訊對所述第二位元執行第二迭代解碼程序以取得所述第三位元的操作包括：錯誤檢查與校正電路根據第一位元翻轉資訊取得所述第二位元的一校驗權重資訊；以及錯誤檢 查與校正電路根據校驗權重資訊來翻轉所述第二位元的至少其中之一。
在本發明的一範例實施例中，所述的錯誤檢查與校正電路根據第一位元翻轉資訊取得所述第二位元的校驗權重資訊的操作包括：錯誤檢查與校正電路對第一位元翻轉資訊執行一縮放操作以產生一參考資訊；以及錯誤檢查與校正電路將參考資訊與所述第二位元的一預設校驗權重資訊相加以取得所述第二位元的校驗權重資訊。
在本發明的一範例實施例中，所述的錯誤檢查與校正電路對第一位元翻轉資訊執行縮放操作以產生參考資訊的操作包括：錯誤檢查與校正電路將第一位元翻轉資訊與一縮放參數相乘，其中縮放參數的值與一總迭代次數為負相關。
在本發明的一範例實施例中，所述的縮放參數的值更與一奇偶檢查矩陣的一行權重為負相關。
在本發明的一範例實施例中，所述的錯誤檢查與校正電路更用以記錄第二迭代解碼程序的一第二位元翻轉資訊。錯誤檢查與校正電路更用以判斷所述第三位元是否具有至少一第三錯誤。若所述第三位元具有所述第三錯誤，錯誤檢查與校正電路更用以根據第二位元翻轉資訊對所述第三位元執行一第三迭代解碼程序以取得多個第四位元，其中第二位元翻轉資訊與第一位元翻轉資訊不同。若所述第三位元不具有所述第三錯誤，錯誤檢查與校正電路更用以輸出所述第三位元。
在本發明的一範例實施例中，所述的錯誤檢查與校正電路是使用一低密度奇偶檢查演算法來編碼與解碼。
基於上述，在本發明的一範例實施例中，每一次執行的迭代解碼程序都會參考過去的位元翻轉資訊。藉此，即使所使用的解碼演算法的運算複雜度較低，解碼效率也能被提升。
為讓本發明的上述特徵和優點能更明顯易懂，下文特舉實施例，並配合所附圖式作詳細說明如下。
1000‧‧‧主機系統
1100‧‧‧電腦
1102‧‧‧微處理器
1104‧‧‧隨機存取記憶體
1106‧‧‧輸入/輸出裝置
1108‧‧‧系統匯流排
1110‧‧‧資料傳輸介面
1202‧‧‧滑鼠
1204‧‧‧鍵盤
1206‧‧‧顯示器
1208‧‧‧印表機
1212‧‧‧隨身碟
1214‧‧‧記憶卡
1216‧‧‧固態硬碟
1310‧‧‧數位相機
1312‧‧‧SD卡
1314‧‧‧MMC卡
1316‧‧‧記憶棒
1318‧‧‧CF卡
1320‧‧‧嵌入式儲存裝置
100‧‧‧記憶體儲存裝置
102‧‧‧連接介面單元
104‧‧‧記憶體控制電路單元
106‧‧‧可複寫式非揮發性記憶體模組
2202‧‧‧記憶胞陣列
2204‧‧‧字元線控制電路
2206‧‧‧位元線控制電路
2208‧‧‧行解碼器
2210‧‧‧資料輸入/輸出緩衝器
2212‧‧‧控制電路
702‧‧‧記憶胞
704‧‧‧位元線
706‧‧‧字元線
708‧‧‧共用源極線
712、714‧‧‧電晶體
400(0)~400(N)‧‧‧實體程式化單元
202‧‧‧記憶體管理電路
204‧‧‧主機介面
206‧‧‧記憶體介面
208‧‧‧錯誤檢查與校正電路
210‧‧‧緩衝記憶體
212‧‧‧電源管理電路
900‧‧‧奇偶檢查矩陣
1010、1020‧‧‧分佈
1030‧‧‧重疊區域
1101、1301、1401‧‧‧碼字
1102、1302、1402‧‧‧校驗向量
1501‧‧‧緩衝電路
1502‧‧‧邏輯運算電路
1503‧‧‧位元翻轉解碼電路
S1601、S1602、S1603、S1604、S1605、S1606、S1607‧‧‧解碼方法各步驟
圖1是根據本發明的一範例實施例所繪示的主機系統與記憶體儲存裝置的範例示意圖。
圖2是根據本發明的一範例實施例所繪示的電腦、輸入/輸出裝置與記憶體儲存裝置的範例示意圖。
圖3是根據本發明的一範例實施例所繪示的主機系統與記憶體儲存裝置的範例示意圖。
圖4是繪示圖1所示的記憶體儲存裝置的概要方塊圖。
圖5是根據本發明的一範例實施例所繪示的可複寫式非揮發性記憶體模組的概要方塊圖。
圖6是根據本發明的一範例實施例所繪示的記憶胞陣列的範例示意圖。
圖7是根據本發明的一範例實施例所繪示的管理可複寫式非 揮發性記憶體模組的範例示意圖。
圖8是根據本發明的一範例實施例所繪示的記憶體控制電路單元的概要方塊圖。
圖9是根據本發明的一範例實施例所繪示的奇耦檢查矩陣的範例示意圖。
圖10是根據本發明的一範例實施例所繪示的SLC型快閃記憶體模組的臨界電壓分佈的範例示意圖。
圖11是根據本發明的一範例實施例所繪示的矩陣相乘的範例示意圖。
圖12是根據本發明的一範例實施例所繪示的第一迭代解碼程序的範例示意圖。
圖13是根據本發明的一範例實施例所繪示的第二迭代解碼程序的範例示意圖。
圖14是根據本發明的一範例實施例所繪示的另一次矩陣相乘的範例示意圖。
圖15是根據本發明的一範例實施例所繪示的錯誤檢查與校正電路的概要方塊圖。
圖16是根據本發明的一範例實施例所繪示的解碼方法的流程圖。
一般而言，記憶體儲存裝置(亦稱，記憶體儲存系統)包括 可複寫式非揮發性記憶體模組與控制器(亦稱，控制電路)。通常記憶體儲存裝置是與主機系統一起使用，以使主機系統可將資料寫入至記憶體儲存裝置或從記憶體儲存裝置中讀取資料。
圖1是根據本發明的一範例實施例所繪示的主機系統與記憶體儲存裝置的範例示意圖。圖2是根據本發明的一範例實施例所繪示的電腦、輸入/輸出裝置與記憶體儲存裝置的範例示意圖。
請參照圖1，主機系統1000一般包括電腦1100與輸入/輸出(input/output,I/O)裝置1106。電腦1100包括微處理器1102、隨機存取記憶體(random access memory,RAM)1104、系統匯流排1108與資料傳輸介面1110。輸入/輸出裝置1106包括如圖2的滑鼠1202、鍵盤1204、顯示器1206與印表機1208。必須瞭解的是，圖2所示的裝置非限制輸入/輸出裝置1106，輸入/輸出裝置1106可更包括其他裝置。
在一範例實施例中，記憶體儲存裝置100是透過資料傳輸介面1110與主機系統1000的其他元件耦接。藉由微處理器1102、隨機存取記憶體1104與輸入/輸出裝置1106的運作可將資料寫入至記憶體儲存裝置100或從記憶體儲存裝置100中讀取資料。例如，記憶體儲存裝置100可以是如圖2所示的隨身碟1212、記憶卡1214或固態硬碟(Solid State Drive,SSD)1216等的可複寫式非揮發性記憶體儲存裝置。
圖3是根據本發明的一範例實施例所繪示的主機系統與記憶體儲存裝置的範例示意圖。
一般而言，主機系統1000為可實質地與記憶體儲存裝置100配合以儲存資料的任意系統。雖然在本範例實施例中，主機系統1000是以電腦系統來作說明，然而，另一範例實施例中，主機系統1000可以是數位相機、攝影機、通信裝置、音訊播放器或視訊播放器等系統。例如，在主機系統為數位相機(攝影機)1310時，可複寫式非揮發性記憶體儲存裝置則為其所使用的SD卡1312、MMC卡1314、記憶棒(memory stick)1316、CF卡1318或嵌入式儲存裝置1320(如圖3所示)。嵌入式儲存裝置1320包括嵌入式多媒體卡(Embedded MMC,eMMC)。值得一提的是，嵌入式多媒體卡是直接耦接於主機系統的基板上。
圖4是繪示圖1所示的記憶體儲存裝置的概要方塊圖。
請參照圖4，記憶體儲存裝置100包括連接介面單元102、記憶體控制電路單元104與可複寫式非揮發性記憶體模組106。
在本範例實施例中，連接介面單元102是相容於序列先進附件(Serial Advanced Technology Attachment,SATA)標準。然而，必須瞭解的是，本發明不限於此，連接介面單元102亦可以是符合並列先進附件(Parallel Advanced Technology Attachment,PATA)標準、電氣和電子工程師協會(Institute of Electrical and Electronic Engineers,IEEE)1394標準、高速周邊零件連接介面(Peripheral Component Interconnect Express,PCI Express)標準、通用序列匯流排(Universal Serial Bus,USB)標準、安全數位 (Secure Digital,SD)介面標準、超高速一代(Ultra High Speed-I，UHS-I)介面標準、超高速二代(Ultra High Speed-II，UHS-II)介面標準、記憶棒(Memory Stick,MS)介面標準、多媒體儲存卡(Multi Media Card,MMC)介面標準、崁入式多媒體儲存卡(Embedded Multimedia Card，eMMC)介面標準、通用快閃記憶體(Universal Flash Storage，UFS)介面標準、小型快閃(Compact Flash,CF)介面標準、整合式驅動電子介面(Integrated Device Electronics,IDE)標準或其他適合的標準。連接介面單元102可與記憶體控制電路單元104封裝在一個晶片中，或者連接介面單元102是佈設於一包含記憶體控制電路單元104之晶片外。
記憶體控制電路單元104用以執行以硬體型式或韌體型式實作的多個邏輯閘或控制指令，並且根據主機系統1000的指令在可複寫式非揮發性記憶體模組106中進行資料的寫入、讀取與抹除等運作。
可複寫式非揮發性記憶體模組106是耦接至記憶體控制電路單元104，並且用以儲存主機系統1000所寫入之資料。可複寫式非揮發性記憶體模組106可以是單階記憶胞(Single Level Cell,SLC)NAND型快閃記憶體模組、多階記憶胞(Multi Level Cell,MLC)NAND型快閃記憶體模組(即，一個記憶胞中可儲存2個位元資料的快閃記憶體模組)、複數階記憶胞(Triple Level Cell，TLC)NAND型快閃記憶體模組(即，一個記憶胞中可儲存3個位元資料的快閃記憶體模組)、其他快閃記憶體模組或其他具有相同特性的 記憶體模組。
圖5是根據本發明的一範例實施例所繪示的可複寫式非揮發性記憶體模組的概要方塊圖。圖6是根據本發明的一範例實施例所繪示的記憶胞陣列的範例示意圖。
請參照圖5，可複寫式非揮發性記憶體模組106包括記憶胞陣列2202、字元線控制電路2204、位元線控制電路2206、行解碼器(column decoder)2208、資料輸入/輸出緩衝器2210與控制電路2212。
在本範例實施例中，記憶胞陣列2202可包括用以儲存資料的多個記憶胞702、多個選擇閘汲極(select gate drain,SGD)電晶體712與多個選擇閘源極(select gate source,SGS)電晶體714、以及連接此些記憶胞的多條位元線704、多條字元線706、與共用源極線708(如圖6所示)。記憶胞702是以陣列方式(或立體堆疊的方式)配置在位元線704與字元線706的交叉點上。當從記憶體控制電路單元104接收到寫入指令或讀取指令時，控制電路2212會控制字元線控制電路2204、位元線控制電路2206、行解碼器2208、資料輸入/輸出緩衝器2210來寫入資料至記憶胞陣列2202或從記憶胞陣列2202中讀取資料，其中字元線控制電路2204用以控制施予至字元線706的電壓，位元線控制電路2206用以控制施予至位元線704的電壓，行解碼器2208依據指令中的列位址以選擇對應的位元線，並且資料輸入/輸出緩衝器2210用以暫存資料。
可複寫式非揮發性記憶體模組106中的每一個記憶胞是 以臨界電壓的改變來儲存一或多個位元。具體來說，每一個記憶胞的控制閘極(control gate)與通道之間有一個電荷捕捉層。透過施予一寫入電壓至控制閘極，可以改變電荷補捉層的電子量，因而改變了記憶胞的臨界電壓。此改變臨界電壓的程序亦稱為”把資料寫入至記憶胞”或”程式化記憶胞”。隨著臨界電壓的改變，記憶胞陣列2202的每一個記憶胞具有多個儲存狀態。並且透過讀取電壓可以判斷記憶胞是屬於哪一個儲存狀態，藉此取得記憶胞所儲存的一或多個位元。
圖7是根據本發明的一範例實施例所繪示的管理可複寫式非揮發性記憶體模組的範例示意圖。
請參照圖7，可複寫式非揮發性記憶體模組106的記憶胞702會構成多個實體程式化單元，並且此些實體程式化單元會構成多個實體抹除單元400(0)~400(N)。具體來說，同一條字元線上的記憶胞會組成一或多個實體程式化單元。若每一個記憶胞可儲存2個以上的位元，則同一條字元線上的實體程式化單元可被分類為下實體程式化單元與上實體程式化單元。例如，每一記憶胞的LSB是屬於下實體程式化單元，並且每一記憶胞的MSB是屬於上實體程式化單元。一般來說，在MLC NAND型快閃記憶體中，下實體程式化單元的寫入速度會大於上實體程式化單元的寫入速度，或下實體程式化單元的可靠度是高於上實體程式化單元的可靠度。在此範例實施例中，實體程式化單元為程式化的最小單元。即，實體程式化單元為寫入資料的最小單元。例如，實體程式化單元 為實體頁面或是實體扇(sector)。若實體程式化單元為實體頁面，則每一個實體程式化單元通常包括資料位元區與冗餘位元區。資料位元區包含多個實體扇，用以儲存使用者的資料，而冗餘位元區用以儲存系統的資料(例如，錯誤更正碼)。在本範例實施例中，每一個資料位元區包含32個實體扇，且一個實體扇的大小為512位元組(byte,B)。然而，在其他範例實施例中，資料位元區中也可包含8個、16個或數目更多或更少的實體扇，本發明並不限制實體扇的大小以及個數。另一方面，實體抹除單元為抹除之最小單位。亦即，每一實體抹除單元含有最小數目之一併被抹除之記憶胞。例如，實體抹除單元為實體區塊。
圖8是根據本發明的一範例實施例所繪示之記憶體控制電路單元的概要方塊圖。
請參照圖8，記憶體控制電路單元104包括記憶體管理電路202、主機介面204、記憶體介面206及錯誤檢查與校正電路208。
記憶體管理電路202用以控制記憶體控制電路單元104的整體運作。具體來說，記憶體管理電路202具有多個控制指令，並且在記憶體儲存裝置100運作時，此些控制指令會被執行以進行資料的寫入、讀取與抹除等運作。以下說明記憶體管理電路202的操作時，等同於說明記憶體控制電路單元104的操作，以下並不再贅述。
在本範例實施例中，記憶體管理電路202的控制指令是以韌體型式來實作。例如，記憶體管理電路202具有微處理器單 元(未繪示)與唯讀記憶體(未繪示)，並且此些控制指令是被燒錄至此唯讀記憶體中。當記憶體儲存裝置100運作時，此些控制指令會由微處理器單元來執行以進行資料的寫入、讀取與抹除等運作。
在另一範例實施例中，記憶體管理電路202的控制指令亦可以程式碼型式儲存於可複寫式非揮發性記憶體模組106的特定區域(例如，記憶體模組中專用於存放系統資料的系統區)中。此外，記憶體管理電路202具有微處理器單元(未繪示)、唯讀記憶體(未繪示)及隨機存取記憶體(未繪示)。特別是，此唯讀記憶體具有開機碼(boot code)，並且當記憶體控制電路單元104被致能時，微處理器單元會先執行此開機碼來將儲存於可複寫式非揮發性記憶體模組106中之控制指令載入至記憶體管理電路202的隨機存取記憶體中。之後，微處理器單元會運轉此些控制指令以進行資料的寫入、讀取與抹除等運作。
此外，在另一範例實施例中，記憶體管理電路202的控制指令亦可以一硬體型式來實作。例如，記憶體管理電路202包括微控制器、記憶體管理單元、記憶體寫入單元、記憶體讀取單元、記憶體抹除單元與資料處理單元。記憶體管理單元、記憶體寫入單元、記憶體讀取單元、記憶體抹除單元與資料處理單元是耦接至微控制器。其中，記憶體管理單元用以管理可複寫式非揮發性記憶體模組106的實體抹除單元；記憶體寫入單元用以對可複寫式非揮發性記憶體模組106下達寫入指令以將資料寫入至可複寫式非揮發性記憶體模組106中；記憶體讀取單元用以對可複 寫式非揮發性記憶體模組106下達讀取指令以從可複寫式非揮發性記憶體模組106中讀取資料；記憶體抹除單元用以對可複寫式非揮發性記憶體模組106下達抹除指令以將資料從可複寫式非揮發性記憶體模組106中抹除；而資料處理單元用以處理欲寫入至可複寫式非揮發性記憶體模組106的資料以及從可複寫式非揮發性記憶體模組106中讀取的資料。
主機介面204是耦接至記憶體管理電路202並且用以接收與識別主機系統1000所傳送的指令與資料。也就是說，主機系統1000所傳送的指令與資料會透過主機介面204來傳送至記憶體管理電路202。在本範例實施例中，主機介面204是相容於SATA標準。然而，必須瞭解的是本發明不限於此，主機介面204亦可以是相容於PATA標準、IEEE 1394標準、PCI Express標準、USB標準、SD標準、UHS-I標準、UHS-II標準、MS標準、MMC標準、eMMC標準、UFS標準、CF標準、IDE標準或其他適合的資料傳輸標準。
記憶體介面206是耦接至記憶體管理電路202並且用以存取可複寫式非揮發性記憶體模組106。也就是說，欲寫入至可複寫式非揮發性記憶體模組106的資料會經由記憶體介面206轉換為可複寫式非揮發性記憶體模組106所能接受的格式。
錯誤檢查與校正電路208是耦接至記憶體管理電路202並且用以執行錯誤檢查與校正程序以確保資料的正確性。具體來說，當記憶體管理電路202從主機系統1000中接收到寫入指令 時，錯誤檢查與校正電路208會為對應此寫入指令的資料產生對應的錯誤更正碼(error correcting code,ECC)及/或錯誤檢查碼(error detecting code，EDC)，並且記憶體管理電路202會將對應此寫入指令的資料與對應的錯誤更正碼或錯誤檢查碼寫入至可複寫式非揮發性記憶體模組106中。之後，當記憶體管理電路202從可複寫式非揮發性記憶體模組106中讀取資料時會同時讀取此資料對應的錯誤更正碼或錯誤檢查碼，並且錯誤檢查與校正電路208會依據此錯誤更正碼或錯誤檢查碼對所讀取的資料執行錯誤檢查與校正程序。
在一範例實施例中，記憶體控制電路單元104還包括緩衝記憶體210與電源管理電路212。
緩衝記憶體210是耦接至記憶體管理電路202並且用以暫存來自於主機系統1000的資料與指令或來自於可複寫式非揮發性記憶體模組106的資料。
電源管理電路212是耦接至記憶體管理電路202並且用以控制記憶體儲存裝置100的電源。
在此範例實施例中，錯誤檢查與校正電路208所使用的是低密度奇偶檢查校正碼(low density parity code，LDPC)。然而，在另一範例實施例中，錯誤檢查與校正電路208所使用的也可以是BCH碼、迴旋碼(convolutional code)、渦輪碼(turbo code)，但不限於此。
在此範例實施例中，錯誤檢查與校正電路208會根據一 個低密度奇偶檢查演算法來編碼與解碼。在低密度奇偶檢查校正碼中，是用一個奇偶檢查矩陣來定義有效的碼字。以下將奇偶檢查矩陣標記為矩陣H，並且一碼字標記為CW。依照以下方程式(1)，若奇偶檢查矩陣H與碼字CW的相乘是零向量，表示碼字CW為有效的碼字。其中運算子表示模2(mod 2)的矩陣相乘。換言之，矩陣H的零空間(null space)便包含了所有的有效碼字。然而，本發明並不限制碼字CW的內容。例如，碼字CW也可以包括用任意演算法所產生的錯誤更正碼或是錯誤檢查碼。
其中矩陣H的維度是k-乘-n(k-by-n)，碼字CW的維度是1-乘-n。k與n為正整數。碼字CW中包括了訊息位元與奇偶位元，即碼字CW可以表示成[M P]，其中向量M是由訊息位元所組成，向量P是由奇偶位元所組成。向量M的維度是1-乘-(n-k)，而向量P的維度是1-乘-k。以下將訊息位元與奇偶位元統稱為資料位元。換言之，碼字CW中具有n個資料位元，其中訊息位元的長度為(n-k)位元，並且奇偶位元的長度是k位元，即碼字CW的碼率(code rate)為(n-k)/n。
一般來說在編碼時會使用一個產生矩陣(以下標記為G)，使得對於任意的向量M都可滿足以下方程式(2)。其中產生矩陣G的維度是(n-k)-乘-n。
由方程式(2)所產生的碼字CW為有效的碼字。因此可將 方程式(2)代入方程式(1)，藉此得到以下方程式(3)。
由於向量M可以是任意的向量，因此以下方程式(4)必定會滿足。也就是說，在決定奇偶檢查矩陣H以後，對應的產生矩陣G也可被決定。
在解碼一個碼字CW時，會先對碼字中的資料位元執行一個奇偶檢查程序，例如將奇偶檢查矩陣H與碼字CW相乘以產生一個向量(以下標記為S，如以下方程式(5)所示)。若向量S是零向量，則可直接輸出碼字CW。若向量S不是零向量，則表示碼字CW不是有效的碼字。
向量S的維度是k-乘-1，其中每一個元素亦稱為校驗子(syndrome)。若碼字CW不是有效的碼字，則錯誤檢查與校正電路208會執行一個解碼程序，以嘗試更正碼字CW中的錯誤位元。在一範例實施例中，錯誤檢查與校正電路208所執行的解碼程序為一迭代(iteration)解碼程序。也就是說，解碼的程序會不斷的重覆執行，直到成功的解出碼字或執行次數到達一預定門檻值為止。
圖9是根據本發明的一範例實施例所繪示的奇耦檢查矩陣的範例示意圖。
請參照圖9，奇偶檢查矩陣900的維度是8-乘-9，但本發明並不限制正整數k與n為多少。奇偶檢查矩陣900的每一列(row) 亦代表了一限制(constraint)。以奇偶檢查矩陣900的第一列為例，若某一個碼字是有效碼字(valid codeword)，則將此碼字中第3、5、7與第8個位元做模2(modulo-2)的加法之後，會得到位元“0”。在此領域有通常知識者應能理解如何用奇偶檢查矩陣900來編碼，在此便不再贅述。此外，奇偶檢查矩陣900僅為一個範例矩陣，而非用以限制本發明。
當記憶體管理電路202要將多個位元寫入至可複寫式非揮發性記憶體模組106時，錯誤檢查與校正電路208會對每(n-k)個欲被寫入的位元(即，訊息位元)都產生對應的k個奇偶位元。接下來，記憶體管理電路202會把這n個位元作為一個碼字寫入至可複寫式非揮發性記憶體模組106。
圖10是根據本發明的一範例實施例所繪示的SLC型快閃記憶體模組的臨界電壓分佈的範例示意圖。
請參照圖10，橫軸代表記憶胞的臨界電壓，而縱軸代表記憶胞個數。例如，圖10是表示一個實體程式化單元中各個記憶胞的臨界電壓。在此假設當某一個記憶胞的臨界電壓是落在分佈1010時，此記憶胞所儲存的是位元“1”；相反地，若某一個記憶胞的臨界電壓是落在分佈1020時，此記憶胞所儲存的是位元“0”。值得一提的是，本範例實施例是以SLC型快閃記憶體模組為例，因此臨界電壓的分佈有兩種可能。然而，在其他範例實施例中，臨界電壓的分佈可能四種、八種或其他任意個可能，而讀取電壓可以在任意兩個分佈之間。此外，本發明也不限制每一個分佈所 代表的位元。
當要從可複寫式非揮發性記憶體模組106讀取資料時，記憶體管理電路202會發送一讀取指令序列至可複寫式非揮發性記憶體模組106。此讀取指令序列包括一或多個指令或程式碼，並且用以指示讀取一個實體程式化單元中的多個記憶胞以取得多個位元(亦稱為第一位元)。例如，根據讀取電壓1001來讀取一個實體程式化單元中的多個記憶胞。若某一個記憶胞的臨界電壓小於此讀取電壓，則此記憶胞會導通，並且記憶體管理電路202會讀到位元“1”。相反地，若某一個記憶胞的臨界電壓大於此讀取電壓，則此記憶胞不會導通，並且記憶體管理電路202會讀到位元“0”。
值得注意的是，分佈1010與分佈1020包含一個重疊區域1030。重疊區域1030表示有一些記憶胞中所儲存的應該是位元“1”(屬於分佈1010)，但其臨界電壓大於讀取電壓1001；或者，有一些記憶胞中所儲存的應該是位元“0”(屬於分佈1020)，但其臨界電壓小於讀取電壓1001。換言之，所讀取的位元中，有部份的位元會有錯誤。在另一範例實施例中，也可以從一個記憶胞中讀取出多個位元，本發明不加以限制。此外，一次的讀取也可以是讀取一個實體扇中的多個記憶胞或者任意數量的記憶胞，本發明不加以限制。
錯誤檢查與校正電路208會判斷這些第一位元是否具有一或多個錯誤(亦稱為第一錯誤)。例如，在本範例實施例中，錯誤 檢查與校正電路208會對這些第一位元執行奇偶檢查程序以取得多個校驗子(syndrome)，其中每一個第一位元是對應至這些校驗子的至少其中之一。換言之，這些校驗子可以組成上述向量S。在一範例實施例中，上述向量S亦稱為校驗向量。錯誤檢查與校正電路208會根據校驗向量S中的多個校驗子判斷這些第一位元是否具有一或多個第一錯誤。例如，若校驗向量S中的每一個校驗子都是“0”，錯誤檢查與校正電路208會判定這些第一位元不具有第一錯誤，並且判定由這些第一位元組成的碼字是有效碼字；若校驗向量S中的一或多個校驗子是“1”，則錯誤檢查與校正電路208會判定這些第一位元具有一或多個第一錯誤，並且判定由這些第一位元所組成的碼字不是有效碼字。
圖11是根據本發明的一範例實施例所繪示的矩陣相乘的範例示意圖。
請參照圖11，奇偶檢查矩陣900與碼字1101相乘的結果是校驗向量1102。碼字1101中的每一個第一位元是對應到校驗向量1102中的至少一個校驗子。舉例來說，碼字1101中的第一個第一位元V0(對應至奇偶檢查矩陣900中的第一行)是對應到校驗子S1、S4及S7；第一位元V1(對應至奇偶檢查矩陣900中的第二行)是對應到校驗子S2、S3及S6，以此類推。若第一位元V0發生了錯誤，則校驗子S1、S4及S7可能會是“1”。若第一位元V1發生了錯誤，則校驗子S2、S3及S6可能會是“1”，以此類推。
若碼字1101中的這些第一位元沒有錯誤，則表示解碼成 功，錯誤檢查與校正電路208會輸出碼字1101中的這些第一位元。若這些第一位元具有一或多個第一錯誤，錯誤檢查與校正電路208會對這些第一位元執行一迭代解碼程序(亦稱為第一迭代解碼程序)以取得多個解碼位元(亦稱為第二位元)。
在第一迭代解碼程序中，錯誤檢查與校正電路208會根據上述校驗子來取得這些第一位元的校驗權重資訊。例如，錯誤檢查與校正電路208會根據每一個第一位元所對應的校驗子來取得這些第一位元的校驗權重資訊。例如，錯誤檢查與校正電路208可以將對應至同一個第一位元的校驗子相加以取得此第一位元的校驗權重資訊。如圖11所示，第一位元V0的校驗權重資訊等於校驗子S1、S4及S7的相加；第一位元V1的校驗權重資訊等於校驗子S2、S3及S6的相加，以此類推。值得注意的是，在此對校驗子S0~S7所做的加法是一般的加法，而不是模2的加法。換言之，錯誤檢查與校正電路208可以透過以下方程式(6)來取得第一位元的校驗權重資訊。
f 1=S T ×H...(6)
其中，向量f 1 即可用來表示每一個第一位元的校驗權重資訊。
錯誤檢查與校正電路208也可以將每一個校驗子乘上一個權重，並且累加校驗子與權重相乘的結果以取得校驗權重資訊。例如，第一位元V0的校驗權重資訊會等於W1S1+W4S4+W7S7，其中權重W1、W4及W7為實數。對應於每一個校驗子的權重可以 相同也可以不同。在本範例實施例中，對應於每一個校驗子的權重都是“1”。在另一範例實施例中，錯誤檢查與校正電路208可以根據一個校驗子是“1”或“0”來決定對應於此校驗子的權重。例如，若一個校驗子是“1”，則對應於此校驗子的權重是“1”；若一個校驗子是“0”，則對應於此校驗子的權重是“-1”。或者，錯誤檢查與校正電路208也可以根據校驗子對應的第一位元的個數來決定權重。例如，校驗子S0是對應到4個第一位元，而校驗子S1是對應到3個第一位元。因此，錯誤檢查與校正電路208可以將權重W0設定的比權重W1還要小(或者大)。本發明並不限制如何設定每一個校驗子的權重。在另一範例實施例中，錯誤檢查與校正電路208也可以把校驗子S0~S7的至少其中之一當作一個函數的輸入，並且把此函數的輸出當作校驗權重資訊。此函數可以是線性函數、多項式函數、指數函數或是其他非線性函數，本發明不加以限制。
錯誤檢查與校正電路208會根據這些第一位元的校驗權重資訊來翻轉(flip)這些第一位元的至少其中之一。例如，錯誤檢查與校正電路208會將某一個或多個第一位元從“1”翻轉成“0”或者從“0”翻轉成“1”。在一範例實施例中，上述翻轉位元的操作亦稱為位元翻轉(bit flipping)。具體而言，錯誤檢查與校正電路208會判斷碼字1101中的每一個第一位元的校驗權重資訊是否符合一權重條件。例如，錯誤檢查與校正電路208會判斷每一個第一位元的校驗權重資訊的值是否大於一門檻值。若某一個第一位元的校驗權重資訊的值大於此門檻值，則錯誤檢查與校正電路208會判 定此第一位元的校驗權重資訊符合權重條件，並且翻轉此第一位元。在一範例實施例中，在每一次的迭代解碼程序中，一個碼字中最多只會有一個位元被翻轉。例如，此被翻轉的位元的校驗權重資訊的值會大於其他沒有被翻轉的位元的校驗權重資訊的值。然而，在另一範例實施例中，每一次的迭代解碼程序中，一個碼字中可以有多個位元被翻轉或是沒有任何位元被翻轉。
圖12是根據本發明的一範例實施例所繪示的第一迭代解碼程序的範例示意圖。
請參照圖12，假設碼字1101中的第一位元V0~V8分別是“1”、“0”、“0”、“1”、“0”、“0”、“0”、“0”及“0”，校驗向量1102中的校驗子S0~S7分別是“0”、“1”、“1”、“0”、“0”、“1”、“0”及“1”，並且校驗向量1102中每一個校驗子對應的權重都是“1”。根據方程式(6)，錯誤檢查與校正電路208會取得向量f 1 ，其用以表示第一位元V0~V8的校驗權重資訊分別是“2”、“1”、“2”、“2”、“1”、“2”、“1”、“1”及“1”。錯誤檢查與校正電路208可以將門檻值設為“2”，並且校驗權重資訊大於或等於“2”的第一位元V0、V2、V3及V5會被翻轉。然後，第一迭代解碼程序會輸出多個第二位元。例如，這些第二位元分別是“0”、“0”、“1”、“0”、“0”、“1”、“0”、“0”及“0”。換言之，這些第二位元包括被翻轉的多個第一位元與沒有被翻轉的多個第一位元。
另一方面，錯誤檢查與校正電路208會記錄第一迭代解碼程序的位元翻轉資訊(亦稱為第一位元翻轉資訊)。在本範例實施 例中，第一位元翻轉資訊包括一錯誤索引資訊，並且此錯誤索引資訊用以指示這些第一位元中被翻轉的一或多個第一位元或是第一位元中沒有被翻轉的一或多個第一位元。例如，此錯誤索引資訊可以是以向量e來表示。例如，在圖12的範例實施例中，向量e中的多個錯誤索引位元分別是“1”、“0”、“1”、“1”、“0”、“1”、“0”、“0”、“0”，其用以表示第一位元V0、V2、V3及V5在第一迭代解碼程序中被翻轉。
在取得這些第二位元之後，錯誤檢查與校正電路208會判斷這些第二位元是否仍具有錯誤(亦稱為第二錯誤)。例如，錯誤檢查與校正電路208會對這些第二位元執行奇偶檢查程序以取得多個校驗子，其中每一個第二位元是對應至這些校驗子的至少其中之一。錯誤檢查與校正電路208會根據這些校驗子判斷這些第二位元是否具有一或多個第二錯誤。在此，判斷這些第二位元是否具有錯誤的操作類似於上述判斷第一位元是否具有錯誤的操作，故在此不重複贅述。
若這些第二位元不具有錯誤，則表示解碼成功，錯誤檢查與校正電路208會輸出這些第二位元。若這些第二位元具有一或多個第二錯誤，錯誤檢查與校正電路208會根據所記錄的第一位元翻轉資訊對這些第二位元執行另一迭代解碼程序(亦稱為第二迭代解碼程序)以取得多個解碼位元(亦稱為第三位元)。例如，錯誤檢查與校正電路208會根據第一位元翻轉資訊取得這些第二位元的校驗權重資訊，並且根據第二位元的校驗權重資訊來翻轉 這些第二位元的至少其中之一。
在本範例實施例中，錯誤檢查與校正電路208會對第一位元翻轉資訊執行縮放(scaling)操作以產生參考資訊。在此提及的縮放操作，是指將第一位元翻轉資訊中的一或多個值放大或縮小。例如，在縮放操作中，錯誤檢查與校正電路208會將第一位元翻轉資訊與一縮放參數相乘以產生參考資訊。此外，在另一範例實施例中，縮放操作還可以包括任意的邏輯運算，本發明不加以限制。然後，錯誤檢查與校正電路208會將參考資訊與這些第二位元的一預設校驗權重資訊相加以取得這些第二位元的校驗權重資訊。上述操作也可以利用以下方程式(7)來表示。
f 2=S T ×H+α×e...(7)
其中，α是縮放參數，α的值可以是任意的整數或正整數。向量f 2 即可用來表示這些第二位元的校驗權重資訊。
圖13是根據本發明的一範例實施例所繪示的第二迭代解碼程序的範例示意圖。
請參照圖13，碼字1301是由第一迭代解碼程序產生的多個第二位元組成。將碼字1301與奇偶檢查矩陣900相乘可取得校驗向量1302。校驗向量1302中每一個校驗子對應的權重都是“1”。假設α=1，且第一位元翻轉資訊中的多個錯誤索引位元分別是“1”、“0”、“1”、“1”、“0”、“1”、“0”、“0”及“0”，則根據方程式(7)，錯誤檢查與校正電路208會取得這些第二位元的預設校驗權重資訊與向量f2。其中，這些第二位元的預設校驗權重資訊分別是 “0”、“1”、“1”、“0”、“1”、“1”、“1”、“1”及“1”，並且這些第二位元的校驗權重資訊分別是“1”、“1”、“2”、“1”、“1”、“2”、“1”、“1”及“1”。錯誤檢查與校正電路208可以將門檻值設為“2”，並且校驗權重資訊大於或等於“2”的第二位元(即，碼字1301中的第3個與第5個位元)會被翻轉。然後，第二迭代解碼程序會輸出多個第三位元。例如，這些第三位元分別是“0”、“0”、“1”、“0”、“0”、“1”、“0”、“0”及“0”。
錯誤檢查與校正電路208會記錄第二迭代解碼程序的位元翻轉資訊(亦稱為第二位元翻轉資訊)。其中，由於每一次的迭代解碼程序都可能有一或多個位元被翻轉，因此第二位元翻轉資訊會與第一位元翻轉資訊不同。例如，對應於在第二迭代解碼程序中被翻轉的第二位元，錯誤檢查與校正電路208會翻轉向量e中的第3與第6個位元，而取得更新後的向量e。例如，更新後的向量e中的多個錯誤索引位元分別是“1”、“0”、“0”、“1”、“0”、“0”、“0”、“0”及“0”。也就是說，第二位元翻轉資訊可以包括更新後的向量e。透過第二位元翻轉資訊，錯誤檢查與校正電路208可以得知在第一迭代解碼與第二迭代解碼中，碼字中的各個位元被翻轉的狀態。此外，在另一範例實施例中，第一位元翻轉資訊與第二位元翻轉資訊也可以是以其他的形式來呈現，本發明不加以限制。
錯誤檢查與校正電路208會判斷這些第三位元是否仍具有錯誤(亦稱為第三錯誤)。若這些第三位元仍具有一或多個第三錯誤，則錯誤檢查與校正電路208會根據第二位元翻轉資訊對這些 第三位元執行另一迭代解碼程序(亦稱為第三迭代解碼程序)以取得多個解碼位元(亦稱為第四位元)，並重複執行上述操作。反之，若這些第三位元不具有錯誤，則表示解碼成功，錯誤檢查與校正電路208會輸出這些第三位元。
圖14是根據本發明的一範例實施例所繪示的另一次矩陣相乘的範例示意圖。
請參照圖14，碼字1401是由第二迭代解碼程序產生的多個第三位元組成。將碼字1401與奇偶檢查矩陣900相乘可取得校驗向量1402。由於校驗向量1402中的每一個校驗子都是“0”，因此錯誤檢查與校正電路208判定碼字1401中不具有任何錯誤，並且錯誤檢查與校正電路208會輸出碼字1401中的這些第三位元。
換言之，在每一次的迭代解碼程序中，錯誤檢查與校正電路208會與被翻轉的位元有關的記錄位元翻轉資訊。在下一次的迭代解碼程序中，錯誤檢查與校正電路208會讀取此位元翻轉資訊，以更加精確的找到碼字中需要被翻轉的位元。藉此，可以減少在多次的迭代解碼程序中重覆翻轉碼字中同一個位元的機率，提升解碼效率。例如，以圖11至圖13的範例實施例為例，經過二次的迭代解碼程序就取得有效碼字。相對地，若沒有參考位元翻轉資訊，則可能會解碼失敗。
值得一提的是，雖然在上述範例實施例中都是以位元翻轉解碼演算法作為範例，然而，在另一範例實施例中，亦可以是以任意的解碼演算法來取代位元翻轉解碼演算法，本發明不加以 限制。另外，在圖12的範例實施例中，由於還沒有任何位元被翻轉過，因此可設定位元翻轉資訊為一個初始值。例如，設定向量e為一零向量。藉此，錯誤檢查與校正電路208可將圖12中的這些第一位元的校驗權重資訊視為第一位元的預設校驗權重資訊，並且根據方程式(7)來取得這些第一位元的校驗權重資訊。然而，在另一範例實施例中，位元翻轉資訊的初始值也可以設定為任意值，本發明不加以限制。
圖15是根據本發明的一範例實施例所繪示的錯誤檢查與校正電路的概要方塊圖。
請參照圖15，在本範例實施例中，錯誤檢查與校正電路208包括緩衝電路1501、邏輯運算電路1502及位元翻轉解碼電路1503。
緩衝電路1501用以儲存位元翻轉資訊。在執行迭代解碼程序時，緩衝電路1501可將位元翻轉資訊傳送至邏輯運算電路1502。邏輯運算電路1502用以對位元翻轉資訊執行縮放操作，並輸出參考資訊至位元翻轉解碼電路1503。在本範例實施例中，邏輯運算電路1502是乘法電路。然而，在另一範例實施例中，邏輯運算電路1502還可以包括任意的邏輯運算電路。位元翻轉解碼電路1503用以接收參考資訊，並且據以執行上述迭代解碼程序。此外，在另一範例實施例中，錯誤檢查與校正電路208還可以包括任意的電路，本發明不加以限制。
值得一提的是，縮放參數α的值可以是不變的或者是隨著 總迭代次數的增加而改變的。例如，在一範例實施例中，縮放參數α的值是與一總迭代次數相關，例如是成負相關(negative correlation)或正相關(positive correlation)，以下之範例實施例以負相關來說明。在圖11至13的範例實施例中，錯誤檢查與校正電路208執行過兩次迭代解碼程序，因此總迭代次數是兩次。在另一範例實施例中，若執行過三次以上的迭代解碼程序，則第三迭代解碼程序所使用的縮放參數α的值可能會大於第二迭代解碼程序所使用的縮放參數α的值。或者，若執行過三十次以上的迭代解碼程序，則第三十次的迭代解碼程序所使用的縮放參數α的值可能會大於第二十次的迭代解碼程序所使用的縮放參數α的值。
在一範例實施例中，縮放參數α的值則是與奇偶檢查矩陣的行權重(column weight)相關，以下之範例實施例以負相關來說明。例如，若奇偶檢查矩陣的每一個行的行權重都相同(例如，在圖9的範例實施例中，奇偶檢查矩陣900的每一個行的行權重都是“3”)，則可根據以下方程式(8)來取得縮放參數α。
α=2δ-γ+m...(8)
其中，δ是目前的迭代解碼程序使用的門檻值(例如，上述第一迭代解碼程序與第二跌代解碼程序的門檻值都是“2”)，γ是所使用的奇偶檢查矩陣的行權重，並且m是縮放參數的調整因子。若m的值減小，在下一次的迭代解碼程序中有較大的機率會翻轉到碼字中曾經被翻轉過的位元，因此可減少再次翻轉同一個位元的機率；若m的值增加，則在下一次的迭代解碼程序中有較 小的機率會翻轉到碼字中已經被翻轉過的位元，因此可增加碼字的收斂速度。
在一範例實施例中，隨著總迭代次數的增加，在每一次的迭代解碼程序中所使用的各個參數也可能改變。例如，在一範例實施例中，若一次的迭代解碼程序中，沒有任何一個位元需要被翻轉，則在下一次的迭代解碼程序中，所使用的門檻值會減“1”。或者，多次的迭代解碼程序亦可以使用相同的一或多個參數。例如，在連續的三次迭代解碼程序中，都使用相同的門檻值δ與縮放參數α。例如，在一範例實施例中，在開始解碼之後，門檻值δ是“5”且縮放參數α是“4”的迭代解碼程序會先被執行。若在三次迭代解碼程序中，都有符合翻轉條件(例如，校驗權重資訊大於或等於門檻值)的位元，則在第四次的迭代解碼程序中，門檻值δ仍然是“5”，但縮放參數α被改變成“4”，以此類推。在前三次的迭代解碼程序中，若某一次(例如，第二次)的迭代解碼程序中沒有任一個位元需要被翻轉，則在下一次(例如，第三次)的迭代解碼程序中，門檻值δ被改變為“4”，且縮放參數α被改變成“3”，以此類推。
另外，若奇偶檢查矩陣不具有相同的行權重，則可根據以下方程式(9)來取得縮放參數α。
α=2δ-m...(9)
在一範例實施例中，根據所使用的奇偶檢查矩陣是否具有相同的行權重，上述方程式(8)與方程式(9)可以被選擇性的用來決定縮放參數α。此外，在另一範例實施例中，縮放參數α也可以 根據其他的演算法或透過查表而獲得，本發明不加以限制。
在一範例實施例中，若一個碼字被判定為無效的碼字，則錯誤檢查與校正電路208會判斷總迭代次數是否達到一預設次數。若總迭代次數尚未達到預設次數，錯誤檢查與校正電路208會執行下一次的迭代解碼程序。若總迭代次數已達到預設次數，則錯誤檢查與校正電路208會判定解碼失敗，並且停止解碼。在一範例實施例中，若判定解碼失敗，則記憶體管理電路202可考慮使用相同或相異的讀取電壓來再次讀取可複寫式非揮發性記憶體模組106以獲得新的碼字，並且錯誤檢查與校正電路208會重新對此新的碼字進行解碼。
圖16是根據本發明的一範例實施例所繪示的解碼方法的流程圖。
請參照圖16，在步驟S1601中，發送一讀取指令序列，其中所述讀取指令序列用以讀取多個記憶胞以取得多個第一位元。在步驟S1602中，判斷所述第一位元是否具有至少一第一錯誤。若所述第一位元不具有所述第一錯誤，在步驟S1603中，輸出所述第一位元。若所述第一位元具有所述第一錯誤，在步驟S1604中，對所述第一位元執行第一迭代解碼程序以取得多個第二位元，並且記錄所述第一迭代解碼程序的第一位元翻轉資訊。在步驟S1605中，判斷所述第二位元是否具有至少一第二錯誤。若所述第二位元不具有所述第二錯誤，在步驟S1606中，輸出所述第二位元。若所述第二位元具有所述第二錯誤，在步驟S1607中， 根據所述第一位元翻轉資訊對所述第二位元執行第二迭代解碼程序以取得多個第三位元。在本範例實施例中，此解碼方法是使用密度奇偶檢查演算法來編碼與解碼。然而，在另一範例實施例中，此解碼方法亦可以是使用BCH碼、迴旋碼(convolutional code)、渦輪碼(turbo code)或其他演算法，本發明不加以限制。
然而，圖16中各步驟已詳細說明如上，在此便不再贅述。值得注意的是，圖16中各步驟可以實作為多個程式碼或是電路，本發明並不在此限。此外，圖16的方法可以搭配以上實施例使用，也可以單獨使用，本發明並不在此限。
綜上所述，在本發明的一範例實施例中，所述解碼方法、記憶體儲存裝置及記憶體控制電路單元會參考過去的位元翻轉資訊來執行迭代解碼程序。藉此，即使所使用的解碼演算法的運算複雜度較低，解碼成功的機率也能被提升。
雖然本發明已以實施例揭露如上，然其並非用以限定本發明，任何所屬技術領域中具有通常知識者，在不脫離本發明的精神和範圍內，當可作些許的更動與潤飾，故本發明的保護範圍當視後附的申請專利範圍所界定者為準。
S1601、S1602、S1603、S1604、S1605、S1606、S1607‧‧‧解碼方法各步驟

Claims (27)

  1. 一種解碼方法，用於一可複寫式非揮發性記憶體模組，該可複寫式非揮發性記憶體模組包括多個記憶胞，該解碼方法包括：發送一讀取指令序列，其中該讀取指令序列用以讀取該些記憶胞以取得多個第一位元；判斷該些第一位元是否具有至少一第一錯誤；若該些第一位元具有該至少一第一錯誤，對該些第一位元執行一第一迭代解碼程序以取得多個第二位元，並且記錄該第一迭代解碼程序的一第一位元翻轉資訊；判斷該些第二位元是否具有至少一第二錯誤；若該些第二位元具有該至少一第二錯誤，根據該第一位元翻轉資訊對該些第二位元執行一第二迭代解碼程序以取得多個第三位元；以及若該些第二位元不具有該至少一第二錯誤，輸出該些第二位元。
  2. 如申請專利範圍第1項所述的解碼方法，其中該第一位元翻轉資訊包括一錯誤索引資訊，並且該錯誤索引資訊用以指示該些第一位元中被翻轉或未被翻轉的至少一第一位元。
  3. 如申請專利範圍第1項所述的解碼方法，其中判斷該些第二位元是否具有該至少一第二錯誤的步驟包括：對該些第二位元執行一奇偶檢查(parity check)程序以取得多個校驗子(syndrome)，其中每一該些第二位元是對應至該些校驗子 的至少其中之一；以及根據該些校驗子判斷該些第二位元是否具有該至少一第二錯誤。
  4. 如申請專利範圍第1項所述的解碼方法，其中根據該第一位元翻轉資訊對該些第二位元執行該第二迭代解碼程序以取得該些第三位元的步驟包括：根據該第一位元翻轉資訊取得該些第二位元的一校驗權重資訊；以及根據該校驗權重資訊來翻轉該些第二位元的至少其中之一。
  5. 如申請專利範圍第4項所述的解碼方法，其中根據該第一位元翻轉資訊取得該些第二位元的該校驗權重資訊的步驟包括：對該第一位元翻轉資訊執行一縮放(scaling)操作以產生一參考資訊；以及將該參考資訊與該些第二位元的一預設校驗權重資訊相加以取得該些第二位元的該校驗權重資訊。
  6. 如申請專利範圍第5項所述的解碼方法，其中對該第一位元翻轉資訊執行該縮放操作以產生該參考資訊的步驟包括：將該第一位元翻轉資訊與一縮放參數相乘，其中該縮放參數的值與一總迭代次數為負相關(negative correlation)。
  7. 如申請專利範圍第6項所述的解碼方法，其中該縮放參數的值更與一奇偶檢查矩陣的一行權重(column weight)為負相關。
  8. 如申請專利範圍第1項所述的解碼方法，更包括： 記錄該第二迭代解碼程序的一第二位元翻轉資訊；判斷該些第三位元是否具有至少一第三錯誤；若該些第三位元具有該至少一第三錯誤，根據該第二位元翻轉資訊對該些第三位元執行一第三迭代解碼程序以取得多個第四位元，其中該第二位元翻轉資訊與該第一位元翻轉資訊不同；以及若該些第三位元不具有該至少一第三錯誤，輸出該些第三位元。
  9. 如申請專利範圍第1項所述的解碼方法，其中該解碼方法是使用一低密度奇偶檢查演算法來編碼與解碼。
  10. 一種記憶體儲存裝置，包括：一連接介面單元，用以耦接至一主機系統；一可複寫式非揮發性記憶體模組，包括多個記憶胞；以及一記憶體控制電路單元，耦接至該連接介面單元與該可複寫式非揮發性記憶體模組，其中該記憶體控制電路單元用以發送一讀取指令序列，其中該讀取指令序列用以讀取該些記憶胞以取得多個第一位元，該記憶體控制電路單元更用以判斷該些第一位元是否具有至少一第一錯誤，若該些第一位元具有該至少一第一錯誤，該記憶體控制電路單元更用以對該些第一位元執行一第一迭代解碼程序以取得多個第二位元，並且記錄該第一迭代解碼程序的一第一位元翻轉資訊， 該記憶體控制電路單元更用以判斷該些第二位元是否具有至少一第二錯誤，若該些第二位元具有該至少一第二錯誤，該記憶體控制電路單元更用以根據該第一位元翻轉資訊對該些第二位元執行一第二迭代解碼程序以取得多個第三位元，若該些第二位元不具有該至少一第二錯誤，該記憶體控制電路單元更用以輸出該些第二位元。
  11. 如申請專利範圍第10項所述的記憶體儲存裝置，其中該第一位元翻轉資訊包括一錯誤索引資訊，並且該錯誤索引資訊用以指示該些第一位元中被翻轉或未被翻轉的至少一第一位元。
  12. 如申請專利範圍第10項所述的記憶體儲存裝置，其中該記憶體控制電路單元判斷該些第二位元是否具有該至少一第二錯誤的操作包括：該記憶體控制電路單元對該些第二位元執行一奇偶檢查程序以取得多個校驗子，其中每一該些第二位元是對應至該些校驗子的至少其中之一，該記憶體控制電路單元根據該些校驗子判斷該些第二位元是否具有該至少一第二錯誤。
  13. 如申請專利範圍第10項所述的記憶體儲存裝置，其中該記憶體控制電路單元根據該第一位元翻轉資訊對該些第二位元執行該第二迭代解碼程序以取得該些第三位元的操作包括：該記憶體控制電路單元根據該第一位元翻轉資訊取得該些第 二位元的一校驗權重資訊，該記憶體控制電路單元根據該校驗權重資訊來翻轉該些第二位元的至少其中之一。
  14. 如申請專利範圍第13項所述的記憶體儲存裝置，其中該記憶體控制電路單元根據該第一位元翻轉資訊取得該些第二位元的該校驗權重資訊的操作包括：該記憶體控制電路單元對該第一位元翻轉資訊執行一縮放操作以產生一參考資訊，該記憶體控制電路單元將該參考資訊與該些第二位元的一預設校驗權重資訊相加以取得該些第二位元的該校驗權重資訊。
  15. 如申請專利範圍第14項所述的記憶體儲存裝置，其中該記憶體控制電路單元對該第一位元翻轉資訊執行該縮放操作以產生該參考資訊的操作包括：該記憶體控制電路單元將該第一位元翻轉資訊與一縮放參數相乘，其中該縮放參數的值與一總迭代次數為負相關。
  16. 如申請專利範圍第15項所述的記憶體儲存裝置，其中該縮放參數的值更與一奇偶檢查矩陣的一行權重為負相關。
  17. 如申請專利範圍第10項所述的記憶體儲存裝置，其中該記憶體控制電路單元更用以記錄該第二迭代解碼程序的一第二位元翻轉資訊，該記憶體控制電路單元更用以判斷該些第三位元是否具有至少一第三錯誤， 若該些第三位元具有該至少一第三錯誤，該記憶體控制電路單元更用以根據該第二位元翻轉資訊對該些第三位元執行一第三迭代解碼程序以取得多個第四位元，其中該第二位元翻轉資訊與該第一位元翻轉資訊不同；以及若該些第三位元不具有該至少一第三錯誤，該記憶體控制電路單元更用以輸出該些第三位元。
  18. 如申請專利範圍第10項所述的記憶體儲存裝置，其中該記憶體控制電路單元是使用一低密度奇偶檢查演算法來編碼與解碼。
  19. 一種記憶體控制電路單元，用於控制一可複寫式非揮發性記憶體模組，其中該可複寫式非揮發性記憶體模組包括多個記憶胞，該記憶體控制電路單元包括：一主機介面，用以耦接至一主機系統；一記憶體介面，用以耦接至該可複寫式非揮發性記憶體模組；一記憶體管理電路，耦接至該主機介面與該記憶體介面，並且用以發送一讀取指令序列，其中該讀取指令序列用以讀取該些記憶胞以取得多個第一位元；以及一錯誤檢查與校正電路，耦接至該記憶體管理電路，並且用以判斷該些第一位元是否具有至少一第一錯誤，若該些第一位元具有該至少一第一錯誤，該錯誤檢查與校正電路更用以對該些第一位元執行一第一迭代解碼程序以取得多個第二位元，並且記錄該第一迭代解碼程序的一第一位元翻轉資訊， 該錯誤檢查與校正電路更用以判斷該些第二位元是否具有至少一第二錯誤，若該些第二位元具有該至少一第二錯誤，該錯誤檢查與校正電路更用以根據該第一位元翻轉資訊對該些第二位元執行一第二迭代解碼程序以取得多個第三位元，若該些第二位元不具有該至少一第二錯誤，該錯誤檢查與校正電路更用以輸出該些第二位元。
  20. 如申請專利範圍第19項所述的記憶體控制電路單元，其中該第一位元翻轉資訊包括一錯誤索引資訊，並且該錯誤索引資訊用以指示該些第一位元中被翻轉或未被翻轉的至少一第一位元。
  21. 如申請專利範圍第19項所述的記憶體控制電路單元，其中該該錯誤檢查與校正電路判斷該些第二位元是否具有該至少一第二錯誤的操作包括：該錯誤檢查與校正電路對該些第二位元執行一奇偶檢查程序以取得多個校驗子，其中每一該些第二位元是對應至該些校驗子的至少其中之一，該錯誤檢查與校正電路根據該些校驗子判斷該些第二位元是否具有該至少一第二錯誤。
  22. 如申請專利範圍第19項所述的記憶體控制電路單元，其中該錯誤檢查與校正電路根據該第一位元翻轉資訊對該些第二位元執行該第二迭代解碼程序以取得該些第三位元的操作包括： 該錯誤檢查與校正電路根據該第一位元翻轉資訊取得該些第二位元的一校驗權重資訊，該錯誤檢查與校正電路根據該校驗權重資訊來翻轉該些第二位元的至少其中之一。
  23. 如申請專利範圍第22項所述的記憶體控制電路單元，其中該錯誤檢查與校正電路根據該第一位元翻轉資訊取得該些第二位元的該校驗權重資訊的操作包括：該錯誤檢查與校正電路對該第一位元翻轉資訊執行一縮放操作以產生一參考資訊，該錯誤檢查與校正電路將該參考資訊與該些第二位元的一預設校驗權重資訊相加以取得該些第二位元的該校驗權重資訊。
  24. 如申請專利範圍第23項所述的記憶體控制電路單元，其中該錯誤檢查與校正電路對該第一位元翻轉資訊執行該縮放操作以產生該參考資訊的操作包括：該錯誤檢查與校正電路將該第一位元翻轉資訊與一縮放參數相乘，其中該縮放參數的值與一總迭代次數為負相關。
  25. 如申請專利範圍第24項所述的記憶體控制電路單元，其中該縮放參數的值更與一奇偶檢查矩陣的一行權重為負相關。
  26. 如申請專利範圍第19項所述的記憶體控制電路單元，其中該錯誤檢查與校正電路更用以記錄該第二迭代解碼程序的一第二位元翻轉資訊，該錯誤檢查與校正電路更用以判斷該些第三位元是否具有至 少一第三錯誤，若該些第三位元具有該至少一第三錯誤，該錯誤檢查與校正電路更用以根據該第二位元翻轉資訊對該些第三位元執行一第三迭代解碼程序以取得多個第四位元，其中該第二位元翻轉資訊與該第一位元翻轉資訊不同；以及若該些第三位元不具有該至少一第三錯誤，該錯誤檢查與校正電路更用以輸出該些第三位元。
  27. 如申請專利範圍第19項所述的記憶體控制電路單元，其中該錯誤檢查與校正電路是使用一低密度奇偶檢查演算法來編碼與解碼。
TW103120045A 2014-06-10 2014-06-10 解碼方法、記憶體儲存裝置及記憶體控制電路單元 TWI543178B (zh)

Priority Applications (2)

Application Number Priority Date Filing Date Title
TW103120045A TWI543178B (zh) 2014-06-10 2014-06-10 解碼方法、記憶體儲存裝置及記憶體控制電路單元
US14/475,585 US9543983B2 (en) 2014-06-10 2014-09-03 Decoding method, memory storage device and memory control circuit unit

Applications Claiming Priority (1)

Application Number Priority Date Filing Date Title
TW103120045A TWI543178B (zh) 2014-06-10 2014-06-10 解碼方法、記憶體儲存裝置及記憶體控制電路單元

Publications (2)

Publication Number Publication Date
TW201546815A true TW201546815A (zh) 2015-12-16
TWI543178B TWI543178B (zh) 2016-07-21

Family

ID=54770412

Family Applications (1)

Application Number Title Priority Date Filing Date
TW103120045A TWI543178B (zh) 2014-06-10 2014-06-10 解碼方法、記憶體儲存裝置及記憶體控制電路單元

Country Status (2)

Country Link
US (1) US9543983B2 (zh)
TW (1) TWI543178B (zh)

Cited By (2)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
TWI645698B (zh) * 2017-07-17 2018-12-21 財團法人工業技術研究院 資料發送裝置、資料接收裝置及其方法
CN112865920A (zh) * 2016-12-30 2021-05-28 慧荣科技股份有限公司 用以解码接收信息的解码方法与相关解码装置

Families Citing this family (15)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
KR102559925B1 (ko) * 2016-07-21 2023-07-26 에스케이하이닉스 주식회사 Ldpc 디코더, 반도체 메모리 시스템 및 그것의 동작 방법
TWI607452B (zh) * 2016-08-12 2017-12-01 群聯電子股份有限公司 解碼方法、記憶體儲存裝置及記憶體控制電路單元
TWI632780B (zh) * 2016-12-30 2018-08-11 慧榮科技股份有限公司 解碼方法與相關解碼裝置
KR102830789B1 (ko) * 2017-01-23 2025-07-07 에스케이하이닉스 주식회사 메모리 시스템 및 메모리 시스템의 동작 방법
US10996739B2 (en) * 2017-12-19 2021-05-04 Microsoft Technology Licensing, Llc Reducing power consumption in a neural network environment using data management
US10514980B2 (en) 2018-03-22 2019-12-24 Winbond Electronics Corp. Encoding method and memory storage apparatus using the same
CN110391815B (zh) * 2018-04-18 2023-08-18 深圳大心电子科技有限公司 解码方法及储存控制器
CN110716824B (zh) * 2018-07-13 2023-08-15 华邦电子股份有限公司 编码方法及使用所述编码方法的存储器存储装置
US10707901B2 (en) * 2019-01-08 2020-07-07 Intel Corporation Die-wise residual bit error rate (RBER) estimation for memories
CN111782438B (zh) * 2019-04-04 2022-08-05 西南科技大学 一种改进的抗辐射加固矩阵码译码电路
TWI697000B (zh) * 2019-12-09 2020-06-21 慧榮科技股份有限公司 記憶體控制器及快閃記憶體的存取方法
US11385833B2 (en) * 2020-04-20 2022-07-12 Alibaba Group Holding Limited Method and system for facilitating a light-weight garbage collection with a reduced utilization of resources
US11533064B2 (en) 2020-11-09 2022-12-20 Micron Technology, Inc. Error correcting code poisoning for memory devices and associated methods and systems
US11379305B2 (en) * 2020-11-16 2022-07-05 Western Digital Technologies, Inc. Fast verification of non-volatile data integrity
CN117331743B (zh) * 2022-06-24 2025-11-11 华为技术有限公司 一种译码方法、芯片及相关装置

Family Cites Families (10)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US8261170B2 (en) * 2007-06-19 2012-09-04 Mitsubishi Electric Research Laboratories, Inc. Multi-stage decoder for error-correcting codes
KR101526317B1 (ko) * 2008-05-09 2015-06-11 삼성전자주식회사 계층적 디코딩 장치
WO2010001502A1 (ja) * 2008-06-30 2010-01-07 国立大学法人愛媛大学 復号化装置、垂直磁気記録再生装置、受信装置、および、復号化方法
US8438461B2 (en) * 2009-10-12 2013-05-07 Marvell World Trade Ltd. Power consumption in LDPC decoder for low-power applications
US8645810B2 (en) * 2011-07-31 2014-02-04 Sandisk Technologies Inc. Fast detection of convergence or divergence in iterative decoding
US8707144B2 (en) * 2011-10-17 2014-04-22 Lsi Corporation LDPC decoder with targeted symbol flipping
US9009578B1 (en) * 2011-11-11 2015-04-14 Marvell International Ltd. Methodology for improved bit-flipping decoder in 1-read and 2-read scenarios
US8850295B2 (en) * 2012-02-01 2014-09-30 Lsi Corporation Symbol flipping data processor
US8904263B1 (en) * 2012-03-23 2014-12-02 Sk Hynix Memory Solutions Inc. Error correction capability improvement in the presence of hard bit errors
US8739004B2 (en) * 2012-05-10 2014-05-27 Lsi Corporation Symbol flipping LDPC decoding system

Cited By (3)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
CN112865920A (zh) * 2016-12-30 2021-05-28 慧荣科技股份有限公司 用以解码接收信息的解码方法与相关解码装置
TWI645698B (zh) * 2017-07-17 2018-12-21 財團法人工業技術研究院 資料發送裝置、資料接收裝置及其方法
US10742783B2 (en) 2017-07-17 2020-08-11 Industrial Technology Research Institute Data transmitting apparatus, data receiving apparatus and method thereof having encoding or decoding functionalities

Also Published As

Publication number Publication date
US20150358036A1 (en) 2015-12-10
TWI543178B (zh) 2016-07-21
US9543983B2 (en) 2017-01-10

Similar Documents

Publication Publication Date Title
TWI543178B (zh) 解碼方法、記憶體儲存裝置及記憶體控制電路單元
TWI540586B (zh) 解碼方法、記憶體儲存裝置、記憶體控制電路單元
TWI541820B (zh) 解碼方法、記憶體控制電路單元及記憶體儲存裝置
TWI537966B (zh) 錯誤處理方法、記憶體儲存裝置及記憶體控制電路單元
TWI521529B (zh) 解碼方法、記憶體儲存裝置及記憶體控制電路單元
CN104601178B (zh) 解码方法、解码电路、存储器存储装置与控制电路单元
TWI512732B (zh) 解碼方法、記憶體儲存裝置與非揮發性記憶體模組
TWI612527B (zh) 解碼方法、記憶體儲存裝置及記憶體控制電路單元
TWI523018B (zh) 解碼方法、記憶體儲存裝置、記憶體控制電路單元
US20160062828A1 (en) Data accessing method, memory storage device and memory controlling circuit unit
TWI527382B (zh) 解碼方法、解碼電路、記憶體儲存裝置與控制電路單元
US10193569B2 (en) Decoding method, memory storage device and memory control circuit unit
CN104733051B (zh) 奇偶校验码的解码方法、存储器储存装置及控制电路单元
TWI594255B (zh) 解碼方法、記憶體控制電路單元及記憶體儲存裝置
TWI672698B (zh) 記憶體控制方法、記憶體儲存裝置及記憶體控制電路單元
TW202022861A (zh) 記憶體控制方法、記憶體儲存裝置及記憶體控制電路單元
CN105304142B (zh) 解码方法、存储器存储装置及存储器控制电路单元
CN104424045B (zh) 解码方法、存储器储存装置与非易失性存储器模块
TWI536749B (zh) 解碼方法、記憶體儲存裝置與記憶體控制電路單元
CN105023613A (zh) 解码方法、存储器存储装置及存储器控制电路单元
CN105022674A (zh) 解码方法、存储器存储装置、存储器控制电路单元
CN104851458A (zh) 解码方法、存储器存储装置与存储器控制电路单元
CN105304143B (zh) 解码方法、存储器控制电路单元及存储器存储装置
CN105575440B (zh) 错误处理方法、存储器储存装置及存储器控制电路单元
TWI702602B (zh) 解碼方法、記憶體儲存裝置及記憶體控制電路單元