TW200417156A - Rate-compatible LDPC codes - Google Patents

Description

200417156 玖、發明說明： 【發明所屬之技術領域】 本發明概言之係關於通信， ^ π ^ ^ 具體g之係關於使用低密 =位权驗（LDPC)碼進行速率可㈣錯誤校正之 【先前技術】 在採用速率適應（例如，根據李 系、、充狀況及要求調整傳輸資 枓速率）之通信系統中，存在僖鈐次 仔在得輸貝枓時須使資料速率靈活 有效適應當前通道狀況之需 而罟典型的錯誤校正設計係 Γ理=擇—具有一特定速率及校正能力之固定碼。爲增加 處理具有不同錯誤保護要求之 、、，、、 J默里貝枓、適應時變通 T狀況、補償未充分獲知之參數之彈性，可使用彈性通道 編碼。 爲實施彈性通道編碼，可將資料位元分組爲若干不同尺 寸的塊，此等塊可編碼成具有不同之冗餘量，產生不同長 度之碼字。較佳使用-可適應若干速率之單—母碼而非^ 用若干單獨錯誤校正碼來對不同群組之位元進行編碼。此 作業稱作速率可相容編碼。使用一單一碼替代若干單獨碼 用於每;所需速率，可明顯降低發射器處編石馬及接收器處 解碼之複雜性，然而，複雜性之降低係以某些性能降級爲 、貝 此種速率可相容編碼方法包含速率可相容穿孔迴 旋⑽w碼。此方法及其它當前方法提供有限之性能或在 解碼器處産生非吾人所期望之計算複雜性。 因此，存在一提供高性能的速率可相容編碼方案之需 要，該等方案可在最大限度降低編碼器及解碼器之複雜性

O:\89\89442.DOC 丄：)0 之同時支持速率適應性。 【發明内容】 本發明揭示一種用於ή g L-〜 禋用於自一具有可變長度輸入字之單一低 密度同位校驗（LDpq碼産生呈右 座生具有可變長度及冗餘之碼字之 方法及裝置（apparatus)。依據—同位校驗矩陣産生—用於對 貧：字進行編碼之母碼，其中調整該母碼以反映欲編碼資 料字之尺寸。-產生||矩陣將母〶應用於資料字，以產生 用於傳輸之碼字。在一音力ά； 丨rb rh 子在貫鈿例中，確定一縮減準則並根據 該縮減準則縮減產生器矩卩束 '度土裔矩I早之尺寸。在接收器處，應用對 應的同位校驗矩陣來對所接收碼字進行解碼。 【實施方式】 一錯誤校正編碼系統通常設計爲滿足-資料傳輸之保護 需求。可選擇-具有-給^碼率之固定碼。校正能力匹配 於保護需求並適於可預料之平均或最壞通道狀況。由於傳 輸的貧料可具有多種不同的錯誤保護需要，因此爲達成速 率適應，編碼系統應當具有彈性。此外，適應需要響應時 變通道狀況。 圖1展示一具有一發射器106及一接收器11〇之無線通信 系統1 〇〇。發射器1 06及接收器11 〇皆可爲一能夠發送及接收 資料通#之收發機。爲簡要起見，在圖〗所示系統丨〇〇中僅 展示用於下文說明之彼等功能模組。發射器i 06包括一傳輸 源1 02及一可變速率編碼器1 04。發射器1 06及接收器11 0經 由一通道108通#。接收器包括一可變速率解碼器H2及一 資訊槽114。欲自源1 〇2發送之資訊可包括指示資料保護需

