<4D F736F F D20B373CEEBB5BEAABABDD7A4E55FADD7A5BF5F2E646F63>

Transcription

1 國 立 交 通 大 學 電 機 與 控 制 工 程 學 系 碩 士 論 文 以 優 先 權 為 基 礎 之 消 去 迴 圈 演 算 法 建 構 低 密 度 同 位 元 檢 查 碼 Constructing Low-Density Parity-Check Codes by Priority Based Cycle Elimination Algorithm 研 究 生 : 連 昶 翔 指 導 教 授 : 董 蘭 榮 博 士 中 華 民 國 九 十 八 年 十 月

2 以 優 先 權 為 基 礎 之 消 去 迴 圈 演 算 法 建 構 低 密 度 同 位 元 檢 查 碼 Constructing Low-Density Parity-Check Codes by Priority Based Cycle Elimination Algorithm 研 究 生 : 連 昶 翔 指 導 教 授 : 董 蘭 榮 博 士 Student:Chang-Hsiang Lien Advisor:Lan-Rong Dung 國 立 交 通 大 學 電 機 與 控 制 工 程 學 系 碩 士 論 文 A Thesis Submitted to Department of Electrical and Control Engineering College of Electrical Engineering and Computer Science National Chaio-Tung University in Partial Fulfillment of the Requirements for the Degree of Master in Electrical and Control Engineering October 2009 Hsinchu, Taiwan, Republic of China 中 華 民 國 九 十 八 年 十 月 i

3 以 優 先 權 為 基 礎 之 消 去 迴 圈 演 算 法 建 構 低 密 度 同 位 元 檢 查 碼 研 究 生 : 連 昶 翔 指 導 教 授 : 董 蘭 榮 博 士 國 立 交 通 大 學 電 機 與 控 制 工 程 學 系 中 文 摘 要 低 密 度 同 位 元 檢 查 碼 具 有 優 異 的 解 碼 能 力 及 硬 體 實 現 的 低 複 雜 度, 近 年 來 受 到 廣 大 討 論 與 研 究, 其 中 一 部 分 研 究 為 設 計 具 有 較 大 周 長 或 是 消 除 更 多 的 短 迴 圈 的 同 位 檢 查 矩 陣 以 得 到 更 好 的 解 碼 效 能 本 論 文 提 出 以 優 先 權 為 基 礎 的 消 去 迴 圈 演 算 法, 統 計 每 個 元 素 包 含 的 迴 圈 數 量 高 低 排 列 優 先 順 序, 如 此 可 有 效 率 打 斷 迴 圈 的 連 結, 故 本 改 良 式 演 算 法 能 大 幅 降 低 建 構 矩 陣 的 運 算 量 此 外 設 計 低 編 碼 長 度 的 位 元 檢 查 矩 陣 時 因 為 優 先 權 的 機 制 能 更 有 效 率 打 斷 迴 圈, 因 此 相 較 其 它 兩 者 類 似 架 構 的 演 算 法 能 消 除 更 多 的 迴 圈, 得 到 效 能 上 的 增 進, 尤 其 是 在 較 高 訊 號 雜 訊 比 的 情 況 下 差 異 較 為 明 顯, 適 用 於 低 功 耗 或 低 運 算 量 等 通 訊 系 統 ii

4 Constructing Low-Density Parity-Check Codes by Priority Based Cycle Elimination Algorithm Student:Lien Chang-Hsiang Advisor:Lan-Rong Dung Institute of Electrical and Control Engineering National Chiao-Tung University Abstract In recent years, Low-Density Parity-Check Codes have attracted a lot of attention and discussion due to great decoding ability and low complexity of hardware implementation. Some research focuses on performance improvement by designing high performance coding with large girth. In this thesis, we propose a priority based cycle elimination algorithm. It is efficient to eliminate cycle by setting the priority based on the number of dependent cycles. As shown in the results, the proposed algorithm can significantly reduce the complexity in operation. It can also construct high-performance codes and eliminate more cycles than traditional approaches for short code-length applications. Comparing with the other algorithms, the proposed algorithm can have better decoding performance, especially in high SNR environment; hence, our algorithm can satisfy the requirement of low-power communication systems. iii

5 誌 謝 這 篇 論 文 的 完 成 要 感 謝 許 多 人, 首 先 感 謝 老 師 兩 年 多 來 的 細 心 指 導 與 督 促, 讓 我 確 定 研 究 的 方 向, 多 方 面 意 見 的 交 流 使 我 改 進 不 足 的 地 方, 給 我 許 多 寶 貴 的 意 見 而 能 繼 續 研 究 下 去 再 來 感 謝 實 驗 室 的 夥 伴, 謝 謝 學 弟 們 幫 忙 我 許 多 事 情, 使 我 更 能 專 心 的 研 究 省 去 一 些 生 活 上 的 不 便, 謝 謝 致 翰 嘉 鴻 以 及 智 勝, 在 課 業 及 生 活 中 給 予 我 許 多 的 幫 助, 並 留 下 許 多 美 好 的 回 憶 最 後 我 要 感 謝 我 的 家 人, 一 直 在 背 後 照 顧 栽 培 我 的 父 親 與 母 親 以 及 可 愛 的 弟 弟, 感 謝 你 們 一 路 支 持 我 使 我 無 後 顧 之 憂 專 心 完 成 學 業, 在 此 獻 上 最 深 的 敬 意 與 感 謝 98 年 10 月 iv

6 目 錄 中 文 摘 要...ii Abstract...iii 誌 謝...iv 第 一 章 導 論 研 究 背 景 與 動 機 論 文 組 織...3 第 二 章 低 密 度 同 位 檢 查 碼 低 密 度 同 位 檢 查 碼 簡 介 基 本 概 念 及 特 性 介 紹 Gallager Codes Mackay Codes LDPC 編 碼 方 式 介 紹 傳 統 編 碼 方 式 Richardson 編 碼 演 算 法 LDPC 解 碼 方 式 介 紹 Sum-Product Algorithm Min-Sum Algorithm Min-Sum Correction-Factor...18 第 三 章 傳 統 消 去 迴 圈 演 算 法 (Cycle Elimination) 基 本 矩 陣 與 擴 展 形 成 迴 圈 之 條 件 與 限 制 傳 統 消 去 迴 圈 演 算 法 演 算 法 流 程...26 v

7 3.3-2 演 算 法 分 析 與 比 較...27 第 四 章 改 良 式 消 去 迴 圈 演 算 法 搜 尋 迴 圈 與 演 算 法 流 程 搜 尋 迴 圈 方 法 演 算 法 流 程 與 架 構 模 擬 結 果 與 分 析 適 用 於 低 編 碼 長 度 之 說 明 與 效 能 模 擬 解 碼 長 度 與 遞 迴 次 數 之 間 的 影 響 周 長 與 短 迴 圈 對 解 碼 效 能 之 模 擬 傳 統 與 改 良 式 演 算 法 在 低 編 碼 長 度 之 模 擬 比 較...44 第 五 章 結 論...50 參 考 文 獻...51 vi

8 圖 目 錄 圖 2-1 (7,3,3) 正 規 檢 查 矩 陣...5 圖 2-2 (7,3,3) 正 規 檢 查 矩 陣 之 Tanner Graph...5 圖 2-3 Gallager LDPC Codes H1 的 區 塊 矩 陣...7 圖 2-4 H 矩 陣 的 下 三 角 矩 陣 格 式...9 圖 2-5 Richardson 定 義 之 矩 陣 格 式...9 圖 2-6 式 2-13 之 Tanner Graph...12 圖 3-1 Cycle 表 示 方 法...20 圖 3-2 擴 展 矩 陣 示 意 圖...21 圖 3-3 擴 展 矩 陣 之 後 迴 圈 情 況...22 圖 3-4 計 算 位 移 量 的 方 向 示 意 圖...23 圖 3-5 方 塊 矩 陣 之 元 素 坐 標 ( 節 錄 自 [20] Fig.5)...25 圖 3-6 各 方 塊 矩 陣 迴 圈 連 結 示 意 圖 ( 節 錄 自 [20] Fig.6)...25 圖 3-7 傳 統 消 去 迴 圈 演 算 法 位 移 動 作 之 圖 例...26 圖 4-1 搜 尋 時 之 方 向 示 意 圖...30 圖 4-2 搜 尋 迴 圈 示 意 圖...31 圖 4-3 造 成 同 一 點 搜 尋 兩 次 之 範 例...32 圖 4-4 搜 尋 時 路 徑 超 過 原 點 左 半 邊 之 範 例...32 圖 4-5 若 A B 共 點 則 C D 共 點 將 無 法 找 到 搜 尋 路 徑 之 圖 例...36 圖 4-6 原 點 被 搜 尋 到 兩 次 之 範 例...36 圖 4-7 表 單 處 理 constraint 動 向 之 示 意 圖...37 圖 4-8 Code Rate=1/2 Irregular Matrix...38 圖 4-9 每 次 執 行 位 移 動 作 後 所 有 元 素 最 大 迴 圈 值 之 長 條 圖...39 圖 4-10 每 次 執 行 位 移 動 作 後 所 有 剩 餘 迴 圈 平 均 值 之 長 條 圖...40 vii

9 圖 4-11 不 同 編 碼 長 度 下 遞 迴 次 數 對 解 碼 效 能 的 影 響...43 圖 4-12 不 同 周 長 的 位 元 檢 查 矩 陣 對 解 碼 效 能 的 影 響...44 圖 4-13 不 同 擴 展 倍 數 下 所 剩 餘 迴 圈 總 量...46 圖 4-14 PCE 與 CE 演 算 法 編 碼 長 度 為 360 之 效 能 圖...46 圖 4-15 PCE 與 CE 演 算 法 編 碼 長 度 為 720 之 效 能 圖...47 圖 4-16 不 同 擴 展 倍 數 下 所 剩 餘 迴 圈 總 量...48 圖 4-17 PCE 與 CE 演 算 法 編 碼 長 度 為 1800 之 效 能 圖...48 圖 4-18 PCE 與 CE 演 算 法 編 碼 長 度 為 1800 之 效 能 圖...49 圖 4-19 PCE 與 CE 演 算 法 編 碼 長 度 為 3600 之 效 能 圖...49 viii

10 表 目 錄 表 2-1 p 1 複 雜 度 分 析...11 表 2-2 p 2 複 雜 度 分 析...11 表 3-1 估 計 運 算 的 constraint 總 量...27 表 3-2 每 條 constraint 的 加 減 法 總 量...28 表 4-1 每 個 元 素 為 1 之 陣 列...30 表 4-2 非 正 規 基 本 矩 陣 各 種 參 數...38 表 4-3 Code Rate=1/2 矩 陣 中 各 種 迴 圈 總 數 與 平 均...39 表 4-4 兩 種 演 算 法 之 比 較 列 表...41 表 4-5 兩 種 演 算 法 之 乘 法 數 與 加 法 數...41 表 4-6 本 演 算 法 在 1 分 佈 密 集 區 域 執 行 後 剩 餘 的 迴 圈 數 量...42 ix

11 第 一 章 導 論 節 內 容 本 章 節 介 紹 論 文 主 題 之 相 關 背 景 及 研 究 的 動 機, 並 在 論 文 組 織 中 簡 述 各 章 1.1 研 究 背 景 與 動 機 在 通 訊 技 術 日 益 進 步 的 現 代, 人 們 越 來 越 倚 靠 通 訊 所 帶 給 人 類 的 便 利 性 無 論 是 最 近 熱 門 的 無 線 網 路 系 統 WI-FI WiMAX 新 一 代 手 機 通 訊 系 統 等 技 術 的 發 展 一 日 千 里, 因 為 這 部 分 擁 有 廣 大 的 商 機 及 市 場, 眾 多 研 究 機 構 及 廠 商 投 資 大 量 人 力 及 金 錢 進 行 研 發 工 作, 而 隨 著 傳 輸 速 度 增 加 及 通 訊 品 質 的 要 求, 尤 其 對 於 高 速 無 線 系 統 來 說 環 境 所 造 成 雜 訊 干 擾 甚 大, 有 時 還 會 受 到 頻 率 範 圍 的 限 制 對 整 體 通 訊 品 質 受 到 影 響, 因 此 大 家 都 專 注 在 如 何 讓 無 線 傳 輸 的 品 質 變 好, 主 要 的 解 決 辦 法 就 是 使 用 錯 誤 更 正 碼 提 升 傳 輸 效 率 及 錯 誤 更 正 能 力 在 傳 輸 系 統 中 資 料 傳 輸 速 度 有 其 上 限 值 稱 為 通 道 容 量, 只 要 傳 輸 的 訊 號 強 度 及 速 度 不 超 過 此 值 均 可 以 使 用 適 當 的 編 解 碼 達 到 良 好 的 錯 誤 更 正 能 力 1948 年 夏 農 (Shannon) 發 表 重 要 的 通 道 理 論 [1], 在 傳 輸 過 程 中 如 果 速 率 小 於 通 道 容 量, 就 可 以 達 到 很 小 的 錯 誤 率, 雖 然 未 指 出 哪 種 編 碼 方 式 的 效 能 可 以 達 到 很 小 的 錯 誤 率, 但 此 理 論 成 為 指 標 也 發 展 了 許 多 的 編 碼 方 式 [2], 這 些 編 碼 主 要 分 成 兩 大 類, 一 類 為 線 性 區 塊 碼 [3](Linear Block Codes) 另 一 類 為 迴 旋 碼 [4] (Convolutional Code), 線 性 區 塊 碼 目 前 較 為 熱 門 有 循 環 碼 [5](Cyclic Codes) 里 德 - 所 羅 門 碼 [6](Reed-Solomon Codes) 低 密 度 同 位 檢 查 碼 (Low-Density Parity-Check Codes)[7], 而 迴 旋 碼 中 熱 門 有 渦 輪 碼 [8](Turbo Codes), 其 中 又 以 低 密 度 同 位 檢 查 碼 跟 渦 輪 碼 最 受 重 視 低 密 度 同 位 檢 查 碼 簡 稱 LDPC Codes 早 在 1962 年 就 由 Gallager 提 出, 當 時 因 為 電 腦 與 超 大 型 積 體 電 路 不 發 達, 因 此 無 1

