解碼設備的製作方法

2023-10-04 04:08:34

專利名稱：解碼設備的製作方法
技術領域：
本發明涉及一種用於對LDPC碼才丸行解碼處理的解碼i殳備。
背景技術：
近年來，例如，在包括移動通信和深空通信的的通信領域以及 包括地波廣播或衛星數字廣播的廣播領域中，已經並且正在顯著進 行研究。連同該研究，還在積極地進行與編碼理論相關的研究，以 才是高糾4昔編碼和解碼的效率。
作為碼性能的理論極限，已知通過香農(C.E.Shannon)的信道 編碼理論提供的香農極限。為了開發表現出與香農極限近似性能的 碼，進行了關於碼理論的研究。近年來，作為表現出與香農極限接 近的性能的編碼方法，已經開發出稱為巻積碼(諸如並行級耳關巻積 碼(PCCC)或串行級聯巻積碼(SCCC))的技術。雖然開發出了 這樣的巻積碼，但是關注的卻是作為長期以來已知的編碼方法的低 密度奇偶校驗碼(以下稱為LDPC碼)。
LDPC碼首先由R.GGallager才是出，"Low density parity check codes" , Cambridge, Massachusetts: M. I. T. Press, 1963。 ot匕後，又#皮D.J.C.Mackay, "Good error correction codes based on very sparse matrices", IEEE Trans. Inf. Theory, IT-45, pp.399-431， 1999、 M.G. Luby， M. Mitzenmacher, M. A. Shokrollahi和D.A.Spielman在關於計 算J裡"i侖的學才艮中的 "Analysis of low density codes and improved designs using irregular graphs" ， pp.249-258,1998等所關注。
通過近年來的研究發現，隨著LDPC碼的碼長增加，通過巻積 碼等同樣獲得與香農才及限近似的性能。而且，由於LDPC碼具有最 小距離與碼長成比例地增加的特性，所以他們具有表現出良好的相無 率特性的特徵，並且有利之處還在於，在LDPC石馬中，4艮少會出iE見 從巻積碼的解碼特;f正等》見察到的誤碼平臺現象，如在R. G. Gallager 戶斤才皮露的，"Low density parity check codes" , IRE Trans. Inform. Theory, vol. 8, pp.21-28, Jan., 1962 (以下《爾為非專利文獻1 )。
LDPC碼是通過包括很少量的非零值元素的稀疏奇偶校驗矩陣 H定義的線性碼，並且非零值元素的數量在校驗矩陣H的行和歹'J中 固定的那些碼被稱為規則LDPC碼，而除了所述碼之外的那些碼被 稱為不^L則LDPC石馬。
按以下方式執行LDPC碼的編碼。特別，對校驗矩陣H應用高 斯消去法和適當列的替換以產生產生矩陣G，並且基於K個信息位 的矢量s和產生矩陣G產生n位的碼字的矢量c。編碼的進一步詳 十青4皮才皮露於G. J. C. Mackay發表的"Good error correction codes based on very sparse matrices" , IEEE Trans. Inf. Theory, IT-45, pp.399-431， 1999年10月(以下稱為非專利文獻2)。
作為用於LDPC石馬的典型解石馬方法，可以採用和積解碼方法。 和積解碼方法基本上等同於稱為置信傳播(BP)的算法。此外，通過基於在限定LDPC碼的Tanner圖上才喿作的消息傳遞 算法的迭代解碼算法來對LDPC碼進行解碼。
在Tanner圖上，每個變量節點對應於41-驗矩陣H的一列，以及 每個校驗節點對應於校驗矩陣H的一行。此外，當算法的目標是確 定對應於來自接收到的值的每個傳輸符號的後驗概率時，由於 LDPC碼的Tanner圖通常包4舌回3各，所以不能通過BP計算出^青確 的後-驗概率，^旦可以使用近似計算法。然而，已知當圖稀疏時，近 似技術提供了較好的結果。
同樣還提出了算法(分層BP算法)，其中，通過為校驗矩陣的 每行將消息P從變量節點更新到校驗節點，消息(3用於在和積解碼 方法中將消息a從校驗節點更新到變量節點，即使迭代的次數很小， 寸旦是仍可以實現與普通和積解碼方法的性能相似的性能並且還可以 減小存儲量。分層BP算法被披露於例如D.E. Hocevar發表的"A reduced complexity decoder architecture via layered decoding of LDPC codes" IEEE Workshop on Signal Processing Systems, pp. 107-122， 2004 (以下-爾為非專利文獻3 )。
在這樣的LDPC解碼過程中，必須/人關於一個碼字的對悽t似然 矢量？ ？iN]或對數後驗概率矢量Q = [q! q2 ... qn ... qN]
內選擇校驗矩陣H的每行中滿足hmn= 1的那些元素，其中，M行 和N列的校驗矩陣H的第n列的第m行中的元素由h^表示。例如， 如果假設NH個集合滿足hmn = 1並且時間間隔由Ts表示，那麼必須 2 x NH x Ts的時間，從而對每個集合執行從變量節點到校驗節點的 消息的更新以及4丸行從校-驗節點到變量節點的消息的更新。另夕卜， 如果從變量節點到校驗節點的消息的更新和從校驗節點到變量節點 的消息的更新^皮分別重複^l^於了 Ni次，則對4妄收碼字進4於解碼所需 的時間是2xNhxN!xTs。通常，允許用於解碼的等待時間在多悽t '清況下〗氐於2 x NH x N！ x Ts,並且有些7#以結合該配置。因此，在所有節點同時^M亍用於消息更新的計算的和積解石馬方 法已經被提出並披露於C， Howland和A. Blanksby發表的"Parallel Decoding Architectures for Low Density Parity Check Codes" IEEE International Symposium on Circuits and Systems, vol. 4, pp. 742-745, May. 2001 (以下稱為非專利文獻4)。在和積解碼方法的配置中，由 於在一個時鐘內扭一f亍NH個集合的計算，所以解碼所需的時間為2 x N!xTs，並因此，可以顯著減少等4寺時間。
另外，還提出了一種配置，其中，對校驗矩陣執行行替換或列 替換，從而將校驗矩陣轉換為另一個校驗矩陣，該另一個校驗矩陣 可以由諸如Pxp個單位矩陣的成分矩陣、單位矩陣的成分中的一 個或多個1變為0的準單^f立矩陣、通過只於單4立矩陣或準單4立矩陣進 行循環移位獲得的移位矩陣、為多個單位矩陣、準單位矩陣和移位 矩陣或Pxp零矩陣的總和的和矩陣的成分矩陣的組合來表示。通 過該配置，可以在LDPC碼的解碼過程中執行從校驗節點到變量節 點的消息的更新，並且對P個消息並行地4丸行關於乂人變量節點到才交 驗節點的消息的更新的計算。所述配置械j皮露於例如日本專利公開 No. 2004-343170 (以下一爾為專利文獻1 )。通過該配置，可以^1尋電3各 尺寸抑制在可實現的範圍內，同時抑制了用於進4亍解碼的時鐘數。 在該配置的情況下，解碼所需的時間是2xNHxN!xTs/P。在校驗 矩陣由上述成分矩陣的結合表示的情況下，其中為0矩陣的每個成 分矩陣被1替換而為非零矩陣的每個成分矩陣被1替換的M/P行和 N/P列的矩陣被稱為權重矩陣。

發明內容
然而，非專利文獻4的糹支術存在由於必須糹丸^f於關於在所有節點 處的並行消息更新的計算而需要增加電路尺寸的問題。此外，根據 該才支術，由於節點之間的連4妄是通過配線建立的，所以存在難以在 多個校驗矩陣之間共享解碼器的問題。ot匕外，在分層BP解石馬方法的情況下，可以4吏用一種配置，其
中，在校驗矩陣的每行中滿足hmn-l的多個對數後驗概率qn被同時 讀出，並且關於對校驗矩陣的一行的消息更新的計算被並行執行。 然而，為了實現該配置，選擇器必需將對數後驗概率qn存儲到寄存
器中並且從例如等於碼長(即，等於N )的多個對凌t後驗概率qn中
選擇在每行中滿足hmfl的多個後驗概率qn的選擇器。通常，由於
LDPC碼的碼長為幾千~幾萬，所以估計該配置需要增加電路尺寸。
此外，取決於將結合到用於下一代無線LAN等的情況中的應 用，所需的等待時間非常嚴^f各，以至於通過專利文獻1的配置也不 能夠滿足。
因此，需要提供一種可以通過簡單配置高速執行用於LDPC碼 的解碼處理的解碼裝置。
根據本發明的一個實施例，提供了 一種用於對低密度奇偶校驗 碼進行解碼的解碼裝置，包括多個存儲部，被配置為將關於一個 碼字的對悽t似然率或對數後-驗相無率存儲到相互獨立的地址中；以及 讀出部，被配置成/人存儲在存儲部中的關於一個碼字的對悽t似然率 或對數後驗概率中，同時讀出與在低密度奇偶校驗碼的編碼處理中 4吏用的才交驗矩陣的預定一4亍中的非零值元素相對應的多個對悽t似然 率或》於^:後-驗;f既率。
存儲部的數量可以'J 、於校驗矩陣的行權重的最大值。
在該實例中，從存儲部讀出與校驗矩陣的任一行中的非零值對 應的所有的那些對ft似然率或後 -驗扭X率所需的讀出次f史可以是通過 用校驗矩陣的行權重的最大值除以存儲部的數量獲得的值向上捨入 成數字值獲得的數。在該實例中，解碼裝置可以進一步包括存儲位置確定部，祐:
配置成將關於 一 個碼字的對數似然率或對數後驗概率存儲到存儲部 中，以使與校驗矩陣的任一行中的非零值元素對應的所有的對數似 然率或對悽t後驗相無率，能夠以通過用4交驗矩陣的行權重的最大值除 以存儲部的數量獲得的值向上捨入成數字值獲得的讀出次數從存儲 部中讀出。
在該實例中，解碼裝置可以^皮配置成使得每個所述存儲部均具
陣的列數除以所述存儲部的數量獲得的值、或通過將所獲得的值加 一得到的值、或通過從所獲得的值中減一得到的值相對應的地址數， 並且關於所述一個碼字的所述對lt似然率或對悽史後-瞼相無率^皮分別存 yf諸到所述存儲部中。
在該實例中，解碼裝置可以:帔配置成使存^f諸位置確定產生用於 指定存儲部之一和其中存儲有關於一個碼字的對數似然率或對數後 驗概率中的每個的地址的存儲位置確定信息，並且讀出部基於存儲
位置確定信息來同時讀出多個對4故似然率或對#:後-驗相無率。
在校驗矩陣包括具有P行和P列的多個小矩陣的情況下，與每 個小矩陣的P個元素相對應的對數似然率或對數後驗概率中的P個 可以被存儲到存儲部之一的一個地址中。
在解碼裝置中，關於一個碼字的對^t似然率或對悽t後-驗和無率祐L 存儲到相互獨立的地址中。然後，從存儲在存儲部中的關於一個碼 字的對數似然率或對數後驗相無率中，同時讀出與在低密度奇偶4交馬金 碼的編碼處理中使用的校驗矩陣的預定一行中的非零值元素相對應 的多個乂於悽"以然率或對1t後-瞼和無率。通過這種解碼裝置，可以用簡單的配置高速地4丸^^氐密度奇偶 才交-驗碼的解碼處理。
從以下描述和所附的權利要求並結合附圖將顯而易見本發明的 以上和其他特徵和優點，在附圖中，相似部件或元件用相同的參考 符號來表示。