O:\89\89442.DOC 200417156 、原專用> §fL (sSI) ’例如對應於一資料流之控制及發送 仏號的貝汛。源ί〇2提供SSJ (若有）至編碼器1⑽。編碼器1㈣ ：應用於速率適應，即依據SSI調整傳輸速率。解碼器 104進步接收提供關於通道丨〇8特性及品質變化之資訊的 通道狀怨貧訊（CSi)。發射器1〇6可使用⑶來決定用於一傳 輸之編碼。編碼器104應用已適於源1〇2及通道1〇8之可變 碼0 較l係包含一可爲速率適應做修改並可避免於每一速率 、且〇所用之不同編碼器之間切換之編碼器結構。一種用於 提供單一編碼器結構之方法係穿孔迴旋碼，其中不發送某 些:位7L。此等碼稱作速率可相容穿孔迴旋（Rcpc)碼。應 注意’迴旋喝僅係速率可相容碼之一實例，其它實施例可 包^其它速率可相容碼，例如穿孔塊碼、穿孔渦輪碼等等。 山穿孔迴旋碼可滿足一速率相容性限制，其中高速率碼可 嵌入較低速率碼内。雖叙cpc編碼可方便—單—編碼器結 構之使用，但存在性能降級的問題。 根據-實施例’編碼器1〇4應用一種方法自一具有可變長 度輸入字之單-低密度同位校驗⑽％)碼中產生具有可變 長度及冗餘之碼字…LDpC碼係—由—同位校驗矩陣規定 之塊碼，其主要包含零及僅少量幾個】。 所述通信系統1〇〇可具有短至中等的塊長度。[Ope碼已 顯示出顯著優於迴旋碼及嫂美於渦輪石馬之印象性能。應注 意，滿輪碼及LDPC碼皆可導致相當大的解碼複雜性，但 LDPC碼具有更加有效解碼之潛力，因此其較满輪碼爲快：

O:\89\89442.DOC 200417156 在具有甚高資料速率之系統（例如’未來的資料速率爲1 〇〇 百萬位元/秒及更高的無線區域網路（WLAN)或無線個人區 域網路（WPAN))中，一渦輪解碼器可在接收器110處形成一 嚴重的處理瓶頸。LDPC碼可提供一用於滿足位元錯誤率及 解碼速度方面之嚴格要求的選擇方案。 存在兩種LDPC碼：規則LDPC碼及不規則LDPC碼。下文 將提供規則LDPC碼及不規則LDPC碼之定義。據報告，對 於甚長之塊長度而言，不規則LDPC碼優於規則LDPC碼及 渴輪碼。然而，對於短至中等塊長度而言，其對於後兩種 碼之性此改良則微不足道。另一方面，規則碼可設計爲具 有甚大的最小距離dmin(下文將闡述），而不規則碼則不同。 應注意，規則碼設計爲具有甚大的最小距離dmin並具有優良 的錯誤偵測能力。此外，規則碼結構支援高效平行解碼器 κ e方案且因此可達成甚高的解碼速度。下文將具體闡 述規則LDPC碼，然而，其它實施例可應用不規則LDpc碼。 LDPC碼係一線性錯誤校正塊碼。碼係由一尺寸 A (n k)列xn仃的稀疏「同位校驗」矩陣η規定，其中^係輸 X〜、即J 1非零元素。碼率係由及=|表示。一 規則LDPC碼母行包含及每列包含3個1，其中s表示爲·· * {^/n - k) ⑴ LDpC,, ^ α此，s>t。列稱作同位校驗而 子之元素稱作位元。矩陣H可表示爲一稱作機率相

O:\89\89442.DOC -9- 200417156 依圖或1^抓以圖之偶圖，其具有一代表所有位元之節點子 集及另一代表所有同位校驗之節點子集。作爲一簡化但具 說明性之實例，假定一4x8同位校驗矩陣表示爲： 1 1 1 0 0 0 0 0 H= 0 0 0 1 1 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 (la) 如圖2所示，η之Tanner圖表示法由n=8個位元節點及 n-k=4個校驗節點組成。位元節點標識爲標有χι，χ2,…，心的 圓形節點且對應於一使用此碼産生的一碼字的8個編碼位 元。校驗節點標識爲標有f^f^f^f4的方形節點且對應於由Η 執行的4次同位校驗。 通常使用一稱作「訊息傳遞」演算法之方法對LDPC碼進 行解碼。此〉貝异法依據同位校驗矩陣之Tanner圖表示法運 作’並計算「軟」位元判定，該判定包含用於編碼位元的 符號和可靠性資訊及關於同位校驗之軟資訊。然後，以一 疊代方式在位元節點與校驗節點之間交換包含軟位元判定 之訊息及包含同位校驗軟資訊之訊息，直至達到一預定停 止準則。因此，作出最後的「硬」位元判定。 應’主思’與規則LDPC碼相反，不規則LDPC碼在其列及 行中具有1之非均勻分佈。在任一情形中，同位校驗矩陣皆 具有低密度的1。可藉由附加隨機産生的權值ί行向量來構 成同位校驗矩陣，以使所産生的列權值爲s。爲減少産生低 權值碼字之機率，限制且將//中任意兩行限制為僅出現 O:\89\89442.DOC -10- 一次非零位元交疊。拖丄 行，的!不應出現在；^，陣"中任選兩行時，兩 T_er圖中將出 位置多於-次。否則，在對應 4被，其可導致解碼性能降級。佶用μ 半隨機構造找到—「俱& 及使用此 機率甚接近於找到—二」=即，：具有大“的碼)的 解碼器作出—錯 …石馬之取紐距離‘°係指當 量。距正確碼字距離广：能夠出現的位元錯誤之最小數 誤判定’此乃心:::::::"器最可能作出的錯 块判定亦會時常發生 ”匕錯 之錯誤判定來支配。最短=:恰好係由具有最短距離 除上述方法外，還^離係由—㈣碼之結構決定。 π ^ ^ <子夕種其他用於產生具有所需性質之 同位权驗矩陣之方法。 Η = [PMn—k 斯根:康：實施例，—旦已構造同位校驗矩陣，即可藉由高 〃約“去法及可能的行調換將矩陣开表示爲如下形式： —Γίγ>λ /ί ί (2) 矩陣u係尺寸爲“)χ“)的單位矩陣。矩陣ρ之尺寸 (峰。對應的碼産生器矩陣。表示爲： (3) (4) 糸統碼，其在一實施例 料字w映射（編碼）爲碼字 G = [lkMPT 其滿足如下性質· G-HT =〇 具有此形式之産生器矩陣可生成一 中爲有利。根據如下方程式將一資

0 \89\89442.DOC -11 - (5) 其中"及,皆係、列向量，且發射器使用産生器矩陣g。接收器 使用同位校驗矩陣以對所接收碼字少實施多達“)次的單 獨同位校驗。所接收碼字表示爲： y = c + e， (6) 其中e表示-錯誤字。在接收器處執行_校驗以驗證： y · Ητ = 0， ⑺ ，意味著錯誤字Km，亦即，所接收及解碼的瑪 子不包含錯誤。若未滿足⑺，則所解碼碼字包含錯誤。 轉置同位校驗矩陣#表示爲：

Λ Ln-k Ητ = ⑻ Θ中展示使用産生器矩陣的編碼過程及使用同位校驗 矩陣丑對所接收碼字或樣本進行解碼及隨後驗證之過程。系 統250包括一向編碼器254提供資料之資訊源252。實碼（亦 即’矩陣好及矩陣G)可離線産生且未必係作業期間系統所實 施的編碼/解碼之一部分。編碼器254對資料進行編碼並經 由一傳輸鏈路208將所編碼資料傳輸至一接收器。單元262 實施解碼及同位校驗，並將結果提供至一槽264以供接收器 使用。