12 法 負 擔 複 雜 運 算 量 高 的 LDPC Codes, 直 到 近 年 來 電 腦 運 算 發 達 的 現 代 才 逐 漸 被 重 視, 並 發 現 他 擁 有 優 異 的 錯 誤 更 正 能 力 [9][10], 開 始 有 許 多 人 踏 入 研 究 LDPC Codes 的 領 域 LDPC Codes 解 碼 方 式 類 似 Turbo Codes, 以 重 覆 遞 迴 更 新 每 一 位 元 的 機 率 資 訊 來 找 出 最 正 確 的 codes, 具 有 高 錯 誤 更 正 率 硬 體 實 現 度 高 且 可 平 行 化 Low error-floor 等 特 性, 同 時 LDPC 屬 於 線 性 區 塊 碼, 一 次 能 處 理 幾 千 甚 至 上 萬 個 位 元 數, 再 利 用 解 碼 平 行 化 的 實 現 [11], 所 以 能 達 到 很 高 的 吞 吐 量 [12], 但 缺 點 為 編 碼 的 複 雜 度 高, 現 在 有 幾 篇 已 發 表 的 論 文 如 [13] 使 編 碼 的 複 雜 度 變 低, 加 速 編 碼 的 速 度 構 成 一 個 好 的 LDPC 有 兩 條 重 要 的 因 素, 一 為 矩 陣 中 元 素 1 的 分 佈 [14], 另 一 為 短 迴 圈 (short cycle) 的 影 響, 因 為 LDPC 解 碼 方 式 為 重 覆 遞 迴 去 逼 近 於 正 確 的 碼 字, 解 碼 的 過 程 與 訊 息 傳 遞 之 間 的 獨 立 性 有 很 大 的 關 係, 在 已 有 的 文 獻 指 出 LDPC 要 有 良 好 的 更 正 能 力 必 須 讓 訊 息 傳 送 盡 可 能 的 獨 立 不 受 干 擾, 所 以 研 究 為 如 何 設 計 一 個 具 有 高 周 長 (Girth) 的 位 元 檢 查 矩 陣 為 本 論 文 研 究 的 動 機 之 一, 另 外 BLOCK-LDPC 的 架 構 在 硬 體 實 現 上 較 為 容 易 且 能 平 行 化 增 加 產 出, 結 合 這 兩 項 因 素 形 成 消 去 迴 圈 演 算 法 的 主 要 理 論 與 架 構 本 篇 論 文 主 要 探 討 建 構 LDPC Codes 的 演 算 法 設 計, 改 良 原 有 消 去 迴 圈 演 算 法 (Cycle Elimination Algorithm), 由 於 CE 演 算 法 本 身 為 近 似 暴 力 法 的 方 式 實 現, 故 運 算 量 及 複 雜 度 高, 且 演 算 法 運 作 特 性 使 然 在 低 擴 展 倍 數 下 打 斷 迴 圈 的 效 果 有 限, 因 此 我 們 提 出 以 CE 演 算 法 為 基 礎 加 入 優 先 權 的 概 念 而 改 良 的 演 算 法, 找 尋 該 元 素 擁 有 最 大 關 聯 性 也 就 是 包 含 最 多 迴 圈 優 先 動 作, 如 此 可 在 每 次 動 作 時 有 效 率 的 打 斷 更 多 迴 圈, 不 僅 大 量 減 低 演 算 法 的 運 算 複 雜 度, 在 設 計 低 編 碼 長 度 小 於 4000 位 元 的 矩 陣 能 消 除 更 多 的 短 迴 圈 進 而 增 加 解 碼 效 能, 模 擬 結 果 也 顯 示 相 較 於 其 它 兩 種 演 算 法 效 能 上 的 改 進, 所 以 適 用 於 行 動 或 無 線 通 訊 系 統 為 了 低 運 算 量 及 省 電 而 採 取 低 編 碼 長 度 的 解 碼 應 用 2

13 1.2 論 文 組 織 本 篇 論 文 將 以 下 的 章 節 劃 分 為 五 個 章 節, 茲 分 述 如 下 : 第 一 章 簡 述 錯 誤 更 正 碼 的 發 展, 說 明 LDPC 碼 的 特 性 與 研 究 背 景, 最 後 提 出 本 論 文 的 動 機 與 方 向 第 二 章 則 介 紹 本 論 文 之 背 景 知 識 作, 內 容 共 分 為 三 個 部 份 第 一 節 介 紹 LDPC 的 基 本 原 理 與 特 性 ; 第 二 節 介 紹 LDPC 的 兩 種 編 法 方 式, 一 種 為 傳 統 式 編 碼, 複 雜 度 會 隨 著 矩 陣 大 小 而 有 明 顯 的 改 變, 另 一 種 為 低 運 算 量 的 編 碼 方 式, 尤 其 針 對 長 矩 陣 的 編 碼 能 有 效 減 低 運 算 複 雜 度 第 三 章 介 紹 傳 統 式 消 去 迴 圈 演 算 法, 除 了 說 明 演 算 法 流 程 之 外, 並 分 析 演 算 法 的 運 算 複 雜 度 與 優 缺 點 第 四 章 介 紹 改 良 式 消 去 迴 圈 演 算 法, 詳 盡 說 明 演 算 法 的 步 驟 與 要 點, 此 外 以 兩 個 範 例 矩 陣 證 明 具 有 快 速 消 除 迴 圈 的 效 果, 也 簡 化 大 量 的 運 算 複 雜 度, 最 後 提 出 以 較 小 的 編 碼 長 度 的 解 碼 效 能 略 優 於 傳 統 式 的 消 去 迴 圈 演 算 法 第 五 章 為 結 論 與 未 來 研 究 方 向 之 提 議 3

14 第 二 章 低 密 度 同 位 檢 查 碼 本 章 將 介 紹 LDPC 碼 的 基 本 概 念, 包 含 了 LDPC 的 特 性 建 構 同 位 檢 查 矩 陣 的 種 類 以 及 編 碼 解 碼 的 方 式 2.1 低 密 度 同 位 檢 查 碼 簡 介 構 此 節 敘 述 LDPC 基 本 概 念 及 特 性, 並 介 紹 最 早 所 提 出 的 Gallager Codes 架 基 本 概 念 及 特 性 介 紹 低 密 度 同 位 檢 查 碼 (LDPC Codes) 是 一 種 線 性 區 塊 碼, 因 此 在 編 碼 及 解 碼 時 會 將 一 連 串 的 來 源 訊 息 分 段 處 理, 每 一 段 的 位 元 長 度 為 K 編 碼 時 將 此 K bits 與 生 成 矩 陣 G K N 位 元, 我 們 可 以 表 示 為 : 相 乘 後 得 到 長 度 為 K+M 的 碼 字 (Code word), 其 中 M bit 為 檢 查 v s G = (1) 1 N 1 K K N 編 碼 後 的 資 料 v 經 由 通 道 傳 輸 到 接 收 端, 再 利 用 同 位 檢 查 矩 陣 H (Parity-Check matrix) 檢 查 收 到 的 碼 是 否 正 確 並 加 以 修 正 H 矩 陣 分 成 正 規 矩 陣 與 非 正 規 矩 陣 (regular codes), 所 謂 正 規 矩 陣 指 H 矩 陣 中 每 一 行 及 每 一 列 中 1 的 個 數 相 同, 若 一 個 m x n 大 小 H 矩 陣 中 每 列 含 有 k 個 1 每 行 含 有 j 個 1 則 定 義 為 (n,j,k)-regular LDPC Codes, 其 中 j k 稱 為 行 權 重 (column weight) 及 列 權 重 (row weight), 並 不 是 每 個 H 矩 陣 都 有 相 同 的 權 重, 而 這 些 矩 陣 為 非 正 規 矩 陣 (irregular codes) 為 了 方 便 我 們 了 解 LDPC 運 作 的 情 形,Tanner[15] 提 出 了 Tanner Graph 也 稱 為 Bipartite Graph, 以 圖 2-1 的 (7,3,3) 正 規 檢 查 矩 陣 為 例, 它 的 Tanner 4

15 Graph 表 示 為 圖 2-2, 每 一 列 均 可 用 一 個 節 點 代 表 稱 做 檢 查 節 點 (check node), 每 一 行 均 可 用 一 個 節 點 代 表 稱 做 位 元 節 點 (check node), 而 檢 查 節 點 與 位 元 節 點 中 間 的 連 線 稱 做 edge, 這 些 edge 將 各 節 點 的 訊 息 互 相 傳 輸 H = M N 圖 2-1 (7,3,3) 正 規 檢 查 矩 陣 C1 C2 C3 C4 C5 C6 C7 Check nodes Edge V1 V2 V3 V4 V5 V6 V7 Bit nodes 圖 2-2 (7,3,3) 正 規 檢 查 矩 陣 之 Tanner Graph 迴 圈 (Cycle) 指 從 一 個 節 點 出 發, 經 過 幾 條 edge 之 後 再 回 到 同 一 個 節 點, 而 這 個 路 徑 是 封 閉 的 且 同 一 節 點 不 能 通 過 兩 次 以 上, 如 圖 2-2 中 虛 線 所 示, 從 V1 節 點 出 發 經 由 edge 通 過 C1 V2 C2 V3 C7 共 六 點 及 六 條 edge 回 到 C1, 這 是 一 條 封 閉 的 Cycle 且 因 為 通 過 六 個 點 我 們 稱 為 Cycle-6, 一 個 矩 陣 所 有 的 Cycle 中 最 小 Cycle length 稱 作 Girth 5

16 LDPC 的 同 位 檢 查 矩 陣 除 了 影 響 編 碼 的 複 雜 度 之 外, 對 解 碼 效 能 的 影 響 更 是 巨 大, 所 以 我 們 一 般 說 建 構 LDPC Codes 就 是 指 設 計 它 的 H 矩 陣 通 常 H 矩 陣 設 計 上 有 兩 個 重 點, 一 為 矩 陣 的 大 小, 因 為 矩 陣 的 大 小 行 數 等 於 Code length, 在 Gallager[7] 文 獻 中 提 到, 一 個 亂 數 產 生 的 (n,j,k) 矩 陣 最 小 距 離 (minimum distance) d min Nσ ( j, k) 其 中 σ ( j, k) >0, 所 以 當 code length N 越 長 時 最 小 距 離 也 跟 著 變 大, 也 就 是 有 較 好 的 效 能 ; 另 一 為 Cycle length 的 大 小,Tanner 在 [14] 文 獻 中 指 出, 如 果 LDPC Codes 有 越 大 的 Girth 時 代 表 解 碼 時 能 有 更 多 獨 立 的 遞 迴 運 算 使 錯 誤 更 正 能 力 增 加 因 此 H 矩 陣 中 短 Cycle 是 盡 量 避 免 的, 這 部 分 也 是 本 論 文 的 重 點, 利 用 改 良 的 演 算 法 使 短 Cycle 消 除 Gallager Codes 前 文 曾 提 到 LDPC Codes 共 分 為 regular 及 irregular 兩 種,Gallager LDPC 則 是 屬 於 regular 隨 機 分 配 的 矩 陣, 具 有 以 下 定 義 及 特 性 一 個 (n,j,k)-regular 的 矩 陣 含 有 nj / k 個 列, 矩 陣 大 小 為 M x N, 而 它 的 檢 查 位 元 (parity bit) 長 度 為 k=m-n, 此 矩 陣 的 排 列 架 構 如 式 (2) 表 示 : H H1 H 2 = H j (2) 對 於 每 一 個 子 矩 陣 H, i = 1,2,..., j 大 小 為 p x (p x k) 列 權 重 為 k 及 行 i 權 重 為 1 第 一 個 子 矩 陣 H 1 的 分 佈 似 階 梯 狀, 如 圖 2-3 所 示 在 第 一 列 中 有 連 續 3 個 1 排 列, 因 此 1 的 排 列 範 圍 為 ( i 1) k + 1 to ik, for i = 1,2,..., p, 此 處 k=3, 其 它 部 分 的 子 矩 陣 是 配 合 第 一 列 所 做 的 隨 機 排 列 矩 陣 6