圖1是示出了 Tanner圖的實例的示圖2是示出了 RAM的不適當存儲位置的實例的示意圖3是示出了 RAM的適當存儲位置的實例的示意圖4是示出了應用本發明實施例的解碼裝置的配置實例的框
圖5是示出了通過圖4所示的控制器執行的軟體的功能配置實 例的框圖6是示出了存儲位置確定處理的實例的流程圖； 圖7是示出了存儲位置候選產生處理的實例的流程圖； 圖8是示出了存儲位置候選校驗處理的實例的流程圖； 圖9是示出了解碼處理的實例的流程圖10是示出了應用本發明的另一個實施例的解石馬裝置的配置 的另一個實例的才醫圖；以及圖11是示出了個人計算機的配置實例的框圖。
具體實施例方式
在詳細描述本發明的優選實施例之前，描述了在所附權利要求 中所述的多個特徵和以下描述的優選實施例的特定元件之間的對應 關係。然而，該描述^f又用於確認支持在權利要求中所述的發明的特 定元件被披露在本發明實施例的描述中。因此，即使在實施例的描 述中所述的 一些特定元件沒有作為以下描述中的特徵之一 ，但這並
不表示特定的元件不對應於該特徵。相反，即4吏一些特定元件;故描 述為對應於特徵之一的元件，^旦這也並不表示該元件不對應於除該 元件之外的任4可其他特徵。
根據本發明的實施例，提供了 一種用於對低密度奇偶校驗 (LDPC)碼進行解碼的解碼裝置，包括多個存儲裝置(例如， 圖4中所示的RAM 100 ~ 103 ),用於將關於一個碼字的對數似然率 或對悽史後-驗相剋率存儲到相互獨立的地址中；以及讀出裝置(例如， 執行在圖9的步驟S203的處理的圖5中所示的解碼部202)，用於 從存儲在存儲裝置中的關於一個碼字的對數似然率或對數後驗概率 中，同時讀出與在低密度奇偶校驗碼的編碼處理中使用的校驗矩陣 的預定一行中的非零值元素的相對應多個對數似然率或對數後驗概 率。
解碼裝置可以進一步包括存l諸位置確定裝置(例如，圖5中 所示的存〗諸位置確定部201 ),用於將關於一個碼字的對悽t似然率或 對數後驗概率存儲到存儲裝置中，以便以通過用校驗矩陣的行權重 的最大值除以存儲裝置的數量獲得的值向上捨入數字值獲得的讀出 次數，從存儲裝置中讀出與4交驗矩陣的任一行中的非零值元素對應 的所有的對lt似、然率或對lt後-驗相無率。以下將參考附圖描述本發明的實施例。
首先，描述在本發明中所使用的LDPC (低密度奇偶校驗碼) 的解碼。
例如，LDPC碼是在包括移動通信和深空通信的通信領域和包 括地波或微型數字廣播的廣播領域中所使用的低密度奇偶校驗碼的 糾4普編碼和解碼的系統。
作為對碼性能的理論極限，已知通過香農(C. E. Shannon)的 信道編碼理i侖糹是供的香農4及限。為了開發表現出與香農4及限近似性 能的碼， 一直在進行關於編碼理論的研究。
近年來，作為表現出與香農極限接近的性能的編碼方法，已經 開發出稱為巻積碼(諸如並行級聯巻積碼(PCCC)或串行級聯巻 積碼(SCCC ))的技術。雖然開發出了這樣的巻積碼，但是關注的 卻是作為長期以來已知的編石馬方法的LDPC石馬。
近年來的研究發現，隨著LDPC碼的碼長增加，通過巻積碼等 同樣獲得與香農極限近似的性能。而且，由於LDPC碼具有最小距 離與碼長成比例地增加的特性，所以他們具有表現出很好的概率特 性的特;f正，並且有利之處還在於，在LDPC碼中，4艮少會出現乂人巻 積碼的解碼特徵等觀察到的誤碼平臺現象。
LDPC碼是通過包括^艮少量的非零值元素的稀疏奇偶校驗矩陣 H定義的線性碼，並且非零值元素的數量在校驗矩陣H的行和列中 固定的那些碼被稱為規則LDPC碼，而除了所述碼之外的那些碼被 稱為不失見則LDPC石馬。
以下，通過將二維LDPC碼作為實例來進行描述。通過基於才之 一驗矩陣H產生產生矩陣G並將產生矩陣G乘以二維信息消息產生碼字來實現LDPC碼的編碼。特別地，根據LDPC碼執行編碼的編 碼裝置首先計算滿足表達式G.HT = 0的產生矩陣G以及校驗矩陣H 的轉置矩陣HT。此處，當產生矩陣G是KxN矩陣時，編碼裝置4吏 產生矩陣G乘以由K位形成的信息消息(矢量s)， 乂人而產生由N 位形成的碼字的矢量c (=s , G)。通過編碼裝置產生的碼字被映射 以使例如值為"0"的每個碼位被映射到"+l"，而值為"1"的每個 碼位4皮映射到"-l"，並^皮以這樣映射的狀態傳輸，然後通過預定通 信路徑被接收器接收。
當校驗矩陣用H表示，產生矩陣用G表示，K個信息位的矢量 用s表示，以及N位的碼字的矢量用c表時示，4艮據以下表達式(1 ) 執行LDPC碼的編碼
c = S G …U)
同時，LDPC碼的解碼可以通過由Gallager l是出作為概率解碼 的算法來實現，作為概率解碼的算法是根據在包括還被稱為消息節 點和校驗節點的變量節點的Tanner圖上的置信傳播的消息傳遞算 法。
作為用於LDPC碼的一個典型解碼方法，可以釆用和積解碼方 法。這基本等同於被稱為置信傳播的算法。
此處，Tanner圖由圖1表示，其中，校'驗矩陣H作為以下表達 式(2)而給出，並且由圖1中的上側上的空白電路指示的節點:帔稱 為變量節點，而由在圖1中的下側上的暗電^各指示的節點;故稱為才交 -驗節點。每個變量節點對應於4交-驗矩陣H的一列，以及每個4交3t節 點對應於校驗矩陣H的一行。雖然算法的目標是確定與來自多個接 收值的每個傳輸符號對應的後驗概率，但是由於通常LDPC碼的Tanner圖包4舌回if各，所以不能通過BP計算4青確的後-3t扭克率，而偵_ 用近似計算。然而，已知當圖稀疏時，近似、汰術提供4交好的結果。
1 1 10 0 0 0 0 1 10 0 L0 0 0 1 1 1
'..(2)
此處，描述了用於二維LDPC碼的和積解碼方法的過程,
布i:沒矢量c是碼長為N且校驗符號數為M的二維LDPC碼， 並且由以下給出的表達式(3)表示的4交-瞼矩陣H限定。應注意， 在以下給出的描述中，符號"或"—"表示值到變量等的替換， 以及符號"三，，表示預定值、變量等的限定。
其中，hmn是校驗矩陣H的第m行和第n列上的元素，以及變 量m和n是分別滿足1^m^M和lSn^N的整悽t。
例如，當關於從接收信號獲得的一個碼字的對數似然率矢量A =[、X2 ... ^ ... Xn]的第n位的對悽t似然率由？tn表示時，從第m個 校驗節點發送到第n個變量節點的消息由(Xmn表示，從第n個變量 節點發送到第m個校驗節點的消息由|3mn表示，在和積解碼方法中， 衝丸行在以下給出的步驟Al ~ A6的處理來執行解碼。
此處，對數似然率^n被解釋為通過以下表達式(4)給出。同 時，P (xly)表示條件概率，其中，當接收信號為y時，原始傳輸 符號為x。進一步地，在傳輸線可以-故假設為AWGN (加性高斯白噪聲)通信路徑並且噪聲的散布用02表示時，對數似然率^可以被
解釋為通過以下表達式(5)給出。
、=* …(5) 步艱《A1:初始4匕
對於滿足hm「1的所有集合(m, n),消息otmn均^皮設為0。進 一步地，循環計數器l被設為1。從接收到的字矢量y = [yi y2…yn... y^中，根據以上給出的表達式(5)對所有n計算對數似然率^。
步驟A2:變量節點處理
對於滿足hmn=l的所有集合(m, n)，根據以下給出的表達式 (6)計算第m個消息pmn。此處，通過B (n)表示連接到第n個 變量節點的4交驗節點的數量集合。
步艱《A3: 4交-瞼節點處理
對於滿足hu^ 1的所有集合(m, n)，根據以下給出的表達式 (7 )計算消息amn。此處，通過A ( m )表示連接至第m個校驗節 點的變量節點的數量的集合。
fnsign(Ai^ff S朝)
formula see original document page 15其中
禱{-I, S …(8)
exp(x)—l
p(x)-l …(9)
步艱《A4:估計》馬字的確定
對在1 範圍內的所有n計算以下給出的表達式(10)，
並且使用基於表達式(10)獲得的值qn計算以下給出的表達式(11 ), 以確定估計的碼字矢量c碼(在本說明書中被表示為c—h，但是在 數值表達式中被表示為在其上增加有標記八的字符c )= [c—h, c—h2… c—hn ... c—hN]。此處，表達式(IO)中的qn是對數後驗概率。
ll"O ,if sign(qa)=l 步驟A5:奇偶校驗
如果估計碼字的矢量c—h = [cjii c_h2 ... c_hn ... cJiN]滿足以下 給出的表達式(12),則估計碼字的矢量cji:[cji, c_h2 ... c_hn ...
Cjl!sj]被輸出作為估計碼字，然後處理結束。
步驟A6:計悽t器的遞增如果滿足1 S lmax，則1被遞增為1 — 1 + 1,然後處理返回到步 驟A2。另一方面，如果不滿足l^lmax,則估計的碼字矢量cji-[c_h, c_h2 ... c—hn ... c—hw]被輸出作為估計碼字，然後處理結束。應 注意，通過和積解碼方法的解碼:帔詳細4皮露於上述非專利文獻2。
另外還提出了一種算法(分層BP算法)，其中，通過上述和積 解碼方法對每行執行對數後驗概率qn的更新過程，即使迭代次數很 小，^f旦是仍可以實玉見等同於正常和積解石馬方法的性能並且還可以減 少存儲量。在分層BP (算法)解碼方法中，通過執行在以下步驟 Bl ~ B5中的處理來寺丸4亍解碼。
步驟B1:初始化
對於滿足hmn = 1的所有集合(m， n ),消息a訓被設為0。進一 步地，循環計數器l被設為l。從接收到的字矢量y二[y,y2 ...yn... yN],根據以上給出的表達式(5)對l^n^N範圍內的所有n計算 對數似然率、，並且將對數似然率^替換為對數後驗概率qn。
步驟B2:關於校驗矩陣的每行的變量節點處理
對於校驗矩陣的每行，對滿足hmn-l的所有集合(m,n)連續計 算以下給出的表達式(13 ) ~ (15)。特別地，4吏用由表達式(13) 確定的&的值計算表達式(14),並且使用由表達式(14)確定的amn 計算表達式(15)。然後，對校驗矩陣H的每行更新數後驗概率qn。
3n —qn-an
仰
'nsign(/u]'ffi;f(iw))
…(14)
…(15)步驟B3:估計》馬字的確定
4吏用^皮獲得作為在步驟B2的處理結果的對數後驗概率qn，對 於在1 ^n^N範圍內的所有n計算以上給出的表達式(11)，以獲 得估計的碼字矢量c_h = [c—h, c_h2 ... c_hn ... c—hN]。
步驟B4:奇偶才交一驗
如果估計碼字的矢量c_h = [cji! c—h2 ... c_hn…cJiN]滿足表達 式(12),貝'J c_h = [cji, c—h2 ... c—hn ... c—hN]被輸出作為估計碼字， 然後處理結束。
步驟B5:計數器的遞增
如果滿足l^lmax，貝'j l被遞增為1 — 1+1，然後處理返回到步 艱《B2。 i口果不滿足1 < lmax,則c一h = [c—hi c—h2 ... c—hn…c一hN]淨皮 輸出作為估計的碼字，然後處理結束。
以此方式，在LDPC碼的解碼的奇偶校驗中，由於校驗矩陣H 的轉置矩陣和估計的碼字的乘積4皮在數學上運算為由表達式(12) 表示，所以判定數學運算的結果是否為0。因此，必須提取與校驗 矩陣H的每行中的非零值("1")的元素的位置對應的(即，與滿 足hm^1的(m， n)對應)估計碼字的位，並且在所4是取的位之間 在邏輯上進行異或運算。
然後，如果才交-驗矩陣H的轉置矩陣和估計的碼字的乘積不是0, 則再次執行變量節點處理和校驗節點處理，並且再次在數學上運算 和更新對ft後-驗;f既率qn。此時，在H學上再次運算和更新的對^t後 驗概率qn可以僅是與用於上述異或數學運算的位對應的對數後驗概 率qn，即，僅是與在校驗矩陣H的每行中滿足hmn=l的(m, n )對 應的^"^t後^企和X率qn。以此方式，在執行LDPC碼的解碼時，為了更新對數後驗概率 qn，必須對校驗矩陣H的每行執行表達式(6 ) ~ ( 7 )以及(13 ) ~ (15)的數學運算處理。因此，如果不能從關於包括M行的校驗矩 陣H的每行的N個對數似然率、(1 ^ n ^ N)或N個對數後驗概率 qn (1 ^ n ^ N)中選擇並提取僅滿足hmn=l的那些對數似然率^或對 數後驗概率qn ，則不能實現有效的解碼處理。
因此，例如，當解碼裝置^皮配置為對LDPC碼進^f亍解碼時，在 相關技術中提供選擇器來對校驗矩陣H的M行中的每行，從存儲 在存儲器、寄存器等中的N個N個對數似然率^ (1 ^ n ^ N)或N個 對數後驗概率qn (1 S n S N)中選擇並輸出滿足hmn=l的那些對數似 然率、或對數後驗概率qn。
例如，當解碼裝置的解碼等4寺時間具有足夠的空隙時，可以通 過指定RAM的;也址，爿尋N個^f悽^f以然率^或N個乂十悽t後-驗相剋率 qn存儲到一個RAM (隨機存取存儲器)中，並且逐個讀出並計算在 校驗矩陣H的每行中滿足hmn=l的那些對數似然率^或對數後驗概 率qn。該配置以下^皮稱為配置A。
但是，在配置A的情況下，關於完成解碼所需的處理要用的時 間增力口。例如，假設校驗矩陣H包括滿足hm^1的NH個集合(m，n)， 並且解碼的重複次數為N!。在當前情況下，為了執行用於校驗矩陣 H的M行的解碼，對NH個元素執行變量節點處理和校驗節點處理 的計算，因此，要求進行2xNH個時鐘的處理。進一步地，由於該 解石馬糹皮重複N!次，所以當時間間隔由Ts表示時，用於4妄收碼字的 解石馬所需的時間為2xNHxN!xTs。
例如，如果下一個接收碼字被存儲到寄存器或存儲器中之前的 時鐘數由Nu表示，如果Nb〉2xNhxNp則可以採用配置A。但是， 如果Nb〈2 xNHxNP則不能採用配置A。進一步地，通過配置A，如果希望減少等;f寺時間，則由於用於完成解碼所需的處理的時鐘數 很大，所以要求的操作頻率很高。從而，很難結合配置A。
作為和積解碼方法的解碼裝置的配置，還4是出了同時衝丸^f亍關於 校驗矩陣H的M行的變量節點處理和校驗節點處理的計算的配置。 該配置以下^皮稱為配置B。在配置B的情況下，由於在一個時4中分 別執行關於校驗矩陣H的M行的NH個元素的變量節點處理和校驗 節點處理的計算，所以解碼所需的時間為2xN,xTs。因此，與配 置A相比較，可以大大減少等4寺時間。
但是，在配置B的情況下，由於必須並行執行關於校驗矩陣H 的M行的計算，因此存在電路尺寸增加的問題。進一步地，在配置 B的情況下，很難將執行具有不同碼長的LDPC碼、具有不同編碼 率的LDPC碼、具有不同4交-驗矩陣的LDPC碼的解碼的解碼裝置作 為單個解碼裝置來實施。因此，配置B被認為具有很高的碼相關性。
另一方面，當配置分層BP解碼方法的解碼裝置時，其可以淨皮 配置為能夠同時讀出與校驗矩陣H的每行中滿足hm^1的(m， n) 對應的那些對數似然率、或對數後驗概率qn,並且並行執行關於校 -驗矩陣H的一4於的變量節點處理和4交-瞼節點處理的計算。然而，為 了實現剛剛描述的配置，需要選擇器從存儲在寄存器等中的N (碼 長)個對數後驗概率qn中連續選擇每行中滿足hmfl的那些對數似 然率、或只於悽t後-驗相無率qn。由於通常LDPC石馬的石馬長為幾千~幾萬， 所以如果採用上述那樣的配置，則電i 各尺寸就會變得非常大。
還提出了一種配置，其中，為校驗矩陣執行行替換或列替換， 以將校驗矩陣轉換為其成分矩陣為例如P x p ( p行和p列)的單位
碼的解碼中可以對P個成分矩陣並行執行校驗節點處理和變量節點 處理的計算。該配置以下^皮稱為配置C。才艮據配置C，對^接收的碼字進4亍解石馬所需的時間為2xNhxN!xTVP。雖然配置C可以衝中制
解碼所需的時間，並且還可以抑制在能夠被實現的範圍內的電路尺
寸，但是當在下一代無線LAN的情況下需要非常低的等待時間時， 仍然需要很高的操作頻率，並且難以結合配置C。
然而，如果通過簡單的配置獲得在短時期內同時選擇與在校-瞼 矩陣H的每行中滿足hmn=l的(m, n )對應的多個對數似然率、或 對悽t後-瞼概率qn的配置，則可以減少解碼所需的時間並且還可以4吏 電路配置不會變得很大。
從而，本發明的實施例採用的是並不逐個、P個P個或一整行 地選4奪對數似然率、或對tt後驗概率qn,而是在短時期內同時選拷， 與在校驗矩陣H的每行中滿足hm^1的(m,n)對應的多個(v或v x p )個對^t似然率、或對悽t後-驗扭克率qn的配置。
通過上述這樣的配置，例如，當與配置C的情況相比4交時，解 碼所需的時間^皮進一步抑制，並且當與配置B的情況相比較時，還 可以減少電^各配置。
例如，為了從N個對數似然率、和對數後驗概率qn中提取多 個對悽t似然率^n或對數後-驗相無率qn，準備多個RAM，並且將一個 對悽t似然率^或對lt後-驗相X率qn存^f諸到RAM的一個地址中。或者， 當由P行和P列的成分矩陣形成校驗矩陣時，為了同時提取由P個 對數似然率^或對數後-驗和無率qn組成的數據，將P個對lt似然率、 或對:數後-驗和克率q。存々者到RAM的一個地址中。
然而，如果對悽t似然率或對悽t後-驗概率qn完全^皮存儲到多個 RAM中，例如，為了從接收的碼字的第一個位開始，當對數似然率 tn或對數後驗概率qn將被提取時，非常可能出現對一個RAM的不 同地址同時存取。這就不可能在短時期內從校驗矩陣的所有行同時讀出與滿足hmn=l的(m, n )對應的多個對數似然率、或對數後-驗 概率qn。
使用簡單實例來對此進行描述。例如，假設從用於對由以下給 出的表達式(16 )表示的碼率為1/2並且碼長為24的碼字進行編碼 或解碼的校-驗矩陣H同時四個四個地連續提耳又，在校-驗矩陣H中， 由以下給出的表達式(17)表示的24個對數後-驗才既率qn分別被存 4諸到四個RAM a d中。
…(16)
Q :[q! q2 q3 <U q5 q6 q7 q8 q9 q10 qu q12 q13 q14 q15 q16 q17qls q19 q加q2％ q24]
' (17)
在當前情況下，由於碼長N為N-24,所以當對數後驗概率qn 分別^皮存4諸到四個RAM中時，每個RAM必須具有6 ( =24/4)個 地址。例如，如果對悽t後-驗和克率qn乂人碼字的第一個位開始糹皮順序存 儲到RAM a d中，則對悽t後-驗;慨率qn以圖2中所示的方式存儲。
然後，從以圖2中所示的方式存儲的對數後驗概率qn中讀出關 於才t驗矩陣H的每行的滿足hmn=l的那些對數後驗概率qn。
在當前情況下，在校驗矩陣H的第一行中,(m， n) = (1， 1), (1， 2), (1,4), (1，6)，(1， 10), (1, 13)和(1, 14)滿足hm廠l。因此，應從24個對 悽t後,瞼才既率qn中讀出對應於上述這樣7個(m， n)的qi、 q2、 q4、 q6、 qio、 qi3和qi4。然而，當以圖2所示的方式存儲對悽t後驗概率
22
ooooooooooll
ooooooooollo
oooooooolloo
ooooooollooo
oooooolloooo
oooolloooooo
ooollooooooo
oolloooooooo
ollooooooooo
11-0000000000
looooloooool
oooloooloolo
oooloolooool
olio- -f lllooll
looolooooolo
lllloololuo
olooloolooooqn時，q2、 q6、 qio和qi4^皮存卡者在相同的RAM中，即，RAMb，並 且如果試圖例如在兩個時鐘(當試圖乂人四個RAM讀出七個值時， 其為最短時間)內讀出七個對數後驗概率qn時，兩個不同的地址必 須被同時存取，這就使得例如RAMb的地址"1"和地址"2"被同 時讀出，然後RAMb的i也址"3"和;也址"4" -故同時讀出。另一 方面，如果試圖讀出所有七個對悽t後一驗扭克率qn而不對RAM b的不 同地址同時存取，則需要四個時鐘，這是低效的。
現在，研究將對數後驗概率q。存^f諸到圖3所示的RAM a ~ d中。 在該實例中，在校驗矩陣H的第一行中將被讀出的qi、 q2、 q4、 q6、 qio、 q,3和q"—^^皮存^諸到所有四個RAM中，並且在才交-驗矩陣H 的第 一行中將被讀出的所有七個對數後驗概率qn可以在兩個時鐘內 #皮讀出而無需同時存取不同的地址。
進一步地，如果對悽丈後-驗扭無率q。以圖3所示的方式淨皮存4諸在 RAMa-d中，則在與第一4亍類似的情況下，還可以在兩個時4中內 讀出在校驗矩陣H的第二行和後續行中的對數後驗概率qn。
因此，如圖3所示，如果對數後驗概率q。在RAM中的存儲位 置被適當地設置，以使可以在兩個或更少時鐘內讀出在校驗矩陣H 的第一~第十二行的每行中將被讀出的所有那些對數後驗概率qn， 則當與逐個讀出對數後-驗概率q。的可選情況相比4交時，可以高速有 效地讀出對數後-驗概率qn。進一步地，如果對數後-驗概率qn到RAM 的存儲位置被適當地設置並存儲，則由於希望的對數後驗概率qn可 以通過地址的指定來提取，所以例如，還可以消除選4奪器從多個對 數後驗概率qn中連續選擇與滿足hmfl的(m, n)對應的對數後驗 概率qn的必要性。
應注意，以下描述用於適當地設置對數後驗概率qn在RAM中 的存儲位置的處理。此外，如果對^:後驗相無率qn在RAM中的存儲位置如圖3所示 被適當設置，則在兩個時鐘(用於讀出每行的最短時期)內讀出與 用於每列的滿足h自-l的(m, n)對應的那些對數後驗概率qn。因 此，由於分開兩次地執行使用所讀出的對數後驗概率qn執行的變量 節點處理和才交-驗節點處理，所以可以實if見電3各的共享。另外，當與 共同一次扭J於關於一^f於的變量節點處理和4交-驗節點處理的可選配置 相比4交時，電3各尺寸可以減小到1/Nrd，在當前情況下，Nrd = 2。
當對數後一驗相無率q。在RAM中的存4渚位置如圖3所示^皮適當i殳 置時，如果碼長由N表示，校驗矩陣H的行權重的最大值由wRMax 表示，用於存儲對數似然率、或對數後驗概率qn的RAM的數量由
N,表示，RAM的地址數由Naddr表示，提取關於校驗矩陣H的一
行的對數似然率^或對數後驗概率qn所需的時鐘數由Nrd表示，則 滿足以下給出的表達式(18)。通過操作頻率、校驗矩陣、解碼重複 數等確定N,,從而可以滿足將要安裝的系統要求的等待時間。另 外，當校驗矩陣H由P xp個小矩陣的組合表示時，為了將對數似
然率？in或對數後驗概率qn放入到每個RAM的一個地址中，視碼長 (apparent code length ) N，被限定為通過以下給出的表達式(9 )給 出。在此應注意，如果視碼長N，可以被N,除盡並且對數似然率>^ 或對數後-驗概率qn統一被放入Nram個RAM中，則RAM的地址數 量Na她通過以下給出的表達式(20)表示。
在表達式(19)中，上部其中，H通過Pxp個矩陣的結合 來表示
…(18)
…(19)同上，下部在4壬4可其<也情況下
…(20)
應注意，校驗矩陣H的行權重的最大值WRMax表示在校驗矩陣 H的任一行中具有非零值的像素的最大數。例如，由於表達式(16)
的校驗矩陣H的每一行中均包括最大為七個"1"的元素，所以行
片又重的最大<直WRMax為7 。
另夕卜，當校驗矩陣H由如以下給出的表達式(21)表示的具有 循環結構的PxP (P4亍和P歹'J )個小矩陣(在當前情況下，P = 4)
的這樣的組合形成時，如果PxP矩陣;陂認為是一個元素hmn,則可 以應用以上描述的方法。在本實例中，衝交驗矩陣H由通過虛線分割 的多個小矩陣形成。特別地，由虛線分割的一個部分是一個小矩陣，
並且以下給出的表達式(21 )由4 x 8 = 32個小矩陣構成，每個小矩 陣均#1形成為4 x 4 (四^亍和四列)的矩陣。
0 0 0 0
一o
0 0 -0 —0 0 0
-1
0 0
0
1 一
…(21)
ot匕處，循環結構是如果矩陣的元素在例如向左或向右的方向上
移位，則可以獲得另一個矩陣的循環結構。例如，如果將在表達式
(21 )的左上角處的小矩陣的第一 ~第四行的所有元素在向右的方
o o o olc-
o o o ao
o o o o-o
o o o ojo
o o o o一 1
1 o o or
-----T1
o i o o！ o
1 o o o"o
o o o丄o
-5 "1^51 o一w
o-o
o o o碰o o 1 0*0 o ,1 o
o o l一o o o Jo o o o
o 1 o一o o 1 oi o o o o
o 1 o
1* o ol
o 1 o o一o o _
1 o o olo o
o ooso
o o o一
o o o_
ooo
o o o
loo
lo o <
> o一o
o o o l一 o
loo olo ，
ooo
o <
o o 1 o一o l
o 1 o or o
n* o o C^JO o
o一o o
o -i -
J、
o o一o <
ooo丄o <
ooo OT <
ooo o一o <
o o o or
o o o o一 o
o <
H向上移一位，則得到的小矩陣變為與在小矩陣的右側相鄰的小矩陣 相同。
如果表達式(21 )被認為類似於表達式(22)並且將被放到每 個RAM中的對數似然率^或對數後馬全概率qn的數從一變為四，則 可以應用本發明實施例的配置。然而，由於因此必須並4亍處理Nram xP個數據，所以執行變量節點處理和校驗節點處理的電路的尺寸 Ai曾力口至"P ^f咅。
在本發明的實施例中，實現通過分別存儲當將關於 一個碼字的 對悽t後-驗和克率q。更新到多個RAM中時所需的消息a^的值或刈-凌丈 後驗概率qn同時執行讀出和寫入多個值的解碼裝置。
以下，參考附圖描述將本發明的實施例應用至分層BP解碼方 法的實例。
圖4是示出了應用本發明實施例的解碼裝置的配置實例的框 圖。參考圖4，所示的解碼裝置IO接收例如從未示出的另一個裝置 以LDPC碼的形式發送的碼字並對接收到的碼字執行糾錯和解碼。
另外，此處的解碼裝置10例如使用由表達式(16)表示的4交-驗 矩陣對以LDPC碼形式編碼的碼字進行解碼。由於通過表達式(16 ) 指示的校驗矩陣H包括12行和24列，所以表示校驗矩陣的行和列 的變量m和n是分別滿足1 12和1 ￡ n S 24的整數。
在圖4所示的解碼裝置10中，用於存儲接收碼字的對數似然率 ^或對^t後'險相剋率qn的RAM由四個RAM (即，RAM 100 ~ 103 )
形成。在該實例中，由於RAM的數N,是Nram-4，所以根據表達
式(20 )計算每個RAM的地址數Naddr = 6。因而，RAM 100 ~ 103 的地址數是6，即，從地址[1]到地址[6]。同時，由於校驗矩陣H的行權重的最大值WRMax是WRMax = 7， 所以才是耳又關於才交-驗矩陣H的一4亍的對悽t似然率？tn或對悽t後'驗相無率
qn所需的時鐘數Hd通過表達式(18)計算為Nrd = 2。
進一步地，在所示的實例中，用於存儲消息a訓的RAM包括
四個RAM 104~107。在當前'清況下，RAM 104 — 107中的每個的 地址悽丈均為24，即，從地址[1 ]到地址[24]。
控制器112包括存儲器等並且存儲以下描述的預先確定的接收 碼字的對數似然率^或對數後驗概率q。的適當存儲位置。控制器 112基於存儲在存儲器中的信息來控制解碼裝置10的組件。
當通過解碼裝置l(H丸行解碼時，首先接收將^皮解碼的碼字，並 且將對應於碼字的各個位的對數似然率A^提供給開關108-111。當 碼長為24位時，將24個對數似然率、按、~ X24的順序提供給開 關108 ~ 111。
此時，控制器112基於存儲在內部存儲器等中的存儲位置輸出 用於控制開關108~ 111的控制信號cll ~cl4。因此，乂人開關108~ 111分別l命出24個對lt似然率Xn作為信號dl ~d4，然後被存〗諸到 RAM 100 ~ 103的適當地址中。
在本實例中，RAM100 103的存儲位置通過q! q24指示，並 且類似於以上參考圖3描述的存儲位置。應注意，當不計算對數後 驗概率qn時，即，當接收碼字的對數似然率、被存儲到RAM 100 ~ 103中時，對悽t似然率、~ X24分別^皮存^f諸到由存々者位置qi ~ q24指示 的存儲位置。
然後，控制器112基於存儲在內部存儲器等中的存儲位置和校 ^r矩陣H的信息控制信號c21 ~ c24, /人而在從RAM 100 ~ 103更新 之前，讀出與在校驗矩陣H的第一行中滿足hm「1的(m， n)對應的對數似然率^來作為對數後驗概率qn，然後將該對數後驗概率qn 才是供鄉合變量節點處理部113。此處，最大的四個乂於悽^f以然率、或四 個對數後驗概率qn被同時讀出並作為信號gl ~g4提供給變量節點 處理部113。
應注意，消息amn的值最初作為值0被存儲在RAM 104 ~ 107 中或在執行第一次讀出之前被初始化為0,並且基於從控制器112 舉lT出的控制^f言號c31 c34從RAM 104 ~ 107讀出悽t學運算所需的那 些消息otmn來作為信號al a4，然後糹是供給變量節點處理部113。
變量節點處理部113執行由表達式(13 )指示的數學運算來計 算pn的值，並且將所計算出的|3n的值作為信號bl ~ b4提供給校-驗 節點處理部114和延遲電路125。此處，變量節點處理部113同時 4丸行關於同時乂人RAM 100 ~ 103讀出的對數似然率？tn (更新之前的 對數後驗概率qj的數學運算。
校驗節點處理部114執行通過表達式(14)表示的數學運算來 更新消息amn。更新的消息amn作為信號al， a4，祐^是供給算術單 元115和RAM 104 ~ 107，從而分別更新了存儲在RAM 104-107
中的消息(Xmn的值。
延遲電路125使信號bl ~b4延遲了通過用於更新在校驗節點
處理部114中的消息(Xmn的計算帶來的延遲量。
算術單元115執行由表達式(15)表示的數學運算，以計算更
新後的對數後驗概率qn。此處，計算對應於Pn值的多個對數後4全概
率qn的數和從延遲電路125和校驗節點處理部114同時提供的更新
的消息(Xmn，然後被分別作為信號gl， -g4，提供給開關108-111。
此時，控制器112基於存儲在內部存儲器等中的存儲位置輸出 控制信號cll ~cl4並從開關108-111分別輸出更新後的對數後-瞼概率qn作為信號dl ~ d4。信號dl ~ d4被存儲在RAM 100 ~ 103的 適當地址中，以更新存儲在RAM 100 ~ 103中的值。執行該操作用 於校驗矩陣H的所有行，從而更新24個對數後^驗概率qn。
在讀出關於校驗矩陣H的一行的與滿足hmn=l的(m， n )對應 的所有對悽"以然率、或對數後-驗;f既率qn並計算通過變量節點處理部 113~算術單元115的處理更新的對悽t後-驗概率q。之後，讀出存4諸 在RAM 100 ~ 103中的對數後驗概率qn的值，然後將其提供給奇偶 校驗部116。應注意，如上所述，通過Nrd ( =2)次讀出操作全部 讀出關於校驗矩陣H的一行的與滿足hmn=l的(m， n )對應的對數 似然率？tn或對ft後-驗糹既率qn。
奇偶4交-瞼部116 4丸4於在上述分層BP解碼方法的步驟B3和B4 的處理，以產生表示奇偶校驗的結果(OK或NG )的信號p並將信 號p提供給控制器112。
當從奇偶校驗部116提供表示結果為NG的信號p時，控制器 112基於存儲在內部存儲器等中的存儲位置和校驗矩陣H的信息輸 出控制信號c21 ~ c24和控制信號c31 ~ c34，以從RAM 100 ~ 103 中讀出在校驗矩陣H的第一行中與滿足hmn-l的(m, n)對應的那 些對悽欠後-瞼相無率qn,並進一步/人RAM 104 ~ 107讀出對應於對悽t後 驗概率qn的消息amn。然後，控制器112將對數後驗概率qn和消息 amj是供給變量節點處理部113。因此，進一步更新了存儲在RAM 100 — 103中的^直。
另 一方面，如果從奇偶校驗部116提供表示結果為OK的信號 p,則控制器112輸出控制信號c4,以便將關於一個碼字的對數後 驗概率q。從開關117輸出到符號判定部118。然後，符號判定部118判定所提供的信號具有正號還是負號。 然後，例如，如果符號是正號，則信號被映射為"0",而如果符號 是負號，則信號被映射為"1"，並且輸出關於一個碼字(即，24位) 的數據作為解碼結果。
圖5示出了控制器112的功能配置的實例。
參考圖5,所示的控制器112包括存儲位置確定部201,控制 確定RAM 100 ~ 103中的對數似然率、或對數後-驗概率qn的存儲位 置(例如，用於指定RAM的ID)的處理。
通過存儲位置確定部201確定的存儲位置祐j是供給控制部103 並被存儲到控制器112等內部存儲器中。
解碼部202控制基於存^f諸位置確定部201確定的存儲位置來讀 出存儲在RAM 100~ 103中的對數似然率^n或對數後驗概率qn並對 接收碼字進行解碼的處理。特別地，解碼部202使解碼裝置10執行 上述分層BP解碼方法的步驟Bl ~ B5的處理。
控制部203發布例如對存儲位置確定部201和解碼部202執行 處理的指示，從而控制諸如用於控制解碼裝置10的組件的控制信號 的產生的多種處理。控制部203存儲由存^f諸位置確定部201確定的 存儲位置和預先設置到內部存儲器等中的校驗矩陣H。然後，控制 部203從存儲器讀出存儲位置或校驗矩陣H，並將存儲位置或校驗 矩陣H 一是供給存〗諸位置確定部201或解碼部202。
應注意，雖然以上描述了提供存儲位置確定部201作為控制器 112的功能塊，^f旦是存儲位置確定部201並不必需^皮提供在解碼裝 置10中。例如，等同於存儲位置確定部201的功能塊可以被提供在 不同於諸如例如個人計算機的解碼裝置10的裝置中，以將由功能塊確定的存儲位置的信息例如通過通信傳輸到解碼裝置10,從而存儲
位置可以被存儲到解碼裝置10的控制器112的內部存儲器中。
概率qn的RAM 100 ~ 103的存儲位置的存儲位置確定處理的流程圖 中。通過執行該處理，解碼裝置10發現每個對數似然率^或對數 後,驗相剋率qn應該^皮存^f諸到哪個RAM中的什麼；也址中，/人而在4丸4亍 解碼的短時期內4是耳又對f欠似然率^或對悽t後—驗糹既率qn。特別地，在 才丸行所述處理時，確定以上參考圖3所述的存儲位置。在此，例如， 預先通過與解碼電^各等分離的裝置扭^亍該處理，並且通過該處理確 定的存儲位置被存儲到控制器112的內部存儲器中。
此處，對用於存儲對數似然率^或對數後驗概率qn的多個RAM 中6勺每個，i者^口侈寸^口四個RAM ( RAM 100 ~ 103 ),分酉己i者^口侈'J^口 1 、 2、3或4的號碼。在以下描述中所使用的存儲位置候選r， = [r，, r，2 ... r，i ... rV]指示其中存儲有對數後驗概率qn的一個RAM。例如，r'8 =4表示對數後驗概率q8的數據將被存儲到號碼為"4"的RAM(即， RAM 103)中。
參考圖6,首先在步驟S101中，存4諸位置確定部201將變量itr 初始化為0，變量itr對多個RAM的存儲位置候選的產生悽t量進4亍 計數。
在步-驟S102，變量itr力口l。
在步驟S103，存儲位置確定部201執行存儲位置候選產生處理 (以下參考圖7進行描述)，以產生第一次的存儲位置候選r，-[r，, r，2 ... r，i ... rV]。在當前情況下，由於碼長N為24,所以表達式(19) 的—見碼長N'也是24。在步驟S104,存儲位置確定部201執行在以下參考圖8描述的 存儲位置候選校驗處理。從而，當N個對數似然率^或N個對數 後-驗扭克率qj皮存^f諸到通過步驟S103的處理產生的第一次存^f諸位置 候選r^[r、r，2…r，i…r，N，]中時，判定與滿足hm^l的(m， n )對 應的那些對lt似然率^或對數後-驗概率qn是否能夠在Nrd個或更少 的時4中內淨皮讀出。
在當前情況下，由於RAM ( RAM 100 ~ 103 )的悽t量是四，Nram =4，並且由於地址數Na她是Naddr = 6以及行權重的最大值wRMax 是WRMax = 7，所以提取關於校驗矩陣H的一行的對數似然率、或對 數後驗概率qn所需的時鐘數Nrd是表達式(18)中的Nrd = 2。換句 話說，如果能夠兩次或更少次地讀出與滿足hmn=l的(m， n)對應 的對數似然率^或對數後驗概率qn，則認為存儲位置候選為以上參 考圖3描述的適當設置的存儲位置。因而，存儲位置候選校驗處理 的才L驗結果為OK。
同時，如果在兩個或更少的時鐘內不能讀出與滿足hmn=l的(m， n)對應的對數似然率？w或對數後驗概率qn,則存儲位置候選不會 被認為是適當設置的存儲位置，而是認為必須進一 步產生存儲位置 候選。因而，存儲位置候選校-驗處理的校'驗結果為NG。
在步驟S104的處理之後，存儲位置確定部201在步驟S105判
定存儲位置候選校驗處理的校驗結果是否為OK。如果判定校驗結 果不是OK，即，校驗結果是NG，則必須進一步產生存儲位置候選。 因此，處理進行到步驟S107。
在步驟S107,判定變量itr是否不同於候選的總數riMAx。如果 變量itr不同於總悽t nMAX，則由於可以淨皮產生的候選仍然存在，處 理返回到步艱《S102來才丸4亍下一個4'美選的產生。然後，如果通過步艱《S103的處理產生第二次的存儲位置^美選r， =[r、 r，2 ... r，j ... r，N，],則將N個對悽t似然率、或N個對悽t後驗才既 率qn第二次存儲到存儲位置候選r，，然後在步驟S105判定與滿足 hmn=l的(m, n)對應的對悽t似然率^n或對悽t後-驗相無率qn是否可以 在N^t個或更少的時鐘內被讀出。
以ot匕方式，分另'JI丸4亍在步艱《S107和S102 ~ S103的處J裡，直到 在步驟S105判定出存儲位置候選校驗處理的校驗結果是OK。如果 在步驟S105判定出存儲位置候選校驗處理的校驗結果是OK,則在 步驟S106,存儲位置候選r，被設為最終確定的存儲位置r,從而結 束存^f諸位置確定處理。在該實例中，例如，確定以上參考圖3描述 的適當存儲位置。
如果在步驟S107變量itr與總數riMAx相符，則由於這意。木著所 有候選均;故產生，所以處理結束。這表示，例外地，雖然可以作為 對數似然率、或對數後驗概率qn的存儲位置存在的存儲位置候選被 全部產生並通過檢驗，但仍不能成功地找出適當設置的存儲位置。
現在，參考圖7的流程圖描述圖6的步驟S103的存儲位置候 選產生處理的詳細實例。
在步驟S121,存儲位置確定部201判定變量itr是否為1。例如， 當通過存儲位置候選產生處理第 一次產生存儲位置候選時，由於變 量itr為1 ，所以處理進行到步驟S124。
在步驟S124，存儲位置確定部201將變量i設為1並將存儲位 置^f'美選r'i-沒為1。
然後，處理進行到步驟S123，在該步驟，存儲位置確定部201 判定存儲位置候選r，i的值是否高於RAM號碼Nram。在當前情況下，由於Nram = 4並且通過步驟S124的處理設置的變量i的值為1 ，則 存儲位置候選r，i為r，i (= 1) $Nram (= 4)，然後處理進行到步驟S125。在步驟S125，變量i的值加l,然後在步驟S126判定變量i是 等於還是小於視碼長N，。在當前情況下，變量i為i (= 2) ^ N， (= 24)， 然後處理進行到步艱《S127。在步驟S127，存儲位置確定部201將存儲位置候選r，i設為1。 在當前情況下，存儲位置候選r，i變為r，2=l。然後，處理返回到步 驟S123。然後，由於在步驟S123r，2一 l)^Nram(=4),所以處理從步驟 S123進4亍至'J步駛艮S125 S127。以此方式，分另ij衝丸4亍在步驟S123和S125 S127的處理，並且 當變量i的值變為25時，存儲位置候選r，為r， = [l 1 ... 1],即，r、 =l,r，2= l，r，3= 1, ...,r，24= 1，並且他們是產生的第一次存儲位置候 選。應注意，當產生存<諸位置4芙選時，由於N個對^:似然率^或N 個對數後-驗概率qn都^皮存儲到RAM 100中，所以在該實例中的存 儲位置作為實際存儲位置是不適當的。因而，校驗結果通過步驟 S104的處理自然;故確定為NG。當產生第二次的存儲位置候選時，由於在圖6的步驟S102變 量itr為2，所以基於圖7的步驟S121的判定結果，處理進行到步 驟S122。在步驟S122,存儲位置確定部201將變量i減1。從而，變量 i變為24 ( -25 - 1 )。然後，存〗渚位置候選r，i加1。在當前情況下， 存儲位置候選rV被設為2(1 + 1)。然後，處理進行到步驟S123，在該步驟，判定存儲位置候選r，i 的值是否高於RAM號碼Nram。在當前情況下，存儲位置候選r，24 為r，24 (= 2) ^ Nram (= 4),並且處理進行到步驟S125。在步艱《S125，變量i的j直力ol,並且在步艱《S126,判定變量i 是等於還是低於視碼長N，。在當前情況下，變量i為i(=25)〉N，(= 24),然後處理結束。在當前情況下，存儲位置候選為r、-l，r，2-l， r，3 = 1，…，r，23 = 1， r，24 = 2。同樣，當產生第三次的存儲位置候選時，他們是r，,-l，r，2-l， r，3= 1, ...,r，23= l,r，24 = 3,以及當產生第四次的存4諸位置候選時， 他們是r、 = l，r，2= l,r，3 = 1,…，r，23 = l,r，24 = 4。當產生第四次的存〗諸位置候選時，作為圖7的步驟S121的判 定結果，處理進行到步驟S122,然後存儲位置確定部201使在步驟 S121變量i減1。因jt匕，變量i變為24 ( =25 - 1 )。進一步i也，存 儲位置確定部201使存儲位置候選r，i加1。在當前情況下，存儲位 置4美選r,24尋皮i殳為5 ( = 4 + 1 )。然後，處理進4亍到步驟S123。在該實例中，存儲位置^f'美選r，24 為r，24(=5)〉Nram(=4)。從而，作為在步驟S123的判定結果，處理 進行到步驟S128。在步驟S128，存儲位置確定部201判定變量i的值是否為1。 在該實例中，由於變量i為i-24,所以處理進4亍到步艱《S122。在步驟S122，存儲位置確定部201使變量i減1。從而，變量 i變為i-23 (=24- 1 )。然後，存^K立置^f夷選r，i加1。 乂人而，存寸諸 位置4美選r，23變為2 ( = 1 + 1 )。此後，處理進4於到步驟S123,在該步驟判定存々者位置4美選r，i 的值是否高於RAM數Nram。在當前情況下，存儲位置候選r，23為r，23 (=2)^Nram(=4)。從而，處理進行到步驟S125。然後，處理通過在步驟S125和S126的處理進行到步驟S127。 在步驟S127，存儲位置候選r，24被設為1。然後，處理返回到步驟 S123。進一步i也，處理通過在步-驟S123和S125 ~ S126的處理後結束。 在當前情況下，存儲位置候選r，i是r、 = l，r，2= l，r，3 = 1， ...，r，23 = 2, r，24 = 1。類似地，當第六次產生存儲位置候選時，存儲位置候選被設為 是r，, = l,r，2= l，r，3= 1, ...， r，23 = 2, r，24 = 2，但是當第七次產生存儲 位置候選時，存鬥諸位置候選淨皮i殳為r，=l,r，2= 1， r，3 = 1， ...，r，23 = 2， r，24 = 3。通過以此方式重複地產生存儲位置候選，產生最大的N,N'= 424 ( 4的二十四次冪)個不同的存儲位置候選r，。特別地，第424 次產生存儲位置候選時，產生存儲位置〗美選為r、 = 4, r，2 = 4， r，3 = 4, ...,r，23 = 4，r，24 = 4。應注意，第424次產生存儲位置候選之後，處 理通過在圖6的步驟S104和S105的處理進行到步驟S107。由於在 圖6的步驟S107的處理判定出變量itr等於候選的總數Nmax( = 424 )， 所以存〗諸位置確定處理結束。現在，參考圖8的流程圖描述在圖6的步驟S104的存儲位置 4'美選才交-驗處理的詳細實例。在步驟S161，存儲位置確定部201對在校驗矩陣H的每行中 與滿足hmn=l的(m, n )對應並且^皮存儲在RAM 100 ~ 103的每個中的對數似然率A^或對數後驗概率qn進行計數，並保留計數結果作為計數器值，其中，基於由在步驟S102的處理產生的存4諸位置候 選r， = [r、 r，2 ... r、 ... rV]將對數似然率、或對數後驗概率q。存儲 到RAM 100 ~ 103。例如，與存儲在RAM 100中的對數似然率^或對數後驗概率 qn的數量的計數器值、存儲在RAM 101中的對數似然率、或對數 後驗概率qn的數量的計數器值 類似，分別對應於四個RAM保留四個計數器值。進一步地，由於計數器值被獲取用於校驗矩陣H 的每行(用於12行)，所以在當前情況下，保留總數為48(-12x 4)個的計數器值。例如，作為用於存儲計數器值的變量的計數器cntm,k被預先限 定。在此，變量m和k械二沒為1 Sm^M，， l^k^Nram，其中，M， 被限定為通過表達式(23)給出。在表達式(23)中，上部其中，H通過Pxp個矩陣的結合表示同上，下部在任何其他情況下計數器cntm,k保持存儲在四個RAM的每個中的對數似然率、 或對悽t後-驗概率qn的數量的計數器值。例如，當通過在步驟S103的處理產生的存儲位置候選r， = [r，, r，2…r，i ... r，N，]為，[1 1111122222233333344444 4]，如 果校驗矩陣H通過表達式(16 )表示，則在校驗矩陣H的第一行中 滿足11訓=1,其中，(m， n) = (1， 1)， (1, 2), (1， 4), (1, 6), (1, 10)， (1, 13)， (1, 14)。進一步;也，由於r、 = 1, r'2 = 1, r，4 = 1, r，6 = 1, r,10 = 2， r，13 = 3…(23)和r，14 = 3，所以存儲將從校驗矩陣H的第一行提取的對數後驗概率 qn，即，qi， q2， q4, q6, qio， qi3和q"， Nrd ( = 2)，所以存儲位置候選是不適當的，並且 才交-瞼結果是NG。另一方面，如果存儲位置確定部201在步驟S162判定出通過 在步艱《S161的處理獲得的48個計悽t器值中沒有一個超過時鐘悽t Nrd,則處理進行到步驟S163。在該實例中，例如，如圖3所示，與滿足hm^1的(m, n)對 應的對數似然率、或對數後驗概率qn可以通過小於時鐘數Nrd的時 鍾悽t讀出。因此，i殳置表示4交-瞼結果為OK等的標記。以此方式，檢驗產生的存儲位置候選是否合適。特別地，檢驗在校驗矩陣H的任一行中將被讀出的那些對數似然率、或對數後驗 概率qn是否能夠通過兩次讀取操作全部讀出。應注意，雖然以上參考圖6~圖8描述的處理是用於將對悽"以 然率^或對數後驗概率qn的存儲位置適當地設定到RAM 100 ~ 103 中的處理實例，但是可以使用 一些其他方法來適當設定存儲位置。例如，作為存儲位置候選r，，僅可以產生使得相同數量的對數 似然率、或對數後-驗概率qn能夠;故存〗諸到RAM中的那些候選。特 別地，當根據表達式(19)確定的視碼長N，可以用RAM數N,除盡時，產生存儲位置候選，從而可以滿足Naddr-NVHam, ^旦是如果視碼長N，不能用RAM數N圓除盡，則產生存儲位置候選，從而滿 足Na她-ceil (NVN,)或Naddr = floor ( NVNram )。在當前情況下， 產生存儲位置候選，4吏得關於一個碼字的24個對lt似然率^或對 數後驗概率qn被六個六個地存儲到四個RAM中。進一步地，在該 實例中，RAM 100~ 103中的每個均具有與通過LDPC石馬的碼長或 校驗矩陣的權重矩陣的列數除以RAM的數量獲得的值，或通過將 這樣獲得的值加1獲得的值或從所獲得的值減1獲得的值對應的地 址數。雖然以上參考圖7描述的處理中描述了將產生的候選總數可以 通過N,^表示，但是當根據該方法產生存儲位置候選時，將產生 的存儲位置候選的總數nMAx可以通過表達式(24)表示。應注意， 符號"!"表示階乘，xCy表示從x個選擇中選擇不同的y個選擇的 結合的總數。這時，可以減少將通過存儲位置候選產生處理產生的 4矣選的lt量，並且可以實現更高效的4臾索。formula see original document page 40…(24)在表達式(24)中，上部當N，可以用N咖除盡時同上，下部在4壬4可其^(也'|"青況下以此方式，可以通過與以上參考圖6~圖8描述的處理不同的 方法適當設定存儲位置。總之，必須能夠確定以上參考圖3描述的 適當存儲位置。另外，如上所述，通過存^f渚位置確定部201執4亍以上例如參考 圖6 -圖8描述的處理確定的存儲位置被提供給控制部203並被預 先存儲到控制器112等的內部存儲器中。特別地，存儲位置候選r， 作為確定的存儲位置r通過在圖6的步驟S106的處理被存儲到控制 器112等的內部存儲器中。現在，參考圖9的流程圖描述通過解碼裝置10的解碼處理。例 如，當接收將被解碼的碼字時，執行該處理。在步驟S201，變量m和1 4皮初始4匕為1。在步艱《S202，解碼部202將對悽t似然率A^存4諸到RAM 100 103中。此時，例如，對應於碼字的每個位的對數似然率^#皮提供給開關108-111,並且基於存儲在控制器112等的內部存儲器中的存儲 位置控制用於控制開關108-111的控制信號cll cl4。從而，24 個對數似然率、被連續存儲到RAM 100 ~ 103的適當地址中。應注意，通過隨後的處理，存〗諸在RAM 100 ~ 103的地址中的乂於悽^f以然率、一皮更4斤為24個^j"lt後-驗;f既率qn。在步驟S203,解碼部202從RAM 100 ~ 103中讀出在校驗矩P車 H的第m行中與滿足hmn=l的(m， n )對應的對數似然率、。此時，基於存儲在控制器112等的內部存儲器中的存儲位置和 校驗矩陣H的信息輸出控制信號c21 ~ c24,並且在更新之前從RAM 100~ 103中讀出在校驗矩陣H的第一行中與滿足hm^1的(m,n) 對應的那些對數似然率^作為對數後驗概率qn，然後將其提供給變 量節點處理部113。進一步地，基於控制信號c31 c34從RAM 104 ~ 107讀出數學運算所需的那些消息amn作為信號al ~a4，然後將其 才是供給變量節點處理部113。在步驟S204，解碼部202計算(Xmn和Pn的值。此時，變量節點處理部113執行由表達式(13 )表示的數學運算，並將這樣計算的Pn提供給校驗節點處理部114。進一步地，校驗節點處理部114執行由表達式(14)表示的數學運算。在步驟S205,解碼部202判定用於校驗矩陣H的一行的與滿 足hmn=l的(m, n )對應的對數似然率、或對數後驗概率qn的所有 是否均被從RAM 100 ~ 103讀出。如果判定出對數似然率、或對凝: 後驗概率q。的所有還沒有被讀出，則處理返回到步驟S203，以重複 4丸4亍步艱朵S203 ~ S205的處5裡。應注意，由於才丸4於以上參考圖6描述的處理來確定存^f諸位置， 所以通過多於一次地乂人RAM 100 ~ 103進行讀取來讀出用於才文-驗矩 陣H的一行中與滿足hmn-l的(m,n)對應的對數似然率、或對數 後-瞼;f既率qn。如果在步驟S205判定出已讀出對ft似然率、或對悽史後驗相剋率 qn,即，在執行兩次步驟S203 S205的處理之後，處理進行到步驟 S206。在步驟S206，解碼部202控制校驗節點處理部114使用根據表 達式(13 )確定的關於校驗矩陣H的一行的pj直數學運算更新消息 anm,並將更新消息a圓作為信號al， ~ a4，提供給算術單元115和 RAM 104 ~ 107。進一步地，算術單元115執行由表達式(15 )表示 的數學運算來計算對數後驗概率qn，從而更新存儲在RAM 100 ~ 103中的j直。在步驟S207,判定是否對校驗矩陣H的M列(即，整個校驗 矩陣H)執行對數後驗概率qn的更新。在當前情況下，M為12。 如果在步驟S207判定出變量m不等於列數M，則由於還沒有完成 對所有行的計算，所以處理進行到步驟S208，在該步驟變量m力口 1 。 此後，處理返回到步驟S203。另一方面，如果在步驟S207判定出 變量m等於列數M，則由於已經完成了用於所有行的計算，處理進 4亍到步駛《S209。在步驟S209,解碼部202執行奇偶校驗。此時，奇偶校-瞼部 116 4丸4亍在以上描述的分層BP解碼方法中的步驟B3 ~ B4的處J裡， 以產生表示奇偶4交驗的結果(OK或NG )的信號P,然後將信號P 提供給控制器112。在步驟S210,解碼部202判定在步驟S209的奇偶^^驗的結果 是否為OK或表示重複次數的變量1是否達到重複次數的上限lmax。 如果判定出奇偶校驗的結果不是OK,即，奇偶校驗的結果是NG， 則處理進行到步驟S2U。在步驟S211,解碼部202將變量m的值初始化為1並將變量1 的值力o 1。此後，處理返回到步驟S203，以便重複^丸行在以步驟S203 開始的多個步驟的處理。另一方面，如果在步驟S210判定結果為OK或表示次數上限 的變量1達到重複次數的上限lmax,則處理進行到步驟S212,在該 步驟解碼部202輸出解碼的結果。此時，輸出控制信號c4，以講關於一個碼字的對數後驗概率qn 乂人開關117 llT出到符號判定部118。然後，符號判定部118在正和 負符號之間判定提供至其的信號，並且例如分別映射關於數據的正 和負的"0"和"1"。然後，符號判定部118輸出解碼結果的關於一 個碼字(24位)的結果數據。按照以上描述的方式執行LDPC碼的解碼。以此方式，通過上述實施例，對數似然率、或對數後驗概率qn 孚皮存Y諸到多個RAM ，即，Nram個RAM,並且同時讀出在校驗矩陣 的每行中與滿足hm^1的(m， n)對應的對數似然率、或對數後驗才既率qn。因此，當與對悽史似然率？tn或對悽t後驗扭無率qn淨皮存儲到單個RAM中並通過i也址指定而逐個讀耳又的可選配置相比4交時，解碼所必 須的時鐘^t可以^皮抑制為一個第Nram。另夕卜，通過上述實施例，關於才交-險矩陣的一^f亍的計算，即，消 息amn、 pn的值和對數後驗概率qn的數學運算被分別執行Nrd次。因 》匕，與一次全部讀出關於才交-驗矩陣的一4亍的對悽"以然率A^或對悽t後驗概率qn以及並行執行關於一行的計算的可選配置相比較時，電路
尺寸可以減小到1/Nrd並且還可以預期共享計算電^各。
進一步地，在同時全部讀出關於校驗矩陣的一行的對數似然率
^或對數後驗概率qn的可選配置中，需要選擇器從存儲在寄存器等 中的對悽t似然率^或對悽t後-驗相剋率qn中連續選擇希望的對悽t似然率 、或對數後驗概率qn。相反，通過上述實施例，不需要上述這樣的 選擇器，從而可以預期電路尺寸的減小。
還可以將本發明的實施例應用於用於LDPC碼的解碼裝置，該 解碼裝置^f吏用由具有例如通過表達式(21 )表示的^t環結構的小矩 陣形成的校驗矩陣。如上所述，表達式(21)包括32個小矩陣，每 個小矩陣被形成為包括四行和四列的4 x 4矩陣。
圖10是示出了應用本發明的實施例的解碼裝置的另一個配置 實例的框圖。圖10所示的解碼裝置11使用由表達式(21 )表示的 校驗矩陣H執行LDPC碼的解碼。
在圖10中所示的解碼裝置11中，不同於圖4中所示的解碼裝 置10,不是1個而是P個(在當前情況下為4)數據被寫入到RAM 100-107中的每個的一個地址中。從而，解碼裝置11包括用於對-首先^皮寫入的P個對lt似然率^進4於積分並將P個對悽史似然率^ 組合成一個^t據的符號連接電^各123。
例如，當一個對數似然率^或對數後驗概率qj皮表示為一個八 位字節的數據時，四個八位字節的H據;故寫入到RAM 100 ~ 107的 每個的一個;也址中。
進一步地，圖IO所示的解碼裝置11包括在輸出解碼結果之前 將組合後一個悽t據轉換回原始的P個(在當前情況下為4)數據的 符號分割電路124。因此，在圖10中，表示提供給RAM 100-103的數據的信號 dl ~ d4、表示/人RAM 100 ~ 103讀出的悽丈才居的4言號gl ~ g4、以及表 示,人RAM 104 ~ 107讀出的悽史據的信號al ~ a4均對應於例如四個/V 位字節的數據。
進一步地，圖10所示的解碼裝置11包括用於分別對從RAM 100- 103輸出的四個數據的位位置進行移位的循環移位器119 ~ 122。循環移位器119 ~ 122對形成例如對應於四個對^t似然率？1 或 對數後驗概率qn的四個八位字節的數據的八位字節進行一維。
雖然表達式(21 )的32個小矩陣均^皮形成為四4於和四列的矩陣， 但是在每個小矩陣中，只有一個元素具有值1,即，每行中的非零 值。因此，當四個對數似然率^或對數後驗概率qn被提供給變量節 點處理部113時，必須指定四個對ft似然率、或四個對悽t後驗相剋率 qn中與才交-驗矩陣H的非零值的元素(即，滿足hmn=l的乂於數似然率 、或對lt後-驗相剋率qn的元素)對應的對lt似然率^或對悽t後驗相剋率 qn之一。
例如，循環移位器119-122將對應於與四個對lt似然率？tn或
四個對悽t後-驗和克率qn對應的四個八位字節的數據中滿足hmfl的對
悽t似然率、或對悽t後-驗扭克率qn的八位字節的數據移位至第 一個八位 字節。應注意，通過從控制器112輸出的控制信號c51 c54控制循 環移位器119 ~ 122，以通過上述方式對^t據進^於移^f立。
因此，表示從圖10中的循環移位器119 ~ 122輸出的數據的信 號gll ~ g14 ^於應於通過分別^N言號gl ~ g4的#:才居的/^[立字節4立置 進行移位獲得的用於四個八位字節的數據。
進一步;也，雖然圖10中所示的變量節點處理部113~算術單元 115和延遲電路125執行與圖4中所示的處理類似的處理，但是他們均由並行連接的四個數學運算電路形成，以便對四個數據並行寺丸 行處理。
因此，表示從變量節點處理部113輸出的數據的信號bl b4、 表示從校驗節點處理部114輸出的數據的信號al， ~ a4，、以及表示 從算術單元115輸出的數據的信號gl， g4，分別對應於例如四個八 位字節的^t據。
圖10中所示的解碼裝置11的其他部分類似於圖4中所示的解 碼裝置10。
因此，能夠應用本發明的實施例來配置^f吏用用於由具有循環結 構的小矩陣構成的校驗矩陣的LDPC碼的解碼裝置。
此外，4艮據本發明的實施例，如果碼長小於碼長N (在當前情 況下為24),則能夠執行使用不同編碼率、不同碼長或不同校驗矩 陣的LDPC碼的解碼。
例如，當使用不同於以上描述的實例中的編碼率、碼長或校驗 矩陣時，以上參考圖6~圖8描述的處理;陂再次^^亍，並且通過存 4諸位置確定部201確定新的存4諸位置。
然後，控制器112輸出對應於新的存儲位置和校驗矩陣的控制 信號cll ~cl4、控制信號c21 ~c24以及控制信號c31 ~ c34。
但是，應注意，新確定的Nrd x M，的值必須低於Nrd x M，的原始值。
作為實例，研究例如代替通過表達式(16 )表示的校驗矩陣H, 使用由以下給出的表達式(25 )表示的校驗矩陣的情況。表達式(25 ) 的才交-瞼矩陣H用於編碼率為2/3的LDPC碼，並JU亍4又重的最大4直WRMax為WRMax =11。在當前情況下，由於Nram = 4 ，則才艮才居表達式
(18)， Nrd = 3 (= ceil(wRMax/Nram) = ceil(l 1/4))。
(25)
在該實例中，當通過以上參考圖6~圖8描述的處理確定存《諸 4立置日寸，侈寸^口，獲4f r， = [l 1 1 12323342442213233144 4] 作為確定的存儲位置候選r，-[r、 r，2 ... r，i ... r，N，]。通過將對數後-驗 概率qn等存儲到這樣獲得的存儲位置中，使用由表達式(25 )表示 的才史-驗矩陣H的LDPC碼可以通過以上參考圖4或圖10描述的配 置的解碼裝置IO或11判定，而無需改變由表達式(16)表示校驗 矩陣H的電^各構成。
應注意，雖然上述實例4吏用分層BP解碼方法，4旦是本發明的 實施例還可以應用於4吏用和積解石馬方法的解碼裝置。
應注意，雖然上述的一系列處理可以通過硬體，執行，但是還可 以通過軟體來執行。當通過軟體執行這些處理時，構成軟體的程序 從網絡或程序記錄介質被安裝到結合至專用硬體的計算機中，或例 如，通過安裝多種程序可以執4亍多種功能的圖11中所示的通用個人 計算4幾500中。
參考圖11,中央處理單元(CPU ) 501才艮據存^f諸在ROM (只讀 存儲器)502中的程序或從存儲部508加載到RAM (隨4幾存取存儲 器)503中的程序來4丸4亍多種處理。CPU 501 4丸4亍處理所必須的數: 據還4皮適當地存儲到RAM 503中。
Goooollo
oooolioo
ollooooo
lioooooo
lilillol
lliooooo
oolo-olol
looloolo
o- 二 -I -- --
oolllooo
loooolol
ololoool-
lolooolo
I，CPU 501、 ROM 502和RAM 503通過總線504 4皮jt匕連4妄。輸 入/輸出接口 505還連接至總線504。
包括鍵盤、滑鼠等的輸入部506、包括可以為CRT (陰極射線 管)或LCD (液晶顯示)單元的顯示單元、揚聲器等的輸出部507、 由石更盤等形成的存儲部508、包括數據機、諸如LAN(區域網) 卡的網絡*接口卡等的通信部509均連4妄至輸入/輸出4妄口 505。通信 部509通過諸如互耳關網的網絡執行通信處理。
進一步地，必要時，驅動器510連接至輸入/輸出接口 505。將 諸如磁碟、光碟、磁光碟、半導體存儲器等的可移動介質適當裝載 到驅動器510中，並且必要時，將從裝載的介質讀取的計算才幾程淨皮 安裝到存儲部508中。
當通過軟體才丸行上述一 系列處理時，從諸如網際網路的網絡或可 以由可移動介質511形成的i己錄介質安裝構成^^牛的禾呈序。
應注意，程序記錄介質可以由其上或其中記錄有程序的^茲盤(包 括軟盤(註冊商標))、光碟(包括CD-ROM (緻密光碟只讀存儲器) 和DVD (數字通用光碟))、磁光碟(包括MD (小型碟片(商標)) 或半導體存儲器形成的圖ll中所示的可移動介質511形成，並且4皮 分配以將程序分別從裝置4幾體提供給用戶。另外，程序記錄介質可 以被形成作為ROM502、包括在存儲部508中的硬碟等，其中，記 錄有程序並以預先結合到裝置主體中的形式分配。
應注意，用於執行在本說明中描述的一系列處理的步驟可以不 必須以描述的順序按時間順序來處理，並且包括在不按時間順序處 理的情況下並4亍或串4亍#^亍的處理。
雖然已4吏用特定術語描述本發明的優選實施例，但這樣的描述 僅用於進行解釋，應理解在不脫離以下權利要求的精神或範圍的情 況下，可以作出多種改變和變4匕。
權利要求
1. 一種用於對低密度奇偶校驗碼進行解碼的解碼設備，包括多個存儲裝置，用於將關於一個碼字的對數似然率或對數後驗概率存儲到相互獨立的地址中；以及讀出裝置，用於從存儲在所述存儲裝置中的所述關於一個碼字的對數似然率或對數後驗概率中，同時讀出與在所述低密度奇偶校驗碼的編碼處理中使用的校驗矩陣的預定一行中的非零值元素相對應的多個所述對數似然率或對數後驗概率。
2. 根據權利要求1所述的解碼設備，其中，所述存儲裝置的數量 小於所述校驗矩陣的行權重的最大值。
3. 根據權利要求1所述的解碼設備，其中，從所述存儲裝置讀出 與所述衝交-瞼矩陣的任一4於中的所述非零值對應的所有的所述 對數似然率或對數後驗概率所需的讀出次數是通過用所述校 驗矩陣的行權重的最大值除以所述存儲裝置的數量獲得的值 向上捨入成數字值獲得的數。
4. 根據權利要求3所述的解碼設備，進一步包括存儲位置確定 裝置，用於將關於所述一個碼字的所述對數似然率或對^1:後驗 概率存儲到所述存儲裝置中，使得與所述校驗矩陣的任一行中 的所述非零值元素對應的所有的所述對lt似然率或只於悽t後馬全 概率，能夠以通過用所述4交-驗矩陣的行4又重的所述最大值除以 所述存儲裝置的數量獲得的值向上捨入成數字值獲得的讀出 次數從所述存儲裝置中讀出。
5. 根據權利要求4所述的解碼設備，其中，每個所述存儲裝置均 具有與通過用所述低密度奇偶校驗碼的碼長或所述校驗矩陣 的權重矩陣的列數除以所述存儲裝置的數量獲得的值、或通過 將所獲得的值加一得到的值、或通過從所獲得的值中減一得到 的值相對應的地址數，並且關於所述一個碼字的所述對數似然 率或對數後-驗概率被分別存儲到所述存儲裝置中。
6. 根據權利要求5所述的解碼設備，其中，所述存儲位置確定裝 置產生用於指定所述存儲裝置之一和其中存儲有關於所述一 個碼字的所述對數似然率或對數後驗概率中的每個的地址的 存儲位置確定信息，並且所述讀出裝置基於所述存儲位置確定 信息來同時讀出多個所述對數似然率或對數後驗概率。
7. 根據權利要求1所述的解碼設備，其中，所述校驗矩陣包括具 有P行和P列的多個小矩陣，與每個小矩陣的P個元素相對 應的所述對數似然率或對悽t後馬全扭無率中的P個^皮存^f諸到所述 存儲裝置之一的 一個地址中。
8. —種用於對低密度奇偶校驗碼進行解碼的解碼設備，包括多個存4諸部，被配置為將關於 一 個碼字的對數似然率或對 :數後驗概率存儲到相互獨立的地址中；以及讀出部，^皮配置成/人存卡者在所述存儲部中的所述關於一個 碼字的所述對數似然率或對數後驗和克率中，同時讀出與在所述中的非零值元素相 對應的多個對數似然率或對數後驗概率。
全文摘要
在本發明中，提供了一種用於對低密度奇偶校驗碼進行解碼的解碼設備，包括多個存儲部，被配置為將關於一個碼字的對數似然率或對數後驗概率存儲到相互獨立的地址中；以及讀出部，被配置為從存儲在存儲部中的關於一個碼字的對數似然率或對數後驗概率中，同時讀出與在低密度奇偶校驗碼的編碼處理中使用的校驗矩陣的預定一行中的非零值元素相對應的多個對數似然率或對數後驗概率。
文檔編號H03M13/11GK101295988SQ20081009505
公開日2008年10月29日 申請日期2008年4月28日 優先權日2007年4月27日
發明者品川仁, 山岸弘幸, 野田誠 申請人:索尼株式會社