O:\89\89442.DOC -12- 右使用母碼，則可使用産生器矩陣σ將短於七之資料字 、扁碼爲具有變化碼率之碼字，以適應一所需資料速率之範 圍f先，假定對一長度爲W之短資料字進行編碼，其中 及 圖3展示自輸入資料字禮生碼字c。在此實例中4 。括版素：υ w個資料元素，表示爲⑽·， )(介個令。然後，將産生器矩陣G應用於輸入資料字『 產生馬字由卜一^)個零、免你個系統位元（其僅爲原始資料 位兀）及（叫個校驗位元組成。若需要，可在傳輸之前廢棄 零，由此產生一長度爲〜//之碼字，其表示爲： ^ff = n-k + ke. ff (9) 其新碼率表示爲： (1〇) R' = keff/neff 零填充等同於刪除G(或A的上部（％)列。f際上，對一 又爲zte//的資料子之編碼可不包含零填充。相反，其可僅 包含W個資料位元乘以矩陣，(減去其上部.列》且最 終碼字將#由所産生的附加至^個系統位元的(W)個校 驗位元組成。如圖4所示，在接收器處，同位校驗矩陣孖Γ(直 對應的最上部^一‘）列已刪除）執行卜一々)次單獨同位校驗了 在圖4中恢復零係說明所接收的縮短碼字係最大長度碼字 的一子集。具體而言，圖4展示所接收碼字具有恢復的卜―^) 個零、<//個系統位元及（〃 —A)個校驗位元，但實際上，接收 器處實施的同位校驗可僅包含個系、統及校驗位元 及Θ (減去其最上部（A-列）。當广y之結果滿足上文給出

O:\89\89442.DOC -13 - 200417156 之方程式（7)時，接收器驗證所接收碼字少。 圖8A展不發射器處的運作，其中過程3⑻係用於準備一用 於傳輸之貧料字，在步驟3Q2中，首先自記憶體中檢索適當 的産生器矩陣。在步驟3〇4中，當接收一資料字時，過程確 定該資料字之尺寸。在步驟3〇6中，若該資料字具有小於免 之尺寸h//，則在步驟308中，添加零來填充資料字以産生以 。然後，將所填充資料字w應用於産生器矩陣σ。 圖8Β展不發射器處之另一過程35〇，其中在步驟乃2中， 自記憶體中檢索產生器矩陣G。在步驟3μ中，當接收一資 料=時，過程確定該資料字之尺寸。在步驟州中，若該資 料子/、有小於^之尺寸h//，則過程繼續至步驟36〇，以將 資料字應用於產生器矩陣⑽一部分（例如較低部分）。在此 障形^ ’不使用零填充資料字。否則，過程繼續至步驟， 以將貧料字應用於全部的産生器矩陣〇。 如圖9A所示，在接收器處，一過程4〇〇開始於步驟術， 在該步驟中，自記憶體中檢索—同位校驗矩陣…該同位校 驗矩陣峨於圖8A所示之產生器矩陣G。在步驟404中， 接收r碼字y並衫該碼字之尺寸。在步驟偏中，若所接 收碼子少之長度小於η，則在步驟4 〇 8 * 之卜多然後在步驟41。中：將’棄同位校驗矩陣^ _減去W列）。 將碼子讀用於同位校驗矩 圖9Β展示接收器處之另一過程45〇,其中在步驟…中， 自記憶體中檢索一同位校驗矩陣开。在步驟454中，接收一 碼字少並確定該碼字之尺寸。在步驟…中，若所接收碼字^