17 H = 圖 2-3 Gallager LDPC Codes H1 的 區 塊 矩 陣 Mackay Codes [16] Mackay 提 出 一 個 隨 機 產 生 位 元 檢 查 矩 陣 的 方 法, 建 構 矩 陣 時 為 一 行 一 行 疊 上 去, 如 第 一 行 元 素 1 的 位 置 是 隨 機 的, 但 第 二 行 開 始 元 素 1 的 位 置 不 能 與 第 一 行 相 同 以 免 造 成 cycle-4 的 迴 圈 產 生, 而 之 後 的 行 數 每 疊 上 去 都 會 檢 查 之 前 行 數 1 的 位 置 避 免 在 同 一 列, 因 此 所 建 構 而 成 的 矩 陣 完 全 沒 有 cycle-4 的 迴 圈 存 在, 可 在 解 碼 時 增 加 錯 誤 更 正 能 力 以 提 升 效 能 2.2 LDPC 編 碼 方 式 介 紹 LDPC 為 線 性 區 塊 碼, 因 此 可 利 用 高 斯 消 去 法 產 生 G, 但 因 為 此 種 方 式 隨 著 code length 增 加 而 需 要 大 量 的 運 算 及 複 雜 度, 所 以 部 分 研 究 針 對 LDPC 編 碼 提 出 有 效 率 的 編 碼 方 法, 以 下 的 內 容 也 會 一 併 介 紹 傳 統 編 碼 方 式 令 原 始 訊 息 為 u= [ u0, u1,..., uk 1], 經 由 生 成 矩 陣 G 得 到 碼 字 c= [ c0, c1,..., cn 1], 可 表 示 為 : c=u.g (3) 7

18 其 中 G 的 大 小 為 k x n 因 為 H 矩 陣 與 G 矩 陣 維 度 互 相 正 交 使 相 乘 之 後 為 零, 故 T H 的 大 小 為 (n-k) x n, 所 以 可 由 以 下 公 式 推 導 出 c H = 0 T G H = 0 T ug H = 0 ( u 0) (4) T c H = 0 如 果 H 矩 陣 為 列 滿 秩 則 由 高 斯 消 去 法 得 到 H H = I P (5) M N sys ( M N) N ( M N) N T 其 中 I 為 單 位 矩 陣, 因 為 G H = 0, 故 G sys T H = 0 sys I ( M N) N Gsys 0 T = P ( M N) N G P I T sys = ( M N ) N ( M N ) N (6) 在 剛 剛 的 高 斯 消 去 法 中 得 到 矩 陣 不 一 定 是 標 準 的 [ I P ] 格 式, 還 需 要 經 過 行 與 行 之 間 的 置 換, 所 以 產 生 的 G sys G 轉 換 成 正 確 的 G 也 要 重 做 行 之 間 的 置 換 Richardson 編 碼 演 算 法 [13] H 矩 陣 經 高 斯 消 去 法 可 得 到 如 圖 2-4 的 矩 陣 分 配, 但 不 是 任 意 矩 陣 均 可 由 高 斯 消 去 法 加 上 行 轉 換 形 成 此 種 矩 陣, 因 此 Richardson 提 出 一 種 有 效 率 的 編 碼 適 用 於 任 何 矩 陣, 且 減 少 矩 陣 運 算 的 複 雜 度 及 運 算 量 8

19 n-m m m n 圖 2-4 H 矩 陣 的 下 三 角 矩 陣 格 式 首 先 將 H 矩 陣 經 過 行 與 列 的 排 列 之 後 形 成 圖 2-5 的 形 式, 此 形 式 表 示 為 H A B T = C D E (7) n-m g m-g m A B T C D E m-g g n 圖 2-5 Richardson 定 義 之 矩 陣 格 式 矩 陣 中 各 子 矩 陣 的 大 小 上 圖 所 標 示, 其 中 T 為 下 三 角 矩 陣, 將 此 矩 陣 的 左 邊 乘 以 下 述 的 子 矩 陣 9

20 I 0 A B T 1 ET I C D E (8) 得 到 A B T 1 1 ET A + C ET B + D 0 (9) 令 編 碼 完 的 碼 字 分 成 三 部 分 c= (, s p1, p2),s 為 長 度 (m-n) 資 訊 位 元 T p1 及 p2 分 別 為 長 度 g 與 (m-g) 的 檢 查 位 元, 因 為 c H = 0, 所 以 將 c 與 式 (9) 相 乘 得 到 兩 條 式 子 T T T As + Bp1 + Tp2 = = 1 T 1 T ( ET A C) s ( ET B D) p1 0 (10) 設 1 r ET B D = + 為 非 奇 異 矩 陣 可 逆, 代 入 式 (10) 運 算 得 p = r ET A+ C s (11) T 1 1 T 1 ( ) T p 1 得 到 後 再 代 回 式 (10) 得 p = T ( As + Bp ) (12) T 1 T T 2 1 有 了 p1, p 2就 可 代 回 原 來 分 段 的 碼 字 中 得 到 c, 即 為 編 碼 後 的 結 果, 整 體 的 運 算 複 雜 度 列 於 表 2-1 與 表 2-2 算 式 內 容 複 雜 度 T As 1 T T [ As ] ET As 1 T [ ] 稀 疏 矩 陣 相 乘 T 1 [ As ] = y [ As ] = Ty T T T T 稀 疏 矩 陣 相 乘 On ( ) On ( ) On ( ) 10

21 T Cs T ET As +[ Cs ] 1 T [ ] 1 1 T T r ET As Cs [ + ] 稀 疏 矩 陣 相 乘 相 加 密 集 矩 陣 相 乘 On ( ) On ( ) 2 Og ( ) 表 2-1 p 1 複 雜 度 分 析 算 式 內 容 複 雜 度 T As T Bp 1 T T [ As ]+[ Bp 1 ] [ + ] 1 T T T As Bp1 稀 疏 矩 陣 相 乘 稀 疏 矩 陣 相 乘 相 加 + = + = 1 T T T T T T T [ As Bp1 ] y [ As Bp1 ] Ty On ( ) On ( ) On ( ) On ( ) 表 2-2 p 2 複 雜 度 分 析 2.3 LDPC 解 碼 方 式 介 紹 LDPC 的 解 碼 方 式 採 用 遞 迴 運 算 (Iterative Decoding), 利 用 多 次 重 覆 傳 送 位 元 節 點 與 檢 查 節 點 之 間 的 訊 息 使 解 碼 結 果 逼 近 原 始 資 料, 通 常 遞 迴 的 次 數 越 多 則 解 碼 值 越 正 確, 此 外 為 了 方 便 硬 體 實 現 及 簡 化 運 算 複 雜 度, 解 碼 時 大 多 採 用 LLR 的 形 式 [17] 本 節 將 介 紹 常 用 的 三 種 解 碼 演 算 法, 這 些 演 算 法 均 屬 於 軟 性 決 策 (Soft decision) 解 碼 而 有 優 秀 的 錯 誤 更 正 能 力 11

22 2.3-1 Sum-Product Algorithm [18] Tanner Graph 的 圖 形 解 碼 使 我 們 容 易 了 解 LDPC 解 碼 的 過 程, 在 說 明 整 體 演 算 法 流 程 之 前, 先 舉 簡 單 的 例 子 表 達 訊 息 傳 遞 及 推 導 機 率 公 式 的 過 程, 其 中 部 分 過 程 參 考 [19] 這 邊 有 一 個 2x4 的 位 元 檢 查 矩 陣 : H = (13) 設 收 到 的 碼 字 code word 為 c=(c1,c2,c3,c4), 要 判 斷 是 否 為 正 確 的 碼 字 則 使 之 與 位 元 檢 查 矩 陣 相 乘 得 到 T c H = (1, c c2, c3, c4) = c1 c4 = 0 ( equation S1) c1 c2 c3 = 0 ( equation S2) (14) 其 中 符 號 代 表 modulo-2 加 法 運 算, 所 得 到 的 兩 條 方 程 式 稱 為 位 元 檢 查 方 程 式 (parity check equation), 而 方 程 式 的 數 量 與 列 的 數 量 相 同 位 元 檢 查 矩 陣 由 Tanner Graph 表 示 如 下 S1 S2 Check nodes c1 c2 c3 c4 Bit nodes 圖 2-6 式 2-13 之 Tanner Graph 12

23 S1 跟 S2 分 別 代 表 兩 條 位 元 檢 查 方 程 式,c1~c4 代 表 code word 中 4 個 位 元 的 點, 首 先 我 們 對 c1 做 單 一 位 元 的 解 碼 : 位 元 c4 的 priori-probability 為 0 與 1 的 機 率 是 p0 與 p1, 其 中 p0+p1=0 因 為 透 過 S1 的 傳 遞 給 c1 訊 息 的 位 元 節 點 有 c4, 所 以 經 由 S1 方 程 式 c1 c4= 0 可 以 得 到 S1 c1 c4 (p0,p1) Pc ( 1 = 0) = Pc ( 4 = 0) = p Pc (1= 1) = Pc (4= 1) = p1 0 (15) 同 理 透 過 S2 的 位 元 節 點 有 c3 c4, 經 由 S2 方 程 式 c1 c2 c3= 0 得 到 S2 c1 c3 c4 (q0,q1) (r0,r1) Pc (1= 0) = Pc (2 c3= 0) = Pc ( 2 = 0) Pc ( 3 = 0) + Pc ( 2 = 1) Pc ( 3 = 1) = qr qr 1 1 Pc (1= 1) = Pc (2 c3= 1) = Pc ( 2= 1) Pc ( 3= 0) + Pc ( 2= 0) Pc ( 3= 1) = qr 10+ qr 01 (16) 因 為 S1 及 S2 都 有 傳 遞 機 率 訊 息 給 c1, 因 此 c1 要 整 合 這 兩 組 資 訊, 我 們 由 式 (17) 表 示 : 13

