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

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

1. 對(duì)于固定的碼長(zhǎng)和碼率，有一組固定的生成多項(xiàng)式和校驗(yàn)多項(xiàng)式，不需要單獨(dú)設(shè)計(jì);

2. 有相對(duì)固定的編碼和譯碼算法;

3. 當(dāng)錯(cuò)誤數(shù)據(jù)個(gè)數(shù)小于一個(gè)指定值時(shí)，可以100%恢復(fù)數(shù)據(jù);當(dāng)數(shù)據(jù)錯(cuò)誤個(gè)數(shù)大于這個(gè)指定值時(shí)，100%不能恢復(fù)數(shù)據(jù);

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

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

相對(duì)于BCH，LDPC具備以下特性：

1. 對(duì)于固定的碼長(zhǎng)和碼率，需要單獨(dú)設(shè)計(jì)編譯碼使用的矩陣(通常指校驗(yàn)矩陣);

2. 有多種解碼算法，但是***的糾錯(cuò)算法計(jì)算復(fù)雜度太高，無(wú)法硬件化，需要權(quán)衡算法特點(diǎn)和譯碼精度，簡(jiǎn)化算法;

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

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

5. 相同碼率情況下，碼長(zhǎng)越長(zhǎng)，糾錯(cuò)能力越強(qiáng);

詳細(xì)解釋一下以上5個(gè)特性：

1. 低密度奇偶校驗(yàn)碼的低密度是指其校驗(yàn)矩陣的稀疏性(在一個(gè)只有“0”元素和“1”元素的矩陣中，“1”元素的比例很低)。LDPC編碼和譯碼都可以利用校驗(yàn)矩陣，矩陣的低密度意味著編譯碼算法的低復(fù)雜度、低運(yùn)算量。對(duì)于固定碼長(zhǎng)和碼率的LDPC碼，校驗(yàn)矩陣有很多種，但是設(shè)計(jì)一個(gè)運(yùn)算量小，復(fù)雜度低且糾錯(cuò)能力強(qiáng)的校驗(yàn)矩陣成為L(zhǎng)DPC編碼應(yīng)用的一個(gè)難點(diǎn)。

LDPC校驗(yàn)矩陣H

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

校驗(yàn)矩陣H對(duì)應(yīng)的Tanner

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

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

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

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

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

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

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

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

總結(jié)：

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