O:\89\89442.DOC -14- 200417156 之長度小於η，則在步驟458中使用沴一 零填充該碼字以生 成一長度η。否則，過程繼續至步驟460，以應用全部的同 位校驗矩陣开。 此外，假定將一全長度（亦即長度k)之資料字編碼爲一其 校驗位元少於（π-Α)之碼字。爲將校驗位元數量減少"，可 在編碼之後穿孔（puncture)最後〜個校驗位元，或可完全省 略最後％個校驗位元之計算，此等於刪除G(或ρΓ)之最右部 〜行。在圖3中，將欲刪除行表示爲一淡影線矩形2〇4。在 此情形中，所産生碼率表示爲： 01) R = k/n - rip 如圖4所示，在接收器處，對應的同位校驗矩陣僅由原始 矩陣丑7'之最左部行組成’其中保留行由—暗灰色影 線矩形202表示。另一選擇爲，解碼器可將「缺少」的校: 位元視作擦除位元（erasure)並在執行所有Μ)次同位校驗 之前在其位置内插入零。 …所述使用-由的于的一子集構成之同位校驗 陣來獲得較高速率碼$本 年碼子牯，全尺寸同位校驗矩陣之性質 佳轉入較小矩陣。呈舻一田 、 須滿足⑴之限㈣件。 狱矩陣 作爲-實例，假定一 碼本。兮·am、 〜Μ具有四種不同速率 馬子遠母碼之同位校驗矩陣展 矩陣標爲仏，且ι ㈡5中。取小同位校 及具有仃榷值ί，亦即，| γ 的矩陣可藉由自g , η 母仃具有Η固1。額 由自取小同位校驗矩陣右下角擴展而形成。

O:\89\89442.DOC -15 - 200417156 作私的第二最小矩陣，由片 一" 7的一右下角擴展有一方拓陆/甘 灯權值皆爲〇、右手側擴展有一 ^ 々矩p皁及底部擴展古— 稀疏矩陣所構成。在稀疏、 干τ 母一列皆至少呈古_ 個1以保證較小的矩陣編 - 八 旱、·扁碼位7^與擴展矩陣編碼位元之問 的足夠相依性’但另一方面卻保持甚稀 造及解碼。所產生同位校驗矩叫具有至=2= 因此，雖然㈣㈣乎—❹wΜ 4之仃推值。 ^規則冋位校驗矩陣，但其不再是 一規則同位校驗矩陣。分g丨雜4 早刀別輪作私及圮的較大矩陣以相同 方式建構而成。在建構全尺寸矩陣之後，如上文所述，使 用局斯-約當消去法將其轉換爲系統形式。所產生矩陣好 展不於圖6中。 圖1〇展不-種使用少於（^)個校驗位元對資料字進行編 碼之方法。過程500開始於步驟5〇2，在該步驟中，檢索一 産生器矩陣。在步驟5G4tn資料字。在此情形下， 在步驟鳩中確定—準則，例如所量測的通道狀態高於-閨 值。對於良好的通道狀態，則不期望傳輸所有校驗位元。 當通道狀態、良好日寺’在步驟508中，#由刪除同位校驗行的 -部分來縮減産生器矩陣σ之尺寸'然後，將資料字w應用 於產生器矩陣G。 圖11展示一對應的解碼過程600，其用於對所接收的支援 縮減同位校驗矩陣尺寸的傳輸進行解碼，其中在步驟6〇2 中，自記憶體中檢索一同位校驗矩陣丑。在步驟6〇4中，接 收一碼字。在判定菱形606中，若滿足一縮減準則，則過程 繼續至步驟608，藉由廢棄其心行來縮減同位校驗矩陣之尺 O:\89\89442.DOC -16- 200417156 寸°否則’過程繼續至步驟㈣，將所接收訊息鴻用於全 尺寸同位校驗矩陣开。應注意，在步驟6〇8中縮減同位校驗 矩陣//之後，過程亦繼續至步驟6〗〇。 <:之可二=情形，亦即，嶋人資料字具有〜 、又 産生〜)個校驗位元。在此情形下，如圖 6中垂直虛線所指將僅使用對應m戈制好上部 (卜“j列，且將刪除歸左部卜心)行（或者，相等地，# 上U歹i)刪除此等行不顯著改變整個同位校驗矩陣 之性質。 —圖12展示-圖8績示過程與圖_示過程相組合之編碼 只％例士圖所不’在步驟(7〇6)中，若資料字長度小於輸 入塊長度’則在步驟708中’使用零填充資料字。然後，在 乂驟中過私°平估一縮減準則。該縮減準則可係一通道 扣貝準則’例如c/Ι閾值等。替代實施例可使用影響一給定 系統之運作及/或性能之其它準則。若滿足縮減準則，則在 步驟（712)中縮減産生器矩陣之尺寸。 圖13展示一將圖9Α所示過程與圖11所示過程相組合之解 馬貝施例。如圖所不，在步驟（_)中，若資料字長度小於 輸入塊長度，則在步驟808中廢棄同位校驗矩陣中的若干 列…、、後’在步驟812中，過程評估一縮減準則。該縮減準 則可係通道品質準則，例如c/l閾值等。其它實施例可使 用影響'給定系統之運作及/或性能之其它準則。若滿足縮 減準則’則在步驟(814)中縮減同位校驗矩陣之尺寸。 般而σ，如上文所述，可使用一稱作訊息傳遞演算法

