糾錯編碼算法(Error Correction Code, ECC)是傳輸過程中發(fā)生錯誤后能在接收端自行發(fā)現(xiàn)并糾正的碼。早期被廣泛應用于通信領域，在發(fā)送端完成數(shù)據(jù)編碼，在接收端完成數(shù)據(jù)譯碼，保證數(shù)據(jù)的可靠傳輸。NAND Flash作為一種廣泛使用的存儲介質，容易受到PE次數(shù)、數(shù)據(jù)保存時間、溫度和Cell間干擾等因素的影響，數(shù)據(jù)寫入后再讀出無法保證絕對的正確性，因此需要ECC算法做數(shù)據(jù)恢復。

在2D NAND Flash時代，SSD控制器一般采用BCH編碼保護數(shù)據(jù)正確性，BCH的幾個特性

1. 對于固定的碼長和碼率，有一組固定的生成多項式和校驗多項式，不需要單獨設計;

2. 有相對固定的編碼和譯碼算法;

3. 當錯誤數(shù)據(jù)個數(shù)小于一個指定值時，可以100%恢復數(shù)據(jù);當數(shù)據(jù)錯誤個數(shù)大于這個指定值時，100%不能恢復數(shù)據(jù);

4. BCH編碼只能接收硬信息，即一個有效數(shù)據(jù)只能用1 bit表示;

但是隨著3D NAND Flash技術的逐步成熟，3D NAND Flash表現(xiàn)出了更好的可靠性。因此，原本采用2D MLC的產(chǎn)品紛紛轉投3D TLC(可靠性對比： 2D MLC > 3D TLC > 2D TLC)，對SSD主控的ECC編碼提出了更高的要求，因此，具備更強糾錯能力的低密度奇偶校驗編碼(Low Density Parity Check, LDPC)越來越多的被采用。

相對于BCH，LDPC具備以下特性：

1. 對于固定的碼長和碼率，需要單獨設計編譯碼使用的矩陣(通常指校驗矩陣);

2. 有多種解碼算法，但是***的糾錯算法計算復雜度太高，無法硬件化，需要權衡算法特點和譯碼精度，簡化算法;

3. 可以接收軟信息(即一個有效數(shù)據(jù)可以用多個 bit表示)，這是LDPC取代BCH的主要原因;

4. 譯碼成功或失敗沒有絕對的界線，即可能在只錯幾個bit的情況下無法成功糾錯，但可以成功完成200 bit錯誤的數(shù)據(jù)譯碼;

5. 相同碼率情況下，碼長越長，糾錯能力越強;

詳細解釋一下以上5個特性：

1. 低密度奇偶校驗碼的低密度是指其校驗矩陣的稀疏性(在一個只有“0”元素和“1”元素的矩陣中，“1”元素的比例很低)。LDPC編碼和譯碼都可以利用校驗矩陣，矩陣的低密度意味著編譯碼算法的低復雜度、低運算量。對于固定碼長和碼率的LDPC碼，校驗矩陣有很多種，但是設計一個運算量小，復雜度低且糾錯能力強的校驗矩陣成為LDPC編碼應用的一個難點。

LDPC校驗矩陣H

2. 麻省理工學院Robert Gallager于1963年在博士論文中提出LDPC碼，但因其復雜的譯碼算法不易實現(xiàn)，并沒有被廣泛采用。1981年，Tanner提出了用圖模型來描述碼字的概念，從而將LDPC碼的校驗矩陣對應到被稱為Tanner圖的雙向圖上，采用Tanner 圖構造的LDPC碼，通過并行譯碼可以顯著地降低譯碼復雜度。

校驗矩陣H對應的Tanner

此后，越來越多的LDPC譯碼算法出現(xiàn)，其中***的是比特翻轉算法(Bit Flipping Algorithm)和最小和算法(Min-Sum Algorithm)。同時也出現(xiàn)了很多基于以上2種糾錯算法的變種算法，用較小的代價提高了譯碼精度。

下圖描述了一個編碼后數(shù)據(jù)位“1101”，在信道上傳輸后變?yōu)?ldquo;1001”后接收端的比特翻轉譯碼的過程。

經(jīng)過一次迭代后，錯誤bit被糾正。

3.軟信息是用多bit表示一個bit的值，即等價于可以用多位精度表示一個信息的置信度。

用硬信息表示一個信息，只有“0”或“1”。而軟信息更精確的表達了一個信息的置信度，軟信息可以有“0.1”、“0.4”、“0.65”、“0.99”等表達方式。有了軟信息，在相同碼率下譯碼器可以糾正更多的錯誤。

但是存儲不同于通信領域，存儲器讀出的數(shù)據(jù)只能是0或者1。因此，軟信息的獲取只能通過改變存儲器讀方式，多次讀取才能獲得。多次讀取同一個信息必然造成讀性能的下降，因此，在SSD控制器上，盡可能減少使用軟信息做譯碼的概率。

4. LDPC是一種概率譯碼算法，在不同的錯誤率的情況下均有一個譯碼成功概率，并且這個概率具備一個明顯的特點。當待譯碼數(shù)據(jù)錯率低時，LDPC譯碼失敗概率很低，可以低至1E-15，但是很難做到0失敗，主要原因是對于每個矩陣都存在一個陷阱集，當陷阱集中包含的位置的點發(fā)生數(shù)據(jù)錯誤，LDPC便無法成功譯碼。隨著錯誤率逐漸增加，譯碼失敗概率會快速增加到接近100%失敗。

5.對于BCH和LDPC，在相同碼率下，碼長越長，糾錯能力越強。對于市場上流行的3D TLC Flash的頁大小(頁大小決定糾錯算法碼率)，我們比較了2KB/4KB BCH和2KB/4KB LDPC硬判決譯碼的糾錯能力。當碼長增加時，相同的譯碼算法以及相同的碼率下，糾錯能力提升了近50%。長碼長ECC算法的應用，更好的提高了糾錯算法的能力，推遲了SSD主控啟用LDPC軟判決譯碼的使用，減少軟判決譯碼帶來的負面影響(性能和功耗方面)。

總結：

數(shù)據(jù)正確性是SSD最基本的要求，糾錯編碼保證了數(shù)據(jù)萬無一失。隨著更多新的Flash結構出現(xiàn)，糾錯編碼算法也在逐步演進。LDPC算法***限度的保證了數(shù)據(jù)的正確性。并且，隨著越來越多SSD主控采用4KB LDPC，更好的延長了SSD的壽命。