24 p, p S1) ( S 0 S1 S2 c1 ( S 0 q, q S1 ) Pc ( 1= 0) PS ( 1= 0 andc1= 0) PS ( 1= 0 andc1= 0) = p q Pc (1= 1) PS ( 1= 0 andc1= 1) PS ( 1= 0 andc1= 1) = p q S0 S0 S1 S1 (17) 其 中 ps0 = p0, ps1 = p1, qs0 = q0r0 + qr 1 1 and qs1 = qr q0r1 以 S2 檢 查 節 點 來 看, 它 要 整 合 c3 及 c4 的 機 率 資 訊, 所 以 我 用 下 式 代 表 c1 得 到 的 機 率 : ps2( q, q, r, r) = ( qr + qr, qr + qr) (18) 因 為 任 一 點 0 與 1 的 機 率 總 合 為 1 也 就 是 p0 p1 1 LLR(Log-Likelihood Ratio) 的 型 式 + =, 為 了 簡 化 運 算 採 用 L p p = = λ (19) 0 ( 0, p1) ln ln p1 代 入 式 (18) 得 qr qr 0 0+ qr 1 1 qr 11 ps2( L1, L2) = ps2( L1 L2) = ln = ln qr r 10+ qr 01 0 q0 + r q

25 L + L L + L L1 L2 2 2 e e e e 1+ λλ 1+ + = = = e + e L1+ L2 L1 L2 = ln(cosh( )) ln(cosh( )) L1 L2 = 2 tanh (tanh( ) tanh( )) ln ln ln L1 L2 L L L L λ1+ λ2 e + e (20) 式 (20) 可 轉 成 另 一 種 型 式 L L ps L L 2 2 = sign( L ) sign( L ) φφ ( ( L ) + φ( L )) ( 1, 2) = 2 tanh (tanh( ) tanh( )) (21) 其 中 x x e + 1 φ( x) = ln tanh( ) = ln and φ( φ( x))= x x 2 e 1 (22) 以 上 為 S2 檢 查 節 點 搜 集 其 它 位 元 節 點 的 資 訊, 經 由 數 學 運 算 統 計 機 率 後 再 傳 給 該 解 碼 的 位 元 節 點, 然 而 S1 與 S2 都 有 連 線 至 c1, 因 此 c1 會 收 到 這 兩 個 檢 查 節 點 的 訊 息, 與 (18) 類 似 的 概 念 得 到 下 式 p q pc1( ps0, ps1, qs0, qs1), p q S0 S0 S1 S1 = ps0qs0 + ps1qs1 ps0qs0 + ps1qs1 (23) 將 式 (19) 代 入 pc1( L, L ) = ln( λ λ ) = lnλ + lnλ = L + L (24) 故 將 兩 個 檢 查 節 點 的 機 率 值 相 加 即 是 綜 合 S1 S2 的 機 率 式 (21) 與 式 (24) 均 為 統 計 運 算 兩 個 節 點 的 機 率 值, 將 此 兩 個 公 式 擴 展 成 整 合 多 數 節 點 的 機 率 值, 由 式 (20) 擴 展 得 到 15

26 ps( L L L ) 1 2 = ps( ps( ps( ps( L L ) L ) ) L ) i i= 1 i= = sign( L1) sign( L2) sign( Ln) φφ ( ( L1 ) + + φ( Ln )) (25) n = sign( L ) φφ ( ( L )) n n n n 此 為 檢 查 節 點 從 n 個 位 元 節 點 統 計 的 機 率 值, 接 著 要 統 計 多 個 檢 查 節 點 至 單 一 位 元 節 點 的 機 率 值, 由 式 (24) 擴 展 得 到 pc( L, L,, L ) = ln( λ λ λ ) 1 2 n 1 2 = ln λ + ln λ + + ln λ = L + L + + L n n (26) 此 為 位 元 節 點 從 n 個 檢 查 節 點 統 計 的 機 率 值, 有 了 上 述 的 概 念 之 後, 接 下 來 介 紹 Sum-Product Algorithm 的 解 碼 流 程, 以 編 號 作 為 演 算 法 之 順 序 (1) 初 始 化 (Initialization) 設 L n P( yn xn = 0) 2 = ln = ( 1) 2 P y x = σ n n y n (27) 其 中 P(a b) 表 示 b 位 元 從 傳 送 端 出 發 在 接 收 端 收 到 a 位 元 時 為 0 與 1 的 機 率, 2 σ 代 表 雜 訊 參 數, 所 以 接 收 到 的 codeword 每 個 位 元 機 率 可 表 示 為 1 ~ L L n 當 H 矩 陣 中 H mn, = 1時 設 q, mn = L, 即 對 應 矩 陣 中 元 素 為 1 的 機 率 值 n (2) 計 算 位 元 節 點 至 檢 查 節 點 的 機 率 資 訊 每 個 檢 查 節 點 均 會 收 到 所 連 結 位 元 節 點 的 機 率 資 訊, 設 這 些 機 率 值 為 q mn,, 但 因 為 統 計 這 些 機 率 不 包 括 本 身 的 機 率, 所 以 表 示 為 16

27 r ps = ( q ) mn, mn, ' n' L( m)\ n (28) = sign( q ) sign( q ) φφ ( ( q ) φ( q )) mn, mn, ' mn, ' mn, n' L( m) n' L( m) x x e + 1 where φ( x) = ln tanh( ) = ln and φ( φ( x))= x x 2 e 1 (3) 計 算 檢 查 節 點 至 位 元 節 點 的 機 率 資 訊 每 個 位 元 節 點 接 收 來 自 所 連 結 檢 查 節 點 的 機 率 資 訊 q = pc( pc ( r ), L ) = L + r (29) mn, m', n n n m', n m' M( n)\ m m' M( n)\ m (4) 計 算 位 元 節 點 本 身 的 機 率 資 訊 與 解 碼 q = pc( pc ( r ), L ) = L + r (30) n m, n n n m, n m M( n) m M( n)\ m 得 到 的 q 進 行 判 斷 : c n n 1 if qn 0 = 0 if qn < 0 (5) 重 複 遞 迴 運 算 T 如 果 解 出 來 的 codeword 滿 足 c H = 0 則 解 碼 結 束, 否 則 重 覆 從 步 驟 (2) 開 始 直 到 解 出 正 確 的 碼 或 達 到 遞 迴 次 數 的 上 限 值 17

28 2.3-2 Min-Sum Algorithm 由 式 (20) 可 改 寫 成 ps2( L, L ) = ps2( L L ) L + L L L = ln(cosh( )) ln(cosh( )) L + L L L 1+ e ln e = + L + L 1 2 L L 1 2 = sign L sign L L L + ( 1) ( 2) min( 1, 2 ) ln 1 sign( L ) sign( L ) min( L, L ) e + e L + L 1 2 L L 1 2 (31) 此 式 將 複 雜 的 運 算 式 φ 簡 化 成 最 小 值 運 算, 雖 然 有 效 降 低 運 算 量 但 也 失 去 部 份 的 效 能, 因 為 φ ( x) 中 x 值 越 小 時 φ 值 越 大, 若 同 時 有 4 個 最 小 值 大 小 排 列 為 x4>x3>x2>x1, 則 算 式 只 會 選 擇 x1 卻 失 去 x2 x3 x4 帶 來 效 能 偏 差, 所 以 通 常 Min-Sum Algorithm 與 Sum-Product Algorithm 在 code length 越 長 時 效 能 影 響 越 大 Min-Sum Correction-Factor [20] 為 了 改 善 Min-Sum Algorithm 的 效 能 損 失, 在 式 (31) 中 省 略 的 部 分 1+ e 1 2 L1+ L2 L1 L2 ln = ln(1 + e ) ln(1 + e ) L1 L2 1+ e L + L (32) 此 參 數 稱 為 Correction-Factor, 可 經 由 查 表 法 LUT 算 出 加 入 此 項 參 數 後 能 修 正 數 值, 使 解 碼 效 能 更 接 近 Sum-Product Algorithm Min-Sum Algorithm 的 解 碼 流 程 如 下 : 18

29 (1) 初 始 化 (Initialization) 設 L n P( yn xn = 0) 2 = ln = ( 1) 2 P y x = σ n n y n (33) (2) 計 算 位 元 節 點 至 檢 查 節 點 的 機 率 資 訊 r ps = ( q ) mn, mn, ' n' L( m)\ n min = sign( q ) sign( q ) { q } mn, mn, ' mn, n' L( m) n' L( m) (34) (3) 計 算 檢 查 節 點 至 位 元 節 點 的 機 率 資 訊 q = pc( pc ( r ), L ) = L + r (35) mn, m', n n n m', n m' M( n)\ m m' M( n)\ m (4) 計 算 位 元 節 點 本 身 的 機 率 資 訊 與 解 碼 q = pc( pc ( r ), L ) = L + r (30) n m, n n n m, n m M( n) m M( n)\ m 得 到 的 q 進 行 判 斷 : c n n 1 if qn 0 = 0 if qn < 0 (5) 重 複 遞 迴 運 算 T 如 果 解 出 來 的 codeword 滿 足 c H = 0 則 解 碼 結 束, 否 則 重 覆 從 步 驟 (2) 開 始 直 到 解 出 正 確 的 碼 或 達 到 遞 迴 次 數 的 上 限 值 19

30 第 三 章 傳 統 消 去 迴 圈 演 算 法 (Cycle Elimination) 一 般 來 說 SPA 演 算 法 具 有 優 異 的 解 碼 能 力, 在 解 碼 的 過 程 中 因 為 訊 息 經 由 edge 互 相 傳 遞 而 造 成 訊 息 的 相 依 關 係, 再 加 上 LDPC 解 碼 屬 於 遞 迴 式 的 演 算 法, 希 望 訊 息 傳 遞 時 盡 可 能 的 獨 立, 如 果 在 位 元 檢 查 矩 陣 中 含 有 許 多 短 迴 圈 (cycle) 會 使 得 收 斂 速 度 變 慢 且 解 碼 效 能 變 低, 因 此 設 計 具 有 長 迴 圈 架 構 的 位 元 檢 查 矩 陣 能 使 訊 息 之 間 相 依 關 係 減 低 進 而 獲 得 效 能 提 升 此 章 將 介 紹 傳 統 消 去 迴 圈 演 算 法 (Cycle Elimination) [21], 採 用 搜 尋 短 迴 圈 並 打 斷 迴 圈 的 機 制 產 生 矩 陣, 並 同 時 擴 展 每 個 元 素 形 成 Block-LDPC 矩 陣 格 式 有 利 於 VLSI 硬 體 上 編 碼 與 解 碼 的 實 現 [22][23] Cycle-4 Cycle 圖 3-1 Cycle 表 示 方 法 3.1 基 本 矩 陣 與 擴 展 矩 陣 中 最 小 的 cycle 定 義 為 Girth, 一 般 而 言 當 Girth=8 以 上 有 較 好 的 解 碼 效 能, 也 就 是 矩 陣 中 不 會 形 成 如 圖 3-1 所 示 cycle-4 或 6 目 前 有 幾 種 演 算 法 能 增 加 矩 陣 中 Girth 長 度, 如 Progressive Edge-Growth(PEG)[24] Bit-Filling [25] 等 演 算 法, 但 產 生 的 矩 陣 中 非 零 的 元 素 亂 數 排 列, 對 實 現 硬 體 上 較 為 困 難 複 雜 度 也 相 對 增 加 20

31 為 了 利 於 硬 體 實 現 並 採 用 平 行 化 的 概 念 以 達 到 高 吞 吐 的 輸 出, 產 生 位 元 檢 查 矩 陣 時 採 用 Block-LDPC[26] 架 構, 如 圖 3-2 所 示 先 準 備 Ms x Mn 大 小 的 基 本 矩 陣 (Base matrix), 再 按 照 code length 所 需 的 大 小 展 開 成 p.ms x p.mn, 其 中 每 個 0 展 開 為 p x p 大 小 的 零 矩 陣, 每 個 1 展 開 為 p x p 大 小 的 單 位 矩 陣 擴 展 基 本 矩 陣 除 了 對 硬 體 實 現 有 好 處 外, 同 時 也 能 對 效 能 有 所 助 益, 因 為 擴 展 後 的 矩 陣 Girth 一 定 大 於 或 等 於 基 本 矩 陣 的 Girth, 此 特 性 也 是 支 持 消 去 迴 圈 演 算 法 的 主 要 理 論, 經 由 擴 展 的 過 程 中 位 移 單 位 矩 陣 達 到 打 斷 Cycle 的 效 果 Ms x Mn T T 0 0 T 0 T 0 0 T T p.ms x p.mn 圖 3-2 擴 展 矩 陣 示 意 圖 3.2 形 成 迴 圈 之 條 件 與 限 制 由 上 一 節 得 知 用 位 移 單 位 矩 陣 打 斷 短 迴 圈, 而 形 成 迴 圈 中 每 一 個 元 素 位 移 情 況 以 圖 3-3 舉 例 說 明 21

32 (1,1) (1,2) (2,1) (2,2) 圖 3-3 擴 展 矩 陣 之 後 迴 圈 情 況 以 圖 3-3 為 例, 將 基 本 矩 陣 中 每 個 元 素 擴 展 成 4 x 4 的 小 區 塊 矩 陣, 每 個 區 塊 都 是 單 位 矩 陣 位 移 之 後 形 成 的,P 為 向 右 位 移 量, 故 P(1,1)=1 P(1,2)=0 P(2,1)=3 P(2,2)=2, 得 到 上 圖 形 成 4 條 長 度 為 4 的 迴 圈, 此 種 迴 圈 通 稱 為 cycle-4, 同 理 長 度 為 六 的 迴 圈 通 稱 為 cycle-6 以 此 類 推, 而 任 何 矩 陣 中 最 小 的 迴 圈 為 cycle-4, 為 了 探 討 各 元 素 位 移 量 與 形 成 迴 圈 之 間 的 關 係, 用 數 學 公 式 來 推 導 證 明 如 下 將 同 一 行 中 兩 個 元 素 歸 類 一 組, 如 P(1,1) 和 P(2,1) 為 一 組 P(1,2) 和 P(2,2) 為 一 組, 在 [27] 中 定 義 : Δ P = P P (31) i, j > i, m i, j i, m, 則 Δ P1,1 > 2,1 = P1,1 P2,1 = 3 1= 2 (32) Δ P2,2 > 1,2 = P2,2 P1,2 = 0 2= 2 (33) 22

33 , 最 後 把 式 (32) 和 式 (33) 相 加 得 到 ( Δ P ) = P 1,2 P 2,2 = (2) + ( 2) = 0 V (34), 式 3-5 中 的 V 代 表 vertical shift-value drops 上 述 是 以 cycle length=4 為 例, Δ P 相 減 的 順 序 如 圖 3-4 所 示, 從 左 上 方 的 元 素 點 出 發 順 時 鐘 或 逆 時 鐘 繞 回 原 點, 保 持 方 向 一 致 性, 不 管 是 Cycle 都 相 同 P(1,1)=1 2 P(1,2)=0-2 P(1,1)=0 2 P(1,2)=3-1 P(2,2)=4 P(2,3)=3 P(1,1)=3 P(2,2)=2-1 P(3,1)=2 P(3,3)=4 圖 3-4 計 算 位 移 量 的 方 向 示 意 圖 因 此 我 們 可 以 直 接 用 數 學 計 算 位 移 量 和 形 成 迴 圈 之 間 的 關 係 首 先 如 圖 3-5 所 示 把 展 開 之 後 的 方 塊 矩 陣 切 成 兩 部 份, 每 一 個 1 的 坐 標 都 可 表 示 為 下 式 : ( ii, + P 0 // L), 當 0 i< L P ( 左 上 方 ) ( ii, + P L), 當 L P i L 1 ( 右 下 方 ) (35), 將 式 (35) 合 併 成 (, ii+ P 0// L) (36) 23

34 , 對 應 圖 3-6 中 表 示 為 ( s, s + P 0// L) (37) i i i,1, 又 得 知 H(1,2) 與 H(2,1) 有 相 同 的 行,H(1,1) 與 H(g,2) 有 相 同 的 行, 以 此 類 推 得 到 下 列 的 式 子 : s + P (0// L) = s + P (0// L) 1 1,2 2 2,1 s + P (0// L) = s + P (0// L) 2 2,2 3 3,1 s + P (0// L) = s + P (0// L) g g,2 1 1,1 (38), 將 上 式 加 總 得 到 ( P P ) + ( P P ) + + ( P P ) = ( y x)( L) (39) 1,2 2,1 2,2 3,1 g,2 1,1, 整 理 得 ( Δ P ) = k L ( k = 0, ± 1, ± 2,, ± g ) V (40) 上 式 為 判 斷 位 移 量 與 迴 圈 的 準 則 稱 做 Cycle constraint, 其 中 g 值 為 cycle 長 度 的 一 半, 例 如 cycle length=6 則 g=3 等 式 成 立 的 話 則 會 形 成 迴 圈, 因 此 以 下 的 內 容 若 稱 滿 足 constraint 則 表 示 等 式 不 成 立, 不 滿 足 constraint 則 表 示 等 式 成 立 24

35 圖 3-5 方 塊 矩 陣 之 元 素 坐 標 ( 節 錄 自 [21] Fig.5) 圖 3-6 各 方 塊 矩 陣 迴 圈 連 結 示 意 圖 ( 節 錄 自 [21] Fig.6) 25

36 3.3 傳 統 消 去 迴 圈 演 算 法 這 裡 以 條 列 式 介 紹 傳 統 的 消 去 迴 圈 演 算 法, 並 分 析 該 演 算 法 之 優 缺 點 及 改 進 的 目 標, 並 在 下 一 章 描 述 改 良 的 演 算 法 演 算 法 流 程 首 先 準 備 好 基 本 矩 陣, 矩 陣 中 每 個 1 含 有 一 個 清 單, 清 單 是 用 來 儲 存 式 (40) 的 constraint, 用 來 判 斷 是 否 有 打 斷 或 重 新 回 復 Cycle 接 著 開 始 搜 尋 Cycle length 為 之 迴 圈, 從 最 左 邊 的 行 (column) 開 始 往 右 搜 尋, 並 將 每 一 個 找 到 的 迴 圈 記 錄 在 清 單 中 以 便 之 後 拿 來 判 斷 使 用, 以 程 式 模 擬 結 果 得 知 Cycle length 越 大 其 個 數 增 加 的 越 快 當 找 出 任 何 迴 圈 時, 開 始 對 此 迴 圈 中 每 個 1 做 constraint 的 判 斷 以 打 斷 迴 圈, 因 為 擴 展 成 L X L 的 區 塊 矩 陣 中 位 移 量 限 制 為 [0, L-1], 為 了 使 位 移 增 加 的 速 度 減 緩, 先 將 每 個 1 的 初 始 位 移 值 儲 存, 每 個 1 檢 查 自 己 的 constraint 是 否 符 合, 若 不 符 合 則 位 移 值 加 1 ( P, = P, + 1) 直 到 滿 足 所 有 constraint, 找 出 i j i j 此 迴 圈 中 位 移 總 合 最 小 的 1 保 留 此 值, 其 它 的 1 回 存 原 值 以 圖 3-7 為 例,P 代 表 總 位 移 值 括 弧 內 代 表 此 迴 圈 檢 查 constraint 所 增 加 的 值, 選 擇 最 小 的 總 位 移 量 (36) 並 回 存 其 它 值 P=72(4) 68 P=36(9) P=56(1) P=45(5) P=50(2) 48 P=60(0) 60 圖 3-7 傳 統 消 去 迴 圈 演 算 法 位 移 動 作 之 圖 例 26

37 3.3-2 演 算 法 分 析 與 比 較 傳 統 消 去 迴 圈 演 算 法 是 找 到 一 個 迴 圈 就 會 進 行 位 移 的 動 作, 以 消 去 目 前 找 到 的 迴 圈 再 進 行 下 一 個 迴 圈 消 除, 此 種 作 法 類 似 暴 力 法, 將 所 有 的 迴 圈 跑 過 一 遍 並 檢 查 迴 圈 中 每 個 元 素 的 constraint, 再 做 比 較 位 移 最 小 值 的 工 作, 因 此 運 算 量 非 常 可 觀, 下 表 為 模 擬 圖 4-8 的 矩 陣 的 結 果 Cycle-4 Cycle-6 Cycle-8 執 行 迴 圈 總 量 平 均 單 一 迴 圈 檢 查 constraint 數 量 總 合 表 3-1 估 計 運 算 的 constraint 總 量 表 3-1 為 code rate=1/2 18 x 36 非 正 規 基 本 矩 陣, 其 中 包 含 117 個 1 該 演 算 法 從 最 左 邊 的 行 (column) 開 始 往 右 動 作, 可 避 免 重 覆 的 迴 圈 運 算, 由 上 表 觀 察 出 cycle 8 數 量 比 cycle 4 6 高 出 許 多, 且 因 為 每 執 行 一 次 消 去 迴 圈 位 移 的 動 作, 就 必 須 把 迴 圈 中 每 個 元 素 1 的 constraint 都 計 算 過 一 遍, 所 以 增 加 不 少 運 算 量 例 如 cycle-6 就 要 檢 查 6 個 點, 相 對 增 加 6 倍 constraint 的 運 算, 故 在 cycle-8 中 平 均 每 cycle 需 檢 查 3253 個 constraint 表 3-2 分 別 列 出 在 cycle 中 每 個 constraint 乘 法 與 加 法 的 總 數, 若 分 別 乘 上 表 3-1 constraint 的 數 量 即 為 整 體 演 算 法 的 運 算 量, 因 此 如 果 把 constraint 定 在 cycle-8 將 會 耗 費 相 當 多 的 運 算 雖 然 傳 統 消 去 迴 圈 演 算 法 的 計 算 方 式 需 要 大 量 運 算 量 及 時 間, 但 是 位 移 打 斷 迴 圈 的 效 果 全 面 且 仔 細 27

38 Cycle-4 Cycle-6 Cycle-8 加 法 數 乘 法 數 表 3-2 每 條 constraint 的 加 減 法 總 量 28

39 第 四 章 改 良 式 消 去 迴 圈 演 算 法 本 章 節 將 介 紹 改 良 式 演 算 法, 根 據 元 素 包 含 的 迴 圈 數 高 低 取 得 優 先 次 序, 執 行 位 移 打 斷 迴 圈 的 動 作, 並 充 分 利 用 每 次 能 打 斷 Cycle 的 機 會 我 將 以 不 同 的 基 本 矩 陣 做 說 明, 除 了 大 幅 改 善 位 移 消 去 之 運 算 量 及 時 間, 在 低 擴 展 倍 數 時 也 能 有 效 的 將 迴 圈 數 量 減 到 最 低 4.1 搜 尋 迴 圈 與 演 算 法 流 程 此 節 介 紹 搜 尋 迴 圈 的 方 式, 詳 細 說 明 改 良 式 消 去 迴 圈 演 算 法 的 流 程 與 架 構, 並 在 下 一 節 分 析 演 算 法 的 模 擬 結 果 搜 尋 迴 圈 方 法 首 先 準 備 基 本 矩 陣, 先 找 出 所 有 元 素 1 儲 存 各 種 資 訊 於 陣 列 中, 如 表 4-1 這 些 包 含 上 下 左 右 1 的 個 數 坐 標 及 位 移 資 訊, 而 演 算 法 中 不 管 是 搜 尋 迴 圈 或 是 權 重 機 制 都 是 從 左 上 方 的 點 開 始 往 右 搜 尋 到 底 後 換 列, 如 圖 4-1 所 示, 直 到 所 有 的 點 都 被 搜 尋 過, 如 此 一 來 保 持 演 算 法 執 行 的 方 向 統 一 避 免 重 覆, 以 下 用 條 列 式 的 方 式 介 紹 搜 尋 方 法 與 順 序, 並 以 圖 4-2 輔 助 說 明 29

40 (x,y) 坐 標 上 端 個 數. 坐 標 下 端 個 數. 坐 標 左 端 個 數. 坐 標 右 端 個 數. 坐 標 Cycle 個 數. 坐 標 位 移 量 位 移 旗 標 表 4-1 每 個 元 素 為 1 之 陣 列 圖 4-1 搜 尋 時 之 方 向 示 意 圖 1. 從 左 上 方 的 原 點 P(1,1) 出 發, 往 右 及 往 下 搜 尋 找 到 P(1,2) 及 P(4,1) 並 標 記 為 第 一 層, 其 中 P(1,2) 與 原 點 有 相 同 的 列 數 P(4,1) 與 原 點 有 相 同 的 行 數 2. 從 P(1,2) 往 上 或 下 搜 尋 得 到 P(2,2), 而 P(4,1) 往 右 搜 尋 得 到 P(4,4), 將 P(2,2) 及 P(4,4) 標 記 為 第 二 層, 其 中 P(1,2) 與 P(2,2) 有 相 同 的 行 數 P(4,1) 與 P(4,4) 有 相 同 的 列 數 3. 從 P(2,2) 往 右 或 左 搜 尋 得 到 P(2,3), 而 P(4,4) 往 上 或 往 下 搜 尋 得 到 P(3,4), 將 P(2,3) 及 P(3,4) 標 記 為 第 三 層, 其 中 P(2,2) 與 P(2,3) 有 相 同 的 列 數 P(3,4) 與 P(4,4) 有 相 同 的 行 數 4. 最 後 搜 尋 全 部 的 點, 若 有 一 點 P(X,Y) 與 P(1,2) 有 相 同 的 行 數 並 且 與 P(4,1) 有 相 同 的 列 數 則 形 成 Cycle-4; 若 有 一 點 P(X,Y) 與 P(2,2) 有 相 同 的 列 數 並 30

41 且 與 P(4,4) 有 相 同 的 行 數 則 形 成 Cycle-6; 若 有 一 點 P(X,Y) 與 P(2,3) 有 相 同 的 行 數 並 且 與 P(3,4) 有 相 同 的 列 數 則 形 成 Cycle-8 P(1,1) P(1,2) P(2,2) P(2,3) P(X,Y) P(3,4) P(4,1) P(4,4) 圖 4-2 搜 尋 迴 圈 示 意 圖 搜 尋 迴 圈 時 有 兩 點 需 要 特 別 注 意 : (1) 在 階 層 搜 尋 時, 必 須 避 免 不 同 階 層 搜 尋 到 相 同 的 點, 這 種 現 在 尤 其 在 cycle-8 時 更 容 易 發 生 如 圖 4-3 所 示, 空 心 的 點 為 原 點, 在 往 右 搜 尋 時 會 先 找 到 A 點, 而 同 樣 地 從 原 點 依 序 往 下 往 右 及 往 上 也 會 找 到 A 點, 造 成 同 一 點 搜 尋 兩 次 的 情 況, 因 此 在 搜 尋 過 程 中 設 定 所 有 點 的 坐 標 均 不 相 等 即 可 (2) 搜 尋 的 方 向 不 能 超 過 起 始 點 左 側 的 行 數, 如 圖 4-4 以 空 心 點 當 原 點 時, 搜 尋 到 第 三 層 也 就 是 虛 線 框 起 來 的 部 分, 這 兩 點 行 數 已 小 於 原 點 ; 而 以 B 點 當 原 點 搜 尋 時 也 會 搜 尋 到 一 樣 的 迴 圈, 造 成 同 一 個 迴 圈 被 搜 尋 至 兩 次, 所 以 要 以 原 點 的 行 數 做 標 準, 任 何 搜 尋 的 路 徑 只 能 在 原 點 的 右 半 側 31

42 A 圖 4-3 造 成 同 一 點 搜 尋 兩 次 之 範 例 此 行 數 為 基 準 時 已 搜 尋 過 B 圖 4-4 搜 尋 時 路 徑 超 過 原 點 左 半 邊 之 範 例 演 算 法 流 程 與 架 構 前 一 章 介 紹 了 傳 統 式 迴 圈 演 算 法, 雖 然 過 程 是 循 序 式 的 將 迴 圈 打 斷, 但 運 算 量 及 複 雜 度 很 高, 所 以 我 們 提 出 改 良 式 消 去 迴 圈 演 算 法, 除 了 有 效 打 斷 消 除 迴 圈 之 外, 依 照 每 一 點 包 含 迴 圈 的 數 量 訂 為 權 重 值, 按 權 重 高 低 消 去 迴 圈 以 簡 化 運 算 量 優 先 權 消 去 迴 圈 演 算 法 流 程 : 32

43 (1) 找 出 基 本 矩 陣 中 為 1 的 元 素, 並 創 造 一 個 空 陣 列 儲 存 各 種 資 訊 (2) 清 空 元 素 1 中 全 部 參 數 的 初 始 值 (3) 從 最 左 上 角 的 1 開 始, 找 出 所 有 1 的 (x,y) 坐 標 及 上 下 左 右 四 個 方 向 為 1 的 個 數 及 坐 標, 並 儲 存 在 陣 列 中 供 搜 尋 迴 圈 使 用 (4) // 搜 尋 Cycle-4 6 8, 同 時 將 每 條 迴 圈 的 坐 標 及 資 訊 存 入 陣 列 (5) 從 原 點 H(i,j) 往 右 往 下 找 到 兩 點 H(i,k) H(m,j), 若 有 一 點 坐 標 為 H(m,k) 則 此 4 點 形 成 cycle-4 (6) for H(i,k) 上 方 及 下 方 的 1 為 H(p,k) H(m,j) 右 方 的 1 為 H(m,n), 若 有 一 點 坐 標 為 H(p,n) 則 此 6 點 形 成 cycle-6 (7) for H(p,k) 右 方 及 左 方 的 1 為 H(p,r) H(m,n) 上 方 及 下 方 的 1 為 H(s,n), 若 有 一 點 坐 標 為 H(s,r) 則 此 8 點 形 成 cycle-8 (8) end (9) end (10) // 優 先 權 一 次 式 消 去 迴 圈 法 (11) while ( 元 素 1 最 大 迴 圈 數 >0) (12) if (( 某 一 點 元 素 迴 圈 數 == 最 大 迴 圈 數 )&&( 位 移 旗 標 ==0)) (13) for ( 該 元 素 所 有 可 位 移 的 值 P = (1~L-1) ) (14) 檢 查 該 元 素 包 含 的 constraint, 分 別 記 錄 滿 足 constraint 及 不 滿 足 的 數 量 ( 這 邊 定 義 參 數 為 rig 與 wro) (15) if (rig > wro) (16) 比 較 該 元 素 所 有 的 位 移 值 並 取 P 使 (rig-wro) 有 最 大 值 (17) else (18) 該 元 素 位 移 值 P=0 ; (19) end (20) 該 元 素 的 位 移 旗 標 設 為 1; 33

44 (21) 更 新 基 本 矩 陣 的 最 大 迴 圈 數 ; (22) elseif (( 某 一 點 元 素 迴 圈 數 == 最 大 迴 圈 數 )&&( 位 移 旗 標 ==1)) (23) 跳 過 並 尋 找 下 一 個 含 有 相 同 最 大 迴 圈 數 之 元 素 ; (24) else (25) 最 大 迴 圈 數 = 最 大 迴 圈 數 -1; (26) end (27) end (28) end 演 算 法 流 程 圖 : 附 註 : 準 備 基 本 矩 陣 1 s: 矩 陣 中 元 素 為 1 的 點 P: 元 素 1 的 位 移 值 rig: 滿 足 constraint 總 數 搜 尋 Cycle 與 記 錄 wro: 不 滿 足 constraint 總 數 迴 圈 最 大 值 >0 No 演 算 法 結 束 Yes 搜 尋 1 s 的 迴 圈 數 No 迴 圈 最 大 值 -1 No 是 否 最 大 值? Yes 位 移 旗 標 =0? Yes 代 入 P 檢 查 constraint 設 P=0 位 移 旗 標 =1 更 新 迴 圈 最 大 值 位 移 旗 標 =1 rig > wro Yes 取 P 使 (rig-wro) 有 最 大 值 No 34

45 演 算 法 分 段 以 行 數 說 明 與 分 析 如 下 : (1)~(3) 行 : 首 先 準 備 一 個 基 本 矩 陣, 所 有 在 矩 陣 中 的 1 均 產 生 如 表 4-1 的 清 單 並 將 初 始 值 歸 零 如 圖 4-1 從 矩 陣 的 左 上 角 開 始 搜 尋 1 的 位 置 記 錄 坐 標, 並 同 時 找 出 上 下 左 右 四 個 方 向 的 1, 將 其 坐 標 與 數 量 儲 存 因 為 每 個 元 素 包 含 許 多 cycle, 每 條 cycle 都 會 轉 成 constraint 存 於 清 單 (4)~(9) 行 : 每 一 點 包 含 4 個 方 向 的 資 訊, 我 們 利 用 此 資 訊 尋 找 迴 圈 在 節 說 明 了 搜 尋 方 法, 但 此 方 法 只 適 用 於 專 門 搜 尋 Cycle 的 情 況, cycle 的 基 本 定 義 為 從 原 點 出 發 繞 過 一 條 封 閉 的 路 徑 回 到 原 點, 且 每 一 個 節 點 不 能 通 過 第 2 次, 所 以 提 出 兩 點 方 法 避 免 找 到 錯 誤 或 重 覆 的 cycle 然 而 這 邊 所 搜 尋 是 未 擴 展 之 前 的 基 本 矩 陣, 經 由 模 擬 結 果 證 明 圖 4-3 的 情 形 在 擴 展 矩 陣 之 後 有 可 能 造 成 新 的 cycle-8, 如 果 我 未 考 慮 及 搜 尋 到 此 種 迴 圈, 即 便 程 式 結 果 指 出 已 打 斷 所 有 迴 圈, 新 的 擴 展 矩 陣 還 會 有 未 打 斷 的 cycle 產 生 為 了 使 程 式 能 完 全 打 斷 所 有 的 迴 圈, 提 出 兩 條 輔 助 方 法 : (1) 以 圖 4-5 當 作 範 例, 若 藍 色 AB 共 點 則 勢 必 造 成 紅 色 CD 共 點, 反 之 亦 然 ; 這 並 不 符 合 構 成 迴 圈 的 形 式, 因 為 當 搜 尋 至 A B 點 時 下 一 步 是 往 水 平 方 向 搜 尋 而 找 到 C D 點, 找 到 C D 點 後 下 一 步 往 垂 直 方 向 搜 尋, 若 C D 共 點 的 話 則 無 法 找 到 搜 尋 的 路 徑, 所 以 除 了 讓 A B 和 C D 不 共 點 之 外 取 消 其 它 避 免 共 點 的 限 制 (2) 在 [13] 文 獻 中 提 到 所 有 搜 尋 的 點 的 行 數 必 須 大 於 原 點 的 行 數 ( d > j ), 但 這 種 說 法 並 不 周 延, 我 的 模 擬 實 驗 出 現 了 一 種 情 況, 以 圖 4-6 所 示 藍 點 為 原 點, 各 點 的 數 字 指 移 位 量, 在 此 種 情 形 下 原 點 被 搜 尋 到 兩 次, 利 用 式 3-11 得 到 Δ P = 0 + (14) + (14) + ( 28) = 0, 代 表 在 擴 展 矩 陣 後 會 形 成 新 的 cycle-8, 並 不 符 合 作 者 演 算 法 中 的 描 述, 因 此 我 修 改 為 所 有 點 的 行 數 必 須 大 於 或 等 於 原 點 的 行 數 35

46 A C B D 圖 4-5 若 A B 共 點 則 C D 共 點 將 無 法 找 到 搜 尋 路 徑 之 圖 例 0 0 原 點 圖 4-6 原 點 被 搜 尋 到 兩 次 之 範 例 (10)~(28) 行 : 權 重 指 元 素 1 所 包 含 迴 圈 總 數, 這 也 是 本 演 算 法 主 要 的 精 神, 依 照 每 個 1 不 同 權 重 來 執 行 迴 圈 消 去 的 優 先 次 序 當 初 的 構 想 是 當 該 元 素 擁 有 最 高 權 重 時, 能 一 次 打 斷 迴 圈 的 數 量 必 會 高 於 其 它 元 素 首 先 找 出 具 有 最 高 權 重 的 元 素, 接 著 把 所 有 的 位 移 值 (1~L-1) 代 入 constraint 表, 統 計 各 別 滿 足 及 不 滿 足 constraint 的 總 數, 首 要 條 件 為 滿 足 的 總 量 必 須 大 於 不 滿 足 的 總 量, 再 來 選 擇 讓 兩 者 相 差 最 大 的 位 移 值, 也 就 是 該 位 移 值 能 打 斷 更 多 的 迴 圈 更 少 重 新 連 結 的 迴 圈, 充 份 利 用 每 一 次 打 斷 的 機 會 另 外 再 準 備 1 張 表 單, 把 滿 足 的 constraint 搬 到 此 表 單 不 滿 足 的 維 持 在 原 表 單, 如 圖 4-7 所 示 方 便 處 理 迴 圈 資 訊 與 數 量 若 滿 足 的 總 量 小 於 不 滿 足 的 總 量, 則 該 元 素 位 移 值 設 為 零, 繼 36

47 續 往 下 一 個 擁 有 高 優 先 權 的 元 素 動 作, 最 後 只 要 有 判 斷 執 行 該 元 素 時 均 拉 起 位 移 旗 標 表 示 已 處 理 過 每 執 行 完 一 次 位 移 動 作 時, 程 式 將 重 新 整 理 取 得 最 新 的 優 先 權 順 序, 再 執 行 位 移 動 作 盡 可 能 打 斷 所 有 的 迴 圈 因 為 整 體 演 算 法 執 行 到 最 後 才 會 將 基 本 矩 陣 擴 展, 不 可 能 每 次 統 計 最 新 優 先 權 時 執 行 搜 尋 迴 圈 的 動 作, 於 是 在 這 邊 使 用 一 個 技 巧, 直 接 讀 取 圖 4-7 中 未 被 打 斷 迴 圈 的 數 量, 就 可 快 速 且 精 準 地 得 到 各 元 素 所 剩 餘 的 迴 圈 數 Cycle_Information Delete_Information 滿 足 即 打 斷 Cycle 未 被 打 斷 的 Cycle 資 訊 及 數 量 已 被 打 斷 的 Cycle 資 訊 及 數 量 不 滿 足 即 回 復 Cycle 圖 4-7 表 單 處 理 constraint 動 向 之 示 意 圖 4.2 模 擬 結 果 與 分 析 以 下 將 以 非 正 規 矩 陣 (irregular matrix) 做 模 擬 與 分 析, 在 [29] [30] 提 出 設 計 良 好 的 非 規 則 矩 陣 解 碼 效 能 比 規 則 矩 陣 好, 而 規 則 矩 陣 的 好 處 為 簡 化 設 計 硬 體 的 複 雜 度, 不 過 隨 著 超 大 型 積 體 電 路 的 進 步, 現 在 的 應 用 大 多 採 用 非 規 則 矩 陣 以 達 到 更 好 的 效 能 模 擬 矩 陣 的 參 數 性 質 列 於 表 4-2, 採 用 [24] 文 獻 中 的 方 法 建 構 而 成 的 基 本 矩 陣, 此 矩 陣 與 表 3-1 所 做 分 析 模 擬 之 矩 陣 相 同, 因 此 稍 後 有 兩 種 演 算 法 模 擬 的 數 據 比 較 37

48 Code Rate 1/2 Variable node degree 2,3,7 Check node degree 5,6 Base matrix size 18x36 表 4-2 非 正 規 基 本 矩 陣 各 種 參 數 圖 4-8 為 code rate=1/2 之 非 規 則 矩 陣, 大 小 為 18x36, 位 元 節 點 的 權 重 分 別 為 { 2,2,,2,3,,3,7,,7 }, 矩 陣 中 共 有 117 個 1, 可 觀 察 出 矩 陣 的 右 半 段 1 的 分 佈 較 為 密 集, 表 示 這 些 點 含 有 大 量 的 迴 圈, 由 程 式 分 析 顯 示 每 一 個 元 素 1 含 有 cycle 平 均 值 達 到 1268 當 基 本 矩 陣 能 擴 展 的 倍 數 越 大, 即 代 表 有 更 多 的 位 移 值 選 擇 而 打 斷 更 多 的 迴 圈, 模 擬 顯 示 擴 展 倍 數 L 需 要 235 方 能 打 斷 所 有 迴 圈 圖 4-8 Code Rate=1/2 Irregular Matrix 38

49 迴 圈 類 型 Cycle-4 Cycle-6 Cycle-8 總 數 324 5, ,488 每 元 素 平 均 值 表 4-3 Code Rate=1/2 矩 陣 中 各 種 迴 圈 總 數 與 平 均 為 什 麼 優 先 權 的 機 制 能 更 有 效 率 打 斷 迴 圈? 因 為 當 一 個 元 素 為 1 的 點 具 有 最 高 迴 圈 數 量 時, 代 表 能 一 次 打 斷 迴 圈 的 數 量 越 多, 迴 圈 的 總 數 是 固 定 的, 如 果 能 在 每 次 位 移 動 作 時 能 打 斷 最 多 的 迴 圈, 不 僅 加 快 迴 圈 消 去 的 速 度, 也 能 減 少 執 行 元 素 位 移 動 作 的 次 數 圖 4-9 為 每 次 執 行 完 該 元 素 位 移 動 作 後, 所 有 元 素 之 最 大 迴 圈 值 的 數 據, 開 始 執 行 10 次 之 內 的 最 大 迴 圈 值 有 明 顯 減 少, 故 每 次 動 作 都 能 打 斷 最 多 的 迴 圈 數 量, 即 可 看 出 採 用 權 重 優 先 打 斷 迴 圈 的 方 法 收 到 良 好 的 成 效, 而 超 過 20 次 後 因 為 最 大 迴 圈 值 變 低 而 打 斷 的 迴 圈 數 量 有 限, 因 此 曲 線 較 為 平 緩, 總 共 花 費 53 次 執 行 遞 迴 次 數 將 所 有 Cycle 消 除 所 有 元 素 之 最 大 迴 圈 值 元 素 執 行 位 移 動 作 之 次 數 圖 4-9 每 次 執 行 位 移 動 作 後 所 有 元 素 最 大 迴 圈 值 之 長 條 圖 39

50 圖 4-10 為 每 次 執 行 位 移 動 作 後 每 個 元 素 的 迴 圈 平 均 值, 在 前 十 次 元 素 位 移 消 去 的 動 作 時, 所 有 剩 下 迴 圈 的 平 均 值 已 從 1268 降 至 361, 下 降 的 幅 度 達 71.5%, 再 次 證 明 以 優 先 權 打 斷 的 機 制 獲 得 了 成 效, 除 此 之 外 執 行 元 素 位 移 的 次 數 減 少 後, 運 算 量 相 對 減 低 許 多, 在 表 3-1 已 討 論 過 相 同 矩 陣 利 用 傳 統 迴 圈 消 去 演 算 法 所 花 費 的 運 算 量, 而 這 邊 也 將 確 切 的 運 算 量 列 於 表 4-4, 由 於 表 3-1 是 以 constraint 的 數 量 做 為 基 準, 而 搜 尋 迴 圈 的 方 法 差 不 多, 故 這 邊 也 是 以 constraint 的 數 量 當 作 比 較 的 單 位 原 作 者 的 演 算 法 每 遇 到 迴 圈 就 搜 尋 此 迴 圈 中 所 有 的 1 並 檢 查 constraint 以 減 低 快 速 增 加 的 位 移 量, 但 帶 來 了 大 量 的 運 算 量, 而 以 權 重 優 先 的 方 式 先 找 出 最 大 迴 圈 值 的 元 素 動 作, 僅 動 用 了 53 個 元 素 還 不 到 總 個 數 的 一 半 就 可 打 斷 所 有 的 迴 圈, 相 對 減 低 檢 查 constraint 的 數 量 達 到 72%, 若 再 乘 上 每 個 constraint 的 加 法 數 及 乘 法 數 將 會 更 可 觀, 結 果 列 於 表 4-5 另 外 也 將 電 腦 模 擬 時 間 列 於 表 4-4, 程 式 由 Matlab 撰 寫 實 現, 電 腦 主 機 為 Intel Core2-Quad Q6600, 擴 展 的 倍 數 為 235 倍 所 有 剩 餘 迴 圈 之 平 均 值 元 素 執 行 位 移 動 作 之 次 數 圖 4-10 每 次 執 行 位 移 動 作 後 所 有 剩 餘 迴 圈 平 均 值 之 長 條 圖 40

51 總 constraint 運 算 量 實 際 運 算 時 間 傳 統 式 76,050, 秒 改 良 式 21,328, 秒 改 進 比 例 (%) 72% 92% 表 4-4 兩 種 演 算 法 之 比 較 列 表 每 條 constraint 傳 統 式 改 良 式 加 法 數 532,068, ,297,148 乘 法 數 684,164, ,953,476 表 4-5 兩 種 演 算 法 之 乘 法 數 與 加 法 數 前 文 提 到 本 矩 陣 靠 近 右 側 具 有 較 密 集 的 1, 因 此 右 側 將 會 產 生 大 量 的 迴 圈, 如 果 當 基 本 矩 陣 的 擴 展 值 有 一 定 的 限 制 時, 以 原 作 者 的 演 算 法 一 定 從 最 左 側 的 行 開 始 消 去, 消 去 到 一 半 時 可 能 將 所 有 擴 展 值 的 選 擇 用 完, 反 而 最 需 要 打 斷 的 右 側 卻 無 法 進 行 打 斷 迴 圈 的 動 作, 所 以 原 作 者 的 演 算 法 遇 到 右 側 有 密 集 的 1 且 擴 展 範 圍 有 限 時 會 遇 到 這 方 面 的 問 題 反 觀 以 迴 圈 的 總 數 排 定 優 先 次 序, 對 於 越 密 集 的 1 所 形 成 的 迴 圈 優 先 打 斷, 整 體 效 果 會 更 好 表 4-6 為 隨 機 取 右 側 9 個 元 素 在 不 同 擴 展 倍 數 剩 餘 的 迴 圈 數 與 原 始 未 被 打 斷 的 數 據 比 較, 證 明 能 有 效 打 斷 這 些 迴 圈, 因 此 本 演 算 法 適 用 於 低 擴 展 倍 數, 也 就 是 編 碼 長 度 短 的 應 用, 將 在 下 一 節 說 明 與 分 析 坐 標 / 擴 展 倍 數 未 擴 展 50 倍 100 倍 150 倍 (2,32) 2, (2,33) 2, (4,33) 1,

52 (6,33) 1, (10,32) 1, (11,32) 1, (11,33) 1, (5,12) 2, (12,33) 2, 表 4-6 本 演 算 法 在 1 分 佈 密 集 區 域 執 行 後 剩 餘 的 迴 圈 數 量 4.3 適 用 於 低 編 碼 長 度 之 說 明 與 效 能 模 擬 解 碼 長 度 與 遞 迴 次 數 之 間 的 影 響 LDPC 為 遞 迴 式 (Iterative) 的 解 碼 機 制, 經 由 反 覆 傳 送 機 率 資 訊 將 收 到 的 碼 更 逼 近 於 正 確 的 碼, 然 而 遞 迴 的 次 數 與 解 碼 長 度 有 很 大 的 關 係 [30], 如 圖 4-12 所 示, 模 擬 通 道 為 AWGN, 使 用 的 解 碼 演 算 法 是 SPA,H 矩 陣 為 碼 率 1/2 的 非 正 規 矩 陣, 紅 色 實 線 與 藍 色 虛 線 分 別 代 表 Code length 為 7200bits 與 3600bits 在 長 度 7200 三 種 遞 迴 次 數 均 造 成 明 顯 的 效 能 差 異 ; 而 在 長 度 3600 遞 迴 次 數 為 30 與 50 的 效 能 差 異 減 低, 但 在 遞 迴 次 數 為 10 時 解 碼 效 能 很 差, 因 此 在 越 長 的 解 碼 長 度 時 除 了 帶 來 大 量 的 運 算, 也 需 要 更 多 的 遞 迴 次 數 達 到 解 碼 收 斂 的 效 果, 其 中 遞 迴 次 數 與 耗 電 量 成 正 比, 如 遞 迴 次 數 50 次 比 30 次 多 出 1.6 倍 的 耗 電 量, 因 此 改 良 式 消 去 迴 圈 演 算 法 應 用 於 低 編 碼 長 度 實 現 模 擬 與 分 析 為 主 要 目 標 42

53 1.0E E E-02 CL=7200,iter=50 CL=7200,iter=30 CL=7200,iter=10 CL=3600,iter=50 CL=3600,iter=30 CL=3600,iter=10 BER 1.0E E E E SNR 圖 4-11 不 同 編 碼 長 度 下 遞 迴 次 數 對 解 碼 效 能 的 影 響 周 長 與 短 迴 圈 對 解 碼 效 能 之 模 擬 在 PEG 演 算 法 [24] 文 獻 中 提 出 如 果 位 元 檢 查 矩 陣 具 有 較 多 的 長 迴 圈, 則 在 解 碼 時 能 使 每 次 遞 迴 動 作 之 間 更 為 獨 立 以 減 低 錯 誤 率 ; 另 外 在 [25] 文 獻 中 提 出 短 迴 圈 數 量 越 少 則 有 較 好 的 錯 誤 更 正 能 力 ; 還 有 在 [31] 文 獻 中 指 出 如 果 在 Tanner Graph 出 現 太 多 短 迴 圈 則 使 MPA 解 碼 的 效 能 變 差 因 此 這 邊 利 用 改 良 式 消 去 迴 圈 演 算 法 產 生 三 種 不 同 周 長 (Girth) 矩 陣, 模 擬 結 果 比 較 於 下 圖 43

54 1.0E E-01 CL=5400,Girth=10 CL=5400,Girth=8 CL=5400,Girth=6 1.0E-02 BER 1.0E E E E SNR 圖 4-12 不 同 周 長 的 位 元 檢 查 矩 陣 對 解 碼 效 能 的 影 響 模 擬 採 用 的 基 本 矩 陣 與 圖 4-8 相 同, 矩 陣 擴 展 的 倍 數 為 150 倍, 遞 迴 次 數 為 50 次, 分 別 產 生 消 除 cycle 的 矩 陣, 另 外 註 明 因 為 全 部 消 除 cycle-8 迴 圈 需 要 擴 展 230 倍 使 編 碼 長 度 達 8280, 為 了 減 低 運 算 量 及 對 照 低 編 碼 長 度 的 情 況, 故 此 處 採 用 展 開 150 倍 的 矩 陣 且 cycle-8 幾 乎 全 部 消 除 由 圖 4-13 得 知 消 除 cycle-8 的 矩 陣 效 能 比 其 它 兩 者 優 異, 因 為 cycle-4 與 6 保 留 太 多 cycle-8 的 迴 圈, 經 擴 展 矩 陣 之 後 產 生 更 多 迴 圈 而 使 短 迴 圈 效 果 影 響 更 明 顯 另 外 參 考 [32] 文 獻 中 模 擬 非 正 規 矩 陣 的 效 能 圖, 得 知 Girth-6 8 的 效 能 接 近, 而 Girth-10 的 效 能 與 其 它 兩 者 差 異 大 傳 統 與 改 良 式 演 算 法 在 低 編 碼 長 度 之 模 擬 比 較 綜 合 前 兩 小 節 的 論 述, 產 生 一 個 低 編 碼 長 度 的 同 位 檢 查 矩 陣 以 減 少 需 要 的 遞 迴 次 數 及 運 算 量, 達 到 低 功 耗 的 目 的 此 外 因 為 改 良 式 演 算 法 擁 有 優 先 權 的 特 44

55 性, 在 低 擴 展 倍 數 仍 然 能 有 效 打 斷 短 迴 圈 進 而 增 進 解 碼 效 能, 所 以 這 邊 將 與 傳 統 式 演 算 法 進 行 分 析 與 模 擬 模 擬 使 用 的 演 算 法 除 了 傳 統 與 改 良 式 消 去 迴 圈 演 算 法 外, 加 入 ZP 演 算 法 [33] 做 為 參 考,ZP 演 算 法 同 為 擴 展 基 本 矩 陣 的 方 式 建 構 位 元 檢 查 矩 陣, 而 每 個 元 素 1 的 位 移 量 是 由 位 移 的 公 式 算 出 : u Pxy, = T ( I), where u = (( x 1) y) mod L ( 式 4-1) 模 擬 的 方 式 分 成 兩 部 分, 因 為 演 算 法 在 擴 展 矩 陣 30 倍 時 能 將 所 有 cycle-4 6 消 除, 所 以 一 類 擴 展 倍 數 低 於 30, 以 不 同 的 倍 數 統 計 剩 下 cycle-4 6 的 總 數, 再 做 效 能 比 較 分 析 ; 另 一 類 擴 展 倍 數 介 於 30 與 200, 以 不 同 的 倍 數 統 計 剩 下 cycle 的 總 數, 最 後 做 效 能 分 析 所 有 的 模 擬 比 較 都 是 建 立 在 相 同 編 碼 長 度 的 基 礎 上, 而 遞 迴 次 數 隨 著 編 碼 長 度 調 整 (1) 編 碼 長 度 小 於 1000 之 模 擬 與 分 析 : 此 擴 展 倍 數 均 小 於 30, 主 要 分 析 兩 者 演 算 法 在 編 碼 長 度 小 於 1000, 針 對 cycle-4 6 消 除 迴 圈 的 情 形 以 及 效 能 結 果 圖 4-14 為 不 同 倍 數 下 剩 餘 短 迴 圈 的 數 量, 得 知 在 擴 展 倍 數 小 的 時 候, 傳 統 演 算 法 尚 未 執 行 至 右 半 邊 矩 陣 的 元 素 就 已 經 達 到 位 移 上 限 值, 因 此 未 打 斷 的 短 迴 圈 數 量 很 多, 而 這 些 短 迴 圈 同 時 對 效 能 造 成 影 響 模 擬 基 本 矩 陣 為 18x36 大 小 的 非 正 規 矩 陣, 擴 展 倍 數 為 10 與 20 次 遞 迴 次 數 設 為 10 與 20 次 圖 4-15 中 兩 者 效 能 差 異 並 不 大, 因 為 打 斷 迴 圈 的 效 果 有 限, 加 上 Girth-6 與 Girth-8 在 非 正 規 矩 陣 中 效 能 差 異 不 明 顯, 只 有 在 SNR=3 也 就 是 低 錯 誤 率 時 效 能 差 距 較 大 45

56 剩 餘 迴 圈 數 CE PCE ZP 擴 展 倍 數 圖 4-13 不 同 擴 展 倍 數 下 所 剩 餘 迴 圈 總 量 1.0E E-01 CL=360,Iter=10,PCE CL=360,Iter=10,CE CL=360,Iter=10,ZP 1.0E-02 BER 1.0E E E SNR 圖 4-14 PCE 與 CE 演 算 法 編 碼 長 度 為 360 之 效 能 圖 46

57 1.0E E-01 CL=720,Iter=20,PCE CL=720,Iter=20,CE CL=720,Iter=20,ZP 1.0E-02 BER 1.0E E E SNR 圖 4-15 PCE 與 CE 演 算 法 編 碼 長 度 為 720 之 效 能 圖 (2) 編 碼 長 度 於 1000 至 4000 之 模 擬 與 分 析 : 圖 4-16 為 不 同 擴 展 倍 數 下 所 剩 餘 短 迴 圈 總 量, 由 於 cycle-8 數 量 非 常 多, 所 以 傳 統 消 去 迴 圈 演 算 法 在 擴 展 60 倍 時 只 能 執 行 左 半 邊 少 許 元 素 的 位 移 動 作 而 留 下 大 量 的 迴 圈, 反 之 改 良 式 演 算 法 直 接 對 最 高 優 先 權 動 作 消 除 許 多 迴 圈, 其 中 擴 展 50 倍 之 內 已 消 除 所 有 cycle-4 6 迴 圈, 因 此 圖 4-16 也 表 示 剩 餘 cycle-8 的 數 量 模 擬 所 使 用 的 基 本 矩 陣 同 上 例, 擴 展 的 矩 陣 倍 數 為 50 與 100, 遞 迴 次 數 為 30 次 在 圖 4-17 中 SNR 大 於 1.5 時, 長 度 1800 的 效 能 曲 線 有 明 顯 差 異, 因 為 擴 展 50 倍 時 傳 統 演 算 法 所 留 下 cycle-8 的 迴 圈 數 比 改 良 式 演 算 法 高 出 許 多, 再 次 驗 證 高 SNR 低 錯 誤 率 時 短 迴 圈 的 影 響 更 大 [34] 此 外 若 為 了 省 電 採 用 低 遞 迴 次 數 解 碼, 在 圖 4-18 所 示 遞 迴 次 數 為 15 次 也 能 得 到 解 碼 效 能 的 改 進 ; 在 擴 展 100 倍 時 兩 者 演 算 法 所 留 下 的 迴 圈 數 較 接 近, 因 此 圖 4-19 反 應 效 能 上 也 比 較 相 近, 但 改 良 式 演 算 法 能 消 除 更 多 的 短 迴 圈 以 增 進 解 碼 效 能 47

58 Remaining Cycle amount CE PCE ZP Expanded Size 圖 4-16 不 同 擴 展 倍 數 下 所 剩 餘 迴 圈 總 量 1.0E E-01 CL=1800,Iter=30,PCE CL=1800,Iter=30,CE CL=1800,Iter=30,ZP 1.0E-02 BER 1.0E E E E SNR 圖 4-17 PCE 與 CE 演 算 法 編 碼 長 度 為 1800 之 效 能 圖 48

59 1.0E E-01 CL=1800,Iter=15,PCE CL=1800,Iter=15,CE CL=1800,Iter=15,ZP 1.0E-02 BER 1.0E E E SNR 圖 4-18 PCE 與 CE 演 算 法 編 碼 長 度 為 1800 之 效 能 圖 1.0E E-01 CL=3600,Iter=30,PCE CL=3600,Iter=30,CE CL=3600,Iter=30,ZP 1.0E-02 BER 1.0E E E E SNR 圖 4-19 PCE 與 CE 演 算 法 編 碼 長 度 為 3600 之 效 能 圖 49

60 第 五 章 結 論 本 篇 論 文 探 討 LDPC Codes 設 計 並 適 用 於 低 編 碼 長 度 之 應 用, 所 建 構 的 位 元 檢 查 矩 陣 採 用 Block-LDPC[17] 的 形 式 有 利 於 硬 體 上 實 現, 主 要 針 對 兩 方 面 做 演 算 法 改 良, 一 方 面 改 良 式 演 算 法 比 傳 統 式 演 算 法 節 省 大 量 運 算 及 複 雜 度, 另 一 方 面 在 不 同 的 擴 展 倍 數 均 能 有 效 打 斷 迴 圈 的 連 結 以 增 進 解 碼 效 能 改 良 式 演 算 法 以 每 個 元 素 1 的 迴 圈 總 數 決 定 優 先 順 序, 從 最 高 優 先 權 開 始 消 除 迴 圈 動 作, 充 分 利 用 每 次 打 斷 迴 圈 的 機 會 故 減 低 了 演 算 法 遞 迴 次 數, 尤 其 在 前 幾 次 遞 迴 動 作 時 有 效 減 少 大 量 迴 圈, 所 以 在 消 去 相 同 迴 圈 總 數 時, 運 算 量 相 較 傳 統 演 算 法 減 低 約 70~80%, 以 Matlab 為 模 擬 平 台 之 模 擬 時 間 減 少 約 90%, 均 可 證 明 改 良 式 演 算 法 能 節 省 大 量 運 算 及 複 雜 度 在 移 動 通 訊 或 無 線 通 訊 的 應 用 中 [35], 若 使 用 LDPC 當 作 編 解 碼 的 媒 介 而 採 用 的 矩 陣 大 多 為 短 編 碼 長 度 的 矩 陣, 因 為 長 編 碼 矩 陣 除 了 帶 來 大 量 運 算, 也 需 要 更 多 次 數 的 遞 迴 解 碼 使 效 能 收 斂, 應 用 上 更 為 耗 電 因 此 我 們 著 重 在 產 生 一 個 好 的 LDPC 矩 陣, 再 加 上 優 先 權 為 基 礎 之 特 性, 在 前 幾 次 遞 迴 運 算 時 就 能 打 斷 大 量 迴 圈, 能 越 早 消 除 大 量 迴 圈 則 在 低 擴 展 倍 數 時 越 有 利, 因 為 遞 迴 次 數 的 增 加 讓 位 移 值 的 選 擇 越 來 越 少 所 以 模 擬 編 碼 長 度 在 4000 位 元 以 下 的 矩 陣 作 為 解 碼 矩 陣, 解 碼 的 效 能 上 均 比 其 它 兩 種 相 同 架 構 的 演 算 法 要 來 得 優 異, 尤 其 在 低 錯 誤 率 時 效 能 增 進 更 明 顯, 突 顯 出 低 編 碼 長 度 時 能 夠 有 效 率 消 除 迴 圈, 適 用 於 省 電 或 低 運 算 量 等 通 訊 系 統 50

61 參 考 文 獻 [1] C. E. Shannon, A Mathematical Theory of Communication, Bell Syst. Tech. J., pp (Part 1); pp (Part 2), July [2] Shu Lin, D. J. Costello, Error Control Coding 2nd ed., Person-Prentice Hall, [3] E. R. Berlekamp, Algebraic Coding Theory, McGraw-Hill, New York, 1968; Rev. ed., Aegean Park Press, Laguna Hills, N. Y., [4] P. Elias, Coding for Noisy Channels, IRE Conv. Rec., p. 4:37-47, [5] E. Prange, Cyclic Error-Correcting Codes in Two Symbols, AFCRC-TN-57, 103, Air Force Cambridge Research Center, Cambridge, Mass., September [6] I. S. Read and G. Solomon, Polynomial Codes over Certain Fields, J. Soc. Ind. App. Math., 8: , June [7] R. G. Gallager, Low-Density Parity-Check Codes. Cambridge, MA: MIT Press, [8] C. Berrou, A. Glavieux, and P. Thitimajshima, Near Shannon Limit Error-Correcting Coding and Decoding: Turbo Codes, IEEE Intl. Conf. Commun., pp , Geneva, Switzerland, May [9] D.J.C Mackay and R.M Neal, Near Shannon limit performance of low-density parity-check codes, Electron. Lett. vol.32, pp , Aug [10] N. Wiberg, Codes and Decoding on General Graphs, IEEE Conf. Inf. Theory, p.468, Sep [11] A. Delvarathinam, E. Kim, and G. Choi, Low-Density Parity-Check Decoder Architecture for High Throughput Optical Fiber Channels, IEEE Intl. Conf. Comp. Design, pp ,

62 [12] A. J. Blanksby and C. J. Howland, A 690-mW 1-Gb/s 1024-b, rate-1/2 Low-Density Parity-Check Code Decoder, IEEE Trans. Solid-State Circuits, vol. 37, no.3, pp , Mar [13] T. Richardson and R. Urbanke, Efficient encoding of Low-Density Parity-Check Codes, IEEE Trans. Inf. Theory, vol. 47, no. 2, pp , Feb [14] T. Richardson, A. Shokrollahi, and R. Urbanke, Design of Capacity Approaching Low-Density Parity-Check Codes, IEEE Trans. Inf. Theory, vol.47, no.2, pp , Feb [15] R. MICHAEL TANNER, A Recursive Approach to Low Complexity Codes, IEEE Trans. Inf. Theory, vol.27, no.2, pp , Sep [16] D. J. C. MacKay, Good error-correcting codes based on very sparse matrices, IEEE Trans. Inf. Theory, vol. 45, no. 2, pp , Mar [17] M. Chiani, A. Conti, and A. Ventura, Evaluation of Low-Density Parity-Check Codes Over Block Fading Channels, IEEE Conf. Commun., vol.3 pp , June [18] F. R. Kschischang, B. J. Frey, and H. A. Loeliger, Factor Graphs and the Sum-Product Algorithm, IEEE Trans. Inf. Theory, vol. 47, pp , Feb [19] 朱 元 志, 低 密 度 對 偶 檢 查 碼 之 改 進 以 及 其 解 碼 器 之 超 大 型 積 體 電 路 實 現, 國 立 交 通 大 學 論 文, [20] Xiao-Yu Hu, E. Eleftheriou, D. M. Arnold, A. Dholakia, Efficient Implementations of the Sum-Product Algorithm for Decoding LDPC, IEEE Conf. Globe Telecom, pp E, Nov

63 [21] Lei Yang, Hui Liu, C.-J Richard Shi, Code Construction and FPGA Implementation of a Low-Error-Floor Multi-Rate Low-Density Parity-Check Code Decoder, IEEE Trans. Circuit and Systems, vol. 53, no. 4, Apr [22] D. E. Hocevar, LDPC Code Construction with Flexible Hardware Implementation, IEEE Conf. Commun., vol.4, pp , May [23] K. Shimizu, T. Ishikawa, N. Togawa, T. Ikenaga, S. Goto, Partially-Parallel LDPC Decoder Based on High-Efficiency Message-Passing Algorithm, IEEE Conf. Com., pp , Oct [24] X. Y. Hu, E. Eleftheriou, and D. M. Arnold, Progressive Edge-Growth Tanner Graphs, IEEE Conf. Global Telecomm., vol. 2, pp , Nov [25] J. Campello, D. S. Modha, and S. Rajagopalan, Designing LDPC Codes Using Bit-Filling, IEEE Conf. Com., pp , June [26] H. Zhang and T. Zhang, Design of VLSI Implementation-Oriented LDPC Codes, IEEE Conf. Technol., vol. 1, pp , Oct [27] L.Yang, H. Liu, and C.-J. R. Shi, Cycle Elimination Method to Construct VLSI Oriented LDPC Codes, IEEE Technol. Conf., pp , Sep [28] D. J. C. Mackay, S. T. Wilson, and M. C. Davey, Comparison of Constructions of Irregular Gallager Codes, IEEE Trans. Comm., vol. 47, pp , Oct [29] T. Tian, C. Jones, J. D. Villasenor, and R. D.Wesel, Construction of Irregular LDPC Codes with Low Error Floors, IEEE Conf. Com., vol. 5, pp , May [30] T. Richardson, Error Floors of LDPC Codes, IEEE Conf. Commun., pp , Oct [31] H. Zhang and T. Zhang, Block-LDPC: A Practical LDPC Coding System Design Approach, IEEE Trans. Circuits and Systems, vol. 52, no. 4, Apr

64 [32] Campello J., Modha D.S., Extended Bit-Filling and LDPC Code Design, IEEE Conf. Global Telecomm., vol. 2, pp , Nov [33] T. Zhang and K. K. Parhi, VLSI Implementation-Oriented (3,k)-Regular Low-Density Parity-Check Codes, IEEE Conf. Signal Process, pp , Sep [34] J. M. F. Moura, Jin Lu, Haotian Zhang, Structured Low-Density Parity-Check Codes, IEEE Trans. Signal Process, vol. 21, pp.42-55, Jan [35] IEEE e-2005, IEEE Standard for Local and Metropolitan Area Network - Part 16: Air Interface for Fixed and Mobile Broadband Wireless Access Systems Amendment 2: Physical and Medium Access Control layers for Combined Fixed and Mobile Operation in Licensed Bands,