O:\89\89442.DOC -17- 200417156 之方法對LDPC碼進行解碼，該方法之目的係㈣最可能滿 ⑺之碼字’且該演算法依據稱作如⑽圖之同位 =驗矩陣圖形表示法運作。該圖由表示編碼位元之η個位元 芦..表7Γ由同位;^驗矩陣規定的（以)次同位校驗之（ 竭點構成。該演算法以-疊代方式在位元節點及校驗 即點之間來回傳遞關於編瑪位元之機率訊息，直到滿足所 有“)次同位校驗，藉此形成由每一編碼位元之符號及可 靠性資訊組成的軟判定之基礎。軟判定可方便地按與已知 渦輪財式相同之方式以對數似，然比（LLR)形式表示。訊息 傳遞演算法之最佳版本稱作和積演算法，一般而言，此演 算法及-稱作最小和演算法之低複雜性逼近法及任一其它 基於訊息傳遞之演算法皆可用於對速率可相容LDPC碼進 行解碼，例如上述實施例。 在解碼過程之前’發射器向接收器提供關於正確使用同 位校驗矩陣之資訊。發射器及接收器可協商建立分別用於 發射器編碼及接收器解瑪之矩陣結構。應注意，可協商G 矩陣及//矩陣之正確使用，例如哪些列及行可廢棄等。°此 外，使用-單-母碼可能難以囊括所有可能的運作狀離. 因此’-系統可具有-組供選擇的母碼，每一母碼皆^適 應-組唯-碼率。此可達成更細的可用碼率與資料速率之 量化度（g—ty)。另-選擇爲’可依據運作狀態或假設 (例如鏈路品質或其它度量）預定矩陣格式。 熟習此項技術者將瞭解可使用多種不同技術及技法中任 一技術及技法表示資訊及信號。舉例而+ 3 上文可能提及 O:\89\89442.DOC -18- 200417156 的資料、指令、命令、：責訊、信號、位元、符號及晶片皆 可由電壓、電流、電磁波、磁場或磁粒子、光場或光粒子 或上述之任一組合來表示。 熟習此項技術者應瞭解，結合本文所揭示實施例闡述的 各種說明性邏輯塊、模組、電路及演算法皆可實作爲電子 硬體、電腦軟體或二者之各種組合。爲清楚地闡釋硬體及 軟體的此種可互換性，上文概括地闡釋了各種說明性元 件、塊、模組、電路及步驟的功能。此種功能性實作爲硬 體還是軟體取決於特定應用及施加於整個系統的設計制約 條件。熟習此項技術者皆可針對每一特定應用以不同方式 貫施所述功能性，但不應將此等實施決定解釋爲導致背離 本發明之範疇。 結合本文所揭示實施例所述的各種說明性邏輯塊、模 組、及電路可藉由下列為執行本文上述功能而設計的裝置 貝施或執行· 一通用處理器、一數位信號處理器（DSp)、一 應用專用積體電路（ASIC)、一場可程式設計閘陣列（FpGA) 或其他可程式設計邏輯裝置、離散閘或電晶體邏輯、離散 硬體元件或上述相關裝置之任一組合。通用處理器可係 欲處理器或者，該處理器亦可係任一傳統處理器、控 制器、微控制器或狀態機。一處理器亦可構建爲計算裝置 之一組合，例如一DSP與一微處理器之組合、複數個微處 理器、一或多個微處理器結合一 Dsp磁芯、或任何其他此 等組態。 結合本文所揭示實施例闡釋的方法或演算法的步驟可直 O:\89\89442.DOC -19- 接具體化於硬體中、一ώ — ^ 处理器執行的軟體模組中戍- 者的一組合t。一軟體模 ^ ^ 、 了駐存於RAM記憶體、快閃 憶體、ROM記憶體、EPRC)M ° .σσ 。己隐體、EEPROM記憶體、暫 存為、硬碟、一可抽換 p , 朱 CD-ROM、或此項技術中 巳知的任一其他形式 ^ , 仔琛體中。可將一實例性儲存媒 體輕合至處理器，以使該處 、 羼理益可自該儲存媒體讀出及向 该儲存媒體寫入資訊。另一 、擇爲，該儲存媒體可與處理 器爲-整體。處理器及儲存媒體可駐存於一遺中。而該 ASIC可駐存於-錢者終端巾或—通㈣統基礎結構元^ 土也。等4者’處理H及儲存媒體可作爲離散元件駐 存於-使用者終端中或-通信系統基礎結構元件中，包括 (仁不限於）中央父換局、一有線/無線存取點、一基地台 等。 中，包括（但不限於）一中央交換局、一有線/無線存取點、 提供上述有關所揭示實施例之說明旨在使任―熟習此項 技術者皆能夠製作或使用本發明。熟f此項技術者將易於 得出該等實施例之各種修改，且本文所定義的—般原理亦 可適用於其他貫施例，此並未背離本發明之精神或範疇。 因此，本文並非意欲將本發明限定於本文所示實施例，而 欲賦予其與本文所揭示原理及新穎特徵相一致的最寬廣範 疇。 【圖式簡單說明】 圖1係一通信系統中的一編碼傳輸方案之圖示。 圖2係一同位校驗矩陣//之Tanner圖形表示法。 O:\89\89442.DOC -20- 200417156 圖3展示藉由一産生器矩陣^對一 成一碼字C。 資料字W進 行編碼以形 圖4展示藉由應用同位校驗矩陣謂一所接收碼 同位校驗。 ^ 圖5展示一速率可相容同位校驗矩陣丑。 圖6以系統形式展示一速率可相容同位校驗矩陣开。 圖7展示-使用速率可相容編碼之無線通信系統。 圖8A及圖㈣展示在發射器處的速率可相容編碼 子少進行 程圖 之流 圖 圖 圖9A及圖9B係展示在接收器處的適應性解碼之流程圖。 圖10係I不包含產生器矩陣縮減之資料字編碼流程 〇 圖11係-展示包含同位校驗矩陣縮減之瑪字解碼流程 圖12係展不包含產生器矩陣縮減之速率可相容碼編瑪 方法流程圖。 圖13係-展示包含同位校驗矩陣縮減之速率可相容碼解 碼方法流程圖。 【圖式代表符號說明】 100無線通信系統 102傳輸源 104 可變速率編碼器 1G6發射器 1G8 通道

O:\89\89442.DOC -21 - 200417156 110 接收器 112 可變速率解碼器 114 資訊槽 fl 校驗節點 fl 校驗節點 fs 校驗節點 f4 校驗節點 Xl 位元節點 X2 位元節點 Xs 位元節點 X4 位元節點 X5 位元節點 Xe 位元節點 X? 位元節點 X8 位元節點 200 産生器矩陣 202 保留行（暗灰色陰線矩形） 204 欲刪除行（淡陰線矩形） Hj 最小同位校驗矩陣 t 行權值 H 同位校驗矩陣 P 矩陣 250 系統 252 資訊源 O:\89\89442.DOC -22- 200417156 254 編碼器 262 單元 264 才曹 2〇8傳輸鏈路 u 資料字 c 碼字 7 碼字 3〇〇用於準備一用於傳輸之資料字之過程 302自記憶體中檢索産生器矩陣g 3 04 接收資料字 306 keff< k ? 3 08使用（^；一^)個零填充資料字以形成u 310 將u應用於産生器矩陣g 350另一用於準備一用於傳輸之資料字之過程 352自記憶體中檢索産生器矩陣G 354 接收資料字 356 keff< k ?

3 58 將資料字應用於全矩陣G 360 將資料字應用於矩陣G之一下部部分 400 接收器處的一過程 402 自記憶體中檢索一同位校驗矩陣丑 404 接收資料字y 406 keff<C k ? 408 廢棄同位校驗矩陣中的（h列 O:\89\89442.DOC -23- 410200417156 450 452 454 456 458 460 500 502 504 506 508 510 600 602 604 606 608 610 700 702 應用同位校驗矩陣丹 接收器處之另一過程 自記憶體中檢索一同位校驗矩陣// 接收資料字y ke/f< k ? 使用零填充碼字 應用同位校驗矩陣丑 使用少於個校驗位元對資料字進行編 法 之方 自記憶體中檢索産生器矩陣G 接收資料字 是否滿足縮減準則？ 藉由刪除同位校驗行來縮減産生器矩陣G之尺寸 將u應用於産生器矩陣^ 用於對所接收的支援縮減同位校驗矩陣尺寸之傳 輸進行解碼之過程 自圮憶體中檢索一同位校驗矩陣好。 接收碼字 是否滿足縮減準則？ 廢棄同位校驗矩陣中的〜行 將少應用於同位校驗矩陣丹 圖8 A所示過程與圖丨〇所示過程相組合之編碼實施 例

自記憶體中檢索産生器矩陣G

O:\89\89442.DOC -24- 200417156 704 接收資料字 706 keff< k ? 708使用^-心#)個零填充資料字以形成“ 710 是否滿足縮減準則？

712藉由刪除同位校驗行來縮減産生器矩陣G之尺寸 714 將w應用於産生器矩陣G 800 圖9A所示過程與圖11所示過程相組合之解碼實施 例 802自記憶體中檢索同位校驗矩陣丑 804 接收碼字>； 806 keff< k ? 808 廢棄同位校驗矩陣中的（K#)列 810 應用同位校驗矩陣丑 812 是否滿足縮減準則？ 814 廢棄同位校驗矩陣//Γ中的〜行 O:\89\89442.DOC -25-

Claims (1)

1. 417156 拾、申請專利範園： 一種用於在一 含： 通L系統中對傳輸進行編碼之方法，其包 石隹疋一呈有一^ 八兩 第一位元長度之第一碼； 接收一具有~裳-Er- λ, 一 第一位疋長度之資料字，其中該第二位 兀長度小於該第—位元長度； 使用若干個零填充該資料字，以將該資料字擴展至該 弟一位元長度；及 使用該第1對該所填充資料字進行編碼。 2.根射請專利範圍第W之方法，其中確定該第 含： 確定一同位校驗矩陣；及 依據該同位校驗矩陣確定一産生器矩陣。 3·根據申請專利範圍第2項之方法，其中該同位校驗矩陣 包含一低密度同位校驗（LDPC)碼。 4.根據申請專利範圍第1項之方法，其進一步包含： 自該第一碼字中廢棄若干零以形成一縮短的第一石馬 字；及 傳輸該縮短的第一碼字。 5· —種裝置，其包含： 一資料源； '麵合至该資料源之碼產生？§ ’該碼産生器適於： 接收一具有一第二位元長度之資料字，其中該第二 位元長度小於該第一位元長度； O:\89\89442.DOC 200417156 使用若干個零填充該資料字，以將該資料字擴展至 該第一位元長度；及 使用一第一碼對該所填充資料字進行編瑪。 6·根據申請專利範圍第5項之裝置，其中該第一碼係一低 密度同位校驗（LDPC)碼。 7. 根據申請專利範圍第6項之裝置，其中該碼産生器進一 步適於： 確定一同位校驗矩陣；及 依據該同位校驗矩陣確定一産生器矩陣。 8. 一種用於在一通信系統中對傳輸進行解碼之方复 含： ’、匕 接收一用於對傳輸進行解碼之第一喝； 依據該第一碼確定一同位校驗矩陣，該第一碼具有 第一位元長度； 接收一第一碼字；及 使用該同位校驗矩陣對該第一碼字進行解碼。 9·根據申請專利範圍第8項之方 ” 〜 ，、甲忒弟一碼係一 松度同位校驗（LDPC)碼。 1〇·根據申請專利範圍第9項之方 一遲一步包含： 確定是否滿足一矩陣縮減準則，·及 若滿足該矩_減準則’則縮減該同位校驗矩陣之 τ 〇 η· 一種裝置，其包含： 一解碼器；及 O:\89\89442.DOC 一耦合至該解碼器之同位校驗單元，其適於： 接收一用於對傳輸進行解碼之第一碼； 依據該第-碼確^ _同位校驗矩陣，該第—碼 一第一位元長度； 、 接收一第一碼字；及 12. 13. 14. 15. 16. 17. 使用該同位校驗矩陣對該第一碼字進行解碼。 根據申請專利範圍第11項之裝置’其中該第-碼係 密度同位校驗（LDPC)碼。 - —種用於在一通信系統中對傳輸進行編碼之方法，其勺 含： ’、L 確定-用於將一資料字轉換爲一碼字之產生器矩陣； 確定一傳輸通道狀態何時高於一閾值；及 響應該傳輸通道狀態縮減該産生器矩陣之尺寸。 根據申請專利範圍第13項之方法，其進一步包含： 確定一同位校驗矩陣，其中該確定該產生器矩陣進— V包$ ·依據該同位校驗矩陣確定該產生器矩陣。 根據申請專利範圍第14項之方法，其中該同位校驗矩陣 包含一低密度同位校驗（LDPC)碼。 一種用於在一通信系統中對傳輸進行解碼之方法，其包 含·· 確定一同位校驗矩陣； 接收一具有一相應第一位元長度之第一碼字；及 響應該第一碼字縮減該同位校驗矩陣之尺寸。 一種用於在一通信系統中對傳輸進行編碼之方法，其包 O:\89\89442.DOC 產生-包含複數個子碼之母碼； 接收—具有-第-位元長度之資料字； 依據該第一位元長度選擇該複數個子碼之及 使用該所選擇子碼對該資料字進行編碼。 •根據申請專利範圍第丨 逮m。 法，其中產生該母碼包1 建立產生器矩陣，及 19祀據申子馬白與該産生器矩陣之—部分相關聯。 y.根據申凊專利範圍第18 ..Α 、心万/去其中選擇包括識別 益矩陣中與每-子碼相關聯之-部分。 2〇.根據申請專利範圍第18項之方法，其進_步包含： 産生該産生器矩陣作爲—同位校驗矩陣之—函數。 21·根據申請專利範圍第2。項之方法，其中產 矩陣包含： 産生複數個對應於該等子瑪之子矩陣。 22. 根據申請專利範圍第2〇項之方法，其進一步包含： 產生複數個對應於該等子碼之産生器子矩陣作爲該 同位校驗矩陣之一函數；及 使用該産生器子矩陣更新該産生器矩陣。 23. —種用於資料進行編碼之方法，其包含·· 産生一具有一輸入塊長度之産生器矩陣； 接收一具有一第一長度之資料字； 當該第一長度小於該輸入塊長度時，使用若干零填充 該資料字； O:\89\89442.DOC -4- 200417156 24 25. 26. 27. 28. 若滿足一産生器矩陣縮減準則，則縮減該産生器矩陣 之尺寸。 將該資料字應用於該尺寸縮減的産生器矩陣。 .根據申請專利範圍第23項之方法，其中該縮減準則係一 通道品質準則。 根據申請專利範圍第23項之方法，其中該產生器矩陣包 括同位校驗行1其中縮減該產生器矩陣包含至 該等同位校驗行之一部分。 # 一種用於對資料進行解碼之方法，其包含： 産生一具有-輸入塊長度之同位校驗矩陣； 接收一具有一第一長度之碼字； “第-長度大於或等於該輸入塊長度時，廢棄該 位校驗矩陣中至少一部分列； 若滿足一同位校驗矩陣縮減準則，則縮減 矩陣之尺寸； 狱 將該碼字應用於該同位校驗矩陣。 根據申請專利範圍第26項 , 、之方法，其中該矩陣縮減準則 係一通道品質準則。 一種用於在一通信系統中對值 一· 了得輸進仃編碼之裝置，其包 含· 一構件，其用於確定一具有一 知一“ 碼； 有位疋長度之第一 一構件，其用於接收-具有—第二μ長度之資 子’其中该第二位元長度小 料 於該第一位元長度； O:\89\89442.DOC 200417156 構件’其諸使㈣第-碼對該所填 一構件，其用於接收一 編石馬 29· —種用於在一通信系統中 含： 碼； 充資料字進行 對傳輸進行解碼之裝置，其包 用於對傳輸進行解碼之第一 ρ 一構件，其用於依據該第-碼確定-同位校驗矩陣， σ亥第一碼具有一第一位元長度； 一構件，其用於接收一第一碼字；及 / -構件，其用於使㈣同位校驗矩陣對該第—碼字進 行解碼。 編碼之裝置，其包 3〇· —種用於在一通信系統對傳輸進行 含·· 一構件’其用於確定一用於腺 ?. 用於將一貢料字轉換爲一碼字 之產生器矩陣； 一構件，其用於確定一傳輪诵省仙At y 士一 寻卿通道狀怨何時高於一閾 值；及 -構件’其用於響應該傳輸通道狀態來縮減該產生器 矩陣之尺寸。 3 1 · 一種用於在一通信系統中對傳給推— τ 1寻韻，】進仃解碼之裝置，其包 含·· 一構件，其用於確定一同位校驗矩陣； O:\89\89442.DOC /1^6 一構件，其用於接收一呈古 ，、有一相應第一位元長度之第 碼子；及 構件，其用於響應該第 陣之尺寸 碼字來縮減該同位校驗矩 32. 一種用於在一通信系統中 含： 對傳輪進行編碼之裝置， 其包 一構件，其用於產生_ 一構件，其用於接收— 字； 包含複數個子碼之母碼； 具有一第一位元長度之資料 m其㈣位元長度選擇該複數個子 —;及 構件#用於使用該所選擇子碼對該資料字進行編 O:\89\89442.DOC